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
220
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
Railsアプリケーションと パフォーマンスチューニング ー 秒間5万リクエストの モバイルオーダーシステムを支える事例 ー Rubyセミナー 大阪
falcon8823
4
950
Go1.25からのGOMAXPROCS
kuro_kurorrr
1
810
git worktree × Claude Code × MCP ~生成AI時代の並列開発フロー~
hisuzuya
1
480
GitHub Copilot and GitHub Codespaces Hands-on
ymd65536
1
120
Gleamという選択肢
comamoca
6
760
NPOでのDevinの活用
codeforeveryone
0
360
datadog dash 2025 LLM observability for reliability and stability
ivry_presentationmaterials
0
120
XP, Testing and ninja testing
m_seki
3
200
データの民主化を支える、透明性のあるデータ利活用への挑戦 2025-06-25 Database Engineering Meetup#7
y_ken
0
320
既存デザインを変更せずにタップ領域を広げる方法
tahia910
1
240
Hypervel - A Coroutine Framework for Laravel Artisans
albertcht
1
100
FormFlow - Build Stunning Multistep Forms
yceruto
1
190
Featured
See All Featured
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
161
15k
Raft: Consensus for Rubyists
vanstee
140
7k
Art, The Web, and Tiny UX
lynnandtonic
299
21k
Build The Right Thing And Hit Your Dates
maggiecrowley
36
2.8k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.5k
Code Reviewing Like a Champion
maltzj
524
40k
Building Better People: How to give real-time feedback that sticks.
wjessup
367
19k
Mobile First: as difficult as doing things right
swwweet
223
9.7k
A Tale of Four Properties
chriscoyier
160
23k
Typedesign – Prime Four
hannesfritz
42
2.7k
Fireside Chat
paigeccino
37
3.5k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
17
940
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