hidane_rules/eval/
constraint.rs

1//! What a list knows of a field its query filters on, when the filters do not give its value:
2//! a `constraint`, as the official emulator calls it (`tools/oracle/rules_list.py`).
3//!
4//! A constraint is the field's filters, each a comparator and a value, each once (`n > 0 &&
5//! n != 3` is `GT 0`, `NEQ 3`; `not-in [1, 2]` is `NEQ 1`, `NEQ 2`; `is not null` is `NEQ null`;
6//! `array-contains 'a'` is `LIST_CONTAINS 'a'`; `super::list` has the filters with null and
7//! NaN). A comparison with it is true when one of the filters alone implies it (`GT 5` implies
8//! `> 4`, `>= 5.0` and `!= 1`; `GTE 1` and `LTE 1` together do not imply `== 1`), and otherwise
9//! an error without a message, which a denial shows as `evaluation error at L5:22`: never
10//! false. A filter implies nothing of a value of another type, but:
11//!
12//! - `!= null` always holds, and `EQ null` implies `== null`;
13//! - `false` is less than `true` (`EQ true` implies `!= false`);
14//! - comparisons with NaN go as in IEEE 754, where no number is equal to, less than or greater
15//!   than NaN: `EQ NaN` lets no value through and so implies any comparison with a number, and a
16//!   filter with another number implies `!= NaN` and nothing else of NaN;
17//! - a float in a filter does not compare with an int in the rule (`>= 1.5` does not imply
18//!   `> 1`) and is never equal to one (`EQ 1.0` implies `!= 1`), though an int in a filter does
19//!   compare with a float (`> 5` implies `> 4.5`, `EQ 1` implies `== 1.0`);
20//! - `<`, `<=`, `>` and `>=` with a value of a type without an order (a bool, null, a list, a
21//!   map, a set, a latlng or a path) are a type error, whatever the filters.
22//!
23//! `x in c` holds when `c` has `LIST_CONTAINS x`, and `c.hasAny(list)` is whether it has one of
24//! the list's items; `c in list` is false, `c is constraint` true, and anything else is the
25//! error any other value of a type without that operation gives.
26
27use std::cmp::Ordering;
28
29use super::{
30    trace::{observe, shows},
31    value::{Error, R, Val, eq, strict_eq, utf16_cmp},
32};
33use crate::ast::BinaryOp;
34
35/// How a filter of a constraint compares.
36#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
37pub enum Comparator {
38    Eq,
39    Neq,
40    Lt,
41    Lte,
42    Gt,
43    Gte,
44    ListContains,
45}
46
47impl Comparator {
48    /// The official name: `EQ`, `NEQ`, `LT`, `LTE`, `GT`, `GTE` or `LIST_CONTAINS`.
49    pub fn name(self) -> &'static str {
50        match self {
51            Self::Eq => "EQ",
52            Self::Neq => "NEQ",
53            Self::Lt => "LT",
54            Self::Lte => "LTE",
55            Self::Gt => "GT",
56            Self::Gte => "GTE",
57            Self::ListContains => "LIST_CONTAINS",
58        }
59    }
60}
61
62/// One filter of a constraint.
63#[derive(Debug, Clone)]
64pub(crate) struct Simple {
65    pub comparator: Comparator,
66    pub value: Val,
67}
68
69impl Simple {
70    /// Whether two filters are one, as the official emulator keeps each filter of a field
71    /// once: the same comparator, and values of the same type that are equal (every NaN alike,
72    /// `1` apart from `1.0`).
73    pub fn same(&self, other: &Self) -> bool {
74        self.comparator == other.comparator && shows(&observe(&self.value), &other.value)
75    }
76}
77
78/// `l op r` when either side is a constraint; `None` when neither is, or the operator treats a
79/// constraint like any other value.
80pub(crate) fn binary(op: BinaryOp, l: &Val, r: &Val) -> Option<R> {
81    let comparison = matches!(
82        op,
83        BinaryOp::Eq | BinaryOp::Ne | BinaryOp::Lt | BinaryOp::Le | BinaryOp::Gt | BinaryOp::Ge
84    );
85    Some(match (l, r) {
86        (Val::Constraint(_), Val::Constraint(_)) if comparison || op == BinaryOp::In => {
87            Err(Error::type_error(
88                "constraint",
89                "bool,duration,float,int,latlng,map,null,string,bytes,timestamp,path,list,\
90                 vector,set",
91            ))
92        }
93        (Val::Constraint(c), v) if comparison => implies(c, op, v),
94        (v, Val::Constraint(c)) if comparison => implies(c, flip(op), v),
95        (v, Val::Constraint(c)) if op == BinaryOp::In => {
96            let contains = c
97                .iter()
98                .any(|s| s.comparator == Comparator::ListContains && strict_eq(&s.value, v));
99            if contains {
100                Ok(Val::Bool(true))
101            } else {
102                Err(Error::undecided())
103            }
104        }
105        _ => return None,
106    })
107}
108
109/// `c.hasAny(items)`.
110pub(crate) fn has_any(c: &[Simple], items: &[Val]) -> bool {
111    c.iter().any(|s| {
112        s.comparator == Comparator::ListContains && items.iter().any(|i| strict_eq(&s.value, i))
113    })
114}
115
116/// `v op c` as `c op' v`.
117fn flip(op: BinaryOp) -> BinaryOp {
118    match op {
119        BinaryOp::Lt => BinaryOp::Gt,
120        BinaryOp::Le => BinaryOp::Ge,
121        BinaryOp::Gt => BinaryOp::Lt,
122        BinaryOp::Ge => BinaryOp::Le,
123        other => other,
124    }
125}
126
127/// `c op v`: true if one filter of `c` implies it, else undecided.
128fn implies(c: &[Simple], op: BinaryOp, v: &Val) -> R {
129    let ordered = matches!(
130        v,
131        Val::Timestamp(..)
132            | Val::Duration(_)
133            | Val::Float(_)
134            | Val::Int(_)
135            | Val::Str(_)
136            | Val::Bytes(_)
137    );
138    if matches!(
139        op,
140        BinaryOp::Lt | BinaryOp::Le | BinaryOp::Gt | BinaryOp::Ge
141    ) && !ordered
142    {
143        return Err(Error::type_error(
144            v.type_name(),
145            "timestamp,duration,float,int,string,bytes",
146        ));
147    }
148    let implied =
149        (op == BinaryOp::Ne && matches!(v, Val::Null)) || c.iter().any(|s| s.implies(op, v));
150    if implied {
151        Ok(Val::Bool(true))
152    } else {
153        Err(Error::undecided())
154    }
155}
156
157fn is_number(v: &Val) -> bool {
158    matches!(v, Val::Int(_) | Val::Float(_))
159}
160
161fn is_nan(v: &Val) -> bool {
162    matches!(v, Val::Float(f) if f.is_nan())
163}
164
165impl Simple {
166    /// Whether every value this filter lets through satisfies `x op v`.
167    fn implies(&self, op: BinaryOp, v: &Val) -> bool {
168        use BinaryOp::{Eq, Ge, Gt, Le, Lt, Ne};
169        use Ordering::{Equal, Greater, Less};
170        if self.comparator == Comparator::ListContains {
171            return false;
172        }
173        if is_number(&self.value) && is_number(v) {
174            // `NEQ NaN` lets any number through, and a filter with NaN that compares otherwise
175            // none.
176            if is_nan(&self.value) {
177                return self.comparator != Comparator::Neq || (op == Ne && is_nan(v));
178            }
179            if is_nan(v) {
180                return op == Ne;
181            }
182            // A float in a filter has no order with an int, and is never equal to one.
183            if let (Val::Float(_), Val::Int(_)) = (&self.value, v) {
184                return self.comparator == Comparator::Eq && op == Ne;
185            }
186        }
187        // How the filter's value compares with `v`.
188        let Some(order) = relation(&self.value, v) else {
189            return false;
190        };
191        match (self.comparator, order) {
192            (Comparator::Eq, Equal) => matches!(op, Eq | Le | Ge),
193            (Comparator::Eq, Less) => matches!(op, Ne | Lt | Le),
194            (Comparator::Eq, Greater) => matches!(op, Ne | Gt | Ge),
195            (Comparator::Neq, Equal) => op == Ne,
196            (Comparator::Gt, Equal | Greater) | (Comparator::Gte, Greater) => {
197                matches!(op, Gt | Ge | Ne)
198            }
199            (Comparator::Gte, Equal) => op == Ge,
200            (Comparator::Lt, Equal | Less) | (Comparator::Lte, Less) => matches!(op, Lt | Le | Ne),
201            (Comparator::Lte, Equal) => op == Le,
202            _ => false,
203        }
204    }
205}
206
207/// How a filter's value compares with a rule's, if they compare.
208fn relation(filter: &Val, rule: &Val) -> Option<Ordering> {
209    match (filter, rule) {
210        (Val::Int(a), Val::Int(b)) => Some(a.cmp(b)),
211        (Val::Float(a), Val::Float(b)) => a.partial_cmp(b),
212        (Val::Int(a), Val::Float(b)) => (*a as f64).partial_cmp(b),
213        (Val::Float(_), Val::Int(_)) => None,
214        (Val::Bool(a), Val::Bool(b)) => Some(a.cmp(b)),
215        (Val::Str(a), Val::Str(b)) => Some(utf16_cmp(a, b)),
216        (Val::Bytes(a), Val::Bytes(b)) => Some(a.cmp(b)),
217        (Val::Timestamp(s, n), Val::Timestamp(t, m)) => Some((s, n).cmp(&(t, m))),
218        (a, b) if eq(a, b) => Some(Ordering::Equal),
219        _ => None,
220    }
221}
hidane_rules/eval/constraint.rs

hidane_rules/eval/
constraint.rs
