データ構造・リスト

構文木は、いったんYARV命令の連結リストに変換されます。その状態で最適化をやって、最後にもう一段、命令語の配列への変換処理が入ります。たぶん、最適化で命令の削除・挿入・並べ替えをよくやるので、全部配列でやるよりもリストにした方が効率がよいという理由だと思います。

それはともかくリストのデータ構造です。

typedef struct iseq_link_element {
    int type;
    struct iseq_link_element *next;
    struct iseq_link_element *prev;
} LINK_ELEMENT;

nextとprevへのポインタがある、よくあるリスト構造ですね。リストに繋ぎたいデータは、このLINK_ELEMENTデータをメモリの先頭に持ちます。そしてtypeメンバにデータの種類を入れます。例えばINSNというデータ構造(すぐ下で解説してます)はLINK_ELEMENTを先頭に持っているので

 +-------------------+
 | LINK | link.type  |
 | _ELE | link.next  |
 | MENT | link.prev  |
 +------+------------+
 | insn_id           |
 | line_no           |
 | ...               |
 +-------------------+

こういうメモリレイアウトになってて、リストを操作したい人が INST* を LINK_ELEMENT* と思って操作できちゃいます。INSTとして操作したいひとは、typeがISEQ_ELEMENT_INSNであることを確認して、INST*にキャストすればOK。INSTクラスがLINK_ELEMENTクラスを継承してるみたいなイメージでもいいかもしれません。

リストに入れるデータは２種類あって、一つめは、YARVの「命令」１個１個です。

#define ISEQ_ELEMENT_INSN  INT2FIX(0x02)
typedef struct iseq_insn_data {
    LINK_ELEMENT link;
    int insn_id;
    int line_no;
    int operand_size;
    int sc_state;
    VALUE *operands;
} INSN;

もう一つは、ジャンプ命令の飛び先などを表す「ラベル」です。

#define ISEQ_ELEMENT_LABEL INT2FIX(0x01)
typedef struct iseq_label_data {
    LINK_ELEMENT link;
    int label_no;
    int position;
    int sc_state;
    int set;
    int sp;
} LABEL;

この「ラベル」と「命令」の混じったリストがYARV中間データ構造として使われているわけです。

あ、ソースコードではもう一つ

#define ISEQ_ELEMENT_SEQ   INT2FIX(0x03)

というtypeも宣言されてましたが、使われている箇所が見あたりませんでした。

さて、LINK_ELEMENTは、リンクの個々の要素を指しています。これにプラスして、「リスト全体」を指すLINK_ANCHORというのも用意されています。

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

メンバ変数lastは、その名の通り、指しているリストの最後のLINK_ELEMENTを指します。これを操作すれば「リストの最後に要素を付け加える」みたいな処理が簡単に実現できてます。ADD_ELEMが、まさにそれをする関数です。

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

anchor->lastのうしろにelemを繋いで、その繋いだelemをanchor->lastで指すようにしてます。引数elemには、他のリストに繋がってない新しく作ったELEMENTを渡して使うっぽいです。

LINK_ANCHORのもう一つのメンバanchorはなんでしょう？これは、リストの先頭というか、lastの初期値というか、そういうものになります。つまりどういうことかというと、新しく空のリストを作るときは、こういう風に宣言するのです。

LINK_ANCHOR newList = {{0,0,0}, &newList.anchor};
 // {0,0,0} : どこにも繋がってないダミーをnewList.anchorとする
 // lastはそのnewList.anchorを指すポインタにしておく

空リストは last==NULL で表現、という方法もありますが、それと比べると、ダミーのanchorを使った方が、ADD_ELEM でNULL判定無しにいきなり anchor->last->next と書けたりして簡単です。あと、リストの先頭要素が
anchor.nextと一発で取れたりしてさらに便利。
ちなみに、空リストの宣言をするコードもマクロ化されています。

#define DECL_ANCHOR(name) \
 LINK_ANCHOR  name##_body__ = {{0,}, &name##_body__.anchor}; \
 LINK_ANCHOR *name = & name##_body__

他にも一連のリスト操作関数が定義されています。実装はふつうなので省略して、名前だけメモしときます。

// LINK_ELEMENTを引数にとる関数
INSERT_ELEM_PREV(elem1, elem2) /* elemX, elem1 =>
                                   elemX, elem2, elem1 */
REPLACE_ELEM(elem1, elem2) /* elemX, elem1, elemY =>
                                elemX, elem2, elemY */
REMOVE_ELEM(elem) /* elemX, elem, elemY =>
                       elemX, elemY */

// LINK_ANCHORを引数にとる関数
FIRST_ELEMENT
POP_ELEMENT
SHIFT_ELEMENT
LIST_SIZE
LIST_SIZE_ZERO
APPEND_LIST