The OpenD Programming Language

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