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
133
133
raise AssertionError('Cache enabled when already enabled.')
135
135
self._cache_misses = cache_misses
136
self.missing_keys = set()
138
137
def disable_cache(self):
139
138
"""Disable and clear the cache."""
140
139
self._cache = None
141
self._cache_misses = None
142
self.missing_keys = set()
144
141
def get_cached_map(self):
145
142
"""Return any cached get_parent_map values."""
146
143
if self._cache is None:
148
return dict(self._cache)
145
return dict((k, v) for k, v in self._cache.items()
150
148
def get_parent_map(self, keys):
151
149
"""See _StackedParentsProvider.get_parent_map."""
154
cache = self._get_parent_map(keys)
150
# Hack to build up the caching logic.
151
ancestry = self._cache
153
# Caching is disabled.
154
missing_revisions = set(keys)
156
needed_revisions = set(key for key in keys if key not in cache)
157
# Do not ask for negatively cached keys
158
needed_revisions.difference_update(self.missing_keys)
160
parent_map = self._get_parent_map(needed_revisions)
161
cache.update(parent_map)
162
if self._cache_misses:
163
for key in needed_revisions:
164
if key not in parent_map:
165
self.note_missing_key(key)
168
value = cache.get(key)
169
if value is not None:
173
def note_missing_key(self, key):
174
"""Note that key is a missing key."""
175
if self._cache_misses:
176
self.missing_keys.add(key)
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
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)
179
170
class Graph(object):
609
600
all_unique_searcher._iterations)
610
601
unique_tip_searchers = next_unique_searchers
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
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.
610
[NULL_REVISION] is used as the parent of the first user-committed
611
revision. Its parent list is empty.
613
If the revision is not present (i.e. a ghost), None is used in place
614
of the list of parents.
616
Deprecated in bzr 1.2 - please see get_parent_map.
618
parents = self.get_parent_map(revisions)
619
return [parents.get(r, None) for r in revisions]
612
621
def get_parent_map(self, revisions):
613
622
"""Get a map of key:parent_list for revisions.
1461
1470
The recipe allows reconstruction of the same results at a later date
1462
1471
without knowing all the found keys. The essential elements are a list
1463
of keys to start and to stop at. In order to give reproducible
1472
of keys to start and and to stop at. In order to give reproducible
1464
1473
results when ghosts are encountered by a search they are automatically
1465
1474
added to the exclude list (or else ghost filling may alter the
1468
:return: A tuple ('search', start_keys_set, exclude_keys_set,
1469
revision_count). To recreate the results of this search, create a
1470
breadth first searcher on the same graph starting at start_keys.
1471
Then call next() (or next_with_ghosts()) repeatedly, and on every
1472
result, call stop_searching_any on any keys from the exclude_keys
1473
set. The revision_count value acts as a trivial cross-check - the
1474
found revisions of the new search should have as many elements as
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
1475
1484
revision_count. If it does not, then additional revisions have been
1476
1485
ghosted since the search was executed the first time and the second
1486
1495
return self._keys
1489
"""Return false if the search lists 1 or more revisions."""
1490
return self._recipe[3] == 0
1492
def refine(self, seen, referenced):
1493
"""Create a new search by refining this search.
1495
:param seen: Revisions that have been satisfied.
1496
:param referenced: Revision references observed while satisfying some
1499
start = self._recipe[1]
1500
exclude = self._recipe[2]
1501
count = self._recipe[3]
1502
keys = self.get_keys()
1503
# New heads = referenced + old heads - seen things - exclude
1504
pending_refs = set(referenced)
1505
pending_refs.update(start)
1506
pending_refs.difference_update(seen)
1507
pending_refs.difference_update(exclude)
1508
# New exclude = old exclude + satisfied heads
1509
seen_heads = start.intersection(seen)
1510
exclude.update(seen_heads)
1511
# keys gets seen removed
1513
# length is reduced by len(seen)
1515
return SearchResult(pending_refs, exclude, count, keys)
1518
class PendingAncestryResult(object):
1519
"""A search result that will reconstruct the ancestry for some graph heads.
1521
Unlike SearchResult, this doesn't hold the complete search result in
1522
memory, it just holds a description of how to generate it.
1525
def __init__(self, heads, repo):
1528
:param heads: an iterable of graph heads.
1529
:param repo: a repository to use to generate the ancestry for the given
1532
self.heads = frozenset(heads)
1535
def get_recipe(self):
1536
"""Return a recipe that can be used to replay this search.
1538
The recipe allows reconstruction of the same results at a later date.
1540
:seealso SearchResult.get_recipe:
1542
:return: A tuple ('proxy-search', start_keys_set, set(), -1)
1543
To recreate this result, create a PendingAncestryResult with the
1546
return ('proxy-search', self.heads, set(), -1)
1549
"""See SearchResult.get_keys.
1551
Returns all the keys for the ancestry of the heads, excluding
1554
return self._get_keys(self.repo.get_graph())
1556
def _get_keys(self, graph):
1557
NULL_REVISION = revision.NULL_REVISION
1558
keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
1559
if key != NULL_REVISION]
1563
"""Return false if the search lists 1 or more revisions."""
1564
if revision.NULL_REVISION in self.heads:
1565
return len(self.heads) == 1
1567
return len(self.heads) == 0
1569
def refine(self, seen, referenced):
1570
"""Create a new search by refining this search.
1572
:param seen: Revisions that have been satisfied.
1573
:param referenced: Revision references observed while satisfying some
1576
referenced = self.heads.union(referenced)
1577
return PendingAncestryResult(referenced - seen, self.repo)
1580
1498
def collapse_linear_regions(parent_map):
1581
1499
"""Collapse regions of the graph that are 'linear'.
added
removed
bzrlib/graph.py
