611 |
611 |
612 common = [self.rev(n) for n in common] |
612 common = [self.rev(n) for n in common] |
613 heads = [self.rev(n) for n in heads] |
613 heads = [self.rev(n) for n in heads] |
614 |
614 |
615 # we want the ancestors, but inclusive |
615 # we want the ancestors, but inclusive |
616 has = dict.fromkeys(self.ancestors(*common)) |
616 has = set(self.ancestors(*common)) |
617 has[nullrev] = None |
617 has.add(nullrev) |
618 for r in common: |
618 has.update(common) |
619 has[r] = None |
|
620 |
619 |
621 # take all ancestors from heads that aren't in has |
620 # take all ancestors from heads that aren't in has |
622 missing = {} |
621 missing = {} |
623 visit = [r for r in heads if r not in has] |
622 visit = [r for r in heads if r not in has] |
624 while visit: |
623 while visit: |
724 else: |
723 else: |
725 # We are descending from nullid, and don't need to care about |
724 # We are descending from nullid, and don't need to care about |
726 # any other roots. |
725 # any other roots. |
727 lowestrev = nullrev |
726 lowestrev = nullrev |
728 roots = [nullid] |
727 roots = [nullid] |
729 # Transform our roots list into a 'set' (i.e. a dictionary where the |
728 # Transform our roots list into a set. |
730 # values don't matter. |
729 descendents = set(roots) |
731 descendents = dict.fromkeys(roots, 1) |
|
732 # Also, keep the original roots so we can filter out roots that aren't |
730 # Also, keep the original roots so we can filter out roots that aren't |
733 # 'real' roots (i.e. are descended from other roots). |
731 # 'real' roots (i.e. are descended from other roots). |
734 roots = descendents.copy() |
732 roots = descendents.copy() |
735 # Our topologically sorted list of output nodes. |
733 # Our topologically sorted list of output nodes. |
736 orderedout = [] |
734 orderedout = [] |
750 if n in roots: |
748 if n in roots: |
751 # If n was a root, check if it's a 'real' root. |
749 # If n was a root, check if it's a 'real' root. |
752 p = tuple(self.parents(n)) |
750 p = tuple(self.parents(n)) |
753 # If any of its parents are descendents, it's not a root. |
751 # If any of its parents are descendents, it's not a root. |
754 if (p[0] in descendents) or (p[1] in descendents): |
752 if (p[0] in descendents) or (p[1] in descendents): |
755 roots.pop(n) |
753 roots.remove(n) |
756 else: |
754 else: |
757 p = tuple(self.parents(n)) |
755 p = tuple(self.parents(n)) |
758 # A node is a descendent if either of its parents are |
756 # A node is a descendent if either of its parents are |
759 # descendents. (We seeded the dependents list with the roots |
757 # descendents. (We seeded the dependents list with the roots |
760 # up there, remember?) |
758 # up there, remember?) |
761 if (p[0] in descendents) or (p[1] in descendents): |
759 if (p[0] in descendents) or (p[1] in descendents): |
762 descendents[n] = 1 |
760 descendents.add(n) |
763 isdescendent = True |
761 isdescendent = True |
764 if isdescendent and ((ancestors is None) or (n in ancestors)): |
762 if isdescendent and ((ancestors is None) or (n in ancestors)): |
765 # Only include nodes that are both descendents and ancestors. |
763 # Only include nodes that are both descendents and ancestors. |
766 orderedout.append(n) |
764 orderedout.append(n) |
767 if (ancestors is not None) and (n in heads): |
765 if (ancestors is not None) and (n in heads): |
776 heads[n] = 1 |
774 heads[n] = 1 |
777 # But, obviously its parents aren't. |
775 # But, obviously its parents aren't. |
778 for p in self.parents(n): |
776 for p in self.parents(n): |
779 heads.pop(p, None) |
777 heads.pop(p, None) |
780 heads = [n for n in heads.iterkeys() if heads[n] != 0] |
778 heads = [n for n in heads.iterkeys() if heads[n] != 0] |
781 roots = roots.keys() |
779 roots = list(roots) |
782 assert orderedout |
780 assert orderedout |
783 assert roots |
781 assert roots |
784 assert heads |
782 assert heads |
785 return (orderedout, roots, heads) |
783 return (orderedout, roots, heads) |
786 |
784 |
805 |
803 |
806 if start is None: |
804 if start is None: |
807 start = nullid |
805 start = nullid |
808 if stop is None: |
806 if stop is None: |
809 stop = [] |
807 stop = [] |
810 stoprevs = dict.fromkeys([self.rev(n) for n in stop]) |
808 stoprevs = set([self.rev(n) for n in stop]) |
811 startrev = self.rev(start) |
809 startrev = self.rev(start) |
812 reachable = {startrev: 1} |
810 reachable = {startrev: 1} |
813 heads = {startrev: 1} |
811 heads = {startrev: 1} |
814 |
812 |
815 parentrevs = self.parentrevs |
813 parentrevs = self.parentrevs |