Recipe: Testing Pure Algorithms

Relevant source files

The following files were used as context for generating this wiki page:

• examples/001-simple/decompPrime/main.spec.ts
• examples/001-simple/indexOf/main.spec.ts
• examples/001-simple/fibonacci/main.spec.ts
• examples/README.md
• packages/vitest/test/vitest-fast-check.spec.ts
• CONTRIBUTING.md

Introduction

Property-based testing is a powerful technique for verifying the correctness of pure algorithms. Instead of writing individual tests for specific inputs, you define general properties that your algorithm must satisfy for all valid inputs. fast-check then automatically generates a large number of diverse inputs to challenge these properties, uncovering edge cases that might be missed by manual example-based testing.

This recipe demonstrates how to use fast-check to test pure functions, which are the ideal candidates for property-based testing due to their deterministic nature. The examples cover algorithms for simple data structures, recursive structures, and other miscellaneous functions, illustrating how to think about and define properties.

Sources: examples/README.md

The Property-Based Testing Flow

The core of testing with fast-check involves defining a property and asserting that it holds true. A property is a function that takes generated values as input and returns true if the condition is met, or false (or throws an error) if it's violated.

The general workflow is as follows:

1. Define Arbitraries: Select or create arbitraries (fc.*) to generate random inputs for your function.
2. Define a Predicate: Write a function (the predicate) that takes the generated inputs, calls your algorithm, and checks if a specific property holds true for the output.
3. Assert the Property: Use fc.assert and fc.property to run the test. fast-check will generate numerous inputs and call your predicate with them. If any input causes the predicate to fail, fast-check will try to "shrink" the input to the smallest possible failing case to simplify debugging.

This diagram illustrates the execution flow of a single property test.

Strategies for Finding Properties

A key skill in property-based testing is identifying the right properties for your algorithm. The following strategies, demonstrated in the project's examples, can help you define effective properties.

Sources: examples/README.md:42-61

Characteristics Derived from Inputs

The output of a function often has a direct, verifiable relationship with its inputs.

• indexOf: The result of text.indexOf(pattern) should be between -1 and text.length - 1. Another property is that text.substring(result) should start with pattern if the result is not -1.
• sort: For any array data, sorted(data) must contain the same elements as data, and its length must be the same.

Sources: examples/README.md:50-53, examples/001-simple/indexOf/main.spec.ts:11-20

Characteristics on Combination of Functions

This involves checking the relationship between different functions or different invocations of the same function.

• fibonacci: A classic property of the Fibonacci sequence is that for any n > 0, fibonacci(n) + fibonacci(n + 1) must equal fibonacci(n + 2).

  // examples/001-simple/fibonacci/main.spec.ts:10-14
  it('should have the property f(n) + f(n+1) = f(n+2)', () => {
    fc.assert(
      fc.property(fc.nat({ max: 90 }), (n) => {
        expect(fibonacci(n) + fibonacci(n + 1)).toBe(fibonacci(n + 2));
      }),
    );
  });
  

  Sources: examples/001-simple/fibonacci/main.spec.ts:10-14

• decompPrime: The product of the prime factors of a number n must equal n.

  // examples/001-simple/decompPrime/main.spec.ts:11-15
  it('should produce a list of factors that can be multiplied to get the original number', () => {
    fc.assert(
      fc.property(fc.nat({ max: 2000000 }), (n) => {
        expect(decompPrime(n).reduce((a, b) => a * b, 1)).toBe(n);
      }),
    );
  });
  

  Sources: examples/001-simple/decompPrime/main.spec.ts:11-15

Restricted Inputs with Known Characteristics

For some inputs, the output is already known or has a simple form.

• decompPrime: For any prime number p, its decomposition into prime factors should be an array containing only p.

Sources: examples/README.md:55-57

Generating Inputs with Arbitraries

Arbitraries are the generators for your test data. fast-check provides a rich set of built-in arbitraries for common data types.

The following table summarizes some arbitraries used in the examples for testing pure algorithms.

Arbitrary	Description	Example Usage	Source File
fc.nat(max)	Generates a non-negative integer up to max.	fc.nat({ max: 90 })	fibonacci/main.spec.ts:12
fc.string()	Generates a string.	fc.string()	indexOf/main.spec.ts:13
fc.tuple(...)	Generates a tuple from other arbitraries.	fc.tuple(fc.string(), fc.string())	indexOf/main.spec.ts:13

Sources: examples/001-simple/fibonacci/main.spec.ts:12, examples/001-simple/indexOf/main.spec.ts:13, examples/001-simple/decompPrime/main.spec.ts:13

Integration with Test Runners

While fc.assert(fc.property(...)) is the core structure, integrations with test runners like Vitest, Jest, or Mocha can provide a more concise syntax. The @fast-check/vitest package, for example, provides a test.prop function that simplifies this pattern.

The following diagram shows how test.prop from @fast-check/vitest wraps the standard fc.assert logic.

This code from the vitest-fast-check test suite shows how runner.prop (which can be test.prop or it.prop) is used.

// packages/vitest/test/vitest-fast-check.spec.ts:41-45
runner.prop([fc.string(), fc.string(), fc.string()])('property', (a, b, c) => {
  return `${a}${b}${c}`.includes(b);
});

This is equivalent to:

it('property', () => {
  fc.assert(
    fc.property(fc.string(), fc.string(), fc.string(), (a, b, c) => {
      return `${a}${b}${c}`.includes(b);
    })
  );
});

This integration makes property-based tests look and feel more like standard unit tests within your chosen framework.

Sources: packages/vitest/test/vitest-fast-check.spec.ts:41-45

Conclusion

Testing pure algorithms with fast-check encourages you to think about your code in terms of its fundamental properties and invariants. This approach provides a higher level of confidence than traditional example-based testing by automatically exploring a vast input space. By defining properties based on input-output relationships, functional composition, or known characteristics, you can build a robust and comprehensive test suite that effectively finds bugs and validates the correctness of your algorithms.

Sources: examples/README.md:4-7