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 def git_newline_style(rev, name):
  75     """
  76     Returns the newline style for a blob, identified by Git revision
  77     ``rev`` and filename ``name``.
  78     """
  79     # XXX This is really expensive
  80     f = tempfile.NamedTemporaryFile(prefix="wizardResolve", delete=False)
  81     shell.call("git", "cat-file", "blob", "%s:%s" % (rev, name), stdout=f, log=False)
  82     f.close()
  83     nl = get_newline(f.name)
  84     os.unlink(f.name)
  85     return nl
  86
  87 # only works on Unix
  88 def get_newline(filename):
  89     """
  90     Determines the newline style of ``filename``.  This will be a
  91     string if only one newline style was find, or a tuple of newline
  92     types found.
  93     """
  94     f = open(filename, 'U')
  95     f.read()
  96     return f.newlines
  97
  98 def convert_newline(filename, dest_nl):
  99     """
 100     Replaces the detected newline style of ``filename`` with
 101     ``dest_nl`` type newlines.
 102     """
 103     contents = open(filename, "U").read().replace("\n", dest_nl)
 104     open(filename, "wb").write(contents)
 105
 106 def merge(common_id, theirs_id,
 107           prepare_config=None,
 108           resolve_conflicts=None):
 109     """
 110     Performs a merge.  Throws a :class:`MergeError` if the merge fails
 111     (and leaves the current working directory in a state amenable
 112     to manual conflict resolution), or returns a tree id of the successful
 113     merge (the directory state is undefined and should not be relied upon).
 114     This function is not responsible for actually coming
 115     up with the real merge commit, because it can fail.
 116
 117     If ``prepare_config`` is used, you are expected to reverse the effects
 118     of this on whatever the final tree is; otherwise you will lose
 119     those changes.
 120
 121     Arguments:
 122
 123         * ``common_id``: base commit to calculate merge off of
 124         * ``theirs_id``: changes to merge in from commit
 125         * ``prepare_config``: function that removes any user-specific
 126           values from files.  This function is expected to ``git add``
 127           any files it changes.
 128         * ``resolve_conflicts``: this function attempts to resolve
 129           conflicts automatically.  Returns ``True`` if all conflicts
 130           are resolved, and ``False`` otherwise.  It is permitted
 131           to resolve some but not all conflicts.
 132
 133     .. note::
 134
 135         Wizard has a strange idea of repository topology (due to lack of
 136         rebases, see documentation about doctoring retroactive commits),
 137         so we require the common and theirs commits, instead of
 138         using the normal Git algorithm.
 139     """
 140     if prepare_config is None:
 141         prepare_config = lambda: None
 142     if resolve_conflicts is None:
 143         resolve_conflicts = lambda: False
 144     ours_id = shell.eval("git", "rev-parse", "HEAD")
 145     theirs_newline_cache = {}
 146     def get_theirs_newline(file):
 147         if file not in theirs_newline_cache:
 148             nl = git_newline_style(theirs_id, file)
 149             if not isinstance(nl, str):
 150                 if nl is not None:
 151                     # A case of incompetent upstream, unfortunately
 152                     logging.warning("Canonical version (theirs) of %s has mixed newline style, forced to \\n", file)
 153                 else:
 154                     logging.debug("Canonical version (theirs) of %s had no newline style, using \\n", file)
 155                 nl = "\n"
 156             theirs_newline_cache[file] = nl
 157         return theirs_newline_cache[file]
 158     theirs_tree = shell.eval("git", "rev-parse", "%s^{tree}" % theirs_id)
 159     # XXX Should be able to skip stats if file doesn't exist
 160     # operations on the ours tree
 161     for file in git_diff_text(ours_id, theirs_id):
 162         try:
 163             theirs_nl = get_theirs_newline(file)
 164             ours_nl = get_newline(file) # current checkout is ours_id
 165         except (IOError, shell.CallError): # hack
 166             continue
 167         if theirs_nl != ours_nl:
 168             if ours_nl is None:
 169                 logging.debug("File had no newlines, ignoring newline style")
 170             else:
 171                 logging.info("Converting our file (3) from %s to %s newlines", repr(ours_nl), repr(theirs_nl))
 172                 convert_newline(file, theirs_nl)
 173                 shell.eval("git", "add", file)
 174     prepare_config() # for Wizard, this usually genericizes config files
 175     ours_tree = shell.eval("git", "write-tree")
 176     logging.info("Merge wrote virtual tree for ours: %s", ours_tree)
 177     # operations on the common tree (pretty duplicate with the above)
 178     shell.call("git", "reset", "--hard", common_id)
 179     for file in git_diff_text(common_id, theirs_id):
 180         try:
 181             theirs_nl = get_theirs_newline(file)
 182             common_nl = get_newline(file) # current checkout is common_id
 183         except (IOError, shell.CallError): # hack
 184             continue
 185         if theirs_nl != common_nl:
 186             if common_nl is None:
 187                 logging.debug("File had no newlines, ignoring newline style")
 188             else:
 189                 logging.info("Converting common file (1) from %s to %s newlines", repr(common_nl), repr(theirs_nl))
 190                 convert_newline(file, theirs_nl)
 191                 shell.eval("git", "add", file)
 192     common_tree = shell.eval("git", "write-tree")
 193     logging.info("Merge wrote virtual tree for common: %s", common_tree)
 194     # construct merge commit graph
 195     common_virtual_id = git_commit_tree(common_tree)
 196     ours_virtual_id   = git_commit_tree(ours_tree, common_virtual_id)
 197     theirs_virtual_id = git_commit_tree(theirs_tree, common_virtual_id)
 198     # perform merge
 199     shell.call("git", "reset", "--hard", ours_virtual_id)
 200     try:
 201         shell.call("git", "merge", theirs_virtual_id)
 202     except shell.CallError as e:
 203         logging.info("Merge failed with these message:\n\n" + e.stderr)
 204         if resolve_conflicts():
 205             logging.info("Resolved conflicts automatically")
 206             shell.call("git", "commit", "-a", "-m", "merge")
 207         else:
 208             raise MergeError
 209     # post-merge operations
 210     result_tree = shell.eval("git", "write-tree")
 211     logging.info("Resolution tree is %s", result_tree)
 212     return result_tree
 213
 214 class Error(wizard.Error):
 215     """Base error class for merge"""
 216     pass
 217
 218 class MergeError(Error):
 219     """Merge terminated with a conflict, oh no!"""
 220     pass