From 8bcaac40ee1afb8c36f98beabe0348ae3713d44d Mon Sep 17 00:00:00 2001 From: Arnaud Bailly Date: Sat, 25 Jan 2025 18:31:41 +0100 Subject: Generate a random list --- .gitignore | 1 + pbt/ts/package-lock.json | 20 ++++++++++++++++++ pbt/ts/package.json | 9 +++++--- pbt/ts/src/index.ts | 40 +++++++++++++++++++++++------------- pbt/ts/src/property.ts | 53 ++++++++++++++++++++++++++++++++++++++++++++++++ pbt/ts/tsconfig.json | 2 +- 6 files changed, 107 insertions(+), 18 deletions(-) create mode 100644 pbt/ts/src/property.ts diff --git a/.gitignore b/.gitignore index 1952f6b..1972246 100644 --- a/.gitignore +++ b/.gitignore @@ -4,3 +4,4 @@ .clj-kondo .lsp node_modules/ +*.ts# diff --git a/pbt/ts/package-lock.json b/pbt/ts/package-lock.json index 4e4aeff..56e87d3 100644 --- a/pbt/ts/package-lock.json +++ b/pbt/ts/package-lock.json @@ -5,6 +5,8 @@ "packages": { "": { "dependencies": { + "dotenv": "^16.4.7", + "prando": "^6.0.1", "typescript": "^5.7.3" }, "devDependencies": { @@ -809,6 +811,18 @@ "node": ">=6.0.0" } }, + "node_modules/dotenv": { + "version": "16.4.7", + "resolved": "https://registry.npmjs.org/dotenv/-/dotenv-16.4.7.tgz", + "integrity": "sha512-47qPchRCykZC03FhkYAhrvwU4xDBFIj1QPqaarj6mdM/hgUzfPHcpkHJOn3mJAufFeeAxAzeGsr5X0M4k6fLZQ==", + "license": "BSD-2-Clause", + "engines": { + "node": ">=12" + }, + "funding": { + "url": "https://dotenvx.com" + } + }, "node_modules/emoji-regex": { "version": "8.0.0", "resolved": "https://registry.npmjs.org/emoji-regex/-/emoji-regex-8.0.0.tgz", @@ -2324,6 +2338,12 @@ "url": "https://github.com/sponsors/jonschlinkert" } }, + "node_modules/prando": { + "version": "6.0.1", + "resolved": "https://registry.npmjs.org/prando/-/prando-6.0.1.tgz", + "integrity": "sha512-ghUWxQ1T9IJmPu6eshc3VU0OwveUtXQ33ZLXYUcz1Oc5ppKLDXKp0TBDj6b0epwhEctzcQSNGR2iHyvQSn4W5A==", + "license": "MIT" + }, "node_modules/prelude-ls": { "version": "1.2.1", "resolved": "https://registry.npmjs.org/prelude-ls/-/prelude-ls-1.2.1.tgz", diff --git a/pbt/ts/package.json b/pbt/ts/package.json index 5aab336..c11b4ba 100644 --- a/pbt/ts/package.json +++ b/pbt/ts/package.json @@ -1,11 +1,13 @@ { "dependencies": { + "dotenv": "^16.4.7", + "prando": "^6.0.1", "typescript": "^5.7.3" }, "devDependencies": { + "@types/node": "^22.7.5", "gts": "^6.0.2", - "typescript": "^5.6.3", - "@types/node": "^22.7.5" + "typescript": "^5.6.3" }, "scripts": { "lint": "gts lint", @@ -14,6 +16,7 @@ "fix": "gts fix", "prepare": "npm run compile", "pretest": "npm run compile", - "posttest": "npm run lint" + "posttest": "npm run lint", + "app": "node build/src/index.js" } } diff --git a/pbt/ts/src/index.ts b/pbt/ts/src/index.ts index 3a71ccf..46454f0 100644 --- a/pbt/ts/src/index.ts +++ b/pbt/ts/src/index.ts @@ -1,20 +1,32 @@ -type Result = 'OK' | 'Falsified' | 'Exception'; +import "dotenv/config"; +import Prando from 'prando'; +import { Gen } from "./property"; -type TestResult = { - result: Result, - seed: number, - counterexample: A | null -}; +let genint: Gen = (rng: Prando) => + (size: number) => + rng.nextInt(-size, size); -type Predicate = (a: A) => boolean; -type Gen = (s: number) => (() => A); +function genlist(gen: Gen): Gen { + return (rng: Prando) => { + let g = gen(rng); + return (size: number) => { + let result = []; + for (let i = 0; i < size; i++) { + result.push(g(size)); + } + return result; + }; + }; +} -type Shrinker = (a: A) => [A]; +function generate(gen: Gen): A { + let rng = new Prando(Math.random() * 1000); + return gen(rng)(100); +} -function property(seed: number, - predicate: Predicate, - generator: Gen, - shrinker: Shrinker): TestResult { - return {result: 'OK', seed, counterexample: null}; +async function main() { + console.log('list: ' + generate(genlist(genint))); } + +main(); diff --git a/pbt/ts/src/property.ts b/pbt/ts/src/property.ts new file mode 100644 index 0000000..e8d3a21 --- /dev/null +++ b/pbt/ts/src/property.ts @@ -0,0 +1,53 @@ +import Prando from "prando"; + +type Result = 'OK' | 'Falsified' | 'Exception'; + +type ShrinkResult = { counterexample: A, shrinks: number }; + +type TestResult = { + result: Result, + counterexample: ShrinkResult | null +}; + +type Predicate = (a: A) => boolean; + +export type Gen = (rng: Prando) => ((size: number) => A); + +type Shrinker = (a: A) => [A]; + +const MAX_SUCCESS = 100; + +function findMinimalCounterExample(x: A, + predicate: Predicate, + shrinker: Shrinker, + depth: number = 0): ShrinkResult { + let xs = shrinker(x); + let counterexample = x; + let shrinks = depth; + for (let y of xs) { + if (!predicate(y)) { + let shrink = findMinimalCounterExample(y, predicate, shrinker, depth + 1); + if (shrink.shrinks > depth) { + counterexample = shrink.counterexample; + shrinks = shrink.shrinks; + } + } + } + return { counterexample, shrinks }; +} + +export function property(rng: Prando, + size: number, + predicate: Predicate, + generator: Gen, + shrinker: Shrinker): TestResult { + let gen = generator(rng); + for (let i = 0; i < MAX_SUCCESS; i++) { + let x = gen(size); + if (!predicate(x)) { + let counterexample = findMinimalCounterExample(x, predicate, shrinker); + return { result: 'Falsified', counterexample }; + } + } + return { result: 'OK', counterexample: null }; +} diff --git a/pbt/ts/tsconfig.json b/pbt/ts/tsconfig.json index d1646f0..15fbe0f 100644 --- a/pbt/ts/tsconfig.json +++ b/pbt/ts/tsconfig.json @@ -7,5 +7,5 @@ "include": [ "src/**/*.ts", "test/**/*.ts" - ] +, "src/property.ts~", "src/index.ts~" ] } -- cgit v1.2.3