Re: Algebraic manipulation of patches vs. dependencies

David Roundy wrote:
> 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.

I'm not sure this is correct, since the algorithm to determine 
dependencies can use cached information and knowledge about the kind of 
the patch.  For example, suppose the patch being recorded is a "hunk" 
patch which alters the contents of a file.  Suppose there is a table 
(already present when this algorithm begins) mapping each line of that 
file to the patch which has most recently touched that line.  Then the 
cost of determining the dependencies of the patch is simply a table 
lookup for each line of the hunk, which is less than O(N) (and also is 
plenty fast for practical purposes).

Note that this is has some similarities with Codeville...

Regards,

Zooko