← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-11-06 16:01:48 UTC
  • mfrom: (5527.1.1 trunk)
  • Revision ID: pqm@pqm.ubuntu.com-20101106160148-8maemz21jbrhpzky
(vila) Move NEWS entry into the correct section (Vincent Ladeuil)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007-2010 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
 
 
17
import time
16
18
 
17
19
from bzrlib import (
 
20
    debug,
18
21
    errors,
 
22
    osutils,
19
23
    revision,
20
 
    symbol_versioning,
21
 
    tsort,
 
24
    trace,
22
25
    )
23
 
from bzrlib.deprecated_graph import (node_distances, select_farthest)
 
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
 
27
 
 
28
STEP_UNIQUE_SEARCHER_EVERY = 5
24
29
 
25
30
# DIAGRAM of terminology
26
31
#       A
55
60
        return 'DictParentsProvider(%r)' % self.ancestry
56
61
 
57
62
    def get_parent_map(self, keys):
58
 
        """See _StackedParentsProvider.get_parent_map"""
 
63
        """See StackedParentsProvider.get_parent_map"""
59
64
        ancestry = self.ancestry
60
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
61
66
 
62
 
 
63
 
class _StackedParentsProvider(object):
64
 
 
 
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
    
65
77
    def __init__(self, parent_providers):
66
78
        self._parent_providers = parent_providers
67
79
 
68
80
    def __repr__(self):
69
 
        return "_StackedParentsProvider(%r)" % self._parent_providers
 
81
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
70
82
 
71
83
    def get_parent_map(self, keys):
72
84
        """Get a mapping of keys => parents
93
105
 
94
106
 
95
107
class CachingParentsProvider(object):
96
 
    """A parents provider which will cache the revision => parents in a dict.
97
 
 
98
 
    This is useful for providers that have an expensive lookup.
 
108
    """A parents provider which will cache the revision => parents as a dict.
 
109
 
 
110
    This is useful for providers which have an expensive look up.
 
111
 
 
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.
 
115
 
 
116
    The cache is enabled by default, but may be disabled and re-enabled.
99
117
    """
 
118
    def __init__(self, parent_provider=None, get_parent_map=None):
 
119
        """Constructor.
100
120
 
101
 
    def __init__(self, parent_provider):
 
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.
 
125
        """
102
126
        self._real_provider = parent_provider
103
 
        # Theoretically we could use an LRUCache here
 
127
        if get_parent_map is None:
 
128
            self._get_parent_map = self._real_provider.get_parent_map
 
129
        else:
 
130
            self._get_parent_map = get_parent_map
 
131
        self._cache = None
 
132
        self.enable_cache(True)
 
133
 
 
134
    def __repr__(self):
 
135
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
 
136
 
 
137
    def enable_cache(self, cache_misses=True):
 
138
        """Enable cache."""
 
139
        if self._cache is not None:
 
140
            raise AssertionError('Cache enabled when already enabled.')
104
141
        self._cache = {}
105
 
 
106
 
    def __repr__(self):
107
 
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
 
142
        self._cache_misses = cache_misses
 
143
        self.missing_keys = set()
 
144
 
 
145
    def disable_cache(self):
 
146
        """Disable and clear the cache."""
 
147
        self._cache = None
 
148
        self._cache_misses = None
 
149
        self.missing_keys = set()
 
150
 
 
151
    def get_cached_map(self):
 
152
        """Return any cached get_parent_map values."""
 
153
        if self._cache is None:
 
154
            return None
 
155
        return dict(self._cache)
108
156
 
109
157
    def get_parent_map(self, keys):
110
 
        """See _StackedParentsProvider.get_parent_map"""
111
 
        needed = set()
112
 
        # If the _real_provider doesn't have a key, we cache a value of None,
113
 
        # which we then later use to realize we cannot provide a value for that
114
 
        # key.
115
 
        parent_map = {}
 
158
        """See StackedParentsProvider.get_parent_map."""
116
159
        cache = self._cache
 
160
        if cache is None:
 
161
            cache = self._get_parent_map(keys)
 
162
        else:
 
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 = {}
117
174
        for key in keys:
118
 
            if key in cache:
119
 
                value = cache[key]
120
 
                if value is not None:
121
 
                    parent_map[key] = value
122
 
            else:
123
 
                needed.add(key)
 
175
            value = cache.get(key)
 
176
            if value is not None:
 
177
                result[key] = value
 
178
        return result
124
179
 
125
 
        if needed:
126
 
            new_parents = self._real_provider.get_parent_map(needed)
127
 
            cache.update(new_parents)
128
 
            parent_map.update(new_parents)
129
 
            needed.difference_update(new_parents)
130
 
            cache.update(dict.fromkeys(needed, None))
131
 
        return parent_map
 
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
184
 
133
185
 
134
186
class Graph(object):
199
251
 
200
252
    def find_difference(self, left_revision, right_revision):
201
253
        """Determine the graph difference between two revisions"""
202
 
        border, common, (left, right) = self._find_border_ancestors(
 
254
        border, common, searchers = self._find_border_ancestors(
203
255
            [left_revision, right_revision])
204
 
        return (left.difference(right).difference(common),
205
 
                right.difference(left).difference(common))
206
 
 
207
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
208
 
    def get_parents(self, revisions):
209
 
        """Find revision ids of the parents of a list of revisions
210
 
 
211
 
        A list is returned of the same length as the input.  Each entry
212
 
        is a list of parent ids for the corresponding input revision.
213
 
 
214
 
        [NULL_REVISION] is used as the parent of the first user-committed
215
 
        revision.  Its parent list is empty.
216
 
 
217
 
        If the revision is not present (i.e. a ghost), None is used in place
218
 
        of the list of parents.
219
 
 
220
 
        Deprecated in bzr 1.2 - please see get_parent_map.
221
 
        """
222
 
        parents = self.get_parent_map(revisions)
223
 
        return [parent.get(r, None) for r in revisions]
 
256
        self._search_for_extra_common(common, searchers)
 
257
        left = searchers[0].seen
 
258
        right = searchers[1].seen
 
259
        return (left.difference(right), right.difference(left))
 
260
 
 
261
    def find_descendants(self, old_key, new_key):
 
262
        """Find descendants of old_key that are ancestors of new_key."""
 
263
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
264
            old_key, new_key))
 
265
        graph = Graph(DictParentsProvider(child_map))
 
266
        searcher = graph._make_breadth_first_searcher([old_key])
 
267
        list(searcher)
 
268
        return searcher.seen
 
269
 
 
270
    def _find_descendant_ancestors(self, old_key, new_key):
 
271
        """Find ancestors of new_key that may be descendants of old_key."""
 
272
        stop = self._make_breadth_first_searcher([old_key])
 
273
        descendants = self._make_breadth_first_searcher([new_key])
 
274
        for revisions in descendants:
 
275
            old_stop = stop.seen.intersection(revisions)
 
276
            descendants.stop_searching_any(old_stop)
 
277
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
278
            descendants.stop_searching_any(seen_stop)
 
279
        return descendants.seen.difference(stop.seen)
 
280
 
 
281
    def get_child_map(self, keys):
 
282
        """Get a mapping from parents to children of the specified keys.
 
283
 
 
284
        This is simply the inversion of get_parent_map.  Only supplied keys
 
285
        will be discovered as children.
 
286
        :return: a dict of key:child_list for keys.
 
287
        """
 
288
        parent_map = self._parents_provider.get_parent_map(keys)
 
289
        parent_child = {}
 
290
        for child, parents in sorted(parent_map.items()):
 
291
            for parent in parents:
 
292
                parent_child.setdefault(parent, []).append(child)
 
293
        return parent_child
 
294
 
 
295
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
 
296
        """Find the left-hand distance to the NULL_REVISION.
 
297
 
 
298
        (This can also be considered the revno of a branch at
 
299
        target_revision_id.)
 
300
 
 
301
        :param target_revision_id: A revision_id which we would like to know
 
302
            the revno for.
 
303
        :param known_revision_ids: [(revision_id, revno)] A list of known
 
304
            revno, revision_id tuples. We'll use this to seed the search.
 
305
        """
 
306
        # Map from revision_ids to a known value for their revno
 
307
        known_revnos = dict(known_revision_ids)
 
308
        cur_tip = target_revision_id
 
309
        num_steps = 0
 
310
        NULL_REVISION = revision.NULL_REVISION
 
311
        known_revnos[NULL_REVISION] = 0
 
312
 
 
313
        searching_known_tips = list(known_revnos.keys())
 
314
 
 
315
        unknown_searched = {}
 
316
 
 
317
        while cur_tip not in known_revnos:
 
318
            unknown_searched[cur_tip] = num_steps
 
319
            num_steps += 1
 
320
            to_search = set([cur_tip])
 
321
            to_search.update(searching_known_tips)
 
322
            parent_map = self.get_parent_map(to_search)
 
323
            parents = parent_map.get(cur_tip, None)
 
324
            if not parents: # An empty list or None is a ghost
 
325
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
 
326
                                                       cur_tip)
 
327
            cur_tip = parents[0]
 
328
            next_known_tips = []
 
329
            for revision_id in searching_known_tips:
 
330
                parents = parent_map.get(revision_id, None)
 
331
                if not parents:
 
332
                    continue
 
333
                next = parents[0]
 
334
                next_revno = known_revnos[revision_id] - 1
 
335
                if next in unknown_searched:
 
336
                    # We have enough information to return a value right now
 
337
                    return next_revno + unknown_searched[next]
 
338
                if next in known_revnos:
 
339
                    continue
 
340
                known_revnos[next] = next_revno
 
341
                next_known_tips.append(next)
 
342
            searching_known_tips = next_known_tips
 
343
 
 
344
        # We reached a known revision, so just add in how many steps it took to
 
345
        # get there.
 
346
        return known_revnos[cur_tip] + num_steps
 
347
 
 
348
    def find_lefthand_distances(self, keys):
 
349
        """Find the distance to null for all the keys in keys.
 
350
 
 
351
        :param keys: keys to lookup.
 
352
        :return: A dict key->distance for all of keys.
 
353
        """
 
354
        # Optimisable by concurrent searching, but a random spread should get
 
355
        # some sort of hit rate.
 
356
        result = {}
 
357
        known_revnos = []
 
358
        ghosts = []
 
359
        for key in keys:
 
360
            try:
 
361
                known_revnos.append(
 
362
                    (key, self.find_distance_to_null(key, known_revnos)))
 
363
            except errors.GhostRevisionsHaveNoRevno:
 
364
                ghosts.append(key)
 
365
        for key in ghosts:
 
366
            known_revnos.append((key, -1))
 
367
        return dict(known_revnos)
 
368
 
 
369
    def find_unique_ancestors(self, unique_revision, common_revisions):
 
370
        """Find the unique ancestors for a revision versus others.
 
371
 
 
372
        This returns the ancestry of unique_revision, excluding all revisions
 
373
        in the ancestry of common_revisions. If unique_revision is in the
 
374
        ancestry, then the empty set will be returned.
 
375
 
 
376
        :param unique_revision: The revision_id whose ancestry we are
 
377
            interested in.
 
378
            XXX: Would this API be better if we allowed multiple revisions on
 
379
                 to be searched here?
 
380
        :param common_revisions: Revision_ids of ancestries to exclude.
 
381
        :return: A set of revisions in the ancestry of unique_revision
 
382
        """
 
383
        if unique_revision in common_revisions:
 
384
            return set()
 
385
 
 
386
        # Algorithm description
 
387
        # 1) Walk backwards from the unique node and all common nodes.
 
388
        # 2) When a node is seen by both sides, stop searching it in the unique
 
389
        #    walker, include it in the common walker.
 
390
        # 3) Stop searching when there are no nodes left for the unique walker.
 
391
        #    At this point, you have a maximal set of unique nodes. Some of
 
392
        #    them may actually be common, and you haven't reached them yet.
 
393
        # 4) Start new searchers for the unique nodes, seeded with the
 
394
        #    information you have so far.
 
395
        # 5) Continue searching, stopping the common searches when the search
 
396
        #    tip is an ancestor of all unique nodes.
 
397
        # 6) Aggregate together unique searchers when they are searching the
 
398
        #    same tips. When all unique searchers are searching the same node,
 
399
        #    stop move it to a single 'all_unique_searcher'.
 
400
        # 7) The 'all_unique_searcher' represents the very 'tip' of searching.
 
401
        #    Most of the time this produces very little important information.
 
402
        #    So don't step it as quickly as the other searchers.
 
403
        # 8) Search is done when all common searchers have completed.
 
404
 
 
405
        unique_searcher, common_searcher = self._find_initial_unique_nodes(
 
406
            [unique_revision], common_revisions)
 
407
 
 
408
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
 
409
        if not unique_nodes:
 
410
            return unique_nodes
 
411
 
 
412
        (all_unique_searcher,
 
413
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
 
414
                                    unique_searcher, common_searcher)
 
415
 
 
416
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
 
417
                                  unique_tip_searchers, common_searcher)
 
418
        true_unique_nodes = unique_nodes.difference(common_searcher.seen)
 
419
        if 'graph' in debug.debug_flags:
 
420
            trace.mutter('Found %d truly unique nodes out of %d',
 
421
                         len(true_unique_nodes), len(unique_nodes))
 
422
        return true_unique_nodes
 
423
 
 
424
    def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
 
425
        """Steps 1-3 of find_unique_ancestors.
 
426
 
 
427
        Find the maximal set of unique nodes. Some of these might actually
 
428
        still be common, but we are sure that there are no other unique nodes.
 
429
 
 
430
        :return: (unique_searcher, common_searcher)
 
431
        """
 
432
 
 
433
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
 
434
        # we know that unique_revisions aren't in common_revisions, so skip
 
435
        # past them.
 
436
        unique_searcher.next()
 
437
        common_searcher = self._make_breadth_first_searcher(common_revisions)
 
438
 
 
439
        # As long as we are still finding unique nodes, keep searching
 
440
        while unique_searcher._next_query:
 
441
            next_unique_nodes = set(unique_searcher.step())
 
442
            next_common_nodes = set(common_searcher.step())
 
443
 
 
444
            # Check if either searcher encounters new nodes seen by the other
 
445
            # side.
 
446
            unique_are_common_nodes = next_unique_nodes.intersection(
 
447
                common_searcher.seen)
 
448
            unique_are_common_nodes.update(
 
449
                next_common_nodes.intersection(unique_searcher.seen))
 
450
            if unique_are_common_nodes:
 
451
                ancestors = unique_searcher.find_seen_ancestors(
 
452
                                unique_are_common_nodes)
 
453
                # TODO: This is a bit overboard, we only really care about
 
454
                #       the ancestors of the tips because the rest we
 
455
                #       already know. This is *correct* but causes us to
 
456
                #       search too much ancestry.
 
457
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
 
458
                unique_searcher.stop_searching_any(ancestors)
 
459
                common_searcher.start_searching(ancestors)
 
460
 
 
461
        return unique_searcher, common_searcher
 
462
 
 
463
    def _make_unique_searchers(self, unique_nodes, unique_searcher,
 
464
                               common_searcher):
 
465
        """Create a searcher for all the unique search tips (step 4).
 
466
 
 
467
        As a side effect, the common_searcher will stop searching any nodes
 
468
        that are ancestors of the unique searcher tips.
 
469
 
 
470
        :return: (all_unique_searcher, unique_tip_searchers)
 
471
        """
 
472
        unique_tips = self._remove_simple_descendants(unique_nodes,
 
473
                        self.get_parent_map(unique_nodes))
 
474
 
 
475
        if len(unique_tips) == 1:
 
476
            unique_tip_searchers = []
 
477
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
 
478
        else:
 
479
            unique_tip_searchers = []
 
480
            for tip in unique_tips:
 
481
                revs_to_search = unique_searcher.find_seen_ancestors([tip])
 
482
                revs_to_search.update(
 
483
                    common_searcher.find_seen_ancestors(revs_to_search))
 
484
                searcher = self._make_breadth_first_searcher(revs_to_search)
 
485
                # We don't care about the starting nodes.
 
486
                searcher._label = tip
 
487
                searcher.step()
 
488
                unique_tip_searchers.append(searcher)
 
489
 
 
490
            ancestor_all_unique = None
 
491
            for searcher in unique_tip_searchers:
 
492
                if ancestor_all_unique is None:
 
493
                    ancestor_all_unique = set(searcher.seen)
 
494
                else:
 
495
                    ancestor_all_unique = ancestor_all_unique.intersection(
 
496
                                                searcher.seen)
 
497
        # Collapse all the common nodes into a single searcher
 
498
        all_unique_searcher = self._make_breadth_first_searcher(
 
499
                                ancestor_all_unique)
 
500
        if ancestor_all_unique:
 
501
            # We've seen these nodes in all the searchers, so we'll just go to
 
502
            # the next
 
503
            all_unique_searcher.step()
 
504
 
 
505
            # Stop any search tips that are already known as ancestors of the
 
506
            # unique nodes
 
507
            stopped_common = common_searcher.stop_searching_any(
 
508
                common_searcher.find_seen_ancestors(ancestor_all_unique))
 
509
 
 
510
            total_stopped = 0
 
511
            for searcher in unique_tip_searchers:
 
512
                total_stopped += len(searcher.stop_searching_any(
 
513
                    searcher.find_seen_ancestors(ancestor_all_unique)))
 
514
        if 'graph' in debug.debug_flags:
 
515
            trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
 
516
                         ' (%d stopped search tips, %d common ancestors'
 
517
                         ' (%d stopped common)',
 
518
                         len(unique_nodes), len(unique_tip_searchers),
 
519
                         total_stopped, len(ancestor_all_unique),
 
520
                         len(stopped_common))
 
521
        return all_unique_searcher, unique_tip_searchers
 
522
 
 
523
    def _step_unique_and_common_searchers(self, common_searcher,
 
524
                                          unique_tip_searchers,
 
525
                                          unique_searcher):
 
526
        """Step all the searchers"""
 
527
        newly_seen_common = set(common_searcher.step())
 
528
        newly_seen_unique = set()
 
529
        for searcher in unique_tip_searchers:
 
530
            next = set(searcher.step())
 
531
            next.update(unique_searcher.find_seen_ancestors(next))
 
532
            next.update(common_searcher.find_seen_ancestors(next))
 
533
            for alt_searcher in unique_tip_searchers:
 
534
                if alt_searcher is searcher:
 
535
                    continue
 
536
                next.update(alt_searcher.find_seen_ancestors(next))
 
537
            searcher.start_searching(next)
 
538
            newly_seen_unique.update(next)
 
539
        return newly_seen_common, newly_seen_unique
 
540
 
 
541
    def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
 
542
                                         all_unique_searcher,
 
543
                                         newly_seen_unique, step_all_unique):
 
544
        """Find nodes that are common to all unique_tip_searchers.
 
545
 
 
546
        If it is time, step the all_unique_searcher, and add its nodes to the
 
547
        result.
 
548
        """
 
549
        common_to_all_unique_nodes = newly_seen_unique.copy()
 
550
        for searcher in unique_tip_searchers:
 
551
            common_to_all_unique_nodes.intersection_update(searcher.seen)
 
552
        common_to_all_unique_nodes.intersection_update(
 
553
                                    all_unique_searcher.seen)
 
554
        # Step all-unique less frequently than the other searchers.
 
555
        # In the common case, we don't need to spider out far here, so
 
556
        # avoid doing extra work.
 
557
        if step_all_unique:
 
558
            tstart = time.clock()
 
559
            nodes = all_unique_searcher.step()
 
560
            common_to_all_unique_nodes.update(nodes)
 
561
            if 'graph' in debug.debug_flags:
 
562
                tdelta = time.clock() - tstart
 
563
                trace.mutter('all_unique_searcher step() took %.3fs'
 
564
                             'for %d nodes (%d total), iteration: %s',
 
565
                             tdelta, len(nodes), len(all_unique_searcher.seen),
 
566
                             all_unique_searcher._iterations)
 
567
        return common_to_all_unique_nodes
 
568
 
 
569
    def _collapse_unique_searchers(self, unique_tip_searchers,
 
570
                                   common_to_all_unique_nodes):
 
571
        """Combine searchers that are searching the same tips.
 
572
 
 
573
        When two searchers are searching the same tips, we can stop one of the
 
574
        searchers. We also know that the maximal set of common ancestors is the
 
575
        intersection of the two original searchers.
 
576
 
 
577
        :return: A list of searchers that are searching unique nodes.
 
578
        """
 
579
        # Filter out searchers that don't actually search different
 
580
        # nodes. We already have the ancestry intersection for them
 
581
        unique_search_tips = {}
 
582
        for searcher in unique_tip_searchers:
 
583
            stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
 
584
            will_search_set = frozenset(searcher._next_query)
 
585
            if not will_search_set:
 
586
                if 'graph' in debug.debug_flags:
 
587
                    trace.mutter('Unique searcher %s was stopped.'
 
588
                                 ' (%s iterations) %d nodes stopped',
 
589
                                 searcher._label,
 
590
                                 searcher._iterations,
 
591
                                 len(stopped))
 
592
            elif will_search_set not in unique_search_tips:
 
593
                # This searcher is searching a unique set of nodes, let it
 
594
                unique_search_tips[will_search_set] = [searcher]
 
595
            else:
 
596
                unique_search_tips[will_search_set].append(searcher)
 
597
        # TODO: it might be possible to collapse searchers faster when they
 
598
        #       only have *some* search tips in common.
 
599
        next_unique_searchers = []
 
600
        for searchers in unique_search_tips.itervalues():
 
601
            if len(searchers) == 1:
 
602
                # Searching unique tips, go for it
 
603
                next_unique_searchers.append(searchers[0])
 
604
            else:
 
605
                # These searchers have started searching the same tips, we
 
606
                # don't need them to cover the same ground. The
 
607
                # intersection of their ancestry won't change, so create a
 
608
                # new searcher, combining their histories.
 
609
                next_searcher = searchers[0]
 
610
                for searcher in searchers[1:]:
 
611
                    next_searcher.seen.intersection_update(searcher.seen)
 
612
                if 'graph' in debug.debug_flags:
 
613
                    trace.mutter('Combining %d searchers into a single'
 
614
                                 ' searcher searching %d nodes with'
 
615
                                 ' %d ancestry',
 
616
                                 len(searchers),
 
617
                                 len(next_searcher._next_query),
 
618
                                 len(next_searcher.seen))
 
619
                next_unique_searchers.append(next_searcher)
 
620
        return next_unique_searchers
 
621
 
 
622
    def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
 
623
                             unique_tip_searchers, common_searcher):
 
624
        """Steps 5-8 of find_unique_ancestors.
 
625
 
 
626
        This function returns when common_searcher has stopped searching for
 
627
        more nodes.
 
628
        """
 
629
        # We step the ancestor_all_unique searcher only every
 
630
        # STEP_UNIQUE_SEARCHER_EVERY steps.
 
631
        step_all_unique_counter = 0
 
632
        # While we still have common nodes to search
 
633
        while common_searcher._next_query:
 
634
            (newly_seen_common,
 
635
             newly_seen_unique) = self._step_unique_and_common_searchers(
 
636
                common_searcher, unique_tip_searchers, unique_searcher)
 
637
            # These nodes are common ancestors of all unique nodes
 
638
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
 
639
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
 
640
                step_all_unique_counter==0)
 
641
            step_all_unique_counter = ((step_all_unique_counter + 1)
 
642
                                       % STEP_UNIQUE_SEARCHER_EVERY)
 
643
 
 
644
            if newly_seen_common:
 
645
                # If a 'common' node is an ancestor of all unique searchers, we
 
646
                # can stop searching it.
 
647
                common_searcher.stop_searching_any(
 
648
                    all_unique_searcher.seen.intersection(newly_seen_common))
 
649
            if common_to_all_unique_nodes:
 
650
                common_to_all_unique_nodes.update(
 
651
                    common_searcher.find_seen_ancestors(
 
652
                        common_to_all_unique_nodes))
 
653
                # The all_unique searcher can start searching the common nodes
 
654
                # but everyone else can stop.
 
655
                # This is the sort of thing where we would like to not have it
 
656
                # start_searching all of the nodes, but only mark all of them
 
657
                # as seen, and have it search only the actual tips. Otherwise
 
658
                # it is another get_parent_map() traversal for it to figure out
 
659
                # what we already should know.
 
660
                all_unique_searcher.start_searching(common_to_all_unique_nodes)
 
661
                common_searcher.stop_searching_any(common_to_all_unique_nodes)
 
662
 
 
663
            next_unique_searchers = self._collapse_unique_searchers(
 
664
                unique_tip_searchers, common_to_all_unique_nodes)
 
665
            if len(unique_tip_searchers) != len(next_unique_searchers):
 
666
                if 'graph' in debug.debug_flags:
 
667
                    trace.mutter('Collapsed %d unique searchers => %d'
 
668
                                 ' at %s iterations',
 
669
                                 len(unique_tip_searchers),
 
670
                                 len(next_unique_searchers),
 
671
                                 all_unique_searcher._iterations)
 
672
            unique_tip_searchers = next_unique_searchers
224
673
 
225
674
    def get_parent_map(self, revisions):
226
675
        """Get a map of key:parent_list for revisions.
253
702
        """
254
703
        if None in revisions:
255
704
            raise errors.InvalidRevisionId(None, self)
256
 
        common_searcher = self._make_breadth_first_searcher([])
257
705
        common_ancestors = set()
258
706
        searchers = [self._make_breadth_first_searcher([r])
259
707
                     for r in revisions]
260
708
        active_searchers = searchers[:]
261
709
        border_ancestors = set()
262
 
        def update_common(searcher, revisions):
263
 
            w_seen_ancestors = searcher.find_seen_ancestors(
264
 
                revision)
265
 
            stopped = searcher.stop_searching_any(w_seen_ancestors)
266
 
            common_ancestors.update(w_seen_ancestors)
267
 
            common_searcher.start_searching(stopped)
268
710
 
269
711
        while True:
270
 
            if len(active_searchers) == 0:
271
 
                return border_ancestors, common_ancestors, [s.seen for s in
272
 
                                                            searchers]
273
 
            try:
274
 
                new_common = common_searcher.next()
275
 
                common_ancestors.update(new_common)
276
 
            except StopIteration:
277
 
                pass
278
 
            else:
279
 
                for searcher in active_searchers:
280
 
                    for revision in new_common.intersection(searcher.seen):
281
 
                        update_common(searcher, revision)
282
 
 
283
712
            newly_seen = set()
284
 
            new_active_searchers = []
285
 
            for searcher in active_searchers:
286
 
                try:
287
 
                    newly_seen.update(searcher.next())
288
 
                except StopIteration:
289
 
                    pass
290
 
                else:
291
 
                    new_active_searchers.append(searcher)
292
 
            active_searchers = new_active_searchers
 
713
            for searcher in searchers:
 
714
                new_ancestors = searcher.step()
 
715
                if new_ancestors:
 
716
                    newly_seen.update(new_ancestors)
 
717
            new_common = set()
293
718
            for revision in newly_seen:
294
719
                if revision in common_ancestors:
295
 
                    for searcher in searchers:
296
 
                        update_common(searcher, revision)
 
720
                    # Not a border ancestor because it was seen as common
 
721
                    # already
 
722
                    new_common.add(revision)
297
723
                    continue
298
724
                for searcher in searchers:
299
725
                    if revision not in searcher.seen:
300
726
                        break
301
727
                else:
 
728
                    # This is a border because it is a first common that we see
 
729
                    # after walking for a while.
302
730
                    border_ancestors.add(revision)
303
 
                    for searcher in searchers:
304
 
                        update_common(searcher, revision)
 
731
                    new_common.add(revision)
 
732
            if new_common:
 
733
                for searcher in searchers:
 
734
                    new_common.update(searcher.find_seen_ancestors(new_common))
 
735
                for searcher in searchers:
 
736
                    searcher.start_searching(new_common)
 
737
                common_ancestors.update(new_common)
 
738
 
 
739
            # Figure out what the searchers will be searching next, and if
 
740
            # there is only 1 set being searched, then we are done searching,
 
741
            # since all searchers would have to be searching the same data,
 
742
            # thus it *must* be in common.
 
743
            unique_search_sets = set()
 
744
            for searcher in searchers:
 
745
                will_search_set = frozenset(searcher._next_query)
 
746
                if will_search_set not in unique_search_sets:
 
747
                    # This searcher is searching a unique set of nodes, let it
 
748
                    unique_search_sets.add(will_search_set)
 
749
 
 
750
            if len(unique_search_sets) == 1:
 
751
                nodes = unique_search_sets.pop()
 
752
                uncommon_nodes = nodes.difference(common_ancestors)
 
753
                if uncommon_nodes:
 
754
                    raise AssertionError("Somehow we ended up converging"
 
755
                                         " without actually marking them as"
 
756
                                         " in common."
 
757
                                         "\nStart_nodes: %s"
 
758
                                         "\nuncommon_nodes: %s"
 
759
                                         % (revisions, uncommon_nodes))
 
760
                break
 
761
        return border_ancestors, common_ancestors, searchers
305
762
 
306
763
    def heads(self, keys):
307
764
        """Return the heads from amongst keys.
387
844
                        new_common.add(ancestor)
388
845
                        for searcher in searchers.itervalues():
389
846
                            seen_ancestors =\
390
 
                                searcher.find_seen_ancestors(ancestor)
 
847
                                searcher.find_seen_ancestors([ancestor])
391
848
                            searcher.stop_searching_any(seen_ancestors)
392
849
            common_walker.start_searching(new_common)
393
850
        return candidate_heads
394
851
 
 
852
    def find_merge_order(self, tip_revision_id, lca_revision_ids):
 
853
        """Find the order that each revision was merged into tip.
 
854
 
 
855
        This basically just walks backwards with a stack, and walks left-first
 
856
        until it finds a node to stop.
 
857
        """
 
858
        if len(lca_revision_ids) == 1:
 
859
            return list(lca_revision_ids)
 
860
        looking_for = set(lca_revision_ids)
 
861
        # TODO: Is there a way we could do this "faster" by batching up the
 
862
        # get_parent_map requests?
 
863
        # TODO: Should we also be culling the ancestry search right away? We
 
864
        # could add looking_for to the "stop" list, and walk their
 
865
        # ancestry in batched mode. The flip side is it might mean we walk a
 
866
        # lot of "stop" nodes, rather than only the minimum.
 
867
        # Then again, without it we may trace back into ancestry we could have
 
868
        # stopped early.
 
869
        stack = [tip_revision_id]
 
870
        found = []
 
871
        stop = set()
 
872
        while stack and looking_for:
 
873
            next = stack.pop()
 
874
            stop.add(next)
 
875
            if next in looking_for:
 
876
                found.append(next)
 
877
                looking_for.remove(next)
 
878
                if len(looking_for) == 1:
 
879
                    found.append(looking_for.pop())
 
880
                    break
 
881
                continue
 
882
            parent_ids = self.get_parent_map([next]).get(next, None)
 
883
            if not parent_ids: # Ghost, nothing to search here
 
884
                continue
 
885
            for parent_id in reversed(parent_ids):
 
886
                # TODO: (performance) We see the parent at this point, but we
 
887
                #       wait to mark it until later to make sure we get left
 
888
                #       parents before right parents. However, instead of
 
889
                #       waiting until we have traversed enough parents, we
 
890
                #       could instead note that we've found it, and once all
 
891
                #       parents are in the stack, just reverse iterate the
 
892
                #       stack for them.
 
893
                if parent_id not in stop:
 
894
                    # this will need to be searched
 
895
                    stack.append(parent_id)
 
896
                stop.add(parent_id)
 
897
        return found
 
898
 
 
899
    def find_lefthand_merger(self, merged_key, tip_key):
 
900
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
901
 
 
902
        We do this by first finding the descendants of merged_key, then
 
903
        walking through the lefthand ancestry of tip_key until we find a key
 
904
        that doesn't descend from merged_key.  Its child is the key that
 
905
        merged merged_key.
 
906
 
 
907
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
908
            merged_key if it is a lefthand ancestor of tip_key.
 
909
            None if no ancestor of tip_key merged merged_key.
 
910
        """
 
911
        descendants = self.find_descendants(merged_key, tip_key)
 
912
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
913
        last_candidate = None
 
914
        for candidate in candidate_iterator:
 
915
            if candidate not in descendants:
 
916
                return last_candidate
 
917
            last_candidate = candidate
 
918
 
395
919
    def find_unique_lca(self, left_revision, right_revision,
396
920
                        count_steps=False):
397
921
        """Find a unique LCA.
424
948
                raise errors.NoCommonAncestor(left_revision, right_revision)
425
949
            revisions = lca
426
950
 
 
951
    def iter_ancestry(self, revision_ids):
 
952
        """Iterate the ancestry of this revision.
 
953
 
 
954
        :param revision_ids: Nodes to start the search
 
955
        :return: Yield tuples mapping a revision_id to its parents for the
 
956
            ancestry of revision_id.
 
957
            Ghosts will be returned with None as their parents, and nodes
 
958
            with no parents will have NULL_REVISION as their only parent. (As
 
959
            defined by get_parent_map.)
 
960
            There will also be a node for (NULL_REVISION, ())
 
961
        """
 
962
        pending = set(revision_ids)
 
963
        processed = set()
 
964
        while pending:
 
965
            processed.update(pending)
 
966
            next_map = self.get_parent_map(pending)
 
967
            next_pending = set()
 
968
            for item in next_map.iteritems():
 
969
                yield item
 
970
                next_pending.update(p for p in item[1] if p not in processed)
 
971
            ghosts = pending.difference(next_map)
 
972
            for ghost in ghosts:
 
973
                yield (ghost, None)
 
974
            pending = next_pending
 
975
 
 
976
    def iter_lefthand_ancestry(self, start_key, stop_keys=None):
 
977
        if stop_keys is None:
 
978
            stop_keys = ()
 
979
        next_key = start_key
 
980
        def get_parents(key):
 
981
            try:
 
982
                return self._parents_provider.get_parent_map([key])[key]
 
983
            except KeyError:
 
984
                raise errors.RevisionNotPresent(next_key, self)
 
985
        while True:
 
986
            if next_key in stop_keys:
 
987
                return
 
988
            parents = get_parents(next_key)
 
989
            yield next_key
 
990
            if len(parents) == 0:
 
991
                return
 
992
            else:
 
993
                next_key = parents[0]
 
994
 
427
995
    def iter_topo_order(self, revisions):
428
996
        """Iterate through the input revisions in topological order.
429
997
 
431
999
        An ancestor may sort after a descendant if the relationship is not
432
1000
        visible in the supplied list of revisions.
433
1001
        """
 
1002
        from bzrlib import tsort
434
1003
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
435
1004
        return sorter.iter_topo_order()
436
1005
 
444
1013
        return set([candidate_descendant]) == self.heads(
445
1014
            [candidate_ancestor, candidate_descendant])
446
1015
 
 
1016
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
 
1017
        """Determine whether a revision is between two others.
 
1018
 
 
1019
        returns true if and only if:
 
1020
        lower_bound_revid <= revid <= upper_bound_revid
 
1021
        """
 
1022
        return ((upper_bound_revid is None or
 
1023
                    self.is_ancestor(revid, upper_bound_revid)) and
 
1024
               (lower_bound_revid is None or
 
1025
                    self.is_ancestor(lower_bound_revid, revid)))
 
1026
 
 
1027
    def _search_for_extra_common(self, common, searchers):
 
1028
        """Make sure that unique nodes are genuinely unique.
 
1029
 
 
1030
        After _find_border_ancestors, all nodes marked "common" are indeed
 
1031
        common. Some of the nodes considered unique are not, due to history
 
1032
        shortcuts stopping the searches early.
 
1033
 
 
1034
        We know that we have searched enough when all common search tips are
 
1035
        descended from all unique (uncommon) nodes because we know that a node
 
1036
        cannot be an ancestor of its own ancestor.
 
1037
 
 
1038
        :param common: A set of common nodes
 
1039
        :param searchers: The searchers returned from _find_border_ancestors
 
1040
        :return: None
 
1041
        """
 
1042
        # Basic algorithm...
 
1043
        #   A) The passed in searchers should all be on the same tips, thus
 
1044
        #      they should be considered the "common" searchers.
 
1045
        #   B) We find the difference between the searchers, these are the
 
1046
        #      "unique" nodes for each side.
 
1047
        #   C) We do a quick culling so that we only start searching from the
 
1048
        #      more interesting unique nodes. (A unique ancestor is more
 
1049
        #      interesting than any of its children.)
 
1050
        #   D) We start searching for ancestors common to all unique nodes.
 
1051
        #   E) We have the common searchers stop searching any ancestors of
 
1052
        #      nodes found by (D)
 
1053
        #   F) When there are no more common search tips, we stop
 
1054
 
 
1055
        # TODO: We need a way to remove unique_searchers when they overlap with
 
1056
        #       other unique searchers.
 
1057
        if len(searchers) != 2:
 
1058
            raise NotImplementedError(
 
1059
                "Algorithm not yet implemented for > 2 searchers")
 
1060
        common_searchers = searchers
 
1061
        left_searcher = searchers[0]
 
1062
        right_searcher = searchers[1]
 
1063
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
 
1064
        if not unique: # No unique nodes, nothing to do
 
1065
            return
 
1066
        total_unique = len(unique)
 
1067
        unique = self._remove_simple_descendants(unique,
 
1068
                    self.get_parent_map(unique))
 
1069
        simple_unique = len(unique)
 
1070
 
 
1071
        unique_searchers = []
 
1072
        for revision_id in unique:
 
1073
            if revision_id in left_searcher.seen:
 
1074
                parent_searcher = left_searcher
 
1075
            else:
 
1076
                parent_searcher = right_searcher
 
1077
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
 
1078
            if not revs_to_search: # XXX: This shouldn't be possible
 
1079
                revs_to_search = [revision_id]
 
1080
            searcher = self._make_breadth_first_searcher(revs_to_search)
 
1081
            # We don't care about the starting nodes.
 
1082
            searcher.step()
 
1083
            unique_searchers.append(searcher)
 
1084
 
 
1085
        # possible todo: aggregate the common searchers into a single common
 
1086
        #   searcher, just make sure that we include the nodes into the .seen
 
1087
        #   properties of the original searchers
 
1088
 
 
1089
        ancestor_all_unique = None
 
1090
        for searcher in unique_searchers:
 
1091
            if ancestor_all_unique is None:
 
1092
                ancestor_all_unique = set(searcher.seen)
 
1093
            else:
 
1094
                ancestor_all_unique = ancestor_all_unique.intersection(
 
1095
                                            searcher.seen)
 
1096
 
 
1097
        trace.mutter('Started %s unique searchers for %s unique revisions',
 
1098
                     simple_unique, total_unique)
 
1099
 
 
1100
        while True: # If we have no more nodes we have nothing to do
 
1101
            newly_seen_common = set()
 
1102
            for searcher in common_searchers:
 
1103
                newly_seen_common.update(searcher.step())
 
1104
            newly_seen_unique = set()
 
1105
            for searcher in unique_searchers:
 
1106
                newly_seen_unique.update(searcher.step())
 
1107
            new_common_unique = set()
 
1108
            for revision in newly_seen_unique:
 
1109
                for searcher in unique_searchers:
 
1110
                    if revision not in searcher.seen:
 
1111
                        break
 
1112
                else:
 
1113
                    # This is a border because it is a first common that we see
 
1114
                    # after walking for a while.
 
1115
                    new_common_unique.add(revision)
 
1116
            if newly_seen_common:
 
1117
                # These are nodes descended from one of the 'common' searchers.
 
1118
                # Make sure all searchers are on the same page
 
1119
                for searcher in common_searchers:
 
1120
                    newly_seen_common.update(
 
1121
                        searcher.find_seen_ancestors(newly_seen_common))
 
1122
                # We start searching the whole ancestry. It is a bit wasteful,
 
1123
                # though. We really just want to mark all of these nodes as
 
1124
                # 'seen' and then start just the tips. However, it requires a
 
1125
                # get_parent_map() call to figure out the tips anyway, and all
 
1126
                # redundant requests should be fairly fast.
 
1127
                for searcher in common_searchers:
 
1128
                    searcher.start_searching(newly_seen_common)
 
1129
 
 
1130
                # If a 'common' node is an ancestor of all unique searchers, we
 
1131
                # can stop searching it.
 
1132
                stop_searching_common = ancestor_all_unique.intersection(
 
1133
                                            newly_seen_common)
 
1134
                if stop_searching_common:
 
1135
                    for searcher in common_searchers:
 
1136
                        searcher.stop_searching_any(stop_searching_common)
 
1137
            if new_common_unique:
 
1138
                # We found some ancestors that are common
 
1139
                for searcher in unique_searchers:
 
1140
                    new_common_unique.update(
 
1141
                        searcher.find_seen_ancestors(new_common_unique))
 
1142
                # Since these are common, we can grab another set of ancestors
 
1143
                # that we have seen
 
1144
                for searcher in common_searchers:
 
1145
                    new_common_unique.update(
 
1146
                        searcher.find_seen_ancestors(new_common_unique))
 
1147
 
 
1148
                # We can tell all of the unique searchers to start at these
 
1149
                # nodes, and tell all of the common searchers to *stop*
 
1150
                # searching these nodes
 
1151
                for searcher in unique_searchers:
 
1152
                    searcher.start_searching(new_common_unique)
 
1153
                for searcher in common_searchers:
 
1154
                    searcher.stop_searching_any(new_common_unique)
 
1155
                ancestor_all_unique.update(new_common_unique)
 
1156
 
 
1157
                # Filter out searchers that don't actually search different
 
1158
                # nodes. We already have the ancestry intersection for them
 
1159
                next_unique_searchers = []
 
1160
                unique_search_sets = set()
 
1161
                for searcher in unique_searchers:
 
1162
                    will_search_set = frozenset(searcher._next_query)
 
1163
                    if will_search_set not in unique_search_sets:
 
1164
                        # This searcher is searching a unique set of nodes, let it
 
1165
                        unique_search_sets.add(will_search_set)
 
1166
                        next_unique_searchers.append(searcher)
 
1167
                unique_searchers = next_unique_searchers
 
1168
            for searcher in common_searchers:
 
1169
                if searcher._next_query:
 
1170
                    break
 
1171
            else:
 
1172
                # All common searcher have stopped searching
 
1173
                return
 
1174
 
 
1175
    def _remove_simple_descendants(self, revisions, parent_map):
 
1176
        """remove revisions which are children of other ones in the set
 
1177
 
 
1178
        This doesn't do any graph searching, it just checks the immediate
 
1179
        parent_map to find if there are any children which can be removed.
 
1180
 
 
1181
        :param revisions: A set of revision_ids
 
1182
        :return: A set of revision_ids with the children removed
 
1183
        """
 
1184
        simple_ancestors = revisions.copy()
 
1185
        # TODO: jam 20071214 we *could* restrict it to searching only the
 
1186
        #       parent_map of revisions already present in 'revisions', but
 
1187
        #       considering the general use case, I think this is actually
 
1188
        #       better.
 
1189
 
 
1190
        # This is the same as the following loop. I don't know that it is any
 
1191
        # faster.
 
1192
        ## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
 
1193
        ##     if p_ids is not None and revisions.intersection(p_ids))
 
1194
        ## return simple_ancestors
 
1195
 
 
1196
        # Yet Another Way, invert the parent map (which can be cached)
 
1197
        ## descendants = {}
 
1198
        ## for revision_id, parent_ids in parent_map.iteritems():
 
1199
        ##   for p_id in parent_ids:
 
1200
        ##       descendants.setdefault(p_id, []).append(revision_id)
 
1201
        ## for revision in revisions.intersection(descendants):
 
1202
        ##   simple_ancestors.difference_update(descendants[revision])
 
1203
        ## return simple_ancestors
 
1204
        for revision, parent_ids in parent_map.iteritems():
 
1205
            if parent_ids is None:
 
1206
                continue
 
1207
            for parent_id in parent_ids:
 
1208
                if parent_id in revisions:
 
1209
                    # This node has a parent present in the set, so we can
 
1210
                    # remove it
 
1211
                    simple_ancestors.discard(revision)
 
1212
                    break
 
1213
        return simple_ancestors
 
1214
 
447
1215
 
448
1216
class HeadsCache(object):
449
1217
    """A cache of results for graph heads calls."""
473
1241
            return set(heads)
474
1242
 
475
1243
 
 
1244
class FrozenHeadsCache(object):
 
1245
    """Cache heads() calls, assuming the caller won't modify them."""
 
1246
 
 
1247
    def __init__(self, graph):
 
1248
        self.graph = graph
 
1249
        self._heads = {}
 
1250
 
 
1251
    def heads(self, keys):
 
1252
        """Return the heads of keys.
 
1253
 
 
1254
        Similar to Graph.heads(). The main difference is that the return value
 
1255
        is a frozen set which cannot be mutated.
 
1256
 
 
1257
        :see also: Graph.heads.
 
1258
        :param keys: The keys to calculate heads for.
 
1259
        :return: A frozenset containing the heads.
 
1260
        """
 
1261
        keys = frozenset(keys)
 
1262
        try:
 
1263
            return self._heads[keys]
 
1264
        except KeyError:
 
1265
            heads = frozenset(self.graph.heads(keys))
 
1266
            self._heads[keys] = heads
 
1267
            return heads
 
1268
 
 
1269
    def cache(self, keys, heads):
 
1270
        """Store a known value."""
 
1271
        self._heads[frozenset(keys)] = frozenset(heads)
 
1272
 
 
1273
 
476
1274
class _BreadthFirstSearcher(object):
477
1275
    """Parallel search breadth-first the ancestry of revisions.
478
1276
 
504
1302
 
505
1303
    def get_result(self):
506
1304
        """Get a SearchResult for the current state of this searcher.
507
 
        
 
1305
 
508
1306
        :return: A SearchResult for this search so far. The SearchResult is
509
1307
            static - the search can be advanced and the search result will not
510
1308
            be invalidated or altered.
514
1312
            # exclude keys for them. However, while we could have a second
515
1313
            # look-ahead result buffer and shuffle things around, this method
516
1314
            # is typically only called once per search - when memoising the
517
 
            # results of the search. 
 
1315
            # results of the search.
518
1316
            found, ghosts, next, parents = self._do_query(self._next_query)
519
1317
            # pretend we didn't query: perhaps we should tweak _do_query to be
520
1318
            # entirely stateless?
527
1325
        return SearchResult(self._started_keys, excludes, len(included_keys),
528
1326
            included_keys)
529
1327
 
 
1328
    def step(self):
 
1329
        try:
 
1330
            return self.next()
 
1331
        except StopIteration:
 
1332
            return ()
 
1333
 
530
1334
    def next(self):
531
1335
        """Return the next ancestors of this revision.
532
1336
 
555
1359
 
556
1360
    def next_with_ghosts(self):
557
1361
        """Return the next found ancestors, with ghosts split out.
558
 
        
 
1362
 
559
1363
        Ancestors are returned in the order they are seen in a breadth-first
560
1364
        traversal.  No ancestor will be returned more than once. Ancestors are
561
1365
        returned only after asking for their parents, which allows us to detect
597
1401
        :return: A tuple: (set(found_revisions), set(ghost_revisions),
598
1402
           set(parents_of_found_revisions), dict(found_revisions:parents)).
599
1403
        """
600
 
        found_parents = set()
 
1404
        found_revisions = set()
601
1405
        parents_of_found = set()
602
1406
        # revisions may contain nodes that point to other nodes in revisions:
603
1407
        # we want to filter them out.
604
1408
        self.seen.update(revisions)
605
1409
        parent_map = self._parents_provider.get_parent_map(revisions)
 
1410
        found_revisions.update(parent_map)
606
1411
        for rev_id, parents in parent_map.iteritems():
607
 
            found_parents.add(rev_id)
608
 
            parents_of_found.update(p for p in parents if p not in self.seen)
609
 
        ghost_parents = revisions - found_parents
610
 
        return found_parents, ghost_parents, parents_of_found, parent_map
 
1412
            if parents is None:
 
1413
                continue
 
1414
            new_found_parents = [p for p in parents if p not in self.seen]
 
1415
            if new_found_parents:
 
1416
                # Calling set.update() with an empty generator is actually
 
1417
                # rather expensive.
 
1418
                parents_of_found.update(new_found_parents)
 
1419
        ghost_revisions = revisions - found_revisions
 
1420
        return found_revisions, ghost_revisions, parents_of_found, parent_map
611
1421
 
612
1422
    def __iter__(self):
613
1423
        return self
614
1424
 
615
 
    def find_seen_ancestors(self, revision):
616
 
        """Find ancestors of this revision that have already been seen."""
617
 
        searcher = _BreadthFirstSearcher([revision], self._parents_provider)
618
 
        seen_ancestors = set()
619
 
        for ancestors in searcher:
620
 
            for ancestor in ancestors:
621
 
                if ancestor not in self.seen:
622
 
                    searcher.stop_searching_any([ancestor])
623
 
                else:
624
 
                    seen_ancestors.add(ancestor)
 
1425
    def find_seen_ancestors(self, revisions):
 
1426
        """Find ancestors of these revisions that have already been seen.
 
1427
 
 
1428
        This function generally makes the assumption that querying for the
 
1429
        parents of a node that has already been queried is reasonably cheap.
 
1430
        (eg, not a round trip to a remote host).
 
1431
        """
 
1432
        # TODO: Often we might ask one searcher for its seen ancestors, and
 
1433
        #       then ask another searcher the same question. This can result in
 
1434
        #       searching the same revisions repeatedly if the two searchers
 
1435
        #       have a lot of overlap.
 
1436
        all_seen = self.seen
 
1437
        pending = set(revisions).intersection(all_seen)
 
1438
        seen_ancestors = set(pending)
 
1439
 
 
1440
        if self._returning == 'next':
 
1441
            # self.seen contains what nodes have been returned, not what nodes
 
1442
            # have been queried. We don't want to probe for nodes that haven't
 
1443
            # been searched yet.
 
1444
            not_searched_yet = self._next_query
 
1445
        else:
 
1446
            not_searched_yet = ()
 
1447
        pending.difference_update(not_searched_yet)
 
1448
        get_parent_map = self._parents_provider.get_parent_map
 
1449
        while pending:
 
1450
            parent_map = get_parent_map(pending)
 
1451
            all_parents = []
 
1452
            # We don't care if it is a ghost, since it can't be seen if it is
 
1453
            # a ghost
 
1454
            for parent_ids in parent_map.itervalues():
 
1455
                all_parents.extend(parent_ids)
 
1456
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
 
1457
            seen_ancestors.update(next_pending)
 
1458
            next_pending.difference_update(not_searched_yet)
 
1459
            pending = next_pending
 
1460
 
625
1461
        return seen_ancestors
626
1462
 
627
1463
    def stop_searching_any(self, revisions):
629
1465
        Remove any of the specified revisions from the search list.
630
1466
 
631
1467
        None of the specified revisions are required to be present in the
632
 
        search list.  In this case, the call is a no-op.
 
1468
        search list.
 
1469
 
 
1470
        It is okay to call stop_searching_any() for revisions which were seen
 
1471
        in previous iterations. It is the callers responsibility to call
 
1472
        find_seen_ancestors() to make sure that current search tips that are
 
1473
        ancestors of those revisions are also stopped.  All explicitly stopped
 
1474
        revisions will be excluded from the search result's get_keys(), though.
633
1475
        """
 
1476
        # TODO: does this help performance?
 
1477
        # if not revisions:
 
1478
        #     return set()
634
1479
        revisions = frozenset(revisions)
635
1480
        if self._returning == 'next':
636
1481
            stopped = self._next_query.intersection(revisions)
641
1486
                self._current_ghosts.intersection(revisions))
642
1487
            self._current_present.difference_update(stopped)
643
1488
            self._current_ghosts.difference_update(stopped)
644
 
            # stopping 'x' should stop returning parents of 'x', but 
 
1489
            # stopping 'x' should stop returning parents of 'x', but
645
1490
            # not if 'y' always references those same parents
646
1491
            stop_rev_references = {}
647
1492
            for rev in stopped_present:
663
1508
                    stop_parents.add(rev_id)
664
1509
            self._next_query.difference_update(stop_parents)
665
1510
        self._stopped_keys.update(stopped)
 
1511
        self._stopped_keys.update(revisions)
666
1512
        return stopped
667
1513
 
668
1514
    def start_searching(self, revisions):
676
1522
        revisions = frozenset(revisions)
677
1523
        self._started_keys.update(revisions)
678
1524
        new_revisions = revisions.difference(self.seen)
679
 
        revs, ghosts, query, parents = self._do_query(revisions)
680
 
        self._stopped_keys.update(ghosts)
681
1525
        if self._returning == 'next':
682
1526
            self._next_query.update(new_revisions)
 
1527
            self.seen.update(new_revisions)
683
1528
        else:
684
1529
            # perform a query on revisions
 
1530
            revs, ghosts, query, parents = self._do_query(revisions)
 
1531
            self._stopped_keys.update(ghosts)
685
1532
            self._current_present.update(revs)
686
1533
            self._current_ghosts.update(ghosts)
687
1534
            self._next_query.update(query)
707
1554
            a SearchResult from a smart server, in which case the keys list is
708
1555
            not necessarily immediately available.
709
1556
        """
710
 
        self._recipe = (start_keys, exclude_keys, key_count)
 
1557
        self._recipe = ('search', start_keys, exclude_keys, key_count)
711
1558
        self._keys = frozenset(keys)
712
1559
 
713
1560
    def get_recipe(self):
714
1561
        """Return a recipe that can be used to replay this search.
715
 
        
 
1562
 
716
1563
        The recipe allows reconstruction of the same results at a later date
717
1564
        without knowing all the found keys. The essential elements are a list
718
 
        of keys to start and and to stop at. In order to give reproducible
 
1565
        of keys to start and to stop at. In order to give reproducible
719
1566
        results when ghosts are encountered by a search they are automatically
720
1567
        added to the exclude list (or else ghost filling may alter the
721
1568
        results).
722
1569
 
723
 
        :return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
724
 
            recreate the results of this search, create a breadth first
725
 
            searcher on the same graph starting at start_keys. Then call next()
726
 
            (or next_with_ghosts()) repeatedly, and on every result, call
727
 
            stop_searching_any on any keys from the exclude_keys set. The
728
 
            revision_count value acts as a trivial cross-check - the found
729
 
            revisions of the new search should have as many elements as
 
1570
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
 
1571
            revision_count). To recreate the results of this search, create a
 
1572
            breadth first searcher on the same graph starting at start_keys.
 
1573
            Then call next() (or next_with_ghosts()) repeatedly, and on every
 
1574
            result, call stop_searching_any on any keys from the exclude_keys
 
1575
            set. The revision_count value acts as a trivial cross-check - the
 
1576
            found revisions of the new search should have as many elements as
730
1577
            revision_count. If it does not, then additional revisions have been
731
1578
            ghosted since the search was executed the first time and the second
732
1579
            time.
740
1587
        """
741
1588
        return self._keys
742
1589
 
 
1590
    def is_empty(self):
 
1591
        """Return false if the search lists 1 or more revisions."""
 
1592
        return self._recipe[3] == 0
 
1593
 
 
1594
    def refine(self, seen, referenced):
 
1595
        """Create a new search by refining this search.
 
1596
 
 
1597
        :param seen: Revisions that have been satisfied.
 
1598
        :param referenced: Revision references observed while satisfying some
 
1599
            of this search.
 
1600
        """
 
1601
        start = self._recipe[1]
 
1602
        exclude = self._recipe[2]
 
1603
        count = self._recipe[3]
 
1604
        keys = self.get_keys()
 
1605
        # New heads = referenced + old heads - seen things - exclude
 
1606
        pending_refs = set(referenced)
 
1607
        pending_refs.update(start)
 
1608
        pending_refs.difference_update(seen)
 
1609
        pending_refs.difference_update(exclude)
 
1610
        # New exclude = old exclude + satisfied heads
 
1611
        seen_heads = start.intersection(seen)
 
1612
        exclude.update(seen_heads)
 
1613
        # keys gets seen removed
 
1614
        keys = keys - seen
 
1615
        # length is reduced by len(seen)
 
1616
        count -= len(seen)
 
1617
        return SearchResult(pending_refs, exclude, count, keys)
 
1618
 
 
1619
 
 
1620
class PendingAncestryResult(object):
 
1621
    """A search result that will reconstruct the ancestry for some graph heads.
 
1622
 
 
1623
    Unlike SearchResult, this doesn't hold the complete search result in
 
1624
    memory, it just holds a description of how to generate it.
 
1625
    """
 
1626
 
 
1627
    def __init__(self, heads, repo):
 
1628
        """Constructor.
 
1629
 
 
1630
        :param heads: an iterable of graph heads.
 
1631
        :param repo: a repository to use to generate the ancestry for the given
 
1632
            heads.
 
1633
        """
 
1634
        self.heads = frozenset(heads)
 
1635
        self.repo = repo
 
1636
 
 
1637
    def get_recipe(self):
 
1638
        """Return a recipe that can be used to replay this search.
 
1639
 
 
1640
        The recipe allows reconstruction of the same results at a later date.
 
1641
 
 
1642
        :seealso SearchResult.get_recipe:
 
1643
 
 
1644
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
 
1645
            To recreate this result, create a PendingAncestryResult with the
 
1646
            start_keys_set.
 
1647
        """
 
1648
        return ('proxy-search', self.heads, set(), -1)
 
1649
 
 
1650
    def get_keys(self):
 
1651
        """See SearchResult.get_keys.
 
1652
 
 
1653
        Returns all the keys for the ancestry of the heads, excluding
 
1654
        NULL_REVISION.
 
1655
        """
 
1656
        return self._get_keys(self.repo.get_graph())
 
1657
 
 
1658
    def _get_keys(self, graph):
 
1659
        NULL_REVISION = revision.NULL_REVISION
 
1660
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
 
1661
                if key != NULL_REVISION and parents is not None]
 
1662
        return keys
 
1663
 
 
1664
    def is_empty(self):
 
1665
        """Return false if the search lists 1 or more revisions."""
 
1666
        if revision.NULL_REVISION in self.heads:
 
1667
            return len(self.heads) == 1
 
1668
        else:
 
1669
            return len(self.heads) == 0
 
1670
 
 
1671
    def refine(self, seen, referenced):
 
1672
        """Create a new search by refining this search.
 
1673
 
 
1674
        :param seen: Revisions that have been satisfied.
 
1675
        :param referenced: Revision references observed while satisfying some
 
1676
            of this search.
 
1677
        """
 
1678
        referenced = self.heads.union(referenced)
 
1679
        return PendingAncestryResult(referenced - seen, self.repo)
 
1680
 
 
1681
 
 
1682
def collapse_linear_regions(parent_map):
 
1683
    """Collapse regions of the graph that are 'linear'.
 
1684
 
 
1685
    For example::
 
1686
 
 
1687
      A:[B], B:[C]
 
1688
 
 
1689
    can be collapsed by removing B and getting::
 
1690
 
 
1691
      A:[C]
 
1692
 
 
1693
    :param parent_map: A dictionary mapping children to their parents
 
1694
    :return: Another dictionary with 'linear' chains collapsed
 
1695
    """
 
1696
    # Note: this isn't a strictly minimal collapse. For example:
 
1697
    #   A
 
1698
    #  / \
 
1699
    # B   C
 
1700
    #  \ /
 
1701
    #   D
 
1702
    #   |
 
1703
    #   E
 
1704
    # Will not have 'D' removed, even though 'E' could fit. Also:
 
1705
    #   A
 
1706
    #   |    A
 
1707
    #   B => |
 
1708
    #   |    C
 
1709
    #   C
 
1710
    # A and C are both kept because they are edges of the graph. We *could* get
 
1711
    # rid of A if we wanted.
 
1712
    #   A
 
1713
    #  / \
 
1714
    # B   C
 
1715
    # |   |
 
1716
    # D   E
 
1717
    #  \ /
 
1718
    #   F
 
1719
    # Will not have any nodes removed, even though you do have an
 
1720
    # 'uninteresting' linear D->B and E->C
 
1721
    children = {}
 
1722
    for child, parents in parent_map.iteritems():
 
1723
        children.setdefault(child, [])
 
1724
        for p in parents:
 
1725
            children.setdefault(p, []).append(child)
 
1726
 
 
1727
    orig_children = dict(children)
 
1728
    removed = set()
 
1729
    result = dict(parent_map)
 
1730
    for node in parent_map:
 
1731
        parents = result[node]
 
1732
        if len(parents) == 1:
 
1733
            parent_children = children[parents[0]]
 
1734
            if len(parent_children) != 1:
 
1735
                # This is not the only child
 
1736
                continue
 
1737
            node_children = children[node]
 
1738
            if len(node_children) != 1:
 
1739
                continue
 
1740
            child_parents = result.get(node_children[0], None)
 
1741
            if len(child_parents) != 1:
 
1742
                # This is not its only parent
 
1743
                continue
 
1744
            # The child of this node only points at it, and the parent only has
 
1745
            # this as a child. remove this node, and join the others together
 
1746
            result[node_children[0]] = parents
 
1747
            children[parents[0]] = node_children
 
1748
            del result[node]
 
1749
            del children[node]
 
1750
            removed.add(node)
 
1751
 
 
1752
    return result
 
1753
 
 
1754
 
 
1755
class GraphThunkIdsToKeys(object):
 
1756
    """Forwards calls about 'ids' to be about keys internally."""
 
1757
 
 
1758
    def __init__(self, graph):
 
1759
        self._graph = graph
 
1760
 
 
1761
    def topo_sort(self):
 
1762
        return [r for (r,) in self._graph.topo_sort()]
 
1763
 
 
1764
    def heads(self, ids):
 
1765
        """See Graph.heads()"""
 
1766
        as_keys = [(i,) for i in ids]
 
1767
        head_keys = self._graph.heads(as_keys)
 
1768
        return set([h[0] for h in head_keys])
 
1769
 
 
1770
    def merge_sort(self, tip_revision):
 
1771
        return self._graph.merge_sort((tip_revision,))
 
1772
 
 
1773
 
 
1774
_counters = [0,0,0,0,0,0,0]
 
1775
try:
 
1776
    from bzrlib._known_graph_pyx import KnownGraph
 
1777
except ImportError, e:
 
1778
    osutils.failed_to_load_extension(e)
 
1779
    from bzrlib._known_graph_py import KnownGraph