[incremental] remove unwanted `DepTrackingMap` methods

[nikomatsakis]

In the current model, it is common to start an incremental task T and have it read some nodes (R) and then write some values (W). This creates a dependency between R and W as shown:

R -> T -> W

But we are planning to migrate to a more "on-demand" model. In that case, the idea is that you don't "start tasks" that have side-effects, rather you "demand things you want". So the right way would be to "demand" W, which then (if not already computed) executes a task (via the ty::queries machinery). This task adopts the dep node W and reads whatever data it needs (the task starts with no context). This results then in a graph like this:

R -> W

In order to transition to this new beautiful vision, I've been searching for the right things to refactor. I think the right plan is to try and remove uses of the following DepTrackingMap methods (except for those that are within the ty::queries machinery itself):

• insert()
• entry()
• push()

In my incr-comp-memoize branch, I've got a commit that renames those methods to __insert__() etc so as to easily identify all the places that they are called. I've gone through them and identified how I think each should be transitioned to a query, which is described below.

Once this is done, the next logical step is to move on to the other methods of DepTrackingMap, since eventually I would like the existence of those maps to be completely encapsulated behind queries.

• custom coerce unsized kind. This is being computed at the same time that coherence checks CoerceUnsized impls for errors. To handle this, I made a coerce_unsized_info task that can be executed on any CoerceUnsized impl (and indeed must be executed on all of them). coherence invokes this task, but so does anything later that just wants to extract the kind. on-demand-ify custom_coerce_unsized_kind and inherent-impls #40683

• associated items. This one is fairly easy. Right now, when we compute AssociatedItem(X), where X is some associated item, we do so by reading the impl/trait that contains X, and not X itself (this is important to avoid undue contamination; won't be needed under red-green system). Since we're reading the impl/trait, we currently wind up generating all the associated items in that impl/trait at the same time. We can just refactor this to extract the one we are interested in. It does mean "O(N^2)" work in some sense, but the N here is really quite small (i.e., for each item in an impl, we'll scan the list of items in the impl, so N is the average number of items in an impl or trait). On-demandify associated item retrieval #40668

• adt def. I'm not 100% sure what's going on here; we publish the adt-def for an item X, sometimes, with two def-ids (one for the constructor as well). Hopefully, we can fix this by either not doing that, or by having a request for the constructor just get redirected to the item that it is a constructor of. Remove unused adt-def insertion by constructor DefIndex #40696

• monomorphic const eval. I don't have a plan here yet, have to dig a bit more deeply.

• inherent impls on-demand-ify custom_coerce_unsized_kind and inherent-impls #40683 and...

• ...variances. These two are a bit complex. They both fit the pattern where you kind of want to scrape a whole bunch of stuff to compute the final result. The naive dependencies here mean that if you're not careful you have each item (e.g. Variance(X) for all X) depending on the entire crate. This will be ok in the red-green system, since if they haven't actually changed we'll limit the damage, but in the current system it's a pain. To side-step this, I think we should adopt the following pattern:

• have a single task that computes a global map (i.e., a map from each struct to its inherent impls, and a map from each struct to its variance).

• when you request a specific item (e.g., InherentImpls(S) for some struct/enum S), we issue a query for the global map, but we use a dep_graph.with_ignore() to hide this dependency. This will avoid creating an edge from * -> InherentImpls(X), but we have to make sure to insert the correct (more minimal) edges. How we do this depends on the case, but it basically is us inserting the right edge from "first principles" (this goes against our overall design, which aims to observe what the compiler does rather than dictate, but we'll refactor it eventually in the red-green system).

In the case of inherent impls, if InherentImpls(S) maps to a vector of impl def-ids V, we will create an edge Hir(v) -> InherentImpls(S) for each def-id v in V.

In the case of variances, the code already has some treatment where it figures out what are a minimal set of dependencies (documented in the variance README). We'll have to reproduce that. I have some other thoughts but no time to write them down just now; this is one of the more complicated cases, anyhow.

[nikomatsakis]

@cramertj and I will probably be tackling this.

cc @michaelwoerister, @eddyb

[eddyb]

monomorphic const eval. I don't have a plan here yet, have to dig a bit more deeply.

My plan was to eventually add Substs to it and just make it the "const evaluation cache", but dealing with errors is a bit tricky, because there is one kind of error ("still too polymorphic") that shouldn't be an user-facing error, only delay evaluation further. Relatedly, Substs is not enough, I need something like ParameterEnvironment that works (efficiently) as part of the key.

That said, just the monomorphic bit can be made on-demand today, quite easily.

[michaelwoerister]

When #42192 lands, this task will be done.

[nikomatsakis]

That landed, closing.