Generic bound over all slice types

So I want to write a custom wrapper type around any sorts of boxed slice types, like a fancier Rc<[T]>. Naively, I'd do something like

struct FancySlice<T>(Rc<[T]>);

However, there's a problem with that: it wouldn't work for str, because FancySlice<str> wouldn't be equivalent to Rc<str>. But I do want str to be a first-class citizen. Same thing for other slice-like newtypes like OsStr.

So I'd like to have something like struct FancySlice<T>(Rc<T>), but now which trait bound do I use to make sure T is actually a slice type?

Why don't you just use Rc<T> with a T: ?Sized bound and then require specific bounds (eg. AsRef<[u8]>) when you actually want to do something with the pointed value?

7 Likes

If you need trait bounds for a set of types that aren’t sufficiently abstracted over already using standard library traits alone, you can always define your own trait. struct FancySlice<S: MySliceTrait + ?Sized>(Rc<S>);

5 Likes

So I tried the option of using bounds only where needed, and while being a bit verbose it got me pretty far already. However, I'm increasingly convinced that a Slice trait would be something good to have in std. It would increase API consistency: For example, as_ptr_range only exists on slices and not str, and OsStr does not even provide as_ptr. from_raw_parts is equally only provided for actual slice types. Of course you can always combine raw parts of a byte array and then convert to str later (as even shown in the documentation: str - Rust), but this only works if you know the concrete type you are working with. There is no way to abstract over that functionality.

There is another benefit a Slice trait would have: Currently, if the user provides a wrong type, they'll get a long type error that <P as Deref>::Target does not satisfy Index<R, Output = <P as Deref>::Target> or something, and only when calling certain methods. With a trait, the error message could be as simple as "this type does not implement Slice, and already in the constructor.

That's arguably trait Slice = Pointee<Metadata = usize>, though that will mean deciding all wide pointers with usize metadata are slice-like.

Yes I have thought about using Pointee<Metadata = usize> for that use case, but I am not comfortable with the assumption that any such pointer types look and behave like slice types. Any function relying on this would have to be marked as unsafe in order to not be unsound. Therefore, such a trait needs to be explicitly implemented by the relevant types.

Future language/std design is better suited to IRLO, but is there anything else you're looking for help accomplishing using Rust today?

(from_raw_parts is already unsafe, by the way, so no loss there. The OsStr considerations are probably because it wasn't even officially decided to own up/commit to the underlying representation always being bytes until quite recently.)

That's no benefit. If you think you want a slice, and we ask why you want one, and you reply "because I want to index into it", then you don't really want a slice. You want precisely something that implements Index instead.

You should be using generics for enforcing and using capabilities, not for restricting to concrete types.

2 Likes

Well, you can build a safe abstraction around it in general. But with Pointee<Metadata = usize> you cannot, because its soundness relies on the assumption that the type actually behaves like a slice, and the caller must uphold it, which is outside of my control as library author.

Well I do want a slice, because I want to do all the things one can do with a slice. Yes I also want to index into it, and I successfully used Index for that.

The thing I need to do now is to check whether a slice is a true sub-slice of another, as in "pointing within a specific memory region" and not "contains the slice based on Eq". For that I'd need a trait that gives me either a pointer+len or a pointer range. I don't know what you'd call it from a capabilities perspective, but I'd call such a trait Slice. (Or maybe such functionality actually belongs to Index/SliceIndex in a way. It's interesting that the trait allows you to get the entire slice, but won't tell you its actual length. This also means that you can't index into the last element, for example. Also I'm not sure but one could probably implement Index for non-slicelike types like linked lists)

(Pointee<Metadata = usize> does not give me the length, it gives me a usize which happens to be the length for some types, but there's no semantic guarantee associated with it which I'd need for using it safely.)

I don't think anything like that exists in std, but it should be easy enough to roll your own. Or, you can directly use <Range<*const T> as RangeBounds>::contains().

You can use indexing by RangeFull for that, and get the slice's length using its len method.

2 Likes

The only types that can do everything that a slice does are either [T] or types that will trivially give you [T], so you can just require that.

You mention wanting to treat str uniformly, but it can't be split at arbitrary indices the way a slice can.


You can do this check for any arbitrary types without needing special bounds:

use std::ops::Range;

fn addr_range<T:?Sized>(obj: &T)->Range<usize> {
    let start = obj as *const T as *const () as usize;
    start .. start+std::mem::size_of_val(obj)
}

pub fn mem_contains<T:?Sized,U:?Sized>(arena: &T, item:&U)->bool {
    let arena = addr_range(arena);
    let item = addr_range(item);
    
    (arena.start <= item.start) && (arena.end >= item.end)
}
3 Likes

So, this is what I've come up with using the size_of_val idea:

pub type OiRc<T> = OiSlice<Rc<T>, T>;
pub type OiArc<T> = OiSlice<Arc<T>, T>;

pub struct OiSlice<P, T: ?Sized> {
    inner: Option<P>,
    slice: *const T,
}

impl <P> OiSlice<P, <P as Deref>::Target>
where
    P: Deref,
{
    pub fn new_wrap(inner: P) -> Self {
        let slice = &*inner as _;
        Self { inner: Some(inner), slice }
    }

    pub fn new_static(slice: &'static <P as Deref>::Target) -> Self {
        Self {
            inner: None,
            slice: &*slice as _,
        }
    }
}

impl <'a, P> OiSlice<P, <P as Deref>::Target>
where
    P: Deref,
    <P as Deref>::Target: 'a,
    P: From<&'a <P as Deref>::Target>,
{
    pub fn new(slice: &'a <P as Deref>::Target) -> Self {
        let inner = P::from(slice);
        Self::new_wrap(inner)
    }
}

impl <P> OiSlice<P, <P as Deref>::Target>
where
    P: Deref + Clone,
{
    pub fn index<R: RangeBounds<usize>>(&self, range: R) -> Self
    where
        <P as Deref>::Target: Index<R, Output = <P as Deref>::Target>,
    {
        Self {
            inner: self.inner.clone(),
            slice: &Borrow::<<P as Deref>::Target>::borrow(self)[range] as _,
        }
    }

    pub fn index_slice(&self, slice: &<P as Deref>::Target) -> Self {
        fn addr_range<T:?Sized>(obj: &T)->Range<usize> {
            let start = obj as *const T as *const () as usize;
            start .. start+std::mem::size_of_val(obj)
        }

        pub fn mem_contains<T:?Sized,U:?Sized>(arena: &T, item:&U)->bool {
            let arena = addr_range(arena);
            let item = addr_range(item);
            
            (arena.start <= item.start) && (arena.end >= item.end)
        }

        if mem_contains(Borrow::<<P as Deref>::Target>::borrow(self), slice) {
            Self {
                inner: self.inner.clone(),
                slice: slice as _,
            }
        } else {
            panic!()
        }
    }
}

impl <P, T: ?Sized> Borrow<T> for OiSlice<P, T> {
    fn borrow(&self) -> &T {
        unsafe { &*self.slice }
    }
}

impl <P: Deref> Deref for OiSlice<P, <P as Deref>::Target> {
    type Target = <P as Deref>::Target;

    fn deref(&self) -> &Self::Target {
        unsafe { &*self.slice }
    }
}

impl <P: Clone, T: ?Sized> Clone for OiSlice<P, T> {
    fn clone(&self) -> Self {
        Self {
            inner: self.inner.clone(),
            slice: self.slice,
        }
    }
}

unsafe impl <P: Deref + Send> Send for OiSlice<P, <P as Deref>::Target> where P: Send { }
unsafe impl <P: Deref + Sync> Sync for OiSlice<P, <P as Deref>::Target> where P: Sync { }

The idea is that you have a shared slice, which you can cheaply sub-slice, but without having to care about compile-time lifetimes.

The core function is index_slice, where you pass in a slice which must be guaranteed to be a sub-slice of the owned value. (The idea is that you can borrow OiSlice as &str, work with that most of the time, and when you're done you can use index_slice to get back a OiSlice to pass around.)

I have no idea about its safety; I'm already happy that it compiles … especially I don't know if the bounds might be too lax, or what may happen if one instantiates it with a dyn Trait instead of a slice type.

This is very obviously unsound.

For example, Self doesn't have any lifetime parameters, and the inherent index() method returns Self, ie. it's effectively a clone, but it doesn't tie the lifetime of the clone to the original. Yet the underlying pointer is only valid as long as the pointee of the original. In general, wrapping a non-owning raw pointer without a lifetime is unsound.

Here's a demo of the unsoundness.

I think the Send + Sync impls are also insufficiently constrained. I'm not even sure if adding P::Target: Send + Sync would be sufficient.

2 Likes

Oh wow, I never intended it to be instantiable with Vec as type for P. But I do see the issue, and how it would also happen with Box. The index function implicitly makes the assumption that cloning will use a reference counter and not copy the contents, which is wrong. Is there a way to enforce this, maybe with Pin?

(Also I think the index function can easily be fixed by indexing into the new cloned value instead of self. The index_slice could maybe work when adding cloned - self as pointer difference to the index??? Sounds scary though)

You should really not make such assumptions while providing a very generic API.

The simplest and most obvious way of making this sound would be to add an explicit lifetime parameter. But at that point, there's absolutely no advantage to re-implementing the functionality of slices. You should just use a regular reference to slice or Rc<[T]> instead.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.