[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gnu-arch-users] [BUG] FEATURE PLANS: "perfect" summary deltas
From: |
Tom Lord |
Subject: |
[Gnu-arch-users] [BUG] FEATURE PLANS: "perfect" summary deltas |
Date: |
Fri, 28 May 2004 17:17:15 -0700 (PDT) |
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] [BUG] FEATURE PLANS: "perfect" summary deltas,
Tom Lord <=