Stack overflow in parser

[vezenovm]

Aim

I want the user to be able to repeat the same token many times (essentially unlimited times as it should be up to the user), without triggering a stack overflow.

Expected Behavior

The compiler should not stack overflow.

Bug

For our example we are just going to comment out EXPONENTIATE in regression_4709. You could even comment out the entire file. This will result in a stack overflow:

thread '<unknown>' has overflowed its stack
fatal runtime error: stack overflow

This overflow looks to be due to recursion being utilized for parsing a list of items

noir/compiler/noirc_frontend/src/parser/parser/parse_many.rs

Line 9 in 74ec723

pub(super) fn parse_many<T, F>(

For comments parse_many is used here.

This is an edge case and seems unlikely to be hit but I did not test under what circumstances we hit the stack limit. It would be good to know under what circumstances we may hit the stack limit as parse_many is utilized in many locations. I could see this stack overflow being hit by a use tree in larger programs with many imports.

To Reproduce

1. Comment out src/main.nr in regression_4709
2. nargo compile
3. See stack overflow

Workaround

Yes

Workaround Description

The workaround is to not have so many repeated tokens.

Additional Context

No response

Project Impact

Nice-to-have

Blocker Context

I would be surprised this would block any user and that they could not work around by manually splitting up their large token list.

Nargo Version

nargo version = 1.0.0-beta.1 noirc version = 1.0.0-beta.1+2e5d91f3d69ce629d07eb6041736b5a8e8ed2013 (git version hash: 2e5d91f, is dirty: false)

NoirJS Version

No response

Proving Backend Tooling & Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[vezenovm]

I just noticed that the first line in regression_4709 is // Regression test for issue #4709. Commenting out the whole file makes this line // // Regression test for issue #4709, which gives me a stack overflow. Deleting the extra // I get

error: cannot compile crate into a program as it does not contain a `main` function

as expected.

[michaeljklein]

@asterite I believe your new parser fixed this?

[asterite]

I think this was reported against the new parser, but I was never able to reproduce it.

[vezenovm]

I think this was reported against the new parser, but I was never able to reproduce it.

I just tried it again on master with a CMD + a and CMD + / to comment out the whole regression_4709 test. I still get the stack overflow.

Also looks like I get a stack overflow in both cases mentioned in this comment: #6975 (comment).

[asterite]

Oh, you are right. I had export RUST_MIN_STACK=104857600 in my ~/.zshrc, but without it I get the stack overflow. I'll take a look at this today.