Skip to main content

relate_core/value/
ordering.rs

1//! `Value` equality and ordering: Cypher's three-valued `cypher_eq`, the
2//! strict `eq_non_null`, the three-valued `compare` and the total
3//! `order_by_cmp` (ADR-0462 depth guards threaded through every container
4//! arm). Extracted from `value/mod.rs` for the file-size rule, following
5//! the `json.rs`/`props.rs` precedent; the methods stay inherent, so no
6//! caller changes.
7
8use std::cmp::Ordering;
9
10use super::*;
11
12/// Three-valued AND over element-wise `cypher_eq` results: any false pair
13/// yields false; otherwise any null pair yields null. Shared by the List
14/// and Map arms of [`Value::cypher_eq`]; `depth` is threaded through so the
15/// ADR-0462 guard reaches the recursive element comparison.
16fn cypher_eq_pairs<'a>(pairs: impl Iterator<Item = (&'a Value, &'a Value)>, depth: u32) -> Value {
17    let mut saw_null = false;
18    for (x, y) in pairs {
19        match x.cypher_eq_at(y, depth) {
20            Value::Bool(false) => return Value::Bool(false),
21            Value::Null => saw_null = true,
22            _ => {}
23        }
24    }
25    if saw_null {
26        Value::Null
27    } else {
28        Value::Bool(true)
29    }
30}
31
32/// The first elementwise comparison that is not `equal`, or `tie` when every
33/// zipped pair ties. Both iterators are zipped, so only the first `min(len)`
34/// pairs are compared; `tie` is where a caller states its length rule. A
35/// `None` result from `cmp` is terminal: a null operand decides the whole
36/// comparison as null. The one spelling of the hand-rolled
37/// first-non-equal loops ([`compare_maps`], [`Value::compare`]'s list arm,
38/// [`Value::order_by_cmp`]'s list/vector arms).
39fn lexicographic<A, B, C>(
40    a: impl Iterator<Item = A>,
41    b: impl Iterator<Item = B>,
42    equal: C,
43    tie: C,
44    mut cmp: impl FnMut(A, B) -> C,
45) -> C
46where
47    C: PartialEq,
48{
49    for (x, y) in a.zip(b) {
50        let result = cmp(x, y);
51        if result != equal {
52            return result;
53        }
54    }
55    tie
56}
57
58/// Elementwise [`Value::eq_non_null`] over two same-length sequences — the
59/// one list/vector element comparison in [`Value::eq_non_null`]. `depth` is
60/// the container level of the elements; the ADR-0462 guard caps the walk.
61fn elementwise_eq(a: &[Value], b: &[Value], depth: u32) -> bool {
62    a.len() == b.len()
63        && a.iter()
64            .zip(b.iter())
65            .all(|(x, y)| x.eq_non_null_at(y, depth))
66}
67
68/// The map half of [`Value::compare`]: size first, then the sorted key lists
69/// element by element, then the values under those keys. Both operands are
70/// `BTreeMap`s, so iteration is already key order and equal lengths plus
71/// equal key lists mean the same key set.
72fn compare_maps(
73    a: &std::collections::BTreeMap<String, Value>,
74    b: &std::collections::BTreeMap<String, Value>,
75    depth: u32,
76) -> Option<Ordering> {
77    match a.len().cmp(&b.len()) {
78        Ordering::Equal => {}
79        other => return Some(other),
80    }
81    let by_key = lexicographic(
82        a.keys(),
83        b.keys(),
84        Ordering::Equal,
85        Ordering::Equal,
86        |ka: &String, kb: &String| ka.cmp(kb),
87    );
88    if by_key != Ordering::Equal {
89        return Some(by_key);
90    }
91    lexicographic(
92        a.values(),
93        b.values(),
94        Some(Ordering::Equal),
95        Some(Ordering::Equal),
96        |x, y| x.compare_at(y, depth),
97    )
98}
99
100impl Value {
101    /// Cypher equality: numbers compare across int/float; null = x is null.
102    /// Lists and maps are three-valued: any `false` pair yields false; otherwise
103    /// any `null` pair yields null.
104    pub fn cypher_eq(&self, other: &Value) -> Value {
105        self.cypher_eq_at(other, 0)
106    }
107
108    /// [`Value::cypher_eq`] with the ADR-0462 depth guard threaded through
109    /// the container arms: a comparison past [`MAX_VALUE_DEPTH`] levels
110    /// answers `false` instead of recursing, consistent with the sibling
111    /// comparison walkers. Unreachable behind the checked constructors.
112    fn cypher_eq_at(&self, other: &Value, depth: u32) -> Value {
113        if self.is_null() || other.is_null() {
114            return Value::Null;
115        }
116        match (self, other) {
117            (Value::List(a), Value::List(b)) if descends(depth) => {
118                if a.len() != b.len() {
119                    return Value::Bool(false);
120                }
121                cypher_eq_pairs(a.iter().zip(b.iter()), depth + 1)
122            }
123            (Value::Map(a), Value::Map(b)) if descends(depth) => {
124                if a.len() != b.len() || a.keys().any(|k| !b.contains_key(k)) {
125                    return Value::Bool(false);
126                }
127                cypher_eq_pairs(
128                    a.iter().map(|(k, v)| (v, b.get(k).expect("key checked"))),
129                    depth + 1,
130                )
131            }
132            // Over-depth containers saturate instead of recursing.
133            (Value::List(_), Value::List(_)) | (Value::Map(_), Value::Map(_)) => Value::Bool(false),
134            // Everything else — including a Vector pair at over-cap depth —
135            // inherits the accumulated budget rather than restarting at 0.
136            _ => Value::Bool(self.eq_non_null_at(other, depth)),
137        }
138    }
139
140    pub fn eq_non_null(&self, other: &Value) -> bool {
141        self.eq_non_null_at(other, 0)
142    }
143
144    /// [`Value::eq_non_null`] with the ADR-0462 depth guard threaded through
145    /// the container arms: a comparison past [`MAX_VALUE_DEPTH`] levels
146    /// answers `false` instead of recursing. Unreachable behind the checked
147    /// constructors — the arms that descend only run at a legal depth.
148    fn eq_non_null_at(&self, other: &Value, depth: u32) -> bool {
149        match (self, other) {
150            (Value::Bool(a), Value::Bool(b)) => a == b,
151            (Value::Int(a), Value::Int(b)) => a == b,
152            (Value::Float(a), Value::Float(b)) => a == b,
153            // Exact Int-vs-Float equality: a plain `(a as f64) == b` cast
154            // rounds away low bits for `|a| > 2^53`, so `9007199254740993`
155            // spuriously equaled `9007199254740992.0` here while the exact
156            // equivalence keys (DISTINCT/GROUP BY/property index) did not --
157            // an index's presence could change a MATCH/MERGE answer.
158            (Value::Int(a), Value::Float(b)) => relate_model::canonical_key::eq_i64_f64(*a, *b),
159            (Value::Float(a), Value::Int(b)) => relate_model::canonical_key::eq_i64_f64(*b, *a),
160            (Value::String(a), Value::String(b)) => a == b,
161            (Value::Bytes(a), Value::Bytes(b)) => a == b,
162            (Value::Uuid(a), Value::Uuid(b)) => a == b,
163            (Value::List(a), Value::List(b)) if descends(depth) => elementwise_eq(a, b, depth + 1),
164            (Value::Map(a), Value::Map(b)) if descends(depth) => {
165                a.len() == b.len()
166                    && a.iter()
167                        .all(|(k, v)| b.get(k).is_some_and(|o| v.eq_non_null_at(o, depth + 1)))
168            }
169            (Value::Node(a), Value::Node(b)) => a.id == b.id,
170            (Value::Relationship(a), Value::Relationship(b)) => a.id == b.id,
171            (Value::Path(a), Value::Path(b)) => a == b,
172            // The spec's temporal equality is offset/zone-sensitive and is
173            // *not* `compare() == Equal`: a DST fall-back overlap is equal
174            // (`Temporal::equals`) yet ordered.
175            (Value::Temporal(a), Value::Temporal(b)) => a.equals(b),
176            (Value::Point(a), Value::Point(b)) => a == b,
177            (
178                Value::Vector {
179                    coord: ac,
180                    values: av,
181                },
182                Value::Vector {
183                    coord: bc,
184                    values: bv,
185                },
186            ) if descends(depth) => {
187                // Elementwise-exact, like the List arm: a derived `av == bv`
188                // is variant-strict (`Int(1)` vs `Float(1.0)` differs), which
189                // disagreed with the equivalence keys' numeric normalization
190                // of vector elements.
191                ac == bc && elementwise_eq(av, bv, depth + 1)
192            }
193            _ => false,
194        }
195    }
196
197    /// Cypher's three-valued ordering over one type-pair (`None` = null: the
198    /// pair is incomparable, or a `null` operand reached here). Orderable:
199    /// numbers, strings, bytes, booleans, lists, maps, and the temporal kinds
200    /// except durations. Not orderable despite having `=`: UUIDs, points,
201    /// durations, and any cross-type pair — the `<=`/`>=` arms of the
202    /// comparison operators still hold for equal operands (`cmp_bool`).
203    pub fn compare(&self, other: &Value) -> Option<Ordering> {
204        self.compare_at(other, 0)
205    }
206
207    /// [`Value::compare`] with the ADR-0462 depth guard threaded through the
208    /// container arms: a comparison past [`MAX_VALUE_DEPTH`] levels answers
209    /// `None` (incomparable) instead of recursing.
210    fn compare_at(&self, other: &Value, depth: u32) -> Option<Ordering> {
211        if self.is_null() || other.is_null() {
212            return None;
213        }
214        match (self, other) {
215            (Value::Int(a), Value::Int(b)) => Some(a.cmp(b)),
216            (Value::Float(a), Value::Float(b)) => a.partial_cmp(b),
217            // Exact Int-vs-Float ordering, consistent with the equality above
218            // (both route through `relate_model::canonical_key`), so `<`/
219            // `ORDER BY` and `=` never disagree past `2^53`.
220            (Value::Int(a), Value::Float(b)) => relate_model::canonical_key::cmp_i64_f64(*a, *b),
221            (Value::Float(a), Value::Int(b)) => {
222                relate_model::canonical_key::cmp_i64_f64(*b, *a).map(Ordering::reverse)
223            }
224            (Value::String(a), Value::String(b)) => Some(a.cmp(b)),
225            // Byte-wise, like the List arm: element by element, then length.
226            (Value::Bytes(a), Value::Bytes(b)) => Some(a.cmp(b)),
227            (Value::Bool(a), Value::Bool(b)) => Some(a.cmp(b)),
228            // CIP-246: UUIDs are NOT ordered by the comparison operators --
229            // only equality is defined, so a distinct pair is incomparable
230            // (NULL for `<`/`>`), while an equal pair still yields `Equal`
231            // and so `>=`/`<=` are true (`UUID(x) >= UUID(x)` is true). The
232            // numeric order lives in `order_by_cmp` (UUID ranks between
233            // BOOLEAN and TEMPORAL), so ORDER BY / min / max still sort.
234            (Value::Uuid(a), Value::Uuid(b)) => (*a == *b).then_some(Ordering::Equal),
235            (Value::Temporal(a), Value::Temporal(b)) => a.compare(b),
236            (Value::List(a), Value::List(b)) if descends(depth) => lexicographic(
237                a.iter(),
238                b.iter(),
239                Some(Ordering::Equal),
240                Some(a.len().cmp(&b.len())),
241                |x, y| x.compare_at(y, depth + 1),
242            ),
243            // Maps have a total order: size, then the sorted keys, then the
244            // values under them. A null value makes the comparison null
245            // while a differing key decides the order on its own, which is
246            // why `{k1: 42} < {k2: null}` is true but `{k: 42} < {k: null}`
247            // is null.
248            (Value::Map(a), Value::Map(b)) if descends(depth) => compare_maps(a, b, depth + 1),
249            // Everything left has no ordering arm: UUIDs and points (only `=`
250            // is defined for them — `ORDER BY` still ranks them, see
251            // `order_by_cmp`), paths, entities, and every cross-type pair.
252            _ => None,
253        }
254    }
255
256    /// Total order for ORDER BY / min / max. Comparison operators still use
257    /// `compare`, which is three-valued and incomparable across types.
258    pub fn order_by_cmp(&self, other: &Value) -> Ordering {
259        self.order_by_cmp_at(other, 0)
260    }
261
262    /// [`Value::order_by_cmp`] with the ADR-0462 depth guard threaded
263    /// through the container arms: past [`MAX_VALUE_DEPTH`] levels the walk
264    /// answers `Equal` instead of recursing. Unreachable behind the checked
265    /// constructors.
266    fn order_by_cmp_at(&self, other: &Value, depth: u32) -> Ordering {
267        let ra = self.order_type_rank();
268        let rb = other.order_type_rank();
269        if ra != rb {
270            return ra.cmp(&rb);
271        }
272        match (self, other) {
273            (Value::Null, Value::Null) => Ordering::Equal,
274            // Not orderable by `compare` (no comparison operators), but
275            // ORDER BY / min / max still rank them.
276            (Value::Uuid(a), Value::Uuid(b)) => a.cmp(b),
277            (Value::Temporal(a), Value::Temporal(b)) => a.total_cmp(b),
278            (Value::List(a), Value::List(b)) if descends(depth) => lexicographic(
279                a.iter(),
280                b.iter(),
281                Ordering::Equal,
282                a.len().cmp(&b.len()),
283                |x, y| x.order_by_cmp_at(y, depth + 1),
284            ),
285            (
286                Value::Vector {
287                    coord: ac,
288                    values: av,
289                },
290                Value::Vector {
291                    coord: bc,
292                    values: bv,
293                },
294            ) if descends(depth) => {
295                let type_order = ac
296                    .order_rank()
297                    .cmp(&bc.order_rank())
298                    .then_with(|| av.len().cmp(&bv.len()));
299                if type_order != Ordering::Equal {
300                    return type_order;
301                }
302                lexicographic(
303                    av.iter(),
304                    bv.iter(),
305                    Ordering::Equal,
306                    Ordering::Equal,
307                    |x, y| x.order_by_cmp_at(y, depth + 1),
308                )
309            }
310            _ => self.compare_at(other, depth).unwrap_or(Ordering::Equal),
311        }
312    }
313
314    /// OpenCypher ORDER BY type order (ascending):
315    /// MAP < NODE < RELATIONSHIP < LIST < BYTES < PATH < VECTOR < POINT <
316    /// TEMPORAL < STRING < BOOLEAN < UUID < NUMBER < NaN < NULL. A temporal
317    /// sorts after the containers/points and before STRING (CIP-222's
318    /// Neo4j-verified mixed-type max/min/sort: `date('2024-06-01')` is the
319    /// minimum and `true` the maximum of `[date, true, 'hi']`; UUID sits
320    /// between BOOLEAN and NUMBER per the CIP-246 amendment; BYTES, a
321    /// sequence value in Neo4j, directly after LIST, ADR-0327).
322    ///
323    /// The temporal kinds are ordered among themselves — ZONED DATETIME <
324    /// LOCAL DATETIME < DATE < ZONED TIME < LOCAL TIME < DURATION — because
325    /// `Temporal::total_cmp` answers `Equal` across unlike kinds and this
326    /// rank is what keeps them distinct (live Neo4j 2026.10.1: `coll.sort`
327    /// and `ORDER BY` agree on that sequence, independent of the values).
328    /// [`TemporalKind`] is declared in exactly that order, so its
329    /// discriminant is the rank's offset from TEMPORAL's base rank.
330    fn order_type_rank(&self) -> u8 {
331        match self {
332            Value::Map(_) => 0,
333            Value::Node(_) => 1,
334            Value::Relationship(_) => 2,
335            Value::List(_) => 3,
336            Value::Bytes(_) => 4,
337            Value::Path(_) => 5,
338            Value::Vector { .. } => 6,
339            Value::Point(_) => 7,
340            Value::Temporal(t) => 8 + t.kind() as u8,
341            Value::String(_) => 14,
342            Value::Bool(_) => 15,
343            // CIP-246: UUID orders between BOOLEAN and NUMBER (live
344            // Neo4j 2026.09: true < uuid < 1).
345            Value::Uuid(_) => 16,
346            Value::Int(_) => 17,
347            Value::Float(f) if f.is_nan() => 19,
348            Value::Float(_) => 17,
349            Value::Null => 20,
350        }
351    }
352}