Документация Engee

Абстрактные синтаксические деревья (AST) в Julia

В Julia есть два представления кода. Сначала идет дерево AST поверхностного синтаксиса, возвращаемое анализатором (например, функцией Meta.parse) и управляемое макросами. Это структурированное представление кода в том виде, в котором он написан, построенное с помощью julia-parser.scm из потока символов. Далее идет пониженная форма, или IR (промежуточное представление), которая используется при выводе типов и генерации кода. В этой форме меньше типов узлов, все макросы развернуты, а весь порядок управления преобразован в явные ветви и последовательности операторов. Она строится с помощью julia-syntax.scm.

Сначала мы рассмотрим дерево AST, поскольку оно необходимо для написания макросов.

AST поверхностного синтаксиса

Интерфейсные AST почти полностью состоят из выражений (Expr) и небольших единиц (например, символов, чисел). Как правило, для каждой визуально отличимой синтаксической формы существует своя вершина выражения. Примеры будут приведены в синтаксисе s-выражения. Каждый заключенный в скобки список соответствует выражению, где первый элемент является вершиной. Например, (call f x) соответствует Expr(:call, :f, :x) в Julia.

Вызовы

Ввод AST

f(x)

(call f x)

f(x, y=1, z=2)

(call f x (kw y 1) (kw z 2))

f(x; y=1)

(call f (parameters (kw y 1)) x)

f(x...)

(call f (... x))

синтаксис do:

f(x) do a,b
    body
end

анализируется как (do (call f x) (-> (tuple a b) (block body))).

Операторы

Чаще всего операторы используются просто для вызовов функций, поэтому они анализируются с помощью вызова (call) вершины. Однако некоторые операторы представляют собой специальные формы (необязательно вызовы функций), и в этих случаях сам оператор является вершиной выражения. В julia-parser.scm они называются «синтаксическими операторами». Некоторые операторы (+ и *) используют N-арный анализ. Цепочки вызовов анализируются как один N-аргументный вызов. Наконец, цепочки сравнений имеют свою особую структуру выражения.

Ввод AST

x+y

(call + x y)

a+b+c+d

(call + a b c d)

2x

(call * 2 x)

a&&b

(&& a b)

x += 1

(+= x 1)

a ? 1 : 2

(if a 1 2)

a,b

(tuple a b)

a==b

(call == a b)

1<i<=n

(comparison 1 < i <= n)

a.b

(. a (quote b))

a.(b)

(. a (tuple b))

Формы, заключенные в квадратные скобки

Ввод AST

a[i]

(ref a i)

t[i;j]

(typed_vcat t i j)

t[i j]

(typed_hcat t i j)

t[a b; c d]

(typed_vcat t (row a b) (row c d))

t[a b;;; c d]

(typed_ncat t 3 (row a b) (row c d))

a{b}

(curly a b)

a{b;c}

(curly a (parameters c) b)

[x]

(vect x)

[x,y]

(vect x y)

[x;y]

(vcat x y)

[x y]

(hcat x y)

[x y; z t]

(vcat (row x y) (row z t))

[x;y;; z;t;;;]

(ncat 3 (nrow 2 (nrow 1 x y) (nrow 1 z t)))

[x for y in z, a in b]

(comprehension (generator x (= y z) (= a b)))

T[x for y in z]

(typed_comprehension T (generator x (= y z)))

(a, b, c)

(tuple a b c)

(a; b; c)

(block a b c)

Макросы

Ввод AST

@m x y

(macrocall @m (line) x y)

Base.@m x y

(macrocall (. Base (quote @m)) (line) x y)

@Base.m x y

(macrocall (. Base (quote @m)) (line) x y)

Строки

Ввод AST

"a"

"a"

x"y"

(macrocall @x_str (line) "y")

x"y"z

(macrocall @x_str (line) "y" "z")

"x = $x"

(string "x = " x)

a b c

(вызов макроса @cmd (строка) «a b c»)

Синтаксис строк документации:

"some docs"
f(x) = x

анализируется как (macrocall (|.| Core '@doc) (line) "some docs" (= (call f x) (block x))).

Импорт и прочее

Ввод AST

import a

(import (. a))

import a.b.c

(import (. a b c))

import ...a

(import (. . . . a))

import a.b, c.d

(import (. a b) (. c d))

import Base: x

(import (: (. Base) (. x)))

import Base: x, y

(import (: (. Base) (. x) (. y)))

export a, b

(export a b)

using имеет такое же представление, как и import, но с вершиной выражения :using вместо :import.

Числа

Julia поддерживает больше числовых типов, чем многие реализации схем, поэтому не все числа представлены в AST непосредственно как числа схемы.

Ввод AST

11111111111111111111

(macrocall @int128_str nothing "11111111111111111111")

0xfffffffffffffffff

(macrocall @uint128_str nothing "0xfffffffffffffffff")

1111...many digits...

(macrocall @big_str nothing "1111....")

Формы блоков

Блок операторов анализируется как (block stmt1 stmt2 ...).

Оператор if:

if a
    b
elseif c
    d
else
    e
end

анализируется как:

(if a (block (line 2) b)
    (elseif (block (line 3) c) (block (line 4) d)
            (block (line 6 e))))

Цикл while анализируется как (while condition body).

Цикл for анализируется как (for (= var iter) body). Если спецификаций итераций несколько, они анализируются как блок: (for (block (= v1 iter1) (= v2 iter2)) body).

break и continue анализируются как нульаргументные выражения (break) и (continue).

let анализируется как (let (= var val) body) или (let (block (= var1 val1) (= var2 val2) ...) body) аналогично циклам for.

Базовое определение функции анализируется как (function (call f x) body). Вот более сложный пример:

function f(x::T; k = 1) where T
    return x+1
end

анализируется как:

(function (where (call f (parameters (kw k 1))
                       (:: x T))
                 T)
          (block (line 2) (return (call + x 1))))

Определение типа:

mutable struct Foo{T<:S}
    x::T
end

анализируется как:

(struct true (curly Foo (<: T S))
        (block (line 2) (:: x T)))

Первый аргумент является логическим и указывает, изменяем ли тип.

Блоки try анализируются как (try try_block var catch_block finally_block). Если после catch нет переменной, то переменная (var) будет иметь вид #f. Если нет предложения finally, значит последний аргумент отсутствует.

Выражения с кавычками

Формы синтаксиса исходного текста Julia для заключения кода в кавычки (quote и :( )) поддерживают интерполяцию с $. В терминологии Lisp это означает, что на самом деле они являются формами использования обратных кавычек. На внутреннем уровне также существует необходимость заключения кода в кавычки без интерполяции. В коде схемы Julia неинтерполирующая кавычка представлена вершиной выражения inert.

Выражения inert преобразуются в объекты Julia QuoteNode. Эти объекты инкапсулируют одно значение любого типа и при оценке просто возвращают его.

Выражение quote, аргументом которого является небольшой элемент, также преобразуется в QuoteNode.

Номера строк

Информация о расположении исходного кода представлена в виде (line line_num file_name), где третий компонент является необязательным (и опускается, когда меняется номер текущей строки, но не имя файла).

Эти выражения представлены в Julia как LineNumberNode.

Макросы

Гигиена макроса представлена через пару вершин выражения escape и hygienic-scope. Результат расширения макроса автоматически заключается в (hygienic-scope block module), чтобы представить результат новой области. Пользователь может вставить (escape block) внутрь, чтобы интерполировать код от вызывающей стороны.

Пониженная форма

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

Помимо символов (Symbol) и некоторых числовых типов, в пониженной форме существуют следующие типы данных.

  • Expr

    Имеет тип узла, указанный полем head, и поле args, которое представляет собой Vector{Any} подвыражений . Тогда как почти каждая часть поверхностного AST представлена типом Expr, IR использует только ограниченное количество Expr и в основном только для вызовов и некоторых форм верхнего уровня.

  • Slot

    Идентифицирует аргументы и локальные переменные с помощью последовательной нумерации. Slot является абстрактным типом с подтипами SlotNumber и TypedSlot. Оба типа имеют поле id с целочисленным значением, представляющим индекс слота. Большинство слотов имеют один и тот же тип при любом использовании и поэтому обозначаются SlotNumber. Типы этих слотов указываются в поле slottypes их объекта CodeInfo. Слоты, требующие аннотаций типов для каждого использования, представлены с помощью TypedSlot, который имеет поле typ.

  • Argument

    То же, что и SlotNumber, но появляется только после оптимизации. Указывает, что слот , на который дана ссылка, является аргументом включающей функции.

  • CodeInfo

    Оборачивает IR группы операторов. Его поле code представляет собой массив выражений для выполнения.

  • GotoNode

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

  • GotoIfNot

    Условная ветвь. Если поле cond имеет значение false, переходит к индексу, определенному полем dest.

  • ReturnNode

    Возвращает свой аргумент (поле val) как значение включающей функции. Если поле val не определено, представляет недоступный оператор.

  • QuoteNode

    Оборачивает произвольное значение, на которое как на данные будет указывать ссылка. Например, функция f() = :a содержит QuoteNode, полем value которого является символ a, чтобы возвращать сам символ, а не определять его.

  • GlobalRef

    Относится к глобальной переменной name в модуле mod.

  • SSAValue

    Относится к последовательно пронумерованной (начиная с 1) статической переменной одиночного присваивания (SSA), вставленной компилятором. Номер (id) SSAValue — это индекс массива кода выражения, значение которого он представляет.

  • NewvarNode

    Отмечает точку, в которой создается переменная (слот). Это приводит к сбросу переменной до неопределенной.

Типы Expr

Эти символы отображаются в поле head выражений (Expr) в пониженной форме.

  • call

    Вызов функции (динамическая диспетчеризация). args[1] — это вызываемая функция, args[2:end] — это аргументы.

  • invoke

    Вызов функции (статическая диспетчеризация). args[1] — это вызываемый MethodInstance, args[2:end] — это аргументы (включая вызываемую функцию с args[2]).

  • static_parameter

    Указывает на статический параметр по индексу.

  • =

    Присваивание. В IR первым аргументом всегда является Slot или GlobalRef.

  • method

    Добавляет метод к универсальной функции и при необходимости присваивает результат.

    Имеет одноаргументную форму и трехаргументную форму. Источником формы с одним аргументом является синтаксис function foo end. В одноаргументной форме аргумент является символом. Если этот символ уже именует функцию в текущей области, ничего не происходит. Если символ не определен, создается новая функция и присваивается идентификатору, указанному символом. Если символ определен, но именует не функцию, возникает ошибка. Определение «именует функцию» заключается в том, что привязка является постоянной, и ссылается на объект одинарного типа. Это объясняется тем, что экземпляр одинарного типа идентифицирует тип, к которому нужно добавить метод. Когда у типа есть поля, будет неясно, добавляется ли метод к экземпляру или его типу.

    Трехаргументная форма имеет следующие аргументы:

    • args[1]

      Имя функции или nothing, если неизвестно или не требуется. Если символ, то выражение сначала ведет себя как одноаргументная форма выше. В дальнейшем этот аргумент игнорируется. Может быть nothing, когда методы добавляются строго по типу, (::T)(x) = x, или когда метод добавляется к существующей функции, MyModule.f(x) = x.

    • args[2]

      SimpleVector данных типа аргумента. args[2][1] — это SimpleVector типов аргументов, а args[2][2] — это SimpleVector переменных типов, соответствующих статическим параметрам метода.

    • args[3]

      CodeInfo самого метода. Для определений методов «вне области» (добавление метода к функции, которая также имеет методы, определенные в других областях) это выражение, которое вычисляется в выражение :lambda.

  • struct_type

    Семиаргументное выражение, которое определяет новую структуру (struct).

    • args[1]

      Имя структуры struct.

    • args[2]

      Выражение call, которое создает SimpleVector, указывая его параметры.

    • args[3]

      Выражение call, которое создает SimpleVector, указывая его имена полей.

    • args[4]

      Symbol, GlobalRef или Expr, указывающие супертип (например, :Integer, GlobalRef(Core, :Any) или :(Core.apply_type(AbstractArray, T, N))).

    • args[5]

      Выражение call, которое создает SimpleVector, указывая его типы полей.

    • args[6]

      Логический, имеет значение true, если является изменяемым (mutable).

    • args[7]

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

  • abstract_type

    Трехаргументное выражение, которое определяет новый абстрактный тип. Аргументы совпадают с аргументами 1, 2 и 4 выражений struct_type.

  • primitive_type

    Четырехаргументное выражение, которое определяет новый примитивный тип. Аргументы 1, 2 и 4 такие же, как в struct_type. Аргумент 3 — это количество битов.

    Совместимость: Julia 1.5

    struct_type, abstract_type и primitive_type были удалены в Julia 1.5 и заменены вызовами новых встроенных объектов.

  • global

    Объявляет глобальную привязку.

  • const

    Объявляет (глобальную) переменную как константу.

  • new

    Выделяет новый структуроподобный объект. Первый аргумент — это тип. Уровень псевдофункции new понижается до этого, а тип всегда вставляется компилятором. Это в значительной степени только внутренняя функция, которая не выполняет проверку. Определение произвольных выражений new может легко привести к сбою.

  • splatnew

    Аналогичен new, за исключением того, что значения полей передаются в виде одного кортежа. Работает так же, как splat(new), если бы new была функцией первого класса. Отсюда и имя.

  • isdefined

    Expr(:isdefined, :x) возвращает логическое значение, указывающее, был ли x уже определен в текущей области видимости.

  • the_exception

    Выдает перехваченное исключение внутри блока catch как возвращенное jl_current_exception().

  • undefcheck

    Временный узел, вставляемый компилятором. Будет обработан в функции type_lift_pass!.

  • enter

    Вводит обработчик событий (setjmp). args[1] — это метка блока catch, в который нужно перейти при ошибке . Выдает токен, используемый pop_exception.

  • leave

    Возвращает обработчики исключений. args[1] — это количество обработчиков, которое нужно возвратить.

  • pop_exception

    Возвращает состояние текущих исключений к состоянию в связанном аргументе enter при выходе из блока catch. args[1] содержит токен из связанного аргумента enter.

    Совместимость: Julia 1.1

    Аргумент pop_exception является новым в Julia 1.1.

  • inbounds

    Управляет включением или отключением проверки границ. Ведется стек. Если первый аргумент этого выражения имеет значение true или false (true означает, что проверка границ отключена), он отправляется в стек. Если первый аргумент — :pop, стек извлекается.

  • boundscheck

    Имеет значение false, если вставлен в участок кода, помеченный с помощью макроса @inbounds, в противном случае имеет значение true.

  • loopinfo

    Помечает конец цикла. Содержит метаданные, которые передаются в LowerSimdLoop, чтобы либо пометить внутренний цикл выражения @simd, либо распространить информацию в передачи цикла LLVM.

  • copyast

    Часть реализации квазикавычки. Аргументом является поверхностный синтаксис AST, который просто рекурсивно копируется и возвращается во время выполнения.

  • meta

    Метаданные. args[1] обычно представляет собой символ, указывающий тип метаданных, а остальные аргументы имеют свободную форму. Обычно используются следующие типы метаданных.

    • :inline и :noinline: указания по встраиванию.

  • foreigncall

    Статически вычисляемый контейнер для информации по ключевому слову ccall. Используются следующие поля.

    • args[1]: имя

      Выражение, которое будет проанализировано для внешней функции.

    • args[2]::Type: RT

      (Литеральный) возвращаемый тип, вычисленный статически, когда был определен содержащий метод.

    • args[3]::SimpleVector (типов): AT

      (Литеральный) вектор типов аргументов, вычисленный статически, когда был определен содержащий метод.

    • args[4]::Int: nreq

      Количество необходимых аргументов для определения функции с переменным количеством аргументов.

    • args[5]::QuoteNode{Symbol}: соглашение о вызовах

      Соглашение о вызовах для вызова.

    • args[6:5+length(args[3])]: аргументы

      Значения для всех аргументов (типы каждого из них указаны в args[3]).

    • args[6+length(args[3])+1:end]: права суперпользователя при сборке мусора

      Дополнительные объекты, которым может потребоваться предоставить права суперпользователя при сборке мусора на время вызова. Сведения об источнике этих объектов и способе их обработки см. в главе Работа с LLVM.

  • new_opaque_closure

    Создает новое непрозрачное замыкание. Используются следующие поля.

    • args[1]: сигнатура

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

    • args[2]: isva

      Указывает, принимает ли замыкание переменное количество аргументов.

    • args[3]: lb

      Нижняя граница для типа вывода. (По умолчанию имеет значение Union{})

    • args[4]: ub

      Верхняя граница для типа вывода. (По умолчанию имеет значение Any)

    • args[5]: метод

      Фактический метод как выражение opaque_closure_method.

    • args[6:end]: записи

      Значения, записываемые непрозрачным замыканием.

    Совместимость: Julia 1.7

    Непрозрачные замыкания были добавлены в Julia 1.7.

Method

Уникальный контейнер, описывающий общие метаданные для одного метода.

  • name, module, file, line, sig

    Метаданные для уникального определения метода для компьютера и человека.

  • ambig

    Кэш других методов, которые могут быть неоднозначными с этим.

  • specializations

    Кэш всех MethodInstance, когда-либо созданных для этого Method, используемых для обеспечения уникальности. Уникальность необходима для обеспечения эффективности, особенно для добавочной предварительной компиляции и отслеживания недействительности методов.

  • source

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

  • generator

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

  • roots

    Указатели на объекты, не относящиеся к AST, которые были интерполированы в AST, требуемые при сжатии AST, выводе типов или генерации собственного кода.

  • nargs, isva, called, isstaged, pure

    Описательные битовые поля для исходного кода данного Method.

  • primary_world

    «Возраст мира» (иерархия определения методов) для этого Method.

MethodInstance

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

  • specTypes

    Первичный ключ для этого MethodInstance. Уникальность гарантируется с помощью поиска def.specializations.

  • def

    Метод (Method), специализацию которого описывает эта функция. Или модуль (Module), если это лямбда верхнего уровня, расширенная в Module, и которая не является частью Method.

  • sparam_vals

    Значения статических параметров в specTypes, индексированных с помощью def.sparam_syms. Для контейнера MethodInstance в Method.unspecialized это пустой вектор SimpleVector. Но для контейнера MethodInstance среды выполнения из кэша MethodTable это значение всегда будет определенным и индексируемым.

  • uninferred

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

  • backedges

    Мы храним обратный список зависимостей кэша для эффективного отслеживания работы по добавочному повторному анализу или перекомпиляции, которые могут потребоваться после определений нового метода. Для этого мы храним список других контейнеров MethodInstance, которые были выведены или оптимизированы, чтобы содержать возможный вызов этого контейнера MethodInstance. Результаты оптимизации могут храниться где-то в кэше (cache), либо это может быть результат чего-то, что не требуется кэшировать, например распространение констант. Таким образом, мы объединяем все эти сведения в различные записи кэша (почти всегда есть только одна применимая запись кэша с контрольным значением для max_world).

  • cache

    Кэш объектов CodeInstance, для которых этот экземпляр шаблона является общим.

CodeInstance

  • def

    Контейнер MethodInstance, из которого получена эта запись кэша.

  • rettype/rettype_const

    Выводимый возвращаемый тип для поля specFunctionObject, который (в большинстве случаев) является также вычисляемым возвращаемым типом для функции в целом.

  • inferred

    Может содержать кэш выводимого исходного кода для этой функции, или может иметь значение nothing, чтобы просто указывать, что ничего не выводится (rettype).

  • ftpr

    Универсальная точка входа jlcall.

  • jlcall_api

    Используемый ABI при вызове fptr. Ниже приведены некоторые важные значения.

    • 0 — еще не скомпилировано

    • 1 — JL*CALLABLE jl*value*t ()(jl*function*t *f, jl*value*t *args[nargs], uint32*t nargs)

    • 2 — константа (значение хранится в rettype_const)

    • 3 — с пересылкой статических параметров jl_value_t ()(jl_svec_t *sparams, jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)

    • 4 — выполнение в интерпретаторе jl_value_t ()(jl_method_instance_t *meth, jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)

  • min_world / max_world

    Диапазон «возрастов мира» (иерархий определений методов), для которых этот экземпляр метода является допустимым для вызова. Если max_world — это специальное значение токена -1, его значение еще не известно. Его можно продолжать использовать до тех пор, пока не появятся сведения, которые потребуют пересмотра.

CodeInfo

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

  • code

    Массив Any операторов.

  • slotnames

    Массив символов, задающих имена для каждого слота (аргумента или локальной переменной).

  • slotflags

    Массив UInt8 свойств слотов, представленных в виде битовых флагов:

    • 2 — присвоено (только false, если отсутствуют операторы присваивания с этой переменной слева)

    • 8 — константа (в настоящее время не используется для локальных переменных)

    • 16 — статически присвоено один раз

    • 32 — может использоваться до присваивания. Этот флаг допустим только после вывода типов.

  • ssavaluetypes

    Любой массив или целое число (Int).

    Если целое число (Int), задает количество вставленных компилятором временных расположений в функции (длина массива code). Если массив, задает тип для каждого расположения.

  • ssaflags

    Флаги уровня оператора для каждого выражения в функции. Многие из них зарезервированы, но еще не реализованы.

    • 0x01 << 0 — оператор помечен как @inbounds

    • 0x01 << 1 — оператор помечен как @inline

    • 0x01 << 2 — оператор помечен как @noinline

    • 0x01 << 3 — оператор находится внутри блока, который приводит к вызову throw

    • 0x01 << 4 — оператор может быть удален, если его результат не используется, в частности если он будет чистым и не будет иметь последствий

    • 0x01 << 5-6 — 

    • 0x01 << 7 — содержит внешнюю информацию

  • linetable

    Массив объектов расположения исходного кода.

  • codelocs

    Массив целочисленных индексов в linetable, указывающих расположение, связанное с каждым оператором.

Необязательные поля:

  • slottypes

    Массив типов для слотов.

  • rettype

    Выводимый возвращаемый тип пониженной формы (IR). Значение по умолчанию — Any.

  • method_for_inference_limit_heuristics

    method_for_inference_heuristics расширяет генератор данного метода, если это необходимо во время вывода.

  • parent

    Контейнер MethodInstance, который «владеет» этим объектом (если применимо).

  • edges

    Передача ребер в экземпляры метода, которые должны быть сделаны недействительными.

  • min_world/max_world

    Диапазон «возрастов мира» (иерархий определений методов), для которых этот код был допустим в момент его вывода.

Логические свойства:

  • inferred

    Было ли получено путем вывода типов.

  • inlineable

    Подходит ли для встраивания.

  • propagate_inbounds

    Следует ли распространять @inbounds при встраивании с целью пропуска блоков @boundscheck.

  • pure

    Известно ли, что это чистая функция своих аргументов, без учета состояния кэшей методов или другого изменяемого глобального состояния.

Параметры UInt8:

  • constprop

    • 0 — использовать эвристику

    • 1 — агрессивный режим

    • 2 — нет

  • purity Состоит из 5-битовых флагов:

    • 0x01 << 0 — этот метод гарантированно возвращает управление или согласованно завершает выполнение (:consistent)

    • 0x01 << 1 — этот метод лишен внешне семантически видимых побочных эффектов (:effect_free)

    • 0x01 << 2 — этот метод гарантированно не вызывает исключение (:nothrow)

    • 0x01 << 3 — этот метод гарантированно завершает выполнение (:terminates_globally)

    • 0x01 << 4 — синтаксический порядок выполнения внутри этого метода гарантированно завершает выполнение (:terminates_locally)

    Дополнительные сведения см. в документации по Base.@assume_effects.