equal
deleted
inserted
replaced
554 l = mdiff.patchedsize(l, self.chunk(x)) |
554 l = mdiff.patchedsize(l, self.chunk(x)) |
555 return l |
555 return l |
556 """ |
556 """ |
557 |
557 |
558 def reachable(self, node, stop=None): |
558 def reachable(self, node, stop=None): |
559 """return a hash of all nodes ancestral to a given node, including |
559 """return the set of all nodes ancestral to a given node, including |
560 the node itself, stopping when stop is matched""" |
560 the node itself, stopping when stop is matched""" |
561 reachable = {} |
561 reachable = set((node,)) |
562 visit = [node] |
562 visit = [node] |
563 reachable[node] = 1 |
|
564 if stop: |
563 if stop: |
565 stopn = self.rev(stop) |
564 stopn = self.rev(stop) |
566 else: |
565 else: |
567 stopn = 0 |
566 stopn = 0 |
568 while visit: |
567 while visit: |
573 continue |
572 continue |
574 for p in self.parents(n): |
573 for p in self.parents(n): |
575 if self.rev(p) < stopn: |
574 if self.rev(p) < stopn: |
576 continue |
575 continue |
577 if p not in reachable: |
576 if p not in reachable: |
578 reachable[p] = 1 |
577 reachable.add(p) |
579 visit.append(p) |
578 visit.append(p) |
580 return reachable |
579 return reachable |
581 |
580 |
582 def ancestors(self, *revs): |
581 def ancestors(self, *revs): |
583 'Generate the ancestors of revs using a breadth-first visit' |
582 'Generate the ancestors of revs using a breadth-first visit' |
676 heads = {} |
675 heads = {} |
677 else: |
676 else: |
678 heads = list(heads) |
677 heads = list(heads) |
679 if not heads: |
678 if not heads: |
680 return nonodes |
679 return nonodes |
681 ancestors = {} |
680 ancestors = set() |
682 # Turn heads into a dictionary so we can remove 'fake' heads. |
681 # Turn heads into a dictionary so we can remove 'fake' heads. |
683 # Also, later we will be using it to filter out the heads we can't |
682 # Also, later we will be using it to filter out the heads we can't |
684 # find from roots. |
683 # find from roots. |
685 heads = dict.fromkeys(heads, 0) |
684 heads = dict.fromkeys(heads, 0) |
686 # Start at the top and keep marking parents until we're done. |
685 # Start at the top and keep marking parents until we're done. |
698 r = self.rev(n) |
697 r = self.rev(n) |
699 if r >= lowestrev: |
698 if r >= lowestrev: |
700 if n not in ancestors: |
699 if n not in ancestors: |
701 # If we are possibly a descendent of one of the roots |
700 # If we are possibly a descendent of one of the roots |
702 # and we haven't already been marked as an ancestor |
701 # and we haven't already been marked as an ancestor |
703 ancestors[n] = 1 # Mark as ancestor |
702 ancestors.add(n) # Mark as ancestor |
704 # Add non-nullid parents to list of nodes to tag. |
703 # Add non-nullid parents to list of nodes to tag. |
705 nodestotag.update([p for p in self.parents(n) if |
704 nodestotag.update([p for p in self.parents(n) if |
706 p != nullid]) |
705 p != nullid]) |
707 elif n in heads: # We've seen it before, is it a fake head? |
706 elif n in heads: # We've seen it before, is it a fake head? |
708 # So it is, real heads should not be the ancestors of |
707 # So it is, real heads should not be the ancestors of |
811 start = nullid |
810 start = nullid |
812 if stop is None: |
811 if stop is None: |
813 stop = [] |
812 stop = [] |
814 stoprevs = set([self.rev(n) for n in stop]) |
813 stoprevs = set([self.rev(n) for n in stop]) |
815 startrev = self.rev(start) |
814 startrev = self.rev(start) |
816 reachable = {startrev: 1} |
815 reachable = set((startrev,)) |
817 heads = {startrev: 1} |
816 heads = set((startrev,)) |
818 |
817 |
819 parentrevs = self.parentrevs |
818 parentrevs = self.parentrevs |
820 for r in xrange(startrev + 1, len(self)): |
819 for r in xrange(startrev + 1, len(self)): |
821 for p in parentrevs(r): |
820 for p in parentrevs(r): |
822 if p in reachable: |
821 if p in reachable: |
823 if r not in stoprevs: |
822 if r not in stoprevs: |
824 reachable[r] = 1 |
823 reachable.add(r) |
825 heads[r] = 1 |
824 heads.add(r) |
826 if p in heads and p not in stoprevs: |
825 if p in heads and p not in stoprevs: |
827 del heads[p] |
826 heads.remove(p) |
828 |
827 |
829 return [self.node(r) for r in heads] |
828 return [self.node(r) for r in heads] |
830 |
829 |
831 def children(self, node): |
830 def children(self, node): |
832 """find the children of a given node""" |
831 """find the children of a given node""" |