mz_repr/adt/
range.rs

1// Copyright Materialize, Inc. and contributors. All rights reserved.
2//
3// Use of this software is governed by the Business Source License
4// included in the LICENSE file.
5//
6// As of the Change Date specified in that file, in accordance with
7// the Business Source License, use of this software will be governed
8// by the Apache License, Version 2.0.
9
10use std::any::type_name;
11use std::cmp::Ordering;
12use std::error::Error;
13use std::fmt::{self, Debug, Display};
14use std::hash::{Hash, Hasher};
15
16use bitflags::bitflags;
17use chrono::{DateTime, NaiveDateTime, Utc};
18use dec::OrderedDecimal;
19use mz_lowertest::MzReflect;
20use mz_proto::{RustType, TryFromProtoError};
21use postgres_protocol::types;
22#[cfg(any(test, feature = "proptest"))]
23use proptest_derive::Arbitrary;
24use serde::{Deserialize, Serialize};
25use tokio_postgres::types::{FromSql, Type as PgType};
26
27use crate::Datum;
28use crate::adt::date::Date;
29use crate::adt::numeric::Numeric;
30use crate::adt::timestamp::CheckedTimestamp;
31use crate::scalar::{DatumKind, SqlScalarType};
32
33include!(concat!(env!("OUT_DIR"), "/mz_repr.adt.range.rs"));
34
35bitflags! {
36    pub(crate) struct InternalFlags: u8 {
37        const EMPTY = 1;
38        const LB_INCLUSIVE = 1 << 1;
39        const LB_INFINITE = 1 << 2;
40        const UB_INCLUSIVE = 1 << 3;
41        const UB_INFINITE = 1 << 4;
42    }
43}
44
45bitflags! {
46    pub(crate) struct PgFlags: u8 {
47        const EMPTY = 0b0000_0001;
48        const LB_INCLUSIVE = 0b0000_0010;
49        const UB_INCLUSIVE = 0b0000_0100;
50        const LB_INFINITE = 0b0000_1000;
51        const UB_INFINITE = 0b0001_0000;
52    }
53}
54
55/// A range of values along the domain `D`.
56///
57/// `D` is generic to facilitate interoperating over multiple representation,
58/// e.g. `Datum` and `mz_pgrepr::Value`. Because of the latter, we have to
59/// "manually derive" traits over `Range`.
60///
61/// Also notable, is that `Datum`s themselves store ranges as
62/// `Range<DatumNested<'a>>`, which lets us avoid unnecessary boxing of the
63/// range's finite bounds, which are most often expressed as `Datum`.
64pub struct Range<D> {
65    /// None value represents empty range
66    pub inner: Option<RangeInner<D>>,
67}
68
69impl crate::scalar::SqlContainerType for Range<Datum<'_>> {
70    fn unwrap_element_type(container: &SqlScalarType) -> &SqlScalarType {
71        container.unwrap_range_element_type()
72    }
73    fn wrap_element_type(element: SqlScalarType) -> SqlScalarType {
74        SqlScalarType::Range {
75            element_type: Box::new(element),
76        }
77    }
78}
79
80impl<D: Display> Display for Range<D> {
81    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
82        match &self.inner {
83            None => f.write_str("empty"),
84            Some(i) => i.fmt(f),
85        }
86    }
87}
88
89impl<D: Debug> Debug for Range<D> {
90    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
91        f.debug_struct("Range").field("inner", &self.inner).finish()
92    }
93}
94
95impl<D: Clone> Clone for Range<D> {
96    fn clone(&self) -> Self {
97        Self {
98            inner: self.inner.clone(),
99        }
100    }
101}
102
103impl<D: Copy> Copy for Range<D> {}
104
105impl<D: PartialEq> PartialEq for Range<D> {
106    fn eq(&self, other: &Self) -> bool {
107        self.inner == other.inner
108    }
109}
110
111impl<D: Eq> Eq for Range<D> {}
112
113impl<D: Ord + PartialOrd> PartialOrd for Range<D> {
114    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
115        Some(self.cmp(other))
116    }
117}
118
119impl<D: Ord> Ord for Range<D> {
120    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
121        self.inner.cmp(&other.inner)
122    }
123}
124
125impl<D: Hash> Hash for Range<D> {
126    fn hash<H: Hasher>(&self, hasher: &mut H) {
127        self.inner.hash(hasher)
128    }
129}
130
131/// Trait alias for traits required for generic range function implementations.
132pub trait RangeOps<'a>:
133    Debug + Ord + PartialOrd + Eq + PartialEq + TryFrom<Datum<'a>> + Into<Datum<'a>>
134where
135    <Self as TryFrom<Datum<'a>>>::Error: std::fmt::Debug,
136{
137    /// Increment `self` one step forward, if applicable. Return `None` if
138    /// overflows.
139    fn step(self) -> Option<Self> {
140        Some(self)
141    }
142
143    fn unwrap_datum(d: Datum<'a>) -> Self {
144        <Self>::try_from(d)
145            .unwrap_or_else(|_| panic!("cannot take {} to {}", d, type_name::<Self>()))
146    }
147
148    fn err_type_name() -> &'static str;
149}
150
151impl<'a> RangeOps<'a> for i32 {
152    fn step(self) -> Option<i32> {
153        self.checked_add(1)
154    }
155
156    fn err_type_name() -> &'static str {
157        "integer"
158    }
159}
160
161impl<'a> RangeOps<'a> for i64 {
162    fn step(self) -> Option<i64> {
163        self.checked_add(1)
164    }
165
166    fn err_type_name() -> &'static str {
167        "bigint"
168    }
169}
170
171impl<'a> RangeOps<'a> for Date {
172    fn step(self) -> Option<Date> {
173        self.checked_add(1).ok()
174    }
175
176    fn err_type_name() -> &'static str {
177        "date"
178    }
179}
180
181impl<'a> RangeOps<'a> for OrderedDecimal<Numeric> {
182    fn err_type_name() -> &'static str {
183        "numeric"
184    }
185}
186
187impl<'a> RangeOps<'a> for CheckedTimestamp<NaiveDateTime> {
188    fn err_type_name() -> &'static str {
189        "timestamp"
190    }
191}
192
193impl<'a> RangeOps<'a> for CheckedTimestamp<DateTime<Utc>> {
194    fn err_type_name() -> &'static str {
195        "timestamptz"
196    }
197}
198
199// Totally generic range implementations.
200impl<D> Range<D> {
201    /// Create a new range.
202    ///
203    /// Note that when constructing `Range<Datum<'a>>`, the range must still be
204    /// canonicalized. If this becomes a common operation, we should consider
205    /// addinga `new_canonical` function that performs both steps.
206    pub fn new(inner: Option<(RangeLowerBound<D>, RangeUpperBound<D>)>) -> Range<D> {
207        Range {
208            inner: inner.map(|(lower, upper)| RangeInner { lower, upper }),
209        }
210    }
211
212    /// Get the flag bits appropriate to use in our internal (i.e. row) encoding
213    /// of range values.
214    ///
215    /// Note that this differs from the flags appropriate to encode with
216    /// Postgres, which has `UB_INFINITE` and `LB_INCLUSIVE` in the alternate
217    /// position.
218    pub fn internal_flag_bits(&self) -> u8 {
219        let mut flags = InternalFlags::empty();
220
221        match &self.inner {
222            None => {
223                flags.set(InternalFlags::EMPTY, true);
224            }
225            Some(RangeInner { lower, upper }) => {
226                flags.set(InternalFlags::EMPTY, false);
227                flags.set(InternalFlags::LB_INFINITE, lower.bound.is_none());
228                flags.set(InternalFlags::UB_INFINITE, upper.bound.is_none());
229                flags.set(InternalFlags::LB_INCLUSIVE, lower.inclusive);
230                flags.set(InternalFlags::UB_INCLUSIVE, upper.inclusive);
231            }
232        }
233
234        flags.bits()
235    }
236
237    /// Get the flag bits appropriate to use in PG-compatible encodings of range
238    /// values.
239    ///
240    /// Note that this differs from the flags appropriate for our internal
241    /// encoding, which has `UB_INFINITE` and `LB_INCLUSIVE` in the alternate
242    /// position.
243    pub fn pg_flag_bits(&self) -> u8 {
244        let mut flags = PgFlags::empty();
245
246        match &self.inner {
247            None => {
248                flags.set(PgFlags::EMPTY, true);
249            }
250            Some(RangeInner { lower, upper }) => {
251                flags.set(PgFlags::EMPTY, false);
252                flags.set(PgFlags::LB_INFINITE, lower.bound.is_none());
253                flags.set(PgFlags::UB_INFINITE, upper.bound.is_none());
254                flags.set(PgFlags::LB_INCLUSIVE, lower.inclusive);
255                flags.set(PgFlags::UB_INCLUSIVE, upper.inclusive);
256            }
257        }
258
259        flags.bits()
260    }
261
262    /// Converts `self` from having bounds of type `D` to type `O`, converting
263    /// the current bounds using `conv`.
264    pub fn into_bounds<F, O>(self, conv: F) -> Range<O>
265    where
266        F: Fn(D) -> O,
267    {
268        Range {
269            inner: self
270                .inner
271                .map(|RangeInner::<D> { lower, upper }| RangeInner::<O> {
272                    lower: RangeLowerBound {
273                        inclusive: lower.inclusive,
274                        bound: lower.bound.map(&conv),
275                    },
276                    upper: RangeUpperBound {
277                        inclusive: upper.inclusive,
278                        bound: upper.bound.map(&conv),
279                    },
280                }),
281        }
282    }
283
284    /// Like [`into_bounds`](Self::into_bounds), but the conversion may fail.
285    ///
286    /// Use this when converting each bound with a fallible function (e.g.
287    /// `into_datum`). Callers need not reach into `Range`'s internals
288    /// (`RangeInner`, `RangeLowerBound`, `RangeUpperBound`).
289    pub fn try_into_bounds<F, O, E>(self, conv: F) -> Result<Range<O>, E>
290    where
291        F: Fn(D) -> Result<O, E>,
292    {
293        let inner = match self.inner {
294            None => None,
295            Some(RangeInner { lower, upper }) => Some(RangeInner {
296                lower: RangeLowerBound {
297                    inclusive: lower.inclusive,
298                    bound: lower.bound.map(&conv).transpose()?,
299                },
300                upper: RangeUpperBound {
301                    inclusive: upper.inclusive,
302                    bound: upper.bound.map(&conv).transpose()?,
303                },
304            }),
305        };
306        Ok(Range { inner })
307    }
308}
309
310/// Range operations on `Range<Datum>` and `Range<DatumNested>`.
311impl<'a, B: Copy + Ord> Range<B> {
312    pub fn contains_elem<T: RangeOps<'a>>(&self, elem: &T) -> bool
313    where
314        Datum<'a>: From<B>,
315        <T as TryFrom<Datum<'a>>>::Error: std::fmt::Debug,
316    {
317        match self.inner {
318            None => false,
319            Some(inner) => inner.lower.satisfied_by(elem) && inner.upper.satisfied_by(elem),
320        }
321    }
322
323    pub fn contains_range(&self, other: &Range<B>) -> bool {
324        match (self.inner, other.inner) {
325            (None, None) | (Some(_), None) => true,
326            (None, Some(_)) => false,
327            (Some(i), Some(j)) => i.lower <= j.lower && j.upper <= i.upper,
328        }
329    }
330
331    pub fn overlaps(&self, other: &Range<B>) -> bool {
332        match (self.inner, other.inner) {
333            (Some(s), Some(o)) => {
334                let r = match s.cmp(&o) {
335                    Ordering::Equal => Ordering::Equal,
336                    Ordering::Less => s.upper.range_bound_cmp(&o.lower),
337                    Ordering::Greater => o.upper.range_bound_cmp(&s.lower),
338                };
339
340                // If smaller upper is >= larger lower, elements overlap.
341                matches!(r, Ordering::Greater | Ordering::Equal)
342            }
343            _ => false,
344        }
345    }
346
347    pub fn before(&self, other: &Range<B>) -> bool {
348        match (self.inner, other.inner) {
349            (Some(s), Some(o)) => {
350                matches!(s.upper.range_bound_cmp(&o.lower), Ordering::Less)
351            }
352            _ => false,
353        }
354    }
355
356    pub fn after(&self, other: &Range<B>) -> bool {
357        match (self.inner, other.inner) {
358            (Some(s), Some(o)) => {
359                matches!(s.lower.range_bound_cmp(&o.upper), Ordering::Greater)
360            }
361            _ => false,
362        }
363    }
364
365    pub fn overleft(&self, other: &Range<B>) -> bool {
366        match (self.inner, other.inner) {
367            (Some(s), Some(o)) => {
368                matches!(
369                    s.upper.range_bound_cmp(&o.upper),
370                    Ordering::Less | Ordering::Equal
371                )
372            }
373            _ => false,
374        }
375    }
376
377    pub fn overright(&self, other: &Range<B>) -> bool {
378        match (self.inner, other.inner) {
379            (Some(s), Some(o)) => {
380                matches!(
381                    s.lower.range_bound_cmp(&o.lower),
382                    Ordering::Greater | Ordering::Equal
383                )
384            }
385            _ => false,
386        }
387    }
388
389    pub fn adjacent(&self, other: &Range<B>) -> bool {
390        match (self.inner, other.inner) {
391            (Some(s), Some(o)) => {
392                // Look at each (lower, upper) pair.
393                for (lower, upper) in [(s.lower, o.upper), (o.lower, s.upper)] {
394                    if let (Some(l), Some(u)) = (lower.bound, upper.bound) {
395                        // If ..x](x.. or ..x)[x.., adjacent
396                        if lower.inclusive ^ upper.inclusive && l == u {
397                            return true;
398                        }
399                    }
400                }
401                false
402            }
403            _ => false,
404        }
405    }
406
407    pub fn union(&self, other: &Range<B>) -> Result<Range<B>, InvalidRangeError> {
408        // Handle self or other being empty
409        let (s, o) = match (self.inner, other.inner) {
410            (None, None) => return Ok(Range { inner: None }),
411            (inner @ Some(_), None) | (None, inner @ Some(_)) => return Ok(Range { inner }),
412            (Some(s), Some(o)) => {
413                // if not overlapping or adjacent, then result would not present continuity, so error.
414                if !(self.overlaps(other) || self.adjacent(other)) {
415                    return Err(InvalidRangeError::DiscontiguousUnion);
416                }
417                (s, o)
418            }
419        };
420
421        let lower = std::cmp::min(s.lower, o.lower);
422        let upper = std::cmp::max(s.upper, o.upper);
423
424        Ok(Range {
425            inner: Some(RangeInner { lower, upper }),
426        })
427    }
428
429    pub fn intersection(&self, other: &Range<B>) -> Range<B> {
430        // Handle self or other being empty
431        let (s, o) = match (self.inner, other.inner) {
432            (Some(s), Some(o)) => {
433                if !self.overlaps(other) {
434                    return Range { inner: None };
435                }
436
437                (s, o)
438            }
439            _ => return Range { inner: None },
440        };
441
442        let lower = std::cmp::max(s.lower, o.lower);
443        let upper = std::cmp::min(s.upper, o.upper);
444
445        Range {
446            inner: Some(RangeInner { lower, upper }),
447        }
448    }
449
450    // Function requires canonicalization so must be taken into `Range<Datum>`,
451    // which can be taken back into `Range<DatumNested>` by the caller if need
452    // be.
453    pub fn difference(&self, other: &Range<B>) -> Result<Range<Datum<'a>>, InvalidRangeError>
454    where
455        Datum<'a>: From<B>,
456    {
457        use std::cmp::Ordering::*;
458
459        // Difference op does nothing if no overlap.
460        if !self.overlaps(other) {
461            return Ok(self.into_bounds(Datum::from));
462        }
463
464        let (s, o) = match (self.inner, other.inner) {
465            (None, _) | (_, None) => unreachable!("already returned from overlap check"),
466            (Some(s), Some(o)) => (s, o),
467        };
468
469        let ll = s.lower.cmp(&o.lower);
470        let uu = s.upper.cmp(&o.upper);
471
472        let r = match (ll, uu) {
473            // `self` totally contains `other`
474            (Less, Greater) => return Err(InvalidRangeError::DiscontiguousDifference),
475            // `other` totally contains `self`
476            (Greater | Equal, Less | Equal) => Range { inner: None },
477            (Greater | Equal, Greater) => {
478                let lower = RangeBound {
479                    inclusive: !o.upper.inclusive,
480                    bound: o.upper.bound,
481                };
482                Range {
483                    inner: Some(RangeInner {
484                        lower,
485                        upper: s.upper,
486                    }),
487                }
488            }
489            (Less, Less | Equal) => {
490                let upper = RangeBound {
491                    inclusive: !o.lower.inclusive,
492                    bound: o.lower.bound,
493                };
494                Range {
495                    inner: Some(RangeInner {
496                        lower: s.lower,
497                        upper,
498                    }),
499                }
500            }
501        };
502
503        let mut r = r.into_bounds(Datum::from);
504
505        r.canonicalize()?;
506
507        Ok(r)
508    }
509}
510
511impl<'a> Range<Datum<'a>> {
512    /// Canonicalize the range by PG's heuristics, which are:
513    /// - Infinite bounds are always exclusive
514    /// - If type has step:
515    ///  - Exclusive lower bounds are rewritten as inclusive += step
516    ///  - Inclusive lower bounds are rewritten as exclusive += step
517    /// - Ranges are empty if lower >= upper after prev. step unless range type
518    ///   does not have step and both bounds are inclusive
519    ///
520    /// # Panics
521    /// - If the upper and lower bounds are finite and of different types.
522    pub fn canonicalize(&mut self) -> Result<(), InvalidRangeError> {
523        let (lower, upper) = match &mut self.inner {
524            Some(inner) => (&mut inner.lower, &mut inner.upper),
525            None => return Ok(()),
526        };
527
528        match (lower.bound, upper.bound) {
529            (Some(l), Some(u)) => {
530                assert_eq!(
531                    DatumKind::from(l),
532                    DatumKind::from(u),
533                    "finite bounds must be of same type"
534                );
535                if l > u {
536                    return Err(InvalidRangeError::MisorderedRangeBounds);
537                }
538            }
539            _ => {}
540        };
541
542        lower.canonicalize()?;
543        upper.canonicalize()?;
544
545        // The only way that you have two inclusive bounds with equal value are
546        // if type does not have step.
547        if !(lower.inclusive && upper.inclusive)
548            && lower.bound >= upper.bound
549            // None is less than any Some, so only need to check this condition.
550            && upper.bound.is_some()
551        {
552            // emtpy range
553            self.inner = None
554        }
555
556        Ok(())
557    }
558}
559
560/// Holds the upper and lower bounds for non-empty ranges.
561#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
562pub struct RangeInner<B> {
563    pub lower: RangeLowerBound<B>,
564    pub upper: RangeUpperBound<B>,
565}
566
567impl<B: Display> Display for RangeInner<B> {
568    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
569        f.write_str(if self.lower.inclusive { "[" } else { "(" })?;
570        self.lower.fmt(f)?;
571        f.write_str(",")?;
572        Display::fmt(&self.upper, f)?;
573        f.write_str(if self.upper.inclusive { "]" } else { ")" })
574    }
575}
576
577impl<B: Ord> Ord for RangeInner<B> {
578    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
579        self.lower
580            .cmp(&other.lower)
581            .then(self.upper.cmp(&other.upper))
582    }
583}
584
585impl<B: PartialOrd + Ord> PartialOrd for RangeInner<B> {
586    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
587        Some(self.cmp(other))
588    }
589}
590
591/// Represents a terminal point of a range.
592#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
593pub struct RangeBound<B, const UPPER: bool = false> {
594    pub inclusive: bool,
595    /// None value represents an infinite bound.
596    pub bound: Option<B>,
597}
598
599impl<const UPPER: bool, D: Display> Display for RangeBound<D, UPPER> {
600    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
601        match &self.bound {
602            None => Ok(()),
603            Some(bound) => bound.fmt(f),
604        }
605    }
606}
607
608impl<const UPPER: bool, D: Ord> Ord for RangeBound<D, UPPER> {
609    fn cmp(&self, other: &Self) -> Ordering {
610        // 1. Sort by bounds
611        let mut cmp = self.bound.cmp(&other.bound);
612        // 2. Infinite bounds vs. finite bounds are reversed for uppers.
613        if UPPER && other.bound.is_none() ^ self.bound.is_none() {
614            cmp = cmp.reverse();
615        }
616        // 3. Tie break by sorting by inclusivity, which is inverted between
617        //    lowers and uppers.
618        cmp.then(if self.inclusive == other.inclusive {
619            Ordering::Equal
620        } else if self.inclusive {
621            if UPPER {
622                Ordering::Greater
623            } else {
624                Ordering::Less
625            }
626        } else if UPPER {
627            Ordering::Less
628        } else {
629            Ordering::Greater
630        })
631    }
632}
633
634impl<const UPPER: bool, D: PartialOrd + Ord> PartialOrd for RangeBound<D, UPPER> {
635    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
636        Some(self.cmp(other))
637    }
638}
639
640/// A `RangeBound` that sorts correctly for use as a lower bound.
641pub type RangeLowerBound<B> = RangeBound<B, false>;
642
643/// A `RangeBound` that sorts correctly for use as an upper bound.
644pub type RangeUpperBound<B> = RangeBound<B, true>;
645
646// Generic RangeBound implementations meant to work over `RangeBound<Datum,..>`
647// and `RangeBound<DatumNested,..>`.
648impl<'a, const UPPER: bool, B: Copy + Ord> RangeBound<B, UPPER> {
649    /// Determines where `elem` lies in relation to the range bound.
650    ///
651    /// # Panics
652    /// - If `self.bound.datum()` is not convertible to `T`.
653    fn elem_cmp<T: RangeOps<'a>>(&self, elem: &T) -> Ordering
654    where
655        Datum<'a>: From<B>,
656        <T as TryFrom<Datum<'a>>>::Error: std::fmt::Debug,
657    {
658        match self.bound.map(|bound| <T>::unwrap_datum(bound.into())) {
659            None if UPPER => Ordering::Greater,
660            None => Ordering::Less,
661            Some(bound) => bound.cmp(elem),
662        }
663    }
664
665    /// Does `elem` satisfy this bound?
666    fn satisfied_by<T: RangeOps<'a>>(&self, elem: &T) -> bool
667    where
668        Datum<'a>: From<B>,
669        <T as TryFrom<Datum<'a>>>::Error: std::fmt::Debug,
670    {
671        match self.elem_cmp(elem) {
672            // Inclusive always satisfied with equality, regardless of upper or
673            // lower.
674            Ordering::Equal => self.inclusive,
675            // Upper satisfied with values less than itself
676            Ordering::Greater => UPPER,
677            // Lower satisfied with values greater than itself
678            Ordering::Less => !UPPER,
679        }
680    }
681
682    // Compares two `RangeBound`, which do not need to both be of the same
683    // `UPPER`.
684    fn range_bound_cmp<const OTHER_UPPER: bool>(
685        &self,
686        other: &RangeBound<B, OTHER_UPPER>,
687    ) -> Ordering {
688        if UPPER == OTHER_UPPER {
689            return self.cmp(&RangeBound {
690                inclusive: other.inclusive,
691                bound: other.bound,
692            });
693        }
694
695        // Handle cases where either are infinite bounds, which have special
696        // semantics.
697        if self.bound.is_none() || other.bound.is_none() {
698            return if UPPER {
699                Ordering::Greater
700            } else {
701                Ordering::Less
702            };
703        }
704        // 1. Sort by bounds
705        let cmp = self.bound.cmp(&other.bound);
706        // 2. Tie break by sorting by inclusivity, which is inverted between
707        //    lowers and uppers.
708        cmp.then(if self.inclusive && other.inclusive {
709            Ordering::Equal
710        } else if UPPER {
711            Ordering::Less
712        } else {
713            Ordering::Greater
714        })
715    }
716}
717
718impl<'a, const UPPER: bool> RangeBound<Datum<'a>, UPPER> {
719    /// Create a new `RangeBound` whose value is "infinite" (i.e. None) if `d ==
720    /// Datum::Null`, otherwise finite (i.e. Some).
721    ///
722    /// There is not a corresponding generic implementation of this because
723    /// genericizing how to express infinite bounds is less clear.
724    pub fn new(d: Datum<'a>, inclusive: bool) -> RangeBound<Datum<'a>, UPPER> {
725        RangeBound {
726            inclusive,
727            bound: match d {
728                Datum::Null => None,
729                o => Some(o),
730            },
731        }
732    }
733
734    /// Rewrite the bounds to the consistent format. This is absolutely
735    /// necessary to perform the correct equality/comparison operations on
736    /// types.
737    fn canonicalize(&mut self) -> Result<(), InvalidRangeError> {
738        Ok(match self.bound {
739            None => {
740                self.inclusive = false;
741            }
742            // Valid range types are defined in typeconv.rs:validate_range_element_type
743            Some(value) => match value {
744                d @ Datum::Int32(_) => self.canonicalize_inner::<i32>(d)?,
745                d @ Datum::Int64(_) => self.canonicalize_inner::<i64>(d)?,
746                d @ Datum::Date(_) => self.canonicalize_inner::<Date>(d)?,
747                Datum::Numeric(..) | Datum::Timestamp(..) | Datum::TimestampTz(..) => {}
748                d => unreachable!("{d:?} not yet supported in ranges"),
749            },
750        })
751    }
752
753    /// Canonicalize `self`'s representation for types that have discrete steps
754    /// between values.
755    ///
756    /// Continuous values (e.g. timestamps, numeric) must not be
757    /// canonicalized.
758    fn canonicalize_inner<T: RangeOps<'a>>(&mut self, d: Datum<'a>) -> Result<(), InvalidRangeError>
759    where
760        <T as TryFrom<Datum<'a>>>::Error: std::fmt::Debug,
761    {
762        // Upper bounds must be exclusive, lower bounds inclusive
763        if UPPER == self.inclusive {
764            let cur = <T>::unwrap_datum(d);
765            self.bound = Some(
766                cur.step()
767                    .ok_or_else(|| {
768                        InvalidRangeError::CanonicalizationOverflow(T::err_type_name().into())
769                    })?
770                    .into(),
771            );
772            self.inclusive = !UPPER;
773        }
774
775        Ok(())
776    }
777}
778
779#[derive(
780    Ord,
781    PartialOrd,
782    Clone,
783    Debug,
784    Eq,
785    PartialEq,
786    Serialize,
787    Deserialize,
788    Hash,
789    MzReflect
790)]
791#[cfg_attr(any(test, feature = "proptest"), derive(Arbitrary))]
792pub enum InvalidRangeError {
793    MisorderedRangeBounds,
794    CanonicalizationOverflow(Box<str>),
795    InvalidRangeBoundFlags,
796    DiscontiguousUnion,
797    DiscontiguousDifference,
798    NullRangeBoundFlags,
799}
800
801impl Display for InvalidRangeError {
802    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
803        match self {
804            InvalidRangeError::MisorderedRangeBounds => {
805                f.write_str("range lower bound must be less than or equal to range upper bound")
806            }
807            InvalidRangeError::CanonicalizationOverflow(t) => {
808                write!(f, "{} out of range", t)
809            }
810            InvalidRangeError::InvalidRangeBoundFlags => f.write_str("invalid range bound flags"),
811            InvalidRangeError::DiscontiguousUnion => {
812                f.write_str("result of range union would not be contiguous")
813            }
814            InvalidRangeError::DiscontiguousDifference => {
815                f.write_str("result of range difference would not be contiguous")
816            }
817            InvalidRangeError::NullRangeBoundFlags => {
818                f.write_str("range constructor flags argument must not be null")
819            }
820        }
821    }
822}
823
824impl Error for InvalidRangeError {
825    fn source(&self) -> Option<&(dyn Error + 'static)> {
826        None
827    }
828}
829
830// Required due to Proto decoding using string as its error type
831impl From<InvalidRangeError> for String {
832    fn from(e: InvalidRangeError) -> Self {
833        e.to_string()
834    }
835}
836
837impl RustType<ProtoInvalidRangeError> for InvalidRangeError {
838    fn into_proto(&self) -> ProtoInvalidRangeError {
839        use Kind::*;
840        use proto_invalid_range_error::*;
841        let kind = match self {
842            InvalidRangeError::MisorderedRangeBounds => MisorderedRangeBounds(()),
843            InvalidRangeError::CanonicalizationOverflow(s) => {
844                CanonicalizationOverflow(s.into_proto())
845            }
846            InvalidRangeError::InvalidRangeBoundFlags => InvalidRangeBoundFlags(()),
847            InvalidRangeError::DiscontiguousUnion => DiscontiguousUnion(()),
848            InvalidRangeError::DiscontiguousDifference => DiscontiguousDifference(()),
849            InvalidRangeError::NullRangeBoundFlags => NullRangeBoundFlags(()),
850        };
851        ProtoInvalidRangeError { kind: Some(kind) }
852    }
853
854    fn from_proto(proto: ProtoInvalidRangeError) -> Result<Self, TryFromProtoError> {
855        use proto_invalid_range_error::Kind::*;
856        match proto.kind {
857            Some(kind) => Ok(match kind {
858                MisorderedRangeBounds(()) => InvalidRangeError::MisorderedRangeBounds,
859                CanonicalizationOverflow(s) => {
860                    InvalidRangeError::CanonicalizationOverflow(s.into())
861                }
862                InvalidRangeBoundFlags(()) => InvalidRangeError::InvalidRangeBoundFlags,
863                DiscontiguousUnion(()) => InvalidRangeError::DiscontiguousUnion,
864                DiscontiguousDifference(()) => InvalidRangeError::DiscontiguousDifference,
865                NullRangeBoundFlags(()) => InvalidRangeError::NullRangeBoundFlags,
866            }),
867            None => Err(TryFromProtoError::missing_field(
868                "`ProtoInvalidRangeError::kind`",
869            )),
870        }
871    }
872}
873
874pub fn parse_range_bound_flags<'a>(flags: &'a str) -> Result<(bool, bool), InvalidRangeError> {
875    let mut flags = flags.chars();
876
877    let lower = match flags.next() {
878        Some('(') => false,
879        Some('[') => true,
880        _ => return Err(InvalidRangeError::InvalidRangeBoundFlags),
881    };
882
883    let upper = match flags.next() {
884        Some(')') => false,
885        Some(']') => true,
886        _ => return Err(InvalidRangeError::InvalidRangeBoundFlags),
887    };
888
889    match flags.next() {
890        Some(_) => Err(InvalidRangeError::InvalidRangeBoundFlags),
891        None => Ok((lower, upper)),
892    }
893}
894
895impl<'a, T: FromSql<'a>> FromSql<'a> for Range<T> {
896    fn from_sql(ty: &PgType, raw: &'a [u8]) -> Result<Range<T>, Box<dyn Error + Sync + Send>> {
897        let inner_typ = match ty {
898            &PgType::INT4_RANGE => PgType::INT4,
899            &PgType::INT8_RANGE => PgType::INT8,
900            &PgType::DATE_RANGE => PgType::DATE,
901            &PgType::NUM_RANGE => PgType::NUMERIC,
902            &PgType::TS_RANGE => PgType::TIMESTAMP,
903            &PgType::TSTZ_RANGE => PgType::TIMESTAMPTZ,
904            _ => unreachable!(),
905        };
906
907        let inner = match types::range_from_sql(raw)? {
908            types::Range::Empty => None,
909            types::Range::Nonempty(lower, upper) => {
910                let mut bounds = Vec::with_capacity(2);
911
912                for bound_outer in [lower, upper].into_iter() {
913                    let bound = match bound_outer {
914                        types::RangeBound::Exclusive(bound)
915                        | types::RangeBound::Inclusive(bound) => bound
916                            .map(|bound| T::from_sql(&inner_typ, bound))
917                            .transpose()?,
918                        types::RangeBound::Unbounded => None,
919                    };
920                    let inclusive = matches!(bound_outer, types::RangeBound::Inclusive(_));
921                    bounds.push(RangeBound { bound, inclusive });
922                }
923
924                let lower = bounds.remove(0);
925                let upper = bounds.remove(0);
926                assert!(bounds.is_empty());
927
928                Some(RangeInner {
929                    lower,
930                    // Rewrite bound in terms of appropriate `UPPER`
931                    upper: RangeBound {
932                        bound: upper.bound,
933                        inclusive: upper.inclusive,
934                    },
935                })
936            }
937        };
938
939        Ok(Range { inner })
940    }
941
942    fn accepts(ty: &PgType) -> bool {
943        matches!(
944            ty,
945            &PgType::INT4_RANGE
946                | &PgType::INT8_RANGE
947                | &PgType::DATE_RANGE
948                | &PgType::NUM_RANGE
949                | &PgType::TS_RANGE
950                | &PgType::TSTZ_RANGE
951        )
952    }
953}
mz_repr/adt/range.rs

mz_repr/adt/
range.rs
