« back to all changes in this revision
Viewing changes to bzrlib/graph.py
- browse files at revision 3181
- compare with another revision
- compare with revision 3287
- download diff
- download tarball
- view history from revision 3181
- Committer: Canonical.com Patch Queue Manager
- Date: 2008-01-15 02:01:29 UTC
- mfrom: (3177.3.3 breadth-first-ghosts)
- Revision ID: pqm@pqm.ubuntu.com-20080115020129-jl22ugxkca1rox94
(robertc) Add next_with_ghosts to the api on breadth-first-searchers.
(Robert Collins)
(Robert Collins)
- files modified:
- NEWS
added
removed
bzrlib/graph.py
506
506
"""
507
507
508
508
def __init__(self, revisions, parents_provider):
509
self._start = set(revisions)
510
self._search_revisions = None
511
self.seen = set(revisions)
509
self._iterations = 0
510
self._next_query = set(revisions)
511
self.seen = set()
512
512
self._parents_provider = parents_provider
513
self._returning = 'next_with_ghosts'
513
514
514
515
def __repr__(self):
515
if self._search_revisions is not None:
516
search = 'searching=%r' % (list(self._search_revisions),)
516
if self._iterations:
517
prefix = "searching"
517
518
else:
518
search = 'starting=%r' % (list(self._start),)
519
return ('_BreadthFirstSearcher(%s,'
520
' seen=%r)' % (search, list(self.seen)))
519
prefix = "starting"
520
search = '%s=%r' % (prefix, list(self._next_query))
521
return ('_BreadthFirstSearcher(iterations=%d, %s,'
522
' seen=%r)' % (self._iterations, search, list(self.seen)))
521
523
522
524
def next(self):
523
525
"""Return the next ancestors of this revision.
524
526
525
527
Ancestors are returned in the order they are seen in a breadth-first
526
traversal. No ancestor will be returned more than once.
528
traversal. No ancestor will be returned more than once. Ancestors are
529
returned before their parentage is queried, so ghosts and missing
530
revisions (including the start revisions) are included in the result.
531
This can save a round trip in LCA style calculation by allowing
532
convergence to be detected without reading the data for the revision
533
the convergence occurs on.
534
535
:return: A set of revision_ids.
527
536
"""
528
if self._search_revisions is None:
529
self._search_revisions = self._start
537
if self._returning != 'next':
538
# switch to returning the query, not the results.
539
self._returning = 'next'
540
self._iterations += 1
541
self.seen.update(self._next_query)
530
542
else:
531
new_search_revisions = set()
532
parent_map = self._parents_provider.get_parent_map(
533
self._search_revisions)
534
for parents in parent_map.itervalues():
535
new_search_revisions.update(p for p in parents if
536
p not in self.seen)
537
self._search_revisions = new_search_revisions
538
if len(self._search_revisions) == 0:
539
raise StopIteration()
540
self.seen.update(self._search_revisions)
541
return self._search_revisions
543
self._advance()
544
if len(self._next_query) == 0:
545
raise StopIteration()
546
return self._next_query
547
548
def next_with_ghosts(self):
549
"""Return the next found ancestors, with ghosts split out.
550
551
Ancestors are returned in the order they are seen in a breadth-first
552
traversal. No ancestor will be returned more than once. Ancestors are
553
returned only after asking for their parents, which allows us to detect
554
which revisions are ghosts and which are not.
555
556
:return: A tuple with (present ancestors, ghost ancestors) sets.
557
"""
558
if self._returning != 'next_with_ghosts':
559
# switch to returning the results, not the current query.
560
self._returning = 'next_with_ghosts'
561
self._advance()
562
if len(self._next_query) == 0:
563
raise StopIteration()
564
self._advance()
565
return self._current_present, self._current_ghosts
566
567
def _advance(self):
568
"""Advance the search.
569
570
Updates self.seen, self._next_query, self._current_present,
571
self._current_ghosts, self._current_parents and self._iterations.
572
"""
573
self._iterations += 1
574
found, ghosts, next, parents = self._do_query(self._next_query)
575
self._current_present = found
576
self._current_ghosts = ghosts
577
self._next_query = next
578
self._current_parents = parents
579
580
def _do_query(self, revisions):
581
"""Query for revisions.
582
583
:param revisions: Revisions to query.
584
:return: A tuple: (set(found_revisions), set(ghost_revisions),
585
set(parents_of_found_revisions), dict(found_revisions:parents)).
586
"""
587
found_parents = set()
588
parents_of_found = set()
589
parent_map = self._parents_provider.get_parent_map(revisions)
590
for rev_id, parents in parent_map.iteritems():
591
found_parents.add(rev_id)
592
parents_of_found.update(p for p in parents if p not in self.seen)
593
ghost_parents = revisions - found_parents
594
self.seen.update(parents_of_found)
595
return found_parents, ghost_parents, parents_of_found, parent_map
542
596
543
597
def __iter__(self):
544
598
return self
562
616
None of the specified revisions are required to be present in the
563
617
search list. In this case, the call is a no-op.
564
618
"""
565
stopped = self._search_revisions.intersection(revisions)
566
self._search_revisions = self._search_revisions.difference(revisions)
619
revisions = frozenset(revisions)
620
if self._returning == 'next':
621
stopped = self._next_query.intersection(revisions)
622
self._next_query = self._next_query.difference(revisions)
623
else:
624
stopped = set()
625
stopped.update(self._current_present.intersection(revisions))
626
stopped.update(self._current_ghosts.intersection(revisions))
627
self._current_present.difference_update(stopped)
628
self._current_ghosts.difference_update(stopped)
629
# stopping 'x' should stop returning parents of 'x', but
630
# not if 'y' always references those same parents
631
stop_rev_references = {}
632
for rev in stopped:
633
for parent_id in self._current_parents[rev]:
634
if parent_id not in stop_rev_references:
635
stop_rev_references[parent_id] = 0
636
stop_rev_references[parent_id] += 1
637
# if only the stopped revisions reference it, the ref count will be
638
# 0 after this loop
639
for parents in self._current_parents.itervalues():
640
for parent_id in parents:
641
try:
642
stop_rev_references[parent_id] -= 1
643
except KeyError:
644
pass
645
stop_parents = set()
646
for rev_id, refs in stop_rev_references.iteritems():
647
if refs == 0:
648
stop_parents.add(rev_id)
649
self._next_query.difference_update(stop_parents)
567
650
return stopped
568
651
569
652
def start_searching(self, revisions):
570
if self._search_revisions is None:
571
self._start = set(revisions)
653
"""Add revisions to the search.
654
655
The parents of revisions will be returned from the next call to next()
656
or next_with_ghosts(). If next_with_ghosts was the most recently used
657
next* call then the return value is the result of looking up the
658
ghost/not ghost status of revisions. (A tuple (present, ghosted)).
659
"""
660
revisions = frozenset(revisions)
661
if self._returning == 'next':
662
self._next_query.update(revisions.difference(self.seen))
663
self.seen.update(revisions)
572
664
else:
573
self._search_revisions.update(revisions.difference(self.seen))
574
self.seen.update(revisions)
665
# perform a query on revisions
666
revs, ghosts, query, parents = self._do_query(revisions)
667
self._current_present.update(revs)
668
self._current_ghosts.update(ghosts)
669
self._next_query.update(query)
670
self._current_parents.update(parents)
671
return revs, ghosts
Loggerhead is a web-based interface for Breezy
Version: 2.0.1