Would non-`'static` TypeId be at all possible?

Well, that's the problem. Lifetimes are such a purely compile-time construct that they're completely erased at runtime.

Consider this function signature:

// If 'b: 'a, then returns Some(x), else returns None
fn downcast_lifetime<'a, 'b>(x: &'a u32) -> Option<&'b u32>

If there was a version of Any that could dynamically test for lifetimes, you could use it to implement downcast_lifetime.

But how would that actually work? downcast_lifetime can be called with either 'a or 'b as the longer lifetime (or they could be equal). Suppose there is one code path that calls downcast where 'b: 'a holds, and another where it doesn't hold. Then no matter how sophisticated a global analysis the compiler performs, it obviously can't prove statically that 'b: 'a either holds or doesn't hold.

So there are two options: it could encode the lifetime at runtime as part of the reference, or it could try to monomorphize functions based on lifetime.

Encoding it at runtime would come with overhead; every reference would probably have to double in size, to store some integer representing the lifetime along with the actual pointer value. It might be possible for the compiler to optimize away the lifetime value in cases where it's known not to be used – sometimes. If you're using references as local variables or function arguments passed by value, and not doing any dynamic dispatch, it might be possible to elide most unneeded lifetimes... with a sophisticated (and slow) global analysis. But what if you have a Vec<&Foo>? The compiler is not going to magically compress the Vec elements in cases where they can be compressed. It's not that smart.

Monomorphizing functions based on lifetime would be difficult. Some might say it's impossible, since the existence of recursion means that there can be an unbounded number of nested lifetimes. But I think (could be wrong) that you'd 'only' need a separate copy of the function for every possible combination of outlives relationships. The number of possible combinations is finite, sure enough… but it grows exponentially in the number of lifetimes. Now, as long as you stick to static calls, you'd only have to monomorphize the combinations that were actually used. But what about dynamic dispatch? Rust allows lifetime generics in trait objects, precisely because lifetimes are erased. To make this work with monomorphized lifetimes, a trait object vtable would need one slot for every possible combination. That's not going to work.

(Also, even ignoring the exponential growth issue, having to compile functions even two or three times just because they were used with different lifetimes would be a massive compile time hit. Maybe you could reduce the impact by carefully keeping track of when lifetimes do and don't affect the end result.)

With all that said, I believe it is possible to make a version of Any that works with non-'static objects, but where all lifetimes involved are known at compile time. You could convert from Foo<'a> to AnyA<'a> and back, but you couldn't convert from Foo<'static> to AnyA<'a>. (You could convert from Foo<'static> to Foo<'a> first, if it happens to be a covariant lifetime parameter, but there would be no way to recover the 'static lifetime afterwards.)

And yes, AnyA is what Soni was proposing the other day. Except I'm pretty sure that, rather than needing a new higher-kinded types feature, you can implement at least a version of it with just GATs...

10 Likes

O(n! * cn+1) if equality is considered distinct.

3 Likes

Do also note that you can get the TypeId of something like for<'a> fn(&'a ()), i.e. you can get a TypeId for what's conceptually a type constructor (but also effectively a type).

Actually, I need to correct my last post.

If you choose to encode lifetimes at runtime, you don't have to store each reference's lifetime alongside its pointer value. In fact, doing so would be incorrect. Lifetimes don't belong to values; they belong to types. You can safely convert e.g. &'a &'b u32 to &'a &'a u32, but that changes the lifetime you should get from the inner reference, even though you're not touching the memory.

Instead, you would want to pass lifetime relationships as a hidden function argument(s). For a given generic function, you would have to encode the relationships of all lifetime parameters it has, as well as all lifetimes embedded in types chosen for its generic parameters. Also, trait objects are the one case where lifetimes do belong to values. Thus, trait object references would have to store lifetime information for their underlying type (not to be confused with the lifetime of the reference itself), making them extra fat.

This is slightly more feasible than what I said last time. But it would still be quite expensive, even if you 'just' store the relationships between lifetimes, which would suffice for some purposes. If you want to allow keeping around potentially expired references, like the OP's mention of sticking a local variable in a global Vec<Box<dyn Any>>, and dynamically test whether a reference is still alive, you would have to store more than that. I think you'd have to maintain some kind of global tree of lifetimes at runtime, which is starting to get into "everything is 10 times slower" territory. :wink:

3 Likes

I don’t fully understand why any internal lifetimes are important for trait objects... a type dyn Trait + 'a has a lifetime in its type and more information than that single lifetime is not really needed to handle the trait object safely.

In particular for

we should not forget that the type Box<dyn Any> is nothing but shorthand for Box<dyn Any + 'static>, with the effect that we wouldn’t gain anything here from an Any trait with implementations for non-'static types; my answer to this question

would be: no, nothing would allow that. Not to say that there isn’t a way to put references to local variables into a global data structure at all with a sufficiently advanced dynamic lifetime system. But it can’t be through ordinary dyn Trait + 'a–style trait objects.


a way to put references to local variables into a global data structure at all with a sufficiently advanced dynamic lifetime system

Another approach—using just non-'static implementations of Any—could involve some kind of scope/guard objects that allow access to a global store. When a scope is left, everything associated to that scope is removed from the global store again. A scope introduces a lifetimes 'a and any Box<T> to be inserted while inside of the scope needs to fulfill T: 'a for conversion into Box<dyn Any + 'a>. There would need to be type comparisons between Box<dyn Any + 'a> and Box<dyn Any + 'b> for different lifetimes 'a and 'b; namely, if two scopes with lifetimes 'a and 'b are using the same store.

Those kind of comparsons would need to be possible anyways because of variance. If you have x: Box<dyn Any + 'a> and y: Box<dyn Any + 'b>, you can treat x and y as having the same type Box<dyn Any + 'c> as long as 'c is shorter than both lifetimes 'a and 'b.

Because specialization is not stable, I've needed the following function for ad-hoc specialization: Given a type T, is T == f64 or not?

With T: 'static this is easy to implement using the current TypeId. It would also be easy to implement with a more relaxed type id, and it would seemingly be easily sound (because one of the two types in the comparison is completely without lifetimes). However, there is no way with the current type system to constrain a function like is_equal<T, U> to only types where U is "lifetime-free".

1 Like

Or into GC territory. ;p

Maybe we could have a fallible constructor, returning Some(TypeId) for T: 'static, otherwise None. Alternatively, it could use a wrapper that treats non-static like a NaN state, to avoid the mistake of comparing None == None and thinking that's type equality.

This: I'd love for a is_equal<T : 'static, U>() -> bool function provided by the stdlib, although I have to admit having needed that to hack into poor man's specialization too :sweat_smile:

1 Like

That doesn't quite work. With such an is_equal function, you could implement:

fn is_this_lifetime_static<'a>() -> bool {
    is_equal::<&'static (), &'a ()>()
}

But such a function would have to pull information out of thin air, given that lifetimes are erased.

What you'd need is not just T: 'static, but some kind of constraint that means "T does not even contain any lifetimes".

Not coincidentally, the "specialization mode" mentioned in this blog post as a path for sound specialization, if implemented, would provide a way to express that constraint. "Specialization mode" is a pretty non-descriptive term, so I like to call it "regardless of lifetimes". Using that name, is_equal could have its signature written as:

fn is_equal<T, U>() -> bool
    where regardless_of_lifetimes(T: 'static)
{ /* ... */ }

This would require that the constraint not only holds for T, but would still hold even if any lifetimes contained in T were replaced with any other legal possibility. In this case it means that T can't have any lifetimes. If it did, then you could replace them with a local lifetime and T would no longer be 'static.

Well, with the exception of useless lifetimes which are forced to be 'static, like struct Foo<'a: 'static> { /* fields */ }. T can have those.

That said, if the goal is poor man's specialization, well… if regardless_of_lifetimes is added to the language, it would probably be stabilized at the same time as specialization, making poor man's specialization unnecessary. But who knows if that will ever happen.

Perhaps in the meantime there could be a lang-item function that works like @cuviper's suggestion, returning Some(TypeId) or None – except that it would have to check that T has no lifetimes, not just that it's 'static.

4 Likes

You're right, I phrased that quite poorly, thanks for pointing it out :ok_hand: In my case I had a concrete type T in mind (such as type T = () or type T = *const c_char) which couldn't possibly be the 'static instantiation of a lifetime-infected type (I guess that's what you mean by regardless_of_lifetimes(T : 'static) – I thank you for letting me map this "'static regardless of lifetimes" wave-handed definition to the "specialization mode" terminology)). I agree that correctly distinguishing these two "use-cases" (the problematic one, and the one I had) apart is footgunny so I can understand why this unchecked API of mine isn't available yet (but for the valid use cases it would still be useful in the meantime :upside_down_face:)

It's still ok if there are 'static lifetimes internally, right? I understand why &'a () vs. &'static () is problematic, or Cow<'a, str> vs. Cow<'static, str>, but struct Moo(Cow<'static, str>) should be fine.

2 Likes

Yeah… I'm not sure of the right terminology, but I'd define "has no lifetimes" as: *ahem* The canonical name of the type, after fully resolving any generic type parameters, type aliases, and trait projections, doesn't mention any lifetimes – except for ones introduced with for<'a> syntax within the type name itself.

So Moo is eligible, because its name is just Moo; the definition of the struct doesn't matter. But Bar<Cow<'a, str>> is obviously ineligible.

More interestingly, Bar<Cow<'static, str>> should probably also be ineligible. In theory the compiler could allow it, if and only if it knew at compile time that the lifetime really was 'static – i.e., yes if you wrote out Bar<Cow<'static, str>> directly, no if you wrote Bar<Cow<'a, str>>, where 'a is some lifetime parameter to your function, and then your function just happened to get called with 'a as 'static. This is the kind of behavior you get today from unstable specialization. Specialization is unsound, but only in conjunction with associated types; there'd be nothing inherently unsound about having this function work that way. But it feels spooky for a function to change its behavior based on not just what a lifetime parameter is, but what it might have been. It's probably better for the compiler to play dumb, at least to start with.

Oh, and about for<'a> syntax (i.e. higher-ranked types): The type for<'a> fn(&'a u32) -> &'a u32, which is just the expanded form of fn(&u32) -> &u32, should be eligible, because there's no concrete lifetime in there that can vary. (You can remove the for<'a> and change it to, say, fn(&'static u32) -> &'static u32, but as Soni mentioned, that is treated as a separate type for monomorphization purposes.) Same goes for, say, Box<for<'a> dyn FnOnce(&'a u32)>.

2 Likes

It's actually dyn for<'a> btw, if we recall correctly.

Itym "the resolved type has no free lifetime variables". That is, if the type's kind incorporates the lifetime kind in any way. So Moo: type but Cow<'static, str>: lifetime -> type in this case, because 'static is an applied parameter of the type.

As you mention, we should exclude cases like Trait<'a>::Assoc = i32.

It's actually dyn for<'a> btw, if we recall correctly.

Both for<'a> $ty and for<'a> $trait are valid; the first is a valid type, the second is a valid bound. I can write for<'a> fn(&'a i32), for example. You can even write for<'a> dyn for<'b> Fn(&'a i32) -> &'b i32.

type X = for<'a> dyn FnOnce(&'a ()); does not compile.

Yes, I can't see how Rust would be able to distinguish that type from a monomorphization of 'a = 'static. I think wrapper types would thus be mandatory.


Funnily enough, I know there is currently an instance where Rust distinguishes between an explicit 'static "monorphization choice" and a fixed 'static lifetime (e.g., through a type alias), although I find that to be more of a bug / inconsistency rather than a feature:

macro_rules! StaticStr {() => ( &'static str )}
type StaticStr = &'static str;

fn foo (_: StaticStr!()) -> &str { "" } // Ok.
fn bar (_: StaticStr   ) -> &str { "" } // Fails.
1 Like

I’m not really understanding the argument here. We’re talking about what should be allowed as the type T in a hypothetical fn is_equal<T: NoFreeLifetimes, U>() functions, right? You explained yourself that &'static () doesn’t work, how is Bar<Cow<'static, str>> any different? Maybe it would work in a setting where Bar is some struct Bar<T: 'static>... but otherwise you’d have the problem of a potential is_equal::<Bar<Cow<'static, str>>, Bar<Cow<'a, str>>> call, wouldn’t you?

That's weird. Though both functions do work if you label the return type explicitly as &'static str, so it's 'just' an issue with lifetime elision.

No, well… I'm talking about what should be allowed in a hypothetical fn some_name_here<T>() -> Option<TypeId> function. But I suppose the difference is less about the function signature, more just a question of naming and user expectations. For a function named is_equal, it's clearly wrong to spuriously return false because it implies the types are not equal. But in theory you could just rename it to is_provably_equal, and document what "provably" means in this context. Or perhaps it could be named is_equal but return Option<bool>, as in 'definitely equal, definitely not equal, or unknown'. Similarly, if the Option<TypeId>-returning function were named type_id_if_static, it would be wrong to spuriously return None, but not if it was named e.g. type_id_if_provably_static.

Still, as I said, these kinds of semantics would be spooky and confusing, so it's probably best to avoid them.

2 Likes

Am I missing a reason we couldn't have TypeId just omit any information about lifetimes?