Re: [Gnu-arch-users] Deconstructing Star-Merge

[Jason McCarty]

This is nice and thorough, but I'll engage in some nitpicking and
comments.

David Allouche wrote:
> === Patchlogs and Revisions ===
> 
> There is a relation of equivalence between Patchlogs and Revisions.
> 
> patchlogOf: Revision --> Patchlog
> revisionOf: PatchLog --> Revision
> 
> patchlogOf(R) = L <=> revisionOf(L) = R

I would be careful with wording here, as "relation of equivalence" could
be confused with "equivalence relation," which this isn't. To prevent
confusion with your other use of "<=>" I would call this an order-
preserving bijection, and use "R ~ L" to mean "R = revisionOf(L)"
(equivalently "L = patchlogOf(R)").

> === Versions ===
> 
> versionOf: Revision --> Version
> versionOf: Patchlog --> Version
> 
> R is a Revison, L a Patchlog
> If R <=> L, then versionOf(L) = versionOf(R)

If R ~ L, then versionOf(L) = versionOf(R)

> The logset of a Tree is the set of Pachlogs present in that Tree.
                                       ^
                                       t
> logIn: Patchlog, Tree --> Boolean
> Patchlog is in logSet(Tree
 ^Whether                   ) ?

> == Documented Algorithm ==
> [...]

Not that it matters, but s/RevisionOf/revisionOf/g

> MA1 = RevisionOf(max(logsFrom(FV, REF)
>                      inter logsFrom(FV, FROM) 
>                      inter logsFrom(FV, TREE)))
> 
> MA2 = RevisionOf(max(logsFrom(RV, REF)
>                      inter logsFrom(RV, FROM)))
> 
> LMIF = max({R in FV \ MA2 is in newPatches(R)})

This should be LMIF = max({R in FV \ patchlogOf(MA2) is in newPatches(R)})
since newPatches : Revision --> Set of Patchlogs.

> If MA1 and MA2 are undefined, then FAIL.
> 
> Elif MA1 is undefined, then ANCESTOR := MA2.
> 
> Elif MA2 is undefined, then ANCESTOR := MA1.
> 
> Elif LMIF < MA1, then ANCESTOR := MA1.
> 
> Elif MA1 < LMIF, then ANCESTOR := MA2.

Strictly reading the docs, this line should be
  Else ANCESTOR := MA2.

> Apply delta(ANCESTOR, FROM) to TREE.

If we call (NTREE, CONFLICTS) the output, then to use your own notation,
  (NTREE, CONFLICTS) = patch(diff(getTree(ANCESTOR), getTree(FROM)), TREE)

> == Implemented Algorithm ==
> [...]
> FV = versionOf(FROM)
> 
> MA1 = max(logsFrom(FV, FROM) inter logsFrom(FV, TREE))

So as implemented, MA1 is the wrong patchlog if MA1 is not in
logsFrom(FV, REF).

> HMFTIF = max(UNION of newPatchesFrom(REF, P)
>                    for P in logsFrom(FV, FROM))
> 
> If HMFTIF is in logSet(TREE), MA2 = HMFTIF 

This is just wacky. I agree it assumes far too much about the presence
of one patchlog implying the presence of another. Even if that
implication were true, the last line should then be
  If HMFTIF is in logSet(REF), MA2 = HMFTIF 

> Apply delta(ANCESTOR, FROM) to TREE.

Since ANCESTOR is a patchlog here, I would say
  (NTREE, CONFLICTS) = patch(diff(getTree(revisionOf(ANCESTOR)),
                                  getTree(FROM)), TREE)

> = Conclusion =
> 
> There seem to be shortcomings in the documentation as well as in the
> implementation.

Differentiating between SOME_VERSION and max(SOME_VERSION) in the docs
is probably beneficial, I agree.

I also think there's some tradeoffs here. As documented, the calculation
of LMIF needs to examine the patchlog of every revision in FV, even
though examining every log in logsFrom(FV, FROM) is probably good
enough, and doesn't require umpteen archive or revlib checks.

> There seems to be an assumption that for every Revision R which is not a
> continuation or an import, patchSet(R-1) is included in patchSet(R).

This makes kind of a mess. If MA2 is defined, then even though some
patchlog of FV must list MA2 as a new-patch, that patchlog may no longer
be present in FROM. But then again, this is a matter of examining the
tree's patchlogs versus the archive's. What does it mean for a user to
remove a patchlog without also removing the new-patches listed by that
patchlog?

I wonder which version, documented or implemented, is closer to the
ideal.

-- 
Jason McCarty <address@hidden>