/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/graph.py

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

• reverse the comparison (7501 to 7490.22.1)
• stop comparing with revision 7490.22.1

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

 

 

19

17

import time

20

18

 

21

19

from . import (

25

23

    revision,

26

24

    trace,

27

25

    )

28

 

from .sixish import (

29

 

    viewitems,

30

 

    viewvalues,

31

 

    )

32

26

 

33

27

STEP_UNIQUE_SEARCHER_EVERY = 5

34

28

 

343

337

        """

344

338

        parent_map = self._parents_provider.get_parent_map(keys)

345

339

        parent_child = {}

346

 

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

 

340

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

347

341

            for parent in parents:

348

342

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

349

343

        return parent_child

654

648

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

655

649

        #       only have *some* search tips in common.

656

650

        next_unique_searchers = []

657

 

        for searchers in viewvalues(unique_search_tips):

 

651

        for searchers in unique_search_tips.values():

658

652

            if len(searchers) == 1:

659

653

                # Searching unique tips, go for it

660

654

                next_unique_searchers.append(searchers[0])

843

837

                         for c in candidate_heads)

844

838

        active_searchers = dict(searchers)

845

839

        # skip over the actual candidate for each searcher

846

 

        for searcher in viewvalues(active_searchers):

 

840

        for searcher in active_searchers.values():

847

841

            next(searcher)

848

842

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

849

843

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

886

880

                    # some searcher has encountered our known common nodes:

887

881

                    # just stop it

888

882

                    ancestor_set = {ancestor}

889

 

                    for searcher in viewvalues(searchers):

 

883

                    for searcher in searchers.values():

890

884

                        searcher.stop_searching_any(ancestor_set)

891

885

                else:

892

886

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

893

 

                    for searcher in viewvalues(searchers):

 

887

                    for searcher in searchers.values():

894

888

                        if ancestor not in searcher.seen:

895

889

                            break

896

890

                    else:

898

892

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

899

893

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

900

894

                        new_common.add(ancestor)

901

 

                        for searcher in viewvalues(searchers):

 

895

                        for searcher in searchers.values():

902

896

                            seen_ancestors =\

903

897

                                searcher.find_seen_ancestors([ancestor])

904

898

                            searcher.stop_searching_any(seen_ancestors)

1021

1015

            processed.update(pending)

1022

1016

            next_map = self.get_parent_map(pending)

1023

1017

            next_pending = set()

1024

 

            for item in viewitems(next_map):

 

1018

            for item in next_map.items():

1025

1019

                yield item

1026

1020

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

1027

1021

            ghosts = pending.difference(next_map)

1259

1253

        # for revision in revisions.intersection(descendants):

1260

1254

        # simple_ancestors.difference_update(descendants[revision])

1261

1255

        # return simple_ancestors

1262

 

        for revision, parent_ids in viewitems(parent_map):

 

1256

        for revision, parent_ids in parent_map.items():

1263

1257

            if parent_ids is None:

1264

1258

                continue

1265

1259

            for parent_id in parent_ids:

1466

1460

        seen.update(revisions)

1467

1461

        parent_map = self._parents_provider.get_parent_map(revisions)

1468

1462

        found_revisions.update(parent_map)

1469

 

        for rev_id, parents in viewitems(parent_map):

 

1463

        for rev_id, parents in parent_map.items():

1470

1464

            if parents is None:

1471

1465

                continue

1472

1466

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

1509

1503

            all_parents = []

1510

1504

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

1511

1505

            # a ghost

1512

 

            for parent_ids in viewvalues(parent_map):

 

1506

            for parent_ids in parent_map.values():

1513

1507

                all_parents.extend(parent_ids)

1514

1508

            next_pending = all_seen.intersection(

1515

1509

                all_parents).difference(seen_ancestors)

1555

1549

                    stop_rev_references[parent_id] += 1

1556

1550

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

1557

1551

            # 0 after this loop

1558

 

            for parents in viewvalues(self._current_parents):

 

1552

            for parents in self._current_parents.values():

1559

1553

                for parent_id in parents:

1560

1554

                    try:

1561

1555

                        stop_rev_references[parent_id] -= 1

1562

1556

                    except KeyError:

1563

1557

                        pass

1564

1558

            stop_parents = set()

1565

 

            for rev_id, refs in viewitems(stop_rev_references):

 

1559

            for rev_id, refs in stop_rev_references.items():

1566

1560

                if refs == 0:

1567

1561

                    stop_parents.add(rev_id)

1568

1562

            self._next_query.difference_update(stop_parents)

1598

1592

def invert_parent_map(parent_map):

1599

1593

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

1600

1594

    child_map = {}

1601

 

    for child, parents in viewitems(parent_map):

 

1595

    for child, parents in parent_map.items():

1602

1596

        for p in parents:

1603

1597

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

1604

1598

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

1650

1644

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

1651

1645

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

1652

1646

    children = {}

1653

 

    for child, parents in viewitems(parent_map):

 

1647

    for child, parents in parent_map.items():

1654

1648

        children.setdefault(child, [])

1655

1649

        for p in parents:

1656

1650

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

• Older »

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