vi っぽいテキストエディタを 120 行で作る

ae - IOCCC 91 Best Utility を獲得したエディタ

 実を言うと 120 行も必要なく、28 行で書けちゃったりするのですが ( “Best Utility IOCCC 91” https://github.com/SirWumpus/ioccc-ae/tree/master/91 )、 それはさておき、本文書では現代風にこのプログラムを書き直してみます。 古文の現代語訳みたいなものだと思っていただければ幸いです。

 ちなみに IOCCC 91 で Best Utility 部門を受賞した全 28 行のプログラムは、このようなソースコードだったそうです(参考までに紹介しておきます):

#include <ctype.h>
#include <curses.h>
#define T isspace(*(t=Z(p)))&&
#define V return
#define _ while
int d,i,j,m,n,p,q,x,y;char*c,b[BUF],*f,*g=b,*h,k[]="hjklHJKL[]tbixWRQ",*t;
char*Z(a){if(a<0)V b;V b+a+(b+a<g?0:h-g);}P(a)char*a;{V
a-b-(a<h?0:h-g);}S(){p=0;}bf(){n=p=P(c);}Q(){q=1;}C(){clear();Y();}
G(){t=Z(p);_(t<g)*--h= *--g;_(h<t)*g++= *h++;p=P(h);}B(){_(!T b<t)--p;_(T
b<t)--p;}M(a){_(b<(t=Z(--a))&&*t-'\n');V
b<t?++a:0;}N(a){_((t=Z(a++))<c&&*t-'\n');V
t<c?a:P(c);}A(a,j){i=0;_((t=Z(a))<c&&*t-'\n'&&i<j){i+= *t-'\t'?1:8-(i&7);++a;}V
a;}L(){0<p&&--p;}R(){p<P(c)&&++p;}U(){p=A(M(M(p)-1),x);}
D(){p=A(N(p),x);}H(){p=M(p);}E(){p=N(p);L();}
J(){m=p=M(n-1);_(0<y--)D();n=P(c);}K(){j=d;_(0<--j)m=M(m-1),U();}
I(){G();_((j=getch())-'\f'){if(j-'\b')g-h&&(*g++=j-'\r'?j:'\n');else
b<g&&--g;p=P(h);Y();}}X(){G();p=h<c?P(++h):p;}
F(){j=p;p=0;G();write(i=creat(f,MODE),h,(int)(c-h));close(i);p=j;}W(){_(!T
t<c)++p;_(T
t<c)++p;}int(*z[])()={L,D,U,R,B,J,K,W,H,E,S,bf,I,X,F,C,Q,G};
Y(){m=p<m?M(p):m;if(n<=p){m=N(p);i=m-P(c)?d:d-2;_(0<i--)m=M(m-1);}
move(0,0);i=j=0;n=m;_(1){p-n||(y=i,x=j);t=Z(n);if(d<=i||c<=t)break;
if(*t-'\r')addch(*t),j+= *t-'\t'?1:8-(j&7);if(*t=='\n'||COLS<=j)
++i,j=0;++n;}clrtobot();++i<d&&mvaddstr(i,0,"<< EOF >>");move(y,x);
refresh();}main(u,v)char**v;{h=c=b+BUF;if(u<2)V
2;initscr();d=LINES;raw();noecho();idlok(stdscr,1);if(0<(i=open(f= *++v,0))){
g+=read(i,b,BUF);g=g<b?b:g;close(i);}S();_(!q){Y();i=0;j=getch();
_(k[i]&&j-k[i])++i;(*z[i])();}endwin();V 0;}

圧倒されますね。行数を減らすための細工がされているとはいえ、たったこれだけのコードで vi ライクなフルスクリーンテキストエディタが実装されているのは 2019 年の現在においても驚きではないでしょうか。

 このエディタは Anthony’s Editor と呼ばれており、ae などと略されたりしています。挿入モードと移動モードがあり、hjkl でカーソル移動でき、i で挿入モード、x で文字削除、行頭・行末への移動や、ページアップ・ページダウンなども実現されています。

 上に示したコードは行数を短くするために、かなり無理をしていますが、同梱されているネタばらし(spoiler)によると 360 行のコードになるようです( spoiler/ae.c )。古(いにしえ)の K&R スタイルで書かれているため、ANSI 以降のスタイルに比べると若干行数が多くなるかと思いますが、300 行強で vi ライクなフルスクリーンエディタが実装できているのは驚異です。

2019 年の Anthony’s Editor (ae2019)

 このように、魅力満載の ae ですが、IOCCC 91 から 28 年。 C++ もずいぶんと進化してきたように感じます。 そのため、本文書では C++ の機能を用いて 120 行で ae を書き直してみようと思います。

 ae では固定長の穴あきバッファを用いていたため、 取扱可能なファイルサイズに上限がありました。 今回作成する ae2019 では、std::vector を用いて、 ファイルサイズの上限および穴あきバッファに関連するコードの削減を目指してみます。 また、オリジナルの ae.c では、 入力されたキー毎に起動される関数が func という配列に格納されていますが、 これも unordered_map を用いて、できるだけ簡単にコーディングするようにしてみました。

 システム的な変更点は以上のみであり、逆に言えばそれ以外の部分は 28 年前のオリジナル版を踏襲していることとなります。Anthony の設計が良いことの証でもあるかもしれません。

 参考までに、Anthony’s Editor のバッファ構造について少し説明しておくと、カーソルのある場所=文字が挿入される可能性のある場所を穴の状態にしておくバッファです。バッファの先頭からカーソルの前までと、バッファの末尾からカーソルの直後までにテキストが詰まっている状態となります。この構造により、文字が追加される場合でも、カーソル以降の文字データをごっそりと移動する必要はありません(穴あきバッファの構造については、spoiler ディレクトリにある ae.c のコメントを読むと、より理解が進むかと思います)。

 話を戻して、まずは、以下に今回作成した全ソースコードを示します。その後、このコードについて簡単な解説を行います。コンパイルは、g++ -std=c++1z ae2019.cpp -lcurses とすれば大丈夫かと思います(macOS では実行形式が正常に作られることを確認しております)。

// ae2019.cpp	Anthony's Editor 2019.
// compile: g++ -std=c++1z ae2019.cpp -lcurses
#include <curses.h>
#include <fstream>
#include <vector>
#include <unordered_map>

using namespace std;
enum { kESC=27,kBS=8,kDEL=127,kCtrlD=4,kCtrlU=21,kCtrlR=18,kCtrlS=19,kCtrlQ=17, };
const char *gFileName;
vector<char> gBuf;
bool gDone=false;
int gIndex=0 /* offset of cursor pos */,gPageStart=0,gPageEnd=0;
int gCol,gRow;

int lineTop(const int inOffset) {
	int offset=inOffset-1;
	while(offset>=0 && gBuf[offset]!='\n') { offset--; }
	return offset<=0 ? 0 : ++offset;
}
int nextLineTop(const int inOffset) {
	int offset=inOffset;
	while(offset<gBuf.size() && gBuf[offset++]!='\n') { /* empty */ }
	return offset<gBuf.size() ? offset : gBuf.size()-1;
}

int adjust(const int inOffset,const int inCol) {
	int offset=inOffset;
	for(int i=0; offset<gBuf.size() && gBuf[offset]!='\n' && i<inCol; offset++) {
		i += gBuf[offset]=='\t' ? 8-(i&7) : 1;
	}
	return offset;
}

void display() {
	if(gIndex<gPageStart) { gPageStart=lineTop(gIndex); }
	if(gPageEnd<=gIndex) {
		gPageStart=nextLineTop(gIndex);
		int n = gPageStart==gBuf.size()-1 ? LINES-2 : LINES;
		for(int i=0; i<n; i++) { gPageStart=lineTop(gPageStart-1); }
	}
	move(0,0);
	int i=0, j=0;
	gPageEnd=gPageStart;
	for(auto p=gBuf.begin()+gPageEnd; /*empty */; gPageEnd++,p++) {
		if(gIndex==gPageEnd) { gRow=i; gCol=j; }	// update cursor pos.
		if(LINES<=i || gBuf.size()<=gPageEnd) { break; }
		if(*p!='\r') { addch(*p); j += *p=='\t' ? 8-(j&7) : 1; }
		if(*p=='\n' || COLS<=j) { ++i; j=0; }
	}
	clrtobot();
	if(++i<LINES) { mvaddstr(i,0,"<< EOF >>"); }
	move(gRow,gCol);
	refresh();
}

void left() { if(0<gIndex) { --gIndex; } }
void right(){ if(gIndex<gBuf.size()) { ++gIndex; }}
void up()   { gIndex=adjust(lineTop(lineTop(gIndex)-1),gCol); }
void down() { gIndex=adjust(nextLineTop(gIndex),gCol); }
void lineBegin() { gIndex=lineTop(gIndex); }
void lineEnd()	 { gIndex=nextLineTop(gIndex); left(); }
void top()  	 { gIndex=0; }
void bottom()	 { gIndex=gBuf.size()-1; }
void del()    { if(gIndex<gBuf.size()-1) { gBuf.erase(gBuf.begin()+gIndex); } }
void quit()   { gDone=true; }
void redraw() { clear(); display(); }

static void insert() {
	for(int ch; (ch=getch())!=kESC; display()) { 
		if(gIndex>0 && (ch==kBS || ch==kDEL)) {
			--gIndex; gBuf.erase(gBuf.begin()+gIndex);
		} else {
			gBuf.insert(gBuf.begin()+gIndex,ch=='\r' ? '\n' : ch);
			gIndex++;
		}
	}
}

void wordLeft() {
	while(!isspace(gBuf[gIndex]) && 0<gIndex) { --gIndex; }
	while( isspace(gBuf[gIndex]) && 0<gIndex) { --gIndex; } 
}
void wordRight() {
	while(!isspace(gBuf[gIndex]) && gIndex<gBuf.size()) { ++gIndex; }
	while( isspace(gBuf[gIndex]) && gIndex<gBuf.size()) { ++gIndex; }
}
void pageDown() {
	gPageStart=gIndex=lineTop(gPageEnd-1);
	while(0<gRow--) { down(); }
	gPageEnd=gBuf.size()-1;
}
void pageUp() { for(int i=LINES; 0<--i; up()) { gPageStart=lineTop(gPageStart-1); } }

void save() {
	ofstream ofs(gFileName,ios::binary);
	ostream_iterator<char> output_iterator(ofs);
    copy(gBuf.begin(),gBuf.end(),output_iterator);
}

unordered_map<char,void(*)()> gAction={
	{'h',left},{'l',right},{'k',up},{'j',down},
	{'b',wordLeft},{'w',wordRight},{kCtrlD,pageDown},{kCtrlU,pageUp},
	{'0',lineBegin},{'$',lineEnd},{'t',top},{'G',bottom},
	{'i',insert},{'x',del},{kCtrlQ,quit},{kCtrlR,redraw},{kCtrlS,save},
};

int main(int argc,char **argv) {
	if(argc<2) { return 2; }
	initscr(); raw(); noecho(); idlok(stdscr,true);	// init screen.
	gFileName=argv[1]; ifstream ifs(gFileName,ios::binary);
	gBuf.assign(istreambuf_iterator<char>(ifs),istreambuf_iterator<char>());
	while(!gDone) {
		display();
		char ch=getch(); if(gAction.count(ch)>0) { gAction[ch](); }
	}
	endwin();
	return 0;
}

コード解説

テキストデータ格納エリア

 オリジナル版では、テキストデータは char buf[BUF] という固定長の char の配列に格納されていました。今回作成したバージョンでは vector gBuf という char の vector にてテキストデータを格納しています。

 vector を用いることにより、文字の挿入や削除なども vector にすべて丸投げすることが可能となります。結果として、オリジナルであった穴あきバッファに関する pos() や ptr() といった関数を廃止できました。

状態変数

 エディタを終了するか否かを司るのは bool gDone という変数です。これはオリジナルでは int done として定義されていました。今回はグローバル変数であることを示すために、小文字の接頭語 g を付した gDone という名前に変更していますが、この変数の本質的な役割は変わっていません。

 オリジナルでは、int index にて、現在カーソルがある位置の文字のバッファ(buf)におけるインデックス値を保持していました。ae2019 では int gIndex という値にて、vector 型の gBuf における位置を保持しています。

 gPageStart と gPageEnd は、それぞれ現在画面に表示されているテキストのバッファ上の位置を示す変数です。これはオリジナルではそれぞれ int page,epage として定義されていました。今回はより分かりやすい名前にするため page start および page end という名前に変更しています。

 int gCol,gRow についてはオリジナルの int col,row と全く同じで、画面上にあるカーソルの座標を保持しています(col が X 軸に関するもので、row が y 軸方向に関するものです)。

 オリジナルに存在した、char *ebuf,*gap,*egap については穴あきバッファやバッファの最後を示すための情報であるため、vector を採用した本バージョンでは不要です。そのため、ae2019 ではこれらの変数は存在しません(使わなくても gBuf の機能にて実現できています)。

 char *fileame は char *fileName という名前に変更しています(私の好みにて変更しただけです)。

 オリジナルで存在した char key[] と void (func[])() = { … } は unordered_map<char,void()()> gAction にて吸収されました。オリジナルでは、key に入力された文字と同じ文字が存在するかを調査し、もし存在したならばそれと同じ位置にある func 配列に格納されている関数を呼び出していました。今回は gAction に、入力された文字と同じキーが格納されているかを count() メソッドにて調査し、存在するならば、その文字をキーとして関数へのポインタを取得&呼び出し、というコードに変更しています。

オリジナル(これが):

i = 0;
ch = getch();
while (key[i] != '\0' && ch != key[i])
    ++i;
(*func[i])();

変更後(こうなる):

char ch=getch();
if(gAction.count(ch)>0) { gAction[ch](); }

連想配列のおかげで少しばかり簡潔に書けています(ありがたや)。

関数

 ae では、大きく分けると、エディタのコマンドとして呼び出される関数と、それらにて利用される下請け関数に大別されます。どちらの関数においても、その本質的な部分は変更されていません(オリジナルと同じ)。

下請け関数

 まず下請け関数について説明します。このグループに属する関数には、lineTop(),nextLineTop(),adjust(),display() があります(lineTop と nextLineTop はそれぞれオリジナルでは prevline と nextline という関数名です)。

 lineTop 関数はテキストバッファ内(つまり gBuf における)オフセット値を引数として受け取り、そのオフセット値に対応する文字が存在する行頭のオフセット値を返します。オリジナルでは prevline でしたが、実際の動作を表すため、このような名前に変更しています。

 単に行頭に移動するだけなら gIndex=lineTop(gIndex) というコードにて処理は完了します。実際、0 というキーバインドを持つ、行頭への移動処理 lineBegin() は以下のように実装されています:

void lineBegin() { gIndex=lineTop(gIndex); }

 同様に nextLineTop は、引数として渡されたオフセット値にカーソルがあるとして、その次の行の行頭を示すオフセット値を返します。

 adjust 関数は、行頭を示すオフセット値と、現在の桁情報(カーソルの X 座標)を引数にとり、行末もしくは指定されたカーソルの X 座標値までのオフセット値を返す関数です。先程説明した nextLineTop 関数と組み合わせて、adjust(nextLineTop(gIndex),gCol) とすると、一行下を示すオフセット値が得られます。

実際、一行下へ移動する関数 down() は次のように実装されています:

void down() { gIndex=adjust(nextLineTop(gIndex),gCol); }

コマンドを司る関数

 関数 left(),right(),up(),down() はそれぞれ移動モードにおいてキー hlkj にて呼び出される関数です。関数名もオリジナルと同じです。処理の内容は、gIndex に関する調整処理のみです。

 up() および down() では、必要に応じてスクロールアップやダウンがが発生します。そのため、表示しているページに関する情報を保持する gPageStart と gPageEnd の更新処理も必要になるのではないかと思ってしまいますが、これらは描画を司る display 関数にて処理しています。

 表示に関しては画面表示に特化すべき、というのが現代的な考え方だと思いますが、表示する時にページ関連の情報を更新するという設計のおかげで、カーソルの移動処理はかなり単純になっています。down は既に示していますので、今回は一行上に移動する up 関数について説明します。

lineTop(gIndex) にて現在カーソルがある行の行頭のオフセット値を得ることができます。この値から 1 を引くと、ひとつ上の行の行末についてのオフセット値を得ます。このオフセット値に対し、再度 lineTop 関数を適用すると、1 行上の行頭のオフセット値を得ることができます。得られたオフセット値に対し adjust 関数を適用すれば、カーソルを上に移動する処理は完了します。

 文章で説明するよりも、実際にコードを見てみた方が分かりやすいかもしれませんので、以下に up 関数の定義を示します:

void up()   { gIndex=adjust(lineTop(lineTop(gIndex)-1),gCol); }

 ページダウンやページアップはさすがに gPageStart と gPageEnd とは無縁でいられなかったようです。これらを司る処理はそれぞれ pageUp() と pageDown() にて記述されています。現在の行の情報 (gRow) や、現在のターミナルの行数などを参照にしながら down() や後述する lineTop() 関数などを呼んでいます。

void pageDown() {
    gPageStart=gIndex=lineTop(gPageEnd-1);
    while(0<gRow--) { down(); }
    gPageEnd=gBuf.size()-1;
}
void pageUp() { for(int i=LINES; 0<--i; up()) { gPageStart=lineTop(gPageStart-1); } }

その他 - キーバインドの変更

 私自身は vim ユーザーですので、どうせなら vim にできるだけ似せた方が楽しいと思い、キーバインドを変更しております。オリジナルではワード単位の移動やページアップおよびダウンは大文字の HJKL を使用していましたが、本作 ae2019 では w,b,Ctrl-U,Ctrl-D とし vim の操作方法に合わせています。行頭や行末への移動もオリジナルでは [ と ] だったのですが、これも 0 と $ に変更しています。

 ae では 2 ストロークコマンドはサポートしていないので、テキストファイルの先頭に移動するコマンドはオリジナルと同様に t を使用しています。しかし、テキストファイルの最後への移動は G に変更し、こちらも vim に合わせています。

 挿入モードおよび 1 文字削除はオリジナルでも vim と同様 i と x でしたので、これは変更せずそのままのキーバインドを採用しています。

おわりに

 120 行という小規模なプログラムであれば、読んでみる気になるかと思います。オリジナル版の設計部分については、できるだけ尊重するようにしたつもりですので、より現代的なコードにて、ae という名作を味わってもらえれば幸いです。

 ae は、簡単に拡張できるよう設計されています。これを元にオリジナルなエディタを作ってみるのも楽しかと思います。現状では、どのモードにいるのか分かりづらいので、ステータス行を実装するのも良いかと思います(ただ、マルチバイト文字への対応は簡単ではないかもしれませんが…)。本コードをベースとして、様々な改造が考えられると思いますので、教育や趣味に活用していただければ幸いです。