Crate index_ext

Adds more index types, improving correctness and clarifying intent.

The crate is separated by modules which each roughly explore one particular index-related idea. As an overview, the main modules are:

• In the array module, a solution for repetitive try-into-unwrapping in the process of interpreting slices as fixed-width arrays is presented.
• In the int module, we explore numerical types with fallible conversion to indices on use, interpreting a failure as out-of-bounds.
• In the mem module, the efficient representation for the type intersection between integers and pointer sized indices is presented as a set of concrete types.
• In the tag module, we apply fancy type-level mechanisms to move the bounds check inherent in safe slice accesses from the usage site to the construction of the index. See in particular the Huffman example that demonstrates the optimization potential.

Read the readme for some examples. In short:

use index_ext::{Intex, SliceIntExt};

let fine = [0u8; 2][Intex(1u32)];
let also = [0u8; 2][Intex(1u128)];

assert_eq!([0u8; 2].get_int(u128::max_value()), None);

Unfinished features

The marker WIP means it is worked on, Planned that it might be worked on due to intrigue of the author, and Idea itself is still unevaluated (looking for a usecase, for instance).

Planned: An index type CharAt(n: usize) that dereferences to the characters of a string around a particular position, represented by a string wrapper that allows converting into a char. In contrast to the standard operator, this would only panic for out-of-bounds coordinates and thus match the main expectation with regards to len.

Idea: Note that a generic PrefixChars<N: usize>, retrieving the first N characters, would not be constant time which may be surprising if used in index position.

Idea: An index type InsertWith for HashMap and BTreeMap that will construct an element when an entry is missing, similar to C++, and thus be a panic free alternative. Maybe we could index a Vec<_> with this type as well, extending as necessary, but this would again not be constant time. The problem here is the super trait relationship IndexMut: Index which might lead to many potential misuses. Also the common alternative of entry.or_insert is both simple an robust already.

Idea: An adapter OrEmpty that uses get internally and substitutes an empty slice instead of panicking. Now this is maybe both clear and cute, I’d actually see some use here. It’s unclear for which types to provide it and if there’s a SemVer risk.

Design notes

The extension traits offered here have a slight ergonomic problem compared to being included in the standard library. Its ops::Index impls on slices are provided by the SliceIndex trait. Since this is a nightly trait and sealed by design we can not use it. However, we also can not use a generic impl for all T: crate::SliceIndex<[U]> as this is forbidden by coherence rules for foreign types. We thus utilize two kinds of indexing: Implement the Index trait directly for all concrete applicable types and provide a single newtype which acts as a proxy for the otherwise unconstrained type parameter of the generic impl. If the types were added to core then this indirection would not be necessary and ergonomics would improve.

Re-exports

• pub use array::ArrayPrefix;
• pub use int::SliceIntExt;

Modules

• array
  Index types that produce arrays.
• int
  Defines wrappers around standard integers to use the as indices.
• mem
  Integer wrappers that are constrained to the range of usize or isize.
• readme
  A rendered version of the Readme file, documentation purpose only.
• tag
  Statically elide bounds checks with the type system.

Functions

• Intex
  Convert an arbitrary integer into an index.