Files
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

82 lines
2.2 KiB
TypeScript

import type { NavigationNode } from "../types";
/**
* Flattens a navigation tree into a list of nodes in depth-first order,
* starting with the root node itself.
*
* @param root The root node of the tree to flatten.
* @returns the root node followed by all of its descendants, or an empty
* list when no root is given.
*/
export const flattenTree = (
root: NavigationNode | null | undefined
): NavigationNode[] => {
const flattened: NavigationNode[] = [];
const visit = (node: NavigationNode) => {
flattened.push(node);
node.children?.forEach(visit);
};
if (root) {
visit(root);
}
return flattened;
};
/**
* Returns the ancestors of a node, ordered from the root of the tree down to
* the node's direct parent. Nodes must have been annotated with a `parent`
* reference (see useCollectionTrees); nodes without one are treated as roots.
*
* @param node The node to return ancestors for.
* @returns the node's ancestors, or an empty list for a root node.
*/
export const ancestors = (
node: NavigationNode | null | undefined
): NavigationNode[] => {
const nodes: NavigationNode[] = [];
const seen = new Set<NavigationNode>();
if (node) {
seen.add(node);
}
let current = node?.parent;
while (current && !seen.has(current)) {
seen.add(current);
nodes.unshift(current);
current = current.parent;
}
return nodes;
};
/**
* Returns the descendants of a node in depth-first order, optionally limited
* to a maximum depth below the node.
*
* @param node The node to return descendants for.
* @param depth The maximum depth to descend to, where 1 returns direct
* children only. Defaults to 0, which returns all descendants.
* @returns the node's descendants, not including the node itself.
*/
export const descendants = (
node: NavigationNode,
depth = 0
): NavigationNode[] => {
const found: NavigationNode[] = [];
const visit = (child: NavigationNode, childDepth: number) => {
if (depth > 0 && childDepth > depth) {
return;
}
found.push(child);
child.children?.forEach((grandchild) => visit(grandchild, childDepth + 1));
};
node.children?.forEach((child) => visit(child, 1));
return found;
};