[libc++] Fix leading zeros in std::to_chars

[ivafanas]

Summary

It is a bugfix proposal for https://bugs.llvm.org/show_bug.cgi?id=42166.

std::to_chars appends leading zeros if input 64-bit value has 9, 10 or 11 digits.
According to documentation std::to_chars must not append leading zeros:
https://en.cppreference.com/w/cpp/utility/to_chars

Changeset should not affect std::to_chars performance:
http://quick-bench.com/CEpRs14xxA9WLvkXFtaJ3TWOVAg

Unit test that std::from_chars supports compatibility for both std::to_chars outputs (previous and fixed one) already exists:
https://github.com/llvm-mirror/libcxx/blob/1f60111b597e5cb80a4513ec86f79b7e137f7793/test/std/utilities/charconv/charconv.from.chars/integral.pass.cpp#L63

[zoecarver]

The example in the bug doesn't work: std::to_chars(buf, buf + 100, (unsigned long)0xffffffff).

Edit: it outputs 0004294967295.

[ivafanas]

In D63047#1535297, @zoecarver wrote:

The example in the bug doesn't work: std::to_chars(buf, buf + 100, (unsigned long)0xffffffff).

Edit: it outputs 0004294967295.

Hi,

Hmm, are you sure?
I've just tested fixed version of std::to_chars and std::to_chars(buf, buf + 100, (unsigned long)0xffffffff) produces 4294967295 as expected.

May be you didn't recompile implementation before run lit tests?

[lichray]

I like the refactoring. I suggest not to drop existing (possibly redundant) tests.

libcxx/src/charconv.cpp

67

I suggest to use if here to align "append1" and "append2" closer to the condition

if (v < 10)
    return append1(buffer, v);
else
    return append2(buffer, v);

PS: I like the way how clang-format splits ternary operators,

return v < 10 ? append1(buffer, v)
              : append2(buffer, v);

but here this line is too short to receive the above formatting.

76

Ditto, and else if should be enough (to align all calls to start from the same column).

79

I suggest to make these new routines templates as well, so even someone changes the logic in actually formatting code slightly "wrong," the code can still behave correctly.

119

Can you keep the static_cast?

136

Can you keep the empty line after this line?

libcxx/test/std/utilities/charconv/charconv.to.chars/integral.pass.cpp

40

Please keep these tests, because it's a sane test for ensuring omitting the "base" argument means base 10.

69

Ditto.

[zoecarver]

In D63047#1535306, @ivafanas wrote:

In D63047#1535297, @zoecarver wrote:

The example in the bug doesn't work: std::to_chars(buf, buf + 100, (unsigned long)0xffffffff).

Edit: it outputs 0004294967295.

Hi,

Hmm, are you sure?
I've just tested fixed version of std::to_chars and std::to_chars(buf, buf + 100, (unsigned long)0xffffffff) produces 4294967295 as expected.

May be you didn't recompile implementation before run lit tests?

Yep, you're right. I applied the patch but forgot to recompile. Sorry for the false alarm. This patch looks good to me :)

[ivafanas]

Code review issues are adressed

[ivafanas]

libcxx/src/charconv.cpp

67

Done

76

Done

79

Done

119

Returned back

136

Do not understand, sorry.
There are already empty lines before and after buffer = append4_no_zeros(buffer, a);

libcxx/test/std/utilities/charconv/charconv.to.chars/integral.pass.cpp

40

Done

69

Done

[lichray]

libcxx/src/charconv.cpp

136

This revision is good, don't worry.

[lichray]

Ping @mclow.lists
Do you plan to do a final scan before I merging this?

[mclow.lists]

In D63047#1535837, @lichray wrote:

Ping @mclow.lists
Do you plan to do a final scan before I merging this?

Yes. This morning.

[mclow.lists]

LGTM, thanks. I have more tests that I'll be adding in the next week or so, but no reason to hold this up for them.

[lichray]

Regenerate the patch from libcxx directory

[lichray]

@ivafanas I forgot to update the description to include a "thank you" in the commit message; sorry about that (

libcxx/src/charconv.cpp

 
 template <typename T>
 inline _LIBCPP_INLINE_VISIBILITY char*
 append4(char* buffer, T i)
 {
     return append2(append2(buffer, (i) / 100), (i) % 100);
 }
 
-char*
-__u32toa(uint32_t value, char* buffer)
-{
-    if (value < 10000)
-    {
-        if (value < 100)
-        {
-            if (value < 10)
-                buffer = append1(buffer, value);
-            else
-                buffer = append2(buffer, value);
-        }
-        else
-        {
-            if (value < 1000)
-                buffer = append3(buffer, value);
-            else
-                buffer = append4(buffer, value);
-        }
-    }
-    else if (value < 100000000)
-    {
-        // value = bbbbcccc
-        const uint32_t b = value / 10000;
-        const uint32_t c = value % 10000;
+
+inline _LIBCPP_INLINE_VISIBILITY char*
+append2_no_zeros(char* buffer, uint32_t v)
+    return v < 10 ? append1(buffer, v) : append2(buffer, v);
+
+inline _LIBCPP_INLINE_VISIBILITY char*
+append4_no_zeros(char* buffer, uint32_t v)
+    if (v < 100)
+        return append2_no_zeros(buffer, v);
+        return v < 1000 ? append3(buffer, v) : append4(buffer, v);
 
-        if (value < 1000000)
-        {
-            if (value < 100000)
-                buffer = append1(buffer, b);
-            else
-                buffer = append2(buffer, b);
-        }
-        else
-        {
-            if (value < 10000000)
-                buffer = append3(buffer, b);
-            else
-                buffer = append4(buffer, b);
-        }
+inline _LIBCPP_INLINE_VISIBILITY char*
+append8_no_zeros(char* buffer, uint32_t v)
+    if (v < 10000)
+    {
+        buffer = append4_no_zeros(buffer, v);
+        buffer = append4_no_zeros(buffer, v / 10000);
+        buffer = append4(buffer, v % 10000);
+    }
+    return buffer;
 
-        buffer = append4(buffer, c);
+char*
+__u32toa(uint32_t value, char* buffer)
+{
+    if (value < 100000000)
+    {
+        buffer = append8_no_zeros(buffer, value);
     }
     else
     {
         // value = aabbbbcccc in decimal
         const uint32_t a = value / 100000000;  // 1 to 42
         value %= 100000000;
 
-        if (a < 10)
-            buffer = append1(buffer, a);
-        else
-            buffer = append2(buffer, a);
-
+        buffer = append2_no_zeros(buffer, a);
         buffer = append4(buffer, value / 10000);
         buffer = append4(buffer, value % 10000);
     }
-
     return buffer;
 }
 
 char*
 __u64toa(uint64_t value, char* buffer)
 {
     if (value < 100000000)
     {
-        uint32_t v = static_cast<uint32_t>(value);
-        if (v < 10000)
-        {
-            if (v < 100)
-            {
-                if (v < 10)
-                    buffer = append1(buffer, v);
-                else
-                    buffer = append2(buffer, v);
-            }
-            else
-            {
-                if (v < 1000)
-                    buffer = append3(buffer, v);
-                else
-                    buffer = append4(buffer, v);
-            }
-        }
-        else
-        {
-            // value = bbbbcccc
-            const uint32_t b = v / 10000;
-            const uint32_t c = v % 10000;
-
-            if (v < 1000000)
-            {
-                if (v < 100000)
-                    buffer = append1(buffer, b);
-                else
-                    buffer = append2(buffer, b);
-            }
-            else
-            {
-                if (v < 10000000)
-                    buffer = append3(buffer, b);
-                else
-                    buffer = append4(buffer, b);
-            }
-
-            buffer = append4(buffer, c);
-        }
+        buffer = append8_no_zeros(buffer, value);
     }
     else if (value < 10000000000000000)
     {
         const uint32_t v0 = static_cast<uint32_t>(value / 100000000);
         const uint32_t v1 = static_cast<uint32_t>(value % 100000000);
 
-        const uint32_t b0 = v0 / 10000;
-        const uint32_t c0 = v0 % 10000;
-
-        if (v0 < 1000000)
-        {
-            if (v0 < 100000)
-                buffer = append1(buffer, b0);
-            else
-                buffer = append2(buffer, b0);
-        }
-        else
-        {
-            if (v0 < 10000000)
-                buffer = append3(buffer, b0);
-            else
-                buffer = append4(buffer, b0);
-        }
-
-        buffer = append4(buffer, c0);
+        buffer = append8_no_zeros(buffer, v0);
         buffer = append4(buffer, v1 / 10000);
         buffer = append4(buffer, v1 % 10000);
     }
     else
     {
         const uint32_t a =
             static_cast<uint32_t>(value / 10000000000000000);  // 1 to 1844
         value %= 10000000000000000;
 
-        if (a < 100)
-        {
-            if (a < 10)
-                buffer = append1(buffer, a);
-            else
-                buffer = append2(buffer, a);
-        }
-        else
-        {
-            if (a < 1000)
-                buffer = append3(buffer, a);
-            else
-                buffer = append4(buffer, a);
-        }
+        buffer = append4_no_zeros(buffer, a);
 
         const uint32_t v0 = static_cast<uint32_t>(value / 100000000);
         const uint32_t v1 = static_cast<uint32_t>(value % 100000000);
         buffer = append4(buffer, v0 / 10000);
         buffer = append4(buffer, v0 % 10000);
         buffer = append4(buffer, v1 / 10000);
         buffer = append4(buffer, v1 % 10000);
     }
 
     return buffer;
 }
 
 }  // namespace __itoa
 
 _LIBCPP_END_NAMESPACE_STD

libcxx/test/std/utilities/charconv/charconv.to.chars/integral.pass.cpp

 template <typename T>
 struct test_basics : to_chars_test_base<T>
 {
     using to_chars_test_base<T>::test;
     using to_chars_test_base<T>::test_value;
 
     void operator()()
     {
-        test(0, "0");
-        test(42, "42");
-        test(32768, "32768");
         test(0, "0", 10);
         test(42, "42", 10);
         test(32768, "32768", 10);
         test(0xf, "f", 16);
         test(0xdeadbeaf, "deadbeaf", 16);
         test(0755, "755", 8);
 
+        // Test each len till len of UINT64_MAX = 20 because to_chars algorithm
+        // makes branches based on decimal digits count in the value string
+        // representation.
+        // Test driver automatically skips values not fitting into source type.
+        test(1UL, "1");
+        test(12UL, "12");
+        test(123UL, "123");
+        test(1234UL, "1234");
+        test(12345UL, "12345");
+        test(123456UL, "123456");
+        test(1234567UL, "1234567");
+        test(12345678UL, "12345678");
+        test(123456789UL, "123456789");
+        test(1234567890UL, "1234567890");
+        test(12345678901UL, "12345678901");
+        test(123456789012UL, "123456789012");
+        test(1234567890123UL, "1234567890123");
+        test(12345678901234UL, "12345678901234");
+        test(123456789012345UL, "123456789012345");
+        test(1234567890123456UL, "1234567890123456");
+        test(12345678901234567UL, "12345678901234567");
+        test(123456789012345678UL, "123456789012345678");
+        test(1234567890123456789UL, "1234567890123456789");
+        test(12345678901234567890UL, "12345678901234567890");
+
+        // Test special cases with zeros inside a value string representation,
+        // to_chars algorithm processes them in a special way and should not
+        // skip trailing zeros
+        // Test driver automatically skips values not fitting into source type.
+        test(0UL, "0");
+        test(10UL, "10");
+        test(100UL, "100");
+        test(1000UL, "1000");
+        test(10000UL, "10000");
+        test(100000UL, "100000");
+        test(1000000UL, "1000000");
+        test(10000000UL, "10000000");
+        test(100000000UL, "100000000");
+        test(1000000000UL, "1000000000");
+        test(10000000000UL, "10000000000");
+        test(100000000000UL, "100000000000");
+        test(1000000000000UL, "1000000000000");
+        test(10000000000000UL, "10000000000000");
+        test(100000000000000UL, "100000000000000");
+        test(1000000000000000UL, "1000000000000000");
+        test(10000000000000000UL, "10000000000000000");
+        test(100000000000000000UL, "100000000000000000");
+        test(1000000000000000000UL, "1000000000000000000");
+        test(10000000000000000000UL, "10000000000000000000");
+
         for (int b = 2; b < 37; ++b)
         {
             using xl = std::numeric_limits<T>;
 
             test_value(1, b);
             test_value(xl::lowest(), b);
             test_value((xl::max)(), b);
             test_value((xl::max)() / 2, b);
         }
     }
 };
 
 template <typename T>
 struct test_signed : to_chars_test_base<T>
 {
     using to_chars_test_base<T>::test;
     using to_chars_test_base<T>::test_value;
 
     void operator()()
     {
-        test(-1, "-1");
-        test(-12, "-12");
         test(-1, "-1", 10);
         test(-12, "-12", 10);
         test(-21734634, "-21734634", 10);
         test(-2647, "-101001010111", 2);
         test(-0xcc1, "-cc1", 16);
 
+        // Test each len till len of INT64_MAX = 19 because to_chars algorithm
+        // makes branches based on decimal digits count in the value string
+        // representation.
+        // Test driver automatically skips values not fitting into source type.
+        test(-1L, "-1");
+        test(-12L, "-12");
+        test(-123L, "-123");
+        test(-1234L, "-1234");
+        test(-12345L, "-12345");
+        test(-123456L, "-123456");
+        test(-1234567L, "-1234567");
+        test(-12345678L, "-12345678");
+        test(-123456789L, "-123456789");
+        test(-1234567890L, "-1234567890");
+        test(-12345678901L, "-12345678901");
+        test(-123456789012L, "-123456789012");
+        test(-1234567890123L, "-1234567890123");
+        test(-12345678901234L, "-12345678901234");
+        test(-123456789012345L, "-123456789012345");
+        test(-1234567890123456L, "-1234567890123456");
+        test(-12345678901234567L, "-12345678901234567");
+        test(-123456789012345678L, "-123456789012345678");
+        test(-1234567890123456789L, "-1234567890123456789");
+
+        // Test special cases with zeros inside a value string representation,
+        // to_chars algorithm processes them in a special way and should not
+        // skip trailing zeros
+        // Test driver automatically skips values not fitting into source type.
+        test(-10L, "-10");
+        test(-100L, "-100");
+        test(-1000L, "-1000");
+        test(-10000L, "-10000");
+        test(-100000L, "-100000");
+        test(-1000000L, "-1000000");
+        test(-10000000L, "-10000000");
+        test(-100000000L, "-100000000");
+        test(-1000000000L, "-1000000000");
+        test(-10000000000L, "-10000000000");
+        test(-100000000000L, "-100000000000");
+        test(-1000000000000L, "-1000000000000");
+        test(-10000000000000L, "-10000000000000");
+        test(-100000000000000L, "-100000000000000");
+        test(-1000000000000000L, "-1000000000000000");
+        test(-10000000000000000L, "-10000000000000000");
+        test(-100000000000000000L, "-100000000000000000");
+        test(-1000000000000000000L, "-1000000000000000000");
+
         for (int b = 2; b < 37; ++b)
         {
             using xl = std::numeric_limits<T>;
 
             test_value(0, b);
             test_value(xl::lowest(), b);
             test_value((xl::max)(), b);
         }