1 | /* @flow weak */
|
2 | /**
|
3 | # JSVerify
|
4 |
|
5 | <img src="https://raw.githubusercontent.com/jsverify/jsverify/master/jsverify-300.png" align="right" height="100" />
|
6 |
|
7 | > Property based checking. Like QuickCheck.
|
8 |
|
9 | [![Build Status](https://secure.travis-ci.org/jsverify/jsverify.svg?branch=master)](http://travis-ci.org/jsverify/jsverify)
|
10 | [![NPM version](https://badge.fury.io/js/jsverify.svg)](http://badge.fury.io/js/jsverify)
|
11 | [![Dependency Status](https://david-dm.org/jsverify/jsverify.svg)](https://david-dm.org/jsverify/jsverify)
|
12 | [![devDependency Status](https://david-dm.org/jsverify/jsverify/dev-status.svg)](https://david-dm.org/jsverify/jsverify#info=devDependencies)
|
13 | [![Code Climate](https://img.shields.io/codeclimate/github/jsverify/jsverify.svg)](https://codeclimate.com/github/jsverify/jsverify)
|
14 |
|
15 | ## Getting Started
|
16 |
|
17 | Install the module with: `npm install jsverify`
|
18 |
|
19 | ## Synopsis
|
20 |
|
21 | ```js
|
22 | var jsc = require("jsverify");
|
23 |
|
24 | // forall (f : bool -> bool) (b : bool), f (f (f b)) = f(b).
|
25 | var boolFnAppliedThrice =
|
26 | jsc.forall("bool -> bool", "bool", function (f, b) {
|
27 | return f(f(f(b))) === f(b);
|
28 | });
|
29 |
|
30 | jsc.assert(boolFnAppliedThrice);
|
31 | // OK, passed 100 tests
|
32 | ```
|
33 | */
|
34 | ;
|
35 |
|
36 | /**
|
37 | ## Documentation
|
38 |
|
39 | ### Usage with [mocha](http://visionmedia.github.io/mocha/)
|
40 |
|
41 | Using jsverify with mocha is easy, just define the properties and use `jsverify.assert`.
|
42 |
|
43 | Starting from version 0.4.3 you can write your specs without any boilerplate:
|
44 |
|
45 | ```js
|
46 | describe("sort", function () {
|
47 | jsc.property("idempotent", "array nat", function (arr) {
|
48 | return _.isEqual(sort(sort(arr)), sort(arr));
|
49 | });
|
50 | });
|
51 | ```
|
52 |
|
53 | You can also provide `--jsverifyRngState state` command line argument, to run tests with particular random generator state.
|
54 |
|
55 | ```
|
56 | $ mocha examples/nat.js
|
57 |
|
58 | 1) natural numbers are less than 90:
|
59 | Error: Failed after 49 tests and 1 shrinks. rngState: 074e9b5f037a8c21d6; Counterexample: 90;
|
60 |
|
61 | $ mocha examples/nat.js --grep 'are less than' --jsverifyRngState 074e9b5f037a8c21d6
|
62 |
|
63 | 1) natural numbers are less than 90:
|
64 | Error: Failed after 1 tests and 1 shrinks. rngState: 074e9b5f037a8c21d6; Counterexample: 90;
|
65 | ```
|
66 |
|
67 | Errorneous case is found with first try.
|
68 |
|
69 | ### Usage with [jasmine](http://pivotal.github.io/jasmine/)
|
70 |
|
71 | Check [jasmineHelpers.js](helpers/jasmineHelpers.js) and [jasmineHelpers2.js](helpers/jasmineHelpers2.js) for jasmine 1.3 and 2.0 respectively.
|
72 |
|
73 | ## API Reference
|
74 |
|
75 | > _Testing shows the presence, not the absence of bugs._
|
76 | >
|
77 | > Edsger W. Dijkstra
|
78 |
|
79 | To show that propositions hold, we need to construct proofs.
|
80 | There are two extremes: proof by example (unit tests) and formal (machine-checked) proof.
|
81 | Property-based testing is somewhere in between.
|
82 | We formulate propositions, invariants or other properties we believe to hold, but
|
83 | only test it to hold for numerous (randomly generated) values.
|
84 |
|
85 | Types and function signatures are written in [Coq](http://coq.inria.fr/)/[Haskell](http://www.haskell.org/haskellwiki/Haskell) influented style:
|
86 | C# -style `List<T> filter(List<T> v, Func<T, bool> predicate)` is represented by
|
87 | `filter(v: array T, predicate: T -> bool): array T` in our style.
|
88 |
|
89 | Methods and objects live in `jsc` object, e.g. `shrink.bless` method is used by
|
90 | ```js
|
91 | var jsc = require("jsverify");
|
92 | var foo = jsc.shrink.bless(...);
|
93 | ```
|
94 |
|
95 | Methods starting with `.dot` are prototype methods:
|
96 | ```js
|
97 | var arb = jsc.nat;
|
98 | var arb2 = jsc.nat.smap(f, g);
|
99 | ```
|
100 |
|
101 | `jsverify` can operate with both synchronous and asynchronous-promise properties.
|
102 | Generally every property can be wrapped inside [functor](http://learnyouahaskell.com/functors-applicative-functors-and-monoids),
|
103 | for now in either identity or promise functor, for synchronous and promise properties respectively.
|
104 | */
|
105 |
|
106 | var assert = require("assert");
|
107 | var lazyseq = require("lazy-seq");
|
108 |
|
109 | var api = require("./api.js");
|
110 | var either = require("./either.js");
|
111 | var environment = require("./environment.js");
|
112 | var FMap = require("./finitemap.js");
|
113 | var fn = require("./fn.js");
|
114 | var functor = require("./functor.js");
|
115 | var random = require("./random.js");
|
116 | var show = require("./show.js");
|
117 | var shrink = require("./shrink.js");
|
118 | var suchthat = require("./suchthat.js");
|
119 | var typify = require("./typify.js");
|
120 | var utils = require("./utils.js");
|
121 |
|
122 | /**
|
123 | ### Properties
|
124 | */
|
125 |
|
126 | function shrinkResult(arbs, x, test, size, shrinksN, exc, transform) {
|
127 | assert(arbs.length === x.length, "shrinkResult: arbs and x has to be of same size");
|
128 | assert(typeof size === "number", "shrinkResult: size should be number");
|
129 | assert(typeof shrinksN === "number", "shrinkResult: shrinkN should be number");
|
130 |
|
131 | var shrinks = utils.pluck(arbs, "shrink");
|
132 | var shows = utils.pluck(arbs, "show");
|
133 |
|
134 | var shrinked = shrink.tuple(shrinks, x);
|
135 |
|
136 | var shrinkP = lazyseq.fold(shrinked, true, function (y, rest) {
|
137 | var t = test(size, y, shrinksN + 1);
|
138 | return functor.map(t, function (tprime) {
|
139 | return tprime !== true ? tprime : rest();
|
140 | });
|
141 | });
|
142 |
|
143 | return functor.map(shrinkP, function (shrinkPPrime) {
|
144 | if (shrinkPPrime === true) {
|
145 | var res = {
|
146 | counterexample: x,
|
147 | counterexamplestr: show.tuple(shows, x),
|
148 | shrinks: shrinksN,
|
149 | exc: exc,
|
150 | };
|
151 | return transform(res);
|
152 | } else {
|
153 | return shrinkPPrime;
|
154 | }
|
155 | });
|
156 | }
|
157 |
|
158 | function isArbitrary(arb) {
|
159 | return (typeof arb === "object" || typeof arb === "function") &&
|
160 | typeof arb.generator === "function" &&
|
161 | typeof arb.shrink === "function" &&
|
162 | typeof arb.show === "function";
|
163 | }
|
164 |
|
165 | /**
|
166 | - `forall(arbs: arbitrary a ..., userenv: (map arbitrary)?, prop : a -> property): property`
|
167 |
|
168 | Property constructor
|
169 | */
|
170 | function forall() {
|
171 | var args = Array.prototype.slice.call(arguments);
|
172 | var gens = args.slice(0, -1);
|
173 | var property = args[args.length - 1];
|
174 | var env;
|
175 |
|
176 | var lastgen = gens[gens.length - 1];
|
177 |
|
178 | if (!isArbitrary(lastgen) && typeof lastgen !== "string") {
|
179 | env = utils.merge(environment, lastgen);
|
180 | gens = gens.slice(0, -1);
|
181 | } else {
|
182 | env = environment;
|
183 | }
|
184 |
|
185 | // Map typify-dsl to hard generators
|
186 | gens = gens.map(function (g) {
|
187 | g = typeof g === "string" ? typify.parseTypify(env, g) : g;
|
188 | return utils.force(g);
|
189 | });
|
190 |
|
191 | assert(typeof property === "function", "property should be a function");
|
192 |
|
193 | function test(size, x, shrinks) {
|
194 | assert(Array.isArray(x), "generators results should be always tuple");
|
195 |
|
196 | return functor.bind(property, x, function (r, exc) {
|
197 | if (r === true) { return true; }
|
198 | if (typeof r === "function") {
|
199 | var rRec = r(size);
|
200 |
|
201 | return functor.map(rRec, function (rRecPrime) {
|
202 | if (rRecPrime === true) {
|
203 | return true;
|
204 | } else {
|
205 | return shrinkResult(gens, x, test, size, shrinks, exc, function (rr) {
|
206 | return {
|
207 | counterexample: rr.counterexample.concat(rRecPrime.counterexample),
|
208 | counterexamplestr: rr.counterexamplestr ,//+ "; " + rRec.counterexamplestr,
|
209 | shrinks: rr.shrinks,
|
210 | exc: rr.exc || rRecPrime.exc,
|
211 | };
|
212 | });
|
213 | }
|
214 | });
|
215 | }
|
216 |
|
217 | return shrinkResult(gens, x, test, size, shrinks, exc, utils.identity);
|
218 | });
|
219 | }
|
220 |
|
221 | return function (size) {
|
222 | var x = gens.map(function (arb) { return arb.generator(size); });
|
223 | var r = test(size, x, 0);
|
224 | return r;
|
225 | };
|
226 | }
|
227 |
|
228 | function formatFailedCase(r, state) {
|
229 | var msg = "Failed after " + r.tests + " tests and " + r.shrinks + " shrinks. ";
|
230 | msg += "rngState: " + (r.rngState || state) + "; ";
|
231 | msg += "Counterexample: " + r.counterexamplestr + "; ";
|
232 | if (r.exc) {
|
233 | msg += "Exception: " + (r.exc instanceof Error ? r.exc.message : r.exc);
|
234 | }
|
235 | return msg;
|
236 | }
|
237 |
|
238 | function findRngState(argv) {
|
239 | for (var i = 0; i < argv.length - 1; i++) {
|
240 | if (argv[i] === "--jsverifyRngState") {
|
241 | return argv[i + 1];
|
242 | }
|
243 | }
|
244 | }
|
245 |
|
246 | /**
|
247 | - `check (prop: property, opts: checkoptions?): result`
|
248 |
|
249 | Run random checks for given `prop`. If `prop` is promise based, result is also wrapped in promise.
|
250 |
|
251 | Options:
|
252 | - `opts.tests` - test count to run, default 100
|
253 | - `opts.size` - maximum size of generated values, default 50
|
254 | - `opts.quiet` - do not `console.log`
|
255 | - `opts.rngState` - state string for the rng
|
256 |
|
257 | The `result` is `true` if check succeeds, otherwise it's an object with various fields:
|
258 | - `counterexample` - an input for which property fails.
|
259 | - `tests` - number of tests run before failing case is found
|
260 | - `shrinks` - number of shrinks performed
|
261 | - `exc` - an optional exception thrown by property function
|
262 | - `rngState` - random number generator's state before execution of the property
|
263 | */
|
264 | function check(property, opts) {
|
265 | opts = opts || {};
|
266 | opts.size = opts.size || 50;
|
267 | opts.tests = opts.tests || 100;
|
268 | opts.quiet = opts.quiet || false;
|
269 |
|
270 | assert(typeof property === "function", "property should be a function");
|
271 |
|
272 | var state;
|
273 |
|
274 | if (opts.rngState) {
|
275 | random.setStateString(opts.rngState);
|
276 | } else if (typeof process !== "undefined") {
|
277 | var argvState = findRngState(process.argv);
|
278 | if (argvState) {
|
279 | random.setStateString(argvState);
|
280 | }
|
281 | }
|
282 |
|
283 | function loop(i) {
|
284 | state = random.currentStateString();
|
285 | if (i > opts.tests) {
|
286 | return true;
|
287 | }
|
288 |
|
289 | var size = random(0, opts.size);
|
290 |
|
291 | var r = property(size);
|
292 | return functor.map(r, function (rPrime) {
|
293 | if (rPrime === true) {
|
294 | return loop(i + 1);
|
295 | } else {
|
296 | rPrime.tests = i;
|
297 | /* global console */
|
298 | if (!opts.quiet) {
|
299 | console.error(formatFailedCase(rPrime, state), rPrime.counterexample);
|
300 | }
|
301 | return rPrime;
|
302 | }
|
303 | });
|
304 | }
|
305 |
|
306 | return functor.map(loop(1), function (r) {
|
307 | if (r === true) {
|
308 | if (!opts.quiet) { console.info("OK, passed " + opts.tests + " tests"); }
|
309 | } else {
|
310 | r.rngState = state;
|
311 | }
|
312 |
|
313 | return r;
|
314 | });
|
315 | }
|
316 |
|
317 | /**
|
318 | - `assert(prop: property, opts: checkoptions?) : void`
|
319 |
|
320 | Same as `check`, but throw exception if property doesn't hold.
|
321 | */
|
322 | function checkThrow(property, opts) {
|
323 | opts = opts || {};
|
324 | if (opts.quiet === undefined) {
|
325 | opts.quiet = true;
|
326 | }
|
327 |
|
328 | return functor.map(check(property, opts), function (r) {
|
329 | if (r !== true) {
|
330 | throw new Error(formatFailedCase(r));
|
331 | }
|
332 | });
|
333 | }
|
334 |
|
335 | /**
|
336 | - `property(name: string, ...)`
|
337 |
|
338 | Assuming there is globally defined `it`, the same as:
|
339 |
|
340 | ```js
|
341 | it(name, function () {
|
342 | jsc.assert(jsc.forall(...));
|
343 | }
|
344 | ```
|
345 |
|
346 | You can use `property` to write facts too:
|
347 | ```js
|
348 | jsc.property("+0 === -0", function () {
|
349 | return +0 === -0;
|
350 | });
|
351 | ```
|
352 | */
|
353 | function bddProperty(name) {
|
354 | /* global it: true */
|
355 | var args = Array.prototype.slice.call(arguments, 1);
|
356 | if (args.length === 1) {
|
357 | it(name, function () {
|
358 | return functor.map(args[0](), function (result) {
|
359 | if (result !== true) {
|
360 | throw new Error(name + " doesn't hold");
|
361 | }
|
362 | });
|
363 | });
|
364 | } else {
|
365 | var prop = forall.apply(undefined, args);
|
366 | it(name, function () {
|
367 | return checkThrow(prop);
|
368 | });
|
369 | }
|
370 | /* global it: false */
|
371 | }
|
372 |
|
373 | /**
|
374 | - `compile(desc: string, env: typeEnv?): arbitrary a`
|
375 |
|
376 | Compile the type describiption in provided type environment, or default one.
|
377 | */
|
378 | function compile(str, env) {
|
379 | env = env ? utils.merge(environment, env) : environment;
|
380 | return typify.parseTypify(env, str);
|
381 | }
|
382 |
|
383 | /**
|
384 | - `sampler(arb: arbitrary a, genSize: nat = 10): (sampleSize: nat?) -> a`
|
385 |
|
386 | Create a sampler for a given arbitrary with an optional size. Handy when used in
|
387 | a REPL:
|
388 | ```
|
389 | > jsc = require('jsverify') // or require('./lib/jsverify') w/in the project
|
390 | ...
|
391 | > jsonSampler = jsc.sampler(jsc.json, 4)
|
392 | [Function]
|
393 | > jsonSampler()
|
394 | 0.08467432763427496
|
395 | > jsonSampler()
|
396 | [ [ [] ] ]
|
397 | > jsonSampler()
|
398 | ''
|
399 | > sampledJson(2)
|
400 | [-0.4199344692751765, false]
|
401 | ```
|
402 | */
|
403 | function sampler(arb, size) {
|
404 | size = typeof size === "number" ? Math.abs(size) : 10;
|
405 | return function (count) {
|
406 | if (typeof count === "number") {
|
407 | var acc = [];
|
408 | count = Math.abs(count);
|
409 | for (var i = 0; i < count; i++) {
|
410 | acc.push(arb.generator(size));
|
411 | }
|
412 | return acc;
|
413 | } else {
|
414 | return arb.generator(size);
|
415 | }
|
416 | };
|
417 | }
|
418 |
|
419 | /**
|
420 | ### Types
|
421 |
|
422 | - `generator a` is a function `(size: nat) -> a`.
|
423 | - `show` is a function `a -> string`.
|
424 | - `shrink` is a function `a -> [a]`, returning *smaller* values.
|
425 | - `arbitrary a` is a triple of generator, shrink and show functions.
|
426 | - `{ generator: nat -> a, shrink : a -> array a, show: a -> string }`
|
427 |
|
428 | ### Blessing
|
429 |
|
430 | We chose to respresent generators and shrinks by functions, yet we would
|
431 | like to have additional methods on them. Thus we *bless* objects with
|
432 | additional properties.
|
433 |
|
434 | Usually you don't need to bless anything explicitly, as all combinators
|
435 | return blessed values.
|
436 |
|
437 | See [perldoc for bless](http://perldoc.perl.org/functions/bless.html).
|
438 | */
|
439 |
|
440 | /// include ./typify.js
|
441 | /// include ./arbitraryBless.js
|
442 | /// include ./bless.js
|
443 | /// include ./primitive.js
|
444 | /// include ./arbitrary.js
|
445 | /// include ./recordWithEnv.js
|
446 | /// include ./record.js
|
447 | /// include ./string.js
|
448 | /// include ./fn.js
|
449 | /// include ./small.js
|
450 | /// include ./generator.js
|
451 | /// include ./shrink.js
|
452 | /// include ./show.js
|
453 | /// include ./random.js
|
454 | /// include ./either.js
|
455 | /// include ./utils.js
|
456 |
|
457 | // Export
|
458 | var jsc = {
|
459 | forall: forall,
|
460 | check: check,
|
461 | assert: checkThrow,
|
462 | property: bddProperty,
|
463 | sampler: sampler,
|
464 |
|
465 | // generators
|
466 | fn: fn.fn,
|
467 | fun: fn.fn,
|
468 | suchthat: suchthat.suchthat,
|
469 |
|
470 | // either
|
471 | left: either.left,
|
472 | right: either.right,
|
473 |
|
474 | // compile
|
475 | compile: compile,
|
476 |
|
477 | generator: api.generator,
|
478 | shrink: api.shrink,
|
479 |
|
480 | // internal utility lib
|
481 | random: random,
|
482 |
|
483 | show: show,
|
484 | utils: utils,
|
485 | _: {
|
486 | FMap: FMap,
|
487 | },
|
488 | };
|
489 |
|
490 | /* primitives */
|
491 | var k;
|
492 | for (k in api.arbitrary) {
|
493 | jsc[k] = api.arbitrary[k];
|
494 | }
|
495 |
|
496 | module.exports = jsc;
|
497 |
|
498 | /// plain ../FAQ.md
|
499 | /// plain ../CONTRIBUTING.md
|
500 | /// plain ../CHANGELOG.md
|
501 | /// plain ../related-work.md
|
502 | /// plain ../LICENSE
|