Specialising Range or overloading ".."

Question

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

Answer 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.