[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