Need help fixing a lifetime issue

Right now, I pass each ast node to a new adapter which iterates the rules individually: query engine · u9g/oxc@0d27dfc · GitHub
This works fine but it's incredibly slow to restart the engine and remake each query for every node.

So instead I would like to switch to passing the nodes() iterator: start converting to iterator · u9g/oxc@3068d90 · GitHub

Passed in here: github[.com]/u9g/oxc/commit/3068d9083f051fdf26b29de63b9066ee02548acd#diff-207225884c5e031ffd802bb99e4fbacbd8364b1343a1cec5485bf50f29186300R149 (can't post three links as a new user)

The current error is:

error: lifetime may not live long enough
  --> crates/oxc_linter/src/lint_adapter.rs:39:9
   |
37 | impl<'a> LintAdapter<'a> {
   |      -- lifetime `'a` defined here
38 |     fn get(&self) -> VertexIterator<'a, Vertex> {
   |            - let's call the lifetime of this reference `'1`
39 |         Box::new(self.nodes.nodes().iter().map(|x| Vertex::AstNode(*x.get())))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

In theory, this should work fine, in reality I have no idea how to get an iterator from this Semantic to my adapter in a way that the borrowchecker will compile my code

I didn't want to reproduce all your deps and failed to mock the error, so this will be some indirect advice which will hopefully lead somewhere.

First, I suggest enabling the #![deny(elided_lifetimes_in_paths)] lint to highlight everywhere borrowing is happening. You're eliding some lifetimes of lifetime-carrying structs like Vertex, and scrutinizing what the borrows actually mean in those locations may help.

(I'm assuming you're familiar with normal function lifetime elision rules.)

For example, did you mean this:

-    fn get(&self) -> VertexIterator<'a, Vertex> {
+    fn get(&self) -> VertexIterator<'a, Vertex<'a>> {

And if not, are you getting what you did mean via elision, i.e.:

     fn get(&self) -> VertexIterator<'a, Vertex<'_>> {

Next, I couldn't figure out where the borrow of &self was getting captured in your iterator (which is what the error you posted is saying happens). You might be able to narrow it down some by doing something like this:

impl<'a> LintAdapter<'a> {
    fn get(&self) -> VertexIterator<'a, Vertex<'a>> {
        let nodes: &'a Rc<Semantic<'a>> = self.nodes;
        let nodes: &'a AstNodes<'a> = nodes.nodes();
        let mut iter = nodes.iter(); // opaque, unnameable type
        let _: Option<&'a Node<SemanticNode<'a>>> = iter.next();
        let mut iter = iter.map(|x| Vertex::AstNode(*x.get()));
        let _: Option<Vertex<'a>> = iter.next();
        Box::new(iter)
    }

And seeing which step is making the compiler unhappy.

There's also some implicit derefs in there, like in nodes.iter(), though I don't see how they would matter.

1 Like

Okay, so I added the deny rule. Then I realized I was passing an rc by reference because it was already happening there before I got there but realized that would force me to give the Rc<Semantic<'a>> an annotation in lib.rs so I instead just cloned the Rc and pass the rc directly. Don't pass Rc reference · u9g/oxc@feb6fa7 · GitHub Anyways, onto the debugging step: I added your code (and changed the first let nodes line to instead be Rc<Semantic<'a>> instead of &'a Rc<Semantic<'a>> since that's what we have now, and here's what the problems are

The tooltip suggests I borrow the self.nodes instead so I did, and I again get the same problem now:

error: lifetime may not live long enough
  --> crates/oxc_linter/src/lint_adapter.rs:39:20
   |
37 | impl<'a> LintAdapter<'a> {
   |      -- lifetime `'a` defined here
38 |     fn get(&self) -> VertexIterator<'a, Vertex<'a>> {
   |            - let's call the lifetime of this reference `'1`
39 |         let nodes: &'a Rc<Semantic<'a>> = &self.nodes;
   |                    ^^^^^^^^^^^^^^^^^^^^ type annotation requires that `'1` must outlive `'a`

When you hold a Rc<Semantic<'a>> in Self, it makes sense that you can only get a &'s Semantic<'a> out of self: &'s Self. You only have access to Self for 's. And that limitation will carry forward through all the function calls where the outer reference lifetime is the same as a lifetime in the return. For example Semantic::<'a>::nodes will hand back an &'s AstNodes<'a> because the signature is

pub fn nodes(&self) -> &AstNodes<'a>
// as per lifetime elision rules
// pub fn nodes<'s>(&'s self) -> &'s AstNodes<'a>

When you held a &'a Rc<Semantic<'a>>, you can just copy the &'a Rc<Semantic<'a>> out from behind &'s self, deref can then give you a &'a Semantic<'a>, nodes gives &'a AstNodes<'a>, etc.

(Apparently somewhere in your OP this fell apart at some step anyway, and I was suggesting one way that might help you find out where. With just the Rc and not the reference, you're probably limited to VertexIterator<'_, Vertex<'a>> (or maybe even VertexIterator<'_, Vertex<'_>>).)

Okay, what changes would I have to make to be able to fix this problem? I guess if you’re saying that an Rc isn’t going to work, maybe I should switch to something else? Not sure.

if I make a change to instead take a &'a Rc<Semantic<'a>> On this line: Don't pass Rc reference · u9g/oxc@feb6fa7 · GitHub, then I have to put a &'a annotation on the &Rc<Semantic<'a>> here: Don't pass Rc reference · u9g/oxc@feb6fa7 · GitHub

Unless I'm missing something simple, this requires much deeper changes, this causes an error like this:

error[E0716]: temporary value dropped while borrowed
   --> crates/oxc_cli/src/lint/runner.rs:220:34
    |
220 |         let result = linter.run(&Rc::new(semantic_ret.semantic));
    |                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - temporary value is freed at the end of this statement
    |                                  |
    |                                  creates a temporary value which is freed while still in use
221 |
222 |         if result.is_empty() {
    |            ----------------- borrow later used here
    |
help: consider using a `let` binding to create a longer lived value
    |
220 ~         let binding = Rc::new(semantic_ret.semantic);
221 ~         let result = linter.run(&binding);
    |

which requires changing this line: oxc/crates/oxc_cli/src/lint/runner.rs at feb6fa705fd28e55eb69e47fc708ecfa0885022c · u9g/oxc · GitHub

to instead look like this:

        let binding = Rc::new(semantic_ret.semantic);
        let result = linter.run(&binding);

However, then I get this error:

error[E0597]: `binding` does not live long enough
   --> crates/oxc_cli/src/lint/runner.rs:221:33
    |
220 |         let binding = Rc::new(semantic_ret.semantic);
    |             ------- binding `binding` declared here
221 |         let result = linter.run(&binding);
    |                                 ^^^^^^^^ borrowed value does not live long enough
...
236 |     }
    |     -
    |     |
    |     `binding` dropped here while still borrowed
    |     borrow might be used here, when `ret` is dropped and runs the destructor for type `ParserReturn<'_>`
    |
    = note: values in a scope are dropped in the opposite order they are defined

The fix is

-fn get(&self) -> VertexIterator<'a, Vertex> {
+fn get(&self) -> VertexIterator<'_, Vertex<'a>>

The reason the first parameter on VertexIterator is '_ is that

  • self.nodes.nodes().iter() contains an implicit deref before calling .iter()
  • so a &'lifetime_on_self AstNodes<'a> is genarated and derefs to &'lifetime_on_self Arena<SemanticNode<'a>> rather than &'a Arena<SemanticNode<'a>>

Then there're some type mismatch errors combined with lifetime errors, so you should fix the type mismatch errors first.

I'm mostly poking around the error site. But let's back up, in one of your files I see this:

impl<'a> Adapter<'a> for LintAdapter<'a> {
    type Vertex = Vertex<'a>;

    fn resolve_starting_vertices(
        &self,
        edge_name: &Arc<str>,
        _parameters: &EdgeParameters,
        _resolve_info: &ResolveInfo,
    ) -> VertexIterator<'a, Self::Vertex> {

And Adapter<'a> is some outside trait you don't control. Supporting that trait is the point?

The borrow of 'a in the result has to exist within Self, and not come from the outside borrow of &self in resolve_starting_vertices. So you need a &'a Semantic<'a> or a &'a Rc<Semantic<'a>> or something like that in order to satisfy the signature. (Unless your iterator doesn't capture any borrows somehow.) If you have an owned Rc in Self, you can only borrow it for as long as the &self borrow.

I'm unsure if that's possible within your project or not, and it may depend on things like "is Semantic<'a> covariant in 'a".

Yeah

I think it is? since Semantic will be alive for the lifetime of the struct which should just be the function body?

I get this when I apply that fix:

error: lifetime may not live long enough
  --> crates/oxc_linter/src/lint_adapter.rs:85:9
   |
76 |   impl<'a> Adapter<'a> for LintAdapter<'a> {
   |        -- lifetime `'a` defined here
...
80 |           &self,
   |           - let's call the lifetime of this reference `'1`
...
85 | /         match edge_name.as_ref() {
86 | |             // "Run" => Box::new(std::iter::once(Vertex::AstNode(self.node))),
87 | |             "Run" => self.get(),
88 | |             _ => unimplemented!("unexpected starting edge: {edge_name}"),
89 | |         }
   | |_________^ method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

Then it's a hassle to continue, as quinedot points out

the trait Adapter in trustfall_core::interpreter - Rust is defined as a giving trait, i.e. the return value from the method has no lifetime connection with &self.

It's fine if you can always give out the shared reference via self.field and Splitting Borrows - The Rustonomicon [1]:

fn giving_pattern(&self) -> TypeIrrelevantToRefSelf<'lifetime_on_struct> {
    /* use field expression and split borrows to generate a reference with lifetime_on_struct */
}

But once you call a lending method, a method in the form of <'_self>(&'_self self, ...) -> TypeTiedToRefSelf<'_self>, in the middle of giving methods, a local reference with maximum '_self lifetime or shorter (like via Deref trait) is yielded, then you'll never get 'lifetime_on_struct afterwards.


  1. or via unsafe code like Iter in std::slice - Rust ↩︎

1 Like

Haha I really hacked it up, I just ended up patching indextree to make their internal nodes vec public, which I then clone and run .into_iter on. Now, I can call it a day and my code goes from 10s to 8ms :))))

I really wish that indextree would provide a "blessed" solution for this, but since they don't and it's been literal days without making any progress on this, I don't care anymore.

Thanks for all the help everyone but in the end everyone basically told me it's not possible lol

Based on this commit:

After looking back this lifetime problem for several times, I found the solution for OP is

 impl<'a> LintAdapter<'a> {
     fn get(&self) -> VertexIterator<'a, Vertex<'a>> {
-        Box::new(self.nodes.nodes().iter().map(|x| Vertex::AstNode(*x.get())))
+        let ast: &indextree::Arena<SemanticNode<'a>> = self.nodes.nodes();
+        let nodes: Vec<Vertex<'a>> = ast.iter().map(|x| Vertex::AstNode(*x.get())).collect();
+        Box::new(nodes.into_iter())
     }
 }

or one line solution

-Box::new(self.nodes.nodes().iter().map(|x| Vertex::AstNode(*x.get())))
+Box::new(self.nodes.nodes().iter().map(|x| Vertex::AstNode(*x.get())).collect::<Vec<_>>().into_iter())

then all the code in repo compiles [1].


The pattern can be summarized as: Rust Playground

struct S<'s>(Vec<&'s str>);
impl<'s> S<'s> {
    // error: lifetime may not live long enough
    // method was supposed to return data with lifetime `'s` 
    // but it is returning data with lifetime `'1`
    // fn f(&self) -> Box<dyn 's + Iterator<Item = E<'s>>> {
    //     Box::new(self.0.iter() /* lending */ .map(|s| E::V(s)))
    // }
    fn fix(&self) -> Box<dyn 's + Iterator<Item = E<'s>>> {
        Box::new(self.0.clone() /* giving */ .into_iter().map(|s| E::V(s)))
    }
} 

enum E<'s> {
    V(&'s str)
}

The key is to get rid of lending patterns (in Deref::deref and Arena::iter) by providing an owned type before the return type, thus fn get(&self) -> VertexIterator<'a, Vertex<'a>> can be a giving pattern as expected.


  1. plus elided_lifetimes_in_paths lint should be disabled in crates/oxc_linter/src/lib.rs first ↩︎

2 Likes

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.