Back to index

moin  1.9.0~rc2
diff3.py
Go to the documentation of this file.
00001 # -*- coding: iso-8859-1 -*-
00002 """
00003     MoinMoin - diff3 algorithm
00004 
00005     @copyright: 2002 Florian Festi
00006     @license: GNU GPL, see COPYING for details.
00007 """
00008 
00009 default_markers = ('<<<<<<<<<<<<<<<<<<<<<<<<<\n',
00010                    '=========================\n',
00011                    '>>>>>>>>>>>>>>>>>>>>>>>>>\n')
00012 
00013 def text_merge(old, other, new, allow_conflicts=1, *markers):
00014     """ do line by line diff3 merge with three strings """
00015     result = merge(old.splitlines(1), other.splitlines(1), new.splitlines(1),
00016                    allow_conflicts, *markers)
00017     return ''.join(result)
00018 
00019 def merge(old, other, new, allow_conflicts=1, *markers):
00020     """ do line by line diff3 merge
00021         input must be lists containing single lines
00022     """
00023     if not markers:
00024         markers = default_markers
00025     marker1, marker2, marker3 = markers
00026 
00027     old_nr, other_nr, new_nr = 0, 0, 0
00028     old_len, other_len, new_len = len(old), len(other), len(new)
00029     result = []
00030 
00031     while old_nr < old_len and other_nr < other_len and new_nr < new_len:
00032         # unchanged
00033         if old[old_nr] == other[other_nr] == new[new_nr]:
00034             result.append(old[old_nr])
00035             old_nr += 1
00036             other_nr += 1
00037             new_nr += 1
00038         else:
00039             if allow_conflicts == 2: # experimental addition to the algorithm
00040                 if other[other_nr] == new[new_nr]:
00041                     result.append(new[new_nr])
00042                     other_nr += 1
00043                     new_nr += 1
00044                     continue
00045             new_match = find_match(old, new, old_nr, new_nr)
00046             other_match = find_match(old, other, old_nr, other_nr)
00047             # new is changed
00048             if new_match != (old_nr, new_nr):
00049                 new_changed_lines = new_match[0] - old_nr
00050                 # other is unchanged
00051                 if match(old, other, old_nr, other_nr,
00052                          new_changed_lines) == new_changed_lines:
00053                     result.extend(new[new_nr:new_match[1]])
00054                     old_nr = new_match[0]
00055                     new_nr = new_match[1]
00056                     other_nr += new_changed_lines
00057                 # both changed, conflict!
00058                 else:
00059                     if not allow_conflicts:
00060                         return None
00061                     old_m, other_m, new_m = tripple_match(
00062                         old, other, new, other_match, new_match)
00063                     result.append(marker1)
00064                     result.extend(other[other_nr:other_m])
00065                     result.append(marker2)
00066                     result.extend(new[new_nr:new_m])
00067                     result.append(marker3)
00068                     old_nr, other_nr, new_nr = old_m, other_m, new_m
00069             # other is changed
00070             else:
00071                 other_changed_lines = other_match[0] - other_nr
00072                 # new is unchanged
00073                 if match(old, new, old_nr, new_nr,
00074                          other_changed_lines) == other_changed_lines:
00075                     result.extend(other[other_nr:other_match[1]])
00076                     old_nr = other_match[0]
00077                     other_nr = other_match[1]
00078                     new_nr += other_changed_lines
00079                 # both changed, conflict!
00080                 else:
00081                     if not allow_conflicts:
00082                         return None
00083                     old_m, other_m, new_m = tripple_match(
00084                         old, other, new, other_match, new_match)
00085                     result.append(marker1)
00086                     result.extend(other[other_nr:other_m])
00087                     result.append(marker2)
00088                     result.extend(new[new_nr:new_m])
00089                     result.append(marker3)
00090                     old_nr, other_nr, new_nr = old_m, other_m, new_m
00091 
00092     # process tail
00093     # all finished
00094     if old_nr == old_len and other_nr == other_len and new_nr == new_len:
00095         pass
00096     # new added lines
00097     elif old_nr == old_len and other_nr == other_len:
00098         result.extend(new[new_nr:])
00099     # other added lines
00100     elif old_nr == old_len and new_nr == new_len:
00101         result.extend(other[other_nr:])
00102     # new deleted lines
00103     elif (new_nr == new_len and (old_len - old_nr == other_len - other_nr) and
00104           match(old, other, old_nr, other_nr, old_len-old_nr) == old_len - old_nr):
00105         pass
00106     # other deleted lines
00107     elif (other_nr == other_len and (old_len - old_nr == new_len-new_nr) and
00108           match(old, new, old_nr, new_nr, old_len-old_nr) == old_len - old_nr):
00109         pass
00110     # conflict
00111     else:
00112         if new == other:
00113             result.extend(new[new_nr:])
00114         else:
00115             if not allow_conflicts:
00116                 return None
00117             result.append(marker1)
00118             result.extend(other[other_nr:])
00119             result.append(marker2)
00120             result.extend(new[new_nr:])
00121             result.append(marker3)
00122     return result
00123 
00124 def tripple_match(old, other, new, other_match, new_match):
00125     """find next matching pattern unchanged in both other and new
00126        return the position in all three lists
00127     """
00128     while 1:
00129         difference = new_match[0] - other_match[0]
00130         # new changed more lines
00131         if difference > 0:
00132             match_len = match(old, other, other_match[0], other_match[1],
00133                               difference)
00134             if match_len == difference:
00135                 return (new_match[0], other_match[1]+difference, new_match[1])
00136             else:
00137                 other_match = find_match(old, other,
00138                                          other_match[0] + match_len,
00139                                          other_match[1] + match_len)
00140         # other changed more lines
00141         elif difference < 0:
00142             difference = -difference
00143             match_len = match(old, new, new_match[0], new_match[1],
00144                               difference)
00145             if match_len == difference:
00146                 return (other_match[0], other_match[1],
00147                         new_match[0] + difference)
00148             else:
00149                 new_match = find_match(old, new,
00150                                        new_match[0] + match_len,
00151                                        new_match[1] + match_len)
00152         # both conflicts change same number of lines
00153         # or no match till the end
00154         else:
00155             return (new_match[0], other_match[1], new_match[1])
00156 
00157 def match(list1, list2, nr1, nr2, maxcount=3):
00158     """ return the number matching items after the given positions
00159         maximum maxcount lines are are processed
00160     """
00161     i = 0
00162     len1 = len(list1)
00163     len2 = len(list2)
00164     while nr1 < len1 and nr2 < len2 and list1[nr1] == list2[nr2]:
00165         nr1 += 1
00166         nr2 += 1
00167         i += 1
00168         if i >= maxcount and maxcount > 0:
00169             break
00170     return i
00171 
00172 def find_match(list1, list2, nr1, nr2, mincount=3):
00173     """searches next matching pattern with lenght mincount
00174        if no pattern is found len of the both lists is returned
00175     """
00176     len1 = len(list1)
00177     len2 = len(list2)
00178     hit1 = None
00179     hit2 = None
00180     idx1 = nr1
00181     idx2 = nr2
00182 
00183     while (idx1 < len1) or (idx2 < len2):
00184         i = nr1
00185         while i <= idx1:
00186             hit_count = match(list1, list2, i, idx2, mincount)
00187             if hit_count >= mincount:
00188                 hit1 = (i, idx2)
00189                 break
00190             i += 1
00191 
00192         i = nr2
00193         while i < idx2:
00194             hit_count = match(list1, list2, idx1, i, mincount)
00195             if hit_count >= mincount:
00196                 hit2 = (idx1, i)
00197                 break
00198             i += 1
00199 
00200         if hit1 or hit2:
00201             break
00202         if idx1 < len1:
00203             idx1 += 1
00204         if idx2 < len2:
00205             idx2 += 1
00206 
00207     if hit1 and hit2:
00208         #XXX which one?
00209         return hit1
00210     elif hit1:
00211         return hit1
00212     elif hit2:
00213         return hit2
00214     else:
00215         return (len1, len2)
00216 
00217 def main():
00218 
00219     text0 = """AAA 001
00220 AAA 002
00221 AAA 003
00222 AAA 004
00223 AAA 005
00224 AAA 006
00225 AAA 007
00226 AAA 008
00227 AAA 009
00228 AAA 010
00229 AAA 011
00230 AAA 012
00231 AAA 013
00232 AAA 014
00233 """
00234 
00235     text1 = """AAA 001
00236 AAA 002
00237 AAA 005
00238 AAA 006
00239 AAA 007
00240 AAA 008
00241 BBB 001
00242 BBB 002
00243 AAA 009
00244 AAA 010
00245 BBB 003
00246 """
00247 
00248     text2 = """AAA 001
00249 AAA 002
00250 AAA 003
00251 AAA 004
00252 AAA 005
00253 AAA 006
00254 AAA 007
00255 AAA 008
00256 CCC 001
00257 CCC 002
00258 CCC 003
00259 AAA 012
00260 AAA 013
00261 AAA 014
00262 """
00263 
00264 
00265     text = text_merge(text0, text1, text2)
00266     print(text)
00267 
00268 if __name__ == '__main__':
00269     main()