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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
59
61
return 'DictParentsProvider(%r)' % self.ancestry
61
63
def get_parent_map(self, keys):
62
"""See StackedParentsProvider.get_parent_map"""
64
"""See _StackedParentsProvider.get_parent_map"""
63
65
ancestry = self.ancestry
64
66
return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
@deprecated_function(deprecated_in((1, 16, 0)))
67
def _StackedParentsProvider(*args, **kwargs):
68
return StackedParentsProvider(*args, **kwargs)
70
class StackedParentsProvider(object):
71
"""A parents provider which stacks (or unions) multiple providers.
73
The providers are queries in the order of the provided parent_providers.
69
class _StackedParentsProvider(object):
76
71
def __init__(self, parent_providers):
77
72
self._parent_providers = parent_providers
79
74
def __repr__(self):
80
return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
75
return "_StackedParentsProvider(%r)" % self._parent_providers
82
77
def get_parent_map(self, keys):
83
78
"""Get a mapping of keys => parents
106
101
class CachingParentsProvider(object):
107
"""A parents provider which will cache the revision => parents as a dict.
109
This is useful for providers which have an expensive look up.
111
Either a ParentsProvider or a get_parent_map-like callback may be
112
supplied. If it provides extra un-asked-for parents, they will be cached,
113
but filtered out of get_parent_map.
115
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.
117
def __init__(self, parent_provider=None, get_parent_map=None):
120
:param parent_provider: The ParentProvider to use. It or
121
get_parent_map must be supplied.
122
:param get_parent_map: The get_parent_map callback to use. It or
123
parent_provider must be supplied.
107
def __init__(self, parent_provider):
125
108
self._real_provider = parent_provider
126
if get_parent_map is None:
127
self._get_parent_map = self._real_provider.get_parent_map
129
self._get_parent_map = get_parent_map
131
self.enable_cache(True)
109
# Theoretically we could use an LRUCache here
133
112
def __repr__(self):
134
113
return "%s(%r)" % (self.__class__.__name__, self._real_provider)
136
def enable_cache(self, cache_misses=True):
138
if self._cache is not None:
139
raise AssertionError('Cache enabled when already enabled.')
141
self._cache_misses = cache_misses
142
self.missing_keys = set()
144
def disable_cache(self):
145
"""Disable and clear the cache."""
147
self._cache_misses = None
148
self.missing_keys = set()
150
def get_cached_map(self):
151
"""Return any cached get_parent_map values."""
152
if self._cache is None:
154
return dict(self._cache)
156
115
def get_parent_map(self, keys):
157
"""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
158
122
cache = self._cache
160
cache = self._get_parent_map(keys)
162
needed_revisions = set(key for key in keys if key not in cache)
163
# Do not ask for negatively cached keys
164
needed_revisions.difference_update(self.missing_keys)
166
parent_map = self._get_parent_map(needed_revisions)
167
cache.update(parent_map)
168
if self._cache_misses:
169
for key in needed_revisions:
170
if key not in parent_map:
171
self.note_missing_key(key)
174
value = cache.get(key)
175
if value is not None:
126
if value is not None:
127
parent_map[key] = value
179
def note_missing_key(self, key):
180
"""Note that key is a missing key."""
181
if self._cache_misses:
182
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))
185
140
class Graph(object):
311
266
return known_revnos[cur_tip] + num_steps
313
def find_lefthand_distances(self, keys):
314
"""Find the distance to null for all the keys in keys.
316
:param keys: keys to lookup.
317
:return: A dict key->distance for all of keys.
319
# Optimisable by concurrent searching, but a random spread should get
320
# some sort of hit rate.
327
(key, self.find_distance_to_null(key, known_revnos)))
328
except errors.GhostRevisionsHaveNoRevno:
331
known_revnos.append((key, -1))
332
return dict(known_revnos)
334
268
def find_unique_ancestors(self, unique_revision, common_revisions):
335
269
"""Find the unique ancestors for a revision versus others.
636
570
all_unique_searcher._iterations)
637
571
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]
639
591
def get_parent_map(self, revisions):
640
592
"""Get a map of key:parent_list for revisions.
939
890
return set([candidate_descendant]) == self.heads(
940
891
[candidate_ancestor, candidate_descendant])
942
def is_between(self, revid, lower_bound_revid, upper_bound_revid):
943
"""Determine whether a revision is between two others.
945
returns true if and only if:
946
lower_bound_revid <= revid <= upper_bound_revid
948
return ((upper_bound_revid is None or
949
self.is_ancestor(revid, upper_bound_revid)) and
950
(lower_bound_revid is None or
951
self.is_ancestor(lower_bound_revid, revid)))
953
893
def _search_for_extra_common(self, common, searchers):
954
894
"""Make sure that unique nodes are genuinely unique.
1391
1331
Remove any of the specified revisions from the search list.
1393
1333
None of the specified revisions are required to be present in the
1396
It is okay to call stop_searching_any() for revisions which were seen
1397
in previous iterations. It is the callers responsibility to call
1398
find_seen_ancestors() to make sure that current search tips that are
1399
ancestors of those revisions are also stopped. All explicitly stopped
1400
revisions will be excluded from the search result's get_keys(), though.
1334
search list. In this case, the call is a no-op.
1402
1336
# TODO: does this help performance?
1403
1337
# if not revisions:
1480
1413
a SearchResult from a smart server, in which case the keys list is
1481
1414
not necessarily immediately available.
1483
self._recipe = ('search', start_keys, exclude_keys, key_count)
1416
self._recipe = (start_keys, exclude_keys, key_count)
1484
1417
self._keys = frozenset(keys)
1486
1419
def get_recipe(self):
1487
1420
"""Return a recipe that can be used to replay this search.
1489
1422
The recipe allows reconstruction of the same results at a later date
1490
1423
without knowing all the found keys. The essential elements are a list
1491
of keys to start and to stop at. In order to give reproducible
1424
of keys to start and and to stop at. In order to give reproducible
1492
1425
results when ghosts are encountered by a search they are automatically
1493
1426
added to the exclude list (or else ghost filling may alter the
1496
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1497
revision_count). To recreate the results of this search, create a
1498
breadth first searcher on the same graph starting at start_keys.
1499
Then call next() (or next_with_ghosts()) repeatedly, and on every
1500
result, call stop_searching_any on any keys from the exclude_keys
1501
set. The revision_count value acts as a trivial cross-check - the
1502
found revisions of the new search should have as many elements as
1429
:return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1430
recreate the results of this search, create a breadth first
1431
searcher on the same graph starting at start_keys. Then call next()
1432
(or next_with_ghosts()) repeatedly, and on every result, call
1433
stop_searching_any on any keys from the exclude_keys set. The
1434
revision_count value acts as a trivial cross-check - the found
1435
revisions of the new search should have as many elements as
1503
1436
revision_count. If it does not, then additional revisions have been
1504
1437
ghosted since the search was executed the first time and the second
1514
1447
return self._keys
1517
"""Return false if the search lists 1 or more revisions."""
1518
return self._recipe[3] == 0
1520
def refine(self, seen, referenced):
1521
"""Create a new search by refining this search.
1523
:param seen: Revisions that have been satisfied.
1524
:param referenced: Revision references observed while satisfying some
1527
start = self._recipe[1]
1528
exclude = self._recipe[2]
1529
count = self._recipe[3]
1530
keys = self.get_keys()
1531
# New heads = referenced + old heads - seen things - exclude
1532
pending_refs = set(referenced)
1533
pending_refs.update(start)
1534
pending_refs.difference_update(seen)
1535
pending_refs.difference_update(exclude)
1536
# New exclude = old exclude + satisfied heads
1537
seen_heads = start.intersection(seen)
1538
exclude.update(seen_heads)
1539
# keys gets seen removed
1541
# length is reduced by len(seen)
1543
return SearchResult(pending_refs, exclude, count, keys)
1546
class PendingAncestryResult(object):
1547
"""A search result that will reconstruct the ancestry for some graph heads.
1549
Unlike SearchResult, this doesn't hold the complete search result in
1550
memory, it just holds a description of how to generate it.
1553
def __init__(self, heads, repo):
1556
:param heads: an iterable of graph heads.
1557
:param repo: a repository to use to generate the ancestry for the given
1560
self.heads = frozenset(heads)
1563
def get_recipe(self):
1564
"""Return a recipe that can be used to replay this search.
1566
The recipe allows reconstruction of the same results at a later date.
1568
:seealso SearchResult.get_recipe:
1570
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1571
To recreate this result, create a PendingAncestryResult with the
1574
return ('proxy-search', self.heads, set(), -1)
1577
"""See SearchResult.get_keys.
1579
Returns all the keys for the ancestry of the heads, excluding
1582
return self._get_keys(self.repo.get_graph())
1584
def _get_keys(self, graph):
1585
NULL_REVISION = revision.NULL_REVISION
1586
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1587
if key != NULL_REVISION and parents is not None]
1591
"""Return false if the search lists 1 or more revisions."""
1592
if revision.NULL_REVISION in self.heads:
1593
return len(self.heads) == 1
1595
return len(self.heads) == 0
1597
def refine(self, seen, referenced):
1598
"""Create a new search by refining this search.
1600
:param seen: Revisions that have been satisfied.
1601
:param referenced: Revision references observed while satisfying some
1604
referenced = self.heads.union(referenced)
1605
return PendingAncestryResult(referenced - seen, self.repo)
1608
1450
def collapse_linear_regions(parent_map):
1609
1451
"""Collapse regions of the graph that are 'linear'.
added
removed
bzrlib/graph.py
