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

hidane_core/
order.rs
