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 sphinx.util import PeekableIterator

+# anything below that ratio is considered equal/changed

def add_uids(doctree, condition):

Adds a unique id to every node in the `doctree` which matches the condition

A callable which returns either ``True`` or ``False`` for a given node.

- old_nodes = old.traverse(condition)

- new_nodes = new.traverse(condition)

+ old_iter = old.traverse(condition)

+ new_iter = new.traverse(condition)

ratios = defaultdict(list)

- for old_node, new_node in product(old_nodes, new_nodes):

+ # compare the nodes each doctree in order

+ for old_node, new_node in zip_longest(old_iter, new_iter):

+ new_nodes.append(new_node)

+ old_nodes.append(old_node)

ratio = get_ratio(old_node.rawsource, new_node.rawsource)

ratios[old_node, new_node] = ratio

+ old_nodes.append(old_node)

+ new_nodes.append(new_node)

+ # calculate the ratios for each unequal pair of nodes, should we stumble

+ # on a pair which is equal we set the uid and add it to the seen ones

+ for old_node, new_node in product(old_nodes, new_nodes):

+ if new_node in seen or (old_node, new_node) in ratios:

+ ratio = get_ratio(old_node.rawsource, new_node.rawsource)

+ new_node.uid = old_node.uid

+ ratios[old_node, new_node] = ratio

+ # choose the old node with the best ratio for each new node and set the uid

+ # as long as the ratio is under a certain value, in which case we consider

+ # them not changed but different

ratios = sorted(ratios.iteritems(), key=itemgetter(1))

for (old_node, new_node), ratio in ratios:

+ if ratio < VERSIONING_RATIO:

new_node.uid = old_node.uid

new_node.uid = uuid4().hex

+ # create new uuids for any new node we left out earlier, this happens

+ # if one or more nodes are simply added.

+ for new_node in set(new_nodes) - seen:

+ new_node.uid = uuid4().hex

Returns a "similiarity ratio" representing the similarity between the two

strings where 0 is equal and anything above less than equal.

+ if not all([old, new]):

+ return VERSIONING_RATIO

return levenshtein_distance(old, new) / (len(old) / 100.0)

def levenshtein_distance(a, b):