#navi_header|C言語系|

お題："test"コマンドの中身を追跡せよ。

シェルスクリプトで良く使われる"test"コマンド(="["コマンド)の仕組みを調べてみる。
※なお、今回はBNF(バッカス・ナウア記法)や字句解析・構文解析などをある程度既知のものとして、駆け足で通していきます。
これら前提とする知識については、「デーモン君のソース探検」を参照するなり、専門書(コンパイラ関係)やWikipediaなどを参照して下さい。

#more||

----

* プログラム本体について

プログラム本体について調べてみる。

 $ which test
 /bin/test
 $ which [
 /bin/[
 $ ls -l /bin/test /bin/[
 -r-xr-xr-x  2 root  wheel  48648 Sep  9  2002 /bin/[*
 -r-xr-xr-x  2 root  wheel  48648 Sep  9  2002 /bin/test*
リンク数が2になっていることから、ハードリンクであることが予想される。i-node数を表示させてみる。
 $ ls -i /bin/[ /bin/test
 92192 /bin/[*
 92192 /bin/test*
同じ、よってハードリンクであることが判明した。

なおmanについては、以下で参照出来る。
 man 1 test
or
 man 1 [

ソースコードの場所を調べる。
 $ locate test
 (... 長すぎるのでもう少し絞ってみる ...)
 $ locate test.c
 ...
 /usr/src/bin/test/test.c
 ...

* test.cの解析(BNFやトークン識別子の定義など)

ソースコードの位置が判明したので、ソースの解析に進む。

まず冒頭からいきなりBNF(バッカス・ナウア記法)でtestコマンドで使える評価パラメータの文法が定義されている。
#pre||>
/* test(1) accepts the following grammar:
        oexpr   ::= aexpr | aexpr "-o" oexpr ;
        aexpr   ::= nexpr | nexpr "-a" aexpr ;
        nexpr   ::= primary | "!" primary
        primary ::= unary-operator operand
                | operand binary-operator operand
                | operand
                | "(" oexpr ")"
                ;
        unary-operator ::= "-r"|"-w"|"-x"|"-f"|"-d"|"-c"|"-b"|"-p"|
                "-u"|"-g"|"-k"|"-s"|"-t"|"-z"|"-n"|"-o"|"-O"|"-G"|"-L"|"-S";

        binary-operator ::= "="|"!="|"-eq"|"-ne"|"-ge"|"-gt"|"-le"|"-lt"|
                        "-nt"|"-ot"|"-ef";
        operand ::= <any legal UNIX file name>
*/
||<
トップダウンでつなげれば、
 oexpr -> aexpr -> nexpr -> primary
の順になり、primaryは次の4種類に分類される。
 1. "unary"形式 : "-r ファイル名" など、一つの値について評価する形式
 2. "binary"形式 : "値1 -eq 値2" など、二つの値を比較して評価する形式
 3. "operand"形式 : "値" だけの形式(値の文字列長が0以上なら真)
 4. "(" + ... + ")"形式 : 括弧でくくった中を優先評価する形式

このBNFに続き、字句解析で使うトークンの識別番号をenumで定義している。
#pre||>
enum token {
        EOI,
        FILRD,
        FILWR,
...
        BOR,
        LPAREN,
        RPAREN,
        OPERAND
};
||<
続いてトークンの形式を表すenumが定義されている。
#pre||>
enum token_types {
        UNOP,
        BINOP,
        BUNOP,
        BBINOP,
        PAREN
};
||<
そして演算子を表す構造体と、字句解析で使う実際の演算子(予約語)の定義。
#pre||>
static struct t_op {
        const char *op_text;
        short op_num, op_type;
} const ops [] = {
        {"-r",  FILRD,  UNOP},
        {"-w",  FILWR,  UNOP},
...
        {"-a",  BAND,   BBINOP},
        {"-o",  BOR,    BBINOP},
        {"(",   LPAREN, PAREN},
        {")",   RPAREN, PAREN},
        {0,     0,      0}
};
||<
宣言・定義の締めくくりはファイル内グローバル変数の定義：
 static char **t_wp;
 static struct t_op const *t_wp_op;
"t_wp"は文字列ポインタへのポインタ。"t_wp_op"は上で配列で定義された"ops"の内、現在処理中の演算子を表すポインタになっている。
その後main()まではプロトタイプ宣言が続くが、省略する。

* test.cの解析(main()関数とBNFに対応する関数の流れ)

main()関数は短く書かれている。まず戻り値用のint型変数が宣言される。
 int res;
続いて"["として起動された場合は対になる"]"がargvの最後にあるかチェックする。
 setprogname(argv[0]);
 if (strcmp(argv[0], "[") == 0) {
     if (strcmp(argv[--argc], "]"))
         error("missing ]");
     argv[argc] = NULL;
 }
"t_wp"をargv[1]へのポインタ、つまり評価用パラメータの最初の1個を指すように初期化する。
 t_wp = &argv[1];
ex:
 $ test abc -o def
 → "t_wp" は "abc" へのポインタに初期化される
そしてBNFでの一番の根本、"oexpr"の分析に進む。
 res = !oexpr(t_lex(*t_wp));

"t_lex()"関数はひとまず置いておいて、oexpr()の中を見てみる。
#pre||>
static int
oexpr(enum token n)
{
        int res;

        res = aexpr(n);
        if (t_lex(*++t_wp) == BOR)
                return oexpr(t_lex(*++t_wp)) || res;
        t_wp--;
        return res;
}
||<
BNFと重ねてみると、
 oexpr   ::= aexpr | aexpr "-o" oexpr ;
 =
 oexpr   ::= aexpr | 
             aexpr "-o" oexpr ;
で、
 res = aexpr(n);
の部分が
 oexpr   ::= aexpr | 
に当たり、続く
 if (t_lex(*++t_wp) == BOR)
     return oexpr(t_lex(*++t_wp)) || res;
がBNFで後半の
 aexpr "-o" oexpr ;
の処理に相当している。

この流れでBNFの通りに進んでいく。
 oexpr() → aexpr() → nexpr() → { primary() | binop() | filestat() }
primary()/binop()/filstat()まで進めば、あとはそれぞれの評価が戻り値として返され、逆方向に伝播してmain()の
 res = !oexpr(t_lex(*t_wp));
まで戻ってくる仕掛けになっている。

それぞれの関数の詳細まではここには載せない。冒頭でも書いたとおり字句解析・構文解析の知識があれば読みこなせる作りになっていると思うし、このメモ書きで特に書き留めておくようなトリッキーな処理は使われていない。

* test.cの解析(t_lex()関数)

最後に t_lex() だけ見てお仕舞いとする。
#pre||>
static enum token
t_lex(char *s)
{
        struct t_op const *op;

        op = ops;

        if (s == 0) {
                t_wp_op = (struct t_op *)0;
                return EOI;
        }
        while (op->op_text) {
                if (strcmp(s, op->op_text) == 0) {
                        if ((op->op_type == UNOP && isoperand()) ||
                            (op->op_num == LPAREN && *(t_wp+1) == 0))
                                break;
                        t_wp_op = op;
                        return op->op_num;
                }
                op++;
        }
        t_wp_op = (struct t_op *)0;
        return OPERAND;
}
||<
かなりシンプルな作りになっている。test.cは字句解析を行うにもかかわらず、比較的簡単で読みやすいソースになっている。
これは、コマンドライン引数が argv という形で、空白文字で分割済の状態で取り出せるおかげだと思われる。
このお陰でt_lex()も大幅に簡素化されている。t_lex()はトークンの識別番号を返すが、
 struct t_op const *op;
 op = ops;
これでまず定義済の演算子トークンの先頭でループ用の変数を初期化し、続くwhileループで現在処理中の文字列が"-r"や"-ne"などの演算子にマッチする場合はそのトークン番号を返す。
whileループをまわりきってしまい、最後の
 } const ops [] = {
 ...
         {0,     0,      0}
 };
まで到達した場合は、primary()での処理用に
 t_wp_op = (struct t_op *)0;
 return OPERAND;
とする。

なお "t_wp" が "argv[1]" で初期化されているお陰で、「次のトークンに進む」が
 ++t_wp
と書ける。また「一つ先のトークン」(=トークンの先読み)も
 t_wp[1]
と書くことができ、これもtest.cが読みやすい理由の一つになっている。

今回のお題については、ここまで。

#navi_footer|C言語系|