Stream: t-compiler

Topic: dropck optimization


simulacrum (Sep 18 2019 at 00:17, on Zulip):

Not sure who all to bug about this -- maybe @pnkfelix would know -- but it seems to me like for the most part, dropck should be able to not care about substituting concrete types in for generics. Currently, we do, which leads to problems like in https://github.com/rust-lang/rust/issues/4287

simulacrum (Sep 18 2019 at 00:18, on Zulip):

AFAICT though

enum Perfect<T> {
    Tip(T),
    Fork(Box<Perfect<(T, T)>>),
}

should either pass dropck or not independent of what T is, right?

simulacrum (Sep 18 2019 at 00:21, on Zulip):

In particular, the documentation in the nomicon talks about how if T here was &'a i32 or so that could lead to problems, but since Drop impls must be equivalent to the struct definition, that seems like it shouldn't be a problem, right? i.e., either all T's are fine or none are, since dropck is overly conservative and "assumes" it has a 'a in the T or so

pnkfelix (Sep 18 2019 at 05:27, on Zulip):

I thought The problem in 4287 was due to the enum definition itself (namely the non-uniform type-recursion)

pnkfelix (Sep 18 2019 at 06:35, on Zulip):

I’ll have to review the thread.

pnkfelix (Sep 18 2019 at 06:36, on Zulip):

But I could imagine an issue arising with the dropck implementation due to the cyclic structure causing the compiler to loop

gnzlbg (Sep 18 2019 at 07:51, on Zulip):

The dropck is very imprecise, I don't think it can reason about this

gnzlbg (Sep 18 2019 at 07:51, on Zulip):

The issue in the nomicon is when you have a &'a i32 and the compiler does not know if the type it points to outlives the reference.

gnzlbg (Sep 18 2019 at 07:52, on Zulip):

which means it must outlive Drop::drop

gnzlbg (Sep 18 2019 at 07:56, on Zulip):

AFAIK we just bail here and require an unsafe Drop impl

pnkfelix (Sep 18 2019 at 08:58, on Zulip):

I'm still trying to understand the original issue being raised. Is the question about why dropck is only failing at the point where one has a use (i.e. instantiation) of Perfect ?

gnzlbg (Sep 18 2019 at 09:13, on Zulip):

That's how I understood the question

gnzlbg (Sep 18 2019 at 09:14, on Zulip):

A drop impl for perfect isn't bad per se, but depending on how it is used, the issue raised by the nomicon can appear - but that issue is essentially how the borrowck handles drop

pnkfelix (Sep 18 2019 at 09:28, on Zulip):

hmm. I am under the impression that dropck would fail in any fn body that attempts to instantiate Perfect with concrete types, regardless of what they are. But that is not what is implied by @simulacrum 's question as I read it.

pnkfelix (Sep 18 2019 at 09:28, on Zulip):

but yes, currently the dropck works by analyzing concrete expressions, not abstract type definitions, and so by its nature you won't get these errors from the enum definition alone.

simulacrum (Sep 18 2019 at 10:13, on Zulip):

My question is basically can dropck work, in theory, on type definitions, not concrete instantiations?

pnkfelix (Sep 18 2019 at 10:17, on Zulip):

the problem in this case, in theory, should be detected on the type definition

simulacrum (Sep 18 2019 at 10:17, on Zulip):

In particular, I would expect us to be able to not check Perfect recursively; my assertion is that dropck should pass for any T in Perfect, i.e. that for all types T, U, dropck(Perfect<T>) = dropck(Perfect<U>). I'm not sure if this is true today, to be clear, I'm just saying that it seems like a correct impl of dropck could satisfy this property

pnkfelix (Sep 18 2019 at 10:18, on Zulip):

because its fundamentally a type definition that is going to cause subsequent analyses to infinite loop

pnkfelix (Sep 18 2019 at 10:18, on Zulip):

but the assertion I am making there is not about dropck; it is about the nature of polymorphic recursion

simulacrum (Sep 18 2019 at 10:18, on Zulip):

I personally wouldn't expect a dropck error on this type

simulacrum (Sep 18 2019 at 10:19, on Zulip):

If my understanding of how dropck could work is correct

pnkfelix (Sep 18 2019 at 10:19, on Zulip):

I want to be clear here: dropck is not rejecting this code, AFAIK. It is causing the compiler to infinite loop

pnkfelix (Sep 18 2019 at 10:19, on Zulip):

and because our attempt to detect cycles on the fly within dropck is not smart enough to catch cases like this

simulacrum (Sep 18 2019 at 10:20, on Zulip):

Right, well, loop really slowly - it will terminate due to the type depth limit

pnkfelix (Sep 18 2019 at 10:20, on Zulip):

okay, sure.

pnkfelix (Sep 18 2019 at 10:20, on Zulip):

I don't consider that to be "dropck is rejecting this code"

pnkfelix (Sep 18 2019 at 10:20, on Zulip):

I consider that to be "the type definition is causing the compiler to have fits"

pnkfelix (Sep 18 2019 at 10:20, on Zulip):

I suppose it is a somewhat subtle/subjective judgement

simulacrum (Sep 18 2019 at 10:21, on Zulip):

Okay, sure. But am I correct that dropck could work without any problems here, and in all cases, solely by analyzing the definition of Perfect?

pnkfelix (Sep 18 2019 at 10:22, on Zulip):

anyway, dropck, or at least part of it, is about analyzing how a concrete variable (of a given type) is used in a body of code. So no, you cannot do all of dropck solely by analyzing the type definition

pnkfelix (Sep 18 2019 at 10:24, on Zulip):

@simulacrum you keep mentioning this desired property that all types T, U, dropck(Perfect<T>) = dropck(Perfect<U>). But this confuses me, because, as far as I can tell, dropck is behaving the same here regardless of how you instantiate Perfect: it is infinite looping for any choice of T/U, (or rather hitting type depth limit), right?

simulacrum (Sep 18 2019 at 10:25, on Zulip):

Kind of - I mention that because if it's true, then I would expect us to be able to avoid the looping by keeping the output of dropck generic

pnkfelix (Sep 18 2019 at 10:25, on Zulip):

My personal claim is that we could, and should, add an extra analysis (that would run long before dropck) of type definitions like that of Perfect that would reject them as exhibiting non-uniform recursion (aka polymorphic recursion)

pnkfelix (Sep 18 2019 at 10:26, on Zulip):

which is what #4287 is about, or at least is my interpretation of it

simulacrum (Sep 18 2019 at 10:26, on Zulip):

Why should we reject such types? Is it just "we're not ready to handle them yet"?

simulacrum (Sep 18 2019 at 10:27, on Zulip):

I guess I was coming at this from the perspective that a good fix is to make this code compile, not fail with a nice error message

pnkfelix (Sep 18 2019 at 10:27, on Zulip):

well if any use of the type implies you need an infinite set of instantiations

pnkfelix (Sep 18 2019 at 10:27, on Zulip):

then you have a problem

pnkfelix (Sep 18 2019 at 10:28, on Zulip):

Languages that handle polymorphic recursion do it, as far as I know, by building method dictionaries at runtime

pnkfelix (Sep 18 2019 at 10:28, on Zulip):

but we use static monomorphization

pnkfelix (Sep 18 2019 at 10:28, on Zulip):

so you need to build all your vtables at compile time

pnkfelix (Sep 18 2019 at 10:28, on Zulip):

see e.g. https://github.com/rust-lang/rust/issues/4287#issuecomment-218304293

pnkfelix (Sep 18 2019 at 10:29, on Zulip):

of course some people do point out that one might be able to handle some instances

simulacrum (Sep 18 2019 at 10:29, on Zulip):

Hm, okay, I think I understand now. So the action item here is to implement another type ck pass which will reject Perfect by indicating polymorphic recursion?

pnkfelix (Sep 18 2019 at 10:29, on Zulip):

Yes, that is what I believe the action item to be

simulacrum (Sep 18 2019 at 10:30, on Zulip):

Okay, makes sense.

simulacrum (Sep 18 2019 at 10:31, on Zulip):

I will take a look at an implementation then

pnkfelix (Sep 18 2019 at 10:31, on Zulip):

this is not a trivial analysis, though

pnkfelix (Sep 18 2019 at 10:32, on Zulip):

mainly because of cases where it arises due to mutual recursion between a set of distinct struct/enum definitions

simulacrum (Sep 18 2019 at 10:33, on Zulip):

I don't think it's trivial, but I'm thinking that some sort of approach that avoids directly instantiating a T would work - basically, keeping track of loops at the non-subst applied type

pnkfelix (Sep 18 2019 at 10:34, on Zulip):

yes, we would definitely want a solution that works without needing to instantiate a T, I think.

simulacrum (Sep 18 2019 at 10:35, on Zulip):

It seems like even a non-perfect pass would already be an improvement, too

pnkfelix (Sep 18 2019 at 10:35, on Zulip):

sure

simulacrum (Sep 18 2019 at 10:37, on Zulip):

In theory I think once we have it the depth limits elsewhere could for the most part be raised/removed, too, right?

pnkfelix (Sep 18 2019 at 10:37, on Zulip):

maybe

pnkfelix (Sep 18 2019 at 10:37, on Zulip):

or

pnkfelix (Sep 18 2019 at 10:37, on Zulip):

yes

pnkfelix (Sep 18 2019 at 10:37, on Zulip):

probably

pnkfelix (Sep 18 2019 at 10:37, on Zulip):

i don't know

pnkfelix (Sep 18 2019 at 10:37, on Zulip):

:smile:

simulacrum (Sep 18 2019 at 10:38, on Zulip):

I guess they could still catch other cases - bugs in compiler, or so

simulacrum (Sep 18 2019 at 10:39, on Zulip):

Anyway, I need to run, thanks for clarifying things for me

gnzlbg (Sep 18 2019 at 10:42, on Zulip):

dropck(Perfect<T>) returns "maybe" at best

gnzlbg (Sep 18 2019 at 10:43, on Zulip):

Depending on how the type is used, it might need an unsafe Drop impl

gnzlbg (Sep 18 2019 at 10:44, on Zulip):

We can't know that from looking at Perfect<T>, because whether that's the case depends on T

gnzlbg (Sep 18 2019 at 10:46, on Zulip):

So what dropck a looks at are expressions using Perfect<T>

simulacrum (Sep 18 2019 at 10:50, on Zulip):

@gnzlbg my impression is that dropck for Perfect<T> at best would return "perfect is good, also, check Box<Perfect<(T, T)>>

simulacrum (Sep 18 2019 at 10:51, on Zulip):

And T I guess

gnzlbg (Sep 18 2019 at 10:51, on Zulip):

What would dropck check for a type ?

simulacrum (Sep 18 2019 at 10:52, on Zulip):

Hm, well, it could conclude for a type with Phantom Data that it's just fine

simulacrum (Sep 18 2019 at 10:52, on Zulip):

If I recall that bit correctly

gnzlbg (Sep 18 2019 at 10:53, on Zulip):

PhantomData<T> just says, this type should look like it owns a T

gnzlbg (Sep 18 2019 at 10:54, on Zulip):

but whether it matters will depend on whether the type actually has a Drop impl or not

gnzlbg (Sep 18 2019 at 10:55, on Zulip):

and also about how the type is actually used

gnzlbg (Sep 18 2019 at 10:55, on Zulip):

the dropck will say for some function, that that function uses the type correctly

gnzlbg (Sep 18 2019 at 10:56, on Zulip):

but for a different one, that it uses it incorrectly

simulacrum (Sep 18 2019 at 10:57, on Zulip):

Sure - there's two parts to dropck though afaict, the generic piece and the concrete piece

simulacrum (Sep 18 2019 at 10:57, on Zulip):

Oh, yeah, I remembered why we treated phantom specially, it's because it doesn't have fields

gnzlbg (Sep 18 2019 at 10:58, on Zulip):

Not only, the phantomdata also says that this type has data of type T

gnzlbg (Sep 18 2019 at 10:58, on Zulip):

and that information is used when evaluating whether a Drop impl is correct or not

gnzlbg (Sep 18 2019 at 10:59, on Zulip):

See here (https://doc.rust-lang.org/nomicon/dropck.html):

For a generic type to soundly implement drop, its generics arguments must strictly outlive it.

gnzlbg (Sep 18 2019 at 11:00, on Zulip):

If you are taking references, that's always the case if the reference is 'static, but if you have a <'a>, then you can't know just by looking at the type

gnzlbg (Sep 18 2019 at 11:00, on Zulip):

Each time the type is used, a different lifetime is passed, and depending on what the code does, the value passed might or might not outlive the type

gnzlbg (Sep 18 2019 at 11:03, on Zulip):

(it also depends on #[may_dangle], etc.)

gnzlbg (Sep 18 2019 at 11:07, on Zulip):

https://github.com/rust-lang/rust/blob/8bf776d5c2fc88624d2562e493aab0d324a3b7d8/src/librustc_typeck/check/dropck.rs#L236

gnzlbg (Sep 18 2019 at 11:08, on Zulip):

The dropck is like the borrowck, it works on expressions

simulacrum (Sep 18 2019 at 11:24, on Zulip):

Right, but it seems like "generic arguments must strictly outlive" can be checked without recursing into the type, whereas the current implementation does recurse

pnkfelix (Sep 18 2019 at 11:40, on Zulip):

Okay so its possible that part of my (our?) confusion in this conversation is arising because there are multiple things that one might say are computed as part of so-called "dropck"

pnkfelix (Sep 18 2019 at 11:41, on Zulip):

There is are two main things I can think of, off the top of my head

pnkfelix (Sep 18 2019 at 11:41, on Zulip):

1. the checking that a destructor doesn't run at a time where there may be a dangling pointer. This is fundamentally connecting to analyzing expressions

pnkfelix (Sep 18 2019 at 11:42, on Zulip):

(and may be why @gnzlbg and I are both confused by the idea of doing dropck on the type declaration alone)

pnkfelix (Sep 18 2019 at 11:43, on Zulip):

2. the implied outlives bounds (and maybe also "strictly outlives" stuff discussed in the dropck RFC) that arise on the type parameters of a type due to that type, or some type reachable via its fields, implementing Drop

simulacrum (Sep 18 2019 at 11:45, on Zulip):

Yes, I think the code I was talking about mostly looks at (2) -- in some sense, (1) is less interesting, as I would imagine it is sort of "part" of borrowck, in that it does very similar work

pnkfelix (Sep 18 2019 at 11:45, on Zulip):

that second thing sounds more like what @simulacrum is saying they would expect to be derived from an analysis of the type definition alone.

simulacrum (Sep 18 2019 at 11:47, on Zulip):

I guess I'm also saying that the first should be able to re-use information from the second, too

simulacrum (Sep 18 2019 at 11:47, on Zulip):

i.e., we should not need to recursively visit fields when dropck-ing an expression, rather just query "what types are needed to outlive for this to drop"

varkor (Sep 18 2019 at 11:47, on Zulip):

just catching up on the discussion: there seem like there are two issues here
- type definitions that require an infinite list of instantiations (e.g. T1<T2<T1<...) through polymorphic recursion
- dropck not handling polymorphic recursion (even the finite kind) properly

varkor (Sep 18 2019 at 11:48, on Zulip):

Perfect, for instance, doesn't seem to require an infinite list of instantiations, and looks fine in theory

varkor (Sep 18 2019 at 11:48, on Zulip):

so it seems like an implementation flaw more than a design flaw

gnzlbg (Sep 18 2019 at 11:48, on Zulip):

FWIW, this type struct<'a>(*mut &'a T) contains a type parameter, but no reference

gnzlbg (Sep 18 2019 at 11:49, on Zulip):

So one really needs to check whether any field actually stores a reference AFAICT (that does not mean that one needs to recurse forever to determine that for Perfect though)

simulacrum (Sep 18 2019 at 11:49, on Zulip):

Yes, but the (2) pass could tell us that said type does not depend on T

simulacrum (Sep 18 2019 at 11:49, on Zulip):

i.e. does not need to outlive T

varkor (Sep 18 2019 at 11:49, on Zulip):

why is dropck something that's not part of the type system?

varkor (Sep 18 2019 at 11:49, on Zulip):

it seems we could have more details lifetimes

varkor (Sep 18 2019 at 11:49, on Zulip):

e.g. 'a.'b for fine-grained ordering

pnkfelix (Sep 18 2019 at 11:50, on Zulip):

@varkor I'm not sure we can compile Perfect today, even if we side-stepped dropck.

gnzlbg (Sep 18 2019 at 11:50, on Zulip):

one part should be part of borrowck, and the other of typeck

varkor (Sep 18 2019 at 11:50, on Zulip):

which would then allow us to do the dropck analysis on the types rather than the expressions

varkor (Sep 18 2019 at 11:51, on Zulip):

@gnzlbg: integrating with both typeck and borrowck

simulacrum (Sep 18 2019 at 11:51, on Zulip):

Perfect, for instance, doesn't seem to require an infinite list of instantiations, and looks fine in theory

I was convinced this is not true by @pnkfelix's argument that we'd need to codegen methods for Perfect<(i32, i32)> and Perfect<((i32, i32), (i32, i32))> etc

pnkfelix (Sep 18 2019 at 11:51, on Zulip):

since, i think, compiling { let a: Perfect<u32>; ... } would requiring emitting glue code to drop Box<Perfect<(u32, u32)>> ... and Box<Perfect<((u32, u32), (u32, u32))>>. etc

pnkfelix (Sep 18 2019 at 11:51, on Zulip):

this is why I brought up the need to create vtables at runtime.

varkor (Sep 18 2019 at 11:51, on Zulip):

ah, I see

pnkfelix (Sep 18 2019 at 11:52, on Zulip):

Languages that handle method-dispatch by passing along a dictionary can do this

gnzlbg (Sep 18 2019 at 11:52, on Zulip):

but doing that still does not require dropck to infinitely recurse right ?

gnzlbg (Sep 18 2019 at 11:52, on Zulip):

as in, maybe codegen fails later due to this

gnzlbg (Sep 18 2019 at 11:52, on Zulip):

but neither of dropck passes should fail

pnkfelix (Sep 18 2019 at 11:52, on Zulip):

(and I could imagine a new Rust calling ABI that would pass along a dictionary, and then dynamically create new ones when necessary)

simulacrum (Sep 18 2019 at 11:52, on Zulip):

Yes, I think we agree that dropck should maybe not fail on this type (it seems to satisfy dropck requirements), but we should provide a good error regardless

pnkfelix (Sep 18 2019 at 11:53, on Zulip):

@gnzlbg yes, I agree that the fact that dropck is infinitely recursing is a bug somewhere

gnzlbg (Sep 18 2019 at 11:53, on Zulip):

maybe its worth it to consider these as separate bugs and fill them separately

pnkfelix (Sep 18 2019 at 11:53, on Zulip):

but my claim is that my ideal approach would be to detect the polymorphic recursion (at the point where the type is declared)

pnkfelix (Sep 18 2019 at 11:53, on Zulip):

and error on it

gnzlbg (Sep 18 2019 at 11:53, on Zulip):

the issue discussing Perfect is quite long

pnkfelix (Sep 18 2019 at 11:53, on Zulip):

rather than attempting to generalize dropck to handle cases that should not arise in the first place.

gnzlbg (Sep 18 2019 at 11:53, on Zulip):

ah, dunno

simulacrum (Sep 18 2019 at 11:54, on Zulip):

Yes, I agree -- it seems like there's just the one bug here, we don't have a polymorphic recursion detector

gnzlbg (Sep 18 2019 at 11:54, on Zulip):

that's kind of a lang team thing

gnzlbg (Sep 18 2019 at 11:54, on Zulip):

is there no case of polymorphic recursion that we support ?

simulacrum (Sep 18 2019 at 11:54, on Zulip):

I think it's just a matter of diagnostics?

simulacrum (Sep 18 2019 at 11:54, on Zulip):

To my knowledge you can't polymorphically recurse today without leading to dropck problems

varkor (Sep 18 2019 at 11:54, on Zulip):

I think the lack of polymorphic recursion is a compiler limitation, and choosing to forbid it is a lang decision

simulacrum (Sep 18 2019 at 11:55, on Zulip):

But we already forbid it today? Like, it would be a lang team decision to do the work to enable it, but we're talking about providing a better lint

varkor (Sep 18 2019 at 11:55, on Zulip):

from a user's perspective, if there aren't special drop rules for Perfect, it doesn't really make sense that you can't define it

varkor (Sep 18 2019 at 11:55, on Zulip):

we don't forbid it – it just doesn't work

gnzlbg (Sep 18 2019 at 11:55, on Zulip):

e.g. Perfect<T: Foo> { one(T), Second(Perfect<(T::Other, T::Other)>) }

pnkfelix (Sep 18 2019 at 11:55, on Zulip):

@simulacrum the problem is that we don't today forbid the type declaration

pnkfelix (Sep 18 2019 at 11:55, on Zulip):

we just fail to handle uses of it

simulacrum (Sep 18 2019 at 11:55, on Zulip):

Right, we could structure the lint to only error on invalid uses, in theory

gnzlbg (Sep 18 2019 at 11:55, on Zulip):

where at some point you get a tuple that implements Foo and Foo::Other = ! (and you keep recursing creating tuples of ! after that point, but that doesn't do anything)

simulacrum (Sep 18 2019 at 11:56, on Zulip):

@gnzlbg that seems like a harder case, but yes, in theory, although I'm not entirely sure we'd handle ((!, !), (!, !))... etc well either

gnzlbg (Sep 18 2019 at 11:57, on Zulip):

maybe just `Perfect<T: Foo> { one(T), Second(T::Other) } where T::Other could be Perfect<..> and at some point some T::Other is just () stopping recursion

simulacrum (Sep 18 2019 at 11:57, on Zulip):

Sure, yeah. Given something like that we do need to check concrete instantiations

gnzlbg (Sep 18 2019 at 11:57, on Zulip):

that recursion is not infinite though

simulacrum (Sep 18 2019 at 11:58, on Zulip):

But it does seem like we can detect the Perfect case as-is and error out rather than stalling

pnkfelix (Sep 18 2019 at 11:58, on Zulip):

@gnzlbg wait, what was your example meant to show?

varkor (Sep 18 2019 at 11:58, on Zulip):

(deleted)

pnkfelix (Sep 18 2019 at 11:58, on Zulip):

that its hard to detect the error in all cases? (without breaking valid code, that is)

pnkfelix (Sep 18 2019 at 11:58, on Zulip):

e.g. this compiles.

pnkfelix (Sep 18 2019 at 11:58, on Zulip):

and thus you wouldn't want to reject it.

gnzlbg (Sep 18 2019 at 11:59, on Zulip):

so how is that different than the original example ?

pnkfelix (Sep 18 2019 at 11:59, on Zulip):

(note that this is not an re-encoding of the Perfect example we are discussing. in particular it changes associated type for the tuple to u32, thus avoiding infinite regress)

simulacrum (Sep 18 2019 at 11:59, on Zulip):

Sure, yes. Though I would argue that we should be able to detect that there's a difference between this and the original Perfect

gnzlbg (Sep 18 2019 at 12:00, on Zulip):

ah yes

pnkfelix (Sep 18 2019 at 12:01, on Zulip):

(I should have alpha-renamed Perfect before sharing it)

pnkfelix (Sep 18 2019 at 12:02, on Zulip):

(I suspect that higher-kinded types, and how they are currently expressed via associated items, are going to be the big hurdle to overcome in an attempt to detect polymorphic recursion solely via analysis of the type declarations.)

varkor (Sep 18 2019 at 12:03, on Zulip):

seems like, in theory, if we could express T: !Drop, then the recursion wouldn't be an issue?

simulacrum (Sep 18 2019 at 12:03, on Zulip):

I think our belief is that _even if_ dropck didn't error here, that wouldn't matter

simulacrum (Sep 18 2019 at 12:03, on Zulip):

we would error somewhere else

varkor (Sep 18 2019 at 12:03, on Zulip):

I mean in terms of generating infinite impls during monomorphisation

simulacrum (Sep 18 2019 at 12:04, on Zulip):

Well, even if T is not Drop, Box<T> is, so you need to codegen infinite impls for Box, right?

pnkfelix (Sep 18 2019 at 12:04, on Zulip):

Sure, yes. Though I would argue that we should be able to detect that there's a difference between this and the original Perfect

Yes, I do believe we should be able to catch infinitely-regressing polymorphic recursion as exemplified in the original Perfect<T> { Tip(T), Fork(Box<Perfect<(T, T)>>) } via some semi-straight-forward analysis.

varkor (Sep 18 2019 at 12:04, on Zulip):

Well, even if T is not Drop, Box<T> is, so you need to codegen infinite impls for Box, right?

I suppose anywhere we call a method on the generic parameter, it's going to start recursing...

simulacrum (Sep 18 2019 at 12:05, on Zulip):

yeah, I think it is safe to forbid types of the pattern Perfect<T> { Tip(T), Fork(Box<Perfect<(T, T)>>) } -- yes, there are similar-looking but not actually wrong patterns, but if we can avoid those then that's good

pnkfelix (Sep 18 2019 at 12:07, on Zulip):

I actually think @varkor has the right intuition

pnkfelix (Sep 18 2019 at 12:07, on Zulip):

in that, if you can get rid of the drop-glue

pnkfelix (Sep 18 2019 at 12:07, on Zulip):

then the problem does go away

simulacrum (Sep 18 2019 at 12:09, on Zulip):

_for dropck_ yes, but not for arbitrary (recursive?) methods, right?

pnkfelix (Sep 18 2019 at 12:10, on Zulip):

heh

simulacrum (Sep 18 2019 at 12:10, on Zulip):

Though one could imagine that would be orthogonal, and for drop-glue of Box for example we have the #[may_dangle] on T so in theory there's just one impl (though that could be a lie, due to being compiler-implemented

varkor (Sep 18 2019 at 12:11, on Zulip):
enum Perfect<T> { Tip(T), Fork(Box<Perfect<(T, T)>>) }

impl<T> Perfect<T> {
    fn foo(&self) {
        if true {
            self.foo(); // impl<(T, T)>
        }
    }
}

fn bar {
    let p = Perfect::Tip(0u32);
    foo(p); // impl<u32>
}
varkor (Sep 18 2019 at 12:11, on Zulip):

something like this presents the problem even without dropck, I think

pnkfelix (Sep 18 2019 at 12:12, on Zulip):

ah

pnkfelix (Sep 18 2019 at 12:12, on Zulip):

I was trying to make an examle

pnkfelix (Sep 18 2019 at 12:12, on Zulip):

but I was putting #[derive(Debug)] on enum Perfect

pnkfelix (Sep 18 2019 at 12:12, on Zulip):

and that was a no-no

pnkfelix (Sep 18 2019 at 12:12, on Zulip):

or ..

pnkfelix (Sep 18 2019 at 12:12, on Zulip):

well never mind, let me wait until I actually get this example to work

pnkfelix (Sep 18 2019 at 12:16, on Zulip):

okay this seems weird to me: badness

pnkfelix (Sep 18 2019 at 12:17, on Zulip):

sorry, add a call to the but_this_doesnt from main to see the "error", if it can be called that (is it a timeout?)

pnkfelix (Sep 18 2019 at 12:17, on Zulip):

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=d6026a8d14d2741dc9fb8b18c2bec3f5

simulacrum (Sep 18 2019 at 12:18, on Zulip):

hm, yeah, it compiles locally

simulacrum (Sep 18 2019 at 12:19, on Zulip):

so I suspect memory limit I think

simulacrum (Sep 18 2019 at 12:19, on Zulip):

timeout usually gives a different error

pnkfelix (Sep 18 2019 at 12:19, on Zulip):

yikes

simulacrum (Sep 18 2019 at 12:19, on Zulip):

(we give like 100MB or so on play, so that's not too surprising)

simulacrum (Sep 18 2019 at 12:20, on Zulip):

113 MB at max used based on local testing

simulacrum (Sep 18 2019 at 12:20, on Zulip):

so just over

pnkfelix (Sep 18 2019 at 12:20, on Zulip):

this is what I wanted to demo, in that it shows a value being constructed

pnkfelix (Sep 18 2019 at 12:20, on Zulip):

and then calling a method on it

pnkfelix (Sep 18 2019 at 12:20, on Zulip):

ah, release mode compiles in playpen

simulacrum (Sep 18 2019 at 12:21, on Zulip):

that case compiles locally for me as well, yes, though it's worth noting that we would not consider this a problem from e.g. dropck due to the indirection

pnkfelix (Sep 18 2019 at 12:22, on Zulip):

and okay, you get problems if you try to call the generate fmt::Debug routine for the Fork variant's payload

simulacrum (Sep 18 2019 at 12:22, on Zulip):

Right, you can't instantiate anything that treats this generically I'd guess and calls "itself"

pnkfelix (Sep 18 2019 at 12:23, on Zulip):

(demo of fmt::Debug infinite regress). Yes I agree with that

pnkfelix (Sep 18 2019 at 12:23, on Zulip):

though it's worth noting that we would not consider this a problem from e.g. dropck due to the indirection

right; this is what I was trying to work my way towards when I said that I thought @varkor had the right intuition about the problems here not arising if you're dealing with types that are !Drop

pnkfelix (Sep 18 2019 at 12:24, on Zulip):

so that's an example where you can have polymorphic recursion today

pnkfelix (Sep 18 2019 at 12:24, on Zulip):

a lot of the standard stuff (like derive(Debug)) won't play well with it

pnkfelix (Sep 18 2019 at 12:25, on Zulip):

but that's not the same as "not supported in the language."

simulacrum (Sep 18 2019 at 12:25, on Zulip):

hm, sure, but you need to be sort of "very careful" and in fact, not actually have it

simulacrum (Sep 18 2019 at 12:25, on Zulip):

i.e. if you attempt to use the fact you have it then it breaks :)

pnkfelix (Sep 18 2019 at 12:25, on Zulip):

why do you say "not actually have it" ?

simulacrum (Sep 18 2019 at 12:25, on Zulip):

i.e. if you attempt to use the fact you have it then it breaks :)

does that clarify?

pnkfelix (Sep 18 2019 at 12:25, on Zulip):

not sure yet

pnkfelix (Sep 18 2019 at 12:26, on Zulip):

my intuition is that the breakage I demoed there is more an artifact of how derive works

pnkfelix (Sep 18 2019 at 12:26, on Zulip):

let me try a manual impl to double check my own intuition

simulacrum (Sep 18 2019 at 12:27, on Zulip):

well, I think it's because we're calling Debug::fmt on Perfect<'a, X>, which means we need to codegen impl for &'a Perfect<(X, X)>

simulacrum (Sep 18 2019 at 12:27, on Zulip):

and so on

pnkfelix (Sep 18 2019 at 12:27, on Zulip):

right, but that's just because of the derive code

pnkfelix (Sep 18 2019 at 12:27, on Zulip):

in theory, you don't have to use a statically generated series of calls to do the debug formatting

simulacrum (Sep 18 2019 at 12:27, on Zulip):

I don't see how you could implement it differently? Like, there's no way to observe polymorphic recursion otherwise, right?

simulacrum (Sep 18 2019 at 12:28, on Zulip):

unless you mean like passing in *mut () that magically knows how to deal with it by at runtime generating the impl.. but that seems ~impossible to get right without compiler knowledge

simulacrum (Sep 18 2019 at 12:29, on Zulip):

sort of a #[may_dangle] for arbitrary impls, I guess, in some sense

pnkfelix (Sep 18 2019 at 12:29, on Zulip):

I guess I'm envisaging someone implementing their own dictionary passing

pnkfelix (Sep 18 2019 at 12:29, on Zulip):

which, okay, is at runtime generating the impl

pnkfelix (Sep 18 2019 at 12:30, on Zulip):

but I'm not so sure it needs compiler magic

simulacrum (Sep 18 2019 at 12:30, on Zulip):

You can't know the layout of the enum/struct/etc to be able to access the fields and recurse polymorphically, right?

pnkfelix (Sep 18 2019 at 12:35, on Zulip):

i'm not being clear; I'm still not convinced you would need to resort to such low-level trickery

pnkfelix (Sep 18 2019 at 12:35, on Zulip):

but I also have failed to make a working example

pnkfelix (Sep 18 2019 at 12:36, on Zulip):

so I'll spend a few more minutes playing around, and if that goes nowhere, I'll abandon ship

simulacrum (Sep 18 2019 at 12:37, on Zulip):

hm, sounds good. I guess I don't see how you could avoid low-level trickery if you want to recursively visit or so

pnkfelix (Sep 18 2019 at 12:37, on Zulip):

okay, its definitely not simple, since, as we've already covered, you cannot rely on the compiler to generate the infinite set of type instantiations for you at compile time

simulacrum (Sep 18 2019 at 12:40, on Zulip):

that's what I was trying to get at -- you'd need to do so at runtime (well, not infinite set, but the subset you "need") and in order to do so it seems like you need to know layout details for it to be useful

simulacrum (Sep 18 2019 at 12:40, on Zulip):

I suppose you _could_ generate a constant depth at compiletime and call those methods

simulacrum (Sep 18 2019 at 12:41, on Zulip):

that seems less useful though

simulacrum (Sep 18 2019 at 12:42, on Zulip):

anyway, I do think we can eke out a polymorphic recursion detector though maybe it won't be as pretty as I was envisioning since we need to be more concrete (due to not actually wanting to forbid the type itself, only instantiations of it), but that seems mostly fine

varkor (Sep 18 2019 at 12:45, on Zulip):

it's subtle if you want to detect instantiations, because they might be generated by #[derive(Debug)], etc.

varkor (Sep 18 2019 at 12:45, on Zulip):

so the diagnostics are going to have to be quite clever

pnkfelix (Sep 18 2019 at 13:03, on Zulip):

I bet you could still do quite well in analyzing the type itself and just looking for where you see mixing of drop with polymorphic recursion

pnkfelix (Sep 18 2019 at 13:04, on Zulip):

basically focus on the cases where the drop-glue is going to be impossible to emit

simulacrum (Sep 18 2019 at 13:53, on Zulip):

Indeed, it won't catch everything but that's probably okay

Last update: Nov 16 2019 at 01:30UTC