hawdb_sql/
ast.rs

1// Copyright 2026 Nowledge
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15pub use hawdb_expression::sql::{
16    Expr, ExprKind, SqlColumnRef, SqlComparisonOp, SqlExpression, SqlFunctionArgument,
17    SqlIndexColumn, SqlLikeEscape, SqlNullOrder, SqlOrderDirection, SqlOrderItem, SqlPredicate,
18    SqlSourceLocation, SqlSourceSpan, SqlValue,
19};
20
21use caseless::Caseless;
22use hawdb_core::{HawDBError, LogicalType, Result};
23
24#[derive(Debug, Clone, PartialEq, Eq)]
25pub enum SqlStatement {
26    Explain(SqlExplainStatement),
27    Select(SelectStatement),
28    Insert(InsertStatement),
29    Update(UpdateStatement),
30    Delete(DeleteStatement),
31    CreateTable(CreateTableStatement),
32    CreateIndex(CreateIndexStatement),
33    AlterTableAddColumn(AlterTableAddColumnStatement),
34    /// Project-scoped branch lifecycle commands. These are deliberately
35    /// distinct from relational DDL: their executor operates on the durable
36    /// branch catalog rather than a selected branch's schema.
37    Branch(BranchSqlStatement),
38}
39
40/// A branch lifecycle command parsed by the PostgreSQL entrypoint.
41///
42/// Keeping this as an AST family makes branch operations visible to the query
43/// runtime and prevents a host integration from recognizing command strings
44/// itself. Lifecycle and selection commands dispatch outside ordinary implicit
45/// data transactions through the storage-owned admission/publication kernel.
46#[derive(Debug, Clone, PartialEq, Eq)]
47pub enum BranchSqlStatement {
48    ShowBranches(ShowBranchesStatement),
49    ShowBranch(ShowBranchStatement),
50    ShowCurrentBranch,
51    UseBranch(BranchSqlSelector),
52    CreateBranch(CreateBranchStatement),
53    DropBranch(DropBranchStatement),
54}
55
56impl BranchSqlStatement {
57    pub const fn changes_context_or_catalog(&self) -> bool {
58        matches!(
59            self,
60            Self::UseBranch(_) | Self::CreateBranch(_) | Self::DropBranch(_)
61        )
62    }
63
64    pub const fn command(&self) -> &'static str {
65        match self {
66            Self::ShowBranches(_) => "SHOW BRANCHES",
67            Self::ShowBranch(_) => "SHOW BRANCH",
68            Self::ShowCurrentBranch => "SHOW CURRENT BRANCH",
69            Self::UseBranch(_) => "USE BRANCH",
70            Self::CreateBranch(_) => "CREATE BRANCH",
71            Self::DropBranch(_) => "DROP BRANCH",
72        }
73    }
74}
75
76#[derive(Debug, Clone, PartialEq, Eq)]
77pub struct CreateBranchStatement {
78    pub name: Option<BranchSqlValue>,
79    pub source: BranchSqlSelector,
80    pub expected_source_revision: SqlBound,
81    pub request_key: BranchSqlValue,
82    pub owner: Option<BranchSqlValue>,
83}
84
85#[derive(Debug, Clone, PartialEq, Eq)]
86pub struct DropBranchStatement {
87    pub id: BranchSqlValue,
88    pub expected_metadata_revision: SqlBound,
89}
90
91/// A bounded page over the durable branch catalog.
92#[derive(Debug, Clone, PartialEq, Eq)]
93pub struct ShowBranchesStatement {
94    pub limit: SqlBound,
95    pub offset: Option<SqlBound>,
96}
97
98#[derive(Debug, Clone, PartialEq, Eq)]
99pub struct ShowBranchStatement {
100    pub selector: BranchSqlSelector,
101}
102
103/// A typed selector avoids treating UUID-looking names as identifiers. The
104/// runtime validates `Id` values as UUIDs only after parameter binding.
105#[derive(Debug, Clone, PartialEq, Eq)]
106pub enum BranchSqlSelector {
107    Name(BranchSqlValue),
108    Id(BranchSqlValue),
109}
110
111/// A branch name, UUID, or opaque selector parameter. Branch commands accept
112/// only string literals or PostgreSQL positional parameters, never SQL
113/// expression evaluation or interpolated text.
114#[derive(Debug, Clone, PartialEq, Eq)]
115pub enum BranchSqlValue {
116    Literal(String),
117    Parameter(usize),
118}
119
120#[derive(Debug, Clone, PartialEq, Eq)]
121pub struct SqlExplainStatement {
122    pub analyze: bool,
123    pub statement: Box<SqlStatement>,
124}
125
126#[derive(Debug, Clone, PartialEq, Eq)]
127pub struct SqlVectorIndexSearch {
128    pub index: SqlValue,
129    pub embedding: SqlValue,
130    pub candidates: SqlValue,
131    pub top_k: SqlValue,
132}
133
134#[derive(Debug, Clone, PartialEq, Eq)]
135pub struct SelectStatement {
136    pub vector_index: Option<Box<SqlVectorIndexSearch>>,
137    pub projection: Vec<SelectProjection>,
138    pub distinct: bool,
139    /// `None` for a FROM-less SELECT (e.g. `SELECT version();`): the
140    /// projection is evaluated exactly once against an implicit row with no
141    /// column bindings, so any column reference in it is rejected the same
142    /// way an unresolvable column against a real table would be.
143    pub from: Option<SqlTableName>,
144    pub from_alias: Option<String>,
145    pub joins: Vec<SqlJoin>,
146    pub selection: Option<SqlPredicate>,
147    pub group_by: Vec<SqlColumnRef>,
148    pub having: Option<SqlPredicate>,
149    pub order_by: Vec<SqlOrderItem>,
150    pub limit: Option<SqlBound>,
151    pub offset: Option<SqlBound>,
152    pub lock_strength: Option<SqlLockStrength>,
153}
154
155impl SelectStatement {
156    /// The base table, for every code path that only ever runs on a real
157    /// table (catalog resolution, access-path selection, join planning, row
158    /// scanning). FROM-less selects never reach these paths — they're
159    /// handled by a separate, earlier branch — so `None` here is a caller
160    /// bug, not a user-facing state.
161    pub fn from_table(&self) -> &SqlTableName {
162        self.from
163            .as_ref()
164            .expect("from_table called on a FROM-less SELECT; it must take the fromless path")
165    }
166}
167
168#[derive(Debug, Clone, Copy, PartialEq, Eq)]
169pub enum SqlLockStrength {
170    Share,
171    Update,
172}
173
174#[derive(Debug, Clone, PartialEq, Eq)]
175pub struct InsertStatement {
176    pub table: SqlTableName,
177    pub columns: Vec<String>,
178    pub rows: Vec<Vec<SqlValue>>,
179    pub on_conflict: Option<SqlOnConflict>,
180    pub returning: Vec<SqlColumnRef>,
181}
182
183#[derive(Debug, Clone, PartialEq, Eq)]
184pub struct UpdateStatement {
185    pub table: SqlTableName,
186    pub alias: Option<String>,
187    pub assignments: Vec<SqlAssignment>,
188    pub selection: Option<SqlPredicate>,
189}
190
191#[derive(Debug, Clone, PartialEq, Eq)]
192pub struct DeleteStatement {
193    pub table: SqlTableName,
194    pub alias: Option<String>,
195    pub selection: Option<SqlPredicate>,
196}
197
198#[derive(Debug, Clone, PartialEq, Eq)]
199pub struct SqlAssignment {
200    pub column: String,
201    pub value: SqlAssignmentValue,
202}
203
204#[derive(Debug, Clone, PartialEq, Eq)]
205pub enum SqlAssignmentValue {
206    Value(SqlValue),
207    Column(SqlColumnRef),
208    Arithmetic {
209        left: SqlArithmeticOperand,
210        operator: SqlArithmeticOperator,
211        right: SqlArithmeticOperand,
212    },
213}
214
215#[derive(Debug, Clone, PartialEq, Eq)]
216pub enum SqlArithmeticOperand {
217    Value(SqlValue),
218    Column(SqlColumnRef),
219}
220
221#[derive(Debug, Clone, Copy, PartialEq, Eq)]
222pub enum SqlArithmeticOperator {
223    Add,
224    Subtract,
225}
226
227#[derive(Debug, Clone, PartialEq, Eq)]
228pub struct SqlOnConflict {
229    pub columns: Vec<String>,
230    pub action: SqlConflictAction,
231}
232
233#[derive(Debug, Clone, PartialEq, Eq)]
234pub enum SqlConflictAction {
235    DoNothing,
236    DoUpdate(Vec<SqlAssignment>),
237}
238
239#[derive(Debug, Clone, PartialEq, Eq)]
240pub struct CreateTableStatement {
241    pub table: SqlTableName,
242    pub if_not_exists: bool,
243    pub columns: Vec<SqlColumnDefinition>,
244    pub constraints: Vec<SqlTableConstraint>,
245    pub storage: SqlTableStorage,
246}
247
248#[derive(Debug, Clone, PartialEq, Eq, Default)]
249pub enum SqlTableStorage {
250    #[default]
251    RowPage,
252    StrictAppend {
253        partition_key: Vec<String>,
254        order_key: Vec<String>,
255        generated_order: SqlGeneratedOrder,
256    },
257}
258
259#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
260pub enum SqlGeneratedOrder {
261    #[default]
262    CallerProvided,
263    CommitSequence,
264}
265
266#[derive(Debug, Clone, PartialEq, Eq)]
267pub struct SqlColumnDefinition {
268    pub name: String,
269    pub data_type: SqlDataType,
270    pub nullable: bool,
271    pub default: Option<SqlColumnDefault>,
272    pub primary_key: bool,
273    pub unique: bool,
274    pub references: Option<SqlForeignKeyReference>,
275}
276
277#[derive(Debug, Clone, PartialEq, Eq)]
278pub enum SqlColumnDefault {
279    Literal(SqlValue),
280    UuidV7,
281}
282
283#[derive(Debug, Clone, Copy, PartialEq, Eq)]
284pub enum SqlDataType {
285    Boolean,
286    BigInt,
287    DoublePrecision,
288    Text,
289    Bytea,
290    Uuid,
291    Vector(hawdb_core::VectorDimension),
292}
293
294impl SqlDataType {
295    pub const fn logical_type(self) -> LogicalType {
296        match self {
297            Self::Boolean => LogicalType::Boolean,
298            Self::BigInt => LogicalType::Int64,
299            Self::DoublePrecision => LogicalType::Float64,
300            Self::Text => LogicalType::Text,
301            Self::Bytea => LogicalType::Binary,
302            Self::Uuid => LogicalType::Uuid,
303            Self::Vector(dimension) => LogicalType::Vector(dimension),
304        }
305    }
306}
307
308#[derive(Debug, Clone, PartialEq, Eq)]
309pub enum SqlTableConstraint {
310    PrimaryKey(Vec<String>),
311    Unique(Vec<String>),
312    ForeignKey {
313        columns: Vec<String>,
314        reference: SqlForeignKeyReference,
315    },
316}
317
318#[derive(Debug, Clone, PartialEq, Eq)]
319pub struct SqlForeignKeyReference {
320    pub table: SqlTableName,
321    pub columns: Vec<String>,
322    pub on_delete: SqlReferentialAction,
323    pub on_update: SqlReferentialAction,
324}
325
326#[derive(Debug, Clone, Copy, PartialEq, Eq)]
327pub enum SqlReferentialAction {
328    NoAction,
329    Restrict,
330    Cascade,
331    SetNull,
332}
333
334#[derive(Debug, Clone, PartialEq, Eq)]
335pub struct CreateIndexStatement {
336    pub name: String,
337    pub table: SqlTableName,
338    pub columns: Vec<SqlIndexColumn>,
339    pub unique: bool,
340    pub if_not_exists: bool,
341}
342
343#[derive(Debug, Clone, PartialEq, Eq)]
344pub struct AlterTableAddColumnStatement {
345    pub table: SqlTableName,
346    pub if_not_exists: bool,
347    pub column: SqlColumnDefinition,
348}
349
350#[derive(Debug, Clone, Copy, PartialEq, Eq)]
351pub enum SqlBound {
352    Literal(u64),
353    Parameter(usize),
354}
355
356#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
357pub struct SqlTableName {
358    pub schema: Option<String>,
359    pub name: String,
360}
361
362#[derive(Debug, Clone, PartialEq, Eq)]
363pub enum SelectProjection {
364    Wildcard,
365    Expression {
366        expression: SqlExpression,
367        alias: Option<String>,
368    },
369}
370
371#[derive(Debug, Clone, PartialEq, Eq)]
372pub struct SqlJoin {
373    pub kind: SqlJoinKind,
374    pub table: SqlTableName,
375    pub alias: Option<String>,
376    pub on: SqlPredicate,
377    /// First input visible to ON, with the SELECT base relation at ordinal zero.
378    /// The current join's right input is the inclusive end of this scope.
379    pub on_scope_start: usize,
380}
381
382#[derive(Debug, Clone, Copy, PartialEq, Eq)]
383pub enum SqlJoinKind {
384    Inner,
385    Left,
386}
387
388/// Matches SQL LIKE patterns with locale-independent Unicode default case folding for ILIKE.
389pub fn sql_like_matches(
390    value: &str,
391    pattern: &str,
392    escape: SqlLikeEscape,
393    case_insensitive: bool,
394) -> Result<bool> {
395    let layout = like_layout(pattern, escape, case_insensitive)?;
396    let value_chars = value.chars().count();
397    layout.scratch_bytes(value_chars)?;
398    let (tokens, literals) = tokenize_like_pattern(pattern, escape, case_insensitive, &layout)?;
399    let mut characters = Vec::with_capacity(value_chars);
400    characters.extend(value.chars());
401    let value = characters;
402
403    let mut value_index = 0;
404    let mut pattern_index = 0;
405    let mut wildcard_index = None;
406    let mut wildcard_value_index = 0;
407    while value_index < value.len() {
408        let matched = match tokens.get(pattern_index) {
409            Some(LikeToken::Literal(expected)) => {
410                if let Some(consumed) = match_like_literal(
411                    &value[value_index..],
412                    &literals[expected.clone()],
413                    case_insensitive,
414                ) {
415                    value_index += consumed;
416                    pattern_index += 1;
417                    true
418                } else {
419                    false
420                }
421            }
422            Some(LikeToken::One) => {
423                value_index += 1;
424                pattern_index += 1;
425                true
426            }
427            Some(LikeToken::Many) => {
428                wildcard_index = Some(pattern_index);
429                wildcard_value_index = value_index;
430                pattern_index += 1;
431                true
432            }
433            None => false,
434        };
435        if matched {
436            continue;
437        }
438        let Some(wildcard_index) = wildcard_index else {
439            return Ok(false);
440        };
441        wildcard_value_index += 1;
442        value_index = wildcard_value_index;
443        pattern_index = wildcard_index + 1;
444    }
445    while matches!(tokens.get(pattern_index), Some(LikeToken::Many)) {
446        pattern_index += 1;
447    }
448    Ok(pattern_index == tokens.len())
449}
450
451/// Requested heap bytes used by the LIKE matcher, before allocating its buffers.
452/// Escape parsing and Unicode folding share the matcher's exact layout pass.
453#[doc(hidden)]
454pub fn sql_like_scratch_bytes(
455    value: &str,
456    pattern: &str,
457    escape: SqlLikeEscape,
458    case_insensitive: bool,
459) -> Result<usize> {
460    like_layout(pattern, escape, case_insensitive)?.scratch_bytes(value.chars().count())
461}
462
463struct LikeLayout {
464    tokens: usize,
465    literal_bytes: usize,
466}
467
468impl LikeLayout {
469    fn scratch_bytes(&self, value_chars: usize) -> Result<usize> {
470        self.tokens
471            .checked_mul(std::mem::size_of::<LikeToken>())
472            .and_then(|bytes| bytes.checked_add(self.literal_bytes))
473            .and_then(|bytes| {
474                value_chars
475                    .checked_mul(std::mem::size_of::<char>())
476                    .and_then(|value| bytes.checked_add(value))
477            })
478            .ok_or_else(like_size_overflow)
479    }
480}
481
482#[derive(Debug, Clone)]
483enum LikeToken {
484    Literal(std::ops::Range<usize>),
485    One,
486    Many,
487}
488
489#[derive(Clone, Copy)]
490enum LikePart {
491    Literal(char),
492    One,
493    Many,
494}
495
496fn like_size_overflow() -> HawDBError {
497    HawDBError::Execution("LIKE scratch length overflow".into())
498}
499
500fn visit_like_pattern(
501    pattern: &str,
502    escape: SqlLikeEscape,
503    mut visit: impl FnMut(LikePart) -> Result<()>,
504) -> Result<()> {
505    let escape = match escape {
506        SqlLikeEscape::Character(character) => Some(character),
507        SqlLikeEscape::Disabled => None,
508    };
509    let mut characters = pattern.chars();
510    while let Some(character) = characters.next() {
511        let part = if Some(character) == escape {
512            LikePart::Literal(characters.next().ok_or_else(|| {
513                HawDBError::Semantic("LIKE pattern ends with its escape character".to_string())
514            })?)
515        } else {
516            match character {
517                '%' => LikePart::Many,
518                '_' => LikePart::One,
519                literal => LikePart::Literal(literal),
520            }
521        };
522        visit(part)?;
523    }
524    Ok(())
525}
526
527fn visit_like_literal(
528    literal: char,
529    case_insensitive: bool,
530    mut visit: impl FnMut(char) -> Result<()>,
531) -> Result<()> {
532    if case_insensitive {
533        for character in std::iter::once(literal).default_case_fold() {
534            visit(character)?;
535        }
536        Ok(())
537    } else {
538        visit(literal)
539    }
540}
541
542fn like_layout(pattern: &str, escape: SqlLikeEscape, case_insensitive: bool) -> Result<LikeLayout> {
543    let mut layout = LikeLayout {
544        tokens: 0,
545        literal_bytes: 0,
546    };
547    let mut previous = None;
548    visit_like_pattern(pattern, escape, |part| {
549        let merged = matches!(
550            (previous, part),
551            (Some(LikePart::Many), LikePart::Many)
552                | (Some(LikePart::Literal(_)), LikePart::Literal(_))
553        );
554        if !merged {
555            layout.tokens = layout
556                .tokens
557                .checked_add(1)
558                .ok_or_else(like_size_overflow)?;
559        }
560        if let LikePart::Literal(literal) = part {
561            visit_like_literal(literal, case_insensitive, |character| {
562                layout.literal_bytes = layout
563                    .literal_bytes
564                    .checked_add(character.len_utf8())
565                    .ok_or_else(like_size_overflow)?;
566                Ok(())
567            })?;
568        }
569        previous = Some(part);
570        Ok(())
571    })?;
572    Ok(layout)
573}
574
575fn tokenize_like_pattern(
576    pattern: &str,
577    escape: SqlLikeEscape,
578    case_insensitive: bool,
579    layout: &LikeLayout,
580) -> Result<(Vec<LikeToken>, String)> {
581    let mut tokens = Vec::with_capacity(layout.tokens);
582    let mut literals = String::with_capacity(layout.literal_bytes);
583    visit_like_pattern(pattern, escape, |part| {
584        match part {
585            LikePart::Literal(literal) => {
586                let start = literals.len();
587                visit_like_literal(literal, case_insensitive, |character| {
588                    literals.push(character);
589                    Ok(())
590                })?;
591                if let Some(LikeToken::Literal(range)) = tokens.last_mut() {
592                    range.end = literals.len();
593                } else {
594                    tokens.push(LikeToken::Literal(start..literals.len()));
595                }
596            }
597            LikePart::Many if !matches!(tokens.last(), Some(LikeToken::Many)) => {
598                tokens.push(LikeToken::Many)
599            }
600            LikePart::Many => {}
601            LikePart::One => tokens.push(LikeToken::One),
602        }
603        Ok(())
604    })?;
605    debug_assert_eq!(tokens.len(), layout.tokens);
606    debug_assert_eq!(literals.len(), layout.literal_bytes);
607    Ok((tokens, literals))
608}
609
610fn match_like_literal(value: &[char], expected: &str, case_insensitive: bool) -> Option<usize> {
611    let mut expected = expected.chars().peekable();
612    for (index, character) in value.iter().copied().enumerate() {
613        if case_insensitive {
614            for folded in std::iter::once(character).default_case_fold() {
615                if expected.next() != Some(folded) {
616                    return None;
617                }
618            }
619        } else if expected.next() != Some(character) {
620            return None;
621        }
622        // Wildcards and literal boundaries consume complete source characters,
623        // even when one character folds into several code points.
624        if expected.peek().is_none() {
625            return Some(index + 1);
626        }
627    }
628    None
629}
630
631#[cfg(test)]
632mod tests {
633    use super::*;
634
635    #[test]
636    fn postgres_data_types_use_shared_logical_types() {
637        assert_eq!(SqlDataType::Boolean.logical_type(), LogicalType::Boolean);
638        assert_eq!(SqlDataType::BigInt.logical_type(), LogicalType::Int64);
639        assert_eq!(
640            SqlDataType::DoublePrecision.logical_type(),
641            LogicalType::Float64
642        );
643        assert_eq!(SqlDataType::Text.logical_type(), LogicalType::Text);
644        assert_eq!(SqlDataType::Bytea.logical_type(), LogicalType::Binary);
645    }
646}
hawdb_sql/ast.rs

hawdb_sql/
ast.rs
