wizard/merge.py

   1 """
   2 Advanced merge tools for git rerere, sloppy commits and parametrization.
   3
   4 Wizard requires infrastructure for reusing merge resolutions across
   5 many repositories, due to the number of user installs and highly
   6 repetitive conflict resolution process.  This environment results
   7 in a number of unique challenges:
   8
   9     1. Users are commonly very sloppy with their text editors and
  10        will frequently change the line-ending style of their file.
  11        Because Git respects newline choice when core.autocrlf is
  12        off, a file that flips newline style will result in a full
  13        merge conflict.
  14
  15     2. We version user configuration files, which means that there
  16        will always be a set of changes between upstream and ours.
  17        Since Git refuses to automatically merge changes that are
  18        too close to each other, these frequently result in spurious
  19        merge commits.
  20
  21 Furthermore, both of these make it difficult to reuse rerere resolutions
  22 across installations.  Thus, an advanced Wizard merge has the following
  23 properties:
  24
  25     1. Wizard will perform a full scan of all files that were
  26        different between common and ours, filter out those that
  27        are binary (using as close to the Git heuristic as possible)
  28        and then check among common, ours and theirs if the newlines
  29        match.  The newline style of theirs always takes precedence.
  30
  31     2. Wizard will genericize the ours copy so that it matches
  32        common and theirs, and reparametrize it once the merge
  33        is finished.  Consumers of this function should be careful
  34        to appropriately reparametrize if there are conflicts
  35        (we can't do it any earlier, because we want clean rerere
  36        postimages).
  37
  38 Usage of this functionality is primarily through the :func:`merge` function;
  39 see that function more usage information.  While the ``git`` and ``newline``
  40 functions published by this module are public, use of these functions outside
  41 of this module is discouraged.
  42 """
  43
  44 import logging
  45 import itertools
  46 import tempfile
  47 import os
  48
  49 import wizard
  50 from wizard import shell
  51
  52 def git_commit_tree(tree, *parents):
  53     """
  54     Convenience wrapper for ``git commit-tree``.  Writes an empty log.
  55     """
  56     parent_args = itertools.chain(*(["-p", p] for p in parents))
  57     commit = shell.eval("git", "commit-tree", tree,
  58             *parent_args, input="", log=True)
  59     return commit
  60
  61 def git_diff_text(a, b):
  62     """
  63     Returns a list of files that are text and are different between
  64     commits ``a`` and ``b``.
  65     """
  66     lines = shell.eval("git", "diff", "--numstat", a, b).strip().split("\n")
  67     files = []
  68     for line in lines:
  69         added, deleted, name = line.split()
  70         if added != "-" and deleted != "-":
  71             files.append(name)
  72     return files
  73
  74 # only works on Unix
  75 def get_newline(filename):
  76     """
  77     Determines the newline style of ``filename``.  This will be a
  78     string if only one newline style was find, or a tuple of newline
  79     types found.
  80     """
  81     f = open(filename, 'U')
  82     f.read()
  83     return f.newlines
  84
  85 def convert_newline(filename, dest_nl):
  86     """
  87     Replaces the detected newline style of ``filename`` with
  88     ``dest_nl`` type newlines.
  89     """
  90     contents = open(filename, "U").read().replace("\n", dest_nl)
  91     open(filename, "wb").write(contents)
  92
  93 def merge(common_id, theirs_id,
  94           prepare_config=None,
  95           resolve_conflicts=None):
  96     """
  97     Performs a merge.  Throws a :class:`MergeError` if the merge fails
  98     (and leaves the current working directory in a state amenable
  99     to manual conflict resolution), or returns a tree id of the successful
 100     merge (the directory state is undefined and should not be relied upon).
 101     This function is not responsible for actually coming
 102     up with the real merge commit, because it can fail.
 103
 104     If ``prepare_config`` is used, you are expected to reverse the effects
 105     of this on whatever the final tree is; otherwise you will lose
 106     those changes.
 107
 108     Arguments:
 109
 110         * ``common_id``: base commit to calculate merge off of
 111         * ``theirs_id``: changes to merge in from commit
 112         * ``prepare_config``: function that removes any user-specific
 113           values from files.  This function is expected to ``git add``
 114           any files it changes.
 115         * ``resolve_conflicts``: this function attempts to resolve
 116           conflicts automatically.  Returns ``True`` if all conflicts
 117           are resolved, and ``False`` otherwise.  It is permitted
 118           to resolve some but not all conflicts.
 119
 120     .. note::
 121
 122         Wizard has a strange idea of repository topology (due to lack of
 123         rebases, see documentation about doctoring retroactive commits),
 124         so we require the common and theirs commits, instead of
 125         using the normal Git algorithm.
 126     """
 127
 128     if prepare_config is None:
 129         prepare_config = lambda: None
 130
 131     if resolve_conflicts is None:
 132         resolve_conflicts = lambda: False
 133
 134     ours_id = shell.eval("git", "rev-parse", "HEAD")
 135     ours_theirs_diff  = git_diff_text(ours_id, theirs_id)
 136
 137     # What files can the merge fail on? Only if ours is different from
 138     # theirs (we don't care about common for this calculation).  Of
 139     # course, this will be conservative, because we need to apply
 140     # prepare_config to ours.  Can we miss a file?  Not unless
 141     # prepare_config introduces a merge conflict, as opposed to
 142     # eliminates them; and it is equally likely to do so on common_id as
 143     # well. We can deal, since we offer the user the ability to resolve
 144     # merges  manually.
 145     theirs_newlines = {}
 146     shell.call("git", "reset", "--hard", theirs_id)
 147     for file in ours_theirs_diff:
 148         # XXX Should be able to skip stats if file was removed
 149         # for the ours tree
 150         try:
 151             nl = get_newline(file)
 152         except IOError:
 153             # File not present in theirs, don't bother
 154             continue
 155         if not isinstance(nl, str):
 156             if nl is not None:
 157                 # A case of incompetent upstream, unfortunately
 158                 logging.warning("Canonical version (theirs) of %s has mixed newline style, forced to \\n", file)
 159             else:
 160                 logging.debug("Canonical version (theirs) of %s had no newline style, using \\n", file)
 161             nl = "\n"
 162         theirs_newlines[file] = nl
 163
 164     shell.call("git", "reset", "--hard", ours_id)
 165     theirs_tree = shell.eval("git", "rev-parse", "%s^{tree}" % theirs_id)
 166     for file in ours_theirs_diff:
 167         try:
 168             theirs_nl = theirs_newlines[file]
 169         except KeyError:
 170             # No need to handle newlines
 171             continue
 172         try:
 173             ours_nl = get_newline(file) # current checkout is ours_id
 174         except (IOError, shell.CallError): # hack
 175             continue
 176         if theirs_nl != ours_nl:
 177             if ours_nl is None:
 178                 logging.debug("Our file %s had no newlines, ignoring newline style", file)
 179             else:
 180                 logging.info("Converting our file %s (3) from %s to %s newlines", file, repr(ours_nl), repr(theirs_nl))
 181                 convert_newline(file, theirs_nl)
 182                 shell.eval("git", "add", file) # XXX batch this
 183     prepare_config() # for Wizard, this usually genericizes config files
 184     ours_tree = shell.eval("git", "write-tree")
 185     logging.info("Merge wrote virtual tree for ours: %s", ours_tree)
 186
 187     # operations on the common tree (pretty duplicate with the above)
 188     shell.call("git", "reset", "--hard", common_id)
 189     for file in git_diff_text(common_id, theirs_id):
 190         try:
 191             theirs_nl = theirs_newlines[file]
 192         except KeyError:
 193             # The merge trivially succeeds, so don't bother.
 194             logging.debug("Merge trivially succeeds for %s, ignoring line check", file)
 195             continue
 196         try:
 197             common_nl = get_newline(file) # current checkout is common_id
 198         except (IOError, shell.CallError): # hack
 199             continue
 200         if theirs_nl != common_nl:
 201             if common_nl is None:
 202                 logging.debug("Common file %s had no newlines, ignoring newline style", file)
 203             else:
 204                 logging.info("Converting common file %s (1) from %s to %s newlines", file, repr(common_nl), repr(theirs_nl))
 205                 convert_newline(file, theirs_nl)
 206                 shell.eval("git", "add", file) # XXX batch
 207     common_tree = shell.eval("git", "write-tree")
 208     logging.info("Merge wrote virtual tree for common: %s", common_tree)
 209
 210     # construct merge commit graph
 211     common_virtual_id = git_commit_tree(common_tree)
 212     ours_virtual_id   = git_commit_tree(ours_tree, common_virtual_id)
 213     theirs_virtual_id = git_commit_tree(theirs_tree, common_virtual_id)
 214
 215     # perform merge
 216     shell.call("git", "reset", "--hard", ours_virtual_id)
 217     try:
 218         shell.call("git", "merge", theirs_virtual_id)
 219     except shell.CallError as e:
 220         logging.info("Merge failed with these message:\n\n" + e.stderr)
 221         if resolve_conflicts():
 222             logging.info("Resolved conflicts automatically")
 223             shell.call("git", "commit", "-a", "-m", "merge")
 224         else:
 225             raise MergeError
 226
 227     # post-merge operations
 228     result_tree = shell.eval("git", "write-tree")
 229     logging.info("Resolution tree is %s", result_tree)
 230     return result_tree
 231
 232 class Error(wizard.Error):
 233     """Base error class for merge"""
 234     pass
 235
 236 class MergeError(Error):
 237     """Merge terminated with a conflict, oh no!"""
 238     pass