4

I have a little library where I can define integer types. These are intended for type-safe indexing into arrays and strings in the kind of algorithms I often write. For example, I can use it to define an offset type, Offset and an index type, Idx such that you can get an Offset by subtracting two Idx, you can get Idx by adding or subtracting Offset, but you cannot for example multiple or add Idx.

let (i,j): (Idx,Idx) = ...;
let offset: Offset = j - i; // Subtracting indices gives an offset
let k: Idx = j + offset; // Adding an offset to an index gives an index
// let _ = i + j; -- You can't add indices

I managed (with some difficulty) to implement std::iter::Step so I can also iterate through a range of indices

for k in i .. j { /* ... */ }

but now I've set my eyes on a higher goal: I also want to use ranges of these types to slice into sequences

let v: Vec<sometype> = vec![...];
let w: &[sometype] = &v[i..j]; // Slice with a range of Idx

This should be a simple matter of implementing std::ops::Index and std::ops::IndexMut, except that the type system won't let me implement

impl<I,T> std::ops::Index<std::ops::Range<I>> for Vec<T>
where I: /* my types */
{ ... }

for a wrapper type, or a generic

impl<I,T> std::ops::Index<std::ops::Range<Wrapper<I>>> for Vec<T>
where I: /* my types */
{ ... }

where Wrapper is the type I actually use and I a trait that helps me write generic code.

The problem is that both Index and Range are defined outside of my crate, so this kind of specialisation is not allowed. Or is it?

Is there any way that I can implement a trait for a generic type outside my crate when its generic parameters are from within my crate?

Or, better still, is there any way to tap into the syntactic sugar of the .. operator, so I can get a wrapped type? What I really want is to wrap Range to get the same behaviour and then some. I can do that by wrapping Range and implementing Deref, but if I go that route, I lose the syntactic sugar of the .. operator.

It is not a big problem, but I can imagine some confusion when you could write

for k in i .. j { /* ... */ }

like you can for the built-in types, but you have to use

let w: &[type] = &v[range(i,j)];

for slicing. It gets even more cumbersome if I want to allow slices such as i.., ..j to be wrapped. (The .. slice doesn't matter here, it won't get my types anyway). If I did that, I would need constructors for three types of ranges, or some ugly wrapping using Option, I think.

The .. syntactic sugar is really neat, but from what I have explored you just cannot use that much for ranges of your own types. You can define ranges and you can, with some hacking, iterate through them, but you can't index with them.

Tell me I'm wrong, or let me know if there are any tricks that gets the job done, or even half-done. Or, if this is indeed impossible, let me know so I can stop wasting time on it and write a wrapper class and give up on the .. operator.

Update I have put a simplified example in playgrounds

13
  • I think this should be possible. What error are you running into? Can you provide a more complete example? BTW "specialization" is the wrong word for what you're trying to do (just implement a trait with generics). Specialization is when you're providing a special implementation for a subset of an existing implementation.
    – PitaJ
    Feb 7, 2022 at 15:48
  • 2
    Your best bet here is to newtype Vec.
    – eggyal
    Feb 7, 2022 at 15:57
  • 1
    I can do it using macros for sure. That is how I implement the operators for the types, and how I implement single index access. I just think that once there are generics, I should be able to use them, rather than use macros as if I was back in C. Feb 7, 2022 at 19:29
  • 1
    If you don't want to implement a newtype of Vec, you could instead create an extension trait adding various convenience methods for your usage, like a custom get(&self, range: Range<Yourtype>)
    – PitaJ
    Feb 7, 2022 at 21:52
  • 1
    The Range operator exists for all types T, yes. But that's not the impl you care about (and isn't really an impl at all), you really care about SliceIndex (or Index<Range<T>>) which is only implemented for Ranges of primitive types. So it's not specialization, because it wouldn't conflict which any existing impls. You problem is orphan rules, and specialization refers to a specific nightly feature in rust.
    – PitaJ
    Feb 8, 2022 at 5:10

2 Answers 2

3

No, you can't.

By definition of the orphan rules:

Given impl<P1..=Pn> Trait<T1..=Tn> for T0, an impl is valid only if at least one of the following is true:

  • Trait is a local trait
  • All of
    • At least one of the types T0..=Tn must be a local type. Let Ti be the first such type.
    • No uncovered type parameters P1..=Pn may appear in T0..Ti (excluding Ti)

Only the appearance of uncovered type parameters is restricted. Note that for the purposes of coherence, fundamental types are special. The T in Box is not considered covered, and Box is considered local.

Local trait

A trait which was defined in the current crate. A trait definition is local or not independent of applied type arguments. Given trait Foo<T, U>, Foo is always local, regardless of the types substituted for T and U.

Local type

A struct, enum, or union which was defined in the current crate. This is not affected by applied type arguments. struct Foo is considered local, but Vec<Foo> is not. LocalType<ForeignType> is local. Type aliases do not affect locality.

As neither Index nor Range nor Vec are local, and Range is not a fundamental type, you cannot impl<T> Index<Range<...>> for Vec<T>, no matter what you put in the place of the ....

The reason for these rules is that nothing prevents Range or Vec from implementing impl<T, Idx> Index<Range<Idx>> for Vec<T>. Such impl does not exist, and probably never will, but the rules are the same among all types, and in the general case this definitely can happen.

You cannot overload the range operator either - it always creates a Range (or RangeInclusive, RangeFull, etc.).

The only solution I can think about is to create a newtype wrapper for Vec, as suggested in the comments.

If you want your vector to return a wrapped slice, you can use a bit of unsafe code:

use std::ops::{Index, IndexMut, Range, Deref, DerefMut};

#[repr(transparent)] // Because of this we can soundly cast `&{mut }[T]` to `&{mut }MySlice<T>`.
pub struct MySlice<T>([T]);

impl<'a, T> From<&'a [T]> for &'a MySlice<T> {
    fn from(v: &'a [T]) -> &'a MySlice<T> {
        unsafe { &*(v as *const [T] as *const MySlice<T>) }
    }
}
impl<'a, T> From<&'a mut [T]> for &'a mut MySlice<T> {
    fn from(v: &'a mut [T]) -> &'a mut MySlice<T> {
        unsafe { &mut *(v as *mut [T] as *mut MySlice<T>) }
    }
}

impl<T> Index<usize> for MySlice<T> {
    type Output = T;
    fn index(&self, idx: usize) -> &Self::Output { &self.0[idx] }
}
impl<T> IndexMut<usize> for MySlice<T> {
    fn index_mut(&mut self, idx: usize) -> &mut Self::Output { &mut self.0[idx] }
}

impl<T> Index<Range<usize>> for MySlice<T> {
    type Output = MySlice<T>;
    fn index(&self, idx: Range<usize>) -> &Self::Output { self.0[idx].into() }
}
impl<T> IndexMut<Range<usize>> for MySlice<T> {
    fn index_mut(&mut self, idx: Range<usize>) -> &mut Self::Output { (&mut self.0[idx]).into() }
}
// And so on, for all range types...

pub struct MyVec<T>(pub Vec<T>);

impl<T> Deref for MyVec<T> {
    type Target = MySlice<T>;
    fn deref(&self) -> &Self::Target { self.0.as_slice().into() }
}
impl<T> DerefMut for MyVec<T> {
    fn deref_mut(&mut self) -> &mut Self::Target { self.0.as_mut_slice().into() }
}
4
  • I'd rather not solve this by implementing my own sequences. I often need to take slices of sequences in divide-and-conquer recursions, so I want my types to work on slices. I suspect it will be quite cumbersome to have to wrap and unwrap slices everywhere in the code, to the point where this exercise will be useless. At least I would have to automatically wrap things, so if v: MyVec then w = &v[MyRange] would give me a wrapped MyWrapped([T]) somehow, and &w[MyRange] would give me another wrapped slice. I can give it a try... Feb 8, 2022 at 11:03
  • No, maybe that idea is dead on arrival simply because the Index trait requires me to return a reference, so I can't wrap that... I'm slowly coming to the realisation that Rust is designed, purposely or accidentally, to prevent me defining new index types... Feb 8, 2022 at 11:20
  • @ThomasMailund Quite wrong. Even rustc defines its own index types for each type to prevent mistakes. But it is indeed impossible to achieve the same amount of comfort. You can wrap the range type if you prefer. I'll edit the answer to show how you can wrap slices, though this require a bit of unsafe code. Feb 9, 2022 at 2:46
  • My comment was (mostly) intended as a joke, and of course I can get there if I give up on some syntactic sugar. I just don't want to ;) Thanks a bunch for the link, I wasn't aware of indices there, and that looks like a perfect place to find inspiration. Also thanks for the updated answer; I can definitely use that. Feb 9, 2022 at 3:13
1

I have a sort-of solution, involving a new Range in my own crate, and a lot of hacking. The full code is in playgrounds. It is a slow compile (lots of type inference, I guess), so you might have to download it to run it. Sorry about that.

There is a bunch of meta-programming to define new index types, but the gist of it is that I use a trait to specify different types and a wrapper to hold the underlying numbers.

// A dummy type to illustrate the types I want to work with
// Different TypeInfo will give me different and incompatible
// types that wrap integers, which is what I want.
trait TypeInfo {
    type WrappedType: num::PrimInt;
}

// A wrapper wraps the type from the TypeInfo trait;
// the TypeInfo trait specifies the type when I define what
// operations I will allow.
#[derive(Debug, Clone, Copy)]
struct Wrapper<T: TypeInfo>(T::WrappedType);

Then I have another trait to specify if a given index is allowed to index in a given sequence type.

// Trait that determines which sequences an index can index
trait CanIndex<Seq: ?Sized> {}

although I am not sure if this is the right solution for that...

Anyway, for most of Rust's types, I need to use usize for indexing, so I have another trait that specifies if I have such a bugger.

// For indexing... (You get too deeply nested genetics without it)
// Maybe I can get rid of it, but that is for another day...
pub trait IndexType {
    fn as_index(&self) -> usize;
}
impl<TI> IndexType for Wrapper<TI>
where
    TI: TypeInfo<WrappedType = usize>,
{
    fn as_index(&self) -> usize {
        self.0
    }
}

While it doesn't make me happy to have to implement Index for every sequence type, at least every generic one, I don't think there is any way around that. For single indices, it is just this:

// Generic index implementation. (The real situation is a bit more
// complicated because I need to specify which types each index type
// is allowed to index, but this is the gist of it)

// Indexing a single element in a vector
impl<TI, T> std::ops::Index<Wrapper<TI>> for Vec<T>
where
    TI: TypeInfo,
    TI: CanIndex<Vec<T>>,
    Wrapper<TI>: IndexType,
{
    type Output = T;
    fn index(&self, i: Wrapper<TI>) -> &Self::Output {
        &self[i.as_index()]
    }
}

// Indexing a single element in a slice
impl<TI, T> std::ops::Index<Wrapper<TI>> for [T]
where
    TI: TypeInfo,
    TI: CanIndex<[T]>,
    Wrapper<TI>: IndexType,
{
    type Output = T;
    fn index(&self, i: Wrapper<TI>) -> &Self::Output {
        &self[i.as_index()]
    }
}

For my new Range type, I went with an enum. It will be more convenient for the things I want to do with it.

// My own type of ranges, now that I cannot use the built-in type...
/// Wrapper of Range that we can work with within Rust's type system
#[derive(Clone, Copy)]
pub enum Range<Idx> {
    Closed(Idx, Idx), // start..end
    Left(Idx),        // start..
    Right(Idx),       // ..end
    Full,             // ..
}

The type needs a constructor, which is complicated by Rust creating different types when you use the .. operator, but you can do it like this:

pub trait GenRange<R, Idx> {
    fn range(r: R) -> Range<Idx>;
}
/*

 Now implement that trait for the different range types.
 Is there a better way?

 */

// Now I can build ranges with this function:
pub fn range<Idx, R: GenRange<R, Idx>>(r: R) -> Range<Idx> {
    R::range(r)
}

With this, I can also implement indexing for ranges. I can use CanIndex<> to specify that I can index with ranges for any type that I can index individual items with.

impl<Idx, T> std::ops::Index<Range<Idx>> for Vec<T>
where
    Idx: IndexType,
    Idx: CanIndex<Vec<T>>,
{
    type Output = [T];
    fn index(&self, r: Range<Idx>) -> &Self::Output {
        match r {
            Range::Closed(start, end) => &self[start.as_index()..end.as_index()],
            Range::Left(start) => &self[start.as_index()..],
            Range::Right(end) => &self[..end.as_index()],
            Range::Full => &self[..],
        }
    }
}

impl<Idx, T> std::ops::Index<Range<Idx>> for [T]
where
    Idx: IndexType,
    Idx: CanIndex<[T]>,
{
    type Output = [T];
    fn index(&self, r: Range<Idx>) -> &Self::Output {
        match r {
            Range::Closed(start, end) => &self[start.as_index()..end.as_index()],
            Range::Left(start) => &self[start.as_index()..],
            Range::Right(end) => &self[..end.as_index()],
            Range::Full => &self[..],
        }
    }
}

It got rather complicated, so I need to clean it up as much as I can, but at least I am beginning to believe that it can be done. And once that is done, I need to figure out a good way to add the usual std::ops::Range interface to Range. But this will do for today.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.