Detta är en gammal version av kurshemsidan och kan innehålla inaktuell information. Klicka här för att komma till årets upplaga av kursen.

TDDI16 Datastrukturer och algoritmer

Ht1 2020

TestLab

TestLab är ett verktyg som försöker hjälpa till med testning av era lösningar till laborationerna i kursen. Det är inspirerat av artikeln Executable Examples for Programming Problem Comprehension. Detta är ett experiment för i år, så det är inte obligatoriskt att använda verktyget under laborationerna, men det kan underlätta testningen. Hör gärna av er om ni använder verktyget och säg vad ni tycker.

Idé

Verktyget är tänkt att hjälpa till med skapandet av relevanta tester. Programmet läser in en uppsättning testfall och säger två saker: dels ifall testfallen är korrekta (dvs. att de matchar den specifikation som finns i laborationerna), och dels ifall testfallen är intressanta. Intressanta testfall är i det här fallet testfall som hittar buggar i en av de felaktiga implementationerna som verktyget känner till.

För att detta ska fungera, finns det alltså till varje laboration ett eller flera korrekta program, och ett eller flera felaktiga program. Målet för er är att skriva testfall som dels stämmer överens med de korrekta programmen, och dels hittar de problem som finns i de inkorrekta problemen. Lyckas ni med det så har ni skrivit en bra testsvit!

De korrekta programmen representerar olika möjliga korrekta implementationer. Anledningen till att det ibland finns flera är att vissa problem inte alltid bara har en godkänd lösning (exempelvis kan det finnas flera olika kortaste vägar). De inkorrekta programmen representerar logiska fel i olika delar av uppgiften, och försöker introducera fel på olika ställen för att ge en bra indikation om alla delar av problemet har testats ordentligt.

Hämta verktyget

Notera: Verktyget finns i dagsläget endast tillgängligt för Linux. Programmet fungerar på Debian-baserade system (Ubuntu, Linux Mint, etc.), och kanske på andra system också. Om inte annat går det att köra via ThinLinc.

På egen dator (Linux)

IP-studenter kan hämta hem verktyget till sina egna system med hjälp av kommandot scp (byt ut <liu-id> mot ditt LiU-id):

scp -r <liu-id>@ssh.edu.liu.se:/courses/TDDI16/test ~/testlab

Efter detta kan testlab köras med kommandot ~/testlab/testlab, vilket kan vara tillräckligt. Det går också att skapa ett alias för att kunna använda testlab i stället. Det görs genom att lägga till följande rad i filen ~/.bashrc:

alias testlab="~/testlab/testlab"

Sedan behöver skalet startas om för att ändringarna ska ha effekt.

Via ThinLinc

Verktyget finns på ThinLinc och på datorerna i SU-salarna i mappen /courses/TDDI16/test/. Det enklaste sättet att använda det på är att lägga till modulen som finns genom att köra:

module add /courses/TDDI16/module

Detta gör att ni kommer åt kommandot testlab i den terminalen där ni skrev kommandot. Vill ni att programmet ska vara åtkomligt varje gång ni loggar in, och i alla terminaler kan ni använda:

module initadd /courses/TDDI16/module

Det kan krävas att ni loggar ut och sedan in igen för att modulen ska laddas ordentligt. TestLab kan sedan köras genom att skriva testlab i terminalen.

Användning

Efter att du har konfigurerat ditt system enligt ovan kan du köra testlab i terminalen. Kommandot tar två parametrar enligt nedan:

testlab <lab> <testfil>

Där <lab> är den lab ni vill testa, och <testfil> är namnet på er fil med testfall. För att testa de testfall som finns i filen lab1_tests.txt kan man alltså skriva:

testlab lab1 lab1_tests.txt

Det finns även ett grafiskt gränssnitt som kan köras med kommandot testlab-gui (kräver Python 3 och PyGtk).

Testfall

Testfallen skrivs i en vanlig textfil med valfri texteditor. Filen består av ett eller flera testfall avgränsade med en rad med minst två bindestreck (----). Varje testfall består i sin tur av en uppsättning parametrar. Parametrarna kan komma i vilken ordning som helst och de skrivs antingen som:

nyckel: värde

eller som nedan ifall flera rader av data ska matas in:

key\
  line1
  line2

Notera indenteringen på raderna som följer key\.

Varje laboration har sitt eget indataformat, vilket beskrivs här nedan:

Lab 1 - AVL-träd

Varje testfall ska innehålla två parametrar: insert och remove. Testramverket sätter först in alla värden som anges efter insert, och tar sedan bort de som står efter remove. Sedan kontrollerar det om trädet ser korrekt ut. Två enkla testfall kan se ut som nedan:

insert: 5 1 8
remove: 8
----
insert: 5 1 8
remove: 1

Lab 2 - Knäcka lösenord

Varje testfall ska innehålla tre parametrar: key är vilken tabell T som användes när lösenordet hashades, hash är det hashade lösenordet som ska knäckas, och passwords är de lösenord som vi förväntar oss att hitta. Två enkla testfall kan se ut som nedan:

key: rand5.txt
hash: exvx5
passwords\
  passw
  i0ocs
----
key: rand5.txt
hash: 0klgh
passwords\
  abcde
  ktfbp

Lab 3 - Ordkedjor

Varje testfall kan innehålla följande parametrar:

dictionary Namn på den fil som innehåller ordlistan som ska användas. Kan också vara en lista av ord som ska användas.
from Startordet i sökningen. Om from utelämnas sker en sökning från alla ord till to
to Slutordet i sökningen.
expected_length Antal ord i den väg som vi förväntar oss att programmet hittar. Längden 0 motsvarar att ingen lösning finns.
expected_first Det ord vi förväntar oss är först i vägen vi hittar. Kan utelämnas om from finns med.
expected_last Det ord vi förväntar oss är sist i vägen vi hittar. Kan utelämnas.

Testramverket kommer också att titta på den vägen som finns och se ifall det är en korrekt ordkedja. Nedan finns ett par exempel på hur testfall kan se ut. Notera att rader som börjar med en fyrkant (#) är kommentarer:

dictionary: simple.txt
from: aaaa
to: aabb
expected_length: 3
# These are optional:
expected_first: aaaa
expected_last: aabb
----
dictionary: simple.txt
to: aaaa
expected_length: 4
expected_first: babb
# This is optional:
expected_last: aaaa
----
# It is possible to inline the dictionary as well.
dictionary\
  aula
  gula
  gala
  gama
  jama
  sten
to: aula
expected_length: 5
expected_first: jama
# This is optional.
expected_last: aula
----
dictionary\
  aaaa
  zzzz
from: aaaa
to: zzzz
# 0 means "no solution"
expected_length: 0

Lab 4 - Mönsterigenkänning

Varje testfall kan innehålla följande parametrar:

points Antingen en lista av punkter (varje punkt på en egen rad), eller ett namn på en fil som innehåller punkter.
lines En lista av de linjer som programmet väntas producera. Endast de längsta linjerna behöver finnas med här. Testet kommer att räknas som godkänt även om kortare versioner av de linjer som finns med här matas ut av programmet.

points\
  10 10
  20 20
  30 30
  40 40
  50 50
  10 100
  20 90
lines\
  10 10 - 50 50
---
points: input7.txt
lines\
  1000 1000 - 5000 5000

Testa er egen lösning

När ni har skapat många bra testfall som hittar alla buggarna i de felaktiga programmen har ni en bra testsvit för att testa ert eget program. Det går såklart att göra genom att manuellt testa de testfallen som finns i testfilen, men det är tråkigt och blir lätt fel. Därför kan testlab hjälpa till även med detta!

Du kan be testlab att köra dina tester på din lösning genom att lägga till namnet på din kompilerade fil sist i kommandoraden. Exempelvis:

testlab lab1 tests.txt avl_tree-test

eller

testlab lab2 tests.txt decrypt