Magic type `super !` that implements every trait

1

Note: See the discussion at Should we have another non-type never? - #2 by beepster - that is the original thread

I am making a crate like serde for deserializing arbitrary formats using a derive macro.

In my crate, I have the trait Value which has to be implemented in order to deserialize any structure. This trait comes in handy because the formats my crate supports can all be described by a HashMap<String, impl Value>

Some formats support things others don't. For example, TOML has Datetime and KDL has Hybrid which has both indexed keys like an array, but also named keys like an object.

All of the methods on trait Value return an Option<T>. One of the methods describes the Hybrid data structure, but since most formats don't support it the default implementation just returns None:

trait Value {
    fn as_hybrid<'a>(&'a self) -> Option<impl Iterator<Item = (Option<Key<'a>>, impl Value)>> {
        None::<std::iter::Empty<(Option<Key<'a>>, std::convert::Infallible)>>
    }
}

As you can see, I need to specify the exact arbitrary type that None is.

In order to specify an arbitrary value for impl Value, In my crate I have an impl Value for Infallible. My crate has no other impls of Value. Instead, downstream crates would implement my_crate::Value for TomlDocument for example.

Since all methods on Value take self as an argument, I was able to provide an impl Value for Infallible like this:

impl Value for Infallible {
    fn as_list(&self) -> Option<impl Iterator<Item = impl Value>> {
        None::<std::iter::Empty<std::convert::Infallible>>
    }

    fn as_map<'a>(&'a self) -> Option<impl Iterator<Item = (Spanned<Key<'a>>, impl Value)>> {
        None::<std::iter::Empty<(Spanned<Key<'a>>, std::convert::Infallible)>>
    }
}

As you can see, In order to provide this impl I once again need to specify a completely arbitrary type that implements those traits for None.

But because the body of these functions can never be reached, it would be nice if I did not have to specify the full explicit type of None here.

What if there was a magic type super ! which implements every trait? I could simplify the impl then:

impl Value for Infallible {
    fn as_list(&self) -> Option<impl Iterator<Item = impl Value>> {
        None::<super !>
    }

    fn as_map<'a>(&'a self) -> Option<impl Iterator<Item = (Spanned<Key<'a>>, impl Value)>> {
        None::<super !>
    }
}

But can such a type even exist? It does not make sense for a type to implement every trait, what about traits such as AlwaysPanic which has the appropriate function?

Therefore, we could have several rules.

Rule 1: You are not allowed to refer to any associated items of a trait implemented by super !. So this would be a compile error, no matter what trait or associated item you reference:

<super ! as Default>::default()

As shown in Should we have another non-type never? - #2 by beepster it is possible to use the return type of a free function if it is never called, so:

Rule 2: You can only use the super ! type in the bodies of trait methods, where the body is unreachable. This should be OK, because unlike free functions: you cannot just use the return type of a particular implementation of a trait method

What do you think? Could super ! actually exist, or is there some fundamental reason this type is impossible due to something I missed?

2

I believe there is another ongoing discussion on the same topic in Should we have another non-type never?

3

Thanks for the link. I updated this thread to put more emphasis on trait methods: The issue shown in Should we have another non-type never? - #2 by beepster shows that the return type of a free function can be used even if the function itself is never called

I don't think you can do the same with methods of traits - where It would be the most useful so I think this is another restriction you could add

4

Once RFC 3654 for return type notation is stabilized, this won't hold anymore. And some form of RTN is expected to be stabilized.

5

You should be able to implement both bodies as match *self {}.

I'm not sure what makes you think this is the case. In the example above I can just use <Infallible as Value>::as_list to refer to a function that internally returns Option<super!>, then pass that function as parameter to a function that is then able to name the return type and call methods on it, just like it was shown in the other thread.

IMO something similar to it could exist, in that the compiler could generate a dummy implementation for some traits where it can prove that it is safe, possible to write manually, and not possible to call the autogenerated methods.

I don't believe super! should exist as a type though because it would be able to do things that are unsound for any other type, e.g. implementing conflicting traits.

Sidenote: isn't this discussion a duplicate of Should we have another non-type never?, which you even linked to in your first post ? What does it add that it warrants its own discussion?

1 Like
6

Sidenote: isn't this discussion a duplicate of Should we have another non-type never?, which you even linked to in your first post ? What does it add that it warrants its own discussion?

Yeah, I only noticed it after posting this thread. If there is some way to "move" this thread and comments over there I would. I'll just add a comment at the top to redirect people

7

I like this is a concrete-ish proposal and comments here can address this proposal specifically. Also this proposal attempts to deal with the associated type issue which is the main blocker. though I don't know how feasible this solution really is.

In this proposal, the super ! type can be for example an iterator, but if you attempt to observe in any way what is the item this iterator yields, the code will fail to compile. Unfortunately this blocks it from calling a simple .next() so I don't know how useful this is, but perhaps this is the most permissive way to deal with this situation (But then, why can't ! by itself work this way? Do we really need another type?)

Maybe a way to expand on this proposal could be: if we infer that the ! type is an iterator, if we don't observe the item type, it works like the super ! proposed (no separate type). But ! can also coerce to an unbounded number of uninhibited types, and each will have a different yielded item, so if we infer this iterator yields i32, it can coerce to the type ! is impl Iterator<Item = i32>, which is an different type than !.

8

One could use the existence of an implementation for a sealed marker (itemless) trait as a proof for something. I can't imagine a design where that would be the best choice, but it's sound today.

super! would break that.

2 Likes