Back to index

moin  1.9.0~rc2
Functions | Variables
MoinMoin.util.diff3 Namespace Reference

Functions

def text_merge
def merge
def tripple_match
def match
def find_match
def main

Variables

tuple default_markers

Function Documentation

def MoinMoin.util.diff3.find_match (   list1,
  list2,
  nr1,
  nr2,
  mincount = 3 
)
searches next matching pattern with lenght mincount
   if no pattern is found len of the both lists is returned

Definition at line 172 of file diff3.py.

00172 
00173 def find_match(list1, list2, nr1, nr2, mincount=3):
00174     """searches next matching pattern with lenght mincount
00175        if no pattern is found len of the both lists is returned
00176     """
00177     len1 = len(list1)
00178     len2 = len(list2)
00179     hit1 = None
00180     hit2 = None
00181     idx1 = nr1
00182     idx2 = nr2
00183 
00184     while (idx1 < len1) or (idx2 < len2):
00185         i = nr1
00186         while i <= idx1:
00187             hit_count = match(list1, list2, i, idx2, mincount)
00188             if hit_count >= mincount:
00189                 hit1 = (i, idx2)
00190                 break
00191             i += 1
00192 
00193         i = nr2
00194         while i < idx2:
00195             hit_count = match(list1, list2, idx1, i, mincount)
00196             if hit_count >= mincount:
00197                 hit2 = (idx1, i)
00198                 break
00199             i += 1
00200 
00201         if hit1 or hit2:
00202             break
00203         if idx1 < len1:
00204             idx1 += 1
00205         if idx2 < len2:
00206             idx2 += 1
00207 
00208     if hit1 and hit2:
00209         #XXX which one?
00210         return hit1
00211     elif hit1:
00212         return hit1
00213     elif hit2:
00214         return hit2
00215     else:
00216         return (len1, len2)

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 217 of file diff3.py.

00217 
00218 def main():
00219 
00220     text0 = """AAA 001
00221 AAA 002
00222 AAA 003
00223 AAA 004
00224 AAA 005
00225 AAA 006
00226 AAA 007
00227 AAA 008
00228 AAA 009
00229 AAA 010
00230 AAA 011
00231 AAA 012
00232 AAA 013
00233 AAA 014
00234 """
00235 
00236     text1 = """AAA 001
00237 AAA 002
00238 AAA 005
00239 AAA 006
00240 AAA 007
00241 AAA 008
00242 BBB 001
00243 BBB 002
00244 AAA 009
00245 AAA 010
00246 BBB 003
00247 """
00248 
00249     text2 = """AAA 001
00250 AAA 002
00251 AAA 003
00252 AAA 004
00253 AAA 005
00254 AAA 006
00255 AAA 007
00256 AAA 008
00257 CCC 001
00258 CCC 002
00259 CCC 003
00260 AAA 012
00261 AAA 013
00262 AAA 014
00263 """
00264 
00265 
00266     text = text_merge(text0, text1, text2)
00267     print(text)

Here is the call graph for this function:

def MoinMoin.util.diff3.match (   list1,
  list2,
  nr1,
  nr2,
  maxcount = 3 
)
return the number matching items after the given positions
    maximum maxcount lines are are processed

Definition at line 157 of file diff3.py.

00157 
00158 def match(list1, list2, nr1, nr2, maxcount=3):
00159     """ return the number matching items after the given positions
00160         maximum maxcount lines are are processed
00161     """
00162     i = 0
00163     len1 = len(list1)
00164     len2 = len(list2)
00165     while nr1 < len1 and nr2 < len2 and list1[nr1] == list2[nr2]:
00166         nr1 += 1
00167         nr2 += 1
00168         i += 1
00169         if i >= maxcount and maxcount > 0:
00170             break
00171     return i

Here is the caller graph for this function:

def MoinMoin.util.diff3.merge (   old,
  other,
  new,
  allow_conflicts = 1,
  markers 
)
do line by line diff3 merge
    input must be lists containing single lines

Definition at line 19 of file diff3.py.

00019 
00020 def merge(old, other, new, allow_conflicts=1, *markers):
00021     """ do line by line diff3 merge
00022         input must be lists containing single lines
00023     """
00024     if not markers:
00025         markers = default_markers
00026     marker1, marker2, marker3 = markers
00027 
00028     old_nr, other_nr, new_nr = 0, 0, 0
00029     old_len, other_len, new_len = len(old), len(other), len(new)
00030     result = []
00031 
00032     while old_nr < old_len and other_nr < other_len and new_nr < new_len:
00033         # unchanged
00034         if old[old_nr] == other[other_nr] == new[new_nr]:
00035             result.append(old[old_nr])
00036             old_nr += 1
00037             other_nr += 1
00038             new_nr += 1
00039         else:
00040             if allow_conflicts == 2: # experimental addition to the algorithm
00041                 if other[other_nr] == new[new_nr]:
00042                     result.append(new[new_nr])
00043                     other_nr += 1
00044                     new_nr += 1
00045                     continue
00046             new_match = find_match(old, new, old_nr, new_nr)
00047             other_match = find_match(old, other, old_nr, other_nr)
00048             # new is changed
00049             if new_match != (old_nr, new_nr):
00050                 new_changed_lines = new_match[0] - old_nr
00051                 # other is unchanged
00052                 if match(old, other, old_nr, other_nr,
00053                          new_changed_lines) == new_changed_lines:
00054                     result.extend(new[new_nr:new_match[1]])
00055                     old_nr = new_match[0]
00056                     new_nr = new_match[1]
00057                     other_nr += new_changed_lines
00058                 # both changed, conflict!
00059                 else:
00060                     if not allow_conflicts:
00061                         return None
00062                     old_m, other_m, new_m = tripple_match(
00063                         old, other, new, other_match, new_match)
00064                     result.append(marker1)
00065                     result.extend(other[other_nr:other_m])
00066                     result.append(marker2)
00067                     result.extend(new[new_nr:new_m])
00068                     result.append(marker3)
00069                     old_nr, other_nr, new_nr = old_m, other_m, new_m
00070             # other is changed
00071             else:
00072                 other_changed_lines = other_match[0] - other_nr
00073                 # new is unchanged
00074                 if match(old, new, old_nr, new_nr,
00075                          other_changed_lines) == other_changed_lines:
00076                     result.extend(other[other_nr:other_match[1]])
00077                     old_nr = other_match[0]
00078                     other_nr = other_match[1]
00079                     new_nr += other_changed_lines
00080                 # both changed, conflict!
00081                 else:
00082                     if not allow_conflicts:
00083                         return None
00084                     old_m, other_m, new_m = tripple_match(
00085                         old, other, new, other_match, new_match)
00086                     result.append(marker1)
00087                     result.extend(other[other_nr:other_m])
00088                     result.append(marker2)
00089                     result.extend(new[new_nr:new_m])
00090                     result.append(marker3)
00091                     old_nr, other_nr, new_nr = old_m, other_m, new_m
00092 
00093     # process tail
00094     # all finished
00095     if old_nr == old_len and other_nr == other_len and new_nr == new_len:
00096         pass
00097     # new added lines
00098     elif old_nr == old_len and other_nr == other_len:
00099         result.extend(new[new_nr:])
00100     # other added lines
00101     elif old_nr == old_len and new_nr == new_len:
00102         result.extend(other[other_nr:])
00103     # new deleted lines
00104     elif (new_nr == new_len and (old_len - old_nr == other_len - other_nr) and
00105           match(old, other, old_nr, other_nr, old_len-old_nr) == old_len - old_nr):
00106         pass
00107     # other deleted lines
00108     elif (other_nr == other_len and (old_len - old_nr == new_len-new_nr) and
00109           match(old, new, old_nr, new_nr, old_len-old_nr) == old_len - old_nr):
00110         pass
00111     # conflict
00112     else:
00113         if new == other:
00114             result.extend(new[new_nr:])
00115         else:
00116             if not allow_conflicts:
00117                 return None
00118             result.append(marker1)
00119             result.extend(other[other_nr:])
00120             result.append(marker2)
00121             result.extend(new[new_nr:])
00122             result.append(marker3)
00123     return result

Here is the call graph for this function:

Here is the caller graph for this function:

def MoinMoin.util.diff3.text_merge (   old,
  other,
  new,
  allow_conflicts = 1,
  markers 
)
do line by line diff3 merge with three strings 

Definition at line 13 of file diff3.py.

00013 
00014 def text_merge(old, other, new, allow_conflicts=1, *markers):
00015     """ do line by line diff3 merge with three strings """
00016     result = merge(old.splitlines(1), other.splitlines(1), new.splitlines(1),
00017                    allow_conflicts, *markers)
00018     return ''.join(result)

Here is the call graph for this function:

Here is the caller graph for this function:

def MoinMoin.util.diff3.tripple_match (   old,
  other,
  new,
  other_match,
  new_match 
)
find next matching pattern unchanged in both other and new
   return the position in all three lists

Definition at line 124 of file diff3.py.

00124 
00125 def tripple_match(old, other, new, other_match, new_match):
00126     """find next matching pattern unchanged in both other and new
00127        return the position in all three lists
00128     """
00129     while 1:
00130         difference = new_match[0] - other_match[0]
00131         # new changed more lines
00132         if difference > 0:
00133             match_len = match(old, other, other_match[0], other_match[1],
00134                               difference)
00135             if match_len == difference:
00136                 return (new_match[0], other_match[1]+difference, new_match[1])
00137             else:
00138                 other_match = find_match(old, other,
00139                                          other_match[0] + match_len,
00140                                          other_match[1] + match_len)
00141         # other changed more lines
00142         elif difference < 0:
00143             difference = -difference
00144             match_len = match(old, new, new_match[0], new_match[1],
00145                               difference)
00146             if match_len == difference:
00147                 return (other_match[0], other_match[1],
00148                         new_match[0] + difference)
00149             else:
00150                 new_match = find_match(old, new,
00151                                        new_match[0] + match_len,
00152                                        new_match[1] + match_len)
00153         # both conflicts change same number of lines
00154         # or no match till the end
00155         else:
00156             return (new_match[0], other_match[1], new_match[1])

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

Initial value:
00001 ('<<<<<<<<<<<<<<<<<<<<<<<<<\n',
00002                    '=========================\n',
00003                    '>>>>>>>>>>>>>>>>>>>>>>>>>\n')

Definition at line 9 of file diff3.py.