hidane_core/
order.rs

1//! Firestore value ordering.
2//!
3//! Values of different types sort by type, in this order (documented in
4//! <https://firebase.google.com/docs/firestore/manage-data/data-types#value_type_ordering> and
5//! confirmed on the official emulator):
6//!
7//! null < booleans < NaN < numbers < timestamps < strings < bytes < references < geo points
8//! < arrays < vectors < maps
9//!
10//! On an enterprise database the BSON types ([`crate::bson`]) take their places in it: min
11//! keys after null, 32-bit integers and 128-bit decimals among the numbers (by exact value),
12//! BSON timestamps after timestamps, binary data among the bytes (plain bytes being subtype 0:
13//! by subtype, then the data), object IDs after references, regular expressions after geo
14//! points (by pattern, then options), max keys after maps
15//! (`tests/fixtures/bson_types.json`).
16//!
17//! Within a type:
18//!
19//! - numbers compare by exact numeric value, integers and doubles mixed: `1 == 1.0`,
20//!   `-0.0 == 0`, `2^53 + 1 > 2^53 as double`, `i64::MIN == -2^63 as double`; every NaN is
21//!   equal to every other NaN;
22//! - strings and map keys compare by UTF-8 bytes (not UTF-16 code units);
23//! - references and document names compare segment by segment; segments of the form
24//!   `__id<i64>__` sort first, numerically, then other segments by UTF-8 bytes;
25//! - arrays compare element by element, then by length;
26//! - vectors (`{__type__: "__vector__", value: [...]}`) compare by length, then element by
27//!   element;
28//! - maps compare key, value, key, value, … in key order, then by size.
29
30use std::cmp::Ordering;
31
32use crate::bson::{self, AnyNumber, Bson};
33use hidane_proto::google::{
34    firestore::v1::{ArrayValue, MapValue, Value, value::ValueType},
35    r#type::LatLng,
36};
37use prost_types::Timestamp;
38
39/// Rank of a value's type in the cross-type order. NaN is ranked with numbers; the number
40/// comparison puts it first.
41#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
42pub enum TypeRank {
43    Null,
44    MinKey,
45    Boolean,
46    Number,
47    Timestamp,
48    BsonTimestamp,
49    String,
50    Bytes,
51    Reference,
52    ObjectId,
53    GeoPoint,
54    Regex,
55    Array,
56    Vector,
57    Map,
58    MaxKey,
59    /// Pipeline expressions (field / variable references, functions, pipelines). They are
60    /// never stored, so their position is arbitrary; they compare equal to each other.
61    Expression,
62}
63
64pub(crate) const VECTOR_TYPE_KEY: &str = "__type__";
65pub(crate) const VECTOR_TYPE: &str = "__vector__";
66pub(crate) const VECTOR_VALUES_KEY: &str = "value";
67
68/// Whether a map is the wire form of a vector embedding.
69pub fn is_vector(map: &MapValue) -> bool {
70    matches!(
71        map.fields.get(VECTOR_TYPE_KEY).and_then(|v| v.value_type.as_ref()),
72        Some(ValueType::StringValue(t)) if t == VECTOR_TYPE
73    )
74}
75
76/// The elements of a vector map (empty if malformed).
77pub fn vector_elements(map: &MapValue) -> &[Value] {
78    match map
79        .fields
80        .get(VECTOR_VALUES_KEY)
81        .and_then(|v| v.value_type.as_ref())
82    {
83        Some(ValueType::ArrayValue(array)) => &array.values,
84        _ => &[],
85    }
86}
87
88pub fn type_rank(value: &Value) -> TypeRank {
89    match &value.value_type {
90        None | Some(ValueType::NullValue(_)) => TypeRank::Null,
91        Some(ValueType::BooleanValue(_)) => TypeRank::Boolean,
92        Some(ValueType::IntegerValue(_) | ValueType::DoubleValue(_)) => TypeRank::Number,
93        Some(ValueType::TimestampValue(_)) => TypeRank::Timestamp,
94        Some(ValueType::StringValue(_)) => TypeRank::String,
95        Some(ValueType::BytesValue(_)) => TypeRank::Bytes,
96        Some(ValueType::ReferenceValue(_)) => TypeRank::Reference,
97        Some(ValueType::GeoPointValue(_)) => TypeRank::GeoPoint,
98        Some(ValueType::ArrayValue(_)) => TypeRank::Array,
99        Some(ValueType::MapValue(map)) if is_vector(map) => TypeRank::Vector,
100        Some(ValueType::MapValue(map)) => match bson::bson(map) {
101            None => TypeRank::Map,
102            Some(Bson::MinKey) => TypeRank::MinKey,
103            Some(Bson::MaxKey) => TypeRank::MaxKey,
104            Some(Bson::ObjectId(_)) => TypeRank::ObjectId,
105            Some(Bson::Regex { .. }) => TypeRank::Regex,
106            Some(Bson::Int32(_) | Bson::Decimal128(_)) => TypeRank::Number,
107            Some(Bson::Timestamp { .. }) => TypeRank::BsonTimestamp,
108            Some(Bson::Binary(_)) => TypeRank::Bytes,
109        },
110        Some(
111            ValueType::FieldReferenceValue(_)
112            | ValueType::VariableReferenceValue(_)
113            | ValueType::FunctionValue(_)
114            | ValueType::PipelineValue(_),
115        ) => TypeRank::Expression,
116    }
117}
118
119/// Firestore's total order over values.
120pub fn compare(a: &Value, b: &Value) -> Ordering {
121    let (rank_a, rank_b) = (type_rank(a), type_rank(b));
122    if rank_a != rank_b {
123        return rank_a.cmp(&rank_b);
124    }
125    match (&a.value_type, &b.value_type) {
126        (Some(ValueType::BooleanValue(x)), Some(ValueType::BooleanValue(y))) => x.cmp(y),
127        (Some(ValueType::MapValue(_)), _) | (_, Some(ValueType::MapValue(_)))
128            if rank_a == TypeRank::Number =>
129        {
130            match (AnyNumber::of(a), AnyNumber::of(b)) {
131                (Some(x), Some(y)) => bson::compare_numbers(x, y),
132                _ => Ordering::Equal,
133            }
134        }
135        (Some(x), Some(y)) if rank_a == TypeRank::Number => compare_numbers(x, y),
136        (Some(ValueType::BytesValue(x)), Some(ValueType::BytesValue(y))) => x.cmp(y),
137        _ if rank_a == TypeRank::Bytes => bson::compare_bytes(subtyped(a), subtyped(b)),
138        _ if matches!(
139            rank_a,
140            TypeRank::ObjectId | TypeRank::Regex | TypeRank::BsonTimestamp
141        ) =>
142        {
143            match (bson::of(a), bson::of(b)) {
144                (Some(Bson::ObjectId(x)), Some(Bson::ObjectId(y))) => x.cmp(y),
145                (
146                    Some(Bson::Regex {
147                        pattern: p,
148                        options: o,
149                    }),
150                    Some(Bson::Regex {
151                        pattern: q,
152                        options: r,
153                    }),
154                ) => p.cmp(q).then_with(|| o.cmp(r)),
155                (
156                    Some(Bson::Timestamp {
157                        seconds: s,
158                        increment: i,
159                    }),
160                    Some(Bson::Timestamp {
161                        seconds: t,
162                        increment: j,
163                    }),
164                ) => (s, i).cmp(&(t, j)),
165                _ => Ordering::Equal,
166            }
167        }
168        (Some(ValueType::TimestampValue(x)), Some(ValueType::TimestampValue(y))) => {
169            compare_timestamps(x, y)
170        }
171        (Some(ValueType::StringValue(x)), Some(ValueType::StringValue(y))) => x.cmp(y),
172        (Some(ValueType::ReferenceValue(x)), Some(ValueType::ReferenceValue(y))) => {
173            compare_paths(x.split('/'), y.split('/'))
174        }
175        (Some(ValueType::GeoPointValue(x)), Some(ValueType::GeoPointValue(y))) => {
176            compare_geo_points(x, y)
177        }
178        (Some(ValueType::ArrayValue(x)), Some(ValueType::ArrayValue(y))) => compare_arrays(x, y),
179        (Some(ValueType::MapValue(x)), Some(ValueType::MapValue(y)))
180            if rank_a == TypeRank::Vector =>
181        {
182            compare_vectors(x, y)
183        }
184        (Some(ValueType::MapValue(x)), Some(ValueType::MapValue(y))) if rank_a == TypeRank::Map => {
185            compare_maps(x, y)
186        }
187        // Null, min and max keys and expressions: equal within their rank.
188        _ => Ordering::Equal,
189    }
190}
191
192/// Bytes, or binary data, as a subtype and the data: plain bytes are subtype 0.
193fn subtyped(value: &Value) -> (u8, &[u8]) {
194    match &value.value_type {
195        Some(ValueType::BytesValue(b)) => (0, b),
196        _ => match bson::of(value) {
197            Some(Bson::Binary(b)) => b.split_first().map_or((0, &[][..]), |(s, d)| (*s, d)),
198            _ => (0, &[]),
199        },
200    }
201}
202
203/// A number as Firestore sees it.
204#[derive(Debug, Clone, Copy)]
205pub enum Number {
206    Integer(i64),
207    Double(f64),
208}
209
210impl Number {
211    pub fn of(value: &ValueType) -> Option<Self> {
212        match value {
213            ValueType::IntegerValue(i) => Some(Self::Integer(*i)),
214            ValueType::DoubleValue(d) => Some(Self::Double(*d)),
215            _ => None,
216        }
217    }
218}
219
220fn compare_numbers(a: &ValueType, b: &ValueType) -> Ordering {
221    match (Number::of(a), Number::of(b)) {
222        (Some(a), Some(b)) => compare_number(a, b),
223        _ => Ordering::Equal,
224    }
225}
226
227pub fn compare_number(a: Number, b: Number) -> Ordering {
228    match (a, b) {
229        (Number::Integer(x), Number::Integer(y)) => x.cmp(&y),
230        (Number::Double(x), Number::Double(y)) => compare_doubles(x, y),
231        (Number::Integer(x), Number::Double(y)) => compare_integer_double(x, y),
232        (Number::Double(x), Number::Integer(y)) => compare_integer_double(y, x).reverse(),
233    }
234}
235
236/// NaN first (all NaN equal), then numeric order with `-0.0 == 0.0`.
237pub fn compare_doubles(a: f64, b: f64) -> Ordering {
238    match (a.is_nan(), b.is_nan()) {
239        (true, true) => Ordering::Equal,
240        (true, false) => Ordering::Less,
241        (false, true) => Ordering::Greater,
242        (false, false) => a.partial_cmp(&b).unwrap_or(Ordering::Equal),
243    }
244}
245
246/// Exact comparison of an `i64` with an `f64`, with no rounding of either side.
247pub fn compare_integer_double(i: i64, d: f64) -> Ordering {
248    const TWO_POW_63: f64 = 9_223_372_036_854_775_808.0;
249    if d.is_nan() {
250        return Ordering::Greater;
251    }
252    if d >= TWO_POW_63 {
253        return Ordering::Less;
254    }
255    if d < -TWO_POW_63 {
256        return Ordering::Greater;
257    }
258    // -2^63 <= d < 2^63, so its integer part fits in an i64 exactly.
259    let whole = d.trunc();
260    #[allow(clippy::cast_possible_truncation)]
261    let whole_int = whole as i64;
262    i.cmp(&whole_int).then_with(|| {
263        let fraction = d - whole;
264        if fraction > 0.0 {
265            Ordering::Less
266        } else if fraction < 0.0 {
267            Ordering::Greater
268        } else {
269            Ordering::Equal
270        }
271    })
272}
273
274pub fn compare_timestamps(a: &Timestamp, b: &Timestamp) -> Ordering {
275    (a.seconds, a.nanos).cmp(&(b.seconds, b.nanos))
276}
277
278fn compare_geo_points(a: &LatLng, b: &LatLng) -> Ordering {
279    compare_doubles(a.latitude, b.latitude).then_with(|| compare_doubles(a.longitude, b.longitude))
280}
281
282fn compare_arrays(a: &ArrayValue, b: &ArrayValue) -> Ordering {
283    compare_sequences(&a.values, &b.values)
284}
285
286fn compare_sequences(a: &[Value], b: &[Value]) -> Ordering {
287    a.iter()
288        .zip(b)
289        .map(|(x, y)| compare(x, y))
290        .find(|o| o.is_ne())
291        .unwrap_or_else(|| a.len().cmp(&b.len()))
292}
293
294fn compare_vectors(a: &MapValue, b: &MapValue) -> Ordering {
295    let (x, y) = (vector_elements(a), vector_elements(b));
296    x.len().cmp(&y.len()).then_with(|| compare_sequences(x, y))
297}
298
299fn compare_maps(a: &MapValue, b: &MapValue) -> Ordering {
300    // Maps compare in UTF-8 key order, whatever order their fields are held in.
301    a.fields
302        .sorted()
303        .into_iter()
304        .zip(b.fields.sorted())
305        .map(|((ka, va), (kb, vb))| ka.cmp(kb).then_with(|| compare(va, vb)))
306        .find(|o| o.is_ne())
307        .unwrap_or_else(|| a.fields.len().cmp(&b.fields.len()))
308}
309
310/// A segment of the form `__id<i64>__` (legacy numeric IDs), the number written the one way
311/// Java prints it: no `+`, no leading zero, no `-0`. The official emulator rejects other
312/// strings that start with `__id` and end with `__` (and `__id0__`, see `names`).
313pub fn numeric_id(segment: &str) -> Option<i64> {
314    let digits = segment.strip_prefix("__id")?.strip_suffix("__")?;
315    let magnitude = digits.strip_prefix('-').unwrap_or(digits);
316    let canonical = match magnitude.as_bytes() {
317        [b'0'] => magnitude.len() == digits.len(),
318        [] | [b'0', ..] => false,
319        bytes => bytes.iter().all(u8::is_ascii_digit),
320    };
321    if canonical { digits.parse().ok() } else { None }
322}
323
324/// Numeric IDs first (numerically), then other segments by UTF-8 bytes.
325pub fn compare_segments(a: &str, b: &str) -> Ordering {
326    match (numeric_id(a), numeric_id(b)) {
327        (Some(x), Some(y)) => x.cmp(&y),
328        (Some(_), None) => Ordering::Less,
329        (None, Some(_)) => Ordering::Greater,
330        (None, None) => a.cmp(b),
331    }
332}
333
334/// Document names and references: segment by segment, then the shorter path first.
335pub fn compare_paths<'a>(
336    a: impl IntoIterator<Item = &'a str>,
337    b: impl IntoIterator<Item = &'a str>,
338) -> Ordering {
339    let (mut a, mut b) = (a.into_iter(), b.into_iter());
340    loop {
341        match (a.next(), b.next()) {
342            (Some(x), Some(y)) => match compare_segments(x, y) {
343                Ordering::Equal => {}
344                other => return other,
345            },
346            (None, None) => return Ordering::Equal,
347            (None, Some(_)) => return Ordering::Less,
348            (Some(_), None) => return Ordering::Greater,
349        }
350    }
351}
352
353#[cfg(test)]
354mod tests {
355    use super::numeric_id;
356
357    #[test]
358    fn numeric_ids_are_written_one_way() {
359        for (segment, expected) in [
360            ("__id5__", Some(5)),
361            ("__id-3__", Some(-3)),
362            ("__id0__", Some(0)),
363            ("__id9223372036854775807__", Some(i64::MAX)),
364            ("__id-9223372036854775808__", Some(i64::MIN)),
365            ("__id-0__", None),
366            ("__id007__", None),
367            ("__id+5__", None),
368            ("__id__", None),
369            ("__id-__", None),
370            ("__id 5__", None),
371            ("__id9223372036854775808__", None),
372            ("id5", None),
373        ] {
374            assert_eq!(numeric_id(segment), expected, "{segment}");
375        }
376    }
377}
hidane_core/order.rs

hidane_core/
order.rs
