structure

linux subdivision ying gai ke yi le ba

- 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)
            "revisions" : recno(REVISION)
         "transactions" : btree(TXN -> TRANSACTION, "next-id" -> TXN)
              "changes" : btree(TXN -> CHANGE)
               "copies" : btree(CPY -> COPY, "next-id" -> CPY)
              "strings" : btree(STR -> STRING, "next-id" -> STR)
      "representations" : btree(REP -> REPRESENTATION, "next-id" -> REP)
                "uuids" : recno(UUID)

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

Table keys:

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

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" ;
               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 ;
                   
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 ;