Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dictdiffer: Diff and Patch Python dictionaries

github.com

Post reply on HN
Print view View original

1–10 of 11 posts

Re: Dictdiffer: Diff and Patch Python dictionaries

#2

Post by lifeisstillgood »

This is one of those odd corners of the python ecosystem

I have written at least two dict differs, and I suspect they are like web frameworks - everyone has written a half working one.

However we need good tools that get polished and standardised - this looks nice and I like the full circle ability, but in python's own version of Catch-22, until it succeeds I will stick with writing my own.

I hope it succeeds - my meware sucks

Re: Dictdiffer: Diff and Patch Python dictionaries

#6

Post by raymondh »

Some of these capabilities are already built into Python.

See Guido's "dictionary views" described at: http://www.python.org/dev/peps/pep-3106/ In Python 2.7, those dictionary views are exposed as d.viewkeys(), d.viewitems(), and d.viewvalues(). The key and item views both support set operations such as union, intersection, and difference. Also note, the dict() constructor will accept sequences of items as input. Those tool make it trivially easy to express diffing and patching in native Python:

    # diff from d to e 
    patch = (d.viewitems() - e.viewitems(),   # deletions
	     e.viewitems() - d.viewitems())   # additions

    # apply the patch to f
    # dict(f.viewitems() - patch[0] | patch[1])

Re: Dictdiffer: Diff and Patch Python dictionaries

#8

Post by ot »

raymondh wrote: post #6

Some of these capabilities are already built into Python. See Guido's "dictionary views" described at: http://www.python.org/dev/peps/pep-3106/ In Python 2.7, those dictionary views are exposed as d.viewkeys(), d.viewitems(), and d.viewvalues(). The key and item views both support set operations such as union, intersection, and difference. Also note, the dict() constructor will accept sequences of items as input. Tho…

Well, this is quite different in the sense that the "patch operations" can also operate on the values, not just add/delete/replace them. In the example, the patch pushes and pops elements from the lists, rather than replacing them altogether.

I haven't looked, but I guess it is also recursive on values that are dictionaries themselves. In this case the "patch" is a sort of sequence of edit operations on the dictionary tree.

Re: Dictdiffer: Diff and Patch Python dictionaries

#9

Post by jmmcd »

The list diff is really a set diff, if I understand it right, in that it disregards order and multiple instances? That should only happen if the dict member is a set. Members which are lists should be treated using a Levenshtein-distance style patch. For free you then get patching of string members.

I'm getting ambitious now, but what about tree-edit distance (with patch script) for members which are nested lists?

There is Python code out there for these:

https://github.com/timtadh/zhang-shasha

https://code.google.com/p/py-editdist

EDIT I have only used the above libraries for distances, not for patchable diffs. But the Levenshtein and tree-edit distance algorithms are amenable to outputting the patch scripts.

Post reply on HN