columnar/
lib.rs

1//! Types supporting flat / "columnar" layout for complex types.
2//!
3//! The intent is to re-layout `Vec<T>` types into vectors of reduced
4//! complexity, repeatedly. One should be able to push and pop easily,
5//! but indexing will be more complicated because we likely won't have
6//! a real `T` lying around to return as a reference. Instead, we will
7//! use Generic Associated Types (GATs) to provide alternate references.
8
9#![no_std]
10#[macro_use]
11extern crate alloc;
12#[cfg(feature = "std")]
13extern crate std;
14use alloc::vec::Vec;
15
16// Re-export derive crate.
17extern crate columnar_derive;
18pub use columnar_derive::Columnar;
19
20pub mod adts;
21pub mod boxed;
22pub mod bytes;
23pub mod lookback;
24pub mod primitive;
25pub mod string;
26pub mod sums;
27pub mod vector;
28pub mod tuple;
29mod arc;
30mod rc;
31
32pub use bytemuck;
33
34pub use vector::Vecs;
35pub use string::Strings;
36pub use sums::{rank_select::RankSelect, result::Results, option::Options, discriminant::Discriminant};
37pub use lookback::{Repeats, Lookbacks};
38
39/// A type that can be represented in columnar form.
40///
41/// For a running example, a type like `(A, Vec<B>)`.
42pub trait Columnar : 'static {
43    /// Repopulates `self` from a reference.
44    ///
45    /// By default this just calls `into_owned()`, but it can be overridden.
46    fn copy_from<'a>(&mut self, other: Ref<'a, Self>) where Self: Sized {
47        *self = Self::into_owned(other);
48    }
49    /// Produce an instance of `Self` from `Self::Ref<'a>`.
50    fn into_owned<'a>(other: Ref<'a, Self>) -> Self;
51
52    /// The type that stores the columnar representation.
53    ///
54    /// The container must support pushing both `&Self` and `Self::Ref<'_>`.
55    /// In our running example this might be `(Vec<A>, Vecs<Vec<B>>)`.
56    type Container: ContainerBytes + for<'a> Push<&'a Self>;
57
58    /// Converts a sequence of the references to the type into columnar form.
59    fn as_columns<'a, I>(selves: I) -> Self::Container where I: IntoIterator<Item=&'a Self>, Self: 'a {
60        let mut columns: Self::Container = Default::default();
61        for item in selves {
62            columns.push(item);
63        }
64        columns
65    }
66    /// Converts a sequence of the type into columnar form.
67    ///
68    /// This consumes the owned `Self` types but uses them only by reference.
69    /// Consider `as_columns()` instead if it is equally ergonomic.
70    fn into_columns<I>(selves: I) -> Self::Container where I: IntoIterator<Item = Self>, Self: Sized {
71        let mut columns: Self::Container = Default::default();
72        for item in selves {
73            columns.push(&item);
74        }
75        columns
76    }
77    /// Reborrows the reference type to a shorter lifetime.
78    ///
79    /// Implementations must not change the contents of the reference, and should mark
80    /// the function as `#[inline(always)]`. It is no-op to overcome limitations
81    /// of the borrow checker. In many cases, it is enough to return `thing` as-is.
82    ///
83    /// For example, when comparing two references `Ref<'a>` and `Ref<'b>`, we can
84    /// reborrow both to a local lifetime to compare them. This allows us to keep the
85    /// lifetimes `'a` and `'b` separate, while otherwise Rust would unify them.
86    #[inline(always)] fn reborrow<'b, 'a: 'b>(thing: Ref<'a, Self>) -> Ref<'b, Self> {
87        Self::Container::reborrow_ref(thing)
88    }
89}
90
91/// The container type of columnar type `T`.
92///
93/// Equivalent to `<T as Columnar>::Container`.
94pub type ContainerOf<T> = <T as Columnar>::Container;
95
96/// The borrowed container type of columnar type `T`.
97///
98/// Equivalent to `<<T as Columnar>::Container> as Borrow>::Borrowed<'a>`.
99pub type BorrowedOf<'a, T> = <ContainerOf<T> as Borrow>::Borrowed<'a>;
100
101/// For a lifetime, the reference type of columnar type `T`.
102///
103/// Equivalent to `<ContainerOf<T> as Borrow>::Ref<'a>`.
104pub type Ref<'a, T> = <ContainerOf<T> as Borrow>::Ref<'a>;
105
106/// A type that can be borrowed into a preferred reference type.
107pub trait Borrow: Len + Clone + 'static {
108    /// For each lifetime, a reference with that lifetime.
109    ///
110    /// As an example, `(&'a A, &'a [B])`.
111    type Ref<'a> : Copy;
112    /// The type of a borrowed container.
113    ///
114    /// Corresponding to our example, `(&'a [A], Vecs<&'a [B], &'a [u64]>)`.
115    type Borrowed<'a>: Copy + Len + Index<Ref = Self::Ref<'a>> where Self: 'a;
116    /// Converts a reference to the type to a borrowed variant.
117    ///
118    /// Implementations should most likely be marked `#[inline(always)]`.
119    fn borrow<'a>(&'a self) -> Self::Borrowed<'a>;
120    /// Reborrows the borrowed type to a shorter lifetime. See [`Columnar::reborrow`] for details.
121    fn reborrow<'b, 'a: 'b>(item: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a;
122    /// Reborrows the borrowed type to a shorter lifetime. See [`Columnar::reborrow`] for details.
123    fn reborrow_ref<'b, 'a: 'b>(item: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a;
124}
125
126
127/// A container that can hold `C`, and provide its preferred references through [`Borrow`].
128///
129/// As an example, `(Vec<A>, Vecs<Vec<B>>)`.
130pub trait Container : Borrow + Clear + for<'a> Push<Self::Ref<'a>> + Default + Send {
131    /// Allocates an empty container that can be extended by `selves` without reallocation.
132    ///
133    /// This goal is optimistic, and some containers may struggle to size correctly, especially
134    /// if they employ compression or other variable-sizing techniques that respond to the data
135    /// and the order in which is it presented. Best effort, but still useful!
136    fn with_capacity_for<'a, I>(selves: I) -> Self
137    where
138        Self: 'a,
139        I: Iterator<Item = Self::Borrowed<'a>> + Clone
140    {
141        let mut output = Self::default();
142        output.reserve_for(selves);
143        output
144    }
145
146    // Ensure that `self` can extend from `selves` without reallocation.
147    fn reserve_for<'a, I>(&mut self, selves: I)
148    where
149        Self: 'a,
150        I: Iterator<Item = Self::Borrowed<'a>> + Clone;
151
152
153    /// Extends `self` by a range in `other`.
154    ///
155    /// This method has a default implementation, but can and should be specialized when ranges can be copied.
156    /// As an example, lists of lists are often backed by contiguous elements, all of which can be memcopied,
157    /// with only the offsets into them (the bounds) to push either before or after (rather than during).
158    #[inline(always)]
159    fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
160        self.extend(range.map(|i| other.get(i)))
161    }
162}
163
164impl<T: Clone + 'static> Borrow for Vec<T> {
165    type Ref<'a> = &'a T;
166    type Borrowed<'a> = &'a [T];
167    #[inline(always)] fn borrow<'a>(&'a self) -> Self::Borrowed<'a> { &self[..] }
168    #[inline(always)] fn reborrow<'b, 'a: 'b>(item: Self::Borrowed<'a>) -> Self::Borrowed<'b> where Self: 'a { item }
169    #[inline(always)] fn reborrow_ref<'b, 'a: 'b>(item: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a { item }
170}
171
172impl<T: Clone + Send + 'static> Container for Vec<T> {
173    fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
174        self.extend_from_slice(&other[range])
175    }
176    fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
177        self.reserve(selves.map(|x| x.len()).sum::<usize>())
178    }
179}
180
181/// A container that can also be viewed as and reconstituted from bytes.
182pub trait ContainerBytes : Container + for<'a> Borrow<Borrowed<'a> : AsBytes<'a> + FromBytes<'a>> { }
183impl<C: Container + for<'a> Borrow<Borrowed<'a> : AsBytes<'a> + FromBytes<'a>>> ContainerBytes for C { }
184
185pub use common::{Clear, Len, Push, IndexMut, Index, IndexAs, Slice, AsBytes, FromBytes};
186/// Common traits and types that are re-used throughout the module.
187pub mod common {
188
189    use alloc::{vec::Vec, string::String};
190
191    /// A type with a length.
192    pub trait Len {
193        /// The number of contained elements.
194        fn len(&self) -> usize;
195        /// Whether this contains no elements.
196        fn is_empty(&self) -> bool {
197            self.len() == 0
198        }
199    }
200    impl<L: Len + ?Sized> Len for &L {
201        #[inline(always)] fn len(&self) -> usize { L::len(*self) }
202    }
203    impl<L: Len + ?Sized> Len for &mut L {
204        #[inline(always)] fn len(&self) -> usize { L::len(*self) }
205    }
206    impl<T> Len for Vec<T> {
207        #[inline(always)] fn len(&self) -> usize { self.len() }
208    }
209    impl<T> Len for [T] {
210        #[inline(always)] fn len(&self) -> usize { <[T]>::len(self) }
211    }
212    impl<T, const N: usize> Len for [T; N] {
213        #[inline(always)] fn len(&self) -> usize { N }
214    }
215
216    /// A type that can accept items of type `T`.
217    pub trait Push<T> {
218        /// Pushes an item onto `self`.
219        fn push(&mut self, item: T);
220        /// Pushes elements of an iterator onto `self`.
221        #[inline(always)] fn extend(&mut self, iter: impl IntoIterator<Item=T>) {
222            for item in iter {
223                self.push(item);
224            }
225        }
226    }
227    impl<T> Push<T> for Vec<T> {
228        #[inline(always)] fn push(&mut self, item: T) { self.push(item) }
229
230        #[inline(always)]
231        fn extend(&mut self, iter: impl IntoIterator<Item=T>) {
232            core::iter::Extend::extend(self, iter)
233        }
234    }
235    impl<'a, T: Clone> Push<&'a T> for Vec<T> {
236        #[inline(always)] fn push(&mut self, item: &'a T) { self.push(item.clone()) }
237
238        #[inline(always)]
239        fn extend(&mut self, iter: impl IntoIterator<Item=&'a T>) {
240            core::iter::Extend::extend(self, iter.into_iter().cloned())
241        }
242    }
243    impl<'a, T: Clone> Push<&'a [T]> for Vec<T> {
244        #[inline(always)] fn push(&mut self, item: &'a [T]) { self.clone_from_slice(item) }
245    }
246
247
248    pub use index::{Index, IndexMut, IndexAs};
249    /// Traits for accessing elements by `usize` indexes.
250    ///
251    /// There are several traits, with a core distinction being whether the returned reference depends on the lifetime of `&self`.
252    /// For one trait `Index` the result does not depend on this lifetime.
253    /// There is a third trait `IndexMut` that allows mutable access, that may be less commonly implemented.
254    pub mod index {
255
256        use alloc::vec::Vec;
257        use crate::Len;
258        use crate::common::IterOwn;
259
260        /// A type that can be mutably accessed by `usize`.
261        pub trait IndexMut {
262            /// Type mutably referencing an indexed element.
263            type IndexMut<'a> where Self: 'a;
264            fn get_mut(& mut self, index: usize) -> Self::IndexMut<'_>;
265            /// A reference to the last element, should one exist.
266            #[inline(always)] fn last_mut(&mut self) -> Option<Self::IndexMut<'_>> where Self: Len {
267                if self.is_empty() { None }
268                else { Some(self.get_mut(self.len()-1)) }
269            }
270        }
271
272        impl<T: IndexMut + ?Sized> IndexMut for &mut T {
273            type IndexMut<'a> = T::IndexMut<'a> where Self: 'a;
274            #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> {
275                T::get_mut(*self, index)
276            }
277        }
278        impl<T> IndexMut for Vec<T> {
279            type IndexMut<'a> = &'a mut T where Self: 'a;
280            #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self[index] }
281        }
282        impl<T> IndexMut for [T] {
283            type IndexMut<'a> = &'a mut T where Self: 'a;
284            #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> { &mut self[index] }
285        }
286
287        /// A type that can be accessed by `usize` but without borrowing `self`.
288        ///
289        /// This can be useful for types which include their own lifetimes, and
290        /// which wish to express that their reference has the same lifetime.
291        /// In the GAT `Index`, the `Ref<'_>` lifetime would be tied to `&self`.
292        ///
293        /// This trait may be challenging to implement for owning containers,
294        /// for example `Vec<_>`, which would need their `Ref` type to depend
295        /// on the lifetime of the `&self` borrow in the `get()` function.
296        ///
297        /// # Performance
298        ///
299        /// A call to `get(index)` will attempt to access member slices at `index`,
300        /// and as these could panic the optimizer cannot eliminate them even if you
301        /// do not then go on to examine the values. If you plan to access a field
302        /// (for tuples or structs) or variant match (for enums) you should perform
303        /// this before calling `get(index)` when able.
304        pub trait Index {
305            /// The type returned by the `get` method.
306            ///
307            /// This trait is most often implemented for lifetimed containers, and the `Ref` type
308            /// will have a lifetime that depends on that of the containers, rather than `&self`.
309            type Ref;
310            /// Returns the reference type for location `index`.
311            ///
312            /// Implementations should most likely be marked `#[inline(always)]`.
313            /// If possible, avoid the potential to panic in these implementations,
314            /// as this prevents Rust/LLVM from eliding the test even if the return
315            /// value is not actually consumed.
316            fn get(&self, index: usize) -> Self::Ref;
317            #[inline(always)] fn last(&self) -> Option<Self::Ref> where Self: Len {
318                if self.is_empty() { None }
319                else { Some(self.get(self.len()-1)) }
320            }
321            /// Converts `&self` into an iterator.
322            ///
323            /// This has an awkward name to avoid collision with `iter()`, which may also be implemented.
324            #[inline(always)]
325            fn index_iter(&self) -> IterOwn<&Self> {
326                IterOwn {
327                    index: 0,
328                    slice: self,
329                }
330            }
331            /// Converts `self` into an iterator.
332            ///
333            /// This has an awkward name to avoid collision with `into_iter()`, which may also be implemented.
334            #[inline(always)]
335            fn into_index_iter(self) -> IterOwn<Self> where Self: Sized {
336                IterOwn {
337                    index: 0,
338                    slice: self,
339                }
340            }
341        }
342
343        // These implementations aim to reveal a longer lifetime, or to copy results to avoid a lifetime.
344        impl<'a, T> Index for &'a [T] {
345            type Ref = &'a T;
346            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { &self[index] }
347        }
348        impl<T: Copy> Index for [T] {
349            type Ref = T;
350            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self[index] }
351        }
352        impl<T: Copy, const N: usize> Index for [T; N] {
353            type Ref = T;
354            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self[index] }
355        }
356        impl<'a, T> Index for &'a Vec<T> {
357            type Ref = &'a T;
358            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { &self[index] }
359        }
360        impl<T: Copy> Index for Vec<T> {
361            type Ref = T;
362            #[inline(always)] fn get(&self, index: usize) -> Self::Ref { self[index] }
363        }
364
365
366        /// Types that can be converted into another type by copying.
367        ///
368        /// We use this trait to unify the ability of `T` and `&T` to be converted into `T`.
369        /// This is handy for copy types that we'd like to use, like `u8`, `u64` and `usize`.
370        pub trait CopyAs<T> : Copy {
371            fn copy_as(self) -> T;
372        }
373        impl<T: Copy> CopyAs<T> for &T {
374            #[inline(always)] fn copy_as(self) -> T { *self }
375        }
376        impl<T: Copy> CopyAs<T> for T {
377            #[inline(always)] fn copy_as(self) -> T { self }
378        }
379
380        pub trait IndexAs<T> {
381            fn index_as(&self, index: usize) -> T;
382            #[inline(always)] fn last(&self) -> Option<T> where Self: Len {
383                if self.is_empty() { None }
384                else { Some(self.index_as(self.len()-1)) }
385            }
386        }
387
388        impl<T: Index, S> IndexAs<S> for T where T::Ref: CopyAs<S> {
389            #[inline(always)] fn index_as(&self, index: usize) -> S { self.get(index).copy_as() }
390        }
391
392    }
393
394    use crate::{Borrow, Container};
395    use crate::common::index::CopyAs;
396    /// A composite trait which captures the ability `Index<Ref = T>`.
397    ///
398    /// Implement `CopyAs<T>` for the reference type.
399    pub trait BorrowIndexAs<T> : for<'a> Borrow<Ref<'a>: CopyAs<T>> { }
400    impl<T, C: for<'a> Borrow<Ref<'a>: CopyAs<T>>> BorrowIndexAs<T> for C { }
401    /// A composite trait which captures the ability `Push<&T>` and `Index<Ref = T>`.
402    ///
403    /// Implement `CopyAs<T>` for the reference type, and `Push<&'a T>` for the container.
404    pub trait PushIndexAs<T> : BorrowIndexAs<T> + Container + for<'a> Push<&'a T> { }
405    impl<T, C: BorrowIndexAs<T> + Container + for<'a> Push<&'a T>> PushIndexAs<T> for C { }
406
407    /// A type that can remove its contents and return to an empty state.
408    ///
409    /// Generally, this method does not release resources, and is used to make the container available for re-insertion.
410    pub trait Clear {
411        /// Clears `self`, without changing its capacity.
412        fn clear(&mut self);
413    }
414    // Vectors can be cleared.
415    impl<T> Clear for Vec<T> {
416        #[inline(always)] fn clear(&mut self) { self.clear() }
417    }
418    // Slice references can be cleared.
419    impl<T> Clear for &[T] {
420        #[inline(always)] fn clear(&mut self) { *self = &[]; }
421    }
422
423    /// A struct representing a slice of a range of values.
424    ///
425    /// The lower and upper bounds should be meaningfully set on construction.
426    #[derive(Copy, Clone, Debug)]
427    pub struct Slice<S> {
428        pub lower: usize,
429        pub upper: usize,
430        pub slice: S,
431    }
432
433    impl<S> core::hash::Hash for Slice<S> where Self: Index<Ref: core::hash::Hash> {
434        fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
435            self.len().hash(state);
436            for i in 0 .. self.len() {
437                self.get(i).hash(state);
438            }
439        }
440    }
441
442    impl<S> Slice<S> {
443        pub fn slice<R: core::ops::RangeBounds<usize>>(self, range: R) -> Self {
444            use core::ops::Bound;
445            let lower = match range.start_bound() {
446                Bound::Included(s) => core::cmp::max(self.lower, *s),
447                Bound::Excluded(s) => core::cmp::max(self.lower, *s+1),
448                Bound::Unbounded => self.lower,
449            };
450            let upper = match range.end_bound() {
451                Bound::Included(s) => core::cmp::min(self.upper, *s+1),
452                Bound::Excluded(s) => core::cmp::min(self.upper, *s),
453                Bound::Unbounded => self.upper,
454            };
455            assert!(lower <= upper);
456            Self { lower, upper, slice: self.slice }
457        }
458        pub fn new(lower: u64, upper: u64, slice: S) -> Self {
459            let lower: usize = lower.try_into().expect("slice bounds must fit in `usize`");
460            let upper: usize = upper.try_into().expect("slice bounds must fit in `usize`");
461            Self { lower, upper, slice }
462        }
463        pub fn len(&self) -> usize { self.upper - self.lower }
464        /// Map the slice to another type.
465        pub(crate) fn map<T>(self, f: impl Fn(S) -> T) -> Slice<T> {
466            Slice {
467                lower: self.lower,
468                upper: self.upper,
469                slice: f(self.slice),
470            }
471        }
472    }
473
474    impl<S: Index> PartialEq for Slice<S> where S::Ref: PartialEq {
475        fn eq(&self, other: &Self) -> bool {
476            if self.len() != other.len() { return false; }
477            for i in 0 .. self.len() {
478                if self.get(i) != other.get(i) { return false; }
479            }
480            true
481        }
482    }
483    impl<S: Index> PartialEq<[S::Ref]> for Slice<S> where S::Ref: PartialEq {
484        fn eq(&self, other: &[S::Ref]) -> bool {
485            if self.len() != other.len() { return false; }
486            for i in 0 .. self.len() {
487                if self.get(i) != other[i] { return false; }
488            }
489            true
490        }
491    }
492    impl<S: Index> PartialEq<Vec<S::Ref>> for Slice<S> where S::Ref: PartialEq {
493        fn eq(&self, other: &Vec<S::Ref>) -> bool {
494            if self.len() != other.len() { return false; }
495            for i in 0 .. self.len() {
496                if self.get(i) != other[i] { return false; }
497            }
498            true
499        }
500    }
501
502    impl<S: Index> Eq for Slice<S> where S::Ref: Eq { }
503
504    impl<S: Index> PartialOrd for Slice<S> where S::Ref: PartialOrd {
505        fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
506            use core::cmp::Ordering;
507            let len = core::cmp::min(self.len(), other.len());
508
509            for i in 0 .. len {
510                match self.get(i).partial_cmp(&other.get(i)) {
511                    Some(Ordering::Equal) => (),
512                    not_equal => return not_equal,
513                }
514            }
515
516            self.len().partial_cmp(&other.len())
517        }
518    }
519
520    impl<S: Index> Ord for Slice<S> where S::Ref: Ord + Eq {
521        fn cmp(&self, other: &Self) -> core::cmp::Ordering {
522            use core::cmp::Ordering;
523            let len = core::cmp::min(self.len(), other.len());
524
525            for i in 0 .. len {
526                match self.get(i).cmp(&other.get(i)) {
527                    Ordering::Equal => (),
528                    not_equal => return not_equal,
529                }
530            }
531
532            self.len().cmp(&other.len())
533        }
534    }
535
536    impl<S> Len for Slice<S> {
537        #[inline(always)] fn len(&self) -> usize { self.len() }
538    }
539
540    impl<S: Index> Index for Slice<S> {
541        type Ref = S::Ref;
542        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
543            assert!(index < self.upper - self.lower);
544            self.slice.get(self.lower + index)
545        }
546    }
547    impl<'a, S> Index for &'a Slice<S>
548    where
549        &'a S : Index,
550    {
551        type Ref = <&'a S as Index>::Ref;
552        #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
553            assert!(index < self.upper - self.lower);
554            (&self.slice).get(self.lower + index)
555        }
556    }
557
558    impl<S: IndexMut> IndexMut for Slice<S> {
559        type IndexMut<'a> = S::IndexMut<'a> where S: 'a;
560        #[inline(always)] fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> {
561            assert!(index < self.upper - self.lower);
562            self.slice.get_mut(self.lower + index)
563        }
564    }
565
566    impl<S: Index + Len> Slice<S> {
567        /// Converts the slice into an iterator.
568        ///
569        /// This method exists rather than an `IntoIterator` implementation to avoid
570        /// a conflicting implementation for pushing an `I: IntoIterator` into `Vecs`.
571        pub fn into_iter(self) -> IterOwn<Slice<S>> {
572            self.into_index_iter()
573        }
574    }
575
576    impl<'a, T> Slice<&'a [T]> {
577        pub fn as_slice(&self) -> &'a [T] {
578            &self.slice[self.lower .. self.upper]
579        }
580    }
581
582    pub struct IterOwn<S> {
583        index: usize,
584        slice: S,
585    }
586
587    impl<S> IterOwn<S> {
588        pub fn new(index: usize, slice: S) -> Self {
589            Self { index, slice }
590        }
591    }
592
593    impl<S: Index + Len> Iterator for IterOwn<S> {
594        type Item = S::Ref;
595        #[inline(always)] fn next(&mut self) -> Option<Self::Item> {
596            if self.index < self.slice.len() {
597                let result = self.slice.get(self.index);
598                self.index += 1;
599                Some(result)
600            } else {
601                None
602            }
603        }
604        #[inline(always)]
605        fn size_hint(&self) -> (usize, Option<usize>) {
606            (self.slice.len() - self.index, Some(self.slice.len() - self.index))
607        }
608    }
609
610    impl<S: Index + Len> ExactSizeIterator for IterOwn<S> { }
611
612    /// A type that can be viewed as byte slices with lifetime `'a`.
613    ///
614    /// Implementors of this trait almost certainly reference the lifetime `'a` themselves.
615    pub trait AsBytes<'a> {
616        /// Presents `self` as a sequence of byte slices, with their required alignment.
617        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])>;
618    }
619
620    /// A type that can be reconstituted from byte slices with lifetime `'a`.
621    ///
622    /// Implementors of this trait almost certainly reference the lifetime `'a` themselves,
623    /// unless they actively deserialize the bytes (vs sit on the slices, as if zero-copy).
624    ///
625    /// # Overriding methods
626    ///
627    /// The only required method is [`from_bytes`](Self::from_bytes). However, the default
628    /// implementation of [`from_store`](Self::from_store) falls back through `from_bytes`,
629    /// which contains panicking operations that prevent LLVM from eliminating unused fields.
630    /// Implementors should override `from_store` and [`element_sizes`](Self::element_sizes)
631    /// to ensure optimal codegen. Missing overrides are functionally correct but silently
632    /// degrade performance. The `#[derive(Columnar)]` macro generates all overrides
633    /// automatically.
634    pub trait FromBytes<'a> {
635        /// The number of byte slices this type consumes when reconstructed.
636        const SLICE_COUNT: usize;
637        /// Reconstructs `self` from a sequence of correctly aligned and sized bytes slices.
638        ///
639        /// The implementation is expected to consume the right number of items from the iterator,
640        /// which may go on to be used by other implementations of `FromBytes`.
641        ///
642        /// The implementation should aim for only doing trivial work, as it backs calls like
643        /// `borrow` for serialized containers.
644        ///
645        /// Implementations should almost always be marked as `#[inline(always)]` to ensure that
646        /// they are inlined. A single non-inlined function on a tree of `from_bytes` calls
647        /// can cause the performance to drop significantly.
648        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self;
649        /// Reconstructs `self` from a [`DecodedStore`](crate::bytes::indexed::DecodedStore),
650        /// using direct random access at a given offset.
651        ///
652        /// Each field indexes directly into the store at its compile-time-known offset,
653        /// with no iterator state or sequential dependency. This enables LLVM to fully
654        /// eliminate unused fields.
655        #[inline(always)]
656        fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self where Self: Sized {
657            // Default: decode each slice from the store and delegate to from_bytes.
658            let start = *offset;
659            *offset += Self::SLICE_COUNT;
660            Self::from_bytes(&mut (start..*offset).map(|i| {
661                let (w, tail) = store.get(i);
662                let bytes: &[u8] = bytemuck::cast_slice(w);
663                let len = if tail == 0 { bytes.len() } else { bytes.len() - (8 - tail as usize) };
664                &bytes[..len]
665            }))
666        }
667        /// Reports the element sizes (in bytes) for each slice this type consumes.
668        ///
669        /// Implementors should override this to report their actual element sizes.
670        /// For example, `&[u32]` pushes `4`, while a tuple delegates to each field.
671        /// The default returns `Err`, so that [`validate`](Self::validate) rejects
672        /// data for types that have not implemented this method.
673        fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
674            let _ = sizes;
675            Err(format!("element_sizes not implemented for this type (SLICE_COUNT = {})", Self::SLICE_COUNT))
676        }
677        /// Validates that the given slices are compatible with this type.
678        ///
679        /// The input provides `(&[u64], u8)` pairs: each is a word slice
680        /// and trailing byte count. This type consumes `Self::SLICE_COUNT` entries and checks
681        /// that each slice's byte length is a multiple of its element size.
682        ///
683        /// Built from [`Self::element_sizes`]; generally should not need to be overridden.
684        fn validate(slices: &[(&[u64], u8)]) -> Result<(), String> where Self: Sized {
685            if slices.len() < Self::SLICE_COUNT {
686                return Err(format!("expected {} slices but got {}", Self::SLICE_COUNT, slices.len()));
687            }
688            let mut sizes = Vec::new();
689            Self::element_sizes(&mut sizes)?;
690            for (i, elem_size) in sizes.iter().enumerate() {
691                let (words, tail) = &slices[i];
692                let byte_len = words.len() * 8 - ((8 - *tail as usize) % 8);
693                if byte_len % elem_size != 0 {
694                    return Err(format!(
695                        "slice {} has {} bytes, not a multiple of element size {}",
696                        i, byte_len, elem_size
697                    ));
698                }
699            }
700            Ok(())
701        }
702    }
703
704}
705
706/// Roaring bitmap (and similar) containers.
707pub mod roaring {
708
709    use alloc::vec::Vec;
710    use crate::Results;
711
712    /// A container for `bool` that uses techniques from Roaring bitmaps.
713    ///
714    /// These techniques are to block the bits into blocks of 2^16 bits,
715    /// and to encode each block based on its density. Either a bitmap
716    /// for dense blocks or a list of set bits for sparse blocks.
717    ///
718    /// Additionally, other representations encode runs of set bits.
719    pub struct RoaringBits {
720        _inner: Results<[u64; 1024], Vec<u16>>,
721    }
722}
723
724pub use chain_mod::{chain, chain_one};
725
726pub mod chain_mod {
727    //! Chain iterators, or iterators and an item. Iterators that might improve inlining, at the
728    //! expense of not providing iterator maker traits.
729
730    /// Chain two iterators together. The result first iterates over `a`, then `b`, until both are
731    /// exhausted.
732    ///
733    /// This addresses a quirk where deep iterators would not be optimized to their full potential.
734    /// Here, functions are marked with `#[inline(always)]` to indicate that the compiler should
735    /// try hard to inline the iterators.
736    #[inline(always)]
737    pub fn chain<A: IntoIterator, B: IntoIterator<Item=A::Item>>(a: A, b: B) -> Chain<A::IntoIter, B::IntoIter> {
738        Chain { a: Some(a.into_iter()), b: Some(b.into_iter()) }
739    }
740
741    pub struct Chain<A, B> {
742        a: Option<A>,
743        b: Option<B>,
744    }
745
746    impl<A, B> Iterator for Chain<A, B>
747    where
748        A: Iterator,
749        B: Iterator<Item=A::Item>,
750    {
751        type Item = A::Item;
752
753        #[inline(always)]
754        fn next(&mut self) -> Option<Self::Item> {
755            if let Some(a) = self.a.as_mut() {
756                let x = a.next();
757                if x.is_none() {
758                    self.a = None;
759                } else {
760                    return x;
761                }
762            }
763            if let Some(b) = self.b.as_mut() {
764                let x = b.next();
765                if x.is_none() {
766                    self.b = None;
767                } else {
768                    return x;
769                }
770            }
771            None
772        }
773
774        #[inline]
775        fn fold<Acc, F>(self, mut acc: Acc, mut f: F) -> Acc
776        where
777            F: FnMut(Acc, Self::Item) -> Acc,
778        {
779            if let Some(a) = self.a {
780                acc = a.fold(acc, &mut f);
781            }
782            if let Some(b) = self.b {
783                acc = b.fold(acc, f);
784            }
785            acc
786        }
787    }
788
789    /// Chain a single item to an iterator. The resulting iterator first iterates over `a`,
790    /// then `b`. The resulting iterator is marked as `#[inline(always)]`, which in some situations
791    /// causes better inlining behavior with current Rust versions.
792    #[inline(always)]
793    pub fn chain_one<A: IntoIterator>(a: A, b: A::Item) -> ChainOne<A::IntoIter> {
794        ChainOne { a: Some(a.into_iter()), b: Some(b) }
795    }
796
797    pub struct ChainOne<A: Iterator> {
798        a: Option<A>,
799        b: Option<A::Item>,
800    }
801
802    impl<A: Iterator> Iterator for ChainOne<A> {
803        type Item = A::Item;
804
805        #[inline(always)]
806        fn next(&mut self) -> Option<Self::Item> {
807            if let Some(a) = self.a.as_mut() {
808                let x = a.next();
809                if x.is_none() {
810                    self.a = None;
811                    self.b.take()
812                } else {
813                    x
814                }
815            } else {
816                None
817            }
818        }
819    }
820
821    #[cfg(test)]
822    mod test {
823        use super::*;
824
825        #[test]
826        fn test_chain() {
827            let a = [1, 2, 3];
828            let b = [4, 5, 6];
829            let mut chain = chain(a, b);
830            assert_eq!(chain.next(), Some(1));
831            assert_eq!(chain.next(), Some(2));
832            assert_eq!(chain.next(), Some(3));
833            assert_eq!(chain.next(), Some(4));
834            assert_eq!(chain.next(), Some(5));
835            assert_eq!(chain.next(), Some(6));
836            assert_eq!(chain.next(), None);
837        }
838
839        #[test]
840        fn test_chain_one() {
841            let a = [1, 2, 3];
842            let b = 4;
843            let mut chain = chain_one(a, b);
844            assert_eq!(chain.next(), Some(1));
845            assert_eq!(chain.next(), Some(2));
846            assert_eq!(chain.next(), Some(3));
847            assert_eq!(chain.next(), Some(4));
848            assert_eq!(chain.next(), None);
849        }
850    }
851}
columnar/lib.rs

columnar/
lib.rs
