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

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

Зачем. Сегодня начинается верхняя половина движка: обработка запросов. Пользователь не должен знать про RID, страницы и пины. Он пишет SELECT name FROM users WHERE id = 42, а движок сам решает, как это исполнить. Между строкой и исполнением стоит фронтенд: лексер режет строку на токены, парсер собирает из токенов дерево. Это прямое продолжение твоего опыта с парсерами из раздела про алгоритмы, но впервые на настоящей грамматике реляционного языка.

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

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

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

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

Что мы парсим

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

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

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

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

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

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

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

Токены

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

// 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 или AND. Ключевое слово мы храним в верхнем регистре, поэтому select, Select и SELECT дадут один и тот же токен keyword со значением SELECT. ident это идентификатор, имя таблицы или колонки, и его мы храним как есть, с сохранением регистра. number и string несут распознанное значение. Дальше идут операторы и пунктуация: скобки, запятая, точка (для table.column), точка с запятой. И eof это часовой конца потока: парсеру удобно, когда поток всегда заканчивается явным токеном, тогда не надо отдельно проверять выход за границу массива.

KEYWORDS это множество, а не список, потому что лексер на каждом слове делает по нему один has, и хочется чтобы это было дёшево.

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

Прежде чем писать лексер, заведём ему способ ругаться. Когда разбор спотыкается, недостаточно бросить Error('syntax error'). Пользователь хочет видеть, где именно. Поэтому ошибка несёт смещение, а рендер собирает из него человекочитаемое сообщение со стрелкой под местом сбоя.

// src/sql/errors.ts

export class SqlError extends Error {
  readonly offset: number;

  constructor(message: string, offset: number) {
    super(message);
    this.name = 'SqlError';
    this.offset = offset;
  }
}

/** Собрать сообщение с позицией и стрелкой `^` под местом ошибки. */
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 это обычная ошибка плюс поле offset. Тесты будут проверять именно его: смещение должно точно указывать на проблемный символ. renderSqlError переводит линейное смещение в пару строка и колонка. Логика прямая: идём от начала до смещения, считаем переводы строки (\n), запоминаем начало текущей строки. Колонка это смещение минус начало строки. Дальше вырезаем саму строку текста и строим caret: столько пробелов, сколько символов до ошибки, и ^. В консоли это выглядит так:

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

Видно сразу: после SELECT ждали выражение, а наткнулись на FROM. Эта мелочь отличает игрушку от инструмента, которым приятно пользоваться.

Лексер

Теперь сам лексер. Это один проход по строке с курсором position. На каждом шаге смотрим текущий символ и решаем, какой токен начинается. Пробелы пропускаем, всё остальное собираем в токены.

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

export function tokenize(source: string): Token[] {
  const tokens: Token[] = [];
  let position = 0;

  const fail = (message: string, offset: number): never => {
    throw new SqlError(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;
}

Цикл устроен как ветвление по первому символу лексемы. Пробел: сдвинули курсор, пошли дальше. Цифра: ели цифры подряд, собрали number. Числа у нас только неотрицательные целые; отрицательные это вопрос синтаксиса выражений, и про них есть упражнение.

Кавычка: открыли строковую константу. Тут одна тонкость, ради которой стоит держать SQL-совместимость. Внутри строки одинарную кавычку экранируют её удвоением: 'it''s ok' это строка it's ok. Поэтому, встретив кавычку внутри, мы смотрим на следующий символ: если это тоже кавычка, добавляем одну в значение и перешагиваем обе; иначе строка закончилась. Если строка не закрылась до конца ввода, падаем с понятной ошибкой, указывая на открывающую кавычку.

Буква или подчёркивание: ели слово, переводим в верхний регистр и проверяем по KEYWORDS. Есть в множестве это keyword, нет это ident (с сохранением исходного регистра). Вот почему ключевые слова и имена не путаются: решает одна проверка по множеству.

Дальше операторы и пунктуация, их вынесем в маленькие помощники. И в самом низу: если ни одна ветка не сработала, символ неожиданный, падаем с указанием на него. В конце дописываем eof.

Осталась мелочёвка: распознавание оператора и классификаторы символов.

// 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

Парсер строит дерево, а тип дерева надо описать заранее. Узлы AST это размеченные объединения: каждый узел несёт поле kind, по которому TypeScript узнаёт его вариант. Начнём с выражений, это рекурсивная часть.

// 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;

Выражение это одно из четырёх. LiteralExpr оборачивает литерал: число (хранится как bigint, тот же int на восемь байт, что в куче из урока 3), строку, булево или null. ColumnExpr это ссылка на колонку, с необязательной квалификацией таблицей (users.id против просто id). BinaryExpr это бинарная операция: оператор и два поддерева. UnaryExpr пока ровно один, NOT. Тип Expr рекурсивен: BinaryExpr содержит два Expr, и так вглубь. Именно эта рекурсия и есть дерево.

Дальше формы внутри SELECT и сами операторы.

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

// -------- части 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;

SelectItem это либо звёздочка (SELECT *), либо выражение с необязательным алиасом (name AS n). Join, OrderBy это вспомогательные части. Дальше пять операторов, каждый со своим kind. Обрати внимание на ? у where, join, orderBy, limit, columns: эти части необязательны, и если их в запросе не было, поля в узле просто нет. ColumnDefinition.type берётся из ~/schema.ts (тот самый ColumnType из урока 3), чтобы фронтенд и слой данных говорили об одних и тех же типах. Statement это объединение всех пяти. Всё, тип дерева описан, можно его строить.