zshのプロンプトテーマを自作した
自分用にzshのプロンプトテーマをRustで自作しました。 自分が常用しても問題ない程度の完成度になったので公開しました。
セグメントの表示内容は左上から
- OS
- ユーザ名@ホスト名
- (中間省略された) カレントディレクトリ
- Gitブランチ
- Gitユーザ
- 直前の終了ステータス
となっています。(順番、色、表示/非表示などに関してはカスタマイズ可能)
まだREADMEが空っぽなので後で中身を書きます。
以前使用していたプロンプト
bobthefish
ログインシェルにfishを使用していた頃 (~ 2018年9月) はプロンプトテーマに bobthefish を使用していました。
高機能で、更に環境変数によってある程度のカスタマイズができる非常によいテーマでした。 特に、それまではデフォルトプロンプトのbashやfishしか使ってこなかったこともあり、Powerline系のセグメントやGit statusの表示などは一種のカルチャーショックでした。 なにより見た目がかっこいい。テンションがあがるものはよいものにきまっている。
中間pathの省略については好みが分かれるところだとは思いますが、自分はonにしていました。
agnoster.zsh-theme
zshに乗り換えてからは agnoster.zsh-theme をカスタマイズして使用していました。 agnoster.zsh-themeはbobthefish以前に開発されたテーマです。
変更の内容は
- 中間path省略の実装
- 入力位置を次行に
- 直前の終了ステータスの値を表示
- 環境変数でセグメントの色や表示/非表示を切り替えられるように
RPROMPTに直前のコマンドの実行時間を表示- 現在のGitユーザ名を表示
などです。
この1年ほどはこれを使用していましたが、以下のような不満がありました。
- bobthefishに比べGit statusの情報が荒い (dirty/clean程度の情報しかわからない)
- zshスクリプトで書かれているのでコードが読みにくい、書きにくい
- 若干動作がもっさりしているような気がする
今回はzshスクリプトではなくRust、つまりネイティブな言語で実装することでもっさり感と書きやすさを解消したわけです。 ついでにGit statusの解像度をbobthefish程度にまで引き上げました。
他の候補
今回した自作したテーマ以外にも、ネイティブ言語で実装されたテーマは存在しています。
それぞれの特徴と、なぜそれらを使用しなかったかの理由を簡単に述べます。
silver
silver は、同じくRustで書かれたテーマです。bash, zsh, fishに対応しています。
gitコマンドをプロセスとして呼び出してその出力を利用するのではなく、libgit2を使用することで高速な表示を実現しています。 libgit2関係のコードはこのsilverを参考にさせてもらいました。
このテーマの不満点を以下に挙げます。
- 入力位置を2行目にすることができない
- Git statusの解像度がagnoster.zsh-themeと同程度
- エラーが発生するとすぐにpanicする
- mac向けのバイナリがGitHub Releaseに用意されていないので
cargo installする必要があるが、自分用dotfilesではRustのインストールをしないようにしているので扱いが難しい
powerline-go
powerline-go はその名の通りGoで実装されたテーマです。同じくbash, zsh, fishに対応しています。 これは珍しく2行表示に対応したテーマです。
このテーマの不満点です。
ちなみにこのテーマはlibgit2を使用せず、gitコマンドの出力を利用してブランチなどの情報を表示しています。
自作テーマ
そういうわけでなんとなくテーマを自作することにしました。 開発はRustで行い、silverに倣ってlibgit2を利用しています。
デザインは基本的に (カスタマイズ後の)agnoster.zsh-theme をトレースしています。
また、$XDG_CONFIG_HOME/almel/ 以下 (もしくは $HOME/.config/almel/以下)にあるYAMLファイルを読み込むことでセグメントの表示順や表示の有無、色、アイコンなどを自由にカスタマイズできるようになっています。
表示速度に関しては、ざっくり1.5倍程度速くなりました。(zshのプリコンパイル機能は思ったよりつよい)
流石にネイティブ実装は速い (エンター押しっぱなしにしたときのzshテーマの反応) pic.twitter.com/e3D4S5Akka
— りょがまや (@Ryooooooga) 2019年10月16日
これから機能の拡張や高速化をしたりドキュメントを整えたりする予定です。 それから、現在はzshにしか対応していないのでbashにも対応させたいです。
インストール
適当にcrates.ioで公開したのでcargoからインストールできます。
cargoを利用したインストール
$ cargo install almel $ eval "$(almel init zsh)"
zpluginを利用したインストール (現在はmac用のバイナリしか用意していない)
$ zplugin ice from"gh-r" as"program" mv"almel* -> almel" $ zplugin load Ryooooooga/almel $ eval "$(almel init zsh)"
セルフホスティングCコンパイラを書いた
セルフホスト(自分自身をビルド)できるCコンパイラnoccを書きました。
はじめに
去年の夏あたりからCコンパイラを書くのが流行っていたのでやってみました。
例によって@rui314さんの8cc、9ccと低レイヤを知りたい人のためのCコンパイラ作成入門を参考にしていますが、バックエンドにはLLVMを使用しています。
工夫した点
以下、作る上で工夫した点です。
言語仕様に制限をつける
C言語の全仕様を網羅しようとすると到底完成は不可能なのでサポートする言語仕様に制限をつけまくりました。 制限には例えば以下のようなものがあります。
- 変数宣言が初期値を取れない。
- 複数の変数をコンマ区切りで宣言できない。
- typedef宣言や型のconst修飾などはその語順を固定している。
- 型解析時は型のconst修飾を無視する。
- 関数のプロトタイプ宣言はトップレベルでのみ行える。
- 関数ポインタが使えない。(関数ポインタ自体は実装してあるが関数ポインタ型の変数を宣言できない)
- 列挙体が使えない。
- etc
セルフコンパイルに不要そうな機能はあらかた切り捨て、また、そのような機能はできる限り使用せずにコードを書くことで比較的短期間でセルフコンパイルに漕ぎつけることができました。(最初のコミットが2019年4月4日 12:02でセルフコンパイルに成功したのが2019年4月14日 14:30 前後なのでだいたい10日間くらい)
テスト駆動的に開発する
noccの開発はテスト駆動的に行いました。
テストの記述にはLLVMのJITコンパイルが非常に役に立ちました。
参考: nocc/test_engine.c at master · Ryooooooga/nocc · GitHub
意味解析器を構文解析器から分離
構文解析器の中に型検査やシンボルの解決などのコードを書くと、コードが肥大化したり見通しが悪くなったりしがちです。
文脈自由言語であれば、構文解析フェーズで(型情報なしの)抽象構文木を生成し、そのあとで木訪問器(Visitor)を使ってその抽象構文木に型情報やシンボルの情報を追加する手法が取られることがあります。
しかし、C言語は文脈依存言語であるため、(typedef宣言をサポートする場合) シンボルの登録や解決を構文解析と同時に行う必要があります。
例えば、a * b;というC言語のコードがあったとして、このコードがどのような意味を持つのかはそれ以前の文脈に依存します。
{
int a;
int b;
a * b; /* ここでは乗算 */
}
{
typedef int a;
a * b; /* ここではint*型の変数bの宣言 */
}
そこでnoccではswiftcなどを参考に意味解析器をモジュール化し、構文解析器から呼び出されるコールバック関数として実装することで構文解析と意味解析のコードを分割することにしました。
実際のコードを示しながらどのように分割を行ったか述べます。
識別子式の解析
以下の関数、parse_identifier_expr()は単一の識別子からなる式(a, ctx, printfのような)の構文解析を行う関数です。
ExprNode *parse_identifier_expr(ParserContext *ctx) {
const Token *t;
/* トークンを読む */
t = consume_token(ctx);
/* トークンが識別子であることをチェックする */
if (t->kind != token_identifier) {
fprintf(stderr, "expected identifier, but got %s\n", t->text);
exit(1);
}
/* 意味解析モジュールの呼び出し */
return sema_identifier_expr(ctx, t);
}
見ての通り、実装としてはトークンを1つ読んで識別子かどうかを確かめているだけの単純なものです。
このparse_identifier_expr()から呼び出されている関数、sema_identifier_expr()が意味解析モジュールのコールバック関数です。
これは1つの識別子トークンを受け取り、シンボルの解決や型情報の解決を行ったあとその式を表す抽象構文木のノードを返す関数です。
ExprNode *sema_identifier_expr(ParserContext *ctx, const Token *t) { /* 抽象構文木のノードを表す構造体 */ IdentifierNode *p; /* ノードの構築 (省略) */ /* 現在のスコープからシンボルの宣言を探す */ p->declaration = scope_stack_find(ctx->env, t->text, true); if (p->declaration == NULL) { /* シンボルが見つからなかった */ fprintf(stderr, "undeclared symbol %s\n", t->text); exit(1); } /* (省略) */ /* 式の型は宣言された変数の型と同じ */ p->type = p->declaration->type; /* 構築したノードを構文解析器に返す */ return (ExprNode *)p; }
[2019/04/15 追記]
次はより複雑な文の解析を行う場合を見てみます。
複合文の解析
{ ... } によって表現される複合文 (Compound Statement)はレキシカルスコープを形成します。
この文の構文解析は以下の関数、parse_compound_stmt()によって行われます。
StmtNode *parse_compound_stmt(ParserContext *ctx) {
const Token *open;
const Token *close;
Vec *stmts;
/* 複合文の形成するレキシカルスコープに入る */
sema_compound_stmt_enter(ctx);
/* トークンを読む */
open = consume_token(ctx);
/* トークンが 「{」 であることを確認する */
if (open->kind != '{') {
fprintf(stderr, "expected {, but got %s\n", open->text);
exit(1);
}
/* 内部の文の抽象構文木ノードを格納するvectorを生成する */
stmts = vec_new();
/* 「}」 トークンが出現するまで繰り返し文を解析する */
while (current_token(ctx)->kind != '}') {
vec_push(stmts, parse_stmt(ctx));
}
/* トークンを読む */
close = consume_token(ctx);
/* トークンが 「}」 であることを確認する */
if (close->kind != '}') {
fprintf(stderr, "expected }, but got %s\n", close->text);
exit(1);
}
/* 抽象構文木ノードを生成し、レキシカルスコープから抜ける */
return sema_compound_stmt_leave(ctx, open, (StmtNode **)stmts->data,
stmts->size, close);
}
上のコードでは、識別子式の例とは異なり意味解析モジュールが2回呼び出されています。
sema_compound_stmt_enter()関数sema_compound_stmt_leave()関数
これらはそれぞれ「{」の出現時、「}」の出現時に呼び出されるコールバック関数であり、複合文が形成するレキシカルスコープの生成と破棄を担当します。
/* 複合文の開始時に呼び出されるコールバック関数 */ void sema_compound_stmt_enter(ParserContext *ctx) { /* 新しいスコープをスタックにプッシュする */ sema_push_scope(ctx); } /* 複合文の終了時に呼び出されるコールバック関数 */ StmtNode *sema_compound_stmt_leave(ParserContext *ctx, const Token *open, StmtNode **stmts, int num_stmts, const Token *close) { /* 抽象構文木のノードを表す構造体 */ CompoundNode *p; /* (省略) */ /* スタックからスコープを取り除く */ sema_pop_scope(ctx); /* ノードの構築 (省略) */ /* 構築したノードを構文解析器に返す */ return (StmtNode *)p; }
[2019/04/15 追記ここまで]
このように構文解析と意味解析を分離する試みは結果的に成功し、構文解析器 (parser.c) と 意味解析器 (sema.c) 双方の見通しの良さを保つことができました。
まとめ
コード生成はLLVMにおんぶにだっこであんまりちゃんと書けた気がしません。
気が向いたらx86_64のコードを吐けるようにしてみようと思います。
現状です pic.twitter.com/9lWaWAS8w1
— あやか (@Ryooooooga) 2019年4月14日
これでコンパイラ書けます言える
— あやか (@Ryooooooga) 2019年4月14日
他人に堂々とコンパイラハラスメントできる
— あやか (@Ryooooooga) 2019年4月14日
JITコンパイル時の関数呼び出しの扱い方
x86_64での関数呼び出し
x86_64(以下x64)ではcall命令の呼び出し関数の指定を相対アドレスで行うため、JITコンパイルをする際はそのアドレスの取り扱いに苦労します。
#include <stdio.h> #include <string.h> #include <sys/mman.h> int main(void) { const char code[] = { /* * int f(void) { * return add(2, 3); * } */ 0xbe, 0x03, 0x00, 0x00, 0x00, // mov esi, 3 0xbf, 0x02, 0x00, 0x00, 0x00, // mov edi, 2 0xe8, 0x01, 0x00, 0x00, 0x00, // call +1 # (相対アドレスでaddを指す) 0xc3, // ret /* * int add(int x, int y) { * return x + y; * } */ 0x89, 0xf8, // mov eax, edi 0x01, 0xf0, // add eax, esi 0xc3, // ret }; const size_t size = sizeof(code); // 実行可能なメモリ領域を確保する void* ptr = mmap(NULL, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (ptr == MAP_FAILED) { return 1; } memcpy(ptr, code, size); // 機械語を呼び出す int (*f)(void) = ptr; printf("%d\n", f()); // 5 // 確保した領域を解放する munmap(ptr, size); return 0; }
上の例では、相対アドレス+0x00000001を指定して、その直後に定義される関数addを呼び出しています。
0xe8, 0x01, 0x00, 0x00, 0x00, // call +1 # (相対アドレスでaddを指す)
呼び出す関数がこのように同一のコードセグメントに含まれる場合はこのように指定すればいいのですが、 標準ライブラリの関数やコンパイラ側で定義した関数の呼び出しを行う場合は呼び出しアドレス指定の取り扱いに困ります。
// C言語側で定義された関数 int sub(int a, int b) { return a - b; } //------------------------ 0xe8, 0x??, 0x??, 0x??, 0x??, // call sub (subの相対オフセットがわからない)
レジスタを経由して絶対アドレス指定で関数を呼び出す
このような場合は、レジスタ経由で呼び出すと絶対アドレス指定ができるため、取り扱いが簡単になります。
mov rax, <subの絶対アドレス> call rax
これをコードにすると次のようになります。
int sub(int a, int b) { return a - b; } //----------------------- char code[] = { /* * int f(void) { * return sub(2, 3); * } */ 0xbe, 0x03, 0x00, 0x00, 0x00, // mov esi, 3 0xbf, 0x02, 0x00, 0x00, 0x00, // mov edi, 2 0x48, 0xb8, 0x00, 0x00, 0x00, 0x00, // mov rax, sub 0x00, 0x00, 0x00, 0x00, // 0xff, 0xd0, // call rax 0xc3, // ret }; // subの絶対アドレスを指定する code[0x0c] = (uintptr_t)sub >> 0; code[0x0d] = (uintptr_t)sub >> 8; code[0x0e] = (uintptr_t)sub >> 16; code[0x0f] = (uintptr_t)sub >> 24; code[0x10] = (uintptr_t)sub >> 32; code[0x11] = (uintptr_t)sub >> 40; code[0x12] = (uintptr_t)sub >> 48; code[0x13] = (uintptr_t)sub >> 56;
全コード
#include <stdio.h> #include <stdint.h> #include <string.h> #include <sys/mman.h> int sub(int a, int b) { return a - b; } int main(void) { char code[] = { /* * int f(void) { * return sub(2, 3); * } */ 0xbe, 0x03, 0x00, 0x00, 0x00, // mov esi, 3 0xbf, 0x02, 0x00, 0x00, 0x00, // mov edi, 2 0x48, 0xb8, 0x00, 0x00, 0x00, 0x00, // mov rax, sub 0x00, 0x00, 0x00, 0x00, // 0xff, 0xd0, // call rax 0xc3, // ret }; code[0x0c] = (uintptr_t)sub >> 0; code[0x0d] = (uintptr_t)sub >> 8; code[0x0e] = (uintptr_t)sub >> 16; code[0x0f] = (uintptr_t)sub >> 24; code[0x10] = (uintptr_t)sub >> 32; code[0x11] = (uintptr_t)sub >> 40; code[0x12] = (uintptr_t)sub >> 48; code[0x13] = (uintptr_t)sub >> 56; const size_t size = sizeof(code); // 実行可能なメモリ領域を確保する void* ptr = mmap(NULL, size, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (ptr == MAP_FAILED) { return 1; } memcpy(ptr, code, size); // 機械語を呼び出す int (*f)(void) = ptr; printf("%d\n", f()); // -1 // 確保した領域を解放する munmap(ptr, size); return 0; }
structured bindings(構造化束縛)を自作クラスで行えるようにする
はじめに
structured bindings (構造化束縛) をstd::pair<>やstd::tuple<>以外の自作のクラスに対して適用するための方法をコード例込みで解説している日本語の記事が見つからなかったのでメモを兼ねて残しておきます。
結論
std::tuple_size<T>を特殊化するstd::tuple_element<N, T>を特殊化するget<N>(T)/T::get<N>()を定義する
structured bindings (構造化束縛)
Structured binding declaration (since C++17) - cppreference.com
structured bindings は C++17 に追加された有用な機能で、関数の返り値からの多値の受け取りなどを簡便に行える言語機能です。
* 関数から複数の値を受け取る例
// 複数の値を返す関数 std::tuple<int, std::string, double> f() { return std::make_tuple(42, "foo", 3.14); } int main() { // 関数からの返り値を受ける auto [n, s, d] = f(); assert(n == 42); assert(s == "foo"); assert(d == 3.14); }
上の例を structured bindings を使わずに書くと例えば次のようになります。
* structured bindings を使わずに関数から複数の値を受け取る例
int main() { int n; std::string s; double d; std::tie(n, s, d) = f(); assert(n == 42); assert(s == "foo"); assert(d == 3.14); }
structured bindings は、std::tuple<>以外にもいくつかの型についてその恩恵を受けることが出来ます。
* std::tuple<>以外の多値型を受け取る例
{
// std::pair<>
auto [a, b] = std::make_pair("bar", 100);
}
{
// 生配列
int raw_array[3] = {1, 2, 3};
auto [a, b, c] = raw_array;
}
{
// std::array<>
std::array<int, 3> array = {1, 2, 3};
auto [a, b, c] = array;
}
{
// 構造体
// 非staticなメンバ変数はすべてpublicである必要がある
struct S {
std::string a;
int b;
};
auto [a, b] = S { "bar", 10 };
}
自作クラスに structured bindings を適用する
上記に当てはまらないようなクラスについても structured bindings を適用することが出来ます。
例えば次のような privateな 非staticメンバ変数を持つクラスColorを考えます。
* 自作クラス
class Color { std::uint32_t c; public: Color(std::uint32_t c) : c(c) {} std::uint8_t red() const { return c >> 16; } std::uint8_t green() const { return c >> 8; } std::uint8_t blue() const { return c >> 0; } };
(Colorは内部に色の16進表現を保存し、メンバ関数red(), green(), blue() でRGBそれぞれの色要素を取り出せるようなクラスを想定しています)
これをauto [r, g, b] = ...のように受け取りたいのですが、そのままでは当然エラーになってしまいます。
int main() { Color orange = 0xff8000; auto [r, g, b] = orange; // エラー: cannot decompose non-public member 'Color::c' of 'Color' }
一度std::tuple<>に変換する関数を用意してauto [r, g, b] = orange.as_tuple();のように書いてもいいのですが直截的でないので別の方法をとります。
1. std::tuple_size<>を特殊化する
まずはじめに、structured bindings で受け取る変数の個数をコンパイラに示します。
コンパイラはstd::tuple_size<>::valueの値でこれを確認するため、std::tuple_size<Color>を特殊化します。
* std::tuple_size<>の特殊化
namespace std { template <> struct tuple_size<Color> : integral_constant<size_t, 3> {}; // Color は 3要素である }
2. std::tuple_element<>を特殊化する
次に要素の型をコンパイラに示します。
これにはstd::tuple_element<>::typeが使われるため、std::tuple_element<N, Color>を特殊化します。
* std::tuple_element<>の特殊化
namespace std { template <size_t N> struct tuple_element<N, Color> { using type = uint8_t; // 要素の型はすべて std::uint8_t }; }
3-a. フリー関数get<>()を定義する
最後に実際に要素の値を取り出します。
これには関数get<N>(Color)が用いられるのでそれを定義します。
使用される関数はADLによって探索されるので目的のクラスと同じ名前空間に定義すれば良いでしょう。
* get<>()の定義
template <std::size_t N> uint8_t get(const Color& c) { if constexpr (N == 0) return c.red(); else if constexpr (N == 1) return c.green(); else return c.blue(); }
以上で自作クラスColorに structured bindings を適用することが可能になります。
* Colorに対する structured bindings
int main() { Color orange = 0xff8000; auto [r, g, b] = orange; assert(r == 255); assert(g == 128); assert(b == 0); }
3-b. メンバ関数get<>()を定義する
フリー関数get<>()の代わりにメンバ関数get<>()を使用することも可能です。
* メンバ関数Color::get<>()の定義
class Color { ... template <std::size_t N> std::uint8_t get() const { if constexpr (N == 0) return red(); else if constexpr (N == 1) return green(); else return blue(); } };
フリー関数get<N>(Color)と、メンバ関数Color::get<N>()が同時に定義されていた場合、メンバ関数Color::get<N>()が優先的に使用されます。
まとめ
structured bindings はGCC/ClangのみでなくMSVCでも利用することの出来る優れた機能です。
「C++は複数の値を関数から返すことのできない言語だ」などと揶揄されることもしばしばありましたが今やその限りではありません。
* 全コード
#include <cassert> #include <tuple> #include <iostream> class Color { std::uint32_t c; public: Color(std::uint32_t c) : c(c) {} std::uint8_t red() const { return c >> 16; } std::uint8_t green() const { return c >> 8; } std::uint8_t blue() const { return c >> 0; } template <std::size_t N> std::uint8_t get() const { std::cout << "Color::get<" << N << ">()" << std::endl; if constexpr (N == 0) return red(); else if constexpr (N == 1) return green(); else return blue(); } }; template <std::size_t N> uint8_t get(const Color& c) { std::cout << "get<" << N << ">(Color)" << std::endl; if constexpr (N == 0) return c.red(); else if constexpr (N == 1) return c.green(); else return c.blue(); } namespace std { template <> struct tuple_size<Color> : integral_constant<size_t, 3> {}; // Color は 3要素である template <size_t N> struct tuple_element<N, Color> { using type = uint8_t; // 要素の型はすべて std::uint8_t }; } int main() { Color orange = 0xff8000; // こう受け取りたい auto [r, g, b] = orange; assert(r == 255); assert(g == 128); assert(b == 0); }
MSVCでempty base optimizationの効かないパターンと対策
問題
2つ以上の空クラスを継承するようなクラスについて、MSVCで empty base optimization (EBO) が期待した通りに働かず、余分な領域が消費される。
struct Empty1 {}; struct Empty2 {}; // 1つの空クラスを基底に持つ struct Derived1 : Empty1 { int i; }; // 2つの空クラスを基底に持つ struct Derived2 : Empty1, Empty2 { int i; }; static_assert(sizeof(Empty1) == 1); static_assert(sizeof(Empty2) == 1); static_assert(sizeof(Derived1) == sizeof(int)); static_assert(sizeof(Derived2) == sizeof(int)); // MSVCにてエラー
対策
__declspec(empty_bases)拡張属性をEBOを期待するクラスの宣言に付与する。
struct __declspec(empty_bases) Derived2 : Empty1, Empty2 { int i; }; static_assert(sizeof(Derived2) == sizeof(int));
参考: Optimizing the Layout of Empty Base Classes in VS2015 Update 2 | Visual C++ Team Blog
empty base optimization
C++では空クラス(メンバ変数を持たず、仮想メンバ関数を持たないクラス)のサイズは必ず 1以上の大きさを持ちます。
(現行のほとんどの環境で空クラスのサイズは1になります)
struct Empty {}; static_assert(sizeof(Empty) > 0); // 多くの環境で sizeof(Empty) == 1
EBOはその様な空クラスを継承する際のメモリレイアウトに関する最適化の一種で、 継承先のクラスに余分な領域を確保しないようにする効果があります。
struct Empty {}; // 空クラス struct NotEmpty { char c; }; // 空でないクラス // どちらもサイズは1byte static_assert(sizeof(Empty) == 1); static_assert(sizeof(NotEmpty) == 1); // 基底クラスが空クラスなのでEBOが効く struct A : Empty { int i; }; static_assert(sizeof(A) == sizeof(int)); // 基底クラスが空でないので // メンバ変数と基底クラスの領域 (+ アライメントのためのパディング)分のサイズを必要とする struct B : NotEmpty { int i; }; static_assert(sizeof(B) > sizeof(int));
例えばsizeof(int) == 4, alignof(int) == 4であるようなある環境ではsizeof(A) == 4, sizeof(B) == 8となりました。
MSVCでの動作
MSVCではただ1つの空クラスを継承するようなクラスに関して他のコンパイラ同様EBOが働きますが、 2つ以上の空クラスを継承する場合 (デフォルトでは) EBOが働きません。
上に挙げた参考サイトの記述によると、
The Visual C++ compiler has historically had limited support for EBCO; however, in Visual Studio 2015 Update 2, we have added a new __declspec(empty_bases) attribute for class types that takes full advantage of this optimization.
VS2015 Update 2 以降では クラスの宣言に__declspec(empty_bases)を付与することで複数の空クラスを継承する場合にもEBOが有効になる様です。
struct Empty1 {}; struct Empty2 {}; // 定義に __declspec(empty_bases) を付ける struct __declspec(empty_bases) Derived1 : Empty1, Empty2 { int i; }; static_assert(sizeof(Derived1) == sizeof(int)); // EBOが効くようになった // または前方宣言に __declspec(empty_bases) を付ける struct __declspec(empty_bases) Derived2; struct Derived2 : Empty1, Empty2 { int i; }; static_assert(sizeof(Derived2) == sizeof(int)); // EBOが効くようになった
MSVCに於いてこのような場合のEBOが依然としてデフォルトで有効にならないのはABI互換性を保つためのようです。
他のコンパイラでもビルドを出来るようにするにはマクロを使った工夫が必要になるでしょう。
#if defined(_MSC_VER) && _MSC_FULL_VER >= 190023918 # define EMPTY_BASES __declspec(empty_bases) // VS2015 Update 2 以降 #else # define EMPTY_BASES #endif struct EMPTY_BASES Derived : Empty1, Empty2 { int i; }; static_assert(sizeof(Derived) == sizeof(int));
見た目がダサい
どのような場合に問題になるか
クラス内部のメモリレイアウトに依存したプログラムを書くような場合、EBOが効かないことが問題となります。
理想的にはクラスのメモリレイアウトに極力依存しないことが理想ではありますが、実際問題としてC/C++では特定のメモリレイアウトを期待するようなプログラムを書く必要に迫られる場面も少なからず存在します。
そのような時、プログラムが予想と違う動作をした場合には実際にメモリ上にどの様にクラスが展開されているのかを注意深く確認しましょう。
最近プリプロセス時処理が楽しい
はじめに
Boost.Preprocessorの実装を調べているうちに色々出来ることが分かって楽しくなってきた。
基本的なことから曲芸的なことまで適当にパターンをメモっておきます。
シンボルの結合
#define PP_CAT(a, b) PP_CAT_I(a, b) #define PP_CAT_I(a, b) a ## b #define PP_CAT3(a, b, c) PP_CAT3_I(a, b, c) #define PP_CAT3_I(a, b, c) a ## b ## c #define X x #define Y y #define Z z PP_CAT(a, b) // => ab PP_CAT(X, Y) // => xy PP_CAT3(a, b, c) // => abc PP_CAT3(X, Y, Z) // => xyz
論理演算
数値 => 0/1
#define PP_BOOL(x) PP_CAT(PP_BOOL_, x) #define PP_BOOL_0 0 #define PP_BOOL_1 1 #define PP_BOOL_2 1 #define PP_BOOL_3 1 #define PP_BOOL_4 1 // ... PP_BOOL(0) // => 0 PP_BOOL(1) // => 1 PP_BOOL(2) // => 1 PP_BOOL(3) // => 1
否定
#define PP_NOT(x) PP_CAT(PP_NOT_, PP_BOOL(x)) #define PP_NOT_0 1 #define PP_NOT_1 0 PP_NOT(0) // => 1 PP_NOT(1) // => 0 PP_NOT(2) // => 0 PP_NOT(3) // => 0
AND/OR
#define PP_OR(x, y) PP_CAT3(PP_OR_, x, y) #define PP_OR_00 0 #define PP_OR_01 1 #define PP_OR_10 1 #define PP_OR_11 1 PP_OR(0, 0) // => 0 PP_OR(0, 1) // => 1 PP_OR(1, 0) // => 1 PP_OR(1, 1) // => 1 #define PP_AND(x, y) PP_CAT3(PP_AND_, x, y) #define PP_AND_00 0 #define PP_AND_01 0 #define PP_AND_10 0 #define PP_AND_11 1 PP_AND(0, 0) // => 0 PP_AND(0, 1) // => 0 PP_AND(1, 0) // => 0 PP_AND(1, 1) // => 1
条件分岐
#define PP_IF(b, x, y) PP_CAT(PP_IF_, PP_BOOL(b))(x, y) #define PP_IF_0(x, y) y #define PP_IF_1(x, y) x PP_IF(0, a, b) // => b PP_IF(1, a, b) // => a
引数
先頭/先頭以外の引数の取り出し
#define PP_ARG_HEAD(_0, ...) _0 #define PP_ARG_TAIL(_0, ...) __VA_ARGS__ PP_ARG_HEAD(a, b, c) // => a PP_ARG_TAIL(a, b, c) // => b, c
N個目の引数の取り出し
#define PP_ARG_GET(n, ...) PP_CAT(PP_ARG_GET_, n)(__VA_ARGS__) #define PP_ARG_GET_0(_0, ...) _0 #define PP_ARG_GET_1(_0, _1, ...) _1 #define PP_ARG_GET_2(_0, _1, _2, ...) _2 #define PP_ARG_GET_3(_0, _1, _2, _3, ...) _3 ... PP_ARG_GET(0, a, b, c) // => a PP_ARG_GET(1, a, b, c) // => b PP_ARG_GET(2, a, b, c) // => c
リスト操作
展開
#define PP_LIST_UNPACK(list) PP_LIST_UNPACK_I list #define PP_LIST_UNPACK_I(...) __VA_ARGS__ PP_LIST_UNPACK((a, b, c)) // => a, b, c
先頭の要素、先頭を取り除いたリストの取り出し
#define PP_LIST_HEAD(list) PP_ARG_HEAD list #define PP_LIST_TAIL(list) (PP_ARG_TAIL list) PP_LIST_HEAD((a, b, c)) // => a PP_LIST_TAIL((a, b, c)) // => (b, c)
N番目の要素の取り出し
#define PP_LIST_GET(list, n) PP_CAT(PP_ARG_GET_, n) list PP_LIST_GET((a, b, c), 0) // => a PP_LIST_GET((a, b, c), 1) // => b PP_LIST_GET((a, b, c), 2) // => c
要素の個数
#define PP_LIST_SIZE(list) PP_ARG_SIZE list PP_LIST_SIZE(()) // => 0 PP_LIST_SIZE((a)) // => 1 PP_LIST_SIZE((a, b)) // => 2 PP_LIST_SIZE((a, b, c)) // => 3
リストが空かどうか
#define PP_LIST_IS_EMPTY(list) PP_NOT(PP_LIST_SIZE(list)) PP_LIST_IS_EMPTY(()) // => 1 PP_LIST_IS_EMPTY((a)) // => 0 PP_LIST_IS_EMPTY((a, b)) // => 0 PP_LIST_IS_EMPTY((a, b, c)) // => 0
要素の追加
#define PP_LIST_PUSH_FRONT(list, item) PP_IF(PP_LIST_SIZE(list), (item, PP_LIST_UNPACK(list)), (item)) #define PP_LIST_PUSH_BACK(list, item) PP_IF(PP_LIST_SIZE(list), (PP_LIST_UNPACK(list), item), (item)) PP_LIST_PUSH_FRONT((), a) // => (a) PP_LIST_PUSH_FRONT((b), a) // => (a, b) PP_LIST_PUSH_FRONT((b, c), a) // => (a, b, c) PP_LIST_PUSH_BACK((), a) // => (a) PP_LIST_PUSH_BACK((a), c) // => (a, b) PP_LIST_PUSH_BACK((a, b), c) // => (a, b, c)
繰り返し
#define PP_WHILE(pred, op, state) PP_WHILE_0(pred, op, state) #define PP_WHILE_0(pred, op, state) PP_IF(pred(state), PP_WHILE_1(pred, op, op(state)), state) #define PP_WHILE_1(pred, op, state) PP_IF(pred(state), PP_WHILE_2(pred, op, op(state)), state) #define PP_WHILE_2(pred, op, state) PP_IF(pred(state), PP_WHILE_3(pred, op, op(state)), state) ... #define PP_WHILE_10(pred, op, state) PP_IF(pred(state), PP_WHILE_11(pred, op, op(state)), state) #define PP_WHILE_11(pred, op, state) PP_WHILE_ERROR PP_WHILE(PP_LIST_SIZE, PP_LIST_TAIL, (a, b, c)) // => () PP_WHILE(PP_LIST_IS_EMPTY, PP_LIST_TAIL, (a, b, c)) // => (a, b, c)
pred(state) が1の間 state <- op(state) を適用し続けます。
擬似コードで書くとこんな感じ
function PP_WHILE(pred, op, state) {
while (pred(state))
state = op(state)
return state
}
ただしマクロ関数は再帰呼び出しが出来ないため同じマクロ関数を複数用意して順番に呼び出していくことで擬似的にループを実現します。
この例では10回までのイテレーションが可能です。
また、PP_WHILE()の引数predまたはopにPP_WHILE()を内部で使うマクロ関数は渡せません。
その場合は再帰呼び出しになるためマクロ展開が失敗します。
そのため、PP_WHILE()と同様のマクロ関数を複数用意しておくといいでしょう。
#define PP_WHILE_A(pred, op, state) PP_WHILE_A_0(pred, op, state) #define PP_WHILE_A_0(pred, op, state) PP_IF(pred(state), PP_WHILE_A_1(pred, op, op(state)), state) #define PP_WHILE_A_1(pred, op, state) PP_IF(pred(state), PP_WHILE_A_2(pred, op, op(state)), state) #define PP_WHILE_A_2(pred, op, state) PP_IF(pred(state), PP_WHILE_A_3(pred, op, op(state)), state) ... #define PP_WHILE_A_10(pred, op, state) PP_IF(pred(state), PP_WHILE_A_11(pred, op, op(state)), state) #define PP_WHILE_A_11(pred, op, state) PP_WHILE_ERROR #define PP_WHILE_B(pred, op, state) PP_WHILE_B_0(pred, op, state) #define PP_WHILE_B_0(pred, op, state) PP_IF(pred(state), PP_WHILE_B_1(pred, op, op(state)), state) #define PP_WHILE_B_1(pred, op, state) PP_IF(pred(state), PP_WHILE_B_2(pred, op, op(state)), state) #define PP_WHILE_B_2(pred, op, state) PP_IF(pred(state), PP_WHILE_B_3(pred, op, op(state)), state) ... #define PP_WHILE_B_10(pred, op, state) PP_IF(pred(state), PP_WHILE_B_11(pred, op, op(state)), state) #define PP_WHILE_B_11(pred, op, state) PP_WHILE_ERROR #define PP_WHILE_C(pred, op, state) PP_WHILE_C_0(pred, op, state) #define PP_WHILE_C_0(pred, op, state) PP_IF(pred(state), PP_WHILE_C_1(pred, op, op(state)), state) #define PP_WHILE_C_1(pred, op, state) PP_IF(pred(state), PP_WHILE_C_2(pred, op, op(state)), state) #define PP_WHILE_C_2(pred, op, state) PP_IF(pred(state), PP_WHILE_C_3(pred, op, op(state)), state) ... #define PP_WHILE_C_10(pred, op, state) PP_IF(pred(state), PP_WHILE_C_11(pred, op, op(state)), state) #define PP_WHILE_C_11(pred, op, state) PP_WHILE_ERROR
[追記]
BOOST_PP_AUTO_REC()(AUTO RECursion)のような仕組みを用いることで使用すべきPP_WHILE_*を自動的に決定できるためPP_WHILE()の引数にPP_WHILE()を使う関数を渡せるようにできます。
www.slideshare.net
#define PP_AUTO_REC(pred) PP_AUTO_REC_NODE_2(pred) #define PP_AUTO_REC_NODE_2(p) PP_IF(p(2), PP_AUTO_REC_NODE_1(p), PP_AUTO_REC_NODE_3(p)) # define PP_AUTO_REC_NODE_1(p) PP_IF(p(1), 1, 2) # define PP_AUTO_REC_NODE_3(p) PP_IF(p(3), 3, 4) #define PP_WHILE PP_CAT(PP_WHILE, PP_AUTO_REC(PP_WHILE_CHECK)) #define PP_WHILE_CHECK(n) PP_CAT(PP_WHILE_CHECK_, PP_WHILE ## n(PP_WHILE_CHECK_P, PP_WHILE_CHECK_O, OK)) #define PP_WHILE_CHECK_P(s) 0 #define PP_WHILE_CHECK_O(s) #define PP_WHILE_CHECK_OK 1 #define PP_WHILE1 PP_WHILE1_0 #define PP_WHILE_CHECK_PP_WHILE1_0(p, o, s) 0 #define PP_WHILE1_0(pred, op, state) PP_IF(pred(state), PP_WHILE1_1(pred, op, op(state)), state) #define PP_WHILE1_1(pred, op, state) PP_IF(pred(state), PP_WHILE1_2(pred, op, op(state)), state) ... #define PP_WHILE2 PP_WHILE2_0 #define PP_WHILE_CHECK_PP_WHILE2_0(p, o, s) 0 #define PP_WHILE2_0(pred, op, state) PP_IF(pred(state), PP_WHILE2_1(pred, op, op(state)), state) #define PP_WHILE2_1(pred, op, state) PP_IF(pred(state), PP_WHILE2_2(pred, op, op(state)), state) ... #define PP_WHILE3 PP_WHILE3_0 #define PP_WHILE_CHECK_PP_WHILE3_0(p, o, s) 0 #define PP_WHILE3_0(pred, op, state) PP_IF(pred(state), PP_WHILE3_1(pred, op, op(state)), state) #define PP_WHILE3_1(pred, op, state) PP_IF(pred(state), PP_WHILE3_2(pred, op, op(state)), state) ... #define PP_WHILE4 PP_WHILE4_0 #define PP_WHILE_CHECK_PP_WHILE4_0(p, o, s) 0 #define PP_WHILE4_0(pred, op, state) PP_IF(pred(state), PP_WHILE4_1(pred, op, op(state)), state) #define PP_WHILE4_1(pred, op, state) PP_IF(pred(state), PP_WHILE4_2(pred, op, op(state)), state) ...
算術演算
インクリメント/デクリメント
#define PP_INC(x) PP_CAT(PP_INC_, x) #define PP_INC_0 1 #define PP_INC_1 2 #define PP_INC_2 3 ... #define PP_INC_9 10 #define PP_INC_10 10 #define PP_DEC(x) PP_CAT(PP_DEC_, x) #define PP_DEC_0 0 #define PP_DEC_1 0 #define PP_DEC_2 1 ... #define PP_DEC_9 8 #define PP_DEC_10 9 PP_INC(0) // => 1 PP_INC(1) // => 2 PP_INC(2) // => 3 PP_INC(10) // => 10 PP_DEC(0) // => 0 PP_DEC(1) // => 0 PP_DEC(2) // => 1 PP_DEC(10) // => 9
結果の値が[0, N]の範囲にクランプされてたほうが扱いやすいのでPP_INC(10) == 10, PP_DEC(0) == 0になるようにしています。
加算
PP_WHILE()とPP_INC(), PP_DEC()を用いて繰り返し数値をインクリメントすることで実現します。
#define PP_ADD(x, y) PP_LIST_GET(PP_WHILE(PP_LIST_HEAD, PP_ADD_O, (x, y)), 1) #define PP_ADD_O(xy) (PP_DEC(PP_LIST_GET(xy, 0)), PP_INC(PP_LIST_GET(xy, 1))) PP_ADD(2, 3) // => 5 PP_ADD(5, 2) // => 7
結果は[0, 10]の範囲に丸められます。
PP_WHILE()を内部で使用するため、別のPP_WHILE_*を使う同様の関数を用意しておくといいです。
#define PP_ADD_A(x, y) PP_LIST_GET(PP_WHILE_A(PP_LIST_HEAD, PP_ADD_O, (x, y)), 1) #define PP_ADD_B(x, y) PP_LIST_GET(PP_WHILE_B(PP_LIST_HEAD, PP_ADD_O, (x, y)), 1) #define PP_ADD_C(x, y) PP_LIST_GET(PP_WHILE_C(PP_LIST_HEAD, PP_ADD_O, (x, y)), 1)
減算
#define PP_SUB(x, y) PP_LIST_GET(PP_WHILE(PP_LIST_HEAD, PP_SUB_O, (y, x)), 1) #define PP_SUB_O(xy) (PP_DEC(PP_LIST_GET(xy, 0)), PP_DEC(PP_LIST_GET(xy, 1))) PP_SUB(2, 3) // => 0 PP_SUB(5, 2) // => 3 #define PP_SUB_A(x, y) PP_LIST_GET(PP_WHILE_A(PP_LIST_HEAD, PP_SUB_O, (y, x)), 1) #define PP_SUB_B(x, y) PP_LIST_GET(PP_WHILE_B(PP_LIST_HEAD, PP_SUB_O, (y, x)), 1) #define PP_SUB_C(x, y) PP_LIST_GET(PP_WHILE_C(PP_LIST_HEAD, PP_SUB_O, (y, x)), 1)
結果は[0, 10]の範囲に丸められます。
同様に繰り返し加減算を行うことで乗算や除算、剰余なども実装できますが割愛します。
さて、これで条件分岐、繰り返しと加減算が扱えるようになったので色々なものが書けます。
(0, 1, 2, ..., n-1)のようなリストを生成したり、
#define PP_IOTA(n) PP_LIST_GET(PP_WHILE(PP_LIST_HEAD, PP_IOTA_O, (n, ())), 1) #define PP_IOTA_O(nl) (PP_DEC(PP_LIST_GET(nl, 0)), PP_LIST_PUSH_FRONT(PP_LIST_GET(nl, 1), PP_DEC(PP_LIST_GET(nl, 0)))) PP_IOTA(0) // => () PP_IOTA(3) // => (0, 1, 2) PP_IOTA(10) // => (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
リストを逆順にしたり、
#define PP_REVERSE(list) PP_LIST_GET(PP_WHILE(PP_REVERSE_P, PP_REVERSE_O, (list, ())), 1) #define PP_REVERSE_P(io) PP_LIST_SIZE(PP_LIST_GET(io, 0)) #define PP_REVERSE_O(io) (PP_LIST_TAIL(PP_LIST_GET(io, 0)), PP_LIST_PUSH_FRONT(PP_LIST_GET(io, 1), PP_LIST_HEAD(PP_LIST_GET(io, 0)))) PP_REVERSE(PP_IOTA(5)) // => (4, 3, 2, 1, 0)
リストの各要素に関数を適用したり。
#define PP_MAP(list, f) PP_LIST_GET(PP_WHILE(PP_MAP_P, PP_MAP_O, (list, f, ())), 2) #define PP_MAP_P(ifo) PP_LIST_SIZE(PP_LIST_GET(ifo, 0)) #define PP_MAP_O(ifo) PP_MAP_O_I ifo #define PP_MAP_O_I(in, f, out) (PP_LIST_TAIL(in), f, PP_LIST_PUSH_BACK(out, f(PP_LIST_HEAD(in)))) #define DOUBLE(x) PP_ADD_A(x, x) PP_MAP(PP_IOTA(4), DOUBLE) // => (0, 2, 4, 6, 8) #define ADD_PREFIX_n(x) PP_CAT(n, x) int PP_LIST_UNPACK(PP_MAP(PP_IOTA(3), ADD_PREFIX_n)); // => int n0, n1, n2;
最後の例とかC++03書く時とか便利だったりするんじゃないでしょうか。
まとめ
以上全コード
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ
プリプロセッサでも様々なことが出来るのがわかったと思います。
手触りとしては再帰呼び出しと算術演算の出来ないSchemeって感じです。
試してみると結構楽しいのでおすすめです(?)
コードはまだ洗練できていませんがFizz Buzzとクイックソートを実装したので供養しておきます。
プリプロセッサFizz Buzzです
— りょがまや (@Ryooooooga) 2018年2月2日
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ https://t.co/buOIonMtXZ pic.twitter.com/0gqmwVqKL9
プリプロセッサ時クイックソートです(Wandboxだとメモリ喰い付くして死にました)
— りょがまや (@Ryooooooga) 2018年2月3日
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ https://t.co/lxs1d3Z95I pic.twitter.com/ImYgWn5s98
疑似再帰一段減らしたら動いた
— りょがまや (@Ryooooooga) 2018年2月3日
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ https://t.co/JLvcY2WGnu
数式微分器の作成 (2) 式木の最適化
前回の記事の続きです。
前回の内容
前回の記事で数式微分器を作成したが、出力が繁雑になった。
結論
今回はそれを解消するために式木に対してより強力な最適化を掛けるようにした結果、出力がこましになった。
前回の反省
前回、出力が繁雑になった原因は主に次の2つです。
割り算ノードを用意しなかった。
前回は必要な式木の型数を小さくするために、割り算に相当するノード型を用意しませんでした。
そのため、
を
のように表現する必要があり、これが出力の式木のノード数が増える原因になっていました。
今回は割り算ノードを用意しました。
式木に対する最適化が甘かった。
前回式木に対して施していた最適化は以下の3項目のみでした。
加算両辺の 0 の削除。
乗算両辺の 1 の削除。
0 を含む乗算の削除。
今回はこれらに加えて式木に対して様々な最適化を行いました。
GitHub - Ryooooooga/Calculator
結果
では前回と同様、を微分してみます。
以下が前回の出力結果です。
((((-1)*sin(x))*sin(x)^{(-1)})+(cos(x)*(sin(x)^{(-1)}*((cos(x)*(-1))*sin(x)^{(-1)}))))
以下が今回の最適化を施したあとの出力です。
(-1-((cos(x)^2)/(sin(x)^2)))
依然として括弧だらけですが、全体的にこざっぱりしました。
なお、二階微分すると爆発します。
-(-(((((((cos(x)^2)*(2*sin(x)))*(sin(x)^2))/cos(x))+(((cos(x)^2)*((sin(x)^2)*(2*cos(x))))/sin(x)))/((sin(x)^2)^2))))
