Live data from Hacker News

Weave – A language aware merge algorithm based on entities

github.com

91–100 of 123 posts

Re: Weave – A language aware merge algorithm based on entities

#91
post #12

At this point, the question is: why keep files as blobs in the first place. If a revision control system stores AST trees instead, all the work is AST-level. One can run SQL-level queries then to see what is changing where. Like - do any concurrent branches touch this function? - what new uses did this function accrete recently? - did we create any actual merge conflicts? Almost LSP-level querying, involving versions…

You might need a bit more than ASTs, as you need code to be human-readable as well as machine-readable. Maybe CSTs?

Re: Weave – A language aware merge algorithm based on entities

#93

> This happens constantly when multiple AI agents work on the same codebase What? Is the idea of "multiple agents" of flesh and blood writing code that far fetched now?

I meant when they each work on a separate branch and merge back, you get the similar kinds of conflicts, where a bunch of them should not even be a conflict, so weave is trying to solve it.

I still don't understand how it makes a difference if the agent is a human or a bot?

Re: Weave – A language aware merge algorithm based on entities

#94
post #6

Some context on the validation so far: Elijah Newren, who wrote git's merge-ort (the default merge strategy), reviewed weave and said language-aware content merging is the right approach, that he's been asked about it enough times to be certain there's demand, and that our fallback-to-line-level strategy for unsupported languages is "a very reasonable way to tackle the problem." Taylor Blau from the Git team said he'…

Does this actually matter for multi-agent use cases? Surely people that are using swarms of AI agents to write code are just letting them resolve merge conflicts.

I'm running agents doing merges right now, and yes and no. They can resolve merges, but it often takes multiple extra rounds. If you can avoid that more often it will definitely save both time and money.

Re: Weave – A language aware merge algorithm based on entities

#95

Earlier quoted context omitted.

I meant when they each work on a separate branch and merge back, you get the similar kinds of conflicts, where a bunch of them should not even be a conflict, so weave is trying to solve it.

I still don't understand how it makes a difference if the agent is a human or a bot?

There's no fundamental difference, but in practice the difference is one of frequency.

E.g. I sometimes have 10+ agents kicking off changes to the same small project at the same time, and likely to all want to merge within the next 15-30 minutes. At that rate, merge conflicts happens very frequently. The agents can mostly resolve them themselves, but it wastes tokens, and time.

Re: Weave – A language aware merge algorithm based on entities

#96
post #12

At this point, the question is: why keep files as blobs in the first place. If a revision control system stores AST trees instead, all the work is AST-level. One can run SQL-level queries then to see what is changing where. Like - do any concurrent branches touch this function? - what new uses did this function accrete recently? - did we create any actual merge conflicts? Almost LSP-level querying, involving versions…

Everything on a disk ends up as a linear sequence of bytes. This is the source of the term "serialization", which I think is easy to hear as a magic word without realizing that it is actually telling you something important in its etymology: It is the process of taking an arbitrary data structure and turning it into something that can be sent or stored serially, that is, in an order, one bit at a time if you really get down to it. To turn something into a file, to send something over a socket, to read something off a sheet of paper to someone else, it has to be serialized.

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.

Re: Weave – A language aware merge algorithm based on entities

#98
post #89

Earlier quoted context omitted.

Great point. C/C++ with macros and preprocessor directives is where tree-sitter's error recovery gets stretched. We support both C and C++ in sem-core( https://github.com/Ataraxy-Labs/sem ) but the entity extraction is best-effort for heavily macro'd code. For most application-level C++ it works well, but something like the Linux kernel would be rough. Honestly that's an argument for gritzko's AST-native storage appr…

It's an argument against preprocessors for programming languages. Tree-sitter's error handling is constrained by its intended use in editors, so incrementality and efficiency are important. For diffing/merging, a more elaborate parsing algorithm might be better, for example one that uses an Earley/CYK-like algorithm but attempts to minimize some error term (which a dynamic programming algorithm could be naturally ext…

Interesting idea. Tree-sitter's trade-off (speed + incrementality over completeness) makes sense for editors but you're right that for merge/diff a more thorough parser could be worth the cost since it's a cold path, not real-time. We only parse three file versions at merge time so spending an extra 50ms on a better parse would be fine. Worth exploring, thanks for the pointer.

Re: Weave – A language aware merge algorithm based on entities

#99

Saw this on Twitter a few weeks ago, interesting approach. The post links to the GitHub repo, but imo the website does a better job of explaining what it does: https://ataraxy-labs.github.io/weave/

Thanks for sharing the website as well here. Appreciate it!

Re: Weave – A language aware merge algorithm based on entities

#100
post #95

Earlier quoted context omitted.

I still don't understand how it makes a difference if the agent is a human or a bot?

There's no fundamental difference, but in practice the difference is one of frequency. E.g. I sometimes have 10+ agents kicking off changes to the same small project at the same time, and likely to all want to merge within the next 15-30 minutes. At that rate, merge conflicts happens very frequently. The agents can mostly resolve them themselves, but it wastes tokens, and time.

This is exactly the use case, thanks for explaining.
Post reply on HN