Recursion in impls can result in stack overflow

[OhseyDev]

Hi Rust developers!
I have been working on a project and I accidentally found a bug.
I tried this code:

enum ExampleEnum {
   InterestingEnum(InterestingStruct),
   JustaDullEnum,
   OtherInterestingEnum(OtherInterestingStruct)
}

impl ExampleEnum {
   pub fn dull(&self) -> bool {
      self == &Self::JustaDullEnum
   }
}

At first, I dereferenced self which, I realised could be problematic but thought that the Rust compiler would tell me off:

impl ExampleEnum {
   pub fn dull(&self) -> bool {
      *self == Self::JustaDullEnum
   }
}

I expected to see this happen: to run the test successfully

Instead, this happened: program crashed due to a 'memory error'

rustc --version --verbose:

rustc 1.61.0 (fe5b13d68 2022-05-18)
binary: rustc
host: x86_64-unknown-linux-gnu
release: 1.61.0
LLVM version: 14.0.0

Debugger Note

Stop reason: signal SIGSEGV: address access protected (fault address: 0x7ffff7a36fb8)

[bugadani]

(Hi! I'm not a dev, just chiming in from the sidelines)

I've not been able to reproduce your issue. In particular:

• ExampleEnum does not implement PartialEq so your example snippet doesn't compile.
• Fixing the first issue, your example compiled and ran just fine.

Please provide a complete example that can be pasted to https://rust.godbolt.org/ directly and reproduces your issue. Also, please try updating to the latest rust compiler (1.62).

I'm fairly certain an enum comparison isn't your actual issue (it's such a widely used pattern, a bug like that would have serious consequences), but I don't think you have provided enough information to start investigating.

[OhseyDev]

Hi what additional info do you need?

[OhseyDev]

Oh my bad in the situation I had an implementation of it PartialEq. Lemme see if I find the commit on the personal project I was working on that I had it.

[OhseyDev]

Right I know what happened. It still compiled but it was unsafe code that Rust didn't pick up.

I had a PartialEq implementation on ExampleEnum that then depended on the "dull" function.

[OhseyDev]

Am I expecting too much of the Rust compiler to spot that kind of memory vulnerability?

[bugadani]

What vulnerability are you talking about? If you make an error in unsafe code, your program has every right to crash. It's possible that miri can catch this particular error for you, but if you write unsafe code, you tell the compiler that you know what you are doing (i.e. you know about and respect certain safety requirements).

[OhseyDev]

No no 'unsafe' block of code existed. It was safe rust.

[bugadani]

It still compiled but it was unsafe code that Rust didn't pick up.

No no 'unsafe' block of code existed.

I'm not sure I understand your problem at this point. Would you provide a complete example that crashes on https://rust.godbolt.org/ please?

[5225225]

Keep in mind stack overflows probably look like a segfault, but are doable in safe code.

[RalfJung]

@ohseyolivia

Hi what additional info do you need?

We need the full source code so we can see what actually happens. :)
Ideally reduced to a form where it's all in a single file. But people here can help with that.
From the snippets you showed us, everything looks fine.

@5225225 on most platforms we should a nice error on stack overflow. For example:

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

[OhseyDev]

Okay then it's probably that. Is that not intended for the Rust compiler to identify?

[5225225]

Well, it might not be a stack overflow, it would be best to show the full code if possible, including the PartialEq implementation too so we can check for sure what it is. Even if it is a stack overflow, then knowing how it was caused helps write better diagnostics to warn against it.

And rust does try to detect easy cases of infinite recursion, but it can be trickier in more complex cases.

For example, this code warns about infinite recursion

fn a() {
    a();
}

But this does not

fn a() {
    b();
}

fn b() {
    a();
}

I've opened #99220 to track the case of a recursive PartialEq implementation using self == rhs, which isn't detected.

[OhseyDev]

I understand the difficulties with detecting complex instances of recursion bugs. I have the repository on my profile but I tweaked the code to avoid the problem. I can fork it and then recreate the problem.

[OhseyDev]

https://github.com/ohseyolivia/reblar/tree/rustcbug for the exact case

[OhseyDev]

Oh also, the relevant file that includes the PartialEq implementation is in src/lex.rs

[5225225]

Ah, yeah, that doesn't look like the case I thought it was, but it's still recursive. Here's a reduced case of it.

#[derive(Debug)]
pub enum Token {
    Identifior(String),
    Indent,
}

impl Token {
    pub fn identifier(&self) -> Option<String> {
        match self {
            Self::Identifior(str) => Some(str.clone()),
            _ => None
        }
    }
    pub fn indent(&self) -> bool {
        self == &Self::Indent
    }
}

impl PartialEq for Token {
    fn eq(&self, other: &Self) -> bool {
        match other {
            Self::Identifior(n) => {
                let ident = self.identifier();
                if ident.is_none() { return false; }
                ident.unwrap() == *n
            }
            Self::Indent => {
                self.indent()
            }
        }
    }
}

fn main() {
    let is_ident = Token::Indent == Token::Indent;
}

So you start of calling PartialEq for Token, which matches on the other's type, which is Indent. So you call self.indent(), which then does self == &Self::Indent, which uses the PartialEq for Token, with the other being Indent.

So this is a trickier case of recursion to detect at compile time. Thank you for sharing the test case, in any case!

[OhseyDev]

Apologies for not being super clear. I am new to working collaboratively in regards to technical subjects so I have been anxious. Thank you all for being patient!

[OhseyDev]

Should I close this issue now?

[workingjubilee]

If you are satisfied this issue has served its purpose, then you may close it as you like, yes.