← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

Update to bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
 
17
import time
 
18
 
17
19
from bzrlib import (
18
20
    debug,
19
21
    errors,
24
26
    )
25
27
from bzrlib.deprecated_graph import (node_distances, select_farthest)
26
28
 
 
29
STEP_UNIQUE_SEARCHER_EVERY = 5
 
30
 
27
31
# DIAGRAM of terminology
28
32
#       A
29
33
#       /\
208
212
        right = searchers[1].seen
209
213
        return (left.difference(right), right.difference(left))
210
214
 
 
215
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
 
216
        """Find the left-hand distance to the NULL_REVISION.
 
217
 
 
218
        (This can also be considered the revno of a branch at
 
219
        target_revision_id.)
 
220
 
 
221
        :param target_revision_id: A revision_id which we would like to know
 
222
            the revno for.
 
223
        :param known_revision_ids: [(revision_id, revno)] A list of known
 
224
            revno, revision_id tuples. We'll use this to seed the search.
 
225
        """
 
226
        # Map from revision_ids to a known value for their revno
 
227
        known_revnos = dict(known_revision_ids)
 
228
        cur_tip = target_revision_id
 
229
        num_steps = 0
 
230
        NULL_REVISION = revision.NULL_REVISION
 
231
        known_revnos[NULL_REVISION] = 0
 
232
 
 
233
        searching_known_tips = list(known_revnos.keys())
 
234
 
 
235
        unknown_searched = {}
 
236
 
 
237
        while cur_tip not in known_revnos:
 
238
            unknown_searched[cur_tip] = num_steps
 
239
            num_steps += 1
 
240
            to_search = set([cur_tip])
 
241
            to_search.update(searching_known_tips)
 
242
            parent_map = self.get_parent_map(to_search)
 
243
            parents = parent_map.get(cur_tip, None)
 
244
            if not parents: # An empty list or None is a ghost
 
245
                raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
 
246
                                                       cur_tip)
 
247
            cur_tip = parents[0]
 
248
            next_known_tips = []
 
249
            for revision_id in searching_known_tips:
 
250
                parents = parent_map.get(revision_id, None)
 
251
                if not parents:
 
252
                    continue
 
253
                next = parents[0]
 
254
                next_revno = known_revnos[revision_id] - 1
 
255
                if next in unknown_searched:
 
256
                    # We have enough information to return a value right now
 
257
                    return next_revno + unknown_searched[next]
 
258
                if next in known_revnos:
 
259
                    continue
 
260
                known_revnos[next] = next_revno
 
261
                next_known_tips.append(next)
 
262
            searching_known_tips = next_known_tips
 
263
 
 
264
        # We reached a known revision, so just add in how many steps it took to
 
265
        # get there.
 
266
        return known_revnos[cur_tip] + num_steps
 
267
 
211
268
    def find_unique_ancestors(self, unique_revision, common_revisions):
212
269
        """Find the unique ancestors for a revision versus others.
213
270
 
236
293
        #    information you have so far.
237
294
        # 5) Continue searching, stopping the common searches when the search
238
295
        #    tip is an ancestor of all unique nodes.
239
 
        # 6) Search is done when all common searchers have completed.
240
 
 
 
296
        # 6) Aggregate together unique searchers when they are searching the
 
297
        #    same tips. When all unique searchers are searching the same node,
 
298
        #    stop move it to a single 'all_unique_searcher'.
 
299
        # 7) The 'all_unique_searcher' represents the very 'tip' of searching.
 
300
        #    Most of the time this produces very little important information.
 
301
        #    So don't step it as quickly as the other searchers.
 
302
        # 8) Search is done when all common searchers have completed.
 
303
 
 
304
        unique_searcher, common_searcher = self._find_initial_unique_nodes(
 
305
            [unique_revision], common_revisions)
 
306
 
 
307
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
 
308
        if not unique_nodes:
 
309
            return unique_nodes
 
310
 
 
311
        (all_unique_searcher,
 
312
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
 
313
                                    unique_searcher, common_searcher)
 
314
 
 
315
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
 
316
                                  unique_tip_searchers, common_searcher)
 
317
        true_unique_nodes = unique_nodes.difference(common_searcher.seen)
241
318
        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
 
319
            trace.mutter('Found %d truly unique nodes out of %d',
 
320
                         len(true_unique_nodes), len(unique_nodes))
 
321
        return true_unique_nodes
 
322
 
 
323
    def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
 
324
        """Steps 1-3 of find_unique_ancestors.
 
325
 
 
326
        Find the maximal set of unique nodes. Some of these might actually
 
327
        still be common, but we are sure that there are no other unique nodes.
 
328
 
 
329
        :return: (unique_searcher, common_searcher)
 
330
        """
 
331
 
 
332
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
 
333
        # we know that unique_revisions aren't in common_revisions, so skip
 
334
        # past them.
249
335
        unique_searcher.next()
250
336
        common_searcher = self._make_breadth_first_searcher(common_revisions)
251
337
 
 
338
        # As long as we are still finding unique nodes, keep searching
252
339
        while unique_searcher._next_query:
253
340
            next_unique_nodes = set(unique_searcher.step())
254
341
            next_common_nodes = set(common_searcher.step())
262
349
            if unique_are_common_nodes:
263
350
                ancestors = unique_searcher.find_seen_ancestors(
264
351
                                unique_are_common_nodes)
 
352
                # TODO: This is a bit overboard, we only really care about
 
353
                #       the ancestors of the tips because the rest we
 
354
                #       already know. This is *correct* but causes us to
 
355
                #       search too much ancestry.
265
356
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
266
357
                unique_searcher.stop_searching_any(ancestors)
267
358
                common_searcher.start_searching(ancestors)
268
359
 
269
 
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
270
 
        if not unique_nodes:
271
 
            return unique_nodes
 
360
        return unique_searcher, common_searcher
 
361
 
 
362
    def _make_unique_searchers(self, unique_nodes, unique_searcher,
 
363
                               common_searcher):
 
364
        """Create a searcher for all the unique search tips (step 4).
 
365
 
 
366
        As a side effect, the common_searcher will stop searching any nodes
 
367
        that are ancestors of the unique searcher tips.
 
368
 
 
369
        :return: (all_unique_searcher, unique_tip_searchers)
 
370
        """
272
371
        unique_tips = self._remove_simple_descendants(unique_nodes,
273
372
                        self.get_parent_map(unique_nodes))
274
373
 
275
374
        if len(unique_tips) == 1:
276
 
            unique_searchers = []
 
375
            unique_tip_searchers = []
277
376
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
278
377
        else:
279
 
            unique_searchers = []
 
378
            unique_tip_searchers = []
280
379
            for tip in unique_tips:
281
380
                revs_to_search = unique_searcher.find_seen_ancestors([tip])
 
381
                revs_to_search.update(
 
382
                    common_searcher.find_seen_ancestors(revs_to_search))
282
383
                searcher = self._make_breadth_first_searcher(revs_to_search)
283
384
                # We don't care about the starting nodes.
284
385
                searcher._label = tip
285
386
                searcher.step()
286
 
                unique_searchers.append(searcher)
 
387
                unique_tip_searchers.append(searcher)
287
388
 
288
389
            ancestor_all_unique = None
289
 
            for searcher in unique_searchers:
 
390
            for searcher in unique_tip_searchers:
290
391
                if ancestor_all_unique is None:
291
392
                    ancestor_all_unique = set(searcher.seen)
292
393
                else:
293
394
                    ancestor_all_unique = ancestor_all_unique.intersection(
294
395
                                                searcher.seen)
295
396
        # Collapse all the common nodes into a single searcher
296
 
        all_unique_searcher = self._make_breadth_first_searcher(ancestor_all_unique)
 
397
        all_unique_searcher = self._make_breadth_first_searcher(
 
398
                                ancestor_all_unique)
297
399
        if ancestor_all_unique:
 
400
            # We've seen these nodes in all the searchers, so we'll just go to
 
401
            # the next
298
402
            all_unique_searcher.step()
299
403
 
300
404
            # Stop any search tips that are already known as ancestors of the
301
405
            # unique nodes
302
 
            common_searcher.stop_searching_any(
 
406
            stopped_common = common_searcher.stop_searching_any(
303
407
                common_searcher.find_seen_ancestors(ancestor_all_unique))
304
408
 
305
409
            total_stopped = 0
306
 
            for searcher in unique_searchers:
 
410
            for searcher in unique_tip_searchers:
307
411
                total_stopped += len(searcher.stop_searching_any(
308
412
                    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
 
 
 
413
        if 'graph' in debug.debug_flags:
 
414
            trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
 
415
                         ' (%d stopped search tips, %d common ancestors'
 
416
                         ' (%d stopped common)',
 
417
                         len(unique_nodes), len(unique_tip_searchers),
 
418
                         total_stopped, len(ancestor_all_unique),
 
419
                         len(stopped_common))
 
420
        return all_unique_searcher, unique_tip_searchers
 
421
 
 
422
    def _step_unique_and_common_searchers(self, common_searcher,
 
423
                                          unique_tip_searchers,
 
424
                                          unique_searcher):
 
425
        """Step all the searchers"""
 
426
        newly_seen_common = set(common_searcher.step())
 
427
        newly_seen_unique = set()
 
428
        for searcher in unique_tip_searchers:
 
429
            next = set(searcher.step())
 
430
            next.update(unique_searcher.find_seen_ancestors(next))
 
431
            next.update(common_searcher.find_seen_ancestors(next))
 
432
            for alt_searcher in unique_tip_searchers:
 
433
                if alt_searcher is searcher:
 
434
                    continue
 
435
                next.update(alt_searcher.find_seen_ancestors(next))
 
436
            searcher.start_searching(next)
 
437
            newly_seen_unique.update(next)
 
438
        return newly_seen_common, newly_seen_unique
 
439
 
 
440
    def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
 
441
                                         all_unique_searcher,
 
442
                                         newly_seen_unique, step_all_unique):
 
443
        """Find nodes that are common to all unique_tip_searchers.
 
444
 
 
445
        If it is time, step the all_unique_searcher, and add its nodes to the
 
446
        result.
 
447
        """
 
448
        common_to_all_unique_nodes = newly_seen_unique.copy()
 
449
        for searcher in unique_tip_searchers:
 
450
            common_to_all_unique_nodes.intersection_update(searcher.seen)
 
451
        common_to_all_unique_nodes.intersection_update(
 
452
                                    all_unique_searcher.seen)
 
453
        # Step all-unique less frequently than the other searchers.
 
454
        # In the common case, we don't need to spider out far here, so
 
455
        # avoid doing extra work.
 
456
        if step_all_unique:
 
457
            tstart = time.clock()
 
458
            nodes = all_unique_searcher.step()
 
459
            common_to_all_unique_nodes.update(nodes)
 
460
            if 'graph' in debug.debug_flags:
 
461
                tdelta = time.clock() - tstart
 
462
                trace.mutter('all_unique_searcher step() took %.3fs'
 
463
                             'for %d nodes (%d total), iteration: %s',
 
464
                             tdelta, len(nodes), len(all_unique_searcher.seen),
 
465
                             all_unique_searcher._iterations)
 
466
        return common_to_all_unique_nodes
 
467
 
 
468
    def _collapse_unique_searchers(self, unique_tip_searchers,
 
469
                                   common_to_all_unique_nodes):
 
470
        """Combine searchers that are searching the same tips.
 
471
 
 
472
        When two searchers are searching the same tips, we can stop one of the
 
473
        searchers. We also know that the maximal set of common ancestors is the
 
474
        intersection of the two original searchers.
 
475
 
 
476
        :return: A list of searchers that are searching unique nodes.
 
477
        """
 
478
        # Filter out searchers that don't actually search different
 
479
        # nodes. We already have the ancestry intersection for them
 
480
        unique_search_tips = {}
 
481
        for searcher in unique_tip_searchers:
 
482
            stopped = searcher.stop_searching_any(common_to_all_unique_nodes)
 
483
            will_search_set = frozenset(searcher._next_query)
 
484
            if not will_search_set:
 
485
                if 'graph' in debug.debug_flags:
 
486
                    trace.mutter('Unique searcher %s was stopped.'
 
487
                                 ' (%s iterations) %d nodes stopped',
 
488
                                 searcher._label,
 
489
                                 searcher._iterations,
 
490
                                 len(stopped))
 
491
            elif will_search_set not in unique_search_tips:
 
492
                # This searcher is searching a unique set of nodes, let it
 
493
                unique_search_tips[will_search_set] = [searcher]
 
494
            else:
 
495
                unique_search_tips[will_search_set].append(searcher)
 
496
        # TODO: it might be possible to collapse searchers faster when they
 
497
        #       only have *some* search tips in common.
 
498
        next_unique_searchers = []
 
499
        for searchers in unique_search_tips.itervalues():
 
500
            if len(searchers) == 1:
 
501
                # Searching unique tips, go for it
 
502
                next_unique_searchers.append(searchers[0])
 
503
            else:
 
504
                # These searchers have started searching the same tips, we
 
505
                # don't need them to cover the same ground. The
 
506
                # intersection of their ancestry won't change, so create a
 
507
                # new searcher, combining their histories.
 
508
                next_searcher = searchers[0]
 
509
                for searcher in searchers[1:]:
 
510
                    next_searcher.seen.intersection_update(searcher.seen)
 
511
                if 'graph' in debug.debug_flags:
 
512
                    trace.mutter('Combining %d searchers into a single'
 
513
                                 ' searcher searching %d nodes with'
 
514
                                 ' %d ancestry',
 
515
                                 len(searchers),
 
516
                                 len(next_searcher._next_query),
 
517
                                 len(next_searcher.seen))
 
518
                next_unique_searchers.append(next_searcher)
 
519
        return next_unique_searchers
 
520
 
 
521
    def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
 
522
                             unique_tip_searchers, common_searcher):
 
523
        """Steps 5-8 of find_unique_ancestors.
 
524
        
 
525
        This function returns when common_searcher has stopped searching for
 
526
        more nodes.
 
527
        """
 
528
        # We step the ancestor_all_unique searcher only every
 
529
        # STEP_UNIQUE_SEARCHER_EVERY steps.
 
530
        step_all_unique_counter = 0
315
531
        # While we still have common nodes to search
316
532
        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())
 
533
            (newly_seen_common,
 
534
             newly_seen_unique) = self._step_unique_and_common_searchers(
 
535
                common_searcher, unique_tip_searchers, unique_searcher)
321
536
            # 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())
 
537
            common_to_all_unique_nodes = self._find_nodes_common_to_all_unique(
 
538
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
 
539
                step_all_unique_counter==0)
 
540
            step_all_unique_counter = ((step_all_unique_counter + 1)
 
541
                                       % STEP_UNIQUE_SEARCHER_EVERY)
 
542
 
329
543
            if newly_seen_common:
330
544
                # If a 'common' node is an ancestor of all unique searchers, we
331
545
                # can stop searching it.
332
546
                common_searcher.stop_searching_any(
333
547
                    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
 
 
 
548
            if common_to_all_unique_nodes:
 
549
                common_to_all_unique_nodes.update(
 
550
                    common_searcher.find_seen_ancestors(
 
551
                        common_to_all_unique_nodes))
346
552
                # The all_unique searcher can start searching the common nodes
347
553
                # 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)
 
554
                # This is the sort of thing where we would like to not have it
 
555
                # start_searching all of the nodes, but only mark all of them
 
556
                # as seen, and have it search only the actual tips. Otherwise
 
557
                # it is another get_parent_map() traversal for it to figure out
 
558
                # what we already should know.
 
559
                all_unique_searcher.start_searching(common_to_all_unique_nodes)
 
560
                common_searcher.stop_searching_any(common_to_all_unique_nodes)
350
561
 
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)
 
562
            next_unique_searchers = self._collapse_unique_searchers(
 
563
                unique_tip_searchers, common_to_all_unique_nodes)
 
564
            if len(unique_tip_searchers) != len(next_unique_searchers):
 
565
                if 'graph' in debug.debug_flags:
 
566
                    trace.mutter('Collapsed %d unique searchers => %d'
 
567
                                 ' at %s iterations',
 
568
                                 len(unique_tip_searchers),
 
569
                                 len(next_unique_searchers),
 
570
                                 all_unique_searcher._iterations)
 
571
            unique_tip_searchers = next_unique_searchers
379
572
 
380
573
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
381
574
    def get_parents(self, revisions):
1047
1240
        return self
1048
1241
 
1049
1242
    def find_seen_ancestors(self, revisions):
1050
 
        """Find ancestors of these revisions that have already been seen."""
 
1243
        """Find ancestors of these revisions that have already been seen.
 
1244
        
 
1245
        This function generally makes the assumption that querying for the
 
1246
        parents of a node that has already been queried is reasonably cheap.
 
1247
        (eg, not a round trip to a remote host).
 
1248
        """
 
1249
        # TODO: Often we might ask one searcher for its seen ancestors, and
 
1250
        #       then ask another searcher the same question. This can result in
 
1251
        #       searching the same revisions repeatedly if the two searchers
 
1252
        #       have a lot of overlap.
1051
1253
        all_seen = self.seen
1052
1254
        pending = set(revisions).intersection(all_seen)
1053
1255
        seen_ancestors = set(pending)
1082
1284
        None of the specified revisions are required to be present in the
1083
1285
        search list.  In this case, the call is a no-op.
1084
1286
        """
 
1287
        # TODO: does this help performance?
 
1288
        # if not revisions:
 
1289
        #     return set()
1085
1290
        revisions = frozenset(revisions)
1086
1291
        if self._returning == 'next':
1087
1292
            stopped = self._next_query.intersection(revisions)