Pierwsze podejście do CSV

Jakiś czas temu zdenerwowałem się na to, że funkcja obsługująca csv w języku pecha (PHP) nie działa prawidłowo. Mógłbym napisać własny taki parser oczywiście, ale nie lubię pisać w tym języku, no ale czasami nie ma się wyboru (bo Python - czyli język w którym błąd wprowadza się przez użycie niewłaściwego edytora, który zrobi własne formatowanie kodu, to żaden wybór - ktoś projektując ten język zrobił coś przed czym przestrzegał Albert Einstein "Wszystko powinno być zrobione tak prosto jak się da, ale nie prościej" - tu niestety ktoś zrobił prościej... Wiem, wiem - są dywagacje, czy to rzeczywiście Einstein był autorem tego określenia i czy dokładnie w tych słowach, ale chodzi o sedno stwierdzenia, z którym się zgadzam - zawsze gdy chciałem coś zbytnio uprościc, działało to źle)

No ale... to nie pora na żale :) Wracam więc do tematu.
Po rozwiązaniu problemu naszedł mnie pomysł, by może właśnie pokazać, jak napisać taki parser. Jednak to byłoby za proste. Taki parser to nic trudnego (co zaraz udowodnię w przykładowym kodzie). Z drugiej strony to dobry punkt wyjściowy, by poćwiczyć optymalizacje poprzez użycie odpowiednich algorytmów i struktur danych, oraz spojrzenia na problem w sposób szerszy, czyli projektowania bardziej uniwersalnego interface'u. I tą drogą zamierzam podążyć. Zaczniemy od:

1) Zdefiniowania problemu

Celem naszym jest przekształcić tekst zapisany jako CSV na dwuwymiarową tablicę tekstów.
Pierwszą zagadką jest CSV (skrót od: comma-separated values, czyli wartości odzielane przecinkiem). Standard (4180) mówi o tym, że mamy rekordy odzielane znakiem końca linii (wg standardu powinno być to CRLF, ale biorąc pod uwagę, że jest to plik tekstowy, to przy przenoszeniu między systemami mógł zostać skonwertowany i nie trzymałbym się tego zagadnienia "sztywno", raczej przyjąłbym, że musi być koniec linii). Natomiast pola w rekordzie (jak nazwa wskazuje) przecinkiem (choć tu niektórzy rozszerzają na to, że może być to inny znak - w praktyce często stosowane sa znaki tabulatora i średnika).
Dodatkowym znakiem specjalnym jest cudzysłów. Treść w cudzysłowie nie jest analizowana i mimo wystąpienia tam znaku specjalnego, nie kończy on ani pola ani rekordu.
Aby używać cudzysłowu jako znaku w tekście należy poprzedzić go drugim takim znakiem, czyli: "" powinno zostać zinterpretowane jako znak tekstu: " I to koniec zawiłości. Cała reszta w zasadzie nie powinna nas interesować (choć niektóre parsery obcinają białe znaki z początku i końca treści, ale myślę, że można to zostawić użytkownikowi)

2) Pierwszego podejścia do rozwiązania

Pierwsze rozwiązanie oczywiście nie jest optymalne, ani pod względem zużycia zasobów, ani szybkości działania, ani nawet dobrego interface'u. W pierwszym podejściu chcemy rozeznać się po prostu z tym jak bardzo skomplikowane jest zadanie. Tak więc algorytm ma być przede wszystkim prosty w implementacji. Tak więc tworzymy sobie prostą funkcję:

tlistarr GetCSV(const char *ainp, char arecsep);

• tlistarr - zdefiniowałem jako prostą kolejkę kolejek stringów (w zasadzie powinienem jako wektor wektorów stringów, ale ze względu na to jak bedzie używane, tak będzie odrobinę optymalniej, bez konieczności wnikania w sam algorytm, bedzie użycie kolejek).
• pierwszy argument to ciąg znaków do analizy
• drugi argument to znak separatora pól (zazwyczaj będzie to przecinek, średnik bądź tabulator)

W samej funkcji mamy zdefiniowane:

tlistarr res;
int lstatus = 0; /// 0 - standardowy tryb, 1 bit otwarcie cudzyslowia, 2 bit jest w cudzyslowie

const char *lact = ainp;
std::string lsbuf = "";

trecofarr row;

• res - oczywiście wartość zwracana,
• lstatus - taka prosta zmienna stanowa, na bitach mamy określony stan w jakim znajduje się algorytm ze względu na to czy wystąpił cudzysłów, a jak tak, to w jakiej formie.

oraz zmienne pomocnicze:

• lact - wskaźnik na aktualnie analizowany znak
• lsbuf - bufor znakowy
• row - bufor kolejek stringów

Po deklaracji mamy główną pętlę:

for (; (*lact); ++lact)

jak widać sprawdzamy, czy wystąpił znak '\0', który kończy dalszą analizę, oraz na końcu pętli przenosimy się na kolejny znak.

Pierwszy krok to sprawdzenie statusu, który nam powie, czy wystąpił znak wcześniej cudzysłów, czy nie. Cały blok wygląda następująco:

if ((lstatus & 1) > 0)
{
    if (*lact == '\"')
    {
       //wstawić "
       lsbuf += "\"";
       lstatus &= (~1);
       continue;
    }
    else if ((lstatus & 2) > 0)
    {
      // zakończyć
      lstatus = 0;
    }
    else
    {
        //rozpoczynamy "
        lsbuf += (*lact);
        lstatus = 2;
        continue;
    }
}

W bloku tym rozpatrujemy 3 przypadki:

• bezpośrednio za znakiem cudzysłowa wystąpił kolejny taki sam znak, więc zapamiętujemy znak ", w buforze oraz przechodzimy do analizy kolejnego znaku (uprzednio wygaszając bit 0 w naszej zmiennej statusowej)
• za znakiem cudzysłowa jest inny znak niż cudzysłów, ale status (ustawiony bit 1) wskazuje, że to był "cudzysłów kończący", toteż ustawiamy status na 0 i pozwalamy dalej analizować ten znak.
• za znakiem cudzysłowa jest inny znak niż cudzysłów, a status wskazuje, że poprzedni znak to znak otwierający cudzysłów. W takim razie nie pozostaje nam nic innego jak dodać go do bufora i przejść do analizy kolejnego znaku.

Jeśli nie przeszliśmy z jakiś powodów do analizy kolejnego znaku, to kolejny blok odpowiedzialny jest za analizę znaku pod kątem, czy nie wystąpił któryś ze znaków specjalnych:

if ((*lact == arecsep) && (lstatus != 2))//koniec rekordu
{
    //utwórz pole z danych w lsbuf
    row.push_back(lsbuf);
    lsbuf = "";
}
else if (((*lact == '\n') || (*lact == '\r'))&& (lstatus != 2))
{
    if (lsbuf.length() > 0)//jeśli są jeszcze dane w buforze - to dodać
    {
        row.push_back(lsbuf);
        lsbuf = "";
    }
    if (row.size() > 0)
    {
        //utwórz rekord
        res.push_back(row);
        row.clear();
    }
}
else if ((*lact == '\"') )
{
    lstatus |= 1;
}
else
{
    lsbuf += (*lact);
}

• Najpierw sprawdzamy, czy nie wystąpił znak końca pola, jeśli wystąpił (a jednocześnie status mówi, że nie jesteśmy w środku cudzysłowu), dodajemy do bufora rekordu zawartość bufora pola i czyścimy bufor na dane kolejnego pola
• Kolejnym krokiem będzie sprawdzenie, czy nie wystąpił znak końca linii. Jeśli wystąpił i "nie jesteśmy w cudzyslowie", to jeśli jest coś w buforze pola, dodajemy do bufora rekordu, czyszcząc jednocześnie bufor na dane kolejnego pola, jeśli w buforze rekordu są jakieś dane, dodajemy zawartość bufora do zwracanej tablicy danych i czyścimy bufor na kolejne dane (dzięki temu manewrowi ignorujemy puste linie oraz algorytm nie jest zależny od rodzaju końca wiersza)
• Przedostatnim wariantem - jest wystąpienie znaku cudzysłowa, ustawiamy wtedy w naszej zmiennej statusowej informację o wystąpieniu takiego znaku.
• Ostatni wariant, to wystąpienie jakiegokolwiek innego znaku, który po prostu dodajemy do bufora pola.

Za pętlą mamy jeszcze wstawienie danych z buforów (jeśli takowe są - wg standardu powinny, ale sprawdzanie tego nie ma sensu) do zmiennej zwracanej na końcu funkcji.

3) Pierwszych uwag, tak aby w kolejnym kroku móc zacząć

Nawet niewprawne oko zauważy, iż tak zdefiniowane dane - mają zaletę - wszystko ładnie na koniec programu się zwolni, tyle że następuje cała masa niepotrzebnych kopiowań danych.
Przechodząc dalej powinniśmy przemyśleć właśnie zwracany typ danych, tak aby optymalnie zajmował mało pamięci, żeby złożoność w dostępie do konkretnego elementu była dostatecznie mała oraz aby bezpiecznie kopiował dane.
Ostatni punkt z tych do przemyslenia na dziś, to czy zawsze dane będą w tablicy znakowej, a co jesli byśmy je czytali z pliku?

4) Małe wyjaśnienie

Do napisania przykładu wybrałem język C++ z tego powodu, że:

• należy do grupy języków, których używam dość często
• ma zdefiniowane typy, które ułatwiają napisanie w miarę czytelnie ten algorytm (w przeciwieństwie do C, ale do niego w dalszych częściach cyklu wrócimy)
• bo kompilator języka C++ działa na większości maszyn i systemów z którymi pracuję (szczególnie na MorphOS-ie, który służy mi do codziennej pracy w domu i na którym powstał ten artykuł)

Oczywiście kod do pobrania: Klik.

Na tym kończe i pozdrawiam
Tomasz Kaczanowski

2014-04-19 18:03:39