SQLite コードジェネレート箇所を探した

Posted on One min read

sqlite3_prepare_v2()でプリペアドステートメント(バイトコード)が生成されている。 バイトコードの生成過程を調べた。

tl;dr

振り返ると普通のコード生成だった。

  • プリペアドステートメントはsqlite3_prepare_v2 で生成される
  • パースはLALR(1)構文解析器が利用される
  • 構文解析器ジェネレーターはLemonを用いている
  • 構文解析は sqlite3Parser にトークンを渡す形で実行される
  • cmd 非終端記号の還元時にバイトコードは生成される
  • 他の非終端記号の還元時は中間情報をノードに格納する
  • OpCodeはBTreeを操作する命令になっている

詳細

sqlite3_prepare_v2

sqlite3_prepare_v2はsqlite3Prepare(in prepare.c)を呼びプリペアドステートメントを取得する。 その中ではsqlite3RunParser(in token.c)を通して構文解析器が呼ばれている。

sqlite3Prepareは大雑把に以下の様な流れでバイトコード格納場所(sqlite3_stmt* ppStmt)へ作成されたバイトコード(pParse->pVdbe)を代入している。 EXPLAIN用の処理はバイトコードを表示しているのでsqlite3RunParserの中でバイトコード生成をしている事が予想される。

1
2
3
4
5
6

## いろいろな事前処理
sqlite3RunParser(pParse, zSql, &zErrMsg);
#ifdef SQLITE_OMIT_EXPLAIN
# ... なんかEXPLAINっぽい事
#endif
*ppStmt = (sqlite3_stmt*)pParse->pVdbe;

sqlite3RunParser

sqlite3RunParser は構文解析器を駆動する。

lemenパーサジェネレータで生成されているのでサンプルと基本的な流れは同じ。 sqlite3GetTokenでトークンを取得しsqlite3Parser(in parse.c, sqliteInt.h)に渡している。

気になった事は

  • 最後に 0 でParserを呼び出す理由がわからない
  • パーサーに任さずにToken種別で分岐する理由がわからない
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

pEngine = sqlite3ParserAlloc(...)
while( !db->mallocFailed && zSql[i]!=0 ) {
    pParse->sLastToken.z = &zSql[i];
    pParse->sLastToken.n = sqlite3GetToken((unsigned char*)&zSql[i],&tokenType);
    switch (tokenType) {
    default:
        sqlite3Parser(pEngine, tokenType, pParse->sLastToken, pParse)
    }
}
if( lastTokenParsed!=TK_SEMI ){
    sqlite3Parser(pEngine, TK_SEMI, pParse->sLastToken, pParse);
    pParse->zTail = &zSql[i];
} else {
    sqlite3Parser(pEngine, 0, pParse->sLastToken, pParse);
}
sqlite3ParserFree(pEngine, sqlite3_free);

sqlite3GetTokenは典型的な字句解析器で特に変わったところはない。

sqlite3ParserはLR系のためシフト・還元の繰返しで実装されている。 yy_find_shift_action()で状態マシンが次に取るアクションナンバーが返却される。 アクションナンバーによりシフト(yy_shift)・還元(yy_reduce)を行う。

バイトコード生成箇所

yy_reduceでcmdに還元する際にアクションとしてバイトコードが生成される。 バイトコード生成関数はpVdbeを操作する事でコードを格納している。 この様な関数はbuild.c,select.cといったソース内に記述されている。 cmd以外の還元アクションで中間情報を記録している。parse.yでコード生成は理解できる。

  • ASTの各ノードは種別ごとに別の型を使う
  • cmd の還元時にコード生成を行う
  • 他の非終端記号の還元時には親ノードで利用する情報をノードに格納する

例えば、SQL関数の実行に関係しそうな部分(状態番号196, 197)では、 sqlite3ExprFunctionが呼ばれてpExprに値が格納されたりしている。 OpCodeはBTreeを操作する命令で構成されている。 BTreeのインタフェースを確認してEXPLAINを使えば概要を掴める。

具体例) SELECT 文の場合

1
2
3
4
5

{
    SelectDest dest = {SRT_Output, 0, 0, 0, 0, 0};
    sqlite3Select(pParse, yymsp[0].minor.yy3, &dest);
    sqlite3SelectDelete(pParse->db, yymsp[0].minor.yy3);
}