Hierarchical tag structure in SetFS

On Tue, Feb 27, 2007 at 09:53:51PM +0000, Tuomo Valkonen wrote:
> One related thing that I've thought about (a little but not enough)
> is typed tags or meta-tags. So e.g. the tag 'ion' could have the 
> meta-tag 'project'. The path component #project would then filter
> out everything that doesn't have a 'project' meta-tagged tag. 
> Furthermore creating an object with tags ion.project/foo/bar, would 
> fail if 'ion' isn't meta-tagged 'project', and if the ion tag doesn't
> exist, meta-tag it a project. 

If you take this a little further and have the tags in a hierarchy I
think you could solve quite a few of the problems.  If you view the
directories in a traditional file system as tags and the files being
allowed being allowed to appear, several times, in any directory (think
hardlinks) then you're pretty much there already.  What would be nice
would be to tag a file as being associated with a directory but without
actually being in it and therefore needing a unique name within it.  It
would also be nice to be able to do the translation back again from file
to find out what names it appears under in the file system.

If we view it as Haskell code, we have a set of Tags that can either be
the root of a hierarchy or appear below another tag with a name,

> data Tag = Root | Tag String Tag

and a set of Objects.

> data Object = Object

Once we have these, we can implement the standard Unix calls:

> readdir :: Tag -> [Object]
> open :: Tag -> String -> Object
> link :: Tag -> Object -> String -> ()
> unlink :: Tag -> String -> ()

Plus the more interesting ones specific to this file system

> tag :: Tag -> Object -> ()
> untag :: Tag -> Object -> ()
> bindings :: Object -> [(Tag, Maybe String)]

Rather than just the intersection of tags, how about using a finite
state automaton (similar to a regexp, but over the names in the tag
hierarchy rather than characters) for searching.  It's the first
formalisation I could come up that seemed as though it would be
generally useful.  The purpose is to allow you to express things like:

  Show me all the files that are tagged with both "projects/sysfs" and
  "people/sam_mason".

  Show me all the files that are tagged with either "people/sam_mason"
  or "people/tuomo_valkonen".

  Show me all the files that are "bound with a name" in a tag that ends
  with "bin" or "sbin".

Here is my best attempt at a grammar (of the syntax) for specifying this
sort of thing, it's mainly based on a grammar for regular expressions.
Specifying this sort of thing at the level of characters is a bit cheesy
but seems to be reasonably standard practice.

> Conjunction ::= Disjunction | Disjunction '&' Conjunction
> 
> Disjunction ::= Sequence | Sequence '|' Disjunction
> 
> Sequence ::= Term | Sequence '/' Term
> 
> Term ::= Assertion | Atom | Atom Quantifier
> 
> Assertion ::= Root | Leaf
> 
> Root ::= '^'
> Leaf ::= '$'
> 
> Quantifier ::=  '*' | '+' | '?'
>   | '{' DecimalDigits '}'
>   | '{' DecimalDigits ',' '}'
>   | '{' DecimalDigits ',' DecimalDigits '}'
> 
> DecimalDigits ::= DecimalDigit | DecimalDigits DecimalDigit
> DecimalDigit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
> 
> Atom ::= NameMatchComp | '(' Disjunction ')'
> 
> NameMatchComp ::= NameMatch | '^' NameMatch
> 
> NameMatch ::= AnyTag | TagName | Tagged | Bound
> 
> AnyTag  ::= '\\' 'a'
> TagName ::= {- something like [a-z]+ -}
> Tagged  ::= '\\' 't'
> Bound   ::= '\\' 'b'

This would allow you to specify the above examples as:

  projects/sysfs&people/sam_mason

  people/sam_mason|people/tuomo_valkonen

  (bin|sbin)$

It would be possible to use '/' for either the Root or Leaf, but if
people accidentally put an extra '/' into the string it would do
strange things.  It's for this reason that I've left the root and leaf
identifiers the same a regular expressions.

Comments?


  Sam