6 files changed, 714 insertions, 39 deletions

diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 1f745f1ee..84b0e2c5c 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -1,53 +1,35 @@
+/*
+ * Copyright 2021 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 "tools/fuzzing.h"
+#include "tools/fuzzing/heap-types.h"
+#include "tools/fuzzing/parameters.h"
 
 namespace wasm {
 
-// Constants that control fuzzing.
 namespace {
-// The maximum amount of params to each function.
-constexpr int MAX_PARAMS = 10;
-
-// The maximum amount of vars in each function.
-constexpr int MAX_VARS = 20;
-
-// The maximum number of globals in a module.
-constexpr int MAX_GLOBALS = 20;
-
-// The maximum number of tuple elements.
-constexpr int MAX_TUPLE_SIZE = 6;
-
-// The maximum rtt depth.
-constexpr int MAX_RTT_DEPTH = 3;
-
-// some things require luck, try them a few times
-constexpr int TRIES = 10;
-
-// beyond a nesting limit, greatly decrease the chance to continue to nest
-constexpr int NESTING_LIMIT = 11;
-
-// the maximum size of a block
-constexpr int BLOCK_FACTOR = 5;
-
-// the memory that we use, a small portion so that we have a good chance of
-// looking at writes (we also look outside of this region with small
-// probability) this should be a power of 2
-constexpr Address USABLE_MEMORY = 16;
-
-// the number of runtime iterations (function calls, loop backbranches) we
-// allow before we stop execution with a trap, to prevent hangs. 0 means
-// no hang protection.
-constexpr int HANG_LIMIT = 10;
 
 // Weighting for the core make* methods. Some nodes are important enough that
 // we should do them quite often.
-constexpr size_t VeryImportant = 4;
-constexpr size_t Important = 2;
 
 } // anonymous namespace
 
 TranslateToFuzzReader::TranslateToFuzzReader(Module& wasm,
                                              std::vector<char>&& input)
-  : wasm(wasm), builder(wasm), random(std::move(input)) {
+  : wasm(wasm), builder(wasm), random(std::move(input), wasm.features) {
   // - funcref cannot be logged because referenced functions can be inlined or
   // removed during optimization
   // - there's no point in logging externref or anyref because these are opaque
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
new file mode 100644
index 000000000..71f701860
--- /dev/null
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -0,0 +1,499 @@
+/*
+ * Copyright 2021 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 <variant>
+
+#include "tools/fuzzing/heap-types.h"
+#include "tools/fuzzing/parameters.h"
+
+namespace wasm {
+
+namespace {
+
+struct HeapTypeGenerator {
+  Random& rand;
+  FeatureSet features;
+  TypeBuilder builder;
+
+  // Map the HeapTypes we are building to their indices in the builder.
+  std::unordered_map<HeapType, Index> typeIndices;
+
+  // For each type we will build, the indices of its subtypes we will build.
+  std::vector<std::vector<Index>> subtypeIndices;
+
+  // Abstract over all the types that may be assigned to a builder slot.
+  using Assignable =
+    std::variant<HeapType::BasicHeapType, Signature, Struct, Array>;
+
+  // Top-level kinds, chosen before the types are actually constructed. This
+  // allows us to choose HeapTypes that we know will be subtypes of data or func
+  // before we actually generate the types.
+  using BasicKind = HeapType::BasicHeapType;
+  struct SignatureKind {};
+  struct DataKind {};
+  using HeapTypeKind = std::variant<BasicKind, SignatureKind, DataKind>;
+  std::vector<HeapTypeKind> typeKinds;
+
+  HeapTypeGenerator(Random& rand, FeatureSet features, size_t n)
+    : rand(rand), features(features), builder(n), subtypeIndices(n) {}
+
+  HeapType::BasicHeapType generateBasicHeapType() {
+    return rand.pick(HeapType::func,
+                     HeapType::ext,
+                     HeapType::any,
+                     HeapType::eq,
+                     HeapType::i31,
+                     HeapType::data);
+  }
+
+  Type::BasicType generateBasicType() {
+    return rand.pick(
+      Random::FeatureOptions<Type::BasicType>{}
+        .add(FeatureSet::MVP, Type::i32, Type::i64, Type::f32, Type::f64)
+        .add(FeatureSet::SIMD, Type::v128)
+        .add(FeatureSet::ReferenceTypes | FeatureSet::GC,
+             Type::funcref,
+             Type::externref,
+             Type::anyref,
+             Type::eqref,
+             Type::i31ref,
+             Type::dataref));
+  }
+
+  HeapType generateHeapType() {
+    if (rand.oneIn(4)) {
+      return generateBasicHeapType();
+    } else {
+      return builder[rand.upTo(builder.size())];
+    }
+  }
+
+  // TODO: Create an enum for `Defaultable, NonDefaultable` in wasm-type.h.
+  Type generateRefType(bool defaultable = false) {
+    auto heapType = generateHeapType();
+    auto nullability = (defaultable || rand.oneIn(2)) ? Nullable : NonNullable;
+    return builder.getTempRefType(heapType, nullability);
+  }
+
+  Type generateRttType() {
+    auto heapType = generateHeapType();
+    auto depth = rand.oneIn(2) ? Rtt::NoDepth : rand.upTo(MAX_RTT_DEPTH);
+    return builder.getTempRttType(Rtt(depth, heapType));
+  }
+
+  Type generateSingleType(bool defaultable = false) {
+    switch (rand.upTo(defaultable ? 2 : 3)) {
+      case 0:
+        return generateBasicType();
+      case 1:
+        return generateRefType(defaultable);
+      case 2:
+        return generateRttType();
+    }
+    WASM_UNREACHABLE("unexpected");
+  }
+
+  Type generateTupleType() {
+    std::vector<Type> types(2 + rand.upTo(MAX_TUPLE_SIZE - 1));
+    for (auto& type : types) {
+      // Make sure tuples are defaultable. See comment in
+      // TranslateToFuzzReader::getTupleType.
+      type = generateSingleType(/*defaultable=*/true);
+    }
+    return builder.getTempTupleType(Tuple(types));
+  }
+
+  Type generateReturnType() {
+    // This is similar to TranslateToFuzzreader::getControlFlowType.
+    if (rand.oneIn(10)) {
+      return Type::none;
+    } else if (features.hasMultivalue() && rand.oneIn(5)) {
+      return generateTupleType();
+    } else {
+      return generateSingleType(/*defaultable=*/true);
+    }
+  }
+
+  Signature generateSignature() {
+    std::vector<Type> types(rand.upToSquared(MAX_PARAMS));
+    for (auto& type : types) {
+      type = generateSingleType();
+    }
+    auto params = builder.getTempTupleType(types);
+    return {params, generateReturnType()};
+  }
+
+  Field generateField() {
+    auto mutability = rand.oneIn(2) ? Mutable : Immutable;
+    if (rand.oneIn(6)) {
+      return {rand.oneIn(2) ? Field::i8 : Field::i16, mutability};
+    } else {
+      return {generateSingleType(), mutability};
+    }
+  }
+
+  Struct generateStruct() {
+    std::vector<Field> fields(rand.upTo(MAX_STRUCT_SIZE + 1));
+    for (auto& field : fields) {
+      field = generateField();
+    }
+    return {fields};
+  }
+
+  Array generateArray() { return {generateField()}; }
+
+  Assignable generateSubData() {
+    switch (rand.upTo(2)) {
+      case 0:
+        return generateStruct();
+      case 1:
+        return generateArray();
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  Assignable generateSubEq() {
+    switch (rand.upTo(3)) {
+      case 0:
+        return HeapType::i31;
+      case 1:
+        return HeapType::data;
+      case 2:
+        return generateSubData();
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  Assignable generateSubAny() {
+    switch (rand.upTo(4)) {
+      case 0:
+        return HeapType::eq;
+      case 1:
+        return HeapType::func;
+      case 2:
+        return generateSubEq();
+      case 3:
+        return generateSignature();
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  Assignable generateSubBasic(HeapType::BasicHeapType type) {
+    if (rand.oneIn(2)) {
+      return type;
+    } else {
+      switch (type) {
+        case HeapType::ext:
+        case HeapType::i31:
+          // No other subtypes.
+          return type;
+        case HeapType::func:
+          return generateSignature();
+        case HeapType::any:
+          return generateSubAny();
+        case HeapType::eq:
+          return generateSubEq();
+        case HeapType::data:
+          return generateSubData();
+      }
+      WASM_UNREACHABLE("unexpected index");
+    }
+  }
+
+  template<typename Kind> std::optional<HeapType> pickKind() {
+    std::vector<HeapType> candidates;
+    // Iterate through the top level kinds, finding matches for `Kind`.
+    for (Index i = 0; i < typeKinds.size(); ++i) {
+      if (std::get_if<Kind>(&typeKinds[i])) {
+        candidates.push_back(builder[i]);
+      }
+    }
+    if (candidates.size()) {
+      return rand.pick(candidates);
+    } else {
+      return {};
+    }
+  }
+
+  HeapType pickSubFunc() {
+    if (auto type = pickKind<SignatureKind>()) {
+      return *type;
+    } else {
+      return HeapType::func;
+    }
+  }
+
+  HeapType pickSubData() {
+    if (auto type = pickKind<DataKind>()) {
+      return *type;
+    } else {
+      return HeapType::data;
+    }
+  }
+
+  HeapType pickSubEq() {
+    if (rand.oneIn(2)) {
+      return HeapType::i31;
+    } else {
+      return pickSubData();
+    }
+  }
+
+  HeapType pickSubAny() {
+    switch (rand.upTo(4)) {
+      case 0:
+        return HeapType::func;
+      case 1:
+        return HeapType::eq;
+      case 2:
+        return pickSubFunc();
+      case 3:
+        return pickSubEq();
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  HeapType pickSubHeapType(HeapType type) {
+    auto it = typeIndices.find(type);
+    if (it != typeIndices.end()) {
+      // This is a constructed type, so we know where its subtypes are.
+      return builder[rand.pick(subtypeIndices[typeIndices[type]])];
+    } else {
+      // This is not a constructed type, so it must be a basic type.
+      assert(type.isBasic());
+      switch (type.getBasic()) {
+        case HeapType::func:
+          return pickSubFunc();
+        case HeapType::ext:
+          return HeapType::ext;
+        case HeapType::any:
+          return pickSubAny();
+        case HeapType::eq:
+          return pickSubEq();
+        case HeapType::i31:
+          return HeapType::i31;
+        case HeapType::data:
+          return pickSubData();
+      }
+      WASM_UNREACHABLE("unexpected kind");
+    }
+  }
+
+  // TODO: Make this part of the wasm-type.h API
+  struct Ref {
+    HeapType type;
+    Nullability nullability;
+  };
+
+  Ref generateSubRef(Ref super) {
+    auto nullability = super.nullability == NonNullable
+                         ? NonNullable
+                         : rand.oneIn(2) ? Nullable : NonNullable;
+    return {pickSubHeapType(super.type), nullability};
+  }
+
+  Rtt generateSubRtt(Rtt super) {
+    auto depth = super.hasDepth()
+                   ? super.depth
+                   : rand.oneIn(2) ? Rtt::NoDepth : rand.upTo(MAX_RTT_DEPTH);
+    return {depth, super.heapType};
+  }
+
+  Type generateSubtype(Type type) {
+    if (type.isBasic()) {
+      // We do not construct types with basic reference types (we go through the
+      // TypeBuilder for those instead), so this must be a non-reference basic
+      // type, which means it has no other subtypes.
+      return type;
+    } else if (type.isRef()) {
+      auto ref = generateSubRef({type.getHeapType(), type.getNullability()});
+      return builder.getTempRefType(ref.type, ref.nullability);
+    } else if (type.isRtt()) {
+      auto rtt = generateSubRtt(type.getRtt());
+      return builder.getTempRttType(rtt);
+    } else {
+      WASM_UNREACHABLE("unexpected type kind");
+    }
+  }
+
+  Signature generateSubSignature(Signature super) {
+    // TODO: Update this once we support nontrivial function subtyping.
+    return super;
+  }
+
+  Field generateSubField(Field super) {
+    if (super.mutable_ == Mutable) {
+      // Only immutable fields support subtyping.
+      return super;
+    }
+    if (super.isPacked()) {
+      // No other subtypes of i8 or i16.
+      return super;
+    }
+    return {generateSubtype(super.type), Immutable};
+  }
+
+  Struct generateSubStruct(const Struct& super) {
+    if (rand.oneIn(2)) {
+      return super;
+    }
+    std::vector<Field> fields;
+    // Depth subtyping
+    for (auto field : super.fields) {
+      fields.push_back(generateSubField(field));
+    }
+    // Width subtyping
+    Index extra = rand.upTo(MAX_STRUCT_SIZE + 1 - fields.size());
+    for (Index i = 0; i < extra; ++i) {
+      fields.push_back(generateField());
+    }
+    return {fields};
+  }
+
+  Array generateSubArray(Array super) {
+    if (rand.oneIn(2)) {
+      return super;
+    }
+    return {generateSubField(super.element)};
+  }
+
+  HeapTypeKind generateHeapTypeKind() {
+    // Building basic heap types is only allowed in equirecursive mode.
+    // TODO: Relax this.
+    size_t options = 2;
+    if (getTypeSystem() == TypeSystem::Equirecursive) {
+      ++options;
+    }
+    switch (rand.upTo(options)) {
+      case 0:
+        return SignatureKind{};
+      case 1:
+        return DataKind{};
+      case 2:
+        return BasicKind{generateBasicHeapType()};
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  HeapTypeKind getSubKind(HeapTypeKind super) {
+    if (auto* basic = std::get_if<BasicKind>(&super)) {
+      if (rand.oneIn(8)) {
+        return super;
+      }
+      switch (*basic) {
+        case HeapType::func:
+          return SignatureKind{};
+        case HeapType::ext:
+        case HeapType::i31:
+          return super;
+        case HeapType::any:
+          return generateHeapTypeKind();
+        case HeapType::eq:
+          if (rand.oneIn(4)) {
+            return HeapType::i31;
+          } else {
+            return DataKind{};
+          }
+        case HeapType::data:
+          return DataKind{};
+      }
+      WASM_UNREACHABLE("unexpected kind");
+    } else {
+      // Signature and Data types can only have Signature and Data subtypes.
+      return super;
+    }
+  }
+
+  std::vector<HeapType> generate() {
+    // Set up the subtype relationships. Start with some number of root types,
+    // then after that start creating subtypes of existing types. Determine the
+    // top-level kind of each type in advance so that we can appropriately use
+    // types we haven't constructed yet.
+    // TODO: Determine individually whether each HeapType is nominal once
+    // mixing type systems is expected to work.
+    typeKinds.reserve(builder.size());
+    std::vector<std::optional<Index>> supertypeIndices(builder.size());
+    Index numRoots = 1 + rand.upTo(builder.size());
+    for (Index i = 0; i < builder.size(); ++i) {
+      typeIndices.insert({builder[i], i});
+      // Everything is a subtype of itself.
+      subtypeIndices[i].push_back(i);
+      if (i < numRoots) {
+        // This is a root type with no supertype. Choose a kind for this type.
+        typeKinds.emplace_back(generateHeapTypeKind());
+      } else {
+        // This is a subtype. Choose one of the previous types to be the
+        // supertype.
+        Index super = rand.upTo(i);
+        builder[i].subTypeOf(builder[super]);
+        supertypeIndices[i] = super;
+        subtypeIndices[super].push_back(i);
+        typeKinds.push_back(getSubKind(typeKinds[super]));
+      }
+    }
+
+    // Create the heap types.
+    for (Index i = 0; i < builder.size(); ++i) {
+      if (!supertypeIndices[i]) {
+        // Create a root type.
+        auto kind = typeKinds[i];
+        if (auto* basic = std::get_if<BasicKind>(&kind)) {
+          builder[i] = *basic;
+        } else if (std::get_if<SignatureKind>(&kind)) {
+          builder[i] = generateSignature();
+        } else if (std::get_if<DataKind>(&kind)) {
+          if (rand.oneIn(2)) {
+            builder[i] = generateStruct();
+          } else {
+            builder[i] = generateArray();
+          }
+        } else {
+          WASM_UNREACHABLE("unexpected kind");
+        }
+      } else {
+        // We have a supertype, so create a subtype.
+        Index super = *supertypeIndices[i];
+        HeapType supertype = builder[super];
+        if (builder.isBasic(super)) {
+          auto assignable = generateSubBasic(builder.getBasic(super));
+          std::visit([&](auto&& arg) { builder[i] = arg; }, assignable);
+        } else if (supertype.isSignature()) {
+          builder[i] = generateSubSignature(supertype.getSignature());
+        } else if (supertype.isStruct()) {
+          builder[i] = generateSubStruct(supertype.getStruct());
+        } else if (supertype.isArray()) {
+          builder[i] = generateSubArray(supertype.getArray());
+        } else {
+          WASM_UNREACHABLE("unexpected kind");
+        }
+      }
+    }
+    return builder.build();
+  }
+};
+
+} // anonymous namespace
+
+namespace HeapTypeFuzzer {
+
+std::vector<HeapType>
+generateHeapTypes(Random& rand, FeatureSet features, size_t n) {
+  return HeapTypeGenerator(rand, features, n).generate();
+}
+
+} // namespace HeapTypeFuzzer
+
+} // namespace wasm
diff --git a/src/tools/fuzzing/heap-types.h b/src/tools/fuzzing/heap-types.h
new file mode 100644
index 000000000..a9a580cf6
--- /dev/null
+++ b/src/tools/fuzzing/heap-types.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2021 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.
+ */
+
+#ifndef wasm_tools_fuzzing_heap_types_h
+#define wasm_tools_fuzzing_heap_types_h
+
+#include "tools/fuzzing/random.h"
+#include "wasm-type.h"
+#include <vector>
+
+namespace wasm::HeapTypeFuzzer {
+
+// Generate a vector of `n` random HeapTypes with interesting subtyping.
+std::vector<HeapType>
+generateHeapTypes(Random& rand, FeatureSet features, size_t n);
+
+} // namespace wasm::HeapTypeFuzzer
+
+#endif // wasm_tools_fuzzing_heap_types_h
diff --git a/src/tools/fuzzing/parameters.h b/src/tools/fuzzing/parameters.h
new file mode 100644
index 000000000..6618ce6db
--- /dev/null
+++ b/src/tools/fuzzing/parameters.h
@@ -0,0 +1,73 @@
+/*
+ * Copyright 2021 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.
+ */
+
+// Constants that control fuzzing.
+
+#ifndef wasm_tools_fuzzing_parameters_h
+#define wasm_tools_fuzzing_parameters_h
+
+#include "wasm.h"
+
+namespace wasm {
+
+// The maximum amount of params to each function.
+constexpr int MAX_PARAMS = 10;
+
+// The maximum amount of vars in each function.
+constexpr int MAX_VARS = 20;
+
+// The maximum number of globals in a module.
+constexpr int MAX_GLOBALS = 20;
+
+// The maximum number of tuple elements.
+constexpr int MAX_TUPLE_SIZE = 6;
+
+// The maximum number of struct fields.
+static const int MAX_STRUCT_SIZE = 6;
+
+// The maximum rtt depth.
+constexpr int MAX_RTT_DEPTH = 3;
+
+// The number of nontrivial heap types to generate.
+constexpr int MIN_HEAPTYPES = 4;
+constexpr int MAX_HEAPTYPES = 20;
+
+// some things require luck, try them a few times
+constexpr int TRIES = 10;
+
+// beyond a nesting limit, greatly decrease the chance to continue to nest
+constexpr int NESTING_LIMIT = 11;
+
+// the maximum size of a block
+constexpr int BLOCK_FACTOR = 5;
+
+// the memory that we use, a small portion so that we have a good chance of
+// looking at writes (we also look outside of this region with small
+// probability) this should be a power of 2
+constexpr Address USABLE_MEMORY = 16;
+
+// the number of runtime iterations (function calls, loop backbranches) we
+// allow before we stop execution with a trap, to prevent hangs. 0 means
+// no hang protection.
+constexpr int HANG_LIMIT = 10;
+
+//
+constexpr size_t VeryImportant = 4;
+constexpr size_t Important = 2;
+
+} // namespace wasm
+
+#endif // wasm_tools_fuzzing_parameters_h
diff --git a/src/tools/fuzzing/random.cpp b/src/tools/fuzzing/random.cpp
index 38a86924e..3d8297c15 100644
--- a/src/tools/fuzzing/random.cpp
+++ b/src/tools/fuzzing/random.cpp
@@ -20,7 +20,8 @@
 
 namespace wasm {
 
-Random::Random(std::vector<char>&& bytes) : bytes(std::move(bytes)) {
+Random::Random(std::vector<char>&& bytes, FeatureSet features)
+  : bytes(std::move(bytes)), features(features) {
   // Ensure there is *some* input to be read.
   if (bytes.empty()) {
     bytes.push_back(0);
diff --git a/src/tools/fuzzing/random.h b/src/tools/fuzzing/random.h
index 156f248ca..845aa2fa5 100644
--- a/src/tools/fuzzing/random.h
+++ b/src/tools/fuzzing/random.h
@@ -18,8 +18,11 @@
 #define wasm_tools_fuzzing_random_h
 
 #include <cstdint>
+#include <map>
 #include <vector>
 
+#include "wasm-features.h"
+
 namespace wasm {
 
 class Random {
@@ -33,9 +36,13 @@ class Random {
   // After we finish the input, we start going through it again, but xoring
   // so it's not identical.
   int xorFactor = 0;
+  // Features used for picking among FeatureOptions.
+  FeatureSet features;
 
 public:
-  Random(std::vector<char>&& bytes);
+  Random(std::vector<char>&& bytes, FeatureSet features);
+  Random(std::vector<char>&& bytes)
+    : Random(std::move(bytes), FeatureSet::All) {}
 
   // Methods for getting random data.
   int8_t get();
@@ -55,6 +62,87 @@ public:
   uint32_t upToSquared(uint32_t x) { return upTo(upTo(x)); }
 
   bool finished() { return finishedInput; }
+
+  // Pick from a vector-like container
+  template<typename T> const typename T::value_type& pick(const T& vec) {
+    assert(!vec.empty());
+    auto index = upTo(vec.size());
+    return vec[index];
+  }
+
+  // Pick from a fixed list
+  template<typename T, typename... Args> T pick(T first, Args... args) {
+    auto num = sizeof...(Args) + 1;
+    auto temp = upTo(num);
+    return pickGivenNum<T>(temp, first, args...);
+  }
+
+  template<typename T> T pickGivenNum(size_t num, T first) {
+    assert(num == 0);
+    return first;
+  }
+
+// Trick to avoid a bug in GCC 7.x.
+// Upstream bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82800
+#define GCC_VERSION                                                            \
+  (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__)
+#if GCC_VERSION > 70000 && GCC_VERSION < 70300
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
+#endif
+
+  template<typename T, typename... Args>
+  T pickGivenNum(size_t num, T first, Args... args) {
+    if (num == 0) {
+      return first;
+    }
+    return pickGivenNum<T>(num - 1, args...);
+  }
+
+#if GCC_VERSION > 70000 && GCC_VERSION < 70300
+#pragma GCC diagnostic pop
+#endif
+
+  template<typename T> struct FeatureOptions {
+    template<typename... Ts>
+    FeatureOptions<T>& add(FeatureSet feature, T option, Ts... rest) {
+      options[feature].push_back(option);
+      return add(feature, rest...);
+    }
+
+    struct WeightedOption {
+      T option;
+      size_t weight;
+    };
+
+    template<typename... Ts>
+    FeatureOptions<T>&
+    add(FeatureSet feature, WeightedOption weightedOption, Ts... rest) {
+      for (size_t i = 0; i < weightedOption.weight; i++) {
+        options[feature].push_back(weightedOption.option);
+      }
+      return add(feature, rest...);
+    }
+
+    FeatureOptions<T>& add(FeatureSet feature) { return *this; }
+
+    std::map<FeatureSet, std::vector<T>> options;
+  };
+
+  template<typename T> std::vector<T> items(FeatureOptions<T>& picker) {
+    std::vector<T> matches;
+    for (const auto& item : picker.options) {
+      if (features.has(item.first)) {
+        matches.reserve(matches.size() + item.second.size());
+        matches.insert(matches.end(), item.second.begin(), item.second.end());
+      }
+    }
+    return matches;
+  }
+
+  template<typename T> const T pick(FeatureOptions<T>& picker) {
+    return pick(items(picker));
+  }
 };
 
 } // namespace wasm