AST fuzzer: mutation that deletes statements
Adds a mutation that deletes a statement.
Fixes: tint:1110
Change-Id: I8a8595378481d12e7586103e2e88a0858d869ef9
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/88446
Commit-Queue: Alastair Donaldson <afdx@google.com>
Reviewed-by: Ryan Harrison <rharrison@chromium.org>
Kokoro: Kokoro <noreply+kokoro@google.com>
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/BUILD.gn b/src/tint/fuzzers/tint_ast_fuzzer/BUILD.gn
index 69ef3fe..58a36ea 100644
--- a/src/tint/fuzzers/tint_ast_fuzzer/BUILD.gn
+++ b/src/tint/fuzzers/tint_ast_fuzzer/BUILD.gn
@@ -46,6 +46,8 @@
"expression_size.cc",
"expression_size.h",
"fuzzer.cc",
+ "jump_tracker.cc",
+ "jump_tracker.h",
"mutation.cc",
"mutation.h",
"mutation_finder.cc",
@@ -54,6 +56,8 @@
"mutation_finders/change_binary_operators.h",
"mutation_finders/change_unary_operators.cc",
"mutation_finders/change_unary_operators.h",
+ "mutation_finders/delete_statements.cc",
+ "mutation_finders/delete_statements.h",
"mutation_finders/replace_identifiers.cc",
"mutation_finders/replace_identifiers.h",
"mutation_finders/wrap_unary_operators.cc",
@@ -62,6 +66,8 @@
"mutations/change_binary_operator.h",
"mutations/change_unary_operator.cc",
"mutations/change_unary_operator.h",
+ "mutations/delete_statement.cc",
+ "mutations/delete_statement.h",
"mutations/replace_identifier.cc",
"mutations/replace_identifier.h",
"mutations/wrap_unary_operator.cc",
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/CMakeLists.txt b/src/tint/fuzzers/tint_ast_fuzzer/CMakeLists.txt
index 5bd8c50..0d1f5a2 100644
--- a/src/tint/fuzzers/tint_ast_fuzzer/CMakeLists.txt
+++ b/src/tint/fuzzers/tint_ast_fuzzer/CMakeLists.txt
@@ -39,14 +39,17 @@
../random_generator.h
../random_generator_engine.h
expression_size.h
+ jump_tracker.h
mutation.h
mutation_finder.h
mutation_finders/change_binary_operators.h
mutation_finders/change_unary_operators.h
+ mutation_finders/delete_statements.h
mutation_finders/replace_identifiers.h
mutation_finders/wrap_unary_operators.h
mutations/change_binary_operator.h
mutations/change_unary_operator.h
+ mutations/delete_statement.h
mutations/replace_identifier.h
mutations/wrap_unary_operator.h
mutator.h
@@ -61,14 +64,17 @@
../random_generator.cc
../random_generator_engine.cc
expression_size.cc
+ jump_tracker.cc
mutation.cc
mutation_finder.cc
mutation_finders/change_binary_operators.cc
mutation_finders/change_unary_operators.cc
+ mutation_finders/delete_statements.cc
mutation_finders/replace_identifiers.cc
mutation_finders/wrap_unary_operators.cc
mutations/change_binary_operator.cc
mutations/change_unary_operator.cc
+ mutations/delete_statement.cc
mutations/replace_identifier.cc
mutations/wrap_unary_operator.cc
mutator.cc
@@ -107,8 +113,10 @@
if (${TINT_BUILD_TESTS})
set(TEST_SOURCES
expression_size_test.cc
+ jump_tracker_test.cc
mutations/change_binary_operator_test.cc
mutations/change_unary_operator_test.cc
+ mutations/delete_statement_test.cc
mutations/replace_identifier_test.cc
mutations/wrap_unary_operator_test.cc)
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.cc b/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.cc
new file mode 100644
index 0000000..66bbaf7
--- /dev/null
+++ b/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.cc
@@ -0,0 +1,83 @@
+// Copyright 2022 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 "src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.h"
+
+#include <cassert>
+#include <unordered_set>
+
+#include "src/tint/ast/break_statement.h"
+#include "src/tint/ast/discard_statement.h"
+#include "src/tint/ast/for_loop_statement.h"
+#include "src/tint/ast/loop_statement.h"
+#include "src/tint/ast/return_statement.h"
+#include "src/tint/ast/switch_statement.h"
+#include "src/tint/ast/while_statement.h"
+#include "src/tint/sem/statement.h"
+
+namespace tint::fuzzers::ast_fuzzer {
+
+JumpTracker::JumpTracker(const Program& program) {
+ // Consider every AST node, looking for break, return and discard statements.
+ for (auto* node : program.ASTNodes().Objects()) {
+ auto* stmt = node->As<ast::Statement>();
+ if (stmt == nullptr) {
+ continue;
+ }
+ if (stmt->As<ast::BreakStatement>()) {
+ // This break statement either exits a loop or a switch statement.
+ // Walk up the AST until either a loop or switch statement is found. In the former case,
+ // it is the innermost loop containing the break statement, and thus all the nodes
+ // encountered along the way are nodes that contain a break from the innermost loop.
+
+ // This records the statements encountered when walking up the AST from the break
+ // statement to the innermost enclosing loop or switch statement.
+ std::unordered_set<const ast::Statement*> candidate_statements;
+ for (const ast::Statement* current = stmt;;
+ current =
+ As<sem::Statement>(program.Sem().Get(current))->Parent()->Declaration()) {
+ if (current->Is<ast::ForLoopStatement>() || current->Is<ast::LoopStatement>() ||
+ current->Is<ast::WhileStatement>()) {
+ // A loop has been encountered, thus all that statements recorded until this
+ // point contain a break from their innermost loop.
+ for (auto* candidate : candidate_statements) {
+ contains_break_for_innermost_loop_.insert(candidate);
+ }
+ break;
+ }
+ if (current->Is<ast::SwitchStatement>()) {
+ // A switch statement has been encountered, so the break does not correspond to
+ // a loop break.
+ break;
+ }
+ candidate_statements.insert(current);
+ }
+ } else if (stmt->As<ast::ReturnStatement>() || stmt->As<ast::DiscardStatement>()) {
+ // Walk up the AST from the return or discard statement, recording that every node
+ // encountered along the way contains a return/discard.
+ auto& target_set = stmt->As<ast::ReturnStatement>() ? contains_return_
+ : contains_intraprocedural_discard_;
+ const ast::Statement* current = stmt;
+ while (true) {
+ target_set.insert(current);
+ auto* parent = program.Sem().Get(current)->Parent();
+ if (parent == nullptr) {
+ break;
+ }
+ current = parent->Declaration();
+ }
+ }
+ }
+}
+} // namespace tint::fuzzers::ast_fuzzer
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.h b/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.h
new file mode 100644
index 0000000..614ceb5
--- /dev/null
+++ b/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.h
@@ -0,0 +1,68 @@
+// Copyright 2022 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 SRC_TINT_FUZZERS_TINT_AST_FUZZER_JUMP_TRACKER_H_
+#define SRC_TINT_FUZZERS_TINT_AST_FUZZER_JUMP_TRACKER_H_
+
+#include <unordered_set>
+
+#include "src/tint/ast/statement.h"
+#include "src/tint/program.h"
+
+namespace tint::fuzzers::ast_fuzzer {
+
+/// This class computes information on which statements contain loop breaks, returns and discards.
+/// It could be extended to handle other jumps, such as switch breaks and loop continues, should
+/// such information prove useful.
+class JumpTracker {
+ public:
+ /// Initializes jump tracking information for the given program.
+ /// @param program - the program for which jumps will be tracked;
+ /// must remain in scope as long as this instance exists.
+ explicit JumpTracker(const Program& program);
+
+ /// Indicates whether a statement contains a break statement for the innermost loop (if any).
+ /// @param statement - the statement of interest.
+ /// @return true if and only if the statement is, or contains, a break for the innermost
+ /// enclosing loop.
+ bool ContainsBreakForInnermostLoop(const ast::Statement& statement) const {
+ return contains_break_for_innermost_loop_.count(&statement) > 0;
+ }
+
+ /// Indicates whether a statement contains a return statement.
+ /// @param statement - the statement of interest.
+ /// @return true if and only if the statement is, or contains, a return statement.
+ bool ContainsReturn(const ast::Statement& statement) const {
+ return contains_return_.count(&statement) > 0;
+ }
+
+ /// Indicates whether a statement contains a discard statement.
+ /// @param statement - the statement of interest.
+ /// @return true if and only if the statement is, or contains, a discard statement. This is
+ /// determined in an intraprocedural fashion: the answer will be "false" if no discard occurs
+ /// inside the statement, even if the statement calls a function that may lead to a discard
+ /// being performed.
+ bool ContainsIntraproceduralDiscard(const ast::Statement& statement) const {
+ return contains_intraprocedural_discard_.count(&statement) > 0;
+ }
+
+ private:
+ std::unordered_set<const ast::Statement*> contains_break_for_innermost_loop_;
+ std::unordered_set<const ast::Statement*> contains_return_;
+ std::unordered_set<const ast::Statement*> contains_intraprocedural_discard_;
+};
+
+} // namespace tint::fuzzers::ast_fuzzer
+
+#endif // SRC_TINT_FUZZERS_TINT_AST_FUZZER_JUMP_TRACKER_H_
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker_test.cc b/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker_test.cc
new file mode 100644
index 0000000..f83e639
--- /dev/null
+++ b/src/tint/fuzzers/tint_ast_fuzzer/jump_tracker_test.cc
@@ -0,0 +1,332 @@
+// Copyright 2022 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 "src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.h"
+
+#include <string>
+
+#include "gtest/gtest.h"
+
+#include "src/tint/ast/block_statement.h"
+#include "src/tint/ast/break_statement.h"
+#include "src/tint/ast/discard_statement.h"
+#include "src/tint/ast/for_loop_statement.h"
+#include "src/tint/ast/if_statement.h"
+#include "src/tint/ast/loop_statement.h"
+#include "src/tint/ast/module.h"
+#include "src/tint/ast/return_statement.h"
+#include "src/tint/ast/switch_statement.h"
+#include "src/tint/ast/while_statement.h"
+#include "src/tint/program.h"
+#include "src/tint/reader/wgsl/parser.h"
+
+namespace tint::fuzzers::ast_fuzzer {
+namespace {
+
+TEST(JumpTrackerTest, Breaks) {
+ std::string content = R"(
+fn main() {
+ var x : u32;
+ for (var i : i32 = 0; i < 100; i++) {
+ if (i == 40) {
+ {
+ break;
+ }
+ }
+ for (var j : i32 = 0; j < 10; j++) {
+ loop {
+ if (i > j) {
+ break;
+ }
+ continuing {
+ i++;
+ j-=2;
+ }
+ }
+ switch (j) {
+ case 0: {
+ if (i == j) {
+ break;
+ }
+ i = i + 1;
+ continue;
+ }
+ default: {
+ break;
+ }
+ }
+ }
+ }
+}
+ )";
+ Source::File file("test.wgsl", content);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ JumpTracker jump_tracker(program);
+
+ const auto* outer_loop_body =
+ program.AST().Functions()[0]->body->statements[1]->As<ast::ForLoopStatement>()->body;
+ const auto* first_if = outer_loop_body->statements[0]->As<ast::IfStatement>();
+ const auto* first_if_body = first_if->body;
+ const auto* block_in_first_if = first_if_body->statements[0]->As<ast::BlockStatement>();
+ const auto* break_in_first_if = block_in_first_if->statements[0]->As<ast::BreakStatement>();
+
+ const auto* innermost_loop_body = outer_loop_body->statements[1]
+ ->As<ast::ForLoopStatement>()
+ ->body->statements[0]
+ ->As<ast::LoopStatement>()
+ ->body;
+ const auto* innermost_loop_if = innermost_loop_body->statements[0]->As<ast::IfStatement>();
+ const auto* innermost_loop_if_body = innermost_loop_if->body;
+ const auto* break_in_innermost_loop =
+ innermost_loop_if_body->statements[0]->As<ast::BreakStatement>();
+
+ std::unordered_set<const ast::Statement*> containing_loop_break = {
+ outer_loop_body, first_if,
+ first_if_body, block_in_first_if,
+ break_in_first_if, innermost_loop_body,
+ innermost_loop_if, innermost_loop_if_body,
+ break_in_innermost_loop};
+
+ for (auto* node : program.ASTNodes().Objects()) {
+ auto* stmt = node->As<ast::Statement>();
+ if (stmt == nullptr) {
+ continue;
+ }
+ if (containing_loop_break.count(stmt) > 0) {
+ ASSERT_TRUE(jump_tracker.ContainsBreakForInnermostLoop(*stmt));
+ } else {
+ ASSERT_FALSE(jump_tracker.ContainsBreakForInnermostLoop(*stmt));
+ }
+ }
+}
+
+TEST(JumpTrackerTest, Returns) {
+ std::string content = R"(
+fn main() {
+ var x : u32;
+ for (var i : i32 = 0; i < 100; i++) {
+ if (i == 40) {
+ {
+ return;
+ }
+ }
+ for (var j : i32 = 0; j < 10; j++) {
+ loop {
+ if (i > j) {
+ return;
+ }
+ continuing {
+ i++;
+ j-=2;
+ }
+ }
+ switch (j) {
+ case 0: {
+ if (i == j) {
+ break;
+ }
+ i = i + 1;
+ continue;
+ }
+ default: {
+ return;
+ }
+ }
+ }
+ }
+}
+ )";
+ Source::File file("test.wgsl", content);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ JumpTracker jump_tracker(program);
+
+ const auto* function_body = program.AST().Functions()[0]->body;
+ const auto* outer_loop = function_body->statements[1]->As<ast::ForLoopStatement>();
+ const auto* outer_loop_body = outer_loop->body;
+ const auto* first_if = outer_loop_body->statements[0]->As<ast::IfStatement>();
+ const auto* first_if_body = first_if->body;
+ const auto* block_in_first_if = first_if_body->statements[0]->As<ast::BlockStatement>();
+ const auto* return_in_first_if = block_in_first_if->statements[0]->As<ast::ReturnStatement>();
+ const auto* inner_for_loop = outer_loop_body->statements[1]->As<ast::ForLoopStatement>();
+ const auto* inner_for_loop_body = inner_for_loop->body;
+ const auto* innermost_loop = inner_for_loop_body->statements[0]->As<ast::LoopStatement>();
+ const auto* innermost_loop_body = innermost_loop->body;
+ const auto* innermost_loop_if = innermost_loop_body->statements[0]->As<ast::IfStatement>();
+ const auto* innermost_loop_if_body = innermost_loop_if->body;
+ const auto* return_in_innermost_loop =
+ innermost_loop_if_body->statements[0]->As<ast::ReturnStatement>();
+ const auto* switch_statement = inner_for_loop_body->statements[1]->As<ast::SwitchStatement>();
+ const auto* default_statement = switch_statement->body[1];
+ const auto* default_statement_body = default_statement->body;
+ const auto* return_in_default_statement =
+ default_statement_body->statements[0]->As<ast::ReturnStatement>();
+
+ std::unordered_set<const ast::Statement*> containing_return = {
+ function_body, outer_loop,
+ outer_loop_body, first_if,
+ first_if_body, block_in_first_if,
+ return_in_first_if, inner_for_loop,
+ inner_for_loop_body, innermost_loop,
+ innermost_loop_body, innermost_loop_if,
+ innermost_loop_if_body, return_in_innermost_loop,
+ switch_statement, default_statement,
+ default_statement_body, return_in_default_statement};
+
+ for (auto* node : program.ASTNodes().Objects()) {
+ auto* stmt = node->As<ast::Statement>();
+ if (stmt == nullptr) {
+ continue;
+ }
+ if (containing_return.count(stmt) > 0) {
+ ASSERT_TRUE(jump_tracker.ContainsReturn(*stmt));
+ } else {
+ ASSERT_FALSE(jump_tracker.ContainsReturn(*stmt));
+ }
+ }
+}
+
+TEST(JumpTrackerTest, Discards) {
+ std::string content = R"(
+fn main() {
+ var x : u32;
+ for (var i : i32 = 0; i < 100; i++) {
+ if (i == 40) {
+ {
+ discard;
+ }
+ }
+ for (var j : i32 = 0; j < 10; j++) {
+ loop {
+ if (i > j) {
+ discard;
+ }
+ continuing {
+ i++;
+ j-=2;
+ }
+ }
+ switch (j) {
+ case 0: {
+ if (i == j) {
+ break;
+ }
+ i = i + 1;
+ continue;
+ }
+ default: {
+ discard;
+ }
+ }
+ }
+ }
+}
+ )";
+ Source::File file("test.wgsl", content);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ JumpTracker jump_tracker(program);
+
+ const auto* function_body = program.AST().Functions()[0]->body;
+ const auto* outer_loop = function_body->statements[1]->As<ast::ForLoopStatement>();
+ const auto* outer_loop_body = outer_loop->body;
+ const auto* first_if = outer_loop_body->statements[0]->As<ast::IfStatement>();
+ const auto* first_if_body = first_if->body;
+ const auto* block_in_first_if = first_if_body->statements[0]->As<ast::BlockStatement>();
+ const auto* discard_in_first_if = block_in_first_if->statements[0]->As<ast::DiscardStatement>();
+ const auto* inner_for_loop = outer_loop_body->statements[1]->As<ast::ForLoopStatement>();
+ const auto* inner_for_loop_body = inner_for_loop->body;
+ const auto* innermost_loop = inner_for_loop_body->statements[0]->As<ast::LoopStatement>();
+ const auto* innermost_loop_body = innermost_loop->body;
+ const auto* innermost_loop_if = innermost_loop_body->statements[0]->As<ast::IfStatement>();
+ const auto* innermost_loop_if_body = innermost_loop_if->body;
+ const auto* discard_in_innermost_loop =
+ innermost_loop_if_body->statements[0]->As<ast::DiscardStatement>();
+ const auto* switch_statement = inner_for_loop_body->statements[1]->As<ast::SwitchStatement>();
+ const auto* default_statement = switch_statement->body[1];
+ const auto* default_statement_body = default_statement->body;
+ const auto* discard_in_default_statement =
+ default_statement_body->statements[0]->As<ast::DiscardStatement>();
+
+ std::unordered_set<const ast::Statement*> containing_discard = {
+ function_body, outer_loop,
+ outer_loop_body, first_if,
+ first_if_body, block_in_first_if,
+ discard_in_first_if, inner_for_loop,
+ inner_for_loop_body, innermost_loop,
+ innermost_loop_body, innermost_loop_if,
+ innermost_loop_if_body, discard_in_innermost_loop,
+ switch_statement, default_statement,
+ default_statement_body, discard_in_default_statement};
+
+ for (auto* node : program.ASTNodes().Objects()) {
+ auto* stmt = node->As<ast::Statement>();
+ if (stmt == nullptr) {
+ continue;
+ }
+ if (containing_discard.count(stmt) > 0) {
+ ASSERT_TRUE(jump_tracker.ContainsIntraproceduralDiscard(*stmt));
+ } else {
+ ASSERT_FALSE(jump_tracker.ContainsIntraproceduralDiscard(*stmt));
+ }
+ }
+}
+
+TEST(JumpTrackerTest, WhileLoop) {
+ std::string content = R"(
+fn main() {
+ var x : u32;
+ x = 0;
+ while (x < 100) {
+ if (x > 50) {
+ break;
+ }
+ x = x + 1;
+ }
+}
+ )";
+ Source::File file("test.wgsl", content);
+ auto program = reader::wgsl::Parse(&file);
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ JumpTracker jump_tracker(program);
+
+ const auto* while_loop_body =
+ program.AST().Functions()[0]->body->statements[2]->As<ast::WhileStatement>()->body;
+ const auto* if_statement = while_loop_body->statements[0]->As<ast::IfStatement>();
+ const auto* if_statement_body = if_statement->body;
+ const auto* break_in_if = if_statement_body->statements[0]->As<ast::BreakStatement>();
+
+ std::unordered_set<const ast::Statement*> containing_loop_break = {
+ while_loop_body, if_statement, if_statement_body, break_in_if};
+
+ for (auto* node : program.ASTNodes().Objects()) {
+ auto* stmt = node->As<ast::Statement>();
+ if (stmt == nullptr) {
+ continue;
+ }
+ if (containing_loop_break.count(stmt) > 0) {
+ ASSERT_TRUE(jump_tracker.ContainsBreakForInnermostLoop(*stmt));
+ } else {
+ ASSERT_FALSE(jump_tracker.ContainsBreakForInnermostLoop(*stmt));
+ }
+ }
+}
+
+} // namespace
+} // namespace tint::fuzzers::ast_fuzzer
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/mutation.cc b/src/tint/fuzzers/tint_ast_fuzzer/mutation.cc
index 6f60fc3..62c970b 100644
--- a/src/tint/fuzzers/tint_ast_fuzzer/mutation.cc
+++ b/src/tint/fuzzers/tint_ast_fuzzer/mutation.cc
@@ -18,6 +18,7 @@
#include "src/tint/fuzzers/tint_ast_fuzzer/mutations/change_binary_operator.h"
#include "src/tint/fuzzers/tint_ast_fuzzer/mutations/change_unary_operator.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.h"
#include "src/tint/fuzzers/tint_ast_fuzzer/mutations/replace_identifier.h"
#include "src/tint/fuzzers/tint_ast_fuzzer/mutations/wrap_unary_operator.h"
@@ -33,6 +34,8 @@
return std::make_unique<MutationReplaceIdentifier>(message.replace_identifier());
case protobufs::Mutation::kChangeBinaryOperator:
return std::make_unique<MutationChangeBinaryOperator>(message.change_binary_operator());
+ case protobufs::Mutation::kDeleteStatement:
+ return std::make_unique<MutationDeleteStatement>(message.delete_statement());
case protobufs::Mutation::kWrapUnaryOperator:
return std::make_unique<MutationWrapUnaryOperator>(message.wrap_unary_operator());
case protobufs::Mutation::MUTATION_NOT_SET:
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/delete_statements.cc b/src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/delete_statements.cc
new file mode 100644
index 0000000..f1d7e4d
--- /dev/null
+++ b/src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/delete_statements.cc
@@ -0,0 +1,68 @@
+// 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 "src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/delete_statements.h"
+
+#include <memory>
+
+#include "src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/util.h"
+#include "src/tint/sem/expression.h"
+#include "src/tint/sem/statement.h"
+#include "src/tint/sem/variable.h"
+
+namespace tint::fuzzers::ast_fuzzer {
+
+MutationList MutationFinderDeleteStatements::FindMutations(const tint::Program& program,
+ NodeIdMap* node_id_map,
+ ProbabilityContext* /*unused*/) const {
+ MutationList result;
+
+ JumpTracker jump_tracker(program);
+
+ // Consider every statement node in the AST.
+ for (auto* node : program.ASTNodes().Objects()) {
+ auto* statement_node = tint::As<ast::Statement>(node);
+
+ if (!statement_node) {
+ continue;
+ }
+
+ const auto* statement_sem_node =
+ tint::As<sem::Statement>(program.Sem().Get(statement_node));
+
+ // Semantic information for the node is required in order to delete it.
+ if (!statement_sem_node) {
+ continue;
+ }
+
+ // Check that this kind of statement can be deleted.
+ if (!MutationDeleteStatement::CanBeDeleted(*statement_node, program, jump_tracker)) {
+ continue;
+ }
+
+ result.push_back(
+ std::make_unique<MutationDeleteStatement>(node_id_map->GetId(statement_node)));
+ }
+
+ return result;
+}
+
+uint32_t MutationFinderDeleteStatements::GetChanceOfApplyingMutation(
+ ProbabilityContext* probability_context) const {
+ return probability_context->GetChanceOfDeletingStatements();
+}
+
+} // namespace tint::fuzzers::ast_fuzzer
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/delete_statements.h b/src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/delete_statements.h
new file mode 100644
index 0000000..97a4cbf
--- /dev/null
+++ b/src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/delete_statements.h
@@ -0,0 +1,36 @@
+// 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 SRC_TINT_FUZZERS_TINT_AST_FUZZER_MUTATION_FINDERS_DELETE_STATEMENTS_H_
+#define SRC_TINT_FUZZERS_TINT_AST_FUZZER_MUTATION_FINDERS_DELETE_STATEMENTS_H_
+
+#include "src/tint/fuzzers/tint_ast_fuzzer/mutation_finder.h"
+
+namespace tint::fuzzers::ast_fuzzer {
+
+/// Looks for opportunities to apply
+/// `MutationFinderDeleteStatements`.
+///
+/// Considers statements for deletion if their deletion would not make the module invalid.
+class MutationFinderDeleteStatements : public MutationFinder {
+ public:
+ MutationList FindMutations(const tint::Program& program,
+ NodeIdMap* node_id_map,
+ ProbabilityContext* probability_context) const override;
+ uint32_t GetChanceOfApplyingMutation(ProbabilityContext* probability_context) const override;
+};
+
+} // namespace tint::fuzzers::ast_fuzzer
+
+#endif // SRC_TINT_FUZZERS_TINT_AST_FUZZER_MUTATION_FINDERS_DELETE_STATEMENTS_H_
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.cc b/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.cc
new file mode 100644
index 0000000..5fbbe23
--- /dev/null
+++ b/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.cc
@@ -0,0 +1,208 @@
+// 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 "src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.h"
+
+#include <algorithm>
+#include <utility>
+#include <vector>
+
+#include "src/tint/ast/block_statement.h"
+#include "src/tint/ast/fallthrough_statement.h"
+#include "src/tint/ast/for_loop_statement.h"
+#include "src/tint/ast/if_statement.h"
+#include "src/tint/ast/loop_statement.h"
+#include "src/tint/ast/variable_decl_statement.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/util.h"
+#include "src/tint/program_builder.h"
+#include "src/tint/sem/for_loop_statement.h"
+#include "src/tint/sem/if_statement.h"
+#include "src/tint/sem/loop_statement.h"
+#include "src/tint/sem/statement.h"
+
+namespace tint::fuzzers::ast_fuzzer {
+
+MutationDeleteStatement::MutationDeleteStatement(protobufs::MutationDeleteStatement message)
+ : message_(std::move(message)) {}
+
+MutationDeleteStatement::MutationDeleteStatement(uint32_t statement_id) {
+ message_.set_statement_id(statement_id);
+}
+
+bool MutationDeleteStatement::IsApplicable(const tint::Program& program,
+ const NodeIdMap& node_id_map) const {
+ auto* statement_node = tint::As<ast::Statement>(node_id_map.GetNode(message_.statement_id()));
+
+ if (!statement_node) {
+ // The statement id is invalid or does not refer to a statement.
+ return false;
+ }
+
+ const auto* statement_sem_node = tint::As<sem::Statement>(program.Sem().Get(statement_node));
+
+ if (!statement_sem_node) {
+ // Semantic information for the statement is not available. This
+ // information is required in order to perform the deletion.
+ return false;
+ }
+
+ // Check whether it is OK to delete this statement.
+ if (!CanBeDeleted(*statement_node, program, JumpTracker(program))) {
+ return false;
+ }
+
+ return true;
+}
+
+void MutationDeleteStatement::Apply(const NodeIdMap& node_id_map,
+ tint::CloneContext* clone_context,
+ NodeIdMap* /* unused */) const {
+ const auto* statement_node =
+ tint::As<ast::Statement>(node_id_map.GetNode(message_.statement_id()));
+ const auto* statement_sem_node =
+ tint::As<sem::Statement>(clone_context->src->Sem().Get(statement_node));
+ const auto* sem_parent = statement_sem_node->Parent();
+
+ if (tint::Is<sem::IfStatement>(sem_parent) &&
+ tint::As<ast::IfStatement>(sem_parent->Declaration())->else_statement == statement_node) {
+ // Remove the "else" part of an if statement.
+ clone_context->Replace(statement_node, static_cast<const ast::Statement*>(nullptr));
+ } else if (tint::Is<sem::ForLoopStatement>(sem_parent) &&
+ tint::As<ast::ForLoopStatement>(sem_parent->Declaration())->initializer ==
+ statement_node) {
+ // Remove the initializer of a for loop.
+ clone_context->Replace(statement_node, static_cast<const ast::Statement*>(nullptr));
+ } else if (tint::Is<sem::ForLoopStatement>(sem_parent) &&
+ tint::As<ast::ForLoopStatement>(sem_parent->Declaration())->continuing ==
+ statement_node) {
+ // Remove the "continuing" statement of a for loop.
+ clone_context->Replace(statement_node, static_cast<const ast::Statement*>(nullptr));
+ } else if (tint::Is<sem::LoopContinuingBlockStatement>(statement_sem_node)) {
+ // Remove the "continuing" block of a loop.
+ clone_context->Replace(statement_node, static_cast<const ast::Statement*>(nullptr));
+ } else if (tint::Is<ast::CaseStatement>(statement_node)) {
+ // Remove a case statement from its enclosing switch statement.
+ const std::vector<const ast::CaseStatement*>* case_statement_list =
+ &sem_parent->Declaration()->As<ast::SwitchStatement>()->body;
+ assert(std::find(case_statement_list->begin(), case_statement_list->end(),
+ statement_node) != case_statement_list->end() &&
+ "Statement not found.");
+ clone_context->Remove(*case_statement_list, statement_node);
+ } else if (tint::Is<ast::BlockStatement>(statement_node)) {
+ // Remove a block statement from the block that encloses it. A special case is required for
+ // this, since a sem::Block has itself as its associated sem::Block, so it is necessary to
+ // look at the parent to get the enclosing block.
+ const auto& statement_list =
+ sem_parent->Declaration()->As<ast::BlockStatement>()->statements;
+ assert(std::find(statement_list.begin(), statement_list.end(), statement_node) !=
+ statement_list.end() &&
+ "Statement not found.");
+ clone_context->Remove(statement_list, statement_node);
+ } else {
+ // Remove a non-block statement from the block that encloses it.
+ const auto& statement_list =
+ statement_sem_node->Block()->Declaration()->As<ast::BlockStatement>()->statements;
+ assert(std::find(statement_list.begin(), statement_list.end(), statement_node) !=
+ statement_list.end() &&
+ "Statement not found.");
+ clone_context->Remove(statement_list, statement_node);
+ }
+}
+
+protobufs::Mutation MutationDeleteStatement::ToMessage() const {
+ protobufs::Mutation mutation;
+ *mutation.mutable_delete_statement() = message_;
+ return mutation;
+}
+
+bool MutationDeleteStatement::CanBeDeleted(const ast::Statement& statement_node,
+ const Program& program,
+ const JumpTracker& jump_tracker) {
+ if (statement_node.Is<ast::VariableDeclStatement>()) {
+ // This is conservative. It would be possible to delete variable declarations if they are
+ // not used. Further analysis could allow that.
+ return false;
+ }
+
+ if (jump_tracker.ContainsReturn(statement_node) ||
+ jump_tracker.ContainsIntraproceduralDiscard(statement_node)) {
+ // This is conservative. It would be possible to delete a return/discard statement as long
+ // as there is still a return/discard on every control flow path.
+ return false;
+ }
+
+ if (jump_tracker.ContainsBreakForInnermostLoop(statement_node)) {
+ // This is conservative. Disallowing the removal of breaks ensures that loops cannot become
+ // statically infinite. However, a loop might in practice have multiple breaks, some of
+ // which can be removed.
+ return false;
+ }
+
+ if (auto* case_statement = statement_node.As<ast::CaseStatement>()) {
+ // It is not OK to delete the final case statement in a switch statement if the penultimate
+ // case statement falls through to the final case statement.
+ auto* switch_statement =
+ program.Sem().Get(case_statement)->Parent()->Declaration()->As<ast::SwitchStatement>();
+
+ if (switch_statement->body.size() > 1 &&
+ switch_statement->body[switch_statement->body.size() - 1] == case_statement) {
+ // There are at least two case statements, and this is the final case statement.
+ auto& penultimate_case_statement_body_statements =
+ switch_statement->body[switch_statement->body.size() - 2]->body->statements;
+ if (penultimate_case_statement_body_statements.size() > 0 &&
+ penultimate_case_statement_body_statements
+ [penultimate_case_statement_body_statements.size() - 1]
+ ->Is<ast::FallthroughStatement>()) {
+ // The penultimate case statement falls through to the final case statement, thus
+ // the final case statement cannot be removed.
+ return false;
+ }
+ }
+ }
+
+ auto* parent_sem = program.Sem().Get(&statement_node)->Parent();
+ if (parent_sem == nullptr) {
+ // Semantic information for the parent node is required.
+ return false;
+ }
+
+ auto* parent_stmt = parent_sem->Declaration();
+
+ // It does not make sense to delete the entire body of a loop or if statement.
+ if (auto* for_loop = parent_stmt->As<ast::ForLoopStatement>()) {
+ if (for_loop->body == &statement_node) {
+ return false;
+ }
+ }
+ if (auto* loop = parent_stmt->As<ast::LoopStatement>()) {
+ if (loop->body == &statement_node) {
+ return false;
+ }
+ }
+ if (auto* while_loop = parent_stmt->As<ast::WhileStatement>()) {
+ if (while_loop->body == &statement_node) {
+ return false;
+ }
+ }
+ if (auto* if_statement = parent_stmt->As<ast::IfStatement>()) {
+ if (if_statement->body == &statement_node) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+} // namespace tint::fuzzers::ast_fuzzer
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.h b/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.h
new file mode 100644
index 0000000..c7c0192
--- /dev/null
+++ b/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.h
@@ -0,0 +1,75 @@
+// 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 SRC_TINT_FUZZERS_TINT_AST_FUZZER_MUTATIONS_DELETE_STATEMENT_H_
+#define SRC_TINT_FUZZERS_TINT_AST_FUZZER_MUTATIONS_DELETE_STATEMENT_H_
+
+#include "src/tint/ast/statement.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/jump_tracker.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/mutation.h"
+
+namespace tint::fuzzers::ast_fuzzer {
+
+/// @see MutationDeleteStatement::Apply
+class MutationDeleteStatement : public Mutation {
+ public:
+ /// @brief Constructs an instance of this mutation from a protobuf message.
+ /// @param message - protobuf message
+ explicit MutationDeleteStatement(protobufs::MutationDeleteStatement message);
+
+ /// @brief Constructor.
+ /// @param statement_id - the id of the statement to delete.
+ explicit MutationDeleteStatement(uint32_t statement_id);
+
+ /// @copybrief Mutation::IsApplicable
+ ///
+ /// The mutation is applicable iff:
+ /// - `statement_id` corresponds to a statement in the AST.
+ /// - `statement_id` does not refer to a variable declaration, since the declared variables will
+ /// be inaccessible if the statement is deleted.
+ /// - `statement_id` is not a return statement, since removing return statements arbitrarily can
+ /// make the program invalid.
+ /// - `statement_id` is not a break statement, since removing break statements can lead to
+ /// syntactically infinite loops.
+ ///
+ /// @copydetails Mutation::IsApplicable
+ bool IsApplicable(const tint::Program& program, const NodeIdMap& node_id_map) const override;
+
+ /// @copybrief Mutation::Apply
+ ///
+ /// Delete the statement referenced by `statement_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;
+
+ /// Return whether the given statement is suitable for deletion.
+ /// @param statement_node - the statement to be considered for deletion.
+ /// @param program - the program containing the statement.
+ /// @param jump_tracker - information about jump statements for the program.
+ /// @return true if and only if it is OK to delete the statement.
+ static bool CanBeDeleted(const ast::Statement& statement_node,
+ const Program& program,
+ const JumpTracker& jump_tracker);
+
+ private:
+ protobufs::MutationDeleteStatement message_;
+};
+
+} // namespace tint::fuzzers::ast_fuzzer
+
+#endif // SRC_TINT_FUZZERS_TINT_AST_FUZZER_MUTATIONS_DELETE_STATEMENT_H_
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement_test.cc b/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement_test.cc
new file mode 100644
index 0000000..925ee80
--- /dev/null
+++ b/src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement_test.cc
@@ -0,0 +1,750 @@
+// 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 "src/tint/fuzzers/tint_ast_fuzzer/mutations/delete_statement.h"
+
+#include <functional>
+#include <string>
+
+#include "gtest/gtest.h"
+
+#include "src/tint/ast/assignment_statement.h"
+#include "src/tint/ast/block_statement.h"
+#include "src/tint/ast/case_statement.h"
+#include "src/tint/ast/fallthrough_statement.h"
+#include "src/tint/ast/for_loop_statement.h"
+#include "src/tint/ast/if_statement.h"
+#include "src/tint/ast/switch_statement.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/mutator.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/node_id_map.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/probability_context.h"
+#include "src/tint/program_builder.h"
+#include "src/tint/reader/wgsl/parser.h"
+#include "src/tint/writer/wgsl/generator.h"
+
+namespace tint::fuzzers::ast_fuzzer {
+namespace {
+
+void CheckStatementDeletionWorks(
+ const std::string& original,
+ const std::string& expected,
+ const std::function<const ast::Statement*(const Program&)>& statement_finder) {
+ Source::File original_file("original.wgsl", original);
+ auto program = reader::wgsl::Parse(&original_file);
+
+ Source::File expected_file("expected.wgsl", expected);
+ auto expected_program = reader::wgsl::Parse(&expected_file);
+
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+ ASSERT_TRUE(expected_program.IsValid()) << expected_program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+ const auto* statement = statement_finder(program);
+ ASSERT_NE(statement, nullptr);
+ auto statement_id = node_id_map.GetId(statement);
+ ASSERT_NE(statement_id, 0);
+ ASSERT_TRUE(MaybeApplyMutation(program, MutationDeleteStatement(statement_id), node_id_map,
+ &program, &node_id_map, nullptr));
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+ writer::wgsl::Options options;
+ auto transformed_result = writer::wgsl::Generate(&program, options);
+ auto expected_result = writer::wgsl::Generate(&expected_program, options);
+ ASSERT_TRUE(transformed_result.success) << transformed_result.error;
+ ASSERT_TRUE(expected_result.success) << expected_result.error;
+ ASSERT_EQ(expected_result.wgsl, transformed_result.wgsl);
+}
+
+void CheckStatementDeletionNotAllowed(
+ const std::string& original,
+ const std::function<const ast::Statement*(const Program&)>& statement_finder) {
+ Source::File original_file("original.wgsl", original);
+ auto program = reader::wgsl::Parse(&original_file);
+
+ ASSERT_TRUE(program.IsValid()) << program.Diagnostics().str();
+
+ NodeIdMap node_id_map(program);
+ const auto* statement = statement_finder(program);
+ ASSERT_NE(statement, nullptr);
+ auto statement_id = node_id_map.GetId(statement);
+ ASSERT_NE(statement_id, 0);
+ ASSERT_FALSE(MaybeApplyMutation(program, MutationDeleteStatement(statement_id), node_id_map,
+ &program, &node_id_map, nullptr));
+}
+
+TEST(DeleteStatementTest, DeleteAssignStatement) {
+ auto original = R"(
+ fn main() {
+ {
+ var a : i32 = 5;
+ a = 6;
+ }
+ })";
+ auto expected = R"(fn main() {
+ {
+ var a : i32 = 5;
+ }
+}
+)";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::BlockStatement>()
+ ->statements[1]
+ ->As<ast::AssignmentStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteForStatement) {
+ auto original =
+ R"(
+ fn main() {
+ for (var i : i32 = 0; i < 10; i++) {
+ }
+ }
+ )";
+ auto expected = "fn main() { }";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::ForLoopStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteIfStatement) {
+ auto original =
+ R"(
+ fn main() {
+ if (true) { } else { }
+ }
+ )";
+ auto expected = "fn main() { }";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::IfStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteBlockStatement) {
+ auto original = "fn main() { { } }";
+ auto expected = "fn main() { }";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::BlockStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteSwitchStatement) {
+ auto original = R"(
+fn main() {
+ switch(1) {
+ case 0, 1: {
+ }
+ default: {
+ fallthrough;
+ }
+ case 2: {
+ }
+ }
+})";
+ auto expected = R"(fn main() { })";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::SwitchStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteCaseStatement) {
+ auto original = R"(
+fn main() {
+ switch(1) {
+ case 0, 1: {
+ }
+ default: {
+ fallthrough;
+ }
+ case 2: {
+ }
+ }
+})";
+ auto expected = R"(
+fn main() {
+ switch(1) {
+ default: {
+ fallthrough;
+ }
+ case 2: {
+ }
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::SwitchStatement>()
+ ->body[0]
+ ->As<ast::CaseStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteFallthroughStatement) {
+ auto original = R"(
+fn main() {
+ switch(1) {
+ case 0, 1: {
+ }
+ default: {
+ fallthrough;
+ }
+ case 2: {
+ }
+ }
+})";
+ auto expected = R"(
+fn main() {
+ switch(1) {
+ case 0, 1: {
+ }
+ default: {
+ }
+ case 2: {
+ }
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::SwitchStatement>()
+ ->body[1]
+ ->As<ast::CaseStatement>()
+ ->body->statements[0]
+ ->As<ast::FallthroughStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteElse) {
+ auto original = R"(
+fn main() {
+ if (true) {
+ } else {
+ }
+})";
+ auto expected = R"(
+fn main() {
+ if (true) {
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::IfStatement>()
+ ->else_statement;
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteCall) {
+ auto original = R"(
+fn main() {
+ sin(1.0);
+})";
+ auto expected = R"(
+fn main() {
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::CallStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteCompoundAssign) {
+ auto original = R"(
+fn main() {
+ var x : i32 = 0;
+ x += 2;;
+})";
+ auto expected = R"(
+fn main() {
+ var x : i32 = 0;
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[1]
+ ->As<ast::CompoundAssignmentStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteLoop) {
+ auto original = R"(
+fn main() {
+ var x : i32 = 0;
+ loop {
+ if (x > 100) {
+ break;
+ }
+ continuing {
+ x++;
+ }
+ }
+})";
+ auto expected = R"(
+fn main() {
+ var x : i32 = 0;
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[1]->As<ast::LoopStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteContinuingBlock) {
+ auto original = R"(
+fn main() {
+ var x : i32 = 0;
+ loop {
+ if (x > 100) {
+ break;
+ }
+ continuing {
+ x++;
+ }
+ }
+})";
+ auto expected = R"(
+fn main() {
+ var x : i32 = 0;
+ loop {
+ if (x > 100) {
+ break;
+ }
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[1]
+ ->As<ast::LoopStatement>()
+ ->continuing;
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteContinue) {
+ auto original = R"(
+fn main() {
+ var x : i32 = 0;
+ loop {
+ if (x > 100) {
+ break;
+ }
+ continue;
+ continuing {
+ x++;
+ }
+ }
+})";
+ auto expected = R"(
+fn main() {
+ var x : i32 = 0;
+ loop {
+ if (x > 100) {
+ break;
+ }
+ continuing {
+ x++;
+ }
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[1]
+ ->As<ast::LoopStatement>()
+ ->body->statements[1]
+ ->As<ast::ContinueStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteIncrement) {
+ auto original = R"(
+fn main() {
+ var x : i32 = 0;
+ loop {
+ if (x > 100) {
+ break;
+ }
+ continuing {
+ x++;
+ }
+ }
+})";
+ auto expected = R"(
+fn main() {
+ var x : i32 = 0;
+ loop {
+ if (x > 100) {
+ break;
+ }
+ continuing {
+ }
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[1]
+ ->As<ast::LoopStatement>()
+ ->continuing->statements[0]
+ ->As<ast::IncrementDecrementStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteForLoopInitializer) {
+ auto original = R"(
+fn main() {
+ var x : i32;
+ for (x = 0; x < 100; x++) {
+ }
+})";
+ auto expected = R"(
+fn main() {
+ var x : i32;
+ for (; x < 100; x++) {
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[1]
+ ->As<ast::ForLoopStatement>()
+ ->initializer->As<ast::AssignmentStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DeleteForLoopContinuing) {
+ auto original = R"(
+fn main() {
+ var x : i32;
+ for (x = 0; x < 100; x++) {
+ }
+})";
+ auto expected = R"(
+fn main() {
+ var x : i32;
+ for (x = 0; x < 100;) {
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[1]
+ ->As<ast::ForLoopStatement>()
+ ->continuing->As<ast::IncrementDecrementStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, AllowDeletionOfInnerLoopWithBreak) {
+ auto original = R"(
+fn main() {
+ loop {
+ loop {
+ break;
+ }
+ break;
+ }
+})";
+ auto expected = R"(
+fn main() {
+ loop {
+ break;
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::LoopStatement>()
+ ->body->statements[0]
+ ->As<ast::LoopStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, AllowDeletionOfInnerCaseWithBreak) {
+ auto original = R"(
+fn main() {
+ loop {
+ switch(0) {
+ case 1: {
+ break;
+ }
+ default: {
+ }
+ }
+ break;
+ }
+})";
+ auto expected = R"(
+fn main() {
+ loop {
+ switch(0) {
+ default: {
+ }
+ }
+ break;
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::LoopStatement>()
+ ->body->statements[0]
+ ->As<ast::SwitchStatement>()
+ ->body[0];
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, AllowDeletionOfBreakFromSwitch) {
+ auto original = R"(
+fn main() {
+ switch(0) {
+ case 1: {
+ break;
+ }
+ default: {
+ }
+ }
+})";
+ auto expected = R"(
+fn main() {
+ switch(0) {
+ case 1: {
+ }
+ default: {
+ }
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::SwitchStatement>()
+ ->body[0]
+ ->body->statements[0]
+ ->As<ast::BreakStatement>();
+ };
+ CheckStatementDeletionWorks(original, expected, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotDeleteVariableDeclaration) {
+ auto original = R"(
+fn main() {
+ var x : i32;
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::VariableDeclStatement>();
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotDeleteCaseDueToFallthrough) {
+ auto original = R"(
+fn main() {
+ switch(1) {
+ default: {
+ fallthrough;
+ }
+ case 2: {
+ }
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::SwitchStatement>()
+ ->body[1]
+ ->As<ast::CaseStatement>();
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotMakeLoopInfinite1) {
+ auto original = R"(
+fn main() {
+ loop {
+ break;
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::LoopStatement>()
+ ->body->statements[0]
+ ->As<ast::BreakStatement>();
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotMakeLoopInfinite2) {
+ auto original = R"(
+fn main() {
+ loop {
+ if (true) {
+ break;
+ }
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST()
+ .Functions()[0]
+ ->body->statements[0]
+ ->As<ast::LoopStatement>()
+ ->body->statements[0]
+ ->As<ast::IfStatement>();
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveReturn) {
+ auto original = R"(
+fn main() {
+ return;
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::ReturnStatement>();
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveStatementContainingReturn) {
+ auto original = R"(
+fn foo() -> i32 {
+ if (true) {
+ return 1;
+ } else {
+ return 2;
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::IfStatement>();
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveDiscard) {
+ auto original = R"(
+fn main() {
+ discard;
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::DiscardStatement>();
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveStatementContainingDiscard) {
+ auto original = R"(
+fn foo() -> i32 {
+ if (true) {
+ discard;
+ } else {
+ discard;
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::IfStatement>();
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveLoopBody) {
+ auto original = R"(
+fn foo() {
+ discard;
+}
+fn main() {
+ loop {
+ foo();
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[1]->body->statements[0]->As<ast::LoopStatement>()->body;
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveForLoopBody) {
+ auto original = R"(
+fn main() {
+ for(var i : i32 = 0; i < 10; i++) {
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::ForLoopStatement>()->body;
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveWhileBody) {
+ auto original = R"(
+fn main() {
+ var i : i32 = 0;
+ while(i < 10) {
+ i++;
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[1]->As<ast::WhileStatement>()->body;
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveIfBody) {
+ auto original = R"(
+fn main() {
+ if(true) {
+ }
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body->statements[0]->As<ast::IfStatement>()->body;
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+TEST(DeleteStatementTest, DoNotRemoveFunctionBody) {
+ auto original = R"(
+fn main() {
+})";
+ auto statement_finder = [](const Program& program) -> const ast::Statement* {
+ return program.AST().Functions()[0]->body;
+ };
+ CheckStatementDeletionNotAllowed(original, statement_finder);
+}
+
+} // namespace
+} // namespace tint::fuzzers::ast_fuzzer
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/mutator.cc b/src/tint/fuzzers/tint_ast_fuzzer/mutator.cc
index f70a947..7153f0c 100644
--- a/src/tint/fuzzers/tint_ast_fuzzer/mutator.cc
+++ b/src/tint/fuzzers/tint_ast_fuzzer/mutator.cc
@@ -22,6 +22,7 @@
#include "src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/change_binary_operators.h"
#include "src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/change_unary_operators.h"
+#include "src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/delete_statements.h"
#include "src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/replace_identifiers.h"
#include "src/tint/fuzzers/tint_ast_fuzzer/mutation_finders/wrap_unary_operators.h"
#include "src/tint/fuzzers/tint_ast_fuzzer/node_id_map.h"
@@ -48,6 +49,8 @@
probability_context, &result);
MaybeAddFinder<MutationFinderChangeUnaryOperators>(enable_all_mutations,
probability_context, &result);
+ MaybeAddFinder<MutationFinderDeleteStatements>(enable_all_mutations, probability_context,
+ &result);
MaybeAddFinder<MutationFinderReplaceIdentifiers>(enable_all_mutations, probability_context,
&result);
MaybeAddFinder<MutationFinderWrapUnaryOperators>(enable_all_mutations, probability_context,
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/probability_context.cc b/src/tint/fuzzers/tint_ast_fuzzer/probability_context.cc
index 639bd60..f2cb159 100644
--- a/src/tint/fuzzers/tint_ast_fuzzer/probability_context.cc
+++ b/src/tint/fuzzers/tint_ast_fuzzer/probability_context.cc
@@ -21,6 +21,7 @@
const std::pair<uint32_t, uint32_t> kChanceOfChangingBinaryOperators = {30, 90};
const std::pair<uint32_t, uint32_t> kChanceOfChangingUnaryOperators = {30, 70};
+const std::pair<uint32_t, uint32_t> kChanceOfDeletingStatements = {30, 70};
const std::pair<uint32_t, uint32_t> kChanceOfReplacingIdentifiers = {30, 70};
const std::pair<uint32_t, uint32_t> kChanceOfWrappingUnaryOperators = {30, 70};
@@ -30,6 +31,7 @@
: generator_(generator),
chance_of_changing_binary_operators_(RandomFromRange(kChanceOfChangingBinaryOperators)),
chance_of_changing_unary_operators_(RandomFromRange(kChanceOfChangingUnaryOperators)),
+ chance_of_deleting_statements_(RandomFromRange(kChanceOfDeletingStatements)),
chance_of_replacing_identifiers_(RandomFromRange(kChanceOfReplacingIdentifiers)),
chance_of_wrapping_unary_operators_(RandomFromRange(kChanceOfWrappingUnaryOperators)) {
assert(generator != nullptr && "generator must not be nullptr");
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/probability_context.h b/src/tint/fuzzers/tint_ast_fuzzer/probability_context.h
index ce46738..410d7cf 100644
--- a/src/tint/fuzzers/tint_ast_fuzzer/probability_context.h
+++ b/src/tint/fuzzers/tint_ast_fuzzer/probability_context.h
@@ -61,6 +61,9 @@
return chance_of_changing_unary_operators_;
}
+ /// @return the probability of changing operator for a binary expression.
+ uint32_t GetChanceOfDeletingStatements() const { return chance_of_deleting_statements_; }
+
/// @return the probability of replacing some identifier with some other one.
uint32_t GetChanceOfReplacingIdentifiers() const { return chance_of_replacing_identifiers_; }
@@ -78,6 +81,7 @@
uint32_t chance_of_changing_binary_operators_;
uint32_t chance_of_changing_unary_operators_;
+ uint32_t chance_of_deleting_statements_;
uint32_t chance_of_replacing_identifiers_;
uint32_t chance_of_wrapping_unary_operators_;
};
diff --git a/src/tint/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.proto b/src/tint/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.proto
index fd3cd81..b1fa5e3 100644
--- a/src/tint/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.proto
+++ b/src/tint/fuzzers/tint_ast_fuzzer/protobufs/tint_ast_fuzzer.proto
@@ -22,6 +22,7 @@
MutationChangeBinaryOperator change_binary_operator = 2;
MutationWrapUnaryOperator wrap_unary_operator = 3;
MutationChangeUnaryOperator change_unary_operator = 4;
+ MutationDeleteStatement delete_statement = 5;
};
}
@@ -64,6 +65,14 @@
uint32 new_operator = 2;
}
+message MutationDeleteStatement {
+ // This transformation deletes a statement, as long as doing so does not
+ // invalidate the program.
+
+ // The id of a statement to be deleted.
+ uint32 statement_id = 1;
+}
+
message MutationReplaceIdentifier {
// This transformation replaces a use of one variable with another.
