Skip to main content

zero_client/hash/
query.rs

1//! Query identities (`packages/zero-protocol/src/query-hash-visitor.ts`).
2//!
3//! The JS implementation folds an AST (or a name and args) into two xxHash32
4//! lanes word by word. These digests are the query IDs the client registers,
5//! so they have to match exactly.
6
7use super::xxhash32::{PRIME1, PRIME5, avalanche, round};
8use crate::ast::*;
9use crate::json::{Value, number};
10use crate::strings;
11
12const TAG_NULL: u32 = 0x1001;
13const TAG_FALSE: u32 = 0x1002;
14const TAG_TRUE: u32 = 0x1003;
15const TAG_INT: u32 = 0x1004;
16const TAG_FLOAT: u32 = 0x1005;
17const TAG_ARR: u32 = 0x1007;
18const TAG_OBJ: u32 = 0x1008;
19const TAG_END: u32 = 0x1009;
20const TAG_UNDEF: u32 = 0x100a;
21
22const TAG_LITERAL: u32 = 0x2001;
23const TAG_COLUMN: u32 = 0x2002;
24const TAG_STATIC: u32 = 0x2003;
25const TAG_SIMPLE: u32 = 0x2004;
26const TAG_SUBQUERY: u32 = 0x2005;
27const TAG_AND: u32 = 0x2006;
28const TAG_OR: u32 = 0x2007;
29const TAG_FORMAT: u32 = 0x2008;
30const TAG_NAME_ARGS: u32 = 0x2009;
31const TAG_SYSTEM_PERMISSIONS: u32 = 0x200a;
32const TAG_SYSTEM_CLIENT: u32 = 0x200b;
33const TAG_SYSTEM_TEST: u32 = 0x200c;
34const TAG_JUNCTION: u32 = 0x200d;
35const TAG_AGGREGATE: u32 = 0x200e;
36const TAG_JSON: u32 = 0x200f;
37const TAG_GROUP_BY: u32 = 0x2010;
38const TAG_DISTINCT: u32 = 0x2011;
39
40const STR_MARK: u32 = 0x4000_0000;
41
42/// `hashOfAST`: the hash of `ast` after normalizing it.
43pub fn hash_of_ast(ast: &Ast) -> String {
44    hash_of_normalized_ast(&ast.normalized())
45}
46
47/// The hash of an AST that is already normalized.
48pub fn hash_of_normalized_ast(ast: &Ast) -> String {
49    let mut s = State::new();
50    s.ast(ast);
51    s.finish()
52}
53
54/// `hashOfNameAndArgs`: the identity of a named (custom) query.
55pub fn hash_of_name_and_args(name: &str, args: &[Value]) -> String {
56    let mut s = State::new();
57    s.mix(TAG_NAME_ARGS);
58    s.string(name);
59    s.array(args);
60    s.finish()
61}
62
63/// `hashOfQueryInternals`: the identity of a query as the client sees it.
64pub fn hash_of_query_internals(
65    ast: &Ast,
66    format: &Value,
67    system: System,
68    current_junction: Option<&str>,
69    custom_query: Option<(&str, Option<&[Value]>)>,
70) -> String {
71    let mut s = State::new();
72    s.ast(ast);
73    s.mix(TAG_FORMAT);
74    s.value(format);
75    s.system(system);
76    match current_junction {
77        Some(j) => {
78            s.mix(TAG_JUNCTION);
79            s.string(j);
80        }
81        None => s.mix(TAG_UNDEF),
82    }
83    match custom_query {
84        Some((name, args)) => {
85            s.mix(TAG_NAME_ARGS);
86            s.string(name);
87            if let Some(args) = args {
88                s.array(args);
89            }
90        }
91        None => s.mix(TAG_UNDEF),
92    }
93    s.finish()
94}
95
96struct State {
97    h1: u32,
98    h2: u32,
99}
100
101impl State {
102    fn new() -> Self {
103        State {
104            h1: PRIME5,
105            h2: PRIME1,
106        }
107    }
108
109    fn mix(&mut self, w: u32) {
110        self.h1 = round(self.h1, w);
111        self.h2 = round(self.h2, w);
112    }
113
114    /// A JS number's `| 0`, for counts and lengths.
115    fn count(&mut self, n: usize) {
116        self.mix(n as u32);
117    }
118
119    fn string(&mut self, s: &str) {
120        let units: Vec<u16> = s.encode_utf16().collect();
121        self.mix(units.len() as u32 | STR_MARK);
122        for pair in units.chunks(2) {
123            self.mix(u32::from(pair[0]) | pair.get(1).map_or(0, |&u| u32::from(u) << 16));
124        }
125    }
126
127    fn number(&mut self, n: f64) {
128        if number::is_int32(n) {
129            self.mix(n as i32 as u32);
130        } else {
131            let bits = n.to_bits(); // little-endian words: low first
132            self.mix(bits as u32);
133            self.mix((bits >> 32) as u32);
134        }
135    }
136
137    fn finish(&self) -> String {
138        format!(
139            "{}{}",
140            base36(avalanche(self.h1)),
141            base36(avalanche(self.h2))
142        )
143    }
144
145    fn array(&mut self, a: &[Value]) {
146        self.mix(TAG_ARR);
147        for e in a {
148            self.value(e);
149        }
150        self.mix(TAG_END);
151    }
152
153    fn value(&mut self, v: &Value) {
154        match v {
155            Value::String(s) => self.string(s),
156            // NaN and Infinity are null on the wire (JSON.stringify writes
157            // null).
158            Value::Number(n) if !n.is_finite() => self.mix(TAG_NULL),
159            Value::Number(n) => {
160                self.mix(if number::is_int32(*n) {
161                    TAG_INT
162                } else {
163                    TAG_FLOAT
164                });
165                self.number(*n);
166            }
167            Value::Bool(b) => self.mix(if *b { TAG_TRUE } else { TAG_FALSE }),
168            Value::Null => self.mix(TAG_NULL),
169            Value::Array(a) => self.array(a),
170            Value::Object(o) => {
171                self.mix(TAG_OBJ);
172                // `Object.keys(v).sort()`: by UTF-16 code unit.
173                let mut entries: Vec<_> = o.iter().collect();
174                entries.sort_by(|a, b| strings::utf16(a.0, b.0));
175                for (k, v) in entries {
176                    self.string(k);
177                    self.value(v);
178                }
179                self.mix(TAG_END);
180            }
181        }
182    }
183
184    fn optional_string(&mut self, s: Option<&str>) {
185        match s {
186            Some(s) => self.string(s),
187            None => self.mix(TAG_UNDEF),
188        }
189    }
190
191    fn system(&mut self, system: System) {
192        self.mix(match system {
193            System::Permissions => TAG_SYSTEM_PERMISSIONS,
194            System::Client => TAG_SYSTEM_CLIENT,
195            System::Test => TAG_SYSTEM_TEST,
196        });
197    }
198
199    fn optional_bool(&mut self, b: Option<bool>) {
200        self.mix(match b {
201            None => TAG_UNDEF,
202            Some(true) => TAG_TRUE,
203            Some(false) => TAG_FALSE,
204        });
205    }
206
207    fn compound_key(&mut self, k: &[String]) {
208        self.count(k.len());
209        for s in k {
210            self.string(s);
211        }
212    }
213
214    fn path(&mut self, path: &[JsonPathSegment]) {
215        self.array(
216            &path
217                .iter()
218                .map(JsonPathSegment::to_json)
219                .collect::<Vec<_>>(),
220        );
221    }
222
223    fn value_position(&mut self, v: &ValuePosition) {
224        match v {
225            ValuePosition::Literal(value) => {
226                self.mix(TAG_LITERAL);
227                self.value(value);
228            }
229            ValuePosition::Column(name) => {
230                self.mix(TAG_COLUMN);
231                self.string(name);
232            }
233            // The wrapped column, then the path as a value.
234            ValuePosition::Json { column, path } => {
235                self.mix(TAG_JSON);
236                self.mix(TAG_COLUMN);
237                self.string(column);
238                self.path(path);
239            }
240            ValuePosition::Static { anchor, field } => {
241                self.mix(TAG_STATIC);
242                self.string(anchor.as_str());
243                match field {
244                    StaticField::Single(f) => self.string(f),
245                    StaticField::Path(p) => self.compound_key(p),
246                }
247            }
248        }
249    }
250
251    fn condition(&mut self, c: &Condition) {
252        match c {
253            Condition::Simple { op, left, right } => {
254                self.mix(TAG_SIMPLE);
255                self.string(op.as_str());
256                self.value_position(left);
257                self.value_position(right);
258            }
259            Condition::CorrelatedSubquery {
260                related,
261                op,
262                flip,
263                scalar,
264            } => {
265                self.mix(TAG_SUBQUERY);
266                self.string(op.as_str());
267                self.optional_bool(*flip);
268                self.optional_bool(*scalar);
269                self.correlated_subquery(related);
270            }
271            Condition::And(conditions) | Condition::Or(conditions) => {
272                self.mix(if matches!(c, Condition::And(_)) {
273                    TAG_AND
274                } else {
275                    TAG_OR
276                });
277                self.count(conditions.len());
278                for cond in conditions {
279                    self.condition(cond);
280                }
281            }
282        }
283    }
284
285    fn correlated_subquery(&mut self, csq: &CorrelatedSubquery) {
286        self.compound_key(&csq.correlation.parent_field);
287        self.compound_key(&csq.correlation.child_field);
288        self.optional_bool(csq.hidden);
289        match csq.system {
290            Some(system) => self.system(system),
291            None => self.mix(TAG_UNDEF),
292        }
293        // Before the subquery, so an absent aggregate, which writes nothing,
294        // is never confused with a present one.
295        self.aggregate(csq.aggregate.as_ref());
296        self.ast(&csq.subquery);
297    }
298
299    /// An absent aggregate, path, or distinct writes nothing, so the hashes
300    /// of queries without them are what they were before they existed.
301    fn aggregate(&mut self, aggregate: Option<&Aggregate>) {
302        let Some(a) = aggregate else { return };
303        self.mix(TAG_AGGREGATE);
304        self.string(a.fn_.as_str());
305        self.optional_string(a.field.as_deref());
306        if let Some(path) = &a.path {
307            self.mix(TAG_JSON);
308            self.path(path);
309        }
310        if let Some(distinct) = &a.distinct {
311            self.mix(TAG_DISTINCT);
312            self.compound_key(distinct);
313        }
314    }
315
316    fn ast(&mut self, ast: &Ast) {
317        self.mix(TAG_OBJ);
318        self.optional_string(ast.schema.as_deref());
319        self.string(&ast.table);
320        self.optional_string(ast.alias.as_deref());
321        match &ast.where_ {
322            Some(w) => self.condition(w),
323            None => self.mix(TAG_UNDEF),
324        }
325        match &ast.related {
326            Some(related) => {
327                self.count(related.len());
328                for r in related {
329                    self.correlated_subquery(r);
330                }
331            }
332            None => self.mix(TAG_UNDEF),
333        }
334        match &ast.start {
335            Some(start) => {
336                self.mix(if start.exclusive { TAG_TRUE } else { TAG_FALSE });
337                self.value(&Value::Object(start.row.clone()));
338            }
339            None => self.mix(TAG_UNDEF),
340        }
341        match ast.limit {
342            Some(limit) => {
343                self.mix(TAG_INT);
344                self.number(limit);
345            }
346            None => self.mix(TAG_UNDEF),
347        }
348        match &ast.order_by {
349            Some(o) => {
350                self.count(o.len());
351                for part in o {
352                    self.string(&part.field);
353                    self.mix(if part.direction == Direction::Asc {
354                        TAG_TRUE
355                    } else {
356                        TAG_FALSE
357                    });
358                }
359            }
360            None => self.mix(TAG_UNDEF),
361        }
362        self.aggregate(ast.aggregate.as_ref());
363        if let Some(group_by) = &ast.group_by {
364            self.mix(TAG_GROUP_BY);
365            self.compound_key(group_by);
366        }
367        self.mix(TAG_END);
368    }
369}
370
371/// Base 36, padded to 7 digits.
372fn base36(mut v: u32) -> String {
373    let mut digits = [b'0'; 7];
374    let mut i = 7;
375    while v > 0 {
376        i -= 1;
377        digits[i] = b"0123456789abcdefghijklmnopqrstuvwxyz"[(v % 36) as usize];
378        v /= 36;
379    }
380    String::from_utf8(digits.to_vec()).expect("ASCII")
381}