Implement std::string_view as described in http://wg21.link/P0254R1. Reviewed as https://reviews.llvm.org/D21459

llvm-svn: 276238

1 files changed, 725 insertions, 0 deletions

diff --git a/libcxx/include/__string b/libcxx/include/__string
new file mode 100644
index 00000000000..334541102b8
--- /dev/null
+++ b/libcxx/include/__string
@@ -0,0 +1,725 @@
+// -*- C++ -*-
+//===-------------------------- __string ----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___STRING
+#define _LIBCPP___STRING
+
+/*
+    string synopsis
+
+namespace std
+{
+
+template <class charT>
+struct char_traits
+{
+    typedef charT     char_type;
+    typedef ...       int_type;
+    typedef streamoff off_type;
+    typedef streampos pos_type;
+    typedef mbstate_t state_type;
+
+    static void assign(char_type& c1, const char_type& c2) noexcept;
+    static constexpr bool eq(char_type c1, char_type c2) noexcept;
+    static constexpr bool lt(char_type c1, char_type c2) noexcept;
+
+    static int              compare(const char_type* s1, const char_type* s2, size_t n);
+    static size_t           length(const char_type* s);
+    static const char_type* find(const char_type* s, size_t n, const char_type& a);
+    static char_type*       move(char_type* s1, const char_type* s2, size_t n);
+    static char_type*       copy(char_type* s1, const char_type* s2, size_t n);
+    static char_type*       assign(char_type* s, size_t n, char_type a);
+
+    static constexpr int_type  not_eof(int_type c) noexcept;
+    static constexpr char_type to_char_type(int_type c) noexcept;
+    static constexpr int_type  to_int_type(char_type c) noexcept;
+    static constexpr bool      eq_int_type(int_type c1, int_type c2) noexcept;
+    static constexpr int_type  eof() noexcept;
+};
+
+template <> struct char_traits<char>;
+template <> struct char_traits<wchar_t>;
+
+}  // std
+
+*/
+
+#include <__config>
+#include <algorithm>  // for search and min
+#include <cstdio>     // For EOF.
+#include <memory>     // for __murmur2_or_cityhash
+
+#include <__undef_min_max>
+
+#include <__debug>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// char_traits
+
+template <class _CharT>
+struct _LIBCPP_TYPE_VIS_ONLY char_traits
+{
+    typedef _CharT    char_type;
+    typedef int       int_type;
+    typedef streamoff off_type;
+    typedef streampos pos_type;
+    typedef mbstate_t state_type;
+
+    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
+        {__c1 = __c2;}
+    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
+        {return __c1 < __c2;}
+
+    static int              compare(const char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static size_t           length(const char_type* __s);
+    _LIBCPP_INLINE_VISIBILITY
+    static const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
+    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static char_type*       assign(char_type* __s, size_t __n, char_type __a);
+
+    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
+        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
+    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
+        {return char_type(__c);}
+    static inline _LIBCPP_CONSTEXPR int_type  to_int_type(char_type __c) _NOEXCEPT
+        {return int_type(__c);}
+    static inline _LIBCPP_CONSTEXPR bool      eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
+        {return int_type(EOF);}
+};
+
+template <class _CharT>
+int
+char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
+{
+    for (; __n; --__n, ++__s1, ++__s2)
+    {
+        if (lt(*__s1, *__s2))
+            return -1;
+        if (lt(*__s2, *__s1))
+            return 1;
+    }
+    return 0;
+}
+
+template <class _CharT>
+inline
+size_t
+char_traits<_CharT>::length(const char_type* __s)
+{
+    size_t __len = 0;
+    for (; !eq(*__s, char_type(0)); ++__s)
+        ++__len;
+    return __len;
+}
+
+template <class _CharT>
+inline
+const _CharT*
+char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
+{
+    for (; __n; --__n)
+    {
+        if (eq(*__s, __a))
+            return __s;
+        ++__s;
+    }
+    return 0;
+}
+
+template <class _CharT>
+_CharT*
+char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
+{
+    char_type* __r = __s1;
+    if (__s1 < __s2)
+    {
+        for (; __n; --__n, ++__s1, ++__s2)
+            assign(*__s1, *__s2);
+    }
+    else if (__s2 < __s1)
+    {
+        __s1 += __n;
+        __s2 += __n;
+        for (; __n; --__n)
+            assign(*--__s1, *--__s2);
+    }
+    return __r;
+}
+
+template <class _CharT>
+inline
+_CharT*
+char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
+{
+    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
+    char_type* __r = __s1;
+    for (; __n; --__n, ++__s1, ++__s2)
+        assign(*__s1, *__s2);
+    return __r;
+}
+
+template <class _CharT>
+inline
+_CharT*
+char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
+{
+    char_type* __r = __s;
+    for (; __n; --__n, ++__s)
+        assign(*__s, __a);
+    return __r;
+}
+
+// char_traits<char>
+
+template <>
+struct _LIBCPP_TYPE_VIS_ONLY char_traits<char>
+{
+    typedef char      char_type;
+    typedef int       int_type;
+    typedef streamoff off_type;
+    typedef streampos pos_type;
+    typedef mbstate_t state_type;
+
+    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
+        {__c1 = __c2;}
+    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
+            {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
+        {return (unsigned char)__c1 < (unsigned char)__c2;}
+
+    static inline int compare(const char_type* __s1, const char_type* __s2, size_t __n)
+        {return __n == 0 ? 0 : memcmp(__s1, __s2, __n);}
+    static inline size_t length(const char_type* __s) {return strlen(__s);}
+    static inline const char_type* find(const char_type* __s, size_t __n, const char_type& __a)
+        {return __n == 0 ? NULL : (const char_type*) memchr(__s, to_int_type(__a), __n);}
+    static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n)
+        {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}
+    static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n)
+        {
+            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
+            return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
+        }
+    static inline char_type* assign(char_type* __s, size_t __n, char_type __a)
+        {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);}
+
+    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
+        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
+    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
+        {return char_type(__c);}
+    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
+        {return int_type((unsigned char)__c);}
+    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
+        {return int_type(EOF);}
+};
+
+// char_traits<wchar_t>
+
+template <>
+struct _LIBCPP_TYPE_VIS_ONLY char_traits<wchar_t>
+{
+    typedef wchar_t   char_type;
+    typedef wint_t    int_type;
+    typedef streamoff off_type;
+    typedef streampos pos_type;
+    typedef mbstate_t state_type;
+
+    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
+        {__c1 = __c2;}
+    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
+        {return __c1 < __c2;}
+
+    static inline int compare(const char_type* __s1, const char_type* __s2, size_t __n)
+        {return __n == 0 ? 0 : wmemcmp(__s1, __s2, __n);}
+    static inline size_t length(const char_type* __s)
+        {return wcslen(__s);}
+    static inline const char_type* find(const char_type* __s, size_t __n, const char_type& __a)
+        {return __n == 0 ? NULL : (const char_type*)wmemchr(__s, __a, __n);}
+    static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n)
+        {return __n == 0 ? __s1 : (char_type*)wmemmove(__s1, __s2, __n);}
+    static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n)
+        {
+            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
+            return __n == 0 ? __s1 : (char_type*)wmemcpy(__s1, __s2, __n);
+        }
+    static inline char_type* assign(char_type* __s, size_t __n, char_type __a)
+        {return __n == 0 ? __s : (char_type*)wmemset(__s, __a, __n);}
+
+    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
+        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
+    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
+        {return char_type(__c);}
+    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
+        {return int_type(__c);}
+    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
+        {return int_type(WEOF);}
+};
+
+#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
+
+template <>
+struct _LIBCPP_TYPE_VIS_ONLY char_traits<char16_t>
+{
+    typedef char16_t       char_type;
+    typedef uint_least16_t int_type;
+    typedef streamoff      off_type;
+    typedef u16streampos   pos_type;
+    typedef mbstate_t      state_type;
+
+    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
+        {__c1 = __c2;}
+    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
+        {return __c1 < __c2;}
+
+    _LIBCPP_INLINE_VISIBILITY
+    static int              compare(const char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static size_t           length(const char_type* __s);
+    _LIBCPP_INLINE_VISIBILITY
+    static const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
+    _LIBCPP_INLINE_VISIBILITY
+    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static char_type*       assign(char_type* __s, size_t __n, char_type __a);
+
+    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
+        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
+    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
+        {return char_type(__c);}
+    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
+        {return int_type(__c);}
+    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
+        {return int_type(0xFFFF);}
+};
+
+inline
+int
+char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
+{
+    for (; __n; --__n, ++__s1, ++__s2)
+    {
+        if (lt(*__s1, *__s2))
+            return -1;
+        if (lt(*__s2, *__s1))
+            return 1;
+    }
+    return 0;
+}
+
+inline
+size_t
+char_traits<char16_t>::length(const char_type* __s)
+{
+    size_t __len = 0;
+    for (; !eq(*__s, char_type(0)); ++__s)
+        ++__len;
+    return __len;
+}
+
+inline
+const char16_t*
+char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a)
+{
+    for (; __n; --__n)
+    {
+        if (eq(*__s, __a))
+            return __s;
+        ++__s;
+    }
+    return 0;
+}
+
+inline
+char16_t*
+char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n)
+{
+    char_type* __r = __s1;
+    if (__s1 < __s2)
+    {
+        for (; __n; --__n, ++__s1, ++__s2)
+            assign(*__s1, *__s2);
+    }
+    else if (__s2 < __s1)
+    {
+        __s1 += __n;
+        __s2 += __n;
+        for (; __n; --__n)
+            assign(*--__s1, *--__s2);
+    }
+    return __r;
+}
+
+inline
+char16_t*
+char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n)
+{
+    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
+    char_type* __r = __s1;
+    for (; __n; --__n, ++__s1, ++__s2)
+        assign(*__s1, *__s2);
+    return __r;
+}
+
+inline
+char16_t*
+char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a)
+{
+    char_type* __r = __s;
+    for (; __n; --__n, ++__s)
+        assign(*__s, __a);
+    return __r;
+}
+
+template <>
+struct _LIBCPP_TYPE_VIS_ONLY char_traits<char32_t>
+{
+    typedef char32_t       char_type;
+    typedef uint_least32_t int_type;
+    typedef streamoff      off_type;
+    typedef u32streampos   pos_type;
+    typedef mbstate_t      state_type;
+
+    static inline void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
+        {__c1 = __c2;}
+    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
+        {return __c1 < __c2;}
+
+    _LIBCPP_INLINE_VISIBILITY
+    static int              compare(const char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static size_t           length(const char_type* __s);
+    _LIBCPP_INLINE_VISIBILITY
+    static const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
+    _LIBCPP_INLINE_VISIBILITY
+    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n);
+    _LIBCPP_INLINE_VISIBILITY
+    static char_type*       assign(char_type* __s, size_t __n, char_type __a);
+
+    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
+        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
+    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
+        {return char_type(__c);}
+    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
+        {return int_type(__c);}
+    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
+        {return __c1 == __c2;}
+    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
+        {return int_type(0xFFFFFFFF);}
+};
+
+inline
+int
+char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
+{
+    for (; __n; --__n, ++__s1, ++__s2)
+    {
+        if (lt(*__s1, *__s2))
+            return -1;
+        if (lt(*__s2, *__s1))
+            return 1;
+    }
+    return 0;
+}
+
+inline
+size_t
+char_traits<char32_t>::length(const char_type* __s)
+{
+    size_t __len = 0;
+    for (; !eq(*__s, char_type(0)); ++__s)
+        ++__len;
+    return __len;
+}
+
+inline
+const char32_t*
+char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a)
+{
+    for (; __n; --__n)
+    {
+        if (eq(*__s, __a))
+            return __s;
+        ++__s;
+    }
+    return 0;
+}
+
+inline
+char32_t*
+char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n)
+{
+    char_type* __r = __s1;
+    if (__s1 < __s2)
+    {
+        for (; __n; --__n, ++__s1, ++__s2)
+            assign(*__s1, *__s2);
+    }
+    else if (__s2 < __s1)
+    {
+        __s1 += __n;
+        __s2 += __n;
+        for (; __n; --__n)
+            assign(*--__s1, *--__s2);
+    }
+    return __r;
+}
+
+inline
+char32_t*
+char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n)
+{
+    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
+    char_type* __r = __s1;
+    for (; __n; --__n, ++__s1, ++__s2)
+        assign(*__s1, *__s2);
+    return __r;
+}
+
+inline
+char32_t*
+char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a)
+{
+    char_type* __r = __s;
+    for (; __n; --__n, ++__s)
+        assign(*__s, __a);
+    return __r;
+}
+
+#endif  // _LIBCPP_HAS_NO_UNICODE_CHARS
+
+// helper fns for basic_string and string_view
+
+// __str_find
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_find(const _CharT *__p, _SizeT __sz, 
+             _CharT __c, _SizeT __pos) _NOEXCEPT
+{
+    if (__pos >= __sz)
+        return __npos;
+    const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
+    if (__r == 0)
+        return __npos;
+    return static_cast<_SizeT>(__r - __p);
+}
+
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_find(const _CharT *__p, _SizeT __sz, 
+       const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
+{
+    if (__pos > __sz || __sz - __pos < __n)
+        return __npos;
+    if (__n == 0)
+        return __pos;
+    const _CharT* __r = 
+        _VSTD::__search(__p + __pos, __p + __sz,
+                        __s, __s + __n, _Traits::eq,
+                        random_access_iterator_tag(), random_access_iterator_tag()).first;
+    if (__r == __p + __sz)
+        return __npos;
+    return static_cast<_SizeT>(__r - __p);
+}
+
+
+// __str_rfind
+
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_rfind(const _CharT *__p, _SizeT __sz, 
+              _CharT __c, _SizeT __pos) _NOEXCEPT
+{
+    if (__sz < 1)
+        return __npos;
+    if (__pos < __sz)
+        ++__pos;
+    else
+        __pos = __sz;
+    for (const _CharT* __ps = __p + __pos; __ps != __p;)
+    {
+        if (_Traits::eq(*--__ps, __c))
+            return static_cast<_SizeT>(__ps - __p);
+    }
+    return __npos;
+}
+
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_rfind(const _CharT *__p, _SizeT __sz, 
+        const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
+{
+    __pos = _VSTD::min(__pos, __sz);
+    if (__n < __sz - __pos)
+        __pos += __n;
+    else
+        __pos = __sz;
+    const _CharT* __r = _VSTD::__find_end(
+                  __p, __p + __pos, __s, __s + __n, _Traits::eq, 
+                        random_access_iterator_tag(), random_access_iterator_tag());
+    if (__n > 0 && __r == __p + __pos)
+        return __npos;
+    return static_cast<_SizeT>(__r - __p);
+}
+
+// __str_find_first_of
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_find_first_of(const _CharT *__p, _SizeT __sz,
+                const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
+{
+    if (__pos >= __sz || __n == 0)
+        return __npos;
+    const _CharT* __r = _VSTD::__find_first_of_ce
+        (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
+    if (__r == __p + __sz)
+        return __npos;
+    return static_cast<_SizeT>(__r - __p);
+}
+
+
+// __str_find_last_of
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_find_last_of(const _CharT *__p, _SizeT __sz,
+               const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
+    {
+    if (__n != 0)
+    {
+        if (__pos < __sz)
+            ++__pos;
+        else
+            __pos = __sz;
+        for (const _CharT* __ps = __p + __pos; __ps != __p;)
+        {
+            const _CharT* __r = _Traits::find(__s, __n, *--__ps);
+            if (__r)
+                return static_cast<_SizeT>(__ps - __p);
+        }
+    }
+    return __npos;
+}
+
+
+// __str_find_first_not_of
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
+                    const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
+{
+    if (__pos < __sz)
+    {
+        const _CharT* __pe = __p + __sz;
+        for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
+            if (_Traits::find(__s, __n, *__ps) == 0)
+                return static_cast<_SizeT>(__ps - __p);
+    }
+    return __npos;
+}
+
+
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
+                          _CharT __c, _SizeT __pos) _NOEXCEPT
+{
+    if (__pos < __sz)
+    {
+        const _CharT* __pe = __p + __sz;
+        for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
+            if (!_Traits::eq(*__ps, __c))
+                return static_cast<_SizeT>(__ps - __p);
+    }
+    return __npos;
+}
+
+
+// __str_find_last_not_of
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
+                   const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
+{
+    if (__pos < __sz)
+        ++__pos;
+    else
+        __pos = __sz;
+    for (const _CharT* __ps = __p + __pos; __ps != __p;)
+        if (_Traits::find(__s, __n, *--__ps) == 0)
+            return static_cast<_SizeT>(__ps - __p);
+    return __npos;
+}
+
+
+template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
+inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
+__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
+                         _CharT __c, _SizeT __pos) _NOEXCEPT
+{
+    if (__pos < __sz)
+        ++__pos;
+    else
+        __pos = __sz;
+    for (const _CharT* __ps = __p + __pos; __ps != __p;)
+        if (!_Traits::eq(*--__ps, __c))
+            return static_cast<_SizeT>(__ps - __p);
+    return __npos;
+}
+
+template<class _Ptr>
+size_t _LIBCPP_INLINE_VISIBILITY __do_string_hash(_Ptr __p, _Ptr __e)
+{
+    typedef typename iterator_traits<_Ptr>::value_type value_type;
+    return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
+}
+
+template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
+struct __quoted_output_proxy
+{
+    _Iter  __first;
+    _Iter  __last;
+    _CharT  __delim;
+    _CharT  __escape;
+
+    __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
+    : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
+    //  This would be a nice place for a string_ref 
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif  // _LIBCPP___STRING