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

"Абстракция — это наложение слоя незнания поверх реальности." — Ричард Габриэль

Структура каталогов

Структура каталогов проекта Nim:

Самозапуск компилятора

Компиляция компилятора — это просто выполнение:

nim c koch.nim
./koch boot

Для релизной версии используйте:

nim c koch.nim
./koch boot -d:release

А для отладочной версии, совместимой с GDB:

nim c koch.nim
./koch boot --debuginfo --linedir:on

Программа koch — скрипт обслуживания Nim. Это замена make и скриптов на shell с преимуществом большей переносимости. Более подробную информацию о её параметрах можно найти в документации koch.

Рекомендации по написанию кода

• Используйте CamelCase, а не underscored_identifiers.
• Отступы — два пробела.
• Максимальная длина строки — 80 символов.
• Добавляйте пробелы вокруг бинарных операторов, если это улучшает читабельность.
• Используйте пробел после двоеточия, но не перед ним.
• [устарело] Начинайте типы с заглавной T, за исключением указателей/ссылок, которые начинаются с P.

См. также документ проектирование имён API.

Портирование на новые платформы

Портирование Nim на новую архитектуру довольно просто, так как C — самый переносимый язык программирования (в определённых пределах), а Nim генерирует C-код, поэтому портирование генератора кода не требуется.

POSIX-совместимые системы на обычном оборудовании обычно довольно легко портируются: добавьте платформу в platform (если её там ещё нет), проверьте, что модули OS и System работают, и перекомпилируйте Nim.

Единственный случай, когда всё не так просто, — это когда сборщику мусора требуется некоторое изменение на ассемблере для работы. Стандартная версия сборщика мусора использует функцию C setjmp для сохранения всех регистров в стеке аппаратного обеспечения. Возможно, для новой платформы потребуется заменить этот универсальный код некоторым кодом на ассемблере.

Сведения о типе во время выполнения

Сведения о типе во время выполнения (RTTI) необходимы для нескольких аспектов языка программирования Nim:

Сбор мусора

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

Сложные присваивания

Последовательности и строки реализованы как указатели на изменяемые буферы, но Nim требует копирования при присваивании. Помимо RTTI, компилятор мог бы генерировать процедуры копирования для любого типа, которому это нужно. Однако это сделало бы код больше, а RTTI, вероятно, уже есть для сборщика мусора.

Мы уже знаем информацию о типе как граф в компиляторе. Таким образом, нам нужно сериализовать этот граф как RTTI для генерации C-кода. Дополнительную информацию можно найти в файле lib/system/hti.nim.

Перестроение компилятора

После первоначальной сборки с помощью sh build_all.sh на posix или build_all.bat на windows, вы можете перестроить компилятор следующим образом:

• nim c koch если вам нужно перестроить koch
• ./koch boot -d:release это гарантирует, что компилятор может перестроить себя (используйте koch вместо ./koch на Windows), что приводит к 3-кратному построению компилятора.

Более быстрый подход, если вам не нужно выполнять полную самозагрузку, подразумеваемую koch boot, выглядит следующим образом:

• pathto/nim c --lib:lib -d:release -o:bin/nim_temp compiler/nim.nim

Где pathto/nim — любая достаточно свежая двоичная программа Nim (например, bin/nim_cources, построенная во время самозапуска, или $HOME/.nimble/bin/nim, установленная choosenim 1.2.0)

Вы можете передать любые дополнительные параметры, такие как -d:leanCompiler если вам не нужны определённые функции, или -d:debug --stacktrace:on --excessiveStackTrace --stackTraceMsgs для отладки компилятора. См. также Отладка компилятора.

Отладка компилятора

Конечно, вы можете использовать GDB или Visual Studio для отладки компилятора (через --debuginfo --lineDir:on). Однако есть также много процедур, которые помогают в отладке:

# pretty prints the Nim AST
echo renderTree(someNode)
# outputs some JSON representation
debug(someNode)
# pretty prints some type
echo typeToString(someType)
debug(someType)
echo symbol.name.s
debug(symbol)
# pretty prints the Nim ast, but annotates symbol IDs:
echo renderTree(someNode, {renderIds})
if `??`(conf, n.info, "temp.nim"):
  # only output when it comes from "temp.nim"
  echo renderTree(n)
if `??`(conf, n.info, "temp.nim"):
  # why does it process temp.nim here?
  writeStackTrace()

Эти процедуры могут не импортироваться модулем. Вы можете импортировать их непосредственно для отладки:

from astalgo import debug
from types import typeToString
from renderer import renderTree
from msgs import `??`

Чтобы создавать новый компилятор для каждого запуска, используйте koch temp:

./koch temp c /tmp/test.nim

koch temp создаёт отладочную сборку компилятора, что полезно для создания стэков вызовов для отладки компилятора. См. также Перестройка компилятора, если вам нужен больший контроль.

Бисекция для регрессий

koch temp возвращает 125 в качестве кода завершения, если компиляция компилятора завершается неудачно. Этот код завершения сообщает git bisect пропустить текущий коммит:

git bisect start bad-commit good-commit
git bisect run ./koch temp -r c test-source.nim

Вы также можете выполнить бисекцию, используя пользовательские параметры для построения компилятора, например, если вам не нужна отладочная версия компилятора (которая работает медленнее), вы можете заменить ./koch temp явным командным выполнением компиляции, см. Перестройка компилятора.

Архитектура компилятора

Nim использует классическую архитектуру компилятора: лексический анализатор/сканер подаёт токены парсеру. Парсер строит дерево синтаксического разбора, которое используется генератором кода. Это дерево синтаксического разбора — интерфейс между парсером и генератором кода. Важно понять большую часть кода компилятора.

Для правильной компиляции Nim проверка типов должна быть отделена от синтаксического разбора. В противном случае обобщения не будут работать.

Краткое описание модулей Nim

Дерево синтаксического разбора

Дерево синтаксического разбора состоит из узлов, которые могут иметь произвольное количество дочерних элементов. Типы и символы представляются другими узлами, так как они могут содержать циклы. AST изменяет свою форму после семантической проверки. Это необходимо для упрощения работы генераторов кода. См. модуль "ast" для определения типов. Модуль macros содержит много примеров, как AST представляет каждую синтаксическую конструкцию.

Как компилируется RTL

Модуль system содержит часть RTL, которая требует поддержки магией компилятора (и то, что должно быть в нём, так как спецификация так говорит). Генератор C-кода генерирует C-код для него, как и для любого другого модуля. Однако вызовы некоторых процедур, таких как addInt, вставляются CCG. Поэтому модуль magicsys содержит таблицу (compilerprocs) со всеми символами, помеченными как compilerproc. compilerprocs необходимы генератору кода. Процедура magic — не то же самое, что процедура compilerproc: процедура magic — это процедура, которая требует магии компилятора для семантической проверки, а процедура compilerproc — это процедура, используемая генератором кода.

Кэш компиляции

Реализация кэша компиляции непростая: нужно решить много проблем для передней и задней частей.

Общий подход: повторное применение AST

Мы храним AST модуля после успешной семантической проверки в базе данных SQLite. Существует множество функций, которые требуют повторного применения подпоследовательности, например:

{.compile: "foo.c".} # even if the module is loaded from the DB,
                     # "foo.c" needs to be compiled/linked.

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

Фактически, это описывает, как AST должен храниться в базе данных, как «плоское» дерево. Предположим, что мы компилируем модуль m со следующим содержимым:

import strutils

var x*: int = 90
{.compile: "foo.c".}
proc p = echo "p"
proc q = echo "q"
static:
  echo "static"

Концептуально, вот AST, который мы храним для модуля:

import strutils

var x*
{.compile: "foo.c".}
proc p
proc q
static:
  echo "static"

Поле символа ast загружается лениво по запросу. Отсюда и большинство преимуществ: только внешний поверхностный AST восстанавливается немедленно.

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

Общий глобальный состояние компиляции

Nim допускает .global, compiletime переменные, которые могут заполняться вызовами макросов в разных модулях. Эта функция существенно нарушает модульность. Было предложено множество различных решений:

• Ограничить типы глобальных переменных времени компиляции до Set[T] или подобных неупорядоченных, только-растущих коллекций, чтобы мы могли отслеживать эффекты записи модуля в эти переменные и повторно применять изменения в другом порядке.
• При каждой компиляции модуля сбрасывать переменную до её значения по умолчанию.
• Предоставить ограниченный API для загрузки/сохранения состояния компиляции в файл.

(Эти решения не взаимоисключающие.)

Поскольку мы приняли идею «повторного применения операторов верхнего уровня», естественным решением этой проблемы является создание псевдо операторов верхнего уровня, отражающих изменения, внесенные в глобальную переменную. Однако это намного сложнее, чем кажется, например squeaknim использует этот фрагмент:

apicall.add(") module: '" & dllName & "'>\C" &
            "\t^self externalCallFailed\C!\C\C")
stCode.add(st & "\C\t\"Generated by NimSqueak\"\C\t" & apicall)

Мы можем «повторно применить» stCode.add только если значения st и apicall известны. И даже тогда хеш-таблица add с её механизмом хеширования слишком сложна для повторного применения.

На практике всё ещё хуже, рассмотрите someGlobal[i][j].add arg. Мы знаем только корень как someGlobal, но конкретный путь к данным, а также значение, которое добавляется, неизвестны. Мы могли бы вычислить «разницу» между глобальными состояниями и использовать её для вычисления набора исправлений для символов, но это довольно большая работа, дорогостоящая во время выполнения (это потребовало бы выполнения после каждой компиляции модуля), и она также не будет работать для хеш-таблиц.

Нам нужен API, который скрывает сложные проблемы алиасинга, не полагаясь на глобальные переменные Nim. Очевидное решение — использовать строковые ключи вместо глобальных переменных:

proc cachePut*(key: string; value: string)
proc cacheGet*(key: string): string

Однако использование строк/JSON в качестве значений — довольно проблематично: многие таблицы поиска, созданные во время компиляции, содержат процедурные переменные и типы, которые не имеют очевидного строкового представления... Похоже, что сравнение AST по-прежнему лучшая идея, так как это не потребует использования чужеродного API и работает с некоторыми существующими пакетами Nimble, по крайней мере.

С другой стороны, в будущем Nim я хотел бы заменить виртуальную машину на нативный код. Алгоритм сравнения не будет работать в этом случае. Вместо этого нативный код будет работать с API, подобным put, get:

proc cachePut*(key: string; value: NimNode)
proc cacheGet*(key: string): NimNode

API должен поддерживать концепцию сравнения AST: см. модуль macrocache для окончательных деталей.

Методы и преобразователи типов

В следующих разделах под глобальным подразумевается совместно используемый между модулями или свойство всего приложения.

Nim содержит языковые функции, которые являются глобальными. Наиболее ярким примером являются многометоды: добавление нового метода с тем же именем и некоторыми совместимыми параметрами объекта означает, что диспетчер методов должен учитывать новый метод. Таким образом, логика диспетчеризации полностью известна только после перевода всего приложения!

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

# module A
converter toBool(x: int): bool =
  result = x != 0

# module B
import A

if 1:
  echo "ugly, but should work"

Если в вышеприведённом примере модуль B перекомпилируется, но A нет, то B должен учитывать toBool, даже если toBool не ссылается на B явным образом.

Обе проблемы — с многометодами и преобразователями типов — решаются реализацией повторного применения AST.

Обобщения

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

Проблемы с бэкэндом

• Процедуры инициализации не должны «забываться» для вызова.
• Файлы не должны «забываться» для связывания.
• Диспетчеры методов являются глобальными.
• Загрузка DLL через dlsym является глобальной.
• Эмулируемые переменные потоков являются глобальными.

Однако самая большая проблема заключается в том, что удаление мёртвого кода нарушает модульность! Чтобы понять почему, рассмотрим этот сценарий: модуль G (например, огромный модуль Gtk2...) компилируется с включённым удалением мёртвого кода. Таким образом, ни одна из процедур G не генерируется вообще.

Затем компилируется модуль B , который требует G.P1. Хорошо, без проблем, G.P1 загружается из файла символов и G.c теперь содержит G.P1.

Затем компилируется модуль A (который зависит от B и G и B и G остаются без изменений. A требует G.P2.

Итак, теперь G.c ДОЛЖЕН содержать как P1, так и P2, но мы даже не загрузили P1 из файла символов, и мы не хотим этого делать, потому что тогда быстро восстановим большую часть всего приложения.

Решение

Бэкенд должен иметь некоторую логику, чтобы, если текущий обрабатываемый модуль находится в кэше компиляции, поле ast не использовалось. Вместо этого сгенерированный C(++) для тела символа также должен быть кэширован и вставлен обратно в создаваемый C-файл. Этот подход, похоже, решает все описанные выше проблемы.

Отладка управления памятью Nim

Следующие абзацы в основном напоминание для меня. Следует иметь в виду:

• Если утверждение в менеджере памяти или GC Nim терпит неудачу, стек-трейс продолжает выделять память! Таким образом, может произойти переполнение стека, скрывая реальную проблему.
• Проблемы, которые кажутся проблемами генерации кода C, часто являются ошибками, возникающими из-за того, что не производятся прототипы, поэтому некоторые типы по умолчанию принимают значение cint. Тестирование без опции -w помогает!

Сборщик мусора

Введение

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

Основной алгоритм — Деферентный подсчёт ссылок с обнаружением циклов. Ссылки в стеке не учитываются для лучшей производительности и более простого генерации кода C.

Каждая ячейка имеет заголовок, состоящий из RC и указателя на её описание типа. Однако программа об этом не знает, поэтому они размещаются с отрицательными смещениями. В коде GC тип PCell обозначает указатель, уменьшенный на нужное смещение, так что заголовок можно легко получить. Крайне важно, чтобы pointer не путался с PCell, так как это приведёт к повреждению памяти.

Структура данных CellSet

GC зависит от чрезвычайно эффективной структуры данных для хранения набора указателей — в исходном коде это называется TCellSet . Вставка, удаление и поиск выполняются за постоянное время. Однако изменение TCellSet во время обхода приведёт к неопределённому поведению.

type
  TCellSet # hidden

proc cellSetInit(s: var TCellSet) # initialize a new set
proc cellSetDeinit(s: var TCellSet) # empty the set and free its memory
proc incl(s: var TCellSet, elem: PCell) # include an element
proc excl(s: var TCellSet, elem: PCell) # exclude an element

proc `in`(elem: PCell, s: TCellSet): bool # tests membership

iterator elements(s: TCellSet): (elem: PCell)

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

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

• Найдите описание страницы для страницы, к которой принадлежит ячейка.
• Установите соответствующий бит в описании страницы, указывающий, что ячейка указывает на начало блока памяти.

Удаление ячейки аналогично — бит должен быть сброшен в ноль. Описания отдельных страниц никогда не удаляются из хеш-таблицы. Это не требуется, так как структуры данных всё равно необходимо периодически перестраивать.

Полный обход выполняется таким образом:

for each page descriptor d:
  for each bit in d:
    if bit == 1:
      traverse the pointer belonging to this bit

Дополнительные сложности

В Nim компилятор не всегда может знать, хранится ли ссылка в стеке или нет. Это вызвано параметрами var. Рассмотрим этот пример:

proc setRef(r: var ref TNode) =
  new(r)

proc usage =
  var
    r: ref TNode
  setRef(r) # here we should not update the reference counts, because
            # r is on the stack
  setRef(r.left) # here we should update the refcounts!

Мы должны решить во время выполнения, находится ли ссылка в стеке или нет. Сгенерированный код примерно такой:

void setref(TNode** ref) {
  unsureAsgnRef(ref, newObj(TNode_TI, sizeof(TNode)))
}
void usage(void) {
  setRef(&r)
  setRef(&r->left)
}

Обратите внимание, что для систем с непрерывным стеком (что имеет большинство систем) проверка того, находится ли ссылка в стеке, очень дешёвая (только два сравнения).

Генерация кода для замыканий

Генерация кода для замыканий реализована с помощью подъёма лямбда-выражений.

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

Процедура closure proc var может вызывать обычные процедуры по умолчанию для Nim. Но не наоборот! Замыкание реализуется как tuple[prc, env]. env может быть nil, подразумевая вызов без замыкания. Это означает, что вызов через замыкание генерирует if, но межплатформенная совместимость стоит затрат на if. Генерирование хинтов тоже возможно, но это немного сложнее для реализации.

Тесты с GCC на Amd64 показали, что очень полезно, если указатель на «среду» передаётся в качестве последнего аргумента, а не первого.

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

receivesClosure(returnsDefaultCC[i])

Хинт должен как-то вызывать 'returnsDefaultCC[i]', и это потребовало бы дополнительного создания замыкания... Хорошо, не совсем, но это требует передачи вызываемой функции. Таким образом, у нас будет 2 косвенных вызова вместо одного. Ещё одна гораздо более серьёзная проблема этого решения заключается в том, что передача указателя на процедуру через универсальный тип ref не является безопасной для GC.

Пример кода:

proc add(x: int): proc (y: int): int {.closure.} =
  return proc (y: int): int =
    return x + y

var add2 = add(2)
echo add2(5) #OUT 7

Это должно произвести примерно такой код:

type
  PEnv = ref object
    x: int # data

proc anon(y: int, c: PEnv): int =
  return y + c.x

proc add(x: int): tuple[prc, data] =
  var env: PEnv
  new env
  env.x = x
  result = (anon, env)

var add2 = add(2)
let tmp = if add2.data == nil: add2.prc(5) else: add2.prc(5, add2.data)
echo tmp

Следите за вложенностью:

proc add(x: int): proc (y: int): proc (z: int): int {.closure.} {.closure.} =
  return lambda (y: int): proc (z: int): int {.closure.} =
    return lambda (z: int): int =
      return x + y + z

var add24 = add(2)(4)
echo add24(5) #OUT 11

Это должно произвести примерно такой код:

type
  PEnvX = ref object
    x: int # data
  
  PEnvY = ref object
    y: int
    ex: PEnvX

proc lambdaZ(z: int, ey: PEnvY): int =
  return ey.ex.x + ey.y + z

proc lambdaY(y: int, ex: PEnvX): tuple[prc, data: PEnvY] =
  var ey: PEnvY
  new ey
  ey.y = y
  ey.ex = ex
  result = (lambdaZ, ey)

proc add(x: int): tuple[prc, data: PEnvX] =
  var ex: PEnvX
  ex.x = x
  result = (labmdaY, ex)

var tmp = add(2)
var tmp2 = tmp.fn(4, tmp.data)
var add24 = tmp2.fn(4, tmp2.data)
echo add24(5)

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

Альтернатива

Обработайте замыкание всех внутренних процедур за один проход и накопите окружения. Однако это не всегда возможно.

Аккумулятор

proc getAccumulator(start: int): proc (): int {.closure} =
  var i = start
  return lambda: int =
    inc i
    return i

proc p =
  var delta = 7
  proc accumulator(start: int): proc(): int =
    var x = start-1
    result = proc (): int =
      x = x + delta
      inc delta
      return x
  
  var a = accumulator(3)
  var b = accumulator(4)
  echo a() + b()

Внутренности

Поднятие лямбда-функций реализовано как часть transf прохода. transf проход генерирует код для настройки окружения и передачи его по окружению. Однако этот проход не изменяет типы! Таким образом, у нас есть несоответствие; с одной стороны, выражение процедуры становится явным кортежем, а с другой стороны, тип tyProc(ccClosure) не изменяется. Для генерации кода C также важно, что скрытый формальный параметр void* , а не что-то более специализированное. Однако более специализированный тип env должен быть передан на бэкенд каким-то образом. Мы решаем это, изменив s.ast[paramPos] так, чтобы он содержал скрытый формальный параметр, но не s.typ!

Целочисленные литералы:

В Nim есть избыточный способ указать тип целочисленного литерала. Прежде всего, не должно быть неожиданностью, что каждый узел имеет вид узла. Узел целочисленного литерала может принимать любые из следующих значений:

nkIntLit, nkInt8Lit, nkInt16Lit, nkInt32Lit, nkInt64Lit, nkUIntLit, nkUInt8Lit, nkUInt16Lit, nkUInt32Lit, nkUInt64Lit

Помимо этого, существует также поле typ для типа. Вид поля typ может быть одним из следующих, и он должен соответствовать виду литерала:

tyInt, tyInt8, tyInt16, tyInt32, tyInt64, tyUInt, tyUInt8, tyUInt16, tyUInt32, tyUInt64

Затем есть также тип целочисленного литерала. Это специфический тип, который неявно преобразуется в требуемый тип, если требуемый тип может содержать значение. Для работы этого тип должен знать конкретное значение литерала. Например, выражение 321 будет иметь тип int literal(321). Этот тип неявно преобразуется ко всем целочисленным типам и диапазонам, которые содержат значение 321. Это будут все встроенные целочисленные типы, кроме uint8 и int8 , где 321 будет за пределами диапазона. Когда этот тип литерала присваивается новой var или let переменной, его тип будет разрешён только до int, а не int literal(321), в отличие от констант. Константа сохраняет полный тип int literal(321) . Вот пример, где это различие имеет значение.

proc foo(arg: int8) =
  echo "def"

const tmp1 = 123
foo(tmp1)  # OK

let tmp2 = 123
foo(tmp2) # Error

В контексте с несколькими перегрузками вид целочисленного литерала всегда будет отдавать предпочтение типу int перед всеми другими типами. Если ни одна из перегрузок не является типа int, то возникнет ошибка из-за неоднозначности.

proc foo(arg: int) =
  echo "abc"
proc foo(arg: int8) =
  echo "def"
foo(123) # output: abc

proc bar(arg: int16) =
  echo "abc"
proc bar(arg: int8) =
  echo "def"

bar(123) # Error ambiguous call

В компиляторе эти типы целочисленных литералов представлены с видом узла nkIntLit, видом типа tyInt и членом n типа, указывающим обратно на узел целочисленного литерала в ast, содержащий целочисленное значение. Это свойства, которые справедливы для типов целочисленных литералов.

n.kind == nkIntLit n.typ.kind == tyInt n.typ.n == n

Другие типы литералов, такие как uint literal(123) , которые автоматически преобразуются в другие целочисленные типы, но предпочитают стать uint , не являются частью языка Nim.

В непроверенном AST поле typ имеет значение nil. Проверяющий типов установит поле typ в соответствии с видом узла. Узлы вида nkIntLit получат тип целочисленного литерала (например, int literal(123)). Узлы вида nkUIntLit получат тип uint (вид tyUint ), и т. д.

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