Recursive Structures cause Stack Overflow

[rushsteve1]

Issue split from #184

Certain recursive structures can cause a panic when attempting to deserialize.

use serde::Deserialize;

#[derive(Debug, Deserialize)]
#[serde(untagged)]
enum Loop {
    Number(usize),
    MaybeRecur(Box<Option<Loop>>)
}

fn main() {
    // Works
    let _: Loop = serde_dhall::from_str("Some 5").parse().unwrap();

    // Works
    let _: Loop = serde_dhall::from_str("Some (Some 5)").parse().unwrap();

    // Errors
    let _: Loop = serde_dhall::from_str("{ x = 5 }").parse().unwrap();
}

The last line attempts to deserialize a Dhall expression that does not match the Loop type, but instead of an error being returned then unwrapped it panics with the following error:

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

Based on the error I believe that something in the parser is causing infinite recursion, but that's just my guess.

[Nadrieril]

The parser is fine, because it can otherwise parse { x = 5 } correctly. The problem is in the conversion into Loop via serde. In particular, it works if you remove #[serde(untagged)].

[Nadrieril]

Hmm, actually it's an unavoidable issue with serde's untagged enums: in this playground link, you can see that Number(0), Recur(Number(0)) etc all serialize to "0". So when deserializing "0" you can't know which value to construct. And in fact serde_json also stack overflows on this. So there's nothing I can do about this I'm afraid.

[rushsteve1]

Ah I see, that makes sense. Thanks for figuring that out!