Конструирование типов и детекция циклов в Go 1.26

Перевод/заметки Type Construction and Cycle Detection.

Статическая типизация в Go - важная причина, почему язык хорошо подходит для надёжных продакшен-систем. Когда компилятор обрабатывает пакет Go, он сначала выполняет синтаксический анализ: парсер превращает исходный код в абстрактное синтаксическое дерево (AST). Затем это дерево передаётся проверщику типов (type checker).

В этом посте мы разберём часть тайпчекера, которую существенно обновили в Go 1.26. Что это меняет для разработчика? Если вы не любитель экзотических и запутанных объявлений типов, то ничего не заметите. Главная цель переработки - сократить число редких случаев и подготовить почву для будущих улучшений языка. Заодно это хороший повод заглянуть во внутренности компилятора: вещь, которая кажется банальной в коде Go, скрывает немало нюансов.

Но для начала: что вообще делает тайпчекер? Этот этап компиляции отсекает целые классы ошибок ещё на этапе сборки. В частности, тайпчекер проверяет два условия:

1. Типы в AST валидны (например, тип ключа в map должен удовлетворять ограничению comparable).
2. Операции с этими типами или их значениями допустимы (нельзя, к примеру, сложить int и string).

Чтобы выполнить эти проверки, тайпчекер строит внутреннее представление каждого типа при обходе AST. Этот процесс неофициально называют конструированием типов (type construction).

Хотя система типов Go известна своей простотой, в некоторых уголках языка конструирование типов оказывается неожиданно сложным.

Конструирование типов

Начнём с простой пары объявлений:

type T []U
type U *int

Когда компилятор доходит до T, в AST фиксируется объявление типа с именем T и выражением типа []U. T - это defined type, то есть новый тип, созданный определением type T ... без знака =. Чтобы представить внутреннюю структуру данных, которую тайпчекер использует для таких типов, будем использовать структуру Defined.

Структура Defined содержит указатель на тип, полученный из выражения справа от имени. Поле underlying указывает на базовый тип (underlying type). Проследим, как обход AST заполняет структуры данных.

Начнём с состояния:

На этом этапе тип T находится в процессе конструирования (отмечен жёлтым цветом). Выражение []U мы ещё не вычисляли (оно всё ещё чёрное), поэтому underlying содержит nil (обозначено пустой стрелкой).

При вычислении []U тайпчекер создаёт структуру Slice - внутреннее представление срезов. Как и Defined, она содержит указатель на тип элемента. Мы ещё не выяснили, какой тип обозначает имя U, поэтому этот указатель тоже пока равен nil:

Чтобы превратить имя U в тип, компилятор находит его объявление. Видя, что U - это ещё один defined type, мы создаём отдельную структуру Defined для U. Справа от U находится выражение *int, которое вычисляется в структуру Pointer, где базовым типом является int.

Когда мы вычисляем int, происходит кое-что особенное: мы получаем предобъявленный (predeclared) тип. Такие типы создаются до того, как тайпчекер начнёт обход AST. Поскольку тип int уже сконструирован, нам остаётся только сослаться на него.

Теперь картина выглядит так:

Обратите внимание: тип Pointer на этом этапе полностью завершён (завершённость отмечена зелёным цветом). Завершённость (completeness) означает, что все поля внутренней структуры данных заполнены, а все типы, на которые они ссылаются, также завершены. Это критически важное свойство: оно гарантирует, что анализ внутренней структуры типа (deconstruction) безопасен и мы располагаем всей информацией о нём.

В нашей схеме структура Pointer содержит только поле base, указывающее на int. У int нет полей для заполнения, поэтому он завершён автоматически, а вместе с ним завершён и тип *int.

Далее тайпчекер разворачивает стек вызовов обратно. Поскольку *int завершён, мы можем завершить тип U. Завершение U позволяет завершить []U, а затем и T. В итоге все типы становятся завершёнными:

Цифры на схеме показывают порядок завершения типов (после Pointer). Обратите внимание, что тип в самом низу завершился первым. Конструирование типов естественным образом происходит в глубину (depth-first), так как для завершения типа сначала должны завершиться все его зависимости.

Рекурсивные типы

С простым примером разобрались, усложним задачу. Система типов Go позволяет выражать рекурсивные типы. Типичный пример - связный список или дерево:

type Node struct {
    next *Node
}

Вернёмся к нашему примеру и добавим рекурсию, заменив *int на *T:

type T []U
type U *T

Проследим выполнение. Компилятор снова начинает с T, но пропустим первые шаги. К моменту вычисления *T тайпчекер приходит в следующее состояние:

Возникает вопрос: что записать в качестве базового типа для *T? У нас уже есть объект для T (структура Defined), но он прямо сейчас находится в процессе конструирования (его поле underlying всё ещё nil).

Тайпчекер просто указывает поле base в *T на T, несмотря на то что T пока не завершён:

Мы делаем это в расчёте на то, что T завершит конструирование в будущем (указав на завершённый тип). Когда это произойдёт, base будет указывать на готовый тип, и *T станет завершённым.

Тем временем мы начинаем подъём по стеку вызовов:

Когда мы возвращаемся на самый верх и заканчиваем конструирование T, «петля» типов замыкается, и все типы в цикле завершаются одновременно:

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

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

При этом многие проверки требуют деконструкции типа. Классический пример - проверка того, что ключ map является comparable. Для этого компилятору нужно заглянуть в поле underlying. Как безопасно работать с неполными типами вроде T?

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

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

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

Рекурсивные типы и значения

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

Рассмотрим следующий пример:

type T [unsafe.Sizeof(T{})]int

Как и в прошлый раз, тайпчекер доходит до следующего состояния:

Чтобы сконструировать Array, компилятору нужно вычислить его размер. В выражении unsafe.Sizeof(T{}) требуется узнать размер типа T. А для вычисления размера массива (такого как T) необходимо деконструировать тип: заглянуть внутрь, узнать длину массива и размер каждого элемента.

Иными словами, конструирование Array требует деконструкции T. Значит, Array не может завершить конструирование (и тем более стать завершённым), пока не завершится T. Старый трюк с одновременно замыкающейся петлёй типов здесь не работает.

Мы попадаем в тупик:

• T не может завершиться, пока не завершится Array.
• Array не может завершиться, пока не завершится T.
• Завершить их одновременно невозможно (в отличие от предыдущего случая).

Эти условия невозможно выполнить. Что делать тайпчекеру?

Детекция циклов

Такой код некорректен: размер T невозможно определить, не зная размера T, независимо от устройства компилятора. Зацикленное определение размера - лишь частный случай ошибок циклического определения (cycle errors). В этот же класс входит, например, объявление type T T, хотя и по другим причинам. Поиск таких ошибок во время проверки типов называют детекцией циклов (cycle detection).

Как работает детекция циклов для type T [unsafe.Sizeof(T{})]int? Посмотрим на выражение T{}. Это составной литерал, и тайпчекер понимает, что итоговое значение имеет тип T. Но поскольку T не завершён, значение T{} является неполным значением.

Здесь нужна осторожность: работа с неполным значением безопасна только в том случае, если операция не требует деконструкции типа этого значения. Например, выражение type T [unsafe.Sizeof(new(T))]int валидно, так как значение new(T) (типа *T) не требует деконструкции - все указатели имеют одинаковый размер на данной платформе. Размер неполного значения типа *T вычислить можно, а типа T - нельзя.

Указатель *T сам по себе несёт достаточно информации для unsafe.Sizeof, тогда как одно имя T не раскрывает его базовый тип. На практике операция с неполным значением небезопасна, если его тип - defined type: одно лишь имя типа не сообщает ничего о его внутреннем устройстве.

Где ловить циклы

До сих пор мы рассматривали прямые вызовы unsafe.Sizeof. В коде type T [unsafe.Sizeof(T{})]int вызов unsafe.Sizeof является корнем выражения размера массива. Но неполное значение T{} легко представить и как операнд в более сложном выражении.

Например, его можно передать в функцию (type T [unsafe.Sizeof(f(T{}))]int), взять срез (type T [unsafe.Sizeof(T{}[:])]int), обратиться по индексу (type T [unsafe.Sizeof(T{}[0])]int) и так далее. Все эти варианты некорректны, так как требуют деконструкции T. К примеру, индексация T требует проверки его базового типа. Выражения, которые «потребляют» неполные значения, назовём выражениями-потребителями (downstreams). Их очень много, и некоторые синтаксически не очевидны.

С другой стороны, T{} - лишь один из примеров выражений, «порождающих» неполные значения. Назовём их выражениями-источниками (upstreams):

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

type T [unsafe.Sizeof(T(42))]int                // приведение типа (conversion)

func f() T
type T [unsafe.Sizeof(f())]int                  // вызов функции

var i interface{}
type T [unsafe.Sizeof(i.(T))]int                // утверждение типа (type assertion)

type T [unsafe.Sizeof(<-(make(<-chan T)))]int   // чтение из канала

type T [unsafe.Sizeof(make(map[int]T)[42])]int  // доступ к элементу map

type T [unsafe.Sizeof(*new(T))]int              // разыменование указателя

// ... и ещё несколько редких случаев

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

Например, при вычислении приведения типа type T [unsafe.Sizeof(T(42))]int обработчик в тайпчекере выглядит примерно так:

func callExpr(call *syntax.CallExpr) operand {
  x := typeOrValue(call.Fun)
  switch x.mode() {
  // ... другие случаи
  case typeExpr:
    // T(), то есть приведение типа
    T := x.typ()
    // ... обработка приведения, T НЕБЕЗОПАСНО деконструировать
  }
}

Заметив, что CallExpr - это приведение к T, компилятор знает, что результат выражения будет иметь тип T. И прежде чем передавать операнд типа T дальше по цепочке, мы проверяем T на завершённость:

func callExpr(call *syntax.CallExpr) operand {
  x := typeOrValue(call.Fun)
  switch x.mode() {
  // ... другие случаи
  case typeExpr:
    // T(), то есть приведение типа
    T := x.typ()
+   if !isComplete(T) {
+     reportCycleErr(T)
+     return invalid
+   }
    // ... обработка приведения, T БЕЗОПАСНО деконструировать
  }
}

Вместо возврата операнда с незавершённым типом мы возвращаем специальный операнд invalid. Это сигнал остальному тайпчекеру о том, что выражение вычислить не удалось. Таким образом мы не даём неполным значениям «утечь» дальше к выражениям-потребителям, а сразу сообщаем об ошибке циклического определения в T.

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

Итог

Систематическая детекция циклов с участием неполных значений появилась в тайпчекере Go 1.26. До этого релиза использовался более сложный алгоритм конструирования типов со специальными проверками циклов, которые срабатывали не всегда. Новый, более простой подход устранил ряд паник компилятора на редких конструкциях (см. задачи #75918, #76383, #76384, #76478 и другие) и сделал компилятор стабильнее.

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