`diff.term <old> <new>`

[aryairani]

• possibly/eventually some heuristic to decide when expressions have changed, vs moved or pushed into a subexpression
• eventually identifying authorship of subexpressions/changes
• we might want eventually to design a custom pretty-printing algorithm for diffs; perhaps wrapping lines differently at diff boundaries

[ChrisPenner]

I'm looking into the approach presented here: https://victorcmiraldo.github.io/data/icfp2019.pdf ; there's a Haskell implementation here

I think it'd be a really good fit for Unison because:

• It provides a generic algorithm for generating structural diffs of ASTs
• The core of the algorithm gets its performance by requiring deterministic hashing of subtrees, (Merkle trees), which we can easily obtain
• There's already a Haskell implementation, which I'll investigate (but the algorithm seems generally simple enough to re-implement if needed for our use-case)
• As an additional benefit, it generates patches, not just diffs, meaning we could potentially also use it to compute merges in Unison in the future.

After a quick read, here's my summary of the algorithm:

diff a b

• Compute the hashes of every subtree of a and b, and their intersection.
• Replace any subtrees which exist in the intersection with the hash representing their subtree.
• Compute the common spine between the simplified version of a and b

There are some complications regarding nested common subtrees, but they're handled with post-processing steps in the paper and the implementation for us.

Pretty-printing these diffs in a readable fashion will be a separate challenge, but this should give us diff trees with all the information we need to do so.

[aryairani]

Cool!

I couldn’t tell from a brief skim of the paper whether they support moves on top of inserts, deletes, copies, but I think we would want that eventually.

[ChrisPenner]

It identifies common subtrees by metavariables and you can compare positions in the old and new diffs, so yeah I'm pretty sure we could detect moves using this.

On further inspection it looks like the hdiff library would require us to use generics-mrsop classes, which are a bit gnarly, and might not give us the flexibility we need, so I think it might be in our best interests to implement the algorithm bespokely for our ABTs, which seems pretty do-able from the paper 😄 . That also would allow us to graft-in any custom functionality we need, e.g. detecting that a changed hash is just an "update" to a named term.

Maybe I'll try implementing it over JSON first to make sure I know what I'm talking about 😋