DarkPlayer 5 days ago | next |

Looking at the architecture, they will probably run into some issues. We are doing something similar with SemanticDiff [1] and also started out using tree-sitter grammars for parsing and GumTree for matching. Both choices turned out to be problematic.

Tree sitter grammars are primarily written to support syntax highlighting and often use a best effort approach to parsing. This is perfectly fine for syntax highlighting, since the worst that can happen is that a few characters are highlighted incorrectly. However, when diffing or modifying code you really want the code to be parsed according to the upstream grammar, not something that mostly resembles it. We are currently in the process of moving away from tree-sitter and instead using the parsers provided by the languages themselves where possible.

GumTree is good at returning a result quickly, but there are quite a few cases where it always returned bad matches for us, no matter how many follow-up papers with improvements we tried to implement. In the end we switched over to a dijkstra based approach that tries to minimize the cost of the mapping, which is more computationally expensive but gives much better results. Difftastic uses a similar approach as well.

[1]: https://semanticdiff.com/

wetneb 5 days ago | root | parent | next |

Thanks for the insightful comments! You surely have a lot more experience than me there, but my impression was that producing visual diffs and merging files are tasks that put different requirements on the tree matching algorithms, and Dijkstra-style approaches felt more fitting for diffs than for merging, so that's why I went for GumTree as it seemed to be the state of the art for merging. Does SemanticDiff offer a merge driver? I could only find documentation about diffing on the website.

As to mismatches: yes, they are bound to happen in some cases. Even for line-based diffing, Git uses rather convoluted heuristics to avoid them (with the "histogram" diff algorithm), but they can't be completely ruled out there either. I hope that with enough safeguards (helper to review merges, downstream consistency checks with local fall-back to line-based diffing) they can be lived with. I'm happy to try other matching algorithms if they are more promising though (there isn't much coupling with the rest of the pipeline).

Concerning tree-sitter, I have noticed some small issues, but nothing that was a show-stopper so far. I actually like it that it's designed for syntax highlighting, because it's really helpful that the representations it gives stay faithful to the original source, to avoid introducing reformatting noise in the merging process. Parsers written for a specific language can sometimes be too zealous (stripping comments out, doing some normalizations behind your back). That's a problem in Spork (which uses Spoon, a pretty advanced Java parser). And the uniform API tree-sitter offers over all those parsers is just too good to give up, in my opinion.

DarkPlayer 5 days ago | root | parent |

I don't think that different algorithms are better for merging or diffing. In both cases, the first step is to match identical nodes, and the quality of the final result depends heavily on this step. The main problem with GumTree is that it is a greedy algorithm. One incorrectly matched node can completely screw up the rest of the matches. A typical example we encountered was adding a decorator to a function in Python. When other functions with the same decorator followed, the algorithm would often map the newly added decorator to an existing decorator, causing all other decorator mappings to be "off-by-one". GumTree has a tendency to come up with more changes than there actually are.

We try to really get the diff quality nailed down before going after merges. We don't have merge functionallity in SemanticDiff yet.

The main issue we have with tree-sitter is that the grammars are often written from scratch and not based on the upstream grammar definition. Sometimes they only cover the most likely cases which can lead to parsing errors or incorrectly parsed code. When you encounter parsing errors it can be difficult to fix them, because the upstream grammar is structured completely different. To give you an example, try to compare the tree-sitter Go grammar for types [1] with the upstream grammar [2]. It is similar but the way the rules are structured is somewhat inverted.

We use separate executables for the parsers (this also helps to secure them using seccomp on Linux), and they all use the same JSON schema for their output. This allows us to write the parser executable in the most appropriate language for the target language. Building all them statically and cross-platform for our VS Code extension isn't easy though ;)

[1]: https://github.com/tree-sitter/tree-sitter-go/blob/master/gr... [2]: https://go.dev/ref/spec#Types

wetneb 5 days ago | root | parent |

Thanks for the details. Concerning matching for diffing vs for merging, the differences I can think of are:

- for diffing, the matching of the leaves is what matters the most, for merging the internal nodes are more important,

- for diffing, it feels more acceptable to restrict the matching to be monotonous on the leaves since it's difficult to visually represent moves if you can detect them. For merging, supporting moves is more interesting as it lets you replay changes on the moved element,

- diffing needs to be faster than merging, so the accuracy/speed tradeoffs can be different.

Packaging parsers into separate executables seems like hard work indeed! I assume you also considered fixing the tree-sitter grammars (vendoring them as needed, if the fixes can't be upstreamed)? Tree-sitter parsers are being used for a lot more than syntax highlighting these days (for instance GitHub's "Symbols" panel) so I would imagine maintainers should be open to making grammars more faithful to the official specs. I'm not particularly looking forward to maintaining dozens of forked grammars but it still feels a lot easier than writing parsers in different languages. I guess you have different distribution constraints also.

DarkPlayer 5 days ago | root | parent |

> - for diffing, the matching of the leaves is what matters the most, for merging the internal nodes are more important,

The leaves are the ones that end up being highlighted in the diff, but the inner nodes play an important role as well. We try to preserve as much of the code structure as possible when mapping the nodes. A developer is unlikely to change the structure of the code just for fun. A mapping with a larger number of structural changes is therefore more likely to be incorrect.

> - for diffing, it feels more acceptable to restrict the matching to be monotonous on the leaves since it's difficult to visually represent moves if you can detect them. For merging, supporting moves is more interesting as it lets you replay changes on the moved element,

We use a pipeline based approach and visualizing the changes is the last step. For some types of changes we don't have a way to visualize them yet (e.g. moves within the same line) and ignore that part of the mapping. We are still trying to get the mapping right though :)

We upstreamed a few bug fixes for tree-sitter itself. The grammars were a bit more complicated because we were just using them as a starting point. We patched tree-sitter, added our own annotations to the grammars and restructured them to help our matching algorithm achieve better results and improve performance. In the end there was not much to upstream any more.

Using a well tested parsing library, such as Roslyn for C#, and writing some code to integrate it into our existing system aligned more with our goals than tinkering with grammars. Context-sensitive keywords in particular were a constant source of annoyance. The grammar looks correct, but it will fail to parse because of the way the lexer works. You don't want your tool to abort just because someone named their parameter "async".

abathur 5 days ago | root | parent | prev | next |

> We are currently in the process of moving away from tree-sitter and instead using the parsers provided by the languages themselves where possible.

I imagine this means you're trying to abstract over those parsers somehow? How well is that going, and have you written about your approach?

(I wrote `resholve` to identify and rewrite references to external dependencies in bash/posixy Shell scripts to absolute paths. This is helpful in the Nix ecosystem to confirm the dependencies are known, specified, present, don't shift when run from a service with a different PATH, etc.

It builds on the mostly-bash-compatible OSH parser from the oilshell/oils-for-unix project for the same reasons you're citing.

It would be ~nice to eventually generalize out something that can handle scripts for other shell languages like fish, zsh, nushell, elvish, the ysh part of the oils-for-unix project, etc., but I suspect that'll be a diminishing-return sort of slog and haven't had any lightbulb-moments to make it feel tractable yet.

We also have some ~related needs here around identifying hardcoded or user-controlled exec...)

DarkPlayer 5 days ago | root | parent |

Our parsers simply return the concrete syntax trees in a JSON format. We do not unify all the different syntax constructs into a common AST if that is what you are looking for. The languages and file formats we support are too diverse for that.

The language specific logic does not end with the parsers though. The core of SemanticDiff also contains language specific rules that are picked up by the matching and visualization steps. For example, the HTML module might add a rule that the order of attributes within a tag is irrelevant. So it all comes down to writing a generic rule system that makes it easy to add new languages.

Sesse__ 5 days ago | root | parent | prev | next |

An important point here is that for certain languages, using the original grammar is pretty much impossible. In particular, for C, you want to do diffing and merging on the un-preprocessed source, but the language's grammar very much assumes the source has gone through the preprocessor.

Of course, the existence of the preprocessor means there are situations where it's completely impossible to know what the correct parse is; it will necessarily be heuristic in some cases.

yencabulator 3 days ago | root | parent |

You can ask Clang for an AST that contains macro definitions and invocations as nodes.

https://docs.rs/clang/latest/clang/struct.Parser.html#method...

https://docs.rs/clang/latest/clang/enum.EntityKind.html#vari...

https://docs.rs/clang/latest/clang/enum.EntityKind.html#vari...

Sesse__ 3 days ago | root | parent |

Using clangd for this very much assumes that you have all include files and build flags available at the point of merge resolution, which is often pretty much impossible.

yencabulator 3 days ago | root | parent |

Agreed, it's not very robust the way tree-sitter is. I just thought that libclang trick was very useful for extracting semantic information from C source.

herrington_d 4 days ago | root | parent | prev | next |

Hi! ast-grep[1] author here. It is a tree-sitter based syntax tool to search tool.

I wonder how you transition from tree-sitter to other builtin parsers? Tree-sitter gave a unified interface to all languages. Using language native parsers will require significant work for various FFI if I am not wrong.

[1]: https://ast-grep.github.io/

alexpovel 4 days ago | root | parent |

Not the OP, but you raise good points. Performance might also be a concern, thinking of languages like Python and its ast package (not sure that’s accessible without going through the interpreter).

For a tool I’m writing, the tree-sitter query language is a core piece of the puzzle as well. Once you only have JSON of the concrete syntax trees, you’re back to implementing a query language yourself. Not that OP needs it, but ast-grep might?

OJFord 5 days ago | root | parent | prev | next |

> best effort approach to parsing. This is perfectly fine for syntax highlighting, since the worst that can happen is that a few characters are highlighted incorrectly. However, when diffing or modifying code you really want the code to be parsed according to the upstream grammar, not something that mostly resembles it.

But surely you need to support code that doesn't parse correctly by the actual language's grammar anyway? 'Merge branch fix-syntax-error'

wetneb 5 days ago | root | parent |

In Mergiraf, as soon as there is a parsing error in any of the revisions, it falls back on line-based merging, even though tree-sitter is generally good at isolating the error. It felt like the safest thing to do (maybe we detected the language wrong), but I'm definitely open to reconsidering…

Gibbon1 4 days ago | root | parent | prev | next |

Small brained primate comment.

I've wondered if you could add annotation keywords to languages to convert them into something that could be parsed reliably with a tree sitter grammar.

I say this as someone that feels like you really want diffs that say, changed 'struct x name from y to z' instead of here's a huge list of files with ten changes each.

drawnwren 5 days ago | root | parent | prev | next |

This may or may not be on your radar, but crypto is desperate for a product like this. Smart contracts are often forks or rewrites (obfuscated or otherwise) of others and an easy interface for end users to be able to see changes between two forks would probably provide a lot of value.

Sparkyte 4 days ago | root | parent | prev |

Good example of when adding abstraction is more problematic than the processes themselves which is like an extra minute or two in flow.

Game_Ender 5 days ago | prev | next |

The tool has an excellent architecture section [0] that goes into how it works under the hood. It stands out to me that a complex tool has an overview to this depth that allows you to grasp conceptually how it works.

0 - https://mergiraf.org/architecture.html

__MatrixMan__ 5 days ago | root | parent |

That is nicely done, often hard to find, and usually it's what I'm looking for when deciding whether to use a piece of software: Show me the complexity you've encapsulated so that I can be the judge of whether the juice is worth the squeeze.

Armed with that, I can tolerate some rough edges. Without it, I'll get stuck in weird ways that your docs can't anticipate.

chrismorgan 5 days ago | prev | next |

Going through the sorts of conflicts it solves, and limitations in that, I find it claiming that in some insertions, order doesn’t matter <https://mergiraf.org/conflicts.html#neighbouring-insertions-...>.

I really don’t like that. At the language level, order may not matter, but quite frequently in such cases the order does matter, insofar as almost every human would put the two things in a particular order; or where there is a particular convention active. If you automatically merge the two sides in a different order from that, doing it automatically has become harmful.

My clearest example: take Base `struct Foo; struct Bar;`, then between these two items, Left inserts `impl Foo { }`, Right inserts `struct Baz;`. To the computer, the difference doesn’t matter, but merging it as `struct Foo; struct Baz; impl Foo { } struct Bar;` is obviously bad to a human. This is the problem: it’s handling language syntax semantics, but can’t be aware of logical semantics. (Hope you can grasp what I’m trying to convey, not sure of the best words.) Left was not inserting something between Foo and Bar, it was attaching something to the end of Foo. Whereas Right was probably inserting something between Foo and Bar—but maybe even it was inserting something before Bar. You perceive that these are all different things, logically.

Another example where this will quickly go wrong: in CSS rulesets, some will sort the declarations by property name lexicographically, some by property name length (seriously, it’s frequently so pretty), some will group by different types of property… you can’t know.

soraminazuki 5 days ago | root | parent | next |

Not only that, the order of fields in a Java class does matter despite what that link claims. It's common to use Lombok to automatically generate constructors, and "the order of the parameters match the order in which the fields appear in your class."

https://projectlombok.org/features/constructor

The first two kinds of conflicts that Mergiraf handles looks somewhat dangerous to me when handled by a computer.

https://mergiraf.org/conflicts.html

wetneb 5 days ago | root | parent | next |

Lombok is an interesting example, but yes, just with reflection you can already get order-dependent behaviors as the docs note. I've been thinking about giving users more control over this commutativity, but it's not clear to me what it should look like. A strict mode where commutativity is disabled entirely? The ability to disable certain commutative parents?

andrewaylett 5 days ago | root | parent | prev |

Code that uses Lombok features which change classes (rather than subclassing them) might have a high degree of similarity to Java, but it's not Java.

soulofmischief 5 days ago | root | parent | prev | next |

I sort my CSS by property type (display, size, position, etc). Takes a while to get used to it but it definitely speeds up my ability to do CSS surgery.

wonger_ 5 days ago | root | parent |

Similarly, I've been wanting to make an autoformatter that reorders CSS properties into these categories: https://9elements.com/css-rule-order/ (box model, positioning, typography, etc)

I think it's the most useful CSS organization method I've found yet.

p4bl0 5 days ago | root | parent | prev | next |

This is what I've always done naturally for the 20+ years I've been writing CSS. The only difference is that I put animation at the end, probably because it came much later than the rest.

soulofmischief 4 days ago | root | parent | prev |

Yeah, it really helps out, and I just head each section with a comment for fast grepping and grokking. My system combines a lot of things into the Display category which could be split out but I think I've struck a good enough balance.

bjackman 5 days ago | root | parent | prev | next |

I am very excited about this tool despite agreeing with what you wrote here.

The reason for that is that most of the time when I'm resolving huge numbers merge conflicts... I don't give a shit about details like field order. I just want to get some code that's functionally correct at p<0.05 so I can figure out what performance characteristics my old feature branch would have if I resurrected it. Or I want to kick off the slow integration tests ASAP. 9/10 times it's that kind of thing.

The 1/10 times where I'm like "OK now I actually wanna merge this code, I have to look over the resolutions, I will upload them to Gerrit/GitHub and do a self-review" I am more than happy to spend 20 minutes correcting order etc. Or I'll happily just switch this tool off and do a totally manual merge.

So yeah I think it just comes down to usecase.

chrismorgan 5 days ago | root | parent | prev | next |

I want to add another problem here. <https://mergiraf.org/adding-a-language.html#add-commutative-...>:

> To let Mergiraf reorder using statements to fix conflicts, we actually need to specify that they can be reordered with any of their siblings (any other child of their parent in the syntax tree).

That’s too coarse-grained. No idea about C♯, but languages could impose a rule that imports must come before anything else—long ago Rust had such a rule, for example. So it might be that within your compilation_unit node, only its using_directive children are commutative, and only among themselves.

Otherwise (lapsing into Rust syntax for convenience), with Base `use A; struct X…`, Left `use A; use B; struct X…` and Right `use A; struct Y; struct X…`, you could end up with the invalid `use A; struct Y; use B; struct X…`.

IshKebab 5 days ago | root | parent | prev | next |

Yes maybe, but these issues are true for Git's native merge algorithms too. It isn't perfect either.

As soon as you do any merge you're accepting that there might be edits you don't agree with.

andybak 5 days ago | root | parent | prev | next |

Could some of this be mitigated by running a prettifier post-merge?

wetneb 5 days ago | root | parent |

It's definitely something I would recommend in general, but I'm not sure if it would solve this particular problem (reordering blocks is perhaps a bit bold for a prettifier).

andybak 5 days ago | root | parent |

Maybe prettifier was the wrong word. I've definitely used code formatting tools that offer sorting of certain syntax elements as a feature. (Python imports in PyCharm springs to mind)

CGamesPlay 5 days ago | root | parent | prev |

But surely Mergiraf has some opinion about the order when it doesn’t matter, right? Like structs before impls, in your example.

wetneb 5 days ago | root | parent |

For now, you let it reorder every child within a given node type, which felt expressive enough to me in most cases, but I agree it would be good to refine that: https://codeberg.org/mergiraf/mergiraf/issues/6

zeotroph 5 days ago | root | parent |

Looking at the nice demo, I think just defaulting to asking for confirmation if there is ambiguity, instead of dazzling the user with `mergiraf solve` magic would help; there is already a `merigraf review`. Then, a confirm prompt, an option to undo the resolution completely, or just do it on a file-by-file basis (with help what command to run next).

nathell 5 days ago | prev | next |

‘Why the giraffe? Two reasons. First, it can see farther due to its height; second, it has one of the biggest hearts of all land mammals. Besides, its ossicones make you believe it listens to you when you look at it.’ – My NVC teacher

Kudos for the nonviolence. :)

aeonik 5 days ago | root | parent | next |

Fyi, giraffes are wild animals, and can be very violent and territorial.

mnsc 4 days ago | root | parent |

I'm very literal minded and many metaphors irk me because they require a unspoken shared agreement of only considering the positive aspects that match and ignore the inconvenient ones. Like all sports metaphors used in work related activities. But still, don't skip nvc just because you can't accept a violent animal as a symbol for non violent communication. It has to much value for us literal minded people.

aeonik 4 days ago | root | parent |

I'm all for minimizing violence and harm, but violence is a necessary part of life.

I just watched a surgeon slice open a woman and save her life and the baby. Blood was everywhere, it was pretty violent. Nothing wrong with it.

Violence != Malice

Mergiraf looks pretty awesome though.

mnsc 2 days ago | root | parent | next |

I agree. Violence is everywhere and specifically in the animal kingdom it is weird to apply a moral judgement on violent animals. Eg. the wolf that in nvc symbolizes violent language does nothing wrong when it gathers the food it needs to live. There is no malice however "ruthless" it looks from the outside. And the giraffe also does nothing wrong when it protects it's grounds by kicking a hyena's head in.

But we humans that use these animals as metaphors when trying to improve our communication skills can apply a moral judgement and say that this way of communicating is better than that way. But we literal minded often get derailed when the metaphors are not 100% solid so I often think that metaphors are bad, or at least risky. (but I like these specific metaphors in nvc somehow)

computerfriend 4 days ago | root | parent | prev |

I agree with your first and last point, but surgery != violence.

aeonik 4 days ago | root | parent |

I disagree, but we are quickly getting deep into semantics.

Surgery is not a harmless procedure. But the surgeon must decide that the patient is more likely to benefit overall from it.

lucasoshiro 5 days ago | prev | next |

Happy to see something being developed for merge drivers, they are a underrated Git feature that could save a lot since the standard three-way merge of file contents is not aware of the language and can create some problems. For example, if you have this valid Python code:

x = input()

if x == 'x': print('foo')

    print('bar')
If you delete the first print in a branch, delete the other print in another branch, then merge the two branches, you'll have this:

x = input()

if x == 'x':

Both branches delete a portion of the code inside the if block, leaving it only with a whitespace. In Python it is not a valid code, as they empty scopes need to be declared with pass.

I installed Mergiraf to see if it can solve this situation, but sadly, it doesn't support Python...

wetneb 5 days ago | root | parent | prev |

I tried your example but git does create a conflict in my case - but maybe I misunderstood the scenario. Python support can likely be done (I would be thrilled if someone made a PR for it), but I don't know if there is a lot of potential for solving conflicts there: imports can have side effects, function arguments are complicated with the mixture of positional and keyword arguments, decorators are effectful… it seems to me that there is a lot of sensitivity to order in many places.

erik_seaberg 5 days ago | prev | next |

Syntax-aware tools always have issues when a team extends the base language to fit their problem. Rust has macros. People started using "go generate" for stuff like early generics. Does Mergiraf take EBNF or plugins or does a team fork it to explain their syntax?

wetneb 5 days ago | root | parent |

Yeah at the moment it just supports whatever the tree-sitter parser accepts, period. A bring-your-own-grammar version could be interesting, I don't see why it couldn't work. Do you have any Rust crates to recommend, to do parsing according to a grammar supplied by the user at run time? It's likely to be slower, but maybe not prohibitively so…

Another approach would be for the tool to accept doing structured merging even if there are error nodes in the parsed tree. If those error span the parts of the file where the extended language is used, then the tool could still help with merging the other parts, treating the errors as atomic blocks. I'd be a bit reluctant to do that, because there could be errors for all sorts of other reasons.

papashell 5 days ago | root | parent |

Since tree sitter parsers output a c library, you could dynamically load it.

The rust bindings themselves are a thin ffi wrapper.

If you wanted to make it a little smoother than needing to compile the tree sitter syntax you could compile/bundle grammars up with wasm so its sandboxed and cross platform

Edit: found this vscode extension that dynamically loads syntaxes compiled to wasm. You should be able to do the same thing in rust: https://github.com/selfint/vscode-tree-sitter

leonheld 5 days ago | prev | next |

I'll certainly give it a try. Another tool I've been using (with varied degree of success) to enhance my git life is https://github.com/tummychow/git-absorb. If both of these worked flawlessly or maybe even officially incorporated in git, I'd be very happy.

ksynwa 5 days ago | root | parent | next |

This sounds like what jujutsu's workflow is like by default

leonheld 5 days ago | root | parent | prev |

I've heard of jujutsu, but I'm kinda over learning new tooling, specially experimental one. If it's not a drop-in replacement that makes my life better (like these easy "git plugins"), I'm basically not using.

stouset 17 hours ago | root | parent | next |

It is a drop-in replacement for git and completely compatible. Your coworkers do not need to know you're using a different tool. And you can continue to use git commands directly if you want.

fallingsquirrel 5 days ago | root | parent | prev |

fwiw you can mix git and jj commands on the same repo and everything will work fine. If you want to stick with 99% git commands, and use jj only as a replacement for git-absorb, you can. For this particular use case, jj will handle merges/tags descended from the fixed commit gracefully, and I don't think git-absorb handles that.

IshKebab 5 days ago | prev | next |

This sounds great. To be honest though none of the merge tools really give me enough information to resolve all conflicts easily.

The best I've got to is zdiff3 in VSCode (not using their fancy merge view which I don't understand at all). But it's missing:

1. Blame for the merge base.

2. Detection of the commit that introduced the first conflict.

3. Most annoyingly, no way to show diffs between the "current" and "incoming". IIRC it has buttons to compare both of those to the merge base, but not to each other. That often leaves me visually scanning the text to manually find differences like a neanderthal. Sometimes it's annoying enough that I copy & paste current/incoming into files and then diff those but that's a right pain.

jappgar 5 days ago | prev | next |

This seems like a really cool idea that would help with a scenario I encounter a lot with conflicts related to auto-formatting. Sometimes a small change can lead to a lot of whitespace changes below (in functional chains in js, for example).

Can this also detect some scenarios where semantic conflicts (but not line conflicts) arise, usually due to moved code?

I don't know the exact circumstances when this happens, but occasionally you can have e.g a function defined twice after two branches both move the same function elsewhere.

manx 4 days ago | prev | next |

Great to see more work in automatic git conflict resolution! I'll definitely give this a try. My own attempt at such a tool involved character based diffing and patching. It is able to solve most trivial conflicts that git cannot: https://fdietze.github.io/blend/

I never found the time to make a cli out of this.

_flux 5 days ago | prev | next |

Python support would certainly be seem useful for this, in particular as its intentation-based AST should play nicely with this.

fuzzy2 5 days ago | prev | next |

I'm eager to try this. Seems like it could revive the genre after Semantic Merge died.

ctenb 5 days ago | prev | next |

Would it be possible to make this work with a treesitter grammar?