wizard/resolve.py

   1 """
   2 .. highlight:: diff
   3
   4 This module contains algorithms for performing conflict
   5 resolution after Git performs its recursive merge.  It
   6 defines a simple domain specific language (that, at
   7 its simplest form, merely involves copying conflict markers
   8 and writing in the form that they should be resolved as) for
   9 specifying how to resolve conflicts.  These are mostly relevant
  10 for resolving conflicts in configuration files.
  11
  12 The conflict resolution DSL is described here:
  13
  14 Resolutions are specified as input-output pairs.  An input
  15 is a string with the conflict resolution markers ``("<" * 7,
  16 "=" * 7 and ">" * 7)``, with the HEAD content above the equals
  17 divider, and the upstream content below the equals divider.
  18 Lines can also be marked as ``***N***`` where N is a natural
  19 number greater than 0 (i.e. 1 or more), which means that
  20 an arbitrary number of lines may be matched and available for output.
  21
  22 Output is a list of integers and strings.  Integers expand
  23 to lines that were specified earlier; -1 and 0 are special integers
  24 that correspond to the entire HEAD text, and the entire upstream
  25 text, respectively.  Strings can be used to insert custom lines.
  26
  27 The DSL does not currently claim to support character level granularity.
  28 It also does not claim to support contiguous conflicts.
  29 Our hope is that this simple syntax will be sufficient to cover
  30 most common merge failures.
  31
  32 Here are some examples::
  33
  34     <<<<<<<
  35     downstream
  36     |||||||
  37     common
  38     =======
  39     upstream
  40     >>>>>>>
  41
  42 With ``[-1]`` would discard all upstream changes, whereas with ``[0]``
  43 would discard downstream changes (you would probably want to be
  44 careful about wildcarding in the upstream string).
  45
  46 Pattern matching in action::
  47
  48     <<<<<<<
  49     ***1***
  50     old upstream
  51     ***2***
  52     old upstream
  53     ***3***
  54     =======
  55     new upstream
  56     >>>>>>>
  57
  58 With ``[0, 1, 2, 3]`` would resolve with the new upstream text, and
  59 then the user matched globs.
  60 """
  61
  62 import re
  63 import itertools
  64 import logging
  65
  66 re_var = re.compile("^\*\*\*(\d+)\*\*\*\\\n", re.MULTILINE)
  67
  68 def spec_to_regex(spec):
  69     """
  70     Translates a specification string into a regular expression tuple.
  71     Note that pattern matches are out of order, so the second element
  72     of the tuple is a dict specified strings to subpattern numbers.
  73     Requires re.DOTALL for correct operation.
  74     """
  75     ours, _, theirs = "".join(spec.strip().splitlines(True)[1:-1]).partition("=======\n")
  76     def regexify(text, fullmatch, matchno):
  77         text_split = re.split(re_var, text)
  78         ret = ""
  79         mappings = {fullmatch: matchno}
  80         for is_var, line in zip(itertools.cycle([False, True]), text_split):
  81             if is_var:
  82                 ret += "(.*\\\n)"
  83                 matchno += 1
  84                 mappings[int(line)] = matchno
  85             else:
  86                 ret += re.escape(line)
  87         return ("(" + ret + ")", mappings)
  88     ours, split, common = ours.partition("|||||||\n")
  89     if not split:
  90         common = "***9999***\n" # force wildcard behavior
  91     ours_regex, ours_mappings     = regexify(ours,   -1, 1)
  92     common_regex, common_mappings = regexify(common, -2, 1 + len(ours_mappings))
  93     theirs_regex, theirs_mappings = regexify(theirs,  0, 1 + len(ours_mappings) + len(common_mappings))
  94     # unify the mappings
  95     ours_mappings.update(theirs_mappings)
  96     ours_mappings.update(common_mappings)
  97     return ("<<<<<<<[^\n]*\\\n" + ours_regex + "\|\|\|\|\|\|\|\\\n" + common_regex + "=======\\\n" + theirs_regex + ">>>>>>>[^\n]*(\\\n|$)", ours_mappings)
  98
  99 def result_to_repl(result, mappings):
 100     """
 101     Converts a list of replacement strings and or references
 102     into a replacement string appropriate for a regular expression.
 103     """
 104     def ritem_to_string(r):
 105         if type(r) is int:
 106             return "\\%d" % mappings[r]
 107         else:
 108             return r + "\n"
 109     return "".join(map(ritem_to_string, result))
 110
 111 def resolve(contents, spec, result):
 112     """
 113     Given a conflicted file, whose contents are ``contents``, attempt
 114     to resolve all conflicts that match ``spec`` with ``result``.
 115     """
 116     rstring, mappings = spec_to_regex(spec)
 117     regex = re.compile(rstring, re.DOTALL)
 118     repl = result_to_repl(result, mappings)
 119     ret = ""
 120     conflict = ""
 121     status = 0
 122     for line in contents.splitlines(True):
 123         if status == 0 and line.startswith("<<<<<<<"):
 124             status = 1
 125         elif status == 1 and line.startswith("|||||||"):
 126             status = 2
 127         elif status == 1 or status == 2 and line.startswith("======="):
 128             status = 3
 129         # ok, now process
 130         if status == 3 and line.startswith(">>>>>>>"):
 131             status = 0
 132             conflict += line
 133             ret += regex.sub(repl, conflict)
 134             conflict = ""
 135         elif status:
 136             conflict += line
 137         else:
 138             ret += line
 139     return ret
 140
 141 def is_conflict(contents):
 142     """
 143     Given ``contents``, return ``True`` if there are any conflicts in it.
 144     """
 145     # Really really simple heuristic
 146     return "<<<<<<<" in contents
 147