~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Vincent Ladeuil
  • Date: 2010-02-10 15:46:03 UTC
  • mfrom: (4985.3.21 update)
  • mto: This revision was merged to the branch mainline in revision 5021.
  • Revision ID: v.ladeuil+lp@free.fr-20100210154603-k4no1gvfuqpzrw7p
Update performs two merges in a more logical order but stop on conflicts

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
import time
18
18
 
19
19
from bzrlib import (
20
20
    debug,
21
21
    errors,
 
22
    osutils,
22
23
    revision,
23
 
    symbol_versioning,
24
24
    trace,
25
 
    tsort,
26
25
    )
 
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
27
 
28
28
STEP_UNIQUE_SEARCHER_EVERY = 5
29
29
 
60
60
        return 'DictParentsProvider(%r)' % self.ancestry
61
61
 
62
62
    def get_parent_map(self, keys):
63
 
        """See _StackedParentsProvider.get_parent_map"""
 
63
        """See StackedParentsProvider.get_parent_map"""
64
64
        ancestry = self.ancestry
65
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
66
 
67
 
 
68
 
class _StackedParentsProvider(object):
69
 
 
 
67
@deprecated_function(deprecated_in((1, 16, 0)))
 
68
def _StackedParentsProvider(*args, **kwargs):
 
69
    return StackedParentsProvider(*args, **kwargs)
 
70
 
 
71
class StackedParentsProvider(object):
 
72
    """A parents provider which stacks (or unions) multiple providers.
 
73
    
 
74
    The providers are queries in the order of the provided parent_providers.
 
75
    """
 
76
    
70
77
    def __init__(self, parent_providers):
71
78
        self._parent_providers = parent_providers
72
79
 
73
80
    def __repr__(self):
74
 
        return "_StackedParentsProvider(%r)" % self._parent_providers
 
81
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
75
82
 
76
83
    def get_parent_map(self, keys):
77
84
        """Get a mapping of keys => parents
121
128
            self._get_parent_map = self._real_provider.get_parent_map
122
129
        else:
123
130
            self._get_parent_map = get_parent_map
124
 
        self._cache = {}
125
 
        self._cache_misses = True
 
131
        self._cache = None
 
132
        self.enable_cache(True)
126
133
 
127
134
    def __repr__(self):
128
135
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
133
140
            raise AssertionError('Cache enabled when already enabled.')
134
141
        self._cache = {}
135
142
        self._cache_misses = cache_misses
 
143
        self.missing_keys = set()
136
144
 
137
145
    def disable_cache(self):
138
146
        """Disable and clear the cache."""
139
147
        self._cache = None
 
148
        self._cache_misses = None
 
149
        self.missing_keys = set()
140
150
 
141
151
    def get_cached_map(self):
142
152
        """Return any cached get_parent_map values."""
143
153
        if self._cache is None:
144
154
            return None
145
 
        return dict((k, v) for k, v in self._cache.items()
146
 
                    if v is not None)
 
155
        return dict(self._cache)
147
156
 
148
157
    def get_parent_map(self, keys):
149
 
        """See _StackedParentsProvider.get_parent_map."""
150
 
        # Hack to build up the caching logic.
151
 
        ancestry = self._cache
152
 
        if ancestry is None:
153
 
            # Caching is disabled.
154
 
            missing_revisions = set(keys)
155
 
            ancestry = {}
 
158
        """See StackedParentsProvider.get_parent_map."""
 
159
        cache = self._cache
 
160
        if cache is None:
 
161
            cache = self._get_parent_map(keys)
156
162
        else:
157
 
            missing_revisions = set(key for key in keys if key not in ancestry)
158
 
        if missing_revisions:
159
 
            parent_map = self._get_parent_map(missing_revisions)
160
 
            ancestry.update(parent_map)
161
 
            if self._cache_misses:
162
 
                # None is never a valid parents list, so it can be used to
163
 
                # record misses.
164
 
                ancestry.update(dict((k, None) for k in missing_revisions
165
 
                                     if k not in parent_map))
166
 
        present_keys = [k for k in keys if ancestry.get(k) is not None]
167
 
        return dict((k, ancestry[k]) for k in present_keys)
 
163
            needed_revisions = set(key for key in keys if key not in cache)
 
164
            # Do not ask for negatively cached keys
 
165
            needed_revisions.difference_update(self.missing_keys)
 
166
            if needed_revisions:
 
167
                parent_map = self._get_parent_map(needed_revisions)
 
168
                cache.update(parent_map)
 
169
                if self._cache_misses:
 
170
                    for key in needed_revisions:
 
171
                        if key not in parent_map:
 
172
                            self.note_missing_key(key)
 
173
        result = {}
 
174
        for key in keys:
 
175
            value = cache.get(key)
 
176
            if value is not None:
 
177
                result[key] = value
 
178
        return result
 
179
 
 
180
    def note_missing_key(self, key):
 
181
        """Note that key is a missing key."""
 
182
        if self._cache_misses:
 
183
            self.missing_keys.add(key)
168
184
 
169
185
 
170
186
class Graph(object):
295
311
        # get there.
296
312
        return known_revnos[cur_tip] + num_steps
297
313
 
 
314
    def find_lefthand_distances(self, keys):
 
315
        """Find the distance to null for all the keys in keys.
 
316
 
 
317
        :param keys: keys to lookup.
 
318
        :return: A dict key->distance for all of keys.
 
319
        """
 
320
        # Optimisable by concurrent searching, but a random spread should get
 
321
        # some sort of hit rate.
 
322
        result = {}
 
323
        known_revnos = []
 
324
        ghosts = []
 
325
        for key in keys:
 
326
            try:
 
327
                known_revnos.append(
 
328
                    (key, self.find_distance_to_null(key, known_revnos)))
 
329
            except errors.GhostRevisionsHaveNoRevno:
 
330
                ghosts.append(key)
 
331
        for key in ghosts:
 
332
            known_revnos.append((key, -1))
 
333
        return dict(known_revnos)
 
334
 
298
335
    def find_unique_ancestors(self, unique_revision, common_revisions):
299
336
        """Find the unique ancestors for a revision versus others.
300
337
 
551
588
    def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
552
589
                             unique_tip_searchers, common_searcher):
553
590
        """Steps 5-8 of find_unique_ancestors.
554
 
        
 
591
 
555
592
        This function returns when common_searcher has stopped searching for
556
593
        more nodes.
557
594
        """
600
637
                                 all_unique_searcher._iterations)
601
638
            unique_tip_searchers = next_unique_searchers
602
639
 
603
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
604
 
    def get_parents(self, revisions):
605
 
        """Find revision ids of the parents of a list of revisions
606
 
 
607
 
        A list is returned of the same length as the input.  Each entry
608
 
        is a list of parent ids for the corresponding input revision.
609
 
 
610
 
        [NULL_REVISION] is used as the parent of the first user-committed
611
 
        revision.  Its parent list is empty.
612
 
 
613
 
        If the revision is not present (i.e. a ghost), None is used in place
614
 
        of the list of parents.
615
 
 
616
 
        Deprecated in bzr 1.2 - please see get_parent_map.
617
 
        """
618
 
        parents = self.get_parent_map(revisions)
619
 
        return [parents.get(r, None) for r in revisions]
620
 
 
621
640
    def get_parent_map(self, revisions):
622
641
        """Get a map of key:parent_list for revisions.
623
642
 
907
926
        An ancestor may sort after a descendant if the relationship is not
908
927
        visible in the supplied list of revisions.
909
928
        """
 
929
        from bzrlib import tsort
910
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
911
931
        return sorter.iter_topo_order()
912
932
 
1209
1229
 
1210
1230
    def get_result(self):
1211
1231
        """Get a SearchResult for the current state of this searcher.
1212
 
        
 
1232
 
1213
1233
        :return: A SearchResult for this search so far. The SearchResult is
1214
1234
            static - the search can be advanced and the search result will not
1215
1235
            be invalidated or altered.
1219
1239
            # exclude keys for them. However, while we could have a second
1220
1240
            # look-ahead result buffer and shuffle things around, this method
1221
1241
            # is typically only called once per search - when memoising the
1222
 
            # results of the search. 
 
1242
            # results of the search.
1223
1243
            found, ghosts, next, parents = self._do_query(self._next_query)
1224
1244
            # pretend we didn't query: perhaps we should tweak _do_query to be
1225
1245
            # entirely stateless?
1266
1286
 
1267
1287
    def next_with_ghosts(self):
1268
1288
        """Return the next found ancestors, with ghosts split out.
1269
 
        
 
1289
 
1270
1290
        Ancestors are returned in the order they are seen in a breadth-first
1271
1291
        traversal.  No ancestor will be returned more than once. Ancestors are
1272
1292
        returned only after asking for their parents, which allows us to detect
1331
1351
 
1332
1352
    def find_seen_ancestors(self, revisions):
1333
1353
        """Find ancestors of these revisions that have already been seen.
1334
 
        
 
1354
 
1335
1355
        This function generally makes the assumption that querying for the
1336
1356
        parents of a node that has already been queried is reasonably cheap.
1337
1357
        (eg, not a round trip to a remote host).
1393
1413
                self._current_ghosts.intersection(revisions))
1394
1414
            self._current_present.difference_update(stopped)
1395
1415
            self._current_ghosts.difference_update(stopped)
1396
 
            # stopping 'x' should stop returning parents of 'x', but 
 
1416
            # stopping 'x' should stop returning parents of 'x', but
1397
1417
            # not if 'y' always references those same parents
1398
1418
            stop_rev_references = {}
1399
1419
            for rev in stopped_present:
1415
1435
                    stop_parents.add(rev_id)
1416
1436
            self._next_query.difference_update(stop_parents)
1417
1437
        self._stopped_keys.update(stopped)
1418
 
        self._stopped_keys.update(revisions - set([revision.NULL_REVISION]))
 
1438
        self._stopped_keys.update(revisions)
1419
1439
        return stopped
1420
1440
 
1421
1441
    def start_searching(self, revisions):
1461
1481
            a SearchResult from a smart server, in which case the keys list is
1462
1482
            not necessarily immediately available.
1463
1483
        """
1464
 
        self._recipe = (start_keys, exclude_keys, key_count)
 
1484
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1465
1485
        self._keys = frozenset(keys)
1466
1486
 
1467
1487
    def get_recipe(self):
1468
1488
        """Return a recipe that can be used to replay this search.
1469
 
        
 
1489
 
1470
1490
        The recipe allows reconstruction of the same results at a later date
1471
1491
        without knowing all the found keys. The essential elements are a list
1472
 
        of keys to start and and to stop at. In order to give reproducible
 
1492
        of keys to start and to stop at. In order to give reproducible
1473
1493
        results when ghosts are encountered by a search they are automatically
1474
1494
        added to the exclude list (or else ghost filling may alter the
1475
1495
        results).
1476
1496
 
1477
 
        :return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1478
 
            recreate the results of this search, create a breadth first
1479
 
            searcher on the same graph starting at start_keys. Then call next()
1480
 
            (or next_with_ghosts()) repeatedly, and on every result, call
1481
 
            stop_searching_any on any keys from the exclude_keys set. The
1482
 
            revision_count value acts as a trivial cross-check - the found
1483
 
            revisions of the new search should have as many elements as
 
1497
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
 
1498
            revision_count). To recreate the results of this search, create a
 
1499
            breadth first searcher on the same graph starting at start_keys.
 
1500
            Then call next() (or next_with_ghosts()) repeatedly, and on every
 
1501
            result, call stop_searching_any on any keys from the exclude_keys
 
1502
            set. The revision_count value acts as a trivial cross-check - the
 
1503
            found revisions of the new search should have as many elements as
1484
1504
            revision_count. If it does not, then additional revisions have been
1485
1505
            ghosted since the search was executed the first time and the second
1486
1506
            time.
1494
1514
        """
1495
1515
        return self._keys
1496
1516
 
 
1517
    def is_empty(self):
 
1518
        """Return false if the search lists 1 or more revisions."""
 
1519
        return self._recipe[3] == 0
 
1520
 
 
1521
    def refine(self, seen, referenced):
 
1522
        """Create a new search by refining this search.
 
1523
 
 
1524
        :param seen: Revisions that have been satisfied.
 
1525
        :param referenced: Revision references observed while satisfying some
 
1526
            of this search.
 
1527
        """
 
1528
        start = self._recipe[1]
 
1529
        exclude = self._recipe[2]
 
1530
        count = self._recipe[3]
 
1531
        keys = self.get_keys()
 
1532
        # New heads = referenced + old heads - seen things - exclude
 
1533
        pending_refs = set(referenced)
 
1534
        pending_refs.update(start)
 
1535
        pending_refs.difference_update(seen)
 
1536
        pending_refs.difference_update(exclude)
 
1537
        # New exclude = old exclude + satisfied heads
 
1538
        seen_heads = start.intersection(seen)
 
1539
        exclude.update(seen_heads)
 
1540
        # keys gets seen removed
 
1541
        keys = keys - seen
 
1542
        # length is reduced by len(seen)
 
1543
        count -= len(seen)
 
1544
        return SearchResult(pending_refs, exclude, count, keys)
 
1545
 
 
1546
 
 
1547
class PendingAncestryResult(object):
 
1548
    """A search result that will reconstruct the ancestry for some graph heads.
 
1549
 
 
1550
    Unlike SearchResult, this doesn't hold the complete search result in
 
1551
    memory, it just holds a description of how to generate it.
 
1552
    """
 
1553
 
 
1554
    def __init__(self, heads, repo):
 
1555
        """Constructor.
 
1556
 
 
1557
        :param heads: an iterable of graph heads.
 
1558
        :param repo: a repository to use to generate the ancestry for the given
 
1559
            heads.
 
1560
        """
 
1561
        self.heads = frozenset(heads)
 
1562
        self.repo = repo
 
1563
 
 
1564
    def get_recipe(self):
 
1565
        """Return a recipe that can be used to replay this search.
 
1566
 
 
1567
        The recipe allows reconstruction of the same results at a later date.
 
1568
 
 
1569
        :seealso SearchResult.get_recipe:
 
1570
 
 
1571
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
 
1572
            To recreate this result, create a PendingAncestryResult with the
 
1573
            start_keys_set.
 
1574
        """
 
1575
        return ('proxy-search', self.heads, set(), -1)
 
1576
 
 
1577
    def get_keys(self):
 
1578
        """See SearchResult.get_keys.
 
1579
 
 
1580
        Returns all the keys for the ancestry of the heads, excluding
 
1581
        NULL_REVISION.
 
1582
        """
 
1583
        return self._get_keys(self.repo.get_graph())
 
1584
 
 
1585
    def _get_keys(self, graph):
 
1586
        NULL_REVISION = revision.NULL_REVISION
 
1587
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
 
1588
                if key != NULL_REVISION and parents is not None]
 
1589
        return keys
 
1590
 
 
1591
    def is_empty(self):
 
1592
        """Return false if the search lists 1 or more revisions."""
 
1593
        if revision.NULL_REVISION in self.heads:
 
1594
            return len(self.heads) == 1
 
1595
        else:
 
1596
            return len(self.heads) == 0
 
1597
 
 
1598
    def refine(self, seen, referenced):
 
1599
        """Create a new search by refining this search.
 
1600
 
 
1601
        :param seen: Revisions that have been satisfied.
 
1602
        :param referenced: Revision references observed while satisfying some
 
1603
            of this search.
 
1604
        """
 
1605
        referenced = self.heads.union(referenced)
 
1606
        return PendingAncestryResult(referenced - seen, self.repo)
 
1607
 
1497
1608
 
1498
1609
def collapse_linear_regions(parent_map):
1499
1610
    """Collapse regions of the graph that are 'linear'.
1566
1677
            removed.add(node)
1567
1678
 
1568
1679
    return result
 
1680
 
 
1681
 
 
1682
class GraphThunkIdsToKeys(object):
 
1683
    """Forwards calls about 'ids' to be about keys internally."""
 
1684
 
 
1685
    def __init__(self, graph):
 
1686
        self._graph = graph
 
1687
 
 
1688
    def heads(self, ids):
 
1689
        """See Graph.heads()"""
 
1690
        as_keys = [(i,) for i in ids]
 
1691
        head_keys = self._graph.heads(as_keys)
 
1692
        return set([h[0] for h in head_keys])
 
1693
 
 
1694
 
 
1695
_counters = [0,0,0,0,0,0,0]
 
1696
try:
 
1697
    from bzrlib._known_graph_pyx import KnownGraph
 
1698
except ImportError, e:
 
1699
    osutils.failed_to_load_extension(e)
 
1700
    from bzrlib._known_graph_py import KnownGraph