Improve Cycle Detection

[hediet]

The scanner should find this:

bar.ts:

import { Foo } from "./foo"; // this is a runtime dependency
class Bar {
}

function foobar() {
  return new Foo();
}

foo.ts:

import * as bar from "./bar"; // this is a runtime+loadtime dependency
class Foo extends bar.Bar {} // this will throw if module "bar.ts" is loaded first!

---

...but not flag this:

bar.ts:

import { Foo } from "./foo"; // this is a runtime dependency
class Bar {
}

function foobar() {
  return new Foo();
}

foo.ts:

import * as bar from "./bar"; // runtime dependency
class Foo {
  createBar() {
     return new bar.Bar();
  }
}

---

When modules are loaded with cyclic dependencies, the cycle is broken up at loadtime at the first edge that would complete the cycle (the imported symbols of that edge are undefined when read).

We need to detect runtime cycles where one edge is a loadtime dependency, as these are the problematic ones.
A non-loadtime dependency cycle is fine, as we can break up the cycle at loadtime at any edge without causing problems, since the exported symbols are not accessed. A dependency cycle of only loadtime dependencies is also fine, as this will always crash, no matter where the cycle is broken up.
However, if there is only one loadtime dependency in a cycle, loading might crash if the cycle is broken up at that dependency, which might be hard to predict.

We need to over-approximate loadtime dependencies, by marking any runtime dependency of a module as "loadtime" if that module is not side-effect free (i.e. has static initializers or top level code).

---

Starting Point (should be fast on incremental program updates, e.g. by caching loadtime/runtime dependencies per source file):

function getCycles(p: ts.Program): { filename: string; error: string }[] {
	const tsApi = ts;
	const cycles: { filename: string; error: string }[] = [];

	const stack: string[] = [];
	const seen = new Set<string>();

	function visitSourceFile(sourceFile: ts.SourceFile): void {
		if (seen.has(sourceFile.fileName)) {
			// check stack -> report!
			const index = stack.indexOf(sourceFile.fileName);
			if (index !== -1) {
				const cycle = stack.slice(index);
				cycles.push({ filename: sourceFile.fileName, error: cycle.join(' -> ') });
			}
			return;
		}
		seen.add(sourceFile.fileName);
		stack.push(sourceFile.fileName);


		function getImports(sf: ts.SourceFile): ts.ImportDeclaration[] {
			return sf.statements.filter(s => ts.isImportDeclaration(s));
		}

		function resolveImport(decl: ts.ImportDeclaration): { resolvedFileName: string } | undefined {
			const result = (p as any).getResolvedModuleFromModuleSpecifier(decl.moduleSpecifier, sourceFile);
			if (!result || !result.resolvedModule) {
				console.error(`ERROR: Cannot resolve import ${decl.moduleSpecifier.getText()} in ${sourceFile.fileName}`);
				return undefined;
			}
			return { resolvedFileName: result.resolvedModule.resolvedFileName };
		}

		const imports = getImports(sourceFile);
		for (const decl of imports) {
			const resolvedFileName = resolveImport(decl);
			if (!resolvedFileName) {
				continue;
			}
			const resolvedPath = normalize(resolvedFileName.resolvedFileName);

			const refSf = p.getSourceFile(resolvedPath);
			if (!refSf) {
				console.error(`ERROR: Cannot find source file for reference ${resolvedPath} in ${sourceFile.fileName}`);
				continue;
			}
			visitSourceFile(refSf);
		}

		stack.pop();
	}

	for (const sourceFile of p.getSourceFiles()) {
		visitSourceFile(sourceFile);
	}

	return cycles;
}

function isSideEffectFree(sf: ts.SourceFile): { sideEffectFree: true, importedSymbolsUsedAtLoadingTime: Set<ts.Symbol> } | { sideEffectFree: false } {

}

Ideally, this should be also implemented (and tested) here: https://github.com/microsoft/vscode-ts-customized-language-service

FYI @jrieken