stream_data.ex

defmodule StreamData do
  @moduledoc """
  Functions to create and combine generators.

  A generator is a `StreamData` struct. Generators can be created through the
  functions exposed in this module, like `constant/1`, and by combining other
  generators through functions like `bind/2`.

  Generators are used for mainly two purposes: to generate test data, and as the
  basis of property testing. When a generator is called internally, it will
  generate a value that is not a directly usable value. Instead, it's a
  "wrapper" around a normal value that is optimized for property testing and,
  more specifically, for *shrinking* (see the section about shrinking below).

  Note that values generated by generators are not unique.

  ## Generation size

  Generators have access to a generation parameter called the **generation
  size**, which is a non-negative integer. This parameter is meant to bind the
  data generated by each generator in a way that is completely up to the
  generator. For example, a generator that generates integer can use the `size`
  parameter to generate integers inside the `-size..size` range. In a similar
  way, a generator that generates lists could use this parameter to generate a
  list with `0` to `size` elements. The generation size parameter is "global",
  that is, complex generators that wrap other generators usually pass it down to
  the inner generators when generating data.

  When creating generators, they can access the generation size using the
  `sized/1` function. Generators can be resized to a fixed generation size using
  `resize/2`.

  ## Enumeration

  Generators implement the `Enumerable` protocol. The implementation yields
  simple values (not shrinkable wrappers as discussed above) when enumerating a
  generator. The enumeration starts with a small generation size, which
  increases when the enumeration continues (up to a fixed maximum size).

  For example, to get an infinite stream of integers that starts with small
  integers and progressively grows the boundaries, you can just use `integer/0`:

      Enum.take(StreamData.integer(), 10)
      #=> [-1, 0, -3, 4, -4, 5, -1, -3, 5, 8]

  Since generators are proper streams, functions from the `Stream` module can be
  used to stream values out of them. For example, to build an infinite stream of
  positive even integers, you can do:

      StreamData.integer()
      |> Stream.filter(&(&1 > 0))
      |> Stream.map(&(&1 * 2))
      |> Enum.take(10)
      #=> [4, 6, 4, 10, 14, 16, 4, 16, 36, 16]

  As we mentioned above, you can see that in general a generator does not
  generate unique values.

  Note that all generators are **infinite** streams that never terminate.

  When using generators for test data, usually using them as enumerables is the
  easiest choice.

  ## Shrinking

  As we mentioned above, the wrapper values generated by generators internally
  are optimized for **shrinking**. These wrapper values contain a generated
  value (the one used when enumerating a generator) alongside a way to shrink
  such value. For example, a value generated by the `list_of/1` generator will
  contain the actual list to use alongside a way to shrink that list, which in
  this specific case means taking elements out of that list until it comes to
  the empty list (which is the "smallest" shrinkable value for lists). Each
  generator shrinks generated values with its own logic, which is documented in
  the generator's documentation.

  Shrinking is used for property testing, where it's important to find the
  minimal value for which a property fails (since generated values are often
  bigger and full of garbage). See `PropertyTest` for more information.

  Note that the generation size is not related in any way with shrinking: while
  intuitively one may think that shrinking just means decreasing the generation
  size, in reality the generation size is related to how generators generate
  values, while shrinking is bound to each generated value and is a way to
  shrink that particular value.

  ## Special generators

  Some Elixir types are implicitly converted to `StreamData` generators when
  used in property testing or composed. These types are:

    * atoms - they generated themselves. For example, `:foo` is equivalent to
      `StreamData.constant(:foo)`.

    * tuples of generators - they generated tuples where each value is a value
      generated by the corresponding generator, exactly like described in
      `tuple/1`. For example, `{StreamData.integer(), StreamData.boolean()}`
      generates entries like `{10, false}`.

  Note that *these terms are only implicitly converted to generators when
  composing them*. This means that these terms are not full-fledged generators:
  for example, atoms cannot be enumerated directly as they don't implement the
  `Enumerable` protocol. However, `StreamData.map(:foo, &Atom.to_string/1)` can
  be enumerated since `:foo` is implicitly converted to a generator when passed
  to a `StreamData` function.
  """

  alias StreamData.LazyTree

  @typep seed :: :rand.state
  @typep size :: non_neg_integer
  @typep generator_fun(a) :: (seed, size -> LazyTree.t(a))

  @typedoc """
  An opaque type that represents a `StreamData` generator that generates values
  of type `a`.

  Note that while this type is opaque, a generator is still guaranteed to be a
  `StreamData` struct (in case you want to pattern match on it).
  """
  @opaque t(a) :: %__MODULE__{
    generator: generator_fun(a),
  }

  @rand_algorithm :exs1024

  defstruct [:generator]

  defmodule FilterTooNarrowError do
    defexception [:max_consecutive_failures]

    def message(%{max_consecutive_failures: max_consecutive_failures}) do
      "too many (#{max_consecutive_failures}) consecutive elements were filtered out. " <>
      "Make sure to avoid filters that are too strict and filter out too many elements " <>
      "and make sure a small generation size doesn't affect the filter too heavily (such as " <>
      "when empty lists are filtered out but small generation size forces generation of many " <>
      "empty lists)"
    end
  end

  defmodule TooManyDuplicatesError do
    defexception [:max_tries, :remaining_to_generate, :generated]

    def message(%{max_tries: max_tries, remaining_to_generate: remaining, generated: generated}) do
      "too many (#{max_tries}) non-unique elements were generated consecutively. " <>
      "Make sure to avoid generating from a small space of data (such as only a " <>
      "handful of terms) and make sure a small generation size doesn't affect " <>
      "uniqueness too heavily. There were still #{remaining} elements left to " <>
      "generate, while the generated elements were:\n\n#{inspect(generated)}"
    end
  end

  ### Minimal interface

  ## Helpers

  defp new(generator) when is_function(generator, 2) do
    %__MODULE__{generator: generator}
  end

  # We support multiple types of generators through call/3: this is basically a
  # poor implementation of a protocol (which we don't want to add just for
  # this).

  defp call(%__MODULE__{generator: generator}, seed, size) do
    %LazyTree{} = generator.(seed, size)
  end

  defp call(atom, _seed, _size) when is_atom(atom) do
    LazyTree.constant(atom)
  end

  defp call(tuple, seed, size) when is_tuple(tuple) do
    case tuple_size(tuple) do
      0 ->
        LazyTree.constant({})
      size ->
        {trees, _seed} =
          Enum.map_reduce(0..size - 1, seed, fn index, acc ->
            {seed1, seed2} = split_seed(acc)
            data = elem(tuple, index)
            {call(data, seed1, size), seed2}
          end)
        trees
        |> LazyTree.zip()
        |> LazyTree.map(&List.to_tuple/1)
    end
  end

  ## Generators

  @doc """
  A generator that always generates the given term.

  ## Examples

      iex> Enum.take(StreamData.constant(:some_term), 3)
      [:some_term, :some_term, :some_term]

  ## Shrinking

  This generator doesn't shrink.
  """
  @spec constant(a) :: t(a) when a: var
  def constant(term) do
    new(fn _seed, _size -> LazyTree.constant(term) end)
  end

  ## Combinators

  @doc """
  Maps the given function `fun` over the given generator `data`.

  Returns a new generator that returns elements from `data` after applying `fun`
  to them.

  ## Examples

      iex> data = StreamData.map(StreamData.integer(), &Integer.to_string/1)
      iex> Enum.take(data, 3)
      ["1", "0", "3"]

  ## Shrinking

  This generator shrinks exactly like `data`, but with `fun` mapped over the
  shrunk data.
  """
  @spec map(t(a), (a -> b)) :: t(b) when a: term, b: term
  def map(data, fun) when is_function(fun, 1) do
    new(fn seed, size ->
      data
      |> call(seed, size)
      |> LazyTree.map(fun)
    end)
  end

  @doc """
  Binds each element generated by `data` and to a new generator returned by
  applying `fun` or filters the generated element.

  Works similarly to `bind/2` but allows to filter out unwanted values. It takes
  a generator `data` and invokes `fun` with each element generated by `data`.
  `fun` must return one of:

    * `{:cont, generator}` - `generator` is then used to generate the next
      element

    * `:skip` - the value generated by `data` is filtered out and a new element
      is generated

  Since this function acts as a filter as well, it behaves similarly to
  `filter/3`: when more than `max_consecutive_failures` elements are filtered
  out (that is, `fun` returns `:skip`), a `StreamData.FilterTooNarrowError` is
  raised.

  ## Examples

  Say we wanted to create a generator that generates two-element tuples where
  the first element is a list of integers with an even number of members and the
  second element is a member of that list. We can do that by generating a list
  and, if it has even length, taking an element out of it, otherwise filtering
  it out.

      require Integer

      list_data = StreamData.nonempty(StreamData.list_of(StreamData.integer()))

      data =
        StreamData.bind_filter(list_data, fn
          list when Integer.is_even(length(list)) ->
            inner_data = StreamData.bind(StreamData.member_of(list), fn member ->
              StreamData.constant({list, member})
            end)
            {:cont, inner_data}
          _odd_list ->
            :skip
        end)

      Enum.at(data, 0)
      #=> {[-6, -7, -4, 5, -9, 8, 7, -9], 5}

  ## Shrinking

  This generator shrinks like `bind/2` but values that are skipped are not used
  for shrinking (similarly to how `filter/3` works).
  """
  @spec bind_filter(t(a), (a -> {:cont, t(b)} | :skip), non_neg_integer) :: t(b) when a: term, b: term
  def bind_filter(data, fun, max_consecutive_failures \\ 10)
      when is_function(fun, 1) and is_integer(max_consecutive_failures) and max_consecutive_failures >= 0 do
    new(fn seed, size ->
      case bind_filter(seed, size, data, fun, max_consecutive_failures) do
        {:ok, lazy_tree} ->
          lazy_tree
        :too_many_failures ->
          raise FilterTooNarrowError, max_consecutive_failures: max_consecutive_failures
      end
    end)
  end

  defp bind_filter(_seed, _size, _data, _mapper, _tries_left = 0) do
    :too_many_failures
  end

  defp bind_filter(seed, size, data, mapper, tries_left) do
    {seed1, seed2} = split_seed(seed)
    lazy_tree = call(data, seed1, size)

    case LazyTree.filter_map(lazy_tree, mapper) do
      {:ok, filter_mapped_tree} ->
        tree =
          filter_mapped_tree
          |> LazyTree.map(&call(&1, seed2, size))
          |> LazyTree.flatten()
        {:ok, tree}
      :error ->
        bind_filter(seed2, size, data, mapper, tries_left - 1)
    end
  end

  @doc """
  Binds each element generated by `data` to a new generator returned by applying `fun`.

  This function is the basic mechanism for composing generators. It takes a
  generator `data` and invokes `fun` with each element in `data`. `fun` must
  return a new *generator* that is effectively used to generate items from
  now on.

  ## Examples

  Say we wanted to create a generator that returns two-element tuples where the
  first element is a list, and the second element is a random element from that
  list. To do that, we can first generate a list and then bind a function to
  that list; this function will return the list and a random element from it.

      StreamData.bind(StreamData.list_of(StreamData.integer()), fn list ->
        StreamData.bind(StreamData.member_of(list), fn elem ->
          StreamData.constant({list, elem})
        end)
      end)

  ## Shrinking

  The generator returned by `bind/2` shrinks by first shrinking the value
  generated by the inner generator and then by shrinking the outer generator
  given as `data`. When `data` shrinks, `fun` is once more applied on the
  shrunk value value and returns a whole new generator, which will most likely
  emit new items.
  """
  @spec bind(t(a), (a -> t(b))) :: t(b) when a: term, b: term
  def bind(data, fun) when is_function(fun, 1) do
    bind_filter(data, fn generated_term -> {:cont, fun.(generated_term)} end)
  end

  @doc """
  Filters the given generator `data` according to the given `predicate` function.

  Only elements generated by `data` that pass the filter are kept in the
  resulting generator.

  If the filter is too strict, it can happen that too few values generated by
  `data` satisfy it. In case more than `max_consecutive_failures` consecutive
  values don't satisfy the filter, a `StreamData.FilterTooNarrowError` will be
  raised. Try to make sure that your filter takes out only a small subset of the
  elements generated by `data`. When possible, a good way to go around the
  limitations of `filter/3` is to instead transform the generated values in the
  shape you want them instead of filtering out the ones you don't want.

  For example, a generator of odd numbers could be implemented as:

      require Integer
      odd_ints = StreamData.filter(StreamData.integer(), &Integer.is_odd/1)
      Enum.take(odd_ints, 3)
      #=> [1, 1, 3]

  However, it will do more work and take more time to generate odd integers
  because it will have to filter out all the even ones that it generates. In
  this case, a better approach would be to generate integers and make sure they
  are odd:

      odd_ints = StreamData.map(StreamData.integer(), &(&1 * 2 + 1))
      Enum.take(odd_ints, 3)
      #=> [1, 1, 3]

  ## Shrinking

  All the values that each generated value shrinks to satisfy `predicate` as
  well.
  """
  @spec filter(t(a), (a -> as_boolean(term)), non_neg_integer) :: t(a) when a: term
  def filter(data, predicate, max_consecutive_failures \\ 10)
      when is_function(predicate, 1) and is_integer(max_consecutive_failures) and max_consecutive_failures >= 0 do
    bind_filter(data, fn term ->
      if predicate.(term) do
        {:cont, constant(term)}
      else
        :skip
      end
    end, max_consecutive_failures)
  end

  ### Rich API

  @doc """
  Generates an integer in the given `range`.

  The generation size is ignored since the integer always lies inside `range`.

  ## Examples

      Enum.take(StreamData.integer(4..8), 3)
      #=> [6, 7, 7]

  ## Shrinking

  Shrinks towards with the smallest absolute value that still lie in `range`.
  """
  @spec integer(Range.t) :: t(integer)
  def integer(_lower.._upper = range) do
    new(fn seed, _size ->
      range
      |> uniform_in_range(seed)
      |> integer_lazy_tree()
      |> LazyTree.filter(&(&1 in range))
    end)
  end

  defp integer_lazy_tree(int) do
    children =
      int
      |> Stream.iterate(&div(&1, 2))
      |> Stream.take_while(&(&1 != 0))
      |> Stream.map(&(int - &1))
      |> Stream.map(&integer_lazy_tree/1)

    LazyTree.new(int, children)
  end

  ## Generator modifiers

  @doc """
  Resize the given generated `data` to have fixed generation size `new_size`.

  The new generator will ignore the generation size and always use `new_size`.

  See the "Generation size" section in the documentation for `StreamData` for
  more information about the generation size.

  ## Examples

      data = StreamData.resize(StreamData.integer(), 10)
      Enum.take(data, 3)
      #=> [4, -5, -9]

  """
  @spec resize(t(a), size) :: t(a) when a: term
  def resize(data, new_size) when is_integer(new_size) and new_size >= 0 do
    new(fn seed, _size ->
      call(data, seed, new_size)
    end)
  end

  @doc """
  Returns the generator returned by calling `fun` with the generation size.

  `fun` takes the generation size and has to return a generator, that can use
  that size to its advantage.

  See the "Generation size" section in the documentation for `StreamData` for
  more information about the generation size.

  ## Examples

  Let's build a generator that generates integers in double the range `integer/0`
  does:

      data = StreamData.sized(fn size ->
        StreamData.resize(StreamData.integer(), size * 2)
      end)

      Enum.take(data, 3)
      #=> [0, -1, 5]

  """
  @spec sized((size -> t(a))) :: t(a) when a: term
  def sized(fun) when is_function(fun, 1) do
    new(fn seed, size ->
      new_data = fun.(size)
      call(new_data, seed, size)
    end)
  end

  @doc """
  Scales the generation size of the given generator `data` according to
  `size_changer`.

  When generating data from `data`, the generation size will be the result of
  calling `size_changer` with the generation size as its argument. This is
  useful, for example, when a generator needs to grow faster or slower than
  the default.

  See the "Generation size" section in the documentation for `StreamData` for
  more information about the generation size.

  ## Examples

  Let's create a generator that generates much smaller integers than `integer/0`
  when size grows. We can do this by scaling the generation size to the
  logarithm of the generation size.

      data = StreamData.scale(StreamData.integer(), fn size ->
        trunc(:math.log(size))
      end)

      Enum.take(data, 3)
      #=> [0, 0, -1]

  Another interesting example is creating a generator with a fixed maximum
  generation size. For example, say we want to generate binaries but we never
  want them to be larger than 64 bytes:

      small_binaries = StreamData.scale(StreamData.binary(), fn size ->
        min(size, 64)
      end)

  """
  @spec scale(t(a), (size -> size)) :: t(a) when a: term
  def scale(data, size_changer) when is_function(size_changer, 1) do
    sized(fn size ->
      resize(data, size_changer.(size))
    end)
  end

  @doc """
  Makes the values generated by `data` not shrink.

  ## Examples

  Let's build a generator of bytes (integers in the `0..255`) range. We can
  build this on top of `integer/1`, but for our purposes, it doesn't make sense for
  a byte to shrink towards `0`:

      byte = StreamData.unshrinkable(StreamData.integer(0..255))
      Enum.take(byte, 3)
      #=> [190, 181, 178]

  ## Shrinking

  The generator returned by `unshrinkable/1` generates the same values as `data`,
  but such values will not shrink.
  """
  @spec unshrinkable(t(a)) :: t(a) when a: term
  def unshrinkable(data) do
    new(fn seed, size ->
      %LazyTree{root: root} = call(data, seed, size)
      LazyTree.constant(root)
    end)
  end

  @doc """
  Generates values from different generators with specified probability.

  `frequencies` is a list of `{frequency, data}` where `frequency` is an integer
  and `data` is a generator. The resulting generator will generate data from one
  of the generators in `frequency`, with probability `frequency / vsum_of_frequencies`.

  ## Examples

  Let's build a generator that returns a binary around 25% of times and a
  integer around 75% of times. We'll use `integer/0` first so that generated values
  will shrink towards integers.

      ints_and_some_bins = StreamData.frequency([
        {3, StreamData.integer()},
        {1, StreamData.binary()},
      ])
      Enum.take(ints_and_some_bins, 3)
      #=> ["", -2, -1]

  ## Shrinking

  Each generated value is shrunk, and then this generator shrinks towards
  values generated by generators earlier in the list of `frequencies`.
  """
  # Right now, it shrinks by first shrinking the generated value, and then
  # shrinking towards earlier generators in "frequencies". Clojure shrinks
  # towards earlier generators *first*, and then shrinks the generated value.
  # An implementation that does this can be:
  #
  #     new(fn seed, size ->
  #       {seed1, seed2} = split_seed(seed)
  #       frequency = uniform_in_range(0..sum - 1, seed1)
  #       index = pick_index(Enum.map(frequencies, &elem(&1, 0)), frequency)
  #       {_frequency, data} = Enum.fetch!(frequencies, index)
  #
  #       tree = call(data, seed2, size)
  #
  #       earlier_children =
  #         frequencies
  #         |> Stream.take(index)
  #         |> Stream.map(&call(elem(&1, 1), seed2, size))
  #       LazyTree.new(tree.root, Stream.concat(earlier_children, tree.children))
  #     end)
  #
  @spec frequency([{pos_integer, t(a)}]) :: t(a) when a: term
  def frequency(frequencies) when is_list(frequencies) do
    sum = Enum.reduce(frequencies, 0, fn {frequency, _data}, acc -> acc + frequency end)
    bind(integer(0..sum - 1), &pick_frequency(frequencies, &1))
  end

  defp pick_frequency([{frequency, data} | rest], int) do
    if int < frequency do
      data
    else
      pick_frequency(rest, int - frequency)
    end
  end

  @doc """
  Generates values out of one of the given `datas`.

  `datas` must be a list of generators. The values generated by this generator
  are values generated by generators in `datas`, chosen each time at random.

  ## Examples

      data = StreamData.one_of([StreamData.integer(), StreamData.binary()])
      Enum.take(data, 3)
      #=> [-1, <<28>>, ""]

  ## Shrinking

  The generated value will be shrunk first according to the generator that
  generated it, and then this generator will shrink towards earlier generators
  in `datas`.
  """
  @spec one_of([t(a)]) :: t(a) when a: term
  def one_of([_ | _] = datas) do
    bind(integer(0..length(datas) - 1), fn index ->
      Enum.fetch!(datas, index)
    end)
  end

  @doc """
  Generates elements taken randomly out of `enum`.

  `enum` must be a non-empty and **finite** enumerable. If given an empty
  enumerable, this function raises an error. If given an infinite enumerable,
  this function will not terminate.

  ## Examples

      Enum.take(StreamData.member_of([:ok, 4, "hello"]), 3)
      #=> [4, 4, "hello"]

  ## Shrinking

  This generator shrinks towards elements that appear earlier in `enum`.
  """
  @spec member_of(Enumerable.t) :: t(term)
  def member_of(enum) do
    enum_length = Enum.count(enum)

    if enum_length == 0 do
      raise "cannot generate elements from an empty enumerable"
    end

    bind(integer(0..enum_length - 1), fn index ->
      constant(Enum.fetch!(enum, index))
    end)
  end

  ## Compound data types

  @doc """
  Generates lists where each values is generated by the given `data`.

  Each generated list can contain duplicate elements. The length of the
  generated list is bound by the generation size. If the generation size is `0`,
  the empty list will always be generated. Note that the accepted options
  provide finer control over the size of the generated list. See the "Options"
  section below.

  ## Options

    * `:length` - (integer or range) if an integer, the exact length the
      generated lists should be; if a range, the range in which the length of
      the generated lists should be. If provided, `:min_length` and
      `:max_length` are ignored.

    * `:min_length` - (integer) the minimum length of the generated lists.

    * `:max_length` - (integer) the maximum length of the generated lists.

  ## Examples

      Enum.take(StreamData.list_of(StreamData.binary()), 3)
      #=> [[""], [], ["", "w"]

      Enum.take(StreamData.list_of(StreamData.integer(), length: 3), 3)
      #=> [[0, 0, -1], [2, -1, 1], [0, 3, -3]]

      Enum.take(StreamData.list_of(StreamData.integer(), max_length: 1), 3)
      #=> [[1], [], []]

  ## Shrinking

  This generator shrinks by taking elements out of the generated list and also
  by shrinking the elements of the generated list. Shrinking still respects any
  possible length-related option: for example, if `:min_length` is provided, all
  shrinked list will have more than `:min_length` elements.
  """
  # We could have an implementation that relies on fixed_list/1 and List.duplicate/2,
  # it would look like this:
  #
  #     new(fn seed, size ->
  #       {seed1, seed2} = split_seed(seed)
  #       length = uniform_in_range(0..size, seed1)
  #       data
  #       |> List.duplicate(length)
  #       |> fixed_list()
  #       |> call(seed2, size)
  #       |> LazyTree.map(&list_lazy_tree/1)
  #       |> LazyTree.flatten()
  #     end)
  #
  @spec list_of(t(a), keyword) :: t([a]) when a: term
  def list_of(data, options \\ []) do
    list_length_range_fun = list_length_range_fun(options)

    new(fn seed, size ->
      {seed1, seed2} = split_seed(seed)
      min_length.._ = length_range = list_length_range_fun.(size)
      length = uniform_in_range(length_range, seed1)

      data
      |> call_n_times(seed2, size, length, [])
      |> LazyTree.zip()
      |> LazyTree.map(&list_lazy_tree(&1, min_length))
      |> LazyTree.flatten()
    end)
  end

  defp list_length_range_fun(options) do
    {min, max} =
      case Keyword.fetch(options, :length) do
        {:ok, length} when is_integer(length) and length >= 0 ->
          {length, length}
        {:ok, min..max} when min >= 0 and max >= 0 ->
          {min(min, max), max(min, max)}
        {:ok, other} ->
          raise ArgumentError, ":length must be a positive integer or a range " <>
                               "of positive integers, got: #{inspect(other)}"
        :error ->
          min_length = Keyword.get(options, :min_length, 0)
          max_length = Keyword.get(options, :max_length, :infinity)
          unless is_integer(min_length) and min_length >= 0 do
            raise ArgumentError, ":min_length must be a positive integer, got: #{inspect(min_length)}"
          end
          unless (is_integer(max_length) and max_length >= 0) or max_length == :infinity do
            raise ArgumentError, ":max_length must be a positive integer, got: #{inspect(max_length)}"
          end
          {min_length, max_length}
      end

    fn size -> min..(max |> min(size) |> max(min)) end
  end

  defp call_n_times(_data, _seed, _size, 0, acc) do
    acc
  end

  defp call_n_times(data, seed, size, length, acc) do
    {seed1, seed2} = split_seed(seed)
    call_n_times(data, seed2, size, length - 1, [call(data, seed1, size) | acc])
  end

  defp list_lazy_tree(list, min_length) do
    length = length(list)

    if length == min_length do
      LazyTree.constant(list)
    else
      children =
        0..length - 1
        |> Stream.map(&List.delete_at(list, &1))
        |> Stream.map(&list_lazy_tree(&1, min_length))

      LazyTree.new(list, children)
    end
  end

  @doc """
  Generates a list of elements generated by `data` without duplicates (possibly
  according to a given uniqueness function).

  This generator will generate lists where each list is unique according to the
  value returned by applying the given uniqueness function to each element
  (similarly to how `Enum.uniq_by/2` works). If more than the value of the
  `:max_tries` option consecutive elements are generated that are considered
  duplicates according to the uniqueness function, a
  `StreamData.TooManyDuplicatesError` error is raised. For this reason, try to
  make sure to not make the uniqueness function return values out of a small
  value space. The uniqueness function and the max number of tries can be
  customized via options.

  ## Options

    * `:uniq_fun` - (a function of arity one) a function that is called with
      each generated element and whose return value is used as the value to
      compare with other values for uniqueness (similarly to `Enum.uniq_by/2`).

    * `:max_tries` - (non-negative integer) the maximum number of times that
      this generator tries to generate the next element of the list before
      giving up and raising a `StreamData.TooManyDuplicatesError` in case it
      can't find a unique element to generate. Note that the generation size
      often affects this: for example, if you have a generator like
      `uniq_list_of(integer(), min_length: 4)` and you start generating elements
      out of it with a generation size of `1`, it will fail by definition
      because `integer/0` generates in `-size..size` so it would only generate
      in a set (`[-1, 0, 1]`) with three elements. Use `resize/2` or `scale/2`
      to manipulate the size (for example by setting a minimum generation size
      of `3`) in such cases.

    * `:length` - (non-negative integer) same as in `list_of/3`.

    * `:min_length` - (non-negative integer) same as in `list_of/3`.

    * `:max_length` - (non-negative integer) same as in `list_of/3`.

  ## Examples

      data = StreamData.uniq_list_of(StreamData.integer())
      Enum.take(data, 3)
      #=> [[1], [], [2, 3, 1]]

  ## Shrinking

  This generator shrinks like `list_of/1`, but the shrunk values are unique
  according to the `:uniq_fun` option as well.
  """
  @spec uniq_list_of(t(a), keyword) :: t([a]) when a: term
  def uniq_list_of(data, options \\ []) do
    uniq_fun = Keyword.get(options, :uniq_fun, &(&1))
    max_tries = Keyword.get(options, :max_tries, 10)
    list_length_range_fun = list_length_range_fun(options)

    new(fn seed, size ->
      {seed1, seed2} = split_seed(seed)
      min_length.._ = length_range = list_length_range_fun.(size)
      length = uniform_in_range(length_range, seed1)

      data
      |> uniq_list_of(uniq_fun, seed2, size, _seen = MapSet.new(), max_tries, max_tries, length, _acc = [])
      |> LazyTree.zip()
      |> LazyTree.map(&list_lazy_tree(&1, min_length))
      |> LazyTree.flatten()
      |> LazyTree.map(&Enum.uniq_by(&1, uniq_fun))
      |> LazyTree.filter(&(length(&1) >= min_length))
    end)
  end

  defp uniq_list_of(_data, _uniq_fun, _seed, _size, seen, _tries_left = 0, max_tries, remaining, _acc) do
    raise TooManyDuplicatesError, max_tries: max_tries, remaining_to_generate: remaining, generated: seen
  end

  defp uniq_list_of(_data, _uniq_fun, _seed, _size, _seen, _tries_left, _max_tries, _remaining = 0, acc) do
    acc
  end

  defp uniq_list_of(data, uniq_fun, seed, size, seen, tries_left, max_tries, remaining, acc) do
    {seed1, seed2} = split_seed(seed)
    tree = call(data, seed1, size)

    key = uniq_fun.(tree.root)

    if MapSet.member?(seen, key) do
      uniq_list_of(data, uniq_fun, seed2, size, seen, tries_left - 1, max_tries, remaining, acc)
    else
      uniq_list_of(data, uniq_fun, seed2, size, MapSet.put(seen, key), max_tries, max_tries, remaining - 1, [tree | acc])
    end
  end

  @doc ~S"""
  Generates non-empty improper lists where elements of the list are generated
  out of `first` and the improper ending out of `improper`.

  ## Examples

      data = StreamData.nonempty_improper_list_of(StreamData.byte(), StreamData.binary())
      Enum.take(data, 3)
      #=> [["\f"], [56 | <<140, 137>>], [226 | "j"]]

  ## Shrinking

  Shrinks towards smaller lists (that are still non-empty, having the improper
  ending) and towards shrunk elements of the list and a shrunk improper
  ending.
  """
  @spec nonempty_improper_list_of(t(a), t(b)) :: t(nonempty_improper_list(a, b)) when a: term, b: term
  def nonempty_improper_list_of(first, improper) do
    map({list_of(first), improper}, fn
      {[], ending} ->
        [ending]
      {list, ending} ->
        List.foldr(list, ending, &[&1 | &2])
    end)
  end

  @doc """
  Generates lists of elements out of `first` with a chance of them being
  improper with the improper ending taken out of `improper`.

  Behaves similarly to `nonempty_improper_list_of/2` but can generate empty
  lists and proper lists as well.

  ## Examples

      data = StreamData.maybe_improper_list_of(StreamData.byte(), StreamData.binary())
      Enum.take(data, 3)
      #=> [[60 | "."], [], [<<212>>]]

  ## Shrinking

  Shrinks towards smaller lists and shrunk elements in those lists, and
  ultimately towards proper lists.
  """
  @spec maybe_improper_list_of(t(a), t(b)) :: t(maybe_improper_list(a, b)) when a: term, b: term
  def maybe_improper_list_of(first, improper) do
    frequency([
      {2, list_of(first)},
      {1, nonempty_improper_list_of(first, improper)},
    ])
  end

  @doc """
  Generates a list of fixed length where each element is generated from the
  corresponding generator in `data`.

  ## Examples

      data = StreamData.fixed_list([StreamData.integer(), StreamData.binary()])
      Enum.take(data, 3)
      #=> [[1, <<164>>], [2, ".T"], [1, ""]]

  ## Shrinking

  Shrinks by shrinking each element in the generated list according to the
  corresponding generator. Shrunk lists never lose elements.
  """
  @spec fixed_list([t(a)]) :: t([a]) when a: term
  def fixed_list(datas) when is_list(datas) do
    new(fn seed, size ->
      {trees, _seed} =
        Enum.map_reduce(datas, seed, fn data, acc ->
          {seed1, seed2} = split_seed(acc)
          {call(data, seed1, size), seed2}
        end)

      LazyTree.zip(trees)
    end)
  end

  @doc """
  Generates tuples where each element is taken out of the corresponding
  generator in the `tuple_datas` tuple.

  ## Examples

      data = StreamData.tuple({StreamData.integer(), StreamData.binary()})
      Enum.take(data, 3)
      #=> [{-1, <<170>>}, {1, "<"}, {1, ""}]

  ## Shrinking

  Shrinks by shrinking each element in the generated tuple according to the
  corresponding generator.
  """
  @spec tuple(tuple) :: t(tuple)
  def tuple(tuple_datas) when is_tuple(tuple_datas) do
    new(fn seed, size -> call(tuple_datas, seed, size) end)
  end

  @doc """
  Generates maps with keys from `key_data` and values from `value_data`.

  Since maps require keys to be unique, this generator behaves similarly to
  `uniq_list_of/3`: if more than `max_tries` duplicate keys are generated
  consequently, it raises a `StreamData.TooManyDuplicatesError` exception.

  ## Examples

      Enum.take(StreamData.map_of(StreamData.integer(), StreamData.boolean()), 3)
      #=> [%{}, %{1 => false}, %{-2 => true, -1 => false}]

  ## Shrinking

  Shrinks towards smallest maps and towards shrinking keys and values according
  to the respective generators.
  """
  @spec map_of(t(key), t(value)) :: t(%{optional(key) => value}) when key: term, value: term
  def map_of(key_data, value_data, max_tries \\ 10) do
    {key_data, value_data}
    |> uniq_list_of(uniq_fun: fn {key, _value} -> key end, max_tries: max_tries)
    |> map(&Map.new/1)
  end

  @doc """
  Generates maps with fixed keys and generated values.

  `data_map` is a map of `fixed_key => data` pairs. Maps generated by this
  generator will have the same keys as `data_map` and values corresponding to
  values generated by the generator under those keys.

  ## Examples

      data = StreamData.fixed_map(%{
        integer: StreamData.integer(),
        binary: StreamData.binary(),
      })
      Enum.take(data, 3)
      #=> [%{binary: "", int: 1}, %{binary: "", int: -2}, %{binary: "R1^", int: -3}]

  ## Shrinking

  This generator shrinks by shrinking the values of the generated map.
  """
  @spec fixed_map(map) :: t(map)
  def fixed_map(data_map) when is_map(data_map) do
    data_map
    |> Enum.map(fn {key, value_data} -> {constant(key), value_data} end)
    |> fixed_list()
    |> map(&Map.new/1)
  end

  @doc """
  Generates keyword lists where values are generated by `value_data`.

  Keys are always atoms.

  ## Examples

      Enum.take(StreamData.keyword_of(StreamData.integer()), 3)
      #=> [[], [sY: 1], [t: -1]]

  ## Shrinking

  This generator shrinks equivalently to a list of key-value tuples generated by
  `list_of/1`, that is, by shrinking the values in each tuple and also reducing
  the size of the generated keyword list.
  """
  @spec keyword_of(t(a)) :: t(keyword(a)) when a: term
  def keyword_of(value_data) do
    list_of({unquoted_atom(), value_data})
  end

  @doc """
  Constrains the given `enum_data` to be non-empty.

  `enum_data` must be a generator that emits enumerables, such as lists
  and maps. `nonempty/1` will filter out enumerables that are empty
  (`Enum.empty?/1` returns `true`).

  ## Examples

      Enum.take(StreamData.nonempty(StreamData.list_of(StreamData.integer())), 3)
      #=> [[1], [-1, 0], [2, 1, -2]]

  """
  @spec nonempty(t(Enumerable.t)) :: t(Enumerable.t)
  def nonempty(enum_data) do
    filter(enum_data, &not(Enum.empty?(&1)))
  end

  @doc ~S"""
  Generates trees of values generated by `leaf_data`.

  `subtree_fun` is a function that takes a generator and returns a generator
  that "combines" that generator. This generator will pass `leaf_data` to
  `subtree_fun` when it needs to go "one level deeper" in the tree. Note that
  raw values from `leaf_data` can sometimes be generated.

  This is best explained with an example. Say that we want to generate binary
  trees of integers, and that we represent binary trees as either an integer (a
  leaf) a `%Branch{}` struct:

      defmodule Branch do
        defstruct [:left, :right]
      end

  We can start off by creating a generator that generates branches given the
  generator that generates the content of each node (`integer/0` in our case):

      defmodule MyTree do
        def branch_data(child_data) do
          StreamData.map({child_data, child_data}, fn {left, right} ->
            %Branch{left: left, right: right}
          end)
        end
      end

  Now, we can generate trees by simply using `branch_data` as the `subtree_fun`,
  and `integer/0` as `leaf_data`:

      tree_data = StreamData.tree(StreamData.integer(), &MyTree.branch_data/1)
      Enum.at(StreamData.resize(tree_data, 10), 0)
      #=> %Branch{left: %Branch{left: 4, right: -1}, right: -2}

  ## Examples

  A common example is nested lists:

      data = StreamData.tree(StreamData.integer(), &StreamData.list_of/1)
      Enum.at(StreamData.resize(data, 10), 0)
      #=> [[], '\t', '\a', [1, 2], -3, [-7, [10]]]

  ## Shrinking

  Shrinks values and shrinks towards less deep trees.
  """
  @spec tree(t(a), (t(a) -> t(b))) :: t(a | b) when a: term, b: term
  def tree(leaf_data, subtree_fun) do
    new(fn seed, size ->
      leaf_data = resize(leaf_data, size)
      {seed1, seed2} = split_seed(seed)
      nodes_on_each_level = random_pseudofactors(trunc(:math.pow(size, 1.1)), seed1)
      data =
        Enum.reduce(nodes_on_each_level, leaf_data, fn nodes_on_this_level, data_acc ->
          frequency([
            {1, data_acc},
            {2, resize(subtree_fun.(data_acc), nodes_on_this_level)},
          ])
        end)

      call(data, seed2, size)
    end)
  end

  defp random_pseudofactors(n, _seed) when n < 2 do
    [n]
  end

  defp random_pseudofactors(n, seed) do
    {seed1, seed2} = split_seed(seed)
    {factor, _seed} = :rand.uniform_s(trunc(:math.log2(n)), seed1)

    if factor == 1 do
      [n]
    else
      [factor | random_pseudofactors(div(n, factor), seed2)]
    end
  end

  ## Data types

  @doc """
  Generates boolean values.

  ## Examples

      Enum.take(StreamData.boolean(), 3)
      #=> [true, true, false]

  ## Shrinking

  Shrinks towards `false`.
  """
  @spec boolean() :: t(boolean)
  def boolean() do
    member_of([false, true])
  end

  @doc """
  Generates integers bound by the generation size.

  ## Examples

      Enum.take(StreamData.integer(), 3)
      #=> [1, -1, -3]

  ## Shrinking

  Generated values shrink towards `0`.
  """
  @spec integer() :: t(integer)
  def integer() do
    sized(fn size -> integer(-size..size) end)
  end

  @doc """
  Generates uniformly distributed floats in the interval `0..1`.

  Note that if you want to have more complex float values, such as negative
  values or bigger values, you can transform this generator. For example, to
  have floats in the interval `0..10`, you can use `map/2`:

      StreamData.map(StreamData.uniform_float(), &(&1 * 10))

  To have sometimes negative floats, you can for example use `bind/2`:

      StreamData.bind(StreamData.boolean(), fn negative? ->
        if negative? do
          StreamData.map(StreamData.uniform_float(), &(-&1))
        else
          StreamData.uniform_float()
        end
      end)

  ## Examples

      Enum.take(StreamData.uniform_float(), 3)
      #=> [0.5122356680893687, 0.7387020706272481, 0.9613874981766901]

  ## Shrinking

  Values generated by this generator do not shrink.
  """
  @spec uniform_float() :: t(float)
  def uniform_float() do
    new(fn seed, _size ->
      {float, _seed} = :rand.uniform_s(seed)
      LazyTree.constant(float)
    end)
  end

  @doc """
  Generates bytes.

  A byte is an integer between `0` and `255`.

  ## Examples

      Enum.take(StreamData.byte(), 3)
      #=> [102, 161, 13]

  ## Shrinking

  Values generated by this generator shrink like integers, so towards bytes
  closer to `0`.
  """
  @spec byte() :: t(byte)
  def byte() do
    integer(0..255)
  end

  @doc """
  Generates binaries.

  The length of the generated binaries is limited by the generation size.

  ## Options

    * `:length` - (non-negative integer) sets the exact length of the generated
      binaries (same as in `list_of/3`).

    * `:min_length` - (non-negative integer) sets the minimum length of the
      generated binaries (same as in `list_of/3`). Ignored if `:length` is
      present.

    * `:max_length` - (non-negative integer) sets the maximum length of the
      generated binaries (same as in `list_of/3`). Ignored if `:length` is
      present.

  ## Examples

      Enum.take(StreamData.binary(), 3)
      #=> [<<1>>, "", "@Q"]

  ## Shrinking

  Values generated by this generator shrink by becoming smaller binaries and by
  having individual bytes that shrink towards `0`.
  """
  @spec binary(keyword) :: t(binary)
  def binary(options \\ []) do
    list_options = Keyword.take(options, [:length, :min_length, :max_length])
    map(list_of(byte(), list_options), &IO.iodata_to_binary/1)
  end

  @doc """
  Generates bitstrings.

  The length of the generated bitstring is limited by the generation size.

  ## Options

    * `:length` - (non-negative integer) sets the exact length of the generated
      bitstrings (same as in `list_of/3`).

    * `:min_length` - (non-negative integer) sets the minimum length of the
      generated bitstrings (same as in `list_of/3`). Ignored if `:length` is
      present.

    * `:max_length` - (non-negative integer) sets the maximum length of the
      generated bitstrings (same as in `list_of/3`). Ignored if `:length` is
      present.

  ## Examples

      Enum.take(StreamData.bitstring(), 3)
      #=> [<<0::size(1)>>, <<2::size(2)>>, <<5::size(3)>>]

  ## Shrinking

  Values generated by this generator shrink by becoming smaller bitstrings and
  by having the individual bits go towards `0`.
  """
  @spec bitstring(keyword) :: t(bitstring)
  def bitstring(options \\ []) do
    bits = member_of([0, 1])
    list_options = Keyword.take(options, [:length, :min_length, :max_length])

    map(list_of(bits, list_options), fn bits ->
      Enum.reduce(bits, <<>>, fn bit, acc ->
        <<bit::1, acc::bits>>
      end)
    end)
  end

  @ascii_chars ?\s..?~
  @alphanumeric_chars [?a..?z, ?A..?Z, ?0..?9]
  @printable_chars [
    ?\n,
    ?\r,
    ?\t,
    ?\v,
    ?\b,
    ?\f,
    ?\e,
    ?\d,
    ?\a,
    0x20..0x7E,
    0xA0..0xD7FF,
    0xE000..0xFFFD,
    0x10000..0x10FFFF,
  ]

  @doc """
  Generates a string of the given kind or from the given characters.

  `kind_or_chars` can be:

    * `:ascii` - strings containing only ASCII characters are generated. Such
      strings shrink towards lower codepoints.

    * `:alphanumeric` - strings containing only alphanumeric characters
      (`?a..?z`, `?A..?Z`, `?0..?9`) are generated. Such strings shrink towards
      `?a` following the order shown previously.

    * `:printable` - printable strings (`String.printable?/1` returns `true`)
      are generated. Such strings shrink towards lower codepoints.

    * a range - strings with characters from the range are generated. Such
      strings shrink towards characters that appear earlier in the range.

    * a list of ranges or single codepoints - strings with characters from the
      ranges or codepoints are generated. Such strings shrink towards earlier
      elements of the given list and towards the beginning of ranges.

  ## Examples

      Enum.take(StreamData.string(:ascii), 3)
      #=> ["c", "9A", ""]

      Enum.take(StreamData.string(Enum.concat([?a..?c, ?l..?o])), 3)
      #=> ["c", "oa", "lb"]

  ## Shrinking

  Shrinks towards smaller strings and as described in the description of the
  possible values of `kind_or_chars` above.
  """
  @spec string(:ascii | :alphanumeric | :printable | Range.t | [Range.t | pos_integer]) ::
        t(String.t)
  def string(kind_or_codepoints, options \\ [])

  def string(:ascii, options) do
    string(@ascii_chars, options)
  end

  def string(:alphanumeric, options) do
    string(@alphanumeric_chars, options)
  end

  def string(:printable, options) do
    string(@printable_chars, options)
  end

  def string(%Range{} = codepoints_range, options) do
    # We do this instead of calling string([codepoints_range], options) for speed.
    list_options = Keyword.take(options, [:length, :min_length, :max_length])
    map(list_of(integer(codepoints_range), list_options), &List.to_string/1)
  end

  def string(codepoints, options)
      when is_list(codepoints) and is_list(options) do
    list_options = Keyword.take(options, [:length, :min_length, :max_length])

    char =
      bind(member_of(codepoints), fn
        %Range{} = range ->
          integer(range)
        codepoint when is_integer(codepoint) ->
          constant(codepoint)
      end)

    map(list_of(char, list_options), &List.to_string/1)
  end

  def string(other, _options) do
    raise ArgumentError, "unsupported string kind, has to be one of :ascii, " <>
                         ":alphanumeric, :printable, a range, or a list of " <>
                         "ranges or single codepoints, got: #{inspect(other)}"
 end

  @unquoted_atom_characters [?a..?z, ?A..?Z, ?0..?9, ?_, ?@]

  @doc """
  Generates atoms that don't need to be quoted when written as literals.

  ## Examples

      Enum.take(StreamData.unquoted_atom(), 3)
      #=> [:xF, :y, :B_]

  ## Shrinking

  Shrinks towards smaller atoms in the `?a..?z` character set.
  """
  @spec unquoted_atom() :: t(atom)
  def unquoted_atom() do
    starting_char =
      frequency([
        {4, integer(?a..?z)},
        {2, integer(?A..?Z)},
        {1, constant(?_)},
      ])

    # We limit the size to 255 so that adding the first character doesn't
    # break the system limit of 256 chars in an atom.
    rest = scale(string(@unquoted_atom_characters), &min(&1, 255))

    {starting_char, rest}
    |> resize_atom_data()
    |> map(fn {first, rest} -> String.to_atom(<<first>> <> rest) end)
  end

  def module_alias() do
    chars = string(unquote(Enum.concat([?a..?z, ?A..?Z, ?0..?9, [?_]])))

    {integer(?A..?Z), scale(chars, &min(&1, 255))}
    |> map(fn {first, rest} -> <<first>> <> rest end)
    |> list_of()
    |> nonempty()
    |> map(&Module.concat/1)
    |> scale(&trunc(:math.pow(&1, 0.5)))
  end

  defp resize_atom_data(data) do
    scale(data, fn size ->
      min(trunc(:math.pow(size, 0.5)), 256)
    end)
  end

  @doc """
  Generates iolists.

  Iolists are values of the `t:iolist/0` type.

  ## Examples

      Enum.take(StreamData.iolist(), 3)
      #=> [[164 | ""], [225], ["" | ""]]

  ## Shrinking

  Shrinks towards smaller and less nested lists and towards bytes instead of
  binaries.
  """
  @spec iolist() :: t(iolist)
  def iolist() do
    # We try to use binaries that scale slower otherwise we end up with iodata with
    # big binaries at many levels deep.
    scaled_binary = scale(binary(), &trunc(:math.pow(&1, 0.6)))

    improper_ending = one_of([scaled_binary, constant([])])
    tree = tree(one_of([byte(), scaled_binary]), &maybe_improper_list_of(&1, improper_ending))
    map(tree, &List.wrap/1)
  end

  @doc """
  Generates iodata.

  Iodata are values of the `t:iodata/0` type.

  ## Examples

      Enum.take(StreamData.iodata(), 3)
      #=> [[""], <<198>>, [115, 172]]

  ## Shrinking

  Shrinks towards less nested iodata and ultimately towards smaller binaries.
  """
  @spec iodata() :: t(iodata)
  def iodata() do
    frequency([
      {3, binary()},
      {2, iolist()},
    ])
  end

  @doc """
  Checks the behaviour of a given function on values generated by `data`.

  This function takes a generator and a function `fun` and verifies that that
  function "holds" for all generated data. `fun` is called with each generated
  value and can return one of:

    * {:ok, term} - means that the function "holds" for the given value. `term`
      can be anything and will be used for internal purposes by `StreamData`.

    * `{:error, term}` - means that the function doesn't hold for the given
      value. `term` is the term that will be shrunk to find the minimal value
      for which `fun` doesn't hold. See below for more information on shrinking.

  When a value is found for which `fun` doesn't hold (returns `{:error, term}`),
  `check_all/3` tries to shrink that value in order to find a minimal value that
  still doesn't satisfy `fun`.

  The return value of this function is one of:

    * `{:ok, map}` - if all generated values satisfy `fun`. `map` is a map of
      metadata that contains no keys for now.

    * `{:error, map}` - if a generated value doesn't satisfy `fun`. `map` is a
      map of metadata that contains the following keys:

      * `:original_failure` - if `fun` returned `{:error, term}` for a generated
        value, this key in the map will be `term`.

      * `:shrunk_failure` - the value returned in `{:error, term}` by `fun`
        when invoked with the smallest failing value that was generated.

      * `:nodes_visited` - the number of nodes (a positive integer) visited in
        the shrinking tree in order to find the smallest value. See also the
        `:max_shrinking_steps` option.

  ## Options

  This function takes the following options:

    * `:initial_seed` - three-element tuple with three integers that is used as
      the initial random seed that drives the random generation. This option is
      required.

    * `:initial_size` - (non-negative integer) the initial generation size used
      to start generating values. The generation size is then incremented by `1`
      on each iteration. See the "Generation size" section of the module
      documentation for more information on generation size. Defaults to `1`.

    * `:max_runs` - (non-negative integer) the total number of elements to
      generate out of `data` and check through `fun`. Defaults to `100`.

    * `:max_shrinking_steps` - (non-negative integer) the maximum numbers of
      shrinking steps to perform in case `check_all/3` finds an element that
      doesn't satisfy `fun`. Defaults to `100`.

  ## Examples

  Let's try out a contrived example: we want to verify that the `integer/0`
  generator generates integers that are not `0` or multiples of `11`. This
  verification is broken by design because `integer/0` is likely to generate
  multiples of `11` at some point, but it will show the capabilities of
  `check_all/3`. For the sake of the example, let's say we want the values that
  fail to be represented as strings instead of the original integers that
  failed. We can implement what we described like this:

      options = [initial_seed: :os.timestamp()]

      {:error, metadata} = StreamData.check_all(StreamData.integer(), options, fn int ->
        if int == 0 or rem(int, 11) != 0 do
          {:ok, nil}
        else
          {:error, Integer.to_string(int)}
        end
      end)

      metadata.nodes_visited
      #=> 7
      metadata.original_failure
      #=> 22
      metadata.shrunk_failure
      #=> 11

  As we can see, the function we passed to `check_all/3` "failed" for `int =
  22`, and `check_all/3` was able to shrink this value to the smallest failing
  value, which in this case is `11`.
  """
  @spec check_all(t(a), Keyword.t, (a -> {:ok, term} | {:error, b})) :: {:ok, map} | {:error, map}
        when a: term, b: term
  def check_all(data, options, fun) when is_list(options) and is_function(fun, 1) do
    seed = new_seed(Keyword.fetch!(options, :initial_seed))
    size = Keyword.get(options, :initial_size, 1)
    max_shrinking_steps = Keyword.get(options, :max_shrinking_steps, 100)
    max_runs = Keyword.get(options, :max_runs, 100)

    config = %{
      max_runs: max_runs,
      max_shrinking_steps: max_shrinking_steps,
    }

    check_all(data, seed, size, fun, _runs = 0, config)
  end

  defp check_all(_data, _seed, _size, _fun, runs, %{max_runs: runs}) do
    {:ok, %{}}
  end

  defp check_all(data, seed, size, fun, runs, config) do
    {seed1, seed2} = split_seed(seed)
    %LazyTree{root: root, children: children} = call(data, seed1, size)

    case fun.(root) do
      {:ok, _term} ->
        check_all(data, seed2, size + 1, fun, runs + 1, config)
      {:error, reason} ->
        shrinking_result = shrink_failure(shrink_initial_cont(children), nil, reason, fun, 1, config)
        shrinking_result = Map.put(shrinking_result, :original_failure, reason)
        {:error, shrinking_result}
    end
  end

  defp shrink_initial_cont(nodes) do
    &Enumerable.reduce(nodes, &1, fn elem, acc -> {:suspend, [elem | acc]} end)
  end

  defp shrink_failure(_cont, _parent_cont, smallest, _fun, nodes_visited, %{max_shrinking_steps: nodes_visited}) do
    %{shrunk_failure: smallest, nodes_visited: nodes_visited}
  end

  # We try to get the next element out of the current nodes. If the current
  # nodes are finished, we check if this was the first check: if it was, it
  # means we were visiting children of a node and this node has no children, so
  # we recurse on the siblings of that node. Otherwise, we return the smallest
  # failure. If we get the next nodes out of the current nodes, we check if it
  # also fails: if it does, we "go down" and recurse on the children of that
  # node but only if it has children, otherwise we move to the siblings. If it
  # doesn't fail, we move to the siblings.

  defp shrink_failure(cont, parent_cont, smallest, fun, nodes_visited, config) do
    case cont.({:cont, []}) do
      {state, _} when state in [:halted, :done] and is_function(parent_cont) ->
        shrink_failure(parent_cont, nil, smallest, fun, nodes_visited, config)
      {state, _} when state in [:halted, :done] ->
        %{shrunk_failure: smallest, nodes_visited: nodes_visited}
      {:suspended, [child], cont} ->
        case fun.(child.root) do
          {:ok, _term} ->
            shrink_failure(cont, nil, smallest, fun, nodes_visited + 1, config)
          {:error, reason} ->
            shrink_failure(shrink_initial_cont(child.children), cont, reason, fun, nodes_visited + 1, config)
        end
    end
  end

  @doc """
  Syntactic sugar to create generators.

  This macro provides ad hoc syntax to write complex generators. Let's see a
  quick example to get a feel of how it works. Say we have a `User` struct:

      defmodule User do
        defstruct [:name, :email]
      end

  We can create a generator of users like this:

      email_generator = map({binary(), binary()}, fn left, right -> left <> "@" <> right end)
      gen all name <- binary(),
              email <- email_generator do
        %User{name: name, email: email}
      end

  Everything between `gen all` and `do` is referred to as **clauses**. Clauses
  are used to specify the values to generate to be used in the body. The newly
  created generator will generated values that are the return value of the
  `do` body for the generated values from the clauses.

  ### Clauses

  As seen in the example above, clauses can be of three types:

    * value generation - they have the form `pattern <- generator` where
      `generator` must be a generator. These clauses take a value out of
      `generator` on each run and match it against `pattern`. Variables bound in
      `pattern` can be then used throughout subsequent clauses and in the `do`
      body.

    * binding - they have the form `pattern = expression`. They are exactly like
      assignment through the `=` operator: if `pattern` doesn't match
      `expression`, an error is raised. They can be used to bind values for use
      in subsequent clauses and in the `do` body.

    * filtering - they have the form `expression`. If a filtering clause returns
      a truthy value, then the set of generated values that appear before the
      filtering clause is considered valid and generation continues. If the
      filtering clause returns a falsey value, then the current value is
      considered invalid and a new value is generated. Note that filtering
      clauses should not filter out too many times; in case they do, a
      `StreamData.FilterTooNarrowError` error is raised (same as `filter/3`).

  ### Body

  The return value of the body passed in the `do` block is what is ultimately
  generated by the generator return by this macro.

  ## Shrinking

  See the module documentation for more information on shrinking. Clauses affect
  shrinking in the following way:

    * binding clauses don't affect shrinking
    * filtering clauses affect shrinking like `filter/3`
    * value generation clauses affect shrinking similarly to `bind/2`

  """
  defmacro gen({:all, _meta, clauses} = _generation_clauses, [do: body] = _block) do
    compile(clauses, body)
  end

  defp compile(clauses, body) do
    quote do
      var!(generated_values, unquote(__MODULE__)) = []
      {:cont, data} = unquote(compile_clauses(clauses, body))
      data
    end
  end

  defp compile_clauses([], body) do
    quote do
      var!(generated_values, unquote(__MODULE__)) = Enum.reverse(var!(generated_values, unquote(__MODULE__)))
      {:cont, StreamData.constant(unquote(body))}
    end
  end

  defp compile_clauses([{:<-, _meta, [pattern, generator]} = clause | rest], body) do
    quote do
      data =
        StreamData.bind_filter(unquote(generator), fn unquote(pattern) = generated_value ->
          var!(generated_values, unquote(__MODULE__)) =
            [{unquote(Macro.to_string(clause)), generated_value} | var!(generated_values, unquote(__MODULE__))]
          unquote(compile_clauses(rest, body))
        end)

      {:cont, data}
    end
  end

  defp compile_clauses([{:=, _meta, [_left, _right]} = assignment | rest], body) do
    quote do
      unquote(assignment)
      unquote(compile_clauses(rest, body))
    end
  end

  defp compile_clauses([clause | rest], body) do
    quote do
      if unquote(clause) do
        unquote(compile_clauses(rest, body))
      else
        :skip
      end
    end
  end

  defp new_seed({int1, int2, int3} = tuple)
       when is_integer(int1) and is_integer(int2) and is_integer(int3) do
    :rand.seed_s(@rand_algorithm, tuple)
  end

  defp split_seed(seed) do
    {int1, seed} = :rand.uniform_s(1_000_000_000, seed)
    {int2, seed} = :rand.uniform_s(1_000_000_000, seed)
    {int3, seed} = :rand.uniform_s(1_000_000_000, seed)
    new_seed = :rand.seed_s(@rand_algorithm, {int1, int2, int3})
    {new_seed, seed}
  end

  defp uniform_in_range(left..right, seed) when left > right do
    uniform_in_range(right..left, seed)
  end

  defp uniform_in_range(left..right, seed) do
    width = right - left
    {random_int, _seed} = :rand.uniform_s(width + 1, seed)
    random_int - 1 + left
  end

  # This is the implementation of Enumerable.reduce/3. It's here because it
  # needs split_seed/1 and call/3 which are private.
  def __reduce__(data, acc, fun) do
    reduce(data, acc, fun, new_seed(:os.timestamp()), _initial_size = 1, _max_size = 100)
  end

  defp reduce(_data, {:halt, acc}, _fun, _seed, _size, _max_size) do
    {:halted, acc}
  end

  defp reduce(data, {:suspend, acc}, fun, seed, size, max_size) do
    {:suspended, acc, &reduce(data, &1, fun, seed, size, max_size)}
  end

  defp reduce(data, {:cont, acc}, fun, seed, size, max_size) do
    {seed1, seed2} = split_seed(seed)
    %LazyTree{root: next} = call(data, seed1, size)
    reduce(data, fun.(next, acc), fun, seed2, min(max_size, size + 1), max_size)
  end

  ## Enumerable

  defimpl Enumerable do
    def reduce(data, acc, fun), do: @for.__reduce__(data, acc, fun)
    def count(_data), do: {:error, __MODULE__}
    def member?(_data, _term), do: {:error, __MODULE__}
  end
end