Hi, I have project that uses LALRPOP to parse a grammar, which involves boxing nested expressions, I tried using bumpalo to arena allocate the nodes but I get errors I'm not sure I really understand in generated code.
I've created a small PoC repo here GitHub - mvtec-bergdolll/bump-alloc-lalrpop: Demo repository. With two branches:
- main - before the switch to arena allocation (compiles)
- bump-alloc - after the switch (fails compile)
The relevant change is Switch to arena allocation by mvtec-bergdolll · Pull Request #1 · mvtec-bergdolll/bump-alloc-lalrpop · GitHub
Which then gives me this wonderful error:
Compiling bump-alloc-lalrpop v0.1.0 (/bump-alloc-lalrpop)
error[E0478]: lifetime bound not satisfied
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:93:23
|
93 | type Symbol = __Symbol<'input, 'alloc>;
| ^^^^^^^^^^^^^^^^^^^^^^^^
|
note: lifetime parameter instantiated with the lifetime `'input` as defined here
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:10
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
note: but lifetime parameter must outlive the lifetime `'alloc` as defined here
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:18
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
error[E0478]: lifetime bound not satisfied
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:94:24
|
94 | type Success = Expr<'input, 'alloc>;
| ^^^^^^^^^^^^^^^^^^^^
|
note: lifetime parameter instantiated with the lifetime `'input` as defined here
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:10
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
note: but lifetime parameter must outlive the lifetime `'alloc` as defined here
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:18
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'input` due to conflicting requirements
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:135:12
|
135 | fn token_to_symbol(&self, token_index: usize, token: Self::Token) -> Self::Symbol {
| ^^^^^^^^^^^^^^^
|
note: first, the lifetime cannot outlive the lifetime `'input` as defined here...
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:10
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
note: ...but the lifetime must also be valid for the lifetime `'alloc` as defined here...
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:18
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
note: ...so that the types are compatible
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:135:12
|
135 | fn token_to_symbol(&self, token_index: usize, token: Self::Token) -> Self::Symbol {
| ^^^^^^^^^^^^^^^
= note: expected `<__StateMachine<'input, 'alloc, 'err> as ParserDefinition>`
found `<__StateMachine<'_, '_, '_> as ParserDefinition>`
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'input` due to conflicting requirements
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:149:12
|
149 | fn error_recovery_symbol(
| ^^^^^^^^^^^^^^^^^^^^^
|
note: first, the lifetime cannot outlive the lifetime `'input` as defined here...
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:10
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
note: ...but the lifetime must also be valid for the lifetime `'alloc` as defined here...
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:18
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
note: ...so that the types are compatible
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:149:12
|
149 | fn error_recovery_symbol(
| ^^^^^^^^^^^^^^^^^^^^^
= note: expected `<__StateMachine<'input, 'alloc, 'err> as ParserDefinition>`
found `<__StateMachine<'_, '_, '_> as ParserDefinition>`
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'input` due to conflicting requirements
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:156:12
|
156 | fn reduce(
| ^^^^^^
|
note: first, the lifetime cannot outlive the lifetime `'input` as defined here...
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:10
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
note: ...but the lifetime must also be valid for the lifetime `'alloc` as defined here...
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:86:18
|
86 | impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
| ^^^^^^
note: ...so that the types are compatible
--> /bump-alloc-lalrpop/target/debug/build/bump-alloc-lalrpop-0129a632e50d0d23/out/grammar.rs:156:12
|
156 | fn reduce(
| ^^^^^^
= note: expected `<__StateMachine<'input, 'alloc, 'err> as ParserDefinition>`
found `<__StateMachine<'_, '_, '_> as ParserDefinition>`
Some errors have detailed explanations: E0478, E0495.
For more information about an error, try `rustc --explain E0478`.
error: could not compile `bump-alloc-lalrpop` due to 5 previous errors
It claims that 'but lifetime parameter must outlive the lifetime 'alloc
', which I don't get why. Where does it require 'alloc
to outlive 'input
?
Here is the relevant part of the generated file:
pub(crate) struct __StateMachine<'input, 'alloc, 'err>
where 'input: 'err
{
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
__phantom: core::marker::PhantomData<(&'input (), &'alloc (), &'err ())>,
}
impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
where 'input: 'err
{
type Location = usize;
type Error = LexError;
type Token = Token<'input>;
type TokenIndex = usize;
type Symbol = __Symbol<'input, 'alloc>;
type Success = Expr<'input, 'alloc>;
type StateIndex = i8;
type Action = i8;
type ReduceIndex = i8;
type NonterminalIndex = usize;
This is the full generated file:
Summary
// auto-generated: "lalrpop 0.19.7"
// sha3: 35f06dec1af196557610e620a2baa61754c790732574dbe95f51b232a67cf018
use bumpalo::Bump;
use lalrpop_util::{ErrorRecovery};
use crate::ast::Expr;
use crate::lex::{Token, LexError};
#[allow(unused_extern_crates)]
extern crate lalrpop_util as __lalrpop_util;
#[allow(unused_imports)]
use self::__lalrpop_util::state_machine as __state_machine;
extern crate core;
extern crate alloc;
#[cfg_attr(rustfmt, rustfmt_skip)]
mod __parse__Lang {
#![allow(non_snake_case, non_camel_case_types, unused_mut, unused_variables, unused_imports, unused_parens, clippy::all)]
use bumpalo::Bump;
use lalrpop_util::{ErrorRecovery};
use crate::ast::Expr;
use crate::lex::{Token, LexError};
#[allow(unused_extern_crates)]
extern crate lalrpop_util as __lalrpop_util;
#[allow(unused_imports)]
use self::__lalrpop_util::state_machine as __state_machine;
extern crate core;
extern crate alloc;
use super::__ToTriple;
#[allow(dead_code)]
pub(crate) enum __Symbol<'input, 'alloc>
{
Variant0(&'input str),
Variant1(Expr<'input, 'alloc>),
}
const __ACTION: &[i8] = &[
// State 0
3, 4, 0,
// State 1
0, 0, 0,
// State 2
0, 0, 0,
// State 3
0, 0, 0,
];
fn __action(state: i8, integer: usize) -> i8 {
__ACTION[(state as usize) * 3 + integer]
}
const __EOF_ACTION: &[i8] = &[
// State 0
0,
// State 1
-3,
// State 2
-1,
// State 3
-2,
];
fn __goto(state: i8, nt: usize) -> i8 {
match nt {
0 => 1,
_ => 0,
}
}
fn __expected_tokens(__state: i8) -> alloc::vec::Vec<alloc::string::String> {
const __TERMINAL: &[&str] = &[
r###""A""###,
r###""B""###,
r###""C""###,
];
__TERMINAL.iter().enumerate().filter_map(|(index, terminal)| {
let next_state = __action(__state, index);
if next_state == 0 {
None
} else {
Some(alloc::string::ToString::to_string(terminal))
}
}).collect()
}
pub(crate) struct __StateMachine<'input, 'alloc, 'err>
where 'input: 'err
{
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
__phantom: core::marker::PhantomData<(&'input (), &'alloc (), &'err ())>,
}
impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
where 'input: 'err
{
type Location = usize;
type Error = LexError;
type Token = Token<'input>;
type TokenIndex = usize;
type Symbol = __Symbol<'input, 'alloc>;
type Success = Expr<'input, 'alloc>;
type StateIndex = i8;
type Action = i8;
type ReduceIndex = i8;
type NonterminalIndex = usize;
#[inline]
fn start_location(&self) -> Self::Location {
Default::default()
}
#[inline]
fn start_state(&self) -> Self::StateIndex {
0
}
#[inline]
fn token_to_index(&self, token: &Self::Token) -> Option<usize> {
__token_to_integer(token, core::marker::PhantomData::<(&(), &(), &())>)
}
#[inline]
fn action(&self, state: i8, integer: usize) -> i8 {
__action(state, integer)
}
#[inline]
fn error_action(&self, state: i8) -> i8 {
__action(state, 3 - 1)
}
#[inline]
fn eof_action(&self, state: i8) -> i8 {
__EOF_ACTION[state as usize]
}
#[inline]
fn goto(&self, state: i8, nt: usize) -> i8 {
__goto(state, nt)
}
fn token_to_symbol(&self, token_index: usize, token: Self::Token) -> Self::Symbol {
__token_to_symbol(token_index, token, core::marker::PhantomData::<(&(), &(), &())>)
}
fn expected_tokens(&self, state: i8) -> alloc::vec::Vec<alloc::string::String> {
__expected_tokens(state)
}
#[inline]
fn uses_error_recovery(&self) -> bool {
false
}
#[inline]
fn error_recovery_symbol(
&self,
recovery: __state_machine::ErrorRecovery<Self>,
) -> Self::Symbol {
panic!("error recovery not enabled for this grammar")
}
fn reduce(
&mut self,
action: i8,
start_location: Option<&Self::Location>,
states: &mut alloc::vec::Vec<i8>,
symbols: &mut alloc::vec::Vec<__state_machine::SymbolTriple<Self>>,
) -> Option<__state_machine::ParseResult<Self>> {
__reduce(
self.bump,
self.errors,
action,
start_location,
states,
symbols,
core::marker::PhantomData::<(&(), &(), &())>,
)
}
fn simulate_reduce(&self, action: i8) -> __state_machine::SimulatedReduce<Self> {
panic!("error recovery not enabled for this grammar")
}
}
fn __token_to_integer<
'input,
'alloc,
'err,
>(
__token: &Token<'input>,
_: core::marker::PhantomData<(&'input (), &'alloc (), &'err ())>,
) -> Option<usize>
{
match *__token {
Token::A(_) if true => Some(0),
Token::B(_) if true => Some(1),
Token::C(_) if true => Some(2),
_ => None,
}
}
fn __token_to_symbol<
'input,
'alloc,
'err,
>(
__token_index: usize,
__token: Token<'input>,
_: core::marker::PhantomData<(&'input (), &'alloc (), &'err ())>,
) -> __Symbol<'input, 'alloc>
{
match __token_index {
0 | 1 | 2 => match __token {
Token::A(__tok0) | Token::B(__tok0) | Token::C(__tok0) if true => __Symbol::Variant0(__tok0),
_ => unreachable!(),
},
_ => unreachable!(),
}
}
pub struct LangParser {
_priv: (),
}
impl LangParser {
pub fn new() -> LangParser {
LangParser {
_priv: (),
}
}
#[allow(dead_code)]
pub fn parse<
'input,
'alloc,
'err,
__TOKEN: __ToTriple<'input, 'alloc, 'err, >,
__TOKENS: IntoIterator<Item=__TOKEN>,
>(
&self,
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
__tokens0: __TOKENS,
) -> Result<Expr<'input, 'alloc>, __lalrpop_util::ParseError<usize, Token<'input>, LexError>>
{
let __tokens = __tokens0.into_iter();
let mut __tokens = __tokens.map(|t| __ToTriple::to_triple(t));
__state_machine::Parser::drive(
__StateMachine {
bump,
errors,
__phantom: core::marker::PhantomData::<(&(), &(), &())>,
},
__tokens,
)
}
}
pub(crate) fn __reduce<
'input,
'alloc,
'err,
>(
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
__action: i8,
__lookahead_start: Option<&usize>,
__states: &mut alloc::vec::Vec<i8>,
__symbols: &mut alloc::vec::Vec<(usize,__Symbol<'input, 'alloc>,usize)>,
_: core::marker::PhantomData<(&'input (), &'alloc (), &'err ())>,
) -> Option<Result<Expr<'input, 'alloc>,__lalrpop_util::ParseError<usize, Token<'input>, LexError>>>
{
let (__pop_states, __nonterminal) = match __action {
0 => {
__reduce0(bump, errors, __lookahead_start, __symbols, core::marker::PhantomData::<(&(), &(), &())>)
}
1 => {
__reduce1(bump, errors, __lookahead_start, __symbols, core::marker::PhantomData::<(&(), &(), &())>)
}
2 => {
// __Lang = Lang => ActionFn(0);
let __sym0 = __pop_Variant1(__symbols);
let __start = __sym0.0.clone();
let __end = __sym0.2.clone();
let __nt = super::__action0::<>(bump, errors, __sym0);
return Some(Ok(__nt));
}
_ => panic!("invalid action code {}", __action)
};
let __states_len = __states.len();
__states.truncate(__states_len - __pop_states);
let __state = *__states.last().unwrap();
let __next_state = __goto(__state, __nonterminal);
__states.push(__next_state);
None
}
#[inline(never)]
fn __symbol_type_mismatch() -> ! {
panic!("symbol type mismatch")
}
fn __pop_Variant1<
'input,
'alloc,
>(
__symbols: &mut alloc::vec::Vec<(usize,__Symbol<'input, 'alloc>,usize)>
) -> (usize, Expr<'input, 'alloc>, usize)
{
match __symbols.pop() {
Some((__l, __Symbol::Variant1(__v), __r)) => (__l, __v, __r),
_ => __symbol_type_mismatch()
}
}
fn __pop_Variant0<
'input,
'alloc,
>(
__symbols: &mut alloc::vec::Vec<(usize,__Symbol<'input, 'alloc>,usize)>
) -> (usize, &'input str, usize)
{
match __symbols.pop() {
Some((__l, __Symbol::Variant0(__v), __r)) => (__l, __v, __r),
_ => __symbol_type_mismatch()
}
}
pub(crate) fn __reduce0<
'input,
'alloc,
'err,
>(
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
__lookahead_start: Option<&usize>,
__symbols: &mut alloc::vec::Vec<(usize,__Symbol<'input, 'alloc>,usize)>,
_: core::marker::PhantomData<(&'input (), &'alloc (), &'err ())>,
) -> (usize, usize)
{
// Lang = "A" => ActionFn(1);
let __sym0 = __pop_Variant0(__symbols);
let __start = __sym0.0.clone();
let __end = __sym0.2.clone();
let __nt = super::__action1::<>(bump, errors, __sym0);
__symbols.push((__start, __Symbol::Variant1(__nt), __end));
(1, 0)
}
pub(crate) fn __reduce1<
'input,
'alloc,
'err,
>(
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
__lookahead_start: Option<&usize>,
__symbols: &mut alloc::vec::Vec<(usize,__Symbol<'input, 'alloc>,usize)>,
_: core::marker::PhantomData<(&'input (), &'alloc (), &'err ())>,
) -> (usize, usize)
{
// Lang = "B" => ActionFn(2);
let __sym0 = __pop_Variant0(__symbols);
let __start = __sym0.0.clone();
let __end = __sym0.2.clone();
let __nt = super::__action2::<>(bump, errors, __sym0);
__symbols.push((__start, __Symbol::Variant1(__nt), __end));
(1, 0)
}
}
pub use self::__parse__Lang::LangParser;
#[allow(unused_variables)]
fn __action0<
'input,
'alloc,
'err,
>(
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
(_, __0, _): (usize, Expr<'input, 'alloc>, usize),
) -> Expr<'input, 'alloc>
{
__0
}
#[allow(unused_variables)]
fn __action1<
'input,
'alloc,
'err,
>(
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
(_, __0, _): (usize, &'input str, usize),
) -> Expr<'input, 'alloc>
{
Expr::A(bump.alloc(Expr::End(__0)))
}
#[allow(unused_variables)]
fn __action2<
'input,
'alloc,
'err,
>(
bump: &'alloc Bump,
errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, LexError>>,
(_, __0, _): (usize, &'input str, usize),
) -> Expr<'input, 'alloc>
{
Expr::B(bump.alloc(Expr::End(__0)))
}
pub trait __ToTriple<'input, 'alloc, 'err, >
{
fn to_triple(value: Self) -> Result<(usize,Token<'input>,usize), __lalrpop_util::ParseError<usize, Token<'input>, LexError>>;
}
impl<'input, 'alloc, 'err, > __ToTriple<'input, 'alloc, 'err, > for (usize, Token<'input>, usize)
{
fn to_triple(value: Self) -> Result<(usize,Token<'input>,usize), __lalrpop_util::ParseError<usize, Token<'input>, LexError>> {
Ok(value)
}
}
impl<'input, 'alloc, 'err, > __ToTriple<'input, 'alloc, 'err, > for Result<(usize, Token<'input>, usize), LexError>
{
fn to_triple(value: Self) -> Result<(usize,Token<'input>,usize), __lalrpop_util::ParseError<usize, Token<'input>, LexError>> {
match value {
Ok(v) => Ok(v),
Err(error) => Err(__lalrpop_util::ParseError::User { error }),
}
}
}
Please help me understand why this error happens, and how I could address it.