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

[Tom Lord]

Here's a plan for self-managing summary-deltas and cached revisions
with no changes to archive format (beyond adding "system branches")
and with simplifications to the revision builder.

Add a new command `tla summarize VERSION' which works as follows.
Suppose that VERSION is:

        proj--branch--1.0

`summarize' ensures the existence of:

        proj--branch+summary--1.0

and ensures that for every revision in proj--branch there is a
corresponding revision in proj--branch+summary.   

`summarize' ensures that every revision in the summarized branch,
a corresponding revision exists in the summary branch.  This
invarient is maintained:

        % tla get proj--branch--1.0 wd

yields exactly the same tree as:

        % tla get proj--branch+summary--1.0 wd
        % tla remove-log-version --dir wd \
              proj--branch+summary--1.0

`summarize' also creates cached revisions in the summary branch.

So, the question is: what exactly are the revisions in the +summary
branch and how should the revision-building code in tla use them?

For every summary branch there is a version variable, "summary-basis",
which is the name of some revision in the summarized branch.   At
revision R in the summary branch, the value of "summary-basis" is a
revsion name of some revision <= the patch level of R.

For example:

        the summary-basis of base-0 _must_ be the base-0 
        revision of the summarized branch.

        the summary basis of patch-34 _may_ be the patch-23
        revision of the summarized branch.

        the summary basis of patch-34 _may_ be the patch-34
        revision of the summarized branch.

        the summary basis of patch-34 _may_NOT_ be the patch-35
        revision of the summarized branch.

        the summary basis of version-0 _may_ be the patch-34
        revision of the summarized branch, provided such a
        revision exists

Let's define the idea of a "relative revision ordinal" within 
a version.

  relative_revision_ordinal (REV1, REV2) 
    := "the number N such that REV2 is the
        Nth revision following REV1"

For example,

  relative_revision_ordinal (patch-3, patch-5) == 2

Suppose that the basis of summary revison REV0 is BASIS.

And suppose that we now want to summarize REV1 which is 
the immediate succesor revision to REV0.

_NORMALLY_ (I'll state an exception below) there are two cases:

Let 

        K = relative_revision_ordinal (BASIS, REV1)

IF

        there exists a positive integer C s.t. 

              K = 2^C - 1

THEN

        summary revision REV1 is a "commit --basis" revision
        with BASIS as the "--basis" argument.  The changeset
        for this revision turns the BASIS tree into the REV1
        tree (plus a patch log entry for the summary branch).

OTHERWISE

        summary revision REV1 is a "commit --basis" revision
        where the "--basis" argument is the revision, SIMPLER, of the
        summarized version, such that:

          relative_revision_ordinal (BASIS, SIMPLER)

          ==

               2^(floor (log_2 (relative_revision_ordinal (BASIS, REV1))))
             - 1

ENDIF


Ignoring the exception I've promised to the preceding rules for a
moment, let's suppose that I _have_ a REV_HAVE revision of the 
summarized version and that I _want_ a REV_WANT revision of the 
summarized version.

Let's further suppose that the corresponding REV_HAVE and REV_WANT 
of the _summary_ version (the "+summary" version) both have the same
"Summary-basis:" header.  Call the basis revision named there, BASIS.

Then I can construct REV_WANT as follows:

LET

   wants_simpler := 2^(floor (log_2 (relative_revision_ordinal (BASIS, 
REV_WANT))))

   to_simpler := 2^(floor (log_2 (relative_revision_ordinal (BASIS, REV_WANT))))

IF wants_simpler == to_simpler

      reverse apply the changeset of the summary version's REV_WANT
      revision to REV_WANT

      forward apply the changeset of the summary version's REV_TO
      revision to that.

      remove-log-version the summary version

ELSE 

      reverse apply the changeset of the summary version's REV_WANT
      to REV_WANT

      reverse apply the changeset of the summary revision
      whose ordinal relative to BASIS is wants_simpler

      forward apply the changeset of the summary revision 
      whose ordinal relative to BASIS is to_simpler

      forward apply the changeset of the summary revision 
      REV_TO

      remove-log-version the summary version

ENDIF

That algorithm will build any revision from any other revision sharing
the same summary basis in at most 4 changeset applications.

The exception with summary branches concerns changes of summary basis:

If creating a new summary revision as described above would result
in a situation where following the construction algorithm described
above would fetch changesets from an archive whose total size exceed
the size of a cacherev of the new revision, then to create the new
summary revision, tag the summarized revision exactly and change the
basis to the newly committed revision.

In other words, the summary version is divided up into phases,
separated by cached revisions:


  (revisions explicitly named are cachereved):

  base-0  ......  patch-K ..... patch-N .... versionfix-X ....
      `----V----' `------v-----'`------V----'
        phase 0        phase 1      phase 2      ....

to build-by-patching, given an existing pristine tree, _within_ any
phase takes either 2 or 4 changeset applications.  To
build-by-patching _across_ phases can be accomplished by fetching the
cacherev at the beginning of the TO phase and building on that,
instead (at most two changeset applications).

-t