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     theirs_tree = shell.eval("git", "rev-parse", "%s^{tree}" % theirs_id)
 165     for file in ours_theirs_diff:
 166         try:
 167             theirs_nl = theirs_newlines[file]
 168         except KeyError:
 169             # No need to handle newlines
 170             continue
 171         try:
 172             ours_nl = get_newline(file) # current checkout is ours_id
 173         except (IOError, shell.CallError): # hack
 174             continue
 175         if theirs_nl != ours_nl:
 176             if ours_nl is None:
 177                 logging.debug("File had no newlines, ignoring newline style")
 178             else:
 179                 logging.info("Converting our file (3) from %s to %s newlines", repr(ours_nl), repr(theirs_nl))
 180                 convert_newline(file, theirs_nl)
 181                 shell.eval("git", "add", file) # XXX batch this
 182     prepare_config() # for Wizard, this usually genericizes config files
 183     ours_tree = shell.eval("git", "write-tree")
 184     logging.info("Merge wrote virtual tree for ours: %s", ours_tree)
 185
 186     # operations on the common tree (pretty duplicate with the above)
 187     shell.call("git", "reset", "--hard", common_id)
 188     for file in git_diff_text(common_id, theirs_id):
 189         try:
 190             theirs_nl = theirs_newlines[file]
 191         except KeyError:
 192             # The merge trivially succeeds, so don't bother.
 193             logging.debug("Merge trivially succeeds for %s, ignoring line check", file)
 194             continue
 195         try:
 196             common_nl = get_newline(file) # current checkout is common_id
 197         except (IOError, shell.CallError): # hack
 198             continue
 199         if theirs_nl != common_nl:
 200             if common_nl is None:
 201                 logging.debug("File had no newlines, ignoring newline style")
 202             else:
 203                 logging.info("Converting common file (1) from %s to %s newlines", repr(common_nl), repr(theirs_nl))
 204                 convert_newline(file, theirs_nl)
 205                 shell.eval("git", "add", file) # XXX batch
 206     common_tree = shell.eval("git", "write-tree")
 207     logging.info("Merge wrote virtual tree for common: %s", common_tree)
 208
 209     # construct merge commit graph
 210     common_virtual_id = git_commit_tree(common_tree)
 211     ours_virtual_id   = git_commit_tree(ours_tree, common_virtual_id)
 212     theirs_virtual_id = git_commit_tree(theirs_tree, common_virtual_id)
 213
 214     # perform merge
 215     shell.call("git", "reset", "--hard", ours_virtual_id)
 216     try:
 217         shell.call("git", "merge", theirs_virtual_id)
 218     except shell.CallError as e:
 219         logging.info("Merge failed with these message:\n\n" + e.stderr)
 220         if resolve_conflicts():
 221             logging.info("Resolved conflicts automatically")
 222             shell.call("git", "commit", "-a", "-m", "merge")
 223         else:
 224             raise MergeError
 225
 226     # post-merge operations
 227     result_tree = shell.eval("git", "write-tree")
 228     logging.info("Resolution tree is %s", result_tree)
 229     return result_tree
 230
 231 class Error(wizard.Error):
 232     """Base error class for merge"""
 233     pass
 234
 235 class MergeError(Error):
 236     """Merge terminated with a conflict, oh no!"""
 237     pass