When reporting the declarations that lead to a cycle, we end up printing an
extra "through reference here" on the function declaration:
class C2: C1, P {
| |- note: through reference here
| `- note: through reference here
15 | // expected-note@-1 2{{through reference here}}
16 | override func run(a: A) {}
| | | `- note: while resolving type 'A'
| | `- note: through reference here
| |- error: circular reference
| |- note: through reference here
| `- note: through reference here
Although I don't plan to bring over new assertions wholesale
into the current qualification branch, it's entirely possible
that various minor changes in main will use the new assertions;
having this basic support in the release branch will simplify that.
(This is why I'm adding the includes as a separate pass from
rewriting the individual assertions)
Macros introduced a significant wrinkle into Swift's name lookup mechanism.
Specifically, when resolving names (and, really, anything else) within the
arguments to a macro expansion, name lookup must not try to expand any
macros, because doing so trivially creates a cyclic dependency amongst the
macro expansions that will be detected by the request-evaluator.
Our lookup requests don't always have enough information to answer the
question "is this part of an argument to a macro?", so we do a much simpler,
more efficient, and not-entirely-sound hack based on the request-evaluator.
Specifically, if we are in the process of resolving a macro (which is
determined by checking for the presence of a `ResolveMacroRequest` in the
request-evaluator stack), then we adjust the options used for the name
lookup request we are forming to exclude macro expansions. The evaluation
of that request will then avoid expanding any macros, and not produce any
results that involve entries in already-expanded macros. By adjusting the
request itself, we still distinguish between requests that can and cannot
look into macro expansions, so it doesn't break caching for those immediate
requests.
Over time, we should seek to replace this heuristic with a location-based
check, where we use ASTScope to determine whether we are inside a macro
argument. This existing check might still be useful because it's going to
be faster than a location-based query, but the location-based query can be
fully correct.
This addresses a class of cyclic dependencies that we've been seeing
with macros, and aligns the lookup behavior for module-level lookups
with that specified in the macros proposals. It is not fully complete
because lookup until nominal types does not yet support excluding
results from macro expansions.
This becomes tricky with the new per-request cache representation.
We can add it back later if we need it, but I feel like this code
path isn't particularly useful right now anyway.
Other than simplifying some code, the big improvement here is
that we 'freeze' the reference dependencies for a request down
to a simple vector. We only use a DenseSet to store dependencies
of active requests.
-enable-experimental-private-intransitive-dependencies -> -enable-direct-intramodule-dependencies
-disable-experimental-private-intransitive-dependencies -> -disable-direct-intramodule-dependencies
While we're here, rename DependencyCollector::Mode's constants and clean
up the documentation.
In order for private dependencies to be completely correct, it must perform the name lookup unioning step when a cached request is replayed - not just when lookups are first performed. In order to reduce the overhead of this union operation, it is not necessary to walk the entire active request stack, just walk to the nearest cached request in the stack and union into that. When it is popped, its replay step will itself union into the next cached request.
To see why, consider a request graph:
A* -> B -> C*
|
-> D*
where A, C, and D are cached.
If a caller were to force C and D, then force A independenty, today we would *only* replay the names looked up by C and D the first time A was evaluated. That is, subsequent evaluations of A do not replay the correct set of names. If we were to perform the union step during replay as well, requests that force A would also see C and D’s lookups.
Without this, callers that force requests like the DeclChecker have to be wary of the way they force the interface type request so other files see the right name sets.
rdar://64008262
Split off the notion of "recording" dependencies from the notion of
"collecting" dependencies. This corrects an oversight in the previous
design where dependency replay and recording were actually not "free" in
WMO where we actually never track dependencies. This architecture also
lays the groundwork for the removal of the referenced name trackers.
The algorithm builds upon the infrastructure for dependency sources and
sinks laid down during the cut over to request-based dependency tracking
in #30723.
The idea of the naive algorithm is this:
For a chain of requests A -> B* -> C -> D* -> ... -> L where L is a lookup
request and all starred requests are cached, once L writes into the
dependency collector, the active stack is walked and at each cache-point
the results of dependency collection are associated with the request
itself (in this example, B* and D* have all the names L found associated
with them). Subsequent evaluations of these cached requests (B* and D*
et al) will then *replay* the previous lookup results from L into the
active referenced name tracker. One complication is, suppose the
evaluation of a cached request involves multiple downstream name
lookups. More concretely, suppose we have the following request trace:
A* -> B -> L
|
-> C -> L
|
-> D -> L
|
-> ...
Then A* must see the union of the results of each L. If this reminds
anyone of a union-find, that is no accident! A persistent union-find
a la Conchon and Filliatre is probably in order to help bring down peak
heap usage...
Finish off private intransitive dependencies with an implementation of
dependency replay.
For the sake of illustration, imagine a chain of requests
A -> B -> C -> ...
Supposing each request is never cached, then every invocation of the
compiler with the same inputs will always kick off the exact same set of
requests. For the purposes of dependency tracking, that also means every
single lookup request will run without issue, and all dependencies will
be accurately reported. But we live in a world with cached requests.
Suppose request B* is cached. The first time we encounter that request,
its evaluation order looks identical:
A -> B* -> C -> ...
If we are in a mode that compiles single primaries, this is not
a problem because every request graph will look like this.
But if we are in a mode where we are compiling multiple primaries, then
subsequent request graphs will *actually* hit the cache and never
execute request C or any of its dependent computations!
A -> B*
Supposing C was a lookup request, that means the name(s) looked up
downstream of B* will *never* be recorded in the referenced name tracker
which can lead to miscompilation. Note that this is not a problem
inherent to the design of the request evaluator - caches in the compiler
have *always* hidden dependent lookups. In fact, the request evaluator
provides us our first opportunity to resolve this correctness bug!
Add a mode bit to the dependency collector that respects the frontend flag in the previous commit.
Notably, we now write over the dependency files at the end of the compiler pipeline when this flag is on so that dependency from SILGen and IRGen are properly written to disk.
Define a new type DependencyCollector that abstracts over the
incremental dependency gathering logic. This will insulate the
request-based name tracking code from future work on private,
intransitive dependencies.
This wrapper is used to type erase a reference to
a request on the stack, and can be converted into
an AnyRequest when persistent storage is required.
Switch the evaluator over to using ActiveRequest
for its stack of active requests, meaning it now
only needs to heap allocate requests when they
enter the cache, or if it's building the (disabled
by default) dependency graph.
To help make the current GraphViz output of the dependency graph more
legible, introduce "fake" nodes for the source buffers we encounter,
and draw edges from those nodes to any requests associated with those
source buffers that have no other edges leading to them. This is a
temporary visualization hack, to be replaced by proper "top-level"
requests for things like type-checking an entire source file.
Use the "nearest source location" information on a request to map it
to a particular source buffer, then use that information in the
GraphViz dependency graphs so we can see cross-file dependencies more
clearly.
The bundling of the form of a request (e.g., the storage that makes up a request)
with the function that evaluates the request value requires us to perform
ad hoc indirection to address the AST —> Sema layering violation. For
example, ClassDecl::getSuperclass() calls through the LazyResolver (when
available) to form the appropriate request. This means that we cannot
use the the request-evaluator’s cache when LazyResolver is null, forcing
all cached state into the AST.
Provide the evaluator with a zone-based registration system, where each
request “zone” (e.g., the type checker’s requests) registers
callbacks to evaluate each kind of request within that zone. The
evaluator indirects through this table of function pointers, allowing
the request classes themselves to be available at a lower level (AST)
than the functions that perform the computation when the value isn’t
in the cache (e.g., Sema).
We are not taking advantage of the indirection yet; that’ll come in a
follow-up commit.
When dumping dependencies, clean up the output in two ways:
* Elide redundant but (non-cyclic) references to the same dependency.
* When dumping a cycle, highlight the path to the cycle so it stands out.
As a debugging aid, introduce a new frontend flag `-debug-cycles` that
will emit a debug dump whenever the request-evaluator encounters a cyclic
dependency, while otherwise allowing compilation to continue.
The type checker has *lots* cycles, and producing diagnostics for them
at this point in the development of the request-evaluator is not
productive because it breaks currently-working code. Disable cycle
diagnostics for now when using the request-evaluator in the type
checker. We'll enable it later as things improve, or as a separate
logging mode in the interim.
