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                let adjusted_lower = start_value + 1;
167                adjusted_lower >= end_value
168            }
169            _ => false,
170        }
171    }
172}
173
174/// This module contains the generic base for all of the "real" range types that we expose.
175mod base {
176    use super::*;
177
178    /// Trait to allow type-specific implementations to inject type-specific logic into the
179    /// constructor for [`Range`].
180    pub trait RangeValidation<T: PartialOrd> {
181        /// Checks if two limits would result in an empty range.
182        fn is_empty(start: &Limit<T>, end: &Limit<T>) -> bool {
183            match (start, end) {
184                (Limit::Inclusive(lower), Limit::Inclusive(upper)) => lower > upper,
185                (Limit::Exclusive(lower), Limit::Exclusive(upper))
186                | (Limit::Exclusive(lower), Limit::Inclusive(upper))
187                | (Limit::Inclusive(lower), Limit::Exclusive(upper)) => lower >= upper,
188                _ => false,
189            }
190        }
191    }
192
193    /// Checks if two limits would result in an empty range of integers. Returns true if there are
194    /// no integer values between `start` and `end`, taking into consideration the exclusivity of
195    /// the limits.
196    pub fn is_int_range_empty<T: CheckedAdd + One + PartialOrd>(
197        start: &Limit<T>,
198        end: &Limit<T>,
199    ) -> bool {
200        match (start, end) {
201            (Limit::Inclusive(lower), Limit::Inclusive(upper)) => lower > upper,
202            (Limit::Exclusive(lower), Limit::Inclusive(upper))
203            | (Limit::Inclusive(lower), Limit::Exclusive(upper)) => lower >= upper,
204            (Limit::Exclusive(lower), Limit::Exclusive(upper)) => {
205                // Checking for e.g. range::[exclusive::1, exclusive::2] which is empty.
206                let adjusted_lower = lower.checked_add(&T::one());
207                // If the _lower_ bound wraps around when we add one, then we know it's empty.
208                if adjusted_lower.is_none() {
209                    return true;
210                }
211                adjusted_lower.unwrap() >= *upper
212            }
213            _ => false,
214        }
215    }
216
217    /// Represents an interval of values where the upper and lower ends can be open, closed, or unbounded.
218    ///
219    /// At least one of the ends must be [`Limit::Exclusive`] or [`Limit::Inclusive`]. A `Range` may not be
220    /// empty (i.e. there must be at least one value for which [`contains`] returns `true`).
221    #[derive(Debug, Clone, PartialEq)]
222    pub struct Range<T> {
223        lower: Limit<T>,
224        upper: Limit<T>,
225    }
226
227    // Note the trait bound! This allows us to inject a different non-empty check depending on the
228    // realized type of `T`.
229    impl<T: PartialOrd + Clone> Range<T>
230    where
231        Self: RangeValidation<T>,
232    {
233        /// Creates a new range.
234        /// At least one limit must be bounded, and the range must be non-empty.
235        pub fn new(start: Limit<T>, end: Limit<T>) -> IonSchemaResult<Self> {
236            isl_require!(start != Limit::Min || end != Limit::Max  => "range may not contain both 'min' and 'max'")?;
237            isl_require!(start != Limit::Max => "range may not be empty (start of range may not be 'max')")?;
238            isl_require!(end != Limit::Min => "range may not be empty (end of range cannot be 'min')")?;
239            isl_require!(!Self::is_empty(&start, &end) => "range may not be empty")?;
240            Ok(Self {
241                lower: start,
242                upper: end,
243            })
244        }
245
246        /// Creates a new range with inclusive endpoints.
247        /// [start] must be less than or equal to [end].
248        pub fn new_inclusive(start: T, end: T) -> IonSchemaResult<Self> {
249            Self::new(Limit::Inclusive(start), Limit::Inclusive(end))
250        }
251
252        /// Creates a new range containing exactly one value.
253        pub fn new_single_value(value: T) -> Self {
254            // This is safe to unwrap because we know both limits will be Closed and start == end.
255            Self::new_inclusive(value.clone(), value).unwrap()
256        }
257
258        pub fn lower(&self) -> &Limit<T> {
259            &self.lower
260        }
261
262        pub fn upper(&self) -> &Limit<T> {
263            &self.upper
264        }
265
266        /// Checks whether the given value is contained within this range.
267        pub fn contains<V: Into<T> + Clone>(&self, value: &V) -> bool {
268            let other = value.clone().into();
269            self.lower <= other && self.upper >= other
270        }
271
272        /// Reads a [`Range`] from an [`Element`] of Ion Schema Language.
273        pub fn from_ion_element<F: Fn(&Element) -> Option<T>>(
274            element: &Element,
275            value_fn: F,
276        ) -> IonSchemaResult<Range<T>> {
277            if element.annotations().contains("range") {
278                isl_require!(element.ion_type() == IonType::List => "range must be a non-null list; found: {element}")?;
279                isl_require!(!element.is_null() => "range must be a non-null list; found: {element}")?;
280                let seq = element.as_sequence().unwrap();
281                isl_require!(seq.len() == 2 => "range must have a lower and upper bound; found: {element}")?;
282
283                let lower_limit = Self::read_range_bound(element, seq.get(0).unwrap(), &value_fn)?;
284                let upper_limit = Self::read_range_bound(element, seq.get(1).unwrap(), &value_fn)?;
285
286                Self::new(lower_limit, upper_limit)
287            } else {
288                let value = value_fn(element);
289                if let Some(value) = value {
290                    Ok(Self::new_single_value(value))
291                } else {
292                    invalid_schema_error(format!("invalid value for range: {element}"))
293                }
294            }
295        }
296
297        fn read_range_bound<F: Fn(&Element) -> Option<T>>(
298            element: &Element,
299            boundary_element: &Element,
300            value_fn: F,
301        ) -> IonSchemaResult<Limit<T>> {
302            let is_exclusive = boundary_element.annotations().contains("exclusive");
303            isl_require!(boundary_element.annotations().len() == if is_exclusive {1} else {0} => "invalid annotation(s) on range boundary {element}")?;
304
305            match boundary_element.as_symbol().map(|s| s.text()) {
306                Some(Some("min")) => {
307                    isl_require!(!is_exclusive => "'min' may not be exclusive")?;
308                    Ok(Limit::Min)
309                }
310                Some(Some("max")) => {
311                    isl_require!(!is_exclusive => "'max' may not be exclusive")?;
312                    Ok(Limit::Max)
313                }
314                _ => {
315                    let limit_value: T = value_fn(boundary_element).ok_or_else(|| {
316                        invalid_schema_error_raw(format!(
317                            "invalid value for range boundary: {element}"
318                        ))
319                    })?;
320                    if is_exclusive {
321                        Ok(Limit::Exclusive(limit_value))
322                    } else {
323                        Ok(Limit::Inclusive(limit_value))
324                    }
325                }
326            }
327        }
328    }
329
330    impl<T: Clone + PartialEq + PartialOrd> From<T> for Range<T>
331    where
332        Self: RangeValidation<T>,
333    {
334        fn from(value: T) -> Self {
335            Range::new_single_value(value)
336        }
337    }
338
339    impl<T: PartialEq + Display> Display for Range<T> {
340        fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
341            match &self.lower {
342                Limit::Inclusive(value) if self.lower == self.upper => value.fmt(f),
343                _ => f.write_fmt(format_args!("range::[{},{}]", self.lower, self.upper)),
344            }
345        }
346    }
347
348    impl<T: WriteAsIon + PartialEq> WriteAsIon for Range<T> {
349        fn write_as_ion<V: ValueWriter>(&self, writer: V) -> IonResult<()> {
350            match &self.lower {
351                Limit::Inclusive(value) if self.lower == self.upper => writer.write(value),
352                _ => writer
353                    .with_annotations(["range"])?
354                    .write([&self.lower, &self.upper]),
355            }
356        }
357    }
358}
359
360#[cfg(test)]
361mod tests {
362    //! These test are for the generic functionality of Range.
363    //! More specific test cases are handled as part of ion-schema-tests.
364
365    use crate::isl::ranges::base::Range;
366    use crate::isl::ranges::{I64Range, Limit};
367    use crate::IonSchemaResult;
368    use ion_rs::Element;
369    use rstest::*;
370
371    #[rstest(
372        case::range_with_min_max("range::[min, max]"),
373        case::range_with_max_lower_bound("range::[max, 5]"),
374        case::range_with_min_upper_bound("range::[5, min]"),
375        case::range_with_lower_bound_greater_than_upper_bound("range::[10, 5]"),
376        case::empty_range_with_exclusive_lower_bound("range::[exclusive::5, 5]"),
377        case::empty_range_with_exclusive_upper_bound("range::[5, exclusive::5]"),
378        case::empty_range_with_mutually_excluding_bounds("range::[exclusive::5, exclusive::5]"),
379        case::range_with_unknown_annotation("range::[0, foo::5]"),
380        case::range_without_range_annotation("[5, 10]")
381    )]
382    fn invalid_ranges_from_isl(#[case] range_ion: &str) {
383        let range =
384            I64Range::from_ion_element(&Element::read_one(range_ion).unwrap(), Element::as_i64);
385        assert!(range.is_err());
386    }
387
388    #[rstest(
389        case::range_with_both_limits_unbounded(Range::new(Limit::Min, Limit::Max)),
390        case::range_with_lower_bound_greater_than_upper_bound(Range::new(
391            Limit::Inclusive(3),
392            Limit::Inclusive(1)
393        )),
394        case::range_with_lower_bound_greater_than_upper_bound(Range::new_inclusive(3, 1)),
395        case::empty_range_with_exclusive_lower_bound(Range::new(
396            Limit::Exclusive(3),
397            Limit::Inclusive(3)
398        )),
399        case::empty_range_with_exclusive_upper_bound(Range::new(
400            Limit::Inclusive(3),
401            Limit::Exclusive(3)
402        ))
403    )]
404    fn invalid_ranges_from_constructor(#[case] range_result: IonSchemaResult<Range<i64>>) {
405        assert!(range_result.is_err());
406    }
407
408    #[rstest(
409        case::lower_is_unbounded(
410            Range::new(Limit::Min, Limit::Inclusive(5)),
411            vec![-128, 0, 5],
412            vec![6, 127],
413        ),
414        case::upper_is_unbounded(
415            Range::new(Limit::Inclusive(5), Limit::Max),
416            vec![5, 6, 127],
417            vec![-128, 0, 4],
418        ),
419        case::lower_bound_is_exclusive(
420            Range::new(Limit::Exclusive(5), Limit::Inclusive(10)),
421            vec![6, 9, 10],
422            vec![0, 5, 11],
423        ),
424        case::upper_bound_is_exclusive(
425            Range::new(Limit::Inclusive(5), Limit::Exclusive(10)),
426            vec![5, 6, 9],
427            vec![0, 4, 10],
428        )
429    )]
430    fn range_contains(
431        #[case] range: IonSchemaResult<Range<i64>>,
432        #[case] valid_values: Vec<i64>,
433        #[case] invalid_values: Vec<i64>,
434    ) {
435        let range = range.unwrap();
436        for valid_value in valid_values {
437            let range_contains_result = range.contains(&valid_value);
438            assert!(
439                range_contains_result,
440                "Value {valid_value} was not in {range}"
441            )
442        }
443        for invalid_value in invalid_values {
444            let range_contains_result = range.contains(&invalid_value);
445            assert!(
446                !range_contains_result,
447                "Value {invalid_value} was unexpectedly in {range}"
448            )
449        }
450    }
451
452    #[rstest(
453        case::a_very_simple_case("range::[0,1]", Range::new(Limit::Inclusive(0), Limit::Inclusive(1)).unwrap()),
454        case::lower_is_unbounded("range::[min,1]", Range::new(Limit::Min, Limit::Inclusive(1)).unwrap()),
455        case::upper_is_unbounded("range::[1,max]", Range::new(Limit::Inclusive(1), Limit::Max).unwrap()),
456        case::lower_equals_upper("1", Range::new_single_value(1)),
457        case::lower_is_exclusive("range::[exclusive::0,2]", Range::new(Limit::Exclusive(0), Limit::Inclusive(2)).unwrap()),
458        case::upper_is_exclusive("range::[0,exclusive::2]", Range::new(Limit::Inclusive(0), Limit::Exclusive(2)).unwrap()),
459        // In some cases, the range can be elided to a number
460        case::upper_is_exclusive("1", Range::new(Limit::Inclusive(1), Limit::Inclusive(1)).unwrap()),
461    )]
462    fn range_display(#[case] expected: &str, #[case] range: Range<i64>) {
463        assert_eq!(expected, format!("{range}"));
464    }
465}
ion_schema/isl/ranges.rs

ion_schema/isl/
ranges.rs
