Foreign trait restrictions on native types make generics hard to use

help
1

Traits seem to have been created contemplating a use case where they are implemented as needed for specific types. There is one kind of case where this pattern is vexing, mathematical types.

For example, many crates end up implementing their own 3D and 2D vector types because there is no native vector algebra library in rust. This leads to developers having to convert between types across library uses even when the vast majority of the time the types are equivalent both in terms of byte layout and in terms of operations.

A way around this is to try to make blanket implementations, but these then start clashing with foreign trait constraints. I will give an example that I am struggling with.

I already have a trait that abstracts away Vector types, it works, I am using it. But for long reasons to explain I now need it to work with scalar types, but for it to work I need to be able to index numbers. Consider this snippet that's trying to do just that:

trait Indexable {
    type Item;
    fn at(&self, i: usize) -> &Self::Item;
    fn at_mut(&mut self, _i: usize) -> &mut Self::Item;
}

impl Indexable for f32 {
    type Item = f32;

    fn at(&self, _i: usize) -> &Self::Item {
        self
    }

    fn at_mut(&mut self, _i: usize) -> &mut Self::Item {
        &mut *self
    }
}

impl<T, I> Indexable for T
where T: Index<usize, Output = I> + IndexMut<usize, Output = I>
{
    type Item = I;

    fn at(&self, i: usize) -> &Self::Item {
        &self[i]
    }

    fn at_mut(&mut self, i: usize) -> &mut Self::Item {
        &mut self[i]
    }
}

This won't compile because f32 and the index traits are foreign and so it could technically be that one day the index trait is implemented for f32. However, it is not currently implemented for it and this is precisely trying to unify behaviour between indexable objects like vectors and slices and scalars, which is what I need.

The only alternative would be to make a wrapping type, but if I do a wrapping type, then it automatically requires the user to do explicit casts, but the entire point of what I am doing is to avoid having to do casts between types that are algebraically equivalent.

I feel stuck here.

2

I'd love to hear that explanation. Because that sounds like a design flaw and/or an xy-problem.

3

The explanation is that I am doing a numerical decomposition of an implicit function into smaller, local functions.

Right now the logic acts on a function of the form f(x, y, z) = w. On the current logic, the system is abstract to the underlying scalar.

Now say you want this to work, generically over any vector function. i.e. you want it to also work for example over f(x, y, z) = (w, u, v). And you want it to remain agnostic over the specific scalar type the vector space is represented over.

If you make a new type to wrap around f32 and f64 to make them act as one dimensional vectors, you are forcing explicit conversion at the call site, but this is quite silly, since the system can already work with f32 and f64 without such conversion.

You could make a copy of the existing structure then modify it to deal with vector types, but then you have redundant code.

The cleanest and most ergonomic implementation is one that simply acknowledges that scalar fields are vector fields, and thus the method can be implemented abstractly as a function from a vector field into a different vector field (which will include scalar fields).

4

I'm not in your shoes, but from my perspective it feels a little confusing to treat scalars as vectors. The explicit use of one-dimension vector would be more coherent and wouldn't hide some behaviour.

For the general issue of blanket implementations using external traits in the bounds, sometimes I wonder if those headaches couldn't be solved by allowing specific implementations to overwrite the general blanket implementation if they're in the same crate, as you did above. It would imply that the specific implementation prevails if Index is implemented for f32 one day. There must be cases that make it unsafe or impractical, I suppose, and it would likely open a can of worms when deciding what's more specific and what's more general.

Another workaround is to implement everything manually, possibly using a declarative macro to avoid repeating code, like in the standard library (something I don't like to see because of its lack of clarity). However, here it would force the user of an external type to implement the trait where the type is defined, which isn't possible if they don't own that crate; there, a wrapper must be used.

5

What do you mean by "the system can already work with f32" when you're saying it doesn't compile?

The typical way to do this is to impl From<f32> for Vector<f32, 1>, just like there is impl From<u32> for u64.

6
Expand for an explanation of the motivations (but it doesn't help you make progress).

The orphan rules are designed around balancing the "rights" of crates to make non-SemVer-breaking changes. You don't have the right to impl Index<usize> for f32 -- all those types and traits are in core, so only core does. Thus when checking for implementation overlap, you're not allowed to assume the implementation will never exist -- so that it remains a non-Semver-breaking change for core to add it.

Implementing for a specific upstream type works because upstream can't implement your trait.

Wrapping the implementor works because upstream traits can only self-implement for your local wrapper type via blanket implementation -- which either exists (and you would get an overlap error) or does not (and is a breaking change to add blanket implementations after day 1).

Implementing Index<LocalIndexTy> for SpecificUpstreamTy works for similar reasons (the only way the upstream trait or implementing type can overlap is via a blanket implementation). I use this in one of the possibilities mentioned below.

A future feature may be the ability for core to implement ! Index<usize> for f32, which acts as a SemVer promise to not add the implementation. That would allow your code to compile.

Well, not having a blanket implementation is technically another alternative.

Using a custom index type may also be an option. Generics can help the ergonomics somewhat.

pub struct Idx(pub usize);
impl From<usize> for Idx { ... }
impl From<Idx> for usize { ... }

impl Index<Idx> for f32 { ... }
impl IndexMut<Idx> for f32 { ... }

fn use_it<V: Index<K>, K: From<usize>>(v: &V, idx: usize) -> &V::Output {
    &v[idx.into()]
}

fn main() {
    println!("{}", use_it(&0.2, 123))
}

(Or with your own Index-like trait,) but I don't see much benefit offhand.)

((Or don't special-case scalars, as others have suggested.))

If Index<_>/Indexable on an f32 is supposed to act like a vector, shouldn't it panic on any index input besides 0?

7

Hiding the behaviour inside of the abstraction is the intention though.

8

The current solution works for a generic type that represents scalar fields. It won;t work if I try to generalize it to work with vector fields.

9

The blanket implementation is the goal, I don't want the user to explicitly implement the trait as that defeats the entire goal of the crate, which is to allow algorithms to be agnostic over any vector type that behaves like a vector should (addition, scalar multiplicaiton, etc)...

If Index<_>/Indexable on an f32 is supposed to act like a vector, shouldn't it panic on any index input besides 0?

Probably but I am just trying to get something working right now.

10

The below will not be possible without negative implementations in coherence,[1] specialization, future-overlap-ignoring leaf crates, a big shift in the orphan rules, or other far-away-if-ever language features.

trait Indexable { ... }
impl Indexable for f32 { ... }
impl<T, I> Indexable for T
   where T: Index<usize, Output = I> + IndexMut<usize, Output = I>
{ ... }

So if that's literally the only acceptable outcome, I'm afraid you're out of luck.

With my K: From<usize> example, they don't need to (based on the thread so far). But perhaps it's not applicable to everything you wish to achieve.

  1. and a negative implementation for the specific cases you need ↩︎

11

while negative coherence should work in theory, f32 does not implemen !Index<usize>. you would need an ACP for that.

12

Negative impls effecting coherence is not stable. AFAIK this is the relevant tracking issue.

But indeed, even if stabilized, the negative impl is required upstream. (I mentioned that in a footnote.)