Repository: pmcelhaney/counterfact
Pull request #661 (2023-11-24 19:46:01)

fix edge case where a file shadows a directory
Say you have a directory structure like this:

```
- a
  - b.js
- a.js
```

The path for "a/b" would be handled by `a.js` instead of `a/b.js`. To fix, I completely rewrote the code to load and find modules and put it in a new class called ModuleTree. 


Patch:
diff --git a/.changeset/silent-boats-mate.md b/.changeset/silent-boats-mate.md
new file mode 100644
index 0000000..a8d2ddd
--- /dev/null
+++ b/.changeset/silent-boats-mate.md
@@ -0,0 +1,5 @@
+---
+"counterfact": patch
+---
+
+fixed an issue where if there was a directory and file with the same name, one would shadow the other
diff --git a/src/server/module-tree.ts b/src/server/module-tree.ts
new file mode 100644
index 0000000..1ae4d1f
--- /dev/null
+++ b/src/server/module-tree.ts
@@ -0,0 +1,234 @@
+import type { Module } from "./registry.js";
+
+interface File {
+  isWildcard: boolean;
+  module: Module;
+  name: string;
+  rawName: string;
+}
+
+interface Directory {
+  directories: { [key: string]: Directory };
+  files: { [key: string]: File };
+  isWildcard: boolean;
+  name: string;
+  rawName: string;
+}
+
+interface Match {
+  matchedPath: string;
+  module: Module;
+  pathVariables: { [key: string]: string };
+}
+
+function isDirectory(test: Directory | undefined): test is Directory {
+  return test !== undefined;
+}
+
+export class ModuleTree {
+  public readonly root: Directory = {
+    directories: {},
+    files: {},
+    isWildcard: false,
+    name: "",
+    rawName: "",
+  };
+
+  private addModuleToDirectory(
+    directory: Directory | undefined,
+    segments: string[],
+    module: Module,
+  ) {
+    if (directory === undefined) {
+      return;
+    }
+
+    const [segment, ...remainingSegments] = segments;
+
+    if (segment === undefined) {
+      throw new Error("segments array is empty");
+    }
+
+    if (remainingSegments.length === 0) {
+      directory.files[segment.toLowerCase()] = {
+        isWildcard: segment.startsWith("{"),
+        module,
+        name: segment.replace(/^\{(?<name>.*)\}$/u, "$<name>"),
+        rawName: segment,
+      };
+      return;
+    }
+
+    // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
+    directory.directories[segment.toLowerCase()] ??= {
+      directories: {},
+      files: {},
+      isWildcard: segment.startsWith("{"),
+      name: segment.replace(/^\{(?<name>.*)\}$/u, "$<name>"),
+      rawName: segment,
+    };
+    this.addModuleToDirectory(
+      directory.directories[segment.toLocaleLowerCase()],
+      remainingSegments,
+      module,
+    );
+  }
+
+  public add(url: string, module: Module) {
+    this.addModuleToDirectory(this.root, url.split("/").slice(1), module);
+  }
+
+  private removeModuleFromDirectory(
+    directory: Directory | undefined,
+    segments: string[],
+  ) {
+    if (!isDirectory(directory)) {
+      return;
+    }
+    const [segment, ...remainingSegments] = segments;
+
+    if (segment === undefined) {
+      return;
+    }
+
+    if (remainingSegments.length === 0) {
+      // eslint-disable-next-line @typescript-eslint/no-dynamic-delete
+      delete directory.files[segment.toLowerCase()];
+      return;
+    }
+    this.removeModuleFromDirectory(
+      directory.directories[segment.toLowerCase()],
+      remainingSegments,
+    );
+  }
+
+  public remove(url: string) {
+    const segments = url.split("/").slice(1);
+
+    this.removeModuleFromDirectory(this.root, segments);
+  }
+
+  // eslint-disable-next-line max-params
+  private buildMatch(
+    directory: Directory,
+    segment: string,
+    pathVariables: { [key: string]: string },
+    matchedPath: string,
+  ) {
+    const match =
+      directory.files[segment.toLowerCase()] ??
+      Object.values(directory.files).find((file) => file.isWildcard);
+
+    if (match === undefined) {
+      return undefined;
+    }
+
+    if (match.isWildcard) {
+      return {
+        ...match,
+
+        matchedPath: `${matchedPath}/${match.rawName}`,
+
+        pathVariables: {
+          ...pathVariables,
+          [match.name]: segment,
+        },
+      };
+    }
+
+    return {
+      ...match,
+
+      matchedPath: `${matchedPath}/${match.rawName}`,
+
+      pathVariables,
+    };
+  }
+
+  // eslint-disable-next-line max-statements, max-params
+  private matchWithinDirectory(
+    directory: Directory,
+    segments: string[],
+    pathVariables: { [key: string]: string },
+    matchedPath: string,
+  ): Match | undefined {
+    if (segments.length === 0) {
+      return undefined;
+    }
+    const [segment, ...remainingSegments] = segments;
+
+    if (segment === undefined) {
+      throw new Error(
+        "segment cannot be undefined but TypeScript doesn't know that",
+      );
+    }
+
+    if (remainingSegments.length === 0) {
+      return this.buildMatch(directory, segment, pathVariables, matchedPath);
+    }
+
+    const exactMatch = directory.directories[segment.toLowerCase()];
+
+    if (isDirectory(exactMatch)) {
+      return this.matchWithinDirectory(
+        exactMatch,
+        remainingSegments,
+        pathVariables,
+        `${matchedPath}/${segment}`,
+      );
+    }
+
+    const wildcardDirectory = Object.values(directory.directories).find(
+      (subdirectory) => subdirectory.isWildcard,
+    );
+
+    if (wildcardDirectory) {
+      return this.matchWithinDirectory(
+        wildcardDirectory,
+        remainingSegments,
+        {
+          ...pathVariables,
+          [wildcardDirectory.name]: segment,
+        },
+        `${matchedPath}/${wildcardDirectory.rawName}`,
+      );
+    }
+
+    return undefined;
+  }
+
+  public match(url: string) {
+    return this.matchWithinDirectory(
+      this.root,
+      url.split("/").slice(1),
+      {},
+      "",
+    );
+  }
+
+  public get routes(): string[] {
+    const routes: string[] = [];
+
+    function traverse(directory: Directory, path: string) {
+      Object.values(directory.directories).forEach((subdirectory) => {
+        traverse(subdirectory, `${path}/${subdirectory.rawName}`);
+      });
+
+      Object.values(directory.files).forEach((file) => {
+        routes.push(`${path}/${file.rawName}`);
+      });
+    }
+
+    // eslint-disable-next-line unicorn/consistent-function-scoping
+    function stripBrackets(string: string) {
+      return string.replaceAll(/\{|\}/gu, "");
+    }
+
+    traverse(this.root, "");
+
+    // eslint-disable-next-line etc/no-assign-mutated-array
+    return routes.sort((first, second) =>
+      stripBrackets(first).localeCompare(stripBrackets(second)),
+    );
+  }
+}
diff --git a/src/server/registry.ts b/src/server/registry.ts
index 9efc05d..dc42f2e 100644
--- a/src/server/registry.ts
+++ b/src/server/registry.ts
@@ -1,5 +1,6 @@
 import createDebugger from "debug";
 
+import { ModuleTree } from "./module-tree.js";
 import type { Tools } from "./tools.js";
 import type { MediaType, ResponseBuilderFactory } from "./types.d.ts";
 
@@ -46,11 +47,6 @@ interface Module {
   TRACE?: (requestData: RequestData) => CounterfactResponse;
 }
 
-interface Node {
-  children?: { [key: string]: Node };
-  module?: Module;
-}
-
 type CounterfactResponseObject =
   | string
   | {
@@ -96,123 +92,33 @@ function castParameters(
   return copy;
 }
 
-function maybe(flag: object | undefined, value: string): string[] {
-  return flag ? [value] : [];
-}
-
-function stripBrackets(string: string) {
-  return string.replaceAll(/\{|\}/gu, "");
-}
-
-function routesForNode(node: Node): string[] {
-  if (!node.children) {
-    return [];
-  }
-
-  return Object.entries(node.children)
-    .flatMap(([segment, child]) => [
-      ...maybe(child.module, `/${segment}`),
-      ...routesForNode(child).map((route) => `/${segment}${route}`),
-    ])
-    .sort((segment1, segment2) =>
-      stripBrackets(segment1).localeCompare(stripBrackets(segment2)),
-    );
-}
-
 export class Registry {
-  private readonly modules: { [key: string]: Module } = {};
-
-  public readonly moduleTree: Node = { children: {} };
+  private readonly moduleTree = new ModuleTree();
 
   public get routes() {
-    return routesForNode(this.moduleTree);
+    return this.moduleTree.routes;
   }
 
   public add(url: string, module: Module) {
-    let node: Node = this.moduleTree;
-
-    for (const segment of url.split("/").slice(1)) {
-      node.children ??= {};
-
-      // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
-      node.children[segment] ??= {};
-      // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
-      node = node.children[segment]!;
-    }
-
-    node.module = module;
+    this.moduleTree.add(url, module);
   }
 
   public remove(url: string) {
-    let node: Node | undefined = this.moduleTree;
-
-    for (const segment of url.split("/").slice(1)) {
-      node = node.children?.[segment];
-
-      if (!node) {
-        return false;
-      }
-    }
-
-    delete node.module;
-
-    return true;
+    this.moduleTree.remove(url);
   }
 
   public exists(method: HttpMethods, url: string) {
     return Boolean(this.handler(url).module?.[method]);
   }
 
-  // eslint-disable-next-line max-statements, sonarjs/cognitive-complexity
   public handler(url: string) {
-    let node: Node | undefined = this.moduleTree;
-
-    const path: { [key: string]: string } = {};
-
-    const matchedParts = [""];
-
-    for (const segment of url.split("/").slice(1)) {
-      if (node === undefined) {
-        throw new Error("node or node node.children cannot be undefined");
-      }
-
-      if (node.children === undefined) {
-        throw new Error("node or node node.children cannot be undefined");
-      }
-
-      const matchingChild = Object.keys(node.children).find(
-        (candidate) => candidate.toLowerCase() === segment.toLowerCase(),
-      );
-
-      debug("segment: %s", segment);
-      debug("matching child: %s", matchingChild);
-
-      if (matchingChild === undefined) {
-        const dynamicSegment: string | undefined = Object.keys(
-          node.children,
-        ).find((ds) => ds.startsWith("{") && ds.endsWith("}"));
+    const match = this.moduleTree.match(url);
 
-        if (dynamicSegment !== undefined) {
-          const variableName: string = dynamicSegment.slice(1, -1);
-
-          path[variableName] = segment;
-
-          node = node.children[dynamicSegment];
-
-          matchedParts.push(dynamicSegment);
-        }
-      } else {
-        node = node.children[matchingChild];
-
-        matchedParts.push(matchingChild);
-      }
-    }
-
-    if (node === undefined) {
-      throw new Error("node cannot be undefined");
-    }
-
-    return { matchedPath: matchedParts.join("/"), module: node.module, path };
+    return {
+      matchedPath: match?.matchedPath ?? "",
+      module: match?.module,
+      path: match?.pathVariables ?? {},
+    };
   }
 
   public endpoint(


Test patch:
diff --git a/test/server/module-tree.test.ts b/test/server/module-tree.test.ts
new file mode 100644
index 0000000..b6cb344
--- /dev/null
+++ b/test/server/module-tree.test.ts
@@ -0,0 +1,111 @@
+import { ModuleTree } from "../../src/server/module-tree.js";
+
+function add(moduleTree: ModuleTree, url: string, name: string) {
+  moduleTree.add(url, {
+    GET() {
+      return { body: name };
+    },
+  });
+}
+
+function match(moduleTree: ModuleTree, path: string) {
+  // @ts-expect-error - not creating an entire request object
+  // eslint-disable-next-line new-cap, @typescript-eslint/no-unsafe-return
+  return moduleTree.match(path)?.module.GET?.()?.body;
+}
+
+it("returns undefined for /", () => {
+  const moduleTree = new ModuleTree();
+  expect(match(moduleTree, "/")).toBe(undefined);
+});
+
+it("finds a file at the root", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a", "a");
+  expect(match(moduleTree, "/a")).toBe("a");
+});
+
+it("finds a file under a subdirectory", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a", "a");
+  add(moduleTree, "/a/b", "b");
+  expect(match(moduleTree, "/a")).toBe("a");
+  expect(match(moduleTree, "/a/b")).toBe("b");
+});
+
+it("finds a file with a wildcard match", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a", "a");
+  add(moduleTree, "/a/{x}", "b");
+  expect(match(moduleTree, "/a")).toBe("a");
+  expect(match(moduleTree, "/a/b")).toBe("b");
+});
+
+it("finds a directory with a wildcard match", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a", "a");
+  add(moduleTree, "/{x}/b", "b");
+  expect(match(moduleTree, "/a")).toBe("a");
+  expect(match(moduleTree, "/a/b")).toBe("b");
+});
+
+it("prefers an exact match to a wildcard", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a", "a");
+  add(moduleTree, "/a/b", "exact");
+  add(moduleTree, "/a/{x}", "wildcard");
+  expect(match(moduleTree, "/a")).toBe("a");
+  expect(match(moduleTree, "/a/b")).toBe("exact");
+});
+
+it("is case-insensitive", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a", "a");
+  add(moduleTree, "/a/b", "exact");
+  add(moduleTree, "/a/{x}", "wildcard");
+  expect(match(moduleTree, "/A")).toBe("a");
+  expect(match(moduleTree, "/A/B")).toBe("exact");
+});
+
+it("captures the path variables", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a/{foo}/{bar}", "wildcard");
+  expect(moduleTree.match("/a/b/c")?.pathVariables).toEqual({
+    bar: "c",
+    foo: "b",
+  });
+});
+
+it("captures the matched path", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a/b/c", "simple");
+  expect(moduleTree.match("/a/b/c")?.matchedPath).toEqual("/a/b/c");
+});
+
+it("captures the matched path with wildcards", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a/{foo}/{bar}", "wildcard");
+  expect(moduleTree.match("/a/b/c")?.matchedPath).toEqual("/a/{foo}/{bar}");
+});
+
+it("removes a module", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a", "a");
+  add(moduleTree, "/a/b", "b");
+  add(moduleTree, "/c", "c");
+  moduleTree.remove("/a/b");
+  moduleTree.remove("/c");
+  expect(match(moduleTree, "/a")).toBe("a");
+  expect(match(moduleTree, "/a/b")).toBe(undefined);
+  expect(match(moduleTree, "/c")).toBe(undefined);
+});
+
+it("has all of the routes", () => {
+  const moduleTree = new ModuleTree();
+  add(moduleTree, "/a", "a");
+  add(moduleTree, "/a/b", "b");
+  add(moduleTree, "/a/{b}", "b");
+  add(moduleTree, "/c", "c");
+  expect(moduleTree.routes).toEqual(["/a", "/a/b", "/a/{b}", "/c"]);
+});
+export default ModuleTree;
diff --git a/test/server/registry.test.ts b/test/server/registry.test.ts
index a191cfe..7aa9c79 100644
--- a/test/server/registry.test.ts
+++ b/test/server/registry.test.ts
@@ -1,30 +1,8 @@
 import {
-  type Module,
   Registry,
   type RequestDataWithBody,
 } from "../../src/server/registry.js";
 
-function makeModule(name: string): Module {
-  return {
-    GET() {
-      return name;
-    },
-  };
-}
-
-async function identifyModule(
-  node: { module?: Module } | undefined,
-): Promise<unknown> {
-  // @ts-expect-error - not creating an entire request object
-  // eslint-disable-next-line new-cap
-  return await node?.module?.GET?.({
-    headers: {},
-    matchedPath: "",
-    path: {},
-    query: {},
-  });
-}
-
 describe("a registry", () => {
   it("knows if a handler exists for a request method at a path", () => {
     const registry = new Registry();
@@ -98,30 +76,6 @@ describe("a registry", () => {
     expect(postB).toBe("POST b");
   });
 
-  it("constructs a tree of the registered modules", async () => {
-    const registry = new Registry();
-
-    registry.add("/nc", makeModule("North Carolina"));
-    registry.add("/nc/charlotte/south-park", makeModule("South Park"));
-    registry.add("/nc/charlotte", makeModule("Charlotte"));
-
-    expect(await identifyModule(registry.moduleTree.children?.nc)).toBe(
-      "North Carolina",
-    );
-    expect(
-      await identifyModule(
-        registry.moduleTree.children?.nc?.children?.charlotte,
-      ),
-    ).toBe("Charlotte");
-    expect(
-      await identifyModule(
-        registry.moduleTree.children?.nc?.children?.charlotte?.children?.[
-          "south-park"
-        ],
-      ),
-    ).toBe("South Park");
-  });
-
   it("handles a dynamic path", async () => {
     const registry = new Registry();