Files
outline/shared/utils/tree.test.ts
T
Tom MoorandClaude Fable 5 c7a580fb8c Harden shared tree utilities and add test coverage (#12924)
* Harden shared tree utilities and add test coverage

- Fix ancestors() throwing a TypeError when a node's parent is undefined
  rather than null, which is the case for nodes that haven't been
  annotated by useCollectionTrees (e.g. shared trees from the server).
- Guard against malformed parent cycles in ancestors() so a bad tree can
  no longer hang the client.
- Compute descendants() depth limits relative to the given node during
  traversal instead of relying on optional absolute depth annotations,
  which silently returned an empty list when they were missing.
- Tolerate nodes without a children array in traversal.
- Remove type assertions, add JSDoc, and add collocated unit tests.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Vt5wWLYomgKZjfgPNk8wN4

* Address review: exclude node from own ancestors on parent cycles

- Seed the cycle guard with the starting node so a malformed parent
  cycle can never include the node in its own ancestor list.
- Widen flattenTree's parameter to accept nullish roots so the runtime
  guard and the type contract agree.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Vt5wWLYomgKZjfgPNk8wN4

---------

Co-authored-by: Claude <noreply@anthropic.com>
2026-07-11 06:22:42 -04:00

143 lines
3.7 KiB
TypeScript

import type { NavigationNode } from "../types";
import { ancestors, descendants, flattenTree } from "./tree";
const buildNode = (
id: string,
children: NavigationNode[] = []
): NavigationNode => ({
id,
title: `Title ${id}`,
url: `/doc/${id}`,
children,
});
/**
* Annotates a tree with the `parent` and `depth` fields added at runtime by
* useCollectionTrees, mirroring how nodes are prepared in the app.
*/
const annotate = (
node: NavigationNode,
parent: NavigationNode | null = null,
depth = 0
): NavigationNode => {
node.parent = parent;
node.depth = depth;
node.children.forEach((child) => annotate(child, node, depth + 1));
return node;
};
const buildTree = () =>
buildNode("root", [
buildNode("a", [buildNode("a1", [buildNode("a1i")]), buildNode("a2")]),
buildNode("b"),
]);
describe("#flattenTree", () => {
it("should return all nodes in depth-first order", () => {
expect(flattenTree(buildTree()).map((node) => node.id)).toEqual([
"root",
"a",
"a1",
"a1i",
"a2",
"b",
]);
});
it("should return a single node for a leaf", () => {
expect(flattenTree(buildNode("leaf")).map((node) => node.id)).toEqual([
"leaf",
]);
});
it("should tolerate nodes without a children array", () => {
const node: Partial<NavigationNode> = buildNode("orphan");
delete node.children;
expect(flattenTree(node as NavigationNode).map((n) => n.id)).toEqual([
"orphan",
]);
});
});
describe("#ancestors", () => {
it("should return ancestors ordered from root to direct parent", () => {
const root = annotate(buildTree());
const deepest = root.children[0].children[0].children[0];
expect(ancestors(deepest).map((node) => node.id)).toEqual([
"root",
"a",
"a1",
]);
});
it("should return an empty list for a root node", () => {
const root = annotate(buildTree());
expect(ancestors(root)).toEqual([]);
});
it("should return an empty list for a missing node", () => {
expect(ancestors(null)).toEqual([]);
});
it("should treat nodes without a parent annotation as roots", () => {
// Nodes straight from the server, e.g. a shared tree, carry no parent.
expect(ancestors(buildNode("unannotated"))).toEqual([]);
});
it("should not loop forever on a malformed parent cycle", () => {
const first = buildNode("first");
const second = buildNode("second");
first.parent = second;
second.parent = first;
// The node itself is never part of its own ancestors, even when the
// parent chain cycles back to it.
expect(ancestors(first).map((node) => node.id)).toEqual(["second"]);
});
});
describe("#descendants", () => {
it("should return all descendants by default", () => {
expect(descendants(buildTree()).map((node) => node.id)).toEqual([
"a",
"a1",
"a1i",
"a2",
"b",
]);
});
it("should limit results to the given depth", () => {
const root = buildTree();
expect(descendants(root, 1).map((node) => node.id)).toEqual(["a", "b"]);
expect(descendants(root, 2).map((node) => node.id)).toEqual([
"a",
"a1",
"a2",
"b",
]);
});
it("should limit by depth relative to the node itself", () => {
const root = annotate(buildTree());
const child = root.children[0];
expect(descendants(child, 1).map((node) => node.id)).toEqual(["a1", "a2"]);
});
it("should not require depth annotations on nodes", () => {
// Nodes straight from the server carry no depth annotation.
expect(descendants(buildTree(), 1).map((node) => node.id)).toEqual([
"a",
"b",
]);
});
it("should return an empty list for a leaf node", () => {
expect(descendants(buildNode("leaf"))).toEqual([]);
});
});