C 言語で minishell (bash 再実装) を作りました
42Tokyo(以下 42) というエンジニア養成機関に入学して早 10ヶ月…ブログを頻繁に更新してる方すごいです。
前回は課題 1 ~ 4 (rank0, rank1) までの振り返り (こちら) を書きました。
その後 2023.5 月に rank2 の課題 5 ~ 7 が終わり、最近は 42 で初めてのチーム課題であり前半の 1 つの山場でもある rank3 の課題 8 (minishell) が約 2 ヶ月半かかって一旦終わったのでその辺りの振り返りをサラッと書いておこうと思います。
- rank2 / 課題 5 ~ 7 (FdF, minitalk, push swap)
- 課題 5 (FdF)
- 課題 6 (minitalk)
- 課題 7 (push swap)
- rank3 / 課題 8 (minishell)
- 課題 8 (minishell)
ついでに書きそびれていた課題 5 ~ 7 についても振り返り。
rank2 / 課題 5 ~ 7 (FdF, minitalk, push swap)
所要時間
ざっくり各課題の(あまり当てにならない)推定所要時間と私が雑に計測している所要時間です。
推定所要時間 | 実際の所要時間 | |
---|---|---|
課題 5 (FdF) | 60 時間 | 56 時間 + 1~2 時間位のレビュー 3回 |
課題 6 (minitalk) | 50 時間 | 44 時間 + 1~2 時間位のレビュー 3回 |
課題 7 (push swap) | 60 時間 | 143 時間 + 1~2 時間位のレビュー 4回 |
課題 5 (FdF)
概要
C 言語で使用可能関数に制限あり。
このような標高 map を受け取り
このように点を繋げて線分にし、 3D 風に表示する
ついでにキー操作やマウス操作で 拡大縮小・上下左右移動・xyz 軸方向に回転・高さ変更・グラデーションで色付け などを追加。
感想
42 に入ってから初めて結構楽しくてしばらく遊んでしまった課題です!
グラフィック系なので、自分で付けた色や機能が実際にすぐ動かして目で楽しめるというのは思いの他嬉しいものでした。
課題に全く関係のない、JAXA が配布してる資料などから世界中の map を持ってきて動かして遊ぶなどをしました。
座標計算で 3D 風や動かすこともできることを知り、描画にかかる計算量の改善など工夫の余地がたくさんある課題でした。
調べたこと
投影、3 次元の座標変換、Bresenham のアルゴリズム、X Window System など
Repository
github.com
課題 6 (minitalk)
概要
C 言語で使用可能関数に制限あり。
2 つのプログラムを起動し、signal を使用してプロセス間通信をしてみる。
感想
今まで意識せず使っていた ctrl + C などが signal であったこと、命令が機械語になった時の割り込みなど signal を安全に使うのはかなり気を使わないといけないということなど、初めて signal について勉強して難しいですが面白かったです。
調べたこと
プロセス、PID、sigaction、kill、volatile、sig_atomic_t、非同期安全、コンパイラによる最適化 など
課題 7 (push swap)
概要
C 言語で使用可能関数に制限あり。
最初にランダムな数列が筒 A に入っているので、筒 A, B のみを用いて数列を sort し、かつその時の手数をなるべく少なくする。
感想
AtCoder でいうヒューリスティックのような課題です。
42 では珍しくアルゴリズム系の課題で、多分これだけです。*1
筒で可能な操作が決まっており、どんな sort が向いているのか、実行時間的にどの程度シミュレーションできるのか考え、所々に最適化を挟んで…という時間をかけようと思えばいくらでもかけられる課題でした。
手数をある程度減らすまでの試行錯誤は慣れている Python で書き、後で C 言語に移植する、という初めての試みをしてみましたが時間が数倍かかっただけでした…。
もっと最適化したかったですが C 言語では骨が折れ…。
手数もそこそこ少なめにでき、先人の方が作ってくれているビジュアライザのおかげで実際に書いたアルゴリズムで sort されていく様子も見られて面白かったです。
push swap visualizer
Copyright (C) 2007 Free Software Foundation, Inc. / LICENSE
調べたこと
色々な sort 方法、リングバッファなどのデータ構造
Repository
github.com
rank3 / 課題 8 (minishell)
所要時間
ざっくり各課題の(あまり当てにならない)推定所要時間と私が雑に計測している所要時間です。
推定所要時間 | 実際の所要時間 | |
---|---|---|
課題 8 (minishell) | 210 時間 | 548 時間 + 2 時間位のレビュー 3回 |
課題 8 (minishell)
概要
C 言語で使用可能関数に制限あり。2 人チームで以下に対応した Bash の簡易版を作成する。
- プロンプト表示して入力待機
- クオート :
'
,"
- リダイレクト :
<
.>
,<<
,>>
- パイプ :
|
- 環境変数、変数展開
$?
ctrl + C
、ctrl + D
、ctrl + \
- ビルトインコマンド : echo、cd、pwd、export、unset、env、exit
- and :
&&
- or :
||
- subshell :
( )
- wildcard :
*
独自の仕様などを含む細かな仕様はこちら → minishell's specification
感想
大変でしたが楽しかったです!!
今回はせっかくのチーム課題ということで、この課題でチーム開発について学べそうなことは時間が許せば全部やってみよう、という目的で取り組みました。
その結果予定を大幅に過ぎてしまったのですが…かなり満足のできる制作過程を踏んで shell が作れたので良い経験になりました。*2
Shell は基本的に Lexer(字句解析) → Parser(構文解析) → Evaluator(評価) というモジュールにきれいに分けられるので、チーム開発のしやすい課題であったというのも良かったです。
以下、試してみたことです。
チーム開発
- Git (branch、checkout、reset、rebase (edit, squash, drop)、stash、cherry pick、diff など)
- GitHub (Issue、Pull Request、Actions (bats, python script)、review 必須、perm link など)
- ペアプロ
- Issue 駆動開発
- テスト自動化 (ユニットテスト、統合テスト、valgrind での leak check)
データ構造
- deque 作成
- hash table 作成 (fnv-1 軽量ハッシュ)
- parser は AST (抽象構文木) を再帰下降構文解析で作成 (参考 : 低レイヤを知りたい人のためのCコンパイラ作成入門)
- AST を辿りながらコマンド実行
C 言語でオブジェクト指向ライク
その他
- 実装中に shell 変数と環境変数を区別できると便利なので declare コマンドの作成
- 課題要件内のものは、挙動や exit status、error message までなるべく本家 Bash に合わせた
良かった点 / 反省点
- 運良く同じような目的を持つ方とチームを組むことができ、最後まで妥協せずに課題に楽しく取り組めた。*3
- 基本ペアプロで、その外も細かい単位でお互いのコードレビューをしっかりすることで常に全体をお互いが大体把握できておりスムーズに進められた。
- 1 人では詰まりそうな所も相談すると解消が速い。
- 寝て起きたら機能が完成していた…!(感動!私も頑張ろうと思えた)
- 少しずつ動くものを拡張して作れたので常に見た目で成果物が試せて楽しかった。
- 休みを設けるのを忘れており知らない間に疲れが溜まっていたりした。ペアプロは特に休息も大事なよう。
- 最後の方は時間がなくなってきてしまったので最初からスケジュールを意識すれば良かった。が、実装したい中から優先順位をつけて限られた時間でできるものを選択する練習にはなった。
- Bash に合わせきれなかった箇所。*4
学んだこと
- 自動テストの大切さ。途中 2 行だけ追加してこのくらいは大丈夫だと思い merge しようとしたら actions test で思わぬ所で落ちたりしたので非常に助かった。
- 何かしら複雑度が増えてきそうなら根本の構造から考え直した方が良いこともある。
- 好みではなくプログラムとしてこっちの方が良いと思う理由を言葉で説明できるようにすることの大事さ。
- 拡張性、汎用性を適度にもたせて作る。
などなど
調べたこと
- man bash
- Bash Reference Manual
- readline, access, fork, wait, waitpid, getcwd, chdir, stat, unlink, exwcve, dup, dup2, pipe, opendir, readdir, closedir, isatty など
Repository
github.com
次は並行・並列プログラミングについての課題や、再びグラフィック系の課題を終えると、ついに C 言語が終わり C++ の課題を始められます。
1 つの課題に時間をかけ過ぎても退学というデッドラインが迫ってくるので塩梅が難しいところです…。