Implement a feature for a sound specialization subset

[matthewjasper]

This implements a new feature (min_specialization) that restricts specialization to a subset that is reasonable for the standard library to use.

The plan is to then:

• Update libcore and liballoc to compile with min_specialization.
• Add a lint to forbid use of feature(specialization) (and other unsound, type system extending features) in the standard library.
• Fix the soundness issues around specialization.
• Remove min_specialization

The rest of this is an overview from a comment in this PR

Basic approach

To enforce this requirement on specializations we take the following approach:

1. Match up the substs for impl2 so that the implemented trait and self-type match those for impl1.
2. Check for any direct use of 'static in the substs of impl2.
3. Check that all of the generic parameters of impl1 occur at most once in the unconstrained substs for impl2. A parameter is constrained if its value is completely determined by an associated type projection predicate.
4. Check that all predicates on impl1 also exist on impl2 (after matching substs).

Example

Suppose we have the following always applicable impl:

impl<T> SpecExtend<T> for std::vec::IntoIter<T> { /* specialized impl */ }
impl<T, I: Iterator<Item=T>> SpecExtend<T> for I { /* default impl */ }

We get that the subst for impl2 are [T, std::vec::IntoIter<T>]. T is constrained to be <I as Iterator>::Item, so we check only std::vec::IntoIter<T> for repeated parameters, which it doesn't have. The predicates of impl1 are only T: Sized, which is also a predicate of impl2`. So this specialization is sound.

Extensions

Unfortunately not all specializations in the standard library are allowed by this. So there are two extensions to these rules that allow specializing on some traits.

rustc_specialization_trait

If a trait is always applicable, then it's sound to specialize on it. We check trait is always applicable in the same way as impls, except that step 4 is now "all predicates on impl1 are always applicable". We require that specialization or min_specialization is enabled to implement these traits.

rustc_unsafe_specialization_marker

There are also some specialization on traits with no methods, including the FusedIterator trait which is advertised as allowing optimizations. We allow marking marker traits with an unstable attribute that means we ignore them in point 3 of the checks above. This is unsound but we allow it in the short term because it can't cause use after frees with purely safe code in the same way as specializing on traits methods can.

r? @nikomatsakis
cc #31844 #67194

[bors]

☔ The latest upstream changes (presumably #69004) made this pull request unmergeable. Please resolve the merge conflicts.

[davidhewitt]

Is there any feeling whether this would be stabilized ahead of soundness issues being fixed in specialization?

pyo3 currently requires nightly, because too many of its APIs have made use of specialization.

If this feature becomes stable, it might just be possible to rework pyo3 to use it rather than the more complicated task of removing specialization entirely.

[nikomatsakis]

First round of reviews! Mostly requests for documentation, but also some substantive questions.

[nikomatsakis]

I find this term ("Specializing on this trait") a bit ambiguous. I think it means "Specialized impls of this trait are allowed"? Maybe we can update the comment to be more precise.

You mentioned that this is not sound in general. I'm not sure if that's true, actually -- for marker traits, I don't think specialization causes any problems. Maybe I don't know what you mean by that, though.

[nikomatsakis]

I think this function would benefit from a bigger comment (also, doc comment). I think it should be something like:

---

Given a specializing impl impl1, and the base impl impl2, returns two substitutions (S1, S2) that equate their trait references. The returned types are expressed in terms of the generics of impl1.

Example:

impl<A, B> Foo<A> for B { /* impl2 */ }
impl<C> Foo<Vec<C>> for C { /* impl1 */ }

Here we would return S1 = [C] and S2 = [Vec<C>, C].

[nikomatsakis]

It would be good to comment why you chose this function. I think the example would be something like:

impl<A> Foo for A { }
impl<B> Foo for dyn Iterator<Item = (B, B)> { }

and here we want to say that, even though B repeats, it's ok because it's constrained?

Another example might be like dyn Foo<B, Out = B> -- this would also be approved.

But, thinking on it more, is that really correct? Like consider the type dyn Foo<&'a u32, Out = &'b u32>. How can we decide whether the impl applies? We'd have to know that 'a = 'b.

[matthewjasper]

parameters_for(_, true) doesn't have any special handling of any TyKind. I'm using it to conveniently handle the 3 different kinds of params.

[nikomatsakis]

Oh, I see. Man, I hate random booleans in the signature, but pre-existing I suppose. :)

[nikomatsakis]

And quite possibly my fault.

[nikomatsakis]

@bors r+

[bors]

📌 Commit c9cd389dd690725c15d5dd0cf030376ea7fdeccb has been approved by nikomatsakis

[bors]

☔ The latest upstream changes (presumably #69076) made this pull request unmergeable. Please resolve the merge conflicts.

[rust-highfive]

The job mingw-check of your PR failed (pretty log, raw log). Through arcane magic we have determined that the following fragments from the build log may contain information about the problem.

Click to expand the log.

2020-03-15T12:51:20.1305064Z ========================== Starting Command Output ===========================
2020-03-15T12:51:20.1310305Z [command]/bin/bash --noprofile --norc /home/vsts/work/_temp/d254c262-04cf-4cec-859e-3f8b708e054e.sh
2020-03-15T12:51:20.1310849Z 
2020-03-15T12:51:20.1315598Z ##[section]Finishing: Disable git automatic line ending conversion
2020-03-15T12:51:20.1336454Z ##[section]Starting: Checkout rust-lang/rust@refs/pull/68970/merge to s
2020-03-15T12:51:20.1339963Z Task         : Get sources
2020-03-15T12:51:20.1340290Z Description  : Get sources from a repository. Supports Git, TfsVC, and SVN repositories.
2020-03-15T12:51:20.1340623Z Version      : 1.0.0
2020-03-15T12:51:20.1340839Z Author       : Microsoft
---
2020-03-15T12:51:21.1215672Z ##[command]git remote add origin https://github.com/rust-lang/rust
2020-03-15T12:51:21.1222546Z ##[command]git config gc.auto 0
2020-03-15T12:51:21.1226606Z ##[command]git config --get-all http.https://github.com/rust-lang/rust.extraheader
2020-03-15T12:51:21.1230271Z ##[command]git config --get-all http.proxy
2020-03-15T12:51:21.1237028Z ##[command]git -c http.extraheader="AUTHORIZATION: basic ***" fetch --force --tags --prune --progress --no-recurse-submodules --depth=2 origin +refs/heads/*:refs/remotes/origin/* +refs/pull/68970/merge:refs/remotes/pull/68970/merge
---
2020-03-15T12:59:11.3696947Z     Checking rustc_infer v0.0.0 (/checkout/src/librustc_infer)
2020-03-15T12:59:14.6927887Z     Checking rustc_ast_lowering v0.0.0 (/checkout/src/librustc_ast_lowering)
2020-03-15T12:59:14.9017832Z     Checking rustc_codegen_utils v0.0.0 (/checkout/src/librustc_codegen_utils)
2020-03-15T12:59:15.4453051Z     Checking rustc_trait_selection v0.0.0 (/checkout/src/librustc_trait_selection)
2020-03-15T12:59:15.5082581Z error: expected `;`, found ``map_err``
2020-03-15T12:59:15.5083988Z      |
2020-03-15T12:59:15.5083988Z      |
2020-03-15T12:59:15.5084766Z 1014 |                     assoc_ty_def(selcx, impl_data.impl_def_id, obligation.predicate.item_def_id)
2020-03-15T12:59:15.5085965Z      |                                                                                                 ^ help: add `;` here
2020-03-15T12:59:15.5087199Z 1015 |                     map_err(|ErrorReported| ())?;
2020-03-15T12:59:15.5088104Z      |                     ------- unexpected token
2020-03-15T12:59:16.7471972Z error[E0425]: cannot find function `map_err` in this scope
2020-03-15T12:59:16.7478661Z     --> src/librustc_trait_selection/traits/project.rs:1015:21
2020-03-15T12:59:16.7479553Z      |
2020-03-15T12:59:16.7479553Z      |
2020-03-15T12:59:16.7480414Z 1015 |                     map_err(|ErrorReported| ())?;
2020-03-15T12:59:16.7482120Z 
2020-03-15T12:59:16.7482120Z 
2020-03-15T12:59:16.9119640Z error[E0609]: no field `node` on type `std::result::Result<rustc::traits::specialization_graph::NodeItem<rustc::ty::AssocItem>, rustc_errors::ErrorReported>`
2020-03-15T12:59:16.9121314Z      |
2020-03-15T12:59:16.9122026Z 1017 |                 let is_default = if node_item.node.is_from_trait() {
2020-03-15T12:59:16.9122892Z      |                                               ^^^^
2020-03-15T12:59:16.9127064Z 
2020-03-15T12:59:16.9127064Z 
2020-03-15T12:59:16.9160649Z error[E0609]: no field `item` on type `std::result::Result<rustc::traits::specialization_graph::NodeItem<rustc::ty::AssocItem>, rustc_errors::ErrorReported>`
2020-03-15T12:59:16.9162412Z      |
2020-03-15T12:59:16.9163087Z 1039 |                     node_item.item.defaultness.is_default()
2020-03-15T12:59:16.9163818Z      |                               ^^^^
2020-03-15T12:59:16.9167677Z 
2020-03-15T12:59:16.9167677Z 
2020-03-15T12:59:16.9199879Z error[E0609]: no field `node` on type `std::result::Result<rustc::traits::specialization_graph::NodeItem<rustc::ty::AssocItem>, rustc_errors::ErrorReported>`
2020-03-15T12:59:16.9201485Z      |
2020-03-15T12:59:16.9201485Z      |
2020-03-15T12:59:16.9202282Z 1040 |                         || super::util::impl_is_default(selcx.tcx(), node_item.node.def_id())
2020-03-15T12:59:16.9207234Z 
2020-03-15T12:59:16.9207234Z 
2020-03-15T12:59:16.9249263Z error[E0609]: no field `item` on type `std::result::Result<rustc::traits::specialization_graph::NodeItem<rustc::ty::AssocItem>, rustc_errors::ErrorReported>`
2020-03-15T12:59:16.9251017Z      |
2020-03-15T12:59:16.9251017Z      |
2020-03-15T12:59:16.9251703Z 1063 | ...                   selcx.tcx().def_path_str(node_item.item.def_id),
2020-03-15T12:59:16.9257216Z 
2020-03-15T12:59:17.4999867Z error: aborting due to 6 previous errors
2020-03-15T12:59:17.5004122Z 
2020-03-15T12:59:17.5013981Z Some errors have detailed explanations: E0425, E0609.
2020-03-15T12:59:17.5013981Z Some errors have detailed explanations: E0425, E0609.
2020-03-15T12:59:17.5024146Z For more information about an error, try `rustc --explain E0425`.
2020-03-15T12:59:17.5097433Z error: could not compile `rustc_trait_selection`.
2020-03-15T12:59:17.5118237Z warning: build failed, waiting for other jobs to finish...
2020-03-15T12:59:20.2139596Z error: build failed
2020-03-15T12:59:20.2162952Z command did not execute successfully: "/checkout/obj/build/x86_64-unknown-linux-gnu/stage0/bin/cargo" "check" "-Zconfig-profile" "--target" "x86_64-unknown-linux-gnu" "-Zbinary-dep-depinfo" "-j" "2" "--release" "--color" "always" "--features" " llvm" "--manifest-path" "/checkout/src/rustc/Cargo.toml" "--message-format" "json-render-diagnostics"
2020-03-15T12:59:20.2178552Z failed to run: /checkout/obj/build/bootstrap/debug/bootstrap check
2020-03-15T12:59:20.2179261Z Build completed unsuccessfully in 0:04:40
2020-03-15T12:59:20.2230639Z == clock drift check ==
2020-03-15T12:59:20.2246681Z   local time: Sun Mar 15 12:59:20 UTC 2020
2020-03-15T12:59:20.2246681Z   local time: Sun Mar 15 12:59:20 UTC 2020
2020-03-15T12:59:20.3862031Z   network time: Sun, 15 Mar 2020 12:59:20 GMT
2020-03-15T12:59:20.3863843Z == end clock drift check ==
2020-03-15T12:59:20.9782781Z 
2020-03-15T12:59:20.9862198Z ##[error]Bash exited with code '1'.
2020-03-15T12:59:20.9887197Z ##[section]Finishing: Run build
2020-03-15T12:59:20.9939464Z ##[section]Starting: Checkout rust-lang/rust@refs/pull/68970/merge to s
2020-03-15T12:59:20.9944654Z Task         : Get sources
2020-03-15T12:59:20.9945028Z Description  : Get sources from a repository. Supports Git, TfsVC, and SVN repositories.
2020-03-15T12:59:20.9945353Z Version      : 1.0.0
2020-03-15T12:59:20.9945788Z Author       : Microsoft
2020-03-15T12:59:20.9945788Z Author       : Microsoft
2020-03-15T12:59:20.9946199Z Help         : [More Information](https://go.microsoft.com/fwlink/?LinkId=798199)
2020-03-15T12:59:20.9946613Z ==============================================================================
2020-03-15T12:59:21.3542718Z Cleaning any cached credential from repository: rust-lang/rust (GitHub)
2020-03-15T12:59:21.3585475Z ##[section]Finishing: Checkout rust-lang/rust@refs/pull/68970/merge to s
2020-03-15T12:59:21.3676665Z Cleaning up task key
2020-03-15T12:59:21.3677989Z Start cleaning up orphan processes.
2020-03-15T12:59:21.3868892Z Terminate orphan process: pid (3645) (python)
2020-03-15T12:59:21.4058787Z ##[section]Finishing: Finalize Job

I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact @rust-lang/infra. (Feature Requests)

[rust-highfive]

The job dist-powerpc64-linux of your PR failed (pretty log, raw log). Through arcane magic we have determined that the following fragments from the build log may contain information about the problem.

Click to expand the log.

I'm a bot! I can only do what humans tell me to, so if this was not helpful or you have suggestions for improvements, please ping or otherwise contact @rust-lang/infra. (Feature Requests)

[bors]

💔 Test failed - checks-azure

[mark-i-m]

Looks like a network failure?

[lqd]

it was the crates.io temporary failure indeed
@bors retry

[bors]

⌛ Testing commit 39ee66a with merge e24252a...

[bors]

☀️ Test successful - checks-azure
Approved by: nikomatsakis
Pushing e24252a to master...

[eggyal]

Are there soundness issues with specializing associated constants? If not, could they be permissible in min_specialization?

[matthewjasper]

The reason to only for functions being a simpler than constants and types is that we only ever work out which impl to select for a (non-const) function when generating code. For constants we can evaluate them during type checking and during codegen and I wanted to avoid potential bugs with any mismatches there.