Engee 文档

Julia中的抽象语法树(AST)

Julia中有两种代码表示。 首先是分析器返回的表面语法的AST树(例如,函数 '元。parse')和宏驱动。 这是使用`julia-parser’构建的代码的结构化表示形式。来自字符流的scm。 接下来是简化形式,或IR(中间表示),用于类型推断和代码生成。 在这种形式中,节点类型更少,所有宏都被扩展,并且整个控制顺序被转换为显式分支和运算符序列。 它是使用`julia-syntax构建的。单片机'。

首先,我们将看一下AST树,因为它是编写宏所必需的。

表面语法的AST

接口AST几乎完全由表达式('Expr')和小单位(例如,字符,数字)。 通常,每个视觉上可区分的句法形式都有自己的表达顶点。 示例将在s表达式的语法中给出。 每个带括号的列表对应于一个表达式,其中第一个元素是顶点。 例如,`(call f x)`对应于Julia中的`Expr(:call,:f,:x)'。

挑战

输入 AST

'f(x)`

(叫f x)

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

(叫f x(kw y1)(kw z2))

'f(x;y=1)`

'(调用f(参数(kw y1))x)`

'f(x。..)`

'(调用f(。.. x))`

'do’语法:

f(x) do a,b
    body
end

分析为'(do(call f x)(->(元组a b)(块体)))`。

营办商

大多数情况下,运算符仅用于函数调用,因此使用顶点调用对其进行分析。 但是,一些运算符是特殊形式(不一定是函数调用),在这些情况下,运算符本身是表达式的顶部。 在julia-parser中。scm它们被称为"句法运算符"。 一些运算符(+'和*`) 使用N-ary分析。 调用链被分析为单个N参数调用。 最后,比较链有自己特殊的表达结构。

输入 AST

x+y

(呼叫+x y)

a+b+c+d

(呼叫+a b c d)

2x

(致电*2x)

'a&&b;`

(&&a b)

'x+=1`

(+=x1)

'a? 1 : 2`

(若12)

'a,b`

'(元组a b)`

'a==b`

(呼叫==a b)

'1<i<=n`

'(比较1<i<=n)`

'a.b`

(. a(报价b))

'a.(b)`

(. a(元组b))

<无翻译>

方括号内的表格

输入 AST

'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(a b行)(c d行))`

't[a b;;;c d]`

(typed_ncat t3(a b行)(c d行))

'a{b}`

'(卷曲a b)`

一{b;c}

'(卷曲a(参数c)b)`

[x]

(矢量x)

[x,y]

(矢量x y)

[x;y]

(vcat x y)

[x y]

(hcat x y)

[x y;z t]

'(vcat(行x y)(行z t))`

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

(ncat3(nrow2(nrow1x y)(nrow1z t)))

'[x代表z中的y,a代表b]`

'(理解(生成器x(=y z)(=a b)))`

'T[x代表z中的y]`

(typed_comprehension T(生成器x(=y z)))

(a,b,c)

'(元组a b c)`

(a;b;c)

(a座b座c座)

输入 AST

'@m x y`

(macrocall@m(线)x y)

"基地。@m x y`

(宏观(。 Base(quote@m))(line)x y)

'@基地。m x y`

(宏观(。 Base(quote@m))(line)x y)

线条

输入 AST

"a"

"a"

'x"y"`

(macrocall@x_str(行)"y")

'x"y"z`

'(macrocall@x_str(行)"y""z")`

"x=$x"

'(字符串"x="x)`

'a b c`

'(macrocall@cmd(行)"a b c")`

文档字符串的语法:

"some docs"
f(x) = x

分析为`(macrocall(/。/Core'@doc)(line)"some docs"(=(call f x)(block x)))`。

进口及其他

输入 AST

`导入a'

'(导入(。 a))`

`进口a.b.c'

'(导入(。 a b c))`

'导入。..a`

'(导入(。 . . . a))`

`进口a.b,c.d'

'(导入(。 a b)(。 c d))`

'进口基数:x`

'(导入(:(。 基)(。 x)))`

'导入基数:x,y`

'(导入(:(。 基)(。 x)(。 y)))`

'出口a,b`

(出口a b)

'using`具有与’import’相同的表示形式,但表达式的顶部是`:using`而不是`:import`。

数字

Julia支持比许多模式实现更多的数字类型,因此并非所有数字都直接在AST中表示为模式数字。

输入 AST

11111111111111111111

(macrocall@int128_str nothing"11111111111111111111111")

0xfffffffffffffffffff

(macrocall@uint128_str"0xfffffffffffffffffffffff")

1111...许多数字。..

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

块形状

运算符块被分析为`(块stmt1stmt2。..)`.

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(=v1iter1)(=v2iter2))body)

'break’和`continue’被分析为空参数表达式`(break)`和'(continue)'。

'let’被分析为'(let(=var val)body)'或'(let(block(=var1val1)(=var2val2)。..)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’子句,则缺少最后一个参数。

带引号的表达式

将代码括在引号(quote`和:())中的Julia源语法形式支持用$`进行插值。 在Lisp术语中,这意味着它们实际上是使用反引号的形式。 在内部层面,还需要将代码用引号括起来而不进行插值。 在Julia模式代码中,非插值引号由表达式`inertia`的顶点表示。

'惰性’表达式被转换为Julia’QuoteNode’对象。 这些对象封装任何类型的单个值,并在计算时简单地返回它。

'Quote’表达式,其参数是一个小元素,也被转换为’QuoteNode'。

行号

有关源代码位置的信息以`(line line_num file_name)`的形式呈现,其中第三个组件是可选的(并且在当前行号更改时省略,但不是文件名)。

这些表达式在Julia中表示为’LineNumberNode'。

宏的卫生通过表达式`escape`和`hygienic-scope’的一对顶点表示。 宏扩展的结果自动是一个`(卫生范围块模块)来表示一个新区域的结果。 用户可以在里面插入(转义块)'来插入来自调用者的代码。

缩小形式

简化形式(IR)对编译器来说更重要,因为它用于类型推断,嵌入等优化和代码生成。 它对人类来说也不那么明显,因为它是由于输入语法的显着重新排序而产生的。

除了符号('Symbol`)和一些数字类型之外,以下数据类型以简化形式存在。

  • 'Expr`

    它具有由`head`字段和`args`字段指定的节点类型,这是一个'Vector{Any}'子表达式。 虽然表面AST的几乎每个部分都由"Expr"类型表示,但IR仅使用有限数量的"Expr",并且主要仅用于调用和一些顶级表单。

  • "睡眠者`

    使用顺序编号标识参数和局部变量。 它有一个"id"字段,其整数值表示插槽索引。 这些插槽的类型可以在其"CodeInfo"对象的"slottypes"字段中找到。

  • "论点`

    与’SlotNumber’相同,但仅在优化后出现。 指示引用的槽是启用函数的参数。

  • `CodeInfo'

    包装一组运算符的IR。 它的"代码"字段是要执行的表达式数组。

  • 'GotoNode`

    的无条件分支。 参数是分支目标对象,表示为要移动到的代码数组中的索引。

  • "GotoIfNot"

    个条件分支。 如果"cond"字段设置为false,则转到"dest"字段定义的索引。

  • `返回号'

    返回其参数(`val’字段)作为封闭函数的值。 如果字段是`val`undefined,则表示不可用的运算符。

  • "报价码`

    包装将作为数据引用的任意值。 例如,函数’f()=:a’包含一个’QuoteNode`,其’value’字段是字符’a',以便返回字符本身,而不是定义它。

  • `GlobalRef'

    指`mod`模块中的全局变量`name'。

  • 'SSAValue`

    指编译器插入的顺序编号(从1开始)静态单赋值变量(SSA)。 数字(id)'SSAValue’是它表示其值的表达式代码数组的索引。

  • 'NewvarNode`

    标记创建变量(插槽)的点。 这将导致变量重置为未定义。

"Expr"的类型

这些字符显示在表达式的’head’字段中(`Expr')的还原形式。

  • '呼叫`

    函数调用(动态调度)。 'args[1]`是被调用的函数,`args[2:end]'是参数。

  • "调用`

    函数调用(静态调度)。 'args[1]`是被调用的MethodInstance,`args[2:end]`是参数(包括使用`args[2]'调用的函数)。

  • 'static_parameter`

    按索引指示静态参数。

  • =

    任务。 在IR中,第一个参数总是’SlotNumber’或’GlobalRef'。

  • '方法`

    将方法添加到通用函数,并在必要时分配结果。

    它有一个单文档表单和一个三文档表单。 单参数形式的来源是语法"函数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)的半大型表达式。

    * `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`

    定义新抽象类型的三参数表达式。 参数匹配`struct_type`表达式的参数1、2和4。

  • `primitive_type'

    定义新基元类型的四参数表达式。 参数1、2和4与`struct_type’中的参数相同。 参数3是位数。

    !!! Compat"Julia1.5"`struct_type`,`abstract_type`和`primitive_type`在Julia1.5中被删除,并替换为对新嵌入对象的调用。

  • "全球`

    声明全局绑定。

  • 'const`

    将(全局)变量声明为常量。

  • 突出显示一个新的类似结构的对象。 第一个参数是类型。 伪函数级别 'new'降级为this,类型始终由编译器插入。 它几乎只是一个不执行验证的内部函数。 定义任意的"新"表达式很容易导致失败。

  • `splatnew'

    它类似于’new`,只是字段值作为单个元组传递。 如果`new`是一流的函数,它的工作方式与`splat(new)`相同。 因此得名。

  • "被定义`

    `Expr(:isdefined,:x)`返回一个布尔值,指示`x’是否已经在当前作用域中定义。

  • `the_exception'

    在`jl_current_exception(ct)`返回的`catch’块内抛出捕获的异常。

  • `进入'

    引入事件处理程序('setjmp')。 'args[1]'是在发生错误时要切换到的catch块的标签。 发出’pop_exception’使用的令牌。

  • "离开`

    返回异常处理程序。 'args[1]'是要返回的处理程序的数量。

  • `pop_exception'

    将当前异常的状态返回到退出catch块时关联的"enter"参数中的状态。 "args[1]"包含来自关联的"enter"参数的标记。

    !!! compat"Julia1.1"`pop_exception’参数在Julia1.1中是新的。

  • inbounds

    控制是启用还是禁用边界检查。 正在维护堆栈。 如果此表达式的第一个参数为true或false(`true’表示禁用边界检查),则将其发送到堆栈。 如果第一个参数是':pop',则堆栈将被删除。

  • 'boundscheck`

    如果它被插入到标有宏"@inbounds"的代码段中,则它具有值"false",否则它具有值"true"。

  • `循环信息'

    标志着周期的结束。 它包含传递给`LowerSimdLoop`的元数据,以标记表达式`@simd`的内部循环,或在LLVM循环传输中分发信息。

  • `复制'

    准引号实现的一部分。 参数是AST的表面语法,它只是递归地复制并在运行时返回。

  • `元'

    元数据。 'args[1]'通常是指示元数据类型的字符,其余参数为自由形式。 通常使用以下类型的元数据。

    * `:inline` and `:noinline`: Inlining hints.
  • "外国球"

    一个静态计算的容器,用于关键字"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
    
      Значения, записываемые непрозрачным замыканием.

    !!! 在Julia1.7中添加了compat"Julia1.7"不透明闭包。

方法

描述单个方法的通用元数据的唯一容器。

  • 'name','module','file','line','sig`

    用于计算机和人类的唯一方法定义的元数据。

  • 'ambig`

    可能与此有歧义的其他方法的缓存。

  • "专业"

    为该方法创建的所有MethodInstance的缓存,用于确保唯一性。 唯一性是保证效率所必需的,特别是对于增量预编译和跟踪方法失效。

  • '来源`

    原始源代码(如果可用,通常以压缩形式)。

  • `发电机'

    可调用对象,可执行该对象以获取特定方法签名的专用源。

  • "根"

    指向已插值到AST中的非AST对象的指针,这些对象是AST压缩、类型推断或本机代码生成所需的。

  • 'nargs`,'isva`,'called`,`is_for_opaque_closure',

    此方法的源代码的描述性位字段。

  • `primary_world'

    该方法的"世界时代"(方法定义的层次结构)。

方法/方法

描述方法的单个可调用签名的唯一容器。 有关安全更改这些字段的重要信息,请参阅 多线程锁的正确维护

  • "眼镜"

    此MethodInstance的主键。 通过搜索`def来保证唯一性。专业化'。

  • 'def`

    此函数描述的方法('方法')。 或者一个模块('Module'),如果它是在模块中扩展的顶级lambda并且不是方法的一部分。

  • `sparam_vals'

    "SpecTypes"中的静态参数值。 为’方法中的’MethodInstance’容器。未指定`是空向量’SimpleVector'。 但是对于来自`MethodTable`缓存的运行时环境的`MethodInstance’容器,该值将始终被定义和索引。

  • "未受影响`

    顶级转换器的未压缩源代码。 此外,对于生成的函数,这是源代码可以位于的许多地方之一。

  • `backedges'

    我们保留一个缓存依赖关系的反向列表,以有效地跟踪新方法定义后可能需要的额外重新分析或重新编译工作。 为此,我们保留了一个已派生或优化的其他"MethodInstance"容器的列表,以包含对此"MethodInstance"容器的可能调用。 优化结果可能存储在缓存中的某个位置('缓存`),或者它可能是不需要缓存的东西的结果,例如常量传播。 因此,我们将所有这些信息组合到各种缓存条目中(几乎总是只有一个适用的缓存条目具有max_world的参考值)。

  • '缓存`

    共享此模板实例的"CodeInstance"对象的缓存。

[医]代码

  • 'def`

    从中获取此缓存条目的’MethodInstance’容器。

  • "业主`

    表示此"代码"所有者的令牌。 将使用’jl_egal’进行匹配。

  • 'rettype`/`rettype_const'

    `SpecFunctionObject`字段的输出返回类型,它(在大多数情况下)也是整个函数的计算返回类型。

  • '推断`

    它可能包含此函数的输出源代码的缓存,或者它可能具有值’nothing’以简单地指示没有输出('rettype')。

  • 'ftpr`

    通用jlcall入口点。

  • jlcall_api

    调用`fptr’时使用的ABI。 以下是一些重要的值。

    * 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令牌的特殊值,则其值尚不清楚。 您可以继续使用它,直到有需要审查的信息。

代码信息

一个(通常是临时的)容器,用于存储降级的源代码。

  • '代码`

    '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位运算符级标志。 有关更多信息,请参阅julia中`jl_code_info_t’的定义。h文件。

  • 'linetable`

    源代码位置对象的数组。

  • `codelocs'

    "Linetable"中的整数索引数组,指示与每个运算符关联的位置。

可选字段:

  • 'slottypes`

    插槽的类型数组。

  • `rettype'

    输出为缩减形式返回类型(IR)。 默认值为"Any"。

  • `method_for_inference_limit_heuristics'

    'method_for_inference_heuristics’扩展此方法的生成器,如果在输出期间需要的话。

  • "家长`

    "拥有"此对象的’MethodInstance’容器(如果适用)。

  • `边缘'

    将边传递给应该无效的方法实例。

  • 'min_world'/'max_world`

    此代码在输出时有效的"世界年龄"(方法定义层次结构)范围。

逻辑属性:

  • '推断`

    是否是通过类型推断得到的。

  • 内联

    是否适合包埋。

  • '传播_inbounds`

    嵌入时是否应该分发'@inbounds`,以便跳过`@boundscheck’块。

'UInt8’参数:

  • '康斯特普` 0—​使用启发式 1—​攻击模式 **2—​无

  • "纯度"由5位标志组成: '0x01<<0'--此方法保证一致返回控制或终止执行(:consistent) '0x01<<1'--此方法没有外部语义上可见的副作用(':effect_free'` '0x01<<2'--此方法保证不会引发异常(':nothrow`) '0x01<<3'--此方法保证终止执行(:terminates_globally' **'0x01<<4'--该方法内部执行的语法顺序保证终止执行(:terminates_locally'

    有关更多信息,请参阅"基本"文档。@assume_effects'。