Re: Darcs and git: plan of action

Linus and gittish people,

I'm cc'ing you on this email, since Juliusz had some interesting ideas as to how darcs could interact with git, which then gave me an idea concerning which I'd like feedback from you. In particular, it would make life (that is, life interacting back and forth with git) easier if we were to embed darcs patches in their entirety in the git comment block. It's a bit of an ugly idea, but would greatly simplify the two-way interaction between git and darcs, since no information would be lost when a darcs patch was merged into git. See below for the discussion.

As I say, it's a bit ugly, and before we explore the idea further, it would be nice to know if this would cause Linus to vomit in disgust and/or refuse patches from darcs users. Another slightly less noxious possibility would be to store the darcs patch as a "hidden" file, if git were given the concept of commit-specific files. So then we could include in the commit log something like "Darcs-patch: 780c057447d4feef015a905aaf6c87db894ff58c". We could do this silently, except that I wonder if fsck would delete these files, since they aren't pointed to by any trees.

On Mon, Apr 18, 2005 at 12:02:15AM +0200, Juliusz Chroboczek wrote:

Right.

It's true that we'd need to keep the cache in sync, which would mean making sure it gets updated with every repository-modifying darcs command, but we've already got a cache that has those properties, and it seems like modifying the interface to deal with a more complex cache would be relatively straightforward, and would likely have other advantages, such as if we wanted to implement a per-file cache to speed up annotate (since the speed of annotate seems to be a relatively common concern).

Basically, I'm imagining that we'd have to replace writePristine and write_dirty_Pristine with the applyPristine that Ian implemented for efficiency reasons. So we'd write to pristine by throwing patches at it, and letting it do what it pleases with them. Then we'd read from Pristine as usual--but we might want to add interfaces for reading slurpies of older versions from the pristine cache. This would again be a helpful interface anyways, since it might allow us, for example, to use checkpoints when reading older versions.

The problem I have with this is that "other" repository formats (e.g. git) store "tree versions", not "changes", and I think it would be fragile to try to store "changes" (in the darcs sense) in them.

I see. You're thinking of using darcs as a client for other SCMs. That's sort of how I'm thinking of darcs interacting with git, so we aren't so far off in terms of goals. My hope would tend to be that people would coalesce around git--since Linus will be using git. If everyone can interoperate with git, we'd be able to interoperate with everyone, in a sense, anyways.

I'm not really comfortable with this, although I can see that there is an appeal to it, and that something like it may turn out to be necesary for interacting with systems for which we can't create a simple mapping of patch IDs.

Okay, this is definitely a good goal. See below for thoughts on how this should be accomplished.

This I find a bit confusing. So a patch can have two IDs, presumably something like a "darcs ID" and a "git ID"? I can see that this might simplify some things, but am not sure how it would work. The IDs would have to have a hierarchy, so that you wouldn't ever end up with the "same" patch having disjoint IDs in two cases.

Here's where I think I'd differ. I think when dealing with git (and probably also with *any* other SCM (arch being a possible exception), we need to consider the exchange medium to be not a patch, but a tag. Git only knows about "versions" of the tree, which in darcs terminology is a tag. It *does* know about the (possibly multiple) parents of a given version, so we have a "context" for the patch--provided those two (or one...) parents are treated as tags.

So in pulling from git, I'd treat each git change as a patch followed by a tag. When pulling from git, unfortunately, the contents of that patch will be determined by our diff algorithm, so if we want long-term stability we might need to mummify a variant of the diff algorithm that we agree not to change, and to always use when computing patches from a git archive. This tagging (and I imagine the tags will look something like "git:0c16636264037e8b5ccd38b28ecd191aebc67389") will mean that we can create a single-patch darcs "patch bundle" for any given git commit. Which is to say, that we'll be able to "see" a git repository as an odd-looking darcs repository.

This means that getting a fresh darcs repository from git would potentially involve a whole lot of merging...

Putting darcs patches *into* git is more complicated, since we'll want to get them back again without modification. Normal "hunk" patches would be no problem, provided we never change our diff algorithm (which has been discussed recently, in the context of making hunks better align with blocks of code). We could perhaps tell users not to use "replace" patches. But avoiding "mv" patches would be downright silly. So we're somehow going to have to either sneak this sort of metadata into the git repository, or we're going to have to store just the darcs "patch ID" in the git repository, and require that darcs users get the actual patch from somewhere else. I had been imagining the latter, but now I'm wondering if the former is a reasonable possibility.

Linus has said that he figures an SCM needs to be built on top of git, and that SCM--rather than git itself--would be the one that would know about things like file renames, probably by storing some sort of rename metadata. I wonder if we could perhaps store the entire darcs patch in the git commit? It seems a bit abusive, but would certainly be the easiest way to interface losslessly with git. So when we pull from git, we'd look in the commit log for the magic words indicating that this is really a darcs patch. If so, we could handle it natively. If not, we'd know it was actually a "gittish" entity, and requires that we diff a couple of trees to find the actual patch to be used with darcs' patch theory.

The ugliness of this idea is that it involves storing redundant information. And I think we'll have a bit of an excercise in commutation and merging when we get the patches from a git repository, since in git they'll be stored in tree form, but that's something we'll have to do even to create a read-only darcs mirror of a git repository.

We could perhaps alleviate the pain by perhaps not including the actual contents of new or deleted files in the patch, but instead retrieve those from git directly. But that might be more trouble than it's worth, at least for the first sketch.

Since git stores a branched history rather than a linear history, I'm not sure that we'll ever need to store mergers in git. Instead, we could just commute until the mergers disappear (which might be a bit scary), and then store *that* in git. On the other hand, if this is to inefficient, and if we store actual darcs patches in git, then we wouldn't perhaps need to worry about mergers as a special case.

Err, I think I've answered that one... :)

On Mon, 18 Apr 2005, David Roundy wrote:

Hell no.

The commit _does_ specify the patch uniquely and exactly, so I really don't see the point. You can always get the patch by just doing a

	git diff $parent_tree $thistree

so putting the patch in the comment is not an option.

Then you can use the patch to index to whatever extra "darcs index" information you want to.

That's definitely the case. I will _not_ be taking random files etc just to keep other peoples stuff straightened up.

If you want to add a "log ID", you can certainly do that, but the data the ID refers to is _you_ data, and will not go into the git archive. So:

No, git will not track commit-specific files. There's the comment section, and that _is_ the commit-specific file. But I will refuse to take any comments that aren't just human-readable explanations, together with maybe one extra line of

	# Darcs ID: 780c057447d4feef015a905aaf6c87db894ff58c

(others will want to track _their_ PR numbers etc) and that's it. The actual darcs data that that ID refers to can obviously be maintained in _another_ git archive, but it's not one I'm going to carry about.

			Linus

On Mon, Apr 18, 2005 at 08:38:25AM -0700, Linus Torvalds wrote:

I was afraid that would be the response...

The issue is that in darcs the parent and child trees *don't* uniquely or exactly specify the patch. In fact, even the output of git diff will depend on what version of diff you're using (e.g. if someone were to use BSD diff rather than GNU diff).

Okay.

The trouble is that the philosophy of darcs and git are about as orthogonal as one can come. Git treats the content as fundamental, where in darcs the changes are fundamental. Since in darcs there can be different changes that lead from the same parent to the same child--and these differences are meaningful when merges happen---when interacting with git, we either need to restrict darcs to only describe changes in a way that can be uniquely determined by a parent and child, or we need to have extra metadata somewhere.

For bidirectional functionality, we either need to avoid the use of advanced darcs features, or we need to include that information in git somehow, or we need to keep a parallel darcs archive holding that information.

Would a small amount of human-readable change information be acceptable in the free-form comment area? In the rename thread I got the impression this would be okay for renames. For example,

rename foo bar

or (this is less important, but you might consider it to be a useful human-readable comment)

replace [_a-zA-Z0-9] old_variable new_variable file/path

Currently these two patch types account for almost the sum total of the cases where different patches lead to the same resulting trees.

On Tue, 19 Apr 2005, David Roundy wrote:

Sure. That's human-readable and meaningful, as in "it actually makes sense as a commit comment regardless of any darcs issues". As does:

which is almost so (a human would have written "rename old to new", but the above isn't _that_ different).

HOWEVER, then the requirement would be that we'd never have complex combinations of the above. Ie having 2-5 lines of something like that is "human-readable". Having 10+ lines of the above is not. See?

I have this suspicion that the "replace" thing often ends up being done on dozens of files, and I don't want to have dozens of lines of stuff that ends up really being machine-readable. But if it's ok to depend on the content changes (you _do_ see which files changed) together with a single line of "replace [token-def] xxx yyy", then hell yes - I consider that to be useful information even outside of git.

(In other words: if it looks like something a careful human _could_ have written, it's certainly ok. But if it looks like something a careful human would have used a script to generate 40 entries of, it's bad).

		Linus

Linus Torvalds wrote:

This is the way that darcs would currently represent a "darcs replace foo bar" on 15 files, which is obviously exactly what you are objecting to: [global foo to bar tupshin@tupshin.com**20050419155539] { replace ./dir1/file1 [A-Za-z_0-9] foo bar replace ./dir1/file2 [A-Za-z_0-9] foo bar replace ./dir1/file3 [A-Za-z_0-9] foo bar replace ./dir1/file4 [A-Za-z_0-9] foo bar replace ./dir1/file5 [A-Za-z_0-9] foo bar replace ./dir2/file1 [A-Za-z_0-9] foo bar replace ./dir2/file2 [A-Za-z_0-9] foo bar replace ./dir2/file3 [A-Za-z_0-9] foo bar replace ./dir2/file4 [A-Za-z_0-9] foo bar replace ./dir2/file5 [A-Za-z_0-9] foo bar replace ./dir3/file1 [A-Za-z_0-9] foo bar replace ./dir3/file2 [A-Za-z_0-9] foo bar replace ./dir3/file3 [A-Za-z_0-9] foo bar replace ./dir3/file4 [A-Za-z_0-9] foo bar replace ./dir3/file5 [A-Za-z_0-9] foo bar }

I see two possible complementary ways to address this:
1) allow something akin to the above form in git free-form comments as a 
*technical* solution, while leaving it up to the individual repository 
owner whether to accept such patches on aesthetic grounds.
2) explore adding a different format to darcs that would allow a files 
affected to be represented more compactly.

I suspect that any use of wildcards in a new format would be impossible for darcs since it wouldn't allow darcs to construct dependencies, though I'll leave it to david to respond to that.

At a minimum, something like: replace ./dir1/[file1|file2|file3|file4|file5] [A-Za-z_0-9] foo bar replace ./dir2/[file1|file2|file3|file4|file5] [A-Za-z_0-9] foo bar replace ./dir3/[file1|file2|file3|file4|file5] [A-Za-z_0-9] foo bar should be pretty feasible.

I don't believe, however, that it would ever be 100% reliable to try to look at a one line replace description and combine it with the actual changes and end up with a correct darcs replace patch.

-Tupshin

On Tue, 19 Apr 2005, Tupshin Harper wrote:

Note that git _does_ very efficiently (and I mean _very_) expose the changed files.

So if this kind of darcs patch is always the same pattern just repeated over <n> files, then you really don't need to even list the files at all. Git gives you a very efficient file listing by just doing a "diff-tree" (which does not diff the _contents_ - it really just gives you a pretty much zero-cost "which files changed" listing).

So that combination would be 100% reliable _if_ you always split up darcs patches to "common elements".

And note that there does not have to be a 1:1 relationship between a git commit and a darcs patch. For example, say that you have a darcs patch that does a combination of "change token x to token y in 100 files" and "rename file a into b". I don't know if you do those kind of "combination patches" at all, but if you do, why not just split them up into two? That way the list of files changed _does_ 100% determine the list of files for the token exchange.

		Linus

On Tue, Apr 19, 2005 at 09:49:12AM -0700, Linus Torvalds wrote:

The catch is that it's possible to have a darcs patch that doesn't change any files, or that affects files without changing them. If I rename function foo to bar, I might want to do

darcs replace foo bar *.c

which would issue a replace on all files, which means that when this patch is merged with any patches that add occurrences of foo in a file, that will get modified to a bar, regardless of whether there was previously an occurrence of foo in that file.

I think we might (when working with git--it would be problematic within darcs straight) be able to work out some sort of a wildcard replace scheme, so it could be something like

replace foo bar in: mm/*.c

The regexp bit could be left out, if we restrict the definition of "tokens" in token replaces--which probably isn't a troublesome limitation. By default darcs uses two tokenizing schemes, one which allows "." in tokens (usually relevant in Makefiles), and one which doesn't, and basically matches C identifiers. We could allow for both of these if we had a second option:

replace filename foo.h bar.h in: mm/*.c

We'd just need to expand the wildcards when translating from the git repository into darcs patches.

We do allow multiple sorts of changes (in darcs terminology, multiple "primitive patches") in a single patch.

One *could* have multiple git commits for a single darcs patch, but that seems ugly and I'd rather avoid it. In my view, revision control system is more about communication than history (which is why by default, darcs doesn't "do" history), and grouping changes together is how we express which changes "go together". Of course, we could still have a grouping at a higher level, so that a single "changeset" could consist of multiple git commits (for example by recognizing that identical commit logs mean that it's a single change), but that adds a layer of complexity that I'd like to avoid if possible.

On Mon, 2005-04-18 at 08:20 -0400, David Roundy wrote:

Okay, I still haven't used git yet (and have only toyed around with darcs for a bit), so take what I'm saying with a grain of salt. Regardless, I think you may be asking the wrong question. The tracking of renames was bandied about pretty thoroughly on-list from Wednesday through Friday (for far better commentary and insight, see Linus' messages with subject: Merge with git-pasky II.)

git does track changesets that describe the parent tree(s) and the result. The trees track filenames and hashes. So, doing a fairly straightforward compare on two trees will let you immediately discover renames that have occurred, as the filename in the tree changed while the hash didn't.

So, the question then becomes, can an outside tool cheaply derive all the information that darcs would need to perform it's work? The renames should be easy, as long as no content changed during the rename. As for token replacement (and whitespace changes, etc.), that could be discovered via domain-specific parsers (something specific per language, for example). Linus tossed a link to one such tool (hmm, where was it. Sheesh. You sure right a lot, dude :-).)

	http://minnie.tuhs.org/Programs   (see Ctcompare)

...which should be viewed more as a proof-of-concept than a mergeable code-set. It does show that diff's vocabulary is sadly lacking in expressiveness, and improving that, I think, would be a useful area to expend effort.

Again, I may be off here, especially considering I've a backlog of a couple hundred messages to read since the weekend. (You guys need to go outside more often.)

Ray

[Using git as a backend for Darcs.]

Not really; a Darcs patch is just a pair of two git versions (from and to). Which is why Darcs needs to support arbitrarily formatted patch ids -- a patch originating from git will be identified by a pair of git hashes.

Obviously, we'll need to think harder when pushing from darcs into git (we'll need to preserve the Darcs patch id somehow), but it's premature to worry about that right now.

Why?

It's a case of ``don't do that''.

Suppose I record a patch in Darcs; it gets a Darcs id. I push it into git, at which point it gets a git id, whether we want it to or not. What do we do when we pull that patch back into darcs?

Either we arbitrarily discard one of the ids (which one?), or we keep both. If there's more pulling/pushing going on on the git side, we definitely need to keep both.

Same to you ;-)

We're thinking in opposite directions -- you're thinking of the alien versions as integrals of Darcs patches, I'm thinking of Darcs patches as derivatives of alien versions.

  You:  alien version = Darcs tag

  Me:   Darcs patch = pair of successive alien versions

My gut instinct is that the second model can be made to work almost seamlessly, unlike the first one. But that's just a guess.

Good point, noted.

Aye, that will require some metadata on the git side (the hack, suggested by Linus, of using git hashes to notice moves won't work). Happily, it's premature to worry about that, too.

                                        Juliusz

On Tue, 2005-04-19 at 02:55 +0200, Juliusz Chroboczek wrote:

Okay, I'm coming to believe I missed something. So, why won't it work?

Ray

Because two files can legitimately have identical contents without being ``the same'' file from the VC system's point of view.

In other words, two files may happen to have the same contents but have distinct histories.

                                        Juliusz

On Tue, 2005-04-19 at 10:22 +0200, Juliusz Chroboczek wrote:

Eh, let's not talk using integral/summation view across all the patches that ever could have come in against the file. We're hamstringing ourselves if we do that, and it's not what darcs does. darcs looks at a differential view of the changes, and for a mv, it looks at it when it happens.

darcs does a "darcs mv" to commit a "file move patch" to whatever logging or patch repository it keeps below the surface.

The equivalent in git would be to have a given tree, move a file via bash's mv, and then checkpoint a new tree. (I'm sure there's details in there, but that's plumbing, and what we have Petr for.)

A differential comparison of the two trees shows no content changed, but a file label was modified. Ergo, a rename occurred.

QED.

~r.

On Tue, Apr 19, 2005 at 02:55:05AM +0200, Juliusz Chroboczek wrote:

...

I'm not clear why it would be necesary, and it takes the only immutable piece of information regarding a patch, and makes it variable. Just seems dangerous and complicated, and I'm not sure why we'd need to do it.

Or alternatively, we could have a one-to-one mapping between git IDs and darcs IDs, which is what I'd do.

The problem is that there is no sequence of alien versions that one can differentiate. Git has a branched history, with each version that follows a merge having multiple parents. How do you define that change? It's easy enough to do if we tag each git version in darcs, since we know what the two parents are, and we know what the final state is, but there *is* no translation from a single git ID either to a single patch(1) patch, or to a single darcs patch--unless you treat its parents as tags.

The key is that we can't make git work like darcs, so we'll have to make darcs work like git. If we do it right (automatically tagging like crazy people), darcs users between themselves can cherry-pick all they like, without introducing inconsistencies or losing interoperability with git.

To summarize how I'd see the mapping between git information and darcs, a git commit would be composed of one darcs patch and one darcs tag. With this mapping, I don't believe we lose any information, and I believe we'll be able to (except that patches would have to be uniquely determined by a pair of trees) simply translate the darcs system right back again, since it's a one-to-one correspondence of information.

My proposed mapping:

tree 6ff0e9f3d131bd110d32829f0b14f07da8313c45 # This is a darcs tag ID parent abd62b9caee377595a9bf75f363328c82a38f86e # This is the context of both a patch and tag. author James Bottomley <James.Bottomley@SteelEye.com> 1113879319 -0700 # This is the author and date of the patch committer Linus Torvalds <torvalds@ppc970.osdl.org.(none)> 1113879319 -0700 # This is the author and date of the tag # Everything below would be the name and long comment of the patch

[PATCH] SCSI trees, merges and git status

Doing the latest SCSI merge exposed two bugs in your merge script:

1) It doesn't like a completely new directory (the misc tree contains a
   new drivers/scsi/lpfc)
2) the merge testing logic is wrong.  You only want to exit 1 if the
   merge fails. 

[Removing Linus from CC, keeping the Git list -- or should we remove it?]

Er... I'm not suggesting to make it variable, just to make it an opaque blob of bytes (still immutable). I see from the examples you give below that you agree that the format needs extending, so I suspect we're actually agreeing here, just failing to communicate.

about having multiple ids per patch:

Okay, you've convinced me. It's much simpler that way, we'll see how well it works.

Yep. I've just realised that this morning. Is there some notion of ``primary parent'' as in Arch? Can a changeset have 0 parents?

You've lost me here. How can you cherry-pick if every tag depends on the preceding patches? Or are you thinking of pulling just the patch and not the tag -- in that case, what happens when you push to git a Darcs patch that depends on a patch that originated with git?

I've started interfacing Haskell with git this week-end, that's something we'll need whichever model we choose. We should be able to start playing with actually modifying Darcs after next week-end.

                                        Juliusz

Dear diary, on Tue, Apr 19, 2005 at 02:20:55PM CEST, I got a letter where Juliusz Chroboczek <Juliusz.Chroboczek@pps.jussieu.fr> told me that...

Yes, the root commit. Usually, there is only one, but there may be multiple of them theoretically.

On Tue, Apr 19, 2005 at 02:25:18PM +0200, Petr Baudis wrote:

Incidentally (and completely off-topic for this thread), wouldn't there be a sha1 tree hash corresponding to a completely empty directory, and couldn't one use that as the parent for the root? Would there be any reason to do so? Just a silly thought...

On Tue, Apr 19, 2005 at 02:20:55PM +0200, Juliusz Chroboczek wrote:

I think leaving much of this on git would be appropriate, since there are issues of how to relate to git that should be relevant.

Yes, I'm thinking of pulling patches from one darcs repo to another. If we cherry-pick in this way, we need to create a "git-tag" for each patch that we pull without its associated tag. To git, this would look like two separate changes that have the same commit log, except that they have different parents and different commiters and commit dates.

I don't think this will be a problem for git, and since darcs will recognize the two patches as the identical darcs patch (we'll need to put somewhere in the git commit log a magic word indicating that this patch originated in darcs), there won't be a problem for darcs either.

In case I haven't been clear (which seems likely), the scenario is that darcs user 1 makes the following changes to his darcs version of a git-based repository:

changes in 1: A -> B tags in 1: A1 B1

Darcs user 2 wants B, but not A, and didn't do any development:

changes in 2: B tags in 2: B2

User 2 pushes to git, and now git has (where P is the parent of both of the above):

git:
P -> B/B2  (where B/B2 is the commit log with B2 as "committer info" and B
            as the "author info and long comment)

User 1 pushes (everything) to git and merges the two (patch M, which has two parents, B1 and B2:

git:

   ->B/B2---------
  /               \
P--> A/A1 -> B/B1---> M

It's a little lame, and if user 2 doesn't do any real work, the git-using person might be annoyed, but I think it's doable.