becheran / grid Goto Github PK

I want to use a (cloned) Grid as a key in a hashmap. This is currently not possible, because Hash isn't implemented for Grid<T>. I think this should be quite straightforward to add, a simple #[derive(Hash)] might already work.

A method like swap((row_a, col_a), (row_b, col_b)) would be very useful, since only the underlying vector has ownership of the values and can move them around.

Operations push_col, pop_col, insert_col are asymptotically less efficient, than they could be. Currently they each run in O(rows * rows * cols) but they could be implemented in O(rows * cols) time.

I cant initialize grid with defined size because struct i use not impl Default
I dont understand bound to Default trait because its possible to create vec and even Vec<Vec> with Vec::with_capacity() function

Sorry if this is due to my lack of understanding of Rust, I'm still learning the language.

assert_eq(vec![1], vec![1]); // works
assert_eq(vec![1.0], vec![1.0]); // works
assert_eq(grid![[1]], grid![[1]]); // works
assert_eq(grid![[1.0]], grid![[1.0]]); // doesn't work

The Grid type has the effective safety invariants that rows.checked_mul(cols) == Some(data.len()) and that rows == 0 if and only if cols == 0. In some panicking paths, Grid::insert_row() can violate these invariants:

• grid.insert_row(i, row) in release mode, where row.len() == grid.cols and grid.rows == usize::MAX. This sets grid.rows to 0, making the other methods' results inconsistent with one another. This is only possible when size_of::<T>() == 0, and I'm not sure if it can cause any UB by itself.
• grid.insert_row(i, row), where i <= grid.rows, row.len() == grid.cols, grid.rows < usize::MAX, and grid.rows * grid.cols > usize::MAX - grid.cols: This increments grid.rows without pushing the new row, allowing invalid get_unchecked() calls. Since this is only possible when size_of::<T>() == 0, it causes library UB but not language UB with the current standard library.
• grid.insert_row(i, row), where i <= grid.rows, row.len() == grid.cols, size_of::<T>() > 0, and (grid.rows + 1) * grid.cols * size_of::<T>() > isize::MAX as usize. This increments grid.rows without pushing the new row, which can cause UB on 32-bit targets:

  /*
  [dependencies]
  grid = "=0.8.1"
  
  cargo run --target i686-unknown-linux-gnu
  */
  
  use grid::Grid;
  use std::panic::{self, AssertUnwindSafe};
  
  fn main() {
      let catch = |f| panic::catch_unwind(AssertUnwindSafe(f)).unwrap_err();
      // 1076 * 1994889 == isize::MAX as usize - 983083
      // 1077 * 1994889 == isize::MAX as usize + 1011806
      let mut grid = Grid::init(1076, 1994889, 0u8);
      catch(|| grid.insert_row(1076, vec![0; 1994889]));
      println!("{}", grid.get(1076, 1994888).unwrap()); // segfault
  }

I think it would be nice to support Hash if the elements support Hash. I was trying to use cached, and couldn't cache on Grid<T> even if T was Hashable. I can try to make a PR.

Hello !

Would it be possible to implement Clone on theses iterators ? The underlying SkipBy iterator implement it, I'm new to rust but from what I've seen it should be possible ?

The use case is having an iterator at a certain point and cloning it to get two iterator starting at the same place:

let rows = grid.iter_rows().skip(1);
let r1 = rows.clone().take(10);
let r2 = rows.skip(10);

Here we need the clone because take consume the iterator AFAIK.

Thanks !

This program produces a segmentation fault:

/*
[dependencies]
grid = "=0.8.0"

cargo run --release
*/

use grid::Grid;

fn main() {
    let grid: Grid<i32> = Grid::new(2, usize::MAX / 2 + 1);
    println!("{}", grid.get(0, 0).unwrap());
}

The documentation on Grid::new() states that it will panic if rows * cols > usize::MAX. However, it currently only panics in debug mode; in release mode, rows * cols will silently overflow without panicking. In this example, rows * cols == 0 due to overflow, so Grid::new() creates a Vec of 0 elements, and we attempt to read from element 0. Since this is an invalid pointer (an empty Vec doesn't point to a real allocation), this results in a segmentation fault.

This issue can be fixed by replacing rows * cols with rows.checked_mul(cols).expect("...") in Grid::new() and Grid::init().

This doesn't work

use grid::Grid;
fn main() {
    let grid : Grid<u8> = Grid::new(usize::MAX, usize::MAX);
}

while this does

use grid::Grid;
  2 fn main() {
  3     let grid : Grid<u8> = Grid::new(u8::MAX, u8::MAX);
  4 }

Not really sure how the type annotations would look like, but you should probably update the documentation to say that grid lengths can only be sqrt(usize::MAX)

Mentioned as the title, I'm glad if we can have a indexed_iter(), and extension to iter() that adds row/col index to each item. That's a great convenience to avoid writing enumerated index by myself.

See discussion in #32

It should be possible to use the rust RawVec struct instead of Vec. This will save the not needed Len usize member variable

Hi,
still learning Rust, so maybe not really a Grid question but how can I read an entire Row and not cell by cell ?
so not grid[x][y], but a way to have grid.get_row(x)
thanks

[Edit:] did what I needed differently by using pop_row().

A great feature of Vec is that you can create a zero-length Vec with Vec::new(), and this does not allocate. This is great if you if you want to initialise a struct containing a Vec, but you don't yet know what the dimensions of the Vec should be. You can initialise the struct with the placeholder for very low cost.

It would be great if grid supported the same. I think it could make sense to only support both dimensions being zero, or both being non-zero. One being zero while the other is non-zero doesn't make much sense.

I would like to be able to get an entire row as a slice. Since the internal vector saves the rows continuously (at least for one of the allocation options, right?), it would be useful to be able to get such a slice, instead of an iterator with .iter_rows. In my use-case, this iterator wouldn't work, because I need to .rev() the rows, and that only works with a slice as far as I'm aware.

I'd like to be able to do the following:

grid.iter_rows(|row| row.iter_row().sum()).collect::<Vec<_>>()

same for cols. This could be a great feature when trying to apply functions row or column wise.

I'm new to Rust, but if you have the patience I'd be interested in creating a pr myself.

:)