hgext/evolve.py
author Denis Laxalde <denis.laxalde@logilab.fr>
Thu, 22 Nov 2012 11:30:36 +0100
branchcompat-hg2.3
changeset 620 232536f5c987
parent 619 f50f8da7a077
child 621 e50a5d9a6cbf
child 623 07d813af96c4
permissions -rw-r--r--
use comments to combine commit messages in fold

# Copyright 2011 Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
#                Logilab SA        <contact@logilab.fr>
#                Pierre-Yves David <pierre-yves.david@ens-lyon.org>
#                Patrick Mezard <patrick@mezard.eu>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.

'''Extends Mercurial feature related to Changeset Evolution

This extension provides several commands to mutate history and deal with
issues it may raise.

It also:

    - enables the "Changeset Obsolescence" feature of mercurial,
    - alters core commands and extensions that rewrite history to use
      this feature,
    - improves some aspect of the early implementation in 2.3
'''

testedwith = '2.3 2.3.1 2.3.2'
buglink = 'https://bitbucket.org/marmoute/mutable-history/issues'


import random

from mercurial import util

try:
    from mercurial import obsolete
    if not obsolete._enabled:
        obsolete._enabled = True
except ImportError:
    raise util.Abort('Evolve extension requires Mercurial 2.3 (or later)')

try:
    getattr(obsolete, 'getrevs') # 2.4 specific
    raise util.Abort('Your version of Mercurial is too recent for this '
                     'version of evolve',
                     hint="upgrade your evolve")
except AttributeError:
    pass


from mercurial import bookmarks
from mercurial import cmdutil
from mercurial import commands
from mercurial import context
from mercurial import copies
from mercurial import discovery
from mercurial import error
from mercurial import extensions
from mercurial import hg
from mercurial import localrepo
from mercurial import lock as lockmod
from mercurial import merge
from mercurial import node
from mercurial import phases
from mercurial import revset
from mercurial import scmutil
from mercurial import templatekw
from mercurial.i18n import _
from mercurial.commands import walkopts, commitopts, commitopts2
from mercurial.node import nullid

import mercurial.hgweb.hgweb_mod



# This extension contains the following code
#
# - Extension Helper code
# - Obsolescence cache
# - ...
# - Older format compat



#####################################################################
### Extension helper                                              ###
#####################################################################

class exthelper(object):
    """Helper for modular extension setup

    A single helper should be instanciated for each extension. Helper
    methods are then used as decorator for various purpose.

    All decorators return the original function and may be chained.
    """

    def __init__(self):
        self._uicallables = []
        self._extcallables = []
        self._repocallables = []
        self._revsetsymbols = []
        self._templatekws = []
        self._commandwrappers = []
        self._extcommandwrappers = []
        self._functionwrappers = []
        self._duckpunchers = []

    def final_uisetup(self, ui):
        """Method to be used as the extension uisetup

        The following operations belong here:

        - Changes to ui.__class__ . The ui object that will be used to run the
          command has not yet been created. Changes made here will affect ui
          objects created after this, and in particular the ui that will be
          passed to runcommand
        - Command wraps (extensions.wrapcommand)
        - Changes that need to be visible to other extensions: because
          initialization occurs in phases (all extensions run uisetup, then all
          run extsetup), a change made here will be visible to other extensions
          during extsetup
        - Monkeypatch or wrap function (extensions.wrapfunction) of dispatch
          module members
        - Setup of pre-* and post-* hooks
        - pushkey setup
        """
        for cont, funcname, func in self._duckpunchers:
            setattr(cont, funcname, func)
        for command, wrapper in self._commandwrappers:
            extensions.wrapcommand(commands.table, command, wrapper)
        for cont, funcname, wrapper in self._functionwrappers:
            extensions.wrapfunction(cont, funcname, wrapper)
        for c in self._uicallables:
            c(ui)

    def final_extsetup(self, ui):
        """Method to be used as a the extension extsetup

        The following operations belong here:

        - Changes depending on the status of other extensions. (if
          extensions.find('mq'))
        - Add a global option to all commands
        - Register revset functions
        """
        knownexts = {}
        for name, symbol in self._revsetsymbols:
            revset.symbols[name] = symbol
        for name, kw in self._templatekws:
            templatekw.keywords[name] = kw
        for ext, command, wrapper in self._extcommandwrappers:
            if ext not in knownexts:
                e = extensions.find(ext)
                if e is None:
                    raise util.Abort('extension %s not found' % ext)
                knownexts[ext] = e.cmdtable
            extensions.wrapcommand(knownexts[ext], commands, wrapper)
        for c in self._extcallables:
            c(ui)

    def final_reposetup(self, ui, repo):
        """Method to be used as a the extension reposetup

        The following operations belong here:

        - All hooks but pre-* and post-*
        - Modify configuration variables
        - Changes to repo.__class__, repo.dirstate.__class__
        """
        for c in self._repocallables:
            c(ui, repo)

    def uisetup(self, call):
        """Decorated function will be executed during uisetup

        example::

            @eh.uisetup
            def setupbabar(ui):
                print 'this is uisetup!'
        """
        self._uicallables.append(call)
        return call

    def extsetup(self, call):
        """Decorated function will be executed during extsetup

        example::

            @eh.extsetup
            def setupcelestine(ui):
                print 'this is extsetup!'
        """
        self._uicallables.append(call)
        return call

    def reposetup(self, call):
        """Decorated function will be executed during reposetup

        example::

            @eh.reposetup
            def setupzephir(ui, repo):
                print 'this is reposetup!'
        """
        self._repocallables.append(call)
        return call

    def revset(self, symbolname):
        """Decorated function is a revset symbol

        The name of the symbol must be given as the decorator argument.
        The symbol is added during `extsetup`.

        example::

            @eh.revset('hidden')
            def revsetbabar(repo, subset, x):
                args = revset.getargs(x, 0, 0, 'babar accept no argument')
                return [r for r in subset if 'babar' in repo[r].description()]
        """
        def dec(symbol):
            self._revsetsymbols.append((symbolname, symbol))
            return symbol
        return dec


    def templatekw(self, keywordname):
        """Decorated function is a revset keyword

        The name of the keyword must be given as the decorator argument.
        The symbol is added during `extsetup`.

        example::

            @eh.templatekw('babar')
            def kwbabar(ctx):
                return 'babar'
        """
        def dec(keyword):
            self._templatekws.append((keywordname, keyword))
            return keyword
        return dec

    def wrapcommand(self, command, extension=None):
        """Decorated function is a command wrapper

        The name of the command must be given as the decorator argument.
        The wrapping is installed during `uisetup`.

        If the second option `extension` argument is provided, the wrapping
        will be applied in the extension commandtable. This argument must be a
        string that will be searched using `extension.find` if not found and
        Abort error is raised. If the wrapping applies to an extension, it is
        installed during `extsetup`

        example::

            @eh.wrapcommand('summary')
            def wrapsummary(orig, ui, repo, *args, **kwargs):
                ui.note('Barry!')
                return orig(ui, repo, *args, **kwargs)

        """
        def dec(wrapper):
            if extension is None:
                self._commandwrappers.append((command, wrapper))
            else:
                self._extcommandwrappers.append((extension, command, wrapper))
            return wrapper
        return dec

    def wrapfunction(self, container, funcname):
        """Decorated function is a function wrapper

        This function takes two arguments, the container and the name of the
        function to wrap. The wrapping is performed during `uisetup`.
        (there is no extension support)

        example::

            @eh.function(discovery, 'checkheads')
            def wrapfunction(orig, *args, **kwargs):
                ui.note('His head smashed in and his heart cut out')
                return orig(*args, **kwargs)
        """
        def dec(wrapper):
            self._functionwrappers.append((container, funcname, wrapper))
            return wrapper
        return dec

    def addattr(self, container, funcname):
        """Decorated function is to be added to the container

        This function takes two arguments, the container and the name of the
        function to wrap. The wrapping is performed during `uisetup`.

        example::

            @eh.function(context.changectx, 'babar')
            def babar(ctx):
                return 'babar' in ctx.description
        """
        def dec(func):
            self._duckpunchers.append((container, funcname, func))
            return func
        return dec

eh = exthelper()
uisetup = eh.final_uisetup
extsetup = eh.final_extsetup
reposetup = eh.final_reposetup

#####################################################################
### Critical fix                                                  ###
#####################################################################

@eh.wrapfunction(mercurial.obsolete, '_readmarkers')
def safereadmarkers(orig, data):
    """safe maker wrapper to remove nullid succesors

    Nullid successors was created by older version of evolve.
    """
    for marker in orig(data):
        if nullid in marker[1]:
            marker = (marker[0],
                      tuple(s for s in marker[1] if s != nullid),
                      marker[2],
                      marker[3])
        yield marker


#####################################################################
### Obsolescence Caching Logic                                    ###
#####################################################################

# IN CORE fb72eec7efd8

# Obsolescence related logic can be very slow if we don't have efficient cache.
#
# This section implements a cache mechanism that did not make it into core for
# time reason. It stores meaningful set of revisions related to obsolescence
# (obsolete, unstable, etc.)
#
# Here is:
#
# - Computation of meaningful sets
# - Cache access logic,
# - Cache invalidation logic,
# - revset and ctx using this cache.
#


### Computation of meaningful set
#
# Most set can be computed with "simple" revset.

#: { set name -> function to compute this set } mapping
#:   function take a single "repo" argument.
#:
#: Use the `cachefor` decorator to register new cache function
try:
    cachefuncs = obsolete.cachefuncs
    cachefor = obsolete.cachefor
    getobscache = obsolete.getobscache
    clearobscaches = obsolete.clearobscaches
except AttributeError:
    cachefuncs = {}

    def cachefor(name):
        """Decorator to register a function as computing the cache for a set"""
        def decorator(func):
            assert name not in cachefuncs
            cachefuncs[name] = func
            return func
        return decorator

    @cachefor('obsolete')
    def _computeobsoleteset(repo):
        """the set of obsolete revisions"""
        obs = set()
        nm = repo.changelog.nodemap
        for prec in repo.obsstore.precursors:
            rev = nm.get(prec)
            if rev is not None:
                obs.add(rev)
        return set(repo.revs('%ld - public()', obs))

    @cachefor('unstable')
    def _computeunstableset(repo):
        """the set of non obsolete revisions with obsolete parents"""
        return set(repo.revs('(obsolete()::) - obsolete()'))

    @cachefor('suspended')
    def _computesuspendedset(repo):
        """the set of obsolete parents with non obsolete descendants"""
        return set(repo.revs('obsolete() and obsolete()::unstable()'))

    @cachefor('extinct')
    def _computeextinctset(repo):
        """the set of obsolete parents without non obsolete descendants"""
        return set(repo.revs('obsolete() - obsolete()::unstable()'))

    @eh.wrapfunction(obsolete.obsstore, '__init__')
    def _initobsstorecache(orig, obsstore, *args, **kwargs):
        """add a cache attribute to obsstore"""
        obsstore.caches = {}
        return orig(obsstore, *args, **kwargs)

### Cache access

    def getobscache(repo, name):
        """Return the set of revision that belong to the <name> set

        Such access may compute the set and cache it for future use"""
        if not repo.obsstore:
            return ()
        if name not in repo.obsstore.caches:
            repo.obsstore.caches[name] = cachefuncs[name](repo)
        return repo.obsstore.caches[name]

### Cache clean up
#
# To be simple we need to invalidate obsolescence cache when:
#
# - new changeset is added:
# - public phase is changed
# - obsolescence marker are added
# - strip is used a repo


    def clearobscaches(repo):
        """Remove all obsolescence related cache from a repo

        This remove all cache in obsstore is the obsstore already exist on the
        repo.

        (We could be smarter here)"""
        if 'obsstore' in repo._filecache:
            repo.obsstore.caches.clear()

    @eh.wrapfunction(localrepo.localrepository, 'addchangegroup')  # new changeset
    @eh.wrapfunction(phases, 'retractboundary')  # phase movement
    @eh.wrapfunction(phases, 'advanceboundary')  # phase movement
    @eh.wrapfunction(localrepo.localrepository, 'destroyed')  # strip
    def wrapclearcache(orig, repo, *args, **kwargs):
        try:
            return orig(repo, *args, **kwargs)
        finally:
            # we are a bit wide here
            # we could restrict to:
            # advanceboundary + phase==public
            # retractboundary + phase==draft
            clearobscaches(repo)

    @eh.wrapfunction(obsolete.obsstore, 'add')  # new marker
    def clearonadd(orig, obsstore, *args, **kwargs):
        try:
            return orig(obsstore, *args, **kwargs)
        finally:
            obsstore.caches.clear()

### Use the case
# Function in core that could benefic from the cache are overwritten by cache using version

# changectx method

    @eh.addattr(context.changectx, 'unstable')
    def unstable(ctx):
        """is the changeset unstable (have obsolete ancestor)"""
        if ctx.node() is None:
            return False
        return ctx.rev() in getobscache(ctx._repo, 'unstable')


    @eh.addattr(context.changectx, 'extinct')
    def extinct(ctx):
        """is the changeset extinct by other"""
        if ctx.node() is None:
            return False
        return ctx.rev() in getobscache(ctx._repo, 'extinct')

# revset

    @eh.revset('obsolete')
    def revsetobsolete(repo, subset, x):
        """``obsolete()``
        Changeset is obsolete.
        """
        args = revset.getargs(x, 0, 0, 'obsolete takes no argument')
        obsoletes = getobscache(repo, 'obsolete')
        return [r for r in subset if r in obsoletes]

    @eh.revset('unstable')
    def revsetunstable(repo, subset, x):
        """``unstable()``
        Unstable changesets are non-obsolete with obsolete ancestors.
        """
        args = revset.getargs(x, 0, 0, 'unstable takes no arguments')
        unstables = getobscache(repo, 'unstable')
        return [r for r in subset if r in unstables]

    @eh.revset('extinct')
    def revsetextinct(repo, subset, x):
        """``extinct()``
        Obsolete changesets with obsolete descendants only.
        """
        args = revset.getargs(x, 0, 0, 'extinct takes no arguments')
        extincts = getobscache(repo, 'extinct')
        return [r for r in subset if r in extincts]

#####################################################################
### Complete troubles computation logic                           ###
#####################################################################

# there is two kind of trouble not handled by core right now:
# - bumped: (successors for public changeset)
# - divergent: (two changeset try to succeed to the same precursors)
#
# This section add support for those two addition trouble
#
# - Cache computation
# - revset and ctx method
# - push warning

### Cache computation
latediff = 1  # flag to prevent taking late comer fix into account

@cachefor('bumped')
def _computebumpedset(repo):
    """the set of rev trying to obsolete public revision"""
    candidates = _allsuccessors(repo, repo.revs('public()'),
                                                haltonflags=latediff)
    query = '%ld - obsolete() - public()'
    return set(repo.revs(query, candidates))

@cachefor('divergent')
def _computedivergentset(repo):
    """the set of rev trying to obsolete public revision"""
    divergent = set()
    obsstore = repo.obsstore
    newermap = {}
    for ctx in repo.set('(not public()) - obsolete()'):
        mark = obsstore.successors.get(ctx.node(), ())
        toprocess = set(mark)
        while toprocess:
            prec = toprocess.pop()[0]
            if prec not in newermap:
                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, ()))
    return divergent

### changectx method

@eh.addattr(context.changectx, 'latecomer')
@eh.addattr(context.changectx, 'bumped')
def bumped(ctx):
    """is the changeset bumped (Try to succeed to public change)"""
    if ctx.node() is None:
        return False
    return ctx.rev() in getobscache(ctx._repo, 'bumped')

@eh.addattr(context.changectx, 'conflicting')
@eh.addattr(context.changectx, 'divergent')
def divergent(ctx):
    """is the changeset divergent (Try to succeed to public change)"""
    if ctx.node() is None:
        return False
    return ctx.rev() in getobscache(ctx._repo, 'divergent')

### revset symbol

@eh.revset('latecomer')
@eh.revset('bumped')
def revsetbumped(repo, subset, x):
    """``bumped()``
    Changesets marked as successors of public changesets.
    """
    args = revset.getargs(x, 0, 0, 'bumped takes no arguments')
    lates = getobscache(repo, 'bumped')
    return [r for r in subset if r in lates]

@eh.revset('conflicting')
@eh.revset('divergent')
def revsetdivergent(repo, subset, x):
    """``divergent()``
    Changesets marked as successors of a same changeset.
    """
    args = revset.getargs(x, 0, 0, 'divergent takes no arguments')
    conf = getobscache(repo, 'divergent')
    return [r for r in subset if r in conf]



### Discovery wrapping

@eh.wrapfunction(discovery, 'checkheads')
def wrapcheckheads(orig, repo, remote, outgoing, *args, **kwargs):
    """wrap mercurial.discovery.checkheads

    * prevent bumped and unstable to be pushed
    """
    # do not push instability
    for h in outgoing.missingheads:
        # Checking heads is enough, obsolete descendants are either
        # obsolete or unstable.
        ctx = repo[h]
        if ctx.bumped():
            raise util.Abort(_("push includes a bumped changeset: %s!")
                             % ctx)
        if ctx.divergent():
            raise util.Abort(_("push includes a divergent changeset: %s!")
                             % ctx)
    return orig(repo, remote, outgoing, *args, **kwargs)

#####################################################################
### Filter extinct changesets from common operations              ###
#####################################################################

@eh.wrapfunction(merge, 'update')
def wrapmergeupdate(orig, repo, node, *args, **kwargs):
    """ensure we don't automatically update on hidden changeset"""
    if node is None:
        # tip of current branch
        branch = repo[None].branch()
        node = repo.revs('last((.:: and branch(%s)) - hidden())', branch)[0]
    return orig(repo, node, *args, **kwargs)

@eh.wrapfunction(localrepo.localrepository, 'branchtip')
def obsbranchtip(orig, repo, branch):
    """ensure "stable" reference does not end on a hidden changeset"""
    if not getattr(repo, '_dofilterbranchtip', True):
        return orig(repo, branch)
    result = ()
    heads = repo.branchmap().get(branch, ())
    if heads:
        result = list(repo.set('last(heads(branch(%n) - hidden()))', heads[0]))
    if not result:
        raise error.RepoLookupError(_("unknown branch '%s'") % branch)
    return result[0].node()


@eh.wrapfunction(mercurial.hgweb.hgweb_mod.hgweb, '__init__')
@eh.wrapfunction(mercurial.hgweb.hgweb_mod.hgweb, 'refresh')
def nofilter(orig, hgweb, *args, **kwargs):
    orig(hgweb, *args, **kwargs)
    hgweb.repo._dofilterbranchtip = False


#####################################################################
### Additional Utilities                                          ###
#####################################################################

# This section contains a lot of small utility function and method

# - Function to create markers
# - useful alias pstatus and pdiff (should probably go in evolve)
# - "troubles" method on changectx
# - function to travel throught the obsolescence graph
# - function to find useful changeset to stabilize

### Marker Create
# NOW IN CORE f85816af6294
try:
    createmarkers = obsolete.createmarkers
except AttributeError:
    def createmarkers(repo, relations, metadata=None, flag=0):
        """Add obsolete markers between changeset in a repo

        <relations> must be an iterable of (<old>, (<new>, ...)) tuple.
        `old` and `news` are changectx.

        Current user and date are used except if specified otherwise in the
        metadata attribute.

        /!\ assume the repo have been locked by the user /!\
        """
        # prepare metadata
        if metadata is None:
            metadata = {}
        if 'date' not in metadata:
            metadata['date'] = '%i %i' % util.makedate()
        if 'user' not in metadata:
            metadata['user'] = repo.ui.username()
        # check future marker
        tr = repo.transaction('add-obsolescence-marker')
        try:
            for prec, sucs in relations:
                if not prec.mutable():
                    raise util.Abort("cannot obsolete immutable changeset: %s" % prec)
                nprec = prec.node()
                nsucs = tuple(s.node() for s in sucs)
                if nprec in nsucs:
                    raise util.Abort("changeset %s cannot obsolete himself" % prec)
                repo.obsstore.create(tr, nprec, nsucs, flag, metadata)
                clearobscaches(repo)
            tr.close()
        finally:
            tr.release()


### Useful alias

@eh.uisetup
def _installalias(ui):
    if ui.config('alias', 'pstatus', None) is None:
        ui.setconfig('alias', 'pstatus', 'status --rev .^')
    if ui.config('alias', 'pdiff', None) is None:
        ui.setconfig('alias', 'pdiff', 'diff --rev .^')
    if ui.config('alias', 'olog', None) is None:
        ui.setconfig('alias', 'olog', "log -r 'precursors(.)' --hidden")
    if ui.config('alias', 'odiff', None) is None:
        ui.setconfig('alias', 'odiff', "diff --rev 'limit(precursors(.),1)' --rev .")

# - "troubles" method on changectx

@eh.addattr(context.changectx, 'troubles')
def troubles(ctx):
    """Return a tuple listing all the troubles that affect a changeset

    Troubles may be "unstable", "bumped" or "divergent".
    """
    troubles = []
    if ctx.unstable():
        troubles.append('unstable')
    if ctx.bumped():
        troubles.append('bumped')
    if ctx.divergent():
        troubles.append('divergent')
    return tuple(troubles)

### Troubled revset symbol

@eh.revset('troubled')
def revsetbumped(repo, subset, x):
    """``troubled()``
    Changesets with troubles.
    """
    _ = revset.getargs(x, 0, 0, 'troubled takes no arguments')
    return repo.revs('%ld and (unstable() + bumped() + divergent())',
                     subset)


### Obsolescence graph

# XXX SOME MAJOR CLEAN UP TO DO HERE XXX

def _precursors(repo, s):
    """Precursor of a changeset"""
    cs = set()
    nm = repo.changelog.nodemap
    markerbysubj = repo.obsstore.successors
    for r in s:
        for p in markerbysubj.get(repo[r].node(), ()):
            pr = nm.get(p[0])
            if pr is not None:
                cs.add(pr)
    return cs

def _allprecursors(repo, s):  # XXX we need a better naming
    """transitive precursors of a subset"""
    toproceed = [repo[r].node() for r in s]
    seen = set()
    allsubjects = repo.obsstore.successors
    while toproceed:
        nc = toproceed.pop()
        for mark in allsubjects.get(nc, ()):
            np = mark[0]
            if np not in seen:
                seen.add(np)
                toproceed.append(np)
    nm = repo.changelog.nodemap
    cs = set()
    for p in seen:
        pr = nm.get(p)
        if pr is not None:
            cs.add(pr)
    return cs

def _successors(repo, s):
    """Successors of a changeset"""
    cs = set()
    nm = repo.changelog.nodemap
    markerbyobj = repo.obsstore.precursors
    for r in s:
        for p in markerbyobj.get(repo[r].node(), ()):
            for sub in p[1]:
                sr = nm.get(sub)
                if sr is not None:
                    cs.add(sr)
    return cs

def _allsuccessors(repo, s, haltonflags=0):  # XXX we need a better naming
    """transitive successors of a subset

    haltonflags allows to provide flags which prevent the evaluation of a
    marker.  """
    toproceed = [repo[r].node() for r in s]
    seen = set()
    allobjects = repo.obsstore.precursors
    while toproceed:
        nc = toproceed.pop()
        for mark in allobjects.get(nc, ()):
            if mark[2] & haltonflags:
                continue
            for sub in mark[1]:
                if sub == nullid:
                    continue # should not be here!
                if sub not in seen:
                    seen.add(sub)
                    toproceed.append(sub)
    nm = repo.changelog.nodemap
    cs = set()
    for s in seen:
        sr = nm.get(s)
        if sr is not None:
            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]




#####################################################################
### Extending revset and template                                 ###
#####################################################################

# this section add several useful revset symbol not yet in core.
# they are subject to changes


if 'hidden' not in revset.symbols:
    # in 2.3+
    @eh.revset('hidden')
    def revsethidden(repo, subset, x):
        """``hidden()``
        Changeset is hidden.
        """
        args = revset.getargs(x, 0, 0, 'hidden takes no argument')
        return [r for r in subset if r in repo.hiddenrevs]

### XXX I'm not sure this revset is useful
@eh.revset('suspended')
def revsetsuspended(repo, subset, x):
    """``suspended()``
    Obsolete changesets with non-obsolete descendants.
    """
    args = revset.getargs(x, 0, 0, 'suspended takes no arguments')
    suspended = getobscache(repo, 'suspended')
    return [r for r in subset if r in suspended]


@eh.revset('precursors')
def revsetprecursors(repo, subset, x):
    """``precursors(set)``
    Immediate precursors of changesets in set.
    """
    s = revset.getset(repo, range(len(repo)), x)
    cs = _precursors(repo, s)
    return [r for r in subset if r in cs]


@eh.revset('allprecursors')
def revsetallprecursors(repo, subset, x):
    """``allprecursors(set)``
    Transitive precursors of changesets in set.
    """
    s = revset.getset(repo, range(len(repo)), x)
    cs = _allprecursors(repo, s)
    return [r for r in subset if r in cs]


@eh.revset('successors')
def revsetsuccessors(repo, subset, x):
    """``successors(set)``
    Immediate successors of changesets in set.
    """
    s = revset.getset(repo, range(len(repo)), x)
    cs = _successors(repo, s)
    return [r for r in subset if r in cs]

@eh.revset('allsuccessors')
def revsetallsuccessors(repo, subset, x):
    """``allsuccessors(set)``
    Transitive successors of changesets in set.
    """
    s = revset.getset(repo, range(len(repo)), x)
    cs = _allsuccessors(repo, s)
    return [r for r in subset if r in cs]

### template keywords
# XXX it does not handle troubles well :-/

@eh.templatekw('obsolete')
def obsoletekw(repo, ctx, templ, **args):
    """:obsolete: String. The obsolescence level of the node, could be
    ``stable``, ``unstable``, ``suspended`` or ``extinct``.
    """
    rev = ctx.rev()
    if ctx.obsolete():
        if ctx.extinct():
            return 'extinct'
        else:
            return 'suspended'
    elif ctx.unstable():
        return 'unstable'
    return 'stable'

#####################################################################
### Various trouble warning                                       ###
#####################################################################

# This section take care of issue warning to the user when troubles appear

@eh.wrapcommand("update")
@eh.wrapcommand("pull")
def wrapmayobsoletewc(origfn, ui, repo, *args, **opts):
    """Warn that the working directory parent is an obsolete changeset"""
    res = origfn(ui, repo, *args, **opts)
    if repo['.'].obsolete():
        ui.warn(_('Working directory parent is obsolete\n'))
    return res

# XXX this could wrap transaction code
# XXX (but this is a bit a layer violation)
@eh.wrapcommand("commit")
@eh.wrapcommand("push")
@eh.wrapcommand("pull")
@eh.wrapcommand("graft")
@eh.wrapcommand("phase")
@eh.wrapcommand("unbundle")
def warnobserrors(orig, ui, repo, *args, **kwargs):
    """display warning is the command resulted in more instable changeset"""
    priorunstables = len(repo.revs('unstable()'))
    priorbumpeds = len(repo.revs('bumped()'))
    priordivergents = len(repo.revs('divergent()'))
    ret = orig(ui, repo, *args, **kwargs)
    # workaround phase stupidity
    phases._filterunknown(ui, repo.changelog, repo._phasecache.phaseroots)
    newunstables = len(repo.revs('unstable()')) - priorunstables
    newbumpeds = len(repo.revs('bumped()')) - priorbumpeds
    newdivergents = len(repo.revs('divergent()')) - priordivergents
    if newunstables > 0:
        ui.warn(_('%i new unstable changesets\n') % newunstables)
    if newbumpeds > 0:
        ui.warn(_('%i new bumped changesets\n') % newbumpeds)
    if newdivergents > 0:
        ui.warn(_('%i new divergent changesets\n') % newdivergents)
    return ret

@eh.reposetup
def _repostabilizesetup(ui, repo):
    """Add a hint for "hg evolve" when troubles make push fails
    """
    if not repo.local():
        return

    opush = repo.push

    class evolvingrepo(repo.__class__):
        def push(self, remote, *args, **opts):
            """wrapper around pull that pull obsolete relation"""
            try:
                result = opush(remote, *args, **opts)
            except util.Abort, ex:
                hint = _("use 'hg evolve' to get a stable history "
                         "or --force to ignore warnings")
                if (len(ex.args) >= 1
                    and ex.args[0].startswith('push includes ')
                    and ex.hint is None):
                    ex.hint = hint
                raise
            return result
    repo.__class__ = evolvingrepo

@eh.wrapcommand("summary")
def obssummary(orig, ui, repo, *args, **kwargs):
    def write(fmt, count):
        s = fmt % count
        if count:
            ui.write(s)
        else:
            ui.note(s)

    ret = orig(ui, repo, *args, **kwargs)
    nbunstable = len(getobscache(repo, 'unstable'))
    nbbumped = len(getobscache(repo, 'bumped'))
    nbdivergent = len(getobscache(repo, 'unstable'))
    write('unstable: %i changesets\n', nbunstable)
    write('bumped: %i changesets\n', nbbumped)
    write('divergent: %i changesets\n', nbdivergent)
    return ret


#####################################################################
### Core Other extension compat                                   ###
#####################################################################

# This section make official history rewritter create obsolete marker


### commit --amend
# make commit --amend create obsolete marker
#
# The precursor is still strip from the repository.

# IN CORE 63e45aee46d4

if getattr(cmdutil, 'obsolete', None) is None:
    @eh.wrapfunction(cmdutil, 'amend')
    def wrapcmdutilamend(orig, ui, repo, commitfunc, old, *args, **kwargs):
        oldnode = old.node()
        new = orig(ui, repo, commitfunc, old, *args, **kwargs)
        if new != oldnode:
            lock = repo.lock()
            try:
                tr = repo.transaction('post-amend-obst')
                try:
                    meta = {
                        'date':  '%i %i' % util.makedate(),
                        'user': ui.username(),
                        }
                    repo.obsstore.create(tr, oldnode, [new], 0, meta)
                    tr.close()
                    clearobscaches(repo)
                finally:
                    tr.release()
            finally:
                lock.release()
        return new

### rebase
#
# - ignore obsolete changeset
# - create obsolete marker *instead of* striping

def buildstate(orig, repo, dest, rebaseset, *ags, **kws):
    """wrapper for rebase 's buildstate that exclude obsolete changeset"""

    rebaseset = repo.revs('%ld - extinct()', rebaseset)
    if not rebaseset:
        repo.ui.warn(_('whole rebase set is extinct and ignored.\n'))
        return {}
    root = min(rebaseset)
    if (not getattr(repo, '_rebasekeep', False)
        and not repo[root].mutable()):
        raise util.Abort(_("can't rebase immutable changeset %s") % repo[root],
                         hint=_('see hg help phases for details'))
    return orig(repo, dest, rebaseset, *ags, **kws)

def defineparents(orig, repo, rev, target, state, *args, **kwargs):
    rebasestate = getattr(repo, '_rebasestate', None)
    if rebasestate is not None:
        repo._rebasestate = dict(state)
        repo._rebasetarget = target
    return orig(repo, rev, target, state, *args, **kwargs)

def concludenode(orig, repo, rev, p1, *args, **kwargs):
    """wrapper for rebase 's concludenode that set obsolete relation"""
    newrev = orig(repo, rev, p1, *args, **kwargs)
    rebasestate = getattr(repo, '_rebasestate', None)
    if rebasestate is not None:
        if newrev is not None:
            nrev = repo[newrev].rev()
        else:
            nrev = p1
        repo._rebasestate[rev] = nrev
    return newrev

def cmdrebase(orig, ui, repo, *args, **kwargs):

    reallykeep = kwargs.get('keep', False)
    kwargs = dict(kwargs)
    kwargs['keep'] = True
    repo._rebasekeep = reallykeep

    # We want to mark rebased revision as obsolete and set their
    # replacements if any. Doing it in concludenode() prevents
    # aborting the rebase, and is not called with all relevant
    # revisions in --collapse case. Instead, we try to track the
    # rebase state structure by sampling/updating it in
    # defineparents() and concludenode(). The obsolete markers are
    # added from this state after a successful call.
    repo._rebasestate = {}
    repo._rebasetarget = None
    try:
        l = repo.lock()
        try:
            res = orig(ui, repo, *args, **kwargs)
            if not reallykeep:
                # Filter nullmerge or unrebased entries
                repo._rebasestate = dict(p for p in repo._rebasestate.iteritems()
                                         if p[1] >= 0)
                if not res and not kwargs.get('abort') and repo._rebasestate:
                    # Rebased revisions are assumed to be descendants of
                    # targetrev. If a source revision is mapped to targetrev
                    # or to another rebased revision, it must have been
                    # removed.
                    markers = []
                    if kwargs.get('collapse'):
                        # collapse assume revision disapear because they are all
                        # in the created revision
                        newrevs = set(repo._rebasestate.values())
                        newrevs.remove(repo._rebasetarget)
                        if newrevs:
                            # we create new revision.
                            # A single one by --collapse design
                            assert len(newrevs) == 1
                            new = tuple(repo[n] for n in newrevs)
                        else:
                            # every body died. no new changeset created
                            new = (repo[repo._rebasetarget],)
                        for rev, newrev in sorted(repo._rebasestate.items()):
                            markers.append((repo[rev], new))
                    else:
                        # no collapse assume revision disapear because they are
                        # contained in parent
                        for rev, newrev in sorted(repo._rebasestate.items()):
                            markers.append((repo[rev], (repo[newrev],)))
                    createmarkers(repo, markers)
            return res
        finally:
            l.release()
    finally:
        delattr(repo, '_rebasestate')
        delattr(repo, '_rebasetarget')

@eh.extsetup
def _rebasewrapping(ui):
    # warning about more obsolete
    try:
        rebase = extensions.find('rebase')
        if rebase:
            incore = getattr(rebase, 'obsolete', None) is not None
            if not incore:
                extensions.wrapcommand(rebase.cmdtable, "rebase", cmdrebase)
            extensions.wrapcommand(rebase.cmdtable, 'rebase', warnobserrors)
            if not incore:
                extensions.wrapfunction(rebase, 'buildstate', buildstate)
                extensions.wrapfunction(rebase, 'defineparents', defineparents)
                extensions.wrapfunction(rebase, 'concludenode', concludenode)
    except KeyError:
        pass  # rebase not found


#####################################################################
### Old Evolve extension content                                  ###
#####################################################################

# XXX need clean up and proper sorting in other section

### util function
#############################

def noderange(repo, revsets):
    """The same as revrange but return node"""
    return map(repo.changelog.node,
               scmutil.revrange(repo, revsets))

### changeset rewriting logic
#############################

def rewrite(repo, old, updates, head, newbases, commitopts):
    """Return (nodeid, created) where nodeid is the identifier of the
    changeset generated by the rewrite process, and created is True if
    nodeid was actually created. If created is False, nodeid
    references a changeset existing before the rewrite call.
    """
    if len(old.parents()) > 1: #XXX remove this unecessary limitation.
        raise error.Abort(_('cannot amend merge changesets'))
    base = old.p1()
    updatebookmarks = _bookmarksupdater(repo, old.node())

    wlock = repo.wlock()
    try:

        # commit a new version of the old changeset, including the update
        # collect all files which might be affected
        files = set(old.files())
        for u in updates:
            files.update(u.files())

        # Recompute copies (avoid recording a -> b -> a)
        copied = copies.pathcopies(base, head)


        # prune files which were reverted by the updates
        def samefile(f):
            if f in head.manifest():
                a = head.filectx(f)
                if f in base.manifest():
                    b = base.filectx(f)
                    return (a.data() == b.data()
                            and a.flags() == b.flags())
                else:
                    return False
            else:
                return f not in base.manifest()
        files = [f for f in files if not samefile(f)]
        # commit version of these files as defined by head
        headmf = head.manifest()
        def filectxfn(repo, ctx, path):
            if path in headmf:
                fctx = head[path]
                flags = fctx.flags()
                mctx = context.memfilectx(fctx.path(), fctx.data(),
                                          islink='l' in flags,
                                          isexec='x' in flags,
                                          copied=copied.get(path))
                return mctx
            raise IOError()
        if commitopts.get('message') and commitopts.get('logfile'):
            raise util.Abort(_('options --message and --logfile are mutually'
                               ' exclusive'))
        if commitopts.get('logfile'):
            message= open(commitopts['logfile']).read()
        elif commitopts.get('message'):
            message = commitopts['message']
        else:
            message = old.description()

        user = commitopts.get('user') or old.user()
        date = commitopts.get('date') or None # old.date()
        extra = dict(commitopts.get('extra', {}))
        extra['branch'] = head.branch()

        new = context.memctx(repo,
                             parents=newbases,
                             text=message,
                             files=files,
                             filectxfn=filectxfn,
                             user=user,
                             date=date,
                             extra=extra)

        if commitopts.get('edit'):
            new._text = cmdutil.commitforceeditor(repo, new, [])
        revcount = len(repo)
        newid = repo.commitctx(new)
        new = repo[newid]
        created = len(repo) != revcount
        if created:
            updatebookmarks(newid)
            # add evolution metadata
            markers = [(u, (new,)) for u in updates]
            markers.append((old, (new,)))
            createmarkers(repo, markers)
        else:
            # newid is an existing revision. It could make sense to
            # replace revisions with existing ones but probably not by
            # default.
            pass
    finally:
        wlock.release()

    return newid, created

class MergeFailure(util.Abort):
    pass

def relocate(repo, orig, dest):
    """rewrite <rev> on dest"""
    try:
        rebase = extensions.find('rebase')
        # dummy state to trick rebase node
        assert orig.p2().rev() == node.nullrev, 'no support yet'
        destbookmarks = repo.nodebookmarks(dest.node())
        cmdutil.duplicatecopies(repo, orig.node(), dest.node())
        nodesrc = orig.node()
        destphase = repo[nodesrc].phase()
        try:
            if rebase.rebasenode.func_code.co_argcount == 5:
                # rebasenode collapse argument was introduced by
                # d1afbf03e69a (2.3)
                r = rebase.rebasenode(repo, orig.node(), dest.node(),
                                      {node.nullrev: node.nullrev}, False)
            else:
                r = rebase.rebasenode(repo, orig.node(), dest.node(),
                                     {node.nullrev: node.nullrev})
            if r[-1]: #some conflict
                raise util.Abort(
                        'unresolved merge conflicts (see hg help resolve)')
            nodenew = rebase.concludenode(repo, orig.node(), dest.node(),
                                          node.nullid)
        except util.Abort, exc:
            class LocalMergeFailure(MergeFailure, exc.__class__):
                pass
            exc.__class__ = LocalMergeFailure
            raise
        oldbookmarks = repo.nodebookmarks(nodesrc)
        if nodenew is not None:
            phases.retractboundary(repo, destphase, [nodenew])
            createmarkers(repo, [(repo[nodesrc], (repo[nodenew],))])
            for book in oldbookmarks:
                repo._bookmarks[book] = nodenew
        else:
            createmarkers(repo, [(repo[nodesrc], ())])
            # Behave like rebase, move bookmarks to dest
            for book in oldbookmarks:
                repo._bookmarks[book] = dest.node()
        for book in destbookmarks: # restore bookmark that rebase move
            repo._bookmarks[book] = dest.node()
        if oldbookmarks or destbookmarks:
            bookmarks.write(repo)
        return nodenew
    except util.Abort:
        # Invalidate the previous setparents
        repo.dirstate.invalidate()
        raise

def _bookmarksupdater(repo, oldid):
    """Return a callable update(newid) updating the current bookmark
    and bookmarks bound to oldid to newid.
    """
    bm = bookmarks.readcurrent(repo)
    def updatebookmarks(newid):
        dirty = False
        if bm:
            repo._bookmarks[bm] = newid
            dirty = True
        oldbookmarks = repo.nodebookmarks(oldid)
        if oldbookmarks:
            for b in oldbookmarks:
                repo._bookmarks[b] = newid
            dirty = True
        if dirty:
            bookmarks.write(repo)
    return updatebookmarks

### new command
#############################
cmdtable = {}
command = cmdutil.command(cmdtable)

@command('^evolve|stabilize|evolve|solve',
    [('n', 'dry-run', False, 'do not perform actions, print what to be done'),
    ('A', 'any', False, 'evolve any troubled changeset'),
    ('c', 'continue', False, 'continue an interrupted evolution'), ],
    _('[OPTIONS]...'))
def evolve(ui, repo, **opts):
    """Solve trouble in your repository

    - rebase unstable changeset to make it stable again,
    - create proper diff from bumped changeset,
    - merge divergent changeset.

    By default, take the first troubles changeset that looks relevant.

    (The logic is still a bit fuzzy)

    - For unstable, that mean the first which could be rebased as child of the
      working directory parent revision or one of its descendants and rebase
      it.

    - For divergent this mean "." if applicable.

    With --any, evolve pick any troubled changeset to solve

    The working directory is updated to the newly created revision.
    """

    contopt = opts['continue']
    anyopt = opts['any']

    if contopt:
        if anyopt:
            raise util.Abort('can not specify both "--any" and "--continue"')
        graftcmd = commands.table['graft'][0]
        return graftcmd(ui, repo, old_obsolete=True, **{'continue': True})

    tr = _picknexttroubled(ui, repo, anyopt)
    if tr is None:
        troubled = repo.revs('troubled()')
        if troubled:
            ui.write_err(_('nothing to evolve here\n'))
            ui.status(_('(%i troubled changesets, do you want --any ?)\n')
                      % len(troubled))
            return 2
        else:
            ui.write_err(_('no troubled changeset\n'))
            return 1
    cmdutil.bailifchanged(repo)
    troubles = tr.troubles()
    if 'unstable' in troubles:
        return _solveunstable(ui, repo, tr, opts['dry_run'])
    elif 'bumped' in troubles:
        return _solvebumped(ui, repo, tr, opts['dry_run'])
    elif 'divergent' in troubles:
        return _solvedivergent(ui, repo, tr, opts['dry_run'])
    else:
        assert False  # WHAT? unknown troubles

def _picknexttroubled(ui, repo, pickany=False):
    """Pick a the next trouble changeset to solve"""
    tr = _stabilizableunstable(repo, repo['.'])
    if tr is None:
        wdp = repo['.']
        if 'divergent' in wdp.troubles():
            tr = wdp
    if tr is None and pickany:
        troubled = list(repo.set('unstable()'))
        if not troubled:
            troubled = list(repo.set('bumped()'))
        if not troubled:
            troubled = list(repo.set('divergent()'))
        if troubled:
            tr = troubled[0]

    return tr

def _stabilizableunstable(repo, pctx):
    """Return a changectx for an unstable changeset which can be
    stabilized on top of pctx or one of its descendants. None if none
    can be found.
    """
    def selfanddescendants(repo, pctx):
        yield pctx
        for ctx in pctx.descendants():
            yield ctx

    # Look for an unstable which can be stabilized as a child of
    # node. The unstable must be a child of one of node predecessors.
    for ctx in selfanddescendants(repo, pctx):
        unstables = list(repo.set('unstable() and children(allprecursors(%d))',
                                  ctx.rev()))
        if unstables:
            return unstables[0]
    return None

def _solveunstable(ui, repo, orig, dryrun=False):
    """Stabilize a unstable changeset"""
    obs = orig.parents()[0]
    if not obs.obsolete():
        obs = orig.parents()[1]
    assert obs.obsolete()
    newer = successorssets(repo, obs.node())
    # search of a parent which is not killed
    while not newer or newer == [()]:
        ui.debug("stabilize target %s is plain dead,"
                 " trying to stabilize on its parent")
        obs = obs.parents()[0]
        newer = successorssets(repo, obs.node())
    if len(newer) > 1:
        ui.write_err(_("conflict rewriting. can't choose destination\n"))
        return 2
    targets = newer[0]
    assert targets
    if len(targets) > 1:
        ui.write_err(_("does not handle splitted parent yet\n"))
        return 2
    target = targets[0]
    displayer = cmdutil.show_changeset(ui, repo, {'template': shorttemplate})
    target = repo[target]
    repo.ui.status(_('move:'))
    if not ui.quiet:
        displayer.show(orig)
    repo.ui.status(_('atop:'))
    if not ui.quiet:
        displayer.show(target)
    todo = 'hg rebase -r %s -d %s\n' % (orig, target)
    if dryrun:
        repo.ui.write(todo)
    else:
        repo.ui.note(todo)
        lock = repo.lock()
        try:
            relocate(repo, orig, target)
        except MergeFailure:
            repo.opener.write('graftstate', orig.hex() + '\n')
            repo.ui.write_err(_('evolve failed!\n'))
            repo.ui.write_err(_('fix conflict and run "hg evolve --continue"\n'))
            raise
        finally:
            lock.release()

def _solvebumped(ui, repo, bumped, dryrun=False):
    """Stabilize a bumped changeset"""
    # For now we deny bumped merge
    if len(bumped.parents()) > 1:
        raise util.Abort('late comer stabilization is confused by bumped'
                         ' %s being a merge' % bumped)
    prec = repo.set('last(allprecursors(%d) and public())', bumped).next()
    # For now we deny target merge
    if len(prec.parents()) > 1:
        raise util.Abort('late comer evolution is confused by precursors'
                         ' %s being a merge' % prec)

    displayer = cmdutil.show_changeset(ui, repo, {'template': shorttemplate})
    repo.ui.status(_('recreate:'))
    if not ui.quiet:
        displayer.show(bumped)
    repo.ui.status(_('atop:'))
    if not ui.quiet:
        displayer.show(prec)
    if dryrun:
        todo = 'hg rebase --rev %s --dest %s;\n' % (bumped, prec.p1())
        repo.ui.write(todo)
        repo.ui.write('hg update %s;\n' % prec)
        repo.ui.write('hg revert --all --rev %s;\n' % bumped)
        repo.ui.write('hg commit --msg "bumped update to %s"')
        return 0
    wlock = repo.wlock()
    try:
        newid = tmpctx = None
        tmpctx = bumped
        lock = repo.lock()
        try:
            bmupdate = _bookmarksupdater(repo, bumped.node())
            # Basic check for common parent. Far too complicated and fragile
            tr = repo.transaction('bumped-stabilize')
            try:
                if not list(repo.set('parents(%d) and parents(%d)', bumped, prec)):
                    # Need to rebase the changeset at the right place
                    repo.ui.status(_('rebasing to destination parent: %s\n') % prec.p1())
                    try:
                        tmpid = relocate(repo, bumped, prec.p1())
                        if tmpid is not None:
                            tmpctx = repo[tmpid]
                            createmarkers(repo, [(bumped, (tmpctx,))])
                    except MergeFailure:
                        repo.opener.write('graftstate', bumped.hex() + '\n')
                        repo.ui.write_err(_('evolution failed!\n'))
                        repo.ui.write_err(_('fix conflict and run "hg evolve --continue"\n'))
                        raise
                # Create the new commit context
                repo.ui.status(_('computing new diff\n'))
                files = set()
                copied = copies.pathcopies(prec, bumped)
                precmanifest = prec.manifest()
                for key, val in bumped.manifest().iteritems():
                    if precmanifest.pop(key, None) != val:
                        files.add(key)
                files.update(precmanifest)  # add missing files
                # commit it
                if files: # something to commit!
                    def filectxfn(repo, ctx, path):
                        if path in bumped:
                            fctx = bumped[path]
                            flags = fctx.flags()
                            mctx = context.memfilectx(fctx.path(), fctx.data(),
                                                      islink='l' in flags,
                                                      isexec='x' in flags,
                                                      copied=copied.get(path))
                            return mctx
                        raise IOError()
                    text = 'bumped update to %s:\n\n' % prec
                    text += bumped.description()

                    new = context.memctx(repo,
                                         parents=[prec.node(), node.nullid],
                                         text=text,
                                         files=files,
                                         filectxfn=filectxfn,
                                         user=bumped.user(),
                                         date=bumped.date(),
                                         extra=bumped.extra())

                    newid = repo.commitctx(new)
                if newid is None:
                    createmarkers(repo, [(tmpctx, ())])
                    newid = prec.node()
                else:
                    phases.retractboundary(repo, bumped.phase(), [newid])
                    createmarkers(repo, [(tmpctx, (repo[newid],))],
                                           flag=latediff)
                bmupdate(newid)
                tr.close()
                repo.ui.status(_('commited as %s\n') % node.short(newid))
            finally:
                tr.release()
        finally:
            lock.release()
        # reroute the working copy parent to the new changeset
        repo.dirstate.setparents(newid, node.nullid)
    finally:
        wlock.release()

def _solvedivergent(ui, repo, divergent, dryrun=False):
    base, others = divergentdata(divergent)
    if len(others) > 1:
        raise util.Abort("We do not handle split yet")
    other = others[0]
    if divergent.phase() <= phases.public:
        raise util.Abort("We can't resolve this conflict from the public side")
    if len(other.parents()) > 1:
        raise util.Abort("divergent changeset can't be a merge (yet)")
    if other.p1() not in divergent.parents():
        raise util.Abort("parents are not common (not handled yet)")

    displayer = cmdutil.show_changeset(ui, repo, {'template': shorttemplate})
    ui.status(_('merge:'))
    if not ui.quiet:
        displayer.show(divergent)
    ui.status(_('with: '))
    if not ui.quiet:
        displayer.show(other)
    ui.status(_('base: '))
    if not ui.quiet:
        displayer.show(base)
    if dryrun:
        ui.write('hg update -c %s &&\n' % divergent)
        ui.write('hg merge %s &&\n' % other)
        ui.write('hg commit -m "auto merge resolving conflict between '
                 '%s and %s"&&\n' % (divergent, other))
        ui.write('hg up -C %s &&\n' % base)
        ui.write('hg revert --all --rev tip &&\n')
        ui.write('hg commit -m "`hg log -r %s --template={desc}`";\n'
                 % divergent)
        return
    wlock = lock = None
    try:
        wlock = repo.wlock()
        lock = repo.lock()
        if divergent not in repo[None].parents():
            repo.ui.status(_('updating to "local" conflict\n'))
            hg.update(repo, divergent.rev())
        repo.ui.note(_('merging divergent changeset\n'))
        stats = merge.update(repo,
                             other.node(),
                             branchmerge=True,
                             force=False,
                             partial=None,
                             ancestor=base.node(),
                             mergeancestor=True)
        hg._showstats(repo, stats)
        if stats[3]:
            repo.ui.status(_("use 'hg resolve' to retry unresolved file merges "
                             "or 'hg update -C .' to abandon\n"))
        if stats[3] > 0:
            raise util.Abort('Merge conflict between several amendments, and this is not yet automated',
                hint="""/!\ You can try:
/!\ * manual merge + resolve => new cset X
/!\ * hg up to the parent of the amended changeset (which are named W and Z)
/!\ * hg revert --all -r X
/!\ * hg ci -m "same message as the amended changeset" => new cset Y
/!\ * hg kill -n Y W Z
""")
        tr = repo.transaction('stabilize-divergent')
        try:
            repo.dirstate.setparents(divergent.node(), node.nullid)
            oldlen = len(repo)
            amend(ui, repo)
            if oldlen == len(repo):
                new = divergent
                # no changes
            else:
                new = repo['.']
            createmarkers(repo, [(other, (new,))])
            phases.retractboundary(repo, other.phase(), [new.node()])
            tr.close()
        finally:
            tr.release()
    finally:
        lockmod.release(lock, wlock)


def divergentdata(ctx):
    """return base, other part of a conflict

    This only return the first one.

    XXX this woobly function won't survive XXX
    """
    for base in ctx._repo.set('reverse(precursors(%d))', ctx):
        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:
            return base, tuple(ctx._repo[o] for o in newer[0])
    raise KeyError('Base seem unknown. This case is not handled yet.')



shorttemplate = '[{rev}] {desc|firstline}\n'

@command('^gdown',
         [],
         '')
def cmdgdown(ui, repo):
    """update to parent an display summary lines"""
    wkctx = repo[None]
    wparents = wkctx.parents()
    if len(wparents) != 1:
        raise util.Abort('merge in progress')

    parents = wparents[0].parents()
    displayer = cmdutil.show_changeset(ui, repo, {'template': shorttemplate})
    if len(parents) == 1:
        p = parents[0]
        hg.update(repo, p.rev())
        displayer.show(p)
        return 0
    else:
        for p in parents:
            displayer.show(p)
        ui.warn(_('multiple parents, explicitly update to one\n'))
        return 1

@command('^gup',
         [],
         '')
def cmdup(ui, repo):
    """update to child an display summary lines"""
    wkctx = repo[None]
    wparents = wkctx.parents()
    if len(wparents) != 1:
        raise util.Abort('merge in progress')

    children = [ctx for ctx in wparents[0].children() if not ctx.obsolete()]
    displayer = cmdutil.show_changeset(ui, repo, {'template': shorttemplate})
    if not children:
        ui.warn(_('No non-obsolete children\n'))
        return 1
    if len(children) == 1:
        c = children[0]
        hg.update(repo, c.rev())
        displayer.show(c)
        return 0
    else:
        for c in children:
            displayer.show(c)
        ui.warn(_('Multiple non-obsolete children, explicitly update to one\n'))
        return 1

@command('^prune|obsolete|kill',
    [('n', 'new', [], _("successor changeset"))],
    _('[OPTION] REV...'))
def kill(ui, repo, *revs, **opts):
    """mark a changeset as obsolete

    This update the parent directory to a not-killed parent if the current
    working directory parent are killed.

    XXX bookmark support
    XXX handle merge
    XXX check immutable first
    """
    wlock = repo.wlock()
    try:
        lock = repo.lock()
        try:
            new = set(noderange(repo, opts['new']))
            targetnodes = set(noderange(repo, revs))
            if not targetnodes:
                raise util.Abort('nothing to prune')
            if new:
                sucs = tuple(repo[n] for n in new)
            else:
                sucs = ()
            markers = []
            for n in targetnodes:
                markers.append((repo[n], sucs))
            createmarkers(repo, markers)

            # update to an unkilled parent
            wdp = repo['.']
            newnode = wdp
            while newnode.obsolete():
                newnode = newnode.parents()[0]
            if newnode.node() != wdp.node():
                commands.update(ui, repo, newnode.rev())
                ui.status(_('working directory now at %s\n') % newnode)
        finally:
            lock.release()
    finally:
        wlock.release()

@command('^amend|refresh',
    [('A', 'addremove', None,
     _('mark new/missing files as added/removed before committing')),
    ('n', 'note', '', _('use text as commit message for this update')),
    ('c', 'change', '', _('specifies the changesets to amend (DEPRECATED)'), _('REV')),
    ('e', 'edit', False, _('invoke editor on commit messages')),
    ] + walkopts + commitopts + commitopts2,
    _('[OPTION]... [FILE]...'))
def amend(ui, repo, *pats, **opts):
    """combine a changeset with updates and replace it with a new one

    Commits a new changeset incorporating both the changes to the given files
    and all the changes from the current parent changeset into the repository.

    See :hg:`commit` for details about committing changes.

    If you don't specify -m, the parent's message will be reused.

    If you specify --change, amend additionally considers all
    changesets between the indicated changeset and the working copy
    parent as updates to be subsumed.

    Behind the scenes, Mercurial first commits the update as a regular child
    of the current parent. Then it creates a new commit on the parent's parents
    with the updated contents. Then it changes the working copy parent to this
    new combined changeset. Finally, the old changeset and its update are hidden
    from :hg:`log` (unless you use --hidden with log).

    Returns 0 on success, 1 if nothing changed.
    """

    # determine updates to subsume
    old = scmutil.revsingle(repo, opts.get('change') or '.')

    lock = repo.lock()
    try:
        wlock = repo.wlock()
        try:
            if old.phase() == phases.public:
                raise util.Abort(_("can not rewrite immutable changeset %s")
                                 % old)
            if not repo.revs('%d and (::.)', old):
                raise error.Abort(_('cannot amend non ancestor changeset'))
            tr = repo.transaction('amend')
            try:
                oldphase = old.phase()
                # commit current changes as update
                # code copied from commands.commit to avoid noisy messages
                ciopts = dict(opts)
                ciopts.pop('message', None)
                ciopts.pop('logfile', None)
                ciopts['message'] = opts.get('note') or ('amends %s' % old.hex())
                e = cmdutil.commiteditor
                def commitfunc(ui, repo, message, match, opts):
                    return repo.commit(message, opts.get('user'), opts.get('date'),
                                       match, editor=e)
                revcount = len(repo)
                tempid = cmdutil.commit(ui, repo, commitfunc, pats, ciopts)
                if len(repo) == revcount:
                    # No revision created
                    tempid = None

                # find all changesets to be considered updates
                head = repo['.']
                updatenodes = set(repo.changelog.nodesbetween(
                        roots=[old.node()], heads=[head.node()])[0])
                updatenodes.remove(old.node())
                okoptions = ['message', 'logfile', 'edit', 'user']
                if not updatenodes:
                    for o in okoptions:
                        if opts.get(o):
                            break
                    else:
                        raise error.Abort(_('no updates found'))
                updates = [repo[n] for n in updatenodes]

                # perform amend
                if opts.get('edit'):
                    opts['force_editor'] = True
                newid, created = rewrite(repo, old, updates, head,
                                         [old.p1().node(), old.p2().node()], opts)
                if created:
                    # reroute the working copy parent to the new changeset
                    phases.retractboundary(repo, oldphase, [newid])
                    repo.dirstate.setparents(newid, node.nullid)
                else:
                    # rewrite() recreated an existing revision, discard
                    # the intermediate revision if any. No need to update
                    # phases or parents.
                    if tempid is not None:
                        createmarkers(repo, [(repo[tempid], ())])
                    # XXX: need another message in collapse case.
                    tr.close()
                    raise error.Abort(_('no updates found'))
                tr.close()
            finally:
                tr.release()
        finally:
            wlock.release()
    finally:
        lock.release()

def _commitfiltered(repo, ctx, match):
    """Recommit ctx with changed files not in match. Return the new
    node identifier, or None if nothing changed.
    """
    base = ctx.p1()
    m, a, r = repo.status(base, ctx)[:3]
    allfiles = set(m + a + r)
    files = set(f for f in allfiles if not match(f))
    if files == allfiles:
        return None

    # Filter copies
    copied = copies.pathcopies(base, ctx)
    copied = dict((src, dst) for src, dst in copied.iteritems()
                  if dst in files)
    def filectxfn(repo, memctx, path):
        if path not in ctx:
            raise IOError()
        fctx = ctx[path]
        flags = fctx.flags()
        mctx = context.memfilectx(fctx.path(), fctx.data(),
                                  islink='l' in flags,
                                  isexec='x' in flags,
                                  copied=copied.get(path))
        return mctx

    new = context.memctx(repo,
                         parents=[base.node(), node.nullid],
                         text=ctx.description(),
                         files=files,
                         filectxfn=filectxfn,
                         user=ctx.user(),
                         date=ctx.date(),
                         extra=ctx.extra())
    # commitctx always create a new revision, no need to check
    newid = repo.commitctx(new)
    return newid

def _uncommitdirstate(repo, oldctx, match):
    """Fix the dirstate after switching the working directory from
    oldctx to a copy of oldctx not containing changed files matched by
    match.
    """
    ctx = repo['.']
    ds = repo.dirstate
    copies = dict(ds.copies())
    m, a, r = repo.status(oldctx.p1(), oldctx, match=match)[:3]
    for f in m:
        if ds[f] == 'r':
            # modified + removed -> removed
            continue
        ds.normallookup(f)

    for f in a:
        if ds[f] == 'r':
            # added + removed -> unknown
            ds.drop(f)
        elif ds[f] != 'a':
            ds.add(f)

    for f in r:
        if ds[f] == 'a':
            # removed + added -> normal
            ds.normallookup(f)
        elif ds[f] != 'r':
            ds.remove(f)

    # Merge old parent and old working dir copies
    oldcopies = {}
    for f in (m + a):
        src = oldctx[f].renamed()
        if src:
            oldcopies[f] = src[0]
    oldcopies.update(copies)
    copies = dict((dst, oldcopies.get(src, src))
                  for dst, src in oldcopies.iteritems())
    # Adjust the dirstate copies
    for dst, src in copies.iteritems():
        if (src not in ctx or dst in ctx or ds[dst] != 'a'):
            src = None
        ds.copy(src, dst)

@command('^uncommit',
    [('a', 'all', None, _('uncommit all changes when no arguments given')),
     ] + commands.walkopts,
    _('[OPTION]... [NAME]'))
def uncommit(ui, repo, *pats, **opts):
    """move changes from parent revision to working directory

    Changes to selected files in parent revision appear again as
    uncommitted changed in the working directory. A new revision
    without selected changes is created, becomes the new parent and
    obsoletes the previous one.

    The --include option specify pattern to uncommit
    The --exclude option specify pattern to keep in the commit

    Return 0 if changed files are uncommitted.
    """
    lock = repo.lock()
    try:
        wlock = repo.wlock()
        try:
            wctx = repo[None]
            if len(wctx.parents()) <= 0:
                raise util.Abort(_("cannot uncommit null changeset"))
            if len(wctx.parents()) > 1:
                raise util.Abort(_("cannot uncommit while merging"))
            old = repo['.']
            if old.phase() == phases.public:
                raise util.Abort(_("cannot rewrite immutable changeset"))
            if len(old.parents()) > 1:
                raise util.Abort(_("cannot uncommit merge changeset"))
            oldphase = old.phase()
            updatebookmarks = _bookmarksupdater(repo, old.node())
            # Recommit the filtered changeset
            newid = None
            if (pats or opts.get('include') or opts.get('exclude')
                or opts.get('all')):
                match = scmutil.match(old, pats, opts)
                newid = _commitfiltered(repo, old, match)
            if newid is None:
                raise util.Abort(_('nothing to uncommit'))
            # Move local changes on filtered changeset
            createmarkers(repo, [(old, (repo[newid],))])
            phases.retractboundary(repo, oldphase, [newid])
            repo.dirstate.setparents(newid, node.nullid)
            _uncommitdirstate(repo, old, match)
            updatebookmarks(newid)
            if not repo[newid].files():
                ui.warn(_("new changeset is empty\n"))
                ui.status(_('(use "hg kill ." to remove it)\n'))
        finally:
            wlock.release()
    finally:
        lock.release()

@eh.wrapcommand('commit')
def commitwrapper(orig, ui, repo, *arg, **kwargs):
    if kwargs.get('amend', False):
        lock = None
    else:
        lock = repo.lock()
    try:
        obsoleted = kwargs.get('obsolete', [])
        if obsoleted:
            obsoleted = repo.set('%lr', obsoleted)
        result = orig(ui, repo, *arg, **kwargs)
        if not result: # commit successed
            new = repo['-1']
            oldbookmarks = []
            markers = []
            for old in obsoleted:
                oldbookmarks.extend(repo.nodebookmarks(old.node()))
                markers.append((old, (new,)))
            if markers:
                createmarkers(repo, markers)
            for book in oldbookmarks:
                repo._bookmarks[book] = new.node()
            if oldbookmarks:
                bookmarks.write(repo)
        return result
    finally:
        if lock is not None:
            lock.release()

@command('^touch',
    [('r', 'rev', [], 'revision to update'),],
    # allow to choose the seed ?
    _('[-r] revs'))
def touch(ui, repo, *revs, **opts):
    """Create successors with exact same property but hash

    This is used to "resurrect" changesets
    """
    revs = list(revs)
    revs.extend(opts['rev'])
    if not revs:
        revs = ['.']
    revs = scmutil.revrange(repo, revs)
    if not revs:
        ui.write_err('no revision to touch\n')
        return 1
    if repo.revs('public() and %ld', revs):
        raise util.Abort("can't touch public revision")
    wlock = lock = None
    try:
        wlock = repo.wlock()
        lock = repo.lock()
        tr = repo.transaction('touch')
        try:
            for r in revs:
                ctx = repo[r]
                extra = ctx.extra().copy()
                extra['__touch-noise__'] = random.randint(0, 0xffffffff)
                new, _ = rewrite(repo, ctx, [], ctx,
                                 [ctx.p1().node(), ctx.p2().node()],
                                 commitopts={'extra': extra})
                createmarkers(repo, [(ctx, (repo[new],))])
                phases.retractboundary(repo, ctx.phase(), [new])
                if ctx in repo[None].parents():
                    repo.dirstate.setparents(new, node.nullid)
            tr.close()
        finally:
            tr.release()
    finally:
        lockmod.release(lock, wlock)

@command('^fold',
    [('r', 'rev', [], 'revisions to fold'),
    ],
    # allow to choose the seed ?
    _('[-r] revs'))
def fold(ui, repo, *revs, **opts):
    """Fold multiple revisions into a single one"""
    revs = list(revs)
    revs.extend(opts['rev'])
    if revs:
        revs = scmutil.revrange(repo, revs)
    if not revs:
        ui.write_err('no revision to fold\n')
        return 1
    roots = repo.revs('roots(%ld)', revs)
    if len(roots) > 1:
        raise util.Abort("set has multiple roots")
    root = repo[roots[0]]
    if root.phase() <= phases.public:
        raise util.Abort("can't fold public revisions")
    heads = repo.revs('heads(%ld)', revs)
    if len(heads) > 1:
        raise util.Abort("set has multiple heads")
    head = repo[heads[0]]
    wlock = lock = None
    try:
        wlock = repo.wlock()
        lock = repo.lock()
        tr = repo.transaction('touch')
        try:
            allctx = [repo[r] for r in revs]
            targetphase = max(c.phase() for c in allctx)
            msgs = ["HG: This is a fold of %d changesets." % len(allctx)]
            msgs += ["HG: Commit message of changeset %s.\n\n%s\n" %
                     (c.rev(), c.description()) for c in allctx]
            commitopts = {'message': "\n".join(msgs)}
            commitopts['edit'] = True
            newid, _ = rewrite(repo, root, allctx, head,
                             [root.p1().node(), root.p2().node()],
                             commitopts=commitopts)
            phases.retractboundary(repo, targetphase, [newid])
            createmarkers(repo, [(ctx, (repo[newid],))
                                 for ctx in allctx])
            tr.close()
        finally:
            tr.release()
        ui.status('%i changesets folded\n' % len(revs))
        if repo.revs('. and %ld', revs):
            hg.update(repo, newid)
    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):
    kwargs = dict(kwargs)
    revs = list(revs) + kwargs.get('rev', [])
    kwargs['rev'] = []
    obsoleted = kwargs.setdefault('obsolete', [])

    lock = repo.lock()
    try:
        if kwargs.get('old_obsolete'):
            if kwargs.get('continue'):
                obsoleted.extend(repo.opener.read('graftstate').splitlines())
            else:
                obsoleted.extend(revs)
        # convert obsolete target into revs to avoid alias joke
        obsoleted[:] = [str(i) for i in repo.revs('%lr', obsoleted)]
        if obsoleted and len(revs) > 1:

            raise error.Abort(_('Can not graft multiple revision while '
                                'obsoleting (for now).'))

        return commitwrapper(orig, ui, repo,*revs, **kwargs)
    finally:
        lock.release()

@eh.extsetup
def oldevolveextsetup(ui):
    try:
        rebase = extensions.find('rebase')
    except KeyError:
        raise error.Abort(_('evolution extension requires rebase extension.'))

    for cmd in ['amend', 'kill', 'uncommit', 'touch', 'fold']:
        entry = extensions.wrapcommand(cmdtable, cmd,
                                       warnobserrors)

    entry = cmdutil.findcmd('commit', commands.table)[1]
    entry[1].append(('o', 'obsolete', [],
                     _("make commit obsolete this revision")))
    entry = cmdutil.findcmd('graft', commands.table)[1]
    entry[1].append(('o', 'obsolete', [],
                     _("make graft obsoletes this revision")))
    entry[1].append(('O', 'old-obsolete', False,
                     _("make graft obsoletes its source")))