C言語系/「デーモン君のソース探検」読書メモ/08, test(1)

• [ Prev ]
• [ Next ]
• [ C言語系 ]

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

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

プログラム本体について

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

$ 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コマンドで使える評価パラメータの文法が定義されている。

/* 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で定義している。

enum token {
        EOI,
        FILRD,
        FILWR,
...
        BOR,
        LPAREN,
        RPAREN,
        OPERAND
};

続いてトークンの形式を表すenumが定義されている。

enum token_types {
        UNOP,
        BINOP,
        BUNOP,
        BBINOP,
        PAREN
};

そして演算子を表す構造体と、字句解析で使う実際の演算子(予約語)の定義。

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()の中を見てみる。

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() だけ見てお仕舞いとする。

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が読みやすい理由の一つになっている。

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

• [ Prev ]
• [ Next ]
• [ Up ]
• [ C言語系 ]