#data-structure #generativity #no_std #lower-bound

no-std indexing

Sound unchecked indexing using “generativity”; a type system approach to indices, pointers and ranges that are trusted to be in bounds

14 releases

✓ Uses Rust 2018 edition

0.4.1 Sep 11, 2019
0.3.2 Jan 17, 2018
0.3.1 Nov 19, 2017
0.3.0 Dec 22, 2016
0.1.0 Feb 16, 2016

#47 in Rust patterns

Download history 70/week @ 2019-05-29 27/week @ 2019-06-05 22/week @ 2019-06-12 72/week @ 2019-06-19 229/week @ 2019-06-26 99/week @ 2019-07-03 41/week @ 2019-07-10 52/week @ 2019-07-17 79/week @ 2019-07-24 9/week @ 2019-07-31 22/week @ 2019-08-07 21/week @ 2019-08-14 143/week @ 2019-08-21 68/week @ 2019-08-28 97/week @ 2019-09-04

313 downloads per month
Used in 2 crates (1 directly)

MIT/Apache

120KB
3K SLoC

indexing

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

Extremely experimental, but somewhat promising & exciting.

Main focus is on index ranges, not just single indices.

build_status crates

Crate Features:

  • use_std Enabled by default, disable to be no_std-compatible.

References

Also now described in: You can't spell trust without Rust. Chapter 6.3 hacking generativity onto rust. Gankro's master's thesis.

Recent Changes

  • 0.4.1
    • Remove the ability to clone non- FixedLength Containers, because allowing to clone a container was wrong in the presencen of the length changing .push()/.insert() methods on vectors in containers.
  • 0.4.0
    • Add method .make_twin() that allows two or more containers to use the same trusted indices, if they are the same size
    • Add new marker trait FixedLength for use in make_twin.
    • Remove the branded raw pointer features, since they need revision (See #11)
    • Fix bug in the proof of .join_cover()
    • Fix signatures in ContiguousMut so that it now uses &mut correctly
    • Update dev-dependencies
    • Add Ord, PartialOrd impls for Range
    • Now using Rust 2018 and requiring Rust 1.32 or later.
  • 0.3.2
    • Fix future compatibility warning about pointer casts.
    • Add Ord, Hash impls for Index and Hash for Range
  • 0.3.1
    • Fixes in tests
    • Add crates.io categories
  • 0.3.0
    • Tweak implementation traits a bit, PointerRange, Provable, ContainerRef, make them unsafe where needed.
    • Add Container::range_of
  • 0.2.0
    • Docs are better
    • Refactor most of the crate, prepare for other backends than slices
    • Expose PIndex, PRange, PSlice which are the pointer-based equivalents of safe trusted indices and ranges. Some algos are better when using a raw pointer representation (for example: lower bound). Since we don't have HKT, traitifying all of this is not so pleasant and is not yet complete.
    • New feature: can combine trusted indices with push/insert on Vec.
  • 0.1.2
    • Add binary_search_by and lower_bound to algorithms. Algorithms don't require T: Debug anymore.
  • 0.1.1
    • Point documentation to docs.rs
  • 0.1.0
    • Add some docs and tests
    • Fix Range::join_cover_both to use ProofAdd
  • 0.1.0-alpha3
    • Add IndexingError and use it for all Results.
  • 0.1.0-alpha2
    • Add ProofAdd and use it in Range::join, Range::join_cover
    • Make Index<'id>, Range<'id> Send + Sync
  • 0.1.0-alpha1
    • First release

License

Dual-licensed to be compatible with the Rust project.

Licensed under the Apache License, Version 2.0 http://www.apache.org/licenses/LICENSE-2.0 or the MIT license http://opensource.org/licenses/MIT, at your option. This file may not be copied, modified, or distributed except according to those terms.

Dependencies

~0–630KB
~15K SLoC