/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/graph.py

• browse files at revision 7490.77.11
• compare with another revision
• download diff
• download tarball
• view history from revision 7490.77.11

• reverse the comparison (7490.77.11 to 7527)
• stop comparing with revision 7527

Show diffs side-by-side

added

removed

breezy/graph.py

14

14

# along with this program; if not, write to the Free Software

15

15

# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

16

16

 

 

17

from __future__ import absolute_import

 

18

 

17

19

import time

18

20

 

19

21

from . import (

23

25

    revision,

24

26

    trace,

25

27

    )

 

28

from .sixish import (

 

29

    viewitems,

 

30

    viewvalues,

 

31

    )

26

32

 

27

33

STEP_UNIQUE_SEARCHER_EVERY = 5

28

34

 

337

343

        """

338

344

        parent_map = self._parents_provider.get_parent_map(keys)

339

345

        parent_child = {}

340

 

        for child, parents in sorted(parent_map.items()):

 

346

        for child, parents in sorted(viewitems(parent_map)):

341

347

            for parent in parents:

342

348

                parent_child.setdefault(parent, []).append(child)

343

349

        return parent_child

648

654

        # TODO: it might be possible to collapse searchers faster when they

649

655

        #       only have *some* search tips in common.

650

656

        next_unique_searchers = []

651

 

        for searchers in unique_search_tips.values():

 

657

        for searchers in viewvalues(unique_search_tips):

652

658

            if len(searchers) == 1:

653

659

                # Searching unique tips, go for it

654

660

                next_unique_searchers.append(searchers[0])

837

843

                         for c in candidate_heads)

838

844

        active_searchers = dict(searchers)

839

845

        # skip over the actual candidate for each searcher

840

 

        for searcher in active_searchers.values():

 

846

        for searcher in viewvalues(active_searchers):

841

847

            next(searcher)

842

848

        # The common walker finds nodes that are common to two or more of the

843

849

        # input keys, so that we don't access all history when a currently

880

886

                    # some searcher has encountered our known common nodes:

881

887

                    # just stop it

882

888

                    ancestor_set = {ancestor}

883

 

                    for searcher in searchers.values():

 

889

                    for searcher in viewvalues(searchers):

884

890

                        searcher.stop_searching_any(ancestor_set)

885

891

                else:

886

892

                    # or it may have been just reached by all the searchers:

887

 

                    for searcher in searchers.values():

 

893

                    for searcher in viewvalues(searchers):

888

894

                        if ancestor not in searcher.seen:

889

895

                            break

890

896

                    else:

892

898

                        # making it be known as a descendant of all candidates,

893

899

                        # so we can stop searching it, and any seen ancestors

894

900

                        new_common.add(ancestor)

895

 

                        for searcher in searchers.values():

 

901

                        for searcher in viewvalues(searchers):

896

902

                            seen_ancestors =\

897

903

                                searcher.find_seen_ancestors([ancestor])

898

904

                            searcher.stop_searching_any(seen_ancestors)

1015

1021

            processed.update(pending)

1016

1022

            next_map = self.get_parent_map(pending)

1017

1023

            next_pending = set()

1018

 

            for item in next_map.items():

 

1024

            for item in viewitems(next_map):

1019

1025

                yield item

1020

1026

                next_pending.update(p for p in item[1] if p not in processed)

1021

1027

            ghosts = pending.difference(next_map)

1253

1259

        # for revision in revisions.intersection(descendants):

1254

1260

        # simple_ancestors.difference_update(descendants[revision])

1255

1261

        # return simple_ancestors

1256

 

        for revision, parent_ids in parent_map.items():

 

1262

        for revision, parent_ids in viewitems(parent_map):

1257

1263

            if parent_ids is None:

1258

1264

                continue

1259

1265

            for parent_id in parent_ids:

1460

1466

        seen.update(revisions)

1461

1467

        parent_map = self._parents_provider.get_parent_map(revisions)

1462

1468

        found_revisions.update(parent_map)

1463

 

        for rev_id, parents in parent_map.items():

 

1469

        for rev_id, parents in viewitems(parent_map):

1464

1470

            if parents is None:

1465

1471

                continue

1466

1472

            new_found_parents = [p for p in parents if p not in seen]

1503

1509

            all_parents = []

1504

1510

            # We don't care if it is a ghost, since it can't be seen if it is

1505

1511

            # a ghost

1506

 

            for parent_ids in parent_map.values():

 

1512

            for parent_ids in viewvalues(parent_map):

1507

1513

                all_parents.extend(parent_ids)

1508

1514

            next_pending = all_seen.intersection(

1509

1515

                all_parents).difference(seen_ancestors)

1549

1555

                    stop_rev_references[parent_id] += 1

1550

1556

            # if only the stopped revisions reference it, the ref count will be

1551

1557

            # 0 after this loop

1552

 

            for parents in self._current_parents.values():

 

1558

            for parents in viewvalues(self._current_parents):

1553

1559

                for parent_id in parents:

1554

1560

                    try:

1555

1561

                        stop_rev_references[parent_id] -= 1

1556

1562

                    except KeyError:

1557

1563

                        pass

1558

1564

            stop_parents = set()

1559

 

            for rev_id, refs in stop_rev_references.items():

 

1565

            for rev_id, refs in viewitems(stop_rev_references):

1560

1566

                if refs == 0:

1561

1567

                    stop_parents.add(rev_id)

1562

1568

            self._next_query.difference_update(stop_parents)

1592

1598

def invert_parent_map(parent_map):

1593

1599

    """Given a map from child => parents, create a map of parent=>children"""

1594

1600

    child_map = {}

1595

 

    for child, parents in parent_map.items():

 

1601

    for child, parents in viewitems(parent_map):

1596

1602

        for p in parents:

1597

1603

            # Any given parent is likely to have only a small handful

1598

1604

            # of children, many will have only one. So we avoid mem overhead of

1644

1650

    # Will not have any nodes removed, even though you do have an

1645

1651

    # 'uninteresting' linear D->B and E->C

1646

1652

    children = {}

1647

 

    for child, parents in parent_map.items():

 

1653

    for child, parents in viewitems(parent_map):

1648

1654

        children.setdefault(child, [])

1649

1655

        for p in parents:

1650

1656

            children.setdefault(p, []).append(child)

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0