title: Rakudo and NQP Internals
subtitle: The guts tormented implementers made
author: Jonathan Worthington

课程概览 - 第二天

欢迎回来. 今天我们会涉及到如下话题:

• 6model
• Bounded Serialization and Module Loading
• The regex and grammar engine
• The JVM backend
• The MoarVM backend

对象系统的组成成分

什么是 6model?

6model 提供了一组用于构建类型和对象系统的原语.

Rakudo 的类, roles, 枚举和 subset 类型都由这些原语组装在一起. NQP 也是, 尽管 NQP 的对象系统更简单, 它仅仅提供了类和 roles.

这些原语已经在 Parrot 和 JVM 虚拟机上实现了. MoarVM 也提供了那些原语, 但是它走的更远, 它让 6model 成为 MoarVM 的对象系统.

那些原语可能比你想象的更加原始. 例如 6model 没有内置继承或角色组合的概念. 这些东西在更高的层级中创建.

Object = 行为 + 状态

无论什么语言, 你发现对象总有:

• 对象继承机制, 对象可以拥有 状态
• 接收一个对象和名字, 使用名字定位一个行为(假设它存在), 并调用它.

状态可以由类携带, 或自由存在。行为可能直接地附加在对象上，附加在每个类上，或者通过多种分派机制定位某个行为。

但总是会有状态和行为。

类型

大多数语言也有一些类型的概念。通常，类型属于彼此之间的关系。例如，给出：

class Event {
    has $.name;
    has $.start-date;
    has $.days;
}
class Hackathon is Event {
    has $.topic;
    has @.hackers;
}

我们可以说 Hackathon 是 Event 的子类型.

Package 种类

我们不仅有不同的类型，我们有不同种类的类型。在 Raku 中，这些对应于不同的包和类型声明符。

package     module      knowhow     class
grammar     role        enum        subset

它们具有相当不同的性质，并且行为方式相当不同。例如，针对 “subset” 类型的类型检查涉及调用它的 “where” 从句.

抛开差异，他们每个都会导致某种代表他们声明的类型的类型对象。

元对象

因此，如果 6model 本身不知道继承和角色组合这样的事情是什么，更不用说子集类型了，这些东西在哪里实现？

答案在于元对象。每个存在的对象都有一个与之关联的元对象，它描述了该对象是如何工作的。许多对象可能具有相同的元对象。例如，在 Raku 中，同一个类的所有对象将共享一个元对象。

要理解的是元对象只是一个对象。
有什么不可思议的。它只是碰巧拥有 new_type，add_method，add_parent 等名字的方法。因此，元对象不绑定到特定的目标虚拟机。

Representations

元对象对对象的类型和语义感兴趣。但是，他们明确地不关心对象在内存中是如何布局的。

与对象有关的内存的分配，布局和访问由表示来控制。

表示不是对象。他们是低级的并且每个后端的实现方式也不同。但他们提供的API是相同的。

因此，除了具有元对象外，每个对象都有一个表示。虽然元对象可能存在于每种类型中，但表示的数量却少得多。

STables 把元对象和表示组合在一起

虽然对象拥有一个元对象和一个表示，但是在这之间实际上有一个间接层：STable。稍后我们会更仔细地看这些。

我们的第一个元对象

这是我们的第一个对象系统。它支持具有方法的类型。类型将始终具有 P6opaque 表示。

class SimpleHOW {
    has %!methods;

    method new_type() {
        nqp::newtype(self.new(), 'P6opaque')
    }

    method add_method($obj, $name, $code) {
        %!methods{$name} := $code;
    }

    method find_method($obj, $name) {
        %!methods{$name}
    }
}

使用我们的元对象

首先，我们来创建一个新的类型，并添加单个方法。

my $Greeter := SimpleHOW.new_type();
$Greeter.HOW.add_method($Greeter, 'greet',
    -> $self, $name { say("Hello, $name") });

现在 $Greeter 变量包含新类型的类型对象。如果我们在它身上调用 greet 方法：

$Greeter.greet('Katerina');

那么，我们的元对象的 find_method 方法将被调用, 使用 greet 参数，它返回的任何东西都会被调用，传递 $Greeter 和字符串 Katerina 作为参数。

HOW’s that?

HOW 这个词通常用于元对象。按照惯例，关键字 class 的元对象将有一个像 ClassHOW 这样的名字。这不是严格遵循的，即使在 Rakudo 和 NQP 中。但是所有类型的元对象都以 HOW 结尾。

如果你拿一个对象并使用 .HOW，你就会得到元对象。我们可以按照我们的意愿去追逐这个链条。

my $mo := $Greeter.HOW;
say($mo.HOW.name($mo));             # SimpleHOW
my $momo := $mo.HOW;
say($momo.HOW.name($momo));         # NQPClassHOW
my $momomo := $momo.HOW;
say($momomo.HOW.name($momomo));     # KnowHOW

KnowHOW, the root of it all

如果你在任何对象上追逐足够多的 HOW 链，最终你会达到被称为 KnowHOW 的东西。 继续前进，你就开始兜圈子了; 链的末端是自我描述的。

KnowHOW 是由 6model 提供的仅有的元对象。它支持:

• Having a name
• Having attributes
• Having methods
• In a type check, it only type checks against itself

就是这些而已。没有角色组合。没有继承。

knowhow 声明符

Rakudo 和 NQP 都存在 knowhow 包声明符。 你没理由自己使用它。 但是，在 NQP 的 src/how 中，你会发现一堆使用它的元对象:

NQPModuleHOW                An NQP module
NQPClassHOW                 An NQP class or grammar
NQPNativeHOW                An NQP native type (int/num/str)
NQPParametricRoleHOW        An NQP role declaration
NQPConcreteRoleHOW          An NQP role made concrete for a given class
NQPCurriedRoleHOW           An NQP role with some arguments pre-set

当然，在实现类的元对象可用之前，我们不能使用 class！ 因此，knowhow 就是我们所拥有的。

Giving Rubyish classes

我们稍后会看一下 NQP 和 Rakudo 的元对象。 但首先，为了看到一些更易于管理的东西，让我们回到我们昨天工作的 Rubyish 编译器并添加非常基本的 OO 支持：

• 声明一个类
• 添加方法
• 使用 new 语句创建类的实例
• 在类上调用方法

我们暂时将继承和属性放在一边; 事实上，我们将使用 NQP 或 Raku 元对象来研究它们。

解析类的定义

解析相对容易，但是我们设置了一些与方法相关的额外动态变量。 我们接下来会看到他们的用法。

token statement:sym<class> {
    :my $*IN_CLASS := 1;
    :my @*METHODS;
    'class' h+ <classbody>
}
rule classbody {
    :my $*CUR_BLOCK := QAST::Block.new(QAST::Stmts.new());
    <ident> n
    <statementlist>
    'end'
}

更新方法的 def

方法声明就像函数一样。 在类的作用域内，应该将函数定义添加到周围的类中。 def 的 action 方法可以更新如下：

method statement:sym<def>($/) {
    my $install := $<defbody>.ast;
    $*CUR_BLOCK[0].push(QAST::Op.new(
        :op('bind'),
        QAST::Var.new( :name($install.name), :scope('lexical'),
            :decl('var') ),
        $install
    ));
    if $*IN_CLASS {
        @*METHODS.push($install);
    }
    make QAST::Op.new( :op('null') );
}

即, 把 QAST::Block 推入到类的 code>@*METHODS</code 中。

一个简单的元对象

我们之前写过的元对象就足够好了。 这是一些小调整。

class RubyishClassHOW {
    has $!name;
    has %!methods;

    method new_type(:$name!) {
        nqp::newtype(self.new(:$name), 'HashAttrStore')
    }

    method add_method($obj, $name, $code) {
        %!methods{$name} := $code;
    }

    method find_method($obj, $name) {
        %!methods{$name}
    }
}

构建元对象 (1)

在 Rubyish 中, 我们会生成构建元对象的代码。首先, 让我们关注 classbody action 方法。

method classbody($/) {
    $*CUR_BLOCK.push($<statementlist>.ast);
    $*CUR_BLOCK.blocktype('immediate');
    make $*CUR_BLOCK;
}

注意 blocktype 是如何被设置为 immediate 的，因为我们希望类体中的代码作为程序主线的一部分运行。

构建元对象 (2)

我们损坏了名称，然后使用 RubyishClassHOW 创建一个新的类型对象来表示它。 请注意，QAST:: WVal 是一种引用对象的方法; 我们稍后会看到更多。

method statement:sym<class>($/) {
    my $body_block  := $<classbody>.ast;
    my $class_stmts := QAST::Stmts.new( $body_block );
    my $ins_name    := '::' ~ $<classbody><ident>;
    $class_stmts.push(QAST::Op.new(
        :op('bind'),
        QAST::Var.new( :name($ins_name), :scope('lexical'),
            :decl('var') ),
        QAST::Op.new(
            :op('callmethod'), :name('new_type'),
            QAST::WVal.new( :value(RubyishClassHOW) ),
            QAST::SVal.new( :value(~$<classbody><ident>),
                :named('name') ) )
        ));

    # <Method code comes here>
    make $class_stmts;
}

构建元对象 (3)

我们还发出对 add_method 方法的调用来为类构建方法表。 回想一下，QAST::BVal 允许我们引用树中其他地方安装的 QAST::Block。

my $class_var := QAST::Var.new( :name($ins_name), :scope('lexical') );
for @*METHODS {
    $class_stmts.push(QAST::Op.new(
        :op('callmethod'), :name('add_method'),
        QAST::Op.new( :op('how'), $class_var ),
        $class_var,
        QAST::SVal.new( :value($_.name) ),
        QAST::BVal.new( :value($_) )));
}

有了这个，我们就有了类和方法。

new 关键字

解析 new 并不令人惊讶（我们跳过构造函数参数）：

token term:sym<new> {
    'new' h+ :s <ident> '(' ')'
}

这些 action 会破坏类名以查找它，然后使用 create NQP op 来创建它的实例。

method term:sym<new>($/) {
    make QAST::Op.new(
        :op('create'),
        QAST::Var.new( :name('::' ~ ~$<ident>), :scope('lexical') )
    );
}

方法调用 (1)

最后但并非最不重要的是，我们需要解析方法调用。 这些可以作为一种后缀处理，具有非常严格的优先级。 首先，我们添加级别：

Rubyish::Grammar.O(':prec<y=>, :assoc<unary>', '%methodop');

然后是解析，这与解析函数调用的方式并不太相似。

token postfix:sym<.>  {
    '.' <ident> '(' :s <EXPR>* % [ ',' ] ')'
    <O('%methodop')>
}

方法调用 (2)

方法调用的 action 相对简单。

method postfix:sym<.>($/) {
    my $meth_call := QAST::Op.new( :op('callmethod'), :name(~$<ident>) );
    for $<EXPR> {
        $meth_call.push($_.ast);
    }
    make $meth_call;
}

发生“魔法”的关键点是 EXPR action 方法将取消后缀应用的术语，这意味着它成为第一个孩子（因而是调用者）。

Exercise 7

在本练习中，您将为 PHPish 添加对类和方法的基本支持。
这将涉及：

• 使用方法为类编写基本元对象
• 检查它是否独立运行
• 为类，方法，新语句和方法调用添加解析
• 添加相关的 action 方法以使工作正常

有关更多信息，请参阅练习册。

STables

每个对象都有一个元对象和一个表示。 但是，它并没有直接指向他们。 相反，每个对象都指向一个 s-table，即共享表(shared table)的缩写。

STable 表示一种类型，并且每个 HOW/REPR 组合都存在。 这是 MoarVM 的 MVMSTable 结构的简化版本:

struct MVMSTable {
    MVMREPROps *REPR;   /* The representation operation table. */
    MVMObject  *HOW;    /* The meta-object. */
    MVMObject  *WHAT;   /* The type-object. */
    MVMObject  *WHO;    /* The underlying package stash. */
    /* More... */
};

表示操作

表示操作分为:

• 常见的的东西：基于表示创建新类型，组成该类型（然后可以计算内存布局），分配，克隆，更改类型（用于 mixins），序列化和反序列化
• 装箱：对于作为原生类型（int/str/num）的装箱类型，get/set 装箱值
• 属性：对于可以存储对象属性的类型，get/bind 属性值以及计算访问提示
• Positional：用于提供类似数组存储的类型，通过索引获取和绑定，push/pop/shift/unshift, splice, 设置元素
• Associative：用于提供类似哈希存储的类型，按键获取和绑定，按键判断是否存在，按键删除

表示可以选择它支持上面的哪些。

常见表示

在使用 NQP 和 rakudo 时，您将遇到的最常见的表示形式是:

P6opaque            Opaque attribute storage; default in Raku
P6int               A native integer; flattens into a P6opaque
P6num               A native float; flattens into a P6opaque
P6str               A native string reference; flattens into a P6opaque
P6bigint            Big integer; flattens into a P6opaque
VMArray             Automatically resizing array, type-parametric
VMHash              Hash table
Uninstantiable      Type object only; used for module, role, etc.

类型设置

nqp::newtype 操作是类型创建的核心。 例如，这是 NQPModuleHOW 中的 new_type 方法。 它创建一个新的元对象，基于它创建一个新类型和 Uninstantiable 表示，并给它一个空的哈希作为它的藏匿处:

method new_type(:$name = '<anon>') {
    my $metaobj := self.new(:name($name));
    nqp::setwho(nqp::newtype($metaobj, 'Uninstantiable'), {});
}

nqp::newtype 创建一个新的类型对象和 STable。 它将类型对象指向 STable，将 STable 的 WHAT 字段指向类型对象。 然后，它将 STable 的 HOW 字段设置为指定的元对象，并将 REPROps 设置为 Uninstantiable 的操作表。

类型组合

各种表示需要类型来完成组合阶段。 对于其他东西，它是可选的。

表示组合通常发生在类组合时（通常在类声明的闭合 } 处完成）。 当元对象有机会配置底层表示时。

例如，必须为 P6opaque 配置应为其计算布局的属性。

# <build attribute info array up into @repr_info>
my %info := nqp::hash();
%info<attribute> := @repr_info;
nqp::composetype($obj, %info)

repr-compose-protocol.markdown 详细记录了这个。

方法缓存

如果每个方法调用真的涉及调用 find_method，那么方法分派就太慢了。 因此，许多类型发布了方法缓存 ，是一个将方法名映射到要调用的东西的哈希表。 这是通过反向遍历解析方法顺序来完成的（所以我们正确地覆盖）。

method publish_method_cache($obj) {
    my %cache;
    my @mro_reversed := reverse(@!mro);
    for @mro_reversed {
        for $_.HOW.method_table($_) {
            %cache{nqp::iterkey_s($_)} := nqp::iterval($_);
        }
    }
    nqp::setmethcache($obj, %cache);
    nqp::setmethcacheauth($obj, 1);
}

方法缓存挂起了 STable。

授权方法缓存

我们可以选择方法缓存是否具有授权:

nqp::setmethcacheauth($obj, 0);     # 非授权模式; 默认
nqp::setmethcacheauth($obj, 1);     # 授权模式

这实际上只是控制在方法缓存中找不到所谈论中的方法时会发生什么 。 在授权模式下，缓存被视为具有完整的方法集。 在非授权模式，如果在缓存中找不到该方法， 我们回退到调用 find_method。

在可能的情况下拥有授权方法缓存很好，因为它可以快速回应 nqp::can(...)。 但是，任何想要做回退处理的类型不能拥有授权模式。 Rakudo 按类型决定授权。

类型检查

类型检查出现在 Raku 中的许多地方：

if $obj ~~ SomeType { ... }         # 显式检查
my SomeType $obj = ...;             # 变量赋值
sub foo(SomeType $obj) { ... }      # 参数绑定

这些最终都归结为同样的操作， nqp::istype。 但是，SomeType 花样百出, 它可能是众多类型中的一种：

class SomeType { }              # Class type
role SomeType { }               # Role type
subset SomeType where { ... }   # Subset type

Left-side-knows 检查

对于某些类型，被检查的对象有答案。 这是子类型关系的情况。

Int ~~ Mu           # Int 知道它继承自 Mu
Block ~~ Callable   # Block 知道它能 Callable

这些情况由 type_check 方法处理。

method type_check($obj, $checkee) {
    for self.mro($obj) {
        return 1 if $_ =:= $checkee;
        if nqp::can($_.HOW, 'role_typecheck_list') {
            for $_.HOW.role_typecheck_list($_) {
                return 1 if $_ =:= $checkee;
            }
        }
    }
    return 0;
}

类型检查缓存

再次，真正每个级别都迭代 MRO 和组合的角色会很慢。 因此，left-side-knows 检查通常由发布类型检查(type-check)缓存的元对象处理。

method publish_type_cache($obj) {
    my @tc;
    for self.mro($obj) {
        @tc.push($_);
        if nqp::can($_.HOW, 'role_typecheck_list') {
            for $_.HOW.role_typecheck_list($_) {
                @tc.push($_);
            }
        }
    }
    nqp::settypecache($obj, @tc)
}

Right-side-knows 检查 (1)

还有其他种类的类型，它是我们的检查是否需要驱动检查的类型。 例如， 子集类型是这样的:

subset Even of Int where * % 2 == 0;

我们需要调用与 Even 子集类型相关联的代码作为类型检查的一部分:

say 11 ~~ Even    # False
say 42 ~~ Even    # True

Right-side-knows 检查 (2)

这些类型实现了 accepts_type 方法。 例如，这是 Raku 的 SubsetHOW 中的一个:

method accepts_type($obj, $checkee) {
    nqp::istype($checkee, $!refinee) &&
        nqp::istrue($!refinement.ACCEPTS($checkee))
}

它还必须为此设置适当的类型检查模式以使其能工作:

nqp::settypecheckmode($type, 2)

Boolification

事实证明，一个相对 hot-path 的操作是决定对象是否将在布尔上下文中计算为 true 或 false。 该 nqp::istrue 操作用于测试对象的真假。 还有一个 nqp::isfalse 操作。

对象如何通过 nqp::setboolspec 设置 boolifies, 它从下面的列表中获取一个标志和一个可选的代码对象。

0   调用指定的代码对象，将对象传递给 test 
1   开箱为int; 非零为真 
2   开箱为浮点数; 非零为真 
3   开箱为字符串; 非空为真 
4   和上面一样，但 "0" 被认为是假 
5   如果是类型对象，则返回 false，否则返回 true 
6   开箱为或视为一个大整数; 非零为真 
7   对于迭代器对象; 如果有更多可用项，则为 true 
8   对于基于 VMArray/VMHash 的对象; 如果 elems 非零，则为 true

调用

还有一个调用规范机制，它表示如果对象被调用（调用）会发生什么。

在 Rakudo 中，通常也在 NQP 中，我们有代码对象。 这些反过来持有 VM 级代码对象。 当我们调用代码对象时需要将调用转发到包含的代码对象。

以下是 NQP 设置的示例:

my knowhow NQPRoutine {
    has $!do;
    ...
}
nqp::setinvokespec(NQPRoutine, NQPRoutine, '$!do', nqp::null);

在 Rakudo 中，请参阅 Raku::Metamodel::InvocationProtocol。

NQP 的元对象

NQP 的元对象都是使用 knowhow 元对象实现的。 他们也不能假设存在 NQP 设置，意味着你会在那里找到一些奇怪的代码。

• NQP 迭代器类型为哈希启用 .key 和 .value 方法尚未设置，因此此代码使用 nqp::iterkey_s 和 nqp::iterval。
• 标量没有 NQPMu 默认值，所以空标量将为 null; 因此 nqp::isnull 会被经常使用。

值得庆幸的是，您需要处理此代码的机会是非常低的。 它也比较紧凑; NQPClassHOW，最复杂的元对象，基本上只有大约 800 行直截了当的代码。

Rakudo 的元对象: 概览

Rakudo 的故事大不相同。 Rakudo 的元对象是根据 NQP 的类和角色实现的。 这意味着继承和角色组合是可用的。

因此，由于 Raku 对象系统的丰富性, 虽然 Rakudo 的元对象必须处理很多, 但是它们被非常巧妙的分解了 。

每个声明符都有一个元对象 （所以 class 映射到 ClassHOW），以及角色的一些额外位（因其类型参数而实现起来相当复杂）。

但是，很多功能都会被分解到角色中, 它们在不同的元对象中被重用。

例子: ClassHOW

以下是 Raku::Metamodel::ClassHOW 完成的角色：

Naming                      Documenting
Versioning                  Stashing
AttributeContainer          MethodContainer
PrivateMethodContainer      MultiMethodContainer
RoleContainer               MultipleInheritance
DefaultParent               C3MRO
MROBasedMethodDispatch      MROBasedTypeChecking
Trusting                    BUILDPLAN
Mixins                      ArrayType
BoolificationProtocol       REPRComposeProtocol
InvocationProtocol

在这些名称中，您还将识别许多 Raku 功能，和我们在本节中介绍的 6model 概念中的一些。

例子: EnumHOW

如果我们看看 Raku::Metamodel::EnumHOW，我们会看到它重用了如下几个角色:

Naming                      Stashing
AttributeContainer          MethodContainer
MultiMethodContainer        RoleContainer
MROBasedMethodDispatch      MROBasedTypeChecking
BUILDPLAN                   BoolificationProtocol
REPRComposeProtocol         InvocationProtocol

事实上，它只组合了一个额外的角色:

BaseType

除了角色，ClassHOW 是 250 行代码, EnumHOW 是 150 行代码。 因此，大多数有趣的东西都存在于角色中。

例子: Naming

有些角色非常简单。 例如，所有的元对象组成 Naming 角色，它只提供两个方法和 $!name 属性:

role Raku::Metamodel::Naming {
    has $!name;
    method set_name($obj, $name) {
        $!name := $name
    }
    method name($obj) {
        $!name
    }
}

代码最多的角色是 C3MRO，它计算 C3 方法解析顺序。 不过，它仍然只有 150 行代码。 要点：事情分为可管理的部分。

例子: GrammarHOW

这是最简单的元对象：

class Raku::Metamodel::GrammarHOW
    is Raku::Metamodel::ClassHOW
    does Raku::Metamodel::DefaultParent
{
}

从本质上讲，grammar 可以完成 class 所做的一切，但是组合 DefaultParent 角色，以便在 BOOTSTRAP 中使用不同的默认父级配置启用 grammar：

Raku::Metamodel::ClassHOW.set_default_parent_type(Any);
Raku::Metamodel::GrammarHOW.set_default_parent_type(Grammar);

容器处理

到目前为止，我们已经看到一种类型可以给出一个 boolification 规范和一个调用规范。 还有一个： 容器规范 。 这在 Raku 中用于实现 Scalar 容器类型。

有几个操作与此有关:

setcontspec         将类型配置为标量容器类型
iscont              检查对象是否是标量容器
decont              获取容器内的值
assign              将值赋值给容器
assignunchecked     赋值，假设不需要进行类型检查

例如，Rakudo 的 BOOTSTRAP 会:

nqp::setcontspec(Scalar, 'rakudo_scalar', nqp::null());

自动去容器化

有人可能想知道为什么 nqp::decont 不需要在 Raku 中无处不在。答案是一系列的 nqp::ops 将自动为您执行 nqp::decont 操作。

一个常见的例外是*属性访问没有去容器化 。 这意味着 nqp::getattr 和它的朋友们的第一个参数可能需要一个显式的 nqp::decont。

nqp::getattr(nqp::decont(@list.Parcel), Parcel, '$!storage')

但是，因为 self 被定义为始终去容器化, 所以这通常不是问题。

练习 8

随着时间的推移，将 PHPish 对象系统扩展为：

• 方法缓存（如果它有用，您可能需要计时）
• 单继承类（需要更新你的方法缓存代码）
• 接口（这些将需要一个不同的元对象，而你将需要为此类添加一个 compose-time，以检查接口中的所有命名方法都提供好了）

像往常一样，练习册有更多提示。

有界序列化和模块加载

让我们拯救世界吧!

一个问题

当我们在 Rubyish 中构建对象支持时，我们通过发射代码以在元对象上做调用。 这样做明显会有启动时间上的缺点。 然而，在 Raku 中，这种方法面临很多更严峻的挑战。

考虑以下例子:

class ABoringExample {
    method yawn() { say "This is at compile time!"; }
}
BEGIN { ABoringExample.yawn }

我们编译时会运行 BEGIN 块。 因此，ABoringExample 的类型对象和元对象需要在我们运行 BEGIN 块时可用。

此外，这必须适用于用户定义的元对象。

这个问题无处不在

子例程声明会生成一个 Sub 对象，它反过来指向一个 Signature 对象而该对象反过来有一个 Parameter 对象在里面。

所有这些都需要在编译时构建。 不仅仅是因为我们可以调用该 sub，但也因为 traits 可能需要混合到其中:

role StoredProcWrapper { has $.sp_name }
multi trait_mod:<is>(Routine:D $r, :sp_wrapper($sp_name)!) {
    $r does StoredProcName($sp_name)
}
# ...
sub LoadStuffAsObjects($id) is sp_wrapper('LoadStuff') {
    call_sp($id).map({ Stuff.new(|%($_)) })
}

编译时 vs. 运行时

一般来说，问题是我们需要能够在编译时建立起对象和元对象，然后在运行时指向它们。 而且，这是一个非常常见的情况，所以需要高效。

这本身并不会太糟糕。 但是，模块预编译使这一点变得更加棘手： 在编译时创建的对象可能需要跨过一个进程边界，保存到磁盘，然后在未来某个点加载。

这是序列化上下文，有界序列化。那么 World 开始发挥作用。

The World

我们的小型 Rubyish 语言缺少的，但是 NQP 和 Rakudo 两者都有的一个概念是 World 类。 而 Actions 类专注于 QAST 树，因而是程序的运行时语义 ，World 专注于管理编译期间的声明和元对象。

world 每个编译单元总是具有唯一句柄。 这个可以基于原始源文本，例如在 Rakudo 中:

my $file := nqp::getlexdyn('$?FILES');
my $source_id := nqp::sha1(
    nqp::defined(%*COMPILING<%?OPTIONS><outer_ctx>)
        ?? self.target() ~ $sc_id++                 # REPL/eval case
        !! self.target());                          # Common case
my $*W := Raku::World.new(:handle($source_id), :description($file));

序列化上下文

编译时/运行时对象交换的核心关键数据结构是序列化上下文 。 真的，一个序列化上下文只是三个数组，每个上下文一个数组, 用于：

• 对象： 任何 6model 对象都可以出现在此列表中，尽管只有把那些明智的序列化放在那里才有意义
• 代码对象： VM 级代码对象, 此对象在序列化上下文可以指向（或间接地指向 ，由于闭包克隆）
• STables： 这个数组的存在是一个实现细节，其内容永远不会被特定于 VM 的代码的外部直接操纵 ，因此您可以忘记它

每个编译单元有一个 World，反过来 World 拥有序列化上下文。 事实上，给 World.new(...) 的 handle 实际上用于 SC。

将对象放在序列化上下文中

NQP::World 和 Raku::World 都继承自 HLL::World。 它包含一个名为 add_object 的方法，它为当前编译单元添加了一个对象到序列化上下文中。 这里是它如何被用于 NQP::World 中的，例如：

method pkg_create_mo($how, :$name, :$repr) {
    my %args;
    if nqp::defined($name) { %args<name> := $name; }
    if nqp::defined($repr) { %args<repr> := $repr; }
    my $type_obj := $how.new_type(|%args);
    self.add_object($type_obj);
    return $type_obj;
}

引用序列化上下文中的对象

序列化上下文中的任何对象 - 目前正在编译中的或来自于另一个模块或设置 - 都可以使用 QAST::WVal 节点类型引用。

例如，这是 Raku::World 的实用方法:

method add_constant_folded_result($r) {
    self.add_object($r);
    QAST::WVal.new( :value($r) )
}

QAST::WVal 中的 W 意味着 “World”，这应该是一点点, 现在比我们以前遇到的更有意义。 :-)

序列化

编译器工具链知道最终目标是要运行进程中的代码或生成字节码以写入磁盘。

在第一种情况下，这很容易：我们只是确保能从运行的代码中可以看到序列化上下文，并编译一个 QAST::WVal 来索引它。

第二种情况需要在序列化上下文中序列化所有的对象 ，然后反过来序列化它们指向的对象 ，根据需要遍历对象图。

它们被转储为二进制序列化格式，记录在 NQP 仓库中。

What’s “bounded” about it

考虑预编译以下模块:

class Cache is Hash {
    has &!computer;
    submethod BUILD(:&!computer!) { }
    method at_key($key) is rw {
        callsame() //= &!computer($key)
    }
}

这里, Hash 来自 Raku 的 CORE.setting。 显然，我们会在 Cache 元对象的 code>@!parents</code 中遇到这种类型 。 但是，我们不想重新序列化 Hash 类型！

当一个对象已经被另一个 SC 拥有时，我们只写一个对它的引用。 所有权是编译单元的序列化的边界 。

反序列化和修正

序列化的反面是反序列化。 这涉及到接收二进制 blob 表示对象和 STable 并从它那儿重新创建对象。

在这样做时，所有对其他序列化上下文的对象的引用必须被解析。 这意味着模块的依赖关系必须在它反序列化之前被加载。

出于这个原因，HLL::World 有一个 add_load_dependency_task， 用于添加代码（指定为 QAST）以在反序列化发生之前执行 。

还有一个 add_fixup_task，它开启代码的注册以在反序列化发生之后运行。

另一个棘手的问题

一个棘手的问题是如果你试图预编译一个包含以下内容的模块会发生什么:

# Ooh! Let's pretend we're Ruby!
augment class Int {
    method times(&block) {
        for ^self { block($_) }
    }
}

Int 元对象和 STable 在 CORE.setting 中序列化。 但是在这里，另一个模块正在修改元对象，而且 更新的方法缓存挂起了 STable，意味着它也发生了改变。

那么我们该怎么办？

Repossession

当一个对象属于序列化上下文的时候，我们就在编译时，它所属的序列化上下文不是我们当前正在编译过程中的那个。写障碍被触发。

这会将对象的所有权切换为我们正在编译的编译单元的序列化上下文。 它还记录了这种情况。

在序列化时，找到要更新的对象然后使用它的新版本来覆盖它。

Repossession conflicts

这留下了另外一个问题：如果加载两个预编译的模块, 这个两个模块都想要扩充同一个类会发生什么？

曾经，”latest won”。 值得庆幸的是，今天这被检测为收回冲突，由此产生的异常表明加载了两个模块, 它们可能无法一起使用。

这应该是故事的结尾。 但事实并非如此。 事实证明，当 Stash 对象开始以有趣的方式发生冲突时， 当模块使用嵌套包时。 因此，现在有一个冲突解析机制，它查看有冲突的对象并尝试合并他们。 对于 Stash 来说，这很容易。

SC 写障碍控制

与序列化上下文相关的大多数 nqp::ops 很少看到，隐藏在 HLL::World 中。 然而，其中两个逃脱了进入常规代码中：

• nqp::scwbdisable 禁用 repossession 检测写入屏障，意味着对自有对象所做的任何更改不会导致它被重新序列化。这通常是由想要保留缓存的元对象完成的。
• nqp::scwbenable 重新启用 repossession 检测。

请注意，这不是二进制标志，而是一个计数器, 它由第一个 op 递增并由第二个递减。 只有当计数器为零时才会发生收回检测。

意外收回

在 Rakudo 和 NQP 上工作时记住收回是很重要的，因为有时可能会让你始料不及。

例如，在 Rakudo 的 CORE.setting 中，你会找到一个 BEGIN 块 看起来像这样：

BEGIN {
    my Mu $methodcall     := nqp::hash('prec', 'y=');
    ...
    trait_mod:<is>(&postfix:<i>, :prec($methodcall));
    ...
}

如果这是在设置主线中完成的，则会导致对 postfix:<i> 的更改会在 CORE 设置中序列化，它可以通过任何编译单元触发设置加载来收回这个 。

QAST::CompUnit, revisited

由 World 组装的各个片段都使用 QAST::CompUnit 传递到后端。

my $compunit := QAST::CompUnit.new(
    :hll('raku'),
    :sc($*W.sc()),
    :code_ref_blocks($*W.code_ref_blocks()),
    :compilation_mode($*W.is_precompilation_mode()),
    :pre_deserialize($*W.load_dependency_tasks()),
    :post_deserialize($*W.fixup_tasks()),
    :repo_conflict_resolver(QAST::Op.new(
        :op('callmethod'), :name('resolve_repossession_conflicts'),
        QAST::Op.new(
            :op('getcurhllsym'),
            QAST::SVal.new( :value('ModuleLoader') )
        )
    )),
    ...);

模块加载的工作原理 (1)

在 Raku 代码中遇到 use 语句时：

use Term::ANSIColor;

解析模块名，提取任何副词（例如 :from）然后将控制传递给 Raku::World 中的 load_module 方法:

my $lnd    := $*W.dissect_longname($longname);
my $name   := $lnd.name;
my %cp     := $lnd.colonpairs_hash('use');
my $module := $*W.load_module($/, $name, %cp, $*GLOBALish);

模块加载的工作原理 (2)

此 load_module 方法首先代理给 Raku::ModuleLoader 以立即加载模块（必须的, 它可能会引入我们需要的类型或做其他更改以继续解析）。加载模块后，它还会注册一个加载依赖项任务以确保模块已加载, 如果我们在反序列化发生之前的预编译情况中。

method load_module($/, $module_name, %opts, $cur_GLOBALish) {
    my $line   := HLL::Compiler.lineof($/.orig, $/.from, :cache(1));
    my $module := Raku::ModuleLoader.load_module($module_name, %opts,
        $cur_GLOBALish, :$line);

    if self.is_precompilation_mode() {
        self.add_load_dependency_task(:deserialize_past(...));
    }

    return $module;
}

模块加载的工作原理 (3)

在 Raku::ModuleLoader 中，完成了一些工作以找到模块在磁盘中国的位置 。如果它以预编译的形式存在，那么 nqp::loadbytecode op 用于加载它。否则，从磁盘中 slurp 源代码并编译。

加载预编译模块会自动触发它的反序列化。

在两个代码路径上执行的几个奇数行值得一些解释， 然而：

my $*CTXSAVE := self;
my $*MAIN_CTX;
nqp::loadbytecode(%chosen<load>);
%modules_loaded{%chosen<key>} := $module_ctx := $*MAIN_CTX;

模块加载的工作原理 (4)

运行模块的主线时，其词法作用域是由某些相当于这样的代码捕获的：

if $*CTXSAVE && nqp::can($*CTXSAVE, 'ctxsave') {
    $*CTXSAVE.ctxsave();
}

ModuleLoader 有这样一个方法：

method ctxsave() {
    $*MAIN_CTX := nqp::ctxcaller(nqp::ctx());
    $*CTXSAVE := 0;
}

这就是被加载的模块的 UNIT（外部词法作用域）是如何获得的。这反过来用于定位 EXPORT。

模块加载的工作原理 (5)

最后，ModuleLoader 触发全局合并。 这涉及到采用模块想要贡献到的 GLOBAL 和将它们合并到 GLOBAL 的当前视图中。

如果这听起来很奇怪，请注意 Raku 有单独的编译， 意味着所有模块都以一个完全干净和空的 GLOBAL 视图开始。这些视图在模块加载时得到了调和（和冲突发生了争执) 。

最后，返回 UNIT lexpad。

my $UNIT := nqp::ctxlexpad($module_ctx);
if [email protected] {
    unless nqp::isnull($UNIT<GLOBALish>) {
        merge_globals(@GLOBALish[0], $UNIT<GLOBALish>);
    }
}
return $UNIT;

模块加载的工作原理 (6)

到目前为止我们所看到的是 need 会做什么。然后使用 use 导入模块。这在模块加载器中还没有实现， 而是存在于 Raku::World 的 import 方法中。

它做了以下事情：

• 找到需要导入的符号
• 如果有多个分派候选者导出并在目标作用域里也存在一些，则合并候选者列表
• 对于其他符号，将它们直接安装到目标作用域中， 抱怨是否有冲突
• 如果导入了任何运算符，请确保当前语言被扩充 ，以便能够解析它们

正则表达式和 grammar 引擎

内部如何解析 Raku

涉及的部分

正则表达式和 grammar 处理涉及许多组件：

• Raku 的正则表达式 grammar/action，从 src/QRegex/P6Regex，它解析 Raku 正则表达式语法并从中生成 QAST 树。这些不是由 NQP 和 Rakudo 直接使用的 ，而是子类化（例如， 嵌套代码块将在正确的 main 语言中解析 ）
• QAST::Regex QAST 节点，这表示我们可以编译的正则表达式构造的整个范围
• Cursor 对象，在我们解析时保持状态
• Match 对象 ，表示解析的结果
• NFA 构造和求值 ，用于最长 token 匹配

QAST::Regex 节点

此节点涵盖所有正则表达式构造。它有一个 rxtype 属性用于指示要执行的正​​则表达式的类型。

它通常可以放置在 QAST 树中的任何位置, 尽管通常会在 QAST::Block 中找到自己。 而且，它期望声明词法 $¢。

除了少数例外，一旦到达 QAST::Regex 节点，QAST 编译器就会在它下面期望只找到其他 QAST::Regex 节点 。有一个显式的 qastnode rxtype 用于逃避到 QAST 的剩余部分。

我们现在将研究可用的 rxtypes

literal

literal rxtype 表示应该在正则表达式中匹配文字字符串 。要匹配的字符串作为子项传递给节点。

QAST::Regex.new( :rxtype<literal>, 'meerkat' )

它有一个子类型 ignorecase，其匹配不区分大小写的字面值。

QAST::Regex.new( :rxtype<literal>, :subtype<ignorecase>, 'meerkat' )

concat

concat 子类型用于匹配一个接一个的 QAST::Regex 节点序列。它希望这些节点成为它的子节点。

这将与上一张幻灯片相同，但会有点低效:

QAST::Regex.new(
    :rxtype<concat>,
    QAST::Regex.new( :rxtype<literal>, 'meer' ),
    QAST::Regex.new( :rxtype<literal>, 'kat' )
)

scan 和 pass

正则表达式倾向于从 scan 节点开始并以 pass 节点结束。

• scan 将生成代码以通过字符串，尝试匹配每个偏移处的模式，直到匹配成功或用完尝试的字符串为止 。这就是让 'slaughter' ~~ /laughter/ 匹配的原理，尽管 laughter 不在字符串的开头。请注意如果匹配没有锚定它才会这样做 （如果被另一个规则调用则会被锚定） ）。
• pass 将在 Cursor 对象上生成一个对 !cursor_pass 的调用，表示正则表达式已匹配。 对于命名正则表达式，标记和规则，此节点也携带要调用的 action 方法的名称。

一个简单的例子

如果我们给 NQP 以下正则表达式：

/meerkat/

并使用 --target=ast，生成的 QAST::Regex 节点包含到目前为止我们所涉及的所有东西:

- QAST::Regex(:rxtype(concat))
  - QAST::Regex(:rxtype(scan))
  - QAST::Regex(:rxtype(concat)) meerkat
    - QAST::Regex(:rxtype(literal)) meerkat
      - meerkat
  - QAST::Regex(:rxtype(pass))

cclass

用于各种常见的内置字符类， 通常通过反斜杠序列表达。例如，d 和 W 分别成为:

QAST::Regex.new( :rxtype<cclass>, :name<d> )
QAST::Regex.new( :rxtype<cclass>, :name<w>, :negate(1) )

name 的可用值如下：

Code    含义 
.       任何字符 (真的, 任何)
d       任何数字字符（Unicode 识别） 
s       任何空白字符（Unicode 识别） 
w       任何单词字符或下划线（Unicode 识别） 
n       字面 n, a rn 序列,或 Unicode LINE_SEPARATOR 

enumcharlist

用于用户自定义字符类。要求当前字符类是子字符串中指定的任何一个。

例如，v（匹配任何垂直空白字符） 编译成：

QAST::Regex.new(
    :rxtype<enumcharlist>,
    "x[0a,0b,0c,0d,85,2028,2029]"
)

enumcharlist 和用户定义的字符类

enumcharlist 节点也用于以下内容:

/<[A..Z]>/

其中，如 --target=ast 显示，变为：

- QAST::Regex(:rxtype(concat))
  - QAST::Regex(:rxtype(scan))
  - QAST::Regex(:rxtype(concat)) <[A..Z]>
    - QAST::Regex(:rxtype(enumcharlist)) [A..Z]
      - ABCDEFGHIJKLMNOPQRSTUVWXYZ
  - QAST::Regex(:rxtype(pass))

anchor

用于各种零宽断言。例如，^（字符串的开头）编译成：

QAST::Regex.new( :rxtype<anchor>, :subtype<bos> )

可用的子类型是：

bos     字符串的开头 (^)
eos     字符串的结尾 ($)
bol     行的开头 (^^)
eol     行的结尾 ($$)
lwb     左单词边界 (<<)
rwb     右单词边界 (>>)
fail    总是失败 
pass    总是通过

quant

用于量词。min 和 max 属性用于指示子节点可以匹配的类型的数量。max 为 -1 意思是”无限的”。因此，正则表达式 d+ 编译成:

QAST::Regex.new(
    :rxtype<quant>, :min(1), :max(-1),
    QAST::Regex.new( :rxtype<concat>, :name<d> )
)

backtrack 属性也可以设置为以下之一:

g       贪婪匹配 (d+!, 默认)
f       非贪婪 (minimal) 匹配 (d+?)
r       棘轮 (无回溯) 匹配 (d+:)

altseq

尝试按顺序匹配其子项，直到找到匹配的子项。 这提供了 Raku 中的 || 语义，与 Perl 5 中的 | 语义相同。因此：

the || them

编译成:

QAST::Regex.new(
    :rxtype<altseq>,
    QAST::Regex.new( :rxtype<literal>, 'the' ),
    QAST::Regex.new( :rxtype<literal>, 'them' )
)

还有一个 conjseq 对应 Raku 的 &&。

alt

支持 Raku 基于 LTM 的备选分支。正则表达式:

the | them

编译成:

QAST::Regex.new(
    :rxtype<alt>,
    QAST::Regex.new( :rxtype<literal>, 'the' ),
    QAST::Regex.new( :rxtype<literal>, 'them' )
)

如果可以的话，这将始终匹配 them，因为它先适用于具有最长声明前缀的分支。

subrule (1)

用于调用另一个规则，捕获是可选的。 例如:

<ident>

会编译成:

QAST::Regex.new(
    :rxtype<subrule>, :subtype<capture>, :name<ident>,
    QAST::Node.new( QAST::SVal.new( :value('ident') ) )
)

name 属性是要捕获的名字，而 QAST::SVal 节点作为要调用的方法的名字。 额外的孩子节点可能会被提供给 QAST::Node 作为调用的参数。

subrule (2)

关于子规则还有一些值得注意的事情。首先，它不需要捕获。 例如：

<.ws>

将编译成:

QAST::Regex.new(
    :rxtype<subrule>, :subtype<method>,
    QAST::Node.new( QAST::SVal.new( :value('ws') ) )
)

subrule (3)

subrule rxtype 也能够处理零宽断言。 例如：

<?alpha>

将编译成:

QAST::Regex.new(
    :rxtype<subrule>, :subtype<zerowidth>,
    QAST::Node.new( QAST::SVal.new( :value('alpha') ) )
)

subrule (4)

最后，还有两个适用于 subrule 的属性：

• 回溯 设置为 r 将阻止子规则调用回溯。这是在 token 和 rule 中设置的，并且避免了保持很多状态。
• 也可以在此节点上设置 negate。这可能与 zerowidth 子类型结合使用最有用, 因为 <!alpha> 就是那样编译的。

最后但并非最不重要的是，subrule 也用于位置捕获。 而不是指定要调用的方法，捕获的内容被编译到嵌套的 QAST::Block 中并被调用。 这个是确保位置匹配获得自己的 Match 对象。

subcapture

这用于实现不是子规则的命名捕获 。 即：

$<num>=[d+]

会编译成:

QAST::Regex.new(
    :rx<subcapture>, :name<num>,
    QAST::Regex.new(
        :rxtype<quant>, :min(1), :max(-1),
        QAST::Regex.new(
            :rxtype<cclass>, :name<d>
        )
    )
)

Cursor

Cursor 是一个保存匹配当前状态的对象。Cursor 是在进入 token/rule/regex 时创建的， 要么通过要么失败。从那时之后，Cursor 就是不可变了的。

Cursor 内的状态包括：

• 目标字符串
• 我们在当前规则中匹配的位置（-1 表示扫描）
• 匹配达到的当前位置
• 一堆回溯标记（稍后更多）
• 一堆捕获的游标（稍后更多）
• 可能是从 Cursor 生成的缓存 Match 对象
• 对于我们可能稍后回溯的传递的 Cursor， 要调用以重新启动匹配的代码对象

NQPCursorRole

NQP 和 Rakudo 都有自己的游标对象，分别叫做 NQPCursor 和 Cursor。但是，它们都组合了 NQPCursorRole，提供他们的大部分方法。

方法可分为以下几类：

• 常见的内省方法： orig, target, from 和 pos
• 内置规则：before, after, ws, ww, wb, ident, alpha,alnum, upper, lower, digit, xdigit, space, blank, cntrl, punct
• 基础设施方法：所有的名称都以一个 ! 开头, 主要由编译 QAST::Regex 节点生成的代码调用, 或作为实现内置规则的一部分。

It starts with !cursor_init

解析 grammar 或将字符串与正则表达式匹配 首先调用 !cursor_init，它创建一个 Cursor 并用目标字符串初始化它，设置选项（例如是否扫描）。

例如，以下是 NQPCursor 的 parse 方法的实现：

method parse($target, :$rule = 'TOP', :$actions, *%options) {
    my $*ACTIONS := $actions;
    my $cur := self.'!cursor_init'($target, |%options);
    nqp::isinvokable($rule) ??
        $rule($cur).MATCH() !!
        nqp::findmethod($cur, $rule)($cur).MATCH()
}

Inside a rule (1)

进入 token, rule or regex 时发生的第一件事是创建一个新的 Cursor 来跟踪它的工作。这是通过调用 !cursor_start_all 方法来完成的，它返回一个状态数组，包括：

• 新创建的 Cursor
• 目标字符串
• 开始匹配的位置（-1 表示扫描）
• 当前的 Cursor 类型（泛型 $?CLASS）
• 回溯标记堆栈
• 重启标志：如果是重启则为 1，否则为 0

除此之外：由于性能原因, 这个确切的因素将来可能会发生变化。

Inside a rule (2)

由 !cursor_start_all 返回的 Cursor 可能有各种各样的方法在匹配进行时调用它：

• !cursor_start_subcapture 生成一个代表子捕获的 Cursor
• !cursor_capture 将 Cursor 推到捕获堆栈 （通过调用子规则返回的一个或为一个创建的子规则返回的一个 subcapture）
• !cursor_pos 更新 Cursor 中的匹配位置（它仅在需要时同步） ！
• !cursor_pass 如果匹配成功; 到达的位置必须通过，如果它是一个命名的正则表达式，那么名称可以通过; 这也会触发对 action 方法的调用!
• !cursor_fail 如果匹配失败，则游标失败

Inside a rule (3)

一旦 token, rule or regex 完成匹配，要么通过要么失败，它应该返回它工作的 Cursor。

事实上，这是协议：任何被称为 subrule 的东西应该将 Cursor 返回给它的调用者。不这样做会导致错误。

在 Cursor 失败的时候，任何回溯和捕获状态将被丢弃。如果它通过，但不能回溯到里面，然后回溯状态也可以被丢掉。

cstack 和 capturing

cstack（ 要么 Capture stack 或 Cursor stack）就在哪里与捕获相对应的 Cursor 对象（位置或命名） 存储。它也可以用于存储我们可以回溯到的子规则的非捕获的 Cursor 。

在这样的东西里面:

token xblock {
    <EXPR> <.ws> <pblock>
}

cstack 最终会在它结束时有两个 Cursor 匹配：一个由 EXPR 调用返回，另一个由对pblock 的调用返回。

bstack 和 backtracking

bstack 是一堆整数。每个“标记”实际上都包含四个整数（所以只讨论4个项组才有意义，而不是个别整数）：

• 正则表达式中的位置跳回（通常由跳转表解释）; 如果为0，那么回溯应该继续看下一项
• 要回到的字符串中的位置
• 可选地，重复计数（由量词使用）
• 标记点处的 cstack 高度。 这用于丢弃我们回溯的任何捕获。

Match object production

Cursor 或 NQPCursor 上的 MATCH 方法接收 Cursor 并创建一个 Match 或 NQPMatch 对象。我们的 action 方法将这些东西作为 $/ 的参数传递。

它们是通过查看 cstack 产生，观察每个条目的名字，并建立一个位置捕获的数组和命名捕获的哈希。位置捕获正好有一个整数名称。

任何带有 *，+ 或 ** 的量词化捕获都会生成一个捕获结果的数组。

大部分工作都是由 CAPHASH 从 NQPCursorRole 中分解出来的。

最长 Token 匹配

还剩一个重要的正则表达式相关主题：最长 token 匹配(Longest Token Matching, 或简称 LTM)。我们已经在 action 中见过它，但现在我们将花几分钟的时间思考它是如何工作的。

每个正则表达式或备选分支都有一个（可能是零长度） 声明性前缀。它涵盖了从正则表达式开始直到被认为是命令式构造（例如代码块， 正向向前查看，等等）的区域。

token even { d+ { +$/ % 2 == 0 } }
             DDD IIIIIIIIIIIIIIII

声明式前缀始终形成 regular language，并且作为结果可以转化为有限自动机。

NFA 片段

一旦单个 token, rule 或 regex 被编译为 QAST，QAST 树被传递给 QRegex::NFA。

这将探讨 QAST，识别声明式前缀，以及从中构建 NFA（非确定性有限自动机）。

如果 QAST 树包含任何备选分支，那么这些分支中的每个分支也有 NFA 构建和存储。

此时，NFA 尚未准备好进行计算。每当有子规则调用，他们只是命名调用。从这个意义上讲，他们是关于整个 grammar 的泛型 ，可能需要多次具体化（由于 grammar 继承）。

Protoregex 和 alternation NFAs

protoregex 通过构建代表所有候选 NFA 的备选分支的 NFA 来决定调用哪个候选者 。

这个 protoregex NFA 总是特定于特定类型的 grammar。作为制作它的一部分，任何子规则调用都让它们的 NFA 替换该调用。

备选分支进行类似的过程，除了这次 NFA 是由分支的 NFA 构建的。

其中任何一个的结果都是可以针对目标字符串执行的 NFA。

NFA 执行

有两个与执行 NFA 有关的 nqp::ops：

• nfarunproto 根据目标字符串中给定的偏移量来计算 NFA 。它返回一个数组，指示候选者应该被尝试的顺序，不包括任何永远不可能的匹配。
• nfarunalt 根据目标字符串中给定的偏移量来计算 NFA 。然后它会推动所有分支的标记, 它可能会以相反的顺序匹配到 bstack，所以 最好的候选者在最顶端。那么正则表达式引擎只是立即“回溯”以开始尝试可能的候选者。

这两个真的只是围绕同一底层 NFA 计算的薄薄的包装 。

练习 9

在本练习中，您将探索一些正则表达式引擎实现。值得注意的是，你会遇到（如果允许时间）：

• Raku 正则表达式 grammar 和 action
• 如何在 NQP 和 Rakudo 中实现嵌入式代码块
• NFA 存储的地方以及它们的外观

请参阅练习页以获取指导。

JVM 后端

将 Raku 带到 Java 的土地上

The JVM

虚拟机最初是为执行 Java 语言而构建的 现在拥有许多跨越多种语言的语言范式，静态，动态等。

指令集约200条指令，但VM 本身也提供了许多类库方法。

指令集和执行模型是基于堆栈的; 值是加载到要操作的堆栈上，作为方法参数传递等

字节码存在于类文件中，它代表具有字段和方法的单个类。

JVM 指令集: constants

将常量加载到堆栈的各种指令：

• aconst_null 加载空引用
• iconst_m1, iconst_0, iconst_1, … iconst_5 l 加载32位整数 -1,0,1,… 5 到堆栈上
• lconst_0, lconst_1 加载64位整数 0 和 1 到堆栈上
• fconst_0, fconst_1, fconst_2 加载 32 位浮点 0.0,1.0,2.0 到堆栈上
• dconst_0, dconst_1 加载 64 位浮点 0.0,1.0 到堆栈上
• bipush 接收 1 字节的参数并将其加载为 32位 整数
• sipush 接收 2 字节的参数并将其加载为 16 位整数
• ldc, ldc_w and ldc2_w 从常量池（int,float 或 String）中加载常量

JVM 指令集: locals

局部变量可以是整数（32位），长整数（64位），浮点数 （32位），双精度（64位）或对象引用。 有加载和存储它们的指令。

• iload, lload, fload, dload 和 aload 接收一个索引并将该局部变量加载到堆栈上
  istore, lstore, fstore, dstore 和 astore 接收一个索引并将当前堆栈顶部的内容存储到本地变量
• 前四个局部变量（索引 0 到 3）可以是使用 <prefix>[load|store]_[0..3] 形式的特殊指令，例如 iload_0, lload_3, astore_2, dstore_0

long 和 double 都计为两个插槽，因此两个相邻的 long 可能在索引 4 和 6; 试图在索引 5 访问某些东西会导致抱怨分割值！

JVM 指令集: arrays

可以使用 int, long, float, double byte, char, short 或任何引用类型类型创建数组。它们不可调整大小。

• newarray 创建一个包含任何原生类型的数组 其中一个字节表示类型并从栈顶分配长度
• anewarray 用于创建引用类型的数组; 类型被指定为常量池条目
• arraylength 获取数组的长度
• 从数组加载元素涉及把数组放置在堆栈上，索引在堆栈上，然后使用 iaload, laload, faload, daload, aaload, baload, caload 或 saload 其中的一个
• 将元素存储到数组涉及将数组放在堆栈上面 ，索引在堆栈上，值在堆栈上，然后使用 iastore, lastore, fastore, dastore, aastore, bastore, castore, 或 sastore 中的一个

JVM 指令集: arithmetic

可以使用通常的算术和按位运算集：

• 加: iadd, ladd, fadd, dadd
• 减: isub, lsub, fsub, dsub
• 乘: imul, lmul, fmul, dmul
• 除: idiv, ldiv, fdiv, ddiv
• 取模: irem, lrem, frem, drem
• 取反: ineg, lneg, fneg, dneg
• 位移: ishl, lshl, ishr, lshr, iushr, lushr
• 按位: iand, land, ior, lor, ixor, lxor

JVM 指令集: compare/branch

血腥不规则！

对于 long，float 和 double，你使用 lcmp, fcmpl, fcmpg, dcmpl, 或 dcmpg 之一,它给出 -1, 0 或 1（就像各种 cmp 语言一样）。然后你用 ifeq, ifne, iflt, ifge, ifgt, 或 ifle 之一进行分支。

32 位整数比较非常特殊，有自己的指令集, 其比较和分支一体化: if_icmpeq, if_icmpne, if_icmplt, if_icmpge, if_icmpgt 和 if_icmple。

引用可以比较相等或不相等，并且根据 if_acmpeq 和 if_acmpne 进行分支。对于 nullness 空检查和分支，有 ifnull 和 ifnonnull。

最后，有一个无条件的 goto 和一个 tableswitch 用于编译成 switch 语句。

JVM 指令集: 对象和字段

使用 new 指令实例化对象。请注意字节码验证器将强制执行其构造函数 invokespecial（见下一张幻灯片）。

访问字段有四条指令（尽管我们没有经常这样做，对于 6model 对象，它被封装在表示的内部）：

• getstatic 从常量池中获取字段引用, 将静态字段的值加载到堆栈上
• getfield 类似，但期望对象访问来自堆栈的实例字段
• putstatic 从常量池中获取字段引用, 将当前堆栈顶部值存储到静态字段
• putfield 是类似的，但期望对象存储实例字段到位于值下方的堆栈上

JVM 指令集: method calls

实例方法调用期望堆栈包含要调用的对象，然后是任何额外的参数。请注意这些对 Java 对象进行操作而不是对 6model 对象进行操作，所以我们不要把它们用于 Raku 的方法分派！

• invokevirtual 执行正常的虚方法调用
• invokespecial 调用精确类中的方法（用于超级等）
• invokeinterface 通过接口调用方法

还有 invokedynamic，只是期望参数在堆栈上。由于大多数 nqp::ops 是静态方法调用，我们用它很频繁 。

最后，还有 invokedynamic，这是实际的 Raku 级例程和方法调用被连接起来的方式。

JVM 指令集: exceptions

只有一个与异常有关的指令， athrow。它抛出当前位于堆栈顶部的异常对象。

异常处理程序存储为表而不是字节码流。

JVM 指令集: other bits

有各种强制指令可以在原始类型之间进行转换。它们的形式为 <from>2<to>，具有相同的用于数组的单字母代码。i2l, i2f, i2d, l2i, l2f, l2d, f2i, f2l, f2d, d2i, d2l, d2f, i2b, i2c, 和 i2s。

还有许多用于操作堆栈的指令：

• Popping: pop, pop2 (注意 long 或 double 计为 2 个插槽)
• Duplicating: dup, dup2 (同一个规则)
• Swapping: swap (不, 对于 long/double 不存在)

最后, 方法能使用 ireturn, lreturn, freturn, dreturn, areturn, 或 return (void) 方法返回(以当前的堆栈顶部为返回值)。

JAST (1)

为了从 NQP 生成 JVM 字节码，我们构建了一堆 JAST 节点（JVM Abstract Syntax Tree 的缩写）。

有一些节点用于 push 常量：

JAST::PushIVal.new( :value(42) )        # 64-bit integer constant
JAST::PushIndex.new( :value(69) )       # 32-bit integer constant
JAST::PushNVal.new( :value(1.5) )       # 64-bit double constant
JAST::PushSVal.new( :value('beer') )    # String constant

还有一个 JAST::PushCVal，用于 push 类字面值。

JAST (2)

顶级结构由 JAST::Class 节点组成。它公开方法 add_field，它需要一个 JAST::Field，和 add_method，它需要一个 JAST::Method。

JAST::Field 有方法(和具名构造器参数)来设置 name, type 还有它是否是 static 的。

JAST::Method 更复杂。还有一个 name 和标志以表明它是否是 static 的, 它还有 locals 和 arguments，以及它返回的(returns)类型。附加字段捕获词法集，NQP 级异常处理程序等。

JAST (3)

单个指令表示为 JAST::Instruction 节点。

JAST::Instruction.new( :op('aconst_null') )

通常，这些被推到 JAST::InstructionList 中，虽然它们也可以被推到 JAST::Method 内部的指令列表中。

my $il := JAST::InstructionList.new();
$il.append(JAST::PushIVal.new( :value($target) ));
$il.append(JAST::Instruction.new( :op('aload'), 'tc' ));
$il.append(JAST::Instruction.new( :op('invokestatic'), $TYPE_OPS,
    'lexotic_tc', $TYPE_SMO, 'Long', $TYPE_TC ));
# ...

JAST (4)

JAST::Label 节点代表一个标签。在给定的 JAST::Method 内部，标签需要是唯一的。

my $if_id    := $qastcomp.unique($op_name);
my $else_lbl := JAST::Label.new(:name($if_id ~ '_else'));

JAST::Label 可以用在分支中：

$il.append(JAST::Instruction.new($else_lbl,
    :op($op_name eq 'if' ?? 'ifeq' !! 'ifne')));

并且它的位置就是被 push 的地方:

$il.append($else_lbl);

JAST (5)

最后，有 JAST::TryCatch，它代表一个（JVM 级别）异常处理程序。

它需要两个 JAST::InstructionLists，一个组成 try，另一个组成 catch。它还需要指定的异常类型 type。

$il.append(JAST::TryCatch.new(
    :try($try_il),
    :catch($catch_il),
    :type($TYPE_EX_LEX)
));

QAST 到 JAST 翻译器

JAST 提供了一种从 NQP 生成 JVM 字节码的方法。 然而，前端生成 QAST 树。他们之间是一个 QAST 到 JAST 的翻译器，它位于 NQP 的 src/vm/jvm/QAST/ 目录。

总之，包括所有 QAST 节点（包括 regex）的翻译和 nqp::ops，它们大约为 5400 行。 这可能听起来很多，但它大约只有 Raku CORE.setting 的三分之一大小!

它的工作因以下几个因素而复杂化：

• 它正在进行 Continuation Passing Style 转换， 因为它着手处理代码生成 - 虽然这是相对隔离的。
• 对于出现在 Raku 表达式（如 try）中间的东西, JVM 拥有堆栈必须是空的约束。

类型和结果

一切都围绕着四种原始类型，你会在编译器中看到到处都有原始类型:

$RT_INT     a JVM long; 在 NQP 中映射到 int
$RT_NUM     a JVM double; 在 NQP 中映射到 num
$RT_STR     Java String 类; 在 NQP 中映射到 str
$RT_OBJ     6model 对象 (org.raku.nqp.sixmodel.SixModelObject)

编译 QAST 节点或 nqp::op 的代码总是返回一个 Result。此类型将 JAST::InstructionList 与上述类型之一组合在一起，表明它在堆栈上留下的内容 。

$RT_VOID 表示没有结果。

Mapping nqp::ops

为数不多的 nqp::ops 直接映射到 JVM ops:

QAST::OperationsJAST.map_jvm_core_op('neg_i', 'lneg', [$RT_INT], $RT_INT);

其他一些映射到 Java 类库中的函数：

QAST::OperationsJAST.map_classlib_core_op('abs_i', $TYPE_MATH, 'abs',
    [$RT_INT], $RT_INT);

但是，在 NQP 运行时, 大多数映射到对 Ops 类的调用 ，经常传递当前的 ThreadContext 对象:

QAST::OperationsJAST.map_classlib_core_op('create', $TYPE_OPS, 'create',
    [$RT_OBJ], $RT_OBJ, :tc);

运行时支持库

许多 nqp::ops，6model 的 JVM 实现，以及各种其他支持代码存在于 NQP 的 src/vm/jvm/runtime/ 目录中。它内置于 nqp-runtime.jar 库中。

如果修改此代码，通常只需重新构建该 JAR 即可看到效果，而不是重建所有的 NQP。将其复制到它的安装位置，也可以为 Rakudo 更新。

Rakudo 还有一个（小得多）运行时支持库，它被构建到 rakudo-runtime.jar 中。

<随着时间的推移探索>

总结 …

JVM 支持包括将 QAST 树转换为 JVM 字节码，通过称为 JAST 的中间形式，和运行时支持库。

大多数工作都用于提供 JVM 所不原生提供的功能，例如 gather/take 所需的持续支持，6model，在堆栈展开之前, 在堆栈顶部运行的异常处理程序，等等。

从这里开始，需要进行优化，更好的代码生成， 和更好的 invokedynamic 使用。

MoarVM 后端

专为 NQP 和 Rakudo 构建的 VM

MoarVM 概览

使用 6model 作为其原生对象系统。

指令集与 nqp::ops 对齐。

提供两代 generational GC（由半空间复制处理）和 gen2（固定大小的池，除了大对象）

包括 Unicode database 支持，并致力于 NFG 字符串。

支持线程，可能的时候使用无锁数据结构。

MAST

MoarVM 没有汇编语言或中间语言; 相反， MAST（MoarVM 汇编语法树）直接汇编为字节码。

MAST 低于 QAST，与 JAST 相当不同 （由于 VM 的设计相当不同以及 MoarVM 不是基于堆栈的这一事实）。但是，如果你熟悉的两者之一（或两者），你会很快对 MAST 感到宾至如归。毕竟，MAST 和 JAST 是同一个人设计的，并且上述的人也为 QAST 设计做出了贡献。:-)

实际上，作为等效的 QAST 节点, 5 个 MAST 节点共享相同的名字和角色 。

MAST nodes: literals

文字整数，浮点数和字符串, 他们的表示并不令人惊讶:

MAST::IVal.new( :value(42) )
MAST::NVal.new( :value(1.2) )
MAST::SVal.new( :value('cwrw') )

然而，虽然它们的 QAST 等价物基本上可以出现在任何地方，这些 MAST 节点只能用作期望文字的指令的参数 （例如，const_i64, const_n64, consts, argconst[ins]，命名参数中的参数名称绑定指令等）相反大多数指令期望一个本地参数。

MAST: 帧

MoarVM 中的词法作用域最小的可调用单元是帧。 这由 MAST::Frame 节点表示。

一个帧有：

• 一个（高级别）名称和（低级别）一个编译单元唯一 ID
• locals/寄存器列表（没有区别，术语可互换使用）。这些只有整数索引， 不是名字。
• 词法列表。这些都有名称和类型。
• 对其静态外部帧的引用（用于词法查找）
• 指令列表

通常，QAST::Block 映射到 MAST::Frame。

MAST nodes: locals

有一个 MAST::Local 代表 locals（当帧执行时可用的存储空间）：

MAST::Local.new( :index($!frame.add_local($type)) )

实际上，很难看到这是直接构建在 QAST 到 MAST 编译器。这一切都隐藏在一些帮助函数背后：

fresh_o     Make a new object local
fresh_i     Make a new int64 local
fresh_n     Make a new num64 local
fresh_s     Make a new string local

使用后，通常会释放 local，以便可以在帧中的其他地方重复使用。

MAST nodes: lexicals

MoarVM 本身也支持词法变量，这（不同于 locals）从嵌套帧中可以看到。同样，这些节点很少直接在 QAST 编译器中生成，而是由解析词法（计算要看多少帧）的帮助程序生成。

method resolve_lexical($name) {
    my $block := self;
    my $out   := 0;
    while $block {
        if ($block.lexicals()){$name} -> $lex {
            return MAST::Lexical.new( :index($lex.index),
                                      :frames_out($out) );
        }
        $out++;
        $block := $block.outer;
    }
    nqp::die("Could not resolve lexical $name");
}

MAST nodes: ops

MAST::Op 节点表示 MoarVM 的操作指令集。这些通常被 push_op 帮助程序创建并推到指令列表中:

sub push_op(@dest, $op, *@args) {
    nqp::push(@dest, MAST::Op.new(
        :op($op),
        |@args
    ));
}

期望作为参数的节点类型随指令而变化。 例如， push_o 指令需要两个 MAST::Local 节点:

push_op($arr.instructions, 'push_o', $arr_reg, $item_reg);

请注意，此级别没有强制/多态。 如果指令想要 local，那么你就不能使用文字了！

MAST nodes: labels

可以将 MAST::Label 放在指令列表中作为目标的一个分支，并用作某些分叉的 MAST::Ops 的参数。

标签在给定的 MAST::Frame 中必须是唯一的，这就是你经常会看到如下代码的原因：

my $if_id    := $qastcomp.unique($op_name);
my $else_lbl := MAST::Label.new(:name($if_id ~ '_else'));
my $end_lbl  := MAST::Label.new(:name($if_id ~ '_end'));

以下是使用标签的一些示例:

push_op(@ins, 'goto', $end_lbl);
nqp::push(@ins, $else_lbl);

MAST nodes: calls

调用归结为以下几个步骤：获取传入参数缓冲区的参数，设置调用点描述符，指示结果寄存器，并自己进行调用。

这是在 MAST::Call 节点后面抽象的：

nqp::push(@ins, MAST::Call.new(
    :target($callee.result_reg),
    :flags(@arg_flags),
    |@arg_regs,
    :result($res_reg)
));

标志表示寄存器类型，以及命名和展平参数。

MAST nodes: 异常处理程序

异常处理程序用于控制流（例如循环中的 next/redo/last）或真正的异常（在 NQP/Raku 中由 CATCH 捕获）。这两个都设置为 MAST::HandlerScope，表示所涵盖的指令处理程序，它感兴趣的是什么样的异常以及如果处理程序被触发会做什么。

MAST::HandlerScope.new(
    :instructions(@loop_il),
    :category_mask($HandlerCategory::redo),
    :action($HandlerAction::unwind_and_goto),
    :goto($redo_lbl)
)

在这里，action 是简单地展开调用堆栈并转到指定标签。相比之下， CATCH 块的 action 是在堆栈顶部运行一个处理程序块并随后展开。

MAST nodes: 编译单元

最后，MAST 汇编树的顶部始终是 MAST::CompUnit。这有一个帧列表（每一帧都使用 add_frame 方法添加）。

某些帧可以被称为特殊帧：

• deserialize_frame 包含驱动反序列化的代码， 并且将始终在编译单元创建或加载时运行
• load_frame 当编译单元被加载为模块时, 保存应运行的代码
• main_frame 当编译单元是初始入口点时, 保存应运行的代码

它还跟踪生成编译单元的 HLL 以及它依赖的序列化上下文集。

QAST 到 MAST 的翻译器

分布到三个文件中：

• QASTOperationsMAST.nqp 处理 nqp::op 的编译
• QASTRegexCompilerMAST.nqp 处理 QAST::Regex 节点的编译
• QASTCompilerMAST.nqp 处理其余部分以及他们工作的各种寄存器

这些参考：

• MAST 节点
• 关于所有可用 op 的元数据和各种操作

MAST::InstructionList

再次，有一个数据结构用于携带编译 QAST 节点的结果：MAST::InstructionList。它有三块儿信息：

• 指令列表（$il.instructions）
• 保存结果（$il.result_reg)的寄存器（local）
• 结果寄存器类型（$il.result_kind）

有四种主要类型的常量：

• $MVM_reg_obj（6model 对象）
• $MVM_reg_int64（int）
• $MVM_reg_num64（num）
• $MVM_reg_str（str，虽然它实际上也是一个 6model 对象）

Register/local allocation

每个块 $*REGALLOC 跟踪寄存器的使用情况。 尽管有这个名字，它不是以传统方式进行寄存器分配（如图着色）。相反，它保持跟踪可用的临时值，使它们可以重复使用。

获取要使用的新寄存器通常如下：

my $callee_reg := $*REGALLOC.fresh_o(); # also _i, _n, _s

然后可以在不再需要时释放它:

$*REGALLOC.release_register($callee_reg, $MVM_reg_obj);

nqp::op mapping

许多 nqp::ops 在 MoarVM 指令集中具有相似或相同的名称。操作数类型数据也很容易获得，因此不需要在映射中指定:

QAST::MASTOperations.add_core_moarop_mapping('atpos', 'atpos_o');
QAST::MASTOperations.add_core_moarop_mapping('atpos_i', 'atpos_i');

MoarVM 中的某些指令无效，但允许使用 r 值上下文作为 nqp::ops。因此，我们选择其中一个输入操作数作为结果，如果需要的话。

QAST::MASTOperations.add_core_moarop_mapping('bindpos', 'bindpos_o', 2);
QAST::MASTOperations.add_core_moarop_mapping('bindpos_i', 'bindpos_i', 2);

在 MoarVM 内部

顶级 src 目录不直接包含太多东西; 代码被归类到子目录里：

• 6model 包含 6model，REPR 的实现， 序列化…
• core 是 VM 的核心，包含解释器， 参数处理，字节码解码，线程处理， 调用，异常…
• gc 是内存分配和垃圾回收存在的地方
• io 包含与 IO 相关的功能，通常委托真正的工作到 libuv
• mast 包含 MAST 到字节码编译器
• math 包含用于大整数支持的 libtommath 绑定
• platform 是平台特定的代码(因为不同的平台以不同的方式做事)
• strings 包含字符串操作，编码/解码 ASCII，UTF-8 等

总结 …

MoarVM 使用 6model 作为其对象模型并具有与 nqp::op 集良好对齐的指令集。作为结果， 从 QAST 到它的映射相对简单。

它也将是我们支持 NFG 字符串的第一个地方 也应该得到良好的 Perl 5 互操作。

未来的发展将包括 6model 感知的 JIT 编译， 这应该会带来显着的性能提升。

前方的路

这还不是结束??!!!

这还不是全部…

这两天我们已经涵盖了很多方面。

当然，有些东西已被搁置。我们还没有查看每个文件的每一行代码！

而且，当然，我们没有涵盖尚未发明的东西，因为我们没有实现需要它们的 Raku规范。

但是， 我们已经涵盖了所有组成 NQP 和 Rakudo 的关键部分。仔细阅读代码和一点点挖掘，应该有可能弄清楚 NQP 和 Rakudo 做的大部分东西，其中大多数东西已经被发现了。

工具链将会发展

NQP 工具链是为了响应理解 Raku 的需求而发展起来的。随着我们不断学习，这种知识将会处理成工具。

在过去，有一些相当戏剧性的改革。 这些很可能已经结束了，尽管肯定会有更多的教训转化成更好的抽象和 API。

例如，并发/并行工作目前正在进行中, 直接来自 Java 类库的类的术语。 但是，最后，关键的抽象可能会被捕获到 nqp:: ops 中, 等等。

记住 …

编译器并不神奇。他们只是软件。

Raku 是一种大型语言，实现它是非常重要的。 然而，NQP 和 Rakudo 已经通过将问题分解为解耦的碎片来管理复杂性做出了合理的尝试。

事实上，这是唯一可以让它易于管理的东西。 在你 hack 的时候记住这一点。 好的架构需要训练。 您想到的第一个解决方案很少是最好的解决方案。而你感觉不对的东西，通常是最后的解决方案。

请以优雅地解决实现问题而自豪，提问, 不要将代码视为神圣，并确保 --Ofun。

谢谢你!

感谢您参加课程！

还有问题吗?

顺便说一句，在 Edument AB，我们也建立并提供如下课程。。。

• Perl 5
• Git
• 软件架构和领域驱动设计
• JavaScript 和其它 Web 技术
• C# 和 .Net
• 测试驱动开发

有关更多信息，请参阅 http://edument.se/courses/。