Replace std::to_string for integers with optimized version

The std::to_chars functions from C++17 can be used to implement
std::to_string with much better performance than calling snprintf. Only
the __detail::__to_chars_len and __detail::__to_chars_10 functions are
needed for to_string, because it always outputs base 10 representations.

The return type of __detail::__to_chars_10 should not be declared before
C++17, so the function body is extracted into a new function that can be
reused by to_string and __detail::__to_chars_10.

The existing tests for to_chars rely on to_string to check for correct
answers. Now that they use the same code that doesn't actually ensure
correctness, so add new tests for std::to_string that compare against
printf output.

	* include/Makefile.am: Add new <bits/charconv.h> header.
	* include/Makefile.in: Regenerate.
	* include/bits/basic_string.h (to_string(int), to_string(unsigned))
	(to_string(long), to_string(unsigned long), to_string(long long))
	(to_string(unsigned long long)): Rewrite to use __to_chars_10_impl.
	* include/bits/charconv.h: New header.
	(__detail::__to_chars_len): Move here from <charconv>.
	(__detail::__to_chars_10_impl): New function extracted from
	__detail::__to_chars_10.
	* include/std/charconv (__cpp_lib_to_chars): Add, but comment out.
	(__to_chars_unsigned_type): New class template that reuses
	__make_unsigned_selector_base::__select to pick a type.
	(__unsigned_least_t): Redefine as __to_chars_unsigned_type<T>::type.
	(__detail::__to_chars_len): Move to new header.
	(__detail::__to_chars_10): Add inline specifier. Move code doing the
	output to __detail::__to_chars_10_impl and call that.
	* include/std/version (__cpp_lib_to_chars): Add, but comment out.
	* testsuite/21_strings/basic_string/numeric_conversions/char/
	to_string.cc: Fix reference in comment. Remove unused variable.
	* testsuite/21_strings/basic_string/numeric_conversions/char/
	to_string_int.cc: New test.

From-SVN: r272186

6 files changed, 176 insertions, 72 deletions

diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index 92975b1..742f2c3 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -102,6 +102,7 @@ bits_headers = \
 	${bits_srcdir}/boost_concept_check.h \
 	${bits_srcdir}/c++0x_warning.h \
 	${bits_srcdir}/char_traits.h \
+	${bits_srcdir}/charconv.h \
 	${bits_srcdir}/codecvt.h \
 	${bits_srcdir}/concept_check.h \
 	${bits_srcdir}/cpp_type_traits.h \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index 58c56f7..fd4dbf7 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -446,6 +446,7 @@ bits_headers = \
 	${bits_srcdir}/boost_concept_check.h \
 	${bits_srcdir}/c++0x_warning.h \
 	${bits_srcdir}/char_traits.h \
+	${bits_srcdir}/charconv.h \
 	${bits_srcdir}/codecvt.h \
 	${bits_srcdir}/concept_check.h \
 	${bits_srcdir}/cpp_type_traits.h \
diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index 897acaa..f1bdc6c 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -6500,6 +6500,7 @@ _GLIBCXX_END_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
 
 #include <ext/string_conversions.h>
+#include <bits/charconv.h>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -6547,43 +6548,68 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
   { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
 #endif // _GLIBCXX_USE_C99_STDLIB
 
-#if _GLIBCXX_USE_C99_STDIO
-  // NB: (v)snprintf vs sprintf.
+  // DR 1261. Insufficent overloads for to_string / to_wstring
 
-  // DR 1261.
   inline string
   to_string(int __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
-					   "%d", __val); }
+  {
+    const bool __neg = __val < 0;
+    const unsigned __uval = __neg ? (unsigned)~__val + 1u : __val;
+    const auto __len = __detail::__to_chars_len(__uval);
+    string __str(__neg + __len, '-');
+    __detail::__to_chars_10_impl(&__str[__neg], __len, __uval);
+    return __str;
+  }
 
   inline string
   to_string(unsigned __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
-					   4 * sizeof(unsigned),
-					   "%u", __val); }
+  {
+    string __str(__detail::__to_chars_len(__val), '\0');
+    __detail::__to_chars_10_impl(&__str[0], __str.size(), __val);
+    return __str;
+  }
 
   inline string
   to_string(long __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
-					   "%ld", __val); }
+  {
+    const bool __neg = __val < 0;
+    const unsigned long __uval = __neg ? (unsigned long)~__val + 1ul : __val;
+    const auto __len = __detail::__to_chars_len(__uval);
+    string __str(__neg + __len, '-');
+    __detail::__to_chars_10_impl(&__str[__neg], __len, __uval);
+    return __str;
+  }
 
   inline string
   to_string(unsigned long __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
-					   4 * sizeof(unsigned long),
-					   "%lu", __val); }
+  {
+    string __str(__detail::__to_chars_len(__val), '\0');
+    __detail::__to_chars_10_impl(&__str[0], __str.size(), __val);
+    return __str;
+  }
 
   inline string
   to_string(long long __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
-					   4 * sizeof(long long),
-					   "%lld", __val); }
+  {
+    const bool __neg = __val < 0;
+    const unsigned long long __uval
+      = __neg ? (unsigned long long)~__val + 1ull : __val;
+    const auto __len = __detail::__to_chars_len(__uval);
+    string __str(__neg + __len, '-');
+    __detail::__to_chars_10_impl(&__str[__neg], __len, __uval);
+    return __str;
+  }
 
   inline string
   to_string(unsigned long long __val)
-  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
-					   4 * sizeof(unsigned long long),
-					   "%llu", __val); }
+  {
+    string __str(__detail::__to_chars_len(__val), '\0');
+    __detail::__to_chars_10_impl(&__str[0], __str.size(), __val);
+    return __str;
+  }
+
+#if _GLIBCXX_USE_C99_STDIO
+  // NB: (v)snprintf vs sprintf.
 
   inline string
   to_string(float __val)
diff --git a/libstdc++-v3/include/bits/charconv.h b/libstdc++-v3/include/bits/charconv.h
new file mode 100644
index 0000000..0911660
--- /dev/null
+++ b/libstdc++-v3/include/bits/charconv.h
@@ -0,0 +1,106 @@
+// Numeric conversions (to_string, to_chars) -*- C++ -*-
+
+// Copyright (C) 2017-2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file bits/charconv.h
+ *  This is an internal header file, included by other library headers.
+ *  Do not attempt to use it directly. @headername{charconv}
+ */
+
+#ifndef _GLIBCXX_CHARCONV_H
+#define _GLIBCXX_CHARCONV_H 1
+
+#pragma GCC system_header
+
+#if __cplusplus >= 201103L
+
+#include <type_traits>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+namespace __detail
+{
+  // Generic implementation for arbitrary bases.
+  template<typename _Tp>
+    _GLIBCXX14_CONSTEXPR unsigned
+    __to_chars_len(_Tp __value, int __base = 10) noexcept
+    {
+      static_assert(is_integral<_Tp>::value, "implementation bug");
+      static_assert(is_unsigned<_Tp>::value, "implementation bug");
+
+      unsigned __n = 1;
+      const int __b2 = __base  * __base;
+      const int __b3 = __b2 * __base;
+      const int __b4 = __b3 * __base;
+      for (;;)
+	{
+	  if (__value < __base) return __n;
+	  if (__value < __b2) return __n + 1;
+	  if (__value < __b3) return __n + 2;
+	  if (__value < __b4) return __n + 3;
+	  __value /= (unsigned)__b4;
+	  __n += 4;
+	}
+    }
+
+  // Write an unsigned integer value to the range [first,first+len).
+  // The caller is required to provide a buffer of exactly the right size
+  // (which can be determined by the __to_chars_len function).
+  template<typename _Tp>
+    void
+    __to_chars_10_impl(char* __first, unsigned __len, _Tp __val) noexcept
+    {
+      static_assert(is_integral<_Tp>::value, "implementation bug");
+      static_assert(is_unsigned<_Tp>::value, "implementation bug");
+
+      static constexpr char __digits[201] =
+	"0001020304050607080910111213141516171819"
+	"2021222324252627282930313233343536373839"
+	"4041424344454647484950515253545556575859"
+	"6061626364656667686970717273747576777879"
+	"8081828384858687888990919293949596979899";
+      unsigned __pos = __len - 1;
+      while (__val >= 100)
+	{
+	  auto const __num = (__val % 100) * 2;
+	  __val /= 100;
+	  __first[__pos] = __digits[__num + 1];
+	  __first[__pos - 1] = __digits[__num];
+	  __pos -= 2;
+	}
+      if (__val >= 10)
+	{
+	  auto const __num = __val * 2;
+	  __first[__pos] = __digits[__num + 1];
+	  __first[__pos - 1] = __digits[__num];
+	}
+      else
+	__first[__pos] = '0' + __val;
+    }
+
+} // namespace __detail
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+#endif // C++11
+#endif // _GLIBCXX_CHARCONV_H
diff --git a/libstdc++-v3/include/std/charconv b/libstdc++-v3/include/std/charconv
index 9f01d4c..a777f60 100644
--- a/libstdc++-v3/include/std/charconv
+++ b/libstdc++-v3/include/std/charconv
@@ -36,8 +36,11 @@
 #include <type_traits>
 #include <limits>
 #include <cctype>
+#include <bits/charconv.h> // for __to_chars_len, __to_chars_10_impl
 #include <bits/error_constants.h> // for std::errc
 
+// Define when floating point is supported: #define __cpp_lib_to_chars 201611L
+
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -76,42 +79,30 @@ namespace __detail
     using __integer_to_chars_result_type
       = enable_if_t<__is_int_to_chars_type<_Tp>::value, to_chars_result>;
 
+  // Pick an unsigned type of suitable size. This is used to reduce the
+  // number of specializations of __to_chars_len, __to_chars etc. that
+  // get instantiated. For example, to_chars<char> and to_chars<short>
+  // and to_chars<unsigned> will all use the same code, and so will
+  // to_chars<long> when sizeof(int) == sizeof(long).
   template<typename _Tp>
-    using __unsigned_least_t
-      = conditional_t<(sizeof(_Tp) <= sizeof(int)), unsigned int,
-	conditional_t<(sizeof(_Tp) <= sizeof(long)), unsigned long,
-	conditional_t<(sizeof(_Tp) <= sizeof(long long)), unsigned long long,
-#if _GLIBCXX_USE_INT128
-	conditional_t<(sizeof(_Tp) <= sizeof(__int128)), unsigned __int128,
-#endif
-	void
+    struct __to_chars_unsigned_type : __make_unsigned_selector_base
+    {
+      using _UInts = _List<unsigned int, unsigned long, unsigned long long
 #if _GLIBCXX_USE_INT128
-	>
+	, unsigned __int128
 #endif
-	>>>;
+	>;
+      using type = typename __select<sizeof(_Tp), _UInts>::__type;
+    };
+
+  template<typename _Tp>
+    using __unsigned_least_t = typename __to_chars_unsigned_type<_Tp>::type;
 
   // Generic implementation for arbitrary bases.
+  // Defined in <bits/charconv.h>.
   template<typename _Tp>
     constexpr unsigned
-    __to_chars_len(_Tp __value, int __base = 10) noexcept
-    {
-      static_assert(is_integral<_Tp>::value, "implementation bug");
-      static_assert(is_unsigned<_Tp>::value, "implementation bug");
-
-      unsigned __n = 1;
-      const int __b2 = __base  * __base;
-      const int __b3 = __b2 * __base;
-      const int __b4 = __b3 * __base;
-      for (;;)
-	{
-	  if (__value < __base) return __n;
-	  if (__value < __b2) return __n + 1;
-	  if (__value < __b3) return __n + 2;
-	  if (__value < __b4) return __n + 3;
-	  __value /= (unsigned)__b4;
-	  __n += 4;
-	}
-    }
+    __to_chars_len(_Tp __value, int __base /* = 10 */) noexcept;
 
   template<typename _Tp>
     constexpr unsigned
@@ -242,7 +233,7 @@ namespace __detail
     }
 
   template<typename _Tp>
-    __integer_to_chars_result_type<_Tp>
+    inline __integer_to_chars_result_type<_Tp>
     __to_chars_10(char* __first, char* __last, _Tp __val) noexcept
     {
       static_assert(is_integral<_Tp>::value, "implementation bug");
@@ -259,29 +250,7 @@ namespace __detail
 	  return __res;
 	}
 
-      static constexpr char __digits[201] =
-	"0001020304050607080910111213141516171819"
-	"2021222324252627282930313233343536373839"
-	"4041424344454647484950515253545556575859"
-	"6061626364656667686970717273747576777879"
-	"8081828384858687888990919293949596979899";
-      unsigned __pos = __len - 1;
-      while (__val >= 100)
-	{
-	  auto const __num = (__val % 100) * 2;
-	  __val /= 100;
-	  __first[__pos] = __digits[__num + 1];
-	  __first[__pos - 1] = __digits[__num];
-	  __pos -= 2;
-	}
-      if (__val >= 10)
-	{
-	  auto const __num = __val * 2;
-	  __first[__pos] = __digits[__num + 1];
-	  __first[__pos - 1] = __digits[__num];
-	}
-      else
-	__first[__pos] = '0' + __val;
+      __detail::__to_chars_10_impl(__first, __len, __val);
       __res.ptr = __first + __len;
       __res.ec = {};
       return __res;
diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version
index 9da3854..cef4f1f 100644
--- a/libstdc++-v3/include/std/version
+++ b/libstdc++-v3/include/std/version
@@ -139,6 +139,7 @@
 #endif
 #define __cpp_lib_shared_ptr_weak_type 201606
 #define __cpp_lib_string_view 201603
+// #define __cpp_lib_to_chars 201611L
 #define __cpp_lib_type_trait_variable_templates 201510L
 #define __cpp_lib_uncaught_exceptions 201411L
 #define __cpp_lib_unordered_map_insertion 201411