Ruby 2.x 源代码学习：语法分析 & 中间代码生成之数据结构

New丶Elements

2019-06-21

LINK_ELEMENT

LINK_ELEMENT 是一个双向链表的"头"节点，包含指向前一个节点和后一个节点的指针，其它结构体通过将 LINK_ELEMENT 放在结构体的头部来将结构体组织成双向链表

// compile.c

typedef struct iseq_link_element {
    enum {
    ISEQ_ELEMENT_NONE,
    ISEQ_ELEMENT_LABEL,
    ISEQ_ELEMENT_INSN,
    ISEQ_ELEMENT_ADJUST
    } type;
    struct iseq_link_element *next;
    struct iseq_link_element *prev;
} LINK_ELEMENT;

以 INSN（表示一条 YNRV 指令）结构体为例，INSN 结构体通过 link 字段将所有的指令链接成一个双向链表

// compile.c

typedef struct iseq_insn_data {
    LINK_ELEMENT link;
    enum ruby_vminsn_type insn_id;
    unsigned int line_no;
    int operand_size;
    int sc_state;
    VALUE *operands;
} INSN;

LINK_ANCHOR

LINK_ANCHOR 结构体用来管理由 LINK_ELEMENT 组成的双向链表，包含表头 anchor 和一个指向双向链表最后一个节点的指针 last，注意 LINK_ANCHOR 本身不包含数据，anchor.next 指向双向链表第一个元素

// compile.c

typedef struct iseq_link_anchor {
    LINK_ELEMENT anchor;
    LINK_ELEMENT *last;
} LINK_ANCHOR;

添加 LINK_ELEMENT

下文讲到创建 INSN 结构体的时候会用到 ADD_ELEM 函数，这里简单介绍一下：

/*
 * elem1, elem2 => elem1, elem2, elem
 */
static void
ADD_ELEM(ISEQ_ARG_DECLARE LINK_ANCHOR *const anchor, LINK_ELEMENT *elem)
{
    elem->prev = anchor->last;
    anchor->last->next = elem;
    anchor->last = elem;
    verify_list("add", anchor);
}

NODE

NODE 结构体用于封装 AST（抽象语法树）的一个节点，NODE 使用了联合体（union）来复用各个语法树节点需要的数据，这也是 C 语言惯用优化手法

// node.h

typedef struct RNode {
    VALUE flags;
    VALUE nd_reserved;        /* ex nd_file */

    union {
        struct RNode *node;
            ID id;
            VALUE value;
            VALUE (*cfunc)(ANYARGS);
            ID *tbl;
    } u1;

    union {
        struct RNode *node;
            ID id;
            long argc;
            VALUE value;
    } u2;

    union {
        struct RNode *node;
            ID id;
            long state;
            struct rb_global_entry *entry;
            struct rb_args_info *args;
            long cnt;
            VALUE value;
    } u3;
} NODE;

node flags

NODE 结构体的 flags 字段包含一系列的比特位，存储了 NODE 的一些属性，通过这种压缩存储可以提高 NODE 结构体的空间利用率

// node.h

/* NODE_FL:
 * 0..4: T_TYPES,
 * 5: KEEP_WB,
 * 6: PROMOTED,
 * 7: NODE_FL_NEWLINE|NODE_FL_CREF_PUSHED_BY_EVAL,
 * 8..14: nd_type,
 * 15..: nd_line
 */

以 nd_type 为例，node.h 定义了 nd_type 在 flag 中的偏移量 NODE_TYPE_SHIFT 以及掩码 NODE_TYPE_MASK，以及获取和设置 nd_type 的宏定义

// node.h

#define NODE_TYPESHIFT 8
#define NODE_TYPEMASK  (((VALUE)0x7f)<<NODE_TYPESHIFT)

#define nd_type(n) ((int) (((RNODE(n))->flags & NODE_TYPEMASK)>>NODE_TYPESHIFT))
#define nd_set_type(n,t) \
    RNODE(n)->flags=((RNODE(n)->flags&~NODE_TYPEMASK)|((((unsigned long)(t))<<NODE_TYPESHIFT)&NODE_TYPEMASK))

node type

node.h 中给出了完整的 node_type 列表，紧跟每个 node_type 后面的宏定义是为了方便访问 not_type

// node.h

enum node_type {
    NODE_SCOPE,
#define NODE_SCOPE NODE_SCOPE
    NODE_BLOCK,
#define NODE_BLOCK NODE_BLOCK
    ...
}

访问 NODE 字段

如果直接以 C 语言联合体的语法访问 NODE 中的字段会导致程序的可读性很差，因此 node.h 中定义了一些宏方便在具体 AST 节点上下文中访问，以 if 语句的 NODE 节点为例，可以通过以下宏定义访问 condition（条件语句块），body（条件为 true 时语句块）以及 else（条件为 false 时语句块）

#define nd_cond  u1.node
#define nd_body  u2.node
#define nd_else  u3.node

新建节点

node.h 中定义了大量的宏方便新建 NODE，这些宏被被组织成一种层次结构
NEW_NODE 宏定义是核心，它直接被展开成 rb_node_newnode 的方法调用

// node.h

#define NEW_NODE(t,a0,a1,a2) rb_node_newnode((t),(VALUE)(a0),(VALUE)(a1),(VALUE)(a2))

我们来看看 rb_node_newnode 的实现：

使用 newobj_of 在 GC 管理的堆空间中分配一个 NODE 节点并初始化
设置节点类型 type

// gc.c

NODE* rb_node_newnode(enum node_type type, VALUE a0, VALUE a1, VALUE a2)
{
    /* TODO: node also should be wb protected */
    NODE *n = (NODE *)newobj_of(0, T_NODE, a0, a1, a2, FALSE); 
    nd_set_type(n, type);
    return n;
}

其它 NEW_XXX 宏引用 NEW_NODE 宏，以 NEW_IF 宏定义（创建if 语句语法树节点）为例：

// node.h

#define NEW_IF(c,t,e) NEW_NODE(NODE_IF,c,t,e)

c 代表 condition，即条件语句对应的 NODE 节点
t 代表 then，即条件为 true 时对应的语句的 NODE 节点
e 代表 else，即条件为 false 时对应的语句的 NODE 节点

INSN

INSN 结构体用于描述一条 YARV 指令：

// compile.c

typedef struct iseq_insn_data {
    LINK_ELEMENT link;
    enum ruby_vminsn_type insn_id;
    unsigned int line_no;
    int operand_size;
    int sc_state;
    VALUE *operands;
} INSN;

link，用于将指令链接成双向链表
insn_id，指令类型
line_no，行号
operand_size，操作数个数
operands，操作数数组

创建 INSN

compile.c 定义了一些宏和函数用于创建 INSN，我们来看几个关键的宏定义

ADD_INSN

// compile.c

#define ADD_INSN(seq, line, insn) \
  ADD_ELEM((seq), (LINK_ELEMENT *) new_insn_body(iseq, (line), BIN(insn), 0))

#define ADD_INSN2(seq, line, insn, op1, op2) \
  ADD_ELEM((seq), (LINK_ELEMENT *) \
           new_insn_body(iseq, (line), BIN(insn), 2, (VALUE)(op1), (VALUE)(op2)))

#define ADD_INSN3(seq, line, insn, op1, op2, op3) \
  ADD_ELEM((seq), (LINK_ELEMENT *) \
           new_insn_body(iseq, (line), BIN(insn), 3, (VALUE)(op1), (VALUE)(op2), (VALUE)(op3)))

ADD_INSN2 和 ADD_INSN3 是 ADD_INSN 带操作数版本，我们先看看简单一点的 ADD_INSN

seq，LINK_ANCHOR 结构体，新建的 INSN 将被链接到 seq 末尾（last）
line，行号
insn，指令枚举值

BIN 宏定义在 insns.inc 中，用于将 iseq 转化为 ruby_viminsn_type 类型的枚举值
例如 BIN(nop) 会被展开成 YARVINSN_nop

#define BIN(n) YARVINSN_##n

enum ruby_vminsn_type {
    BIN(nop) = 0,
    ...
}

我们接着来看一下 new_insn_body 函数

如果指令字节码包含操作数，即 argc > 0，则调用 compile_data_alloc 在 iseq 中分配空间并初始化 operands
调用 new_insn_core 函数创建具体的 INSN
new_insn_core 函数调用 compile_data_alloc_insn 函数在 iseq 中分配空间并初始化 INSN

static INSN *
new_insn_body(rb_iseq_t *iseq, int line_no, enum ruby_vminsn_type insn_id, int argc, ...)
{
    VALUE *operands = 0;
    va_list argv;
    if (argc > 0) {
    int i;
    va_init_list(argv, argc);
    operands = (VALUE *)compile_data_alloc(iseq, sizeof(VALUE) * argc);
    for (i = 0; i < argc; i++) {
        VALUE v = va_arg(argv, VALUE);
        operands[i] = v;
    }
    va_end(argv);
    }
    return new_insn_core(iseq, line_no, insn_id, argc, operands);
}

static INSN *
new_insn_core(rb_iseq_t *iseq, int line_no,
          int insn_id, int argc, VALUE *argv)
{
    INSN *iobj = compile_data_alloc_insn(iseq);
    /* printf("insn_id: %d, line: %d\n", insn_id, line_no); */

    iobj->link.type = ISEQ_ELEMENT_INSN;
    iobj->link.next = 0;
    iobj->insn_id = insn_id;
    iobj->line_no = line_no;
    iobj->operands = argv;
    iobj->operand_size = argc;
    iobj->sc_state = 0;
    return iobj;
}

ADD_SEND_R

ADD_SEND_R 宏定义如下：

// compile.c

#define ADD_SEND_R(seq, line, id, argc, block, flag, keywords) \
  ADD_ELEM((seq), (LINK_ELEMENT *) new_insn_send(iseq, (line), (id), (VALUE)(argc), (block), (VALUE)(flag), (keywords)))

包含的参数比较多

seq，LINK_ANCHOR，新建的 SEND INSN 将被添加到 seq 末尾
line，行号
id，方法 id
argc，参数个数
block，block 参数
flag，标志位
keywords，关键字参数

rb_iseq_t

rb_iseq_t 是对 Ruby 虚拟机执行的指令序列的抽象，包含运行时信息 rb_iseq_constant_body 的引用，以及编译时信息 iseq_compile_data 的引用。虚拟机指令的生成和执行都围绕着 rb_iseq_t 结构体，可见其重要性

// iseq.h

#ifndef rb_iseq_t
typedef struct rb_iseq_struct rb_iseq_t;
#define rb_iseq_t rb_iseq_t
#endif

// vm_core.h

/* T_IMEMO/iseq */
/* typedef rb_iseq_t is in method.h */
struct rb_iseq_struct {
    VALUE flags;
    VALUE reserved1;
    struct rb_iseq_constant_body *body;

    union { /* 4, 5 words */
        struct iseq_compile_data *compile_data; /* used at compile time */

        struct {
            VALUE obj;
            int index;
        } loader;
    } aux;
};

创建 rb_iseq_t

rb_iseq_new_with_opt 函数创建以参数 node 为根的抽象语法树（AST）对应的 rb_iseq_t，或者按照《编译原理》的说法：根据 AST 生成中间代码（rb_iseq_t）

parent，父 rb_iseq_t，因此可以推断出 rb_iseq_t 被组织成层次结构
type，类型
option，构建选项

// iseq.c

rb_iseq_t * rb_iseq_new_with_opt(NODE *node, VALUE name, VALUE path, VALUE absolute_path,
             VALUE first_lineno, const rb_iseq_t *parent,
             enum iseq_type type, const rb_compile_option_t *option)
{
    /* TODO: argument check */
    rb_iseq_t *iseq = iseq_alloc();

    if (!option) option = &COMPILE_OPTION_DEFAULT;
    prepare_iseq_build(iseq, name, path, absolute_path, first_lineno, parent, type, option);

    rb_iseq_compile_node(iseq, node);
    cleanup_iseq_build(iseq);

    return iseq_translate(iseq);
}

iseq_imemo_alloc

该函数用于分配 rb_iseq_t 所需内存，里面调用的 iseq_imemo_alloc，ZALLOC 等函数涉及到 Ruby 内存管理，暂不展开

// iseq.c

static rb_iseq_t * iseq_alloc(void)
{
    rb_iseq_t *iseq = iseq_imemo_alloc();
    iseq->body = ZALLOC(struct rb_iseq_constant_body);
    return iseq;
}

prepare_iseq_build

prepare_iseq_build 函数为翻译 AST 做一些准备，这里仅列出和 rb_iseq_t 数据结构相关的一段的代码

static VALUE
prepare_iseq_build(rb_iseq_t *iseq,
           VALUE name, VALUE path, VALUE absolute_path, VALUE first_lineno,
           const rb_iseq_t *parent, enum iseq_type type,
           const rb_compile_option_t *option) {
    ...
    iseq->body->type = type;
    set_relation(iseq, parent);
    ...
}

set_relation 函数设置 iseq 的 parent

static void set_relation(rb_iseq_t *iseq, const rb_iseq_t *piseq)
{
    ...
    if (piseq) {
    iseq->body->parent_iseq = piseq;
    }
    ...
}

rb_iseq_compile_node

在经过了前面的准备工作之后，rb_iseq_compile_node 函数开始将 AST 翻译成 rb_iseq_t

VALUE rb_iseq_compile_node(rb_iseq_t *iseq, NODE *node) {
    // 初始化 LINK_ANCHOR，翻译过程中所有的指令（ISNS 结构体）都会被添加到 ret 里面
    DECL_ANCHOR(ret);
    INIT_ANCHOR(ret);

    if (node == 0) {
        // 代码块 1
    } else if (nd_type(node) == NODE_SCOPE) {
        // 代码块 2
    } else if (RB_TYPE_P((VALUE) node, T_IMEMO)) {
        // 代码块 3
    } else {
        // 代码块 4
    }

    // 优化并将 ret 从链式结构转换成线性（数组）结构存储在 iseq 中
    return iseq_setup(iseq, ret);
}

为了理清思路，对关键代码段进行了注释，并且标明了主要的 4 个分支逻辑

代码块1

代码块1 对应 AST 是一棵空树的情况，即没有 ruby 脚本需要转译，COMPILE 是一个宏定义，下文再详细介绍

if (node == 0) {
    COMPILE(ret, "nil", node);
    iseq_set_local_table(iseq, 0);
}

代码块2

代码端2 是通常会走到的逻辑，即翻译一个 block, method, class 或 top 作用域

else if (nd_type(node) == NODE_SCOPE) {
    /* iseq type of top, method, class, block */
    iseq_set_local_table(iseq, node->nd_tbl);
    iseq_set_arguments(iseq, ret, node->nd_args);

    switch (iseq->body->type) {
        case ISEQ_TYPE_BLOCK: {
            break;
        }
        case ISEQ_TYPE_CLASS: {
            break;
        }
        case ISEQ_TYPE_METHOD: {
            break;
        }
        default: {
        }
    }
}

代码块3

代码块4

语法分析链表 typedef element

Ruby 2.x 源代码学习：语法分析 & 中间代码生成 之 数据结构