Weave – A language aware merge algorithm based on entities

Are any of these statements public, or is this all private communication?

> We are also working with GitButler team to integrate it as a research feature.

Referring to this discussion, I assume: https://github.com/gitbutlerapp/gitbutler/discussions/12274

I also think that this approach has a lot of potential. Keep up the good work sir.

The pragmatic reason weave works at the git layer: adoption. Getting people to switch merge drivers is hard enough, getting them to switch VCS is nearly impossible. So weave parses the three file versions on the fly during merge, extracts entities, resolves per-entity, and writes back a normal file that git stores as a blob. You get entity-level merging without anyone changing their workflow.

But you're pointing at the ceiling of that approach. A VCS that stores ASTs natively could answer "did any concurrent branches touch this function?" as a query, not as a computation. That's a fundamentally different capability. Beagle looks interesting, will dig into the BASON format.

We built something adjacent with sem (https://github.com/ataraxy-labs/sem) which extracts the entity dependency graph from git history. It can answer "what new uses did this function accrete" and "what's the blast radius of this change" but it's still a layer on top of git, not native storage.

The problem is that disks (and storage in general) store only bytes so you inherently need to deal with bytes at some point. You could view source code files as the serialization of the AST (or other parse tree).

This is especially apparent with LISPs and their sexprs, but equally applies to other languages too.

I built lix [0] which stores AST’s instead of blobs.

Direct AST writing works for apps that are “ast aware”. And I can confirm, it works great.

But, the all software just writes bytes atm.

The binary -> parse -> diff is too slow.

The parse and diff step need to get out of the hot path. That semi defeats the idea of a VCS that stores ASTs though.

[0] https://github.com/opral/lix

https://www.unison-lang.org/

The process of taking such a linear stream and reconstructing the arbitrary data structure used to generate it (or, in more sophisticated cases, something related to it if not identical), is deserialization. You can't send anyone a cyclic graph directly but you can send them something they can deserialize into a cyclic graph if you arrange the serialization/deserialization protocol correctly. They may deserialize it into a raw string in some programming language so they can run regexes over it. They may deserialize it into a stream of tokens. This all happens from the same source of serialized data.

So let's say we have an AST in memory. As complicated as your language likes, however recursive, however cross-"module", however bizarre it may be. But you want to store it on a disk or send it somewhere else. In that case it must be serialized and then deserialized.

What determines what the final user ends up with is not the serialization protocol. What determines what the final user ends up with is the deserialization procedure they use. They may, for instance, drop everything except some declaration of what a "package" is if they're just doing some initial scan. They may deserialize it into a compiler's AST. They may deserialize it into tree sitter's AST. They may deserialize it into some other proprietary AST used by a proprietary static code analyzer with objects designed to not just represent the code but also be immediately useful in complicated flow analyses that no other user of the data is interested in using.

The point of this seemingly rambling description of what serialization is is that

"why keep files as blobs in the first place. If a revision control system stores AST trees instead"

doesn't correspond to anything actionable or real. Structured text files are already your programming language's code stored as ASTs. The corresponding deserialization format involves "parsing" them, which is a perfectly sensible and very, very common deserialization method. For example, the HTML you are reading was deserialized into the browser's data structures, which are substantially richer than "just" an AST of HTML due to all the stuff a browser does with the HTML, with a very complicated parsing algorithm defined by the HTML standard. The textual representation may be slightly suboptimal for some purposes but they're pretty good at others (e.g., lots of regexes run against code over the years). If you want some other data structure in the consumer, the change has to happen in the code that consumes the serialized stream. There is no way to change the code as it is stored on disk to make it "more" or "less" AST-ish than it already is, and always has been.

You can see that in the article under discussion. You don't have to change the source code, which is to say, the serialized representation of code on the disk, to get this new feature. You just have to change the deserializer, in this case, to use tree sitter to parse instead of deserializing into "an array of lines which are themselves just strings except maybe we ignore whitespace for some purposes".

Once you see the source code as already being an AST, it is easy to see that there are multiple ways you could store it that could conceivably be optimized for other uses... but nothing you do to the serialization format is going to change what is possible at all, only adjust the speed at which it can be done. There is no "more AST-ish" representation that will make this tree sitter code any easier to write. What is on the disk is already maximally "AST-ish" as it is today. There isn't any "AST-ish"-ness being left on the table. The problem was always the consumers, not the representation.

And as far as I can tell, it isn't generally the raw deserialization speed nowadays that is the problem with source code. Optimizing the format for any other purpose would break the simple ability to read it is as source code, which is valuable in its own right. But then, nothing stops you from representing source code in some other way right now if you want... but that doesn't open up possibilities that were previously impossible, it just tweak how quickly some things will run.

Cheers,

The key difference: mergiraf matches individual AST nodes (GumTree + PCS triples). Weave matches entities (functions, classes, methods) as whole units. Simpler, faster, and conflicts are readable ("conflict in validate_token" instead of a tree of node triples).

The other big gap: weave ships as an MCP server with 14 tools for agent coordination. Agents can claim entities before editing and detect conflicts before they merge. That's the piece mergiraf doesn't have.

On bash: weave falls back to line-level for unsupported languages, so it'll work as well as git does there.

Adding a bash tree-sitter grammar would unlock entity-level merge for it. But I can work on it tonight, if you want it urgently.

Cheers,

If you have a language specific parser, you can make a merge algorithm like weave. But the bigger win isn't resolving conflicts git shows you. It's catching the ones git misses entirely. So in those cases weave is much better, and there also other things like confidence-scored conflict classification, you should try it out it improves the agents performance, especially if you are a power user.

Cheers,

For diffing arbitrary files outside git, we built sem (https://github.com/ataraxy-labs/sem) which does entity-level diffs. sem diff file1.py file2.py shows you which functions changed, were added, or deleted rather than line-level changes

We also handle Python class merge specifically: if both sides add different methods to the same class, weave merges them as separate inner entities rather than treating the whole class as one conflicting block. The indentation is derived from the AST structure, not from line diffing, so it can't accidentally shift a method out of its class scope.

The good part is that this research extends really good for code review because tracking entities is more semantically rich than lines.