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…
Weave – A language aware merge algorithm based on entities
91–100 of 123 posts
Re: Weave – A language aware merge algorithm based on entities
#92The 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/
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.
Re: Weave – A language aware merge algorithm based on entities
#94Some 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.
Re: Weave – A language aware merge algorithm based on entities
#95Earlier 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?
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
#96At 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…
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
#97Re: Weave – A language aware merge algorithm based on entities
#98Earlier 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…
Re: Weave – A language aware merge algorithm based on entities
#99Saw 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/
Re: Weave – A language aware merge algorithm based on entities
#100Earlier 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.