Důležité!

Pozorně si přečtěte pokyny k výuce během rektorského volna!

Cvičení 10: Jednotkové testovanie

Na cvičení 7 ste si skúsili implementovať jednoduchú dátovú štruktúru, spájaný zoznam. Na dnešom cvičení sa úlohy obrátia. V kostre máte pripravenú implementáciu úplne inej dátovej štruktúry a vašou úlohou je pomocou testov odhaliť niekoľko chýb voči požadovanému chovaniu.

Zadanie

V hlavičke queue.h sa nachádza deklarácia dátovej štruktúry cyklický rad s fixnou veľkosťou (angl. fixed-size cyclic queue). Vašou úlohou je do tests.c napísať testy pre každú funkciu tak, aby ste odhalili chyby implementácie voči očakávanému chovaniu popísanému v dokumentácii hlavičkového súboru.

Popis cyklického radu

Rad (čes. fronta, angl. queue) je abstraktná dátová štruktúra, ktorá má typicky dve operácie, enqueue a dequeue (môžu sa volať aj inak). Prvá operácia prvky do radu vkladá, druhá ich vyberá. Prvky sa z radu vyberajú presne v takom poradí, v akom sa vkladajú.

V kontexte minulého cvičenia by bolo možné rad implementovať pomocou obojsmerne spájaného zoznamu napríklad tak, že

  • enqueue urobí listPush(),

  • dequeue urobí listShift(),

  • ostatné operácie listPop() a listUnshift() sa zakážu

Variant, kedy sa použije listUnshift() a listPop() bude fungovať tiež.

Implementácia použitá v tomto cvičení však spájaný zoznam nepoužíva, pretože by ste museli testovať aj interné stavy uzlov. Implementácia preto používa pevnú veľkosť (fixed size), pričom sa recykluje stále rovnaký úsek pamäte akoby "do kruhu" (cyclic).

Štruktúra struct queue obsahuje 5 položiek:

  • size_t element — veľkosť prvkov

  • size_t capacity — počet prvkov, ktoré sa dajú uložiť v rade

  • size_t index — index prvku v pomyslenom poli radu, ktorý sa najbližšie vyberie operáciou dequeue, ak sú v rade nejaké prvky

  • size_t size — počet aktuálne uložených prvkov

  • void *memory — interná pamäť radu

Pri vložení prvku do radu sa hodnota (nie pointer) skopíruje do poľa memory na pozíciu tak, aby bol size * element bytov ďaleko od index. Ak by táto hodnota prekročila veľkosť pamäte, tak sa začne znova od začiatku. Prvky sa vyberajú jednoducho z pozície označenej ako index, jeho hodnota s následne zvýši alebo vráti na 0, ak by sa dostala na capacity.

Príklad

Majme rad znakov (char) kapacity 4, ktorý je iniciálne prázdny. To znamená, že element = sizeof(char), capacity = 4, index = 0 a size = 0. Rad zapíšeme ako [>?,?,?,?], kde > označuje index. Hodnoty ? sú neinicializované alebo neznáme.

  • vložením znakov a, b a c vznikne rad [>a,b,c,?]

  • výberom znaku dostaneme a, ostane rad [?,>b,c,?]

  • výberom ďalšieho znaku dostaneme b, ostane rad [?,?,>c,?]

  • vložením znaku d dostaneme rad [?,?,>c,d]

  • vložením ďalšieho znaku e sa prvky začnú vkladať odzačiatku, tj. dostaneme rad [e,?,>c,d]

Popis operácií

Presné požiadavky na chovanie, ktoré máte testovať, nájdete v hlavičkovom súbore queue.h
bool queueCreate(struct queue **queue, size_t elementSize, size_t capacity);
  • vytvorí nový rad s požadovanými parametrami

void queueDestroy(struct queue *queue);
  • dealokuje štruktúru

size_t queueElementSize(const struct queue *queue);
size_t queueCapacity(const struct queue *queue);
size_t queueSize(const struct queue *queue);
  • funkcie vyššie zisťujú rôzne informácie o rade

bool queueIsEmpty(const struct queue *queue);
bool queueIsFull(const struct queue *queue);
  • test, či je rad prázdny resp. plný

bool queueEnqueue(struct queue *queue, const void *data);
  • implementuje operáciu enqueue

  • v kontraste s cvičením so spájaným zoznamom táto funkcia kopíruje dáta, nie hodnotu ukazateľa

bool queueDequeue(struct queue *queue, void *data);
  • implementuje operáciu dequeue

const void *queuePeek(const struct queue *queue);
  • vráti konštantný ukazateľ na najstarší prvok v rade, ak existuje

Ukážku použitia tejto štruktúry nájdete v playground.c.

Prečo zdrojový kód vyzerá ako Perl?
Cieľom cvičenia je testovať chovanie štruktúry podľa dokumentácie. Často je možné odhaliť chyby jednoduchým prečítaním zdrojového kódu, obzvlášť v implementáciách, ako je táto. Aby sme tomu zabránili, zdrojový kód dodaný k cvičeniu prešiel procesom obfuskácie.

Obfuskácia sa používa vtedy, ak chceme čo najviac sťažiť porozumenie zdrojového kódu. Zdrojový kód v queue.c prešiel týmito zmenami:

  1. prístup ku štruktúram sa implementuje cez globálne pole unionov,

  2. jednoduché operácie a konštanty (napr. 0) sú implementované pomocou volaní nesúvisiacich funkcí, okrajových prípadov atď.

  3. množstvo kódu generujú makrá v perl.h

Úloha: Testovanie

Cvičiaci vytvorí v službe collabedit zdieľaný dokument, do ktorého sa budú ukladať testy. Následne rozdelí študentov do niekoľkých skupín, pričom každá skupina dostane pár funkcí na otestovanie. Odporúčané rozdelenie je na 4 skupiny:

  1. queueSize(), queueElementSize(), queueCapacity()

  2. queuePeek(), queueIsFull(), queueIsEmpty()

  3. queueCreate(), queueEnqueue()

  4. queueDequeue()

Študenti v skupine môžu diskutovať o prípadoch, ktoré by mali otestovať, a následne k nim písať testy. Svoje testy študenti priebežne kopírujú do zdieľaného dokumentu. Cvičiaci tieto testy občas spustí a prípadne vysvetlí, prečo zlyhali. Cieľom je pomocou testov nájsť chyby voči dokumentácii.

Testovací nástroj

Testy píšte do tests.c. Tento súbor nemá funkciu main(), obsahuje len testy. Každý test sa začína makrom TEST s názvom testu.

V tele v blokových zátvorkých je možné písať ľubovoľný kód jazyka C, môžete volať funkcie, deklarovať premenné, používať cykly atď. Okrem toho môžete používať makro CHECK, ktoré skontroluje, že nejaká podmienka platí, inak test skončí neúspešne.

TEST(zero)
{
    int zero = 0;
    CHECK(zero == 0);
}

Ako na jednotkové testovanie

Testovanie je všeobecne ťažké a trvá dlhý čas a prax, kým sa programátor naučí poriadne testovať. Táto časť preto uvádza len veľmi jednoduché rady, čo pri testovaní robiť a čo nie.

Testujte vždy len jednu funkciu

Predstavte si takýto test:

TEST(velky_spatny)
{
    struct queue *queue;
    queueCreate(&queue, sizeof(int), 16u);

    int data = 42;
    queueEnqueue(queue, &data);
    CHECK(queueSize(queue) == 1u);
}

Ak tento test zlyhá, nedá sa jednoznačne povedať, ktorá funkcia za to môže. Chyba môže byť v queueSize(), queueEnqueue() alebo rovnako aj queueCreate().

Každý TEST by mal preto volať len jednu funkciu z testovaného rozhrania.

Vytvárajte štruktúru sami

Keďže by ste vďaka predchádzajúcemu bodu nemali volať queueCreate() s výnimkou testu priamo pre túto funkciu, musíte si štruktúru vyrobiť sami pred každým testom. Takto máte kontrolu nad vstupom funkcie a môžete jednoducho otestovať, že po skončení sa štruktúra zmenila očakávaným spôsobom.

Príklady nájdete v ukážkových testoch v tests.c.

Každý test nech testuje jeden prípad

Aby bolo možné ľahko odlíšiť okolnosti, za akých sa funkcia nespráva očakávane, každý test by mal testovať jeden špecifický scenár.

Napríklad, pre test queueEnqueue() môžeme testovať tieto prípady:

  • prázdny rad s nenulovou kapacitou

  • čiastočne zaplnený rad, v ktorom je miesto na konci

  • čiastočne zaplnený rad, v ktorom je miesto na začiatku

  • plný rad

  • …​

Pre každý takýto prípad by mal exitovať samostatný test. Tieto testy môžete pomenovať nazovTestovanejFunkcie__pripad, napríklad queueEnqueue__empty_with_nonzero_capacity.

Nepoužívajte náhodnosť

Testy založené na náhodnosti sú veľmi užitočné, ale je ťažké ich urobiť správne. Jeden z hlavných problémov je determinizácia. V prípade, že test zlyhá, je často nutné takýto test zopakovať, napríklad kvôli ladeniu. Na toto cvičenie náhodné testy nepotrebujete.