[darcs-users] darcs conflicts/dependencies -- is patch theory the place to start?

[Owen Stephens]

Hi Anthony,

I think I've merged in hunks from several of your emails to ease replying:

On 10 September 2012 23:53, AntC <anthony_clayden at clear.net.nz> wrote:
> Thanks, yes I understand a repo is conceptually a *set* of patches, and
not a
> DAG [as KevinQ points out]. And yet ... by the time you've commuted a
patch
> round to the target of a pull, it might have morphed quite a bit. It has
the
> same 'moral effect' but is it the *same* patch??

Yes! Darcs modifies a patch's *effect*, when commuting, but its *identity*
stays the same. Therefore, you could do something like `darcs cha -p 'my
patch'` and then `darcs optimize --reorder` and different hunks if you
called
`darcs cha -p 'my patch'` again. (You might not, if no commutation was
done).

> Thanks for the ref. Aha! That's the first place I've seen discussion of
> duplicates (which is what my example is about).

Yep, Duplicates are something that the original Darcs patch theory didn't
have,
I believe they were introduced to handle the many "trivial" add-add
conflicts
that would be resolved manually by just "ignoring" one of the adds (which is
what a Duplicate essentially does).

Unfortunately, they're rather poorly understood/described, and their
interactions when commuting with conflicts are very non-trivial --- due to
that, the current implementation is buggy, and information gets lost, such
that
Darcs can't properly re-commute a successfully commutated pair (a property
of
patches is that if <A, B> commuted to <B', A'> then we should be able to
commute <B', A'> to obtain <A, B> again.

> So as an outsider trying to understand the theory:
> - There's lots of talk of conflicts/dependencies.
> - But it's all very abstract, very few examples,
> - and no distinction between duplicates vs hunk conflicts, etc.
> - Are there perhaps different sub-categories of conflicts?
> - Are some less intractable than others?

In order:
 - Yes.
 - Yes - but the key ideas can (with effort) be understood with a high level
         of abstraction. A user manual or UI-facing output on the other hand
         must give the user more information!
 - No - there is a distinction, at least internally (which as I've
described,
        does cause issues...)
 - Yes & No -

> It's not clear from what I've read (again apologies if I've not reached
the
> right places), that if a depended-upon patch is already pulled to the
target
> repo, that doesn't count as a conflict.

No it doesn't, because it is the *same* patch that is required by the
dependency. I can't dream up a nice analogy, but if you already "have" the
(exact) item you seek, you don't need to "get" it again.

Now, that *is* different to attempting to pull a different (in terms of
patch
ID) patch with the same (or "overlapping") change in which case you would
require a Conflictor/Duplicate.

> >> [snip]
> >> - At the point of 'sliding' past the Create towards the end of Fork B,
> >> - Detect it's the same patch and identical effect, so they 'cancel
out'.
>
> > Well, essentially, but it's done before any real commutation is
attempted.
>
> Thanks, "before commutation is attempted" is the bit I didn't understand.

Yeah, sorry. It's because the "sliding" as you say, is what I think you
mean as
commutation of patches to re-context them in terms of the other patches.

When deciding which patches to push Darcs can "filter" patches that you
already
have, just by looking at their name so no commutation may be required.
(I've blurred the situation a bit though, because there can easily be
patches
"under" a patch that you already have, which you would need to commute out,
in
order to pull)

> This is how I think of the sameness of patches, but is it too much of a
fairy
> story? ...
>
> Each primitive patch has:
> - an action -- create/delete/modify/move
> - a target or location -- directory for a file action, line num for a hunk
>                        -- a move has two locations, source and target
> - a content -- file name to create, text to remove/insert (so two
contents)
>             -- a move has null content

Yes! Here are the relevant datatypes from Darcs:
(
http://hub.darcs.net/darcs/darcs-reviewed/browse/src/Darcs/Patch/Prim/V1/Core.hs#43
)

data Prim wX wY where
    Move :: !FileName -> !FileName -> Prim wX wY
    DP :: !FileName -> !(DirPatchType wX wY) -> Prim wX wY
    FP :: !FileName -> !(FilePatchType wX wY) -> Prim wX wY
    ChangePref :: !String -> !String -> !String -> Prim wX wY

data FilePatchType wX wY = RmFile
                         | AddFile
                         | Hunk !Int [B.ByteString] [B.ByteString]
                         | TokReplace !String !String !String
                         | Binary B.ByteString B.ByteString
                         deriving (Eq, Ord)

data DirPatchType wX wY = RmDir
                        | AddDir
                        deriving (Eq, Ord)


> Inverting a primitive patch does one of:
> - either 'flips' the action -- create 'flips' to delete, etc
> - Xor 'flips' the locations -- as with inverting a move
> - Xor 'flips' the content -- flips text to insert/remove

Yes, I think. More code:

instance Invert Prim where
    invert (FP f RmFile)  = FP f AddFile
    invert (FP f AddFile)  = FP f RmFile
    invert (FP f (Hunk line old new))  = FP f $ Hunk line new old
    invert (FP f (TokReplace t o n)) = FP f $ TokReplace t n o
    invert (FP f (Binary o n)) = FP f $ Binary n o
    invert (DP d RmDir) = DP d AddDir
    invert (DP d AddDir) = DP d RmDir
    invert (Move f f') = Move f' f
    invert (ChangePref p f t) = ChangePref p t f

> Commuting two primitive patches (providing they don't conflict):
> - keeps the same action for each
> - possibly adjusts the location
> - keeps the same content(s)

Somethine like that, but I won't paste the code :-)
see:
(
http://hub.darcs.net/darcs/darcs-reviewed/browse/src/Darcs/Patch/Prim/V1/Commute.hs
)

> Does that thinking help understanding? Or does it confuse more?

Yes, certainly!

> Perhaps a file copy can't be fitted in to this model? So perhaps a copy
should
> be seen as non-primitive? I see that inverting and commuting file copies
is
> problematic(?)

Given a model that tracks file id/content separately you *can* have a copy
operation on files that is more powerful than plain renaming --- file
"names"
would become some sort of symlink to file "data". This is what the GSoC
work by
mornfall was aiming towards. Who knows, it'll probably form some sort of
basis
for a future version of Darcs...

Phew!

Cheers,
Owen.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20120911/1ca66db7/attachment.html>