Zalamovanie riadkov

Na prvý pohľad sa môže zdať, že implementácia zalamovania riadkov v editore je triviálna. Tiež som si to myslel...

Prečo zalamovanie?

Zalamovanie pri programovaní nie je nijak kritické, často je lepšie keď je vypnuté. Avšak pri písaní dokumentov, či už v HTML, alebo reStructuredText, LaTeX-e, MarkDown-e, je veľmi dôležité.

Nemám rád výmysly ako Microsoft Word. Mojím snom je používať klasický plain-textový editor na písanie akejkoľvek dokumentácie. To vyžaduje ako dobrý formátovací jazyk, tak editor, ktorý dokumenty dokáže dobre zobrazovať.

Požiadavky

Ako je našim dobrým zvykom, pred implementáciou sme zosumarizovali požiadavky toho čoho má byť zalamovanie schopné.

• Dynamické zalamovanie – text je zalamovaný na okraji editora, podlieha teda veľkosti okna.
• Fixné zalamovanie – text je zalamovaný na fixne definovanej hranici, je teda možné text zalamovať napríklad po 80 znakoch bez ohľadu na rozmery editora
• Odsadenie zalomených riadkov – zalomené riadky sa odsadzujú o určitý počet znakov, alebo obrazových bodov
• Intype plne podporuje Unicode, treba ho teda podporovať aj v zalamovaní
• Čo najnižší overhead!

Unicode

Unicode je taká pandorina skrinka, alebo “malá sviňa” ak chcete. Dokáže veľmi rýchlo demotivovať, ak ju podceníte. Okolo Unicode existuje niekoľko mýtov. Najčastejším omylom býva:

V Unicode sú všetky znaky dlhé dva byty.

V súčasnosti existuje nepreberné množstvo kódových stránok (codepages) mapujúcich potreby niekoľko málo jazykov do obmezenej tabuľky (najčastejšie do jedno bytovej tabulky s max 256 hodnotami, pričom prvých 128 znakov je už okupovaných ASCII tabuľkou). Unicode sa snaží definovať jednu jedinú tabuľku pre všetky jazykové systémy.

Vo svojom základe je Unicode tabuľkou tzv. code-points:

U+0041 "Latin Capital Letter A"
U+03BE "Greek Small Letter Xi"
U+1D176 "Musical Symbol End Tie"

V začiatkoch Unicode bolo definovaných približne 55000 code-pointov na ktoré vtedajšie kódovanie UCS-2 celkom stačilo. Dodnes však platíme za krátkozrakosť. Pretože vo verzii 4.0 definuje Unicode 96 382 code-pointov. Tož a sme v pérdely pane hrábě.

Situáciu zachraňovalo kódovanie UTF-16, ktoré síce stále používa 16-bitové hodnoty, ale pre znaky od 0x10000 do 0x10FFFF sú potrebné dve 16-bitové hodnoty reprezentujúce tzv. Surrogate Pair. Ergo, UTF-16 nemá zaistené mapovanie 1 znak na 1 hodnotu.

Intype používa interne kódovanie UTF-16, ergo 16-bitové kódovanie. V pohode pracuje so surrogate pairs, ale stále je tu pár malých svíň, ktore treba zohladniť pri zalamovaní.

Algoritmus

Vo všeobecnosti zalamovanie funguje nasledovnie:

1. Vezmi riadok textu
2. Nájdi poslednú hranicu slova
3. Ak je hranica slova, zalom
4. Ak nie je, rozdeľ slovo na hranici
5. Opakuj od bodu 2. kým neskončí riadok
6. Opakuj od bodu 1. kým sú riadky

Predtým ako sa vrhneme na rozpis jednotlivých bodov, je potrebné ešte spomenúť jeden detail: vrámci jedného riadku môžete mať hneď niekoľko fontov. Či už tučné, naklonené, alebo väčšie, menšie, rez z úplne inej rodiny, alebo dokonca text písaný zprava-doľava (RTL).

Na spracovanie takéhoto maglajzu sa používajú tzv. text runs. Text runs sú kusy textu s jedným fontom a jedným smerom (LTR alebo RTL). Tým sa algoritmus komplikuje. Je nutné iterovať cez text-runs a kontrolu smeru v ktorom sa text zobrazuje.

Hranice slov (word boundaries)

V prvom rade je potrebné vedieť kde sa hranice slov nachádzajú. V jazykoch používajúcich latinku sú pravidlá pre nás všetkých jasné. Čo ale s thajštinou, arabštinou, alebo japonštinou? Tam sa už vedomosti akosi vytrácajú a mlžia. Unicode je nebezpečný.

Naštastie existuje hneď niekoľko knižníc, ktoré sa o Unicode dáta dokážu postarať a hranice slov nájsť. V Intype používame knižnicu Uniscribe, ktorá je štandardnou súčasťou systému Windows. Tá pomáha.

Rozseknutie slova (word break)

S rozseknutím slova je už trošku viac problémov. Je potrebné násť najvhodnejšie miesto v slove v ktorom sa rozseknutie môže udiať. Mimo surrogate pairs, jeden code-point stále nie je to čo by sa dalo nazvať znakom. Predstavte si, že aj dlhé Á sa môže zapísať:

• Jednou hodnotou Á (obyčajne používané v systémoch Windows):

  U+00C1 LATIN CAPITAL LETTER A WITH ACUTE
  

• Dvomi hodnotami A´ (obyčajne používaný zápis v Mac OS X):

  U+0041 LATIN CAPITAL LETTER A
  U+00B4 ACUTE ACCENT
  

A rozhodne si nemôžeme dovoliť ukrátiť dlhé Á o jeho dĺžeň. Tu nastupujú na scénu clusters a glyphs. Glyph je asi najbližšie k tomu ako vizuálne vyzerá jeden code-point. Glyphy sú definované v používanom fonte. Spracovávaním reťazca code-pointov sa vytvára reťazec glyphov, teda indexov do samotného fontu.

Dlhé Á je (v druhom prípade) zložené z dvoch glyfov – zo znaku A a z dĺžňa. Tieto dva glyphs tvoria jeden cluster – nedeliteľnú jednotku (z pohľadu implementácie zalamovania a zobrazovania). Čiže pri zalamovaní je bezpečné zalomiť pred alebo za cluster-om.

Right-To-Left (šľak ma ide trafiť)

Aby toho nebolo málo. Niektoré jazyky (pravda Bers) sa vykresľujú zprava doľava, teda opačne ako to čo je štandardom u nás. Typickým príkladom pre RTL je arabština (nečudujem sa, že sa tak búria, tiež by mi z toho šibalo). Ak rozlomíte arabské slovo, jeho pravá časť ostáva na tom istom riadku a ľavá sa presúva do ďalšieho. Lalalala.

Optimalizácie

Je jasné, že si Intype nemôže dovoliť rozlámať celý dokument po načítaní. Unicode dáta, ich získavanie a zalamovanie, by zaberali príliš veľa času a pamäte. Je kritické aby bolo zalamované iba to čo je naozaj potrebné, ideálne iba to čo užívateľ vidí (plus-mínus jedna obrazovka ako záloha).

Na optimalizáciu sa používa zmeska cache, indexovaných tabuliek a pár očných klamov. Ale o tých neskôr.

Nabudúce ukážem ako bude zalamovanie vyzerať v Intype. Osobne som pár z jeho vlastností márne hľadal v iných editoroch a dúfam, že vás ako používateľov nadchnú tak ako mňa.