golang

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

  • пятница, 14 марта 2025 г. в 00:00:15
https://habr.com/ru/articles/890382/

Всем привет! В продолжение прошлой статьи, где мы залезли в компилятор 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 {

  }
}
Рисунок 1. Пример вложенности в Go
Рисунок 1. Пример вложенности в Go

Все операторы (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