Editor teks modern tidak hanya dapat berbunyi bip dan tidak meninggalkan program. Ternyata metabolisme yang sangat kompleks bermuara di dalamnya. Ingin tahu trik apa yang sedang dilakukan untuk menghitung ulang koordinat dengan cepat, bagaimana gaya, lipatan dan softwraps dilampirkan pada teks dan bagaimana semuanya diperbarui, apa yang harus dilakukan dengan struktur data fungsional dan antrian prioritas, serta cara menipu pengguna - selamat datang di kucing!



Artikel ini didasarkan pada laporan Alexei Kudryavtsev dengan Joker 2017. Alexei telah menulis Intellij IDEA di JetBrains selama sekitar 10 tahun. Di bawah potongan Anda akan menemukan transkrip video dan teks dari laporan.

Struktur Data Di Dalam Editor Teks

Untuk memahami cara kerja editor, mari kita tulis.



Itu saja, editor paling sederhana kami sudah siap.

Di dalam editor, teks termudah untuk disimpan dalam array karakter, atau, apa yang sama (dalam hal organisasi memori), di kelas Java StringBuffer. Untuk mendapatkan beberapa karakter dengan offset, kita memanggil metode StringBuffer.charAt (i). Dan untuk memasukkan ke dalamnya karakter yang kita ketikkan pada keyboard, kita memanggil metode StringBuffer.insert (), yang menyisipkan karakter di suatu tempat di tengah.

Apa yang paling menarik, terlepas dari semua kesederhanaan dan kebodohan editor ini, adalah ide terbaik yang dapat Anda ciptakan. Ini sederhana dan hampir selalu cepat.

Sayangnya, masalah skala muncul dengan editor ini. Bayangkan kita mencetak banyak teks di dalamnya dan akan memasukkan huruf lain di tengah. Berikut ini akan terjadi. Kami sangat membutuhkan ruang kosong untuk surat ini dengan menggerakkan semua huruf lainnya satu karakter ke depan. Untuk melakukan ini, kami menggeser surat ini dengan satu posisi, lalu yang berikutnya dan seterusnya, sampai akhir teks.

Begini tampilannya di memori:



Menggeser banyak megabita ini tidak terlalu baik: lambat. Tentu saja, untuk komputer modern, ini adalah masalah sepele - semacam megabita yang menyedihkan untuk bergerak maju mundur. Tetapi untuk perubahan teks yang sangat aktif, ini bisa terlihat.

Untuk mengatasi masalah ini memasukkan karakter di tengah, waktu yang lama muncul dengan solusi yang disebut "Penyangga Gap".

Penyangga celah

Gap adalah gap. Buffer adalah, seperti yang Anda bayangkan, buffer. Struktur data Gap Buffer adalah buffer kosong yang kami simpan di tengah teks kami, untuk berjaga-jaga. Jika kami perlu mencetak sesuatu, kami menggunakan buffer teks kecil ini untuk mengetik dengan cepat.



Struktur data telah berubah sedikit - array tetap di tempatnya, tetapi dua petunjuk telah muncul: di awal buffer dan di akhir. Untuk mengambil karakter dari editor di beberapa offset, kita perlu memahami apakah itu sebelum atau sesudah buffer ini dan sedikit mengoreksi offset. Dan untuk memasukkan karakter, pertama-tama kita harus memindahkan Penyangga Gap ke tempat ini dan mengisinya dengan karakter ini. Dan, tentu saja, jika kami melampaui buffer kami, entah bagaimana membuatnya kembali. Ini adalah tampilannya di gambar.



Seperti yang Anda lihat, pertama-tama kita bergerak untuk waktu yang lama pada buffer celah kecil (kotak biru) ke lokasi pengeditan (cukup menukar karakter dari tepi kiri dan kanan pada gilirannya). Lalu kami menggunakan buffer ini, mengetik karakter di sana.

Seperti yang Anda lihat, tidak ada pergerakan megabita karakter, sisipannya sangat cepat, untuk waktu yang konstan, dan sepertinya semua orang senang. Segalanya tampak baik-baik saja, tetapi jika prosesor kami sangat lambat, waktu yang cukup nyata terbuang untuk memindahkan celah-buffer dan teks bolak-balik. Ini terutama terlihat pada saat megahertz yang sangat kecil.

Meja potong

Tepat pada saat itu, sebuah perusahaan bernama Microsoft menulis editor teks Word. Mereka memutuskan untuk menerapkan ide lain untuk mempercepat pengeditan yang disebut "Piece Table", yaitu, "Piece Table". Dan mereka mengusulkan untuk menyimpan teks editor dalam array karakter paling sederhana yang sama, yang tidak akan berubah, dan menempatkan semua perubahannya dalam tabel terpisah dari potongan-potongan yang sangat diedit ini.



Jadi, jika kita perlu menemukan beberapa karakter dengan offset, kita perlu menemukan bagian ini yang kita edit dan ekstrak karakter ini darinya, dan jika tidak ada di sana, maka pergi ke teks asli. Memasukkan simbol menjadi lebih mudah, kita hanya perlu membuat dan menambahkan bagian baru ini ke tabel. Berikut tampilannya di gambar:



Di sini kami ingin menghapus ruang di offset 5. Untuk melakukan ini, kami menambahkan dua potongan baru ke tabel irisan: satu menunjukkan fragmen pertama ("Nyebelin"), dan yang kedua menunjukkan fragmen setelah mengedit ("domba"). Ternyata celah dari mereka menghilang, dua bagian ini direkatkan bersama, dan kami sudah mendapatkan teks baru tanpa spasi: "Oblomovtsy". Kemudian kami menambahkan teks baru ("menderita Oblomovisme") ke akhir. Gunakan buffer tambahan dan tambahkan irisan baru ke tabel potongan yang menunjuk ke teks terbaru ini ditambahkan.

Seperti yang Anda lihat, tidak ada gerakan bolak-balik, semua teks tetap di tempatnya. Berita buruknya adalah semakin sulit untuk mendapatkan simbol, karena memilah-milah semua bagian ini cukup sulit.

Untuk meringkas.

Apa yang baik tentang Sepotong Meja :

• Sematkan cepat;
• Mudah dilakukan undo;
• Hanya tambahkan.

Apa yang buruk:

• Sangat sulit untuk mengakses dokumen;
• Sangat sulit untuk diimplementasikan.

Mari kita lihat siapa yang biasanya kita gunakan apa.

NetBeans, Eclipse dan Emacs menggunakan Gap Buffer - bagus sekali! Vi tidak repot dan hanya menggunakan daftar baris. Word menggunakan Piece Table (baru-baru ini mereka meletakkan jenis kuno mereka dan di sana Anda bahkan dapat memahami sesuatu).

Atom lebih menarik. Sampai saat ini, mereka tidak mengganggu dan menggunakan daftar garis JavaScript. Dan kemudian mereka memutuskan untuk menulis ulang semuanya dalam C ++ dan menumpuk struktur yang agak rumit, yang tampaknya mirip dengan Piece Table. Tetapi potongan-potongan ini tidak disimpan dalam daftar, tetapi di pohon, dan dalam apa yang disebut pohon splay - ini adalah pohon yang menyesuaikan diri ketika dimasukkan ke dalamnya, sehingga memasukkan baru-baru ini lebih cepat. Mereka melakukan hal yang sangat rumit.

Apa yang digunakan Intellij IDEA?
Tidak, tidak gap-buffer. Tidak, Anda salah juga, bukan meja potong.
Ya, benar, sepedamu sendiri.

Faktanya adalah bahwa persyaratan IDE untuk menyimpan teks sedikit berbeda dari pada editor teks biasa. IDE memerlukan dukungan untuk berbagai hal rumit seperti daya saing, yaitu akses paralel ke teks dari editor. Misalnya, agar berbagai macam makanan panggang dapat membacanya dan melakukan sesuatu. (Inspeksi adalah sepotong kecil kode yang mem-parsing program dengan satu atau lain cara - misalnya, mencari tempat yang melempar NullPointerException). IDE juga membutuhkan dukungan versi teks yang dapat diedit. Beberapa versi secara bersamaan di memori saat Anda bekerja dengan dokumen sehingga proses panjang ini terus menganalisis versi yang lama.

Masalahnya

Daya Saing / Versi

Untuk menjaga paralelisme, operasi teks biasanya dibungkus dengan "disinkronkan", atau dalam Baca / Tulis-kunci. Sayangnya, ini tidak skala dengan sangat baik. Pendekatan lain adalah Teks Tidak Berubah, yaitu repositori teks tidak berubah.



Inilah yang terlihat seperti editor dengan dokumen abadi sebagai struktur data pendukung.

Bagaimana cara kerja struktur data?

Alih-alih array karakter, kita akan memiliki objek baru tipe ImmutableText, yang menyimpan teks dalam bentuk pohon, di mana substring kecil disimpan dalam lembaran. Ketika mengakses di beberapa offset, dia mencoba mencapai lembar paling bawah di pohon ini, dan dia sudah akan ditanya simbol yang kita maksudkan. Dan ketika Anda memasukkan teks, ia membuat pohon baru dan menyimpannya di tempat yang lama.



Misalnya, kami memiliki dokumen dengan teks "Bebas kalori". Ini diimplementasikan sebagai pohon dengan dua lembar pengganti "Setan" dan "tinggi kalori." Ketika kami ingin memasukkan baris "cantik" di tengah, versi baru dari dokumen kami dibuat. Dan tepatnya, root baru dibuat, yang sudah terlampir tiga lembar: "Setan", "cukup" dan "tinggi kalori". Selain itu, dua lembar baru ini dapat merujuk ke versi pertama dari dokumen kami. Dan untuk lembar di mana kita memasukkan garis "cantik", sebuah simpul baru dialokasikan. Di sini baik versi pertama dan versi kedua tersedia pada saat yang sama dan semuanya tidak berubah, tidak dapat diubah. Semuanya terlihat bagus.

Siapa yang menggunakan struktur rumit apa?



Sebagai contoh, di GNOME, beberapa widget standar mereka menggunakan struktur yang disebut Rope. Xi-Editor, editor baru brilian dari Raf Levien , menggunakan Persistent Rope. Dan Intellij IDEA menggunakan Pohon Abadi ini. Di balik semua nama ini, pada kenyataannya, kurang lebih struktur data yang sama dengan representasi teks seperti pohon. Kecuali bahwa GtkTextBuffer menggunakan Mutable Rope, mis. Pohon dengan simpul yang bisa berubah, dan Intellij IDEA dan Xi-Editor - Immutable.

Hal berikutnya yang perlu dipertimbangkan ketika mengembangkan repositori karakter dalam IDE modern disebut multicats. Fitur ini memungkinkan Anda mencetak di beberapa tempat sekaligus, menggunakan beberapa media.



Kita dapat mencetak sesuatu dan pada saat yang sama di beberapa tempat dokumen kita memasukkan apa yang kita cetak di sana. Jika kita melihat bagaimana struktur data kita, yang kita periksa, bereaksi terhadap multicaret, kita akan melihat sesuatu yang menarik.



Jika kita memasukkan karakter ke editor primitif pertama kita, tentu saja akan membutuhkan waktu linier untuk memindahkan sekelompok karakter bolak-balik. Ini ditulis sebagai O (N). Untuk editor berdasarkan Gap Buffer, pada gilirannya, waktu yang konstan diperlukan, untuk itulah ia diciptakan.

Untuk pohon yang tidak dapat diubah, waktu tergantung pada ukuran logaritmik, karena Anda harus terlebih dahulu pergi dari atas pohon ke daunnya - ini adalah logaritma, dan kemudian untuk semua simpul di jalur untuk membuat simpul baru untuk pohon baru - ini lagi-lagi adalah logaritma. Piece Table juga membutuhkan konstanta.
Tapi semuanya berubah sedikit jika kita mencoba mengukur waktu memasukkan karakter ke dalam editor dengan multi-gerbong, yaitu, memasukkan secara bersamaan di beberapa tempat. Sekilas, waktu tampaknya meningkat secara proporsional dengan faktor C - jumlah tempat di mana simbol dimasukkan. Inilah yang terjadi, dengan pengecualian Gap Buffer. Dalam kasusnya, waktu, alih-alih waktu C, secara tak terduga meningkatkan beberapa waktu C * L yang tidak dapat dipahami, di mana L adalah jarak rata-rata antara gerbong. Mengapa ini terjadi?

Bayangkan kita perlu memasukkan baris ", on" di dua tempat di dokumen kita.



Inilah yang terjadi pada editor saat ini.

• Buat gap-buffer di editor (kotak biru kecil di gambar);
• Kami memulai dua gerbong (garis vertikal tebal hitam);
• Kami mencoba mencetak;
• Masukkan koma ke Penyangga Gap kami;
• Anda sekarang harus memasukkannya di tempat kereta kedua;
• Untuk melakukan ini, kita perlu memindahkan Penyangga Celah kita ke posisi gerbong berikutnya;
• Mencetak koma di tempat kedua;
• Sekarang Anda perlu memasukkan karakter berikutnya di posisi kereta pertama;
• Dan kita harus mendorong Penyangga Gap kita kembali;
• Masukkan huruf "n";
• Dan kami memindahkan penyangga lama kami ke tempat gerbong kedua;
• Kami memasukkan "n" kami di sana;
• Pindahkan buffer kembali untuk memasukkan karakter berikutnya.

Rasakan kemana semuanya pergi?

Ya, ternyata karena banyak gerakan penyangga ini bolak-balik, total waktu kita meningkat. Sejujurnya, ini bukan karena ngeri secara langsung karena telah meningkat - untuk memindahkan megabyte yang menyedihkan, gigabyte bolak-balik untuk komputer modern bukanlah masalah, tetapi menarik bahwa struktur data ini bekerja secara radikal berbeda dalam kasus multicats.

Terlalu banyak garis? LineSet!

Apa masalah lain yang ada dalam editor teks biasa? Masalah yang paling sulit adalah menggulung, yaitu menggambar ulang editor sambil memindahkan carriage ke baris berikutnya.



Ketika editor menggulir, kita perlu memahami dari baris mana, dari simbol apa kita perlu mulai menggambar teks di jendela kecil kita. Untuk melakukan ini, kita perlu dengan cepat memahami baris mana yang sesuai dengan offset mana.



Ada antarmuka yang jelas untuk ini, ketika kita perlu memahami offsetnya dalam teks dengan nomor baris. Dan sebaliknya, oleh offset dalam teks untuk memahami di baris mana itu. Bagaimana ini bisa dilakukan dengan cepat?

Misalnya, seperti ini:

Atur garis-garis ini menjadi pohon dan tandai setiap simpul pohon ini dengan menggeser awal garis dan menggeser ujung garis. Dan kemudian, untuk memahami dengan offset di mana garis itu berada, Anda hanya perlu menjalankan pencarian logaritmik di pohon ini dan menemukannya.



Cara lain bahkan lebih mudah.

Tuliskan dalam tabel offset dari awal baris dan akhir baris. Dan kemudian, untuk menemukan offset awal dan akhir dengan nomor baris, Anda perlu mengakses indeks.



Menariknya, di dunia nyata, kedua metode digunakan.



Sebagai contoh, Eclipse menggunakan struktur kayu sedemikian rupa sehingga, seperti yang Anda lihat, bekerja dalam waktu logaritmik untuk membaca dan memperbarui. Dan IDEA menggunakan struktur tabel, yang pembacaannya adalah konstanta cepat, itu adalah pembalikan indeks dalam tabel, tetapi pembangunan kembali agak lambat, karena Anda perlu membangun kembali seluruh tabel saat mengubah panjang baris.

Masih terlalu banyak baris? Lipatan!

Apa lagi hal buruk yang terjadi pada editor teks? Misalnya lipatan. Ini adalah potongan-potongan teks yang dapat Anda "runtuh" ​​dan menunjukkan sesuatu yang lain sebagai gantinya.



Titik-titik ini pada latar belakang hijau dalam gambar menyembunyikan banyak simbol di belakang kami, tetapi jika kita tidak tertarik melihatnya (seperti dalam kasus, misalnya dokumen Java membosankan atau daftar impor yang paling lama), kita menyembunyikannya, menutupnya elipsis.

Dan di sini lagi Anda perlu memahami kapan itu berakhir dan kapan wilayah yang perlu kami tunjukkan dimulai, dan bagaimana cara memperbaruinya dengan cepat? Bagaimana ini diatur, saya akan katakan nanti.

Garis terlalu panjang? Bungkus lembut!

Juga, editor modern tidak dapat hidup tanpa bungkus lunak. Gambar tersebut menunjukkan bahwa pengembang membuka file JavaScript setelah minimalisasi dan segera menyesalinya. Garis besar JavaScript ini, ketika kami mencoba menampilkannya di editor, tidak akan masuk ke layar mana pun. Oleh karena itu, bungkus lunak secara paksa merobeknya menjadi beberapa garis dan mendorongnya ke layar.
Bagaimana ini diatur - nanti.

Kecantikannya terlalu sedikit

Dan akhirnya, saya juga ingin membawa keindahan ke editor teks. Misalnya, sorot beberapa kata. Pada gambar di atas, kata kunci disorot dengan huruf tebal biru, beberapa metode statis dengan cetak miring, beberapa anotasi - juga dalam warna yang berbeda.

Jadi bagaimana Anda masih menyimpan dan memproses lipatan, pembungkus lunak, dan highlight?
Ternyata semua ini, pada prinsipnya, adalah satu dan tugas yang sama.

Kecantikannya terlalu kecil? Range highlighters!

Untuk mendukung semua fitur ini, yang perlu kita lakukan hanyalah menempelkan beberapa atribut teks pada offset yang diberikan dalam teks, misalnya, warna, font atau teks untuk melipat. Selain itu, atribut teks ini harus diperbarui setiap saat di tempat ini sehingga mereka dapat bertahan dari segala jenis penyisipan dan penghapusan.

Bagaimana ini biasanya diterapkan? Secara alami, dalam bentuk pohon.

Masalah: kecantikan terlalu banyak? Pohon interval!

Misalnya, di sini kami memiliki beberapa highlight kuning yang ingin kami simpan dalam teks. Kami menambahkan interval highlight ini ke dalam pohon pencarian, yang disebut pohon interval. Ini adalah pohon pencarian yang sama, tetapi sedikit rumit karena kita perlu menyimpan interval, bukan angka.

Dan karena ada interval sehat dan kecil, bagaimana memilah mereka, membandingkannya satu sama lain dan menempatkannya di pohon adalah tugas yang agak tidak sepele. Meskipun sangat dikenal luas dalam ilmu komputer. Kemudian lihat bagaimana pun waktu luang Anda cara kerjanya. Jadi, kita mengambil dan meletakkan semua interval kita di pohon, dan kemudian setiap perubahan dalam teks di suatu tempat di tengah mengarah ke perubahan logaritmik di pohon ini. Misalnya, memasukkan karakter harus menghasilkan pembaruan semua interval di sebelah kanan karakter itu. Untuk melakukan ini, kami menemukan semua simpul dominan untuk simbol ini dan menunjukkan bahwa semua simpul mereka harus dipindahkan satu simbol ke kanan.

Masih menginginkan kecantikan? Ligatur!

Masih ada hal yang mengerikan - pengikat, yang juga ingin saya dukung. Ini adalah keindahan yang berbeda, seperti tanda "! =" Digambar dalam bentuk mesin terbang besar "tidak sama" dan seterusnya. Untungnya, di sini kita mengandalkan mekanisme ayunan untuk mendukung ligatur ini. Dan, dalam pengalaman kami, ia tampaknya bekerja dengan cara yang paling sederhana. Di dalam font, daftar semua pasangan karakter ini disimpan, yang, jika digabungkan bersama, membentuk semacam ikatan yang rumit. Kemudian, ketika menggambar garis, Swing hanya mengulangi semua pasangan ini, menemukan yang diperlukan dan menariknya sesuai. Jika Anda memiliki banyak ligatur di font, maka, tampaknya, menampilkannya akan melambat secara proporsional.

Tip rem

Dan yang paling penting - masalah lain yang dihadapi dalam editor kompleks modern adalah optimalisasi tip, yaitu, menekan tombol dan menampilkan hasilnya.



Jika Anda masuk ke Intellij IDEA dan melihat apa yang terjadi ketika Anda menekan tombol, maka akan terjadi horor berikut:

• Pada klik tombol, kita harus melihat apakah kita berada dalam popup penyelesaian untuk menutup menu untuk penyelesaian jika, misalnya, kita mengetikkan beberapa "Enter".
• Anda perlu melihat apakah file tersebut di bawah beberapa sistem kontrol versi yang rumit, seperti Perforce, yang perlu mengambil beberapa tindakan untuk mulai mengedit.
• Periksa apakah ada wilayah khusus dalam dokumen yang tidak dapat dicetak, seperti beberapa teks yang dibuat secara otomatis.
• Jika dokumen diblokir oleh operasi yang belum berakhir, Anda harus menyelesaikan pemformatan, dan hanya kemudian melanjutkan.
• injected-, , , - .
• auto popup handler, , , .
• info , , . selection remove, selection , . selection , .
• typed handler, , .
• .
• undo, virtual space' write action.
• , .

!

, , . , . , listener , , - . editor view. - listener'.

, , - DocumentListener?

Editor.documentChanged() :

• error stripe;
• gutter size, ;
• editor component size, ;
• ;
• soft wrap, ;
• repaint().

repaint() — Swing, . , Repaint Swing.

- , repaint , :



paint-, , .

, , ?



, , . Intellij IDEA .



, - - , , , . ! , , , - — ! , - . . «Zero latency typing».

— .

? , — , Google Docs - - .

:

• ;
• .

, , .

- . , , . . — , «intention preservation». , - , , , . — . , - , .

Operation transformation

, , «operation transformation». . , - : , . Operation transformation . , , , - . , . , - . , , .

, , , . «TP2 puzzle».



- , , . , Operation transformation , , , («»). («»). , . , Operation transformation, - .

, Google Docs, Google Wave - Etherpad. Operation transformation .

Conflict-free replicated data type

: « , OT!» , , . , , , , 100% . «CRDT» (Conflict-free replicated data type).



, , . , , , . , . - ( ), () ( ).



?

Ya , G-counter', , . , . «+1» , «+1» , , — «2». , , . G-counter, , . G-counter, . , , . . — . , CRDT. , .

Conflict-free replicated inserts

, , , . , , .

, , - - , , , , . , , , , . , , , , 2 «», , «» «» «».

Conflict-free replicated deletes

. , , , - . , , . , , , .
, .

Conflict-free replicated edits

, , CRDT - , , Xi-Editor, Fuchsia. , , .

Zipper

, «Zipper». , , . , , . , ( «» , , « »). , - . , - , . Zipper.

, . .



Zipper , (« »). Zipper' . — . (), , . , Zipper, - , . , , , ( ). , ( ). , . , .

, .

? -, , , , . , , . -, , . . Terima kasih

→
→

Referensi

Zipper data structure
CRDT in Xi Editor



, Visual Studio Code editor Piece Table .
, - .

Ingin laporan yang lebih kuat, termasuk Java 11? Kemudian kami menunggu Anda di Joker 2018 . Pembicara tahun ini: Josh Long, John McClean, Marcus Hirth, Robert Scholte, dan speaker keren lainnya. Ada 17 hari tersisa sebelum konferensi. Tiket di situs.