コンソールで動くエディタを作る(18日目) formatter、Rope構造

本稿は[自作エディタをつくる Advent Calendar 2016](http://qiita.com/advent-calendar/2016/make_editor)の18日目です、レポジトリは[こちら](https://github.com/tinyco/tiny_code_editor)

# プルリクエストをまた貰いました！

equal-l2氏にプルリクエストを貰いました。
ソースコードの最後が空行じゃないと、コンパイラに指摘される環境もあるようです。
自分の環境だと指摘されないので気づきませんでした。
Linterみたいなのがあったほうがいいかな、と思い調べてみます。
・・・Atomのpluginにあるらしい。でも自分のエディタで作りたいし。
でも、自分の場合は何かしないと空行をまたつけ忘れるのは確実です。

# フォーマッタをつける

自分のエディタをできるだけ使いたいので、書きながら警告貰うのはやめて[clang-format](http://clang.llvm.org/docs/ClangFormat.html)を試してみます、がビルドが通らなくなりました。
どうやら、オレオレ仕様のヘッダファイル生成ルール[これ](https://github.com/tinyco/clang_gen_header)が、
`//PUBLIC`を期待しているのに、`// PUBLIC`とスペースが入ったからのようです。

ヘッダファイル生成ルールに空白無視をつけて、clang-formatのフォーマットルールに

```
ColumnLimit: 1000
SortIncludes: false
```

を追加します。
前者は折り返しはヘッダファイル生成ルールが対応しておらず、後者はincludeを場当たり的に適当につけているので順序に依存性があるためです。
ひどいこと言ってる自覚はありますが、始めることが大事なんだと思うことにします。

ビルドも無事通ったので、試しにファイル末尾の空行をとってみます(上のプルリクエストを貰う前の状態)。自動で空行がつくはず！
・・・clang-formatは直してくれませんでした。しょんぼり。
ただ、ファイル末尾に空行を連続で入れると1個にはしてくれるので、実行前に空行を入れておきます。

```
find . | grep '\.c$' | sed 's/\(.*\)/ echo "" >> \1 /g' | sh
find . | grep '\.c$' | sed 's/\(.*\)/ clang-format -i \1 /g' | sh
```

これで、自動で末尾空行もそろうようになりました。

自動テストもちょっとずつしないとなぁ、とは思いつつ。

ちなみに[gnu-indent](https://www.gnu.org/software/indent/manual/indent.html)も試してみましたが、両者デフォルト設定だとclang-formatのほうがいい感じの気がします。
好みの問題ではあると思うのですが、後者のほうが普通っぽい感じがするというか。
どちらもMacだとbrewでインストールできます。

# バグをなおすぞ！

とりあえず、使ってて一番困るファイル名を間違えるバグをなおします。まあ落ちるのも困るんですが。

処理を順番に追いながらprintfデバッグしていきます。

・・・うーん。ハマった。

調べる過程で他の人のQiitaを読んでいたときに、なんとなく通知をみると前日分(といいつつさっき投稿した)の内容にコメントが来ていたので読むと
そのものズバリの指摘があります。

以下引用

> 本当にざっとですがソースコードを見てみました。
> ↓ の箇所の sizeof(filename) というのが間違ってますね。 これだと filename の大きさ、つまり char * の大きさが帰ってきてしまいます。 ここで本来知りたいのはポインタの大きさではなく文字列の長さなのですから strlen で長さチェックするべきです。

> https://github.com/tinyco/tiny_code_editor/blob/07fb86f26ea2395dd95462238b0ca08a8f5b778c/src/type/context_type.c#L22

SaitoAtsushi氏、ご指摘ありがとうございます。

ざっとみてわかるものなんだっていう驚きがありますが、指摘通り直すと動くようになりました。

main.c内でprintf("%s",context.filename);をしてもそれらしい値がprintfされていたのですが、
どうやら確保してない領域まで値を書いてprintfしてたっぽいですね。
そこはセグメンテーションフォールトしないのが少し不思議です。

# rope構造をしらべる

同じくSaitoAtsushi氏に頂いたコメントの[Rope](https://en.wikipedia.org/wiki/Rope_(data_structure))を調べてみます。

B-treeっぽい感じですが、分割のしかたが面白いですね。

ちょっと疑問に思ったのは、改行でデータ構造を割らないのだろうか、ということです。

僕のデータ構造は、まず改行で分けて双方向リストをつくり、行先頭から可変長文字列のために単方向リストをつくる構造です。

`abcdef<改行>ghi<改行>jklmn`という文だと

```
abc → def
⇅
ghi
⇅
jkl → mn
```

みたいな感じです。

それは

- (abc/ghi/jkl)部分、行先頭に素早くアクセスできると嬉しい。方法は考えてない。
- (abc/def)や(jkl/mn)部分、行の中身は「１行に入れる文字は、大抵そこまで大きくない」という仮定がおけるので、多少遅くても適当で良い。表示・編集する行しか見ないし。

と思っていました。

もし高速化を考えたときに、この構造であれば行番号は単なる連番なので、2分木でもよさそうだし、表示位置付近に頻繁にアクセスするだろうからキャッシュもよさそうです。

仮にrope構造を用いるのであれば、

- 普通は改行でデータ構造を分割せずに、文字数だけでデータを分割していくのだろうか
- 例えば5行目から表示したいときに、どうやって5行目(つまり改行文字4つめの場所)を探すのだろうか
- 改行位置をテーブルっぽいものでキャッシュしたら、改行追加や行削除とか大変では？

あたりが不思議です。

そもそも分割しやすいのデータ構造を持つということは、コピーペーストを行うときの速度を重視しているんでしょうか。

ざっくりいうと、表示することより編集することがボトルネックなのかなぁ、というのも疑問です。

気づいてなかったけど、コンソール上だとOSがコピーペーストの面倒みてくれないのか・・・。ひぇ。

あと、よく考えると可変長文字列ってどうやって実装してるんですかね。もちろん言語によるんだろうけど。


# 今日のまとめ

- clang-formatを導入しました
- ファイル名のバグを直してもらいました
- rope構造を調べました


意外にもプルリクエストが来たり、コードを読んだ上で指摘が来たりするので、
自分だけわかればいいや、と思わずに綺麗に書く努力をしないと！と思いました。

明日は読みづらいと思いつつ、放置していた(そしてよくバグる)string_type.cを綺麗にするぞ！