program.ts

namespace ts {
    export function findConfigFile(searchPath: string, fileExists: (fileName: string) => boolean, configName = "tsconfig.json"): string | undefined {
        return forEachAncestorDirectory(searchPath, ancestor => {
            const fileName = combinePaths(ancestor, configName);
            return fileExists(fileName) ? fileName : undefined;
        });
    }

    export function resolveTripleslashReference(moduleName: string, containingFile: string): string {
        const basePath = getDirectoryPath(containingFile);
        const referencedFileName = isRootedDiskPath(moduleName) ? moduleName : combinePaths(basePath, moduleName);
        return normalizePath(referencedFileName);
    }

    /* @internal */
    export function computeCommonSourceDirectoryOfFilenames(fileNames: readonly string[], currentDirectory: string, getCanonicalFileName: GetCanonicalFileName): string {
        let commonPathComponents: string[] | undefined;
        const failed = forEach(fileNames, sourceFile => {
            // Each file contributes into common source file path
            const sourcePathComponents = getNormalizedPathComponents(sourceFile, currentDirectory);
            sourcePathComponents.pop(); // The base file name is not part of the common directory path

            if (!commonPathComponents) {
                // first file
                commonPathComponents = sourcePathComponents;
                return;
            }

            const n = Math.min(commonPathComponents.length, sourcePathComponents.length);
            for (let i = 0; i < n; i++) {
                if (getCanonicalFileName(commonPathComponents[i]) !== getCanonicalFileName(sourcePathComponents[i])) {
                    if (i === 0) {
                        // Failed to find any common path component
                        return true;
                    }

                    // New common path found that is 0 -> i-1
                    commonPathComponents.length = i;
                    break;
                }
            }

            // If the sourcePathComponents was shorter than the commonPathComponents, truncate to the sourcePathComponents
            if (sourcePathComponents.length < commonPathComponents.length) {
                commonPathComponents.length = sourcePathComponents.length;
            }
        });

        // A common path can not be found when paths span multiple drives on windows, for example
        if (failed) {
            return "";
        }

        if (!commonPathComponents) { // Can happen when all input files are .d.ts files
            return currentDirectory;
        }

        return getPathFromPathComponents(commonPathComponents);
    }

    interface OutputFingerprint {
        hash: string;
        byteOrderMark: boolean;
        mtime: Date;
    }

    export function createCompilerHost(options: CompilerOptions, setParentNodes?: boolean): CompilerHost {
        return createCompilerHostWorker(options, setParentNodes);
    }

    /*@internal*/
    // TODO(shkamat): update this after reworking ts build API
    export function createCompilerHostWorker(options: CompilerOptions, setParentNodes?: boolean, system = sys): CompilerHost {
        const existingDirectories = new Map<string, boolean>();
        const getCanonicalFileName = createGetCanonicalFileName(system.useCaseSensitiveFileNames);
        const computeHash = maybeBind(system, system.createHash) || generateDjb2Hash;
        function getSourceFile(fileName: string, languageVersion: ScriptTarget, onError?: (message: string) => void): SourceFile | undefined {
            let text: string | undefined;
            try {
                performance.mark("beforeIORead");
                text = compilerHost.readFile(fileName);
                performance.mark("afterIORead");
                performance.measure("I/O Read", "beforeIORead", "afterIORead");
            }
            catch (e) {
                if (onError) {
                    onError(e.message);
                }
                text = "";
            }
            return text !== undefined ? createSourceFile(fileName, text, languageVersion, setParentNodes) : undefined;
        }

        function directoryExists(directoryPath: string): boolean {
            if (existingDirectories.has(directoryPath)) {
                return true;
            }
            if ((compilerHost.directoryExists || system.directoryExists)(directoryPath)) {
                existingDirectories.set(directoryPath, true);
                return true;
            }
            return false;
        }

        function writeFile(fileName: string, data: string, writeByteOrderMark: boolean, onError?: (message: string) => void) {
            try {
                performance.mark("beforeIOWrite");

                // NOTE: If patchWriteFileEnsuringDirectory has been called,
                // the system.writeFile will do its own directory creation and
                // the ensureDirectoriesExist call will always be redundant.
                writeFileEnsuringDirectories(
                    fileName,
                    data,
                    writeByteOrderMark,
                    (path, data, writeByteOrderMark) => writeFileWorker(path, data, writeByteOrderMark),
                    path => (compilerHost.createDirectory || system.createDirectory)(path),
                    path => directoryExists(path));

                performance.mark("afterIOWrite");
                performance.measure("I/O Write", "beforeIOWrite", "afterIOWrite");
            }
            catch (e) {
                if (onError) {
                    onError(e.message);
                }
            }
        }

        let outputFingerprints: ESMap<string, OutputFingerprint>;
        function writeFileWorker(fileName: string, data: string, writeByteOrderMark: boolean) {
            if (!isWatchSet(options) || !system.getModifiedTime) {
                system.writeFile(fileName, data, writeByteOrderMark);
                return;
            }

            if (!outputFingerprints) {
                outputFingerprints = new Map<string, OutputFingerprint>();
            }

            const hash = computeHash(data);
            const mtimeBefore = system.getModifiedTime(fileName);

            if (mtimeBefore) {
                const fingerprint = outputFingerprints.get(fileName);
                // If output has not been changed, and the file has no external modification
                if (fingerprint &&
                    fingerprint.byteOrderMark === writeByteOrderMark &&
                    fingerprint.hash === hash &&
                    fingerprint.mtime.getTime() === mtimeBefore.getTime()) {
                    return;
                }
            }

            system.writeFile(fileName, data, writeByteOrderMark);

            const mtimeAfter = system.getModifiedTime(fileName) || missingFileModifiedTime;

            outputFingerprints.set(fileName, {
                hash,
                byteOrderMark: writeByteOrderMark,
                mtime: mtimeAfter
            });
        }

        function getDefaultLibLocation(): string {
            return getDirectoryPath(normalizePath(system.getExecutingFilePath()));
        }

        const newLine = getNewLineCharacter(options, () => system.newLine);
        const realpath = system.realpath && ((path: string) => system.realpath!(path));
        const compilerHost: CompilerHost = {
            getSourceFile,
            getDefaultLibLocation,
            getDefaultLibFileName: options => combinePaths(getDefaultLibLocation(), getDefaultLibFileName(options)),
            writeFile,
            getCurrentDirectory: memoize(() => system.getCurrentDirectory()),
            useCaseSensitiveFileNames: () => system.useCaseSensitiveFileNames,
            getCanonicalFileName,
            getNewLine: () => newLine,
            fileExists: fileName => system.fileExists(fileName),
            readFile: fileName => system.readFile(fileName),
            trace: (s: string) => system.write(s + newLine),
            directoryExists: directoryName => system.directoryExists(directoryName),
            getEnvironmentVariable: name => system.getEnvironmentVariable ? system.getEnvironmentVariable(name) : "",
            getDirectories: (path: string) => system.getDirectories(path),
            realpath,
            readDirectory: (path, extensions, include, exclude, depth) => system.readDirectory(path, extensions, include, exclude, depth),
            createDirectory: d => system.createDirectory(d),
            createHash: maybeBind(system, system.createHash)
        };
        return compilerHost;
    }

    /*@internal*/
    interface CompilerHostLikeForCache {
        fileExists(fileName: string): boolean;
        readFile(fileName: string, encoding?: string): string | undefined;
        directoryExists?(directory: string): boolean;
        createDirectory?(directory: string): void;
        writeFile?: WriteFileCallback;
    }

    /*@internal*/
    export function changeCompilerHostLikeToUseCache(
        host: CompilerHostLikeForCache,
        toPath: (fileName: string) => Path,
        getSourceFile?: CompilerHost["getSourceFile"]
    ) {
        const originalReadFile = host.readFile;
        const originalFileExists = host.fileExists;
        const originalDirectoryExists = host.directoryExists;
        const originalCreateDirectory = host.createDirectory;
        const originalWriteFile = host.writeFile;
        const readFileCache = new Map<string, string | false>();
        const fileExistsCache = new Map<string, boolean>();
        const directoryExistsCache = new Map<string, boolean>();
        const sourceFileCache = new Map<string, SourceFile>();

        const readFileWithCache = (fileName: string): string | undefined => {
            const key = toPath(fileName);
            const value = readFileCache.get(key);
            if (value !== undefined) return value !== false ? value : undefined;
            return setReadFileCache(key, fileName);
        };
        const setReadFileCache = (key: Path, fileName: string) => {
            const newValue = originalReadFile.call(host, fileName);
            readFileCache.set(key, newValue !== undefined ? newValue : false);
            return newValue;
        };
        host.readFile = fileName => {
            const key = toPath(fileName);
            const value = readFileCache.get(key);
            if (value !== undefined) return value !== false ? value : undefined; // could be .d.ts from output
            // Cache json or buildInfo
            if (!fileExtensionIs(fileName, Extension.Json) && !isBuildInfoFile(fileName)) {
                return originalReadFile.call(host, fileName);
            }

            return setReadFileCache(key, fileName);
        };

        const getSourceFileWithCache: CompilerHost["getSourceFile"] | undefined = getSourceFile ? (fileName, languageVersion, onError, shouldCreateNewSourceFile) => {
            const key = toPath(fileName);
            const value = sourceFileCache.get(key);
            if (value) return value;

            const sourceFile = getSourceFile(fileName, languageVersion, onError, shouldCreateNewSourceFile);
            if (sourceFile && (isDeclarationFileName(fileName) || fileExtensionIs(fileName, Extension.Json))) {
                sourceFileCache.set(key, sourceFile);
            }
            return sourceFile;
        } : undefined;

        // fileExists for any kind of extension
        host.fileExists = fileName => {
            const key = toPath(fileName);
            const value = fileExistsCache.get(key);
            if (value !== undefined) return value;
            const newValue = originalFileExists.call(host, fileName);
            fileExistsCache.set(key, !!newValue);
            return newValue;
        };
        if (originalWriteFile) {
            host.writeFile = (fileName, data, writeByteOrderMark, onError, sourceFiles) => {
                const key = toPath(fileName);
                fileExistsCache.delete(key);

                const value = readFileCache.get(key);
                if (value !== undefined && value !== data) {
                    readFileCache.delete(key);
                    sourceFileCache.delete(key);
                }
                else if (getSourceFileWithCache) {
                    const sourceFile = sourceFileCache.get(key);
                    if (sourceFile && sourceFile.text !== data) {
                        sourceFileCache.delete(key);
                    }
                }
                originalWriteFile.call(host, fileName, data, writeByteOrderMark, onError, sourceFiles);
            };
        }

        // directoryExists
        if (originalDirectoryExists && originalCreateDirectory) {
            host.directoryExists = directory => {
                const key = toPath(directory);
                const value = directoryExistsCache.get(key);
                if (value !== undefined) return value;
                const newValue = originalDirectoryExists.call(host, directory);
                directoryExistsCache.set(key, !!newValue);
                return newValue;
            };
            host.createDirectory = directory => {
                const key = toPath(directory);
                directoryExistsCache.delete(key);
                originalCreateDirectory.call(host, directory);
            };
        }

        return {
            originalReadFile,
            originalFileExists,
            originalDirectoryExists,
            originalCreateDirectory,
            originalWriteFile,
            getSourceFileWithCache,
            readFileWithCache
        };
    }

    export function getPreEmitDiagnostics(program: Program, sourceFile?: SourceFile, cancellationToken?: CancellationToken): readonly Diagnostic[];
    /*@internal*/ export function getPreEmitDiagnostics(program: BuilderProgram, sourceFile?: SourceFile, cancellationToken?: CancellationToken): readonly Diagnostic[]; // eslint-disable-line @typescript-eslint/unified-signatures
    export function getPreEmitDiagnostics(program: Program | BuilderProgram, sourceFile?: SourceFile, cancellationToken?: CancellationToken): readonly Diagnostic[] {
        let diagnostics: Diagnostic[] | undefined;
        diagnostics = addRange(diagnostics, program.getConfigFileParsingDiagnostics());
        diagnostics = addRange(diagnostics, program.getOptionsDiagnostics(cancellationToken));
        diagnostics = addRange(diagnostics, program.getSyntacticDiagnostics(sourceFile, cancellationToken));
        diagnostics = addRange(diagnostics, program.getGlobalDiagnostics(cancellationToken));
        diagnostics = addRange(diagnostics, program.getSemanticDiagnostics(sourceFile, cancellationToken));

        if (getEmitDeclarations(program.getCompilerOptions())) {
            diagnostics = addRange(diagnostics, program.getDeclarationDiagnostics(sourceFile, cancellationToken));
        }

        return sortAndDeduplicateDiagnostics(diagnostics || emptyArray);
    }

    export interface FormatDiagnosticsHost {
        getCurrentDirectory(): string;
        getCanonicalFileName(fileName: string): string;
        getNewLine(): string;
    }

    export function formatDiagnostics(diagnostics: readonly Diagnostic[], host: FormatDiagnosticsHost): string {
        let output = "";

        for (const diagnostic of diagnostics) {
            output += formatDiagnostic(diagnostic, host);
        }
        return output;
    }

    export function formatDiagnostic(diagnostic: Diagnostic, host: FormatDiagnosticsHost): string {
        const errorMessage = `${diagnosticCategoryName(diagnostic)} TS${diagnostic.code}: ${flattenDiagnosticMessageText(diagnostic.messageText, host.getNewLine())}${host.getNewLine()}`;

        if (diagnostic.file) {
            const { line, character } = getLineAndCharacterOfPosition(diagnostic.file, diagnostic.start!); // TODO: GH#18217
            const fileName = diagnostic.file.fileName;
            const relativeFileName = convertToRelativePath(fileName, host.getCurrentDirectory(), fileName => host.getCanonicalFileName(fileName));
            return `${relativeFileName}(${line + 1},${character + 1}): ` + errorMessage;
        }

        return errorMessage;
    }

    /** @internal */
    export enum ForegroundColorEscapeSequences {
        Grey = "\u001b[90m",
        Red = "\u001b[91m",
        Yellow = "\u001b[93m",
        Blue = "\u001b[94m",
        Cyan = "\u001b[96m"
    }
    const gutterStyleSequence = "\u001b[7m";
    const gutterSeparator = " ";
    const resetEscapeSequence = "\u001b[0m";
    const ellipsis = "...";
    const halfIndent = "  ";
    const indent = "    ";
    function getCategoryFormat(category: DiagnosticCategory): ForegroundColorEscapeSequences {
        switch (category) {
            case DiagnosticCategory.Error: return ForegroundColorEscapeSequences.Red;
            case DiagnosticCategory.Warning: return ForegroundColorEscapeSequences.Yellow;
            case DiagnosticCategory.Suggestion: return Debug.fail("Should never get an Info diagnostic on the command line.");
            case DiagnosticCategory.Message: return ForegroundColorEscapeSequences.Blue;
        }
    }

    /** @internal */
    export function formatColorAndReset(text: string, formatStyle: string) {
        return formatStyle + text + resetEscapeSequence;
    }

    function formatCodeSpan(file: SourceFile, start: number, length: number, indent: string, squiggleColor: ForegroundColorEscapeSequences, host: FormatDiagnosticsHost) {
        const { line: firstLine, character: firstLineChar } = getLineAndCharacterOfPosition(file, start);
        const { line: lastLine, character: lastLineChar } = getLineAndCharacterOfPosition(file, start + length);
        const lastLineInFile = getLineAndCharacterOfPosition(file, file.text.length).line;

        const hasMoreThanFiveLines = (lastLine - firstLine) >= 4;
        let gutterWidth = (lastLine + 1 + "").length;
        if (hasMoreThanFiveLines) {
            gutterWidth = Math.max(ellipsis.length, gutterWidth);
        }

        let context = "";
        for (let i = firstLine; i <= lastLine; i++) {
            context += host.getNewLine();
            // If the error spans over 5 lines, we'll only show the first 2 and last 2 lines,
            // so we'll skip ahead to the second-to-last line.
            if (hasMoreThanFiveLines && firstLine + 1 < i && i < lastLine - 1) {
                context += indent + formatColorAndReset(padLeft(ellipsis, gutterWidth), gutterStyleSequence) + gutterSeparator + host.getNewLine();
                i = lastLine - 1;
            }

            const lineStart = getPositionOfLineAndCharacter(file, i, 0);
            const lineEnd = i < lastLineInFile ? getPositionOfLineAndCharacter(file, i + 1, 0) : file.text.length;
            let lineContent = file.text.slice(lineStart, lineEnd);
            lineContent = trimStringEnd(lineContent);  // trim from end
            lineContent = lineContent.replace(/\t/g, " ");   // convert tabs to single spaces

            // Output the gutter and the actual contents of the line.
            context += indent + formatColorAndReset(padLeft(i + 1 + "", gutterWidth), gutterStyleSequence) + gutterSeparator;
            context += lineContent + host.getNewLine();

            // Output the gutter and the error span for the line using tildes.
            context += indent + formatColorAndReset(padLeft("", gutterWidth), gutterStyleSequence) + gutterSeparator;
            context += squiggleColor;
            if (i === firstLine) {
                // If we're on the last line, then limit it to the last character of the last line.
                // Otherwise, we'll just squiggle the rest of the line, giving 'slice' no end position.
                const lastCharForLine = i === lastLine ? lastLineChar : undefined;

                context += lineContent.slice(0, firstLineChar).replace(/\S/g, " ");
                context += lineContent.slice(firstLineChar, lastCharForLine).replace(/./g, "~");
            }
            else if (i === lastLine) {
                context += lineContent.slice(0, lastLineChar).replace(/./g, "~");
            }
            else {
                // Squiggle the entire line.
                context += lineContent.replace(/./g, "~");
            }
            context += resetEscapeSequence;
        }
        return context;
    }

    /* @internal */
    export function formatLocation(file: SourceFile, start: number, host: FormatDiagnosticsHost, color = formatColorAndReset) {
        const { line: firstLine, character: firstLineChar } = getLineAndCharacterOfPosition(file, start); // TODO: GH#18217
        const relativeFileName = host ? convertToRelativePath(file.fileName, host.getCurrentDirectory(), fileName => host.getCanonicalFileName(fileName)) : file.fileName;

        let output = "";
        output += color(relativeFileName, ForegroundColorEscapeSequences.Cyan);
        output += ":";
        output += color(`${firstLine + 1}`, ForegroundColorEscapeSequences.Yellow);
        output += ":";
        output += color(`${firstLineChar + 1}`, ForegroundColorEscapeSequences.Yellow);
        return output;
    }

    export function formatDiagnosticsWithColorAndContext(diagnostics: readonly Diagnostic[], host: FormatDiagnosticsHost): string {
        let output = "";
        for (const diagnostic of diagnostics) {
            if (diagnostic.file) {
                const { file, start } = diagnostic;
                output += formatLocation(file, start!, host); // TODO: GH#18217
                output += " - ";
            }

            output += formatColorAndReset(diagnosticCategoryName(diagnostic), getCategoryFormat(diagnostic.category));
            output += formatColorAndReset(` TS${diagnostic.code}: `, ForegroundColorEscapeSequences.Grey);
            output += flattenDiagnosticMessageText(diagnostic.messageText, host.getNewLine());

            if (diagnostic.file) {
                output += host.getNewLine();
                output += formatCodeSpan(diagnostic.file, diagnostic.start!, diagnostic.length!, "", getCategoryFormat(diagnostic.category), host); // TODO: GH#18217
            }
            if (diagnostic.relatedInformation) {
                output += host.getNewLine();
                for (const { file, start, length, messageText } of diagnostic.relatedInformation) {
                    if (file) {
                        output += host.getNewLine();
                        output += halfIndent + formatLocation(file, start!, host); // TODO: GH#18217
                        output += formatCodeSpan(file, start!, length!, indent, ForegroundColorEscapeSequences.Cyan, host); // TODO: GH#18217
                    }
                    output += host.getNewLine();
                    output += indent + flattenDiagnosticMessageText(messageText, host.getNewLine());
                }
            }
            output += host.getNewLine();
        }
        return output;
    }

    export function flattenDiagnosticMessageText(diag: string | DiagnosticMessageChain | undefined, newLine: string, indent = 0): string {
        if (isString(diag)) {
            return diag;
        }
        else if (diag === undefined) {
            return "";
        }
        let result = "";
        if (indent) {
            result += newLine;

            for (let i = 0; i < indent; i++) {
                result += "  ";
            }
        }
        result += diag.messageText;
        indent++;
        if (diag.next) {
            for (const kid of diag.next) {
                result += flattenDiagnosticMessageText(kid, newLine, indent);
            }
        }
        return result;
    }

    /* @internal */
    export function loadWithLocalCache<T>(names: string[], containingFile: string, redirectedReference: ResolvedProjectReference | undefined, loader: (name: string, containingFile: string, redirectedReference: ResolvedProjectReference | undefined) => T): T[] {
        if (names.length === 0) {
            return [];
        }
        const resolutions: T[] = [];
        const cache = new Map<string, T>();
        for (const name of names) {
            let result: T;
            if (cache.has(name)) {
                result = cache.get(name)!;
            }
            else {
                cache.set(name, result = loader(name, containingFile, redirectedReference));
            }
            resolutions.push(result);
        }
        return resolutions;
    }

    /* @internal */
    interface SourceFileImportsList {
        imports: SourceFile["imports"];
        moduleAugmentations: SourceFile["moduleAugmentations"];
        impliedNodeFormat?: SourceFile["impliedNodeFormat"];
    };

    /* @internal */
    export function getModeForResolutionAtIndex(file: SourceFileImportsList, index: number) {
        if (file.impliedNodeFormat === undefined) return undefined;
        // we ensure all elements of file.imports and file.moduleAugmentations have the relevant parent pointers set during program setup,
        // so it's safe to use them even pre-bind
        return getModeForUsageLocation(file, getModuleNameStringLiteralAt(file, index));
    }

    /* @internal */
    export function getModeForUsageLocation(file: {impliedNodeFormat?: SourceFile["impliedNodeFormat"]}, usage: StringLiteralLike) {
        if (file.impliedNodeFormat === undefined) return undefined;
        if (file.impliedNodeFormat !== ModuleKind.ESNext) {
            // in cjs files, import call expressions are esm format, otherwise everything is cjs
            return isImportCall(walkUpParenthesizedExpressions(usage.parent)) ? ModuleKind.ESNext : ModuleKind.CommonJS;
        }
        // in esm files, import=require statements are cjs format, otherwise everything is esm
        // imports are only parent'd up to their containing declaration/expression, so access farther parents with care
        const exprParentParent = walkUpParenthesizedExpressions(usage.parent)?.parent;
        return exprParentParent && isImportEqualsDeclaration(exprParentParent) ? ModuleKind.CommonJS : ModuleKind.ESNext;
    }

    /* @internal */
    export function loadWithModeAwareCache<T>(names: string[], containingFile: SourceFile, containingFileName: string, redirectedReference: ResolvedProjectReference | undefined, loader: (name: string, resolverMode: ModuleKind.CommonJS | ModuleKind.ESNext | undefined, containingFileName: string, redirectedReference: ResolvedProjectReference | undefined) => T): T[] {
        if (names.length === 0) {
            return [];
        }
        const resolutions: T[] = [];
        const cache = new Map<string, T>();
        let i = 0;
        for (const name of names) {
            let result: T;
            const mode = getModeForResolutionAtIndex(containingFile, i);
            i++;
            const cacheKey = mode !== undefined ? `${mode}|${name}` : name;
            if (cache.has(cacheKey)) {
                result = cache.get(cacheKey)!;
            }
            else {
                cache.set(cacheKey, result = loader(name, mode, containingFileName, redirectedReference));
            }
            resolutions.push(result);
        }
        return resolutions;
    }

    /* @internal */
    export function forEachResolvedProjectReference<T>(
        resolvedProjectReferences: readonly (ResolvedProjectReference | undefined)[] | undefined,
        cb: (resolvedProjectReference: ResolvedProjectReference, parent: ResolvedProjectReference | undefined) => T | undefined
    ): T | undefined {
        return forEachProjectReference(/*projectReferences*/ undefined, resolvedProjectReferences, (resolvedRef, parent) => resolvedRef && cb(resolvedRef, parent));
    }

    function forEachProjectReference<T>(
        projectReferences: readonly ProjectReference[] | undefined,
        resolvedProjectReferences: readonly (ResolvedProjectReference | undefined)[] | undefined,
        cbResolvedRef: (resolvedRef: ResolvedProjectReference | undefined, parent: ResolvedProjectReference | undefined, index: number) => T | undefined,
        cbRef?: (projectReferences: readonly ProjectReference[] | undefined, parent: ResolvedProjectReference | undefined) => T | undefined
    ): T | undefined {
        let seenResolvedRefs: Set<Path> | undefined;

        return worker(projectReferences, resolvedProjectReferences, /*parent*/ undefined);

        function worker(
            projectReferences: readonly ProjectReference[] | undefined,
            resolvedProjectReferences: readonly (ResolvedProjectReference | undefined)[] | undefined,
            parent: ResolvedProjectReference | undefined,
        ): T | undefined {

            // Visit project references first
            if (cbRef) {
                const result = cbRef(projectReferences, parent);
                if (result) return result;
            }

            return forEach(resolvedProjectReferences, (resolvedRef, index) => {
                if (resolvedRef && seenResolvedRefs?.has(resolvedRef.sourceFile.path)) {
                    // ignore recursives
                    return undefined;
                }

                const result = cbResolvedRef(resolvedRef, parent, index);
                if (result || !resolvedRef) return result;

                (seenResolvedRefs ||= new Set()).add(resolvedRef.sourceFile.path);
                return worker(resolvedRef.commandLine.projectReferences, resolvedRef.references, resolvedRef);
            });
        }
    }

    /* @internal */
    export const inferredTypesContainingFile = "__inferred type names__.ts";

    interface DiagnosticCache<T extends Diagnostic> {
        perFile?: ESMap<Path, readonly T[]>;
        allDiagnostics?: readonly T[];
    }

    /*@internal*/
    export function isReferencedFile(reason: FileIncludeReason | undefined): reason is ReferencedFile {
        switch (reason?.kind) {
            case FileIncludeKind.Import:
            case FileIncludeKind.ReferenceFile:
            case FileIncludeKind.TypeReferenceDirective:
            case FileIncludeKind.LibReferenceDirective:
                return true;
            default:
                return false;
        }
    }

    /*@internal*/
    export interface ReferenceFileLocation {
        file: SourceFile;
        pos: number;
        end: number;
        packageId: PackageId | undefined;
    }

    /*@internal*/
    export interface SyntheticReferenceFileLocation {
        file: SourceFile;
        packageId: PackageId | undefined;
        text: string;
    }

    /*@internal*/
    export function isReferenceFileLocation(location: ReferenceFileLocation | SyntheticReferenceFileLocation): location is ReferenceFileLocation {
        return (location as ReferenceFileLocation).pos !== undefined;
    }

    /*@internal*/
    export function getReferencedFileLocation(getSourceFileByPath: (path: Path) => SourceFile | undefined, ref: ReferencedFile): ReferenceFileLocation | SyntheticReferenceFileLocation {
        const file = Debug.checkDefined(getSourceFileByPath(ref.file));
        const { kind, index } = ref;
        let pos: number | undefined, end: number | undefined, packageId: PackageId | undefined;
        switch (kind) {
            case FileIncludeKind.Import:
                const importLiteral = getModuleNameStringLiteralAt(file, index);
                packageId = file.resolvedModules?.get(importLiteral.text, getModeForResolutionAtIndex(file, index))?.packageId;
                if (importLiteral.pos === -1) return { file, packageId, text: importLiteral.text };
                pos = skipTrivia(file.text, importLiteral.pos);
                end = importLiteral.end;
                break;
            case FileIncludeKind.ReferenceFile:
                ({ pos, end } = file.referencedFiles[index]);
                break;
            case FileIncludeKind.TypeReferenceDirective:
                ({ pos, end } = file.typeReferenceDirectives[index]);
                packageId = file.resolvedTypeReferenceDirectiveNames?.get(toFileNameLowerCase(file.typeReferenceDirectives[index].fileName), file.impliedNodeFormat)?.packageId;
                break;
            case FileIncludeKind.LibReferenceDirective:
                ({ pos, end } = file.libReferenceDirectives[index]);
                break;
            default:
                return Debug.assertNever(kind);
        }
        return { file, pos, end, packageId };
    }

    /**
     * Determines if program structure is upto date or needs to be recreated
     */
    /* @internal */
    export function isProgramUptoDate(
        program: Program | undefined,
        rootFileNames: string[],
        newOptions: CompilerOptions,
        getSourceVersion: (path: Path, fileName: string) => string | undefined,
        fileExists: (fileName: string) => boolean,
        hasInvalidatedResolution: HasInvalidatedResolution,
        hasChangedAutomaticTypeDirectiveNames: HasChangedAutomaticTypeDirectiveNames | undefined,
        getParsedCommandLine: (fileName: string) => ParsedCommandLine | undefined,
        projectReferences: readonly ProjectReference[] | undefined
    ): boolean {
        // If we haven't created a program yet or have changed automatic type directives, then it is not up-to-date
        if (!program || hasChangedAutomaticTypeDirectiveNames?.()) return false;

        // If root file names don't match
        if (!arrayIsEqualTo(program.getRootFileNames(), rootFileNames)) return false;

        let seenResolvedRefs: ResolvedProjectReference[] | undefined;

        // If project references don't match
        if (!arrayIsEqualTo(program.getProjectReferences(), projectReferences, projectReferenceUptoDate)) return false;

        // If any file is not up-to-date, then the whole program is not up-to-date
        if (program.getSourceFiles().some(sourceFileNotUptoDate)) return false;

        // If any of the missing file paths are now created
        if (program.getMissingFilePaths().some(fileExists)) return false;

        const currentOptions = program.getCompilerOptions();
        // If the compilation settings do no match, then the program is not up-to-date
        if (!compareDataObjects(currentOptions, newOptions)) return false;

        // If everything matches but the text of config file is changed,
        // error locations can change for program options, so update the program
        if (currentOptions.configFile && newOptions.configFile) return currentOptions.configFile.text === newOptions.configFile.text;

        return true;

        function sourceFileNotUptoDate(sourceFile: SourceFile) {
            return !sourceFileVersionUptoDate(sourceFile) ||
                hasInvalidatedResolution(sourceFile.path);
        }

        function sourceFileVersionUptoDate(sourceFile: SourceFile) {
            return sourceFile.version === getSourceVersion(sourceFile.resolvedPath, sourceFile.fileName);
        }

        function projectReferenceUptoDate(oldRef: ProjectReference, newRef: ProjectReference, index: number) {
            return projectReferenceIsEqualTo(oldRef, newRef) &&
                resolvedProjectReferenceUptoDate(program!.getResolvedProjectReferences()![index], oldRef);
        }

        function resolvedProjectReferenceUptoDate(oldResolvedRef: ResolvedProjectReference | undefined, oldRef: ProjectReference): boolean {
            if (oldResolvedRef) {
                    // Assume true
                if (contains(seenResolvedRefs, oldResolvedRef)) return true;

                const refPath = resolveProjectReferencePath(oldRef);
                const newParsedCommandLine = getParsedCommandLine(refPath);

                // Check if config file exists
                if (!newParsedCommandLine) return false;

                // If change in source file
                if (oldResolvedRef.commandLine.options.configFile !== newParsedCommandLine.options.configFile) return false;

                // check file names
                if (!arrayIsEqualTo(oldResolvedRef.commandLine.fileNames, newParsedCommandLine.fileNames)) return false;

                // Add to seen before checking the referenced paths of this config file
                (seenResolvedRefs || (seenResolvedRefs = [])).push(oldResolvedRef);

                // If child project references are upto date, this project reference is uptodate
                return !forEach(oldResolvedRef.references, (childResolvedRef, index) =>
                    !resolvedProjectReferenceUptoDate(childResolvedRef, oldResolvedRef.commandLine.projectReferences![index]));
            }

            // In old program, not able to resolve project reference path,
            // so if config file doesnt exist, it is uptodate.
            const refPath = resolveProjectReferencePath(oldRef);
            return !getParsedCommandLine(refPath);
        }
    }

    export function getConfigFileParsingDiagnostics(configFileParseResult: ParsedCommandLine): readonly Diagnostic[] {
        return configFileParseResult.options.configFile ?
            [...configFileParseResult.options.configFile.parseDiagnostics, ...configFileParseResult.errors] :
            configFileParseResult.errors;
    }

    /**
     * A function for determining if a given file is esm or cjs format, assuming modern node module resolution rules, as configured by the
     * `options` parameter.
     *
     * @param fileName The normalized absolute path to check the format of (it need not exist on disk)
     * @param [packageJsonInfoCache] A cache for package file lookups - it's best to have a cache when this function is called often
     * @param host The ModuleResolutionHost which can perform the filesystem lookups for package json data
     * @param options The compiler options to perform the analysis under - relevant options are `moduleResolution` and `traceResolution`
     * @returns `undefined` if the path has no relevant implied format, `ModuleKind.ESNext` for esm format, and `ModuleKind.CommonJS` for cjs format
     */
    export function getImpliedNodeFormatForFile(fileName: Path, packageJsonInfoCache: PackageJsonInfoCache | undefined, host: ModuleResolutionHost, options: CompilerOptions): ModuleKind.ESNext | ModuleKind.CommonJS | undefined {
        switch (getEmitModuleResolutionKind(options)) {
            case ModuleResolutionKind.Node12:
            case ModuleResolutionKind.NodeNext:
                return fileExtensionIsOneOf(fileName, [Extension.Dmts, Extension.Mts, Extension.Mjs]) ? ModuleKind.ESNext :
                    fileExtensionIsOneOf(fileName, [Extension.Dcts, Extension.Cts, Extension.Cjs]) ? ModuleKind.CommonJS :
                    fileExtensionIsOneOf(fileName, [Extension.Dts, Extension.Ts, Extension.Tsx, Extension.Js, Extension.Jsx]) ? lookupFromPackageJson() :
                    undefined; // other extensions, like `json` or `tsbuildinfo`, are set as `undefined` here but they should never be fed through the transformer pipeline
            default:
                return undefined;
        }
        function lookupFromPackageJson(): ModuleKind.ESNext | ModuleKind.CommonJS {
            const scope = getPackageScopeForPath(fileName, packageJsonInfoCache, host, options);
            return scope?.packageJsonContent.type === "module" ? ModuleKind.ESNext : ModuleKind.CommonJS;

        }
    }

    /**
     * Determine if source file needs to be re-created even if its text hasn't changed
     */
    function shouldProgramCreateNewSourceFiles(program: Program | undefined, newOptions: CompilerOptions): boolean {
        if (!program) return false;
        // If any compiler options change, we can't reuse old source file even if version match
        // The change in options like these could result in change in syntax tree or `sourceFile.bindDiagnostics`.
        return optionsHaveChanges(program.getCompilerOptions(), newOptions, sourceFileAffectingCompilerOptions);
    }

    function createCreateProgramOptions(rootNames: readonly string[], options: CompilerOptions, host?: CompilerHost, oldProgram?: Program, configFileParsingDiagnostics?: readonly Diagnostic[]): CreateProgramOptions {
        return {
            rootNames,
            options,
            host,
            oldProgram,
            configFileParsingDiagnostics
        };
    }

    /**
     * Create a new 'Program' instance. A Program is an immutable collection of 'SourceFile's and a 'CompilerOptions'
     * that represent a compilation unit.
     *
     * Creating a program proceeds from a set of root files, expanding the set of inputs by following imports and
     * triple-slash-reference-path directives transitively. '@types' and triple-slash-reference-types are also pulled in.
     *
     * @param createProgramOptions - The options for creating a program.
     * @returns A 'Program' object.
     */
    export function createProgram(createProgramOptions: CreateProgramOptions): Program;
    /**
     * Create a new 'Program' instance. A Program is an immutable collection of 'SourceFile's and a 'CompilerOptions'
     * that represent a compilation unit.
     *
     * Creating a program proceeds from a set of root files, expanding the set of inputs by following imports and
     * triple-slash-reference-path directives transitively. '@types' and triple-slash-reference-types are also pulled in.
     *
     * @param rootNames - A set of root files.
     * @param options - The compiler options which should be used.
     * @param host - The host interacts with the underlying file system.
     * @param oldProgram - Reuses an old program structure.
     * @param configFileParsingDiagnostics - error during config file parsing
     * @returns A 'Program' object.
     */
    export function createProgram(rootNames: readonly string[], options: CompilerOptions, host?: CompilerHost, oldProgram?: Program, configFileParsingDiagnostics?: readonly Diagnostic[]): Program;
    export function createProgram(rootNamesOrOptions: readonly string[] | CreateProgramOptions, _options?: CompilerOptions, _host?: CompilerHost, _oldProgram?: Program, _configFileParsingDiagnostics?: readonly Diagnostic[]): Program {
        const createProgramOptions = isArray(rootNamesOrOptions) ? createCreateProgramOptions(rootNamesOrOptions, _options!, _host, _oldProgram, _configFileParsingDiagnostics) : rootNamesOrOptions; // TODO: GH#18217
        const { rootNames, options, configFileParsingDiagnostics, projectReferences } = createProgramOptions;
        let { oldProgram } = createProgramOptions;

        let processingDefaultLibFiles: SourceFile[] | undefined;
        let processingOtherFiles: SourceFile[] | undefined;
        let files: SourceFile[];
        let symlinks: SymlinkCache | undefined;
        let commonSourceDirectory: string;
        let diagnosticsProducingTypeChecker: TypeChecker;
        let noDiagnosticsTypeChecker: TypeChecker;
        let classifiableNames: Set<__String>;
        const ambientModuleNameToUnmodifiedFileName = new Map<string, string>();
        let fileReasons = createMultiMap<Path, FileIncludeReason>();
        const cachedBindAndCheckDiagnosticsForFile: DiagnosticCache<Diagnostic> = {};
        const cachedDeclarationDiagnosticsForFile: DiagnosticCache<DiagnosticWithLocation> = {};

        let resolvedTypeReferenceDirectives = new Map<string, ResolvedTypeReferenceDirective | undefined>();
        let fileProcessingDiagnostics: FilePreprocessingDiagnostics[] | undefined;

        // The below settings are to track if a .js file should be add to the program if loaded via searching under node_modules.
        // This works as imported modules are discovered recursively in a depth first manner, specifically:
        // - For each root file, findSourceFile is called.
        // - This calls processImportedModules for each module imported in the source file.
        // - This calls resolveModuleNames, and then calls findSourceFile for each resolved module.
        // As all these operations happen - and are nested - within the createProgram call, they close over the below variables.
        // The current resolution depth is tracked by incrementing/decrementing as the depth first search progresses.
        const maxNodeModuleJsDepth = typeof options.maxNodeModuleJsDepth === "number" ? options.maxNodeModuleJsDepth : 0;
        let currentNodeModulesDepth = 0;

        // If a module has some of its imports skipped due to being at the depth limit under node_modules, then track
        // this, as it may be imported at a shallower depth later, and then it will need its skipped imports processed.
        const modulesWithElidedImports = new Map<string, boolean>();

        // Track source files that are source files found by searching under node_modules, as these shouldn't be compiled.
        const sourceFilesFoundSearchingNodeModules = new Map<string, boolean>();

        tracing?.push(tracing.Phase.Program, "createProgram", { configFilePath: options.configFilePath, rootDir: options.rootDir }, /*separateBeginAndEnd*/ true);
        performance.mark("beforeProgram");

        const host = createProgramOptions.host || createCompilerHost(options);
        const configParsingHost = parseConfigHostFromCompilerHostLike(host);

        let skipDefaultLib = options.noLib;
        const getDefaultLibraryFileName = memoize(() => host.getDefaultLibFileName(options));
        const defaultLibraryPath = host.getDefaultLibLocation ? host.getDefaultLibLocation() : getDirectoryPath(getDefaultLibraryFileName());
        const programDiagnostics = createDiagnosticCollection();
        const currentDirectory = host.getCurrentDirectory();
        const supportedExtensions = getSupportedExtensions(options);
        const supportedExtensionsWithJsonIfResolveJsonModule = getSupportedExtensionsWithJsonIfResolveJsonModule(options, supportedExtensions);

        // Map storing if there is emit blocking diagnostics for given input
        const hasEmitBlockingDiagnostics = new Map<string, boolean>();
        let _compilerOptionsObjectLiteralSyntax: ObjectLiteralExpression | false | undefined;

        let moduleResolutionCache: ModuleResolutionCache | undefined;
        let typeReferenceDirectiveResolutionCache: TypeReferenceDirectiveResolutionCache | undefined;
        let actualResolveModuleNamesWorker: (moduleNames: string[], containingFile: SourceFile, containingFileName: string, reusedNames?: string[], redirectedReference?: ResolvedProjectReference) => ResolvedModuleFull[];
        const hasInvalidatedResolution = host.hasInvalidatedResolution || returnFalse;
        if (host.resolveModuleNames) {
            actualResolveModuleNamesWorker = (moduleNames, containingFile, containingFileName, reusedNames, redirectedReference) => host.resolveModuleNames!(Debug.checkEachDefined(moduleNames), containingFileName, reusedNames, redirectedReference, options, containingFile).map(resolved => {
                // An older host may have omitted extension, in which case we should infer it from the file extension of resolvedFileName.
                if (!resolved || (resolved as ResolvedModuleFull).extension !== undefined) {
                    return resolved as ResolvedModuleFull;
                }
                const withExtension = clone(resolved) as ResolvedModuleFull;
                withExtension.extension = extensionFromPath(resolved.resolvedFileName);
                return withExtension;
            });
            moduleResolutionCache = host.getModuleResolutionCache?.();
        }
        else {
            moduleResolutionCache = createModuleResolutionCache(currentDirectory, getCanonicalFileName, options);
            const loader = (moduleName: string, resolverMode: ModuleKind.CommonJS | ModuleKind.ESNext | undefined, containingFileName: string, redirectedReference: ResolvedProjectReference | undefined) => resolveModuleName(moduleName, containingFileName, options, host, moduleResolutionCache, redirectedReference, resolverMode).resolvedModule!; // TODO: GH#18217
            actualResolveModuleNamesWorker = (moduleNames, containingFile, containingFileName, _reusedNames, redirectedReference) => loadWithModeAwareCache<ResolvedModuleFull>(Debug.checkEachDefined(moduleNames), containingFile, containingFileName, redirectedReference, loader);
        }

        let actualResolveTypeReferenceDirectiveNamesWorker: (typeDirectiveNames: string[], containingFile: string, redirectedReference?: ResolvedProjectReference) => (ResolvedTypeReferenceDirective | undefined)[];
        if (host.resolveTypeReferenceDirectives) {
            actualResolveTypeReferenceDirectiveNamesWorker = (typeDirectiveNames, containingFile, redirectedReference) => host.resolveTypeReferenceDirectives!(Debug.checkEachDefined(typeDirectiveNames), containingFile, redirectedReference, options);
        }
        else {
            typeReferenceDirectiveResolutionCache = createTypeReferenceDirectiveResolutionCache(currentDirectory, getCanonicalFileName, /*options*/ undefined, moduleResolutionCache?.getPackageJsonInfoCache());
            const loader = (typesRef: string, containingFile: string, redirectedReference: ResolvedProjectReference | undefined) => resolveTypeReferenceDirective(
                typesRef,
                containingFile,
                options,
                host,
                redirectedReference,
                typeReferenceDirectiveResolutionCache,
            ).resolvedTypeReferenceDirective!; // TODO: GH#18217
            actualResolveTypeReferenceDirectiveNamesWorker = (typeReferenceDirectiveNames, containingFile, redirectedReference) => loadWithLocalCache<ResolvedTypeReferenceDirective>(Debug.checkEachDefined(typeReferenceDirectiveNames), containingFile, redirectedReference, loader);
        }

        // Map from a stringified PackageId to the source file with that id.
        // Only one source file may have a given packageId. Others become redirects (see createRedirectSourceFile).
        // `packageIdToSourceFile` is only used while building the program, while `sourceFileToPackageName` and `isSourceFileTargetOfRedirect` are kept around.
        const packageIdToSourceFile = new Map<string, SourceFile>();
        // Maps from a SourceFile's `.path` to the name of the package it was imported with.
        let sourceFileToPackageName = new Map<Path, string>();
        // Key is a file name. Value is the (non-empty, or undefined) list of files that redirect to it.
        let redirectTargetsMap = createMultiMap<Path, string>();
        let usesUriStyleNodeCoreModules = false;

        /**
         * map with
         * - SourceFile if present
         * - false if sourceFile missing for source of project reference redirect
         * - undefined otherwise
         */
        const filesByName = new Map<string, SourceFile | false | undefined>();
        let missingFilePaths: readonly Path[] | undefined;
        // stores 'filename -> file association' ignoring case
        // used to track cases when two file names differ only in casing
        const filesByNameIgnoreCase = host.useCaseSensitiveFileNames() ? new Map<string, SourceFile>() : undefined;

        // A parallel array to projectReferences storing the results of reading in the referenced tsconfig files
        let resolvedProjectReferences: readonly (ResolvedProjectReference | undefined)[] | undefined;
        let projectReferenceRedirects: ESMap<Path, ResolvedProjectReference | false> | undefined;
        let mapFromFileToProjectReferenceRedirects: ESMap<Path, Path> | undefined;
        let mapFromToProjectReferenceRedirectSource: ESMap<Path, SourceOfProjectReferenceRedirect> | undefined;

        const useSourceOfProjectReferenceRedirect = !!host.useSourceOfProjectReferenceRedirect?.() &&
            !options.disableSourceOfProjectReferenceRedirect;
        const { onProgramCreateComplete, fileExists, directoryExists } = updateHostForUseSourceOfProjectReferenceRedirect({
            compilerHost: host,
            getSymlinkCache,
            useSourceOfProjectReferenceRedirect,
            toPath,
            getResolvedProjectReferences,
            getSourceOfProjectReferenceRedirect,
            forEachResolvedProjectReference
        });