hryuutaのブログ

課題の概要
取り組み方
1.Lexer（単語分割）
- なぜ、分割するのか？
- 実装
2.Parser (構文解析)
4.Command execution（コマンド実行）
- パイプの実装方法
- FDの切り替え
工夫した点
感想
- 楽しかったこと
- 大変だったこと
終わりに

課題の概要

機能が制限されたbashを再実装します。

主に

・cat, touch, wc等のシンプルコマンド

・指定されたいくつかのbuiltin command

・cd, echo, pwdなどのコマンド

・構文解釈（ | "" ''）

・リダイレクト（< > >> <<<）

・環境変数の展開

を２人で実装します。

この課題で学べたこと・bashの仕様

・構文解析（Lexer, Parser）

・プロセスの作成、任意のプログラム実行

・パイプ、レダイレクション

・シグナルハンドリング

取り組み方

最初は何をしたらいいか分からなかったので、

The Architecture of Open Source Applications というオープンソースアプリケーションの設計について書かれた本の日本語訳を繰り返し読みました。

処理は大きく５つに分けられました。

Lexer（単語分割）
Parser（構文解析）
Expansion（変数展開）
builtin commandの実装
Command execution（コマンド実行）

ツールは以下を使用しました。

github
Nortion

　それぞれ、作業用のブランチを切って、ある程度の処理を実装できたらプルリクを送り、相手にレビューしてもらいました。

　共同スペースで、作業の進捗状況や情報、資料の共有を行いました。

担当は以下のように分けました。

Lexer（単語分割）担当　自分
Parser（構文解析）担当　自分
Expansion（変数展開）担当　ootaki
builtin commandの実装　担当　ootaki
Command execution（コマンド実行）担当　自分

1.Lexer（単語分割）

最初の処理の部分で受け取ったコマンドを最小単位まで分割します。

こんな感じで↓

//分割前
>$ echo "hello w"'w orld'|cat<file|wc

//分割後
echo
"hello w"'w orld'
|
cat
<
file
|
wc

なぜ、分割するのか？

入力されたコマンドが実行できるか判定するに当たっては、そもそも入力されたコマンドを構成する文字列はどうなっているかを確認する必要があります。そのチェックをし易くするために単語分割を行います。

実装

・分割する文字を判別

スペース、| > >> << <<< など、単語を分割すべき文字を見つけたら、そこで単語を分割します。

Lexerの段階では、まだ " ' は残ったままです。

”で囲まれている文字列は”ごと分割しています。" ' は3. Expansion で除去します。

2.Parser (構文解析)

// 分割前
>$ cat << exit > test.txt | cat > test.txt

// 分割後
>$ cat
>$ <<
>$ exit
>$ >
>$ test.txt
>$ |
>$ cat
>$ >
>$ test.txt

今回は;を考慮する必要がなく、｜を区切り文字として、連結リストを使い、cmd, redirectリストにグループ分けしています。

分割後の単語のc_typeを１個ずつ見ていき、dataのcmdリストとredirectリストに分割していきます。リストを分割した理由は主に

・HEAR_DOCがあるかどうか調べる必要があり、先頭から全部みるのは面倒臭いということ。

・fdの切り替えを行う必要があったこと。

からです。

c_typeがHEAR_DOCの場合、LIMMITERとなる文字を確保する必要があるので、limmiterにその文字列を確保しています。今回の例で言えば「exit」がLIMMITERになります。

|が来たら、dataをnextさせ、新しいリストを追加します。

f:id:hryuuta:20211102105438p:plain

data_lstの中には環境変数を入れたenv_listを入れています。keyには環境変数を代入し、valueには環境変数の中身を入れています。例えば、「USER = username」の場合、key = USER, value = usernameが入ります。環境変数はmain()の第三引数を入れると、環境変数を取ることができます。こんな感じで↓

MANPATH=/usr/share/man:/usr/local/share/man:/opt/homebrew/share/man
TERM_PROGRAM=vscode
TERM=xterm-256color
SHELL=/bin/zsh
HOMEBREW_REPOSITORY=/opt/homebrew
TMPDIR=/var/folders/t9/7vrrlrdn0h301z_br8cf_vb00000gn/T/
TERM_PROGRAM_VERSION=1.58.2
ORIGINAL_XDG_CURRENT_DESKTOP=undefined
USER=handaryuuta
HOMEBREW_SHELLENV_PREFIX=/opt/homebrew
COMMAND_MODE=unix2003
SSH_AUTH_SOCK=/private/tmp/com.apple.launchd.LTxIhR8yZt/Listeners
__CF_USER_TEXT_ENCODING=0x1F5:0x1:0xE
PATH=/usr/local/opt/llvm/bin:/usr/local/bin:/usr/bin:/bin:/usr/sbin:/sbin:/Library/Apple/usr/bin:/usr/local/opt/llvm/bin:/opt/homebrew/bin:/opt/homebrew/sbin
LaunchInstanceID=D3912DE0-AA6C-42C2-9397-C8CC55B646C4
__CFBundleIdentifier=com.microsoft.VSCode
PWD=/Users/handaryuuta/hryuuta/42tokyo/42_cursus/project_lank03/minishell
LANG=ja_JP.UTF-8
XPC_FLAGS=0x0
PS1=%F{green}%n%f:%F{blue}%d%f %F{yellow}⚡️%f
XPC_SERVICE_NAME=0
SHLVL=2
HOME=/Users/handaryuuta
VSCODE_GIT_ASKPASS_MAIN=/Applications/Visual Studio Code.app/Contents/Resources/app/extensions/git/dist/askpass-main.js
HOMEBREW_PREFIX=/opt/homebrew
LOGNAME=handaryuuta
VSCODE_GIT_IPC_HANDLE=/var/folders/t9/7vrrlrdn0h301z_br8cf_vb00000gn/T/vscode-git-05efc1ebb2.sock
VSCODE_GIT_ASKPASS_NODE=/Applications/Visual Studio Code.app/Contents/Frameworks/Code Helper (Renderer).app/Contents/MacOS/Code Helper (Renderer)
GIT_ASKPASS=/Applications/Visual Studio Code.app/Contents/Resources/app/extensions/git/dist/askpass.sh
INFOPATH=/opt/homebrew/share/info:
HOMEBREW_CELLAR=/opt/homebrew/Cellar
SECURITYSESSIONID=186b8
COLORTERM=truecolor
_=/usr/bin/env

4.Command execution（コマンド実行）

Expansionが終わると次はCommand executionに移ります。Command executionでは

大きく「パイプの実装」「FDの切り替え」「コマンド実行」の３つに分けられます。

パイプの実装方法

パイプは情報を受け渡しする役割を果たします。情報をストックする箱だと思ってください。

int pipe(int pipefd[2])　を使うとその箱が作られます。

pipefd[]にはpipefd[0]に読み込み用のfd、pipefd[1]に書き込み用のfdが格納されます。

pipeから情報を読み込む時はpipefd[0]を、書き込む時はpipefd[1]を使用します。

f:id:hryuuta:20211102105337p:plain

※pipefd[1]を閉じずにpipefd[0]から読み込みすると書き込みを待って処理が停止してしまいます。必ず、片方のpipefdは閉じて使用します。

pipeが複数の場合はpipeをその数分作る必要があります。

PIPEに書き込み、読み込みを行うのは

int execve(const char *filename， char *const argv[]， char *const envp[]) を使用して行います。

実行形式のファイルを実行する。

通常標準入力fdから入力を受け取り、標準出力fdに実行結果を出力します。

f:id:hryuuta:20211102105319p:plain

execveでは標準入力fd＝０、標準出力fd＝１に設定されているため、このまま使ってもPIPEには何も書き込まれません。

そこでPIPEから書き込み、読み込みができるようにするのがint dup2(int oldfd, int newfd) です。

oldfd(fd=ファイルディスクリプタ)を複製してnewfdに割り当てます。つまり、newfdはoldfdと同じファイルを指します。

例として、execve()を使いPIPEから読み込み、PIPEに書き込むためには

STDIN_FILENOとSTDOUT_FILENOの指し示し先をpipefd[0]とpipefd[1]が指し示す先と同じにする必要があります。それを行うと以下の図のようになります。

f:id:hryuuta:20211102105214p:plain

dup2()でfdを複製後、oldfdは使わないので、close(oldfd)します。

最終的に以下の図のようになります。

f:id:hryuuta:20211102105243p:plain

この状態でexecve()を実行するとPIPEから読み込んだ情報をもとにexecve()でコマンドを実行し、出力結果をPIPEに書き込まれます。

これまでの説明を元に、実際の打たれたコマンドの処理を図式化すると以下のような図になります。

入力例

$> cat infile | cat | wc -l

プロセスの処理イメージ図

FDの切り替え

パイプで繋がれていないbuiltinコマンドの場合、子プロセスでなく親プロセスで実行されます。子プロセスにしてしまうとexportなど環境変数の設定が親プロセスに反映されないためです。

親プロセスでリダイレクトすると、親の標準入力、標準出力などが書き換わり、その後のコマンド実行に影響が出ます。このため、上書きする前にファイルディスクリプタをdupしてバックアップし、リダイレクトが完了したら dup2 して復元する必要があります。

工夫した点

工夫した点としてはコマンドラインで入力された文字列が正しくパースされているかを確認しやすくする為にパース後のデータを出力するようにしました。このお陰でバグが起きた時に原因を突き止めやすくなりました。以下デバック時の動画

感想

楽しかったこと

チーム開発の楽しさ

２人での３ヶ月間の開発でしたが、自分にとっては初めての共同での開発であったため、個人の開発とは違う良い経験ができました。

プログラミング歴がほとんど同じ（だと思います。違ったらすみません）でしたが、コードの書き方や考え方が違い、意見交換やレビューをするのが非常に楽しく、勉強にもなりました。

大変だったこと

bashの仕様理解

42では毎度お馴染みですが、取り組み始めた時は本当に何をすればいいか分かりませんでした笑。bashの仕様がある程度理解できるまでは設計書を読み、bashのソースコードを読んで、サイトで参考になるものを探して、周りの人に聞いてを繰り返していました。

どこまで、originalのbashに寄せるか迷った

実装している途中でこれを実装としたら、これも実装した方がよくない？とどんどんbashの深みにハマっていきました笑

bashの細かい処理まで実装しようと思ったらキリがなく、どこまで実装すればいいか迷いました。

終わりに

最初は何をすればいいかわかりませんでしたが、お互い協力してなんとか終わらせることができました。

今回の課題を通して、共同開発の経験とbashの仕様やプログラムの実行を学ぶことができて良かったです。

気が向いたら、違う言語でbashを実装してみようかと思います。

ootakiさんありがとうございました。