Re: Algebraic manipulation of patches vs. dependencies

On Sat, Jun 24, 2006 at 04:54:38PM +0100, Mark Seaborn wrote:
> 
> I've been trying out Darcs recently, finding it useful, and trying to
> understand how it works.
> 
> What puzzles me is that Darcs does not store a dependency graph of all
> the patches in a repository.  Instead it keeps patches in a list, and
> manipulates the list algebraically, reordering patches that commute.
> When two patches modifying the same file are reordered, the line
> numbers they refer to must be rewritten.  In some cases, Darcs groups
> together patches that can be applied in parallel.
> 
> Is there any reason why Darcs doesn't go a step further by storing a
> full dependency tree?  This would have the advantage of being a
> canonical representation.  Patches' line numbers would not need to be
> rewritten according to where the patch appears in the sequence.  The
> line numbers of a patch could be given relative to the file contents
> defined by all the patches it depends on.

If we stored patches as a full dependency tree, then recording a new
change would be an O(N) process, where N is the number of patches in
the history.  That's a scary thought, to me anyways.  Similarly,
pulling a single change would also be an O(N) process in general,
since you'd have to do a merge in order to find out how to apply the
patch to the current file.
-- 
David Roundy