Support UTF8 strings. PiperOrigin-RevId: 761213017
diff --git a/LICENSE b/LICENSE index 1979ef9..227b21f 100644 --- a/LICENSE +++ b/LICENSE
@@ -1,3 +1,20 @@ +Files: fuzztest/internal/domains/rune.* +The authors of this software are Rob Pike and Ken Thompson. + Copyright (c) 2002 by Lucent Technologies. +Permission to use, copy, modify, and distribute this software for any +purpose without fee is hereby granted, provided that this entire notice +is included in all copies of any software which is or includes a copy +or modification of this software and in all copies of the supporting +documentation for such software. +THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED +WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE +ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF +THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. + +rune.* have been converted to compile as C++ code in fuzztest::internal +namespace. + +--- Files: grammar_codegen/generated_antlr_parser/* [The "BSD 3-clause license"]
diff --git a/doc/domains-reference.md b/doc/domains-reference.md index 03e2bce..481323a 100644 --- a/doc/domains-reference.md +++ b/doc/domains-reference.md
@@ -126,6 +126,7 @@ - `String()` is an alias for `Arbitrary<std::string>()`. - `AsciiString()` represents strings of ASCII characters. - `PrintableAsciiString()` represents printable strings. +- `Utf8String()` represents valid UTF-8 strings. You also define your string domains with custom character domains using the [StringOf()](#string-combinator) domain combinator.
diff --git a/domain_tests/string_domains_test.cc b/domain_tests/string_domains_test.cc index ffd375c..0ad0906 100644 --- a/domain_tests/string_domains_test.cc +++ b/domain_tests/string_domains_test.cc
@@ -160,5 +160,70 @@ } } } + +TEST(Domain, Utf8StringWorksWithSeeds) { + auto domain = Utf8String().WithSeeds({"\u0414\u0430!\n"}); + EXPECT_THAT(GenerateValues(domain), + Contains(Value(domain, "\u0414\u0430!\n"))); +} + +TEST(Domain, Utf8StringIgnoresInvalideSeeds) { + const std::string invalid_utf8 = "abc\x80"; + EXPECT_THAT(Utf8String().FromValue(invalid_utf8), Eq(std::nullopt)); +} + +TEST(Domain, Utf8StringUsesDictionary) { + auto domain = Utf8String(); + internal::TablesOfRecentCompares cmp_tables; + // Fill the table with the same entry. + for (int i = 0; i < cmp_tables.GetMutable<0>().kTableSize; ++i) { + cmp_tables.GetMutable<0>().Insert(reinterpret_cast<const uint8_t*>("abcd"), + reinterpret_cast<const uint8_t*>("1234"), + 4); + } + + absl::BitGen bitgen; + std::vector<std::string> mutants; + const double hit_probability = // + 1.0 / 2 // to pick String() within OverlapOf(...) + * 1.0 / 4 // to use dictionaries + * 1.0 / 4 // to use cmp tables + * 1.0 / 2; // to pick the memcmp table + for (int i = 0; i < IterationsToHitAll(/*num_cases=*/1, hit_probability); + ++i) { + auto mutant = domain.FromValue("abcd"); + ASSERT_TRUE(mutant.has_value()); + domain.Mutate(*mutant, bitgen, {/*cmp_tables=*/&cmp_tables}, false); + mutants.push_back(domain.GetValue(*mutant)); + } + EXPECT_THAT(mutants, Contains(HasSubstr("1234"))); +} + +TEST(Domain, AsciiStringUsesDictionary) { + auto domain = AsciiString(); + internal::TablesOfRecentCompares cmp_tables; + // Fill the table with the same entry. + for (int i = 0; i < cmp_tables.GetMutable<0>().kTableSize; ++i) { + cmp_tables.GetMutable<0>().Insert(reinterpret_cast<const uint8_t*>("abcd"), + reinterpret_cast<const uint8_t*>("1234"), + 4); + } + + absl::BitGen bitgen; + std::vector<std::string> mutants; + const double hit_probability = // + 1.0 / 4 // to use dictionaries + * 1.0 / 4 // to use cmp tables + * 1.0 / 2; // to pick the memcmp table + for (int i = 0; i < IterationsToHitAll(/*num_cases=*/1, hit_probability); + ++i) { + auto mutant = domain.FromValue("abcd"); + ASSERT_TRUE(mutant.has_value()); + domain.Mutate(*mutant, bitgen, {/*cmp_tables=*/&cmp_tables}, false); + mutants.push_back(domain.GetValue(*mutant)); + } + EXPECT_THAT(mutants, Contains(HasSubstr("1234"))); +} + } // namespace } // namespace fuzztest
diff --git a/fuzztest/BUILD b/fuzztest/BUILD index 66bc60c..29c9bc4 100644 --- a/fuzztest/BUILD +++ b/fuzztest/BUILD
@@ -365,6 +365,22 @@ ], ) +cc_library( + name = "utf", + srcs = [ + "internal/domains/rune.cc", + "internal/domains/rune.h", + "internal/domains/utf.cc", + ], + hdrs = [ + "internal/domains/utf.h", + ], + visibility = ["//visibility:private"], + deps = [ + "@abseil-cpp//absl/strings:string_view", + ], +) + # The core domain library without external dependencies e.g. re2. Mainly used # by the default Centipede mutation. cc_library( @@ -408,6 +424,7 @@ ":status", ":table_of_recent_compares", ":type_support", + ":utf", "@abseil-cpp//absl/container:flat_hash_map", "@abseil-cpp//absl/container:flat_hash_set", "@abseil-cpp//absl/functional:function_ref",
diff --git a/fuzztest/CMakeLists.txt b/fuzztest/CMakeLists.txt index 08a494e..4f40b53 100644 --- a/fuzztest/CMakeLists.txt +++ b/fuzztest/CMakeLists.txt
@@ -315,6 +315,19 @@ fuzztest_cc_library( NAME + utf + HDRS + "internal/domains/utf.h" + SRCS + "internal/domains/rune.cc" + "internal/domains/rune.h" + "internal/domains/utf.cc" + DEPS + absl::string_view +) + +fuzztest_cc_library( + NAME domain_core HDRS "domain_core.h" @@ -353,6 +366,7 @@ fuzztest::status fuzztest::table_of_recent_compares fuzztest::type_support + fuzztest::utf absl::flat_hash_map absl::flat_hash_set absl::function_ref
diff --git a/fuzztest/domain_core.h b/fuzztest/domain_core.h index d95dbc1..926aba4 100644 --- a/fuzztest/domain_core.h +++ b/fuzztest/domain_core.h
@@ -61,6 +61,7 @@ #include "./fuzztest/internal/domains/overlap_of_impl.h" #include "./fuzztest/internal/domains/smart_pointer_of_impl.h" #include "./fuzztest/internal/domains/unique_elements_container_of_impl.h" +#include "./fuzztest/internal/domains/utf.h" #include "./fuzztest/internal/domains/variant_of_impl.h" #include "./fuzztest/internal/logging.h" #include "./fuzztest/internal/meta.h" @@ -1038,6 +1039,30 @@ return inner.WithMinSize(1); } +inline auto Utf8String() { + // Generate valid UTF-8 by first generating a sequence of valid Unicode code + // points and converting it into UTF-8. This will improve the efficiency of + // the test. + // Valid Unicode code point values are in [0, 0x10FFFF], excluding + // [0xD800, 0xDFFF], so generate code points from the two valid subranges. + auto utf8_string = ReversibleMap( + internal::EncodeAsUTF8, + [](const std::string& utf8) + -> std::optional<std::tuple<std::vector<int>>> { + auto code_points = internal::DecodeFromUTF8(utf8); + if (!code_points.has_value()) return std::nullopt; + return *code_points; + }, + ContainerOf<std::vector<int>>( + OneOf(InRange(0, 0xD7FF), InRange(0xE000, 0x10FFFF)))); + // We further overlap it with String() to be able to use the + // dictionary-based mutation. + return OverlapOf(utf8_string, String()) + // Use the same serialization as the previous domain definition to avoid + // widely invalidating the existing corpora/reproducers. + .WithSerializationDomain(0); +} + } // namespace internal_no_adl // Inject the names from internal_no_adl into fuzztest, without allowing for
diff --git a/fuzztest/internal/domains/rune.cc b/fuzztest/internal/domains/rune.cc new file mode 100644 index 0000000..36badf9 --- /dev/null +++ b/fuzztest/internal/domains/rune.cc
@@ -0,0 +1,172 @@ +/* + * The authors of this software are Rob Pike and Ken Thompson. + * Copyright (c) 2002 by Lucent Technologies. + * Permission to use, copy, modify, and distribute this software for any + * purpose without fee is hereby granted, provided that this entire notice + * is included in all copies of any software which is or includes a copy + * or modification of this software and in all copies of the supporting + * documentation for such software. + * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED + * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE + * ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF + * THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. + * + * rune.* have been converted to compile as C++ code in fuzztest::internal + * namespace. + */ + +#include "./fuzztest/internal/domains/rune.h" + +#include <stdarg.h> + +namespace fuzztest::internal { + +enum { + Bit1 = 7, + Bitx = 6, + Bit2 = 5, + Bit3 = 4, + Bit4 = 3, + Bit5 = 2, + + T1 = ((1 << (Bit1 + 1)) - 1) ^ 0xFF, /* 0000 0000 */ + Tx = ((1 << (Bitx + 1)) - 1) ^ 0xFF, /* 1000 0000 */ + T2 = ((1 << (Bit2 + 1)) - 1) ^ 0xFF, /* 1100 0000 */ + T3 = ((1 << (Bit3 + 1)) - 1) ^ 0xFF, /* 1110 0000 */ + T4 = ((1 << (Bit4 + 1)) - 1) ^ 0xFF, /* 1111 0000 */ + T5 = ((1 << (Bit5 + 1)) - 1) ^ 0xFF, /* 1111 1000 */ + + Rune1 = (1 << (Bit1 + 0 * Bitx)) - 1, /* 0000 0000 0111 1111 */ + Rune2 = (1 << (Bit2 + 1 * Bitx)) - 1, /* 0000 0111 1111 1111 */ + Rune3 = (1 << (Bit3 + 2 * Bitx)) - 1, /* 1111 1111 1111 1111 */ + Rune4 = (1 << (Bit4 + 3 * Bitx)) - 1, + /* 0001 1111 1111 1111 1111 1111 */ + + Maskx = (1 << Bitx) - 1, /* 0011 1111 */ + Testx = Maskx ^ 0xFF, /* 1100 0000 */ + + Bad = Runeerror, +}; + +int chartorune(Rune *rune, const char *str) { + int c, c1, c2, c3; + Rune l; + + /* + * one character sequence + * 00000-0007F => T1 + */ + c = *(unsigned char *)str; + if (c < Tx) { + *rune = c; + return 1; + } + + /* + * two character sequence + * 0080-07FF => T2 Tx + */ + c1 = *(unsigned char *)(str + 1) ^ Tx; + if (c1 & Testx) goto bad; + if (c < T3) { + if (c < T2) goto bad; + l = ((c << Bitx) | c1) & Rune2; + if (l <= Rune1) goto bad; + *rune = l; + return 2; + } + + /* + * three character sequence + * 0800-FFFF => T3 Tx Tx + */ + c2 = *(unsigned char *)(str + 2) ^ Tx; + if (c2 & Testx) goto bad; + if (c < T4) { + l = ((((c << Bitx) | c1) << Bitx) | c2) & Rune3; + if (l <= Rune2) goto bad; + *rune = l; + return 3; + } + + /* + * four character sequence (21-bit value) + * 10000-1FFFFF => T4 Tx Tx Tx + */ + c3 = *(unsigned char *)(str + 3) ^ Tx; + if (c3 & Testx) goto bad; + if (c < T5) { + l = ((((((c << Bitx) | c1) << Bitx) | c2) << Bitx) | c3) & Rune4; + if (l <= Rune3) goto bad; + *rune = l; + return 4; + } + + /* + * Support for 5-byte or longer UTF-8 would go here, but + * since we don't have that, we'll just fall through to bad. + */ + + /* + * bad decoding + */ +bad: + *rune = Bad; + return 1; +} + +int runetochar(char *str, const Rune *rune) { + /* Runes are signed, so convert to unsigned for range check. */ + unsigned int c; + + /* + * one character sequence + * 00000-0007F => 00-7F + */ + c = *rune; + if (c <= Rune1) { + str[0] = static_cast<char>(c); + return 1; + } + + /* + * two character sequence + * 0080-07FF => T2 Tx + */ + if (c <= Rune2) { + str[0] = T2 | static_cast<char>(c >> 1 * Bitx); + str[1] = Tx | (c & Maskx); + return 2; + } + + /* + * If the Rune is out of range, convert it to the error rune. + * Do this test here because the error rune encodes to three bytes. + * Doing it earlier would duplicate work, since an out of range + * Rune wouldn't have fit in one or two bytes. + */ + if (c > Runemax) c = Runeerror; + + /* + * three character sequence + * 0800-FFFF => T3 Tx Tx + */ + if (c <= Rune3) { + str[0] = T3 | static_cast<char>(c >> 2 * Bitx); + str[1] = Tx | ((c >> 1 * Bitx) & Maskx); + str[2] = Tx | (c & Maskx); + return 3; + } + + /* + * four character sequence (21-bit value) + * 10000-1FFFFF => T4 Tx Tx Tx + */ + str[0] = T4 | static_cast<char>(c >> 3 * Bitx); + str[1] = Tx | ((c >> 2 * Bitx) & Maskx); + str[2] = Tx | ((c >> 1 * Bitx) & Maskx); + str[3] = Tx | (c & Maskx); + return 4; +} + +} // namespace fuzztest::internal
diff --git a/fuzztest/internal/domains/rune.h b/fuzztest/internal/domains/rune.h new file mode 100644 index 0000000..d62a369 --- /dev/null +++ b/fuzztest/internal/domains/rune.h
@@ -0,0 +1,38 @@ +/* + * The authors of this software are Rob Pike and Ken Thompson. + * Copyright (c) 2002 by Lucent Technologies. + * Permission to use, copy, modify, and distribute this software for any + * purpose without fee is hereby granted, provided that this entire notice + * is included in all copies of any software which is or includes a copy + * or modification of this software and in all copies of the supporting + * documentation for such software. + * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED + * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE + * ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF + * THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. + * + * rune.* have been converted to compile as C++ code in fuzztest::internal + * namespace. + */ + +#ifndef FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_RUNE_H_ +#define FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_RUNE_H_ + +namespace fuzztest::internal { + +typedef signed int Rune; /* Code-point values in Unicode 4.0 are 21 bits wide.*/ + +enum { + UTFmax = 4, /* maximum bytes per rune */ + Runesync = 0x80, /* cannot represent part of a UTF sequence (<) */ + Runeself = 0x80, /* rune and UTF sequences are the same (<) */ + Runeerror = 0xFFFD, /* decoding error in UTF */ + Runemax = 0x10FFFF, /* maximum rune value */ +}; + +int runetochar(char* s, const Rune* r); +int chartorune(Rune* r, const char* s); + +} // namespace fuzztest::internal + +#endif // FUZZTEST_FUZZTEST_INTERNAL_DOMAINS_RUNE_H_
diff --git a/fuzztest/internal/domains/utf.cc b/fuzztest/internal/domains/utf.cc new file mode 100644 index 0000000..60f4b4c --- /dev/null +++ b/fuzztest/internal/domains/utf.cc
@@ -0,0 +1,56 @@ +// Copyright 2025 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/utf.h" + +#include <cstdint> +#include <optional> +#include <string> +#include <vector> + +#include "absl/strings/string_view.h" +#include "./fuzztest/internal/domains/rune.h" + +namespace fuzztest::internal { + +std::string EncodeAsUTF8(const std::vector<int>& code_points) { + std::string out; + out.reserve(code_points.size()); + for (int c : code_points) { + if ((static_cast<uint32_t>(c) < 0xD800) || (c >= 0xE000 && c <= 0x10FFFF)) { + char buf[4]; + out.append(std::string(buf, runetochar(buf, &c))); + } else { + static constexpr char ReplacementChars[] = {'\xEF', '\xBF', '\xBD'}; + out.append(ReplacementChars, sizeof(ReplacementChars)); + } + } + return out; +} + +std::optional<std::vector<int>> DecodeFromUTF8(const std::string& utf8) { + std::vector<int> out; + absl::string_view in(utf8); + out.reserve(in.size()); + while (!in.empty()) { + Rune r; + int len = chartorune(&r, in.data()); + out.push_back(r); + if (r == Runeerror && len != 3) return std::nullopt; + in.remove_prefix(len); + } + return out; +} + +} // namespace fuzztest::internal
diff --git a/fuzztest/internal/domains/utf.h b/fuzztest/internal/domains/utf.h new file mode 100644 index 0000000..a1a94eb --- /dev/null +++ b/fuzztest/internal/domains/utf.h
@@ -0,0 +1,33 @@ +// Copyright 2025 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. + +#ifndef FUZZTEST_INTERNAL_DOMAINS_UTF_H_ +#define FUZZTEST_INTERNAL_DOMAINS_UTF_H_ + +#include <optional> +#include <string> +#include <vector> + +namespace fuzztest::internal { + +// Encode a sequence of code points as UTF-8 string. +std::string EncodeAsUTF8(const std::vector<int>& code_points); + +// Decode a UTF-8 string into a sequence of code points. Returns nullopt if the +// string is not valid UTF-8. +std::optional<std::vector<int>> DecodeFromUTF8(const std::string& utf8); + +} // namespace fuzztest::internal + +#endif // FUZZTEST_INTERNAL_DOMAINS_UTF_H_