Struggling with cannot infer an appropriate lifetime

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 https://github.com/mvtec-bergdolll/bump-alloc-lalrpop. With two branches:

  • main - before the switch to arena allocation (compiles)
  • bump-alloc - after the switch (fails compile)

The relevant change is https://github.com/mvtec-bergdolll/bump-alloc-lalrpop/pull/1/files

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.

I believe the error message is saying the opposite: 'input must outlive 'alloc.

And this, from what I gathered, is caused by the following chain of type definitions:

  • type Symbol = __Symbol<'input, 'alloc>
    
  • pub(crate) enum __Symbol<'input, 'alloc>
    {
        Variant0(&'input str),
        Variant1(Expr<'input, 'alloc>),
    }
    
  • in src/ast.rs:
    pub enum Expr<'input, 'alloc> {
        A(&'alloc Expr<'input, 'alloc>),
        B(&'alloc Expr<'input, 'alloc>),
        End(&'input str),
    }
    

And here, we can see that &'alloc Expr<'input, 'alloc> does indeed require that 'input outlive 'alloc.

In fact, manually adding this bound fixes the lifetime errors !

impl<'input, 'alloc, 'err> __state_machine::ParserDefinition for __StateMachine<'input, 'alloc, 'err>
where
    'input: 'err,
    'input: 'alloc // <- new !
{
    // ...
}

Now, I am not sure what you could do about this, since it is generated by a macro...

Ok, I think I have a simple work-around: get rid of the 'alloc lifetime :slight_smile:
Each time you use the 'alloc lifetime in src/ast.rs or src/grammar.lalrpop, just use 'input instead.

Example

  • before:
    pub enum Expr<'input, 'alloc> {
        A(&'alloc Expr<'input, 'alloc>),
        B(&'alloc Expr<'input, 'alloc>),
        End(&'input str),
    }
    
  • after:
    pub enum Expr<'input> {
        A(&'input Expr<'input>),
        B(&'input Expr<'input>),
        End(&'input str),
    }
    

I guess this might cause other errors later, so, maybe not ideal :confused: but, it works in this case.

Thanks for the answer. Well I needed the lifetime to be separate. But the idea is good, instead of 'input I'll unify it on 'alloc. That means I have to bump.alloc_str memcpy the input strings into the bump allocator, but that has two benefits. It simplifies the code and should be nice for cache locality.

cc @Marwes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.