timely/
order.rs

Help
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<Rhs: ?Sized = Self>: PartialEq<Rhs> {
9    /// Returns `true` iff one element is strictly less than the other.
10    fn less_than(&self, other: &Rhs) -> 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: &Rhs) -> 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    use columnar::Columnar;
64    use serde::{Deserialize, Serialize};
65
66    use columnation::{Columnation, Region};
67    use crate::order::{Empty, TotalOrder};
68    use crate::progress::Timestamp;
69    use crate::progress::timestamp::PathSummary;
70    use crate::progress::timestamp::Refines;
71
72    /// A nested pair of timestamps, one outer and one inner.
73    ///
74    /// We use `Product` rather than `(TOuter, TInner)` so that we can derive our own `PartialOrder`,
75    /// because Rust just uses the lexicographic total order.
76    #[derive(Copy, Clone, Hash, Eq, PartialEq, Default, Ord, PartialOrd, Serialize, Deserialize, Columnar)]
77    #[columnar(derive(Eq, PartialEq, Ord, PartialOrd))]
78    pub struct Product<TOuter, TInner> {
79        /// Outer timestamp.
80        pub outer: TOuter,
81        /// Inner timestamp.
82        pub inner: TInner,
83    }
84
85    impl<TOuter, TInner> Product<TOuter, TInner> {
86        /// Creates a new product from outer and inner coordinates.
87        pub fn new(outer: TOuter, inner: TInner) -> Self {
88            Product {
89                outer,
90                inner,
91            }
92        }
93    }
94
95    // Debug implementation to avoid seeing fully qualified path names.
96    impl<TOuter: Debug, TInner: Debug> Debug for Product<TOuter, TInner> {
97        fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
98            f.write_str(&format!("({:?}, {:?})", self.outer, self.inner))
99        }
100    }
101
102    use super::PartialOrder;
103    impl<TOuter, TOuter2, TInner, TInner2> PartialOrder<Product<TOuter2, TInner2>> for Product<TOuter, TInner>
104    where
105        TOuter: PartialOrder<TOuter2>,
106        TInner: PartialOrder<TInner2>,
107        Self: PartialEq<Product<TOuter2, TInner2>>,
108    {
109        #[inline]
110        fn less_equal(&self, other: &Product<TOuter2, TInner2>) -> bool {
111            self.outer.less_equal(&other.outer) && self.inner.less_equal(&other.inner)
112        }
113    }
114
115    impl<TOuter: Timestamp, TInner: Timestamp> Timestamp for Product<TOuter, TInner> {
116        type Summary = Product<TOuter::Summary, TInner::Summary>;
117        fn minimum() -> Self { Self { outer: TOuter::minimum(), inner: TInner::minimum() }}
118    }
119
120    impl<TOuter: Timestamp, TInner: Timestamp> PathSummary<Product<TOuter, TInner>> for Product<TOuter::Summary, TInner::Summary> {
121        #[inline]
122        fn results_in(&self, product: &Product<TOuter, TInner>) -> Option<Product<TOuter, TInner>> {
123            self.outer.results_in(&product.outer)
124                .and_then(|outer|
125                    self.inner.results_in(&product.inner)
126                        .map(|inner| Product::new(outer, inner))
127                )
128        }
129        #[inline]
130        fn followed_by(&self, other: &Self) -> Option<Self> {
131            self.outer.followed_by(&other.outer)
132                .and_then(|outer|
133                    self.inner.followed_by(&other.inner)
134                        .map(|inner| Product::new(outer, inner))
135                )
136        }
137    }
138
139    impl<TOuter: Timestamp, TInner: Timestamp> Refines<TOuter> for Product<TOuter, TInner> {
140        fn to_inner(other: TOuter) -> Self {
141            Product::new(other, TInner::minimum())
142        }
143        fn to_outer(self: Product<TOuter, TInner>) -> TOuter {
144            self.outer
145        }
146        fn summarize(path: <Self as Timestamp>::Summary) -> <TOuter as Timestamp>::Summary {
147            path.outer
148        }
149    }
150
151    impl<T1: Empty, T2: Empty> Empty for Product<T1, T2> { }
152    impl<T1, T2> TotalOrder for Product<T1, T2> where T1: Empty, T2: TotalOrder { }
153
154    impl<T1: Columnation, T2: Columnation> Columnation for Product<T1, T2> {
155        type InnerRegion = ProductRegion<T1::InnerRegion, T2::InnerRegion>;
156    }
157
158    #[derive(Default)]
159    pub struct ProductRegion<T1, T2> {
160        outer_region: T1,
161        inner_region: T2,
162    }
163
164    impl<T1: Region, T2: Region> Region for ProductRegion<T1, T2> {
165        type Item = Product<T1::Item, T2::Item>;
166
167        #[inline]
168        unsafe fn copy(&mut self, item: &Self::Item) -> Self::Item {
169            Product { outer: self.outer_region.copy(&item.outer), inner: self.inner_region.copy(&item.inner) }
170        }
171
172        fn clear(&mut self) {
173            self.outer_region.clear();
174            self.inner_region.clear();
175        }
176
177        fn reserve_items<'a, I>(&mut self, items1: I) where Self: 'a, I: Iterator<Item=&'a Self::Item> + Clone {
178            let items2 = items1.clone();
179            self.outer_region.reserve_items(items1.map(|x| &x.outer));
180            self.inner_region.reserve_items(items2.map(|x| &x.inner))
181        }
182
183        fn reserve_regions<'a, I>(&mut self, regions1: I) where Self: 'a, I: Iterator<Item=&'a Self> + Clone {
184            let regions2 = regions1.clone();
185            self.outer_region.reserve_regions(regions1.map(|r| &r.outer_region));
186            self.inner_region.reserve_regions(regions2.map(|r| &r.inner_region));
187        }
188
189        fn heap_size(&self, mut callback: impl FnMut(usize, usize)) {
190            self.outer_region.heap_size(&mut callback);
191            self.inner_region.heap_size(callback);
192        }
193    }
194}
195
196/// Rust tuple ordered by the lexicographic order.
197mod tuple {
198
199    use super::PartialOrder;
200    impl<TOuter, TOuter2, TInner, TInner2> PartialOrder<(TOuter2, TInner2)> for (TOuter, TInner)
201    where
202        TOuter: PartialOrder<TOuter2>,
203        TInner: PartialOrder<TInner2>,
204        (TOuter, TInner): PartialEq<(TOuter2, TInner2)>,
205    {
206        #[inline]
207        fn less_equal(&self, other: &(TOuter2, TInner2)) -> bool {
208            // We avoid Rust's `PartialOrd` implementation, for reasons of correctness.
209            self.0.less_than(&other.0) || (self.0.eq(&other.0) && self.1.less_equal(&other.1))
210        }
211    }
212
213    use super::TotalOrder;
214    impl<T1, T2> TotalOrder for (T1, T2) where T1: TotalOrder, T2: TotalOrder { }
215
216    use crate::progress::Timestamp;
217    impl<TOuter: Timestamp, TInner: Timestamp> Timestamp for (TOuter, TInner) {
218        type Summary = (TOuter::Summary, TInner::Summary);
219        fn minimum() -> Self { (TOuter::minimum(), TInner::minimum()) }
220    }
221
222    use crate::progress::timestamp::PathSummary;
223    impl<TOuter: Timestamp, TInner: Timestamp> PathSummary<(TOuter, TInner)> for (TOuter::Summary, TInner::Summary) {
224        #[inline]
225        fn results_in(&self, (outer, inner): &(TOuter, TInner)) -> Option<(TOuter, TInner)> {
226            self.0.results_in(outer)
227                .and_then(|outer|
228                    self.1.results_in(inner)
229                        .map(|inner| (outer, inner))
230                )
231        }
232        #[inline]
233        fn followed_by(&self, (outer, inner): &(TOuter::Summary, TInner::Summary)) -> Option<(TOuter::Summary, TInner::Summary)> {
234            self.0.followed_by(outer)
235                .and_then(|outer|
236                    self.1.followed_by(inner)
237                        .map(|inner| (outer, inner))
238                )
239        }
240    }
241
242    use crate::progress::timestamp::Refines;
243    impl<TOuter: Timestamp, TInner: Timestamp> Refines<TOuter> for (TOuter, TInner) {
244        fn to_inner(other: TOuter) -> Self {
245            (other, TInner::minimum())
246        }
247        fn to_outer(self: (TOuter, TInner)) -> TOuter {
248            self.0
249        }
250        fn summarize(path: <Self as Timestamp>::Summary) -> <TOuter as Timestamp>::Summary {
251            path.0
252        }
253    }
254
255    use super::Empty;
256    impl<T1: Empty, T2: Empty> Empty for (T1, T2) { }
257}
timely/order.rs

timely/
order.rs
