टेक्स्ट एडिटर की डेटा संरचना

• अपना खुद का टेक्स्ट एडिटर बनाने के लिए, टेक्स्ट डेटा संरचना को सीधे बनाने की प्रक्रिया।
• टेक्स्ट एडिटर में बहुत बड़ी फ़ाइलें संपादित करनी होती हैं, और multi-cursor, undo/redo जैसी विभिन्न सुविधाओं के कारण इसकी संरचना बनाना बहुत कठिन होता है।
• इसलिए डेटा संरचना के लिए आवश्यक सुविधाएँ इस प्रकार हैं।
  • कुशल insertion/deletion
  • कुशल undo/redo
  • UTF-8 encoding का उपयोग करने की क्षमता
  • कुशल multi-cursor editing
• Gap Buffer का implementation सरल है, लेकिन undo और multi-cursor सुविधाओं को implement करना बहुत कठिन है।
• Rope बड़ी फ़ाइलों को छोटे हिस्सों में बाँटकर संशोधित करने की सुविधा देता है, इसलिए कुशल है, लेकिन undo सुविधा के लिए overhead बढ़ जाता है और memory usage अपेक्षा से अधिक बढ़ सकता है।
• Piece Table Microsoft Word में इस्तेमाल होने जितनी कुशल संरचना है, लेकिन बहुत अधिक संपादन होने पर performance घट सकती है और undo के लिए memory usage बढ़ सकता है।
• Piece Tree ऊपर बताई गई सभी कमियों को हल करने के लिए VSCode टीम द्वारा implement की गई, टेक्स्ट एडिटर के लिए सबसे अच्छी डेटा संरचना है।
  • यह Rope और Piece Table के केवल फ़ायदों को चुनकर implement की गई है।
  • टुकड़ों के बीच कनेक्शन के लिए RB Tree का उपयोग होने से, बहुत अधिक संपादन होने पर भी यह कुशल बनी रहती है।
  • हालाँकि VSCode टीम द्वारा implement किया गया version immutable data structure नहीं है, इसलिए undo सुविधा में थोड़ी अक्षमता रहती है।
• इन सभी समस्याओं को हल करने के लिए immutable गुण जोड़कर एक नया Piece Tree implement करने का निर्णय लिया गया।
  • पारंपरिक RB Tree को immutable नहीं बनाया जा सकता, इसलिए Bartosz Milewski द्वारा implement किए गए immutable RB Tree को संदर्भ बनाकर implementation शुरू किया गया।
  • VSCode टीम द्वारा implement की गई संरचना से इसके अंतर इस प्रकार हैं।
    • क्योंकि editor को Carriage Return character पर विचार करने की ज़रूरत कम पड़ती है, इसलिए CRLF को अलग से record नहीं किया जाता।
    • debugging के लिए ऐसा API जो पूरे buffer को iterator जैसी संरचना में देख सके, जोड़ा गया।
    • डेटा संरचना immutable होने के कारण undo/redo बहुत सरल हो जाता है।
  • deletion सुविधा को implement करना सबसे कठिन था, लेकिन अंततः इसे सफलतापूर्वक implement कर लिया गया।
• नई लिखी गई डेटा संरचना को fredbuf नाम से जारी किया गया है।

[junghan0611]

ओह! धन्यवाद। ऐसी कीमती जानकारी! Emacs को ठीक से इस्तेमाल करना शुरू करने के बाद से टेक्स्ट एडिटर खुद ही मेरे लिए बहुत दिलचस्प हो गए हैं। मूल लेख भी आराम से पढ़ना पड़ेगा! :-)

[cosine20]

इतनी विस्तार से सारांश देने के लिए धन्यवाद। मैंने भी कभी न कभी यह सोचा है कि text editor के data structure आखिर कैसे implement किए जाते होंगे, और अब पता चला कि ऐसे data structure इस्तेमाल होते हैं।