[PATCH 1 of 5] obsolete: compute successors set
Pierre-Yves David
pierre-yves.david at ens-lyon.org
Fri Nov 9 19:23:44 CST 2012
# 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 ..
+
More information about the Mercurial-devel
mailing list