Move the `InRegexp` implementation code from the header file to the source file. #cleanup PiperOrigin-RevId: 756360272
diff --git a/fuzztest/BUILD b/fuzztest/BUILD index 86a458e..6a7f414 100644 --- a/fuzztest/BUILD +++ b/fuzztest/BUILD
@@ -327,7 +327,10 @@ cc_library( name = "domain", - srcs = ["internal/domains/in_grammar_impl.cc"], + srcs = [ + "internal/domains/in_grammar_impl.cc", + "internal/domains/in_regexp_impl.cc", + ], hdrs = [ "domain.h", "internal/domains/in_grammar_impl.h",
diff --git a/fuzztest/CMakeLists.txt b/fuzztest/CMakeLists.txt index d6f6975..8288b31 100644 --- a/fuzztest/CMakeLists.txt +++ b/fuzztest/CMakeLists.txt
@@ -288,6 +288,7 @@ "internal/domains/protobuf_domain_impl.h" SRCS "internal/domains/in_grammar_impl.cc" + "internal/domains/in_regexp_impl.cc" DEPS fuzztest::any fuzztest::domain_core
diff --git a/fuzztest/internal/domains/in_regexp_impl.cc b/fuzztest/internal/domains/in_regexp_impl.cc new file mode 100644 index 0000000..03210ce --- /dev/null +++ b/fuzztest/internal/domains/in_regexp_impl.cc
@@ -0,0 +1,234 @@ +// Copyright 2022 Google LLC +// +// 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 "./fuzztest/internal/domains/in_regexp_impl.h" + +#include <algorithm> +#include <cstddef> +#include <optional> +#include <string> +#include <string_view> +#include <utility> +#include <vector> + +#include "absl/random/bit_gen_ref.h" +#include "absl/random/distributions.h" +#include "absl/status/status.h" +#include "absl/status/statusor.h" +#include "absl/strings/str_cat.h" +#include "absl/types/span.h" +#include "./fuzztest/internal/domains/domain_base.h" +#include "./fuzztest/internal/domains/regexp_dfa.h" +#include "./fuzztest/internal/logging.h" +#include "./fuzztest/internal/serialization.h" +#include "./fuzztest/internal/status.h" +#include "./fuzztest/internal/type_support.h" + +namespace fuzztest::internal { + +InRegexpImpl::InRegexpImpl(std::string_view regex_str) + : regex_str_(regex_str), dfa_(RegexpDFA::Create(regex_str_)) {} + +DFAPath InRegexpImpl::Init(absl::BitGenRef prng) { + if (auto seed = MaybeGetRandomSeed(prng)) return *seed; + absl::StatusOr<DFAPath> path = + dfa_.StringToDFAPath(dfa_.GenerateString(prng)); + FUZZTEST_INTERNAL_CHECK_PRECONDITION(path.ok(), + "Init should generate valid paths"); + return *path; +} + +void InRegexpImpl::Mutate(DFAPath& path, absl::BitGenRef prng, + const domain_implementor::MutationMetadata&, + bool only_shrink) { + if (only_shrink) { + // Fast path to remove loop. + if (absl::Bernoulli(prng, 0.5)) { + if (ShrinkByRemoveLoop(prng, path)) return; + } + + if (ShrinkByFindShorterSubPath(prng, path)) return; + return; + } + + size_t rand_offset = absl::Uniform(prng, 0u, path.size()); + // Maps states to the path index of their first appearance. We want the + // mutation to be minimal, so if a state appears multiple times in the path, + // we only keep the index of its first appearance. + std::vector<std::optional<int>> sink_states_first_appearance( + dfa_.state_count()); + for (size_t i = rand_offset; i < path.size(); ++i) { + int state_id = path[i].from_state_id; + if (sink_states_first_appearance[state_id].has_value()) continue; + sink_states_first_appearance[state_id] = i; + } + std::vector<RegexpDFA::Edge> new_subpath = dfa_.FindPath( + prng, path[rand_offset].from_state_id, sink_states_first_appearance); + int to_state_id = new_subpath.back().from_state_id; + new_subpath.pop_back(); + + DFAPath new_path; + for (size_t i = 0; i < rand_offset; ++i) { + new_path.push_back(path[i]); + } + for (size_t i = 0; i < new_subpath.size(); ++i) { + new_path.push_back(new_subpath[i]); + } + + // Found a node in the original path, so we append the remaining substring + // of the original path. + if (sink_states_first_appearance[to_state_id].has_value()) { + for (size_t i = *sink_states_first_appearance[to_state_id]; i < path.size(); + ++i) { + new_path.push_back(path[i]); + } + } + ValidatePathRoundtrip(new_path); + path = std::move(new_path); +} + +StringPrinter InRegexpImpl::GetPrinter() const { return StringPrinter{}; } + +InRegexpImpl::value_type InRegexpImpl::GetValue(const corpus_type& v) const { + absl::StatusOr<std::string> val = dfa_.DFAPathToString(v); + FUZZTEST_INTERNAL_CHECK(val.ok(), "Corpus is invalid!"); + return *val; +} + +std::optional<InRegexpImpl::corpus_type> InRegexpImpl::FromValue( + const value_type& v) const { + absl::StatusOr<corpus_type> path = dfa_.StringToDFAPath(v); + if (!path.ok()) return std::nullopt; + return *path; +} + +std::optional<InRegexpImpl::corpus_type> InRegexpImpl::ParseCorpus( + const IRObject& obj) const { + auto subs = obj.Subs(); + if (!subs) return std::nullopt; + if (subs->size() % 2 != 0) return std::nullopt; + corpus_type corpus_value; + for (size_t i = 0; i < subs->size(); i += 2) { + auto from_state_id = (*subs)[i].ToCorpus<int>(); + auto edge_index = (*subs)[i + 1].ToCorpus<int>(); + if (!from_state_id.has_value() || !edge_index.has_value()) + return std::nullopt; + corpus_value.push_back(RegexpDFA::Edge{*from_state_id, *edge_index}); + } + return corpus_value; +} + +IRObject InRegexpImpl::SerializeCorpus(const corpus_type& path) const { + IRObject obj; + auto& subs = obj.MutableSubs(); + for (const auto& edge : path) { + subs.push_back(IRObject::FromCorpus(edge.from_state_id)); + subs.push_back(IRObject::FromCorpus(edge.edge_index)); + } + return obj; +} + +absl::Status InRegexpImpl::ValidateCorpusValue( + const corpus_type& corpus_value) const { + // Check whether this is a valid path in the DFA. + absl::StatusOr<std::string> str = dfa_.DFAPathToString(corpus_value); + if (str.ok()) return absl::OkStatus(); + return Prefix(str.status(), absl::StrCat("Invalid value for InRegexp(\"", + regex_str_, "\")")); +} + +void InRegexpImpl::ValidatePathRoundtrip(const DFAPath& path) const { + absl::StatusOr<std::string> str = dfa_.DFAPathToString(path); + FUZZTEST_INTERNAL_CHECK(str.ok(), "Invalid path in the DFA!"); + absl::StatusOr<DFAPath> new_path = dfa_.StringToDFAPath(*str); + FUZZTEST_INTERNAL_CHECK(new_path.ok(), "Invalid path in the DFA!"); +} + +bool InRegexpImpl::ShrinkByRemoveLoop(absl::BitGenRef prng, DFAPath& path) { + std::vector<std::vector<int>> state_appearances(dfa_.state_count()); + for (int i = 0; i < path.size(); ++i) { + state_appearances[path[i].from_state_id].push_back(i); + } + std::vector<int> states_with_loop; + for (int i = 0; i < dfa_.state_count(); ++i) { + if (state_appearances[i].size() > 1) states_with_loop.push_back(i); + } + if (!states_with_loop.empty()) { + size_t rand_state_id = + states_with_loop[absl::Uniform(prng, 0u, states_with_loop.size())]; + std::vector<int>& loop_indexes = state_appearances[rand_state_id]; + size_t loop_start = absl::Uniform(prng, 0u, loop_indexes.size() - 1); + size_t loop_end = absl::Uniform(prng, loop_start + 1, loop_indexes.size()); + // Delete the detected loop. + path.erase(path.begin() + loop_indexes[loop_start], + path.begin() + loop_indexes[loop_end]); + ValidatePathRoundtrip(path); + return true; + } + return false; +} + +bool InRegexpImpl::ShrinkByFindShorterSubPath(absl::BitGenRef prng, + DFAPath& path) { + if (path.size() <= 1) { + return false; + } + constexpr int n_trial = 40; + constexpr int max_exploration_length = 100; + for (int i = 0; i < n_trial; ++i) { + // Pick any state in `path` as the start of the subpath, *except* the one + // in the last element. + size_t from_index = absl::Uniform(prng, 0u, path.size() - 1); + int from_state_id = path[from_index].from_state_id; + + // Pick a state after the "from state" as the end of the subpath. + size_t to_index, length; + int to_state_id; + if (i <= n_trial / 2) { + // Pick any state in `path` after the "from state" as the end of the + // subpath; this excludes the "end state". + to_index = absl::Uniform( + prng, from_index + 1, + std::min(from_index + max_exploration_length, path.size())); + to_state_id = path[to_index].from_state_id; + length = to_index - from_index; + } else { + // If failing too many times, try to find a shorter path to the + // end_state as a fall back. In this case, to_index isn't the index of + // a valid element in `path`. + to_index = path.size(); + to_state_id = dfa_.end_state_id(); + length = to_index - from_index; + } + + if (length == 1) continue; + + std::vector<RegexpDFA::Edge> new_subpath = + dfa_.FindPathWithinLengthDFS(prng, from_state_id, to_state_id, length); + // If the size is unchanged, keep trying. + if (new_subpath.size() == length) continue; + + DFAPath new_path(path.begin(), path.begin() + from_index); + new_path.insert(new_path.end(), new_subpath.begin(), new_subpath.end()); + for (size_t idx = to_index; idx < path.size(); ++idx) { + new_path.push_back(path[idx]); + } + ValidatePathRoundtrip(new_path); + path = std::move(new_path); + return true; + } + return false; +} + +} // namespace fuzztest::internal
diff --git a/fuzztest/internal/domains/in_regexp_impl.h b/fuzztest/internal/domains/in_regexp_impl.h index 144779c..c607539 100644 --- a/fuzztest/internal/domains/in_regexp_impl.h +++ b/fuzztest/internal/domains/in_regexp_impl.h
@@ -15,25 +15,16 @@ #ifndef FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_IN_REGEXP_IMPL_H_ #define FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_IN_REGEXP_IMPL_H_ -#include <algorithm> -#include <cstddef> #include <optional> #include <string> #include <string_view> -#include <utility> #include <vector> #include "absl/random/bit_gen_ref.h" -#include "absl/random/distributions.h" #include "absl/status/status.h" -#include "absl/status/statusor.h" -#include "absl/strings/str_cat.h" -#include "absl/types/span.h" #include "./fuzztest/internal/domains/domain_base.h" #include "./fuzztest/internal/domains/regexp_dfa.h" -#include "./fuzztest/internal/logging.h" #include "./fuzztest/internal/serialization.h" -#include "./fuzztest/internal/status.h" #include "./fuzztest/internal/type_support.h" namespace fuzztest::internal { @@ -44,205 +35,41 @@ : public domain_implementor::DomainBase<InRegexpImpl, std::string, DFAPath> { public: - explicit InRegexpImpl(std::string_view regex_str) - : regex_str_(regex_str), dfa_(RegexpDFA::Create(regex_str_)) {} + explicit InRegexpImpl(std::string_view regex_str); - DFAPath Init(absl::BitGenRef prng) { - if (auto seed = MaybeGetRandomSeed(prng)) return *seed; - absl::StatusOr<DFAPath> path = - dfa_.StringToDFAPath(dfa_.GenerateString(prng)); - FUZZTEST_INTERNAL_CHECK_PRECONDITION(path.ok(), - "Init should generate valid paths"); - return *path; - } + DFAPath Init(absl::BitGenRef prng); // Strategy: Parse the input string into a path in the DFA. Pick a node in the // path and random walk from the node until we reach an end state or go back // to the original path. void Mutate(DFAPath& path, absl::BitGenRef prng, - const domain_implementor::MutationMetadata&, bool only_shrink) { - if (only_shrink) { - // Fast path to remove loop. - if (absl::Bernoulli(prng, 0.5)) { - if (ShrinkByRemoveLoop(prng, path)) return; - } + const domain_implementor::MutationMetadata&, bool only_shrink); - if (ShrinkByFindShorterSubPath(prng, path)) return; - return; - } + StringPrinter GetPrinter() const; - size_t rand_offset = absl::Uniform(prng, 0u, path.size()); - // Maps states to the path index of their first appearance. We want the - // mutation to be mininal, so if a state appears multiple times in the path, - // we only keep the index of its first appearance. - std::vector<std::optional<int>> sink_states_first_appearance( - dfa_.state_count()); - for (size_t i = rand_offset; i < path.size(); ++i) { - int state_id = path[i].from_state_id; - if (sink_states_first_appearance[state_id].has_value()) continue; - sink_states_first_appearance[state_id] = i; - } - std::vector<RegexpDFA::Edge> new_subpath = dfa_.FindPath( - prng, path[rand_offset].from_state_id, sink_states_first_appearance); - int to_state_id = new_subpath.back().from_state_id; - new_subpath.pop_back(); + value_type GetValue(const corpus_type& v) const; - DFAPath new_path; - for (size_t i = 0; i < rand_offset; ++i) { - new_path.push_back(path[i]); - } - for (size_t i = 0; i < new_subpath.size(); ++i) { - new_path.push_back(new_subpath[i]); - } + std::optional<corpus_type> FromValue(const value_type& v) const; - // Found a node in the original path, so we append the remaining substring - // of the original path. - if (sink_states_first_appearance[to_state_id].has_value()) { - for (size_t i = *sink_states_first_appearance[to_state_id]; - i < path.size(); ++i) { - new_path.push_back(path[i]); - } - } - ValidatePathRoundtrip(new_path); - path = std::move(new_path); - } + std::optional<corpus_type> ParseCorpus(const IRObject& obj) const; - auto GetPrinter() const { return StringPrinter{}; } + IRObject SerializeCorpus(const corpus_type& path) const; - value_type GetValue(const corpus_type& v) const { - absl::StatusOr<std::string> val = dfa_.DFAPathToString(v); - FUZZTEST_INTERNAL_CHECK(val.ok(), "Corpus is invalid!"); - return *val; - } - - std::optional<corpus_type> FromValue(const value_type& v) const { - absl::StatusOr<corpus_type> path = dfa_.StringToDFAPath(v); - if (!path.ok()) return std::nullopt; - return *path; - } - - std::optional<corpus_type> ParseCorpus(const IRObject& obj) const { - auto subs = obj.Subs(); - if (!subs) return std::nullopt; - if (subs->size() % 2 != 0) return std::nullopt; - corpus_type corpus_value; - for (size_t i = 0; i < subs->size(); i += 2) { - auto from_state_id = (*subs)[i].ToCorpus<int>(); - auto edge_index = (*subs)[i + 1].ToCorpus<int>(); - if (!from_state_id.has_value() || !edge_index.has_value()) - return std::nullopt; - corpus_value.push_back(RegexpDFA::Edge{*from_state_id, *edge_index}); - } - return corpus_value; - } - - IRObject SerializeCorpus(const corpus_type& path) const { - IRObject obj; - auto& subs = obj.MutableSubs(); - for (const auto& edge : path) { - subs.push_back(IRObject::FromCorpus(edge.from_state_id)); - subs.push_back(IRObject::FromCorpus(edge.edge_index)); - } - return obj; - } - - absl::Status ValidateCorpusValue(const corpus_type& corpus_value) const { - // Check whether this is a valid path in the DFA. - absl::StatusOr<std::string> str = dfa_.DFAPathToString(corpus_value); - if (str.ok()) return absl::OkStatus(); - return Prefix(str.status(), absl::StrCat("Invalid value for InRegexp(\"", - regex_str_, "\")")); - } + absl::Status ValidateCorpusValue(const corpus_type& corpus_value) const; private: - void ValidatePathRoundtrip(const DFAPath& path) const { - absl::StatusOr<std::string> str = dfa_.DFAPathToString(path); - FUZZTEST_INTERNAL_CHECK(str.ok(), "Invalid path in the DFA!"); - absl::StatusOr<DFAPath> new_path = dfa_.StringToDFAPath(*str); - FUZZTEST_INTERNAL_CHECK(new_path.ok(), "Invalid path in the DFA!"); - } + void ValidatePathRoundtrip(const DFAPath& path) const; // Remove a random loop in the DFA path and return the string from the // modified path. A loop is a subpath that starts and ends with the same // state. - bool ShrinkByRemoveLoop(absl::BitGenRef prng, DFAPath& path) { - std::vector<std::vector<int>> state_appearances(dfa_.state_count()); - for (int i = 0; i < path.size(); ++i) { - state_appearances[path[i].from_state_id].push_back(i); - } - std::vector<int> states_with_loop; - for (int i = 0; i < dfa_.state_count(); ++i) { - if (state_appearances[i].size() > 1) states_with_loop.push_back(i); - } - if (!states_with_loop.empty()) { - size_t rand_state_id = - states_with_loop[absl::Uniform(prng, 0u, states_with_loop.size())]; - std::vector<int>& loop_indexes = state_appearances[rand_state_id]; - size_t loop_start = absl::Uniform(prng, 0u, loop_indexes.size() - 1); - size_t loop_end = - absl::Uniform(prng, loop_start + 1, loop_indexes.size()); - // Delete the detected loop. - path.erase(path.begin() + loop_indexes[loop_start], - path.begin() + loop_indexes[loop_end]); - ValidatePathRoundtrip(path); - return true; - } - return false; - } + bool ShrinkByRemoveLoop(absl::BitGenRef prng, DFAPath& path); // Randomly pick a subpath and try to replace it with a shorter one. As this // might fail we keep trying until success or the maximum number of trials is // reached. - bool ShrinkByFindShorterSubPath(absl::BitGenRef prng, DFAPath& path) { - if (path.size() <= 1) { - return false; - } - constexpr int n_trial = 40; - constexpr int max_exploration_length = 100; - for (int i = 0; i < n_trial; ++i) { - // Pick any state in `path` as the start of the subpath, *except* the one - // in the last element. - size_t from_index = absl::Uniform(prng, 0u, path.size() - 1); - int from_state_id = path[from_index].from_state_id; + bool ShrinkByFindShorterSubPath(absl::BitGenRef prng, DFAPath& path); - // Pick a state after the "from state" as the end of the subpath. - size_t to_index, length; - int to_state_id; - if (i <= n_trial / 2) { - // Pick any state in `path` after the "from state" as the end of the - // subpath; this excludes the "end state". - to_index = absl::Uniform( - prng, from_index + 1, - std::min(from_index + max_exploration_length, path.size())); - to_state_id = path[to_index].from_state_id; - length = to_index - from_index; - } else { - // If failing too many times, try to find a shorter path to the - // end_state as a fall back. In this case, to_index isn't the index of - // a valid element in `path`. - to_index = path.size(); - to_state_id = dfa_.end_state_id(); - length = to_index - from_index; - } - - if (length == 1) continue; - - std::vector<RegexpDFA::Edge> new_subpath = dfa_.FindPathWithinLengthDFS( - prng, from_state_id, to_state_id, length); - // If the size is unchanged, keep trying. - if (new_subpath.size() == length) continue; - - DFAPath new_path(path.begin(), path.begin() + from_index); - new_path.insert(new_path.end(), new_subpath.begin(), new_subpath.end()); - for (size_t idx = to_index; idx < path.size(); ++idx) { - new_path.push_back(path[idx]); - } - ValidatePathRoundtrip(new_path); - path = std::move(new_path); - return true; - } - return false; - } std::string regex_str_; RegexpDFA dfa_; };
diff --git a/fuzztest/internal/domains/regexp_dfa.cc b/fuzztest/internal/domains/regexp_dfa.cc index 468c926..67d7e5b 100644 --- a/fuzztest/internal/domains/regexp_dfa.cc +++ b/fuzztest/internal/domains/regexp_dfa.cc
@@ -26,7 +26,9 @@ #include <vector> #include "absl/container/flat_hash_map.h" +#include "absl/random/bit_gen_ref.h" #include "absl/random/discrete_distribution.h" +#include "absl/random/distributions.h" #include "absl/status/status.h" #include "absl/status/statusor.h" #include "absl/strings/str_cat.h" @@ -45,6 +47,118 @@ return dfa; } +std::string RegexpDFA::GenerateString(absl::BitGenRef prng) { + std::string result; + State* state = &states_[0]; + while (true) { + FUZZTEST_INTERNAL_CHECK(!state->next.empty(), "Empty next state!"); + + // Pick a random next state by weight. + int rand_index = state->edge_weight_distribution(prng); + auto& [next_string, next_id] = state->next[rand_index]; + state = &states_[next_id]; + result.insert(result.end(), next_string.begin(), next_string.end()); + if (next_string.back() == kEndOfString) { + FUZZTEST_INTERNAL_CHECK(state->is_end_state(), + "EOS should lead to end state!"); + result.pop_back(); + break; + } + } + return result; +} + +std::vector<RegexpDFA::Edge> RegexpDFA::FindPath( + absl::BitGenRef prng, int from_state_id, + const std::vector<std::optional<int>>& to_state_ids) { + std::vector<Edge> path; + int cur_state_id = from_state_id; + State* cur_state = &states_[cur_state_id]; + while (true) { + FUZZTEST_INTERNAL_CHECK(!cur_state->next.empty(), "Empty next state!"); + + // Pick a random next state. + int offset = cur_state->edge_weight_distribution(prng); + auto& [next_char, next_state_id] = cur_state->next[offset]; + path.push_back({cur_state_id, offset}); + + cur_state_id = next_state_id; + cur_state = &states_[cur_state_id]; + // Reached an end state or found a state in the original path? + if (cur_state->is_end_state() || to_state_ids[next_state_id].has_value()) { + path.push_back({next_state_id, -1}); + break; + } + } + return path; +} + +std::vector<RegexpDFA::Edge> RegexpDFA::FindPathWithinLengthDFS( + absl::BitGenRef prng, int from_state_id, int to_state_id, int length) { + // Each state maintains an edge and a counter for each possible length. The + // edge is the last edge in the path from `from_state` to the state and can + // be used to reconstruct the path. And the counter is the number of paths + // to the state, which can be used for reservoir sampling. + struct LastEdgeAndCounter { + std::optional<Edge> edge; + int counter; + }; + std::vector<std::vector<LastEdgeAndCounter>> last_edges_and_counters( + states_.size(), std::vector<LastEdgeAndCounter>(length + 1)); + + // Randomness for DFS. Instead of always starting to explore from edge index + // 0, we start with a different random offset for each state. + std::vector<int> rand_edge_offsets(states_.size(), 0); + for (int& i : rand_edge_offsets) i = absl::Uniform<int>(prng, 0u, 256); + + std::vector<Edge> stack{Edge{from_state_id, 0}}; + do { + auto [current_state_id, edge_index] = stack.back(); + if (edge_index == states_[current_state_id].next.size()) { + stack.pop_back(); + continue; + } + ++stack.back().edge_index; + const int current_path_length = static_cast<int>(stack.size()); + const int real_edge_index = + (edge_index + rand_edge_offsets[current_state_id]) % + static_cast<int>(states_[current_state_id].next.size()); + const int next_state_id = + states_[current_state_id].next[real_edge_index].next_state_id; + const int n_path_of_current_length = + ++last_edges_and_counters[next_state_id][current_path_length].counter; + // Reservoir Sampling. + if (absl::Bernoulli(prng, 1.0 / n_path_of_current_length)) { + last_edges_and_counters[next_state_id][current_path_length].edge = + Edge{current_state_id, real_edge_index}; + } + if (n_path_of_current_length == 1 && current_path_length != length) { + stack.push_back(Edge{next_state_id, 0}); + } + } while (!stack.empty()); + + std::vector<int> candidate_lens; + for (int len = 1; len <= length; ++len) { + if (last_edges_and_counters[to_state_id][len].edge.has_value()) { + candidate_lens.push_back(len); + } + } + FUZZTEST_INTERNAL_CHECK(!candidate_lens.empty(), "Cannot find a path!"); + + int state_id = to_state_id; + std::vector<Edge> result; + for (int len = + candidate_lens[absl::Uniform<int>(prng, 0, candidate_lens.size())]; + len > 0; --len) { + result.push_back(*(last_edges_and_counters[state_id][len].edge)); + state_id = last_edges_and_counters[state_id][len].edge->from_state_id; + } + FUZZTEST_INTERNAL_CHECK(state_id == from_state_id, + "Cannot find a path from from_state"); + std::reverse(result.begin(), result.end()); + return result; +} + absl::StatusOr<std::vector<RegexpDFA::Edge>> RegexpDFA::StringToDFAPath( absl::string_view s) const { std::vector<RegexpDFA::Edge> path;
diff --git a/fuzztest/internal/domains/regexp_dfa.h b/fuzztest/internal/domains/regexp_dfa.h index 142659f..7a0c86a 100644 --- a/fuzztest/internal/domains/regexp_dfa.h +++ b/fuzztest/internal/domains/regexp_dfa.h
@@ -15,7 +15,6 @@ #ifndef FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_REGEXP_DFA_H_ #define FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_REGEXP_DFA_H_ -#include <algorithm> #include <cstddef> #include <cstdint> #include <memory> @@ -25,14 +24,12 @@ #include "absl/random/bit_gen_ref.h" #include "absl/random/discrete_distribution.h" -#include "absl/random/distributions.h" #include "absl/status/statusor.h" -#include "absl/strings/str_cat.h" #include "absl/strings/string_view.h" -#include "./fuzztest/internal/logging.h" #include "re2/re2.h" namespace fuzztest::internal { + // Represents the deterministic finite automaton (DFA) of a regular expression. class RegexpDFA { public: @@ -45,7 +42,7 @@ int next_state_id; }; std::vector<StateTransition> next; - // The weight reprensents the probablity of an edge being chosen during + // The weight represents the probability of an edge being chosen during // random walk. The larger the weight, the higher chance the edge gets // picked. An edge transitioning to a node that is more likely to reach the // end state has larger weight than that doesn't. @@ -60,126 +57,22 @@ static RegexpDFA Create(absl::string_view regexp); - std::string GenerateString(absl::BitGenRef prng) { - std::string result; - State* state = &states_[0]; - while (true) { - FUZZTEST_INTERNAL_CHECK(!state->next.empty(), "Empty next state!"); - - // Pick a random next state by weight. - int rand_index = state->edge_weight_distribution(prng); - auto& [next_string, next_id] = state->next[rand_index]; - state = &states_[next_id]; - result.insert(result.end(), next_string.begin(), next_string.end()); - if (next_string.back() == kEndOfString) { - FUZZTEST_INTERNAL_CHECK(state->is_end_state(), - "EOS should lead to end state!"); - result.pop_back(); - break; - } - } - return result; - } + std::string GenerateString(absl::BitGenRef prng); // Randomly walk from the state of `from_state_id` to any state of // `to_state_ids` or an end state. std::vector<Edge> FindPath( absl::BitGenRef prng, int from_state_id, - const std::vector<std::optional<int>>& to_state_ids) { - std::vector<Edge> path; - int cur_state_id = from_state_id; - State* cur_state = &states_[cur_state_id]; - while (true) { - FUZZTEST_INTERNAL_CHECK(!cur_state->next.empty(), "Empty next state!"); - - // Pick a random next state. - int offset = cur_state->edge_weight_distribution(prng); - auto& [next_char, next_state_id] = cur_state->next[offset]; - path.push_back({cur_state_id, offset}); - - cur_state_id = next_state_id; - cur_state = &states_[cur_state_id]; - // Reached an end state or found a state in the original path? - if (cur_state->is_end_state() || - to_state_ids[next_state_id].has_value()) { - path.push_back({next_state_id, -1}); - break; - } - } - return path; - } + const std::vector<std::optional<int>>& to_state_ids); // Randomly DFS from the state of `from_state_id` to the state of // `to_state_id`, trying to find a path of length less than, if no, equal to // `length`. If we have multiple such paths, randomly pick one of them. Since - // this (nearly) fully exlpores all the paths, there is no big difference in + // this (nearly) fully explores all the paths, there is no big difference in // the efficiency. And we prefer DFS to BFS for better readability. std::vector<Edge> FindPathWithinLengthDFS(absl::BitGenRef prng, int from_state_id, int to_state_id, - int length) { - // Each state maintains an edge and a counter for each possible length. The - // edge is the last edge in the path from `from_state` to the state and can - // be used to reconstruct the path. And the counter is the number of paths - // to the state, which can be used for reservoir sampling. - struct LastEdgeAndCounter { - std::optional<Edge> edge; - int counter; - }; - std::vector<std::vector<LastEdgeAndCounter>> last_edges_and_counters( - states_.size(), std::vector<LastEdgeAndCounter>(length + 1)); - - // Randomness for DFS. Instead of always starting to explore from edge index - // 0, we start with a different random offset for each state. - std::vector<int> rand_edge_offsets(states_.size(), 0); - for (int& i : rand_edge_offsets) i = absl::Uniform<int>(prng, 0u, 256); - - std::vector<Edge> stack{Edge{from_state_id, 0}}; - do { - auto [current_state_id, edge_index] = stack.back(); - if (edge_index == states_[current_state_id].next.size()) { - stack.pop_back(); - continue; - } - ++stack.back().edge_index; - const int current_path_length = static_cast<int>(stack.size()); - const int real_edge_index = - (edge_index + rand_edge_offsets[current_state_id]) % - static_cast<int>(states_[current_state_id].next.size()); - const int next_state_id = - states_[current_state_id].next[real_edge_index].next_state_id; - const int n_path_of_current_length = - ++last_edges_and_counters[next_state_id][current_path_length].counter; - // Reservoir Sampling. - if (absl::Bernoulli(prng, 1.0 / n_path_of_current_length)) { - last_edges_and_counters[next_state_id][current_path_length].edge = - Edge{current_state_id, real_edge_index}; - } - if (n_path_of_current_length == 1 && current_path_length != length) { - stack.push_back(Edge{next_state_id, 0}); - } - } while (!stack.empty()); - - std::vector<int> candidate_lens; - for (int len = 1; len <= length; ++len) { - if (last_edges_and_counters[to_state_id][len].edge.has_value()) { - candidate_lens.push_back(len); - } - } - FUZZTEST_INTERNAL_CHECK(!candidate_lens.empty(), "Cannot find a path!"); - - int state_id = to_state_id; - std::vector<Edge> result; - for (int len = - candidate_lens[absl::Uniform<int>(prng, 0, candidate_lens.size())]; - len > 0; --len) { - result.push_back(*(last_edges_and_counters[state_id][len].edge)); - state_id = last_edges_and_counters[state_id][len].edge->from_state_id; - } - FUZZTEST_INTERNAL_CHECK(state_id == from_state_id, - "Cannot find a path from from_state"); - std::reverse(result.begin(), result.end()); - return result; - } + int length); absl::StatusOr<std::vector<Edge>> StringToDFAPath(absl::string_view s) const; @@ -192,7 +85,7 @@ int end_state_id() const { return end_state_id_; } private: - RegexpDFA() {} + RegexpDFA() = default; // Given a state and the next input character, try to match the character and // return the index in State::next. Return `nullopt` if the matching fails.