Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Goでテキストエディタを作った話@GDG Devfest2020
Search
arakawa
October 17, 2020
Programming
0
230
Goでテキストエディタを作った話@GDG Devfest2020
https://tokyo.gdgjapan.org/devfest2020
arakawa
October 17, 2020
Tweet
Share
More Decks by arakawa
See All by arakawa
Goのソースコードから読み解くオブジェクト指向プログラミング@Object-Oriented Conference 2020
adsholoko
5
1.1k
Other Decks in Programming
See All in Programming
testingを眺める
matumoto
1
140
Deep Dive into Kotlin Flow
jmatsu
1
320
Rancher と Terraform
fufuhu
2
240
もうちょっといいRubyプロファイラを作りたい (2025)
osyoyu
1
430
私の後悔をAWS DMSで解決した話
hiramax
4
210
Design Foundational Data Engineering Observability
sucitw
3
190
print("Hello, World")
eddie
2
530
Laravel Boost 超入門
fire_arlo
3
210
🔨 小さなビルドシステムを作る
momeemt
4
680
1から理解するWeb Push
dora1998
7
1.9k
2025 年のコーディングエージェントの現在地とエンジニアの仕事の変化について
azukiazusa1
24
12k
モバイルアプリからWebへの横展開を加速した話_Claude_Code_実践術.pdf
kazuyasakamoto
0
320
Featured
See All Featured
GitHub's CSS Performance
jonrohan
1032
460k
Typedesign – Prime Four
hannesfritz
42
2.8k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
12
1.1k
Fireside Chat
paigeccino
39
3.6k
How to Ace a Technical Interview
jacobian
279
23k
Side Projects
sachag
455
43k
Being A Developer After 40
akosma
90
590k
Fantastic passwords and where to find them - at NoRuKo
philnash
52
3.4k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Writing Fast Ruby
sferik
628
62k
Optimising Largest Contentful Paint
csswizardry
37
3.4k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
53
2.9k
Transcript
Goでテキストエディタを作った話
荒川聖悟 Sansan事業部 プロダクト開発部 iOSエンジニア 自己紹介 2 @adsholoko
車輪の再発明が好きです 3 NESエミュレータ『goones』 https://github.com/ad-sho-loko/goones DB『bogoDB』 https://github.com/ad-sho-loko/bogoDB 他にもコンパイラなど...
ターミナル上で動作するテキストエディタmille
milleの特徴 - ターミナルで動作する自作テキストエディタ - ソースコードは1000行以内(テストコードは除く) - Goで実装 - 外部ライブラリを利用していない
milleの機能 - ASCII対応 - キーボードショートカット - ファイルの読み込み/保存 - Goのキーワードハイライト機能
参考実装
どうやって作るのか3つほど紹介 - キーボード入力を受け付ける仕組み - ターミナルをテキストエディタに変える仕組み - 文字入力を効率化するためのデータ構造
キーボードからの入力受け付け - 当然、標準入力から受け付ける - ただし処理中にキー入力があった場 合にも取りこぼさないように実装する 必要がある goroutineにて別スレッドとして実行させ、排 他制御のためにchannelを利用
ターミナルをテキストエディタに変える仕組み 通常、プロセスは標準入力のデータをバッファし、改行が行われたときにプロセスに渡 されるようになっている(Cookedモード) しかしテキストエディタでは1文字入力するごとにプロセスに渡したい場合はrawモード にする必要がある。
Rawモードへ移行する方法 https://viewsourcecode.org/snaptoken/kilo/02.enteringRawMode.html https://en.wikipedia.org/wiki/Terminal_mode 参考
テキストエディタに適したデータ構造選び - 当然ながらテキストエディタは文字を入力し、それを格納する必要がある - 文字の参照・入力・挿入・削除はなるべく早く実行したい! - しかしすべてがO(1)なデータ構造はない... GapBufferというデータ構造を採用することに
“Hello, World”を入力することを考えてみる 文字入力の動き
文字入力の動き ‘H’を挿入 H
H e ‘e’を挿入 文字入力の動き
H e l 文字入力の動き
H e l l o , W o r l
d ! ‘!’を挿入 文字入力の動き
H e l , W o r l d !
’lo’を入力し忘れた! もし入力ミスが起きたときに...
配列の場合 H e l , W o r l d
! ‘l’を挿入
配列の場合 H e l , , W o r l
d ! O(n)操作が発生! 挿入処理のためにずらす必要がある
配列の場合 H e l l , W o r l
d ! ‘o’を挿入
配列の場合 H e l l , W o r l
d ! O(n)操作が発生!(二回目)
配列の場合 H e l l o , W o r
l d ! 挿入操作が走るたびにO(n)発生する
GapBuffer H e l , W o r l d
! ’lo’を入力し忘れた!
GapBuffer H e l , W o r l d
! ‘l’を挿入
GapBuffer H e l , W , W o r
l d ! 挿入位置以降の文字列を後方に移す
GapBuffer H e l , W , W o r
l d ! O(n)操作が発生! 挿入位置以降の文字列を後方に移す
GapBuffer H e l l , W o r l
d ! ‘o’を挿入
GapBuffer H e l l o , W o r
l d ! ‘o’を挿入 O(1)で挿入可能!
GapBuffer - データ構造 H e l l o , W
o r l d ! array startPieceIndex endPieceIndex https://github.com/ad-sho-loko/mille/blob/master/gap_table.go
GapBuffer メリット 挿入をする箇所から連続で入力する人間の動きに適したデータ構造である - 実装コードがシンプル - 参照はO(1)で可能 - 一定の条件下では挿入O(1)、削除O(1) デメリット
- 要素をランダムに挿入・削除すると、配列と同様にO(n) 分のコストがかかる
まとめ - テキストエディタに適したデータ構造やアルゴリズムが存在する - Goが低レイヤな箇所は抽象化しており、本質的な箇所の実装だけで良い - 1000行未満のコードなのでぜひ詳細はコードリーディングしてみてください - 車輪の再発明は楽しい!!
テキストエディタ作りましょう
質問はTwitterにてどうぞ! @adsholoko 34