9 ms·

The state of merging technology

70 points by bumbledraven 3y ago

toomim 3y ago
> The next easiest win would be to use the weave algorithm for non-rebase merges. The weave is essentially a CRDT, but invented in 1977 by SCCS. Anyone interested in weaves should consider modern CRDT tech. I've been keeping some notes on the correspondence within the Braid.org group (e.g. https://braid.org/meeting-60/sccs-is-a-time-collapse https://braid.org/meeting-60/sccs-is-a-time-collapse) and encourage anyone interested to reach out!
kragen 3y ago
some relevant context is that bram and his brother ross developed an early decentralized version control system named 'codeville', more or less contemporary with git and mercurial; they put a lot of work into figuring out how merging should handle different hairy scenarios bram was deeply disappointed that the systems that got widely adopted, like git, did a terrible job with these hairy scenarios, since he knew that it was possible to do much better
- ajb 3y ago
  Oh yeah, there was a bit of a Cambrian explosion of version control systems around then, due to everyone getting fed up with CVS as well as the bitkeeper debacle. Codeville, TLA, monotone, vesta... I quite liked the idea of vesta, which included a build system and with hindsight looks a lot like nix/guix
  - kragen 3y ago
    yeah, bram and len featured a lot of them in codecon. but i don't agree with your explanation of why it happened svn was the result of everyone getting fed up with cvs; basically it does the same thing as cvs, but does it in a less janky way, and with atomic commits. but it still suffers from cvs's design weaknesses vesta was a digital research (decwrl?) project from the previous millennium; peter deutsch told me about it at the time, but it was still proprietary, and it took them a while to be able to open-source it. it was basically a clone of dsee, just like clearcase, though perhaps better done. it wasn't motivated by dissatisfaction with cvs and in fact couldn't do things cvs could do i think the main thing that kicked off the cambrian explosion wasn't 'everyone getting fed up with cvs' but rather tom lord (rip) writing arch (tla, later baz and bzr) which demonstrated to everyone that it was possible to do enormously better than cvs/svn, with features like atomic commits, forking your own branches without permission from the core team, decentralization, and serving from regular ftp or web servers (no special server software) these design features were ideologically driven on tom's part; he wanted to give ordinary users version-control tools that were just as powerful as the ones used by core teams on projects like freebsd and apache, motivated by the same egalitarianism that had led him to become an employee of the fsf and i think graydon hoare's monotone was the thing that most inspired the other follow-on systems, like git, mercurial, codeville, fossil, maybe darcs, and maybe even baz and bzr maybe kernel hackers getting experience with bitkeeper in 02000 to 02005 added motivation for moving to better-than-cvs-and-svn models too tho shlomi fish's site from the time in question has a lot of material on what was happening, including even lesser known version tracking systems like aegis: https://better-scm.shlomifish.org/aegis/ https://better-scm.shlomifish.org/aegis/
    - ajb 3y ago
      Fair enough, your history is probably more accurate. I didn't know Tom Lord had died. And not very old either darn it :-(
      - kragen 3y ago
        yeah, it's a huge loss
        sitkack 3y ago
        Tom Lord has died (berkeleydailyplanet.com) https://news.ycombinator.com/item?id=32155067 https://news.ycombinator.com/item?id=32155067
    - sockaddr 3y ago
      > 02000 to 02005 I think this is the first time I've seen this five-digit notation used in the wild after reading about The Long Now Foundation using it years ago.
      - ComputerGuru 3y ago
        It’s how you know a kragen post on HN.
    - hyperthesis 3y ago
      Historically, bitkeeper directly led to git. But you're saying arch, then monotone, came before bitkeeper? What innovations did each provide? (git's innovation was content-based addressing, so the data structure does the heavy lifting. bitkeeper used sha1 hashes for decentralization - was that its main contribution?) Probably the internet enabled the decentralized version control Cambrian explosion (or, at least, a Cambrian explosion) BTW: funfact re "merging": bitkeeper had first-class renaming, which git lost. A process of subtraction as well as addition.
      - kragen 3y ago
kuahyeow 3y ago
Didn't Git have a new default merge strategy, `ort` https://github.com/git/git/blob/master/Documentation/RelNotes/2.34.0.txt https://github.com/git/git/blob/master/Documentation/RelNote... ?
- juped 3y ago
  histogram is a diff algorithm
  - skywal_l 3y ago
    From the article: > switch the default 3 way merge algorithm to histogram
    - toomim 3y ago
      Yeah, that was poorly written and confused me too. It should say "switch the default diff algorithm to histogram." The diff algorithm is used within the recursive 3-way merge algorithm.
wscott 3y ago
The piece of BitKeeper I wish people would steal is the smerge gca conflict format. See https://www.bitkeeper.org/man/smerge.html https://www.bitkeeper.org/man/smerge.html Example: <<<<<<< local slib.c 1.642.1.6 vs 1.645 sc = sccs_init(file, INIT_NOCKSUM|INIT_SAVEPROJ, s->proj); - assert(sc->tree); - sccs_sdelta(sc, sc->tree, file); + assert(HASGRAPH(sc)); + sccs_sdelta(sc, sccs_ino(sc), file); <<<<<<< remote slib.c 1.642.1.6 vs 1.642.2.1 - sc = sccs_init(file, INIT_NOCKSUM|INIT_SAVEPROJ, s->proj); + sc = sccs_init(file, INIT_NOCKSUM|INIT_SAVEPROJ, p); assert(sc->tree); sccs_sdelta(sc, sc->tree, file); >>>>>>> Here we have a code conflict and rather than showing you what the file looks like on the two sides it shows you what was changed on both sides relative to the GCA. So we get two unified diffs. The local side made this edit, while on the remote side we had that edit. Then it is obvious how to resolve the conflict without losing a change. This works for the cris-cross case because that GCA is really a set of common revisions merged together.
- gavinhoward 3y ago
 I'm making a VCS based on the weave. Your wish will be answered; I wanted a conflict-aware format, and I will definitely plunder the smerge format.
- teraflop 3y ago
 Git has something similar if you turn on the "diff3" conflict style, and I can't for the life of me understand why it's not on by default, because there are many situations where you just don't have enough information to properly resolve a merge without it.
 - pabs3 3y ago
 BTW zdiff3 is a newer version of that style that is slightly better than diff3.
 - juped 3y ago
jez 3y ago
The biggest day-to-day merge conflict annoyance I have is situations like this. As far as I know, there’s no solution: commit aaaaaaaa diff --git a/README.md b/README.md --- a/README.md +++ b/README.md @@ -1,4 +1,4 @@ - + <img width="200" src="logo.svg"> commit bbbbbbbb diff --git a/README.md b/README.md --- a/README.md +++ b/README.md @@ -1,5 +1,5 @@ - <img width="200" src="logo.svg"> + <img width="345" src="logo.svg"> # Project Commit aaaaaaaa changes some text on line 1. Commit bbbbbbbb changes some unrelated text on line 2. I don’t want to have to manually resolve this—just merge the lines. If there’s a semantic conflict I’ll let the tests sort it out. When I’ve looked in the past there wasn’t a merge strategy that fixes this.
- wscott 3y ago
 BitKeeper was able to merge that successfully by looking at the revision history and seeing that the changes involved just those lines. If one of them added a line between the two being changed then it would still be a conflict. I spent a year looking at interesting merges (and commits fixing bad merges) in the Linux kernel and making a catalog of interesting cases before writing 'smerge' for BitKeeper. It is impossible to make a perfect merge tool, but we can do a lot better than diff3.

70 points by bumbledraven 3y ago

> The next easiest win would be to use the weave algorithm for non-rebase merges. The weave is essentially a CRDT, but invented in 1977 by SCCS. Anyone interested in weaves should consider modern CRDT tech. I've been keeping some notes on the correspondence within the Braid.org group (e.g. https://braid.org/meeting-60/sccs-is-a-time-collapse https://braid.org/meeting-60/sccs-is-a-time-collapse) and encourage anyone interested to reach out!

kragen 3y ago

some relevant context is that bram and his brother ross developed an early decentralized version control system named 'codeville', more or less contemporary with git and mercurial; they put a lot of work into figuring out how merging should handle different hairy scenarios bram was deeply disappointed that the systems that got widely adopted, like git, did a terrible job with these hairy scenarios, since he knew that it was possible to do much better

ajb 3y ago
Oh yeah, there was a bit of a Cambrian explosion of version control systems around then, due to everyone getting fed up with CVS as well as the bitkeeper debacle. Codeville, TLA, monotone, vesta... I quite liked the idea of vesta, which included a build system and with hindsight looks a lot like nix/guix
- kragen 3y ago
  yeah, bram and len featured a lot of them in codecon. but i don't agree with your explanation of why it happened svn was the result of everyone getting fed up with cvs; basically it does the same thing as cvs, but does it in a less janky way, and with atomic commits. but it still suffers from cvs's design weaknesses vesta was a digital research (decwrl?) project from the previous millennium; peter deutsch told me about it at the time, but it was still proprietary, and it took them a while to be able to open-source it. it was basically a clone of dsee, just like clearcase, though perhaps better done. it wasn't motivated by dissatisfaction with cvs and in fact couldn't do things cvs could do i think the main thing that kicked off the cambrian explosion wasn't 'everyone getting fed up with cvs' but rather tom lord (rip) writing arch (tla, later baz and bzr) which demonstrated to everyone that it was possible to do enormously better than cvs/svn, with features like atomic commits, forking your own branches without permission from the core team, decentralization, and serving from regular ftp or web servers (no special server software) these design features were ideologically driven on tom's part; he wanted to give ordinary users version-control tools that were just as powerful as the ones used by core teams on projects like freebsd and apache, motivated by the same egalitarianism that had led him to become an employee of the fsf and i think graydon hoare's monotone was the thing that most inspired the other follow-on systems, like git, mercurial, codeville, fossil, maybe darcs, and maybe even baz and bzr maybe kernel hackers getting experience with bitkeeper in 02000 to 02005 added motivation for moving to better-than-cvs-and-svn models too tho shlomi fish's site from the time in question has a lot of material on what was happening, including even lesser known version tracking systems like aegis: https://better-scm.shlomifish.org/aegis/ https://better-scm.shlomifish.org/aegis/
  - ajb 3y ago
    Fair enough, your history is probably more accurate. I didn't know Tom Lord had died. And not very old either darn it :-(
    - kragen 3y ago
      yeah, it's a huge loss
      - sitkack 3y ago
        Tom Lord has died (berkeleydailyplanet.com) https://news.ycombinator.com/item?id=32155067 https://news.ycombinator.com/item?id=32155067
  - sockaddr 3y ago
    > 02000 to 02005 I think this is the first time I've seen this five-digit notation used in the wild after reading about The Long Now Foundation using it years ago.
    - ComputerGuru 3y ago
      It’s how you know a kragen post on HN.
  - hyperthesis 3y ago
    Historically, bitkeeper directly led to git. But you're saying arch, then monotone, came before bitkeeper? What innovations did each provide? (git's innovation was content-based addressing, so the data structure does the heavy lifting. bitkeeper used sha1 hashes for decentralization - was that its main contribution?) Probably the internet enabled the decentralized version control Cambrian explosion (or, at least, a Cambrian explosion) BTW: funfact re "merging": bitkeeper had first-class renaming, which git lost. A process of subtraction as well as addition.
    - kragen 3y ago

kuahyeow 3y ago

Didn't Git have a new default merge strategy, `ort` https://github.com/git/git/blob/master/Documentation/RelNotes/2.34.0.txt https://github.com/git/git/blob/master/Documentation/RelNote... ?

juped 3y ago
histogram is a diff algorithm
- skywal_l 3y ago
  From the article: > switch the default 3 way merge algorithm to histogram
  - toomim 3y ago
    Yeah, that was poorly written and confused me too. It should say "switch the default diff algorithm to histogram." The diff algorithm is used within the recursive 3-way merge algorithm.

wscott 3y ago

The piece of BitKeeper I wish people would steal is the smerge gca conflict format. See https://www.bitkeeper.org/man/smerge.html https://www.bitkeeper.org/man/smerge.html Example: <<<<<<< local slib.c 1.642.1.6 vs 1.645 sc = sccs_init(file, INIT_NOCKSUM|INIT_SAVEPROJ, s->proj); - assert(sc->tree); - sccs_sdelta(sc, sc->tree, file); + assert(HASGRAPH(sc)); + sccs_sdelta(sc, sccs_ino(sc), file); <<<<<<< remote slib.c 1.642.1.6 vs 1.642.2.1 - sc = sccs_init(file, INIT_NOCKSUM|INIT_SAVEPROJ, s->proj); + sc = sccs_init(file, INIT_NOCKSUM|INIT_SAVEPROJ, p); assert(sc->tree); sccs_sdelta(sc, sc->tree, file); >>>>>>> Here we have a code conflict and rather than showing you what the file looks like on the two sides it shows you what was changed on both sides relative to the GCA. So we get two unified diffs. The local side made this edit, while on the remote side we had that edit. Then it is obvious how to resolve the conflict without losing a change. This works for the cris-cross case because that GCA is really a set of common revisions merged together.

gavinhoward 3y ago
I'm making a VCS based on the weave. Your wish will be answered; I wanted a conflict-aware format, and I will definitely plunder the smerge format.
teraflop 3y ago
Git has something similar if you turn on the "diff3" conflict style, and I can't for the life of me understand why it's not on by default, because there are many situations where you just don't have enough information to properly resolve a merge without it.
- pabs3 3y ago
  BTW zdiff3 is a newer version of that style that is slightly better than diff3.
  - juped 3y ago

jez 3y ago

The biggest day-to-day merge conflict annoyance I have is situations like this. As far as I know, there’s no solution: commit aaaaaaaa diff --git a/README.md b/README.md --- a/README.md +++ b/README.md @@ -1,4 +1,4 @@ - + <img width="200" src="logo.svg"> commit bbbbbbbb diff --git a/README.md b/README.md --- a/README.md +++ b/README.md @@ -1,5 +1,5 @@ - <img width="200" src="logo.svg"> + <img width="345" src="logo.svg"> # Project Commit aaaaaaaa changes some text on line 1. Commit bbbbbbbb changes some unrelated text on line 2. I don’t want to have to manually resolve this—just merge the lines. If there’s a semantic conflict I’ll let the tests sort it out. When I’ve looked in the past there wasn’t a merge strategy that fixes this.

wscott 3y ago
BitKeeper was able to merge that successfully by looking at the revision history and seeing that the changes involved just those lines. If one of them added a line between the two being changed then it would still be a conflict. I spent a year looking at interesting merges (and commits fixing bad merges) in the Linux kernel and making a catalog of interesting cases before writing 'smerge' for BitKeeper. It is impossible to make a perfect merge tool, but we can do a lot better than diff3.