Skip to content

Instantly share code, notes, and snippets.

@sogaiu

sogaiu/random-all-the-way-down-and-cscheck-notes.md

Last active August 13, 2025 12:12
Show Gist options
  • Save sogaiu/446a2b2e2e942480b37a25c6b067e9ed to your computer and use it in GitHub Desktop.
Save sogaiu/446a2b2e2e942480b37a25c6b067e9ed to your computer and use it in GitHub Desktop.
Download ZIP
random all the way down and cscheck notes
Raw
random-all-the-way-down-and-cscheck-notes.md

questions and notes

  • what's the basic idea in cscheck? answer from "random all the way down" article:

    The idea is simple: instead of coming up with a deliberate algorithm to make values smaller, we just - in technical terms - throw shit to the wall and see what sticks. That is, we're already counting on random generation to find bugs, let's also randomly try to find smaller values that still make our test fail.

    Unlike the shrinking strategies we've seen so far, which produce a limited number of smaller values to try, this new approach can keep trying forever. If the random generator is "random enough", a good shrink should show up at some point.

    In practice, that can take too long, especially if the test itself is slow. However, we can avoid running a test, or even generating an actual value, by calculating the size of the value that we're about to generate beforehand. We'll keep the size of the smallest value that fails the test so far, and then randomly generate another and estimate its size while we generate. If that size is greater than that of the current smallest value, we're not interested in running the test with it, or creating the rest of the value. Instead we'll make the generator short-circuit - basically abort and move on to the next value. This avoids a lot of useless work.

  • what is Size? answer from the horse's mouth:

    CsCheck creates a value and Size tuple. The Size is a comparison proxy for the value (it's an int64 tree). This also composes.

  • what does min?.Below(size) mean?
  • Size.Add seems to be used to "incorporate" a Size value after something has been generated...when exactly should it be used?
  • Size.Append seems to be used more near where something is returned...when exactly should it be used?
  • is there some meaningful connection between Below and Append (besides them both being defined in Size)?
  • the out Size size part of var v1 = gen1.Generate(pcg, min, out size); appears to be how the Size of the generated value gets communicated (as compared to the generated value itself being returned)
  • if (Size.IsLessThan(min, size)) return default!; seems to be an example of "short-circuiting" as described in the "random all the way down" article
  • in the article, min_size signals whether execution is in the random generation phase or the shrinking phase (perhaps a similar thing is true in cscheck?):

    If min_size is None, we're in the random generation phase of the test run - meaning we haven't found a failing test yet and so the generator should never short-circuit. If min_size is a Size value, we are shrinking, and min_size is the current smallest value for which the test fails. If a generator exceeds that size, there's no point in going on, and the generator should throw SizeExceeded to short-circuit.

public sealed class Size
{
  public ulong I;
  public Size? Next;

  public Size(ulong i) => I = i;

  public Size(ulong i, Size next)
  {
    I = i;
    Next = next;
  }

  public void Add(Size a)
  {
    var nI = I + a.I;
    I = nI >= I && nI >= a.I ? nI : ulong.MaxValue;
    if (a.Next is not null)
    {
      if (Next is null) Next = a.Next;
      else Next.Add(a.Next);
    }
  }
  public void Append(Size s)
  {
    var final = this;
    while (final.Next is not null) final = final.Next;
    final.Next = s;
  }

  public Size? Below(Size? s)
  {
    var r = this;
    while (s is not null && r is not null)
    {
      if (s.I != r.I) return null;
        s = s.Next;
        r = r.Next;
    }
    return r;
  }

  public static bool IsLessThan(Size? s1, Size? s2)
  {
    while (true)
    {
      if (s1 is null || s2 is null || s1.I > s2.I) return false;
      if (s1.I < s2.I) return true;
      s1 = s1.Next;
      s2 = s2.Next;
    }
  }
}
[Fact]
public void Single_Unit_Range()
{
  Gen.Single.Unit.Sample(f => Assert.InRange(f, 0f, 0.9999999f));
}

  • flow: Sample -> Generate -> Execute

  • below is code using Sample with Action (assert), instead of Sample with Func (predicate), but the basic idea seems similar. the example entry point above may be using the Func stuff (and not the Action stuff). to see the Func stuff look in Check.cs for SampleFuncWorker<T> and Sample<T> with Func<T, bool> predicate -- though there may be other applicable bits too. there is way too much boilerplaty code in CsCheck...may be that's unavoidable in c#

  /// <summary>Sample the gen calling the assert each time across multiple threads. Shrink any exceptions if necessary.</summary>
  /// <param name="gen">The sample input data generator.</param>
  /// <param name="assert">The code to call with the input data raising an exception if it fails.</param>
  /// <param name="writeLine">WriteLine function to use for the summary total iterations output.</param>
  /// <param name="seed">The initial seed to use for the first iteration.</param>
  /// <param name="iter">The number of iterations to run in the sample (default 100).</param>
  /// <param name="time">The number of seconds to run the sample.</param>
  /// <param name="threads">The number of threads to run the sample on (default number logical CPUs).</param>
  /// <param name="print">A function to convert the input data to a string for error reporting (default Check.Print).</param>
  /// <param name="logger">Log metrics regarding generated inputs and results.</param>
  public static void Sample<T>(this Gen<T> gen, Action<T> assert, Action<string>? writeLine = null,
    string? seed = null, long iter = -1, int time = -1, int threads = -1, Func<T, string>? print = null,
    ILogger? logger = null)
  {
    seed ??= Seed;
    if (iter == -1) iter = Iter;
    if (time == -1) time = Time;
    if (threads == -1) threads = Threads;
    bool isIter = time < 0;
    var cde = new CountdownEvent(threads);
    if (logger is not null)
      assert = logger.WrapAssert(assert);

    var worker = new SampleActionWorker<T>(
      gen,
      assert,
      cde,
      seed,
      isIter ? seed is null ? iter : iter - 1 : Stopwatch.GetTimestamp() + time * Stopwatch.Frequency,
      isIter);

    if (seed is not null)
    {
      var pcg = PCG.Parse(seed);
      ulong state = pcg.State;
      Size? size = null;
      T t = default!;
      try
      {
        assert(t = gen.Generate(pcg, null, out size));
      }
      catch (Exception e)
      {
        worker.MinSize = size;
        worker.MinPCG = pcg;
        worker.MinState = state;
        worker.MinT = t;
        worker.MinException = e;
        worker.Shrinks++;
      }
    }

    while (--threads > 0)
      ThreadPool.UnsafeQueueUserWorkItem(worker, false);
    worker.Execute();
    cde.Wait();
    cde.Dispose();

    if (worker.MinPCG is not null)
      throw new CsCheckException(worker.ExceptionMessage(print ?? Print), worker.MinException);
    if (writeLine is not null) writeLine($"Passed {worker.Total:#,0} iterations.");
  }
  // ...
  sealed class GenSelectMany<T1, T2, T3, R>(Gen<T1> gen1, Gen<T2> gen2, Gen<T3> gen3, Func<T1, T2, T3, IGen<R>> selector) : Gen<R>
  {
    public override R Generate(PCG pcg, Size? min, out Size size)
    {
      var v1 = gen1.Generate(pcg, min, out size);
      if (Size.IsLessThan(min, size)) return default!;
      var v2 = gen2.Generate(pcg, min, out var s);
      size.Add(s);
      if (Size.IsLessThan(min, size)) return default!;
      var v3 = gen3.Generate(pcg, min, out s);
      size.Add(s);
      if (Size.IsLessThan(min, size)) return default!;
      var vR = selector(v1, v2, v3).Generate(pcg, min?.Below(size), out s);
      size.Append(s);
      return vR;
    }
  }
  // ...
  sealed class GenSelectManyResult<T1, T2, T3, R>(Gen<T1> gen1, Gen<T2> gen2, Func<T1, T2, IGen<T3>> genSelector, Func<T1, T2, T3, R> resultSelector) : Gen<R>
  {
    public override R Generate(PCG pcg, Size? min, out Size size)
    {
      var v1 = gen1.Generate(pcg, min, out size);
      if (Size.IsLessThan(min, size)) return default!;
      var v2 = gen2.Generate(pcg, min, out var s);
      size.Add(s);
      if (Size.IsLessThan(min, size)) return default!;
      var v3 = genSelector(v1, v2).Generate(pcg, min?.Below(size), out s);
      size.Append(s);
      if (Size.IsLessThan(min, size)) return default!;
      return resultSelector(v1, v2, v3);
    }
  }
/// <summary>Main random testing Check functions.</summary>
public static partial class Check
{
  /// <summary>The number of iterations to run in the sample (default 100).</summary>
  public static long Iter = ParseEnvironmentVariableToLong("CsCheck_Iter", 100);
  /// <summary>The number of seconds to run the sample.</summary>
  public static int Time = ParseEnvironmentVariableToInt("CsCheck_Time" , -1);
  /// <summary>The number of times to retry the seed to reproduce a SampleParallel fail (default 100).</summary>
  public static int Replay = ParseEnvironmentVariableToInt("CsCheck_Replay", 100);
  /// <summary>The number of threads to run the sample on (default number logical CPUs).</summary>
  public static int Threads = ParseEnvironmentVariableToInt("CsCheck_Threads", Environment.ProcessorCount);
  /// <summary>The initial seed to use for the first iteration.</summary>
  public static string? Seed = ParseEnvironmentVariableToSeed("CsCheck_Seed");
  /// <summary>The sigma to use for Faster (default 6).</summary>
  public static double Sigma = ParseEnvironmentVariableToDouble("CsCheck_Sigma", 6.0);
  /// <summary>The timeout in seconds to use for Faster (default 60 seconds).</summary>
  public static int Timeout = ParseEnvironmentVariableToInt("CsCheck_Timeout", 60);
  /// <summary>The number of ulps to approximate to when printing doubles and floats.</summary>
  public static int Ulps = ParseEnvironmentVariableToInt("CsCheck_Ulps", 4);
  /// <summary>The number of Where Gne iterations before throwing an exception.</summary>
  public static int WhereLimit = ParseEnvironmentVariableToInt("CsCheck_WhereLimit", 100);
  internal static bool IsDebug = Assembly.GetCallingAssembly().GetCustomAttribute<DebuggableAttribute>()?.IsJITTrackingEnabled ?? false;

  sealed class SampleActionWorker<T>(Gen<T> gen, Action<T> assert, CountdownEvent cde, string? seed, long target, bool isIter) : IThreadPoolWorkItem
  {
    public PCG? MinPCG;
    public ulong MinState;
    public Size? MinSize;
    public T MinT = default!;
    public Exception? MinException;
    public int Shrinks = -1;
    public long Total = seed is null ? 0 : 1;
    public long Skipped;

    public void Execute()
    {
      var pcg = PCG.ThreadPCG;
      Size? size = null;
      T t = default!;
      long skippedLocal = 0, totalLocal = 0;
      ulong state = 0;
      while (true)
      {
        try
        {
          while (true)
          {
            if ((isIter ? Interlocked.Decrement(ref target) : target - Stopwatch.GetTimestamp()) < 0)
            {
              Interlocked.Add(ref Skipped, skippedLocal);
              Interlocked.Add(ref Total, totalLocal);
              cde.Signal();
              return;
            }
            totalLocal++;
            state = pcg.State;
            t = gen.Generate(pcg, MinSize, out size);
            if (MinSize is null || Size.IsLessThan(size, MinSize))
            {
              assert(t);
            }
            else
              skippedLocal++;
          }
        }
        catch (Exception e)
        {
          lock (cde)
          {
            if (MinSize is null || Size.IsLessThan(size, MinSize))
            {
              MinSize = size;
              MinPCG = pcg;
              MinState = state;
              MinT = t;
              MinException = e;
              Shrinks++;
            }
          }
        }
      }
    }
    public string ExceptionMessage(Func<T, string> print)
    {
      return SampleErrorMessage(MinPCG!.ToString(MinState), print(MinT!), Shrinks, Skipped, Total);
    }
  }

references

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment