Skip to content

Commit 04083af

Browse files
committed
perf(shared): avoid pairwise scans for file link labels
1 parent d806251 commit 04083af

2 files changed

Lines changed: 84 additions & 15 deletions

File tree

‎packages/shared/src/fileLinks.test.ts‎

Lines changed: 75 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,85 @@
1-
import { describe, expect, it } from "vite-plus/test";
1+
import { describe, expect, it, vi } from "vite-plus/test";
22
import {
3+
buildFileLinkParentSuffixByPath,
34
fileLinkLabel,
45
parseFileUrlHref,
56
splitFilePathPosition,
67
resolvePathLinkTarget,
78
} from "./fileLinks.ts";
89

10+
describe("buildFileLinkParentSuffixByPath", () => {
11+
it.each([
12+
{
13+
paths: ["", "/", "index.ts", "/repo/src/index.ts"],
14+
suffixes: [["/repo/src/index.ts", "repo/src"]],
15+
},
16+
{ paths: ["/repo/a.ts", "/repo/b.ts", "/repo/a.ts"], suffixes: [] },
17+
{
18+
paths: ["/repo/src/index.ts", "/repo/test/index.ts"],
19+
suffixes: [
20+
["/repo/src/index.ts", "repo/src"],
21+
["/repo/test/index.ts", "repo/test"],
22+
],
23+
},
24+
{
25+
paths: ["/repo/a/src/index.ts", "/repo/b/src/index.ts"],
26+
suffixes: [
27+
["/repo/a/src/index.ts", "a/src"],
28+
["/repo/b/src/index.ts", "b/src"],
29+
],
30+
},
31+
{
32+
paths: ["/a/pkg/src/index.ts", "/b/pkg/src/index.ts"],
33+
suffixes: [
34+
["/a/pkg/src/index.ts", "a/pkg/src"],
35+
["/b/pkg/src/index.ts", "b/pkg/src"],
36+
],
37+
},
38+
{
39+
paths: ["src/index.ts", "/repo/src/index.ts"],
40+
suffixes: [
41+
["src/index.ts", "src"],
42+
["/repo/src/index.ts", "repo/src"],
43+
],
44+
},
45+
{
46+
paths: ["/repo//src/index.ts", "/repo/src/index.ts"],
47+
suffixes: [
48+
["/repo//src/index.ts", "repo/src"],
49+
["/repo/src/index.ts", "repo/src"],
50+
],
51+
},
52+
{ paths: [String.raw`C:\repo\src\index.ts`, "C:/repo/src/index.ts"], suffixes: [] },
53+
{
54+
paths: [String.raw`C:\repo\src\index.ts`, String.raw`D:\repo\src\index.ts`],
55+
suffixes: [
56+
["C:/repo/src/index.ts", "C:/repo/src"],
57+
["D:/repo/src/index.ts", "D:/repo/src"],
58+
],
59+
},
60+
{
61+
paths: [String.raw`\\one\share\src\index.ts`, String.raw`\\two\share\src\index.ts`],
62+
suffixes: [
63+
["//one/share/src/index.ts", "one/share/src"],
64+
["//two/share/src/index.ts", "two/share/src"],
65+
],
66+
},
67+
])("preserves suffixes for $paths", ({ paths, suffixes }) => {
68+
expect([...buildFileLinkParentSuffixByPath(paths)]).toEqual(suffixes);
69+
});
70+
71+
it("bounds suffix construction by path count for a same-basename group", () => {
72+
const paths = Array.from({ length: 128 }, (_, i) => `/repo/packages/pkg-${i}/src/index.ts`);
73+
using joins = vi.spyOn(Array.prototype, "join");
74+
const result = buildFileLinkParentSuffixByPath(paths);
75+
const suffixConstructions = joins.mock.calls.length;
76+
77+
expect(result).toEqual(new Map(paths.map((path, i) => [path, `pkg-${i}/src`])));
78+
// Count work instead of elapsed time so a pairwise scan fails on every machine.
79+
expect(suffixConstructions).toBeLessThan(paths.length * 20);
80+
});
81+
});
82+
983
describe("parseFileUrlHref", () => {
1084
it.each([
1185
[

‎packages/shared/src/fileLinks.ts‎

Lines changed: 9 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -135,31 +135,26 @@ export function buildFileLinkParentSuffixByPath(
135135
const parentSegmentsByPath = new Map(
136136
uniquePaths.map((filePath) => [filePath, pathParentSegments(filePath)]),
137137
);
138-
const minUniqueDepthByPath = new Map<string, number>();
138+
const suffixCounts = new Map<string, number>();
139+
for (const segments of parentSegmentsByPath.values()) {
140+
for (let depth = 1; depth <= segments.length; depth += 1) {
141+
const suffix = segments.slice(-depth).join("/");
142+
suffixCounts.set(suffix, (suffixCounts.get(suffix) ?? 0) + 1);
143+
}
144+
}
139145

140146
for (const filePath of uniquePaths) {
141147
const segments = parentSegmentsByPath.get(filePath) ?? [];
142148
let resolvedDepth = segments.length;
143149
for (let depth = 1; depth <= segments.length; depth += 1) {
144150
const candidate = segments.slice(-depth).join("/");
145-
const collision = uniquePaths.some((otherPath) => {
146-
if (otherPath === filePath) return false;
147-
const otherSegments = parentSegmentsByPath.get(otherPath) ?? [];
148-
return otherSegments.slice(-depth).join("/") === candidate;
149-
});
150-
if (!collision) {
151+
if (suffixCounts.get(candidate) === 1) {
151152
resolvedDepth = depth;
152153
break;
153154
}
154155
}
155-
minUniqueDepthByPath.set(filePath, resolvedDepth);
156-
}
157-
158-
for (const filePath of uniquePaths) {
159-
const segments = parentSegmentsByPath.get(filePath) ?? [];
160156
if (segments.length === 0) continue;
161-
const minUniqueDepth = minUniqueDepthByPath.get(filePath) ?? 1;
162-
const suffixDepth = Math.min(segments.length, Math.max(minUniqueDepth, 2));
157+
const suffixDepth = Math.min(segments.length, Math.max(resolvedDepth, 2));
163158
suffixByPath.set(filePath, segments.slice(-suffixDepth).join("/"));
164159
}
165160
}

0 commit comments

Comments
 (0)