Resolve `T::A`-style associated types based solely on type, instead of a Def

[eddyb]

Right now astconv::associated_path_def_to_ty takes a def::TyParamProvenance obtained from either def::DefTyParam or def::DefSelfTy.

This information cannot be easily extracted from the type, and #22172 doesn't change that, which means <T>::AssocTy does not work at all (pretends to be ambiguous).

We should be able to make progress after #22172 and #22512 both land, and I believe @nikomatsakis has a solution in mind for dealing with at least some cases.

After this is fixed, the finish_resolving_def_to_ty function introduced in #22172 can be split into def_to_ty and resolve_extra_associated_types and its callers would only need the latter for <T>::A::B::C, instead of providing a dummy Def to the entire thing.

[nrc]

This also addresses the annoying behaviour that inside impl T for C { ... }, Self::Foo and <Self as T>::Foo are valid (assuming T has an associated type called Foo), but <Self>::Foo is not.

[nikomatsakis]

cc me

[quantheory]

Unless someone else has a serious head start, I'm going to take a crack at this.

[eddyb]

@quantheory Not that I know of. I couldn't implement this initially because @nikomatsakis hadn't merged #22172 and #22512 at the time. You probably want to record traits in scope via resolve (like we do with method call expressions) and maybe generalize the method lookup logic. I would love to see all associated items dealt with in a common manner (even though some are types and others are values) with some special cases for method calls and their autoref/deref semantics.

[quantheory]

@eddyb That makes sense. What I've done so far is to separate out the resolution parts of rustc_typeck::check::method, particularly resolve_ufcs, most of probe, and the types that they depend on, into a new rustc_typeck::resolve module (all names subject to change, of course). Then I removed all the direct dependencies of that module on check by having FnCtxt implement a ResolveCtxt trait, in the hope that I can write a separate impl for collect to solve the problem.

I'm not entirely done with that step, though, since I still have some things in probe that are no good for the collect phase, like using the ty::lookup_* functions to get information about items that won't have been written to tcx at that point.

[eddyb]

@quantheory You might end up moving this to rustc::middle::traits so that const_eval can use it. Alternatively, const_eval could be moved to rustc_typeck, but rustc_trans calls into it - I believe that could be avoided, but it's more work.

[quantheory]

I'm still trying to figure this out, but it is a bit slow and difficult. I figured that I'd document things here in case anyone had any bright ideas. Instead of inventing a ResolveCtxt, I've extended AstConv, because the two ended up being so closely associated that the distinction didn't seem to buy much.

The main difficulties are:

1. Because probe was designed to run after collect, moving it up to collect in a naive way ends up producing a pretty ridiculous number of spurious cycles.

   The biggest problem is that it assumes that all the predicates on every trait are converted. For example, currently, trait_map contains all of the traits that contain any item that might match a given expression. probe unconditionally searches all predicates of all of these traits (and predicates on all of their associated types), for relevant information. This really needs to be toned down, but it does require a bit of surgery to try to selectively convert predicates.

   Another issue is that even if there is an inherent impl match, the various "assemble_*" methods run to search for trait impls anyway. Cycles found during such a search are (probably) irrelevant, because an inherent impl was already found.

2. Quite a bit of the collect and AstConv logic needs to be enhanced with the ability to deal with hypothetical assumptions that are useful for probing. For example, take the IntoIterator definition:

   pub trait IntoIterator {
      /// The type of the elements being iterated
      #[stable(feature = "rust1", since = "1.0.0")]
      type Item;
   
      /// A container for iterating over elements of type `Item`
      #[stable(feature = "rust1", since = "1.0.0")]
      type IntoIter: Iterator<Item=Self::Item>;
   
      /// Consumes `Self` and returns an iterator over it
      #[stable(feature = "rust1", since = "1.0.0")]
      fn into_iter(self) -> Self::IntoIter;
   }

   Converting IntoIter requires resolution of Self::Item to a particular trait. Due to the way that probe works, it ends up looking at every trait in scope that has an item named Item, including IntoIterator itself, and requests all of their predicates. As mentioned before, this is probably excessive in many cases. But in this case, it is (probably) correct to check predicates in IntoIterator itself at some point. For instance, we would probably want to produce an error if Item was given a circular default such as:

      type Item = <Self::IntoIter as Iterator>::Item;

   But if we convert all of the associated type bounds in IntoIterator, that includes the one on IntoIter, which requires resolving Self::Item again, which is a spurious cycle.

   I'm thinking that we need some way to either a) avoid converting predicates that are not relevant during probing (which I'm trying to figure out how to determine, at least heuristically), or b) have the probe be able to act as if we had already resolved Self::Item to <Self as IntoIterator>::Item, so that there are no spurious cycles (beyond what's already produced if the trait is specified).

[steveklabnik]

Triage: this ticket is deep in the weeds of compiler internals; I'm not sure if it's still relevant or not.

[eddyb]

Still is entirely relevant.

[steveklabnik]

Triage: not aware of changes, guessing like last time it's still relevant

[eddyb]

I am not sure which issue is the canonical one for T::X::Y::Z, but I found this one.

@nikomatsakis So I was thinking about the lazy normalization approach and what you'd need to encode in the typesystem. To handle everything supported today, this would work:

• self_ty: Ty (T in T::X aka <T>::X)
• assoc_name: Ident (X in T::X)
• scope: DefId (the definition with a T: Trait bound in its ParamEnv)

But to extend this to take into account traits in scope (via use imports) as well, in order to resolve types that don't resolve today, we need to be able to represent scopes inside bodies, e.g.:

fn foo() {
    {
        use std::ops::Deref;
        <&i32>::Target::default();
    }
}

While scope: HirId might work in a pinch, it's not as useful cross-crate.

However, there is something that might be even simpler to work with: an interned scope chain.

struct TraitsInScope<'tcx> {
    parent: &'tcx TraitsInScope<'tcx>,
    traits: StableVec<DefId>,
}

So then the scope could be (&'tcx TraitsInScope<'tcx>, DefId), and that should work nicely cross-crate as well.

(We have traits_in_scope today for associated fn/const resolution, but it doesn't use chaining so it has many copies of the same trait list, I wonder if a scope chain would be leaner/faster)