Remove phase separation between specialization graph construction and projection #32205

aturon · 2016-03-11T22:45:25Z

Specialization is fundamentally reentrant: to determine that one impl specializes another, we end up needing to call back into the full trait system machinery (selection, projection, normalization), which in turn depends on the result of specialization (for associated types in particular).

The initial implementation institutes a strict "phase split", where any attempt to perform a projection that would require walking the specialization graph while we are constructing the specialization graph simply ICEs the compiler. The need to walk the graph for a projection arises whenever you are trying to project an inherited associated type. That means examples like the following will ICE:

trait Assoc {
    type Output;
}

impl<T> Assoc for T {
    type Output = bool;
}

impl Assoc for u8 {} // <- inherits the non-default type from above

trait Foo {}
impl Foo for <u8 as Assoc>::Output {}  // <- this projection will fail with an ICE

To fix this problem, we will need to allow the specialization graph to be consulted while it's being constructed.

…r issue rust-lang#32205

@larsluthman

[12/12] On-demand type-checking, const-evaluation, MIR building & const-qualification. _This is the last of a series ([prev](#38813)) of patches designed to rework rustc into an out-of-order on-demand pipeline model for both better feature support (e.g. [MIR-based](https://github.com/solson/miri) early constant evaluation) and incremental execution of compiler passes (e.g. type-checking), with beneficial consequences to IDE support as well. If any motivation is unclear, please ask for additional PR description clarifications or code comments._ <hr> As this contains all of the changes that didn't fit neatly into other PRs, I'll be elaborating a bit: ### User-facing changes * when determining whether an `impl Trait` type implements an auto-trait (e.g. `Send` or `Sync`), the function the `impl Trait` came from has to be inferred and type-checking, disallowing cycles * this results from not having an obvious place to put the "deferred obligation" in on-demand atm * while we could model side-effects like that and "post-processing passes" better, it's still more limiting than being able to know the result in the original function (e.g. specialization) *and* there are serious problems around region-checking (if a `Send` impl required `'static`, it wasn't enforced) * early const-eval requires type-checking and const-qualification to be performed first, which means: * you get the intended errors before (if any) constant evaluation error that is simply fallout * associated consts should always work now, and `const fn` type parameters are properly tracked * don't get too excited, array lengths still can't depend on type parameters * #38864 works as intended now, with `Self` being allowed in `impl` bounds * #32205 is largely improved, with associated types being limited to "exact match" `impl`s (as opposed to traversing the specialization graph to resolve unspecified type parameters to their defaults in another `impl` or in the `trait`) *while* checking for overlaps building the specialization graph for that trait - once all the trait impls' have been checked for coherence (including ahead-of-time/on-demand), it's uniform * [crater report](https://gist.github.com/eddyb/bbb869072468c7e08d6d808e75938051) looks clean (aside from `clippy` which broke due to `rustc` internal changes) ### Compiler-internal changes * `ty::Generics` * no longer contains the actual type parameter defaults, instead they're associated with the type parameter's `DefId`, like associated types in a trait definition * this allows computing `ty::Generics` as a leaf (reading only its own HIR) * holds a mapping from `DefIndex` of type parameters to their indices * `ty::AdtDef` * only tracks `#[repr(simd)]` in its `ReprOptions` `repr` field * doesn't contain `enum` discriminant values, but instead each variant either refers to either an explicit value for its discriminant, or the distance from the last explicit discriminant, if any * the `.discriminants(tcx)` method produces an iterator of `ConstInt` values, looking up explicit discriminants in a separate map, if necessary * this allows computing `ty::AdtDef` as a leaf (reading only its own HIR) * Small note: the two above (`Generics`, `AdtDef`), `TraitDef` and `AssociatedItem` should probably end up as part of the HIR, eventually, as they're trivially constructed from it * `ty::FnSig` * now also holds ABI and unsafety, alongside argument types, return type and C variadicity * `&ty::BareFnTy` and `ty::ClosureTy` have been replaced with `PolyFnSig = Binder<FnSig>` * `BareFnTy` was interned and `ClosureTy` was treated as non-trivial to `Clone` because they had a `PolyFnSig` and so used to contain a `Vec<Ty>` (now `&[Ty]`) * `ty::maps` * all the `DepTrackingMap`s have been grouped in a structure available at `tcx.maps` * when creating the `tcx`, a set of `Providers` (one `fn` pointer per map) is required for the local crate, and one for all other crates (i.e. metadata loading), `librustc_driver` plugging the various crates (e.g. `librustc_metadata`, `librustc_typeck`, `librustc_mir`) into it * when a map is queried and the value is missing, the appropriate `fn` pointer from the `Providers` of that crate is called with the `TyCtxt` and the key being queried, to produce the value on-demand * `rustc_const_eval` * demands both `typeck_tables` and `mir_const_qualif` (in preparation for miri) * tracks `Substs` in `ConstVal::Function` for `const fn` calls * returns `TypeckError` if type-checking has failed (or cases that can only be reached if it had) * this error kind is never reported, resulting in less noisy/redundant diagnostics * fixes #39548 (testcase by @larsluthman, taken from #39812, which this supersedes) * on-demand has so far been hooked up to: * `rustc_metadata::cstore_impl`: `ty`, `generics`, `predicates`, `super_predicates`, `trait_def`, `adt_def`, `variances`, `associated_item_def_ids`, `associated_item`, `impl_trait_ref`, `custom_coerce_unsized_kind`, `mir`, `mir_const_qualif`, `typeck_tables`, `closure_kind`, `closure_type` * `rustc_typeck::collect`: `ty`, `generics`, `predicates`, `super_predicates`, `type_param_predicates`, `trait_def`, `adt_def`, `impl_trait_ref` * `rustc_typeck::coherence`: `coherent_trait`, `coherent_inherent_impls` * `rustc_typeck::check`: `typeck_tables`, `closure_type`, `closure_kind` * `rustc_mir::mir_map`: `mir` * `rustc_mir::transform::qualify_consts`: `mir_const_qualif`

@larsluthman

[12/12] On-demand type-checking, const-evaluation, MIR building & const-qualification. _This is the last of a series ([prev](#38813)) of patches designed to rework rustc into an out-of-order on-demand pipeline model for both better feature support (e.g. [MIR-based](https://github.com/solson/miri) early constant evaluation) and incremental execution of compiler passes (e.g. type-checking), with beneficial consequences to IDE support as well. If any motivation is unclear, please ask for additional PR description clarifications or code comments._ <hr> As this contains all of the changes that didn't fit neatly into other PRs, I'll be elaborating a bit: ### User-facing changes * when determining whether an `impl Trait` type implements an auto-trait (e.g. `Send` or `Sync`), the function the `impl Trait` came from has to be inferred and type-checking, disallowing cycles * this results from not having an obvious place to put the "deferred obligation" in on-demand atm * while we could model side-effects like that and "post-processing passes" better, it's still more limiting than being able to know the result in the original function (e.g. specialization) *and* there are serious problems around region-checking (if a `Send` impl required `'static`, it wasn't enforced) * early const-eval requires type-checking and const-qualification to be performed first, which means: * you get the intended errors before (if any) constant evaluation error that is simply fallout * associated consts should always work now, and `const fn` type parameters are properly tracked * don't get too excited, array lengths still can't depend on type parameters * #38864 works as intended now, with `Self` being allowed in `impl` bounds * #32205 is largely improved, with associated types being limited to "exact match" `impl`s (as opposed to traversing the specialization graph to resolve unspecified type parameters to their defaults in another `impl` or in the `trait`) *while* checking for overlaps building the specialization graph for that trait - once all the trait impls' have been checked for coherence (including ahead-of-time/on-demand), it's uniform * [crater report](https://gist.github.com/eddyb/bbb869072468c7e08d6d808e75938051) looks clean (aside from `clippy` which broke due to `rustc` internal changes) ### Compiler-internal changes * `ty::Generics` * no longer contains the actual type parameter defaults, instead they're associated with the type parameter's `DefId`, like associated types in a trait definition * this allows computing `ty::Generics` as a leaf (reading only its own HIR) * holds a mapping from `DefIndex` of type parameters to their indices * `ty::AdtDef` * only tracks `#[repr(simd)]` in its `ReprOptions` `repr` field * doesn't contain `enum` discriminant values, but instead each variant either refers to either an explicit value for its discriminant, or the distance from the last explicit discriminant, if any * the `.discriminants(tcx)` method produces an iterator of `ConstInt` values, looking up explicit discriminants in a separate map, if necessary * this allows computing `ty::AdtDef` as a leaf (reading only its own HIR) * Small note: the two above (`Generics`, `AdtDef`), `TraitDef` and `AssociatedItem` should probably end up as part of the HIR, eventually, as they're trivially constructed from it * `ty::FnSig` * now also holds ABI and unsafety, alongside argument types, return type and C variadicity * `&ty::BareFnTy` and `ty::ClosureTy` have been replaced with `PolyFnSig = Binder<FnSig>` * `BareFnTy` was interned and `ClosureTy` was treated as non-trivial to `Clone` because they had a `PolyFnSig` and so used to contain a `Vec<Ty>` (now `&[Ty]`) * `ty::maps` * all the `DepTrackingMap`s have been grouped in a structure available at `tcx.maps` * when creating the `tcx`, a set of `Providers` (one `fn` pointer per map) is required for the local crate, and one for all other crates (i.e. metadata loading), `librustc_driver` plugging the various crates (e.g. `librustc_metadata`, `librustc_typeck`, `librustc_mir`) into it * when a map is queried and the value is missing, the appropriate `fn` pointer from the `Providers` of that crate is called with the `TyCtxt` and the key being queried, to produce the value on-demand * `rustc_const_eval` * demands both `typeck_tables` and `mir_const_qualif` (in preparation for miri) * tracks `Substs` in `ConstVal::Function` for `const fn` calls * returns `TypeckError` if type-checking has failed (or cases that can only be reached if it had) * this error kind is never reported, resulting in less noisy/redundant diagnostics * fixes #39548 (testcase by @larsluthman, taken from #39812, which this supersedes) * on-demand has so far been hooked up to: * `rustc_metadata::cstore_impl`: `ty`, `generics`, `predicates`, `super_predicates`, `trait_def`, `adt_def`, `variances`, `associated_item_def_ids`, `associated_item`, `impl_trait_ref`, `custom_coerce_unsized_kind`, `mir`, `mir_const_qualif`, `typeck_tables`, `closure_kind`, `closure_type` * `rustc_typeck::collect`: `ty`, `generics`, `predicates`, `super_predicates`, `type_param_predicates`, `trait_def`, `adt_def`, `impl_trait_ref` * `rustc_typeck::coherence`: `coherent_trait`, `coherent_inherent_impls` * `rustc_typeck::check`: `typeck_tables`, `closure_type`, `closure_kind` * `rustc_mir::mir_map`: `mir` * `rustc_mir::transform::qualify_consts`: `mir_const_qualif`

@larsluthman

[12/12] On-demand type-checking, const-evaluation, MIR building & const-qualification. _This is the last of a series ([prev](#38813)) of patches designed to rework rustc into an out-of-order on-demand pipeline model for both better feature support (e.g. [MIR-based](https://github.com/solson/miri) early constant evaluation) and incremental execution of compiler passes (e.g. type-checking), with beneficial consequences to IDE support as well. If any motivation is unclear, please ask for additional PR description clarifications or code comments._ <hr> As this contains all of the changes that didn't fit neatly into other PRs, I'll be elaborating a bit: ### User-facing changes * when determining whether an `impl Trait` type implements an auto-trait (e.g. `Send` or `Sync`), the function the `impl Trait` came from has to be inferred and type-checking, disallowing cycles * this results from not having an obvious place to put the "deferred obligation" in on-demand atm * while we could model side-effects like that and "post-processing passes" better, it's still more limiting than being able to know the result in the original function (e.g. specialization) *and* there are serious problems around region-checking (if a `Send` impl required `'static`, it wasn't enforced) * early const-eval requires type-checking and const-qualification to be performed first, which means: * you get the intended errors before (if any) constant evaluation error that is simply fallout * associated consts should always work now, and `const fn` type parameters are properly tracked * don't get too excited, array lengths still can't depend on type parameters * #38864 works as intended now, with `Self` being allowed in `impl` bounds * #32205 is largely improved, with associated types being limited to "exact match" `impl`s (as opposed to traversing the specialization graph to resolve unspecified type parameters to their defaults in another `impl` or in the `trait`) *while* checking for overlaps building the specialization graph for that trait - once all the trait impls' have been checked for coherence (including ahead-of-time/on-demand), it's uniform * [crater report](https://gist.github.com/eddyb/bbb869072468c7e08d6d808e75938051) looks clean (aside from `clippy` which broke due to `rustc` internal changes) ### Compiler-internal changes * `ty::Generics` * no longer contains the actual type parameter defaults, instead they're associated with the type parameter's `DefId`, like associated types in a trait definition * this allows computing `ty::Generics` as a leaf (reading only its own HIR) * holds a mapping from `DefIndex` of type parameters to their indices * `ty::AdtDef` * only tracks `#[repr(simd)]` in its `ReprOptions` `repr` field * doesn't contain `enum` discriminant values, but instead each variant either refers to either an explicit value for its discriminant, or the distance from the last explicit discriminant, if any * the `.discriminants(tcx)` method produces an iterator of `ConstInt` values, looking up explicit discriminants in a separate map, if necessary * this allows computing `ty::AdtDef` as a leaf (reading only its own HIR) * Small note: the two above (`Generics`, `AdtDef`), `TraitDef` and `AssociatedItem` should probably end up as part of the HIR, eventually, as they're trivially constructed from it * `ty::FnSig` * now also holds ABI and unsafety, alongside argument types, return type and C variadicity * `&ty::BareFnTy` and `ty::ClosureTy` have been replaced with `PolyFnSig = Binder<FnSig>` * `BareFnTy` was interned and `ClosureTy` was treated as non-trivial to `Clone` because they had a `PolyFnSig` and so used to contain a `Vec<Ty>` (now `&[Ty]`) * `ty::maps` * all the `DepTrackingMap`s have been grouped in a structure available at `tcx.maps` * when creating the `tcx`, a set of `Providers` (one `fn` pointer per map) is required for the local crate, and one for all other crates (i.e. metadata loading), `librustc_driver` plugging the various crates (e.g. `librustc_metadata`, `librustc_typeck`, `librustc_mir`) into it * when a map is queried and the value is missing, the appropriate `fn` pointer from the `Providers` of that crate is called with the `TyCtxt` and the key being queried, to produce the value on-demand * `rustc_const_eval` * demands both `typeck_tables` and `mir_const_qualif` (in preparation for miri) * tracks `Substs` in `ConstVal::Function` for `const fn` calls * returns `TypeckError` if type-checking has failed (or cases that can only be reached if it had) * this error kind is never reported, resulting in less noisy/redundant diagnostics * fixes #39548 (testcase by @larsluthman, taken from #39812, which this supersedes) * on-demand has so far been hooked up to: * `rustc_metadata::cstore_impl`: `ty`, `generics`, `predicates`, `super_predicates`, `trait_def`, `adt_def`, `variances`, `associated_item_def_ids`, `associated_item`, `impl_trait_ref`, `custom_coerce_unsized_kind`, `mir`, `mir_const_qualif`, `typeck_tables`, `closure_kind`, `closure_type` * `rustc_typeck::collect`: `ty`, `generics`, `predicates`, `super_predicates`, `type_param_predicates`, `trait_def`, `adt_def`, `impl_trait_ref` * `rustc_typeck::coherence`: `coherent_trait`, `coherent_inherent_impls` * `rustc_typeck::check`: `typeck_tables`, `closure_type`, `closure_kind` * `rustc_mir::mir_map`: `mir` * `rustc_mir::transform::qualify_consts`: `mir_const_qualif`

@larsluthman

[12/12] On-demand type-checking, const-evaluation, MIR building & const-qualification. _This is the last of a series ([prev](#38813)) of patches designed to rework rustc into an out-of-order on-demand pipeline model for both better feature support (e.g. [MIR-based](https://github.com/solson/miri) early constant evaluation) and incremental execution of compiler passes (e.g. type-checking), with beneficial consequences to IDE support as well. If any motivation is unclear, please ask for additional PR description clarifications or code comments._ <hr> As this contains all of the changes that didn't fit neatly into other PRs, I'll be elaborating a bit: ### User-facing changes * when determining whether an `impl Trait` type implements an auto-trait (e.g. `Send` or `Sync`), the function the `impl Trait` came from has to be inferred and type-checking, disallowing cycles * this results from not having an obvious place to put the "deferred obligation" in on-demand atm * while we could model side-effects like that and "post-processing passes" better, it's still more limiting than being able to know the result in the original function (e.g. specialization) *and* there are serious problems around region-checking (if a `Send` impl required `'static`, it wasn't enforced) * early const-eval requires type-checking and const-qualification to be performed first, which means: * you get the intended errors before (if any) constant evaluation error that is simply fallout * associated consts should always work now, and `const fn` type parameters are properly tracked * don't get too excited, array lengths still can't depend on type parameters * #38864 works as intended now, with `Self` being allowed in `impl` bounds * #32205 is largely improved, with associated types being limited to "exact match" `impl`s (as opposed to traversing the specialization graph to resolve unspecified type parameters to their defaults in another `impl` or in the `trait`) *while* checking for overlaps building the specialization graph for that trait - once all the trait impls' have been checked for coherence (including ahead-of-time/on-demand), it's uniform * [crater report](https://gist.github.com/eddyb/bbb869072468c7e08d6d808e75938051) looks clean (aside from `clippy` which broke due to `rustc` internal changes) ### Compiler-internal changes * `ty::Generics` * no longer contains the actual type parameter defaults, instead they're associated with the type parameter's `DefId`, like associated types in a trait definition * this allows computing `ty::Generics` as a leaf (reading only its own HIR) * holds a mapping from `DefIndex` of type parameters to their indices * `ty::AdtDef` * only tracks `#[repr(simd)]` in its `ReprOptions` `repr` field * doesn't contain `enum` discriminant values, but instead each variant either refers to either an explicit value for its discriminant, or the distance from the last explicit discriminant, if any * the `.discriminants(tcx)` method produces an iterator of `ConstInt` values, looking up explicit discriminants in a separate map, if necessary * this allows computing `ty::AdtDef` as a leaf (reading only its own HIR) * Small note: the two above (`Generics`, `AdtDef`), `TraitDef` and `AssociatedItem` should probably end up as part of the HIR, eventually, as they're trivially constructed from it * `ty::FnSig` * now also holds ABI and unsafety, alongside argument types, return type and C variadicity * `&ty::BareFnTy` and `ty::ClosureTy` have been replaced with `PolyFnSig = Binder<FnSig>` * `BareFnTy` was interned and `ClosureTy` was treated as non-trivial to `Clone` because they had a `PolyFnSig` and so used to contain a `Vec<Ty>` (now `&[Ty]`) * `ty::maps` * all the `DepTrackingMap`s have been grouped in a structure available at `tcx.maps` * when creating the `tcx`, a set of `Providers` (one `fn` pointer per map) is required for the local crate, and one for all other crates (i.e. metadata loading), `librustc_driver` plugging the various crates (e.g. `librustc_metadata`, `librustc_typeck`, `librustc_mir`) into it * when a map is queried and the value is missing, the appropriate `fn` pointer from the `Providers` of that crate is called with the `TyCtxt` and the key being queried, to produce the value on-demand * `rustc_const_eval` * demands both `typeck_tables` and `mir_const_qualif` (in preparation for miri) * tracks `Substs` in `ConstVal::Function` for `const fn` calls * returns `TypeckError` if type-checking has failed (or cases that can only be reached if it had) * this error kind is never reported, resulting in less noisy/redundant diagnostics * fixes #39548 (testcase by @larsluthman, taken from #39812, which this supersedes) * on-demand has so far been hooked up to: * `rustc_metadata::cstore_impl`: `ty`, `generics`, `predicates`, `super_predicates`, `trait_def`, `adt_def`, `variances`, `associated_item_def_ids`, `associated_item`, `impl_trait_ref`, `custom_coerce_unsized_kind`, `mir`, `mir_const_qualif`, `typeck_tables`, `closure_kind`, `closure_type` * `rustc_typeck::collect`: `ty`, `generics`, `predicates`, `super_predicates`, `type_param_predicates`, `trait_def`, `adt_def`, `impl_trait_ref` * `rustc_typeck::coherence`: `coherent_trait`, `coherent_inherent_impls` * `rustc_typeck::check`: `typeck_tables`, `closure_type`, `closure_kind` * `rustc_mir::mir_map`: `mir` * `rustc_mir::transform::qualify_consts`: `mir_const_qualif`

steveklabnik · 2018-09-24T18:19:26Z

This no longer ICEs, and compiles just fine. Closing!

aturon added I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ A-traits Area: Trait system A-compiler labels Mar 11, 2016

aturon added a commit to aturon/rust that referenced this issue Mar 13, 2016

Introduce ICE when the topmost projection restriction kicks in, as pe…

8eb4811

…r issue rust-lang#32205

aturon added a commit to aturon/rust that referenced this issue Mar 14, 2016

Introduce ICE when the topmost projection restriction kicks in, as pe…

e36620d

…r issue rust-lang#32205

rphmeier mentioned this issue May 7, 2016

Unhelpful error message for specialization-related type projection failures. #33481

Open

weiznich mentioned this issue Jun 30, 2016

Improve implementation of associations!! diesel-rs/diesel#363

Closed

5 tasks

eddyb mentioned this issue Feb 21, 2017

[12/12] On-demand type-checking, const-evaluation, MIR building & const-qualification. #40008

Merged

steveklabnik added T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. and removed A-compiler labels Mar 24, 2017

eddyb mentioned this issue May 12, 2017

Remove interior mutability from TraitDef by turning fields into queries #41911

Merged

Mark-Simulacrum added the C-bug Category: This is a bug. label Jul 22, 2017

steveklabnik closed this as completed Sep 24, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Remove phase separation between specialization graph construction and projection #32205

Remove phase separation between specialization graph construction and projection #32205

aturon commented Mar 11, 2016

steveklabnik commented Sep 24, 2018

Remove phase separation between specialization graph construction and projection #32205

Remove phase separation between specialization graph construction and projection #32205

Comments

aturon commented Mar 11, 2016

steveklabnik commented Sep 24, 2018