Запускаем код на Go снизу вверх

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

В этой статье, как небольшое дополнение к предыдущей, я хочу рассмотреть, как Go работает с AST, и заодно реализовать конструкцию InverseCode{} (название Inverse оказалось занято пакетом math), которая будет читать код снизу вверх.

Вот примерный результат, который мы получим:

alek.dmitriev@alek-dmitriev habr % cat main.go package main  import "fmt"  func main() {          inversecode {                 fmt.Println("start")                 fmt.Println("end")         }  }   alek.dmitriev@alek-dmitriev habr % go/bin/go run main.go end start

Предподготовка.

Первым делом добавим нашу конструкцию InverseCode{} в компилятор. Чтобы не повторяться, отмечу, что большинство шагов схожи с теми, что описаны в предыдущей статье. Однако есть и некоторые отличия.

syntax/nodes.go

В отличие от цикла while, в данном случае нам не нужны дополнительные операторы, такие как условие, инициализация или пост-действие. Поэтому в нашей структуре InverseCodeStmt оставим только поле body, в котором будет находиться сам код.

WhileStmt struct { Init SimpleStmt Cond Expr Post SimpleStmt Body *BlockStmt stmt }  InverseCodeStmt struct { Body *BlockStmt stmt }

Погружаемся в структуру Body

Давайте внимательнее рассмотрим, что представляет собой поле Body. По сути, это ещё один statement, с типомBlockStmt. В Go BlockStmt относится к оператору { }, то есть к блоку кода. В Go можно использовать фигурные скобки без операторов, и внутри них будет своя область видимости. Хотя в реальной жизни я не встречал практического применения этой возможности, всё равно интересно, что она существует.

Внутри блока мы увидим следующий код:

BlockStmt struct { List   []Stmt Rbrace Pos stmt }

Что такое BlockStmt?

• Реализует интерфейс Stmt: это означает, что блок кода сам по себе является оператором.

• Хранит слайс других Stmt: внутри блока могут находиться другие операторы, которые также могут быть блоками. Это создает возможность для большой вложенности.

while True {   if a == b {     if b != c {      }   } else {    } }

Все операторы (Stmt), которые находятся внутри блока, добавляются в слайс в определённом порядке. Именно этот порядок определяет, как код будет обрабатываться и выполняться. Чтобы реализовать нашу задумку — выполнение кода в обратном порядке — нам нужно изменить порядок записи этих операторов в слайс или изменить порядок чтения.

Меняем порядок выполнения кода.

В этой статье мы опустим полный цикл компилятора и сосредоточимся на том, как строится AST (абстрактное синтаксическое дерево) и как происходит его обход. Чтобы понять, как именно мы можем изменить порядок выполнения кода, нам нужно подробнее изучить пакеты cmd/compile/internal/syntax и cmd/compile/internal/walk. Именно здесь происходит построение, обход и преобразование дерева перед генерацией машинного кода.

Построение дерева

Чтобы изменить порядок выполнения программы на этапе построения AST, нам нужно изменить логику записи операторов (statements) в слайс. Запись происходит во время парсинга, поэтому давайте перейдем в файл parser.go и внимательно изучим, что там происходит.

func (p *parser) inverseCodeStmt() Stmt { if trace { defer p.trace("inverseCodeStmt")() }  s := new(InverseCodeStmt) s.pos = p.pos()  s.Body = p.blockStmt("inversecode clause") return s }

На примере WhileStmt мы можем написать обработчик для inverseCode. Однако, в отличие от WhileStmt, нам не нужны переменные Init и Cond. В нашем случае они отсутствуют. Вместо этого нас интересует только Body, который представляет собой обработчик для блока.

// context must be a non-empty string unless we know that p.tok == _Lbrace. func (p *parser) blockStmt(context string) *BlockStmt { if trace { defer p.trace("blockStmt")() }  s := new(BlockStmt) s.pos = p.pos()  // people coming from C may forget that braces are mandatory in Go if !p.got(_Lbrace) { p.syntaxError("expected { after " + context) p.advance(_Name, _Rbrace) s.Rbrace = p.pos() // in case we found "}" if p.got(_Rbrace) { return s } }  s.List = p.stmtList() s.Rbrace = p.pos() p.want(_Rbrace)  return s }

Обработка самого блока нас не интересует. Давайте внимательно изучим метод stmtList, который отвечает за заполнение слайса операторов (List). Именно здесь происходит запись операторов в том порядке, в котором они встречаются в исходном коде. Этот метод вызывается при обработке блоков кода, таких как inverseCode, while, if и других.

// StatementList = { Statement ";" } . func (p *parser) stmtList() (l []Stmt) { if trace { defer p.trace("stmtList")() }  for p.tok != _EOF && p.tok != _Rbrace && p.tok != _Case && p.tok != _Default { s := p.stmtOrNil() p.clearPragma() if s == nil { break } l = append(l, s) // ";" is optional before "}" if !p.got(_Semi) && p.tok != _Rbrace { p.syntaxError("at end of statement") p.advance(_Semi, _Rbrace, _Case, _Default) p.got(_Semi) // avoid spurious empty statement } } return }

Что происходит в этом методе?

1. Цикл for:

   • Метод проходит по всем операторам в блоке кода, пока не достигнет конца файла (_EOF), закрывающей фигурной скобки (_Rbrace) или ключевых слов case/default (в случае switch).

2. Получение оператора:

   • s := p.stmtOrNil() — получаем следующий оператор из исходного кода.

   • Если оператор равен nil, цикл прерывается.

3. Запись оператора в слайс:

   • l = append(l, s) — оператор добавляется в конец слайса l.

   • Это ключевая строка, которая определяет порядок выполнения операторов.

4. Обработка точки с запятой:

   • В Go точка с запятой (;) не обязательна перед закрывающей фигурной скобкой (}).

   • Если точка с запятой отсутствует и следующий токен не является }, выводится ошибка синтаксиса.

Как изменить порядок записи операторов?

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

Измененный метод stmtList:

func (p *parser) stmtReverseList() (l []Stmt) {     if trace {         defer p.trace("stmtList")()     }      for p.tok != _EOF && p.tok != _Rbrace && p.tok != _Case && p.tok != _Default {         s := p.stmtOrNil()         p.clearPragma()         if s == nil {             break         }         // Добавляем оператор в начало слайса         l = append([]Stmt{s}, l...)         // ";" is optional before "}"         if !p.got(_Semi) && p.tok != _Rbrace {             p.syntaxError("at end of statement")             p.advance(_Semi, _Rbrace, _Case, _Default)             p.got(_Semi) // avoid spurious empty statement         }     }     return }

Что изменилось?

• l = append([]Stmt{s}, l...) — оператор s добавляется в начало слайса l.

• В результате операторы будут записаны в обратном порядке.

Итого

Теперь, когда мы написали кастомный метод stmtReverseList для записи операторов в обратном порядке, давайте интегрируем его в обработку нашего кастомного блока inverseCode.

// context must be a non-empty string unless we know that p.tok == _Lbrace. func (p *parser) blockReverseStmt(context string) *BlockStmt { if trace { defer p.trace("blockStmt")() }  s := new(BlockStmt) s.pos = p.pos()  // people coming from C may forget that braces are mandatory in Go if !p.got(_Lbrace) { p.syntaxError("expected { after " + context) p.advance(_Name, _Rbrace) s.Rbrace = p.pos() // in case we found "}" if p.got(_Rbrace) { return s } }  s.List = p.stmtList() s.Rbrace = p.pos() p.want(_Rbrace)  return s }  func (p *parser) inverseCodeStmt() Stmt { if trace { defer p.trace("inverseCodeStmt")() }  s := new(InverseCodeStmt) s.pos = p.pos()  s.Body = p.blockInverseStmt("inversecode clause") return s } 

Альтернативный подход: чтение statement’ов в обратном порядке

Запись дерева в обратном порядке — это не единственный способ решения задачи. Мы также можем изменить порядок чтения statement’ов (операторов) во время обхода AST. Давайте разберемся, как это можно сделать. Для этого перейдем в пакет walk, где происходит обход и преобразование дерева перед генерацией машинного кода.

Шаг 1: Добавляем кейс для InverseCode

В методе walkStmt мы добавляем новый кейс для нашего оператора InverseCode. Этот кейс будет срабатывать, когда компилятор встречает наш оператор в AST. Внутри кейса мы преобразуем узел дерева в тип *ir.InverseCodeStmt и вызываем специальную функцию для его обработки.

case ir.OINVERSECODE: n := n.(*ir.InverseCodeStmt) return walkInverseCode(n)

Шаг 2: Реализуем функцию walkInverseCode

Функция walkInverseCode будет отвечать за обработку нашего оператора InverseCode. Её задача — пройтись по всем операторам внутри блока InverseCode и обработать их. Для этого мы вызываем вспомогательную функцию walkInverseCodeStmtList, которая отвечает за обход списка операторов.

func walkInverseCode(n *ir.InverseCodeStmt) ir.Node { walkInverseCodeStmtList(n.Body) return n }

Шаг 3: Обход операторов в обратном порядке

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

func walkInverseCodeStmtList(s []ir.Node) { // Обходим список операторов в обратном порядке for i := len(s) - 1; i >= 0; i-- { s[i] = walkStmt(s[i]) } }

Итого

В итоге мы получаем две разные реализации одного и того же, но с одним большим НО. Возможно, внимательный читатель уже догадался об этом, но всё-таки полноценно этот код идти снизу вверх не будет. Так как операторы с вложенностью, такие как if, else, Block и другие, он воспринимает как операторы целиком, не заглядывая внутрь блока. Команды в блоке будут работать в привычном нам порядке, но на первом уровне вложенности — в обратном. После компиляции мы получаем примерно следующее:

alek.dmitriev@alek-dmitriev habr % cat main.go package main  import "fmt"  func main() {         inversecode {                 if i == 1 {                         if i == 1 {                                 fmt.Printf("start")                         }                         i = i + 1                 }                 if i == 0 {                         if i == 0 {                                 fmt.Printf("end")                         }                         i = i + 1                 }                 i := 0         } } alek.dmitriev@alek-dmitriev habr % go/bin/go run main.go end start