Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

unsoundness relating to WF requirements on trait object types #44454

Closed
nikomatsakis opened this issue Sep 9, 2017 · 18 comments · Fixed by #105546
Closed

unsoundness relating to WF requirements on trait object types #44454

nikomatsakis opened this issue Sep 9, 2017 · 18 comments · Fixed by #105546
Labels
A-trait-system Area: Trait system A-type-system Area: Type system C-bug Category: This is a bug. E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-medium Medium priority T-lang Relevant to the language team, which will review and decide on the PR/issue.

Comments

@nikomatsakis
Copy link
Contributor

nikomatsakis commented Sep 9, 2017

So @scalexm pointed me at this curious example:

trait Animal<X>: 'static { }

fn foo<Y, X>() where Y: Animal<X> + ?Sized {
    // `Y` implements `Animal<X>` so `Y` is 'static.
    baz::<Y>()
}

fn bar<'a>(arg: &'a i32) {
    foo::<Animal<&'a i32>, &'a i32>()
    
    // If you uncomment this line, you will get an error.
    //baz::<Animal<&'a i32>>()
}

fn baz<T: 'static + ?Sized>() {
}

fn main() {
    let a = 5;
    bar(&a);
}

There's a lot going on here, but the key point is that, in the call to foo::<Animal<&'a i32>, &'a i32>, we assume that Animal<&'a i32>: Animal<&'a i32>. This is reasonable, since it's a trait object type -- however, it is a malformed trait object type, and hence one where no impl could ever exist (i.e., we could never make an instance of this type). Interestingly, we are not smart enough to extend this to the case where the 'static bound is applied directly (hence the commented out call to baz::<Animal<&'a i32>>.

At the very least, this is inconsistent behavior, but I feel like there is an unsoundness lurking here. What makes me nervous is that we say that a projection type <P0 as Trait<P1...Pn>>::Foo outlives 'a if Pi: 'a for all i. I am worried that you could use an impl like this:

trait Projector { type Foo; }

impl<X> Projector for Animal<X> {
  type Foo = X;
}

to prove then that <Animal<&'a i32> as Projector>::Foo outlives 'static (say). I have not yet quite managed to weaponize this, but I got pretty close -- that's a gist in which we invoke a function is_static<U: 'static>(u: U) where U will be of type &'a i32 when monomophized. If rustc were as smart as chalk, I suspect we could easily craft a transmute of some kind to &'static i32. There may be a way to do it within current rustc too.

I'm not sure what's the best fix here. I suspect we should require that trait object types meet the WF requirements declared on the trait; and yet, I think the reason we did not is because we don't know the Self type, which means we can't fully validate that. =) This also feels a mite inconsistent with implied bounds. (Perhaps most likely is that we could tweak the WF rules for trait objects to specifically target lifetime bounds, but I have to think about that, feels .. hacky?)

We could tweak the notion of what type parameters are constrained -- or at least which may appear in a projection. e.g., we could disallow that impl of Projector for Animal<X>, because X would not be considered "sufficiently" constrained to appear in type Foo = .... Backwards incompatible, obviously, and feels unfortunate.


This causes actual unsoundness, as discovered by @scalexm in #44454 (comment);

use std::any::Any;

trait Animal<X>: 'static { }

trait Projector {
  type Foo;
}

impl<X> Projector for dyn Animal<X> {
  type Foo = X;
}

fn make_static<'a, T>(t: &'a T) -> &'static T {
    let x: <dyn Animal<&'a T> as Projector>::Foo = t;
    let any = generic::<dyn Animal<&'a T>, &'a T>(x);
    any.downcast_ref::<&'static T>().unwrap()
}

fn generic<T: Projector + Animal<U> + ?Sized, U>(x: <T as Projector>::Foo)
    -> Box<dyn Any>
{
    make_static_any(x)
}

fn make_static_any<U: 'static>(u: U) -> Box<dyn Any> {
    Box::new(u)
}

fn main() {
    let a = make_static(&"salut".to_string());
    println!("{}", *a);
}

cc @arielb1 @aturon

@nikomatsakis nikomatsakis added I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness T-lang Relevant to the language team, which will review and decide on the PR/issue. labels Sep 9, 2017
@nikomatsakis
Copy link
Contributor Author

nikomatsakis commented Sep 9, 2017

Actually, thinking about this more, the problem is maybe not quite how I was thinking of it. That is, it seems like the problem lies in the definition of object safety. That is, if you imagine that you had to write the impl for Animal<X> by hand, it would look like:

impl<X> Animal<X> for Animal<X> { ... }

and this would fail the well-formedness checks because Animal<X>: 'static does not hold, at least not without relying on the impl we are writing =).

The goal of the object safety rules are to ensure such an impl could be written.

Maybe the rules of object safety have to be more conditional -- i.e., Animal<X> is object safe if X: 'static.

@scalexm
Copy link
Member

scalexm commented Sep 9, 2017

Here is an actual unsoundness, using std::any::Any:
https://play.rust-lang.org/?gist=1385ed4e051354b305ea2d2413f8724f&version=stable

@arielb1 arielb1 changed the title *possible* unsoundness relating to WF requirements on trait types *possible* unsoundness relating to WF requirements on trait object types Sep 10, 2017
@arielb1 arielb1 changed the title *possible* unsoundness relating to WF requirements on trait object types unsoundness relating to WF requirements on trait object types Sep 10, 2017
@arielb1
Copy link
Contributor

arielb1 commented Sep 10, 2017

This looks similar to #27675 - in both cases we have a trait object that is not WF.

I think a reasonable way to solve this would be to have a trait object predicate depend on a WF(Self) predicate, so we basically have the rule

'λ₀...'λₙ lifetimes
τ₀...τₙ types
Trait object-safe
~~WF(for<...> Trait<'λ₀...'λₙ, τ₀...τₙ>) - this part is new~~
WF(for<...> Trait<'λ₀...'λₙ, τ₀...τₙ>: Trait<'λ₀...'λₙ, τ₀...τₙ>) - this part is new
----------------
for<...> Trait<'λ₀...'λₙ, τ₀...τₙ>: for<...> Trait<'λ₀...'λₙ, τ₀...τₙ>

@arielb1
Copy link
Contributor

arielb1 commented Sep 11, 2017

The "this part is new" part is actually more subtle than I realized.

Object types (aka dyn Trait<'λ₀...'λₙ, τ₀...τₙ>, to avoid confusion) are actually a funny way of writing

exists<σ> (σ, for<...> WF(dyn Trait<'λ₀...'λₙ, τ₀...τₙ>: Trait<'λ₀...'λₙ, τ₀...τₙ>) → σ: Trait<'λ₀...'λₙ, τ₀...τₙ>)

And the idea is that if the trait is object-safe, we can write a "compiler impl"

impl<'λ₀...'λₙ, τ₀...τₙ> Traitl<'λ₀...'λₙ, τ₀...τₙ> for dyn Trait<'λ₀...'λₙ, τ₀...τₙ> {
    // ...
}

If we want to write such an impl, we need the where-clauses on the trait (both associated types and others) to hold. For supertraits, this follows by obvious induction. For other constraints, this is something that won't hold by itself.

Therefore, we probably need to add these other predicates as conditions on the impl, and have

impl<'λ₀...'λₙ, τ₀...τₙ> Trait<'λ₀...'λₙ, τ₀...τₙ> for dyn Trait<'λ₀...'λₙ, τ₀...τₙ>
    where WF(Trait<'λ₀...'λₙ, τ₀...τₙ>: dyn Trait<'λ₀...'λₙ, τ₀...τₙ>)
{
    // ...
}

@nikomatsakis
Copy link
Contributor Author

I agree that it is the same as #27675. As we said on IRC, I think that the current fix is roughly as I described here -- in particular, when we check that dyn Trait<P...>: Trait<P...>, we need to also check that the where-clauses declared on Trait hold for dyn Trait<P...>. This subsumes some of the object safety checks (e.g. the search for where Self: Sized).

@bstrie
Copy link
Contributor

bstrie commented Sep 14, 2017

I agree that it is the same as #27675.

Shall we close this as a dupe, then?

@nikomatsakis
Copy link
Contributor Author

ping @arielb1 -- whatever happened with your branch here? I remember we had some discussions about cycles and don't recall how (if at all) they were resolved.

@aturon
Copy link
Member

aturon commented Oct 19, 2017

Marking P-medium. While there's overlap with #27675, this issue has more in-depth information. We plan to keep them both open until fixed.

@rust-lang rust-lang deleted a comment from Eallaneg46 Oct 19, 2017
@rust-lang rust-lang deleted a comment from Eallaneg46 Oct 19, 2017
@rust-lang rust-lang deleted a comment from Eallaneg46 Oct 19, 2017
@rust-lang rust-lang deleted a comment from Eallaneg46 Oct 19, 2017
@scalexm scalexm self-assigned this Oct 19, 2018
@Centril Centril added A-type-system Area: Type system A-trait-system Area: Trait system labels Nov 20, 2018
@Elinvynia Elinvynia added the I-prioritize Issue: Indicates that prioritization has been requested for this issue. label Jun 9, 2020
@LeSeulArtichaut LeSeulArtichaut removed the I-prioritize Issue: Indicates that prioritization has been requested for this issue. label Jun 9, 2020
@scalexm
Copy link
Member

scalexm commented Jun 14, 2021

We agreed that this issue and #27675 shared a similar root cause, but my weaponized example still compiles on both stable and nightly and is still unsound.

I did not know about #73905 until now, but it seems to only have fixed the case of Trait<Item = &'a i32> when Item is supposed to be 'static. It’s quite obvious why this case was incorrect in the first place.

Conversely, it’s less obvious why there should be a problem with dyn Animal<&'a i32> + 'static in my initial example. After all, it’s possible to implement Animal<&'a i32> for SomeType: 'static.

The reason being that lifetime requirements are syntactic and if you allow dyn Animal<&'a i32>: Animal<&'a i32> in conjunction with implied bounds, you can derive contradictory things. It’s the same reason why the type fn(&'a i32) is not considered to outlive 'static, even if the underlying object is just a function pointer.

rust-lang/chalk#203 describes a formal solution under the full implied bounds setting (it would need to be slightly adapted for RFC 2027 ).

I think an easy fix with the current limited form of implied bounds would just be to collect all lifetimes appearing in dyn Trait<…> + 'a, and check that they verify the outlive clauses transitively required by Trait. If the check fails, we say thatdyn Trait<…> is not well-formed. I believe this would be sufficient to fix the soundness bug.

@lcnr
Copy link
Contributor

lcnr commented Jul 6, 2022

another repro for the same issue (i think)

trait Trait<ARG: 'static>: 'static {
    type Assoc: AsRef<str>;
}

fn hr<T: ?Sized, ARG>(x: T::Assoc) -> Box<dyn AsRef<str> + 'static>
where
    T: Trait<ARG>
{
    Box::new(x)
}

fn extend_lt<'a>(x: &'a str) -> Box<dyn AsRef<str> + 'static> {
    type DynTrait = dyn for<'a> Trait<&'a str, Assoc = &'a str>;
    hr::<DynTrait, _>(x)
} 

fn main() {
    let extended = extend_lt(&String::from("hello"));
    println!("{}", extended.as_ref().as_ref());
}

@oli-obk
Copy link
Contributor

oli-obk commented Jul 15, 2022

@rustbot claim

@rustbot rustbot assigned oli-obk and unassigned scalexm Jul 15, 2022
@oli-obk oli-obk removed their assignment Aug 30, 2022
@nikomatsakis
Copy link
Contributor Author

We looked at this in the types meeting -- none of the the existing reproductions compile anymore -- but we're not sure if this is truly fixed or not. It's not clear what made them stop compile.

A good first step would be bisecting to see what PR fixed this example:

#44454 (comment)

@oli-obk oli-obk added E-needs-bisection Call for participation: This issue needs bisection: https://github.com/rust-lang/cargo-bisect-rustc E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. E-needs-mcve Call for participation: This issue has a repro, but needs a Minimal Complete and Verifiable Example labels Nov 30, 2022
@Noratrieb
Copy link
Member

Noratrieb commented Nov 30, 2022

searched nightlies: from nightly-2020-01-01 to nightly-2022-11-30
regressed nightly: nightly-2022-08-10
searched commit range: f03ce30...34a6cae
regressed commit: 63e4312

bisected with cargo-bisect-rustc v0.6.4

Host triple: x86_64-unknown-linux-gnu
Reproduce with:

cargo bisect-rustc --access github --regress error

so it was fixed by #99217

@lcnr
Copy link
Contributor

lcnr commented Nov 30, 2022

it looks like the original unsoundness was fixed before #99217, it seems like that stopped compiling in 1.61. @Nilstrieb can I get you to bisect this one as well?

use std::any::Any;

trait Animal<X>: 'static { }

trait Projector {
  type Foo;
}

impl<X> Projector for dyn Animal<X> {
  type Foo = X;
}

fn make_static<'a, T>(t: &'a T) -> &'static T {
    let x: <dyn Animal<&'a T> as Projector>::Foo = t;
    let any = generic::<dyn Animal<&'a T>, &'a T>(x);
    any.downcast_ref::<&'static T>().unwrap()
}

fn generic<T: Projector + Animal<U> + ?Sized, U>(x: <T as Projector>::Foo)
    -> Box<dyn Any>
{
    make_static_any(x)
}

fn make_static_any<U: 'static>(u: U) -> Box<dyn Any> {
    Box::new(u)
}

fn main() {
    let a = make_static(&"salut".to_string());
    println!("{}", *a);
}

@albertlarsan68
Copy link
Member

I got Regression in nightly-2022-03-16, which maps to

2022-03-14UTC: Auto merge of #94929 - flip1995:clippyup, r=Manishearth
2022-03-14UTC: Auto merge of #94935 - matthiaskrgr:rollup-2o2kyz6, r=matthiaskrgr
2022-03-15UTC: Auto merge of #92285 - compiler-errors:dyn-proj-bounds, r=nikomatsakis
2022-03-15UTC: Auto merge of #94584 - pnkfelix:inject-use-suggestion-sites, r=ekuber
2022-03-15UTC: Auto merge of #94938 - lnicola:rust-analyzer-2022-03-14, r=lnicola
2022-03-15UTC: Auto merge of #94261 - michaelwoerister:debuginfo-types-refactor, r=wesleywiser
2022-03-15UTC: Auto merge of #94928 - lcnr:inline-as_substs, r=michaelwoerister
2022-03-15UTC: Auto merge of #94966 - matthiaskrgr:rollup-iqzswh3, r=matthiaskrgr
2022-03-15UTC: Auto merge of #94973 - GuillaumeGomez:more-gui-tests, r=notriddle

Unfortunately, there is no CI builds anymore for this range, and I do not have the power to bisect those commit myself now.

Reproduce with cargo bisect-rustc --access=github --end 1.61.0 -- check

@oli-obk
Copy link
Contributor

oli-obk commented Dec 1, 2022

I'm guessing it was @compiler-errors' #92285

@compiler-errors compiler-errors removed E-needs-bisection Call for participation: This issue needs bisection: https://github.com/rust-lang/cargo-bisect-rustc E-needs-mcve Call for participation: This issue has a repro, but needs a Minimal Complete and Verifiable Example labels Dec 1, 2022
@lcnr
Copy link
Contributor

lcnr commented Dec 1, 2022

that's cool, looks like we only need the add ui tests and can then close this issue 🎉

JohnTitor added a commit to JohnTitor/rust that referenced this issue Dec 11, 2022
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue Dec 11, 2022
…errors

Add some regression tests for rust-lang#44454

Closes rust-lang#44454
r? `@compiler-errors`

Signed-off-by: Yuki Okushi <[email protected]>
bors added a commit to rust-lang-ci/rust that referenced this issue Dec 11, 2022
…iaskrgr

Rollup of 6 pull requests

Successful merges:

 - rust-lang#105411 (Introduce `with_forced_trimmed_paths`)
 - rust-lang#105532 (Document behaviour of `--remap-path-prefix` with several matches)
 - rust-lang#105537 (compiler: remove unnecessary imports and qualified paths)
 - rust-lang#105539 (rustdoc: Only hide lines starting with `#` in rust code blocks )
 - rust-lang#105546 (Add some regression tests for rust-lang#44454)
 - rust-lang#105547 (Add regression test for rust-lang#104582)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup
@bors bors closed this as completed in f145825 Dec 11, 2022
@fmease fmease added A-trait-system Area: Trait system and removed A-trait-system Area: Trait system labels Dec 21, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-trait-system Area: Trait system A-type-system Area: Type system C-bug Category: This is a bug. E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-medium Medium priority T-lang Relevant to the language team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.