[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

RE: filesystem merge() behavior

From: Bill Tutt <rassilon_at_lyra.org>
Date: 2002-05-30 19:50:45 CEST

> From: cmpilato@collab.net [mailto:cmpilato@collab.net]
>
> "Bill Tutt" <rassilon@lyra.org> writes:
>
> > > LIST-FOLK: If you think we need to keep `svnadmin deltify'
around,
> > > you better let me know soon, 'cause she's about to disappear!
> > > `svnadmin undeltify' will stay, though (it scratches my itch).
> > >
> >
> > Killing it is fine by me. Die die die!
>
> ... as if *you* even needed to answer this particular request for
> opinion ... :-)
>
> > > > No, auto-merging should commit the predecessor nodes correctly.
> > >
> > > Oh...um...the merge code doesn't (any more) do any cloning
whatsoever.
> > > That code has been ripped out. Hm. Looks like I have some more
work
> > > to do. {grumble, mumble}
> > >
> >
> > Err. The case I mentioned to cause you to go into apoplexy is
covered
> > by:
> > For Every E not in Ancestor:
> > ....
> > /* E does not exist in target */
> > if (! t_entry)
> > {
> > /* target takes source */
> > if (! svn_fs__dag_check_mutable (target, txn_id))
> > return svn_error_createf
> > (SVN_ERR_FS_NOT_MUTABLE, 0, NULL, trail->pool,
> > "unexpected immutable node at \"%s\"", target_path);
> >
> > SVN_ERR (svn_fs__dag_set_entry
> > (target, s_entry->name, s_entry->id, txn_id,
trail));
> > }
> >
> > Having a mutable NodeRevision in target, should cause the right
thing to
> > happen here.
> >
> > For the case of the code that I think you were talking about. (logic
> > case 2 in your new code) There also isn't a problem, because merge
gets
> > invoked recursively, which creates mutable NodeRevisions.
>
> I'm either misunderstanding you, or you are misunderstanding the
> code. Let's repeat that example:
>

I'm misunderstanding the code.

> 1. cmpilato creates txn1 and makes a change to /foo/bar.
> 2. rassilon creates txn2 and makes a change to /foo/baz.
> 3. rassilon commits txn2
This creates revision 2.
> 4. cmpilato commits txn1
This creates revision 3.

>
> Now, I just reproduced this case, using gdb to halt cmpilato's commit
> at the call to svn_fs_commit_txn() until after a rassilon's commit was
> started and finished (so cmpilato got the first txn, but the second
> commit). Now, I'm looking at a db_dump of the `nodes' table, and I
> see exactly what *I* expected, but what I think *you* would not expect
> to see (sorry for being so dense about this).
>
> Please allow me to annotate, C-style:
>
> /* / in revision 0 */
> 0.0.0
> ((dir) 0 0 )
>
> /* / in revision 1 (in which I created /foo, /foo/bar, and
/foo/baz) */
> 0.0.1
> ((dir 5 0.0.0) 0 1 0)
>
> /* / in cmpilato's txn */
> 0.0.4
> ((dir 5 0.0.1) 0 1 5)
>
> /* / in rassilon's txn */
> 0.0.5
> ((dir 5 0.0.1) 0 1 8)
>
> /* /foo in revision 1 */
> 1.0.1
> ((dir) 0 1 1)
>
> /* /foo in cmpilato's txn */
> 1.0.4
> ((dir 5 1.0.1) 0 1 6)
>
> /* /foo in rassilon's txn */
> 1.0.5
> ((dir 5 1.0.1) 0 1 9)
>
> [...] /* bar's and baz's node revisions follow, but they don't
> really matter. */
>
> Now, while auto-merging allowed cmpilato's commit at all -- noting
> accurately that while /foo was now out of date, it certainly bore no
> conflicting changes -- pay attention to the predecessor IDs in those
> skels. cmpilato's /foo and rassilon's /foo both have a predecessor of
> the original revision 1 /foo. Am I correct in assuming that you think
> that cmpilato's /foo should have assumed a predecessor of rassilon's
> /foo during the merge process?
>

For a second lets pretend I am thinking that:
/foo in revision 2 (aka 1.0.5)'s predecessor node is correct.
/foo in revision 3 (aka 1.0.4)'s predecessor node should be 1.0.5.

The auto-merge performed on cmpilato's txn has the following (A, S, T)
data for /:
A for /: 0.0.1 with a predecessor of 0.0.0
S for /: 0.0.5 with a predecessor of 0.0.1
T for /: 0.0.4 with a predecessor of 0.0.1
We know the following facts:
A < S
A < T
As yet, S and T don't have an ordering to each other.

The condition for considering a recursive merge is:

A != S
AND
!(A == T
  OR (
      (A <= T && A.NodeID == T.NodeID && A is ordered wrt T)
      AND (T <= S && T.NodeID == S.NodeID && T is ordered wrt S))
AND
  !(S <= T && S.NodeID == T.NodeID && S is ordered wrt T)
AND A, S, and T are directories

For every ancestry check in the above condition I've inserted reminders
that NodeIDs remain constant, and that some ordering is known between
the objects under comparison.

In this case S <= T is certainly false because S and T don't have an
ordering yet. However, S <= T doesn't actually mean anything in our
problem domain. Source always comes after Target. This always confuses
me to no end, because negative definitions are just harder to follow
than positive definitions.

When you push the inverse operator down one level you get:
    (S.NodeID != T.NodeID
     OR !(S <= T
          AND S.NodeID == T.NodeID
          AND S is ordered wrt T))

If you push the NOT on the left hand side of the OR down into the
sub-expressions you get:
    (S.NodeID != T.NodeID
     OR (T < S && S.NodeID == T.NodeID && S is ordered wrt T)
         OR (S.NodeID != T.NodeID
             OR S is NOT ordered wrt T)
When we inverted the ancestry check I reinserted the implied
requirements for every ancestry check to help remind folks what
information we know in every sub-expression of the OR.

The duplicate NodeID checks cancel out, yielding:
(S.NodeID != T.NodeID
 OR ((T < S && S.NodeID == T.NodeID && S is ordered wrt T)
     OR S is not yet ordered wrt T)

After adding additional commentary to indicate how we're expecting the
NodeIDs to behave under each OR we get this:
(S.NodeID != T.NodeID
 OR ((T < S && S.NodeID == T.NodeID && S is ordered wrt T)
     OR (S.NodeID == T.NodeID
         AND S is not yet ordered wrt T)

Rewriting the above for clarity yields this:
(S.NodeID != T.NodeID
 OR (S.NodeID == T.NodeID
     AND ((T < S && S is ordered wrt T)
          OR S is not yet ordered wrt T)
Ok, this expression I can understand and follow.

The recursive merging then happens, and the recursive merge succeeds.

Now that merging has finished we can assign a real ordering to S and T

We just need to know when we need to do this. Fortunately, the
expression we ended up with above gives us that answer.

If (S.NodeID == T.NodeID
    AND S is not yet ordered wrt T)
Then
    Make T the successor of S by fiat since auto-merging just succeeded.
Otherwise
    We have no issue since a brand new NodeID would have no relavent
predecessor data that needs changing.

The old code only handled this when it was convenient to create a
successor using the old NodeRevisionID mechanism. Now that we have
chained predecessors, this problem is much simpler!

Did I make sense, I hope so...
Bill

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Sat Jun 1 14:36:42 2002

This is an archived mail posted to the Subversion Dev mailing list.