diff options
Diffstat (limited to 'absl/strings/internal')
43 files changed, 5244 insertions, 148 deletions
diff --git a/absl/strings/internal/bits.h b/absl/strings/internal/bits.h deleted file mode 100644 index a7d0ee5b..00000000 --- a/absl/strings/internal/bits.h +++ /dev/null @@ -1,55 +0,0 @@ -// Copyright 2018 The Abseil 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 ABSL_STRINGS_INTERNAL_BITS_H_ -#define ABSL_STRINGS_INTERNAL_BITS_H_ - -#include <cstdint> - -#if defined(_MSC_VER) && defined(_M_X64) -#include <intrin.h> -#pragma intrinsic(_BitScanReverse64) -#endif - -namespace absl { -inline namespace lts_2018_06_20 { -namespace strings_internal { - -// Returns the number of leading 0 bits in a 64-bit value. -inline int CountLeadingZeros64(uint64_t n) { -#if defined(__GNUC__) - static_assert(sizeof(unsigned long long) == sizeof(n), // NOLINT(runtime/int) - "__builtin_clzll does not take 64bit arg"); - return n == 0 ? 64 : __builtin_clzll(n); -#elif defined(_MSC_VER) && defined(_M_X64) - unsigned long result; // NOLINT(runtime/int) - if (_BitScanReverse64(&result, n)) { - return 63 - result; - } - return 64; -#else - int zeroes = 60; - if (n >> 32) zeroes -= 32, n >>= 32; - if (n >> 16) zeroes -= 16, n >>= 16; - if (n >> 8) zeroes -= 8, n >>= 8; - if (n >> 4) zeroes -= 4, n >>= 4; - return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0\0"[n] + zeroes; -#endif -} - -} // namespace strings_internal -} // inline namespace lts_2018_06_20 -} // namespace absl - -#endif // ABSL_STRINGS_INTERNAL_BITS_H_ diff --git a/absl/strings/internal/char_map.h b/absl/strings/internal/char_map.h index e1280b03..10b7d007 100644 --- a/absl/strings/internal/char_map.h +++ b/absl/strings/internal/char_map.h @@ -28,7 +28,7 @@ #include "absl/base/port.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { class Charmap { @@ -150,7 +150,7 @@ constexpr Charmap GraphCharmap() { return PrintCharmap() & ~SpaceCharmap(); } constexpr Charmap PunctCharmap() { return GraphCharmap() & ~AlnumCharmap(); } } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_CHAR_MAP_H_ diff --git a/absl/strings/internal/charconv_bigint.cc b/absl/strings/internal/charconv_bigint.cc index eb2e2976..dac907e2 100644 --- a/absl/strings/internal/charconv_bigint.cc +++ b/absl/strings/internal/charconv_bigint.cc @@ -19,7 +19,7 @@ #include <string> namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { namespace { @@ -355,5 +355,5 @@ template class BigUnsigned<4>; template class BigUnsigned<84>; } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl diff --git a/absl/strings/internal/charconv_bigint.h b/absl/strings/internal/charconv_bigint.h index 9827b56e..ffafc11c 100644 --- a/absl/strings/internal/charconv_bigint.h +++ b/absl/strings/internal/charconv_bigint.h @@ -25,7 +25,7 @@ #include "absl/strings/string_view.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { // The largest power that 5 that can be raised to, and still fit in a uint32_t. @@ -58,17 +58,10 @@ class BigUnsigned { "unsupported max_words value"); BigUnsigned() : size_(0), words_{} {} - explicit BigUnsigned(uint32_t v) : size_(v > 0 ? 1 : 0), words_{v} {} - explicit BigUnsigned(uint64_t v) - : size_(0), - words_{static_cast<uint32_t>(v & 0xffffffff), - static_cast<uint32_t>(v >> 32)} { - if (words_[1]) { - size_ = 2; - } else if (words_[0]) { - size_ = 1; - } - } + explicit constexpr BigUnsigned(uint64_t v) + : size_((v >> 32) ? 2 : v ? 1 : 0), + words_{static_cast<uint32_t>(v & 0xffffffffu), + static_cast<uint32_t>(v >> 32)} {} // Constructs a BigUnsigned from the given string_view containing a decimal // value. If the input std::string is not a decimal integer, constructs a 0 @@ -422,7 +415,7 @@ extern template class BigUnsigned<4>; extern template class BigUnsigned<84>; } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_CHARCONV_BIGINT_H_ diff --git a/absl/strings/internal/charconv_bigint_test.cc b/absl/strings/internal/charconv_bigint_test.cc index 118b0dcb..dbab3208 100644 --- a/absl/strings/internal/charconv_bigint_test.cc +++ b/absl/strings/internal/charconv_bigint_test.cc @@ -19,7 +19,7 @@ #include "gtest/gtest.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { TEST(BigUnsigned, ShiftLeft) { @@ -201,5 +201,5 @@ TEST(BigUnsigned, TenToTheNth) { } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl diff --git a/absl/strings/internal/charconv_parse.cc b/absl/strings/internal/charconv_parse.cc index 37d75635..68d65a8a 100644 --- a/absl/strings/internal/charconv_parse.cc +++ b/absl/strings/internal/charconv_parse.cc @@ -22,7 +22,7 @@ #include "absl/strings/internal/memutil.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace { // ParseFloat<10> will read the first 19 significant digits of the mantissa. @@ -92,7 +92,7 @@ static_assert(std::numeric_limits<int>::digits10 >= kDecimalExponentDigitsMax, // To avoid incredibly large inputs causing integer overflow for our exponent, // we impose an arbitrary but very large limit on the number of significant -// digits we will accept. The implementation refuses to match a std::string with +// digits we will accept. The implementation refuses to match a string with // more consecutive significant mantissa digits than this. constexpr int kDecimalDigitLimit = 50000000; @@ -494,5 +494,5 @@ template ParsedFloat ParseFloat<16>(const char* begin, const char* end, chars_format format_flags); } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl diff --git a/absl/strings/internal/charconv_parse.h b/absl/strings/internal/charconv_parse.h index 41f4f40d..17d5a8f8 100644 --- a/absl/strings/internal/charconv_parse.h +++ b/absl/strings/internal/charconv_parse.h @@ -20,7 +20,7 @@ #include "absl/strings/charconv.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { // Enum indicating whether a parsed float is a number or special value. @@ -93,6 +93,6 @@ extern template ParsedFloat ParseFloat<16>(const char* begin, const char* end, absl::chars_format format_flags); } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_CHARCONV_PARSE_H_ diff --git a/absl/strings/internal/charconv_parse_test.cc b/absl/strings/internal/charconv_parse_test.cc index 1ff86004..f48b9aee 100644 --- a/absl/strings/internal/charconv_parse_test.cc +++ b/absl/strings/internal/charconv_parse_test.cc @@ -29,16 +29,16 @@ using absl::strings_internal::ParseFloat; namespace { -// Check that a given std::string input is parsed to the expected mantissa and +// Check that a given string input is parsed to the expected mantissa and // exponent. // -// Input std::string `s` must contain a '$' character. It marks the end of the +// Input string `s` must contain a '$' character. It marks the end of the // characters that should be consumed by the match. It is stripped from the // input to ParseFloat. // -// If input std::string `s` contains '[' and ']' characters, these mark the region +// If input string `s` contains '[' and ']' characters, these mark the region // of characters that should be marked as the "subrange". For NaNs, this is -// the location of the extended NaN std::string. For numbers, this is the location +// the location of the extended NaN string. For numbers, this is the location // of the full, over-large mantissa. template <int base> void ExpectParsedFloat(std::string s, absl::chars_format format_flags, @@ -92,10 +92,10 @@ void ExpectParsedFloat(std::string s, absl::chars_format format_flags, EXPECT_EQ(characters_matched, expected_characters_matched); } -// Check that a given std::string input is parsed to the expected mantissa and +// Check that a given string input is parsed to the expected mantissa and // exponent. // -// Input std::string `s` must contain a '$' character. It marks the end of the +// Input string `s` must contain a '$' character. It marks the end of the // characters that were consumed by the match. template <int base> void ExpectNumber(std::string s, absl::chars_format format_flags, @@ -106,7 +106,7 @@ void ExpectNumber(std::string s, absl::chars_format format_flags, expected_literal_exponent); } -// Check that a given std::string input is parsed to the given special value. +// Check that a given string input is parsed to the given special value. // // This tests against both number bases, since infinities and NaNs have // identical representations in both modes. @@ -116,7 +116,7 @@ void ExpectSpecial(const std::string& s, absl::chars_format format_flags, ExpectParsedFloat<16>(s, format_flags, type, 0, 0); } -// Check that a given input std::string is not matched by Float. +// Check that a given input string is not matched by Float. template <int base> void ExpectFailedParse(absl::string_view s, absl::chars_format format_flags) { ParsedFloat parsed = diff --git a/absl/strings/internal/escaping_test_common.h b/absl/strings/internal/escaping_test_common.h index 478e0582..50ef595f 100644 --- a/absl/strings/internal/escaping_test_common.h +++ b/absl/strings/internal/escaping_test_common.h @@ -22,7 +22,7 @@ #include "absl/strings/string_view.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { struct base64_testcase { @@ -127,7 +127,7 @@ inline const std::array<base64_testcase, 5>& base64_strings() { } } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_ESCAPING_TEST_COMMON_H_ diff --git a/absl/strings/internal/memutil.cc b/absl/strings/internal/memutil.cc index 13ad686c..1d6cfa36 100644 --- a/absl/strings/internal/memutil.cc +++ b/absl/strings/internal/memutil.cc @@ -17,7 +17,7 @@ #include <cstdlib> namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { int memcasecmp(const char* s1, const char* s2, size_t len) { @@ -108,5 +108,5 @@ const char* memmatch(const char* phaystack, size_t haylen, const char* pneedle, } } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl diff --git a/absl/strings/internal/memutil.h b/absl/strings/internal/memutil.h index 828b01d5..dcc5c9a3 100644 --- a/absl/strings/internal/memutil.h +++ b/absl/strings/internal/memutil.h @@ -14,7 +14,7 @@ // limitations under the License. // -// These routines provide mem versions of standard C std::string routines, +// These routines provide mem versions of standard C string routines, // such as strpbrk. They function exactly the same as the str versions, // so if you wonder what they are, replace the word "mem" by // "str" and check out the man page. I could return void*, as the @@ -22,14 +22,14 @@ // since this is by far the most common way these functions are called. // // The difference between the mem and str versions is the mem version -// takes a pointer and a length, rather than a '\0'-terminated std::string. +// takes a pointer and a length, rather than a '\0'-terminated string. // The memcase* routines defined here assume the locale is "C" // (they use absl::ascii_tolower instead of tolower). // // These routines are based on the BSD library. // -// Here's a list of routines from std::string.h, and their mem analogues. -// Functions in lowercase are defined in std::string.h; those in UPPERCASE +// Here's a list of routines from string.h, and their mem analogues. +// Functions in lowercase are defined in string.h; those in UPPERCASE // are defined here: // // strlen -- @@ -69,7 +69,7 @@ #include "absl/strings/ascii.h" // for absl::ascii_tolower namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { inline char* memcat(char* dest, size_t destlen, const char* src, @@ -142,7 +142,7 @@ const char* memmatch(const char* phaystack, size_t haylen, const char* pneedle, size_t neelen); } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_MEMUTIL_H_ diff --git a/absl/strings/internal/numbers_test_common.h b/absl/strings/internal/numbers_test_common.h index a511dcf7..32aa0bfa 100644 --- a/absl/strings/internal/numbers_test_common.h +++ b/absl/strings/internal/numbers_test_common.h @@ -24,7 +24,7 @@ #include <string> namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { template <typename IntType> @@ -65,11 +65,11 @@ struct uint32_test_case { inline const std::array<uint32_test_case, 27>& strtouint32_test_cases() { static const std::array<uint32_test_case, 27> test_cases{{ - {"0xffffffff", true, 16, std::numeric_limits<uint32_t>::max()}, + {"0xffffffff", true, 16, (std::numeric_limits<uint32_t>::max)()}, {"0x34234324", true, 16, 0x34234324}, {"34234324", true, 16, 0x34234324}, {"0", true, 16, 0}, - {" \t\n 0xffffffff", true, 16, std::numeric_limits<uint32_t>::max()}, + {" \t\n 0xffffffff", true, 16, (std::numeric_limits<uint32_t>::max)()}, {" \f\v 46", true, 10, 46}, // must accept weird whitespace {" \t\n 72717222", true, 8, 072717222}, {" \t\n 072717222", true, 8, 072717222}, @@ -78,7 +78,7 @@ inline const std::array<uint32_test_case, 27>& strtouint32_test_cases() { // Base-10 version. {"34234324", true, 0, 34234324}, - {"4294967295", true, 0, std::numeric_limits<uint32_t>::max()}, + {"4294967295", true, 0, (std::numeric_limits<uint32_t>::max)()}, {"34234324 \n\t", true, 10, 34234324}, // Unusual base @@ -97,8 +97,8 @@ inline const std::array<uint32_test_case, 27>& strtouint32_test_cases() { {" \t\n -123", false, 0, 0}, // Out of bounds. - {"4294967296", false, 0, std::numeric_limits<uint32_t>::max()}, - {"0x100000000", false, 0, std::numeric_limits<uint32_t>::max()}, + {"4294967296", false, 0, (std::numeric_limits<uint32_t>::max)()}, + {"0x100000000", false, 0, (std::numeric_limits<uint32_t>::max)()}, {nullptr, false, 0, 0}, }}; return test_cases; @@ -120,7 +120,7 @@ inline const std::array<uint64_test_case, 34>& strtouint64_test_cases() { {"000", true, 0, 0}, {"0", true, 0, 0}, {" \t\n 0xffffffffffffffff", true, 16, - std::numeric_limits<uint64_t>::max()}, + (std::numeric_limits<uint64_t>::max)()}, {"012345670123456701234", true, 8, int64_t{012345670123456701234}}, {"12345670123456701234", true, 8, int64_t{012345670123456701234}}, @@ -131,7 +131,7 @@ inline const std::array<uint64_test_case, 34>& strtouint64_test_cases() { {"34234324487834466", true, 0, int64_t{34234324487834466}}, {" \t\n 18446744073709551615", true, 0, - std::numeric_limits<uint64_t>::max()}, + (std::numeric_limits<uint64_t>::max)()}, {"34234324487834466 \n\t ", true, 0, int64_t{34234324487834466}}, @@ -157,12 +157,13 @@ inline const std::array<uint64_test_case, 34>& strtouint64_test_cases() { // Out of bounds. {"18446744073709551616", false, 10, 0}, {"18446744073709551616", false, 0, 0}, - {"0x10000000000000000", false, 16, std::numeric_limits<uint64_t>::max()}, + {"0x10000000000000000", false, 16, + (std::numeric_limits<uint64_t>::max)()}, {"0X10000000000000000", false, 16, - std::numeric_limits<uint64_t>::max()}, // 0X versus 0x. - {"0x10000000000000000", false, 0, std::numeric_limits<uint64_t>::max()}, + (std::numeric_limits<uint64_t>::max)()}, // 0X versus 0x. + {"0x10000000000000000", false, 0, (std::numeric_limits<uint64_t>::max)()}, {"0X10000000000000000", false, 0, - std::numeric_limits<uint64_t>::max()}, // 0X versus 0x. + (std::numeric_limits<uint64_t>::max)()}, // 0X versus 0x. {"0x1234", true, 16, 0x1234}, @@ -174,7 +175,7 @@ inline const std::array<uint64_test_case, 34>& strtouint64_test_cases() { } } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_NUMBERS_TEST_COMMON_H_ diff --git a/absl/strings/internal/ostringstream.cc b/absl/strings/internal/ostringstream.cc index 9fe5b3c5..77f4b0b3 100644 --- a/absl/strings/internal/ostringstream.cc +++ b/absl/strings/internal/ostringstream.cc @@ -15,7 +15,7 @@ #include "absl/strings/internal/ostringstream.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { OStringStream::Buf::int_type OStringStream::overflow(int c) { @@ -32,5 +32,5 @@ std::streamsize OStringStream::xsputn(const char* s, std::streamsize n) { } } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl diff --git a/absl/strings/internal/ostringstream.h b/absl/strings/internal/ostringstream.h index 66ae3c29..908e170c 100644 --- a/absl/strings/internal/ostringstream.h +++ b/absl/strings/internal/ostringstream.h @@ -23,21 +23,21 @@ #include "absl/base/port.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { -// The same as std::ostringstream but appends to a user-specified std::string, +// The same as std::ostringstream but appends to a user-specified string, // and is faster. It is ~70% faster to create, ~50% faster to write to, and -// completely free to extract the result std::string. +// completely free to extract the result string. // -// std::string s; +// string s; // OStringStream strm(&s); // strm << 42 << ' ' << 3.14; // appends to `s` // // The stream object doesn't have to be named. Starting from C++11 operator<< // works with rvalues of std::ostream. // -// std::string s; +// string s; // OStringStream(&s) << 42 << ' ' << 3.14; // appends to `s` // // OStringStream is faster to create than std::ostringstream but it's still @@ -46,14 +46,14 @@ namespace strings_internal { // // Creates unnecessary instances of OStringStream: slow. // -// std::string s; +// string s; // OStringStream(&s) << 42; // OStringStream(&s) << ' '; // OStringStream(&s) << 3.14; // // Creates a single instance of OStringStream and reuses it: fast. // -// std::string s; +// string s; // OStringStream strm(&s); // strm << 42; // strm << ' '; @@ -83,7 +83,7 @@ class OStringStream : private std::basic_streambuf<char>, public std::ostream { }; } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_OSTRINGSTREAM_H_ diff --git a/absl/strings/internal/pow10_helper.cc b/absl/strings/internal/pow10_helper.cc new file mode 100644 index 00000000..c7f4875a --- /dev/null +++ b/absl/strings/internal/pow10_helper.cc @@ -0,0 +1,122 @@ +// Copyright 2018 The Abseil 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 "absl/strings/internal/pow10_helper.h" + +#include <cmath> + +namespace absl { +inline namespace lts_2018_12_18 { +namespace strings_internal { + +namespace { + +// The exact value of 1e23 falls precisely halfway between two representable +// doubles. Furthermore, the rounding rules we prefer (break ties by rounding +// to the nearest even) dictate in this case that the number should be rounded +// down, but this is not completely specified for floating-point literals in +// C++. (It just says to use the default rounding mode of the standard +// library.) We ensure the result we want by using a number that has an +// unambiguous correctly rounded answer. +constexpr double k1e23 = 9999999999999999e7; + +constexpr double kPowersOfTen[] = { + 0.0, 1e-323, 1e-322, 1e-321, 1e-320, 1e-319, 1e-318, 1e-317, 1e-316, + 1e-315, 1e-314, 1e-313, 1e-312, 1e-311, 1e-310, 1e-309, 1e-308, 1e-307, + 1e-306, 1e-305, 1e-304, 1e-303, 1e-302, 1e-301, 1e-300, 1e-299, 1e-298, + 1e-297, 1e-296, 1e-295, 1e-294, 1e-293, 1e-292, 1e-291, 1e-290, 1e-289, + 1e-288, 1e-287, 1e-286, 1e-285, 1e-284, 1e-283, 1e-282, 1e-281, 1e-280, + 1e-279, 1e-278, 1e-277, 1e-276, 1e-275, 1e-274, 1e-273, 1e-272, 1e-271, + 1e-270, 1e-269, 1e-268, 1e-267, 1e-266, 1e-265, 1e-264, 1e-263, 1e-262, + 1e-261, 1e-260, 1e-259, 1e-258, 1e-257, 1e-256, 1e-255, 1e-254, 1e-253, + 1e-252, 1e-251, 1e-250, 1e-249, 1e-248, 1e-247, 1e-246, 1e-245, 1e-244, + 1e-243, 1e-242, 1e-241, 1e-240, 1e-239, 1e-238, 1e-237, 1e-236, 1e-235, + 1e-234, 1e-233, 1e-232, 1e-231, 1e-230, 1e-229, 1e-228, 1e-227, 1e-226, + 1e-225, 1e-224, 1e-223, 1e-222, 1e-221, 1e-220, 1e-219, 1e-218, 1e-217, + 1e-216, 1e-215, 1e-214, 1e-213, 1e-212, 1e-211, 1e-210, 1e-209, 1e-208, + 1e-207, 1e-206, 1e-205, 1e-204, 1e-203, 1e-202, 1e-201, 1e-200, 1e-199, + 1e-198, 1e-197, 1e-196, 1e-195, 1e-194, 1e-193, 1e-192, 1e-191, 1e-190, + 1e-189, 1e-188, 1e-187, 1e-186, 1e-185, 1e-184, 1e-183, 1e-182, 1e-181, + 1e-180, 1e-179, 1e-178, 1e-177, 1e-176, 1e-175, 1e-174, 1e-173, 1e-172, + 1e-171, 1e-170, 1e-169, 1e-168, 1e-167, 1e-166, 1e-165, 1e-164, 1e-163, + 1e-162, 1e-161, 1e-160, 1e-159, 1e-158, 1e-157, 1e-156, 1e-155, 1e-154, + 1e-153, 1e-152, 1e-151, 1e-150, 1e-149, 1e-148, 1e-147, 1e-146, 1e-145, + 1e-144, 1e-143, 1e-142, 1e-141, 1e-140, 1e-139, 1e-138, 1e-137, 1e-136, + 1e-135, 1e-134, 1e-133, 1e-132, 1e-131, 1e-130, 1e-129, 1e-128, 1e-127, + 1e-126, 1e-125, 1e-124, 1e-123, 1e-122, 1e-121, 1e-120, 1e-119, 1e-118, + 1e-117, 1e-116, 1e-115, 1e-114, 1e-113, 1e-112, 1e-111, 1e-110, 1e-109, + 1e-108, 1e-107, 1e-106, 1e-105, 1e-104, 1e-103, 1e-102, 1e-101, 1e-100, + 1e-99, 1e-98, 1e-97, 1e-96, 1e-95, 1e-94, 1e-93, 1e-92, 1e-91, + 1e-90, 1e-89, 1e-88, 1e-87, 1e-86, 1e-85, 1e-84, 1e-83, 1e-82, + 1e-81, 1e-80, 1e-79, 1e-78, 1e-77, 1e-76, 1e-75, 1e-74, 1e-73, + 1e-72, 1e-71, 1e-70, 1e-69, 1e-68, 1e-67, 1e-66, 1e-65, 1e-64, + 1e-63, 1e-62, 1e-61, 1e-60, 1e-59, 1e-58, 1e-57, 1e-56, 1e-55, + 1e-54, 1e-53, 1e-52, 1e-51, 1e-50, 1e-49, 1e-48, 1e-47, 1e-46, + 1e-45, 1e-44, 1e-43, 1e-42, 1e-41, 1e-40, 1e-39, 1e-38, 1e-37, + 1e-36, 1e-35, 1e-34, 1e-33, 1e-32, 1e-31, 1e-30, 1e-29, 1e-28, + 1e-27, 1e-26, 1e-25, 1e-24, 1e-23, 1e-22, 1e-21, 1e-20, 1e-19, + 1e-18, 1e-17, 1e-16, 1e-15, 1e-14, 1e-13, 1e-12, 1e-11, 1e-10, + 1e-9, 1e-8, 1e-7, 1e-6, 1e-5, 1e-4, 1e-3, 1e-2, 1e-1, + 1e+0, 1e+1, 1e+2, 1e+3, 1e+4, 1e+5, 1e+6, 1e+7, 1e+8, + 1e+9, 1e+10, 1e+11, 1e+12, 1e+13, 1e+14, 1e+15, 1e+16, 1e+17, + 1e+18, 1e+19, 1e+20, 1e+21, 1e+22, k1e23, 1e+24, 1e+25, 1e+26, + 1e+27, 1e+28, 1e+29, 1e+30, 1e+31, 1e+32, 1e+33, 1e+34, 1e+35, + 1e+36, 1e+37, 1e+38, 1e+39, 1e+40, 1e+41, 1e+42, 1e+43, 1e+44, + 1e+45, 1e+46, 1e+47, 1e+48, 1e+49, 1e+50, 1e+51, 1e+52, 1e+53, + 1e+54, 1e+55, 1e+56, 1e+57, 1e+58, 1e+59, 1e+60, 1e+61, 1e+62, + 1e+63, 1e+64, 1e+65, 1e+66, 1e+67, 1e+68, 1e+69, 1e+70, 1e+71, + 1e+72, 1e+73, 1e+74, 1e+75, 1e+76, 1e+77, 1e+78, 1e+79, 1e+80, + 1e+81, 1e+82, 1e+83, 1e+84, 1e+85, 1e+86, 1e+87, 1e+88, 1e+89, + 1e+90, 1e+91, 1e+92, 1e+93, 1e+94, 1e+95, 1e+96, 1e+97, 1e+98, + 1e+99, 1e+100, 1e+101, 1e+102, 1e+103, 1e+104, 1e+105, 1e+106, 1e+107, + 1e+108, 1e+109, 1e+110, 1e+111, 1e+112, 1e+113, 1e+114, 1e+115, 1e+116, + 1e+117, 1e+118, 1e+119, 1e+120, 1e+121, 1e+122, 1e+123, 1e+124, 1e+125, + 1e+126, 1e+127, 1e+128, 1e+129, 1e+130, 1e+131, 1e+132, 1e+133, 1e+134, + 1e+135, 1e+136, 1e+137, 1e+138, 1e+139, 1e+140, 1e+141, 1e+142, 1e+143, + 1e+144, 1e+145, 1e+146, 1e+147, 1e+148, 1e+149, 1e+150, 1e+151, 1e+152, + 1e+153, 1e+154, 1e+155, 1e+156, 1e+157, 1e+158, 1e+159, 1e+160, 1e+161, + 1e+162, 1e+163, 1e+164, 1e+165, 1e+166, 1e+167, 1e+168, 1e+169, 1e+170, + 1e+171, 1e+172, 1e+173, 1e+174, 1e+175, 1e+176, 1e+177, 1e+178, 1e+179, + 1e+180, 1e+181, 1e+182, 1e+183, 1e+184, 1e+185, 1e+186, 1e+187, 1e+188, + 1e+189, 1e+190, 1e+191, 1e+192, 1e+193, 1e+194, 1e+195, 1e+196, 1e+197, + 1e+198, 1e+199, 1e+200, 1e+201, 1e+202, 1e+203, 1e+204, 1e+205, 1e+206, + 1e+207, 1e+208, 1e+209, 1e+210, 1e+211, 1e+212, 1e+213, 1e+214, 1e+215, + 1e+216, 1e+217, 1e+218, 1e+219, 1e+220, 1e+221, 1e+222, 1e+223, 1e+224, + 1e+225, 1e+226, 1e+227, 1e+228, 1e+229, 1e+230, 1e+231, 1e+232, 1e+233, + 1e+234, 1e+235, 1e+236, 1e+237, 1e+238, 1e+239, 1e+240, 1e+241, 1e+242, + 1e+243, 1e+244, 1e+245, 1e+246, 1e+247, 1e+248, 1e+249, 1e+250, 1e+251, + 1e+252, 1e+253, 1e+254, 1e+255, 1e+256, 1e+257, 1e+258, 1e+259, 1e+260, + 1e+261, 1e+262, 1e+263, 1e+264, 1e+265, 1e+266, 1e+267, 1e+268, 1e+269, + 1e+270, 1e+271, 1e+272, 1e+273, 1e+274, 1e+275, 1e+276, 1e+277, 1e+278, + 1e+279, 1e+280, 1e+281, 1e+282, 1e+283, 1e+284, 1e+285, 1e+286, 1e+287, + 1e+288, 1e+289, 1e+290, 1e+291, 1e+292, 1e+293, 1e+294, 1e+295, 1e+296, + 1e+297, 1e+298, 1e+299, 1e+300, 1e+301, 1e+302, 1e+303, 1e+304, 1e+305, + 1e+306, 1e+307, 1e+308, +}; + +} // namespace + +double Pow10(int exp) { + if (exp < -324) { + return 0.0; + } else if (exp > 308) { + return INFINITY; + } else { + return kPowersOfTen[exp + 324]; + } +} + +} // namespace strings_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/pow10_helper.h b/absl/strings/internal/pow10_helper.h new file mode 100644 index 00000000..750051bd --- /dev/null +++ b/absl/strings/internal/pow10_helper.h @@ -0,0 +1,38 @@ +// +// Copyright 2018 The Abseil 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. +// +// This test helper library contains a table of powers of 10, to guarantee +// precise values are computed across the full range of doubles. We can't rely +// on the pow() function, because not all standard libraries ship a version +// that is precise. +#ifndef ABSL_STRINGS_POW10_HELPER_H_ +#define ABSL_STRINGS_POW10_HELPER_H_ + +#include <vector> + +namespace absl { +inline namespace lts_2018_12_18 { +namespace strings_internal { + +// Computes the precise value of 10^exp. (I.e. the nearest representable +// double to the exact value, rounding to nearest-even in the (single) case of +// being exactly halfway between.) +double Pow10(int exp); + +} // namespace strings_internal +} // inline namespace lts_2018_12_18 +} // namespace absl + +#endif // ABSL_STRINGS_POW10_HELPER_H_ diff --git a/absl/strings/internal/pow10_helper_test.cc b/absl/strings/internal/pow10_helper_test.cc new file mode 100644 index 00000000..371fe122 --- /dev/null +++ b/absl/strings/internal/pow10_helper_test.cc @@ -0,0 +1,122 @@ +// Copyright 2018 The Abseil 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 "absl/strings/internal/pow10_helper.h" + +#include <cmath> + +#include "gtest/gtest.h" +#include "absl/strings/str_format.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace strings_internal { + +namespace { + +struct TestCase { + int power; // Testing Pow10(power) + uint64_t significand; // Raw bits of the expected value + int radix; // significand is adjusted by 2^radix +}; + +TEST(Pow10HelperTest, Works) { + // The logic in pow10_helper.cc is so simple that theoretically we don't even + // need a test. However, we're paranoid and believe that there may be + // compilers that don't round floating-point literals correctly, even though + // it is specified by the standard. We check various edge cases, just to be + // sure. + constexpr TestCase kTestCases[] = { + // Subnormals + {-323, 0x2, -1074}, + {-322, 0x14, -1074}, + {-321, 0xca, -1074}, + {-320, 0x7e8, -1074}, + {-319, 0x4f10, -1074}, + {-318, 0x316a2, -1074}, + {-317, 0x1ee257, -1074}, + {-316, 0x134d761, -1074}, + {-315, 0xc1069cd, -1074}, + {-314, 0x78a42205, -1074}, + {-313, 0x4b6695433, -1074}, + {-312, 0x2f201d49fb, -1074}, + {-311, 0x1d74124e3d1, -1074}, + {-310, 0x12688b70e62b, -1074}, + {-309, 0xb8157268fdaf, -1074}, + {-308, 0x730d67819e8d2, -1074}, + // Values that are very close to rounding the other way. + // Comment shows difference of significand from the true value. + {-307, 0x11fa182c40c60d, -1072}, // -.4588 + {-290, 0x18f2b061aea072, -1016}, // .4854 + {-276, 0x11BA03F5B21000, -969}, // .4709 + {-259, 0x1899C2F6732210, -913}, // .4830 + {-252, 0x1D53844EE47DD1, -890}, // -.4743 + {-227, 0x1E5297287C2F45, -807}, // -.4708 + {-198, 0x1322E220A5B17E, -710}, // -.4714 + {-195, 0x12B010D3E1CF56, -700}, // .4928 + {-192, 0x123FF06EEA847A, -690}, // .4968 + {-163, 0x1708D0F84D3DE7, -594}, // -.4977 + {-145, 0x13FAAC3E3FA1F3, -534}, // -.4785 + {-111, 0x133D4032C2C7F5, -421}, // .4774 + {-106, 0x1D5B561574765B, -405}, // -.4869 + {-104, 0x16EF5B40C2FC77, -398}, // -.4741 + {-88, 0x197683DF2F268D, -345}, // -.4738 + {-86, 0x13E497065CD61F, -338}, // .4736 + {-76, 0x17288E1271F513, -305}, // -.4761 + {-63, 0x1A53FC9631D10D, -262}, // .4929 + {-30, 0x14484BFEEBC2A0, -152}, // .4758 + {-21, 0x12E3B40A0E9B4F, -122}, // -.4916 + {-5, 0x14F8B588E368F1, -69}, // .4829 + {23, 0x152D02C7E14AF6, 24}, // -.5000 (exactly, round-to-even) + {29, 0x1431E0FAE6D721, 44}, // -.4870 + {34, 0x1ED09BEAD87C03, 60}, // -.4721 + {70, 0x172EBAD6DDC73D, 180}, // .4733 + {105, 0x1BE7ABD3781ECA, 296}, // -.4850 + {126, 0x17A2ECC414A03F, 366}, // -.4999 + {130, 0x1CDA62055B2D9E, 379}, // .4855 + {165, 0x115D847AD00087, 496}, // -.4913 + {172, 0x14B378469B6732, 519}, // .4818 + {187, 0x1262DFEEBBB0F9, 569}, // -.4805 + {210, 0x18557F31326BBB, 645}, // -.4992 + {212, 0x1302CB5E6F642A, 652}, // -.4838 + {215, 0x1290BA9A38C7D1, 662}, // -.4881 + {236, 0x1F736F9B3494E9, 731}, // .4707 + {244, 0x176EC98994F489, 758}, // .4924 + {250, 0x1658E3AB795204, 778}, // -.4963 + {252, 0x117571DDF6C814, 785}, // .4873 + {254, 0x1B4781EAD1989E, 791}, // -.4887 + {260, 0x1A03FDE214CAF1, 811}, // .4784 + {284, 0x1585041B2C477F, 891}, // .4798 + {304, 0x1D2A1BE4048F90, 957}, // -.4987 + // Out-of-range values + {-324, 0x0, 0}, + {-325, 0x0, 0}, + {-326, 0x0, 0}, + {309, 1, 2000}, + {310, 1, 2000}, + {311, 1, 2000}, + }; + for (const TestCase& test_case : kTestCases) { + EXPECT_EQ(Pow10(test_case.power), + std::ldexp(test_case.significand, test_case.radix)) + << absl::StrFormat("Failure for Pow10(%d): %a vs %a", test_case.power, + Pow10(test_case.power), + std::ldexp(test_case.significand, test_case.radix)); + } +} + +} // namespace +} // namespace strings_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/resize_uninitialized.h b/absl/strings/internal/resize_uninitialized.h index b3690332..2951bf84 100644 --- a/absl/strings/internal/resize_uninitialized.h +++ b/absl/strings/internal/resize_uninitialized.h @@ -24,7 +24,7 @@ #include "absl/meta/type_traits.h" // for void_t namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { // Is a subclass of true_type or false_type, depending on whether or not @@ -45,8 +45,8 @@ void ResizeUninit(string_type* s, size_t new_size, std::false_type) { s->resize(new_size); } -// Returns true if the std::string implementation supports a resize where -// the new characters added to the std::string are left untouched. +// Returns true if the string implementation supports a resize where +// the new characters added to the string are left untouched. // // (A better name might be "STLStringSupportsUninitializedResize", alluding to // the previous function.) @@ -58,14 +58,14 @@ inline constexpr bool STLStringSupportsNontrashingResize(string_type*) { // Like str->resize(new_size), except any new characters added to "*str" as a // result of resizing may be left uninitialized, rather than being filled with // '0' bytes. Typically used when code is then going to overwrite the backing -// store of the std::string with known data. Uses a Google extension to std::string. +// store of the string with known data. Uses a Google extension to ::string. template <typename string_type, typename = void> inline void STLStringResizeUninitialized(string_type* s, size_t new_size) { ResizeUninit(s, new_size, HasResizeUninitialized<string_type>()); } } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_RESIZE_UNINITIALIZED_H_ diff --git a/absl/strings/internal/stl_type_traits.h b/absl/strings/internal/stl_type_traits.h index 7fc56a3c..fed7bf7c 100644 --- a/absl/strings/internal/stl_type_traits.h +++ b/absl/strings/internal/stl_type_traits.h @@ -40,7 +40,7 @@ #include "absl/meta/type_traits.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { template <typename C, template <typename...> class T> @@ -243,6 +243,6 @@ struct IsStrictlyBaseOfAndConvertibleToSTLContainer IsConvertibleToSTLContainer<C>> {}; } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_STL_TYPE_TRAITS_H_ diff --git a/absl/strings/internal/str_format/arg.cc b/absl/strings/internal/str_format/arg.cc new file mode 100644 index 00000000..e5e1eee5 --- /dev/null +++ b/absl/strings/internal/str_format/arg.cc @@ -0,0 +1,379 @@ +// +// POSIX spec: +// http://pubs.opengroup.org/onlinepubs/009695399/functions/fprintf.html +// +#include "absl/strings/internal/str_format/arg.h" + +#include <cassert> +#include <cerrno> +#include <cstdlib> +#include <string> +#include <type_traits> + +#include "absl/base/port.h" +#include "absl/strings/internal/str_format/float_conversion.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { +namespace { + +const char kDigit[2][32] = { "0123456789abcdef", "0123456789ABCDEF" }; + +// Reduce *capacity by s.size(), clipped to a 0 minimum. +void ReducePadding(string_view s, size_t *capacity) { + *capacity = Excess(s.size(), *capacity); +} + +// Reduce *capacity by n, clipped to a 0 minimum. +void ReducePadding(size_t n, size_t *capacity) { + *capacity = Excess(n, *capacity); +} + +template <typename T> +struct MakeUnsigned : std::make_unsigned<T> {}; +template <> +struct MakeUnsigned<absl::uint128> { + using type = absl::uint128; +}; + +template <typename T> +struct IsSigned : std::is_signed<T> {}; +template <> +struct IsSigned<absl::uint128> : std::false_type {}; + +class ConvertedIntInfo { + public: + template <typename T> + ConvertedIntInfo(T v, ConversionChar conv) { + using Unsigned = typename MakeUnsigned<T>::type; + auto u = static_cast<Unsigned>(v); + if (IsNeg(v)) { + is_neg_ = true; + u = Unsigned{} - u; + } else { + is_neg_ = false; + } + UnsignedToStringRight(u, conv); + } + + string_view digits() const { + return {end() - size_, static_cast<size_t>(size_)}; + } + bool is_neg() const { return is_neg_; } + + private: + template <typename T, bool IsSigned> + struct IsNegImpl { + static bool Eval(T v) { return v < 0; } + }; + template <typename T> + struct IsNegImpl<T, false> { + static bool Eval(T) { + return false; + } + }; + + template <typename T> + bool IsNeg(T v) { + return IsNegImpl<T, IsSigned<T>::value>::Eval(v); + } + + template <typename T> + void UnsignedToStringRight(T u, ConversionChar conv) { + char *p = end(); + switch (conv.radix()) { + default: + case 10: + for (; u; u /= 10) + *--p = static_cast<char>('0' + static_cast<size_t>(u % 10)); + break; + case 8: + for (; u; u /= 8) + *--p = static_cast<char>('0' + static_cast<size_t>(u % 8)); + break; + case 16: { + const char *digits = kDigit[conv.upper() ? 1 : 0]; + for (; u; u /= 16) *--p = digits[static_cast<size_t>(u % 16)]; + break; + } + } + size_ = static_cast<int>(end() - p); + } + + const char *end() const { return storage_ + sizeof(storage_); } + char *end() { return storage_ + sizeof(storage_); } + + bool is_neg_; + int size_; + // Max size: 128 bit value as octal -> 43 digits + char storage_[128 / 3 + 1]; +}; + +// Note: 'o' conversions do not have a base indicator, it's just that +// the '#' flag is specified to modify the precision for 'o' conversions. +string_view BaseIndicator(const ConvertedIntInfo &info, + const ConversionSpec conv) { + bool alt = conv.flags().alt; + int radix = conv.conv().radix(); + if (conv.conv().id() == ConversionChar::p) + alt = true; // always show 0x for %p. + // From the POSIX description of '#' flag: + // "For x or X conversion specifiers, a non-zero result shall have + // 0x (or 0X) prefixed to it." + if (alt && radix == 16 && !info.digits().empty()) { + if (conv.conv().upper()) return "0X"; + return "0x"; + } + return {}; +} + +string_view SignColumn(bool neg, const ConversionSpec conv) { + if (conv.conv().is_signed()) { + if (neg) return "-"; + if (conv.flags().show_pos) return "+"; + if (conv.flags().sign_col) return " "; + } + return {}; +} + +bool ConvertCharImpl(unsigned char v, const ConversionSpec conv, + FormatSinkImpl *sink) { + size_t fill = 0; + if (conv.width() >= 0) fill = conv.width(); + ReducePadding(1, &fill); + if (!conv.flags().left) sink->Append(fill, ' '); + sink->Append(1, v); + if (conv.flags().left) sink->Append(fill, ' '); + return true; +} + +bool ConvertIntImplInner(const ConvertedIntInfo &info, + const ConversionSpec conv, FormatSinkImpl *sink) { + // Print as a sequence of Substrings: + // [left_spaces][sign][base_indicator][zeroes][formatted][right_spaces] + size_t fill = 0; + if (conv.width() >= 0) fill = conv.width(); + + string_view formatted = info.digits(); + ReducePadding(formatted, &fill); + + string_view sign = SignColumn(info.is_neg(), conv); + ReducePadding(sign, &fill); + + string_view base_indicator = BaseIndicator(info, conv); + ReducePadding(base_indicator, &fill); + + int precision = conv.precision(); + bool precision_specified = precision >= 0; + if (!precision_specified) + precision = 1; + + if (conv.flags().alt && conv.conv().id() == ConversionChar::o) { + // From POSIX description of the '#' (alt) flag: + // "For o conversion, it increases the precision (if necessary) to + // force the first digit of the result to be zero." + if (formatted.empty() || *formatted.begin() != '0') { + int needed = static_cast<int>(formatted.size()) + 1; + precision = std::max(precision, needed); + } + } + + size_t num_zeroes = Excess(formatted.size(), precision); + ReducePadding(num_zeroes, &fill); + + size_t num_left_spaces = !conv.flags().left ? fill : 0; + size_t num_right_spaces = conv.flags().left ? fill : 0; + + // From POSIX description of the '0' (zero) flag: + // "For d, i, o, u, x, and X conversion specifiers, if a precision + // is specified, the '0' flag is ignored." + if (!precision_specified && conv.flags().zero) { + num_zeroes += num_left_spaces; + num_left_spaces = 0; + } + + sink->Append(num_left_spaces, ' '); + sink->Append(sign); + sink->Append(base_indicator); + sink->Append(num_zeroes, '0'); + sink->Append(formatted); + sink->Append(num_right_spaces, ' '); + return true; +} + +template <typename T> +bool ConvertIntImplInner(T v, const ConversionSpec conv, FormatSinkImpl *sink) { + ConvertedIntInfo info(v, conv.conv()); + if (conv.flags().basic && conv.conv().id() != ConversionChar::p) { + if (info.is_neg()) sink->Append(1, '-'); + if (info.digits().empty()) { + sink->Append(1, '0'); + } else { + sink->Append(info.digits()); + } + return true; + } + return ConvertIntImplInner(info, conv, sink); +} + +template <typename T> +bool ConvertIntArg(T v, const ConversionSpec conv, FormatSinkImpl *sink) { + if (conv.conv().is_float()) { + return FormatConvertImpl(static_cast<double>(v), conv, sink).value; + } + if (conv.conv().id() == ConversionChar::c) + return ConvertCharImpl(static_cast<unsigned char>(v), conv, sink); + if (!conv.conv().is_integral()) + return false; + if (!conv.conv().is_signed() && IsSigned<T>::value) { + using U = typename MakeUnsigned<T>::type; + return FormatConvertImpl(static_cast<U>(v), conv, sink).value; + } + return ConvertIntImplInner(v, conv, sink); +} + +template <typename T> +bool ConvertFloatArg(T v, const ConversionSpec conv, FormatSinkImpl *sink) { + return conv.conv().is_float() && ConvertFloatImpl(v, conv, sink); +} + +inline bool ConvertStringArg(string_view v, const ConversionSpec conv, + FormatSinkImpl *sink) { + if (conv.conv().id() != ConversionChar::s) + return false; + if (conv.flags().basic) { + sink->Append(v); + return true; + } + return sink->PutPaddedString(v, conv.width(), conv.precision(), + conv.flags().left); +} + +} // namespace + +// ==================== Strings ==================== +ConvertResult<Conv::s> FormatConvertImpl(const std::string &v, + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertStringArg(v, conv, sink)}; +} + +ConvertResult<Conv::s> FormatConvertImpl(string_view v, + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertStringArg(v, conv, sink)}; +} + +ConvertResult<Conv::s | Conv::p> FormatConvertImpl(const char *v, + const ConversionSpec conv, + FormatSinkImpl *sink) { + if (conv.conv().id() == ConversionChar::p) + return {FormatConvertImpl(VoidPtr(v), conv, sink).value}; + size_t len; + if (v == nullptr) { + len = 0; + } else if (conv.precision() < 0) { + len = std::strlen(v); + } else { + // If precision is set, we look for the null terminator on the valid range. + len = std::find(v, v + conv.precision(), '\0') - v; + } + return {ConvertStringArg(string_view(v, len), conv, sink)}; +} + +// ==================== Raw pointers ==================== +ConvertResult<Conv::p> FormatConvertImpl(VoidPtr v, const ConversionSpec conv, + FormatSinkImpl *sink) { + if (conv.conv().id() != ConversionChar::p) + return {false}; + if (!v.value) { + sink->Append("(nil)"); + return {true}; + } + return {ConvertIntImplInner(v.value, conv, sink)}; +} + +// ==================== Floats ==================== +FloatingConvertResult FormatConvertImpl(float v, const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertFloatArg(v, conv, sink)}; +} +FloatingConvertResult FormatConvertImpl(double v, const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertFloatArg(v, conv, sink)}; +} +FloatingConvertResult FormatConvertImpl(long double v, + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertFloatArg(v, conv, sink)}; +} + +// ==================== Chars ==================== +IntegralConvertResult FormatConvertImpl(char v, const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(signed char v, + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(unsigned char v, + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} + +// ==================== Ints ==================== +IntegralConvertResult FormatConvertImpl(short v, // NOLINT + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(unsigned short v, // NOLINT + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(int v, const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(unsigned v, const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(long v, // NOLINT + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(unsigned long v, // NOLINT + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(long long v, // NOLINT + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(unsigned long long v, // NOLINT + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} +IntegralConvertResult FormatConvertImpl(absl::uint128 v, + const ConversionSpec conv, + FormatSinkImpl *sink) { + return {ConvertIntArg(v, conv, sink)}; +} + +ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_(); + + +} // namespace str_format_internal + +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/arg.h b/absl/strings/internal/str_format/arg.h new file mode 100644 index 00000000..0af4c839 --- /dev/null +++ b/absl/strings/internal/str_format/arg.h @@ -0,0 +1,422 @@ +#ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_ARG_H_ +#define ABSL_STRINGS_INTERNAL_STR_FORMAT_ARG_H_ + +#include <string.h> +#include <wchar.h> + +#include <cstdio> +#include <iomanip> +#include <limits> +#include <sstream> +#include <string> +#include <type_traits> + +#include "absl/base/port.h" +#include "absl/meta/type_traits.h" +#include "absl/numeric/int128.h" +#include "absl/strings/internal/str_format/extension.h" +#include "absl/strings/string_view.h" + +class Cord; +class CordReader; + +namespace absl { +inline namespace lts_2018_12_18 { + +class FormatCountCapture; +class FormatSink; + +namespace str_format_internal { + +template <typename T, typename = void> +struct HasUserDefinedConvert : std::false_type {}; + +template <typename T> +struct HasUserDefinedConvert< + T, void_t<decltype(AbslFormatConvert( + std::declval<const T&>(), std::declval<ConversionSpec>(), + std::declval<FormatSink*>()))>> : std::true_type {}; +template <typename T> +class StreamedWrapper; + +// If 'v' can be converted (in the printf sense) according to 'conv', +// then convert it, appending to `sink` and return `true`. +// Otherwise fail and return `false`. +// Raw pointers. +struct VoidPtr { + VoidPtr() = default; + template <typename T, + decltype(reinterpret_cast<uintptr_t>(std::declval<T*>())) = 0> + VoidPtr(T* ptr) // NOLINT + : value(ptr ? reinterpret_cast<uintptr_t>(ptr) : 0) {} + uintptr_t value; +}; +ConvertResult<Conv::p> FormatConvertImpl(VoidPtr v, ConversionSpec conv, + FormatSinkImpl* sink); + +// Strings. +ConvertResult<Conv::s> FormatConvertImpl(const std::string& v, ConversionSpec conv, + FormatSinkImpl* sink); +ConvertResult<Conv::s> FormatConvertImpl(string_view v, ConversionSpec conv, + FormatSinkImpl* sink); +ConvertResult<Conv::s | Conv::p> FormatConvertImpl(const char* v, + ConversionSpec conv, + FormatSinkImpl* sink); +template <class AbslCord, + typename std::enable_if< + std::is_same<AbslCord, ::Cord>::value>::type* = nullptr, + class AbslCordReader = ::CordReader> +ConvertResult<Conv::s> FormatConvertImpl(const AbslCord& value, + ConversionSpec conv, + FormatSinkImpl* sink) { + if (conv.conv().id() != ConversionChar::s) return {false}; + + bool is_left = conv.flags().left; + size_t space_remaining = 0; + + int width = conv.width(); + if (width >= 0) space_remaining = width; + + size_t to_write = value.size(); + + int precision = conv.precision(); + if (precision >= 0) + to_write = std::min(to_write, static_cast<size_t>(precision)); + + space_remaining = Excess(to_write, space_remaining); + + if (space_remaining > 0 && !is_left) sink->Append(space_remaining, ' '); + + string_view piece; + for (AbslCordReader reader(value); + to_write > 0 && reader.ReadFragment(&piece); to_write -= piece.size()) { + if (piece.size() > to_write) piece.remove_suffix(piece.size() - to_write); + sink->Append(piece); + } + + if (space_remaining > 0 && is_left) sink->Append(space_remaining, ' '); + return {true}; +} + +using IntegralConvertResult = + ConvertResult<Conv::c | Conv::numeric | Conv::star>; +using FloatingConvertResult = ConvertResult<Conv::floating>; + +// Floats. +FloatingConvertResult FormatConvertImpl(float v, ConversionSpec conv, + FormatSinkImpl* sink); +FloatingConvertResult FormatConvertImpl(double v, ConversionSpec conv, + FormatSinkImpl* sink); +FloatingConvertResult FormatConvertImpl(long double v, ConversionSpec conv, + FormatSinkImpl* sink); + +// Chars. +IntegralConvertResult FormatConvertImpl(char v, ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(signed char v, ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(unsigned char v, ConversionSpec conv, + FormatSinkImpl* sink); + +// Ints. +IntegralConvertResult FormatConvertImpl(short v, // NOLINT + ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(unsigned short v, // NOLINT + ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(int v, ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(unsigned v, ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(long v, // NOLINT + ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(unsigned long v, // NOLINT + ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(long long v, // NOLINT + ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(unsigned long long v, // NOLINT + ConversionSpec conv, + FormatSinkImpl* sink); +IntegralConvertResult FormatConvertImpl(uint128 v, ConversionSpec conv, + FormatSinkImpl* sink); +template <typename T, enable_if_t<std::is_same<T, bool>::value, int> = 0> +IntegralConvertResult FormatConvertImpl(T v, ConversionSpec conv, + FormatSinkImpl* sink) { + return FormatConvertImpl(static_cast<int>(v), conv, sink); +} + +// We provide this function to help the checker, but it is never defined. +// FormatArgImpl will use the underlying Convert functions instead. +template <typename T> +typename std::enable_if<std::is_enum<T>::value && + !HasUserDefinedConvert<T>::value, + IntegralConvertResult>::type +FormatConvertImpl(T v, ConversionSpec conv, FormatSinkImpl* sink); + +template <typename T> +ConvertResult<Conv::s> FormatConvertImpl(const StreamedWrapper<T>& v, + ConversionSpec conv, + FormatSinkImpl* out) { + std::ostringstream oss; + oss << v.v_; + if (!oss) return {false}; + return str_format_internal::FormatConvertImpl(oss.str(), conv, out); +} + +// Use templates and dependent types to delay evaluation of the function +// until after FormatCountCapture is fully defined. +struct FormatCountCaptureHelper { + template <class T = int> + static ConvertResult<Conv::n> ConvertHelper(const FormatCountCapture& v, + ConversionSpec conv, + FormatSinkImpl* sink) { + const absl::enable_if_t<sizeof(T) != 0, FormatCountCapture>& v2 = v; + + if (conv.conv().id() != str_format_internal::ConversionChar::n) + return {false}; + *v2.p_ = static_cast<int>(sink->size()); + return {true}; + } +}; + +template <class T = int> +ConvertResult<Conv::n> FormatConvertImpl(const FormatCountCapture& v, + ConversionSpec conv, + FormatSinkImpl* sink) { + return FormatCountCaptureHelper::ConvertHelper(v, conv, sink); +} + +// Helper friend struct to hide implementation details from the public API of +// FormatArgImpl. +struct FormatArgImplFriend { + template <typename Arg> + static bool ToInt(Arg arg, int* out) { + // A value initialized ConversionSpec has a `none` conv, which tells the + // dispatcher to run the `int` conversion. + return arg.dispatcher_(arg.data_, {}, out); + } + + template <typename Arg> + static bool Convert(Arg arg, str_format_internal::ConversionSpec conv, + FormatSinkImpl* out) { + return arg.dispatcher_(arg.data_, conv, out); + } + + template <typename Arg> + static typename Arg::Dispatcher GetVTablePtrForTest(Arg arg) { + return arg.dispatcher_; + } +}; + +// A type-erased handle to a format argument. +class FormatArgImpl { + private: + enum { kInlinedSpace = 8 }; + + using VoidPtr = str_format_internal::VoidPtr; + + union Data { + const void* ptr; + const volatile void* volatile_ptr; + char buf[kInlinedSpace]; + }; + + using Dispatcher = bool (*)(Data, ConversionSpec, void* out); + + template <typename T> + struct store_by_value + : std::integral_constant<bool, (sizeof(T) <= kInlinedSpace) && + (std::is_integral<T>::value || + std::is_floating_point<T>::value || + std::is_pointer<T>::value || + std::is_same<VoidPtr, T>::value)> {}; + + enum StoragePolicy { ByPointer, ByVolatilePointer, ByValue }; + template <typename T> + struct storage_policy + : std::integral_constant<StoragePolicy, + (std::is_volatile<T>::value + ? ByVolatilePointer + : (store_by_value<T>::value ? ByValue + : ByPointer))> { + }; + + // To reduce the number of vtables we will decay values before hand. + // Anything with a user-defined Convert will get its own vtable. + // For everything else: + // - Decay char* and char arrays into `const char*` + // - Decay any other pointer to `const void*` + // - Decay all enums to their underlying type. + // - Decay function pointers to void*. + template <typename T, typename = void> + struct DecayType { + static constexpr bool kHasUserDefined = + str_format_internal::HasUserDefinedConvert<T>::value; + using type = typename std::conditional< + !kHasUserDefined && std::is_convertible<T, const char*>::value, + const char*, + typename std::conditional<!kHasUserDefined && + std::is_convertible<T, VoidPtr>::value, + VoidPtr, const T&>::type>::type; + }; + template <typename T> + struct DecayType<T, + typename std::enable_if< + !str_format_internal::HasUserDefinedConvert<T>::value && + std::is_enum<T>::value>::type> { + using type = typename std::underlying_type<T>::type; + }; + + public: + template <typename T> + explicit FormatArgImpl(const T& value) { + using D = typename DecayType<T>::type; + static_assert( + std::is_same<D, const T&>::value || storage_policy<D>::value == ByValue, + "Decayed types must be stored by value"); + Init(static_cast<D>(value)); + } + + private: + friend struct str_format_internal::FormatArgImplFriend; + template <typename T, StoragePolicy = storage_policy<T>::value> + struct Manager; + + template <typename T> + struct Manager<T, ByPointer> { + static Data SetValue(const T& value) { + Data data; + data.ptr = &value; + return data; + } + + static const T& Value(Data arg) { return *static_cast<const T*>(arg.ptr); } + }; + + template <typename T> + struct Manager<T, ByVolatilePointer> { + static Data SetValue(const T& value) { + Data data; + data.volatile_ptr = &value; + return data; + } + + static const T& Value(Data arg) { + return *static_cast<const T*>(arg.volatile_ptr); + } + }; + + template <typename T> + struct Manager<T, ByValue> { + static Data SetValue(const T& value) { + Data data; + memcpy(data.buf, &value, sizeof(value)); + return data; + } + + static T Value(Data arg) { + T value; + memcpy(&value, arg.buf, sizeof(T)); + return value; + } + }; + + template <typename T> + void Init(const T& value) { + data_ = Manager<T>::SetValue(value); + dispatcher_ = &Dispatch<T>; + } + + template <typename T> + static int ToIntVal(const T& val) { + using CommonType = typename std::conditional<std::is_signed<T>::value, + int64_t, uint64_t>::type; + if (static_cast<CommonType>(val) > + static_cast<CommonType>((std::numeric_limits<int>::max)())) { + return (std::numeric_limits<int>::max)(); + } else if (std::is_signed<T>::value && + static_cast<CommonType>(val) < + static_cast<CommonType>((std::numeric_limits<int>::min)())) { + return (std::numeric_limits<int>::min)(); + } + return static_cast<int>(val); + } + + template <typename T> + static bool ToInt(Data arg, int* out, std::true_type /* is_integral */, + std::false_type) { + *out = ToIntVal(Manager<T>::Value(arg)); + return true; + } + + template <typename T> + static bool ToInt(Data arg, int* out, std::false_type, + std::true_type /* is_enum */) { + *out = ToIntVal(static_cast<typename std::underlying_type<T>::type>( + Manager<T>::Value(arg))); + return true; + } + + template <typename T> + static bool ToInt(Data, int*, std::false_type, std::false_type) { + return false; + } + + template <typename T> + static bool Dispatch(Data arg, ConversionSpec spec, void* out) { + // A `none` conv indicates that we want the `int` conversion. + if (ABSL_PREDICT_FALSE(spec.conv().id() == ConversionChar::none)) { + return ToInt<T>(arg, static_cast<int*>(out), std::is_integral<T>(), + std::is_enum<T>()); + } + + return str_format_internal::FormatConvertImpl( + Manager<T>::Value(arg), spec, static_cast<FormatSinkImpl*>(out)) + .value; + } + + Data data_; + Dispatcher dispatcher_; +}; + +#define ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(T, E) \ + E template bool FormatArgImpl::Dispatch<T>(Data, ConversionSpec, void*) + +#define ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_(...) \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(str_format_internal::VoidPtr, \ + __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(bool, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(char, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(signed char, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(unsigned char, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(short, __VA_ARGS__); /* NOLINT */ \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(unsigned short, /* NOLINT */ \ + __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(int, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(unsigned int, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(long, __VA_ARGS__); /* NOLINT */ \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(unsigned long, /* NOLINT */ \ + __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(long long, /* NOLINT */ \ + __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(unsigned long long, /* NOLINT */ \ + __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(uint128, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(float, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(double, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(long double, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(const char*, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(std::string, __VA_ARGS__); \ + ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(string_view, __VA_ARGS__) + +ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_(extern); + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_STR_FORMAT_ARG_H_ diff --git a/absl/strings/internal/str_format/arg_test.cc b/absl/strings/internal/str_format/arg_test.cc new file mode 100644 index 00000000..9cb9559c --- /dev/null +++ b/absl/strings/internal/str_format/arg_test.cc @@ -0,0 +1,113 @@ +// Copyright 2017 The Abseil 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 +// +#include "absl/strings/internal/str_format/arg.h" + +#include <ostream> +#include <string> +#include "gtest/gtest.h" +#include "absl/strings/str_format.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { +namespace { + +class FormatArgImplTest : public ::testing::Test { + public: + enum Color { kRed, kGreen, kBlue }; + + static const char *hi() { return "hi"; } +}; + +TEST_F(FormatArgImplTest, ToInt) { + int out = 0; + EXPECT_TRUE(FormatArgImplFriend::ToInt(FormatArgImpl(1), &out)); + EXPECT_EQ(1, out); + EXPECT_TRUE(FormatArgImplFriend::ToInt(FormatArgImpl(-1), &out)); + EXPECT_EQ(-1, out); + EXPECT_TRUE( + FormatArgImplFriend::ToInt(FormatArgImpl(static_cast<char>(64)), &out)); + EXPECT_EQ(64, out); + EXPECT_TRUE(FormatArgImplFriend::ToInt( + FormatArgImpl(static_cast<unsigned long long>(123456)), &out)); // NOLINT + EXPECT_EQ(123456, out); + EXPECT_TRUE(FormatArgImplFriend::ToInt( + FormatArgImpl(static_cast<unsigned long long>( // NOLINT + std::numeric_limits<int>::max()) + + 1), + &out)); + EXPECT_EQ(std::numeric_limits<int>::max(), out); + EXPECT_TRUE(FormatArgImplFriend::ToInt( + FormatArgImpl(static_cast<long long>( // NOLINT + std::numeric_limits<int>::min()) - + 10), + &out)); + EXPECT_EQ(std::numeric_limits<int>::min(), out); + EXPECT_TRUE(FormatArgImplFriend::ToInt(FormatArgImpl(false), &out)); + EXPECT_EQ(0, out); + EXPECT_TRUE(FormatArgImplFriend::ToInt(FormatArgImpl(true), &out)); + EXPECT_EQ(1, out); + EXPECT_FALSE(FormatArgImplFriend::ToInt(FormatArgImpl(2.2), &out)); + EXPECT_FALSE(FormatArgImplFriend::ToInt(FormatArgImpl(3.2f), &out)); + EXPECT_FALSE(FormatArgImplFriend::ToInt( + FormatArgImpl(static_cast<int *>(nullptr)), &out)); + EXPECT_FALSE(FormatArgImplFriend::ToInt(FormatArgImpl(hi()), &out)); + EXPECT_FALSE(FormatArgImplFriend::ToInt(FormatArgImpl("hi"), &out)); + EXPECT_TRUE(FormatArgImplFriend::ToInt(FormatArgImpl(kBlue), &out)); + EXPECT_EQ(2, out); +} + +extern const char kMyArray[]; + +TEST_F(FormatArgImplTest, CharArraysDecayToCharPtr) { + const char* a = ""; + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(a)), + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(""))); + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(a)), + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl("A"))); + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(a)), + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl("ABC"))); + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(a)), + FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(kMyArray))); +} + +TEST_F(FormatArgImplTest, OtherPtrDecayToVoidPtr) { + auto expected = FormatArgImplFriend::GetVTablePtrForTest( + FormatArgImpl(static_cast<void *>(nullptr))); + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest( + FormatArgImpl(static_cast<int *>(nullptr))), + expected); + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest( + FormatArgImpl(static_cast<volatile int *>(nullptr))), + expected); + + auto p = static_cast<void (*)()>([] {}); + EXPECT_EQ(FormatArgImplFriend::GetVTablePtrForTest(FormatArgImpl(p)), + expected); +} + +TEST_F(FormatArgImplTest, WorksWithCharArraysOfUnknownSize) { + std::string s; + FormatSinkImpl sink(&s); + ConversionSpec conv; + conv.set_conv(ConversionChar::FromChar('s')); + conv.set_flags(Flags()); + conv.set_width(-1); + conv.set_precision(-1); + EXPECT_TRUE( + FormatArgImplFriend::Convert(FormatArgImpl(kMyArray), conv, &sink)); + sink.Flush(); + EXPECT_EQ("ABCDE", s); +} +const char kMyArray[] = "ABCDE"; + +} // namespace +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/bind.cc b/absl/strings/internal/str_format/bind.cc new file mode 100644 index 00000000..5cf026b6 --- /dev/null +++ b/absl/strings/internal/str_format/bind.cc @@ -0,0 +1,231 @@ +#include "absl/strings/internal/str_format/bind.h" + +#include <cerrno> +#include <limits> +#include <sstream> +#include <string> + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { + +namespace { + +inline bool BindFromPosition(int position, int* value, + absl::Span<const FormatArgImpl> pack) { + assert(position > 0); + if (static_cast<size_t>(position) > pack.size()) { + return false; + } + // -1 because positions are 1-based + return FormatArgImplFriend::ToInt(pack[position - 1], value); +} + +class ArgContext { + public: + explicit ArgContext(absl::Span<const FormatArgImpl> pack) : pack_(pack) {} + + // Fill 'bound' with the results of applying the context's argument pack + // to the specified 'props'. We synthesize a BoundConversion by + // lining up a UnboundConversion with a user argument. We also + // resolve any '*' specifiers for width and precision, so after + // this call, 'bound' has all the information it needs to be formatted. + // Returns false on failure. + bool Bind(const UnboundConversion *props, BoundConversion *bound); + + private: + absl::Span<const FormatArgImpl> pack_; +}; + +inline bool ArgContext::Bind(const UnboundConversion* unbound, + BoundConversion* bound) { + const FormatArgImpl* arg = nullptr; + int arg_position = unbound->arg_position; + if (static_cast<size_t>(arg_position - 1) >= pack_.size()) return false; + arg = &pack_[arg_position - 1]; // 1-based + + if (!unbound->flags.basic) { + int width = unbound->width.value(); + bool force_left = false; + if (unbound->width.is_from_arg()) { + if (!BindFromPosition(unbound->width.get_from_arg(), &width, pack_)) + return false; + if (width < 0) { + // "A negative field width is taken as a '-' flag followed by a + // positive field width." + force_left = true; + width = -width; + } + } + + int precision = unbound->precision.value(); + if (unbound->precision.is_from_arg()) { + if (!BindFromPosition(unbound->precision.get_from_arg(), &precision, + pack_)) + return false; + } + + bound->set_width(width); + bound->set_precision(precision); + bound->set_flags(unbound->flags); + if (force_left) + bound->set_left(true); + } else { + bound->set_flags(unbound->flags); + bound->set_width(-1); + bound->set_precision(-1); + } + + bound->set_length_mod(unbound->length_mod); + bound->set_conv(unbound->conv); + bound->set_arg(arg); + return true; +} + +template <typename Converter> +class ConverterConsumer { + public: + ConverterConsumer(Converter converter, absl::Span<const FormatArgImpl> pack) + : converter_(converter), arg_context_(pack) {} + + bool Append(string_view s) { + converter_.Append(s); + return true; + } + bool ConvertOne(const UnboundConversion& conv, string_view conv_string) { + BoundConversion bound; + if (!arg_context_.Bind(&conv, &bound)) return false; + return converter_.ConvertOne(bound, conv_string); + } + + private: + Converter converter_; + ArgContext arg_context_; +}; + +template <typename Converter> +bool ConvertAll(const UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args, Converter converter) { + if (format.has_parsed_conversion()) { + return format.parsed_conversion()->ProcessFormat( + ConverterConsumer<Converter>(converter, args)); + } else { + return ParseFormatString(format.str(), + ConverterConsumer<Converter>(converter, args)); + } +} + +class DefaultConverter { + public: + explicit DefaultConverter(FormatSinkImpl* sink) : sink_(sink) {} + + void Append(string_view s) const { sink_->Append(s); } + + bool ConvertOne(const BoundConversion& bound, string_view /*conv*/) const { + return FormatArgImplFriend::Convert(*bound.arg(), bound, sink_); + } + + private: + FormatSinkImpl* sink_; +}; + +class SummarizingConverter { + public: + explicit SummarizingConverter(FormatSinkImpl* sink) : sink_(sink) {} + + void Append(string_view s) const { sink_->Append(s); } + + bool ConvertOne(const BoundConversion& bound, string_view /*conv*/) const { + UntypedFormatSpecImpl spec("%d"); + + std::ostringstream ss; + ss << "{" << Streamable(spec, {*bound.arg()}) << ":" << bound.flags(); + if (bound.width() >= 0) ss << bound.width(); + if (bound.precision() >= 0) ss << "." << bound.precision(); + ss << bound.length_mod() << bound.conv() << "}"; + Append(ss.str()); + return true; + } + + private: + FormatSinkImpl* sink_; +}; + +} // namespace + +bool BindWithPack(const UnboundConversion* props, + absl::Span<const FormatArgImpl> pack, + BoundConversion* bound) { + return ArgContext(pack).Bind(props, bound); +} + +std::string Summarize(const UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args) { + typedef SummarizingConverter Converter; + std::string out; + { + // inner block to destroy sink before returning out. It ensures a last + // flush. + FormatSinkImpl sink(&out); + if (!ConvertAll(format, args, Converter(&sink))) { + return ""; + } + } + return out; +} + +bool FormatUntyped(FormatRawSinkImpl raw_sink, + const UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args) { + FormatSinkImpl sink(raw_sink); + using Converter = DefaultConverter; + return ConvertAll(format, args, Converter(&sink)); +} + +std::ostream& Streamable::Print(std::ostream& os) const { + if (!FormatUntyped(&os, format_, args_)) os.setstate(std::ios::failbit); + return os; +} + +std::string& AppendPack(std::string* out, const UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args) { + size_t orig = out->size(); + if (ABSL_PREDICT_FALSE(!FormatUntyped(out, format, args))) { + out->erase(orig); + } + return *out; +} + +int FprintF(std::FILE* output, const UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args) { + FILERawSink sink(output); + if (!FormatUntyped(&sink, format, args)) { + errno = EINVAL; + return -1; + } + if (sink.error()) { + errno = sink.error(); + return -1; + } + if (sink.count() > std::numeric_limits<int>::max()) { + errno = EFBIG; + return -1; + } + return static_cast<int>(sink.count()); +} + +int SnprintF(char* output, size_t size, const UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args) { + BufferRawSink sink(output, size ? size - 1 : 0); + if (!FormatUntyped(&sink, format, args)) { + errno = EINVAL; + return -1; + } + size_t total = sink.total_written(); + if (size) output[std::min(total, size - 1)] = 0; + return static_cast<int>(total); +} + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/bind.h b/absl/strings/internal/str_format/bind.h new file mode 100644 index 00000000..df5562f6 --- /dev/null +++ b/absl/strings/internal/str_format/bind.h @@ -0,0 +1,199 @@ +#ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_BIND_H_ +#define ABSL_STRINGS_INTERNAL_STR_FORMAT_BIND_H_ + +#include <array> +#include <cstdio> +#include <sstream> +#include <string> + +#include "absl/base/port.h" +#include "absl/container/inlined_vector.h" +#include "absl/strings/internal/str_format/arg.h" +#include "absl/strings/internal/str_format/checker.h" +#include "absl/strings/internal/str_format/parser.h" +#include "absl/types/span.h" + +namespace absl { +inline namespace lts_2018_12_18 { + +class UntypedFormatSpec; + +namespace str_format_internal { + +class BoundConversion : public ConversionSpec { + public: + const FormatArgImpl* arg() const { return arg_; } + void set_arg(const FormatArgImpl* a) { arg_ = a; } + + private: + const FormatArgImpl* arg_; +}; + +// This is the type-erased class that the implementation uses. +class UntypedFormatSpecImpl { + public: + UntypedFormatSpecImpl() = delete; + + explicit UntypedFormatSpecImpl(string_view s) + : data_(s.data()), size_(s.size()) {} + explicit UntypedFormatSpecImpl( + const str_format_internal::ParsedFormatBase* pc) + : data_(pc), size_(~size_t{}) {} + + bool has_parsed_conversion() const { return size_ == ~size_t{}; } + + string_view str() const { + assert(!has_parsed_conversion()); + return string_view(static_cast<const char*>(data_), size_); + } + const str_format_internal::ParsedFormatBase* parsed_conversion() const { + assert(has_parsed_conversion()); + return static_cast<const str_format_internal::ParsedFormatBase*>(data_); + } + + template <typename T> + static const UntypedFormatSpecImpl& Extract(const T& s) { + return s.spec_; + } + + private: + const void* data_; + size_t size_; +}; + +template <typename T, typename...> +struct MakeDependent { + using type = T; +}; + +// Implicitly convertible from `const char*`, `string_view`, and the +// `ExtendedParsedFormat` type. This abstraction allows all format functions to +// operate on any without providing too many overloads. +template <typename... Args> +class FormatSpecTemplate + : public MakeDependent<UntypedFormatSpec, Args...>::type { + using Base = typename MakeDependent<UntypedFormatSpec, Args...>::type; + + public: +#if ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + + // Honeypot overload for when the std::string is not constexpr. + // We use the 'unavailable' attribute to give a better compiler error than + // just 'method is deleted'. + FormatSpecTemplate(...) // NOLINT + __attribute__((unavailable("Format std::string is not constexpr."))); + + // Honeypot overload for when the format is constexpr and invalid. + // We use the 'unavailable' attribute to give a better compiler error than + // just 'method is deleted'. + // To avoid checking the format twice, we just check that the format is + // constexpr. If is it valid, then the overload below will kick in. + // We add the template here to make this overload have lower priority. + template <typename = void> + FormatSpecTemplate(const char* s) // NOLINT + __attribute__(( + enable_if(str_format_internal::EnsureConstexpr(s), "constexpr trap"), + unavailable( + "Format specified does not match the arguments passed."))); + + template <typename T = void> + FormatSpecTemplate(string_view s) // NOLINT + __attribute__((enable_if(str_format_internal::EnsureConstexpr(s), + "constexpr trap"))) { + static_assert(sizeof(T*) == 0, + "Format specified does not match the arguments passed."); + } + + // Good format overload. + FormatSpecTemplate(const char* s) // NOLINT + __attribute__((enable_if(ValidFormatImpl<ArgumentToConv<Args>()...>(s), + "bad format trap"))) + : Base(s) {} + + FormatSpecTemplate(string_view s) // NOLINT + __attribute__((enable_if(ValidFormatImpl<ArgumentToConv<Args>()...>(s), + "bad format trap"))) + : Base(s) {} + +#else // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + + FormatSpecTemplate(const char* s) : Base(s) {} // NOLINT + FormatSpecTemplate(string_view s) : Base(s) {} // NOLINT + +#endif // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + + template <Conv... C, typename = typename std::enable_if< + sizeof...(C) == sizeof...(Args) && + AllOf(Contains(ArgumentToConv<Args>(), + C)...)>::type> + FormatSpecTemplate(const ExtendedParsedFormat<C...>& pc) // NOLINT + : Base(&pc) {} +}; + +template <typename... Args> +struct FormatSpecDeductionBarrier { + using type = FormatSpecTemplate<Args...>; +}; + +class Streamable { + public: + Streamable(const UntypedFormatSpecImpl& format, + absl::Span<const FormatArgImpl> args) + : format_(format), args_(args.begin(), args.end()) {} + + std::ostream& Print(std::ostream& os) const; + + friend std::ostream& operator<<(std::ostream& os, const Streamable& l) { + return l.Print(os); + } + + private: + const UntypedFormatSpecImpl& format_; + absl::InlinedVector<FormatArgImpl, 4> args_; +}; + +// for testing +std::string Summarize(UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args); +bool BindWithPack(const UnboundConversion* props, + absl::Span<const FormatArgImpl> pack, BoundConversion* bound); + +bool FormatUntyped(FormatRawSinkImpl raw_sink, + UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args); + +std::string& AppendPack(std::string* out, UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args); + +inline std::string FormatPack(const UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args) { + std::string out; + AppendPack(&out, format, args); + return out; +} + +int FprintF(std::FILE* output, UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args); +int SnprintF(char* output, size_t size, UntypedFormatSpecImpl format, + absl::Span<const FormatArgImpl> args); + +// Returned by Streamed(v). Converts via '%s' to the string created +// by std::ostream << v. +template <typename T> +class StreamedWrapper { + public: + explicit StreamedWrapper(const T& v) : v_(v) { } + + private: + template <typename S> + friend ConvertResult<Conv::s> FormatConvertImpl(const StreamedWrapper<S>& v, + ConversionSpec conv, + FormatSinkImpl* out); + const T& v_; +}; + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_STR_FORMAT_BIND_H_ diff --git a/absl/strings/internal/str_format/bind_test.cc b/absl/strings/internal/str_format/bind_test.cc new file mode 100644 index 00000000..58d9e072 --- /dev/null +++ b/absl/strings/internal/str_format/bind_test.cc @@ -0,0 +1,133 @@ +#include "absl/strings/internal/str_format/bind.h" + +#include <string.h> + +#include "gtest/gtest.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { +namespace { + +template <typename T, size_t N> +size_t ArraySize(T (&)[N]) { + return N; +} + +class FormatBindTest : public ::testing::Test { + public: + bool Extract(const char *s, UnboundConversion *props, int *next) const { + absl::string_view src = s; + return ConsumeUnboundConversion(&src, props, next) && src.empty(); + } +}; + +TEST_F(FormatBindTest, BindSingle) { + struct Expectation { + int line; + const char *fmt; + int ok_phases; + const FormatArgImpl *arg; + int width; + int precision; + int next_arg; + }; + const int no = -1; + const int ia[] = { 10, 20, 30, 40}; + const FormatArgImpl args[] = {FormatArgImpl(ia[0]), FormatArgImpl(ia[1]), + FormatArgImpl(ia[2]), FormatArgImpl(ia[3])}; +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wmissing-field-initializers" + const Expectation kExpect[] = { + {__LINE__, "d", 2, &args[0], no, no, 2}, + {__LINE__, "4d", 2, &args[0], 4, no, 2}, + {__LINE__, ".5d", 2, &args[0], no, 5, 2}, + {__LINE__, "4.5d", 2, &args[0], 4, 5, 2}, + {__LINE__, "*d", 2, &args[1], 10, no, 3}, + {__LINE__, ".*d", 2, &args[1], no, 10, 3}, + {__LINE__, "*.*d", 2, &args[2], 10, 20, 4}, + {__LINE__, "1$d", 2, &args[0], no, no, 0}, + {__LINE__, "2$d", 2, &args[1], no, no, 0}, + {__LINE__, "3$d", 2, &args[2], no, no, 0}, + {__LINE__, "4$d", 2, &args[3], no, no, 0}, + {__LINE__, "2$*1$d", 2, &args[1], 10, no, 0}, + {__LINE__, "2$*2$d", 2, &args[1], 20, no, 0}, + {__LINE__, "2$*3$d", 2, &args[1], 30, no, 0}, + {__LINE__, "2$.*1$d", 2, &args[1], no, 10, 0}, + {__LINE__, "2$.*2$d", 2, &args[1], no, 20, 0}, + {__LINE__, "2$.*3$d", 2, &args[1], no, 30, 0}, + {__LINE__, "2$*3$.*1$d", 2, &args[1], 30, 10, 0}, + {__LINE__, "2$*2$.*2$d", 2, &args[1], 20, 20, 0}, + {__LINE__, "2$*1$.*3$d", 2, &args[1], 10, 30, 0}, + {__LINE__, "2$*3$.*1$d", 2, &args[1], 30, 10, 0}, + {__LINE__, "1$*d", 0}, // indexed, then positional + {__LINE__, "*2$d", 0}, // positional, then indexed + {__LINE__, "6$d", 1}, // arg position out of bounds + {__LINE__, "1$6$d", 0}, // width position incorrectly specified + {__LINE__, "1$.6$d", 0}, // precision position incorrectly specified + {__LINE__, "1$*6$d", 1}, // width position out of bounds + {__LINE__, "1$.*6$d", 1}, // precision position out of bounds + }; +#pragma GCC diagnostic pop + for (const Expectation &e : kExpect) { + SCOPED_TRACE(e.line); + SCOPED_TRACE(e.fmt); + UnboundConversion props; + BoundConversion bound; + int ok_phases = 0; + int next = 0; + if (Extract(e.fmt, &props, &next)) { + ++ok_phases; + if (BindWithPack(&props, args, &bound)) { + ++ok_phases; + } + } + EXPECT_EQ(e.ok_phases, ok_phases); + if (e.ok_phases < 2) continue; + if (e.arg != nullptr) { + EXPECT_EQ(e.arg, bound.arg()); + } + EXPECT_EQ(e.width, bound.width()); + EXPECT_EQ(e.precision, bound.precision()); + } +} + +TEST_F(FormatBindTest, FormatPack) { + struct Expectation { + int line; + const char *fmt; + const char *summary; + }; + const int ia[] = { 10, 20, 30, 40, -10 }; + const FormatArgImpl args[] = {FormatArgImpl(ia[0]), FormatArgImpl(ia[1]), + FormatArgImpl(ia[2]), FormatArgImpl(ia[3]), + FormatArgImpl(ia[4])}; + const Expectation kExpect[] = { + {__LINE__, "a%4db%dc", "a{10:4d}b{20:d}c"}, + {__LINE__, "a%.4db%dc", "a{10:.4d}b{20:d}c"}, + {__LINE__, "a%4.5db%dc", "a{10:4.5d}b{20:d}c"}, + {__LINE__, "a%db%4.5dc", "a{10:d}b{20:4.5d}c"}, + {__LINE__, "a%db%*.*dc", "a{10:d}b{40:20.30d}c"}, + {__LINE__, "a%.*fb", "a{20:.10f}b"}, + {__LINE__, "a%1$db%2$*3$.*4$dc", "a{10:d}b{20:30.40d}c"}, + {__LINE__, "a%4$db%3$*2$.*1$dc", "a{40:d}b{30:20.10d}c"}, + {__LINE__, "a%04ldb", "a{10:04ld}b"}, + {__LINE__, "a%-#04lldb", "a{10:-#04lld}b"}, + {__LINE__, "a%1$*5$db", "a{10:-10d}b"}, + {__LINE__, "a%1$.*5$db", "a{10:d}b"}, + }; + for (const Expectation &e : kExpect) { + absl::string_view fmt = e.fmt; + SCOPED_TRACE(e.line); + SCOPED_TRACE(e.fmt); + UntypedFormatSpecImpl format(fmt); + EXPECT_EQ(e.summary, + str_format_internal::Summarize(format, absl::MakeSpan(args))) + << "line:" << e.line; + } +} + +} // namespace +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/checker.h b/absl/strings/internal/str_format/checker.h new file mode 100644 index 00000000..d0191968 --- /dev/null +++ b/absl/strings/internal/str_format/checker.h @@ -0,0 +1,327 @@ +#ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_CHECKER_H_ +#define ABSL_STRINGS_INTERNAL_STR_FORMAT_CHECKER_H_ + +#include "absl/strings/internal/str_format/arg.h" +#include "absl/strings/internal/str_format/extension.h" + +// Compile time check support for entry points. + +#ifndef ABSL_INTERNAL_ENABLE_FORMAT_CHECKER +#if defined(__clang__) && !defined(__native_client__) +#if __has_attribute(enable_if) +#define ABSL_INTERNAL_ENABLE_FORMAT_CHECKER 1 +#endif // __has_attribute(enable_if) +#endif // defined(__clang__) && !defined(__native_client__) +#endif // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { + +constexpr bool AllOf() { return true; } + +template <typename... T> +constexpr bool AllOf(bool b, T... t) { + return b && AllOf(t...); +} + +template <typename Arg> +constexpr Conv ArgumentToConv() { + return decltype(str_format_internal::FormatConvertImpl( + std::declval<const Arg&>(), std::declval<const ConversionSpec&>(), + std::declval<FormatSinkImpl*>()))::kConv; +} + +#if ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + +constexpr bool ContainsChar(const char* chars, char c) { + return *chars == c || (*chars && ContainsChar(chars + 1, c)); +} + +// A constexpr compatible list of Convs. +struct ConvList { + const Conv* array; + int count; + + // We do the bound check here to avoid having to do it on the callers. + // Returning an empty Conv has the same effect as short circuiting because it + // will never match any conversion. + constexpr Conv operator[](int i) const { + return i < count ? array[i] : Conv{}; + } + + constexpr ConvList without_front() const { + return count != 0 ? ConvList{array + 1, count - 1} : *this; + } +}; + +template <size_t count> +struct ConvListT { + // Make sure the array has size > 0. + Conv list[count ? count : 1]; +}; + +constexpr char GetChar(string_view str, size_t index) { + return index < str.size() ? str[index] : char{}; +} + +constexpr string_view ConsumeFront(string_view str, size_t len = 1) { + return len <= str.size() ? string_view(str.data() + len, str.size() - len) + : string_view(); +} + +constexpr string_view ConsumeAnyOf(string_view format, const char* chars) { + return ContainsChar(chars, GetChar(format, 0)) + ? ConsumeAnyOf(ConsumeFront(format), chars) + : format; +} + +constexpr bool IsDigit(char c) { return c >= '0' && c <= '9'; } + +// Helper class for the ParseDigits function. +// It encapsulates the two return values we need there. +struct Integer { + string_view format; + int value; + + // If the next character is a '$', consume it. + // Otherwise, make `this` an invalid positional argument. + constexpr Integer ConsumePositionalDollar() const { + return GetChar(format, 0) == '$' ? Integer{ConsumeFront(format), value} + : Integer{format, 0}; + } +}; + +constexpr Integer ParseDigits(string_view format, int value = 0) { + return IsDigit(GetChar(format, 0)) + ? ParseDigits(ConsumeFront(format), + 10 * value + GetChar(format, 0) - '0') + : Integer{format, value}; +} + +// Parse digits for a positional argument. +// The parsing also consumes the '$'. +constexpr Integer ParsePositional(string_view format) { + return ParseDigits(format).ConsumePositionalDollar(); +} + +// Parses a single conversion specifier. +// See ConvParser::Run() for post conditions. +class ConvParser { + constexpr ConvParser SetFormat(string_view format) const { + return ConvParser(format, args_, error_, arg_position_, is_positional_); + } + + constexpr ConvParser SetArgs(ConvList args) const { + return ConvParser(format_, args, error_, arg_position_, is_positional_); + } + + constexpr ConvParser SetError(bool error) const { + return ConvParser(format_, args_, error_ || error, arg_position_, + is_positional_); + } + + constexpr ConvParser SetArgPosition(int arg_position) const { + return ConvParser(format_, args_, error_, arg_position, is_positional_); + } + + // Consumes the next arg and verifies that it matches `conv`. + // `error_` is set if there is no next arg or if it doesn't match `conv`. + constexpr ConvParser ConsumeNextArg(char conv) const { + return SetArgs(args_.without_front()).SetError(!Contains(args_[0], conv)); + } + + // Verify that positional argument `i.value` matches `conv`. + // `error_` is set if `i.value` is not a valid argument or if it doesn't + // match. + constexpr ConvParser VerifyPositional(Integer i, char conv) const { + return SetFormat(i.format).SetError(!Contains(args_[i.value - 1], conv)); + } + + // Parse the position of the arg and store it in `arg_position_`. + constexpr ConvParser ParseArgPosition(Integer arg) const { + return SetFormat(arg.format).SetArgPosition(arg.value); + } + + // Consume the flags. + constexpr ConvParser ParseFlags() const { + return SetFormat(ConsumeAnyOf(format_, "-+ #0")); + } + + // Consume the width. + // If it is '*', we verify that it matches `args_`. `error_` is set if it + // doesn't match. + constexpr ConvParser ParseWidth() const { + return IsDigit(GetChar(format_, 0)) + ? SetFormat(ParseDigits(format_).format) + : GetChar(format_, 0) == '*' + ? is_positional_ + ? VerifyPositional( + ParsePositional(ConsumeFront(format_)), '*') + : SetFormat(ConsumeFront(format_)) + .ConsumeNextArg('*') + : *this; + } + + // Consume the precision. + // If it is '*', we verify that it matches `args_`. `error_` is set if it + // doesn't match. + constexpr ConvParser ParsePrecision() const { + return GetChar(format_, 0) != '.' + ? *this + : GetChar(format_, 1) == '*' + ? is_positional_ + ? VerifyPositional( + ParsePositional(ConsumeFront(format_, 2)), '*') + : SetFormat(ConsumeFront(format_, 2)) + .ConsumeNextArg('*') + : SetFormat(ParseDigits(ConsumeFront(format_)).format); + } + + // Consume the length characters. + constexpr ConvParser ParseLength() const { + return SetFormat(ConsumeAnyOf(format_, "lLhjztq")); + } + + // Consume the conversion character and verify that it matches `args_`. + // `error_` is set if it doesn't match. + constexpr ConvParser ParseConversion() const { + return is_positional_ + ? VerifyPositional({ConsumeFront(format_), arg_position_}, + GetChar(format_, 0)) + : ConsumeNextArg(GetChar(format_, 0)) + .SetFormat(ConsumeFront(format_)); + } + + constexpr ConvParser(string_view format, ConvList args, bool error, + int arg_position, bool is_positional) + : format_(format), + args_(args), + error_(error), + arg_position_(arg_position), + is_positional_(is_positional) {} + + public: + constexpr ConvParser(string_view format, ConvList args, bool is_positional) + : format_(format), + args_(args), + error_(false), + arg_position_(0), + is_positional_(is_positional) {} + + // Consume the whole conversion specifier. + // `format()` will be set to the character after the conversion character. + // `error()` will be set if any of the arguments do not match. + constexpr ConvParser Run() const { + return (is_positional_ ? ParseArgPosition(ParsePositional(format_)) : *this) + .ParseFlags() + .ParseWidth() + .ParsePrecision() + .ParseLength() + .ParseConversion(); + } + + constexpr string_view format() const { return format_; } + constexpr ConvList args() const { return args_; } + constexpr bool error() const { return error_; } + constexpr bool is_positional() const { return is_positional_; } + + private: + string_view format_; + // Current list of arguments. If we are not in positional mode we will consume + // from the front. + ConvList args_; + bool error_; + // Holds the argument position of the conversion character, if we are in + // positional mode. Otherwise, it is unspecified. + int arg_position_; + // Whether we are in positional mode. + // It changes the behavior of '*' and where to find the converted argument. + bool is_positional_; +}; + +// Parses a whole format expression. +// See FormatParser::Run(). +class FormatParser { + static constexpr bool FoundPercent(string_view format) { + return format.empty() || + (GetChar(format, 0) == '%' && GetChar(format, 1) != '%'); + } + + // We use an inner function to increase the recursion limit. + // The inner function consumes up to `limit` characters on every run. + // This increases the limit from 512 to ~512*limit. + static constexpr string_view ConsumeNonPercentInner(string_view format, + int limit = 20) { + return FoundPercent(format) || !limit + ? format + : ConsumeNonPercentInner( + ConsumeFront(format, GetChar(format, 0) == '%' && + GetChar(format, 1) == '%' + ? 2 + : 1), + limit - 1); + } + + // Consume characters until the next conversion spec %. + // It skips %%. + static constexpr string_view ConsumeNonPercent(string_view format) { + return FoundPercent(format) + ? format + : ConsumeNonPercent(ConsumeNonPercentInner(format)); + } + + static constexpr bool IsPositional(string_view format) { + return IsDigit(GetChar(format, 0)) ? IsPositional(ConsumeFront(format)) + : GetChar(format, 0) == '$'; + } + + constexpr bool RunImpl(bool is_positional) const { + // In non-positional mode we require all arguments to be consumed. + // In positional mode just reaching the end of the format without errors is + // enough. + return (format_.empty() && (is_positional || args_.count == 0)) || + (!format_.empty() && + ValidateArg( + ConvParser(ConsumeFront(format_), args_, is_positional).Run())); + } + + constexpr bool ValidateArg(ConvParser conv) const { + return !conv.error() && FormatParser(conv.format(), conv.args()) + .RunImpl(conv.is_positional()); + } + + public: + constexpr FormatParser(string_view format, ConvList args) + : format_(ConsumeNonPercent(format)), args_(args) {} + + // Runs the parser for `format` and `args`. + // It verifies that the format is valid and that all conversion specifiers + // match the arguments passed. + // In non-positional mode it also verfies that all arguments are consumed. + constexpr bool Run() const { + return RunImpl(!format_.empty() && IsPositional(ConsumeFront(format_))); + } + + private: + string_view format_; + // Current list of arguments. + // If we are not in positional mode we will consume from the front and will + // have to be empty in the end. + ConvList args_; +}; + +template <Conv... C> +constexpr bool ValidFormatImpl(string_view format) { + return FormatParser(format, + {ConvListT<sizeof...(C)>{{C...}}.list, sizeof...(C)}) + .Run(); +} + +#endif // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_STR_FORMAT_CHECKER_H_ diff --git a/absl/strings/internal/str_format/checker_test.cc b/absl/strings/internal/str_format/checker_test.cc new file mode 100644 index 00000000..b4f38979 --- /dev/null +++ b/absl/strings/internal/str_format/checker_test.cc @@ -0,0 +1,152 @@ +#include <string> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/strings/str_format.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { +namespace { + +std::string ConvToString(Conv conv) { + std::string out; +#define CONV_SET_CASE(c) \ + if (Contains(conv, Conv::c)) out += #c; + ABSL_CONVERSION_CHARS_EXPAND_(CONV_SET_CASE, ) +#undef CONV_SET_CASE + if (Contains(conv, Conv::star)) out += "*"; + return out; +} + +TEST(StrFormatChecker, ArgumentToConv) { + Conv conv = ArgumentToConv<std::string>(); + EXPECT_EQ(ConvToString(conv), "s"); + + conv = ArgumentToConv<const char*>(); + EXPECT_EQ(ConvToString(conv), "sp"); + + conv = ArgumentToConv<double>(); + EXPECT_EQ(ConvToString(conv), "fFeEgGaA"); + + conv = ArgumentToConv<int>(); + EXPECT_EQ(ConvToString(conv), "cdiouxXfFeEgGaA*"); + + conv = ArgumentToConv<std::string*>(); + EXPECT_EQ(ConvToString(conv), "p"); +} + +#if ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + +struct Case { + bool result; + const char* format; +}; + +template <typename... Args> +constexpr Case ValidFormat(const char* format) { + return {ValidFormatImpl<ArgumentToConv<Args>()...>(format), format}; +} + +TEST(StrFormatChecker, ValidFormat) { + // We want to make sure these expressions are constexpr and they have the + // expected value. + // If they are not constexpr the attribute will just ignore them and not give + // a compile time error. + enum e {}; + enum class e2 {}; + constexpr Case trues[] = { + ValidFormat<>("abc"), // + + ValidFormat<e>("%d"), // + ValidFormat<e2>("%d"), // + ValidFormat<int>("%% %d"), // + ValidFormat<int>("%ld"), // + ValidFormat<int>("%lld"), // + ValidFormat<std::string>("%s"), // + ValidFormat<std::string>("%10s"), // + ValidFormat<int>("%.10x"), // + ValidFormat<int, int>("%*.3x"), // + ValidFormat<int>("%1.d"), // + ValidFormat<int>("%.d"), // + ValidFormat<int, double>("%d %g"), // + ValidFormat<int, std::string>("%*s"), // + ValidFormat<int, double>("%.*f"), // + ValidFormat<void (*)(), volatile int*>("%p %p"), // + ValidFormat<string_view, const char*, double, void*>( + "string_view=%s const char*=%s double=%f void*=%p)"), + + ValidFormat<int>("%% %1$d"), // + ValidFormat<int>("%1$ld"), // + ValidFormat<int>("%1$lld"), // + ValidFormat<std::string>("%1$s"), // + ValidFormat<std::string>("%1$10s"), // + ValidFormat<int>("%1$.10x"), // + ValidFormat<int>("%1$*1$.*1$d"), // + ValidFormat<int, int>("%1$*2$.3x"), // + ValidFormat<int>("%1$1.d"), // + ValidFormat<int>("%1$.d"), // + ValidFormat<double, int>("%2$d %1$g"), // + ValidFormat<int, std::string>("%2$*1$s"), // + ValidFormat<int, double>("%2$.*1$f"), // + ValidFormat<void*, string_view, const char*, double>( + "string_view=%2$s const char*=%3$s double=%4$f void*=%1$p " + "repeat=%3$s)")}; + + for (Case c : trues) { + EXPECT_TRUE(c.result) << c.format; + } + + constexpr Case falses[] = { + ValidFormat<int>(""), // + + ValidFormat<e>("%s"), // + ValidFormat<e2>("%s"), // + ValidFormat<>("%s"), // + ValidFormat<>("%r"), // + ValidFormat<int>("%s"), // + ValidFormat<int>("%.1.d"), // + ValidFormat<int>("%*1d"), // + ValidFormat<int>("%1-d"), // + ValidFormat<std::string, int>("%*s"), // + ValidFormat<int>("%*d"), // + ValidFormat<std::string>("%p"), // + ValidFormat<int (*)(int)>("%d"), // + + ValidFormat<>("%3$d"), // + ValidFormat<>("%1$r"), // + ValidFormat<int>("%1$s"), // + ValidFormat<int>("%1$.1.d"), // + ValidFormat<int>("%1$*2$1d"), // + ValidFormat<int>("%1$1-d"), // + ValidFormat<std::string, int>("%2$*1$s"), // + ValidFormat<std::string>("%1$p"), + + ValidFormat<int, int>("%d %2$d"), // + }; + + for (Case c : falses) { + EXPECT_FALSE(c.result) << c.format; + } +} + +TEST(StrFormatChecker, LongFormat) { +#define CHARS_X_40 "1234567890123456789012345678901234567890" +#define CHARS_X_400 \ + CHARS_X_40 CHARS_X_40 CHARS_X_40 CHARS_X_40 CHARS_X_40 CHARS_X_40 CHARS_X_40 \ + CHARS_X_40 CHARS_X_40 CHARS_X_40 +#define CHARS_X_4000 \ + CHARS_X_400 CHARS_X_400 CHARS_X_400 CHARS_X_400 CHARS_X_400 CHARS_X_400 \ + CHARS_X_400 CHARS_X_400 CHARS_X_400 CHARS_X_400 + constexpr char long_format[] = + CHARS_X_4000 "%d" CHARS_X_4000 "%s" CHARS_X_4000; + constexpr bool is_valid = ValidFormat<int, std::string>(long_format).result; + EXPECT_TRUE(is_valid); +} + +#endif // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + +} // namespace +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/convert_test.cc b/absl/strings/internal/str_format/convert_test.cc new file mode 100644 index 00000000..95d57b67 --- /dev/null +++ b/absl/strings/internal/str_format/convert_test.cc @@ -0,0 +1,577 @@ +#include <errno.h> +#include <stdarg.h> +#include <stdio.h> +#include <cmath> +#include <string> + +#include "gtest/gtest.h" +#include "absl/strings/internal/str_format/bind.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { +namespace { + +template <typename T, size_t N> +size_t ArraySize(T (&)[N]) { + return N; +} + +std::string LengthModFor(float) { return ""; } +std::string LengthModFor(double) { return ""; } +std::string LengthModFor(long double) { return "L"; } +std::string LengthModFor(char) { return "hh"; } +std::string LengthModFor(signed char) { return "hh"; } +std::string LengthModFor(unsigned char) { return "hh"; } +std::string LengthModFor(short) { return "h"; } // NOLINT +std::string LengthModFor(unsigned short) { return "h"; } // NOLINT +std::string LengthModFor(int) { return ""; } +std::string LengthModFor(unsigned) { return ""; } +std::string LengthModFor(long) { return "l"; } // NOLINT +std::string LengthModFor(unsigned long) { return "l"; } // NOLINT +std::string LengthModFor(long long) { return "ll"; } // NOLINT +std::string LengthModFor(unsigned long long) { return "ll"; } // NOLINT + +std::string EscCharImpl(int v) { + if (isprint(v)) return std::string(1, static_cast<char>(v)); + char buf[64]; + int n = snprintf(buf, sizeof(buf), "\\%#.2x", + static_cast<unsigned>(v & 0xff)); + assert(n > 0 && n < sizeof(buf)); + return std::string(buf, n); +} + +std::string Esc(char v) { return EscCharImpl(v); } +std::string Esc(signed char v) { return EscCharImpl(v); } +std::string Esc(unsigned char v) { return EscCharImpl(v); } + +template <typename T> +std::string Esc(const T &v) { + std::ostringstream oss; + oss << v; + return oss.str(); +} + +void StrAppend(std::string *dst, const char *format, va_list ap) { + // First try with a small fixed size buffer + static const int kSpaceLength = 1024; + char space[kSpaceLength]; + + // It's possible for methods that use a va_list to invalidate + // the data in it upon use. The fix is to make a copy + // of the structure before using it and use that copy instead. + va_list backup_ap; + va_copy(backup_ap, ap); + int result = vsnprintf(space, kSpaceLength, format, backup_ap); + va_end(backup_ap); + if (result < kSpaceLength) { + if (result >= 0) { + // Normal case -- everything fit. + dst->append(space, result); + return; + } + if (result < 0) { + // Just an error. + return; + } + } + + // Increase the buffer size to the size requested by vsnprintf, + // plus one for the closing \0. + int length = result + 1; + char *buf = new char[length]; + + // Restore the va_list before we use it again + va_copy(backup_ap, ap); + result = vsnprintf(buf, length, format, backup_ap); + va_end(backup_ap); + + if (result >= 0 && result < length) { + // It fit + dst->append(buf, result); + } + delete[] buf; +} + +std::string StrPrint(const char *format, ...) { + va_list ap; + va_start(ap, format); + std::string result; + StrAppend(&result, format, ap); + va_end(ap); + return result; +} + +class FormatConvertTest : public ::testing::Test { }; + +template <typename T> +void TestStringConvert(const T& str) { + const FormatArgImpl args[] = {FormatArgImpl(str)}; + struct Expectation { + const char *out; + const char *fmt; + }; + const Expectation kExpect[] = { + {"hello", "%1$s" }, + {"", "%1$.s" }, + {"", "%1$.0s" }, + {"h", "%1$.1s" }, + {"he", "%1$.2s" }, + {"hello", "%1$.10s" }, + {" hello", "%1$6s" }, + {" he", "%1$5.2s" }, + {"he ", "%1$-5.2s" }, + {"hello ", "%1$-6.10s" }, + }; + for (const Expectation &e : kExpect) { + UntypedFormatSpecImpl format(e.fmt); + EXPECT_EQ(e.out, FormatPack(format, absl::MakeSpan(args))); + } +} + +TEST_F(FormatConvertTest, BasicString) { + TestStringConvert("hello"); // As char array. + TestStringConvert(static_cast<const char*>("hello")); + TestStringConvert(std::string("hello")); + TestStringConvert(string_view("hello")); +} + +TEST_F(FormatConvertTest, NullString) { + const char* p = nullptr; + UntypedFormatSpecImpl format("%s"); + EXPECT_EQ("", FormatPack(format, {FormatArgImpl(p)})); +} + +TEST_F(FormatConvertTest, StringPrecision) { + // We cap at the precision. + char c = 'a'; + const char* p = &c; + UntypedFormatSpecImpl format("%.1s"); + EXPECT_EQ("a", FormatPack(format, {FormatArgImpl(p)})); + + // We cap at the nul terminator. + p = "ABC"; + UntypedFormatSpecImpl format2("%.10s"); + EXPECT_EQ("ABC", FormatPack(format2, {FormatArgImpl(p)})); +} + +TEST_F(FormatConvertTest, Pointer) { +#if _MSC_VER + // MSVC's printf implementation prints pointers differently. We can't easily + // compare our implementation to theirs. + return; +#endif + static int x = 0; + const int *xp = &x; + char c = 'h'; + char *mcp = &c; + const char *cp = "hi"; + const char *cnil = nullptr; + const int *inil = nullptr; + using VoidF = void (*)(); + VoidF fp = [] {}, fnil = nullptr; + volatile char vc; + volatile char* vcp = &vc; + volatile char* vcnil = nullptr; + const FormatArgImpl args[] = { + FormatArgImpl(xp), FormatArgImpl(cp), FormatArgImpl(inil), + FormatArgImpl(cnil), FormatArgImpl(mcp), FormatArgImpl(fp), + FormatArgImpl(fnil), FormatArgImpl(vcp), FormatArgImpl(vcnil), + }; + struct Expectation { + std::string out; + const char *fmt; + }; + const Expectation kExpect[] = { + {StrPrint("%p", &x), "%p"}, + {StrPrint("%20p", &x), "%20p"}, + {StrPrint("%.1p", &x), "%.1p"}, + {StrPrint("%.20p", &x), "%.20p"}, + {StrPrint("%30.20p", &x), "%30.20p"}, + + {StrPrint("%-p", &x), "%-p"}, + {StrPrint("%-20p", &x), "%-20p"}, + {StrPrint("%-.1p", &x), "%-.1p"}, + {StrPrint("%.20p", &x), "%.20p"}, + {StrPrint("%-30.20p", &x), "%-30.20p"}, + + {StrPrint("%p", cp), "%2$p"}, // const char* + {"(nil)", "%3$p"}, // null const char * + {"(nil)", "%4$p"}, // null const int * + {StrPrint("%p", mcp), "%5$p"}, // nonconst char* + + {StrPrint("%p", fp), "%6$p"}, // function pointer + {StrPrint("%p", vcp), "%8$p"}, // function pointer + +#ifndef __APPLE__ + // Apple's printf differs here (0x0 vs. nil) + {StrPrint("%p", fnil), "%7$p"}, // null function pointer + {StrPrint("%p", vcnil), "%9$p"}, // null function pointer +#endif + }; + for (const Expectation &e : kExpect) { + UntypedFormatSpecImpl format(e.fmt); + EXPECT_EQ(e.out, FormatPack(format, absl::MakeSpan(args))) << e.fmt; + } +} + +struct Cardinal { + enum Pos { k1 = 1, k2 = 2, k3 = 3 }; + enum Neg { kM1 = -1, kM2 = -2, kM3 = -3 }; +}; + +TEST_F(FormatConvertTest, Enum) { + const Cardinal::Pos k3 = Cardinal::k3; + const Cardinal::Neg km3 = Cardinal::kM3; + const FormatArgImpl args[] = {FormatArgImpl(k3), FormatArgImpl(km3)}; + UntypedFormatSpecImpl format("%1$d"); + UntypedFormatSpecImpl format2("%2$d"); + EXPECT_EQ("3", FormatPack(format, absl::MakeSpan(args))); + EXPECT_EQ("-3", FormatPack(format2, absl::MakeSpan(args))); +} + +template <typename T> +class TypedFormatConvertTest : public FormatConvertTest { }; + +TYPED_TEST_CASE_P(TypedFormatConvertTest); + +std::vector<std::string> AllFlagCombinations() { + const char kFlags[] = {'-', '#', '0', '+', ' '}; + std::vector<std::string> result; + for (size_t fsi = 0; fsi < (1ull << ArraySize(kFlags)); ++fsi) { + std::string flag_set; + for (size_t fi = 0; fi < ArraySize(kFlags); ++fi) + if (fsi & (1ull << fi)) + flag_set += kFlags[fi]; + result.push_back(flag_set); + } + return result; +} + +TYPED_TEST_P(TypedFormatConvertTest, AllIntsWithFlags) { + typedef TypeParam T; + typedef typename std::make_unsigned<T>::type UnsignedT; + using remove_volatile_t = typename std::remove_volatile<T>::type; + const T kMin = std::numeric_limits<remove_volatile_t>::min(); + const T kMax = std::numeric_limits<remove_volatile_t>::max(); + const T kVals[] = { + remove_volatile_t(1), + remove_volatile_t(2), + remove_volatile_t(3), + remove_volatile_t(123), + remove_volatile_t(-1), + remove_volatile_t(-2), + remove_volatile_t(-3), + remove_volatile_t(-123), + remove_volatile_t(0), + kMax - remove_volatile_t(1), + kMax, + kMin + remove_volatile_t(1), + kMin, + }; + const char kConvChars[] = {'d', 'i', 'u', 'o', 'x', 'X'}; + const std::string kWid[] = {"", "4", "10"}; + const std::string kPrec[] = {"", ".", ".0", ".4", ".10"}; + + const std::vector<std::string> flag_sets = AllFlagCombinations(); + + for (size_t vi = 0; vi < ArraySize(kVals); ++vi) { + const T val = kVals[vi]; + SCOPED_TRACE(Esc(val)); + const FormatArgImpl args[] = {FormatArgImpl(val)}; + for (size_t ci = 0; ci < ArraySize(kConvChars); ++ci) { + const char conv_char = kConvChars[ci]; + for (size_t fsi = 0; fsi < flag_sets.size(); ++fsi) { + const std::string &flag_set = flag_sets[fsi]; + for (size_t wi = 0; wi < ArraySize(kWid); ++wi) { + const std::string &wid = kWid[wi]; + for (size_t pi = 0; pi < ArraySize(kPrec); ++pi) { + const std::string &prec = kPrec[pi]; + + const bool is_signed_conv = (conv_char == 'd' || conv_char == 'i'); + const bool is_unsigned_to_signed = + !std::is_signed<T>::value && is_signed_conv; + // Don't consider sign-related flags '+' and ' ' when doing + // unsigned to signed conversions. + if (is_unsigned_to_signed && + flag_set.find_first_of("+ ") != std::string::npos) { + continue; + } + + std::string new_fmt("%"); + new_fmt += flag_set; + new_fmt += wid; + new_fmt += prec; + // old and new always agree up to here. + std::string old_fmt = new_fmt; + new_fmt += conv_char; + std::string old_result; + if (is_unsigned_to_signed) { + // don't expect agreement on unsigned formatted as signed, + // as printf can't do that conversion properly. For those + // cases, we do expect agreement with printf with a "%u" + // and the unsigned equivalent of 'val'. + UnsignedT uval = val; + old_fmt += LengthModFor(uval); + old_fmt += "u"; + old_result = StrPrint(old_fmt.c_str(), uval); + } else { + old_fmt += LengthModFor(val); + old_fmt += conv_char; + old_result = StrPrint(old_fmt.c_str(), val); + } + + SCOPED_TRACE(std::string() + " old_fmt: \"" + old_fmt + + "\"'" + " new_fmt: \"" + + new_fmt + "\""); + UntypedFormatSpecImpl format(new_fmt); + EXPECT_EQ(old_result, FormatPack(format, absl::MakeSpan(args))); + } + } + } + } + } +} + +TYPED_TEST_P(TypedFormatConvertTest, Char) { + typedef TypeParam T; + using remove_volatile_t = typename std::remove_volatile<T>::type; + static const T kMin = std::numeric_limits<remove_volatile_t>::min(); + static const T kMax = std::numeric_limits<remove_volatile_t>::max(); + T kVals[] = { + remove_volatile_t(1), remove_volatile_t(2), remove_volatile_t(10), + remove_volatile_t(-1), remove_volatile_t(-2), remove_volatile_t(-10), + remove_volatile_t(0), + kMin + remove_volatile_t(1), kMin, + kMax - remove_volatile_t(1), kMax + }; + for (const T &c : kVals) { + const FormatArgImpl args[] = {FormatArgImpl(c)}; + UntypedFormatSpecImpl format("%c"); + EXPECT_EQ(StrPrint("%c", c), FormatPack(format, absl::MakeSpan(args))); + } +} + +REGISTER_TYPED_TEST_CASE_P(TypedFormatConvertTest, AllIntsWithFlags, Char); + +typedef ::testing::Types< + int, unsigned, volatile int, + short, unsigned short, + long, unsigned long, + long long, unsigned long long, + signed char, unsigned char, char> + AllIntTypes; +INSTANTIATE_TYPED_TEST_CASE_P(TypedFormatConvertTestWithAllIntTypes, + TypedFormatConvertTest, AllIntTypes); +TEST_F(FormatConvertTest, Uint128) { + absl::uint128 v = static_cast<absl::uint128>(0x1234567890abcdef) * 1979; + absl::uint128 max = absl::Uint128Max(); + const FormatArgImpl args[] = {FormatArgImpl(v), FormatArgImpl(max)}; + + struct Case { + const char* format; + const char* expected; + } cases[] = { + {"%1$d", "2595989796776606496405"}, + {"%1$30d", " 2595989796776606496405"}, + {"%1$-30d", "2595989796776606496405 "}, + {"%1$u", "2595989796776606496405"}, + {"%1$x", "8cba9876066020f695"}, + {"%2$d", "340282366920938463463374607431768211455"}, + {"%2$u", "340282366920938463463374607431768211455"}, + {"%2$x", "ffffffffffffffffffffffffffffffff"}, + }; + + for (auto c : cases) { + UntypedFormatSpecImpl format(c.format); + EXPECT_EQ(c.expected, FormatPack(format, absl::MakeSpan(args))); + } +} + +TEST_F(FormatConvertTest, Float) { +#if _MSC_VER + // MSVC has a different rounding policy than us so we can't test our + // implementation against the native one there. + return; +#endif // _MSC_VER + + const char *const kFormats[] = { + "%", "%.3", "%8.5", "%9", "%.60", "%.30", "%03", "%+", + "% ", "%-10", "%#15.3", "%#.0", "%.0", "%1$*2$", "%1$.*2$"}; + + std::vector<double> doubles = {0.0, + -0.0, + .99999999999999, + 99999999999999., + std::numeric_limits<double>::max(), + -std::numeric_limits<double>::max(), + std::numeric_limits<double>::min(), + -std::numeric_limits<double>::min(), + std::numeric_limits<double>::lowest(), + -std::numeric_limits<double>::lowest(), + std::numeric_limits<double>::epsilon(), + std::numeric_limits<double>::epsilon() + 1, + std::numeric_limits<double>::infinity(), + -std::numeric_limits<double>::infinity()}; + +#ifndef __APPLE__ + // Apple formats NaN differently (+nan) vs. (nan) + doubles.push_back(std::nan("")); +#endif + + // Some regression tests. + doubles.push_back(0.99999999999999989); + + if (std::numeric_limits<double>::has_denorm != std::denorm_absent) { + doubles.push_back(std::numeric_limits<double>::denorm_min()); + doubles.push_back(-std::numeric_limits<double>::denorm_min()); + } + + for (double base : + {1., 12., 123., 1234., 12345., 123456., 1234567., 12345678., 123456789., + 1234567890., 12345678901., 123456789012., 1234567890123.}) { + for (int exp = -123; exp <= 123; ++exp) { + for (int sign : {1, -1}) { + doubles.push_back(sign * std::ldexp(base, exp)); + } + } + } + + for (const char *fmt : kFormats) { + for (char f : {'f', 'F', // + 'g', 'G', // + 'a', 'A', // + 'e', 'E'}) { + std::string fmt_str = std::string(fmt) + f; + for (double d : doubles) { + int i = -10; + FormatArgImpl args[2] = {FormatArgImpl(d), FormatArgImpl(i)}; + UntypedFormatSpecImpl format(fmt_str); + // We use ASSERT_EQ here because failures are usually correlated and a + // bug would print way too many failed expectations causing the test to + // time out. + ASSERT_EQ(StrPrint(fmt_str.c_str(), d, i), + FormatPack(format, absl::MakeSpan(args))) + << fmt_str << " " << StrPrint("%.18g", d) << " " + << StrPrint("%.999f", d); + } + } + } +} + +TEST_F(FormatConvertTest, LongDouble) { + const char *const kFormats[] = {"%", "%.3", "%8.5", "%9", + "%.60", "%+", "% ", "%-10"}; + + // This value is not representable in double, but it is in long double that + // uses the extended format. + // This is to verify that we are not truncating the value mistakenly through a + // double. + long double very_precise = 10000000000000000.25L; + + std::vector<long double> doubles = { + 0.0, + -0.0, + very_precise, + 1 / very_precise, + std::numeric_limits<long double>::max(), + -std::numeric_limits<long double>::max(), + std::numeric_limits<long double>::min(), + -std::numeric_limits<long double>::min(), + std::numeric_limits<long double>::infinity(), + -std::numeric_limits<long double>::infinity()}; + + for (const char *fmt : kFormats) { + for (char f : {'f', 'F', // + 'g', 'G', // + 'a', 'A', // + 'e', 'E'}) { + std::string fmt_str = std::string(fmt) + 'L' + f; + for (auto d : doubles) { + FormatArgImpl arg(d); + UntypedFormatSpecImpl format(fmt_str); + // We use ASSERT_EQ here because failures are usually correlated and a + // bug would print way too many failed expectations causing the test to + // time out. + ASSERT_EQ(StrPrint(fmt_str.c_str(), d), + FormatPack(format, {&arg, 1})) + << fmt_str << " " << StrPrint("%.18Lg", d) << " " + << StrPrint("%.999Lf", d); + } + } + } +} + +TEST_F(FormatConvertTest, IntAsFloat) { + const int kMin = std::numeric_limits<int>::min(); + const int kMax = std::numeric_limits<int>::max(); + const int ia[] = { + 1, 2, 3, 123, + -1, -2, -3, -123, + 0, kMax - 1, kMax, kMin + 1, kMin }; + for (const int fx : ia) { + SCOPED_TRACE(fx); + const FormatArgImpl args[] = {FormatArgImpl(fx)}; + struct Expectation { + int line; + std::string out; + const char *fmt; + }; + const double dx = static_cast<double>(fx); + const Expectation kExpect[] = { + { __LINE__, StrPrint("%f", dx), "%f" }, + { __LINE__, StrPrint("%12f", dx), "%12f" }, + { __LINE__, StrPrint("%.12f", dx), "%.12f" }, + { __LINE__, StrPrint("%12a", dx), "%12a" }, + { __LINE__, StrPrint("%.12a", dx), "%.12a" }, + }; + for (const Expectation &e : kExpect) { + SCOPED_TRACE(e.line); + SCOPED_TRACE(e.fmt); + UntypedFormatSpecImpl format(e.fmt); + EXPECT_EQ(e.out, FormatPack(format, absl::MakeSpan(args))); + } + } +} + +template <typename T> +bool FormatFails(const char* test_format, T value) { + std::string format_string = std::string("<<") + test_format + ">>"; + UntypedFormatSpecImpl format(format_string); + + int one = 1; + const FormatArgImpl args[] = {FormatArgImpl(value), FormatArgImpl(one)}; + EXPECT_EQ(FormatPack(format, absl::MakeSpan(args)), "") + << "format=" << test_format << " value=" << value; + return FormatPack(format, absl::MakeSpan(args)).empty(); +} + +TEST_F(FormatConvertTest, ExpectedFailures) { + // Int input + EXPECT_TRUE(FormatFails("%p", 1)); + EXPECT_TRUE(FormatFails("%s", 1)); + EXPECT_TRUE(FormatFails("%n", 1)); + + // Double input + EXPECT_TRUE(FormatFails("%p", 1.)); + EXPECT_TRUE(FormatFails("%s", 1.)); + EXPECT_TRUE(FormatFails("%n", 1.)); + EXPECT_TRUE(FormatFails("%c", 1.)); + EXPECT_TRUE(FormatFails("%d", 1.)); + EXPECT_TRUE(FormatFails("%x", 1.)); + EXPECT_TRUE(FormatFails("%*d", 1.)); + + // String input + EXPECT_TRUE(FormatFails("%n", "")); + EXPECT_TRUE(FormatFails("%c", "")); + EXPECT_TRUE(FormatFails("%d", "")); + EXPECT_TRUE(FormatFails("%x", "")); + EXPECT_TRUE(FormatFails("%f", "")); + EXPECT_TRUE(FormatFails("%*d", "")); +} + +} // namespace +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/extension.cc b/absl/strings/internal/str_format/extension.cc new file mode 100644 index 00000000..e3b41c82 --- /dev/null +++ b/absl/strings/internal/str_format/extension.cc @@ -0,0 +1,86 @@ +// +// Copyright 2017 The Abseil 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 "absl/strings/internal/str_format/extension.h" + +#include <errno.h> +#include <algorithm> +#include <string> + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { +namespace { +// clang-format off +#define ABSL_LENGTH_MODS_EXPAND_ \ + X_VAL(h) X_SEP \ + X_VAL(hh) X_SEP \ + X_VAL(l) X_SEP \ + X_VAL(ll) X_SEP \ + X_VAL(L) X_SEP \ + X_VAL(j) X_SEP \ + X_VAL(z) X_SEP \ + X_VAL(t) X_SEP \ + X_VAL(q) +// clang-format on +} // namespace + +const LengthMod::Spec LengthMod::kSpecs[] = { +#define X_VAL(id) { LengthMod::id, #id, strlen(#id) } +#define X_SEP , + ABSL_LENGTH_MODS_EXPAND_, {LengthMod::none, "", 0} +#undef X_VAL +#undef X_SEP +}; + +const ConversionChar::Spec ConversionChar::kSpecs[] = { +#define X_VAL(id) { ConversionChar::id, #id[0] } +#define X_SEP , + ABSL_CONVERSION_CHARS_EXPAND_(X_VAL, X_SEP), + {ConversionChar::none, '\0'}, +#undef X_VAL +#undef X_SEP +}; + +std::string Flags::ToString() const { + std::string s; + s.append(left ? "-" : ""); + s.append(show_pos ? "+" : ""); + s.append(sign_col ? " " : ""); + s.append(alt ? "#" : ""); + s.append(zero ? "0" : ""); + return s; +} + +const size_t LengthMod::kNumValues; + +const size_t ConversionChar::kNumValues; + +bool FormatSinkImpl::PutPaddedString(string_view v, int w, int p, bool l) { + size_t space_remaining = 0; + if (w >= 0) space_remaining = w; + size_t n = v.size(); + if (p >= 0) n = std::min(n, static_cast<size_t>(p)); + string_view shown(v.data(), n); + space_remaining = Excess(shown.size(), space_remaining); + if (!l) Append(space_remaining, ' '); + Append(shown); + if (l) Append(space_remaining, ' '); + return true; +} + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/extension.h b/absl/strings/internal/str_format/extension.h new file mode 100644 index 00000000..d401b4ed --- /dev/null +++ b/absl/strings/internal/str_format/extension.h @@ -0,0 +1,414 @@ +// +// Copyright 2017 The Abseil 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 ABSL_STRINGS_INTERNAL_STR_FORMAT_EXTENSION_H_ +#define ABSL_STRINGS_INTERNAL_STR_FORMAT_EXTENSION_H_ + +#include <limits.h> +#include <cstddef> +#include <cstring> +#include <ostream> + +#include "absl/base/port.h" +#include "absl/strings/internal/str_format/output.h" +#include "absl/strings/string_view.h" + +class Cord; + +namespace absl { +inline namespace lts_2018_12_18 { + +namespace str_format_internal { + +class FormatRawSinkImpl { + public: + // Implicitly convert from any type that provides the hook function as + // described above. + template <typename T, decltype(str_format_internal::InvokeFlush( + std::declval<T*>(), string_view()))* = nullptr> + FormatRawSinkImpl(T* raw) // NOLINT + : sink_(raw), write_(&FormatRawSinkImpl::Flush<T>) {} + + void Write(string_view s) { write_(sink_, s); } + + template <typename T> + static FormatRawSinkImpl Extract(T s) { + return s.sink_; + } + + private: + template <typename T> + static void Flush(void* r, string_view s) { + str_format_internal::InvokeFlush(static_cast<T*>(r), s); + } + + void* sink_; + void (*write_)(void*, string_view); +}; + +// An abstraction to which conversions write their string data. +class FormatSinkImpl { + public: + explicit FormatSinkImpl(FormatRawSinkImpl raw) : raw_(raw) {} + + ~FormatSinkImpl() { Flush(); } + + void Flush() { + raw_.Write(string_view(buf_, pos_ - buf_)); + pos_ = buf_; + } + + void Append(size_t n, char c) { + if (n == 0) return; + size_ += n; + auto raw_append = [&](size_t count) { + memset(pos_, c, count); + pos_ += count; + }; + while (n > Avail()) { + n -= Avail(); + if (Avail() > 0) { + raw_append(Avail()); + } + Flush(); + } + raw_append(n); + } + + void Append(string_view v) { + size_t n = v.size(); + if (n == 0) return; + size_ += n; + if (n >= Avail()) { + Flush(); + raw_.Write(v); + return; + } + memcpy(pos_, v.data(), n); + pos_ += n; + } + + size_t size() const { return size_; } + + // Put 'v' to 'sink' with specified width, precision, and left flag. + bool PutPaddedString(string_view v, int w, int p, bool l); + + template <typename T> + T Wrap() { + return T(this); + } + + template <typename T> + static FormatSinkImpl* Extract(T* s) { + return s->sink_; + } + + private: + size_t Avail() const { return buf_ + sizeof(buf_) - pos_; } + + FormatRawSinkImpl raw_; + size_t size_ = 0; + char* pos_ = buf_; + char buf_[1024]; +}; + +struct Flags { + bool basic : 1; // fastest conversion: no flags, width, or precision + bool left : 1; // "-" + bool show_pos : 1; // "+" + bool sign_col : 1; // " " + bool alt : 1; // "#" + bool zero : 1; // "0" + std::string ToString() const; + friend std::ostream& operator<<(std::ostream& os, const Flags& v) { + return os << v.ToString(); + } +}; + +struct LengthMod { + public: + enum Id : uint8_t { + h, hh, l, ll, L, j, z, t, q, none + }; + static const size_t kNumValues = none + 1; + + LengthMod() : id_(none) {} + + // Index into the opaque array of LengthMod enums. + // Requires: i < kNumValues + static LengthMod FromIndex(size_t i) { + return LengthMod(kSpecs[i].value); + } + + static LengthMod FromId(Id id) { return LengthMod(id); } + + // The length modifier std::string associated with a specified LengthMod. + string_view name() const { + const Spec& spec = kSpecs[id_]; + return {spec.name, spec.name_length}; + } + + Id id() const { return id_; } + + friend bool operator==(const LengthMod& a, const LengthMod& b) { + return a.id() == b.id(); + } + friend bool operator!=(const LengthMod& a, const LengthMod& b) { + return !(a == b); + } + friend std::ostream& operator<<(std::ostream& os, const LengthMod& v) { + return os << v.name(); + } + + private: + struct Spec { + Id value; + const char *name; + size_t name_length; + }; + static const Spec kSpecs[]; + + explicit LengthMod(Id id) : id_(id) {} + + Id id_; +}; + +// clang-format off +#define ABSL_CONVERSION_CHARS_EXPAND_(X_VAL, X_SEP) \ + /* text */ \ + X_VAL(c) X_SEP X_VAL(C) X_SEP X_VAL(s) X_SEP X_VAL(S) X_SEP \ + /* ints */ \ + X_VAL(d) X_SEP X_VAL(i) X_SEP X_VAL(o) X_SEP \ + X_VAL(u) X_SEP X_VAL(x) X_SEP X_VAL(X) X_SEP \ + /* floats */ \ + X_VAL(f) X_SEP X_VAL(F) X_SEP X_VAL(e) X_SEP X_VAL(E) X_SEP \ + X_VAL(g) X_SEP X_VAL(G) X_SEP X_VAL(a) X_SEP X_VAL(A) X_SEP \ + /* misc */ \ + X_VAL(n) X_SEP X_VAL(p) +// clang-format on + +struct ConversionChar { + public: + enum Id : uint8_t { + c, C, s, S, // text + d, i, o, u, x, X, // int + f, F, e, E, g, G, a, A, // float + n, p, // misc + none + }; + static const size_t kNumValues = none + 1; + + ConversionChar() : id_(none) {} + + public: + // Index into the opaque array of ConversionChar enums. + // Requires: i < kNumValues + static ConversionChar FromIndex(size_t i) { + return ConversionChar(kSpecs[i].value); + } + + static ConversionChar FromChar(char c) { + ConversionChar::Id out_id = ConversionChar::none; + switch (c) { +#define X_VAL(id) \ + case #id[0]: \ + out_id = ConversionChar::id; \ + break; + ABSL_CONVERSION_CHARS_EXPAND_(X_VAL, ) +#undef X_VAL + default: + break; + } + return ConversionChar(out_id); + } + + static ConversionChar FromId(Id id) { return ConversionChar(id); } + Id id() const { return id_; } + + int radix() const { + switch (id()) { + case x: case X: case a: case A: case p: return 16; + case o: return 8; + default: return 10; + } + } + + bool upper() const { + switch (id()) { + case X: case F: case E: case G: case A: return true; + default: return false; + } + } + + bool is_signed() const { + switch (id()) { + case d: case i: return true; + default: return false; + } + } + + bool is_integral() const { + switch (id()) { + case d: case i: case u: case o: case x: case X: + return true; + default: return false; + } + } + + bool is_float() const { + switch (id()) { + case a: case e: case f: case g: case A: case E: case F: case G: + return true; + default: return false; + } + } + + bool IsValid() const { return id() != none; } + + // The associated char. + char Char() const { return kSpecs[id_].name; } + + friend bool operator==(const ConversionChar& a, const ConversionChar& b) { + return a.id() == b.id(); + } + friend bool operator!=(const ConversionChar& a, const ConversionChar& b) { + return !(a == b); + } + friend std::ostream& operator<<(std::ostream& os, const ConversionChar& v) { + char c = v.Char(); + if (!c) c = '?'; + return os << c; + } + + private: + struct Spec { + Id value; + char name; + }; + static const Spec kSpecs[]; + + explicit ConversionChar(Id id) : id_(id) {} + + Id id_; +}; + +class ConversionSpec { + public: + Flags flags() const { return flags_; } + LengthMod length_mod() const { return length_mod_; } + ConversionChar conv() const { + // Keep this field first in the struct . It generates better code when + // accessing it when ConversionSpec is passed by value in registers. + static_assert(offsetof(ConversionSpec, conv_) == 0, ""); + return conv_; + } + + // Returns the specified width. If width is unspecfied, it returns a negative + // value. + int width() const { return width_; } + // Returns the specified precision. If precision is unspecfied, it returns a + // negative value. + int precision() const { return precision_; } + + void set_flags(Flags f) { flags_ = f; } + void set_length_mod(LengthMod lm) { length_mod_ = lm; } + void set_conv(ConversionChar c) { conv_ = c; } + void set_width(int w) { width_ = w; } + void set_precision(int p) { precision_ = p; } + void set_left(bool b) { flags_.left = b; } + + private: + ConversionChar conv_; + Flags flags_; + LengthMod length_mod_; + int width_; + int precision_; +}; + +constexpr uint64_t ConversionCharToConvValue(char conv) { + return +#define CONV_SET_CASE(c) \ + conv == #c[0] ? (uint64_t{1} << (1 + ConversionChar::Id::c)): + ABSL_CONVERSION_CHARS_EXPAND_(CONV_SET_CASE, ) +#undef CONV_SET_CASE + conv == '*' + ? 1 + : 0; +} + +enum class Conv : uint64_t { +#define CONV_SET_CASE(c) c = ConversionCharToConvValue(#c[0]), + ABSL_CONVERSION_CHARS_EXPAND_(CONV_SET_CASE, ) +#undef CONV_SET_CASE + + // Used for width/precision '*' specification. + star = ConversionCharToConvValue('*'), + + // Some predefined values: + integral = d | i | u | o | x | X, + floating = a | e | f | g | A | E | F | G, + numeric = integral | floating, + string = s, // absl:ignore(std::string) + pointer = p +}; + +// Type safe OR operator. +// We need this for two reasons: +// 1. operator| on enums makes them decay to integers and the result is an +// integer. We need the result to stay as an enum. +// 2. We use "enum class" which would not work even if we accepted the decay. +constexpr Conv operator|(Conv a, Conv b) { + return Conv(static_cast<uint64_t>(a) | static_cast<uint64_t>(b)); +} + +// Get a conversion with a single character in it. +constexpr Conv ConversionCharToConv(char c) { + return Conv(ConversionCharToConvValue(c)); +} + +// Checks whether `c` exists in `set`. +constexpr bool Contains(Conv set, char c) { + return (static_cast<uint64_t>(set) & ConversionCharToConvValue(c)) != 0; +} + +// Checks whether all the characters in `c` are contained in `set` +constexpr bool Contains(Conv set, Conv c) { + return (static_cast<uint64_t>(set) & static_cast<uint64_t>(c)) == + static_cast<uint64_t>(c); +} + +// Return type of the AbslFormatConvert() functions. +// The Conv template parameter is used to inform the framework of what +// conversion characters are supported by that AbslFormatConvert routine. +template <Conv C> +struct ConvertResult { + static constexpr Conv kConv = C; + bool value; +}; +template <Conv C> +constexpr Conv ConvertResult<C>::kConv; + +// Return capacity - used, clipped to a minimum of 0. +inline size_t Excess(size_t used, size_t capacity) { + return used < capacity ? capacity - used : 0; +} + +} // namespace str_format_internal + +} // inline namespace lts_2018_12_18 +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_STR_FORMAT_EXTENSION_H_ diff --git a/absl/strings/internal/str_format/extension_test.cc b/absl/strings/internal/str_format/extension_test.cc new file mode 100644 index 00000000..224fc923 --- /dev/null +++ b/absl/strings/internal/str_format/extension_test.cc @@ -0,0 +1,65 @@ +// +// Copyright 2017 The Abseil 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 "absl/strings/internal/str_format/extension.h" + +#include <random> +#include <string> +#include "absl/strings/str_format.h" + +#include "gtest/gtest.h" + +namespace { + +std::string MakeRandomString(size_t len) { + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution<> dis('a', 'z'); + std::string s(len, '0'); + for (char& c : s) { + c = dis(gen); + } + return s; +} + +TEST(FormatExtensionTest, SinkAppendSubstring) { + for (size_t chunk_size : {1, 10, 100, 1000, 10000}) { + std::string expected, actual; + absl::str_format_internal::FormatSinkImpl sink(&actual); + for (size_t chunks = 0; chunks < 10; ++chunks) { + std::string rand = MakeRandomString(chunk_size); + expected += rand; + sink.Append(rand); + } + sink.Flush(); + EXPECT_EQ(actual, expected); + } +} + +TEST(FormatExtensionTest, SinkAppendChars) { + for (size_t chunk_size : {1, 10, 100, 1000, 10000}) { + std::string expected, actual; + absl::str_format_internal::FormatSinkImpl sink(&actual); + for (size_t chunks = 0; chunks < 10; ++chunks) { + std::string rand = MakeRandomString(1); + expected.append(chunk_size, rand[0]); + sink.Append(chunk_size, rand[0]); + } + sink.Flush(); + EXPECT_EQ(actual, expected); + } +} +} // namespace diff --git a/absl/strings/internal/str_format/float_conversion.cc b/absl/strings/internal/str_format/float_conversion.cc new file mode 100644 index 00000000..7b617689 --- /dev/null +++ b/absl/strings/internal/str_format/float_conversion.cc @@ -0,0 +1,485 @@ +#include "absl/strings/internal/str_format/float_conversion.h" + +#include <string.h> +#include <algorithm> +#include <cassert> +#include <cmath> +#include <string> + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { + +namespace { + +char *CopyStringTo(string_view v, char *out) { + std::memcpy(out, v.data(), v.size()); + return out + v.size(); +} + +template <typename Float> +bool FallbackToSnprintf(const Float v, const ConversionSpec &conv, + FormatSinkImpl *sink) { + int w = conv.width() >= 0 ? conv.width() : 0; + int p = conv.precision() >= 0 ? conv.precision() : -1; + char fmt[32]; + { + char *fp = fmt; + *fp++ = '%'; + fp = CopyStringTo(conv.flags().ToString(), fp); + fp = CopyStringTo("*.*", fp); + if (std::is_same<long double, Float>()) { + *fp++ = 'L'; + } + *fp++ = conv.conv().Char(); + *fp = 0; + assert(fp < fmt + sizeof(fmt)); + } + std::string space(512, '\0'); + string_view result; + while (true) { + int n = snprintf(&space[0], space.size(), fmt, w, p, v); + if (n < 0) return false; + if (static_cast<size_t>(n) < space.size()) { + result = string_view(space.data(), n); + break; + } + space.resize(n + 1); + } + sink->Append(result); + return true; +} + +// 128-bits in decimal: ceil(128*log(2)/log(10)) +// or std::numeric_limits<__uint128_t>::digits10 +constexpr int kMaxFixedPrecision = 39; + +constexpr int kBufferLength = /*sign*/ 1 + + /*integer*/ kMaxFixedPrecision + + /*point*/ 1 + + /*fraction*/ kMaxFixedPrecision + + /*exponent e+123*/ 5; + +struct Buffer { + void push_front(char c) { + assert(begin > data); + *--begin = c; + } + void push_back(char c) { + assert(end < data + sizeof(data)); + *end++ = c; + } + void pop_back() { + assert(begin < end); + --end; + } + + char &back() { + assert(begin < end); + return end[-1]; + } + + char last_digit() const { return end[-1] == '.' ? end[-2] : end[-1]; } + + int size() const { return static_cast<int>(end - begin); } + + char data[kBufferLength]; + char *begin; + char *end; +}; + +enum class FormatStyle { Fixed, Precision }; + +// If the value is Inf or Nan, print it and return true. +// Otherwise, return false. +template <typename Float> +bool ConvertNonNumericFloats(char sign_char, Float v, + const ConversionSpec &conv, FormatSinkImpl *sink) { + char text[4], *ptr = text; + if (sign_char) *ptr++ = sign_char; + if (std::isnan(v)) { + ptr = std::copy_n(conv.conv().upper() ? "NAN" : "nan", 3, ptr); + } else if (std::isinf(v)) { + ptr = std::copy_n(conv.conv().upper() ? "INF" : "inf", 3, ptr); + } else { + return false; + } + + return sink->PutPaddedString(string_view(text, ptr - text), conv.width(), -1, + conv.flags().left); +} + +// Round up the last digit of the value. +// It will carry over and potentially overflow. 'exp' will be adjusted in that +// case. +template <FormatStyle mode> +void RoundUp(Buffer *buffer, int *exp) { + char *p = &buffer->back(); + while (p >= buffer->begin && (*p == '9' || *p == '.')) { + if (*p == '9') *p = '0'; + --p; + } + + if (p < buffer->begin) { + *p = '1'; + buffer->begin = p; + if (mode == FormatStyle::Precision) { + std::swap(p[1], p[2]); // move the . + ++*exp; + buffer->pop_back(); + } + } else { + ++*p; + } +} + +void PrintExponent(int exp, char e, Buffer *out) { + out->push_back(e); + if (exp < 0) { + out->push_back('-'); + exp = -exp; + } else { + out->push_back('+'); + } + // Exponent digits. + if (exp > 99) { + out->push_back(exp / 100 + '0'); + out->push_back(exp / 10 % 10 + '0'); + out->push_back(exp % 10 + '0'); + } else { + out->push_back(exp / 10 + '0'); + out->push_back(exp % 10 + '0'); + } +} + +template <typename Float, typename Int> +constexpr bool CanFitMantissa() { + return +#if defined(__clang__) && !defined(__SSE3__) + // Workaround for clang bug: https://bugs.llvm.org/show_bug.cgi?id=38289 + // Casting from long double to uint64_t is miscompiled and drops bits. + (!std::is_same<Float, long double>::value || + !std::is_same<Int, uint64_t>::value) && +#endif + std::numeric_limits<Float>::digits <= std::numeric_limits<Int>::digits; +} + +template <typename Float> +struct Decomposed { + Float mantissa; + int exponent; +}; + +// Decompose the double into an integer mantissa and an exponent. +template <typename Float> +Decomposed<Float> Decompose(Float v) { + int exp; + Float m = std::frexp(v, &exp); + m = std::ldexp(m, std::numeric_limits<Float>::digits); + exp -= std::numeric_limits<Float>::digits; + return {m, exp}; +} + +// Print 'digits' as decimal. +// In Fixed mode, we add a '.' at the end. +// In Precision mode, we add a '.' after the first digit. +template <FormatStyle mode, typename Int> +int PrintIntegralDigits(Int digits, Buffer *out) { + int printed = 0; + if (digits) { + for (; digits; digits /= 10) out->push_front(digits % 10 + '0'); + printed = out->size(); + if (mode == FormatStyle::Precision) { + out->push_front(*out->begin); + out->begin[1] = '.'; + } else { + out->push_back('.'); + } + } else if (mode == FormatStyle::Fixed) { + out->push_front('0'); + out->push_back('.'); + printed = 1; + } + return printed; +} + +// Back out 'extra_digits' digits and round up if necessary. +bool RemoveExtraPrecision(int extra_digits, bool has_leftover_value, + Buffer *out, int *exp_out) { + if (extra_digits <= 0) return false; + + // Back out the extra digits + out->end -= extra_digits; + + bool needs_to_round_up = [&] { + // We look at the digit just past the end. + // There must be 'extra_digits' extra valid digits after end. + if (*out->end > '5') return true; + if (*out->end < '5') return false; + if (has_leftover_value || std::any_of(out->end + 1, out->end + extra_digits, + [](char c) { return c != '0'; })) + return true; + + // Ends in ...50*, round to even. + return out->last_digit() % 2 == 1; + }(); + + if (needs_to_round_up) { + RoundUp<FormatStyle::Precision>(out, exp_out); + } + return true; +} + +// Print the value into the buffer. +// This will not include the exponent, which will be returned in 'exp_out' for +// Precision mode. +template <typename Int, typename Float, FormatStyle mode> +bool FloatToBufferImpl(Int int_mantissa, int exp, int precision, Buffer *out, + int *exp_out) { + assert((CanFitMantissa<Float, Int>())); + + const int int_bits = std::numeric_limits<Int>::digits; + + // In precision mode, we start printing one char to the right because it will + // also include the '.' + // In fixed mode we put the dot afterwards on the right. + out->begin = out->end = + out->data + 1 + kMaxFixedPrecision + (mode == FormatStyle::Precision); + + if (exp >= 0) { + if (std::numeric_limits<Float>::digits + exp > int_bits) { + // The value will overflow the Int + return false; + } + int digits_printed = PrintIntegralDigits<mode>(int_mantissa << exp, out); + int digits_to_zero_pad = precision; + if (mode == FormatStyle::Precision) { + *exp_out = digits_printed - 1; + digits_to_zero_pad -= digits_printed - 1; + if (RemoveExtraPrecision(-digits_to_zero_pad, false, out, exp_out)) { + return true; + } + } + for (; digits_to_zero_pad-- > 0;) out->push_back('0'); + return true; + } + + exp = -exp; + // We need at least 4 empty bits for the next decimal digit. + // We will multiply by 10. + if (exp > int_bits - 4) return false; + + const Int mask = (Int{1} << exp) - 1; + + // Print the integral part first. + int digits_printed = PrintIntegralDigits<mode>(int_mantissa >> exp, out); + int_mantissa &= mask; + + int fractional_count = precision; + if (mode == FormatStyle::Precision) { + if (digits_printed == 0) { + // Find the first non-zero digit, when in Precision mode. + *exp_out = 0; + if (int_mantissa) { + while (int_mantissa <= mask) { + int_mantissa *= 10; + --*exp_out; + } + } + out->push_front(static_cast<char>(int_mantissa >> exp) + '0'); + out->push_back('.'); + int_mantissa &= mask; + } else { + // We already have a digit, and a '.' + *exp_out = digits_printed - 1; + fractional_count -= *exp_out; + if (RemoveExtraPrecision(-fractional_count, int_mantissa != 0, out, + exp_out)) { + // If we had enough digits, return right away. + // The code below will try to round again otherwise. + return true; + } + } + } + + auto get_next_digit = [&] { + int_mantissa *= 10; + int digit = static_cast<int>(int_mantissa >> exp); + int_mantissa &= mask; + return digit; + }; + + // Print fractional_count more digits, if available. + for (; fractional_count > 0; --fractional_count) { + out->push_back(get_next_digit() + '0'); + } + + int next_digit = get_next_digit(); + if (next_digit > 5 || + (next_digit == 5 && (int_mantissa || out->last_digit() % 2 == 1))) { + RoundUp<mode>(out, exp_out); + } + + return true; +} + +template <FormatStyle mode, typename Float> +bool FloatToBuffer(Decomposed<Float> decomposed, int precision, Buffer *out, + int *exp) { + if (precision > kMaxFixedPrecision) return false; + + // Try with uint64_t. + if (CanFitMantissa<Float, std::uint64_t>() && + FloatToBufferImpl<std::uint64_t, Float, mode>( + static_cast<std::uint64_t>(decomposed.mantissa), + static_cast<std::uint64_t>(decomposed.exponent), precision, out, exp)) + return true; + +#if defined(__SIZEOF_INT128__) + // If that is not enough, try with __uint128_t. + return CanFitMantissa<Float, __uint128_t>() && + FloatToBufferImpl<__uint128_t, Float, mode>( + static_cast<__uint128_t>(decomposed.mantissa), + static_cast<__uint128_t>(decomposed.exponent), precision, out, + exp); +#endif + return false; +} + +void WriteBufferToSink(char sign_char, string_view str, + const ConversionSpec &conv, FormatSinkImpl *sink) { + int left_spaces = 0, zeros = 0, right_spaces = 0; + int missing_chars = + conv.width() >= 0 ? std::max(conv.width() - static_cast<int>(str.size()) - + static_cast<int>(sign_char != 0), + 0) + : 0; + if (conv.flags().left) { + right_spaces = missing_chars; + } else if (conv.flags().zero) { + zeros = missing_chars; + } else { + left_spaces = missing_chars; + } + + sink->Append(left_spaces, ' '); + if (sign_char) sink->Append(1, sign_char); + sink->Append(zeros, '0'); + sink->Append(str); + sink->Append(right_spaces, ' '); +} + +template <typename Float> +bool FloatToSink(const Float v, const ConversionSpec &conv, + FormatSinkImpl *sink) { + // Print the sign or the sign column. + Float abs_v = v; + char sign_char = 0; + if (std::signbit(abs_v)) { + sign_char = '-'; + abs_v = -abs_v; + } else if (conv.flags().show_pos) { + sign_char = '+'; + } else if (conv.flags().sign_col) { + sign_char = ' '; + } + + // Print nan/inf. + if (ConvertNonNumericFloats(sign_char, abs_v, conv, sink)) { + return true; + } + + int precision = conv.precision() < 0 ? 6 : conv.precision(); + + int exp = 0; + + auto decomposed = Decompose(abs_v); + + Buffer buffer; + + switch (conv.conv().id()) { + case ConversionChar::f: + case ConversionChar::F: + if (!FloatToBuffer<FormatStyle::Fixed>(decomposed, precision, &buffer, + nullptr)) { + return FallbackToSnprintf(v, conv, sink); + } + if (!conv.flags().alt && buffer.back() == '.') buffer.pop_back(); + break; + + case ConversionChar::e: + case ConversionChar::E: + if (!FloatToBuffer<FormatStyle::Precision>(decomposed, precision, &buffer, + &exp)) { + return FallbackToSnprintf(v, conv, sink); + } + if (!conv.flags().alt && buffer.back() == '.') buffer.pop_back(); + PrintExponent(exp, conv.conv().upper() ? 'E' : 'e', &buffer); + break; + + case ConversionChar::g: + case ConversionChar::G: + precision = std::max(0, precision - 1); + if (!FloatToBuffer<FormatStyle::Precision>(decomposed, precision, &buffer, + &exp)) { + return FallbackToSnprintf(v, conv, sink); + } + if (precision + 1 > exp && exp >= -4) { + if (exp < 0) { + // Have 1.23456, needs 0.00123456 + // Move the first digit + buffer.begin[1] = *buffer.begin; + // Add some zeros + for (; exp < -1; ++exp) *buffer.begin-- = '0'; + *buffer.begin-- = '.'; + *buffer.begin = '0'; + } else if (exp > 0) { + // Have 1.23456, needs 1234.56 + // Move the '.' exp positions to the right. + std::rotate(buffer.begin + 1, buffer.begin + 2, + buffer.begin + exp + 2); + } + exp = 0; + } + if (!conv.flags().alt) { + while (buffer.back() == '0') buffer.pop_back(); + if (buffer.back() == '.') buffer.pop_back(); + } + if (exp) PrintExponent(exp, conv.conv().upper() ? 'E' : 'e', &buffer); + break; + + case ConversionChar::a: + case ConversionChar::A: + return FallbackToSnprintf(v, conv, sink); + + default: + return false; + } + + WriteBufferToSink(sign_char, + string_view(buffer.begin, buffer.end - buffer.begin), conv, + sink); + + return true; +} + +} // namespace + +bool ConvertFloatImpl(long double v, const ConversionSpec &conv, + FormatSinkImpl *sink) { + return FloatToSink(v, conv, sink); +} + +bool ConvertFloatImpl(float v, const ConversionSpec &conv, + FormatSinkImpl *sink) { + return FloatToSink(v, conv, sink); +} + +bool ConvertFloatImpl(double v, const ConversionSpec &conv, + FormatSinkImpl *sink) { + return FloatToSink(v, conv, sink); +} + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/float_conversion.h b/absl/strings/internal/str_format/float_conversion.h new file mode 100644 index 00000000..280c471a --- /dev/null +++ b/absl/strings/internal/str_format/float_conversion.h @@ -0,0 +1,23 @@ +#ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_FLOAT_CONVERSION_H_ +#define ABSL_STRINGS_INTERNAL_STR_FORMAT_FLOAT_CONVERSION_H_ + +#include "absl/strings/internal/str_format/extension.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { + +bool ConvertFloatImpl(float v, const ConversionSpec &conv, + FormatSinkImpl *sink); + +bool ConvertFloatImpl(double v, const ConversionSpec &conv, + FormatSinkImpl *sink); + +bool ConvertFloatImpl(long double v, const ConversionSpec &conv, + FormatSinkImpl *sink); + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_STR_FORMAT_FLOAT_CONVERSION_H_ diff --git a/absl/strings/internal/str_format/output.cc b/absl/strings/internal/str_format/output.cc new file mode 100644 index 00000000..010bf341 --- /dev/null +++ b/absl/strings/internal/str_format/output.cc @@ -0,0 +1,72 @@ +// Copyright 2017 The Abseil 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 "absl/strings/internal/str_format/output.h" + +#include <errno.h> +#include <cstring> + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { + +namespace { +struct ClearErrnoGuard { + ClearErrnoGuard() : old_value(errno) { errno = 0; } + ~ClearErrnoGuard() { + if (!errno) errno = old_value; + } + int old_value; +}; +} // namespace + +void BufferRawSink::Write(string_view v) { + size_t to_write = std::min(v.size(), size_); + std::memcpy(buffer_, v.data(), to_write); + buffer_ += to_write; + size_ -= to_write; + total_written_ += v.size(); +} + +void FILERawSink::Write(string_view v) { + while (!v.empty() && !error_) { + // Reset errno to zero in case the libc implementation doesn't set errno + // when a failure occurs. + ClearErrnoGuard guard; + + if (size_t result = std::fwrite(v.data(), 1, v.size(), output_)) { + // Some progress was made. + count_ += result; + v.remove_prefix(result); + } else { + if (errno == EINTR) { + continue; + } else if (errno) { + error_ = errno; + } else if (std::ferror(output_)) { + // Non-POSIX compliant libc implementations may not set errno, so we + // have check the streams error indicator. + error_ = EBADF; + } else { + // We're likely on a non-POSIX system that encountered EINTR but had no + // way of reporting it. + continue; + } + } + } +} + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/output.h b/absl/strings/internal/str_format/output.h new file mode 100644 index 00000000..0f3ab349 --- /dev/null +++ b/absl/strings/internal/str_format/output.h @@ -0,0 +1,103 @@ +// Copyright 2017 The Abseil 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. +// +// Output extension hooks for the Format library. +// `internal::InvokeFlush` calls the appropriate flush function for the +// specified output argument. +// `BufferRawSink` is a simple output sink for a char buffer. Used by SnprintF. +// `FILERawSink` is a std::FILE* based sink. Used by PrintF and FprintF. + +#ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_OUTPUT_H_ +#define ABSL_STRINGS_INTERNAL_STR_FORMAT_OUTPUT_H_ + +#include <cstdio> +#include <ostream> +#include <string> + +#include "absl/base/port.h" +#include "absl/strings/string_view.h" + +class Cord; + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { + +// RawSink implementation that writes into a char* buffer. +// It will not overflow the buffer, but will keep the total count of chars +// that would have been written. +class BufferRawSink { + public: + BufferRawSink(char* buffer, size_t size) : buffer_(buffer), size_(size) {} + + size_t total_written() const { return total_written_; } + void Write(string_view v); + + private: + char* buffer_; + size_t size_; + size_t total_written_ = 0; +}; + +// RawSink implementation that writes into a FILE*. +// It keeps track of the total number of bytes written and any error encountered +// during the writes. +class FILERawSink { + public: + explicit FILERawSink(std::FILE* output) : output_(output) {} + + void Write(string_view v); + + size_t count() const { return count_; } + int error() const { return error_; } + + private: + std::FILE* output_; + int error_ = 0; + size_t count_ = 0; +}; + +// Provide RawSink integration with common types from the STL. +inline void AbslFormatFlush(std::string* out, string_view s) { + out->append(s.data(), s.size()); +} +inline void AbslFormatFlush(std::ostream* out, string_view s) { + out->write(s.data(), s.size()); +} + +template <class AbslCord, typename = typename std::enable_if< + std::is_same<AbslCord, ::Cord>::value>::type> +inline void AbslFormatFlush(AbslCord* out, string_view s) { + out->Append(s); +} + +inline void AbslFormatFlush(FILERawSink* sink, string_view v) { + sink->Write(v); +} + +inline void AbslFormatFlush(BufferRawSink* sink, string_view v) { + sink->Write(v); +} + +template <typename T> +auto InvokeFlush(T* out, string_view s) + -> decltype(str_format_internal::AbslFormatFlush(out, s)) { + str_format_internal::AbslFormatFlush(out, s); +} + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_STR_FORMAT_OUTPUT_H_ diff --git a/absl/strings/internal/str_format/output_test.cc b/absl/strings/internal/str_format/output_test.cc new file mode 100644 index 00000000..0a014cac --- /dev/null +++ b/absl/strings/internal/str_format/output_test.cc @@ -0,0 +1,80 @@ +// Copyright 2017 The Abseil 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 "absl/strings/internal/str_format/output.h" + +#include <sstream> +#include <string> + + +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace { + +TEST(InvokeFlush, String) { + std::string str = "ABC"; + str_format_internal::InvokeFlush(&str, "DEF"); + EXPECT_EQ(str, "ABCDEF"); + +#if UTIL_FORMAT_HAS_GLOBAL_STRING + std::string str2 = "ABC"; + str_format_internal::InvokeFlush(&str2, "DEF"); + EXPECT_EQ(str2, "ABCDEF"); +#endif // UTIL_FORMAT_HAS_GLOBAL_STRING +} + +TEST(InvokeFlush, Stream) { + std::stringstream str; + str << "ABC"; + str_format_internal::InvokeFlush(&str, "DEF"); + EXPECT_EQ(str.str(), "ABCDEF"); +} + +TEST(BufferRawSink, Limits) { + char buf[16]; + { + std::fill(std::begin(buf), std::end(buf), 'x'); + str_format_internal::BufferRawSink bufsink(buf, sizeof(buf) - 1); + str_format_internal::InvokeFlush(&bufsink, "Hello World237"); + EXPECT_EQ(std::string(buf, sizeof(buf)), "Hello World237xx"); + } + { + std::fill(std::begin(buf), std::end(buf), 'x'); + str_format_internal::BufferRawSink bufsink(buf, sizeof(buf) - 1); + str_format_internal::InvokeFlush(&bufsink, "Hello World237237"); + EXPECT_EQ(std::string(buf, sizeof(buf)), "Hello World2372x"); + } + { + std::fill(std::begin(buf), std::end(buf), 'x'); + str_format_internal::BufferRawSink bufsink(buf, sizeof(buf) - 1); + str_format_internal::InvokeFlush(&bufsink, "Hello World"); + str_format_internal::InvokeFlush(&bufsink, "237"); + EXPECT_EQ(std::string(buf, sizeof(buf)), "Hello World237xx"); + } + { + std::fill(std::begin(buf), std::end(buf), 'x'); + str_format_internal::BufferRawSink bufsink(buf, sizeof(buf) - 1); + str_format_internal::InvokeFlush(&bufsink, "Hello World"); + str_format_internal::InvokeFlush(&bufsink, "237237"); + EXPECT_EQ(std::string(buf, sizeof(buf)), "Hello World2372x"); + } +} + +} // namespace +} // inline namespace lts_2018_12_18 +} // namespace absl + diff --git a/absl/strings/internal/str_format/parser.cc b/absl/strings/internal/str_format/parser.cc new file mode 100644 index 00000000..119a711e --- /dev/null +++ b/absl/strings/internal/str_format/parser.cc @@ -0,0 +1,311 @@ +#include "absl/strings/internal/str_format/parser.h" + +#include <assert.h> +#include <string.h> +#include <wchar.h> +#include <cctype> +#include <cstdint> + +#include <algorithm> +#include <initializer_list> +#include <limits> +#include <ostream> +#include <string> +#include <unordered_set> + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { +namespace { + +bool CheckFastPathSetting(const UnboundConversion& conv) { + bool should_be_basic = !conv.flags.left && // + !conv.flags.show_pos && // + !conv.flags.sign_col && // + !conv.flags.alt && // + !conv.flags.zero && // + (conv.width.value() == -1) && + (conv.precision.value() == -1); + if (should_be_basic != conv.flags.basic) { + fprintf(stderr, + "basic=%d left=%d show_pos=%d sign_col=%d alt=%d zero=%d " + "width=%d precision=%d\n", + conv.flags.basic, conv.flags.left, conv.flags.show_pos, + conv.flags.sign_col, conv.flags.alt, conv.flags.zero, + conv.width.value(), conv.precision.value()); + } + return should_be_basic == conv.flags.basic; +} + +// Keep a single table for all the conversion chars and length modifiers. +// We invert the length modifiers to make them negative so that we can easily +// test for them. +// Everything else is `none`, which is a negative constant. +using CC = ConversionChar::Id; +using LM = LengthMod::Id; +static constexpr std::int8_t none = -128; +static constexpr std::int8_t kIds[] = { + none, none, none, none, none, none, none, none, // 00-07 + none, none, none, none, none, none, none, none, // 08-0f + none, none, none, none, none, none, none, none, // 10-17 + none, none, none, none, none, none, none, none, // 18-1f + none, none, none, none, none, none, none, none, // 20-27 + none, none, none, none, none, none, none, none, // 28-2f + none, none, none, none, none, none, none, none, // 30-37 + none, none, none, none, none, none, none, none, // 38-3f + none, CC::A, none, CC::C, none, CC::E, CC::F, CC::G, // @ABCDEFG + none, none, none, none, ~LM::L, none, none, none, // HIJKLMNO + none, none, none, CC::S, none, none, none, none, // PQRSTUVW + CC::X, none, none, none, none, none, none, none, // XYZ[\]^_ + none, CC::a, none, CC::c, CC::d, CC::e, CC::f, CC::g, // `abcdefg + ~LM::h, CC::i, ~LM::j, none, ~LM::l, none, CC::n, CC::o, // hijklmno + CC::p, ~LM::q, none, CC::s, ~LM::t, CC::u, none, none, // pqrstuvw + CC::x, none, ~LM::z, none, none, none, none, none, // xyz{|}~! + none, none, none, none, none, none, none, none, // 80-87 + none, none, none, none, none, none, none, none, // 88-8f + none, none, none, none, none, none, none, none, // 90-97 + none, none, none, none, none, none, none, none, // 98-9f + none, none, none, none, none, none, none, none, // a0-a7 + none, none, none, none, none, none, none, none, // a8-af + none, none, none, none, none, none, none, none, // b0-b7 + none, none, none, none, none, none, none, none, // b8-bf + none, none, none, none, none, none, none, none, // c0-c7 + none, none, none, none, none, none, none, none, // c8-cf + none, none, none, none, none, none, none, none, // d0-d7 + none, none, none, none, none, none, none, none, // d8-df + none, none, none, none, none, none, none, none, // e0-e7 + none, none, none, none, none, none, none, none, // e8-ef + none, none, none, none, none, none, none, none, // f0-f7 + none, none, none, none, none, none, none, none, // f8-ff +}; + +template <bool is_positional> +bool ConsumeConversion(string_view *src, UnboundConversion *conv, + int *next_arg) { + const char *pos = src->data(); + const char *const end = pos + src->size(); + char c; + // Read the next char into `c` and update `pos`. Returns false if there are + // no more chars to read. +#define ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR() \ + do { \ + if (ABSL_PREDICT_FALSE(pos == end)) return false; \ + c = *pos++; \ + } while (0) + + const auto parse_digits = [&] { + int digits = c - '0'; + // We do not want to overflow `digits` so we consume at most digits10 + // digits. If there are more digits the parsing will fail later on when the + // digit doesn't match the expected characters. + int num_digits = std::numeric_limits<int>::digits10; + for (;;) { + if (ABSL_PREDICT_FALSE(pos == end || !num_digits)) break; + c = *pos++; + if (!std::isdigit(c)) break; + --num_digits; + digits = 10 * digits + c - '0'; + } + return digits; + }; + + if (is_positional) { + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + if (ABSL_PREDICT_FALSE(c < '1' || c > '9')) return false; + conv->arg_position = parse_digits(); + assert(conv->arg_position > 0); + if (ABSL_PREDICT_FALSE(c != '$')) return false; + } + + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + + // We should start with the basic flag on. + assert(conv->flags.basic); + + // Any non alpha character makes this conversion not basic. + // This includes flags (-+ #0), width (1-9, *) or precision (.). + // All conversion characters and length modifiers are alpha characters. + if (c < 'A') { + conv->flags.basic = false; + + for (; c <= '0';) { + // FIXME: We might be able to speed this up reusing the kIds lookup table + // from above. + // It might require changing Flags to be a plain integer where we can |= a + // value. + switch (c) { + case '-': + conv->flags.left = true; + break; + case '+': + conv->flags.show_pos = true; + break; + case ' ': + conv->flags.sign_col = true; + break; + case '#': + conv->flags.alt = true; + break; + case '0': + conv->flags.zero = true; + break; + default: + goto flags_done; + } + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + } +flags_done: + + if (c <= '9') { + if (c >= '0') { + int maybe_width = parse_digits(); + if (!is_positional && c == '$') { + if (ABSL_PREDICT_FALSE(*next_arg != 0)) return false; + // Positional conversion. + *next_arg = -1; + conv->flags = Flags(); + conv->flags.basic = true; + return ConsumeConversion<true>(src, conv, next_arg); + } + conv->width.set_value(maybe_width); + } else if (c == '*') { + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + if (is_positional) { + if (ABSL_PREDICT_FALSE(c < '1' || c > '9')) return false; + conv->width.set_from_arg(parse_digits()); + if (ABSL_PREDICT_FALSE(c != '$')) return false; + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + } else { + conv->width.set_from_arg(++*next_arg); + } + } + } + + if (c == '.') { + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + if (std::isdigit(c)) { + conv->precision.set_value(parse_digits()); + } else if (c == '*') { + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + if (is_positional) { + if (ABSL_PREDICT_FALSE(c < '1' || c > '9')) return false; + conv->precision.set_from_arg(parse_digits()); + if (c != '$') return false; + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + } else { + conv->precision.set_from_arg(++*next_arg); + } + } else { + conv->precision.set_value(0); + } + } + } + + std::int8_t id = kIds[static_cast<unsigned char>(c)]; + + if (id < 0) { + if (ABSL_PREDICT_FALSE(id == none)) return false; + + // It is a length modifier. + using str_format_internal::LengthMod; + LengthMod length_mod = LengthMod::FromId(static_cast<LM>(~id)); + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + if (c == 'h' && length_mod.id() == LengthMod::h) { + conv->length_mod = LengthMod::FromId(LengthMod::hh); + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + } else if (c == 'l' && length_mod.id() == LengthMod::l) { + conv->length_mod = LengthMod::FromId(LengthMod::ll); + ABSL_FORMAT_PARSER_INTERNAL_GET_CHAR(); + } else { + conv->length_mod = length_mod; + } + id = kIds[static_cast<unsigned char>(c)]; + if (ABSL_PREDICT_FALSE(id < 0)) return false; + } + + assert(CheckFastPathSetting(*conv)); + (void)(&CheckFastPathSetting); + + conv->conv = ConversionChar::FromId(static_cast<CC>(id)); + if (!is_positional) conv->arg_position = ++*next_arg; + *src = string_view(pos, end - pos); + return true; +} + +} // namespace + +bool ConsumeUnboundConversion(string_view *src, UnboundConversion *conv, + int *next_arg) { + if (*next_arg < 0) return ConsumeConversion<true>(src, conv, next_arg); + return ConsumeConversion<false>(src, conv, next_arg); +} + +struct ParsedFormatBase::ParsedFormatConsumer { + explicit ParsedFormatConsumer(ParsedFormatBase *parsedformat) + : parsed(parsedformat), data_pos(parsedformat->data_.get()) {} + + bool Append(string_view s) { + if (s.empty()) return true; + + size_t text_end = AppendText(s); + + if (!parsed->items_.empty() && !parsed->items_.back().is_conversion) { + // Let's extend the existing text run. + parsed->items_.back().text_end = text_end; + } else { + // Let's make a new text run. + parsed->items_.push_back({false, text_end, {}}); + } + return true; + } + + bool ConvertOne(const UnboundConversion &conv, string_view s) { + size_t text_end = AppendText(s); + parsed->items_.push_back({true, text_end, conv}); + return true; + } + + size_t AppendText(string_view s) { + memcpy(data_pos, s.data(), s.size()); + data_pos += s.size(); + return static_cast<size_t>(data_pos - parsed->data_.get()); + } + + ParsedFormatBase *parsed; + char* data_pos; +}; + +ParsedFormatBase::ParsedFormatBase(string_view format, bool allow_ignored, + std::initializer_list<Conv> convs) + : data_(format.empty() ? nullptr : new char[format.size()]) { + has_error_ = !ParseFormatString(format, ParsedFormatConsumer(this)) || + !MatchesConversions(allow_ignored, convs); +} + +bool ParsedFormatBase::MatchesConversions( + bool allow_ignored, std::initializer_list<Conv> convs) const { + std::unordered_set<int> used; + auto add_if_valid_conv = [&](int pos, char c) { + if (static_cast<size_t>(pos) > convs.size() || + !Contains(convs.begin()[pos - 1], c)) + return false; + used.insert(pos); + return true; + }; + for (const ConversionItem &item : items_) { + if (!item.is_conversion) continue; + auto &conv = item.conv; + if (conv.precision.is_from_arg() && + !add_if_valid_conv(conv.precision.get_from_arg(), '*')) + return false; + if (conv.width.is_from_arg() && + !add_if_valid_conv(conv.width.get_from_arg(), '*')) + return false; + if (!add_if_valid_conv(conv.arg_position, conv.conv.Char())) return false; + } + return used.size() == convs.size() || allow_ignored; +} + +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_format/parser.h b/absl/strings/internal/str_format/parser.h new file mode 100644 index 00000000..9842c117 --- /dev/null +++ b/absl/strings/internal/str_format/parser.h @@ -0,0 +1,294 @@ +#ifndef ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_ +#define ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_ + +#include <limits.h> +#include <stddef.h> +#include <stdlib.h> + +#include <cassert> +#include <initializer_list> +#include <iosfwd> +#include <iterator> +#include <memory> +#include <vector> + +#include "absl/strings/internal/str_format/checker.h" +#include "absl/strings/internal/str_format/extension.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { + +// The analyzed properties of a single specified conversion. +struct UnboundConversion { + UnboundConversion() + : flags() /* This is required to zero all the fields of flags. */ { + flags.basic = true; + } + + class InputValue { + public: + void set_value(int value) { + assert(value >= 0); + value_ = value; + } + int value() const { return value_; } + + // Marks the value as "from arg". aka the '*' format. + // Requires `value >= 1`. + // When set, is_from_arg() return true and get_from_arg() returns the + // original value. + // `value()`'s return value is unspecfied in this state. + void set_from_arg(int value) { + assert(value > 0); + value_ = -value - 1; + } + bool is_from_arg() const { return value_ < -1; } + int get_from_arg() const { + assert(is_from_arg()); + return -value_ - 1; + } + + private: + int value_ = -1; + }; + + // No need to initialize. It will always be set in the parser. + int arg_position; + + InputValue width; + InputValue precision; + + Flags flags; + LengthMod length_mod; + ConversionChar conv; +}; + +// Consume conversion spec prefix (not including '%') of '*src' if valid. +// Examples of valid specs would be e.g.: "s", "d", "-12.6f". +// If valid, the front of src is advanced such that src becomes the +// part following the conversion spec, and the spec part is broken down and +// returned in 'conv'. +// If invalid, returns false and leaves 'src' unmodified. +// For example: +// Given "d9", returns "d", and leaves src="9", +// Given "!", returns "" and leaves src="!". +bool ConsumeUnboundConversion(string_view* src, UnboundConversion* conv, + int* next_arg); + +// Parse the format string provided in 'src' and pass the identified items into +// 'consumer'. +// Text runs will be passed by calling +// Consumer::Append(string_view); +// ConversionItems will be passed by calling +// Consumer::ConvertOne(UnboundConversion, string_view); +// In the case of ConvertOne, the string_view that is passed is the +// portion of the format string corresponding to the conversion, not including +// the leading %. On success, it returns true. On failure, it stops and returns +// false. +template <typename Consumer> +bool ParseFormatString(string_view src, Consumer consumer) { + int next_arg = 0; + while (!src.empty()) { + const char* percent = + static_cast<const char*>(memchr(src.data(), '%', src.size())); + if (!percent) { + // We found the last substring. + return consumer.Append(src); + } + // We found a percent, so push the text run then process the percent. + size_t percent_loc = percent - src.data(); + if (!consumer.Append(string_view(src.data(), percent_loc))) return false; + if (percent + 1 >= src.data() + src.size()) return false; + + UnboundConversion conv; + + switch (percent[1]) { + case '%': + if (!consumer.Append("%")) return false; + src.remove_prefix(percent_loc + 2); + continue; + +#define PARSER_CASE(ch) \ + case #ch[0]: \ + src.remove_prefix(percent_loc + 2); \ + conv.conv = ConversionChar::FromId(ConversionChar::ch); \ + conv.arg_position = ++next_arg; \ + break; + ABSL_CONVERSION_CHARS_EXPAND_(PARSER_CASE, ); +#undef PARSER_CASE + + default: + src.remove_prefix(percent_loc + 1); + if (!ConsumeUnboundConversion(&src, &conv, &next_arg)) return false; + break; + } + if (next_arg == 0) { + // This indicates an error in the format std::string. + // The only way to get next_arg == 0 is to have a positional argument + // first which sets next_arg to -1 and then a non-positional argument + // which does ++next_arg. + // Checking here seems to be the cheapeast place to do it. + return false; + } + if (!consumer.ConvertOne( + conv, string_view(percent + 1, src.data() - (percent + 1)))) { + return false; + } + } + return true; +} + +// Always returns true, or fails to compile in a constexpr context if s does not +// point to a constexpr char array. +constexpr bool EnsureConstexpr(string_view s) { + return s.empty() || s[0] == s[0]; +} + +class ParsedFormatBase { + public: + explicit ParsedFormatBase(string_view format, bool allow_ignored, + std::initializer_list<Conv> convs); + + ParsedFormatBase(const ParsedFormatBase& other) { *this = other; } + + ParsedFormatBase(ParsedFormatBase&& other) { *this = std::move(other); } + + ParsedFormatBase& operator=(const ParsedFormatBase& other) { + if (this == &other) return *this; + has_error_ = other.has_error_; + items_ = other.items_; + size_t text_size = items_.empty() ? 0 : items_.back().text_end; + data_.reset(new char[text_size]); + memcpy(data_.get(), other.data_.get(), text_size); + return *this; + } + + ParsedFormatBase& operator=(ParsedFormatBase&& other) { + if (this == &other) return *this; + has_error_ = other.has_error_; + data_ = std::move(other.data_); + items_ = std::move(other.items_); + // Reset the vector to make sure the invariants hold. + other.items_.clear(); + return *this; + } + + template <typename Consumer> + bool ProcessFormat(Consumer consumer) const { + const char* const base = data_.get(); + string_view text(base, 0); + for (const auto& item : items_) { + const char* const end = text.data() + text.size(); + text = string_view(end, (base + item.text_end) - end); + if (item.is_conversion) { + if (!consumer.ConvertOne(item.conv, text)) return false; + } else { + if (!consumer.Append(text)) return false; + } + } + return !has_error_; + } + + bool has_error() const { return has_error_; } + + private: + // Returns whether the conversions match and if !allow_ignored it verifies + // that all conversions are used by the format. + bool MatchesConversions(bool allow_ignored, + std::initializer_list<Conv> convs) const; + + struct ParsedFormatConsumer; + + struct ConversionItem { + bool is_conversion; + // Points to the past-the-end location of this element in the data_ array. + size_t text_end; + UnboundConversion conv; + }; + + bool has_error_; + std::unique_ptr<char[]> data_; + std::vector<ConversionItem> items_; +}; + + +// A value type representing a preparsed format. These can be created, copied +// around, and reused to speed up formatting loops. +// The user must specify through the template arguments the conversion +// characters used in the format. This will be checked at compile time. +// +// This class uses Conv enum values to specify each argument. +// This allows for more flexibility as you can specify multiple possible +// conversion characters for each argument. +// ParsedFormat<char...> is a simplified alias for when the user only +// needs to specify a single conversion character for each argument. +// +// Example: +// // Extended format supports multiple characters per argument: +// using MyFormat = ExtendedParsedFormat<Conv::d | Conv::x>; +// MyFormat GetFormat(bool use_hex) { +// if (use_hex) return MyFormat("foo %x bar"); +// return MyFormat("foo %d bar"); +// } +// // 'format' can be used with any value that supports 'd' and 'x', +// // like `int`. +// auto format = GetFormat(use_hex); +// value = StringF(format, i); +// +// This class also supports runtime format checking with the ::New() and +// ::NewAllowIgnored() factory functions. +// This is the only API that allows the user to pass a runtime specified format +// string. These factory functions will return NULL if the format does not match +// the conversions requested by the user. +template <str_format_internal::Conv... C> +class ExtendedParsedFormat : public str_format_internal::ParsedFormatBase { + public: + explicit ExtendedParsedFormat(string_view format) +#if ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + __attribute__(( + enable_if(str_format_internal::EnsureConstexpr(format), + "Format std::string is not constexpr."), + enable_if(str_format_internal::ValidFormatImpl<C...>(format), + "Format specified does not match the template arguments."))) +#endif // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER + : ExtendedParsedFormat(format, false) { + } + + // ExtendedParsedFormat factory function. + // The user still has to specify the conversion characters, but they will not + // be checked at compile time. Instead, it will be checked at runtime. + // This delays the checking to runtime, but allows the user to pass + // dynamically sourced formats. + // It returns NULL if the format does not match the conversion characters. + // The user is responsible for checking the return value before using it. + // + // The 'New' variant will check that all the specified arguments are being + // consumed by the format and return NULL if any argument is being ignored. + // The 'NewAllowIgnored' variant will not verify this and will allow formats + // that ignore arguments. + static std::unique_ptr<ExtendedParsedFormat> New(string_view format) { + return New(format, false); + } + static std::unique_ptr<ExtendedParsedFormat> NewAllowIgnored( + string_view format) { + return New(format, true); + } + + private: + static std::unique_ptr<ExtendedParsedFormat> New(string_view format, + bool allow_ignored) { + std::unique_ptr<ExtendedParsedFormat> conv( + new ExtendedParsedFormat(format, allow_ignored)); + if (conv->has_error()) return nullptr; + return conv; + } + + ExtendedParsedFormat(string_view s, bool allow_ignored) + : ParsedFormatBase(s, allow_ignored, {C...}) {} +}; +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_STR_FORMAT_PARSER_H_ diff --git a/absl/strings/internal/str_format/parser_test.cc b/absl/strings/internal/str_format/parser_test.cc new file mode 100644 index 00000000..14d90344 --- /dev/null +++ b/absl/strings/internal/str_format/parser_test.cc @@ -0,0 +1,391 @@ +#include "absl/strings/internal/str_format/parser.h" + +#include <string.h> +#include "gtest/gtest.h" +#include "absl/base/macros.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace str_format_internal { + +namespace { + +TEST(LengthModTest, Names) { + struct Expectation { + int line; + LengthMod::Id id; + const char *name; + }; + const Expectation kExpect[] = { + {__LINE__, LengthMod::none, "" }, + {__LINE__, LengthMod::h, "h" }, + {__LINE__, LengthMod::hh, "hh"}, + {__LINE__, LengthMod::l, "l" }, + {__LINE__, LengthMod::ll, "ll"}, + {__LINE__, LengthMod::L, "L" }, + {__LINE__, LengthMod::j, "j" }, + {__LINE__, LengthMod::z, "z" }, + {__LINE__, LengthMod::t, "t" }, + {__LINE__, LengthMod::q, "q" }, + }; + EXPECT_EQ(ABSL_ARRAYSIZE(kExpect), LengthMod::kNumValues); + for (auto e : kExpect) { + SCOPED_TRACE(e.line); + LengthMod mod = LengthMod::FromId(e.id); + EXPECT_EQ(e.id, mod.id()); + EXPECT_EQ(e.name, mod.name()); + } +} + +TEST(ConversionCharTest, Names) { + struct Expectation { + ConversionChar::Id id; + char name; + }; + // clang-format off + const Expectation kExpect[] = { +#define X(c) {ConversionChar::c, #c[0]} + X(c), X(C), X(s), X(S), // text + X(d), X(i), X(o), X(u), X(x), X(X), // int + X(f), X(F), X(e), X(E), X(g), X(G), X(a), X(A), // float + X(n), X(p), // misc +#undef X + {ConversionChar::none, '\0'}, + }; + // clang-format on + EXPECT_EQ(ABSL_ARRAYSIZE(kExpect), ConversionChar::kNumValues); + for (auto e : kExpect) { + SCOPED_TRACE(e.name); + ConversionChar v = ConversionChar::FromId(e.id); + EXPECT_EQ(e.id, v.id()); + EXPECT_EQ(e.name, v.Char()); + } +} + +class ConsumeUnboundConversionTest : public ::testing::Test { + public: + typedef UnboundConversion Props; + string_view Consume(string_view* src) { + int next = 0; + const char* prev_begin = src->data(); + o = UnboundConversion(); // refresh + ConsumeUnboundConversion(src, &o, &next); + return {prev_begin, static_cast<size_t>(src->data() - prev_begin)}; + } + + bool Run(const char *fmt, bool force_positional = false) { + string_view src = fmt; + int next = force_positional ? -1 : 0; + o = UnboundConversion(); // refresh + return ConsumeUnboundConversion(&src, &o, &next) && src.empty(); + } + UnboundConversion o; +}; + +TEST_F(ConsumeUnboundConversionTest, ConsumeSpecification) { + struct Expectation { + int line; + string_view src; + string_view out; + string_view src_post; + }; + const Expectation kExpect[] = { + {__LINE__, "", "", "" }, + {__LINE__, "b", "", "b" }, // 'b' is invalid + {__LINE__, "ba", "", "ba"}, // 'b' is invalid + {__LINE__, "l", "", "l" }, // just length mod isn't okay + {__LINE__, "d", "d", "" }, // basic + {__LINE__, "d ", "d", " " }, // leave suffix + {__LINE__, "dd", "d", "d" }, // don't be greedy + {__LINE__, "d9", "d", "9" }, // leave non-space suffix + {__LINE__, "dzz", "d", "zz"}, // length mod as suffix + {__LINE__, "1$*2$d", "1$*2$d", "" }, // arg indexing and * allowed. + {__LINE__, "0-14.3hhd", "0-14.3hhd", ""}, // precision, width + {__LINE__, " 0-+#14.3hhd", " 0-+#14.3hhd", ""}, // flags + }; + for (const auto& e : kExpect) { + SCOPED_TRACE(e.line); + string_view src = e.src; + EXPECT_EQ(e.src, src); + string_view out = Consume(&src); + EXPECT_EQ(e.out, out); + EXPECT_EQ(e.src_post, src); + } +} + +TEST_F(ConsumeUnboundConversionTest, BasicConversion) { + EXPECT_FALSE(Run("")); + EXPECT_FALSE(Run("z")); + + EXPECT_FALSE(Run("dd")); // no excess allowed + + EXPECT_TRUE(Run("d")); + EXPECT_EQ('d', o.conv.Char()); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_LT(o.width.value(), 0); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_LT(o.precision.value(), 0); + EXPECT_EQ(1, o.arg_position); + EXPECT_EQ(LengthMod::none, o.length_mod.id()); +} + +TEST_F(ConsumeUnboundConversionTest, ArgPosition) { + EXPECT_TRUE(Run("d")); + EXPECT_EQ(1, o.arg_position); + EXPECT_TRUE(Run("3$d")); + EXPECT_EQ(3, o.arg_position); + EXPECT_TRUE(Run("1$d")); + EXPECT_EQ(1, o.arg_position); + EXPECT_TRUE(Run("1$d", true)); + EXPECT_EQ(1, o.arg_position); + EXPECT_TRUE(Run("123$d")); + EXPECT_EQ(123, o.arg_position); + EXPECT_TRUE(Run("123$d", true)); + EXPECT_EQ(123, o.arg_position); + EXPECT_TRUE(Run("10$d")); + EXPECT_EQ(10, o.arg_position); + EXPECT_TRUE(Run("10$d", true)); + EXPECT_EQ(10, o.arg_position); + + // Position can't be zero. + EXPECT_FALSE(Run("0$d")); + EXPECT_FALSE(Run("0$d", true)); + EXPECT_FALSE(Run("1$*0$d")); + EXPECT_FALSE(Run("1$.*0$d")); + + // Position can't start with a zero digit at all. That is not a 'decimal'. + EXPECT_FALSE(Run("01$p")); + EXPECT_FALSE(Run("01$p", true)); + EXPECT_FALSE(Run("1$*01$p")); + EXPECT_FALSE(Run("1$.*01$p")); +} + +TEST_F(ConsumeUnboundConversionTest, WidthAndPrecision) { + EXPECT_TRUE(Run("14d")); + EXPECT_EQ('d', o.conv.Char()); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_EQ(14, o.width.value()); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_LT(o.precision.value(), 0); + + EXPECT_TRUE(Run("14.d")); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_EQ(14, o.width.value()); + EXPECT_EQ(0, o.precision.value()); + + EXPECT_TRUE(Run(".d")); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_LT(o.width.value(), 0); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_EQ(0, o.precision.value()); + + EXPECT_TRUE(Run(".5d")); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_LT(o.width.value(), 0); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_EQ(5, o.precision.value()); + + EXPECT_TRUE(Run(".0d")); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_LT(o.width.value(), 0); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_EQ(0, o.precision.value()); + + EXPECT_TRUE(Run("14.5d")); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_EQ(14, o.width.value()); + EXPECT_EQ(5, o.precision.value()); + + EXPECT_TRUE(Run("*.*d")); + EXPECT_TRUE(o.width.is_from_arg()); + EXPECT_EQ(1, o.width.get_from_arg()); + EXPECT_TRUE(o.precision.is_from_arg()); + EXPECT_EQ(2, o.precision.get_from_arg()); + EXPECT_EQ(3, o.arg_position); + + EXPECT_TRUE(Run("*d")); + EXPECT_TRUE(o.width.is_from_arg()); + EXPECT_EQ(1, o.width.get_from_arg()); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_LT(o.precision.value(), 0); + EXPECT_EQ(2, o.arg_position); + + EXPECT_TRUE(Run(".*d")); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_LT(o.width.value(), 0); + EXPECT_TRUE(o.precision.is_from_arg()); + EXPECT_EQ(1, o.precision.get_from_arg()); + EXPECT_EQ(2, o.arg_position); + + // mixed implicit and explicit: didn't specify arg position. + EXPECT_FALSE(Run("*23$.*34$d")); + + EXPECT_TRUE(Run("12$*23$.*34$d")); + EXPECT_EQ(12, o.arg_position); + EXPECT_TRUE(o.width.is_from_arg()); + EXPECT_EQ(23, o.width.get_from_arg()); + EXPECT_TRUE(o.precision.is_from_arg()); + EXPECT_EQ(34, o.precision.get_from_arg()); + + EXPECT_TRUE(Run("2$*5$.*9$d")); + EXPECT_EQ(2, o.arg_position); + EXPECT_TRUE(o.width.is_from_arg()); + EXPECT_EQ(5, o.width.get_from_arg()); + EXPECT_TRUE(o.precision.is_from_arg()); + EXPECT_EQ(9, o.precision.get_from_arg()); + + EXPECT_FALSE(Run(".*0$d")) << "no arg 0"; + + // Large values + EXPECT_TRUE(Run("999999999.999999999d")); + EXPECT_FALSE(o.width.is_from_arg()); + EXPECT_EQ(999999999, o.width.value()); + EXPECT_FALSE(o.precision.is_from_arg()); + EXPECT_EQ(999999999, o.precision.value()); + + EXPECT_FALSE(Run("1000000000.999999999d")); + EXPECT_FALSE(Run("999999999.1000000000d")); +} + +TEST_F(ConsumeUnboundConversionTest, Flags) { + static const char kAllFlags[] = "-+ #0"; + static const int kNumFlags = ABSL_ARRAYSIZE(kAllFlags) - 1; + for (int rev = 0; rev < 2; ++rev) { + for (int i = 0; i < 1 << kNumFlags; ++i) { + std::string fmt; + for (int k = 0; k < kNumFlags; ++k) + if ((i >> k) & 1) fmt += kAllFlags[k]; + // flag order shouldn't matter + if (rev == 1) { std::reverse(fmt.begin(), fmt.end()); } + fmt += 'd'; + SCOPED_TRACE(fmt); + EXPECT_TRUE(Run(fmt.c_str())); + EXPECT_EQ(fmt.find('-') == std::string::npos, !o.flags.left); + EXPECT_EQ(fmt.find('+') == std::string::npos, !o.flags.show_pos); + EXPECT_EQ(fmt.find(' ') == std::string::npos, !o.flags.sign_col); + EXPECT_EQ(fmt.find('#') == std::string::npos, !o.flags.alt); + EXPECT_EQ(fmt.find('0') == std::string::npos, !o.flags.zero); + } + } +} + +TEST_F(ConsumeUnboundConversionTest, BasicFlag) { + // Flag is on + for (const char* fmt : {"d", "llx", "G", "1$X"}) { + SCOPED_TRACE(fmt); + EXPECT_TRUE(Run(fmt)); + EXPECT_TRUE(o.flags.basic); + } + + // Flag is off + for (const char* fmt : {"3d", ".llx", "-G", "1$#X"}) { + SCOPED_TRACE(fmt); + EXPECT_TRUE(Run(fmt)); + EXPECT_FALSE(o.flags.basic); + } +} + +struct SummarizeConsumer { + std::string* out; + explicit SummarizeConsumer(std::string* out) : out(out) {} + + bool Append(string_view s) { + *out += "[" + std::string(s) + "]"; + return true; + } + + bool ConvertOne(const UnboundConversion& conv, string_view s) { + *out += "{"; + *out += std::string(s); + *out += ":"; + *out += std::to_string(conv.arg_position) + "$"; + if (conv.width.is_from_arg()) { + *out += std::to_string(conv.width.get_from_arg()) + "$*"; + } + if (conv.precision.is_from_arg()) { + *out += "." + std::to_string(conv.precision.get_from_arg()) + "$*"; + } + *out += conv.conv.Char(); + *out += "}"; + return true; + } +}; + +std::string SummarizeParsedFormat(const ParsedFormatBase& pc) { + std::string out; + if (!pc.ProcessFormat(SummarizeConsumer(&out))) out += "!"; + return out; +} + +class ParsedFormatTest : public testing::Test {}; + +TEST_F(ParsedFormatTest, ValueSemantics) { + ParsedFormatBase p1({}, true, {}); // empty format + EXPECT_EQ("", SummarizeParsedFormat(p1)); + + ParsedFormatBase p2 = p1; // copy construct (empty) + EXPECT_EQ(SummarizeParsedFormat(p1), SummarizeParsedFormat(p2)); + + p1 = ParsedFormatBase("hello%s", true, {Conv::s}); // move assign + EXPECT_EQ("[hello]{s:1$s}", SummarizeParsedFormat(p1)); + + ParsedFormatBase p3 = p1; // copy construct (nonempty) + EXPECT_EQ(SummarizeParsedFormat(p1), SummarizeParsedFormat(p3)); + + using std::swap; + swap(p1, p2); + EXPECT_EQ("", SummarizeParsedFormat(p1)); + EXPECT_EQ("[hello]{s:1$s}", SummarizeParsedFormat(p2)); + swap(p1, p2); // undo + + p2 = p1; // copy assign + EXPECT_EQ(SummarizeParsedFormat(p1), SummarizeParsedFormat(p2)); +} + +struct ExpectParse { + const char* in; + std::initializer_list<Conv> conv_set; + const char* out; +}; + +TEST_F(ParsedFormatTest, Parsing) { + // Parse should be equivalent to that obtained by ConversionParseIterator. + // No need to retest the parsing edge cases here. + const ExpectParse kExpect[] = { + {"", {}, ""}, + {"ab", {}, "[ab]"}, + {"a%d", {Conv::d}, "[a]{d:1$d}"}, + {"a%+d", {Conv::d}, "[a]{+d:1$d}"}, + {"a% d", {Conv::d}, "[a]{ d:1$d}"}, + {"a%b %d", {}, "[a]!"}, // stop after error + }; + for (const auto& e : kExpect) { + SCOPED_TRACE(e.in); + EXPECT_EQ(e.out, + SummarizeParsedFormat(ParsedFormatBase(e.in, false, e.conv_set))); + } +} + +TEST_F(ParsedFormatTest, ParsingFlagOrder) { + const ExpectParse kExpect[] = { + {"a%+ 0d", {Conv::d}, "[a]{+ 0d:1$d}"}, + {"a%+0 d", {Conv::d}, "[a]{+0 d:1$d}"}, + {"a%0+ d", {Conv::d}, "[a]{0+ d:1$d}"}, + {"a% +0d", {Conv::d}, "[a]{ +0d:1$d}"}, + {"a%0 +d", {Conv::d}, "[a]{0 +d:1$d}"}, + {"a% 0+d", {Conv::d}, "[a]{ 0+d:1$d}"}, + {"a%+ 0+d", {Conv::d}, "[a]{+ 0+d:1$d}"}, + }; + for (const auto& e : kExpect) { + SCOPED_TRACE(e.in); + EXPECT_EQ(e.out, + SummarizeParsedFormat(ParsedFormatBase(e.in, false, e.conv_set))); + } +} + +} // namespace +} // namespace str_format_internal +} // inline namespace lts_2018_12_18 +} // namespace absl diff --git a/absl/strings/internal/str_join_internal.h b/absl/strings/internal/str_join_internal.h index 5834403e..90b06d6f 100644 --- a/absl/strings/internal/str_join_internal.h +++ b/absl/strings/internal/str_join_internal.h @@ -43,7 +43,7 @@ #include "absl/strings/str_cat.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { // @@ -190,7 +190,7 @@ struct DefaultFormatter<std::unique_ptr<ValueType>> // // The main joining algorithm. This simply joins the elements in the given -// iterator range, each separated by the given separator, into an output std::string, +// iterator range, each separated by the given separator, into an output string, // and formats each element using the provided Formatter object. template <typename Iterator, typename Formatter> std::string JoinAlgorithm(Iterator start, Iterator end, absl::string_view s, @@ -206,20 +206,20 @@ std::string JoinAlgorithm(Iterator start, Iterator end, absl::string_view s, } // A joining algorithm that's optimized for a forward iterator range of -// std::string-like objects that do not need any additional formatting. This is to -// optimize the common case of joining, say, a std::vector<std::string> or a +// string-like objects that do not need any additional formatting. This is to +// optimize the common case of joining, say, a std::vector<string> or a // std::vector<absl::string_view>. // // This is an overload of the previous JoinAlgorithm() function. Here the // Formatter argument is of type NoFormatter. Since NoFormatter is an internal // type, this overload is only invoked when strings::Join() is called with a -// range of std::string-like objects (e.g., std::string, absl::string_view), and an +// range of string-like objects (e.g., string, absl::string_view), and an // explicit Formatter argument was NOT specified. // // The optimization is that the needed space will be reserved in the output -// std::string to avoid the need to resize while appending. To do this, the iterator +// string to avoid the need to resize while appending. To do this, the iterator // range will be traversed twice: once to calculate the total needed size, and -// then again to copy the elements and delimiters to the output std::string. +// then again to copy the elements and delimiters to the output string. template <typename Iterator, typename = typename std::enable_if<std::is_convertible< typename std::iterator_traits<Iterator>::iterator_category, @@ -307,7 +307,7 @@ std::string JoinRange(const Range& range, absl::string_view separator) { } } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_STR_JOIN_INTERNAL_H_ diff --git a/absl/strings/internal/str_split_internal.h b/absl/strings/internal/str_split_internal.h index e2d2c6b0..2300193a 100644 --- a/absl/strings/internal/str_split_internal.h +++ b/absl/strings/internal/str_split_internal.h @@ -47,12 +47,12 @@ #endif // _GLIBCXX_DEBUG namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { // This class is implicitly constructible from everything that absl::string_view // is implicitly constructible from. If it's constructed from a temporary -// std::string, the data is moved into a data member so its lifetime matches that of +// string, the data is moved into a data member so its lifetime matches that of // the ConvertibleToStringView instance. class ConvertibleToStringView { public: @@ -103,7 +103,7 @@ ConvertibleToStringView(std::string&& s) // NOLINT(runtime/explicit) absl::string_view value_; }; -// An iterator that enumerates the parts of a std::string from a Splitter. The text +// An iterator that enumerates the parts of a string from a Splitter. The text // to be split, the Delimiter, and the Predicate are all taken from the given // Splitter object. Iterators may only be compared if they refer to the same // Splitter instance. @@ -160,7 +160,7 @@ class SplitIterator { } const absl::string_view text = splitter_->text(); const absl::string_view d = delimiter_.Find(text, pos_); - if (d.data() == text.end()) state_ = kLastState; + if (d.data() == text.data() + text.size()) state_ = kLastState; curr_ = text.substr(pos_, d.data() - (text.data() + pos_)); pos_ += curr_.size() + d.size(); } while (!predicate_(curr_)); @@ -229,14 +229,31 @@ struct IsInitializerList // compiled in C++11 will get an error due to ambiguous conversion paths (in // C++11 std::vector<T>::operator= is overloaded to take either a std::vector<T> // or an std::initializer_list<T>). + +template <typename C, bool has_value_type, bool has_mapped_type> +struct SplitterIsConvertibleToImpl : std::false_type {}; + +template <typename C> +struct SplitterIsConvertibleToImpl<C, true, false> + : std::is_constructible<typename C::value_type, absl::string_view> {}; + +template <typename C> +struct SplitterIsConvertibleToImpl<C, true, true> + : absl::conjunction< + std::is_constructible<typename C::key_type, absl::string_view>, + std::is_constructible<typename C::mapped_type, absl::string_view>> {}; + template <typename C> struct SplitterIsConvertibleTo - : std::enable_if< + : SplitterIsConvertibleToImpl< + C, #ifdef _GLIBCXX_DEBUG !IsStrictlyBaseOfAndConvertibleToSTLContainer<C>::value && #endif // _GLIBCXX_DEBUG - !IsInitializerList<C>::value && HasValueType<C>::value && - HasConstIterator<C>::value> { + !IsInitializerList< + typename std::remove_reference<C>::type>::value && + HasValueType<C>::value && HasConstIterator<C>::value, + HasMappedType<C>::value> { }; // This class implements the range that is returned by absl::StrSplit(). This @@ -282,7 +299,8 @@ class Splitter { // An implicit conversion operator that is restricted to only those containers // that the splitter is convertible to. template <typename Container, - typename OnlyIf = typename SplitterIsConvertibleTo<Container>::type> + typename = typename std::enable_if< + SplitterIsConvertibleTo<Container>::value>::type> operator Container() const { // NOLINT(runtime/explicit) return ConvertToContainer<Container, typename Container::value_type, HasMappedType<Container>::value>()(*this); @@ -431,7 +449,7 @@ class Splitter { }; } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_STR_SPLIT_INTERNAL_H_ diff --git a/absl/strings/internal/utf8.cc b/absl/strings/internal/utf8.cc index 81b6241b..c6ab0d52 100644 --- a/absl/strings/internal/utf8.cc +++ b/absl/strings/internal/utf8.cc @@ -17,7 +17,7 @@ #include "absl/strings/internal/utf8.h" namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { size_t EncodeUTF8Char(char *buffer, char32_t utf8_char) { @@ -49,5 +49,5 @@ size_t EncodeUTF8Char(char *buffer, char32_t utf8_char) { } } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl diff --git a/absl/strings/internal/utf8.h b/absl/strings/internal/utf8.h index 5a94ae6f..59c4f5b4 100644 --- a/absl/strings/internal/utf8.h +++ b/absl/strings/internal/utf8.h @@ -22,7 +22,7 @@ #include <cstdint> namespace absl { -inline namespace lts_2018_06_20 { +inline namespace lts_2018_12_18 { namespace strings_internal { // For Unicode code points 0 through 0x10FFFF, EncodeUTF8Char writes @@ -43,7 +43,7 @@ enum { kMaxEncodedUTF8Size = 4 }; size_t EncodeUTF8Char(char *buffer, char32_t utf8_char); } // namespace strings_internal -} // inline namespace lts_2018_06_20 +} // inline namespace lts_2018_12_18 } // namespace absl #endif // ABSL_STRINGS_INTERNAL_UTF8_H_ |