timely/
order.rs

1//! Traits and types for partially ordered sets.
2
3/// A type that is partially ordered.
4///
5/// This trait is distinct from Rust's `PartialOrd` trait, because the implementation
6/// of that trait precludes a distinct `Ord` implementation. We need an independent
7/// trait if we want to have a partially ordered type that can also be sorted.
8pub trait PartialOrder : Eq {
9    /// Returns true iff one element is strictly less than the other.
10    fn less_than(&self, other: &Self) -> bool {
11        self.less_equal(other) && self != other
12    }
13    /// Returns true iff one element is less than or equal to the other.
14    fn less_equal(&self, other: &Self) -> bool;
15}
16
17/// A type that is totally ordered.
18///
19/// This trait is a "carrier trait", in the sense that it adds no additional functionality
20/// over `PartialOrder`, but instead indicates that the `less_than` and `less_equal` methods
21/// are total, meaning that `x.less_than(&y)` is equivalent to `!y.less_equal(&x)`.
22///
23/// This trait is distinct from Rust's `Ord` trait, because several implementors of
24/// `PartialOrd` also implement `Ord` for efficient canonicalization, deduplication,
25/// and other sanity-maintaining operations.
26pub trait TotalOrder : PartialOrder { }
27
28/// A type that does not affect total orderedness.
29///
30/// This trait is not useful, but must be made public and documented or else Rust
31/// complains about its existence in the constraints on the implementation of
32/// public traits for public types.
33pub trait Empty : PartialOrder { }
34
35impl Empty for () { }
36
37macro_rules! implement_partial {
38    ($($index_type:ty,)*) => (
39        $(
40            impl PartialOrder for $index_type {
41                #[inline] fn less_than(&self, other: &Self) -> bool { self < other }
42                #[inline] fn less_equal(&self, other: &Self) -> bool { self <= other }
43            }
44        )*
45    )
46}
47
48macro_rules! implement_total {
49    ($($index_type:ty,)*) => (
50        $(
51            impl TotalOrder for $index_type { }
52        )*
53    )
54}
55
56implement_partial!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, (), ::std::time::Duration,);
57implement_total!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, (), ::std::time::Duration,);
58
59pub use product::Product;
60/// A pair of timestamps, partially ordered by the product order.
61mod product {
62    use std::fmt::{Formatter, Error, Debug};
63
64    use crate::container::columnation::{Columnation, Region};
65    use crate::order::{Empty, TotalOrder};
66    use crate::progress::Timestamp;
67    use crate::progress::timestamp::PathSummary;
68    use crate::progress::timestamp::Refines;
69
70    /// A nested pair of timestamps, one outer and one inner.
71    ///
72    /// We use `Product` rather than `(TOuter, TInner)` so that we can derive our own `PartialOrder`,
73    /// because Rust just uses the lexicographic total order.
74    #[derive(Abomonation, Copy, Clone, Hash, Eq, PartialEq, Default, Ord, PartialOrd, Serialize, Deserialize)]
75    pub struct Product<TOuter, TInner> {
76        /// Outer timestamp.
77        pub outer: TOuter,
78        /// Inner timestamp.
79        pub inner: TInner,
80    }
81
82    impl<TOuter, TInner> Product<TOuter, TInner> {
83        /// Creates a new product from outer and inner coordinates.
84        pub fn new(outer: TOuter, inner: TInner) -> Self {
85            Product {
86                outer,
87                inner,
88            }
89        }
90    }
91
92    // Debug implementation to avoid seeing fully qualified path names.
93    impl<TOuter: Debug, TInner: Debug> Debug for Product<TOuter, TInner> {
94        fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
95            f.write_str(&format!("({:?}, {:?})", self.outer, self.inner))
96        }
97    }
98
99    use super::PartialOrder;
100    impl<TOuter: PartialOrder, TInner: PartialOrder> PartialOrder for Product<TOuter, TInner> {
101        #[inline]
102        fn less_equal(&self, other: &Self) -> bool {
103            self.outer.less_equal(&other.outer) && self.inner.less_equal(&other.inner)
104        }
105    }
106
107    impl<TOuter: Timestamp, TInner: Timestamp> Timestamp for Product<TOuter, TInner> {
108        type Summary = Product<TOuter::Summary, TInner::Summary>;
109        fn minimum() -> Self { Self { outer: TOuter::minimum(), inner: TInner::minimum() }}
110    }
111
112    impl<TOuter: Timestamp, TInner: Timestamp> PathSummary<Product<TOuter, TInner>> for Product<TOuter::Summary, TInner::Summary> {
113        #[inline]
114        fn results_in(&self, product: &Product<TOuter, TInner>) -> Option<Product<TOuter, TInner>> {
115            self.outer.results_in(&product.outer)
116                .and_then(|outer|
117                    self.inner.results_in(&product.inner)
118                        .map(|inner| Product::new(outer, inner))
119                )
120        }
121        #[inline]
122        fn followed_by(&self, other: &Self) -> Option<Self> {
123            self.outer.followed_by(&other.outer)
124                .and_then(|outer|
125                    self.inner.followed_by(&other.inner)
126                        .map(|inner| Product::new(outer, inner))
127                )
128        }
129    }
130
131    impl<TOuter: Timestamp, TInner: Timestamp> Refines<TOuter> for Product<TOuter, TInner> {
132        fn to_inner(other: TOuter) -> Self {
133            Product::new(other, TInner::minimum())
134        }
135        fn to_outer(self: Product<TOuter, TInner>) -> TOuter {
136            self.outer
137        }
138        fn summarize(path: <Self as Timestamp>::Summary) -> <TOuter as Timestamp>::Summary {
139            path.outer
140        }
141    }
142
143    impl<T1: Empty, T2: Empty> Empty for Product<T1, T2> { }
144    impl<T1, T2> TotalOrder for Product<T1, T2> where T1: Empty, T2: TotalOrder { }
145
146    impl<T1: Columnation, T2: Columnation> Columnation for Product<T1, T2> {
147        type InnerRegion = ProductRegion<T1::InnerRegion, T2::InnerRegion>;
148    }
149
150    #[derive(Default)]
151    pub struct ProductRegion<T1, T2> {
152        outer_region: T1,
153        inner_region: T2,
154    }
155
156    impl<T1: Region, T2: Region> Region for ProductRegion<T1, T2> {
157        type Item = Product<T1::Item, T2::Item>;
158
159        #[inline]
160        unsafe fn copy(&mut self, item: &Self::Item) -> Self::Item {
161            Product { outer: self.outer_region.copy(&item.outer), inner: self.inner_region.copy(&item.inner) }
162        }
163
164        fn clear(&mut self) {
165            self.outer_region.clear();
166            self.inner_region.clear();
167        }
168
169        fn reserve_items<'a, I>(&mut self, items1: I) where Self: 'a, I: Iterator<Item=&'a Self::Item> + Clone {
170            let items2 = items1.clone();
171            self.outer_region.reserve_items(items1.map(|x| &x.outer));
172            self.inner_region.reserve_items(items2.map(|x| &x.inner))
173        }
174
175        fn reserve_regions<'a, I>(&mut self, regions1: I) where Self: 'a, I: Iterator<Item=&'a Self> + Clone {
176            let regions2 = regions1.clone();
177            self.outer_region.reserve_regions(regions1.map(|r| &r.outer_region));
178            self.inner_region.reserve_regions(regions2.map(|r| &r.inner_region));
179        }
180
181        fn heap_size(&self, mut callback: impl FnMut(usize, usize)) {
182            self.outer_region.heap_size(&mut callback);
183            self.inner_region.heap_size(callback);
184        }
185    }
186}
187
188/// Rust tuple ordered by the lexicographic order.
189mod tuple {
190
191    use super::PartialOrder;
192    impl<TOuter: PartialOrder, TInner: PartialOrder> PartialOrder for (TOuter, TInner) {
193        #[inline]
194        fn less_equal(&self, other: &Self) -> bool {
195            // We avoid Rust's `PartialOrd` implementation, for reasons of correctness.
196            self.0.less_than(&other.0) || (self.0.eq(&other.0) && self.1.less_equal(&other.1))
197        }
198    }
199
200    use super::TotalOrder;
201    impl<T1, T2> TotalOrder for (T1, T2) where T1: TotalOrder, T2: TotalOrder { }
202
203    use crate::progress::Timestamp;
204    impl<TOuter: Timestamp, TInner: Timestamp> Timestamp for (TOuter, TInner) {
205        type Summary = (TOuter::Summary, TInner::Summary);
206        fn minimum() -> Self { (TOuter::minimum(), TInner::minimum()) }
207    }
208
209    use crate::progress::timestamp::PathSummary;
210    impl<TOuter: Timestamp, TInner: Timestamp> PathSummary<(TOuter, TInner)> for (TOuter::Summary, TInner::Summary) {
211        #[inline]
212        fn results_in(&self, (outer, inner): &(TOuter, TInner)) -> Option<(TOuter, TInner)> {
213            self.0.results_in(outer)
214                .and_then(|outer|
215                    self.1.results_in(inner)
216                        .map(|inner| (outer, inner))
217                )
218        }
219        #[inline]
220        fn followed_by(&self, (outer, inner): &(TOuter::Summary, TInner::Summary)) -> Option<(TOuter::Summary, TInner::Summary)> {
221            self.0.followed_by(outer)
222                .and_then(|outer|
223                    self.1.followed_by(inner)
224                        .map(|inner| (outer, inner))
225                )
226        }
227    }
228
229    use crate::progress::timestamp::Refines;
230    impl<TOuter: Timestamp, TInner: Timestamp> Refines<TOuter> for (TOuter, TInner) {
231        fn to_inner(other: TOuter) -> Self {
232            (other, TInner::minimum())
233        }
234        fn to_outer(self: (TOuter, TInner)) -> TOuter {
235            self.0
236        }
237        fn summarize(path: <Self as Timestamp>::Summary) -> <TOuter as Timestamp>::Summary {
238            path.0
239        }
240    }
241
242    use super::Empty;
243    impl<T1: Empty, T2: Empty> Empty for (T1, T2) { }
244}
timely/order.rs

timely/
order.rs
