Implement AST fuzzer
This change implements a new fuzzer. It mutates a WGSL shader by traversing
the AST of a program and applying various transformations that might or might not
be semantics preserving.
Change-Id: I6b144bd1067444c3f0b815ba1a646aaf6e739b52
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/52160
Kokoro: Kokoro <noreply+kokoro@google.com>
Commit-Queue: Vasyl Teliman <vasniktel@gmail.com>
Reviewed-by: Alastair Donaldson <allydonaldson@googlemail.com>
Reviewed-by: Ben Clayton <bclayton@google.com>
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 2359e4d..3985a5f 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -51,6 +51,7 @@
option(TINT_BUILD_WGSL_WRITER "Build the WGSL output writer" ON)
option(TINT_BUILD_FUZZERS "Build fuzzers" OFF)
option(TINT_BUILD_SPIRV_TOOLS_FUZZER "Build SPIRV-Tools fuzzer" OFF)
+option(TINT_BUILD_AST_FUZZER "Build AST fuzzer" OFF)
option(TINT_BUILD_TESTS "Build tests" ${TINT_BUILD_TESTS_DEFAULT})
option(TINT_BUILD_AS_OTHER_OS "Override OS detection to force building of *_other.cc files" OFF)
option(TINT_BUILD_REMOTE_COMPILE "Build the remote-compile tool for validating shaders on a remote machine" OFF)
@@ -73,6 +74,7 @@
message(STATUS "Tint build WGSL writer: ${TINT_BUILD_WGSL_WRITER}")
message(STATUS "Tint build fuzzers: ${TINT_BUILD_FUZZERS}")
message(STATUS "Tint build SPIRV-Tools fuzzer: ${TINT_BUILD_SPIRV_TOOLS_FUZZER}")
+message(STATUS "Tint build AST fuzzer: ${TINT_BUILD_AST_FUZZER}")
message(STATUS "Tint build tests: ${TINT_BUILD_TESTS}")
message(STATUS "Tint build with ASAN: ${TINT_ENABLE_ASAN}")
message(STATUS "Tint build with MSAN: ${TINT_ENABLE_MSAN}")
@@ -85,13 +87,13 @@
if (${TINT_BUILD_SPIRV_TOOLS_FUZZER})
message(STATUS "TINT_BUILD_SPIRV_TOOLS_FUZZER is ON - setting
- TINT_BUILD_FUZZERS,
- TINT_BUILD_SPV_READER,
- TINT_BUILD_WGSL_READER,
- TINT_BUILD_WGSL_WRITER,
- TINT_BUILD_HLSL_WRITER,
- TINT_BUILD_MSL_WRITER,
- TINT_BUILD_SPV_WRITER to ON")
+ TINT_BUILD_FUZZERS
+ TINT_BUILD_SPV_READER
+ TINT_BUILD_WGSL_READER
+ TINT_BUILD_WGSL_WRITER
+ TINT_BUILD_HLSL_WRITER
+ TINT_BUILD_MSL_WRITER
+ TINT_BUILD_SPV_WRITER to ON")
set(TINT_BUILD_FUZZERS ON)
set(TINT_BUILD_SPV_READER ON)
set(TINT_BUILD_WGSL_READER ON)
@@ -101,6 +103,22 @@
set(TINT_BUILD_SPV_WRITER ON)
endif()
+if (${TINT_BUILD_AST_FUZZER})
+ message(STATUS "TINT_BUILD_AST_FUZZER is ON - setting
+ TINT_BUILD_FUZZERS
+ TINT_BUILD_WGSL_READER
+ TINT_BUILD_WGSL_WRITER
+ TINT_BUILD_SPV_WRITER
+ TINT_BUILD_MSL_WRITER
+ TINT_BUILD_HLSL_WRITER to ON")
+ set(TINT_BUILD_FUZZERS ON)
+ set(TINT_BUILD_WGSL_READER ON)
+ set(TINT_BUILD_WGSL_WRITER ON)
+ set(TINT_BUILD_SPV_WRITER ON)
+ set(TINT_BUILD_MSL_WRITER ON)
+ set(TINT_BUILD_HLSL_WRITER ON)
+endif()
+
set(TINT_ROOT_SOURCE_DIR ${PROJECT_SOURCE_DIR})
# CMake < 3.15 sets /W3 in CMAKE_CXX_FLAGS. Remove it if it's there.
diff --git a/DEPS b/DEPS
index d3b3dcb..c710f14 100644
--- a/DEPS
+++ b/DEPS
@@ -45,7 +45,7 @@
'/google/googletest.git@' + Var('googletest_revision'),
'third_party/protobuf': Var('chromium_git') + Var('github') +
- '/protocolbuffers/protobuf.git@' + Var('protobuf_revision'),
+ '/protocolbuffers/protobuf.git@' + Var('protobuf_revision'),
}
hooks = [
diff --git a/Doxyfile b/Doxyfile
index 8cf5eee..211e3b8 100644
--- a/Doxyfile
+++ b/Doxyfile
@@ -789,6 +789,8 @@
fuzzers/tint_spirv_tools_fuzzer \
src \
tools/src \
+ fuzzers/tint_spirv_tools_fuzzer \
+ fuzzers/tint_ast_fuzzer
# This tag can be used to specify the character encoding of the source files
# that doxygen parses. Internally doxygen uses the UTF-8 encoding. Doxygen uses
diff --git a/fuzzers/CMakeLists.txt b/fuzzers/CMakeLists.txt
index 70e1ceb..8847be2 100644
--- a/fuzzers/CMakeLists.txt
+++ b/fuzzers/CMakeLists.txt
@@ -77,3 +77,7 @@
if (${TINT_BUILD_SPIRV_TOOLS_FUZZER})
add_subdirectory(tint_spirv_tools_fuzzer)
endif()
+
+if (${TINT_BUILD_AST_FUZZER})
+ add_subdirectory(tint_ast_fuzzer)
+endif()
diff --git a/fuzzers/tint_ast_fuzzer/CMakeLists.txt b/fuzzers/tint_ast_fuzzer/CMakeLists.txt
new file mode 100644
index 0000000..e8d5a42
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/CMakeLists.txt
@@ -0,0 +1,102 @@
+# Copyright 2021 The Tint Authors.
+#
+# 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.
+
+if (NOT (${CMAKE_CXX_COMPILER_ID} MATCHES Clang))
+ message(FATAL_ERROR "Libfuzzer is supported only on clang")
+endif ()
+
+set(PROTOBUF_SOURCES ${CMAKE_CURRENT_SOURCE_DIR}/protobufs/tint_ast_fuzzer.proto)
+
+file(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/protobufs)
+
+add_custom_command(
+ OUTPUT
+ ${CMAKE_CURRENT_BINARY_DIR}/protobufs/tint_ast_fuzzer.pb.cc
+ ${CMAKE_CURRENT_BINARY_DIR}/protobufs/tint_ast_fuzzer.pb.h
+ COMMAND
+ "protobuf::protoc" -I=${CMAKE_CURRENT_SOURCE_DIR}/protobufs
+ --cpp_out=${CMAKE_CURRENT_BINARY_DIR}/protobufs ${PROTOBUF_SOURCES}
+ DEPENDS ${PROTOBUF_SOURCES}
+ COMMENT "Generate protobuf sources from proto definition file.")
+
+set(LIBTINT_AST_FUZZER_SOURCES
+ mt_rng.h
+ mutation.h
+ mutation_finder.h
+ mutation_finders/replace_identifiers.h
+ mutations/replace_identifier.h
+ mutator.h
+ node_id_map.h
+ probability_context.h
+ protobufs/tint_ast_fuzzer.h
+ random_number_generator.h
+ util.h
+ ${CMAKE_CURRENT_BINARY_DIR}/protobufs/tint_ast_fuzzer.pb.h)
+
+set(LIBTINT_AST_FUZZER_SOURCES ${LIBTINT_AST_FUZZER_SOURCES}
+ mt_rng.cc
+ mutation.cc
+ mutation_finder.cc
+ mutation_finders/replace_identifiers.cc
+ mutations/replace_identifier.cc
+ mutator.cc
+ node_id_map.cc
+ probability_context.cc
+ random_number_generator.cc
+ ${CMAKE_CURRENT_BINARY_DIR}/protobufs/tint_ast_fuzzer.pb.cc)
+
+set_source_files_properties(${CMAKE_CURRENT_BINARY_DIR}/protobufs/tint_ast_fuzzer.pb.cc PROPERTIES COMPILE_FLAGS -w)
+
+# Add static library target.
+add_library(libtint_ast_fuzzer STATIC ${LIBTINT_AST_FUZZER_SOURCES})
+target_link_libraries(libtint_ast_fuzzer protobuf::libprotobuf libtint)
+tint_default_compile_options(libtint_ast_fuzzer)
+target_include_directories(libtint_ast_fuzzer PRIVATE ${CMAKE_BINARY_DIR})
+
+set(AST_FUZZER_SOURCES
+ cli.cc
+ cli.h
+ fuzzer.cc
+ ../tint_common_fuzzer.cc
+ ../tint_common_fuzzer.h)
+
+set_source_files_properties(fuzzer.cc PROPERTIES COMPILE_FLAGS -Wno-missing-prototypes)
+
+# Add libfuzzer target.
+add_executable(tint_ast_fuzzer ${AST_FUZZER_SOURCES})
+target_link_libraries(tint_ast_fuzzer libtint-fuzz libtint_ast_fuzzer)
+tint_default_compile_options(tint_ast_fuzzer)
+target_compile_definitions(tint_ast_fuzzer PRIVATE CUSTOM_MUTATOR)
+target_include_directories(tint_ast_fuzzer PRIVATE ${CMAKE_BINARY_DIR})
+
+# Add tests.
+if (${TINT_BUILD_TESTS})
+ set(TEST_SOURCES
+ mutations/replace_identifier_test.cc)
+
+ add_executable(tint_ast_fuzzer_unittests ${TEST_SOURCES})
+
+ target_include_directories(
+ tint_ast_fuzzer_unittests PRIVATE ${gmock_SOURCE_DIR}/include)
+ target_link_libraries(tint_ast_fuzzer_unittests gmock_main libtint_ast_fuzzer)
+ tint_default_compile_options(tint_ast_fuzzer_unittests)
+ target_compile_options(tint_ast_fuzzer_unittests PRIVATE
+ -Wno-global-constructors
+ -Wno-weak-vtables
+ -Wno-covered-switch-default)
+
+ target_include_directories(tint_ast_fuzzer_unittests PRIVATE ${CMAKE_BINARY_DIR})
+
+ add_test(NAME tint_ast_fuzzer_unittests COMMAND tint_ast_fuzzer_unittests)
+endif ()
diff --git a/fuzzers/tint_ast_fuzzer/cli.cc b/fuzzers/tint_ast_fuzzer/cli.cc
new file mode 100644
index 0000000..5e3f073
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/cli.cc
@@ -0,0 +1,162 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/cli.h"
+
+#include <cstring>
+#include <iostream>
+#include <limits>
+#include <sstream>
+#include <string>
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+namespace {
+
+const char* const kHelpMessage = R"(
+This is a fuzzer for the Tint compiler that works by mutating the AST.
+
+Below is a list of all supported parameters for this fuzzer. You may want to
+run it with -help=1 to check out libfuzzer parameters.
+
+ --enable_all_mutations=
+ If `false`, the fuzzer will only apply mutations from a
+ randomly selected subset of mutation types. Otherwise,
+ all mutation types will be considered. This must be one
+ of `true` or `false` (without `). By default it's `false`.
+
+ --fuzzing_target=
+ Specifies the shading language to target during fuzzing.
+ This must be one or a combination of `wgsl`, `spv`, `hlsl`,
+ `msl` (without `) separated by commas. By default it's
+ `wgsl,msl,hlsl,spv`.
+
+ --help
+ Show this message. Note that there is also a -help=1
+ parameter that will display libfuzzer's help message.
+
+ --mutation_batch_size=
+ The number of mutations to apply in a single libfuzzer
+ mutation session. This must be a numeric value that fits
+ in type `uint32_t`. By default it's 5.
+
+ --record_mutations=
+ Whether to record applied mutations in the protobuf
+ message. This is useful to debug the fuzzer and during
+ metamorphic fuzzing. The value must be one of `true` or
+ `false` (without `). By default it's `false`.
+)";
+
+bool HasPrefix(const char* str, const char* prefix) {
+ return strncmp(str, prefix, strlen(prefix)) == 0;
+}
+
+[[noreturn]] void InvalidParam(const char* param) {
+ std::cout << "Invalid value for " << param << std::endl;
+ std::cout << kHelpMessage << std::endl;
+ exit(1);
+}
+
+bool ParseBool(const char* value, bool* out) {
+ if (!strcmp(value, "true")) {
+ *out = true;
+ } else if (!strcmp(value, "false")) {
+ *out = false;
+ } else {
+ return false;
+ }
+ return true;
+}
+
+bool ParseUint32(const char* value, uint32_t* out) {
+ auto parsed = strtoul(value, nullptr, 10);
+ if (parsed > std::numeric_limits<uint32_t>::max()) {
+ return false;
+ }
+ *out = static_cast<uint32_t>(parsed);
+ return true;
+}
+
+bool ParseFuzzingTarget(const char* value, FuzzingTarget* out) {
+ if (!strcmp(value, "wgsl")) {
+ *out = FuzzingTarget::kWgsl;
+ } else if (!strcmp(value, "spv")) {
+ *out = FuzzingTarget::kSpv;
+ } else if (!strcmp(value, "msl")) {
+ *out = FuzzingTarget::kMsl;
+ } else if (!strcmp(value, "hlsl")) {
+ *out = FuzzingTarget::kHlsl;
+ } else {
+ return false;
+ }
+ return true;
+}
+
+} // namespace
+
+CliParams ParseCliParams(int argc, const char* const* argv) {
+ CliParams cli_params;
+ auto help = false;
+
+ for (int i = 1; i < argc; ++i) {
+ auto param = argv[i];
+ if (HasPrefix(param, "--record_mutations=")) {
+ if (!ParseBool(param + sizeof("--record_mutations=") - 1,
+ &cli_params.record_mutations)) {
+ InvalidParam(param);
+ }
+ } else if (HasPrefix(param, "--enable_all_mutations=")) {
+ if (!ParseBool(param + sizeof("--enable_all_mutations=") - 1,
+ &cli_params.enable_all_mutations)) {
+ InvalidParam(param);
+ }
+ } else if (HasPrefix(param, "--mutation_batch_size=")) {
+ if (!ParseUint32(param + sizeof("--mutation_batch_size=") - 1,
+ &cli_params.mutation_batch_size)) {
+ InvalidParam(param);
+ }
+ } else if (HasPrefix(param, "--fuzzing_target=")) {
+ auto result = FuzzingTarget::kNone;
+
+ std::stringstream ss(param + sizeof("--fuzzing_target=") - 1);
+ for (std::string value; std::getline(ss, value, ',');) {
+ auto tmp = FuzzingTarget::kNone;
+ if (!ParseFuzzingTarget(value.c_str(), &tmp)) {
+ InvalidParam(param);
+ }
+ result = result | tmp;
+ }
+
+ if (result == FuzzingTarget::kNone) {
+ InvalidParam(param);
+ }
+
+ cli_params.fuzzing_target = result;
+ } else if (!strcmp(param, "--help")) {
+ help = true;
+ }
+ }
+
+ if (help) {
+ std::cout << kHelpMessage << std::endl;
+ exit(0);
+ }
+
+ return cli_params;
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/cli.h b/fuzzers/tint_ast_fuzzer/cli.h
new file mode 100644
index 0000000..dd94fbb
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/cli.h
@@ -0,0 +1,74 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_CLI_H_
+#define FUZZERS_TINT_AST_FUZZER_CLI_H_
+
+#include <cstdint>
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// The backend this fuzzer will test.
+enum class FuzzingTarget {
+ kNone = 0,
+ kHlsl = 1 << 0,
+ kMsl = 1 << 1,
+ kSpv = 1 << 2,
+ kWgsl = 1 << 3,
+ kAll = kHlsl | kMsl | kSpv | kWgsl
+};
+
+inline FuzzingTarget operator|(FuzzingTarget a, FuzzingTarget b) {
+ return static_cast<FuzzingTarget>(static_cast<int>(a) | static_cast<int>(b));
+}
+
+inline FuzzingTarget operator&(FuzzingTarget a, FuzzingTarget b) {
+ return static_cast<FuzzingTarget>(static_cast<int>(a) & static_cast<int>(b));
+}
+
+/// CLI parameters accepted by the fuzzer. Type --help in the CLI to see the
+/// help message
+struct CliParams {
+ /// Whether to record applied mutations.
+ bool record_mutations = false;
+
+ /// Whether to use all mutation finders or only a randomly selected subset of
+ /// them.
+ bool enable_all_mutations = false;
+
+ /// The maximum number of mutations applied during a single mutation session
+ /// (i.e. a call to `ast_fuzzer::Mutate` function).
+ uint32_t mutation_batch_size = 5;
+
+ /// Compiler backends we want to fuzz.
+ FuzzingTarget fuzzing_target = FuzzingTarget::kAll;
+};
+
+/// @brief Parses CLI parameters.
+///
+/// This function will exit the process with non-zero return code if some
+/// parameters are invalid.
+///
+/// @param argc - the total number of parameters.
+/// @param argv - array of all CLI parameters.
+/// @return parsed parameters.
+CliParams ParseCliParams(int argc, const char* const* argv);
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_CLI_H_
diff --git a/fuzzers/tint_ast_fuzzer/fuzzer.cc b/fuzzers/tint_ast_fuzzer/fuzzer.cc
new file mode 100644
index 0000000..59dc075
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/fuzzer.cc
@@ -0,0 +1,154 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 <cstddef>
+#include <cstdint>
+
+#include "fuzzers/tint_ast_fuzzer/cli.h"
+#include "fuzzers/tint_ast_fuzzer/mt_rng.h"
+#include "fuzzers/tint_ast_fuzzer/mutator.h"
+#include "fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.h"
+#include "fuzzers/tint_common_fuzzer.h"
+
+#include "src/reader/wgsl/parser.h"
+#include "src/writer/wgsl/generator.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+namespace {
+
+CliParams cli_params{};
+
+extern "C" int LLVMFuzzerInitialize(int* argc, char*** argv) {
+ // Parse CLI parameters. `ParseCliParams` will call `exit` if some parameter
+ // is invalid.
+ cli_params = ParseCliParams(*argc, *argv);
+ return 0;
+}
+
+extern "C" size_t LLVMFuzzerCustomMutator(uint8_t* data,
+ size_t size,
+ size_t max_size,
+ unsigned seed) {
+ protobufs::MutatorState mutator_state;
+ auto success = mutator_state.ParseFromArray(data, static_cast<int>(size));
+ (void)success; // This variable will be unused in release mode.
+ assert(success && "Can't parse protobuf message");
+
+ tint::Source::File file("test.wgsl", mutator_state.program());
+ auto program = reader::wgsl::Parse(&file);
+ protobufs::MutationSequence* mutation_sequence = nullptr;
+
+ if (cli_params.record_mutations) {
+ // If mutations are being recorded, then `mutator_state.program` is the
+ // original (unmodified) program and it is necessary to replay all
+ // mutations.
+ mutation_sequence = mutator_state.mutable_mutation_sequence();
+ program = Replay(std::move(program), *mutation_sequence);
+ if (!program.IsValid()) {
+ std::cout << "Replayer produced invalid WGSL:" << std::endl
+ << " seed: " << seed << std::endl
+ << program.Diagnostics().str() << std::endl;
+ return 0;
+ }
+ }
+
+ // Run the mutator.
+ MtRng mt_rng(seed);
+ ProbabilityContext probability_context(&mt_rng);
+ program = Mutate(std::move(program), &probability_context,
+ cli_params.enable_all_mutations,
+ cli_params.mutation_batch_size, mutation_sequence);
+
+ if (!program.IsValid()) {
+ std::cout << "Mutator produced invalid WGSL:" << std::endl
+ << " seed: " << seed << std::endl
+ << program.Diagnostics().str() << std::endl;
+ return 0;
+ }
+
+ if (!cli_params.record_mutations) {
+ // If mutations are not being recorded, then the mutated `program` must be
+ // stored into the `mutator_state`.
+ writer::wgsl::Generator generator(&program);
+ if (!generator.Generate()) {
+ std::cout << "Can't generate WGSL for valid tint::Program:" << std::endl
+ << " seed: " << seed << std::endl
+ << generator.error() << std::endl;
+ return 0;
+ }
+ *mutator_state.mutable_program() = generator.result();
+ }
+
+ if (mutator_state.ByteSizeLong() > max_size) {
+ return 0;
+ }
+
+ success = mutator_state.SerializeToArray(data, static_cast<int>(max_size));
+ assert(success && "Can't serialize a protobuf message");
+ return mutator_state.ByteSizeLong();
+}
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size) {
+ if (size == 0) {
+ return 0;
+ }
+
+ protobufs::MutatorState mutator_state;
+ auto success = mutator_state.ParseFromArray(data, static_cast<int>(size));
+ (void)success; // This variable will be unused in release mode.
+ assert(success && "Can't parse a protobuf message");
+
+ std::string program_text;
+ if (cli_params.record_mutations) {
+ // If mutations are being recorded, then it's necessary to replay them
+ // before invoking the system under test.
+ Source::File file("test.wgsl", mutator_state.program());
+ auto program =
+ Replay(reader::wgsl::Parse(&file), mutator_state.mutation_sequence());
+ assert(program.IsValid() && "Replayed program is invalid");
+
+ writer::wgsl::Generator generator(&program);
+ success = generator.Generate();
+ assert(success && "Can't generate a shader for the valid tint::Program");
+ program_text = generator.result();
+ } else {
+ program_text.assign(data, data + size);
+ }
+
+ std::pair<FuzzingTarget, OutputFormat> targets[] = {
+ {FuzzingTarget::kWgsl, OutputFormat::kWGSL},
+ {FuzzingTarget::kHlsl, OutputFormat::kHLSL},
+ {FuzzingTarget::kMsl, OutputFormat::kMSL},
+ {FuzzingTarget::kSpv, OutputFormat::kSpv}};
+
+ for (auto target : targets) {
+ if ((target.first & cli_params.fuzzing_target) != target.first) {
+ continue;
+ }
+
+ CommonFuzzer fuzzer(InputFormat::kWGSL, target.second);
+ fuzzer.EnableInspector();
+ fuzzer.Run(reinterpret_cast<const uint8_t*>(program_text.data()),
+ program_text.size());
+ }
+
+ return 0;
+}
+
+} // namespace
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/mt_rng.cc b/fuzzers/tint_ast_fuzzer/mt_rng.cc
new file mode 100644
index 0000000..586b2d9
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mt_rng.cc
@@ -0,0 +1,44 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/mt_rng.h"
+
+#include <cassert>
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+namespace {
+
+template <typename T>
+T RandomUInt(std::mt19937* rng, T bound) {
+ assert(bound > 0 && "`bound` must be positive");
+ return std::uniform_int_distribution<T>(0, bound - 1)(*rng);
+}
+
+} // namespace
+
+MtRng::MtRng(uint32_t seed) : rng_(seed) {}
+
+uint32_t MtRng::RandomUint32(uint32_t bound) {
+ return RandomUInt(&rng_, bound);
+}
+
+uint64_t MtRng::RandomUint64(uint64_t bound) {
+ return RandomUInt(&rng_, bound);
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/mt_rng.h b/fuzzers/tint_ast_fuzzer/mt_rng.h
new file mode 100644
index 0000000..ebbddc4
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mt_rng.h
@@ -0,0 +1,45 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_MT_RNG_H_
+#define FUZZERS_TINT_AST_FUZZER_MT_RNG_H_
+
+#include <random>
+
+#include "fuzzers/tint_ast_fuzzer/random_number_generator.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// The random number generator that uses STL's Mersenne Twister (std::mt19937)
+/// under the hood.
+class MtRng : public RandomNumberGenerator {
+ public:
+ /// @brief Initializes this RNG with some `seed`.
+ /// @param seed - passed down to the `std::mt19937`.
+ explicit MtRng(uint32_t seed);
+
+ uint32_t RandomUint32(uint32_t bound) override;
+ uint64_t RandomUint64(uint64_t bound) override;
+
+ private:
+ std::mt19937 rng_;
+};
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_MT_RNG_H_
diff --git a/fuzzers/tint_ast_fuzzer/mutation.cc b/fuzzers/tint_ast_fuzzer/mutation.cc
new file mode 100644
index 0000000..0e524710
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutation.cc
@@ -0,0 +1,40 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/mutation.h"
+
+#include <cassert>
+
+#include "fuzzers/tint_ast_fuzzer/mutations/replace_identifier.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+Mutation::~Mutation() = default;
+
+std::unique_ptr<Mutation> Mutation::FromMessage(
+ const protobufs::Mutation& message) {
+ switch (message.mutation_case()) {
+ case protobufs::Mutation::kReplaceIdentifier:
+ return std::make_unique<MutationReplaceIdentifier>(
+ message.replace_identifier());
+ case protobufs::Mutation::MUTATION_NOT_SET:
+ assert(false && "Mutation is not set");
+ }
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/mutation.h b/fuzzers/tint_ast_fuzzer/mutation.h
new file mode 100644
index 0000000..77f29f3
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutation.h
@@ -0,0 +1,86 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_MUTATION_H_
+#define FUZZERS_TINT_AST_FUZZER_MUTATION_H_
+
+#include <memory>
+#include <vector>
+
+#include "fuzzers/tint_ast_fuzzer/node_id_map.h"
+#include "fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.h"
+
+#include "src/clone_context.h"
+#include "src/program.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// The base class for all the mutations in the fuzzer. Children must override
+/// three methods:
+/// - `IsApplicable` - checks whether it is possible to apply the mutation
+/// in a manner that will lead to a valid program.
+/// - `Apply` - applies the mutation.
+/// - `ToMessage` - converts the mutation data into a protobuf message.
+class Mutation {
+ public:
+ /// Virtual destructor.
+ virtual ~Mutation();
+
+ /// @brief Determines whether this mutation is applicable to the `program`.
+ ///
+ /// @param program - the program this mutation will be applied to. The program
+ /// must be valid.
+ /// @param node_id_map - the map from `tint::ast::` nodes to their ids.
+ /// @return `true` if `Apply` method can be called without breaking the
+ /// semantics of the `program`.
+ /// @return `false` otherwise.
+ virtual bool IsApplicable(const tint::Program& program,
+ const NodeIdMap& node_id_map) const = 0;
+
+ /// @brief Applies this mutation to the `clone_context`.
+ ///
+ /// Precondition: `IsApplicable` must return `true` when invoked on the same
+ /// `node_id_map` and `clone_context->src` instance of `tint::Program`. A new
+ /// `tint::Program` that arises in `clone_context` must be valid.
+ ///
+ /// @param node_id_map - the map from `tint::ast::` nodes to their ids.
+ /// @param clone_context - the context that will clone the program with some
+ /// changes introduced by this mutation.
+ /// @param new_node_id_map - this map will store ids for the mutated and
+ /// cloned program. This argument cannot be a `nullptr` nor can it point
+ /// to the same object as `node_id_map`.
+ virtual void Apply(const NodeIdMap& node_id_map,
+ tint::CloneContext* clone_context,
+ NodeIdMap* new_node_id_map) const = 0;
+
+ /// @return a protobuf message for this mutation.
+ virtual protobufs::Mutation ToMessage() const = 0;
+
+ /// @brief Converts a protobuf message into the mutation instance.
+ ///
+ /// @param message - a protobuf message.
+ /// @return the instance of this class.
+ static std::unique_ptr<Mutation> FromMessage(
+ const protobufs::Mutation& message);
+};
+
+using MutationList = std::vector<std::unique_ptr<Mutation>>;
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_MUTATION_H_
diff --git a/fuzzers/tint_ast_fuzzer/mutation_finder.cc b/fuzzers/tint_ast_fuzzer/mutation_finder.cc
new file mode 100644
index 0000000..daf1d6d
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutation_finder.cc
@@ -0,0 +1,25 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/mutation_finder.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+MutationFinder::~MutationFinder() = default;
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/mutation_finder.h b/fuzzers/tint_ast_fuzzer/mutation_finder.h
new file mode 100644
index 0000000..546dce4
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutation_finder.h
@@ -0,0 +1,77 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_MUTATION_FINDER_H_
+#define FUZZERS_TINT_AST_FUZZER_MUTATION_FINDER_H_
+
+#include <memory>
+#include <vector>
+
+#include "fuzzers/tint_ast_fuzzer/mutation.h"
+#include "fuzzers/tint_ast_fuzzer/node_id_map.h"
+#include "fuzzers/tint_ast_fuzzer/probability_context.h"
+
+#include "src/program.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// Instances of this class traverse the `tint::Program`, looking for
+/// opportunities to apply mutations and return them to the caller.
+///
+/// Ideally, the behaviour of this class (precisely, its `FindMutations` method)
+/// should not be probabilistic. This is useful when mutation finders are used
+/// for test case reduction, because it enables the test case reducer to
+/// systematically explore all available mutations. There may be some
+/// exceptions, however. For example, if a huge number of mutations is returned,
+/// it would make sense to apply only a probabilistically selected subset of
+/// them.
+class MutationFinder {
+ public:
+ /// Virtual destructor.
+ virtual ~MutationFinder();
+
+ /// @brief Traverses the `program`, looking for opportunities to apply
+ /// mutations.
+ ///
+ /// @param program - the program being fuzzed.
+ /// @param node_id_map - a map from `tint::ast::` nodes in the `program` to
+ /// their unique ids.
+ /// @param probability_context - determines various probabilistic stuff in the
+ /// mutator. This should ideally be used as less as possible.
+ /// @return all the found mutations.
+ virtual MutationList FindMutations(
+ const tint::Program& program,
+ const NodeIdMap& node_id_map,
+ ProbabilityContext* probability_context) const = 0;
+
+ /// @brief Compute a probability of applying a single mutation, returned by
+ /// this class.
+ ///
+ /// @param probability_context - contains information about various
+ /// non-deterministic stuff in the fuzzer.
+ /// @return a number in the range [0; 100] which is a chance of applying a
+ /// mutation.
+ virtual uint32_t GetChanceOfApplyingMutation(
+ ProbabilityContext* probability_context) const = 0;
+};
+
+using MutationFinderList = std::vector<std::unique_ptr<MutationFinder>>;
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_MUTATION_FINDER_H_
diff --git a/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.cc b/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.cc
new file mode 100644
index 0000000..7eb3f6d
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.cc
@@ -0,0 +1,79 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h"
+
+#include <memory>
+
+#include "fuzzers/tint_ast_fuzzer/mutations/replace_identifier.h"
+#include "fuzzers/tint_ast_fuzzer/util.h"
+
+#include "src/sem/expression.h"
+#include "src/sem/statement.h"
+#include "src/sem/variable.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+MutationList MutationFinderReplaceIdentifiers::FindMutations(
+ const tint::Program& program,
+ const NodeIdMap& node_id_map,
+ ProbabilityContext* probability_context) const {
+ MutationList result;
+
+ // Go through each variable in the AST and for each user of that variable, try
+ // to replace it with some other variable usage.
+
+ for (const auto* node : program.SemNodes().Objects()) {
+ const auto* sem_variable = tint::As<sem::Variable>(node);
+ if (!sem_variable) {
+ continue;
+ }
+
+ // Iterate over all users of `sem_variable`.
+ for (const auto* user : sem_variable->Users()) {
+ // Get all variables that can be used to replace the `user` of
+ // `sem_variable`.
+ auto candidate_variables = util::GetAllVarsInScope(
+ program, user->Stmt(), [user](const sem::Variable* var) {
+ return var != user->Variable() && var->Type() == user->Type();
+ });
+
+ if (candidate_variables.empty()) {
+ // No suitable replacements have been found.
+ continue;
+ }
+
+ const auto* replacement =
+ candidate_variables[probability_context->GetRandomIndex(
+ candidate_variables)];
+
+ result.push_back(std::make_unique<MutationReplaceIdentifier>(
+ node_id_map.GetId(user->Declaration()),
+ node_id_map.GetId(replacement->Declaration())));
+ }
+ }
+
+ return result;
+}
+
+uint32_t MutationFinderReplaceIdentifiers::GetChanceOfApplyingMutation(
+ ProbabilityContext* probability_context) const {
+ return probability_context->GetChanceOfReplacingIdentifiers();
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h b/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h
new file mode 100644
index 0000000..957abf2
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h
@@ -0,0 +1,42 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_MUTATION_FINDERS_REPLACE_IDENTIFIERS_H_
+#define FUZZERS_TINT_AST_FUZZER_MUTATION_FINDERS_REPLACE_IDENTIFIERS_H_
+
+#include "fuzzers/tint_ast_fuzzer/mutation_finder.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// Looks for opportunities to apply `MutationReplaceIdentifier`.
+///
+/// Concretely, for each variable in the module, tries to replace its users with
+/// the uses of some other variables.
+class MutationFinderReplaceIdentifiers : public MutationFinder {
+ public:
+ MutationList FindMutations(
+ const tint::Program& program,
+ const NodeIdMap& node_id_map,
+ ProbabilityContext* probability_context) const override;
+ uint32_t GetChanceOfApplyingMutation(
+ ProbabilityContext* probability_context) const override;
+};
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_MUTATION_FINDERS_REPLACE_IDENTIFIERS_H_
diff --git a/fuzzers/tint_ast_fuzzer/mutations/replace_identifier.cc b/fuzzers/tint_ast_fuzzer/mutations/replace_identifier.cc
new file mode 100644
index 0000000..2b2bb9d
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutations/replace_identifier.cc
@@ -0,0 +1,106 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/mutations/replace_identifier.h"
+
+#include <utility>
+
+#include "fuzzers/tint_ast_fuzzer/util.h"
+#include "src/program_builder.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+MutationReplaceIdentifier::MutationReplaceIdentifier(
+ protobufs::MutationReplaceIdentifier message)
+ : message_(std::move(message)) {}
+
+MutationReplaceIdentifier::MutationReplaceIdentifier(uint32_t use_id,
+ uint32_t replacement_id) {
+ message_.set_use_id(use_id);
+ message_.set_replacement_id(replacement_id);
+}
+
+bool MutationReplaceIdentifier::IsApplicable(
+ const tint::Program& program,
+ const NodeIdMap& node_id_map) const {
+ const auto* use_ast_node = tint::As<ast::IdentifierExpression>(
+ node_id_map.GetNode(message_.use_id()));
+ if (!use_ast_node) {
+ // Either the `use_id` is invalid or the node is not an
+ // `IdentifierExpression`.
+ return false;
+ }
+
+ const auto* use_sem_node =
+ tint::As<sem::VariableUser>(program.Sem().Get(use_ast_node));
+ if (!use_sem_node) {
+ // Either the semantic information is not present for a `use_node` or that
+ // node is not a variable user.
+ return false;
+ }
+
+ const auto* replacement_ast_node =
+ tint::As<ast::Variable>(node_id_map.GetNode(message_.replacement_id()));
+ if (!replacement_ast_node) {
+ // Either the `replacement_id` is invalid or is not an id of a variable.
+ return false;
+ }
+
+ const auto* replacement_sem_node = program.Sem().Get(replacement_ast_node);
+ if (!replacement_sem_node) {
+ return false;
+ }
+
+ if (replacement_sem_node == use_sem_node->Variable()) {
+ return false;
+ }
+
+ auto in_scope =
+ util::GetAllVarsInScope(program, use_sem_node->Stmt(),
+ [replacement_sem_node](const sem::Variable* var) {
+ return var == replacement_sem_node;
+ });
+ if (in_scope.empty()) {
+ // The replacement variable is not in scope.
+ return false;
+ }
+
+ return use_sem_node->Type() == replacement_sem_node->Type();
+}
+
+void MutationReplaceIdentifier::Apply(const NodeIdMap& node_id_map,
+ tint::CloneContext* clone_context,
+ NodeIdMap* new_node_id_map) const {
+ const auto* use_node = node_id_map.GetNode(message_.use_id());
+ const auto* replacement_var =
+ tint::As<ast::Variable>(node_id_map.GetNode(message_.replacement_id()));
+
+ auto* cloned_replacement =
+ clone_context->dst->Expr(clone_context->Clone(use_node->source()),
+ clone_context->Clone(replacement_var->symbol()));
+ clone_context->Replace(use_node, cloned_replacement);
+ new_node_id_map->Add(cloned_replacement, message_.use_id());
+}
+
+protobufs::Mutation MutationReplaceIdentifier::ToMessage() const {
+ protobufs::Mutation mutation;
+ *mutation.mutable_replace_identifier() = message_;
+ return mutation;
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/mutations/replace_identifier.h b/fuzzers/tint_ast_fuzzer/mutations/replace_identifier.h
new file mode 100644
index 0000000..fa16715
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutations/replace_identifier.h
@@ -0,0 +1,77 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_MUTATIONS_REPLACE_IDENTIFIER_H_
+#define FUZZERS_TINT_AST_FUZZER_MUTATIONS_REPLACE_IDENTIFIER_H_
+
+#include "fuzzers/tint_ast_fuzzer/mutation.h"
+
+#include "src/sem/variable.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// @see MutationReplaceIdentifier::Apply
+class MutationReplaceIdentifier : public Mutation {
+ public:
+ /// @brief Constructs an instance of this mutation from a protobuf message.
+ /// @param message - protobuf message
+ explicit MutationReplaceIdentifier(
+ protobufs::MutationReplaceIdentifier message);
+
+ /// @brief Constructor.
+ /// @param use_id - the id of a variable user.
+ /// @param replacement_id - the id of a variable to replace the `use_id`.
+ MutationReplaceIdentifier(uint32_t use_id, uint32_t replacement_id);
+
+ /// @copybrief Mutation::IsApplicable
+ ///
+ /// The mutation is applicable iff:
+ /// - `use_id` is a valid id of an `ast::IdentifierExpression`, that
+ /// references a variable.
+ /// - `replacement_id` is a valid id of an `ast::Variable`.
+ /// - The identifier expression doesn't reference the variable of a
+ /// `replacement_id`.
+ /// - The variable with `replacement_id` is in scope of an identifier
+ /// expression with `use_id`.
+ /// - The identifier expression and the variable have the same type.
+ ///
+ /// @copydetails Mutation::IsApplicable
+ bool IsApplicable(const tint::Program& program,
+ const NodeIdMap& node_id_map) const override;
+
+ /// @copybrief Mutation::Apply
+ ///
+ /// Replaces the use of an identifier expression with `use_id` with a newly
+ /// created identifier expression, that references a variable with
+ /// `replacement_id`. The newly created identifier expression will have the
+ /// same id as the old one (i.e. `use_id`).
+ ///
+ /// @copydetails Mutation::Apply
+ void Apply(const NodeIdMap& node_id_map,
+ tint::CloneContext* clone_context,
+ NodeIdMap* new_node_id_map) const override;
+
+ protobufs::Mutation ToMessage() const override;
+
+ private:
+ protobufs::MutationReplaceIdentifier message_;
+};
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_MUTATIONS_REPLACE_IDENTIFIER_H_
diff --git a/fuzzers/tint_ast_fuzzer/mutations/replace_identifier_test.cc b/fuzzers/tint_ast_fuzzer/mutations/replace_identifier_test.cc
new file mode 100644
index 0000000..84e47b5
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutations/replace_identifier_test.cc
@@ -0,0 +1,723 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 <string>
+
+#include "gtest/gtest.h"
+
+#include "fuzzers/tint_ast_fuzzer/mt_rng.h"
+#include "fuzzers/tint_ast_fuzzer/mutations/replace_identifier.h"
+#include "fuzzers/tint_ast_fuzzer/mutator.h"
+#include "fuzzers/tint_ast_fuzzer/probability_context.h"
+
+#include "fuzzers/tint_ast_fuzzer/node_id_map.h"
+
+#include "src/ast/call_statement.h"
+#include "src/program_builder.h"
+#include "src/reader/wgsl/parser.h"
+#include "src/writer/wgsl/generator.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+namespace {
+
+TEST(ReplaceIdentifierTest, NotApplicable_Simple) {
+ std::string content = R"(
+ fn main() {
+ let a = 5;
+ let c = 6;
+ let b = a + 5;
+
+ let d = vec2<i32>(1, 2);
+ let e = d.x;
+ }
+ )";
+ Source::File file("test.wgsl", content);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ const auto& main_fn_stmts =
+ program.AST().Functions()[0]->body()->statements();
+
+ const auto* a_var =
+ main_fn_stmts[0]->As<ast::VariableDeclStatement>()->variable();
+ ASSERT_NE(a_var, nullptr);
+
+ const auto* b_var =
+ main_fn_stmts[2]->As<ast::VariableDeclStatement>()->variable();
+ ASSERT_NE(b_var, nullptr);
+
+ const auto* e_var =
+ main_fn_stmts[4]->As<ast::VariableDeclStatement>()->variable();
+ ASSERT_NE(e_var, nullptr);
+
+ auto a_var_id = node_id_map.GetId(a_var);
+ ASSERT_NE(a_var_id, 0);
+
+ auto b_var_id = node_id_map.GetId(b_var);
+ ASSERT_NE(b_var_id, 0);
+
+ const auto* sum_expr = b_var->constructor()->As<ast::BinaryExpression>();
+ ASSERT_NE(sum_expr, nullptr);
+
+ auto a_ident_id = node_id_map.GetId(sum_expr->lhs());
+ ASSERT_NE(a_ident_id, 0);
+
+ auto sum_expr_id = node_id_map.GetId(sum_expr);
+ ASSERT_NE(sum_expr_id, 0);
+
+ auto e_var_id = node_id_map.GetId(e_var);
+ ASSERT_NE(e_var_id, 0);
+
+ auto vec_member_access_id = node_id_map.GetId(
+ e_var->constructor()->As<ast::MemberAccessorExpression>()->member());
+ ASSERT_NE(vec_member_access_id, 0);
+
+ // use_id is invalid.
+ EXPECT_FALSE(MutationReplaceIdentifier(0, a_var_id)
+ .IsApplicable(program, node_id_map));
+
+ // use_id is not an identifier expression.
+ EXPECT_FALSE(MutationReplaceIdentifier(sum_expr_id, a_var_id)
+ .IsApplicable(program, node_id_map));
+
+ // use_id is an identifier but not a variable user.
+ EXPECT_FALSE(MutationReplaceIdentifier(vec_member_access_id, a_var_id)
+ .IsApplicable(program, node_id_map));
+
+ // replacement_id is invalid.
+ EXPECT_FALSE(MutationReplaceIdentifier(a_ident_id, 0)
+ .IsApplicable(program, node_id_map));
+
+ // replacement_id is not a variable.
+ EXPECT_FALSE(MutationReplaceIdentifier(a_ident_id, sum_expr_id)
+ .IsApplicable(program, node_id_map));
+
+ // Can't replace a variable with itself.
+ EXPECT_FALSE(MutationReplaceIdentifier(a_ident_id, a_var_id)
+ .IsApplicable(program, node_id_map));
+
+ // Replacement is not in scope.
+ EXPECT_FALSE(MutationReplaceIdentifier(a_ident_id, b_var_id)
+ .IsApplicable(program, node_id_map));
+ EXPECT_FALSE(MutationReplaceIdentifier(a_ident_id, e_var_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, GlobalVarNotInScope) {
+ // Can't use the global variable if it's not in scope.
+ std::string shader = R"(
+var<private> a: i32;
+
+fn f() {
+ a = 3;
+}
+
+var<private> b: i32;
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::AssignmentStatement>()
+ ->lhs());
+ ASSERT_NE(use_id, 0);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[1]);
+ ASSERT_NE(replacement_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable1) {
+ // Can't replace `a` with `b` since the store type is wrong (the same storage
+ // class though).
+ std::string shader = R"(
+var<private> a: i32;
+var<private> b: u32;
+fn f() {
+ *&a = 4;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[1]);
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::AssignmentStatement>()
+ ->lhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable2) {
+ // Can't replace `a` with `b` since the store type is wrong (the storage
+ // class is different though).
+ std::string shader = R"(
+var<private> a: i32;
+fn f() {
+ var b: u32;
+ *&a = 4;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::VariableDeclStatement>()
+ ->variable());
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[1]
+ ->As<ast::AssignmentStatement>()
+ ->lhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable3) {
+ // Can't replace `a` with `b` since the latter is not a reference (the store
+ // type is the same, though).
+ std::string shader = R"(
+var<private> a: i32;
+fn f() {
+ let b = 45;
+ *&a = 4;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::VariableDeclStatement>()
+ ->variable());
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[1]
+ ->As<ast::AssignmentStatement>()
+ ->lhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable4) {
+ // Can't replace `a` with `b` since the latter is not a reference (the store
+ // type is the same, though).
+ std::string shader = R"(
+var<private> a: i32;
+fn f(b: i32) {
+ *&a = 4;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id =
+ node_id_map.GetId(program.AST().Functions()[0]->params()[0]);
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::AssignmentStatement>()
+ ->lhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable5) {
+ // Can't replace `a` with `b` since the latter has a wrong access mode
+ // (`read` for uniform storage class).
+ std::string shader = R"(
+[[block]]
+struct S {
+ a: i32;
+};
+
+var<private> a: S;
+[[group(1), binding(1)]] var<uniform> b: S;
+fn f() {
+ *&a = S(4);
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[1]);
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::AssignmentStatement>()
+ ->lhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable6) {
+ // Can't replace `ptr_b` with `a` since the latter is not a pointer.
+ std::string shader = R"(
+[[block]]
+struct S {
+ a: i32;
+};
+
+var<private> a: S;
+[[group(1), binding(1)]] var<uniform> b: S;
+fn f() {
+ let ptr_b = &b;
+ *&a = *ptr_b;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[0]);
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[1]
+ ->As<ast::AssignmentStatement>()
+ ->rhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable8) {
+ // Can't replace `ptr_b` with `c` since the latter has a wrong access mode and
+ // storage class.
+ std::string shader = R"(
+[[block]]
+struct S {
+ a: i32;
+};
+
+var<private> a: S;
+[[group(1), binding(1)]] var<uniform> b: S;
+[[group(1), binding(2)]] var<storage, write> c: S;
+fn f() {
+ let ptr_b = &b;
+ *&a = *ptr_b;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[2]);
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[1]
+ ->As<ast::AssignmentStatement>()
+ ->rhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable9) {
+ // Can't replace `b` with `e` since the latter is not a reference.
+ std::string shader = R"(
+[[block]]
+struct S {
+ a: i32;
+};
+
+var<private> a: S;
+let e = 3;
+[[group(1), binding(1)]] var<uniform> b: S;
+fn f() {
+ *&a = *&b;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[1]);
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::AssignmentStatement>()
+ ->rhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable10) {
+ // Can't replace `b` with `e` since the latter has a wrong access mode.
+ std::string shader = R"(
+[[block]]
+struct S {
+ a: i32;
+};
+
+var<private> a: S;
+[[group(0), binding(0)]] var<storage, write> e: S;
+[[group(1), binding(1)]] var<uniform> b: S;
+fn f() {
+ *&a = *&b;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[1]);
+ ASSERT_NE(replacement_id, 0);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::AssignmentStatement>()
+ ->rhs()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, Applicable1) {
+ // Can replace `a` with `b` (same storage class).
+ std::string shader = R"(
+fn f() {
+ var b : vec2<u32>;
+ var a = vec2<u32>(34u, 45u);
+ (*&a)[1] = 3u;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[2]
+ ->As<ast::AssignmentStatement>()
+ ->lhs()
+ ->As<ast::ArrayAccessorExpression>()
+ ->array()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ auto replacement_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[0]
+ ->As<ast::VariableDeclStatement>()
+ ->variable());
+ ASSERT_NE(replacement_id, 0);
+
+ ASSERT_TRUE(MaybeApplyMutation(
+ program, MutationReplaceIdentifier(use_id, replacement_id), node_id_map,
+ &program, &node_id_map, nullptr));
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ writer::wgsl::Generator generator(&program);
+ ASSERT_TRUE(generator.Generate()) << generator.error();
+
+ std::string expected_shader = R"(fn f() {
+ var b : vec2<u32>;
+ var a = vec2<u32>(34u, 45u);
+ (*(&(b)))[1] = 3u;
+}
+)";
+ ASSERT_EQ(expected_shader, generator.result());
+}
+
+TEST(ReplaceIdentifierTest, Applicable2) {
+ // Can replace `ptr_a` with `b` - the function parameter.
+ std::string shader = R"(
+fn f(b: ptr<function, vec2<u32>>) {
+ var a = vec2<u32>(34u, 45u);
+ let ptr_a = &a;
+ (*ptr_a)[1] = 3u;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[2]
+ ->As<ast::AssignmentStatement>()
+ ->lhs()
+ ->As<ast::ArrayAccessorExpression>()
+ ->array()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ auto replacement_id =
+ node_id_map.GetId(program.AST().Functions()[0]->params()[0]);
+ ASSERT_NE(replacement_id, 0);
+
+ ASSERT_TRUE(MaybeApplyMutation(
+ program, MutationReplaceIdentifier(use_id, replacement_id), node_id_map,
+ &program, &node_id_map, nullptr));
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ writer::wgsl::Generator generator(&program);
+ ASSERT_TRUE(generator.Generate()) << generator.error();
+
+ std::string expected_shader = R"(fn f(b : ptr<function, vec2<u32>>) {
+ var a = vec2<u32>(34u, 45u);
+ let ptr_a = &(a);
+ (*(b))[1] = 3u;
+}
+)";
+ ASSERT_EQ(expected_shader, generator.result());
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable12) {
+ // Can't replace `a` with `b` (both are references with different storage
+ // class).
+ std::string shader = R"(
+var<private> b : vec2<u32>;
+fn f() {
+ var a = vec2<u32>(34u, 45u);
+ (*&a)[1] = 3u;
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[1]
+ ->As<ast::AssignmentStatement>()
+ ->lhs()
+ ->As<ast::ArrayAccessorExpression>()
+ ->array()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[0]);
+ ASSERT_NE(replacement_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable13) {
+ // Can't replace `a` with `b` (both are references with different storage
+ // class).
+ std::string shader = R"(
+var<private> b : vec2<u32>;
+fn f() {
+ var a = vec2<u32>(34u, 45u);
+ let c = (*&a)[1];
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[1]
+ ->As<ast::VariableDeclStatement>()
+ ->variable()
+ ->constructor()
+ ->As<ast::ArrayAccessorExpression>()
+ ->array()
+ ->As<ast::UnaryOpExpression>()
+ ->expr()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ auto replacement_id = node_id_map.GetId(program.AST().GlobalVariables()[0]);
+ ASSERT_NE(replacement_id, 0);
+
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+TEST(ReplaceIdentifierTest, NotApplicable14) {
+ // Can't replace `ptr_a` with `ptr_b` (both are pointers with different
+ // storage class).
+ std::string shader = R"(
+var<private> b: vec2<u32>;
+fn f() {
+ var a = vec2<u32>(34u, 45u);
+ let ptr_a = &a;
+ let ptr_b = &b;
+ let c = (*ptr_a)[1];
+}
+)";
+ Source::File file("test.wgsl", shader);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+
+ auto use_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[3]
+ ->As<ast::VariableDeclStatement>()
+ ->variable()
+ ->constructor()
+ ->As<ast::ArrayAccessorExpression>()
+ ->array()
+ ->As<ast::UnaryOpExpression>()
+ ->expr());
+ ASSERT_NE(use_id, 0);
+
+ auto replacement_id = node_id_map.GetId(program.AST()
+ .Functions()[0]
+ ->body()
+ ->statements()[2]
+ ->As<ast::VariableDeclStatement>()
+ ->variable());
+ ASSERT_NE(replacement_id, 0);
+ ASSERT_FALSE(MutationReplaceIdentifier(use_id, replacement_id)
+ .IsApplicable(program, node_id_map));
+}
+
+} // namespace
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/mutator.cc b/fuzzers/tint_ast_fuzzer/mutator.cc
new file mode 100644
index 0000000..f8ebb7c
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutator.cc
@@ -0,0 +1,184 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/mutator.h"
+
+#include <cassert>
+#include <memory>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+#include "fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h"
+#include "fuzzers/tint_ast_fuzzer/node_id_map.h"
+
+#include "src/program_builder.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+namespace {
+
+template <typename T, typename... Args>
+void MaybeAddFinder(bool enable_all_mutations,
+ ProbabilityContext* probability_context,
+ MutationFinderList* finders,
+ Args&&... args) {
+ if (enable_all_mutations || probability_context->RandomBool()) {
+ finders->push_back(std::make_unique<T>(std::forward<Args>(args)...));
+ }
+}
+
+MutationFinderList CreateMutationFinders(
+ ProbabilityContext* probability_context,
+ bool enable_all_mutations) {
+ MutationFinderList result;
+ do {
+ MaybeAddFinder<MutationFinderReplaceIdentifiers>(
+ enable_all_mutations, probability_context, &result);
+ } while (result.empty());
+ return result;
+}
+
+} // namespace
+
+bool MaybeApplyMutation(const tint::Program& program,
+ const Mutation& mutation,
+ const NodeIdMap& node_id_map,
+ tint::Program* out_program,
+ NodeIdMap* out_node_id_map,
+ protobufs::MutationSequence* mutation_sequence) {
+ assert(out_program && "`out_program` may not be a nullptr");
+ assert(out_node_id_map && "`out_node_id_map` may not be a nullptr");
+
+ if (!mutation.IsApplicable(program, node_id_map)) {
+ return false;
+ }
+
+ // The mutated `program` will be copied into the `mutated` program builder.
+ tint::ProgramBuilder mutated;
+ tint::CloneContext clone_context(&mutated, &program);
+ NodeIdMap new_node_id_map;
+ clone_context.ReplaceAll(
+ [&node_id_map, &new_node_id_map, &clone_context](ast::Node* node) {
+ // Make sure all `tint::ast::` nodes' ids are preserved.
+ auto* cloned = tint::As<ast::Node>(node->Clone(&clone_context));
+ new_node_id_map.Add(cloned, node_id_map.GetId(node));
+ return cloned;
+ });
+
+ mutation.Apply(node_id_map, &clone_context, &new_node_id_map);
+ if (mutation_sequence) {
+ *mutation_sequence->add_mutation() = mutation.ToMessage();
+ }
+
+ clone_context.Clone();
+ *out_program = tint::Program(std::move(mutated));
+ *out_node_id_map = std::move(new_node_id_map);
+ return true;
+}
+
+tint::Program Replay(tint::Program program,
+ const protobufs::MutationSequence& mutation_sequence) {
+ assert(program.IsValid() && "Initial program is invalid");
+
+ NodeIdMap node_id_map(program);
+ for (const auto& mutation_message : mutation_sequence.mutation()) {
+ auto mutation = Mutation::FromMessage(mutation_message);
+ auto status = MaybeApplyMutation(program, *mutation, node_id_map, &program,
+ &node_id_map, nullptr);
+ (void)status; // `status` will be unused in release mode.
+ assert(status && "`mutation` is inapplicable - it's most likely a bug");
+ if (!program.IsValid()) {
+ // `mutation` has a bug.
+ break;
+ }
+ }
+
+ return program;
+}
+
+tint::Program Mutate(tint::Program program,
+ ProbabilityContext* probability_context,
+ bool enable_all_mutations,
+ uint32_t max_applied_mutations,
+ protobufs::MutationSequence* mutation_sequence) {
+ assert(max_applied_mutations != 0 &&
+ "Maximum number of mutations is invalid");
+ assert(program.IsValid() && "Initial program is invalid");
+
+ // The number of allowed failed attempts to apply mutations. If this number is
+ // exceeded, the mutator is considered stuck and the mutation session is
+ // stopped.
+ const uint32_t kMaxFailureToApply = 10;
+
+ auto finders =
+ CreateMutationFinders(probability_context, enable_all_mutations);
+ NodeIdMap node_id_map(program);
+
+ // Total number of applied mutations during this call to `Mutate`.
+ uint32_t applied_mutations = 0;
+
+ // The number of consecutively failed attempts to apply mutations.
+ uint32_t failure_to_apply = 0;
+
+ // Apply mutations as long as the `program` is valid, the limit on the number
+ // of mutations is not reached and the mutator is not stuck (i.e. unable to
+ // apply any mutations for some time).
+ while (program.IsValid() && applied_mutations < max_applied_mutations &&
+ failure_to_apply < kMaxFailureToApply) {
+ // Get all applicable mutations from some mutation finder.
+ const auto& mutation_finder =
+ finders[probability_context->GetRandomIndex(finders)];
+ auto mutations = mutation_finder->FindMutations(program, node_id_map,
+ probability_context);
+
+ const auto old_applied_mutations = applied_mutations;
+ for (const auto& mutation : mutations) {
+ if (!probability_context->ChoosePercentage(
+ mutation_finder->GetChanceOfApplyingMutation(
+ probability_context))) {
+ // Skip this `mutation` probabilistically.
+ continue;
+ }
+
+ if (!MaybeApplyMutation(program, *mutation, node_id_map, &program,
+ &node_id_map, mutation_sequence)) {
+ // This `mutation` is inapplicable. This may happen if some of the
+ // earlier mutations cancelled this one.
+ continue;
+ }
+
+ applied_mutations++;
+ if (!program.IsValid()) {
+ // This `mutation` has a bug.
+ return program;
+ }
+ }
+
+ if (old_applied_mutations == applied_mutations) {
+ // No mutation was applied. Increase the counter to prevent an infinite
+ // loop.
+ failure_to_apply++;
+ } else {
+ failure_to_apply = 0;
+ }
+ }
+
+ return program;
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/mutator.h b/fuzzers/tint_ast_fuzzer/mutator.h
new file mode 100644
index 0000000..7746e6a
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/mutator.h
@@ -0,0 +1,102 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_MUTATOR_H_
+#define FUZZERS_TINT_AST_FUZZER_MUTATOR_H_
+
+#include "fuzzers/tint_ast_fuzzer/mutation.h"
+#include "fuzzers/tint_ast_fuzzer/mutation_finder.h"
+#include "fuzzers/tint_ast_fuzzer/node_id_map.h"
+#include "fuzzers/tint_ast_fuzzer/probability_context.h"
+#include "fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.h"
+#include "fuzzers/tint_ast_fuzzer/random_number_generator.h"
+
+#include "src/program.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+/// @file
+
+/// @brief Tries to apply a `mutation` to the `program`.
+///
+/// If the `mutation` is inapplicable, this function will return `false` and
+/// `out_program`, `out_node_id_map` and `mutation_sequence` won't be modified.
+///
+/// The `mutation` is required to produce a valid program when the
+/// `Mutation::Apply` method is called. This guarantees that this function
+/// returns a valid program as well.
+///
+/// @param program - the initial program (must be valid).
+/// @param mutation - the mutation that will be applied.
+/// @param node_id_map - a map from `tint::ast::` nodes in the `program` to
+/// their unique ids.
+/// @param out_program - the resulting mutated program will be written through
+/// this pointer. It may *not* be a `nullptr`. It _may_ point to `program`,
+/// so that a program can be updated in place.
+/// @param out_node_id_map - will contain new ids for the AST nodes in the
+/// mutated program. It may *not* be a `nullptr`. It _may_ point to
+/// `node_id_map`, so that a map can be updated in place.
+/// @param mutation_sequence - the message about this mutation will be recorded
+/// here. It may be a `nullptr`, in which case it's ignored.
+/// @return `true` if the `mutation` was applied.
+/// @return `false` if the `mutation` is inapplicable.
+bool MaybeApplyMutation(const tint::Program& program,
+ const Mutation& mutation,
+ const NodeIdMap& node_id_map,
+ tint::Program* out_program,
+ NodeIdMap* out_node_id_map,
+ protobufs::MutationSequence* mutation_sequence);
+
+/// @brief Applies mutations from `mutations_sequence` to the `program`.
+///
+/// All mutations in `mutation_sequence` must be applicable. Additionally, all
+/// mutations must produce a valid program when the `Mutation::Apply` method is
+/// called. This guarantees that this function returns a valid program as well.
+///
+/// @param program - the initial program - must be valid.
+/// @param mutation_sequence - a sequence of mutations.
+/// @return the mutated program.
+tint::Program Replay(tint::Program program,
+ const protobufs::MutationSequence& mutation_sequence);
+
+/// @brief Applies up to `max_applied_mutations` mutations to the `program`.
+///
+/// All applied mutations must produce valid programs. This guarantees that the
+/// returned program is valid as well. The returned program may be identical to
+/// the initial `program` if no mutation was applied.
+///
+/// @param program - initial program - must be valid.
+/// @param probability_context - contains information about various
+/// probabilistic behaviour of the fuzzer.
+/// @param enable_all_mutations - if `false`, only mutations from a
+/// probabilistically selected set of mutation types are applied. If `true`,
+/// all mutation types are considered.
+/// @param max_applied_mutations - the maximum number of applied mutations. This
+/// may not be 0.
+/// @param mutation_sequence - applied mutations will be recorded into this
+/// protobuf message. This argument may be `nullptr`, in which case it's
+/// ignored.
+/// @return the mutated program.
+tint::Program Mutate(tint::Program program,
+ ProbabilityContext* probability_context,
+ bool enable_all_mutations,
+ uint32_t max_applied_mutations,
+ protobufs::MutationSequence* mutation_sequence);
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_MUTATOR_H_
diff --git a/fuzzers/tint_ast_fuzzer/node_id_map.cc b/fuzzers/tint_ast_fuzzer/node_id_map.cc
new file mode 100644
index 0000000..bdb22eb
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/node_id_map.cc
@@ -0,0 +1,61 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/node_id_map.h"
+
+#include <cassert>
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+NodeIdMap::NodeIdMap() = default;
+
+NodeIdMap::NodeIdMap(const tint::Program& program) : NodeIdMap() {
+ for (const auto* node : program.ASTNodes().Objects()) {
+ Add(node, TakeFreshId());
+ }
+}
+
+NodeIdMap::IdType NodeIdMap::GetId(const ast::Node* node) const {
+ auto it = node_to_id_.find(node);
+ return it == node_to_id_.end() ? 0 : it->second;
+}
+
+const ast::Node* NodeIdMap::GetNode(IdType id) const {
+ auto it = id_to_node_.find(id);
+ return it == id_to_node_.end() ? nullptr : it->second;
+}
+
+void NodeIdMap::Add(const ast::Node* node, IdType id) {
+ assert(!node_to_id_.count(node) && "The node already exists in the map");
+ assert(!id_to_node_.count(id) && "Id already exists in the map");
+ assert(node && "`node` can't be a nullptr");
+ assert(id && "`id` can't be equal to 0");
+
+ node_to_id_[node] = id;
+ id_to_node_[id] = node;
+ if (id >= fresh_id_) {
+ fresh_id_ = id + 1;
+ }
+}
+
+NodeIdMap::IdType NodeIdMap::TakeFreshId() {
+ assert(fresh_id_ != 0 && "`NodeIdMap` id has overflowed");
+ return fresh_id_++;
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/node_id_map.h b/fuzzers/tint_ast_fuzzer/node_id_map.h
new file mode 100644
index 0000000..e6e2e3d
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/node_id_map.h
@@ -0,0 +1,89 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_
+#define FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_
+
+#include <unordered_map>
+
+#include "src/program.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// Contains a one-to-one mapping between the nodes in the AST of the program
+/// and their ids.
+///
+/// The motivation for having this mapping is:
+/// - To be able to uniquely identify a node in the AST. This will be used
+/// to record transformations in the protobuf messages.
+/// - When the AST is being modified, only the mapping for the modified nodes
+/// must be affected. That is, if some node is unchanged, it must have the
+/// same id defined in this class.
+///
+/// This class achieves these goals partially. Concretely, the only way to
+/// change the AST is by cloning it since all instances of `tint::ast::` classes
+/// are immutable. This will invalidate all the pointers to the AST nodes which
+/// are used in this class. To overcome this, a new instance of this class is
+/// created with all the cloned nodes and the old instance is discarded.
+class NodeIdMap {
+ public:
+ /// Type of the id used by this map.
+ using IdType = uint32_t;
+
+ /// Creates an empty map.
+ NodeIdMap();
+
+ /// @brief Initializes this instance with all the nodes in the `program`.
+ /// @param program - must be valid.
+ explicit NodeIdMap(const tint::Program& program);
+
+ /// @brief Returns a node for the given `id`.
+ /// @param id - any value is accepted.
+ /// @return a pointer to some node if `id` exists in this map.
+ /// @return `nullptr` otherwise.
+ const ast::Node* GetNode(IdType id) const;
+
+ /// @brief Returns an id of the given `node`.
+ /// @param node - can be a `nullptr`.
+ /// @return not equal to 0 if `node` exists in this map.
+ /// @return 0 otherwise.
+ IdType GetId(const ast::Node* node) const;
+
+ /// @brief Adds a mapping from `node` to `id` to this map.
+ /// @param node - may not be a `nullptr` and can't be present in this map.
+ /// @param id - may not be 0 and can't be present in this map.
+ void Add(const ast::Node* node, IdType id);
+
+ /// @brief Returns an id that is guaranteed to be unoccupied in this map.
+ ///
+ /// This will effectively increase the counter. This means that two
+ /// consecutive calls to this method will return different ids.
+ ///
+ /// @return an unoccupied id.
+ IdType TakeFreshId();
+
+ private:
+ IdType fresh_id_ = 1;
+
+ std::unordered_map<const ast::Node*, IdType> node_to_id_;
+ std::unordered_map<IdType, const ast::Node*> id_to_node_;
+};
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_NODE_ID_MAP_H_
diff --git a/fuzzers/tint_ast_fuzzer/probability_context.cc b/fuzzers/tint_ast_fuzzer/probability_context.cc
new file mode 100644
index 0000000..1b38a10
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/probability_context.cc
@@ -0,0 +1,39 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/probability_context.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+namespace {
+
+const std::pair<uint32_t, uint32_t> kChanceOfReplacingIdentifiers = {30, 70};
+
+} // namespace
+
+ProbabilityContext::ProbabilityContext(RandomNumberGenerator* rng)
+ : rng_(rng),
+ chance_of_replacing_identifiers_(
+ RandomFromRange(kChanceOfReplacingIdentifiers)) {}
+
+uint32_t ProbabilityContext::RandomFromRange(
+ std::pair<uint32_t, uint32_t> range) {
+ assert(range.first <= range.second && "Range must be non-decreasing");
+ return range.first + rng_->RandomUint32(range.second - range.first + 1);
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/probability_context.h b/fuzzers/tint_ast_fuzzer/probability_context.h
new file mode 100644
index 0000000..572f125
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/probability_context.h
@@ -0,0 +1,72 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_PROBABILITY_CONTEXT_H_
+#define FUZZERS_TINT_AST_FUZZER_PROBABILITY_CONTEXT_H_
+
+#include <utility>
+#include <vector>
+
+#include "fuzzers/tint_ast_fuzzer/random_number_generator.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// This class is intended to be used by the `MutationFinder`s to introduce some
+/// variance to the mutation process.
+class ProbabilityContext {
+ public:
+ /// Initializes this instance with a random number generator.
+ /// @param rng - may not be a `nullptr`. Must remain in scope as long as this
+ /// instance exists.
+ explicit ProbabilityContext(RandomNumberGenerator* rng);
+
+ /// @copydoc RandomNumberGenerator::RandomBool
+ bool RandomBool() { return rng_->RandomBool(); }
+
+ /// @copydoc RandomNumberGenerator::ChoosePercentage
+ bool ChoosePercentage(uint32_t percentage) {
+ return rng_->ChoosePercentage(percentage);
+ }
+
+ /// Returns a random value in the range `[0; arr.size())`.
+ /// @tparam T - type of the elements in the vector.
+ /// @param arr - may not be empty.
+ /// @return the random index in the `arr`.
+ template <typename T>
+ size_t GetRandomIndex(const std::vector<T>& arr) {
+ return static_cast<size_t>(rng_->RandomUint64(arr.size()));
+ }
+
+ /// @return the probability of replacing some identifier with some other one.
+ uint32_t GetChanceOfReplacingIdentifiers() const {
+ return chance_of_replacing_identifiers_;
+ }
+
+ private:
+ /// @param range - a pair of integers `a` and `b` s.t. `a <= b`.
+ /// @return an random number in the range `[a; b]`.
+ uint32_t RandomFromRange(std::pair<uint32_t, uint32_t> range);
+
+ RandomNumberGenerator* rng_;
+
+ uint32_t chance_of_replacing_identifiers_;
+};
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_PROBABILITY_CONTEXT_H_
diff --git a/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.h b/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.h
new file mode 100644
index 0000000..9439ed3
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.h
@@ -0,0 +1,33 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_PROTOBUFS_TINT_AST_FUZZER_H_
+#define FUZZERS_TINT_AST_FUZZER_PROTOBUFS_TINT_AST_FUZZER_H_
+
+// Compilation of the protobuf library and its autogenerated code can produce
+// warnings. Ignore them since we can't control them.
+#pragma clang diagnostic push
+#pragma clang diagnostic ignored "-Wunused-parameter"
+#pragma clang diagnostic ignored "-Wreserved-id-macro"
+#pragma clang diagnostic ignored "-Wsign-conversion"
+#pragma clang diagnostic ignored "-Wzero-as-null-pointer-constant"
+#pragma clang diagnostic ignored "-Wextra-semi-stmt"
+#pragma clang diagnostic ignored "-Winconsistent-missing-destructor-override"
+#pragma clang diagnostic ignored "-Wweak-vtables"
+
+#include "fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.pb.h"
+
+#pragma clang diagnostic pop
+
+#endif // FUZZERS_TINT_AST_FUZZER_PROTOBUFS_TINT_AST_FUZZER_H_
diff --git a/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.proto b/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.proto
new file mode 100644
index 0000000..3682a0c
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.proto
@@ -0,0 +1,48 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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.
+
+syntax = "proto3";
+
+package tint.fuzzers.ast_fuzzer.protobufs;
+
+message Mutation {
+ oneof mutation { MutationReplaceIdentifier replace_identifier = 1; };
+}
+
+message MutationSequence {
+ repeated Mutation mutation = 1;
+}
+
+message MutatorState {
+ // Contains the state of the fuzzer.
+
+ // The program that is being fuzzed. This can be either
+ // the original program (if mutation sequence is available) or
+ // the mutated version (if mutations are being recorded).
+ string program = 1;
+
+ // The sequence of mutations that was applied to the `program`.
+ // This may not have any mutations if they are not being recorded.
+ MutationSequence mutation_sequence = 2;
+}
+
+message MutationReplaceIdentifier {
+ // This transformation replaces a use of one variable with another.
+
+ // The id of the use of a variable in the AST.
+ uint32 use_id = 1;
+
+ // The id of a definition of a variable to replace the use with.
+ uint32 replacement_id = 2;
+}
diff --git a/fuzzers/tint_ast_fuzzer/random_number_generator.cc b/fuzzers/tint_ast_fuzzer/random_number_generator.cc
new file mode 100644
index 0000000..6d32e38
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/random_number_generator.cc
@@ -0,0 +1,37 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 "fuzzers/tint_ast_fuzzer/random_number_generator.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+RandomNumberGenerator::~RandomNumberGenerator() = default;
+
+bool RandomNumberGenerator::RandomBool() {
+ return RandomUint32(2);
+}
+
+bool RandomNumberGenerator::ChoosePercentage(uint32_t percentage) {
+ assert(percentage <= 100 && "|percentage| is invalid");
+ // 100 is used as a bound instead of 101 because otherwise it would be
+ // possible to return `false` when `percentage == 100` holds. This would
+ // happen when the result of `RandomUint32` is 100 as well.
+ return RandomUint32(100) < percentage;
+}
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
diff --git a/fuzzers/tint_ast_fuzzer/random_number_generator.h b/fuzzers/tint_ast_fuzzer/random_number_generator.h
new file mode 100644
index 0000000..27b1b54
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/random_number_generator.h
@@ -0,0 +1,57 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_RANDOM_NUMBER_GENERATOR_H_
+#define FUZZERS_TINT_AST_FUZZER_RANDOM_NUMBER_GENERATOR_H_
+
+#include <cassert>
+#include <cstdint>
+#include <vector>
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+
+/// Abstracts away the underlying algorithm that is used to generate random
+/// numbers.
+class RandomNumberGenerator {
+ public:
+ /// Virtual destructor.
+ virtual ~RandomNumberGenerator();
+
+ /// @brief Compute a random `uint32_t` value in the range `[0; bound)`.
+ /// @param bound - the upper exclusive bound for the computed integer
+ /// (must be positive).
+ /// @return the random number.
+ virtual uint32_t RandomUint32(uint32_t bound) = 0;
+
+ /// @brief Compute a random `uint64_t` value in the range `[0; bound)`.
+ /// @param bound - the upper exclusive bound for the computed integer
+ /// (must be positive).
+ /// @return the random number.
+ virtual uint64_t RandomUint64(uint64_t bound) = 0;
+
+ /// @return a randomly generated boolean value.
+ bool RandomBool();
+
+ /// @param percentage - must be in the range `[0; 100]`.
+ /// @return `true` with `percentage` probability.
+ bool ChoosePercentage(uint32_t percentage);
+};
+
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_RANDOM_NUMBER_GENERATOR_H_
diff --git a/fuzzers/tint_ast_fuzzer/util.h b/fuzzers/tint_ast_fuzzer/util.h
new file mode 100644
index 0000000..ec2f5ee
--- /dev/null
+++ b/fuzzers/tint_ast_fuzzer/util.h
@@ -0,0 +1,107 @@
+// Copyright 2021 The Tint Authors.
+//
+// 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 FUZZERS_TINT_AST_FUZZER_UTIL_H_
+#define FUZZERS_TINT_AST_FUZZER_UTIL_H_
+
+#include <vector>
+
+#include "src/ast/module.h"
+#include "src/ast/variable_decl_statement.h"
+#include "src/program.h"
+#include "src/sem/block_statement.h"
+#include "src/sem/statement.h"
+#include "src/sem/variable.h"
+
+namespace tint {
+namespace fuzzers {
+namespace ast_fuzzer {
+namespace util {
+/// @file
+
+/// @brief Returns all in-scope variables (including formal function parameters)
+/// related to statement `curr_stmt`.
+///
+/// These variables are additionally filtered by applying a predicate `pred`.
+///
+/// @tparam Pred - a predicate that accepts a `const sem::Variable*` and returns
+/// `bool`.
+/// @param program - the program to look for variables in.
+/// @param curr_stmt - the current statement. Everything below it is not in
+/// scope.
+/// @param pred - a predicate (e.g. a function pointer, functor, lambda etc) of
+/// type `Pred`.
+/// @return a vector of all variables that can be accessed from `curr_stmt`.
+template <typename Pred>
+std::vector<const sem::Variable*> GetAllVarsInScope(
+ const tint::Program& program,
+ const sem::Statement* curr_stmt,
+ Pred&& pred) {
+ std::vector<const sem::Variable*> result;
+
+ // Walk up the hierarchy of blocks in which `curr_stmt` is contained.
+ for (const auto* block = curr_stmt->Block(); block; block = block->Block()) {
+ for (const auto* stmt : *block->Declaration()) {
+ if (stmt == curr_stmt->Declaration()) {
+ // `curr_stmt` was found. This is only possible if `block is the
+ // enclosing block of `curr_stmt` since the AST nodes are not shared.
+ // Because of all this, skip the iteration of the inner loop since
+ // the rest of the instructions in the `block` are not visible from the
+ // `curr_stmt`.
+ break;
+ }
+
+ if (const auto* var_node = tint::As<ast::VariableDeclStatement>(stmt)) {
+ const auto* sem_var = program.Sem().Get(var_node->variable());
+ if (pred(sem_var)) {
+ result.push_back(sem_var);
+ }
+ }
+ }
+ }
+
+ // Process function parameters.
+ for (const auto* param : curr_stmt->Function()->params()) {
+ const auto* sem_var = program.Sem().Get(param);
+ if (pred(sem_var)) {
+ result.push_back(sem_var);
+ }
+ }
+
+ // Global variables do not belong to any ast::BlockStatement.
+ for (const auto* global_decl : program.AST().GlobalDeclarations()) {
+ if (global_decl == curr_stmt->Function()) {
+ // The same situation as in the previous loop. The current function has
+ // been reached. If there are any variables declared below, they won't be
+ // visible in this function. Thus, exit the loop.
+ break;
+ }
+
+ if (const auto* global_var = tint::As<ast::Variable>(global_decl)) {
+ const auto* sem_node = program.Sem().Get(global_var);
+ if (pred(sem_node)) {
+ result.push_back(sem_node);
+ }
+ }
+ }
+
+ return result;
+}
+
+} // namespace util
+} // namespace ast_fuzzer
+} // namespace fuzzers
+} // namespace tint
+
+#endif // FUZZERS_TINT_AST_FUZZER_UTIL_H_
diff --git a/third_party/CMakeLists.txt b/third_party/CMakeLists.txt
index 230d66e..fcf025d 100644
--- a/third_party/CMakeLists.txt
+++ b/third_party/CMakeLists.txt
@@ -17,8 +17,11 @@
add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/googletest EXCLUDE_FROM_ALL)
endif()
-if (${TINT_BUILD_SPIRV_TOOLS_FUZZER} AND (NOT TARGET protobuf::libprotobuf OR NOT TARGET protobuf::protoc))
- set(SPIRV_BUILD_FUZZER ON CACHE BOOL "Build spirv-fuzz")
+if ((${TINT_BUILD_SPIRV_TOOLS_FUZZER} OR ${TINT_BUILD_AST_FUZZER}) AND
+ (NOT TARGET protobuf::libprotobuf OR NOT TARGET protobuf::protoc))
+ if (${TINT_BUILD_SPIRV_TOOLS_FUZZER})
+ set(SPIRV_BUILD_FUZZER ON CACHE BOOL "Build spirv-fuzz")
+ endif()
set(protobuf_BUILD_TESTS OFF CACHE BOOL "Disable protobuf tests")
set(protobuf_MSVC_STATIC_RUNTIME OFF CACHE BOOL "Do not build protobuf static runtime")
add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/protobuf/cmake)
