[PATCH 1 of 5] obsolete: compute successors set
Augie Fackler
raf at durin42.com
Sun Nov 11 15:38:07 CST 2012
This looks reasonable to me, though I found the new function in obsolete a little hard to follow control-flow wise. I don't have any suggestions on how to simplify it though.
On Nov 9, 2012, at 7:23 PM, Pierre-Yves David <pierre-yves.david at ens-lyon.org> wrote:
> # HG changeset patch
> # User Pierre-Yves David <pierre-yves.david at logilab.fr>
> # Date 1352486233 -3600
> # Node ID c9b7c8ba13c0904afea4ecf035db2c02befab070
> # Parent fb14a5dcdc62987512820531fe60719d650491b6
> obsolete: compute successors set
>
> Successors set are an important part of obsolescence. It is necessary to detect
> and solve divergence situation. This changeset add a core function to compute
> them, a debug command to audit them and solid test on the concept.
>
> Check function docstring for details about the concept.
>
> diff --git a/mercurial/commands.py b/mercurial/commands.py
> --- a/mercurial/commands.py
> +++ b/mercurial/commands.py
> @@ -2451,6 +2451,58 @@
> ui.write(' source %s\n' % v[0])
> ui.write(' revision %s\n' % v[1])
>
> + at 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 = hex
> + else:
> + ui.write('%s\n'% ctx)
> + s = short
> + for ss in obsolete.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
> +
> @command('debugwalk', walkopts, _('[OPTION]... [FILE]...'))
> def debugwalk(ui, repo, *pats, **opts):
> """show how files match on given patterns"""
> diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
> --- a/mercurial/obsolete.py
> +++ b/mercurial/obsolete.py
> @@ -402,6 +402,125 @@
> seen.add(suc)
> remaining.add(suc)
>
> +nodemod = node
> +def successorssets(repo, initialnode, cache=None):
> + """Return all set of successors of initial nodes
> +
> + 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.
> +
> + They are returned as a list of tuple containing all valid successors set.
> +
> + Final successors unknown locally are considered plain prune (obsoleted
> + without successors).
> +
> + The `cache` parameter is a dictionary that may contains precomputed
> + successors set. It is meant to reuse the computation of previous call to
> + successorssets when multiple call are made at the same time."""
> +
> + # prec -> markers mapping
> + markersfor = repo.obsstore.successors
> +
> + # 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 next iteration)
> + cache[node] = list(set(tuple(r) for r in lss if r))
> + return cache[initialnode]
> +
> def _knownrevs(repo, nodes):
> """yield revision numbers of known nodes passed in parameters
>
> diff --git a/tests/test-debugcomplete.t b/tests/test-debugcomplete.t
> --- a/tests/test-debugcomplete.t
> +++ b/tests/test-debugcomplete.t
> @@ -96,6 +96,7 @@
> debugsetparents
> debugstate
> debugsub
> + debugsuccessorssets
> debugwalk
> debugwireargs
>
> @@ -247,6 +248,7 @@
> debugsetparents:
> debugstate: nodates, datesort
> debugsub: rev
> + debugsuccessorssets:
> debugwalk: include, exclude
> debugwireargs: three, four, five, ssh, remotecmd, insecure
> graft: rev, continue, edit, log, currentdate, currentuser, date, user, tool, dry-run
> diff --git a/tests/test-obsolete-divergent.t b/tests/test-obsolete-divergent.t
> new file mode 100644
> --- /dev/null
> +++ b/tests/test-obsolete-divergent.t
> @@ -0,0 +1,398 @@
> +Test file dedicated 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 > obs.py << EOF
> + > import mercurial.obsolete
> + > mercurial.obsolete._enabled = True
> + > EOF
> + $ cat >> $HGRCPATH << EOF
> + > [ui]
> + > logtemplate = {rev}:{node|short} {desc}\n
> + > [extensions]
> + > obs=${TESTTMP}/obs.py
> + > [alias]
> + > debugobsolete = debugobsolete -d '0 0'
> + > [phases]
> + > publish=False
> + > EOF
> +
> +
> + $ 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
> + 82623d38b9ba
> + 392fd25390da
> + 82623d38b9ba
> + 82623d38b9ba
> + 392fd25390da
> + 392fd25390da
> + $ 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
> + $ 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
> + 82623d38b9ba
> + 392fd25390da
> + 82623d38b9ba
> + 82623d38b9ba
> + 392fd25390da
> + 392fd25390da
> + $ 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
> + $ 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
> +
> +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
> +
> +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
> +
> +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
> +
> + $ cd ..
> +
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
More information about the Mercurial-devel
mailing list