60
60
def __repr__(self):
61
61
return 'DictParentsProvider(%r)' % self.ancestry
63
# Note: DictParentsProvider does not implement get_cached_parent_map
64
# Arguably, the data is clearly cached in memory. However, this class
65
# is mostly used for testing, and it keeps the tests clean to not
63
68
def get_parent_map(self, keys):
64
"""See _StackedParentsProvider.get_parent_map"""
69
"""See StackedParentsProvider.get_parent_map"""
65
70
ancestry = self.ancestry
66
return dict((k, ancestry[k]) for k in keys if k in ancestry)
69
class _StackedParentsProvider(object):
71
return dict([(k, ancestry[k]) for k in keys if k in ancestry])
74
class StackedParentsProvider(object):
75
"""A parents provider which stacks (or unions) multiple providers.
77
The providers are queries in the order of the provided parent_providers.
71
80
def __init__(self, parent_providers):
72
81
self._parent_providers = parent_providers
74
83
def __repr__(self):
75
return "_StackedParentsProvider(%r)" % self._parent_providers
84
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
77
86
def get_parent_map(self, keys):
78
87
"""Get a mapping of keys => parents
101
126
class CachingParentsProvider(object):
102
"""A parents provider which will cache the revision => parents in a dict.
104
This is useful for providers that have an expensive lookup.
127
"""A parents provider which will cache the revision => parents as a dict.
129
This is useful for providers which have an expensive look up.
131
Either a ParentsProvider or a get_parent_map-like callback may be
132
supplied. If it provides extra un-asked-for parents, they will be cached,
133
but filtered out of get_parent_map.
135
The cache is enabled by default, but may be disabled and re-enabled.
137
def __init__(self, parent_provider=None, get_parent_map=None):
107
def __init__(self, parent_provider):
140
:param parent_provider: The ParentProvider to use. It or
141
get_parent_map must be supplied.
142
:param get_parent_map: The get_parent_map callback to use. It or
143
parent_provider must be supplied.
108
145
self._real_provider = parent_provider
109
# Theoretically we could use an LRUCache here
146
if get_parent_map is None:
147
self._get_parent_map = self._real_provider.get_parent_map
149
self._get_parent_map = get_parent_map
151
self.enable_cache(True)
154
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
156
def enable_cache(self, cache_misses=True):
158
if self._cache is not None:
159
raise AssertionError('Cache enabled when already enabled.')
161
self._cache_misses = cache_misses
162
self.missing_keys = set()
164
def disable_cache(self):
165
"""Disable and clear the cache."""
167
self._cache_misses = None
168
self.missing_keys = set()
170
def get_cached_map(self):
171
"""Return any cached get_parent_map values."""
172
if self._cache is None:
174
return dict(self._cache)
176
def get_cached_parent_map(self, keys):
177
"""Return items from the cache.
179
This returns the same info as get_parent_map, but explicitly does not
180
invoke the supplied ParentsProvider to search for uncached values.
185
return dict([(key, cache[key]) for key in keys if key in cache])
187
def get_parent_map(self, keys):
188
"""See StackedParentsProvider.get_parent_map."""
191
cache = self._get_parent_map(keys)
193
needed_revisions = set(key for key in keys if key not in cache)
194
# Do not ask for negatively cached keys
195
needed_revisions.difference_update(self.missing_keys)
197
parent_map = self._get_parent_map(needed_revisions)
198
cache.update(parent_map)
199
if self._cache_misses:
200
for key in needed_revisions:
201
if key not in parent_map:
202
self.note_missing_key(key)
205
value = cache.get(key)
206
if value is not None:
210
def note_missing_key(self, key):
211
"""Note that key is a missing key."""
212
if self._cache_misses:
213
self.missing_keys.add(key)
216
class CallableToParentsProviderAdapter(object):
217
"""A parents provider that adapts any callable to the parents provider API.
219
i.e. it accepts calls to self.get_parent_map and relays them to the
220
callable it was constructed with.
223
def __init__(self, a_callable):
224
self.callable = a_callable
112
226
def __repr__(self):
113
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
227
return "%s(%r)" % (self.__class__.__name__, self.callable)
115
229
def get_parent_map(self, keys):
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
126
if value is not None:
127
parent_map[key] = value
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))
230
return self.callable(keys)
140
233
class Graph(object):
212
306
right = searchers[1].seen
213
307
return (left.difference(right), right.difference(left))
309
def find_descendants(self, old_key, new_key):
310
"""Find descendants of old_key that are ancestors of new_key."""
311
child_map = self.get_child_map(self._find_descendant_ancestors(
313
graph = Graph(DictParentsProvider(child_map))
314
searcher = graph._make_breadth_first_searcher([old_key])
318
def _find_descendant_ancestors(self, old_key, new_key):
319
"""Find ancestors of new_key that may be descendants of old_key."""
320
stop = self._make_breadth_first_searcher([old_key])
321
descendants = self._make_breadth_first_searcher([new_key])
322
for revisions in descendants:
323
old_stop = stop.seen.intersection(revisions)
324
descendants.stop_searching_any(old_stop)
325
seen_stop = descendants.find_seen_ancestors(stop.step())
326
descendants.stop_searching_any(seen_stop)
327
return descendants.seen.difference(stop.seen)
329
def get_child_map(self, keys):
330
"""Get a mapping from parents to children of the specified keys.
332
This is simply the inversion of get_parent_map. Only supplied keys
333
will be discovered as children.
334
:return: a dict of key:child_list for keys.
336
parent_map = self._parents_provider.get_parent_map(keys)
338
for child, parents in sorted(parent_map.items()):
339
for parent in parents:
340
parent_child.setdefault(parent, []).append(child)
215
343
def find_distance_to_null(self, target_revision_id, known_revision_ids):
216
344
"""Find the left-hand distance to the NULL_REVISION.
570
719
all_unique_searcher._iterations)
571
720
unique_tip_searchers = next_unique_searchers
573
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
574
def get_parents(self, revisions):
575
"""Find revision ids of the parents of a list of revisions
577
A list is returned of the same length as the input. Each entry
578
is a list of parent ids for the corresponding input revision.
580
[NULL_REVISION] is used as the parent of the first user-committed
581
revision. Its parent list is empty.
583
If the revision is not present (i.e. a ghost), None is used in place
584
of the list of parents.
586
Deprecated in bzr 1.2 - please see get_parent_map.
588
parents = self.get_parent_map(revisions)
589
return [parents.get(r, None) for r in revisions]
591
722
def get_parent_map(self, revisions):
592
723
"""Get a map of key:parent_list for revisions.
766
897
common_walker.start_searching(new_common)
767
898
return candidate_heads
900
def find_merge_order(self, tip_revision_id, lca_revision_ids):
901
"""Find the order that each revision was merged into tip.
903
This basically just walks backwards with a stack, and walks left-first
904
until it finds a node to stop.
906
if len(lca_revision_ids) == 1:
907
return list(lca_revision_ids)
908
looking_for = set(lca_revision_ids)
909
# TODO: Is there a way we could do this "faster" by batching up the
910
# get_parent_map requests?
911
# TODO: Should we also be culling the ancestry search right away? We
912
# could add looking_for to the "stop" list, and walk their
913
# ancestry in batched mode. The flip side is it might mean we walk a
914
# lot of "stop" nodes, rather than only the minimum.
915
# Then again, without it we may trace back into ancestry we could have
917
stack = [tip_revision_id]
920
while stack and looking_for:
923
if next in looking_for:
925
looking_for.remove(next)
926
if len(looking_for) == 1:
927
found.append(looking_for.pop())
930
parent_ids = self.get_parent_map([next]).get(next, None)
931
if not parent_ids: # Ghost, nothing to search here
933
for parent_id in reversed(parent_ids):
934
# TODO: (performance) We see the parent at this point, but we
935
# wait to mark it until later to make sure we get left
936
# parents before right parents. However, instead of
937
# waiting until we have traversed enough parents, we
938
# could instead note that we've found it, and once all
939
# parents are in the stack, just reverse iterate the
941
if parent_id not in stop:
942
# this will need to be searched
943
stack.append(parent_id)
947
def find_lefthand_merger(self, merged_key, tip_key):
948
"""Find the first lefthand ancestor of tip_key that merged merged_key.
950
We do this by first finding the descendants of merged_key, then
951
walking through the lefthand ancestry of tip_key until we find a key
952
that doesn't descend from merged_key. Its child is the key that
955
:return: The first lefthand ancestor of tip_key to merge merged_key.
956
merged_key if it is a lefthand ancestor of tip_key.
957
None if no ancestor of tip_key merged merged_key.
959
descendants = self.find_descendants(merged_key, tip_key)
960
candidate_iterator = self.iter_lefthand_ancestry(tip_key)
961
last_candidate = None
962
for candidate in candidate_iterator:
963
if candidate not in descendants:
964
return last_candidate
965
last_candidate = candidate
769
967
def find_unique_lca(self, left_revision, right_revision,
770
968
count_steps=False):
771
969
"""Find a unique LCA.
1119
1348
return ('_BreadthFirstSearcher(iterations=%d, %s,'
1120
1349
' seen=%r)' % (self._iterations, search, list(self.seen)))
1122
def get_result(self):
1123
"""Get a SearchResult for the current state of this searcher.
1125
:return: A SearchResult for this search so far. The SearchResult is
1126
static - the search can be advanced and the search result will not
1127
be invalidated or altered.
1351
def get_state(self):
1352
"""Get the current state of this searcher.
1354
:return: Tuple with started keys, excludes and included keys
1129
1356
if self._returning == 'next':
1130
1357
# We have to know the current nodes children to be able to list the
1131
1358
# exclude keys for them. However, while we could have a second
1132
1359
# look-ahead result buffer and shuffle things around, this method
1133
1360
# is typically only called once per search - when memoising the
1134
# results of the search.
1361
# results of the search.
1135
1362
found, ghosts, next, parents = self._do_query(self._next_query)
1136
1363
# pretend we didn't query: perhaps we should tweak _do_query to be
1137
1364
# entirely stateless?
1141
1368
next_query = self._next_query
1142
1369
excludes = self._stopped_keys.union(next_query)
1143
1370
included_keys = self.seen.difference(excludes)
1144
return SearchResult(self._started_keys, excludes, len(included_keys),
1371
return self._started_keys, excludes, included_keys
1373
def _get_result(self):
1374
"""Get a SearchResult for the current state of this searcher.
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.
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),
1147
1385
def step(self):
1348
1594
return revs, ghosts
1351
class SearchResult(object):
1352
"""The result of a breadth first search.
1354
A SearchResult provides the ability to reconstruct the search or access a
1355
set of the keys the search found.
1597
def invert_parent_map(parent_map):
1598
"""Given a map from child => parents, create a map of parent=>children"""
1600
for child, parents in parent_map.iteritems():
1602
# Any given parent is likely to have only a small handful
1603
# of children, many will have only one. So we avoid mem overhead of
1604
# a list, in exchange for extra copying of tuples
1605
if p not in child_map:
1606
child_map[p] = (child,)
1608
child_map[p] = child_map[p] + (child,)
1612
def collapse_linear_regions(parent_map):
1613
"""Collapse regions of the graph that are 'linear'.
1619
can be collapsed by removing B and getting::
1623
:param parent_map: A dictionary mapping children to their parents
1624
:return: Another dictionary with 'linear' chains collapsed
1358
def __init__(self, start_keys, exclude_keys, key_count, keys):
1359
"""Create a SearchResult.
1361
:param start_keys: The keys the search started at.
1362
:param exclude_keys: The keys the search excludes.
1363
:param key_count: The total number of keys (from start to but not
1365
:param keys: The keys the search found. Note that in future we may get
1366
a SearchResult from a smart server, in which case the keys list is
1367
not necessarily immediately available.
1369
self._recipe = (start_keys, exclude_keys, key_count)
1370
self._keys = frozenset(keys)
1372
def get_recipe(self):
1373
"""Return a recipe that can be used to replay this search.
1375
The recipe allows reconstruction of the same results at a later date
1376
without knowing all the found keys. The essential elements are a list
1377
of keys to start and and to stop at. In order to give reproducible
1378
results when ghosts are encountered by a search they are automatically
1379
added to the exclude list (or else ghost filling may alter the
1382
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1383
recreate the results of this search, create a breadth first
1384
searcher on the same graph starting at start_keys. Then call next()
1385
(or next_with_ghosts()) repeatedly, and on every result, call
1386
stop_searching_any on any keys from the exclude_keys set. The
1387
revision_count value acts as a trivial cross-check - the found
1388
revisions of the new search should have as many elements as
1389
revision_count. If it does not, then additional revisions have been
1390
ghosted since the search was executed the first time and the second
1396
"""Return the keys found in this search.
1398
:return: A set of keys.
1626
# Note: this isn't a strictly minimal collapse. For example:
1634
# Will not have 'D' removed, even though 'E' could fit. Also:
1640
# A and C are both kept because they are edges of the graph. We *could* get
1641
# rid of A if we wanted.
1649
# Will not have any nodes removed, even though you do have an
1650
# 'uninteresting' linear D->B and E->C
1652
for child, parents in parent_map.iteritems():
1653
children.setdefault(child, [])
1655
children.setdefault(p, []).append(child)
1657
orig_children = dict(children)
1659
result = dict(parent_map)
1660
for node in parent_map:
1661
parents = result[node]
1662
if len(parents) == 1:
1663
parent_children = children[parents[0]]
1664
if len(parent_children) != 1:
1665
# This is not the only child
1667
node_children = children[node]
1668
if len(node_children) != 1:
1670
child_parents = result.get(node_children[0], None)
1671
if len(child_parents) != 1:
1672
# This is not its only parent
1674
# The child of this node only points at it, and the parent only has
1675
# this as a child. remove this node, and join the others together
1676
result[node_children[0]] = parents
1677
children[parents[0]] = node_children
1685
class GraphThunkIdsToKeys(object):
1686
"""Forwards calls about 'ids' to be about keys internally."""
1688
def __init__(self, graph):
1691
def topo_sort(self):
1692
return [r for (r,) in self._graph.topo_sort()]
1694
def heads(self, ids):
1695
"""See Graph.heads()"""
1696
as_keys = [(i,) for i in ids]
1697
head_keys = self._graph.heads(as_keys)
1698
return set([h[0] for h in head_keys])
1700
def merge_sort(self, tip_revision):
1701
nodes = self._graph.merge_sort((tip_revision,))
1703
node.key = node.key[0]
1706
def add_node(self, revision, parents):
1707
self._graph.add_node((revision,), [(p,) for p in parents])
1710
_counters = [0,0,0,0,0,0,0]
1712
from bzrlib._known_graph_pyx import KnownGraph
1713
except ImportError, e:
1714
osutils.failed_to_load_extension(e)
1715
from bzrlib._known_graph_py import KnownGraph
added
removed
bzrlib/graph.py
