Reverse-delta storage

Just some quick thougths after a first glance at fs-improvements.txt:

First, I'd like to propose a small change to the grammar, just for
consistency with `structure'. Notice that SOURCE-REVISION goes away, too.

   ! Berkeley DB tables
   ! ------------------
   !
   ! "nodes" : btree(ID -> REPRESENTATION)
   ! "revisions" : recno(REVISION)
   ! "transactions" : btree(TXN -> TRANSACTION,
   ! "next-id" -> TXN)
   ! "strings" : recno(PROPLIST | string)
   !
   !
   ! Syntactic elements
   ! ------------------
   !
   ! Table keys:
   ! ID ::= node.revision-id ;
   ! TXN ::= number ;
   ! STRING-KEY ::= atom ; /* a recno in the "strings" table */
   !
   ! Filesystem revisions:
   ! REVISION ::= ("revision" ID PROPLIST) ;
   ! PROPLIST ::= (PROP ...) ;
   ! PROP ::= atom atom ;
   !
   ! Transactions:
   ! TRANSACTION ::= ("transaction" ROOT-ID BASE-ROOT-ID) ;
   ! ROOT-ID ::= node.revision-id ;
   ! BASE-ROOT-ID ::= node.revision-id ;
   !
   ! Node revisions:
   ! NODE-REVISION ::= FILE | DIR ;
   ! FILE ::= (HEADER PROPLIST CONTENTS) ;
   ! DIR ::= (HEADER PROPLIST (ENTRY ...)) ;
   ! ENTRY ::= (NAME ID) ;
   ! NAME ::= atom ;
   !
   ! HEADER ::= (KIND FLAG ...) ;
   ! KIND ::= "file" | "dir" ;
   ! FLAG ::= ("mutable" PARENT-ID) ;
   ! PARENT-ID ::= "" | node.revision-id ;
   !
   ! CONTENTS, PROPLIST ::= ("fulltext" STRING-KEY)
   ! | ("shared" ID)
   ! | ("svndiff" BASE-ID STRING-KEY CHECKSUM) ;
   !
   ! CHECKSUM ::= ("md5" BYTES) ;
   ! BYTES ::= atom ;
   !
   !
   ! Lexical elements
   ! ----------------
   !
   ! File contents:
   !
   ! string ::= /.*/ ;
And a typo, I suspect:

-If CONTENTS is a fulltext, the `("string" STRING-KEY)' form is used.
+If CONTENTS is a fulltext, the `("fulltext" STRING-KEY)' form is used.

I'm a bit uneasy about one thing: in the "strings" table, there's no way
to distinguist between a PROPLIST and file contents. This means we can't
(consistently) check that a STRING-KEY refers to the right kind of data.
Do we want to have such sanity checks? If yes, we might have two string
tables instead, one for PROPLISTs and one for CONTENTS.

The rest seems fine.

As I mentioned before, I've been searching for articles about delta
composition. It turns out I was a bit too optimistic about the results.
It looks like we'll have to invent the wheel again, or at least spokes
... So, again, if anybody has any ideas, please yell.

-- 
Brane �ibej
    home:   <brane_at_xbc.nu>             http://www.xbc.nu/brane/
    work:   <branko.cibej_at_hermes.si>   http://www.hermes-softlab.com/
     ACM:   <brane_at_acm.org>            http://www.acm.org/