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. In unserer QuickCheck C++ Variante versuchen wir sehr nahe an der originalen Haskell Version zu bleiben.

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.

Automatische Generierung von Testeingaben

Ein Testfall besteht aus

Eingabewert.
“unit” welche durch Eingabewert stimuliert wird.
Prüfe, ob tatsächlicher (Rückgabe)Wert dem erwarteten Wert entspricht.

Wir möchten die Generierung von Eingabewerten automatisieren. Der Ansatz dazu ist wie folgt.

Generatoren um beliebige Werte eines Typs zu bilden.
Typ-spezifische Instanzen für Generatoren.

Im folgenden betrachten wir eine Kodierung dieser Idee in C++.

`Gen` und `arbitrary`

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();

Ein Generator ist eine Funktion welche einen Wert liefert. Dies ist dargestellt durch ein C++ Object Gen<T> wobei die Methode gen einen zufälligen Wert vom Typ T liefert.

Generatoren Instanzen werden durch Überladung der arbitrary Funktion geliefert.

`arbitrary` Instanzen

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

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

// int
template<>
Gen<int> arbitrary() { return Gen<int>([] () -> int { return rand(); }); }

Weitere Instanzen können hinzugefügt werden. Dadurch kann ein Test Ingenieur die Generierung von Applikations-spezifischen Werten automatisieren.

Komplexere Generatoren

template<typename T>
Gen<T> elements(vector<T> v) {
  return Gen<T>([v] () -> T { return v[abs(rand()) % v.size()]; });
}

template<typename T>
Gen<vector<T>> vectorN(int n) {
  return Gen<vector<T>>([n] () -> vector<T>
                             {
                               vector<T> v;
                               for(int i=0; i < n; i++) {
                                  auto x = arbitrary<T>().generate();
                                  v.push_back(x);
                                }
                   return v;
                 });
}

elements wählt ein zufälliges Element aus.

vectorN baut einen Vector von zufälligen Werten.

Viele weitere Generatorfunktionen sind denkbar. Je nach Applikation, kann dadurch die “zufällige” Testgenerierung einfacher programmiert werden.

Applikation: Generierung von Strings

#define QC_STRING_SIZE  40

template<>
Gen<string> arbitrary() {
  return Gen<string>([] () -> string
    {
      int i = rand() % QC_STRING_SIZE;

      Gen<vector<char>> x = vectorN<char>(i);
      vector<char> v = x.generate();
      string s(v.begin(), v.end());

      return s;
    });
}

Maximale Größe der Strings ist fest, könnte aber auch mit Hilfe von Gen parametrisiert werden.

Die arbitrary Instanz für string verwendet vectorN und die arbitrary Instanz für `char.

Eigenschafts-basiertes Testen

Die Generierung von Testeingaben konnten wir automatisieren.

Was fehlt noch? Wie können wir automatisch überprüfen, ob das Resultat der Testausführung dem erwarteten Ergebnis entspricht?

Idee. Wir verwenden Eigenschaften (“properties”). Diese Eigenschaften entsprechen Assertionens (Zusicherung) = Invarianten.

Hier sind ein paar Eigenschaften in Bezug auf das “count” Beispiel.

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));
}

prop1: Anzahl der Wörter muss immer größer gleich Null sein.

prop2: Der Originale String und der umgekehrte String liefern das gleiche Ergebnis.

Wir können nun schnell überprüfen (“quick check”), ob die Eigenschaften stimmen.

Generiere zufällige Eingabe.
Wende Eigenschaft auf jede Eingabe an.

#define QC_TEST_DATA_SIZE 20

template<typename T>
void quickCheck(bool p(T)) {
  auto v = arbitrary<T>();
  for(int i =0; i < QC_TEST_DATA_SIZE; i++) {
    auto b = p(v.generate());
    if (b) {
      cout << "\n +++ OK";
    } else {
      cout << "\n *** Failed";
    }
  }
}

“count” Demo

Wir betrachten auch folgende Eigenschaft.

bool prop3(string s) {
  string s2;

  s2 = s + s;

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

}

Zwischenfazit

Der “bug” kann in der Eigenschaft liegen. Siehe prop3.
Falls die Eigenschaften gelten, heisst dies nicht dass das Programm bug-frei ist.

Betrachte folgenden “count” Variante.

int count2 (string s) { return 0; }

count2 erfüllt für alle Eingaben prop1, prop2 and prop3.

Automatische Generierung von Eingaben und Eigenschafts-basiertes Testen sind sehr effiziente Testmethoden.

Sie dienen zur Unterstützung von klassischen Unit-Tests (sollen aber diese nicht ersetzen).

Je mehr diversitäre Testmethoden wir verwenden, desto größer sind die Chancen bugs zu finden.

Applikation: Generierung von Wörtern

Wir möchten bei der Generierung von Wörtern zielgerichteter Vorgehen. Bisher generieren wir zufällige Strings. Wir möchten Strings generieren welchen gewissen Vorgaben genügen.

// Generate inputs for count satisfying the following conditions:
// Maximum of 4 blanks between words.
// Maximum of 10 words.
// Words consist of between 1 to 5 upper/lower-case letters only.

typedef struct { string str; } myString;

typedef struct { char letter; } myLetter;

template<>
Gen<myLetter> arbitrary() {
  return Gen<myLetter>([] () -> myLetter {
              vector<char> letters;
              for (int i = int('a'); i <= int('z'); i++) {
                 letters.push_back(char(i));
              }
              for (int i = int('A'); i <= int('Z'); i++) {
                 letters.push_back(char(i));
              }

          return myLetter{elements(letters).generate()};
    });

}


template<>
Gen<myString> arbitrary() {
  return Gen<myString>([] () -> myString {

      auto mkWord = [] () -> string {
    int n = (rand() % 5) + 1;
    auto l = arbitrary<myLetter>();
    string s;
        for (int i = 1; i <= n; i++) {
      s = s + char(l.generate().letter);
    }
        return s;
      };

      auto mkBlanks = [] () -> string {
    int n = rand() & 3;
    string s;
        for(int i = 1; i<= n; i++) {
      s = s + " ";
    }
    return s;
      };

      int nWords = (rand() & 10) + 1;
      string s;

      for (int i = 1; i <= nWords; i++) {
    s = s + mkBlanks() + mkWord() + mkBlanks();
      }

      return myString{s};
    });
}

Demo

Zusammenfassung

Eine wirkliche coole Idee: QuickCheck

Zufällige Generierung von Testeingaben
- Programmiere eigene Zufallsverteilung
Eigenschafts-basiertes Testen
- Spezifiziere eigene Eigenschaften

Kompletter Source Code

quickCheck.h und quickCheckCount.cpp

`quickCheck.h`


#ifndef __QUICKCHECK__
#define __QUICKCHECK__

// Usage: g++ -std=c++11 quickCheck.cpp

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

using namespace std;

// Some constants

#define QC_STRING_SIZE  40
#define QC_TEST_DATA_SIZE 20


// Generator interface.
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(); };
};

// Computing an arbitrary generator.
template<typename T>
Gen<T> arbitrary();

// Some instances

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

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

// int
template<>
Gen<int> arbitrary() { return Gen<int>([] () -> int { return rand(); }); }


// Some generators.

// Pick a random element.
template<typename T>
Gen<T> elements(vector<T> v) {
  return Gen<T>([v] () -> T { return v[abs(rand()) % v.size()]; });
}


// Build a vector of arbitrary values.
// Assumes arbitrary for T.
template<typename T>
Gen<vector<T>> vectorN(int n) {
  return Gen<vector<T>>([n] () -> vector<T>
                             {
                               vector<T> v;
                               for(int i=0; i < n; i++) {
                                  auto x = arbitrary<T>().generate();
                                  v.push_back(x);
                                }
                   return v;
                 });
}




// string, makes use of char
template<>
Gen<string> arbitrary() {
  return Gen<string>([] () -> string
    {
      int i = rand() % QC_STRING_SIZE;

      Gen<vector<char>> x = vectorN<char>(i);
      vector<char> v = x.generate();
      string s(v.begin(), v.end());

      return s;
    });
}


// property-based testing

template<typename T>
void quickCheck(bool p(T)) {
  auto v = arbitrary<T>();
  for(int i =0; i < QC_TEST_DATA_SIZE; i++) {
    auto b = p(v.generate());
    if (b) {
      cout << "\n +++ OK";
    } else {
      cout << "\n *** Failed";
    }
  }
}

// verbose version

template<typename T>
string show(T);

template<>
string show(int x) { return to_string(x); }

template<>
string show(char x) { return to_string(x); }

template<>
string show(string x) { return x; }

template<typename T>
void verboseCheck(bool p(T)) {
  auto v = arbitrary<T>();
  for(int i =0; i < QC_TEST_DATA_SIZE; i++) {
    auto d = v.generate();
    auto b = p(d);
    if (b) {
      cout << "\n +++ OK";
      cout << "  " + show(d);
    } else {
      cout << "\n *** Failed";
      cout << "  " + show(d);
    }
  }
}


#endif // __QUICKCHECK__

`quickCheckCount.cpp`

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

#include "quickCheck.h"

using namespace std;


////////////////////////
// count with string

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

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


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

  while(*input != '\0') {
    input = skipBlanks(input);
    if(*input != '\0') {
      cnt++;
      input = scanWord(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);
}

//////////////////
// Properties

// Number of words counted must be greater or equal zero.
bool prop1(string s) {
  return countString(s) >= 0;
}

// Reversing the string yields the same number of words.
bool prop2(string s) {
  string sRev;

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

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


// Concatenating the string doubles the number of words.
bool prop3(string s) {
  string s2;

  s2 = s + s;

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

}

void quickCheckCount() {

  cout << "\n**** prop1 \n";
  quickCheck(prop1);
  cout << "\n**** prop2 \n";
  quickCheck(prop2);
  cout << "\n**** prop3 \n";
  //  quickCheck(prop3);
  verboseCheck(prop3);

}

// Customizing test data generation

// Generate inputs for count satisfying the following conditions:
// Maximum of 4 blanks between words.
// Maximum of 10 words.
// Words consist of between 1 to 5 upper/lower-case letters only.

typedef struct { string str; } myString;

typedef struct { char letter; } myLetter;

template<>
Gen<myLetter> arbitrary() {
  return Gen<myLetter>([] () -> myLetter {
              vector<char> letters;
              for (int i = int('a'); i <= int('z'); i++) {
                 letters.push_back(char(i));
              }
              for (int i = int('A'); i <= int('Z'); i++) {
                 letters.push_back(char(i));
              }

          return myLetter{elements(letters).generate()};
    });

}


template<>
Gen<myString> arbitrary() {
  return Gen<myString>([] () -> myString {

      auto mkWord = [] () -> string {
    int n = (rand() % 5) + 1;
    auto l = arbitrary<myLetter>();
    string s;
        for (int i = 1; i <= n; i++) {
      s = s + char(l.generate().letter);
    }
        return s;
      };

      auto mkBlanks = [] () -> string {
    int n = rand() & 3;
    string s;
        for(int i = 1; i<= n; i++) {
      s = s + " ";
    }
    return s;
      };

      int nWords = (rand() & 10) + 1;
      string s;

      for (int i = 1; i <= nWords; i++) {
    s = s + mkBlanks() + mkWord() + mkBlanks();
      }

      return myString{s};
    });
}

template<>
string show(myString x) { return "\"" + x.str + "\""; }


myString toMyString(string s) {
  return myString{s};
}

string fromMyString(myString s) {
  return s.str;
}


bool prop1_myString(myString s) {
  return prop1(fromMyString(s));
}

bool prop2_myString(myString s) {
  return prop2(fromMyString(s));
}

bool prop3_myString(myString s) {
  return prop3(fromMyString(s));
}

void quickCheckCountMyString() {

  cout << "\n**** prop1_myString \n";
  quickCheck(prop1_myString);
  cout << "\n**** prop2_myString \n";
  quickCheck(prop2_myString);
  cout << "\n**** prop3_myString \n";
  //  quickCheck(prop3_myString);
  verboseCheck(prop3_myString);

}

void genMyString() {
  Gen<myString> x = arbitrary<myString>();

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

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

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

int main() {
  //  genMyString();
  //  genString();
  //  quickCheckCount();
  quickCheckCountMyString();

}

Einführung in C++ - Teil 5 (QuickCheck: Automatisiertes Testen)