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
//! Standard generic traits. //! //! # Why //! //! Did you ever need a generic `Sequence` trait? Ever wanted a data structure //! that was generic over either `Rc` or `Arc`? An iterator that returns //! borrowed data? //! //! These are not usually thought to be possible in stable Rust due to lack of //! native support for higher-kinded types (HKTs). HKTs is a feature that would //! allow us to reason about, say, `Vec` without fully defining it with type //! arguments (`Vec<T>`). The classic example that is usually thought //! impossible is the streaming (or borrowing) iterator, where `next()` returns //! an item wih a lifetime bound by the iterator itself: //! //! ```compile_fail //! trait StreamingIterator { //! type Item = &str; //! fn next<'a>(&'a mut self) -> Option<&'a str> { //! unimplemented!() //! } //! } //! ``` //! //! This does not compile because the reference `&str` must be declared with a //! lifetime, but we only have the lifetime for `self` in `next()` itself and //! not in the associated type declaration. Unlike `type` aliases, associated //! types (`type` in a trait) cannot have type arguments. That is, the //! following is not valid: //! //! ```compile_fail //! trait StreamingIterator { //! type Item<'a> = &'a str; //! fn next<'a>(&'a mut self) -> Option<&'a str> { //! unimplemented!() //! } //! } //! ``` //! //! This is called an associated type constructor. For more information, see //! the //! [RFC](https://github.com/rust-lang/rfcs/blob/master/text/1598-generic_associated_types.md) //! and //! [Nicholas'](https://smallcultfollowing.com/babysteps/blog/2016/11/02/associated-type-constructors-part-1-basic-concepts-and-introduction/) //! ATC post series. //! //! However, it is possible to emulate this behaviour in stable Rust with more //! boilerplate. See the [`StreamingIterator`](trait.StreamingIterator.html) //! trait. //! //! # How //! //! This library implements multiple generic traits for `std` types using a //! variation of //! [Edmund Smith's](https://gist.github.com/edmundsmith/855fcf0cb35dd467c29a9350481f0ecf) //! method to emulate higher-kinded types. See the [plug](plug/index.html) //! module for details. //! //! # Limitations //! //! HKT for types seems to be complete using the plug method. That is, any //! functionality you could get with native HKT support for types, you can get //! with this method. Ergonomy is not great though, even if it works. //! //! There are limitations regarding HKT lifetimes due to the fact that is //! impossible to put bounds on HRTB lifetimes. That is, something like //! `for<'a: 'b>` is inexpressible. As a result some traits and impls may have //! more restrictive lifetime bounds than necessary. //! //! # Current Status //! //! This crate is highly experimental and many traits have limited //! functionality. pub mod plug; pub mod rc; pub mod reference; pub mod slice; pub mod sync; pub mod vec; #[cfg(test)] mod tests; use crate::plug::*; use std::ops::Deref; /// Trait for structs that can be constructed with a preallocated capacity. pub trait WithCapacity { fn with_capacity(capacity: usize) -> Self; } /// Trait for collections that store elements in a linear sequence, allowing /// for linear traversal and indexing with an `usize`. /// /// # Note /// /// The `H1Iterator` bounds are not specific enough due to language /// limitations. The correct declaration for the trait and `H1Iterator` is: /// /// ```compile_fail /// trait Sequence<'a, T> /// where /// T: 'a /// { /// type H1Iterator: for<'b> PlugLifetime<'b> /// where /// 'a: 'b, /// <H1Iterator as PlugLifetime<'b>>::T: StreamingIterator; /// ... /// } /// ``` /// /// Because we can't declare `'a: 'b`, implementors must only allow /// `T: 'static`. In other words, we can't declare that all items outlive the /// iterator for any specific lifetime (so that stuff like `next()` returning a /// `&T` is valid if `T` contains references), so we must use a shotgun and /// prohibit `T` from containing any non-`'static` references. /// /// Also, where clauses in associated types are not stable so we have to move /// `StreamingIterator` bound to the `iter()` declaration. pub trait Sequence<T> { /// HKT iterator with a lifetime slot. type H1Iterator: for<'a> PlugLifetime<'a>; fn len(&self) -> usize; fn is_empty(&self) -> bool { self.len() == 0 } fn contains<'a>(&'a self, x: &T) -> bool where T: PartialEq; fn get(&self, index: usize) -> Option<&T>; fn first(&self) -> Option<&T> { self.get(0) } fn last(&self) -> Option<&T> { self.get(self.len() - 1) } fn iter<'a>(&'a self) -> <Self::H1Iterator as PlugLifetime<'a>>::T where <Self::H1Iterator as PlugLifetime<'a>>::T: StreamingIterator; } /// Trait for mutable collections that store elements in a linear sequence, /// allowing for linear traversal and indexing with an `usize`. pub trait SequenceMut<T> { fn capacity(&self) -> usize; fn clear(&mut self); fn reserve(&mut self, additional: usize); fn reserve_exact(&mut self, additional: usize); fn shrink_to_fit(&mut self); fn push(&mut self, x: T); fn pop(&mut self) -> Option<T>; fn insert(&mut self, index: usize, x: T); fn remove(&mut self, index: usize) -> T; } /// Trait for iterators that can return elements borrowed from itself. pub trait StreamingIterator { /// HTK item with a lifetime slot. type H1Item: for<'a> PlugLifetime<'a>; fn next(&mut self) -> Option<<Self::H1Item as PlugLifetime>::T>; } impl<I> StreamingIterator for I where I: Iterator, { type H1Item = H0<I::Item>; fn next(&mut self) -> Option<<Self::H1Item as PlugLifetime>::T> { Iterator::next(self) } } /// Trait for reference-counted boxes. pub trait Rcb<T>: Clone + Deref<Target = T> { type Weak: WeakRcb<T>; fn new(x: T) -> Self; fn try_unwrap(this: Self) -> Result<T, Self>; fn downgrade(this: &Self) -> Self::Weak; } /// Trait for weak pointers to reference-counted boxes. pub trait WeakRcb<T> { type Strong: Rcb<T>; fn upgrade(&self) -> Option<Self::Strong>; }