How do you make a 2D collection with 2d views?

help
1

Hey all. So what I'd like to do is to have a bunch of values, u8s or whatever, that are "2D", so you index them with (x,y) indexes. Easy. But what I'd also like to do is to have "slice-like" views into the whole grid. This seems next to impossible to do ergonomically, because the Traits from std::ops don't really seem to allow for it.

Now we all know that Vec derefs to a slice, and String derefs to a str, but the way that it happens seems to border on magic. Slice seems to be a builtin fat pointer that the compiler just knows how to handle, and &str also seems to be a semi-magical type and I'm not sure where the data "inside" the str value is even living when you return a &str.

To slice a 2d thing properly, you'd need more than (ptr/len), you need (ptr/height/width/pitch); I'm not sure how to have a "base" type that derefs into a (ptr/height/width/pitch) blob, because the sub-slice struct doesn't live long enough. I went around on this whole thing on IRC last night, and it kept feeling like we almost had it until we didn't have it. I'm not sure if we weren't expert enough or if you just can't do this in rust using the signatures that the std::ops traits force you to use.

Playground link of what I had in mind so far and about where I got stuck:

1 Like
2

You haven't really told us what you want to do (what do you want the code that uses this to look like?), but if you just want to slice your PaletteBitmap you just need to implement Deref<&[u8]>for it such that you return pixels.as_slice() since from your code the invariant height * width == pixes.len() holds.

3

No that produces a 1d slice. Since this data is 2d, the slice form should also be 2d. So, instead of slicing a sub-range of a vec with v[2..5], you'd slice a bitmap with something like b[(2,2)..(4,5)], and instead of a vec that derefs to its own full range as a slice (so that most functionality can be written just on the slice type), you'd have a bitmap that derefs to its full set of pixels as a 2d slice.

4

Ah I see, then you need a user defined type:

struct Slice<'a> {
    bitmap: &'a PaletteBitmap,
    from: (usize, usize),
    to: (usize, usize),
}

and implement Index<(usize,usize)> for it in such a way that (0,0) accesses from from the bitmap. To iterate over it, note that Slice cannot Deref it into a &[u8] because the pixels of that slice are not in a contiguous memory region. That is, you need to add another type, e.g. SliceIterator that implements Iterator and use it to iterate over the Slice:

struct SliceIter<'a> {
  slice: Slice<'a>,
  current: (usize, usize),
}

impl<'a> Iterator for SliceIter<'a> { ... }
5

I wrote the imgref crate for this.

3 Likes
6

That's really nice! You should promote it more :wink:
I've suggested it for "Crate of the week"

2 Likes
7

ndarray is also a very good crate, with arbitrary slicing and striding of multi-dimensional arrays.

2 Likes
8

@gnzlbg Right, I never thought that you'd deref a sub-square into a straight slice of bytes :stuck_out_tongue: but my point is, if you want Bitmap to Deref into a BitmapSlice... how do you do you do that? Like, precisely what does the impl signature look like there? Because, for example, I'm not clear on how to get your example struct with its <'a> to work right with Deref, much less with something funky like Index<Range>. I tried to add the following to the bottom of my playground link code:

struct Slice<'a> {
    bitmap: &'a PaletteBitmap,
    from: (usize, usize),
    to: (usize, usize),
}

impl<'a> Deref for PaletteBitmap {
    type Target = Slice<'a>;
    
    fn deref(&self) -> &'a Self::Target {
        & Slice {
            bitmap: &self,
            from: (0,0),
            to: (self.width, self.height),
        }
    }
}

but I just get E0207, "the lifetime parameter 'a is not constrained by the impl trait, self type, or predicates".

Sadly, I'm not yet wise enough in the ways of rust to know where I need to add extra 'a values to get it to work.

@kornel Your crate seems to have Img as the base type for most operations, but that type doesn't implement Deref or indexing by range to get a subrange, so I'm not clear how you'd get a sub-grid of the full pixel grid with your type. There's a thing called ImgRef but that's a type alias, not a struct of its own. I might not be looking in the right part of your crate, so just point me to the right spot if I need to look elsewhere.

@AndrewGaspar it seems like ndarray is quite advanced in features, but it also seems like they are totally ignoring the std::ops traits in favor of making up their own API. They don't have any impl for Deref or Range at all. This strongly implies to me that my earlier conclusion was correct: 2d-slicing like this is simply beyond the ability of what the rusts ops are capable of handling (because they put the "refness" of the output in the wrong place).

9 
fn nope() -> &S {
    &S {}
}

Such code can't work in any case. It's not a matter of annotations, it's just impossible to make it work, because the struct is allocated on the stack.

It's the same as the classic dangling pointer error in C:

struct S* nope() {
    struct S obj = {};
    return &obj;
}

In Rust & is not a pointer, but a reference to already existing data which the caller never needs to free. This means you can't return any newly-created object in deref/as_ref and similar.

There is no way to nicely implement 2d references. Rust simply doesn't support such thing. That's why the imgref crate uses ImgRef which pretends to be a reference instead of using &Img.

10

In imgref you use .sub_image() to get a reference to a "slice" within a larger image.

11

Yeah, I sure thought that was the case, but I didn't know if gnzlbg had some expert knowledge I was missing :frowning:

It seems like Vec and String get by because the &[T] and &str you get back from their Deref impls just kinda cheese it with fat pointer magic that's only available for linear fat pointers.

12

You don't use Deref, you just add a method to the impl PaletteBitmap called as_slice that returns Slice<'a>, for example:

impl PaletteBitmap {
   fn as_slice<'a>(&'a self) -> Slice<'a> { ... }
}

like this: Rust Playground

1 Like
13

Ah, yeah, doing it without trying to use the std::ops stuff is very easy, you just lose a ton of syntax support.

Maybe in rust 2.0!

14

Which syntax do you lose? AFAICT only the ability to use &, you can still do foo.as_slice()[(2,2)..(4,4)].

15

So, by syntax support, what I mean is that, for example, the Vec type doesn't actually have a lot of the methods it appears to. Vec doesn't have sort, what it has is "Methods from Deref<Target=[T]>", which includes sort. So when you call my_vec.sort() what you get is Deref Magic that figures out to think about the Vec as a slice and then use the sort method of the slice type. And it all works out because slice is a semi-magical type within the language.

Also, you can do foo.as_slice() to slice out the whole thing, and then i guess the [(2,2)..(4,4)] part means you want to sub-slice out some smaller portion.... but I sure don't think you can write that method. Going back to your playground link, the bitmap slice type was defined as

pub struct Slice<'a> {
    bitmap: &'a PaletteBitmap,
    from: (usize, usize),
    to: (usize, usize),
}

So your "subslice with a range" Index trait impl would look like this, right?

impl<'a> Index<Range<(usize, usize)>> for Slice<'a> {
  type Output = Slice<'a>;
  
  fn index(&self, r: Range<(usize, usize)>) -> &Self::Output {
    // just ignore bounds checks for a moment, not important
    & Slice {
        bitmap: self.bitmap,
        from: (self.from.0 + r.start.0, self.from.1 + r.start.1),
        to: (self.from.0 + r.end.0, self.from.1 + r.end.1),
    } 
  }
}

But of course that's a classic borrowed value does not live long enough error. As far as I can tell you also can't jigger the lifetimes to make the output slice key off of the lifetime of the original source bitmap or anything like that. I'm not an expert, but a few folks on IRC and Discord were all defeated by this problem, maybe you can see something none of us do. Otherwise, not only can you not use . to activate Deref coercions, but you also can't use Index or IndexMut with a Range to pull out a sub-slice or mutable sub-slice.

16

If you've heard the phrase "Custom DST" around here, that's the not-really-designed-yet feature for letting types define their own fat pointer magic :slight_smile:

17

I ended up doing a thing that's very "first draft", but I think you can see where things are going easily enough

https://github.com/Lokathor/retro-pixel-rs/blob/master/src/indexmap.rs