A generic trait Base consists of types that can be classified into multiple non-overlapping classes.
There are corresponding traits SpecialN describing each class. Each special traits are supposed to be non-overlapping with each other, and provides different set of methods on top of the basic ones.
Object safety for the traits is not required. All usage of those traits are within generic parameters.
Difficulties preventing other work-arounds
All classes share sufficiently large number of methods in common, such that cancelling the Base trait would produces way too many boilerplates or macro spamming.
SpecialN traits are exposed to downstream users who are supposed to provide implementations for their custom types, and abstracting away this class of polymorphism by more interface methods is impossible.
(For starters) Most famously, rust's type system does not support negative trait bounds and specialization. Generic implementation for more than one traits will hit the "conflicting implementation, T : Special1 and T :Speical2 could be true at the same time" stuff.
Example Scenario
Copy vs NonCopy traits
RenderObjectElement vs ComponentElement (No render object, different memory layout, different lifecycle, etc)
Code Patterns Requesting Review
I extracted different methods from SpecialN into fn pointers, and stored those fn pointers in a const associated enum GetSpecial.
Handwriting GetSpecial will be tedious if there are many methods. Associated types Base::GetSpecial are used to link to existing types SpecialNAssoc to provide default GetSpecial implementations.
Type gymnastics are done to ensure only correct trait can associate with correct associating types which provide correct GetSpecial variant.
UserExampleType shows how it was used on the user side. The users will have to impl both Base and SpecialN traits for their custom types, and then associate with the correct SpecialNAssoc.
library_example_fn shows how to use this polymorphism.
Is there any pitfall for const fn pointer inlining in rustc? Although const inlining is an implementation detail, I would expect this pattern (const assoc item + enum matching + fn pointer) not to prevent inlining from happening.
that's a really interesting pattern, I have never seen that. it's kind of like erase the type and dispatch on vtables, but at compile time. I'd say I am very impressed. I tried my best to grok the technique, and I can't think of another way to achieve the same effect.
in order to have a single entry point function for the library, I have to figure out what type the argument should use, and here's my failed attempts:
attemp #1: use sum type:
pub enum Either<T1: Special1, T2: Special2> {
Special1(T1),
Special2(T2),
}
// the library entry point is strait forward
pub fn library_example_fn<T1: Special1, T2: Special2>(arg: Either<T1, T2>) {
match arg {
Either::Special1(spec1) => todo!(),
Either::Special2(spec2) => todo!(),
}
}
// but fails at the user side
struct Example;
impl Base for Example {}
impl Special2 for Example {}
fn main() {
// error: can't infer the T2 generic type
library_example_fn(Either::Special2(Example));
}
// workaround: use uninhabitable placeholder type, such as void::Void
use void::Void;
impl Special1 for Void {}
impl Special2 for Void {}
fn special1<T: Special1>(value: T) -> Either<T, Void> { Either::Special1(value) }
fn special2<T: Special2>(value: T) -> Either<Void, T> { Either::Special2(value) }
// draw backs:
// - it might not be practical (or possible?) to implement non-trvial traits for a dummy type
// - user still need to explicit convert user type `Example` to `Either`,
// - the library function cannot use something like `impl Into<...>`
// because we can't define blanket conversions generically, a.k.a.
// the negative trait bound problem: the following will not compile
// impl<T1, T2> From T1 for Either<T1, T2> where ...
// impl<T1, T2> From T2 for Either<T1, T2> where ...
attemp #2: use associated type and associated constant
pub trait Either {
type Special1: Speical1;
type Special2: Speical2;
const IS_SPECIAL1: bool = false;
const IS_SPECIAL2: bool = false;
fn into_spec1(self) -> Option<Self::Special1> { None }
fn into_spec2(self) -> Option<Self::Special2> { None }
}
// the library entry point function
fn library_example_fn<T: Either>(arg: T) {
if T::IS_SPECIAL1 {
let Some(spec1) = arg.into_spec1 else {
unreachable!()
};
}
if T::IS_SPECIAL1 {
let Some(spec1) = arg.into_spec1 else {
unreachable!()
};
}
}
then I found out it had the same problem of attemp #1, i.e. user still need to define the dispatch path manually because blanket implementation is not possible generically, and a placeholder type was still needed.
at this point I realized I can't get rid of the placeholder type, because we don't have higher kinded traits, we must dispatch on actual type instead of type classes (beside the usual negative trait bound problem). what I need but doesn't exists (in pseudo code):
then I realize it's basically equivalent to your original solution, but my code only works when the traits are object safe, and relys on the de-virtualization optimization (I'm not sure if feature(const_trait_impl) can be used here) while your example uses constants dispatch table.
personally I can't think of a "better" solution, surely, there's are alternatives, but I don't think I can call them "better" ones.
as I already mentioned for my failed attempts, since the we have one concrete type at the callsite, the entry point function (we want to it to be polymophic) can only dispatch based on values, not types. so some kind of discriminator is unvoidable, be it an enum type like your solution, or several const IS_SPECIAL_x: bool; flags in my attempts (which can be implicit encoded into the Option<> return types).
I think you are good. although I can't find an explicit documented statement about what optimization passes are guaranteed to run, I don't see any reason the optimizer would not run the constant propagation pass (and dead code elimination after that), as it is a baseline optimization and enables more optmization opportunities for other passes.
a quick glance over the rustc source I found the passes listed here. I'm not a compiler guy, but guessing from the names, many passes might be relevant, like SimplifyCfg, UnreachablePorpagation, ConstProp, SimplifyConstCondition, DataflowConstProp, MatchBranchSimplification, etc.
also, there will be many more optimizations on the backend side, but I don't bother to figure out what passes are enabled.
Can you help me understand this problem better by providing an example? Are you saying that you want your library users to be able to use : Base as a type bound instead of : Special1 + Special2 + ...?
You can use macros to generate those implementations. Look up the differences between enum and dyn Trait (static and dynamic dispatch) to learn more about your options here.
I am not sure sure that a function pointer stored a value that might be mutated at run-time can be inlined at compile time by the compiler.
Probably you should not define the Base trait and wait for trait aliases. The standard library defines Add, Sub, Mul, ... also as individual traits and not a single Integer trait which I believe to be a good choice. This is because not all "addable" types that we want to implement Add for will support all traits captured by Integer. If libraries would implement some functionality for T: Integer instead of T: Add where that was possible, it would not work with String which implements Add but not the hypothetical Integer (what does it mean to divide strings?).
The desire is for the (nonexistent) type bound Special1 ^ Special2 ^ ... where ^ means exactly one of the options applies.
Here's my attempt at this; it uses an uninhabited type that implements all of the specializations to make the invalid Try... conversions work efficiently, and doesn't enforce some of the desired properties (neither disjointness nor existence of a valid conversion; no exhaustiveness checking a conversion sites).
pub trait Base: TrySpecialA + TrySpecialB {}
pub trait SpecialA: Base {
fn a(&self);
}
pub trait SpecialB: Base {
fn b(self) -> Self;
}
// ----------------------
// Conversion traits
pub trait TrySpecialA {
type Special: SpecialA;
fn try_into_a(self)->Result<Self::Special, Self> where Self:Sized { Err(self) }
fn try_ref_a(&self)->Option<&Self::Special> { None }
fn try_mut_a(&mut self)->Option<&mut Self::Special> { None }
}
pub trait TrySpecialB {
type Special: SpecialB;
fn try_into_b(self)->Result<Self::Special, Self> where Self:Sized { Err(self) }
fn try_ref_b(&self)->Option<&Self::Special> { None }
fn try_mut_b(&mut self)->Option<&mut Self::Special> { None }
}
/// Macro to implement the Try... traits
/// Maybe better as a "#[derive(...)] proc macro"
macro_rules! derive_try_special {
{ ($T:ty) @SpecialA TrySpecialA } => {
impl TrySpecialA for $T {
type Special = Self;
fn try_into_a(self)->Result<Self,Self> where Self:Sized { Ok(self) }
fn try_ref_a(&self)->Option<&Self> { Some(self) }
fn try_mut_a(&mut self)->Option<&mut Self> { Some(self) }
}
};
{ ($T:ty) @SpecialB TrySpecialB } => {
impl TrySpecialB for $T {
type Special = Self;
fn try_into_b(self)->Result<Self,Self> where Self:Sized { Ok(self) }
fn try_ref_b(&self)->Option<&Self> { Some(self) }
fn try_mut_b(&mut self)->Option<&mut Self> { Some(self) }
}
};
// And so on for all specialization classes
// Fallback for non-matching traits
{ ($T:ty) @$_:ident $trait:ident } => {
impl $trait for $T { type Special = Invalid; }
};
// User syntax
{ $T:ty: $special:ident } => {
derive_try_special!{ ($T) @$special TrySpecialA }
derive_try_special!{ ($T) @$special TrySpecialB }
// And so on for all specialization classes
}
}
// ---------------------
/// Uninhabited type to represent invalid conversions.
/// "Implements" all specializations, but can't actually be constructed.
enum Invalid {}
impl Base for Invalid {}
impl SpecialA for Invalid {
fn a(&self) { unreachable!() }
}
impl SpecialB for Invalid {
fn b(self) -> Self { unreachable!() }
}
derive_try_special!{ Invalid: None }
// --------------------------
// User code example
pub fn library_example_fn<T: Base>(param: T) {
if let Some(spec_a) = param.try_ref_a() { spec_a.a(); }
else if let Ok(spec_b) = param.try_into_b() { spec_b.b(); }
else { unreachable!("Unknown specialization"); }
}
struct UserExampleType;
impl Base for UserExampleType {}
impl SpecialB for UserExampleType {
fn b(self) -> Self {
println!("UserExampleType::b()");
self
}
}
derive_try_special! { UserExampleType: SpecialB }
fn main() {
library_example_fn(UserExampleType);
}
And here's a slightly different, perhaps cleaner, approach. It also uses an uninhabited type that implements every specialization as a marker, but defines an enum Specialized<...> to specify which particular specialization any given type implements. Because all variants except one of any given Specialized instance are uninhabited, the call to specialize() should compile to a no-op.
pub trait Base: Specialize {}
pub trait Specialize: Sized {
type SpecialA: SpecialA;
type SpecialB: SpecialB;
fn specialize(self)->Specialized<Self::SpecialA, Self::SpecialB>;
fn specialize_ref(&self)->SpecializedRef<'_, Self::SpecialA, Self::SpecialB>;
fn specialize_mut(&mut self)->SpecializedMut<'_, Self::SpecialA, Self::SpecialB>;
}
#[derive(Copy,Clone,Debug,Eq,PartialEq)]
pub enum Specialized<A:SpecialA, B:SpecialB> {
SpecialA(A), SpecialB(B)
}
#[derive(Copy,Clone,Debug,Eq,PartialEq)]
pub enum SpecializedRef<'a, A:SpecialA, B:SpecialB> {
SpecialA(&'a A), SpecialB(&'a B)
}
#[derive(Debug,Eq,PartialEq)]
pub enum SpecializedMut<'a, A:SpecialA, B:SpecialB> {
SpecialA(&'a mut A), SpecialB(&'a mut B)
}
pub trait SpecialA: Base {
fn a(&self);
}
pub trait SpecialB: Base+Clone {
fn b(self) -> Self;
}
/// Macro to implement the Try... traits
/// Maybe better as a "#[derive(...)] proc macro"
macro_rules! derive_specialize {
{ @SpecialA SpecialA } => { type SpecialA = Self; };
{ @SpecialB SpecialB } => { type SpecialB = Self; };
// And so on for all specialization classes
// Fallback for non-matching traits
{ @$_:ident $variant:ident } => { type $variant = Invalid; };
// User syntax
{ $T:ty: $variant:ident } => {
impl Specialize for $T {
derive_specialize!{ @$variant SpecialA }
derive_specialize!{ @$variant SpecialB }
// And so on for all specialization classes
fn specialize(self)->Specialized<Self::SpecialA, Self::SpecialB> {
Specialized::$variant(self)
}
fn specialize_ref(&self)->SpecializedRef<'_, Self::SpecialA, Self::SpecialB> {
SpecializedRef::$variant(self)
}
fn specialize_mut(&mut self)->SpecializedMut<'_, Self::SpecialA, Self::SpecialB> {
SpecializedMut::$variant(self)
}
}
}
}
// ---------------------
/// Uninhabited type to represent invalid conversions.
/// "Implements" all specializations, but can't actually be constructed.
#[derive(Copy,Clone,Debug,Eq,PartialEq)]
enum Invalid {}
impl Base for Invalid {}
impl SpecialA for Invalid {
fn a(&self) { unreachable!() }
}
impl SpecialB for Invalid {
fn b(self) -> Self { unreachable!() }
}
impl Specialize for Invalid {
type SpecialA = Self;
type SpecialB = Self;
fn specialize(self)->Specialized<Self,Self> {
unreachable!()
}
fn specialize_ref(&self)->SpecializedRef<'_,Self,Self> {
unreachable!()
}
fn specialize_mut(&mut self)->SpecializedMut<'_,Self,Self> {
unreachable!()
}
}
// --------------------------
// User code example
pub fn library_example_fn<T: Base>(param: T) {
use Specialized::*;
let specialized = param.specialize();
// Just for demonstration; doesn't need to actually be written ever
assert_eq!(
std::mem::size_of::<T>(),
std::mem::size_of_val(&specialized)
);
match specialized {
SpecialA(spec_a) => { spec_a.a(); }
SpecialB(spec_b) => { spec_b.b(); }
}
}
pub fn library_example_fn_ref<T: Base>(param: &T) {
use SpecializedRef::*;
match param.specialize_ref() {
SpecialA(spec_a) => { spec_a.a(); }
SpecialB(spec_b) => { spec_b.clone().b(); }
}
}
#[derive(Clone,Debug)]
struct UserExampleType;
impl Base for UserExampleType {}
impl SpecialB for UserExampleType {
fn b(self) -> Self {
println!("UserExampleType::b()");
self
}
}
derive_specialize! { UserExampleType: SpecialB }
fn main() {
library_example_fn_ref(&UserExampleType);
}
I have a slightly better idea of the kind of construct you're trying to build. I am curious if you could provide a convincing problem that you believe is best modeled in this way (while keeping it small for illustration purposes). Or are you just exploring a curiosity about what you can do with the Rust type system (totally fine and I support doing such an exploration for learning)?
impl <T: Special1 ^ Special2> would be the same as two blocks impl <T: Special1 + !Special2> and impl <T: !Special1 + Special2>. So I suppose your XOR trait bound is related to negative trait bounds.
I think I can provide an example. Though I don't think it will be small, since a large, user-facing interface is what preventing a different design. This pattern is equivalent to the type promotion patterns in other OOP languages. (Yes, OOP smells. But did not see a better way than type promotion.)
There is a trait Element which downstream users are supposed to implement on their custom type. It contains a few basic logic method such as Element::perform_rebuild and Element::perform_inflate
The trait are managed in instances of Arc<ElementNode<E>> where E: Element. And this ElementNode<E> is a big type that implements some 30-ish complex methods such as rebuild_sync, inflate_async, commit_async, try_poll_rebuild, visit_with_rebuild_context, unmount, occupy etc.
However, there will be subtle logic differences between variants RenderObjectElement, ComponentElement, SuspenseElement. They each provide 1~3 extra methods to expose some distinctive lifecycle functions. Only in some portions of four of ElementNode<E>'s methods, these variants will show different behaviors. The different behaviors refer to their distinctive lifecycle functions being conditionally invoked and composed after checking various resources status. And importantly, those four functions composes those lifecycles in entirely differently ways.
If you abstract each site with a new method, it means four new impossible-to-correctly-impl methods in the interface and leaky abstraction. And there might be more such polymorphic sites in the future.
The above problem already calls for the need of this type of workaround. And the below point is an optional problem that happens to be solvable by the specific associated type workaround in the post.
And there is also different memory layout problem. Ideally, in those sites RenderObjectElement needs to be supplied with a parameter of Option<Self::Render> where Self::Render : Render and trait Render : Sized (No dynamic dispatch). For the same consistency we can supply Option<Never> to ComponentElement and make Never : Render.
To me it seems like you are describing a solution, not the underlying modelling problem. I will try my best to guess what the underlying modelling problem is. Correct me if I'm wrong.
You are writing a library that provides building blocks to build user interfaces. The building blocks, called Elements share some common properties and behavior. You would like to enable users of your library to override this behavior in some way.
Perhaps you can use default trait implementations and dynamic dispatch to achieve this: