columnation/
lib.rs

Help
1//! An unsafe columnar arena for owned data.
2//!
3//! This library contains types and traits that allow one to collect
4//! types with owned data but is backed by relatively few allocations.
5//! The catch is that collected instances can only be used by reference,
6//! as they are not valid owned data (their pointers do not point to
7//! allocations that can be returned to the allocator).
8//!
9//! # Safety
10//!
11//! This crate is wildly unsafe, on account of it uses the `unsafe`
12//! keyword and Rust's safety is not yet clearly enough specified
13//! for me to make any stronger statements than that.
14
15/// A type that can absorb owned data from type `T`.
16///
17/// This type will ensure that absorbed data remain valid as long as the
18/// instance itself is valid. Responsible users will couple the lifetime
19/// of this instance with that of *all* instances it returns from `copy`.
20pub trait Region : Default {
21    /// The type of item the region contains.
22    type Item;
23    /// Add a new element to the region.
24    ///
25    /// The argument will be copied in to the region and returned as an
26    /// owned instance. It is unsafe to unwrap and then drop the result.
27    ///
28    /// # Safety
29    ///
30    /// It is unsafe to use the result in any way other than to reference
31    /// its contents, and then only for the lifetime of the columnar region.
32    /// Correct uses of this method are very likely exclusive to this crate.
33    unsafe fn copy(&mut self, item: &Self::Item) -> Self::Item;
34    /// Retain allocations but discard their contents.
35    ///
36    /// The elements in the region do not actually own resources, and
37    /// their normal `Drop` implementations will not be called. This method
38    /// should only be called after all instances returned by `copy` have
39    /// been disposed of, as this method may invalidate their contents.
40    fn clear(&mut self);
41
42    /// Ensure that the region can absorb `items` without reallocation.
43    fn reserve_items<'a, I>(&mut self, items: I)
44    where
45        Self: 'a,
46        I: Iterator<Item=&'a Self::Item>+Clone;
47
48    /// Allocate an instance of `Self` that can absorb `items` without reallocation.
49    fn with_capacity_items<'a, I>(items: I) -> Self
50    where
51        Self: 'a,
52        I: Iterator<Item=&'a Self::Item>+Clone
53    {
54        let mut region = Self::default();
55        region.reserve_items(items);
56        region
57    }
58
59    // Ensure that the region can absorb the items of `regions` without reallocation
60    fn reserve_regions<'a, I>(&mut self, regions: I)
61    where
62        Self: 'a,
63        I: Iterator<Item = &'a Self> + Clone;
64
65    /// Allocate an instance of `Self` that can absorb the items of `regions` without reallocation.
66    fn with_capacity_regions<'a, I>(regions: I) -> Self
67    where
68        Self: 'a,
69        I: Iterator<Item = &'a Self> + Clone
70    {
71        let mut region = Self::default();
72        region.reserve_regions(regions);
73        region
74    }
75
76    /// Determine this region's memory used and reserved capacity in bytes.
77    ///
78    /// An implementation should invoke the `callback` for each distinct allocation, providing the
79    /// used capacity as the first parameter and the actual capacity as the second parameter.
80    /// Both parameters represent a number of bytes. The implementation should only mention
81    /// allocations it owns, but not itself, because another object owns it.
82    ///
83    /// The closure is free to sum the parameters, or do more advanced analysis such as creating a
84    /// histogram of allocation sizes.
85    fn heap_size(&self, callback: impl FnMut(usize, usize));
86}
87
88/// A vacuous region that just copies items.
89pub struct CopyRegion<T> {
90    phantom: std::marker::PhantomData<T>,
91}
92
93impl<T> Default for CopyRegion<T> {
94    fn default() -> Self {
95        Self { phantom: std::marker::PhantomData }
96    }
97}
98
99// Any type that implements copy can use a non-region that just copies items.
100impl<T: Copy> Region for CopyRegion<T> {
101    type Item = T;
102    #[inline(always)]
103    unsafe fn copy(&mut self, item: &Self::Item) -> Self::Item {
104        *item
105    }
106    #[inline(always)]
107    fn clear(&mut self) { }
108
109    fn reserve_items<'a, I>(&mut self, _items: I)
110    where
111        Self: 'a,
112        I: Iterator<Item=&'a Self::Item> + Clone { }
113
114    fn reserve_regions<'a, I>(&mut self, _regions: I)
115    where
116        Self: 'a,
117        I: Iterator<Item = &'a Self> + Clone { }
118
119    #[inline]
120    fn heap_size(&self, _callback: impl FnMut(usize, usize)) {
121        // Does not contain any allocation
122    }
123}
124
125
126/// A region allocator which holds items at stable memory locations.
127///
128/// Items once inserted will not be moved, and their locations in memory
129/// can be relied on by others, until the region is cleared.
130///
131/// This type accepts owned data, rather than references, and does not
132/// itself intend to implement `Region`. Rather, it is a useful building
133/// block for other less-safe code that wants allocated data to remain at
134/// fixed memory locations.
135pub struct StableRegion<T> {
136    /// The active allocation into which we are writing.
137    local: Vec<T>,
138    /// All previously active allocations.
139    stash: Vec<Vec<T>>,
140    /// The maximum allocation size
141    limit: usize,
142}
143
144// Manually implement `Default` as `T` may not implement it.
145impl<T> Default for StableRegion<T> {
146    fn default() -> Self {
147        Self {
148            local: Vec::new(),
149            stash: Vec::new(),
150            limit: usize::MAX,
151        }
152    }
153}
154
155impl<T> StableRegion<T> {
156    /// Construct a [StableRegion] with a allocation size limit.
157    pub fn with_limit(limit: usize) -> Self {
158        Self {
159            local: Default::default(),
160            stash: Default::default(),
161            limit: limit,
162        }
163    }
164
165    /// Clears the contents without dropping any elements.
166    #[inline]
167    pub fn clear(&mut self) {
168        unsafe {
169            // Unsafety justified in that setting the length to zero exposes
170            // no invalid data.
171            self.local.set_len(0);
172            // Release allocations in `stash` without dropping their elements.
173            for mut buffer in self.stash.drain(..) {
174                buffer.set_len(0);
175            }
176        }
177    }
178    /// Copies an iterator of items into the region.
179    #[inline]
180    pub fn copy_iter<I>(&mut self, items: I) -> &mut [T]
181    where
182        I: Iterator<Item = T> + std::iter::ExactSizeIterator,
183    {
184        self.reserve(items.len());
185        let initial_len = self.local.len();
186        self.local.extend(items);
187        &mut self.local[initial_len ..]
188    }
189    /// Copies a slice of cloneable items into the region.
190    #[inline]
191    pub fn copy_slice(&mut self, items: &[T]) -> &mut [T]
192    where
193        T: Clone,
194    {
195        self.reserve(items.len());
196        let initial_len = self.local.len();
197        self.local.extend_from_slice(items);
198        &mut self.local[initial_len ..]
199    }
200
201    /// Ensures that there is space in `self.local` to copy at least `count` items.
202    #[inline(always)]
203    pub fn reserve(&mut self, count: usize) {
204        // Check if `item` fits into `self.local` without reallocation.
205        // If not, stash `self.local` and increase the allocation.
206        if count > self.local.capacity() - self.local.len() {
207            // Increase allocated capacity in powers of two.
208            // We could choose a different rule here if we wanted to be
209            // more conservative with memory (e.g. page size allocations).
210            let mut next_len = (self.local.capacity() + 1).next_power_of_two();
211            next_len = std::cmp::min(next_len, self.limit);
212            next_len = std::cmp::max(count, next_len);
213            let new_local = Vec::with_capacity(next_len);
214            if self.local.is_empty() {
215                self.local = new_local;
216            } else {
217                self.stash.push(std::mem::replace(&mut self.local, new_local));
218            }
219        }
220    }
221
222    /// Allocates a new `Self` that can accept `count` items without reallocation.
223    pub fn with_capacity(count: usize) -> Self {
224        let mut region = Self::default();
225        region.reserve(count);
226        region
227    }
228
229    /// The number of items current held in the region.
230    pub fn len(&self) -> usize {
231        self.local.len() + self.stash.iter().map(|r| r.len()).sum::<usize>()
232    }
233
234    #[inline]
235    pub fn heap_size(&self, mut callback: impl FnMut(usize, usize)) {
236        // Calculate heap size for local, stash, and stash entries
237        let size_of_t = std::mem::size_of::<T>();
238        callback(
239            self.local.len() * size_of_t,
240            self.local.capacity() * size_of_t,
241        );
242        callback(
243            self.stash.len() * std::mem::size_of::<Vec<T>>(),
244            self.stash.capacity() * std::mem::size_of::<Vec<T>>(),
245        );
246        for stash in &self.stash {
247            callback(stash.len() * size_of_t, stash.capacity() * size_of_t);
248        }
249    }
250}
251
252
253/// A type that can be stored in a columnar region.
254///
255/// This trait exists only to allow types to name the columnar region
256/// that should be used.
257pub trait Columnation: Sized {
258    /// The type of region capable of absorbing allocations owned by
259    /// the `Self` type. Note: not allocations of `Self`, but of the
260    /// things that it owns.
261    type InnerRegion: Region<Item = Self>;
262}
263
264pub use columnstack::ColumnStack;
265
266mod columnstack {
267
268    use super::{Columnation, Region};
269
270    /// An append-only vector that store records as columns.
271    ///
272    /// This container maintains elements that might conventionally own
273    /// memory allocations, but instead the pointers to those allocations
274    /// reference larger regions of memory shared with multiple instances
275    /// of the type. Elements can be retrieved as references, and care is
276    /// taken when this type is dropped to ensure that the correct memory
277    /// is returned (rather than the incorrect memory, from running the
278    /// elements' `Drop` implementations).
279    pub struct ColumnStack<T: Columnation> {
280        pub(crate) local: Vec<T>,
281        pub(crate) inner: T::InnerRegion,
282    }
283
284    impl<T: Columnation> ColumnStack<T> {
285        /// Construct a [ColumnStack], reserving space for `capacity` elements
286        ///
287        /// Note that the associated region is not initialized to a specific capacity
288        /// because we can't generally know how much space would be required. For this reason,
289        /// this function is private.
290        fn with_capacity(capacity: usize) -> Self {
291            Self {
292                local: Vec::with_capacity(capacity),
293                inner: T::InnerRegion::default(),
294            }
295        }
296
297        /// Ensures `Self` can absorb `items` without further allocations.
298        ///
299        /// The argument `items` may be cloned and iterated multiple times.
300        /// Please be careful if it contains side effects.
301        #[inline(always)]
302        pub fn reserve_items<'a, I>(&'a mut self, items: I)
303        where
304            I: Iterator<Item= &'a T>+Clone,
305        {
306            self.local.reserve(items.clone().count());
307            self.inner.reserve_items(items);
308        }
309
310        /// Ensures `Self` can absorb `items` without further allocations.
311        ///
312        /// The argument `items` may be cloned and iterated multiple times.
313        /// Please be careful if it contains side effects.
314        #[inline(always)]
315        pub fn reserve_regions<'a, I>(&mut self, regions: I)
316        where
317            Self: 'a,
318            I: Iterator<Item= &'a Self>+Clone,
319        {
320            self.local.reserve(regions.clone().map(|cs| cs.local.len()).sum());
321            self.inner.reserve_regions(regions.map(|cs| &cs.inner));
322        }
323
324
325        /// Copies an element in to the region.
326        ///
327        /// The element can be read by indexing
328        pub fn copy(&mut self, item: &T) {
329            // TODO: Some types `T` should just be cloned.
330            // E.g. types that are `Copy` or vecs of ZSTs.
331            unsafe {
332                self.local.push(self.inner.copy(item));
333            }
334        }
335        /// Empties the collection.
336        pub fn clear(&mut self) {
337            unsafe {
338                // Unsafety justified in that setting the length to zero exposes
339                // no invalid data.
340                self.local.set_len(0);
341                self.inner.clear();
342            }
343        }
344        /// Retain elements that pass a predicate, from a specified offset.
345        ///
346        /// This method may or may not reclaim memory in the inner region.
347        pub fn retain_from<P: FnMut(&T)->bool>(&mut self, index: usize, mut predicate: P) {
348            if index < self.local.len() {
349                let mut write_position = index;
350                for position in index .. self.local.len() {
351                    if predicate(&self[position]) {
352                        // TODO: compact the inner region and update pointers.
353                        self.local.swap(position, write_position);
354                        write_position += 1;
355                    }
356                }
357                unsafe {
358                    // Unsafety justified in that `write_position` is no greater than
359                    // `self.local.len()` and so this exposes no invalid data.
360                    self.local.set_len(write_position);
361                }
362            }
363        }
364
365        /// Estimate the memory capacity in bytes.
366        #[inline]
367        pub fn heap_size(&self, mut callback: impl FnMut(usize, usize)) {
368            let size_of = std::mem::size_of::<T>();
369            callback(self.local.len() * size_of, self.local.capacity() * size_of);
370            self.inner.heap_size(callback);
371        }
372
373        /// Estimate the consumed memory capacity in bytes, summing both used and total capacity.
374        #[inline]
375        pub fn summed_heap_size(&self) -> (usize, usize) {
376            let (mut length, mut capacity) = (0, 0);
377            self.heap_size(|len, cap| {
378                length += len;
379                capacity += cap
380            });
381            (length, capacity)
382        }
383    }
384
385    impl<T: Columnation> std::ops::Deref for ColumnStack<T> {
386        type Target = [T];
387        #[inline(always)]
388        fn deref(&self) -> &Self::Target {
389            &self.local[..]
390        }
391    }
392
393    impl<T: Columnation> Drop for ColumnStack<T> {
394        fn drop(&mut self) {
395            self.clear();
396        }
397    }
398
399    impl<T: Columnation> Default for ColumnStack<T> {
400        fn default() -> Self {
401            Self {
402                local: Vec::new(),
403                inner: T::InnerRegion::default(),
404            }
405        }
406    }
407
408    impl<'a, T: Columnation + 'a> Extend<&'a T> for ColumnStack<T> {
409        fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) {
410            for element in iter {
411                self.copy(element)
412            }
413        }
414    }
415
416    impl<'a, T: Columnation + 'a> std::iter::FromIterator<&'a T> for ColumnStack<T> {
417        fn from_iter<I: IntoIterator<Item=&'a T>>(iter: I) -> Self {
418            let iter = iter.into_iter();
419            let mut c = ColumnStack::<T>::with_capacity(iter.size_hint().0);
420            c.extend(iter);
421            c
422        }
423    }
424
425    impl<T: Columnation + PartialEq> PartialEq for ColumnStack<T> {
426        fn eq(&self, other: &Self) -> bool {
427            PartialEq::eq(&self[..], &other[..])
428        }
429    }
430
431    impl<T: Columnation + Eq> Eq for ColumnStack<T> {}
432
433    impl<T: Columnation + std::fmt::Debug> std::fmt::Debug for ColumnStack<T> {
434        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
435            (&self[..]).fmt(f)
436        }
437    }
438
439    impl<T: Columnation> Clone for ColumnStack<T> {
440        fn clone(&self) -> Self {
441            let mut new: Self = Default::default();
442            for item in &self[..] {
443                new.copy(item);
444            }
445            new
446        }
447
448        fn clone_from(&mut self, source: &Self) {
449            self.clear();
450            for item in &source[..] {
451                self.copy(item);
452            }
453        }
454    }
455}
456
457mod implementations {
458
459    use super::{Region, CopyRegion, StableRegion, Columnation, ColumnStack};
460
461    // Implementations for types whose `clone()` suffices for the region.
462    macro_rules! implement_columnation {
463        ($index_type:ty) => (
464            impl Columnation for $index_type {
465                type InnerRegion = CopyRegion<$index_type>;
466            }
467        )
468    }
469    implement_columnation!(());
470    implement_columnation!(bool);
471    implement_columnation!(char);
472
473    implement_columnation!(u8);
474    implement_columnation!(u16);
475    implement_columnation!(u32);
476    implement_columnation!(u64);
477    implement_columnation!(u128);
478    implement_columnation!(usize);
479
480    implement_columnation!(i8);
481    implement_columnation!(i16);
482    implement_columnation!(i32);
483    implement_columnation!(i64);
484    implement_columnation!(i128);
485    implement_columnation!(isize);
486
487    implement_columnation!(f32);
488    implement_columnation!(f64);
489
490    implement_columnation!(std::num::Wrapping<i8>);
491    implement_columnation!(std::num::Wrapping<i16>);
492    implement_columnation!(std::num::Wrapping<i32>);
493    implement_columnation!(std::num::Wrapping<i64>);
494    implement_columnation!(std::num::Wrapping<i128>);
495    implement_columnation!(std::num::Wrapping<isize>);
496
497    implement_columnation!(std::time::Duration);
498
499    /// Implementations for `Option<T: Columnation>`.
500    pub mod option {
501
502        use super::{Columnation, Region};
503
504        #[derive(Default)]
505        pub struct OptionRegion<R: Region> {
506            region: R,
507        }
508
509        impl<R: Region> Region for OptionRegion<R> {
510            type Item = Option<R::Item>;
511            #[inline(always)]
512            unsafe fn copy(&mut self, item: &Self::Item) -> Self::Item {
513                item.as_ref().map(|inner| self.region.copy(inner))
514            }
515            #[inline(always)]
516            fn clear(&mut self) {
517                self.region.clear();
518            }
519            #[inline(always)]
520            fn reserve_items<'a, I>(&mut self, items: I)
521            where
522                Self: 'a,
523                I: Iterator<Item=&'a Self::Item>+Clone,
524            {
525                self.region.reserve_items(items.flat_map(|x| x.as_ref()));
526            }
527
528            fn reserve_regions<'a, I>(&mut self, regions: I)
529            where
530                Self: 'a,
531                I: Iterator<Item = &'a Self> + Clone,
532            {
533                self.region.reserve_regions(regions.map(|r| &r.region));
534            }
535            #[inline]
536            fn heap_size(&self, callback: impl FnMut(usize, usize)) {
537                self.region.heap_size(callback)
538            }
539        }
540
541        impl<T: Columnation> Columnation for Option<T> {
542            type InnerRegion = OptionRegion<T::InnerRegion>;
543        }
544    }
545
546    /// Implementations for `Result<T: Columnation, E: Columnation>`.
547    pub mod result {
548
549        use super::{Columnation, Region};
550
551        #[derive(Default)]
552        pub struct ResultRegion<R1: Region, R2: Region> {
553            region1: R1,
554            region2: R2,
555        }
556
557
558        impl<R1: Region, R2: Region> Region for ResultRegion<R1, R2> {
559            type Item = Result<R1::Item, R2::Item>;
560            #[inline(always)]
561            unsafe fn copy(&mut self, item: &Self::Item) -> Self::Item {
562                match item {
563                    Ok(item) => { Ok(self.region1.copy(item)) },
564                    Err(item) => { Err(self.region2.copy(item)) },
565                }
566            }
567            #[inline(always)]
568            fn clear(&mut self) {
569                self.region1.clear();
570                self.region2.clear();
571            }
572            #[inline]
573            fn reserve_items<'a, I>(&mut self, items: I)
574            where
575                Self: 'a,
576                I: Iterator<Item=&'a Self::Item>+Clone,
577            {
578                let items2 = items.clone();
579                self.region1.reserve_items(items2.flat_map(|x| x.as_ref().ok()));
580                self.region2.reserve_items(items.flat_map(|x| x.as_ref().err()));
581            }
582
583            fn reserve_regions<'a, I>(&mut self, regions: I)
584            where
585                Self: 'a,
586                I: Iterator<Item = &'a Self> + Clone,
587            {
588                self.region1.reserve_regions(regions.clone().map(|r| &r.region1));
589                self.region2.reserve_regions(regions.map(|r| &r.region2));
590            }
591            #[inline]
592            fn heap_size(&self, mut callback: impl FnMut(usize, usize)) {
593                self.region1.heap_size(&mut callback);
594                self.region2.heap_size(callback)
595            }
596        }
597
598        impl<T: Columnation, E: Columnation> Columnation for Result<T, E> {
599            type InnerRegion = ResultRegion<T::InnerRegion, E::InnerRegion>;
600        }
601    }
602
603    /// Implementations for `Vec<T: Columnation>`.
604    pub mod vec {
605
606        use super::{Columnation, Region, StableRegion};
607
608        /// Region allocation for the contents of `Vec<T>` types.
609        ///
610        /// Items `T` are stored in stable contiguous memory locations,
611        /// and then a `Vec<T>` referencing them is falsified.
612        pub struct VecRegion<T: Columnation> {
613            /// Region for stable memory locations for `T` items.
614            region: StableRegion<T>,
615            /// Any inner region allocations.
616            inner: T::InnerRegion,
617        }
618
619        // Manually implement `Default` as `T` may not implement it.
620        impl<T: Columnation> Default for VecRegion<T> {
621            fn default() -> Self {
622                VecRegion {
623                    region: StableRegion::<T>::default(),
624                    inner: T::InnerRegion::default(),
625                }
626            }
627        }
628
629        impl<T: Columnation> Columnation for Vec<T> {
630            type InnerRegion = VecRegion<T>;
631        }
632
633        impl<T: Columnation> Region for VecRegion<T> {
634            type Item = Vec<T>;
635            #[inline]
636            fn clear(&mut self) {
637                self.region.clear();
638                self.inner.clear();
639            }
640            #[inline(always)]
641            unsafe fn copy(&mut self, item: &Self::Item) -> Self::Item {
642                // TODO: Some types `T` should just be cloned, with `copy_slice`.
643                // E.g. types that are `Copy` or vecs of ZSTs.
644                let inner = &mut self.inner;
645                let slice = self.region.copy_iter(item.iter().map(|element| inner.copy(element)));
646                Vec::from_raw_parts(slice.as_mut_ptr(), item.len(), item.len())
647            }
648            #[inline(always)]
649            fn reserve_items<'a, I>(&mut self, items: I)
650            where
651                Self: 'a,
652                I: Iterator<Item=&'a Self::Item>+Clone,
653            {
654                self.region.reserve(items.clone().count());
655                self.inner.reserve_items(items.flat_map(|x| x.iter()));
656            }
657
658            fn reserve_regions<'a, I>(&mut self, regions: I)
659            where
660                Self: 'a,
661                I: Iterator<Item = &'a Self> + Clone,
662            {
663                self.region.reserve(regions.clone().map(|r| r.region.len()).sum());
664                self.inner.reserve_regions(regions.map(|r| &r.inner));
665            }
666            #[inline]
667            fn heap_size(&self, mut callback: impl FnMut(usize, usize)) {
668                self.inner.heap_size(&mut callback);
669                self.region.heap_size(callback);
670            }
671        }
672    }
673
674    /// Implementation for `String`.
675    pub mod string {
676
677        use super::{Columnation, Region, StableRegion};
678
679        /// Region allocation for `String` data.
680        ///
681        /// Content bytes are stored in stable contiguous memory locations,
682        /// and then a `String` referencing them is falsified.
683        #[derive(Default)]
684        pub struct StringStack {
685            region: StableRegion<u8>,
686        }
687
688        impl Columnation for String {
689            type InnerRegion = StringStack;
690        }
691
692        impl Region for StringStack {
693            type Item = String;
694            #[inline]
695            fn clear(&mut self) {
696                self.region.clear();
697            }
698            // Removing `(always)` is a 20% performance regression in
699            // the `string10_copy` benchmark.
700            #[inline(always)] unsafe fn copy(&mut self, item: &String) -> String {
701                let bytes = self.region.copy_slice(item.as_bytes());
702                String::from_raw_parts(bytes.as_mut_ptr(), item.len(), item.len())
703            }
704            #[inline(always)]
705            fn reserve_items<'a, I>(&mut self, items: I)
706            where
707                Self: 'a,
708                I: Iterator<Item=&'a Self::Item>+Clone,
709            {
710                self.region.reserve(items.map(|x| x.len()).sum());
711            }
712
713            fn reserve_regions<'a, I>(&mut self, regions: I)
714            where
715                Self: 'a,
716                I: Iterator<Item = &'a Self> + Clone,
717            {
718                self.region.reserve(regions.clone().map(|r| r.region.len()).sum());
719            }
720            #[inline]
721            fn heap_size(&self, callback: impl FnMut(usize, usize)) {
722                self.region.heap_size(callback)
723            }
724        }
725    }
726
727    /// Implementation for tuples.
728    pub mod tuple {
729
730        use super::{Columnation, ColumnStack, Region};
731
732        use paste::paste;
733
734        macro_rules! tuple_columnation_inner1 {
735            ([$name0:tt $($name:tt)*], [($index0:tt) $(($index:tt))*], $self:tt, $items:tt) => ( paste! {
736                    $self.[<region $name0>].reserve_items($items.clone().map(|item| {
737                        &item.$index0
738                    }));
739                    tuple_columnation_inner1!([$($name)*], [$(($index))*], $self, $items);
740                }
741            );
742            ([], [$(($index:tt))*], $self:ident, $items:ident) => ( );
743        }
744
745        // This macro is copied from the above macro, but could probably be simpler as it does not need indexes.
746        macro_rules! tuple_columnation_inner2 {
747            ([$name0:tt $($name:tt)*], [($index0:tt) $(($index:tt))*], $self:tt, $regions:tt) => ( paste! {
748                    $self.[<region $name0>].reserve_regions($regions.clone().map(|region| {
749                        &region.[<region $name0>]
750                    }));
751                    tuple_columnation_inner2!([$($name)*], [$(($index))*], $self, $regions);
752                }
753            );
754            ([], [$(($index:tt))*], $self:ident, $regions:ident) => ( );
755        }
756
757        /// The macro creates the region implementation for tuples
758        macro_rules! tuple_columnation {
759            ( $($name:ident)+) => ( paste! {
760                impl<$($name: Columnation),*> Columnation for ($($name,)*) {
761                    type InnerRegion = [<Tuple $($name)* Region >]<$($name::InnerRegion,)*>;
762                }
763
764                #[allow(non_snake_case)]
765                #[derive(Default)]
766                pub struct [<Tuple $($name)* Region >]<$($name: Region),*> {
767                    $([<region $name>]: $name),*
768                }
769
770                #[allow(non_snake_case)]
771                impl<$($name: Region),*> [<Tuple $($name)* Region>]<$($name),*> {
772                    #[allow(clippy::too_many_arguments)]
773                    #[inline] pub unsafe fn copy_destructured(&mut self, $([<r $name>]: &$name::Item),*) -> <[<Tuple $($name)* Region>]<$($name),*> as Region>::Item {
774                        (
775                            $(self.[<region $name>].copy(&[<r $name>]),)*
776                        )
777                    }
778                }
779
780                #[allow(non_snake_case)]
781                impl<$($name: Region),*> Region for [<Tuple $($name)* Region>]<$($name),*> {
782                    type Item = ($($name::Item,)*);
783                    #[inline]
784                    fn clear(&mut self) {
785                        $(self.[<region $name>].clear());*
786                    }
787                    #[inline] unsafe fn copy(&mut self, item: &Self::Item) -> Self::Item {
788                        let ($(ref $name,)*) = *item;
789                        (
790                            $(self.[<region $name>].copy($name),)*
791                        )
792                    }
793                    #[inline(always)]
794                    fn reserve_items<'a, It>(&mut self, items: It)
795                    where
796                        Self: 'a,
797                        It: Iterator<Item=&'a Self::Item>+Clone,
798                    {
799                        tuple_columnation_inner1!([$($name)+], [(0) (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)], self, items);
800                    }
801
802                    #[inline(always)]
803                    fn reserve_regions<'a, It>(&mut self, regions: It)
804                    where
805                        Self: 'a,
806                        It: Iterator<Item = &'a Self> + Clone,
807                    {
808                        tuple_columnation_inner2!([$($name)+], [(0) (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)], self, regions);
809                    }
810                    #[inline] fn heap_size(&self, mut callback: impl FnMut(usize, usize)) {
811                        $(self.[<region $name>].heap_size(&mut callback);)*
812                    }
813                }
814                }
815                tuple_column_stack!(ColumnStack, $($name)*);
816            );
817        }
818
819        /// The macro creates the `copy_destructured` implementation for a custom column stack
820        /// with a single generic parameter characterizing the type `T` it stores.
821        /// It assumes there are two fields on `self`:
822        /// * `local`: A type supporting `push(T)`, e.g, `Vec`.
823        /// * `inner`: A region of type `T`.
824        /// We're exporting this macro so custom `ColumnStack` implementations can benefit from it.
825        #[macro_export]
826        macro_rules! tuple_column_stack {
827            ( $type:ident, $($name:ident)+) => (
828                #[allow(non_snake_case)]
829                impl<$($name: Columnation),*> $type<($($name,)*)> {
830                    /// Copies a destructured tuple into this column stack.
831                    ///
832                    /// This serves situations where a tuple should be constructed from its constituents but not
833                    /// not all elements are available as owned data.
834                    ///
835                    /// The element can be read by indexing
836                    pub fn copy_destructured(&mut self, $($name: &$name,)*) {
837                        unsafe {
838                            self.local.push(self.inner.copy_destructured($($name,)*));
839                        }
840                    }
841                }
842            );
843        }
844
845        tuple_columnation!(A);
846        tuple_columnation!(A B);
847        tuple_columnation!(A B C);
848        tuple_columnation!(A B C D);
849        tuple_columnation!(A B C D E);
850        tuple_columnation!(A B C D E F);
851        tuple_columnation!(A B C D E F G);
852        tuple_columnation!(A B C D E F G H);
853        tuple_columnation!(A B C D E F G H I);
854        tuple_columnation!(A B C D E F G H I J);
855        tuple_columnation!(A B C D E F G H I J K);
856        tuple_columnation!(A B C D E F G H I J K L);
857        tuple_columnation!(A B C D E F G H I J K L M);
858        tuple_columnation!(A B C D E F G H I J K L M N);
859        tuple_columnation!(A B C D E F G H I J K L M N O);
860        tuple_columnation!(A B C D E F G H I J K L M N O P);
861        tuple_columnation!(A B C D E F G H I J K L M N O P Q);
862        tuple_columnation!(A B C D E F G H I J K L M N O P Q R);
863        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S);
864        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T);
865        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U);
866        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V);
867        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W);
868        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X);
869        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X Y);
870        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z);
871        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA);
872        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB);
873        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB AC);
874        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB AC AD);
875        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB AC AD AE);
876        tuple_columnation!(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB AC AD AE AF);
877    }
878}
columnation/lib.rs

columnation/
lib.rs
