update git imerge

1 files changed, 482 insertions, 236 deletions

diff --git a/bin/git/git-imerge b/bin/git/git-imerge
index f2e7772..457fdab 100755
--- a/bin/git/git-imerge
+++ b/bin/git/git-imerge
@@ -1,4 +1,4 @@
-#! /usr/bin/env python2
+#! /usr/bin/env python
 
 # Copyright 2012-2013 Michael Haggerty <mhagger@alum.mit.edu>
 #
@@ -25,25 +25,9 @@ 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.
+repository as references under 'refs/imerge/NAME'.
 
 An incremental merge can be interrupted and resumed arbitrarily, or
 even pushed to a server to allow somebody else to work on it.
@@ -51,148 +35,76 @@ even pushed to a server to allow somebody else to work on it.
 
 Instructions:
 
-For basic operation, you only need to know three git-imerge commands.
-To merge BRANCH2 into BRANCH1 or rebase BRANCH2 onto BRANCH1,
-
-    git checkout BRANCH1
-    git-imerge start --name=NAME --goal=GOAL --first-parent BRANCH2
-    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).
+To start an incremental merge or rebase, use one of the following
+commands:
 
-    GOAL describes how you want the "finish" or "simplify" command to
-        record the results of the incremental merge in your project's
-        permanent history.  The "goal" of the incremental merge can be
-        one of the following:
+    git-imerge merge BRANCH      # analogous to "git merge BRANCH"
+    git-imerge rebase BRANCH     # analogous to "git rebase BRANCH"
+    git-imerge start --name=NAME --goal=GOAL --first-parent BRANCH
 
-        * merge
-            keep only a simple merge of the second branch into the
-            first branch, discarding all intermediate merges.  The end
-            result is similar to what you would get from
+Then the tool will present conflicts to you one at a time, similar to
+"git rebase --incremental".  Resolve each conflict, and then
 
-                git checkout BRANCH1
-                git merge BRANCH2
+    git add FILE...
+    git-imerge continue
 
-        * rebase
-            keep the versions of the commits from the second branch
-            rebased onto the first branch.  The end result is similar
-            to what you would get from
+You can view your progress at any time with
 
-                git checkout BRANCH2
-                git rebase BRANCH1
+    git-imerge diagram
 
-        * rebase-with-history
-            like rebase, except that it retains the old versions of
-            the rebased commits in the history.  It is equivalent to
-            merging the commits from BRANCH2 into BRANCH1, one commit
-            at a time.  In other words, it transforms this:
+When you have resolved all of the conflicts, simplify and record the
+result by typing
 
-                o---o---o---o          BRANCH1
-                     \
-                      A---B---C---D    BRANCH2
-
-            into this:
-
-                o---o---o---o---A'--B'--C'--D'   NEW_BRANCH
-                     \         /   /   /   /
-                      --------A---B---C---D
-
-            It is safe to rebase an already-published branch using this
-            approach.  See [3] for more information.
-
-        * full
-            don't simplify the incremental merge at all: do all of the
-            intermediate merges and retain them all in the permanent
-            history.
-
-For the full documentation, type
-
-    git-imerge --help
+    git-imerge finish
 
-and
+To get more help about any git-imerge subcommand, type
 
     git-imerge SUBCOMMAND --help
 
-
-[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
-
 """
 
+from __future__ import absolute_import
+from __future__ import division
+from __future__ import print_function
+from __future__ import unicode_literals
+
+import locale
 import sys
 import re
 import subprocess
+from subprocess import CalledProcessError
+from subprocess import check_call
 import itertools
 import functools
 import argparse
-from cStringIO import StringIO
+from io 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
+
+PREFERRED_ENCODING = locale.getpreferredencoding()
+
+
+# Define check_output() for ourselves, including decoding of the
+# output into PREFERRED_ENCODING:
+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 = communicate(process)[0]
+    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, 2, 0)
+STATE_VERSION = (1, 3, 0)
 
 ZEROS = '0' * 40
 
@@ -222,7 +134,7 @@ class Failure(Exception):
         def wrapper(*args, **kw):
             try:
                 return f(*args, **kw)
-            except klass, e:
+            except klass as e:
                 sys.exit(str(e))
 
         return wrapper
@@ -276,7 +188,7 @@ def iter_neighbors(iterable):
     i = iter(iterable)
 
     try:
-        last = i.next()
+        last = next(i)
     except StopIteration:
         return
 
@@ -312,12 +224,25 @@ def call_silently(cmd):
         NULL = subprocess.PIPE
 
     p = subprocess.Popen(cmd, stdout=NULL, stderr=NULL)
-    (out,err) = p.communicate()
+    p.communicate()
     retcode = p.wait()
     if retcode:
         raise CalledProcessError(retcode, cmd)
 
 
+def communicate(process, input=None):
+    """Return decoded output from process."""
+    if input is not None:
+        input = input.encode(PREFERRED_ENCODING)
+
+    output, error = process.communicate(input)
+
+    output = None if output is None else output.decode(PREFERRED_ENCODING)
+    error = None if error is None else error.decode(PREFERRED_ENCODING)
+
+    return (output, error)
+
+
 class UncleanWorkTreeError(Failure):
     pass
 
@@ -332,7 +257,7 @@ def require_clean_work_tree(action):
         ['git', 'rev-parse', '--verify', 'HEAD'],
         stdout=subprocess.PIPE, stderr=subprocess.PIPE,
         )
-    _unused, err = process.communicate()
+    err = communicate(process)[1]
     retcode = process.poll()
     if retcode:
         raise UncleanWorkTreeError(err.rstrip())
@@ -341,7 +266,7 @@ def require_clean_work_tree(action):
         ['git', 'update-index', '-q', '--ignore-submodules', '--refresh'],
         stdout=subprocess.PIPE, stderr=subprocess.PIPE,
         )
-    out, err = process.communicate()
+    out, err = communicate(process)
     retcode = process.poll()
     if retcode:
         raise UncleanWorkTreeError(err.rstrip() or out.rstrip())
@@ -367,6 +292,21 @@ def require_clean_work_tree(action):
         raise UncleanWorkTreeError('\n'.join(error))
 
 
+class InvalidBranchNameError(Failure):
+    pass
+
+
+def check_branch_name_format(name):
+    """Check that name is a valid branch name."""
+
+    try:
+        call_silently(
+            ['git', 'check-ref-format', 'refs/heads/%s' % (name,)]
+            )
+    except CalledProcessError:
+        raise InvalidBranchNameError('Name %r is not a valid branch name!' % (name,))
+
+
 def rev_parse(arg):
     return check_output(['git', 'rev-parse', '--verify', '--quiet', arg]).strip()
 
@@ -434,9 +374,9 @@ def get_author_info(commit):
         ]).strip().split('\x00')
 
     return {
-        'GIT_AUTHOR_NAME': a[0],
-        'GIT_AUTHOR_EMAIL': a[1],
-        'GIT_AUTHOR_DATE': a[2],
+        str('GIT_AUTHOR_NAME'): str(a[0]),
+        str('GIT_AUTHOR_EMAIL'): str(a[1]),
+        str('GIT_AUTHOR_DATE'): str(a[2]),
         }
 
 
@@ -461,7 +401,7 @@ def commit_tree(tree, parents, msg, metadata=None):
     process = subprocess.Popen(
         cmd, env=env, stdin=subprocess.PIPE, stdout=subprocess.PIPE,
         )
-    out, err = process.communicate(msg)
+    out = communicate(process, input=msg)[0]
     retcode = process.poll()
 
     if retcode:
@@ -473,6 +413,51 @@ def commit_tree(tree, parents, msg, metadata=None):
     return out.strip()
 
 
+def get_boundaries(tip1, tip2):
+    """Get the boundaries of an incremental merge.
+
+    Given the tips of two branches that should be merged, return
+    (merge_base, commits1, commits2) describing the edges of the
+    imerge.  Raise Failure if there are any problems."""
+
+    try:
+        merge_base = check_output(['git', 'merge-base', '--all', tip1, tip2]).splitlines()
+    except CalledProcessError:
+        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)
+            )
+
+    return (merge_base, commits1, commits2)
+
+
 class TemporaryHead(object):
     """A context manager that records the current HEAD state then restores it.
 
@@ -495,7 +480,7 @@ class TemporaryHead(object):
                     '-m', self.message, 'HEAD',
                     self.head_name,
                     ])
-            except Exception, e:
+            except Exception as e:
                 raise Failure(
                     'Could not restore HEAD to %r!:    %s\n'
                     % (self.head_name, e.message,)
@@ -503,7 +488,7 @@ class TemporaryHead(object):
             else:
                 try:
                     check_call(['git', 'reset', '--hard', self.orig_head])
-                except Exception, e:
+                except Exception as e:
                     raise Failure(
                         'Could not restore HEAD to %r!:    %s\n'
                         % (self.orig_head, e.message,)
@@ -553,7 +538,7 @@ def reparent(commit, parent_sha1s, msg=None):
         ['git', 'hash-object', '-t', 'commit', '-w', '--stdin'],
         stdin=subprocess.PIPE, stdout=subprocess.PIPE,
         )
-    out, err = process.communicate(new_commit.getvalue())
+    out = communicate(process, input=new_commit.getvalue())[0]
     retcode = process.poll()
     if retcode:
         raise Failure('Could not reparent commit %s' % (commit,))
@@ -910,7 +895,7 @@ class MergeFrontier(object):
         i1 = 1
         i2 = find_first_false(
             lambda i: block.is_mergeable(i1, i),
-            1, block.len2,
+            2, block.len2,
             )
 
         # Now we know that (1,i2-1) is mergeable but (1,i2) is not;
@@ -954,9 +939,11 @@ class MergeFrontier(object):
             # 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])
+            if (
+                i1 == block.len1 - 1
+                or block.is_mergeable(block.len1 - 1, i2 - 1)
+                ):
+                blocks.append(block[:block.len1,:i2])
                 break
             else:
                 i1 = find_first_false(
@@ -981,13 +968,13 @@ class MergeFrontier(object):
             # 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):
+            if i2 - 1 == 1 or not block.is_mergeable(i1, 1):
+                break
+            else:
                 i2 = find_first_false(
                     lambda i: block.is_mergeable(i1, i),
                     2, i2 - 1,
                     )
-            else:
-                break
 
         return MergeFrontier(block, blocks)
 
@@ -1002,6 +989,11 @@ class MergeFrontier(object):
 
         return iter(self.blocks)
 
+    def __bool__(self):
+        """Return True iff this frontier has no completed parts."""
+
+        return bool(self.blocks)
+
     def __nonzero__(self):
         """Return True iff this frontier has no completed parts."""
 
@@ -1032,7 +1024,7 @@ class MergeFrontier(object):
 
         if legend is None:
             legend = ['?', '*', '.', '#', '@', '-', '|', '+']
-        merge = node & ~cls.FRONTIER_MASK
+        merge = node & Block.MERGE_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:
@@ -1058,15 +1050,49 @@ class MergeFrontier(object):
         and zero or more of the FRONTIER_* constants defined in this class."""
 
         diagram = self.block.create_diagram()
-        for block in self:
+
+        try:
+            next_block = self.blocks[0]
+        except IndexError:
+            next_block = None
+
+        diagram[0][-1] |= self.FRONTIER_BOTTOM_EDGE
+        for i2 in range(1, self.block.len2):
+            if next_block is None or i2 >= next_block.len2:
+                diagram[0][i2] |= self.FRONTIER_RIGHT_EDGE
+
+        prev_block = None
+        for n in range(len(self.blocks)):
+            block = self.blocks[n]
+            try:
+                next_block = self.blocks[n + 1]
+            except IndexError:
+                next_block = None
+
             for i1 in range(block.len1):
                 for i2 in range(block.len2):
                     v = self.FRONTIER_WITHIN
-                    if i1 == block.len1 - 1:
+                    if i1 == block.len1 - 1 and (
+                        next_block is None or i2 >= next_block.len2
+                        ):
                         v |= self.FRONTIER_RIGHT_EDGE
-                    if i2 == block.len2 - 1:
+                    if i2 == block.len2 - 1 and (
+                        prev_block is None or i1 >= prev_block.len1
+                        ):
                         v |= self.FRONTIER_BOTTOM_EDGE
                     diagram[i1][i2] |= v
+            prev_block = block
+
+        try:
+            prev_block = self.blocks[-1]
+        except IndexError:
+            prev_block = None
+
+        for i1 in range(1, self.block.len1):
+            if prev_block is None or i1 >= prev_block.len1:
+                diagram[i1][0] |= self.FRONTIER_BOTTOM_EDGE
+        diagram[-1][0] |= self.FRONTIER_RIGHT_EDGE
+
         return diagram
 
     def format_diagram(self, formatter=None, diagram=None):
@@ -1098,13 +1124,27 @@ class MergeFrontier(object):
             self.FRONTIER_BOTTOM_EDGE: 'frontier_bottom_edge',
             }
 
-        def map_to_classes(node):
-            merge = node & ~self.FRONTIER_MASK
+        def map_to_classes(i1, i2, node):
+            merge = node & Block.MERGE_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])
+            if not (node & self.FRONTIER_WITHIN):
+                ret.append('frontier_without')
+            elif (node & Block.MERGE_MASK) == Block.MERGE_UNKNOWN:
+                ret.append('merge_skipped')
+            if i1 == 0 or i2 == 0:
+                ret.append('merge_initial')
+            if i1 == 0:
+                ret.append('col_left')
+            if i1 == self.block.len1 - 1:
+                ret.append('col_right')
+            if i2 == 0:
+                ret.append('row_top')
+            if i2 == self.block.len2 - 1:
+                ret.append('row_bottom')
             return ret
 
         f.write("""\
@@ -1118,10 +1158,18 @@ class MergeFrontier(object):
 """ % (name, cssfile))
 
         diagram = self.create_diagram()
+
+        f.write('  <tr>\n')
+        f.write('    <th class="indexes">&nbsp;</td>\n')
+        for i1 in range(self.block.len1):
+            f.write('    <th class="indexes">%d-*</td>\n' % (i1,))
+        f.write('  </tr>\n')
+
         for i2 in range(self.block.len2):
             f.write('  <tr>\n')
+            f.write('    <th class="indexes">*-%d</td>\n' % (i2,))
             for i1 in range(self.block.len1):
-                classes = map_to_classes(diagram[i1][i2])
+                classes = map_to_classes(i1, i2, diagram[i1][i2])
                 record = self.block.get_value(i1, i2)
                 sha1 = record.sha1 or ''
                 td_id = record.sha1 and ' id="%s"' % (record.sha1) or ''
@@ -1146,7 +1194,7 @@ class MergeFrontier(object):
 
         i = iter(blocks)
         try:
-            last = i.next()
+            last = next(i)
         except StopIteration:
             return
 
@@ -1451,7 +1499,7 @@ class Block(object):
             try:
                 merge = automerge(commit1, commit2, msg=logmsg)
                 sys.stderr.write('success.\n')
-            except AutomaticMergeFailed, e:
+            except AutomaticMergeFailed as e:
                 sys.stderr.write('unexpected conflict.  Backtracking...\n')
                 raise UnexpectedMergeFailure(str(e), i1, i2)
             if record:
@@ -1529,7 +1577,7 @@ class Block(object):
                 msg=logmsg,
                 )
             sys.stderr.write('success.\n')
-        except AutomaticMergeFailed, e:
+        except AutomaticMergeFailed:
             sys.stderr.write('conflict.\n')
             self[i1,i2].record_blocked(True)
             return False
@@ -1553,7 +1601,7 @@ class Block(object):
 
         try:
             best_block.auto_outline()
-        except UnexpectedMergeFailure, e:
+        except UnexpectedMergeFailure as e:
             # One of the merges that we expected to succeed in
             # fact failed.
             merge_frontier.remove_failure(e.i1, e.i2)
@@ -1581,6 +1629,7 @@ class Block(object):
     MERGE_AUTOMATIC = 2
     MERGE_BLOCKED = 3
     MERGE_UNBLOCKED = 4
+    MERGE_MASK = 7
 
     # A map {(is_known(), manual, is_blocked()) : integer constant}
     MergeState = {
@@ -1722,7 +1771,7 @@ class MergeState(Block):
         r"""
         ^
         refs\/imerge\/
-        (?P<name>[^\/]+)
+        (?P<name>.+)
         \/state
         $
         """,
@@ -1749,7 +1798,7 @@ class MergeState(Block):
         state_string = check_output(['git', 'cat-file', 'blob', sha1])
         state = json.loads(state_string)
 
-        version = tuple(map(int, state['version'].split('.')))
+        version = tuple(int(i) for i in state['version'].split('.'))
         if version[0] != STATE_VERSION[0] or version[1] > STATE_VERSION[1]:
             raise Failure(
                 'The format of imerge %s (%s) is not compatible with this script version.'
@@ -1793,7 +1842,7 @@ class MergeState(Block):
         if name is None:
             try:
                 check_call(['git', 'config', '--unset', 'imerge.default'])
-            except CalledProcessError, e:
+            except CalledProcessError as e:
                 if e.returncode == 5:
                     # Value was not set
                     pass
@@ -1830,9 +1879,6 @@ class MergeState(Block):
     def check_name_format(name):
         """Check that name is a valid imerge name."""
 
-        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,)]
@@ -1841,49 +1887,23 @@ class MergeState(Block):
             raise Failure('Name %r is not a valid refname component!' % (name,))
 
     @staticmethod
-    def initialize(name, tip1, tip2, goal=DEFAULT_GOAL, manual=False):
+    def initialize(
+        name, merge_base,
+        tip1, commits1,
+        tip2, commits2,
+        goal=DEFAULT_GOAL, manual=False, branch=None,
+        ):
         """Create and return a new MergeState object."""
 
         MergeState.check_name_format(name)
+        if branch:
+            check_branch_name_format(branch)
+        else:
+            branch = 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)
 
@@ -1894,6 +1914,7 @@ class MergeState(Block):
             MergeRecord.NEW_MANUAL,
             goal=goal,
             manual=manual,
+            branch=branch,
             )
 
     @staticmethod
@@ -1999,6 +2020,7 @@ class MergeState(Block):
             raise Failure('Goal %r, read from state, is not recognized.' % (goal,))
 
         manual = state['manual']
+        branch = state.get('branch', name)
 
         state = MergeState(
             name, merge_base,
@@ -2007,10 +2029,11 @@ class MergeState(Block):
             MergeRecord.SAVED_MANUAL,
             goal=goal,
             manual=manual,
+            branch=branch,
             )
 
         # Now write the rest of the merges to state:
-        for ((i1, i2), (sha1, source)) in merges.iteritems():
+        for ((i1, i2), (sha1, source)) in merges.items():
             if i1 == 0 and i2 >= state.len2:
                 raise Failure('Merge 0-%d is missing!' % (state.len2,))
             if i1 >= state.len1 and i2 == 0:
@@ -2069,7 +2092,7 @@ class MergeState(Block):
                         '-m', 'imerge: remove merge %r' % (name,),
                         '-d', refname,
                         ])
-            except CalledProcessError, e:
+            except CalledProcessError as e:
                 sys.stderr.write(
                     'Warning: error removing reference %r: %s' % (refname, e)
                     )
@@ -2085,12 +2108,14 @@ class MergeState(Block):
         source,
         goal=DEFAULT_GOAL,
         manual=False,
+        branch=None,
         ):
         Block.__init__(self, name, len(commits1) + 1, len(commits2) + 1)
         self.tip1 = tip1
         self.tip2 = tip2
         self.goal = goal
         self.manual = bool(manual)
+        self.branch = branch or name
 
         # A simulated 2D array.  Values are None or MergeRecord instances.
         self._data = [[None] * self.len2 for i1 in range(self.len1)]
@@ -2148,7 +2173,7 @@ class MergeState(Block):
                 progress_made = True
         except BlockCompleteError:
             return
-        except FrontierBlockedError, e:
+        except FrontierBlockedError as e:
             self.save()
             if not progress_made:
                 # Adjust the error message:
@@ -2383,17 +2408,18 @@ class MergeState(Block):
                     blockers.append((i1, i2))
 
         state = dict(
-            version='.'.join(map(str, STATE_VERSION)),
+            version='.'.join(str(i) for i in STATE_VERSION),
             blockers=blockers,
             tip1=self.tip1, tip2=self.tip2,
             goal=self.goal,
             manual=self.manual,
+            branch=self.branch,
             )
         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)
+        out = communicate(p, input=state_string)[0]
         retcode = p.poll()
         if retcode:
             raise CalledProcessError(retcode, cmd)
@@ -2645,6 +2671,11 @@ def main(args):
         help='the goal of the incremental merge',
         )
     subparser.add_argument(
+        '--branch',
+        action='store', default=None,
+        help='the name of the branch to which the result will be stored',
+        )
+    subparser.add_argument(
         '--manual',
         action='store_true', default=False,
         help=(
@@ -2662,11 +2693,90 @@ def main(args):
             ),
         )
     subparser.add_argument(
-        'branch', action='store',
+        'tip2', action='store', metavar='branch',
+        help='the tip of the branch to be merged into HEAD',
+        )
+
+    subparser = subparsers.add_parser(
+        'merge',
+        help='start a simple merge via incremental merge',
+        )
+    subparser.add_argument(
+        '--name', action='store', default=None,
+        help='name to use for this incremental merge',
+        )
+    subparser.add_argument(
+        '--goal',
+        action='store', default='merge',
+        choices=ALLOWED_GOALS,
+        help='the goal of the incremental merge',
+        )
+    subparser.add_argument(
+        '--branch',
+        action='store', default=None,
+        help='the name of the branch to which the result will be stored',
+        )
+    subparser.add_argument(
+        '--manual',
+        action='store_true', default=False,
+        help=(
+            'ask the user to complete all merges manually, even when they '
+            'appear conflict-free.  This option disables the usual bisection '
+            'algorithm and causes the full incremental merge diagram to be '
+            'completed.'
+            ),
+        )
+    subparser.add_argument(
+        '--first-parent', action='store_true', default=True,
+        help=argparse.SUPPRESS,
+        )
+    subparser.add_argument(
+        'tip2', action='store', metavar='branch',
         help='the tip of the branch to be merged into HEAD',
         )
 
     subparser = subparsers.add_parser(
+        'rebase',
+        help='start a simple rebase via incremental merge',
+        )
+    subparser.add_argument(
+        '--name', action='store', default=None,
+        help='name to use for this incremental merge',
+        )
+    subparser.add_argument(
+        '--goal',
+        action='store', default='rebase',
+        choices=ALLOWED_GOALS,
+        help='the goal of the incremental merge',
+        )
+    subparser.add_argument(
+        '--branch',
+        action='store', default=None,
+        help='the name of the branch to which the result will be stored',
+        )
+    subparser.add_argument(
+        '--manual',
+        action='store_true', default=False,
+        help=(
+            'ask the user to complete all merges manually, even when they '
+            'appear conflict-free.  This option disables the usual bisection '
+            'algorithm and causes the full incremental merge diagram to be '
+            'completed.'
+            ),
+        )
+    subparser.add_argument(
+        '--first-parent', action='store_true', default=True,
+        help=argparse.SUPPRESS,
+        )
+    subparser.add_argument(
+        'tip1', action='store', metavar='branch',
+        help=(
+            'the tip of the branch onto which the current branch should '
+            'be rebased'
+            ),
+        )
+
+    subparser = subparsers.add_parser(
         'continue',
         help=(
             'record the merge at branch imerge/NAME '
@@ -2715,8 +2825,9 @@ def main(args):
         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 '
+            '(default is the value provided to "init" or "start" if any; '
+            'otherwise 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.'
             ),
@@ -2779,6 +2890,11 @@ def main(args):
         help='the goal of the incremental merge',
         )
     subparser.add_argument(
+        '--branch',
+        action='store', default=None,
+        help='the name of the branch to which the result will be stored',
+        )
+    subparser.add_argument(
         '--manual',
         action='store_true', default=False,
         help=(
@@ -2796,7 +2912,7 @@ def main(args):
             ),
         )
     subparser.add_argument(
-        'branch', action='store',
+        'tip2', action='store', metavar='branch',
         help='the tip of the branch to be merged into HEAD',
         )
 
@@ -2853,8 +2969,9 @@ def main(args):
         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 '
+            '(default is the value provided to "init" or "start" if any; '
+            'otherwise 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.'
             ),
@@ -2889,7 +3006,7 @@ def main(args):
     # 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'
+    os.environ[str('GIT_IMERGE')] = str('1')
 
     if options.subcommand == 'list':
         default_merge = MergeState.get_default_name()
@@ -2915,10 +3032,14 @@ def main(args):
                 ).strip()
         except CalledProcessError:
             tip1 = 'HEAD'
-        tip2 = options.branch
+        tip2 = options.tip2
+        (merge_base, commits1, commits2) = get_boundaries(tip1, tip2)
         merge_state = MergeState.initialize(
-            options.name, tip1, tip2,
+            options.name, merge_base,
+            tip1, commits1,
+            tip2, commits2,
             goal=options.goal, manual=options.manual,
+            branch=(options.branch or options.name),
             )
         merge_state.save()
         MergeState.set_default_name(options.name)
@@ -2939,17 +3060,141 @@ def main(args):
                 ).strip()
         except CalledProcessError:
             tip1 = 'HEAD'
-        tip2 = options.branch
+        tip2 = options.tip2
+        (merge_base, commits1, commits2) = get_boundaries(tip1, tip2)
         merge_state = MergeState.initialize(
-            options.name, tip1, tip2,
+            options.name, merge_base,
+            tip1, commits1,
+            tip2, commits2,
+            goal=options.goal, manual=options.manual,
+            branch=(options.branch or options.name),
+            )
+        merge_state.save()
+        MergeState.set_default_name(options.name)
+
+        try:
+            merge_state.auto_complete_frontier()
+        except FrontierBlockedError as e:
+            request_user_merge(merge_state, e.i1, e.i2)
+        else:
+            sys.stderr.write('Merge is complete!\n')
+    elif options.subcommand == 'merge':
+        require_clean_work_tree('proceed')
+
+        if not options.first_parent:
+            parser.error(
+                'The --first-parent option is currently required for the "merge" command'
+                )
+
+        tip2 = options.tip2
+
+        if options.name:
+            name = options.name
+        else:
+            # By default, name the imerge after the branch being merged:
+            name = tip2
+            MergeState.check_name_format(name)
+
+        try:
+            tip1 = check_output(
+                ['git', 'symbolic-ref', '--quiet', '--short', 'HEAD'],
+                ).strip()
+            if not options.branch:
+                # See if we can store the result to the checked-out branch:
+                try:
+                    check_branch_name_format(tip1)
+                except InvalidBranchNameError:
+                    pass
+                else:
+                    options.branch = tip1
+        except CalledProcessError:
+            tip1 = 'HEAD'
+
+        if not options.branch:
+            if options.name:
+                options.branch = options.name
+            else:
+                parser.error(
+                    'HEAD is not a simple branch.  '
+                    'Please specify --branch for storing results.'
+                    )
+
+        (merge_base, commits1, commits2) = get_boundaries(tip1, tip2)
+        merge_state = MergeState.initialize(
+            name, merge_base,
+            tip1, commits1,
+            tip2, commits2,
+            goal=options.goal, manual=options.manual,
+            branch=options.branch,
+            )
+        merge_state.save()
+        MergeState.set_default_name(name)
+
+        try:
+            merge_state.auto_complete_frontier()
+        except FrontierBlockedError as e:
+            request_user_merge(merge_state, e.i1, e.i2)
+        else:
+            sys.stderr.write('Merge is complete!\n')
+    elif options.subcommand == 'rebase':
+        require_clean_work_tree('proceed')
+
+        if not options.first_parent:
+            parser.error(
+                'The --first-parent option is currently required for the "rebase" command'
+                )
+
+        tip1 = options.tip1
+
+        try:
+            tip2 = check_output(
+                ['git', 'symbolic-ref', '--quiet', '--short', 'HEAD'],
+                ).strip()
+            if not options.branch:
+                # See if we can store the result to the current branch:
+                try:
+                    check_branch_name_format(tip2)
+                except InvalidBranchNameError:
+                    pass
+                else:
+                    options.branch = tip2
+            if not options.name:
+                # By default, name the imerge after the branch being rebased:
+                options.name = tip2
+
+        except CalledProcessError:
+            tip2 = rev_parse('HEAD')
+
+        if not options.name:
+            parser.error(
+                'The checked-out branch could not be used as the imerge name.\n'
+                'Please use the --name option.'
+                )
+
+        if not options.branch:
+            if options.name:
+                options.branch = options.name
+            else:
+                parser.error(
+                    'HEAD is not a simple branch.  '
+                    'Please specify --branch for storing results.'
+                    )
+
+        (merge_base, commits1, commits2) = get_boundaries(tip1, tip2)
+
+        merge_state = MergeState.initialize(
+            options.name, merge_base,
+            tip1, commits1,
+            tip2, commits2,
             goal=options.goal, manual=options.manual,
+            branch=options.branch,
             )
         merge_state.save()
         MergeState.set_default_name(options.name)
 
         try:
             merge_state.auto_complete_frontier()
-        except FrontierBlockedError, e:
+        except FrontierBlockedError as e:
             request_user_merge(merge_state, e.i1, e.i2)
         else:
             sys.stderr.write('Merge is complete!\n')
@@ -2961,14 +3206,14 @@ def main(args):
             incorporate_user_merge(merge_state, edit_log_msg=options.edit)
         except NoManualMergeError:
             pass
-        except NotABlockingCommitError, e:
+        except NotABlockingCommitError as e:
             raise Failure(str(e))
-        except ManualMergeUnusableError, e:
+        except ManualMergeUnusableError as e:
             raise Failure(str(e))
 
         try:
             merge_state.auto_complete_frontier()
-        except FrontierBlockedError, e:
+        except FrontierBlockedError as e:
             request_user_merge(merge_state, e.i1, e.i2)
         else:
             sys.stderr.write('Merge is complete!\n')
@@ -2976,16 +3221,16 @@ def main(args):
         merge_state = read_merge_state(options.name)
         try:
             incorporate_user_merge(merge_state, edit_log_msg=options.edit)
-        except NoManualMergeError, e:
+        except NoManualMergeError as e:
             raise Failure(str(e))
         except NotABlockingCommitError:
             raise Failure(str(e))
-        except ManualMergeUnusableError, e:
+        except ManualMergeUnusableError as e:
             raise Failure(str(e))
 
         try:
             merge_state.auto_complete_frontier()
-        except FrontierBlockedError, e:
+        except FrontierBlockedError as e:
             pass
         else:
             sys.stderr.write('Merge is complete!\n')
@@ -2995,7 +3240,7 @@ def main(args):
         with TemporaryHead():
             try:
                 merge_state.auto_complete_frontier()
-            except FrontierBlockedError, e:
+            except FrontierBlockedError as e:
                 raise Failure(str(e))
     elif options.subcommand == 'simplify':
         require_clean_work_tree('proceed')
@@ -3003,7 +3248,7 @@ def main(args):
         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),)
+        refname = 'refs/heads/%s' % ((options.branch or merge_state.branch),)
         if options.goal is not None:
             merge_state.set_goal(options.goal)
             merge_state.save()
@@ -3014,7 +3259,7 @@ def main(args):
         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),)
+        refname = 'refs/heads/%s' % ((options.branch or merge_state.branch),)
         if options.goal is not None:
             merge_state.set_goal(options.goal)
             merge_state.save()
@@ -3061,8 +3306,8 @@ def main(args):
             sys.exit('HEAD is not a valid commit')
 
         try:
-            parent_sha1s = map(get_commit_sha1, options.parents)
-        except ValueError, e:
+            parent_sha1s = [get_commit_sha1(p) for p in options.parents]
+        except ValueError as e:
             sys.exit(e.message)
 
         sys.stdout.write('%s\n' % (reparent(commit_sha1, parent_sha1s),))
@@ -3072,3 +3317,4 @@ def main(args):
 
 main(sys.argv[1:])
 
+# vim: set expandtab ft=python: