TATEditor内で使っている文字列クラスと編集履歴の実装についてです。

1. 文字列クラス（概要）

1.1 内部表現

TATEditorにおける文字列クラスではUTF-16を採用しています。
これは

偽UTF-32や偽UTF-8のように謎のサロゲートペアが紛れ込むことがない
- UTF-16ならBMP外のコードポイントはすべてサロゲートペアになる
- サロゲートペアというのは16bitのコードポイントふたつで16bitでは収まらないコードポイントを表現するもの
文字数カウントはUTF-32のコードポイントと一致しない
- 改行の\r\nとか、異体字セレクタとか
- これらと同じ枠組みでサロゲートペアを扱った方が楽
メモリ使用量的にもいい感じ
- あまり気にしなくてもいいけど
ICUというUnicodeのライブラリも内部表現にUTF-16を採用している
- これは後付けの理由ですね

1.2 アウトライン構造

行の先頭に指定の文字を置くことで、アウトラインの次のノードであるということを宣言できる仕様になっています。
つまり先頭の文字を.であるということにした場合、

a ←先頭行からは第0ノード
.b ←ここから第1ノード
c
d
.e ←ここから第2ノード
..e ←ここから第3ノード

というようなイメージです。
ただし、ここで

行
- 最終文字以外に改行コードを含まない最大の文字列
- ただし、\r\nは1文字として扱う
ノード
- 先頭行以外に行頭に指定文字を含まない最大の単連結な行の範囲全体

1.3 座標系

TATEditorの文字列クラスでは、通常のインデックスでのアクセスの他にも以下のような指定で文字へアクセスすることができます。

テキスト内でのUTF-16でのインデックス ∈ ℕ≥₀
(テキスト内での行, 行内のUTF-16でのインデックス) ∈ ℕ≥₀²
(テキスト内でのノード, ノード内での行, 行内のUTF-16でのインデックス) ∈ ℕ≥₀³

なお、ここでは扱うの文字列の塊（テキストファイルなど）をテキストと呼んでいます。
このときアクセスにかかる時間は概ね対数時間になっています。

また、以下のような座標を与えることで、ノードや行へのアクセスも可能です。

行へのアクセス
- テキスト内での行 ∈ ℕ≥₀
- (テキスト内でのノード, ノード内での行) ∈ ℕ≥₀×ℕ≥₀
ノードへのアクセス
- テキスト内でのノード ∈ ℕ≥₀

アクセスした先のノードや行も、またひとつの文字列クラスとして振る舞います。

1.4 編集

また、編集については

テキスト内の指定された範囲の文字列を与えられた文字列で置き換える
- 範囲は上の3つの座標系のいずれかで始点と終点を指定できます
テキスト内の指定された範囲の行を与えられた行の配列で置き換える
- 範囲は次の2つの座標系のいずれかで始点と終点が指定されます
  - テキスト内での行∈ℕ≥₀
  - (テキスト内でのノード, ノード内での行)∈ℕ≥₀²
テキスト内の指定された範囲のノードを与えられたノードの配列で置き換える
- 範囲はテキスト内でのノード≥₀で始点と終点が指定されます
テキスト内の指定された単連結な文字列を指定された座標へ移動する
テキスト内の指定された単連結な行の配列を指定された座標へ移動する
テキスト内の指定された単連結なノードの配列を指定された座標へ移動する

といったことができるようになっています。
また、文字列クラスは編集履歴を持つことができますが、こちらについては後ほど詳しく説明します。

2. 文字列クラス（実装）

さて、上で説明した文字列クラスは以下のようなクラスによって構成されています。

2.1 文字列クラス（擬行）

これは最終文字以外に改行コードを持たない文字列＝メモリを管理する文字列クラスです。
（最大の文字列ではないことに注意が必要です）
このクラスが1つ以上連結することで「行：最終文字以外に改行コードを含まない最大の文字列」を構成します。
つまりabc, def\n, 012というデータを持つ3つの文字列クラス（擬行）を連結したテキストはabcdef\nと012という2つの行を持ちます。

2.2 文字列クラス（擬行）の集合で構成される文字列クラス（擬ノード）

文字列クラス（擬ノード）は文字列クラス（擬行）と同様に、こちらもノードの定義から「最大」を除いたものになります。
このクラスを1つ以上連結することで「ノード」を構成します。

また、この文字列クラス（擬ノード）は文字列データを直接は管理しません。
その代わりに、文字列クラス（擬ノード）という文字列全体を構成する文字列クラス（擬行）の配列を持っています。
ただしこの配列のインデックスは文字列クラス（擬行）の性質上、行数とは一致しません。
さらに、配列自体は内部的には平行2分木になっています。

このクラスはノード内の行へのアクセスなどを担います。

2.3 文字列クラス（擬行）の集合で構成される文字列クラス（擬ノード）の集合で構成される文字列クラス（テキスト）

文字列クラス（テキスト）は文字列クラス（擬ノード）と同様に、文字列クラス（擬ノード）を子として持つテキスト全体を管理するクラスです。

このクラスはテキスト内のノードや行へのアクセスなどを担います。

2.4 まとめ

つまり、TATEditorでは文字列クラス（テキスト）を通してノードという編集単位を管理し、文字列クラス（擬ノード）を通して行という編集単位を管理しています。
これによって、テキスト内の行やノードへのアクセスをほぼ対数時間に収めることができています。

ほぼというのは、まだ文字列クラス（擬行）から行を構成する部分で先頭の文字列クラス（擬行）から順に改行コードを探すという処理になっているためです。ここも対数時間にすることは可能なのですが、実装時間とそもそも現在の実装で実用上問題ないため先送りにされています。

3. 編集履歴

さて、そもそもなぜ上に記したような面倒な文字列クラスになっているのかという問いへの答えが、編集履歴にあります。

まず、TATEditorの編集履歴ができることをざっと紹介します。

アンドゥ・リドゥ（元に戻す・やり直し）
- 特に回数に制限なし
- 所詮文字列なので実用上メモリ不足にはならないという仮定
ノードを指定してアンドゥ・リドゥ
- 指定したノードの中での変更のみを対象にします
- アンドゥ・リドゥ後も、テキスト全体のアンドゥ・リドゥは保持されます
行を指定してアンドゥ・リドゥ
- 指定した行の中での変更のみを対象にします
- アンドゥ・リドゥ後も、この行を含むノードやテキスト全体のアンドゥ・リドゥは保持されます
木構造のアンドゥ・リドゥ
- 連結リストのような編集履歴ではない
- 以下のようなことが可能
  1. a（リドゥなし）
  2. ab（リドゥなし）
    - 1.に編集履歴を追加（1個目）
  3. a: アンドゥ
    - 1.の状態
    - bを追加するリドゥがある
  4. ac（リドゥなし）
    - 1.に編集履歴を追加（2個目）
  5. a: アンドゥ（bを追加するリドゥとcを追加するリドゥがある）
    - 1.の状態
    - 2.へのリドゥがある
    - 4.へのリドゥがある
  6. ab: 2.の操作をリドゥした
- リスト構造の編集履歴は木構造の編集履歴の真部分実装になっている
  - なので内部的にはオプションでそちらに切り替えることもできる

3.1 文字列クラス（擬行）が持ちうる編集履歴

このクラスは基本的には通常の文字列クラスと変わりはないので、どの範囲の文字列をどの文字列で置換したかを保存するだけです。

新しい文字列が挿入されたインデックス
新しい文字列のUTF-16での長さ
挿入時に削除された文字列

が最低限必要な情報です。

これを適切に文字列クラス（擬行）に紐づいた編集履歴の木構造に追加していくだけです。

ただし、文字列クラス（擬行）の性質上、最終文字以外に改行コードを含めるような編集が走った場合、

改行コードから後ろを削除する（編集履歴に残す）
削除した文字列を持つ文字列クラス（擬行）を作成する
その文字列クラス（擬行）を自身の親である文字列クラス（擬ノード）に渡す

という処理を行います。
これで、文字列クラス（擬行）の性質を満足しつつ行内の編集履歴がすべて残ることになります。

3.2 文字列クラス（擬ノード）が持ちうる編集履歴

さて、ここでの編集履歴には一工夫が必要です。
それが以下の手順です。

自身の持つ文字列クラス（擬行）の配列の編集履歴を自身の編集履歴に追加する
子の文字列クラス（擬行）の編集履歴をすべて受け取り、その情報を自身の編集履歴に追加する
子から渡される改行以降の文字列クラス（擬行）を適切な場所に挿入し、その情報を自身の編集履歴に追加する

これによって、文字列クラス（擬ノード）の内部での編集履歴をすべて寄贈像に収めることができます。
アンドゥ・リドゥ時に編集内容が子のものならは子の文字列クラス（擬行）にアンドゥ・リドゥを依頼する形になります。
しかし、文字列クラス（擬行）に直接ユーザーから渡ってきたアンドゥ・リドゥの情報は自身では受け取りません。

3.3 文字列クラス（テキスト）が持ちうる編集履歴

こちらは基本的に文字列クラス（擬ノード）の編集履歴と思想は同じです。

3.4 まとめ

文字列クラスの括弧内に「擬」がつくのは、例えば、改行を削除すると、後ろの行と連結してひとつの行になるのですが、そのときにクラスの中身が「行」としてしまうとどちらのかの行の編集履歴を抹殺する必要があるためです。

これによって、行の編集履歴とノードの編集履歴、テキストの編集履歴を独立して（弱い結合で）保持することができ、

「アンドゥしてから上書きしてしまったあの編集に戻りたい」（木構造の編集履歴）
「この行のここだけ直したい」（行のアンドゥ・リドゥ）
「直した後にもノードのアンドゥ・リドゥはこのまま使い続けたい」（行とノードとテキストで独立した編集履歴）

ということが可能になります。

4. おわりに

現在の文字列クラス（ノード）と文字列クラス（テキストファイル）は抽象度が低すぎて使いにくいため、時間があるときにデータ構造の抽象化を行おうと思っています。

なお、この内容を実現可能なもっと簡単な方法があれば教えて欲しいです。