[MERGE] deprecated EmptyTree

[Robert Collins]

On Sun, 2006-07-23 at 21:48 -0400, Aaron Bentley wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Robert Collins wrote:
> > I find it hard to conceive of 'tree' without a root. In my prior
> > thinking, the root node is always present, because if it isn't, you dont
> > have a tree. 
> 
> I don't have a problem conceiving of a tree without a root.  The empty
> tree is meant to represent nothing, and I find it hard to conceive of
> nothing having a root.

I disagree - the empty tree represents *an empty tree*, not nothing. Say
we have an empty tree '/tmp/foo'. That directory exists. If /tmp/foo
does not exist, we dont even have a tree at all.

> The effort in nested trees is toward making root as un-special as
> possible.  It's just a directory that doesn't have any parents.  And
> until you init, that directory has no id, so you shouldn't pretend it did.

So before you init we dont even have an empty tree, we've got nothing.

> >>> I realise this is different to what you have done - so I'd like to know
> >>> what things it would impact negatively.
> >> Well, I think it means a bit more special casing for operations that
> >> compare trees.  diff / status -r 0..1 shouldn't show deletion of the
> >> tree root.  (They don't show an add of the tree root right now, but I
> >> think that's at least plausible, even if we decide not to.)
> > 
> > So, if iter_entries yields the root, we have a choice of special casing
> > the change of root id value, or special casing the addition of a root
> > node. I'm not sure which is nicer..
> 
> I think that representing a change in root id value would mean another
> level of indirection, and I would strongly oppose that.
> 
> Representing it as a delete+add would be possible, but if we must
> special-case delete+add, it's better to just special-case add.

I dont think what I'm proposing adds a *new* special case at all. (I'm
not arguing that it is a special case, just that its not a new one).
Existing trees have a ROOT_ID root node id. They will want to change
that ROOT_ID to be a unique id, if they want to be nestable. And they'll
want merges of this to Do The Right Thing with files in /. This is
exactly the same special case as assigning a unique root to the first
commit if the empty working tree starts with ROOT_ID.

> >> If we do a merge of unrelated trees, and BASE has a TREE_ROOT for a
> >> root, and OTHER has UNIQUE_ROOT-asdf for a root, and THIS has TREE_ROOT
> >> for a root, the merge will attempt to delete TREE_ROOT.  It won't
> >> succeed of course, but it will produce a conflict.  Preventing that
> >> conflict would require special-casing.
> > 
> > Well, I think there is a general-special-case for handling directory
> > nodes that is different to handling file nodes, for merge. Which we
> > haven't implemented yet. The point of this general-special case is to
> > make merging between trees with different directory ids nicer - merging
> > the contents rather than forcibly keeping them separate.
> 
> I don't think we can conclude anything about the contents of
> directories, based on their filenames, anymore than we could with files.
>  Some directory names are common.  Others are rare.  Some appear
> multiple times in a source tree.

If we compare both file-id and filename, we can do so I think, for some
very common cases. We may want it to be able to be 'turned on' with a
flag if its not considered robust enough to be on by default.

> Say we are merging the shelf plugin into bzrtools.  Both contain 'test'
> directories.
> 
> Say bzrtools is
> .
> ./test
> 
> and shelf is also
> .
> ./test
> 
> The desired output is
> .
> ./test
> ./shelf
> ./shelf/test
> 
> By your proposal, we would wind up with the shelf tests intermixed with
> the bzrtools tests.  We would also be unable to fix the situation,
> because one of the 'test' file ids would be lost.

Well heres I would like to see that work:
$ bzr merge --force SHELFURL
... some output ...
$ bzr st
... realise that ./test is incorrectly mingled
$ bzr revert
$ bzr merge --merge-into=shelf SHELFURL
... some output ...
$ bzr st
... shows the desired output ...

> > I dont see the
> > root node needing root-specific-special casing if this is done.
> 
> The handling you describe only handles duplicate adds.  But the merge
> scenario I describe has a spurious tree-root deletion, and this doesn't
> handle that.

I think these are different use cases - my description was not intended
to handle joining of trees at roots. Heres a use case I have in mind:

user 1 does a tailor conversion of $PROJ to bzr
user 2 does a tailor conversion of $PROJ to bzr

now user 1 wants to merge from user 2.

There are a number of things we need to implement for this to be doable
- but please dont let that distract us :).

During this merge, the directories will have identical paths, and its
here that merging the content is IMO the right *default* behaviour.
Remembering that the user will have had to do --force or some such to
make it merge at all.



> > 
> > Well, I want it for consistency, to avoid special cases, and to allow
> > the tree interface to be understandable.
> 
> I don't believe you will achieve that.  I think this will produce more
> special cases, because we'll have to deal with a delete/add pair,
> instead of just an add.

We could implement fileid aliases first. Though I'd rather not. I do
think that handling delete+add here is easy though: in terms of
snapshots if we change the root id and add a file, we will see:
OLD:
ROOT-ID
ROOT-ID/foo
ROOT-ID/bar

NEW:
UNIQUE-ROOT/
UNIQUE-ROOT/foo
UNIQUE-ROOT/bar
UNIQUE-ROOT/gam

Now, a merge that covers OLD-NEW into a tree with ROOT-ID and a fourth
file 'quux' will see:
foo is reparented - no problem
bar is reparented - no problem
gam is new - no problem
quux is not deleted, but its parent is deleted, and replaced with a new
node at the same path.

so for handling quux, this is one of those things we still dont do
*really well* - handling tree shape conflicts in the nicest possible
way. (We're a lot better than a lot of systems, dont get me wrong). I
think handling quux here would be done nicely be:
 - mark quux as being conflicted
 - put quux on disk inside the new directory (we have no home for it as
its parent was removed, so this is no worse than any other path).

> > For me, changing the id of the root is a lot cleaner than adding one,
> > but thats because I think a tree needs a root to be a tree. (In fact,
> > having Tree and the root be separate objects does not make all that much
> > sense to me, but thats a different discussion).
> 
> I don't think I understand this concept of having a root be a tree.  If
> the tree == the root, then two different trees must have different roots.

Well we identify a node by path + id. If the root node and the tree are
synonymous, then two trees which have the same root id are completely
possible. (because the path of the root is '/' always, and the id is
able to be the same). The physical location of the tree - the base, or
url - would be a separate attribute on the tree.

> >> I'm just concerned that's Roberts request is just pushing the bugs
> >> further down. Because once we have real roots, then even an empty
> >> working tree won't match EmptyTree. 
> > 
> > I dont see why it wont match :).
> 
> Because TREE_ROOT != MY_UNIQUE_TREE_ROOT-asdflkjh
>
> > In fact, my tree interface tests will
> > assure that it is. I think that an empty working tree *may* be different
> > to an empty tree, once its had a root id assigned to it, but only after
> > that.
> 
> But root ids are assigned when working trees are initialized.


I get that. I dont see *why* we have to assign the root id at 'init'
time, rather than at first commit time. If we assign the root during
commit, then its entirely possible to have an empty revision tree and an
empty working tree match entirely.

Rob


-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060725/2c29e2d2/attachment.pgp