regexp_dfa.cc | Explore in Territory

// 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/regexp_dfa.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <memory>
#include <optional>
#include <queue>
#include <string>
#include <utility>
#include <vector>

#include "absl/container/flat_hash_map.h"
#include "absl/random/discrete_distribution.h"
#include "absl/strings/string_view.h"
#include "./fuzztest/internal/logging.h"
#include "re2/prog.h"
#include "re2/regexp.h"

namespace fuzztest::internal {

RegexpDFA RegexpDFA::Create(absl::string_view regexp) { … }

std::optional<std::vector<RegexpDFA::Edge>> RegexpDFA::StringToDFAPath(
    absl::string_view s) const { … }

std::optional<std::string> RegexpDFA::DFAPathToString(
    const std::vector<RegexpDFA::Edge>& path, size_t start_offset,
    std::optional<size_t> end_offset) const { … }

std::optional<int> RegexpDFA::NextState(
    const State& cur_state, const std::vector<std::int16_t>& input_chars,
    size_t& cur_index) const { … }

std::unique_ptr<re2::Prog> RegexpDFA::CompileRegexp(absl::string_view regexp) { … }

void RegexpDFA::BuildEntireDFA(std::unique_ptr<re2::Prog> compiled_regexp) { … }

void RegexpDFA::ComputeEdgeWeights() { … }

// Compress a state if the state has only one outgoing state. For example, if we
// have S0-(a)->S1-(b)->S2, then we can compress S1 to S0 and get S0-(ab)->S2.
// We do so by setting S0's outgoing edge to S2 and append S1's matching
// characters to S0's edge.
void RegexpDFA::CompressStates() { … }

}  // namespace fuzztest::internal
chromium/third_party/fuzztest/src/fuzztest/internal/domains/regexp_dfa.cc
