Re: Algebraic manipulation of patches vs. dependencies

Zooko O'Whielacronx <zooko-F7hWHBaSm8MAvxtiuMwx3w@xxxxxxxxxxxxxxxx> wrote:

> 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).

Right.  You would cache annotated versions of the pristine copies of
the files.  The annotated versions would contain information similar
to what is produced by "cvs/svn/darcs annotate": Ranges of lines would
be associated with the patch that inserted those lines.  You would
also need to record deletions: Indexes between line ranges would be
marked with patches that had removed lines from that point to produce
this version of the file.

Here's what I have in mind:

The contents of a file would be specified by a set of non-conflicting
patches.

Suppose for example the first patch to insert into a file is p1, and it
produces the following annotated file:

  File {p1}:
    lines from p1:
  0   >int f()
  1   >{
  2   >  foo();
  3   >  bar();
  4   >  return 0;
  5   >}


With {p1} as the starting point, you record a patch p2, defined as:

  Patch p2 is defined as: from {p1} remove range 3..4

which gives the annotated file:

  File {p1,p2}:
    lines from p1:
  0   >int f()
  1   >{
  2   >  foo();
    lines were deleted by p2 at this point
    lines from p1:
  3   >  return 0;
  4   >}


If you then replace lines 2 and 3, the resulting patch will depend on
p2 as well as p1:

  Patch p3 is defined as: from {p1,p2} replace range 2..4 with:
    >  return 1;

giving the annotated file:

  File {p1,p2,p3}:
    lines from p1:
  0   >int f()
  1   >{
    lines from p3:
  2   >  return 1;
    lines from p1:
  3   >}


If you choose to edit the first line of {p1,p2,p3}, the resulting
patch only depends on p1:

  Patch p4 is defined as: from {p1} replace range 0..1 with:
    >int function()

{p1,p4} specifies a valid file, and so does {p1,p2,p3,p4}.

When representing {p1,p2,p3,p4}, an implementation only needs to store
{p3,p4}, because p1 and p2 are implied by the definitions of p3 and
p4, which list their dependencies.  The closure of the set under the
dependency relation gets back p1 and p2:
Closure{p3,p4} = {p1,p2,p3,p4}

Is this anything like what you had in mind, Zooko?

Cheers,
Mark