Re: [darcs-devel] Darcs and git: plan of action

Er... no.

One of darcs' big points is that it has at least two fundamentally different *kinds* of patches. One is the classic diff(1) style.

The other is "replace very instace of identifier `foo` with identifier`bar`".

Note that merging such a patch with another that adds a new instance of "foo" has a quite different effect from a similar diff-style patch. Even though both have identical effects on the tree to which they were initially merged.

And darcs is specifically intended to support additional kinds of patches. Again, all in order that the patch can work better when applied to trees *other* that the one it was originally developed against.

Anyway, the point is that, in the darcs world, it is NOT possible to reconstruct a patch from the before and after trees.

On Mon, 2005-04-18 at 21:04 +0000, linux@horizon.com wrote:

That could be derived, however, by a particularly smart parser [1]. Alternately, that itself could be embedded in the comment for patches sourced from darcs. Of course, that means patches from others are less commutable than from other darcs users, but that's the price you'd pay for relying on the user to explicitly note a token rename.

  [1] An example: http://minnie.tuhs.org/Programs/Ctcompare/index.html

As for "darcs mv", that can be derived from the before/after pictures of the trees.

Anything missing out of what I listed above? (darcs has adddir and addfile, IIRC, but those are trivially discovered via inspection of the trees as well, I think.)

Not yet, and maybe not ever, but I think we can certainly get closer to discovering what the coder was thinking during a changeset.

Ray

Ray Lee wrote:

No, it can't. Seriously. A darcs replace patch is encoded as rules, not effects, and it is impossible to derive the rules just by looking at the results. Not difficult. Impossible. You could guess, but that's not good enough for darcs to be able to reliably commute the patches later.

I am curious whether Linus's suggestion about including the corresponding darcs patch id in the git commit comments would be good enough.

Perhaps. If a file is moved and edited within the same commit, I'm not sure that you can be certain whether it was done with d 'darcs mv' or not. Requiring separate checkins for the rename and the subsequent modify would make things easier on SCM's, but is impractical in real life. Automated refactoring tools, for example, perform the rename+modify as an atomic operation.

Now, git might not need to deal with any of this, because it only needs to work with the kernel project. But darcs does have to deal with this wide range of uses, as does just about any other SCM.

I'm *not* advocating cluttering up git with features that are not directly needed for kernel development. I'm just trying to clarify the facts so everyone can understand what darcs is trying to do.

Kevin

On Mon, 2005-04-18 at 21:05 -0400, Kevin Smith wrote:

Okay, either I'm a sight stupider than I thought, or I'm not communicating well. Same net effect either way, I 'spose.

If I do a token replace in an editor (say one of those fancy new-fangled refactoring thangs, or good ol' vi), a token-level comparator can discover what I did. That link I sent is an example of one such beast.

Who said anything about guessing? If a user replaces all instances of foo with bar, that's as close to proof as you can ever get, without recording intent of the user at the time it's done. Now, I realize that darcs *does* record intent, but I claim that's immaterial.

Perhaps I'm clueless; it's happened before, I'm resigned to it happening again. So, tell it to me with full jargon, if you will. When it comes down to brass tacks, why does my suggestion place weaker guarantees about the quality of the resulting patch operator?

Agreed. But then you go lart the committer of that patch.

Eh? Why? "darcs mv" *is* a commit. Just because it doesn't seem to look like one doesn't change the fact that you just invoked the SCM.

And that's harder, I agree. But unless I'm missing some nifty refactoring editor out there that integrates with darcs during the edit session, the user *still* has to tell the SCM about the rename manually.

It'd be unfortunate if git were limited to such a small developer base.

I'm not claiming you are. We want the same thing -- a nuanced SCM that can take some of the drudge-work away from this stuff.

Ray

Ray Lee wrote:

The big feature of a darcs replace patch is that it works forward and backward in time. Let me try to come up with an example that can help explain it. Hopefully I'll get it right. Let's start with a file like this that exists in a project for which both you and I have darcs repos:

cat dog fish

Now, you change it to:

cat dog dog fish

while I simultaneously do a replace of "dog" with "plant", resulting in:

cat plant fish

We merge. The final result in both of our trees is:

cat plant plant fish

Notice that just by looking at my diffs, you can't tell that I used a replace operation. I didn't just replace the instances of "dog" that were in my file at that moment. I conceptually replaced all instances, including ones that aren't there yet.

Now, I should mention here that I personally dislike the replace operation, and I think it is more dangerous than helpful. However, other darcs users are quite happy with it, and it certainly is a creative and powerful feature.

Other creative patch types have also been dreamed of. For example, a powerful language-specific refactoring operation has been discussed as a far-future possibility. That would be safe, and cool.

Although there are no such nifty refactoring tools available today, they will exist at some point. If they existed today, the world would be a better place.

Even without tools, many shops have policies against checking in code that won't compile. If you rename a java class, you must simultaneously perform the rename and modify the class name inside. If you commit between those steps, it's broken. [I do realize that the kernel doesn't have java code, by the way.]

I should also mention that I currently believe that Linus is correct that explicit rename tracking is not required for git. I have every hope that his plan for handling the more general case of "moved text" will take care of renames as a side effect. I don't know if that will be sufficient to allow a two-way lossless gateway between git and darcs or other systems that do track renames explicitly.

Kevin

On Monday 18 April 2005 10:05 pm, Kevin Smith wrote:

I think that's the best explanation of how it works. And that is partially why darcs is so powerful.

(Sorry for the delayed reply -- I'm living on tape delay for a bit.)

On Mon, 2005-04-18 at 22:05 -0400, Kevin Smith wrote:

That's *not* a feature of the token replace patch, however. That's a feature of the darcs commutation machinery, correct? (With the obvious caveat that darcs can only *do* the commutation if it has correctly nuanced darcs-style token replace patches, rather than mere ASCII textual diffs.)

Okay, that all makes sense.

Here's where we disagree. If you checkpoint your tree before the replace, and immediately after, the only differences in the source-controlled files would be due to the replace. And since the language of the file is known (and thereby the tokenization -- it *is* well-defined), then a tokenizer that compares the before and after trees (for just the files that changed, obviously), can discover what you did, and promote the mere ASCII diff into a token-replace diff. (The same sort of idea could be done for reindention, I'd hope.)

Well yes, that's exactly what we want. And the key point of all of this is that there's no magic here. The darcs machinery does all the commutations such that the patches can wiggle together without conflicts. To do it's job, of course, it needs nuanced patches, rather than the quite literal ones generated by diff.

We agree on everything except that it's provable that one can discover a replace operation, given a before and after tree.

It's creative alright, though I had the same misgivings. In my common code workflow, I almost never have global tokens -- all my replaces would be per function, so I never saw an opportunity to use it when I was screwing around with darcs.

<subliminal> indention patch type, indention patch type... </subliminal>

Yeah, I spent some time drooling over the refactoring editors before slapping myself and deciding I'd wait for others to live on that bleeding edge for a while. I've had to clean up too much code from other people.

I'm trying hard to find a nice way to say that's silly. I'm failing. My suggestion in that case would be that the local coder commit many patches to a local repository, one of which is the rename. Then upon completion of the refactoring, the set of patches is committed to the group repository. Tags before and after preserve the repository's precondition that it always compiles.

Don't worry, I didn't think that you did :-).

Ray

Ray Lee wrote:

This is assuming that you only have one replace and no other operations recorded in the patch. If you have multiple replaces or a replace and a traditional diff recorded in the same patch, then this is not true.

See above for one set of limitations on this. A more fundamental problem comes back to intent. If I have a file "foo" before: a1 a2 and after: b1 b2 is that a "replace [_a-zA-Z0-9] a b foo" patch, or is that a -a1 -a2 +b1 +b2 patch? Note that this comes down to heuristics, and no matter what you use, you will be wrong sometimes, *and* the choice that is made can substantively affect the contents of the repository after additional patches are applied.

It's provable that you can not.

-Tupshin

On Tue, 2005-04-19 at 16:00 -0700, Tupshin Harper wrote:

I had a precondition on my argument (not quoted), that the code was checkpointed before and after. Obviously, a large set of changes in one patch is a problem. However, a darcs replace is (effectively) a commit on its own, so I was limiting myself to the same situation under a different system.

Okay, so in reading the online darcs manual (yet) again, I now see that it allows regular expressions for the match and replace, which means multiple unique tokens could change atomically. (Does anyone actually *use* regexes? Sounds like a cannon that'd be hard to aim.)

Regardless, I only care about code, not free text. If it's in a language that doesn't do some use-'em-as-you-need-'em duck typing spiel (<cough>python</cough), then the context of your patch (namely, the file) already has those tokens somewhere in them. And I bet that if *you* looked at that file, you could tell if it was a replace or a mere textual diff. Am I wrong?

Unless I'm missing something, the darcs replace patch can already do the wrong thing. If I do a replace patch on a variable introduced in a local tree, then do a darcs replace on it before committing it to a shared repository, and coder B introduces a variable of the same original name in my copy, then there's a chance that the replace patch will incorrectly apply upon his newly introduced variable. No?

I'm still not seeing the problem, at least when it comes to ANSI C.

Ray

Ray Lee wrote:

Yes, and replace patches need to be used very carefully.

Yes. See my hello world example from my last email.

Yes, depending on how you define wrong. Darcs replace is fully predictable, and poorly chosen replaces can lead to incorrect results after future patches are applied.

Absolutely correct, and the exact reason why replace patches need to be used *very* selectively.

See hello world example in my other email. You can argue that it is an existing problem in darcs, but really, it just points out the fact that a computer is *incapable* of knowing whether it is safe to use a replace patch based on a diff because replace patches are dangerous if not used intelligently.

-Tupshin

Ray Lee wrote:

But I might have manually changed those tokens, or I might have done it with a replace operation. Just looking at the diffs, those two cases would look identical and be indistinguishable. The only way to know whether or not a darcs replace was done was to look at the patch metadata.

Pop quiz:

Here is revision 1 of my file:

    abcde

Here is revision 2:

    wow

Now, did I do that with a darcs replace, or just by typing?

Kevin

On Tue, 2005-04-19 at 19:03 -0400, Kevin Smith wrote:

I'm still not communicating well.

Give me a case where assuming it's a replace will do the wrong thing, for C code, where it's a variable or function name.

Ray

Ray Lee wrote:

I think you are communicating fine, but not fully understanding darcs.

try this: initial patch creates hello.c #include <stdio.h>

int main(int argc, char *argv[])
{
  printf("Hello world!\n");
  return 0;
}

second patch: replace ./hello.c [A-Za-z_0-9] world universe

third patch, for conceptual clarity, created in another repository that 
had seen the first patch, but not the second (adds function wide_world):
hunk ./hello.c 3
+void wide_world()
+{
+  printf("Hello wide world\n");
+}
+
hunk ./hello.c 11
+  wide_world();
}

If patch2 was a replace patch, then the result of running the combined 3 patch version would be: Hello universe! Hello wide universe

but if patch2 was a non-replace patch, then the result would be: Hello universe! Hello wide world

-Tupshin

Thanks for your patience.

On Tue, 2005-04-19 at 16:32 -0700, Tupshin Harper wrote:

Aha! Okay, I now see at least part of issue: we're using different definitions of 'token.' Yours is quite sensible, in that it matches the darcs syntax. However, I'm claiming a token is defined by the file's language, and that a replace patch on anything but a token as per those language standards is a silly thing.

In your example, I'd claim you did an inter-token edit, as the natural token there was "Hello world!\n".

With that, let me restate what I think is possible.

One should be able to discover renames (replaces) of user identifiers in C code programmatically. Is that everything darcs replace does? Obviously not. Is that what users would usually *want*? If I were using it, that's what I'd want (especially including the limited scope of replacement -- user identifiers such as variable or function names, etc.). But then I'm not a lurker on the darcs user list, so I don't know how usage of darcs replace plays out in actual practice.

So, it's a subset. Is it a useful subset? Yes, as it addresses what happens during refactoring, which is when I'd usually see this getting used. (Syntactically ignorant search and replace is so, y'know, *1970s*.)

Any clearer?

Ray

Please recall the context of this discussion: getting Darcs to grok git repositories.

You are arguing that it should be possible to design a set of heuristics that Do The Right Thing often enough. And you are probably right.

But the point is immaterial as nobody has stepped up to implement in Darcs the sort of heuristics you have in mind. Partly because nobody has time, but mostly because we don't like heuristics, we prefer Darcs to remain deterministic.

So while yes, it might be possible to get about using heuristics, it seems rather unlikely that that's what we'll do.

                                        Juliusz

On Tue, Apr 19, 2005 at 06:11:43PM -0700, Ray Lee wrote:

The trouble is that a token based on language standards is also wrong, unless your file at all times is syntactically correct. It also means (for C in particular) that the result of the token replace isn't uniquely determined by the combination of the token replace patch and the file it applies to, since you need parse any header files in order to tokenize the C file. In the case of header files, it may not be possible to tokenize them uniquely, since they may tokenize differently depending on what other header files are included before them. And of course, none of this may be possible if you haven't run autoconf and configure, since you may not actually *have* the header files in the first place...

In a (reasonably) general-purpose tool like darcs, I think it's better to stick with a simpler definition of token that doesn't require a complete integrated development environment.

It's also true that often you want to modify headers and string contents simultaneously with the change of the code itself. When I replace get_pseudowavefunction with get_atomic_orbital, I also want to modify

// We call get_pseudowavefunction to get the atomic orbital...

and

printf("Error in get_pseudowavefunction!\n");

Hi Ray,

How about two patches.

    1.  s/foo/bar/ throughout file because foo() has been decided upon
    as the name of a new globally visible forthcoming function but was
    already in use as a static function.

    2.  Add definition of new foo().

Patch 1 mustn't be a `darcs replace' despite it changing every occurence of the C token foo into bar.

Cheers,

Ralph.

On Mon, Apr 18, 2005 at 06:42:11PM -0700, Ray Lee wrote:

The problem is, how do you know how to define a token? That's also included in a darcs patch. And a darcs user may choose not to use a replace patch, if (for example) he's renaming a local variable, since he might not want to mess with other functions in the same file.

Guessing the author's intent cannot reliably reproduce the author's stated intent. Either we need to include that information in one form or another (and in one location or another), or we've got to simply disallow replaces (and moves?) when interacting with git.