Datové struktury a principy editoru textu

Title Datové struktury a principy editoru textu
Author Richard Michalský
Date 6.12.1998
Reference kralik@mail.kolej.mff.cuni.cz
File docs/editstructs.html
Project KTTV

Tento návrh datových struktur editoru textu vznikl na půlnoční pracovní schůzce projektu a zdá se, že hlavně pokročilé hodině můžeme děkovat za výrazné zjednodušení druhdy tak komplikované problematiky (i když Jindřich bude tvrdit něco jiného). Přestože se návrhu účastnili čtyři členové týmu ve složení Lišák, Einstein, Jindřich a Králík, bylo rozhodnuto, že na zbývající tupou programátorskou práci by měli Lišák a Králík stačit sami.

Datové struktury prezentace

Celou prezentaci si lze představit jako vertikální seznam jednotlivých bloků (dva bloky této nejvyšší úrovně nemohou být vedle sebe), kde blok je jakási samostatná část dokumentu, která se "stará sama o sebe", jejich společnou vlastností je, že jim při zobrazení náleží nějaká obdélníková oblast prezentace. Bloky mohou obsahovat další bloky a mohou být následujících typů (převzato od Lišáka): Každý blok má metody na nastavení maximální šířky, aby se vešel na canvas, vykreslení na určenou pozici, editaci, umí vrátit svou výšku a požadované odsazení od předchozího a následujícího bloku. Hlavně posledních dvou se využívá při zobrazování. Canvas, na který se kreslí, totiž neobsahuje celý dokument (složité na překreslování, moc velké,...), ale ve vertikálním směru jen právě viditelný výřez plus kousek pro plynulý scrolling, horizontálně ovšem celou šířku dokumentu. Prezentace na úrovni bloků nenese žádné informace o výškách bloků a jejich offsetu od začátku dokumentu, ale počítá je "on the fly" při pohybu viditelného výřezu po prezentaci.

Formátovaný text

Zdá se, že předformátovaný text, nadpisy i seznamy jsou speciálními nebo zjednodušenými případy bloku formátovaného textu, začínám tedy s ním. Blok tohoto typu odpovídá klasickému odstavci, tj. každý odstavec je zvláštní blok. Je tvořen opět vertikálním seznamem svých řádků, už zalomených na požadovanou šířku. Zalomení se provádí při načítání textu z parseru a při editaci. Řádek je opět objekt, který kromě hlavičky obsahuje hlavně v řetězci vlastní text a údaje o stylech (vnitřní formát řádku - viz dále). Řádek se, podobně jako blok (asi budou mít společného předka LayoutBox) umí zobrazit, editovat, vrátit svou výšku a zná své odsazení od ostatních (to je u všech řádků konstantní a stejné nahoře i dole). Dále umí vložit do svého textu řetězec a zalomit se. Zobrazení bloku vypadá tak, že blok dostane pozici, na níž se má zobrazit, odsadí se a zavolá zobrazení svého prvního řádku. Ten mu vrátí svou výšku k níž se přičte výška odsazení mezi řádky, blok zavolá zobrazení druhého řádku na nové pozici, atd. dokud se nevykreslí celý nebo nevyjde ze zobrazovaného výřezu. Při editaci opět volá editaci aktuálního řádku a pouze hlídá, který z nich to vlastně je (stojí na něm kursor). Pokud dojde k zalomení řádku, zalomený řádek vrací bloku přetečený text nebo požadavek na kus textu z následujícího řádku - pokud byl zkrácen. Blok jej opět předá následujícímu řádku, aby si ho přidal na začátek svého textu. Pokud se zalomí i tenhle, pokračuje dokud se text "neutřepe", nebo není nucen na konec přidat nový řádek. Žádosti o text z následujícího řádku se budou buď rekurzivně vnořovat (pak se zpracovávají LIFO), nabo řadit do nějaké pomocné fronty (zpracování FIFO). Je vidět, že zalamování je už poměrně komplikovaná činnost, kterou není vhodné provádět při každém vložení znaku nebo slova, ale řeší se buď timerem např. každé 2 sekundy (jako v AmiPro), nebo při přechodu na jiný řádek (Emacs, aj.).

Struktura řádku

Pozn.: zpřesnění a doplnění dokumentace o struktuře řádku atd. zde. Řádek jako potomek objektu LayoutBox (nebo TextBox, do něhož by spadaly i textové bloky) má výše zmíněné vlastnosti a metody. Jeho vnitřní reprezentace obsahuje kromě nějaké hlavičky (obsahující např. jeho šířku nebo výšku v pixelech, pokud bychom ji nepočítali průběžně), pomocí níž se na řádek odkazuje, hlavně řetězec, obsahující text řádku spolu s údaji o stylech (nakonec zvítězila idea "značek" nad objektovým modelem, protože se zdá, že jakkoliv složité řetězcové operace budou rychlejší než vzájemná volání kdovíjakých virtuálních metod objektů). Z důvodů, které uvedu později nebude řetězec "céčkový", tj. null terminated, ale "pascalský", tj. skutečná délka je uložena v hlavičce a samotný řetězec je pole, v první verzi třeba pevné velikosti (když text doleze na konec jeho fyzické délky, zalomí se i když mu bude viditelná délka ještě stačit), ve finální verzi pak podle potřeby dynamicky realokovaný. Údaje o stylech textu budou uloženy v řetězci pomocí značek (párových vždy pro začátek a konec stylu), což budou řetězce platformově závislé velikosti (na Linuxu sedmibytové), nesoucí informace jako "začátek kurzívy", "konec horního indexu", atd. První a poslední byte budou znaky začátku a konce značky (některé z řídících znaků), druhý byte bude samotné určení stylu, resp. druhu značky a zbývající místo je pro upřesňující "uživatelské" informace. Platformová závislost plyne z toho, že se tam musí vejít céčkový ukazatel, který může také obsahovat znak NULL a tím vylučuje použití céčkového řetězce. Řádky jsou navzájem "značkově autonomní", tj. na začátku každého řádku jsou uvedené všechny značky nutné k úplnému určení aktuálního stylu, tj. při požadavku na zjištění aktuálního stylu na pozici stačí procházet aktuální řádek a ne celý blok. Na konci řetězce budou zase značky všechny nastavené styly ukončující. Jednotlivé styly se tedy mohou libovolně překrývat ("brutální příklad takové situace" vypadá uvnitř: "brutální <začátek tučného>příklad <začátek kurzívy>takové <konec tučného>situace<konec kurzívy>", což HTML asi nepovoluje - Einsteine, těš se na parser:)), ale nedají se vnořovat, tj. situace, že po značce začátku nějakého stylu bude někde bez jeho ukončení následovat opět začátek téhož stylu, by neměla nastat. Druhy značek jsou:

Nástin postupů práce se značkami

Při vykreslování (nebo i při prostém procházení kursorem) bude řádek procházet svůj text, podle přeskakovaných značek nastavovat aktuální styl a průběžně počítat šířku a výšku zobrazovaného písma (variantou je údaje si pamatovat a přepočítávat při editaci - dobré na zobrazování, ale pro editaci pomalé). Pevná délka značek a znaky začátku a konce značky umožňují rychlé procházení oběma směry. Při editaci také může dojít ke slévání značek, tj. když se v textu setkají konec a začátek téhož stylu (spojení dvou textů s tímto stylem) nebo obráceně (smazání textu nějakého stylu - tady je třeba kontrolovat, jestli to nejsou právě vložené párové značky pro vkládání textu bez daného stylu). U hyperlinků je navíc nutná kontrola, jestli jde o stejný hyperlink. Pokud bezprostředně za sebou následuje více značek, berou se jako paralelní, tj. slévá se přes ně (u <začátek tučného><začátek kurzívy><konec tučného> se tučné písmo slije). Je třeba implementovat i opačný postup, tj. např. umět rozdělit řádek s vytvořením párových značek konce a začátku všech aktivních stylů v místě zlomu.

Další typy textových bloků

Nadpisy
To samé v bleděmodrém, jen defaultní text má jiné atributy (může být větší, tučný, s jiným fontface), blok je jinak horizontálně i vertikálně odsazený

Seznamy
Jedná se o seznam textových bloků nějak jinak odsazených a opatřených odrážkami, čísly nebo u seznamu definic složitěji umístěných. Každý podblok se o sebe stará sám, seznam se zajišťuje jenom pohyb mezi svými bloky při editaci.

Předformátovaný text
Opět podobné normálnímu textu, jen písmo je vždy monospace a nezalamuje se. Ještě nebylo vyřešeno, co s písmem, které přesáhne pravý okraj canvasu. Jestli canvas zvětšit (není VYSIWYG - papír na tiskárně roztáhnout nejde), písmo "wrapnout" (pokazí vložený ascii art), nebo prostě zbytek nezobrazit (ztrácí se informace).

Transientní ukazatele do textu

Na závěr ještě něco o slibovaných transientních ukazatelích do textu. To jsou ty, jejichž platnost se nemusí zachovávat během editace, zato jsou mnohem rychlejší než dříve popsané ukazatele perzistentní. Jsou tvořeny normálním céčkovským ukazatelem přímo na řádek (na hlavičku, nikoli na samotný řetězec - kvůli možnosti realokace) a offsetem udávajícím přímo počet bytů od začátku řetězce. Umožňují tedy i ukazovat dovnitř značky, ale v praxi by tato situace neměla nastat. Používají se u kursoru - přímo se účastní editace, takže jak ukazatel, tak offset se mohou podle prováděných změn snadno přizpůsobovat, na začátku a konci označeného textu - při editaci se označení zruší a ukazatele přestanou platit a konečně v undo, kde se takto ukládá i každá změna, takže postupné provádění undo opraví text pro značky v předchozím kroku (vypadá to podezřele, ale pokud bude dodrženo, že smazané objekty se pouze přepojí do kill ringu a nevytváří se nová instance - byť pomocí copy constructoru, funguje to).