File size: 3,239 Bytes
a070805 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | export interface FileTreeNode {
name: string;
path: string; // full path relative to workspace root
isDirectory: boolean;
children: FileTreeNode[];
}
function sortTreeInPlace(node: FileTreeNode): void {
node.children.sort((a, b) => {
if (a.isDirectory !== b.isDirectory) return a.isDirectory ? -1 : 1;
return a.name.localeCompare(b.name);
});
for (const child of node.children) {
if (child.isDirectory) sortTreeInPlace(child);
}
}
/**
* Build a tree representation of a flat list of relative file paths.
* Directories are sorted before files; siblings are sorted alphabetically.
*
* Implementation notes:
* - We keep a side-table mapping each parent node to its own
* `Map<name, child>` so adding a segment is O(1) instead of the
* O(n) `children.find(...)` linear scan we used to do. With a
* directory containing 1000 siblings, the old code did ~500k string
* comparisons just to bucket them all in; the Map cuts that to
* ~1000. The side-table lives only for the duration of the build
* call so the public FileTreeNode shape stays clean.
* - If we encounter a path like `"src"` followed by `"src/index.ts"`,
* the first entry creates `src` as a file (`isDirectory: false`),
* then the second needs to add a child to it. We promote the leaf
* to a directory in that case rather than dropping the child on
* the floor. (The flat input shouldn't normally contain both, but
* defensive coding here is cheap and keeps the tree well-formed.)
*/
function getOrCreateChild(
parent: FileTreeNode,
childMap: Map<FileTreeNode, Map<string, FileTreeNode>>,
segment: string,
prefix: string,
isLast: boolean,
): FileTreeNode {
let map = childMap.get(parent);
if (!map) {
map = new Map();
childMap.set(parent, map);
}
const existing = map.get(segment);
if (existing) {
// Promote a leaf to a directory if we're about to descend into it.
if (!isLast && !existing.isDirectory) {
existing.isDirectory = true;
}
return existing;
}
const node: FileTreeNode = {
name: segment,
path: prefix,
isDirectory: !isLast,
children: [],
};
parent.children.push(node);
map.set(segment, node);
return node;
}
export function buildFileTree(paths: string[]): FileTreeNode {
const root: FileTreeNode = {
name: "",
path: "",
isDirectory: true,
children: [],
};
// Side-table mapping a parent node to its child lookup map. Keeping the
// accelerator out of the FileTreeNode shape itself means consumers never
// see it — no post-build cleanup pass, and the public type stays clean.
const childMap = new Map<FileTreeNode, Map<string, FileTreeNode>>();
for (const path of paths) {
const segments = path.split("/").filter(Boolean);
if (segments.length > 0) {
let cursor: FileTreeNode = root;
let prefix = "";
for (let i = 0; i < segments.length; i += 1) {
const segment = segments[i];
prefix = prefix ? `${prefix}/${segment}` : segment;
const isLast = i === segments.length - 1;
cursor = getOrCreateChild(cursor, childMap, segment, prefix, isLast);
}
}
}
sortTreeInPlace(root);
return root;
}
|