structure

subversion-1.4.3-1.tar.gz 配置svn的源码

   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


Non-Historical Properties

[[Yes, do tell.]]


UUIDs: Universally Unique Identifiers

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


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.



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)

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-REV ::= 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-KEY [EDIT-DATA-KEY]) ;
                    DIR ::= (HEADER PROP-KEY ENTRIES-KEY) ;

                 HEADER ::= (KIND CREATED-PATH [PRED-ID [PRED-COUNT]]) ;
                   KIND ::= "file" | "dir" ;
                PRED-ID ::= NODE-REV-ID ;
             PRED-COUNT ::= number ;
           CREATED-PATH ::= atom ;
               PROP-KEY ::= atom ;
                REP-KEY ::= atom ;


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 [CHECKSUM]) ;
                   KIND ::= "fulltext" | "delta" ;
             
                   SIZE ::= number ;
               CHECKSUM ::= ("md5" BYTES) ;
                  BYTES ::= 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)


        
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 ;