Monomorphization of associated constants

Delphy · December 26, 2024, 8:16pm

Hi, while trying to find a way to ensure that two types are distinct, I encountered some behavior I don't understand. I have a struct TypesNeqInternal, which takes two type parameters. Futhermore the traits Distinct and Same each provide an associated constant OK, which, when read from TypesNeqInternal should either evaluate to a value or cause a deliberate compilation error when the two type parameters to TypesNeqInternal are the same. So far, this part works fine.

I then introduced the type TypesNeq, which acts as a wrapper around TypesNeqInternal. TypesNeq provides its own associated constant which is initialized via the corresponding TypesNeqInternal type. However, for some reason TypesNeq::<T1, T2>::OK always gets initialized to <TypesNeqInternal::<T1, T2> as Distinct>::OK, even when T1 and T2 refer to the same type. My expectation was that compilation should still fail in that case.

The compiler also warns that the Same trait is unused.

Why does TypesNeq::<T1, T2>::OK always get initialized to the value from the Distinct trait, even when the implementation of the Same trait should also apply and cause a conflict?

use core::marker::PhantomData;

trait Distinct {
    const OK: bool = true;
}

trait Same {
    const OK: bool = false;
}

struct TypesNeqInternal<T1, T2>(PhantomData<T1>, PhantomData<T2>);

impl<T1, T2> Distinct for TypesNeqInternal<T1, T2> {}

impl<T> Same for TypesNeqInternal<T, T> {}

pub struct TypesNeq<T1, T2>(TypesNeqInternal<T1, T2>);

impl<T1, T2> TypesNeq<T1, T2> {
    pub const OK: bool = TypesNeqInternal::<T1, T2>::OK;
}

fn main() {
    // Should this work?
    println!("{}", TypesNeq::<usize, usize>::OK);

    // This one works, i.e. fails, fine:
    // println!("{}", TypesNeqInternal::<usize, usize>::OK);
}

(Playground)

Output:

true

Errors:

   Compiling playground v0.0.1 (/playground)
warning: trait `Same` is never used
 --> src/main.rs:7:7
  |
7 | trait Same {
  |       ^^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: `playground` (bin "playground") generated 1 warning
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 1.53s
     Running `target/debug/playground`

steffahn · December 26, 2024, 8:50pm

What's happening here?

The implementation does not apply, because the question of whether a trait implementation applies or not is only answered once generically. If you write this code

impl<T1, T2> TypesNeq<T1, T2> {
    pub const OK: bool = TypesNeqInternal::<T1, T2>::OK;
}

the compiler will wonder “where does TypesNeqInternal::OK come from?”:

could it be Distinct::OK? Sure, that works, because it’s implemented for any two types
could it be Same::OK? Not that wouldn’t be legal here, because whe can’t be sure T1 and T2 always are the same type here.

Basically you can try this manually by replacing the inference with a manual annotation:

TypesNeqInternal::<T1, T2>::OK

this is not fully explicit, you are not explicitly writing down which OK item this belongs to. The traits Distinct and Same are both in scope and both (independently) have associated items with that name, but you’re letting the compiler infer which one it is.

Rust type inference can, in certain cases, infer which trait (or which trait impl) you mean by deducing that there’s only one possible legal choice.

The explicit syntax to write TypesNeqInternal::<T1, T2>::OK while specifying the trait involved would be

<TypesNeqInternal<T1, T2> as Distinct>::OK

or

<TypesNeqInternal<T1, T2> as Same>::OK

Let’s try our options:

first option: Distinct

impl<T1, T2> TypesNeq<T1, T2> {
    pub const OK: bool = <TypesNeqInternal<T1, T2> as Distinct>::OK;
}

(playground) yes that works fine! (I hope you aren’t surprised.)

second option: Same

impl<T1, T2> TypesNeq<T1, T2> {
    pub const OK: bool = <TypesNeqInternal<T1, T2> as Same>::OK;
}

(playground) no that doesn’t work:

error[E0277]: the trait bound `TypesNeqInternal<T1, T2>: Same` is not satisfied
  --> src/lib.rs:20:27
   |
20 |     pub const OK: bool = <TypesNeqInternal<T1, T2> as Same>::OK;
   |                           ^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Same` is not implemented for `TypesNeqInternal<T1, T2>`
   |
help: consider introducing a `where` clause, but there might be an alternative better way to express this requirement
   |
19 | impl<T1, T2> TypesNeq<T1, T2> where TypesNeqInternal<T1, T2>: Same {
   |                               ++++++++++++++++++++++++++++++++++++

For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground` (lib) due to 1 previous error

This results in a compilation error. Rust does (unlike for instance C++) fully type-check generic code, functions, constants, trait implementations, etc… in their generic context. If you wanted to write such an impl, you’d have to restrict the pair of type parameters <T1, T2> further, e.g. remove one and make them the same – or add a TypesNeqInternal<T1, T2>: Same (which the compiler suggest) which would also cover any other cases if additional TypesNeqInternal implementations were added in the future, or by downstream users.

The fact that this option of explicitly writing <TypesNeqInternal<T1, T2> as Same>::OK results in a compilation error in this place in the source code means it is not a viable interpretation of what TypesNeqInternal::<T1, T2>::OK means in this position. It does fail to compile because it can’t be valid in all cases. For this question, it doesn’t matter that some pairs of types T1, T2 do fulfill the Same: TypesNeqInternal<T1, T2> requirement. This decision, that OK from the trait Same can’t be used here is made once, in the generic code, and pre-monomorphization.

Because of the possible “desugarings” (i.e. filling in extra implicit typing information inferred by the type checker / by type inference), i.e. <TypesNeqInternal<T1, T2> as Same>::OK and <TypesNeqInternal<T1, T2> as Distinct>::OK, only one (the latter) is acceptable code in this context, the type checker / inference algorithm of Rust does, in this case, decide to infer that <TypesNeqInternal<T1, T2> as Distinct>::OK is exactly what you meant here. (Note that not everything that “would result in compile error” is necessarily ruled out by type inference, when it comes to resolving methods, or other associated items [an associated constant in this context] for a type; there are certain limitations, and I certainly don’t know them all myself either, off the top of my head).

TL;DR, your code is sort-of “desugared” by type inference / associated-item resolution once and after this, the code is completely equivalent to as if you had manually written it like this instead:

impl<T1, T2> TypesNeq<T1, T2> {
    pub const OK: bool = <TypesNeqInternal<T1, T2> as Distinct>::OK;
}

Only now can we consider

    println!("{}", TypesNeq::<usize, usize>::OK);

this is easy now. Since your code behaves as if you had written

pub const OK: bool = <TypesNeqInternal<T1, T2> as Distinct>::OK;

here at the use-case, the term

TypesNeq::<usize, usize>::OK

is just evaluating to

<TypesNeqInternal<usize, usize> as Distinct>::OK

by that definition, which then further evaluates to true (hopefully unsurprisingly).

Fixing the abstraction

Note that a possible way around the issue of “method (or other associated item) resolution only happening once and in a generic, pre-monomorphization context” would be to replace

pub struct TypesNeq<T1, T2>(TypesNeqInternal<T1, T2>);

impl<T1, T2> TypesNeq<T1, T2> {
    pub const OK: bool = TypesNeqInternal::<T1, T2>::OK;
}

with a macro. E.g.

macro_rules! types_neq {
    ($T1:ty, $T2: ty) => {
        TypesNeqInternal::<$T1, $T2>::OK
    };
}

(playground)

However; as you probably also noticed, even if you define it like this, it still isn’t a super useful macro, because it doesn’t guarantee that it would fail to compiler whenever types aren’t equal, but instead it only fails to compile when the compiler can’t be sure that they’re definitely equal, but when generics are involved, they might turn out to be (definitely) equal, after monomorphization, anyway!

Fixing the false negatives

If you’d rather want to be conservative the opposite way, and define some macro that will fail to compiler whenever the compiler deduces the types might possibly be equal, i.e. only succeed to compile if the types are definitely non-equal, there is an established pattern for defining a macro like that. Please note however, that this macro also still works the usual Rust way, by reasoning about the types provided at its call-site only once in a generic, pre-monomorphization kind of manner. This is an explicit goal of Rust’s design: avoid post-monomorphization errors as much as possible. It’s a bit limiting (as you note in this case), but really for any downstream users of an API, they generally benefit a lot from this design, because post-monomirphization errors are often brittle and often hard to understand.

So while the above types_neq! macro failed to serve as a sort-of static (compiler-time) assertion of “make sure these two are definitely non-equal, or else fail compilation”, the opposite way can use the following idea:

consider trait implementations:

trait HelperTrait {}

impl HelperTrait for u8 {}
impl HelperTrait for i8 {}

this works in Rust (pretty boring trait stuff…) but note that the following does not work:

trait HelperTrait {}

impl HelperTrait for u8 {}
impl HelperTrait for u8 {}

error[E0119]: conflicting implementations of trait `HelperTrait` for type `u8`
 --> src/lib.rs:4:1
  |
3 | impl HelperTrait for u8 {}
  | ----------------------- first implementation here
4 | impl HelperTrait for u8 {}
  | ^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `u8`

For more information about this error, try `rustc --explain E0119`.
error: could not compile `playground` (lib) due to 1 previous error

This is because Rust ensures trait implementations don’t overlap. So the compiler has a mechanism to be like “ensure these types are definitely never equal or else fail”. We can make a macro out of that:

macro_rules! types_neq {
    ($T1:ty, $T2: ty) => {
        trait HelperTrait {}
        impl HelperTrait for $T1 {}
        impl HelperTrait for $T2 {}
    };
}

types_neq!(usize, u8); // ok

(playground)
This isn’t perfect yet,

types_neq!(usize, u8);
types_neq!(usize, i8);

error[E0428]: the name `HelperTrait` is defined multiple times
  --> src/lib.rs:19:9
   |
19 |         trait HelperTrait {}
   |         ^^^^^^^^^^^^^^^^^
   |         |
   |         `HelperTrait` redefined here
   |         previous definition of the trait `HelperTrait` here
...
25 | types_neq!(usize, u8); // ok
   | --------------------- in this macro invocation
   |
   = note: `HelperTrait` must be defined only once in the type namespace of this module
   = note: this error originates in the macro `types_neq` (in Nightly builds, run with -Z macro-backtrace for more info)

because we don’t contain this trait defn. The common pattern to avoid the issue would be to wrap this into an unnamed const. (This is somewhat hacky, but a commonly established for macros nowadays.)

macro_rules! types_neq {
    ($T1:ty, $T2: ty) => {
        const _: () = {
            trait HelperTrait {}
            impl HelperTrait for $T1 {}
            impl HelperTrait for $T2 {}
        };
    };
}


types_neq!(usize, u8);
types_neq!(usize, i8);
// types_neq!(usize, usize); // would fail

Note that this macro approach actually doesn’t support generic arguments at all, though it’s possible to imagine extending the macro to allow a bit of generalization, e.g. some syntax like types_neq!([T] Box<T>, [U] Vec<U>) and the macro translates into impl<T> HelperTrait for Box<T> and impl<U> HelperTrait for Box<U>.

Also, such a macro (not extended for generics) is provided by the crate: static_assertions

Forcing post-monomorphization errors

Rust isn’t immune to post-monomorphization errors. Though type-equality can’t actually be checked post-monomorphization anyways, due to lifetimes. (They are erased early in compilation, so you can never really tell T<'foo> and T<'bar> are different, at a post-monomorphization stage.) But if we rule out lifetimes (by means of restricting ourselves to T: 'static types) it’s not impossible. Rust offers the API around TypeId for this. These aren’t available in const contexts yet though; but to illustrate the concept, here’s what a post-monomorphization check for same-sized-ness could look like

trait NotEqualSize {
    const CHECKED: ();
}
impl<T1, T2> NotEqualSize for (T1, T2) {
    const CHECKED: () = assert!(std::mem::size_of::<T1>() != std::mem::size_of::<T2>());
}


macro_rules! types_neq_size {
    ($T1:ty, $T2: ty) => {
        <($T1, $T2) as NotEqualSize>::CHECKED
    };
}


fn test<T, U>() {
    types_neq_size!(T, U);
}

fn main() {
    types_neq_size!(usize, u8);
    // types_neq_size!(usize, usize); // fails expectedly
    test::<usize, u8>();
    // test::<usize, usize>(); // fails expectedly
}

I would encourage everyone to avoid such code however. As mentioned, in Rust we don’t really like post-monomorphization errors.

Using unstable features on nightly rust, it’s possible to (badly ab-)use TypeId to make the same thing kind of work, for type identity too. (== on TypeId isn’t even unstably available in constants though, we hack our way around this in a definitely-not-guaranteed-future-proof-at-all kind of transmuting way…) Using unstable features, another approach in principle to such functionality would be to use specialization.

kpreid · December 26, 2024, 9:16pm

Even more generally:

All name resolution happens generically; for a given generic function, the concrete type substitution cannot affect where the associated item (or method) is taken from; only the bounds on the generic function can.
Distinct::OK and Same::OK are different items. There is no way to generically refer to “OK, regardless of which trait you get it from”.

You can get effects like these in macros (hence things like “autoref specialization” can work) but you cannot ever get them in generic code.

Delphy · December 26, 2024, 9:43pm

Wow, this is really in-depth, thank you both so much! I wasn't aware that implementations are chosen before monomorphization, so this definitly cleared things up for me!

kpreid · December 26, 2024, 9:56pm

To be more precise, I would say that traits, not trait implementations, are chosen during name resolution, which always happens before the substitution of concrete types into a generic item (I'm not saying "monomorphization" because that's more of an implementation detail, but I'm not sure what the most common or precise term for the other thing is). The existence of trait implementations can affect which trait is picked in a specific piece of code — as you observed, TypesNeqInternal::<usize, usize>::OK is ambiguous and distinct types aren't — but that selection is fixed and cannot be revised using more specific concrete types.

steffahn · December 26, 2024, 11:57pm

Ah, well it’s not only about name resolution though. Trait implementations are also very much … let’s say “handled” before monomorphization. And somewhat not… The full story is that the compiler handles trait implementations twice.

before monomorphization, the compiler does look for trait implementations for every usage of trait items. The goal here is always to check “does an implementation exist?” In most cases, the compiler aims to answer this check either with “yes” or “possibly not” (in the latter case you do get a compilation error).^[1]
This check works with all the existing trait implementations available (in the current crate and all dependencies); as well as with additional local information (generally from where clauses, or : Trait bounds on parameters).
It doesn’t really “choose” the implementation here… but it does infer everything relevant, i.e.
- what is the trait? (in a name resolution sense)
- what is the Self type? (this type can involve local generic type parameters, too, in which not necessarily the concrete type needs to be determined but the type as some unambiguous expression in terms of those generic parameters is okay)
- what are all the additional types^[2] as arguments to the trait (if the trait has additional arguments)?
Even though the check only determines “yes there definitely is some impl for this combination of Self, trait, and arguments”, once all of this is determined, the trait implementation is effectively “fixed”. This is because Rust enforces there to be no overlap
after monomorphization, the compiler looks for trait implementations again. This time however it sees all the concrete types of course; and it only works with actual impl Trait… for Type… { … } items. All the where clauses don’t matter anymore; as it’s after monomorphization we don’t have generic type parameters T to worry about either. Thus you can of course also consider this the moment that the actual impl is “chosen” and this would be @kpreid’s interpretation of that phrase, as far as I understand. impls from downstream crates might be involved here, too, because monomorphization can happen when downstream crates are compiled.
- at this stage, one could ask “what happens if none, or multiple impls are found”?
  - multiple implementations should be impossible due to Rust’s coherence rules (trait impls are checked for overlap; and the orphan rules also ensure that any possible overlap is actually visible on either side)
  - the check before monomorphization should have made sure that “none” is impossible, though do note that that check was able to work with where clauses and such…
    - however, if where clauses were a “lie”, then nobody can ever call use the function being monomorphized, because they are enforced to be true at the call-site – so we shouldn’t ever be monomorphizing this instance of the function anyway, right?
    - additionally, the relevant impl Trait… for Type… { … } will always be visible to the monomorphization, which is also related to orphan rules^[3]
  - if things go unexpectedly anyways then something must have gone very wrong. Probably the checks before monomorphization weren't implemented well or so… the compiler will be unhappy and throw an “internal compiler error”, and there would exist a compiler bug
    - here an example where that used to happen
- So realistically one could also argue that at this stage, trait implementations are just “found” and not “chosen” here, because there’s never any actual choice when the identity of the trait, the Self type, and all parameters, are already fixed/unambiguous.

a few cases of trait checking also ask the question for “possibly yet” vs “definitely not”, such as e.g. checks that prevent overlapping trait impls – this is also a before-monomorphization thing ↩︎
or lifetimes or const generics ↩︎
this is an interesting, subtle point. Let's say you have a trait object dyn Trait<Arg>, and one method foo of this trait has a where clause like where A: Display. And then let's say there’s an impl Trait<Vec<u8>> for String, so here, Arg = Vec<u8> is a non-Display type. Then we use &String as &dyn Trait<Vec<u8>>, so to create a vtable, monomorphization of all the methods of <String as Trait<Vec<u8>>> will happen. The foo method can’t work though; because a concrete impl for fulfilling Vec<u8>: Display can’t be found. In this case, effectively the vtable contains a null pointer for that function. However, any downstream crate now cannot implement Display for Vec<u8> either. This is enforced by orphan rules, of course, but if that wasn’t a rule, then a downstream crate could be like “I’ll call (&some_string as &dyn Trait)::foo now, because Vec<u8> is Display!” That wouldn't be sound, the vtable already exists, we can’t add that method anymore. ↩︎

Topic		Replies	Views
Associated Types and Monomorphisation help	13	110	November 11, 2024
Associated const in traits with const generics	27	7049	March 21, 2021
Trait associated constants at type level help	7	576	January 9, 2022
Confused about traits, generics and/versus associated types help	10	1977	September 25, 2022
"ambiguous associated type" even though it isn't ambiguous help	5	131	October 15, 2024