add git-imerge

1 files changed, 2805 insertions, 0 deletions

diff --git a/bin/git/git-imerge b/bin/git/git-imerge
new file mode 100755
index 0000000..a9d646c
--- /dev/null
+++ b/bin/git/git-imerge
@@ -0,0 +1,2805 @@
+#! /usr/bin/env python2
+
+# Copyright 2012-2013 Michael Haggerty <mhagger@alum.mit.edu>
+#
+# This file is part of git-imerge.
+#
+# git-imerge is free software: you can redistribute it and/or
+# modify it under the terms of the GNU General Public License as
+# published by the Free Software Foundation, either version 2 of the
+# License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+# General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see
+# <http://www.gnu.org/licenses/>.
+
+r"""Git incremental merge
+
+Perform the merge between two branches incrementally.  If conflicts
+are encountered, figure out exactly which pairs of commits conflict,
+and present the user with one pairwise conflict at a time for
+resolution.
+
+git-imerge has two primary design goals:
+
+* Reduce the pain of resolving merge conflicts to its unavoidable
+  minimum, by finding and presenting the smallest possible conflicts:
+  those between the changes introduced by one commit from each branch.
+
+* Allow a merge to be saved, tested, interrupted, published, and
+  collaborated on while it is in progress.
+
+The best thing to read to get started is "git-imerge: A Practical
+Introduction" [1].  The theory and benefits of incremental merging are
+described in minute detail in a series of blog posts [2], as are the
+benefits of retaining history when doing a rebase [3].
+
+Multiple incremental merges can be in progress at the same time.  Each
+incremental merge has a name, and its progress is recorded in the Git
+repository as references under 'refs/imerge/NAME'.  The current state
+of an incremental merge can (crudely) be visualized using the
+"diagram" command.
+
+An incremental merge can be interrupted and resumed arbitrarily, or
+even pushed to a server to allow somebody else to work on it.
+
+When an incremental merge is finished, you can discard the
+intermediate merge commits and create a simpler history to record
+permanently in your project repository using either the "finish" or
+"simplify" command.  The incremental merge can be simplified in one of
+three ways:
+
+  * merge
+      keep only a simple merge of the second branch into the first
+      branch, discarding all intermediate merges.  The result is
+      similar to what you would get from
+
+          git checkout BRANCH1
+          git merge BRANCH2
+
+  * rebase
+      keep the versions of the commits from the second branch rebased
+      onto the first branch.  The result is similar to what you would
+      get from
+
+          git checkout BRANCH2
+          git rebase BRANCH1
+
+  * rebase-with-history
+      like rebase, except that each of the rebased commits is recorded
+      as a merge from its original version to its rebased predecessor.
+      This is a style of rebasing that does not discard the old
+      version of the branch, and allows an already-published branch to
+      be rebased.  See [3] for more information.
+
+Simple operation:
+
+For basic operation, you only need to know three git-imerge commands.
+To merge BRANCH into MASTER or rebase BRANCH onto MASTER,
+
+    git checkout MASTER
+    git-imerge start --name=NAME --goal=GOAL --first-parent BRANCH
+    while not done:
+        <fix conflict presented to you>
+        git commit
+        git-imerge continue
+    git-imerge finish
+
+where
+
+    NAME is the name for this merge (and also the default name of the
+        branch to which the results will be saved)
+
+    GOAL describes how you want to simplify the results:
+
+        "merge" for a simple merge
+
+        "rebase" for a simple rebase
+
+        "rebase-with-history" for a rebase that retains history.  This
+        is equivalent to merging the commits from BRANCH into MASTER,
+        one commit at a time. In other words, it transforms this::
+
+            o---o---o---o          MASTER
+                 \
+                  A---B---C---D    BRANCH
+
+        into this::
+
+            o---o---o---o---A'--B'--C'--D'    MASTER
+                 \         /   /   /   /
+                  --------A---B---C---D       BRANCH
+
+        This is like a rebase, except that it retains the history of
+        individual merges.  See [3] for more information.
+
+
+[1] http://softwareswirl.blogspot.com/2013/05/git-imerge-practical-introduction.html
+
+[2] http://softwareswirl.blogspot.com/2012/12/the-conflict-frontier-of-nightmare-merge.html
+    http://softwareswirl.blogspot.com/2012/12/mapping-merge-conflict-frontier.html
+    http://softwareswirl.blogspot.com/2012/12/real-world-conflict-diagrams.html
+    http://softwareswirl.blogspot.com/2013/05/git-incremental-merge.html
+    http://softwareswirl.blogspot.com/2013/05/one-merge-to-rule-them-all.html
+    http://softwareswirl.blogspot.com/2013/05/incremental-merge-vs-direct-merge-vs.html
+
+[3] http://softwareswirl.blogspot.com/2009/04/truce-in-merge-vs-rebase-war.html
+    http://softwareswirl.blogspot.com/2009/08/upstream-rebase-just-works-if-history.html
+    http://softwareswirl.blogspot.com/2009/08/rebase-with-history-implementation.html
+
+"""
+
+import sys
+import re
+import subprocess
+import itertools
+import functools
+import argparse
+from cStringIO import StringIO
+import json
+import os
+
+# CalledProcessError, check_call, and check_output were not in the
+# original Python 2.4 subprocess library, so implement it here if
+# necessary (implementations are taken from the Python 2.7 library):
+try:
+    from subprocess import CalledProcessError
+except ImportError:
+    class CalledProcessError(Exception):
+        def __init__(self, returncode, cmd, output=None):
+            self.returncode = returncode
+            self.cmd = cmd
+            self.output = output
+        def __str__(self):
+            return "Command '%s' returned non-zero exit status %d" % (self.cmd, self.returncode)
+
+try:
+    from subprocess import check_call
+except ImportError:
+    def check_call(*popenargs, **kwargs):
+        retcode = subprocess.call(*popenargs, **kwargs)
+        if retcode:
+            cmd = kwargs.get("args")
+            if cmd is None:
+                cmd = popenargs[0]
+            raise CalledProcessError(retcode, cmd)
+        return 0
+
+try:
+    from subprocess import check_output
+except ImportError:
+    def check_output(*popenargs, **kwargs):
+        if 'stdout' in kwargs:
+            raise ValueError('stdout argument not allowed, it will be overridden.')
+        process = subprocess.Popen(stdout=subprocess.PIPE, *popenargs, **kwargs)
+        output, unused_err = process.communicate()
+        retcode = process.poll()
+        if retcode:
+            cmd = kwargs.get("args")
+            if cmd is None:
+                cmd = popenargs[0]
+            # We don't store output in the CalledProcessError because
+            # the "output" keyword parameter was not supported in
+            # Python 2.6:
+            raise CalledProcessError(retcode, cmd)
+        return output
+
+
+STATE_VERSION = (1, 0, 0)
+
+ZEROS = '0' * 40
+
+ALLOWED_GOALS = [
+    #'full',
+    'rebase-with-history',
+    'rebase',
+    'merge',
+    ]
+DEFAULT_GOAL = 'merge'
+
+
+class Failure(Exception):
+    """An exception that indicates a normal failure of the script.
+
+    Failures are reported at top level via sys.exit(str(e)) rather
+    than via a Python stack dump."""
+
+    @classmethod
+    def wrap(klass, f):
+        """Wrap a function inside a try...except that catches this error.
+
+        If the exception is thrown, call sys.exit().  This function
+        can be used as a decorator."""
+
+        @functools.wraps(f)
+        def wrapper(*args, **kw):
+            try:
+                return f(*args, **kw)
+            except klass, e:
+                sys.exit(str(e))
+
+        return wrapper
+
+    pass
+
+
+class AnsiColor:
+    BLACK = '\033[0;30m'
+    RED = '\033[0;31m'
+    GREEN = '\033[0;32m'
+    YELLOW = '\033[0;33m'
+    BLUE = '\033[0;34m'
+    MAGENTA = '\033[0;35m'
+    CYAN = '\033[0;36m'
+    B_GRAY = '\033[0;37m'
+    D_GRAY = '\033[1;30m'
+    B_RED = '\033[1;31m'
+    B_GREEN = '\033[1;32m'
+    B_YELLOW = '\033[1;33m'
+    B_BLUE = '\033[1;34m'
+    B_MAGENTA = '\033[1;35m'
+    B_CYAN = '\033[1;36m'
+    WHITE = '\033[1;37m'
+    END = '\033[0m'
+
+    @classmethod
+    def disable(cls):
+        cls.BLACK = ''
+        cls.RED = ''
+        cls.GREEN = ''
+        cls.YELLOW = ''
+        cls.BLUE = ''
+        cls.MAGENTA = ''
+        cls.CYAN = ''
+        cls.B_GRAY = ''
+        cls.D_GRAY = ''
+        cls.B_RED = ''
+        cls.B_GREEN = ''
+        cls.B_YELLOW = ''
+        cls.B_BLUE = ''
+        cls.B_MAGENTA = ''
+        cls.B_CYAN = ''
+        cls.WHITE = ''
+        cls.END = ''
+
+
+def iter_neighbors(iterable):
+    """For an iterable (x0, x1, x2, ...) generate [(x0,x1), (x1,x2), ...]."""
+
+    i = iter(iterable)
+
+    try:
+        last = i.next()
+    except StopIteration:
+        return
+
+    for x in i:
+        yield (last, x)
+        last = x
+
+
+def find_first_false(f, lo, hi):
+    """Return the smallest i in lo <= i < hi for which f(i) returns False using bisection.
+
+    If there is no such i, return hi.
+
+    """
+
+    # Loop invariant: f(i) returns True for i < lo; f(i) returns False
+    # for i >= hi.
+
+    while lo < hi:
+        mid = (lo + hi) // 2
+        if f(mid):
+            lo = mid + 1
+        else:
+            hi = mid
+
+    return lo
+
+
+def call_silently(cmd):
+    try:
+        NULL = open(os.devnull, 'w')
+    except (IOError, AttributeError):
+        NULL = subprocess.PIPE
+
+    p = subprocess.Popen(cmd, stdout=NULL, stderr=NULL)
+    (out,err) = p.communicate()
+    retcode = p.wait()
+    if retcode:
+        raise CalledProcessError(retcode, cmd)
+
+
+class UncleanWorkTreeError(Failure):
+    pass
+
+
+def require_clean_work_tree(action):
+    """Verify that the current tree is clean.
+
+    The code is a Python translation of the git-sh-setup(1) function
+    of the same name."""
+
+    process = subprocess.Popen(
+        ['git', 'rev-parse', '--verify', 'HEAD'],
+        stdout=subprocess.PIPE, stderr=subprocess.PIPE,
+        )
+    _unused, err = process.communicate()
+    retcode = process.poll()
+    if retcode:
+        raise UncleanWorkTreeError(err.rstrip())
+
+    process = subprocess.Popen(
+        ['git', 'update-index', '-q', '--ignore-submodules', '--refresh'],
+        stdout=subprocess.PIPE, stderr=subprocess.PIPE,
+        )
+    out, err = process.communicate()
+    retcode = process.poll()
+    if retcode:
+        raise UncleanWorkTreeError(err.rstrip() or out.rstrip())
+
+    error = []
+    try:
+        check_call(['git', 'diff-files', '--quiet', '--ignore-submodules'])
+    except CalledProcessError:
+        error.append('Cannot %s: You have unstaged changes.' % (action,))
+
+    try:
+        check_call([
+            'git', 'diff-index', '--cached', '--quiet',
+            '--ignore-submodules', 'HEAD', '--',
+            ])
+    except CalledProcessError:
+        if not error:
+            error.append('Cannot %s: Your index contains uncommitted changes.' % (action,))
+        else:
+            error.append('Additionally, your index contains uncommitted changes.')
+
+    if error:
+        raise UncleanWorkTreeError('\n'.join(error))
+
+
+def rev_parse(arg):
+    return check_output(['git', 'rev-parse', '--verify', '--quiet', arg]).strip()
+
+
+def rev_list(*args):
+    return [
+        l.strip()
+        for l in check_output(['git', 'rev-list'] + list(args),).splitlines()
+        ]
+
+
+def get_type(arg):
+    """Return the type of a git object ('commit', 'tree', 'blob', or 'tag')."""
+
+    return check_output(['git', 'cat-file', '-t', arg]).strip()
+
+
+def get_tree(arg):
+    return rev_parse('%s^{tree}' % (arg,))
+
+
+BRANCH_PREFIX = 'refs/heads/'
+
+def checkout(refname):
+    if refname.startswith(BRANCH_PREFIX):
+        target = refname[len(BRANCH_PREFIX):]
+    else:
+        target = '%s^0' % (refname,)
+    check_call(['git', 'checkout', target])
+
+
+def get_commit_sha1(arg):
+    """Convert arg into a SHA1 and verify that it refers to a commit.
+
+    If not, raise ValueError."""
+
+    try:
+        return rev_parse('%s^{commit}' % (arg,))
+    except CalledProcessError:
+        raise ValueError('%r does not refer to a valid git commit' % (arg,))
+
+
+def get_commit_parents(commit):
+    """Return a list containing the parents of commit."""
+
+    return check_output(
+        ['git', '--no-pager', 'log', '--no-walk', '--pretty=format:%P', commit]
+        ).strip().split()
+
+
+def get_log_message(commit):
+    contents = check_output([
+            'git', 'cat-file', 'commit', commit
+            ]).splitlines(True)
+    contents = contents[contents.index('\n') + 1:]
+    if contents and contents[-1][-1:] != '\n':
+        contents.append('\n')
+    return ''.join(contents)
+
+
+def get_author_info(commit):
+    a = check_output([
+        'git', '--no-pager', 'log', '-n1',
+        '--format=%an%x00%ae%x00%ad', commit
+        ]).strip().split('\x00')
+
+    return {
+        'GIT_AUTHOR_NAME': a[0],
+        'GIT_AUTHOR_EMAIL': a[1],
+        'GIT_AUTHOR_DATE': a[2],
+        }
+
+
+def commit_tree(tree, parents, msg, metadata=None):
+    """Create a commit containing the specified tree.
+
+    metadata can be author or committer information to be added to the
+    environment; e.g., {'GIT_AUTHOR_NAME' : 'me'}.
+
+    Return the SHA-1 of the new commit object."""
+
+    cmd = ['git', 'commit-tree', tree]
+    for parent in parents:
+        cmd += ['-p', parent]
+
+    if metadata is not None:
+        env = os.environ.copy()
+        env.update(metadata)
+    else:
+        env = os.environ
+
+    process = subprocess.Popen(
+        cmd, env=env, stdin=subprocess.PIPE, stdout=subprocess.PIPE,
+        )
+    out, err = process.communicate(msg)
+    retcode = process.poll()
+
+    if retcode:
+        # We don't store the output in the CalledProcessError because
+        # the "output" keyword parameter was not supported in Python
+        # 2.6:
+        raise CalledProcessError(retcode, cmd)
+
+    return out.strip()
+
+
+class TemporaryHead(object):
+    """A context manager that records the current HEAD state then restores it.
+
+    The message is used for the reflog."""
+
+    def __enter__(self, message='imerge: restoring'):
+        self.message = message
+        try:
+            self.head_name = check_output(['git', 'symbolic-ref', '--quiet', 'HEAD']).strip()
+        except CalledProcessError:
+            self.head_name = None
+        self.orig_head = get_commit_sha1('HEAD')
+        return self
+
+    def __exit__(self, exc_type, exc_val, exc_tb):
+        if self.head_name:
+            try:
+                check_call([
+                    'git', 'symbolic-ref',
+                    '-m', self.message, 'HEAD',
+                    self.head_name,
+                    ])
+            except Exception, e:
+                raise Failure(
+                    'Could not restore HEAD to %r!:    %s\n'
+                    % (self.head_name, e.message,)
+                    )
+            else:
+                try:
+                    check_call(['git', 'reset', '--hard', self.orig_head])
+                except Exception, e:
+                    raise Failure(
+                        'Could not restore HEAD to %r!:    %s\n'
+                        % (self.orig_head, e.message,)
+                        )
+        return False
+
+
+def reparent(commit, parent_sha1s):
+    """Create a new commit object like commit, but with the specified parents.
+
+    commit is the SHA1 of an existing commit and parent_sha1s is a
+    list of SHA1s.  Create a new commit exactly like that one, except
+    that it has the specified parent commits.  Return the SHA1 of the
+    resulting commit object, which is already stored in the object
+    database but is not yet referenced by anything."""
+
+    old_commit = check_output(['git', 'cat-file', 'commit', commit])
+    separator = old_commit.index('\n\n')
+    headers = old_commit[:separator + 1].splitlines(True)
+    rest = old_commit[separator + 1:]
+
+    new_commit = StringIO()
+    for i in range(len(headers)):
+        line = headers[i]
+        if line.startswith('tree '):
+            new_commit.write(line)
+            for parent_sha1 in parent_sha1s:
+                new_commit.write('parent %s\n' % (parent_sha1,))
+        elif line.startswith('parent '):
+            # Discard old parents:
+            pass
+        else:
+            new_commit.write(line)
+
+    new_commit.write(rest)
+
+    process = subprocess.Popen(
+        ['git', 'hash-object', '-t', 'commit', '-w', '--stdin'],
+        stdin=subprocess.PIPE, stdout=subprocess.PIPE,
+        )
+    out, err = process.communicate(new_commit.getvalue())
+    retcode = process.poll()
+    if retcode:
+        raise Failure('Could not reparent commit %s' % (commit,))
+    return out.strip()
+
+
+class AutomaticMergeFailed(Exception):
+    def __init__(self, commit1, commit2):
+        Exception.__init__(
+            self, 'Automatic merge of %s and %s failed' % (commit1, commit2,)
+            )
+        self.commit1, self.commit2 = commit1, commit2
+
+
+def automerge(commit1, commit2):
+    """Attempt an automatic merge of commit1 and commit2.
+
+    Return the SHA1 of the resulting commit, or raise
+    AutomaticMergeFailed on error.  This must be called with a clean
+    worktree."""
+
+    call_silently(['git', 'checkout', '-f', commit1])
+    try:
+        call_silently(['git', '-c', 'rerere.enabled=false', 'merge', commit2])
+    except CalledProcessError:
+        # We don't use "git merge --abort" here because it was only
+        # added in git version 1.7.4.
+        call_silently(['git', 'reset', '--merge'])
+        raise AutomaticMergeFailed(commit1, commit2)
+    else:
+        return get_commit_sha1('HEAD')
+
+
+class MergeRecord(object):
+    # Bits for the flags field:
+
+    # There is a saved successful auto merge:
+    SAVED_AUTO = 0x01
+
+    # An auto merge (which may have been unsuccessful) has been done:
+    NEW_AUTO = 0x02
+
+    # There is a saved successful manual merge:
+    SAVED_MANUAL = 0x04
+
+    # A manual merge (which may have been unsuccessful) has been done:
+    NEW_MANUAL = 0x08
+
+    # A merge that is currently blocking the merge frontier:
+    BLOCKED = 0x10
+
+    # Some useful bit combinations:
+    SAVED = SAVED_AUTO | SAVED_MANUAL
+    NEW = NEW_AUTO | NEW_MANUAL
+
+    AUTO = SAVED_AUTO | NEW_AUTO
+    MANUAL = SAVED_MANUAL | NEW_MANUAL
+
+    ALLOWED_INITIAL_FLAGS = [
+        SAVED_AUTO,
+        SAVED_MANUAL,
+        NEW_AUTO,
+        NEW_MANUAL,
+        ]
+
+    def __init__(self, sha1=None, flags=0):
+        # The currently believed correct merge, or None if it is
+        # unknown or the best attempt was unsuccessful.
+        self.sha1 = sha1
+
+        if self.sha1 is None:
+            if flags != 0:
+                raise ValueError('Initial flags (%s) for sha1=None should be 0' % (flags,))
+        elif flags not in self.ALLOWED_INITIAL_FLAGS:
+            raise ValueError('Initial flags (%s) is invalid' % (flags,))
+
+        # See bits above.
+        self.flags = flags
+
+    def record_merge(self, sha1, source):
+        """Record a merge at this position.
+
+        source must be SAVED_AUTO, SAVED_MANUAL, NEW_AUTO, or NEW_MANUAL."""
+
+        if source == self.SAVED_AUTO:
+            # SAVED_AUTO is recorded in any case, but only used if it
+            # is the only info available.
+            if self.flags & (self.MANUAL | self.NEW) == 0:
+                self.sha1 = sha1
+            self.flags |= source
+        elif source == self.NEW_AUTO:
+            # NEW_AUTO is silently ignored if any MANUAL value is
+            # already recorded.
+            if self.flags & self.MANUAL == 0:
+                self.sha1 = sha1
+                self.flags |= source
+        elif source == self.SAVED_MANUAL:
+            # SAVED_MANUAL is recorded in any case, but only used if
+            # no NEW_MANUAL is available.
+            if self.flags & self.NEW_MANUAL == 0:
+                self.sha1 = sha1
+            self.flags |= source
+        elif source == self.NEW_MANUAL:
+            # NEW_MANUAL is always used, and also causes NEW_AUTO to
+            # be forgotten if present.
+            self.sha1 = sha1
+            self.flags = (self.flags | source) & ~self.NEW_AUTO
+        else:
+            raise ValueError('Undefined source: %s' % (source,))
+
+    def record_blocked(self, blocked):
+        if blocked:
+            self.flags |= self.BLOCKED
+        else:
+            self.flags &= ~self.BLOCKED
+
+    def is_known(self):
+        return self.sha1 is not None
+
+    def is_blocked(self):
+        return self.flags & self.BLOCKED != 0
+
+    def is_manual(self):
+        return self.flags & self.MANUAL != 0
+
+    def save(self, name, i1, i2):
+        """If this record has changed, save it."""
+
+        def set_ref(source):
+            check_call([
+                    'git', 'update-ref',
+                    '-m', 'imerge %r: Record %s merge' % (name, source,),
+                    'refs/imerge/%s/%s/%d-%d' % (name, source, i1, i2),
+                    self.sha1,
+                    ])
+
+        def clear_ref(source):
+            check_call([
+                    'git', 'update-ref',
+                    '-d', 'imerge %r: Remove obsolete %s merge' % (name, source,),
+                    'refs/imerge/%s/%s/%d-%d' % (name, source, i1, i2),
+                    ])
+
+        if self.flags & self.MANUAL:
+            if self.flags & self.AUTO:
+                # Any MANUAL obsoletes any AUTO:
+                if self.flags & self.SAVED_AUTO:
+                    clear_ref('auto')
+
+                self.flags &= ~self.AUTO
+
+            if self.flags & self.NEW_MANUAL:
+                # Convert NEW_MANUAL to SAVED_MANUAL.
+                if self.sha1:
+                    set_ref('manual')
+                    self.flags |= self.SAVED_MANUAL
+                elif self.flags & self.SAVED_MANUAL:
+                    # Delete any existing SAVED_MANUAL:
+                    clear_ref('manual')
+                    self.flags &= ~self.SAVED_MANUAL
+                self.flags &= ~self.NEW_MANUAL
+
+        elif self.flags & self.NEW_AUTO:
+            # Convert NEW_AUTO to SAVED_AUTO.
+            if self.sha1:
+                set_ref('auto')
+                self.flags |= self.SAVED_AUTO
+            elif self.flags & self.SAVED_AUTO:
+                # Delete any existing SAVED_AUTO:
+                clear_ref('auto')
+                self.flags &= ~self.SAVED_AUTO
+            self.flags &= ~self.NEW_AUTO
+
+
+class UnexpectedMergeFailure(Exception):
+    def __init__(self, msg, i1, i2):
+        Exception.__init__(self, msg)
+        self.i1, self.i2 = i1, i2
+
+
+class BlockCompleteError(Exception):
+    pass
+
+
+class FrontierBlockedError(Exception):
+    def __init__(self, msg, i1, i2):
+        Exception.__init__(self, msg)
+        self.i1 = i1
+        self.i2 = i2
+
+
+class NotABlockingCommitError(Exception):
+    pass
+
+
+class MergeFrontier(object):
+    """Represents the merge frontier within a Block.
+
+    A MergeFrontier is represented by a list of SubBlocks, each of
+    which is thought to be completely mergeable.  The list is kept in
+    normalized form:
+
+    * Only non-empty blocks are retained
+
+    * Blocks are sorted from bottom left to upper right
+
+    * No redundant blocks
+
+    """
+
+    @staticmethod
+    def map_known_frontier(block):
+        """Return the MergeFrontier describing existing successful merges in block.
+
+        The return value only includes the part that is fully outlined
+        and whose outline consists of rectangles reaching back to
+        (0,0).
+
+        A blocked commit is *not* considered to be within the
+        frontier, even if a merge is registered for it.  Such merges
+        must be explicitly unblocked."""
+
+        # FIXME: This algorithm can take combinatorial time, for
+        # example if there is a big block of merges that is a dead
+        # end:
+        #
+        #     +++++++
+        #     +?+++++
+        #     +?+++++
+        #     +?+++++
+        #     +?*++++
+        #
+        # The problem is that the algorithm will explore all of the
+        # ways of getting to commit *, and the number of paths grows
+        # like a binomial coefficient.  The solution would be to
+        # remember dead-ends and reject any curves that visit a point
+        # to the right of a dead-end.
+        #
+        # For now we don't intend to allow a situation like this to be
+        # created, so we ignore the problem.
+
+        # A list (i1, i2, down) of points in the path so far.  down is
+        # True iff the attempted step following this one was
+        # downwards.
+        path = []
+
+        def create_frontier(path):
+            blocks = []
+            for ((i1old, i2old, downold), (i1new, i2new, downnew)) in iter_neighbors(path):
+                if downold == True and downnew == False:
+                    blocks.append(block[:i1new + 1, :i2new + 1])
+            return MergeFrontier(block, blocks)
+
+        # Loop invariants:
+        #
+        # * path is a valid path
+        #
+        # * (i1, i2) is in block but it not yet added to path
+        #
+        # * down is True if a step downwards from (i1, i2) has not yet
+        #   been attempted
+        (i1, i2) = (block.len1 - 1, 0)
+        down = True
+        while True:
+            if down:
+                if i2 == block.len2 - 1:
+                    # Hit edge of block; can't move down:
+                    down = False
+                elif (i1, i2 + 1) in block and not block.is_blocked(i1, i2 + 1):
+                    # Can move down
+                    path.append((i1, i2, True))
+                    i2 += 1
+                else:
+                    # Can't move down.
+                    down = False
+            else:
+                if i1 == 0:
+                    # Success!
+                    path.append((i1, i2, False))
+                    return create_frontier(path)
+                elif (i1 - 1, i2) in block and not block.is_blocked(i1 - 1, i2):
+                    # Can move left
+                    path.append((i1, i2, False))
+                    down = True
+                    i1 -= 1
+                else:
+                    # There's no way to go forward; backtrack until we
+                    # find a place where we can still try going left:
+                    while True:
+                        try:
+                            (i1, i2, down) = path.pop()
+                        except IndexError:
+                            # This shouldn't happen because, in the
+                            # worst case, there is a valid path across
+                            # the top edge of the merge diagram.
+                            raise RuntimeError('Block is improperly formed!')
+                        if down:
+                            down = False
+                            break
+
+    @staticmethod
+    def compute_by_bisection(block):
+        """Return a MergeFrontier instance for block.
+
+        We make the following assumptions (using Python subscript
+        notation):
+
+        0. All of the merges in block[1:,0] and block[0,1:] are
+           already known.  (This is an invariant of the Block class.)
+
+        1. If a direct merge can be done between block[i1-1,0] and
+           block[0,i2-1], then all of the pairwise merges in
+           block[1:i1, 1:i2] can also be done.
+
+        2. If a direct merge fails between block[i1-1,0] and
+           block[0,i2-1], then all of the pairwise merges in
+           block[i1-1:,i2-1:] would also fail.
+
+        Under these assumptions, the merge frontier is a stepstair
+        pattern going from the bottom-left to the top-right, and
+        bisection can be used to find the transition between mergeable
+        and conflicting in any row or column.
+
+        Of course these assumptions are not rigorously true, so the
+        MergeFrontier returned by this function is only an
+        approximation of the real merge diagram.  We check for and
+        correct such inconsistencies later."""
+
+        # Given that these diagrams typically have few blocks, check
+        # the end of a range first to see if the whole range can be
+        # determined, and fall back to bisection otherwise.  We
+        # determine the frontier block by block, starting in the lower
+        # left.
+
+        if block.len1 <= 1 or block.len2 <= 1 or block.is_blocked(1, 1):
+            return MergeFrontier(block, [])
+
+        if not block.is_mergeable(1, 1):
+            # There are no mergeable blocks in block; therefore,
+            # block[1,1] must itself be unmergeable.  Record that
+            # fact:
+            block[1,1].record_blocked(True)
+            return MergeFrontier(block, [])
+
+        blocks = []
+
+        # At this point, we know that there is at least one mergeable
+        # commit in the first column.  Find the height of the success
+        # block in column 1:
+        i1 = 1
+        i2 = find_first_false(
+            lambda i: block.is_mergeable(i1, i),
+            1, block.len2,
+            )
+
+        # Now we know that (1,i2-1) is mergeable but (1,i2) is not;
+        # e.g., (i1, i2) is like 'A' (or maybe 'B') in the following
+        # diagram (where '*' means mergeable, 'x' means not mergeable,
+        # and '?' means indeterminate) and that the merge under 'A' is
+        # not mergeable:
+        #
+        #          i1
+        #
+        #        0123456
+        #      0 *******
+        #      1 **?????
+        #  i2  2 **?????
+        #      3 **?????
+        #      4 *Axxxxx
+        #      5 *xxxxxx
+        #         B
+
+        while True:
+            if i2 == 1:
+                break
+
+            # At this point in the loop, we know that any blocks to
+            # the left of 'A' have already been recorded, (i1, i2-1)
+            # is mergeable but (i1, i2) is not; e.g., we are at a
+            # place like 'A' in the following diagram:
+            #
+            #          i1
+            #
+            #        0123456
+            #      0 **|****
+            #      1 **|*???
+            #  i2  2 **|*???
+            #      3 **|Axxx
+            #      4 --+xxxx
+            #      5 *xxxxxx
+            #
+            # This implies that (i1, i2) is the first unmergeable
+            # commit in a blocker block (though blocker blocks are not
+            # recorded explicitly).  It also implies that a mergeable
+            # block has its last mergeable commit somewhere in row
+            # i2-1; find its width.
+            if block.is_mergeable(block.len1 - 1, i2 - 1):
+                i1 = block.len1
+                blocks.append(block[:i1,:i2])
+                break
+            else:
+                i1 = find_first_false(
+                    lambda i: block.is_mergeable(i, i2 - 1),
+                    i1 + 1, block.len1 - 1,
+                    )
+                blocks.append(block[:i1,:i2])
+
+            # At this point in the loop, (i1-1, i2-1) is mergeable but
+            # (i1, i2-1) is not; e.g., 'A' in the following diagram:
+            #
+            #          i1
+            #
+            #        0123456
+            #      0 **|*|**
+            #      1 **|*|??
+            #  i2  2 --+-+xx
+            #      3 **|xxAx
+            #      4 --+xxxx
+            #      5 *xxxxxx
+            #
+            # The block ending at (i1-1,i2-1) has just been recorded.
+            # Now find the height of the conflict rectangle at column
+            # i1 and fill it in:
+            if block.is_mergeable(i1, 1):
+                i2 = find_first_false(
+                    lambda i: block.is_mergeable(i1, i),
+                    2, i2 - 1,
+                    )
+            else:
+                break
+
+        return MergeFrontier(block, blocks)
+
+    def __init__(self, block, blocks=None):
+        self.block = block
+        blocks = list(self._iter_non_empty_blocks(blocks or []))
+        blocks.sort(key=lambda block: block.len1)
+        self.blocks = list(self._iter_non_redundant_blocks(blocks))
+
+    def __iter__(self):
+        """Iterate over blocks from bottom left to upper right."""
+
+        return iter(self.blocks)
+
+    def __nonzero__(self):
+        """Return True iff this frontier has no completed parts."""
+
+        return bool(self.blocks)
+
+    def is_complete(self):
+        """Return True iff the frontier covers the whole block."""
+
+        return (
+            len(self.blocks) == 1
+            and self.blocks[0].len1 == self.block.len1
+            and self.blocks[0].len2 == self.block.len2
+            )
+
+    # Additional codes used in the 2D array returned from create_diagram()
+    FRONTIER_WITHIN = 0x10
+    FRONTIER_RIGHT_EDGE = 0x20
+    FRONTIER_BOTTOM_EDGE = 0x40
+    FRONTIER_MASK = 0x70
+
+    @classmethod
+    def default_formatter(cls, node, legend=None):
+        def color(node, within):
+            if within:
+                return AnsiColor.B_GREEN + node + AnsiColor.END
+            else:
+                return AnsiColor.B_RED + node + AnsiColor.END
+
+        if legend is None:
+            legend = ["?", "*", ".", "#", "@", "-", "|", "+"]
+        merge = node & ~cls.FRONTIER_MASK
+        within = merge == Block.MERGE_MANUAL or (node & cls.FRONTIER_WITHIN)
+        skip = [Block.MERGE_MANUAL, Block.MERGE_BLOCKED, Block.MERGE_UNBLOCKED]
+        if merge not in skip:
+            vertex = (cls.FRONTIER_BOTTOM_EDGE | cls.FRONTIER_RIGHT_EDGE)
+            edge_status = node & vertex
+            if edge_status == vertex:
+                return color(legend[-1], within)
+            elif edge_status == cls.FRONTIER_RIGHT_EDGE:
+                return color(legend[-2], within)
+            elif edge_status == cls.FRONTIER_BOTTOM_EDGE:
+                return color(legend[-3], within)
+        return color(legend[merge], within)
+
+    def create_diagram(self):
+        """Generate a diagram of this frontier.
+
+        The returned diagram is a nested list of integers forming a 2D array,
+        representing the merge frontier embedded in the diagram of commits
+        returned from Block.create_diagram().
+
+        At each node in the returned diagram is an integer whose value is a
+        bitwise-or of existing MERGE_* constant from Block.create_diagram()
+        and zero or more of the FRONTIER_* constants defined in this class."""
+
+        diagram = self.block.create_diagram()
+        for block in self:
+            for i1 in range(block.len1):
+                for i2 in range(block.len2):
+                    v = self.FRONTIER_WITHIN
+                    if i1 == block.len1 - 1:
+                        v |= self.FRONTIER_RIGHT_EDGE
+                    if i2 == block.len2 - 1:
+                        v |= self.FRONTIER_BOTTOM_EDGE
+                    diagram[i1][i2] |= v
+        return diagram
+
+    def format_diagram(self, formatter=None, diagram=None):
+        if formatter is None:
+            formatter = self.default_formatter
+        if diagram is None:
+            diagram = self.create_diagram()
+        return [
+            [formatter(diagram[i1][i2]) for i2 in range(self.block.len2)]
+            for i1 in range(self.block.len1)]
+
+    def write(self, f):
+        """Write this frontier to file-like object f."""
+        diagram = self.format_diagram()
+        for i2 in range(self.block.len2):
+            for i1 in range(self.block.len1):
+                f.write(diagram[i1][i2])
+            f.write('\n')
+
+    def write_html(self, f, name, cssfile="imerge.css", abbrev_sha1=7):
+        class_map = {
+            Block.MERGE_UNKNOWN: "merge_unknown",
+            Block.MERGE_MANUAL: "merge_manual",
+            Block.MERGE_AUTOMATIC: "merge_automatic",
+            Block.MERGE_BLOCKED: "merge_blocked",
+            Block.MERGE_UNBLOCKED: "merge_unblocked",
+            self.FRONTIER_WITHIN: "frontier_within",
+            self.FRONTIER_RIGHT_EDGE: "frontier_right_edge",
+            self.FRONTIER_BOTTOM_EDGE: "frontier_bottom_edge",
+            }
+
+        def map_to_classes(node):
+            merge = node & ~self.FRONTIER_MASK
+            ret = [class_map[merge]]
+            for bit in [self.FRONTIER_WITHIN, self.FRONTIER_RIGHT_EDGE,
+                        self.FRONTIER_BOTTOM_EDGE]:
+                if node & bit:
+                    ret.append(class_map[bit])
+            return ret
+
+        f.write("""\
+<html>
+<head>
+<title>git-imerge: %s</title>
+<link rel="stylesheet" href="%s" type="text/css" />
+</head>
+<body>
+<table id="imerge">
+""" % (name, cssfile))
+
+        diagram = self.create_diagram()
+        for i2 in range(self.block.len2):
+            f.write("  <tr>\n")
+            for i1 in range(self.block.len1):
+                classes = map_to_classes(diagram[i1][i2])
+                record = self.block.get_value(i1, i2)
+                sha1 = record.sha1 or ""
+                td_id = record.sha1 and ' id="%s"' % (record.sha1) or ''
+                td_class = classes and ' class="' + " ".join(classes) + '"' or ''
+                f.write("    <td%s%s>%.*s</td>\n" % (
+                        td_id, td_class, abbrev_sha1, sha1))
+            f.write("  </tr>\n")
+        f.write("</table>\n</body>\n</html>\n")
+
+    @staticmethod
+    def _iter_non_empty_blocks(blocks):
+        for block in blocks:
+            if block.len1 > 1 and block.len2 > 1:
+                yield block
+
+    @staticmethod
+    def _iter_non_redundant_blocks(blocks):
+        def contains(block1, block2):
+            """Return true if block1 contains block2."""
+
+            return block1.len1 >= block2.len1 and block1.len2 >= block2.len2
+
+        i = iter(blocks)
+        try:
+            last = i.next()
+        except StopIteration:
+            return
+
+        for block in i:
+            if contains(last, block):
+                pass
+            elif contains(block, last):
+                last = block
+            else:
+                yield last
+                last = block
+
+        yield last
+
+    def remove_failure(self, i1, i2):
+        """Refine the merge frontier given that the specified merge fails."""
+
+        newblocks = []
+        shrunk_block = False
+
+        for block in self.blocks:
+            if i1 < block.len1 and i2 < block.len2:
+                if i1 > 1:
+                    newblocks.append(block[:i1, :])
+                if i2 > 1:
+                    newblocks.append(block[:, :i2])
+                shrunk_block = True
+            else:
+                newblocks.append(block)
+
+        if shrunk_block:
+            self.blocks = list(self._iter_non_redundant_blocks(newblocks))
+
+    def partition(self, block):
+        """Return two MergeFrontier instances partitioned by block.
+
+        Return (frontier1, frontier2), where each frontier is limited
+        to each side of the argument.
+
+        block must be contained in this MergeFrontier and already be
+        outlined."""
+
+        # Remember that the new blocks have to include the outlined
+        # edge of the partitioning block to satisfy the invariant that
+        # the left and upper edge of a block has to be known.
+
+        left = []
+        right = []
+        for b in self.blocks:
+            if b.len1 == block.len1 and b.len2 == block.len2:
+                # That's the block we're partitioning on; just skip it.
+                pass
+            elif b.len1 < block.len1 and b.len2 > block.len2:
+                left.append(b[:, block.len2 - 1:])
+            elif b.len1 > block.len1 and b.len2 < block.len2:
+                right.append(b[block.len1 - 1:, :])
+            else:
+                raise ValueError(
+                    'MergeFrontier partitioned with inappropriate block'
+                    )
+        return (
+            MergeFrontier(self.block[:block.len1, block.len2 - 1:], left),
+            MergeFrontier(self.block[block.len1 - 1:, :block.len2], right),
+            )
+
+    def iter_blocker_blocks(self):
+        """Iterate over the blocks on the far side of this frontier.
+
+        This must only be called for an outlined frontier."""
+
+        if not self:
+            yield self.block
+            return
+
+        blockruns = []
+        if self.blocks[0].len2 < self.block.len2:
+            blockruns.append([self.block[0,:]])
+        blockruns.append(self)
+        if self.blocks[-1].len1 < self.block.len1:
+            blockruns.append([self.block[:,0]])
+
+        for block1, block2 in iter_neighbors(itertools.chain(*blockruns)):
+            yield self.block[block1.len1 - 1:block2.len1, block2.len2 - 1: block1.len2]
+
+    def get_affected_blocker_block(self, i1, i2):
+        """Return the blocker block that a successful merge (i1,i2) would unblock.
+
+        If there is no such block, raise NotABlockingCommitError."""
+
+        for block in self.iter_blocker_blocks():
+            try:
+                (block_i1, block_i2) = block.convert_original_indexes(i1, i2)
+            except IndexError:
+                pass
+            else:
+                if (block_i1, block_i2) == (1,1):
+                    # That's the one we need to improve this block:
+                    return block
+                else:
+                    # An index pair can only be in a single blocker
+                    # block, which we've already found:
+                    raise NotABlockingCommitError(
+                        'Commit %d-%d was not blocking the frontier.'
+                        % self.block.get_original_indexes(i1, i2)
+                        )
+        else:
+            raise NotABlockingCommitError(
+                'Commit %d-%d was not on the frontier.'
+                % self.block.get_original_indexes(i1, i2)
+                )
+
+    def auto_expand(self):
+        """Try pushing out one of the blocks on this frontier.
+
+        Raise BlockCompleteError if the whole block has already been
+        solved.  Raise FrontierBlockedError if the frontier is blocked
+        everywhere.  This method does *not* update self; if it returns
+        successfully you should recompute the frontier from
+        scratch."""
+
+        blocks = list(self.iter_blocker_blocks())
+        if not blocks:
+            raise BlockCompleteError('The block is already complete')
+        # Try blocks from biggest to smallest:
+        blocks.sort(key=lambda block: block.get_area(), reverse=True)
+        for block in blocks:
+            if block.auto_outline_frontier():
+                return
+        else:
+            # None of the blocks could be expanded.  Suggest that the
+            # caller do a manual merge of the commit that is blocking
+            # the *smallest* blocker block.
+            i1, i2 = blocks[-1].get_original_indexes(1, 1)
+            raise FrontierBlockedError(
+                'Frontier blocked; suggest manual merge of %d-%d' % (i1, i2),
+                i1, i2
+                )
+
+
+class NoManualMergeError(Exception):
+    pass
+
+
+class ManualMergeUnusableError(Exception):
+    def __init__(self, msg, commit):
+        Exception.__init__(self, 'Commit %s is not usable; %s' % (commit, msg))
+        self.commit = commit
+
+
+class CommitNotFoundError(Exception):
+    def __init__(self, commit):
+        Exception.__init__(
+            self,
+            'Commit %s was not found among the known merge commits' % (commit,),
+            )
+        self.commit = commit
+
+
+class Block(object):
+    """A rectangular range of commits, indexed by (i1,i2).
+
+    The commits block[0,1:] and block[1:,0] are always all known.
+    block[0,0] may or may not be known; it is usually unneeded (except
+    maybe implicitly).
+
+    Members:
+
+        len1, len2 -- the dimensions of the block.
+
+    """
+
+    def __init__(self, len1, len2):
+        self.len1 = len1
+        self.len2 = len2
+
+    def get_area(self):
+        """Return the area of this block, ignoring the known edges."""
+
+        return (self.len1 - 1) * (self.len2 - 1)
+
+    def _check_indexes(self, i1, i2):
+        if not (0 <= i1 < self.len1):
+            raise IndexError('first index (%s) is out of range 0:%d' % (i1, self.len1,))
+        if not (0 <= i2 < self.len2):
+            raise IndexError('second index (%s) is out of range 0:%d' % (i2, self.len2,))
+
+    def _normalize_indexes(self, index):
+        """Return a pair of non-negative integers (i1, i2)."""
+
+        try:
+            (i1, i2) = index
+        except TypeError:
+            raise IndexError('Block indexing requires exactly two indexes')
+
+        if i1 < 0:
+            i1 += self.len1
+        if i2 < 0:
+            i2 += self.len2
+
+        self._check_indexes(i1, i2)
+        return (i1, i2)
+
+    def get_original_indexes(self, i1, i2):
+        """Return the original indexes corresponding to (i1,i2) in this block.
+
+        This function supports negative indexes."""
+
+        return self._normalize_indexes((i1, i2))
+
+    def convert_original_indexes(self, i1, i2):
+        """Return the indexes in this block corresponding to original indexes (i1,i2).
+
+        raise IndexError if they are not within this block.  This
+        method does not support negative indices."""
+
+        return (i1, i2)
+
+    def _set_value(self, i1, i2, value):
+        """Set the MergeRecord for integer indexes (i1, i2).
+
+        i1 and i2 must be non-negative."""
+
+        raise NotImplementedError()
+
+    def get_value(self, i1, i2):
+        """Return the MergeRecord for integer indexes (i1, i2).
+
+        i1 and i2 must be non-negative."""
+
+        raise NotImplementedError()
+
+    def __getitem__(self, index):
+        """Return the MergeRecord at (i1, i2) (requires two indexes).
+
+        If i1 and i2 are integers but the merge is unknown, return
+        None.  If either index is a slice, return a SubBlock."""
+
+        try:
+            (i1, i2) = index
+        except TypeError:
+            raise IndexError('Block indexing requires exactly two indexes')
+        if isinstance(i1, slice) or isinstance(i2, slice):
+            return SubBlock(self, i1, i2)
+        else:
+            return self.get_value(*self._normalize_indexes((i1, i2)))
+
+    def __contains__(self, index):
+        return self[index].is_known()
+
+    def is_blocked(self, i1, i2):
+        """Return True iff the specified commit is blocked."""
+
+        (i1, i2) = self._normalize_indexes((i1, i2))
+        return self[i1, i2].is_blocked()
+
+    def is_mergeable(self, i1, i2):
+        """Determine whether (i1,i2) can be merged automatically.
+
+        If we already have a merge record for (i1,i2), return True.
+        Otherwise, attempt a merge (discarding the result)."""
+
+        (i1, i2) = self._normalize_indexes((i1, i2))
+        if (i1, i2) in self:
+            return True
+        else:
+            sys.stderr.write(
+                'Attempting automerge of %d-%d...' % self.get_original_indexes(i1, i2)
+                )
+            try:
+                automerge(self[i1, 0].sha1, self[0, i2].sha1)
+                sys.stderr.write('success.\n')
+                return True
+            except AutomaticMergeFailed:
+                sys.stderr.write('failure.\n')
+                return False
+
+    def auto_outline(self):
+        """Complete the outline of this Block.
+
+        raise UnexpectedMergeFailure if automerging fails."""
+
+        # Check that all of the merges go through before recording any
+        # of them permanently.
+        merges = []
+
+        def do_merge(i1, commit1, i2, commit2, msg='Autofilling %d-%d...', record=True):
+            if (i1, i2) in self:
+                return self[i1,i2].sha1
+            try:
+                sys.stderr.write(msg % self.get_original_indexes(i1, i2))
+                merge = automerge(commit1, commit2)
+                sys.stderr.write('success.\n')
+            except AutomaticMergeFailed, e:
+                sys.stderr.write('unexpected conflict.  Backtracking...\n')
+                raise UnexpectedMergeFailure(str(e), i1, i2)
+            if record:
+                merges.append((i1, i2, merge))
+            return merge
+
+        i2 = self.len2 - 1
+        left = self[0, i2].sha1
+        for i1 in range(1, self.len1 - 1):
+            left = do_merge(i1, self[i1,0].sha1, i2, left)
+
+        i1 = self.len1 - 1
+        above = self[i1, 0].sha1
+        for i2 in range(1, self.len2 - 1):
+            above = do_merge(i1, above, i2, self[0,i2].sha1)
+
+        # We will compare two ways of doing the final "vertex" merge:
+        # as a continuation of the bottom edge, or as a continuation
+        # of the right edge.  We only accept it if both approaches
+        # succeed and give identical trees.
+        i1, i2 = self.len1 - 1, self.len2 - 1
+        vertex_v1 = do_merge(
+            i1, self[i1,0].sha1, i2, left,
+            msg='Autofilling %d-%d (first way)...',
+            record=False,
+            )
+        vertex_v2 = do_merge(
+            i1, above, i2, self[0,i2].sha1,
+            msg='Autofilling %d-%d (second way)...',
+            record=False,
+            )
+        if get_tree(vertex_v1) == get_tree(vertex_v2):
+            sys.stderr.write(
+                'The two ways of autofilling %d-%d agree.\n'
+                % self.get_original_indexes(i1, i2)
+                )
+        else:
+            sys.stderr.write(
+                'The two ways of autofilling %d-%d do not agree.  Backtracking...\n'
+                % self.get_original_indexes(i1, i2)
+                )
+            raise UnexpectedMergeFailure('Inconsistent vertex merges', i1, i2)
+
+        # Everything is OK.  Now reparent the actual vertex merge to
+        # have above and left as its parents:
+        merges.append((i1, i2, reparent(vertex_v1, [above, left])))
+
+        # Done!  Now we can record the results:
+        sys.stderr.write('Recording autofilled block %s.\n' % (self,))
+        for (i1, i2, merge) in merges:
+            self[i1, i2].record_merge(merge, MergeRecord.NEW_AUTO)
+
+    def auto_outline_frontier(self, merge_frontier=None):
+        """Try to outline the merge frontier of this block.
+
+        Return True iff some progress was made."""
+
+        if merge_frontier is None:
+            merge_frontier = MergeFrontier.compute_by_bisection(self)
+
+        if not merge_frontier:
+            # Nothing to do.
+            return False
+
+        best_block = max(merge_frontier, key=lambda block: block.get_area())
+
+        try:
+            best_block.auto_outline()
+        except UnexpectedMergeFailure, e:
+            # One of the merges that we expected to succeed in
+            # fact failed.
+            merge_frontier.remove_failure(e.i1, e.i2)
+            return self.auto_outline_frontier(merge_frontier)
+        else:
+            f1, f2 = merge_frontier.partition(best_block)
+            if f1:
+                f1.block.auto_outline_frontier(f1)
+            if f2:
+                f2.block.auto_outline_frontier(f2)
+            return True
+
+    # The codes in the 2D array returned from create_diagram()
+    MERGE_UNKNOWN = 0
+    MERGE_MANUAL = 1
+    MERGE_AUTOMATIC = 2
+    MERGE_BLOCKED = 3
+    MERGE_UNBLOCKED = 4
+
+    # A map {(is_known(), manual, is_blocked()) : integer constant}
+    MergeState = {
+        (False, False, False) : MERGE_UNKNOWN,
+        (False, False, True) : MERGE_BLOCKED,
+        (True, False, True) : MERGE_UNBLOCKED,
+        (True, True, True) : MERGE_UNBLOCKED,
+        (True, False, False) : MERGE_AUTOMATIC,
+        (True, True, False) : MERGE_MANUAL,
+        }
+
+    def create_diagram(self):
+        """Generate a diagram of this Block.
+
+        The returned diagram, is a nested list of integers forming a 2D array,
+        where the integer at diagram[i1][i2] is one of MERGE_UNKNOWN,
+        MERGE_MANUAL, MERGE_AUTOMATIC, MERGE_BLOCKED, or MERGE_UNBLOCKED,
+        representing the state of the commit at (i1, i2)."""
+
+        diagram = [[None for i2 in range(self.len2)] for i1 in range(self.len1)]
+
+        for i2 in range(self.len2):
+            for i1 in range(self.len1):
+                rec = self.get_value(i1, i2)
+                c = self.MergeState[
+                    rec.is_known(), rec.is_manual(), rec.is_blocked()]
+                diagram[i1][i2] = c
+
+        return diagram
+
+    def format_diagram(self, legend=None, diagram=None):
+        if legend is None:
+            legend = [
+                AnsiColor.D_GRAY + "?" + AnsiColor.END,
+                AnsiColor.B_GREEN + "*" + AnsiColor.END,
+                AnsiColor.B_GREEN + "." + AnsiColor.END,
+                AnsiColor.B_RED + "#" + AnsiColor.END,
+                AnsiColor.B_YELLOW + "@" + AnsiColor.END,
+                ]
+        if diagram is None:
+            diagram = self.create_diagram()
+        return [
+            [legend[diagram[i1][i2]] for i2 in range(self.len2)]
+            for i1 in range(self.len1)]
+
+    def write(self, f, legend=None, sep='', linesep='\n'):
+        diagram = self.format_diagram(legend)
+        for i2 in range(self.len2):
+            f.write(sep.join(diagram[i1][i2] for i1 in range(self.len1)) + linesep)
+
+    def writeppm(self, f):
+        f.write('P3\n')
+        f.write('%d %d 255\n' % (self.len1, self.len2,))
+        legend = ['127 127 0', '0 255 0', '0 127 0', '255 0 0', '127 0 0']
+        self.write(f, legend, sep='  ')
+
+
+class SubBlock(Block):
+    @staticmethod
+    def _convert_to_slice(i, len):
+        """Return (start, len) for the specified index.
+
+        i may be an integer or a slice with step equal to 1."""
+
+        if isinstance(i, int):
+            if i < 0:
+                i += len
+            i = slice(i, i + 1)
+        elif isinstance(i, slice):
+            if i.step is not None and i.step != 1:
+                raise ValueError('Index has a non-zero step size')
+        else:
+            raise ValueError('Index cannot be converted to a slice')
+
+        (start, stop, step) = i.indices(len)
+        return (start, stop - start)
+
+    def __init__(self, block, slice1, slice2):
+        (start1, len1) = self._convert_to_slice(slice1, block.len1)
+        (start2, len2) = self._convert_to_slice(slice2, block.len2)
+        Block.__init__(self, len1, len2)
+        if isinstance(block, SubBlock):
+            # Peel away one level of indirection:
+            self._block = block._block
+            self._start1 = start1 + block._start1
+            self._start2 = start2 + block._start2
+        else:
+            self._block = block
+            self._start1 = start1
+            self._start2 = start2
+
+    def get_original_indexes(self, i1, i2):
+        i1, i2 = self._normalize_indexes((i1, i2))
+        return self._block.get_original_indexes(i1 + self._start1, i2 + self._start2)
+
+    def convert_original_indexes(self, i1, i2):
+        (i1, i2) = self._block.convert_original_indexes(i1, i2)
+        if not (
+            self._start1 <= i1 < self._start1 + self.len1
+            and self._start2 <= i2 < self._start2 + self.len2
+            ):
+            raise IndexError('Indexes are not within block')
+        return (i1 - self._start1, i2 - self._start2)
+
+    def _set_value(self, i1, i2, sha1, flags):
+        self._check_indexes(i1, i2)
+        self._block._set_value(i1 + self._start1, i2 + self._start2, sha1, flags)
+
+    def get_value(self, i1, i2):
+        self._check_indexes(i1, i2)
+        return self._block.get_value(i1 + self._start1, i2 + self._start2)
+
+    def __str__(self):
+        return '%s[%d:%d,%d:%d]' % (
+            self._block,
+            self._start1, self._start1 + self.len1,
+            self._start2, self._start2 + self.len2,
+            )
+
+
+class MergeState(Block):
+    SOURCE_TABLE = {
+        'auto' : MergeRecord.SAVED_AUTO,
+        'manual' : MergeRecord.SAVED_MANUAL,
+        }
+
+    MERGE_STATE_RE = re.compile(
+        r"""
+        ^
+        refs\/imerge\/
+        (?P<name>[^\/]+)
+        \/state
+        $
+        """,
+        re.VERBOSE,
+        )
+
+    @staticmethod
+    def iter_existing_names():
+        """Iterate over the names of existing MergeStates in this repo."""
+
+        for line in check_output(['git', 'for-each-ref', 'refs/imerge',]).splitlines():
+            (sha1, type, refname) = line.split()
+            if type == 'blob':
+                m = MergeState.MERGE_STATE_RE.match(refname)
+                if m:
+                    yield m.group('name')
+
+    @staticmethod
+    def get_scratch_refname(name):
+        return 'refs/heads/imerge/%s' % (name,)
+
+    @staticmethod
+    def _read_state(name, sha1):
+        state_string = check_output(['git', 'cat-file', 'blob', sha1])
+        state = json.loads(state_string)
+
+        version = tuple(map(int, state['version'].split('.')))
+        if version[0] != STATE_VERSION[0] or version > STATE_VERSION:
+            raise Failure(
+                'The format of imerge %s (%s) is not compatible with this script version.'
+                % (name, state['version'],)
+                )
+        state['version'] = version
+        return state
+
+    @staticmethod
+    def check_exists(name):
+        """Verify that a MergeState with the given name exists.
+
+        Just check for the existence, readability, and compatible
+        version of the "state" reference.  If the reference doesn't
+        exist, just return False.  If it exists but is unusable for
+        some other reason, raise an exception."""
+
+        try:
+            call_silently(
+                ['git', 'check-ref-format', 'refs/imerge/%s' % (name,)]
+                )
+        except CalledProcessError:
+            raise Failure('Name %r is not a valid refname component!' % (name,))
+
+        state_refname = 'refs/imerge/%s/state' % (name,)
+        for line in check_output(['git', 'for-each-ref', state_refname]).splitlines():
+            (sha1, type, refname) = line.split()
+            if refname == state_refname and type == 'blob':
+                MergeState._read_state(name, sha1)
+                # If that didn't throw an exception:
+                return True
+        else:
+            return False
+
+    @staticmethod
+    def set_default_name(name):
+        """Set the default merge to the specified one.
+
+        name can be None to cause the default to be cleared."""
+
+        if name is None:
+            try:
+                check_call(['git', 'config', '--unset', 'imerge.default'])
+            except CalledProcessError, e:
+                if e.returncode == 5:
+                    # Value was not set
+                    pass
+                else:
+                    raise
+        else:
+            check_call(['git', 'config', 'imerge.default', name])
+
+    @staticmethod
+    def get_default_name():
+        """Get the name of the default merge, or None if none is currently set."""
+
+        try:
+            return check_output(['git', 'config', 'imerge.default']).rstrip()
+        except CalledProcessError:
+            return None
+
+    @staticmethod
+    def _check_no_merges(commits):
+        multiparent_commits = [
+            commit
+            for commit in commits
+            if len(get_commit_parents(commit)) > 1
+            ]
+        if multiparent_commits:
+            raise Failure(
+                'The following commits on the to-be-merged branch are merge commits:\n'
+                '    %s\n'
+                '--goal=\'rebase\' is not yet supported for branches that include merges.\n'
+                % ('\n    '.join(multiparent_commits),)
+                )
+
+    @staticmethod
+    def initialize(name, goal, tip1, tip2):
+        """Create and return a new MergeState object."""
+
+        if '/' in name:
+            raise Failure('Name %r must not include a slash character!' % (name,))
+
+        try:
+            call_silently(
+                ['git', 'check-ref-format', 'refs/imerge/%s' % (name,)]
+                )
+        except CalledProcessError:
+            raise Failure('Name %r is not a valid refname component!' % (name,))
+
+        if check_output(['git', 'for-each-ref', 'refs/imerge/%s' % (name,)]):
+            raise Failure('Name %r is already in use!' % (name,))
+
+        try:
+            merge_base = check_output(['git', 'merge-base', '--all', tip1, tip2]).splitlines()
+        except CalledProcessError, e:
+            raise Failure('Cannot compute merge base for %r and %r' % (tip1, tip2))
+        if not merge_base:
+            raise Failure('%r and %r do not have a common merge base' % (tip1, tip2))
+        if len(merge_base) > 1:
+            raise Failure('%r and %r do not have a unique merge base' % (tip1, tip2))
+
+        [merge_base] = merge_base
+
+        ancestry_path1 = set(rev_list('--ancestry-path', '%s..%s' % (merge_base, tip1)))
+        commits1 = [
+            sha1
+            for sha1 in rev_list('--first-parent', '%s..%s' % (merge_base, tip1))
+            if sha1 in ancestry_path1
+            ]
+        commits1.reverse()
+        if not commits1:
+            raise Failure(
+                'There are no commits on %r that are not already in %r' % (tip1, tip2)
+                )
+
+        ancestry_path2 = set(rev_list('--ancestry-path', '%s..%s' % (merge_base, tip2)))
+        commits2 = [
+            sha1
+            for sha1 in rev_list('--first-parent', '%s..%s' % (merge_base, tip2))
+            if sha1 in ancestry_path2
+            ]
+        commits2.reverse()
+        if not commits2:
+            raise Failure(
+                'There are no commits on %r that are not already in %r' % (tip2, tip1)
+                )
+
+        if goal == 'rebase':
+            MergeState._check_no_merges(commits2)
+
+        return MergeState(name, goal, merge_base, commits1, commits2, MergeRecord.NEW_MANUAL)
+
+    @staticmethod
+    def read(name):
+        merge_ref_re = re.compile(
+            r"""
+            ^
+            refs\/imerge\/
+            """ + re.escape(name) + r"""
+            \/(?P<source>auto|manual)\/
+            (?P<i1>0|[1-9][0-9]*)
+            \-
+            (?P<i2>0|[1-9][0-9]*)
+            $
+            """,
+            re.VERBOSE,
+            )
+
+        state_ref_re = re.compile(
+            r"""
+            ^
+            refs\/imerge\/
+            """ + re.escape(name) + r"""
+            \/state
+            $
+            """,
+            re.VERBOSE,
+            )
+
+        state = None
+
+        # A map {(i1, i2) : (sha1, source)}:
+        merges = {}
+
+        # refnames that were found but not understood:
+        unexpected = []
+
+        for line in check_output([
+                'git', 'for-each-ref', 'refs/imerge/%s' % (name,)
+                ]).splitlines():
+            (sha1, type, refname) = line.split()
+            m = merge_ref_re.match(refname)
+            if m:
+                if type != 'commit':
+                    raise Failure('Reference %r is not a commit!' % (refname,))
+                i1, i2 = int(m.group('i1')), int(m.group('i2'))
+                source = MergeState.SOURCE_TABLE[m.group('source')]
+                merges[i1, i2] = (sha1, source)
+                continue
+
+            m = state_ref_re.match(refname)
+            if m:
+                if type != 'blob':
+                    raise Failure('Reference %r is not a blob!' % (refname,))
+                state = MergeState._read_state(name, sha1)
+                continue
+
+            unexpected.append(refname)
+
+        if state is None:
+            raise Failure(
+                'No state found; it should have been a blob reference at '
+                '"refs/imerge/%s/state' % (name,)
+                )
+
+        goal = state['goal']
+        if goal not in ALLOWED_GOALS:
+            raise Failure('Goal %r, read from state, is not recognized.' % (goal,))
+
+        blockers = state.get('blockers', [])
+
+        if unexpected:
+            raise Failure(
+                'Unexpected reference(s) found in "refs/imerge/%s" namespace:\n    %s\n'
+                % (name, '\n    '.join(unexpected),)
+                )
+
+        # Find merge_base, commits1, and commits2:
+        (merge_base, source) = merges.pop((0, 0))
+        if source != MergeRecord.SAVED_MANUAL:
+            raise Failure('Merge base should be manual!')
+        commits1 = []
+        for i1 in itertools.count(1):
+            try:
+                (sha1, source) = merges.pop((i1, 0))
+                if source != MergeRecord.SAVED_MANUAL:
+                    raise Failure('Merge %d-0 should be manual!' % (i1,))
+                commits1.append(sha1)
+            except KeyError:
+                break
+
+        commits2 = []
+        for i2 in itertools.count(1):
+            try:
+                (sha1, source) = merges.pop((0, i2))
+                if source != MergeRecord.SAVED_MANUAL:
+                    raise Failure('Merge (0,%d) should be manual!' % (i2,))
+                commits2.append(sha1)
+            except KeyError:
+                break
+
+        state = MergeState(name, goal, merge_base, commits1, commits2, MergeRecord.SAVED_MANUAL)
+
+        # Now write the rest of the merges to state:
+        for ((i1, i2), (sha1, source)) in merges.iteritems():
+            if i1 == 0 and i2 >= state.len2:
+                raise Failure('Merge 0-%d is missing!' % (state.len2,))
+            if i1 >= state.len1 and i2 == 0:
+                raise Failure('Merge %d-0 is missing!' % (state.len1,))
+            if i1 >= state.len1 or i2 >= state.len2:
+                raise Failure(
+                    'Merge %d-%d is out of range [0:%d,0:%d]'
+                    % (i1, i2, state.len1, state.len2)
+                    )
+            state[i1, i2].record_merge(sha1, source)
+
+        # Record any blockers:
+        for (i1,i2) in blockers:
+            state[i1, i2].record_blocked(True)
+
+        return state
+
+    @staticmethod
+    def remove(name):
+        # If HEAD is the scratch refname, abort any in-progress
+        # commits and detach HEAD:
+        scratch_refname = MergeState.get_scratch_refname(name)
+        try:
+            head_refname = check_output(['git', 'symbolic-ref', '--quiet', 'HEAD']).strip()
+        except CalledProcessError:
+            head_refname = None
+        if head_refname == scratch_refname:
+            try:
+                # We don't use "git merge --abort" here because it was
+                # only added in git version 1.7.4.
+                check_call(['git', 'reset', '--merge'])
+            except CalledProcessError:
+                pass
+            # Detach head so that we can delete scratch_refname:
+            check_call([
+                    'git', 'update-ref', '--no-deref',
+                    '-m', 'Detach HEAD from %s' % (scratch_refname,),
+                    'HEAD', get_commit_sha1('HEAD'),
+                    ])
+
+        # Delete the scratch refname:
+        check_call([
+                'git', 'update-ref',
+                '-m', 'imerge %s: remove scratch reference' % (name,),
+                '-d', scratch_refname,
+                ])
+
+        # Remove any references referring to intermediate merges:
+        for line in check_output([
+                'git', 'for-each-ref', 'refs/imerge/%s' % (name,)
+                ]).splitlines():
+            (sha1, type, refname) = line.split()
+            try:
+                check_call([
+                        'git', 'update-ref',
+                        '-m', 'imerge: remove merge %r' % (name,),
+                        '-d', refname,
+                        ])
+            except CalledProcessError, e:
+                sys.stderr.write(
+                    'Warning: error removing reference %r: %s' % (refname, e)
+                    )
+
+        # If this merge was the default, unset the default:
+        if MergeState.get_default_name() == name:
+            MergeState.set_default_name(None)
+
+    def __init__(self, name, goal, merge_base, commits1, commits2, source):
+        Block.__init__(self, len(commits1) + 1, len(commits2) + 1)
+        self.name = name
+        self.goal = goal
+
+        # A simulated 2D array.  Values are None or MergeRecord instances.
+        self._data = [[None] * self.len2 for i1 in range(self.len1)]
+
+        self.get_value(0, 0).record_merge(merge_base, source)
+        for (i1, commit) in enumerate(commits1, 1):
+            self.get_value(i1, 0).record_merge(commit, source)
+        for (i2, commit) in enumerate(commits2, 1):
+            self.get_value(0, i2).record_merge(commit, source)
+
+    def set_goal(self, goal):
+        if goal not in ALLOWED_GOALS:
+            raise ValueError('%r is not an allowed goal' % (goal,))
+
+        if goal == 'rebase':
+            self._check_no_merges(
+                [self[0,i2].sha1 for i2 in range(1,self.len2)]
+                )
+
+        self.goal = goal
+
+    def _set_value(self, i1, i2, value):
+        self._data[i1][i2] = value
+
+    def get_value(self, i1, i2):
+        value = self._data[i1][i2]
+        # Missing values spring to life on first access:
+        if value is None:
+            value = MergeRecord()
+            self._data[i1][i2] = value
+        return value
+
+    def __contains__(self, index):
+        # Avoid creating new MergeRecord objects here.
+        (i1, i2) = self._normalize_indexes(index)
+        value = self._data[i1][i2]
+        return (value is not None) and value.is_known()
+
+    def auto_complete_frontier(self):
+        """Complete the frontier using automerges.
+
+        If progress is blocked before the frontier is complete, raise
+        a FrontierBlockedError.  Save the state as progress is
+        made."""
+
+        progress_made = False
+        try:
+            while True:
+                frontier = MergeFrontier.map_known_frontier(self)
+                frontier.auto_expand()
+                self.save()
+                progress_made = True
+        except BlockCompleteError:
+            return
+        except FrontierBlockedError, e:
+            self.save()
+            if not progress_made:
+                # Adjust the error message:
+                raise FrontierBlockedError(
+                    'No progress was possible; suggest manual merge of %d-%d'
+                    % (e.i1, e.i2),
+                    e.i1, e.i2,
+                    )
+            else:
+                raise
+
+    def find_index(self, commit):
+        """Return (i1,i2) for the specified commit.
+
+        Raise CommitNotFoundError if it is not known."""
+
+        for i2 in range(0, self.len2):
+            for i1 in range(0, self.len1):
+                if (i1, i2) in self:
+                    record = self[i1,i2]
+                    if record.sha1 == commit:
+                        return (i1, i2)
+        raise CommitNotFoundError(commit)
+
+    def incorporate_manual_merge(self, commit):
+        """Record commit as a manual merge of its parents.
+
+        Return the indexes (i1,i2) where it was recorded.  If the
+        commit is not usable for some reason, raise
+        ManualMergeUnusableError."""
+
+        parents = get_commit_parents(commit)
+        if len(parents) < 2:
+            raise ManualMergeUnusableError('it is not a merge', commit)
+        if len(parents) > 2:
+            raise ManualMergeUnusableError('it is an octopus merge', commit)
+        # Find the parents among our contents...
+        try:
+            (i1first, i2first) = self.find_index(parents[0])
+            (i1second, i2second) = self.find_index(parents[1])
+        except CommitNotFoundError:
+            raise ManualMergeUnusableError(
+                'its parents are not known merge commits', commit,
+                )
+        swapped = False
+        if i1first < i1second:
+            # Swap parents to make the parent from above the first parent:
+            (i1first, i2first, i1second, i2second) = (i1second, i2second, i2first, i1first)
+            swapped = True
+        if i1first != i1second + 1 or i2first != i2second - 1:
+            raise ManualMergeUnusableError(
+                'it is not a pairwise merge of adjacent parents', commit,
+                )
+        if swapped:
+            # Create a new merge with the parents in the conventional order:
+            commit = reparent(commit, [parents[1], parents[0]])
+
+        i1, i2 = i1first, i2second
+        self[i1, i2].record_merge(commit, MergeRecord.NEW_MANUAL)
+        return (i1, i2)
+
+    @staticmethod
+    def _is_ancestor(commit1, commit2):
+        """Return True iff commit1 is an ancestor (or equal to) commit2."""
+
+        if commit1 == commit2:
+            return True
+        else:
+            return int(
+                check_output([
+                        'git', 'rev-list', '--count', '--ancestry-path',
+                        '%s..%s' % (commit1, commit2,),
+                        ]).strip()
+                ) != 0
+
+    @staticmethod
+    def _set_refname(refname, commit, force=False):
+        try:
+            ref_oldval = get_commit_sha1(refname)
+        except ValueError:
+            # refname doesn't already exist; simply point it at commit:
+            check_call(['git', 'update-ref', refname, commit])
+            checkout(refname)
+        else:
+            # refname already exists.  This has two ramifications:
+            # 1. HEAD might point at it
+            # 2. We may only fast-forward it (unless force is set)
+            try:
+                head_refname = check_output(['git', 'symbolic-ref', '--quiet', 'HEAD']).strip()
+            except CalledProcessError:
+                head_refname = None
+
+            if not force:
+                if not MergeState._is_ancestor(ref_oldval, commit):
+                    raise Failure(
+                        '%s cannot be fast-forwarded to %s!' % (refname, commit)
+                        )
+
+            if head_refname == refname:
+                check_call(['git', 'reset', '--hard', commit])
+            else:
+                check_call([
+                        'git', 'update-ref',
+                        '-m', 'imerge: recording final merge',
+                        refname, commit,
+                        ])
+                checkout(refname)
+
+    def simplify_to_rebase_with_history(self, refname, force=False):
+        i1 = self.len1 - 1
+        for i2 in range(1, self.len2):
+            if not (i1, i2) in self:
+                raise Failure(
+                    'Cannot simplify to rebase-with-history because '
+                    'merge %d-%d is not yet done'
+                    % (i1, i2)
+                    )
+
+        commit = self[i1, 0].sha1
+        for i2 in range(1, self.len2):
+            orig = self[0, i2].sha1
+            tree = get_tree(self[i1, i2].sha1)
+
+            # Create a commit, copying the old log message:
+            commit = commit_tree(tree, [commit, orig], msg=get_log_message(orig))
+
+        self._set_refname(refname, commit, force=force)
+
+    def simplify_to_rebase(self, refname, force=False):
+        i1 = self.len1 - 1
+        for i2 in range(1, self.len2):
+            if not (i1, i2) in self:
+                raise Failure(
+                    'Cannot simplify to rebase because merge %d-%d is not yet done'
+                    % (i1, i2)
+                    )
+
+        commit = self[i1, 0].sha1
+        for i2 in range(1, self.len2):
+            orig = self[0, i2].sha1
+            tree = get_tree(self[i1, i2].sha1)
+            authordata = get_author_info(orig)
+
+            # Create a commit, copying the old log message and author info:
+            commit = commit_tree(
+                tree, [commit], msg=get_log_message(orig), metadata=authordata,
+                )
+
+        self._set_refname(refname, commit, force=force)
+
+    def simplify_to_merge(self, refname, force=False):
+        if not (-1, -1) in self:
+            raise Failure(
+                'Cannot simplify to merge because merge %d-%d is not yet done'
+                % (self.len1 - 1, self.len2 - 1)
+                )
+        tree = get_tree(self[-1, -1].sha1)
+        parents = [self[-1,0].sha1, self[0,-1].sha1]
+
+        # Create a preliminary commit with a generic commit message:
+        sha1 = commit_tree(
+            tree, parents,
+            msg='Merge commit %s into commit %s' % (parents[1], parents[0]),
+            )
+
+        self._set_refname(refname, sha1, force=force)
+
+        # Now let the user edit the commit log message:
+        check_call(['git', 'commit', '--amend'])
+
+    def simplify(self, refname, force=False):
+        """Simplify this MergeState and save the result to refname.
+
+        The merge must be complete before calling this method."""
+
+        if self.goal == 'rebase-with-history':
+            self.simplify_to_rebase_with_history(refname, force=force)
+        elif self.goal == 'rebase':
+            self.simplify_to_rebase(refname, force=force)
+        elif self.goal == 'merge':
+            self.simplify_to_merge(refname, force=force)
+        else:
+            raise ValueError('Invalid value for goal (%r)' % (self.goal,))
+
+    def save(self):
+        """Write the current MergeState to the repository."""
+
+        blockers = []
+        for i2 in range(0, self.len2):
+            for i1 in range(0, self.len1):
+                record = self[i1,i2]
+                if record.is_known():
+                    record.save(self.name, i1, i2)
+                if record.is_blocked():
+                    blockers.append((i1, i2))
+
+        state = dict(
+            version='.'.join(map(str, STATE_VERSION)),
+            goal=self.goal,
+            blockers=blockers,
+            )
+        state_string = json.dumps(state, sort_keys=True) + '\n'
+
+        cmd = ['git', 'hash-object', '-t', 'blob', '-w', '--stdin']
+        p = subprocess.Popen(cmd, stdin=subprocess.PIPE, stdout=subprocess.PIPE)
+        (out, err) = p.communicate(state_string)
+        retcode = p.poll()
+        if retcode:
+            raise CalledProcessError(retcode, cmd)
+        sha1 = out.strip()
+        check_call([
+                'git', 'update-ref',
+                '-m', 'imerge %r: Record state' % (self.name,),
+                'refs/imerge/%s/state' % (self.name,),
+                sha1,
+                ])
+
+    def __str__(self):
+        return 'MergeState(%r, goal=%r)' % (self.name, self.goal,)
+
+
+def request_user_merge(merge_state, i1, i2):
+    """Prepare the working tree for the user to do a manual merge.
+
+    It is assumed that the merge above and to the left of (i1, i2) are
+    already done."""
+
+    above = merge_state[i1, i2 - 1]
+    left = merge_state[i1 - 1, i2]
+    if not above.is_known() or not left.is_known():
+        raise RuntimeError('The parents of merge %d-%d are not ready' % (i1, i2))
+    refname = MergeState.get_scratch_refname(merge_state.name)
+    check_call([
+            'git', 'update-ref',
+            '-m', 'imerge %r: Prepare merge %d-%d' % (merge_state.name, i1, i2,),
+            refname, above.sha1,
+            ])
+    checkout(refname)
+    try:
+        check_call([
+                'git', 'merge', '--no-commit',
+                '-m', 'Merge %d-%d of incremental merge \'%s\'' % (i1, i2, merge_state.name,),
+                left.sha1,
+                ])
+    except CalledProcessError:
+        # We expect an error (otherwise we would have automerged!)
+        pass
+    sys.stderr.write(
+        '\n'
+        'Original first commit:\n'
+        )
+    check_call(['git', '--no-pager', 'log', '--no-walk', merge_state[i1,0].sha1])
+    sys.stderr.write(
+        '\n'
+        'Original second commit:\n'
+        )
+    check_call(['git', '--no-pager', 'log', '--no-walk', merge_state[0,i2].sha1])
+    sys.stderr.write(
+        '\n'
+        'There was a conflict merging commit %d-%d, shown above.\n'
+        'Please resolve the conflict, commit the result, then type\n'
+        '\n'
+        '    git-imerge continue\n'
+        % (i1, i2)
+        )
+
+def incorporate_user_merge(merge_state):
+    """If the user has done a merge for us, incorporate the results.
+
+    If reference refs/heads/imerge/NAME exists, try to incorporate it
+    into merge_state, delete the reference, and return (i1,i2)
+    corresponding to the merge.  If the reference cannot be used,
+    raise NoManualMergeError().  If the reference exists but cannot be
+    used, raise a ManualMergeUnusableError.  This function must be
+    called with a clean work tree."""
+
+    refname = MergeState.get_scratch_refname(merge_state.name)
+    try:
+        commit = get_commit_sha1(refname)
+    except ValueError:
+        raise NoManualMergeError('There was no merge at %s!' % (refname,))
+
+    merge_frontier = MergeFrontier.map_known_frontier(merge_state)
+
+    # This might throw ManualMergeUnusableError:
+    (i1, i2) = merge_state.incorporate_manual_merge(commit)
+
+    try:
+        headref = check_output(['git', 'symbolic-ref', '-q', 'HEAD']).strip()
+    except CalledProcessError:
+        pass
+    else:
+        if headref == refname:
+            # Detach head so that we can delete refname.
+            check_call([
+                    'git', 'update-ref', '--no-deref',
+                    '-m', 'Detach HEAD from %s' % (refname,),
+                    'HEAD', commit,
+                    ])
+
+    check_call([
+            'git', 'update-ref',
+            '-m', 'imerge %s: remove scratch reference' % (merge_state.name,),
+            '-d', refname,
+            ])
+
+    try:
+        # This might throw NotABlockingCommitError:
+        unblocked_block = merge_frontier.get_affected_blocker_block(i1, i2)
+        unblocked_block[1,1].record_blocked(False)
+        sys.stderr.write(
+            'Merge has been recorded for merge %d-%d.\n'
+            % unblocked_block.get_original_indexes(1, 1)
+            )
+    except NotABlockingCommitError:
+        raise
+    finally:
+        merge_state.save()
+
+
+def choose_merge_name(name, default_to_unique=True):
+    # If a name was specified, try to use it and fail if not possible:
+    if name is not None:
+        if not MergeState.check_exists(name):
+            raise Failure('There is no incremental merge called \'%s\'!' % (name,))
+        MergeState.set_default_name(name)
+        return name
+
+    # A name was not specified.  Try to use the default name:
+    default_name = MergeState.get_default_name()
+    if default_name:
+        if MergeState.check_exists(default_name):
+            return default_name
+        else:
+            # There's no reason to keep the invalid default around:
+            MergeState.set_default_name(None)
+            raise Failure(
+                'Warning: The default incremental merge \'%s\' has disappeared.\n'
+                '(The setting imerge.default has been cleared.)\n'
+                'Please select an incremental merge using --name'
+                % (default_name,)
+                )
+
+    if default_to_unique:
+        # If there is exactly one imerge, set it to be the default and use it.
+        names = list(MergeState.iter_existing_names())
+        if len(names) == 1 and MergeState.check_exists(names[0]):
+            MergeState.set_default_name(names[0])
+            return names[0]
+
+    raise Failure('Please select an incremental merge using --name')
+
+
+def read_merge_state(name=None):
+    return MergeState.read(choose_merge_name(name))
+
+
+@Failure.wrap
+def main(args):
+    parser = argparse.ArgumentParser(
+        description=__doc__,
+        formatter_class=argparse.RawDescriptionHelpFormatter,
+        )
+    subparsers = parser.add_subparsers(dest='subcommand', help='sub-command')
+
+    parser_start = subparsers.add_parser(
+        'start',
+        help=(
+            'start a new incremental merge '
+            '(equivalent to "init" followed by "continue")'
+            ),
+        )
+    parser_start.add_argument(
+        '--name', action='store', default=None,
+        help='name to use for this incremental merge',
+        )
+    parser_start.add_argument(
+        '--goal',
+        action='store', default=DEFAULT_GOAL,
+        choices=ALLOWED_GOALS,
+        help='the goal of the incremental merge',
+        )
+    #parser_start.add_argument(
+    #    '--conflicts', ...
+    #    action='store', default='pairwise',
+    #    choices=['pairwise', 'fewest'],
+    #    help='what sort of conflicts will be presented to the user',
+    #    )
+    parser_start.add_argument(
+        '--first-parent', action='store_true', default=None,
+        help=(
+            'handle only the first parent commits '
+            '(this option is currently required)'
+            ),
+        )
+    parser_start.add_argument(
+        'branch', action='store',
+        help='the tip of the branch to be merged into HEAD',
+        )
+
+    parser_continue = subparsers.add_parser(
+        'continue',
+        help=(
+            'record the merge at branch imerge/NAME '
+            'and start the next step of the merge '
+            '(equivalent to "record" followed by "autofill" '
+            'and then sets up the working copy with the next '
+            'conflict that has to be resolved manually)'
+            ),
+        )
+    parser_continue.add_argument(
+        '--name', action='store', default=None,
+        help='name of merge to continue',
+        )
+
+    parser_finish = subparsers.add_parser(
+        'finish',
+        help=(
+            'simplify then remove a completed incremental merge '
+            '(equivalent to "simplify" followed by "remove")'
+            ),
+        )
+    parser_finish.add_argument(
+        '--name', action='store', default=None,
+        help='name of merge to finish',
+        )
+    parser_finish.add_argument(
+        '--goal',
+        action='store', default=None,
+        choices=ALLOWED_GOALS,
+        help=(
+            'the type of simplification to be made '
+            '(default is the value provided to "init" or "start")'
+            ),
+        )
+    parser_finish.add_argument(
+        '--branch',
+        action='store', default=None,
+        help=(
+            'the name of the branch to which to store the result '
+            '(default is the name of the merge).   If '
+            'BRANCH already exists then it must be able to be '
+            'fast-forwarded to the result unless the --force option is '
+            'specified.'
+            ),
+        )
+    parser_finish.add_argument(
+        '--force',
+        action='store_true', default=False,
+        help='allow the target branch to be updated in a non-fast-forward manner',
+        )
+
+    parser_diagram = subparsers.add_parser(
+        'diagram',
+        help='display a diagram of the current state of a merge',
+        )
+    parser_diagram.add_argument(
+        '--name', action='store', default=None,
+        help='name of merge to diagram',
+        )
+    parser_diagram.add_argument(
+        '--commits', action='store_true', default=False,
+        help='show the merges that have been made so far',
+        )
+    parser_diagram.add_argument(
+        '--frontier', action='store_true', default=False,
+        help='show the current merge frontier',
+        )
+    parser_diagram.add_argument(
+        '--html', action='store', default=None,
+        help='generate HTML diagram showing the current merge frontier',
+        )
+    parser_diagram.add_argument(
+        '--color', dest='color', action='store_true', default=None,
+        help='draw diagram with colors',
+        )
+    parser_diagram.add_argument(
+        '--no-color', dest='color', action='store_false',
+        help='draw diagram without colors',
+        )
+
+    parser_list = subparsers.add_parser(
+        'list',
+        help=(
+            'list the names of incremental merges that are currently in progress.  '
+            'The active merge is shown with an asterisk next to it.'
+            ),
+        )
+
+    parser_init = subparsers.add_parser(
+        'init',
+        help='initialize a new incremental merge',
+        )
+    parser_init.add_argument(
+        '--name', action='store', default=None,
+        help='name to use for this incremental merge',
+        )
+    parser_init.add_argument(
+        '--goal',
+        action='store', default=DEFAULT_GOAL,
+        choices=ALLOWED_GOALS,
+        help='the goal of the incremental merge',
+        )
+    #parser_init.add_argument(
+    #    '--conflicts', ...
+    #    action='store', default='pairwise',
+    #    choices=['pairwise', 'fewest'],
+    #    help='what sort of conflicts will be presented to the user',
+    #    )
+    parser_init.add_argument(
+        '--first-parent', action='store_true', default=None,
+        help=(
+            'handle only the first parent commits '
+            '(this option is currently required)'
+            ),
+        )
+    parser_init.add_argument(
+        'branch', action='store',
+        help='the tip of the branch to be merged into HEAD',
+        )
+
+    parser_record = subparsers.add_parser(
+        'record',
+        help='record the merge at branch imerge/NAME',
+        )
+    parser_record.add_argument(
+        '--name', action='store', default=None,
+        help='name of merge to which the merge should be added',
+        )
+
+    parser_autofill = subparsers.add_parser(
+        'autofill',
+        help='autofill non-conflicting merges',
+        )
+    parser_autofill.add_argument(
+        '--name', action='store', default=None,
+        help='name of merge to autofill',
+        )
+
+    parser_simplify = subparsers.add_parser(
+        'simplify',
+        help=(
+            'simplify a completed incremental merge by discarding unneeded '
+            'intermediate merges and cleaning up the ancestry of the commits '
+            'that are retained'
+            ),
+        )
+    parser_simplify.add_argument(
+        '--name', action='store', default=None,
+        help='name of merge to simplify',
+        )
+    parser_simplify.add_argument(
+        '--goal',
+        action='store', default=None,
+        choices=ALLOWED_GOALS,
+        help=(
+            'the type of simplification to be made '
+            '(default is the value provided to "init" or "start")'
+            ),
+        )
+    parser_simplify.add_argument(
+        '--branch',
+        action='store', default=None,
+        help=(
+            'the name of the branch to which to store the result '
+            '(default is the name of the merge).   If '
+            'BRANCH already exists then it must be able to be '
+            'fast-forwarded to the result unless the --force option is '
+            'specified.'
+            ),
+        )
+    parser_simplify.add_argument(
+        '--force',
+        action='store_true', default=False,
+        help='allow the target branch to be updated in a non-fast-forward manner',
+        )
+
+    parser_remove = subparsers.add_parser(
+        'remove',
+        help='irrevocably remove an incremental merge',
+        )
+    parser_remove.add_argument(
+        '--name', action='store', default=None,
+        help='name of incremental merge to remove',
+        )
+
+    parser_reparent = subparsers.add_parser(
+        'reparent',
+        help='change the parents of the HEAD commit',
+        )
+    parser_reparent.add_argument(
+        'parents', nargs='*', help='[PARENT...]',
+        )
+
+    options = parser.parse_args(args)
+
+    # Set an environment variable GIT_IMERGE=1 while we are running.
+    # This makes it possible for hook scripts etc. to know that they
+    # are being run within git-imerge, and should perhaps behave
+    # differently.  In the future we might make the value more
+    # informative, like GIT_IMERGE=[automerge|autofill|...].
+    os.environ['GIT_IMERGE'] = '1'
+
+    if options.subcommand == 'list':
+        default_merge = MergeState.get_default_name()
+        for name in MergeState.iter_existing_names():
+            if name == default_merge:
+                sys.stdout.write('* %s\n' % (name,))
+            else:
+                sys.stdout.write('  %s\n' % (name,))
+    elif options.subcommand == 'init':
+        require_clean_work_tree('proceed')
+
+        if not options.first_parent:
+            parser.error(
+                'The --first-parent option is currently required for the "init" command'
+                )
+        if not options.name:
+            parser.error(
+                'Please specify the --name to be used for this incremental merge'
+                )
+        merge_state = MergeState.initialize(
+            options.name, options.goal, 'HEAD', options.branch,
+            )
+        merge_state.save()
+        MergeState.set_default_name(options.name)
+    elif options.subcommand == 'start':
+        require_clean_work_tree('proceed')
+
+        if not options.first_parent:
+            parser.error(
+                'The --first-parent option is currently required for the "start" command'
+                )
+        if not options.name:
+            parser.error(
+                'Please specify the --name to be used for this incremental merge'
+                )
+        merge_state = MergeState.initialize(
+            options.name, options.goal, 'HEAD', options.branch,
+            )
+        merge_state.save()
+        MergeState.set_default_name(options.name)
+
+        try:
+            merge_state.auto_complete_frontier()
+        except FrontierBlockedError, e:
+            request_user_merge(merge_state, e.i1, e.i2)
+        else:
+            sys.stderr.write('Merge is complete!\n')
+    elif options.subcommand == 'remove':
+        MergeState.remove(choose_merge_name(options.name, default_to_unique=False))
+    elif options.subcommand == 'continue':
+        require_clean_work_tree('proceed')
+        merge_state = read_merge_state(options.name)
+        try:
+            incorporate_user_merge(merge_state)
+        except NoManualMergeError:
+            pass
+        except NotABlockingCommitError, e:
+            raise Failure(str(e))
+        except ManualMergeUnusableError, e:
+            raise Failure(str(e))
+
+        try:
+            merge_state.auto_complete_frontier()
+        except FrontierBlockedError, e:
+            request_user_merge(merge_state, e.i1, e.i2)
+        else:
+            sys.stderr.write('Merge is complete!\n')
+    elif options.subcommand == 'record':
+        require_clean_work_tree('proceed')
+        merge_state = read_merge_state(options.name)
+        try:
+            incorporate_user_merge(merge_state)
+        except NoManualMergeError, e:
+            raise Failure(str(e))
+        except NotABlockingCommitError:
+            raise Failure(str(e))
+        except ManualMergeUnusableError, e:
+            raise Failure(str(e))
+
+        try:
+            merge_state.auto_complete_frontier()
+        except FrontierBlockedError, e:
+            pass
+        else:
+            sys.stderr.write('Merge is complete!\n')
+    elif options.subcommand == 'autofill':
+        require_clean_work_tree('proceed')
+        merge_state = read_merge_state(options.name)
+        with TemporaryHead():
+            try:
+                merge_state.auto_complete_frontier()
+            except FrontierBlockedError, e:
+                raise Failure(str(e))
+    elif options.subcommand == 'simplify':
+        require_clean_work_tree('proceed')
+        merge_state = read_merge_state(options.name)
+        merge_frontier = MergeFrontier.map_known_frontier(merge_state)
+        if not merge_frontier.is_complete():
+            raise Failure('Merge %s is not yet complete!' % (merge_state.name,))
+        refname = 'refs/heads/%s' % ((options.branch or merge_state.name),)
+        if options.goal is not None:
+            merge_state.set_goal(options.goal)
+            merge_state.save()
+        merge_state.simplify(refname, force=options.force)
+    elif options.subcommand == 'finish':
+        require_clean_work_tree('proceed')
+        options.name = choose_merge_name(options.name, default_to_unique=False)
+        merge_state = read_merge_state(options.name)
+        merge_frontier = MergeFrontier.map_known_frontier(merge_state)
+        if not merge_frontier.is_complete():
+            raise Failure('Merge %s is not yet complete!' % (merge_state.name,))
+        refname = 'refs/heads/%s' % ((options.branch or merge_state.name),)
+        if options.goal is not None:
+            merge_state.set_goal(options.goal)
+            merge_state.save()
+        merge_state.simplify(refname, force=options.force)
+        MergeState.remove(options.name)
+    elif options.subcommand == 'diagram':
+        if not (options.commits or options.frontier):
+            options.frontier = True
+        if not (options.color or (options.color is None and sys.stdout.isatty())):
+            AnsiColor.disable()
+
+        merge_state = read_merge_state(options.name)
+        if options.commits:
+            merge_state.write(sys.stdout)
+            sys.stdout.write('\n')
+        if options.frontier:
+            merge_frontier = MergeFrontier.map_known_frontier(merge_state)
+            merge_frontier.write(sys.stdout)
+            sys.stdout.write('\n')
+        if options.html:
+            merge_frontier = MergeFrontier.map_known_frontier(merge_state)
+            html = open(options.html, "w")
+            merge_frontier.write_html(html, merge_state.name)
+            html.close()
+        sys.stdout.write(
+            'Key:\n'
+            )
+        if options.frontier:
+            sys.stdout.write(
+                '  |,-,+ = rectangles forming current merge frontier\n'
+                )
+        sys.stdout.write(
+            '  * = merge done manually\n'
+            '  . = merge done automatically\n'
+            '  # = conflict that is currently blocking progress\n'
+            '  @ = merge was blocked but has been resolved\n'
+            '  ? = no merge recorded\n'
+            '\n'
+            )
+    elif options.subcommand == 'reparent':
+        try:
+            commit_sha1 = get_commit_sha1('HEAD')
+        except ValueError:
+            sys.exit('HEAD is not a valid commit')
+
+        try:
+            parent_sha1s = map(get_commit_sha1, options.parents)
+        except ValueError, e:
+            sys.exit(e.message)
+
+        sys.stdout.write('%s\n' % (reparent(commit_sha1, parent_sha1s),))
+    else:
+        parser.error('Unrecognized subcommand')
+
+
+main(sys.argv[1:])
+