Triki z PowerShellem #14 – Moja własna mała konsolka

Jak zdołałem (mam nadzieję) pokazać w kilkunastu notkach na temat PowerShella, narzędzie to pozwala na (pół)automatyczne wykonywanie wielu niekiedy skomplikowanych operacji, o ile tylko potrafimy je zakodować w postaci odpowiednich skryptów. Możemy więc ułatwić sobie życie szybkim uploadem na serwer FTP, wysyłaniem maili, a nawet (ło kurczę!) uaktualnianiem statusu na Twitterze :) Kiedyś możemy jednak chcieć takie pojedyncze rozwiązania złożyć w jakąś większą całość – na przykład w tytułową „małą własną konsolkę”.

O co chodzi? W skrócie: o coś w rodzaju własnego shella, przyjmującego ograniczony i ściśle określony zestaw poleceń, pozwalających na wykonywanie prostych czynności. Różnica względem normalnej powłoki jest taka, iż komendy te mają być w założeniu bardzo wysokopoziomowe – każda z opisywanych dotąd przeze mnie powershellowych „sztuczek” podpadałaby pod li tylko jedno polecenie, jeśli w ogóle. Najbliższym graficznym odpowiednikiem czegoś takiego jest pasek narzędzi lub skrótów do programów.
Aby nasz mały shell stał się faktem, potrzebujemy tylko kilku rzeczy, wśród których są:

• Pobieranie poleceń od użytkownika. Od tego mamy w PSh instrukcję Read-Host, nad którą nie ma co się rozwodzić w jakiś specjalny sposób. Ot, po prostu daje nam w wyniku linijkę tekstu wpisaną do konsoli. Jeśli użyjemy parametru Prompt, nasz shell może mieć ładny znak zachęty :)
• Wybór właściwej akcji w zależności od wpisanej komendy. Gdybyśmy pisali „normalny” program w „normalnym” języku programowania, wtedy pewnie dodalibyśmy bazowy interfejs dla komend, potem specyficzne klasy go implementujące, a potem jeszcze fabrykę tychże… No dobra, zdecydowanie przeginam ;-) W rzeczywistości zwykły switch jest tu niemal zbytkiem, zwłaszcza że w PowerShellu posiada on pożyteczny parametr -wildcard, pozwalający na dopasowanie ciągów znaków do wzorców zawierających symbole wieloznaczne (jak np. * lub ?). Dzięki temu można ograniczyć konieczność wpisywania całych nazw poleceń, jeśli jednoznaczna jest już sama pierwsza litera ("t*" zamiast "tweet", itp.).
• Uruchamianie programów z parametrami. Odpalenie aplikacji w powłoce takiej jak PowerShell jest oczywiście bardzo proste. Nie zapominajmy jednak, ze mamy tutaj dostęp również do API .NET-owego, w tym chociażby do klasy System.Diagonistics.Process i jej metody Start – czegoś w rodzaju arcyprzydatnej kiedyś funkcji Windows API o nazwie ShellExecute. Jeśli zaś chodzi o przekazywanie parametrów, to nie zapominajmy o metodach do obsługi stringów – cała klasa System.String jest przecież dostępna.
• Kontrola wejścia i wyjścia. Pod Windows nie jest to specjalnie powszechne, ale zdarzają się programy „w stylu uniksowym” – przyjmujące dane ze standardowego wejścia i wypisujące wyniki na standardowe wyjście. Pamiętajmy, ze przy pomocy potokowania (operator pionowej kreski |) możemy sobie z takimi aplikacjami radzić. PowerShell jest zresztą dobrym narzędziem do tworzenia używalnych front-endów do tego rodzaju programów.
• Pobieranie kodu wyjścia programów. W starych plikach .bat można było (hmm… w sumie to nadal można) korzystać ze zmiennej %ERRORLEVEL%, zawierającej kod wyjścia ostatnio uruchomionego programu. W PSh. jej odpowiednik ma bardziej opisową nazwę: $LASTEXITCODE. Przypomnieć warto, że dla kodów wyjścia wartością oznaczającą poprawne wykonanie programu jest zero.

Składając te elementy w całość, możemy utworzyć shella z wygodnym dla nas zestawem poleceń. Kto wie, może będzie on nam odpowiadał bardziej niż pełne ikonek, kolorowe paski narzędzi :)

Równoczesne zastępowanie kilku fraz w tekście

Łańcuchy znaków w językach programowania udostępniają zwykle operację zamiany wszystkich wystąpień jednego podciągu na inny. Nawet jeśli tak nie jest (co dotyczy chociażby C++, jak zwykle), możliwe jest jej łatwe zaimplementowanie przy pomocy prostszych funkcji (jak choćby std::string::find).
Gorzej jest z nieco bardziej skomplikowaną procedurą zastępowania kilku fraz naraz. Zaznaczam od razu, że nie jest to wcale równoważne wywołaniu funkcji typu Replace parę razy dla różnych argumentów. Jeśli bowiem zastąpimy w tekście X₁ przez Y₁, a w wyniku X₂ przez Y₂, to możemy otrzymać inny rezultat niż przy dokonywaniu obu zamian równocześnie - wystarczy, że Y₁ będzie w sobie zawierał ciąg X₂. W celu uzyskania poprawnego wyniku należy wszystkie zamiany przeprowadzać jednocześnie.

Prosta implementacja takiej operacji może się sprowadzać do przeglądania tekstu w poszukiwaniu któregoś z podciągów do zastąpienia, a następnie dokonania faktycznej zamiany dla tego z nich, który został wykryty najwcześniej w stosunku do aktualnej pozycji w tekście. Należy następnie przesunąć się tuż za znalezioną frazę i działanie powtórzyć - i tak aż do końca tekstu. W C++ wygląda to wszystko mniej więcej tak:

Jeśli tekst, na którym operujemy, ma długość n, a fraz do wyszukania i zastąpienia jest k, to w najgorszym przypadku całość może zabrać czas O(kn). Wymagałoby to jednak dość specyficznych danych, więc w praktyce nie musi być aż tak źle :) Dla lepszych rezultatów - zwłaszcza przy "obrabianiu" większej liczby tekstów tym samym słownikiem fraz - należałoby pewnie użyć specjalistycznych struktur danych, np. drzew prefiksowych (trie).

Zasada gołębiej dziury

Dzisiejsza notka będzie o pewnej matematycznej ciekawostce, która pokazuje, że nawet pozornie oczywiste stwierdzenie mogą mieć daleko idące konsekwencje, jakich nie da się na pierwszy rzut oka przewidzieć. Mamy mianowicie pewną kombinatoryczną regułę, mówiącą (w jednej z wersji), że:

Jeżeli n obiektów umieścimy w m < n pudełkach, to znajdzie się pudełko zawierające więcej niż jeden obiekt.

Zaskakujące, prawda? ;-) Wydaje się, że niewiele jest rzeczy bardziej oczywistych. A jednak powyższe twierdzenie doczekało się swojej własnej nazwy - i to nawet takiej, która uwzględnia nazwisko odkrywcy! W języku polskim mówimy mianowicie o zasadzie szufladkowej Dirichleta, a analogią jest podobno układanie skarpetek w szufladach. W angielskim z kolei używa się do tego... gołębi, a reguła jest znana jako pigeonhole principle - w dosłownym tłumaczeniu 'zasada gołębiej dziury'.

Co jest niezwykłego w tak prostej obserwacji? Otóż jej wyjątkową cechą jest to, że stosuje się do wręcz nieograniczonego spektrum zjawisk różnego typu i wielu dziedzin, pozwalając udowadniać prawdziwość mnóstwa czasami zaskakujących stwierdzeń. Ich ciężar gatunkowy może się wahać od zabawnych, aczkolwiek pouczających, aż do zupełnie kluczowych dla niektórych dziedzin nauki. Oto przykłady:

• Struktury danych oparte na haszowaniu zawsze muszą uwzględniać metody rozwiązywania kolizji. Ten znany fakt jest konsekwencją tego, iż liczba możliwych kluczy n przekracza (zazwyczaj znacznie) rozmiar pojemnika m, więc nawet przy najlepszej funkcji haszującej znajdą się takie dwa klucze, które zostaną przyporządkowane w to samo miejsce.
• W pudełku jest 5 czarnych i 5 białych kul. Ile co najmniej kul musimy wybrać, żeby wśród nich znalazła się para tego samego koloru? Nie, wcale nie sześć - wystarczą trzy. Skoro mamy m = 2 kolorów, to już n = 3 kul gwarantuje, że będzie wśród nich para tego samego koloru.
• Wśród wszystkich obecnie żyjących ludzi co najmniej dwójka wypowiedziała w ciągu swojego dotychczasowego życia identyczną liczbę słów. Nawet gdyby ktoś paplał 24 godziny na dobę z prędkością jednego słowa na sekundę, w ciągu jednej doby nie powie ich więcej niż 86.400. Najstarszy człowiek miał/ma około 130 lat, w związku z czym ilość możliwych wartości dla wielkości 'liczba wypowiedzianych słów' to ok. 86.400 * 365,25 * 130, czyli nieco ponad 4 miliardy. Ponieważ na Ziemi żyje obecnie ponad 6 miliardów ludzi - czyli więcej - na mocy zasady szufladkowej wnioskujemy, że musi istnieć co najmniej dwójka, która wypowiedziała w ciągu życia tę samą liczbę słów.
• Jeśli algorytm kompresji bezstratnej rzeczywiście kompresuje (tj. zmniejsza objętość przynajmniej jednego pliku), to istnieje dla niego taki plik, który po "kompresji" będzie większy niż przed nią. Innymi słowy, nie ma doskonałych metod kompresji i nawet rosyjscy hakerzy nic na to nie poradzą :) Jest to bowiem bezpośrednia konsekwencja zasady 'gołębiej dziury'.
  Powiedzmy, że najmniejszy plik faktycznie kompresowany (tj. zmniejszany) przez nas algorytm ma początkowy rozmiar , zaś po kompresji jest to już , gdzie . Istnieje skończona liczba plików rozmiaru , którą oznaczymy . (Jeśli na przykład jest to rozmiar w bajtach, to ). Z założenia żaden z tych plików nie zmienia rozmiaru podczas kompresji, więc ich wielkość po skompresowaniu to również . Oznacza to jednak, że tych plików to wyniki kompresji plików, bo także (większy niż ) jest kompresowany do jednego z tych plików. Ponieważ , na mocy zasady szufladkowej istnieją dwa takie pliki - mianowicie i jakiś plik rozmiaru - które są kompresowane do tego samego pliku wyjściowego. Jeśli tak jest, to algorytm nie może być bezstratny - czyli mamy sprzeczność, Q.E.D. :-)

Całkiem sprytne, nieprawdaż? Jak na zupełnie "oczywistą oczywistość", zasada szufladkowa wykazuje niezwykłą użyteczność w wielu zaskakujących momentach. Warto o niej pamiętać nie tylko podczas poszukiwań pary pasujących skarpetek :)

C# i zbiory

Dłuższy czas temu popełniłem notkę o tym, że w C# (lub szerzej: w .NET) brakuje pewnych struktur danych, które niekiedy bywają przydatne. Jedną z nich jest bardzo prosty rodzaj pojemnika: zbiór.
Zbiory (w programowaniu) to kontenery, które przechowują elementy niepowtarzające się i umożliwiają szybkie sprawdzenie, czy jakaś wartość do danego zbioru należy. 'Szybkie' oznacza tu złożoność logarytmiczną (względem rozmiaru pojemnika) lub lepszą. Podstawowa różnica w stosunku do zbiorów matematycznych jest natomiast taka, iż te drugie mogą zawierać elementy różnych rodzajów, podczas struktura danych o tej nazwie przechowuje obiekty jednego typu.

W C++ zbiór implementuje STL-owa klasa std::set. W C# z kolei - jak napisałem na początku - jej odpowiednika nie ma. Takowy trzeba by dopiero napisać, co w przypadku tego języka jest raczej zaskakujące :) Tym niemniej da się to zrobić w miarę prosto, używając do tego... klasy Dictionary. Pomysł polega na tym, żeby całkowicie zignorować tę jej część, która kluczom w słowniku pozwala przypisywać wartości. Zamiast tego interesują nas wyłącznie same klucze jako elementy naszego zbioru. Zarys klasy opartej o tę ideę może wyglądać choćby tak:

Skorzystanie ze słownika (klasy Dictionary) sprawia, że kluczowa operacja Contains (sprawdzenie przynależności) jest bardzo szybka. MSDN podaje, że wydajność odpowiadającej jej operacji słownikowej ContainsKey "zbliża się do O(1)". Mamy tu też oczywiście niezbędne metody do dodawania i usuwania elementów, a także kilka innych związanych z implementowanymi interfejsami ICollection i IEnumerable, które pozwalają na przykład na iterowanie po zbiorze pętlą foreach.
Można naturalnie jeszcze ulepszyć tę klasę, dodając nowe konstruktory, metody i implementując następne interfejsy (na przykład ISerializable). Nie jest to trudne, bo polega głównie na wywoływaniu odpowiadających metod obiektu Dictionary lub jego kolekcji kluczy. Dopiero operacje matematyczne - jak suma i iloczyn zbiorów - wymagałoby nieco większej ilości kodu.
Ale przecież dla chcącego nic trudnego :)

Szablony klas i funkcje zaprzyjaźnione

Chcę dzisiaj napisać o pewnego rodzaju "ciekawostce", związanej z dwoma pojęciami z tytułu notki, na którą natknąłem się jakiś czas temu. Po zredukowaniu nadmiaru szczegółów można przyjąć, że rzecz dotyczy sytuacji, w której mamy szablon klasy oraz zadeklarowaną wewnątrz niego funkcję zaprzyjaźnioną - na przykład przeciążony operator strumieniowy <<:

Funkcja jest zadeklarowana, lecz nie jest od razu zaimplementowana wewnątrz bloku class. Zamiast tego umieszczamy jej kod osobno:

co jest może trochę osobliwe, ale wydaje się poprawne. No właśnie; wydaje się. Próba użycia tak zdefiniowana operatora:

nie przeszkadza wprawdzie kompilatorowi, jednak linker ma poważne zastrzeżenia. Okazuje się, że funkcja operator << w wymaganej postaci nie jest zdefiniowana - czyli mamy zwyczajny unresolved external, aczkolwiek o niecodziennych przyczynach.

Przyznać muszę teraz, że nie jestem do końca pewien co do ich natury, jako że konsultacja z zaufanymi źródłami (w postaci książki C++. Szablony panów Vandevoorde'a i Josuttisa) nie dała jednoznacznej odpowiedzi, co tutaj tak naprawdę się dzieje. Przypuszczam, że ma tu miejsce pewien dziwnej interakcji między konkretyzacją szablonu klasy a deklaracją friend, która przy okazji jest też deklaracją funkcji operator <&lt. Mimo że nie stanowi ona części szablonu, owej konkretyzacji podlega, czego skutkiem jest stworzenie zwykłej (nieszablonowej) deklaracji:

Nie ma więc ona nic wspólnego z szablonem funkcji operator <<, który jest zdefiniowany później! W rzeczywistości wygląda zresztą tak, że ów szablon jest całkowicie pominięty przy kompilacji jako niewykorzystywany; to zapewne z powodu reguł przeciążania funkcji w C++, nakazujących najwyraźniej wybranie raczej funkcji nieszablonowej (o powyższej deklaracji) zamiast szablonu funkcji. A że przypadkiem funkcja ta nie ma implementacji... Cóż, kompilator nie ma obowiązku się o to martwić :)

Tyle moja teoria. Niezależnie od tego, czy jest ona prawdziwa czy nie, dobrze byłoby wiedzieć, jak z problemu wybrnąć. Naturalnym wyjściem jest przenieść kod funkcji tam, gdzie jego miejsce - czyli z deklaracji funkcji w klasie (opatrzonej słówkiem friend) uczynić też jej definicję. Faktycznie, to działa; najwyraźniej powstaje wtedy nieszablonowa funkcja o nagłówku danym wyżej, razem ze swoją implementacją - czyli wszystko jest w porządku.
Drugie rozwiązanie to opatrzenie deklaracji friend klauzulą template:

W tej wersji - jak sądzę - następuje zaprzyjaźnienie każdej specjalizacji klasy Foo z odpowiadającą jej specjalizacją metody operator <<. Oba szablony podlegają niezależnym konkretyzacjom, ale linker potrafi prawidłowo rozwiązać relację między nimi.

Uff, trochę to skomplikowane. Jak widać, z zaprzyjaźnianiem bywają problemy - i to nie tylko dlatego, iż "In C++ friends touch each other's private parts." ;) Dziwne efekty związane z szablonami i konkretyzacją potrafią bowiem skonfudować nawet doświadczonych programistów.

Dwukierunkowe funkcje i obiekty proxy

Jedną z pierwszych rzeczy poznawanych w trakcie nauki programowania jest sposób działania funkcji. Mam tu na myśli zupełnie elementarny fakt, iż funkcje przyjmują zero lub więcej argumentów na wejściu i produkują co najwyżej jeden rezultat na wyjściu. Niezachwiana pewność w tę własność funkcji może być potem mocno nadwątlona, jeśli poznamy języki o bardziej egzotycznym sposobie działania, jak na przykład Prolog; tam wszystkie parametry funkcji mogą przekazywać dane w obu kierunkach, dzięki czemu np. za dzielenie i łączenie ciągów lub list odpowiada jedna i ta sam funkcja.
Nie trzeba jednak uciekać tak daleko od starego dobrego programowania imperatywnego, żeby zaobserwować odstępstwa od reguły. Parametry mogą przecież służyć do zwracania wartości - dzieje się to przy pomocy słów kluczowych ref/out w C# lub zwykłych wskaźników/referencji w C++. Często zdarza się wtedy, że "normalny" rezultat zwracany przez funkcję służy jedynie przekazaniu informacji o ewentualnym błędzie.

Rzadsza sytuacja polega na tym, że wynik funkcji staje się jej argumentem wejściowym. Technicznie nie jest nawet możliwe, ale można tak traktować sytuacje, gdy rezultatem jest l-wartość (l-value), tj. obiekt, do którego można przypisywać:

Typowo jest to referencja (tutaj int&), a powyższa konstrukcja - poprzez swojej podobieństwo do indeksowania zwykłej tablicy - nie należy do wielce zaskakujących. Co jednak można powiedzieć o tej:

poza widocznym od razu faktem, że pochodzi ona z języka, którego rozwlekłość składni przyprawia o niestrawność? :) Mianowicie tutaj nie ma już oczywistych przesłanek co do tego, czym jest lewa strona. Widać bowiem, że możemy jej przypisać dłuższy podciąg niż oryginalny i zostanie on mimo wszystko poprawnie zastąpiony - nie jest to więc żaden prosty "wyrób wskaźnikopodobny". Może więc to po prostu feature akurat tego języka, którego nie da się zreplikować?...

Odpowiedź jest - jak można się domyślać, skoro o tym piszę - oczywiście negatywna :) Ażeby podobny efekt osiągnąć w C++, konieczne jest jednak zastosowanie techniki znanej jako obiekt pośredniczący - proxy. Powinien on zachowywać się jak zwykły rezultat funkcji, ale w razie potrzeby dawać również możliwość przypisywania do siebie. Naturalnie efekt takiego działania jest specyficzny dla konkretnej funkcji, która swoją drogą może być często zredukowana do samego tworzenia obiektu proxy:

Minimum, jakie rzeczony obiekt musi zapewniać, to operator przypisania oraz jakiś operator rzutowania, który pozwoli na "wyciągnięcie" rezultatu funkcji, gdy jest ona użyta w zwykły sposób:

Widzimy tutaj, że przy takim proxy nasza funkcja Mid użyta w zwykły sposób zachowuje się jak metoda substr. Gdy jednak umieścimy jej wywołanie po lewej stronie przypisania, zadziała metoda replace, służąca do zastępowania podciągu innym. W sumie więc poniższy kod:

będzie działał analogicznie do prezentowanego wyżej fragmentu w języku Visual Basic.

Opisana tu sztuczka nie jest oczywiście doskonała. Do pełni możliwości potrzebna jest jeszcze wersja read-only funkcji Mid, przyjmująca stałą referencję do stringa i wywołująca substr bezpośrednio, z pominięciem obiektu proxy. To jednak da się łatwo zauważyć.
Mniej widoczny jest natomiast fakt, że obiekt proxy, dodając kolejną warstwę niejawnych konwersji (tutaj: z siebie na string) może spowodować kłopoty tam, gdzie jedna niestandardowa konwersja jest już wykorzystywana. Dobry przykład to interakcja ze strumieniem:

która nie powiedzie, bo operator strumienowy << nie posiada wersji dla lewego prawego argumentu będącego std::stringiem, a jedynie dla const char* (co swoją drogą jest dość dziwne). Rozwiązaniem jest napisanie takowego dla samego obiektu proxy.

Zależności między projektami w Visual Studio

Zdarza się, że pracuje nad złożonym systemem, na który składa się kilka osobnych projektów. IDE znają dobrze takie przypadki i potrafią je obsługiwać - stąd chociażby pojęcie solution (dawniej workspace) w Visual Studio. Dla pojedynczych aplikacji i bibliotek wydaje się ono zbędne, jednak staje się nieodzowne wtedy, gdy nasze projekty zależą od siebie.

Typowa sytuacja to wspólna biblioteka (framework, engine czy co jeszcze kto woli) rozwijana razem z programami, które z niej korzystają. (W najprostszym przypadku to może być po prostu jakaś aplikacja testowa). Wówczas pojawiają się zależności między projektami na etapie ich budowania: wynik szeroko pojętej "kompilacji" jednego jest wejściem do procesu budowania innego. Jeśli nie poświęcimy temu faktowi należytej uwagi, to mogą nas czekać kłopoty. W najlepszym razie jest to konieczność wciskania F7 (Build Solution) więcej niż raz, aż do zbudowania wszystkich projektów. W gorszym - uruchamianie (i debugowanie!) aplikacji korzystającej z nieaktualnej, bo nieprzekompilowanej wersji biblioteki.

Zależności między projektami w procesie budowania da się na szczęście określić. W Visual Studio służy do tego opcja Project Dependencies z menu - a jakże - Project. Możemy w niej określić dla każdego projektu, z jakimi innymi projektami z tego samego solution jest on powiązany, czyli które z nich powinny być już wcześniej od niego zbudowane. Na podstawie tak podanej sieci zależności da się następnie określić właściwą kolejności "kompilacji" dla wszystkich projektów w danym solution. VS oczywiście to czyni, używając do tego zapewne sortowania topologicznego w analogiczny sposób jak dla kompilacji jednego projektu składającego się z wielu plików.