Re: [Monotone-devel] About the recent change of cvs_import...

[Nathaniel Smith]

On Mon, May 23, 2005 at 12:39:07AM +0200, Graydon Hoare wrote:
> On 5/20/05, Nathaniel Smith <address@hidden> wrote:
> > Err, crud.  You're right.  I hadn't actually looked at graydon's
> > change yet, thanks for pointing it out... This change is a problem,
> > because it means that we _have_ to support file suturing, in all its
> > icky glory, right from the get-go.  Or else tell people that have
> > imported from cvs that sorry, they just can't do any merging, which
> > would be terrible.
> 
> I do not immediately see the problem with suturing. there's a missing
> LCAD state S on your diagram, above A and B (else this degrades
> immediately to 2-way merge). on the S-D edge of the merge you have a
> composite edge saying "add foo" and on the S-E edge you have a
> composite edge saying "add foo, add bar". none of these 3 files can be
> identified -- the tids all have null names in S so cannot be
> name-compared for identification -- so you will be doing a fresh 2-way
> merge on the tree states. which is, I think, somewhat calm and
> non-pathological. probably, as usual, I'm missing the pathological
> case.

Yes, at the moment, this works fine.  However, in the above, you're
taking advantage of the fact that 3-way merge loses information about
file identity, which is a problem that we need to fix... :-)

It may make the weirdness inherent in suturing clearer to imagine a
(slightly) different example: suppose that the two files "foo" were
created independently, and then got renamed to "bar" and "baz" on one
side, and got sutured on the other.  Now, if we looked at one part of
the graph, we have a rename versus nothing, so we'd expect the sutured
file to end up with the name "bar".  If we look at the other, we'd
expect the sutured file to end up with the name "baz".  But... these
have become the same file.

We can, at least in this case, come up with _something_ to call "the
result of the merge", by using 3-way and throwing away some
information.  But it doesn't seem like this is a particularly good
thing, and I'm not confident that it really works right in general...
I'd be much more comfortable saying that you get a new logical file
each time you say "add", and no other time.  In the above, we
effectively added two files, and ended up with 3 logical files.  In
the general case, I think you can add n files, and end up with 2^n - 1
logical files, or something like that.

The situation may be worse for deletes; consider that if instead of
renaming the files, I just deleted them on each side, and then merged
with the sutured file -- the sutured file would survive, even though
both of its ancestors were deleted.

> > Surely we can do better than this?  I _think_ cvs2svn does something
> > more sensible here, and it's solving exactly the same problem we are;
> > if someone could figure out how it handles this sort of wackiness,
> > that would be very helpful.
> 
> hey, if they have an algorithm which actually works, by all means crib it.

I'm not sure what their algorithm is, but it certainly seems like an
existence proof that it's possible to do better than just giving
up...

> > It also seems like it would be _better_ than the current thing to just
> > make a guess at the branch-point -- basically, calculate exactly the
> > same manifests we calculate now, but instead of rooting them at the
> > tail ancestor, root them at the first commit on the branch we see.
> 
> I considered doing this, but it really doesn't work:
> 
> - there is no guarantee there ever was a commit "on the branch". the
> branch tag might be present in a file, but it could just be a tag
> hanging off the last-committed-trunk-version. this could be very old;
> you don't necessarily want to go all the way back to it.
> 
> - there is no guarantee of a shared branching tree-order between
> files. I can just randomly branch-tag a file into branch B from branch
> C, and another file into B from A. we have a testcase from a real CVS
> repository which does this.
> 
> - it is not what CVS does. if a branch tag is present in 5 of 10
> files, checking out the branch is only supposed to check out those 5
> files. not all 10, even if they were live when the branch was cut.
> 
> I considered rooting the branch in the latest branchpoint in any of
> the affected files, and killing non-tagged files, but the second point
> killed that idea. I'm open to suggestions though.

What if we do what you say, and deal with the second point by just
saying, oh well, one of you loses?  i.e., if there are
inconsistencies between files, pick one file to win, and lose some
history on the others; it would seem better than losing history in all
cases, even those where the the history could have been represented
exactly...?

But perhaps I'm not understanding the issues, I haven't stared as
deeply into the cvs_import abyss as some :-).

-- Nathaniel

-- 
"On arrival in my ward I was immediately served with lunch. `This is
what you ordered yesterday.' I pointed out that I had just arrived,
only to be told: `This is what your bed ordered.'"
  -- Letter to the Editor, The Times, September 2000