I'm running into an issue when passing a reference to a trait object's method â the borrow checker complains that the reference is still "live" until the end of the function, even though it's only used as an input. Here's a minimal example:
trait MyTrait<T> {
fn do_smth_with_t(&self, t: T);
}
impl<T> MyTrait<T> for () {
fn do_smth_with_t(&self, _t: T) {
println!("Imma do nothing!");
}
}
fn usage() {
let boxed: Box<dyn MyTrait<_>> = Box::new(());
let t = String::from("hello");
boxed.do_smth_with_t(&t); // error here
}
error[E0597]: `t` does not live long enough
--> src/main.rs:12:26
|
11 | let t = String::from("hello");
| - binding `t` declared here
12 | boxed.do_smth_with_t(&t);
| ^^ borrowed value does not live long enough
13 | }
| -
| |
| `t` dropped here while still borrowed
| borrow might be used here, when `boxed` is dropped and runs the destructor for type `Box<dyn MyTrait<&String>>`
Now, if I explicitly use a higher-ranked trait bound, it compiles:
fn usage() {
let boxed: Box<dyn for<'a> MyTrait<&'a String>> = Box::new(());
let t = String::from("hello");
boxed.do_smth_with_t(&t); // works
}
However, things get more complicated when I try to wrap the construction of the boxed trait object in a function:
Thanks for the example. Because an implementor can store T in its internal structure, Rust requires T to outlive the trait object itself. But is there a way to express that: T only lives during the function call? In my higher-ranked lifetime example later, I get it to work using the Box<dyn for<'a> MyTrait<&'a String>> but I couldn't figure out how to wrap it in a function.
the generic type parameter T is in the trait, not the method. the generic parameter must be namable when you construct the trait object. let's write the lifetime explicitly in pseudo syntax:
fn usage() {
// the placeholder `_` is inferred as a single type, let's call it `&'a String`
let boxed: Box<dyn MyTrait<&'a String>> = Box::new(()); //<---- region `'a` starts this line
let t = String::from("hello"); //<---- region `'b` CANNOT start before this line
boxed.do_smth_with_t(&'b t); //<---- type signature requires `&'b String`: `&'a String`, which cannot be satisfied
}
if you change the order of 'a and 'b, then it compiles:
let t = String::from("hello");
let boxed: Box<dyn MyTrait<_>> = Box::new(());
boxed.do_smth_with_t(&t);
as you already found out, make the trait object higher ranked also solves the problem
It fails because generic type parameters like N can only represent a single type, whereas in for<'a> MyTrait<&'a String>, &'a String is representing an infinite number of types -- one for every distinct lifetime 'a.
If you want any sort of lifetime-parameterized type constructor in place of N -- i.e., not just &NPrime specifically or &mut NPrime specifically, et cetera -- you have to do so indirectly, like through a trait.
Thanks for the explanation. However, in real usage, that trait object is reused to traverse some tree data structures. Also, the N type parameter can be an owned type, reference, a refcell guard, or an Rc
Thanks for the solution. If I'm understanding correctly, this is the HKT emulation pattern. While reading your sketch, I don't understand why there is a Guard type parameter that isn't used anywhere.
trait MaybeBorrowed<'a, Guard = &'a Self> {
type Ty;
}
Besides, this is a wonderful workaround! I tried to remove the type annotation, and it's still working.
fn usage() {
let boxed = make::<RefRepresentative<String>>();
let t = String::from("asd");
boxed.do_smth_with_t(&t);
}
Is there a way to omit the RefRepresentative for local type? I wonder if this is valid?
// ... continue from your playground
struct MyT<'a>(&'a String);
// This can be a derive macro
impl<'a, 'hkt> MaybeBorrowed<'hkt> for MyT<'a> {
type Ty = MyT<'hkt>;
}
fn usage() {
let boxed = make::<MyT>(); // elided MyT<'_> bound
let t = String::from("asd");
let myt = MyT(&t);
boxed.do_smth_with_t(myt);
}
It is sometimes needed if you need to support something like for<'a> MyTrait<&'a NotStatic<'b>>. Here's an article about how it works. Your use case might not need it. In which case, a GAT might also work.
Your OP worked when I pasted the pieces into the playground, because it chose a single lifetime, something like dyn for<'a> MyTrait<&'static String>. The annotations were just to illustrate/ensure that the actually desired type was produced.
Seems to work just fine. (I think I did that mechanically as I've often had a conflicting blanket implementation when using this basic pattern.)
After I tried adding an associated item to an iterator, I cannot use the for <'a> lifetime inside Iterator::Item associated type. It gives this error:
error[E0582]: binding for associated type `Iter` references lifetime `'a`, which does not appear in the trait input types
--> src/lib.rs:20:39
|
20 | -> Box<dyn for<'a> MyTrait<R::Ty<'a>, Iter = Box<dyn Iterator<Item = R::Ty<'a>> + 'a>>>
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
There's a couple things going on here. Here's one:
impl<T> MyTrait<T> for () {
// This is a `Box<dyn Iterator<Item = T> + 'static>`
//
// There is unfortunately no way to code this to be exactly a
// `Box<dyn Iterator<Item = T> + 'longest_lifetime_t_outlives>`
// (but you can add a lifetime parameter and use all `'t where T: 't`)
type Iter = Box<dyn Iterator<Item = T>>;
The latter scenario encounters this error because Foo::Assoc<'a> could be implemented by a type that does not use the 'a parameter, so there is no guarantee that X::Assoc<'a> actually uses 'a.
This seems overly restrictive to me for some cases (though I may be missing something), but I can see how it is problematic for your signature...
-> Box<
dyn for<'a> MyTrait<
R::Ty<'a>,
Iter = Box<
dyn Iterator<Item = R::Ty<'a>> + 'a
>
>
>
...as it implies an implementation of MyTrait<X> for a single X (an R::Ty<'_> that doesn't contain any lifetimes), which somehow has an infinite number of distinct definitions for the associated Iter type (one for each + 'a).
(Also note that nothing requires R::Ty<'a>: 'a in the playground,[1] but adding that constraint doesn't change these problems.)
Here are the actual traits I used. I wanted a CSS-like syntax for traversing tree-like data structures so I don't have to use nested iterators, especially ones with guarded nodes. NodeView is an adapter for any tree-like data structure. Selector traverses the tree using the provided adapter. The playground below is the version where I haven't introduced any helper traits yet. Playground
// Compiler wants NodeView + 'q here but I don't think this is correct.
// the NodeView can be droped after use and the selector should continue
// to live as long as `query` is still around
TypeEraser<'i, S>: Selector<N> requires <S as Selector<N>>::Iter: 'i
TypeSelector<'q>'s Iter is impl Iterator<..> + use<N, 'q>
In fact it's a std::option::IntoIter<Result<N, Self::Err>>
The 'i in TypeEraser<'i, TypeSelector<'q>> in the body is inferred, but you coerce that to a dyn ... + 'q, so 'i: 'q is required
So <TypeSelector<'q> as Selector<N>>::Iter: 'q is required
So std::option::IntoIter<Result<N, Self::Err>>: 'q is required
So N: 'q is required
(Reasoning about how long values are around is often misleading when it comes to borrow checker errors, which are typically about duration of borrows or the properties of types.)
The other error can be fixed by declaring node first.
fn usage() {
let mut node;
let query = "h1";
let selector = make(query);
node = Node {
c: vec![],
n: "h1".into(),
};
selector.select(&mut node);
}
The 'i in TypeEraser<'i, TypeSelector<'q>> in the body is inferred, but you coerce that to a dyn ... + 'q , so 'i: 'q is required
Is there a way I can decouple the lifetime of the query string and the node used to traverse? The node lifetime could be smaller than the selector. One use case requires it, I want to reuse the selector, similar to the regex crate, which shares some similarity with what I'm doing later, parsing the expression tree of a query and constructing a selector and that is potentially expensive so it would be nice to be able to do something like this.
OK, I got somewhere. Let me try to walk through how I got there.
From your snippet, you don't want something that works with one &mut Node lifetime, you want something that works with all &mut Node lifetimes, and is suitable to put in a 'static. So something like a
pub type TypeErasedMutForStatic<N> = Arc<
dyn Send
+ Sync
+ for<'any> Selector<
&'any mut N,
Err = ErrBox<'static>,
Iter = BoxIter<'any, &'any mut N>
>
// + 'static
>;
But now the problem is that there is no TypeEraser<'x> that implements Selector<&'a mut N> for all 'a. The lifetime parameter on that struct is putting a lower limit on the validity of N and S::Iter, and there is no "shortest lifetime". There's always some "shorter" &'n mut Node that isn't covered by the implementation.
I don't think there's a way to make that work with that lifetime in there, so we need to get rid of the lifetime. But if we don't have it in our type, yet still need to refer to it, we have to have it in the traits we implement.
pub struct TypeEraser<S>(pub S);
// You can't have an unconstrained lifetime like this
// vv
impl<'i, S, N> Selector<N> for TypeEraser<S>
where
S: Selector<N>,
S::Iter: 'i,
N: NodeView + 'i,
So let's add it to Selector.
pub trait Selector<'i, N: NodeView> {
// Not actually used...
Then you go put lifetimes everywhere that now complains and... that's enough for this one to compile. (Often you have to sneak in implied bounds to get things like this to work, so I was somewhat surprised that's all it took.[1])
Alternatively, you can leave Selector alone, get rid of TypeEraser, and have an erased trait instead.
Where the made-up syntax 'use<N> means the largest lifetime 'x such that N: 'x. Or alternatively, you wish there was a way to have 'i be an upper limit, like if you could have a bound like
impl<'i, S, N> Selector<N> for TypeEraser<'i, S>
where
S: Selector<N>,
N: NodeView,
'i: N + S::Iter,
though that is probably only useful if there was some "shortest lifetime" annotation.
I believe these are what is called existential lifetimes in various compiler/language design discussions.
And now I'm glad I took the time to write this up, as my actual route involved adding some implied bounds that end up to not be needed. So far. âŠī¸
Thanks for the write-up. I don't think I can come up with this on my own. Before posting the question, I also tried to come up with something that will not depend on a single lifetime &'a mut Node for some specific 'a using htrb. But the compiler tells me that the current compiler limitation implies a 'static bound (sorry, I didn't commit this version to git, so I can't give you the full example)
impl<S, N> Selector<N> for TypeEraser<S>
where
S: Selector<N>,
for<'i> S::Iter: 'i,
for<'i> N: NodeView + 'i,
Anyway, when I tried to add the make() function back for the user to dynamically construct a selector based on a user query and it no longer works, and the compiler error doesn't say which bound causes 'q to outlive 'static
In that particular case, I don't think it's a limitation that can go away; some sort of limited bound would have to have some additional syntax.
Yeah, figures. Remember when I said...
Turns out, this problem also doesn't need implied bounds (so far). But the way I solved it was to assume that it would. And it turns out that did eventually highlight the problem. So I'll walk through what I did, as it feels like a useful tool even if you end up not keeping the implied bounds. You'll also end up with some choices on what bounds you want to leave in place.
Often when you need to satisfy some higher-ranked bound...
The where clauses which can cause the bound we need to satisfy to fail.[1] But if those same bounds were implied so they didn't have to be stated explicitly, the bound would pass.
So our goal is to figure out how to make all the bounds on the implementation implied. For example, the presence of a &'i N somewhere in the inputs to this implementation would make N: 'i implied, so we could remove that part of the where clause.
For the S::Iter: 'i clause, we can make use of that 'i parameter we added to Selector.
pub trait Selector<'i, N: NodeView> {
type Err: Error + 'static;
- type Iter: Iterator<Item = Result<N, Self::Err>>;
+ // The associated type bound will be impiled by T: Selector<'i, N>
+ type Iter: Iterator<Item = Result<N, Self::Err>> + 'i;
fn select(&self, node: N) -> Result<Self::Iter, (N, Self::Err)>;
}
error[E0477]: the type `<TypeSelector<'a> as Selector<'_, N>>::Iter` does not fulfill the required lifetime
--> src/lib.rs:134:17
|
134 | type Iter = impl Iterator<Item = Result<N, Self::Err>>;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The problem is, these are equivalent:
impl<'a, N: NodeView> Selector<'_, N> for TypeSelector<'a> {
type Err = N::Err;
type Iter = impl Iterator<Item = Result<N, Self::Err>>;
impl<'a, 'i, N: NodeView> Selector<'i, N> for TypeSelector<'a> {
type Err = N::Err;
type Iter = impl Iterator<Item = Result<N, Self::Err>> + use<'a, 'i, N>;
// ^^^^^^
type Iter = std::option::IntoIter<Result<N, Self::Err>>;
...but if you can't or don't want to do that, you'll have to use TAIT instead.
pub type TypeSelectorIter<N: NodeView> = impl Iterator<Item = Result<N, N::Err>>;
// New attribute since last I tried TAIT. Better than having to put
// all the defining uses in their own module like before...
#[define_opaque(TypeSelectorIter)]
fn type_selector_iter<N: NodeView>(this: &TypeSelector<'_>, node: N)
->
Result<TypeSelectorIter<N>, (N, N::Err)>
{
let x = node.node_type()?;
let rs = if x.get() == this.ty {
let reclaim = x.node();
Some(Ok(reclaim))
} else {
None
};
Ok(rs.into_iter())
}
impl<'a, 'i, N: NodeView + 'i> Selector<'i, N> for TypeSelector<'a> {
type Err = N::Err;
type Iter = TypeSelectorIter<N>;
fn select(&self, node: N) -> Result<Self::Iter, (N, Self::Err)> {
type_selector_iter(self, node)
}
}
and could also get rid of 'i, though it doesn't matter for our bound âŠī¸
Or I don't understand how it works. Here's a stalled stabilization issue. The list of related issues is a bit to daunting to try and find something more specific right now... âŠī¸
If I understand correctly after reading this, usually explicit lifetime bound may cause a higher-ranked trait bound to fail, but it is not in this case? The underlying problem in this case is TypeSelector<'a>::Iter overly captures lifetime? If this is the case, why TypeSelector<'a>::Iter capturing 'a make 'q in query: &'q str to outlive 'static? Doesn't it just require the query to outlive the returned iterator?
I did some experiments with Seleter::Itercapturing the lifetime inside the selector or even referencing the selector itself. While I think the ChildFilterSelector requirement might not be needed since all Selectors eventually become Arc, more on this later. But something like ChildFilterSelectorSlim should be supported.
Also, another use case is common selector combinators: eg chaining the output of a selector to another selector. In the experiment above. The ChildFilterSelector(Slim) can be composed by Chain<ChildSelector, NodeTypeSelector>, and the chaining logic is abstracted away from the selector, and they only have to implement their specific logic. I have come up with this but it also requires 'q to be 'static.
Note that this implementation also requires the chained selector to be Clone. It works well in my type-erased Arc selector unless the user wants to opt out of my default, which I plan to support other strategies for upcasting (actually provide the opportunity for, not sure I will implement it in my crate), using another container instead of Arc.
This Chain selector is also a major reason I chose Arc instead of Box as a default type-erased selector. It would be nice if we could reference it to allow Box<Selector> without the Clone bound.
Yes. The Sabrina Jewson article has more exploration; basically it's usually because you end up with something like a for<'a> ThingWith<'a>: ... when you needed a for<'a where 'b: 'a> ThingWith<'a>: .... Implied bounds are a way to emulate the latter.
It was capturing 'i which caused it to not outlive 'a / 'q. Given these:
impl<'a, 'i, N: NodeView> Selector<'i, N> for TypeSelector<'a> {
type Err = N::Err;
type Iter = impl Iterator<Item = Result<N, Self::Err>> + use<'a, 'i, N>;
impl<'i, S, N> Selector<'i, N> for TypeEraser<S>
where
S: Selector<'i, N>,
S::Iter: 'i,
N: NodeView + 'i,
Now N can contain a reborrow of *self, even if Self: 'static, which, well... have you read the Sabrina Jewson article yet? I would mostly be repeating a lot of that material.
Once borrows or reborrows of Self end up in the Iter, you might run into needing something like
Edit: Here's a more complete example since it required another workaround. I only implemented Selector<..> for dyn Send + Sync + ..., not for all combinations of auto-traits. I also went back to precise capturing associated types (see the next comment).