"Fossies" - the Fresh Open Source Software Archive

Member "dmd2/src/druntime/import/core/stdcpp/string.d" (20 Nov 2020, 101679 Bytes) of package /linux/misc/dmd.2.094.2.linux.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) D source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /**
    2  * D header file for interaction with C++ std::string.
    3  *
    4  * Copyright: Copyright (c) 2019 D Language Foundation
    5  * License: Distributed under the
    6  *      $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
    7  *    (See accompanying file LICENSE)
    8  * Authors:   Guillaume Chatelet
    9  *            Manu Evans
   10  * Source:    $(DRUNTIMESRC core/stdcpp/string.d)
   11  */
   12 
   13 module core.stdcpp.string;
   14 
   15 import core.stdcpp.allocator;
   16 import core.stdcpp.xutility : StdNamespace;
   17 import core.stdc.stddef : wchar_t;
   18 
   19 version (OSX)
   20     version = Darwin;
   21 else version (iOS)
   22     version = Darwin;
   23 else version (TVOS)
   24     version = Darwin;
   25 else version (WatchOS)
   26     version = Darwin;
   27 
   28 version (Darwin)
   29 {
   30     // Apple decided to rock a different ABI... good for them!
   31     version = _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT;
   32 }
   33 
   34 version (CppRuntime_Gcc)
   35 {
   36     version (_GLIBCXX_USE_CXX98_ABI)
   37     {
   38         private enum StringNamespace = "std";
   39         version = __GTHREADS;
   40     }
   41     else
   42     {
   43         import core.internal.traits : AliasSeq;
   44         private enum StringNamespace = AliasSeq!("std", "__cxx11");
   45     }
   46 }
   47 else
   48     alias StringNamespace = StdNamespace;
   49 
   50 enum DefaultConstruct { value }
   51 
   52 /// Constructor argument for default construction
   53 enum Default = DefaultConstruct();
   54 
   55 @nogc:
   56 
   57 /**
   58  * Character traits classes specify character properties and provide specific
   59  * semantics for certain operations on characters and sequences of characters.
   60  */
   61 extern(C++, (StdNamespace)) struct char_traits(CharT)
   62 {
   63     alias char_type = CharT;
   64 
   65     static size_t length(const(char_type)* s) @trusted pure nothrow @nogc
   66     {
   67         static if (is(char_type == char) || is(char_type == ubyte))
   68         {
   69             import core.stdc.string : strlen;
   70             return strlen(s);
   71         }
   72         else
   73         {
   74             size_t len = 0;
   75             for (; *s != char_type(0); ++s)
   76                 ++len;
   77             return len;
   78         }
   79     }
   80 
   81     static char_type* move(char_type* s1, const char_type* s2, size_t n) @trusted pure nothrow @nogc
   82     {
   83         import core.stdc.string : memmove;
   84         import core.stdc.wchar_ : wmemmove;
   85         import core.stdc.stddef : wchar_t;
   86 
   87         if (n == 0)
   88             return s1;
   89 
   90         version (CRuntime_Microsoft)
   91         {
   92             enum crt = __traits(getTargetInfo, "cppRuntimeLibrary");
   93             static if (crt.length >= 6 && crt[0 .. 6] == "msvcrt")
   94                 enum use_wmemmove = false; // https://issues.dlang.org/show_bug.cgi?id=20456
   95             else
   96                 enum use_wmemmove = true;
   97         }
   98         else
   99             enum use_wmemmove = true;
  100 
  101         static if (use_wmemmove
  102                 && (is(char_type == wchar_t)
  103                     || is(char_type == ushort) && wchar_t.sizeof == ushort.sizeof // Windows
  104                     || is(char_type == uint) && wchar_t.sizeof == uint.sizeof)) // POSIX
  105             return cast(char_type*) wmemmove(s1, s2, n);
  106         else
  107             return cast(char_type*) memmove(s1, s2, n * char_type.sizeof);
  108     }
  109 }
  110 
  111 // I don't think we can have these here, otherwise symbols are emit to druntime, and we don't want that...
  112 //alias std_string = basic_string!char;
  113 //alias std_u16string = basic_string!wchar; // TODO: can't mangle these yet either...
  114 //alias std_u32string = basic_string!dchar;
  115 //alias std_wstring = basic_string!wchar_t; // TODO: we can't mangle wchar_t properly (yet?)
  116 
  117 /**
  118  * D language counterpart to C++ std::basic_string.
  119  *
  120  * C++ reference: $(LINK2 https://en.cppreference.com/w/cpp/string/basic_string)
  121  */
  122 extern(C++, class)
  123 extern(C++, (StringNamespace))
  124 struct basic_string(T, Traits = char_traits!T, Alloc = allocator!T)
  125 {
  126 extern(D):
  127 @nogc:
  128 
  129     ///
  130     enum size_type npos = size_type.max;
  131 
  132     ///
  133     alias size_type = size_t;
  134     ///
  135     alias difference_type = ptrdiff_t;
  136     ///
  137     alias value_type = T;
  138     ///
  139     alias traits_type = Traits;
  140     ///
  141     alias allocator_type = Alloc;
  142     ///
  143     alias pointer = value_type*;
  144     ///
  145     alias const_pointer = const(value_type)*;
  146 
  147     ///
  148     alias toString = as_array;
  149 
  150     /// MSVC allocates on default initialisation in debug, which can't be modelled by D `struct`
  151     @disable this();
  152 
  153     ///
  154     alias length = size;
  155     ///
  156     alias opDollar = length;
  157     ///
  158     bool empty() const nothrow @safe                                        { return size() == 0; }
  159 
  160     ///
  161     size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const pure nothrow @safe @nogc { return [start, end]; }
  162 
  163     ///
  164     ref inout(T) opIndex(size_t index) inout pure nothrow @safe @nogc       { return as_array[index]; }
  165     ///
  166     inout(T)[] opIndex(size_t[2] slice) inout pure nothrow @safe @nogc      { return as_array[slice[0] .. slice[1]]; }
  167     ///
  168     inout(T)[] opIndex() inout pure nothrow @safe @nogc                     { return as_array(); }
  169 
  170     /// Two `basic_string`s are equal if they represent the same sequence of code units.
  171     bool opEquals(scope const ref basic_string s) const pure nothrow @safe  { return as_array == s.as_array; }
  172     /// ditto
  173     bool opEquals(scope const T[] s) const pure nothrow @safe               { return as_array == s; }
  174 
  175     /// Performs lexicographical comparison.
  176     int opCmp(scope const ref basic_string rhs) const pure nothrow @safe    { return __cmp(as_array, rhs.as_array); }
  177     /// ditto
  178     int opCmp(scope const T[] rhs) const pure nothrow @safe                 { return __cmp(as_array, rhs); }
  179 
  180     /// Hash to allow `basic_string`s to be used as keys for built-in associative arrays.
  181     /// **The result will generally not be the same as C++ `std::hash<std::basic_string<T>>`.**
  182     size_t toHash() const @nogc nothrow pure @safe                          { return .hashOf(as_array); }
  183 
  184     ///
  185     void clear()                                                            { eos(0); } // TODO: bounds-check
  186     ///
  187     void resize(size_type n, T c = T(0)) @trusted
  188     {
  189         if (n <= size())
  190             eos(n);
  191         else
  192             append(n - size(), c);
  193     }
  194 
  195     ///
  196     ref inout(T) front() inout nothrow @safe                                { return this[0]; }
  197     ///
  198     ref inout(T) back() inout nothrow @safe                                 { return this[$-1]; }
  199 
  200     ///
  201     const(T)* c_str() const nothrow @safe                                   { return data(); }
  202 
  203     // Modifiers
  204     ///
  205     ref basic_string opAssign()(auto ref basic_string str)                  { return assign(str); }
  206 //    ref basic_string assign(size_type n, T c);
  207     ///
  208     ref basic_string opAssign(const(T)[] str)                               { return assign(str); }
  209     ///
  210     ref basic_string opAssign(T c)                                          { return assign((&c)[0 .. 1]); }
  211 
  212     ///
  213     ref basic_string opIndexAssign(T c, size_t index)                       { as_array[index] = c; return this; }
  214     ///
  215     ref basic_string opIndexAssign(T c, size_t[2] slice)                    { as_array[slice[0] .. slice[1]] = c; return this; }
  216     ///
  217     ref basic_string opIndexAssign(const(T)[] str, size_t[2] slice)         { as_array[slice[0] .. slice[1]] = str[]; return this; }
  218     ///
  219     ref basic_string opIndexAssign(T c)                                     { as_array[] = c; return this; }
  220     ///
  221     ref basic_string opIndexAssign(const(T)[] str)                          { as_array[] = str[]; return this; }
  222 
  223     ///
  224     ref basic_string opIndexOpAssign(string op)(T c, size_t index)          { mixin("as_array[index] " ~ op ~ "= c;"); return this; }
  225     ///
  226     ref basic_string opIndexOpAssign(string op)(T c, size_t[2] slice)       { mixin("as_array[slice[0] .. slice[1]] " ~ op ~ "= c;"); return this; }
  227     ///
  228     ref basic_string opIndexOpAssign(string op)(const(T)[] str, size_t[2] slice)    { mixin("as_array[slice[0] .. slice[1]] " ~ op ~ "= str[];"); return this; }
  229     ///
  230     ref basic_string opIndexOpAssign(string op)(T c)                        { mixin("as_array[] " ~ op ~ "= c;"); return this; }
  231     ///
  232     ref basic_string opIndexOpAssign(string op)(const(T)[] str)             { mixin("as_array[] " ~ op ~ "= str[];"); return this; }
  233     ///
  234     ref basic_string append(T c)                                            { return append((&c)[0 .. 1]); }
  235     ///
  236     ref basic_string opOpAssign(string op : "~")(const(T)[] str)            { return append(str); }
  237     ///
  238     ref basic_string opOpAssign(string op : "~")(T c)                       { return append((&c)[0 .. 1]); }
  239 
  240     ///
  241     ref basic_string insert(size_type pos, ref const(basic_string) str)     { return insert(pos, str.data(), str.size()); }
  242     ///
  243     ref basic_string insert(size_type pos, ref const(basic_string) str, size_type subpos, size_type sublen) @trusted
  244     {
  245         const _strsz = str.size();
  246         assert(subpos <= _strsz);
  247 //        if (subpos > _strsz)
  248 //            throw new RangeError("subpos exceeds length of str");
  249         return insert(pos, str.data() + subpos, min(sublen, _strsz - subpos));
  250     }
  251     ///
  252     ref basic_string insert(S : size_type)(S pos, const(T)* s)
  253     {
  254         // This overload is declared as a template to give precedence to the slice overload const(T)[] in case of conflict.
  255         assert(s);
  256         return insert(pos, s, traits_type.length(s));
  257     }
  258     ///
  259     ref basic_string insert(size_type pos, const(T)[] s)                    { insert(pos, &s[0], s.length); return this; }
  260 
  261     ///
  262     ref basic_string erase(size_type pos = 0) // TODO: bounds-check
  263     {
  264 //        _My_data._Check_offset(pos);
  265         eos(pos);
  266         return this;
  267     }
  268     ///
  269     ref basic_string erase(size_type pos, size_type len) // TODO: bounds-check
  270     {
  271 //        _My_data._Check_offset(pos);
  272         T[] str = as_array();
  273         size_type new_len = str.length - len;
  274         this[pos .. new_len] = this[pos + len .. str.length]; // TODO: should be memmove!
  275         eos(new_len);
  276         return this;
  277     }
  278 
  279     ///
  280     ref basic_string replace()(size_type pos, size_type len, auto ref basic_string str)     { return replace(pos, len, str.data(), str.size()); }
  281     ///
  282     ref basic_string replace()(size_type pos, size_type len, auto ref basic_string str,
  283                             size_type subpos, size_type sublen=npos)
  284     {
  285         size_type strsz = str.size();
  286         assert(subpos <= strsz);
  287 //        if (subpos > strsz)
  288 //            throw new RangeError("subpos exceeds size of str");
  289         return replace(pos, len, str.data() + subpos, min(sublen, strsz - subpos));
  290     }
  291     ///
  292     ref basic_string replace(size_type pos, size_type len, const(value_type)[] s)           { return replace(pos, len, s.ptr, s.length); }
  293     ///
  294     ref basic_string replace(S : size_type)(S pos, size_type len, const(value_type)* s)
  295     {
  296         // This overload is declared as a template to give precedence to the slice overload const(T)[] in case of conflict.
  297         assert(s !is null, "string::replace received null");
  298         return replace(pos, len, s, traits_type.length(s));
  299     }
  300 
  301     ///
  302     void push_back(T c) @trusted                                            { append((&c)[0 .. 1]); }
  303     ///
  304     void pop_back()                                                         { erase(size() - 1); }
  305 
  306     version (CppRuntime_Microsoft)
  307     {
  308         //----------------------------------------------------------------------------------
  309         // Microsoft runtime
  310         //----------------------------------------------------------------------------------
  311 
  312         ///
  313         this(DefaultConstruct)                                              { _Alloc_proxy(); _Tidy_init(); }
  314         ///
  315         this(const(T)[] str)                                                { _Alloc_proxy(); _Tidy_init(); assign(str); }
  316         ///
  317         this(const(T)[] str, ref const(allocator_type) al)                  { _Alloc_proxy(); _AssignAllocator(al); _Tidy_init(); assign(str); }
  318         ///
  319         this(this)
  320         {
  321             _Alloc_proxy();
  322             if (_Get_data()._IsAllocated())
  323             {
  324                 T[] _Str = _Get_data()._Mystr;
  325                 _Tidy_init();
  326                 assign(_Str);
  327             }
  328         }
  329 
  330         ///
  331         ~this()                                                             { _Tidy_deallocate(); }
  332 
  333         ///
  334         ref inout(Alloc) get_allocator() inout                              { return _Getal(); }
  335 
  336         ///
  337         size_type max_size() const nothrow @safe                            { return ((size_t.max / T.sizeof) - 1) / 2; } // HACK: clone the windows version precisely?
  338 
  339         ///
  340         size_type size() const nothrow @safe                                { return _Get_data()._Mysize; }
  341         ///
  342         size_type capacity() const nothrow @safe                            { return _Get_data()._Myres; }
  343         ///
  344         inout(T)* data() inout @safe                                        { return _Get_data()._Myptr; }
  345         ///
  346         inout(T)[] as_array() inout nothrow @trusted                        { return _Get_data()._Myptr[0 .. _Get_data()._Mysize]; }
  347         ///
  348         ref inout(T) at(size_type i) inout nothrow @trusted                 { return _Get_data()._Myptr[0 .. _Get_data()._Mysize][i]; }
  349 
  350         ///
  351         ref basic_string assign(const(T)[] str)
  352         {
  353             size_type _Count = str.length;
  354             auto _My_data = &_Get_data();
  355             if (_Count <= _My_data._Myres)
  356             {
  357                 T* _Old_ptr = _My_data._Myptr;
  358                 _My_data._Mysize = _Count;
  359                 _Old_ptr[0 .. _Count] = str[]; // TODO: this needs to be a memmove(), does that work here?
  360                 _Old_ptr[_Count] = T(0);
  361                 return this;
  362             }
  363             return _Reallocate_for(_Count, (T* _New_ptr, size_type _Count, const(T)* _Ptr) nothrow {
  364                 _New_ptr[0 .. _Count] = _Ptr[0 .. _Count];
  365                 _New_ptr[_Count] = T(0);
  366             }, str.ptr);
  367         }
  368 
  369         ///
  370         ref basic_string assign(const ref basic_string str)
  371         {
  372             if (&this != &str)
  373                 assign(str.as_array);
  374             return this;
  375         }
  376 
  377         ///
  378         ref basic_string append(const(T)[] str)
  379         {
  380             size_type _Count = str.length;
  381             auto _My_data = &_Get_data();
  382             size_type _Old_size = _My_data._Mysize;
  383             if (_Count <= _My_data._Myres - _Old_size)
  384             {
  385                 pointer _Old_ptr = _My_data._Myptr;
  386                 _My_data._Mysize = _Old_size + _Count;
  387                 _Old_ptr[_Old_size .. _Old_size + _Count] = str[]; // TODO: this needs to be a memmove(), does that work here?
  388                 _Old_ptr[_Old_size + _Count] = T(0);
  389                 return this;
  390             }
  391             return _Reallocate_grow_by(_Count, (T* _New_ptr, const(T)[] _Old_str, const(T)[] _Str) {
  392                 _New_ptr[0 .. _Old_str.length] = _Old_str[];
  393                 _New_ptr[_Old_str.length .. _Old_str.length + _Str.length] = _Str[];
  394                 _New_ptr[_Old_str.length + _Str.length] = T(0);
  395             }, str);
  396         }
  397 
  398         ///
  399         ref basic_string append(size_type n, T c)
  400         {
  401             alias _Count = n;
  402             alias _Ch = c;
  403             auto _My_data = &_Get_data();
  404             const size_type _Old_size = _My_data._Mysize;
  405             if (_Count <= _My_data._Myres - _Old_size)
  406             {
  407                 _My_data._Mysize = _Old_size + _Count;
  408                 pointer _Old_ptr = _My_data._Myptr();
  409                 _Old_ptr[_Old_size .. _Old_size + _Count] = _Ch;
  410                 _Old_ptr[_Old_size + _Count] = T(0);
  411                 return this;
  412             }
  413 
  414             return _Reallocate_grow_by(_Count, (T* _New_ptr, const(T)[] _Old_str, size_type _Count, T _Ch) {
  415                 _New_ptr[0 .. _Old_str.length] = _Old_str[];
  416                 _New_ptr[_Old_str.length .. _Old_str.length + _Count] = _Ch;
  417                 _New_ptr[_Old_str.length + _Count] = T(0);
  418             }, _Count, _Ch);
  419         }
  420 
  421         ///
  422         void reserve(size_type _Newcap = 0)
  423         {
  424             // determine new minimum length of allocated storage
  425 
  426             auto _My_data = &_Get_data();
  427 
  428             if (_My_data._Mysize > _Newcap)
  429             {
  430                 // requested capacity is not large enough for current size, ignore
  431                 return; // nothing to do
  432             }
  433 
  434             if (_My_data._Myres == _Newcap)
  435             {
  436                 // we're already at the requested capacity
  437                 return; // nothing to do
  438             }
  439 
  440             if (_My_data._Myres < _Newcap)
  441             {
  442                 // reallocate to grow
  443                 const size_type _Old_size = _My_data._Mysize;
  444                 _Reallocate_grow_by(
  445                     _Newcap - _Old_size, (T* _New_ptr, const(T)[] _Old_str) {
  446                         _New_ptr[0 .. _Old_str.length] = _Old_str[];
  447                         _New_ptr[_Old_str.length] = _Old_str.ptr[_Old_str.length];
  448                     });
  449 
  450                 _My_data._Mysize = _Old_size;
  451                 return;
  452             }
  453 
  454             if (_My_data._BUF_SIZE > _Newcap && _My_data._Large_string_engaged())
  455             {
  456                 // deallocate everything; switch back to "small" mode
  457                 _Become_small();
  458                 return;
  459             }
  460 
  461             // ignore requests to reserve to [_BUF_SIZE, _Myres)
  462         }
  463 
  464         ///
  465         void shrink_to_fit()
  466         {
  467             // reduce capacity
  468 
  469             auto _My_data = &_Get_data();
  470             if (!_My_data._Large_string_engaged())
  471             {
  472                 // can't shrink from small mode
  473                 return;
  474             }
  475 
  476             if (_My_data._Mysize < _My_data._BUF_SIZE)
  477             {
  478                 _Become_small();
  479                 return;
  480             }
  481 
  482             const size_type _Target_capacity = min(_My_data._Mysize | _My_data._ALLOC_MASK, max_size());
  483             if (_Target_capacity < _My_data._Myres)
  484             {
  485                 // worth shrinking, do it
  486                 auto _Al = &_Getal();
  487                 pointer _New_ptr = _Al.allocate(_Target_capacity + 1); // throws
  488                 _Base._Orphan_all();
  489                 _New_ptr[0 .. _My_data._Mysize + 1] = _My_data._Bx._Ptr[0 .. _My_data._Mysize + 1];
  490                 _Al.deallocate(_My_data._Bx._Ptr, _My_data._Myres + 1);
  491                 _My_data._Bx._Ptr = _New_ptr;
  492                 _My_data._Myres = _Target_capacity;
  493             }
  494         }
  495 
  496         ///
  497         ref basic_string insert(size_type pos, const(T)* s, size_type n)
  498         {
  499             // insert [_Ptr, _Ptr + _Count) at _Off
  500             alias _Off = pos;
  501             alias _Ptr = s;
  502             alias _Count = n;
  503             auto _My_data = &_Get_data();
  504 //            _My_data._Check_offset(_Off);
  505             const size_type _Old_size = _My_data._Mysize;
  506             if (_Count <= _My_data._Myres - _Old_size)
  507             {
  508                 _My_data._Mysize = _Old_size + _Count;
  509                 T* _Old_ptr = _My_data._Myptr();
  510                 T* _Insert_at = _Old_ptr + _Off;
  511                 // the range [_Ptr, _Ptr + _Ptr_shifted_after) is left alone by moving the suffix out,
  512                 // while the range [_Ptr + _Ptr_shifted_after, _Ptr + _Count) shifts down by _Count
  513                 size_type _Ptr_shifted_after;
  514                 if (_Ptr + _Count <= _Insert_at || _Ptr > _Old_ptr + _Old_size)
  515                 {
  516                     // inserted content is before the shifted region, or does not alias
  517                     _Ptr_shifted_after = _Count; // none of _Ptr's data shifts
  518                 }
  519                 else if (_Insert_at <= _Ptr)
  520                 {
  521                     // all of [_Ptr, _Ptr + _Count) shifts
  522                     _Ptr_shifted_after = 0;
  523                 }
  524                 else
  525                 {
  526                     // [_Ptr, _Ptr + _Count) contains _Insert_at, so only the part after _Insert_at shifts
  527                     _Ptr_shifted_after = cast(size_type)(_Insert_at - _Ptr);
  528                 }
  529 
  530                 _Traits.move(_Insert_at + _Count, _Insert_at, _Old_size - _Off + 1); // move suffix + null down
  531                 _Insert_at[0 .. _Ptr_shifted_after] = _Ptr[0 .. _Ptr_shifted_after];
  532                 (_Insert_at + _Ptr_shifted_after)[0 .. _Count - _Ptr_shifted_after] = (_Ptr + _Count + _Ptr_shifted_after)[0 .. _Count - _Ptr_shifted_after];
  533                 return this;
  534             }
  535 
  536             return _Reallocate_grow_by(
  537                 _Count,
  538                 (T* _New_ptr, const(T)[] _Old_str, size_type _Off, const(T)* _Ptr, size_type _Count) {
  539                     _New_ptr[0 .. _Off] = _Old_str[0 .. _Off];
  540                     _New_ptr[_Off .. _Off + _Count] = _Ptr[0 .. _Count];
  541                     _New_ptr[_Off + _Count .. _Old_str.length + _Count + 1] = _Old_str.ptr[_Off .. _Old_str.length + 1];
  542                 },
  543                 _Off, _Ptr, _Count);
  544         }
  545 
  546         ///
  547         ref basic_string insert(size_type pos, size_type n, T c)
  548         {
  549             // insert _Count * _Ch at _Off
  550             alias _Off = pos;
  551             alias _Count = n;
  552             alias _Ch = c;
  553             auto _My_data = &_Get_data();
  554 //            _My_data._Check_offset(_Off);
  555             const size_type _Old_size = _My_data._Mysize;
  556             if (_Count <= _My_data._Myres - _Old_size)
  557             {
  558                 _My_data._Mysize = _Old_size + _Count;
  559                 T* _Old_ptr = _My_data._Myptr();
  560                 T* _Insert_at = _Old_ptr + _Off;
  561                 _Traits.move(_Insert_at + _Count, _Insert_at, _Old_size - _Off + 1); // move suffix + null down
  562                 _Insert_at[0 .. _Count] = _Ch; // fill hole
  563                 return this;
  564             }
  565 
  566             return _Reallocate_grow_by(
  567                 _Count,
  568                 (T* _New_ptr, const(T)[] _Old_str, size_type _Off, size_type _Count, T _Ch)
  569                 {
  570                     _New_ptr[0 .. _Off] = _Old_str[0 .. _Off];
  571                     _New_ptr[_Off .. _Off + _Count] = _Ch;
  572                     _New_ptr[_Off + _Count .. _Old_str.length + 1] = _Old_str.ptr[_Off .. _Old_str.length + 1];
  573                 },
  574                 _Off, _Count, _Ch);
  575         }
  576 
  577         ///
  578         ref basic_string replace(size_type pos, size_type len, const(T)* s, size_type slen)
  579         {
  580             // replace [_Off, _Off + _N0) with [_Ptr, _Ptr + _Count)
  581             alias _Off = pos;
  582             alias _N0 = len;
  583             alias _Ptr = s;
  584             alias _Count = slen;
  585             auto _My_data = &_Get_data();
  586 //            _Mypair._Myval2._Check_offset(_Off);
  587             _N0 = _My_data._Clamp_suffix_size(_Off, _N0);
  588             if (_N0 == _Count)
  589             {
  590                 // size doesn't change, so a single move does the trick
  591                 _Traits.move(_My_data._Myptr() + _Off, _Ptr, _Count);
  592                 return this;
  593             }
  594 
  595             const size_type _Old_size = _My_data._Mysize;
  596             const size_type _Suffix_size = _Old_size - _N0 - _Off + 1;
  597             if (_Count < _N0)
  598             {
  599                 // suffix shifts backwards; we don't have to move anything out of the way
  600                 _My_data._Mysize = _Old_size - (_N0 - _Count);
  601                 T* _Old_ptr = _My_data._Myptr();
  602                 T* _Insert_at = _Old_ptr + _Off;
  603                 _Traits.move(_Insert_at, _Ptr, _Count);
  604                 _Traits.move(_Insert_at + _Count, _Insert_at + _N0, _Suffix_size);
  605                 return this;
  606             }
  607 
  608             const size_type _Growth = cast(size_type)(_Count - _N0);
  609             if (_Growth <= _My_data._Myres - _Old_size)
  610             {
  611                 // growth fits
  612                 _My_data._Mysize = _Old_size + _Growth;
  613                 T* _Old_ptr = _My_data._Myptr();
  614                 T* _Insert_at = _Old_ptr + _Off;
  615                 T* _Suffix_at = _Insert_at + _N0;
  616 
  617                 size_type _Ptr_shifted_after; // see rationale in insert
  618                 if (_Ptr + _Count <= _Insert_at || _Ptr > _Old_ptr + _Old_size)
  619                     _Ptr_shifted_after = _Count;
  620                 else if (_Suffix_at <= _Ptr)
  621                     _Ptr_shifted_after = 0;
  622                 else
  623                     _Ptr_shifted_after = cast(size_type)(_Suffix_at - _Ptr);
  624 
  625                 _Traits.move(_Suffix_at + _Growth, _Suffix_at, _Suffix_size);
  626                 // next case must be move, in case _Ptr begins before _Insert_at and contains part of the hole;
  627                 // this case doesn't occur in insert because the new content must come from outside the removed
  628                 // content there (because in insert there is no removed content)
  629                 _Traits.move(_Insert_at, _Ptr, _Ptr_shifted_after);
  630                 // the next case can be copy, because it comes from the chunk moved out of the way in the
  631                 // first move, and the hole we're filling can't alias the chunk we moved out of the way
  632                 _Insert_at[_Ptr_shifted_after .. _Count] = _Ptr[_Growth + _Ptr_shifted_after .. _Growth + _Count];
  633                 return this;
  634             }
  635 
  636             return _Reallocate_grow_by(
  637                 _Growth,
  638                 (T* _New_ptr, const(T)[] _Old_str, size_type _Off, size_type _N0, const(T)* _Ptr, size_type _Count) {
  639                     _New_ptr[0 .. _Off] = _Old_str[0 .. _Off];
  640                     _New_ptr[_Off .. _Count] = _Ptr[0 .. _Count];
  641                     const __n = _Old_str.length - _N0 - _Off + 1;
  642                     (_New_ptr + _Off + _Count)[0 .. __n] = (_Old_str.ptr + _Off + _N0)[0 .. __n];
  643                 },
  644                 _Off, _N0, _Ptr, _Count);
  645         }
  646 
  647         ///
  648         ref basic_string replace(size_type _Off, size_type _N0, size_type _Count, T _Ch)
  649         {
  650             // replace [_Off, _Off + _N0) with _Count * _Ch
  651             auto _My_data = &_Get_data();
  652 //            _My_data._Check_offset(_Off);
  653             _N0 = _My_data._Clamp_suffix_size(_Off, _N0);
  654             if (_Count == _N0)
  655             {
  656                 _My_data._Myptr()[_Off .. _Off + _Count] = _Ch;
  657                 return this;
  658             }
  659 
  660             const size_type _Old_size = _My_data._Mysize;
  661             if (_Count < _N0 || _Count - _N0 <= _My_data._Myres - _Old_size)
  662             {
  663                 // either we are shrinking, or the growth fits
  664                 _My_data._Mysize = _Old_size + _Count - _N0; // may temporarily overflow;
  665                                                                     // OK because size_type must be unsigned
  666                 T* _Old_ptr = _My_data._Myptr();
  667                 T* _Insert_at = _Old_ptr + _Off;
  668                 _Traits.move(_Insert_at + _Count, _Insert_at + _N0, _Old_size - _N0 - _Off + 1);
  669                 _Insert_at[0 .. _Count] = _Ch;
  670                 return this;
  671             }
  672 
  673             return _Reallocate_grow_by(
  674                 _Count - _N0,
  675                 (T* _New_ptr, const(T)[] _Old_str, size_type _Off, size_type _N0, size_type _Count, T _Ch) {
  676                     _New_ptr[0 .. _Off] = _Old_str[0 .. _Off];
  677                     _New_ptr[_Off .. _Off + _Count] = _Ch;
  678                     const __n = _Old_str.length - _N0 - _Off + 1;
  679                     (_New_ptr + _Off + _Count)[0 .. __n] = (_Old_str.ptr + _Off + _N0)[0 .. __n];
  680                 },
  681                 _Off, _N0, _Count, _Ch);
  682         }
  683 
  684         ///
  685         void swap(ref basic_string _Right)
  686         {
  687             import core.internal.lifetime : swap;
  688             import core.stdcpp.type_traits : is_empty;
  689 
  690             if (&this != &_Right)
  691             {
  692                 static if (!is_empty!allocator_type.value
  693                         && allocator_traits!allocator_type.propagate_on_container_swap)
  694                 {
  695                     swap(_Getal(), _Right._Getal());
  696                 }
  697 
  698                 static if (_ITERATOR_DEBUG_LEVEL != 0)
  699                 {
  700                     auto _My_data = &_Get_data();
  701                     const bool _My_large = _My_data._Large_string_engaged();
  702                     const bool _Right_large = _Right._Get_data()._Large_string_engaged();
  703                     if (!_My_large)
  704                         _Base._Orphan_all();
  705 
  706                     if (!_Right_large)
  707                         _Right._Base._Orphan_all();
  708 
  709                     if (_My_large || _Right_large)
  710                         _My_data._Base._Swap_proxy_and_iterators(_Right._Get_data()._Base);
  711                 } // _ITERATOR_DEBUG_LEVEL != 0
  712             }
  713 
  714             _Swap_data!_Can_memcpy_val(_Right);
  715         }
  716 
  717     private:
  718         import core.stdcpp.xutility : MSVCLinkDirectives;
  719         import core.stdcpp.xutility : _Container_base;
  720 
  721         alias _Traits = traits_type;
  722         alias _Scary_val = _String_val!T;
  723 
  724         enum bool _Can_memcpy_val = is(_Traits == char_traits!E, E) && is(pointer == U*, U);
  725         // This offset skips over the _Container_base members, if any
  726         enum size_t _Memcpy_val_offset = _Size_after_ebco_v!_Container_base;
  727         enum size_t _Memcpy_val_size   = _Scary_val.sizeof - _Memcpy_val_offset;
  728 
  729         // Make sure the object files wont link against mismatching objects
  730         mixin MSVCLinkDirectives!true;
  731 
  732         pragma (inline, true)
  733         {
  734             void eos(size_type offset) nothrow                              { _Get_data()._Myptr[_Get_data()._Mysize = offset] = T(0); }
  735 
  736             ref inout(_Base.Alloc) _Getal() inout nothrow @safe             { return _Base._Mypair._Myval1; }
  737             ref inout(_Base.ValTy) _Get_data() inout nothrow @safe          { return _Base._Mypair._Myval2; }
  738         }
  739 
  740         void _Alloc_proxy() nothrow
  741         {
  742             static if (_ITERATOR_DEBUG_LEVEL > 0)
  743                 _Base._Alloc_proxy();
  744         }
  745 
  746         void _AssignAllocator(ref const(allocator_type) al) nothrow
  747         {
  748             static if (_Base._Mypair._HasFirst)
  749                 _Getal() = al;
  750         }
  751 
  752         void _Become_small()
  753         {
  754             // release any held storage and return to small string mode
  755             // pre: *this is in large string mode
  756             // pre: this is small enough to return to small string mode
  757             auto _My_data = &_Get_data();
  758             _Base._Orphan_all();
  759             pointer _Ptr = _My_data._Bx._Ptr;
  760             auto _Al = &_Getal();
  761             _My_data._Bx._Buf[0 .. _My_data._Mysize + 1] = _Ptr[0 .. _My_data._Mysize + 1];
  762             _Al.deallocate(_Ptr, _My_data._Myres + 1);
  763             _My_data._Myres = _My_data._BUF_SIZE - 1;
  764         }
  765 
  766         void _Tidy_init() nothrow
  767         {
  768             auto _My_data = &_Get_data();
  769             _My_data._Mysize = 0;
  770             _My_data._Myres = _My_data._BUF_SIZE - 1;
  771             _My_data._Bx._Buf[0] = T(0);
  772         }
  773 
  774         size_type _Calculate_growth(size_type _Requested) const nothrow
  775         {
  776             auto _My_data = &_Get_data();
  777             size_type _Masked = _Requested | _My_data._ALLOC_MASK;
  778             size_type _Old = _My_data._Myres;
  779             size_type _Expanded = _Old + _Old / 2;
  780             return _Masked > _Expanded ? _Masked : _Expanded;
  781         }
  782 
  783         ref basic_string _Reallocate_for(_ArgTys...)(size_type _New_size, void function(pointer, size_type, _ArgTys) nothrow @nogc _Fn, _ArgTys _Args)
  784         {
  785             auto _My_data = &_Get_data();
  786             size_type _Old_capacity = _My_data._Myres;
  787             size_type _New_capacity = _Calculate_growth(_New_size);
  788             auto _Al = &_Getal();
  789             pointer _New_ptr = _Al.allocate(_New_capacity + 1); // throws
  790             _Base._Orphan_all();
  791             _My_data._Mysize = _New_size;
  792             _My_data._Myres = _New_capacity;
  793             _Fn(_New_ptr, _New_size, _Args);
  794             if (_My_data._BUF_SIZE <= _Old_capacity)
  795                 _Al.deallocate(_My_data._Bx._Ptr, _Old_capacity + 1);
  796             _My_data._Bx._Ptr = _New_ptr;
  797             return this;
  798         }
  799 
  800         ref basic_string _Reallocate_grow_by(_ArgTys...)(size_type _Size_increase, void function(pointer, const(T)[], _ArgTys) nothrow @nogc _Fn, _ArgTys _Args)
  801         {
  802             auto _My_data = &_Get_data();
  803             size_type _Old_size = _My_data._Mysize;
  804             size_type _New_size = _Old_size + _Size_increase;
  805             size_type _Old_capacity = _My_data._Myres;
  806             size_type _New_capacity = _Calculate_growth(_New_size);
  807             auto _Al = &_Getal();
  808             pointer _New_ptr = _Al.allocate(_New_capacity + 1); // throws
  809             _Base._Orphan_all();
  810             _My_data._Mysize = _New_size;
  811             _My_data._Myres = _New_capacity;
  812             if (_My_data._BUF_SIZE <= _Old_capacity)
  813             {
  814                 pointer _Old_ptr = _My_data._Bx._Ptr;
  815                 _Fn(_New_ptr, _Old_ptr[0 .. _Old_size], _Args);
  816                 _Al.deallocate(_Old_ptr, _Old_capacity + 1);
  817             }
  818             else
  819                 _Fn(_New_ptr, _My_data._Bx._Buf[0 .. _Old_size], _Args);
  820             _My_data._Bx._Ptr = _New_ptr;
  821             return this;
  822         }
  823 
  824         void _Tidy_deallocate()
  825         {
  826             _Base._Orphan_all();
  827             auto _My_data = &_Get_data();
  828             if (_My_data._BUF_SIZE <= _My_data._Myres)
  829             {
  830                 pointer _Ptr = _My_data._Bx._Ptr;
  831                 auto _Al = &_Getal();
  832                 _Al.deallocate(_Ptr, _My_data._Myres + 1);
  833             }
  834             _My_data._Mysize = 0;
  835             _My_data._Myres = _My_data._BUF_SIZE - 1;
  836             _My_data._Bx._Buf[0] = T(0);
  837         }
  838 
  839         void _Swap_data(bool _memcpy : true)(ref basic_string _Right)
  840         {
  841             import core.stdc.string : memcpy;
  842 
  843             // exchange _String_val instances with _Right, memcpy optimization
  844             auto _My_data = &_Get_data();
  845             auto _My_data_mem = cast(ubyte*)_My_data + _Memcpy_val_offset;
  846             auto _Right_data_mem = cast(ubyte*)(&_Right._Get_data()) + _Memcpy_val_offset;
  847             ubyte[_Memcpy_val_size] _Temp_mem;
  848             memcpy(_Temp_mem.ptr, _My_data_mem, _Memcpy_val_size);
  849             memcpy(_My_data_mem, _Right_data_mem, _Memcpy_val_size);
  850             memcpy(_Right_data_mem, _Temp_mem.ptr, _Memcpy_val_size);
  851         }
  852 
  853         void _Swap_data(bool _memcpy : false)(ref basic_string _Right)
  854         {
  855             import core.lifetime : swap;
  856 
  857             // exchange _String_val instances with _Right, general case
  858             auto _My_data = &_Get_data();
  859             auto _Right_data = &_Right._Get_data();
  860             const bool _My_large = _My_data._Large_string_engaged();
  861             const bool _Right_large = _Right_data._Large_string_engaged();
  862             if (_My_large)
  863             {
  864                 if (_Right_large) // swap buffers, iterators preserved
  865                     swap(_My_data._Bx._Ptr, _Right_data._Bx._Ptr);
  866                 else // swap large with small
  867                     _Swap_bx_large_with_small(*_My_data, *_Right_data);
  868             }
  869             else
  870             {
  871                 if (_Right_large) // swap small with large
  872                     _Swap_bx_large_with_small(*_Right_data, *_My_data);
  873                 else
  874                 {
  875                     enum _BUF_SIZE = _My_data._BUF_SIZE;
  876                     T[_BUF_SIZE] _Temp_buf;
  877                     _Temp_buf[0 .. _BUF_SIZE] = _My_data._Bx._Buf[0 .. _BUF_SIZE];
  878                     _My_data._Bx._Buf[0 .. _BUF_SIZE] = _Right_data._Bx._Buf[0 .. _BUF_SIZE];
  879                     _Right_data._Bx._Buf[0 .. _BUF_SIZE] = _Temp_buf[0 .. _BUF_SIZE];
  880                 }
  881             }
  882 
  883             swap(_My_data._Mysize, _Right_data._Mysize);
  884             swap(_My_data._Myres, _Right_data._Myres);
  885         }
  886 
  887         void _Swap_bx_large_with_small(ref _Scary_val _Starts_large, ref _Scary_val _Starts_small)
  888         {
  889             // exchange a string in large mode with one in small mode
  890             pointer _Ptr = _Starts_large._Bx._Ptr;
  891             _Starts_large._Bx._Buf[] = _Starts_small._Bx._Buf[];
  892             _Starts_small._Bx._Ptr = _Ptr;
  893         }
  894 
  895         _String_alloc!(_String_base_types!(T, Alloc)) _Base;
  896     }
  897     else version (CppRuntime_Gcc)
  898     {
  899         version (_GLIBCXX_USE_CXX98_ABI)
  900         {
  901             //----------------------------------------------------------------------------------
  902             // Old GCC/libstdc++ ref-counted implementation
  903             //----------------------------------------------------------------------------------
  904 
  905             ///
  906             this(DefaultConstruct)
  907             {
  908                 version (_GLIBCXX_FULLY_DYNAMIC_STRING)
  909                     static_assert(false, "DO WE NEED THIS?");
  910                 else
  911                     _M_data = _S_empty_rep()._M_refdata();
  912             }
  913             ///
  914             this(const(T)[] str, ref const(allocator_type) al)                  { _M_assign_allocator(al); this(str); }
  915             ///
  916             this(const(T)[] str)
  917             {
  918                 _M_data = _S_construct(str.ptr, str.ptr + str.length, _M_get_allocator);
  919             }
  920             ///
  921             this(const ref basic_string str)
  922             {
  923                 import core.stdcpp.type_traits : is_empty;
  924 
  925                 static if (!is_empty!allocator_type.value)
  926                     _M_Alloc = str.get_allocator();
  927                 _M_data = str._M_rep()._M_grab(get_allocator(), str.get_allocator());
  928             }
  929 
  930             ///
  931             ~this()                                                             { _M_rep()._M_dispose(get_allocator()); }
  932 
  933             ///
  934             ref inout(Alloc) get_allocator() inout                              { return _M_get_allocator(); }
  935 
  936             ///
  937             size_type max_size() const nothrow @safe                            { return _Rep._S_max_size; }
  938 
  939             ///
  940             size_type size() const nothrow @safe                                { return _M_rep()._M_length; }
  941             ///
  942             size_type capacity() const nothrow                                  { return _M_rep()._M_capacity; }
  943             ///
  944             inout(T)* data() inout @safe                                        { return _M_data; }
  945             ///
  946             inout(T)[] as_array() inout nothrow @trusted                        { return _M_data[0 .. _M_rep()._M_length]; }
  947             ///
  948             ref inout(T) at(size_type i) inout nothrow                          { return _M_data[0 .. _M_rep()._M_length][i]; }
  949 
  950             ///
  951             ref basic_string assign(const(T)[] str)
  952             {
  953                 const(T)* __s = str.ptr;
  954                 size_t __n = str.length;
  955 //                __glibcxx_requires_string_len(__s, __n);
  956                 _M_check_length(size(), __n, "basic_string::assign");
  957                 if (_M_disjunct(__s) || _M_rep()._M_is_shared())
  958                     return _M_replace_safe(size_type(0), this.size(), __s, __n);
  959                 else
  960                 {
  961                     const size_type __pos = __s - _M_data;
  962                     if (__pos >= __n)
  963                         _S_copy(_M_data, __s, __n);
  964                     else if (__pos)
  965                         _S_move(_M_data, __s, __n);
  966                     _M_rep()._M_set_length_and_sharable(__n);
  967                     return this;
  968                 }
  969             }
  970 
  971             ///
  972             ref basic_string assign(const ref basic_string str)
  973             {
  974                 if (_M_rep() != str._M_rep())
  975                 {
  976                     // XXX MT
  977                     allocator_type __a = this.get_allocator();
  978                     T* __tmp = str._M_rep()._M_grab(__a, str.get_allocator());
  979                     _M_rep()._M_dispose(__a);
  980                     _M_data = __tmp;
  981                 }
  982                 return this;
  983             }
  984 
  985             ///
  986             ref basic_string append(const(T)[] str)
  987             {
  988                 const(T)* __s = str.ptr;
  989                 size_t __n = str.length;
  990 //                __glibcxx_requires_string_len(__s, __n);
  991                 if (__n)
  992                 {
  993                     _M_check_length(size_type(0), __n, "basic_string::append");
  994                     const size_type __len = __n + size();
  995                     if (__len > capacity() || _M_rep()._M_is_shared())
  996                     {
  997                         if (_M_disjunct(__s))
  998                             reserve(__len);
  999                         else
 1000                         {
 1001                             const size_type __off = __s - _M_data;
 1002                             reserve(__len);
 1003                             __s = _M_data + __off;
 1004                         }
 1005                     }
 1006                     _S_copy(_M_data + size(), __s, __n);
 1007                     _M_rep()._M_set_length_and_sharable(__len);
 1008                 }
 1009                 return this;
 1010             }
 1011 
 1012             ///
 1013             ref basic_string append(size_type __n, T __c)
 1014             {
 1015                 if (__n)
 1016                 {
 1017                     _M_check_length(size_type(0), __n, "basic_string::append");
 1018                     const size_type __len = __n + size();
 1019                     if (__len > capacity() || _M_rep()._M_is_shared())
 1020                         reserve(__len);
 1021                     const __sz = size();
 1022                     _M_data[__sz .. __sz + __n] = __c;
 1023                     _M_rep()._M_set_length_and_sharable(__len);
 1024                 }
 1025                 return this;
 1026             }
 1027 
 1028             ///
 1029             void reserve(size_type __res = 0)
 1030             {
 1031                 if (__res != capacity() || _M_rep()._M_is_shared())
 1032                 {
 1033                     // Make sure we don't shrink below the current size
 1034                     if (__res < size())
 1035                         __res = size();
 1036                     allocator_type __a = get_allocator();
 1037                     T* __tmp = _M_rep()._M_clone(__a, __res - size());
 1038                     _M_rep()._M_dispose(__a);
 1039                     _M_data = __tmp;
 1040                 }
 1041             }
 1042 
 1043             ///
 1044             void shrink_to_fit() nothrow
 1045             {
 1046                 if (capacity() > size())
 1047                 {
 1048                     try reserve(0);
 1049                     catch (Throwable) {}
 1050                 }
 1051             }
 1052 
 1053             ///
 1054             ref basic_string insert(size_type __pos, const(T)* __s, size_type __n)
 1055             {
 1056 //                __glibcxx_requires_string_len(__s, __n);
 1057                 cast(void) _M_check(__pos, "basic_string::insert");
 1058                 _M_check_length(size_type(0), __n, "basic_string::insert");
 1059                 if (_M_disjunct(__s) || _M_rep()._M_is_shared())
 1060                     return _M_replace_safe(__pos, size_type(0), __s, __n);
 1061                 else
 1062                 {
 1063                     // Work in-place.
 1064                     const size_type __off = __s - _M_data;
 1065                     _M_mutate(__pos, 0, __n);
 1066                     __s = _M_data + __off;
 1067                     T* __p = _M_data + __pos;
 1068                     if (__s  + __n <= __p)
 1069                         __p[0 .. __n] = __s[0 .. __n];
 1070                     else if (__s >= __p)
 1071                         __p[0 .. __n] = (__s + __n)[0 .. __n];
 1072                     else
 1073                     {
 1074                         const size_type __nleft = __p - __s;
 1075                         __p[0 .. __nleft] = __s[0.. __nleft];
 1076                         (__p + __nleft)[0 .. __n - __nleft] = (__p + __n)[0 .. __n - __nleft];
 1077                     }
 1078                     return this;
 1079                 }
 1080             }
 1081 
 1082             ///
 1083             ref basic_string insert(size_type pos, size_type n, T c)
 1084             {
 1085                 return _M_replace_aux(_M_check(pos, "basic_string::insert"), size_type(0), n, c);
 1086             }
 1087 
 1088             ///
 1089             ref basic_string replace(size_type __pos, size_type __n1, const(T)* __s, size_type __n2)
 1090             {
 1091 //                __glibcxx_requires_string_len(__s, __n2);
 1092                 cast(void) _M_check(__pos, "basic_string::replace");
 1093                 __n1 = _M_limit(__pos, __n1);
 1094                 _M_check_length(__n1, __n2, "basic_string::replace");
 1095                 bool __left;
 1096                 if (_M_disjunct(__s) || _M_rep()._M_is_shared())
 1097                     return _M_replace_safe(__pos, __n1, __s, __n2);
 1098                 else if ((__left = __s + __n2 <= _M_data + __pos) == true || _M_data + __pos + __n1 <= __s)
 1099                 {
 1100                     // Work in-place: non-overlapping case.
 1101                     size_type __off = __s - _M_data;
 1102                     __left ? __off : (__off += __n2 - __n1);
 1103                     _M_mutate(__pos, __n1, __n2);
 1104                     (_M_data + __pos)[0 .. __n2] = (_M_data + __off)[0 .. __n2];
 1105                     return this;
 1106                 }
 1107                 else
 1108                 {
 1109                     // Todo: overlapping case.
 1110                     auto __tmp = basic_string(__s[0 .. __n2]);
 1111                     return _M_replace_safe(__pos, __n1, __tmp._M_data, __n2);
 1112                 }
 1113             }
 1114 
 1115             ///
 1116             ref basic_string replace(size_type pos, size_type n1, size_type n2, T c)
 1117             {
 1118                 return _M_replace_aux(_M_check(pos, "basic_string::replace"), _M_limit(pos, n1), n2, c);
 1119             }
 1120 
 1121             ///
 1122             void swap(ref basic_string __s)
 1123             {
 1124                 if (_M_rep()._M_is_leaked())
 1125                     _M_rep()._M_set_sharable();
 1126                 if (__s._M_rep()._M_is_leaked())
 1127                     __s._M_rep()._M_set_sharable();
 1128                 if (this.get_allocator() == __s.get_allocator())
 1129                 {
 1130                     T* __tmp = _M_data;
 1131                     _M_data = __s._M_data;
 1132                     __s._M_data = __tmp;
 1133                 }
 1134                 // The code below can usually be optimized away.
 1135                 else
 1136                 {
 1137                     import core.lifetime : move;
 1138 
 1139                     auto __tmp1 = basic_string(this[], __s.get_allocator());
 1140                     auto __tmp2 = basic_string(__s[], this.get_allocator());
 1141                     this = move(__tmp2);
 1142                     __s = move(__tmp1);
 1143                 }
 1144             }
 1145 
 1146         private:
 1147             import core.stdcpp.type_traits : is_empty;
 1148 
 1149             version (__GTHREADS)
 1150             {
 1151                 import core.atomic;
 1152                 alias _Atomic_word = int; // should we use atomic!int?
 1153             }
 1154             else
 1155                 alias _Atomic_word = int;
 1156 
 1157             struct _Rep_base
 1158             {
 1159                 size_type       _M_length;
 1160                 size_type       _M_capacity;
 1161                 _Atomic_word    _M_refcount;
 1162             }
 1163 
 1164             struct _Rep
 1165             {
 1166                 _Rep_base base;
 1167                 alias base this;
 1168 
 1169                 alias _Raw_bytes_alloc = Alloc.rebind!char;
 1170 
 1171                 enum size_type _S_max_size = (((npos - _Rep_base.sizeof) / T.sizeof) - 1) / 4;
 1172                 enum T _S_terminal = T(0);
 1173 
 1174                 __gshared size_type[(_Rep_base.sizeof + T.sizeof + size_type.sizeof - 1) / size_type.sizeof] _S_empty_rep_storage;
 1175 
 1176                 static ref _Rep _S_empty_rep() nothrow @trusted { return *cast(_Rep*)_S_empty_rep_storage.ptr; }
 1177 
 1178                 void _M_set_sharable() nothrow
 1179                 {
 1180                     _M_refcount = 0;
 1181                 }
 1182 
 1183                 void _M_set_length_and_sharable(size_type __n) nothrow
 1184                 {
 1185                     if (&this != &_S_empty_rep())
 1186                     {
 1187                         _M_set_sharable();
 1188                         _M_length = __n;
 1189                         _M_refdata()[__n] = _S_terminal;
 1190                     }
 1191                 }
 1192 
 1193                 bool _M_is_leaked() const nothrow
 1194                 {
 1195                     import core.atomic : atomicLoad;
 1196 
 1197                     version (__GTHREADS)
 1198                         return atomicLoad!(MemoryOrder.raw)(this._M_refcount) < 0;
 1199                     else
 1200                         return _M_refcount < 0;
 1201                 }
 1202 //
 1203                 bool _M_is_shared() const nothrow
 1204                 {
 1205                     import core.atomic : atomicLoad;
 1206 
 1207                     version (__GTHREADS)
 1208                         return atomicLoad!(MemoryOrder.acq)(this._M_refcount) > 0;
 1209                     else
 1210                         return _M_refcount > 0;
 1211                 }
 1212 
 1213                 T* _M_refdata() nothrow @trusted    { return cast(T*)(&this + 1); }
 1214 
 1215                 T* _M_grab(ref allocator_type __alloc1, const ref allocator_type __alloc2)
 1216                 {
 1217                     return (!_M_is_leaked() && __alloc1 == __alloc2)
 1218                           ? _M_refcopy() : _M_clone(__alloc1);
 1219                 }
 1220 
 1221                 static _Rep* _S_create(size_type __capacity, size_type __old_capacity, ref Alloc __alloc)
 1222                 {
 1223                     assert(__capacity <= _S_max_size);
 1224 //                    if (__capacity > _S_max_size)
 1225 //                        __throw_length_error(__N("basic_string::_S_create"));
 1226 
 1227                     enum __pagesize = 4096;
 1228                     enum __malloc_header_size = 4 * pointer.sizeof;
 1229 
 1230                     if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
 1231                         __capacity = 2 * __old_capacity;
 1232 
 1233                     size_type __size = (__capacity + 1) * T.sizeof + _Rep.sizeof;
 1234 
 1235                     const size_type __adj_size = __size + __malloc_header_size;
 1236                     if (__adj_size > __pagesize && __capacity > __old_capacity)
 1237                     {
 1238                         const size_type __extra = __pagesize - __adj_size % __pagesize;
 1239                         __capacity += __extra / T.sizeof;
 1240                         if (__capacity > _S_max_size)
 1241                             __capacity = _S_max_size;
 1242                         __size = (__capacity + 1) * T.sizeof + _Rep.sizeof;
 1243                     }
 1244 
 1245                     _Rep* __p = cast(_Rep*)_Raw_bytes_alloc(__alloc).allocate(__size);
 1246                     *__p = _Rep.init;
 1247                     __p._M_capacity = __capacity;
 1248                     __p._M_set_sharable();
 1249                     return __p;
 1250                 }
 1251 
 1252                 void _M_dispose(ref Alloc __a)
 1253                 {
 1254                     import core.stdcpp.xutility : __exchange_and_add_dispatch;
 1255 
 1256                     if (&this != &_S_empty_rep())
 1257                     {
 1258                         // Be race-detector-friendly.  For more info see bits/c++config.
 1259 //                        _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this._M_refcount);
 1260                         // Decrement of _M_refcount is acq_rel, because:
 1261                         // - all but last decrements need to release to synchronize with
 1262                         //   the last decrement that will delete the object.
 1263                         // - the last decrement needs to acquire to synchronize with
 1264                         //   all the previous decrements.
 1265                         // - last but one decrement needs to release to synchronize with
 1266                         //   the acquire load in _M_is_shared that will conclude that
 1267                         //   the object is not shared anymore.
 1268                         if (__exchange_and_add_dispatch(&this._M_refcount, -1) <= 0)
 1269                         {
 1270 //                            _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this._M_refcount);
 1271                             _M_destroy(__a);
 1272                         }
 1273                     }
 1274                 }
 1275 
 1276                 void _M_destroy(ref Alloc __a)
 1277                 {
 1278                     const size_type __size = _Rep_base.sizeof + (_M_capacity + 1) * T.sizeof;
 1279                     _Raw_bytes_alloc(__a).deallocate(cast(char*)&this, __size);
 1280                 }
 1281 
 1282                 T* _M_refcopy() nothrow @trusted
 1283                 {
 1284                     import core.stdcpp.xutility : __atomic_add_dispatch;
 1285 
 1286                     if (&this != &_S_empty_rep())
 1287                         __atomic_add_dispatch(&this._M_refcount, 1);
 1288                     return _M_refdata();
 1289                     // XXX MT
 1290                 }
 1291 
 1292                 T* _M_clone(ref Alloc __alloc, size_type __res = 0)
 1293                 {
 1294                     const size_type __requested_cap = _M_length + __res;
 1295                     _Rep* __r = _S_create(__requested_cap, _M_capacity, __alloc);
 1296                     if (_M_length)
 1297                         _S_copy(__r._M_refdata(), _M_refdata(), _M_length);
 1298 
 1299                     __r._M_set_length_and_sharable(_M_length);
 1300                     return __r._M_refdata();
 1301                 }
 1302             }
 1303 
 1304             static if (!is_empty!allocator_type.value)
 1305                 allocator_type _M_Alloc;
 1306             T* _M_p; // The actual data.
 1307 
 1308             alias _M_data = _M_p;
 1309 
 1310             pragma (inline, true)
 1311             {
 1312                 void eos(size_type offset)
 1313                 {
 1314                     _M_mutate(offset, size() - offset, size_type(0));
 1315                 }
 1316 
 1317                 ref inout(allocator_type) _M_get_allocator() inout
 1318                 {
 1319                     static if (!is_empty!allocator_type.value)
 1320                         return _M_Alloc;
 1321                     else
 1322                         return *cast(inout(allocator_type)*)&this;
 1323                 }
 1324 
 1325                 _Rep* _M_rep() const nothrow @trusted   { return &(cast(_Rep*)_M_data)[-1]; }
 1326 
 1327                 size_type _M_limit(size_type __pos, size_type __off) const @safe nothrow @nogc pure
 1328                 {
 1329                     const bool __testoff =  __off < size() - __pos;
 1330                     return __testoff ? __off : size() - __pos;
 1331                 }
 1332             }
 1333 
 1334             size_type _M_check(size_type __pos, const char* __s) const
 1335             {
 1336                 assert(__pos <= size());
 1337 //                if (__pos > size())
 1338 //                    __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
 1339 //                                                    "this->size() (which is %zu)"),
 1340 //                                                __s, __pos, this->size());
 1341                 return __pos;
 1342             }
 1343 
 1344             static ref _Rep _S_empty_rep() nothrow
 1345             {
 1346                 return _Rep._S_empty_rep();
 1347             }
 1348 
 1349             static T* _S_construct(const(T)* __beg, const(T)* __end, ref Alloc __a)
 1350             {
 1351                 version (_GLIBCXX_FULLY_DYNAMIC_STRING) {} else
 1352                 {
 1353                     if (__beg == __end && __a == Alloc())
 1354                         return _S_empty_rep()._M_refdata();
 1355                 }
 1356 
 1357                 const size_type __dnew = __end - __beg;
 1358 
 1359                 _Rep* __r = _Rep._S_create(__dnew, size_type(0), __a);
 1360                 _S_copy(__r._M_refdata(), __beg, __end - __beg);
 1361                 __r._M_set_length_and_sharable(__dnew);
 1362                 return __r._M_refdata();
 1363             }
 1364 
 1365             ref basic_string _M_replace_safe(size_type __pos1, size_type __n1, const(T)* __s, size_type __n2)
 1366             {
 1367                 _M_mutate(__pos1, __n1, __n2);
 1368                 if (__n2)
 1369                     _S_copy(_M_data + __pos1, __s, __n2);
 1370                 return this;
 1371             }
 1372 
 1373             ref basic_string _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, T __c)
 1374             {
 1375                 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
 1376                 _M_mutate(__pos1, __n1, __n2);
 1377                 if (__n2)
 1378                     _M_data[__pos1 .. __pos1 + __n2] = __c;
 1379                 return this;
 1380             }
 1381 
 1382             void _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 1383             {
 1384                 const size_type __old_size = size();
 1385                 const size_type __new_size = __old_size + __len2 - __len1;
 1386                 const size_type __how_much = __old_size - __pos - __len1;
 1387 
 1388                 if (__new_size > capacity() || _M_rep()._M_is_shared())
 1389                 {
 1390                     allocator_type __a = get_allocator();
 1391                     _Rep* __r = _Rep._S_create(__new_size, capacity(), __a);
 1392 
 1393                     if (__pos)
 1394                         _S_copy(__r._M_refdata(), _M_data, __pos);
 1395                     if (__how_much)
 1396                         _S_copy(__r._M_refdata() + __pos + __len2, _M_data + __pos + __len1, __how_much);
 1397 
 1398                     allocator_type* __al = cast() &__a;
 1399                     _M_rep()._M_dispose(*__al);
 1400                     _M_data = __r._M_refdata();
 1401                 }
 1402                 else if (__how_much && __len1 != __len2)
 1403                     _S_move(_M_data + __pos + __len2, _M_data + __pos + __len1, __how_much);
 1404                 _M_rep()._M_set_length_and_sharable(__new_size);
 1405             }
 1406         }
 1407         else
 1408         {
 1409             pragma(msg, "libstdc++ std::__cxx11::basic_string is not yet supported; the struct contains an interior pointer which breaks D move semantics!");
 1410 
 1411             //----------------------------------------------------------------------------------
 1412             // GCC/libstdc++ modern implementation
 1413             //----------------------------------------------------------------------------------
 1414 
 1415             ///
 1416             this(DefaultConstruct)                                              { _M_p = _M_local_data(); _M_set_length(0); }
 1417             ///
 1418             this(const(T)[] str, ref const(allocator_type) al)                  { _M_assign_allocator(al); this(str); }
 1419             ///
 1420             this(const(T)[] str)
 1421             {
 1422                 _M_p = _M_local_data();
 1423                 _M_construct(str.ptr, str.length);
 1424             }
 1425             ///
 1426             this(this)
 1427             {
 1428                 assert(false);
 1429                 // TODO: how do I know if it was local before?!
 1430             }
 1431 
 1432             ///
 1433             ~this()                                                             { _M_dispose(); }
 1434 
 1435             ///
 1436             ref inout(Alloc) get_allocator() inout                              { return _M_get_allocator(); }
 1437 
 1438             ///
 1439             size_type max_size() const nothrow @safe                            { return ((size_t.max / T.sizeof) - 1) / 2; }
 1440 
 1441             ///
 1442             size_type size() const nothrow @safe                                { return _M_string_length; }
 1443             ///
 1444             size_type capacity() const nothrow                                  { return _M_is_local ? _S_local_capacity : _M_allocated_capacity; }
 1445             ///
 1446             inout(T)* data() inout @safe                                        { return _M_data; }
 1447             ///
 1448             inout(T)[] as_array() inout nothrow @trusted                        { return _M_data[0 .. _M_string_length]; }
 1449             ///
 1450             ref inout(T) at(size_type i) inout nothrow                          { return _M_data[0 .. _M_string_length][i]; }
 1451 
 1452             ///
 1453             ref basic_string assign(const(T)[] str)
 1454             {
 1455 //                __glibcxx_requires_string_len(str.ptr, str.length);
 1456                 return _M_replace(size_type(0), size(), str.ptr, str.length);
 1457             }
 1458 
 1459             ///
 1460             ref basic_string assign(const ref basic_string str)
 1461             {
 1462                 if (&this != &str)
 1463                     assign(str.as_array);
 1464                 return this;
 1465             }
 1466 
 1467             ///
 1468             ref basic_string append(const(T)[] str)
 1469             {
 1470 //                __glibcxx_requires_string_len(str.ptr, str.length);
 1471                 _M_check_length(size_type(0), str.length, "basic_string::append");
 1472                 return _M_append(str.ptr, str.length);
 1473             }
 1474 
 1475             ///
 1476             ref basic_string append(size_type n, T c)
 1477             {
 1478                 return _M_replace_aux(size(), size_type(0), n, c);
 1479             }
 1480 
 1481             ///
 1482             void reserve(size_type __res = 0)
 1483             {
 1484                 // Make sure we don't shrink below the current size.
 1485                 if (__res < length())
 1486                     __res = length();
 1487 
 1488                 const size_type __capacity = capacity();
 1489                 if (__res != __capacity)
 1490                 {
 1491                     if (__res > __capacity || __res > size_type(_S_local_capacity))
 1492                     {
 1493                         pointer __tmp = _M_create(__res, __capacity);
 1494                         _S_copy(__tmp, _M_data, length() + 1);
 1495                         _M_dispose();
 1496                         _M_data = __tmp;
 1497                         _M_capacity = __res;
 1498                     }
 1499                     else if (!_M_is_local())
 1500                     {
 1501                         _S_copy(_M_local_data(), _M_data, length() + 1);
 1502                         _M_destroy(__capacity);
 1503                         _M_data = _M_local_data();
 1504                     }
 1505                 }
 1506             }
 1507 
 1508             ///
 1509             void shrink_to_fit() nothrow
 1510             {
 1511                 if (capacity() > size())
 1512                 {
 1513                     try reserve(0);
 1514                     catch (Throwable) {}
 1515                 }
 1516             }
 1517 
 1518             ///
 1519             ref basic_string insert(size_type pos, const(T)* s, size_type n)
 1520             {
 1521                 return replace(pos, size_type(0), s, n);
 1522             }
 1523 
 1524             ///
 1525             ref basic_string insert(size_type pos, size_type n, T c)
 1526             {
 1527                 return _M_replace_aux(_M_check(pos, "basic_string::insert"), size_type(0), n, c);
 1528             }
 1529 
 1530             ///
 1531             ref basic_string replace(size_type pos, size_type n1, const(T)* s, size_type n2)
 1532             {
 1533 //                __glibcxx_requires_string_len(s, n2);
 1534                 return _M_replace(_M_check(pos, "basic_string::replace"), _M_limit(pos, n1), s, n2);
 1535             }
 1536 
 1537             ///
 1538             ref basic_string replace(size_type pos, size_type n1, size_type n2, T c)
 1539             {
 1540                 return _M_replace_aux(_M_check(pos, "basic_string::replace"), _M_limit(pos, n1), n2, c);
 1541             }
 1542 
 1543             ///
 1544             void swap(ref basic_string __s)
 1545             {
 1546                 if (&this == &__s)
 1547                     return;
 1548 
 1549                 __alloc_on_swap(__s._M_get_allocator());
 1550 
 1551                 if (_M_is_local())
 1552                 {
 1553                     if (__s._M_is_local())
 1554                     {
 1555                         if (length() && __s.length())
 1556                         {
 1557                             T[_S_local_capacity + 1] __tmp_data;
 1558                             __tmp_data[] = __s._M_local_buf[];
 1559                             __s._M_local_buf[] = _M_local_buf[];
 1560                             _M_local_buf[] = __tmp_data[];
 1561                         }
 1562                         else if (__s.length())
 1563                         {
 1564                             _M_local_buf[] = __s._M_local_buf[];
 1565                             _M_length = __s.length();
 1566                             __s._M_set_length(0);
 1567                             return;
 1568                         }
 1569                         else if (length())
 1570                         {
 1571                             __s._M_local_buf[] = _M_local_buf[];
 1572                             __s._M_length = length();
 1573                             _M_set_length(0);
 1574                             return;
 1575                         }
 1576                     }
 1577                     else
 1578                     {
 1579                         const size_type __tmp_capacity = __s._M_allocated_capacity;
 1580                         __s._M_local_buf[] = _M_local_buf[];
 1581                         _M_data = __s._M_data;
 1582                         __s._M_data = __s._M_local_buf.ptr;
 1583                         _M_capacity = __tmp_capacity;
 1584                     }
 1585                 }
 1586                 else
 1587                 {
 1588                     const size_type __tmp_capacity = _M_allocated_capacity;
 1589                     if (__s._M_is_local())
 1590                     {
 1591                         _M_local_buf[] = __s._M_local_buf[];
 1592                         __s._M_data = _M_data;
 1593                         _M_data = _M_local_buf.ptr;
 1594                     }
 1595                     else
 1596                     {
 1597                         pointer __tmp_ptr = _M_data;
 1598                         _M_data = __s._M_data;
 1599                         __s._M_data = __tmp_ptr;
 1600                         _M_capacity = __s._M_allocated_capacity;
 1601                     }
 1602                     __s._M_capacity = __tmp_capacity;
 1603                 }
 1604 
 1605                 const size_type __tmp_length = length();
 1606                 _M_length = __s.length();
 1607                 __s._M_length = __tmp_length;
 1608             }
 1609 
 1610         private:
 1611 //            import core.exception : RangeError;
 1612             import core.stdcpp.type_traits : is_empty;
 1613 
 1614             static if (!is_empty!allocator_type.value)
 1615                 allocator_type _M_Alloc;
 1616             pointer _M_p; // The actual data.
 1617             size_type _M_string_length;
 1618 
 1619             enum size_type _S_local_capacity = 15 / T.sizeof;
 1620             union
 1621             {
 1622                 T[_S_local_capacity + 1]    _M_local_buf;
 1623                 size_type                   _M_allocated_capacity;
 1624             }
 1625 
 1626             alias _M_length = _M_string_length;
 1627             alias _M_capacity = _M_allocated_capacity;
 1628             alias _M_data = _M_p;
 1629 
 1630             pragma (inline, true)
 1631             {
 1632                 void eos(size_type offset) nothrow                              { _M_set_length(offset); }
 1633 
 1634                 inout(pointer) _M_local_data() inout                            { return _M_local_buf.ptr; }
 1635                 bool _M_is_local() const                                        { return _M_data == _M_local_data; }
 1636 
 1637                 ref inout(allocator_type) _M_get_allocator() inout
 1638                 {
 1639                     static if (!is_empty!allocator_type.value)
 1640                         return _M_Alloc;
 1641                     else
 1642                         return *cast(inout(allocator_type)*)&this;
 1643                 }
 1644 
 1645                 void _M_set_length(size_type __n)
 1646                 {
 1647                     _M_length = __n;
 1648                     _M_data[__n] = T(0);
 1649                 }
 1650 
 1651                 size_type _M_check(size_type __pos, const char* __s) const
 1652                 {
 1653                     assert(__pos <= size());
 1654 //                    if (__pos > size())
 1655 //                        __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
 1656 //                                   "this->size() (which is %zu)"),
 1657 //                               __s, __pos, this->size());
 1658                     return __pos;
 1659                 }
 1660 
 1661                 // NB: _M_limit doesn't check for a bad __pos value.
 1662                 size_type _M_limit(size_type __pos, size_type __off) const nothrow pure @nogc @safe
 1663                 {
 1664                     const bool __testoff =  __off < size() - __pos;
 1665                     return __testoff ? __off : size() - __pos;
 1666                 }
 1667 
 1668                 void __alloc_on_swap()(ref allocator_type __a)
 1669                 if (!is_empty!allocator_type.value)
 1670                 {
 1671                     import core.internal.lifetime : swap;
 1672 
 1673                     static if (allocator_traits!allocator_type.propagate_on_container_swap)
 1674                       swap(_M_get_allocator(), __a);
 1675                 }
 1676 
 1677                 void __alloc_on_swap()(ref allocator_type __a)
 1678                 if (is_empty!allocator_type.value)
 1679                 {
 1680                     import core.internal.lifetime : swap;
 1681                     import core.lifetime : move;
 1682 
 1683                     static if (allocator_traits!allocator_type.propagate_on_container_swap)
 1684                     {
 1685                         static if (is(typeof(_M_get_allocator().opAssign(move(__a)))))
 1686                             swap(_M_get_allocator(), __a);
 1687                     }
 1688                 }
 1689             }
 1690 
 1691             void _M_construct(const(T)* __beg, size_type __dnew)
 1692             {
 1693                 if (__dnew > _S_local_capacity)
 1694                 {
 1695                     _M_data = _M_create(__dnew, size_type(0));
 1696                     _M_capacity = __dnew;
 1697                 }
 1698                 _M_data[0 .. __dnew] = __beg[0 .. __dnew];
 1699                 _M_set_length(__dnew);
 1700             }
 1701 
 1702             pointer _M_create(ref size_type __capacity, size_type __old_capacity)
 1703             {
 1704                 assert(__capacity <= max_size());
 1705 //                if (__capacity > max_size())
 1706 //                    throw new RangeError("Length exceeds `max_size()`"); // std::__throw_length_error(__N("basic_string::_M_create"));
 1707                 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
 1708                 {
 1709                     __capacity = 2 * __old_capacity;
 1710                     if (__capacity > max_size())
 1711                         __capacity = max_size();
 1712                 }
 1713                 return _M_get_allocator().allocate(__capacity + 1);
 1714             }
 1715 
 1716             ref basic_string _M_replace(size_type __pos, size_type __len1, const(T)* __s, const size_type __len2)
 1717             {
 1718                 _M_check_length(__len1, __len2, "basic_string::_M_replace");
 1719 
 1720                 const size_type __old_size = size();
 1721                 const size_type __new_size = __old_size + __len2 - __len1;
 1722 
 1723                 if (__new_size <= capacity())
 1724                 {
 1725                     pointer __p = _M_data + __pos;
 1726 
 1727                     const size_type __how_much = __old_size - __pos - __len1;
 1728                     if (_M_disjunct(__s))
 1729                     {
 1730                         if (__how_much && __len1 != __len2)
 1731                             _S_move(__p + __len2, __p + __len1, __how_much);
 1732                         if (__len2)
 1733                             _S_copy(__p, __s, __len2);
 1734                     }
 1735                     else
 1736                     {
 1737                         // Work in-place.
 1738                         if (__len2 && __len2 <= __len1)
 1739                             _S_move(__p, __s, __len2);
 1740                         if (__how_much && __len1 != __len2)
 1741                             _S_move(__p + __len2, __p + __len1, __how_much);
 1742                         if (__len2 > __len1)
 1743                         {
 1744                             if (__s + __len2 <= __p + __len1)
 1745                                 _S_move(__p, __s, __len2);
 1746                             else if (__s >= __p + __len1)
 1747                                 _S_copy(__p, __s + __len2 - __len1, __len2);
 1748                             else
 1749                             {
 1750                                 const size_type __nleft = (__p + __len1) - __s;
 1751                                 _S_move(__p, __s, __nleft);
 1752                                 _S_copy(__p + __nleft, __p + __len2,
 1753                                         __len2 - __nleft);
 1754                             }
 1755                         }
 1756                     }
 1757                 }
 1758                 else
 1759                     _M_mutate(__pos, __len1, __s, __len2);
 1760 
 1761                 _M_set_length(__new_size);
 1762                 return this;
 1763             }
 1764 
 1765             ref basic_string _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, T __c)
 1766             {
 1767                 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
 1768 
 1769                 const size_type __old_size = size();
 1770                 const size_type __new_size = __old_size + __n2 - __n1;
 1771 
 1772                 if (__new_size <= capacity())
 1773                 {
 1774                     pointer __p = _M_data + __pos1;
 1775 
 1776                     const size_type __how_much = __old_size - __pos1 - __n1;
 1777                     if (__how_much && __n1 != __n2)
 1778                         _S_move(__p + __n2, __p + __n1, __how_much);
 1779                 }
 1780                 else
 1781                     _M_mutate(__pos1, __n1, null, __n2);
 1782 
 1783                 if (__n2)
 1784                     _M_data[__pos1 .. __pos1 + __n2] = __c;
 1785 
 1786                 _M_set_length(__new_size);
 1787                 return this;
 1788             }
 1789 
 1790             ref basic_string _M_append(const(T)* __s, size_type __n)
 1791             {
 1792                 const size_type __len = __n + size();
 1793                 if (__len <= capacity())
 1794                 {
 1795                     if (__n)
 1796                         _S_copy(_M_data + size(), __s, __n);
 1797                 }
 1798                 else
 1799                     _M_mutate(size(), size_type(0), __s, __n);
 1800                 _M_set_length(__len);
 1801                 return this;
 1802             }
 1803 
 1804             void _M_mutate(size_type __pos, size_type __len1, const(T)* __s, size_type __len2)
 1805             {
 1806                 const size_type __how_much = length() - __pos - __len1;
 1807 
 1808                 size_type __new_capacity = length() + __len2 - __len1;
 1809                 pointer __r = _M_create(__new_capacity, capacity());
 1810 
 1811                 if (__pos)
 1812                     _S_copy(__r, _M_data, __pos);
 1813                 if (__s && __len2)
 1814                     _S_copy(__r + __pos, __s, __len2);
 1815                 if (__how_much)
 1816                     _S_copy(__r + __pos + __len2,
 1817                             _M_data + __pos + __len1, __how_much);
 1818 
 1819                 _M_dispose();
 1820                 _M_data = __r;
 1821                 _M_capacity = __new_capacity;
 1822             }
 1823 
 1824             void _M_dispose()
 1825             {
 1826                 if (!_M_is_local)
 1827                     _M_destroy(_M_allocated_capacity);
 1828             }
 1829 
 1830             void _M_destroy(size_type __size)
 1831             {
 1832                 _M_get_allocator().deallocate(_M_data, __size + 1);
 1833             }
 1834         }
 1835 
 1836         // common GCC/stdlibc++ code
 1837 
 1838         void _M_check_length(size_type __n1, size_type __n2, const char* __s) const
 1839         {
 1840             assert (!(max_size() - (size() - __n1) < __n2));
 1841 //            if (max_size() - (size() - __n1) < __n2)
 1842 //            __throw_length_error(__N(__s));
 1843         }
 1844 
 1845         void _M_assign_allocator(ref const(allocator_type) al) nothrow
 1846         {
 1847             static if (!is_empty!allocator_type.value)
 1848                 _M_Alloc = al;
 1849         }
 1850 
 1851         bool _M_disjunct(const(T)* __s) const nothrow
 1852         {
 1853             return __s < _M_data || _M_data + size() < __s;
 1854         }
 1855 
 1856         static void _S_move(T* __d, const(T)* __s, size_type __n)
 1857         {
 1858             if (__d == __s)
 1859                 return;
 1860             if (__d < __s)
 1861             {
 1862                 for (size_t i = 0; i < __n; ++i)
 1863                     __d[i] = __s[i];
 1864             }
 1865             else
 1866             {
 1867                 for (ptrdiff_t i = __n - 1; i >= 0; --i)
 1868                     __d[i] = __s[i];
 1869             }
 1870         }
 1871         static void _S_copy(T* __d, const(T)* __s, size_type __n)
 1872         {
 1873             __d[0 .. __n] = __s[0 .. __n];
 1874         }
 1875     }
 1876     else version (CppRuntime_Clang)
 1877     {
 1878         //----------------------------------------------------------------------------------
 1879         // Clang/libc++ implementation
 1880         //----------------------------------------------------------------------------------
 1881 
 1882         ///
 1883         this(DefaultConstruct)                                              { __zero(); }
 1884         ///
 1885         this(const(T)[] str, ref const(allocator_type) al)                  { __assign_allocator(al); this(str); }
 1886         ///
 1887         this(const(T)[] str)                                                { __init(str.ptr, str.length); }
 1888         ///
 1889         this(this)
 1890         {
 1891             if (__is_long())
 1892                 __init(__get_long_pointer(), __get_long_size());
 1893         }
 1894 
 1895         ///
 1896         ~this()
 1897         {
 1898 //            __get_db()->__erase_c(this); // TODO: support `_LIBCPP_DEBUG_LEVEL >= 2` ??
 1899             if (__is_long())
 1900                 __alloc().deallocate(__get_long_pointer(), __get_long_cap());
 1901         }
 1902 
 1903         ///
 1904         ref inout(Alloc) get_allocator() inout                              { return __alloc(); }
 1905 
 1906         ///
 1907         size_type max_size() const nothrow @safe
 1908         {
 1909             size_type __m = size_t.max; // TODO: __alloc_traits::max_size(__alloc());
 1910             version (BigEndian)
 1911                 return (__m <= ~__long_mask ? __m : __m/2) - __alignment;
 1912             else
 1913                 return __m - __alignment;
 1914         }
 1915 
 1916         ///
 1917         size_type size() const nothrow                                      { return __is_long() ? __get_long_size() : __get_short_size(); }
 1918         ///
 1919         size_type capacity() const nothrow                                  { return (__is_long() ? __get_long_cap() : __min_cap) - 1; }
 1920         ///
 1921         inout(T)* data() inout @safe                                        { return __get_pointer(); }
 1922         ///
 1923         inout(T)[] as_array() inout nothrow @trusted                        { return __get_pointer()[0 .. size()]; }
 1924         ///
 1925         ref inout(T) at(size_type i) inout nothrow @trusted                 { return __get_pointer()[0 .. size()][i]; }
 1926 
 1927         ///
 1928         ref basic_string assign(const(T)[] str)
 1929         {
 1930             const(value_type)* __s = str.ptr;
 1931             size_type __n = str.length;
 1932             size_type __cap = capacity();
 1933             if (__cap >= __n)
 1934             {
 1935                 value_type* __p = __get_pointer();
 1936                 __p[0 .. __n] = __s[0 .. __n]; // TODO: is memmove?
 1937                 __p[__n] = value_type(0);
 1938                 __set_size(__n);
 1939 //                __invalidate_iterators_past(__n); // TODO: support `_LIBCPP_DEBUG_LEVEL >= 2` ??
 1940             }
 1941             else
 1942             {
 1943                 size_type __sz = size();
 1944                 __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s);
 1945             }
 1946             return this;
 1947         }
 1948 
 1949         ///
 1950         ref basic_string assign(const ref basic_string str)
 1951         {
 1952             if (&this != &str)
 1953                 assign(str.as_array);
 1954             return this;
 1955         }
 1956 
 1957         ///
 1958         ref basic_string append(const(T)[] str)
 1959         {
 1960             const(value_type)* __s = str.ptr;
 1961             size_type __n = str.length;
 1962             size_type __cap = capacity();
 1963             size_type __sz = size();
 1964             if (__cap - __sz >= __n)
 1965             {
 1966                 if (__n)
 1967                 {
 1968                     value_type* __p = __get_pointer();
 1969                     (__p + __sz)[0 .. __n] = __s[0 .. __n];
 1970                     __sz += __n;
 1971                     __set_size(__sz);
 1972                     __p[__sz] = value_type(0);
 1973                 }
 1974             }
 1975             else
 1976                 __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __sz, 0, __n, __s);
 1977             return this;
 1978         }
 1979 
 1980         ///
 1981         ref basic_string append(size_type __n, value_type __c)
 1982         {
 1983             if (__n)
 1984             {
 1985                 size_type __cap = capacity();
 1986                 size_type __sz = size();
 1987                 if (__cap - __sz < __n)
 1988                     __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0);
 1989                 pointer __p = __get_pointer();
 1990                 __p[__sz .. __sz + __n] = __c;
 1991                 __sz += __n;
 1992                 __set_size(__sz);
 1993                 __p[__sz] = value_type(0);
 1994             }
 1995             return this;
 1996         }
 1997 
 1998         ///
 1999         void reserve(size_type __res_arg = 0)
 2000         {
 2001             assert(__res_arg <= max_size());
 2002 //            if (__res_arg > max_size())
 2003 //                __throw_length_error();
 2004             size_type __cap = capacity();
 2005             size_type __sz = size();
 2006             __res_arg = max(__res_arg, __sz);
 2007             __res_arg = __recommend(__res_arg);
 2008             if (__res_arg != __cap)
 2009             {
 2010                 pointer __new_data, __p;
 2011                 bool __was_long, __now_long;
 2012                 if (__res_arg == __min_cap - 1)
 2013                 {
 2014                     __was_long = true;
 2015                     __now_long = false;
 2016                     __new_data = __get_short_pointer();
 2017                     __p = __get_long_pointer();
 2018                 }
 2019                 else
 2020                 {
 2021                     if (__res_arg > __cap)
 2022                         __new_data = __alloc().allocate(__res_arg+1);
 2023                     else
 2024                     {
 2025                         try
 2026                             __new_data = __alloc().allocate(__res_arg+1);
 2027                         catch (Throwable)
 2028                             return;
 2029                     }
 2030                     __now_long = true;
 2031                     __was_long = __is_long();
 2032                     __p = __get_pointer();
 2033                 }
 2034                 __new_data[0 .. size()+1] = __p[0 .. size()+1];
 2035                 if (__was_long)
 2036                     __alloc().deallocate(__p, __cap+1);
 2037                 if (__now_long)
 2038                 {
 2039                     __set_long_cap(__res_arg+1);
 2040                     __set_long_size(__sz);
 2041                     __set_long_pointer(__new_data);
 2042                 }
 2043                 else
 2044                     __set_short_size(__sz);
 2045 //                __invalidate_all_iterators(); // TODO:
 2046             }
 2047         }
 2048 
 2049         ///
 2050         void shrink_to_fit()
 2051         {
 2052             reserve();
 2053         }
 2054 
 2055         ///
 2056         ref basic_string insert(size_type __pos, const(value_type)* __s, size_type __n)
 2057         {
 2058             assert(__n == 0 || __s != null, "string::insert received null");
 2059             size_type __sz = size();
 2060             assert(__pos <= __sz);
 2061 //            if (__pos > __sz)
 2062 //                this->__throw_out_of_range();
 2063             size_type __cap = capacity();
 2064             if (__cap - __sz >= __n)
 2065             {
 2066                 if (__n)
 2067                 {
 2068                     value_type* __p = __get_pointer();
 2069                     size_type __n_move = __sz - __pos;
 2070                     if (__n_move != 0)
 2071                     {
 2072                         if (__p + __pos <= __s && __s < __p + __sz)
 2073                             __s += __n;
 2074                         traits_type.move(__p + __pos + __n, __p + __pos, __n_move);
 2075                     }
 2076                     traits_type.move(__p + __pos, __s, __n);
 2077                     __sz += __n;
 2078                     __set_size(__sz);
 2079                     __p[__sz] = value_type(0);
 2080                 }
 2081             }
 2082             else
 2083                 __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n, __s);
 2084             return this;
 2085         }
 2086 
 2087         ///
 2088         ref basic_string insert(size_type pos, size_type n, value_type c)
 2089         {
 2090             alias __pos = pos;
 2091             alias __n = n;
 2092             alias __c = c;
 2093             size_type __sz = size();
 2094             assert(__pos <= __sz);
 2095 //            if (__pos > __sz)
 2096 //                __throw_out_of_range();
 2097             if (__n)
 2098             {
 2099                 size_type __cap = capacity();
 2100                 value_type* __p;
 2101                 if (__cap - __sz >= __n)
 2102                 {
 2103                     __p = __get_pointer();
 2104                     size_type __n_move = __sz - __pos;
 2105                     if (__n_move != 0)
 2106                         traits_type.move(__p + __pos + __n, __p + __pos, __n_move);
 2107                 }
 2108                 else
 2109                 {
 2110                     __grow_by(__cap, __sz + __n - __cap, __sz, __pos, 0, __n);
 2111                     __p = __get_long_pointer();
 2112                 }
 2113                 __p[__pos .. __pos + __n] = __c;
 2114                 __sz += __n;
 2115                 __set_size(__sz);
 2116                 __p[__sz] = value_type(0);
 2117             }
 2118             return this;
 2119         }
 2120 
 2121         ///
 2122         ref basic_string replace(size_type __pos, size_type __n1, const(T)* __s, size_type __n2)
 2123         {
 2124             assert(__n2 == 0 || __s != null, "string::replace received null");
 2125             size_type __sz = size();
 2126             assert(__pos <= __sz);
 2127 //            if (__pos > __sz)
 2128 //                __throw_out_of_range();
 2129             __n1 = min(__n1, __sz - __pos);
 2130             size_type __cap = capacity();
 2131             if (__cap - __sz + __n1 >= __n2)
 2132             {
 2133                 value_type* __p = __get_pointer();
 2134                 if (__n1 != __n2)
 2135                 {
 2136                     size_type __n_move = __sz - __pos - __n1;
 2137                     if (__n_move != 0)
 2138                     {
 2139                         if (__n1 > __n2)
 2140                         {
 2141                             traits_type.move(__p + __pos, __s, __n2);
 2142                             traits_type.move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
 2143                             goto __finish;
 2144                         }
 2145                         if (__p + __pos < __s && __s < __p + __sz)
 2146                         {
 2147                             if (__p + __pos + __n1 <= __s)
 2148                                 __s += __n2 - __n1;
 2149                             else // __p + __pos < __s < __p + __pos + __n1
 2150                             {
 2151                                 traits_type.move(__p + __pos, __s, __n1);
 2152                                 __pos += __n1;
 2153                                 __s += __n2;
 2154                                 __n2 -= __n1;
 2155                                 __n1 = 0;
 2156                             }
 2157                         }
 2158                         traits_type.move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
 2159                     }
 2160                 }
 2161                 traits_type.move(__p + __pos, __s, __n2);
 2162         __finish:
 2163         // __sz += __n2 - __n1; in this and the below function below can cause unsigned integer overflow,
 2164         // but this is a safe operation, so we disable the check.
 2165                 __sz += __n2 - __n1;
 2166                 __set_size(__sz);
 2167 //                __invalidate_iterators_past(__sz); // TODO
 2168                 __p[__sz] = value_type(0);
 2169             }
 2170             else
 2171                 __grow_by_and_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2, __s);
 2172             return this;
 2173         }
 2174 
 2175         ///
 2176         ref basic_string replace(size_type __pos, size_type __n1, size_type __n2, value_type __c)
 2177         {
 2178             size_type __sz = size();
 2179             assert(__pos <= __sz);
 2180 //            if (__pos > __sz)
 2181 //                __throw_out_of_range();
 2182             __n1 = min(__n1, __sz - __pos);
 2183             size_type __cap = capacity();
 2184             value_type* __p;
 2185             if (__cap - __sz + __n1 >= __n2)
 2186             {
 2187                 __p = __get_pointer();
 2188                 if (__n1 != __n2)
 2189                 {
 2190                     size_type __n_move = __sz - __pos - __n1;
 2191                     if (__n_move != 0)
 2192                         traits_type.move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
 2193                 }
 2194             }
 2195             else
 2196             {
 2197                 __grow_by(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2);
 2198                 __p = __get_long_pointer();
 2199             }
 2200             __p[__pos .. __pos + __n2] = __c;
 2201             __sz += __n2 - __n1;
 2202             __set_size(__sz);
 2203 //            __invalidate_iterators_past(__sz); // TODO
 2204             __p[__sz] = value_type(0);
 2205             return this;
 2206         }
 2207 
 2208         ///
 2209         void swap(ref basic_string __str)
 2210         {
 2211             import core.internal.lifetime : swap;
 2212 //            static if (_LIBCPP_DEBUG_LEVEL >= 2)
 2213 //            {
 2214 //                if (!__is_long())
 2215 //                    __get_db().__invalidate_all(&this);
 2216 //                if (!__str.__is_long())
 2217 //                    __get_db().__invalidate_all(&__str);
 2218 //                __get_db().swap(&this, &__str);
 2219 //            }
 2220             assert(
 2221                 __alloc_traits.propagate_on_container_swap ||
 2222                 __alloc_traits.is_always_equal ||
 2223                 __alloc() == __str.__alloc(), "swapping non-equal allocators");
 2224             swap(__r_.first(), __str.__r_.first());
 2225             __swap_allocator(__alloc(), __str.__alloc());
 2226         }
 2227 
 2228     private:
 2229 //        import core.exception : RangeError;
 2230         import core.stdcpp.xutility : __compressed_pair;
 2231 
 2232         alias __alloc_traits = allocator_traits!allocator_type;
 2233 
 2234         enum __alignment = 16;
 2235 
 2236         version (_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT)
 2237         {
 2238             struct __long
 2239             {
 2240                 pointer   __data_;
 2241                 size_type __size_;
 2242                 size_type __cap_;
 2243             }
 2244 
 2245             version (BigEndian)
 2246             {
 2247                 enum size_type __short_mask = 0x01;
 2248                 enum size_type __long_mask  = 0x1;
 2249             }
 2250             else
 2251             {
 2252                 enum size_type __short_mask = 0x80;
 2253                 enum size_type __long_mask  = ~(size_type(~0) >> 1);
 2254             }
 2255 
 2256             enum size_type __min_cap = (__long.sizeof - 1)/value_type.sizeof > 2 ? (__long.sizeof - 1)/value_type.sizeof : 2;
 2257 
 2258             struct __short
 2259             {
 2260                 value_type[__min_cap] __data_;
 2261                 struct
 2262                 {
 2263                     static if (value_type.sizeof > 1)
 2264                         ubyte[value_type.sizeof-1] __xx; // __padding<value_type>
 2265                     ubyte __size_;
 2266                 }
 2267             }
 2268         }
 2269         else
 2270         {
 2271             struct __long
 2272             {
 2273                 size_type __cap_;
 2274                 size_type __size_;
 2275                 pointer   __data_;
 2276             }
 2277 
 2278             version (BigEndian)
 2279             {
 2280                 enum size_type __short_mask = 0x80;
 2281                 enum size_type __long_mask  = ~(size_type(~0) >> 1);
 2282             }
 2283             else
 2284             {
 2285                 enum size_type __short_mask = 0x01;
 2286                 enum size_type __long_mask  = 0x1;
 2287             }
 2288 
 2289             enum size_type __min_cap = (__long.sizeof - 1)/value_type.sizeof > 2 ? (__long.sizeof - 1)/value_type.sizeof : 2;
 2290 
 2291             struct __short
 2292             {
 2293                 union
 2294                 {
 2295                     ubyte __size_;
 2296                     value_type __lx;
 2297                 }
 2298                 value_type[__min_cap] __data_;
 2299             }
 2300         }
 2301 
 2302         union __ulx { __long __lx; __short __lxx; }
 2303         enum __n_words = __ulx.sizeof / size_type.sizeof;
 2304 
 2305         struct __raw
 2306         {
 2307             size_type[__n_words] __words;
 2308         }
 2309 
 2310         struct __rep
 2311         {
 2312             union
 2313             {
 2314                 __long  __l;
 2315                 __short __s;
 2316                 __raw   __r;
 2317             }
 2318         }
 2319 
 2320         __compressed_pair!(__rep, allocator_type) __r_;
 2321 
 2322         pragma (inline, true)
 2323         {
 2324             void eos(size_type offset) nothrow
 2325             {
 2326                 __set_size(offset);
 2327 //                __invalidate_iterators_past(__sz); // TODO: support `_LIBCPP_DEBUG_LEVEL >= 2` ??
 2328                 __get_pointer()[offset] = value_type(0);
 2329             }
 2330 
 2331             version (_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT)
 2332             {
 2333                 version (BigEndian)
 2334                 {
 2335                     void __set_short_size(size_type __s) nothrow @safe          { __r_.first().__s.__size_ = cast(ubyte)(__s << 1); }
 2336                     size_type __get_short_size() const nothrow @safe            { return __r_.first().__s.__size_ >> 1; }
 2337                 }
 2338                 else
 2339                 {
 2340                     void __set_short_size(size_type __s) nothrow @safe          { __r_.first().__s.__size_ = cast(ubyte)(__s);}
 2341                     size_type __get_short_size() const nothrow @safe            { return __r_.first().__s.__size_;}
 2342                 }
 2343             }
 2344             else
 2345             {
 2346                 version (BigEndian)
 2347                 {
 2348                     void __set_short_size(size_type __s) nothrow @safe          { __r_.first().__s.__size_ = cast(ubyte)(__s); }
 2349                     size_type __get_short_size() const nothrow @safe            { return __r_.first().__s.__size_; }
 2350                 }
 2351                 else
 2352                 {
 2353                     void __set_short_size(size_type __s) nothrow @safe          { __r_.first().__s.__size_ = cast(ubyte)(__s << 1); }
 2354                     size_type __get_short_size() const nothrow @safe            { return __r_.first().__s.__size_ >> 1; }
 2355                 }
 2356             }
 2357             void __set_long_size(size_type __s) nothrow                         { __r_.first().__l.__size_ = __s; }
 2358             size_type __get_long_size() const nothrow                           { return __r_.first().__l.__size_; }
 2359             void __set_size(size_type __s) nothrow                              { if (__is_long()) __set_long_size(__s); else __set_short_size(__s); }
 2360 
 2361             void __set_long_cap(size_type __s) nothrow                          { __r_.first().__l.__cap_  = __long_mask | __s; }
 2362             size_type __get_long_cap() const nothrow                            { return __r_.first().__l.__cap_ & size_type(~__long_mask); }
 2363 
 2364             void __set_long_pointer(pointer __p) nothrow                        { __r_.first().__l.__data_ = __p; }
 2365             inout(T)* __get_long_pointer() inout nothrow                        { return __r_.first().__l.__data_; }
 2366             inout(T)* __get_short_pointer() inout nothrow @safe                 { return &__r_.first().__s.__data_[0]; }
 2367             inout(T)* __get_pointer() inout nothrow                             { return __is_long() ? __get_long_pointer() : __get_short_pointer(); }
 2368 
 2369             bool __is_long() const nothrow @safe                                { return (__r_.first().__s.__size_ & __short_mask) != 0; }
 2370 
 2371             void __zero() nothrow @safe                                         { __r_.first().__r.__words[] = 0; }
 2372 
 2373             ref inout(allocator_type) __alloc() inout nothrow @safe             { return __r_.second(); }
 2374 
 2375             void __init(const(value_type)* __s, size_type __sz)                 { return __init(__s, __sz, __sz); }
 2376         }
 2377 
 2378         void __assign_allocator(ref const(allocator_type) al) nothrow
 2379         {
 2380             static if (!__r_.Ty2Empty)
 2381                 __alloc() = al;
 2382         }
 2383 
 2384         void __init(const(value_type)* __s, size_type __sz, size_type __reserve)
 2385         {
 2386             assert(__reserve <= max_size());
 2387 //            if (__reserve > max_size())
 2388 //                throw new RangeError("Length exceeds `max_size()`"); // this->__throw_length_error();
 2389             pointer __p;
 2390             if (__reserve < __min_cap)
 2391             {
 2392                 __set_short_size(__sz);
 2393                 __p = __get_short_pointer();
 2394             }
 2395             else
 2396             {
 2397                 size_type __cap = __recommend(__reserve);
 2398                 __p = __alloc().allocate(__cap+1, null);
 2399                 __set_long_pointer(__p);
 2400                 __set_long_cap(__cap+1);
 2401                 __set_long_size(__sz);
 2402             }
 2403             __p[0 .. __sz] = __s[0 .. __sz];
 2404             __p[__sz] = value_type(0);
 2405         }
 2406 
 2407         static size_type __recommend(size_type __s) nothrow @safe
 2408         {
 2409             static size_type __align_it(size_type __a)(size_type __s) nothrow @safe { return (__s + (__a-1)) & ~(__a-1); }
 2410             if (__s < __min_cap) return __min_cap - 1;
 2411             size_type __guess = __align_it!(value_type.sizeof < __alignment ? __alignment/value_type.sizeof : 1)(__s+1) - 1;
 2412             if (__guess == __min_cap) ++__guess;
 2413             return __guess;
 2414         }
 2415 
 2416         void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz, size_type __n_copy,
 2417                                  size_type __n_del, size_type __n_add, const(value_type)* __p_new_stuff)
 2418         {
 2419             size_type __ms = max_size();
 2420             assert(__delta_cap <= __ms - __old_cap - 1);
 2421 //            if (__delta_cap > __ms - __old_cap - 1)
 2422 //                throw new RangeError("Length exceeds `max_size()`"); // this->__throw_length_error();
 2423             pointer __old_p = __get_pointer();
 2424             size_type __cap = __old_cap < __ms / 2 - __alignment ?
 2425                 __recommend(max(__old_cap + __delta_cap, 2 * __old_cap)) :
 2426             __ms - 1;
 2427             pointer __p = __alloc().allocate(__cap+1);
 2428 //            __invalidate_all_iterators(); // TODO: support `_LIBCPP_DEBUG_LEVEL >= 2` ??
 2429             if (__n_copy != 0)
 2430                 __p[0 .. __n_copy] = __old_p[0 .. __n_copy];
 2431             if (__n_add != 0)
 2432                 (__p + __n_copy)[0 .. __n_add] = __p_new_stuff[0 .. __n_add];
 2433             size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
 2434             if (__sec_cp_sz != 0)
 2435                 (__p + __n_copy + __n_add)[0 .. __sec_cp_sz] = (__old_p + __n_copy + __n_del)[0 .. __sec_cp_sz];
 2436             if (__old_cap+1 != __min_cap)
 2437                 __alloc().deallocate(__old_p, __old_cap+1);
 2438             __set_long_pointer(__p);
 2439             __set_long_cap(__cap+1);
 2440             __old_sz = __n_copy + __n_add + __sec_cp_sz;
 2441             __set_long_size(__old_sz);
 2442             __p[__old_sz] = value_type(0);
 2443         }
 2444 
 2445         void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
 2446                         size_type __n_copy,  size_type __n_del, size_type __n_add = 0)
 2447         {
 2448             size_type __ms = max_size();
 2449             assert(__delta_cap <= __ms - __old_cap);
 2450 //            if (__delta_cap > __ms - __old_cap)
 2451 //                __throw_length_error();
 2452             pointer __old_p = __get_pointer();
 2453             size_type __cap = __old_cap < __ms / 2 - __alignment ?
 2454                                   __recommend(max(__old_cap + __delta_cap, 2 * __old_cap)) :
 2455                                   __ms - 1;
 2456             pointer __p = __alloc().allocate(__cap+1);
 2457 //            __invalidate_all_iterators(); // TODO:
 2458             if (__n_copy != 0)
 2459                 __p[0 .. __n_copy] = __old_p[0 .. __n_copy];
 2460             size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
 2461             if (__sec_cp_sz != 0)
 2462                 (__p + __n_copy + __n_add)[0 .. __sec_cp_sz] = (__old_p + __n_copy + __n_del)[0 .. __sec_cp_sz];
 2463             if (__old_cap+1 != __min_cap)
 2464                 __alloc().deallocate(__old_p, __old_cap+1);
 2465             __set_long_pointer(__p);
 2466             __set_long_cap(__cap+1);
 2467         }
 2468     }
 2469     else
 2470     {
 2471         static assert(false, "C++ runtime not supported");
 2472     }
 2473 }
 2474 
 2475 
 2476 // platform detail
 2477 private:
 2478 version (CppRuntime_Microsoft)
 2479 {
 2480     import core.stdcpp.xutility : _ITERATOR_DEBUG_LEVEL;
 2481 
 2482 extern(C++, (StdNamespace)):
 2483     extern (C++) struct _String_base_types(_Elem, _Alloc)
 2484     {
 2485         alias Ty = _Elem;
 2486         alias Alloc = _Alloc;
 2487     }
 2488 
 2489     extern (C++, class) struct _String_alloc(_Alloc_types)
 2490     {
 2491         import core.stdcpp.xutility : _Compressed_pair;
 2492 
 2493         alias Ty = _Alloc_types.Ty;
 2494         alias Alloc = _Alloc_types.Alloc;
 2495         alias ValTy = _String_val!Ty;
 2496 
 2497     extern(D) @safe @nogc:
 2498         pragma(inline, true)
 2499         {
 2500             ref inout(Alloc) _Getal() inout pure nothrow { return _Mypair._Myval1; }
 2501             ref inout(ValTy) _Get_data() inout pure nothrow { return _Mypair._Myval2; }
 2502         }
 2503 
 2504         void _Orphan_all() nothrow { _Get_data._Base._Orphan_all(); }
 2505 
 2506         static if (_ITERATOR_DEBUG_LEVEL > 0)
 2507         {
 2508             import core.stdcpp.xutility : _Container_proxy;
 2509 
 2510             ~this()
 2511             {
 2512                 _Free_proxy();
 2513             }
 2514 
 2515             pragma(inline, true)
 2516             ref inout(_Container_proxy*) _Myproxy() inout pure nothrow { return _Get_data._Base._Myproxy; }
 2517 
 2518             void _Alloc_proxy() nothrow @trusted
 2519             {
 2520                 import core.lifetime : emplace;
 2521 
 2522                 alias _Alproxy = Alloc.rebind!_Container_proxy;
 2523                 try // TODO: or should we make allocator<T>::allocate() `nothrow`?
 2524                     _Myproxy() = _Alproxy(_Getal()).allocate(1);
 2525                 catch (Throwable)
 2526                     assert(false, "Failed to allocate iterator debug container proxy");
 2527                 emplace!_Container_proxy(_Myproxy());
 2528                 _Myproxy()._Mycont = &_Get_data()._Base;
 2529             }
 2530             void _Free_proxy() nothrow @trusted
 2531             {
 2532                 alias _Alproxy = Alloc.rebind!_Container_proxy;
 2533                 _Orphan_all();
 2534                 destroy!false(*_Myproxy());
 2535                 try // TODO: or should we make allocator<T>::deallocate() `nothrow`?
 2536                     _Alproxy(_Getal()).deallocate(_Myproxy(), 1);
 2537                 catch (Throwable)
 2538                     assert(false, "Failed to deallocate iterator debug container proxy");
 2539                 _Myproxy() = null;
 2540             }
 2541         }
 2542 
 2543         _Compressed_pair!(Alloc, ValTy) _Mypair;
 2544     }
 2545 
 2546     extern (C++, class) struct _String_val(T)
 2547     {
 2548         import core.stdcpp.xutility : _Container_base;
 2549         import core.stdcpp.type_traits : is_empty;
 2550 
 2551         enum _BUF_SIZE = 16 / T.sizeof < 1 ? 1 : 16 / T.sizeof;
 2552         enum _ALLOC_MASK = T.sizeof <= 1 ? 15 : T.sizeof <= 2 ? 7 : T.sizeof <= 4 ? 3 : T.sizeof <= 8 ? 1 : 0;
 2553 
 2554         static if (!is_empty!_Container_base.value)
 2555             _Container_base _Base;
 2556         else
 2557             ref inout(_Container_base) _Base() inout { return *cast(inout(_Container_base)*)&this; }
 2558 
 2559         union _Bxty
 2560         {
 2561             T[_BUF_SIZE] _Buf;
 2562             T* _Ptr;
 2563         }
 2564 
 2565         _Bxty _Bx;
 2566         size_t _Mysize = 0;             // current length of string
 2567         size_t _Myres = _BUF_SIZE - 1;  // current storage reserved for string
 2568 
 2569     pragma (inline, true):
 2570     extern (D):
 2571     pure nothrow @nogc:
 2572         bool _IsAllocated() const @safe                 { return _BUF_SIZE <= _Myres; }
 2573         alias _Large_string_engaged = _IsAllocated;
 2574         @property inout(T)* _Myptr() inout @trusted     { return _BUF_SIZE <= _Myres ? _Bx._Ptr : _Bx._Buf.ptr; }
 2575         @property inout(T)[] _Mystr() inout @trusted    { return _BUF_SIZE <= _Myres ? _Bx._Ptr[0 .. _Mysize] : _Bx._Buf[0 .. _Mysize]; }
 2576 
 2577         auto _Clamp_suffix_size(T)(const T _Off, const T _Size) const
 2578         {
 2579             // trims _Size to the longest it can be assuming a string at/after _Off
 2580             return min(_Size, _Mysize - _Off);
 2581         }
 2582     }
 2583 
 2584     template _Size_after_ebco_v(_Ty)
 2585     {
 2586         import core.stdcpp.type_traits : is_empty;
 2587 
 2588         enum size_t _Size_after_ebco_v = is_empty!_Ty.value ? 0 : _Ty.sizeof; // get _Ty's size after being EBCO'd
 2589     }
 2590 }
 2591 
 2592 auto ref T max(T)(auto ref T a, auto ref T b) { return b > a ? b : a; }
 2593 auto ref T min(T)(auto ref T a, auto ref T b) { return b < a ? b : a; }