diff -r f01721161532 -r 8152fedbac65 hgext/evolve.py --- a/hgext/evolve.py Tue Oct 23 15:44:24 2012 +0200 +++ b/hgext/evolve.py Tue Oct 23 16:36:29 2012 +0200 @@ -537,17 +537,17 @@ obsstore = repo.obsstore newermap = {} for ctx in repo.set('(not public()) - obsolete()'): - prec = obsstore.successors.get(ctx.node(), ()) - toprocess = set(prec) + mark = obsstore.successors.get(ctx.node(), ()) + toprocess = set(mark) while toprocess: prec = toprocess.pop()[0] if prec not in newermap: - newermap[prec] = newerversion(repo, prec) - newer = [n for n in newermap[prec] if n] # filter kill + successorssets(repo, prec, newermap) + newer = [n for n in newermap[prec] if n] if len(newer) > 1: divergent.add(ctx.rev()) break - toprocess.update(obsstore.successors.get(prec, ())) + toprocess.update(obsstore.successors.get(prec, ())) return divergent ### changectx method @@ -815,6 +815,122 @@ cs.add(sr) return cs +nodemod = node +def successorssets(repo, initialnode, cache=None): + """Return the newer version of an obsolete changeset""" + + # prec -> markers mapping + markersfor = repo.obsstore.precursors + + # Stack of node need to know the last successors set + toproceed = [initialnode] + # set version of toproceed for fast loop detection + stackedset = set(toproceed) + if cache is None: + cache = {} + while toproceed: + # work on the last node of the stack + node = toproceed[-1] + if node in cache: + # We already have a value for it. + # Keep working on something else. + stackedset.remove(toproceed.pop()) + elif node not in markersfor: + # The node is not obsolete. + # This mean it is its own last successors. + if node in repo: + # We have a valid last successors. + cache[node] = [(node,)] + else: + # final obsolete version is unknown locally. + # Do not count that as a valid successors + cache[node] = [] + else: + # stand for Last Successors Sets + # it contains the list of all last successors for the current node. + lss = [] + for mark in markersfor[node]: + # stand for Marker Last Successors Sets + # it contains the list of last successors set introduced by + # this marker. + mlss = [[]] + # iterate over possible multiple successors + for suc in mark[1]: + if suc not in cache: + # We do not know the last successors of that yet. + if suc in stackedset: + # Loop detected! + # + # we won't be able to ever compute a proper last + # successors the naive and simple approve is to + # consider it killed + cache[suc] = [] + else: + # Add the successor to the stack and break the next + # iteration will work on this successors and the + # algorithm will eventually process the current + # node again. + toproceed.append(suc) + stackedset.add(suc) + break + # if we did not break, we can extend the possible set of + # last successors. + # + # I say "extends" because if the marker have multiple + # successors we have to generate + # + # if successors have multiple successors set (when ther are + # divergent themself), we do a cartesian product of + # possible successors set of already processed successors + # and newly obtains successors set. + newmlss = [] + for prefix in mlss: + for suffix in cache[suc]: + newss = list(prefix) + for part in suffix: + # do not duplicated entry in successors set. + # first entry win. + if part not in newss: + newss.append(part) + newmlss.append(newss) + mlss = newmlss + else: + # note: mlss is still empty if the marker was a bare killing + # of this changeset + # + # We extends the list of all possible successors sets with + # successors set continuted by this marker + lss.extend(mlss) + # we use continue here to skip the break right bellow + continue + # propagate "nested for" break. + # if the nested for exited on break, it did not ran the else + # clause and didn't "continue + break + else: + # computation was succesful for *all* marker. + # Add computed successors set to the cache + # (will be poped from to proceeed) on the new iteration + # + # We remove successors set that are subset of another one + # this fil + candsucset = sorted(((len(ss), set(ss), ss) for ss in lss), + reverse=True) + finalsucset = [] + for cl, cs, css in candsucset: + if not css: + # remove empty successors set + continue + for fs, fss in finalsucset: + if cs.issubset(fs): + break + else: + finalsucset.append((cs, css)) + finalsucset = [s[1] for s in finalsucset] + finalsucset.reverse() + cache[node] = finalsucset + return cache[initialnode] + def newerversion(repo, obs): @@ -1681,7 +1797,7 @@ XXX this woobly function won't survive XXX """ for base in ctx._repo.set('reverse(precursors(%d))', ctx): - newer = newerversion(ctx._repo, base.node()) + newer = successorssets(ctx._repo, base.node()) # drop filter and solution including the original ctx newer = [n for n in newer if n and ctx.node() not in n] if newer: @@ -2141,6 +2257,60 @@ finally: lockmod.release(lock, wlock) +if 'debugsuccessorssets' not in commands.table: + + @command('debugsuccessorssets', + [], + _('[REV]')) + def debugsuccessorssets(ui, repo, *revs): + """show set of successors for revision + + Successors set of changeset A are a consistent group of revision that + succeed to A. Successors set contains non-obsolete changeset only. + + In most case a changeset A have zero (changeset pruned) or a single + successors set that contains a single successors (changeset A replacement + by A') + + But splitted changeset will result with successors set containing more than + a single element. Divergent rewritting will result in multiple successor + set. + + result is displayed as follows:: + + + + + + + + here rev2 have two possible successors sets. One hold three elements. + + add --debug if you want full size node id. + """ + cache = {} + s = str + if ui.debug: + def s(ctx): + return ctx.hex() + for rev in scmutil.revrange(repo, revs): + ctx = repo[rev] + if ui.debug(): + ui.write('%s\n'% ctx.hex()) + s = node.hex + else: + ui.write('%s\n'% ctx) + s = node.short + for ss in successorssets(repo, ctx.node(), cache): + if ss: + ui.write(' ') + ui.write(s(ss[0])) + for n in ss[1:]: + ui.write(' ') + ui.write(s(n)) + ui.write('\n') + pass + @eh.wrapcommand('graft') def graftwrapper(orig, ui, repo, *revs, **kwargs):