- Proses membangun sendiri struktur data teks untuk membuat editor teks buatan sendiri.
- Editor teks sangat sulit dirancang strukturnya karena harus menangani berkas besar serta berbagai fitur seperti multi-cursor dan undo/redo.
- Karena itu, fitur yang dibutuhkan dari struktur data adalah sebagai berikut.
- Penyisipan/penghapusan yang efisien
- Undo/redo yang efisien
- Dapat menggunakan encoding UTF-8
- Pengeditan multi-cursor yang efisien
- Gap Buffer mudah diimplementasikan, tetapi sangat sulit untuk menerapkan fitur undo dan multi-cursor.
- Rope efisien karena dapat membagi berkas besar menjadi potongan kecil untuk dimodifikasi, tetapi untuk fitur undo overhead-nya besar dan penggunaan memorinya bisa meningkat lebih banyak dari perkiraan.
- Piece Table adalah struktur yang cukup efisien hingga pernah digunakan di Microsoft Word, tetapi jika pengeditan sangat banyak, performanya menurun dan penggunaan memori untuk undo dapat bertambah.
- Piece Tree adalah struktur data terbaik untuk editor teks yang diimplementasikan oleh tim VSCode untuk mengatasi semua kekurangan di atas.
- Diimplementasikan dengan mengambil hanya keunggulan dari Rope dan Piece Table.
- Karena menggunakan RB Tree untuk menghubungkan antar potongan, struktur ini tetap efisien meskipun terjadi banyak pengeditan.
- Namun, versi yang diimplementasikan tim VSCode bukan struktur data immutable, sehingga memiliki sedikit inefisiensi pada fitur undo.
- Diputuskan untuk mengimplementasikan Piece Tree baru dengan menambahkan immutability pada struktur data guna menyelesaikan semua masalah.
- RB tree tradisional tidak bisa dibuat immutable, sehingga implementasi dimulai dengan merujuk pada RB tree immutable yang dibuat oleh Bartosz Milewski.
- Perbedaannya dengan struktur yang diimplementasikan tim VSCode adalah sebagai berikut.
- Karena editor jarang perlu mempertimbangkan karakter Carriage Return, CRLF tidak dicatat secara terpisah.
- Untuk debugging, ditambahkan API yang memungkinkan seluruh buffer diperiksa dalam bentuk seperti iterator.
- Karena struktur datanya immutable, undo/redo menjadi sangat sederhana.
- Implementasi fitur penghapusan adalah bagian yang paling sulit, tetapi pada akhirnya berhasil diselesaikan.
- Struktur data yang baru ditulis ini dirilis dengan nama fredbuf.
2 komentar
Oh! Terima kasih. Informasi berharga seperti ini! Sejak mulai benar-benar menggunakan Emacs, saya jadi makin tertarik pada editor teks itu sendiri. Saya juga harus membaca artikel aslinya pelan-pelan! :-)
Terima kasih atas rangkuman yang detail. Saya pernah setidaknya sekali bertanya-tanya bagaimana struktur data editor teks diimplementasikan, dan ternyata struktur data seperti ini yang digunakan.