quickcheck/Property.hh

Go to the documentation of this file.

/*
 * Copyright (C) 2009  Cyril Soldani
 * 
 * This file is part of QuickCheck++.
 * 
 * QuickCheck++ is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option)
 * any later version.
 * 
 * QuickCheck++ is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * QuickCheck++. If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef QUICKCHECK_PROPERTY_H
#define QUICKCHECK_PROPERTY_H

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

#include "generate.hh"

namespace quickcheck {

enum Unit { UNIT };

template<class A>
void printArgument(std::ostream& out, size_t n, const A& a)
{
   out << "  " << n << ": " << a << std::endl;
}

template<>
void printArgument(std::ostream&, size_t, const Unit&) { }

template<class A, class B, class C, class D, class E>
class PropertyBase {

   public:

      explicit PropertyBase();

      virtual ~PropertyBase();

      bool check(size_t n = 100, size_t max = 0, bool isVerbose = false,
                 std::ostream& out = std::cout);

   protected:

      void _addFixed(const A& a, const B& b, const C& c, const D& d,
                     const E& e);

   private:

      struct Input {
         A a;
         B b;
         C c;
         D d;
         E e;
      };

      void printInput(std::ostream& out, const A& a, const B& b, const C& c,
                      const D& d, const E& e);

      virtual size_t sizeHint(size_t testNo);

      virtual bool _accepts(const A& a, const B& b, const C& c, const D& d,
                            const E& e) = 0;

      virtual const std::string _classify(const A& a, const B& b, const C& c,
                                          const D& d, const E& e) = 0;

      virtual void _generateInput(size_t n, A& a, B& b, C& c, D& d, E& e) = 0;

      virtual bool _holdsFor(const A& a, const B& b, const C& c, const D& d,
                             const E& e) = 0;

      virtual bool _isTrivialFor(const A& a, const B& b, const C& c,
                                 const D& d, const E& e) = 0;

      std::vector<Input> _fixedInputs;

};

template<class A, class B, class C, class D, class E>
PropertyBase<A, B, C, D, E>::PropertyBase() :
   _fixedInputs(std::vector<Input>())
{
   // Nothing more to do than what was done in initialisation list
}

template<class A, class B, class C, class D, class E>
PropertyBase<A, B, C, D, E>::~PropertyBase()
{
   // Nothing to do, only defined for derivation purpose
}

template<class A, class B, class C, class D, class E>
bool PropertyBase<A, B, C, D, E>::check(size_t n, size_t max, bool isVerbose,
                                        std::ostream& out)
{
   if (max < n)
      max = 5 * n;
   size_t nTrivial = 0;
   // ClassMap maps input classes to the number of their occurrence in the
   // tests
   typedef std::map<const std::string, size_t> ClassMap;
   ClassMap classes;
   // First verifies fixed inputs
   size_t len = _fixedInputs.size();
   size_t testNo;
   for (testNo = 0; testNo < len; ++testNo) {
      const Input& input = _fixedInputs[testNo];
      if (_isTrivialFor(input.a, input.b, input.c, input.d, input.e))
         ++nTrivial;
      ++classes[_classify(input.a, input.b, input.c, input.d, input.e)];
      if (isVerbose) {
         out << "Test " << testNo << ":" << std::endl;
         printInput(out, input.a, input.b, input.c, input.d, input.e);
      }
      if (!_holdsFor(input.a, input.b, input.c, input.d, input.e)) {
         out << "Falsifiable after " << testNo + 1 << " tests for input:" <<
            std::endl;
         printInput(out, input.a, input.b, input.c, input.d, input.e);
         return false;
      }
   }
   // And now the random tests
   n += len;
   size_t attemptNo;
   for (attemptNo = 0; attemptNo < max && testNo < n; ++attemptNo) {
      // Generates random arguments (that may or may not form valid input).
      // Size hint is random test number, so that we begin with small values
      // before going on with larger values.
      A a;
      B b;
      C c;
      D d;
      E e;
      _generateInput(sizeHint(testNo - len), a, b, c, d, e);
      // Only do the test if generated input is valid
      if (_accepts(a, b, c, d, e)) {
         if (_isTrivialFor(a, b, c, d, e))
            ++nTrivial;
         ++classes[_classify(a, b, c, d, e)];
         if (isVerbose) {
            out << "Test " << testNo << ":" << std::endl;
            printInput(out, a, b, c, d, e);
         }
         if (!_holdsFor(a, b, c, d, e)) {
            out << "Falsifiable after " << testNo + 1 << " tests for input:"
               << std::endl;
            printInput(out, a, b, c, d, e);
            return false;
         }
         ++testNo;
      }
   }
   // Prints summary results
   if (testNo < n)
      out << "Arguments exhausted after ";
   else
      out << "OK, passed ";
   out << testNo << " tests";
   if (nTrivial > 0)
      out << " (" << nTrivial * 100 / testNo << "% trivial)";
   out << "." << std::endl;
   // Prints input distribution if necessary
   classes.erase("");
   if (!classes.empty()) {
      // We sort input classes by number of occurrences by building a sorted
      // vector of (occurrences, class) from the class map
      typedef std::vector< std::pair<size_t, std::string> > ClassVec;
      ClassVec sorted;
      for (ClassMap::const_iterator i = classes.begin(); i != classes.end();
           ++i) {
         std::pair<size_t, std::string> elem = make_pair(i->second, i->first);
         ClassVec::iterator pos = lower_bound(sorted.begin(), sorted.end(),
                                              elem);
         sorted.insert(pos, elem);
      }
      std::reverse(sorted.begin(), sorted.end());
      for (ClassVec::const_iterator i = sorted.begin(); i != sorted.end(); ++i)
         out << std::setw(4) << i->first * 100 / testNo << "% " << i->second
            << std::endl;
   }
   return (testNo == n);
}

template<class A, class B, class C, class D, class E>
void PropertyBase<A, B, C, D, E>::_addFixed(const A& a, const B& b, const C& c,
                                            const D& d, const E& e)
{
   Input i = { a, b, c, d, e };
   _fixedInputs.push_back(i);
}

template<class A, class B, class C, class D, class E>
void PropertyBase<A, B, C, D, E>::printInput(std::ostream& out, const A& a,
                                             const B& b, const C& c,
                                             const D& d, const E& e)
{
   // We call printArgument for all arguments as it should print nothing when
   // given UNIT
   printArgument(out, 0, a);
   printArgument(out, 1, b);
   printArgument(out, 2, c);
   printArgument(out, 3, d);
   printArgument(out, 4, e);
}

template<class A, class B, class C, class D, class E>
size_t PropertyBase<A, B, C, D, E>::sizeHint(size_t testNo)
{
   return testNo / 2 + 3;
}

template<class A, class B = Unit, class C = Unit, class D = Unit,
         class E = Unit>
class Property : public PropertyBase<A, B, C, D, E> {

   public:

      virtual void addFixed(const A& a, const B& b, const C& c, const D& d,
                            const E& e);

   private:

      virtual bool accepts(const A& a, const B& b, const C& c, const D& d,
                           const E& e);

      virtual const std::string classify(const A& a, const B& b, const C& c,
                                         const D& d, const E& e);

      virtual void generateInput(size_t n, A& a, B& b, C& c, D& d, E& e);

      virtual bool holdsFor(const A& a, const B& b, const C& c, const D& d,
                            const E& e) = 0;

      virtual bool isTrivialFor(const A& a, const B& b, const C& c, const D& d,
                                const E& e);

      bool _accepts(const A& a, const B& b, const C& c, const D& d,
                    const E& e);

      const std::string _classify(const A& a, const B& b, const C& c,
                                  const D& d, const E& e);

      void _generateInput(size_t n, A& a, B& b, C& c, D& d, E& e);

      bool _holdsFor(const A& a, const B& b, const C& c, const D& d,
                     const E& e);

      bool _isTrivialFor(const A& a, const B& b, const C& c, const D& d,
                         const E& e);

};

template<class A, class B, class C, class D, class E>
void Property<A, B, C, D, E>::addFixed(const A& a, const B& b, const C& c,
                                       const D& d, const E& e)
{
   _addFixed(a, b, c, d, e);
}

template<class A, class B, class C, class D, class E>
bool Property<A, B, C, D, E>::accepts(const A&, const B&, const C&, const D&,
                                      const E&)
{
   return true;
}

template<class A, class B, class C, class D, class E>
const std::string Property<A, B, C, D, E>::classify(
   const A&, const B&, const C&, const D&, const E&)
{
   return "";
}

template<class A, class B, class C, class D, class E>
void Property<A, B, C, D, E>::generateInput(size_t n,
                                            A& a, B& b, C& c, D& d, E& e)
{
   generate(n, a);
   generate(n, b);
   generate(n, c);
   generate(n, d);
   generate(n, e);
}

template<class A, class B, class C, class D, class E>
bool Property<A, B, C, D, E>::isTrivialFor(const A&, const B&, const C&,
                                           const D&, const E&)
{
   return false;
}

template<class A, class B, class C, class D, class E>
bool Property<A, B, C, D, E>::_accepts(const A& a, const B& b, const C& c,
                                       const D& d, const E& e)
{
   return accepts(a, b, c, d, e);
}

template<class A, class B, class C, class D, class E>
const std::string Property<A, B, C, D, E>::_classify(
   const A& a, const B& b, const C& c, const D& d, const E& e)
{
   return classify(a, b, c, d, e);
}

template<class A, class B, class C, class D, class E>
void Property<A, B, C, D, E>::_generateInput(size_t n,
                                             A& a, B& b, C& c, D& d, E& e)
{
   generateInput(n, a, b, c, d, e);
}

template<class A, class B, class C, class D, class E>
bool Property<A, B, C, D, E>::_holdsFor(const A& a, const B& b, const C& c,
                                        const D& d, const E& e)
{
   return holdsFor(a, b, c, d, e);
}

template<class A, class B, class C, class D, class E>
bool Property<A, B, C, D, E>::_isTrivialFor(const A& a, const B& b, const C& c,
                                            const D& d, const E& e)
{
   return isTrivialFor(a, b, c, d, e);
}

template<class A, class B, class C, class D>
class Property<A, B, C, D> : public PropertyBase<A, B, C, D, Unit> {

   public:

      virtual void addFixed(const A& a, const B& b, const C& c, const D& d);

   private:

      virtual bool accepts(const A& a, const B& b, const C& c, const D& d);

      virtual const std::string classify(const A& a, const B& b, const C& c,
                                         const D& d);

      virtual void generateInput(size_t n, A& a, B& b, C& c, D& d);

      virtual bool holdsFor(const A& a, const B& b, const C& c, const D& d)
         = 0;

      virtual bool isTrivialFor(const A& a, const B& b, const C& c,
                                const D& d);

      bool _accepts(const A& a, const B& b, const C& c, const D& d,
                    const Unit& e);

      const std::string _classify(const A& a, const B& b, const C& c,
                                  const D& d, const Unit& e);

      void _generateInput(size_t n, A& a, B& b, C& c, D& d, Unit& e);

      bool _holdsFor(const A& a, const B& b, const C& c, const D& d,
                     const Unit& e);

      bool _isTrivialFor(const A& a, const B& b, const C& c, const D& d,
                         const Unit& e);

};

template<class A, class B, class C, class D>
void Property<A, B, C, D>::addFixed(const A& a, const B& b, const C& c,
                                    const D& d)
{
   _addFixed(a, b, c, d, UNIT);
}

template<class A, class B, class C, class D>
bool Property<A, B, C, D>::accepts(const A&, const B&, const C&, const D&)
{
   return true;
}

template<class A, class B, class C, class D>
const std::string Property<A, B, C, D>::classify(const A&, const B&, const C&,
                                                 const D&)
{
   return "";
}

template<class A, class B, class C, class D>
void Property<A, B, C, D>::generateInput(size_t n, A& a, B& b, C& c, D& d)
{
   generate(n, a);
   generate(n, b);
   generate(n, c);
   generate(n, d);
}

template<class A, class B, class C, class D>
bool Property<A, B, C, D>::isTrivialFor(const A&, const B&, const C&,
                                        const D&)
{
   return false;
}

template<class A, class B, class C, class D>
bool Property<A, B, C, D>::_accepts(const A& a, const B& b, const C& c,
                                    const D& d, const Unit&)
{
   return accepts(a, b, c, d);
}

template<class A, class B, class C, class D>
const std::string Property<A, B, C, D>::_classify(
   const A& a, const B& b, const C& c, const D& d, const Unit&)
{
   return classify(a, b, c, d);
}

template<class A, class B, class C, class D>
void Property<A, B, C, D>::_generateInput(size_t n, A& a, B& b, C& c, D& d, 
                                          Unit&)
{
   generateInput(n, a, b, c, d);
}

template<class A, class B, class C, class D>
bool Property<A, B, C, D>::_holdsFor(const A& a, const B& b, const C& c,
                                     const D& d, const Unit&)
{
   return holdsFor(a, b, c, d);
}

template<class A, class B, class C, class D>
bool Property<A, B, C, D>::_isTrivialFor(const A& a, const B& b, const C& c,
                                         const D& d, const Unit&)
{
   return isTrivialFor(a, b, c, d);
}

template<class A, class B, class C>
class Property<A, B, C> : public PropertyBase<A, B, C, Unit, Unit> {

   public:

   virtual void addFixed(const A& a, const B& b, const C& c);

   private:

   virtual bool accepts(const A& a, const B& b, const C& c);

   virtual const std::string classify(const A& a, const B& b, const C& c);

   virtual void generateInput(size_t n, A& a, B& b, C& c);

   virtual bool holdsFor(const A& a, const B& b, const C& c) = 0;

   virtual bool isTrivialFor(const A& a, const B& b, const C& c);

   bool _accepts(const A& a, const B& b, const C& c, const Unit& d,
                 const Unit& e);

   const std::string _classify(const A& a, const B& b, const C& c,
                               const Unit& d, const Unit& e);

   void _generateInput(size_t n, A& a, B& b, C& c, Unit& d, Unit& e);

   bool _holdsFor(const A& a, const B& b, const C& c, const Unit& d,
                  const Unit& e);

   bool _isTrivialFor(const A& a, const B& b, const C& c, const Unit& d,
                      const Unit& e);

};

template<class A, class B, class C>
void Property<A, B, C>::addFixed(const A& a, const B& b, const C& c)
{
   _addFixed(a, b, c, UNIT, UNIT);
}

template<class A, class B, class C>
bool Property<A, B, C>::accepts(const A&, const B&, const C&)
{
   return true;
}

template<class A, class B, class C>
const std::string Property<A, B, C>::classify(const A&, const B&, const C&)
{
   return "";
}

template<class A, class B, class C>
void Property<A, B, C>::generateInput(size_t n, A& a, B& b, C& c)
{
   generate(n, a);
   generate(n, b);
   generate(n, c);
}

template<class A, class B, class C>
bool Property<A, B, C>::isTrivialFor(const A&, const B&, const C&)
{
   return false;
}

template<class A, class B, class C>
bool Property<A, B, C>::_accepts(const A& a, const B& b, const C& c,
                                 const Unit&, const Unit&)
{
   return accepts(a, b, c);
}

template<class A, class B, class C>
const std::string Property<A, B, C>::_classify(
   const A& a, const B& b, const C& c, const Unit&, const Unit&)
{
   return classify(a, b, c);
}

template<class A, class B, class C>
void Property<A, B, C>::_generateInput(size_t n, A& a, B& b, C& c, Unit&, 
                                       Unit&)
{
   generateInput(n, a, b, c);
}

template<class A, class B, class C>
bool Property<A, B, C>::_holdsFor(const A& a, const B& b, const C& c,
                                  const Unit&, const Unit&)
{
   return holdsFor(a, b, c);
}

template<class A, class B, class C>
bool Property<A, B, C>::_isTrivialFor(const A& a, const B& b, const C& c,
                                      const Unit&, const Unit&)
{
   return isTrivialFor(a, b, c);
}

template<class A, class B>
class Property<A, B> : public PropertyBase<A, B, Unit, Unit, Unit> {

   public:

      virtual void addFixed(const A& a, const B& b);

   private:

      virtual bool accepts(const A& a, const B& b);

      virtual const std::string classify(const A& a, const B& b);

      virtual void generateInput(size_t n, A& a, B& b);

      virtual bool holdsFor(const A& a, const B& b) = 0;

      virtual bool isTrivialFor(const A& a, const B& b);

      bool _accepts(const A& a, const B& b, const Unit& c, const Unit& d,
                    const Unit& e);

      const std::string _classify(const A& a, const B& b, const Unit& c,
                                  const Unit& d, const Unit& e);

      void _generateInput(size_t n, A& a, B& b, Unit& c, Unit& d, Unit& e);

      bool _holdsFor(const A& a, const B& b, const Unit& c, const Unit& d,
                     const Unit& e);

      bool _isTrivialFor(const A& a, const B& b, const Unit& c, const Unit& d,
                         const Unit& e);

};

template<class A, class B>
void Property<A, B>::addFixed(const A& a, const B& b)
{
   _addFixed(a, b, UNIT, UNIT, UNIT);
}

template<class A, class B>
bool Property<A, B>::accepts(const A&, const B&)
{
   return true;
}

template<class A, class B>
const std::string Property<A, B>::classify(const A&, const B&)
{
   return "";
}

template<class A, class B>
void Property<A, B>::generateInput(size_t n, A& a, B& b)
{
   generate(n, a);
   generate(n, b);
}

template<class A, class B>
bool Property<A, B>::isTrivialFor(const A&, const B&)
{
   return false;
}

template<class A, class B>
bool Property<A, B>::_accepts(const A& a, const B& b, const Unit&,
                              const Unit&, const Unit&)
{
   return accepts(a, b);
}

template<class A, class B>
const std::string Property<A, B>::_classify(
   const A& a, const B& b, const Unit&, const Unit&, const Unit&)
{
   return classify(a, b);
}

template<class A, class B>
void Property<A, B>::_generateInput(size_t n, A& a, B& b, Unit&, Unit&, Unit&)
{
   generateInput(n, a, b);
}

template<class A, class B>
bool Property<A, B>::_holdsFor(const A& a, const B& b, const Unit&,
                               const Unit&, const Unit&)
{
   return holdsFor(a, b);
}

template<class A, class B>
bool Property<A, B>::_isTrivialFor(const A& a, const B& b, const Unit&,
                                   const Unit&, const Unit&)
{
   return isTrivialFor(a, b);
}

template<class A>
class Property<A> : public PropertyBase<A, Unit, Unit, Unit, Unit> {

   public:

      virtual void addFixed(const A& a);

   private:

      virtual bool accepts(const A& a);

      virtual const std::string classify(const A& a);

      virtual void generateInput(size_t n, A& a);

      virtual bool holdsFor(const A& a) = 0;

      virtual bool isTrivialFor(const A& a);

      bool _accepts(const A& a, const Unit& b, const Unit& c, const Unit& d,
                    const Unit& e);

      const std::string _classify(const A& a, const Unit& b, const Unit& c,
                                  const Unit& d, const Unit& e);

      void _generateInput(size_t n, A& a, Unit& b, Unit& c, Unit& d, Unit& e);

      bool _holdsFor(const A& a, const Unit& b, const Unit& c, const Unit& d,
                     const Unit& e);

      bool _isTrivialFor(const A& a, const Unit& b, const Unit& c,
                         const Unit& d, const Unit& e);

};

template<class A>
void Property<A>::addFixed(const A& a)
{
   _addFixed(a, UNIT, UNIT, UNIT, UNIT);
}

template<class A>
bool Property<A>::accepts(const A&)
{
   return true;
}

template<class A>
const std::string Property<A>::classify(const A&)
{
   return "";
}

template<class A>
void Property<A>::generateInput(size_t n, A& a)
{
   generate(n, a);
}

template<class A>
bool Property<A>::isTrivialFor(const A&)
{
   return false;
}

template<class A>
bool Property<A>::_accepts(const A& a, const Unit&, const Unit&, const Unit&,
                           const Unit&)
{
   return accepts(a);
}

template<class A>
const std::string Property<A>::_classify(const A& a, const Unit&, const Unit&,
                                         const Unit&, const Unit&)
{
   return classify(a);
}

template<class A>
void Property<A>::_generateInput(size_t n, A& a, Unit&, Unit&, Unit&, Unit&)
{
   generateInput(n, a);
}

template<class A>
bool Property<A>::_holdsFor(const A& a, const Unit&, const Unit&, const Unit&,
                            const Unit&)
{
   return holdsFor(a);
}

template<class A>
bool Property<A>::_isTrivialFor(const A& a, const Unit&, const Unit&,
                                const Unit&, const Unit&)
{
   return isTrivialFor(a);
}

}

#endif // !QUICKCHECK_PROPERTY_H

---