/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: Canonical.com Patch Queue Manager
  • Date: 2008-05-21 05:46:23 UTC
  • mfrom: (3377.4.9 find_unique_ancestors)
  • Revision ID: pqm@pqm.ubuntu.com-20080521054623-5ayhndccwr6o45uq
(jam) refactor find_unique_ancestors for clarity,
        and collapse searchers for performance

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
#       /\
236
240
        #    information you have so far.
237
241
        # 5) Continue searching, stopping the common searches when the search
238
242
        #    tip is an ancestor of all unique nodes.
239
 
        # 6) Search is done when all common searchers have completed.
240
 
 
 
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)
241
265
        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
 
266
            trace.mutter('Found %d truly unique nodes out of %d',
 
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.
249
282
        unique_searcher.next()
250
283
        common_searcher = self._make_breadth_first_searcher(common_revisions)
251
284
 
 
285
        # As long as we are still finding unique nodes, keep searching
252
286
        while unique_searcher._next_query:
253
287
            next_unique_nodes = set(unique_searcher.step())
254
288
            next_common_nodes = set(common_searcher.step())
262
296
            if unique_are_common_nodes:
263
297
                ancestors = unique_searcher.find_seen_ancestors(
264
298
                                unique_are_common_nodes)
 
299
                # TODO: This is a bit overboard, we only really care about
 
300
                #       the ancestors of the tips because the rest we
 
301
                #       already know. This is *correct* but causes us to
 
302
                #       search too much ancestry.
265
303
                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
266
304
                unique_searcher.stop_searching_any(ancestors)
267
305
                common_searcher.start_searching(ancestors)
268
306
 
269
 
        unique_nodes = unique_searcher.seen.difference(common_searcher.seen)
270
 
        if not unique_nodes:
271
 
            return unique_nodes
 
307
        return unique_searcher, common_searcher
 
308
 
 
309
    def _make_unique_searchers(self, unique_nodes, unique_searcher,
 
310
                               common_searcher):
 
311
        """Create a searcher for all the unique search tips (step 4).
 
312
 
 
313
        As a side effect, the common_searcher will stop searching any nodes
 
314
        that are ancestors of the unique searcher tips.
 
315
 
 
316
        :return: (all_unique_searcher, unique_tip_searchers)
 
317
        """
272
318
        unique_tips = self._remove_simple_descendants(unique_nodes,
273
319
                        self.get_parent_map(unique_nodes))
274
320
 
275
321
        if len(unique_tips) == 1:
276
 
            unique_searchers = []
 
322
            unique_tip_searchers = []
277
323
            ancestor_all_unique = unique_searcher.find_seen_ancestors(unique_tips)
278
324
        else:
279
 
            unique_searchers = []
 
325
            unique_tip_searchers = []
280
326
            for tip in unique_tips:
281
327
                revs_to_search = unique_searcher.find_seen_ancestors([tip])
 
328
                revs_to_search.update(
 
329
                    common_searcher.find_seen_ancestors(revs_to_search))
282
330
                searcher = self._make_breadth_first_searcher(revs_to_search)
283
331
                # We don't care about the starting nodes.
284
332
                searcher._label = tip
285
333
                searcher.step()
286
 
                unique_searchers.append(searcher)
 
334
                unique_tip_searchers.append(searcher)
287
335
 
288
336
            ancestor_all_unique = None
289
 
            for searcher in unique_searchers:
 
337
            for searcher in unique_tip_searchers:
290
338
                if ancestor_all_unique is None:
291
339
                    ancestor_all_unique = set(searcher.seen)
292
340
                else:
293
341
                    ancestor_all_unique = ancestor_all_unique.intersection(
294
342
                                                searcher.seen)
295
343
        # Collapse all the common nodes into a single searcher
296
 
        all_unique_searcher = self._make_breadth_first_searcher(ancestor_all_unique)
 
344
        all_unique_searcher = self._make_breadth_first_searcher(
 
345
                                ancestor_all_unique)
297
346
        if ancestor_all_unique:
 
347
            # We've seen these nodes in all the searchers, so we'll just go to
 
348
            # the next
298
349
            all_unique_searcher.step()
299
350
 
300
351
            # Stop any search tips that are already known as ancestors of the
301
352
            # unique nodes
302
 
            common_searcher.stop_searching_any(
 
353
            stopped_common = common_searcher.stop_searching_any(
303
354
                common_searcher.find_seen_ancestors(ancestor_all_unique))
304
355
 
305
356
            total_stopped = 0
306
 
            for searcher in unique_searchers:
 
357
            for searcher in unique_tip_searchers:
307
358
                total_stopped += len(searcher.stop_searching_any(
308
359
                    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
 
 
 
360
        if 'graph' in debug.debug_flags:
 
361
            trace.mutter('For %d unique nodes, created %d + 1 unique searchers'
 
362
                         ' (%d stopped search tips, %d common ancestors'
 
363
                         ' (%d stopped common)',
 
364
                         len(unique_nodes), len(unique_tip_searchers),
 
365
                         total_stopped, len(ancestor_all_unique),
 
366
                         len(stopped_common))
 
367
        return all_unique_searcher, unique_tip_searchers
 
368
 
 
369
    def _step_unique_and_common_searchers(self, common_searcher,
 
370
                                          unique_tip_searchers,
 
371
                                          unique_searcher):
 
372
        """Step all the searchers"""
 
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
        common_to_all_unique_nodes = newly_seen_unique.copy()
 
396
        for searcher in unique_tip_searchers:
 
397
            common_to_all_unique_nodes.intersection_update(searcher.seen)
 
398
        common_to_all_unique_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 step_all_unique:
 
404
            tstart = time.clock()
 
405
            nodes = all_unique_searcher.step()
 
406
            common_to_all_unique_nodes.update(nodes)
 
407
            if 'graph' in debug.debug_flags:
 
408
                tdelta = time.clock() - tstart
 
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 common_to_all_unique_nodes
 
414
 
 
415
    def _collapse_unique_searchers(self, unique_tip_searchers,
 
416
                                   common_to_all_unique_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(common_to_all_unique_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 %d searchers into a single'
 
460
                                 ' searcher searching %d nodes with'
 
461
                                 ' %d 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
315
478
        # While we still have common nodes to search
316
479
        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())
 
480
            (newly_seen_common,
 
481
             newly_seen_unique) = self._step_unique_and_common_searchers(
 
482
                common_searcher, unique_tip_searchers, unique_searcher)
321
483
            # 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())
 
484
            common_to_all_unique_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)
 
489
 
329
490
            if newly_seen_common:
330
491
                # If a 'common' node is an ancestor of all unique searchers, we
331
492
                # can stop searching it.
332
493
                common_searcher.stop_searching_any(
333
494
                    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
 
 
 
495
            if common_to_all_unique_nodes:
 
496
                common_to_all_unique_nodes.update(
 
497
                    common_searcher.find_seen_ancestors(
 
498
                        common_to_all_unique_nodes))
346
499
                # The all_unique searcher can start searching the common nodes
347
500
                # 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)
 
501
                # This is the sort of thing where we would like to not have it
 
502
                # start_searching all of the nodes, but only mark all of them
 
503
                # as seen, and have it search only the actual tips. Otherwise
 
504
                # it is another get_parent_map() traversal for it to figure out
 
505
                # what we already should know.
 
506
                all_unique_searcher.start_searching(common_to_all_unique_nodes)
 
507
                common_searcher.stop_searching_any(common_to_all_unique_nodes)
350
508
 
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)
 
509
            next_unique_searchers = self._collapse_unique_searchers(
 
510
                unique_tip_searchers, common_to_all_unique_nodes)
 
511
            if len(unique_tip_searchers) != len(next_unique_searchers):
 
512
                if 'graph' in debug.debug_flags:
 
513
                    trace.mutter('Collapsed %d unique searchers => %d'
 
514
                                 ' at %s iterations',
 
515
                                 len(unique_tip_searchers),
 
516
                                 len(next_unique_searchers),
 
517
                                 all_unique_searcher._iterations)
 
518
            unique_tip_searchers = next_unique_searchers
379
519
 
380
520
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
381
521
    def get_parents(self, revisions):
1047
1187
        return self
1048
1188
 
1049
1189
    def find_seen_ancestors(self, revisions):
1050
 
        """Find ancestors of these revisions that have already been seen."""
 
1190
        """Find ancestors of these revisions that have already been seen.
 
1191
        
 
1192
        This function generally makes the assumption that querying for the
 
1193
        parents of a node that has already been queried is reasonably cheap.
 
1194
        (eg, not a round trip to a remote host).
 
1195
        """
 
1196
        # TODO: Often we might ask one searcher for its seen ancestors, and
 
1197
        #       then ask another searcher the same question. This can result in
 
1198
        #       searching the same revisions repeatedly if the two searchers
 
1199
        #       have a lot of overlap.
1051
1200
        all_seen = self.seen
1052
1201
        pending = set(revisions).intersection(all_seen)
1053
1202
        seen_ancestors = set(pending)
1082
1231
        None of the specified revisions are required to be present in the
1083
1232
        search list.  In this case, the call is a no-op.
1084
1233
        """
 
1234
        # TODO: does this help performance?
 
1235
        # if not revisions:
 
1236
        #     return set()
1085
1237
        revisions = frozenset(revisions)
1086
1238
        if self._returning == 'next':
1087
1239
            stopped = self._next_query.intersection(revisions)