VSCodeとZedなどのテキストエディタのテキストバッファの実装について

こんにちは。RevCommでフロントエンドエンジニアしているnobkzと申します。

はじめに

普段みなさんは、どのようなエディタをお使いでしょうか？私は普段から色んなエディタを使っていて、また色んなテキストエディタの実装を見ています。そこで、今回は、テキストエディタに関して重要な、テキストバッファの実装について見ていきましょう。

テキストバッファとは?

そもそもテキストエディタとは何でしょうか？それは、テキストの情報を保持して、ユーザーの指示により内容を表示編集するプログラムです。

テキストバッファとは、　テキストエディタのテキストそのものを保持している場所であり、さまざまな機能が要求されます。

テキストバッファで特に重要な機能といえば、文字参照、挿入、削除です。

つまり、このcharAtやinsert、eraseの効率が重要になってきます。そのため、テキストバッファはこの効率のために、エディタごとに工夫したデータ構造をとっています。今回はそのようなテキストバッファのデータ構造を見ていきましょう。

テキストバッファのデータ構造

インターフェース

今回の記事では、TypeScriptで実装を紹介していきます。まず、簡単にテキストバッファを操作するためのインターフェースを定義してみましょう。今回は、TypeScriptを利用します。

type charAt<Buffer> = (buffer: Buffer, pos: number) => string;
type insert<Buffer> = (buffer: Buffer, pos:number, char: string) => Buffer;
type erase<Buffer> = (buffer: Buffer, pos: number) => Buffer;

簡単なデータ構造によるテキストバッファ

テキストバッファのデータ構造としてまず、簡単なデータ構造である配列やリストについて紹介して検討していきましょう。

配列をBufferにする

まず、簡単にテキストを保持するデータ構造といえば、文字列型でしょう。文字列型は、言語によりますが基本的には文字の配列となっていることが多いでしょう。ここで配列とは、

文字の配列で、実際にTextBufferを実装してみます。JSには、さまざまな配列のメソッドが存在しますが、あえて配列のメソッドを使わず、わかりやすさのため配列の添字によるアクセス、代入によって実装してみます。

まずはデータ型の定義からですね。

type ArrayTextBuffer = {
  data: string[],
  length: number;
  capacity: number;
}

ひとまず、stringの配列としてますが、1文字の配列だと考えてください。ここで、lengthはテキストの長さ、capacityは配列が確保している長さです。上記の図の例でいえば、lengthは7, capacityは10となります。 次に、charAtの実装をしてみましょう

const arrayCharAt: charAt<ArrayTextBuffer> = (buffer, pos) => buffer.data[pos];

文字参照は添字によって直接アクセスでき配列のサイズに依存しないので、計算量はとなります。

次に、挿入と削除を実装してみましょう。以下のようになります。

const arrayInsert: insert<ArrayTextBuffer> = (buffer, pos, char) =>  {
  if(buffer.length === buffer.capacity){
    buffer.capacity *= 2;
    const newData = new Array(buffer.capacity);
    buffer.data.forEach((c,i)=>{newData[i] = c});
    buffer.data = newData;
  }
  for(let i = buffer.length -1; i >= pos; i--){
    buffer.data[i+1] = buffer.data[i];
  }
  buffer.data[pos] = char;
  buffer.length++;
  return buffer;
}

const arrayErase: erase<ArrayTextBuffer> = (buffer, pos) => {
  for(let i = pos; i < buffer.length; i++){
    buffer.data[i] = buffer.data[i+1];
  }
  buffer.length--;
  return buffer;
};

このように、挿入される場所から後の文字を1文字ずらして、文字を代入したり、削除は単純に1文字逆にずらして、実装します。このようにサイズが大きくなると、ずらす量も線形に増えて、計算量は、となります。挿入においては、capacityとlengthが一致すると、バッファが満杯になっているので、バッファを2倍にしていることがわかると思います。

上記により配列をテキストバッファにすると、

• 文字参照は
• 挿入、削除は

となり、小さなテキストだとこの実装で十分ですが、大きなテキストデータの挿入削除は非効率です。ただし、末尾に挿入や削除はになります。これが、後々Gab Bufferや、Piece Treeといったデータ構造に重要になってきます。

双方向リストをテキストバッファにしてみる

双方向リストをテキストバッファにしてみましょう。

データ型の定義は以下の通りになります。

type ListTextBuffer = {
  char: string,
  prev?: ListTextBuffer,
  next?: ListTextBuffer
} | null; // nullで空を表現

まず文字参照の実装をしてみましょう。実際には添え字の範囲外のエラーなどを出すべきですが、今回は簡単な実装に留めています。

const getNode  = (buffer:ListTextBuffer, pos: number) => {
  let node = buffer;
  for(let i = 0; i < pos; i++){
    node = node?.next ?? null;
  }
  return node;
}

const listCharAt : charAt<ListTextBuffer> = (buffer: ListTextBuffer, pos: number) => {
  return getNode(buffer, pos)?.char || "";
}

文字参照は、先頭から順番に参照を得ないといけないため、配列とは対照的に計算量はとなります。

次に挿入と削除を実装しましょう。

const listInsert: insert<ListTextBuffer> = (buffer: ListTextBuffer, pos: number, char: string) => {
  const next = getNode(buffer, pos);
  const prev = next?.prev;
  const node : ListTextBuffer = {
    char,
    next,
    prev
  };
  if(next){
    next.prev = node;
  }
  if(prev){
    prev.next = node;
  }
  return buffer;
}

const listErase: erase<ListTextBuffer> = (buffer: ListTextBuffer, pos: number => {
  const targetNode = getNode(buffer, pos);
  const prev = targetNode?.prev;
  const next = targetNode?.next;
  if(prev){
    prev.next = next;
  }
  next.prev = prev;
  return buffer;
}

getNodeが現状の実装だと、ですが、一旦それを無視してください。すると単につなぎかえるだけなので計算量がとなります。

局所参照性

ところで、テキストエディタには局所参照性があります。局所参照性とは、メモリなどのリソースのアクセスが使用した部分の周辺が繰り返しアクセスされやすいという性質です。カーソル周りで編集がたくさんされやすいと考えればわかりやすいでしょう。テキストエディタの場合は、通常99%はシーケンシャルな参照*1らしいです。このような性質を前提としてテキストエディタは、データ構造を最適化して処理速度の向上が可能になります。

配列とリストの評価

さて、上記のgetNode()の実装は簡単な実装に留めていましたが、実際にやるのであれば、このキャッシュしておくなどして、処理速度を効率化させて行くでしょう。

ここで、配列とリストについて評価をしていくと、配列はシンプルですが挿入や削除がです。一方でリストは文字参照がです。どちらも一長一短があります。局所参照性を考えると若干リストの方が良さそうに思えますが、他にも、実際のところ、1文字につきポインタが2つ必要になったりするのでメモリ使用量が増えたりなどの問題があります。

このような配列やリストの実装をベースとして他のバッファがこのようなパフォーマンスがどのように改善されていくか？みていきましょう。

行をリストで管理する

元々も、配列自体が挿入削除がとなることわかります。このようになる原因はそもそも、テキスト全体一つの配列に詰め込んだからです。そうすると、テキスト全体を一つの配列ではなく区切って小さい単位に分けていこうとなるのは自然な発想となります。Software Tools*2では、テキストエディタのバッファのデータ構造として、行単位で分けて、管理していました。

データ構造の定義は以下の通りになります。

type LineTextBuffer = {
  text: ArrayTextBuffer,
  prev?: LineTextBuffer,
  next?: LineTextBuffer
} | null;

さて、文字参照、挿入削除。実装自体は省略します。(ぜひやってみてください）。文字参照は、Lが行数として、最初はとなりますが、連続で同じ行をアクセスする場合は参照したい行が確定しているためとなります。また、対象行の文字数をlと置くと、挿入削除は、最初は、同じ行を編集するならとなります。配列やリストの管理を比較するとより、高速になったことがわかると思います。

こように行をリストで管理するのは、テキストエディタを実装としてよくみられます。VSCodeの最初の実装はこのような行単位管理による実装でした。ただし現在では後述するPieceTreeによって実装されます

Gap Buffer

行単位でリスト管理する方法がある一方で、より局所参照の最適化を図ったデータ構造があります。それは、Gap Bufferです。Gap Bufferはemacsのテキストのデータ構造として利用されています。Gapバッファは、配列にGapつまり隙間があるデータ構造です。下の図のようはデータ構造になります。

データ構造を定義するなら以下のようになります。

type GapBuffer = {
  data: ArrayTextBuffer,
  capacity: number,
  gapStart: number,
  gapSize: number
}

まず文字参照をみていきましょう。

const gapBufferChartAt : charAt<GapBuffer> = (buffer, pos) => {
  if(pos < buffer.gapStart){
    return buffer.data[pos];
  }else{
    return buffer.data[pos+buffer.gapSize];
  }
}

文字参照は、gapStartの手前であれば、そのままposで参照し、超えていればgapSize+posで参照します。計算量はとなります。

次に挿入や削除を実装してみましょう。動作のイメージは以下の通りです。

実装は以下のようになります。

const gapBufferInsert: insert<GapBuffer> = (buffer, pos, char) => {
  if(buffer.gapSize === 0){
    buffer.gapStart = buffer.capacity;
    buffer.gapSize = buffer.capacity;
    buffer.capacity *= 2;
    const newData = new Array(buffer.capacity);
    buffer.data.forEach((c,i)=>{newData[i] = c});
    buffer.data = newData;
  }

  while(pos !== buffer.gapStart){
    const tmp = buffer.data[buffer.gapStart + buffer.gapSize - 1];
    buffer.data[buffer.gapStart + buffer.gapSize - 1] = buffer.data[buffer.gapStart - 1];
    buffer.data[buffer.gapStart - 1] = tmp;
    buffer.gapStart--;
  }

  buffer.data[pos] = char;
  buffer.gapSize--;
  buffer.gapStart++;
  return buffer;
}


const gapBufferErase: erase<GapBuffer> = (buffer, pos) => {
  while(pos !== buffer.gapStart){
    const tmp = buffer.data[buffer.gapStart + buffer.gapSize - 1];
    buffer.data[buffer.gapStart + buffer.gapSize - 1] = buffer.data[buffer.gapStart - 1];
    buffer.data[buffer.gapStart - 1] = tmp;
    buffer.gapStart--;
  }

  buffer.gapSize++;
  buffer.gapStart--;
  return buffer;
}

さて、挿入は、gapSizeが0であれば、バッファが満杯なので、capacityを2倍にしていることがわかります。ArrayTextBufferの時と一緒ですね。そして、ギャップの最初の位置が一致するまで、ギャップをずらしています。削除の場合も、削除する位置にずらしています。ただし削除する場合は、配列からデータを消さずに、gapの位置だけずらして、文字参照から見えなくしているんですね。後述するデータ構造も、削除は実はデータ自体は保持されていますが、見えなくして削除しているデータ構造になっていることが多いです。さて、計算量について考えてみましょう。もしgapが一番後ろにあって、先頭に文字を挿入するならば、ほとんと配列と同様の操作となりになりますが、一方で、連続してテキストを編集するならば、ギャップをずらす必要がないため、です。

gap bufferは非常に優秀なデータ構造で、これはテキストエディタの局所参照性を最大限に最適化したものと言えるでしょう。

PieceTable

PieceTableは現在のVSCodeで利用されているPiece tree*3の元となったデータ構造です。Pieceとは、断片という意味です。Piece Tableとは断片の表という意味ですが、ちょっと意味がわからないですよね。簡単に言えばPiece Tableとは、テキストの断片、つまり区間を表にしたデータ構造です。先ほどの行単位の管理のイメージを持つ人もいるとは思いますが、何が違うかと言えば、編集区間を表にしたと考えればわかりやすいかもしれません。

簡単にイメージしてみましょう。まず2つの配列バッファがあります。オリジナルバッファと、追記用のバッファです。オリジナルバッファは読み取り専用で、編集元のデータとなります。読み取り専用なので、このバッファ自体は変化しません。そして、追記用のバッファが、末尾に追加するだけのデータバッファで、編集でどんどん追記して大きくなっていきます。その2つのバッファとは別に、それぞれのテキストの区間を表す表があります。この区間の表は、順番があり、実際のテキストの順になるように作られています。

イメージとしては以下の通りです。

このイメージだと「吾輩はねLISPがすきである」という文章になります。オリジナルバッファの3番目の「猫」は表にないので、文章には入ってないことに注意してください。

さてデータ型を定義してみましょう。

type PieceTable = {
  originalData: ArrayTextBuffer,
  additionalData: ArrayTextBuffer,
  table: Piece[]
}

// startとendは閉区間にする
type Piece = {
    bufferType : "original" | "additional",
    start : number,
    end: number 
}

さて文字参照を実装してみましょう。

const pieceTableCharAt : charAt<PieceTable> = (buffer, pos) => {
  const {offset, piece} = localPiece(buffer, pos);
  // pieceが見つからなかったらひとまず空文字を返しておく
  if(piece == null){
    return "";
  }
  return piece.bufferType == "original" ?
  arrayCharAt(buffer.originalData, piece.start + offset)
  : arrayCharAt(buffer.additinonalData, piece.start + offset);
}

// 閉区間なので長さは差分を取って+1
const pieceLen = (p: Piece) => p.end - p.start + 1;

// 位置から、その位置を含むPieceとoffsetを取得する
const localPiece = (
  buffer: PieceTable,
  pos: number,
): { piece: Piece | null; pieceIndex: number; offset: number } => {
  if (pos < 0) return { piece: null, pieceIndex: -1, offset: 0 };

  let rem = pos;
  for (let i = 0; i < buffer.table.length; i++) {
    const piece = buffer.table[i];
    const len = pieceLen(piece);
    if (rem < len) return { piece, pieceIndex: i, offset: rem };
    rem -= len;
  }
  //　空テーブルの時など
  return { piece: null, pieceIndex: -1, offset: 0 };
};

Pieceの区間の処理をしないといけない分複雑になりましたね。さて、計算量はPieceの数に依存するので、Piecesの数を単純にPと置いてとなります。ただし、この実装には含んでいませんが、部分を連続で参照する場合、発見したPieceを再活用できるためになります。

挿入削除を実装してみましょう。まず挿入のイメージですが以下になります。

つまり、編集したいPieceを発見して、分割して、その間に新しいPieceを挿入するということです。実装してみましょう。

const pieceTableInsert: insert<PieceTable> = (buffer, pos, char) => {
  // 追加バッファ末尾に1文字追加
  const addPos = buffer.additionalData.length; // 追加開始位置
  arrayInsert(buffer.additionalData, addPos, char);

  const newPiece: Piece = { bufferType: "additional", start: addPos, end: addPos };
  const {offset, piece, pieceIndex} = localPiece(buffer, pos);

   if (offset === 0) {
    // piece の先頭に挿入 = その前に newPiece を入れる
    buffer.table.splice(pieceIndex, 0, newPiece);
    return buffer;
  }

  // pieceが見つからなかったらひとまず何もしないでおく
  if(piece == null){
    return buffer;
  }

  // piece を split して間に newPiece を挿入
  // piece: [start .. end] (closed)
  // left:  [start .. start+offset-1]
  // right: [start+offset .. end]
  const left: Piece = {
    bufferType: piece.bufferType,
    start: piece.start,
    end: piece.start + offset - 1,
  };
  const right: Piece = {
    bufferType: piece.bufferType,
    start: piece.start + offset,
    end: piece.end,
  };

 buffer.table.splice(pieceIndex, 1, left, newPiece, right);
 return buffer;
}

このように挿入の場合は、addtionalBufferに追加して、Pieceを分割して、新しいPieceを挿入すれば良いわけです。削除の場合は実装しませんが、こちらもPieceを発見して、分割、そして、Pieceのstartやendの位置を単にずらせばいいのですよね。Pieceが発見されてない場合は、ですが、Pieceが発見されていて、newPieceに連続で編集する場合は、追記バッファの末尾の追加と、newPieceのendを増やせばいいだけになるのでになります。削除も同様です。(削除は実装しないのでチャレンジしてみてください。）

上記の実装は簡単な実装であり、本来であれば、Pieceを合併したりする処理があるのですが、長くなるので割愛します。

Piece Tree

さてVSCodeでは、Pieceの管理を、連続的な表ではなく、赤黒木で持つようにしました。その理由として、上記のPiece Tableの課題点として、編集が増えれば増えるほど、Pieceの数が増大し、探索がボトルネックになってきます。そこで、VSCodeでは、連続したTableとして持つのではなく、赤黒木としてPieceを持つようにしました。これがPiece Treeです。そのおかげで、文字参照の計算量はとなりました。

Piece Treeの実装の方はやりません。（チャレンジしてみてもいいでしょう）

追記型の利点

Piece TableやPiece Treeは、このような性能のみならず、追記型であるがゆえに、編集履歴の管理にも強いと言う側面があります。なぜなら、バッファの追記のみで構成されるため、履歴管理には基本的には、Pieceの変更だけ追えば良いからです。

Rope

さて、最近私はZed*4を利用しています。Zedは共同編集やAIエディタなどを想定して、複数のユーザーから参照されると言う要件がでてきます。そのため、テキストバッファにRopeを採用しています。

RopeはPiece Treeと同様に大きな文字列を小さな断片に分け、それを木構造で保持するデータ構造です。Ropeは末端の葉は、文字の断片を表しますが、葉以外のノードは左部分木の文字数を示しています。イメージで言うと以下の通りです。

データ構造としては以下のようになります。今回、葉の設計がPiece Treeと同様の設計にしています。（一般的には、stringとして持つことが多いです。）

type RopeNode = {
  kind: "node";
  weight: number;
  left: RopeNode | RopeLeaf;
  right: RopeNode | RopeLeaf;
};

type RopeLeaf = {
  kind: "leaf";
  bufferType: "original" | "additional";
  start: number; // closed
  end: number;   // closed
};


type RopeBuffer = {
  original: ArrayTextBuffer;
  additional: ArrayTextBuffer;
  root: (RopeNode | RopeLeaf) | null;
};

文字参照について簡単に実装してみましょう。動作イメージは以下の通りになります。

つまり、ノードと比較して、小さいなら左、大きいなら、右に進み、右に進むときに、調べる文字数を引けばいいのですね。

// 型ガード
const isLeaf = (x: RopeNode | RopeLeaf): x is RopeLeaf => x.kind === "leaf";

const leafLen = (leaf: RopeLeaf) => leaf.end - leaf.start + 1;

const ropeCharAt: charAt<RopeBuffer> = (buf, pos) => {
  if (buf.root == null) return "";
  if (pos < 0) return "";

  let node: RopeNode | RopeLeaf = buf.root;
  let i = pos;

  while (true) {
    if (isLeaf(node)) {
      if (i >= leafLen(node)) return "";
      const idx = node.start + i;
      return node.bufferType === "original"
        ? arrayCharAt(buf.original, idx)
        : arrayCharAt(buf.additional, idx);
    }

    // node は RopeNode に 좁まってる
    if (i < node.weight) {
      node = node.left;
    } else {
      i -= node.weight;
      node = node.right;
    }
  }
};

木はバランスしている前提ならば、文字参照は高さに比例して （L は leaf 数）になります。

次に挿入や削除を見ていきましょう。Ropeの木の挿入と削除は、基本は split（分割） と concat（連結） の2つに落とし込めます。

• split(tree, pos) : pos で木を左右の Rope に分割する
• concat(left, right) : 2つの Rope を連結する（新しいノードを作る）

これができると、挿入は

1. (L, R) = split(tree, pos)
2. 追加バッファ末尾に char を追加し、それを指す leaf を作る
3. tree' = concat(concat(L, newLeaf), R)

削除は

1. (A, B) = split(tree, pos)
2. (trash, C) = split(B, 1) （先頭 1 文字を落とす）
3. tree' = concat(A, C)

で表現できます。なので、今回はconcatとsplitのみ実装してみます。

const len = (t: (RopeNode | RopeLeaf) | null): number => {
  if (t == null) return 0;
  if (isLeaf(t)) return leafLen(t);
  return t.weight + len(t.right);
};

const concat = (
  a: (RopeNode | RopeLeaf) | null,
  b: (RopeNode | RopeLeaf) | null,
): (RopeNode | RopeLeaf) | null => {
  if (a == null) return b;
  if (b == null) return a;
  return { kind: "node", weight: len(a), left: a, right: b };
};

// split(t, pos) => [0..pos-1], [pos..end]
const split = (
  t: (RopeNode | RopeLeaf) | null,
  pos: number,
): [(RopeNode | RopeLeaf) | null, (RopeNode | RopeLeaf) | null] => {
  if (t == null) return [null, null];

  if (pos <= 0) return [null, t];
  const tlen = len(t);
  if (pos >= tlen) return [t, null];

  if (isLeaf(t)) {
    const leftLen = pos;
    const leftLeaf: RopeLeaf = {
      kind: "leaf",
      bufferType: t.bufferType,
      start: t.start,
      end: t.start + leftLen - 1,
    };
    const rightLeaf: RopeLeaf = {
      kind: "leaf",
      bufferType: t.bufferType,
      start: t.start + leftLen,
      end: t.end,
    };
    return [leftLeaf, rightLeaf];
  }

  if (pos < t.weight) {
    const [l, r] = split(t.left, pos);
    return [l, concat(r, t.right)];
  } else {
    const [l, r] = split(t.right, pos - t.weight);
    return [concat(t.left, l), r];
  }
};

これで挿入や削除は以下のように実装できます。

const ropeInsert: insert<RopeBuffer> = (buf, pos, char) => {
  // 追加バッファ末尾に 1 文字追加
  const addPos = buf.additional.length;
  arrayInsert(buf.additional, addPos, char);

  const newLeaf: RopeLeaf = {
　　... 略
  };

  const [L, R] = split(buf.tree, pos);
  return { tree: concat(concat(L, newLeaf), R)};
};

const ropeErase: erase<RopeBuffer> = (buf, pos) => {
  const [A, B] = split(buf.tree, pos);
  const [, C] = split(B, 1); // 先頭 1 文字を捨てる
  return {tree: concat(A,C)};
};

注意点として、今回は二分木の平衡を考慮していない実装です。実際にはそれなりに複雑になります。 木がバランスしている前提なら、こちらの計算量も、となります。今回の実装には含まれていませんが、同じLeafに連続で編集する限り実装によりますが計算量は末端の葉のサイズをlと置いてとなります。

Ropeと共同編集の容易性

さて、Ropeは、PieceTreeやGap Bufferと比較すると若干性能が悪いように見えます。しかしながら、Ropeは性能よりも共同編集に主眼を置いています。上記のデータ構造は、挿入も削除もよくみてみると、元の木のデータ構造を直接編集していません。concatは単に元ある木の結合ですし、splitも単に分割するだけで、直接木のに変更を加えていません。そして、削除や挿入はこのconcatやsplitを組み合わせて元にある木から、新しい木を構築しているだけなのです。

挿入と削除のイメージは以下になります。

つまり、Ropeは更新のたびに全体をコピーせず、変更が必要な部分だけを新しく作り、残りは共有するデータ構造になります。つまり、元のテキストを保持したまま、変更後のテキストを構築することができ、また、並行編集などを考えると、並行して複数のバージョンが持ちやすく、その結果、共同編集などの機能に強いデータ構造になっています。

さらに、Piece Tableと同様に履歴操作にも強いデータ構造になっていることがわかるかと思います。

まとめ

本記事では、テキストエディタの内部で使われるテキストバッファのデータ構造を、文字参照（charAt）・挿入（insert）・削除（erase）という観点で見てきました。

• 配列: charAt は常に O(1)。ただし insert/erase は後ろをずらすので O(N)。 速い参照の代償として編集が重い。
• リスト: insert/erase は繋ぎ替え自体は O(1) だが、位置まで行く探索が O(N)。 編集は軽く“できる”が、そもそも目的地に辿り着くのが遅い。
• 行単位管理: 「全文字を1本に持つ」せいで O(N) になるなら、分割して局所化する。 → 参照・編集が “行数 + 行内” に落ち、現実の編集（同じ行を触り続ける）で効く。
• Gap Buffer: 局所参照性（カーソル近傍を連続編集）を前提に、“そこだけO(1)” を作る。ギャップ移動は最悪 O(N) だが、連続編集は実質 O(1)。
• Piece Table / Piece Tree: 文字列本体を動かさず、編集を“参照の断片（Piece）”として表現する。Piece が増えると探索が効くので、表（配列）→ 木（赤黒木）で O(P) → O(log P) にする（VSCode）。
• Rope: 断片＋木で、split/concat に編集を還元する。変更は「必要な経路だけ作り直し、残りは共有」になり、履歴・複数ビュー・並行操作に自然に強い。

さまざまなテキストエディタのテキストバッファのデータ構造についてみていきました。普段、使っているエディタがどのような実装になっているかあまり気にしたことない方もたくさんいらっしゃるかもしれませんが、このようにさまざまなデータ構造の工夫がありとても面白いものとなっています。

また、ここまで書いてきましたが、テキストエディタの実装の話題ままだまだたくさんあり、たとえば、改行の管理や、カーソルの移動や、範囲選択、スクロール、折り返し、検索、共同編集などさまざまなことについてまだまだ深掘りできるところがあります。是非とも普段お使いのエディタについて探索してはいかがでしょうか？

*1:https://www.cs.unm.edu/~crowley/papers/sds.pdf

*2: P.J. Kernighan, Brian W. Plauger Software Tools 1976 Addison-Wesley Professional 020103669X

*3:https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation

*4:https://zed.dev/