What's the best way to debug a lifetime issue?

I appear to have painted myself into a corner. I'm running into a lifetime issue and I don't know that I have the right tools to figure it out. I'm first-and-foremost interested in how people go about solving lifetime issues like this, and secondly interested in help with this particular issue.

The instigating issue

I have a little prefix tree structure that lets you query the subtree for some given prefix. It currently returns this subtree as a Vec<PathAndValue<Token, Value>> where PathAndValue<Token, Value> has the path (as a Vec<&Token>) to the given node in the subtree and value is the value stored at said node.

pub struct PathAndValue<'path, 'value, Token, Value> {
    pub path: Vec<&'path Token>,
    pub value: &'value Value,
}

struct PrefixTree<Token, Value> {
    t: std::marker::PhantomData<Token>,
    v: std::marker::PhantomData<Value>,
}

impl<Token, Value> PrefixTree<Token, Value> {
    // ...
    pub fn find_by_prefix<'this, 'prefix, 'return_path, 'return_value, 'tokens, 'node>(
        &'this self,
        _prefix: &'prefix [Token],
    ) -> Vec<PathAndValue<'return_path, 'return_value, Token, Value>>
    where
        'this: 'return_path,
        'this: 'return_value,
        'this: 'tokens,
        'this: 'node,
        'tokens: 'return_path,
        'node: 'return_value,
        'node: 'return_path,
    {
        todo!()
    }
    // ...
}

The prefix used to query should have a wholly independent lifetime to that of the returned PathAndValues, allowing for consumers to create short-lived prefixes and pass around the resulting sub-tree.

In a consuming struct, I have an issue where the lifetime of the prefix is somehow needing to outlive part of my returned subtree.


struct Consumer {
    tree: PrefixTree<&'static str, Box<()>>,
}

impl Consumer {
    // The result of this often outlives `path` as it is dynamically constructed in
    // a wrapper/helper but the results are passed out.
    pub fn list_subtree<'this, 'path, 'arg_tokens, 'return_path, 'return_value, 'stored_tokens>(
        &'this self,
        path: &'path [&'arg_tokens str],
    ) -> Vec<PathAndValue<'return_path, 'return_value, &'stored_tokens str, Box<()>>>
    where
        'this: 'return_path,
        'this: 'return_value,
        'this: 'stored_tokens,
        'stored_tokens: 'return_path,
    {
        self.tree.find_by_prefix(path)
    }
}

You can try to build this code on the Rust Playground.

So, yeah... how should I try understanding what I'm doing wrong? What tools do y'all use to debug lifetime issues like this?

There are so many lifetime parameters here… too many lifetime parameters. This signature for example

impl<Token, Value> PrefixTree<Token, Value> {
    pub fn find_by_prefix<'this, 'prefix, 'return_path, 'return_value, 'tokens, 'node>(
        &'this self,
        _prefix: &'prefix [Token],
    ) -> Vec<PathAndValue<'return_path, 'return_value, Token, Value>>
    where
        'this: 'return_path,
        'this: 'return_value,
        'this: 'tokens,
        'this: 'node,
        'tokens: 'return_path,
        'node: 'return_value,
        'node: 'return_path,
    { … }
}

The lifetime 'node doesn’t even appear in any of the input or output types, and the transitive outlive relations from

        'this: 'node,
        'node: 'return_value,
        'node: 'return_path,

namely

        'this: 'return_value,
        'this: 'return_path,

are already present.

The same is true for 'tokens.

impl<Token, Value> PrefixTree<Token, Value> {
    pub fn find_by_prefix<'this, 'prefix, 'return_path, 'return_value>(
        &'this self,
        _prefix: &'prefix [Token],
    ) -> Vec<PathAndValue<'return_path, 'return_value, Token, Value>>
    where
        'this: 'return_path,
        'this: 'return_value,
    { … }
}

Due to the covariance of the output type PathAndValue in its lifetimes, the generalization of the signature to differentiate 'this from 'return_path and 'return_value is unnecessary. Callers can always subsequently (implicitly) coerce a Vec<PathAndValue<'this, 'this, Token, Value>> further into something like Vec<PathAndValue<'return_path, 'return_value, Token, Value>> if they need to.

impl<Token, Value> PrefixTree<Token, Value> {
    pub fn find_by_prefix<'this, 'prefix>(
        &'this self,
        _prefix: &'prefix [Token],
    ) -> Vec<PathAndValue<'this, 'this, Token, Value>>
    { … }
}

Now, this signature has become fairly standard – in facto so standard that it perfectly fits lifetime elision rules (under which elided lifetimes in a return type relate to the lifetime of self)

impl<Token, Value> PrefixTree<Token, Value> {
    pub fn find_by_prefix(&self, _prefix: &[Token]) -> Vec<PathAndValue<'_, '_, Token, Value>> {
        …
    }
}

In any case, I’d say the approach I’m following here is removing unnecessary complexity to make the situation easier to understand. (If you aren’t deeply familiar with elision rules, it’s perfectly fine not to go the last step, or even go the last step in reverse to make code that used to have elided lifetimes easier to understand.)


Of course, I’ll do the same to list_subtrees, replacing all those return type lifetimes just with 'this

impl Consumer {
    // The result of this often outlives `path` as it is dynamically constructed in
    // a wrapper/helper but the results are passed out.
    pub fn list_subtree<'this, 'path, 'arg_tokens>(
        &'this self,
        path: &'path [&'arg_tokens str],
    ) -> Vec<PathAndValue<'this, 'this, &'this str, Box<()>>>
    {
        self.tree.find_by_prefix(path)
    }
}

Anyways, let’s look at the actual error message now that the code is somwhar digestable

error: lifetime may not live long enough
  --> src/lib.rs:29:9
   |
24 |     pub fn list_subtree<'this, 'path, 'arg_tokens>(
   |                         -----         ----------- lifetime `'arg_tokens` defined here
   |                         |
   |                         lifetime `'this` defined here
...
29 |         self.tree.find_by_prefix(path)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ method was supposed to return data with lifetime `'this` but it is returning data with lifetime `'arg_tokens`
   |
   = help: consider adding the following bound: `'arg_tokens: 'this`

Alright, we’re seeing it complain about 'arg_tokens. And the call is to find_by_prefix.

Initially I’m thinking: 'arg_tokens is part of the type of path: &'path [&'arg_tokens str], and passed to find_by_prefix as the argument _prefix: &[Token]. There were no lifetime restrictions on that argument, so why the error?

Immediately, on second look I can notice that 'arg_tokens becomes part of the Token type. For the function call, we need to unify types… the type

&'path [&'arg_tokens str]

must match

&[Token]

so

&'arg_tokens str

must match

Token

Naively, this means that Token and &'arg_tokens str would need to be the same type. However, we’ll also need to consider covariance, so lifetimes can become shorter.

The type of self.tree is PrefixTree<&'static str, Box<()>>, so Token would be &'static str. For the call to list_subtree one might thus assume that &'arg_tokens str needs to coerce into Token == &'static str, though that’s ignoring that the value &self.tree itself can be coerced, too, before the method call to list_subtree.

So &self.tree is of some type &'lifetime_1 PrefixTree<&'static str, Box<()>>, but can coerce to any type &'lifetime_1 PrefixTree<&'lifetime_2 str, Box<()>> with 'lifetime_2: 'lifetime_1. Then the list_subtree call happens with Tokens == &'lifetime_2 str, and &'arg_tokens str need to coerce to this which gives the restriction 'arg_tokens: 'lifetime_2. Ultimately, that returns a Vec<PathAndValue<'lifetime_1, 'lifetime_1, &'lifetime_2 str, Box<()>>> (which is the return type Vec<PathAndValue<'_, '_, Token, Value>> with the right lifetimes and types substituted in) and we want to return Vec<PathAndValue<'this, 'this, &'this str, Box<()>>>.

So some lifetimes reasoning / reasoning about coercions can be useful. This not makes me realize I may have over-“simplified” your signature here… there’s no reason for 'this in the &'this str return type if that just turns out to demand “too much”. Since – before coercions – this &'stored_tokens str was going to be the Tokens type, &'arg_tokens str anyways, let’s fix that, and the signature that results compiles without issues.

impl Consumer {
    pub fn list_subtree<'this, 'path, 'arg_tokens>(
        &'this self,
        path: &'path [&'arg_tokens str],
    ) -> Vec<PathAndValue<'this, 'this, &'arg_tokens str, Box<()>>>
    {
        self.tree.find_by_prefix(path)
    }
}

Once again, we can go further and make use of elision to arrive at something like

impl Consumer {
    pub fn list_subtree<'tok>(
        &self,
        path: &[&'tok str],
    ) -> Vec<PathAndValue<'_, '_, &'tok str, Box<()>>> {
        self.tree.find_by_prefix(path)
    }
}

Rust Playground

On that note, if there isn’t a good reason for it to stay separate, the two lifetimes 'path, 'value on PathAndValue could possibly also be unified, but whether or not that works depends on whether there’s any API that perhaps, unlike find_by_prefix, returns actually distinct borrows there.


Now that I’ve gone through this error, it appears to me that there wasn’t the whole picture presented.

On one hand, I’m not sure what exactly is meant by your comment that

The result of Consumer::list_subtree often outlives path as it is dynamically constructed in a wrapper/helper but the results are passed out.

Does this “outlives path” include outliving the &strs contained within? Or just the slice? If it’s the former, no wonder there are problems, as your PrefixTree::find_by_prefix does take the Token type from its _prefix argument.

On the other hand, the compiler, even in your overly lifetime-parameter-heavy version of the code does give out a precise hint as for what lifetimes relation was missing:

help: consider adding the following bound: `'arg_tokens: 'return_path`

so I suppose there must be reasons why you weren’t simply able to apply this (and the two subsequent outlives relations that follow… 'arg_tokens: 'return_value and 'arg_tokens: 'stored_tokens, the latter of which even makes the 'arg_tokens: 'return_value constraint redundant again).

Re-reading your question now that I’ve looked at the code…

You seem not to like the 'arg_tokens: 'return_path bound the compiler suggested. First of all, my answer above does nothing to change that. It features fewer explicit lifetimes and no explicit outlives relations but the implicit ones still stand.

In your original code, the return type PathAndValue<'return_path, 'return_value, &'stored_tokens str, Box<()> contains a value of type Vec<&'return_path &'stored_tokens str> in the PathAndValue field called path. This results in an implicit 'stored_tokens: 'return_path requirement which can even imply 'arg_tokens: 'return_path, once we’ve established that 'stored_tokens bust re-borrow from 'arg_tokens, i.e. 'arg_tokens: 'stored_tokens.

And my “simplified” version of the code still features the same implicit bound, this time it’s 'arg_tokens: 'this in the return type Vec<PathAndValue<'this, 'this, &'arg_tokens str, Box<()>>>. (I’m looking at the elision-free version of the code, so that the lifetimes have names.)

If these liftime connections turn out to be problematic in your use-case, please provide more context. Also in that case, the signatures would need to be seriously re-worked as the lifetime relationships in question come not from the lifetimes in find_by_prefix’s signature, but merely from the fact that the same Token type is used in the _prefix parameter and the Vec<PathAndValue<'return_path, 'return_value, Token, Value>> return type.

@steffahn, thank you for your extensive answers!

For some context: the excessive lifetimes, as presented, were not where I started. I expanded out all lifetimes used internally to my actual implementation. Expanding every lifetime helps me grok what the actual relationships are and pin down where the ultimate issue is. I chose to leave them in the shared version in large part to try and communicate the semantic relationships between the various lifetimes present.

This expansion from the "simple" lifetime form (both elided and inferred via '_) is one of the few tools I have in my arsenal for lifetime-issues.

To the question of the compiler's demands of 'arg_tokens: 'return_path, I very much can't live with this. The returned subtree almost always outlives the path parameter passed in.

To clarify: the parameter passed in is not involved in the memory that is returned and so a constraint of 'arg_tokens: 'return_path is semantically incorrect. Further, defining any relationship between 'arg_tokens and 'return_path is semantically incorrect... they're wholly independent.

What I'm hearing in your replies is that the Token type is explicitly resolving in such a way as the returned generic type of Token must match (including lifetimes) the query parameter's Token type. In turn, this forces 'stored_tokens to equal 'arg_tokens when these are very much not the same.

This makes some sense... but is not something I had considered.

How would you suggest I explicitly differentiate the demands on these types? Naively I'd imagine this would require breaking Token into some QueryToken and OutputToken generic type parameters.... Off the top of my head, I don't quite know how to restrict QueryToken and OutputToken so that they are forced to be the same type "below the reference". Note that these types are not always references and can be value types (think a Token of String) as well.

Ah, that’s somewhat reassuring to hear. So it’s not some crazy coding style I’ll need to criticise :sweat_smile:

Hard to say… presumably somewhat via traits. More context might be useful here. E.g. you could list some other examples of Token types that you use. Do they all involve lifetimes or only few of them? If you want to return the &str tokens, who does own them if they aren’t copies / re-borrows of the original &'arg_tokens str tokens? Is the PrefixTree::find_by_prefix signature simply more restrictive than its implementation? It seems overly general anyways, I presume you put some kind of trait bounds on Token to do something useful to them?

Like assuming it’s something like Token: Eq, and you merely compare the tokens from _prefix with ==, yeah I can see why its overly restricting to make Token == &str require the &str’s to have equal types. To stay in this analogy/example then, something like PrefixToken as a separate type with a trait bound such as Token: Partial<PrefixToken> would allow == comparisons more heterogeniously.

Or if (most or) all Tokens require lifetimes anyways, and you have some custom trait bounds, then you could even consider adding a GAT. If I had (to stay within the Eq analogy something like this to start out

trait MyTraitLikeEq {
    fn eq(&self, other: &Self) -> bool;
}

then one possible alternative with GATs look as follows

trait MyTraitLikeEq {
    type WithShorterLifetime<'a>;
    fn eq(&self, other: &Self::WithShorterLifetime<'_>) -> bool;
}
// some non-lifetime-bearing impl
impl MyTraitLikeEq for i32 {
    type WithShorterLifetime<'a> = i32;
    fn eq(&self, other: &i32) -> bool {
        *self == *other
    } 
}
// some ifetime-bearing impl
impl MyTraitLikeEq for &str {
    type WithShorterLifetime<'a> = &'a str;
    fn eq(&self, other: &&str) -> bool {
        *self == *other
    } 
}

with

_prefix: &'prefix [Token::WithShorterLifetime<'_>]

@steffahn's replies are generally superb, but I didn't read them before writing this up, so there may be some significant overlap.


The thing about that context with the OP question...

...is that adding excessive lifetimes is counter to how I would go about solving whatever the original borrow error actually was. Showing what your code looked like when the error first popped up might lead to a better discussion on "how one solves this".

I can walk backwards from the excessive situation though, I suppose.

First when I see this:

pub struct PathAndValue<'path, 'value, Token, Value> {
    pub path: Vec<&'path Token>,
    pub value: &'value Value,
}

Both those lifetimes are covariant (can be implicitly shrunk), and usually you can get away with just having a single lifetime in your struct when they're all covariant. But I would go ahead and leave them both in to start. Next we have

impl<Token, Value> PrefixTree<Token, Value> {
    // ...
    pub fn find_by_prefix<'this, 'prefix, 'return_path, 'return_value, 'tokens, 'node>(
        &'this self,
        _prefix: &'prefix [Token],
    ) -> Vec<PathAndValue<'return_path, 'return_value, Token, Value>>
    where
        'this: 'return_path,
        'this: 'return_value,
        'this: 'tokens,
        'this: 'node,
        'tokens: 'return_path,
        'node: 'return_value,
        'node: 'return_path,
    {
        todo!()
    }
    // ...
}

It's hard to say what exactly is desired here from the code alone, because todo!() tells me nothing about what might borrow from what. However, we see that 'tokens and 'nodes are neither inputs nor outputs to the method, and are thus superfluous. Getting rid of them is already a good start:

    pub fn find_by_prefix<'this, 'prefix, 'return_path, 'return_value>(
        &'this self,
        _prefix: &'prefix [Token],
    ) -> Vec<PathAndValue<'return_path, 'return_value, Token, Value>>
    where
        'this: 'return_path,
        'this: 'return_value,

And it seems from what's left that prefix is an input lifetime only, and the two output lifetimes can only be related to 'this. Reading your prose instead of the code confirms this:

So the next simplification is to just get rid of 'prefix...

    pub fn find_by_prefix<'this, 'return_path, 'return_value>(
        &'this self,
        _prefix: &[Token],
    ) -> Vec<PathAndValue<'return_path, 'return_value, Token, Value>>
    where
        'this: 'return_path,
        'this: 'return_value,

...however being explicit about the covariance of the input and output lifetimes doesn't actually gain you much in this situation. If I were writing this myself I probably would have written it like so...

    pub fn find_by_prefix<'this>(
        &'this self,
        _prefix: &[Token],
    ) -> Vec<PathAndValue<'this, 'this, Token, Value>> {
        todo!()
    }

...however there are certain circumstances (like naming the output type as a generic type parameter) where being explicit about the ability of the lifetimes to differ can matter, so I'll leave the three lifetime version as it is for now and move on.

Now we're ready to look at the code that produces an error:

impl Consumer {
    // The result of this often outlives `path` as it is dynamically constructed in
    // a wrapper/helper but the results are passed out.
    pub fn list_subtree<'this, 'path, 'arg_tokens, 'return_path, 'return_value, 'stored_tokens>(
        &'this self,
        path: &'path [&'arg_tokens str],
    ) -> Vec<PathAndValue<'return_path, 'return_value, &'stored_tokens str, Box<()>>>
    where
        'this: 'return_path,
        'this: 'return_value,
        'this: 'stored_tokens,
        'stored_tokens: 'return_path,
    {
        self.tree.find_by_prefix(path)
    }
}

The relationships can also be expressed as

// made-up transitive outlives syntax
'this: 'stored_tokens: 'return_path,
'this:                 'return_value,

So we have the same "borrows of 'this" pattern as above, with a third lifetime 'stored_tokens... but you want 'stored_tokens to be at least as long as 'return_path for some reason. (Reacting to a previous error?)

There's no relationships stated for 'path and 'arg_tokens, and they don't appear in the output type, so if this signature was workable, they could be deleted similar to what we saw with the first method.

But there's an error about 'arg_tokens:

error: lifetime may not live long enough
  --> src/lib.rs:41:9
   |
31 |     pub fn list_subtree<'this, 'path, 'arg_tokens, 'return_path, 'return_value, 'stored_tokens>(
   |                                       -----------  ------------ lifetime `'return_path` defined here
   |                                       |
   |                                       lifetime `'arg_tokens` defined here
...
41 |         self.tree.find_by_prefix(path)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ method was supposed to return data with lifetime `'return_path` but it is returning data with lifetime `'arg_tokens`
   |
   = help: consider adding the following bound: `'arg_tokens: 'return_path`

What role does 'arg_tokens play? It (or a shorter reborrow) is what you pass as a Token. And the Token of the output is 'stored_tokens. From this I would guess that the intended signature was actually:

    pub fn list_subtree<'this, 'arg_tokens, 'return_path, 'return_value, 'stored_tokens>(
        &'this self,
        path: &[&'arg_tokens str],
    ) -> Vec<PathAndValue<'return_path, 'return_value, &'stored_tokens str, Box<()>>>
    where
        'this: 'return_path,
        'this: 'return_value,
        'arg_tokens: 'stored_tokens,

And unlike the case where there are two returned reborrows that may differ, there is only one returned borrow of 'arg_tokens -- it's 'stored_tokens -- and there's even less likelihood that making the covariance explicit is going to help (especially here at the leaf of the current problem). So I will go with this instead:

    pub fn list_subtree<'this, 'arg_tokens, 'return_path, 'return_value>(
        &'this self,
        path: &[&'arg_tokens str],
    ) -> Vec<PathAndValue<'return_path, 'return_value, &'arg_tokens str, Box<()>>>
    where
        'this: 'return_path,
        'this: 'return_value,

Yet the error remains, which is where, IMO, things get interesting.


So let's begin again, with this as the starting point. The error is now:

error: lifetime may not live long enough
  --> src/lib.rs:39:9
   |
31 |     pub fn list_subtree<'this, 'arg_tokens, 'return_path, 'return_value>(
   |                                -----------                ------------- lifetime `'return_value` defined here
   |                                |
   |                                lifetime `'arg_tokens` defined here
...
39 |         self.tree.find_by_prefix(path)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ method was supposed to return data with lifetime `'return_value` but it is returning data with lifetime `'arg_tokens`
   |
   = help: consider adding the following bound: `'arg_tokens: 'return_value`

And this does seem pretty odd. To get to the root of the problem, we need to look at the return type in more detail:

pub struct PathAndValue<'path, 'value, Token, Value> {
    pub path: Vec<&'path Token>,
    pub value: &'value Value,
}
// made up syntax
with
    Token = &'arg_tokens str,
    Value = Box<()>,
    'path = 'return_path,
    'value = 'return_value,

There are actually some inferred bounds at play here, which the borrow checker can make use of and impose on your APIs: Token: 'path and Value: 'value. They are inferred from your field types, because a referenced type must always be valid where the lifetime of the reference is valid. These bounds used to have to be declared on the struct (and all its usage sites) like so:

pub struct PathAndValue<'path, 'value, Token: 'path, Value: 'value>

But you don't have to do that anymore because it's simpler... at least until it becomes relevant and you have to learn about them anyway.

In terms of the return type, this means there are actually some other implied bounds:

    &'arg_tokens str: 'path,
    Box<()>: 'value,

The latter is trivially satisfied for any lifetime 'value, but the former implies

'arg_tokens: 'path // = 'return_path

So back at the error site we actually have:

'this:       'return_path + 'return_value,
'arg_tokens: 'return_path,

And the compiler wants us to make this:

'this:       'return_path + 'return_value,
'arg_tokens: 'return_path + 'return_value,

Adding that bound does indeed allow things to compile. So there must be some problem when 'return_value is a lifetime which is not contained within 'arg_tokens.

If we look at the call we're making:

        self.tree.find_by_prefix(path)

We[1]

  • want a Vec<PathAndValue<'r_path, 'r_value, &'arg_tokens str, Box<()>>
  • so we call PrefixTree::<&'arg_tokens str, Box<()>>::find_by_prefix(...)
    • this is possible due to covariance of the PrefixTree<&'static str, _> field
  • with a borrow of the PrefixTree -- call it 't2 -- that must be less than 'this
    • but must contain 'r_path and 'r_value
    • in practice this will be the union of 'r_path and 'r_value

What happens when 'r_value is not contained in 'arg_tokens? Then 't2 must also be valid for all of 'r_value, including the parts not contained in 'arg_tokens. But then this means we have a

&'t2 self = &'t2 PrefixTree<&'arg_tokens str, Box<()>>

Where the outer lifetime 't2 is valid in some regions where the inner reference &'arg_tokens str is not valid.

This is UB in Rust, and thus never allowed in safe code and never what you want in any code.

That's the source of the borrow error.


Set relations are a pain to draw in text, but with all rectangular lifetimes when the error is present, we have:

+----------------------------+
| 'arg_tokens                |
|                            |
|          +-----------------+--------------+
|          |                 |              |
|          |    +----------+ |              |
|          |    | 'r_p     | |              |
|          |    |      +---+-+------+       |
|          |    |      |   | |      |       |
|          |    +------+---+ |      |       |
|          |           |     |      |       |
+----------+-----------+-----+      |       |
           |           |       'r_v |       |
           |           +------------+       |
           |                          'this |
           +--------------------------------+

And the problem is when the union of 'r_v and 'r_p is not contained in 'arg_tokens.[2] Adding 'arg_tokens: 'return_value as the compiler suggested does indeed remove that problem. Other bounds you could add which are notionally (but perhaps not practically) more restrictive include

  • 'return_path: 'return_value
  • 'arg_tokens: 'this

Or even

  • 'return_path: 'this
    • AKA 'this = 'return_path becuase we already have 'this: 'return_path

As this forces 'return_value to also be contained in 'return_path (which is contained in 'arg_tokens).


Given that last observation, what happens when we give up on the notionally more flexible distinct covariant output lifetimes, and just trust that covariance gets everything right, like so?

    pub fn list_subtree<'this, 'arg_tokens>(
        &'this self,
        path: &[&'arg_tokens str],
    ) -> Vec<PathAndValue<'this, 'this, &'arg_tokens str, Box<()>>>
    // n.b. no explicit bounds required

There's no error when coded this way. The maximum-flexibility approach was too flexible for how we wanted to code the method body, unless we add additional bounds such as 'arg_tokens: 'return_value.

If we go this route with find_by_prefix as well...

    pub fn find_by_prefix<'this>(
        &'this self,
        _prefix: &[Token],
    ) -> Vec<PathAndValue<'this, 'this, Token, Value>>
    // n.b. no explicit bounds required

...it still works. And we can take it one step further and make PathAndValue have a single lifetime parameter like so:

pub struct PathAndValue<'pv, Token, Value> {
    pub path: Vec<&'pv Token>,
    pub value: &'pv Value,
}

And at least with the code presented, there is no fallout.


  1. using abbreviated names ↩︎

  2. Due to the implicit 'arg_tokens: 'r_p bound, this can only happen when part of 'r_v is not contained in 'arg_tokens. ↩︎

I'm pretty sure this is just a rehash of what was already said, but anyway...


If we're talking about something like this situation:

    pub fn list_subtree<'t, 'p, 'arg_tokens, 'return_path, 'v>(
        &'t self,
        path: &'p [&'arg_tokens str],
    ) -> Vec<PathAndValue<'return_path, 'v, &'arg_tokens str, Box<()>>>
    where /* ... */
    {
        self.tree.find_by_prefix(path)
    }
}

Where &'arg_tokens str are the Token type parameter and 'return_path is the 'path lifetime parameter of PathAndValue:

pub struct PathAndValue<'path, 'value, Token, Value> {
    pub path: Vec<&'path Token>,
    pub value: &'value Value,
}
// after generic "reification" of some sort =>
PathAndValue<'return_path, 'v, &'arg_tokens str, Box<()>> {
    path: Vec<&'return_path &'arg_tokens str>,
    //        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    value: &'v Box<()>,
}

The lifetimes are not independent; you must have 'arg_tokens: 'return_path so that the highlighted nested reference type is well-formed (and using unsafe to circumvent this would be UB).


So perhaps you really want something like...?

// Didn't change            vvvvvvvvvvvv
let _: Vec<PathAndValue<'_, &'static str, Box<()>>> =
    self.tree.find_by_prefix(path);

In this case, you can't unify the implementing type's Token with the prefix: &[Token] argument of find_by_prefix. Perhaps something like...

trait StartsWith<Prefix> {
    fn starts_with(&self, prefix: Prefix) -> bool;
}
impl StartsWith<&str> for str { /* ... */ }
impl StartsWith<&str> for &str { /* ... */ }

impl<Token, Value> PrefixTree<Token, Value> {
    pub fn find_by_prefix<Prefix>(
        &self,
        _prefix: &[Prefix]
    ) -> Vec<PathAndValue<'_, Token, Value>>
    where
        Token: StartsWith<Prefix>,
    { /* ... */ }
}

impl Consumer {
    pub fn list_subtree(
        &self,
        path: &[&str],
    ) -> Vec<PathAndValue<'_, &'static str, Box<()>>> {
        self.tree.find_by_prefix(path)
    }
}

(Using the same name as this method is probably a bad idea and confirming I didn't accidentally make something infinitely recurse is left as an exercise :slightly_smiling_face:)

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.