1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245
//! Sound unchecked indexing in Rust using “generativity”; a type system //! approach to indices, pointers and ranges that are trusted to be in bounds. //! //! We are developing our own “algebra” for transformations of in bounds ranges. //! //! Apart from trusted single indices and pointers, there are intervals like //! `Range<'id, P>` (indices) and `PRange<'id, T, P>` (pointers). //! //! These particles use marker types to for example enable certain methods only //! for ranges that are known to be nonempty. //! //! ***This is an experiment.*** The API is all of inconsistent, incomplete //! and redundant, but it explores interesting concepts. //! //! # Basic Parts //! //! - A scope is created using the [`scope`](container/fn.scope.html) function; //! inside this scope, there is a [`Container`][c] 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, P>` is a trusted range. //! - For a range, if the proof parameter `P` 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 and pointers 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 or pointer //! in the range, but it's only when the range is nonempty that the returned //! particle is also `NonEmpty` and thus dereferenceable. //! //! [c]: container/struct.Container.html //! //! # Raw Pointers //! //! Branded raw pointers work very similarly to indices. However, the code //! needs revision and it's not of good quality, so it's not enabled by default. //! //! - `PIndex<'id, T>` and `PRange<'id, T, P>` are equivalent to `Index` and //! `Range`, but they use trusted raw pointers instead. //! There are even two kinds of ranges: `PRange` uses a begin and end pointer //! representation, and `PSlice` a begin pointer and length representation. //! //! # Borrowing Rules //! //! - The indices, pointers and ranges are freely copyable and do not track //! mutability or exclusive access themselves. All access to the underlying data //! goes through the Container, for example by indexing the container with //! a trusted particle. //! //! //! //! # Example //! //! Find the lower bound index for element `elt` with a binary search using pointer ranges: //! //! ```rust //! use indexing::scope; //! //! fn lower_bound<T: PartialOrd>(v: &[T], elt: &T) -> usize { //! scope(v, move |v| { //! let mut range = v.range(); //! while let Ok(range_) = range.nonempty() { //! // The upper half of the split range still carries the proof //! // that it is non-empty, so we can access the element at `b.first()` //! let (a, b) = range_.split_in_half(); //! //! // THIS is the only access to the data in the underlying slice; //! // accessing the first element after the range's split point. //! // Access uses indexing syntax `v[index]` but note that the access //! // uses no runtime bounds checking and is guaranteed to be in bounds. //! if v[b.first()] < *elt { //! // A nonempty range has a tail (everything but the first element) //! range = b.tail(); //! } else { //! range = a; //! } //! } //! // return the start index of the range //! range.first().integer() //! }) //! } //! //! //! // Find the lower bound for "2", which is the point exactly between the ones and the twos. //! let data = [0, 1, 1, 2, 2, 2, 3, 4]; //! assert_eq!(lower_bound(&data, &2), 3); //! ``` //! #![doc(html_root_url="https://docs.rs/indexing/0.2/")] #![cfg_attr(not(feature = "use_std"), no_std)] #[cfg(not(feature = "use_std"))] extern crate core as std; use std::marker::PhantomData; use std::fmt::{self, Debug}; #[macro_use] mod macro_utils; pub mod indexing; pub mod proof; pub mod algorithms; pub mod container_traits; pub mod container; #[cfg(feature="experimental_pointer_ranges")] pub mod pointer; mod index_error; mod pointer_ext; pub use crate::index_error::IndexingError; pub use crate::container::{Container, scope}; pub use crate::proof::{NonEmpty, Unknown}; // Common types // /// `Id<'id>` is invariant w.r.t `'id` /// /// This means that the inference engine is not allowed to shrink or /// grow 'id to solve the borrow system. #[derive(Copy, Clone, PartialEq, PartialOrd, Eq)] struct Id<'id> { id: PhantomData<*mut &'id ()>, } unsafe impl<'id> Sync for Id<'id> { } unsafe impl<'id> Send for Id<'id> { } impl<'id> Default for Id<'id> { #[inline] fn default() -> Self { Id { id: PhantomData } } } impl<'id> Debug for Id<'id> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { f.write_str("Id<'id>") } } /// A branded index. /// /// `Index<'id>` only indexes the container instantiated with the exact same /// particular lifetime for the parameter `'id` at its inception from /// the `scope()` function. /// /// The type parameter `Proof` determines if the index is dereferenceable. /// /// A `NonEmpty` index points to a valid element. An `Unknown` index is unknown, /// or it points to an edge index (just past the end). pub struct Index<'id, Proof = NonEmpty> { id: Id<'id>, index: usize, /// NonEmpty or Unknown proof: PhantomData<Proof>, } copy_and_clone!(['id, P] Index<'id, P>); impl<'id, P> Index<'id, P> { #[inline(always)] unsafe fn new(index: usize) -> Index<'id, P> { debug_assert!(index as isize >= 0); Index { id: Id::default(), index: index, proof: PhantomData } } #[inline] // Assume any proof for index unsafe fn assume_any_index<Q>(other: Index<'id, Q>) -> Self { Self::new(other.index) } } /// A branded range. /// /// `Range<'id>` only indexes the container instantiated with the exact same /// particular lifetime for the parameter `'id` at its inception from /// the `scope()` function. /// /// The `Range` may carry a proof of nonemptiness (type parameter `Proof`), /// which enables further methods. /// /// The range is delimited by a start index and an end index. Some methods /// will use offsets relative the the start of a range, others will use /// “absolute indices” which are offsets relative to the base `Container` /// itself. pub struct Range<'id, Proof=Unknown> { id: Id<'id>, start: usize, end: usize, /// NonEmpty or Unknown proof: PhantomData<Proof>, } copy_and_clone!(['id, P] Range<'id, P>); impl<'id> Range<'id> { #[inline(always)] unsafe fn from(start: usize, end: usize) -> Range<'id> { debug_assert!(start <= end); Range { id: Id::default(), start: start, end: end, proof: PhantomData } } } impl<'id> Range<'id, NonEmpty> { #[inline(always)] unsafe fn from_ne(start: usize, end: usize) -> Range<'id, NonEmpty> { debug_assert!(start < end); Range { id: Id::default(), start: start, end: end, proof: PhantomData } } #[inline] unsafe fn assume_nonempty_range<Q>(other: Range<'id, Q>) -> Range<'id, NonEmpty> { Range::from_ne(other.start, other.end) } } impl<'id, P> Range<'id, P> { #[inline(always)] unsafe fn from_any(start: usize, end: usize) -> Range<'id, P> { debug_assert!(start <= end); Range { id: Id::default(), start: start, end: end, proof: PhantomData } } #[inline] unsafe fn assume_any_range<Q>(other: Range<'id, Q>) -> Self { Self::from_any(other.start, other.end) } } // Access the internals of Container in the whole crate (but not outside) trait ContainerPrivate { type Array; fn array(&self) -> &Self::Array; fn array_mut(&mut self) -> &mut Self::Array; }