path: root/src/tools/wasm-fuzz-lattices.cpp

/*
 * Copyright 2023 WebAssembly Community Group participants
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <optional>
#include <random>
#include <string>
#include <type_traits>
#include <variant>

#include "analysis/lattice.h"
#include "analysis/lattices/array.h"
#include "analysis/lattices/bool.h"
#include "analysis/lattices/flat.h"
#include "analysis/lattices/int.h"
#include "analysis/lattices/inverted.h"
#include "analysis/lattices/lift.h"
#include "analysis/lattices/shared.h"
#include "analysis/lattices/stack.h"
#include "analysis/lattices/tuple.h"
#include "analysis/lattices/valtype.h"
#include "analysis/lattices/vector.h"
#include "analysis/liveness-transfer-function.h"
#include "analysis/reaching-definitions-transfer-function.h"
#include "analysis/transfer-function.h"

#include "support/command-line.h"
#include "tools/fuzzing.h"
#include "tools/fuzzing/random.h"

namespace wasm {
using RandEngine = std::mt19937_64;
using namespace analysis;

// Helps printing error messages.
std::string LatticeComparisonNames[4] = {
  "No Relation", "Equal", "Less", "Greater"};

uint64_t getSeed() {
  // Return a (truly) random 64-bit value.
  std::random_device rand;
  return std::uniform_int_distribution<uint64_t>{}(rand);
}

// Actually a pointer to `L::ElementImpl`, but we erase the type to avoid
// getting into a situation where `L` satisfying `Lattice` or `FullLattice`
// circularly requires that `L` satisfies `Lattice` or `FullLattice`. C++ does
// not allow concepts to depend on themselves. Also make the pointer copyable to
// satisfy that constraint on lattice elements.
template<typename L>
struct RandomElement : std::unique_ptr<void, void (*)(void*)> {
  RandomElement() = default;

  RandomElement(typename L::ElementImpl&& other)
    : std::unique_ptr<void, void (*)(void*)>(
        new typename L::ElementImpl(std::move(other)),
        [](void* e) { delete static_cast<typename L::ElementImpl*>(e); }) {}

  RandomElement(const RandomElement& other)
    : RandomElement([&]() {
        auto copy = *other;
        return copy;
      }()) {}

  RandomElement(RandomElement&& other) = default;
  RandomElement& operator=(const RandomElement& other) {
    if (this != &other) {
      new (this) RandomElement(other);
    }
    return *this;
  }

  RandomElement& operator=(RandomElement&& other) = default;

  typename L::ElementImpl& operator*() {
    return *static_cast<typename L::ElementImpl*>(get());
  }

  const typename L::ElementImpl& operator*() const {
    return *static_cast<const typename L::ElementImpl*>(get());
  }

  typename L::ElementImpl* operator->() { return &*(*this); }

  const typename L::ElementImpl* operator->() const { return &*(*this); }
};

struct RandomFullLattice {
  // The inner lattice and lattice element types. These must be defined later
  // because they depend on `RandomFullLattice` satisfying `FullLattice`, but
  // that requires the type to be complete.
  struct LatticeImpl;
  struct ElementImpl;
  using Element = RandomElement<RandomFullLattice>;

  Random& rand;

  // Indirect because LatticeImpl recursively contains RandomFullLattice.
  std::unique_ptr<LatticeImpl> lattice;

  RandomFullLattice(Random& rand,
                    size_t depth = 0,
                    std::optional<uint32_t> maybePick = std::nullopt);

  // Make a random element of this lattice.
  Element makeElement() const noexcept;

  Element getBottom() const noexcept;
  Element getTop() const noexcept;
  LatticeComparison compare(const Element& a, const Element& b) const noexcept;
  bool join(Element& a, const Element& b) const noexcept;
  bool meet(Element& a, const Element& b) const noexcept;
};

struct RandomLattice {
  // The inner lattice and lattice element types. These must be defined later
  // because they depend on `RandomLattice` satisfying `Lattice`, but that
  // requires the type to be complete.
  struct LatticeImpl;
  struct ElementImpl;
  using Element = RandomElement<RandomLattice>;

  Random& rand;

  // Indirect because L recursively contains RandomLattice.
  std::unique_ptr<LatticeImpl> lattice;

  RandomLattice(Random& rand, size_t depth = 0);

  // Make a random element of this lattice.
  Element makeElement() const noexcept;

  Element getBottom() const noexcept;
  LatticeComparison compare(const Element& a, const Element& b) const noexcept;
  bool join(Element& a, const Element& b) const noexcept;
};

#if __cplusplus >= 202002L
static_assert(FullLattice<RandomFullLattice>);
static_assert(Lattice<RandomLattice>);
#endif

using ArrayFullLattice = analysis::Array<RandomFullLattice, 2>;
using ArrayLattice = analysis::Array<RandomLattice, 2>;

using TupleFullLattice = analysis::Tuple<RandomFullLattice, RandomFullLattice>;
using TupleLattice = analysis::Tuple<RandomLattice, RandomLattice>;

using FullLatticeVariant = std::variant<Bool,
                                        UInt32,
                                        ValType,
                                        Inverted<RandomFullLattice>,
                                        ArrayFullLattice,
                                        Vector<RandomFullLattice>,
                                        TupleFullLattice>;

struct RandomFullLattice::LatticeImpl : FullLatticeVariant {};

using FullLatticeElementVariant =
  std::variant<typename Bool::Element,
               typename UInt32::Element,
               typename ValType::Element,
               typename Inverted<RandomFullLattice>::Element,
               typename ArrayFullLattice::Element,
               typename Vector<RandomFullLattice>::Element,
               typename TupleFullLattice::Element>;

struct RandomFullLattice::ElementImpl : FullLatticeElementVariant {};

using LatticeVariant = std::variant<RandomFullLattice,
                                    Flat<uint32_t>,
                                    Lift<RandomLattice>,
                                    ArrayLattice,
                                    Vector<RandomLattice>,
                                    TupleLattice,
                                    SharedPath<RandomLattice>>;

struct RandomLattice::LatticeImpl : LatticeVariant {};

using LatticeElementVariant =
  std::variant<typename RandomFullLattice::Element,
               typename Flat<uint32_t>::Element,
               typename Lift<RandomLattice>::Element,
               typename ArrayLattice::Element,
               typename Vector<RandomLattice>::Element,
               typename TupleLattice::Element,
               typename SharedPath<RandomLattice>::Element>;

struct RandomLattice::ElementImpl : LatticeElementVariant {};

constexpr int FullLatticePicks = 7;

RandomFullLattice::RandomFullLattice(Random& rand,
                                     size_t depth,
                                     std::optional<uint32_t> maybePick)
  : rand(rand) {
  // TODO: Limit the depth once we get lattices with more fan-out.
  uint32_t pick = maybePick ? *maybePick : rand.upTo(FullLatticePicks);
  switch (pick) {
    case 0:
      lattice = std::make_unique<LatticeImpl>(LatticeImpl{Bool{}});
      return;
    case 1:
      lattice = std::make_unique<LatticeImpl>(LatticeImpl{UInt32{}});
      return;
    case 2:
      lattice = std::make_unique<LatticeImpl>(LatticeImpl{ValType{}});
      return;
    case 3:
      lattice = std::make_unique<LatticeImpl>(
        LatticeImpl{Inverted{RandomFullLattice{rand, depth + 1}}});
      return;
    case 4:
      lattice = std::make_unique<LatticeImpl>(
        LatticeImpl{ArrayFullLattice{RandomFullLattice{rand, depth + 1}}});
      return;
    case 5:
      lattice = std::make_unique<LatticeImpl>(
        LatticeImpl{Vector{RandomFullLattice{rand, depth + 1}, rand.upTo(4)}});
      return;
    case 6:
      lattice = std::make_unique<LatticeImpl>(
        LatticeImpl{TupleFullLattice{RandomFullLattice{rand, depth + 1},
                                     RandomFullLattice{rand, depth + 1}}});
      return;
  }
  WASM_UNREACHABLE("unexpected pick");
}

RandomLattice::RandomLattice(Random& rand, size_t depth) : rand(rand) {
  // TODO: Limit the depth once we get lattices with more fan-out.
  uint32_t pick = rand.upTo(FullLatticePicks + 6);

  if (pick < FullLatticePicks) {
    lattice = std::make_unique<LatticeImpl>(
      LatticeImpl{RandomFullLattice{rand, depth, pick}});
    return;
  }

  switch (pick) {
    case FullLatticePicks + 0:
      lattice = std::make_unique<LatticeImpl>(LatticeImpl{Flat<uint32_t>{}});
      return;
    case FullLatticePicks + 1:
      lattice = std::make_unique<LatticeImpl>(
        LatticeImpl{Lift{RandomLattice{rand, depth + 1}}});
      return;
    case FullLatticePicks + 2:
      lattice = std::make_unique<LatticeImpl>(
        LatticeImpl{ArrayLattice{RandomLattice{rand, depth + 1}}});
      return;
    case FullLatticePicks + 3:
      lattice = std::make_unique<LatticeImpl>(
        LatticeImpl{Vector{RandomLattice{rand, depth + 1}, rand.upTo(4)}});
      return;
    case FullLatticePicks + 4:
      lattice = std::make_unique<LatticeImpl>(LatticeImpl{TupleLattice{
        RandomLattice{rand, depth + 1}, RandomLattice{rand, depth + 1}}});
      return;
    case FullLatticePicks + 5:
      lattice = std::make_unique<LatticeImpl>(
        LatticeImpl{SharedPath{RandomLattice{rand, depth + 1}}});
      return;
  }
  WASM_UNREACHABLE("unexpected pick");
}

RandomFullLattice::Element RandomFullLattice::makeElement() const noexcept {
  if (std::get_if<Bool>(lattice.get())) {
    return ElementImpl{rand.pick(true, false)};
  }
  if (std::get_if<UInt32>(lattice.get())) {
    return ElementImpl{rand.upToSquared(33)};
  }
  if (std::get_if<ValType>(lattice.get())) {
    Type type;
    // Choose a random type. No need to make all possible types available as
    // long as we cover all the kinds of relationships between types.
    switch (rand.upTo(8)) {
      case 0:
        type = Type::unreachable;
        break;
      case 1:
        type = Type::none;
        break;
      case 2:
        type = Type::i32;
        break;
      case 3:
        type = Type::f32;
        break;
      case 4:
        type = Type(HeapType::any, rand.oneIn(2) ? Nullable : NonNullable);
        break;
      case 5:
        type = Type(HeapType::none, rand.oneIn(2) ? Nullable : NonNullable);
        break;
      case 6:
        type = Type(HeapType::struct_, rand.oneIn(2) ? Nullable : NonNullable);
        break;
      case 7:
        type = Type(HeapType::array, rand.oneIn(2) ? Nullable : NonNullable);
        break;
    }
    return ElementImpl{type};
  }
  if (const auto* l = std::get_if<Inverted<RandomFullLattice>>(lattice.get())) {
    return ElementImpl{l->lattice.makeElement()};
  }
  if (const auto* l = std::get_if<ArrayFullLattice>(lattice.get())) {
    return ElementImpl{typename ArrayFullLattice::Element{
      l->lattice.makeElement(), l->lattice.makeElement()}};
  }
  if (const auto* l = std::get_if<Vector<RandomFullLattice>>(lattice.get())) {
    std::vector<typename RandomFullLattice::Element> elem;
    elem.reserve(l->size);
    for (size_t i = 0; i < l->size; ++i) {
      elem.push_back(l->lattice.makeElement());
    }
    return ElementImpl{std::move(elem)};
  }
  if (const auto* l = std::get_if<TupleFullLattice>(lattice.get())) {
    return ElementImpl{typename TupleFullLattice::Element{
      std::get<0>(l->lattices).makeElement(),
      std::get<1>(l->lattices).makeElement()}};
  }
  WASM_UNREACHABLE("unexpected lattice");
}

RandomLattice::Element RandomLattice::makeElement() const noexcept {
  if (const auto* l = std::get_if<RandomFullLattice>(lattice.get())) {
    return ElementImpl{l->makeElement()};
  }
  if (const auto* l = std::get_if<Flat<uint32_t>>(lattice.get())) {
    auto pick = rand.upTo(6);
    switch (pick) {
      case 4:
        return ElementImpl{l->getBottom()};
      case 5:
        return ElementImpl{l->getTop()};
      default:
        return ElementImpl{l->get(std::move(pick))};
    }
  }
  if (const auto* l = std::get_if<Lift<RandomLattice>>(lattice.get())) {
    return ElementImpl{rand.oneIn(4) ? l->getBottom()
                                     : l->get(l->lattice.makeElement())};
  }
  if (const auto* l = std::get_if<ArrayLattice>(lattice.get())) {
    return ElementImpl{typename ArrayLattice::Element{
      l->lattice.makeElement(), l->lattice.makeElement()}};
  }
  if (const auto* l = std::get_if<Vector<RandomLattice>>(lattice.get())) {
    std::vector<typename RandomLattice::Element> elem;
    elem.reserve(l->size);
    for (size_t i = 0; i < l->size; ++i) {
      elem.push_back(l->lattice.makeElement());
    }
    return ElementImpl{std::move(elem)};
  }
  if (const auto* l = std::get_if<TupleLattice>(lattice.get())) {
    return ElementImpl{
      typename TupleLattice::Element{std::get<0>(l->lattices).makeElement(),
                                     std::get<1>(l->lattices).makeElement()}};
  }
  if (const auto* l = std::get_if<SharedPath<RandomLattice>>(lattice.get())) {
    auto elem = l->getBottom();
    l->join(elem, l->lattice.makeElement());
    return ElementImpl{elem};
  }
  WASM_UNREACHABLE("unexpected lattice");
}

void indent(std::ostream& os, int depth) {
  for (int i = 0; i < depth; ++i) {
    os << "  ";
  }
}

void printFullElement(std::ostream& os,
                      const typename RandomFullLattice::Element& elem,
                      int depth) {
  indent(os, depth);

  if (const auto* e = std::get_if<typename Bool::Element>(&*elem)) {
    os << (*e ? "true" : "false") << "\n";
  } else if (const auto* e = std::get_if<typename UInt32::Element>(&*elem)) {
    os << *e << "\n";
  } else if (const auto* e = std::get_if<typename ValType::Element>(&*elem)) {
    os << *e << "\n";
  } else if (const auto* e =
               std::get_if<typename Inverted<RandomFullLattice>::Element>(
                 &*elem)) {
    os << "Inverted(\n";
    printFullElement(os, *e, depth + 1);
    indent(os, depth);
    os << ")\n";
  } else if (const auto* e =
               std::get_if<typename ArrayFullLattice::Element>(&*elem)) {
    os << "Array[\n";
    printFullElement(os, e->front(), depth + 1);
    printFullElement(os, e->back(), depth + 1);
    indent(os, depth);
    os << "]\n";
  } else if (const auto* vec =
               std::get_if<typename Vector<RandomFullLattice>::Element>(
                 &*elem)) {
    os << "Vector[\n";
    for (const auto& e : *vec) {
      printFullElement(os, e, depth + 1);
    }
    indent(os, depth);
    os << "]\n";
  } else if (const auto* e =
               std::get_if<typename TupleFullLattice::Element>(&*elem)) {
    os << "Tuple(\n";
    const auto& [first, second] = *e;
    printFullElement(os, first, depth + 1);
    printFullElement(os, second, depth + 1);
    indent(os, depth);
    os << ")\n";
  } else {
    WASM_UNREACHABLE("unexpected element");
  }
}

void printElement(std::ostream& os,
                  const typename RandomLattice::Element& elem,
                  int depth = 0) {
  if (const auto* e =
        std::get_if<typename RandomFullLattice::Element>(&*elem)) {
    printFullElement(os, *e, depth);
    return;
  }

  indent(os, depth);

  if (const auto* e = std::get_if<typename Flat<uint32_t>::Element>(&*elem)) {
    if (e->isBottom()) {
      os << "flat bot\n";
    } else if (e->isTop()) {
      os << "flat top\n";
    } else {
      os << "flat " << *e->getVal() << "\n";
    }
  } else if (const auto* e =
               std::get_if<typename Lift<RandomLattice>::Element>(&*elem)) {
    if (e->isBottom()) {
      os << "lift bot\n";
    } else {
      os << "Lifted(\n";
      printElement(os, **e, depth + 1);
      indent(os, depth);
      os << ")\n";
    }
  } else if (const auto* e =
               std::get_if<typename ArrayLattice::Element>(&*elem)) {
    os << "Array[\n";
    printElement(os, e->front(), depth + 1);
    printElement(os, e->back(), depth + 1);
    indent(os, depth);
    os << ")\n";
  } else if (const auto* vec =
               std::get_if<typename Vector<RandomLattice>::Element>(&*elem)) {
    os << "Vector[\n";
    for (const auto& e : *vec) {
      printElement(os, e, depth + 1);
    }
    indent(os, depth);
    os << "]\n";
  } else if (const auto* e =
               std::get_if<typename TupleLattice::Element>(&*elem)) {
    os << "Tuple(\n";
    const auto& [first, second] = *e;
    printElement(os, first, depth + 1);
    printElement(os, second, depth + 1);
    indent(os, depth);
    os << ")\n";
  } else if (const auto* e =
               std::get_if<typename SharedPath<RandomLattice>::Element>(
                 &*elem)) {
    os << "SharedPath(\n";
    printElement(os, **e, depth + 1);
    indent(os, depth);
    os << ")\n";
  } else {
    WASM_UNREACHABLE("unexpected element");
  }
}

std::ostream& operator<<(std::ostream& os,
                         const typename RandomLattice::Element& elem) {
  printElement(os, elem);
  return os;
}

// Check that random lattices have the correct mathematical properties by
// checking the relationships between random elements.
void checkLatticeProperties(Random& rand, bool verbose) {
  RandomLattice lattice(rand);

  // Generate the lattice elements we will perform checks on.
  typename RandomLattice::Element elems[3] = {
    lattice.makeElement(), lattice.makeElement(), lattice.makeElement()};

  if (verbose) {
    std::cout << "Random lattice elements:\n"
              << elems[0] << "\n"
              << elems[1] << "\n"
              << elems[2];
  }

  // Calculate the relations between the generated elements.
  LatticeComparison relation[3][3];
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      relation[i][j] = lattice.compare(elems[i], elems[j]);
    }
  }

  // Reflexivity: x == x
  for (int i = 0; i < 3; ++i) {
    if (lattice.compare(elems[i], elems[i]) != EQUAL) {
      Fatal() << "Lattice element is not reflexive:\n" << elems[i];
    }
  }

  // Anti-symmetry: x < y implies y > x, etc.
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      auto forward = relation[i][j];
      auto reverse = relation[j][i];
      if (reverseComparison(forward) != reverse) {
        Fatal()
          << "Lattice elements are not anti-symmetric.\nFirst element:\n\n"
          << elems[i] << "\nSecond element:\n\n"
          << elems[j]
          << "\nForward relation: " << LatticeComparisonNames[forward]
          << "\nReverse relation: " << LatticeComparisonNames[reverse] << "\n";
      }
    }
  }

  // Transitivity: x < y and y < z imply x < z, etc.
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        auto ij = relation[i][j], jk = relation[j][k], ik = relation[i][k];
        if (ij == NO_RELATION || jk == NO_RELATION) {
          continue;
        }
        if ((ij == LESS && jk == GREATER) || (ij == GREATER && jk == LESS)) {
          continue;
        }
        auto expected = ij == EQUAL ? jk : ij;
        if (ik != expected) {
          Fatal() << "Lattice elements are not transitive.\nFrist element:\n\n"
                  << elems[i] << "\nSecond element:\n\n"
                  << elems[j] << "\nThird element:\n\n"
                  << elems[k] << "\nFirst to second relation: "
                  << LatticeComparisonNames[ij]
                  << "\nSecond to third relation: "
                  << LatticeComparisonNames[jk]
                  << "\nFirst to thrid relation: " << LatticeComparisonNames[ik]
                  << "\n";
        }
      }
    }
  }

  // Joins (i.e. least upper bounds)
  for (int i = 0; i < 3; ++i) {
    {
      // Identity: elem u bot = elem
      auto join = elems[i];
      lattice.join(join, lattice.getBottom());
      if (lattice.compare(join, elems[i]) != EQUAL) {
        Fatal()
          << "Join of element and bottom is not equal to element:\nElement:\n\n"
          << elems[i] << "\nJoin:\n\n"
          << join;
      }
    }
    {
      // Identity: bot u elem = elem
      auto join = lattice.getBottom();
      lattice.join(join, elems[i]);
      if (lattice.compare(join, elems[i]) != EQUAL) {
        Fatal()
          << "Join of bottom and element is not equal to element:\nElement:\n\n"
          << elems[i] << "\nJoin:\n\n"
          << join;
      }
    }
    {
      // Identity: elem u elem = elem
      auto join = elems[i];
      lattice.join(join, elems[i]);
      if (lattice.compare(join, elems[i]) != EQUAL) {
        Fatal()
          << "Join of element with itself  equal to element:\nElement:\n\n"
          << elems[i] << "\nJoin:\n\n"
          << join;
      }
    }
    for (int j = 0; j < 3; ++j) {
      // Commutativity: x u y = y u x
      auto ij = elems[i];
      bool ijModified = lattice.join(ij, elems[j]);
      auto ji = elems[j];
      bool jiModified = lattice.join(ji, elems[i]);
      if (lattice.compare(ij, ji) != EQUAL) {
        Fatal() << "Join is not commutative:\nFirst element:\n\n"
                << elems[i] << "\nSecond element:\n\n"
                << elems[j] << "\nJoin(first, second):\n\n"
                << ij << "\nJoin(second, first):\n\n"
                << ji;
      }

      // Identity: x < y implies x u y = y
      if (relation[i][j] == LESS) {
        if (lattice.compare(ij, elems[j]) != EQUAL) {
          Fatal()
            << "Join is not equal to greater element:\nLesser element:\n\n"
            << elems[i] << "\nGreater element:\n\n"
            << elems[j] << "\nJoin:\n\n"
            << ij;
        }
        if (jiModified) {
          Fatal()
            << "Join incorrectly reported modification:\nLesser element:\n\n"
            << elems[i] << "\nGreater element:\n\n"
            << elems[j];
        }
        if (!ijModified) {
          Fatal()
            << "Join should have reported modification:\nLesser element:\n\n"
            << elems[i] << "\nGreater element:\n\n"
            << elems[j];
        }
      }

      for (int k = 0; k < 3; ++k) {
        // *Least* upper bound: x <= z && y <= z implies x u y <= z
        if (relation[i][k] == LESS && relation[j][k] == LESS) {
          auto IJtoK = lattice.compare(ij, elems[k]);
          if (IJtoK != EQUAL && IJtoK != LESS) {
            Fatal() << "Join is not least upper bound:\nFirst element:\n\n"
                    << elems[i] << "\nSecond element:\n\n"
                    << elems[j] << "\nJoin:\n\n"
                    << ij << "\nOther upper bound:\n\n"
                    << elems[k];
          }
        }
      }
    }
  }
}

// Utility class which provides methods to check properties of the transfer
// function and lattice of an analysis.
template<Lattice L, TransferFunction TxFn> struct AnalysisChecker {
  L& lattice;
  TxFn& txfn;
  std::string latticeName;
  std::string txfnName;
  uint64_t latticeElementSeed;
  Name funcName;

  AnalysisChecker(L& lattice,
                  TxFn& txfn,
                  std::string latticeName,
                  std::string txfnName,
                  uint64_t latticeElementSeed,
                  Name funcName)
    : lattice(lattice), txfn(txfn), latticeName(latticeName),
      txfnName(txfnName), latticeElementSeed(latticeElementSeed),
      funcName(funcName) {}

  void printFailureInfo(std::ostream& os) {
    os << "Error for " << txfnName << " and " << latticeName
       << " at lattice element seed " << latticeElementSeed << " and function "
       << funcName << ".\n";
  }

  // Prints information about a particular test case consisting of a randomly
  // generated function and triple of randomly generate lattice elements.
  void printVerboseFunctionCase(std::ostream& os,
                                typename L::Element& x,
                                typename L::Element& y,
                                typename L::Element& z) {
    os << "Using lattice element seed " << latticeElementSeed << "\nGenerated "
       << latticeName << " elements:\n";
    x.print(os);
    os << ",\n";
    y.print(os);
    os << ",\n";
    z.print(os);
    os << "\nfor " << funcName << " to test " << txfnName << ".\n\n";
  }

public:
  // Given two input - output lattice pairs of a transfer function, checks if
  // the transfer function is monotonic. If this is violated, then we print out
  // the CFG block input which caused the transfer function to exhibit
  // non-monotonic behavior.
  void checkMonotonicity(const BasicBlock& bb,
                         typename L::Element& first,
                         typename L::Element& second,
                         typename L::Element& firstResult,
                         typename L::Element& secondResult) {
    LatticeComparison beforeCmp = lattice.compare(first, second);
    LatticeComparison afterCmp = lattice.compare(firstResult, secondResult);

    // Cases in which monotonicity is preserved.
    if (beforeCmp == LatticeComparison::NO_RELATION) {
      // If there is no relation in the first place, we can't expect anything.
      return;
    } else if (beforeCmp == LatticeComparison::LESS &&
               (afterCmp == LatticeComparison::LESS ||
                afterCmp == LatticeComparison::EQUAL)) {
      // x < y and f(x) <= f(y)
      return;
    } else if (beforeCmp == LatticeComparison::GREATER &&
               (afterCmp == LatticeComparison::GREATER ||
                afterCmp == LatticeComparison::EQUAL)) {
      // x > y and f(x) >= f(y)
      return;
    } else if (beforeCmp == LatticeComparison::EQUAL &&
               afterCmp == LatticeComparison::EQUAL) {
      // x = y and f(x) = f(y)
      return;
    }

    std::stringstream ss;
    printFailureInfo(ss);

    ss << "Elements ";
    first.print(ss);
    ss << " -> ";
    firstResult.print(ss);
    ss << " and ";
    second.print(ss);
    ss << " -> ";
    secondResult.print(ss);
    ss << "\n show that the transfer function is not monotone when given the "
          "input:\n";
    bb.print(ss);
    ss << "\n";

    Fatal() << ss.str();
  }

  // Checks transfer function relevant properties given a CFG and three input
  // states. It does this by applying the transfer function on each CFG block
  // using the same three input states each time and then checking properties on
  // the inputs and outputs.
  void checkTransferFunction(CFG& cfg,
                             typename L::Element x,
                             typename L::Element y,
                             typename L::Element z) {
    for (const auto& bb : cfg) {
      // Apply transfer function on each lattice element.
      auto xResult = x;
      txfn.transfer(bb, xResult);
      auto yResult = y;
      txfn.transfer(bb, yResult);
      auto zResult = z;
      txfn.transfer(bb, zResult);

      // Check monotonicity for every pair of transfer function outputs.
      checkMonotonicity(bb, x, y, xResult, yResult);
      checkMonotonicity(bb, x, z, xResult, zResult);
      checkMonotonicity(bb, y, z, yResult, zResult);
    }
  }
};

// Struct to set up and check liveness analysis lattice and transfer function.
struct LivenessChecker {
  LivenessTransferFunction txfn;
  FiniteIntPowersetLattice lattice;
  AnalysisChecker<FiniteIntPowersetLattice, LivenessTransferFunction> checker;
  LivenessChecker(Function* func, uint64_t latticeElementSeed, Name funcName)
    : lattice(func->getNumLocals()), checker(lattice,
                                             txfn,
                                             "FiniteIntPowersetLattice",
                                             "LivenessTransferFunction",
                                             latticeElementSeed,
                                             funcName) {}

  FiniteIntPowersetLattice::Element getRandomElement(Random& rand) {
    FiniteIntPowersetLattice::Element result = lattice.getBottom();

    // Uses rand to randomly select which members are to be included (i. e. flip
    // bits in the bitvector).
    for (size_t i = 0; i < lattice.getSetSize(); ++i) {
      result.set(i, rand.oneIn(2));
    }
    return result;
  }

  // Runs all checks for liveness analysis.
  void runChecks(CFG& cfg, Random& rand, bool verbose) {
    FiniteIntPowersetLattice::Element x = getRandomElement(rand);
    FiniteIntPowersetLattice::Element y = getRandomElement(rand);
    FiniteIntPowersetLattice::Element z = getRandomElement(rand);

    if (verbose) {
      checker.printVerboseFunctionCase(std::cout, x, y, z);
    }

    checker.checkTransferFunction(cfg, x, y, z);
  }
};

// Struct to set up and check reaching definitions analysis lattice and transfer
// function.
struct ReachingDefinitionsChecker {
  LocalGraph::GetSetsMap getSetsMap;
  LocalGraph::Locations locations;
  ReachingDefinitionsTransferFunction txfn;
  AnalysisChecker<FinitePowersetLattice<LocalSet*>,
                  ReachingDefinitionsTransferFunction>
    checker;
  ReachingDefinitionsChecker(Function* func,
                             uint64_t latticeElementSeed,
                             Name funcName)
    : txfn(func, getSetsMap, locations),
      checker(txfn.lattice,
              txfn,
              "FinitePowersetLattice<LocalSet*>",
              "ReachingDefinitionsTransferFunction",
              latticeElementSeed,
              funcName) {}

  FinitePowersetLattice<LocalSet*>::Element getRandomElement(Random& rand) {
    FinitePowersetLattice<LocalSet*>::Element result = txfn.lattice.getBottom();

    // Uses rand to randomly select which members are to be included (i. e. flip
    // bits in the bitvector).
    for (size_t i = 0; i < txfn.lattice.getSetSize(); ++i) {
      result.set(i, rand.oneIn(2));
    }
    return result;
  }

  // Runs all checks for reaching definitions analysis.
  void runChecks(CFG& cfg, Random& rand, bool verbose) {
    FinitePowersetLattice<LocalSet*>::Element x = getRandomElement(rand);
    FinitePowersetLattice<LocalSet*>::Element y = getRandomElement(rand);
    FinitePowersetLattice<LocalSet*>::Element z = getRandomElement(rand);

    if (verbose) {
      checker.printVerboseFunctionCase(std::cout, x, y, z);
    }

    checker.checkTransferFunction(cfg, x, y, z);
  }
};

// Uninteresting implementation details for RandomFullLattice and RandomLattice.

RandomFullLattice::Element RandomFullLattice::getBottom() const noexcept {
  return std::visit(
    [](const auto& l) -> Element { return ElementImpl{l.getBottom()}; },
    (const FullLatticeVariant&)*lattice);
}

RandomFullLattice::Element RandomFullLattice::getTop() const noexcept {
  return std::visit(
    [](const auto& l) -> Element { return ElementImpl{l.getTop()}; },
    (const FullLatticeVariant&)*lattice);
}

// TODO: use std::remove_cvref_t from C++20 instead.
template<typename T> using bare = std::remove_cv_t<std::remove_reference_t<T>>;

LatticeComparison RandomFullLattice::compare(const Element& a,
                                             const Element& b) const noexcept {
  return std::visit(
    [](const auto& l,
       const auto& elemA,
       const auto& elemB) -> LatticeComparison {
      using ElemT = typename bare<decltype(l)>::Element;
      using A = bare<decltype(elemA)>;
      using B = bare<decltype(elemB)>;
      if constexpr (std::is_same_v<ElemT, A> && std::is_same_v<ElemT, B>) {
        return l.compare(elemA, elemB);
      }
      WASM_UNREACHABLE("unexpected element types");
    },
    (const FullLatticeVariant&)*lattice,
    (const FullLatticeElementVariant&)*a,
    (const FullLatticeElementVariant&)*b);
}

bool RandomFullLattice::join(Element& a, const Element& b) const noexcept {
  return std::visit(
    [](const auto& l, auto& elemA, const auto& elemB) -> bool {
      using ElemT = typename bare<decltype(l)>::Element;
      using A = bare<decltype(elemA)>;
      using B = bare<decltype(elemB)>;
      if constexpr (std::is_same_v<ElemT, A> && std::is_same_v<ElemT, B>) {
        return l.join(elemA, elemB);
      }
      WASM_UNREACHABLE("unexpected element types");
    },
    (const FullLatticeVariant&)*lattice,
    (FullLatticeElementVariant&)*a,
    (const FullLatticeElementVariant&)*b);
}

bool RandomFullLattice::meet(Element& a, const Element& b) const noexcept {
  return std::visit(
    [](const auto& l, auto& elemA, const auto& elemB) -> bool {
      using ElemT = typename bare<decltype(l)>::Element;
      using A = bare<decltype(elemA)>;
      using B = bare<decltype(elemB)>;
      if constexpr (std::is_same_v<ElemT, A> && std::is_same_v<ElemT, B>) {
        return l.meet(elemA, elemB);
      }
      WASM_UNREACHABLE("unexpected element types");
    },
    (const FullLatticeVariant&)*lattice,
    (FullLatticeElementVariant&)*a,
    (const FullLatticeElementVariant&)*b);
}

RandomLattice::Element RandomLattice::getBottom() const noexcept {
  return std::visit(
    [](const auto& l) -> Element { return ElementImpl{l.getBottom()}; },
    (const LatticeVariant&)*lattice);
}

LatticeComparison RandomLattice::compare(const Element& a,
                                         const Element& b) const noexcept {
  return std::visit(
    [](const auto& l,
       const auto& elemA,
       const auto& elemB) -> LatticeComparison {
      using ElemT = typename bare<decltype(l)>::Element;
      using A = bare<decltype(elemA)>;
      using B = bare<decltype(elemB)>;
      if constexpr (std::is_same_v<ElemT, A> && std::is_same_v<ElemT, B>) {
        return l.compare(elemA, elemB);
      }
      WASM_UNREACHABLE("unexpected element types");
    },
    (const LatticeVariant&)*lattice,
    (const LatticeElementVariant&)*a,
    (const LatticeElementVariant&)*b);
}

bool RandomLattice::join(Element& a, const Element& b) const noexcept {
  return std::visit(
    [](const auto& l, auto& elemA, const auto& elemB) -> bool {
      using ElemT = typename bare<decltype(l)>::Element;
      using A = bare<decltype(elemA)>;
      using B = bare<decltype(elemB)>;
      if constexpr (std::is_same_v<ElemT, A> && std::is_same_v<ElemT, B>) {
        return l.join(elemA, elemB);
      }
      WASM_UNREACHABLE("unexpected element types");
    },
    (const LatticeVariant&)*lattice,
    (LatticeElementVariant&)*a,
    (const LatticeElementVariant&)*b);
}

// The main entry point.
struct Fuzzer {
  bool verbose;

  Fuzzer(bool verbose) : verbose(verbose) {}

  // Helper function to run per-function tests. latticeElementSeed is used to
  // generate three lattice elements randomly. It is also used to select which
  // analysis is to be tested for the function.
  void runOnFunction(Function* func, uint64_t latticeElementSeed) {
    RandEngine getFuncRand(latticeElementSeed);

    // Fewer bytes are needed to generate three random lattices.
    std::vector<char> funcBytes(128);
    for (size_t i = 0; i < funcBytes.size(); i += sizeof(uint64_t)) {
      *(uint64_t*)(funcBytes.data() + i) = getFuncRand();
    }

    Random rand(std::move(funcBytes));
    checkLatticeProperties(rand, verbose);

    CFG cfg = CFG::fromFunction(func);

    switch (rand.upTo(2)) {
      case 0: {
        LivenessChecker livenessChecker(func, latticeElementSeed, func->name);
        livenessChecker.runChecks(cfg, rand, verbose);
        break;
      }
      case 1: {
        ReachingDefinitionsChecker reachingDefinitionsChecker(
          func, latticeElementSeed, func->name);
        reachingDefinitionsChecker.runChecks(cfg, rand, verbose);
        break;
      }
    }
  }

  // Generates a module. The module is used as an input to fuzz transfer
  // functions as well as randomly generated lattice element states. Lattice
  // properties are also fuzzed from the randomly generated states.
  void run(uint64_t seed,
           uint64_t* latticeElementSeed = nullptr,
           std::string* funcName = nullptr) {
    RandEngine getRand(seed);
    std::cout << "Running with seed " << seed << "\n";

    // 4kb of random bytes should be enough for anyone!
    std::vector<char> bytes(4096);
    for (size_t i = 0; i < bytes.size(); i += sizeof(uint64_t)) {
      *(uint64_t*)(bytes.data() + i) = getRand();
    }

    Module testModule;
    TranslateToFuzzReader reader(testModule, std::move(bytes));
    reader.build();

    if (verbose) {
      std::cout << "Generated test module: \n";
      std::cout << testModule;
      std::cout << "\n";
    }

    // If a specific function and lattice element seed is specified, only run
    // that.
    if (latticeElementSeed && funcName) {
      runOnFunction(testModule.getFunction(*funcName), *latticeElementSeed);
      return;
    }

    ModuleUtils::iterDefinedFunctions(testModule, [&](Function* func) {
      uint64_t funcSeed = getRand();
      runOnFunction(func, funcSeed);
    });
  }
};

} // namespace wasm

int main(int argc, const char* argv[]) {
  using namespace wasm;

  const std::string WasmFuzzTypesOption = "wasm-fuzz-lattices options";

  Options options("wasm-fuzz-lattices",
                  "Fuzz lattices for reflexivity, transitivity, and "
                  "anti-symmetry, and tranfer functions for monotonicity.");

  std::optional<uint64_t> seed;
  options.add("--seed",
              "",
              "Run a single workload generated by the given seed",
              WasmFuzzTypesOption,
              Options::Arguments::One,
              [&](Options*, const std::string& arg) {
                seed = uint64_t(std::stoull(arg));
              });

  std::optional<uint64_t> latticeElementSeed;
  options.add("--lattice-element-seed",
              "",
              "Seed which generated the lattice elements to be checked.",
              WasmFuzzTypesOption,
              Options::Arguments::One,
              [&](Options*, const std::string& arg) {
                latticeElementSeed = uint64_t(std::stoull(arg));
              });

  std::optional<std::string> functionName;
  options.add(
    "--function-name",
    "",
    "Name of the function in the module generated by --seed to be checked.",
    WasmFuzzTypesOption,
    Options::Arguments::One,
    [&](Options*, const std::string& arg) { functionName = arg; });

  bool verbose = false;
  options.add("--verbose",
              "-v",
              "Print extra information",
              WasmFuzzTypesOption,
              Options::Arguments::Zero,
              [&](Options*, const std::string& arg) { verbose = true; });

  options.parse(argc, argv);

  Fuzzer fuzzer{verbose};
  if (seed) {
    if (latticeElementSeed && functionName) {
      // Run test a single function and lattice element seed.
      fuzzer.run(*seed, &(*latticeElementSeed), &(*functionName));
    } else {
      // Run just a single workload with the given seed.
      fuzzer.run(*seed);
    }
  } else {
    // Continuously run workloads with new randomly generated seeds.
    size_t i = 0;
    RandEngine nextSeed(getSeed());
    while (true) {
      std::cout << "Iteration " << ++i << "\n";
      fuzzer.run(nextSeed());
    }
  }
  return 0;
}