Rustc overflows its stack with enums

help
#1

There's a issue out there stating similar problems, but it seems to relate with Serialize trait and serde library, which I did not use.
The problem appears in a project with single source file, and I was testing out a logically complex(?) enum, and rustc just overflows its stack.

use std::cell::RefCell;
use std::collections::LinkedList;
use std::ops::{Index, Range};

enum WhList<'a, T> {
    Single(T),
    Vector(Vec<T>),
    Chain(&'a WhList<'a, T>, &'a WhList<'a, T>),
    Append(&'a WhList<'a, T>, T),
    Overlay(&'a WhList<'a, T>, &'a WhList<'a, Option<T>>),
    Shadow(&'a WhList<'a, T>, usize, T),
    Slice(&'a WhList<'a, T>, usize, usize)
}

impl <'a, T> WhList<'a, T> {
    fn len(&'a self) -> usize {
        match self {
            WhList::Single(_) => 1,
            WhList::Vector(vec) => vec.len(),
            WhList::Chain(whl, whr) => whl.len() + whr.len(),
            WhList::Append(whl, _) => whl.len() + 1,
            WhList::Overlay(whl, _) => whl.len(),
            WhList::Shadow(whl, _, _) => whl.len(),
            WhList::Slice(_, bi, ee) => ee - bi,
        }
    }

    fn refer(&'a self, index: usize) -> Option<&'a T> {
        match self {
            WhList::Single(val) =>
                if index == 0 { Some(val) } else { None },
            WhList::Vector(vec) =>
                vec.get(index),
            WhList::Chain(whl, whr) =>
                if index >= whl.len() { whr.refer(index) } else { whl.refer(index) },
            WhList::Append(whl, val) =>
                if index == whl.len() { Some(val) } else { whl.refer(index) },
            WhList::Overlay(whl, who) =>
                match who.refer(index) {
                    Some(Some(val)) => Some(val),
                    _ => whl.refer(index),
                },
            WhList::Shadow(whl, idx, val) =>
                if *idx == index { Some(val) } else { whl.refer(index) },
            WhList::Slice(whl, bi, ee) =>
                if index >= *ee { None } else { whl.refer(bi + index) },
        }
    }

    fn from_vec(vec: Vec<T>) -> WhList<'a, T> {
        WhList::Vector(vec)
    }

    fn from_single(single: T) -> WhList<'a, T> {
        WhList::Single(single)
    }

    fn modify(&'a self, index: usize, value: T) -> Option<WhList<'a, T>> {
        if index >= self.len() {
            return None
        }
        Some(WhList::Shadow(self, index, value))
    }
}

fn main() {
    let a = WhList::from_vec(vec![1, 2, 3]);
    println!("Hello, world!");
}

I guess I'd better not disturb Rust devs if I wrote something seriously wrong :frowning: .

1 Like
#2

Just to clarify: did the compiler itself crash? That's always a bug (if your code is wrong, the compiler is supposed to tell you, not crash).

1 Like
#3

Yes, I confirm that because of following output by rustc:

thread 'rustc' has overflowed its stack
error: could not compile `whlist`; 9 warnings emitted
#4

Yep, that's definitely a compiler bug, then. Feel free to file an issue after verifying that it's not yet reported.

1 Like
#5

The WhList<'a, Option<T>> in the struct definition cannot work because of how Rust generics work (monomorphization), so there would need to be an infinite number of types being generated. Nonetheless, a stack overflow is not correct compiler behavior here. (Also Iā€™m surprised that this particular code example does compile successfully in --release mode. Well, presumably the unused enum variant is optimized away before code-gen or something like that.)

Here is a reduced version of your code

enum WhList<'a, T> {
    Vector(Vec<T>),
    Overlay(&'a WhList<'a, Option<T>>),
}

fn main() {
    let a = WhList::Vector(vec![1, 2, 3]);
    println!("Hello, world!");
}

Feel free to open an issue :slight_smile:

(Edit: Some minor further simplification:)

enum Foo<T: 'static> {
    Value(T),
    Recursive(&'static Foo<Option<T>>),
}

fn main() {
    let _x = Foo::Value(());
}
5 Likes
#6

I opened a new issue, and unfortunately, this is the first ever issue I opened. I hope I didn't screw it up.

Thanks for any help provided by you.

3 Likes
#7

Just out of curiosity, is there any reason why it does not crash when using a Box instead of a reference?

enum Foo<T> {
    Value(T),
    Recursive(Box<Foo<Option<T>>>),
}

fn main() {
    let _x = Foo::Value(());
}
#8

Presumably because it gets caught earlier in compilation (something about a recursion limit being reached for drop-check).

#9

Looks pretty good to me. Thanks for helping to make the compiler better :slightly_smiling_face:

1 Like