Раздел 10 · Databases

Своя СУБД на Rust · урок 5: свой SQL, лексер и парсер

senior~190 мин

без входаВойди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти

Своя СУБД на Rust · урок 5: свой SQL, лексер и парсер

Кому это. К этому уроку у тебя собрана вся нижняя половина движка на Rust. В уроке 1 появились Page и DiskManager, в уроке 2 над диском встал буферный пул с PageGuard, в уроке 3 выросла куча, в уроке 4 к ней добавился B+Tree индекс. Получилось индексированное key-value хранилище: кладёшь кортеж, получаешь Rid, ищешь по ключу. Но звать heap.insert_tuple и btree.search руками из кода это ещё не СУБД. СУБД понимает язык.

Зачем именно Rust. Сегодня начинается верхняя половина движка: обработка запросов. Между строкой SELECT name FROM users WHERE id = 42 и исполнением стоит фронтенд: лексер режет строку на токены, парсер собирает дерево. Это та задача, ради которой в Rust есть перечисления с данными и match: дерево SQL это ровно enum Expr с вариантами под литерал, колонку, бинарную операцию и NOT, а компилятор проверяет, что принтер и binder обработали каждый вариант. Второй подарок языка касается ошибок. Сбой разбора может случиться на любой глубине рекурсии, и в TS его бросают исключением, а в Effect ловят бросок на границе в Result. В Rust исключений нет, зато есть оператор ?, который делает протаскивание Result сквозь каждую функцию почти бесплатным для глаз. Поэтому здесь ошибка честно течёт значением от parse_primary до самого верха.

Важно про код. Ты пишешь реализацию с нуля, в своём крейте ourdb (только std, edition 2021, rust-version = "1.84"). Сегодня в нём появляется модуль sql из четырёх файлов: ast.rs, lexer.rs, parser.rs, printer.rs. После байтовой возни уроков 1-4 этот урок отдыхает: лексер, парсер и принтер это чистые функции над строками и деревьями, без диска, без PageGuard, без from_le_bytes. Единственная связь с нижней половиной это ColumnType из tuple.rs урока 3: фронтенд и хранилище говорят о типах колонок одним и тем же перечислением. Печатай по блокам, гоняй cargo test --test lesson_05_sql и обязательно поиграй с виджетом.

Где мы в движке

┌────────────────────────────────────────────────┐
│  Бинарный протокол + TCP-сервер                  │  урок 11
├────────────────────────────────────────────────┤
│  Исполнитель (Volcano) + EXPLAIN                 │  урок 6
│  Планировщик, binder (семантический анализ)      │  урок 6
│  Парсер SQL (рекурсивный спуск + Pratt)          │  урок 5  ← мы здесь
│  Лексер (строка в токены)                        │  урок 5  ← мы здесь
├────────────────────────────────────────────────┤
│  Vacuum                                          │  урок 10
│  Блокировки (2PL), граф ожидания                 │  урок 9
│  MVCC (xid, снимки, undo)                        │  урок 8
│  WAL (журнал, redo, recovery)                    │  урок 7
├────────────────────────────────────────────────┤
│  B+Tree индекс                                   │  урок 4
│  Куча (slotted pages, seq scan)                  │  урок 3
├────────────────────────────────────────────────┤
│  Буферный пул (clock, PageGuard)                 │  урок 2
│  DiskManager (страницы поверх файла)             │  урок 1
└────────────────────────────────────────────────┘

Фронтенд не трогает нижние слои совсем. Лексер и парсер ничего не знают ни про кучу, ни про индекс, ни про каталог таблиц. Их работа закончилась, когда строка превратилась в дерево. Связать дерево с реальными таблицами это дело binder в уроке 6. Поэтому в сигнатурах сегодняшнего кода не будет ни &BufferPool, ни &mut DiskManager: вход &str или &Statement, выход дерево или String.

Что мы парсим

Парсер начинается не с кода, а с грамматики. Прежде чем писать разбор, надо точно знать, что считается валидным запросом. Иначе будешь латать парсер под каждый новый пример, и он расползётся.

Мы берём небольшое подмножество SQL, которого хватает на весь воркшоп. Это тот же диалект, что в TS-эталоне и в остальных портах, записанный в EBNF, нотации, которая один в один ложится на рекурсивный спуск: каждое правило станет одним методом.

statement   = createTable | insert | select | update | delete ;

createTable = "CREATE" "TABLE" ident "(" columnDef { "," columnDef } ")" ;
columnDef   = ident type [ "PRIMARY" "KEY" | "NOT" "NULL" ] ;
type        = "INT" | "TEXT" | "BOOL" ;

insert      = "INSERT" "INTO" ident [ "(" ident { "," ident } ")" ]
              "VALUES" "(" literal { "," literal } ")" ;

select      = "SELECT" ( "*" | projection )
              "FROM" ident [ join ]
              [ "WHERE" expr ]
              [ "ORDER" "BY" ident [ "ASC" | "DESC" ] ]
              [ "LIMIT" number ] ;
projection  = expr [ "AS" ident ] { "," expr [ "AS" ident ] } ;
join        = ( "INNER" | "LEFT" ) "JOIN" ident "ON" expr ;

update      = "UPDATE" ident "SET" assignment { "," assignment } [ "WHERE" expr ] ;
delete      = "DELETE" "FROM" ident [ "WHERE" expr ] ;
assignment  = ident "=" expr ;

expr        = orExpr ;
orExpr      = andExpr { "OR" andExpr } ;
andExpr     = cmpExpr { "AND" cmpExpr } ;
cmpExpr     = addExpr [ ( "=" | "<>" | "<" | "<=" | ">" | ">=" | "LIKE" ) addExpr ] ;
addExpr     = mulExpr { ( "+" | "-" ) mulExpr } ;
mulExpr     = primary { ( "*" | "/" ) primary } ;
primary     = literal | column | "(" expr ")" | "NOT" primary ;
column      = [ ident "." ] ident ;
literal     = number | string | "TRUE" | "FALSE" | "NULL" ;

Первые шесть правил это операторы. Каждое начинается с ключевого слова, по которому его сразу видно: CREATE, INSERT, SELECT, UPDATE, DELETE. Это и есть план парсера: посмотреть на первый токен и вызвать нужный метод.

Вторая половина, от orExpr до primary, описывает выражения после WHERE и в проекциях. Эта лесенка из шести уровней кодирует приоритеты операторов: OR слабее AND, тот слабее сравнений, те слабее сложения, то слабее умножения. Писать шесть почти одинаковых методов скучно и легко напутать, поэтому выражения мы разберём одной функцией и числом приоритета у каждого оператора. Это Pratt-парсер, до него дойдём во второй половине урока.

JOIN, ORDER BY и LIMIT парсер принимает уже сейчас, хотя исполнитель урока 6 их отвергнет как упражнения: грамматика описывает весь язык, а исполняемое подмножество решает binder. Транзакционные команды (BEGIN, COMMIT, ROLLBACK) и EXPLAIN это отдельные верхнеуровневые формы. В Rust-порте они живут в одном перечислении Command и разбираются отдельной функцией parse_command, чтобы движку урока 6 не пришлось потом переделывать фронтенд.

Граница Rust: Result в каждой функции

Прежде чем писать код, договоримся, как этот слой обходится с ошибками. Здесь три порта воркшопа расходятся сильнее всего, и сравнение учит больше любого абзаца теории.

Рекурсивный спуск устроен так, что сбой может случиться на любой глубине: parse_primary глубоко внутри parse_expr внутри parse_select вдруг видит не тот токен. Разбор надо оборвать целиком и вернуть ошибку наверх.

  • TS-эталон бросает SqlError, и бросок пролетает сквозь все рекурсивные вызовы. Удобно, но тип parse(source: string): Statement молчит о том, что функция может упасть. Тест ловит ошибку через try/catch.
  • Effect-порт бросает внутри ядра так же, а на публичной границе ловит бросок в Result<Statement, SqlError>. Протаскивать Result через каждую функцию там значило бы обернуть в flatMap каждую строку парсера.
  • Rust-порт делает то, что в TS и Effect было бы шумом: каждый метод парсера возвращает Result<T>, и ошибка честно течёт значением. Шума нет, потому что протаскивание стоит один символ. let table = self.expect_ident()?; читается как «прочитай идентификатор, а если не вышло, верни ошибку вызывающему». Ни try, ни flatMap, ни ветки if err != nil.

Итог: tokenize(source: &str) -> Result<Vec<Token>> и parse(source: &str) -> Result<Statement> честны в типе, исключений нет, а ошибку разбора в уроке 6 движок пробросит дальше тем же ?: match parse_command(sql)? { ... }. Result здесь это синоним из error.rs урока 1, std::result::Result<T, ourdb::Error>, поэтому ошибка SQL ложится в тот же enum Error, что и сбой диска.

А что с паникой? Она остаётся для багов самого движка, как и в bytes.rs урока 1: индекс за границей вектора токенов это ошибка программиста, а кривой SQL пользователя это ожидаемый исход, и он возвращается значением.

Конвейер из трёх чистых функций

Весь урок это три функции в конвейере:

&str ── tokenize ──▶ Result<Vec<Token>> ── parse ──▶ Result<Statement> ── pretty_print ──▶ String

tokenize режет строку на токены, parse собирает из токенов дерево, pretty_print печатает дерево обратно в SQL. Третья функция нужна, чтобы проверять парсер (round-trip), чтобы в уроке 6 печатать имена выражений в проекции и чтобы каталог хранил CREATE TABLE в каноническом виде.

Корень модуля собирает всё вместе и переэкспортирует публичный интерфейс:

// src/sql/mod.rs
//! Свой SQL (урок 5): лексер, парсер (рекурсивный спуск плюс Pratt) и pretty-printer.

pub mod ast;
pub mod lexer;
pub mod parser;
pub mod printer;

pub use ast::*;
pub use lexer::{render_sql_error, tokenize, Token, TokenType, KEYWORDS};
pub use parser::{parse, parse_command};
pub use printer::{pretty_print, print_expr};

И строчка pub mod sql; в lib.rs. После неё внешний код (и тесты урока) пишет use ourdb::sql::*; и получает и узлы дерева, и три функции конвейера. Поехали снизу вверх.

Токены

Токен это распознанная лексема с пометкой вида и позицией в исходнике. Позиция (offset) нужна не парсеру, а пользователю: по ней мы покажем, где именно сломался запрос.

// src/sql/lexer.rs
//! Лексер (урок 5): строка SQL в плоский поток токенов. Пробелы пропускаются, ключевые
//! слова без учёта регистра, строки в одинарных кавычках с `''` как экранированной
//! кавычкой, числа это неотрицательные целые. `<=`, `>=`, `<>` ловятся заглядыванием.
//! Смещения считаются в символах (Unicode scalar values) исходной строки.

use crate::error::{Error, Result};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TokenType {
    Keyword,
    Ident,
    Number,
    String,
    Operator,
    LParen,
    RParen,
    Comma,
    Dot,
    Semicolon,
    Eof,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Token {
    pub ty: TokenType,
    /// Лексема: keyword в верхнем регистре, для number и string распознанное значение.
    pub value: String,
    /// Смещение начала токена в символах исходной строки.
    pub offset: usize,
}

/// Ключевые слова диалекта.
pub const KEYWORDS: &[&str] = &[
    "SELECT", "FROM", "WHERE", "INSERT", "INTO", "VALUES", "CREATE", "TABLE", "UPDATE", "SET",
    "DELETE", "EXPLAIN", "BEGIN", "COMMIT", "ROLLBACK", "ORDER", "BY", "ASC", "DESC", "LIMIT",
    "AS", "INNER", "LEFT", "JOIN", "ON", "AND", "OR", "NOT", "LIKE", "TRUE", "FALSE", "NULL",
    "INT", "TEXT", "BOOL", "PRIMARY", "KEY",
];

TokenType это перечисление без данных, поэтому оно Copy: сравнить token.ty == TokenType::Eof или положить вид в кортеж ничего не стоит, никакого клонирования. Поле называется ty, потому что type в Rust зарезервированное слово. Тот же приём встретится в AST: where_ вместо where.

Разберём виды. Keyword это зарезервированное слово вроде SELECT или AND. Ключевое слово мы храним в верхнем регистре, поэтому select, Select и SELECT дадут один и тот же токен со значением "SELECT". Ident это идентификатор, имя таблицы или колонки, его храним как есть. Number и String несут распознанное значение: для строки это текст уже без кавычек и с раскрытым ''. Дальше операторы и пунктуация. И Eof это часовой конца потока: поток всегда кончается явным токеном, и парсеру не надо отдельно думать о выходе за границу вектора.

KEYWORDS это срез строковых констант &[&str], а не HashSet. На каждом слове лексер делает KEYWORDS.contains(...), то есть линейный проход по 37 коротким строкам. Для запросов в сотню токенов это неразличимо с хешем, зато константа живёт в бинарнике, не требует инициализации в рантайме и не тянет OnceLock. TS-эталон держит тут Set, потому что в JS множество строк дёшево создать при загрузке модуля. Если словарь вырастет до сотен слов, это место первым просится на match по строке или на отсортированный срез с binary_search.

Ошибки с позицией

Прежде чем писать лексер, заведём ему способ ругаться. Когда разбор спотыкается, мало сказать «syntax error». Пользователь хочет видеть, где именно. В Rust-порте ошибка разбора это вариант общего перечисления из урока 1:

// src/error.rs (фрагмент)

#[derive(Debug)]
pub enum Error {
    /// Ошибка ввода-вывода (диск, сокет).
    Io(io::Error),
    /// Ошибка разбора SQL: сообщение уже с позицией и стрелкой, offset в символах.
    Sql { message: String, offset: usize },
    // ... Engine, Invalid и классы ошибок транзакций уроков 6-9
}

Вариант Sql несёт два поля: готовое сообщение и смещение. Тесты проверяют именно offset, он должен точно указывать на проблемный символ. Сообщение собирается один раз в момент ошибки, поэтому Display для Error::Sql просто печатает message, а SQLSTATE у этого варианта 42601, как у синтаксической ошибки Postgres.

Собирают ошибку две функции лексера:

// src/sql/lexer.rs (продолжение)

/// Ошибка разбора с позицией и стрелкой `^` под местом ошибки.
pub(crate) fn sql_error(message: &str, offset: usize, source: &str) -> Error {
    Error::Sql {
        message: render_sql_error(message, offset, source),
        offset,
    }
}

/// Собрать сообщение с позицией: `message (строка L, колонка C)`, строка исходника, `^`.
pub fn render_sql_error(message: &str, offset: usize, source: &str) -> String {
    let chars: Vec<char> = source.chars().collect();
    let clamped = offset.min(chars.len());
    let mut line_start = 0;
    let mut line = 1;
    for (index, &character) in chars[..clamped].iter().enumerate() {
        if character == '\n' {
            line += 1;
            line_start = index + 1;
        }
    }
    let line_end = chars[line_start..]
        .iter()
        .position(|&character| character == '\n')
        .map_or(chars.len(), |at| line_start + at);
    let line_text: String = chars[line_start..line_end].iter().collect();
    let column = clamped - line_start + 1;
    let caret = " ".repeat(clamped - line_start);
    format!("{message} (строка {line}, колонка {column})\n{line_text}\n{caret}^")
}

sql_error помечен pub(crate): его зовут лексер и парсер, а снаружи крейта ошибки не фабрикуют. render_sql_error публичный и переэкспортирован из sql: собрать такое же сообщение со стрелкой можно и снаружи крейта. Логика прямая: идём от начала до смещения, считаем переводы строки, запоминаем начало текущей. Конец строки ищет position по итератору, а map_or закрывает случай «перевода строки дальше нет, строка тянется до конца ввода». offset.min(chars.len()) страхует от смещения за концом: у токена Eof оно ровно chars.len(), и стрелка должна встать сразу за последним символом, а не уронить срез.

В консоли это выглядит так:

ожидалось выражение, встретилось ключевое слово FROM (строка 1, колонка 8)
SELECT FROM t
       ^

Почему символы, а не байты

Самое интересное в этой функции первая строка: source.chars().collect(). Зачем копировать строку в Vec<char>, если &str и так умеет срезы?

Потому что &str в Rust это UTF-8, и его индексы считаются в байтах. Кириллица занимает два байта на букву, эмодзи четыре. Возьми запрос SELECT 'привет', @x. Неожиданный @ стоит по смещению 17 в символах, но 23 в байтах. Посчитай смещение в байтах, и стрелка уедет на шесть позиций вправо, под пустоту. Хуже того, &source[..offset] с байтовым индексом посреди буквы п не вернёт мусор, а запаникует: Rust не даёт разрезать строку внутри символа. Об этой разнице String и байтов подробно в уроке про коллекции и строки.

Поэтому лексер и рендер живут в одной системе координат: Vec<char>, где каждый элемент это один Unicode scalar value, а индекс в векторе это и есть номер символа. Плата за это четыре байта на символ и одна копия запроса. Для строки SQL в пару килобайт это ничто, а взамен лексер индексирует chars[position] за O(1) и никогда не попадает внутрь буквы.

Тонкость для кросс-языковой совместимости. TS-эталон считает смещение в единицах UTF-16 (так устроены строки JS). Для кириллицы и всего, что лежит в базовой плоскости Unicode, числа совпадают с нашими символами. Для эмодзи разойдутся: JS насчитает две единицы, Rust один char. Тесты урока пишут ошибочные запросы на ASCII, поэтому порты сходятся, но знать про эту границу полезно.

Лексер

Теперь сам лексер. Это один проход по Vec<char> с курсором position. На каждом шаге смотрим текущий символ и решаем, какой токен начинается.

// src/sql/lexer.rs (продолжение)

pub fn tokenize(source: &str) -> Result<Vec<Token>> {
    let chars: Vec<char> = source.chars().collect();
    let mut tokens = Vec::new();
    let mut position = 0;
    let push = |tokens: &mut Vec<Token>, ty, value: String, offset| {
        tokens.push(Token { ty, value, offset });
    };

    while position < chars.len() {
        let character = chars[position];
        let start = position;

        if matches!(character, ' ' | '\t' | '\n' | '\r') {
            position += 1;
        } else if character.is_ascii_digit() {
            while position < chars.len() && chars[position].is_ascii_digit() {
                position += 1;
            }
            let value = chars[start..position].iter().collect();
            push(&mut tokens, TokenType::Number, value, start);
        } else if character == '\'' {
            // ... строковая константа, разберём ниже
        } else if is_ident_start(character) {
            // ... слово: ключевое или идентификатор
        } else if let Some(operator) = read_operator(&chars, position) {
            position += operator.len();
            push(&mut tokens, TokenType::Operator, operator.to_owned(), start);
        } else if let Some(ty) = punctuation(character) {
            position += 1;
            push(&mut tokens, ty, character.to_string(), start);
        } else {
            let message = format!("неожиданный символ {}", json_quote(&character.to_string()));
            return Err(sql_error(&message, start, source));
        }
    }

    push(&mut tokens, TokenType::Eof, String::new(), position);
    Ok(tokens)
}

Сначала мелочь, которая выдаёт характер Rust: замыкание push принимает tokens параметром, а не захватывает его. Захвати оно &mut tokens из окружения, и это заимствование жило бы до последнего вызова push, а между вызовами нам нужно читать tokens (в тестах, в отладке) и, главное, вернуть его в Ok(tokens). Явный параметр держит заимствование ровно на время одного вызова. Это частый приём, когда замыкание хочется сделать помощником над изменяемым состоянием: передай состояние аргументом, и проверка заимствований перестанет спорить.

Дальше цепочка if разбирает символ по видам:

  • Пробелы пропускаются. matches! это match, который отвечает bool: короче четырёх сравнений через ||.
  • Число это подряд идущие ASCII-цифры. Значение собирается из среза chars[start..position] через collect() в String: тип результата collect выводится из того, что push ждёт value: String. Отрицательных чисел лексер не делает, минус останется оператором, и унарный минус это твоё упражнение.
  • Оператор определяет read_operator, она же говорит длину, на которую сдвинуть курсор.
  • Пунктуация определяет punctuation.
  • Всё остальное это ошибка с точным смещением символа. return Err(...) обрывает цикл и возвращает ошибку вызывающему, токены, собранные до этого, просто освобождаются вместе с вектором.

После цикла кладём Eof со смещением position, то есть chars.len(): стрелка ошибки «встретилось конец запроса» встанет сразу за последним символом.

Строки и экранированная кавычка

Строковая константа в SQL берётся в одинарные кавычки, а кавычка внутри строки удваивается: 'it''s' это текст it's. Вот ветка лексера:

// src/sql/lexer.rs, ветка строковой константы внутри tokenize

        } else if character == '\'' {
            position += 1;
            let mut value = String::new();
            loop {
                match chars.get(position) {
                    None => return Err(sql_error("незакрытая строковая константа", start, source)),
                    Some('\'') if chars.get(position + 1) == Some(&'\'') => {
                        value.push('\'');
                        position += 2;
                    }
                    Some('\'') => {
                        position += 1;
                        break;
                    }
                    Some(&inside) => {
                        value.push(inside);
                        position += 1;
                    }
                }
            }
            push(&mut tokens, TokenType::String, value, start);

Это хороший пример, как match заменяет вложенные if. chars.get(position) отдаёт Option<&char>, и четыре ветки читаются как таблица:

  1. None: ввод кончился, а закрывающей кавычки нет. Ошибка указывает на открывающую кавычку (start), а не на конец: так пользователь видит, какая строка не закрыта.
  2. Some('\'') с охранным условием «следующий тоже кавычка»: это экранирование, кладём одну кавычку и прыгаем через две.
  3. Some('\'') без условия: закрывающая кавычка, выходим из цикла.
  4. Some(&inside): любой другой символ, кладём как есть. Образец &inside сразу разыменовывает &char в char.

Порядок веток важен: ветка с охранным условием стоит раньше простой кавычки, иначе '' закрывало бы строку. chars.get(position + 1) не паникует на конце ввода, а отдаёт None, поэтому 'abc' в самом конце запроса разбирается без отдельной проверки границы.

Внутри строки допустим любой Unicode: 'привет' лексер примет, потому что value.push(inside) кладёт char в String, а та сама перекодирует его в UTF-8.

Слова: ключевое или идентификатор

// src/sql/lexer.rs, ветка слова внутри tokenize

        } else if is_ident_start(character) {
            while position < chars.len() && is_ident_part(chars[position]) {
                position += 1;
            }
            let word: String = chars[start..position].iter().collect();
            let upper = word.to_ascii_uppercase();
            if KEYWORDS.contains(&upper.as_str()) {
                push(&mut tokens, TokenType::Keyword, upper, start);
            } else {
                push(&mut tokens, TokenType::Ident, word, start);
            }
// src/sql/lexer.rs (продолжение)

fn is_ident_start(character: char) -> bool {
    character.is_ascii_alphabetic() || character == '_'
}

fn is_ident_part(character: char) -> bool {
    is_ident_start(character) || character.is_ascii_digit()
}

Слово начинается с буквы или подчёркивания и продолжается буквами, цифрами, подчёркиваниями. Обе проверки ASCII-шные: имя таблицы пользователи наш диалект не примет, лексер ответит «неожиданный символ “п”». Это осознанное упрощение, как и в эталоне.

Распознав слово, переводим его в верхний регистр и ищем в KEYWORDS. Нашли, это Keyword со значением в верхнем регистре. Не нашли, это Ident с исходным текстом. Заметь владение: word и upper это две разные String, и в каждую ветку уходит ровно одна из них, перемещением, без клона. KEYWORDS.contains(&upper.as_str()) выглядит громоздко из-за типов: срез хранит &str, contains ждёт ссылку на элемент, то есть &&str.

Операторы и пунктуация

// src/sql/lexer.rs (продолжение)

/// Оператор в текущей позиции, двухсимвольные раньше односимвольных.
fn read_operator(chars: &[char], position: usize) -> Option<&'static str> {
    let pair = (chars[position], chars.get(position + 1).copied());
    Some(match pair {
        ('<', Some('=')) => "<=",
        ('>', Some('=')) => ">=",
        ('<', Some('>')) => "<>",
        ('=', _) => "=",
        ('<', _) => "<",
        ('>', _) => ">",
        ('+', _) => "+",
        ('-', _) => "-",
        ('*', _) => "*",
        ('/', _) => "/",
        _ => return None,
    })
}

fn punctuation(character: char) -> Option<TokenType> {
    Some(match character {
        '(' => TokenType::LParen,
        ')' => TokenType::RParen,
        ',' => TokenType::Comma,
        '.' => TokenType::Dot,
        ';' => TokenType::Semicolon,
        _ => return None,
    })
}

Двухсимвольные операторы (<=, >=, <>) надо проверить раньше односимвольных, иначе <= распадётся на < и =. Это заглядывание на один символ, и в Rust его удобно записать сопоставлением пары: текущий символ и Option следующего. Ветки match проверяются сверху вниз, поэтому ('<', Some('=')) стоит раньше ('<', _). chars.get(position + 1).copied() превращает Option<&char> в Option<char>, чтобы образцы сравнивали значения, а не ссылки.

Оба помощника написаны одной идиомой: Some(match ... { ..., _ => return None }). Каждая ветка даёт голое значение, общий Some оборачивает их разом, а «не подошло» выходит из функции через return None прямо из ветки. Это читается как таблица соответствий и не плодит десять Some(...).

Возвращаемый тип Option<&'static str> говорит, что оператор это ссылка на строковую константу из бинарника, живущую всю программу. operator.len() здесь равна числу символов, потому что операторы ASCII: один байт на символ.

Последний помощник json_quote берёт символ или строку в двойные кавычки с экранированием, как JSON.stringify в сообщениях эталона. Он нужен только ради одинаковых текстов ошибок у всех портов (неожиданный символ "@"), устроен как цикл по символам с match на спецсимволы, и разбирать его подробно нет смысла.

AST: перечисления вместо размеченных объединений

Токены это плоский список. Парсер превратит его в AST. В TS-эталоне узлы это размеченные объединения с полем kind, и switch по нему сужает тип. В Rust это сразу встроено в язык: enum с данными в вариантах и match, который компилятор проверяет на полноту. Забыл обработать вариант в принтере, и сборка не пройдёт.

Начнём с бинарных операторов, это сердце выражений:

// src/sql/ast.rs
//! AST диалекта SQL (урок 5). Парсер строит эти узлы, pretty-printer печатает их обратно,
//! binder урока 6 их резолвит. Типы колонок общие со слоем данных (tuple::ColumnType).

use crate::tuple::ColumnType;

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum BinaryOp {
    Eq,
    Ne,
    Lt,
    Le,
    Gt,
    Ge,
    Add,
    Sub,
    Mul,
    Div,
    And,
    Or,
    Like,
}

impl BinaryOp {
    pub fn as_str(self) -> &'static str {
        match self {
            BinaryOp::Eq => "=",
            BinaryOp::Ne => "<>",
            BinaryOp::Lt => "<",
            BinaryOp::Le => "<=",
            BinaryOp::Gt => ">",
            BinaryOp::Ge => ">=",
            BinaryOp::Add => "+",
            BinaryOp::Sub => "-",
            BinaryOp::Mul => "*",
            BinaryOp::Div => "/",
            BinaryOp::And => "AND",
            BinaryOp::Or => "OR",
            BinaryOp::Like => "LIKE",
        }
    }

    /// Приоритет: больше число крепче связывает. Все бинарные левоассоциативны.
    pub fn precedence(self) -> u8 {
        match self {
            BinaryOp::Or => 1,
            BinaryOp::And => 2,
            BinaryOp::Eq
            | BinaryOp::Ne
            | BinaryOp::Lt
            | BinaryOp::Le
            | BinaryOp::Gt
            | BinaryOp::Ge
            | BinaryOp::Like => 3,
            BinaryOp::Add | BinaryOp::Sub => 4,
            BinaryOp::Mul | BinaryOp::Div => 5,
        }
    }

    /// Оператор по лексеме (символьной или ключевому слову).
    pub fn from_lexeme(lexeme: &str) -> Option<BinaryOp> {
        Some(match lexeme {
            "=" => BinaryOp::Eq,
            "<>" => BinaryOp::Ne,
            "<" => BinaryOp::Lt,
            "<=" => BinaryOp::Le,
            ">" => BinaryOp::Gt,
            ">=" => BinaryOp::Ge,
            "+" => BinaryOp::Add,
            "-" => BinaryOp::Sub,
            "*" => BinaryOp::Mul,
            "/" => BinaryOp::Div,
            "AND" => BinaryOp::And,
            "OR" => BinaryOp::Or,
            "LIKE" => BinaryOp::Like,
            _ => return None,
        })
    }
}

В TS-эталоне оператор это строковый литерал '+' | '<=' | 'AND', а приоритет живёт в отдельной таблице PRECEDENCE: Record<BinaryOp, number>, и таблица дублируется в парсере и в принтере. В Rust оператор это собственный тип, а приоритет его метод. Таблица одна, и match в precedence полный: добавишь вариант BinaryOp::Mod, и компилятор не даст забыть ему приоритет. from_lexeme это обратное отображение «лексема в оператор», знакомая идиома Some(match ...).

Теперь литералы и выражения:

// src/sql/ast.rs (продолжение)

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Literal {
    Number(i64),
    String(String),
    Bool(bool),
    Null,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
    Literal(Literal),
    Column {
        table: Option<String>,
        name: String,
    },
    Binary {
        op: BinaryOp,
        left: Box<Expr>,
        right: Box<Expr>,
    },
    Not(Box<Expr>),
}

impl Expr {
    /// Колонка без квалификатора (удобно в тестах).
    pub fn column(name: &str) -> Expr {
        Expr::Column {
            table: None,
            name: name.to_owned(),
        }
    }

    pub fn binary(op: BinaryOp, left: Expr, right: Expr) -> Expr {
        Expr::Binary {
            op,
            left: Box::new(left),
            right: Box::new(right),
        }
    }
}

Literal::Number(i64) это тот же int на восемь байт, что хранит куча урока 3. В TS-эталоне число стало bigint, у которого нет границ, и проверку диапазона пришлось бы писать руками. В Rust граница встроена в тип: число вне i64 парсер отвергнет ошибкой, увидишь ниже.

Главная Rust-деталь здесь Box<Expr> в Binary и Not. Почему не просто left: Expr? Потому что размер перечисления компилятор считает по самому большому варианту. Если Expr содержит Expr прямо, размер выходит бесконечным: Binary содержит два Expr, каждый из которых может быть Binary с двумя Expr, и так без дна. Компилятор отвергнет такой тип с ошибкой «recursive type has infinite size». Box разрывает рекурсию: в узле лежит указатель фиксированного размера, а потомок живёт в куче. Подробнее про умные указатели в уроке 24 раздела Rust, а сам пример с рекурсивным типом есть в Rust Book.

Обрати внимание, чего тут нет: ни Rc, ни RefCell, ни времён жизни. Дерево разбора это чистое владение сверху вниз: корень владеет детьми, дети владеют внуками. После урока 4, где B+Tree держал родителя запиненным, пока рекурсия спускалась в ребёнка, это отдых. Владение дерева совпадает с его формой, и Drop освобождает его целиком сам.

Помощники Expr::column и Expr::binary прячут Box::new и to_owned(). Без них ожидаемое дерево в тесте превращается в лес Box::new(Expr::Column { table: None, name: "a".to_owned() }).

Остаются операторы. Каждый это структура со своими полями, а Statement объединяет их в перечисление:

// src/sql/ast.rs (продолжение)

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum SelectItem {
    Star,
    Expr { expr: Expr, alias: Option<String> },
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum JoinType {
    Inner,
    Left,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Join {
    pub ty: JoinType,
    pub table: String,
    pub on: Expr,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Direction {
    Asc,
    Desc,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct OrderBy {
    pub column: String,
    pub direction: Direction,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Constraint {
    PrimaryKey,
    NotNull,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ColumnDef {
    pub name: String,
    pub ty: ColumnType,
    pub constraint: Option<Constraint>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CreateTable {
    pub table: String,
    pub columns: Vec<ColumnDef>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Insert {
    pub table: String,
    pub columns: Option<Vec<String>>,
    pub values: Vec<Literal>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Select {
    pub items: Vec<SelectItem>,
    pub from: String,
    pub join: Option<Join>,
    pub where_: Option<Expr>,
    pub order_by: Option<OrderBy>,
    pub limit: Option<u64>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Assignment {
    pub column: String,
    pub value: Expr,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Update {
    pub table: String,
    pub assignments: Vec<Assignment>,
    pub where_: Option<Expr>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Delete {
    pub table: String,
    pub where_: Option<Expr>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Statement {
    CreateTable(CreateTable),
    Insert(Insert),
    Select(Select),
    Update(Update),
    Delete(Delete),
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TxnOp {
    Begin,
    Commit,
    Rollback,
}

/// Верхнеуровневая команда: оператор, EXPLAIN над оператором (урок 6) или BEGIN/COMMIT/ROLLBACK.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Command {
    Statement(Statement),
    Explain(Statement),
    Txn(TxnOp),
}

Несколько решений, которые стоит проговорить.

Необязательное это Option. Нет WHERE, значит where_: None. Нет списка колонок в INSERT, значит columns: None. В TS это where?: Expr, и ничто не мешает забыть проверку на undefined. Здесь достать Expr из Option<Expr> без match, if let или ? нельзя.

Варианты с данными против структур. Statement::Select(Select) оборачивает отдельную структуру, а не перечисляет поля прямо в варианте. Так у каждого оператора есть собственный тип: binder урока 6 принимает &Select, а не «Statement, про который мы обещаем, что это Select». Выражение, наоборот, держит поля прямо в вариантах (Expr::Binary { op, left, right }): его узлы маленькие и разбираются только через match.

limit: Option<u64>. Отрицательного лимита не бывает, и тип это говорит.

derive у каждого узла. Debug даёт печать дерева в {:?} и сообщения упавших тестов. Clone нужен каталогу урока 6: тот хранит копию CreateTable. А PartialEq даёт главное для этого урока: два дерева сравниваются через == целиком, рекурсивно, сквозь Box и Vec. Весь тест round-trip это одна строка assert_eq!(parse(&pretty_print(&ast))?, ast). В TS-эталоне для этого нужен глубокий toEqual, в Rust сравнение структурное по построению. Про то, что делает derive для PartialEq и Eq, подробно в уроке про сравнение и newtype.

Command отделяет верхний уровень: просто оператор, EXPLAIN над оператором или транзакционная команда. EXPLAIN держит Statement, а не Command: EXPLAIN BEGIN и EXPLAIN EXPLAIN грамматика не допускает, и тип это закрепляет.

дальше после входа

Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.

Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.

войти