deltas.texi

linux subdivision ying gai ke yi le ba

  <open name='dir1'>
    <directory>
      <tree-delta>
        <open name='file1'>
          <file ancestor='/dir1/file2'/>
        </open>
        <open name='file2'>
          <file ancestor='/dir1/file1'/>
        </open>
      </tree-delta>
    </directory>
  </open>
</tree-delta>
@end example
The indirectness allows the tree delta to capture an arbitrary
rearrangement without resorting to temporary filenames.

Another example, starting from the same source tree:
@enumerate
@item
rename @file{/dir1/dir2} to @file{/dir1/dir4},
@item
rename @file{/dir1/dir3} to @file{/dir1/dir2}, and
@item
move @file{file3} from @var{/dir1/dir4} to @var{/dir1/dir2}.
@end enumerate
Note that @file{file3}'s path has remained the same, even though the
directories around it have changed.  Here is the tree delta:
@example
<tree-delta>
  <open name='dir1'>
    <directory>
      <tree-delta>
        <open name='dir2'>
          <directory ancestor='/dir1/dir3'>
            <tree-delta>
              <add name='file3'>
                <file ancestor='/dir1/dir2/file3'/>
              </add>
            </tree-delta>
          </directory>
        </open>
        <delete name='dir3'/>
        <add name='dir4'>
          <directory ancestor='/dir1/dir2'>
            <tree-delta>
              <delete name='file3'/>
            </tree-delta>
          </directory>
        </add>
      </tree-delta>
    </directory>
  </open>
</tree-delta>
@end example
In other words:
@itemize @bullet
@item
@file{/dir1} has changed;
@item
the new directory @file{/dir1/dir2} is derived from the old
@file{/dir1/dir3}, and contains a new entry @file{file3}, derived from
the old @file{/dir1/dir2/file3};
@item
there is no longer any @file{/dir1/dir3}; and
@item
the new directory @file{/dir1/dir4} is derived from the old
@file{/dir1/dir2}, except that its entry for @file{file3} is now gone.
@end itemize

Some more possible maneuvers, left as exercises for the reader:
@itemize @bullet
@item
Delete @file{dir2}, and then create a file named @file{dir2}.
@item
Rename @file{/dir1/dir2} to @file{/dir1/dir4}; move @file{file2} into
@file{/dir1/dir4}; and move @file{file3} into @var{/dir1/dir3}.
@item
Move @file{dir2} into @file{dir3}, and move @file{dir3} into @file{/}.
@end itemize

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

It is sometimes useful to represent a set of changes to a tree without
providing text deltas in the middle of the stream.  Text deltas are
often large and expensive to compute, and tree deltas can be useful
without them.  For example, one can detect whether two changes might
conflict --- whether they change the same file, for example --- without
knowing exactly how the conflicting files changed.

For this reason, our XML representation of a tree delta allows the text
deltas to come @emph{after} the </tree-delta> closure.  This allows the
client to receive early notice of conflicts:  during a @code{svn commit}
command, the client sends a tree-delta to the server, which can check
for skeletal conflicts and reject the commit, before the client takes the
time to transmit the (possibly large) textual changes.  This potentially
saves quite a bit of network traffic.

In terms of XML, postfix text deltas are split into two parts.  The
first part appears "in-line" and contains a reference ID.  The second
part appears after the tree delta is complete.  Here's an example:

@example
 <tree-delta>
   <open name="foo.c">
      <file>
        <text-delta-ref id="123">
      </file>
   </open>
   <add name="bar.c">
      <file>
        <text-delta-ref id="456">
      </file>
    </add>
 </tree-delta>
 <text-delta id="123">@emph{data}</text-delta>
 <text-delta id="456">@emph{data}</text-delta>
@end example


@c ----------------------------------------------------------------------
@node Serializing Deltas via the "Editor" Interface
@section Serializing Deltas via the "Editor" Interface

The static XML forms above are useful as an import/export format, and as
a visualization aid, but we also need a way to express a delta as a
@emph{series of operations}, to implement directory tree diffing and
patching.  Subversion defines a standard set of such operations in the
vtable @code{svn_delta_edit_fns_t}, a set of function prototypes which
anyone may implement (see @file{svn_delta.h}).

Each function in an instance of @code{svn_delta_editor_t}
(colloquially known as an @dfn{editor}) implements some distinct subtask
of editing a directory tree.  In fact, if you compare the editor
function prototypes to the XML elements described previously, you'll
notice a fairly strict correspondence: there's one function for
replacing a directory, another function for replacing a file, one for
adding a directory, another for adding a file, a function for deleting,
and so on.

Although the editor interface was designed around the general idea of
making changes to a directory tree, a specific implementation's behavior
depends on its role.  For example, the versioning filesystem library
offers an editor that creates new revisions, while the working copy
library offers an editor that updates working copies.  And the network
layer offers an editor that turns editing calls into wire protocol,
which is then converted back into editing calls on the other side!  All
of these different tasks can share a single interface, because they are
all fundamentally about the same thing: expressing and applying
differences between directory trees.

Like the XML forms, a series of editor calls must follow certain nesting
conventions; these conventions are implicit in the interface, in that
some of the functions take arguments that can only be obtained from
previous calls to other editor functions.

Editors can best be understood by watching one work on a real directory
tree.  For example:

@c kff todo: fooo working here.

Suppose that the user has made a number of local changes to her working
copy and wants to commit them to the repository.  Let's represent her
changes with the same tree-delta from a previous example.  Notice that
she has also made textual modifications to @file{file3}; hence the
in-line @code{<text-delta>}:

@example
<tree-delta>
  <open name='dir1'>
    <directory>
      <tree-delta>
        <open name='dir2'>
          <directory ancestor='/dir1/dir3'>
            <tree-delta>
              <add name='file3'>
                <file ancestor='/dir1/dir2/file3'>
                  <text-delta>@emph{data}</text-delta>
                </file>
              </add>
            </tree-delta>
          </directory>
        </open>
        <delete name='dir3'/>
        <add name='dir4'>
          <directory ancestor='/dir1/dir2'>
            <tree-delta>
              <delete name='file3'/>
            </tree-delta>
          </directory>
        </add>
      </tree-delta>
    </directory>
  </open>
</tree-delta>
@end example

So how does the client send this information to the server?

In a nutshell: the tree-delta is @emph{streamed} over the network, as a
series of individual commands given in depth-first order.

Let's be more specific.  The server presents the client with an object
of type @code{struct svn_delta_edit_fns_t}, colloquially known as an
@dfn{editor}.  An editor is really just table of functions; each
function makes a change to a filesystem.  Agent A (who has a private
filesystem) presents an editor to agent B.  Agent B then calls the
editor's functions to change A's filesystem.  B is said to be
@dfn{driving} the editor.

As Karl Fogel likes to describe the process, if one thinks of the
tree-delta as a lion, the editor is a "hoop" that the lion jumps through
-- each portion of the lion being decomposed through time.

B cannot call the functions in any willy-nilly order; there are some
logical restrictions.  In particular, as B drives the editor, it
receives opaque data structures which represent directories and files.
It must use and pass these structures, known as @dfn{batons}, to make
further function calls.

As an example, let's watch how the client would transmit the above
tree-delta to the repository.  (The description below is slightly
simplified.  For exact interface details, see
@file{subversion/include/svn_delta.h}.)

[Note:  in the examples below, and throughout Subversion's code base,
you'll see references to 'baton' objects.  This is simply a project
convention, a name given to structures that define contexts for
functions.  Many APIs call these structures 'userdata'.  In
Subversion, we like the term 'baton', because it reminds us of one
function ``handing off'' context to another function.]

@enumerate

@item 
The repository hands an "editor" to the client.

@item
The client begins by calling

    @code{root_baton = editor->open_root();}

The client now has an opaque object, @dfn{root_baton}, which represents
the root of the repository's filesystem.

@item
@code{dir1_baton = editor->open_dir("dir1", root_baton);}

Notice that @emph{root_baton} gives the client free license to make any
changes it wants in the repository's root directory -- until, of course,
it calls @code{editor->close_dir(root_baton)}.

The first change made was a replacement of @file{dir1}.  In return, the
client now has a new opaque data structure that can be used to change
@file{dir1}.

@item
@code{dir2_baton = editor->open_dir("dir2", "/dir1/dir3", dir1_baton);}

The @emph{dir1_baton} is now used to open @file{dir2} with a
directory whose ancestor is @file{/dir1/dir3}.

@item
@code{file_baton = editor->add_file("file3", "/dir1/dir2/file3", dir2_baton);}

Edits are now made to @file{dir2} (using @emph{dir2_baton}).  In
particular, a new file is added to this directory whose ancestor is
@file{/dir1/dir2/file3}. 

@item
Now the text-delta associated with @emph{file_baton} needs to be
transmitted:

  @code{window_handler = editor->apply_textdelta(file_baton);}

Text-deltas themselves, for network efficiency, are streamed in
"chunks".  So instead of receiving a baton object, we now have a routine
that is able to receive any number of small "windows" of text-delta
data.

We won't go into the details of the @code{svn_txdelta_*} functions right
here;  but suffice it to say that these routines are used for sending
svndiff data to the @emph{window_handler} routine.

@item
@code{editor->close_file(file_baton);}

The client is done sending the file's text-delta, so it releases the
file baton.

@item
@code{editor->close_dir(dir2_baton));}

The client is done making changes to @file{dir2}, so it releases its
baton as well.

@item
The client isn't yet finished with @file{dir1}, however; it makes two
more edits:

  @code{editor->delete_item("dir3", dir1_baton);} @*
  @code{dir4_baton = editor->add_dir("dir4", "/dir1/dir2", dir1_baton);}

@emph{(The function's name is @code{delete_item} rather than
@code{delete} to avoid gratuitous incompatibility with C++, where
@code{delete} is a reserved keyword.)}

@item
Within the directory @file{dir4} (whose ancestry is @file{/dir1/dir2}),
the client removes a file:

  @code{editor->delete_item("file3", dir4_baton);}

@item
The client is now finished with both @file{dir4}, as well as its parent
@file{dir1}:

  @code{editor->close_dir(dir4_baton);} @*
  @code{editor->close_dir(dir1_baton);}

@item
The entire tree-delta is complete.  The repository knows this when the
root directory is closed:

  @code{editor->close_dir(root_baton);}

@end enumerate


Of course, at any point above, the repository may reject an edit.  If
this is the case, the client aborts the transmission and the repository
hasn't changed a bit.  (Thank goodness for transactions!)

Note, however, that this "editor interface" works in the other direction
as well.  When the repository wishes to update a client's working copy,
it is the @emph{client's} reponsibility to give a custom editor-object
to the server, and the @emph{server} is the editor-driver.

Here are the main advantages of this interface:

@itemize @bullet

@item
@emph{Consistency}.  Tree-deltas move across the network, in both
directions, using the same interface.

@item
@emph{Flexibility}.  Custom editor-implementations can be written to do
anything one might want;  the editor-driver has no idea what is
happening on the other side of the interface.  For example, an editor
might

@itemize @bullet
@item
Output XML that matches the tree-delta DTD above;
@item
Output human-readable descriptions of the edits taking place;
@item
Modify a filesystem
@end itemize

@end itemize

Whatever the case, it's easy to "swap" editors around, and make client
and server do new and interesting things.