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

[Bug Goo]

Created as bug 146

On Sat May 29 05:58:14 2004, Tom Lord wrote:
> 
> 
> 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
> 
> 
> 
> _______________________________________________
> Gnu-arch-users mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/gnu-arch-users
> 
> GNU arch home page:
> http://savannah.gnu.org/projects/gnu-arch/
>