__init__.py 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198
  1. '''
  2. Simple Diff for Python version 1.0
  3. Annotate two versions of a list with the values that have been
  4. changed between the versions, similar to unix's `diff` but with
  5. a dead-simple Python interface.
  6. (C) Paul Butler 2008-2012 <http://www.paulbutler.org/>
  7. May be used and distributed under the zlib/libpng license
  8. <http://www.opensource.org/licenses/zlib-license.php>
  9. '''
  10. __all__ = ['diff', 'string_diff', 'html_diff']
  11. __version__ = '1.0'
  12. def diff(old, new):
  13. '''
  14. Find the differences between two lists. Returns a list of pairs, where the
  15. first value is in ['+','-','='] and represents an insertion, deletion, or
  16. no change for that list. The second value of the pair is the list
  17. of elements.
  18. Params:
  19. old the old list of immutable, comparable values (ie. a list
  20. of strings)
  21. new the new list of immutable, comparable values
  22. Returns:
  23. A list of pairs, with the first part of the pair being one of three
  24. strings ('-', '+', '=') and the second part being a list of values from
  25. the original old and/or new lists. The first part of the pair
  26. corresponds to whether the list of values is a deletion, insertion, or
  27. unchanged, respectively.
  28. Examples:
  29. >>> diff([1,2,3,4],[1,3,4])
  30. [('=', [1]), ('-', [2]), ('=', [3, 4])]
  31. >>> diff([1,2,3,4],[2,3,4,1])
  32. [('-', [1]), ('=', [2, 3, 4]), ('+', [1])]
  33. >>> diff('The quick brown fox jumps over the lazy dog'.split(),
  34. ... 'The slow blue cheese drips over the lazy carrot'.split())
  35. ... # doctest: +NORMALIZE_WHITESPACE
  36. [('=', ['The']),
  37. ('-', ['quick', 'brown', 'fox', 'jumps']),
  38. ('+', ['slow', 'blue', 'cheese', 'drips']),
  39. ('=', ['over', 'the', 'lazy']),
  40. ('-', ['dog']),
  41. ('+', ['carrot'])]
  42. '''
  43. # Create a map from old values to their indices
  44. old_index_map = dict()
  45. for i, val in enumerate(old):
  46. old_index_map.setdefault(val,list()).append(i)
  47. # Find the largest substring common to old and new.
  48. # We use a dynamic programming approach here.
  49. #
  50. # We iterate over each value in the `new` list, calling the
  51. # index `inew`. At each iteration, `overlap[i]` is the
  52. # length of the largest suffix of `old[:i]` equal to a suffix
  53. # of `new[:inew]` (or unset when `old[i]` != `new[inew]`).
  54. #
  55. # At each stage of iteration, the new `overlap` (called
  56. # `_overlap` until the original `overlap` is no longer needed)
  57. # is built from the old one.
  58. #
  59. # If the length of overlap exceeds the largest substring
  60. # seen so far (`sub_length`), we update the largest substring
  61. # to the overlapping strings.
  62. overlap = dict()
  63. # `sub_start_old` is the index of the beginning of the largest overlapping
  64. # substring in the old list. `sub_start_new` is the index of the beginning
  65. # of the same substring in the new list. `sub_length` is the length that
  66. # overlaps in both.
  67. # These track the largest overlapping substring seen so far, so naturally
  68. # we start with a 0-length substring.
  69. sub_start_old = 0
  70. sub_start_new = 0
  71. sub_length = 0
  72. for inew, val in enumerate(new):
  73. _overlap = dict()
  74. for iold in old_index_map.get(val,list()):
  75. # now we are considering all values of iold such that
  76. # `old[iold] == new[inew]`.
  77. _overlap[iold] = (iold and overlap.get(iold - 1, 0)) + 1
  78. if(_overlap[iold] > sub_length):
  79. # this is the largest substring seen so far, so store its
  80. # indices
  81. sub_length = _overlap[iold]
  82. sub_start_old = iold - sub_length + 1
  83. sub_start_new = inew - sub_length + 1
  84. overlap = _overlap
  85. if sub_length == 0:
  86. # If no common substring is found, we return an insert and delete...
  87. return (old and [('-', old)] or []) + (new and [('+', new)] or [])
  88. else:
  89. # ...otherwise, the common substring is unchanged and we recursively
  90. # diff the text before and after that substring
  91. return diff(old[ : sub_start_old], new[ : sub_start_new]) + \
  92. [('=', new[sub_start_new : sub_start_new + sub_length])] + \
  93. diff(old[sub_start_old + sub_length : ],
  94. new[sub_start_new + sub_length : ])
  95. def string_diff(old, new):
  96. '''
  97. Returns the difference between the old and new strings when split on
  98. whitespace. Considers punctuation a part of the word
  99. This function is intended as an example; you'll probably want
  100. a more sophisticated wrapper in practice.
  101. Params:
  102. old the old string
  103. new the new string
  104. Returns:
  105. the output of `diff` on the two strings after splitting them
  106. on whitespace (a list of change instructions; see the docstring
  107. of `diff`)
  108. Examples:
  109. >>> string_diff('The quick brown fox', 'The fast blue fox')
  110. ... # doctest: +NORMALIZE_WHITESPACE
  111. [('=', ['The']),
  112. ('-', ['quick', 'brown']),
  113. ('+', ['fast', 'blue']),
  114. ('=', ['fox'])]
  115. '''
  116. return diff(old.split(), new.split())
  117. def html_diff(old, new):
  118. '''
  119. Returns the difference between two strings (as in stringDiff) in
  120. HTML format. HTML code in the strings is NOT escaped, so you
  121. will get weird results if the strings contain HTML.
  122. This function is intended as an example; you'll probably want
  123. a more sophisticated wrapper in practice.
  124. Params:
  125. old the old string
  126. new the new string
  127. Returns:
  128. the output of the diff expressed with HTML <ins> and <del>
  129. tags.
  130. Examples:
  131. >>> html_diff('The quick brown fox', 'The fast blue fox')
  132. 'The <del>quick brown</del> <ins>fast blue</ins> fox'
  133. '''
  134. con = {'=': (lambda x: x),
  135. '+': (lambda x: "<ins>" + x + "</ins>"),
  136. '-': (lambda x: "<del>" + x + "</del>")}
  137. return " ".join([(con[a])(" ".join(b)) for a, b in string_diff(old, new)])
  138. def check_diff(old, new):
  139. '''
  140. This tests that diffs returned by `diff` are valid. You probably won't
  141. want to use this function, but it's provided for documentation and
  142. testing.
  143. A diff should satisfy the property that the old input is equal to the
  144. elements of the result annotated with '-' or '=' concatenated together.
  145. Likewise, the new input is equal to the elements of the result annotated
  146. with '+' or '=' concatenated together. This function compares `old`,
  147. `new`, and the results of `diff(old, new)` to ensure this is true.
  148. Tests:
  149. >>> check_diff('ABCBA', 'CBABA')
  150. >>> check_diff('Foobarbaz', 'Foobarbaz')
  151. >>> check_diff('Foobarbaz', 'Boobazbam')
  152. >>> check_diff('The quick brown fox', 'Some quick brown car')
  153. >>> check_diff('A thick red book', 'A quick blue book')
  154. >>> check_diff('dafhjkdashfkhasfjsdafdasfsda', 'asdfaskjfhksahkfjsdha')
  155. >>> check_diff('88288822828828288282828', '88288882882828282882828')
  156. >>> check_diff('1234567890', '24689')
  157. '''
  158. old = list(old)
  159. new = list(new)
  160. result = diff(old, new)
  161. _old = [val for (a, vals) in result if (a in '=-') for val in vals]
  162. assert old == _old, 'Expected %s, got %s' % (old, _old)
  163. _new = [val for (a, vals) in result if (a in '=+') for val in vals]
  164. assert new == _new, 'Expected %s, got %s' % (new, _new)