#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

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

#1378 in Rust patterns

Download history 126/week @ 2023-10-20 126/week @ 2023-10-27 138/week @ 2023-11-03 109/week @ 2023-11-10 135/week @ 2023-11-17 164/week @ 2023-11-24 139/week @ 2023-12-01 100/week @ 2023-12-08 153/week @ 2023-12-15 173/week @ 2023-12-22 63/week @ 2023-12-29 118/week @ 2024-01-05 121/week @ 2024-01-12 130/week @ 2024-01-19 102/week @ 2024-01-26 96/week @ 2024-02-02

460 downloads per month
Used in 2 crates (via gll)

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–10MB
~69K SLoC