/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Richard Wilbur
  • Date: 2016-02-04 19:07:28 UTC
  • mto: This revision was merged to the branch mainline in revision 6618.
  • Revision ID: richard.wilbur@gmail.com-20160204190728-p0zvfii6zase0fw7
Update COPYING.txt from the original http://www.gnu.org/licenses/gpl-2.0.txt  (Only differences were in whitespace.)  Thanks to Petr Stodulka for pointing out the discrepancy.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
18
18
 
19
19
import time
20
20
 
21
 
from . import (
 
21
from bzrlib import (
22
22
    debug,
23
23
    errors,
24
24
    osutils,
25
25
    revision,
26
26
    trace,
27
27
    )
28
 
from .sixish import (
29
 
    viewitems,
30
 
    viewvalues,
31
 
    )
32
28
 
33
29
STEP_UNIQUE_SEARCHER_EVERY = 5
34
30
 
339
335
        """
340
336
        parent_map = self._parents_provider.get_parent_map(keys)
341
337
        parent_child = {}
342
 
        for child, parents in sorted(viewitems(parent_map)):
 
338
        for child, parents in sorted(parent_map.items()):
343
339
            for parent in parents:
344
340
                parent_child.setdefault(parent, []).append(child)
345
341
        return parent_child
362
358
        NULL_REVISION = revision.NULL_REVISION
363
359
        known_revnos[NULL_REVISION] = 0
364
360
 
365
 
        searching_known_tips = list(known_revnos)
 
361
        searching_known_tips = list(known_revnos.keys())
366
362
 
367
363
        unknown_searched = {}
368
364
 
369
365
        while cur_tip not in known_revnos:
370
366
            unknown_searched[cur_tip] = num_steps
371
367
            num_steps += 1
372
 
            to_search = {cur_tip}
 
368
            to_search = set([cur_tip])
373
369
            to_search.update(searching_known_tips)
374
370
            parent_map = self.get_parent_map(to_search)
375
371
            parents = parent_map.get(cur_tip, None)
485
481
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
486
482
        # we know that unique_revisions aren't in common_revisions, so skip
487
483
        # past them.
488
 
        next(unique_searcher)
 
484
        unique_searcher.next()
489
485
        common_searcher = self._make_breadth_first_searcher(common_revisions)
490
486
 
491
487
        # As long as we are still finding unique nodes, keep searching
649
645
        # TODO: it might be possible to collapse searchers faster when they
650
646
        #       only have *some* search tips in common.
651
647
        next_unique_searchers = []
652
 
        for searchers in viewvalues(unique_search_tips):
 
648
        for searchers in unique_search_tips.itervalues():
653
649
            if len(searchers) == 1:
654
650
                # Searching unique tips, go for it
655
651
                next_unique_searchers.append(searchers[0])
832
828
            # NULL_REVISION is only a head if it is the only entry
833
829
            candidate_heads.remove(revision.NULL_REVISION)
834
830
            if not candidate_heads:
835
 
                return {revision.NULL_REVISION}
 
831
                return set([revision.NULL_REVISION])
836
832
        if len(candidate_heads) < 2:
837
833
            return candidate_heads
838
834
        searchers = dict((c, self._make_breadth_first_searcher([c]))
839
835
                          for c in candidate_heads)
840
836
        active_searchers = dict(searchers)
841
837
        # skip over the actual candidate for each searcher
842
 
        for searcher in viewvalues(active_searchers):
843
 
            next(searcher)
 
838
        for searcher in active_searchers.itervalues():
 
839
            searcher.next()
844
840
        # The common walker finds nodes that are common to two or more of the
845
841
        # input keys, so that we don't access all history when a currently
846
842
        # uncommon search point actually meets up with something behind a
852
848
            ancestors = set()
853
849
            # advance searches
854
850
            try:
855
 
                next(common_walker)
 
851
                common_walker.next()
856
852
            except StopIteration:
857
853
                # No common points being searched at this time.
858
854
                pass
859
 
            for candidate in list(active_searchers):
 
855
            for candidate in active_searchers.keys():
860
856
                try:
861
857
                    searcher = active_searchers[candidate]
862
858
                except KeyError:
865
861
                    # a descendant of another candidate.
866
862
                    continue
867
863
                try:
868
 
                    ancestors.update(next(searcher))
 
864
                    ancestors.update(searcher.next())
869
865
                except StopIteration:
870
866
                    del active_searchers[candidate]
871
867
                    continue
881
877
                if ancestor in common_walker.seen:
882
878
                    # some searcher has encountered our known common nodes:
883
879
                    # just stop it
884
 
                    ancestor_set = {ancestor}
885
 
                    for searcher in viewvalues(searchers):
 
880
                    ancestor_set = set([ancestor])
 
881
                    for searcher in searchers.itervalues():
886
882
                        searcher.stop_searching_any(ancestor_set)
887
883
                else:
888
884
                    # or it may have been just reached by all the searchers:
889
 
                    for searcher in viewvalues(searchers):
 
885
                    for searcher in searchers.itervalues():
890
886
                        if ancestor not in searcher.seen:
891
887
                            break
892
888
                    else:
894
890
                        # making it be known as a descendant of all candidates,
895
891
                        # so we can stop searching it, and any seen ancestors
896
892
                        new_common.add(ancestor)
897
 
                        for searcher in viewvalues(searchers):
 
893
                        for searcher in searchers.itervalues():
898
894
                            seen_ancestors =\
899
895
                                searcher.find_seen_ancestors([ancestor])
900
896
                            searcher.stop_searching_any(seen_ancestors)
1017
1013
            processed.update(pending)
1018
1014
            next_map = self.get_parent_map(pending)
1019
1015
            next_pending = set()
1020
 
            for item in viewitems(next_map):
 
1016
            for item in next_map.iteritems():
1021
1017
                yield item
1022
1018
                next_pending.update(p for p in item[1] if p not in processed)
1023
1019
            ghosts = pending.difference(next_map)
1051
1047
        An ancestor may sort after a descendant if the relationship is not
1052
1048
        visible in the supplied list of revisions.
1053
1049
        """
1054
 
        from breezy import tsort
 
1050
        from bzrlib import tsort
1055
1051
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
1056
1052
        return sorter.iter_topo_order()
1057
1053
 
1062
1058
        smallest number of parent lookups to determine the ancestral
1063
1059
        relationship between N revisions.
1064
1060
        """
1065
 
        return {candidate_descendant} == self.heads(
 
1061
        return set([candidate_descendant]) == self.heads(
1066
1062
            [candidate_ancestor, candidate_descendant])
1067
1063
 
1068
1064
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
1253
1249
        ## for revision in revisions.intersection(descendants):
1254
1250
        ##   simple_ancestors.difference_update(descendants[revision])
1255
1251
        ## return simple_ancestors
1256
 
        for revision, parent_ids in viewitems(parent_map):
 
1252
        for revision, parent_ids in parent_map.iteritems():
1257
1253
            if parent_ids is None:
1258
1254
                continue
1259
1255
            for parent_id in parent_ids:
1374
1370
        included_keys = self.seen.difference(excludes)
1375
1371
        return self._started_keys, excludes, included_keys
1376
1372
 
 
1373
    def _get_result(self):
 
1374
        """Get a SearchResult for the current state of this searcher.
 
1375
 
 
1376
        :return: A SearchResult for this search so far. The SearchResult is
 
1377
            static - the search can be advanced and the search result will not
 
1378
            be invalidated or altered.
 
1379
        """
 
1380
        from bzrlib.vf_search import SearchResult
 
1381
        (started_keys, excludes, included_keys) = self.get_state()
 
1382
        return SearchResult(started_keys, excludes, len(included_keys),
 
1383
            included_keys)
 
1384
 
1377
1385
    def step(self):
1378
1386
        try:
1379
 
            return next(self)
 
1387
            return self.next()
1380
1388
        except StopIteration:
1381
1389
            return ()
1382
1390
 
1383
 
    def __next__(self):
 
1391
    def next(self):
1384
1392
        """Return the next ancestors of this revision.
1385
1393
 
1386
1394
        Ancestors are returned in the order they are seen in a breadth-first
1406
1414
        self.seen.update(self._next_query)
1407
1415
        return self._next_query
1408
1416
 
1409
 
    next = __next__
1410
 
 
1411
1417
    def next_with_ghosts(self):
1412
1418
        """Return the next found ancestors, with ghosts split out.
1413
1419
 
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 viewitems(parent_map):
 
1469
        for rev_id, parents in parent_map.iteritems():
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 viewvalues(parent_map):
 
1512
            for parent_ids in parent_map.itervalues():
1507
1513
                all_parents.extend(parent_ids)
1508
1514
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
1509
1515
            seen_ancestors.update(next_pending)
1548
1554
                    stop_rev_references[parent_id] += 1
1549
1555
            # if only the stopped revisions reference it, the ref count will be
1550
1556
            # 0 after this loop
1551
 
            for parents in viewvalues(self._current_parents):
 
1557
            for parents in self._current_parents.itervalues():
1552
1558
                for parent_id in parents:
1553
1559
                    try:
1554
1560
                        stop_rev_references[parent_id] -= 1
1555
1561
                    except KeyError:
1556
1562
                        pass
1557
1563
            stop_parents = set()
1558
 
            for rev_id, refs in viewitems(stop_rev_references):
 
1564
            for rev_id, refs in stop_rev_references.iteritems():
1559
1565
                if refs == 0:
1560
1566
                    stop_parents.add(rev_id)
1561
1567
            self._next_query.difference_update(stop_parents)
1591
1597
def invert_parent_map(parent_map):
1592
1598
    """Given a map from child => parents, create a map of parent=>children"""
1593
1599
    child_map = {}
1594
 
    for child, parents in viewitems(parent_map):
 
1600
    for child, parents in parent_map.iteritems():
1595
1601
        for p in parents:
1596
1602
            # Any given parent is likely to have only a small handful
1597
1603
            # of children, many will have only one. So we avoid mem overhead of
1643
1649
    # Will not have any nodes removed, even though you do have an
1644
1650
    # 'uninteresting' linear D->B and E->C
1645
1651
    children = {}
1646
 
    for child, parents in viewitems(parent_map):
 
1652
    for child, parents in parent_map.iteritems():
1647
1653
        children.setdefault(child, [])
1648
1654
        for p in parents:
1649
1655
            children.setdefault(p, []).append(child)
1689
1695
        """See Graph.heads()"""
1690
1696
        as_keys = [(i,) for i in ids]
1691
1697
        head_keys = self._graph.heads(as_keys)
1692
 
        return {h[0] for h in head_keys}
 
1698
        return set([h[0] for h in head_keys])
1693
1699
 
1694
1700
    def merge_sort(self, tip_revision):
1695
1701
        nodes = self._graph.merge_sort((tip_revision,))
1701
1707
        self._graph.add_node((revision,), [(p,) for p in parents])
1702
1708
 
1703
1709
 
1704
 
_counters = [0, 0, 0, 0, 0, 0, 0]
 
1710
_counters = [0,0,0,0,0,0,0]
1705
1711
try:
1706
 
    from ._known_graph_pyx import KnownGraph
1707
 
except ImportError as e:
 
1712
    from bzrlib._known_graph_pyx import KnownGraph
 
1713
except ImportError, e:
1708
1714
    osutils.failed_to_load_extension(e)
1709
 
    from ._known_graph_py import KnownGraph
 
1715
    from bzrlib._known_graph_py import KnownGraph