1import type { FileDiffMetadata } from "@pierre/diffs";
2
3import { resolveFileDiffPath } from "~/lib/diffRendering";
4
5/**
6 * Which of the three reading passes a file belongs to.
7 *
8 * A reviewer reads the change itself first, then what proves it, and a lockfile or a build output
9 * only ever confirms what the source already said. Ordering by path alone buries the one file the
10 * change is really about under whichever directory happens to sort first.
11 */
12export type DiffFileTier = "source" | "test" | "generated";
13
14const GENERATED_FILE_NAMES = new Set([
15 "pnpm-lock.yaml",
16 "yarn.lock",
17 "package-lock.json",
18 "bun.lockb",
19 "Cargo.lock",
20 "go.sum",
21 "composer.lock",
22 "Gemfile.lock",
23]);
24const GENERATED_DIRECTORIES = new Set([
25 "__snapshots__",
26 "__generated__",
27 "dist",
28 "build",
29 "vendor",
30]);
31const TEST_DIRECTORIES = new Set(["__tests__", "tests", "test"]);
32const MODULE_EXTENSIONS = [".ts", ".tsx", ".js", ".jsx", ".mjs", ".cjs"];
33
34function diffFileTier(path: string): DiffFileTier {
35 const segments = path.split("/");
36 const name = segments.at(-1) ?? "";
37 if (
38 GENERATED_FILE_NAMES.has(name) ||
39 name.endsWith(".snap") ||
40 name.endsWith(".min.js") ||
41 name.endsWith(".min.css") ||
42 /\.generated\./.test(name) ||
43 segments.slice(0, -1).some((segment) => GENERATED_DIRECTORIES.has(segment))
44 ) {
45 return "generated";
46 }
47 if (
48 /\.(?:test|spec)\./.test(name) ||
49 segments.slice(0, -1).some((segment) => TEST_DIRECTORIES.has(segment))
50 ) {
51 return "test";
52 }
53 return "source";
54}
55
56function stripExtension(path: string): string {
57 const dot = path.lastIndexOf(".");
58 const slash = path.lastIndexOf("/");
59 return dot > slash ? path.slice(0, dot) : path;
60}
61
62function baseName(path: string): string {
63 return stripExtension(path.split("/").at(-1) ?? "");
64}
65
66/** Resolves `../x` against the importer's directory; no package resolution, only what git shows. */
67function resolveRelative(fromPath: string, specifier: string): string {
68 const segments = fromPath.split("/").slice(0, -1);
69 for (const part of specifier.split("/")) {
70 if (part === "." || part === "") continue;
71 if (part === "..") segments.pop();
72 else segments.push(part);
73 }
74 return segments.join("/");
75}
76
77// `import x from "y"`, `import "y"`, `export … from "y"` and `require("y")` all reduce to a quoted
78// specifier preceded by one of three words.
79const IMPORT_SPECIFIER = /(?:\bfrom|\bimport|\brequire\s*\()\s*\(?\s*["']([^"']+)["']/g;
80
81/** Which changed files a file's patch lines import, by path. */
82function importedPaths(
83 path: string,
84 lines: ReadonlyArray<string>,
85 byModulePath: ReadonlyMap<string, string>,
86 byBaseName: ReadonlyMap<string, string>,
87): ReadonlySet<string> {
88 const imported = new Set<string>();
89 for (const line of lines) {
90 IMPORT_SPECIFIER.lastIndex = 0;
91 let match = IMPORT_SPECIFIER.exec(line);
92 while (match !== null) {
93 const specifier = match[1] ?? "";
94 const withExtension = specifier.startsWith(".")
95 ? resolveRelative(path, specifier)
96 : specifier;
97 // A specifier may name the extension the module map dropped, and it need not be the one on
98 // disk: TypeScript's own imports point at the `.js` beside a `.ts`.
99 const extension = MODULE_EXTENSIONS.find((candidate) => withExtension.endsWith(candidate));
100 const resolved =
101 extension === undefined ? withExtension : withExtension.slice(0, -extension.length);
102 const target =
103 byModulePath.get(resolved) ??
104 byModulePath.get(`${resolved}/index`) ??
105 byBaseName.get(baseName(resolved));
106 if (target !== undefined && target !== path) imported.add(target);
107 match = IMPORT_SPECIFIER.exec(line);
108 }
109 }
110 return imported;
111}
112
113/**
114 * Source files with what they import ahead of what imports them.
115 *
116 * Kahn's, but every step takes the lowest remaining path rather than any ready node, so the same
117 * change always reads the same way and files of one directory stay together. A cycle leaves nothing
118 * ready: the lowest path still standing is taken anyway, which is the alphabetical order the tier
119 * would have had without a graph.
120 */
121function orderByImports(
122 paths: ReadonlyArray<string>,
123 imports: ReadonlyMap<string, ReadonlySet<string>>,
124): Array<string> {
125 const remaining = new Set(paths);
126 const ordered: Array<string> = [];
127 const sorted = [...paths].sort((left, right) => left.localeCompare(right));
128 while (remaining.size > 0) {
129 const candidates = sorted.filter((path) => remaining.has(path));
130 const next =
131 candidates.find((path) =>
132 [...(imports.get(path) ?? [])].every((dependency) => !remaining.has(dependency)),
133 ) ?? candidates[0]!;
134 remaining.delete(next);
135 ordered.push(next);
136 }
137 return ordered;
138}
139
140/** The implementation a test names: `foo.test.ts` and `__tests__/foo.ts` both point at `foo`. */
141function testedBaseName(path: string): string {
142 return (path.split("/").at(-1) ?? "").replace(/\.(?:test|spec)\..*$/, "").replace(/\.[^.]+$/, "");
143}
144
145/**
146 * Diff files in reading order: source in dependency order, then the tests that cover it, then
147 * whatever a tool wrote.
148 */
149export function orderDiffFiles(
150 files: ReadonlyArray<FileDiffMetadata>,
151): ReadonlyArray<FileDiffMetadata> {
152 const byPath = new Map<string, FileDiffMetadata>();
153 for (const file of files) byPath.set(resolveFileDiffPath(file), file);
154 const tiers = new Map<string, DiffFileTier>();
155 for (const path of byPath.keys()) tiers.set(path, diffFileTier(path));
156
157 const sourcePaths = [...byPath.keys()].filter((path) => tiers.get(path) === "source");
158 const byModulePath = new Map<string, string>();
159 const ambiguousBaseNames = new Set<string>();
160 const byBaseName = new Map<string, string>();
161 for (const path of sourcePaths) {
162 byModulePath.set(stripExtension(path), path);
163 const base = baseName(path);
164 if (byBaseName.has(base)) ambiguousBaseNames.add(base);
165 byBaseName.set(base, path);
166 }
167 for (const base of ambiguousBaseNames) byBaseName.delete(base);
168
169 const imports = new Map<string, ReadonlySet<string>>();
170 for (const path of sourcePaths) {
171 const file = byPath.get(path)!;
172 imports.set(
173 path,
174 importedPaths(path, [...file.additionLines, ...file.deletionLines], byModulePath, byBaseName),
175 );
176 }
177 const orderedSource = orderByImports(sourcePaths, imports);
178
179 const sourcePositions = new Map<string, number>();
180 orderedSource.forEach((path, index) => {
181 const base = baseName(path);
182 if (!sourcePositions.has(base)) sourcePositions.set(base, index);
183 });
184 const orderedTests = [...byPath.keys()]
185 .filter((path) => tiers.get(path) === "test")
186 .sort((left, right) => {
187 const leftPosition = sourcePositions.get(testedBaseName(left)) ?? Number.MAX_SAFE_INTEGER;
188 const rightPosition = sourcePositions.get(testedBaseName(right)) ?? Number.MAX_SAFE_INTEGER;
189 return leftPosition - rightPosition || left.localeCompare(right);
190 });
191
192 const orderedGenerated = [...byPath.keys()]
193 .filter((path) => tiers.get(path) === "generated")
194 .sort((left, right) => left.localeCompare(right));
195
196 return [...orderedSource, ...orderedTests, ...orderedGenerated].map((path) => byPath.get(path)!);
197}