diff --git a/hgext/graphlog.py b/hgext/graphlog.py --- a/hgext/graphlog.py +++ b/hgext/graphlog.py @@ -249,8 +249,6 @@ def graphlog(ui, repo, path=None, **opts 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: diff --git a/mercurial/graphmod.py b/mercurial/graphmod.py --- a/mercurial/graphmod.py +++ b/mercurial/graphmod.py @@ -18,43 +18,66 @@ Data depends on type. """ 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 @@ def colored(dag): # 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 diff --git a/tests/test-debugbuilddag.t b/tests/test-debugbuilddag.t --- a/tests/test-debugbuilddag.t +++ b/tests/test-debugbuilddag.t @@ -317,5 +317,5 @@ glog glog X $ hg glog --template '{rev}: {desc} [{branches}]\n' X o 2: r2 [] - + | $ cd .. diff --git a/tests/test-glog.t b/tests/test-glog.t --- a/tests/test-glog.t +++ b/tests/test-glog.t @@ -463,115 +463,115 @@ File glog: | | | 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 @@ File glog: | | | | | 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 @@ File glog: | | | | | 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 @@ File log with revs != cset revs: | 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