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

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

Зачем именно Effect. Сегодня начинается верхняя половина движка: обработка запросов. Между строкой SELECT name FROM users WHERE id = 42 и исполнением стоит фронтенд: лексер режет строку на токены, парсер собирает дерево. И вот где Effect показывает грань, которой не было в прошлых уроках: разбор это чистые функции, но они могут не сложиться. Тут нет ни диска, ни ресурса, ни состояния, поэтому Effect был бы перебором. Но сбой (кривой синтаксис) всё равно надо вернуть значением, а не выбросить наружу. Это работа для Result: tokenize и parse вернут Result<результат, SqlError>. Сбой ляжет в Failure как значение, а не вылетит исключением.

Важно про код. Как и прежде, ты пишешь реализацию с нуля, листинги приведены целиком. После байтовой возни уроков 1-4 этот урок отдыхает: лексер, парсер и принтер это чистые функции над строками и деревьями, без диска, без пина страниц, без байтов. Печатай по блокам, прогоняй тесты, и обязательно поиграй с виджетом.

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

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

Заметь важное: фронтенд не трогает нижние слои совсем. Лексер и парсер ничего не знают ни про кучу, ни про индекс, ни про каталог таблиц. Их работа закончилась, когда строка превратилась в дерево. Связать дерево с реальными таблицами это дело binder в уроке 6. Поэтому весь сегодняшний код это чистые функции, и зависимости от BufferPool тут не будет: вход строка или дерево, выход дерево или строка.

Что мы парсим

Парсер начинается не с кода, а с грамматики. Мы берём небольшое подмножество SQL, которого хватает на весь воркшоп. Записывается грамматика в 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, кодирует приоритеты операторов. Писать шесть почти одинаковых функций скучно, поэтому выражения мы разберём одной функцией с таблицей приоритетов, это Pratt-парсер.

Транзакционные команды (BEGIN, COMMIT, ROLLBACK) и EXPLAIN это отдельные верхнеуровневые формы. Они появятся, когда им будет что обслуживать: EXPLAIN в уроке 6 вместе с планом, транзакции в уроке 7. Сегодня разбираем пять операторов работы с данными, и parse отдаёт ровно один Statement.

Граница Effect: чистый разбор, ошибка в значении

Прежде чем писать код, договоримся, как этот слой обходится с ошибками, потому что тут Effect-порт делает осознанный выбор, отличный от рефлекса “всё в Effect”.

Рекурсивный спуск устроен так, что сбой может случиться на любой глубине: parsePrimary глубоко внутри parseExpr внутри parseSelect вдруг видит не тот токен. Естественный способ оборвать весь спуск из глубины это бросок: функция fail() кидает SqlError, и он пролетает сквозь все рекурсивные вызовы до самого верха. Протаскивать вместо этого Result через каждый parsePrimary, parseExpr, parseSelect значило бы обернуть в монаду каждую строку парсера: сплошная обвязка flatMap там, где по смыслу просто “читаем токен за токеном”. Это шум без пользы.

Поэтому Effect-порт делает прагматично: внутри лексер и парсер по-прежнему бросают SqlError для управления потоком (чистый рекурсивный спуск так естественнее), а на публичной границе мы ловим этот бросок в Result. Помощник sqlResult оборачивает разбор: успех становится Success, брошенный SqlError становится Failure, а любой другой бросок (баг в коде) пробрасывается дальше как настоящий дефект. Снаружи tokenize и parse это чистые функции строка -> Result<результат, SqlError>: бросок не вылетает из модуля, он превращается в значение на краю.

Почему Result, а не Effect. У этого слоя нет ни ресурса, ни асинхронности, ни зависимости из контекста, только два исхода: разобралось или нет. Result<A, SqlError> это ровно это, чистый родственник каналов успеха и ошибки в Effect, но без рантайма. А в уроке 6 движок, у которого ресурсы есть, поднимет этот Result в свой канал ошибок одной строкой: yield* Effect.fromResult(parse(sql)) либо даёт значение, либо роняет SqlError в E. Так чистый разбор и эффектный движок состыкуются без швов.

Запомни этот приём, он типичен для переноса парсеров на Effect: бросай внутри чистого ядра, лови на границе в Result. То же прагматичное решение, что мутабельный аккумулятор внутри чистой функции: локальный бросок не нарушает чистоты, потому что parse(s) всегда возвращает один и тот же Result.

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

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

строка SQL ── tokenize ──▶ Result токенов ── parse ──▶ Result AST ── prettyPrint ──▶ строка SQL

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

Токены

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

// src/sql/token.ts

export type TokenType =
  | 'keyword'
  | 'ident'
  | 'number'
  | 'string'
  | 'operator'
  | 'lparen'
  | 'rparen'
  | 'comma'
  | 'dot'
  | 'semicolon'
  | 'eof';

export interface Token {
  readonly type: TokenType;
  /** Лексема: для keyword в верхнем регистре, для number и string распознанное значение. */
  readonly value: string;
  /** Смещение начала токена в исходной строке. */
  readonly offset: number;
}

/** Ключевые слова диалекта (сравнение без учёта регистра). */
export const KEYWORDS: ReadonlySet<string> = new Set([
  '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',
]);

keyword это зарезервированное слово, его храним в верхнем регистре, поэтому select, Select и SELECT дают один токен. ident это имя таблицы или колонки, его храним как есть, с сохранением регистра. number и string несут распознанное значение. eof это часовой конца потока: парсеру удобно, когда поток всегда заканчивается явным токеном.

Ошибки с позицией: SqlError на Data.TaggedError

Вот первое отличие порта. В TS-треке SqlError это подкласс Error. В Effect-порте это Data.TaggedError, как все наши ошибки слоёв (IoError, BufferPoolError, HeapError, BTreeError). И тут же заведём sqlResult, ту самую границу.

// src/sql/errors.ts
import { Data, Result } from 'effect';

/** Ошибка разбора SQL: rendered-сообщение и смещение в исходнике. */
export class SqlError extends Data.TaggedError('SqlError')<{
  readonly message: string;
  readonly offset: number;
}> {}

/** Собрать сообщение с позицией и стрелкой `^` под местом ошибки. */
export function renderSqlError(message: string, offset: number, source: string): string {
  const clamped = Math.min(Math.max(offset, 0), source.length);

  let lineStart = 0;
  let line = 1;
  for (let index = 0; index < clamped; index++) {
    if (source[index] === '\n') {
      line++;
      lineStart = index + 1;
    }
  }
  const newlineAt = source.indexOf('\n', lineStart);
  const lineEnd = newlineAt === -1 ? source.length : newlineAt;
  const column = clamped - lineStart + 1;
  const lineText = source.slice(lineStart, lineEnd);
  const caret = `${' '.repeat(clamped - lineStart)}^`;

  return `${message} (строка ${line}, колонка ${column})\n${lineText}\n${caret}`;
}

/**
 * Запустить чистый разбор, поймав брошенный SqlError в `Result.failure`. Любой другой
 * бросок это дефект (баг), пробрасываем его дальше как настоящее исключение.
 */
export const sqlResult = <A>(thunk: () => A): Result.Result<A, SqlError> =>
  Result.try({
    try: thunk,
    catch: (error) => {
      if (error instanceof SqlError) {
        return error;
      }
      throw error;
    },
  });

SqlError несёт уже собранное message и offset. Тесты проверяют именно offset: смещение должно точно указывать на проблемный символ. renderSqlError переводит линейное смещение в строку и колонку, вырезает строку текста и строит caret (столько пробелов, сколько символов до ошибки, и ^). В консоли это выглядит так:

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

sqlResult это и есть граница. Result.try запускает thunk, и если внутри бросили SqlError, кладёт его в Failure. catch страхует: если прилетело что-то не SqlError, это баг, и мы пробрасываем его дальше настоящим исключением, не пряча в Failure. Так в Failure попадают только наши размеченные ошибки разбора, а не случайные TypeError из бага.

Лексер

Лексер это один проход по строке с курсором. Внутренний scan бросает SqlError (его зовёт парсер напрямую), а публичный tokenize оборачивает бросок в Result через sqlResult.

// src/sql/lexer.ts
import { type Result } from 'effect';

import { renderSqlError, SqlError, sqlResult } from '~/sql/errors.ts';
import { KEYWORDS, type Token } from '~/sql/token.ts';

/** Внутренний бросающий лексер. Парсер зовёт его напрямую. */
export function scan(source: string): Token[] {
  const tokens: Token[] = [];
  let position = 0;

  const fail = (message: string, offset: number): never => {
    throw new SqlError({ message: renderSqlError(message, offset, source), offset });
  };

  while (position < source.length) {
    const character = source[position]!;

    if (isWhitespace(character)) {
      position++;
      continue;
    }

    const start = position;

    if (isDigit(character)) {
      while (position < source.length && isDigit(source[position]!)) {
        position++;
      }
      tokens.push({ type: 'number', value: source.slice(start, position), offset: start });
      continue;
    }

    if (character === "'") {
      position++;
      let value = '';
      for (;;) {
        if (position >= source.length) {
          fail('незакрытая строковая константа', start);
        }
        const inside = source[position]!;
        if (inside === "'") {
          if (source[position + 1] === "'") {
            value += "'";
            position += 2;
            continue;
          }
          position++;
          break;
        }
        value += inside;
        position++;
      }
      tokens.push({ type: 'string', value, offset: start });
      continue;
    }

    if (isIdentStart(character)) {
      while (position < source.length && isIdentPart(source[position]!)) {
        position++;
      }
      const word = source.slice(start, position);
      const upper = word.toUpperCase();
      if (KEYWORDS.has(upper)) {
        tokens.push({ type: 'keyword', value: upper, offset: start });
      } else {
        tokens.push({ type: 'ident', value: word, offset: start });
      }
      continue;
    }

    const operator = readOperator(source, position);
    if (operator !== null) {
      tokens.push({ type: 'operator', value: operator, offset: start });
      position += operator.length;
      continue;
    }

    const punctuation = PUNCTUATION[character];
    if (punctuation !== undefined) {
      tokens.push({ type: punctuation, value: character, offset: start });
      position++;
      continue;
    }

    fail(`неожиданный символ ${JSON.stringify(character)}`, start);
  }

  tokens.push({ type: 'eof', value: '', offset: position });
  return tokens;
}

/** Публичный лексер: строка в поток токенов или SqlError. */
export const tokenize = (source: string): Result.Result<ReadonlyArray<Token>, SqlError> =>
  sqlResult(() => scan(source));

Цикл это ветвление по первому символу лексемы. Пробел: сдвинули курсор. Цифра: ели цифры подряд, собрали number (числа только неотрицательные целые, отрицательные это вопрос синтаксиса выражений, про них упражнение). Кавычка: открыли строковую константу, и тут SQL-тонкость: одинарную кавычку внутри экранируют удвоением, 'it''s ok' это it's ok. Буква или подчёркивание: ели слово, перевели в верхний регистр, проверили по KEYWORDS, есть это keyword, нет это ident. Если строка не закрылась или символ неожиданный, зовём fail, который бросает SqlError.

Заметь две функции с разными ролями. scan бросает, и его зовёт парсер напрямую (ему удобнее работать с массивом токенов и ловить общий бросок один раз на весь разбор). tokenize это публичный вход для тех, кому нужны только токены: он sqlResult(() => scan(source)), то есть ловит бросок в Result. Дальше распознавание оператора и классификаторы.

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

const PUNCTUATION: Record<string, Token['type'] | undefined> = {
  '(': 'lparen',
  ')': 'rparen',
  ',': 'comma',
  '.': 'dot',
  ';': 'semicolon',
};

/** Распознать оператор в текущей позиции, двухсимвольные раньше односимвольных. */
function readOperator(source: string, position: number): string | null {
  const pair = source.slice(position, position + 2);
  if (pair === '<=' || pair === '>=' || pair === '<>') {
    return pair;
  }
  const single = source[position]!;
  if ('=<>+-*/'.includes(single)) {
    return single;
  }
  return null;
}

function isWhitespace(character: string): boolean {
  return character === ' ' || character === '\t' || character === '\n' || character === '\r';
}

function isDigit(character: string): boolean {
  return character >= '0' && character <= '9';
}

function isIdentStart(character: string): boolean {
  return (
    (character >= 'a' && character <= 'z') ||
    (character >= 'A' && character <= 'Z') ||
    character === '_'
  );
}

function isIdentPart(character: string): boolean {
  return isIdentStart(character) || isDigit(character);
}

readOperator пробует двухсимвольные операторы (<=, >=, <>) раньше односимвольных, иначе <= распался бы на < и =. Классификаторы символов тривиальны.

AST: размеченные объединения

Дерево разбора это набор размеченных объединений по полю kind. Парсер их строит, принтер печатает, binder урока 6 резолвит. Чистые типы, совпадают с TS-треком.

// src/sql/ast.ts
import type { ColumnType } from '~/schema.ts';

// -------- выражения --------

export type BinaryOp =
  | '=' | '<>' | '<' | '<=' | '>' | '>='
  | '+' | '-' | '*' | '/'
  | 'AND' | 'OR' | 'LIKE';

export type Literal =
  | { readonly kind: 'number'; readonly value: bigint }
  | { readonly kind: 'string'; readonly value: string }
  | { readonly kind: 'bool'; readonly value: boolean }
  | { readonly kind: 'null' };

export interface LiteralExpr {
  readonly kind: 'literal';
  readonly literal: Literal;
}

export interface ColumnExpr {
  readonly kind: 'column';
  readonly table?: string;
  readonly name: string;
}

export interface BinaryExpr {
  readonly kind: 'binary';
  readonly op: BinaryOp;
  readonly left: Expr;
  readonly right: Expr;
}

export interface UnaryExpr {
  readonly kind: 'unary';
  readonly op: 'NOT';
  readonly operand: Expr;
}

export type Expr = LiteralExpr | ColumnExpr | BinaryExpr | UnaryExpr;

// -------- выражения внутри SELECT --------

export type SelectItem =
  | { readonly kind: 'star' }
  | { readonly kind: 'expr'; readonly expr: Expr; readonly alias?: string };

export interface Join {
  readonly type: 'inner' | 'left';
  readonly table: string;
  readonly on: Expr;
}

export interface OrderBy {
  readonly column: string;
  readonly direction: 'asc' | 'desc';
}

// -------- операторы (statements) --------

export interface ColumnDefinition {
  readonly name: string;
  readonly type: ColumnType;
  readonly constraint?: 'primaryKey' | 'notNull';
}

export interface CreateTableStmt {
  readonly kind: 'createTable';
  readonly table: string;
  readonly columns: readonly ColumnDefinition[];
}

export interface InsertStmt {
  readonly kind: 'insert';
  readonly table: string;
  readonly columns?: readonly string[];
  readonly values: readonly Literal[];
}

export interface SelectStmt {
  readonly kind: 'select';
  readonly items: readonly SelectItem[];
  readonly from: string;
  readonly join?: Join;
  readonly where?: Expr;
  readonly orderBy?: OrderBy;
  readonly limit?: number;
}

export interface Assignment {
  readonly column: string;
  readonly value: Expr;
}

export interface UpdateStmt {
  readonly kind: 'update';
  readonly table: string;
  readonly assignments: readonly Assignment[];
  readonly where?: Expr;
}

export interface DeleteStmt {
  readonly kind: 'delete';
  readonly table: string;
  readonly where?: Expr;
}

export type Statement = CreateTableStmt | InsertStmt | SelectStmt | UpdateStmt | DeleteStmt;

Тип колонки ColumnType мы импортируем из ~/schema.ts (урок 3), чтобы фронтенд и слой данных говорили об int, text, bool одинаково. Statement это объединение пяти операторов. EXPLAIN и транзакционные команды это отдельные верхнеуровневые формы, их добавим в уроки 6 и 7, когда им будет что обслуживать.