Submitter | Pierre-Yves David |
---|---|

Date | Nov. 18, 2014, 11:56 p.m. |

Message ID | <ee131567469924b16429.1416354969@marginatus.alto.octopoid.net> |

Download | mbox | patch |

Permalink | /patch/6781/ |

State | Superseded |

Headers | show |

## Comments

## Patch

diff --git a/mercurial/graphmod.py b/mercurial/graphmod.py --- a/mercurial/graphmod.py +++ b/mercurial/graphmod.py @@ -96,83 +96,87 @@ def topoiter(revs, parentsfunc): # would be easy. The iteration will have to be done using both input # revision and parents (see cl.ancestors function + a few tweaks) but # only revisions parts of the initial set should be emitted. groups = [([], unblocked)] for current in revs: - # Look for a group awaiting on the current revision. - matching = [i for i, g in enumerate(groups) if current in g[1]] + if True: + # Look for a group awaiting on the current revision. + matching = [i for i, g in enumerate(groups) if current in g[1]] - if matching: - # The main idea is to gather together all set that await on the - # same revision. + if matching: + # The main idea is to gather together all set that await on the + # same revision. + # + # this merging is done at the time we are about to add this + # common awaited to the group for simplicity purpose. Such + # merge could happen sooner when we update the "blocked" set of + # revision. + # + # We also always keep the oldest group first. We can + # probably improve the behavior by having the longuest set + # first. That way, graph algorythms could minimise the + # length of parallele lines their draw. This is currently + # not done. + targetidx = matching.pop(0) + trevs, tparents = groups[targetidx] + for i in matching: + gr = groups[i] + trevs.extend(gr[0]) + tparents |= gr[1] + # delete all merged groups (but the one we keep) + # (starting from the last group for performance and sanity + # reason) + for i in reversed(matching): + del groups[i] + else: + # his is a new head we create a new group for it. + targetidx = len(groups) + groups.append(([], set([current]))) + + gr = groups[targetidx] + + # We now adds the current nodes to this groups. This is done after + # the group merging because all elements from a group that relied + # on this rev must preceed it. # - # this merging is done at the time we are about to add this common - # awaited to the group for simplicity purpose. Such merge could - # happen sooner when we update the "blocked" set of revision. + # we also update the <parents> set to includes the parents on the + # new nodes. + gr[0].append(current) + gr[1].remove(current) + gr[1].update([p for p in parentsfunc(current) if p > nullrev]) + + # Look for a group to display # - # We also always keep the oldest group first. We can - # probably improve the behavior by having the longuest set - # first. That way, graph algorythms could minimise the - # length of parallele lines their draw. This is currently - # not done. - targetidx = matching.pop(0) - trevs, tparents = groups[targetidx] - for i in matching: - gr = groups[i] - trevs.extend(gr[0]) - tparents |= gr[1] - # delete all merged groups (but the one we keep) - # (starting from the last group for performance and sanity reason) - for i in reversed(matching): - del groups[i] - else: - # his is a new head we create a new group for it. - targetidx = len(groups) - groups.append(([], set([current]))) + # When unblocked is empty (if clause), We are not waiting over any + # revision during the first iteration (if no priority was given) or + # if we outputed a whole disconnected sets of the graph (reached a + # root). In that case we arbitrarily takes the oldest known group. + # The heuristique could probably be better. + # + # Otherwise (elif clause) this mean we have some emitted revision. + # if the group awaits on the same revision that the outputed ones, + # we can safely output it. + if not unblocked: + if len(groups) > 1: # display other subset + targetidx = 1 + gr = groups[1] + elif not gr[1] & unblocked: + gr = None - gr = groups[targetidx] - - # We now adds the current nodes to this groups. This is done after - # the group merging because all elements from a group that relied on - # this rev must preceed it. - # - # we also update the <parents> set to includes the parents on the - # new nodes. - gr[0].append(current) - gr[1].remove(current) - gr[1].update([p for p in parentsfunc(current) if p > nullrev]) - - # Look for a group to display - # - # When unblocked is empty (if clause), We are not waiting over any - # revision during the first iteration (if no priority was given) or if - # we outputed a whole disconnected sets of the graph (reached a root). - # In that case we arbitrarily takes the oldest known group. The - # heuristique could probably be better. - # - # Otherwise (elif clause) this mean we have some emitted revision. - # if the group awaits on the same revision that the outputed ones, - # we can safely output it. - if not unblocked: - if len(groups) > 1: # display other subset - targetidx = 1 - gr = groups[1] - elif not gr[1] & unblocked: - gr = None - - if gr is not None: - # update the set of awaited revisions with the one from the group - unblocked |= gr[1] - # output all revisions in the group - for r in gr[0]: - yield r - # deleted the group that you just outputed. - # unless it is group[0] in which case you just empty it. - if targetidx: - del groups[targetidx] - else: - gr[0][:] = [] + if gr is not None: + # update the set of awaited revisions with the one from the + # group + unblocked |= gr[1] + # output all revisions in the group + for r in gr[0]: + yield r + # deleted the group that you just outputed. + # unless it is group[0] in which case you just empty it. + if targetidx: + del groups[targetidx] + else: + gr[0][:] = [] def dagwalker(repo, revs): """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples This generator function walks through revisions (which should be ordered