Mercurial > hg
changeset 14042:9966c95b8c4f
graphmod: use revsets internally
Thanks for the idea and most of the implementation to Klaus Koch
Backs revisions() and filerevs() with DAG walker which can iterate through
arbitrary list of revisions instead of strict one by one iteration from start to
stop. When a gap occurs in a revisions (i.e. in file log), the next topological
parent within the revset is searched and the connection to it is printed in the
ascii graph.
File graph can draw sometimes more connections than previous version, because
graph is produced according to the revset, not according to a file's filelog.
In case the graph contains several branches where the left parent is null, the
graphs for each are printed sequentially, not in parallel as it was a case
earlier (see for example the graph for README in hg-dev).
| author | Alexander Solovyov <alexander@solovyov.net> |
|---|---|
| date | Sun, 13 Mar 2011 15:53:38 +0100 |
| parents | bcc6ed0f6c3b |
| children | 1c1e1232abdc |
| files | hgext/graphlog.py mercurial/graphmod.py tests/test-debugbuilddag.t tests/test-glog.t |
| diffstat | 4 files changed, 297 insertions(+), 201 deletions(-) [+] |
line wrap: on
line diff
--- a/hgext/graphlog.py Fri Apr 29 03:34:18 2011 -0500 +++ b/hgext/graphlog.py Sun Mar 13 15:53:38 2011 +0100 @@ -249,8 +249,6 @@ if start == nullrev: return - if path: - path = scmutil.canonpath(repo.root, os.getcwd(), path) if path: # could be reset in canonpath revdag = graphmod.filerevs(repo, path, start, stop, limit) else:
--- a/mercurial/graphmod.py Fri Apr 29 03:34:18 2011 -0500 +++ b/mercurial/graphmod.py Sun Mar 13 15:53:38 2011 +0100 @@ -18,43 +18,66 @@ """ from mercurial.node import nullrev +from mercurial.cmdutil import revrange CHANGESET = 'C' -def revisions(repo, start, stop): - """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples - - This generator function walks through the revision history from revision - start to revision stop (which must be less than or equal to start). It - returns a tuple for each node. The node and parent ids are arbitrary - integers which identify a node in the context of the graph returned. +def revisions(repo, start, end): + """DAG generator for revisions between start and end """ - cur = start - while cur >= stop: - ctx = repo[cur] - parents = set([p.rev() for p in ctx.parents() if p.rev() != nullrev]) - yield (cur, CHANGESET, ctx, sorted(parents)) - cur -= 1 + revset = '%s:%s' % (start, end) + return dagwalker(repo, revrange(repo, [revset])) def filerevs(repo, path, start, stop, limit=None): - """file cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples + """DAG generator, which is limited by file passed + """ + revset = '%s:%s and file("%s")' % (start, stop, path) + if limit: + revset = 'limit(%s, %s)' % (revset, limit) + return dagwalker(repo, revrange(repo, [revset])) - This generator function walks through the revision history of a single - file from revision start down to revision stop. +def dagwalker(repo, revs): + """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples + + This generator function walks through revisions (which should be ordered + from bigger to lower). It returns a tuple for each node. The node and parent + ids are arbitrary integers which identify a node in the context of the graph + returned. """ - filerev = len(repo.file(path)) - 1 - rev = stop + 1 - count = 0 - while filerev >= 0 and rev > stop: - fctx = repo.filectx(path, fileid=filerev) - parents = set([f.linkrev() for f in fctx.parents() if f.path() == path]) - rev = fctx.rev() - if rev <= start: - yield (rev, CHANGESET, fctx.changectx(), sorted(parents)) - count += 1 - if count == limit: - break - filerev -= 1 + if not revs: + return [] + + ns = [repo[r].node() for r in revs] + revdag = list(nodes(repo, ns)) + + cl = repo.changelog + lowestrev = min(revs) + gpcache = {} + leafs = {} + + for i, (id, c, ctx, parents) in enumerate(revdag): + mpars = [p.rev() for p in ctx.parents() if + p.rev() != nullrev and p.rev() not in parents] + grandparents = [] + + for mpar in mpars: + gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar) + gpcache[mpar] = gp + if gp is None: + leafs.setdefault(mpar, []).append((i, ctx)) + else: + grandparents.append(gp) + + if grandparents: + for gp in grandparents: + if gp not in revdag[i][3]: + revdag[i][3].append(gp) + + for parent, leafs in leafs.iteritems(): + for i, ctx in leafs: + revdag[i][3].append(parent) + + return revdag def nodes(repo, nodes): """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples @@ -120,3 +143,78 @@ # Yield and move on 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'. + """ + ancestors = set() + # Start at the top and keep marking parents until we're done. + revstotag = set([head]) + revstotag.discard(nullrev) + 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
--- a/tests/test-debugbuilddag.t Fri Apr 29 03:34:18 2011 -0500 +++ b/tests/test-debugbuilddag.t Sun Mar 13 15:53:38 2011 +0100 @@ -317,5 +317,5 @@ glog X $ hg glog --template '{rev}: {desc} [{branches}]\n' X o 2: r2 [] - + | $ cd ..
--- a/tests/test-glog.t Fri Apr 29 03:34:18 2011 -0500 +++ b/tests/test-glog.t Sun Mar 13 15:53:38 2011 +0100 @@ -463,115 +463,115 @@ | | | date: Thu Jan 01 00:00:32 1970 +0000 | | | summary: (32) expand | | | - | o | changeset: 31:621d83e11f67 - | | | parent: 21:d42a756af44d - | | | parent: 30:6e11cd4b648f - | | | user: test - | | | date: Thu Jan 01 00:00:31 1970 +0000 - | | | summary: (31) expand - | | | - | o | changeset: 30:6e11cd4b648f - | |\ \ parent: 28:44ecd0b9ae99 - | | | | parent: 29:cd9bb2be7593 - | | | | user: test - | | | | date: Thu Jan 01 00:00:30 1970 +0000 - | | | | summary: (30) expand - | | | | - | | o | changeset: 29:cd9bb2be7593 - | | | | parent: 0:e6eb3150255d - | | | | user: test - | | | | date: Thu Jan 01 00:00:29 1970 +0000 - | | | | summary: (29) regular commit - | | | | - | o | | changeset: 28:44ecd0b9ae99 - | | | | parent: 1:6db2ef61d156 - | | | | parent: 26:7f25b6c2f0b9 + | o | changeset: 31:621d83e11f67 + | |\ \ parent: 21:d42a756af44d + | | | | parent: 30:6e11cd4b648f | | | | user: test - | | | | date: Thu Jan 01 00:00:28 1970 +0000 - | | | | summary: (28) merge zero known - | | | | - o | | | changeset: 27:886ed638191b - | | | | parent: 21:d42a756af44d - | | | | user: test - | | | | date: Thu Jan 01 00:00:27 1970 +0000 - | | | | summary: (27) collapse - | | | | - | o | | changeset: 26:7f25b6c2f0b9 - | | | | parent: 18:1aa84d96232a - | | | | parent: 25:91da8ed57247 - | | | | user: test - | | | | date: Thu Jan 01 00:00:26 1970 +0000 - | | | | summary: (26) merge one known; far right - | | | | - | o | | changeset: 25:91da8ed57247 - | | | | parent: 21:d42a756af44d - | | | | parent: 24:a9c19a3d96b7 - | | | | user: test - | | | | date: Thu Jan 01 00:00:25 1970 +0000 - | | | | summary: (25) merge one known; far left - | | | | - | o | | changeset: 24:a9c19a3d96b7 - | | | | parent: 0:e6eb3150255d - | | | | parent: 23:a01cddf0766d - | | | | user: test - | | | | date: Thu Jan 01 00:00:24 1970 +0000 - | | | | summary: (24) merge one known; immediate right + | | | | date: Thu Jan 01 00:00:31 1970 +0000 + | | | | summary: (31) expand | | | | - | o | | changeset: 23:a01cddf0766d - | | | | parent: 1:6db2ef61d156 - | | | | parent: 22:e0d9cccacb5d - | | | | user: test - | | | | date: Thu Jan 01 00:00:23 1970 +0000 - | | | | summary: (23) merge one known; immediate left - | | | | - | o | | changeset: 22:e0d9cccacb5d - |/ / / parent: 18:1aa84d96232a - | | | parent: 21:d42a756af44d - | | | user: test - | | | date: Thu Jan 01 00:00:22 1970 +0000 - | | | summary: (22) merge two known; one far left, one far right - | | | - o | | changeset: 21:d42a756af44d - |\ \ \ parent: 19:31ddc2c1573b - | | | | parent: 20:d30ed6450e32 - | | | | user: test - | | | | date: Thu Jan 01 00:00:21 1970 +0000 - | | | | summary: (21) expand + | | o | changeset: 30:6e11cd4b648f + | | |\ \ parent: 28:44ecd0b9ae99 + | | | | | parent: 29:cd9bb2be7593 + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:30 1970 +0000 + | | | | | summary: (30) expand + | | | | | + | | | o | changeset: 29:cd9bb2be7593 + | | | | | parent: 0:e6eb3150255d + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:29 1970 +0000 + | | | | | summary: (29) regular commit + | | | | | + | | o | | changeset: 28:44ecd0b9ae99 + | | |\ \ \ parent: 1:6db2ef61d156 + | | | | | | parent: 26:7f25b6c2f0b9 + | | | | | | user: test + | | | | | | date: Thu Jan 01 00:00:28 1970 +0000 + | | | | | | summary: (28) merge zero known + | | | | | | + o | | | | | changeset: 27:886ed638191b + |/ / / / / parent: 21:d42a756af44d + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:27 1970 +0000 + | | | | | summary: (27) collapse + | | | | | + | | o---+ changeset: 26:7f25b6c2f0b9 + | | | | | parent: 18:1aa84d96232a + | | | | | parent: 25:91da8ed57247 + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:26 1970 +0000 + | | | | | summary: (26) merge one known; far right + | | | | | + +---o | | changeset: 25:91da8ed57247 + | | | | | parent: 21:d42a756af44d + | | | | | parent: 24:a9c19a3d96b7 + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:25 1970 +0000 + | | | | | summary: (25) merge one known; far left + | | | | | + | | o | | changeset: 24:a9c19a3d96b7 + | | |\| | parent: 0:e6eb3150255d + | | | | | parent: 23:a01cddf0766d + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:24 1970 +0000 + | | | | | summary: (24) merge one known; immediate right + | | | | | + | | o | | changeset: 23:a01cddf0766d + | |/| | | parent: 1:6db2ef61d156 + | | | | | parent: 22:e0d9cccacb5d + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:23 1970 +0000 + | | | | | summary: (23) merge one known; immediate left + | | | | | + +---o---+ changeset: 22:e0d9cccacb5d + | | | | parent: 18:1aa84d96232a + | | / / parent: 21:d42a756af44d + | | | | user: test + | | | | date: Thu Jan 01 00:00:22 1970 +0000 + | | | | summary: (22) merge two known; one far left, one far right | | | | - | o---+ changeset: 20:d30ed6450e32 - | | | parent: 0:e6eb3150255d - | / / parent: 18:1aa84d96232a - | | | user: test - | | | date: Thu Jan 01 00:00:20 1970 +0000 - | | | summary: (20) merge two known; two far right - | | | - o | | changeset: 19:31ddc2c1573b - |\ \ \ parent: 15:1dda3f72782d - | | | | parent: 17:44765d7c06e0 - | | | | user: test - | | | | date: Thu Jan 01 00:00:19 1970 +0000 - | | | | summary: (19) expand + o | | | changeset: 21:d42a756af44d + |\ \ \ \ parent: 19:31ddc2c1573b + | | | | | parent: 20:d30ed6450e32 + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:21 1970 +0000 + | | | | | summary: (21) expand + | | | | | + | o---+-+ changeset: 20:d30ed6450e32 + | | | | parent: 0:e6eb3150255d + | / / / parent: 18:1aa84d96232a + | | | | user: test + | | | | date: Thu Jan 01 00:00:20 1970 +0000 + | | | | summary: (20) merge two known; two far right | | | | - +-----o changeset: 18:1aa84d96232a - | | | parent: 1:6db2ef61d156 - | | | parent: 15:1dda3f72782d - | | | user: test - | | | date: Thu Jan 01 00:00:18 1970 +0000 - | | | summary: (18) merge two known; two far left - | | | - | o | changeset: 17:44765d7c06e0 - | |\ \ parent: 12:86b91144a6e9 - | | | | parent: 16:3677d192927d - | | | | user: test - | | | | date: Thu Jan 01 00:00:17 1970 +0000 - | | | | summary: (17) expand + o | | | changeset: 19:31ddc2c1573b + |\ \ \ \ parent: 15:1dda3f72782d + | | | | | parent: 17:44765d7c06e0 + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:19 1970 +0000 + | | | | | summary: (19) expand + | | | | | + +---+---o changeset: 18:1aa84d96232a + | | | | parent: 1:6db2ef61d156 + | | | | parent: 15:1dda3f72782d + | | | | user: test + | | | | date: Thu Jan 01 00:00:18 1970 +0000 + | | | | summary: (18) merge two known; two far left | | | | - | | o | changeset: 16:3677d192927d - | | | | parent: 0:e6eb3150255d - | | | | parent: 1:6db2ef61d156 - | | | | user: test - | | | | date: Thu Jan 01 00:00:16 1970 +0000 - | | | | summary: (16) merge two known; one immediate right, one near right + | o | | changeset: 17:44765d7c06e0 + | |\ \ \ parent: 12:86b91144a6e9 + | | | | | parent: 16:3677d192927d + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:17 1970 +0000 + | | | | | summary: (17) expand + | | | | | + | | o---+ changeset: 16:3677d192927d + | | | | | parent: 0:e6eb3150255d + | | |/ / parent: 1:6db2ef61d156 + | | | | user: test + | | | | date: Thu Jan 01 00:00:16 1970 +0000 + | | | | summary: (16) merge two known; one immediate right, one near right | | | | o | | | changeset: 15:1dda3f72782d |\ \ \ \ parent: 13:22d8966a97e3 @@ -580,9 +580,9 @@ | | | | | date: Thu Jan 01 00:00:15 1970 +0000 | | | | | summary: (15) expand | | | | | - | o | | | changeset: 14:8eac370358ef - | |/ / / parent: 0:e6eb3150255d - | | | | parent: 12:86b91144a6e9 + | o-----+ changeset: 14:8eac370358ef + | | | | | parent: 0:e6eb3150255d + | |/ / / parent: 12:86b91144a6e9 | | | | user: test | | | | date: Thu Jan 01 00:00:14 1970 +0000 | | | | summary: (14) merge two known; one immediate right, one far right @@ -595,72 +595,72 @@ | | | | | summary: (13) expand | | | | | +---o | | changeset: 12:86b91144a6e9 - | | / / parent: 1:6db2ef61d156 + | | |/ / parent: 1:6db2ef61d156 | | | | parent: 9:7010c0af0a35 | | | | user: test | | | | date: Thu Jan 01 00:00:12 1970 +0000 | | | | summary: (12) merge two known; one immediate right, one far left | | | | - | o | | changeset: 11:832d76e6bdf2 - | | | | parent: 6:b105a072e251 - | | | | parent: 10:74c64d036d72 - | | | | user: test - | | | | date: Thu Jan 01 00:00:11 1970 +0000 - | | | | summary: (11) expand - | | | | - | o | | changeset: 10:74c64d036d72 - | | | | parent: 0:e6eb3150255d - | | | | parent: 6:b105a072e251 - | | | | user: test - | | | | date: Thu Jan 01 00:00:10 1970 +0000 - | | | | summary: (10) merge two known; one immediate left, one near right + | o | | changeset: 11:832d76e6bdf2 + | |\ \ \ parent: 6:b105a072e251 + | | | | | parent: 10:74c64d036d72 + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:11 1970 +0000 + | | | | | summary: (11) expand + | | | | | + | | o---+ changeset: 10:74c64d036d72 + | | | | | parent: 0:e6eb3150255d + | |/ / / parent: 6:b105a072e251 + | | | | user: test + | | | | date: Thu Jan 01 00:00:10 1970 +0000 + | | | | summary: (10) merge two known; one immediate left, one near right | | | | - o | | | changeset: 9:7010c0af0a35 - | | | | parent: 7:b632bb1b1224 - | | | | parent: 8:7a0b11f71937 - | | | | user: test - | | | | date: Thu Jan 01 00:00:09 1970 +0000 - | | | | summary: (9) expand - | | | | - o | | | changeset: 8:7a0b11f71937 - | | | | parent: 0:e6eb3150255d - | | | | parent: 7:b632bb1b1224 - | | | | user: test - | | | | date: Thu Jan 01 00:00:08 1970 +0000 - | | | | summary: (8) merge two known; one immediate left, one far right + o | | | changeset: 9:7010c0af0a35 + |\ \ \ \ parent: 7:b632bb1b1224 + | | | | | parent: 8:7a0b11f71937 + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:09 1970 +0000 + | | | | | summary: (9) expand + | | | | | + | o-----+ changeset: 8:7a0b11f71937 + | | | | | parent: 0:e6eb3150255d + |/ / / / parent: 7:b632bb1b1224 + | | | | user: test + | | | | date: Thu Jan 01 00:00:08 1970 +0000 + | | | | summary: (8) merge two known; one immediate left, one far right | | | | - o | | | changeset: 7:b632bb1b1224 - | | | | parent: 2:3d9a33b8d1e1 - | | | | parent: 5:4409d547b708 - | | | | user: test - | | | | date: Thu Jan 01 00:00:07 1970 +0000 - | | | | summary: (7) expand + o | | | changeset: 7:b632bb1b1224 + |\ \ \ \ parent: 2:3d9a33b8d1e1 + | | | | | parent: 5:4409d547b708 + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:07 1970 +0000 + | | | | | summary: (7) expand + | | | | | + +---o | | changeset: 6:b105a072e251 + | |/ / / parent: 2:3d9a33b8d1e1 + | | | | parent: 5:4409d547b708 + | | | | user: test + | | | | date: Thu Jan 01 00:00:06 1970 +0000 + | | | | summary: (6) merge two known; one immediate left, one far left | | | | - | o | | changeset: 6:b105a072e251 - |/ / / parent: 2:3d9a33b8d1e1 - | | | parent: 5:4409d547b708 - | | | user: test - | | | date: Thu Jan 01 00:00:06 1970 +0000 - | | | summary: (6) merge two known; one immediate left, one far left - | | | - o | | changeset: 5:4409d547b708 - | | | parent: 3:27eef8ed80b4 - | | | parent: 4:26a8bac39d9f - | | | user: test - | | | date: Thu Jan 01 00:00:05 1970 +0000 - | | | summary: (5) expand - | | | - o | | changeset: 4:26a8bac39d9f - | | | parent: 1:6db2ef61d156 - | | | parent: 3:27eef8ed80b4 - | | | user: test - | | | date: Thu Jan 01 00:00:04 1970 +0000 - | | | summary: (4) merge two known; one immediate left, one immediate right - | | | - o | | changeset: 3:27eef8ed80b4 - | | | user: test - | | | date: Thu Jan 01 00:00:03 1970 +0000 - | | | summary: (3) collapse + | o | | changeset: 5:4409d547b708 + | |\ \ \ parent: 3:27eef8ed80b4 + | | | | | parent: 4:26a8bac39d9f + | | | | | user: test + | | | | | date: Thu Jan 01 00:00:05 1970 +0000 + | | | | | summary: (5) expand + | | | | | + | | o | | changeset: 4:26a8bac39d9f + | |/|/ / parent: 1:6db2ef61d156 + | | | | parent: 3:27eef8ed80b4 + | | | | user: test + | | | | date: Thu Jan 01 00:00:04 1970 +0000 + | | | | summary: (4) merge two known; one immediate left, one immediate right + | | | | + | o | | changeset: 3:27eef8ed80b4 + |/ / / user: test + | | | date: Thu Jan 01 00:00:03 1970 +0000 + | | | summary: (3) collapse | | | o | | changeset: 2:3d9a33b8d1e1 |/ / user: test @@ -733,10 +733,10 @@ | summary: more | o changeset: 1:5ac72c0599bf - user: test - date: Thu Jan 01 00:00:00 1970 +0000 - summary: two - + | user: test + | date: Thu Jan 01 00:00:00 1970 +0000 + | summary: two + | Issue1896: File log with explicit style $ hg glog --style=default one