Hacker News Reader

Comment by krupan | Hacker News Reader

This distinction between commits and patches (I've been following git, hg, and darcs for over a decade) is one I've never quite understood. A patch says, take this original line of code found here and change it into this new line of code. A commit is just a patch that records when in the history you can be sure to find that original line of code. If you take an arbitrary patch and apply it to an arbitrary set of code you might not even be able to find that original line of code. How do darcs and/or pijul solve that problem? Git and mercurial have tools like rebase and cherry pick that allow you to rearrange commits and they can even use three way merge algorithms (because of the DAG) to help recompute the patches for when that original line of code isn't quite what the patch specifies anymore. How are darcs and/or pijul different in that regard?

View on HN

A commit is not a patch. A commit is just often represented as a patch (i.e. a diff), but in general neither git nor hg even save a commit as a patch, except as a minor, optional, and opaque optimisation. What they really save is the entire state of your repo at a particular time, with the hash(es) of the state of the repo just before this one. In the case of git, it saves a tree of hashes that refer to all of the blobs (files) at the current commit. In the case of Mercurial, it saves a manifest of hashes that point to files represented in revlogs. Whenever both git and hg show you a commit as a diff, this involves a computation. They are not merely showing you diffs that they have pre-computed and stored.

Bitkeeper does have a weave data structure that more closely resembles patches. It's an encoded set of instructions for transforming one file from one state into another:

https://www.bitkeeper.org/src-notes/SCCSWEAVE.html

This data structure has a big advantage when computing annotations (blames): it's much faster than Mercurial's revlog (which in turn is faster than git's blob-tree-ref structure).

All that sounds like differences in the intr internal model. From everything I have understood it wor would be possible to reimplement git to store only patches, their position in the commit tree and the commit hash, and have it behave exactly like the git reference implementation.

Is the difference between patches and git commits in a DAG really only a difference in internal representations or is there a user-facing difference?

Speed is about the only user-facing difference. But the big user-facing difference is that commits are glued to their parents. They really are glued; the merges and potential conflicts involved with rebasing and cherry-picking are a consequence of trying to undo this glue.

Darcs' and pijuls' patches aren't glued, they only either commute or do not, and the conflict resolution mechanisms for non-commutative patches are different.

What does commute mean in this context? I'm getting the impression that it means that the original line of code that the patch references and is going to change is where the patch expects it to be.

It's probably best to get this from the source:

https://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theo...

Yes. The DAG in a context in darcs or pijul (so, I have a checkout; how did those files come into existence) is a consequence of the set of patches; the order is computed, not intrinsically part of every commit. This has many UX consequences; for example, when you darcs pull, you automatically cherry-pick patches in any order (as long as you have the dependencies) -- when you git pull, you pull in a commit in a position in a DAG, and automatically merge its entire history.

If you've heard someone say "never git pull, always git fetch and then either merge or rebase as appropriate", then they've noticed the difference between the two.

It would be certainly be possible to reimplement git using only patches, showing that Pijul cannot be worse than git.

However, it would not be possible to implement a patch-based system (Pijul/darcs) based on git.

- One example is cherry-picking: in git, when you are on some branch A, and cherry-pick from another branch B, after the cherry-picking is done, if you try to cherry-pick from B again, you'll get conflicts. In Pijul and darcs, that comes for free.

- Another example is merge: merge between commits is provably wrong (https://tahoe-lafs.org/~zooko/badmerge/simple.html). With patches, this cannot happen.

Thanks for that link, that finally helped me understand the real benefit of the patch model, this quote in particular:

> The difference between what svn does and what darcs does here is, contrary to popular belief, not that darcs makes a better or luckier guess as to where the line from c1 should go, but that darcs uses information that svn does not use -- namely the information contained in b1 -- to learn that the location has moved and precisely to where it has moved.

Darcs/Pijul understand which lines a patch is interested in, and if those lines get moved around in another branch, the patch "follows" them to the right place, rather than just finding/applying the shortest possible diff.

A commit stores information about the state of the whole repository (in hashes). A patch is stateless, just describing what operations you do on the repository.

One confusing thing for git users is, git represents a number of commits (but not all types of commits) as patches.

Two differences:

- Cherry picking is possible, but when you cherry pick twice from the same branch, you get conflicts with commits, because cherry-picking change their identity. With patches, this works just as expected.

- Merging can be made associative with patches, not with commits. Concretely, in git, if Alice and Bob add lines to a file, even when there are no conflicts, Alice's new lines can be merged in the middle of parts added by Bob, even though she's never seen these parts. Even worse, there is no way to tell when this happens to you (git doesn't say). "Associativity" is the mathematical property that this never happens.

> Git and mercurial have tools like rebase and cherry pick

darcs had incredible cherry picking about ten years ago.

Instead of saying "get this commit" and solve merge conflicts manually, like git does, darcs would get one patch and every other that was necessary for it.

It effectively made cherry picking work as in "I want this feature from that branch" instead of "I want some code from that branch".

It was glorious, other than the little detail of occasionally exponential merge times...

darcs and pijul have an internal model that tells it where patches can go; it does not suggest patches can go pretty much everywhere (in fact; at any given time it probably only has exactly one idea of which order the patches go in). Once those patches have dependencies, it enforces their order; but e.g. groups of dependent patches can still be transplanted around.

The Darcs wiki has some cool graphics around cherry-picking merges that might answer your question better than a paragraph of prose can: http://darcs.net/Using/Model#merging-with-cherry-picking

Reply on news.ycombinator.com