Repository / storage abstraction — name the question, not the container

The idea

Name the question, not the container

You reach for a HashMap and you are usually right. The decision that gets skipped is not where the data lives. It is who is allowed to ask.

corpus/file-system has eight operations and one six-method interface, PathResolver. Every operation asks it "what is at this path" and acts on the answer. None of them walks a directory's children itself.

Then a curveball adds shortcuts, so finding something can mean following a pointer. Measured cost: reference_diff 28, and one operation changed. read, ls, kindOf, exists, mkdir, mv and delete changed zero lines, because the thing that learned to follow pointers was the one place they all asked. Glob search cost 4 lines for the same reason. Eight operations each poking a map would have paid eight times.

The other half of the item is what one bypassed call site does. corpus/rate-limiter shipped that bug: remaining(key) read budgets.get(key) while tryAcquire went through Scopes. Two paths disagreed about who resolves a key, and the base suite passed 28 of 28 with the bug in place. seam-bypassed is a tracked defect tag for exactly this.

The threshold, because a lookup interface is genuinely overusable. Name it when three or more operations ask the same question about where something is, or when a requirement names a second place things could live. One caller over one map is a field, and wrapping it scores lower at D3 level 3, not higher.

Worked walkthrough

The five questions, and the lines that keep them the only way in

Fourteen files in worked/src including the driver, 649 lines, the longest 104. Run it:

.toolchain/jdk-21/bin/javac -Xlint:all -d out lessons/B5/worked/src/*.java && java -cp out Main

javac 21 with -Xlint:all prints nothing. What Main prints:

built the same ten paths on both stores: names read  tree 32  flat 23

reads: same question, same answer, and the flat map is cheaper
                                     tree           flat          names read
ls /                                [srv, tmp, var] [srv, tmp, var] 0 / 11
ls /var/log                         [app.log, err.log] [app.log, err.log] 2 / 11
read /var/log/app.log               [started, then reconfigured] [started, then reconfigured] 3 / 1
exists /srv/www/index.html          [true]         [true]         3 / 1
exists /nowhere                     [false]        [false]        1 / 1

structure changes: where the flat map stops being cheaper
mv /var /srv/var, then ls it        [app.log, err.log] [app.log, err.log] 7 / 24
delete /srv, then ls /              [tmp]          [tmp]          1 / 15

refusals: from the store, or from the operation
read /tmp                           IsADirectoryException: is a directory: /tmp
ls /tmp/notes.txt                   NotADirectoryException: not a directory: /tmp/notes.txt
mkdir /tmp                          PathAlreadyExistsException: path already exists: /tmp
delete /nowhere                     NoSuchPathException: no such path: /nowhere
mv /tmp /tmp/inside                 IllegalArgumentException: /tmp cannot be moved into its own subtree
ls var/log                          IllegalArgumentException: path must be absolute (start with '/'): var/log

names read in total   tree 54   flat 87

Two stores, one set of operations, and every answer in the two middle columns matches. Main throws an AssertionError if they ever stop matching, so that agreement is checked rather than claimed.

How the method list was chosen

Go through the operations and write down the question each one asks. Then keep the distinct questions and throw the rest away. That is the whole derivation:

Not one of those rows says "map", "tree", "table" or "row". A Map is one possible answer to "how do you find things", never the question. corpus/file-system/reference/src/PathResolver.java puts the same point in its own javadoc: the tree's storage is "a thing behind an interface rather than a Map field a dozen methods all reach into directly."

The reason the list is short is that the questions collapse. read and exists are the same question with different tolerance for a missing answer, so they are one method plus a default.

NodeStore.get — the default that stops the two stores disagreeing

    default Node get(String path) {
        return find(path).orElseThrow(() -> new NoSuchPathException(path));
    }

"Must exist" is find plus one refusal. Written twice, the two implementations get two chances to pick a different exception for the same situation. A caller writing catch (NoSuchPathException) would then work under one store and not the other. The default makes that divergence unavailable.

childNames returns names, and that is the load-bearing choice

The tempting signature is DirectoryNode getDirectory(String path), which is what the corpus's PathResolver actually returns. It can afford to: it has exactly one implementation, and that implementation stores children inside directories. Here there are two, and only TreeStore does.

So DirectoryNode.childNames() is a true answer under one store and an empty list under the other:

    /** The names directly under this directory, in name order. */
    List<String> childNames() {
        return List.copyOf(children.keySet());
    }

FlatStore never fills that map. It keeps the parent-child relation in its key strings, so under FlatStore a DirectoryNode is a marker saying "a directory is here" and nothing more. The narrower return type is the one both stores can honour, which is D1 and C5 doing work for B5.

The bypass, and why the base suite cannot see it

StoredFileSystem.ls is one line:

    List<String> ls(String path) {
        return store.childNames(path);
    }

The version a competent engineer writes when the seam is a habit rather than a rule is this, and it compiles:

        if (store.get(path) instanceof DirectoryNode dir) {
            return dir.childNames();
        }
        throw new NotADirectoryException(path);

Under TreeStore the two are indistinguishable. Under FlatStore the second answers [] for every directory, while read and exists on the same paths stay correct. Two paths through the same design disagree about who resolves a path.

Measured on this code. One suite of three tests built only on TreeStore, which is the shape a base suite takes when one implementation exists. Against faded/GapTest, which runs every assertion against both stores:

The left-hand column is reproducible, because that suite ships as worked/TreeOnlyTest.java:

.toolchain/jdk-21/bin/javac -cp .toolchain/junit-platform-console-standalone.jar -d out-test \
  lessons/B5/worked/src/*.java lessons/B5/worked/TreeOnlyTest.java
.toolchain/jdk-21/bin/java -jar .toolchain/junit-platform-console-standalone.jar \
  execute -cp out-test --select-class=TreeOnlyTest

Swap any gap in faded/src for the wrong answer named in GapTest, compile the same way, and watch it stay green. The both-stores column runs the same way against faded/solution.

Every wrong answer compiles, and every one of them passes a suite that only ever built one store. That is the same result corpus/rate-limiter/reference/DECISION_LOG.md records at full scale: remaining(key) read budgets.get(key) while tryAcquire went through Scopes, and "the base suite passed 28/28 with the bug in place." Its verdict is worth keeping: "A seam honoured by one of the two methods that answer questions about it is not a seam; it is a coincidence."

The bottom two rows are the mirror image, and they are the payoff. A change to how things are found lands inside one file, and the seven operations above it are not opened.

move belongs to the store, and the reason is not tidiness

mv keeps its own two refusals, because "the root cannot be moved" and "a directory cannot be moved into itself" are true whatever holds the nodes. What it hands over is the rehoming:

        store.move(from, to);

The hand-rolled alternative is store.put(to, store.get(from)); store.remove(from);. It works under TreeStore, because a subtree is reachable through its root and moving the root moves the subtree. Under FlatStore it rehomes one key and then remove deletes the descendants, which are still keyed under the old prefix. "Everything beneath this path" is a fact only a store has. Keep the operation that needs that fact on the interface.

Look at the two implementations side by side. TreeStore.move rewrites two child links and reads nothing under from. FlatStore.move scans every key twice and writes one per descendant. The driver prices it: the mv row costs 7 names read against 24.

The counters are on the implementations, not on the interface

    /** How many stored names this store has looked at since it was built. */
    long inspections() {
        return inspections;
    }

Declared on TreeStore and on FlatStore, and deliberately not on NodeStore. "How many names did you read" is a fact about one way of storing things, in units a future store may not have. Put it on the interface and every implementation owes a number it cannot honestly produce, which is the interface-segregation failure C5 is about. Main holds the two concrete types for this one line and holds NodeStore everywhere else.

Neither store is the wrong answer, and the numbers say so

corpus/file-system/reference/DECISION_LOG.md calls the flat map "the plausible wrong answer" and prices it: the map is O(everything in the file system) for ls, mv of a directory, and recursive delete. The driver reproduces that, and also the part the phrase hides. On point reads the flat map wins: read /var/log/app.log costs 3 names read against 1, because a tree walks a segment at a time and a map hashes once.

That is the honest shape of the trade. The flat map is cheaper for find and dearer for anything structural, and this problem's contract is built around ls, mv and recursive delete. Which is why the reference picks the tree — and why the choice being reversible for the cost of one file is worth more than the choice itself.

The corpus numbers, checked rather than quoted

Verified by reading the files, not the summaries:

So the claim "seven of the eight operations changed by zero lines" is not a rounding of something looser. mkdir, read, ls, mv, delete, exists and kindOf appear in neither hunk. 01-shortcuts/reference-patch/PATCH.md names the alternative price: with every operation resolving paths by hand, "every one of them would need its own copy of the follow-and-detect-a-cycle logic."

The 28 is worth keeping in view rather than hiding. It is the largest of the three, and PATCH.md argues why. A shortcut is a third kind of node where the problem said there were two, and 16 of the 28 lines are the cycle-detection algorithm itself. A seam does not make a requirement free. It decides how many files pay for it.

Not public, and that is a decision

NodeStore is declared without public, and it is not in a contract/ directory. So is PathResolver in corpus/file-system/reference/src, and so is EvictionPolicy in corpus/lru-cache/reference/src. corpus/lru-cache/reference/DECISION_LOG.md says why in its own terms. The cache never hands back its key set in any order. Doing so would leak "whichever EvictionPolicy's internal representation the cache happens to be running", which is what the policy seam exists to keep out of the contract.

A storage seam that appears in the public API has stopped hiding storage. It has published it.

What is deliberately not abstracted

• PathSyntax is static and not injected. Nothing in this problem varies about what a well-formed path is. Both stores call it, and neither would change if the rules did.
• No Path value type. A path is a String at the boundary and a List<String> once PathSyntax is finished with it. corpus/file-system's log makes the same call, and the phrase for a class holding two facts and no behaviour is "a class earning nothing."
• The three-way decision in write stays in write. Whether a write may replace what is at a path is a property of writing, not of finding. Moving it into the store would give the store a second reason to change.
• No lock. One caller at a time. Where one would go is settled, though, and that is a side effect worth having. The shared mutable state is whatever the store holds, and every read and write already passes through NodeStore.

When not to

When a map field is the right answer

Two of the twenty corpus problems keep their main collection as a bare field, and neither is a mistake.

    private final Map<String, Object> values = new HashMap<>();

That is corpus/lru-cache/reference/src/LruCache.java:35. No interface, no repository, no store. corpus/rate-limiter/reference/src/RateLimiter.java:67 does the same with a ConcurrentHashMap<ClientKey, KeyBudget>. Neither problem tags B5 in its problem.json, and both were reviewed by the same process that produced PathResolver.

Why they get away with it: in LruCache, three methods touch values, and all three are inside the class that owns the capacity rule they serve. There is no second place the values could live that the contract would recognise, and no other class asks where a value is. The map is a field because it is one class's private bookkeeping, which is what a field means.

The version that scores lower

A NodeStore in a design where one operation asks it a question is the shape to avoid. So is this, which is worse because it looks like progress:

interface NodeStore {
    Map<String, Node> nodes();
}

That names the container. Every caller now writes store.nodes().get(path), so the map is still public and the lookup rule is still copied at every call site. There is a file and an indirection to read before finding out that nothing was hidden. Swapping in a tree is not possible either, because the return type is the storage.

The next thing that arrives is a NodeStoreFactory returning the single implementation, and then a NodeStoreProvider returning the factory.

STANDARD v1.0 scores that. D3 level 3 requires a minimal seam set: "no speculative interface with a single implementation and no foreseeable second one." The failure tag is over-engineered, it is in rubric.mjs's closed D3 vocabulary alongside seam-bypassed, and doing more work scores less than doing none.

The shape that fails more slowly: a method per question

corpus/library/reference/src/LoanRepository.java warns about this in its own javadoc, because the library problem is where it nearly happened. The tempting interface is findByMember, findByIsbn, findByCopy, findOverdue:

That interface grows a method every time somebody asks the loans a new question.

Every one of those methods then has to be written again in every implementation. Its own conclusion: the seam that was meant to absorb change "becomes the thing change is charged to."

It shipped with four methods instead: save, find, remove, and outstanding(). Three base operations already needed exactly that last one, so it is not speculative. A new question is a filter over it, in a new file. Measured: curveball 03 wants a library-wide overdue report and a lending rule that refuses on it, and budget.json records reference_diff 5, two of which are the contract method's declaration.

The threshold

Name the lookup when at least one of these is true:

1. Three or more call sites ask the same "where is it" question. A rule that changes, such as following a pointer or folding case, starts costing more to copy than to name at about three. corpus/file-system has eight, which is why PathResolver was never in doubt.
2. A requirement names a second place things could live. A database, a file, a remote service. Named in the requirements, not imagined by you.
3. The answer needs a rule the callers should not each hold. TreeStore.find walks segments and stops at a file; nothing above it should know that.

Below all three, write the field. If the class later grows a third caller, extracting the interface then is a rename of the field's users, which is the cheapest refactor in Java.

The count that matters is callers, not implementations

PathResolver has exactly one implementation in corpus/file-system/reference/src, and its row in DECISION_LOG.md reads "never — it is a seam, not a policy". By the single-implementation test alone it would look premature. It is not, on two grounds, and both are checkable.

Eight callers, one question. The shortcuts curveball changed one operation out of eight because seven of them asked rather than walked. That number is the justification, and it was measured before the lesson was written.

It costs nothing at the API surface. PathResolver is declared without public and sits outside contract/, as does EvictionPolicy in corpus/lru-cache/reference/src. An internal seam can be deleted in an afternoon. A published one cannot, which is why the same interface can be right inside a package and over-engineering in a contract.

So the honest form of the rule is not "wait for a second implementation." It is: count the callers that ask, keep the interface out of the contract, and let the second implementation arrive whenever it likes.

Worked source

The 15 files of the worked design

Every file below is the one the app opens, verbatim. This is the part worth reading slowly: the prose above argues for a shape, and these are the lines that have it.

• worked/TreeOnlyTest.java 73 lines
• worked/src/DirectoryNode.java 44 lines
• worked/src/FileNode.java 17 lines
• worked/src/FileSystemException.java 15 lines
• worked/src/FlatStore.java 104 lines
• worked/src/IsADirectoryException.java 9 lines
• worked/src/NoSuchPathException.java 9 lines
• worked/src/Node.java 3 lines
• worked/src/NodeStore.java 79 lines
• worked/src/NotADirectoryException.java 9 lines
• worked/src/PathAlreadyExistsException.java 9 lines
• worked/src/PathSyntax.java 61 lines
• worked/src/StoredFileSystem.java 98 lines
• worked/src/TreeStore.java 88 lines
• worked/src/Main.java 104 lines

worked/TreeOnlyTest.java73 lines

import org.junit.jupiter.api.Test;

import java.util.List;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertThrows;

/**
 * The base suite this design would have if only one store existed. Three tests, every one of them
 * building a {@link TreeStore}, covering the same behaviour {@code faded/GapTest} covers.
 *
 * <p>It ships so the table in {@code NOTES.md} is reproducible rather than asserted. Fill any of the
 * four gaps in {@code faded/src} with the compiling wrong answer named in {@code GapTest} and this
 * suite still passes 3 of 3. That is the shape of the bug
 * {@code corpus/rate-limiter/reference/DECISION_LOG.md} records shipping: a bypassed seam is
 * invisible to a suite that only ever built one implementation.
 *
 * <p>It is not the lesson's grading suite. The app runs {@code faded/GapTest}, which asserts the
 * same things against both stores.
 */
class TreeOnlyTest {

    private static StoredFileSystem populated() {
        StoredFileSystem files = new StoredFileSystem(new TreeStore());
        files.mkdir("/var");
        files.mkdir("/var/log");
        files.write("/var/log/app.log", "started");
        files.write("/var/log/err.log", "none yet");
        files.mkdir("/srv");
        files.mkdir("/srv/www");
        files.write("/srv/www/index.html", "<h1>hello</h1>");
        files.mkdir("/tmp");
        return files;
    }

    @Test
    void lsListsDirectChildren() {
        StoredFileSystem files = populated();
        assertEquals(List.of("srv", "tmp", "var"), files.ls("/"));
        assertEquals(List.of("app.log", "err.log"), files.ls("/var/log"));
        assertEquals(List.of("log"), files.ls("/var"));
        assertEquals(List.of(), files.ls("/tmp"));
        assertThrows(NotADirectoryException.class, () -> files.ls("/var/log/app.log"));
        assertThrows(NoSuchPathException.class, () -> files.ls("/nowhere"));
    }

    @Test
    void mvMovesTheSubtree() {
        StoredFileSystem files = populated();
        files.mv("/var", "/srv/var");
        assertEquals(List.of("log"), files.ls("/srv/var"));
        assertEquals(List.of("app.log", "err.log"), files.ls("/srv/var/log"));
        assertEquals("started", files.read("/srv/var/log/app.log"));
        assertFalse(files.exists("/var"));
        assertFalse(files.exists("/var/log/app.log"));
        assertThrows(PathAlreadyExistsException.class, () -> files.mv("/tmp", "/srv"));
        assertThrows(NoSuchPathException.class, () -> files.mv("/nowhere", "/tmp/x"));
    }

    @Test
    void readWriteDeleteExists() {
        StoredFileSystem files = populated();
        files.write("/var/log/app.log", "restarted");
        assertEquals("restarted", files.read("/var/log/app.log"));
        files.delete("/var");
        assertFalse(files.exists("/var/log/app.log"));
        assertEquals(List.of("srv", "tmp"), files.ls("/"));
        assertThrows(IsADirectoryException.class, () -> files.read("/tmp"));
        assertThrows(PathAlreadyExistsException.class, () -> files.mkdir("/tmp"));
        assertThrows(IllegalArgumentException.class, () -> files.ls("var/log"));
    }
}

worked/src/DirectoryNode.java44 lines

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * A directory.
 *
 * <p>The children map is {@link TreeStore}'s bookkeeping and nobody else's. {@link FlatStore}
 * leaves it empty and keeps the parent-child relation in its key strings instead, so reading
 * this map from outside a store gives the right answer under one store and an empty list under
 * the other. That is why {@link NodeStore#childNames(String)} exists as a question rather than
 * as a getter on this class.
 */
final class DirectoryNode implements Node {

    private final Map<String, Node> children = new TreeMap<>();

    Node child(String name) {
        return children.get(name);
    }

    boolean hasChild(String name) {
        return children.containsKey(name);
    }

    /** The names directly under this directory, in name order. */
    List<String> childNames() {
        return List.copyOf(children.keySet());
    }

    /**
     * Refuses a name this directory already holds, every time, not only when the caller
     * happened to check first. A caller that forgot cannot leave two children under one name.
     */
    void addChild(String name, Node node) {
        if (children.putIfAbsent(name, node) != null) {
            throw new IllegalStateException("directory already has a child named '" + name + "'");
        }
    }

    Node removeChild(String name) {
        return children.remove(name);
    }
}

worked/src/FileNode.java17 lines

/** A file: its content, and nothing about where it sits. */
final class FileNode implements Node {

    private String content;

    FileNode(String content) {
        this.content = content;
    }

    String content() {
        return content;
    }

    void write(String content) {
        this.content = content;
    }
}

worked/src/FileSystemException.java15 lines

/**
 * The root of every failure that walking a well-formed path can produce.
 *
 * <p>A caller who does not care which of the four happened catches this. A malformed path is
 * deliberately not under here: that is {@code IllegalArgumentException}, a caller bug, and it
 * belongs to {@link PathSyntax} rather than to a store.
 */
abstract class FileSystemException extends RuntimeException {

    private static final long serialVersionUID = 1L;

    FileSystemException(String message) {
        super(message);
    }
}

worked/src/FlatStore.java104 lines

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.TreeMap;

/**
 * Nodes held in one map keyed by full path. The parent-child relation lives in the key strings,
 * so every question about structure is a scan.
 *
 * <p>This is the design {@code corpus/file-system/reference/DECISION_LOG.md} calls "the
 * plausible wrong answer" in its first seam, and it is here because it is the one a competent
 * engineer reaches for first. It is not wrong in the sense of broken: it passes every test
 * {@link TreeStore} passes. It is wrong in the sense of expensive, and the expense is confined
 * to this file.
 */
final class FlatStore implements NodeStore {

    private final Map<String, Node> nodes = new TreeMap<>();
    private long inspections;

    FlatStore() {
        nodes.put("/", new DirectoryNode());
    }

    @Override
    public Optional<Node> find(String path) {
        inspections++;
        return Optional.ofNullable(nodes.get(PathSyntax.canonical(path)));
    }

    @Override
    public List<String> childNames(String path) {
        String key = requireDirectory(path);
        String prefix = key.equals("/") ? "/" : key + "/";
        List<String> names = new ArrayList<>();
        for (String candidate : nodes.keySet()) {
            inspections++;
            if (candidate.startsWith(prefix)
                    && candidate.length() > prefix.length()
                    && candidate.indexOf('/', prefix.length()) < 0) {
                names.add(candidate.substring(prefix.length()));
            }
        }
        return List.copyOf(names);
    }

    @Override
    public void put(String path, Node node) {
        requireDirectory(PathSyntax.parent(path));
        String key = PathSyntax.canonical(path);
        if (find(path).isPresent()) {
            throw new PathAlreadyExistsException(path);
        }
        nodes.put(key, node);
    }

    @Override
    public void remove(String path) {
        String key = PathSyntax.canonical(path);
        if (find(path).isEmpty()) {
            throw new NoSuchPathException(path);
        }
        // A full scan, because "everything beneath this path" is a fact about key strings here.
        for (String candidate : List.copyOf(nodes.keySet())) {
            inspections++;
            if (candidate.equals(key) || candidate.startsWith(key + "/")) {
                nodes.remove(candidate);
            }
        }
    }

    @Override
    public void move(String from, String to) {
        get(from);
        if (find(to).isPresent()) {
            throw new PathAlreadyExistsException(to);
        }
        requireDirectory(PathSyntax.parent(to));
        String source = PathSyntax.canonical(from);
        String destination = PathSyntax.canonical(to);
        // Every key under the old prefix is rewritten. A second full scan, and a write for each
        // descendant, none of which changed in any way a caller would recognise.
        for (String candidate : List.copyOf(nodes.keySet())) {
            inspections++;
            if (candidate.equals(source) || candidate.startsWith(source + "/")) {
                nodes.put(destination + candidate.substring(source.length()), nodes.remove(candidate));
            }
        }
    }

    /** How many stored names this store has looked at since it was built. */
    long inspections() {
        return inspections;
    }

    /** The canonical key of an existing directory. */
    private String requireDirectory(String path) {
        if (!(get(path) instanceof DirectoryNode)) {
            throw new NotADirectoryException(path);
        }
        return PathSyntax.canonical(path);
    }
}

worked/src/IsADirectoryException.java9 lines

/** Something is at this path, and it is a directory where a file was needed. */
final class IsADirectoryException extends FileSystemException {

    private static final long serialVersionUID = 1L;

    IsADirectoryException(String path) {
        super("is a directory: " + path);
    }
}

worked/src/NoSuchPathException.java9 lines

/** Nothing is at this path. */
final class NoSuchPathException extends FileSystemException {

    private static final long serialVersionUID = 1L;

    NoSuchPathException(String path) {
        super("no such path: " + path);
    }
}

worked/src/Node.java3 lines

/** A node is a file or a directory. This problem gives no third kind. */
sealed interface Node permits FileNode, DirectoryNode {
}

worked/src/NodeStore.java79 lines

import java.util.List;
import java.util.Optional;

/**
 * Where nodes live, and how one is found. Five abstract methods and one default, and not one of
 * them mentions a map, a tree, a table or a file handle.
 *
 * <h2>The rule that produced this method list</h2>
 * Every method is a question an operation actually asks. {@code read} asks "what is at this
 * path". {@code ls} asks "what is directly under this directory". {@code mv} asks "put this
 * subtree over there". None of them asks "give me your map", because a map is one possible
 * answer to "how do you find things", not the question itself.
 *
 * <p>{@link TreeStore} answers by walking child links. {@link FlatStore} answers by inspecting
 * key strings in a {@code Map<String, Node>}. Both are correct. They differ in cost, and the
 * seven operations in {@link StoredFileSystem} cannot tell which one they are holding.
 *
 * <h2>Why {@code move} is here and not in the caller</h2>
 * Rehoming a subtree looks like the caller's business: get the node, put it there, remove the
 * old one. Under a tree that even works, because a subtree is reachable through its root and
 * moving the root moves the subtree. Under a flat map keyed by full path it silently drops
 * every descendant, since nothing rewrote their keys. "Everything beneath this path" is a fact
 * only the store knows, so the store owns the operation.
 *
 * <h2>Why {@code childNames} returns names and not nodes</h2>
 * Handing back {@code DirectoryNode} would tie every caller to the one store whose directories
 * hold their own children. The contract's {@code ls} wants names, so the question is names.
 * That is D1 and C5 as much as B5: the narrower return type is the one both stores can honour.
 *
 * <h2>Not public</h2>
 * This interface is package-private on purpose. It is an internal seam, not part of the API a
 * caller of the file system sees, exactly as {@code PathResolver} is in
 * {@code corpus/file-system/reference/src} and {@code EvictionPolicy} is in
 * {@code corpus/lru-cache/reference/src}. Both are declared without {@code public} and both
 * live outside their problem's {@code contract/} directory.
 */
interface NodeStore {

    /** The node at path, or empty if nothing is there. Never throws for "not there". */
    Optional<Node> find(String path);

    /**
     * The node at path, which must exist.
     *
     * <p>A default, because "must exist" is {@link #find} plus one refusal, and writing that
     * refusal twice invites the two stores to disagree about which exception a caller gets.
     */
    default Node get(String path) {
        return find(path).orElseThrow(() -> new NoSuchPathException(path));
    }

    /**
     * The names directly under the directory at path, in name order.
     *
     * @throws NoSuchPathException     if nothing is at path
     * @throws NotADirectoryException  if what is at path is not a directory
     */
    List<String> childNames(String path);

    /**
     * Stores node at path. The parent must already exist and be a directory, and path must be
     * free.
     *
     * @throws PathAlreadyExistsException if something is already at path
     */
    void put(String path, Node node);

    /** Forgets the node at path and everything beneath it. */
    void remove(String path);

    /**
     * Moves the node at path {@code from}, and everything beneath it, to {@code to}.
     *
     * <p>{@code to} must be free and its parent must be an existing directory. Whether the move
     * is legal in domain terms — moving a directory into itself, say — is the caller's question,
     * not this one.
     */
    void move(String from, String to);
}

worked/src/NotADirectoryException.java9 lines

/** Something is at this path, and it is not a directory. */
final class NotADirectoryException extends FileSystemException {

    private static final long serialVersionUID = 1L;

    NotADirectoryException(String path) {
        super("not a directory: " + path);
    }
}

worked/src/PathAlreadyExistsException.java9 lines

/** Something is already at this path. */
final class PathAlreadyExistsException extends FileSystemException {

    private static final long serialVersionUID = 1L;

    PathAlreadyExistsException(String path) {
        super("path already exists: " + path);
    }
}

worked/src/PathSyntax.java61 lines

import java.util.ArrayList;
import java.util.List;

/**
 * What makes a path well-formed, and how it splits. No store depends on which store you picked;
 * both of them below call this before they look anything up.
 */
final class PathSyntax {

    private PathSyntax() {
    }

    /** The non-empty names in an absolute path. "/" is the empty list. */
    static List<String> segments(String path) {
        if (path == null || !path.startsWith("/")) {
            throw new IllegalArgumentException("path must be absolute (start with '/'): " + path);
        }
        String body = path.length() > 1 && path.endsWith("/")
                ? path.substring(0, path.length() - 1)
                : path;
        if (body.equals("/")) {
            return List.of();
        }
        List<String> names = new ArrayList<>();
        for (String name : body.substring(1).split("/", -1)) {
            if (name.isEmpty()) {
                throw new IllegalArgumentException("path has an empty segment: " + path);
            }
            names.add(name);
        }
        return List.copyOf(names);
    }

    /** The path spelled from its segments: no trailing slash, exactly one leading slash. */
    static String join(List<String> segments) {
        return "/" + String.join("/", segments);
    }

    /** The one spelling of a path that a flat store can use as a key. */
    static String canonical(String path) {
        return join(segments(path));
    }

    /** The directory holding this path's last segment. "/f" gives "/". */
    static String parent(String path) {
        List<String> segments = segments(path);
        if (segments.isEmpty()) {
            throw new IllegalArgumentException("the root has no parent");
        }
        return join(segments.subList(0, segments.size() - 1));
    }

    /** The last segment of a path. "/var/log" gives "log". */
    static String leaf(String path) {
        List<String> segments = segments(path);
        if (segments.isEmpty()) {
            throw new IllegalArgumentException("the root has no name");
        }
        return segments.get(segments.size() - 1);
    }
}

worked/src/StoredFileSystem.java98 lines

import java.util.List;

/**
 * The seven operations. Every one of them is a short sequence: ask {@link NodeStore} where
 * something is, decide whether that is legal, tell the store what to change.
 *
 * <p>The discipline worth stating out loud, because it is the whole item: <b>no method here ever
 * reads a {@link DirectoryNode}'s children or holds a node it found by walking links itself.</b>
 * Everything goes through the store. Grep this file for {@code child}, {@code childNames} on a
 * node, or a cast to {@code DirectoryNode} used to get at structure — there are none.
 *
 * <p>The store is a constructor argument, so which one is running is decided in one place
 * ({@code Main}) rather than by this class.
 */
final class StoredFileSystem {

    private final NodeStore store;

    StoredFileSystem(NodeStore store) {
        this.store = store;
    }

    /** Creates a directory. The parent must already exist. */
    void mkdir(String path) {
        store.put(path, new DirectoryNode());
    }

    /**
     * Writes a file, replacing the file that is there.
     *
     * <p>The three-way decision stays here rather than moving into the store: "may a write
     * replace what is at this path" is a property of writing, not of finding.
     */
    void write(String path, String content) {
        Node existing = store.find(path).orElse(null);
        if (existing instanceof DirectoryNode) {
            throw new IsADirectoryException(path);
        }
        if (existing instanceof FileNode file) {
            file.write(content);
            return;
        }
        store.put(path, new FileNode(content));
    }

    /** The content of the file at path. */
    String read(String path) {
        Node node = store.get(path);
        if (node instanceof FileNode file) {
            return file.content();
        }
        throw new IsADirectoryException(path);
    }

    /** The names directly under the directory at path, in name order. */
    List<String> ls(String path) {
        return store.childNames(path);
    }

    /** Moves a node, and everything beneath it, to a path nothing occupies yet. */
    void mv(String from, String to) {
        if (PathSyntax.segments(from).isEmpty() || PathSyntax.segments(to).isEmpty()) {
            throw new IllegalArgumentException("the root can neither be moved nor moved onto");
        }
        if (isSelfOrDescendant(from, to)) {
            throw new IllegalArgumentException(from + " cannot be moved into its own subtree");
        }
        store.move(from, to);
    }

    /** Deletes a node and everything beneath it. */
    void delete(String path) {
        if (PathSyntax.segments(path).isEmpty()) {
            throw new IllegalArgumentException("the root cannot be deleted");
        }
        store.remove(path);
    }

    /** Whether anything is at path. A missing path is the answer here, not a failure. */
    boolean exists(String path) {
        return store.find(path).isPresent();
    }

    /** True if to is from itself, or lies anywhere underneath it. */
    private static boolean isSelfOrDescendant(String from, String to) {
        List<String> source = PathSyntax.segments(from);
        List<String> destination = PathSyntax.segments(to);
        if (destination.size() < source.size()) {
            return false;
        }
        for (int i = 0; i < source.size(); i++) {
            if (!source.get(i).equals(destination.get(i))) {
                return false;
            }
        }
        return true;
    }
}

worked/src/TreeStore.java88 lines

import java.util.List;
import java.util.Optional;

/**
 * Nodes held as a tree: every directory holds its own children, so a subtree is reachable only
 * through its root. This is the design {@code corpus/file-system/reference/src/TreeResolver}
 * uses.
 *
 * <p>{@code inspections()} counts names this store looked at while answering. It is declared
 * here and not on {@link NodeStore} because it is a fact about an implementation, not a question
 * about the file system, and putting it on the interface would force every future store to
 * report a number in units it does not have.
 */
final class TreeStore implements NodeStore {

    private final DirectoryNode root = new DirectoryNode();
    private long inspections;

    @Override
    public Optional<Node> find(String path) {
        Node current = root;
        for (String segment : PathSyntax.segments(path)) {
            if (!(current instanceof DirectoryNode directory)) {
                return Optional.empty();   // a file partway along the path blocks it
            }
            inspections++;
            current = directory.child(segment);
            if (current == null) {
                return Optional.empty();
            }
        }
        return Optional.of(current);
    }

    @Override
    public List<String> childNames(String path) {
        return directoryAt(path).childNames();
    }

    @Override
    public void put(String path, Node node) {
        DirectoryNode parent = directoryAt(PathSyntax.parent(path));
        String leaf = PathSyntax.leaf(path);
        inspections++;
        if (parent.hasChild(leaf)) {
            throw new PathAlreadyExistsException(path);
        }
        parent.addChild(leaf, node);
    }

    @Override
    public void remove(String path) {
        DirectoryNode parent = directoryAt(PathSyntax.parent(path));
        inspections++;
        if (parent.removeChild(PathSyntax.leaf(path)) == null) {
            throw new NoSuchPathException(path);
        }
        // Nothing else runs. The subtree was reachable only through the link just cut, so the
        // garbage collector reclaims it — which is what "recursive delete" costs when a
        // directory's children are stored inside it rather than rebuilt from key prefixes.
    }

    @Override
    public void move(String from, String to) {
        Node node = get(from);
        if (find(to).isPresent()) {
            throw new PathAlreadyExistsException(to);
        }
        DirectoryNode source = directoryAt(PathSyntax.parent(from));
        DirectoryNode destination = directoryAt(PathSyntax.parent(to));
        source.removeChild(PathSyntax.leaf(from));
        destination.addChild(PathSyntax.leaf(to), node);
        // Two links rewritten, whatever the subtree holds. Nothing under `from` was read.
    }

    /** How many stored names this store has looked at since it was built. */
    long inspections() {
        return inspections;
    }

    private DirectoryNode directoryAt(String path) {
        Node node = get(path);
        if (node instanceof DirectoryNode directory) {
            return directory;
        }
        throw new NotADirectoryException(path);
    }
}

worked/src/Main.java104 lines

import java.util.List;

/**
 * Runs one sequence of operations against both stores and prints the answers side by side.
 *
 * <p>The point of the driver is the middle columns: every answer matches, because the operations
 * asked questions rather than reading a container. The last column is what the choice of store
 * actually costs, counted in stored names looked at.
 */
public final class Main {

    private static long treeMark;
    private static long flatMark;

    public static void main(String[] args) {
        TreeStore tree = new TreeStore();
        FlatStore flat = new FlatStore();
        StoredFileSystem overTree = new StoredFileSystem(tree);
        StoredFileSystem overFlat = new StoredFileSystem(flat);

        build(overTree);
        build(overFlat);
        System.out.printf("built the same ten paths on both stores: names read  tree %d  flat %d%n%n",
                tree.inspections(), flat.inspections());
        mark(tree, flat);

        System.out.println("reads: same question, same answer, and the flat map is cheaper");
        System.out.println("                                     tree           flat          names read");
        answer("ls /", overTree.ls("/"), overFlat.ls("/"), tree, flat);
        answer("ls /var/log", overTree.ls("/var/log"), overFlat.ls("/var/log"), tree, flat);
        answer("read /var/log/app.log",
                List.of(overTree.read("/var/log/app.log")),
                List.of(overFlat.read("/var/log/app.log")), tree, flat);
        answer("exists /srv/www/index.html",
                List.of(String.valueOf(overTree.exists("/srv/www/index.html"))),
                List.of(String.valueOf(overFlat.exists("/srv/www/index.html"))), tree, flat);
        answer("exists /nowhere",
                List.of(String.valueOf(overTree.exists("/nowhere"))),
                List.of(String.valueOf(overFlat.exists("/nowhere"))), tree, flat);

        System.out.println();
        System.out.println("structure changes: where the flat map stops being cheaper");
        overTree.mv("/var", "/srv/var");
        overFlat.mv("/var", "/srv/var");
        answer("mv /var /srv/var, then ls it",
                overTree.ls("/srv/var/log"), overFlat.ls("/srv/var/log"), tree, flat);
        overTree.delete("/srv");
        overFlat.delete("/srv");
        answer("delete /srv, then ls /", overTree.ls("/"), overFlat.ls("/"), tree, flat);

        System.out.println();
        System.out.println("refusals: from the store, or from the operation");
        refusal("read /tmp", () -> overTree.read("/tmp"));
        refusal("ls /tmp/notes.txt", () -> overTree.ls("/tmp/notes.txt"));
        refusal("mkdir /tmp", () -> overTree.mkdir("/tmp"));
        refusal("delete /nowhere", () -> overTree.delete("/nowhere"));
        refusal("mv /tmp /tmp/inside", () -> overTree.mv("/tmp", "/tmp/inside"));
        refusal("ls var/log", () -> overTree.ls("var/log"));

        System.out.printf("%nnames read in total   tree %d   flat %d%n",
                tree.inspections(), flat.inspections());
    }

    /** The same ten paths, created through the same operations, on whichever store. */
    private static void build(StoredFileSystem files) {
        files.mkdir("/var");
        files.mkdir("/var/log");
        files.write("/var/log/app.log", "started");
        files.write("/var/log/app.log", "started, then reconfigured");
        files.write("/var/log/err.log", "none yet");
        files.mkdir("/srv");
        files.mkdir("/srv/www");
        files.write("/srv/www/index.html", "<h1>hello</h1>");
        files.mkdir("/tmp");
        files.write("/tmp/notes.txt", "scratch");
    }

    private static void answer(String label, List<String> fromTree, List<String> fromFlat,
                               TreeStore tree, FlatStore flat) {
        long treeCost = tree.inspections() - treeMark;
        long flatCost = flat.inspections() - flatMark;
        mark(tree, flat);
        System.out.printf("%-35s %-14s %-14s %d / %d%n",
                label, fromTree, fromFlat, treeCost, flatCost);
        if (!fromTree.equals(fromFlat)) {
            throw new AssertionError("the two stores disagreed about " + label);
        }
    }

    private static void mark(TreeStore tree, FlatStore flat) {
        treeMark = tree.inspections();
        flatMark = flat.inspections();
    }

    private static void refusal(String label, Runnable call) {
        try {
            call.run();
            System.out.printf("%-35s no refusal%n", label);
        } catch (RuntimeException refused) {
            System.out.printf("%-35s %s: %s%n",
                    label, refused.getClass().getSimpleName(), refused.getMessage());
        }
    }
}