BurntSushi / memchr

Optimized string search routines for Rust.
The Unlicense
873 stars 99 forks source link

Use rustc_layout_scalar_valid_range_end(usize::MAX - 1) for the index #72

Closed jyn514 closed 3 years ago

jyn514 commented 4 years ago

From https://github.com/rust-lang/rust/pull/73139#discussion_r439832328:

The index is always less than the length. So even if the length is usize::MAX, the index will be at most MAX - 1 and so cannot overflow.

It would be great to tell rustc this is the case by using rustc_layout_scalar_valid_range_end(usize::MAX - 1). That would allow storing Option<index> in usize instead of needing an extra bit, which in some cases could double the size of the struct due to alignment requirements.

Failing that (since rustc_layout_scalar_valid_range_end is unstable and likely will never be stabilized), would it be possible to document that the index is always less than usize::MAX?

BurntSushi commented 4 years ago

I guess I'm not opposed to documenting this, although it kind of seems self evident to me? memchr returns the position of a particular byte in a slice, if it exists. It it doesn't exist, then None is returned. Since the largest possible size of a slice is usize::MAX and since memchr can never possibly return an index greater than or equal to the length of the given slice (since it would be an invalid index), it follows immediately that the value returned is guaranteed to be less than usize::MAX.