Online demo

Author Ondřej Pavlata Jablonec nad Nisou Czech Republic

Document date Initial release July 15, 2011 Last major release July 15, 2011 Last update July 15, 2011

Warning

1. This document has been created without any prepublication review except those made by the author himself.
2. The author is a habitual user of Total Commander [].

Table of contents

Introduction

Advocacy of hierarchical filesystems

1. a container,
2. a container plus its contents.

Operational semantics follows the physical world conventions:

• Deleting a directory means destroying both the container and its contents.
• Moving a directory means moving both the container and its contents.
• If a, b are directories not contained in each other, then a change in content of a does not affect the content of b.

Note: The Linux Virtual Filesystem contains 3 features that might break the above rules: multiple hardlinks, bind-mounts and symbolic links. However, there is an underlying low-level structure, which is not affected by the latter two features, so that only multiple hardlinks can be regarded as hierarchy defects. We consider such defects of being of low importance - they can be avoided by simply not using multiple hardlinks.

In an ever increasing measure, limitations of hierarchical filesystems have been recognized, in particular that of the single classification constraint: Users are forced to choose just one of possibly many classifications for the filed data. The problem is illustrated in the following example.

Example: Consider a hierarchy, part of which looks like in A or B.

Numerous solutions have been proposed to support multiple classification within file systems, giving rise to so called semantic file systems. Two main approaches can be distinguished [], []:

• Augmented approach. The file system consists of a hierarchical filesystem (observable to the user) equipped with a tool-set that provides alternative view(s) of data.
• Integrated approach. This approach tries to bypass hierarchical filesystems altogether. An integrated semantic file system has no intrinsic subsystem correspondent to a hierarchical filesystem. As of 2011, after at least two decades of research in the field, proposed solutions ([], [], [], [], []) seem to possess significant limitations. In particular:
  • Insufficient support for spatial containment. Classification (tagging) semantics is established at the expense of containment semantics.
  • Insufficient support for local naming. Names that identify file system objects have global scope so that the possibility of naming conflicts is substantially higher than with local identifiers.
  As a consequence, none of the solutions seems to be acceptable for practical use, even at the conceptual level.

Trying to replace hierarchical filesystems by a Logic File System was a noble research idea, but a bad idea. Using LFS as an additional filesystem, an additional way to access your actual hierarchical filesystem is far better; less ambitious, but better.

Conclusion: Despite the limitations, there are reasons to assume that hierarchical filesystems remain in widespread use over the next decades.

Filesystem of the Web

• (A) A tree [] – used in the context of hierarchical filesystems.
• (B) A forest [].
• (C) A partially ordered set – used e.g. within the term hierarchy of concepts [].

If we use the (B) interpretation we can arguably claim that a significant portion of the World Wide Web is constituted of (or is expressible as) a hierarchical filesystem. A global filesystem – just like the Web itself is global. The Web can be considered as a huge storage medium consisting of web servers. Most servers host hierarchical filesystems or at least contain data that can be meaningfully expressed (and manipulated) as hierarchical filesystems.

To discover how the concept of the Web as a filesystem is currently supported we pose the following questions:

1. Which standards (documents, research papers, concepts) do describe the filesystem view of the Web?
2. Which web application does provide global filesystem access of the Web? (Give the URL of such an application.)

As of 2011, the answers to these questions seems to be: 1. None, 2. None.

Note: The WebDAV method-set [] declares itself as a Network File System for the Internet []. However, WebDAV only supports communication to/from a single web server. It does not provide a unified view of the Web as a global filesystem. Speaking in Linux/Unix/POSIX terms, WebDAV is just a low-level filesystem. But we are concerned in the high-level filesystem here, in something which can be considered the Virtual File System of the Web.

Main goals

• Provide a world-wide web-based Virtual File System accessible via a web browser.
• Use existing filesystem-conformant parts of the web, in particular, FTP sites.
• Make the filesystem operation as convenient as with desktop applications (so that the user can have the feeling of the web being added to his/her computer).

Data model

The base layer

• N is the set of base nodes,
• ≤ is a partial order (a descendancy relation) on N such that every component is a finite tree in the usual sense.

• a directory,
• a (regular) file, and
• a (rich (symbolic)) link.

The account layer

Accounts are partially mapped to directories of the base forest via the target-directory function .t : A ↷ N. There can be accounts with the target directory undefined.

There is an initial account a for which .t is always defined.

Most accounts have a connection state: they can be connected or disconnected.

Contexted nodes

• Ѧ = { (a,n) ∈ A × N | n ≤ a.t }

• (a,n) ≤ (b,m)   iff   a = b and n ≤ m

Names

• Σ_down – local names (e.g. orange, docs), also called down names,
• Σ_root – global names (e.g. ftp.wave.vw::timber), also called root names,
• Σ_spec – special names (e.g. .. or .).

1. Each non-root base node (i.e. any node which has a parent directory) has a local name which is unique within its parent directory.
2. Each account has a unique global name.
3. The initial account is named by ::.

Global names

• <host name> is the host name,
• <user name> is the account name within the host.

Lookup

• n.ℓ₁(α) = m if one of the following holds:
  1. α is a local name and m is an α-labelled child of n,
  2. α is a global name and m equals x.t for anα-labelled account x,
  3. α is ".." and m is the parent of n,
  4. α is "." and m = n.
• .ℓ₂() is a restriction of .ℓ₁() such that:
  1. Only directory nodes are allowed to be in the domain.
  2. Accounts which have connection state must be connected.

Notes:

• For a global name α, the partial application .ℓ₂(α) : Ѧ ↷ Ѧ is constant (or empty).
• Further version of the lookup operator is parametrized with connection passdata that can be used for establishing account connection on the fly.

Pathnames

• A path starting with a global name is called absolute.
• If, in addition, its all other names are local then it is called canonic.

Pathname resolution

There are several kinds of path resolution. The most important criterium is how links are involved. Similarly to POSIX symlinks, any link node n provides a path, n.lpath. If the link is encountered, this path is potentially subject to the resolution process. The following modes of link resolution (of path resolution) are considered:

• literal - perform no link resolution,
• full - resolve all links,
• normal - resolve all links except for the last member of the path

Resolvability of absolute paths is independent on the directory where the resolution starts.

The logical forest

• Ͼ is set of canonical paths resolvable in normal resolution mode, and
• ≤ is a descendancy relation defined by path extension, i.e. p is a descendant of q iff p, as a sequence, is an extension of q.

Links

• A link cannot be resolved to a non-directory.
• A link can provide additional parameters for global name resolution.

A plain link just contains the lpath. The content of a non-plain link is roughly of the form

<global name> + <connection parameters> + <subsequent path> .

• the name of the protocol suggested to access resources,
• a password.

Non-plain links provide a persistent counterpart to a login form. The persistency is up to the password. By default, the password is not stored with the link - it is only used for establishing account connection.

VFS spheres

Data manipulation (VFS methods)

The following table lists modification methods which are considered mandatory to the manager.

Notes:

• Data retrieval methods are not listed - they are undefined by this proposal.
• No methods for account retrieval / manipulation are defined by this proposal.
• Unlike HTTP/WebDAV methods which work on a single-resource-tree basis, delete, copy, move, and mkdir work on multiple items.
• (*) Since Windows Vista / Windows Server 2008, the New Technology File System (NTFS) supports the mklink command [].

WFM operation

WFM versus VFS

Tasks and turns

• adding UI (dialog) control,
• iteration.

• updating directory views,
• displaying the response obtained from the VFS,
• providing the most suitable interface for user control, in particular, for
  • building the next turn request if the task is unfinished.

Demo application

Main goals

• Provide a start point for application development. In particular:
  • Describe proposed VFS methods.
  • Describe request-response iteration (the turn logic).
• Give a picture about possible look and feel.

Technical parameters

• No server-side present, the demo-app runs completely in the browser as a Javascript application.
• PHP only used as a dynamic assemblage tool.
• No (external) Javascript library or Ajax framework used.
• More than 30 thousand lines of code, more than 1 thousand classes.

Browser support

Browser		Version	Status
	Firefox	3.6 4.0	Recommended – the development browser
	Google Chrome	(12.0)	Recommended
	Safari	5.0	Recommended
	Opera	11.11	Usable, with deficiencies (most notably, there are screen update problems).
	Internet Explorer	7.0 8.0	Usable, with layout deficiencies.

Projects

Path resolution

PathResol > * > *

• Final to a Directory
  The path is resolved to a directory.
• Final to a File
  The path is resolved to a directory to a regular file.
• Final to a Link
  The path is resolved to a directory to a link.
• Non-final to a directory (tail)
  The path is not resolvable. The maximum resolvable prefix is resolved to a directory – leaving an unresolved path tail. Only the simplest case is considered here, such that
  • the tail consists of a single down-name (other cases are contained in PathResol > * > * > Tail),
  • no broken link is encountered - the resolution stops at zero link-depth (the non-zero link-depth cases are covered below).
• Non-final to a file
  The path is not resolvable. The maximum resolvable prefix is resolved to a regular file.
• Non-final to a file - slash trail
  A sub-case of the previous case. The path is unresolvable due to a forcing slash at the end.
• Empty path
  The path is empty.
• Relative path
  The path is relative. (Working directory paths are requested to be absolute.)
• Invalid path component
  The path contains a member that is not a valid component name.
• Password required
  A root name is encountered that requires a password to be supplied within the parameters.
  More precisely: The first unresolved component in the (last) expansion of the path is a root name that addresses a disconnected account. A password is required to establish the connection.
• Password invalid
  Similarly to the previous case. The supplied password is invalid.
• Broken link
  Path resolution stops at non-zero link-depth – due to local lookup fault.
• Cyclic link
  Path resolution exceeds the link-depth limit.
• Invalid link
  Path resolution stops at non-zero link-depth – due to an invalid link content.

PathResol > * > * > Tail

• at zero link-depth,
• at a directory,
• due to local lookup fault.

• Single down-name
  The path tail consists of a single down-name.
• Multiple down-names
  The path tail consists of multiple down-names.
• Having a dot-name
  The path tail contains a '.'.
• Having a dotdot-name
  The path tail contains a '..'.
• Ending with a slash trail
  The path tail ends with a '/'.
• Having a root-name
  The path tail contains a root name ('boulder::boulder').

PathResol > * > * > RootUp

Note: The WFM proposal interprets '..' in the strict sense – roots have no parents.

• Going up the initial root
• Going up a root (after a link)
• Going up a root (after a root-name)

PathResol > * > * > RootName

• Final to a (root-named) directory
• Going up a root (after a link)
• Going up a root (after a root-name)

Link manipulation

Link > * > *

• Entirely resolvable
  Link content is resolvable to a target directory.
• Empty Host and/or User Name
  The Host and/or User Name field has empty value.
• Invalid Host and/or User Name
  The Host and/or User Name field has non-empty invalid value.
• Host not found
  There is no account with the requested host.
• User not found
  There is no account with the given root-name.
• Empty Password
  A password is required for the root-name resolution and the given password is empty.
• Invalid Password
  The given password is invalid.
• Invalid Directory Path
  The subsequent directory path does not conform to the naming domain.
• Unresolved Directory Path
  The subsequent directory path is unresolved. No broken link is encountered - the resolution stops at zero link-depth.
• Subsequently Broken Link
  The subsequent directory path refers to a broken link.

Operation

Oper > *

• Non-deletable node
  A non-deletable node is encountered during a deletion-requesting operation.
• Target-source descendancy
  Requested target directory is a descendant of the source directory in the base forest (N, ≤).
• Target-source identity
  Requested target directory is identical to the source directory.
• Invalid target name
  Requested target name is invalid.

Oper > * > Overwrite

• Overwrite files (as items)
  Both source item path and target item path are resolved to regular files.
• Overwrite files (as nodes during merge)
  A source-target directory merge occurs. A subpath is resolved to a regular file in both the source and target directory trees.
• Merge directories
  Both source item path and target item path are resolved to directories so that a source-target directory merge is suggested.
• Merge directories, overwrite files
  A combination of the previous two cases. (The overwrite files as nodes case occurs after multiple iteration.)
• Type mismatch (items)
  Either the source item path is resolved to a directory and the target item path is resolved to a non-directory or vice versa.
• Type mismatch (nodes, during merge)
  A source-target directory merge occurs. A subpath is resolved to a directory in the source tree and to a non-directory in the target tree or vice versa.

Oper > * > StartPos

• Start before the whole item (default)
  By default, the start position is placed before the item.
• Start after the whole item (abnormal)
  The opposite of the previous case. This is an artificial case – it should not occur during standard user operation.
• Start inside the item
  The start position is placed before/after some node within the first item's (source) tree. Such a request is created after a turn with incomplete operation (the stop position of a turn becomes the start position of the subsequent turn).
• Invalid subpath component
  The start position subpath contains an invalid component. This is an artificial case.
• Nonexistent node
  The start position subpath is not resolved. This can occur if the subpath's node is deleted by another agent in-between turns.
• Subpath having a dotdot
  The start position subpath contains '..'. This is an artificial case.
• Subpath having a root-name
  The start position subpath contains a root-name. This is an artificial case.

Oper > * > StartPos > Point

• Before pre-visit
  The start position is in the pre-visit phase before the node refered to by the given subpath.
• After pre-visit
  The start position is in the pre-visit phase after the node.
• Before post-visit
  The start position is in the post-visit phase before the node.
• After post-visit
  The start position is in the post-visit phase after the node.

Basic tables

Delete > Basic

• Leaf node
  Leaf node deletion.
• Non-empty directory
  Non-leaf node deletion.
• Resilient node
  A non-deletable node encountered during tree deletion.
• Incorrect start position
  See Oper > * > StartPos > Nonexistent node.
• Iterated non-leaf node
  A non-leaf node is encountered on post-visit during tree deletion. This case can occur for internal start positions.

MkDir > Basic

• Single new directory (standard)
  A single new directory is requested and created.
• Multiple items (nonstop)
  Multiple new directories created without any naming conflict.
• Existing directory
  Creation of an already existing directory is requested.
• Existing directory (special names)
  Directories refered to by '..', '.' and '/' to be created.
• Missing ancestors
  Some intermediate paths refer to non-existing directories.
• Multiple items (various stops)
  Combination of cases (a) existing directories and (b) missing ancestors via multiple items.
• Existing non-directory
  A naming conflict with an existing non-directory.
• Non-directory parent
  Path prefix refers to a regular file.
• Non-directory parent (via a link)
  Path prefix refers to a regular file (via a link).
• New subpath having a dot-segment
  Directory chain creation; the tail subpath contains a '.'.
• New name having a trail
  Directory chain creation; the tail subpath ends with '/'.
• Invalid name
  A name outside the naming domain is requested.
• New subpath having dotdot
  The requested tail subpath contains '..' (not supported).
• Root name
  Creation of a root-named directory is requested.
• Multiple errors
  Multiple errors occur in combination.

* > Basic

• Single directory copied/moved
  A single directory copy/move.
• Single directory copied/moved & renamed
  A single directory copy/move with a new end name.
• Missing target directory (missing ancestors)
  The requested target directory has to be (auto)created.
• Invalid target directory path
  The target directory path contains an invalid name.
• Non-directory target parent
  The target directory path points to a regular file.
• Invalid target name
  The requested target name is invalid.
• Incorrect start position
  The start position subpath does not point to an existing node.
• Target-source descendancy
  Requested target directory is a descendant of the source directory in the base forest.
• Target-source identity
  Requested target directory is identical to the source directory.

* > Overwrite

• Overwrite files (as items)
• Overwrite files (as nodes during merge)
• Merge directories
• Merge directories, overwrite files
• Type mismatch (items)
• Type mismatch (nodes, during merge)

* > Links

• Copy / Move link items
  An example of link copy/move.

Default

• Initial state
  Suggested initial state of the file manager. A link named 'a' is to be created in the i-links built-in directory.

MultiTask

• Delete + MkDir + Copy + Move
  Example of multiple open tasks.

DirView

• Broken Link in a Directory View
  The directory lists the content of a broken link.
• Non-initial root in panel path
  Example of a non-initial root-name in the panel path. Such a case is considered non-standard.

Bibliographic references

Epilogue

Don't deceive yourself. You did know it – you have always known it.

George Orwell, 1984

License