7 ms·
Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc
- saagarjha 6y agoInteresting use of U+031F COMBINING PLUS SIGN BELOW to indicate additions, I don't think I've seen that before.
- ynx0 6y agoI think it's really cool as well. Although, it does start to look a little wonky with quotes and probably some other characters and makes skimming a bit harder. Maybe monospaced fonts will start to handle this better if it gets popular?
- eurasiantiger 6y agoRuby typography support in terminals maybe?
- hinkley 6y agoIt's the kind of UI experimentation I like to see people try, but I'm not sure they nailed this one. Probably onto something though. Try different diacritical symbols and see what sticks. Given how '"' looks, maybe combining above or below needs to vary by character. Above probably looks awful for '.' and ','. Really I think the strikethrough might suffice. The only way to know for sure is to take away the color highlighting, so my brain doesn't use it as a crutch, and see if people can still read the diff.
- jacobolus 6y agoUsing diacritics for this is extremely visually noisy and not very legible. There has to be a better method.
- colejohnson66 6y agoPlus and minus symbols at the beginning of a colored line have worked pretty well. It is a neat trick, but it is noisy.
- trentdotexe 6y agoThere's also a blog post for Graphtage. https://blog.trailofbits.com/2020/08/28/graphtage/ https://blog.trailofbits.com/2020/08/28/graphtage/
- acidbaseextract 6y agoIt's cool, but does seem quite slow. I'm diffing two 45kB CSVs on a fast computer and after 10 minutes I'm still at: Diffing: 0% ... 0/93195 [00:00<?, ?it/s] Tightening Fringe Diagonal 48 of 792: ...
- acidbaseextract 6y ago30 minutes in and I still don't have a diff of the two CSVs... Has this program worked for anyone here? Diffing: 0%| | 153/93195 [30:02<151:31:17, 5.86s/it] Tightening Fringe Diagonal 82 of 792: 48%|...| 7453/15514 [00:30<00:35, 226.08it/s]
- dan-robertson 6y agoI think it’s ended up with a quadratic algorithm for diffing sequences and a quadratic log algorithm for diffing dictionaries. To understand why the sequences problem is quadratic, consider a sequence A of length m being doffed with a sequence B of length n. We want to express our diff in the minimum number of operations where an operation is removing, adding, or editing an element in the sequence. Construct a graph as follows: the nodes will be the points on an mxn lattice corresponding to points in the two sequences. An edge going right means “delete this item from sequence A,” and costs (eg 1). An edge going down means “add this item from sequence B” and has a similar cost. An edge going diagonally down and right means to edit the item in A into the item in B and it’s cost depends on how different they are. The problem is to find the shortest path from the top left to the bottom right. If you could compute the entire graph for free and then applied something like Dijkstra’s algorithm you would be worst-case quadratic (if all the diagonal costs were 2 or more, you would need to touch every node). There are a few ways you could try to improve this: 1. Look for easy opportunities to optimise. Eg you could have a patience style strategy of cutting off any common prefix or suffix. This won’t help in the worst case. 2. Limit to a fixed width diagonal. This might mean worse diffs but means the graph search problem becomes more linear. I suspect something is going on with the diagonal based on the description 3. Somehow develop some good heuristics and use a better search algorithm like A*. This might not help in the worst case 4. Something else.
- 6y ago
- kemitchell 6y ago> Graphtage matches ordered sequences like lists using an “online”[note], “constructive”[note] implementation of the Levenshtein distance metric[note], similar to the Wagner–Fischer algorithm[note[. The algorithm starts with an unbounded mapping and iteratively improves it until the bounds converge, at which point the optimal edit sequence is discovered. This is implemented in the graphtage.levenshtein module. https://trailofbits.github.io/graphtage/latest/howitworks.html https://trailofbits.github.io/graphtage/latest/howitworks.ht... So not a tree algo, but an adaptation of a list-diff algo? Or is this just a note on how the tree-diff compares sequences?
- spankalee 6y agoAnyone know of similar libraries in JavaScript? It's difficult to search for HTML diff libraries these days because all the hits are vdom like things, instead of diffing HTML text for development / testing.
- stereosteve 6y agoCan relate. After some searching I found: https://github.com/Teamwork/visual-dom-diff https://github.com/Teamwork/visual-dom-diff Which is quite good and fast. Encodes HTML tags as Unicode chars, calls diff-match-path and uses diff to build a final visual output.
- pimlottc 6y agoCheers for making this a local tool. So many versions of this sort of tool are online-only, which is a non-starter for proprietary data.
- jkaptur 6y agoMy diff tool, diff.so, is a web app, but it doesn’t send the text to the server (unless you publish). I wish there were a technical mechanism that could guarantee and enforce that, and certify it to users.
- tmpz22 6y agoYou could distribute it as a single index.html file, with unobfuscated/unminimized vanilla javascript. The user could then execute it offline no problem.
- jkaptur 6y agoThat’s an interesting idea - you could even imagine an “Electron without the networking” so you wouldn’t have to take the whole computer offline.
- _frkl 6y agoFor fun, you could even use redbean ( https://justine.lol/redbean/index.html https://justine.lol/redbean/index.html ), which has been discussed on here recently. That would give you a tiny executable running a webserver that serves your webapp locally. Probably not much advantage compared to a plain html file, though. Might be smaller overall, since everything would be compressed.
- thunderbong 6y agoI'm also very impressed by redbean. However, I couldn't get it to work, just like many of the other HNers on that thread.
- 6y ago
- jonnycomputer 6y agoThis could really use more input/output examples in the readme to get a feel for what it would be like to use.
- beams 6y agoCool I will definitely try this. Thank you
- indeyets 6y agoIs there a corresponding patch utility? Can I generate compact diff file for changed dataset, distribute it and have people apply the difference on their side?
- ducktective 6y agoAny chance of integration with vimdiff? Any ways to have "semantic" diffing in vimdiff?
- jrockway 6y agoThis is neat. I decided to diff two pods in a replicated Kubernetes service. It seemed that it was going to take forever to run, so I just wrote a short Go program to do the same thing (load two JSON files into a map[string]interface{}, cmp.Diff them) while it was going: https://gist.github.com/jrockway/73982949b3d2ce9b443528042c4562d4 https://gist.github.com/jrockway/73982949b3d2ce9b443528042c4... My program runs in less than 10 milliseconds (/usr/bin/time reports 0.00 seconds), and graphtage takes 5 minutes and 17 seconds. I'm 317,000x faster! (Not including the time to write the program; if you do that, then it's about even assuming graphtage took 0 seconds to write.) Graphtage prints the entire file in JQ colors, with diffs inside fields colored red and green, which I love: ... "hostIP": "10.136.13̟9̟2̶1̶.139̟1̶", "podIP": "10.244.1.18̟6̟7̶", ... (My terminal can't display the dots under the numbers and the strikethrough, but it looks great on HN! I really love it.) My program produces relatively boring line-by-line diffs: - "hostIP": string("10.136.121.131"), + "hostIP": string("10.136.139.139"), "phase": string("Running"), - "podIP": string("10.244.1.17"), + "podIP": string("10.244.1.186"), Honestly, I get what I want out of mine, and wait 317,000x less time, so... I probably won't be using this on a daily basis. But I will be stealing those dots and Unicode strikethroughs.
- bboreham 6y agoYour approach works less well if someone re-orders one of the arrays, like `containers` or `env`.
- rmetzler 6y agoIt's neat that you built what you needed in a few lines of code. I must say, I don't quite like the output of Graphtage, I like your's a little bit more, but without a context it's not easy to see how podIP is nested. Usecases might be a little bit different, but please allow me to share my solution. The problem with diffing JSON and yaml is, that these formats aren't line based and hashes don't need to be ordered. But there is gron to turn json into a greppable line-based format [1]. Then you can sort. The sorted output is possible to diff now and then you can color the diff output with delta or a similar tool [2]. diff -u <(kubectl get pod pod1 -o json | gron | sort) <(kubectl get pod pod2 -o json | gron | sort) | delta --light --word-diff-regex="\W+" This output provides a lot of context for me to see and understand the differences. [1] gron https://github.com/tomnomnom/gron https://github.com/tomnomnom/gron [2] delta https://github.com/dandavison/delta https://github.com/dandavison/delta
- deknos 6y agoand now please, build a tool which converts all these thinks, like imagemagick for machinereadable documents.
- hermitcrab 6y agoIf you mean convert between data formats (e.g. between, CSV,YAML,JSON, XML) there are programs already that can do that. For example our Easy Data Transform. However there are wrinkles because some of these formats are trees and some are tables. Flattening a tree into a table isn't too hard. But unflattening a table back into the same tree as the original is trickier. Has anyone got any good references on that?
- deknos 6y agodo you have a list for that? i am aware, that there are dialects and {table,trees,graphs}<->{table,trees,graphs} may be a problem for some languages, but having it at least would be a progress.
- hermitcrab 6y agoDo you mean a link? If so: https://www.easydatatransform.com/ https://www.easydatatransform.com/ Just as an example of the tree<->table issue: If you input this JSON tree: { "Color": "Blue", "Part": [ { "Type": "A", "Number": [ "1", "2" ] }, { "Type": "B", "Number": [ "1" ] } ] It can be converted to a table as: Color,Part.Type,Part.Number Blue,A,1 Blue,A,2 Blue,B,1 Which is fine is you then want to output as Excel, CSV etc. But if you then output that back to JSON you get: [ { "Color": "Blue", "Part": { "Type": "A", "Number": "1" } }, { "Color": "Blue", "Part": { "Type": "A", "Number": "2" } }, { "Color": "Blue", "Part": { "Type": "B", "Number": "1" } } ] Which is conceptually equivalent, but less compact (similarly for XML). I am hoping to fix this issue. But if anyone has any links to how to unflatten a table into a compact tree, I'm all ears.
- deknos 6y ago
- BadOakOx 6y agoIt seems, nobody is satisfied with the recent JSON diff utilities and everybody has a different take on it. A few weeks back I started my semantic JSON compare too: https://paldys.github.io/semantic-json/ https://paldys.github.io/semantic-json/ Your data stays in the browser. The list compare is pretty naive at the moment, and it doesn't allow key changes as Graphtage promises.
- carapace 6y ago(The name Trail of Bits reminds me of the Trail of Tears. Maybe it's just an unfortunate co-incidence?)
- davedrouin 6y agoThanks for making this - great for displaying diffs in dicts for unit test assertion failures.