zero_client/hash/
query.rs1use 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
42pub fn hash_of_ast(ast: &Ast) -> String {
44 hash_of_normalized_ast(&ast.normalized())
45}
46
47pub fn hash_of_normalized_ast(ast: &Ast) -> String {
49 let mut s = State::new();
50 s.ast(ast);
51 s.finish()
52}
53
54pub 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
63pub 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 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(); 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 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 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 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 self.aggregate(csq.aggregate.as_ref());
296 self.ast(&csq.subquery);
297 }
298
299 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
371fn 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}