[darcs-users] Patches are immutable

Juliusz Chroboczek jch at pps.jussieu.fr
Sun Oct 24 16:03:57 UTC 2004


                        Patches Are Immutable
                                  or
                     Rerecord Considered Harmful

  Abstract: we argue that patches in Darcs should be immutable.  We
  further argue that people who want to make patches mutable are
  looking for the wrong solution to a real problem.

1. Background: referential transparency

Any person discovering Darcs is amazed at its simplicity -- all the
features of Arch with the simplicity of RCS.  Some people might think
this is simply due to a well-designed user-interface; they don't
understand that a simple user-interface is only possible with a
well-designed data structure.

The basic data structure in Darcs is a repository, a collection of
patches.  Patches are identified by a triple (a, t, n), where a is the
author of the patch, t is its time, and n is the patch name; we will
call such a triple a /patch identity/.

  (Side note: arguably, with 20/20 hindsight, better notions of patch
   identity could be devised -- one could think of using a random
   identity, or a hash of the patch contents, as in Monotone.  But that
   is not the way Darcs works.)

In Darcs, two patches that have the same identity are the same patch.
This property is usually known as /referential transparency/: if two
things are the same, one can be substituted for the other.

2. Mutable patches break Darcs

The assumption that patches are referentially transparent runs
throughout Darcs.  Fundamentally, this is the property that makes it
safe to use unsafePerformIO; this is the property that makes pull and
push work, and this is the property that allows us to cooperate with a
web proxy when fetching patches over HTTP.  It is also the property
that allows the ``siblings'' code that I'm in the process of imple-
menting, and the property behind the ``cheap branches'' improvement
that was recently proposed on this list.

Making patches mutable breaks all of the above.  You should not
propose making patches mutable until you understand every single use
of unsafePerformIO in the Darcs code, you understand HTTP/1.1 caching
semantics, you understand sibling repositories and you understand
cheap branches.  Even then, you should not propose making patches
mutable.

There is a lot of confusion about the rerecord command in Darcs,
leading various people to propose renaming it or adding random
metadata to repositories to make it slightly more safe.  I believe
those people are losing their time: rerecord breaks the basic
assumptions in Darcs, which is what makes it fundamentally confusing.
The only solution is not to use rerecord.

3. But mistakes happen

Rewriting patches is the quick and dirty solution to a very real
problem: fixing a patch that contains a typo.  One might argue that
even then one should not rewrite history: mistakes are part of history.

Taking a less principled view, it is quite possible to implement the
/illusion/ of mutable patches without breaking Darcs.  At least two
ways of doing so have been proposed:

 (i) compound, or bundled patches.  A compound patch is a group of
     patches that are treated by the UI as a single patch.  It is
     impossible to get at the individual patches in a compound without 
     an explicit ``explode'' command.

(ii) subsumption of patches.  Allowing a patch to be marked as
     subsuming, or superseding, one or more previous patches.  Pulling 
     such a patch causes all the subsumed patches to be unpulled.

Some will say that this amounts to adding metadata; yes, but it adds
metadata *to patches* rather than to a repository, and hence fits in
the Darcs model -- that all data lives in (immutable) patches.

4. Conclusion

Patches are immutable.  Mutable patches break Darcs.

Rerecord should be deleted, or at least made not to appear in |darcs help|.

Don't fix the symptoms of the limitation in Darcs, fit the limitations
themselves.  Implement compound patches or implement patch subsumption,
but don't make patches mutable.

                                        Juliusz Chroboczek




More information about the darcs-users mailing list