Uśmiechnij się!

Włożyłem dużo pracy w funkcję, której nawet nie używam: emotikony graficzne. Jak zazwyczaj, mały problem przerodził się w duże przepisywanie kodu. Miałem za zadanie poprawić regresje względem Pidgina 2.x.y, więc zabrałem się za nie działające zdalne emotikony. To funkcja, która pozwala dodawać do programu własne emotikony, których później można używać w rozmowie. Jeżeli wyślemy jakąś do znajomego, który nie ma jej na swoim komputerze, ta zostanie automatycznie przesłana. W przypadku protokołów nie wspierających tej funkcji, zamiast obrazka zostanie wyświetlony jej tekstowy odpowiednik.

Kod odpowiedzialny za obsługę emotikon był potworny. Już w gałęzi 2.x.y był trochę bałagan, ale po zmianie GtkIMHtml na WebKitGTK jako komponentu do wyświetlania wiadomości, zaczęło być tragicznie. Problem leżał w tym, że stary kod parsowania wiadomości był zoptymalizowany dla GtkIMHtml. Był totalnie niekompatybilny z WebKitGTK, więc student GSoC, który się tym zajmował, napisał swój własny, prowizoryczny parser. To przelało czarę goryczy w jakości tego kodu.

Obrazki w wiadomościach

Zarówno GtkIMHtml jak i WebKitGTK używają libpurplowych „stored images” aby przechowywać obrazki dla emotikon. To jest ogólna struktura przechowująca nieprzetworzone dane plików z obrazkami, bez dekodowania właściwego obrazu. Jego głównym zadaniem było powiązanie tych danych z prostymi, globalnymi identyfikatorami liczbowymi. Dzięki temu można osadzać obrazki w HTMLu prostym kodem <img src="purple-image:5">. To całkiem wygodne, ale API było trochę bałaganiarskie. Nie było aż tak źle, ale i tak planowaliśmy przekonwertować ten kod na klasę GObject. Zamiast klonować stare rozwiązanie, zrobiłem to co zwykle: napisałem całkowicie od nowa klasę PurpleImage, dużo bogatszą, ale też łatwiejszą w użyciu.

Przykład rozmowy z użyciem zdalnych emotikon i obrazków

Klasa PurpleImage, poza funkcją wiązania zawartości obrazków z identyfikatorami, ma kilka nowych. Użytkownicy odczują najbardziej obsługę zdalnych obrazków. Można tu zdefiniować pusty obrazek i dostarczyć jego dane później. Od teraz, jeżeli otrzymamy wiadomość z osadzonymi obrazkami (niekoniecznie emotikoną), zostanie wyświetlona bez niego a obrazek zostanie wyświetlony, gdy będzie gotowy – zupełnie jak w przeglądarkach internetowych. Ma to duże znaczenie dla wtyczek protokołów: przy starym API, musiały czekać z wyświetleniem wiadomości na przesłanie obrazków, co mogło być kłopotliwe w implementacji. Teraz jest to obsługiwane w całości przez libpurple. Przy okazji wdrażania nowego rozwiązania naprawiłem obsługę osadzonych obrazków we wszystkich protokołach je wspierających.

Drzewa trie

Jak wspomniałem wcześniej, parser emotikon dla gałęzi 3.0.0 był prowizoryczny, a ten stary nie mógł działać z WebKitGTK. GtkIMHtml (komponent Pidgina 2.x.y, wbrew swojej nazwie z obszaru Gtk) pozwalał na dostęp do swojego mechanizmu parsowania, w którym można było przetwarzać osobno każdy literał w parsowanym HTMLu. W ten sposób, funkcja libpurple była wywoływana dla każdego wyrazu i jeżeli natrafiła na emotikonę – zastępowała ją obrazkiem. Takie sprawdzenie było dość szybkie, dzięki strukturze GtkSmileyTree, implementującej pewien rodzaj drzew trie.

Przykład drzewa trie

Drzewo trie jest strukturą do przechowywania wielu ciągów tekstowych i wyszukiwania ich po prefiksach. Główną ideą drzew trie jest łączenie podobnych ciągów na ich prefiksach i rozgałęzianie na dalszych, różniących się sufiksach. Jest to tylko bazowa struktura, która może być użyta do rozwiązywania różnych problemów. Rzeczywiście, jest użyta zarówno w starym GtkSmileyTree, jak i w moim nowym parserze, ale poza tym podobieństwem obie implementacje mają ze sobą mało wspólnego.

Zamiast pisać duży-ale-wydajny parser, zdecydowałem aby wydzielić całkowicie niezależną klasę PurpleTrie – algorytm wyszukiwania wzorców oparty o drzewa trie. Pozwala na wyszukiwanie wielu wzorców na raz w danym tekście, a także na użycie tej struktury wiele razy. A to wszystko w czasie liniowym! Szacując dokładniej, potrzebuje O(m) czasu aby zbudować drzewo wyszukiwania (gdzie m to sumaryczna długość wzorców) oraz O(n) czasu na wyszukiwanie (gdzie n to długość tekstu w którym szukamy). Częstotliwość występowania wzorców nie ma wpływu na te oszacowania. Najlepsze jest to, że ta struktura jest dostępna do użycia również przez wtyczki libpurple, nie tylko do parsowania emotikon.

Dla kontrastu, tymczasowa implementacja parsera emotikon nie była wcale skierowana ku wydajności. Czas wyszukiwania mógłby być oszacowany przez O(n * m * t), gdzie n to ilość emotikon, m to ich długość (zakładamy, że są równe – w rzeczywistości formuła powinna być bardziej skomplikowana) oraz t to długość wiadomości. Jest tak źle głownie dlatego, że każda obsługiwana (niekoniecznie użyta w wiadomości) emotikona jest parsowana osobno. Fragment m * t zależy od implementacji strstr, ale nawet dla tych bardziej wydajnych możemy znaleźć podobnie zły przykład kombinacji emotikon w wiadomości. Z tak słabą złożonością mogło być to wykorzystane nawet do ataku typu denial-of-service na komputer ofiary.

Co dalej?

W gałęzi 3.0.0 było bardzo dużo błędów związanych z emotikonami i obrazkami osadzonymi w wiadomościach. Nie opisałem ich tutaj wszystkich, ale mam nadzieję, że wszystkie poprawiłem. Można obejrzeć szczegóły mojej pracy w repozytorium, w commitach związanych z emotikonami, pomiędzy 302a7cb4c1ab a d598e7950c34. A teraz zajmę się odwiecznym problemem – wersją dla systemu Windows.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.