Preventing legacy mutable variable borrowing to solve lifetime problem

(For the background of problem, you can jump to this)

MWE in Rust 1.76:

/// The trait similar from [`From`]
/// but with a parser to determine how it will be parsed into.
///
/// It will be implemented to support `parser.parse::<Target>(source)` grammar.
trait ParseFrom<From, Parser> {
    fn parse_from(from: From, parser: Parser) -> Self;
}

/// Source data, which is needed to be parsed into `Target`
#[derive(Debug, Clone)]
struct Source(String);

/// Target
#[derive(Debug)]
struct Target(Source);

/// The parser parsing `Source` into `Target`
/// * It will references some referenced data, so contains a lifetime parameter.
#[derive(Debug)]
struct Parser<'a> {
    data: &'a str,
}

/// The parse state for parsing
#[derive(Debug)]
struct ParseState<'a> {
    data: &'a str,
    parse_count: usize,
    source: Source,
}

impl<'a> Parser<'a> {
    /// Build the parse state to parse the source data
    pub fn build_state(&self, source: Source) -> ParseState<'a> {
        ParseState {
            data: "S", // any possible data using in parsing
            parse_count: 0,
            source,
        }
    }
}

impl<'a> ParseState<'a> {
    /// Let the state start to parse to calculate the output.
    /// * It should be generic function to reuse the function name likes [`str::parse`]
    fn parse<To>(&'a mut self) -> To
    where
        To: ParseFrom<(), &'a mut Self>,
    {
        To::parse_from((), self)
    }
}

/// () ---[ParseState]--> Target
impl<'a> ParseFrom<(), &'a mut ParseState<'a>> for Target {
    /// Run the parse progress to yield result
    fn parse_from(_: (), state: &'a mut ParseState) -> Self {
        // the values in parse state may be changed
        state.parse_count += 1;
        Target(state.source.clone())
    }
}

/// Source ---[Parser]--> ParserState --> AnyTarget
impl<'a, AnyTarget> ParseFrom<Source, &'a Parser<'a>> for AnyTarget
where
    // Type `AnyTarget` should be possible to be yielded from `ParseState`
    AnyTarget: ParseFrom<(), &'a mut ParseState<'a>>,
{
    /// For all things `ParserState` can yield, it can be parsed from `Source`
    fn parse_from(source: Source, parser: &'a Parser) -> Self {
        // Build the parse state
        let mut state = parser.build_state(source);

        // Let the state parse the inner data to yield a result
        let result = state.parse(); // line A

        // Explicitly destruct the state after parsing data, to show more details
        drop(state); // line B

        // Return the result of parsing
        result
    }
}

At line A:

error[E0597]: `state` does not live long enough
  --> main.rs:76:22
  |
65 | impl<'a, AnyTarget> ParseFrom<Source, &'a Parser<'a>> for AnyTarget
  |      -- lifetime `'a` defined here
...
73 |         let mut state = parser.build_state(source);
  |             --------- binding `state` declared here
...
76 |         let result = state.parse(); // line A
  |                      ^^^^^--------
  |                      |
  |                      borrowed value does not live long enough
  |                      argument requires that `state` is borrowed for `'a`
...
83 |     }
  |     - `state` dropped here while still borrowed

At line B:

error[E0505]: cannot move out of `state` because it is borrowed
  --> main.rs:79:14
   |
65 | impl<'a, AnyTarget> ParseFrom<Source, &'a Parser<'a>> for AnyTarget
   |      -- lifetime `'a` defined here
...
73 |         let mut state = parser.build_state(source);
   |             --------- binding `state` declared here
...
76 |         let result = state.parse(); // line A
   |                      -------------
   |                      |
   |                      borrow of `state` occurs here
   |                      argument requires that `state` is borrowed for `'a`
...
79 |         drop(state); // line B
   |              ^^^^^ move out of `state` occurs here

How to resolve this lifetime problem, making guarantee to the compiler that the variable result don't borrow anything from variable state?

Also see Rust Playground

This means that result always requires state:

fn parse<To>(&'a mut self) -> To
    where
        To: ParseFrom<(), &'a mut Self>,

To simplify it:

fn parse(&'a mut self) -> ParseFrom<(), &'a mut Self>

and because the same lifetime is on self and the returned value, it means that destroying self (state) will invalidate returned value.

I don't understand why you have ParseFrom and To combined like that. See how parse and FromStr trait works in the standard library.

@@ -29,9 +29,9 @@ struct ParseState<'a> {
     source: Source,
 }

-impl<'a> Parser<'a> {
+impl Parser<'_> {
     /// Build the parse state to parse the source data
-    pub fn build_state(&self, source: Source) -> ParseState<'a> {
+    pub fn build_state(&self, source: Source) -> ParseState<'_> {
         ParseState {
             data: "S", // any possible data using in parsing
             parse_count: 0,
@@ -43,18 +43,18 @@ impl<'a> Parser<'a> {
 impl<'a> ParseState<'a> {
     /// Let the state start to parse to calculate the output.
     /// * It should be generic function to reuse the function name likes [`str::parse`]
-    fn parse<To>(&'a mut self) -> To
+    fn parse<'p, To>(&'p mut self) -> To
     where
-        To: ParseFrom<(), &'a mut Self>,
+        To: ParseFrom<(), &'p mut Self>,
     {
         To::parse_from((), self)
     }
 }

 /// () ---[ParseState]--> Target
-impl<'a> ParseFrom<(), &'a mut ParseState<'a>> for Target {
+impl<'p> ParseFrom<(), &'p mut ParseState<'_>> for Target {
     /// Run the parse progress to yield result
-    fn parse_from(_: (), state: &'a mut ParseState) -> Self {
+    fn parse_from(_: (), state: &'p mut ParseState) -> Self {
         // the values in parse state may be changed
         state.parse_count += 1;
         Target(state.source.clone())
@@ -62,10 +62,10 @@ impl<'a> ParseFrom<(), &'a mut ParseState<'a>> for Target {
 }

 /// Source ---[Parser]--> ParserState --> AnyTarget
-impl<'a, AnyTarget> ParseFrom<Source, &'a Parser<'a>> for AnyTarget
+impl<'a, AnyTarget> ParseFrom<Source, &'a Parser<'_>> for AnyTarget
 where
     // Type `AnyTarget` should be possible to be yielded from `ParseState`
-    AnyTarget: ParseFrom<(), &'a mut ParseState<'a>>,
+    AnyTarget: for<'p> ParseFrom<(), &'p mut ParseState<'a>>,
 {
     /// For all things `ParserState` can yield, it can be parsed from `Source`
     fn parse_from(source: Source, parser: &'a Parser) -> Self {

Rust Playground

You shouldn't have &'a mut ParseState<'a>. It borrows forever.

3 Likes

I'm sorry I forgot to mention my background.
I switched to Rust from Julia/TypeScript, been learning Rust for less than a month, and am currently trying to write some string-DSL parsers as an advanced exercise;
The parser architecture I am currently designing is

  1.   Enter the string input: `&str`
    
  2.   Convert the string into a character array `&[char]`, which is loaded into a special `ParseState` parse state
    
  3.   Call its own method to parse input.        It will change itself in the parsing procedure (so I using `&mut ParseState`)
    
  4.   Extract the field values and produce the parsing result `Target` (there may be multiple `Target` types).
    
  5.   Preserve parsing state to support parsing multiple strings at once (by reusing `ParseState` object)
    

The main reason I encountered this problem was the requirements for the universality of the DSL:

  1.   There are multiple DSL formats to support (the representation in the question is reduced to the field `data` in `ParseState`)
    
  2.   There are multiple type of target objects that need to be output (e.g. a complete DSL statement or a partial expression within it)
    

For the first point, I introduced the data field in ParseState and used &str instead of String for performance reasons
For the second point, I'd like to do something like From::from or str::parse, such as parser.parse::<Target>(input) (internally represented as parser.build_state(input).parse::<Target>())

So I introduced the trait ParseFrom<From, Parser> to implement ParseFrom<&str, Parser> to the Target, which requires a lifetime parameter on the implementation;
Then, I want to unify the resolution of the internal state (specifying the destination to which the state is resolved), but ParseState has no "input type", so I use the unit type () as the input: impl ParseFrom<(), &mut ParseState> for Target. It also need to introduce a lifetime parameter for &mut ParseState

The whole implementation went well, even when implementing ParseFrom<&str, Parser> and ParseFrom<(), ParseState> for specific Target types
But when I try to avoid too much boilerplane code, hoping that "Any type that implements ParseFrom<(), ParseState> automatically implements ParseFrom<&str, Parser>", the lifecycle problem arises by the borrow checker, as described initially in this topic.

Problem solved perfectly, thank you!
I refer to the Rustnomicon of the two articles, discover that I really don't know much about anonymous lifetime parameters '_ and high-level trait bounds for<'a> (HRTB);
Wish I can finally figure them out🙏