I'm building a recursive parser where different syntax structures reference each other. Each parser implements try_construct, which merges recovery contexts using context.merge_with(self.recovery_context()).
The issue arises when calling try_construct of FunctionSignatureParser inside TypeParser. This causes Rust to overflow while evaluating trait bounds:
error[E0275]: overflow evaluating the requirement `core::CombinedRecovery<&DummyRecovery, DelimitedRecoveryStragery<'_, seperated::SeparatedBy<ParameterParser>>>: Sized`
|
= help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`skullbrain_parser`)
note: required for `CombinedRecovery<&CombinedRecovery<&DummyRecovery, ...>, ...>` to implement `core::RecoveryStrategy`
--> skullbrain-parser/src/core/mod.rs:142:16
|
142 | impl<'a, A, B> RecoveryStrategy for CombinedRecovery<&'a A, B>
| - ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^
| |
| unsatisfied trait bound introduced here
= note: 128 redundant requirements hidden
= note: required for `CombinedRecovery<&CombinedRecovery<&CombinedRecovery<&..., ...>, ...>, ...>` to implement `core::RecoveryStrategy`
= note: the full name for the type has been written to '/home/user/SkullBrain/target/debug/deps/skullbrain_parser-8bf45239dc460134.long-type-1258188400081423112.txt'
= note: consider using `--verbose` to print the full type name to the console
error[E0275]: overflow evaluating the requirement `core::CombinedRecovery<&DummyRecovery, TypeParserRecoveryStragery>: Sized`
|
= help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`skullbrain_parser`)
note: required for `CombinedRecovery<&CombinedRecovery<&DummyRecovery, TypeParserRecoveryStragery>, ...>` to implement `core::RecoveryStrategy`
--> skullbrain-parser/src/core/mod.rs:142:16
|
142 | impl<'a, A, B> RecoveryStrategy for CombinedRecovery<&'a A, B>
| - ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^
| |
| unsatisfied trait bound introduced here
= note: 127 redundant requirements hidden
= note: required for `CombinedRecovery<&CombinedRecovery<&CombinedRecovery<&..., ...>, ...>, ...>` to implement `core::RecoveryStrategy`
note: required for `CombinedRecovery<&CombinedRecovery<&CombinedRecovery<&..., ...>, ...>, ...>` to implement `core::Recovery`
--> skullbrain-parser/src/core/recovery.rs:4:9
|
4 | impl<T> Recovery for T
| ^^^^^^^^ ^
5 | where
6 | T: RecoveryStrategy,
| ---------------- unsatisfied trait bound introduced here
= note: the full name for the type has been written to '/home/user/SkullBrain/target/debug/deps/skullbrain_parser-8bf45239dc460134.long-type-14150472290417344823.txt'
= note: consider using `--verbose` to print the full type name to the console
However:
- Increasing the recursion limit does not fix the issue. (even up to 2024)
- Calling
try_constructofTypeParserinsideFunctionSignatureParserworks, but the reverse (callingFunctionSignatureParser::try_constructinTypeParser) does not. (Possibily due to some recursiveness???) - Merging recovery contexts itself does not cause issues; the error only occurs when actually calling
try_constructinsideTypeParser.
Syntax Example:
For reference, the expected syntax (using TokenKind) is something like :
TYPE = TokenKind::Type OR TokenKind::Ident OR FUNC_SIG;
FUNC_SIG = ( TokenKind::Ident : TYPE ) RETURN TYPE;
This shows that TYPE and FUNC_SIG are mutually recursive.
Code Structure:
pub enum TokenKind {
Type, Ident
///.....
}
pub(crate) struct TypeParser(FunctionSignatureParser);
pub(super) struct FunctionSignatureParser {
pub(super) parameters: Parameters,
}
pub(crate) struct Parameters(Rc<DelimitedContentParser<ParameterList>>);
type ParameterList = SeparatedBy<ParameterParser>;
pub(crate) struct ParameterParser(pub(super) Rc<RefCell<TypeParser>>);
Utility structs:
pub(crate) struct SeparatedBy<T: SyntaxConstructor> {
separator: TokenKind,
content_parser: T,
}
pub(crate) struct DelimitedContentParser<T: SyntaxConstructor> {
content_parser: T,
}
pub(crate) struct CombinedRecovery<A, B> {
primary: A,
secondary: B,
}
/// Literally only used to pass some value for the recovery_context to the try_construct method, and defines no recovery point
struct DummyRecovery;
Recovery strategy:
pub(crate) trait RecoveryStrategy {
fn is_recovery_point(&self, kind: &TokenKind) -> bool;
fn merge_with<T: RecoveryStrategy>(&self, other: T) -> CombinedRecovery<&Self, T> {
CombinedRecovery {
primary: self,
secondary: other,
}
}
}
impl<'a, A, B> RecoveryStrategy for CombinedRecovery<&'a A, B>
where
A: RecoveryStrategy,
B: RecoveryStrategy,
{
fn is_recovery_point(&self, kind: &TokenKind) -> bool {
self.primary.is_recovery_point(kind) || self.secondary.is_recovery_point(kind)
}
}
And a simplified try_construct for the parsers:
impl SyntaxConstructor for TypeParser {
fn recovery_context<'a>(&'a self) -> impl RecoveryStrategy + 'a {
/// Usually either a unit-struct or a wrapper around self
todo!()
}
fn try_construct(
&self,
// stream_state: &mut TokenStreamState,
// syntax_tree: &mut RawSyntaxTree,
recovery_ctx: &impl RecoveryStrategy,
// parent_id: NodeId,
) -> RecoveryResult {
let recovery_ctx = recovery_ctx.merge_with(self.recovery_context()); // This works fine
// Some parsing code that advances the stream_state
// With some parsers containing a
// self.some_other_parser.try_construct(stream_state, syntax_tree, &recovery_ctx, parent_id)
}
}
Initialization Code:
pub(self) fn initialize_type_parser() -> (TypeParser, FunctionSignatureParser) {
// Create shared reference to be used by both parsers (a new-type around `Rc<RefCell<Option<T>>>`
let mut type_parser_ref = CircularRef::default();
// Create parameters parser with reference to type parser (which is None for now)
let parameters: Parameters = parameters(CircularRef::clone(&type_parser_ref));
let function_signature = FunctionSignatureParser {
parameters: parameters,
};
// Create type parser with reference to function signature
let type_parser = TypeParser::new(&function_signature);
// Now set the type parser in the shared reference
type_parser_ref.set(type_parser.clone());
(type_parser, function_signature)
}
pub(crate) fn parameters(type_ref: CircularRef<TypeParser>) -> Parameters {
// DelimitedContentParser::parentheses omitted as its not important
let inner = DelimitedContentParser::parentheses(parameter_list(type_ref));
Parameters(Rc::new(inner))
}
My Understanding:
I know that impl Trait just hides the concrete type, so a recursive problem is possible. However, I expected this not to be an issue since try_construct (of FunctionSignatureParser in TypeParser) is only called when the correct tokens are found in stream_state, meaning it should execute in a bounded manner rather than infinitely expanding at compile time. (right??)
Questions:
- Why does calling
try_constructonFunctionSignatureParserinsideTypeParsercause a compile time error but the reverse works? (For the latter I am guessing that it completes the circular cycle) - Is there a way to restructure my code to avoid this issue or is this a limitation of my current design?
Thanks in advance!