Parsowanie plików pcap w Haskellu

Dzisiaj przykład prostego parsowania w Haskellu. Zadanie to znalazłem na stronie firmy Tsuru Capital jako code sample do napisania, gdybyśmy ubiegali się o stanowisko programisty. Opis zadania znajduje się tutaj. Jest tam dostępny także przykładowy plik z danymi w formacie pcap.

W skrócie to co mamy zrobić to:

• wyciągnąć z pliku linie, które zaczynają się od znaków B6034,
• daną linię sparsować,
• i wypisać ją w ten sposób:
  

     @ ... @ @ ... @

To jak dokładnie wygląda linia danych jest opisane na stronie z opisem zadania. Generalnie wystarczy wypisać tylko część danych z linii oraz w nieco innej kolejności.
• uruchamiając nasz program z parametrem "-r" powinien on sortować dane po zawartej w linii informacji "accept-time". Dla ułatwienia podana jest informacja, że różnica między czasem wysłania pakietu (czyli pkt-time) a accept-time nigdy nie jest większa niż 3 sekundy.

No to zaczynamy. Na początku warto wspomnieć o pakiecie Network.Pcap, który ułatwi nam czytanie z takich plików. Jedyne co nam pozostaje zrobić to parsowanie linii, ewentualne jej sortowanie oraz wypisanie przeczytanych danych. Zacznijmy od zdefiniowania sobie głównych typów danych:

module Main where

import Network.Pcap
import qualified Data.ByteString.Char8 as BS

data MarketData = MarketData {
      issueCode  :: BS.ByteString
    , bids       :: [(BS.ByteString, BS.ByteString)]
    , asks       :: [(BS.ByteString, BS.ByteString)]
    , acceptTime :: AcceptTime
    }

data AcceptTime = AcceptTime {
      hh :: BS.ByteString
    , mm :: BS.ByteString
    , ss :: BS.ByteString
    , uu :: BS.ByteString
    }

Jako, że pakiet Network.Pcap dostarcza nam danych w ByteStringach to wszędzie będziemy ich używać. Na uwagę zasługują pola bids i asks w MarketData. Otóż są to pary, w których pierwsza wartość to cena a druga to liczba danego towaru. Stworzone wyżej typy danych reprezentują jedną linię w pliku z danymi. Teraz sprawmy aby się automatycznie dobrze wypisywały:

instance Show AcceptTime where
    show (AcceptTime h m s u) = (BS.unpack h) ++ ":"
                                              ++ (BS.unpack m)
                                              ++ ":"
                                              ++ (BS.unpack s)
                                              ++ "."
                                              ++ (BS.unpack u)

instance Show MarketData where
    show (MarketData i b a t) = (show t)
        ++ " " ++ (BS.unpack i)
        ++ " " ++ (drop 1 $ foldr (\(ty, pr) ac ->
            "@" ++ (BS.unpack ty) ++ "@" ++ (BS.unpack pr) ++ ac) [] b)
        ++ " " ++ (drop 1 $ foldr (\(ty, pr) ac ->
            "@" ++ (BS.unpack ty) ++ "@" ++ (BS.unpack pr) ++ ac) [] a)

W ten sposób wystarczy wywołać funkcję show na typie MarketData i otrzymamy linię opisaną w zadaniu.

Przechodzimy zatem do najtrudniejszej części czyli parsowania danych. W pakiecie Network.Pcap dostępna jest funkcja dispatch, która przyjmuje otworzony plik (może to być również gniazdo sieciowe), liczbę pakietów do przeczytania (w naszym przypadku -1 czyli cały plik) oraz funkcję, która będzie przetwarzać dany pakiet o typie PktHdr -> ByteString -> IO (). Zanim jednak przejdziemy do napisania funkcji parsującej przypomnijmy sobie warunek czytania danego pakietu. Otóż musi się on zaczynać od znaków B6034, a to z kolei oznacza, że mogą pojawić się pakiety, które tego warunku spełniać nie będą. W takim wypadku musimy je pominąć. Napiszmy więc funkcję sprawdzającą ten warunek i jeżeli on zachodzi to parsujemy daną linię i ją wyświetlamy, a jeżeli nie to nic nie robimy. Nazwijmy ją showData:

prefix :: BS.ByteString
prefix = (BS.pack "B6034")

showData :: PktHdr
         -> BS.ByteString
         -> IO ()
showData hdr dat = do
    let (_, _d) = BS.breakSubstring prefix dat
        (sec, msec) = (hdrTime hdr) `divMod` 1000000
    if (BS.length _d) > 0
        then putStrLn $ (show $ TOD (toInteger sec) (toInteger (msec*1000000)))
            ++ " " ++ (show $ parseData _d)
        else return ()

To wszystko co występuje przed wywołaniem funkcji parseData to wyświetlenie po prostu pkt-time, który nie jest zawarty w danych ale w nagłówku pakietu. Sprawdzanie odbywa się w ten sposób, że dzielimy linię na dwie części: tam gdzie występuje prefix i to co przed nim. Jeżeli uda się podzielić linię w ten sposób to znaczy, że możemy parsować:

parseData :: BS.ByteString
          -> MarketData
parseData line = MarketData (BS.take 12 l) _bids _asks (AcceptTime h m s u)
  where
    l = BS.drop 5 line
    (_bids, r1) = takeBids $ BS.drop 24 l
    (_asks, r2) = takeAsks $ BS.drop 7 r1
    (h, r3) = BS.splitAt 2 (BS.take 8 $ BS.drop 50 r2)
    (m, r4) = BS.splitAt 2 r3
    (s, u) = BS.splitAt 2 r4
 
takeBids :: BS.ByteString
         -> ([(BS.ByteString, BS.ByteString)], BS.ByteString)
takeBids bs = takeBids' bs (5::Integer)
  where
    takeBids' b n
        | n > 0     = let (_b, _r) = takeBids' (BS.drop 12 b) (n-1)
                      in (_b ++ [(BS.splitAt 5 $ BS.take 12 b)], _r)
        | otherwise = ([], b)
 
takeAsks :: BS.ByteString
         -> ([(BS.ByteString, BS.ByteString)], BS.ByteString)
takeAsks bs = takeAsks' bs (5::Integer)
  where
    takeAsks' b n
        | n > 0     = let (_b, _r) = takeAsks' (BS.drop 12 b) (n-1)
                      in ((BS.splitAt 5 $ BS.take 12 b):_b, _r)
        | otherwise = ([], b)

Funkcja parseData jest bardzo prosta. Pobiera ona kolejną konkretną ilość znaków z linii i wrzuca je odpowiednio do konstruktora MarketData. Np. jako pierwszy parametr konstruktor przyjmuje issueCode, który według opisu zadania ma długość 12 znaków. W tym celu najpierw pomijamy pierwsze 5 znaków warunkowych (czyli B6034) po czym bierzemy kolejne 12 właśnie jako issueCode itd. Na uwagę zasługują jeszcze dwie funkcje takeBids oraz takeAsks. Są one niemal identyczne - różnią się kolejnością dodawania czytanych elementów do listy. Pierwsza odwraca kolejność a druga pozostawia ją bez zmian. Obie natomiast czytają dane rekurencyjnie biorąc 12 znaków i dzieląc je na dwie listy od 1 do 5 znaku oraz od 6 do 12. Powtarzają tą czynność tak długo aż uzyskają 5 par danych (parametr n).

Pozostaje nam tylko dopisanie pozostałych funkcji odpalających cały mechanizm:

readQuote :: Bool
          -> PcapHandle
          -> IO ()
readQuote False h = dispatchBS h (-1) showData >> return ()
readQuote True h = return ()
 
main :: IO ()
main = do
    opt <- liftA parseOptions getArgs
    hdl <- openOffline $ filename opt
    readQuote (quoteOrder opt) hdl
 
data Options = Options { filename :: FilePath, quoteOrder :: Bool }

parseOptions :: [String]
             -> Options
parseOptions [] = Options "" False
parseOptions (x:xs)
    | x == "-r" = Options (head xs) True
    | otherwise = Options x False

Dodałem tu nowy typ danych Options, który odpowiada za parametry programu, takie jak nazwa pliku oraz czy ma być sortowany. Funkcja openOffline zwraca nam uchwyt do otworzonego pliku pcap, a funkcja readQuote przyjmuje jako parametr czy ma sortować dane (jeżeli tak to nic nie robi) i dalej wywołuje funkcję dispatchBS, która przetwarza dane wywołując showData na każdym pakiecie.

To by było na tyle. Sortowanie oczywiście pozostawiam czytelnikom do samodzielnej realizacji :)

Jakby jednak ktoś chciał zobaczyć jak ja wykonałem sortowanie danych to tutaj jest cały plik.