More trouble with boxed slices

Continuing the discussion from Nested `Vec` with capacity:

I previously expressed my problems with boxed slices:

Now consider the following code, which works (through deref coercion, I guess [1]):

fn main() {
    let boxed_slice = vec!["Hello", "World"].into_boxed_slice();
    println!("One: {}", &boxed_slice[0]);
    println!("Two: {}", &boxed_slice[1]);
}

(Playground)

Output:

One: Hello
Two: World

But I would like to write a generic function that takes an index-able type that could be a Vec or a Box. Unfortunately, this fails:

fn foo<T, U>(arg: T)
where
    T: std::ops::Index<usize, Output = U>,
    U: std::fmt::Display,
{
    println!("One: {}", &arg[0]);
    println!("Two: {}", &arg[1]);
}

fn main() {
    let vec = vec!["Hello", "World"];
    foo(vec);
    let boxed_slice = vec!["Hello", "World"].into_boxed_slice();
    foo(boxed_slice);
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0277]: the type `Box<[&str]>` cannot be indexed by `usize`
  --> src/main.rs:14:9
   |
14 |     foo(boxed_slice);
   |     --- ^^^^^^^^^^^ `Box<[&str]>` cannot be indexed by `usize`
   |     |
   |     required by a bound introduced by this call
   |
   = help: the trait `Index<usize>` is not implemented for `Box<[&str]>`
note: required by a bound in `foo`
  --> src/main.rs:3:8
   |
1  | fn foo<T, U>(arg: T)
   |    --- required by a bound in this function
2  | where
3  |     T: std::ops::Index<usize, Output = U>,
   |        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `foo`

For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground` (bin "playground") due to previous error

Any advice what to do? Ban Box<[_]> from all my code? :unamused:


  1. See Array and slice indexing expressions in the Rust reference. ↩︎

The right solution would be for the standard library to add IntoIterator, FromIterator, Index, etc. impls to Box<[_]>.

A possible workaround in the meantime would be to require a Deref<Target = [_]> type instead:

fn foo<T, F>(arg: F)
where
    F: Deref<Target = [T]>,
    T: std::fmt::Display,
{
    println!("One: {}", &arg[0]);
    println!("Two: {}", &arg[1]);
}
2 Likes

In this case, I'd probably bound on AsRef<[U]>

fn foo<T, U>(arg: T)
where
    T: AsRef<[U]>,
    U: std::fmt::Display,
{
    let arg = arg.as_ref();
    println!("One: {}", &arg[0]);
    println!("Two: {}", &arg[1]);
}

fn main() {
    let vec = vec!["Hello", "World"];
    foo(vec);
    let boxed_slice = vec!["Hello", "World"].into_boxed_slice();
    foo(boxed_slice);
}
4 Likes

I checked the issue tracker. After a quick search, I didn't find a corresponding issue. I wonder if it would be a possibly breaking change?

I also wonder if it's the "right solution". I have witnessed a lot of boilerplate impls in Rust library code (standard library and third party crates). I wonder if this is a consequence of some shortcomings of Rust's type system (maybe lacking higher kinded types?). I feel like the "root" of the problem is much deeper here.

Mmmm, yeah, I might go for that. It's a slightly more specific bound though, because it requires the type to provide a contiguous slice in memory (rather than just indexing). Also, due to Deref not being transitive per-se (only in method resolution), it sometimes requires annoying extra syntax:

    let vec = vec!["Hello", "World"];
    //foo(&vec); // fails
    foo(&*vec); // we need this

(Playground)


Usually I prefer to avoid AsRef due to some unresolved issues in regard to pointer behavior and transitive implementations (I find that pretty messy). Though I think these problems don't apply here. (edit: Actually you can see how smart pointers may act differently in this Playground example.)

Nonetheless, the AsRef solution is overspecific in the same way as Deref (it requires the type to provide a contiguous slice of memory instead of just being "indexable").

Still, I feel like AsRef might be the best solution in practice.

fn foo<T, U>(arg: T)
where
    T: AsRef<[U]>,
    U: std::fmt::Display,
{
    let arg = arg.as_ref();
    println!("One: {}", &arg[0]);
    println!("Two: {}", &arg[1]);
}

fn main() {
    let vec = vec!["Hello", "World"];
    foo(&vec);
    foo(vec);
    let boxed_slice = vec!["Hello", "World"].into_boxed_slice();
    foo(&boxed_slice);
    foo(boxed_slice);
}

(Playground)

1 Like

I don't see how HKTs would be relevant here. Box<[T]> is a perfectly legitimate container type; it really should implement the iterator and indexing-related traits. You may be right that some of those could be breaking, I don't know precisely of the top off my head; however, I suspect that at least the simple ones should work, because Rust's trait/coherence system tries very hard to not make the addition of trait impls a breaking change.

If this is a concern, then just accept a reference-to-slice directly, which will allow the caller to enjoy deref coercions, given that the argument type is now concrete.

2 Likes

The underlying problem I see is that Box isn't specific in regard to indexing. If we implement Index for Box<[T]>, then we also need to implement Index for Rc<[T]>. And for Arc<[T]>. And for MyFancySmartPointer<[T]>. And for MyOtherFancySmartPointer<[T]>.

And we should make that implementations blanket impls, such that it also works for MyOtherFancySmartPointer<U> where U is not a slice but U: Index,

Does that mean we have to (or at least should?) provide all smart pointers with blanket implementations forwarding trait implementations for their target? And this doesn't only hold for Index but also for IndexMut, Add, BitXOrAssign, etc. etc.

So we have a matrix of all smart pointers and all traits that demand implementations.

I mean… maybe it's reasonable for std to do that. But if I write a third party crate, i don't want to add endless impls for any Derefable type.

Maybe it doesn't have to do anything with HKTs, but I feel like this is a problem of Rust's type system here.

That sounds about right. The author of any particular smart pointer type should be responsible for implementing traits that make sense for their own type. We shouldn't be second guessing 3rd-party code unless the thing is very trivial and obvious. impl<T> From<T> for T is OK. impl<T> FunkyTrait for AllWrappersEver<T> is not OK.

No, I don't think that's desirable. I would personally find that surprising. For example, it would be horrible UX to discover there's a conflicting trait impl with one that std "helpfully" pre-defined for me, and which I now can't override. Worse yet, what if I don't want such an impl, e.g. due to encapsulation concerns, especially in the presence of unsafe code? Then there'd be no way for me to remove such an impl. (No, I don't want to deal with negative impls and the mess they come with when it comes to the compiler trying to reason about my code.)

3 Likes

Regarding FunkyTrait, I agree. However, aren't Deref-able types supposed to be transparent in regard to indexing in particular? It's even built into the language:

For other types an index expression a[b] is equivalent to *std::ops::Index::index(&a, b), or *std::ops::IndexMut::index_mut(&mut a, b) in a mutable place expression context. Just as with methods, Rust will also insert dereference operations on a repeatedly to find an implementation.

(Rust reference on Array and slice indexing expressions)

But in consequence, if we have two speparate crates of which one defines MyOtherFancySmartPointer and another one defines some type X that is Indexable, and further assuming that these two crates have been developed independently, then we'll never be able to write generic code accepting the smart pointer (with type X as inner type) as indexable. Yet we can invoke the indexing operator (as stated in the Rust reference above).

What's your actual use case? I'm asking because I don't think it's your OP:

fn foo<T, U>(arg: T)
where
    T: std::ops::Index<usize, Output = U>,
    U: std::fmt::Display,
{
    println!("One: {}", &arg[0]);
    println!("Two: {}", &arg[1]);
}

fn main() {
    let vec = vec!["Hello", "World"];
    foo(vec);
    let boxed_slice = vec!["Hello", "World"].into_boxed_slice();
    foo(boxed_slice);
}

This is what I consider a toy example, because it presents a use case that rarely comes up in practice: I own a Vec or Box or the like, but I'm going to give it away to do something which does not require ownership. Chances are I'm not going to want to do that! I'm going to try to use my Vec later and get an error.

So, try to fix this code at the call site.

  • foo(&vec) doesn't work (&Vec<_> doesn't implement Index)
  • foo(&*vec) doesn't work (&[_] doesn't implement Index)
  • You have to foo(vec.clone())... or wire up some new type around references I guess

That's why I think that the chances are this function couldn't actually work for what you wanted to do anyway. Or you wanted something entirely different.


I think what you actually wish worked was auto-ref and deref coercion for non-receiver arguments... but the goalposts moved multiple times in this thread so I'm not actually sure.

5 Likes

The actual use case is multivariate_optimization::splitter::Splitter::merge:

pub fn merge<'a, T, I, R>(&'a self, results: R) -> impl 'a + Iterator<Item = T>
where
    I: Iterator<Item = T> + 'a,
    R: Iterator<Item = I>,
{
    let mut results = results.collect::<Box<_>>();
    self.assignments.iter().copied().map(move |assignment| {
        results[assignment]
            .next()
            .unwrap_or_else(|| panic!("iterator for group #{} exhausted", assignment))
    })
}

It's part of a helper module, which I decided to make public though, because it could be helpful in other places too (maybe at some point it could even move to an own crate). See Splitter::new:

Randomly assign indices to fixed number of groups.

Create a Splitter struct, by randomly assigning indices (from 0..source_len) to a fixed number of groups (group_count). The returned struct provides access to the created groups (containing their assigned indices, see groups) and allows merging of iterators (see merge). If group_count is smaller than source_len, the number of groups is set (i.e. limited) to input_len.

In my current use case, this is to reduce efforts for covariance calculation (at the price of ignoring some covariances). The only place I currently use this is in multivariate_optimization::optimize::Solver::recombined_specimens:

Create recombined specimens.

If Solver was created with Solver::new_async, then Futures of specimens are returned instead.

Setting the local_factor to a value greater than 0.0 (but smaller than 1.0) selects a particular specimen with a correspondingly proportional chance to be modified. This allows performing more localized searches. A reasonable value seems to be 0.01 / self.dim() as f64.

The relevant code:

(0..children_count)
    .into_par_iter()
    .map_init(
        || rand::thread_rng(),
        |rng, _| {
            let param_groups_iter =
                sub_dists.iter().map(|dist| dist.sample(rng).into_iter());
            let mut params: Vec<_> = splitter.merge(param_groups_iter).collect();
            let specimen = self.specimens.choose(rng).unwrap();
            let parent_params = specimen.params();
            let factor1: f64 = Standard.sample(rng);
            let factor1 = 2.0 * factor1.powf(local_exp);
            let factor2: f64 = 1.0 - factor1;
            for i in 0..params.len() {
                params[i] = factor1 * parent_params[i] + factor2 * params[i];
                if let SearchRange::Finite { low, high } = self.search_space[i] {
                    if !(low..=high).contains(&params[i]) {
                        return self.random_specimen(rng);
                    }
                }
            }
            (self.constructor)(params)
        },
    )
    .collect()

Here, param_groups_iter is already an iterator, so it's convenient that merge takes an iterator as argument and performs the collect internally. So I don't have any problem right now at this call site.

My consideration really is in regard to the API of Splitter and it's method Splitter::merge. Its inner code boils down to this:

    self.assignments.iter().copied().map(move |assignment| {
        results[assignment]
            .next()
            .unwrap_or_else(|| panic!("iterator for group #{} exhausted", assignment))
    })

assignment is a usize here and results needs to be mutably indexable by usize and be able to call .next, which works on &mut results.

Currently, I accept an Iterator and collect within merge:

    let mut results = results.collect::<Box<_>>();

But if a caller already has a Vec or Box of iterators, then this would be overhead. I feel like it should be done at the caller side.

I explored several alternative types for results:

  • Vec<impl Iterator> (specific to Vec)
  • &mut [impl Iterator] (requires me to write &mut param_groups_iter at the caller side, even though the referenced argument is usually unusable after the call; consuming the argument seems to be more clear instead)
  • &mut R where R: Index<usize> + IndexMut<usize> + 'a + ?Sized (more generic, but even requires extra manual-deref at the caller side, see example below).
-    pub fn merge<'a, T, I, R>(&'a self, results: R) -> impl 'a + Iterator<Item = T>
+    pub fn merge<'a, T, I, R>(&'a self, results: &'a mut R) -> impl 'a + Iterator<Item = T>
     where
         I: Iterator<Item = T> + 'a,
-        R: Iterator<Item = I>,
+        R: Index<usize, Output = I> + IndexMut<usize> + 'a + ?Sized,
     {
-        let mut results = results.collect::<Box<_>>();
         self.assignments.iter().copied().map(move |assignment| {

And then at the caller side:

-                    let param_groups_iter =
-                        sub_dists.iter().map(|dist| dist.sample(rng).into_iter());
-                    let mut params: Vec<_> = splitter.merge(param_groups_iter).collect();
+                    let mut param_groups_iter = sub_dists
+                        .iter()
+                        .map(|dist| dist.sample(rng).into_iter())
+                        .collect::<Box<[_]>>();
+                    let mut params: Vec<_> = splitter.merge(&mut *param_groups_iter).collect();

As you can see, the concrete caller-side gets more messy, even though I could argue that the API is slightly more "correct" (except that it should consume the argument instead of taking a mutable reference to it).

I also tried this:

pub fn merge<'a, T, I, R, X>(&'a self, mut results: X) -> impl 'a + Iterator<Item = T>
where
    I: Iterator<Item = T> + 'a,
    R: Index<usize, Output = I> + IndexMut<usize> + 'a + ?Sized,
    X: BorrowMut<R> + 'a,
{
    self.assignments.iter().copied().map(move |assignment| {
        results.borrow_mut()[assignment]
            .next()
            .unwrap_or_else(|| panic!("iterator for group #{} exhausted", assignment))
    })
}

But then I end up in Type-Annotations-Needed-Hell when trying to call this method.

Or how about the following?

use std::ops::{Deref, Index};
use std::fmt::Display;

fn foo<T, U>(arg: T)
where
    T: Deref,
    <T as Deref>::Target: Index<usize, Output = U>,
    U: Display,
{
    println!("One: {}", &arg[0]);
    println!("Two: {}", &arg[1]);
}

fn main() {
    let vec = vec!["Hello", "World"];
    foo(vec);
    let boxed_slice = vec!["Hello", "World"].into_boxed_slice();
    foo(boxed_slice);
}

(Playground)

(But something feels bad about this. :thinking:)


What feels bad about it, is that it should perhaps be fixed at the call site. @quinedot already brought this up:

So if we keep foo defined in a straight forward way, then we can do:

use std::ops::{Deref, Index};
use std::fmt::Display;

fn foo<T, U>(arg: T)
where
    T: Index<usize, Output = U>,
    U: Display,
{
    println!("One: {}", &arg[0]);
    println!("Two: {}", &arg[1]);
}

struct DerefIndex<T>(pub T);

impl<T, I> Index<I> for DerefIndex<T>
where
    T: Deref,
    <T as Deref>::Target: Index<I>,
{
    type Output = <<T as Deref>::Target as Index<I>>::Output;
    fn index(&self, idx: I) -> &Self::Output {
        self.0.index(idx)
    }
}

fn main() {
    let vec = vec!["Hello", "World"];
    foo(vec);
    let boxed_slice = vec!["Hello", "World"].into_boxed_slice();
    foo(DerefIndex(boxed_slice));
}

(Playground)

But… if I define foo straight forward like that, then that means if a caller happens to have a Box<[T]> then this tremendous effort is needed.

I think I figured out the root of the problem:

trait Foo {
    fn foo(&self);
}

fn borrows_foo<T: Foo + ?Sized>(arg: &T) {
    arg.foo()
}

fn moves_foo<'a, T: Foo + 'a>(arg: T) -> impl FnMut() + 'a {
    move || arg.foo()
}

struct F;

impl Foo for [F] {
    fn foo(&self) {
        println!("FOOO!");
    }
}

fn main() {
    let f = vec![F];
    //borrows_foo(&f); // doesn't work, but that's not a problem
    borrows_foo(&*f); // because we can do this

    // but the following isn't easily solvable
    // because `[_]: Foo` is `!Sized`:
    //moves_foo(*f);
    
    // We must do this, which is pretty unwieldly:
    struct DerefFoo<T>(pub T);
    impl<T> Foo for DerefFoo<T>
    where
        T: Deref,
        <T as Deref>::Target: Foo,
    {
        // This gets nasty if `Foo` has more methods:
        fn foo(&self) {
            self.0.foo()
        }
    }
    moves_foo(DerefFoo(f))();
}

(Playground)

I don't need auto deref. I think the problem here is that I can't even manually dereference here (because the type that implements the trait in question is !Sized). The only way to work around this is to provide a newtype wrapper, and that's arguably very ugly.

Any thoughts?


I think the solution is this:

fn borrows_foo<T: Foo + ?Sized>(arg: &T) {
    arg.foo()
}

fn moves_foo<'a, T>(arg: T) -> impl FnMut() + 'a
where
    T: Deref + 'a, // we need `Deref` here
    <T as Deref>::Target: Foo, 
{
    move || arg.foo()
}

fn main() {
    let f = vec![F];
    borrows_foo(&*f); // manually dereference here
    moves_foo(f)();
}

(Playground)

I had that idea before (which was basically an improvement to @H2CO3's suggestion), where I wrote:

But having re-thought about this, I think it's actually the right solution to use Deref as a bound. It might actually be one of the rare cases where a Deref bound makes sense.


In terms of my real-world API, the solution would be this: GitHub commit.


However, there remains a problem with this solution: It doesn't work out well when Foo is also implemented on Sized types (which IndexMut could be). Then you would have to provide a dummy wrapper in order to pass values to moves_foo. :face_with_diagonal_mouth:

#[derive(Clone)]
struct G;

impl Foo for G {
    fn foo(&self) {
        println!("FOOOGOOO!");
    }
}

fn main() {
    let f = vec![F];
    borrows_foo(&*f); // manually dereference here
    moves_foo(f)();
    let g = G;
    //moves_foo(g); // doesn't work
    moves_foo(std::borrow::Cow::<G>::Owned(g))(); // workaround
}

(Playground)

So I feel like the real problem isn't solved yet in a nice and clean way. Maybe it's impossible to solve.

When the generalization roadblock can be summarized as "I can use the trait functionality with this variable" but "passing the variable as a function argument doesn't satisfy the trait bound," then yeah, the generalization you're trying to get into the API is autoderef.

Could the compiler automatically synthesize trait implementations for receivers for object-safe traits? Theoretically yes, and it's generally considered good practice to provide them, at least for the fundamental receivers (&T, &mut T, and Box<T>) when a trait is intended to be used polymorphically. Impl delegation might eventually make writing those impls easier, and thoughts around dyn trait declarations sometimes do synthesize forwarding impls. But traits not designed for polymorphic use often don't provide forwarding impls, and adding them after the fact would actually be API breaking due to the types' fundamental nature[1].

My base advice in cases like these is to avoid generalizing for use cases you don't have, though. Unless you're actually using the extra flexibility afforded by a more generic API, you're making it harder to work with for no gain. It's perfectly acceptable for some code to be a little inefficient, for callers to sometimes need to write .into(), to sometimes require adapters to massage data into the requested shape.

I am self admittedly overly generics-pilled. I enjoy making my code work in more conditions and golfing down required allocations and indirections. But it's just as important to be able to identify when the generalization effort is adding friction rather than removing it; it's okay for APIs to be "dumber" when cleverness results in complexity.

Oh, and if it's a stack value, just use Vec<T> instead of Box<[T]>. One usize on the stack is much cheaper than forcing a shrink_to_fit reallocation. The cases where you should actually prefer to use Box<[T]> do exist, but are fairly few and far between, and generally involve it being part of a larger data structure.


  1. Specifically, you're allowed to implement an upstream trait for &T (or &mut T or Box<T>), so long as T is a local type. Thus, adding new "blanket" implementations which would conflict with such a downstream impl is a breaking change. ↩︎

3 Likes

My auto/deref comment was more about the borrowing case, which basically relates to how one should prefer &[T] over &Container<T> etc, which leads to performing &*owned_container or the like at the call site. And why T: AsRef<U> is a bad yet endemic pattern when you only need &U. But you say in your playground that's not a problem (and I agree), so :+1: I suppose.

On the other hand, it's still of adjacent relevance. The reason I got to that point in my thinking is you asserted things like Deref implementors "supposed to" be transparent around Index specifically (they're not, the docs you quoted were just about method dispatch generally and would apply to any trait), and then noting that you could still index a concrete type but couldn't pass it to the generic function in some cases...

...and the reason you could index the concrete type is because indexing performs method-receiver auto/deref coercion on the concrete type. You can't do that on the generic if you haven't declared the necessary abilities via trait bounds...

...which is basically what this is. I considered this approach too. It had some perceived downsides in my mind, but I think the ones I was considering don't really apply to your use case.

  • You don't need ownership in the function, you just consider it more logical on the assumption you'll be emptying iterators and emptied iterators aren't reusable; so it's ok that this doesn't force ownership

  • This pattern also accepts &mut Indexable so if the caller has an Indexable that doesn't implement the new Deref constraint, they are not necessarily out of luck either

...oh hey look, you thought of it too! Heh. You can just foo(&g)() in the playground. You don't need the Cow because you don't actually need ownership. The caller might in some circumstances -- to avoid lifetime problems. But then there's still the workaround Cow::Owned or another custom "just here for the Deref" wrapper.


I haven't thought of any better[1] patterns for your use case [2]. It's more general than taking a &mut ("the borrowing case"), the Deref is basically acting like a non-generic Borrow to avoid being too generic for inference, the Sized concrete implementors of Index you've mentioned implement Deref too, it works around the problem of Box<[_]> not implementing Index, callers can work around the Deref requirement if need be.

If Box<[_]> gets Index in the future, you won't be able to change the bounds to only take types that directly implement Index (without it being a breaking change), if you care about that.

The other vantage point[3] is that it's on the implementors of "smart pointers"[4] to implement Index when it makes sense (they are foreign types and Index is a foreign trait afterall), stick with your direct owned Index bounds, and lobby for Box<[_]> to implement the trait. If you still wanted to supply a workaround in the meanwhile, it'd probably be in the form of a newtype.

The other main alternative to juggling std trait bounds is a new trait with a blanket implementation of your choosing plus concrete implementations to fill in gaps as required.


  1. in terms of generic for the sake of generic; covering the concrete types mentioned so far ↩︎

  2. without introducing new traits ↩︎

  3. without introducing new traits ↩︎

  4. whatever that means ↩︎

1 Like

Well, even if "auto deref" would solve the problem (maybe with other implications/downsides), I'd be satisfied if I could manually deref like I can do with borrows_foo in this Playground (which doesn't work with moves_foo easily). That's what I tried to say in my quote above.

Having to provide these seems to be like a lot of boilerplate whenever you create and implement your own traits. So you basically mean I should always do this?

pub trait Foo {
    fn foo(&self);
}

impl<T> Foo for &T
where
    T: Foo + ?Sized,
{
    fn foo(&self) {
        (**self).foo()
    }
}

impl<T> Foo for &mut T
where
    T: Foo + ?Sized,
{
    fn foo(&self) {
        (**self).foo()
    }
}

impl<T> Foo for Box<T>
where
    T: Foo,
{
    fn foo(&self) {
        (**self).foo()
    }
}

impl<T> Foo for std::rc::Rc<T>
where
    T: Foo,
{
    fn foo(&self) {
        (**self).foo()
    }
}

impl<T> Foo for std::sync::Arc<T>
where
    T: Foo,
{
    fn foo(&self) {
        (**self).foo()
    }
}

impl<T> Foo for std::borrow::Cow<'_, T>
where
    T: Foo + ToOwned,
{
    fn foo(&self) {
        (**self).foo()
    }
}

// … when does this end?

(Playground)

I can't follow here. Which "traits" do you mean specificially? Something like Foo above? Or something like Box? I assume you are referring to fundamental type constructors here? Why would adding impl<T> Foo for Box<T> be a breaking change for that crate in the above Playground?

Would it be a breaking change for std to add an impl<T, I: SliceIndex<[T]>> Index<I> for Box<[T]>, like @H2CO3 proposed in the very first response?


I understand. It's a bit tragic from an aesthetic p.o.v. though. And it's not only aesthetic because people keep running into friction (though I admit that when you try to write your code more "smartly" you seem to run into friction more often than if you just use Vec<T> and don't care).

I'm exploring this problem not just to provide a nice API in the real-world use case (it's still a goal though), but also to understand better how to write idiomatic Rust in general. It's not the first time I ran into limitations of Rust's type system, or into questionable or missing implementations of traits in std. I still think that Rust's type system overall does a good job, but… something bugs me about it because I keep running into problems here and there. I think I just have to deal with Rust not being perfect here. I still would like to understand, however, how to deal with the particular scenario(s) discussed here, in order to improve my relationship with Rust :grin:. I'll try to come up with some concrete questions on that matter at the end of this post.

But collecting directly into a Box shouldn't involve shrinking if the iterator provides a correct size_hint, right?

A potential problem I see with the borrowing case is that you can't store the returned type along with the owned_container somewhere (because safe Rust doesn't allow self-referential types).

I already accept writing &* where needed. But always infecting a return value with a lifetime is a different issue. This might not be a problem in my particular use case though, because the return value is infected with a lifetime 'a anyway (because of working on &'a self).

The docs I quoted are not just about method dispatch but about "index expressions" in particular. But I understand how this is the same as method invocation: I can invoke a method of a trait implemented by the Deref::Target type, but this doesn't make my outer (Deref) type implement the trait. The same holds for indexing operations (which get forwarded) and fulfilling the Index/IndexMut traits (which get not forwarded). So Rust is "consistent" here. Yet it causes friction in both cases (not that I have a solution for it).

&mut Indexable would likely be the workaround to choose (when needed), especially considering that the returned impl 'a + Iterator is lifetime-infected anyway (due to &'a self). So I feel more confident with that approach now (GitHub link again).

I think in my concrete case, the caller might never have to (as I said, the impl 'a + Iterator captures a lifetime anyway).

:unamused:

… might not be such a big deal, but I'll think about it. Thanks for the warning. (It's not an important crate and I'm still at 0.0.1 but maybe at some point I want some more stability.)

I think if std implemented Index for Box<[_]>, I'd rather get rid of the Deref approach. Is that a breaking change for std? For smart-pointers which fail to provide that implementation, there is still the "newtype escape hatch".

Oh, that is an interesting solution too! But I think in this case it wouldn't cover more cases than what I can cover with the Deref approach.


In this post, I promised to get back to some concrete questions:

  1. When I implement a generic smart-pointer, should I provide forwarding implementations for all traits in std? (Note that it's a lot of boilerplate.) To give an example, should deref_owned::Owned provide a blanket implementation for Index, IndexMut, Shl, Shr, AddAssign, Not, etc.?
  2. When I provide a new trait Foo, when should I add blanket implementations for &T, &mut T, Box<T>, Rc<T>, etc. where T: Foo or T: Foo + ?Sized, respectively?
  3. What is generally/usually the best way to consume a list of values that don't need to be extended, assuming I need random access[4]? Just use Vec<T> and forget about Box<[T]>?

Not sure if I forgot any question.

Anyway, your responses have already been very helpful for me to understand the practical issues with Rust's type system better (and why I experience certain friction here and there). :heart:


Update:

I tried to answer some of these questions on my own by looking into what std does and what the language provides:

struct Smart<T>(pub T);

impl<T> Deref for Smart<T> {
    type Target = T;
    fn deref(&self) -> &T {
        &self.0
    }
}

fn add<T: Add<T>>(a: T, b: T) {}
fn cmp<T: Ord>(a: T, b: T) {}
fn idx<T: Index<usize>>(x: T) {}

fn main() {
    //add(Rc::new(1), Rc::new(2)); // doesn't work
    //Rc::new(1) + Rc::new(2); // doesn't work
    add(&1, &1); // there are concrete implementations though
    cmp(Rc::new(1), Rc::new(2)); // `Rc` forwards `Ord`
    Rc::new(1) < Rc::new(2); // this wouldn't work otherwise, …
    //Smart(1) < Smart(2); // …because `Smart` is dumb
    //cmp(Smart(1), Smart(2)); // also fails because `Smart` is dumb
    idx([1]); // arrays implement `Index`
    //idx(Rc::new([1])); // `Rc` doesn't forward `Index`
    Rc::new([1])[0]; // but the operator gets forwarded (opposed to `+`)
    Smart([1])[0]; // so this works too
}

(Playground)

So trying to answer my question #1 above:

  1. When I implement a generic smart-pointer, should I provide forwarding implementations for all traits in std?

Following what std does, a generic smart-pointer shouldn't forward all traits. Exceptions are probably Ord (as well as PartialOrd, Eq, PartialEq), Display (as well as Debug), maybe Default and Hash. But not Add, Sub, etc.

A curious case, however, is Index. The standard library decided to not make Rc, Arc, etc. forward this. (Instead, it provided a concrete implementation for [T].) The language, in contrast, will perform Deref based lookup for the index operators when indexing a smart pointer. But this breaks when using Index as a trait, as shown throughout this thread.

Index and IndexMut differ fundamentally from all the other traits in std::ops (except Deref and DerefMut), because only for these, the language has built-in forwarding (when a type implements Deref). This explains why missing generic implementations of Index for smart pointers don't usually cause any trouble – because unless you want to use Index as a trait bound, you'll not experience any trouble (see Playground above, where the expression Smart([1])[0] works fine, even though Smart doesn't provide a forwarding implementation for Index).

I feel like std should provide a generic impl<U: Deref<Target=T>, T: Index<I>, I> Index<I> for U, but I'm not sure if that would cause trouble. Likely it's impossible to add such an implementation now (I don't really overview the consequences).

Given the fact that none of std's generic smart pointers implement Index, I feel like doing so in third party crates would be unidiomatic.

I guess in the end, Index is just broken as it is right now (when it comes to generics). Or maybe "broken" is a too harsh word, and you could say "not suitable for generic use". Hypothesis: Maybe Index should be avoided in bounds and only used for operator overloading then?

Following that hypothesis and getting back to my original problem, I wonder if @2e71828's proposal to use AsRef<[U]> is the way to go then. However, I previously argued that AsRef isn't meant for dereference (see also PR #99460 and Issue #45742). This leads me to the conclusion that maybe Borrow<[U]> would be the "cleanest" solution (Playground).


In regard to the actual use-case, it would look like this: GitHub commit.


  1. Specifically, you're allowed to implement an upstream trait for &T (or &mut T or Box<T>), so long as T is a local type. Thus, adding new "blanket" implementations which would conflict with such a downstream impl is a breaking change. ↩︎

  2. without introducing new traits ↩︎

  3. whatever that means ↩︎

  4. If I don't need random access, I can take an Iterator, of course. ↩︎