[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Gnu-arch-users] [OT] Darcs data model [was: the state of the union]

From: Tom Lord
Subject: Re: [Gnu-arch-users] [OT] Darcs data model [was: the state of the union]
Date: Mon, 30 Aug 2004 11:55:06 -0700 (PDT)

    > From: Juliusz Chroboczek <address@hidden>

    > The basic idea behind darcs is that patches are only ordered when they
    > depend on each other.  Hence, if the patches A and B are committed
    > (``recorded'') to a darcs repository, they have no intrinsic ordering
    > -- the repository contains both A and B, or equivalently both B and A.

As you go on to mention, Darcs also had "variance adjustment".  I.e.,
let's suppose that B truly does depend on A (they modify overlapping
regions and A comes first).  Given a tree, I can make the tree:

        new_tree == B [A [orig_tree]]

Variance adjustment says that given that A and B I can produce A' and
B' such that:

        new_tree == A' [B' [orig_tree]]

where A' differs from A only in line numbers and in the contents of
source and context lines being modified (and similarly for B/B').

That non-overlapping patches commute is nothing more than the
observation that if A and B do not overlap then A' == B'.

All of that is a swell trick and all.  An un- or partially- ordered
set of patches isn't something arch currently has any use for but,
certainly, versions could be repurposed that way in an upwards
compatible way.  (It's not unlike our recently discussed idea of
"commit --base" versions.   A Darcs-style archive is like a subset of
that functionality, with some new merging commands mixed in.)

My issue with Darcs (and with varience adjustment generally) is that
it discards information the programmer put into a change in a wildly
hard to predict way.   I.e., even though varience adjustment the idea
is mechnically simple, varience adjustment as a way to modify source
code is a kind of "weird" idea:  it'll be even more surprising if it
works well for many purposes than was the discovery that
diff/patch-style patching works well for many purposes.

    > (Side note: darcs actually stores patches in a given order; however,
    > there are a number of operations that will randomly reorder commuting
    > patches.  Hence, you cannot rely on patches remaining in the order
    > they are in.)

That is the part of darcs where I stopped reading.   Not that that was
the part I found unconvincing -- but that that was the first part the
depended upon the part I found unconvincing.

    > On the other hand, this model significantly reduces conceptual load.

If wishes and "but"s were candy and nuts.....

    > The ``patch algebra and all that jazz'' is basically about two things.
    > First, when do patches commute, and how do you commute them
    > (i.e. given A and B, construct B' and A'); this part is fairly simple
    > and elegant.  

Textually, yes.   In terms of it being a kind of "editor command"
(which is what merge commands really are) --- it's at best a pretty
esoteric one, I think, and Darcs makes the mistake of deploying it
exclusively (e.g,. darcs lacks the other kinds of merging arch has) 
and, as you go on to say, in a way that resists controlling it:

    > Second, what to do when patches don't commute, but darcs
    > needs to commute them anyway -- something that happens when there is a
    > merge conflict; this part of the algorithm is messy, and I still do
    > not fully understand it.

    > Now my personal feeling is that while the notion of changeset used by
    > darcs is similar to the one used by Arch, the global data model is
    > fundamentally different, which is why I don't understand Tom's claim
    > that darcs is a subset of Arch.

Hopefully now you do.   One could add varience adjustment to arch.
We will, regardless, be adding versions (development lines) consisting
entirely of "commit --base REVISION" commits.    Such a version, with
a varience-adjusting-based merge command, would behave essentially
isomorphically to a Darcs archive.   It's pretty easy to build on arch
-- nobody has yet be inspired to do it; possibly for good reason.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]