Emacsのバッファの内部実装について #agile渋谷

井上誠一郎アリエルネットワークCTO

P2P教科書
パーフェクトJava
実践JS サーバサイドJavaScript入門
パーフェクトJavaScript

Software Design Emacsのトラノマキ連載

Emacsのバッファの内部実装ついてなので、教養であり、かつ
日々の役には立たないことを了承してください。

Emacsにとってのバッファ

編集/表示しているテキスト
ファイルの中身をメモリに読み込んだ実体
ウインドウに表示しているテキストに対応するメモリ領域

プログラムからみたバッファ

文字列
内容は変更可能(mutable)
巨大な文字配列でも実装可能

代表的アルゴリズム

リンクトリスト(文字列配列)
ローブ(ツリー、文字列の塊)
ギャップバッファ

Emacsのバッファと言えば「ギャップバッファ」

gap buffer

gap bufferとは

巨大な文字配列 + ギャップ (=隙間)
編集位置(=カーソル位置)に常にギャップを動かす
意外に単純な発想
Emacsの実績を知らなったら、そんな局所最適化は意味があるのかと問いたくなるようなアルゴリズム

ギャップを生成してから文字を挿入(デフォルトのギャップサイズは2000バイト)

ソースコード

buffer.h
buffer.c
insdel.c

/* バッファから参照 */
struct buffer

/* バッファの実際のテキストBufferオブジェクトから参照される */
struct buffer_text

struct buffer
{
  struct buffer_text_own_text;
  struct buffer_text *text;
  ...
}

struct buffer_text {
  unsigned char *beg;
  EMACS_INT gpt;
  EMACS_INT z;
  EMACS_INT gpt_type;
  ...
}

バッファの先頭と末尾

#define BEG (1)
#define BEG_TYPE (BEG)
/* バッファのポイントが1から始まる */

/* バッファ先頭 */
#define BUF_BEG(bug) (BEG)

/* バッファ終端 */
#defin BUF_Z(buf) ((buf)->text->z)

ナローイング

#define NARROWED ((BEGV != BEG) || (ZV != Z))

バイト位置と文字位置

利用者に見えるのは文字位置なので、

- (バッファ内)文字位置
- (バッファ内)バイト位置
- (ギャップバッファ内)実アドレス

の2段階の変換が必要。

ギャップバッファの動作理解には、文字位置からバイト位置への
変換後の世界だけ考えれば充分

文字挿入時の処理

現在ポイントに文字列を挿入
ギャップの移動
ギャップ拡大
ギャップへの文字挿入とポインタ加算処理

ギャップの移動処理

文字挿入位置で場合分け

memcopy vs memmove

普通に考えたらコピーを大量に作っているので
効率悪そう…
ただし、コピーのコストはそんなに大きくない。

Emacs Lispは楽しんで読んだほうがよろし。

by shigemk2

当面は技術的なことしか書かない