Обновление от 2022-08-09: процесс компиляции несколько изменился с момента написания оригинальной статьи, из-за чего она была актуализирована до версии Go 1.19.

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

Мы собираемся изменить компилятор Go, добавив новую (условно) языковую фичу, и собрать модифицированный компилятор, чтобы ее опробовать.

Задача — добавление нового оператора

Многие языки имеют оператор while, который в Go выражается с помощью for:

for <some-condition> {
  <loop body>
}

Добавление оператора while в Go было бы тривиальным — почти такое же как и для for (возможно, ограничив варианты того, что может сделать этот оператор). Поэтому я выбрал немного более сложную задачу — добавить until. until это то же самое, что и while, за исключением того, что условие для него будет противоположным. Например, этот код:

i := 4
until i == 0 {
  i--
  fmt.Println("Hello, until!")
}

Эквивалентен:

i := 4
for i != 0 {
  i--
  fmt.Println("Hello, until!")
}

Мы могли бы использовать инициализатор в объявлении цикла следующим образом:

until i := 4; i == 0 {
  i--
  fmt.Println("Hello, until!")
}

Наша реализация это поддерживает.

Обязательный дисклеймер — это просто тренировочное упражнение. Я не думаю, что добавление until в Go — это вообще хорошая идея; Минимализм Go является его преимуществом.

Высокоуровневая структура компилятора Go 

Дефолтный компилятор Go (gc) имеет довольно традиционную структуру, которая должна быть вам знакома, если вы раньше уже работали с другими компиляторами: 

Относительно корня репозитория Go реализация компилятора находится в src/cmd/compile/internal; все пути кода, упомянутые далее в посте, будут относительно этого каталога. Все это написано на Go, поэтому код довольно читабелен. В этом посте мы будем рассматривать эти этапы один за другим, добавляя необходимый код для поддержки оператора until .

Ознакомьтесь с README в src/cmd/compile, где вы найдете подробное пошаговое описание этапов компиляции. Этот файл является хорошим дополнением к этой статье.

Сканирование

Сканер (также известный как лексер) разбивает текст исходного кода на отдельные элементы для компилятора. Например, слово for становится константой _For; символы ... становятся _DotDotDot, а одна . становится _Dot и так далее.

Сканер реализован в пакете syntax. Все, что нам нужно от него здесь, это чтобы он понял новое ключевое слово — until. Файл syntax/tokens.go содержит список всех токенов, понятных компилятору, и мы добавим туда новый:

_Fallthrough // fallthrough
_For         // for
_Until       // until
_Func        // func

Комментарий с правой стороны от константы токена не так важен, так как он используется для идентификации токена в тексте. Это делается с помощью генерации кода из tokens.go, в котором есть эта строка над списком токенов

//go:generate stringer -type token -linecomment

go generate должен быть запущен вручную а результирующий файл (syntax/token_string.go) отражается в репозитории исходного кода Go. Чтобы восстановить его, я выполнил следующую команду из каталога syntax:

GOROOT=<src checkout> go generate tokens.go

Настройка GOROOT очень важна по версии Go 1.12, и должна указывать на корень исходного кода, где мы модифицируем компилятор.

Запустив генератор кода и убедившись, что token_string.go теперь имеет новый токен, я попытался пересобрать компилятор и столкнулся с паникой:

panic: imperfect hash

Это происходит из этого кода в syntax/scanner.go:

// Предполагается, что длина s не меньше 2.
func hash(s []byte) uint {
  return (uint(s[0])<<4 ^ uint(s[1]) + uint(len(s))) & uint(len(keywordMap)-1)
}

var keywordMap [1 << 6]token // size must be power of two

func init() {
  // заполняем keywordMap
  for tok := _Break; tok <= _Var; tok++ {
    h := hash([]byte(tok.String()))
    if keywordMap[h] != 0 {
      panic("imperfect hash")
    }
    keywordMap[h] = tok
  }
}

Компилятор пытается построить "идеальную" хэш-таблицу для выполнения поиска строки ключевого слова в по токенам. Под “идеальной” подразумевается отсутствие коллизий, а только линейный массив, в котором каждое ключевое слово соответствует одному индексу. Хэш-функция довольно специфична (например, она просматривает только содержимое первых символов строкового токена), и отладить, почему новый токен создает коллизии, очень непросто. Чтобы обойти это, я увеличил размер таблицы поиска, изменив его на [1 << 7]token, тем самым изменив размер массива поиска с 64 до 128. Это дает хэш-функции гораздо больше места для распределения своих ключей, и коллизии закончились.

Парсинг

Go имеет достаточно стандартный парсер с рекурсивным спуском, который преобразует поток токенов, выдаваемых сканером, в конкретное синтаксическое дерево (CST). Мы начнем с добавления нового типа узла для until в синтаксис/nodes.go:

UntilStmt struct {
  Init SimpleStmt
  Cond Expr
  Body *BlockStmt
  stmt
}

Я позаимствовал общую структуру из ForStmt, которая используется для циклов for. Как и в случае с for, наш until имеет несколько необязательных подоператоров:

until <init>; <cond> {
  <body>
}

И <init> и <cond> — опциональные, хотя не принято опускать <cond>. Встроенное поле UntilStmt.stmt используется для всех операторов синтаксического дерева и содержит информацию о позиции.

Сам синтаксический анализ выполняется в syntax/parser.go. Метод parser.stmtOrNil анализирует оператор в текущей позиции. Он просматривает текущий токен и принимает решение о том, какой оператор анализировать. Вот фрагмент кода, который мы добавляем:

switch p.tok {
case _Lbrace:
  return p.blockStmt("")

// ...

case _For:
  return p.forStmt()

case _Until:
  return p.untilStmt()

И это untilStmt:

func (p *parser) untilStmt() Stmt {
  if trace {
    defer p.trace("untilStmt")()
  }

  s := new(UntilStmt)
  s.pos = p.pos()

  s.Init, s.Cond, _ = p.header(_Until)
  s.Body = p.blockStmt("until clause")

  return s
}

Мы повторно используем существующий parser.header , который анализирует заголовок для if и for . В самом общем виде он поддерживает три части (разделенные точкой с запятой). В for третья часть может использоваться для оператора «post», но мы не собираемся поддерживать это для until, нас интересуют только первые два. Обратите внимание, что header позволяет токену источника различать типы операторов, которые он обслуживает; например, он отклонил бы оператор “post” для if. Мы должны явно отклонить его и для unti тоже, хотя я не удосужился реализовать это прямо сейчас.

Это все изменения, которые нам нужны для парсера. Поскольку структура  until очень похожа на существующие операторы, мы могли бы повторно использовать большую часть функциональности.

Если мы позволяем компилятору вывести синтаксическое дерево (используя syntax.Fdump) после того как мы распарсили и запустились с ним:

i = 4
until i == 0 {
  i--
  fmt.Println("Hello, until!")
}

Мы получим этот фрагмент для оператора until:

84  .  .  .  .  .  3: *syntax.UntilStmt {
 85  .  .  .  .  .  .  Init: nil
 86  .  .  .  .  .  .  Cond: *syntax.Operation {
 87  .  .  .  .  .  .  .  Op: ==
 88  .  .  .  .  .  .  .  X: i @ ./useuntil.go:13:8
 89  .  .  .  .  .  .  .  Y: *syntax.BasicLit {
 90  .  .  .  .  .  .  .  .  Value: "0"
 91  .  .  .  .  .  .  .  .  Kind: 0
 92  .  .  .  .  .  .  .  }
 93  .  .  .  .  .  .  }
 94  .  .  .  .  .  .  Body: *syntax.BlockStmt {
 95  .  .  .  .  .  .  .  List: []syntax.Stmt (2 entries) {
 96  .  .  .  .  .  .  .  .  0: *syntax.AssignStmt {
 97  .  .  .  .  .  .  .  .  .  Op: -
 98  .  .  .  .  .  .  .  .  .  Lhs: i @ ./useuntil.go:14:3
 99  .  .  .  .  .  .  .  .  .  Rhs: *(Node @ 52)
100  .  .  .  .  .  .  .  .  }
101  .  .  .  .  .  .  .  .  1: *syntax.ExprStmt {
102  .  .  .  .  .  .  .  .  .  X: *syntax.CallExpr {
103  .  .  .  .  .  .  .  .  .  .  Fun: *syntax.SelectorExpr {
104  .  .  .  .  .  .  .  .  .  .  .  X: fmt @ ./useuntil.go:15:3
105  .  .  .  .  .  .  .  .  .  .  .  Sel: Println @ ./useuntil.go:15:7
106  .  .  .  .  .  .  .  .  .  .  }
107  .  .  .  .  .  .  .  .  .  .  ArgList: []syntax.Expr (1 entries) {
108  .  .  .  .  .  .  .  .  .  .  .  0: *syntax.BasicLit {
109  .  .  .  .  .  .  .  .  .  .  .  .  Value: "\"Hello, until!\""
110  .  .  .  .  .  .  .  .  .  .  .  .  Kind: 4
111  .  .  .  .  .  .  .  .  .  .  .  }
112  .  .  .  .  .  .  .  .  .  .  }
113  .  .  .  .  .  .  .  .  .  .  HasDots: false
114  .  .  .  .  .  .  .  .  .  }
115  .  .  .  .  .  .  .  .  }
116  .  .  .  .  .  .  .  }
117  .  .  .  .  .  .  .  Rbrace: syntax.Pos {}
118  .  .  .  .  .  .  }
119  .  .  .  .  .  }

Проверка типов

Следующим шагом в компиляции является проверка типов, которая выполняется в синтаксическом дереве и задействует пакет types2 [1]. В дополнение к обнаружению ошибок с типами, проверка типов в Go также включает в себя выведение типов, что позволяет нам писать такие операторы, как:

res, err := func(args)

без объявления типов res и err явным образом. Средство проверки типов Go выполняет еще несколько задач, таких как связывание идентификаторов с их объявлениями и вычисление констант времени компиляции. Код находится в types2/. Еще раз, следуя for, мы добавим это предложение в свитч в методе stmt в Checker:

case *syntax.UntilStmt:
  inner |= breakOk | continueOk

  check.openScope(s, "until")
  defer check.closeScope()

  check.simpleStmt(s.Init)
  if s.Cond != nil {
    var x operand
    check.expr(&x, s.Cond)
    if x.mode != invalid && !allBoolean(x.typ) {
      check.error(s.Cond, "non-boolean condition in for statement")
    }
  }
  check.stmt(inner, s.Body)

Создание AST

Теперь, когда у нас есть синтаксическое дерево с проверенными типами, компилятор строит абстрактное синтаксическое дерево (AST). Я уже писал об абстрактных и конкретных синтаксических деревьях в предыдущих статьях — вам стоит разобраться в этой теме, если вы не знакомы с различиями. Однако в случае Go в будущем это может измениться. Компилятор Go изначально был написан на C, а затем автоматически транслирован на Go; некоторые его части являются рудиментами из старых C-дней, а некоторые новые. Будущие рефакторинги могут оставить только один тип синтаксического дерева, но на данный момент (Go 1.19) мы должны следовать этому процессу.

Код AST находится в пакете ir, а типы узлов определены в ir/node.go и ir/stmt.go.

Мы начнем с добавления новой константы для идентификации узла until в ir/node.go:

// операторы
// ...
OFALL     // fallthrough
OFOR      // for Init; Cond; Post { Body }
OUNTIL

Мы снова запустим go generate, на этот раз для ir/node.go, чтобы сгенерировать строковое представление для нового типа узла:

// из каталога ir
GOROOT=<src checkout> go generate node.go

Это должно обновить файл gc/op_string.go, включив в него OUNTIL [2]. Еще один инструмент, который нам нужно запустить, — это mknode.go из того же каталога. Этот инструмент генерирует дополнительный код для нового узла:

// из каталога ir
GOROOT=<src checkout> <checkout/bin>go run -mod=mod mknode.go

Теперь давайте определим типы узлов AST для нашего нового оператора.

type UntilStmt struct {
  miniStmt
  Label    *types.Sym
  Cond     Node
  Body     Nodes
  HasBreak bool
}

func NewUntilStmt(pos src.XPos, init Node, cond Node, body []Node) *UntilStmt {
  n := &UntilStmt{Cond: cond}
  n.pos = pos
  n.op = OUNTIL
  if init != nil {
    n.init = []Node{init}
  }
  n.Body = body
  return n
}

Нам также потребуется обновить ir/fmt.go , чтобы иметь возможность форматировать/выводить наш новый узел для дебага:

// ... добавить это в OpNamse слайс
OFOR:         "for",
OUNTIL:       "until",

А также этот пункт для свича в методе stmtFmt:

case OUNTIL:
  n := n.(*UntilStmt)
  opname := "for"
  if !exportFormat {
    fmt.Fprintf(s, "%s loop", opname)
    break
  }

  fmt.Fprint(s, opname)
  if simpleinit {
    fmt.Fprintf(s, " %v;", n.Init()[0])
  }

  if n.Cond != nil {
    fmt.Fprintf(s, " %v", n.Cond)
  }

  if simpleinit {
    fmt.Fprint(s, ";")
  }

  fmt.Fprintf(s, " { %v }", n.Body)

Наконец, компонент noder отвечает за фактическое преобразование синтаксических деревьев в AST; мы добавим этот код в noder/stmt.go:

// в метод stmt irgen...

case *syntax.ForStmt:
  return g.forStmt(stmt)
case *syntax.UntilStmt:
  return g.untilStmt(stmt)

И новый метод:

func (g *irgen) untilStmt(stmt *syntax.UntilStmt) ir.Node {
  return ir.NewUntilStmt(g.pos(stmt), g.stmt(stmt.Init), g.expr(stmt.Cond), g.blockStmt(stmt.Body))
}

Анализ и перезапись AST

После проверки типов компилятор проходит несколько этапов анализа и перезаписи AST. Точная последовательность изложена в функции gc.Main в gc/main.go. В номенклатуре компиляторов такие этапы обычно называют проходами (passes).

Многие проходы не требуют модификаций для поддержки until, потому что они реагируют обобщенно на все виды операторов (здесь приходит на выручку обобщенная структура gc.Node). Однако некоторым все-таки это нужно. Например, escape-анализ, который пытается найти, какие переменные “сбегают” из области видимости своей функции и, следовательно, должны быть размещены в куче, а не в стеке.

Escape-анализ работает для каждого типа оператора, поэтому мы должны добавить этот пункт свича в escape.stmt:

case ir.OUNTIL:
  n := n.(*ir.UntilStmt)
  e.loopDepth++
  e.discard(n.Cond)
  e.block(n.Body)
  e.loopDepth--

Теперь мы подходим к завершающему этапу основной работы с компилятором: переписываем AST. Этот шаг называется "walk" в номенклатуре компилятора Go. Его основная цель — разложить сложные операции на более простые, чтобы бэкенду приходилось иметь дело с меньшим количеством типов операций.

Нам придется обновить walk/order.go, чтобы объявить о добавленном нами новом узле AST. Он мало что делает, за исключением того, что служит сквозным каналом для трансформации:

case ir.OUNTIL:
  n := n.(*ir.UntilStmt)
  t := o.markTemp()
  n.Cond = o.exprInPlace(n.Cond)
  n.Body.Prepend(o.cleanTempNoPop(t)...)
  orderBlock(&n.Body, o.free)
  o.out = append(o.out, n)
  o.cleanTemp(t)

Остальной код walk собирает набор трансформаций AST, которые впоследствии помогают сократить AST до SSA. Например, он переписывает range в for на более простые формы for с явной переменной цикла [3]. Он также переписывает доступ к map для вызовы во время выполнения и делает еще многое чего полезного.

Именно здесь мы реализуем наш новый оператор until, превратив его в for с инвертированным условием.

Мы начнем с обработки новой операции в свиче в walkStmt (этот код находится в walk/stmt.go):

case ir.OUNTIL:
  n := n.(*ir.UntilStmt)
  return walkUntil(n)

И добавляем walkUntil следующим образом:

func walkUntil(n *ir.UntilStmt) ir.Node {
  if n.Cond != nil {
    init := ir.TakeInit(n.Cond)
    walkStmtList(init)
    n.Cond = ir.NewUnaryExpr(base.Pos, ir.ONOT, walkExpr(n.Cond, &init))
    n.Cond = ir.InitExpr(init, n.Cond)
  }

  walkStmtList(n.Body)
  return ir.NewForStmt(n.Pos(), nil, n.Cond, nil, n.Body)
}

Вот и все! Это перепишет узел UntilStmt в узел ForStmt, добавляя унарное логическое отрицание (по сути, !) к условию, как мы проговаривали в самом начале поста.

Тестирование

Теперь мы можем протестировать наш модифицированный компилятор на примере программы, которая содержит оператор until:

$ cat useuntil.go
package main

import "fmt"

func main() {
  i := 4
  until i == 0 {
    i--
    fmt.Println("Hello, until!")
  }
}

$ <src checkout>/bin/go run useuntil.go
Hello, until!
Hello, until!
Hello, until!
Hello, until!

Все работает!

Напоминание: <src checkout> — это каталог, в который мы извлекли Go, изменили его и скомпилировали (подробнее смотрите в Приложении).

Заключение первой части

На этом мы заканчиваем первую часть. Мы успешно реализовали новый оператор в компиляторе Go. Мы не рассмотрели все части компилятора, потому что мы могли сократить работу, переписав AST, чтобы вместо узлов until использовались узлы for. Это совершенно валидная стратегия компиляции, и компилятор Go уже имеет много подобных трансформаций для канонизации AST (сокращение до меньшего количества форм, чтобы на последних этапах компиляции было меньше работы). Тем не менее, мы по-прежнему заинтересованы в изучении последних двух этапов компиляции — Преобразовать в SSA и сгенерировать машинный код. Об этом мы расскажем во второй части.

Приложение — сборка инструментария Go

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

Есть два пути:

1. Клонировать официальный репозиторий Go и внести изменения, описанные в этом посте.

2. (рекомендуется) Клонируйте мой форк репозитория Go и проверьте ветку adduntil-119-part1 , где все эти изменения уже применены вместе с некоторыми хелперами для дебага.

Клонированный каталог — это куда указывает <src checkout> на протяжении всего поста.

Чтобы скомпилировать инструментарий, войдите в src/ и запустите ./make.bash. Вы также можете запустить ./all.bash для запуска тестов после его сборки. Выполнение make.bash запускает полный трехэтапный процесс начальной построения Go, но даже на моем старом компьютере это занимает всего около минуты.

После сборки инструментарий устанавливается в bin вместе с src. Затем мы можем выполнить более быструю пересборку самого компилятора, запустив bin/go install cmd/compile.

---

[1] Пакет types2 — это порт (на внутренние структуры данных компилятора) алгоритмов проверки типов в go/types. Он синхронизируется с go/types.

[2] Если вы просмотрите эту и связанные с ней части кода компилятора, вы заметите, что есть еще один опкод под названием OFORUNTIL. Этот узел реализует цикл for, в котором условие проверяется в конце итерации; он используется внутри компилятора для преобразования некоторых циклов и недоступен программистам Go. Мы проигнорируем это в целях этой статьи.

[3] В Go есть несколько специальных “волшебных” операторов range, таких как range по строке, который разбивает ее на руны. Вот где реализованы такие трансформации.

---

В ближайший час состоится открытое занятие по внутреннему устройству каналов Go. На занятии вы узнаете:
- что происходит под капотом, когда Go работает с каналами;
- когда каналы без буфера лучше, чем с буфером;
- и как записать данные из одной горутины в стэк другой.
Если интересно, заходите по ссылке.