[HN Gopher] Mergiraf: a syntax-aware merge driver for Git
___________________________________________________________________
Mergiraf: a syntax-aware merge driver for Git
Author : p4bl0
Score : 301 points
Date : 2024-11-09 11:06 UTC (11 hours ago)
(HTM) web link (mergiraf.org)
(TXT) w3m dump (mergiraf.org)
| chrismorgan wrote:
| 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.
| andybak wrote:
| Could some of this be mitigated by running a prettifier post-
| merge?
| wetneb wrote:
| 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).
| CGamesPlay wrote:
| But surely Mergiraf has some opinion about the order when it
| doesn't matter, right? Like structs before impls, in your
| example.
| wetneb wrote:
| 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 wrote:
| 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).
| soulofmischief wrote:
| 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_ wrote:
| 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.
| fallingsquirrel wrote:
| You might be interested in
| https://github.com/hudochenkov/stylelint-order
| p4bl0 wrote:
| 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.
| wetneb wrote:
| Yes, that's definitely something that could be refined, for
| instance by specifying that only children of specific types can
| be reordered together:
| https://codeberg.org/mergiraf/mergiraf/issues/6
| chrismorgan wrote:
| 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...`.
| tokinonagare wrote:
| > No idea about C#
|
| C#'s _using_ aren 't imports, and order indeed doesn't
| matter.
| soraminazuki wrote:
| 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 wrote:
| 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 wrote:
| 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.
| IshKebab wrote:
| 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.
| bjackman wrote:
| 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.
| nathell wrote:
| '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 wrote:
| Fyi, giraffes are wild animals, and can be very violent and
| territorial.
| postepowanieadm wrote:
| Boa constrictor could be a less friendly mascot.
| arunix wrote:
| There was such a project long time ago.
|
| https://boa-constructor.sourceforge.net/
| lucasoshiro wrote:
| 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 wrote:
| 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.
| masklinn wrote:
| FWIW your examples are very unclear as they use text
| formatting, you need to indent lines by 4 spaces (with an empty
| line before and after) for a code block e.g.
|
| if a == b: print("x")
|
| versus if a == b: print("x")
| chrismorgan wrote:
| The minimum required is actually only two spaces.
| pknopf wrote:
| Can LLMs help here?
| wetneb wrote:
| There are attempts to do that, such as
| https://arxiv.org/abs/2111.11904 or
| https://arxiv.org/abs/2109.00084. I couldn't find any open
| source implementation though. I'm personally not so keen to use
| LLMs for merging: I want it to be quick and predictable.
| leonheld wrote:
| 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 wrote:
| This sounds like what jujutsu's workflow is like by default
| leonheld wrote:
| 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.
| fallingsquirrel wrote:
| 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.
| dochtman wrote:
| git absorb is great, use it all the time.
| jappgar wrote:
| 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.
| wetneb wrote:
| Yes, see this example:
| https://mergiraf.org/conflicts.html#line-based-merges
| donatj wrote:
| Neat idea for sure. Language support is pretty limited right now,
| hopefully there's support for more in the works.
| wetneb wrote:
| Out of curiosity, which languages would you be interested in?
| wlll wrote:
| For me, Ruby.
| donatj wrote:
| Off the top of my head, PHP, TypeScript and INI. JavaScript
| might cover TypeScript, I don't know.
| Game_Ender wrote:
| 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__ wrote:
| 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.
| _flux wrote:
| Python support would certainly be seem useful for this, in
| particular as its intentation-based AST should play nicely with
| this.
| fuzzy2 wrote:
| I'm eager to try this. Seems like it could revive the genre after
| Semantic Merge died.
| ctenb wrote:
| Would it be possible to make this work with a treesitter grammar?
| wetneb wrote:
| It's based on tree-sitter indeed: https://mergiraf.org/adding-
| a-language.html
| froh wrote:
| what do you mean?
|
| its treesitter based already:
|
| https://mergiraf.org/architecture.html
| ctenb wrote:
| Hm, I failed to notice that, since it is not mentioned in
| their introduction, and the list of supported languages is
| fairly small :)
| IshKebab wrote:
| 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.
| secondcoming wrote:
| Have you tried p4merge? It's usually one of the first tools I
| install.
| DrBenCarson wrote:
| How is this better than Difftastic?
| https://github.com/Wilfred/difftastic
| jFriedensreich wrote:
| difftastic does only diffing not merging.
| DarkPlayer wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > - 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".
| drawnwren wrote:
| 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.
| Sesse__ wrote:
| 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.
| abathur wrote:
| > 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 wrote:
| 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.
| OJFord wrote:
| > 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 wrote:
| 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...
| jay-anderson wrote:
| Nice to see lilypond in the example.
| cool-RR wrote:
| I'm flummoxed at the lack of Python support.
| 77pt77 wrote:
| No typescript either, but it does support JS.
| erik_seaberg wrote:
| 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 wrote:
| 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.
___________________________________________________________________
(page generated 2024-11-09 23:00 UTC)