Re: [Gnu-arch-users] Re: [BUG] FEATURE PLANS: "perfect" summary deltas

[Tom Lord]

    > From: Aaron Bentley <address@hidden>

    > [complaints about the builder algorithm I sketched for 
    >  summary deltas.]

Ok, you're right, I oversimplified.

The builder should use the framework I hope you've built for
backbuilding.   Specifically, it should use multiple calls to 
ancestor-tracing recursive functions to trace out a few different
possible build paths then, from among those that actually work, choose
the shortest one that is consistent with the demands of the user's 
revision libraries.

You named two tracing algorithms:

  1. Backwards from the closest same-version descendent we have.

  2. Backwards to the closest ancestor we have.

And of course there's also cacherevs to terminate those traces.

The general way to write the trace-gathering algorithm should
be something like this:

   { 

      forwards-starter = the revision i want to build;

      backwards-starter = the nearest namespace-descendent i have
                          of that;

      summary-starter = the corresponding summary revision;

      paths-in-progress = the set of traces {forwards-starter, 
                                            backwards-starter, 
                                            summary-starter};

      winning-paths = the empty set;

      while (paths-in-progress is not the empty set)
      {
        remaining-paths-in-progress = the empty set;

        t = pick one trace from paths-in-progress;

        for each way of continuing t, bringing it closer to 
            the revision we want
          {
            make t' which is that way of extending t

            if t' reaches the goal, add it to winning-paths
            otherwise, add it to remaining-paths-in-progress
          }

        paths-in-progress = remaining-paths-in-progress;
      }

      use the "best" of winning-paths;
    }


Your code should be able to generalize to that easily and _that_,
unlike my earlier mistake, will provide what I promised greek0.


    > (Also, note that building backwards using a summary delta has the
    > interesting property that you must *add* a patchlog so that
    > reverse-applying the changeset works.  Good thing the patchlogs can be 
    > retrived separately.)

Yup.

    > > (Another reason is that it's deterministic and
    > > predictable, and hence a reliable tool.)

    > Here's an alternative deterministic approach:
    > Take both the build paths (from step 4. above).  For each of them:

    > 1. find all the deltas whose START-REVISION and END-REVSISION are in the 
    > path.
    > 2. select the delta with the largest revision ordinal.
    > 3. delete all revisions in the path from START-REVISION to END-REVISION, 
    > and replace with the delta
    > 4. repeat until no deltas have both START-REVISION and END-REVISION in 
    > the path

    > This will always improve performance.  It deterministic and simple, and 
    > scales O(n) with the number of deltas.  It fits nicely with the 
    > backbuilder's design.

    > I haven't sorted out the best way to use external deltas, but I think a 
    > similar approach could apply (probably as a first step).  The tricky bit 
    > is determining when to use an external delta whose START-REVISION isn't 
    > in a revlib.

I like the way mine generalizes better.  It's got that step of

        for each way of continuing [the path] t

whereas your approach would handle _only_ summary deltas.

Plus I still don't agree that adding a new free-form subdir for
whatever deltas people care to add is really all that useful an idea.
Setting parameters on my-style of summary deltas can always get you
close to the best you could do with aribtrary deltas and with less
fuss and fewer unanswered questions.   Arbitrary deltas are
flexability that nobody really needs.

-t