trustfall_core/interpreter/hints/
candidates.rs

1#![allow(dead_code)]
2
3use std::{
4    borrow::{Borrow, Cow},
5    fmt::Debug,
6    ops::Bound,
7};
8
9use itertools::Itertools;
10use serde::{Deserialize, Serialize};
11
12use crate::ir::FieldValue;
13
14/// Candidate values for the value of a vertex property.
15#[non_exhaustive]
16#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
17pub enum CandidateValue<T> {
18    /// This property has no valid value that satisfies the query.
19    Impossible,
20
21    /// There's only one value that could satisfy the query.
22    Single(T),
23
24    /// There are multiple discrete values that could satisfy the query.
25    Multiple(Vec<T>),
26
27    /// A continuous range of values for this property could satisfy this query.
28    /// The endpoints of the range may be inclusive or exclusive, and
29    /// the range may include or exclude the `null` value.
30    Range(Range<T>),
31
32    /// We've detected no constraints on the value of this property.
33    All,
34}
35
36impl<T: Clone> CandidateValue<&T> {
37    /// Converts from `CandidateValue<&T>` to `CandidateValue<T>`.
38    pub(crate) fn cloned(&self) -> CandidateValue<T> {
39        match self {
40            CandidateValue::Impossible => CandidateValue::Impossible,
41            CandidateValue::Single(s) => CandidateValue::Single((*s).clone()),
42            CandidateValue::Multiple(m) => {
43                CandidateValue::Multiple(m.iter().copied().cloned().collect())
44            }
45            CandidateValue::Range(r) => CandidateValue::Range(r.cloned()),
46            CandidateValue::All => CandidateValue::All,
47        }
48    }
49}
50
51impl<T: Clone> CandidateValue<T> {
52    /// Converts from `CandidateValue<T>` to `CandidateValue<&T>`.
53    pub(crate) fn as_ref(&self) -> CandidateValue<&T> {
54        match self {
55            CandidateValue::Impossible => CandidateValue::Impossible,
56            CandidateValue::Single(s) => CandidateValue::Single(s),
57            CandidateValue::Multiple(m) => CandidateValue::Multiple(m.iter().collect()),
58            CandidateValue::Range(r) => CandidateValue::Range(r.as_ref()),
59            CandidateValue::All => CandidateValue::All,
60        }
61    }
62}
63
64impl<T: Clone> CandidateValue<Cow<'_, T>> {
65    pub(super) fn into_owned(self) -> CandidateValue<T> {
66        match self {
67            CandidateValue::Impossible => CandidateValue::Impossible,
68            CandidateValue::Single(s) => CandidateValue::Single(s.into_owned()),
69            CandidateValue::Multiple(mult) => {
70                CandidateValue::Multiple(mult.into_iter().map(|x| x.into_owned()).collect())
71            }
72            CandidateValue::Range(range) => CandidateValue::Range(range.into_owned()),
73            CandidateValue::All => CandidateValue::All,
74        }
75    }
76
77    pub(super) fn as_deref(&self) -> CandidateValue<&T> {
78        match self {
79            CandidateValue::Impossible => CandidateValue::Impossible,
80            CandidateValue::Single(s) => CandidateValue::Single(s.as_ref()),
81            CandidateValue::Multiple(mult) => {
82                CandidateValue::Multiple(mult.iter().map(|x| x.as_ref()).collect())
83            }
84            CandidateValue::Range(range) => CandidateValue::Range(range.as_deref()),
85            CandidateValue::All => CandidateValue::All,
86        }
87    }
88}
89
90impl<T: Clone + PartialEq> PartialEq<CandidateValue<&T>> for CandidateValue<Cow<'_, T>> {
91    fn eq(&self, other: &CandidateValue<&T>) -> bool {
92        match (self, other) {
93            (CandidateValue::Impossible, CandidateValue::Impossible) => true,
94            (CandidateValue::Single(l), CandidateValue::Single(r)) => l.as_ref() == *r,
95            (CandidateValue::Multiple(mult_l), CandidateValue::Multiple(mult_r)) => {
96                mult_l.len() == mult_r.len() && mult_l.iter().zip(mult_r.iter()).all_equal()
97            }
98            (CandidateValue::Range(l), CandidateValue::Range(r)) => l.as_deref() == *r,
99            (CandidateValue::All, CandidateValue::All) => true,
100            _ => false,
101        }
102    }
103}
104
105impl<T: Clone + PartialEq> PartialEq<CandidateValue<T>> for CandidateValue<Cow<'_, T>> {
106    fn eq(&self, other: &CandidateValue<T>) -> bool {
107        match (self, other) {
108            (CandidateValue::Impossible, CandidateValue::Impossible) => true,
109            (CandidateValue::Single(l), CandidateValue::Single(r)) => l.as_ref() == r,
110            (CandidateValue::Multiple(mult_l), CandidateValue::Multiple(mult_r)) => {
111                mult_l.len() == mult_r.len() && mult_l.iter().zip(mult_r.iter()).all_equal()
112            }
113            (CandidateValue::Range(l), CandidateValue::Range(r)) => l.as_deref() == r.as_ref(),
114            (CandidateValue::All, CandidateValue::All) => true,
115            _ => false,
116        }
117    }
118}
119
120impl<T: Debug + Clone + PartialEq + Eq + PartialOrd + NullableValue + Default> CandidateValue<T> {
121    pub(super) fn intersect(&mut self, mut other: CandidateValue<T>) {
122        match self {
123            Self::Impossible => {} // still impossible
124            Self::Single(val) => {
125                // It can only be single value,
126                // but might become impossible depending on the other side.
127                match other {
128                    Self::Impossible => *self = CandidateValue::Impossible,
129                    Self::Single(other) => {
130                        if val != &other {
131                            *self = CandidateValue::Impossible;
132                        }
133                    }
134                    Self::Multiple(others) => {
135                        if !others.contains(val) {
136                            *self = CandidateValue::Impossible;
137                        }
138                    }
139                    Self::Range(others) => {
140                        if !others.contains(val) {
141                            *self = CandidateValue::Impossible;
142                        }
143                    }
144                    Self::All => {} // self is unchanged.
145                }
146            }
147            Self::Multiple(multiple) => {
148                match other {
149                    Self::Impossible => *self = CandidateValue::Impossible,
150                    Self::Single(other) => {
151                        // The other side can only be a single value.
152                        // The result is either only a single value or impossible
153                        // depending on whether there's overlap.
154                        if multiple.contains(&other) {
155                            *self = Self::Single(other);
156                        } else {
157                            *self = Self::Impossible;
158                        }
159                    }
160                    Self::Multiple(_) | Self::Range(_) => {
161                        // We normalize at the end, for now let's just
162                        // eliminate the disallowed values.
163                        if let Self::Multiple(others) = &other {
164                            multiple.retain(|value| others.contains(value));
165                        } else if let Self::Range(others) = &other {
166                            multiple.retain(|value| others.contains(value));
167                        } else {
168                            unreachable!("expected only Multiple or Range in this branch, but got: {other:?}");
169                        }
170                    }
171                    Self::All => {} // self is unchanged.
172                }
173            }
174            Self::Range(range) => {
175                if let CandidateValue::Range(other) = other {
176                    range.intersect(other)
177                } else {
178                    // We've already handled this case, just with operands reversed.
179                    let mut placeholder = CandidateValue::All;
180                    std::mem::swap(self, &mut placeholder);
181                    other.intersect(placeholder);
182                    *self = other;
183                }
184            }
185            Self::All => {
186                // Whatever the other candidate was. It can't be any wider than Self::All.
187                *self = other;
188            }
189        }
190
191        self.normalize();
192    }
193
194    pub(super) fn exclude_single_value<U: PartialEq + Eq + PartialOrd + NullableValue>(
195        &mut self,
196        value: &U,
197    ) where
198        T: Borrow<U>,
199    {
200        match self {
201            CandidateValue::Impossible => {} // nothing further to exclude
202            CandidateValue::Single(s) => {
203                if <T as Borrow<U>>::borrow(s) == value {
204                    *self = CandidateValue::Impossible;
205                }
206            }
207            CandidateValue::Multiple(multiple) => {
208                multiple.retain(|v| v.borrow() != value);
209                self.normalize();
210            }
211            CandidateValue::Range(range) => {
212                if value.is_null() {
213                    range.null_included = false;
214                } else {
215                    // TODO: When the values are integers, we can do better here:
216                    //       we can move from one included bound to another, tighter included bound.
217                    //       This can allow subsequent value exclusions through other heuristics.
218                    if let Bound::Included(incl) = range.start_bound() {
219                        if incl.borrow() == value {
220                            range.start = Bound::Excluded(incl.clone());
221                        }
222                    }
223                    if let Bound::Included(incl) = range.end_bound() {
224                        if incl.borrow() == value {
225                            range.end = Bound::Excluded(incl.clone());
226                        }
227                    }
228                }
229                self.normalize();
230            }
231            CandidateValue::All => {
232                // We can only meaningfully exclude null values from the full range.
233                //
234                // TODO: In principle, we can also exclude the extreme values of integers,
235                //       if we want to special-case this to the type of values.
236                if value.is_null() {
237                    *self = CandidateValue::Range(Range::full_non_null())
238                }
239            }
240        }
241    }
242
243    pub(super) fn normalize(&mut self) {
244        let next_self = if let Self::Range(range) = self {
245            if range.null_only() {
246                Some(Self::Single(T::default()))
247            } else if range.degenerate() {
248                Some(CandidateValue::Impossible)
249            } else if range.start_bound() == range.end_bound() {
250                if *range == Range::full() {
251                    Some(CandidateValue::All)
252                } else if let Bound::Included(b) = range.start_bound() {
253                    // If the range is point-like (possibly +null), convert it to discrete values.
254                    if range.null_included() {
255                        Some(Self::Multiple(vec![T::default(), b.clone()]))
256                    } else {
257                        Some(Self::Single(b.clone()))
258                    }
259                } else {
260                    None
261                }
262            } else {
263                None
264            }
265        } else if let Self::Multiple(values) = self {
266            if values.is_empty() {
267                Some(Self::Impossible)
268            } else if values.len() == 1 {
269                Some(Self::Single(values.pop().expect("no value present")))
270            } else {
271                None
272            }
273        } else {
274            None
275        };
276
277        if let Some(next_self) = next_self {
278            *self = next_self;
279        }
280    }
281}
282
283/// A way to check whether the value represents `null`.
284pub trait NullableValue {
285    /// Returns `true` if the value represents `null`.
286    fn is_null(&self) -> bool;
287}
288
289impl NullableValue for FieldValue {
290    fn is_null(&self) -> bool {
291        matches!(self, FieldValue::Null)
292    }
293}
294
295impl NullableValue for &FieldValue {
296    fn is_null(&self) -> bool {
297        matches!(*self, FieldValue::Null)
298    }
299}
300
301impl NullableValue for Cow<'_, FieldValue> {
302    fn is_null(&self) -> bool {
303        match self {
304            Cow::Borrowed(v) => v.is_null(),
305            Cow::Owned(v) => v.is_null(),
306        }
307    }
308}
309
310/// A range of values. Both its endpoints may be included or excluded in the range, or unbounded.
311#[non_exhaustive]
312#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
313pub struct Range<T> {
314    start: Bound<T>,
315    end: Bound<T>,
316    null_included: bool,
317}
318
319impl<T: Clone> Range<&T> {
320    /// Converts from `Range<&T>` to `Range<T>`.
321    pub fn cloned(&self) -> Range<T> {
322        let start = match self.start {
323            Bound::Unbounded => Bound::Unbounded,
324            Bound::Included(b) => Bound::Included(b.clone()),
325            Bound::Excluded(b) => Bound::Excluded(b.clone()),
326        };
327        let end = match self.end {
328            Bound::Unbounded => Bound::Unbounded,
329            Bound::Included(b) => Bound::Included(b.clone()),
330            Bound::Excluded(b) => Bound::Excluded(b.clone()),
331        };
332        Range { start, end, null_included: self.null_included }
333    }
334}
335
336impl<T: Clone> Range<Cow<'_, T>> {
337    fn into_owned(self) -> Range<T> {
338        let start = self.start.map(|b| b.into_owned());
339        let end = self.end.map(|b| b.into_owned());
340        Range { start, end, null_included: self.null_included }
341    }
342
343    fn as_deref(&self) -> Range<&T> {
344        let start = match &self.start {
345            Bound::Included(incl) => Bound::Included(incl.as_ref()),
346            Bound::Excluded(excl) => Bound::Excluded(excl.as_ref()),
347            Bound::Unbounded => Bound::Unbounded,
348        };
349        let end = match &self.end {
350            Bound::Included(incl) => Bound::Included(incl.as_ref()),
351            Bound::Excluded(excl) => Bound::Excluded(excl.as_ref()),
352            Bound::Unbounded => Bound::Unbounded,
353        };
354        Range { start, end, null_included: self.null_included }
355    }
356}
357
358impl<T> Range<T> {
359    /// The full, unbounded range of values.
360    pub const fn full() -> Range<T> {
361        Self { start: Bound::Unbounded, end: Bound::Unbounded, null_included: true }
362    }
363
364    /// The full range of values, except null.
365    pub const fn full_non_null() -> Range<T> {
366        Self { start: Bound::Unbounded, end: Bound::Unbounded, null_included: false }
367    }
368
369    /// Converts from `&Range<T>` to `Range<&T>`.
370    pub fn as_ref(&self) -> Range<&T> {
371        Range {
372            start: self.start.as_ref(),
373            end: self.end.as_ref(),
374            null_included: self.null_included,
375        }
376    }
377}
378
379impl<T: Debug + Clone + PartialEq + Eq + PartialOrd + NullableValue> Range<T> {
380    pub(super) fn new(start: Bound<T>, end: Bound<T>, null_included: bool) -> Self {
381        match &start {
382            Bound::Included(v) | Bound::Excluded(v) => {
383                assert!(!v.is_null(), "cannot bound range with null value")
384            }
385            Bound::Unbounded => {}
386        }
387        match &end {
388            Bound::Included(v) | Bound::Excluded(v) => {
389                assert!(!v.is_null(), "cannot bound range with null value")
390            }
391            Bound::Unbounded => {}
392        }
393        Self { start, end, null_included }
394    }
395
396    pub(super) fn with_start(start: Bound<T>, null_included: bool) -> Self {
397        match &start {
398            Bound::Included(v) | Bound::Excluded(v) => {
399                assert!(!v.is_null(), "cannot bound range with null value")
400            }
401            Bound::Unbounded => {}
402        }
403        Self { start, end: Bound::Unbounded, null_included }
404    }
405
406    pub(super) fn with_end(end: Bound<T>, null_included: bool) -> Self {
407        match &end {
408            Bound::Included(v) | Bound::Excluded(v) => {
409                assert!(!v.is_null(), "cannot bound range with null value")
410            }
411            Bound::Unbounded => {}
412        }
413        Self { start: Bound::Unbounded, end, null_included }
414    }
415
416    pub(super) fn intersect(&mut self, other: Range<T>) {
417        match &mut self.start {
418            Bound::Included(start) => {
419                debug_assert!(!start.is_null());
420                match &other.start {
421                    Bound::Included(other_start) => {
422                        debug_assert!(!other_start.is_null());
423                        if &*start < other_start {
424                            self.start = other.start;
425                        }
426                    }
427                    Bound::Excluded(other_start) => {
428                        debug_assert!(!other_start.is_null());
429                        if &*start <= other_start {
430                            // self.end should become a Bound::Excluded
431                            self.start = other.start;
432                        }
433                    }
434                    Bound::Unbounded => {}
435                }
436            }
437            Bound::Excluded(start) => {
438                debug_assert!(!start.is_null());
439                match &other.start {
440                    Bound::Included(other_start) | Bound::Excluded(other_start) => {
441                        debug_assert!(!other_start.is_null());
442                        if &*start < other_start {
443                            self.start = other.start;
444                        }
445                    }
446                    Bound::Unbounded => {}
447                }
448            }
449            Bound::Unbounded => self.start = other.start,
450        }
451
452        match &mut self.end {
453            Bound::Included(end) => {
454                debug_assert!(!end.is_null());
455                match &other.end {
456                    Bound::Included(other_end) => {
457                        debug_assert!(!other_end.is_null());
458                        if &*end > other_end {
459                            self.end = other.end;
460                        }
461                    }
462                    Bound::Excluded(other_end) => {
463                        debug_assert!(!other_end.is_null());
464                        if &*end >= other_end {
465                            // self.end should become a Bound::Excluded
466                            self.end = other.end;
467                        }
468                    }
469                    Bound::Unbounded => {}
470                }
471            }
472            Bound::Excluded(end) => {
473                debug_assert!(!end.is_null());
474                match &other.end {
475                    Bound::Included(other_end) | Bound::Excluded(other_end) => {
476                        debug_assert!(!other_end.is_null());
477                        if &*end > other_end {
478                            self.end = other.end;
479                        }
480                    }
481                    Bound::Unbounded => {}
482                }
483            }
484            Bound::Unbounded => self.end = other.end,
485        }
486
487        self.null_included &= other.null_included;
488    }
489
490    /// The range's start point. May include or exclude the value at the specified point.
491    #[inline]
492    pub fn start_bound(&self) -> Bound<&T> {
493        self.start.as_ref()
494    }
495
496    /// The range's end point. May include or exclude the value at the specified point.
497    #[inline]
498    pub fn end_bound(&self) -> Bound<&T> {
499        self.end.as_ref()
500    }
501
502    /// Whether the range includes the `null` value or not.
503    #[inline]
504    pub fn null_included(&self) -> bool {
505        self.null_included
506    }
507
508    /// A range is considered degenerate if it cannot contain any non-`null` values.
509    /// Degenerate ranges may still contain the `null` value.
510    #[inline]
511    pub fn degenerate(&self) -> bool {
512        match (self.start_bound(), self.end_bound()) {
513            (Bound::Included(l), Bound::Included(r)) => l > r,
514            (Bound::Included(l), Bound::Excluded(r))
515            | (Bound::Excluded(l), Bound::Included(r))
516            | (Bound::Excluded(l), Bound::Excluded(r)) => l >= r,
517            (_, Bound::Unbounded) | (Bound::Unbounded, _) => false,
518        }
519    }
520
521    /// Returns `true` if the range *only* contains the `null` value.
522    #[inline]
523    pub fn null_only(&self) -> bool {
524        self.null_included && self.degenerate()
525    }
526
527    /// Checks whether the specified value is part of the range.
528    pub fn contains(&self, item: &T) -> bool {
529        let is_null = item.is_null();
530        if is_null {
531            self.null_included
532        } else {
533            (match self.start_bound() {
534                Bound::Included(start) => start <= item,
535                Bound::Excluded(start) => start < item,
536                Bound::Unbounded => true,
537            }) && (match self.end_bound() {
538                Bound::Included(end) => item <= end,
539                Bound::Excluded(end) => item < end,
540                Bound::Unbounded => true,
541            })
542        }
543    }
544}
545
546#[cfg(test)]
547mod tests {
548    use std::ops::Bound;
549
550    use itertools::Itertools;
551
552    use crate::ir::FieldValue;
553
554    use super::CandidateValue;
555
556    #[test]
557    fn candidate_intersecting() {
558        use super::Range as R;
559        use CandidateValue::*;
560        let one = FieldValue::Int64(1);
561        let two = FieldValue::Int64(2);
562        let three = FieldValue::Int64(3);
563        let four = FieldValue::Int64(4);
564
565        let test_cases = [
566            // Anything merged into Impossible is Impossible.
567            (Impossible, Impossible, Impossible),
568            (Impossible, Single(&one), Impossible),
569            (Impossible, Multiple(vec![&one, &two]), Impossible),
570            (Impossible, Range(R::with_start(Bound::Included(&one), true)), Impossible),
571            //
572            // Intersecting Impossible into anything produces Imposssible.
573            (Single(&one), Impossible, Impossible),
574            (Multiple(vec![&one, &two]), Impossible, Impossible),
575            (Range(R::with_start(Bound::Included(&one), true)), Impossible, Impossible),
576            //
577            // Intersecting null into non-null, or vice versa, produces Impossible.
578            (Single(&FieldValue::NULL), Single(&one), Impossible),
579            (Single(&FieldValue::NULL), Multiple(vec![&one, &two]), Impossible),
580            (
581                Single(&FieldValue::NULL),
582                Range(R::with_start(Bound::Included(&one), false)),
583                Impossible,
584            ),
585            //
586            // Intersecting non-overlapping single or multiple values produces Impossible.
587            (Single(&one), Single(&two), Impossible),
588            (Single(&one), Multiple(vec![&two, &three]), Impossible),
589            (Multiple(vec![&one, &two]), Single(&three), Impossible),
590            (Multiple(vec![&one, &two]), Multiple(vec![&three, &four]), Impossible),
591            //
592            // Intersecting values with a non-overlapping range produces Impossible.
593            (Single(&one), Range(R::with_start(Bound::Excluded(&one), true)), Impossible),
594            (Single(&one), Range(R::with_start(Bound::Included(&two), false)), Impossible),
595            (
596                Multiple(vec![&two, &three]),
597                Range(R::with_end(Bound::Included(&one), true)),
598                Impossible,
599            ),
600            (
601                Multiple(vec![&two, &three]),
602                Range(R::with_end(Bound::Excluded(&two), false)),
603                Impossible,
604            ),
605            //
606            // Intersecting overlapping single values, or single with multiple or a range,
607            // produces the overlapping Single.
608            (Single(&one), Single(&one), Single(&one)),
609            (Multiple(vec![&one, &two]), Single(&one), Single(&one)),
610            (Single(&one), Multiple(vec![&one, &two]), Single(&one)),
611            (Single(&one), Range(R::with_start(Bound::Included(&one), false)), Single(&one)),
612            (Single(&one), Range(R::with_end(Bound::Excluded(&two), false)), Single(&one)),
613            //
614            // Intersecting null into multiple or a range that contains null produces null.
615            (
616                Single(&FieldValue::NULL),
617                Multiple(vec![&one, &FieldValue::Null]),
618                Single(&FieldValue::NULL),
619            ),
620            (
621                Single(&FieldValue::NULL),
622                Range(R::with_end(Bound::Excluded(&two), true)),
623                Single(&FieldValue::NULL),
624            ),
625            (
626                Single(&FieldValue::NULL),
627                Range(R::with_start(Bound::Excluded(&two), true)),
628                Single(&FieldValue::NULL),
629            ),
630            (
631                Single(&FieldValue::NULL),
632                Range(R::new(Bound::Unbounded, Bound::Unbounded, true)),
633                Single(&FieldValue::NULL),
634            ),
635            (
636                Single(&FieldValue::NULL),
637                Range(R::new(Bound::Excluded(&one), Bound::Excluded(&one), true)),
638                Single(&FieldValue::NULL),
639            ),
640            //
641            // Intersecting multiple values that include null works correctly too.
642            (
643                Multiple(vec![&one, &FieldValue::Null, &two, &three]),
644                Multiple(vec![&one, &FieldValue::Null, &four]),
645                Multiple(vec![&one, &FieldValue::Null]),
646            ),
647            //
648            // Intersecting ranges that only overlap on null produces Single(null).
649            (
650                Range(R::new(Bound::Included(&one), Bound::Included(&one), true)),
651                Range(R::new(Bound::Included(&two), Bound::Included(&two), true)),
652                Single(&FieldValue::NULL),
653            ),
654            (
655                Range(R::new(Bound::Included(&one), Bound::Excluded(&two), true)),
656                Range(R::new(Bound::Included(&two), Bound::Excluded(&three), true)),
657                Single(&FieldValue::NULL),
658            ),
659            //
660            // Intersecting ranges that only overlap on a single non-null value produces Single.
661            (
662                Range(R::new(Bound::Included(&one), Bound::Included(&two), false)),
663                Range(R::new(Bound::Included(&two), Bound::Included(&three), true)),
664                Single(&two),
665            ),
666            //
667            // Intersecting ranges that don't overlap at all produces Impossible.
668            (
669                Range(R::new(Bound::Included(&one), Bound::Included(&one), true)),
670                Range(R::new(Bound::Included(&two), Bound::Included(&two), false)),
671                Impossible,
672            ),
673            (
674                Range(R::new(Bound::Included(&one), Bound::Excluded(&two), false)),
675                Range(R::new(Bound::Included(&two), Bound::Excluded(&three), true)),
676                Impossible,
677            ),
678            //
679            // Intersecting ranges that only overlap on null and exactly one other value
680            // produces Multiple(null, that value).
681            (
682                Range(R::new(Bound::Included(&one), Bound::Included(&two), true)),
683                Range(R::new(Bound::Included(&two), Bound::Included(&three), true)),
684                Multiple(vec![&FieldValue::NULL, &two]),
685            ),
686            //
687            // Intersecting ranges that overlap on a range produces the overlapping range.
688            (
689                Range(R::new(Bound::Included(&one), Bound::Included(&three), true)),
690                Range(R::new(Bound::Included(&two), Bound::Included(&four), true)),
691                Range(R::new(Bound::Included(&two), Bound::Included(&three), true)),
692            ),
693            (
694                Range(R::new(Bound::Included(&one), Bound::Included(&three), false)),
695                Range(R::new(Bound::Included(&two), Bound::Included(&four), true)),
696                Range(R::new(Bound::Included(&two), Bound::Included(&three), false)),
697            ),
698            (
699                Range(R::new(Bound::Included(&one), Bound::Excluded(&three), true)),
700                Range(R::new(Bound::Included(&two), Bound::Included(&four), true)),
701                Range(R::new(Bound::Included(&two), Bound::Excluded(&three), true)),
702            ),
703            (
704                Range(R::new(Bound::Included(&one), Bound::Included(&three), false)),
705                Range(R::new(Bound::Excluded(&two), Bound::Included(&four), true)),
706                Range(R::new(Bound::Excluded(&two), Bound::Included(&three), false)),
707            ),
708            //
709            // Intersecting overlapping multiple values (or multiple + range)
710            // can produce either a Single or a Multiple, depending on the overlap size.
711            (Multiple(vec![&one, &two]), Multiple(vec![&two, &three]), Single(&two)),
712            (Multiple(vec![&two, &three]), Multiple(vec![&one, &two]), Single(&two)),
713            (
714                Multiple(vec![&two, &three]),
715                Multiple(vec![&one, &two, &three, &four]),
716                Multiple(vec![&two, &three]),
717            ),
718            (
719                Multiple(vec![&one, &two]),
720                Range(R::new(Bound::Included(&two), Bound::Included(&three), true)),
721                Single(&two),
722            ),
723            (
724                Multiple(vec![&two, &three]),
725                Range(R::new(Bound::Included(&one), Bound::Included(&two), true)),
726                Single(&two),
727            ),
728            (
729                Multiple(vec![&two, &three]),
730                Range(R::new(Bound::Included(&one), Bound::Included(&four), true)),
731                Multiple(vec![&two, &three]),
732            ),
733            //
734            // Intersecting Candidate::All from either position produces whatever the other value was.
735            (All, Impossible, Impossible),
736            (Impossible, All, Impossible),
737            (All, Single(&one), Single(&one)),
738            (Multiple(vec![&one, &two]), All, Multiple(vec![&one, &two])),
739            (
740                All,
741                Range(R::with_start(Bound::Included(&one), true)),
742                Range(R::with_start(Bound::Included(&one), true)),
743            ),
744            (All, All, All),
745        ];
746
747        for (original, intersected, expected) in test_cases {
748            let mut base = original.clone();
749            base.intersect(intersected.clone());
750            assert_eq!(expected, base, "{original:?} + {intersected:?} = {base:?} != {expected:?}");
751
752            let mut base = intersected.clone();
753            base.intersect(original.clone());
754            assert_eq!(expected, base, "{intersected:?} + {original:?} = {base:?} != {expected:?}");
755        }
756    }
757
758    /// Intersecting ranges where one is completely contained in the other
759    /// produces the smaller range, with appropriate "null_included".
760    #[test]
761    fn candidate_intersecting_preserves_overlap() {
762        use CandidateValue::*;
763        let one = FieldValue::Int64(1);
764        let two = FieldValue::Int64(2);
765        let three = FieldValue::Int64(3);
766        let four = FieldValue::Int64(4);
767        use super::Range as R;
768
769        let one_incl = Bound::Included(&one);
770        let one_excl = Bound::Excluded(&one);
771        let four_incl = Bound::Included(&four);
772        let four_excl = Bound::Excluded(&four);
773
774        let mut larger_ranges = vec![];
775        for one in [&one_incl, &one_excl, &Bound::Unbounded] {
776            for four in [&four_incl, &four_excl, &Bound::Unbounded] {
777                for null_included in [true, false] {
778                    larger_ranges.push(Range(R::new(*one, *four, null_included)));
779                }
780            }
781        }
782
783        let two_incl = Bound::Included(&two);
784        let two_excl = Bound::Excluded(&two);
785        let three_incl = Bound::Included(&three);
786        let three_excl = Bound::Excluded(&three);
787
788        let mut smaller_ranges = vec![];
789        for two in [&two_incl, &two_excl] {
790            for three in [&three_incl, &three_excl] {
791                for null_included in [true, false] {
792                    smaller_ranges.push(Range(R::new(*two, *three, null_included)));
793                }
794            }
795        }
796
797        for (original, intersected) in larger_ranges.into_iter().cartesian_product(smaller_ranges) {
798            let mut expected = intersected.clone();
799            if let Range(r) = &mut expected {
800                if let Range(r2) = &original {
801                    r.null_included &= r2.null_included;
802                } else {
803                    unreachable!();
804                }
805            } else {
806                unreachable!();
807            }
808
809            let mut base = original.clone();
810            base.intersect(intersected.clone());
811            assert_eq!(expected, base, "{original:?} + {intersected:?} = {base:?} != {expected:?}");
812
813            let mut base = intersected.clone();
814            base.intersect(original.clone());
815            assert_eq!(expected, base, "{intersected:?} + {original:?} = {base:?} != {expected:?}");
816        }
817    }
818
819    #[test]
820    fn candidate_intersecting_preserves_order_in_overlap() {
821        use CandidateValue::*;
822        let one = FieldValue::Int64(1);
823        let two = FieldValue::Int64(2);
824        let three = FieldValue::Int64(3);
825        let four = FieldValue::Int64(4);
826        let test_cases = [
827            //
828            // Intersecting multiple overlapping values preserves the order of the original.
829            (
830                Multiple(vec![&one, &two, &three, &four]),
831                Multiple(vec![&three, &two]),
832                Multiple(vec![&two, &three]),
833            ),
834            (
835                Multiple(vec![&three, &two]),
836                Multiple(vec![&one, &two, &three, &four]),
837                Multiple(vec![&three, &two]),
838            ),
839        ];
840
841        for (original, intersected, expected) in test_cases {
842            let mut base = original.clone();
843            base.intersect(intersected.clone());
844            assert_eq!(expected, base, "{original:?} + {intersected:?} = {base:?} != {expected:?}");
845        }
846    }
847
848    #[test]
849    fn candidate_excluding_value() {
850        use super::super::Range as R;
851        use CandidateValue::*;
852        let one = FieldValue::Int64(1);
853        let two = FieldValue::Int64(2);
854        let three = FieldValue::Int64(3);
855        let test_data = [
856            (Single(&one), &one, CandidateValue::Impossible),
857            (
858                // element order is preserved
859                Multiple(vec![&one, &two, &three]),
860                &one,
861                Multiple(vec![&two, &three]),
862            ),
863            (
864                // element order is preserved
865                Multiple(vec![&one, &two, &three]),
866                &two,
867                Multiple(vec![&one, &three]),
868            ),
869            (Multiple(vec![&one, &two]), &two, Single(&one)),
870            (Multiple(vec![&one, &FieldValue::NULL]), &one, Single(&FieldValue::NULL)),
871            (Multiple(vec![&one, &FieldValue::NULL]), &FieldValue::NULL, Single(&one)),
872            (Single(&one), &one, Impossible),
873            (Single(&FieldValue::NULL), &FieldValue::NULL, Impossible),
874            (All, &FieldValue::NULL, Range(R::full_non_null())),
875            (
876                Range(R::with_start(Bound::Included(&two), false)),
877                &two,
878                Range(R::with_start(Bound::Excluded(&two), false)),
879            ),
880            (
881                Range(R::with_end(Bound::Included(&two), true)),
882                &two,
883                Range(R::with_end(Bound::Excluded(&two), true)),
884            ),
885            (
886                Range(R::with_end(Bound::Included(&two), true)),
887                &FieldValue::NULL,
888                Range(R::with_end(Bound::Included(&two), false)),
889            ),
890        ];
891
892        for (candidate, excluded, expected) in test_data {
893            let mut base = candidate.clone();
894            base.exclude_single_value(&excluded);
895            assert_eq!(
896                expected, base,
897                "{candidate:?} - {excluded:?} produced {base:?} instead of {expected:?}"
898            );
899        }
900    }
901
902    #[test]
903    fn candidate_excluding_value_no_ops() {
904        use super::super::Range as R;
905        use CandidateValue::*;
906        let one = FieldValue::Int64(1);
907        let two = FieldValue::Int64(2);
908        let three = FieldValue::Int64(3);
909        let test_data = [
910            (Impossible, &one),
911            (Single(&one), &two),
912            (Multiple(vec![&one, &two]), &three),
913            (Range(R::full_non_null()), &FieldValue::NULL),
914            (Range(R::with_start(Bound::Included(&two), false)), &one),
915            (Range(R::with_start(Bound::Excluded(&two), false)), &two),
916            (Range(R::with_end(Bound::Included(&one), false)), &two),
917            (Range(R::with_end(Bound::Excluded(&one), false)), &one),
918            (Range(R::new(Bound::Included(&one), Bound::Included(&three), false)), &two),
919        ];
920
921        for (candidate, excluded) in test_data {
922            let mut base = candidate.clone();
923            base.exclude_single_value(&excluded);
924            assert_eq!(
925                candidate, base,
926                "{candidate:?} - {excluded:?} should have been a no-op but it produced {base:?}"
927            );
928        }
929    }
930
931    #[test]
932    fn candidate_excluding_value_of_different_integer_kind() {
933        use super::super::Range as R;
934        use CandidateValue::*;
935        let signed_one = FieldValue::Int64(1);
936        let signed_two = FieldValue::Int64(2);
937        let unsigned_one = FieldValue::Uint64(1);
938        let unsigned_two = FieldValue::Uint64(2);
939        let test_data = [
940            (Single(&signed_one), &unsigned_one, Impossible),
941            (Multiple(vec![&signed_one, &signed_two]), &unsigned_one, Single(&signed_two)),
942            (
943                Range(R::with_start(Bound::Included(&signed_one), true)),
944                &unsigned_one,
945                Range(R::with_start(Bound::Excluded(&signed_one), true)),
946            ),
947            (
948                Range(R::with_end(Bound::Included(&signed_one), true)),
949                &unsigned_one,
950                Range(R::with_end(Bound::Excluded(&signed_one), true)),
951            ),
952            (Single(&unsigned_one), &signed_one, Impossible),
953            (Multiple(vec![&unsigned_one, &unsigned_two]), &signed_one, Single(&unsigned_two)),
954            (
955                Range(R::with_start(Bound::Included(&unsigned_one), true)),
956                &signed_one,
957                Range(R::with_start(Bound::Excluded(&unsigned_one), true)),
958            ),
959            (
960                Range(R::with_end(Bound::Included(&unsigned_one), true)),
961                &signed_one,
962                Range(R::with_end(Bound::Excluded(&unsigned_one), true)),
963            ),
964        ];
965
966        for (candidate, excluded, expected) in test_data {
967            let mut base = candidate.clone();
968            base.exclude_single_value(&excluded);
969            assert_eq!(
970                expected, base,
971                "{candidate:?} - {excluded:?} produced {base:?} instead of {expected:?}"
972            );
973        }
974    }
975
976    #[test]
977    fn candidate_direct_normalization() {
978        use super::Range as R;
979        use CandidateValue::*;
980        let one = FieldValue::Int64(1);
981        let two = FieldValue::Int64(2);
982        let test_cases = [
983            (Multiple(vec![]), Impossible),
984            (Multiple(vec![&FieldValue::NULL]), Single(&FieldValue::NULL)),
985            (Multiple(vec![&two]), Single(&two)),
986            (Range(R::full()), All),
987            (
988                Range(R::new(Bound::Included(&one), Bound::Included(&one), true)),
989                Multiple(vec![&FieldValue::NULL, &one]),
990            ),
991            (Range(R::new(Bound::Included(&one), Bound::Included(&one), false)), Single(&one)),
992            (
993                Range(R::new(Bound::Included(&one), Bound::Excluded(&one), true)),
994                Single(&FieldValue::NULL),
995            ),
996            (Range(R::new(Bound::Included(&one), Bound::Excluded(&one), false)), Impossible),
997            (
998                Range(R::new(Bound::Included(&two), Bound::Included(&one), true)),
999                Single(&FieldValue::NULL),
1000            ),
1001            (Range(R::new(Bound::Included(&two), Bound::Included(&one), false)), Impossible),
1002            (
1003                Range(R::new(Bound::Excluded(&two), Bound::Included(&one), true)),
1004                Single(&FieldValue::NULL),
1005            ),
1006            (Range(R::new(Bound::Excluded(&two), Bound::Included(&one), false)), Impossible),
1007            (
1008                Range(R::new(Bound::Included(&two), Bound::Excluded(&one), true)),
1009                Single(&FieldValue::NULL),
1010            ),
1011            (Range(R::new(Bound::Included(&two), Bound::Excluded(&one), false)), Impossible),
1012            (
1013                Range(R::new(Bound::Excluded(&two), Bound::Excluded(&one), true)),
1014                Single(&FieldValue::NULL),
1015            ),
1016            (Range(R::new(Bound::Excluded(&two), Bound::Excluded(&one), false)), Impossible),
1017        ];
1018
1019        for (unnormalized, expected) in test_cases {
1020            let mut base = unnormalized.clone();
1021            base.normalize();
1022
1023            assert_eq!(expected, base, "{unnormalized:?}.normalize() = {base:?} != {expected:?}");
1024        }
1025    }
1026
1027    #[test]
1028    fn candidate_normalization() {
1029        use super::Range as R;
1030        use CandidateValue::*;
1031        let one = FieldValue::Int64(1);
1032        let two = FieldValue::Int64(2);
1033        let three = FieldValue::Int64(3);
1034        let four = FieldValue::Int64(4);
1035        let test_cases = [
1036            //
1037            // Causing a Multiple to lose all its elements turns it into Impossible
1038            (Multiple(vec![&one, &two, &three]), Single(&four), Impossible),
1039            (Multiple(vec![&one, &two]), Multiple(vec![&three, &four]), Impossible),
1040            (
1041                Multiple(vec![&one, &two]),
1042                Range(R::with_start(Bound::Included(&three), true)),
1043                Impossible,
1044            ),
1045            (
1046                Multiple(vec![&one, &two]),
1047                Range(R::with_start(Bound::Excluded(&two), true)),
1048                Impossible,
1049            ),
1050            (
1051                Multiple(vec![&one, &two, &FieldValue::NULL]),
1052                Range(R::with_start(Bound::Excluded(&two), false)),
1053                Impossible,
1054            ),
1055            //
1056            // Causing a Multiple to lose all but one of its elements turns it into Single
1057            (Multiple(vec![&one, &two, &three]), Single(&two), Single(&two)),
1058            (Multiple(vec![&one, &two, &three]), Multiple(vec![&two, &four]), Single(&two)),
1059            (
1060                Multiple(vec![&two, &three, &FieldValue::NULL]),
1061                Range(R::with_end(Bound::Included(&two), false)),
1062                Single(&two),
1063            ),
1064            (
1065                Multiple(vec![&two, &three, &FieldValue::NULL]),
1066                Range(R::with_end(Bound::Excluded(&two), true)),
1067                Single(&FieldValue::NULL),
1068            ),
1069        ];
1070
1071        for (original, intersected, expected) in test_cases {
1072            let mut base = original.clone();
1073            base.intersect(intersected.clone());
1074            assert_eq!(expected, base, "{original:?} + {intersected:?} = {base:?} != {expected:?}");
1075
1076            let mut base = intersected.clone();
1077            base.intersect(original.clone());
1078            assert_eq!(expected, base, "{intersected:?} + {original:?} = {base:?} != {expected:?}");
1079        }
1080    }
1081
1082    /// The test cases here codify the current behavior, which isn't that smart about integers.
1083    /// If/when the code becomes smarter here, these test cases can be updated and moved out
1084    /// from this module.
1085    mod future_work {
1086        use std::ops::Bound;
1087
1088        use crate::{interpreter::hints::CandidateValue, ir::FieldValue};
1089
1090        fn range_normalization_does_not_prefer_inclusive_bounds_for_integers() {
1091            use super::super::Range as R;
1092            use CandidateValue::*;
1093            let signed_one = FieldValue::Int64(1);
1094            let signed_three = FieldValue::Int64(3);
1095            let unsigned_one = FieldValue::Uint64(1);
1096            let unsigned_three = FieldValue::Uint64(3);
1097            let test_data = [
1098                Range(R::new(Bound::Excluded(&signed_one), Bound::Excluded(&signed_three), false)),
1099                Range(R::new(
1100                    Bound::Excluded(&unsigned_one),
1101                    Bound::Excluded(&unsigned_three),
1102                    false,
1103                )),
1104                Range(R::with_start(Bound::Excluded(&signed_one), false)),
1105                Range(R::with_start(Bound::Excluded(&unsigned_one), false)),
1106                Range(R::with_end(Bound::Excluded(&signed_three), false)),
1107                Range(R::with_end(Bound::Excluded(&unsigned_three), false)),
1108            ];
1109
1110            for candidate in test_data {
1111                let mut base = candidate.clone();
1112                base.normalize();
1113                assert_eq!(
1114                    candidate, base,
1115                    "normalization changed this value: {candidate:?} != {base:?}"
1116                );
1117            }
1118        }
1119
1120        fn candidate_value_exclusion_does_not_special_case_integers() {
1121            use super::super::Range as R;
1122            use CandidateValue::*;
1123            let signed_one = FieldValue::Int64(1);
1124            let signed_two = FieldValue::Int64(2);
1125            let signed_three = FieldValue::Int64(3);
1126            let unsigned_one = FieldValue::Uint64(1);
1127            let unsigned_two = FieldValue::Uint64(2);
1128            let unsigned_three = FieldValue::Uint64(3);
1129            let test_data = [
1130                (Range(R::full_non_null()), &FieldValue::Int64(i64::MIN)),
1131                (Range(R::full_non_null()), &FieldValue::Int64(i64::MAX)),
1132                (Range(R::full_non_null()), &FieldValue::Uint64(u64::MIN)),
1133                (Range(R::full_non_null()), &FieldValue::Uint64(u64::MAX)),
1134                (Range(R::with_start(Bound::Excluded(&signed_one), false)), &signed_two),
1135                (Range(R::with_start(Bound::Excluded(&unsigned_one), false)), &unsigned_two),
1136                (Range(R::with_end(Bound::Excluded(&signed_two), false)), &signed_one),
1137                (Range(R::with_end(Bound::Excluded(&unsigned_two), false)), &unsigned_one),
1138                (
1139                    Range(R::new(
1140                        Bound::Included(&unsigned_one),
1141                        Bound::Included(&unsigned_three),
1142                        false,
1143                    )),
1144                    &unsigned_two,
1145                ),
1146                (
1147                    Range(R::new(
1148                        Bound::Included(&signed_one),
1149                        Bound::Included(&signed_three),
1150                        false,
1151                    )),
1152                    &signed_two,
1153                ),
1154            ];
1155
1156            for (candidate, excluded) in test_data {
1157                let mut base = candidate.clone();
1158                base.exclude_single_value(&excluded);
1159                assert_eq!(
1160                    candidate, base,
1161                    "exclusion changed this value: {candidate:?} - {excluded:?} produced {base:?}"
1162                );
1163            }
1164        }
1165    }
1166}
trustfall_core/interpreter/hints/candidates.rs

trustfall_core/interpreter/hints/
candidates.rs
