Своя СУБД на Go · урок 5: свой SQL, лексер и парсер
Кому это. К этому уроку у тебя собрана вся нижняя половина движка на Go. В уроке 1 появились page.Page и disk.Manager, в уроке 2 над диском встал буферный пул под мьютексом, в уроке 3 выросла куча, в уроке 4 к ней добавился B+Tree. Получилось индексированное хранилище ключей. Но звать h.Insert и tree.Search руками это ещё не СУБД. СУБД понимает язык.
Зачем это на Go. Сегодня начинается верхняя половина движка: обработка запросов. Между строкой SELECT name FROM users WHERE id = 42 и исполнением стоит фронтенд: лексер режет строку на токены, парсер собирает дерево. После четырёх уроков с байтами, пинами и мьютексами этот слой выглядит отпуском: ни диска, ни горутин, только строки и деревья. Зато здесь Go показывает три приёма, которых в нижних слоях не было. Закрытое множество вариантов узла (в Go нет размеченных объединений, их собирают из интерфейса). Разница между байтом и символом в строке. И паника как законный ранний выход из глубокой рекурсии, которая наружу всё равно выходит обычным error.
Важно про код. Как и прежде, ты пишешь реализацию с нуля, листинги приведены целиком, а где сокращены, это сказано прямо. Весь урок живёт в одном пакете ourdb/sql: файлы token.go, errors.go, lexer.go, ast.go, parser.go, printer.go и тест lesson05_sql_test.go. Пакет называется sql, как и стандартный database/sql, но конфликта нет: импортируем мы его по полному пути "ourdb/sql", а если когда-нибудь понадобятся оба, один получит псевдоним. Сторонних модулей по-прежнему ноль, только стандартная библиотека Go 1.23.
Где мы в движке
┌────────────────────────────────────────────────┐
│ Бинарный протокол + 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
│ disk.Manager (страницы поверх файла) │ урок 1
└────────────────────────────────────────────────┘Заметь важное: фронтенд не трогает нижние слои совсем. Пакет sql не импортирует ни heap, ни btree, ни bufferpool. Единственная связь с хранилищем это тип колонки tuple.ColumnType: фронтенд и куча должны одинаково понимать, что такое int, text и bool. Связать дерево с реальными таблицами это работа binder в уроке 6. Поэтому весь сегодняшний код это чистые функции: вход строка или дерево, выход дерево или строка, плюс error, если не сложилось.
Граф импортов Go это проверяет за тебя. Если однажды рука потянется вызвать из парсера каталог таблиц, компилятор напомнит про направление зависимостей: engine импортирует sql, а обратная стрелка дала бы цикл импортов, которого Go не терпит.
Что мы парсим
Парсер начинается не с кода, а с грамматики. Мы берём небольшое подмножество SQL, которого хватает на весь воркшоп. Записывается грамматика в EBNF, нотации, которая один в один ложится на парсер рекурсивного спуска. Грамматика общая для всех портов ourdb, она та же, что в TS-треке.
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 и 8. Ключевые слова для них лексер узнаёт уже сегодня (так проще не переделывать таблицу потом), но Parse пока разбирает пять операторов работы с данными и отдаёт ровно один Statement.
Граница Go: паника внутри, error снаружи
Прежде чем писать код, договоримся, как этот слой обходится с ошибками. В нижних уроках правило было простым: каждая функция, которая может не сложиться, возвращает последним значением error, а вызывающий проверяет его сразу. disk.Manager.ReadPage, pool.FetchPage, h.Insert все так устроены. Почему бы и парсеру не жить по тому же правилу?
Посмотри, как устроен рекурсивный спуск. selectStmt зовёт expr, expr зовёт primary, primary в скобках снова зовёт expr. Сбой может случиться на любой глубине: primary глубоко внутри expr внутри selectStmt вдруг видит FROM там, где ждал выражение. Если каждая функция возвращает (Expr, error), то каждая строка парсера обрастает проверкой: прочитал ключевое слово, проверил ошибку, прочитал имя, проверил ошибку, разобрал выражение, проверил ошибку. В selectStmt таких шагов больше десяти. Логика “читаем токен за токеном” тонет в обвязке, хотя на каждый if err != nil ответ один и тот же: бросить всё и вернуть ошибку наверх.
Go даёт для этого механизм, о котором в уроке про ошибки сказано “только для неустранимых ситуаций”: panic и recover. Правило верное для границ пакета, и у него есть известное исключение, описанное прямо в Effective Go: пакет может внутри себя бросать панику со своим типом ошибки как ранний выход из глубокой рекурсии, если на своей границе ловит её через recover и превращает в обычный error. Effective Go показывает это на парсере регулярных выражений, README порта сравнивает приём со стандартным go/parser. Мы делаем так же:
- внутри пакета
sqlметодfailбросаетpanic(*Error), и паника пролетает сквозь все рекурсивные вызовы до самого верха; - на границе
Parseзапускает разбор через помощникcatch, который вdeferловит панику, и если это наш*Error, кладёт его в возвращаемыйerror; - чужая паника (выход за срез, разыменование nil, то есть баг) пробрасывается дальше как есть: прятать баг под видом синтаксической ошибки нельзя.
Снаружи Tokenize, Parse и Print это обычные функции Go. Вызывающий видит (Statement, error) и никогда не узнает, что внутри была паника. Это та же прагматика, что изменяемый накопитель внутри чистой функции: локальный приём не портит контракт, потому что Parse(s) на одну строку всегда возвращает одно и то же.
Лексер, кстати, паникой не пользуется. Он плоский: один цикл без рекурсии, и ошибка в нём возникает в двух местах. Там обычный return nil, err честнее и короче.
Конвейер из трёх чистых функций
Весь урок это три функции в конвейере:
строка SQL ── Tokenize ──▶ []Token ── Parse ──▶ Statement ── Print ──▶ строка SQL
│ │
└──── error ───────────┴──── (*sql.Error со смещением)Tokenize режет строку на токены, Parse собирает из токенов дерево (и сам зовёт Tokenize), Print печатает дерево обратно в SQL. Третья функция нужна, чтобы проверять парсер (round-trip), а в уроке 6 ею печатаются имена вычисляемых колонок, в уроке 7 через неё DDL попадает в журнал. Поехали снизу вверх.
Токены
Токен это распознанная лексема с пометкой вида и позицией. Позиция (Offset) нужна не парсеру, а пользователю: по ней покажем, где сломался запрос.
// sql/token.go
// Package sql это фронтенд диалекта (урок 5): лексер, парсер рекурсивным спуском плюс Pratt
// для выражений, AST и pretty-printer (SPEC.md, раздел "Грамматика SQL").
package sql
// TokenType это вид токена.
type TokenType string
const (
TokKeyword TokenType = "keyword"
TokIdent TokenType = "ident"
TokNumber TokenType = "number"
TokString TokenType = "string"
TokOperator TokenType = "operator"
TokLParen TokenType = "lparen"
TokRParen TokenType = "rparen"
TokComma TokenType = "comma"
TokDot TokenType = "dot"
TokSemicolon TokenType = "semicolon"
TokEOF TokenType = "eof"
)
// Token это лексема: для keyword в верхнем регистре, для string распознанное значение.
type Token struct {
Type TokenType
Value string
Offset int
}
// Keywords это ключевые слова диалекта (сравнение без учёта регистра).
var Keywords = map[string]bool{
"SELECT": true, "FROM": true, "WHERE": true, "INSERT": true, "INTO": true, "VALUES": true,
"CREATE": true, "TABLE": true, "UPDATE": true, "SET": true, "DELETE": true, "EXPLAIN": true,
"BEGIN": true, "COMMIT": true, "ROLLBACK": true, "ORDER": true, "BY": true, "ASC": true,
"DESC": true, "LIMIT": true, "AS": true, "INNER": true, "LEFT": true, "JOIN": true, "ON": true,
"AND": true, "OR": true, "NOT": true, "LIKE": true, "TRUE": true, "FALSE": true, "NULL": true,
"INT": true, "TEXT": true, "BOOL": true, "PRIMARY": true, "KEY": true,
}Здесь два решения, которые стоит проговорить.
Вид токена это строковый тип, а не iota. Классический Go-рефлекс для перечисления это type TokenType int и константы через iota. Но число в выводе теста ничего не говорит: want 3, got 7 придётся расшифровывать по исходнику. Строковый TokenType печатается сам собой, %v выдаст keyword, и тест может сравнить string(tok.Type) с "keyword" без таблицы перевода. Цена одна: сравнение строк дороже сравнения чисел, но лексер не горячий путь движка, запрос разбирается один раз. Отдельный именованный тип при этом сохраняет типобезопасность: функция, ждущая TokenType, не примет случайную строку из переменной без явного приведения.
Множество ключевых слов это map[string]bool. В Go нет встроенного типа множества, и его собирают из map двумя способами: map[string]struct{} (ноль байт на значение) или map[string]bool. Мы берём второй ради одной строки в лексере: Keywords[upper] для отсутствующего ключа вернёт нулевое значение false, поэтому проверка “это ключевое слово?” пишется одним выражением без _, ok :=. Три десятка лишних байтов на всю программу того стоят.
Остальное как в TS-треке. keyword хранится в верхнем регистре, поэтому select, Select и SELECT дают один токен. ident это имя таблицы или колонки, оно хранится как есть. number и string несут распознанное значение. eof это часовой конца потока: парсеру удобнее, когда поток всегда заканчивается явным токеном, и peek никогда не выходит за срез.
Ошибки с позицией: *sql.Error
Прежде чем писать лексер, заведём ему способ ругаться. Когда разбор спотыкается, недостаточно вернуть errors.New("syntax error"). Пользователь хочет видеть, где именно.
// sql/errors.go
package sql
import (
"fmt"
"strings"
"unicode/utf8"
)
// Error это ошибка разбора SQL. Offset это байтовое смещение в исходнике; Error() показывает
// строку, колонку (в символах) и стрелку под местом ошибки.
type Error struct {
Msg string
Offset int
}
func (e *Error) Error() string { return e.Msg }
// newError собирает сообщение с позицией и стрелкой `^`.
func newError(source string, offset int, format string, args ...any) *Error {
msg := fmt.Sprintf(format, args...)
clamped := min(max(offset, 0), len(source))
lineStart := strings.LastIndexByte(source[:clamped], '\n') + 1
line := strings.Count(source[:clamped], "\n") + 1
lineEnd := strings.IndexByte(source[lineStart:], '\n')
if lineEnd < 0 {
lineEnd = len(source)
} else {
lineEnd += lineStart
}
col := utf8.RuneCountInString(source[lineStart:clamped])
rendered := fmt.Sprintf("%s (строка %d, колонка %d)\n%s\n%s^",
msg, line, col+1, source[lineStart:lineEnd], strings.Repeat(" ", col))
return &Error{Msg: rendered, Offset: offset}
}Error это обычная структура с методом Error() string, а значит, она удовлетворяет встроенному интерфейсу error без всякого объявления. Метод висит на указателе *Error, поэтому ошибкой считается именно *Error, и тест будет доставать её через errors.As с переменной типа *sql.Error. Подробно этот приём разобран в уроке про кастомные ошибки.
Сообщение собирается один раз, в момент создания, и кладётся в Msg уже со стрелкой. Можно было бы хранить исходник и рисовать стрелку лениво в Error(), но тогда каждая ошибка тащила бы за собой весь текст запроса. Разбор падает редко, а сообщение нужно почти всегда, поэтому считаем сразу.
Логика позиции короткая, потому что пакет strings делает всю чёрную работу. strings.LastIndexByte(source[:clamped], '\n') + 1 находит начало текущей строки: последний перевод строки до места ошибки плюс один (а если перевода нет, -1 + 1 даёт ноль, начало текста). strings.Count считает переводы строки до ошибки, это номер строки. strings.IndexByte от начала строки ищет её конец. clamped страхует от смещения за пределами текста: встроенные min и max появились в Go 1.21, и с ними зажим в диапазон пишется одним выражением.
Байт или символ
Вот место, где Go заставляет подумать о том, о чём TS-трек молчит. Строка в Go это последовательность байтов в UTF-8, и len(s), s[i] и срезы s[a:b] работают с байтами. Буква В в UTF-8 занимает два байта, а @ один. Подробно это разобрано в уроке про строки, байты и руны.
Поэтому у ошибки две разные позиции:
Offsetв байтах. Это индекс вsource, по нему код режет строку:source[:clamped]иsource[lineStart:lineEnd]обязаны получать байтовые индексы, иначе срез разрежет букву пополам.- Колонка в символах. Это то, что видит человек.
utf8.RuneCountInString(source[lineStart:clamped])считает руны от начала строки до ошибки, и ровно столько пробелов встаёт перед стрелкой.
Проверим на запросе с кириллицей в строковой константе:
неожиданный символ "@" (строка 1, колонка 37)
SELECT * FROM t WHERE name = 'Вася' @
^Смещение @ в байтах равно 40: четыре буквы Вася дали восемь байтов вместо четырёх. А колонка 37, и стрелка стоит точно под @. Если бы мы рисовали стрелку по байтам, она уехала бы на четыре позиции вправо. У TS-порта и смещение, и колонка в единицах UTF-16, поэтому там такой развилки нет; README Go-порта отмечает это расхождение отдельно.
На обычном запросе сообщение выглядит так:
ожидалось выражение, встретилось ключевое слово FROM (строка 1, колонка 8)
SELECT FROM t
^Видно сразу: после SELECT ждали выражение, а наткнулись на FROM. Эта мелочь отличает игрушку от инструмента, которым приятно пользоваться.
Лексер
Теперь сам лексер. Это один проход по строке с курсором pos. На каждом шаге смотрим текущий байт и решаем, какой токен начинается.
// sql/lexer.go
package sql
import (
"strconv"
"strings"
"unicode/utf8"
)
var punctuation = map[byte]TokenType{'(': TokLParen, ')': TokRParen, ',': TokComma, '.': TokDot, ';': TokSemicolon}
// Tokenize режет строку SQL на плоский поток токенов. Строки в одинарных кавычках с `''`
// как экранированной кавычкой, числа это неотрицательные целые, `<=`, `>=`, `<>` ловятся
// заглядыванием на символ вперёд.
func Tokenize(source string) ([]Token, error) {
var tokens []Token
pos := 0
for pos < len(source) {
c := source[pos]
start := pos
switch {
case c == ' ' || c == '\t' || c == '\n' || c == '\r':
pos++
case isDigit(c):
for pos < len(source) && isDigit(source[pos]) {
pos++
}
tokens = append(tokens, Token{TokNumber, source[start:pos], start})
case c == '\'':
var value strings.Builder
for pos++; ; {
if pos >= len(source) {
return nil, newError(source, start, "незакрытая строковая константа")
}
if source[pos] == '\'' {
if pos+1 < len(source) && source[pos+1] == '\'' {
value.WriteByte('\'')
pos += 2
continue
}
pos++
break
}
value.WriteByte(source[pos])
pos++
}
tokens = append(tokens, Token{TokString, value.String(), start})
case isIdentStart(c):
for pos < len(source) && (isIdentStart(source[pos]) || isDigit(source[pos])) {
pos++
}
word := source[start:pos]
if upper := strings.ToUpper(word); Keywords[upper] {
tokens = append(tokens, Token{TokKeyword, upper, start})
} else {
tokens = append(tokens, Token{TokIdent, word, start})
}
default:
if op := readOperator(source, pos); op != "" {
tokens = append(tokens, Token{TokOperator, op, start})
pos += len(op)
} else if typ, ok := punctuation[c]; ok {
tokens = append(tokens, Token{typ, string(c), start})
pos++
} else {
r, _ := utf8.DecodeRuneInString(source[pos:])
return nil, newError(source, start, "неожиданный символ %s", strconv.Quote(string(r)))
}
}
}
return append(tokens, Token{TokEOF, "", pos}), nil
}Цикл устроен как switch без выражения: Go проверяет ветки case сверху вниз и берёт первую истинную, это короче лестницы if/else if. Пройдём по веткам.
Пробел. Сдвинули курсор, пошли дальше. Никакого continue не нужно: в Go ветка switch не проваливается в следующую, и после неё цикл просто идёт на новый круг.
Цифра. Ели цифры подряд и собрали number. Значение токена это срез source[start:pos], и он не копирует байты: подстрока в Go делит память с исходной строкой. Числа у нас только неотрицательные целые; отрицательные это вопрос синтаксиса выражений, и про них есть упражнение. Литерал в число превратит уже парсер, и там нас ждёт проверка на переполнение int64.
Кавычка. Открыли строковую константу. Внутри строки одинарную кавычку экранируют удвоением: 'it''s ok' это строка it's ok. Поэтому, встретив кавычку внутри, смотрим на следующий байт: если это тоже кавычка, кладём одну в значение и перешагиваем обе; иначе строка закончилась. Значение копится в strings.Builder, потому что строку собираем по байту, а склейка через += на каждом шаге копировала бы весь накопленный текст заново.
Две тонкости этой ветки стоит увидеть глазами. Первая: for pos++; ; { ... } это цикл без условия с одним начальным действием, он перешагивает открывающую кавычку и дальше крутится, пока его не прервут изнутри. Вторая: break внутри него. В Go break внутри switch выходит из switch, а не из цикла, и на этом регулярно спотыкаются. Здесь ловушки нет: ближайшая к break конструкция это внутренний for, а не внешний switch, поэтому break закрывает строковый цикл, и мы идём дописывать токен. Если строка не закрылась до конца ввода, возвращаем ошибку, указывая на открывающую кавычку (start), а не на конец текста: так человек сразу видит, какая из кавычек осталась без пары.
Буква или подчёркивание. Ели слово, перевели в верхний регистр и проверили по Keywords. Есть в таблице, значит keyword; нет, значит ident с исходным регистром. Ключевые слова и имена не путаются, потому что решает одна проверка по таблице. Обрати внимание на форму if upper := strings.ToUpper(word); Keywords[upper]: переменная upper живёт только внутри if и else, снаружи её нет.
Всё остальное. Сначала пробуем оператор, потом пунктуацию через map punctuation (снова typ, ok :=, потому что здесь нулевое значение "" для отсутствующего ключа было бы ложным видом токена). Ни то ни другое не подошло, значит символ неожиданный. В конце дописываем eof, и его смещение это pos, длина текста: стрелка ошибки “встретилось конец запроса” встанет сразу за последним символом.
Почему байтовый лексер не ломает UTF-8
Лексер смотрит на source[pos], то есть на байт, а не на символ. Казалось бы, на кириллице он должен развалиться. Не развалится, и причина в устройстве UTF-8: все байты многобайтного символа больше 0x7F, а все символы синтаксиса SQL (буквы латиницы, цифры, кавычка, скобки, операторы) это ASCII, меньше 0x80. Байт из середины буквы я никогда не совпадёт с ' или (. Поэтому:
- внутри строковой константы байты кириллицы копируются в
strings.Builderкак есть и собираются обратно в ту же букву; - вне строки байт кириллицы не проходит ни одну ветку и падает в
default.
В последнем случае и пригодился utf8.DecodeRuneInString. Он декодирует целую руну, начиная с pos, и сообщение показывает букву целиком:
неожиданный символ "и" (строка 1, колонка 8)
SELECT имя FROM t
^Возьми мы string(c) от одного байта, в сообщении оказался бы обломок буквы, невалидный UTF-8, а strconv.Quote напечатал бы его как "\xd0". Имена в нашем диалекте только латиницей, это ограничение грамматики, а не лексера: расширить isIdentStart до unicode.IsLetter над рунами можно, но тогда лексеру придётся шагать по рунам, а не по байтам.
Операторы и классификаторы
// sql/lexer.go (продолжение)
func readOperator(source string, pos int) string {
if pair := source[pos:min(pos+2, len(source))]; pair == "<=" || pair == ">=" || pair == "<>" {
return pair
}
if strings.IndexByte("=<>+-*/", source[pos]) >= 0 {
return source[pos : pos+1]
}
return ""
}
func isDigit(c byte) bool { return c >= '0' && c <= '9' }
func isIdentStart(c byte) bool { return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c == '_' }readOperator показывает классическую ловушку лексера: правило самого длинного совпадения. Сначала пробуем пару (<=, >=, <>), потом одиночный символ. Перепутаешь порядок, и <= распадётся на < и =.
Срез source[pos:min(pos+2, len(source))] берёт два байта, а у последнего символа строки один: min не даёт выйти за конец, и паники выхода за границы не будет. Пустая строка "" вместо “нет оператора” это идиома Go для функции, у которой нулевое значение результата никогда не бывает правильным ответом: настоящий оператор пустым не бывает, поэтому отдельный флаг ok не нужен. isIdentStart полагается на приоритеты операторов Go: && крепче ||, поэтому скобки вокруг диапазонов не нужны, gofmt их и не просит.
Прогоним лексер на запросе из начала урока:
keyword "SELECT" @0
ident "name" @7
keyword "FROM" @12
ident "users" @17
keyword "WHERE" @23
ident "id" @29
operator "=" @32
number "42" @34
eof "" @36Лексер готов. Это первая из трёх функций: строка зашла, []Token или error вышли.
AST: закрытые интерфейсы
Парсер собирает AST, и вот где Go заметнее всего расходится с TS. В TypeScript узел выражения это размеченное объединение: type Expr = LiteralExpr | ColumnExpr | BinaryExpr | UnaryExpr, и поле kind говорит, какой это вариант. В Go размеченных объединений нет. Есть интерфейсы, и из них собирают то же самое.
Код ниже сокращён: настоящий ast.go уже содержит верхнеуровневую форму Command и узлы Explain и Txn для уроков 6-8. Их мы добавим, когда до них дойдёт дело.
// sql/ast.go (без Command, Explain и Txn: они появятся в уроке 6)
package sql
import "ourdb/tuple"
// -------- выражения --------
// Expr это узел выражения: *Literal, *Column, *Binary или *Unary.
type Expr interface{ expr() }
// LiteralKind это вид литерала.
type LiteralKind string
const (
LitNumber LiteralKind = "number"
LitString LiteralKind = "string"
LitBool LiteralKind = "bool"
LitNull LiteralKind = "null"
)
// Literal это литерал; значимо только поле его вида.
type Literal struct {
Kind LiteralKind
Int int64
Str string
Bool bool
}
// Column это ссылка на колонку, Table пуст без квалификатора.
type Column struct {
Table string
Name string
}
// Binary это бинарный оператор: = <> < <= > >= + - * / AND OR LIKE.
type Binary struct {
Op string
Left, Right Expr
}
// Unary это NOT.
type Unary struct {
Operand Expr
}
func (*Literal) expr() {}
func (*Column) expr() {}
func (*Binary) expr() {}
func (*Unary) expr() {}Метод-маркер закрывает множество
Expr interface{ expr() } это интерфейс с одним методом, и метод этот ничего не делает. Его смысл в имени: expr пишется со строчной буквы, значит, он не экспортируется. Реализовать такой интерфейс может только тип из пакета sql: чужой пакет не в силах объявить у своего типа метод sql.expr. Получается закрытое множество из ровно четырёх вариантов, *Literal, *Column, *Binary и *Unary, и добавить пятый можно, только отредактировав ast.go.
Зачем закрывать? Чтобы Expr нельзя было собрать из чего попало. Без маркера, с пустым interface{} (или any), в поле Where легально положить 42 или "hello", и компилятор промолчит. С маркером Where Expr примет только узел выражения. Этот же приём ты встретишь в стандартной библиотеке: так устроены узлы в go/ast. Как работают интерфейсы и any, разобрано в уроке про интерфейсы.
Чего маркер не даёт, так это проверки полноты. В TS switch (expr.kind) без одной ветки компилятор подсветит, если ты попросишь. В Go switch e := e.(type) без ветки *Unary скомпилируется молча, а узел просто не попадёт ни в одну ветку. Поэтому у каждого switch по узлам есть явный путь после всех case: принтер в этом уроке вернёт там пустую строку, binder в уроке 6 вернёт ошибку unknown expression. Если хочется проверки на этапе сборки, для неё есть сторонние линтеры, но воркшоп обходится стандартными go vet и тестами.
Указатели, а не значения
Методы-маркеры объявлены на указателях: func (*Literal) expr(). Это значит, что Expr реализует *Literal, а не Literal. Почему так?
- Узлы деревьев живут на куче и делятся.
Binaryдержит два поддерева. Будь узлы значениями, каждое присваивание копировало бы поддерево целиком. - Сравнение деревьев в тестах.
reflect.DeepEqualидёт по указателям вглубь и сравнивает то, на что они указывают, поэтому&sql.Binary{...}из теста равен&sql.Binary{...}из парсера, хотя адреса разные. - Единообразие. Все варианты указатели, и type switch всегда пишется как
case *Binary:. Смешай значения и указатели, и одна забытая звёздочка вcaseмолча пропустит узел.
Но Literal при этом используется и как значение: Insert.Values это []Literal, а не []*Literal. В списке VALUES стоят только литералы, никакой полиморфизм там не нужен, и срез значений лежит в памяти одним куском, без лишних указателей. Когда литерал становится частью выражения, парсер берёт его адрес: lit := p.literal(); return &lit.
Литерал: одна структура вместо четырёх
Обрати внимание, что Literal это не четыре типа под общим интерфейсом, а одна структура с полем Kind и тремя полями под значения. Комментарий честно предупреждает: “значимо только поле его вида”. Literal{Kind: LitNumber, Int: 42} держит пустые Str и Bool, и их надо просто не читать.
Это компромисс. Отдельные типы NumberLit, StringLit и так далее дали бы строгость (у строкового литерала физически нет поля Int), но каждый потребитель литерала превратился бы во вложенный type switch. Литерал же везде обрабатывается одинаково: switch l.Kind, четыре ветки. Плоская структура сравнима через ==, копируется без выделений памяти, и её нулевое значение Literal{} безвредно. Для узла, у которого нет детей и нет поведения, это разумная цена.
Число хранится в int64. У TS-эталона литерал это bigint без границ, а в Go-порте int колонки это ровно восемь байтов int64 (так записано в контракте байтов из урока 3). Литерал больше int64 поэтому не заворачивается молча, а становится ошибкой разбора. Это мы увидим в парсере.
Операторы
// sql/ast.go (продолжение)
// -------- части SELECT --------
// SelectItem это `*` (Star) или выражение с необязательным алиасом.
type SelectItem struct {
Star bool
Expr Expr
Alias string
}
// Join это INNER или LEFT JOIN.
type Join struct {
Type string // "inner" | "left"
Table string
On Expr
}
// OrderBy это ORDER BY колонка ASC|DESC.
type OrderBy struct {
Column string
Direction string // "asc" | "desc"
}
// -------- операторы --------
// Statement это *CreateTable, *Insert, *Select, *Update или *Delete.
type Statement interface{ statement() }
// ColumnDef это колонка в CREATE TABLE. Constraint: "", "primaryKey" или "notNull".
type ColumnDef struct {
Name string
Type tuple.ColumnType
Constraint string
}
type CreateTable struct {
Table string
Columns []ColumnDef
}
// Insert без списка колонок держит Columns = nil.
type Insert struct {
Table string
Columns []string
Values []Literal
}
type Select struct {
Items []SelectItem
From string
Join *Join
Where Expr
OrderBy *OrderBy
Limit *int
}
type Assignment struct {
Column string
Value Expr
}
type Update struct {
Table string
Assignments []Assignment
Where Expr
}
type Delete struct {
Table string
Where Expr
}
func (*CreateTable) statement() {}
func (*Insert) statement() {}
func (*Select) statement() {}
func (*Update) statement() {}
func (*Delete) statement() {}Statement закрыт тем же приёмом, что и Expr, своим маркером statement(). Два разных маркера нужны, чтобы множества не смешивались: *Select это оператор, но не выражение, и положить его в Where нельзя.
Самое интересное здесь в том, как Go выражает “необязательное”. В TS-эталоне это where?: Expr, поле, которого может не быть. В Go у каждого поля структуры всегда есть значение, поэтому отсутствие кодируется нулевым значением, и для каждого поля оно своё:
Where Exprэто интерфейс, его нулевое значениеnil. НетWHERE, значитs.Where == nil, и принтер с исполнителем проверяют ровно это.Join *JoinиOrderBy *OrderByэто указатели,nilзначит “нет соединения” и “нет сортировки”. Структура без указателя не могла бы отличить “сортировки нет” от “сортировка по пустому имени”.Limit *intуказатель на число. Тут иначе нельзя:LIMIT 0это законный запрос, и нулевое значениеintне отличило бы его от отсутствияLIMIT. Указатель различает “нет” (nil) и “ноль” (&0). Про указатели как способ сказать “значения может не быть” подробно в уроке про указатели.Columns []stringсрез, и комментарий фиксирует контракт: без списка колонокColumns = nil. Не пустой срез[]string{}, а именноnil. Дляlenиrangeразницы нет, ноreflect.DeepEqualразличаетnilи пустой срез, и round-trip тест это заметит. Парсер поэтому заводит срез только черезappend, когда колонки действительно есть.Alias stringиConstraint stringобходятся пустой строкой: пустой алиас и пустое ограничение не бывают осмысленными, нулевое значение тут и значит “нет”.
Тип колонки tuple.ColumnType пришёл из урока 3: фронтенд и хранилище говорят о типах одним языком, и binder в уроке 6 не будет ничего переводить.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.