Testen = Dynamische Programm Analyse

Niemand schreibt gerne Tests! Tests sind aber notwendig. Ohne Tests bleiben bugs oft unentdeckt und sind schlecht reproduzierbar.

Klassischer Testansatz: Unit Tests

Definiere Eingabe und führe “unit” aus.
Vergleiche tatsächliches Programmverhalten mit dem erwarteten Programmverhalten.

Siehe Beispiel “count”.

In der Regel viel händische Arbeit notwendig.

Testen im Stile von QuickCheck

Automatische Generierung von Testdaten (“type-specific test (input) data generation”)
Eigenschafts-basiertes Testen (“property-based testing”)

Punkt 1: Automatische Ausführung der “unit”.

Punkt 2: Automatische Überprüfung auf erwartetes Programmverhalten.

Beide Punkte wurden populär gemacht durch die Haskell Bibliothek QuickCheck.

Wir zeigen hier die Ideen hinter QuickCheck im Kontext von C++. Die QuickCheck Idee wurde auf viele Programmiersprachen portiert. Siehe QuickCheck for other languages

Wir betrachten zwei Umsetzungen der QuickCheck Idee in C++:

Eine Umsetzung welche OO (Vererbung) verwendet
Eine weitere Umsetzung welche funktionale Abstraktionen verwendet und sehr nahe an der originalen Haskell Version ist.

Motivierendes Beispiel “count”

User + unit Tests
Verlangt sehr viel manuelle Arbeit (und Fehler können sich einschleichen)


#include <cstdlib>
#include <iostream>
#include <string>
#include <functional>

using namespace std;


// Recall

char* skipB(char* input) {
  while(*input == ' ')
    input++;
  return input;
}

char* scanW(char* input) {
  while(*input != '\0' && *input != ' ')
    input++;
  return input;
}


int count(char* input) {
  int cnt = 0;

  while(*input != '\0') {
    input = skipB(input);
    if(*input != '\0') {
      cnt++;
      input = scanW(input);
    }
  }
  return cnt;
}

int countString(string s) {
 char cString[s.size() + 1];

 s.copy(cString, s.size() + 1);
 cString[s.size()] = '\0';

 return count(cString);
}


// User style testing

void testCount(int count(string)) {

  auto test = [count](string s) {
    cout << "\n" << s << " => " << count(s);
  };

  test("");

  test("hallo");

  test(" hallo");

  test(" hal lo");


}

// Unit testing

void unitTestCount(int count(string)) {

  auto test = [count](string s, int expected) {
    auto res = count(s) == expected ? "okay" : "fail";
    cout << "\n" << s << " => " << res;
  };

  test("",0);

  test("hallo",1);

  test(" hallo", 1);

  test(" hal lo", 2);


}

int main() {

  cout << "\ncountString:";
  testCount(countString);

  unitTestCount(countString);
}

QuickCheck Idee

Generiere Testeingaben
Führe Test Unit aus
Prüfe, ob Testausgaben gewisse Eigenschaften erfüllen.

Generiere

Wie?

Zufällig?
Mit Hilfe einer KI?

Nein!

Wir bauen uns eine clevere Bibliothek von Generatoren.
Wir können damit Programme schreiben welche “zufällige” Testeingaben generieren

Prüfe Eigenschaften

Wie?

Zufällig?
Mit Hilfe einer KI?

Nein!

Wir verwenden Invarianten (aka Eigenschaften aka “properties”)

Wie sehen diese Eigenschaften aus?

In der Regel hängt es von der Anwendung (Test Unit) ab.
Eine oft verwendete Eigenschaft: Aktuelle und vorherige Release Version liefern die gleichen Ausgaben.

Umsetzung von QuickCheck mit Hilfe von OO

template<typename T>
class GenOO {
public:
  virtual T generate() = 0;
};


template<typename T>
void quickCheckOO(GenOO<T>* g, bool p(T)) {

for(int i =0; i < 20; i++) {
    auto b = p(g->generate());
    if (b) {
      cout << "\n +++ OK";
    } else {
      cout << "\n *** Failed";
    }
  }

}

Object der Klasse GenOO<T> implementiert einen Testdaten Generator
quickCheck bekommt als Parameter
- Testdaten Generator, und
- zu überprüfende Eigenschaft repräsentiert als Funktion bool p(T)

Generatoren Instanzen

class Bool : public GenOO<bool> {
public:
  bool generate() {
    return (rand() % 2 == 2) ? true : false;
  }
};


class Char : public GenOO<char> {
public:
  char generate() {
    return (char)(rand() % 255);
  }
};

class String : public GenOO<string> {
public:
  string generate() {
    int n = rand() % 15;
    string s;
    Char g;
    for(int i=0; i < n; i++) {
      s = s + g.generate();
    }
    return s;
  }
};

Eigenschaften

bool prop1(string s) {
  return countString(s) >= 0;
}

bool prop2(string s) {
  string sRev;

  sRev = s;
  reverse(sRev.begin(), sRev.end());

  return (countString(s) == countString(sRev));
}

bool prop3(string s) {
  string s2;

  s2 = s + s;

  return (2 * countString(s) == countString(s2));
}

Gelten alle Eigenschaften immer?

“QuickCheck count”

void quickCheckOOCount() {


  cout << "\n**** prop1 \n";
  String* g = new String();

  quickCheckOO<string>(g, prop1);

  cout << "\n**** prop2 \n";
  quickCheckOO<string>(g, prop2);


  cout << "\n**** prop3 \n";
  quickCheckOO<string>(g, prop3);

  delete g;

}

`prop3` fails

Warum? Betrachte z.B. "Hallo".

Betrachte folgende Korrekturen.

bool prop3a(string s) {
  string s2;

  s2 = s + s;

  return (2 * countString(s) >= countString(s2));
}


bool prop3b(string s) {
  string s2;

  s2 = s + " " + s;

  return (2 * countString(s) == countString(s2));
}

prop3a gilt immer.

Wieso gilt prop3b nicht immer?

countString ruft count auf
Der C++ String wird Zeichen für Zeichen in einen C String (mit Nullterminator am Schluss) umgewandelt
Da ASCII Code Null in dem C++ vorkommen kann, wird deshalb das Ergebnis möglicherweise verfälscht

Umsetzung von QuickCheck mit Hilfe funktionaler Abstraktion

Eine Generatorenobjekt ist jetzt nichts anderes wie eine Funktion welche eine zufälligen Wert vom Typ T liefert.

Wie generieren wir Generatorenobjekt für verschiedene Instanzen von T, z.b. char, string, …?

Wir verwenden dazu arbitrary Funktionen. Diese Funktionen unterscheiden sich nur im Rückgabetyp. Solch eine Form der Überladung ist eigentlich in C++ nicht möglich. Wir können solch eine Überladungsform aber mit Hilfe von Template Instanzierung emulieren.

template<typename T>
class Gen {
 public:
  Gen() {};
  Gen(std::function<T()> gen_) { gen = std::function<T()>(gen_); }
  std::function<T()> gen;
  T generate() { return gen(); };
};


template<typename T>
Gen<T> arbitrary();

template<typename T>
void quickCheck(bool p(T)) {
  Gen<T> g = arbitrary<T>();

for(int i =0; i < 20; i++) {
    auto b = p(g.generate());
    if (b) {
      cout << "\n +++ OK";
    } else {
      cout << "\n *** Failed";
    }
  }

}

Beachte:

Generatorenobjekte sind nicht mehr notwendig
Generatoren Instanzen werden rein der Typ Instanz selektiert

Generatoren Instanzen

template<typename T>
Gen<T> arbitrary();

template<>
Gen<bool> arbitrary() { return Gen<bool>([] () -> bool { return (rand() % 2 == 0) ? true : false; }); }

template<>
Gen<char> arbitrary() { return Gen<char>([] () -> char { return (char)(rand() % 255); }); }

template<>
Gen<string> arbitrary() {

  return Gen<string>(
             [] () -> string {
               int n = rand() % 15;
               string s;
               Gen<char> g = arbitrary<char>();
               for(int i=0; i<n; i++) {
             s = s + g.generate();
               }
               return s;
             }
             );
}

“QuickCheck count”

void quickCheckCount() {

  cout << "\n**** prop1 \n";
  quickCheck<string>(prop1);

  cout << "\n**** prop2 \n";
  quickCheck<string>(prop2);


  cout << "\n**** prop3 \n";
  quickCheck<string>(prop3);

}

Im Vergleich zur “OO” Version sind weniger Parameter notwendig.

Kompletter Programmcode


#include <cstdlib>
#include <iostream>
#include <string>
#include <functional>
#include <algorithm>

using namespace std;

/////////////////////////////////////////////
// Zaehlen von Woertern

char* skipB(char* input) {
  while(*input == ' ')
    input++;
  return input;
}

char* scanW(char* input) {
  while(*input != '\0' && *input != ' ')
    input++;
  return input;
}


int count(char* input) {
  int cnt = 0;

  while(*input != '\0') {
    input = skipB(input);
    if(*input != '\0') {
      cnt++;
      input = scanW(input);
    }
  }
  return cnt;
}

int countString(string s) {
 char cString[s.size() + 1];

 s.copy(cString, s.size() + 1);
 cString[s.size()] = '\0';

 return count(cString);
}


/////////////////////////////////////////////
// User Tests

void testCount(int count(string)) {

  auto test = [count](string s) {
    cout << "\n" << s << " => " << count(s);
  };

  test("");

  test("hallo");

  test(" hallo");

  test(" hal lo");


}

/////////////////////////////////////////////
// Unit Tests

void unitTestCount(int count(string)) {

  auto test = [count](string s, int expected) {
    auto res = count(s) == expected ? "okay" : "fail";
    cout << "\n" << s << " => " << res;
  };

  test("",0);

  test("hallo",1);

  test(" hallo", 1);

  test(" hal lo", 2);

  test(" hal looo", 3);
  // Tests koennen auch Fehlerhaft sein!


}


void runTests() {

  testCount(countString);

  unitTestCount(countString);

}


/////////////////////////////////////////////
// QuickCheck unter Verwendung von OO


// Eigenschaften

bool prop1(string s) {
  return countString(s) >= 0;
}

bool prop2(string s) {
  string sRev;

  sRev = s;
  reverse(sRev.begin(), sRev.end());

  return (countString(s) == countString(sRev));
}

bool prop3(string s) {
  string s2;

  s2 = s + s;

  return (2 * countString(s) == countString(s2));
}



// Testdaten Generatoren

template<typename T>
class GenOO {
public:
  virtual T generate() = 0;
};


// Instanzen

class Bool : public GenOO<bool> {
public:
  bool generate() {
    return (rand() % 2 == 2) ? true : false;
  }
};


class Char : public GenOO<char> {
public:
  char generate() {
    return (char)(rand() % 255);
  }
};

class String : public GenOO<string> {
public:
  string generate() {
    int n = rand() % 15;
    string s;
    Char g;
    for(int i=0; i < n; i++) {
      s = s + g.generate();
    }
    return s;
  }
};


// Generierung von strings

void genStringOO() {
  String x;

  for (int i = 1; i < 10; i ++) {
    cout << "\n" + x.generate();
  }

}


template<typename T>
void quickCheckOO(GenOO<T>* g, bool p(T)) {

for(int i =0; i < 20; i++) {
    auto b = p(g->generate());
    if (b) {
      cout << "\n +++ OK";
    } else {
      cout << "\n *** Failed";
    }
  }

}


// QuickCheck count

void quickCheckOOCount() {


  cout << "\n**** prop1 \n";
  String* g = new String();

  quickCheckOO<string>(g, prop1);

  cout << "\n**** prop2 \n";
  quickCheckOO<string>(g, prop2);


  cout << "\n**** prop3 \n";
  quickCheckOO<string>(g, prop3);

  delete g;

}

/////////////////////////////////////////////
// QuickCheck mit Hilfe funktionaler Abstraktion

template<typename T>
class Gen {
 public:
  Gen() {};
  Gen(std::function<T()> gen_) { gen = std::function<T()>(gen_); }
  std::function<T()> gen;
  T generate() { return gen(); };
};


template<typename T>
Gen<T> arbitrary();

template<>
Gen<bool> arbitrary() { return Gen<bool>([] () -> bool { return (rand() % 2 == 0) ? true : false; }); }

template<>
Gen<char> arbitrary() { return Gen<char>([] () -> char { return (char)(rand() % 255); }); }

template<>
Gen<string> arbitrary() {

  return Gen<string>(
             [] () -> string {
               int n = rand() % 15;
               string s;
               Gen<char> g = arbitrary<char>();
               for(int i=0; i<n; i++) {
             s = s + g.generate();
               }
               return s;
             }
             );
}


void genString() {
  Gen<string> x = arbitrary<string>();

  for (int i = 1; i < 10; i ++) {
    cout << "\n" + x.generate();
  }

}

template<typename T>
void quickCheck(bool p(T)) {
  Gen<T> g = arbitrary<T>();

for(int i =0; i < 20; i++) {
    auto b = p(g.generate());
    if (b) {
      cout << "\n +++ OK";
    } else {
      cout << "\n *** Failed";
    }
  }

}


void quickCheckCount() {

  cout << "\n**** prop1 \n";
  quickCheck<string>(prop1);

  cout << "\n**** prop2 \n";
  quickCheck<string>(prop2);


  cout << "\n**** prop3 \n";
  quickCheck<string>(prop3);

}


int main() {

  // runTests();

  // genStringOO();

  // quickCheckOOCount();

  // genString();

  // quickCheckCount();
}

QuickCheck in C++

Testen = Dynamische Programm Analyse

Klassischer Testansatz: Unit Tests

Testen im Stile von QuickCheck

Motivierendes Beispiel “count”

QuickCheck Idee

Generiere

Prüfe Eigenschaften

Umsetzung von QuickCheck mit Hilfe von OO

Generatoren Instanzen

Eigenschaften

“QuickCheck count”

`prop3` fails

Umsetzung von QuickCheck mit Hilfe funktionaler Abstraktion

Generatoren Instanzen

“QuickCheck count”

Kompletter Programmcode

Weitere Anwendung

QuickCheck in C++

Testen = Dynamische Programm Analyse

Klassischer Testansatz: Unit Tests

Testen im Stile von QuickCheck

Motivierendes Beispiel “count”

QuickCheck Idee

Generiere

Prüfe Eigenschaften

Umsetzung von QuickCheck mit Hilfe von OO

Generatoren Instanzen

Eigenschaften

“QuickCheck count”

prop3 fails

Umsetzung von QuickCheck mit Hilfe funktionaler Abstraktion

Generatoren Instanzen

“QuickCheck count”

Kompletter Programmcode

Weitere Anwendung

`prop3` fails