Skip to main content

zero_client/ast/
normalize.rs

1//! AST normalization (`normalizeAST` in `packages/zero-protocol/src/ast.ts`):
2//! `related` sorted by alias, `where` flattened and sorted. Two ASTs that
3//! describe the same query hash the same once normalized.
4//!
5//! The comparators are ported verbatim, including their asymmetries, since
6//! the sort order decides the hash; [`crate::sort`] reproduces V8's sort.
7
8use super::*;
9use crate::sort;
10use crate::strings::utf8;
11use std::cmp::Ordering;
12
13impl Ast {
14    pub fn normalized(&self) -> Ast {
15        let mut ast = self.clone();
16        ast.where_ = self
17            .where_
18            .as_ref()
19            .map(|w| normalize_condition(&normalize_subqueries(w)));
20        if let Some(related) = &self.related {
21            let mut related: Vec<CorrelatedSubquery> = related
22                .iter()
23                .map(|r| {
24                    let mut r = r.clone();
25                    r.subquery = Box::new(r.subquery.normalized());
26                    r
27                })
28                .collect();
29            if related
30                .windows(2)
31                .any(|w| cmp_related(&w[0], &w[1]).is_gt())
32            {
33                sort::sort(&mut related, cmp_related);
34            }
35            ast.related = Some(related);
36        }
37        ast
38    }
39}
40
41fn normalize_subqueries(cond: &Condition) -> Condition {
42    match cond {
43        Condition::Simple { .. } => cond.clone(),
44        Condition::CorrelatedSubquery {
45            related,
46            op,
47            flip,
48            scalar,
49        } => {
50            let mut related = related.clone();
51            related.subquery = Box::new(related.subquery.normalized());
52            Condition::CorrelatedSubquery {
53                related,
54                op: *op,
55                flip: *flip,
56                scalar: *scalar,
57            }
58        }
59        Condition::And(c) => Condition::And(c.iter().map(normalize_subqueries).collect()),
60        Condition::Or(c) => Condition::Or(c.iter().map(normalize_subqueries).collect()),
61    }
62}
63
64pub fn normalize_condition(cond: &Condition) -> Condition {
65    let (is_and, children) = match cond {
66        Condition::And(c) => (true, c),
67        Condition::Or(c) => (false, c),
68        _ => return cond.clone(),
69    };
70    let mut conditions = Vec::with_capacity(children.len());
71    for c in children {
72        match (is_and, normalize_condition(c)) {
73            (true, Condition::And(nested)) | (false, Condition::Or(nested)) => {
74                conditions.extend(nested)
75            }
76            (_, n) => conditions.push(n),
77        }
78    }
79    // A singleton conjunction is the condition itself. Empty ones are
80    // meaningful: an empty `and` is true and an empty `or` is false.
81    if conditions.len() == 1 {
82        return conditions.pop().expect("one");
83    }
84    sort::sort(&mut conditions, cmp_condition);
85    if is_and {
86        Condition::And(conditions)
87    } else {
88        Condition::Or(conditions)
89    }
90}
91
92fn type_name(c: &Condition) -> &'static str {
93    match c {
94        Condition::Simple { .. } => "simple",
95        Condition::And(_) => "and",
96        Condition::Or(_) => "or",
97        Condition::CorrelatedSubquery { .. } => "correlatedSubquery",
98    }
99}
100
101fn cmp_condition(a: &Condition, b: &Condition) -> Ordering {
102    if let Condition::Simple {
103        op: aop,
104        left: al,
105        right: ar,
106    } = a
107    {
108        let Condition::Simple {
109            op: bop,
110            left: bl,
111            right: br,
112        } = b
113        else {
114            return Ordering::Less;
115        };
116        return compare_value_position(al, bl)
117            .then_with(|| utf8(aop.as_str(), bop.as_str()))
118            .then_with(|| compare_value_position(ar, br));
119    }
120    if matches!(b, Condition::Simple { .. }) {
121        return Ordering::Greater;
122    }
123    if let Condition::CorrelatedSubquery {
124        related: ar,
125        op: aop,
126        flip: af,
127        scalar: asc,
128    } = a
129    {
130        let Condition::CorrelatedSubquery {
131            related: br,
132            op: bop,
133            flip: bf,
134            scalar: bsc,
135        } = b
136        else {
137            return Ordering::Less;
138        };
139        return cmp_related(ar, br)
140            .then_with(|| utf8(aop.as_str(), bop.as_str()))
141            .then_with(|| cmp_optional_bool(*af, *bf))
142            .then_with(|| cmp_optional_bool(*asc, *bsc));
143    }
144    // Asymmetric, as in JS: a subquery and a conjunction each sort before
145    // the other, whichever is on the left.
146    if matches!(b, Condition::CorrelatedSubquery { .. }) {
147        return Ordering::Less;
148    }
149    let t = utf8(type_name(a), type_name(b));
150    if t.is_ne() {
151        return t;
152    }
153    let (ac, bc) = (
154        a.conditions().expect("and/or"),
155        b.conditions().expect("and/or"),
156    );
157    for (l, r) in ac.iter().zip(bc) {
158        let v = cmp_condition(l, r);
159        if v.is_ne() {
160            return v;
161        }
162    }
163    ac.len().cmp(&bc.len())
164}
165
166fn value_position_type(v: &ValuePosition) -> &'static str {
167    match v {
168        ValuePosition::Literal(_) => "literal",
169        ValuePosition::Column(_) => "column",
170        ValuePosition::Json { .. } => "json",
171        ValuePosition::Static { .. } => "static",
172    }
173}
174
175fn compare_value_position(a: &ValuePosition, b: &ValuePosition) -> Ordering {
176    match (a, b) {
177        (ValuePosition::Literal(x), ValuePosition::Literal(y)) => cmp_literal_value(x, y),
178        (ValuePosition::Column(x), ValuePosition::Column(y)) => utf8(x, y),
179        (
180            ValuePosition::Json {
181                column: ac,
182                path: ap,
183            },
184            ValuePosition::Json {
185                column: bc,
186                path: bp,
187            },
188        ) => utf8(ac, bc)
189            .then_with(|| cmp_literal_value(&coding::path_to_json(ap), &coding::path_to_json(bp))),
190        (
191            ValuePosition::Static {
192                anchor: aa,
193                field: af,
194            },
195            ValuePosition::Static {
196                anchor: ba,
197                field: bf,
198            },
199        ) => utf8(aa.as_str(), ba.as_str())
200            .then_with(|| cmp_literal_value(&af.to_json(), &bf.to_json())),
201        _ => utf8(value_position_type(a), value_position_type(b)),
202    }
203}
204
205/// null < boolean < number < string < array.
206fn literal_value_type(v: &Value) -> u8 {
207    match v {
208        Value::Null | Value::Object(_) => 0,
209        Value::Bool(_) => 1,
210        Value::Number(_) => 2,
211        Value::String(_) => 3,
212        Value::Array(_) => 4,
213    }
214}
215
216fn cmp_literal_value(a: &Value, b: &Value) -> Ordering {
217    let t = literal_value_type(a).cmp(&literal_value_type(b));
218    if t.is_ne() {
219        return t;
220    }
221    match (a, b) {
222        (Value::Array(x), Value::Array(y)) => {
223            for (l, r) in x.iter().zip(y) {
224                let v = cmp_literal_value(l, r);
225                if v.is_ne() {
226                    return v;
227                }
228            }
229            x.len().cmp(&y.len())
230        }
231        (Value::String(x), Value::String(y)) => utf8(x, y),
232        (Value::Number(x), Value::Number(y)) => x.partial_cmp(y).unwrap_or(Ordering::Equal),
233        (Value::Bool(x), Value::Bool(y)) => x.cmp(y),
234        _ => Ordering::Equal,
235    }
236}
237
238pub(crate) fn cmp_related(a: &CorrelatedSubquery, b: &CorrelatedSubquery) -> Ordering {
239    utf8(
240        a.subquery.alias.as_deref().unwrap_or(""),
241        b.subquery.alias.as_deref().unwrap_or(""),
242    )
243}
244
245fn cmp_optional_bool(a: Option<bool>, b: Option<bool>) -> Ordering {
246    let n = |v: Option<bool>| match v {
247        None => 0,
248        Some(false) => 1,
249        Some(true) => 2,
250    };
251    n(a).cmp(&n(b))
252}