Skip to main content

h5i_app_pgsql/
lib.rs

1//! The SQL h5i-app runs on PostgreSQL.
2//!
3//! [`compile`] turns an `h5i_app_sql::Stmt` into a [`Query`] over a small SQL
4//! subset ([`Sql`]); [`render`] prints it. Extracted to Lean (`proofs/`): a
5//! compiled statement matches `H5iAppLib.Sql.exec` on the tenant's rows and
6//! leaves other tenants alone.
7//!
8//! Aeneas subset: no `?`, no `String`, no iterator adapters.
9
10use h5i_app_sql::{Stmt, Val};
11
12/// A column type.
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub enum Kind {
15    Int,
16    Bool,
17    Text,
18    Bytes,
19}
20
21/// A column of a tenant table.
22#[derive(Clone, Debug, PartialEq, Eq)]
23pub struct Column {
24    pub name: Vec<u8>,
25    pub kind: Kind,
26    pub nullable: bool,
27}
28
29/// A tenant table: `tenant_id`, then `columns`. Key: `tenant_id` and the first `key_len` columns.
30#[derive(Clone, Debug, PartialEq, Eq)]
31pub struct Table {
32    pub name: Vec<u8>,
33    pub columns: Vec<Column>,
34    pub key_len: u32,
35}
36
37/// A column definition in `CREATE TABLE`.
38#[derive(Clone, Debug, PartialEq, Eq)]
39pub struct ColDef {
40    pub name: Vec<u8>,
41    pub kind: Kind,
42    pub not_null: bool,
43}
44
45/// A `WHERE` condition; `$param` counts from 1.
46#[derive(Clone, Debug, PartialEq, Eq)]
47pub enum Cond {
48    /// `"col" = $param`
49    Eq { col: Vec<u8>, param: u32 },
50    /// `"col" IS NOT DISTINCT FROM $param`
51    Same { col: Vec<u8>, param: u32 },
52}
53
54/// A statement of the subset. Names are printed quoted.
55#[derive(Clone, Debug, PartialEq, Eq)]
56pub enum Sql {
57    /// `CREATE TABLE IF NOT EXISTS "table" ("c" KIND [NOT NULL], ..., PRIMARY KEY ("k", ...))`
58    Create { table: Vec<u8>, cols: Vec<ColDef>, key: Vec<Vec<u8>> },
59    /// `SELECT "c", ... FROM "table" [WHERE cond AND ...] [ORDER BY "o", ...]`
60    Select { table: Vec<u8>, cols: Vec<Vec<u8>>, conds: Vec<Cond>, order: Vec<Vec<u8>> },
61    /// `INSERT ... ON CONFLICT ("k", ...) DO UPDATE SET "u" = EXCLUDED."u", ...` (`DO NOTHING` if `update` is empty)
62    Insert { table: Vec<u8>, cols: Vec<Vec<u8>>, conflict: Vec<Vec<u8>>, update: Vec<Vec<u8>> },
63    /// `DELETE FROM "table" [WHERE cond AND ...]`
64    Delete { table: Vec<u8>, conds: Vec<Cond> },
65}
66
67/// A statement and the values of its parameters, `$1` first.
68#[derive(Clone, Debug, PartialEq, Eq)]
69pub struct Query {
70    pub sql: Sql,
71    pub params: Vec<Val>,
72}
73
74/// `tenant_id`, the first column of every table.
75pub fn tenant_col() -> Vec<u8> {
76    let mut v = Vec::new();
77    push_lit(&mut v, b"tenant_id");
78    v
79}
80
81fn push_lit(out: &mut Vec<u8>, s: &[u8]) {
82    let mut i = 0;
83    while i < s.len() {
84        out.push(s[i]);
85        i += 1;
86    }
87}
88
89/// Quoted, PostgreSQL keeps it as written: nonempty, no NUL, at most 63 bytes.
90fn name_ok(n: &Vec<u8>) -> bool {
91    if n.len() == 0 || n.len() > 63 {
92        return false;
93    }
94    let mut i = 0;
95    while i < n.len() {
96        if n[i] == 0 {
97            return false;
98        }
99        i += 1;
100    }
101    true
102}
103
104/// `names[i]` differs from every later name.
105fn distinct_from(names: &Vec<Vec<u8>>, i: usize) -> bool {
106    let mut j = i + 1;
107    while j < names.len() {
108        if names[i] == names[j] {
109            return false;
110        }
111        j += 1;
112    }
113    true
114}
115
116fn all_distinct(names: &Vec<Vec<u8>>) -> bool {
117    let mut i = 0;
118    while i < names.len() {
119        if !distinct_from(names, i) {
120            return false;
121        }
122        i += 1;
123    }
124    true
125}
126
127fn all_ok(names: &Vec<Vec<u8>>) -> bool {
128    let mut i = 0;
129    while i < names.len() {
130        if !name_ok(&names[i]) {
131            return false;
132        }
133        i += 1;
134    }
135    true
136}
137
138/// Every column's name, `tenant_id` first.
139fn col_names(t: &Table) -> Vec<Vec<u8>> {
140    let mut out = Vec::new();
141    out.push(tenant_col());
142    let mut i = 0;
143    while i < t.columns.len() {
144        out.push(t.columns[i].name.clone());
145        i += 1;
146    }
147    out
148}
149
150/// Starts with `h5i_`, the prefix of the engine's own tables.
151fn reserved(n: &Vec<u8>) -> bool {
152    n.len() >= 4 && n[0] == 104 && n[1] == 53 && n[2] == 105 && n[3] == 95
153}
154
155/// 1..1599 columns (PostgreSQL caps at 1600 with `tenant_id`), distinct good names.
156fn table_ok(t: &Table) -> bool {
157    if !name_ok(&t.name) || reserved(&t.name) || t.columns.len() == 0 || t.columns.len() >= 1600 {
158        return false;
159    }
160    let names = col_names(t);
161    (t.key_len as usize) <= t.columns.len() && all_ok(&names) && all_distinct(&names)
162}
163
164/// Tables well formed with distinct names; no `tenant_id` column, no `h5i_` table.
165pub fn valid(tables: &Vec<Table>) -> bool {
166    let mut names = Vec::new();
167    let mut i = 0;
168    while i < tables.len() {
169        if !table_ok(&tables[i]) {
170            return false;
171        }
172        names.push(tables[i].name.clone());
173        i += 1;
174    }
175    all_distinct(&names)
176}
177
178fn kind_eq(a: Kind, b: Kind) -> bool {
179    match a {
180        Kind::Int => match b {
181            Kind::Int => true,
182            _ => false,
183        },
184        Kind::Bool => match b {
185            Kind::Bool => true,
186            _ => false,
187        },
188        Kind::Text => match b {
189            Kind::Text => true,
190            _ => false,
191        },
192        Kind::Bytes => match b {
193            Kind::Bytes => true,
194            _ => false,
195        },
196    }
197}
198
199/// `v` has type `k` (`NULL` has every type).
200fn has_kind(v: &Val, k: Kind) -> bool {
201    match v {
202        Val::Int(_) => kind_eq(k, Kind::Int),
203        Val::Bool(_) => kind_eq(k, Kind::Bool),
204        Val::Text(_) => kind_eq(k, Kind::Text),
205        Val::Bytes(_) => kind_eq(k, Kind::Bytes),
206        Val::Null => true,
207    }
208}
209
210fn is_null(v: &Val) -> bool {
211    match v {
212        Val::Null => true,
213        _ => false,
214    }
215}
216
217/// Column `i` of `t` may hold `v`; `NULL` only in a nullable non-key column.
218fn fits(t: &Table, i: usize, v: &Val) -> bool {
219    let c = &t.columns[i];
220    has_kind(v, c.kind) && (!is_null(v) || (c.nullable && i >= t.key_len as usize))
221}
222
223/// `CREATE TABLE` for `t`.
224pub fn create(t: &Table) -> Sql {
225    let mut cols = Vec::new();
226    cols.push(ColDef { name: tenant_col(), kind: Kind::Int, not_null: true });
227    let mut key = Vec::new();
228    key.push(tenant_col());
229    let n = t.key_len as usize;
230    let mut i = 0;
231    while i < t.columns.len() {
232        cols.push(ColDef { name: t.columns[i].name.clone(), kind: t.columns[i].kind, not_null: !t.columns[i].nullable || i < n });
233        if i < n {
234            key.push(t.columns[i].name.clone());
235        }
236        i += 1;
237    }
238    Sql::Create { table: t.name.clone(), cols, key }
239}
240
241/// The names of columns `lo..hi`.
242fn names_between(t: &Table, lo: usize, hi: usize) -> Vec<Vec<u8>> {
243    let mut out = Vec::new();
244    let mut i = lo;
245    while i < hi && i < t.columns.len() {
246        out.push(t.columns[i].name.clone());
247        i += 1;
248    }
249    out
250}
251
252/// The tenant's rows of `table` (no `tenant_id`), optionally filtered by
253/// `col IS NOT DISTINCT FROM val`. `None` on a bad schema, table, column, or type.
254pub fn select(tables: &Vec<Table>, tenant: i64, table: u32, filter: Option<(u32, Val)>) -> Option<Query> {
255    if !valid(tables) || table as usize >= tables.len() {
256        return None;
257    }
258    let t = &tables[table as usize];
259    let mut conds = Vec::new();
260    conds.push(Cond::Eq { col: tenant_col(), param: 1 });
261    let mut params = Vec::new();
262    params.push(Val::Int(tenant));
263    match filter {
264        None => {}
265        Some((col, val)) => {
266            let i = col as usize;
267            if i >= t.columns.len() || !has_kind(&val, t.columns[i].kind) {
268                return None;
269            }
270            conds.push(Cond::Same { col: t.columns[i].name.clone(), param: 2 });
271            params.push(val);
272        }
273    }
274    let sql = Sql::Select {
275        table: t.name.clone(),
276        cols: names_between(t, 0, t.columns.len()),
277        conds,
278        order: names_between(t, 0, t.key_len as usize),
279    };
280    Some(Query { sql, params })
281}
282
283/// Every value of `vs` fits the column at its position plus `off`.
284fn all_fit(t: &Table, off: usize, vs: &Vec<Val>) -> bool {
285    let mut i = 0;
286    while i < vs.len() {
287        if !fits(t, off + i, &vs[i]) {
288            return false;
289        }
290        i += 1;
291    }
292    true
293}
294
295/// The query that runs `s` for `tenant`. `None` on a bad schema, a missing
296/// table, or values that do not fit. `Delete` and `DeleteWhere` need key
297/// columns: a keyless table holds one row, which is only replaced.
298pub fn compile(tables: &Vec<Table>, tenant: i64, s: &Stmt) -> Option<Query> {
299    if !valid(tables) {
300        return None;
301    }
302    match s {
303        Stmt::Upsert { table, key, rest } => {
304            if *table as usize >= tables.len() {
305                return None;
306            }
307            let t = &tables[*table as usize];
308            let n = t.key_len as usize;
309            if key.len() != n || rest.len() != t.columns.len() - n || !all_fit(t, 0, key) || !all_fit(t, n, rest) {
310                return None;
311            }
312            let mut params = Vec::new();
313            params.push(Val::Int(tenant));
314            let mut i = 0;
315            while i < key.len() {
316                params.push(key[i].clone());
317                i += 1;
318            }
319            let mut j = 0;
320            while j < rest.len() {
321                params.push(rest[j].clone());
322                j += 1;
323            }
324            let mut conflict = Vec::new();
325            conflict.push(tenant_col());
326            let mut k = 0;
327            while k < n {
328                conflict.push(t.columns[k].name.clone());
329                k += 1;
330            }
331            let sql = Sql::Insert {
332                table: t.name.clone(),
333                cols: col_names(t),
334                conflict,
335                update: names_between(t, n, t.columns.len()),
336            };
337            Some(Query { sql, params })
338        }
339        Stmt::Delete { table, key } => {
340            if *table as usize >= tables.len() {
341                return None;
342            }
343            let t = &tables[*table as usize];
344            if t.key_len == 0 || key.len() != t.key_len as usize || !all_fit(t, 0, key) {
345                return None;
346            }
347            let mut conds = Vec::new();
348            conds.push(Cond::Eq { col: tenant_col(), param: 1 });
349            let mut params = Vec::new();
350            params.push(Val::Int(tenant));
351            let mut i = 0;
352            while i < key.len() {
353                conds.push(Cond::Eq { col: t.columns[i].name.clone(), param: i as u32 + 2 });
354                params.push(key[i].clone());
355                i += 1;
356            }
357            Some(Query { sql: Sql::Delete { table: t.name.clone(), conds }, params })
358        }
359        Stmt::DeleteWhere { table, col, val } => {
360            if *table as usize >= tables.len() {
361                return None;
362            }
363            let t = &tables[*table as usize];
364            let i = *col as usize;
365            if t.key_len == 0 || i >= t.columns.len() || !has_kind(val, t.columns[i].kind) {
366                return None;
367            }
368            let mut conds = Vec::new();
369            conds.push(Cond::Eq { col: tenant_col(), param: 1 });
370            conds.push(Cond::Same { col: t.columns[i].name.clone(), param: 2 });
371            let mut params = Vec::new();
372            params.push(Val::Int(tenant));
373            params.push(val.clone());
374            Some(Query { sql: Sql::Delete { table: t.name.clone(), conds }, params })
375        }
376    }
377}
378
379/// Appends `n` quoted: `"` around it, and each `"` inside doubled.
380fn push_name(out: &mut Vec<u8>, n: &Vec<u8>) {
381    out.push(34);
382    let mut i = 0;
383    while i < n.len() {
384        if n[i] == 34 {
385            out.push(34);
386        }
387        out.push(n[i]);
388        i += 1;
389    }
390    out.push(34);
391}
392
393/// Appends quoted names separated by `, `.
394fn push_names(out: &mut Vec<u8>, ns: &Vec<Vec<u8>>) {
395    let mut i = 0;
396    while i < ns.len() {
397        if i > 0 {
398            push_lit(out, b", ");
399        }
400        push_name(out, &ns[i]);
401        i += 1;
402    }
403}
404
405/// Appends `n` in decimal.
406fn push_dec(out: &mut Vec<u8>, n: u32) {
407    if n >= 10 {
408        push_dec(out, n / 10);
409    }
410    out.push(48 + (n % 10) as u8);
411}
412
413fn push_param(out: &mut Vec<u8>, p: u32) {
414    out.push(36);
415    push_dec(out, p);
416}
417
418fn push_cond(out: &mut Vec<u8>, c: &Cond) {
419    match c {
420        Cond::Eq { col, param } => {
421            push_name(out, col);
422            push_lit(out, b" = ");
423            push_param(out, *param);
424        }
425        Cond::Same { col, param } => {
426            push_name(out, col);
427            push_lit(out, b" IS NOT DISTINCT FROM ");
428            push_param(out, *param);
429        }
430    }
431}
432
433fn push_where(out: &mut Vec<u8>, cs: &Vec<Cond>) {
434    let mut i = 0;
435    while i < cs.len() {
436        if i == 0 {
437            push_lit(out, b" WHERE ");
438        } else {
439            push_lit(out, b" AND ");
440        }
441        push_cond(out, &cs[i]);
442        i += 1;
443    }
444}
445
446fn push_kind(out: &mut Vec<u8>, k: Kind) {
447    match k {
448        Kind::Int => push_lit(out, b"BIGINT"),
449        Kind::Bool => push_lit(out, b"BOOLEAN"),
450        Kind::Text => push_lit(out, b"TEXT"),
451        Kind::Bytes => push_lit(out, b"BYTEA"),
452    }
453}
454
455fn push_coldefs(out: &mut Vec<u8>, cs: &Vec<ColDef>) {
456    let mut i = 0;
457    while i < cs.len() {
458        push_name(out, &cs[i].name);
459        out.push(32);
460        push_kind(out, cs[i].kind);
461        if cs[i].not_null {
462            push_lit(out, b" NOT NULL");
463        }
464        push_lit(out, b", ");
465        i += 1;
466    }
467}
468
469/// `$1, $2, ..., $n`.
470fn push_placeholders(out: &mut Vec<u8>, n: usize) {
471    let mut i = 0;
472    while i < n {
473        if i > 0 {
474            push_lit(out, b", ");
475        }
476        push_param(out, i as u32 + 1);
477        i += 1;
478    }
479}
480
481fn push_sets(out: &mut Vec<u8>, ns: &Vec<Vec<u8>>) {
482    let mut i = 0;
483    while i < ns.len() {
484        if i > 0 {
485            push_lit(out, b", ");
486        }
487        push_name(out, &ns[i]);
488        push_lit(out, b" = EXCLUDED.");
489        push_name(out, &ns[i]);
490        i += 1;
491    }
492}
493
494/// The text of `s`, as sent to PostgreSQL.
495pub fn render(s: &Sql) -> Vec<u8> {
496    let mut out = Vec::new();
497    match s {
498        Sql::Create { table, cols, key } => {
499            push_lit(&mut out, b"CREATE TABLE IF NOT EXISTS ");
500            push_name(&mut out, table);
501            push_lit(&mut out, b" (");
502            push_coldefs(&mut out, cols);
503            push_lit(&mut out, b"PRIMARY KEY (");
504            push_names(&mut out, key);
505            push_lit(&mut out, b"))");
506        }
507        Sql::Select { table, cols, conds, order } => {
508            push_lit(&mut out, b"SELECT ");
509            push_names(&mut out, cols);
510            push_lit(&mut out, b" FROM ");
511            push_name(&mut out, table);
512            push_where(&mut out, conds);
513            if order.len() > 0 {
514                push_lit(&mut out, b" ORDER BY ");
515                push_names(&mut out, order);
516            }
517        }
518        Sql::Insert { table, cols, conflict, update } => {
519            push_lit(&mut out, b"INSERT INTO ");
520            push_name(&mut out, table);
521            push_lit(&mut out, b" (");
522            push_names(&mut out, cols);
523            push_lit(&mut out, b") VALUES (");
524            push_placeholders(&mut out, cols.len());
525            push_lit(&mut out, b") ON CONFLICT (");
526            push_names(&mut out, conflict);
527            if update.len() > 0 {
528                push_lit(&mut out, b") DO UPDATE SET ");
529                push_sets(&mut out, update);
530            } else {
531                push_lit(&mut out, b") DO NOTHING");
532            }
533        }
534        Sql::Delete { table, conds } => {
535            push_lit(&mut out, b"DELETE FROM ");
536            push_name(&mut out, table);
537            push_where(&mut out, conds);
538        }
539    }
540    out
541}
542
543// Not extracted: the declarative reads' SQL, differential-tested (see `read.rs`).
544mod read;
545pub use read::{compile_read, compile_read_with_mode, create_index, ReadQuery, ReadSqlMode};
546
547#[cfg(test)]
548mod tests {
549    use super::*;
550
551    fn col(name: &str, kind: Kind, nullable: bool) -> Column {
552        Column { name: name.as_bytes().to_vec(), kind, nullable }
553    }
554
555    fn members() -> Vec<Table> {
556        vec![Table {
557            name: b"members".to_vec(),
558            columns: vec![col("project", Kind::Int, false), col("user", Kind::Int, false), col("note", Kind::Text, true)],
559            key_len: 2,
560        }]
561    }
562
563    fn text(s: &Sql) -> String {
564        String::from_utf8(render(s)).unwrap()
565    }
566
567    #[test]
568    fn renders_statements() {
569        let ts = members();
570        assert_eq!(
571            text(&create(&ts[0])),
572            "CREATE TABLE IF NOT EXISTS \"members\" (\"tenant_id\" BIGINT NOT NULL, \"project\" BIGINT NOT NULL, \
573             \"user\" BIGINT NOT NULL, \"note\" TEXT, PRIMARY KEY (\"tenant_id\", \"project\", \"user\"))"
574        );
575        let up = Stmt::Upsert { table: 0, key: vec![Val::Int(1), Val::Int(2)], rest: vec![Val::Null] };
576        let q = compile(&ts, 7, &up).unwrap();
577        assert_eq!(
578            text(&q.sql),
579            "INSERT INTO \"members\" (\"tenant_id\", \"project\", \"user\", \"note\") VALUES ($1, $2, $3, $4) \
580             ON CONFLICT (\"tenant_id\", \"project\", \"user\") DO UPDATE SET \"note\" = EXCLUDED.\"note\""
581        );
582        assert_eq!(q.params, vec![Val::Int(7), Val::Int(1), Val::Int(2), Val::Null]);
583        let del = Stmt::Delete { table: 0, key: vec![Val::Int(1), Val::Int(2)] };
584        assert_eq!(
585            text(&compile(&ts, 7, &del).unwrap().sql),
586            "DELETE FROM \"members\" WHERE \"tenant_id\" = $1 AND \"project\" = $2 AND \"user\" = $3"
587        );
588        let dw = Stmt::DeleteWhere { table: 0, col: 2, val: Val::Null };
589        assert_eq!(
590            text(&compile(&ts, 7, &dw).unwrap().sql),
591            "DELETE FROM \"members\" WHERE \"tenant_id\" = $1 AND \"note\" IS NOT DISTINCT FROM $2"
592        );
593        assert_eq!(
594            text(&select(&ts, 7, 0, Some((0, Val::Int(3)))).unwrap().sql),
595            "SELECT \"project\", \"user\", \"note\" FROM \"members\" WHERE \"tenant_id\" = $1 \
596             AND \"project\" IS NOT DISTINCT FROM $2 ORDER BY \"project\", \"user\""
597        );
598    }
599
600    #[test]
601    fn quotes_names() {
602        let mut out = Vec::new();
603        push_name(&mut out, &b"a\"b".to_vec());
604        assert_eq!(out, b"\"a\"\"b\"".to_vec());
605        let mut out = Vec::new();
606        push_placeholders(&mut out, 12);
607        assert!(out.ends_with(b"$10, $11, $12"));
608    }
609
610    #[test]
611    fn rejects_bad_input() {
612        let ts = members();
613        // A NULL key, a wrong type, a short row, a missing table.
614        assert!(compile(&ts, 7, &Stmt::Upsert { table: 0, key: vec![Val::Null, Val::Int(2)], rest: vec![Val::Null] }).is_none());
615        assert!(compile(&ts, 7, &Stmt::Delete { table: 0, key: vec![Val::Bool(true), Val::Int(2)] }).is_none());
616        assert!(compile(&ts, 7, &Stmt::Upsert { table: 0, key: vec![Val::Int(1), Val::Int(2)], rest: vec![] }).is_none());
617        assert!(compile(&ts, 7, &Stmt::Delete { table: 1, key: vec![] }).is_none());
618        // NULL only in a nullable column.
619        assert!(compile(&ts, 7, &Stmt::Upsert { table: 0, key: vec![Val::Int(1), Val::Int(2)], rest: vec![Val::Text(b"x".to_vec())] }).is_some());
620        // Schemas: a column named tenant_id, duplicate tables, an empty name.
621        let mut bad = members();
622        bad[0].columns[2].name = b"tenant_id".to_vec();
623        assert!(!valid(&bad));
624        let mut dup = members();
625        dup.push(dup[0].clone());
626        assert!(!valid(&dup));
627        let mut empty = members();
628        empty[0].columns[0].name = Vec::new();
629        assert!(!valid(&empty));
630        let mut framework = members();
631        framework[0].name = b"h5i_clock".to_vec();
632        assert!(!valid(&framework));
633        assert!(valid(&members()));
634    }
635}