{"action":"created","issue":{"url":"https://api.github.com/repos/rust-ndarray/ndarray/issues/543","repository_url":"https://api.github.com/repos/rust-ndarray/ndarray","labels_url":"https://api.github.com/repos/rust-ndarray/ndarray/issues/543/labels{/name}","comments_url":"https://api.github.com/repos/rust-ndarray/ndarray/issues/543/comments","events_url":"https://api.github.com/repos/rust-ndarray/ndarray/issues/543/events","html_url":"https://github.com/rust-ndarray/ndarray/pull/543","id":381825324,"node_id":"MDExOlB1bGxSZXF1ZXN0MjMxNzA0OTY4","number":543,"title":"Clarify invariants and fix constructors and is_standard_layout","user":{"login":"jturner314","id":1836850,"node_id":"MDQ6VXNlcjE4MzY4NTA=","avatar_url":"https://avatars1.githubusercontent.com/u/1836850?v=4","gravatar_id":"","url":"https://api.github.com/users/jturner314","html_url":"https://github.com/jturner314","followers_url":"https://api.github.com/users/jturner314/followers","following_url":"https://api.github.com/users/jturner314/following{/other_user}","gists_url":"https://api.github.com/users/jturner314/gists{/gist_id}","starred_url":"https://api.github.com/users/jturner314/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jturner314/subscriptions","organizations_url":"https://api.github.com/users/jturner314/orgs","repos_url":"https://api.github.com/users/jturner314/repos","events_url":"https://api.github.com/users/jturner314/events{/privacy}","received_events_url":"https://api.github.com/users/jturner314/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":4,"created_at":"2018-11-17T04:01:47Z","updated_at":"2018-11-17T21:13:29Z","closed_at":null,"author_association":"MEMBER","pull_request":{"url":"https://api.github.com/repos/rust-ndarray/ndarray/pulls/543","html_url":"https://github.com/rust-ndarray/ndarray/pull/543","diff_url":"https://github.com/rust-ndarray/ndarray/pull/543.diff","patch_url":"https://github.com/rust-ndarray/ndarray/pull/543.patch"},"body":"Various method and iterator implementations in `ndarray` implicitly made some assumptions that were not enforced. For example,\r\n\r\n* In a number of places, methods/iterators violated the safety constraints on [`.offset()`](https://doc.rust-lang.org/std/primitive.pointer.html#method.offset). For example, `AxisIterCore` offsets the pointer along the axis of iteration even if one of the other axes is zero-length. As a result, before this PR, this program would have undefined behavior:\r\n\r\n  ```rust\r\n  extern crate ndarray;\r\n\r\n  use ndarray::prelude::*;\r\n\r\n  fn main() {\r\n      let a = ArrayView2::<i32>::from_shape((0, 3), &[1]).unwrap();\r\n      for v in a.axis_iter(Axis(1)) {\r\n          println!(\"{:?}\", v);\r\n      }\r\n  }\r\n  ```\r\n\r\n  The stride of axis 1 is 1, so `AxisIter` calls `ptr.offset(0 * 1)`, `ptr.offset(1 * 1)`, and `ptr.offset(2 * 1)`. The first and second offsets are fine because they're \"in bounds or one byte past the end of the same allocated object\", but the last offset is undefined behavior.\r\n\r\n  This PR states the invariant that offsets along all axes must be safe, even if there are zero-length axes, and it checks this property in array constructors.\r\n\r\n* In some places, implementations made the assumption that the axis lengths would always be less than or equal to `isize::MAX`, such as in the [`stride_offset` function in the `dimension` module](https://github.com/rust-ndarray/ndarray/blob/245cfbb031eb8c59981ea8639c109b83d9ba8954/src/dimension/mod.rs#L33-L35). However, it is possible to create a `Vec`/slice with length greater than `isize::MAX` of zero-size elements, and the implementation of `size_checked` allowed creation of arrays with axis lengths greater than `isize::MAX` (e.g. `ArrayView2::<i32>::from_shape((isize::MAX as usize + 1, 0), &[]).unwrap()`. I have trouble finding a place where this would cause undefined behavior, but these cases could cause unexpected panics in debug mode due to overflow, and the fact that I've seen code making this invalid assumption makes me uncomfortable that there may be a soundness issue I haven't found.\r\n\r\n  This PR changes the constructors to enforce that the product of non-zero axis lengths must not exceed `isize::MAX`.\r\n\r\nThis PR explicitly states the invariants that `ArrayBase` must uphold and methods can depend on. It also adds the necessary checks to enforce these invariants when arrays are created. The invariants are carefully designed so that slices/subviews/reshapes/etc. preserve them, so checks are needed only in the constructors and not in method/iterator implementations.\r\n\r\nThis PR does make some changes to the behavior of constructors, the default strides for empty arrays, and `is_standard_layout` in some edge cases. However, I would still consider it a backwards-compatible change because it's enforcing assumptions that were made in previous versions that should have been checked. In other words, it's a bug fix.\r\n\r\nA few notes about possible alternatives:\r\n\r\n* We could drop the requirement that it must be safe to offset the pointer along all axes even in empty arrays. However, this would mean we'd need to add explicit checks for empty arrays in things like `AxisIter` and `.subview_inplace()`. These checks would be easy-to-forget, which is problematic because missing a check could result in undefined behavior. I much prefer performing the necessary checks in constructors so that all the other method/iterator implementations can be simple.\r\n* We could drop the requirement that the product of non-zero axis lengths must fit in `isize`. This would be slightly more flexible because, for example, it be possible possible to create a 1-D array of `usize::MAX` zero-size elements. However, this additional flexibility doesn't have practical applications and would require us to explicitly check for overflow in a lot more places.\r\n* We could drop the requirement that the pointer must be non-null even for empty arrays. There may even be some advantage to doing this because it would make `ArrayPtr`/`ArrayPtrMut` in #496 more flexible. However, method implementations already make this assumption (e.g. [`.as_slice()`](https://github.com/rust-ndarray/ndarray/blob/245cfbb031eb8c59981ea8639c109b83d9ba8954/src/impl_methods.rs#L1079)), allowing null pointers isn't significantly more useful than allowing dangling pointers, and forbidding null pointers will allow us to switch `ArrayBase.ptr` to use `NonNull` in the future (which should remove the need for \"reborrow\" methods (#412))."},"comment":{"url":"https://api.github.com/repos/rust-ndarray/ndarray/issues/comments/439648060","html_url":"https://github.com/rust-ndarray/ndarray/pull/543#issuecomment-439648060","issue_url":"https://api.github.com/repos/rust-ndarray/ndarray/issues/543","id":439648060,"node_id":"MDEyOklzc3VlQ29tbWVudDQzOTY0ODA2MA==","user":{"login":"jturner314","id":1836850,"node_id":"MDQ6VXNlcjE4MzY4NTA=","avatar_url":"https://avatars1.githubusercontent.com/u/1836850?v=4","gravatar_id":"","url":"https://api.github.com/users/jturner314","html_url":"https://github.com/jturner314","followers_url":"https://api.github.com/users/jturner314/followers","following_url":"https://api.github.com/users/jturner314/following{/other_user}","gists_url":"https://api.github.com/users/jturner314/gists{/gist_id}","starred_url":"https://api.github.com/users/jturner314/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jturner314/subscriptions","organizations_url":"https://api.github.com/users/jturner314/orgs","repos_url":"https://api.github.com/users/jturner314/repos","events_url":"https://api.github.com/users/jturner314/events{/privacy}","received_events_url":"https://api.github.com/users/jturner314/received_events","type":"User","site_admin":false},"created_at":"2018-11-17T21:13:29Z","updated_at":"2018-11-17T21:13:29Z","author_association":"MEMBER","body":"> the argument for allowing more general strides for zero length axes would be that they can come up in normal operation somehow?\r\n\r\nHere's an example demonstrating that arbitrary strides can occur for zero-length axes in normal operation:\r\n\r\n```rust\r\nextern crate ndarray;\r\n\r\nuse ndarray::{array, s, Axis};\r\n\r\nfn main() {\r\n    let mut a = array![[1, 2, 3], [4, 5, 6]];\r\n    a.invert_axis(Axis(0));\r\n    println!(\"a =\\n{:?}\", a);\r\n    let s = a.slice(s![0..0, ..]);\r\n    println!(\"s =\\n{:?}\", s);\r\n}\r\n```\r\n\r\nIt prints:\r\n\r\n```\r\na =\r\n[[4, 5, 6],\r\n [1, 2, 3]] shape=[2, 3], strides=[-3, 1], layout=Custom (0x0)\r\ns =\r\n[[]] shape=[0, 3], strides=[-3, 1], layout=Custom (0x0)\r\n```\r\n\r\nThe stride of axis 0 is `-3` in the view `s`.\r\n\r\nWe could still ban them in constructors, but I don't see a good reason to if they can occur in normal operation."}}
{"actor":{"display_login":"jturner314"}}