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}