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

representable check fails if an enum references another enum that is cyclic #3008

Closed
nikomatsakis opened this Issue Jul 24, 2012 · 8 comments

Comments

Projects
None yet
6 participants
@nikomatsakis
Contributor

nikomatsakis commented Jul 24, 2012

Here is a test case:

// Compiler fails here because it starts to check foo which references
// bar which is cyclic.
enum foo { foo(bar) }
enum bar { bar_none, bar_some(bar) }

// As before, but with order reversed, so that should we happen to
// start checking from end of file forward, we'd still have the same
// problem.
enum bar1 { bar1_none, bar1_some(bar1) }
enum foo1 { foo1(bar1) }

fn main() {}

I think the right approach is to replace ty_structurally_contains() with something like walk_interior_tys(). then we have to keeep a stack of def-ids and when we enter a new nominal type check that we do not already have it on the stack. i started this then realized it was a big distraction from what I'm trying to do, so filing a bug instead. Marking as A-typesystem as this check is performed in middle/typeck/check.rs

@pnkfelix

This comment has been minimized.

Show comment
Hide comment
@pnkfelix

pnkfelix Apr 25, 2013

Member

Just to make this concrete: both of the cases that Niko describes yield ICE's. The first (the foo and bar items) yields an ICE with no useful error information. The second (bar1 and foo1) yields an error describing the illegal recursive enum type (followed by an ICE :).

Member

pnkfelix commented Apr 25, 2013

Just to make this concrete: both of the cases that Niko describes yield ICE's. The first (the foo and bar items) yields an ICE with no useful error information. The second (bar1 and foo1) yields an error describing the illegal recursive enum type (followed by an ICE :).

@pcwalton

This comment has been minimized.

Show comment
Hide comment
@pcwalton

pcwalton May 16, 2013

Contributor

I don't believe this is backwards incompatible, renominating.

Contributor

pcwalton commented May 16, 2013

I don't believe this is backwards incompatible, renominating.

@graydon

This comment has been minimized.

Show comment
Hide comment
@graydon

graydon Jun 6, 2013

Contributor

accepted for production-ready milestone

Contributor

graydon commented Jun 6, 2013

accepted for production-ready milestone

@bblum

This comment has been minimized.

Show comment
Hide comment
@bblum

bblum Aug 16, 2013

Contributor

appears to be properly classified

Contributor

bblum commented Aug 16, 2013

appears to be properly classified

@pnkfelix

This comment has been minimized.

Show comment
Hide comment
@pnkfelix

pnkfelix Jan 16, 2014

Member

Accepting for P-high.

Member

pnkfelix commented Jan 16, 2014

Accepting for P-high.

@pnkfelix

This comment has been minimized.

Show comment
Hide comment
@pnkfelix

pnkfelix Jan 16, 2014

Member

Tagging as mentorship bug, with @nikomatsakis as mentor

Member

pnkfelix commented Jan 16, 2014

Tagging as mentorship bug, with @nikomatsakis as mentor

@typelist

This comment has been minimized.

Show comment
Hide comment
@typelist

typelist Jan 19, 2014

Contributor

This code triggers the same infinite recursion in type_structurally_contains:

enum E { A, B(Bad) }
struct Bad { x: Bad }
Contributor

typelist commented Jan 19, 2014

This code triggers the same infinite recursion in type_structurally_contains:

enum E { A, B(Bad) }
struct Bad { x: Bad }
@typelist

This comment has been minimized.

Show comment
Hide comment
@typelist

typelist Jan 27, 2014

Contributor

I have a fix for this written, in case anyone is wondering whether to start working on it. I'll submit a pull request soon.

Contributor

typelist commented Jan 27, 2014

I have a fix for this written, in case anyone is wondering whether to start working on it. I'll submit a pull request soon.

typelist added a commit to typelist/rust that referenced this issue Jan 27, 2014

bors added a commit that referenced this issue Jan 30, 2014

auto merge of #11839 : typelist/rust/issue3008, r=huonw
It was possible to trigger a stack overflow in rustc because the routine used to verify enum representability,
type_structurally_contains, would recurse on inner types until hitting the original type. The overflow condition was when a different structurally recursive type (enum or struct) was contained in the type being checked.

I suspect my solution isn't as efficient as it could be. I pondered adding a cache of previously-seen types to avoid duplicating work (if enums A and B both contain type C, my code goes through C twice), but I didn't want to do anything that may not be necessary.

I'm a new contributor, so please pay particular attention to any unidiomatic code, misuse of terminology, bad naming of tests, or similar horribleness :)

Updated to verify struct representability as well.

Fixes #3008.
Fixes #3779.

@bors bors closed this in 056363f Jan 30, 2014

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment