60
61
return 'DictParentsProvider(%r)' % self.ancestry
62
63
def get_parent_map(self, keys):
63
"""See StackedParentsProvider.get_parent_map"""
64
"""See _StackedParentsProvider.get_parent_map"""
64
65
ancestry = self.ancestry
65
66
return dict((k, ancestry[k]) for k in keys if k in ancestry)
67
@deprecated_function(deprecated_in((1, 16, 0)))
68
def _StackedParentsProvider(*args, **kwargs):
69
return StackedParentsProvider(*args, **kwargs)
71
class StackedParentsProvider(object):
72
"""A parents provider which stacks (or unions) multiple providers.
74
The providers are queries in the order of the provided parent_providers.
69
class _StackedParentsProvider(object):
77
71
def __init__(self, parent_providers):
78
72
self._parent_providers = parent_providers
80
74
def __repr__(self):
81
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
75
return "_StackedParentsProvider(%r)" % self._parent_providers
83
77
def get_parent_map(self, keys):
84
78
"""Get a mapping of keys => parents
107
101
class CachingParentsProvider(object):
108
"""A parents provider which will cache the revision => parents as a dict.
110
This is useful for providers which have an expensive look up.
112
Either a ParentsProvider or a get_parent_map-like callback may be
113
supplied. If it provides extra un-asked-for parents, they will be cached,
114
but filtered out of get_parent_map.
116
The cache is enabled by default, but may be disabled and re-enabled.
102
"""A parents provider which will cache the revision => parents in a dict.
104
This is useful for providers that have an expensive lookup.
118
def __init__(self, parent_provider=None, get_parent_map=None):
121
:param parent_provider: The ParentProvider to use. It or
122
get_parent_map must be supplied.
123
:param get_parent_map: The get_parent_map callback to use. It or
124
parent_provider must be supplied.
107
def __init__(self, parent_provider):
126
108
self._real_provider = parent_provider
127
if get_parent_map is None:
128
self._get_parent_map = self._real_provider.get_parent_map
130
self._get_parent_map = get_parent_map
132
self.enable_cache(True)
109
# Theoretically we could use an LRUCache here
134
112
def __repr__(self):
135
113
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
137
def enable_cache(self, cache_misses=True):
139
if self._cache is not None:
140
raise AssertionError('Cache enabled when already enabled.')
142
self._cache_misses = cache_misses
143
self.missing_keys = set()
145
def disable_cache(self):
146
"""Disable and clear the cache."""
148
self._cache_misses = None
149
self.missing_keys = set()
151
def get_cached_map(self):
152
"""Return any cached get_parent_map values."""
153
if self._cache is None:
155
return dict(self._cache)
157
115
def get_parent_map(self, keys):
158
"""See StackedParentsProvider.get_parent_map."""
116
"""See _StackedParentsProvider.get_parent_map"""
118
# If the _real_provider doesn't have a key, we cache a value of None,
119
# which we then later use to realize we cannot provide a value for that
159
122
cache = self._cache
161
cache = self._get_parent_map(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)
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)
175
value = cache.get(key)
176
if value is not None:
126
if value is not None:
127
parent_map[key] = value
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)
132
new_parents = self._real_provider.get_parent_map(needed)
133
cache.update(new_parents)
134
parent_map.update(new_parents)
135
needed.difference_update(new_parents)
136
cache.update(dict.fromkeys(needed, None))
186
140
class Graph(object):
258
212
right = searchers[1].seen
259
213
return (left.difference(right), right.difference(left))
261
def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
"""Find the left-hand distance to the NULL_REVISION.
264
(This can also be considered the revno of a branch at
267
:param target_revision_id: A revision_id which we would like to know
269
:param known_revision_ids: [(revision_id, revno)] A list of known
270
revno, revision_id tuples. We'll use this to seed the search.
272
# Map from revision_ids to a known value for their revno
273
known_revnos = dict(known_revision_ids)
274
cur_tip = target_revision_id
276
NULL_REVISION = revision.NULL_REVISION
277
known_revnos[NULL_REVISION] = 0
279
searching_known_tips = list(known_revnos.keys())
281
unknown_searched = {}
283
while cur_tip not in known_revnos:
284
unknown_searched[cur_tip] = num_steps
286
to_search = set([cur_tip])
287
to_search.update(searching_known_tips)
288
parent_map = self.get_parent_map(to_search)
289
parents = parent_map.get(cur_tip, None)
290
if not parents: # An empty list or None is a ghost
291
raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
295
for revision_id in searching_known_tips:
296
parents = parent_map.get(revision_id, None)
300
next_revno = known_revnos[revision_id] - 1
301
if next in unknown_searched:
302
# We have enough information to return a value right now
303
return next_revno + unknown_searched[next]
304
if next in known_revnos:
306
known_revnos[next] = next_revno
307
next_known_tips.append(next)
308
searching_known_tips = next_known_tips
310
# We reached a known revision, so just add in how many steps it took to
312
return known_revnos[cur_tip] + num_steps
314
def find_lefthand_distances(self, keys):
315
"""Find the distance to null for all the keys in keys.
317
:param keys: keys to lookup.
318
:return: A dict key->distance for all of keys.
320
# Optimisable by concurrent searching, but a random spread should get
321
# some sort of hit rate.
328
(key, self.find_distance_to_null(key, known_revnos)))
329
except errors.GhostRevisionsHaveNoRevno:
332
known_revnos.append((key, -1))
333
return dict(known_revnos)
335
215
def find_unique_ancestors(self, unique_revision, common_revisions):
336
216
"""Find the unique ancestors for a revision versus others.
815
713
common_walker.start_searching(new_common)
816
714
return candidate_heads
818
def find_merge_order(self, tip_revision_id, lca_revision_ids):
819
"""Find the order that each revision was merged into tip.
821
This basically just walks backwards with a stack, and walks left-first
822
until it finds a node to stop.
824
if len(lca_revision_ids) == 1:
825
return list(lca_revision_ids)
826
looking_for = set(lca_revision_ids)
827
# TODO: Is there a way we could do this "faster" by batching up the
828
# get_parent_map requests?
829
# TODO: Should we also be culling the ancestry search right away? We
830
# could add looking_for to the "stop" list, and walk their
831
# ancestry in batched mode. The flip side is it might mean we walk a
832
# lot of "stop" nodes, rather than only the minimum.
833
# Then again, without it we may trace back into ancestry we could have
835
stack = [tip_revision_id]
838
while stack and looking_for:
841
if next in looking_for:
843
looking_for.remove(next)
844
if len(looking_for) == 1:
845
found.append(looking_for.pop())
848
parent_ids = self.get_parent_map([next]).get(next, None)
849
if not parent_ids: # Ghost, nothing to search here
851
for parent_id in reversed(parent_ids):
852
# TODO: (performance) We see the parent at this point, but we
853
# wait to mark it until later to make sure we get left
854
# parents before right parents. However, instead of
855
# waiting until we have traversed enough parents, we
856
# could instead note that we've found it, and once all
857
# parents are in the stack, just reverse iterate the
859
if parent_id not in stop:
860
# this will need to be searched
861
stack.append(parent_id)
865
716
def find_unique_lca(self, left_revision, right_revision,
866
717
count_steps=False):
867
718
"""Find a unique LCA.
1481
1311
a SearchResult from a smart server, in which case the keys list is
1482
1312
not necessarily immediately available.
1484
self._recipe = ('search', start_keys, exclude_keys, key_count)
1314
self._recipe = (start_keys, exclude_keys, key_count)
1485
1315
self._keys = frozenset(keys)
1487
1317
def get_recipe(self):
1488
1318
"""Return a recipe that can be used to replay this search.
1490
1320
The recipe allows reconstruction of the same results at a later date
1491
1321
without knowing all the found keys. The essential elements are a list
1492
of keys to start and to stop at. In order to give reproducible
1322
of keys to start and and to stop at. In order to give reproducible
1493
1323
results when ghosts are encountered by a search they are automatically
1494
1324
added to the exclude list (or else ghost filling may alter the
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
1327
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1328
recreate the results of this search, create a breadth first
1329
searcher on the same graph starting at start_keys. Then call next()
1330
(or next_with_ghosts()) repeatedly, and on every result, call
1331
stop_searching_any on any keys from the exclude_keys set. The
1332
revision_count value acts as a trivial cross-check - the found
1333
revisions of the new search should have as many elements as
1504
1334
revision_count. If it does not, then additional revisions have been
1505
1335
ghosted since the search was executed the first time and the second
1515
1345
return self._keys
1518
"""Return false if the search lists 1 or more revisions."""
1519
return self._recipe[3] == 0
1521
def refine(self, seen, referenced):
1522
"""Create a new search by refining this search.
1524
:param seen: Revisions that have been satisfied.
1525
:param referenced: Revision references observed while satisfying some
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
1542
# length is reduced by len(seen)
1544
return SearchResult(pending_refs, exclude, count, keys)
1547
class PendingAncestryResult(object):
1548
"""A search result that will reconstruct the ancestry for some graph heads.
1550
Unlike SearchResult, this doesn't hold the complete search result in
1551
memory, it just holds a description of how to generate it.
1554
def __init__(self, heads, repo):
1557
:param heads: an iterable of graph heads.
1558
:param repo: a repository to use to generate the ancestry for the given
1561
self.heads = frozenset(heads)
1564
def get_recipe(self):
1565
"""Return a recipe that can be used to replay this search.
1567
The recipe allows reconstruction of the same results at a later date.
1569
:seealso SearchResult.get_recipe:
1571
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1572
To recreate this result, create a PendingAncestryResult with the
1575
return ('proxy-search', self.heads, set(), -1)
1578
"""See SearchResult.get_keys.
1580
Returns all the keys for the ancestry of the heads, excluding
1583
return self._get_keys(self.repo.get_graph())
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]
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
1596
return len(self.heads) == 0
1598
def refine(self, seen, referenced):
1599
"""Create a new search by refining this search.
1601
:param seen: Revisions that have been satisfied.
1602
:param referenced: Revision references observed while satisfying some
1605
referenced = self.heads.union(referenced)
1606
return PendingAncestryResult(referenced - seen, self.repo)
1609
def collapse_linear_regions(parent_map):
1610
"""Collapse regions of the graph that are 'linear'.
1616
can be collapsed by removing B and getting::
1620
:param parent_map: A dictionary mapping children to their parents
1621
:return: Another dictionary with 'linear' chains collapsed
1623
# Note: this isn't a strictly minimal collapse. For example:
1631
# Will not have 'D' removed, even though 'E' could fit. Also:
1637
# A and C are both kept because they are edges of the graph. We *could* get
1638
# rid of A if we wanted.
1646
# Will not have any nodes removed, even though you do have an
1647
# 'uninteresting' linear D->B and E->C
1649
for child, parents in parent_map.iteritems():
1650
children.setdefault(child, [])
1652
children.setdefault(p, []).append(child)
1654
orig_children = dict(children)
1656
result = dict(parent_map)
1657
for node in parent_map:
1658
parents = result[node]
1659
if len(parents) == 1:
1660
parent_children = children[parents[0]]
1661
if len(parent_children) != 1:
1662
# This is not the only child
1664
node_children = children[node]
1665
if len(node_children) != 1:
1667
child_parents = result.get(node_children[0], None)
1668
if len(child_parents) != 1:
1669
# This is not its only parent
1671
# The child of this node only points at it, and the parent only has
1672
# this as a child. remove this node, and join the others together
1673
result[node_children[0]] = parents
1674
children[parents[0]] = node_children
1682
class GraphThunkIdsToKeys(object):
1683
"""Forwards calls about 'ids' to be about keys internally."""
1685
def __init__(self, graph):
1688
def topo_sort(self):
1689
return [r for (r,) in self._graph.topo_sort()]
1691
def heads(self, ids):
1692
"""See Graph.heads()"""
1693
as_keys = [(i,) for i in ids]
1694
head_keys = self._graph.heads(as_keys)
1695
return set([h[0] for h in head_keys])
1697
def merge_sort(self, tip_revision):
1698
return self._graph.merge_sort((tip_revision,))
1701
_counters = [0,0,0,0,0,0,0]
1703
from bzrlib._known_graph_pyx import KnownGraph
1704
except ImportError, e:
1705
osutils.failed_to_load_extension(e)
1706
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
