← 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: 2008-05-09 16:40:21 UTC
  • mto: This revision was merged to the branch mainline in revision 3422.
  • Revision ID: v.ladeuil+lp@free.fr-20080509164021-kxtz21ozxnv16ivt
Fixed as per John's review.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
import time
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
16
 
19
17
from bzrlib import (
20
18
    debug,
21
19
    errors,
22
 
    osutils,
23
20
    revision,
 
21
    symbol_versioning,
24
22
    trace,
 
23
    tsort,
25
24
    )
26
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
 
 
28
 
STEP_UNIQUE_SEARCHER_EVERY = 5
 
25
from bzrlib.deprecated_graph import (node_distances, select_farthest)
29
26
 
30
27
# DIAGRAM of terminology
31
28
#       A
60
57
        return 'DictParentsProvider(%r)' % self.ancestry
61
58
 
62
59
    def get_parent_map(self, keys):
63
 
        """See StackedParentsProvider.get_parent_map"""
 
60
        """See _StackedParentsProvider.get_parent_map"""
64
61
        ancestry = self.ancestry
65
62
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
63
 
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
 
    
 
64
 
 
65
class _StackedParentsProvider(object):
 
66
 
77
67
    def __init__(self, parent_providers):
78
68
        self._parent_providers = parent_providers
79
69
 
80
70
    def __repr__(self):
81
 
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
 
71
        return "_StackedParentsProvider(%r)" % self._parent_providers
82
72
 
83
73
    def get_parent_map(self, keys):
84
74
        """Get a mapping of keys => parents
105
95
 
106
96
 
107
97
class CachingParentsProvider(object):
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.
 
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.
117
101
    """
118
 
    def __init__(self, parent_provider=None, get_parent_map=None):
119
 
        """Constructor.
120
102
 
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
 
        """
 
103
    def __init__(self, parent_provider):
126
104
        self._real_provider = parent_provider
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)
 
105
        # Theoretically we could use an LRUCache here
 
106
        self._cache = {}
133
107
 
134
108
    def __repr__(self):
135
109
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
136
110
 
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.')
141
 
        self._cache = {}
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)
156
 
 
157
111
    def get_parent_map(self, keys):
158
 
        """See StackedParentsProvider.get_parent_map."""
 
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 = {}
159
118
        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 = {}
174
119
        for key in keys:
175
 
            value = cache.get(key)
176
 
            if value is not None:
177
 
                result[key] = value
178
 
        return result
 
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)
179
126
 
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)
 
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
184
134
 
185
135
 
186
136
class Graph(object):
258
208
        right = searchers[1].seen
259
209
        return (left.difference(right), right.difference(left))
260
210
 
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
211
    def find_unique_ancestors(self, unique_revision, common_revisions):
336
212
        """Find the unique ancestors for a revision versus others.
337
213
 
360
236
        #    information you have so far.
361
237
        # 5) Continue searching, stopping the common searches when the search
362
238
        #    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)
 
239
        # 6) Search is done when all common searchers have completed.
 
240
 
385
241
        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.
 
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
402
249
        unique_searcher.next()
403
250
        common_searcher = self._make_breadth_first_searcher(common_revisions)
404
251
 
405
 
        # As long as we are still finding unique nodes, keep searching
406
252
        while unique_searcher._next_query:
407
253
            next_unique_nodes = set(unique_searcher.step())
408
254
            next_common_nodes = set(common_searcher.step())
416
262
            if unique_are_common_nodes:
417
263
                ancestors = unique_searcher.find_seen_ancestors(
418
264
                                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
265
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
424
266
                unique_searcher.stop_searching_any(ancestors)
425
267
                common_searcher.start_searching(ancestors)
426
268
 
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
 
        """
 
269
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
 
270
        if not unique_nodes:
 
271
            return unique_nodes
438
272
        unique_tips = self._remove_simple_descendants(unique_nodes,
439
273
                        self.get_parent_map(unique_nodes))
440
274
 
441
275
        if len(unique_tips) == 1:
442
 
            unique_tip_searchers = []
 
276
            unique_searchers = []
443
277
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
444
278
        else:
445
 
            unique_tip_searchers = []
 
279
            unique_searchers = []
446
280
            for tip in unique_tips:
447
281
                revs_to_search = unique_searcher.find_seen_ancestors([tip])
448
 
                revs_to_search.update(
449
 
                    common_searcher.find_seen_ancestors(revs_to_search))
450
282
                searcher = self._make_breadth_first_searcher(revs_to_search)
451
283
                # We don't care about the starting nodes.
452
284
                searcher._label = tip
453
285
                searcher.step()
454
 
                unique_tip_searchers.append(searcher)
 
286
                unique_searchers.append(searcher)
455
287
 
456
288
            ancestor_all_unique = None
457
 
            for searcher in unique_tip_searchers:
 
289
            for searcher in unique_searchers:
458
290
                if ancestor_all_unique is None:
459
291
                    ancestor_all_unique = set(searcher.seen)
460
292
                else:
461
293
                    ancestor_all_unique = ancestor_all_unique.intersection(
462
294
                                                searcher.seen)
463
295
        # Collapse all the common nodes into a single searcher
464
 
        all_unique_searcher = self._make_breadth_first_searcher(
465
 
                                ancestor_all_unique)
 
296
        all_unique_searcher = self._make_breadth_first_searcher(ancestor_all_unique)
466
297
        if ancestor_all_unique:
467
 
            # We've seen these nodes in all the searchers, so we'll just go to
468
 
            # the next
469
298
            all_unique_searcher.step()
470
299
 
471
300
            # Stop any search tips that are already known as ancestors of the
472
301
            # unique nodes
473
 
            stopped_common = common_searcher.stop_searching_any(
 
302
            common_searcher.stop_searching_any(
474
303
                common_searcher.find_seen_ancestors(ancestor_all_unique))
475
304
 
476
305
            total_stopped = 0
477
 
            for searcher in unique_tip_searchers:
 
306
            for searcher in unique_searchers:
478
307
                total_stopped += len(searcher.stop_searching_any(
479
308
                    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
 
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
 
598
315
        # While we still have common nodes to search
599
316
        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)
 
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())
603
321
            # 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
 
 
 
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())
610
329
            if newly_seen_common:
611
330
                # If a 'common' node is an ancestor of all unique searchers, we
612
331
                # can stop searching it.
613
332
                common_searcher.stop_searching_any(
614
333
                    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))
 
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
 
619
346
                # The all_unique searcher can start searching the common nodes
620
347
                # 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
 
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]
639
397
 
640
398
    def get_parent_map(self, revisions):
641
399
        """Get a map of key:parent_list for revisions.
815
573
            common_walker.start_searching(new_common)
816
574
        return candidate_heads
817
575
 
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
 
 
865
576
    def find_unique_lca(self, left_revision, right_revision,
866
577
                        count_steps=False):
867
578
        """Find a unique LCA.
926
637
        An ancestor may sort after a descendant if the relationship is not
927
638
        visible in the supplied list of revisions.
928
639
        """
929
 
        from bzrlib import tsort
930
640
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
641
        return sorter.iter_topo_order()
932
642
 
940
650
        return set([candidate_descendant]) == self.heads(
941
651
            [candidate_ancestor, candidate_descendant])
942
652
 
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
653
    def _search_for_extra_common(self, common, searchers):
955
654
        """Make sure that unique nodes are genuinely unique.
956
655
 
1229
928
 
1230
929
    def get_result(self):
1231
930
        """Get a SearchResult for the current state of this searcher.
1232
 
 
 
931
        
1233
932
        :return: A SearchResult for this search so far. The SearchResult is
1234
933
            static - the search can be advanced and the search result will not
1235
934
            be invalidated or altered.
1239
938
            # exclude keys for them. However, while we could have a second
1240
939
            # look-ahead result buffer and shuffle things around, this method
1241
940
            # is typically only called once per search - when memoising the
1242
 
            # results of the search.
 
941
            # results of the search. 
1243
942
            found, ghosts, next, parents = self._do_query(self._next_query)
1244
943
            # pretend we didn't query: perhaps we should tweak _do_query to be
1245
944
            # entirely stateless?
1286
985
 
1287
986
    def next_with_ghosts(self):
1288
987
        """Return the next found ancestors, with ghosts split out.
1289
 
 
 
988
        
1290
989
        Ancestors are returned in the order they are seen in a breadth-first
1291
990
        traversal.  No ancestor will be returned more than once. Ancestors are
1292
991
        returned only after asking for their parents, which allows us to detect
1336
1035
        parent_map = self._parents_provider.get_parent_map(revisions)
1337
1036
        found_revisions.update(parent_map)
1338
1037
        for rev_id, parents in parent_map.iteritems():
1339
 
            if parents is None:
1340
 
                continue
1341
1038
            new_found_parents = [p for p in parents if p not in self.seen]
1342
1039
            if new_found_parents:
1343
1040
                # Calling set.update() with an empty generator is actually
1350
1047
        return self
1351
1048
 
1352
1049
    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.
 
1050
        """Find ancestors of these revisions that have already been seen."""
1363
1051
        all_seen = self.seen
1364
1052
        pending = set(revisions).intersection(all_seen)
1365
1053
        seen_ancestors = set(pending)
1392
1080
        Remove any of the specified revisions from the search list.
1393
1081
 
1394
1082
        None of the specified revisions are required to be present in the
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.
 
1083
        search list.  In this case, the call is a no-op.
1402
1084
        """
1403
 
        # TODO: does this help performance?
1404
 
        # if not revisions:
1405
 
        #     return set()
1406
1085
        revisions = frozenset(revisions)
1407
1086
        if self._returning == 'next':
1408
1087
            stopped = self._next_query.intersection(revisions)
1413
1092
                self._current_ghosts.intersection(revisions))
1414
1093
            self._current_present.difference_update(stopped)
1415
1094
            self._current_ghosts.difference_update(stopped)
1416
 
            # stopping 'x' should stop returning parents of 'x', but
 
1095
            # stopping 'x' should stop returning parents of 'x', but 
1417
1096
            # not if 'y' always references those same parents
1418
1097
            stop_rev_references = {}
1419
1098
            for rev in stopped_present:
1435
1114
                    stop_parents.add(rev_id)
1436
1115
            self._next_query.difference_update(stop_parents)
1437
1116
        self._stopped_keys.update(stopped)
1438
 
        self._stopped_keys.update(revisions)
1439
1117
        return stopped
1440
1118
 
1441
1119
    def start_searching(self, revisions):
1481
1159
            a SearchResult from a smart server, in which case the keys list is
1482
1160
            not necessarily immediately available.
1483
1161
        """
1484
 
        self._recipe = ('search', start_keys, exclude_keys, key_count)
 
1162
        self._recipe = (start_keys, exclude_keys, key_count)
1485
1163
        self._keys = frozenset(keys)
1486
1164
 
1487
1165
    def get_recipe(self):
1488
1166
        """Return a recipe that can be used to replay this search.
1489
 
 
 
1167
        
1490
1168
        The recipe allows reconstruction of the same results at a later date
1491
1169
        without knowing all the found keys. The essential elements are a list
1492
 
        of keys to start and to stop at. In order to give reproducible
 
1170
        of keys to start and and to stop at. In order to give reproducible
1493
1171
        results when ghosts are encountered by a search they are automatically
1494
1172
        added to the exclude list (or else ghost filling may alter the
1495
1173
        results).
1496
1174
 
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
 
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
1504
1182
            revision_count. If it does not, then additional revisions have been
1505
1183
            ghosted since the search was executed the first time and the second
1506
1184
            time.
1514
1192
        """
1515
1193
        return self._keys
1516
1194
 
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 topo_sort(self):
1689
 
        return [r for (r,) in self._graph.topo_sort()]
1690
 
 
1691
 
    def heads(self, ids):
1692
 
        """See Graph.heads()"""
1693
 
        as_keys = [(i,) for i in ids]
1694
 
        head_keys = self._graph.heads(as_keys)
1695
 
        return set([h[0] for h in head_keys])
1696
 
 
1697
 
    def merge_sort(self, tip_revision):
1698
 
        return self._graph.merge_sort((tip_revision,))
1699
 
 
1700
 
 
1701
 
_counters = [0,0,0,0,0,0,0]
1702
 
try:
1703
 
    from bzrlib._known_graph_pyx import KnownGraph
1704
 
except ImportError, e:
1705
 
    osutils.failed_to_load_extension(e)
1706
 
    from bzrlib._known_graph_py import KnownGraph