526 # A node's revision number represents its place in a |
526 # A node's revision number represents its place in a |
527 # topologically sorted list of nodes. |
527 # topologically sorted list of nodes. |
528 r = self.rev(n) |
528 r = self.rev(n) |
529 if r >= lowestrev: |
529 if r >= lowestrev: |
530 if n not in ancestors: |
530 if n not in ancestors: |
531 # If we are possibly a descendent of one of the roots |
531 # If we are possibly a descendant of one of the roots |
532 # and we haven't already been marked as an ancestor |
532 # and we haven't already been marked as an ancestor |
533 ancestors.add(n) # Mark as ancestor |
533 ancestors.add(n) # Mark as ancestor |
534 # Add non-nullid parents to list of nodes to tag. |
534 # Add non-nullid parents to list of nodes to tag. |
535 nodestotag.update([p for p in self.parents(n) if |
535 nodestotag.update([p for p in self.parents(n) if |
536 p != nullid]) |
536 p != nullid]) |
560 # We are descending from nullid, and don't need to care about |
560 # We are descending from nullid, and don't need to care about |
561 # any other roots. |
561 # any other roots. |
562 lowestrev = nullrev |
562 lowestrev = nullrev |
563 roots = [nullid] |
563 roots = [nullid] |
564 # Transform our roots list into a set. |
564 # Transform our roots list into a set. |
565 descendents = set(roots) |
565 descendants = set(roots) |
566 # Also, keep the original roots so we can filter out roots that aren't |
566 # Also, keep the original roots so we can filter out roots that aren't |
567 # 'real' roots (i.e. are descended from other roots). |
567 # 'real' roots (i.e. are descended from other roots). |
568 roots = descendents.copy() |
568 roots = descendants.copy() |
569 # Our topologically sorted list of output nodes. |
569 # Our topologically sorted list of output nodes. |
570 orderedout = [] |
570 orderedout = [] |
571 # Don't start at nullid since we don't want nullid in our output list, |
571 # Don't start at nullid since we don't want nullid in our output list, |
572 # and if nullid shows up in descedents, empty parents will look like |
572 # and if nullid shows up in descedents, empty parents will look like |
573 # they're descendents. |
573 # they're descendants. |
574 for r in xrange(max(lowestrev, 0), highestrev + 1): |
574 for r in xrange(max(lowestrev, 0), highestrev + 1): |
575 n = self.node(r) |
575 n = self.node(r) |
576 isdescendent = False |
576 isdescendant = False |
577 if lowestrev == nullrev: # Everybody is a descendent of nullid |
577 if lowestrev == nullrev: # Everybody is a descendant of nullid |
578 isdescendent = True |
578 isdescendant = True |
579 elif n in descendents: |
579 elif n in descendants: |
580 # n is already a descendent |
580 # n is already a descendant |
581 isdescendent = True |
581 isdescendant = True |
582 # This check only needs to be done here because all the roots |
582 # This check only needs to be done here because all the roots |
583 # will start being marked is descendents before the loop. |
583 # will start being marked is descendants before the loop. |
584 if n in roots: |
584 if n in roots: |
585 # If n was a root, check if it's a 'real' root. |
585 # If n was a root, check if it's a 'real' root. |
586 p = tuple(self.parents(n)) |
586 p = tuple(self.parents(n)) |
587 # If any of its parents are descendents, it's not a root. |
587 # If any of its parents are descendants, it's not a root. |
588 if (p[0] in descendents) or (p[1] in descendents): |
588 if (p[0] in descendants) or (p[1] in descendants): |
589 roots.remove(n) |
589 roots.remove(n) |
590 else: |
590 else: |
591 p = tuple(self.parents(n)) |
591 p = tuple(self.parents(n)) |
592 # A node is a descendent if either of its parents are |
592 # A node is a descendant if either of its parents are |
593 # descendents. (We seeded the dependents list with the roots |
593 # descendants. (We seeded the dependents list with the roots |
594 # up there, remember?) |
594 # up there, remember?) |
595 if (p[0] in descendents) or (p[1] in descendents): |
595 if (p[0] in descendants) or (p[1] in descendants): |
596 descendents.add(n) |
596 descendants.add(n) |
597 isdescendent = True |
597 isdescendant = True |
598 if isdescendent and ((ancestors is None) or (n in ancestors)): |
598 if isdescendant and ((ancestors is None) or (n in ancestors)): |
599 # Only include nodes that are both descendents and ancestors. |
599 # Only include nodes that are both descendants and ancestors. |
600 orderedout.append(n) |
600 orderedout.append(n) |
601 if (ancestors is not None) and (n in heads): |
601 if (ancestors is not None) and (n in heads): |
602 # We're trying to figure out which heads are reachable |
602 # We're trying to figure out which heads are reachable |
603 # from roots. |
603 # from roots. |
604 # Mark this head as having been reached |
604 # Mark this head as having been reached |