← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Robert Collins
  • Date: 2010-04-08 04:34:03 UTC
  • mfrom: (5138 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5139.
  • Revision ID: robertc@robertcollins.net-20100408043403-56z0d07vdqrx7f3t
Update bugfix for 528114 to trunk.

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 (
18
20
    debug,
19
21
    errors,
 
22
    osutils,
20
23
    revision,
21
 
    symbol_versioning,
22
24
    trace,
23
 
    tsort,
24
25
    )
25
 
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
26
29
 
27
30
# DIAGRAM of terminology
28
31
#       A
57
60
        return 'DictParentsProvider(%r)' % self.ancestry
58
61
 
59
62
    def get_parent_map(self, keys):
60
 
        """See _StackedParentsProvider.get_parent_map"""
 
63
        """See StackedParentsProvider.get_parent_map"""
61
64
        ancestry = self.ancestry
62
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
63
66
 
64
 
 
65
 
class _StackedParentsProvider(object):
66
 
 
 
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
    
67
77
    def __init__(self, parent_providers):
68
78
        self._parent_providers = parent_providers
69
79
 
70
80
    def __repr__(self):
71
 
        return "_StackedParentsProvider(%r)" % self._parent_providers
 
81
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
72
82
 
73
83
    def get_parent_map(self, keys):
74
84
        """Get a mapping of keys => parents
95
105
 
96
106
 
97
107
class CachingParentsProvider(object):
98
 
    """A parents provider which will cache the revision => parents in a dict.
99
 
 
100
 
    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.
101
117
    """
 
118
    def __init__(self, parent_provider=None, get_parent_map=None):
 
119
        """Constructor.
102
120
 
103
 
    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
        """
104
126
        self._real_provider = parent_provider
105
 
        # 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.')
106
141
        self._cache = {}
107
 
 
108
 
    def __repr__(self):
109
 
        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)
110
156
 
111
157
    def get_parent_map(self, keys):
112
 
        """See _StackedParentsProvider.get_parent_map"""
113
 
        needed = set()
114
 
        # If the _real_provider doesn't have a key, we cache a value of None,
115
 
        # which we then later use to realize we cannot provide a value for that
116
 
        # key.
117
 
        parent_map = {}
 
158
        """See StackedParentsProvider.get_parent_map."""
118
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 = {}
119
174
        for key in keys:
120
 
            if key in cache:
121
 
                value = cache[key]
122
 
                if value is not None:
123
 
                    parent_map[key] = value
124
 
            else:
125
 
                needed.add(key)
 
175
            value = cache.get(key)
 
176
            if value is not None:
 
177
                result[key] = value
 
178
        return result
126
179
 
127
 
        if needed:
128
 
            new_parents = self._real_provider.get_parent_map(needed)
129
 
            cache.update(new_parents)
130
 
            parent_map.update(new_parents)
131
 
            needed.difference_update(new_parents)
132
 
            cache.update(dict.fromkeys(needed, None))
133
 
        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)
134
184
 
135
185
 
136
186
class Graph(object):
208
258
        right = searchers[1].seen
209
259
        return (left.difference(right), right.difference(left))
210
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
 
211
335
    def find_unique_ancestors(self, unique_revision, common_revisions):
212
336
        """Find the unique ancestors for a revision versus others.
213
337
 
236
360
        #    information you have so far.
237
361
        # 5) Continue searching, stopping the common searches when the search
238
362
        #    tip is an ancestor of all unique nodes.
239
 
        # 6) Search is done when all common searchers have completed.
240
 
 
 
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)
241
385
        if 'graph' in debug.debug_flags:
242
 
            _mutter = trace.mutter
243
 
        else:
244
 
            def _mutter(*args, **kwargs):
245
 
                pass
246
 
 
247
 
        unique_searcher = self._make_breadth_first_searcher([unique_revision])
248
 
        # we know that unique_revision isn't in common_revisions
 
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.
249
402
        unique_searcher.next()
250
403
        common_searcher = self._make_breadth_first_searcher(common_revisions)
251
404
 
 
405
        # As long as we are still finding unique nodes, keep searching
252
406
        while unique_searcher._next_query:
253
407
            next_unique_nodes = set(unique_searcher.step())
254
408
            next_common_nodes = set(common_searcher.step())
262
416
            if unique_are_common_nodes:
263
417
                ancestors = unique_searcher.find_seen_ancestors(
264
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.
265
423
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
266
424
                unique_searcher.stop_searching_any(ancestors)
267
425
                common_searcher.start_searching(ancestors)
268
426
 
269
 
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
270
 
        if not unique_nodes:
271
 
            return unique_nodes
 
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
        """
272
438
        unique_tips = self._remove_simple_descendants(unique_nodes,
273
439
                        self.get_parent_map(unique_nodes))
274
440
 
275
441
        if len(unique_tips) == 1:
276
 
            unique_searchers = []
 
442
            unique_tip_searchers = []
277
443
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
278
444
        else:
279
 
            unique_searchers = []
 
445
            unique_tip_searchers = []
280
446
            for tip in unique_tips:
281
447
                revs_to_search = unique_searcher.find_seen_ancestors([tip])
 
448
                revs_to_search.update(
 
449
                    common_searcher.find_seen_ancestors(revs_to_search))
282
450
                searcher = self._make_breadth_first_searcher(revs_to_search)
283
451
                # We don't care about the starting nodes.
284
452
                searcher._label = tip
285
453
                searcher.step()
286
 
                unique_searchers.append(searcher)
 
454
                unique_tip_searchers.append(searcher)
287
455
 
288
456
            ancestor_all_unique = None
289
 
            for searcher in unique_searchers:
 
457
            for searcher in unique_tip_searchers:
290
458
                if ancestor_all_unique is None:
291
459
                    ancestor_all_unique = set(searcher.seen)
292
460
                else:
293
461
                    ancestor_all_unique = ancestor_all_unique.intersection(
294
462
                                                searcher.seen)
295
463
        # Collapse all the common nodes into a single searcher
296
 
        all_unique_searcher = self._make_breadth_first_searcher(ancestor_all_unique)
 
464
        all_unique_searcher = self._make_breadth_first_searcher(
 
465
                                ancestor_all_unique)
297
466
        if ancestor_all_unique:
 
467
            # We've seen these nodes in all the searchers, so we'll just go to
 
468
            # the next
298
469
            all_unique_searcher.step()
299
470
 
300
471
            # Stop any search tips that are already known as ancestors of the
301
472
            # unique nodes
302
 
            common_searcher.stop_searching_any(
 
473
            stopped_common = common_searcher.stop_searching_any(
303
474
                common_searcher.find_seen_ancestors(ancestor_all_unique))
304
475
 
305
476
            total_stopped = 0
306
 
            for searcher in unique_searchers:
 
477
            for searcher in unique_tip_searchers:
307
478
                total_stopped += len(searcher.stop_searching_any(
308
479
                    searcher.find_seen_ancestors(ancestor_all_unique)))
309
 
            _mutter('For %s unique nodes, created %s + 1 unique searchers'
310
 
                    ' (%s stopped search tips, %s common ancestors)',
311
 
                    len(unique_nodes), len(unique_searchers), total_stopped,
312
 
                    len(ancestor_all_unique))
313
 
            del ancestor_all_unique
314
 
 
 
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
315
598
        # While we still have common nodes to search
316
599
        while common_searcher._next_query:
317
 
            newly_seen_common = set(common_searcher.step())
318
 
            newly_seen_unique = set()
319
 
            for searcher in unique_searchers:
320
 
                newly_seen_unique.update(searcher.step())
 
600
            (newly_seen_common,
 
601
             newly_seen_unique) = self._step_unique_and_common_searchers(
 
602
                common_searcher, unique_tip_searchers, unique_searcher)
321
603
            # These nodes are common ancestors of all unique nodes
322
 
            unique_are_common_nodes = newly_seen_unique.copy()
323
 
            for searcher in unique_searchers:
324
 
                unique_are_common_nodes = unique_are_common_nodes.intersection(
325
 
                                            searcher.seen)
326
 
            unique_are_common_nodes = unique_are_common_nodes.intersection(
327
 
                                        all_unique_searcher.seen)
328
 
            unique_are_common_nodes.update(all_unique_searcher.step())
 
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
 
329
610
            if newly_seen_common:
330
611
                # If a 'common' node is an ancestor of all unique searchers, we
331
612
                # can stop searching it.
332
613
                common_searcher.stop_searching_any(
333
614
                    all_unique_searcher.seen.intersection(newly_seen_common))
334
 
            if unique_are_common_nodes:
335
 
                # We have new common-to-all-unique-searchers nodes
336
 
                for searcher in unique_searchers:
337
 
                    unique_are_common_nodes.update(
338
 
                        searcher.find_seen_ancestors(unique_are_common_nodes))
339
 
                unique_are_common_nodes.update(
340
 
                    all_unique_searcher.find_seen_ancestors(unique_are_common_nodes))
341
 
                # Since these are common, we can grab another set of ancestors
342
 
                # that we have seen
343
 
                unique_are_common_nodes.update(
344
 
                    common_searcher.find_seen_ancestors(unique_are_common_nodes))
345
 
 
 
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))
346
619
                # The all_unique searcher can start searching the common nodes
347
620
                # but everyone else can stop.
348
 
                all_unique_searcher.start_searching(unique_are_common_nodes)
349
 
                common_searcher.stop_searching_any(unique_are_common_nodes)
350
 
 
351
 
                # Filter out searchers that don't actually search different
352
 
                # nodes. We already have the ancestry intersection for them
353
 
                next_unique_searchers = []
354
 
                unique_search_sets = set()
355
 
                for searcher in unique_searchers:
356
 
                    stopped = searcher.stop_searching_any(unique_are_common_nodes)
357
 
                    will_search_set = frozenset(searcher._next_query)
358
 
                    if not will_search_set:
359
 
                        _mutter('Unique searcher %s was stopped.'
360
 
                                ' (%s iterations) %d nodes stopped',
361
 
                                searcher._label,
362
 
                                searcher._iterations,
363
 
                                len(stopped))
364
 
                    elif will_search_set not in unique_search_sets:
365
 
                        # This searcher is searching a unique set of nodes, let it
366
 
                        unique_search_sets.add(will_search_set)
367
 
                        next_unique_searchers.append(searcher)
368
 
                    else:
369
 
                        _mutter('Unique searcher %s stopped for repeated'
370
 
                                ' search of %s nodes', 
371
 
                                searcher._label, len(will_search_set))
372
 
                if len(unique_searchers) != len(next_unique_searchers):
373
 
                    _mutter('Collapsed %s unique searchers => %s'
374
 
                            ' at %s iterations',
375
 
                            len(unique_searchers), len(next_unique_searchers),
376
 
                            all_unique_searcher._iterations)
377
 
                unique_searchers = next_unique_searchers
378
 
        return unique_nodes.difference(common_searcher.seen)
379
 
 
380
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
381
 
    def get_parents(self, revisions):
382
 
        """Find revision ids of the parents of a list of revisions
383
 
 
384
 
        A list is returned of the same length as the input.  Each entry
385
 
        is a list of parent ids for the corresponding input revision.
386
 
 
387
 
        [NULL_REVISION] is used as the parent of the first user-committed
388
 
        revision.  Its parent list is empty.
389
 
 
390
 
        If the revision is not present (i.e. a ghost), None is used in place
391
 
        of the list of parents.
392
 
 
393
 
        Deprecated in bzr 1.2 - please see get_parent_map.
394
 
        """
395
 
        parents = self.get_parent_map(revisions)
396
 
        return [parents.get(r, None) for r in revisions]
 
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
397
639
 
398
640
    def get_parent_map(self, revisions):
399
641
        """Get a map of key:parent_list for revisions.
573
815
            common_walker.start_searching(new_common)
574
816
        return candidate_heads
575
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
 
576
865
    def find_unique_lca(self, left_revision, right_revision,
577
866
                        count_steps=False):
578
867
        """Find a unique LCA.
637
926
        An ancestor may sort after a descendant if the relationship is not
638
927
        visible in the supplied list of revisions.
639
928
        """
 
929
        from bzrlib import tsort
640
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
641
931
        return sorter.iter_topo_order()
642
932
 
650
940
        return set([candidate_descendant]) == self.heads(
651
941
            [candidate_ancestor, candidate_descendant])
652
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
 
653
954
    def _search_for_extra_common(self, common, searchers):
654
955
        """Make sure that unique nodes are genuinely unique.
655
956
 
928
1229
 
929
1230
    def get_result(self):
930
1231
        """Get a SearchResult for the current state of this searcher.
931
 
        
 
1232
 
932
1233
        :return: A SearchResult for this search so far. The SearchResult is
933
1234
            static - the search can be advanced and the search result will not
934
1235
            be invalidated or altered.
938
1239
            # exclude keys for them. However, while we could have a second
939
1240
            # look-ahead result buffer and shuffle things around, this method
940
1241
            # is typically only called once per search - when memoising the
941
 
            # results of the search. 
 
1242
            # results of the search.
942
1243
            found, ghosts, next, parents = self._do_query(self._next_query)
943
1244
            # pretend we didn't query: perhaps we should tweak _do_query to be
944
1245
            # entirely stateless?
985
1286
 
986
1287
    def next_with_ghosts(self):
987
1288
        """Return the next found ancestors, with ghosts split out.
988
 
        
 
1289
 
989
1290
        Ancestors are returned in the order they are seen in a breadth-first
990
1291
        traversal.  No ancestor will be returned more than once. Ancestors are
991
1292
        returned only after asking for their parents, which allows us to detect
1035
1336
        parent_map = self._parents_provider.get_parent_map(revisions)
1036
1337
        found_revisions.update(parent_map)
1037
1338
        for rev_id, parents in parent_map.iteritems():
 
1339
            if parents is None:
 
1340
                continue
1038
1341
            new_found_parents = [p for p in parents if p not in self.seen]
1039
1342
            if new_found_parents:
1040
1343
                # Calling set.update() with an empty generator is actually
1047
1350
        return self
1048
1351
 
1049
1352
    def find_seen_ancestors(self, revisions):
1050
 
        """Find ancestors of these revisions that have already been seen."""
 
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.
1051
1363
        all_seen = self.seen
1052
1364
        pending = set(revisions).intersection(all_seen)
1053
1365
        seen_ancestors = set(pending)
1080
1392
        Remove any of the specified revisions from the search list.
1081
1393
 
1082
1394
        None of the specified revisions are required to be present in the
1083
 
        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.
1084
1402
        """
 
1403
        # TODO: does this help performance?
 
1404
        # if not revisions:
 
1405
        #     return set()
1085
1406
        revisions = frozenset(revisions)
1086
1407
        if self._returning == 'next':
1087
1408
            stopped = self._next_query.intersection(revisions)
1092
1413
                self._current_ghosts.intersection(revisions))
1093
1414
            self._current_present.difference_update(stopped)
1094
1415
            self._current_ghosts.difference_update(stopped)
1095
 
            # stopping 'x' should stop returning parents of 'x', but 
 
1416
            # stopping 'x' should stop returning parents of 'x', but
1096
1417
            # not if 'y' always references those same parents
1097
1418
            stop_rev_references = {}
1098
1419
            for rev in stopped_present:
1114
1435
                    stop_parents.add(rev_id)
1115
1436
            self._next_query.difference_update(stop_parents)
1116
1437
        self._stopped_keys.update(stopped)
 
1438
        self._stopped_keys.update(revisions)
1117
1439
        return stopped
1118
1440
 
1119
1441
    def start_searching(self, revisions):
1159
1481
            a SearchResult from a smart server, in which case the keys list is
1160
1482
            not necessarily immediately available.
1161
1483
        """
1162
 
        self._recipe = (start_keys, exclude_keys, key_count)
 
1484
        self._recipe = ('search', start_keys, exclude_keys, key_count)
1163
1485
        self._keys = frozenset(keys)
1164
1486
 
1165
1487
    def get_recipe(self):
1166
1488
        """Return a recipe that can be used to replay this search.
1167
 
        
 
1489
 
1168
1490
        The recipe allows reconstruction of the same results at a later date
1169
1491
        without knowing all the found keys. The essential elements are a list
1170
 
        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
1171
1493
        results when ghosts are encountered by a search they are automatically
1172
1494
        added to the exclude list (or else ghost filling may alter the
1173
1495
        results).
1174
1496
 
1175
 
        :return: A tuple (start_keys_set, exclude_keys_set, revision_count). To
1176
 
            recreate the results of this search, create a breadth first
1177
 
            searcher on the same graph starting at start_keys. Then call next()
1178
 
            (or next_with_ghosts()) repeatedly, and on every result, call
1179
 
            stop_searching_any on any keys from the exclude_keys set. The
1180
 
            revision_count value acts as a trivial cross-check - the found
1181
 
            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
1182
1504
            revision_count. If it does not, then additional revisions have been
1183
1505
            ghosted since the search was executed the first time and the second
1184
1506
            time.
1192
1514
        """
1193
1515
        return self._keys
1194
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