In-memory file system

Design an in-memory file system with files and directories. Support paths, create, delete, move and copy, the size of a directory, and search by name or extension, with clear errors for invalid operations.

Design a small file system that lives in memory. Users create directories and files, move around with relative paths such as `../docs`, delete, move and copy items, ask for the size of a directory, and search for files by name or extension. Bad requests must fail with a clear error and change nothing.

Questions to ask first

• Do we store file contents? Assume no. A file has a name and a size in bytes, and that is all the design needs.
• How are paths written? Assume `/` separates names, a path that starts with `/` is absolute, and any other path is relative to a current directory.
• What does `..` mean at the root? Assume it stays at the root, as in a real shell.
• Does moving or copying need the full target name? Assume the target is a directory, and the item keeps its own name inside it.
• What if the target already holds that name? Assume the call fails with EXISTS. We never overwrite silently.
• How does search match? Assume an exact name, or an extension written as `*.txt`. More match rules will come later.

Requirements

• Create directories and files. The parent directory must already exist.
• Resolve absolute and relative paths, including `.` and `..`, against a current directory.
• Delete a file, or a directory with everything inside it.
• Move and copy a file or a directory into another directory. A copy is a deep copy.
• Report the size of a file, or of a directory as the sum of everything inside it.
• List a directory, and search a subtree by exact name or by extension.
• Refuse invalid operations with a clear error: NOT_FOUND, NOT_A_DIRECTORY, EXISTS or INVALID.

Out of scope

• File contents, reading and writing bytes, and disk storage.
• Permissions, owners, links and timestamps (see the extensions).
• Many users or threads at the same time.

Entities

• FsNode: name, parent -> size(), copy(), path()
• FileNode: a leaf with a size in bytes
• DirectoryNode: children by name -> add(), remove(), child(), size() adds up the children
• PathResolver: turns any path into an absolute one -> resolve(cwd, path)
• NodeFilter: a search rule -> matches(node), with NameFilter and ExtensionFilter
• FileSystem: the entry point, owns the root and the current directory -> cd(), mkdir(), create(), delete(), move(), copy(), size(), ls(), find()
• FsException: an operation the file system refuses, with a code

Classes in the model design

• FsNode (abstract)
• FileNode (class)
• DirectoryNode (class)
• PathResolver (class)
• NodeFilter (interface)
• NameFilter (class)
• ExtensionFilter (class)
• FileSystem (class)
• FsException (class)

The main use case, step by step

1. A user types `copy /docs /pics`. The client calls `FileSystem.copy("/docs", "/pics")`.
2. The file system asks the `PathResolver` to turn both paths into absolute paths. Relative parts and `..` disappear here. The resolver reads only the text, so it needs no tree.
3. The file system looks up the two absolute paths in the tree, one name at a time from the root. A missing name throws `FsException(NOT_FOUND)`. A name that is a file in the middle of a path throws `NOT_A_DIRECTORY`.
4. It checks the rules for a copy. The target must be a directory, and it must not already hold a child named `docs`, or the call throws EXISTS. Nothing has changed yet.
5. It calls `copy()` on the source node. A `FileNode` returns a new file with the same name and size. A `DirectoryNode` copies each child the same way, so the whole subtree is duplicated.
6. It adds the copy to the target directory. The new directory sets itself as the parent of each of its children. A later change to `/docs` does not change `/pics/docs`.
7. A call to `size("/pics")` asks the `DirectoryNode` for its size. It adds the sizes of its children, and any directory among them adds up its own children the same way.

Patterns used

• Composite: FsNode with FileNode (a leaf) and DirectoryNode (a node that holds children). Its size(), copy() and collect() work on both.. A directory holds files and other directories, to any depth. With one shared type, `size()` and `copy()` are written once per class, and no code asks 'is this a file or a directory?' before it recurses.
• Strategy: NodeFilter with NameFilter and ExtensionFilter, passed to the tree walk in find().. The walk over the tree is always the same. Only the question 'does this node match?' changes. A new search rule is one new class, and the walk does not change.
• Facade: FileSystem is the one class callers talk to. It resolves paths, finds nodes, checks rules and then changes the tree.. Callers never touch nodes directly, so every rule (no duplicate names, no moving a folder into itself) is checked in one place.

Key code

The composite: files and directories as nodes

public abstract class FsNode {
    private final String name;
    private DirectoryNode parent;

    protected FsNode(String name) { this.name = name; }

    public String name() { return name; }
    public DirectoryNode parent() { return parent; }
    void setParent(DirectoryNode parent) { this.parent = parent; }

    public abstract int size();
    public abstract FsNode copy();
    public abstract boolean isDirectory();
    /** The absolute path, built by walking up to the root. */
    public String path() {
        return parent == null ? "/" : (parent.parent() == null ? "" : parent.path()) + "/" + name;
    }
    /** True when this node is other, or is somewhere below it. */
    public boolean isInside(FsNode other) {
        for (FsNode n = this; n != null; n = n.parent) if (n == other) return true;
        return false;
    }
    /** Adds this node to out if it matches. A directory also asks its children. */
    public void collect(NodeFilter filter, List<FsNode> out) {
        if (filter.matches(this)) out.add(this);
    }
}

public final class FileNode extends FsNode {
    private final int sizeBytes;
    public FileNode(String name, int sizeBytes) { super(name); this.sizeBytes = sizeBytes; }
    @Override public int size() { return sizeBytes; }
    @Override public FsNode copy() { return new FileNode(name(), sizeBytes); }
    @Override public boolean isDirectory() { return false; }
}

public final class DirectoryNode extends FsNode {
    private final Map<String, FsNode> children = new TreeMap<>();   // sorted by name

    public DirectoryNode(String name) { super(name); }
    @Override public int size() { return children.values().stream().mapToInt(FsNode::size).sum(); }
    @Override public boolean isDirectory() { return true; }

    @Override public FsNode copy() {
        DirectoryNode twin = new DirectoryNode(name());
        for (FsNode child : children.values()) twin.add(child.copy());
        return twin;
    }

    @Override public void collect(NodeFilter filter, List<FsNode> out) {
        super.collect(filter, out);
        for (FsNode child : children.values()) child.collect(filter, out);
    }

    public FsNode child(String name) { return children.get(name); }
    public void add(FsNode node) { children.put(node.name(), node); node.setParent(this); }
    public void remove(FsNode node) { children.remove(node.name()); node.setParent(null); }
}

Resolving paths and moving a node

public final class PathResolver {
    /** Text only: it never looks at the tree. Returns an absolute path such as "/docs/work". */
    public String resolve(String cwd, String path) {
        if (path == null || path.isEmpty()) throw new FsException("INVALID");
        Deque<String> parts = new ArrayDeque<>();
        String start = path.startsWith("/") ? path : cwd + "/" + path;
        for (String part : start.split("/")) {
            if (part.isEmpty() || part.equals(".")) continue;
            if (part.equals("..")) parts.pollLast();     // at the root, pollLast does nothing
            else parts.addLast(part);
        }
        return "/" + String.join("/", parts);
    }
}

// Inside FileSystem
public void move(String from, String toDir) {
    FsNode node = lookup(from);
    DirectoryNode target = asDirectory(lookup(toDir));
    boolean movesRoot = node == root;
    boolean movesCurrentPlace = cwd.isInside(node);         // the current directory or one above it
    boolean movesIntoItself = target.isInside(node);        // the target is the node or below it
    if (movesRoot || movesCurrentPlace || movesIntoItself) throw new FsException("INVALID");
    if (target.child(node.name()) != null) throw new FsException("EXISTS");
    node.parent().remove(node);
    target.add(node);
}

private FsNode lookup(String path) {
    FsNode node = root;
    for (String part : resolver.resolve(cwd.path(), path).split("/")) {
        if (part.isEmpty()) continue;
        node = asDirectory(node).child(part);            // a file in the middle gives NOT_A_DIRECTORY
        if (node == null) throw new FsException("NOT_FOUND");
    }
    return node;
}

Search rules as strategies

public interface NodeFilter {
    boolean matches(FsNode node);
}

public final class NameFilter implements NodeFilter {
    private final String name;
    public NameFilter(String name) { this.name = name; }
    @Override public boolean matches(FsNode node) { return node.name().equals(name); }
}

public final class ExtensionFilter implements NodeFilter {
    private final String suffix;
    public ExtensionFilter(String extension) { this.suffix = "." + extension; }
    @Override public boolean matches(FsNode node) { return !node.isDirectory() && node.name().endsWith(suffix); }
}

// Inside FileSystem: the query "*.txt" picks the extension rule, anything else is a name.
public List<String> find(String startDir, String query) {
    NodeFilter filter = query.startsWith("*.") ? new ExtensionFilter(query.substring(2)) : new NameFilter(query);
    List<FsNode> hits = new ArrayList<>();
    lookup(startDir).collect(filter, hits);
    return hits.stream().map(FsNode::path).sorted().collect(Collectors.toList());
}

Deep dives

How to model files and directories

Weak: One Node class with a boolean isDirectory, a size field and a children list that is null for files. Every method starts with if (isDirectory). A file with children, or a directory with a size, is a bug the compiler cannot see.

Good: Two unrelated classes, File and Directory, and a Directory that holds List<Object>. Types are clear, but every walk over the tree needs instanceof checks and casts. Each new operation repeats them.

Great: An abstract FsNode with two subclasses, the Composite pattern. size() and copy() are abstract. FileNode answers directly, and DirectoryNode asks its children. Callers hold an FsNode and never check the type. A parent pointer on the node gives path() and the "is this inside that?" check for move and delete.

Trade-off: A parent pointer makes path() easy, but a move must update two links, the old parent's map and the node's own pointer. Forget one and the tree is wrong. Keep all changes inside add() and remove() so nobody changes links by hand.

Resolving relative paths and `..`

Weak: Walk the tree while reading the path. On .., go to the parent node. On ., stay. It works for simple cases, but a/../b fails if a does not exist, although it means the same as b. The parsing code and the tree code are tangled together.

Good: Split on / into a list. Keep a stack of names. A .. pops the last name, a . or an empty part is skipped, and anything else is pushed. The result is an absolute path. Only then look it up in the tree. Parsing now has no tree in it and is easy to test.

Great: Put that logic in its own PathResolver class with one method, resolve(cwd, path). Give it a clear rule for the root: .. at the root stays at the root. FileSystem calls it first in every operation, so no operation can forget it. Test it with a table of inputs and outputs, with no tree at all.

Trade-off: Cleaning the text first ignores what is really on disk. In a system with symbolic links, link/.. is not always the parent of link, so a real shell must look at the tree. For this problem, with no links, text-only resolution is simpler and gives the same answers.

Search by name or extension

Weak: Write findByName and findByExtension, each with its own copy of the tree walk. A third rule, such as "bigger than 1 MB", means a third copy. A fix in one walk is missed in the others.

Good: Write one walk that takes a NodeFilter, the Strategy pattern. NameFilter and ExtensionFilter are two small classes. The walk does not know what is being searched for. A new rule is a new class.

Great: Keep the walk inside the nodes, as collect(filter, out). A DirectoryNode collects itself and then each child, so the recursion lives with the structure. If you also need operations that return different results, such as size, a tree printout and search, a Visitor lets you add each as one class. Say that, and say why you did not use it here.

Trade-off: A Visitor makes new operations cheap and new node types costly, because every visitor must change. A filter keeps the code small while there is one operation, search, and many rules. With only two node types that will not change, either choice is fair. Pick the smaller one and be ready to explain it.

Now add one more feature

• Now add permissions: read, write and execute per node. What changes? `FsNode` gets a `Permissions` field. `FileSystem` checks it in one helper before it changes or reads a node, and throws `FsException(DENIED)`. The nodes themselves do not change.
• Now add symbolic links. What changes? Add a `LinkNode` that stores a target path and resolves it when followed. `lookup` follows links, with a limit on how many it follows, so a link to itself cannot loop forever. `PathResolver` can no longer use text only for `..` after a link.
• Now add undo for delete and move. What changes? Turn each operation into a command object with `execute()` and `undo()`. A delete keeps the removed node and its old parent. The `FileSystem` keeps a stack of commands.
• Now add search by size, such as 'files over 1 MB', and combine rules with AND and OR. What changes? Add `SizeFilter`, and `AndFilter` and `OrFilter` that hold other filters. The tree walk and the other filters stay the same.
• Now add a storage limit for the whole file system. What changes? `FileSystem` checks `root.size() + newSize` against the limit before it creates or copies, and throws `FsException(FULL)`. Keeping a running total on each directory makes the check cheap.

What each level is expected to show

SDE-1: A shared node type with a file class and a directory class, a directory that adds up its children for `size`, absolute and relative path handling, and the main operations with errors for bad input. A working `main` that builds a small tree is enough.

SDE-2: Everything at SDE-1, plus a separate path resolver with a clear root rule, and a filter strategy for search with the Visitor trade-off explained. Deep copy must not share nodes, and move must refuse a folder into itself. Discuss links, permissions and undo as extensions.

Common mistakes

• Using one `Node` class with `isDirectory` checks and a nullable children list, so every method repeats the same `if`.
• Copying a directory by adding the same child objects to the new parent. Both trees now share nodes, and a later delete changes both.
• Allowing a move of a directory into itself or one of its children. The subtree is cut off from the root and lost.
• Parsing `..` while walking the tree, so `a/../b` fails when `a` is missing, and the root has no rule for `..`.
• Computing a directory's size by hand with a loop in `FileSystem`, instead of asking the node. Each new node type then needs a change there.
• Throwing a generic exception or returning null, so the caller cannot tell a missing path from a file used as a directory.
• Deleting the directory the user is standing in, which leaves the current directory pointing at a node that is no longer in the tree.

Lessons behind this answer

• Facade
• Strategy
• Inheritance, composition and polymorphism
• From requirements to classes
• Iterator