Notes
Requirements
Fix the scope. Make a directory, or a whole chain of them with dash p. Change directory and print the working directory. List a path: a directory lists its children in sorted order, a file lists just itself. Write, append and read files. Paths can be absolute or relative and may contain dot and dot dot. Several users work at once, each with their own working directory. Permissions, remove and move are extensions.
Clarify the edge cases, because each one becomes a line of code. Making a directory whose parent is missing is an error, unless dash p is given. Dash p on a directory that already exists does nothing. Dot dot at the root stays at the root, as in a real shell. Writing to a missing file creates it, but its parent directory must exist. And changing directory into a file is an error that says not a directory.
- mkdir path, mkdir -p path
- cd path, pwd
- ls path: dir lists children,
- a file lists itself
- write, append, cat a file
- absolute and relative paths
- with . and ..
- many users, each with a cwd
- du: total size of a subtree
- later: permissions, rm, mv
- mkdir a/b when a is missing?
- error, unless -p
- mkdir -p on an existing dir?
- fine, nothing to do
- .. at the root?
- stays at the root
- write to a missing file?
- create it; parent must exist
- cd into a file?
- error: not a directory
Entities
The entities. The file system owns one tree that starts at the root directory. Every entry in the tree is a node, and a node is either a directory or a file. A directory contains child nodes, so the tree is recursive. The current directory does not belong to the file system: it belongs to a session, one per terminal, along with the user name. That split is what lets two users stand in different directories of the same tree.
Composite
This is the Composite pattern: a directory and a file share one parent type, and a directory holds a collection of that same type. Callers can ask any node its size or its path without caring which kind it is. In Java seventeen the node class is sealed, so it permits exactly directory and file, and a pattern-matching instance-of tells them apart safely. Children sit in a tree map, so listing comes out sorted for free.
The payoff of Composite is recursion with no type checks. A directory's size is the sum of its children's sizes, and a file's size is its length, so du on any path is one call. The path goes the other way: each node keeps a pointer to its parent, and the path is the parent's path plus a slash and the name, stopping at the root. Keeping the parent pointer is also what makes dot dot and pwd cheap.
abstract sealed class Node
permits Directory, File {
String name; Directory parent;
abstract long size();
String path() { ... }
}
final class Directory extends Node {
Map<String, Node> children =
new TreeMap<>(); }
final class File extends Node {
StringBuilder content; } // Directory: sum of children
long size() {
return children.values().stream()
.mapToLong(Node::size).sum();
}
// File
long size() { return content.length(); }
String path() { // walk to the root
if (parent == null) return "/";
return parentPath + "/" + name; } Path parsing
Path parsing is where most bugs hide, so keep it in one place. An absolute path starts at the root, and a relative one starts at the session's current directory. Split on slashes and drop empty parts, which handles double slashes and a trailing slash, and drop single dots. Then walk: dot dot moves to the parent, or stays at the root, and a name looks up a child. Every step except the last must be a directory, or we report not a directory.
start = path starts with "/"
? root : session.cwd
for (p : split("/"), skip "" and ".")
if (cur is not a Directory) error
if (p == "..")
cur = parent, or root at root
else cur = children.get(p)
missing: no such file
"logs/../conf/." from /srv/app
is /srv/app/conf Flow: mkdir -p
Making directories walks the parts the same way, but creates what is missing. Without dash p, only the last part may be new, so mkdir slash a slash b fails when a does not exist, with a hint to use dash p. With dash p, every missing part is created and an existing one is simply passed through. In both modes, a file sitting where a directory is needed is an error, never silently replaced.
for each part:
next = cur.children.get(part)
missing and not last and not -p:
error: use -p
missing: create a Directory
exists, last, not -p:
error: already exists
next is a File: not a directory
cur = next Flow: cd and pwd
Change directory resolves the path and insists the result is a directory, then stores that directory object in the session. Storing the node, not a string, means pwd is just the node's path, and relative paths start from a real object without parsing anything. Changing into a file fails with not a directory, and the session keeps its old working directory.
void cd(Session s, String path) {
s.cwd = resolveDir(s, path);
}
String pwd(Session s) {
return s.cwd.path();
}
cd /srv/app/conf/app.yml
error: not a directory Flow: files
Files follow one flow. Resolve the parent directory from every part except the last, look up the name, and create an empty file if it is missing. If the name is a directory, refuse. Then either clear the content and write, or append. Reading resolves the path and returns the content. Listing a directory returns its children with a slash after directories, and listing a file returns just its own name, exactly as a real shell does.
dir = resolveDir(all parts but last) n = dir.children.get(name) if (n == null) create a File if (n is a Directory) error if (!append) content.setLength(0) content.append(text) ls on a file: just its name ls on a dir: children, dirs end /
Command pattern
The shell uses the Command pattern. Each verb, make directory, change directory, list, write, append, read and disk usage, is a small object with one run method, stored in a map by name. Executing a line splits it into words, looks up the first word and runs it with the rest. A new verb is one more entry, not another branch in a growing switch. Errors are caught in one place and printed as error lines.
interface Command {
String run(Session s, List<String> a);
}
Map<String, Command> commands = Map.of(
"mkdir", (s, a) -> ...,
"cd", (s, a) -> ...,
"cat", (s, a) -> readFile(..));
exec(s, "cd /srv/app"):
split, look up "cd", run it,
errors become "error: ..." Concurrency
Concurrency. The tree is shared, so one read-write lock guards it. Listing, reading, changing directory and computing sizes take the read lock and run in parallel. Making directories and writing files take the write lock. A session belongs to one terminal, so its working directory needs no lock. In the demo eight threads each make a hundred nested directories and append to one shared log, and the log ends up exactly eight hundred characters long.
- read lock: ls, cat, cd, pwd,
- du, every resolve
- write lock: mkdir, write,
- append, later rm and mv
- session: one per thread,
- so cwd needs no lock
- test: 8 threads x 100
- mkdir -p + append to one log
- log size 800, 9 entries
Extension: permissions
Permissions arrive as an extension. Each node records its owner and a set of what everyone else may do, read or write. The owner may do anything. Walking into a directory needs read, creating inside it needs write, and changing a file needs write on that file. In the demo a guest can read the admin's config file but appending to it fails with permission denied. Groups and execute bits are the same idea with more fields.
boolean allows(String user, Perm p) {
return user.equals(owner)
|| others.contains(p);
}
walk into a dir: needs READ
create in a dir: needs WRITE
write a file: needs WRITE
guest cat app.yml: works
guest append: permission denied Extensibility
Other extensions fit the same shape. Remove unlinks a node from its parent, and recursive remove is needed for a non-empty directory. Move unlinks and relinks, after checking that a directory is not being moved inside itself. Symbolic links become a third node kind added to the sealed list, with a hop limit so loops cannot hang the walk. Find is a visitor walking the composite with a predicate.
- rm: unlink from the parent;
- rm -r on a non-empty dir
- mv: unlink + relink, check the
- target is not inside itself
- symlinks: a third Node type,
- limit hops to stop loops
- find / visitor: walk the
- composite with a predicate
- big files: chunks, not one
- StringBuilder
Testing
The full code is below the player. The demo drives the shell with a script: make nested directories with and without dash p, change directory with dot and dot dot, write and append a config file, list a directory and a file, total the sizes, and try to change into a file. A guest session reads but cannot write. Then eight threads build directories and append to one log at once, and the totals are asserted.
$ mkdir /a/b error: no such directory: a (use -p) $ cd logs/../conf/. then pwd /srv/app/conf $ ls /srv/app conf/ logs/ $ du /srv 24 chars guest $ append /srv/app/conf/app.yml error: permission denied race: log size 800, entries 9 all checks passed
Follow-ups
Expect follow-ups. Why is the working directory in the session? Because two users must be able to stand in different places. Why not a lock per directory? It allows more parallel writes, but a move touches two directories, so you must lock them in a fixed order to avoid deadlock. Recursive listing is recursion on the composite. And to survive a restart, append every change to a journal and replay it on startup.
- why is cwd not in FileSystem?
- each user needs their own
- lock per directory?
- faster, but mv needs two
- locks in a fixed order
- ls -R or find?
- recursion on the composite
- paths with spaces?
- a real tokenizer with quotes
- persist it? a journal of ops
Say it like this
The short version. It is a composite: a sealed node is either a directory or a file, and a directory keeps child nodes in a sorted map, so size and listing are simple recursion. One resolver handles absolute and relative paths with dot and dot dot. The current directory lives in a session per user, not in the tree. Shell verbs are commands in a map, and a read-write lock lets readers share the tree.
- "Composite: a sealed Node is
- a Directory or a File, and a
- directory holds Nodes in a
- TreeMap. One resolver handles
- absolute, relative, . and ..
- The cwd lives in a Session.
- Shell verbs are Commands; a
- read-write lock guards the tree."