Lifetime issues when parsing multi-file programs

[jimmycuadra]

I'm trying to write a recursive function called check that lexes and parses a program written across multiple files. The logical flow is:

1. check is called with the path to the entry source file, its source code as a &str, and a hash map used to track the output of the parser for each file in the program.
2. The source is lexed to produce tokens of type Token<'src>.
3. The tokens are parsed to produce AST nodes of type Item<'tokens>. "Item" is an enum and is the same thing as it is in Rust: a top-level declaration.
4. The items of the parsed file are iterated to check for ones representing imports from other files. For each import detected, its source file is read from the file system, and then check is called recursively.

Because Token borrows from the &str input and Item borrows from Token, I'm running into lifetime issues with this pattern. Here's what the function looks like, though some of the details here aren't related to the core problem (specifically, ignore the error handling and the input_file_parent parameter/usage):

pub fn check<'tokens, 'src: 'tokens>(
    input_file: &Path,
    input_file_parent: Option<&Path>,
    source: &'src str,
    mut modules: HashMap<PathBuf, Vec<Item<'tokens>>>,
) -> Result<HashMap<PathBuf, Vec<Item<'tokens>>>, String> {
    let (maybe_tokens, lex_errors) = crate::lexer().parse(source).into_output_errors();

    let parse_errors = if let Some(tokens) = maybe_tokens {
        let (maybe_items, parse_errors) = crate::parser(crate::make_input)
            .parse(crate::make_input((0..source.len()).into(), &tokens))
            .into_output_errors();

        if let Some(items) = maybe_items {
            for item in &items {
                if let Item::Use(item_use) = item
                    && !item_use.is_self_module()
                    && !item_use.is_std_module()
                {
                    let input_file = item_use.file_path(input_file_parent);
                    let source =
                        std::fs::read_to_string(&input_file).map_err(|error| error.to_string())?;

                    modules = check(
                        &input_file,
                        input_file_parent,
                        &source,
                        modules,
                    )?;
                }
            }

            if !modules.contains_key(input_file) {
                modules.insert(input_file.to_path_buf(), items);
            }

            return Ok(modules);
        }

        parse_errors
    } else {
        Vec::new()
    };

    Err(lex_errors
        .into_iter()
        .map(|lex_error| lex_error.to_string())
        .chain(
            parse_errors
                .into_iter()
                .map(|parse_error| parse_error.to_string()),
        )
        .collect())
}

This results in the following compiler errors:

error[E0597]: `tokens` does not live long enough
   --> src/module.rs:172:64
    |
162 | pub fn check<'tokens, 'src: 'tokens>(
    |              ------- lifetime `'tokens` defined here
...
170 |     let parse_errors = if let Some(tokens) = maybe_tokens {
    |                                    ------ binding `tokens` declared here
171 |         let (maybe_items, parse_errors) = crate::parser(crate::make_input)
172 |             .parse(crate::make_input((0..source.len()).into(), &tokens))
    |                                                                ^^^^^^^ borrowed value does not live long enough
...
195 |                 modules.insert(input_file.to_path_buf(), items);
    |                 ----------------------------------------------- argument requires that `tokens` is borrowed for `'tokens`
...
202 |     } else {
    |     - `tokens` dropped here while still borrowed

error[E0597]: `source` does not live long enough
   --> src/module.rs:188:25
    |
162 | pub fn check<'tokens, 'src: 'tokens>(
    |              ------- lifetime `'tokens` defined here
...
182 |                     let source =
    |                         ------ binding `source` declared here
...
185 |                     modules = check(
    |                     ------- assignment requires that `source` is borrowed for `'tokens`
...
188 |                         &source,
    |                         ^^^^^^^ borrowed value does not live long enough
...
191 |                 }
    |                 - `source` dropped here while still borrowed

For more information about this error, try `rustc --explain E0597`.

Both of these errors make sense to me and are really just standard Rust stuff: I can't return AST nodes referencing tokens that are local to the function, and I can't return tokens that reference the contents of the additional files read while looping through each file's AST. But I can't read all the files before lexing/parsing each one, because I only know which files need to be read by inspecting the AST of the previous files.

I've tried a few approaches to solve this problem. I've tried storing the source of each file in a structure owned by the function that initially calls check so that they all outlive the tokens/nodes generated from them, but ultimately, the Chumsky parsers operate on borrowed values as input, so I end up with the same problem no matter how I get them into scope within check.

I even went so far as to do a massive change across my whole compiler to make Token and Item values that don't borrow anything. I wasn't able to get that to compile, and it boiled down to the make_input function as discussed in #891:

#[must_use]
pub fn make_input<'a>(
    eoi: SimpleSpan,
    tokens: &'a [Spanned<Token<'a>>],
) -> impl BorrowInput<'a, Token = Token<'a>, Span = SimpleSpan> {
    tokens.map(eoi, |(token, span)| (token, span))
}

I couldn't figure out how to create an "owned" version of this, and kept getting:

error[E0515]: cannot return value referencing function parameter `tokens`
   --> src/ast.rs:169:5
    |
169 |     tokens.map(eoi, |(token, span)| (token, span))
    |     ------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |     |
    |     returns a value referencing data owned by the current function
    |     `tokens` is borrowed here

For more information about this error, try `rustc --explain E0515`.

Anyway, I assume I was going down the wrong path by trying to make all the lexer/parser output non-borrowing anyway. Surely there's a good reason why all the Chumsky examples use tokens and nodes that borrow from their inputs.

Any suggestions on how to lex and parse multi-file programs like this? I can provide more code if what I showed here doesn't give enough context.

[zesterer]

Why does check need to have the lifetime 'tokens in its signature at all? The lifetime of the tokens exists entirely within the function body and doesn't escape it. Maybe you're getting it mixed up with the 'src lifetime?

[Zij-IT]

Gah! My bad. This is what I get for following along on mobile. Anywhoodles!

Your signature shortens the lifetime of the tokens to the borrow of the token slice.

Try:

pub fn make_input<'a, 'b>(
    eoi: SimpleSpan,
    tokens: &'b [Spanned<Token<'a>>],
) -> impl BorrowInput<'b, Token = Token<'a>, Span = SimpleSpan> {
    tokens.map(eoi, |(token, span)| (token, span))
}

The idea here is that we retain that tokens have the lifetime of the source &str/&[u8] and that this new borrowed input spits out these tokens.

[jimmycuadra]

I still get the same two errors using that signature, but at least it doesn't introduce new errors. 😄

Would it be useful if try to get a minimal reproduction I can share in a Gist?

[jimmycuadra]

Here's a minimal reproduction of the errors: https://gist.github.com/jimmycuadra/ecde3940045a544fcc219b990697706d

[zesterer]

So, interestingly, neither of these errors really has anything to do with chumsky (sort of).

One of the lifetime errors you're seeing is pointing at a real problem. Take a look at the following code:

if let Item::Use(item_use) = item {
    let input_file = PathBuf::from(item_use.file_path);
    let source =
        std::fs::read_to_string(&input_file).map_err(|error| error.to_string())?;

    modules = check(&input_file, &source, modules)?;
}

Here, you load the contents of a file into a String, source. You then call check, which returns Result<HashMap<PathBuf, Vec<Item<'src>>>, String>. Note that this type contains the 'src lifetime, which only lives as long as source! But source gets dropped at the end of the if let block, so the hashmap being assigned to modules can't be permitted to outlive it because it refers to source.

Hence, the following error:

error[E0597]: `source` does not live long enough
  --> src/main.rs:89:50
   |
69 | pub fn check<'src>(
   |              ---- lifetime `'src` defined here
...
86 |                     let source =
   |                         ------ binding `source` declared here
...
89 |                     modules = check(&input_file, &source, modules)?;
   |                     -------                      ^^^^^^^ borrowed value does not live long enough
   |                     |
   |                     assignment requires that `source` is borrowed for `'src`
90 |                 }
   |                 - `source` dropped here while still borrowed

This isn't a phantom: this code would contain UB if it were allowed to compile because the file_path field would be pointing at a string that's already been dropped. What solution you choose to use is up to you, but I would personally suggest the simplest option: make the ItemUse type self-owning, since the design of your compiler as-is doesn't allow the source code to outlive the tokens that refer to it anyway:

struct ItemUse {
    file_path: String,
}

The second error you're seeing looks like this:

error[E0597]: `tokens` does not live long enough
   --> src/main.rs:78:57
    |
 76 |     let parse_errors = if let Some(tokens) = maybe_tokens {
    |         ------------               ------ binding `tokens` declared here
    |         |
    |         borrow later stored here
 77 |         let (maybe_items, parse_errors) = parser(make_input)
 78 |             .parse(make_input((0..source.len()).into(), &tokens))
    |                                                         ^^^^^^^ borrowed value does not live long enough
...
101 |     } else {
    |     - `tokens` dropped here while still borrowed

It's complaining because the parse_errors being returned from the if let outlive the thing they refer to: the tokens vector, which gets dropped at the end of the if let. Why do the parse_errors refer to the token vector? Because chumsky tries its best to avoid allocating unnecessarily, and one of the ways it does this is by having Rich reference the input.

But thankfully, there's a solution to this. Chumsky provides a Rich::into_owned method for this very purpose which allows you to clone away the internal references, making the Rich error self-owned, and allowing it to outlive the token input. You can do that like this:

let parse_errors = if let Some(tokens) = maybe_tokens {
    ...

    // Make each error self-owned, then re-collect into a vector again
    parse_errors.into_iter().map(|err| err.into_owned()).collect()
} else {
    Vec::new()
};

For completeness, here's a working version of your code (I also gave the lifetime parameters more explicit names, mostly for my own sake; but I think it helps): https://gist.github.com/zesterer/e739b118be8a9f1dc357ae5974e97148

[jimmycuadra]

Thanks! I understood that the core of the first error was that I was trying to return Items which held references to the source String that was being dropped. This is why I made the pain-staking attempt to redo my entire compiler so that both Item (and the Expr expressions they are made up of) were entirely owned values with no lifetime parameters. But that's where I got stuck on the make_input error I mentioned in my original post. I couldn't figure out a way to make a version of that function that worked with owned values.

I feel like it might also be possible using Rc rather than static references. But then Parser::parse would have to accept Rc<T> as input in addition to &str/&[T]/etc.

[zesterer]

Yeah, it all starts to get funky. If you're really, really desperate to avoid owned values then I'd highly recommend that you look into string interning. Either the internment crate or the lasso crate are good (or you can DIY it - good fun too!). That'll give you the performance you want (in fact, it's often much better due to cheaper comparisons!), but without the lifetime pain.

[jimmycuadra]

I actually think it would be nicer to use owned values for my AST if I could get a working equivalent to make_input. Is there nothing that can be done there? I still find that technique to be the hardest thing to understand using Chumsky. This is twice now I've been kinda stumped by it. 😩 I'm not sure string interning will make a difference cause I'll still need a version ofmake_input that works with owned values.

[zesterer]

There actually is! Just the other day I merged a change that makes working with nested, non-trivial inputs much cleaner. Take a look at what it did to the nested_spans.rs example: https://github.com/zesterer/chumsky/pull/915/files#diff-c77f103c34622aebc3cf8d2dd9df6d53d9224ce174da0fbc3dc2c961de44bc1c