Why is `!Trait` not possible?

language design
1

Hello :waving_hand:

Firstly, for context:
I want to do make a type-level type map, similar to tlist as a list, but where I have ((((), A), B), A) and then can retrieve the outermost &A by going through the tuple from outer to inner, checking if (_, T); T = A and then reference that, elsewise go down the tuple tree.
For a dummy implementation with specialization, that would look like this:

trait TMap<T> {
    fn get(&self) -> &T;
}

impl<Down, T> TMap<T> for (Down, T) {
    fn get(&self) -> &T {
        &self.1
    }
}

impl<Down: TMap<T>, T, Other> TMap<T> for (Down, Other) {
    fn get(&self) -> &T {
        self.0.get()
    }
}

the only problem is that this makes a conflicting implementation between type (_, _) and (_, _).

Now I know that specialization is a year-, almost decade-long complicated and discussion heavy topic, which shouldn't be just half-ready implemented, so I went on a way to see if I can get around that.

I won't mention the other things I tried here, as they all lead to other forbidden or not-yet-ready implemented features. If you want to know them, let me know.

The thing I'm interested in the most is with this variant:

trait Is<T> {}
impl<T> Is<T> for T {}

trait TMap<T> {
    fn get(&self) -> &T;
}

impl<Down, T> TMap<T> for (Down, T)
where
    T: Is<T>,
{
    fn get(&self) -> &T {
        &self.1
    }
}

impl<Down: TMap<T>, T, Other> TMap<T> for (Down, Other)
where
    Other: !Is<T>,
{
    fn get(&self) -> &T {
        self.0.get()
    }
}

here, I want to convince the compiler that the second type in the tuple is concretely not implementing the trait which the other impl block requires so that they don't conflict.
Tho this doesn't work, I get the error negative bounds are not supported.

And finally, my simple question: Why? Is there any specific reason for that? Something that makes it hard to implement? Is there some Pre-RFC already? (at least I couldn't find one after a quick search here in the forum) Would this be something to RFC?

Thank you for reading this mess of thoughts and hacky stuff :heart_hands:

1 Like
2

well, for one thing,

impl<T> Paradox for T where T: !Paradox {}

if you're clever then you may immediately think of various approaches the compiler could take to handling this kind of thing, but it turns out that each of them is its own can of worms, too! Negative bounds greatly increase the theoretical demands the trait solver has to fulfill.

4 Likes
3

Hmm fair.
I'm not that deep in rust's compiler logic but couldn't that be solved with a circular check..

Thinking about it a bit more, wouldn't it be the same problem as with

impl<T> Paradox for T where T: Paradox {}

so if I were to write an RFC, couldn't I just explain !T as an autotrait which get's unimplemented by T?

4

You may also notice that your technique would be able to implement EVERY possible usage of specialization – just have the specialized version and the general version be separate impl's, where the general one has a negative bound! This makes negative bounds strictly more powerful than specialization (which you've already realized has posed difficulties).

I'm going to see if I can help you find a trick for your specific problem – I've messed around a lot with type level nonsense, so maybe I can think of something.

3 Likes
5

also: simpler way of specialization sounds interesting to me.. as auto traits are already implemented theoretically AFAIK

And thanks for looking into that! Really appreciate that, I sadly don't think it's possible as I've also tried lots of things, but I also don't know everything :sweat_smile:

6

Okay, so the bad news is that your stated goal inherently requires the ability to tell that one type is different from another – which is surprisingly much of a theoretical challenge. Even with just specialization, you can implement a paradox by projection through associated types (you could make a list where one of the elements is an associated type that depends on whether the list itself contains that type!). Because of this kind of thing, Rust basically doesn't let you do any logic based on types being different from each other… And sometimes doesn't even manage to realize that types are the same when they actually are.

Now, I think what you can do is reference the map members by their index, by implementing a unary index type that's the same shape as the list, and implementing a trait expressing "list L has a member of type A at index I". Whether that's helpful depends on what your underlying goals are.

1 Like
7

Hmm interesting idea, sadly I quite need the feature of not having to specify the location and it just using the "newest"/most on top item :confused:

8

Some other directions you can compromise:

  • do the whole thing using macros rather than type-level logic
  • make only a finite collection of types that can be included in such lists, which allows you to replace the negative "skip the first element because it's not equal" impl into a collection of N-1 positive impls, one for each of the different types. (Macros can let you implement this conveniently enough, and even make the finite collection extensible – the only limit is that the finite collection must be known before the trait system starts doing anything.)
9

Also won't work, it is intended to be used as a library ._.

10

The second most promising thing was

trait Is<T> {
    const IS: bool = false;
}
impl<T> Is<T> for T {
    const IS: bool = true;
}

trait TMap<T> {
    fn get(&self) -> &T;
}

impl<Down, T> TMap<T> for (Down, T)
where
    T: Is<T, IS = true>,
{
    fn get(&self) -> &T {
        &self.1
    }
}

impl<Down: TMap<T>, T, Other> TMap<T> for (Down, Other)
where
    Other: Is<T, IS = false>,
{
    fn get(&self) -> &T {
        self.0.get()
    }
}

which get's me both the (_, _) and (_, _) conflict error and associated const equality is incomplete see issue #92827 for more information

11

Technically you could have the library-user use these macros, but that would definitely be a pain, yes.

What's the reason that you need "first-of-type"? My instincts say that's inelegant and there may be a better approach.

12

Well I'm trying to make a context-like to pass down, so that I can just say "I need to get the winit context" (Env: TMap<WinitCtx>) and then for adding/replacing that context I can just use (other_ctx, winit_ctx).

As for macros, how just roughly would such a macro look like? So like that it's not a single big monolithic macro call but that different dependencies can mark their structs as Contextable?

13

Oh boy. Do you need to solve the diamond problem here? That is, might there be multiple dependencies that both require a winit context, and provide their own lists, which the final user has to be able to merge so that they only construct-and-use one winit context?

14

Well the idea is that the context just gets passed down. So when you think about that every type could be in that map thing, the winit dependency can say "I have a winit runner, and in that closure you give me, you have the context you gave me + my winit context" - So there is no merging or type conflict, it's just one thing that get's added and removed from all the time and when I want type A, I need to name it.

15

Note that this data structure has already been implemented in frunk::HList.

It avoids conflicting implementations by adding a dummy generic parameter which specifies where in the list to look, which the type inference algorithm is willing to infer based on there being only one type match. That inference behavior is a bit sketchy[1], but it works well here and doesn’t require new or unstable features.

(@benschulz ’s post below is a minimal version of the same technique.)

  1. relying on it in other situations can make your code stop compiling when dependencies add new impls ↩︎

16

Does the following work for you?

trait TMap<T, N> {
    fn get(&self) -> &T;
}

impl<Down, T> TMap<T, ()> for (Down, T) {
    fn get(&self) -> &T {
        &self.1
    }
}

impl<N, Down: TMap<T, N>, T, Other> TMap<T, (N,)> for (Down, Other) {
    fn get(&self) -> &T {
        self.0.get()
    }
}

fn main() {
    let x = ((((((), 5u128), 4u64), 3u32), 2u16), 1u8);
    let a: &u8 = x.get();
    let b: &u16 = x.get();
    let c: &u32 = x.get();
    let d: &u64 = x.get();
    let e: &u128 = x.get();

    println!("{a} {b} {c} {d} {e}");
}

Of course, if the same type appears multiple times, you need to resolve the ambiguity. :frowning:

2 Likes
17

:0 that's interesting.. before I try, is it even possible to make this work with having the same type multiple times?

18

Okay. It sounds like the assumption is that there is exactly one of each type in the list, and in order to construct the list in the first place, some piece of code would have to know all the types, syntactically, probably in the final binary crate – this makes it perfect for a macro, because the binary crate must already be able to list the types on a syntactic level.

If that's viable, you don't even need this type-level list: you could have a proc-macro that's used like

#[derive(DasLixousCrate::Context)]
struct MyContext {
  winit_context: WinitContext,
  other_context: OtherContext,
  ...etc
}

and then #[derive(DasLixousCrate::Context)] could expand to:

impl DasLixousCrate::ContextContains<WinitContext> for MyContext {
  fn get(&self) -> &WinitContext {
    &self.winit_context
  }
}

...etc

and dependencies can use it with the trait bounds like

fn whatever<UserContext>(context: &UserContext)
  where UserContext: ContextContains<WinitContext>,
        UserContext: ContextContains<AnyOtherContextYouNeed>,
        ... {
19

yeah no that's what I'm trying to get rid of... and there may be multiple of the same type in the list :confused:

20

wait, what's the purpose of having multiple of the same type, if only the first can ever be accessed?