:license: BSD, see LICENSE for details.
+from operator import itemgetter
+from collections import defaultdict
from itertools import product
- from itertools import izip_longest as zip_longest
- from itertools import zip_longest
-from difflib import SequenceMatcher
from sphinx.util import PeekableIterator
-def merge_node(old, new):
- Merges the `old` node with the `new` one, if it's successful the `new` node
- get's the unique identifier of the `new` one and ``True`` is returned. If
- the merge is unsuccesful ``False`` is returned.
- equals, changed, replaced = make_diff(old.rawsource,
def merge_doctrees(old, new, condition):
Merges the `old` doctree with the `new` one while looking at nodes matching
A callable which returns either ``True`` or ``False`` for a given node.
- old_iter = PeekableIterator(old.traverse(condition))
- new_iter = PeekableIterator(new.traverse(condition))
- for old_node, new_node in zip_longest(old_iter, new_iter):
+ old_nodes = old.traverse(condition)
+ new_nodes = new.traverse(condition)
+ ratios = defaultdict(list)
+ for old_node, new_node in product(old_nodes, new_nodes):
+ ratios[old_node, new_node] = get_ratio(old_node.rawsource,
+ ratios = sorted(ratios.iteritems(), key=itemgetter(1))
+ for (old_node, new_node), ratio in ratios:
- if not merge_node(old_node, new_node):
- for i, very_old_node in enumerate(old_nodes):
- if merge_node(very_old_node, new_node):
- # If the last identified node which has not matched the
- # unidentified node matches the current one, we have to
- # assume that the last unidentified one has been
- # As the required time multiplies with each insert, we
- # want to avoid that by checking if the next
- # unidentified node matches the current identified one
- # and if so we make a shift.
- if i == len(old_nodes):
- next_new_node = new_iter.next()
- if not merge_node(old_node, next_new_node):
- for (i, new_node), (j, old_node) in product(enumerate(new_nodes),
- if merge_node(old_node, new_node):
- # Yielding the new nodes here makes it possible to use this generator
+ new_node.uid = old_node.uid
+ new_node.uid = uuid4().hex
+def (old, new):
- Takes two strings `old` and `new` and returns a :class:`tuple` of boolean
- values ``(equals, changed, replaced)``.
- ``True`` if the `old` string and the `new` one are equal.
- ``True`` if the `new` string is a changed version of the `old` one.
- ``True`` if the `new` string and the `old` string are totally
- .. note:: This assumes the two strings are human readable text or at least
- something very similar to that, otherwise it can not detect if
- the string has been changed or replaced. In any case the
- detection should not be considered reliable.
+ Returns a "similiarity ratio" representing the similarity between the two
+ strings where 0 is equal and anything above less than equal.
- return True, False, False
- if new in old or levenshtein_distance(old, new) / (len(old) / 100.0) < 70:
- return False, True, False
- return False, False, True
+ ratio = levenshtein_distance(old, new) / (len(old) / 100.0)
def levenshtein_distance(a, b):