deltas.texi

linux subdivision ying gai ke yi le ba

@node Deltas
@chapter Deltas

Subversion uses three kinds of deltas:

@itemize @bullet
@item
A @b{@dfn{tree delta}} describes the difference between two arbitrary
directory trees, the way a traditional patch describes the difference
between two files.  For example, the delta between directories A and B
could be applied to A, to produce B.

Tree deltas can also carry ancestry information, indicating how the
files in one tree are related to files in the other tree.  And deltas
can describe changes to file meta-information, like permission bits,
creation dates, and so on.  The repository and working copy use deltas
to communicate changes.

@item
A @b{@dfn{text delta}} describes changes to a string of bytes, such as the
contents of a file.  It is analogous to traditional patch format, except
that it works equally well on binary and text files, and is not
invertible (because context and deleted data are not recorded).

@item
A @b{@dfn{property delta}} describes changes to a list of named
properties (@pxref{Properties}).
@end itemize

The term @dfn{delta} without qualification generally means a tree delta,
unless some other meaning is clear from context.

In the examples below, deltas will be described in XML, which happens
to be Subversion's (now mostly defunct) import/export patch format.
However, note that deltas are an abstract data structure, of which the
XML format is merely one representation.  Later, we will describe
other representations: for example, there is a serialized
representation (useful for streaming protocols, among other things),
and a db-style representation, used for repository storage.  The
various representations of a given delta are (in theory, anyway)
perfectly isomorphic to one another, since they describe the same
underlying structure.

@menu
* Text Deltas::                 
* Property Deltas::             
* Tree Deltas::                 
* Postfix Text Deltas::                     
* Serializing Deltas via the "Editor" Interface::
@end menu


@c -----------------------------------------------------------------------
@node Text Deltas
@section Text Deltas

A text delta describes the difference between two strings of bytes, the
@dfn{source} string and the @dfn{target} string.  Given a source string
and a target string, we can compute a text delta; given a source string
and a delta, we can reconstruct the target string.  However, note that
deltas are not invertible: you cannot always reconstruct the source
string given the target string and delta.

The standard Unix ``diff'' format is one possible representation for
text deltas; however, diffs are not ideal for internal use by a revision
control system, for several reasons:
@itemize @bullet
@item
Diffs are line-oriented, which makes them human-readable, but sometimes
makes them perform poorly on binary files.
@item
Diffs represent a series of replacements, exchanging selected ranges of
the old text with new text; again, this is easy for humans to read, but
it is more expensive to compute and less compact than some alternatives.
@end itemize

Instead, Subversion uses the VDelta binary-diffing algorithm, as
described in @cite{Hunt, J. J., Vo, K.-P., and Tichy, W. F.  An
empirical study of delta algorithms.  Lecture Notes in Computer Science
1167 (July 1996), 49-66.}  Currently, the output of this algorithm is
stored in a custom data format called @dfn{svndiff}, invented by Greg
Hudson <@email{ghudson@@mit.edu}>, a Subversion developer.

The concrete form of a text delta is a well-formed XML element, having
the following form:
@example
<text-delta>@var{data}</text-delta>
@end example
Here, @var{data} is the raw svndiff data, encoded in the MIME Base64
format.

@c -----------------------------------------------------------------------
@node Property Deltas
@section Property Deltas

A property delta describes changes to a property list, of the sort
associated with files, directories, and directory entries, and revision
numbers (@pxref{Properties}).  A property delta can record creating,
deleting, and changing the text of any number of properties.

A property delta is an unordered set of name/change pairs.  No two
pairs within a given property delta have the same name.  A pair's name
indicates the property affected, and the change indicates what happens
to its value.  There are two kinds of changes:
@table @code
@item set @var{value}
Change the value of the named property to the byte string @var{value}.
If there is no property with the given name, one is added to the
property list.
@item delete
Remove the named property from the property list.
@end table

At the moment, the @code{set} command can either create or change a
property value.  However, this simplification means that the server
cannot distinguish between a client which believes it is creating a
value afresh, and a client which believes it is changing the value of an
existing property.  It may simplify conflict detection to divide
@code{set} into two separate @code{add} and @code{change} operations.

In the future, we may add a @code{text-delta} change, which specifies a
change to an existing property's value as a text delta.  This would give
us a compact way to describe small changes to large property values.

The concrete form of a property delta is a well-formed XML element,
having the following form:
@example
<property-delta>@var{change}@dots{}</property-delta>
@end example
Each @var{change} in a property delta has one of the following forms:
@example
<set name='@var{name}'>@var{value}</set>
<delete name='@var{name}'/>
@end example
The @var{name} attribute of a @code{set} or @code{delete} element gives
the name of the property to change.  The @var{value} of a @code{set}
element gives the new value of the property.

If either the property name or the property value contains the
characters @samp{&}, @samp{<}, or @samp{'}, they should be replaced with
the sequences @samp{&#38}, @samp{&#60}, or @samp{&#39}, respectively.


@c -----------------------------------------------------------------------
@node Tree Deltas
@section Tree Deltas

A tree delta describes changes between two directory trees, the
@dfn{source tree} and the @dfn{target tree}.  Tree deltas can describe
copies, renames, and deletions of files and directories, changes to file
contents, and changes to property lists.  A tree delta can also carry
information about how the files in the target tree are derived from the
files in the source tree, if this information is available.

The format for tree deltas described here is easy to compute from a
Subversion working directory, and easy to apply to a Subversion
repository.  Furthermore, the size of a tree delta in this format is
independent of the commands used to produce the target tree --- it
depends only on the degree of difference between the source and target
trees.

A tree delta is interpreted in the context of three parameters:
@itemize @bullet
@item
@var{source-root}, the name of the directory to which this complete
tree delta applies,
@item
@var{revision}, indicating a particular revision of @dots{}
@item
@var{source-dir}, which is a directory in the source tree that we are
currently modifying to yield @dots{}
@item
@dots{} @dfn{target-dir} --- the directory we're constructing.
@end itemize
When we start interpreting a tree delta, @var{source-root},
@var{source-dir}, and @var{target-dir} are all equal.  As we walk the
tree delta, @var{target-dir} walks the tree we are constructing, and
@var{source-dir} walks the corresponding portion of the source tree,
which we use as the original.  @var{Source-root} remains constant as we
walk the delta; we may use it to choose new source trees.

A tree delta is a list of changes of the form
@example
<tree-delta>@var{change}@dots{}</tree-delta>
@end example
which describe how to edit the contents of @var{source-dir} to yield
@var{target-dir}.  There are three kinds of changes:
@table @code

@item <delete name='@var{name}'/>
@var{Source-dir} has an entry named @var{name}, which is not present in
@var{target-dir}.

@item <add name='@var{name}'>@var{content}</add>
@var{target-dir} has an entry named @var{name}, which is not present in
@var{source-dir}; @var{content} describes the file or directory to which
the new directory entry refers.

@item <open name='@var{name}'>@var{content}</open>
Both @var{source-dir} and @var{target-dir} have an entry named
@var{name}, which has changed; @var{content} describes the new file or
directory.

@end table
Any entries in @var{source-dir} whose names aren't mentioned are assumed
to appear unchanged in @var{target-dir}.  Thus, an empty
@code{tree-delta} element indicates that @var{target-dir} is identical
to @var{source-dir}.

In the change descriptions above, each @var{content} takes one of the
following forms:
@table @code

@item <file @var{ancestor}>@var{prop-delta} @var{text-delta}</file>
The given @var{target-dir} entry refers to a file, @var{f}.
@var{Ancestor} indicates which file in the source tree @var{f} is
derived from, if any.

@var{Prop-delta} is a property delta describing how @var{f}'s properties
differ from that ancestor; it may be omitted, indicating that the
properties are unchanged.

@var{Text-delta} is a text delta describing how to construct @var{f}
from that ancestor; it may also be omitted, indicating that @var{f}'s
text is identical to its ancestor's.


@item <file @var{ancestor}/>
An abbreviation for @code{<file @var{ancestor}></file>} --- a file
element with no property or text delta, thus describing a file identical
to its ancestor.


@item <directory @var{ancestor}>@var{prop-delta} @var{tree-delta}</directory>
The given @var{target-dir} entry refers to a subdirectory, @var{sub}.
@var{Ancestor} indicates which directory in the source tree @var{sub} is
derived from, if any.

@var{Prop-delta} is a property delta describing how @var{sub}'s
properties differ from that ancestor; it may be omitted, indicating that
the properties are unchanged.

@var{Tree-delta} describes how to construct @var{sub} from that
ancestor; it may be omitted, indicating that the directory is identical
to its ancestor.  @var{Tree-delta} should be interpreted with a new
@var{target-dir} of @file{@var{target-dir}/@var{name}}.

Since @var{tree-delta} is itself a complete tree delta structure, tree
deltas are themselves trees, whose structure is a subgraph of the target
tree.


@item <directory @var{ancestor}/>
An abbreviation for @code{<directory @var{ancestor}></directory>} --- a
directory element with no property or tree delta, thus describing a
directory identical to its ancestor.

@end table

The @var{content} of a @code{add} or @code{open} tag may also contain
a property delta, describing changes to the properties of that
@emph{directory entry}.

In the @code{file} and @code{directory} elements described above, each
@var{ancestor} has one of the following forms:
@table @code

@item ancestor='@var{path}'
The ancestor of the new or changed file or directory is
@file{@var{source-root}/@var{path}}, in @var{revision}.  When this
appears as an attribute of a @code{file} element, the element's text
delta should be applied to @file{@var{source-root}/@var{path}}.  When
this appears as an attribute of a @code{directory} element,
@file{@var{source-root}/@var{path}} should be the new @var{source-dir}
for interpreting that element's tree delta.

@item new='true'
This indicates that the file or directory has no ancestor in the source
tree.  When followed by a @var{text-delta}, that delta should be applied
to the empty file to yield the new text; when followed by a
@var{tree-delta}, that delta should be evaluated as if @var{source-dir}
were an imaginary empty directory.

@item @var{nothing}
If neither an @code{ancestor} nor a @code{new} attribute is given, this
is an abbreviation for @code{ancestor='@var{source-dir}/@var{name}'},
with the same revision number.  This makes the common case --- files or
directories modified in place --- more compact.

@end table

If the @var{ancestor} spec is not @code{new='true'}, it may also contain
the text @code{revision='@var{rev}'}, indicating a new value for
@var{revision}, in which we should find the ancestor.

If a filename or path appearing as a @var{name} or @var{path} in the
description above contains the characters @samp{&}, @samp{<}, or
@samp{'}, they should be replaced with the sequences @samp{&#38;},
@samp{&#60;}, or @samp{&#39;}, respectively.

Suppose we have the following source tree:
@example
/dir1/file1
      file2
      dir2/file3
           file4
      dir3/file5
           file6
@end example
  
If we edit the contents of @file{/dir1/file1}, we can describe the
effect on the tree with the following tree delta, to be applied to the
root:
@example
<tree-delta>
  <open name='dir1'>
    <directory>
      <tree-delta>
        <open name='file1'>
          <file>@var{text-delta}</file>
        </open>
      </tree-delta>
    </directory>
  </open>
</tree-delta>
@end example
The outer @code{tree-delta} element describes the changes made to the root
directory.  Within the root directory, there are changes in @file{dir1},
described by the nested @code{tree-delta}.  Within @file{/dir1}, there are
changes in @file{file1}, described by the @var{text-delta}.

If we had edited both @file{/dir1/file1} and @file{/dir1/file2}, then
there would simply be two @code{open} elements in the inner
@code{tree-delta}.

As another example, starting from the same source tree, suppose we
rename @file{/dir1/file1} to @file{/dir1/file8}:
@example
<tree-delta>
  <open name='dir1'>
    <directory>
      <tree-delta>
        <delete name='file1'/>
        <add name='file8'>
          <file ancestor='/dir1/file1'/>
        </add>
      </tree-delta>
    </directory>
  </open>
</tree-delta>
@end example
As above, the inner @code{tdelta} describes how @file{/dir1} has
changed: the entry for @file{/dir1/file1} has disappeared, but there is
a new entry, @file{/dir1/file8}, which is derived from and textually
identical to @file{/dir1/file1} in the source directory.  This is just
an indirect way of describing the rename.

Why is it necessary to be so indirect?  Consider the delta representing
the result of:
@enumerate
@item
renaming @file{/dir1/file1} to @file{/dir1/tmp},
@item
renaming @file{/dir1/file2} to @file{/dir1/file1}, and
@item
renaming @file{/dir1/tmp} to @file{/dir1/file2}
@end enumerate
(in other words, exchanging @file{file1} and @file{file2}):
@example
<tree-delta>