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)