[Fwd: Some filesystem questions]

FYI, this is a discussion about the filesystem Jim and I are having, and
which by mistake didn't make it to the list.

    Brane

attached mail follows:

Hi Jim,

I've been reading the documentation in "structure" and
"skel.h", trying to understand what's going on. I modified
the "structure" file a bit, fixing what I think is an
ambiguity in the description of revisions, and a few typos,
see the attached diff.

The next thing I did was try to formalise the representation
syntax from the descriptions in "structure" and "skel.h",
also attached. I noticed two things here: First, the
BASE_PATH isn't described in "structure"; and second, in the
"Cloning" section, I can't quite make out whether BASE_PATH
and BASE_NAME are used interchangeably or not.

More questions:

We have

     CLONE ::= ("cloned" CLONE_ID)
             | ("moved" PARENT_CLONE_ID ENTRY);

and

     DIR ::= (HEADER (ENTRIES)) ;
     ENTRIES ::= | ENTRY ENTRIES ;
     ENTRY ::= (NAME ID) | (NAME ID BASE_PATH) ;

Is the ENTRY the same in both cases? And in DIR, if I'm
right, ENTRIES can be empty -- but "skel.h" doesn't allow an
empty list.

Sorry for being so pedantic, but I'm trying to wrap my head
around this, and the questions just popped up. And don't
worry, I'll be asking more questions soon, no doubt. :-)

     Brane

-- 
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/

## Berkeley DB tables

       "nodes": btree(ID -> REPRESENTATION)
      "clones": btree((TXN BASE_PATH) -> CLONE)
   "revisions": recno(REVISION)
"transactions": btree(TXN -> (ROOT_ID BASE_ROOT_ID),
                      "next-id" -> TXN)

ID ::= node.id ;
TXN ::= number ;
CLONE ::= ("cloned" CLONE_ID)
        | ("moved" PARENT_CLONE_ID ENTRY);
REVISION ::= ("revision" ID PROPLIST) ;
REPRESENTATION ::= ("fulltext" NODE-REVISION)
                 | ("younger" DELTA CHECKSUM) ;
ROOT_ID, BASE_ROOT_ID, CLONE_ID, PARENT_CLONE_ID ::= node.id ;

## BASE_PATH ::= ??

## Node revisions

NODE-REVISION ::= FILE | DIR ;
FILE ::= (HEADER DATA) ;
DATA ::= atom ;
DIR ::= (HEADER (ENTRIES)) ;
ENTRIES ::= | ENTRY ENTRIES ;
ENTRY ::= (NAME ID) | (NAME ID BASE_PATH) ;
NAME ::= atom ;

HEADER ::= (KIND PROPLIST FLAGS) ;
KIND ::= "file" | "dir" ;
PROPLIST ::= | atom atom PROPLIST ;
FLAGS ::= | skel FLAGS ;

DELTA ::= ("svndiff" DATA) ;
CHECKSUM ::= ("md5" BYTES) ;
BYTES ::= atom ;

## Node & revision IDs

node.id ::= number | node.revision-id '.' number ;
node.revision-id ::= node.id '.' number ;
number ::= /[0-9]+/ ;

## Skels

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

atom.impl ::= /[A-Za-z][^\t\n\f\r\ ]*[\t\n\f\r\ ]/ ;
atom.expl ::= /([0-9]+)[\t\n\f\r\ ].{\1}/ ;

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

space.opt ::= /[\t\n\f\r\ ]*/ ;

attached mail follows:

> We have
>
> CLONE ::= ("cloned" CLONE_ID)
> | ("moved" PARENT_CLONE_ID ENTRY);
>
> and
>
> DIR ::= (HEADER (ENTRIES)) ;
> ENTRIES ::= | ENTRY ENTRIES ;
> ENTRY ::= (NAME ID) | (NAME ID BASE_PATH) ;
>
> Is the ENTRY the same in both cases? And in DIR, if I'm
> right, ENTRIES can be empty -- but "skel.h" doesn't allow an
> empty list.

No, ENTRY isn't the same in both cases. In a CLONE, the entry is just
the name of the directory entry.

Yes, ENTRIES can be empty. skel.h should allow an empty list; if it
doesn't, that's a bug. An empty list is a skel_t whose `is_atom' and
`children' members are both zero.

> Sorry for being so pedantic, but I'm trying to wrap my head
> around this, and the questions just popped up. And don't
> worry, I'll be asking more questions soon, no doubt. :-)

No problem! If you can think of a simpler way to track cloning, do
let me know. Keep in mind that the base revision can do arbitrary
structure sharing, and in fact, will do so in everyday cases.

One thing to note about the syntax: I'm imitating the list structure
notation used in Scheme. The `...' syntax is actually well-defined
for describing list (or skel) structure --- it means zero or more
repetitions of the preceding object. So (FOO ...) is a list of zero
or more FOO's. ((FOO BAR) ...) is a list of zero or more lists, each
of which contains a FOO, and a BAR. It's less general than writing
out the recursion in BNF, but it's still very handy.

>
> ## Berkeley DB tables
>
> "nodes": btree(ID -> REPRESENTATION)
> "clones": btree((TXN BASE_PATH) -> CLONE)
> "revisions": recno(REVISION)
> "transactions": btree(TXN -> (ROOT_ID BASE_ROOT_ID),
> "next-id" -> TXN)
>
>
> ID ::= node.id ;
> TXN ::= number ;
> CLONE ::= ("cloned" CLONE_ID)
> | ("moved" PARENT_CLONE_ID ENTRY);
> REVISION ::= ("revision" ID PROPLIST) ;
> REPRESENTATION ::= ("fulltext" NODE-REVISION)
> | ("younger" DELTA CHECKSUM) ;
> ROOT_ID, BASE_ROOT_ID, CLONE_ID, PARENT_CLONE_ID ::= node.id ;
>
>
> ## BASE_PATH ::= ??
>
> ## Node revisions
>
> NODE-REVISION ::= FILE | DIR ;
> FILE ::= (HEADER DATA) ;
> DATA ::= atom ;
> DIR ::= (HEADER (ENTRIES)) ;
> ENTRIES ::= | ENTRY ENTRIES ;
> ENTRY ::= (NAME ID) | (NAME ID BASE_PATH) ;
> NAME ::= atom ;
>
> HEADER ::= (KIND PROPLIST FLAGS) ;
> KIND ::= "file" | "dir" ;
> PROPLIST ::= | atom atom PROPLIST ;
> FLAGS ::= | skel FLAGS ;
>
> DELTA ::= ("svndiff" DATA) ;
> CHECKSUM ::= ("md5" BYTES) ;
> BYTES ::= atom ;
>
>
> ## Node & revision IDs
>
> node.id ::= number | node.revision-id '.' number ;
> node.revision-id ::= node.id '.' number ;
> number ::= /[0-9]+/ ;
>
>
> ## Skels
>
> skel ::= atom | list;
> atom ::= atom.imp-len | atom.exp-len ;
> list ::= list.head list.body list.tail ;
>
> atom.impl ::= /[A-Za-z][^\t\n\f\r\ ]*[\t\n\f\r\ ]/ ;
> atom.expl ::= /([0-9]+)[\t\n\f\r\ ].{\1}/ ;
>
> list.head ::= '(' space.opt ;
> list.tail ::= spaces.opt ')' ;
> list.body ::= skel | list.body space.opt skel ;
>
> space.opt ::= /[\t\n\f\r\ ]*/ ;
>
> --------------070705080402010909000801--
>
>