Stream: t-compiler/help

Topic: substs of Unevaluated consts


lcnr (May 19 2020 at 13:52, on Zulip):

Currently trying to fix https://github.com/rust-lang/rust/issues/72129#issuecomment-627181925

// run-pass
#![feature(const_generics)]
#![allow(incomplete_features, unused_braces)]

trait Bar<T> {}
impl<T> Bar<T> for [u8; {7}] {}

struct Foo<const N: usize> {}
impl<const N: usize> Foo<N>
where
    [u8; N]: Bar<[(); N]>,
{
    fn foo() {}
}

fn main() {
    Foo::foo();
}
lcnr (May 19 2020 at 13:54, on Zulip):

While type checking main, we end up equating Equate.tys([(); ConstVar(_#0c)], TyVar _#1t)

lcnr (May 19 2020 at 13:55, on Zulip):

This means that we instantiante TyVar(_#1t) as [(); ConstVar(_#0c)]

lcnr (May 19 2020 at 13:56, on Zulip):

To do so, we generalize [(); ConstVar(_#0c)], which causes a problem, as ConstVar(_#0c) is already known as Const { ty: usize, val: Unevaluated(DefId(0:7 ~ issue_69654_run_pass[317d]::{{impl}}[0]::{{constant}}[0]), [TyVar _#1t], None) }

lcnr (May 19 2020 at 13:57, on Zulip):

We therefore store TyVar(_#1t) := Const { ty: usize, val: Unevaluated(DefId(0:7 ~ issue_69654_run_pass[317d]::{{impl}}[0]::{{constant}}[0]), [TyVar(_#1t)], None) } in the unification table, causing a stack overflow when trying to resolve this later on.

lcnr (May 19 2020 at 14:05, on Zulip):

I realized I don't even have a clear question to ask here :sweat_smile: Both helpful and unhelpful suggestions are always welcome though.

lcnr (May 19 2020 at 14:50, on Zulip):

Opened https://github.com/rust-lang/rust/pull/72351/ for now

lcnr (May 19 2020 at 18:17, on Zulip):

I think I now understand the problem here, #72351 is incorrect afaict.

lcnr (May 19 2020 at 18:19, on Zulip):

Due to lazy normalization {7} remains as ConstKind::Unevaluated and has T as a subst as it should be able to use T in the future, lets say for

impl<T> Bar<T> for [u8; std::mem::size_of::<T>()] {}
lcnr (May 19 2020 at 18:21, on Zulip):

During type inference, we assemble the candidates for Foo::foo.
Inside of assemble_candidates_from_impl we find an impl of foo and have to to satisfy the where clause [u8; N]: Bar<[(); N]>,.

lcnr (May 19 2020 at 18:23, on Zulip):

We then first unify [u8; N] with [u8; {7}] => N == {7}.

lcnr (May 19 2020 at 18:23, on Zulip):

This means N now has T in its subst.

lcnr (May 19 2020 at 18:24, on Zulip):

When we now unify Bar<T> with Bar[(); N] we set T == [(); N]. Which means T now contains itself as a substitution.

lcnr (May 19 2020 at 18:25, on Zulip):

cc @varkor @nikomatsakis Do you understand this explanation/does this makes sense to you?

lcnr (May 19 2020 at 18:25, on Zulip):

And if so, how could we proceed here?

varkor (May 19 2020 at 19:05, on Zulip):

I'll try to read and reply later this evening.

nikomatsakis (May 19 2020 at 23:36, on Zulip):

Hmm I am I think too tired to give useful feedback here as well :)

lcnr (May 20 2020 at 07:35, on Zulip):

I managed a slightly more minimal repro which still has a stack overflow:

#![feature(const_generics)]

trait A<const N: usize> {}

struct Const<const N: usize>;

impl<const N: usize> A<N> for Const<{ 6 + 1 }> {}
//                                  ^ ConstKind::Unevaluated with substs [N]

fn foo<const M: usize>()
where
    Const<M>: A<M>,
{
}

fn main() {
    foo();
    // We must satisfy `Const<M>: A<M>` here.
    //
    // This has an impl candidate with `Const<{ 6 + 1 }>: A<N>`.
    // We now unify the `TraitRef`s `Const<M>: A<M>` with `Const<{ 6 + 1 }>: A<N>`.
    //
    // `Const<M> == Const<{ 6 + 1 }>` results in `M == ConstKind::Unevaluated with substs [N]`.
    //
    // `A<M> == A<N>` => `M == N` => `N == ConstKind::Unevaluated with substs [N]`
}
lcnr (Jun 22 2020 at 15:17, on Zulip):

Also relevant here is

// check-pass
#![feature(const_generics)]
#![allow(incomplete_features)]

const LEN: usize = 1024;

struct V<T = [u32; LEN]>(T); // This cause an ICE.

fn main() {
    let _: V; // More accurately this use causes an ICE.
}
lcnr (Jun 22 2020 at 15:18, on Zulip):

With lazy norm, LEN is ConstKind::Unevaluated(..., substs = [T]) which causes an ICE

lcnr (Jun 22 2020 at 15:21, on Zulip):

which is the same reason this has a cycle error

#![feature(const_generics)]

const LEN: usize = 1024;

fn hoge<const T: [u32; LEN]>() {}
oli (Jun 22 2020 at 15:29, on Zulip):

so... lazy normalization isn't actually normalizing when needed?

lcnr (Jun 22 2020 at 15:30, on Zulip):

IMO the problem is generic params should not contain itself as a subst

lcnr (Jun 22 2020 at 15:30, on Zulip):

So I think it is fine for LEN to remain unnormalized

lcnr (Jun 22 2020 at 15:31, on Zulip):

but it shouldn't have access to its parent subst

lcnr (Jun 22 2020 at 15:31, on Zulip):

But I am not completely sure about that and have to look at how this is done for types

lcnr (Jun 22 2020 at 16:38, on Zulip):

Ok, so afaict it's just not possible to have a default type with substs :sweat_smile:

lcnr (Jun 22 2020 at 16:39, on Zulip):

*problematic substs

lcnr (Jun 22 2020 at 17:06, on Zulip):

@varkor @eddyb @nikomatsakis looking at the three above examples, I think the "easiest" solution for this mess is to stop using the parent generics in AnonConsts and instead use some kind of visitor to only include the relevant parameters in the substs.

I am not exactly sure how well this works and there are probably a lot of complications I did not think of yet. Do you think this is feasable/useful?

eddyb (Jun 22 2020 at 17:08, on Zulip):

/me takes a peek and starts screaming

lcnr (Jun 22 2020 at 17:08, on Zulip):

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

lcnr (Jun 22 2020 at 17:08, on Zulip):

let me join

eddyb (Jun 22 2020 at 17:09, on Zulip):

this basically the same thing as the hack we use to ban type parameter defaults from seeing type parameters after them as being in scope

lcnr (Jun 22 2020 at 17:09, on Zulip):

type parameters work during resolution

eddyb (Jun 22 2020 at 17:09, on Zulip):

for const X: [u8; LEN] - the fix is easy, just don't have generics in scope at all. we don't support them

eddyb (Jun 22 2020 at 17:09, on Zulip):

for type parameter defaults, it's worse

eddyb (Jun 22 2020 at 17:10, on Zulip):

basically we allow struct Foo<A, B = A>(...); but not <A = B, B>

lcnr (Jun 22 2020 at 17:10, on Zulip):

jup

eddyb (Jun 22 2020 at 17:10, on Zulip):

but that's done syntactically (well, at name resolution time)

lcnr (Jun 22 2020 at 17:10, on Zulip):

(deleted)

eddyb (Jun 22 2020 at 17:10, on Zulip):

and there is no equivalent in the parent generics system

eddyb (Jun 22 2020 at 17:11, on Zulip):

just ban const expressions in type param defaults from using any generics in scope

eddyb (Jun 22 2020 at 17:11, on Zulip):

I guess?

lcnr (Jun 22 2020 at 17:12, on Zulip):
#![feature(const_generics)]

trait A<const N: usize> {}

struct Const<const N: usize>;

impl<const N: usize> A<N> for Const<{ 6 + 1 }> {}
//                                  ^ ConstKind::Unevaluated with substs [N]

fn foo<const M: usize>()
where
    Const<M>: A<M>,
{
}

fn main() {
    foo();
    // We must satisfy `Const<M>: A<M>` here.
    //
    // This has an impl candidate with `Const<{ 6 + 1 }>: A<N>`.
    // We now equate the `TraitRef`s `Const<M>: A<M>` with `Const<{ 6 + 1 }>: A<N>`.
    //
    // `Const<M> == Const<{ 6 + 1 }>` results in `M == ConstKind::Unevaluated with substs [N]`.
    //
    // `A<M> == A<N>` => `M == N` => `N == ConstKind::Unevaluated with substs [N]`
}
eddyb (Jun 22 2020 at 17:12, on Zulip):

then you can do the same treatment as in types of const params

lcnr (Jun 22 2020 at 17:12, on Zulip):

doesn't fix that though

eddyb (Jun 22 2020 at 17:12, on Zulip):

I think that one is fine

eddyb (Jun 22 2020 at 17:12, on Zulip):

in that it's one of the situations that requires lazy normalization to work

lcnr (Jun 22 2020 at 17:12, on Zulip):

we already have lazy norm

eddyb (Jun 22 2020 at 17:13, on Zulip):

maybe it's not lazy enough :P

eddyb (Jun 22 2020 at 17:13, on Zulip):

both impl headers and where clauses are the problem situations

varkor (Jun 22 2020 at 17:13, on Zulip):

there were aspects skinny121 was going to address after the initial PRs, that they never got to: perhaps that's one of the situations

lcnr (Jun 22 2020 at 17:14, on Zulip):

eddyb said:

maybe it's not lazy enough :P

{ 6 + 1 } now remains ConstKind::Unevaluated

eddyb (Jun 22 2020 at 17:14, on Zulip):

the explanation doesn't entirely track: miri is designed to allow evaluating that with arbitrary substs since N isn't used in the expression

eddyb (Jun 22 2020 at 17:14, on Zulip):

okay maybe it's too lazy

eddyb (Jun 22 2020 at 17:14, on Zulip):

but an on-demand normalization would succeed

eddyb (Jun 22 2020 at 17:14, on Zulip):

no matter the substs

eddyb (Jun 22 2020 at 17:14, on Zulip):

maybe something checks that the substs are concrete? that would be wrong

eddyb (Jun 22 2020 at 17:15, on Zulip):

(again, the system is designed for polymorphic evaluation)

lcnr (Jun 22 2020 at 17:15, on Zulip):

The above example fails because an infer var references itself

eddyb (Jun 22 2020 at 17:15, on Zulip):

this is different from the situation with types inside either const param types or type param defaults, which can cause some unfortunate cycles

eddyb (Jun 22 2020 at 17:15, on Zulip):

ah lol

lcnr (Jun 22 2020 at 17:16, on Zulip):

causing a happy little stack overflow

eddyb (Jun 22 2020 at 17:16, on Zulip):

right, I see. N = ANON_CONST::<N>

eddyb (Jun 22 2020 at 17:16, on Zulip):

where ANON_CONST doesn't use N

eddyb (Jun 22 2020 at 17:17, on Zulip):

that's funny. I think that's a bug in the inference cycle detection? (which I don't even think is working if you're seeing stack overflows)

eddyb (Jun 22 2020 at 17:17, on Zulip):

pretty sure for types you get an error

lcnr (Jun 22 2020 at 17:17, on Zulip):

It is, but the example should still compile...

eddyb (Jun 22 2020 at 17:17, on Zulip):

you want to see this error https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=65e9f16b6945f605239d95b2bbd67140

lcnr (Jun 22 2020 at 17:18, on Zulip):

{ 6 + 1 } just really shouldn't rely on N

eddyb (Jun 22 2020 at 17:18, on Zulip):

only after you can reliably get an error instead of an ICE, you can change the behavior

eddyb (Jun 22 2020 at 17:18, on Zulip):

but the naive semantics should result in an error like that

lcnr (Jun 22 2020 at 17:19, on Zulip):

Then let me first implement the naive semantics :laughing:

lcnr (Jun 22 2020 at 17:19, on Zulip):

I still believe we have to stop using the parent generics though

eddyb (Jun 22 2020 at 17:19, on Zulip):

note that "infinite size" refers to the type being infinite in its definition, not size_of being infinite

eddyb (Jun 22 2020 at 17:19, on Zulip):

@lcnr that would be a tragedy IMO since that's what we've been striving to do for years

lcnr (Jun 22 2020 at 17:20, on Zulip):

~ I write sins not tragedies ~

eddyb (Jun 22 2020 at 17:20, on Zulip):

anyway, somewhat curious how @nikomatsakis feels about breaking an inference cycle of the form $N = ANON_CONST::<$N> by trying to evaluate ANON_CONST and hoping it doesn't depend on $N

lcnr (Jun 22 2020 at 17:22, on Zulip):

I think this stops working once an ANON_CONST depends on some (but not all) of its parents generic variables

lcnr (Jun 22 2020 at 17:22, on Zulip):

So we can't eval it eagerly, because it's still polymorphic

eddyb (Jun 22 2020 at 17:23, on Zulip):

but you can if what it depends on is specified

eddyb (Jun 22 2020 at 17:23, on Zulip):

since you don't evaluate either fully polymorphically or fully concretely

eddyb (Jun 22 2020 at 17:23, on Zulip):

you evaluate for some given substs

eddyb (Jun 22 2020 at 17:24, on Zulip):

e.g. it could be $N = ANON_CONST::<1, 2, $N, 3> instead and the substs that miri would see would be exists X. [1, 2, X, 3] or similar

eddyb (Jun 22 2020 at 17:25, on Zulip):

(via canonicalization)

lcnr (Jun 22 2020 at 17:26, on Zulip):

My concern is $N = ANON_CONST::<1, $M, $N, 3>, where $M is also not yet inferred

eddyb (Jun 22 2020 at 17:27, on Zulip):

but wouldn't that imply that there is a cycle? if M is needed and uninferrable

lcnr (Jun 22 2020 at 17:33, on Zulip):

not sure, I don't fully grasp how $N = ANON_CONST::<..., $N, ...> can be handled so it might be fine

lcnr (Jun 22 2020 at 17:35, on Zulip):

that's funny. I think that's a bug in the inference cycle detection? (which I don't even think is working if you're seeing stack overflows)

I can go ahead and fix this first and then try to eagerly eval ANON_CONST::<N> and see if this fixes everything

lcnr (Jun 23 2020 at 21:24, on Zulip):

BORN FROM THE ASHES

https://github.com/rust-lang/rust/pull/72351

lcnr (Jun 23 2020 at 21:25, on Zulip):

I already had a fix for the inference cycle which I closed because I wasn't sure if this is the correct solution :sweat_smile:

lcnr (Jun 23 2020 at 21:25, on Zulip):

not sure if you want to get pinged here @eddyb

Last update: Sep 27 2020 at 12:30UTC