[libc++] Fixes std::to_chars for bases != 10.

[Mordante]

Summary

While working on D70631, Microsoft's unit tests discovered an issue.
Our std::to_chars implementation for bases != 10 uses the range
[first,last) as temporary buffer. This violates the contract for
to_chars:
[charconv.to.chars]/1 http://eel.is/c++draft/charconv#to.chars-1
to_chars_result to_chars(char* first, char* last, see below value, int base = 10);
"If the member ec of the return value is such that the value is equal to
the value of a value-initialized errc, the conversion was successful and
the member ptr is the one-past-the-end pointer of the characters
written."

Our implementation modifies the range [member ptr, last), which causes
Microsoft's test to fail. Their test verifies the buffer
[member ptr, last) is unchanged. (The test is only done when the
conversion is successful.)

While looking at the code I noticed the performance for bases != 10 also
is suboptimal. This is tracked in D97705.

This patch fixes the issue and adds a benchmark. This benchmark will be
used as baseline for D97705.

[Mordante]

Fixes signed vs unsigned compiler warnings.

[Mordante]

Friendly ping.

[• Quuxplusone]

LGTM % nits. You probably want to ping Louis (or whoever) by name, though.

libcxx/include/charconv

405

Break line after int.
Also, it'd be nice to use the same 4-space indents in these two new functions as are used everywhere else in the file.

408–410

Nit: I'd have named these __base2, __base3, __base4 and expressed __base4 as __base2 * __base2.

440–445

IIUC, __diff is __cap and __width is __n? I think you should do the renaming.

libcxx/test/support/charconv_test_helpers.h

111

Might be even better to initialize with
for (int i=0; i < sizeof(buf); ++i) buf[i] = i+1;
and check with
for (int i=0; i < sizeof(buf); ++i) assert(buf[i] < r.ptr || buf[i] == i+1);
or something along those lines (I didn't think too hard about it), to verify that we're not even replacing part of the buffer with some shuffled other part of the buffer, or memsetting the buffer to buf[0], or anything dumb like that.
I can't think of any plausible mechanism that would cause such a bug, though, so maybe this doesn't matter.

[Mordante]

Thanks for the review!

libcxx/include/charconv

405

This is what clang-format makes of it. IMO if we don't like the style we should change our clang-format settings.

408–410

Renamed to __base_x.

440–445

Copy-paste programming ;-) Renamed them.

libcxx/test/support/charconv_test_helpers.h

111

I also can't think of a plausible reason. However the change is trivial so I've changed it.

[Mordante]

Addresses review comments.

[zoecarver]

Send it. Thanks!

libcxx/benchmarks/to_chars.bench.cpp

+//===----------------------------------------------------------------------===//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <array>
+#include <charconv>
+#include <random>
+
+#include "benchmark/benchmark.h"
+#include "test_macros.h"
+
+static const std::array<unsigned, 1000> input = [] {
+  std::mt19937 generator;
+  std::uniform_int_distribution<unsigned> distribution(0, std::numeric_limits<unsigned>::max());
+  std::array<unsigned, 1000> result;
+  std::generate_n(result.begin(), result.size(), [&] { return distribution(generator); });
+  return result;
+}();
+
+static void BM_to_chars_good(benchmark::State& state) {
+  char buffer[128];
+  int base = state.range(0);
+  while (state.KeepRunningBatch(input.size()))
+    for (auto value : input)
+      benchmark::DoNotOptimize(std::to_chars(buffer, &buffer[128], value, base));
+}
+BENCHMARK(BM_to_chars_good)->DenseRange(2, 36, 1);
+
+static void BM_to_chars_bad(benchmark::State& state) {
+  char buffer[128];
+  int base = state.range(0);
+  struct sample {
+    unsigned size;
+    unsigned value;
+  };
+  std::array<sample, 1000> data;
+  // Assume the failure occurs, on average, halfway during the conversion.
+  std::transform(input.begin(), input.end(), data.begin(), [&](unsigned value) {
+    std::to_chars_result result = std::to_chars(buffer, &buffer[128], value, base);
+    return sample{unsigned((result.ptr - buffer) / 2), value};
+  });
+
+  while (state.KeepRunningBatch(data.size()))
+    for (auto element : data)
+      benchmark::DoNotOptimize(std::to_chars(buffer, &buffer[element.size], element.value, base));
+}
+BENCHMARK(BM_to_chars_bad)->DenseRange(2, 36, 1);
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  benchmark::RunSpecifiedBenchmarks();
+}

libcxx/include/charconv

 
 */
 
 #include <__config>
 #include <__availability>
 #include <__errc>
 #include <cmath> // for log2f
 #include <cstdint>
+#include <cstdlib> // for _LIBCPP_UNREACHABLE
 #include <cstring>
 #include <limits>
 #include <type_traits>
 #include <utility>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
if (__value < 0 && __first != __last)
         *__first++ = '-';
         __x = __complement(__x);
     }
 
     return __to_chars_integral(__first, __last, __x, __base, false_type());
 }
 
 template <typename _Tp>
+_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_INLINE_VISIBILITY unsigned __to_chars_integral_width(_Tp __value,
+                                                                                           unsigned __base) {
+  _LIBCPP_ASSERT(__value >= 0, "The function requires a non-negative value.");
+
+  unsigned __pow_2 = __base * __base;
+  unsigned __pow_3 = __pow_2 * __base;
+  unsigned __pow_4 = __pow_3 * __base;
+
+  unsigned __r = 0;
+  while (true) {
+    if (__value < __base)
+      return __r + 1;
+    if (__value < __pow_2)
+      return __r + 2;
+    if (__value < __pow_3)
+      return __r + 3;
+    if (__value < __pow_4)
+      return __r + 4;
+
+    __value /= __pow_4;
+    __r += 4;
+  }
+
+  _LIBCPP_UNREACHABLE();
+}
+
+template <typename _Tp>
 _LIBCPP_AVAILABILITY_TO_CHARS
 inline _LIBCPP_INLINE_VISIBILITY to_chars_result
 __to_chars_integral(char* __first, char* __last, _Tp __value, int __base,
                     false_type)
 {
-    if (__base == 10)
-        return __to_chars_itoa(__first, __last, __value, false_type());
 
-    auto __p = __last;
-    while (__p != __first)
-    {
-        auto __c = __value % __base;
-        __value /= __base;
-        *--__p = "0123456789abcdefghijklmnopqrstuvwxyz"[__c];
-        if (__value == 0)
-            break;
-    }
-
-    auto __len = __last - __p;
-    if (__value != 0 || !__len)
-        return {__last, errc::value_too_large};
-    else
-    {
-        _VSTD::memmove(__first, __p, __len);
-        return {__first + __len, {}};
-    }
+  auto __diff = __last - __first;
+  auto __width = __to_chars_integral_width(__value, __base);
+  if (__width > __diff)
+    return {__last, errc::value_too_large};
+
+  __last = __first + __width;
+  do {
+  } while (__value != 0);
+  return {__last, errc(0)};
 }
 
 template <typename _Tp, typename enable_if<is_integral<_Tp>::value, int>::type = 0>
 _LIBCPP_AVAILABILITY_TO_CHARS
 inline _LIBCPP_INLINE_VISIBILITY to_chars_result
 to_chars(char* __first, char* __last, _Tp __value)
 {
     return __to_chars_itoa(__first, __last, __value, is_signed<_Tp>());

libcxx/test/support/charconv_test_helpers.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SUPPORT_CHARCONV_TEST_HELPERS_H
 #define SUPPORT_CHARCONV_TEST_HELPERS_H
 
+#include <algorithm>
 #include <charconv>
 #include <cassert>
 #include <limits>
 #include <string.h>
 #include <stdlib.h>
 
 #include "test_macros.h"
 
struct to_chars_test_base
     }
 
     template <typename... Ts>
     void test_value(X v, Ts... args)
     {
         using std::to_chars;
         std::to_chars_result r;
 
+        // Poison the buffer for testing whether a successful std::to_chars
+        // doesn't modify data beyond r.ptr.
+        std::fill(buf, buf + sizeof(buf), '~');
         r = to_chars(buf, buf + sizeof(buf), v, args...);
         assert(r.ec == std::errc{});
+        assert(std::all_of(r.ptr, buf + sizeof(buf), [](char c) { return c == '~'; }));
         *r.ptr = '\0';
 
         auto a = fromchars(buf, r.ptr, args...);
         assert(v == a);
 
         auto ep = r.ptr - 1;
         r = to_chars(buf, ep, v, args...);
         assert(r.ptr == ep);