shellの文字列分解と環境変数展開を再実装した

42tokyoの課題で、bashを模したシェルを製作しました。
shellに入力された文字列を分割するLexer,環境変数を展開するexpansionを担当したので、実装を行う際、気を付けたことを書きます。

Lexer

Lexerってなんだ

Lexerとは、shellに入力された文字列を、Parserが構文解析を行うToken単位に分割する機能のことです。
様々なオープンソースのアーキテクチャについて記述されているAOSAの3章に記されているshellのアーキテクチャを見るとすごくわかりやすいです。(日本語訳)

$echo hello world <- 入力値
↓
[echo] -> [hello] -> [world]　<- Lexerが処理した後

$ echo "hello world" > hello.txt ; cat hello.txt | grep hello
↓
[echo] -> ["hello world"] -> [>] -> [hello.txt] -> [;] -> [cat] -> [hello.txt] -> [|] -> [grep] -> [hello] 

入力された文字列が何を意味しているかは解釈せず、構文解析を容易に行うための下準備を行います。

実装方針

入力された文字列をLexerに通すと、双方向連結リストに分解されて吐き出されることを目標に実装しました。
連結リストの構造体はこんな感じ。

typedef struct s_token  t_token;
struct          s_token
{
    t_token         *next;
    t_token         *prev;
    t_token_type    type;
    char            *data;
};

dataの部分に分割した文字列を格納し、typeにはこのトークンが何を表しているのかをenumで保持しています。

入力された文字列を一文字づつ確認し、分割する必要のある文字が現れたら分割を行います。
分割する必要のある文字は、|や;などのshellが構文解析を行う際、特別な意味を持っている文字です。
空白も文字列の区切りとして判定できますが、その後の処理に必要ないので、分割する際に取り除いています。

(イメージ)
$ echo hello|cat;
↓
{"echo", Token}
↓
{"hello", Token}
↓
{"|", Pipe}
↓
{"cat", Token}
↓
{";", Semicolon}

保持しておくべき変数が多いので、親分構造体を操作して文字列の分解を行いました。

typedef struct  s_tokeniser{
    size_t          str_i;//入力値のindex
    size_t          tok_i;//token内の文字列のindex
    size_t          str_len;//入力値の長さ
    t_bool          esc_flag;//エスケープを行うか
    t_bool          is_quoted;//現在クオートの中にいるか
    t_token         *token;//現在操作しているトークン
    t_token         *tokens_start;//トークンリストの先頭
    t_token_state   state;//何のトークンであるか
    char            *quote_start; //クオートの開始地点
}               t_tokeniser;

クオートについて

shellの入力値は、クオートで囲むと、分割せず１つのトークンとして解釈されます。
そのため、ただ文字列を見ているだけでは、クオートで囲まれた;と通常の;を区別することができません。

例
$ echo "hello world ; echo hello" <- 分割しなくてよいセミコロン
hello world ; echo hello

$ echo hello world ; echo hello   <- 分割しなければならないセミコロン
hello world
hello

このようなパターンをうまく分割するため、文字列を処理する際、今見ている文字がクオートに囲まれている文字なのか、通常の文字なのかという状態を保持しておく必要があります。

また、クオートは、トークンを分割する区切り文字として処理していません。
環境変数展開、クオートの取り除きが行われると、クオートの周りの文字列は連結されるため、初めから連結されている状態で次の処理に渡した方が処理しやすいと思います。

$ export TEST="ch"
$ e"$TEST"o hello
hello

Expansion

expansionってなんだ

expansionは、shellに入力された文字列の中に含まれる、環境変数の展開を行う部分です。
こちらもAOSAがわかりやすいです。(日本語訳)

AOSAを参照してわかるように、expansionは環境変数展開を行うだけではなく、~,$"",*,{}といった要素の展開も行っています。

expansionがどのような処理を担っているのかは、gnuが公開しているbashのドキュメントが参考になります。(3.5章が変数展開について解説している部分です。)

今回は、$変数名の形式で指定される環境変数の展開のみ実装しました。

調査

環境変数の展開は様々なパターンが存在するので、実装を行う前に挙動を調べました。
下記のようなコマンドに気をつけながら実装を行いました。

$export TEST="ch"
+ export TEST=ch
+ TEST=ch
$ e"$TEST"o  hello
+ echo hello　　　<- クオート前後の文字列は連結される。
hello

export TEST="echo hello" 
+ export 'TEST=echo hello'
+ TEST='echo hello'
$ $TEST
+ echo hello　<-環境変数内の空白は分割される
hello

実装方針

expansionの基本動作は、与えられた文字列をすべてチェックし、$を見つけると環境変数展開を行います。

$が存在している位置によっては、環境変数展開を行わなくてよい可能性があるので、前後の文字や、クオートに気をつけながら$を探します。

シングルクオートの中に存在している$は変数展開をしなくてよいので、シングルクオートを見つけると、次にシングルクオートを見つけるまで$を無視します。

また、$がエスケープされている場合や、$の後に変数名以外の文字が存在しているときも変数展開されません。

展開されないパターン達

"$"USER
'$USER'
\$USER

echo $  <- 文字として認識される

echo $: <-$に続く文字が環境変数として指定できる文字ではない

クオートが含まれるの環境変数の展開について

展開される変数の内部にクオートが含まれていると、変数展開された文字としてのクオートなのか、文字列をグループ化するためのクオートなのか区別をつけることができません。

export TEST="\" hello \""
$ echo $TEST
" hello "

echo "$TEST"
↓
何も考えずに展開する

echo "" hello ""　<- クオートが閉じられているように見える。

そのため、エスケープが必要な文字が環境変数の中に含まれる際は、エスケープ用のバックスラッシュを追加して展開を行うよう実装しました。

export TEST="\" hello \""
$ echo $TEST
" hello "

echo "$TEST"
↓
エスケープようにバックスラッシュを追加し展開する

echo "\" hello \""　<-エスケープ処理を行うとクオートが文字として認識される。

バックスラッシュを追加して展開することで、エスケープ処理を行うと、クオートを自動的に文字として認識させることができました。

2度目の文字列分解(WordSplitting)について

AOSAの3.1に記載されている図を参照すると、
環境変数展開を行った後、execを行う前にWordSplittingという処理が挟まれています。
この処理が存在することにより、下記のコマンドが正しく実行されます。

$ export TEST="echo hello"
$ $TEST
hello

環境変数展開を行った後文字列分解の処理を実行すると簡単な気がしますが、下記のコマンドを見るとそうもいきません。

$ export TEST="hello";
$ export TEST="world"; echo $TEST
world

環境変数展開を先に行ってしまうと、$TESTがhelloに展開されてしまうので、アーキテクチャにそって、文字列分解→環境変数展開→文字列分解の手順で動作させています。

また、環境変数展開をおこなった後の文字列は、まだエスケープとクオートが残った状態になっているので、Wordsplittingと同時に処理しました。

エスケープ

shellに文字列を入力する際、バックスラッシュをつけることで、特別な意味を持った文字を、ただの文字列として処理させることができます。

二度目の文字列展開を行う際、バックスラッシュを見つけたときは、無条件で1文字先の文字をトークンに含めることで機能させました。

エスケープの仕様

無条件にすべてエスケープ
echo \"\$\`\\ \a\A\1\@
"$`\ aA1@

ダブルクオート内では特定の文字しかエスケープされない
$ echo "\"\$\`\\" "\a\A\1\@"
"$`\ \a\A\1\@

シングルクオート内ではエスケープは発生しない

echo '\"\$\`\\' '\a\A\1\@'
\"\$\`\\ \a\A\1\@

クオート取り除き

二度目の文字列分解を行う際、クオート取り除きを行っています。
文字列分解を行う過程で、現在のクオート状態を常に認識しているので、クオート状態が変化するタイミングで読み飛ばし、トークンに格納する文字列から取り除いています。

おわり

Bashのソースやman、アーキテクチャとにらめっこしながら実装することで、${}といった普段使わない機能や、展開の仕組みなど、bashについての理解を深めることができました。

shellの再実装をチームでともに開発したnafukaさんの記事では、今回記事にした部分以外の処理について詳しく書かれています。ぜひご覧ください。

コードは下記リポジトリで公開しています。