rcs.ms

早期freebsd实现

arrow
box "2.2"
arrow dashed
.ps +2
.PE
.ce 1
Figure 2.  A slender revision tree.
.sp 0
Now imagine a customer requesting a fix of
a problem in revision 1.3, although actual development has moved on
to release 2.  RCS does not permit an extra
revision to be spliced in between 1.3 and 2.1, since that would not reflect
the actual development history.  Instead, create a branch
at revision 1.3, and check in the fix on that branch.
The first branch starting at 1.3 has number 1.3.1, and
the revisions on that branch are numbered 1.3.1.1, 1.3.1.2, etc.
The double numbering is needed to allow for another
branch at 1.3, say 1.3.2.
Revisions on the second branch would be numbered
1.3.2.1, 1.3.2.2, and so on.
The following steps create
branch 1.3.1 and add revision 1.3.1.1:
.sp 0
.I
.nr VS 12p
.vs 12p
.TS
tab(%);
l l l.
     %co  \-r1.3  f.c% \*- check out revision 1.3
     %edit  f.c% \*- change it
     %ci  \-r1.3.1  f.c% \*- check it in on branch 1.3.1
.TE
.nr VS 18p
.vs 18p
.R
This sequence of commands transforms the tree of Figure 2 into
the one in Figure 3.
Note that it may be necessary to incorporate the differences
between 1.3 and 1.3.1.1
into a revision at level 2.  The operation \fIrcsmerge\fR automates this
process (see the Appendix).
.ne 7
.PS  4i
.ps -2
     box "1.1"
     arrow
     box "1.2"
     arrow
R13: box "1.3"
     arrow
R21: box "2.1"
     arrow
R22: box "2.2"
     arrow dashed
     line invis down from R21.s
RB1: box "1.3.1.1"
     arrow dashed right from RB1.e
     arrow from R13.s to RB1.w
.ps +2
.PE
.ce 1
Figure 3.  A revision tree with one side branch
.sp
.IP "\fIDistributed development and customer modifications\fR"
.sp 0
Assume a situation as in Figure 2, where revision 1.3 is in operation
at several customer sites,
while release 2 is in development.
Customer sites should use RCS to store the distributed software.
However, customer modifications should not be placed on the same branch
as the distributed source; instead, they should be placed on a side branch.
When the next software distribution arrives,
it should be appended to the trunk of
the customer's RCS file, and the customer
can then merge the local modifications back into the new release.
In the above example, a
customer's RCS file would contain the following tree, assuming
that the customer has received revision 1.3, added his local modifications
as revision 1.3.1.1, then received revision 2.4, and merged
2.4 and 1.3.1.1, resulting in 2.4.1.1.
.ne 7
.PS  4i
.ps -2
R13: box "1.3"
     line invis
R21: box invis
     line invis
R22: box invis
     line invis
R24: box "2.4"
     line invis
R25: box invis
     line invis
     arrow from R13.e to R24.w
     line invis down from R21.s
RB1: box "1.3.1.1"
     arrow from R13.s to RB1.w
     right
     line invis down from R25.s
RB2: box "2.4.1.1"
     arrow from R24.s to RB2.w
.ps +2
.PE
.ce 1
Figure 4.  A customer's revision tree with local modifications.
.sp 1
This approach is actually practiced in the CSNET project,
where several universities and a company cooperate
in developing a national computer network.
.IP "\fIParallel development\fR"
.sp 0
Sometimes it is desirable to explore an alternate design or
a different implementation technique in parallel with the
main line development.  Such development
should be carried out on a side branch.
The experimental changes may later be moved into the main line, or abandoned.
.IP "\fIConflicting updates\fR"
.sp 0
A common occurrence is that one programmer
has checked out a revision, but cannot complete the assignment
for some reason.  In the meantime, another person
must perform another modification
immediately.  In that case, the second person should check-out the same revision,
modify it, and check it in on a side branch, for later merging.
.PP
Every node in a revision tree consists of the following attributes:
a revision number, a check-in date and time, the author's identification,
a log entry, a state and the actual text.  All these attributes
are determined at the time the revision is checked in.
The state attribute indicates the status of a revision.
It is set automatically to `experimental' during check-in.
A revision can later be promoted to a higher status, for example
`stable' or `released'.  The set of states is user-defined.
.NH 2
Revisions are represented as deltas
.PP
For conserving space, RCS stores revisions in the form
of deltas, i.e., as differences between revisions.
The user interface completely hides this fact.
.PP
A delta is a sequence of edit commands that transforms one string
into another.  The deltas employed by RCS are line-based, which means
that the only edit commands allowed are insertion and deletion of lines.
If a single character in a line is changed, the
edit scripts consider the entire line changed.
The program \fIdiff\fR\u2\d
produces a small, line-based delta between pairs of text files.
A character-based edit script would take much longer to compute,
and would not be significantly shorter.
.PP
Using deltas is a classical space-time tradeoff: deltas reduce the
space consumed, but increase access time.
However, a version control tool should impose as little delay
as possible on programmers.
Excessive delays discourage the use of version controls,
or induce programmers to take shortcuts that compromise system integrity.
To gain reasonably fast access time for both editing and compiling,
RCS arranges deltas in the following way.
The most recent revision on the trunk is stored intact.
All other revisions on the trunk are stored as reverse deltas.
A reverse delta describes how to go backward in the development history:
it produces the desired revision if applied to the successor of that revision.
This implementation has the advantage
that extraction of the latest revision is a simple and fast copy
operation.
Adding a new revision to the trunk is also fast: \fIci\fR simply
adds the new revision intact, replaces the previous
revision with a reverse delta, and keeps the rest of the old deltas.
Thus, \fIci\fR requires the computation
of only one new delta.
.PP
Branches need special treatment.  The naive solution would be to
store complete copies for the tips of all branches.
Clearly, this approach would cost too much space.  Instead,
RCS uses \fIforward\fR deltas for branches.  Regenerating a revision
on a side branch proceeds as follows.  First, extract the latest revision
on the trunk; secondly, apply reverse deltas until the fork revision for
the branch is obtained; thirdly, apply forward deltas until the desired
branch revision is reached.  Figure 5 illustrates a tree with
one side branch.  Triangles pointing to the left and right represent
reverse and forward deltas, respectively.
.ne 8
.PS  4i
.ps -2
define BD X [line invis $1 right .5;
line up .3 then left .5 down .3 then right .5 down .3 then up .3] X

define FD X [line invis $1 right .5;
line left .5 down .3 then up .6 then right .5 down .3;] X

right
D11:    BD(" 1.1")
	arrow right from D11.e
D12:    BD(" 1.2")
	arrow  right from D12.e
D13:    BD(" 1.3")
	arrow  right from D13.e
D21:    BD(" 2.1")
	arrow  right from D21.e
D22:    box "2.2"
	line invis down from D21.s
F1:     FD("1.3.1.1 ")
	arrow from D13.se to F1.w
	arrow from F1.e right
	right
F2:     FD("1.3.1.2 ")
.ps +2
.PE
.ce 1
Figure 5.  A revision tree with reverse and forward deltas.
.sp 0
.PP
Although implementing fast check-out for the latest trunk revision,
this arrangement has the disadvantage that generation of other revisions
takes time proportional to the number of deltas applied.  For example,
regenerating the branch tip in Figure 5 requires application of five
deltas (including the initial one).  Since usage statistics show that
the latest trunk revision is the one that is retrieved in 95 per cent
of all cases (see the section on usage statistics), biasing check-out time
in favor of that revision results in significant savings.
However, careful implementation of the delta application process is
necessary to provide low retrieval overhead for other revisions, in
particular for branch tips.
.PP
There are several techniques for delta application.
The naive one is to pass each delta to a general-purpose text editor.
A prototype of RCS invoked the UNIX editor \fIed\fR both
for applying deltas and for expanding the identification markers.
Although easy to implement, performance was poor, owing to the
high start-up costs and excess generality of \fIed\fR.  An intermediate
version of RCS used a special-purpose, stream-oriented editor.
This technique reduced the cost of applying a delta to the cost of
checking out the latest trunk revision.  The reason for this behavior
is that each delta application involves a complete pass over
the preceding revision.
.PP
However, there is a much better algorithm.  Note that the deltas are
line oriented and that most of the work of a stream editor involves
copying unchanged lines from one revision to the next.  A faster
algorithm avoids unnecessary copying of character strings by using
a \fIpiece table\fR.
A piece table is a one-dimensional array, specifying how a given
revision is `pieced together' from lines in the RCS file.
Suppose piece table \fIPT\dr\u\fR represents revision \fIr\fR.
Then \fIPT\dr\u[i]\fR contains the starting position of line \fIi\fR
of revision \fIr\fR.
Application of the next delta transforms piece table \fIPT\dr\u\fR
into \fIPT\dr+1\u\fR.  For instance, a delete command removes a
series of entries from the piece table.  An insertion command inserts
new entries, moving the entries following the insertion point further down the
array.  The inserted entries point to the text lines in the delta.
Thus, no I/O is involved except for reading the delta itself.  When all
deltas have been applied to the piece table, a sequential pass
through the table looks up each line in the RCS file and copies it to
the output file, updating identification markers at the same time.
Of course, the RCS file must permit random access, since the copied
lines are scattered throughout that file.  Figure 6 illustrates an
RCS file with two revisions and the corresponding piece tables.
.ne 13
.sp 6
.ce 1
\fIFigure 6 is not available.\fP
.sp 5
.ce 1
Figure 6.  An RCS file and its piece tables
.sp 0
.PP
The piece table approach has the property that the time for applying a single
delta is roughly determined by the size of the delta, and not by the
size of the revision.  For example, if a delta is
10 per cent of the size of a revision, then applying it takes only
10 per cent of the time to generate the latest trunk revision.  (The stream
editor would take 100 per cent.)
.PP
There is an important alternative for representing deltas that affects
performance.  SCCS\u3\d,
a precursor of RCS, uses \fIinterleaved\fR deltas.
A file containing interleaved deltas is partitioned into blocks of lines.
Each block has a header that specifies to which revision(s) the block
belongs.  The blocks are sorted out in such a way that a single
pass over the file can pick up all the lines belonging to a given
revision.  Thus, the regeneration time for all revisions is the same:
all headers must be inspected, and the associated blocks either copied
or skipped.  As the number of revisions increases, the cost of retrieving
any revision is much higher than the cost of checking out the
latest trunk revision with reverse deltas.  A detailed comparison
of SCCS's interleaved deltas and RCS's reverse deltas can be found
in Reference 4.
This reference considers the version of RCS with the
stream editor only.  The piece table method improves performance
further, so that RCS is always faster than SCCS, except if 10
or more deltas are applied.
.PP
Additional speed-up for both delta methods can be obtained by caching
the most recently generated revision, as has been implemented in DSEE.\u5\d
With caching, access time to frequently used revisions can approach normal file
access time, at the cost of some additional space.
.NH
Locking: A Controversial Issue
.PP
The locking mechanism for RCS was difficult to design.
The problem and its solution are first presented in their `pure' form,
followed by a discussion of the complications
caused by `real-world' considerations.
.PP
RCS must prevent two or more persons from depositing competing changes of the
same revision.
Suppose two programmers check out revision 2.4 and
modify it.  Programmer A checks in a revision before programmer B\&.
Unfortunately, programmer B has not seen A's
changes, so the effect is that A's changes are covered up by B's deposit.
A's changes are not lost since all revisions
are saved, but they are confined to a single revision.\(dd
.FS \(dd
Note that this problem is entirely different from the atomicity problem.
Atomicity means that
concurrent update operations on the same RCS file cannot be permitted,
because that may result in inconsistent data.
Atomic updates are essential (and implemented in RCS),
but do not solve the conflict discussed here.
.FE
.PP
This conflict is prevented in RCS by locking.
Whenever someone intends to edit a revision (as opposed
to reading or compiling it), the revision should be checked out
and locked,
using the \fI\-l\fR option on \fIco\fR.  On subsequent check-in,
\fIci\fR tests the lock and then removes it.
At most one programmer at a time may
lock a particular revision, and only this programmer may check in
the succeeding revision.
Thus, while a revision is locked, it is the exclusive responsibility
of the locker.
.PP
An important maxim for software tools like RCS is that they must
not stand in the way of making progress with a project.
This consideration leads to several weakenings of the locking mechanism.
First of all, even if a revision is locked, it can
still be checked out.  This is necessary if other people
wish to compile or inspect the locked revision
while the next one is in preparation.  The only operations they
cannot do are to lock the revision or to check in the succeeding one.  Secondly,
check-in operations on other branches in the RCS file are still possible; the
locking of one revision does not affect any other revision.
Thirdly, revisions are occasionally locked for a long period of time
because a programmer is absent or otherwise unable to complete
the assignment.  If another programmer has to make a pressing change,
there are the following three alternatives for making progress:
a) find out who is holding the lock and ask that person to release it;
b) check out the locked revision, modify it, check it
in on a branch, and merge the changes later;
c) break the lock.  Breaking a lock leaves a highly visible
trace, namely an electronic mail message that is sent automatically to the
holder of the lock, recording the breaker and a commentary requested from him.
Thus, breaking locks is tolerated under certain circumstances,
but will not go unnoticed.
Experience has shown that the automatic mail message attaches a high enough
stigma to lock breaking,
such that programmers break locks only in real emergencies,
or when a co-worker resigns and leaves locked revisions behind.
.PP
If an RCS file is private, i.e., when a programmer owns an RCS file
and does not expect anyone else to perform check-in operations,
locking is an unnecessary nuisance.
In this case,
the `strict locking feature' discussed earlier may be disabled,
provided that file protection
is set such that only the owner may write the RCS file.
This has the effect that only the owner can check-in revisions,
and that no lock is needed for doing so.
.PP
As added protection,
each RCS file contains an access list that specifies the users
who may execute update operations.  If an access list is empty,
only normal UNIX file protection applies.  Thus, the access list is
useful for restricting the set of people who would otherwise have update
permission.  Just as with locking, the access list
has no effect on read-only operations such as \fIco\fR.  This approach
is consistent with the UNIX philosophy of openness, which contributes
to a productive software development environment.
.NH