Documentation

Mathlib.Testing.SlimCheck.Testable

Testable Class #

Testable propositions have a procedure that can generate counter-examples together with a proof that they invalidate the proposition.

This is a port of the Haskell QuickCheck library.

Creating Customized Instances #

The type classes Testable, SampleableExt and Shrinkable are the means by which SlimCheck creates samples and tests them. For instance, the proposition ∀ i j : ℕ, i ≤ j has a Testable instance because is sampleable and i ≤ j is decidable. Once SlimCheck finds the Testable instance, it can start using the instance to repeatedly creating samples and checking whether they satisfy the property. Once it has found a counter-example it will then use a Shrinkable instance to reduce the example. This allows the user to create new instances and apply SlimCheck to new situations.

What do I do if I'm testing a property about my newly defined type? #

Let us consider a type made for a new formalization:

structure MyType where
  x : ℕ
  y : ℕ
  h : x ≤ y
  deriving Repr

How do we test a property about MyType? For instance, let us consider Testable.check <| ∀ a b : MyType, a.y ≤ b.x → a.x ≤ b.y. Writing this property as is will give us an error because we do not have an instance of Shrinkable MyType and SampleableExt MyType. We can define one as follows:

instance : Shrinkable MyType where
  shrink := fun ⟨x,y,h⟩ ↦
    let proxy := Shrinkable.shrink (x, y - x)
    proxy.map (fun ⟨⟨fst, snd⟩, ha⟩ ↦ ⟨⟨fst, fst + snd, sorry⟩, sorry⟩)

instance : SampleableExt MyType :=
  SampleableExt.mkSelfContained do
    let x ← SampleableExt.interpSample Nat
    let xyDiff ← SampleableExt.interpSample Nat
    pure <| ⟨x, x + xyDiff, sorry⟩

Again, we take advantage of the fact that other types have useful Shrinkable implementations, in this case Prod. Note that the second proof is heavily based on WellFoundedRelation since it's used for termination so the first step you want to take is almost always to simp_wf in order to get through the WellFoundedRelation.

Main definitions #

Tags #

random testing

References #

inductive SlimCheck.TestResult (p : Prop) :

Result of trying to disprove p The constructors are:

  • success : (Unit ⊕' p) → TestResult p succeed when we find another example satisfying p In success h, h is an optional proof of the proposition. Without the proof, all we know is that we found one example where p holds. With a proof, the one test was sufficient to prove that p holds and we do not need to keep finding examples.
  • gaveUp : ℕ → TestResult p give up when a well-formed example cannot be generated. gaveUp n tells us that n invalid examples were tried. Above 100, we give up on the proposition and report that we did not find a way to properly test it.
  • failure : ¬ p → (List String) → ℕ → TestResult p a counter-example to p; the strings specify values for the relevant variables. failure h vs n also carries a proof that p does not hold. This way, we can guarantee that there will be no false positive. The last component, n, is the number of times that the counter-example was shrunk.
Instances For
    Equations

    Configuration for testing a property.

    Instances For
      Equations
      • One or more equations did not get rendered due to their size.
      Equations
      • One or more equations did not get rendered due to their size.

      Allow elaboration of Configuration arguments to tactics.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For

        PrintableProp p allows one to print a proposition so that SlimCheck can indicate how values relate to each other. It's basically a poor man's delaborator.

        Instances
          @[instance 100]
          Equations
          • SlimCheck.instPrintableProp = { printProp := "⋯" }

          Testable p uses random examples to try to disprove p.

          Instances
            Equations
            Instances For
              Equations
              Instances For
                Equations
                • SlimCheck.TestResult.instToString = { toString := SlimCheck.TestResult.toString }
                def SlimCheck.TestResult.combine {p : Prop} {q : Prop} :
                Unit ⊕' (pq)Unit ⊕' pUnit ⊕' q

                Applicative combinator proof carrying test results.

                Equations
                Instances For
                  def SlimCheck.TestResult.imp {p : Prop} {q : Prop} (h : qp✝) (r : SlimCheck.TestResult p✝) (p : optParam (Unit ⊕' (p✝q)) (PSum.inl ())) :

                  If q → p, then ¬ p → ¬ q which means that testing p can allow us to find counter-examples to q.

                  Equations
                  Instances For

                    Test q by testing p and proving the equivalence between the two.

                    Equations
                    Instances For
                      def SlimCheck.TestResult.addInfo {p : Prop} {q : Prop} (x : String) (h : qp✝) (r : SlimCheck.TestResult p✝) (p : optParam (Unit ⊕' (p✝q)) (PSum.inl ())) :

                      When we assign a value to a universally quantified variable, we record that value using this function so that our counter-examples can be informative.

                      Equations
                      Instances For
                        def SlimCheck.TestResult.addVarInfo {p : Prop} {q : Prop} {γ : Type u_1} [Repr γ] (var : String) (x : γ) (h : qp✝) (r : SlimCheck.TestResult p✝) (p : optParam (Unit ⊕' (p✝q)) (PSum.inl ())) :

                        Add some formatting to the information recorded by addInfo.

                        Equations
                        Instances For
                          Equations
                          Instances For

                            A configuration with all the trace options enabled, useful for debugging.

                            Equations
                            • One or more equations did not get rendered due to their size.
                            Instances For

                              A dbgTrace with special formatting

                              Equations
                              Instances For
                                Equations
                                • One or more equations did not get rendered due to their size.
                                Equations
                                • One or more equations did not get rendered due to their size.
                                Equations
                                • One or more equations did not get rendered due to their size.
                                instance SlimCheck.Testable.decGuardTestable {p : Prop} {var : String} [SlimCheck.PrintableProp p] [Decidable p] {β : pProp} [(h : p) → SlimCheck.Testable (β h)] :
                                SlimCheck.Testable (SlimCheck.NamedBinder var (∀ (h : p), β h))
                                Equations
                                • One or more equations did not get rendered due to their size.
                                Equations
                                • One or more equations did not get rendered due to their size.
                                Equations

                                Format the counter-examples found in a test failure.

                                Equations
                                Instances For

                                  Increase the number of shrinking steps in a test result.

                                  Equations
                                  Instances For
                                    instance SlimCheck.Testable.instInhabitedOptionTOfPure {α : Type u} {m : Type u → Type u_1} [Pure m] :
                                    Equations
                                    • SlimCheck.Testable.instInhabitedOptionTOfPure = { default := pure none }

                                    Shrink a counter-example x by using Shrinkable.shrink x, picking the first candidate that falsifies a property and recursively shrinking that one. The process is guaranteed to terminate because shrink x produces a proof that all the values it produces are smaller (according to SizeOf) than x.

                                    Once a property fails to hold on an example, look for smaller counter-examples to show the user.

                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For
                                      instance SlimCheck.Testable.varTestable {var : String} {α : Sort u_1} [SlimCheck.SampleableExt α] {β : αProp} [(x : α) → SlimCheck.Testable (β x)] :
                                      SlimCheck.Testable (SlimCheck.NamedBinder var (∀ (x : α), β x))

                                      Test a universal property by creating a sample of the right type and instantiating the bound variable with it.

                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      instance SlimCheck.Testable.propVarTestable {var : String} {β : PropProp} [(b : Bool) → SlimCheck.Testable (β (b = true))] :

                                      Test a universal property about propositions

                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      @[instance 10000]
                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      @[instance 2000]
                                      instance SlimCheck.Testable.subtypeVarTestable {var : String} {α : Sort u_1} {p : αProp} {β : αProp} [(x : α) → SlimCheck.PrintableProp (p x)] [(x : α) → SlimCheck.Testable (β x)] [SlimCheck.SampleableExt (Subtype p)] {var' : String} :
                                      SlimCheck.Testable (SlimCheck.NamedBinder var (∀ (x : α), SlimCheck.NamedBinder var' (p xβ x)))
                                      Equations
                                      @[instance 100]
                                      Equations
                                      • One or more equations did not get rendered due to their size.
                                      instance SlimCheck.Eq.printableProp {α : Type u_1} [Repr α] {x : α} {y : α} :
                                      Equations
                                      instance SlimCheck.Ne.printableProp {α : Type u_1} [Repr α] {x : α} {y : α} :
                                      Equations
                                      instance SlimCheck.LE.printableProp {α : Type u_1} [Repr α] [LE α] {x : α} {y : α} :
                                      Equations
                                      instance SlimCheck.LT.printableProp {α : Type u_1} [Repr α] [LT α] {x : α} {y : α} :
                                      Equations
                                      Equations
                                      Equations
                                      Equations
                                      • SlimCheck.Bool.printableProp = { printProp := if b = true then "true" else "false" }
                                      Equations

                                      Execute cmd and repeat every time the result is gave_up (at most n times).

                                      Equations
                                      Instances For

                                        Try n times to find a counter-example for p.

                                        Equations
                                        Instances For
                                          def SlimCheck.Testable.runSuite (p : Prop) [SlimCheck.Testable p] (cfg : optParam SlimCheck.Configuration { numInst := 100, maxSize := 100, numRetries := 10, traceDiscarded := false, traceSuccesses := false, traceShrink := false, traceShrinkCandidates := false, randomSeed := none, quiet := false }) :

                                          Try to find a counter-example of p.

                                          Equations
                                          Instances For
                                            def SlimCheck.Testable.checkIO (p : Prop) [SlimCheck.Testable p] (cfg : optParam SlimCheck.Configuration { numInst := 100, maxSize := 100, numRetries := 10, traceDiscarded := false, traceSuccesses := false, traceShrink := false, traceShrinkCandidates := false, randomSeed := none, quiet := false }) :

                                            Run a test suite for p in BaseIO using the global RNG in stdGenRef.

                                            Equations
                                            • One or more equations did not get rendered due to their size.
                                            Instances For

                                              Traverse the syntax of a proposition to find universal quantifiers quantifiers and add NamedBinder annotations next to them.

                                              @[reducible, inline]

                                              DecorationsOf p is used as a hint to mk_decorations to specify that the goal should be satisfied with a proposition equivalent to p with added annotations.

                                              Equations
                                              Instances For

                                                In a goal of the shape DecorationsOf p, mk_decoration examines the syntax of p and adds NamedBinder around universal quantifications to improve error messages. This tool can be used in the declaration of a function as follows:

                                                def foo (p : Prop) (p' : Decorations.DecorationsOf p := by mk_decorations) [Testable p'] : ...
                                                

                                                p is the parameter given by the user, p' is a definitionally equivalent proposition where the quantifiers are annotated with NamedBinder.

                                                Equations
                                                Instances For
                                                  def SlimCheck.Testable.check (p : Prop) (cfg : optParam SlimCheck.Configuration { numInst := 100, maxSize := 100, numRetries := 10, traceDiscarded := false, traceSuccesses := false, traceShrink := false, traceShrinkCandidates := false, randomSeed := none, quiet := false }) (p' : autoParam (SlimCheck.Decorations.DecorationsOf p) _auto✝) [SlimCheck.Testable p'] :

                                                  Run a test suite for p and throw an exception if p does not hold.

                                                  Equations
                                                  • One or more equations did not get rendered due to their size.
                                                  Instances For