- Copy stable/10 (r259064) to releng/10.0 as part of the

[FreeBSD/releng/10.0.git] / contrib / subversion / subversion / libsvn_fs_base / notes / structure

Subversion on Berkeley DB                                    -*- text -*-

There are many different ways to implement the Subversion filesystem
interface.  You could implement it directly using ordinary POSIX
filesystem operations; you could build it using an SQL server as a
back end; you could build it on RCS; and so on.

This implementation of the Subversion filesystem interface is built on
top of Berkeley DB (http://www.sleepycat.com).  Berkeley DB supports
transactions and recoverability, making it well-suited for Subversion.


\f
Nodes and Node Revisions

In a Subversion filesystem, a `node' corresponds roughly to an
`inode' in a Unix filesystem:

   * A node is either a file or a directory.

   * A node's contents change over time.

   * When you change a node's contents, it's still the same node; it's
     just been changed.  So a node's identity isn't bound to a specific
     set of contents.

   * If you rename a node, it's still the same node, just under a
     different name.  So a node's identity isn't bound to a particular
     filename.

A `node revision' refers to a node's contents at a specific point in
time.  Changing a node's contents always creates a new revision of that
node.  Once created, a node revision's contents never change.

When we create a node, its initial contents are the initial revision of
the node.  As users make changes to the node over time, we create new
revisions of that same node.  When a user commits a change that deletes
a file from the filesystem, we don't delete the node, or any revision
of it --- those stick around to allow us to recreate prior revisions of
the filesystem.  Instead, we just remove the reference to the node
from the directory.


\f
ID's

Within the database, we refer to nodes and node revisions using a
string of three unique identifiers (the "node ID", the "copy ID", and
the "txn ID"), separated by periods.

    node_revision_id ::= node_id '.' copy_id '.' txn_id

The node ID is unique to a particular node in the filesystem across
all of revision history.  That is, two node revisions who share
revision history (perhaps because they are different revisions of the
same node, or because one is a copy of the other, e.g.) have the same
node ID, whereas two node revisions who have no common revision
history will not have the same node ID.

The copy ID is a key into the `copies' table (see `Copies' below), and
identifies that a given node revision, or one of its ancestors,
resulted from a unique filesystem copy operation.

The txn ID is just an identifier that is unique to a single filesystem
commit.  All node revisions created as part of a commit share this txn
ID (which, incidentally, gets its name from the fact that this id is
the same id used as the primary key of Subversion transactions; see
`Transactions' below).

A directory entry identifies the file or subdirectory it refers to
using a node revision ID --- not a node ID.  This means that a change
to a file far down in a directory hierarchy requires the parent
directory of the changed node to be updated, to hold the new node
revision ID.  Now, since that parent directory has changed, its parent
needs to be updated, and so on to the root.  We call this process
"bubble-up".

If a particular subtree was unaffected by a given commit, the node
revision ID that appears in its parent will be unchanged.  When
doing an update, we can notice this, and ignore that entire
subtree.  This makes it efficient to find localized changes in
large trees.


\f
A Word About Keys

Some of the Subversion database tables use base-36 numbers as their
keys.  Some debate exists about whether the use of base-36 (as opposed
to, say, regular decimal values) is either necessary or good.  It is
outside the scope of this document to make a claim for or against this
usage.  As such, the reader will please note that for the majority of
the document, the use of the term "number" when referring to keys of
database tables should be interpreted to mean "a monotonically
increasing unique key whose order with respect to other keys in the
table is irrelevant".  :-)

To determine the actual type currently in use for the keys of a given
table, you are invited to check out the "Appendix: Filesystem
structure summary" section of this document.


\f
NODE-REVISION: how we represent a node revision

We represent a given revision of a file or directory node using a list
skel (see include/private/svn_skel.h for an explanation of skels).
A node revision skel has the form:

    (HEADER PROP-KEY KIND-SPECIFIC ...)

where HEADER is a header skel, whose structure is common to all nodes,
PROP-KEY is the key of the representation that contains this node's
properties list, and the KIND-SPECIFIC elements carry data dependent
on what kind of node this is --- file, directory, etc.

HEADER has the form:

    (KIND CREATED-PATH [PRED-ID [PRED-COUNT [HAS-MERGEINFO MERGEINFO-COUNT]]])

where:

   * KIND indicates what sort of node this is.  It must be one of the
     following:
       - "file", indicating that the node is a file (see FILE below).
       - "dir", indicating that the node is a directory (see DIR below).

   * CREATED-PATH is the canonicalized absolute filesystem path at
     which this node was created.

   * PRED-ID, if present, indicates the node revision which is the
     immediate ancestor of this node.

   * PRED-COUNT, if present, indicates the number of predecessors the
     node revision has (recursively).

   * HAS-MERGEINFO and MERGEINFO-COUNT, if present, indicate ...
     ### TODO

Note that a node cannot change its kind from one revision to the next.
A directory node is always a directory; a file node is always a file;
etc.  The fact that the node's kind is stored in each node revision,
rather than in some revision-independent place, might suggest that
it's possible for a node to change kinds from revision to revision, but
Subversion does not allow this.

PROP-KEY is a key into the `representations' table (see REPRESENTATIONS 
below), whose value is a representation pointing to a string 
(see `strings' table) that is a PROPLIST skel.

The KIND-SPECIFIC portions are discussed below.


\f
PROPLIST: a property list is a list skel of the form:

    (NAME1 VALUE1 NAME2 VALUE2 ...)

where each NAMEi is the name of a property, and VALUEi is the value of
the property named NAMEi.  Every valid property list has an even
number of elements.


\f
FILE: how files are represented.

If a NODE-REVISION's header's KIND is "file", then the node-revision
skel represents a file, and has the form:

    (HEADER PROP-KEY DATA-INFO [EDIT-DATA-KEY])

where

    DATA-INFO ::= DATA-KEY | (DATA-KEY DATA-KEY-UNIQID)

and DATA-KEY identifies the representation for the file's current
contents, and EDIT-DATA-KEY identifies the representation currently
available for receiving new contents for the file.

DATA-KEY-UNIQID ...
### TODO

See discussion of representations later.


\f
DIR: how directories are represented.

If the header's KIND is "dir", then the node-revision skel
represents a directory, and has the form:

    (HEADER PROP-KEY ENTRIES-KEY)

where ENTRIES-KEY identifies the representation for the directory's
entries list (see discussion of representations later).  An entries
list has the form

    (ENTRY ...)

where each entry is

    (NAME ID)

where:

   * NAME is the name of the directory entry, in UTF-8, and

   * ID is the ID of the node revision to which this entry refers


\f
REPRESENTATIONS: where and how Subversion stores your data.

Some parts of a node revision are essentially constant-length: for
example, the KIND field and the REV.  Other parts can have
arbitrarily varying length: property lists, file contents, and
directory entry lists.  This variable-length data is often similar
from one revision to the next, so Subversion stores just the deltas
between them, instead of successive fulltexts.

The HEADER portion of a node revision holds the constant-length stuff,
which is never deltified.  The rest of a node revision just points to
data stored outside the node revision proper.  This design makes the
repository code easier to maintain, because deltification and
undeltification are confined to a layer separate from node revisions,
and makes the code more efficient, because Subversion can retrieve
just the parts of a node it needs for a given operation.

Deltifiable data is stored in the `strings' table, as mediated by the
`representations' table.  Here's how it works:

The `strings' table stores only raw bytes.  A given string could be
any one of these:

   - a file's contents
   - a delta that reconstructs file contents, or part of a file's contents
   - a directory entry list skel
   - a delta that reconstructs a dir entry list skel, or part of same
   - a property list skel
   - a delta that reconstructs a property list skel, or part of same

There is no way to tell, from looking at a string, what kind of data
it is.  A directory entry list skel is indistinguishable from file
contents that just happen to look exactly like the unparsed form of a
directory entry list skel.  File contents that just happen to look
like svndiff data are indistinguishable from delta data.

The code is able to interpret a given string because Subversion

   a) knows whether to be looking for a property list or some
      kind-specific data,

   b) knows the `kind' of the node revision in question,

   c) always goes through the `representations' table to discover if
      any undeltification or other transformation is needed.

The `representations' table is an intermediary between node revisions
and strings.  Node revisions never refer directly into the `strings'
table; instead, they always refer into the `representations' table,
which knows whether a given string is a fulltext or a delta, and if it
is a delta, what it is a delta against.  That, combined with the
knowledge in (a) and (b) above, allows Subversion to retrieve the data
and parse it appropriately.  A representation has the form:

   (HEADER KIND-SPECIFIC)

where HEADER is

   (KIND TXN [MD5 [SHA1]])

The KIND is "fulltext" or "delta".  TXN is the txn ID for the txn in
which this representation was created.  MD5 is a checksum of the
representation's contents, that is, what the representation produces,
regardless of whether it is stored deltified or as fulltext.  (For
compatibility with older versions of Subversion, MD5 may be
absent, in which case the filesystem behaves as though the checksum is
there and is correct.) An additional kind of checksum, SHA1, is present
in newer formats, starting with version ...
### TODO

The TXN also serves as a kind of mutability flag: if txn T tries to
change a representation's contents, but the rep's TXN is not T, then
something has gone horribly wrong and T should leave the rep alone
(and probably error).  Of course, "change a representation" here means
changing what the rep's consumer sees.  Switching a representation's
storage strategy, for example from fulltext to deltified, wouldn't
count as a change, since that wouldn't affect what the rep produces.

KIND-SPECIFIC varies considerably depending on the kind of
representation.  Here are the two forms currently recognized:

   (("fulltext" TXN [MD5 [SHA1]]) STRING-KEY)
       The data is at STRING-KEY in the `strings' table.

   (("delta" TXN [MD5 [SHA1]]) (OFFSET WINDOW) ...)
       Each OFFSET indicates the point in the fulltext that this
       element reconstructs, and WINDOW says how to reconstruct it:

       WINDOW ::= (DIFF SIZE REP-KEY [REP-OFFSET]) ;
       DIFF   ::= ("svndiff" VERSION STRING-KEY)

       Notice that a WINDOW holds only metadata.  REP-KEY says what
       the window should be applied against, or none if this is a
       self-compressed delta; SIZE says how much data this window
       reconstructs; VERSION says what version of the svndiff format
       is being used (currently only version 0 is supported); and
       STRING-KEY says which string contains the actual svndiff data
       (there is no diff data held directly in the representations
       table, of course).

       Note also that REP-KEY might refer to a representation that
       itself requires undeltification.  We use a delta combiner to
       combine all the deltas needed to reproduce the fulltext from
       some stored plaintext.

       Branko says this is what REP-OFFSET is for:
       > The offsets embedded in the svndiff are stored in a string;
       > these offsets would be in the representation. The point is that
       > you get all the information you need to select the appropriate
       > windows from the rep skel -- without touching a single
       > string. This means a bit more space used in the repository, but
       > lots less memory used on the server.

       We'll see if it turns out to be necessary.

In the future, there may be other representations, for example
indicating that the text is stored elsewhere in the database, or
perhaps in an ordinary Unix file.

Let's work through an example node revision:

   (("file" REV COUNT) PROP-KEY "2345")

The entry for key "2345" in `representations' is:

   (("delta" TXN CHECKSUM) (0 (("svndiff" 0 "1729") 65 "2343")))

and the entry for key "2343" in `representations' is:

   (("fulltext" TXN CHECKSUM) "1001")

while the entry for key "1729" in `strings' is:

   <some unprintable glob of svndiff data>

which, when applied to the fulltext at key "1001" in strings, results
in this new fulltext:

   "((some text) (that looks) (deceptively like) (directory entries))"

Et voila!  Subversion knew enough, via the `representations' and
`strings' tables, to undeltify and get that fulltext; and knew enough,
because of the node revision's "file" type, to interpret the result as
file contents, not as a directory entry list.

(Note that the `strings' table stores multiple DB values per key.
That is, although it's accurate to say there is one string per key,
the string may be divided into multiple consecutive blocks, all
sharing that key.  You use a Berkeley DB cursor to find the desired
value[s], when retrieving a particular offset+len in a string.)

Representations know nothing about ancestry -- the `representations'
table never refers to node revision id's, only to strings or to other
representations.  In other words, while the `nodes' table allows
recovery of ancestry information, the `representations' and `strings'
tables together handle deltification and undeltification
*independently* of ancestry.  At present, Subversion generally stores
the youngest strings in "fulltext" form, and older strings as "delta"s
against them (unless the delta would save no space compared to the
fulltext).  However, there's nothing magic about that particular
arrangement.  Other interesting alternatives:

   * We could store the N most recently accessed strings as fulltexts,
     letting access patterns determine the most appropriate
     representation for each revision.

   * We could occasionally store deltas against the N'th younger
     revision, storing larger jumps with a frequency inverse to the
     distance covered, yielding a tree-structured history.

Since the filesystem interface doesn't expose these details, we can
change the representation pretty much as we please to optimize
whatever parameter we care about --- storage size, speed, robustness,
etc.

Representations never share strings - every string is referred to by
exactly one representation.  This is so that when we change a
representation to a different form (e.g. during deltification), we can
delete the strings containing the old form, and know that we're not
messing up any other reps by doing so.


Further Notes On Deltifying:
----------------------------

When a representation is deltified, it is changed in place.
New strings are created containing the new delta, the representation
is changed to refer to the new strings, and the original (usually
fulltext) string or strings are deleted.

The node revisions referring to that representation will not be
changed; instead, the same rep key will now be associated with
different value.  That way, we get reader locking for free: if someone
is reading a file while Subversion is deltifying that file, one of the
two sides will get a DB_DEADLOCK and svn_fs__retry_txn() will retry.

### todo: add a note about cycle-checking here, too.


\f
The Berkeley DB "nodes" table

The database contains a table called "nodes", which is a btree indexed
by node revision ID's, mapping them onto REPRESENTATION skels.  Node 0
is always the root directory, and node revision ID 0.0.0 is always the
empty directory.  We use the value of the key 'next-key' to indicate
the next unused node ID.

Assuming that we store the most recent revision on every branch as
fulltext, and all other revisions as deltas, we can retrieve any node
revision by searching for the last revision of the node, and then
walking backwards to specific revision we desire, applying deltas as
we go.


\f
REVISION: filesystem revisions, and the Berkeley DB "revisions" table

We represent a filesystem revision using a skel of the form:

    ("revision" TXN)

where TXN is the key into the `transactions' table (see 'Transactions' below)
whose value is the transaction that was committed to create this revision.

The database contains a table called "revisions", which is a
record-number table mapping revision numbers onto REVISION skels.
Since Berkeley DB record numbers start with 1, whereas Subversion
filesystem revision numbers start at zero, revision V is stored as
record number V+1 in the `revisions' table.  Filesystem revision zero
always has node revision 0.0.0 as its root directory; that node
revision is guaranteed to be an empty directory.


\f
Transactions

Every transaction ends when it is either successfully committed, or
aborted.  We call a transaction which has been either committed or
aborted "finished", and one which hasn't "unfinished".  

Transactions are identified by unique numbers, called transaction
ID's.  Currently, transaction ID's are never reused, though this is
not mandated by the schema.  In the database, we always represent a
transaction ID in its shortest ASCII form.

The Berkeley DB `transactions' table records both unfinished and
committed transactions.  Every key in this table is a transaction ID.
Unfinished transactions have values that are skels of one of the
following forms:

   ("transaction" ROOT-ID BASE-ID PROPLIST COPIES)
   ("dead" ROOT-ID BASE-ID PROPLIST COPIES)

where:

   * ROOT-ID is the node revision ID of the transaction's root
     directory.  This is of the form 0.0.THIS-TXN-ID.

   * BASE-ID is the node revision ID of the root of the transaction's
     base revision.  This is of the form 0.0.BASE-TXN-ID - the base
     transaction is, of course, the transaction of the base revision.

   * PROPLIST is a skel giving the revision properties for the
     transaction.

   * COPIES contains a list of keys into the `copies' table,
     referencing all the filesystem copies created inside of this
     transaction.  If the transaction is aborted, these copies get
     removed from the `copies' table.

   * A "dead" transaction is one that has been requested to be
     destroyed, and should never, ever, be committed.

Committed transaction, however, have values that are skels of the form:

   ("committed" ROOT-ID REV PROPLIST COPIES)

where:

   * ROOT-ID is the node revision ID of the committed transaction's (or
     revision's) root node.

   * REV represents the revision that was created when the
     transaction was committed.

   * PROPLIST is a skel giving the revision properties for the
     committed transaction.

   * COPIES contains a list of keys into the `copies' table,
     referencing all the filesystem copies created by this committed
     transaction.  Nothing currently uses this information for
     committed transactions, but it could be useful in the future.

As the sole exception to the rule above, the `transactions' table
always has one entry whose key is `next-key', and whose value is the
lowest transaction ID that has never yet been used.  We use this entry
to allocate ID's for new transactions.

The `transactions' table is a btree, with no particular sort order.


\f
Changes

As modifications are made (files and dirs added or removed, text and
properties changed, etc.) on Subversion transaction trees, the
filesystem tracks the basic change made in the Berkeley DB `changes'
table.  

The `changes' table is a btree with Berkeley's "duplicate keys"
functionality (and with no particular sort order), and maps the
one-to-many relationship of a transaction ID to a "change" item.
Change items are skels of the form:

   ("change" PATH ID CHANGE-KIND TEXT-MOD PROP-MOD)

where:

   * PATH is the path that was operated on to enact this change.

   * ID is the node revision ID of the node changed.  The precise
     meaning varies based on the kind of the change:
      - "add" or "modify": a new node revision created in the current
        txn.
      - "delete": a node revision from a previous txn.
      - "replace": a replace operation actually acts on two node
        revisions, one being deleted, one being added.  Only the added
        node-revision ID is recorded in the `changes' table - this is
        a design flaw.
      - "reset": no node revision applies.  A zero atom is used as a
        placeholder.

   * CHANGE-KIND is one of the following:

     - "add"     : PATH/ID was added to the filesystem.
     - "delete"  : PATH/ID was removed from the filesystem.
     - "replace" : PATH/ID was removed, then re-added to the filesystem.
     - "modify"  : PATH/ID was otherwise modified.
     - "reset"   : Ignore any previous changes for PATH/ID in this txn.
                   This kind is no longer created by Subversion 1.3.0
                   and later, and can probably be removed at the next
                   schema bump.

   * TEXT-MOD is a bit specifying whether or not the contents of
     this node was modified.

   * PROP-MOD is a bit specifying whether or not the properties of
     this node where modified.

In order to fully describe the changes made to any given path as part
of a single transaction, one must read all the change items associated
with the transaction's ID, and "collapse" multiple entries that refer
to that path. 


\f
Copies

Each time a filesystem copy operation is performed, Subversion records
meta-data about that copy.  

Copies are identified by unique numbers called copy ID's.  Currently,
copy ID's are never reused, though this is not mandated by the schema.
In the database, we always represent a copy ID in its shortest ASCII
form.

The Berkeley DB `copies' table records all filesystem copies.  Every
key in this table is copy ID, and every value is a skel of one of the
following forms:

   ("copy" SRC-PATH SRC-TXN DST-NODE-ID)
   ("soft-copy" SRC-PATH SRC-TXN DST-NODE-ID)

where:

   * "copy" indicates an explicitly requested copy, and "soft-copy"
     indicates a node that was cloned internally as part of an
     explicitly requested copy of some parent directory. See the
     section "Copies and Copy IDs" in the file <fs-history> for
     details.

   * SRC-PATH and SRC-TXN are the canonicalized absolute path and
     transaction ID, respectively, of the source of the copy.

   * DST-NODE-ID represents the new node revision created as a result
     of the copy.

As the sole exception to the rule above, the `copies' table always has
one entry whose key is `next-key', and whose value is the lowest copy ID
that has never yet been used.  We use this entry to allocate new
copy ID's.

The `copies' table is a btree, with no particular sort order.


\f
Locks

When a caller locks a file -- reserving an exclusive right to modify
or delete it -- an lock object is created in a `locks' table.

The `locks' table is a btree whose key is a UUID string known as
a "lock-token", and whose value is a skel representing a lock.  The
fields in the skel mirror those of an svn_lock__t (see svn_types.h):

    ("lock" PATH TOKEN OWNER COMMENT XML-P CREATION-DATE EXPIRATION-DATE)

where:

   * PATH is the absolute filesystem path reserved by the lock.

   * TOKEN is the universally unique identifier of the lock, known
     as the lock-token.  This is the same as the row's key.

   * OWNER is the authenticated username that "owns" the lock.

   * COMMENT is a string describing the lock.  It may be empty, or it
     might describe the rationale for locking.

   * XML-P is a boolean (either 0 or 1) indicating whether the COMMENT
     field is wrapped in an XML tag.  (This is something only used by
     the DAV layer, for webdav interoperabliity.)

   * CREATION-DATE is a string representation of the date/time when
     the lock was created.  (see svn_time_to_cstring())

   * EXPIRATION-DATE is a string representation of the date/time when
     the lock will cease to be valid.  (see svn_time_to_cstring())

In addition to creating a lock in the `locks' table, a new row is
created in a `lock-tokens' table.  The `lock-tokens' table is a btree
whose key is an absolute path in the filesystem.  The value of each
key is a lock-token (which is a key into the `locks' table.)

To test if a path is locked, simply check if the path is a key in the
`lock-tokens' table.  To see if a certain directory has any locked
children below, we ask BerkeleyDB to do a "greater or equal match" on
the directory path, and see if any results come back.  If they do,
then at least one of the directory's children is locked, and thus the
directory cannot be deleted without further investigation.

Locks are ephemeral things, not historied in any way.  They are
potentially created and deleted quite often.  When a lock is
destroyed, the appropriate row is removed from the `locks' table.
Additionally, the locked-path is removed from the `lock-tokens' table.




\f
Merge rules

The Subversion filesystem must provide the following characteristics:

- clients can submit arbitrary rearrangements of the tree, to be
  performed as atomic changes to the filesystem tree
- multiple clients can submit non-overlapping changes at the same time,
  without blocking
- readers must never block other readers or writers
- writers must never block readers
- writers may block writers

Merging rules:

   The general principle: a series of changes can be merged iff the
   final outcome is independent of the order you apply them in.

Merging algorithm:

   For each entry NAME in the directory ANCESTOR:
  
     Let ANCESTOR-ENTRY, SOURCE-ENTRY, and TARGET-ENTRY be the IDs of
     the name within ANCESTOR, SOURCE, and TARGET respectively.
     (Possibly null if NAME does not exist in SOURCE or TARGET.)
  
     If ANCESTOR-ENTRY == SOURCE-ENTRY, then:
       No changes were made to this entry while the transaction was in
       progress, so do nothing to the target.
  
     Else if ANCESTOR-ENTRY == TARGET-ENTRY, then:
       A change was made to this entry while the transaction was in
       process, but the transaction did not touch this entry.  Replace
       TARGET-ENTRY with SOURCE-ENTRY.
  
     Else:
       Changes were made to this entry both within the transaction and
       to the repository while the transaction was in progress.  They
       must be merged or declared to be in conflict.
  
       If SOURCE-ENTRY and TARGET-ENTRY are both null, that's a
       double delete; if one of them is null, that's a delete versus
       a modification. In any of these cases, flag a conflict.
  
       If any of the three entries is of type file, declare a conflict.
  
       If either SOURCE-ENTRY or TARGET-ENTRY is not a direct
       modification of ANCESTOR-ENTRY (determine by comparing the
       node-id fields), declare a conflict.  A replacement is
       incompatible with a modification or other replacement--even
       an identical replacement.
  
       Direct modifications were made to the directory ANCESTOR-ENTRY
       in both SOURCE and TARGET.  Recursively merge these
       modifications.
  
   For each leftover entry NAME in the directory SOURCE:
  
     If NAME exists in TARGET, declare a conflict.  Even if SOURCE and
     TARGET are adding exactly the same thing, two additions are not
     auto-mergeable with each other.
  
     Add NAME to TARGET with the entry from SOURCE.
  
   Now that we are done merging the changes from SOURCE into the
   directory TARGET, update TARGET's predecessor to be SOURCE.

The following algorithm was used when the Subversion filesystem was
initially written, but has been replaced with the simpler and more
performant algorithm above:

   Merging two nodes, A and B, with respect to a common ancestor
   ANCESTOR:
   
   - First, the merge fails unless A, B, and ANCESTOR are all the same
     kind of node.
   - If A and B are text files:
     - If A is an ancestor of B, then B is the merged result.
     - If A is identical to B, then B (arbitrarily) is the merged
       result.
     - Otherwise, the merge fails.
   - If A and B are both directories:
     - For every directory entry E in either A, B, or ANCESTOR, here
       are the cases:
         - E exists in neither ANCESTOR nor A.
         - E doesn't exist in ANCESTOR, and has been added to A.
         - E exists in ANCESTOR, but has been deleted from A.
         - E exists in both ANCESTOR and A ...
           - but refers to different nodes.
           - but refers to different revisions of the same node.
           - and refers to the same node revision.
   
       The same set of possible relationships with ANCESTOR holds for B,
       so there are thirty-six combinations.  The matrix is symmetrical
       with A and B reversed, so we only have to describe one triangular
       half, including the diagonal --- 21 combinations.
   
       - (6) E exists in neither ANCESTOR nor A:
         - (1) E exists in neither ANCESTOR nor B.  Can't occur, by
           assumption that E exists in either A, B, or ancestor.
         - (1) E has been added to B.  Add E in the merged result. ***
         - (1) E has been deleted from B.  Can't occur, by assumption
           that E doesn't exist in ANCESTOR.
         - (3) E exists in both ANCESTOR and B.  Can't occur, by
           assumption that E doesn't exist in ancestor.
       - (5) E doesn't exist in ANCESTOR, and has been added to A.
         - (1) E doesn't exist in ANCESTOR, and has been added to B.
           Conflict.
         - (1) E exists in ANCESTOR, but has been deleted from B.
           Can't occur, by assumption that E doesn't exist in
           ANCESTOR.
         - (3) E exists in both ANCESTOR and B.  Can't occur, by
           assumption that E doesn't exist in ANCESTOR.
       - (4) E exists in ANCESTOR, but has been deleted from A.
         - (1) E exists in ANCESTOR, but has been deleted from B.  If
           neither delete was a result of a rename, then omit E from
           the merged tree.  *** Otherwise, conflict.
         - E exists in both ANCESTOR and B ...
           - (1) but refers to different nodes.  Conflict.
           - (1) but refers to different revisions of the same node.
             Conflict.
           - (1) and refers to the same node revision.  Omit E from
             the merged tree. ***
       - (3) E exists in both ANCESTOR and A, but refers to different
         nodes.
         - (1) E exists in both ANCESTOR and B, but refers to
           different nodes.  Conflict.
         - (1) E exists in both ANCESTOR and B, but refers to
           different revisions of the same node.  Conflict.
         - (1) E exists in both ANCESTOR and B, and refers to the same
           node revision.  Replace E with A's node revision.  ***
       - (2) E exists in both ANCESTOR and A, but refers to different
         revisions of the same node.
         - (1) E exists in both ANCESTOR and B, but refers to
           different revisions of the same node.  Try to merge A/E and
           B/E, recursively.  ***
         - (1) E exists in both ANCESTOR and B, and refers to the same
           node revision.  Replace E with A's node revision.  ***
       - (1) E exists in both ANCESTOR and A, and refers to the same
         node revision.
         - (1) E exists in both ANCESTOR and B, and refers to the same
           node revision.  Nothing has happened to ANCESTOR/E, so no
           change is necessary.
   
   *** == something actually happens

\f
Non-Historical Properties

[[Yes, do tell.]]

\f
UUIDs: Universally Unique Identifiers

Every filesystem has a UUID.  This is represented as record #1 in the
`uuids' table.

\f
Layers

In previous structurings of the code, I had trouble keeping track of
exactly who has implemented which promises, based on which other
promises from whom.

I hope the arrangement below will help me keep things straight, and
make the code more reliable.  The files are arranged in order from
low-level to high-level: each file depends only on services provided
by the files before it.

skel.c, id.c, dbt.c, convert-size.c

                Low-level utility functions.

fs_skels.c      Routines for marshaling between skels and native FS types.

fs.c            Creating and destroying filesystem objects.

err.c           Error handling.

nodes-table.c, txn-table.c, rev-table.c, reps-table.c, strings-table.c

                Create and open particular database tables.
                Responsible for intra-record consistency.

node-rev.c      Creating, reading, and writing node revisions.
                Responsible for deciding what gets deltified when.

reps-strings.c
                Retrieval and storage of represented strings.
                This will handle delta-based storage,

dag.c           Operations on the DAG filesystem.  "DAG" because the
                interface exposes the filesystem's sharing structure.
                Enforce inter-record consistency.

tree.c          Operations on the tree filesystem.  This layer is
                built on top of dag.c, but transparently distinguishes
                virtual copies, making the underlying DAG look like a
                real tree.  This makes incomplete transactions behave
                like ordinary mutable filesystems.

delta.c         Computing deltas.


\f
Appendix: Filesystem structure summary
======================================

Berkeley DB tables
------------------

                "nodes" : btree(ID -> NODE-REVISION, "next-key" -> NODE-ID)
            "revisions" : recno(REVISION)
         "transactions" : btree(TXN -> TRANSACTION, "next-key" -> TXN)
              "changes" : btree(TXN -> CHANGE)
               "copies" : btree(CPY -> COPY, "next-key" -> CPY)
              "strings" : btree(STR -> STRING, "next-key" -> STR)
      "representations" : btree(REP -> REPRESENTATION, "next-key" -> REP)
                "uuids" : recno(UUID)
                "locks" : btree(TOKEN -> LOCK)
          "lock-tokens" : btree(PATH -> TOKEN)
         "node-origins" : btree(NODE-ID -> ID)
        "checksum-reps" : btree(SHA1SUM -> REP, "next-key" -> number-36)
        "miscellaneous" : btree(STRING -> STRING)

Syntactic elements
------------------

Table keys:

                     ID ::= NODE-REV-ID ;
                    TXN ::= number-36 ;
                    CPY ::= number-36 ;
                    STR ::= number-36 ;
                    REP ::= number-36 ;
                  TOKEN ::= uuid ;

Property lists:

               PROPLIST ::= (PROP ...) ;
                   PROP ::= atom atom ;


Filesystem revisions:

               REVISION ::= ("revision" TXN) ;


Transactions:

            TRANSACTION ::= UNFINISHED-TXN | COMMITTED-TXN | DEAD-TXN
         UNFINISHED-TXN ::= ("transaction" ROOT-ID BASE-ID PROPLIST COPIES) ;
          COMMITTED-TXN ::= ("committed" ROOT-ID REV PROPLIST COPIES) ;
               DEAD-TXN ::= ("dead" ROOT-ID BASE-ID PROPLIST COPIES) ;
                ROOT-ID ::= NODE-REV-ID ;
                BASE-ID ::= NODE-REV-ID ;
                 COPIES ::= (CPY ...) ;
                    REV ::= number ;


Changes:

                 CHANGE ::= ("change" PATH ID CHANGE-KIND TEXT-MOD PROP-MOD) ;
            CHANGE-KIND ::= "add" | "delete" | "replace" | "modify" | "reset";
               TEXT-MOD ::= atom ;
               PROP-MOD ::= atom ;


Copies:

                   COPY ::= REAL-COPY | SOFT-COPY
              REAL-COPY ::= ("copy" SRC-PATH SRC-TXN DST-NODE-ID)
              SOFT-COPY ::= ("soft-copy" SRC-PATH SRC-TXN DST-NODE-ID)
               SRC-PATH ::= atom ;
                SRC-TXN ::= TXN ;
            DST-NODE-ID ::= NODE-REV-ID ;


Entries lists:

                ENTRIES ::= (ENTRY ...) ;
                  ENTRY ::= (NAME ID) ;
                   NAME ::= atom ;


Node revisions:

          NODE-REVISION ::= FILE | DIR ;
                   FILE ::= (HEADER PROP-KEY DATA-INFO [EDIT-DATA-KEY]) ;
                    DIR ::= (HEADER PROP-KEY ENTRIES-KEY) ; 
                 HEADER ::= (KIND CREATED-PATH 
                             [PRED-ID [PRED-COUNT 
                              [HAS-MERGEINFO MERGEINFO-COUNT]]]) ;
                   KIND ::= "file" | "dir" ;
                PRED-ID ::= NODE-REV-ID | "";
             PRED-COUNT ::= number | "" ;
           CREATED-PATH ::= atom ;
               PROP-KEY ::= atom ;
              DATA-INFO ::= DATA-KEY | (DATA-KEY DATA-KEY-UNIQID)
               DATA-KEY ::= atom ;
        DATA-KEY-UNIQID ::= atom ;
          EDIT-DATA-KEY ::= atom ;
          HAS-MERGEINFO ::= "0" | "1" ;
        MERGEINFO-COUNT ::= number ;


Representations:

         REPRESENTATION ::= FULLTEXT | DELTA ;
               FULLTEXT ::= (HEADER STRING-KEY) ;
                  DELTA ::= (HEADER (OFFSET WINDOW) ...) ;
                 WINDOW ::= (DIFF SIZE REP-KEY [REP-OFFSET]) ;
                   DIFF ::= ("svndiff" VERSION STRING-KEY) ;
                VERSION ::= number ;
                REP-KEY ::= atom ;
             STRING-KEY ::= atom ;
                 OFFSET ::= number ;
             REP-OFFSET ::= number ;

                 HEADER ::= (KIND TXN [MD5 [SHA1]]) ;
                   KIND ::= "fulltext" | "delta" ;
             
                   SIZE ::= number ;
                    MD5 ::= ("md5" MD5SUM) ;
                   SHA1 ::= ("sha1" SHA1SUM) ;
                 MD5SUM ::= atom ;
                SHA1SUM ::= atom ;


Strings:

                 STRING ::= RAWTEXT | LISTTEXT | DIFFTEXT
                RAWTEXT ::= /{anything.class}*/ ;
               LISTTEXT ::= list ;
               DIFFTEXT ::= /{anything.class}*/ ;


Node revision IDs:

            NODE-REV-ID ::= NODE-ID '.' CPY '.' TXN ;
                NODE-ID ::= number ;

UUIDs:
                   UUID ::= uuid ;


Locks:

                   LOCK ::= ("lock" PATH TOKEN OWNER 
                                    COMMENT XML-P CR-DATE [X-DATE]);
                   PATH ::= atom ;
                  OWNER ::= atom ;
                COMMENT ::= atom ;
                  XML-P ::= "0" | "1" ;
                CR-DATE ::= atom ;
                 X-DATE ::= atom ;

Lock tokens:

               (the value is just a lock-token, which is a uuid)


Node origins:

                NODE-ID ::= NODE-REV-ID ;


Lexical elements
----------------

UUIDs:

                   uuid ::= hexits-32 '-' hexits-16 '-' hexits-16 '-'
                            hexits-16 '-' hexits-48 ;
 
Numbers:

                 number ::= /{digit.class}+/ ;
              number-36 ::= /{base36.class}+/ ;
              hexits-32 ::= /{base16.class}{8}/ ;
              hexits-16 ::= /{base16.class}{4}/ ;
              hexits-48 ::= /{base16.class}{12}/ ;

(Note: the following are described in skel.h)
Skels:

                   skel ::= atom | list;
                   list ::= list.head list.body.opt list.tail ;
                   atom ::= atom.imp-len | atom.exp-len ;

              list.head ::= '(' spaces.opt ;
              list.tail ::= spaces.opt ')' ;
          list.body.opt ::=  | list.body ;
              list.body ::= skel | list.body spaces.opt skel ;

           atom.imp-len ::= /{name.class}[^\(\){ws.class}]*/ ;
           atom.exp-len ::= /({digit.class}+){ws.class}.{\1}/ ;

             spaces.opt ::= /{ws.class}*/ ;


Character classes:

               ws.class ::= [\t\n\f\r\ ] ;
            digit.class ::= [0-9] ;
             name.class ::= [A-Za-z] ;
           base16.class ::= [0-9a-f]
           base36.class ::= [a-z0-9]
         anything.class ::= anything at all ;


\f
Appendix: 'miscellaneous' table contents
======================================

The 'miscellaneous' table contains string keys mapped to string
values.  Here is a table of the supported keys, the descriptions of
their values, and the filesystem format version in which they were
introduced.

   Fmt   Key                  Value
   ---   ------------------   ------------------------------------
    4    forward-delta-rev    Youngest revision in the repository as of
                              the moment when it was upgraded to support
                              forward deltas.