1 /**
2    Random Testing with arbitrary data.
3  */
4 module qcheck.quickcheck;
5 
6 import std.conv, std.datetime, std.exception, std.traits, std.typecons, std.typetuple, std.stdio;
7 import core.exception : AssertError;
8 import qcheck.arbitrary, qcheck.config, qcheck.exceptions;
9 
10 /// Result of a testee. It is okay for a testee to just return a boolean result.
11 enum QCheckResult
12 {
13     discard = -1, /// discard input
14     pass = true, /// test succeeded
15     ok = pass, /// alias for pass
16     fail = false, /// test failed
17 }
18 
19 /**
20    Feed testee with arbitrary data to check that it behaves correctly.
21  */
22 bool quickCheck(alias Testee, Generators...)(Config config=Config.init)
23 {
24     alias TypeTuple!(staticMap!(Unqual, ParameterTypeTuple!Testee)) TP;
25 
26     size_t succeeded, failed, discarded;
27 
28     alias Tuple!(size_t, Tuple!TP, string) FailPair;
29 
30     FailPair[] failingParams;
31     Tuple!TP params;
32 
33     string head = Identifier!Testee;
34     if (head.length > 16)
35         head = head[0 .. 13] ~ "...";
36     writef("CHECK: %-16s [                                                  ]\r", head);
37     writef("CHECK: %-16s [", head);
38     ushort progress;
39     while (succeeded < config.maxSuccess && discarded < config.maxDiscarded && failed < config.maxFails)
40     {
41         try
42         {
43             params = getArbitraryTuple!(Tuple!TP, Generators)(config);
44             auto result = Testee(params.tupleof);
45 
46             if (result == QCheckResult.fail)
47             {
48                 failingParams ~= FailPair(succeeded + failed, params, Identifier!Testee ~ " false");
49                 ++failed;
50             }
51             else if (result == QCheckResult.ok)
52             {
53                 ++succeeded;
54                 if (progress < 50 * succeeded / config.maxSuccess)
55                 {
56                     do
57                     {
58                         write("=");
59                     } while (++progress < 50 * succeeded / config.maxSuccess);
60                     stdout.flush();
61                 }
62             }
63             else if (result == QCheckResult.discard)
64             {
65                 ++discarded;
66             }
67             else
68             {
69                 assert(0, "Unexpected return value " ~ to!string(result));
70             }
71         }
72         catch(AssertError e)
73         {
74             failingParams ~= FailPair(succeeded + failed, params, to!string(e));
75             ++failed;
76             if (!config.keepGoing)
77                 break;
78         }
79         catch(Exception e)
80         {
81             failingParams ~= FailPair(succeeded + failed, params, to!string(e));
82             ++failed;
83             if (!config.keepGoing)
84                 break;
85         }
86     }
87 
88     if (!failed && succeeded == config.maxSuccess)
89     {
90         writeln("] OK");
91     }
92     else if (!failed)
93     {
94         assert(succeeded < config.maxSuccess);
95         auto total = succeeded + discarded;
96         writefln("] FAIL (%s/%s)", succeeded, total);
97         writeln("Giving up after too many discards.");
98     }
99     else
100     {
101         writeln("] FAIL");
102         writeln("Failing Parameters:");
103         foreach (p; failingParams)
104             writefln("======== %s ========\n%s\n%s", p[]);
105     }
106 
107     return failingParams.length == 0;
108 }
109 
110 /// comparing sort algorithms
111 unittest
112 {
113     // https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#D
114     static T[] bubbleSort(T)(T[] data) pure nothrow
115     {
116         import std.algorithm : swap;
117         foreach_reverse (n; 0 .. data.length)
118         {
119             bool swapped;
120             foreach (i; 0 .. n)
121                 if (data[i] > data[i + 1]) {
122                     swap(data[i], data[i + 1]);
123                     swapped = true;
124                 }
125             if (!swapped)
126                 break;
127         }
128         return data;
129     }
130 
131     /// random data is injected into testee arguments
132     static bool testee(ubyte[] data)
133     {
134         import std.algorithm : equal, sort;
135 
136         return bubbleSort(data.dup).equal(data.sort());
137     }
138 
139     quickCheck!testee;
140 }
141 
142 /// testee can reject random arguments to enforce additional constraints
143 unittest
144 {
145     static QCheckResult testee(string haystack, string needle)
146     {
147         import std.algorithm : canFind, boyerMooreFinder;
148 
149         if (needle.length < haystack.length)
150             return QCheckResult.discard;
151 
152         auto bmFinder = boyerMooreFinder(needle);
153         immutable found = !!bmFinder.beFound(haystack).length;
154         return found == haystack.canFind(needle) ? QCheckResult.pass : QCheckResult.fail;
155     }
156 
157     randomSeed = 42;
158     quickCheck!testee;
159 }
160 
161 private:
162 
163 template Identifier(alias Testee)
164 {
165     enum Identifier = __traits(identifier, Testee);
166 }