Skip to content

Commit a7fcbcd

Browse files
RyanCavanaughRyanCavanaugh
committed
Use better toposorting algorithm
1 parent 1863d3f commit a7fcbcd

2 files changed

Lines changed: 130 additions & 115 deletions

File tree

‎src/compiler/tsbuild.ts‎

Lines changed: 88 additions & 97 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ namespace ts {
44
* specified like "./blah" to an absolute path to an actual
55
* tsconfig file, e.g. "/root/blah/tsconfig.json"
66
*/
7-
type ResolvedConfigFileName = string & { _isResolvedConfigFileName: never };
7+
export type ResolvedConfigFileName = string & { _isResolvedConfigFileName: never };
88

99
const minimumDate = new Date(-8640000000000000);
1010
const maximumDate = new Date(8640000000000000);
@@ -42,7 +42,7 @@ namespace ts {
4242

4343
type Mapper = ReturnType<typeof createDependencyMapper>;
4444
interface DependencyGraph {
45-
buildQueue: ResolvedConfigFileName[][];
45+
buildQueue: ResolvedConfigFileName[];
4646
dependencyMap: Mapper;
4747
}
4848

@@ -409,7 +409,8 @@ namespace ts {
409409
getUpToDateStatusOfFile,
410410
buildProjects,
411411
cleanProjects,
412-
resetBuildContext
412+
resetBuildContext,
413+
getBuildGraph
413414
};
414415

415416
function resetBuildContext(opts = defaultOptions) {
@@ -420,6 +421,13 @@ namespace ts {
420421
return getUpToDateStatus(configFileCache.parseConfigFile(configFileName));
421422
}
422423

424+
function getBuildGraph(configFileNames: string[]) {
425+
const resolvedNames: ResolvedConfigFileName[] | undefined = resolveProjectNames(configFileNames);
426+
if (resolvedNames === undefined) return;
427+
428+
return createDependencyGraph(resolvedNames);
429+
}
430+
423431
function getUpToDateStatus(project: ParsedCommandLine | undefined): UpToDateStatus {
424432
if (project === undefined) {
425433
return { type: UpToDateStatusType.Unbuildable, reason: "File deleted mid-build" };
@@ -583,66 +591,62 @@ namespace ts {
583591
};
584592
}
585593

586-
// TODO: Use the better algorithm
587-
function createDependencyGraph(roots: ResolvedConfigFileName[]): DependencyGraph {
588-
// This is a list of list of projects that need to be built.
589-
// The ordering here is "backwards", i.e. the first entry in the array is the last set of projects that need to be built;
590-
// and the last entry is the first set of projects to be built.
591-
// Each subarray is effectively unordered.
592-
// We traverse the reference graph from each root, then "clean" the list by removing
593-
// any entry that is duplicated to its right.
594-
const buildQueue: ResolvedConfigFileName[][] = [];
595-
const dependencyMap = createDependencyMapper();
596-
let buildQueuePosition = 0;
594+
function createDependencyGraph(roots: ResolvedConfigFileName[]): DependencyGraph | undefined {
595+
const temporaryMarks: { [path: string]: true } = {};
596+
const permanentMarks: { [path: string]: true } = {};
597+
const circularityReportStack: string[] = [];
598+
const buildOrder: ResolvedConfigFileName[] = [];
599+
const graph = createDependencyMapper();
600+
601+
let hadError = false;
602+
597603
for (const root of roots) {
598-
const config = configFileCache.parseConfigFile(root);
599-
if (config === undefined) {
600-
reportDiagnostic(createCompilerDiagnostic(Diagnostics.File_0_does_not_exist, root));
601-
continue;
602-
}
603-
enumerateReferences(normalizePath(root) as ResolvedConfigFileName, config);
604+
visit(root);
605+
}
606+
607+
if (hadError) {
608+
return undefined;
604609
}
605-
removeDuplicatesFromBuildQueue(buildQueue);
606610

607611
return {
608-
buildQueue,
609-
dependencyMap
612+
buildQueue: buildOrder,
613+
dependencyMap: graph
610614
};
611615

612-
function enumerateReferences(fileName: ResolvedConfigFileName, root: ParsedCommandLine): void {
613-
const myBuildLevel = buildQueue[buildQueuePosition] = buildQueue[buildQueuePosition] || [];
614-
if (myBuildLevel.indexOf(fileName) < 0) {
615-
myBuildLevel.push(fileName);
616-
}
617-
618-
const refs = root.projectReferences;
619-
if (refs === undefined) return;
620-
buildQueuePosition++;
621-
for (const ref of refs) {
622-
const actualPath = resolveProjectReferencePath(host, ref) as ResolvedConfigFileName;
623-
dependencyMap.addReference(fileName, actualPath);
624-
const resolvedRef = configFileCache.parseConfigFile(actualPath);
625-
if (resolvedRef === undefined) continue;
626-
enumerateReferences(normalizePath(actualPath) as ResolvedConfigFileName, resolvedRef);
616+
function visit(projPath: ResolvedConfigFileName, inCircularContext = false) {
617+
// Already visited
618+
if (permanentMarks[projPath]) return;
619+
// Circular
620+
if (temporaryMarks[projPath]) {
621+
if (!inCircularContext) {
622+
hadError = true;
623+
reportDiagnostic(createCompilerDiagnostic(Diagnostics.Project_references_may_not_form_a_circular_graph_Cycle_detected_Colon_0, circularityReportStack.join("\r\n")));
624+
return;
625+
}
627626
}
628-
buildQueuePosition--;
629-
}
630627

631-
/**
632-
* Removes entries from arrays which appear in later arrays.
633-
*/
634-
function removeDuplicatesFromBuildQueue(queue: string[][]): void {
635-
// No need to check the last array
636-
for (let i = 0; i < queue.length - 1; i++) {
637-
queue[i] = queue[i].filter(fn => !occursAfter(fn, i + 1));
628+
temporaryMarks[projPath] = true;
629+
circularityReportStack.push(projPath);
630+
const parsed = configFileCache.parseConfigFile(projPath);
631+
if (parsed === undefined) {
632+
hadError = true;
633+
return;
638634
}
639-
640-
function occursAfter(s: string, start: number) {
641-
for (let i = start; i < queue.length; i++) {
642-
if (queue[i].indexOf(s) >= 0) return true;
635+
if (parsed.projectReferences) {
636+
for (const ref of parsed.projectReferences) {
637+
const resolvedRefPath = resolveProjectName(ref.path);
638+
if (resolvedRefPath === undefined) {
639+
hadError = true;
640+
break;
641+
}
642+
visit(resolvedRefPath, inCircularContext || ref.circular);
643+
graph.addReference(projPath, resolvedRefPath);
643644
}
644-
return false;
645645
}
646+
647+
circularityReportStack.pop();
648+
permanentMarks[projPath] = true;
649+
buildOrder.push(projPath);
646650
}
647651
}
648652

@@ -762,20 +766,19 @@ namespace ts {
762766

763767
// Get the same graph for cleaning we'd use for building
764768
const graph = createDependencyGraph(resolvedNames);
769+
if (graph === undefined) return undefined;
765770

766771
const filesToDelete: string[] = [];
767-
for (const level of graph.buildQueue) {
768-
for (const proj of level) {
769-
const parsed = configFileCache.parseConfigFile(proj);
770-
if (parsed === undefined) {
771-
// File has gone missing; fine to ignore here
772-
continue;
773-
}
774-
const outputs = getAllProjectOutputs(parsed);
775-
for (const output of outputs) {
776-
if (host.fileExists(output)) {
777-
filesToDelete.push(output);
778-
}
772+
for (const proj of graph.buildQueue) {
773+
const parsed = configFileCache.parseConfigFile(proj);
774+
if (parsed === undefined) {
775+
// File has gone missing; fine to ignore here
776+
continue;
777+
}
778+
const outputs = getAllProjectOutputs(parsed);
779+
for (const output of outputs) {
780+
if (host.fileExists(output)) {
781+
filesToDelete.push(output);
779782
}
780783
}
781784
}
@@ -805,21 +808,27 @@ namespace ts {
805808
}
806809
}
807810

811+
function resolveProjectName(name: string): ResolvedConfigFileName | undefined {
812+
let fullPath = resolvePath(host.getCurrentDirectory(), name);
813+
if (host.fileExists(fullPath)) {
814+
return fullPath as ResolvedConfigFileName;
815+
}
816+
fullPath = combinePaths(fullPath, "tsconfig.json");
817+
if (host.fileExists(fullPath)) {
818+
return fullPath as ResolvedConfigFileName;
819+
}
820+
reportDiagnostic(createCompilerDiagnostic(Diagnostics.File_0_not_found, fullPath));
821+
return undefined;
822+
}
823+
808824
function resolveProjectNames(configFileNames: string[]): ResolvedConfigFileName[] | undefined {
809825
const resolvedNames: ResolvedConfigFileName[] = [];
810826
for (const name of configFileNames) {
811-
let fullPath = resolvePath(host.getCurrentDirectory(), name);
812-
if (host.fileExists(fullPath)) {
813-
resolvedNames.push(fullPath as ResolvedConfigFileName);
814-
continue;
815-
}
816-
fullPath = combinePaths(fullPath, "tsconfig.json");
817-
if (host.fileExists(fullPath)) {
818-
resolvedNames.push(fullPath as ResolvedConfigFileName);
819-
continue;
827+
const resolved = resolveProjectName(name);
828+
if (resolved === undefined) {
829+
return undefined;
820830
}
821-
reportDiagnostic(createCompilerDiagnostic(Diagnostics.File_0_not_found, fullPath));
822-
return undefined;
831+
resolvedNames.push(resolved);
823832
}
824833
return resolvedNames;
825834
}
@@ -830,12 +839,12 @@ namespace ts {
830839

831840
// Establish what needs to be built
832841
const graph = createDependencyGraph(resolvedNames);
842+
if (graph === undefined) return;
833843

834844
const queue = graph.buildQueue;
835845
reportBuildQueue(graph);
836846

837-
let next: ResolvedConfigFileName | undefined;
838-
while (next = getNext()) {
847+
for (const next of queue) {
839848
const proj = configFileCache.parseConfigFile(next);
840849
if (proj === undefined) {
841850
break;
@@ -866,21 +875,6 @@ namespace ts {
866875

867876
buildSingleProject(next);
868877
}
869-
870-
function getNext(): ResolvedConfigFileName | undefined {
871-
if (queue.length === 0) {
872-
return undefined;
873-
}
874-
while (queue.length > 0) {
875-
const last = queue[queue.length - 1];
876-
if (last.length === 0) {
877-
queue.pop();
878-
continue;
879-
}
880-
return last.pop()!;
881-
}
882-
return undefined;
883-
}
884878
}
885879

886880
/**
@@ -890,12 +884,9 @@ namespace ts {
890884
if (!context.options.verbose) return;
891885

892886
const names: string[] = [];
893-
for (const level of graph.buildQueue) {
894-
for (const el of level) {
895-
names.push(el);
896-
}
887+
for (const name of graph.buildQueue) {
888+
names.push(name);
897889
}
898-
names.reverse();
899890
context.verbose(Diagnostics.Sorted_list_of_input_projects_Colon_0, names.map(s => "\r\n * " + s).join(""));
900891
}
901892

‎src/harness/unittests/tsbuild.ts‎

Lines changed: 42 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -207,25 +207,49 @@ namespace ts {
207207
});
208208

209209
describe("tsbuild - graph-ordering", () => {
210-
it("orders the graph correctly", () => {
211-
const fs = new vfs.FileSystem(false);
212-
const host = new fakes.CompilerHost(fs);
213-
const deps: [string, string][] = [
214-
["A", "B"],
215-
["B", "C"],
216-
["A", "C"],
217-
["B", "D"],
218-
["C", "D"],
219-
["C", "E"],
220-
["F", "E"]
221-
];
222-
223-
writeProjects(fs, ["A", "B", "C", "D", "E", "F", "G"], deps);
224-
const builder = createSolutionBuilder(host, reportDiagnostic, { dry: true, force: false, verbose: false });
225-
builder.buildProjects(["/project/A", "/project/G"]);
226-
printDiagnostics();
210+
const fs = new vfs.FileSystem(false);
211+
const host = new fakes.CompilerHost(fs);
212+
const deps: [string, string][] = [
213+
["A", "B"],
214+
["B", "C"],
215+
["A", "C"],
216+
["B", "D"],
217+
["C", "D"],
218+
["C", "E"],
219+
["F", "E"]
220+
];
221+
222+
writeProjects(fs, ["A", "B", "C", "D", "E", "F", "G"], deps);
223+
224+
const builder = createSolutionBuilder(host, reportDiagnostic, { dry: true, force: false, verbose: false });
225+
226+
it("orders the graph correctly - specify two roots", () => {
227+
checkGraphOrdering(["A", "G"], ["A", "B", "C", "D", "E", "G"]);
227228
});
228229

230+
it("orders the graph correctly - multiple parts of the same graph in various orders", () => {
231+
// TODO add cases here
232+
});
233+
234+
function checkGraphOrdering(rootNames: string[], expectedBuildSet: string[]) {
235+
const projFileNames = rootNames.map(getProjectFileName);
236+
const graph = builder.getBuildGraph(projFileNames);
237+
if (graph === undefined) throw new Error("Graph shouldn't be undefined");
238+
239+
assert.sameMembers(graph.buildQueue, expectedBuildSet.map(getProjectFileName));
240+
241+
for (const dep of deps) {
242+
const child = getProjectFileName(dep[0]);
243+
if (graph.buildQueue.indexOf(child) < 0) continue;
244+
const parent = getProjectFileName(dep[1]);
245+
assert.isAbove(graph.buildQueue.indexOf(child), graph.buildQueue.indexOf(parent), `Expecting child ${child} to be built after parent ${parent}`);
246+
}
247+
}
248+
249+
function getProjectFileName(proj: string) {
250+
return `/project/${proj}/tsconfig.json` as ResolvedConfigFileName;
251+
}
252+
229253
function writeProjects(fileSystem: vfs.FileSystem, projectNames: string[], deps: [string, string][]): string[] {
230254
const projFileNames: string[] = [];
231255
for (const dep of deps) {
@@ -235,7 +259,7 @@ namespace ts {
235259
for (const proj of projectNames) {
236260
fileSystem.mkdirpSync(`/project/${proj}`);
237261
fileSystem.writeFileSync(`/project/${proj}/${proj}.ts`, "export {}");
238-
const configFileName = `/project/${proj}/tsconfig.json`;
262+
const configFileName = getProjectFileName(proj);
239263
const configContent = JSON.stringify({
240264
compilerOptions: { composite: true },
241265
files: [`./${proj}.ts`],

0 commit comments

Comments
 (0)