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

Implied bounds by associated types as function parameters are inconsistent in an unsound way. #91068

Closed
steffahn opened this issue Nov 20, 2021 · 24 comments
Labels
A-associated-items Area: Associated items (types, constants & functions) A-lifetimes Area: Lifetimes / regions A-trait-system Area: Trait system A-type-system Area: Type system C-bug Category: This is a bug. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-critical Critical priority regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-types Relevant to the types team, which will review and decide on the PR/issue.

Comments

@steffahn
Copy link
Member

Taking a simple trait

trait Trait {
    type Type;
}

impl<T> Trait for T {
    type Type = ();
}

the type <&'a &'b () as Trait>::Type as a function argument gives rise to a 'a: 'b bound, as can be demonstrated by e.g.

fn f<'a, 'b>(s: &'b str, _: <&'a &'b () as Trait>::Type) -> &'a str {
    s
}

However, this bound is apparently not really enforced. I suppose the compiler “simplifies” such a function to f<'a, 'b>(s: &'b str, _: ()) -> &'a str for the caller? So

fn main() {
    let x = String::from("Hello World!");
    let y = f(&x, ());
    drop(x);
    println!("{}", y);
}

compiles fine and produces UB. (playground)

Another implication of the same kind of issue is that a function like

type Type<T> = <T as Trait>::Type;

fn g<'a>(_: Type<&'a ()>) -> &'a str {
    ""
}

fails to compile with a weird error message.

   Compiling playground v0.0.1 (/playground)
error[E0581]: return type references lifetime `'a`, which is not constrained by the fn input types
  --> src/lib.rs:11:30
   |
11 | fn g<'a>(_: Type<&'a ()>) -> &'a str {
   |                              ^^^^^^^

For more information about this error, try `rustc --explain E0581`.

The error code 581 only talks about fn-pointer types (playground)

@rustbot label T-compiler, A-lifetimes, A-typesystem, A-traits, A-associated-items, I-unsound

Originally discovered in a discussion on URLO.

@steffahn steffahn added the C-bug Category: This is a bug. label Nov 20, 2021
@rustbot rustbot added A-associated-items Area: Associated items (types, constants & functions) A-lifetimes Area: Lifetimes / regions A-trait-system Area: Trait system A-type-system Area: Type system I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Nov 20, 2021
@steffahn steffahn changed the title Implied bounds by types of associated items are inconsistent in an unsound way. Implied bounds by associated types as function parameters are inconsistent in an unsound way. Nov 20, 2021
@ecstatic-morse
Copy link
Contributor

Another dupe of #25860?

@Cyborus04
Copy link
Contributor

Another dupe of #25860?

I knew I had seen something like this before, I was just searching through my history to see if I could find it haha

@steffahn
Copy link
Member Author

steffahn commented Nov 20, 2021

Another dupe of #25860?

No, not a dupe of #25860. This issue has nothing to do with variance.

Edit: To be clear, the issues are certainly related and I wouldn't be surprised if a fix of #25860 also fixes this issue.

@danielhenrymantilla
Copy link
Contributor

I can confirm this doesn't have to do with variance:

trait Trait { type T; }
impl Trait for &'_ &'_ () { type T = (); }

/// Invariant
struct Inv<'lt>(fn(&()) -> &mut &'lt ());

fn transmute_lt<'src : 'src, 'dst : 'dst> (
    s: Inv<'src>,
    // `'src : 'dst` i.e. `'src ⊇ 'dst`
    _dst_implied_smaller: <&'dst &'src () as Trait>::T,
    // `'dst : 'src` i.e. `'dst ⊇ 'src`
    _dst_implied_greater: <&'src &'dst () as Trait>::T,
) -> Inv<'dst> {
    // => `'src = 'dst` => does typecheck
    s
}

/// Typechecks!
fn enlarge<'short, 'long : 'short> (
    it: Inv<'short>,
) -> Inv<'long>
{
    // signature of transmute_lt:
    let f: fn(Inv<'short>, (), ()) -> Inv<'long> = transmute_lt::<'short, 'long>;
    f(it, (), ())
}

@steffahn
Copy link
Member Author

steffahn commented Nov 20, 2021

To demonstrate the point that this has nothing to do with variance or double-references, here's the same thing with a custom invariant struct

struct S<'a: 'static>(*mut &'a ());

fn f<'a>(s: &'a str, _: <S<'a> as Trait>::Type) -> &'static str {
    s
}

// same main function…

(playground)

@steffahn
Copy link
Member Author

The same bug can (not too surprisingly) also be used to write trait implementations that (unsoundly) have additional implied bounds available in the method body. E.g.

trait Trait<Dummy> {
    type Type;
}

impl<T, Dummy> Trait<Dummy> for T {
    type Type = T;
}

struct StrRef<'a>(&'a str);

impl<'a, 'b> From<&'a str> for StrRef<'b> {
    fn from(s: <&'a str as Trait<&'b &'a str>>::Type) -> StrRef<'b> {
        Self(s)
    }
}

fn main() {
    let x = String::from("Hello World!");
    let y = StrRef::from(x.as_str()).0;
    drop(x);
    println!("{}", y);
}

(playground)

@apiraino
Copy link
Contributor

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-critical

@rustbot rustbot added P-critical Critical priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Nov 22, 2021
@steffahn
Copy link
Member Author

steffahn commented Nov 22, 2021

Just checked what rust versions are affected. My original example only works from 1.56, so the latest rust version.

@rustbot label regression-from-stable-to-stable, E-needs-bisection

Edit: Same goes for the example involving From above, as well as @danielhenrymantilla's example or my invariant example. Only the problem with

type Type<T> = <T as Trait>::Type;

fn g<'a>(_: Type<&'a ()>) -> &'a str {
    ""
}

not compiling appears to be older.

@rustbot rustbot added regression-from-stable-to-stable Performance or correctness regression from one stable version to another. E-needs-bisection Call for participation: This issue needs bisection: https://github.com/rust-lang/cargo-bisect-rustc labels Nov 22, 2021
@steffahn
Copy link
Member Author

searched nightlies: from nightly-2021-05-01 to nightly-2021-11-22
regressed nightly: nightly-2021-08-30
searched commit range: 5eacec9...2f662b1
regressed commit: 59ce765

bisected with cargo-bisect-rustc v0.6.1

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

cargo bisect-rustc --regress non-error --access github --start 2021-05-01 

@rustbot label -E-needs-bisection

@rustbot rustbot removed the E-needs-bisection Call for participation: This issue needs bisection: https://github.com/rust-lang/cargo-bisect-rustc label Nov 22, 2021
@steffahn
Copy link
Member Author

That’s

cc @jackh726, @nikomatsakis

@steffahn
Copy link
Member Author

Edit: Same goes for the example involving From above, as well as @danielhenrymantilla's example or my invariant example.

Double-checked, they’re all regressing at #88312

@jackh726
Copy link
Member

Well...shoot.

I guess we can either just revert #88312 for now or change the rule to be something like "if all the parameters of an associated type are well formed, then the associated type is", which should solve this.

@steffahn
Copy link
Member Author

I suppose #88312 was only fixing a problem observable on nightly, correct? If reverting (for now) is done easily (i.e. no subsequent changes rely on #88312), then I suppose by reverting, we could get a fix out quickly and perhaps even get it beta-backported so that 1.57 is no longer affected? (I assume doing anything other than a revert is not really possible anymore time-wise until 1.57 release next week.)

@steffahn
Copy link
Member Author

change the rule to be something like "if all the parameters of an associated type are well formed, then the associated type is"

I can't comment on the alternative you lay out here, since I'm not at all familiar with the details of what's going on here. If this is just an oversight in #88312 / easily fixed / not a fundamental problem with that PR; and if it seems very unlikely to introduce any other issues, then that other approach might also work for inclusion in 1.57? A revert might be easier though.

@steffahn
Copy link
Member Author

@jackh726

change the rule to be something like "if all the parameters of an associated type are well formed, then the associated type is

would this imply that

trait Trait {
    type Type;
}

impl<T> Trait for T {
    type Type = ();
}

fn f<'a, 'b>(_: <&'a &'b () as Trait>::Type) where 'a: 'a, 'b: 'b {}
fn g<'a, 'b>() {
    f::<'a, 'b>(());
}

no longer compiles? (Because if yes, that would be a regression for code that works since Rust 1.0!)

@steffahn
Copy link
Member Author

Only the problem with

type Type<T> = <T as Trait>::Type;

fn g<'a>(_: Type<&'a ()>) -> &'a str {
    ""
}

not compiling appears to be older.

Looks like this observation might be an instance of #47511.

@jackh726
Copy link
Member

I suppose #88312 was only fixing a problem observable on nightly, correct?

This is correct.

then I suppose by reverting, we could get a fix out quickly

Also correct.

would this imply that ... no longer compiles?

I'm not sure yet; probably this should still compile. Really, the point of #88312 was to recognize that if an associated type is created, then the where clauses/bounds on that associated type must have been met. Well, the wrinkle here is that in <&'a &'b () as Trait>::Type, we don't necessarily have to create a &'a &'b to create a <&'a &'b () as Trait>::Type.

@Aaron1011
Copy link
Member

PRs #91243 and #91242 have been opened to fix this on nightly and beta (by partially reverting #88312)

@pnkfelix
Copy link
Member

pnkfelix commented Dec 2, 2021

Addressed by PR #91243 and PR #91361, fixed in 1.57 release. Closing.

@pnkfelix pnkfelix closed this as completed Dec 2, 2021
@steffahn
Copy link
Member Author

steffahn commented Dec 2, 2021

It might make sense to also add a test for the case I listed above, i.e.

trait Trait {
    type Type;
}

impl<T> Trait for T {
    type Type = ();
}

fn f<'a, 'b>(_: <&'a &'b () as Trait>::Type) where 'a: 'a, 'b: 'b {}
fn g<'a, 'b>() {
    f::<'a, 'b>(());
}

to make sure future updates don't break code like that?

@jackh726
Copy link
Member

jackh726 commented Dec 2, 2021

@steffahn any way I can convince you to make a PR for that and I'll review?

@steffahn
Copy link
Member Author

steffahn commented Dec 2, 2021

I can make the PR. I just don’t know where exactly the test should go.

@jackh726
Copy link
Member

jackh726 commented Dec 2, 2021

Probably just src/test/ui/fn/implied-bounds-unnorm-associated-type-2.rs

matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Dec 2, 2021
…, r=jackh726

Add additional test from rust issue number 91068

see rust-lang#91068

r? `@jackh726`
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Dec 2, 2021
…, r=jackh726

Add additional test from rust issue number 91068

see rust-lang#91068

r? ``@jackh726``
bors added a commit to rust-lang-ci/rust that referenced this issue Aug 9, 2022
consider unnormalized types for implied bounds

extracted, and slightly modified, from rust-lang#98900

The idea here is that generally, rustc is split into things which can assume its inputs are well formed[^1], and things which have verify that themselves.

Generally most predicates should only deal with well formed inputs, e.g. a `&'a &'b (): Trait` predicate should be able to assume that `'b: 'a` holds. Normalization can loosen wf requirements (see rust-lang#91068) and must therefore not be used in places which still have to check well formedness. The only such place should hopefully be `WellFormed` predicates

fixes rust-lang#87748 and rust-lang#98543

r? `@jackh726` cc `@rust-lang/types`

[^1]: These places may still encounter non-wf inputs and have to deal with them without causing an ICE as we may check for well formedness out of order.
@yshui

This comment was marked as resolved.

@compiler-errors compiler-errors added the T-types Relevant to the types team, which will review and decide on the PR/issue. label Oct 11, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-associated-items Area: Associated items (types, constants & functions) A-lifetimes Area: Lifetimes / regions A-trait-system Area: Trait system A-type-system Area: Type system C-bug Category: This is a bug. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-critical Critical priority regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-types Relevant to the types team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests