This PR introduces a completely redesigned auto-import collection infrastructure. As we ported Strada's auto-import code to Corsa, two things became clear:

1. The cache infrastructure would need to be redesigned to work with the snapshot-based LSP.
2. We were leaving significant parallelization opportunities on the table.

We wanted to address these issues before (or while) adding package.json-based dependency discovery, the main feature missing from the initial port of Strada's auto-imports code.

While the data collection backend has been completely redesigned, the fix generation code is mostly unchanged, although the files have been moved frominternal/ls intointernal/ls/autoimport.

I’m closing existing all bugs/crashes filed against this repo’s auto-imports implementation with this PR. Please comment if you have a bug that still repros the exact same way after this PR.

• ClosesRethink AutoImportProvider automatic limits TypeScript#60704
• ClosesHow to trace/debug auto import suggestions? TypeScript#62829
• ClosesCrash for value usage of type-only import #2301
• Closespanic handling request textDocument/completion (autoimports) #1677
• ClosesLSP doesn't offer auto-importing packages #2189
• ClosesPanic handling request completionItem/resolve Some exportInfo should match the specified exportMapKey #2143

Strada's collection and cache infrastructure

The earliest version of auto-imports in TypeScript had no caching or separate collection phase. During every global completions request, we used the type checker to gather every export from every source file in the program. This was actually fairly fast, in part because we deferred computing the actual import module specifier until a completion item was highlighted. Eventually, we wanted to address two common complaints: (1) users wanted to see the import module specifier for every item in the completion list without having to highlight it first, and (2) we would often suggest imports from transitive dependencies, bloating the list with entries that should really never be imported. Computing module specifiers for every item in the list slowed things down enough that we implemented a caching layer to compensate. Since the cache included module specifiers and filtering based on what dependencies were accessible to the file requesting completions, much of the cache was specific to the requesting file, and needed to be rebuilt whenever the user started editing a different file.

Later, we added a very commonly requested feature: auto-imports from package.json dependencies. Since the data source for auto-imports was source files already in the program, a common complaint was that immediately afternpm installing a dependency, auto-imports from that package wouldn't show up. Users would have to manually write an import from the new package once, then auto-imports would start appearing, even in other files. To address this without completely overhauling all the existing infrastructure, which was designed to use a type checker to extract exports from source files in a program, we added a separate program and type checker “in the background” (scare quotes because we couldn’t actually do anything in a separate process; we just added it onto project loading) containing entrypoints from package.json dependencies that were absent from the main program. Then, the language service could basically just run its existing auto-import collection code twice: once for the main program, and once for the package.json dependencies program. Since this had the potential to add significant amounts of work both to project loading and completions requests, we added a conservative bail-out if more than ten entrypoints were going to be loaded into the background program. This bail-out strategy was a big and imprecise hammer, since those ten entrypoints could trigger an arbitrarily large or small amount of work through transitive imports that would be eventually be filtered out.

In short, auto-imports was due for a rewrite even before typescript-go.

New infrastructure

The primary innovations of the new system are:

Granular buckets

The new infrastructure stores exports in separate buckets that are independent of each other and independent of the requesting file. Theautoimport.Registry contains one bucket for each project owning the editor's open files, plus one bucket for eachnode_modules directory visible to the open files. Project buckets contain exports from the project's local, non-node_modules files. This means that when switching between open files, any buckets that are already populated can be reused. When a project updates, allnode_modules buckets are unaffected; when annpm install happens, only thenode_modules directories that were touched need to be updated.

Highly parallelized collection

Previously, collection of exports for package.json dependencies worked by creating a program containing all the entrypoints we care about, then using the type checker to extract exports from every source file in that program. The disadvantage of creating a program for this purpose is that we would resolve and parse transitive dependencies that have absolutely no impact on the exports we actually care about. In the new infrastructure, we instead create a mock program (autoimport.aliasResolver) for each dependency package, seeded with just the entrypoint files for that package. We then walk the exports of those entrypoints, and only use a checker when one of those exports is a re-export from another module. The result is that we only process exactly what we need, we limit our reliance on type checkers, and when we do need a type checker, the data backing it is much smaller, so we can create many checkers very cheaply.

Pre-computed module specifiers fornode_modules

Since the old infrastructure originally started from a program's source files, module specifier generation always went through the full process of “importing file name + destination file name => module specifier.” That process could be complicated for node_modules files, since the destination file could be the realpath of a symlinked package, or could have been a transitive import that’s not actually reachable from the importing file, or could be blocked by the package’s package.json"exports". Without knowing how that file got into the program, there were a dozen edge cases that needed to be considered to reverse engineer the correct module specifier, or even to determine whether a valid one exists at all. With the new directory-based buckets and extraction only from dependency entrypoints, we actually know the module specifier for every entrypoint as we find it, so we just store it alongside the export information.

Limitations / observable differences compared to Strada

• Since we usesourceFile.Symbol.Exports instead ofchecker.GetExportsAndPropertiesOfModule, properties ofexport = assignments are not collected. Many of these properties were filtered out in the old logic because they were highly suspicious anyway (e.g. class instance methods, properties of arrays). There is a special syntactic carve-out for JavaScriptmodule.exports = { foo, bar, ... } patterns, which are still collected. This limitation did not cause any new test failures.
• For node_modules packages, since we only initialize the type checker with entrypoints from that package, re-exports of globals declared in other packages or non-entrypoint files of that package will not resolve, and so may lack proper categorization and deduplication with other exports. (This limiation does not apply to re-exports from ambient modules declared elsewhere, which has special handling.) Exporting a global is rare; I would be surprised if this limitation were ever noticed.
• Since we only use a type checker when we encounter a re-export, some categorization features that eventually determine the icon for a completion entry may differ. In particular,export declare const foo: SomeType would appear as a function ifSomeType declared call signatures, but now appears as a variable.
• Previously, an unresolvable module augmentation would not contribute anything to auto-imports. Now, they do, even though importing them will cause an error. This seems possibly desirable, since the user may fix the underlying module resolution issue.
• For now, untyped dependency packages don't show up. Previously, we would parse JavaScript file entrypoints as a last resort. There are currently bugs in JavaScript reparsing that cause crashes, performance problems, and phantom exports when loading bundled JavaScript files, so I've disabled JS loading until those are addressed.
• Previously, completions would usually avoid offering multiple ways of importing the same symbol based on several ranking criteria, and then falling back to an arbitrary symbol-based order. The same ranking criteria is still applied, but instead of falling back to a totally arbitrary order, same-ranked entries generate multiple completion items.

Performance

It's extremely hard to compare this tomain to Strada, because each has its own limitations that results in very different behavior, not just different timing characteristics:

• Strada: volatile cache, package.json dependencies parsed on project load, more info cached on completions request
• Corsa main: no cache, no package.json dependencies, everything done during completions
• Corsa new: stable cache, package.json dependencies parsed on first edit, local module specifiers cached on completions request

That said, here are some numbers on two example projects.

Signal-Desktop

VS Code

Follow-up work

• Investigate including untyped packages after aforementioned JS reparsing bugs are fixed. Even after the fix, we may want some extra heuristics for avoiding minified or bundled files.
• There’s currently no specific integration with automatic type acquisition. I think Strada had some special logic for this that’s not ported.
• Import path string completions are not yet implemented (LSP: Path suggestion missing (import/export) #2383), and the node_modules registry buckets implemented here will be very helpful for simplifying the complex logic that exists in Strada.
• completionItem/resolve is surprisingly slow (not just for auto-imports), and may be missing info like JSDoc that was previously(?) there for auto-imports