Skip to main content

sqlive/
random_scopes.rs

1//! Random live queries and writes over a schema whose joins, views,
2//! subqueries and conditions sqlive narrows by, so a test can check that a
3//! live query runs again whenever a commit changes what it returns. sqlive's
4//! own test runs them over plain tables, and a host's test runs them over the
5//! host's own writes. A seed reproduces a case.
6
7use crate::SqlValue;
8
9/// A small deterministic generator, so a seed reproduces a case.
10pub struct Rng(u64);
11
12impl Rng {
13    /// The generator of `seed`'s case.
14    pub fn seeded(seed: u64) -> Self {
15        Self(seed.wrapping_mul(0x9e37_79b9_7f4a_7c15) | 1)
16    }
17
18    fn next(&mut self) -> u64 {
19        self.0 ^= self.0 << 13;
20        self.0 ^= self.0 >> 7;
21        self.0 ^= self.0 << 17;
22        self.0
23    }
24
25    /// A number below `bound`.
26    pub fn below(&mut self, bound: usize) -> usize {
27        (self.next() % bound as u64) as usize
28    }
29
30    /// One of `items`.
31    pub fn pick<'a, T>(&mut self, items: &'a [T]) -> &'a T {
32        &items[self.below(items.len())]
33    }
34
35    /// True `percent` times in a hundred.
36    pub fn chance(&mut self, percent: usize) -> bool {
37        self.below(100) < percent
38    }
39}
40
41/// Tables keyed by integer, and a captured one keyed by text, with columns
42/// whose small domains make values collide, and text values that name the
43/// captured table's keys, so joins find rows.
44pub const SCHEMA: &str = "CREATE TABLE t(id INTEGER PRIMARY KEY, a INTEGER, b TEXT, c INTEGER);
45CREATE TABLE u(id INTEGER PRIMARY KEY, a INTEGER, b TEXT, c INTEGER, n TEXT COLLATE NOCASE);
46CREATE TABLE s(id TEXT NOT NULL PRIMARY KEY, a INTEGER, b TEXT, c INTEGER);
47CREATE VIEW tv AS SELECT id, a, b, c FROM t;
48CREATE VIEW tu AS SELECT t.id, t.a, u.b, u.c FROM t JOIN u ON u.a = t.id;
49CREATE VIEW tuv AS SELECT id, a, b, c FROM t UNION ALL SELECT * FROM (SELECT id, a, b, c FROM u);
50CREATE VIEW grouped AS SELECT a AS id, count(*) AS a, b, min(c) AS c FROM t GROUP BY a;
51CREATE VIEW lefty AS SELECT u.id, u.a, t.b, t.c FROM u LEFT JOIN t ON t.id = u.c;
52CREATE VIEW sv(id, a, b, c) AS SELECT s.id, s.a, s.b, s.c FROM s WHERE s.c < 8;
53CREATE INDEX u_a ON u(a);
54CREATE INDEX s_b ON s(b);";
55
56/// Views of the generated tables, each with the columns id, a, b and c, and
57/// the table whose ids theirs are.
58const VIEWS: [(&str, &str); 6] =
59    [("tv", "t"), ("tu", "t"), ("tuv", "t"), ("grouped", "t"), ("lefty", "u"), ("sv", "s")];
60
61/// The generated tables.
62pub const TABLES: [&str; 3] = ["t", "u", "s"];
63
64/// The table keyed by text, which a host captures, or syncs.
65pub const CAPTURED: &str = "s";
66
67/// The key `id` of a row of `table`, as SQL.
68pub fn key(table: &str, id: usize) -> String {
69    if table == CAPTURED {
70        format!("'k{id}'")
71    } else {
72        id.to_string()
73    }
74}
75
76/// A value of the column `a`, as SQL.
77pub fn a_value(rng: &mut Rng) -> String {
78    (*rng.pick(&["NULL", "0", "1", "2", "3", "4"])).to_owned()
79}
80
81/// A value of the column `b`, as SQL.
82pub fn b_value(rng: &mut Rng) -> String {
83    (*rng.pick(&["NULL", "'x'", "'k1'", "'k2'", "'k3'", "'1'"])).to_owned()
84}
85
86/// One generated live query.
87pub struct Generated {
88    /// Its SQL.
89    pub sql: String,
90    /// The values it binds.
91    pub parameters: Vec<SqlValue>,
92    /// Whether its WHERE holds a condition sqlive narrows by.
93    pub narrows: bool,
94    /// What it reads from: one of [`SHAPES`].
95    pub shape: &'static str,
96}
97
98/// The kinds of source a generated query reads from, which a test holds a
99/// precision bound for each of.
100pub const SHAPES: [&str; 7] = ["compound", "no from", "table", "view", "derived", "cte", "join"];
101
102/// A bound value of any type, among them ones a column would convert.
103fn any_value(rng: &mut Rng) -> SqlValue {
104    match rng.below(10) {
105        0 => SqlValue::Null,
106        1..=3 => SqlValue::Integer(rng.below(5) as i64),
107        4 => SqlValue::Real(rng.below(5) as f64 + 0.5),
108        5 => SqlValue::Real(rng.below(5) as f64),
109        6..=8 => SqlValue::Text((*rng.pick(&["x", "X", "k*", "*1", "k1", "2", "k?"])).into()),
110        _ => SqlValue::Blob(vec![b'x']),
111    }
112}
113
114/// A condition on one row of `table`, named `name` in the statement, and
115/// whether sqlive can narrow by it.
116fn condition(
117    rng: &mut Rng,
118    table: &str,
119    name: &str,
120    parameters: &mut Vec<SqlValue>,
121    depth: usize,
122) -> (String, bool) {
123    if depth < 2 && rng.chance(30) {
124        let (left, left_narrows) = condition(rng, table, name, parameters, depth + 1);
125        let (right, right_narrows) = condition(rng, table, name, parameters, depth + 1);
126        return if rng.chance(60) {
127            (format!("({left} AND {right})"), left_narrows || right_narrows)
128        } else {
129            (format!("({left} OR {right})"), left_narrows && right_narrows)
130        };
131    }
132    let id = rng.below(10);
133    match rng.below(23) {
134        0 => (format!("{name}.id = {}", key(table, id)), true),
135        1 => (format!("{name}.a = {}", rng.below(5)), true),
136        2 => (format!("{name}.b = {}", b_value(rng)), true),
137        3 => (format!("{name}.c >= {}", rng.below(10)), true),
138        4 => (format!("{name}.a IN ({}, {})", rng.below(5), rng.below(5)), true),
139        5 => {
140            // A parameter, sometimes of a type the column would convert.
141            parameters.push(if rng.chance(70) {
142                SqlValue::Integer(rng.below(5) as i64)
143            } else {
144                SqlValue::Text(rng.below(5).to_string().into_bytes())
145            });
146            let narrows = matches!(parameters.last(), Some(SqlValue::Integer(_)));
147            (format!("{name}.a = ?{}", parameters.len()), narrows)
148        }
149        6 => (format!("{name}.b <> {}", b_value(rng)), true),
150        7 => {
151            let column = *rng.pick(&["a", "b", "c"]);
152            let spelling = *rng.pick(&["IS NULL", "ISNULL"]);
153            (format!("{name}.{column} {spelling}"), true)
154        }
155        11 => {
156            let column = *rng.pick(&["a", "b", "c"]);
157            let spelling = *rng.pick(&["IS NOT NULL", "NOTNULL", "NOT NULL"]);
158            (format!("{name}.{column} {spelling}"), true)
159        }
160        12 => {
161            // A parameter that is NULL, or a value the column may convert.
162            parameters.push(match rng.below(10) {
163                0..=3 => SqlValue::Null,
164                4..=8 => SqlValue::Integer(rng.below(5) as i64),
165                _ => SqlValue::Text(rng.below(5).to_string().into_bytes()),
166            });
167            let narrows = !matches!(parameters.last(), Some(SqlValue::Text(_)));
168            (format!("{name}.a IS ?{}", parameters.len()), narrows)
169        }
170        13 => (format!("{name}.a IS {}", rng.below(5)), true),
171        14 => {
172            let value = b_value(rng);
173            let narrows = value == "NULL";
174            (format!("{name}.b IS NOT {value}"), narrows)
175        }
176        15..=17 => {
177            // The truth of a condition, compared with a value of any type.
178            parameters.push(match rng.below(10) {
179                0..=2 => SqlValue::Null,
180                3..=7 => SqlValue::Integer(rng.below(3) as i64),
181                _ => SqlValue::Text(rng.below(3).to_string().into_bytes()),
182            });
183            let index = parameters.len();
184            let condition = match rng.below(3) {
185                0 => format!("({name}.a IS NULL) = ?{index}"),
186                1 => format!("({name}.b = 'x') < ?{index}"),
187                _ => format!("({name}.c >= 3) IS ?{index}"),
188            };
189            (condition, true)
190        }
191        8 => (format!("abs({name}.c) = {}", rng.below(10)), true),
192        9 => (format!("{name}.b LIKE {}", b_value(rng)), true),
193        18 => {
194            parameters.push(any_value(rng));
195            (format!("lower({name}.b) = ?{}", parameters.len()), true)
196        }
197        19 => {
198            parameters.push(any_value(rng));
199            (format!("{name}.a + 1 > ?{}", parameters.len()), true)
200        }
201        20 => {
202            parameters.push(any_value(rng));
203            parameters.push(any_value(rng));
204            let (first, second) = (parameters.len() - 1, parameters.len());
205            (format!("CASE WHEN {name}.a = ?{first} THEN 0 ELSE 1 END = ?{second}"), true)
206        }
207        21 => {
208            parameters.push(any_value(rng));
209            parameters.push(any_value(rng));
210            let (first, second) = (parameters.len() - 1, parameters.len());
211            (format!("({name}.a, {name}.c) >= (?{first}, ?{second})"), true)
212        }
213        22 => {
214            parameters.push(any_value(rng));
215            (format!("{name}.b GLOB ?{}", parameters.len()), true)
216        }
217        _ => (format!("{name}.c < {}", rng.below(10)), true),
218    }
219}
220
221/// The joins of a generated statement: its FROM clause, the qualifiers it
222/// names, and conditions the joins themselves add to the WHERE.
223fn joins(
224    rng: &mut Rng,
225    parameters: &mut Vec<SqlValue>,
226) -> (String, Vec<(&'static str, &'static str)>) {
227    match rng.below(22) {
228        20 | 21 => {
229            ("u LEFT JOIN t ON t.id = u.c WHERE t.a IS NULL".into(), vec![("u", "u"), ("t", "t")])
230        }
231        14..=16 => (
232            "t JOIN u ON u.a = t.id JOIN s ON s.id = u.b".into(),
233            vec![("t", "t"), ("u", "u"), ("s", "s")],
234        ),
235        17..=19 => (
236            "s JOIN t ON t.b = s.id JOIN u ON u.c = t.id".into(),
237            vec![("s", "s"), ("t", "t"), ("u", "u")],
238        ),
239        12 => ("tv JOIN s ON s.id = tv.b".into(), vec![("t", "tv"), ("s", "s")]),
240        13 => (
241            "s JOIN tuv ON tuv.b = s.id LEFT JOIN lefty ON lefty.c = tuv.id".into(),
242            vec![("s", "s"), ("t", "tuv"), ("u", "lefty")],
243        ),
244        10 => ("t JOIN u ON u.n = t.b".into(), vec![("t", "t"), ("u", "u")]),
245        11 => ("u JOIN t ON t.b = u.n".into(), vec![("u", "u"), ("t", "t")]),
246        0 => ("t JOIN u ON u.a = t.id".into(), vec![("t", "t"), ("u", "u")]),
247        1 => ("u JOIN t ON t.id = u.c".into(), vec![("u", "u"), ("t", "t")]),
248        2 => ("t, s WHERE s.id = t.b".into(), vec![("t", "t"), ("s", "s")]),
249        3 => ("u LEFT JOIN t ON t.id = u.c".into(), vec![("u", "u"), ("t", "t")]),
250        4 => (
251            "s JOIN t ON t.b = s.id LEFT JOIN u ON u.a = t.id AND u.b = 'x'".into(),
252            vec![("s", "s"), ("t", "t"), ("u", "u")],
253        ),
254        5 => {
255            let ids: Vec<String> =
256                (0..1 + rng.below(3)).map(|_| rng.below(10).to_string()).collect();
257            parameters.push(SqlValue::Text(format!("[{}]", ids.join(",")).into_bytes()));
258            (
259                format!("json_each(?{}) AS w JOIN t ON t.id = w.value", parameters.len()),
260                vec![("t", "t")],
261            )
262        }
263        6 => ("t JOIN u ON u.c = t.id + 1".into(), vec![("t", "t"), ("u", "u")]),
264        7 => ("t JOIN u ON t.b = u.a".into(), vec![("t", "t"), ("u", "u")]),
265        8 => (
266            "t, json_each(json_array(t.b, 'k1')) AS w JOIN s ON s.id = w.value".into(),
267            vec![("t", "t"), ("s", "s")],
268        ),
269        _ => ("t a JOIN t b ON b.c = a.c".into(), vec![("t", "a"), ("t", "b")]),
270    }
271}
272
273/// A subquery over a generated table named `name`, with a condition of its
274/// own and, sometimes, equalities with columns of `outer`, the sources
275/// around it, and conditions on those alone, which narrow nothing; `select`
276/// gives what it selects. Also whether its own conditions narrow.
277fn subquery(
278    rng: &mut Rng,
279    name: &str,
280    outer: &[(&str, &str)],
281    select: &str,
282    parameters: &mut Vec<SqlValue>,
283) -> (String, bool) {
284    let table = *rng.pick(&TABLES);
285    let mut conditions = Vec::new();
286    let mut narrows = false;
287    if rng.chance(70) {
288        let (condition, narrowing) = condition(rng, table, name, parameters, 1);
289        narrows = narrowing;
290        conditions.push(condition);
291    }
292    if !outer.is_empty() && rng.chance(80) {
293        let (outer_table, outer_name) = *rng.pick(outer);
294        let (correlation, narrowing) = match rng.below(5) {
295            0 => (format!("{name}.a = {outer_name}.a"), true),
296            1 => (format!("{name}.b = {outer_name}.b"), true),
297            2 if table == "s" => (format!("{name}.id = {outer_name}.b"), true),
298            3 if outer_table == "s" => (format!("{name}.b = {outer_name}.id"), true),
299            3 => (format!("{name}.c = {outer_name}.id + 1"), true),
300            // Columns of different affinities narrow nothing.
301            _ => (format!("{name}.a = {outer_name}.b"), false),
302        };
303        narrows |= narrowing;
304        conditions.push(correlation);
305    }
306    if !outer.is_empty() && rng.chance(25) {
307        let (outer_table, outer_name) = *rng.pick(outer);
308        let (_, other_name) = *rng.pick(outer);
309        conditions.push(if other_name != outer_name && rng.chance(50) {
310            format!("{outer_name}.a = {other_name}.a")
311        } else {
312            condition(rng, outer_table, outer_name, parameters, 1).0
313        });
314    }
315    if rng.chance(20) {
316        // A subquery inside this one, which sees this one's rows too.
317        let inner = format!("{name}{name}");
318        let mut around = outer.to_vec();
319        around.push((table, name));
320        let (nested, _) = subquery(rng, &inner, &around, "1", parameters);
321        conditions.push(format!("EXISTS ({nested})"));
322    }
323    let filter = if conditions.is_empty() {
324        String::new()
325    } else {
326        format!(" WHERE {}", conditions.join(" AND "))
327    };
328    (format!("SELECT {} FROM {table} {name}{filter}", select.replace("{}", name)), narrows)
329}
330
331/// A condition holding a subquery, correlated with `sources`, with the
332/// source it tests alone, or with none.
333fn subquery_condition(
334    rng: &mut Rng,
335    sources: &[(&str, &str)],
336    parameters: &mut Vec<SqlValue>,
337) -> (String, bool) {
338    let (tested_table, name) = *rng.pick(sources);
339    let tested = [(tested_table, name)];
340    let outer = match rng.below(10) {
341        0..=5 => sources,
342        6 | 7 => &tested,
343        _ => &[],
344    };
345    match rng.below(6) {
346        0 => {
347            let (sql, narrows) = subquery(rng, "q", outer, "1", parameters);
348            (format!("EXISTS ({sql})"), narrows)
349        }
350        1 => {
351            let (sql, narrows) = subquery(rng, "q", outer, "1", parameters);
352            (format!("NOT EXISTS ({sql})"), narrows)
353        }
354        2 => {
355            // The subquery's column narrows the tested one.
356            let (sql, _) = subquery(rng, "q", outer, "{}.a", parameters);
357            (format!("{name}.a IN ({sql})"), true)
358        }
359        3 => {
360            let (sql, narrows) = subquery(rng, "q", outer, "count(*)", parameters);
361            (format!("{name}.c >= ({sql})"), narrows)
362        }
363        4 => {
364            let (sql, _) = subquery(rng, "q", outer, "{}.a", parameters);
365            (format!("{name}.a = ({sql} LIMIT 1)"), true)
366        }
367        _ => {
368            let (sql, _) = subquery(rng, "q", outer, "{}.b", parameters);
369            (format!("{name}.b IN ({sql})"), true)
370        }
371    }
372}
373
374/// A live query over the generated tables and views.
375pub fn query(rng: &mut Rng) -> Generated {
376    let mut parameters = Vec::new();
377    match rng.below(10) {
378        0 => {
379            // A compound: each arm narrows by its own condition.
380            let mut arms = Vec::new();
381            let mut narrows = true;
382            for _ in 0..2 {
383                let table = *rng.pick(&TABLES);
384                let (condition, narrowing) = condition(rng, table, "x", &mut parameters, 0);
385                narrows &= narrowing;
386                arms.push(format!("SELECT x.id, x.a FROM {table} x WHERE {condition}"));
387            }
388            let operator = *rng.pick(&["UNION", "UNION ALL", "EXCEPT", "INTERSECT"]);
389            return Generated {
390                sql: format!("{} {operator} {} ORDER BY 1, 2", arms[0], arms[1]),
391                parameters,
392                narrows,
393                shape: "compound",
394            };
395        }
396        1 => {
397            // No FROM: only what its subqueries read.
398            let (exists, narrows) = subquery(rng, "q", &[], "1", &mut parameters);
399            let (count, _) = subquery(rng, "p", &[], "count(*)", &mut parameters);
400            return Generated {
401                sql: format!("SELECT EXISTS ({exists}), ({count})"),
402                parameters,
403                narrows,
404                shape: "no from",
405            };
406        }
407        _ => {}
408    }
409    let mut with = String::new();
410    let mut shape = "join";
411    let (from, sources) = match rng.below(10) {
412        0..=3 => {
413            shape = "table";
414            let table = *rng.pick(&TABLES);
415            (table.to_owned(), vec![(table, table)])
416        }
417        4 | 5 => {
418            shape = "view";
419            let (view, table) = *rng.pick(&VIEWS);
420            (view.to_owned(), vec![(table, view)])
421        }
422        6 => {
423            // A subquery in FROM, with a condition of its own.
424            shape = "derived";
425            let table = *rng.pick(&TABLES);
426            let (condition, _) = condition(rng, table, "x", &mut parameters, 1);
427            (
428                format!("(SELECT x.id, x.a, x.b, x.c FROM {table} x WHERE {condition}) AS d"),
429                vec![(table, "d")],
430            )
431        }
432        7 => {
433            // A CTE, sometimes kept apart as SQLite reads it.
434            shape = "cte";
435            let table = *rng.pick(&TABLES);
436            let materialized = *rng.pick(&["", "MATERIALIZED "]);
437            with = format!("WITH d AS {materialized}(SELECT * FROM {table}) ");
438            ("d".to_owned(), vec![(table, "d")])
439        }
440        _ => joins(rng, &mut parameters),
441    };
442    let mut narrows = false;
443    let mut conditions = Vec::new();
444    if rng.chance(85) {
445        let (table, name) = *rng.pick(&sources);
446        let (condition, narrowing) = condition(rng, table, name, &mut parameters, 0);
447        narrows = narrowing;
448        conditions.push(condition);
449    }
450    if rng.chance(35) {
451        let (condition, narrowing) = subquery_condition(rng, &sources, &mut parameters);
452        narrows |= narrowing;
453        conditions.push(condition);
454    }
455    // A join of the form `t, s WHERE …` brings its own WHERE.
456    let joined = !from.starts_with('(') && from.contains(" WHERE ");
457    let filter = match (joined, conditions.is_empty()) {
458        (_, true) => String::new(),
459        (true, false) => format!(" AND {}", conditions.join(" AND ")),
460        (false, false) => format!(" WHERE {}", conditions.join(" AND ")),
461    };
462    let (_, last) = sources[sources.len() - 1];
463    let (_, first) = sources[0];
464    let sql = match rng.below(8) {
465        0 => format!("SELECT count(*) FROM {from}{filter}"),
466        1 => format!("SELECT sum({last}.c), count({first}.b) FROM {from}{filter}"),
467        2 => format!(
468            "SELECT {first}.a, count(*) FROM {from}{filter} GROUP BY {first}.a ORDER BY 1"
469        ),
470        3 => format!(
471            "SELECT {first}.id, {last}.b FROM {from}{filter} ORDER BY {first}.c, 1, 2 LIMIT {}",
472            1 + rng.below(3)
473        ),
474        4 => {
475            let (sql, _) = subquery(rng, "q", &sources, "max({}.c)", &mut parameters);
476            format!("SELECT {first}.id, ({sql}) FROM {from}{filter} ORDER BY 1, 2")
477        }
478        5 => {
479            // Sorted by one source's columns with a LIMIT, so a full run's
480            // last row can bound that source: a table, a LEFT JOIN's right
481            // side, a subquery, a CTE or a view.
482            let (_, sorted) = *rng.pick(&sources);
483            let direction = *rng.pick(&["", " DESC"]);
484            format!(
485                "SELECT {sorted}.c, {sorted}.id, {first}.id, {last}.id, {last}.b FROM {from}{filter} ORDER BY {sorted}.c{direction}, {sorted}.id, {first}.id, {last}.id LIMIT {}",
486                1 + rng.below(3)
487            )
488        }
489        _ => format!(
490            "SELECT {first}.id, {first}.a, {last}.id, {last}.b, {last}.c FROM {from}{filter} ORDER BY 1, 2, 3, 4, 5"
491        ),
492    };
493    Generated { sql: format!("{with}{sql}"), parameters, narrows, shape }
494}
495
496/// One generated write.
497pub struct Write {
498    /// Its statements, one after another.
499    pub sql: String,
500    /// Whether a statement changes [`CAPTURED`].
501    pub captured: bool,
502}
503
504/// A write of one to three statements.
505pub fn write(rng: &mut Rng) -> Write {
506    let mut statements = Vec::new();
507    let mut captured = false;
508    for _ in 0..1 + rng.below(3) {
509        // Each statement its own table, so one write can change a joined
510        // table and its partners together.
511        let table = *rng.pick(&TABLES);
512        captured |= table == CAPTURED;
513        let id = key(table, rng.below(10));
514        statements.push(match rng.below(8) {
515            // Text that a NOCASE comparison folds together.
516            7 if table == "u" => format!(
517                "UPDATE u SET n = {} WHERE id = {id}",
518                rng.pick(&["NULL", "'x'", "'X'", "'k1'", "'K1'", "'k2'"])
519            ),
520            0 | 1 => format!(
521                "INSERT OR IGNORE INTO {table}(id, a, b, c) VALUES ({id}, {}, {}, {})",
522                a_value(rng),
523                b_value(rng),
524                rng.below(10)
525            ),
526            2 => format!("UPDATE {table} SET a = {} WHERE id = {id}", a_value(rng)),
527            3 => format!("UPDATE {table} SET b = {}, c = c + 1 WHERE id = {id}", b_value(rng)),
528            4 => format!("UPDATE {table} SET c = {} WHERE a = {}", rng.below(10), rng.below(5)),
529            5 if table != CAPTURED => {
530                format!("UPDATE OR IGNORE {table} SET id = {} WHERE id = {id}", rng.below(10))
531            }
532            _ => format!("DELETE FROM {table} WHERE id = {id}"),
533        });
534    }
535    Write { sql: statements.join("; "), captured }
536}