← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Vincent Ladeuil
  • Date: 2010-02-09 17:27:46 UTC
  • mto: (5029.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 5030.
  • Revision ID: v.ladeuil+lp@free.fr-20100209172746-6f4mvlnr2mac807j
Move NoSmartTransportServer to bzrlib.tests.test_server

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, 2008, 2009 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_distance_to_null(self, target_revision_id, known_revision_ids):
 
262
        """Find the left-hand distance to the NULL_REVISION.
 
263
 
 
264
        (This can also be considered the revno of a branch at
 
265
        target_revision_id.)
 
266
 
 
267
        :param target_revision_id: A revision_id which we would like to know
 
268
            the revno for.
 
269
        :param known_revision_ids: [(revision_id, revno)] A list of known
 
270
            revno, revision_id tuples. We'll use this to seed the search.
 
271
        """
 
272
        # Map from revision_ids to a known value for their revno
 
273
        known_revnos = dict(known_revision_ids)
 
274
        cur_tip = target_revision_id
 
275
        num_steps = 0
 
276
        NULL_REVISION = revision.NULL_REVISION
 
277
        known_revnos[NULL_REVISION] = 0
 
278
 
 
279
        searching_known_tips = list(known_revnos.keys())
 
280
 
 
281
        unknown_searched = {}
 
282
 
 
283
        while cur_tip not in known_revnos:
 
284
            unknown_searched[cur_tip] = num_steps
 
285
            num_steps += 1
 
286
            to_search = set([cur_tip])
 
287
            to_search.update(searching_known_tips)
 
288
            parent_map = self.get_parent_map(to_search)
 
289
            parents = parent_map.get(cur_tip, None)
 
290
            if not parents: # An empty list or None is a ghost
 
291
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
 
292
                                                       cur_tip)
 
293
            cur_tip = parents[0]
 
294
            next_known_tips = []
 
295
            for revision_id in searching_known_tips:
 
296
                parents = parent_map.get(revision_id, None)
 
297
                if not parents:
 
298
                    continue
 
299
                next = parents[0]
 
300
                next_revno = known_revnos[revision_id] - 1
 
301
                if next in unknown_searched:
 
302
                    # We have enough information to return a value right now
 
303
                    return next_revno + unknown_searched[next]
 
304
                if next in known_revnos:
 
305
                    continue
 
306
                known_revnos[next] = next_revno
 
307
                next_known_tips.append(next)
 
308
            searching_known_tips = next_known_tips
 
309
 
 
310
        # We reached a known revision, so just add in how many steps it took to
 
311
        # get there.
 
312
        return known_revnos[cur_tip] + num_steps
 
313
 
 
314
    def find_lefthand_distances(self, keys):
 
315
        """Find the distance to null for all the keys in keys.
 
316
 
 
317
        :param keys: keys to lookup.
 
318
        :return: A dict key->distance for all of keys.
 
319
        """
 
320
        # Optimisable by concurrent searching, but a random spread should get
 
321
        # some sort of hit rate.
 
322
        result = {}
 
323
        known_revnos = []
 
324
        ghosts = []
 
325
        for key in keys:
 
326
            try:
 
327
                known_revnos.append(
 
328
                    (key, self.find_distance_to_null(key, known_revnos)))
 
329
            except errors.GhostRevisionsHaveNoRevno:
 
330
                ghosts.append(key)
 
331
        for key in ghosts:
 
332
            known_revnos.append((key, -1))
 
333
        return dict(known_revnos)
 
334
 
 
335
    def find_unique_ancestors(self, unique_revision, common_revisions):
 
336
        """Find the unique ancestors for a revision versus others.
 
337
 
 
338
        This returns the ancestry of unique_revision, excluding all revisions
 
339
        in the ancestry of common_revisions. If unique_revision is in the
 
340
        ancestry, then the empty set will be returned.
 
341
 
 
342
        :param unique_revision: The revision_id whose ancestry we are
 
343
            interested in.
 
344
            XXX: Would this API be better if we allowed multiple revisions on
 
345
                 to be searched here?
 
346
        :param common_revisions: Revision_ids of ancestries to exclude.
 
347
        :return: A set of revisions in the ancestry of unique_revision
 
348
        """
 
349
        if unique_revision in common_revisions:
 
350
            return set()
 
351
 
 
352
        # Algorithm description
 
353
        # 1) Walk backwards from the unique node and all common nodes.
 
354
        # 2) When a node is seen by both sides, stop searching it in the unique
 
355
        #    walker, include it in the common walker.
 
356
        # 3) Stop searching when there are no nodes left for the unique walker.
 
357
        #    At this point, you have a maximal set of unique nodes. Some of
 
358
        #    them may actually be common, and you haven't reached them yet.
 
359
        # 4) Start new searchers for the unique nodes, seeded with the
 
360
        #    information you have so far.
 
361
        # 5) Continue searching, stopping the common searches when the search
 
362
        #    tip is an ancestor of all unique nodes.
 
363
        # 6) Aggregate together unique searchers when they are searching the
 
364
        #    same tips. When all unique searchers are searching the same node,
 
365
        #    stop move it to a single 'all_unique_searcher'.
 
366
        # 7) The 'all_unique_searcher' represents the very 'tip' of searching.
 
367
        #    Most of the time this produces very little important information.
 
368
        #    So don't step it as quickly as the other searchers.
 
369
        # 8) Search is done when all common searchers have completed.
 
370
 
 
371
        unique_searcher, common_searcher = self._find_initial_unique_nodes(
 
372
            [unique_revision], common_revisions)
 
373
 
 
374
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
 
375
        if not unique_nodes:
 
376
            return unique_nodes
 
377
 
 
378
        (all_unique_searcher,
 
379
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
 
380
                                    unique_searcher, common_searcher)
 
381
 
 
382
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
 
383
                                  unique_tip_searchers, common_searcher)
 
384
        true_unique_nodes = unique_nodes.difference(common_searcher.seen)
 
385
        if 'graph' in debug.debug_flags:
 
386
            trace.mutter('Found %d truly unique nodes out of %d',
 
387
                         len(true_unique_nodes), len(unique_nodes))
 
388
        return true_unique_nodes
 
389
 
 
390
    def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
 
391
        """Steps 1-3 of find_unique_ancestors.
 
392
 
 
393
        Find the maximal set of unique nodes. Some of these might actually
 
394
        still be common, but we are sure that there are no other unique nodes.
 
395
 
 
396
        :return: (unique_searcher, common_searcher)
 
397
        """
 
398
 
 
399
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
 
400
        # we know that unique_revisions aren't in common_revisions, so skip
 
401
        # past them.
 
402
        unique_searcher.next()
 
403
        common_searcher = self._make_breadth_first_searcher(common_revisions)
 
404
 
 
405
        # As long as we are still finding unique nodes, keep searching
 
406
        while unique_searcher._next_query:
 
407
            next_unique_nodes = set(unique_searcher.step())
 
408
            next_common_nodes = set(common_searcher.step())
 
409
 
 
410
            # Check if either searcher encounters new nodes seen by the other
 
411
            # side.
 
412
            unique_are_common_nodes = next_unique_nodes.intersection(
 
413
                common_searcher.seen)
 
414
            unique_are_common_nodes.update(
 
415
                next_common_nodes.intersection(unique_searcher.seen))
 
416
            if unique_are_common_nodes:
 
417
                ancestors = unique_searcher.find_seen_ancestors(
 
418
                                unique_are_common_nodes)
 
419
                # TODO: This is a bit overboard, we only really care about
 
420
                #       the ancestors of the tips because the rest we
 
421
                #       already know. This is *correct* but causes us to
 
422
                #       search too much ancestry.
 
423
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
 
424
                unique_searcher.stop_searching_any(ancestors)
 
425
                common_searcher.start_searching(ancestors)
 
426
 
 
427
        return unique_searcher, common_searcher
 
428
 
 
429
    def _make_unique_searchers(self, unique_nodes, unique_searcher,
 
430
                               common_searcher):
 
431
        """Create a searcher for all the unique search tips (step 4).
 
432
 
 
433
        As a side effect, the common_searcher will stop searching any nodes
 
434
        that are ancestors of the unique searcher tips.
 
435
 
 
436
        :return: (all_unique_searcher, unique_tip_searchers)
 
437
        """
 
438
        unique_tips = self._remove_simple_descendants(unique_nodes,
 
439
                        self.get_parent_map(unique_nodes))
 
440
 
 
441
        if len(unique_tips) == 1:
 
442
            unique_tip_searchers = []
 
443
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
 
444
        else:
 
445
            unique_tip_searchers = []
 
446
            for tip in unique_tips:
 
447
                revs_to_search = unique_searcher.find_seen_ancestors([tip])
 
448
                revs_to_search.update(
 
449
                    common_searcher.find_seen_ancestors(revs_to_search))
 
450
                searcher = self._make_breadth_first_searcher(revs_to_search)
 
451
                # We don't care about the starting nodes.
 
452
                searcher._label = tip
 
453
                searcher.step()
 
454
                unique_tip_searchers.append(searcher)
 
455
 
 
456
            ancestor_all_unique = None
 
457
            for searcher in unique_tip_searchers:
 
458
                if ancestor_all_unique is None:
 
459
                    ancestor_all_unique = set(searcher.seen)
 
460
                else:
 
461
                    ancestor_all_unique = ancestor_all_unique.intersection(
 
462
                                                searcher.seen)
 
463
        # Collapse all the common nodes into a single searcher
 
464
        all_unique_searcher = self._make_breadth_first_searcher(
 
465
                                ancestor_all_unique)
 
466
        if ancestor_all_unique:
 
467
            # We've seen these nodes in all the searchers, so we'll just go to
 
468
            # the next
 
469
            all_unique_searcher.step()
 
470
 
 
471
            # Stop any search tips that are already known as ancestors of the
 
472
            # unique nodes
 
473
            stopped_common = common_searcher.stop_searching_any(
 
474
                common_searcher.find_seen_ancestors(ancestor_all_unique))
 
475
 
 
476
            total_stopped = 0
 
477
            for searcher in unique_tip_searchers:
 
478
                total_stopped += len(searcher.stop_searching_any(
 
479
                    searcher.find_seen_ancestors(ancestor_all_unique)))
 
480
        if 'graph' in debug.debug_flags:
 
481
            trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
 
482
                         ' (%d stopped search tips, %d common ancestors'
 
483
                         ' (%d stopped common)',
 
484
                         len(unique_nodes), len(unique_tip_searchers),
 
485
                         total_stopped, len(ancestor_all_unique),
 
486
                         len(stopped_common))
 
487
        return all_unique_searcher, unique_tip_searchers
 
488
 
 
489
    def _step_unique_and_common_searchers(self, common_searcher,
 
490
                                          unique_tip_searchers,
 
491
                                          unique_searcher):
 
492
        """Step all the searchers"""
 
493
        newly_seen_common = set(common_searcher.step())
 
494
        newly_seen_unique = set()
 
495
        for searcher in unique_tip_searchers:
 
496
            next = set(searcher.step())
 
497
            next.update(unique_searcher.find_seen_ancestors(next))
 
498
            next.update(common_searcher.find_seen_ancestors(next))
 
499
            for alt_searcher in unique_tip_searchers:
 
500
                if alt_searcher is searcher:
 
501
                    continue
 
502
                next.update(alt_searcher.find_seen_ancestors(next))
 
503
            searcher.start_searching(next)
 
504
            newly_seen_unique.update(next)
 
505
        return newly_seen_common, newly_seen_unique
 
506
 
 
507
    def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
 
508
                                         all_unique_searcher,
 
509
                                         newly_seen_unique, step_all_unique):
 
510
        """Find nodes that are common to all unique_tip_searchers.
 
511
 
 
512
        If it is time, step the all_unique_searcher, and add its nodes to the
 
513
        result.
 
514
        """
 
515
        common_to_all_unique_nodes = newly_seen_unique.copy()
 
516
        for searcher in unique_tip_searchers:
 
517
            common_to_all_unique_nodes.intersection_update(searcher.seen)
 
518
        common_to_all_unique_nodes.intersection_update(
 
519
                                    all_unique_searcher.seen)
 
520
        # Step all-unique less frequently than the other searchers.
 
521
        # In the common case, we don't need to spider out far here, so
 
522
        # avoid doing extra work.
 
523
        if step_all_unique:
 
524
            tstart = time.clock()
 
525
            nodes = all_unique_searcher.step()
 
526
            common_to_all_unique_nodes.update(nodes)
 
527
            if 'graph' in debug.debug_flags:
 
528
                tdelta = time.clock() - tstart
 
529
                trace.mutter('all_unique_searcher step() took %.3fs'
 
530
                             'for %d nodes (%d total), iteration: %s',
 
531
                             tdelta, len(nodes), len(all_unique_searcher.seen),
 
532
                             all_unique_searcher._iterations)
 
533
        return common_to_all_unique_nodes
 
534
 
 
535
    def _collapse_unique_searchers(self, unique_tip_searchers,
 
536
                                   common_to_all_unique_nodes):
 
537
        """Combine searchers that are searching the same tips.
 
538
 
 
539
        When two searchers are searching the same tips, we can stop one of the
 
540
        searchers. We also know that the maximal set of common ancestors is the
 
541
        intersection of the two original searchers.
 
542
 
 
543
        :return: A list of searchers that are searching unique nodes.
 
544
        """
 
545
        # Filter out searchers that don't actually search different
 
546
        # nodes. We already have the ancestry intersection for them
 
547
        unique_search_tips = {}
 
548
        for searcher in unique_tip_searchers:
 
549
            stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
 
550
            will_search_set = frozenset(searcher._next_query)
 
551
            if not will_search_set:
 
552
                if 'graph' in debug.debug_flags:
 
553
                    trace.mutter('Unique searcher %s was stopped.'
 
554
                                 ' (%s iterations) %d nodes stopped',
 
555
                                 searcher._label,
 
556
                                 searcher._iterations,
 
557
                                 len(stopped))
 
558
            elif will_search_set not in unique_search_tips:
 
559
                # This searcher is searching a unique set of nodes, let it
 
560
                unique_search_tips[will_search_set] = [searcher]
 
561
            else:
 
562
                unique_search_tips[will_search_set].append(searcher)
 
563
        # TODO: it might be possible to collapse searchers faster when they
 
564
        #       only have *some* search tips in common.
 
565
        next_unique_searchers = []
 
566
        for searchers in unique_search_tips.itervalues():
 
567
            if len(searchers) == 1:
 
568
                # Searching unique tips, go for it
 
569
                next_unique_searchers.append(searchers[0])
 
570
            else:
 
571
                # These searchers have started searching the same tips, we
 
572
                # don't need them to cover the same ground. The
 
573
                # intersection of their ancestry won't change, so create a
 
574
                # new searcher, combining their histories.
 
575
                next_searcher = searchers[0]
 
576
                for searcher in searchers[1:]:
 
577
                    next_searcher.seen.intersection_update(searcher.seen)
 
578
                if 'graph' in debug.debug_flags:
 
579
                    trace.mutter('Combining %d searchers into a single'
 
580
                                 ' searcher searching %d nodes with'
 
581
                                 ' %d ancestry',
 
582
                                 len(searchers),
 
583
                                 len(next_searcher._next_query),
 
584
                                 len(next_searcher.seen))
 
585
                next_unique_searchers.append(next_searcher)
 
586
        return next_unique_searchers
 
587
 
 
588
    def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
 
589
                             unique_tip_searchers, common_searcher):
 
590
        """Steps 5-8 of find_unique_ancestors.
 
591
 
 
592
        This function returns when common_searcher has stopped searching for
 
593
        more nodes.
 
594
        """
 
595
        # We step the ancestor_all_unique searcher only every
 
596
        # STEP_UNIQUE_SEARCHER_EVERY steps.
 
597
        step_all_unique_counter = 0
 
598
        # While we still have common nodes to search
 
599
        while common_searcher._next_query:
 
600
            (newly_seen_common,
 
601
             newly_seen_unique) = self._step_unique_and_common_searchers(
 
602
                common_searcher, unique_tip_searchers, unique_searcher)
 
603
            # These nodes are common ancestors of all unique nodes
 
604
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
 
605
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
 
606
                step_all_unique_counter==0)
 
607
            step_all_unique_counter = ((step_all_unique_counter + 1)
 
608
                                       % STEP_UNIQUE_SEARCHER_EVERY)
 
609
 
 
610
            if newly_seen_common:
 
611
                # If a 'common' node is an ancestor of all unique searchers, we
 
612
                # can stop searching it.
 
613
                common_searcher.stop_searching_any(
 
614
                    all_unique_searcher.seen.intersection(newly_seen_common))
 
615
            if common_to_all_unique_nodes:
 
616
                common_to_all_unique_nodes.update(
 
617
                    common_searcher.find_seen_ancestors(
 
618
                        common_to_all_unique_nodes))
 
619
                # The all_unique searcher can start searching the common nodes
 
620
                # but everyone else can stop.
 
621
                # This is the sort of thing where we would like to not have it
 
622
                # start_searching all of the nodes, but only mark all of them
 
623
                # as seen, and have it search only the actual tips. Otherwise
 
624
                # it is another get_parent_map() traversal for it to figure out
 
625
                # what we already should know.
 
626
                all_unique_searcher.start_searching(common_to_all_unique_nodes)
 
627
                common_searcher.stop_searching_any(common_to_all_unique_nodes)
 
628
 
 
629
            next_unique_searchers = self._collapse_unique_searchers(
 
630
                unique_tip_searchers, common_to_all_unique_nodes)
 
631
            if len(unique_tip_searchers) != len(next_unique_searchers):
 
632
                if 'graph' in debug.debug_flags:
 
633
                    trace.mutter('Collapsed %d unique searchers => %d'
 
634
                                 ' at %s iterations',
 
635
                                 len(unique_tip_searchers),
 
636
                                 len(next_unique_searchers),
 
637
                                 all_unique_searcher._iterations)
 
638
            unique_tip_searchers = next_unique_searchers
224
639
 
225
640
    def get_parent_map(self, revisions):
226
641
        """Get a map of key:parent_list for revisions.
253
668
        """
254
669
        if None in revisions:
255
670
            raise errors.InvalidRevisionId(None, self)
256
 
        common_searcher = self._make_breadth_first_searcher([])
257
671
        common_ancestors = set()
258
672
        searchers = [self._make_breadth_first_searcher([r])
259
673
                     for r in revisions]
260
674
        active_searchers = searchers[:]
261
675
        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
676
 
269
677
        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
678
            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
 
679
            for searcher in searchers:
 
680
                new_ancestors = searcher.step()
 
681
                if new_ancestors:
 
682
                    newly_seen.update(new_ancestors)
 
683
            new_common = set()
293
684
            for revision in newly_seen:
294
685
                if revision in common_ancestors:
295
 
                    for searcher in searchers:
296
 
                        update_common(searcher, revision)
 
686
                    # Not a border ancestor because it was seen as common
 
687
                    # already
 
688
                    new_common.add(revision)
297
689
                    continue
298
690
                for searcher in searchers:
299
691
                    if revision not in searcher.seen:
300
692
                        break
301
693
                else:
 
694
                    # This is a border because it is a first common that we see
 
695
                    # after walking for a while.
302
696
                    border_ancestors.add(revision)
303
 
                    for searcher in searchers:
304
 
                        update_common(searcher, revision)
 
697
                    new_common.add(revision)
 
698
            if new_common:
 
699
                for searcher in searchers:
 
700
                    new_common.update(searcher.find_seen_ancestors(new_common))
 
701
                for searcher in searchers:
 
702
                    searcher.start_searching(new_common)
 
703
                common_ancestors.update(new_common)
 
704
 
 
705
            # Figure out what the searchers will be searching next, and if
 
706
            # there is only 1 set being searched, then we are done searching,
 
707
            # since all searchers would have to be searching the same data,
 
708
            # thus it *must* be in common.
 
709
            unique_search_sets = set()
 
710
            for searcher in searchers:
 
711
                will_search_set = frozenset(searcher._next_query)
 
712
                if will_search_set not in unique_search_sets:
 
713
                    # This searcher is searching a unique set of nodes, let it
 
714
                    unique_search_sets.add(will_search_set)
 
715
 
 
716
            if len(unique_search_sets) == 1:
 
717
                nodes = unique_search_sets.pop()
 
718
                uncommon_nodes = nodes.difference(common_ancestors)
 
719
                if uncommon_nodes:
 
720
                    raise AssertionError("Somehow we ended up converging"
 
721
                                         " without actually marking them as"
 
722
                                         " in common."
 
723
                                         "\nStart_nodes: %s"
 
724
                                         "\nuncommon_nodes: %s"
 
725
                                         % (revisions, uncommon_nodes))
 
726
                break
 
727
        return border_ancestors, common_ancestors, searchers
305
728
 
306
729
    def heads(self, keys):
307
730
        """Return the heads from amongst keys.
387
810
                        new_common.add(ancestor)
388
811
                        for searcher in searchers.itervalues():
389
812
                            seen_ancestors =\
390
 
                                searcher.find_seen_ancestors(ancestor)
 
813
                                searcher.find_seen_ancestors([ancestor])
391
814
                            searcher.stop_searching_any(seen_ancestors)
392
815
            common_walker.start_searching(new_common)
393
816
        return candidate_heads
394
817
 
 
818
    def find_merge_order(self, tip_revision_id, lca_revision_ids):
 
819
        """Find the order that each revision was merged into tip.
 
820
 
 
821
        This basically just walks backwards with a stack, and walks left-first
 
822
        until it finds a node to stop.
 
823
        """
 
824
        if len(lca_revision_ids) == 1:
 
825
            return list(lca_revision_ids)
 
826
        looking_for = set(lca_revision_ids)
 
827
        # TODO: Is there a way we could do this "faster" by batching up the
 
828
        # get_parent_map requests?
 
829
        # TODO: Should we also be culling the ancestry search right away? We
 
830
        # could add looking_for to the "stop" list, and walk their
 
831
        # ancestry in batched mode. The flip side is it might mean we walk a
 
832
        # lot of "stop" nodes, rather than only the minimum.
 
833
        # Then again, without it we may trace back into ancestry we could have
 
834
        # stopped early.
 
835
        stack = [tip_revision_id]
 
836
        found = []
 
837
        stop = set()
 
838
        while stack and looking_for:
 
839
            next = stack.pop()
 
840
            stop.add(next)
 
841
            if next in looking_for:
 
842
                found.append(next)
 
843
                looking_for.remove(next)
 
844
                if len(looking_for) == 1:
 
845
                    found.append(looking_for.pop())
 
846
                    break
 
847
                continue
 
848
            parent_ids = self.get_parent_map([next]).get(next, None)
 
849
            if not parent_ids: # Ghost, nothing to search here
 
850
                continue
 
851
            for parent_id in reversed(parent_ids):
 
852
                # TODO: (performance) We see the parent at this point, but we
 
853
                #       wait to mark it until later to make sure we get left
 
854
                #       parents before right parents. However, instead of
 
855
                #       waiting until we have traversed enough parents, we
 
856
                #       could instead note that we've found it, and once all
 
857
                #       parents are in the stack, just reverse iterate the
 
858
                #       stack for them.
 
859
                if parent_id not in stop:
 
860
                    # this will need to be searched
 
861
                    stack.append(parent_id)
 
862
                stop.add(parent_id)
 
863
        return found
 
864
 
395
865
    def find_unique_lca(self, left_revision, right_revision,
396
866
                        count_steps=False):
397
867
        """Find a unique LCA.
456
926
        An ancestor may sort after a descendant if the relationship is not
457
927
        visible in the supplied list of revisions.
458
928
        """
 
929
        from bzrlib import tsort
459
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
460
931
        return sorter.iter_topo_order()
461
932
 
469
940
        return set([candidate_descendant]) == self.heads(
470
941
            [candidate_ancestor, candidate_descendant])
471
942
 
 
943
    def is_between(self, revid, lower_bound_revid, upper_bound_revid):
 
944
        """Determine whether a revision is between two others.
 
945
 
 
946
        returns true if and only if:
 
947
        lower_bound_revid <= revid <= upper_bound_revid
 
948
        """
 
949
        return ((upper_bound_revid is None or
 
950
                    self.is_ancestor(revid, upper_bound_revid)) and
 
951
               (lower_bound_revid is None or
 
952
                    self.is_ancestor(lower_bound_revid, revid)))
 
953
 
 
954
    def _search_for_extra_common(self, common, searchers):
 
955
        """Make sure that unique nodes are genuinely unique.
 
956
 
 
957
        After _find_border_ancestors, all nodes marked "common" are indeed
 
958
        common. Some of the nodes considered unique are not, due to history
 
959
        shortcuts stopping the searches early.
 
960
 
 
961
        We know that we have searched enough when all common search tips are
 
962
        descended from all unique (uncommon) nodes because we know that a node
 
963
        cannot be an ancestor of its own ancestor.
 
964
 
 
965
        :param common: A set of common nodes
 
966
        :param searchers: The searchers returned from _find_border_ancestors
 
967
        :return: None
 
968
        """
 
969
        # Basic algorithm...
 
970
        #   A) The passed in searchers should all be on the same tips, thus
 
971
        #      they should be considered the "common" searchers.
 
972
        #   B) We find the difference between the searchers, these are the
 
973
        #      "unique" nodes for each side.
 
974
        #   C) We do a quick culling so that we only start searching from the
 
975
        #      more interesting unique nodes. (A unique ancestor is more
 
976
        #      interesting than any of its children.)
 
977
        #   D) We start searching for ancestors common to all unique nodes.
 
978
        #   E) We have the common searchers stop searching any ancestors of
 
979
        #      nodes found by (D)
 
980
        #   F) When there are no more common search tips, we stop
 
981
 
 
982
        # TODO: We need a way to remove unique_searchers when they overlap with
 
983
        #       other unique searchers.
 
984
        if len(searchers) != 2:
 
985
            raise NotImplementedError(
 
986
                "Algorithm not yet implemented for > 2 searchers")
 
987
        common_searchers = searchers
 
988
        left_searcher = searchers[0]
 
989
        right_searcher = searchers[1]
 
990
        unique = left_searcher.seen.symmetric_difference(right_searcher.seen)
 
991
        if not unique: # No unique nodes, nothing to do
 
992
            return
 
993
        total_unique = len(unique)
 
994
        unique = self._remove_simple_descendants(unique,
 
995
                    self.get_parent_map(unique))
 
996
        simple_unique = len(unique)
 
997
 
 
998
        unique_searchers = []
 
999
        for revision_id in unique:
 
1000
            if revision_id in left_searcher.seen:
 
1001
                parent_searcher = left_searcher
 
1002
            else:
 
1003
                parent_searcher = right_searcher
 
1004
            revs_to_search = parent_searcher.find_seen_ancestors([revision_id])
 
1005
            if not revs_to_search: # XXX: This shouldn't be possible
 
1006
                revs_to_search = [revision_id]
 
1007
            searcher = self._make_breadth_first_searcher(revs_to_search)
 
1008
            # We don't care about the starting nodes.
 
1009
            searcher.step()
 
1010
            unique_searchers.append(searcher)
 
1011
 
 
1012
        # possible todo: aggregate the common searchers into a single common
 
1013
        #   searcher, just make sure that we include the nodes into the .seen
 
1014
        #   properties of the original searchers
 
1015
 
 
1016
        ancestor_all_unique = None
 
1017
        for searcher in unique_searchers:
 
1018
            if ancestor_all_unique is None:
 
1019
                ancestor_all_unique = set(searcher.seen)
 
1020
            else:
 
1021
                ancestor_all_unique = ancestor_all_unique.intersection(
 
1022
                                            searcher.seen)
 
1023
 
 
1024
        trace.mutter('Started %s unique searchers for %s unique revisions',
 
1025
                     simple_unique, total_unique)
 
1026
 
 
1027
        while True: # If we have no more nodes we have nothing to do
 
1028
            newly_seen_common = set()
 
1029
            for searcher in common_searchers:
 
1030
                newly_seen_common.update(searcher.step())
 
1031
            newly_seen_unique = set()
 
1032
            for searcher in unique_searchers:
 
1033
                newly_seen_unique.update(searcher.step())
 
1034
            new_common_unique = set()
 
1035
            for revision in newly_seen_unique:
 
1036
                for searcher in unique_searchers:
 
1037
                    if revision not in searcher.seen:
 
1038
                        break
 
1039
                else:
 
1040
                    # This is a border because it is a first common that we see
 
1041
                    # after walking for a while.
 
1042
                    new_common_unique.add(revision)
 
1043
            if newly_seen_common:
 
1044
                # These are nodes descended from one of the 'common' searchers.
 
1045
                # Make sure all searchers are on the same page
 
1046
                for searcher in common_searchers:
 
1047
                    newly_seen_common.update(
 
1048
                        searcher.find_seen_ancestors(newly_seen_common))
 
1049
                # We start searching the whole ancestry. It is a bit wasteful,
 
1050
                # though. We really just want to mark all of these nodes as
 
1051
                # 'seen' and then start just the tips. However, it requires a
 
1052
                # get_parent_map() call to figure out the tips anyway, and all
 
1053
                # redundant requests should be fairly fast.
 
1054
                for searcher in common_searchers:
 
1055
                    searcher.start_searching(newly_seen_common)
 
1056
 
 
1057
                # If a 'common' node is an ancestor of all unique searchers, we
 
1058
                # can stop searching it.
 
1059
                stop_searching_common = ancestor_all_unique.intersection(
 
1060
                                            newly_seen_common)
 
1061
                if stop_searching_common:
 
1062
                    for searcher in common_searchers:
 
1063
                        searcher.stop_searching_any(stop_searching_common)
 
1064
            if new_common_unique:
 
1065
                # We found some ancestors that are common
 
1066
                for searcher in unique_searchers:
 
1067
                    new_common_unique.update(
 
1068
                        searcher.find_seen_ancestors(new_common_unique))
 
1069
                # Since these are common, we can grab another set of ancestors
 
1070
                # that we have seen
 
1071
                for searcher in common_searchers:
 
1072
                    new_common_unique.update(
 
1073
                        searcher.find_seen_ancestors(new_common_unique))
 
1074
 
 
1075
                # We can tell all of the unique searchers to start at these
 
1076
                # nodes, and tell all of the common searchers to *stop*
 
1077
                # searching these nodes
 
1078
                for searcher in unique_searchers:
 
1079
                    searcher.start_searching(new_common_unique)
 
1080
                for searcher in common_searchers:
 
1081
                    searcher.stop_searching_any(new_common_unique)
 
1082
                ancestor_all_unique.update(new_common_unique)
 
1083
 
 
1084
                # Filter out searchers that don't actually search different
 
1085
                # nodes. We already have the ancestry intersection for them
 
1086
                next_unique_searchers = []
 
1087
                unique_search_sets = set()
 
1088
                for searcher in unique_searchers:
 
1089
                    will_search_set = frozenset(searcher._next_query)
 
1090
                    if will_search_set not in unique_search_sets:
 
1091
                        # This searcher is searching a unique set of nodes, let it
 
1092
                        unique_search_sets.add(will_search_set)
 
1093
                        next_unique_searchers.append(searcher)
 
1094
                unique_searchers = next_unique_searchers
 
1095
            for searcher in common_searchers:
 
1096
                if searcher._next_query:
 
1097
                    break
 
1098
            else:
 
1099
                # All common searcher have stopped searching
 
1100
                return
 
1101
 
 
1102
    def _remove_simple_descendants(self, revisions, parent_map):
 
1103
        """remove revisions which are children of other ones in the set
 
1104
 
 
1105
        This doesn't do any graph searching, it just checks the immediate
 
1106
        parent_map to find if there are any children which can be removed.
 
1107
 
 
1108
        :param revisions: A set of revision_ids
 
1109
        :return: A set of revision_ids with the children removed
 
1110
        """
 
1111
        simple_ancestors = revisions.copy()
 
1112
        # TODO: jam 20071214 we *could* restrict it to searching only the
 
1113
        #       parent_map of revisions already present in 'revisions', but
 
1114
        #       considering the general use case, I think this is actually
 
1115
        #       better.
 
1116
 
 
1117
        # This is the same as the following loop. I don't know that it is any
 
1118
        # faster.
 
1119
        ## simple_ancestors.difference_update(r for r, p_ids in parent_map.iteritems()
 
1120
        ##     if p_ids is not None and revisions.intersection(p_ids))
 
1121
        ## return simple_ancestors
 
1122
 
 
1123
        # Yet Another Way, invert the parent map (which can be cached)
 
1124
        ## descendants = {}
 
1125
        ## for revision_id, parent_ids in parent_map.iteritems():
 
1126
        ##   for p_id in parent_ids:
 
1127
        ##       descendants.setdefault(p_id, []).append(revision_id)
 
1128
        ## for revision in revisions.intersection(descendants):
 
1129
        ##   simple_ancestors.difference_update(descendants[revision])
 
1130
        ## return simple_ancestors
 
1131
        for revision, parent_ids in parent_map.iteritems():
 
1132
            if parent_ids is None:
 
1133
                continue
 
1134
            for parent_id in parent_ids:
 
1135
                if parent_id in revisions:
 
1136
                    # This node has a parent present in the set, so we can
 
1137
                    # remove it
 
1138
                    simple_ancestors.discard(revision)
 
1139
                    break
 
1140
        return simple_ancestors
 
1141
 
472
1142
 
473
1143
class HeadsCache(object):
474
1144
    """A cache of results for graph heads calls."""
559
1229
 
560
1230
    def get_result(self):
561
1231
        """Get a SearchResult for the current state of this searcher.
562
 
        
 
1232
 
563
1233
        :return: A SearchResult for this search so far. The SearchResult is
564
1234
            static - the search can be advanced and the search result will not
565
1235
            be invalidated or altered.
569
1239
            # exclude keys for them. However, while we could have a second
570
1240
            # look-ahead result buffer and shuffle things around, this method
571
1241
            # is typically only called once per search - when memoising the
572
 
            # results of the search. 
 
1242
            # results of the search.
573
1243
            found, ghosts, next, parents = self._do_query(self._next_query)
574
1244
            # pretend we didn't query: perhaps we should tweak _do_query to be
575
1245
            # entirely stateless?
582
1252
        return SearchResult(self._started_keys, excludes, len(included_keys),
583
1253
            included_keys)
584
1254
 
 
1255
    def step(self):
 
1256
        try:
 
1257
            return self.next()
 
1258
        except StopIteration:
 
1259
            return ()
 
1260
 
585
1261
    def next(self):
586
1262
        """Return the next ancestors of this revision.
587
1263
 
610
1286
 
611
1287
    def next_with_ghosts(self):
612
1288
        """Return the next found ancestors, with ghosts split out.
613
 
        
 
1289
 
614
1290
        Ancestors are returned in the order they are seen in a breadth-first
615
1291
        traversal.  No ancestor will be returned more than once. Ancestors are
616
1292
        returned only after asking for their parents, which allows us to detect
652
1328
        :return: A tuple: (set(found_revisions), set(ghost_revisions),
653
1329
           set(parents_of_found_revisions), dict(found_revisions:parents)).
654
1330
        """
655
 
        found_parents = set()
 
1331
        found_revisions = set()
656
1332
        parents_of_found = set()
657
1333
        # revisions may contain nodes that point to other nodes in revisions:
658
1334
        # we want to filter them out.
659
1335
        self.seen.update(revisions)
660
1336
        parent_map = self._parents_provider.get_parent_map(revisions)
 
1337
        found_revisions.update(parent_map)
661
1338
        for rev_id, parents in parent_map.iteritems():
662
 
            found_parents.add(rev_id)
663
 
            parents_of_found.update(p for p in parents if p not in self.seen)
664
 
        ghost_parents = revisions - found_parents
665
 
        return found_parents, ghost_parents, parents_of_found, parent_map
 
1339
            if parents is None:
 
1340
                continue
 
1341
            new_found_parents = [p for p in parents if p not in self.seen]
 
1342
            if new_found_parents:
 
1343
                # Calling set.update() with an empty generator is actually
 
1344
                # rather expensive.
 
1345
                parents_of_found.update(new_found_parents)
 
1346
        ghost_revisions = revisions - found_revisions
 
1347
        return found_revisions, ghost_revisions, parents_of_found, parent_map
666
1348
 
667
1349
    def __iter__(self):
668
1350
        return self
669
1351
 
670
 
    def find_seen_ancestors(self, revision):
671
 
        """Find ancestors of this revision that have already been seen."""
672
 
        searcher = _BreadthFirstSearcher([revision], self._parents_provider)
673
 
        seen_ancestors = set()
674
 
        for ancestors in searcher:
675
 
            for ancestor in ancestors:
676
 
                if ancestor not in self.seen:
677
 
                    searcher.stop_searching_any([ancestor])
678
 
                else:
679
 
                    seen_ancestors.add(ancestor)
 
1352
    def find_seen_ancestors(self, revisions):
 
1353
        """Find ancestors of these revisions that have already been seen.
 
1354
 
 
1355
        This function generally makes the assumption that querying for the
 
1356
        parents of a node that has already been queried is reasonably cheap.
 
1357
        (eg, not a round trip to a remote host).
 
1358
        """
 
1359
        # TODO: Often we might ask one searcher for its seen ancestors, and
 
1360
        #       then ask another searcher the same question. This can result in
 
1361
        #       searching the same revisions repeatedly if the two searchers
 
1362
        #       have a lot of overlap.
 
1363
        all_seen = self.seen
 
1364
        pending = set(revisions).intersection(all_seen)
 
1365
        seen_ancestors = set(pending)
 
1366
 
 
1367
        if self._returning == 'next':
 
1368
            # self.seen contains what nodes have been returned, not what nodes
 
1369
            # have been queried. We don't want to probe for nodes that haven't
 
1370
            # been searched yet.
 
1371
            not_searched_yet = self._next_query
 
1372
        else:
 
1373
            not_searched_yet = ()
 
1374
        pending.difference_update(not_searched_yet)
 
1375
        get_parent_map = self._parents_provider.get_parent_map
 
1376
        while pending:
 
1377
            parent_map = get_parent_map(pending)
 
1378
            all_parents = []
 
1379
            # We don't care if it is a ghost, since it can't be seen if it is
 
1380
            # a ghost
 
1381
            for parent_ids in parent_map.itervalues():
 
1382
                all_parents.extend(parent_ids)
 
1383
            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
 
1384
            seen_ancestors.update(next_pending)
 
1385
            next_pending.difference_update(not_searched_yet)
 
1386
            pending = next_pending
 
1387
 
680
1388
        return seen_ancestors
681
1389
 
682
1390
    def stop_searching_any(self, revisions):
684
1392
        Remove any of the specified revisions from the search list.
685
1393
 
686
1394
        None of the specified revisions are required to be present in the
687
 
        search list.  In this case, the call is a no-op.
 
1395
        search list.
 
1396
 
 
1397
        It is okay to call stop_searching_any() for revisions which were seen
 
1398
        in previous iterations. It is the callers responsibility to call
 
1399
        find_seen_ancestors() to make sure that current search tips that are
 
1400
        ancestors of those revisions are also stopped.  All explicitly stopped
 
1401
        revisions will be excluded from the search result's get_keys(), though.
688
1402
        """
 
1403
        # TODO: does this help performance?
 
1404
        # if not revisions:
 
1405
        #     return set()
689
1406
        revisions = frozenset(revisions)
690
1407
        if self._returning == 'next':
691
1408
            stopped = self._next_query.intersection(revisions)
696
1413
                self._current_ghosts.intersection(revisions))
697
1414
            self._current_present.difference_update(stopped)
698
1415
            self._current_ghosts.difference_update(stopped)
699
 
            # stopping 'x' should stop returning parents of 'x', but 
 
1416
            # stopping 'x' should stop returning parents of 'x', but
700
1417
            # not if 'y' always references those same parents
701
1418
            stop_rev_references = {}
702
1419
            for rev in stopped_present:
718
1435
                    stop_parents.add(rev_id)
719
1436
            self._next_query.difference_update(stop_parents)
720
1437
        self._stopped_keys.update(stopped)
 
1438
        self._stopped_keys.update(revisions)
721
1439
        return stopped
722
1440
 
723
1441
    def start_searching(self, revisions):
731
1449
        revisions = frozenset(revisions)
732
1450
        self._started_keys.update(revisions)
733
1451
        new_revisions = revisions.difference(self.seen)
734
 
        revs, ghosts, query, parents = self._do_query(revisions)
735
 
        self._stopped_keys.update(ghosts)
736
1452
        if self._returning == 'next':
737
1453
            self._next_query.update(new_revisions)
 
1454
            self.seen.update(new_revisions)
738
1455
        else:
739
1456
            # perform a query on revisions
 
1457
            revs, ghosts, query, parents = self._do_query(revisions)
 
1458
            self._stopped_keys.update(ghosts)
740
1459
            self._current_present.update(revs)
741
1460
            self._current_ghosts.update(ghosts)
742
1461
            self._next_query.update(query)
762
1481
            a SearchResult from a smart server, in which case the keys list is
763
1482
            not necessarily immediately available.
764
1483
        """
765
 
        self._recipe = (start_keys, exclude_keys, key_count)
 
1484
        self._recipe = ('search', start_keys, exclude_keys, key_count)
766
1485
        self._keys = frozenset(keys)
767
1486
 
768
1487
    def get_recipe(self):
769
1488
        """Return a recipe that can be used to replay this search.
770
 
        
 
1489
 
771
1490
        The recipe allows reconstruction of the same results at a later date
772
1491
        without knowing all the found keys. The essential elements are a list
773
 
        of keys to start and and to stop at. In order to give reproducible
 
1492
        of keys to start and to stop at. In order to give reproducible
774
1493
        results when ghosts are encountered by a search they are automatically
775
1494
        added to the exclude list (or else ghost filling may alter the
776
1495
        results).
777
1496
 
778
 
        :return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
779
 
            recreate the results of this search, create a breadth first
780
 
            searcher on the same graph starting at start_keys. Then call next()
781
 
            (or next_with_ghosts()) repeatedly, and on every result, call
782
 
            stop_searching_any on any keys from the exclude_keys set. The
783
 
            revision_count value acts as a trivial cross-check - the found
784
 
            revisions of the new search should have as many elements as
 
1497
        :return: A tuple ('search', start_keys_set, exclude_keys_set,
 
1498
            revision_count). To recreate the results of this search, create a
 
1499
            breadth first searcher on the same graph starting at start_keys.
 
1500
            Then call next() (or next_with_ghosts()) repeatedly, and on every
 
1501
            result, call stop_searching_any on any keys from the exclude_keys
 
1502
            set. The revision_count value acts as a trivial cross-check - the
 
1503
            found revisions of the new search should have as many elements as
785
1504
            revision_count. If it does not, then additional revisions have been
786
1505
            ghosted since the search was executed the first time and the second
787
1506
            time.
795
1514
        """
796
1515
        return self._keys
797
1516
 
 
1517
    def is_empty(self):
 
1518
        """Return false if the search lists 1 or more revisions."""
 
1519
        return self._recipe[3] == 0
 
1520
 
 
1521
    def refine(self, seen, referenced):
 
1522
        """Create a new search by refining this search.
 
1523
 
 
1524
        :param seen: Revisions that have been satisfied.
 
1525
        :param referenced: Revision references observed while satisfying some
 
1526
            of this search.
 
1527
        """
 
1528
        start = self._recipe[1]
 
1529
        exclude = self._recipe[2]
 
1530
        count = self._recipe[3]
 
1531
        keys = self.get_keys()
 
1532
        # New heads = referenced + old heads - seen things - exclude
 
1533
        pending_refs = set(referenced)
 
1534
        pending_refs.update(start)
 
1535
        pending_refs.difference_update(seen)
 
1536
        pending_refs.difference_update(exclude)
 
1537
        # New exclude = old exclude + satisfied heads
 
1538
        seen_heads = start.intersection(seen)
 
1539
        exclude.update(seen_heads)
 
1540
        # keys gets seen removed
 
1541
        keys = keys - seen
 
1542
        # length is reduced by len(seen)
 
1543
        count -= len(seen)
 
1544
        return SearchResult(pending_refs, exclude, count, keys)
 
1545
 
 
1546
 
 
1547
class PendingAncestryResult(object):
 
1548
    """A search result that will reconstruct the ancestry for some graph heads.
 
1549
 
 
1550
    Unlike SearchResult, this doesn't hold the complete search result in
 
1551
    memory, it just holds a description of how to generate it.
 
1552
    """
 
1553
 
 
1554
    def __init__(self, heads, repo):
 
1555
        """Constructor.
 
1556
 
 
1557
        :param heads: an iterable of graph heads.
 
1558
        :param repo: a repository to use to generate the ancestry for the given
 
1559
            heads.
 
1560
        """
 
1561
        self.heads = frozenset(heads)
 
1562
        self.repo = repo
 
1563
 
 
1564
    def get_recipe(self):
 
1565
        """Return a recipe that can be used to replay this search.
 
1566
 
 
1567
        The recipe allows reconstruction of the same results at a later date.
 
1568
 
 
1569
        :seealso SearchResult.get_recipe:
 
1570
 
 
1571
        :return: A tuple ('proxy-search', start_keys_set, set(), -1)
 
1572
            To recreate this result, create a PendingAncestryResult with the
 
1573
            start_keys_set.
 
1574
        """
 
1575
        return ('proxy-search', self.heads, set(), -1)
 
1576
 
 
1577
    def get_keys(self):
 
1578
        """See SearchResult.get_keys.
 
1579
 
 
1580
        Returns all the keys for the ancestry of the heads, excluding
 
1581
        NULL_REVISION.
 
1582
        """
 
1583
        return self._get_keys(self.repo.get_graph())
 
1584
 
 
1585
    def _get_keys(self, graph):
 
1586
        NULL_REVISION = revision.NULL_REVISION
 
1587
        keys = [key for (key, parents) in graph.iter_ancestry(self.heads)
 
1588
                if key != NULL_REVISION and parents is not None]
 
1589
        return keys
 
1590
 
 
1591
    def is_empty(self):
 
1592
        """Return false if the search lists 1 or more revisions."""
 
1593
        if revision.NULL_REVISION in self.heads:
 
1594
            return len(self.heads) == 1
 
1595
        else:
 
1596
            return len(self.heads) == 0
 
1597
 
 
1598
    def refine(self, seen, referenced):
 
1599
        """Create a new search by refining this search.
 
1600
 
 
1601
        :param seen: Revisions that have been satisfied.
 
1602
        :param referenced: Revision references observed while satisfying some
 
1603
            of this search.
 
1604
        """
 
1605
        referenced = self.heads.union(referenced)
 
1606
        return PendingAncestryResult(referenced - seen, self.repo)
 
1607
 
 
1608
 
 
1609
def collapse_linear_regions(parent_map):
 
1610
    """Collapse regions of the graph that are 'linear'.
 
1611
 
 
1612
    For example::
 
1613
 
 
1614
      A:[B], B:[C]
 
1615
 
 
1616
    can be collapsed by removing B and getting::
 
1617
 
 
1618
      A:[C]
 
1619
 
 
1620
    :param parent_map: A dictionary mapping children to their parents
 
1621
    :return: Another dictionary with 'linear' chains collapsed
 
1622
    """
 
1623
    # Note: this isn't a strictly minimal collapse. For example:
 
1624
    #   A
 
1625
    #  / \
 
1626
    # B   C
 
1627
    #  \ /
 
1628
    #   D
 
1629
    #   |
 
1630
    #   E
 
1631
    # Will not have 'D' removed, even though 'E' could fit. Also:
 
1632
    #   A
 
1633
    #   |    A
 
1634
    #   B => |
 
1635
    #   |    C
 
1636
    #   C
 
1637
    # A and C are both kept because they are edges of the graph. We *could* get
 
1638
    # rid of A if we wanted.
 
1639
    #   A
 
1640
    #  / \
 
1641
    # B   C
 
1642
    # |   |
 
1643
    # D   E
 
1644
    #  \ /
 
1645
    #   F
 
1646
    # Will not have any nodes removed, even though you do have an
 
1647
    # 'uninteresting' linear D->B and E->C
 
1648
    children = {}
 
1649
    for child, parents in parent_map.iteritems():
 
1650
        children.setdefault(child, [])
 
1651
        for p in parents:
 
1652
            children.setdefault(p, []).append(child)
 
1653
 
 
1654
    orig_children = dict(children)
 
1655
    removed = set()
 
1656
    result = dict(parent_map)
 
1657
    for node in parent_map:
 
1658
        parents = result[node]
 
1659
        if len(parents) == 1:
 
1660
            parent_children = children[parents[0]]
 
1661
            if len(parent_children) != 1:
 
1662
                # This is not the only child
 
1663
                continue
 
1664
            node_children = children[node]
 
1665
            if len(node_children) != 1:
 
1666
                continue
 
1667
            child_parents = result.get(node_children[0], None)
 
1668
            if len(child_parents) != 1:
 
1669
                # This is not its only parent
 
1670
                continue
 
1671
            # The child of this node only points at it, and the parent only has
 
1672
            # this as a child. remove this node, and join the others together
 
1673
            result[node_children[0]] = parents
 
1674
            children[parents[0]] = node_children
 
1675
            del result[node]
 
1676
            del children[node]
 
1677
            removed.add(node)
 
1678
 
 
1679
    return result
 
1680
 
 
1681
 
 
1682
class GraphThunkIdsToKeys(object):
 
1683
    """Forwards calls about 'ids' to be about keys internally."""
 
1684
 
 
1685
    def __init__(self, graph):
 
1686
        self._graph = graph
 
1687
 
 
1688
    def heads(self, ids):
 
1689
        """See Graph.heads()"""
 
1690
        as_keys = [(i,) for i in ids]
 
1691
        head_keys = self._graph.heads(as_keys)
 
1692
        return set([h[0] for h in head_keys])
 
1693
 
 
1694
 
 
1695
_counters = [0,0,0,0,0,0,0]
 
1696
try:
 
1697
    from bzrlib._known_graph_pyx import KnownGraph
 
1698
except ImportError, e:
 
1699
    osutils.failed_to_load_extension(e)
 
1700
    from bzrlib._known_graph_py import KnownGraph