@need 3200

@node The Theory of Patches and Revisions
@appendix The Theory of Patches and Revisions

This appendix briefly explains "patch sets" and "revision control"
in the abstract.

@need 3200

@section The Theory of Patches

A @geindex patch set
@dfn{patch set} is an expression of the differences between two
revisions of a tree of files (usually, primarily, text files).  A
patch set tells you what files and directories have been added or
removed between the two revisions, what files have been renamed, what
files have changed.  For files added or removed, a patch set tells you
the complete contents of those files.  For files modified, a patch set
contains a description of the changes in the form of a @geindex context diff
@dfn{context diff}
(see the man page for @code{diff(1)}).  If a file is a symbolic link, and
the link target has changed, the patch set records that fact.  If a
regular file or directory is replaced by a symbolic link (or vice
versa) the patch records that fact.  Finally, if any files have had
their permissions or modification times changed -- a patch set records
that too.


Some notation will be helpful.  A shorter name for "patch set" is
@geindex delta
@dfn{delta}.  Let's suppose that @code{A} and @code{B} are two revisions of a source
tree.  Then:

@example
@group
        delta (A, B)
@end group
@group
@end group
@end example

@noindent
is the name for a patch set describing the differences between @code{A} and
@code{B}.


Anytime you make a series of changes to a tree, perhaps using shell
utilities and text editors, the entire series of changes can be
summarized as a single patch set.   In a sense, a patch set (or
"delta") is @geindex the fundamental editting operation
@dfn{the fundamental editting operation}, in terms of which
all others, and all combinations of others, can be described.


You can @geindex apply a patch
@dfn{apply a patch} -- which means to make the changes it
describes.  In our notation:

@example
@group
        delta (A, B) [A] == B
@end group
@group
@end group
@end example

@noindent
says "the patch set describing the differences between A and B, when
applied to A, gives B".  A patch set can also be applied "in
reverse":

@example
@group
        delta (A, B) @{B@} == A
@end group
@group
@end group
@end example

"the delta from A to B, applied in reverse to B, gives A".


A patch set can also be applied (or reverse-applied) to a tree which
is not the same as either @code{A} or @code{B}.  For example, suppose that we
have a tree @code{A_prime} which is similar to @code{A}, but has some slight
differences.  Then:

@example
@group
        delta (A, B) [A_prime] ~== B_prime
@end group
@group
@end group
@end example

@noindent
where @code{~==} means "approximately equals".  When a patch set is
applied to a tree which is not one of the trees used to compute the
patch set, the edits might or might not go well.  For example, if the
patch set wants to modify a file @code{F}, but @code{A_prime} doesn't contain
@code{F}, the patch can't be applied perfectly.  Similarly, if the patch
set wants to modify @code{F}, but the version of @code{F} in @code{A_prime} is
already very different from the version in @code{A}, then those edits can't
be done automatically.


Nevertheless, for the kinds of changes people typically make to trees
of source code, approximately applied patch sets are very useful.
For example, suppose we start with tree A, and create two revisions
@code{B_one} and @code{B_two}.  Then:

@example
@group
        delta (A, B_one) [B_two] ~== delta (A, B_two) [B_one]
@end group
@group
@end group
@end example

To make that more concrete: if programmer Alice makes a set of changes
to give us @code{B_one}, and programmer Bob makes a set of changes to give
us @code{B_two}, then the patch sets between A and those two revisions of
@code{B} give us a way to get @code{B_three} -- a tree that contains @emph{both}
Alice's and Bob's changes.   Even when a patch set can't be perfectly
applied in that way, it can often be applied to do "80%" of the
work, making it much easier to finish merging the two sets of changes
by hand.


Incidently, patch sets have a useful algebraic property if we think of
them as functions that can be composed.  Using the notation @code{F o G} to
mean "the function F composed with the function G":

@example
@group
        For all trees, A, B, and C:
@end group
@group
@end group
@end example
@example
@group
        delta (B, C) o delta (A, B) == delta (A, C)
@end group
@group
@end group
@end example

@noindent
so to build @code{C} from @code{A}, we can use:

@example
@group
        delta (A, C) [ A ] == C
@end group
@group
@end group
@end example

@noindent
but that is the same as:

@example
@group
        (delta (B, C) o delta (A, B)) [ A ] == C
@end group
@group
@end group
@end example

@noindent
or, in other words:

@example
@group
        delta (B, C) [ delta (A, B) [ A ]] == C
@end group
@group
@end group
@end example

The algebraic property suggests that if I want to apply:

@example
@group
        delta (B, C) o delta (A, B)
@end group
@group
@end group
@end example

I can save time by instead applying:

@example
@group
        delta (A, C)
@end group
@group
@end group
@end example

@noindent
and if I want to have a record of all three:

@example
@group
        delta (A, B)
        delta (B, C)
        delta (A, C)
@end group
@group
@end group
@end example

I can save space by storing only:

@example
@group
        delta (A, B)
        delta (B, C)
@end group
@group
@end group
@end example

And if we're applying patch sets to trees that might need to be
touched up by hand, and I want to apply @code{delta (A, C)}, then I have a
choice between applying:

@example
@group
        delta (A, C)
@end group
@group
@end group
@end example

@noindent
and have just one, possibly large set of errors to clean-up by hand,
or applying:

@example
@group
        delta (A, B) then delta (B, C)
@end group
@group
@end group
@end example

@noindent
and having two, but possibly smaller sets of errors to clean-up by
hand.


Patch sets have many uses, but three important ones are:


@strong{Compression} One use is @emph{compression}.  If @code{A} and @code{B} are large
trees, and the differences between them small, then the patch set
between them will be much smaller than either tree.  You can save disk
space by not storing both @code{A} and @code{B}, but instead, storing only @code{A}
(or only @code{B}) along with @code{delta (A, B)}.  That makes patch sets an
ideal form for space-efficient archival of multiple revisions of a
tree.


Similarly, if someone has downloaded a copy of @code{A} (or @code{B}) and they
want a copy of @code{B} (or @code{A}), they can save download time and bandwidth
by downloading only @code{delta (A, B)}.  That makes patch sets a good way
to distribute multiple revisions of a tree.


@strong{Inspection} Another use for patch sets is @emph{inspection}.  If a patch
set is stored in a human-readable format, it provides a useful way to
quickly see precisely what has changed between two revisions of a
tree.  For example, a patch set is handy for reviewing the changes
made by programmers to a large source tree.


@strong{Combining Separate Efforts} For some kinds of trees, patch sets are
good at merging (combining) changes made by people working separately
(as in the example of Alice and Bob, above).  This is especially true
of program source code.  That makes patch sets a very handy tool for
making a team of programmers more effective -- allowing the work
separately up to a point, then combine their efforts by creating and
applying patch sets.




@need 3200

@section The Theory of Revisions

Suppose that we start with a tree, @code{A0}, and make a set of changes
resulting in the tree @code{A1}:

@example
@group
        A0
        A1
@end group
@group
@end group
@end example

We can repeat that process several times:

@example
@group
        A0
        A1
        A2
        A3
        ...
@end group
@group
@end group
@end example

Each instance of the tree is called a @geindex revision
@dfn{revision}.  Between each
revision and its successor, we can compute a patch set:

@example
@group
        delta (A0,A1) [A0] == A1
        delta (A1,A2) [A1] == A2
        delta (A2,A3) [A2] == A3
        ...
@end group
@group
@end group
@end example

Something we can usefully do is create an @geindex archive
@dfn{archive} of revisions.  We
might store the first tree verbatim, and every successive tree as a
delta:

@example
@group
        A0: "complete copy of tree"
        A1: delta (A0,A1)
        A2: delta (A1,A2)
        A3: delta (A2,A3)
        ...
@end group
@group
@end group
@end example

If we want to retrieve an @code{An}, we start with @code{A0} and apply the first
@code{n} deltas:

@example
@group
        delta (An-1, An) [delta (An-2, An-1) [....[A0]...]] = An
@end group
@group
@end group
@end example

@noindent
or, making our notation more concise:

@example
@group
        An [ An-1 [ An-2 [ ... [A0] ...]]] = An
@end group
@group
@end group
@end example

Each revision in a series like this is called a @geindex patch level
@dfn{patch level}.  The
entire series is called a @geindex development path
@dfn{development path}.


At any point along the way, we might make a copy of some @code{An}, and
start a new development path.  For example, we might copy @code{A2} to
form @code{B0}:

@example
@group
        A0
        A1
        A2 ----------------> B0
        A3                   B1
        ...                  B2
                             ...
@end group
@group
@end group
@end example

When we have multiple, related development paths, each is called a
@geindex branch
@dfn{branch}.  The tree we copied to start a new branch (e.g. @code{A2}) is
called a @geindex branch point
@dfn{branch point}.


If we're building an archive, we can store @code{B0} as a pointer to the
@code{A0} development path, and every successive revision of the @code{B0}
path as an ordinary delta:

@example
@group
        A0                      B0: "equal to A2"
        A1: delta (A0,A1)       B1: delta (B0, B1)
        A2: delta (A1,A2)       B2: delta (B1, B2)
        A3: delta (A2,A3)       B3: delta (B2, B3)
        ...                     ...
@end group
@group
@end group
@end example

To make all this more concrete, imagine that the @code{A0} development path
is successive revisions of a program we're working on.  Alice wants to
add a very complicated feature.  Rather than make many small changes
to the @code{A0} development path, she makes a branch, the @code{B0} development
path -- and works on the complicated feature there.  Each new revision
of the @code{B0} branch is a small step on the way to the complicated
feature.


Eventually, Alice is done with the feature -- but meanwhile, the @code{A0}
development path has added several changes of its own.  What we'd
like to do next is to make a revision of the tree that has both sets of
changes -- from both development paths.

@example
@group
        A0                      B0: "equal to A2"
        A1: delta (A0,A1)       B1: delta (B0, B1)
        A2: delta (A1,A2)       B2: delta (B1, B2)
        A3: delta (A2,A3)       B3: delta (B2, B3)
        A4: delta (A3,A4)       B4: delta (B3, B4)
@end group
@group
@end group
@end example
@example
@group
              How can we make revision A5, which
               includes all the changes made on
                        both branches?
@end group
@group
@end group
@end example

The "theory of patches" gives us several possible solutions.  


One solution is to make this tree:

@example
@group
        B4 [ B3 [ B2 [ B1 [ A4 ]]]]
@end group
@group
@end group
@end example

That solution is called @geindex replaying
@dfn{replaying} the patches from the @code{B0}
branch against the @code{A0} branch.


That @emph{might} work reasonably, but patch set @code{B1} wasn't formed from
@code{A4} -- it was formed from @code{B0} which is the same as @code{A2}.  So when we
apply @code{B1} to @code{A4}, there might be problems that have to be resolved
"by hand".  The same will happen again when we apply @code{B2}, @code{B3}, and
@code{B4}.   In some situations, the risk and complexity of doing all that
work by hand is worth it -- but not in other situations.  What other
options do we have?


Another solution is to make this tree:

@example
@group
        A4 [ A3 [ B4 ] ]
@end group
@group
@end group
@end example

That solution is also replaying: replaying the patches from the @code{A0}
branch against the @code{B0} branch.  The same kind of problem
might occur (having to fix things up by hand), but in this case, we're
only applying two patches instead of four -- so this might be a
simpler solution.


Here's a third solution:

@example
@group
        delta (A2, B4) [A4]
@end group
@group
@end group
@end example

That solution is based on the fact that:

@example
@group
        B0 == A2
@end group
@group
@end group
@end example

@noindent
and the algebraic property that:

@example
@group
        B4 o B3 o B2 o B1 == delta (B0, B4)
@end group
@group
@end group
@end example

That solution is called @geindex updating
@dfn{updating} the @code{B0} development path with
respect to the @code{A0} path.  The difference between "replaying" and
"updating" is a little bit subtle.  When we "replay" from another
development path, that means that we take all patches we're missing
from that other path, and apply them in order.  When we "update"from
another development path, that means we take the latest revision on
that other path, and apply to it a delta between the branch point and
our own most-recent revision.


Applying the patch during an update certainly can fail to work
perfectly -- it might require fixing up by-hand.  On the other hand,
an update only ever applies one patch; often, therefore, the amount of
by-hand repairs is minimized.  "Nine times out of ten," updating is
the preferred technique for joining two previously branched revisions.


There are other, more obscure solutions too.  To choose one
arbitrarilly, we might try building:

@example
@group
        B4 [ A3 [ B2 [ A4 [ B1 [ B3 [ A2 ]]]]]]
@end group
@group
@end group
@end example

A bizarre solution like that is so rare it doesn't really have name --
but "one time in ten thousand" -- it's the solution that works best.


No matter what solution we choose, if we store the resulting revision
back on the @code{B0} path, we'll wind up with:

@example
@group
        A0                      B0: "equal to A2"
        A1: delta (A0,A1)       B1: delta (B0, B1)
        A2: delta (A1,A2)       B2: delta (B1, B2)
        A3: delta (A2,A3)       B3: delta (B2, B3)
        A4: delta (A3,A4)       B4: delta (B3, B4)
                                B5: delta (B4, B5) "has changes A3, A4"
@end group
@group
@end group
@end example

We can store that same revision back on the @code{A0} development path:

@example
@group
        A0                      B0: "equal to A2"
        A1: delta (A0,A1)       B1: delta (B0, B1)
        A2: delta (A1,A2)       B2: delta (B1, B2)
        A3: delta (A2,A3)       B3: delta (B2, B3)
        A4: delta (A3,A4)       B4: delta (B3, B4)
        A5: delta (A5, A4) ==   B5: delta (B4, B5) "has changes A3, A4"
@end group
@group
@end group
@end example

@code{A5} and @code{B5} are called a @geindex merge point
@dfn{merge point}.  For all practical purposes,
a merge point is also a branch point -- since, using the example, @code{B5}
and @code{A5} are equal, just the the two revisions of the original branch
point (@code{A2} and @code{B0}) were equal.  If additional development happens
on the two branches, we no longer have to worry about merging all
changes since @code{A2} and @code{B0}; we can instead just merge only the
changes since @code{A5} and @code{B5}.




@need 3200

@section What is a Revision Control System?

So what is a revision control system?


A revision control system is a set of tools for computing and applying
patch sets, for archiving patch sets, for distributing patch sets, and
for helping to merge changes on the basis of patch sets.


A revision control system has to come up with a reasonable way of
naming and cataloging revisions.  It has to be able to represent
branch points and help with merges.  When merges occur, a good
revision control system should help figure out what patches to apply
to which revisions in order to minimize hand-editting.







