シェル実装の課題を完走した

42Tokyoで minishell という課題があり, 完走したので感想書きます.

minishellについて

minishellとはbashっぽいシェルをC言語で実装する課題.

実装する機能は以下の通り

• readlineを使った入力と履歴の実装.
• 絶対パス もしくは $PATH 環境変数を使った実行ファイルの実行 (/bin/ls や ls)
• ビルトインコマンド
  • echo (-nオプションのみ対応)
  • cd (相対か絶対パス)
  • pwd (オプションなし)
  • export (オプションなし)
  • unset (オプションなし)
  • env (オプションなし)
  • exit (オプションなし)
• シングルクオートとダブルクオート
• 入出力リダイレクション (<, >, >>) と heredocument (<<)
• パイプ (|)
• 環境変数 と $?
• ctrl-C(SIGINT), ctrl-\(SIGQUIT), ctrl-D(EOF)

っていう感じでbashっぽい小さなシェル(minishell)を作るという課題です.

この課題はチーム課題で, torusさん とチームを組んで取り組みました.

実装

実装したコードはここにあります.

github.com

動いている様子

gyazo.com

シェル全体の構成

全体を超大雑把に分けると以下のようなコンポーネントに分解できます.

1. 入力処理(readline): JUN
2. Lexer & Parser: torus
3. CommandExecution: JUN

JUNと書いてあるのが自分が主に担当した部分で, torusと書いてあるのがtorusさんが主に担当した部分です.

大まかな設計は The Architecture of Open Source Applications という本の中にあるbashの章の中のbashのコンポーネントのアーキテクチャ図を参考にしてコンポーネントを分け, その後それぞれに担当を決めました.

ここから先はこれらコンポーネントそれぞれについての説明を書くのですが, 自分が担当した部分に関しては詳細に書けるのですが, 自分が担当していない部分に関しては少し大雑把な説明になるかもしれないです.

入力処理

入力処理はreadlineを使って良いとのことなので, 使いました.

正直 readline が便利すぎてあまり入力処理について説明することは無いです. 強いて言うならシグナルハンドリングは少し気をつける必要がありますが, The GNU Readline Libraryを使ったを見ればなんとかなります.

実はこの入力処理についてはちょっとした小話があるのですが, それはまた後ほど...

Lexer & Parser

Lexer (字句解析)

Lexerとは字句解析機であり, 入力文字列を解釈し, 字句(ひとつの意味のある文字列単位)単位で取り出せるみたいな感じです. 字句はToken, 字句解析機はTokenizerとも呼ぶみたいです.

例えば入力が echo Hello I am "JUN" 'san' | cat なら以下のように取り出せるイメージです.

Token	Type
echo	EXPANDABLE
Hello	EXPANDABLE
am	EXPANDABLE
JUN	EXPANDABLE_QUOTED
san	NON_EXPANDABLE
|	PIPE
cat	EXPANDABLE

ja.wikipedia.org

Parser (構文解析)

Lexerで字句単位に文字列を取り出せるようになったのでここでは取り出した字句を元に構文解析を行い抽象構文木(AST)を作成します.

シェルが受け付ける文字列の文脈自由文法(課題に必要な部分のみ)は バッカス・ナウア記法(BNF) を用いて以下のように表される.

command_line ::=
      "\n"
    | sequencial_commands delimiter "\n"
    | sequencial_commands "\n"

delimiter ::=
      ";"

sequencial_commands ::=
      piped_commands delimiter sequencial_commands
    | piped_commands

piped_commands ::=
      command "|" piped_commands
    | command

command ::=
      arguments

arguments ::=
      redirection
    | redirection arguments
    | string
    | string arguments

string ::=
      expandable <no_space> string
    | expandable
    | not_expandable <no_space> string
    | not_expandable
    | expandable_quoted <no_space> string
    | expandable_quoted

redirection ::=
      "<" string
    | ">" string
    | ">>" string
    | "<<" string

この文法に基づいて再帰下降構文解析を行いASTを生成する.

abc def | file < infile ; xyz ; のパース結果

CommandExecution

Lexer, Parser の処理が完了し, ASTが生成できたら今度はそれを元に実際にリダイレクションの処理やコマンドの実行などを行います.

今回は "Lexer & Parser" と "CommandExecution" を完全に分けて実装したので, ASTをそのまま使って実行するのではなくCommandExecution側で受け取りたい構造体(t_command_invocation)というのを予め定義しておき, ASTとt_command_invocationを変換する関数を最終的に作ることによって同時並行でそれぞれの担当箇所を実装できると共に, どちらか一方に変更があっても変換関数を修正すれば良いだけになります.

t_command_invocation は具体的には以下のような構造体です.

typedef struct s_command_invocation
{
    t_cmd_redirection           *output_redirections;
    struct s_command_invocation    *piped_command;
    t_cmd_redirection           *input_redirections;
    const char                    **exec_and_args;
    pid_t                       pid;
}   t_command_invocation;

• t_cmd_redirection はリダイレクションに関する情報を持つ片方向連結リストの構造体です. 具体的には以下の情報を持っています.

  • ファイルパス (heredocの場合は入力された文字列)
  • リダイレクションの種類(追記かどうか, heredocかどうかなど)
  • リダイレクションで指定されたファイルディスクリプタ
  • 次のリダイレクションへのポインタ

• piped_command はパイプの次のコマンドへのポインタです.

• exec_and_args は実行するプログラムに渡す文字列配列です. int main(int argc, char **argv) と書いたら受け取れる argv の部分です.

• pid はコマンド(プログラム)が子プロセスで実行された時のプロセスIDです. fork() して作成した子プロセスを wait() して終了ステータスを取得するために使います. あと, fork()して作成した子プロセスを正しくwait()してあげないとゾンビプロセスになってしまうのでこれを避けるためにも子プロセスのpidは必要です.

リダイレクションの処理

リダイレクションの処理は基本的には dup2() などを使って標準入出力のfd(2>や3<みたいなfd指定の場合は指定のfd)をファイルのfdに置き換えれば出来ます.

気をつけるべき点としては, bashでは複数リダイレクションが存在する時, そのfdのリダイレクションの中で最後リダイレクションのみが書き込みや読み込みが行われることです.

bash で echo hello > file1 > file2 > file3 と実行するとfile1とfile2はファイルは作成されるが, 何も書き込まれておらず, file3にのみ"hello"が書き込まれています. ちなみにzshの場合だと全てのファイルに"hello" が書き込まれるという違いがあります.

入力の場合も同様で, cat < file1 < file2 の場合, 実際にcatコマンドの標準入力に繋がれるのは file2 のみです.

heredocument

heredocument はbash特有の概念ではなく, いろんな言語に実装されている.

en.wikipedia.org

要は複数行文字列リテラルということみたいです. bashにおいては << と区切り文字の組み合わせで始まり, もう一度区切り文字が出現するまでの文字列をコマンドの標準入力に流し込むというものになっています.

heredocumentの例

複数heredocumentの例

パイプとheredocumentを組み合わせた例

まぁ大体雰囲気はこんな感じです.

で, 実装の方なんですが, heredocumentの入力タイミングはParserの後, ASTをt_command_invocationに変換する関数内で行うようにしました. つまり, cat << EOF はparserが処理して, そこから先入力される文字列はParserではなくCommandExecution側で入力を受け付けて, 入力された文字列を構造体のメンバに保存します.

fd周りについてですが, ファイルのリダイレクションだとopen()すればよいのですが, heredocument はファイルを入力としているわけではないので, リダイレクションとは分けて考えるべきです.

しかし, 最初どういう風に実装されているか全然わからなかったのでbashのソースコードを見に行きました. そうするとどうやら親プロセスから子プロセスに対してheredocument用のpipeを繋いで文字列を渡しているようです.

先程紹介した "パイプとheredocumentを組み合わせた例" を例に図にすると以下のような感じです.

パイプラインのコマンド間のパイプ以外にも, シェルのプロセスと子プロセス間のheredocument用のパイプを作成し, そのpipeに対してheredocumentで入力された文字列をwrite()することで実現出来ます.

プログラムの実行

今回自分はシェルのパイプラインの実装はループで子プロセスを生成していくやり方にしました. echo hello | wc -l | cat を例として考えると以下の様になります.

シェルのパイプライン処理の実装方法はいくつかあるのですが, 複数コマンドが同時に動くという点(並列実行)に気をつけましょう.

例えば bash で cat | ls とすると, catの実行が完了する前にlsの出力が先に出現します. これはcatの実行が完了してからlsを実行する逐次的な実行ではなく, cat と ls を並列に実行させているからです.

`cat` と `ls`が同時に実行され `cat` が入力待ちになっている

ビルトインコマンド

ビルトインコマンドというのはシェル側で実装してシェルに組み込まれているコマンドです.

ビルトインコマンドの実装自体は基本的にはbashのビルトインコマンドのヘルプとかを読みながら関数として実装すれば良いです.

で, 問題となるのはコマンドそのものというよりかはビルトインコマンドの実行方法です. ビルトインコマンドは外部のプログラムを呼び出すわけではないので execvp() などはしません.

ビルトインコマンドは単体で実行される場合とパイプラインとして実行される場合で実行方法が異なります.

ビルトインコマンド単体で実行される場合はfork()せずにシェルのプロセス上で対象の関数を呼び出します.

その際にリダイレクションが含まれている場合は標準入出力をdup() などを使って保存しておき, 後に復元する必要があります. こうしないとその後標準入出力が使えなくなります.

例えば echo hello > output.txtが入力された時, もしechoが外部コマンドならSTDOUT_FILENOをopen("output.txt", O_WRONLY | O_CREAT)で出力先ファイルのfdを使ってdup2(fd, STDOUT_FILENO) のように置き換えれば良いだけです. なぜなら外部コマンドを実行しているプロセスはシェルのプロセスではなく, シェルのプロセスからfork()された子プロセスであり, 子プロセスのfdがどうなろうと親プロセスには影響しないからです.

しかし, シェルのプロセスで実行するビルトインコマンドは話が違います. そのまま愚直にdup2(fd, STDOUT_FILENO)などとしようものなら標準出力はcloseされ, その後シェルが標準出力に書き込む手段が無くなります. なのでこのような悲惨な事態を避けるために dup(STDOUT_FILENO) のようにリダイレクション用のfdとは別に標準入出力のfdを複製して保持しておきます. そしてリダイレクションの処理を行っている時に複製した標準入出力のfdとリダイレクションで指定されたfd(2> みたいなやつ)が被ったらもう一度dup(複製した標準入出力のfd)をしてからファイルのfdに置き換えることで標準入出力のfdを失わないようにしながらリダイレクションを処理する必要があります.

そしてリダイレクションなどの処理が終わり, ビルトインコマンド関数の実行が完了したらリダイレクション用に開けていたfdを閉じて, 標準入出力のfdを元のfdに戻して完了です.

このようにビルトインコマンド単体の場合はシェルと同じプロセスで実行されるためリダイレクション周りなどは注意を払う必要が有ります.

次にパイプラインの中にビルトインコマンドがある場合, 例えば echo hello | cat のような場合です.

この場合, 外部コマンドを実行する時と同じ様にfork()して子プロセスを生成します. 違いはexecvp()で外部のプログラムを読み込んでメモリを別のプログラムに置き換えることはせず, ビルトインコマンドに対応した関数を呼び出して終了する点です.

ここまでの話で説明したとおりビルトインコマンドは単体の場合はシェルのプロセスで, パイプライン内の場合はシェルの子プロセスで実行されます. そして子プロセスの環境変数やfdの変更, メモリの操作, カレントディレクトリの変更 は親プロセスに影響しません.つまりどういうことが起きるかというと, 以下のようなことが起きます.

bashでの実行例

パイプライン内で export した環境変数が反映されていませんね. これは export は環境変数を追加したけれど, コマンドがパイプライン内にあるのでexportは子プロセスで実行され, 親プロセスであるシェルのプロセス内の環境変数には反映されていないのです.

cdでも同様にパイプライン内で実行するとシステムコールchdir()が子プロセス内で実行されるためシェルのcwdは変わりません.

bashでの実行例

こういうのを知るとなぜ export や unset, cdなどがビルトインコマンドとしてシェルに組み込まれているかがわかりますね.

その他

環境変数の保持方法

初めのころは, 環境変数は文字列配列environをそのまま保持していて, 環境変数を追加する時は文字列配列のメモリ領域を確保し直し(課題の制約でrealloc()は使えないので), environにもともと入っていたデータを新しい配列にコピーしその後最後の要素に新しい環境変数の文字列("key=value"形式)を入れるようにしていました.

しかし, この方法はおすすめできません. なぜなら環境変数の取得や追加, 削除などの操作に多くの手間が必要になりバグの原因になりますし拡張性が低いです. なので良い子は連結リストやハッシュテーブルなどの扱いやすいデータ構造で環境変数を保持しておき, コマンドを実行する時に文字列配列に変換する関数を作りましょう.

今回自分は連結リストで環境変数を保持するようにしました. 速度ガー! って思うかもしれませんが, 環境変数の数なんて大して大きくなることは無いはずなので問題ないと判断しました. (問題が起きそうなら別のデータ構造に変えればいいだけ)

typedef struct s_var {
    const char            *key;
    const char            *value;
    bool               is_shell_var;
    struct s_var       *next;
}                       t_var;

入力処理に関しての小話

入力処理に関してはreadlineを使ったから苦労してない的なことを書きましたが, 実は自分のチームが課題を始めたころはreadlineは使えずTermcapを使って実装する必要がありました. (Termcapの部分はtorusさんがやってくれました)

en.wikipedia.org

このtermcapがかなり曲者のようでして, 入力処理の実装はかなり苦労していました. しかし, 自分達が課題を提出直前に課題変更があり, readlineが使えるようになりTermcapを使う必要が無くなったのと, 課題要件にheredocの追加が行われ, 話し合った結果Termcapによる入力処理の実装は破棄し, readlineによる入力処理を実装することにしました.

課題変更前はTermcapによる入力処理と履歴機能と文字列編集の実装のためにロープ木)による文字列編集が実装されていました.

GitHub - torus/42-minishell at termcapありのバージョン からTermcapを使ったバージョンのコードが見れます. (heredocumentは実装されていません)

豆知識

ここではminishellをやる上で役に立つかもしれない豆知識を書いておきます. (自分用の備忘録でもある)

bashのコードリーディング

bashのコードは1996年頃に書かれていて, 現代のC言語のコードとは書き方が一部異なっており, それを知らないととても読みづらいです.

具体的には

• インデントのサイズはスペース8
• 古いC言語の規格では引数の型は関数ヘッダーの次の行に書く必要がある.

en.wikipedia.org

この書き方をK&Rスタイルと言うらしいです.

なのでbashのコードを読む時はエディタのインデントサイズを8にして, 古いC言語の書き方を頭の片隅に置いておくとスムーズにコードが読めると思います.

GNUフラグパーサー

echo -n -n hello や echo -nnnn hello と書いた時に echo -n hello と同じ挙動をするのはGNUのフラグパーサーライブラリであるgetoptの仕様によるものである.

en.wikipedia.org

www.gnu.org

完走した感想

いやー, 長かった. 4月に課題に取り組み始めてから提出するまで約3ヶ月かかりました. まぁ3ヶ月の間全てminishellやっていたというわけではなく競プロやったりフラクタルの実装したりちょくちょく寄り道したりしてましたが, それでも大変でした.

コミット数も42の課題では初めて1000コミット超えました. まぁPRやrevertなどのコミットがいっぱい入っているので全てのコミットがコードの実装を含んでいるというわけでもないですが.

この課題をするまでシェルというものが自分で実装できるものというイメージは全くありませんでしたが, 今回実装してみてシェルの内部での処理やUNIXプログラミングについて少し詳しくなり, シェルくらい頑張れば実装できるっしょっていう気持ちになりました.

また, 今回シェルを作ったことでこの課題に取り組む前と後でシェルに対する意識が大きく変わったように思えます. 課題に取り組む前は, シェルはブラックボックスって感じで, とりあえずなんか知らんけどコマンドを入力したら実行してくれるって感じでしたが, 今では内部でどのような処理が行われているかがわかっているためシェルを触っている時にシェルの実装側からの視点というものがわかるようになった気がします.

この記事ではあまり深堀りしてませんでしたが, cdを含むいくつかのビルトインコマンドはbashのhelpコマンドでは出てこない挙動などがあり, それを知るためにbashのソースコードを読んだりもしました. コミットが25年前(1996年)とかが普通にあり, 自分より年上のコードを読むのは新鮮でした. 25年前ともなると現在のC言語の文法やインデントスタイルなどが違っていたりして読むのが大変でした.

今回始めてUNIXプログラミングと呼ばれるものを行っったのですが,「詳解UNIXプログラミング」という本がとてもとても役に立ちました.

詳解UNIXプログラミング 第3版

UNIXとはなんぞやという説明からUNIXにおけるファイルの扱い, シグナルやプロセス等々...UNIXプログラミングを行う上で必要な知識がここに書かれています. この本のおかげでminishellなんとかクリア出来たと言っても過言では無いくらいに役に立ちました. (自分の中では勝手に聖書と呼んでいます)

また, 今回一緒にチームを組んだtorusさんはキャリアの長いプログラマーの方で, 多くのことを教えて頂き大変勉強になりました. 豆知識のセクションに書いてある知識はtorusさんから教えてもらったものだったりします.

あと, 提出する直前で課題が大幅に変更されたのは堪えました. 特にtorusさんはその時点で既にTermcapに関わる入出力関係のコードを数週間掛けて千行以上書いていました. しかし, Termcapでの入出力をheredocに対応させる(複数行入力対応)こととreadlineの実装に切り替えるという2つの選択肢を考えた時に, ここまで書いてきた千行以上のコードを破棄し, readlineでの実装に舵を切ったのは凄いなぁと思いました. もし自分だったら惜しくて既存のコードに固執してしまうかもしれません.

Termcapの削除に関するPR

github.com

今回の課題は今までの課題で一番重く, 実装量も多いため記事内で全てを解説しませんでした. 具体的なコードが見たい人はGitHubのリポジトリを見てください.

github.com

とても大変でしたが, やりがいと学びのある良い課題でした.

といったところで今日はこのへんで. ではでは〜〜👋👋

参考リンク

bash関係

• Shell & Utilities: Detailed Toc -- The Open Group Base Specifications
• GNU公式 Bash Reference Manual
• Shell Command Language
• Chapter 19. Here Documents

シェル関係

• bash再実装の課題振り返り - Nafuka Lines
• Unix Pipes (ohio-state edu)
• 入門 シェル実装
• システムプログラム（2020年度第4回） プロセスについて 筑波coins
• UNIXシェル：コマンドラインの解釈とパイプラインの設計 notion
• Writing a Unix Shell - Part I

パーサー関係

• 参照カウント - Wikipedia
• Cコンパイラ作成入門 - 文法の記述方法と再帰下降構文解析
• 再帰下降構文解析 - Wikipedia

readline

• The GNU Readline Libraryを使った - メモの日々(2008-03-19)
• GNU Readline Library - Programming with GNU Readline

Termcap

• Termcap - Wikipedia
• The Termcap Library
• Splay tree - Wikipedia
• Rope (data structure) - Wikipedia

その他

• 42_minishell_tester
• Indentation style - Wikipedia
• GNU Readline Library:
• getopt - Wikipedia
• Linux におけるファイル I/O の基礎 - itkq.jp