ion_schema/isl/
ranges.rs

1// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
2// SPDX-License-Identifier: Apache-2.0
3
4//! Range types used in Ion Schema.
5//!
6//! ### Why so many range types?
7//! - [`UsizeRange`] is used for `*_length` constraints and `occurs`
8//! - [`U64Range`] is used for the `precision` constraint because [`Decimal`] precision is measured using `u64`.
9//! - [`I64Range`] is used for `exponent` and `scale` constraints
10//! - [`TimestampPrecisionRange`] is used for `timestamp_precision` constraint
11//! - [`NumberRange`] and [`TimestampRange`] are used for valid_values constraint
12
13// It would be ideal to use [`NonZeroU64`][std::num::NonZeroU64] for the `precision` constraint, but
14// `NonZeroU64` is difficult to work with because it doesn't implement core ops (such as `Add`) and
15// as a result, it cannot even implement the checked ops traits (such as `CheckedAdd`) from the
16// `num_traits` crate. See https://github.com/rust-num/num-traits/issues/274.
17
18use crate::isl::ranges::base::RangeValidation;
19use crate::isl::util::TimestampPrecision;
20use crate::IonSchemaResult;
21use crate::{invalid_schema_error, invalid_schema_error_raw, isl_require};
22use ion_rs::Decimal;
23use ion_rs::{Element, IonResult, ValueWriter, WriteAsIon};
24use ion_rs::{IonType, Timestamp};
25use num_traits::{CheckedAdd, One};
26use std::cmp::Ordering;
27use std::fmt::{Display, Formatter};
28
29/// An end (upper or lower) of a [`Range`].
30#[derive(Debug, PartialEq, Clone)]
31pub enum Limit<T> {
32    /// Indicates that the end of a range has no limit or appears to have no limit.
33    /// For example, when `NumberRange::lower() == Unbounded`, there is no actual limit to the lower
34    /// end of the range—it is effectively negative infinity. On the other hand, for a finite type
35    /// such as `i64`, when `I64Range::upper() == Unbounded`, it appears that there is no limit to
36    /// the upper end of the range because then the upper limit of the range is effectively the
37    /// maximum value that can be represented by `i64`.
38    ///
39    /// `Unbounded` is represented in Ion Schema Language as `min` or `max`, depending on the
40    /// position in which it occurs.
41    Min,
42    Max,
43    /// Indicates that the end of the range includes the given value.
44    Inclusive(T),
45    /// Indicates that the end of the range excludes the given value.
46    Exclusive(T),
47}
48
49impl<T: PartialOrd> PartialEq<T> for Limit<T> {
50    fn eq(&self, other: &T) -> bool {
51        match self {
52            Limit::Inclusive(x) => x == other,
53            _ => false,
54        }
55    }
56}
57
58impl<T: PartialOrd> PartialOrd<T> for Limit<T> {
59    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
60        match self {
61            Limit::Min => Some(Ordering::Less),
62            Limit::Max => Some(Ordering::Greater),
63            Limit::Inclusive(x) => x.partial_cmp(other),
64            Limit::Exclusive(x) => {
65                // Exclusive limits can never be equal—only lesser or greater
66                match x.partial_cmp(other) {
67                    Some(Ordering::Equal) => None,
68                    order => order,
69                }
70            }
71        }
72    }
73}
74
75impl<T: Display> Display for Limit<T> {
76    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
77        match self {
78            Limit::Min => "min".fmt(f),
79            Limit::Max => "max".fmt(f),
80            Limit::Inclusive(value) => value.fmt(f),
81            Limit::Exclusive(value) => write!(f, "exclusive::{value}"),
82        }
83    }
84}
85
86impl<T: WriteAsIon> WriteAsIon for Limit<T> {
87    fn write_as_ion<V: ValueWriter>(&self, writer: V) -> IonResult<()> {
88        match self {
89            Limit::Min => writer.write_symbol("min"),
90            Limit::Max => writer.write_symbol("max"),
91            Limit::Inclusive(t) => writer.write(t),
92            Limit::Exclusive(t) => writer.with_annotations(["exclusive"])?.write(t),
93        }
94    }
95}
96
97pub type UsizeRange = base::Range<usize>;
98impl RangeValidation<usize> for UsizeRange {
99    fn is_empty(start: &Limit<usize>, end: &Limit<usize>) -> bool {
100        base::is_int_range_empty(start, end)
101    }
102}
103impl UsizeRange {
104    /// Constructs a degenerate range that only contains 1.
105    pub fn one() -> Self {
106        Self::new_single_value(1)
107    }
108
109    /// Constructs an inclusive range from 0 to 1.
110    pub fn zero_or_one() -> Self {
111        Self::new_inclusive(0, 1).expect("This is safe to unwrap because 0 <= 1")
112    }
113
114    pub fn inclusive_endpoints(&self) -> (usize, usize) {
115        // There is no danger of under/overflow because of the range is known to be non-empty, which
116        // implies that the lower limit cannot be Exclusive(usize::MAX) and the upper limit cannot
117        // be Exclusive(0)
118        let lower = match self.lower() {
119            Limit::Min => 0,
120            Limit::Inclusive(x) => *x,
121            Limit::Exclusive(x) => x + 1,
122            Limit::Max => unreachable!(),
123        };
124        let upper = match self.upper() {
125            Limit::Max => usize::MAX,
126            Limit::Inclusive(x) => *x,
127            Limit::Exclusive(x) => x - 1,
128            Limit::Min => unreachable!(),
129        };
130        (lower, upper)
131    }
132}
133
134pub type U64Range = base::Range<u64>;
135impl RangeValidation<u64> for U64Range {
136    fn is_empty(start: &Limit<u64>, end: &Limit<u64>) -> bool {
137        base::is_int_range_empty(start, end)
138    }
139}
140
141pub type I64Range = base::Range<i64>;
142impl RangeValidation<i64> for I64Range {
143    fn is_empty(start: &Limit<i64>, end: &Limit<i64>) -> bool {
144        base::is_int_range_empty(start, end)
145    }
146}
147
148pub type NumberRange = base::Range<Decimal>;
149impl RangeValidation<Decimal> for NumberRange {}
150
151pub type TimestampRange = base::Range<Timestamp>;
152impl RangeValidation<Timestamp> for TimestampRange {}
153
154pub type TimestampPrecisionRange = base::Range<TimestampPrecision>;
155impl RangeValidation<TimestampPrecision> for TimestampPrecisionRange {
156    fn is_empty(start: &Limit<TimestampPrecision>, end: &Limit<TimestampPrecision>) -> bool {
157        match (start, end) {
158            (Limit::Inclusive(lower), Limit::Inclusive(upper)) => lower > upper,
159            (Limit::Exclusive(lower), Limit::Inclusive(upper))
160            | (Limit::Inclusive(lower), Limit::Exclusive(upper)) => lower >= upper,
161            (Limit::Exclusive(lower), Limit::Exclusive(upper)) => {
162                let start_value = lower.int_value();
163                let end_value = upper.int_value();
164
165                // Checking for e.g. range::[exclusive::1, exclusive::2] which is empty.
166                // Integer overflow is not possible here because TimestampPrecision range boundaries
167                // have an i64 range of `-4 ..= 9`.
168                let adjusted_lower = start_value + 1;
169                adjusted_lower >= end_value
170            }
171            _ => false,
172        }
173    }
174}
175
176/// This module contains the generic base for all of the "real" range types that we expose.
177mod base {
178    use super::*;
179
180    /// Trait to allow type-specific implementations to inject type-specific logic into the
181    /// constructor for [`Range`].
182    pub trait RangeValidation<T: PartialOrd> {
183        /// Checks if two limits would result in an empty range.
184        fn is_empty(start: &Limit<T>, end: &Limit<T>) -> bool {
185            match (start, end) {
186                (Limit::Inclusive(lower), Limit::Inclusive(upper)) => lower > upper,
187                (Limit::Exclusive(lower), Limit::Exclusive(upper))
188                | (Limit::Exclusive(lower), Limit::Inclusive(upper))
189                | (Limit::Inclusive(lower), Limit::Exclusive(upper)) => lower >= upper,
190                _ => false,
191            }
192        }
193    }
194
195    /// Checks if two limits would result in an empty range of integers. Returns true if there are
196    /// no integer values between `start` and `end`, taking into consideration the exclusivity of
197    /// the limits.
198    pub fn is_int_range_empty<T: CheckedAdd + One + PartialOrd>(
199        start: &Limit<T>,
200        end: &Limit<T>,
201    ) -> bool {
202        match (start, end) {
203            (Limit::Inclusive(lower), Limit::Inclusive(upper)) => lower > upper,
204            (Limit::Exclusive(lower), Limit::Inclusive(upper))
205            | (Limit::Inclusive(lower), Limit::Exclusive(upper)) => lower >= upper,
206            (Limit::Exclusive(lower), Limit::Exclusive(upper)) => {
207                // Checking for e.g. range::[exclusive::1, exclusive::2] which is empty.
208                let adjusted_lower = lower.checked_add(&T::one());
209                // If the _lower_ bound wraps around when we add one, then we know it's empty.
210                if adjusted_lower.is_none() {
211                    return true;
212                }
213                adjusted_lower.unwrap() >= *upper
214            }
215            _ => false,
216        }
217    }
218
219    /// Represents an interval of values where the upper and lower ends can be open, closed, or unbounded.
220    ///
221    /// At least one of the ends must be [`Limit::Exclusive`] or [`Limit::Inclusive`]. A `Range` may not be
222    /// empty (i.e. there must be at least one value for which [`contains`] returns `true`).
223    #[derive(Debug, Clone, PartialEq)]
224    pub struct Range<T> {
225        lower: Limit<T>,
226        upper: Limit<T>,
227    }
228
229    // Note the trait bound! This allows us to inject a different non-empty check depending on the
230    // realized type of `T`.
231    impl<T: PartialOrd + Clone> Range<T>
232    where
233        Self: RangeValidation<T>,
234    {
235        /// Creates a new range.
236        /// At least one limit must be bounded, and the range must be non-empty.
237        pub fn new(start: Limit<T>, end: Limit<T>) -> IonSchemaResult<Self> {
238            isl_require!(start != Limit::Min || end != Limit::Max  => "range may not contain both 'min' and 'max'")?;
239            isl_require!(start != Limit::Max => "range may not be empty (start of range may not be 'max')")?;
240            isl_require!(end != Limit::Min => "range may not be empty (end of range cannot be 'min')")?;
241            isl_require!(!Self::is_empty(&start, &end) => "range may not be empty")?;
242            Ok(Self {
243                lower: start,
244                upper: end,
245            })
246        }
247
248        /// Creates a new range with inclusive endpoints.
249        /// [start] must be less than or equal to [end].
250        pub fn new_inclusive(start: T, end: T) -> IonSchemaResult<Self> {
251            Self::new(Limit::Inclusive(start), Limit::Inclusive(end))
252        }
253
254        /// Creates a new range containing exactly one value.
255        pub fn new_single_value(value: T) -> Self {
256            // This is safe to unwrap because we know both limits will be Closed and start == end.
257            Self::new_inclusive(value.clone(), value).unwrap()
258        }
259
260        pub fn lower(&self) -> &Limit<T> {
261            &self.lower
262        }
263
264        pub fn upper(&self) -> &Limit<T> {
265            &self.upper
266        }
267
268        /// Checks whether the given value is contained within this range.
269        pub fn contains<V: Into<T> + Clone>(&self, value: &V) -> bool {
270            let other = value.clone().into();
271            self.lower <= other && self.upper >= other
272        }
273
274        /// Reads a [`Range`] from an [`Element`] of Ion Schema Language.
275        pub fn from_ion_element<F: Fn(&Element) -> Option<T>>(
276            element: &Element,
277            value_fn: F,
278        ) -> IonSchemaResult<Range<T>> {
279            if element.annotations().contains("range") {
280                isl_require!(element.ion_type() == IonType::List => "range must be a non-null list; found: {element}")?;
281                isl_require!(!element.is_null() => "range must be a non-null list; found: {element}")?;
282                let seq = element.as_sequence().unwrap();
283                isl_require!(seq.len() == 2 => "range must have a lower and upper bound; found: {element}")?;
284
285                let lower_limit = Self::read_range_bound(element, seq.get(0).unwrap(), &value_fn)?;
286                let upper_limit = Self::read_range_bound(element, seq.get(1).unwrap(), &value_fn)?;
287
288                Self::new(lower_limit, upper_limit)
289            } else {
290                let value = value_fn(element);
291                if let Some(value) = value {
292                    Ok(Self::new_single_value(value))
293                } else {
294                    invalid_schema_error(format!("invalid value for range: {element}"))
295                }
296            }
297        }
298
299        fn read_range_bound<F: Fn(&Element) -> Option<T>>(
300            element: &Element,
301            boundary_element: &Element,
302            value_fn: F,
303        ) -> IonSchemaResult<Limit<T>> {
304            let is_exclusive = boundary_element.annotations().contains("exclusive");
305            isl_require!(boundary_element.annotations().len() == if is_exclusive {1} else {0} => "invalid annotation(s) on range boundary {element}")?;
306
307            match boundary_element.as_symbol().map(|s| s.text()) {
308                Some(Some("min")) => {
309                    isl_require!(!is_exclusive => "'min' may not be exclusive")?;
310                    Ok(Limit::Min)
311                }
312                Some(Some("max")) => {
313                    isl_require!(!is_exclusive => "'max' may not be exclusive")?;
314                    Ok(Limit::Max)
315                }
316                _ => {
317                    let limit_value: T = value_fn(boundary_element).ok_or_else(|| {
318                        invalid_schema_error_raw(format!(
319                            "invalid value for range boundary: {element}"
320                        ))
321                    })?;
322                    if is_exclusive {
323                        Ok(Limit::Exclusive(limit_value))
324                    } else {
325                        Ok(Limit::Inclusive(limit_value))
326                    }
327                }
328            }
329        }
330    }
331
332    impl<T: Clone + PartialEq + PartialOrd> From<T> for Range<T>
333    where
334        Self: RangeValidation<T>,
335    {
336        fn from(value: T) -> Self {
337            Range::new_single_value(value)
338        }
339    }
340
341    impl<T: PartialEq + Display> Display for Range<T> {
342        fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
343            match &self.lower {
344                Limit::Inclusive(value) if self.lower == self.upper => value.fmt(f),
345                _ => f.write_fmt(format_args!("range::[{},{}]", self.lower, self.upper)),
346            }
347        }
348    }
349
350    impl<T: WriteAsIon + PartialEq> WriteAsIon for Range<T> {
351        fn write_as_ion<V: ValueWriter>(&self, writer: V) -> IonResult<()> {
352            match &self.lower {
353                Limit::Inclusive(value) if self.lower == self.upper => writer.write(value),
354                _ => writer
355                    .with_annotations(["range"])?
356                    .write([&self.lower, &self.upper]),
357            }
358        }
359    }
360}
361
362#[cfg(test)]
363mod tests {
364    //! These test are for the generic functionality of Range.
365    //! More specific test cases are handled as part of ion-schema-tests.
366
367    use crate::isl::ranges::base::Range;
368    use crate::isl::ranges::{I64Range, Limit};
369    use crate::IonSchemaResult;
370    use ion_rs::Element;
371    use rstest::*;
372
373    #[rstest(
374        case::range_with_min_max("range::[min, max]"),
375        case::range_with_max_lower_bound("range::[max, 5]"),
376        case::range_with_min_upper_bound("range::[5, min]"),
377        case::range_with_lower_bound_greater_than_upper_bound("range::[10, 5]"),
378        case::empty_range_with_exclusive_lower_bound("range::[exclusive::5, 5]"),
379        case::empty_range_with_exclusive_upper_bound("range::[5, exclusive::5]"),
380        case::empty_range_with_mutually_excluding_bounds("range::[exclusive::5, exclusive::5]"),
381        case::range_with_unknown_annotation("range::[0, foo::5]"),
382        case::range_without_range_annotation("[5, 10]")
383    )]
384    fn invalid_ranges_from_isl(#[case] range_ion: &str) {
385        let range =
386            I64Range::from_ion_element(&Element::read_one(range_ion).unwrap(), Element::as_i64);
387        assert!(range.is_err());
388    }
389
390    #[rstest(
391        case::range_with_both_limits_unbounded(Range::new(Limit::Min, Limit::Max)),
392        case::range_with_lower_bound_greater_than_upper_bound(Range::new(
393            Limit::Inclusive(3),
394            Limit::Inclusive(1)
395        )),
396        case::range_with_lower_bound_greater_than_upper_bound(Range::new_inclusive(3, 1)),
397        case::empty_range_with_exclusive_lower_bound(Range::new(
398            Limit::Exclusive(3),
399            Limit::Inclusive(3)
400        )),
401        case::empty_range_with_exclusive_upper_bound(Range::new(
402            Limit::Inclusive(3),
403            Limit::Exclusive(3)
404        ))
405    )]
406    fn invalid_ranges_from_constructor(#[case] range_result: IonSchemaResult<Range<i64>>) {
407        assert!(range_result.is_err());
408    }
409
410    #[rstest(
411        case::lower_is_unbounded(
412            Range::new(Limit::Min, Limit::Inclusive(5)),
413            vec![-128, 0, 5],
414            vec![6, 127],
415        ),
416        case::upper_is_unbounded(
417            Range::new(Limit::Inclusive(5), Limit::Max),
418            vec![5, 6, 127],
419            vec![-128, 0, 4],
420        ),
421        case::lower_bound_is_exclusive(
422            Range::new(Limit::Exclusive(5), Limit::Inclusive(10)),
423            vec![6, 9, 10],
424            vec![0, 5, 11],
425        ),
426        case::upper_bound_is_exclusive(
427            Range::new(Limit::Inclusive(5), Limit::Exclusive(10)),
428            vec![5, 6, 9],
429            vec![0, 4, 10],
430        )
431    )]
432    fn range_contains(
433        #[case] range: IonSchemaResult<Range<i64>>,
434        #[case] valid_values: Vec<i64>,
435        #[case] invalid_values: Vec<i64>,
436    ) {
437        let range = range.unwrap();
438        for valid_value in valid_values {
439            let range_contains_result = range.contains(&valid_value);
440            assert!(
441                range_contains_result,
442                "Value {valid_value} was not in {range}"
443            )
444        }
445        for invalid_value in invalid_values {
446            let range_contains_result = range.contains(&invalid_value);
447            assert!(
448                !range_contains_result,
449                "Value {invalid_value} was unexpectedly in {range}"
450            )
451        }
452    }
453
454    #[rstest(
455        case::a_very_simple_case("range::[0,1]", Range::new(Limit::Inclusive(0), Limit::Inclusive(1)).unwrap()),
456        case::lower_is_unbounded("range::[min,1]", Range::new(Limit::Min, Limit::Inclusive(1)).unwrap()),
457        case::upper_is_unbounded("range::[1,max]", Range::new(Limit::Inclusive(1), Limit::Max).unwrap()),
458        case::lower_equals_upper("1", Range::new_single_value(1)),
459        case::lower_is_exclusive("range::[exclusive::0,2]", Range::new(Limit::Exclusive(0), Limit::Inclusive(2)).unwrap()),
460        case::upper_is_exclusive("range::[0,exclusive::2]", Range::new(Limit::Inclusive(0), Limit::Exclusive(2)).unwrap()),
461        // In some cases, the range can be elided to a number
462        case::upper_is_exclusive("1", Range::new(Limit::Inclusive(1), Limit::Inclusive(1)).unwrap()),
463    )]
464    fn range_display(#[case] expected: &str, #[case] range: Range<i64>) {
465        assert_eq!(expected, format!("{range}"));
466    }
467}
ion_schema/isl/ranges.rs

ion_schema/isl/
ranges.rs
