# HG changeset patch
# User Patrick Mezard <pmezard@gmail.com>
# Date 2011-05-01 13:51:46
# Node ID 03e1c2d35c6a0dcd139fdcde48be674f24b344fa
# Parent  5e4ec4119485904cbc6be2b2c39bb05c25556251

graphmod: correctly emit nodes with more than 2 predecessors

The grandparent() function was returning only the closest predecessor of a
missing parent while it must return all of them to display a correct ancestry
graph.

diff --git a/mercurial/graphmod.py b/mercurial/graphmod.py
--- a/mercurial/graphmod.py
+++ b/mercurial/graphmod.py
@@ -45,12 +45,13 @@ def dagwalker(repo, revs):
                  p.rev() != nullrev and p.rev() not in parents]
 
         for mpar in mpars:
-            gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar)
-            gpcache[mpar] = gp
+            gp = gpcache.get(mpar)
             if gp is None:
+                gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar)
+            if not gp:
                 parents.append(mpar)
-            elif gp not in parents:
-                parents.append(gp)
+            else:
+                parents.extend(g for g in gp if g not in parents)
 
         yield (ctx.rev(), CHANGESET, ctx, parents)
 
@@ -119,77 +120,20 @@ def colored(dag):
         yield (cur, type, data, (col, color), edges)
         seen = next
 
-
 def grandparent(cl, lowestrev, roots, head):
-    """Return closest 'root' rev in topological path from 'roots' to 'head'.
-
-    Derived from revlog.revlog.nodesbetween, but only returns next rev
-    of topologically sorted list of all nodes N that satisfy of these
-    constraints:
-
-    1. N is a descendant of some node in 'roots'
-    2. N is an ancestor of 'head'
-    3. N is some node in 'roots' or nullrev
-
-    Every node is considered to be both a descendant and an ancestor
-    of itself, so every reachable node in 'roots' and 'head' will be
-    included in 'nodes'.
+    """Return all ancestors of head in roots which revision is
+    greater or equal to lowestrev.
     """
-    ancestors = set()
-    # Start at the top and keep marking parents until we're done.
-    revstotag = set([head])
-    revstotag.discard(nullrev)
+    pending = set([head])
+    seen = set()
+    kept = set()
     llowestrev = max(nullrev, lowestrev)
-
-    while revstotag:
-        r = revstotag.pop()
-        # A node's revision number represents its place in a
-        # topologically sorted list of nodes.
-        if r >= llowestrev:
-            if r not in ancestors:
-                # If we are possibly a descendent of one of the roots
-                # and we haven't already been marked as an ancestor
-                ancestors.add(r) # Mark as ancestor
-                # Add non-nullrev parents to list of nodes to tag.
-                revstotag.update([p for p in cl.parentrevs(r)])
-
-    if not ancestors:
-        return
-    # Now that we have our set of ancestors, we want to remove any
-    # roots that are not ancestors.
-
-    # If one of the roots was nullrev, everything is included anyway.
-    if lowestrev > nullrev:
-        # But, since we weren't, let's recompute the lowest rev to not
-        # include roots that aren't ancestors.
-
-        # Filter out roots that aren't ancestors of heads
-        _roots = ancestors.intersection(roots)
-        if not _roots:
-            return
-        # Recompute the lowest revision
-        lowestrev = min(roots)
-    else:
-        # We are descending from nullrev, and don't need to care about
-        # any other roots.
-        lowestrev = nullrev
-        _roots = [nullrev]
-
-    # The roots are just the descendants.
-    # Don't start at nullrev since we don't want nullrev in our output list,
-    # and if nullrev shows up in descedents, empty parents will look like
-    # they're descendents.
-    lowestrevisnullrev = (lowestrev == nullrev)
-    for r in xrange(head - 1, max(lowestrev, -1) - 1, -1):
-        if lowestrevisnullrev or r in _roots:
-            pass
-        elif _roots.issuperset(cl.parentrevs(r)):
-            # A node is a descendent if either of its parents are
-            # descendents.  (We seeded the dependents list with the roots
-            # up there, remember?)
-            _roots.add(r)
-        else:
-            continue
-        if r in ancestors:
-            # Only include nodes that are both descendents and ancestors.
-            return r
+    while pending:
+        r = pending.pop()
+        if r >= llowestrev and r not in seen:
+            if r in roots:
+                kept.add(r)
+            else:
+                pending.update([p for p in cl.parentrevs(r)])
+            seen.add(r)
+    return sorted(kept)
diff --git a/tests/test-glog.t b/tests/test-glog.t
--- a/tests/test-glog.t
+++ b/tests/test-glog.t
@@ -1411,8 +1411,33 @@ Test log -G options
   \s*0 (re)
   $ hg log -G --only-merges --template 'nodetag {rev}\n' | grep nodetag | wc -l
   \s*28 (re)
-  $ hg log -G --no-merges --template 'nodetag {rev}\n' | grep nodetag | wc -l
-  \s*9 (re)
+  $ hg log -G --no-merges --template 'nodetag {rev}\n'
+  o  nodetag 35
+  |
+  o    nodetag 34
+  |\
+  | \
+  | |\
+  | | \
+  | | |\
+  | | | \
+  | | | |\
+  | | | | \
+  | | | | |\
+  +-+-+-+-----o  nodetag 33
+  | | | | | |
+  +---------o  nodetag 29
+  | | | | |
+  +-+-+---o  nodetag 27
+  | | | |/
+  | | | o  nodetag 3
+  | | |/
+  | | o  nodetag 2
+  | |/
+  | o  nodetag 1
+  |/
+  o  nodetag 0
+  
   $ hg log -G -d 'brace ) in a date'
   abort: invalid date: 'brace ) in a date'
   [255]