downsweep: make control flow simpler and cache correct

downsweep: make control flow simpler and cache correct

This refactor extracts the control flow of downsweep into a single
function `dfsBuild`, which takes care of iteratively expanding and
traversing all nodes of the in-construction module graph necessary to
build a full `ModuleGraph`.

There are three levels of caching going on, all of which are necessary
to make sure we don't do repeated work (specifically: NEVER summarise
the same module twice).

1. `dfsBuild` accumulates the final module graph and never revisits the
   same node of the module graph. Cache is keyed by the final
   `ModuleGraph`s `NodeKey`s.

2. For Module A in home-unit u1, each import in the list of imports
   needs to be *found* (call to `findImportedModuleWithIsBoot`): at this
   point, we only have the `ModuleName` of the import, not the `Module`.
   This *finding* is somewhat expensive, so we cache it as well
   (`ImportsCache`). The cache key is the home-unit to which the module
   belongs~[1], the import package qualifier, and the ModuleName.

   [1] Different home-units will have different package flags, which means
   potentially different `Module` resolution for the same `ModuleName`.

3. The most expensive operation we want to avoid is summarising a
   `Module` into a `ModSummary`, which notably involves parsing the
   module header from scratch.
   The third cache, in essence, maps a `Module` to its `ModSummary`
   (named `ModSummaryCache`). This cache upholds the invariant: we NEVER
   summarise the same module twice. In practice, the cache key is the
   Module's UnitId and the Source path; the reason is we need to
   distinguish between `.hs` and `.hs-boot` files, as their summaries
   will differ.

   Note that (2) can't guarantee this alone: Two ModuleName imports in
   separate units can (and likely do) map to the same `Module`.

Note that the previous implementation failed to achieve the
no-duplicate-work summarisation invariant, and we ended up doing a
quadratic amount of processing in scenarios like test
`MultiComponentModules100`.

See also Note [Downsweep Control Flow and Caching]

Fixes #27461

Fixes #27461 (closed)

Merge request reports

Loading