Документация 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

(macrocall @cmd (line) "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 и в основном только для вызовов и некоторых форм верхнего уровня.

  • SlotNumber

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

  • 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 первым аргументом всегда является SlotNumber или 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 — это количество битов.

    !!! compat "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(ct).

  • enter

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

  • leave

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

  • pop_exception

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

    !!! compat "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` and `:noinline`: Inlining hints.
  • foreigncall

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

    * `args[1]` : name
    
      Выражение, которое будет проанализировано для внешней функции.
    
    * `args[2]::Type` : RT
    
      (Литеральный) возвращаемый тип, вычисленный статически, когда был определен содержащий метод.
    
    * `args[3]::SimpleVector` (of Types) : AT
    
      (Литеральный) вектор типов аргументов, вычисленный статически, когда был определен содержащий метод.
    
    * `args[4]::Int` : nreq
    
      Количество необходимых аргументов для определения функции с переменным количеством аргументов.
    
    * `args[5]::QuoteNode{Symbol}` : calling convention
    
      Соглашение о вызовах для вызова.
    
    * `args[6:5+length(args[3])]` : arguments
    
      Значения для всех аргументов (типы каждого из них указаны в args[3]).
    
    * `args[6+length(args[3])+1:end]` : gc-roots
    
      Дополнительные объекты, которым может потребоваться предоставить права суперпользователя при сборке мусора на время вызова. Сведения об источнике этих объектов и способе их обработки см. в главе [Работа с LLVM](@ref Working-with-LLVM).
  • new_opaque_closure

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

    * `args[1]` : signature
    
      Сигнатура функции для непрозрачного замыкания. Непрозрачные замыкания не используются в диспетчеризации, но входные типы могут быть ограничены.
    
    * `args[2]` : isva
    
      Указывает, принимает ли замыкание переменное количество аргументов.
    
    * `args[3]` : lb
    
      Нижняя граница для типа вывода. (По умолчанию имеет значение `Union{}`)
    
    * `args[4]` : ub
    
      Верхняя граница для типа вывода. (По умолчанию имеет значение `Any`)
    
    * `args[5]` : method
    
      Фактический метод как выражение `opaque_closure_method`.
    
    * `args[6:end]` : captures
    
      Значения, записываемые непрозрачным замыканием.

    !!! compat "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, is_for_opaque_closure,

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

  • primary_world

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

MethodInstance

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

  • specTypes

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

  • def

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

  • sparam_vals

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

  • uninferred

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

  • backedges

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

  • cache

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

CodeInstance

  • def

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

  • owner

    Токен, представляющий владельца этого CodeInstance. Будет использовать jl_egal для соответствия.

  • rettype/rettype_const

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

  • inferred

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

  • ftpr

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

  • jlcall_api

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

    * 0 - Not compiled yet
    * 1 - `JL_CALLABLE` `jl_value_t *(*)(jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)`
    * 2 - Constant (value stored in `rettype_const`)
    * 3 - With Static-parameters forwarded `jl_value_t *(*)(jl_svec_t *sparams, jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)`
    * 4 - Run in interpreter `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 свойств слотов, представленных в виде битовых флагов:

    * 0x02 - assigned (only false if there are *no* assignment statements with this var on the left)
    * 0x08 - used (if there is any read or write of the slot)
    * 0x10 - statically assigned once
    * 0x20 - might be used before assigned. This flag is only valid after type inference.
  • ssavaluetypes

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

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

  • ssaflags

    32-битные флаги уровня оператора для каждого выражения в функции. Дополнительные сведения см. в определении jl_code_info_t в файле julia.h.

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

Параметры 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.