- กระบวนการลองสร้างโครงสร้างข้อมูลข้อความขึ้นมาเอง เพื่อทำโปรแกรมแก้ไขข้อความของตัวเอง
- โปรแกรมแก้ไขข้อความมีโครงสร้างที่สร้างได้ยากมาก เพราะต้องรองรับทั้งการแก้ไขไฟล์ขนาดใหญ่, เคอร์เซอร์หลายตัว, เลิกทำ/ทำซ้ำ และฟังก์ชันอื่น ๆ อีกมากมาย
- ดังนั้นความสามารถที่โครงสร้างข้อมูลนี้ต้องมีจึงมีดังนี้
- แทรก/ลบได้อย่างมีประสิทธิภาพ
- เลิกทำ/ทำซ้ำได้อย่างมีประสิทธิภาพ
- รองรับการเข้ารหัส UTF-8
- รองรับการแก้ไขแบบหลายเคอร์เซอร์อย่างมีประสิทธิภาพ
- Gap Buffer แม้จะติดตั้งใช้งานได้ง่าย แต่ทำให้การทำฟีเจอร์เลิกทำและหลายเคอร์เซอร์เป็นเรื่องยากมาก
- Rope มีประสิทธิภาพเพราะแบ่งไฟล์ขนาดใหญ่ออกเป็นส่วนเล็ก ๆ เพื่อแก้ไขได้ แต่หากต้องทำฟีเจอร์เลิกทำจะมีโอเวอร์เฮดสูง และการใช้หน่วยความจำอาจเพิ่มขึ้นมากกว่าที่คาด
- Piece Table เป็นโครงสร้างที่มีประสิทธิภาพมากจนถึงขั้น Microsoft Word เคยใช้งาน แต่ถ้ามีการแก้ไขจำนวนมาก ประสิทธิภาพอาจลดลง และการรองรับเลิกทำอาจทำให้ใช้หน่วยความจำเพิ่มขึ้น
- Piece Tree คือโครงสร้างข้อมูลที่ดีที่สุดสำหรับโปรแกรมแก้ไขข้อความ ซึ่งทีม VSCode พัฒนาขึ้นมาเพื่อแก้ข้อเสียทั้งหมดข้างต้น
- เลือกนำมาใช้เฉพาะข้อดีของ Rope และ Piece Table
- ใช้ RB Tree ในการเชื่อมต่อระหว่างแต่ละชิ้นส่วน จึงยังคงมีประสิทธิภาพแม้จะมีการแก้ไขจำนวนมาก
- อย่างไรก็ตาม เวอร์ชันที่ทีม VSCode พัฒนาขึ้นไม่ใช่โครงสร้างข้อมูลแบบ immutable จึงยังมีความไม่มีประสิทธิภาพอยู่บ้างในฟีเจอร์เลิกทำ
- จึงตัดสินใจพัฒนา Piece Tree แบบใหม่ที่เพิ่มคุณสมบัติ immutable เข้าไปเพื่อแก้ทุกปัญหา
- เนื่องจาก RB Tree แบบดั้งเดิมไม่สามารถทำให้เป็น immutable ได้ จึงเริ่มพัฒนาโดยอ้างอิง immutable RB Tree ที่ Bartosz Milewski เคยทำไว้
- ความแตกต่างจากโครงสร้างที่ทีม VSCode พัฒนามีดังนี้
- เนื่องจากมีกรณีที่ตัวแก้ไขต้องคำนึงถึงอักขระ Carriage Return ไม่มากนัก จึงไม่บันทึก CRLF แยกต่างหาก
- เพิ่ม API ที่สามารถตรวจดูบัฟเฟอร์ทั้งหมดในลักษณะคล้าย iterator เพื่อช่วยในการดีบัก
- เนื่องจากโครงสร้างข้อมูลเป็นแบบ immutable จึงทำให้ฟีเจอร์เลิกทำ/ทำซ้ำง่ายมาก
- การพัฒนาฟังก์ชันลบเป็นส่วนที่ยากที่สุด แต่สุดท้ายก็ทำสำเร็จ
- ได้เผยแพร่โครงสร้างข้อมูลที่เขียนขึ้นใหม่นี้ในชื่อ fredbuf
2 ความคิดเห็น
โอ้! ขอบคุณครับ ข้อมูลดี ๆ แบบนี้หายากมาก! พอเริ่มใช้ Emacs อย่างจริงจัง ก็เริ่มสนใจตัวโปรแกรมแก้ไขข้อความเองมากขึ้นเลยครับ ไว้ต้องค่อย ๆ ไปอ่านต้นฉบับด้วย! :-)
ขอบคุณสำหรับการสรุปอย่างละเอียดนะครับ/ค่ะ ผม/ฉันเองก็เคยสงสัยอยู่เหมือนกันว่าวิธีสร้างโครงสร้างข้อมูลของโปรแกรมแก้ไขข้อความทำกันอย่างไร ที่แท้ก็ใช้โครงสร้างข้อมูลแบบนี้นี่เอง