PathTrie Class — astro Architecture

Source Code

packages/integrations/cloudflare/src/utils/generate-routes-json.ts lines 88–164

class PathTrie {
	root: TrieNode;
	returnHasWildcard = false;

	constructor() {
		this.root = new TrieNode();
	}

	insert(thisPath: string[]) {
		let node = this.root;
		for (const segment of thisPath) {
			if (segment === '*') {
				node.hasWildcardChild = true;
				break;
			}
			if (!node.children.has(segment)) {
				node.children.set(segment, new TrieNode());
			}

			node = node.children.get(segment)!;
		}

		node.isEndOfPath = true;
	}

	/**
	 * Depth-first search (dfs), traverses the "graph"  segment by segment until the end or wildcard (*).
	 * It makes sure that all necessary paths are returned, but not paths with an existing wildcard prefix.
	 * e.g. if we have a path like /foo/* and /foo/bar, we only want to return /foo/*
	 */
	private dfs(node: TrieNode, thisPath: string[], allPaths: string[][]): void {
		if (node.hasWildcardChild) {
			this.returnHasWildcard = true;
			allPaths.push([...thisPath, '*']);
			return;
		}

		if (node.isEndOfPath) {
			allPaths.push([...thisPath]);
		}

		for (const [segment, childNode] of node.children) {
			this.dfs(childNode, [...thisPath, segment], allPaths);
		}
	}

	/**
	 * The reduce function is used to remove unnecessary paths from the trie.
	 * It receives a trie node to compare with the current node.
	 */
	private reduce(compNode: TrieNode, node: TrieNode): void {
		if (node.hasWildcardChild || compNode.hasWildcardChild) return;

		for (const [segment, childNode] of node.children) {
			if (childNode.children.size === 0) continue;

			const compChildNode = compNode.children.get(segment);
			if (compChildNode === undefined) {
				childNode.hasWildcardChild = true;
				continue;
			}

			this.reduce(compChildNode, childNode);
		}
	}

	reduceAllPaths(compTrie: PathTrie): this {
		this.reduce(compTrie.root, this.root);
		return this;
	}

	getAllPaths(): [string[][], boolean] {
		const allPaths: string[][] = [];
		this.dfs(this.root, [], allPaths);
		return [allPaths, this.returnHasWildcard];
	}
}