Extract queries for the trait system operations that are performed in trans

[nikomatsakis]

Currently, there are a number of trait system operations that are used by the code in trans. Currently, they are invoked directly, and behind the scenes they use a DepTrackingMap to memoize across multiple calls. It would be better for incremental if they were converted into named queries. Effectively the goal is to remove the trans_trait_caches field of the tcx. For these particular operations, since they do not work on types that include inference variables, this should be fairly straight-forward:

• trans_fulfill_obligation, defined here, which immediately invokes the memoize function here.
• The associated type normalization that is cached here could also be invoking a (newly defined) query.

The idea would to take the following steps:

• Define a query for trans_fulfill_obligation.
  • Reference material on how to define a query can be found here.
  • Reference material on how the Rust compiler represents types and what the Ty<'tcx> type is.
  • In this case, you will need to add an appropriate line to the list of queries, and then you will need to convert the existing fn trans_fulfill_obligation from a method (as it is currently defined) into a free-standing function that serves as a provider. You can just remove the call to memoize, which would no longer be needed.
  • The trait system already defines a number of queries; those providers are linked here, so you could pick one of those to use as a rough model for what bits go where (e.g., the specialization_graph_of query).
• With respect to the normalization that is taking place here, I think a wee bit of refactoring is in order before we introduce the query. The actual setup here is a bit confused and probably could use even more refactoring, but for the purposes of this issue, we can do something fairly tailored.
  • Step 1: Rename the method normalize_associated_type() to normalize_associated_type_in(). This method is defined here. It only has a handful of callers (as you can see with a quick rg \.normalize_associated_type\().
    • This is a generic function that will normalize associated types in all kinds of things.
  • Step 2: Define a query normalize_ty(Ty<'tcx>) -> Ty<'tcx> that simply invokes normalize_associated_types_in. This is basically that function in query form, but specialized to inputs of type Ty<'tcx>.
  • Step 3. Replace these lines that invoke memoize()) with code that just invokes the query self.tcx.normalize_ty(ty).

For bonus points, we might consider converting the following functions into queries. It seems like they could benefit from caching:

• traits::get_vtable_methods (definition)
  • would have to be converted to return a vector
• traits::normalize_and_test_predicates
• trans_normalize
• trans_apply_param_substs

It's unclear though if this is a good idea. I'd keep those for a later PR so we can do some experiments with performance and memory use.

[wesleywiser]

I'd like to take a shot at this if that's ok.

[nikomatsakis]

cc @michaelwoerister

[nikomatsakis]

@wesleywiser definitely! Feel free to reach out on gitter if you have any questions along the way. You can also leave comments here, but I have a hard time keeping up with GH notifications, so that can sometimes lead to a long lag in getting a reply. =)

[nikomatsakis]

Oh one other thing. There is no reason to do this all at once. In particular, it would be fine to open a PR that just tackles trans_fulfill_obligation, and then tackle the second one later.

[wesleywiser]

Thanks! I'll definitely work on trans_fulfill_obligation first.

[wesleywiser]

I'm working on the first part of creating a query for trans_fulfill_obligation. I've added a query which returns a Vtable because that's what trans_fulfill_obligation returns but now I'm getting this error:

error[E0277]: the trait bound traits::Vtable<'_, ()>: rustc_data_structures::stable_hasher::HashStable<ich::hcx::StableHashingContext<'_>> is not satisfied

(Full error here)
I understand that this means that Vtable doesn't implement HashStable and I'll need to implement that. I just wanted to check in and make sure that's the right approach. Is there some other value I should be returning instead of Vtable that's stable hash friendly?

[michaelwoerister]

Copying from gitter to make sure you see it:

You're on the right path. Returning a Vtable is the right way to go and implementing HashStable is also the correct thing to do.
The implementation will probably end up looking something like https://github.com/rust-lang/rust/blob/master/src/librustc/ich/impls_ty.rs#L206

[Maaarcocr]

I would like to work on turning normalize_associated_type() to a query!

[theotherjimmy]

I'm working on traits::get_vtable_methods

[theotherjimmy]

Oh, I #45137 does the traits::get_vtable_methods => VtableMethods query conversion.

[BurntPizza]

I've query-ifed normalize_and_test_predicates, which you can see here: https://github.com/BurntPizza/rust/tree/query-snatp
I'm not noticing any timing difference on some quick by-hand benchmarks, but I'm not looking at memory usage. or anything incremental. Should I make a PR?
Also, @nikomatsakis , I want to thank you for such clear and actionable instructions. I've had "contribute to rustc" on the "I'd like to do that" list for a while, but this got me over the edge.

[michaelwoerister]

Should I make a PR?

Sure, go ahead! Thanks, @BurntPizza!

[nikomatsakis]

I feel like this "got done" enough to close this general issue.