Mercurial > hg
changeset 14131:03e1c2d35c6a
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.
| author | Patrick Mezard <pmezard@gmail.com> |
|---|---|
| date | Sun, 01 May 2011 15:51:46 +0200 |
| parents | 5e4ec4119485 |
| children | 7d3bd0640262 |
| files | mercurial/graphmod.py tests/test-glog.t |
| diffstat | 2 files changed, 46 insertions(+), 77 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/graphmod.py Sun May 01 15:51:20 2011 +0200 +++ b/mercurial/graphmod.py Sun May 01 15:51:46 2011 +0200 @@ -45,12 +45,13 @@ 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 @@ 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)
--- a/tests/test-glog.t Sun May 01 15:51:20 2011 +0200 +++ b/tests/test-glog.t Sun May 01 15:51:46 2011 +0200 @@ -1411,8 +1411,33 @@ \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]