Struktury danych nieobecne w .NET

Programując z użyciem platformy .NET można niekiedy mieć wrażenie, że jest w niej niemal wszystko. Oczywiście takie przekonanie jest nietrwałe: wystarczy bowiem znaleźć coś, co być w niej mogłoby (a zwłaszcza coś, co występuje w innych, podobnych bibliotekach), a czego jednak nie ma. Nietrudno zauważyć, że takich rzeczy jest mimo wszystko większość – bo w sumie nie może być przecież inaczej :)
Niektóre braki są aczkolwiek bardziej dotkliwe niż inne. Należą do nich chociażby luki w systemie kolekcji obiektów, czyli – mówiąc ogólniej – wszelkiego rodzaju struktur danych. W .NET brakuje bowiem takich rzeczy jak:

Niedużo tego…

• Zbiory. Wprawdzie niemal każdy pojemnik zawiera metodę Contains o wiadomym przeznaczeniu, jednak tylko kontenery słownikowe sprawdzają unikalność umieszczanych w nich obiektów. Te zaś zasadniczo służą do czegoś innego: mapowania jednych obiektów na inne. Brakuje więc zwykłej, prostej klasy Set z operacjami dodawania, usuwania i wyszukiwania elementów – odpowiednika std::set z STL.
• Kolejki priorytetowe (priority queues). Tutaj znowu można je symulować przy pomocy klas typu SortedDictionary, które jednak nie są zasadniczo do tego przeznaczone. Kolejka priorytetowa powinna mieć przecież niemal identyczny interfejs do zwykłej kolejki FIFO (czyli głównie metody Push i Pop), bo różnica polega wyłącznie na porządku zwracanych elementów, określonym przez ich porównania.
• Kolekcje zbiorów rozłącznych (disjoint sets). Te dość specyficzne struktury danych są przydatne wtedy, gdy musimy szybko zorganizować kolekcję obiektów w osobne podgrupy wedle jakichś kryteriów. Można to oczywiście zrobić za pomocą dowolnych pojemników, tyle że będzie to nieefektywne. Dedykowana implementacja z użyciem wydajnych algorytmów (tzw. łączenia według rangi i kompresji ścieżek) byłaby znacznie bardziej na miejscu.
• Grafy. Wprawdzie grafy nie są aż tak często wykorzystywane, ale nie da się ukryć, że czasami ich użycie jest konieczne. Na pewno nie zaszkodziłoby posiadanie ich jako wbudowanego feature‘a w każdej bibliotece struktur danych. Zwłaszcza z gotowym zestawem podstawowych algorytmów grafowych.

Tę listę można by oczywiście ciągnąć bardzo długo, ale zdecydowałem się ograniczyć do tych czterech rzeczy z dwóch powodów. Po pierwsze, przynajmniej raz zdarzyło się, że potrzebowałem którejś z wymienionych tutaj struktur w .NET i byłem zmuszony poradzić sobie we własnym zakresie. Po drugie, bez problemu można podać przykłady innych bibliotek, języków czy środowisk, gdzie jedna z nich, większość lub nawet wszystkie są obecne. Najlepszym przykładem jest C++ (z STL) uzupełniony o bibliotekę Boost, który pod względem struktur danych prezentuje się w tej postaci naprawdę potężnie.
Nie widzę więc specjalnych usprawiedliwień dla faktu, że w .NET lista standardowych struktur prezentuje się nadzwyczaj skromnie. Może więc zamiast dodawać w nowych wersjach platformy kolejne wątpliwej jakości “usprawnienia” – jak wyrażenia lambda wbudowane w C# czy zabawki typu LINQ – programiści Microsoftu zajęliby się raczej zaniedbanymi dotąd podstawami?…

Tej funkcji brakuje ‘n’

W dzisiejszych niebezpiecznych czasach niemal każdy program może stać się przedmiotem ataku, za pomocą którego można – jak to się zwykło mówić w żargonie speców od bezpieczeństwa – “wykonać dowolny kod” (execute arbitrary code). Chyba najbardziej znanym exploitem tego typu jest przepełnienie bufora (buffer overflow), które w najprostszym wypadku może dotyczyć na przykład takiej sytuacji jak poniższa:

Gdy bowiem bufor rezyduje na stosie, a jakaś funkcja przypadkowo “wyjedzie” poza jego zakres, możliwe jest nadpisanie innej części stosu. Jedną z nich może być odkładany przy wywołaniu każdej funkcji adres powrotu. Po zakończeniu działania kodu funkcji, adres ten jest zdejmowany ze stosu i program skacze pod uzyskane w ten sposób miejsce w pamięci. Dzięki temu wykonanie programu może wrócić do miejsca tuż za wywołaniem funkcji i kontynuować działanie. Jeśli jednak ów adres zostanie nadpisany przez exploit, możemy w rezultacie skoczyć pod zupełnie inny adres i wykonać dowolny – potencjalnie szkodliwy – kod.

Dlatego też nie należy nigdy ślepo zakładać, że przekazywane nam tablice będą zawsze wystarczająco duże na pomieszczenie rezultatów funkcji. Powinniśmy na to zwrócić baczną uwagę zwłaszcza wtedy, gdy mamy zapisać w buforze dane pochodzące z zewnątrz – z pliku, sieci, od użytkownika, itd. Pisząc funkcje operujące na buforach będących tablicami w C, powinniśmy więc zawsze dodawać do nich jeszcze jeden parametr: rozmiar przekazywanego bufora. Oczywiście nalezy potem dbać, aby go nie przekroczyć.
A co z już istniejącymi funkcjami C, jak sprintf, strcpy, gets?… Wszystkie aktualne dokumentacje do kompilatorów, w których funkcje te występują (MSDN, linuksowy man, itp.), solidnie przestrzegają przed potencjalnym przepełnieniem bufora, które może być skutkiem ich używania. Zwykle też podawane są bezpieczne alternatywy, do których przekazuje się rozmiar bufora: w Visual C++ są one oznaczone końcówką _s (np. sprintf_s), a w GNU GCC dodatkową literką n w nazwie (np. snprintf). To ich właśnie należy używać, jeśli występuje potencjalna możliwość przepełnienia bufora.

Wyjątkiem jest gets, której to… nie powinniśmy w ogóle używać :) Co ciekawe, tylko MSDN wspomina o jej bezpiecznym odpowiedniku (gets_s). Pod GCC funkcji gets po prostu permanentnie brakuje n ;-]

Wyjątki mają warstwy

Kiedy w kodzie zdarza się coś niedobrego, na co nie mamy natychmiastowego rozwiązania, zwykle rzucamy wyjątek. To nam odwija stos, wychodząc po kolei z głęboko zagnieżdżonych funkcji – aż w końcu natrafimy na handler, który potrafi rzeczony błąd obsłużyć. Odwiecznym problemem wyjątków jest to, gdzie należy tak naprawdę je łapać; zwykle bardzo łatwo jest umieścić kod ich obsługi na zbyt wysokim poziomie, tłumacząc się, że przecież “niżej” nic na ten błąd nie można było poradzić.
Faktycznie zaradzić wyjątkowi często nie można, ale prawie zawsze można w tym pomóc już na wczesnym etapie jego obsługi. Błąd gdzieś “w środku” powoduje bowiem niepowodzenie wywołania wszystkich funkcji po drodze, a każda z takich porażek jest specyficzna dla czynności, która dana funkcja wykonuje. Jeśli przykładowo chcemy odczytać jakiś parametr konfiguracyjny programu, który wymaga załadowania z pliku, to może się okazać, że tego pliku nie da się otworzyć. Wówczas odczytywanie konfiguracji nie powiedzie się – co samo w sobie jest błędem, ale także powoduje, że niemożliwe jest uzyskanie wartości żądanego parametru – kolejny błąd. Widać więc, że błędy-wyjątki mogą być dla siebie kolejno przyczyną i skutkiem.
Taka szczegółowa “historia błędów” jest przydatna, bo pozwala oddzielić informacje ważniejsze od mniej ważnych. Nasza aplikacja może na przykład w ogóle nie wiedzieć, że jej konfiguracja jest zapisywana w pliku (a nie np. Rejestrze) i dlatego wyjątek ‘Nie znaleziono pliku konfiguracyjnego’ powinien być przed nią ukryty. Trzeba go opakować w błąd wyższego rzędu.

Nazywa się to wewnętrznymi wyjątkami (inner exceptions) i jako wbudowany mechanizm występuje chociażby w .NET i Javie. Idea jest prosta: kiedy złapiemy wyjątek “z dołu”, którego nie możemy do końca obsłużyć, zapakowujemy go w nowy obiekt, sygnalizujący niepowodzenie na “naszym” poziomie kodu. Ten nowy wyjątek wyrzucamy dalej; może on potem podlegać bardzo podobnemu procesowi.
I tak w przykładzie z ładowaniem konfiguracji, próba odczytania nieistniejącego pliku skończy się w .NET wyjątkiem IOException, który zostanie pewnie natychmiast opakowany w FileNotFoundException. Funkcja odczytująca dane konfiguracyjne z pliku najpewniej sama wsadzi ten wyjątek w nowy, np. ArgumentException, co mówi wywołującemu, że przekazany argument – tu: nazwa pliku z konfiguracją – jest nieprawidłowy. W końcu, ponieważ nie będzie można odczytać żądanej wartości, funkcja która miała ją zwrócić może nas ostatecznie uraczyć wyjątkiem InvalidOperationException, zawierającym w środku wszystkie wymienione wcześniej błędy. Których było zresztą całkiem sporo :)
Gdy w końcu złapiemy cały ten wielokrotnie zapakowany wyjątek w innym miejscu, możemy dostać się do całego łańcucha przyczynowo-skutkowego, który powstał podczas odwijania stosu. W tym celu korzysta się z właściwości InnerException w .NET lub metody getCause w Javie – na przykład tak:

Zapewne jednak rzadko będziemy sięgali aż do samego dna – zwykle tylko w celach logowania. Dzięki odpowiedniemu opakowaniu możemy bowiem zająć się od razu sytuacją wyjątkową “najwyższego rzędu” – adekwatną do czynności, którą chcieliśmy wykonać (a nie tą pochodzącą z głębokich czeluści kodu niższego poziomu, od której wszystko się zaczęło).

Triki z PowerShellem #2 – Szybki upload

Oto zadanie: mamy plik, który chcemy komuś przesłać przez Internet i mieć przy tym jak najmniej zawracania głowy. Jest oczywiście e-mail, są komunikatory, podprotokół IRC-a o nazwie DCC serwisy typu RapidShare, itd. Każdy z tych sposobów wymaga jednak albo wymiany jakichś informacji typu adres czy numer identyfikacyjny, albo nie zawsze chce działać w różnych konfiguracjach sieci (zwłaszcza gdy jedna ze stron jest ukryta za NAT-em), albo… wymaga wpatrywania się w literki celem odróżnienia psów od kotów :)
Jeśli jednak dysponujemy serwerem FTP z zawartością dostępną przez HTTP (czyli po prostu hostingiem strony WWW), to możemy dzielić się plikami w prostszy i szybszy sposób. W tym celu posłużyć się można odpowiednim skryptem w PowerShellu, który potrafi samodzielnie połączyć się z serwerem FTP i wgrać na niego podany plik, a potem zwrócić jego URL. Następnie możemy przekazać go osobie, której chcemy przekazać plik.

Całkiem zmyślnie, prawda? Wystarczy jedynie odczytać lokalny plik, a następnie użyć .NET-owej klasy System.Net.FtpWebRequest w celu wykonania “żądania FTP” w postaci uploadu tegoż pliku na serwer.

Co jednak zrobić z takim skryptem, aby był użyteczny?… Jako że jego parametrem jest ścieżka do lokalnego pliku, który chcemy załadować, możemy użyć następującej komendy:

w celu jego wywołania – o ile potrafimy sprawić, by system Windows zamienił nam symbol zastępczy %1 na rzeczoną ścieżkę. Jest to możliwe przynajmniej na dwa sposoby:

1. Możemy dodać nowe polecenie do podmenu kontekstowego Wyślij do, wyświetlanego dla każdego pliku w Eksploratorze Windows. W tym celu wystarczy stworzyć plik wsadowy (.bat) w katalogu SendTo, zawierający powyższą komendę, i nazwać go odpowiednio intuicyjnie. Po odświeżeniu Eksploratora, we wspomnianym menu pojawi się nowa pozycja, której wybór uruchomi nam nasz skrypt dla wybranego pliku.
2. Innym wyjściem jest po prostu dodać nową akcję dla każdego typu plików, przez co będzie ona wyświetlania w głównym menu kontekstowym, obok innych: Otwórz, Edytuj, Drukuj, itd. Aby tego dokonać, najwygodniej jest po prostu otworzyć Edytor Rejestru i przejść do klucza HKEY_CLASSES_ROOT/*/shell. Tworzymy tam nowy podklucz, nazywając go jakoś odpowiednio (np. upload) i wpisując jako wartość domyślną tekst polecenia, który chcemy zobaczyć w menu (np. Upload). Następnie tworzymy tam podklucz command, ustawiając jego wartość domyślną na polecenia uruchomienia skryptu. Odświeżamy Eksplorator i mamy już nowe polecenie w menu kontekstowym.

Sprytne i wygodne. I kto teraz powie, że tylko w systemach linuksowych można bezustannie kombinować, by dostosowywać je do swoich potrzeb ;-)

PS. Użyty w skrypcie program clip jest bardzo prosty: kopiuje on po prostu swoje wejście do Schowka. Niestety, to malutkie narzędzie nie jest obecne w Windows XP. Nie ma tam więc prostego sposobu na wpisanie tekstu do Schowka z poziomu PowerShella. Alternatywą jest wypisanie URLa- do załadowanego pliku bezpośrednio w oknie konsoli PSh. Wystarczy po prostu zmienić clip na Out-Host, a także zmienić wywołanie skryptu, dodając parametr -NoExit:

To sprawi, że o wykonaniu operacji konsola PowerShella pozostanie otwarta wraz z wypisanym w niej URL-em, który można z niej skopiować.

Artykuł o odśmiecaniu pamięci w C++

W przypływie weny twórczej zrealizowałem pomysł na artykuł, który dotąd znajdował się na szczycie kolejki priorytetowej takich pomysłów. Opisuje on, jak można uzupełnić język C++ o prosty mechanizm odśmiecacza pamięci (garbage collector – GC), czyli modułu zajmującego się automatycznym zwalnianiem nieużywanych obiektów. Osoby programujące choć przez chwilę w Javie czy .NET wiedzą, że obecność GC jest bardzo wygodna, lecz dopóki nie powstanie standard C++0x, w naszym ulubionym języku programowania mechanizm nie będzie domyślnie obecny.

W artykule opisuję, jak można to naprawić, pisząc własną, prostą implementację odśmiecacza pamięci w C++. Zainteresowanych zapraszam do lektury – mam nadzieję, że warto :)

• Prosty garbage collector w C++

Cztery rodzaje operatora new

Do alokowania pamięci (albo raczej: tworzenia obiektów na stercie) służy w C++ operator o wiele mówiącej nazwie new. Chociaż jest on powszechnie znany i nieustannie używany przez każdego programistę C++, pewni nie wszyscy wiedzą, że występuje on nie w jednej, ale aż w czterech odmianach, z których każda różni się sposobem wywołania!
Oto krótki przegląd:

• “Zwykły” operator new (co obejmuje też formę tablicową new[]) jest oczywiście najbardziej znany i najczęściej stosowany. Warto pamiętać, że zazwyczaj robi on dwie rzeczy: oprócz alokacji pamięci wywołuje też konstruktor dla tworzonego obiektu (lub obiektów w tablicy), któremu możemy też podać parametry.
• Przeciążony operator new zmienia natomiast swoje zachowanie tylko w zakresie tej pierwszej czynności, czyli samej alokacji. Ciekawostką jest to, że możemy wyposażyć go (tj. sam operator new) w dodatkowe parametry – czyli przeciążyć go w pełnym znaczeniu tego słowa! Typowym przykładem, jaki się tutaj zwykle przytacza, jest następująca funkcja:
  1. void* operator new (size_t bytes, char fill)
  2. {
  3.     // alokacja z wypełnieniem podanym wzorcem
  4.     char* p = ::new char[bytes];
  5.     for (size_t i = 0; i < bytes; ++i) p&#91;i] = fill;
  6.     return p;
  7. }&#91;/cpp]
  8. która tworzy przeciążoną wersję operatora <code>new</code>, wypełniającą świeżo zaalokowaną pamięć podanym wzorcem:
  9. [cpp]char* ptr = new('X') char[10];  // alokuje tablicę charów wypełnioną X-ami

  Naturalnie możliwe są bardziej przydatne zastosowania. Jeśli mamy na przykład kilka rozłącznych ze sobą stert, to możemy tak napisać operator new, by poprzez dodatkowy argument pozwalał decydować o tym, którą z nich chcemy w danym przypadku wybrać.

• new nierzucający wyjątków. Domyślnie alokacja za pomocą new rzuca wyjątek std::badalloc, jeżeli operacja się nie powiodła (zwykle z powodu braku pamięci). To zachowanie – wymagające do poprawnej obsługi bloku try-catch może nam się nie podobać, ale na szczęście można je zmienić. Wystarczy użyć wersji new z dodatkowym parametrem std::nothrow:
  1. int* pEnormousArray = new(std::nothrow) int[0xffffffff]; // "tylko" 4GB :)

  Wymaga to jeszcze dołączenia standardowego pliku nagłówkowego o wielce trafnej nazwie new.

• Ostatni rodzaj zwie się placement new, co nie ma żadnego specjalnie dobrego tłumaczenia na język polski. Użycie tego operatora wymaga podania wskaźnika na już zaalokowany kawałek pamięci. Działanie operatora new ogranicza się wtedy do skonstruowania obiektu w tym właśnie miejscu, na które pokazuje przekazany wskaźnik. Tak więc w tym przypadku new tak naprawdę niczego nie alokuje; jest to po prostu najzupełniej legalny sposób na wywołanie konstruktora bez robienia czegokolwiek innego. Jakkolwiek może to się wydawać przydatne, zdecydowanie odradzam korzystania z tego mechanizmu w sposób nieprzemyślany, bo można przy tym popełnić “ciekawe” błędy.

Mamy więc aż cztery różne warianty new, ale raczej nie powinno to rodzić dylematów w rodzaju “Który z nich wybrać?”. W praktyce i tak nieczęsto zachodzi potrzeba skorzystania z któregokolwiek poza pierwszym. Co nie znaczy rzecz jasna, że nie warto znać pozostałych – podobnie jak całej masy innych kruczków języka C++ :]

O układaniu kontrolek

Najprostszym sposobem na rozmieszczanie kontrolek w oknie programu jest oczywiście… podanie ich pozycji i rozmiarów dosłownie. Ta metoda sprawdza się dobrze jednak tylko w prostych przypadkach: gdy mamy stałą (i raczej niewielką) liczbę obiektów, gdy rozmiary okna są stałe, gdy nie dostosowujemy rozmiaru interfejsu do rozdzielczości ekranu, itd. W wielu przypadkach to jednak nie wystarcza i dlatego systemy GUI oferują też inne narzędzia pozycjonowania elementów interfejsu. Niektóre z nich są całkiem pomysłowe. Oto kilka przykładów:

• 
  Przykład dokowania

  Dokowanie (docking), zwane też wyrównywaniem (align). Polega to na “przyklejeniu” kontrolki do którejś z krawędzi nadrzędnego pojemnika (np. okna) w jednym wymiarze oraz do obu krawędzi w wymiarze prostopadłym. Komponentowi pozostaje wówczas jeden stopień swobody. Przykładowo, kontrolka zadokowana po lewej stronie może się jedynie rozszerzać w prawo (lub zmniejszać w lewo), zaś jej górna i dolna krawędź pokrywają się zawsze z odpowiednimi krawędziami zawierającego ją pojemnika.
  Ten sposób pozycjonowania jest idealny chociażby dla pasków stanu (status bar), które zawsze umiejscowione są w dolnej krawędzi okna.

• 
  Ustawianie zakotwiczania
  w Visual Studio

  Zakotwiczanie (anchoring) polega z kolei na ustawieniu stałej odległości pewnych krawędzi kontrolki od odpowiednich krawędzi kontrolki nadrzędnej. Domyślnie na przykład każdy komponent jest zakotwiczony z lewej i z góry. Gdy zmieniamy rozmiar zawierającego go okna, dystans między lewą krawędzią tegoż okna i lewą krawędzią kontrolki pozostaje stały; podobnie jest z górnymi brzegami. Zmieniając ustawienia zakotwiczania możemy uzyskać efekt kontrolki “wyrównanej” w podobny sposób jak tekst w edytorze, np. do prawej strony okna zamiast do lewej.
  Anchoring można uznać za nieco lepszą wersję dokowania, ale w istocie różni się on od niego dość znacznie (zwłaszcza jeśli dokujemy wiele kontrolek po jednej stronie). Jest on jednak przydatny wtedy, gdy kontrolka ma w określony sposób zmieniać rozmiar wraz z oknem.

• 
  Układ typu flow

  Układy (layouts) kontrolek. Są to bardziej wyspecjalizowane narzędzia, których jedynym zadaniem jest układanie elementów interfejsu w określony sposób. Do najbardziej przydatnych należy układ typu flow oraz układ tabelkowy. Ten pierwszy polega na rozmieszczaniu kontrolek po kolei (w ustalonym porządku) tak, jak wypisuje się tekst w kolejnych wierszach. (Jak widać, analogie tekstowe w projektowaniu interfejsu pojawiają się całkiem często ;]). Z kolei układ tabelkowy, jak nazwa wskazuje, dzieli zadany obszar na wiersze i kolumny tak, że w każdej z powstałych w ten sposób komórek mieści się dokładnie jedna kontrolką i wypełnia ją całkowicie.
  Układy mają spore zastosowanie zwłaszcza wtedy, gdy rozmieszczane kontrolki są tworzone dynamicznie w trakcie działania programu. Potrafią wówczas zaoszczędzić dużo pracy z ręcznym przeliczaniem ich pozycji i/lub rozmiarów.

To stwierdzenie odnosi się zresztą do każdego z tych trzech sposobów na określanie wymiarów elementu interfejsu. Obecnie bardzo często okazuje się, że nawet stosunkowo zaawansowany układ kontrolek, który musi dostosowywać się do zmian rozmiaru okna, da się stworzyć bez obsługiwania zdarzeń typu OnResize i ręcznego rozmieszczania komponentów. A to może oszczędzić kilku kłopotów i pozwala łatwiej skoncentrować się na tych częściach programu, których wprawdzie nie widać, ale które są o wiele ważniejsze :)