indexing

"Sound unchecked indexing" in Rust using "generativity" (branding by unique lifetime parameter).

This is a partial fork of https://github.com/bluss/indexing, with most of the code directly inspired from such.

This fork is immutable only, doesn't offer pointer indices/ranges, and doesn't allow manipulating the indices/ranges without a reference to the container. In exchange for these limitations, it works for fully sound fully unchecked indexing of Rust's UTF-8 string types.

lib.rs:

Sound unchecked indexing using the techniques from generative lifetimes, extended to string slices and without pointer or mutability support.

Major kudos go to Gankro and especially Bluss for the original indexing crate, from which this crate blatantly steals all of its cleverness.

Basic Structure

• A scope is created using the scope function; inside this scope, there is a Container object that has two roles: (1) it gives out or vets trusted indices, pointers and ranges (2) it provides access to the underlying data through these indices and ranges.

• The container and its indices and ranges are “branded” with a lifetime parameter 'id which is an identity marker. Branded items can't leave their scope, and they tie the items uniquely to a particular container. This makes it possible to trust them.

• Index<'id> is a trusted index

• Range<'id, Emptiness> is a trusted range.

• For a range, if the proof parameter Emptiness is NonEmpty, then the range is known to have at least one element. An observation: A non-empty range always has a valid front index, so it is interchangeable with the index representation.

• Indices also use the same proof parameter. A NonEmpty index points to a valid element, while an Unknown index is an edge index (it can be used to slice the container, but not to dereference to an element).

• All ranges have a .first() method to get the first index in the range, but it's only when the range is nonempty that the returned index is also NonEmpty and thus dereferenceable.

Borrowing

• Indices and ranges are freely copyable and do not track the backing data themselves. All access to the underlying data goes through the Container (e.g. by indexing the container with a trusted index).