Stream: t-compiler/const-eval

Topic: lazy norm and cycles


nikomatsakis (Feb 25 2019 at 18:49, on Zulip):

Hey @oli, @eddyb -- I'm trying to dig more into the lazy normalization situation. I've asked before but I'm looking for a simple example of the sort of thing that causes a problem today (I'm trying to prep a plan as part of Traits WG, and having concrete example to work from would be great). Skimming github issue threads etc I didn't find what I was looking for.

I do have this example (playground):

struct Foo<T> {
    bytes: [u8; std::mem::size_of::<T>()],
    data: T,
}

fn main() {}

but right now it errors out because it can't prove T: Sized. I have some vague memory that maybe we don't use the true parameter environment (because of cycles, perhaps?) and hence this is why we have this problem?

nikomatsakis (Feb 26 2019 at 18:32, on Zulip):

cc @varkor :point_up: are you familiar with this question as well?

oli (Feb 26 2019 at 18:37, on Zulip):

So... the array length constant is essentially a new (but anonymous) item. Unlike associated constants they do not look into their parents for generics. I wonder if it would be enough to just treat them like impl trait (anonymous existential types) and give them access to their parent's scope. I mean this would be easy to feature gate, so we can experiment. I don't see anything immediately problematic.

nikomatsakis (Feb 26 2019 at 18:37, on Zulip):

Hmm.

oli (Feb 26 2019 at 18:38, on Zulip):

Cycles already exist if we try to use anything interesting from Foo during the computation of the array length:

struct Foo<T> {
    bytes: [u8; std::mem::size_of::<Foo<u32>>()],
    data: T,
}
nikomatsakis (Feb 26 2019 at 18:38, on Zulip):

That's a different cycle

nikomatsakis (Feb 26 2019 at 18:38, on Zulip):

That is, it seems like a kind of "legit" cycle

oli (Feb 26 2019 at 18:38, on Zulip):

it is, but I don't see how going directly through T could be worse

nikomatsakis (Feb 26 2019 at 18:38, on Zulip):

Oh, I would expect the code above to work

oli (Feb 26 2019 at 18:39, on Zulip):

so would I. I understood your question as "is there code that would fail even though we'd think it was sane"

nikomatsakis (Feb 26 2019 at 18:39, on Zulip):

but I'm trying to get at the problem that @eddyb is talking about where const generics are blocked on lazy norm. I think a better example is :

fn foo<T>()
where T: Foo<[u8; 22]>
{ .. }

where here the problem would be that to "normalize" the 22 expression (compute its value), we would need to know the predicates from the surrounding fn, but of course to get those we have to normalize.

We solve this for associated types with a rather special purpose evaluation.

nikomatsakis (Feb 26 2019 at 18:40, on Zulip):

I've asked them for examples before and I can't seem to find those messages in my chat history

oli (Feb 26 2019 at 18:41, on Zulip):

normalizing the 22 would probably not immediately cause cycles. Only if the value actually tried to use T in an interesting manner

oli (Feb 26 2019 at 18:42, on Zulip):

we're probably going to have some degenerate cases, but these are errors where we want to allow something and not the inverse

nikomatsakis (Feb 26 2019 at 18:42, on Zulip):

I don't think that's true

nikomatsakis (Feb 26 2019 at 18:42, on Zulip):

That is, I think that -- if we use a naive impl -- any normalization would trigger a cycle

oli (Feb 26 2019 at 18:43, on Zulip):

because of the ParamEnv computation?

nikomatsakis (Feb 26 2019 at 18:43, on Zulip):

( just because we are invoking predicates_of )

nikomatsakis (Feb 26 2019 at 18:43, on Zulip):

let me go review how the code is setup here I guess

nikomatsakis (Feb 26 2019 at 18:44, on Zulip):

I'm kind of just guessing

oli (Feb 26 2019 at 18:44, on Zulip):

not any of the const eval code (I just checked to be sure)

oli (Feb 26 2019 at 18:44, on Zulip):

so it could be the normalization around it

nikomatsakis (Feb 26 2019 at 18:46, on Zulip):

so there's this kind of complex logic around normalizing constants

oli (Feb 26 2019 at 18:47, on Zulip):

jup, looking through that right now. We do have the call to Instance::resolve that might be problematic

nikomatsakis (Feb 26 2019 at 18:47, on Zulip):

I'm trying to reconstruct in my mind the reasoning behind this :)

oli (Feb 26 2019 at 18:52, on Zulip):

I wish we had a callgraph of rustc XD the rabbit hole is pretty deep

nikomatsakis (Feb 26 2019 at 18:54, on Zulip):

it feels to me like the logic in Instance::resolve and the logic in project.rs is duplicated, and that's part of the problem

nikomatsakis (Feb 26 2019 at 18:54, on Zulip):

i.e., I'd expect normalizing constants to work more like associated types

nikomatsakis (Feb 26 2019 at 18:54, on Zulip):

but I'm trying to remember why .. I should actually check the PR where this was added, I have a memory of chatting a bit with @eddyb about it

varkor (Feb 26 2019 at 20:04, on Zulip):

I know @eddyb gave me an example of where this is would be an issue with const generics, but I can't remember off the top of my head

centril (Feb 26 2019 at 22:17, on Zulip):

Oh, I would expect the code above to work

@nikomatsakis just to be clear, by "above", you are referring to [u8; std::mem::size_of::<T>()] or also [u8; std::mem::size_of::<Foo<u32>>()]?

The latter requires knowing the layout of struct Foo_u32 { bytes: [u8; size_of::<Foo_u32>()], data: u32 } which should produce a cycle...?

centril (Feb 26 2019 at 22:18, on Zulip):

So... the array length constant is essentially a new (but anonymous) item. Unlike associated constants they do not look into their parents for generics. I wonder if it would be enough to just treat them like impl trait (anonymous existential types) and give them access to their parent's scope. I mean this would be easy to feature gate, so we can experiment. I don't see anything immediately problematic.

@oli A more principled treatment of this might be to introduce ScopedTypeVariables at large; would be useful in general; but I'm not opposed to experimentation with a subset :slight_smile:

Last update: Nov 15 2019 at 21:15UTC