Mercurial > hg > evolve
changeset 587:8152fedbac65 stable
evolve: smarter code for divergent changeset
This newer version properly handle split now. Code and test copied for future
upstream one.
author | Pierre-Yves David <pierre-yves.david@logilab.fr> |
---|---|
date | Tue, 23 Oct 2012 16:36:29 +0200 |
parents | f01721161532 |
children | 89c8550019d0 |
files | hgext/evolve.py tests/test-obsolete-divergent.t tests/test-obsolete.t tests/test-stabilize-result.t |
diffstat | 4 files changed, 626 insertions(+), 8 deletions(-) [+] |
line wrap: on
line diff
--- a/hgext/evolve.py +++ b/hgext/evolve.py @@ -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: + # <lss> stand for Last Successors Sets + # it contains the list of all last successors for the current node. + lss = [] + for mark in markersfor[node]: + # <mlss> 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:: + + <rev1> + <successors-1A> + <rev2> + <successors-2A> + <successors-2B1> <successors-2B1> <successors-2B1> + + 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):
new file mode 100644 --- /dev/null +++ b/tests/test-obsolete-divergent.t @@ -0,0 +1,439 @@ +Test file decicated to testing the divergent troubles from obsolete changeset. + +This is the most complexe troubles from far so we isolate it in a dedicated +file. + +Enable obsolete + + $ cat >> $HGRCPATH << EOF + > [ui] + > logtemplate = {rev}:{node|short} {desc}\n + > [alias] + > debugobsolete = debugobsolete -d '0 0' + > [phases] + > publish=False + > [extensions] + > rebase= + > EOF + $ echo "evolve=$(echo $(dirname $TESTDIR))/hgext/evolve.py" >> $HGRCPATH + + + $ mkcommit() { + > echo "$1" > "$1" + > hg add "$1" + > hg ci -m "$1" + > } + $ getid() { + > hg id --debug -ir "desc('$1')" + > } + +setup repo + + $ hg init reference + $ cd reference + $ mkcommit base + $ mkcommit A_0 + $ hg up 0 + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ mkcommit A_1 + created new head + $ hg up 0 + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ mkcommit A_2 + created new head + $ hg up 0 + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ cd .. + + + $ newcase() { + > hg clone -u 0 -q reference $1 + > cd $1 + > } + +direct divergence +----------------- + +A_1 have two direct and divergent successors A_1 and A_1 + + $ newcase direct + $ hg debugobsolete `getid A_0` `getid A_1` + $ hg debugobsolete `getid A_0` `getid A_2` + $ hg log -G --hidden + o 3:392fd25390da A_2 + | + | o 2:82623d38b9ba A_1 + |/ + | x 1:007dc284c1f8 A_0 + |/ + @ 0:d20a80d4def3 base + + $ hg debugsuccessorssets 'all()' + d20a80d4def3 + d20a80d4def3 + 007dc284c1f8 + 392fd25390da + 82623d38b9ba + 82623d38b9ba + 82623d38b9ba + 392fd25390da + 392fd25390da + $ hg log -r 'divergent()' + 2:82623d38b9ba A_1 + 3:392fd25390da A_2 + +check that mercurial refuse to push + + $ hg init ../other + $ hg push ../other + pushing to ../other + searching for changes + abort: push includes a divergent changeset: 82623d38b9ba! + (use 'hg evolve' to get a stable history or --force to ignore warnings) + [255] + + $ cd .. + + +indirect divergence with known changeset +------------------------------------------- + + $ newcase indirect_known + $ hg debugobsolete `getid A_0` `getid A_1` + $ hg debugobsolete `getid A_0` `getid A_2` + $ mkcommit A_3 + created new head + $ hg debugobsolete `getid A_2` `getid A_3` + $ hg log -G --hidden + @ 4:01f36c5a8fda A_3 + | + | x 3:392fd25390da A_2 + |/ + | o 2:82623d38b9ba A_1 + |/ + | x 1:007dc284c1f8 A_0 + |/ + o 0:d20a80d4def3 base + + $ hg debugsuccessorssets 'all()' + d20a80d4def3 + d20a80d4def3 + 007dc284c1f8 + 01f36c5a8fda + 82623d38b9ba + 82623d38b9ba + 82623d38b9ba + 392fd25390da + 01f36c5a8fda + 01f36c5a8fda + 01f36c5a8fda + $ hg log -r 'divergent()' + 2:82623d38b9ba A_1 + 4:01f36c5a8fda A_3 + $ cd .. + + +indirect divergence with known changeset +------------------------------------------- + + $ newcase indirect_unknown + $ hg debugobsolete `getid A_0` aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa + $ hg debugobsolete aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa `getid A_1` + $ hg debugobsolete `getid A_0` `getid A_2` + $ hg log -G --hidden + o 3:392fd25390da A_2 + | + | o 2:82623d38b9ba A_1 + |/ + | x 1:007dc284c1f8 A_0 + |/ + @ 0:d20a80d4def3 base + + $ hg debugsuccessorssets 'all()' + d20a80d4def3 + d20a80d4def3 + 007dc284c1f8 + 392fd25390da + 82623d38b9ba + 82623d38b9ba + 82623d38b9ba + 392fd25390da + 392fd25390da + $ hg log -r 'divergent()' + 2:82623d38b9ba A_1 + 3:392fd25390da A_2 + $ cd .. + +do not take unknown node in account if they are final +----------------------------------------------------- + + $ newcase final-unknown + $ hg debugobsolete `getid A_0` `getid A_1` + $ hg debugobsolete `getid A_1` `getid A_2` + $ hg debugobsolete `getid A_0` bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb + $ hg debugobsolete bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb cccccccccccccccccccccccccccccccccccccccc + $ hg debugobsolete `getid A_1` dddddddddddddddddddddddddddddddddddddddd + + $ hg debugsuccessorssets 'desc('A_0')' + 007dc284c1f8 + 392fd25390da + + $ cd .. + +divergence that converge again is not divergence anymore +----------------------------------------------------- + + $ newcase converged_divergence + $ hg debugobsolete `getid A_0` `getid A_1` + $ hg debugobsolete `getid A_0` `getid A_2` + $ mkcommit A_3 + created new head + $ hg debugobsolete `getid A_1` `getid A_3` + $ hg debugobsolete `getid A_2` `getid A_3` + $ hg log -G --hidden + @ 4:01f36c5a8fda A_3 + | + | x 3:392fd25390da A_2 + |/ + | x 2:82623d38b9ba A_1 + |/ + | x 1:007dc284c1f8 A_0 + |/ + o 0:d20a80d4def3 base + + $ hg debugsuccessorssets 'all()' + d20a80d4def3 + d20a80d4def3 + 007dc284c1f8 + 01f36c5a8fda + 82623d38b9ba + 01f36c5a8fda + 392fd25390da + 01f36c5a8fda + 01f36c5a8fda + 01f36c5a8fda + $ hg log -r 'divergent()' + $ cd .. + +split is not divergences +----------------------------- + + $ newcase split + $ hg debugobsolete `getid A_0` `getid A_1` `getid A_2` + $ hg log -G --hidden + o 3:392fd25390da A_2 + | + | o 2:82623d38b9ba A_1 + |/ + | x 1:007dc284c1f8 A_0 + |/ + @ 0:d20a80d4def3 base + + $ hg debugsuccessorssets 'all()' + d20a80d4def3 + d20a80d4def3 + 007dc284c1f8 + 82623d38b9ba 392fd25390da + 82623d38b9ba + 82623d38b9ba + 392fd25390da + 392fd25390da + $ hg log -r 'divergent()' + +Even when subsequente rewriting happen + + $ mkcommit A_3 + created new head + $ hg debugobsolete `getid A_1` `getid A_3` + $ hg up 0 + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ mkcommit A_4 + created new head + $ hg debugobsolete `getid A_2` `getid A_4` + $ hg up 0 + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ mkcommit A_5 + created new head + $ hg debugobsolete `getid A_4` `getid A_5` + $ hg log -G --hidden + @ 6:e442cfc57690 A_5 + | + | x 5:6a411f0d7a0a A_4 + |/ + | o 4:01f36c5a8fda A_3 + |/ + | x 3:392fd25390da A_2 + |/ + | x 2:82623d38b9ba A_1 + |/ + | x 1:007dc284c1f8 A_0 + |/ + o 0:d20a80d4def3 base + + $ hg debugsuccessorssets 'all()' + d20a80d4def3 + d20a80d4def3 + 007dc284c1f8 + 01f36c5a8fda e442cfc57690 + 82623d38b9ba + 01f36c5a8fda + 392fd25390da + e442cfc57690 + 01f36c5a8fda + 01f36c5a8fda + 6a411f0d7a0a + e442cfc57690 + e442cfc57690 + e442cfc57690 + $ hg log -r 'divergent()' + +Check more complexe obsolescence graft (with divergence) + + $ mkcommit B_0; hg up 0 + 0 files updated, 0 files merged, 2 files removed, 0 files unresolved + $ hg debugobsolete `getid B_0` `getid A_2` + $ mkcommit A_7; hg up 0 + created new head + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ mkcommit A_8; hg up 0 + created new head + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ hg debugobsolete `getid A_5` `getid A_7` `getid A_8` + $ mkcommit A_9; hg up 0 + created new head + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ hg debugobsolete `getid A_5` `getid A_9` + $ hg log -G --hidden + o 10:bed64f5d2f5a A_9 + | + | o 9:14608b260df8 A_8 + |/ + | o 8:7ae126973a96 A_7 + |/ + | x 7:3750ebee865d B_0 + | | + | x 6:e442cfc57690 A_5 + |/ + | x 5:6a411f0d7a0a A_4 + |/ + | o 4:01f36c5a8fda A_3 + |/ + | x 3:392fd25390da A_2 + |/ + | x 2:82623d38b9ba A_1 + |/ + | x 1:007dc284c1f8 A_0 + |/ + @ 0:d20a80d4def3 base + + $ hg debugsuccessorssets 'all()' + d20a80d4def3 + d20a80d4def3 + 007dc284c1f8 + 01f36c5a8fda bed64f5d2f5a + 01f36c5a8fda 7ae126973a96 14608b260df8 + 82623d38b9ba + 01f36c5a8fda + 392fd25390da + bed64f5d2f5a + 7ae126973a96 14608b260df8 + 01f36c5a8fda + 01f36c5a8fda + 6a411f0d7a0a + bed64f5d2f5a + 7ae126973a96 14608b260df8 + e442cfc57690 + bed64f5d2f5a + 7ae126973a96 14608b260df8 + 3750ebee865d + bed64f5d2f5a + 7ae126973a96 14608b260df8 + 7ae126973a96 + 7ae126973a96 + 14608b260df8 + 14608b260df8 + bed64f5d2f5a + bed64f5d2f5a + $ hg log -r 'divergent()' + 4:01f36c5a8fda A_3 + 8:7ae126973a96 A_7 + 9:14608b260df8 A_8 + 10:bed64f5d2f5a A_9 + +fix the divergence + + $ mkcommit A_A; hg up 0 + created new head + 0 files updated, 0 files merged, 1 files removed, 0 files unresolved + $ hg debugobsolete `getid A_9` `getid A_A` + $ hg debugobsolete `getid A_7` `getid A_A` + $ hg debugobsolete `getid A_8` `getid A_A` + $ hg log -G --hidden + o 11:a139f71be9da A_A + | + | x 10:bed64f5d2f5a A_9 + |/ + | x 9:14608b260df8 A_8 + |/ + | x 8:7ae126973a96 A_7 + |/ + | x 7:3750ebee865d B_0 + | | + | x 6:e442cfc57690 A_5 + |/ + | x 5:6a411f0d7a0a A_4 + |/ + | o 4:01f36c5a8fda A_3 + |/ + | x 3:392fd25390da A_2 + |/ + | x 2:82623d38b9ba A_1 + |/ + | x 1:007dc284c1f8 A_0 + |/ + @ 0:d20a80d4def3 base + + $ hg debugsuccessorssets 'all()' + d20a80d4def3 + d20a80d4def3 + 007dc284c1f8 + 01f36c5a8fda a139f71be9da + 82623d38b9ba + 01f36c5a8fda + 392fd25390da + a139f71be9da + 01f36c5a8fda + 01f36c5a8fda + 6a411f0d7a0a + a139f71be9da + e442cfc57690 + a139f71be9da + 3750ebee865d + a139f71be9da + 7ae126973a96 + a139f71be9da + 14608b260df8 + a139f71be9da + bed64f5d2f5a + a139f71be9da + a139f71be9da + a139f71be9da + $ hg log -r 'divergent()' + + $ cd .. + + +Subset does not diverge +------------------------------ + +Do not report divergent successors-set if it is a subset of another +successors-set. (report [A,B] not [A] + [A,B]) + + $ newcase subset + $ hg debugobsolete `getid A_0` `getid A_2` + $ hg debugobsolete `getid A_0` `getid A_1` `getid A_2` + $ hg debugsuccessorssets 'desc('A_0')' + 007dc284c1f8 + 82623d38b9ba 392fd25390da + + $ cd ..
--- a/tests/test-obsolete.t +++ b/tests/test-obsolete.t @@ -644,7 +644,13 @@ latecomer: 1 changesets $ hg debugobsolete `getid a7a6f2b5d8a5` `getid 50f11e5e3a63` $ hg log -r 'conflicting()' - changeset: 1[46]:50f11e5e3a63 (re) + changeset: 12:6db5e282cb91 + parent: 10:2033b4e49474 + user: test + date: Thu Jan 01 00:00:00 1970 +0000 + summary: add obsol_d''' + + changeset: 14:50f11e5e3a63 tag: tip parent: 11:9468a5f5d8b2 user: test
--- a/tests/test-stabilize-result.t +++ b/tests/test-stabilize-result.t @@ -297,7 +297,10 @@ Working directory parent is obsolete $ echo 'gotta break' >> a $ hg amend - 1 new divergent changesets + 2 new divergent changesets + $ hg phase 'divergent()' + 22: draft + 24: draft $ hg evolve -qn hg update -c c956a4b140b6 && hg merge ac6d600735a4 &&