/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2008-05-20 23:10:20 UTC
  • mto: This revision was merged to the branch mainline in revision 3443.
  • Revision ID: john@arbash-meinel.com-20080520231020-wh8g3pq0whu2p78i
Lots of refactoring for find_unique_ancestors.

Split up the function into a bunch of helper functions.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
240
240
        #    information you have so far.
241
241
        # 5) Continue searching, stopping the common searches when the search
242
242
        #    tip is an ancestor of all unique nodes.
243
 
        # 6) Search is done when all common searchers have completed.
244
 
 
 
243
        # 6) Aggregate together unique searchers when they are searching the
 
244
        #    same tips. When all unique searchers are searching the same node,
 
245
        #    stop move it to a single 'all_unique_searcher'.
 
246
        # 7) The 'all_unique_searcher' represents the very 'tip' of searching.
 
247
        #    Most of the time this produces very little important information.
 
248
        #    So don't step it as quickly as the other searchers.
 
249
        # 8) Search is done when all common searchers have completed.
 
250
 
 
251
        unique_searcher, common_searcher = self._find_initial_unique_nodes(
 
252
            [unique_revision], common_revisions)
 
253
 
 
254
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
 
255
        if not unique_nodes:
 
256
            return unique_nodes
 
257
 
 
258
        (all_unique_searcher,
 
259
         unique_tip_searchers) = self._make_unique_searchers(unique_nodes,
 
260
                                    unique_searcher, common_searcher)
 
261
 
 
262
        self._refine_unique_nodes(unique_searcher, all_unique_searcher,
 
263
                                  unique_tip_searchers, common_searcher)
 
264
        true_unique_nodes = unique_nodes.difference(common_searcher.seen)
245
265
        if 'graph' in debug.debug_flags:
246
 
            _mutter = trace.mutter
247
 
        else:
248
 
            def _mutter(*args, **kwargs):
249
 
                pass
250
 
 
251
 
        unique_searcher = self._make_breadth_first_searcher([unique_revision])
252
 
        # we know that unique_revision isn't in common_revisions
 
266
            trace.mutter('Found %s truly unique nodes out of %s',
 
267
                         len(true_unique_nodes), len(unique_nodes))
 
268
        return true_unique_nodes
 
269
 
 
270
    def _find_initial_unique_nodes(self, unique_revisions, common_revisions):
 
271
        """Steps 1-3 of find_unique_ancestors.
 
272
 
 
273
        Find the maximal set of unique nodes. Some of these might actually
 
274
        still be common, but we are sure that there are no other unique nodes.
 
275
 
 
276
        :return: (unique_searcher, common_searcher)
 
277
        """
 
278
 
 
279
        unique_searcher = self._make_breadth_first_searcher(unique_revisions)
 
280
        # we know that unique_revisions aren't in common_revisions, so skip
 
281
        # past them.
253
282
        unique_searcher.next()
254
283
        common_searcher = self._make_breadth_first_searcher(common_revisions)
255
284
 
 
285
        # As long as we are still finding unique nodes, keep searching
256
286
        while unique_searcher._next_query:
257
287
            next_unique_nodes = set(unique_searcher.step())
258
288
            next_common_nodes = set(common_searcher.step())
264
294
            unique_are_common_nodes.update(
265
295
                next_common_nodes.intersection(unique_searcher.seen))
266
296
            if unique_are_common_nodes:
 
297
                ancestors = unique_searcher.find_seen_ancestors(
 
298
                                unique_are_common_nodes)
267
299
                # TODO: This is a bit overboard, we only really care about
268
300
                #       the ancestors of the tips because the rest we
269
301
                #       already know. This is *correct* but causes us to
270
 
                #       search far too much ancestry.
271
 
                ancestors = unique_searcher.find_seen_ancestors(
272
 
                                unique_are_common_nodes)
 
302
                #       search too much ancestry.
273
303
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
274
304
                unique_searcher.stop_searching_any(ancestors)
275
305
                common_searcher.start_searching(ancestors)
276
306
 
277
 
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
278
 
        if not unique_nodes:
279
 
            return unique_nodes
 
307
        return unique_searcher, common_searcher
 
308
 
 
309
 
 
310
    def _make_unique_searchers(self, unique_nodes, unique_searcher,
 
311
                               common_searcher):
 
312
        """Create a searcher for all the unique search tips (step 4).
 
313
 
 
314
        As a side effect, the common_searcher will stop searching any nodes
 
315
        that are ancestors of the unique searcher tips.
 
316
 
 
317
        :return: (all_unique_searcher, unique_tip_searchers)
 
318
        """
280
319
        unique_tips = self._remove_simple_descendants(unique_nodes,
281
320
                        self.get_parent_map(unique_nodes))
282
321
 
283
322
        if len(unique_tips) == 1:
284
 
            unique_searchers = []
 
323
            unique_tip_searchers = []
285
324
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
286
325
        else:
287
 
            unique_searchers = []
 
326
            unique_tip_searchers = []
288
327
            for tip in unique_tips:
289
328
                revs_to_search = unique_searcher.find_seen_ancestors([tip])
290
329
                revs_to_search.update(
293
332
                # We don't care about the starting nodes.
294
333
                searcher._label = tip
295
334
                searcher.step()
296
 
                unique_searchers.append(searcher)
 
335
                unique_tip_searchers.append(searcher)
297
336
 
298
337
            ancestor_all_unique = None
299
 
            for searcher in unique_searchers:
 
338
            for searcher in unique_tip_searchers:
300
339
                if ancestor_all_unique is None:
301
340
                    ancestor_all_unique = set(searcher.seen)
302
341
                else:
303
342
                    ancestor_all_unique = ancestor_all_unique.intersection(
304
343
                                                searcher.seen)
305
344
        # Collapse all the common nodes into a single searcher
306
 
        all_unique_searcher = self._make_breadth_first_searcher(ancestor_all_unique)
 
345
        all_unique_searcher = self._make_breadth_first_searcher(
 
346
                                ancestor_all_unique)
307
347
        if ancestor_all_unique:
 
348
            # We've seen these nodes in all the searchers, so we'll just go to
 
349
            # the next
308
350
            all_unique_searcher.step()
309
351
 
310
352
            # Stop any search tips that are already known as ancestors of the
313
355
                common_searcher.find_seen_ancestors(ancestor_all_unique))
314
356
 
315
357
            total_stopped = 0
316
 
            for searcher in unique_searchers:
 
358
            for searcher in unique_tip_searchers:
317
359
                total_stopped += len(searcher.stop_searching_any(
318
360
                    searcher.find_seen_ancestors(ancestor_all_unique)))
319
 
            _mutter('For %s unique nodes, created %s + 1 unique searchers'
320
 
                    ' (%s stopped search tips, %s common ancestors'
321
 
                    ' (%s stopped common)',
322
 
                    len(unique_nodes), len(unique_searchers), total_stopped,
323
 
                    len(ancestor_all_unique), len(stopped_common))
324
 
            del ancestor_all_unique, stopped_common
325
 
 
326
 
        # We step the ancestor_all_unique searcher only every other step
327
 
        step_all_unique = 0
 
361
        if 'graph' in debug.debug_flags:
 
362
            trace.mutter('For %s unique nodes, created %s + 1 unique searchers'
 
363
                         ' (%s stopped search tips, %s common ancestors'
 
364
                         ' (%s stopped common)',
 
365
                         len(unique_nodes), len(unique_tip_searchers),
 
366
                         total_stopped, len(ancestor_all_unique),
 
367
                         len(stopped_common))
 
368
        return all_unique_searcher, unique_tip_searchers
 
369
 
 
370
    def _step_unique_and_common_searchers(self, common_searcher,
 
371
                                          unique_tip_searchers,
 
372
                                          unique_searcher):
 
373
        newly_seen_common = set(common_searcher.step())
 
374
        newly_seen_unique = set()
 
375
        for searcher in unique_tip_searchers:
 
376
            next = set(searcher.step())
 
377
            next.update(unique_searcher.find_seen_ancestors(next))
 
378
            next.update(common_searcher.find_seen_ancestors(next))
 
379
            for alt_searcher in unique_tip_searchers:
 
380
                if alt_searcher is searcher:
 
381
                    continue
 
382
                next.update(alt_searcher.find_seen_ancestors(next))
 
383
            searcher.start_searching(next)
 
384
            newly_seen_unique.update(next)
 
385
        return newly_seen_common, newly_seen_unique,
 
386
 
 
387
    def _find_nodes_common_to_all_unique(self, unique_tip_searchers,
 
388
                                         all_unique_searcher,
 
389
                                         newly_seen_unique, step_all_unique):
 
390
        """Find nodes that are common to all unique_tip_searchers.
 
391
 
 
392
        If it is time, step the all_unique_searcher, and add its nodes to the
 
393
        result.
 
394
        """
 
395
        unique_are_common_nodes = newly_seen_unique.copy()
 
396
        for searcher in unique_tip_searchers:
 
397
            unique_are_common_nodes.intersection_update(searcher.seen)
 
398
        unique_are_common_nodes.intersection_update(
 
399
                                    all_unique_searcher.seen)
 
400
        # Step all-unique less frequently than the other searchers.
 
401
        # In the common case, we don't need to spider out far here, so
 
402
        # avoid doing extra work.
 
403
        if not step_all_unique:
 
404
            tstart = time.clock()
 
405
            nodes = all_unique_searcher.step()
 
406
            unique_are_common_nodes.update(nodes)
 
407
            tdelta = time.clock() - tstart
 
408
            if 'graph' in debug.debug_flags:
 
409
                trace.mutter('all_unique_searcher step() took %.3fs'
 
410
                             'for %d nodes (%d total), iteration: %s',
 
411
                             tdelta, len(nodes), len(all_unique_searcher.seen),
 
412
                             all_unique_searcher._iterations)
 
413
        return unique_are_common_nodes
 
414
 
 
415
    def _collapse_unique_searchers(self, unique_tip_searchers,
 
416
                                   unique_are_common_nodes):
 
417
        """Combine searchers that are searching the same tips.
 
418
 
 
419
        When two searchers are searching the same tips, we can stop one of the
 
420
        searchers. We also know that the maximal set of common ancestors is the
 
421
        intersection of the two original searchers.
 
422
 
 
423
        :return: A list of searchers that are searching unique nodes.
 
424
        """
 
425
        # Filter out searchers that don't actually search different
 
426
        # nodes. We already have the ancestry intersection for them
 
427
        unique_search_tips = {}
 
428
        for searcher in unique_tip_searchers:
 
429
            stopped = searcher.stop_searching_any(unique_are_common_nodes)
 
430
            will_search_set = frozenset(searcher._next_query)
 
431
            if not will_search_set:
 
432
                if 'graph' in debug.debug_flags:
 
433
                    trace.mutter('Unique searcher %s was stopped.'
 
434
                                 ' (%s iterations) %d nodes stopped',
 
435
                                 searcher._label,
 
436
                                 searcher._iterations,
 
437
                                 len(stopped))
 
438
            elif will_search_set not in unique_search_tips:
 
439
                # This searcher is searching a unique set of nodes, let it
 
440
                unique_search_tips[will_search_set] = [searcher]
 
441
            else:
 
442
                unique_search_tips[will_search_set].append(searcher)
 
443
        # TODO: it might be possible to collapse searchers faster when they
 
444
        #       only have *some* search tips in common.
 
445
        next_unique_searchers = []
 
446
        for searchers in unique_search_tips.itervalues():
 
447
            if len(searchers) == 1:
 
448
                # Searching unique tips, go for it
 
449
                next_unique_searchers.append(searchers[0])
 
450
            else:
 
451
                # These searchers have started searching the same tips, we
 
452
                # don't need them to cover the same ground. The
 
453
                # intersection of their ancestry won't change, so create a
 
454
                # new searcher, combining their histories.
 
455
                next_searcher = searchers[0]
 
456
                for searcher in searchers[1:]:
 
457
                    next_searcher.seen.intersection_update(searcher.seen)
 
458
                if 'graph' in debug.debug_flags:
 
459
                    trace.mutter('Combining %s searchers into a single'
 
460
                                 ' searcher searching %s nodes with'
 
461
                                 ' %s ancestry',
 
462
                                 len(searchers),
 
463
                                 len(next_searcher._next_query),
 
464
                                 len(next_searcher.seen))
 
465
                next_unique_searchers.append(next_searcher)
 
466
        return next_unique_searchers
 
467
 
 
468
    def _refine_unique_nodes(self, unique_searcher, all_unique_searcher,
 
469
                             unique_tip_searchers, common_searcher):
 
470
        """Steps 5-8 of find_unique_ancestors.
 
471
        
 
472
        This function returns when common_searcher has stopped searching for
 
473
        more nodes.
 
474
        """
 
475
        # We step the ancestor_all_unique searcher only every
 
476
        # STEP_UNIQUE_SEARCHER_EVERY steps.
 
477
        step_all_unique_counter = 0
328
478
        # While we still have common nodes to search
329
479
        while common_searcher._next_query:
330
 
            newly_seen_common = set(common_searcher.step())
331
 
            newly_seen_unique = set()
332
 
            def step_searchers():
333
 
                for searcher in unique_searchers:
334
 
                    next = set(searcher.step())
335
 
                    next.update(unique_searcher.find_seen_ancestors(next))
336
 
                    next.update(common_searcher.find_seen_ancestors(next))
337
 
                    for alt_searcher in unique_searchers:
338
 
                        if alt_searcher is searcher:
339
 
                            continue
340
 
                        next.update(alt_searcher.find_seen_ancestors(next))
341
 
                    searcher.start_searching(next)
342
 
                    newly_seen_unique.update(next)
343
 
            step_searchers()
 
480
            (newly_seen_common,
 
481
             newly_seen_unique) = self._step_unique_and_common_searchers(
 
482
                common_searcher, unique_tip_searchers, unique_searcher)
344
483
            # These nodes are common ancestors of all unique nodes
345
 
            unique_are_common_nodes = newly_seen_unique.copy()
346
 
            def intersect_searchers():
347
 
                for searcher in unique_searchers:
348
 
                    unique_are_common_nodes.intersection_update(searcher.seen)
349
 
                unique_are_common_nodes.intersection_update(
350
 
                                            all_unique_searcher.seen)
351
 
                # Step the all-unique less frequently than the other searchers.
352
 
                # In the common case, we don't need to spider out far here, so
353
 
                # avoid doing extra work.
354
 
                if not step_all_unique:
355
 
                    tstart = time.clock()
356
 
                    nodes = all_unique_searcher.step()
357
 
                    unique_are_common_nodes.update(nodes)
358
 
                    tdelta = time.clock() - tstart
359
 
                    _mutter('all_unique_searcher step() took %.3fs for %d nodes'
360
 
                            ' (%d total), iteration: %s', tdelta, 
361
 
                            len(nodes), len(all_unique_searcher.seen),
362
 
                            all_unique_searcher._iterations)
363
 
            intersect_searchers()
364
 
            step_all_unique = (step_all_unique + 1) % STEP_UNIQUE_SEARCHER_EVERY
 
484
            unique_are_common_nodes = self._find_nodes_common_to_all_unique(
 
485
                unique_tip_searchers, all_unique_searcher, newly_seen_unique,
 
486
                step_all_unique_counter==0)
 
487
            step_all_unique_counter = ((step_all_unique_counter + 1)
 
488
                                       % STEP_UNIQUE_SEARCHER_EVERY)
365
489
 
366
490
            if newly_seen_common:
367
491
                # If a 'common' node is an ancestor of all unique searchers, we
376
500
                all_unique_searcher.start_searching(unique_are_common_nodes)
377
501
                common_searcher.stop_searching_any(unique_are_common_nodes)
378
502
 
379
 
            def filter_searchers():
380
 
                # Filter out searchers that don't actually search different
381
 
                # nodes. We already have the ancestry intersection for them
382
 
                unique_search_tips = {}
383
 
                for searcher in unique_searchers:
384
 
                    stopped = searcher.stop_searching_any(unique_are_common_nodes)
385
 
                    will_search_set = frozenset(searcher._next_query)
386
 
                    if not will_search_set:
387
 
                        _mutter('Unique searcher %s was stopped.'
388
 
                                ' (%s iterations) %d nodes stopped',
389
 
                                searcher._label,
390
 
                                searcher._iterations,
391
 
                                len(stopped))
392
 
                    elif will_search_set not in unique_search_tips:
393
 
                        # This searcher is searching a unique set of nodes, let it
394
 
                        unique_search_tips[will_search_set] = [searcher]
395
 
                    else:
396
 
                        unique_search_tips[will_search_set].append(searcher)
397
 
                next_unique_searchers = []
398
 
                for searchers in unique_search_tips.itervalues():
399
 
                    if len(searchers) == 1:
400
 
                        # Searching unique tips, go for it
401
 
                        next_unique_searchers.append(searchers[0])
402
 
                    else:
403
 
                        # These searchers have started searching the same tips, we
404
 
                        # don't need them to cover the same ground. The
405
 
                        # intersection of their ancestry won't change, so create a
406
 
                        # new searcher, combining their histories.
407
 
                        next_searcher = searchers[0]
408
 
                        ancestor_intersection = next_searcher.seen
409
 
                        for searcher in searchers[1:]:
410
 
                            ancestor_intersection = ancestor_intersection.intersection(searcher.seen)
411
 
                        next_searcher.seen = ancestor_intersection
412
 
                        _mutter('Combining %s searchers into a single searcher'
413
 
                                ' searching %s nodes with %s ancestry',
414
 
                                len(searchers), len(next_searcher._next_query),
415
 
                                len(next_searcher.seen))
416
 
                        next_unique_searchers.append(next_searcher)
417
 
                return next_unique_searchers
418
 
            next_unique_searchers = filter_searchers()
419
 
            if len(unique_searchers) != len(next_unique_searchers):
420
 
                _mutter('Collapsed %s unique searchers => %s'
421
 
                        ' at %s iterations',
422
 
                        len(unique_searchers), len(next_unique_searchers),
423
 
                        all_unique_searcher._iterations)
424
 
            unique_searchers = next_unique_searchers
425
 
        true_unique_nodes = unique_nodes.difference(common_searcher.seen)
426
 
        _mutter('Found %s truly unique nodes out of %s',
427
 
                len(true_unique_nodes), len(unique_nodes))
428
 
        return true_unique_nodes
 
503
            next_unique_searchers = self._collapse_unique_searchers(
 
504
                unique_tip_searchers, unique_are_common_nodes)
 
505
            if len(unique_tip_searchers) != len(next_unique_searchers):
 
506
                if 'graph' in debug.debug_flags:
 
507
                    trace.mutter('Collapsed %s unique searchers => %s'
 
508
                                 ' at %s iterations',
 
509
                                 len(unique_tip_searchers),
 
510
                                 len(next_unique_searchers),
 
511
                                 all_unique_searcher._iterations)
 
512
            unique_tip_searchers = next_unique_searchers
429
513
 
430
514
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
431
515
    def get_parents(self, revisions):
1095
1179
        return self
1096
1180
 
1097
1181
    def find_seen_ancestors(self, revisions):
1098
 
        """Find ancestors of these revisions that have already been seen."""
 
1182
        """Find ancestors of these revisions that have already been seen.
 
1183
        
 
1184
        This function generally makes the assumption that querying for the
 
1185
        parents of a node that has already been queried is reasonably cheap.
 
1186
        (eg, not a round trip to a remote host).
 
1187
        """
 
1188
        # TODO: Often we might ask one searcher for its seen ancestors, and
 
1189
        #       then ask another searcher the same question. This can result in
 
1190
        #       searching the same revisions repeatedly if the two searchers
 
1191
        #       have a lot of overlap.
1099
1192
        all_seen = self.seen
1100
1193
        pending = set(revisions).intersection(all_seen)
1101
1194
        seen_ancestors = set(pending)
1130
1223
        None of the specified revisions are required to be present in the
1131
1224
        search list.  In this case, the call is a no-op.
1132
1225
        """
 
1226
        # TODO: does this help performance?
 
1227
        # if not revisions:
 
1228
        #     return set()
1133
1229
        revisions = frozenset(revisions)
1134
1230
        if self._returning == 'next':
1135
1231
            stopped = self._next_query.intersection(revisions)