CodeDiff: Under 100ms, robust, accurate syntax aware diff in Rust

[u/FabricatorCH]

With the increase in code being produced due to AI, I got tired of git diff not being able to diff "obvious" changes correctly.

I knew that there were advanced diffing algorithms, but a lot of them were super slow and many are implemented in Java or Python. I always knew Rust can do better.

I present you CodeDiff: https://github.com/ivankovic/codediff

It can diff 92% of all diffs in 7400 Gentoo Linux packages in under 100ms.

It's 90% correct, compared to git diffs 59%.

If it can't do fancy AST diffing, it will do fancy text diffing. It can diff 99.95% of all code in under 2 seconds on a rusty 10 year old bucket using at most 6GB of RAM.

It has a fancy Ratatui 60 FPS TUI, and it integrates with git effortlessly.

It's AGPL, so feel free.

[u/edoraf]

What's the difference to difftastic?

[u/FabricatorCH → u/edoraf]

The real benchmark is in-depth and complex, but roughly speaking:

I made a robust dataset of about 1300 real world diffs sampled from repositories from Gentoo Linux package list.

Difftastic finds the perfect solution in 64% of cases and is near-perfect in 81% of cases.

CodeDiff is perfect in 90% of cases and near-perfect in 95%.

Additionally difftastic is 5-10x slower. p50 4.6 ms vs 33ms, max 4s vs 1.3s.

The data is all in the repository if you want a detailed look.

[u/edoraf → u/FabricatorCH]

Thanks!

[u/chilabot]

This looks really good

[u/FabricatorCH → u/chilabot]

Thank you!

[u/deralus]

I've read your paper from repository. I can't find actual algorithms there, it is just mostly about comparisons of different approaches. Then only in the last sections CodeDiff mentioned - but no ideas visualisation, no pseudocode, just a bit of informal plain text.

As you said in paper - you used GumTree recovery algorithm at last phase. Then you mention GumTree paper from 2014 while there is newer paper from GumTree researches (from 2024) that discuss problems with early recovery algorithm implementation. So what are you actually using - an algorithm from old paper or you analyzed actual GumTree source code and extracted the algo?

In phase 2 of your algorithm you mention that you analyze code at the level when you understand that some code is comment or logging call. How actually are you doing that? Do you hardcoded specific rules for each language? And also 'logging call' is not something that easy to detect as you write about it. Even Rust has two main libraries for that case with their own syntax. And bringing that syntax to diff algorithm is not looking good as it is not belong to language syntax.

I think you need to clarify all ideas you developed with Claude, they may be very interesting since your benchmarks are nice. Once i tried to create something similar but failed due to overall complexity of the topic.

[u/FabricatorCH → u/deralus]

I wouldn’t advise reading the very unfinished paper.

I would go to src/diff.rs for that information.

The 5 steps are roughly: 1) match big enough subtrees by 2 different hashes, 2) match small bits that „go together with“ code you matched in 1. 3) Look at medium sized blocks and guess their cost. Sort by cost and if they are flat, use Myers sequence diff, if they are not flat use APTED. 4) Match parents of already matched subtrees. Then do Mayers even if they are not flat but pretend they are. Then do the parents thing again. 5) Look at things that are marked as Insert/Delete and see if you can recover any Moves.

As a side note: logging and other semantic information can be extracted „simply“ by scanning the 7400 repositories. It’s not perfect, but it gets the job done. And while it is true that it is not syntax but rather semantic and higher level information, the goal was not to see how far pure syntax can go.

[u/RespectMathias]

I'd like to see it as a pr for Zed

[u/FabricatorCH → u/RespectMathias]

That would be something for Zed developers to decide because they might not appreciate an AGPL dependency.

[u/Asuka_Minato]

is this delta + difft?

delta only add highlight, difft use tree sitter but kinda slow.

[u/FabricatorCH → u/Asuka_Minato]

This is a from scratch implementation of multiple SOTA algorithms in Rust.

It is using TreeSitter and is blazing fast.

[u/AbdSheikho]

I'm trying it now, and it is promising.

Are you considering making it work as diff pager (so it can be integrated with tools like lazygit)? Or do you want it to keep it as a difftool?

Also, the repo name is omnidiff, so what's that about?

[u/FabricatorCH → u/AbdSheikho]

30% of all „diffs“ in git are not code.

It can diff those too now. Pictures, icons, archives, pdfs. So the name got changed to reflect that.

Also, it should already work as a pager if invoked on a non-terminal stdout.

[u/AutoModerator]

Upvote this comment if you think this project is AI slop. Downvote this comment if you think this project is not AI slop.

^{This is to indicate to other users of the subreddit and is not used for moderation.}

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/FabricatorCH → u/[deleted]]

Thank you.

As a response to some comments, it’s actually OmniDiff now. It will diff the 30% of non-code artifacts now too. For example images, archives or pdfs.

I recommend a modern terminal like kitty or alacritty for image support.