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

timely/
order.rs
