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

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

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

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

Запуск компилятора по принципу "bootstrap"

Примечание: Добавьте . в ваш PATH, чтобы koch можно было использовать без ./.

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

nim c koch.nim
koch boot -d:release

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

nim c koch.nim
koch boot

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

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

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

Воспроизводимые сборки

Установите метку времени компиляции с помощью переменной среды SOURCE_DATE_EPOCH.

export SOURCE_DATE_EPOCH=$(git log -n 1 --format=%at)
koch boot # or `./build_all.sh`

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

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

Иногда возникает ошибка, вызванная регрессией в компиляторе или стандартной библиотеке. Бисекция коммитов репозитория Nim — полезный инструмент для определения коммита, в котором произошла регрессия.

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

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

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

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

См. также:

• Многоплатформенная бисекция C/Cpp/Valgrind/JS в GitHub: https://github.com/juancarlospaco/nimrun-action#examples

Сборка отлаженного компилятора

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

По умолчанию koch temp создаст лёгкую версию компилятора с включённой -d:debug. Компилятор по умолчанию записывается в bin/nim_temp. Лёгкая версия компилятора не включает JS и генерацию документации.

bin/nim_temp можно напрямую использовать для запуска тестовых случаев или использовать с testament с testament --nim:bin/nim_temp r tests/category/tsometest.

koch temp создаст временный компилятор с включённой -d:debug. Вот параметры компилятора, которые могут быть полезны при отладке:

• -d:debug: включает assert-выражения, трассировки стека и все проверки во время выполнения
• --opt:speed: сборка с включёнными оптимизациями
• --debugger:native: включает --debuginfo --lineDir:on для использования родного отладчика, такого как GDB, LLDB или CDB
• -d:nimDebug: вызывает вызовы quit для поднятия исключения утверждения
• -d:nimDebugUtils: включает различные средства отладки; см. compiler/debugutils
• -d:stacktraceMsgs -d:nimCompilerStacktraceHints: добавляет некоторые дополнительные подсказки для трассировки стека; см. https://github.com/nim-lang/Nim/pull/13351
• -u:leanCompiler: включение JS и генерации документации

Другой метод сборки и запуска компилятора — напрямую через koch:

koch temp [options] c test.nim

# (will build with js support)
koch temp [options] js test.nim

# (will build with doc support)
koch temp [options] doc test.nim

Отладочная регистрация

"Printf-отладка" по-прежнему является наиболее подходящим способом отладки многих проблем, возникающих при разработке компилятора. Обычно использование точек останова для отладки кода менее практично, так как почти все пути кода в компиляторе будут выполняться сотни раз до достижения конкретного участка тестируемой программы, где нужно активировать недавно разработанный код.

Для решения этой проблемы, вы обычно добавляете оператор if в код компилятора, более точно определяя условия, в которых используется тестируемая функция. Один из очень распространённых способов достижения этого — использование условия mdbg, которое будет истинным только в контекстах обработки выражений и операторов из текущего основного модуля, подлежащего компиляции:

# inside some compiler module
if mdbg:
  debug someAstNode

Использование условия isCompilerDebug вместе с вставкой некоторых операторов в тестовый случай обеспечивает более точную регистрацию:

# compilermodule.nim
if isCompilerDebug():
  debug someAstNode

# testcase.nim
proc main =
  {.define(nimCompilerDebug).}
  let a = 2.5 * 3
  {.undef(nimCompilerDebug).}

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

if `??`(conf, n.info, "module.nim"):
  debug(n)

В приведенных выше примерах также используется процедура debug, которая способна выводить удобочитаемую форму произвольного дерева AST. Другие распространённые способы вывода информации о внутренних типах компилятора включают:

# pretty print PNode

# pretty prints the Nim ast
echo renderTree(someNode)

# pretty prints the Nim ast, but annotates symbol IDs
echo renderTree(someNode, {renderIds})

# pretty print ast as JSON
debug(someNode)

# print as YAML
echo treeToYaml(config, someNode)


# pretty print PType

# print type name
echo typeToString(someType)

# pretty print as JSON
debug(someType)

# print as YAML
echo typeToYaml(config, someType)


# pretty print PSym

# print the symbol's name
echo symbol.name.s

# pretty print as JSON
debug(symbol)

# print as YAML
echo symToYaml(config, symbol)


# pretty print TLineInfo
lineInfoToStr(lineInfo)


# print the structure of any type
repr(someVar)

Вот некоторые другие полезные утилиты:

# how did execution reach this location?
writeStackTrace()

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

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

Родная отладка

Пошаговое выполнение компилятора с помощью родного отладчика — очень мощный инструмент для изучения и отладки. Тем не менее, всё ещё необходимо ограничивать моменты запуска точек останова. Те же методы, что и в Отладочной регистрации, могут быть применены здесь в сочетании с вызовами отладочных помощников enteringDebugSection() и exitingDebugSection().

1. Скомпилируйте временный компилятор с --debugger:native -d:nimDebugUtils
2. Установите необходимые точки останова или точки наблюдения.
3. Настройте отладчик:
   • GDB: выполните source tools/compiler.gdb при запуске
   • LLDB: выполните command source tools/compiler.lldb при запуске
4. Используйте одного из помощников по ограничению области, например, так:

if isCompilerDebug():
  enteringDebugSection()
else:
  exitingDebugSection()

Ограничение этого метода заключается в том, что все точки останова и точки наблюдения включены или выключены. Кроме того, из-за ошибки, для LLDB можно ограничить только точки останова.

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

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

Семантический анализ отделён от синтаксического анализа.

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

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

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

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

Nim имеет два различных средства выполнения: «старое средство выполнения» и «новое средство выполнения». Старое средство выполнения поддерживает старые сборщики мусора (markAndSweep, refc, Boehm), новое средство выполнения поддерживает ARC/ORC. Новое средство выполнения активно when defined(nimV2).

Рекомендации по программированию

• Мы следуем официальному руководству по стилю Nim, см. NEP1.
• Максимальная длина строки — 100 символов.
• Добавляйте пробелы вокруг бинарных операторов, если это улучшает читаемость.
• Используйте пробел после двоеточия, но не перед ним.
• (устарело) Начинайте типы с заглавной буквы T, если это не указатели/ссылки, которые начинаются с P.
• Предпочитайте import package вместо from package import symbol.

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

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

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

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

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

Файлы, которые могут потребовать изменения для вашей платформы:

• compiler/platform.nim Добавить свойства os/cpu.
• lib/system.nim Добавить os/cpu в документацию для system.hostOS и system.hostCPU.
• compiler/options.nim Добавить проверки специальных свойств os/cpu в isDefined.
• compiler/installer.ini Добавить os/cpu в поле Project.Platforms.
• lib/system/platforms.nim Добавить os/cpu.
• std/private/osseps.nim Добавить специализации os.
• lib/pure/distros.nim Добавить os, обработчик пакетов.
• tools/niminst/makefile.nimf Добавить флаги компилятора/линкера os/cpu.
• tools/niminst/buildsh.nimf Добавить флаги компилятора/линкера os/cpu.

Если опции --os или --cpu не переданы компилятору, Nim определит текущую систему, процессор и порядок байтов из system.cpuEndian, system.hostOS и system.hostCPU. Эти значения получены из compiler/platform.nim.

Для того, чтобы новая платформа могла быть запущена с помощью csources, она должна:

• иметь compiler/platform.nim обновленным
• иметь compiler/installer.ini обновленным
• иметь tools/niminst/buildsh.nimf обновленным
• иметь tools/niminst/makefile.nimf обновленным
• быть перенесена обратно в версию Nim, используемую csources
• новый csources должен быть отправлен
• новая версия csources должна быть обновлена в config/build_config.txt

Информация о типе во время выполнения

Примечание: Этот раздел описывает «старое средство выполнения».

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

Сбор мусора

Старые сборщики мусора используют RTTI для обхода произвольных типов Nim, но обычно только поле marker содержащее процедуру, выполняющую обход.

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

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

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

Магии и compilerProcs

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

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

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

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

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

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

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

receivesClosure(returnsDefaultCC[i])

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

Пример кода:

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
  Env = ref object
    x: int # data

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

proc add(x: int): tuple[prc, data] =
  var env: Env
  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
  EnvX = ref object
    x: int # data
  
  EnvY = ref object
    y: int
    ex: EnvX

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

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

proc add(x: int): tuple[prc, data: EnvX] =
  var ex: EnvX
  ex.x = x
  result = (lambdaY, 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!

Примечания о представлении типов и AST

Подлежит расширению.

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

В 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.