- Quá trình tự xây dựng một cấu trúc dữ liệu văn bản để tạo ra trình soạn thảo văn bản của riêng mình.
- Trình soạn thảo văn bản rất khó thiết kế cấu trúc vì phải xử lý các tệp khổng lồ hoặc nhiều tính năng đa dạng như đa con trỏ, hoàn tác/làm lại.
- Vì vậy, các yêu cầu đối với cấu trúc dữ liệu như sau.
- chèn/xóa hiệu quả
- hoàn tác/làm lại hiệu quả
- có thể sử dụng mã hóa UTF-8
- chỉnh sửa đa con trỏ hiệu quả
- Gap Buffer có cách triển khai đơn giản, nhưng rất khó hiện thực tính năng hoàn tác và đa con trỏ.
- Rope hiệu quả vì có thể chia tệp lớn thành các phần nhỏ để chỉnh sửa, nhưng chi phí phụ trợ cho tính năng hoàn tác khá lớn và mức dùng bộ nhớ có thể tăng nhiều hơn dự kiến.
- Piece Table là cấu trúc hiệu quả đến mức từng được Microsoft Word sử dụng, nhưng nếu chỉnh sửa quá nhiều thì hiệu năng có thể giảm và mức dùng bộ nhớ cho hoàn tác có thể tăng lên.
- Piece Tree là cấu trúc dữ liệu tốt nhất cho trình soạn thảo văn bản do nhóm VSCode triển khai để giải quyết mọi nhược điểm ở trên.
- Cấu trúc này được xây dựng bằng cách chọn lọc các ưu điểm của Rope và Piece Table.
- Vì dùng RB Tree để liên kết giữa các mảnh, nên dù có nhiều lần chỉnh sửa vẫn giữ được hiệu quả.
- Tuy vậy, phiên bản do nhóm VSCode triển khai không phải là cấu trúc dữ liệu bất biến, nên có một chút kém hiệu quả ở tính năng hoàn tác.
- Tác giả quyết định triển khai một Piece Tree mới có thêm tính bất biến để giải quyết toàn bộ các vấn đề.
- RB Tree truyền thống không thể có tính bất biến, nên bắt đầu triển khai bằng cách tham khảo RB Tree bất biến do Bartosz Milewski xây dựng.
- Khác biệt so với cấu trúc do nhóm VSCode triển khai như sau.
- Vì có ít trường hợp trình soạn thảo phải xét đến ký tự Carriage Return, nên không ghi riêng CRLF.
- Đã thêm API cho phép xem toàn bộ bộ đệm theo dạng giống như iterator để phục vụ gỡ lỗi.
- Vì cấu trúc dữ liệu là bất biến, nên hoàn tác/làm lại trở nên rất đơn giản.
- Việc triển khai chức năng xóa là khó nhất, nhưng cuối cùng cũng đã thành công.
- Cấu trúc dữ liệu mới được công bố với tên fredbuf.
2 bình luận
Ôi! Cảm ơn bạn. Thông tin quý giá thật! Từ khi bắt đầu sử dụng Emacs một cách nghiêm túc, mình ngày càng thấy hứng thú với chính bản thân trình soạn thảo văn bản. Chắc mình cũng phải đọc kỹ bài gốc mới được! :-)
Cảm ơn bạn đã tóm tắt rất chi tiết. Tôi cũng từng có lúc tự hỏi cấu trúc dữ liệu của trình soạn thảo văn bản được triển khai như thế nào, hóa ra người ta dùng những cấu trúc dữ liệu như thế này.