At the moment the algorithm for code diffing is a particularly efficient implementation of APTED which is a tree diffing algorithm that doesn’t natively construct anything useful for a three way diff. I have a notebook with a bunch of failed attempts at a good algorithm for a three way merge, but so far nothing particularly impressive.

It’s a long term goal to solve, but it’s the hardest one.

I’ll definitely reach out to you to upstream. Thank you for the kind offer!

[delayed]

It’s a 5 step pipeline.

In practice, tree hashing is doing a huge amount of work because most diffs are tiny. Half of all diffs are less than 10 lines, so a hash can extremely quickly match large subtrees.

In a profoundly degenerate case of a C++ header file with only a 20MB array of bytes, it detects a degenerate tree and uses Myers O(N) sequence diffing algorithm instead of treating it as a tree.

How would one craft an input that maximizes the runtime of your diff while staying below some (reasonable) bound of edit distance apart? Basically suppose I wanted to provide a malicious diff designed to hang or timeout the diff program, how would I construct it?

You need to maximize the size of the residual tree sent to the final APTED step.

I actually don’t know how to do that and stay under a bounded edit distance.

Alternatively, you can crash it if you just encode the entire “Star Trek - In the pale moonlight” episode as a sequence of bytes in a const int array in C++.

> I actually don’t know how to do that and stay under a bounded edit distance.

I’m sure there’s an interesting result there, but I am not the person to find it :D

Good episode btw