File Search: composable filters, traversal and extensions

The file tree is in place, and the traversal over it has no type checks. Now the problem's real test: the search criteria. This lesson builds the filter design the round is scoring, writes the walk that uses it, and then shows how the finished design absorbs each extension question with new classes rather than edits.

The filter design

This is the insight the problem is testing. The same structure used for the file tree applies a second time, now to the search criteria.

The naive filter, and how it decays

Most first attempts produce something shaped like this:

1public class SearchCriteria {2    private String name;3    private String extension;4    private Long minSize;5    private Instant modifiedAfter;6}78public boolean matches(FileEntry f, SearchCriteria c) {9    if (c.name != null && !f.getName().equals(c.name)) return false;10    if (c.extension != null && !f.extension().equals(c.extension)) return false;11    if (c.minSize != null && f.size() < c.minSize) return false;12    if (c.modifiedAfter != null && f.getModifiedAt().isBefore(c.modifiedAfter)) return false;13    return true;14}

It works, and it fails three ways.

Adding a criterion edits two places — a field on SearchCriteria and a branch in matches. That violates requirement N1 directly.

It can only express AND. ".log files OR anything over 100 MB" has nowhere to go. Adding OR means adding a mode flag, and then nesting is impossible.

Every criterion is optional and null-checked, so the class carries four nulls to express one condition, and nothing stops a caller setting minSize above maxSize.

The repair: one interface, one method

public interface Filter {    boolean matches(FileSystemEntry entry);}

That is the whole contract. Each criterion becomes a small class that holds its own parameters:

1public class NameFilter implements Filter {2    private final Pattern pattern;                     // compiled from a glob3    private final boolean caseSensitive;4    public boolean matches(FileSystemEntry e) {5        String n = caseSensitive ? e.getName() : e.getName().toLowerCase();6        return pattern.matcher(n).matches();7    }8}910public class SizeFilter implements Filter {11    private final long min, max;                       // Long.MAX_VALUE for "no upper bound"12    public boolean matches(FileSystemEntry e) {13        long s = e.size();14        return s >= min && s <= max;15    }16}1718public class ModifiedAfterFilter implements Filter {19    private final Instant cutoff;20    public boolean matches(FileSystemEntry e) { return e.getModifiedAt().isAfter(cutoff); }21}

Each class holds exactly the parameters it needs. No nulls. No shared class to edit.

Composite, the second time

Now the move that makes this design good. The combinators are themselves filters, and they hold filters:

1public class AndFilter implements Filter {2    private final List<Filter> filters;3    public boolean matches(FileSystemEntry e) {4        return filters.stream().allMatch(f -> f.matches(e));    // short-circuits5    }6}78public class OrFilter implements Filter {9    private final List<Filter> filters;10    public boolean matches(FileSystemEntry e) {11        return filters.stream().anyMatch(f -> f.matches(e));12    }13}1415public class NotFilter implements Filter {16    private final Filter inner;17    public boolean matches(FileSystemEntry e) { return !inner.matches(e); }18}

Twelve lines, and the design is now complete. Any boolean expression over any criteria is a tree of these objects:

1// (*.log OR *.txt) AND larger than 10 MB AND NOT modified in the last day2Filter query = new AndFilter(List.of(3    new OrFilter(List.of(new ExtensionFilter("log"), new ExtensionFilter("txt"))),4    new SizeFilter(10L * 1024 * 1024, Long.MAX_VALUE),5    new NotFilter(new ModifiedAfterFilter(clock.now().minus(Duration.ofDays(1))))6));

FileSearcher sees one Filter. It has no idea whether it is holding a name check or a twelve-node expression tree, and it will never need to change again.

Why this is the same pattern twice

Say this out loud. "This is Composite again — the same shape as the file tree, applied to the criteria. A combinator is a filter that holds filters, so the searcher only ever sees one filter." Naming the repeat is what makes the answer look like understanding rather than recall.

Traversal and filtering, in code

Three things to write: the recursive walk, the iterative version for deep trees, and the optimisation about which directories to skip.

The recursive walk

With Composite in place, this is as short as promised:

1public class FileSearcher {2    public List<FileSystemEntry> search(Directory root, Filter filter) {3        List<FileSystemEntry> results = new ArrayList<>();4        walk(root, filter, results);5        return results;6    }78    private void walk(FileSystemEntry entry, Filter filter, List<FileSystemEntry> results) {9        if (filter.matches(entry)) results.add(entry);10        if (entry instanceof Directory dir) {11            for (FileSystemEntry child : dir.getChildren()) walk(child, filter, results);12        }13    }14}

One instanceof remains, and it is honest: only a directory has children to descend into. An alternative is a children() method on FileSystemEntry that returns an empty list for files, which removes the check at the cost of giving files a method that means nothing for them. Both are defensible; mention the trade-off and pick one.

The iterative version, for deep trees

Recursion depth equals tree depth. A stack overflow on a pathological tree — or an infinite one created by a symbolic link cycle — turns a search into a crash. An explicit stack removes the limit:

1public List<FileSystemEntry> searchIterative(Directory root, Filter filter) {2    List<FileSystemEntry> results = new ArrayList<>();3    Deque<FileSystemEntry> stack = new ArrayDeque<>();4    stack.push(root);5    while (!stack.isEmpty()) {6        FileSystemEntry entry = stack.pop();7        if (filter.matches(entry)) results.add(entry);8        if (entry instanceof Directory dir) {9            for (FileSystemEntry child : dir.getChildren()) stack.push(child);10        }11    }12    return results;13}

Same traversal, heap memory instead of stack memory. Swap push/pop for a queue's add/poll and you get breadth-first order, which finds shallow matches sooner — worth mentioning when the requirement is "first ten matches".

Where to apply the filter, and the subtle bug

Requirement N3 said not to descend directories that cannot match. The obvious implementation is wrong:

1// WRONG2if (entry instanceof Directory dir && filter.matches(dir)) {3    for (FileSystemEntry child : dir.getChildren()) walk(child, filter, results);4}

A filter for *.log does not match the directory /var/log/archive, so this skips the directory and finds nothing inside it. A directory failing the filter says nothing about its children.

The correct version separates two different questions — does this entry match? and could anything under here match? — with a second, optional interface:

1public interface PruningFilter extends Filter {2    boolean couldContainMatch(Directory dir);   // false ⇒ safe to skip the whole subtree3}45// In the walk:6if (entry instanceof Directory dir) {7    if (filter instanceof PruningFilter p && !p.couldContainMatch(dir)) return;  // prune8    for (FileSystemEntry child : dir.getChildren()) walk(child, filter, results);9}

Only filters that can honestly answer the second question implement it. A path-prefix filter can: nothing under /home can be inside /var/log. A size filter cannot — a small directory can contain a huge file. A name filter cannot.

That distinction is the interesting part of the traversal, and stating it — "a filter's verdict on a directory tells you nothing about its children unless the filter is about the path" — is the sentence worth saying.

Extensions

1. Content search (grep)

"Find .log files containing the word timeout" adds a filter that reads bytes:

1public class ContentFilter implements Filter {2    private final Pattern pattern;3    public boolean matches(FileSystemEntry e) {4        if (e.isDirectory()) return false;5        return contentReader.linesOf(e).anyMatch(line -> pattern.matcher(line).find());6    }7}

The design absorbs it with no changes — that is the payoff for the filter design above. But say the cost out loud: this filter is thousands of times more expensive than a name check, because it reads the file. So order matters inside AndFilter: evaluate cheap filters first so the expensive one runs on the few files that survive.

That is a two-line change with a large effect, and it is a good thing to volunteer:

public class AndFilter implements Filter {    private final List<Filter> filters;   // sorted by estimated cost, cheapest first}

Adding an estimatedCost() method to Filter lets AndFilter sort automatically. Mention it; implement it only if there is time.

2. Symbolic links and cycles

A symbolic link is a filesystem entry that points at another entry. Two consequences:

• A link to a parent directory creates an infinite tree. /a/b/link → /a means the walk never ends.
• The same file can be reached by several paths, so results contain duplicates.

Both are fixed by tracking visited identities — not paths, since the whole problem is that one file has several paths. Use the filesystem's inode number, or object identity in an in-memory model:

Set<Object> visited = Collections.newSetFromMap(new IdentityHashMap<>());if (!visited.add(entry)) return;    // already walked this one

Real find defaults to not following symbolic links for exactly this reason, and offers a flag to follow them. Mentioning that default is a nice domain touch.

3. Very large directories and streaming

Returning List<FileSystemEntry> means the whole result set is in memory before the caller sees anything. For a search matching two million files, that is a problem, and it also prevents the caller from stopping early.

Return a lazy stream or accept a callback instead:

public void search(Directory root, Filter filter, Consumer<FileSystemEntry> onMatch)// orpublic Stream<FileSystemEntry> searchLazily(Directory root, Filter filter)

The callback version is simpler and enough to make the point: the caller can stop by throwing, memory is constant, and the first result arrives immediately rather than after the full walk. This is the answer to "what if there are a hundred million files?" — which is the scale follow-up this problem attracts.

4. Visitor, for operations beyond search

If the requirement grows to "delete matches", "count by extension", "compute total size", then search is one operation among several over the same tree. Rather than adding a method to FileSystemEntry per operation, add a Visitor:

1public interface FileSystemVisitor<R> {2    R visitFile(FileEntry file);3    R visitDirectory(Directory dir);4}

Be honest about the trade-off, because it goes the opposite way to Composite: Visitor makes new operations cheap and new entry types expensive, since every visitor must gain a method when a type is added. In a filesystem there are exactly two entry types and they will never change, so that trade is favourable here. In a design where new types arrive regularly it would be the wrong choice.