64b50a182e1eb1e4bbb7ea8f7cd8c3241fc083e3
[WebKit-https.git] / Source / WTF / wtf / text / StringBuilder.h
1 /*
2  * Copyright (C) 2009-2018 Apple Inc. All rights reserved.
3  * Copyright (C) 2012 Google Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
25  */
26
27 #pragma once
28
29 #include <wtf/CheckedArithmetic.h>
30 #include <wtf/text/AtomString.h>
31 #include <wtf/text/IntegerToStringConversion.h>
32 #include <wtf/text/StringConcatenateNumbers.h>
33 #include <wtf/text/StringView.h>
34 #include <wtf/text/WTFString.h>
35
36 namespace WTF {
37
38 // StringBuilder currently uses a Checked<int32_t, ConditionalCrashOnOverflow> for m_length.
39 // Ideally, we would want to make StringBuilder a template with an OverflowHandler parameter, and
40 // m_length can be instantiated based on that OverflowHandler instead. However, currently, we're
41 // not able to get clang to export explicitly instantiated template methods (which would be needed
42 // if we templatize StringBuilder). As a workaround, we use the ConditionalCrashOnOverflow handler
43 // instead to do a runtime check on whether it should crash on overflows or not.
44 //
45 // When clang is able to export explicitly instantiated template methods, we can templatize
46 // StringBuilder and do away with ConditionalCrashOnOverflow.
47 // See https://bugs.webkit.org/show_bug.cgi?id=191050.
48
49 class StringBuilder {
50     // Disallow copying since it's expensive and we don't want code to do it by accident.
51     WTF_MAKE_NONCOPYABLE(StringBuilder);
52     WTF_MAKE_FAST_ALLOCATED;
53
54 public:
55     enum class OverflowHandler {
56         CrashOnOverflow,
57         RecordOverflow
58     };
59
60     StringBuilder(OverflowHandler handler = OverflowHandler::CrashOnOverflow)
61         : m_bufferCharacters8(nullptr)
62     {
63         m_length.setShouldCrashOnOverflow(handler == OverflowHandler::CrashOnOverflow);
64     }
65     StringBuilder(StringBuilder&&) = default;
66     StringBuilder& operator=(StringBuilder&&) = default;
67
68     ALWAYS_INLINE void didOverflow() { m_length.overflowed(); }
69     ALWAYS_INLINE bool hasOverflowed() const { return m_length.hasOverflowed(); }
70     ALWAYS_INLINE bool crashesOnOverflow() const { return m_length.shouldCrashOnOverflow(); }
71
72     WTF_EXPORT_PRIVATE void appendCharacters(const UChar*, unsigned);
73     WTF_EXPORT_PRIVATE void appendCharacters(const LChar*, unsigned);
74
75     ALWAYS_INLINE void appendCharacters(const char* characters, unsigned length) { appendCharacters(reinterpret_cast<const LChar*>(characters), length); }
76
77     void append(const AtomString& atomString)
78     {
79         append(atomString.string());
80     }
81
82     void append(const String& string)
83     {
84         if (hasOverflowed())
85             return;
86
87         if (!string.length())
88             return;
89
90         // If we're appending to an empty string, and there is not a buffer (reserveCapacity has not been called)
91         // then just retain the string.
92         if (!m_length && !m_buffer) {
93             m_string = string;
94             m_length = string.length();
95             m_is8Bit = m_string.is8Bit();
96             return;
97         }
98
99         if (string.is8Bit())
100             appendCharacters(string.characters8(), string.length());
101         else
102             appendCharacters(string.characters16(), string.length());
103     }
104
105     void append(const StringBuilder& other)
106     {
107         if (hasOverflowed())
108             return;
109         if (other.hasOverflowed())
110             return didOverflow();
111
112         if (!other.m_length)
113             return;
114
115         // If we're appending to an empty string, and there is not a buffer (reserveCapacity has not been called)
116         // then just retain the string.
117         if (!m_length && !m_buffer && !other.m_string.isNull()) {
118             m_string = other.m_string;
119             m_length = other.m_length;
120             m_is8Bit = other.m_is8Bit;
121             return;
122         }
123
124         if (other.is8Bit())
125             appendCharacters(other.characters8(), other.m_length.unsafeGet());
126         else
127             appendCharacters(other.characters16(), other.m_length.unsafeGet());
128     }
129
130     void append(StringView stringView)
131     {
132         if (stringView.is8Bit())
133             appendCharacters(stringView.characters8(), stringView.length());
134         else
135             appendCharacters(stringView.characters16(), stringView.length());
136     }
137
138 #if USE(CF)
139     WTF_EXPORT_PRIVATE void append(CFStringRef);
140 #endif
141 #if USE(CF) && defined(__OBJC__)
142     void append(NSString *string) { append((__bridge CFStringRef)string); }
143 #endif
144     
145     void appendSubstring(const String& string, unsigned offset, unsigned length)
146     {
147         if (!string.length())
148             return;
149
150         if ((offset + length) > string.length())
151             return;
152
153         if (string.is8Bit())
154             appendCharacters(string.characters8() + offset, length);
155         else
156             appendCharacters(string.characters16() + offset, length);
157     }
158
159     void append(const char* characters)
160     {
161         if (characters)
162             appendCharacters(characters, strlen(characters));
163     }
164
165     void appendCharacter(UChar) = delete;
166     void append(UChar c)
167     {
168         if (hasOverflowed())
169             return;
170         unsigned length = m_length.unsafeGet<unsigned>();
171         if (m_buffer && length < m_buffer->length() && m_string.isNull()) {
172             if (!m_is8Bit) {
173                 m_bufferCharacters16[length] = c;
174                 m_length++;
175                 return;
176             }
177
178             if (!(c & ~0xff)) {
179                 m_bufferCharacters8[length] = static_cast<LChar>(c);
180                 m_length++;
181                 return;
182             }
183         }
184         appendCharacters(&c, 1);
185     }
186
187     void appendCharacter(LChar) = delete;
188     void append(LChar c)
189     {
190         if (hasOverflowed())
191             return;
192         unsigned length = m_length.unsafeGet<unsigned>();
193         if (m_buffer && length < m_buffer->length() && m_string.isNull()) {
194             if (m_is8Bit)
195                 m_bufferCharacters8[length] = c;
196             else
197                 m_bufferCharacters16[length] = c;
198             m_length++;
199         } else
200             appendCharacters(&c, 1);
201     }
202
203     void appendCharacter(char) = delete;
204     void append(char c)
205     {
206         append(static_cast<LChar>(c));
207     }
208
209     void appendCharacter(UChar32 c)
210     {
211         if (U_IS_BMP(c)) {
212             append(static_cast<UChar>(c));
213             return;
214         }
215         append(U16_LEAD(c));
216         append(U16_TRAIL(c));
217     }
218
219     WTF_EXPORT_PRIVATE void appendQuotedJSONString(const String&);
220
221     template<unsigned characterCount>
222     ALWAYS_INLINE void appendLiteral(const char (&characters)[characterCount]) { appendCharacters(characters, characterCount - 1); }
223
224     WTF_EXPORT_PRIVATE void appendNumber(int);
225     WTF_EXPORT_PRIVATE void appendNumber(unsigned);
226     WTF_EXPORT_PRIVATE void appendNumber(long);
227     WTF_EXPORT_PRIVATE void appendNumber(unsigned long);
228     WTF_EXPORT_PRIVATE void appendNumber(long long);
229     WTF_EXPORT_PRIVATE void appendNumber(unsigned long long);
230     WTF_EXPORT_PRIVATE void appendNumber(float);
231     WTF_EXPORT_PRIVATE void appendNumber(double);
232
233     WTF_EXPORT_PRIVATE void appendFixedPrecisionNumber(float, unsigned precision = 6, TrailingZerosTruncatingPolicy = TruncateTrailingZeros);
234     WTF_EXPORT_PRIVATE void appendFixedPrecisionNumber(double, unsigned precision = 6, TrailingZerosTruncatingPolicy = TruncateTrailingZeros);
235     WTF_EXPORT_PRIVATE void appendFixedWidthNumber(float, unsigned decimalPlaces);
236     WTF_EXPORT_PRIVATE void appendFixedWidthNumber(double, unsigned decimalPlaces);
237
238     // FIXME: Rename to append(...) after renaming any overloads of append that take more than one argument.
239     template<typename... StringTypes> void flexibleAppend(StringTypes...);
240
241     String toString()
242     {
243         if (!m_string.isNull()) {
244             ASSERT(!m_buffer || m_isReified);
245             ASSERT(!hasOverflowed());
246             return m_string;
247         }
248
249         RELEASE_ASSERT(!hasOverflowed());
250         shrinkToFit();
251         reifyString();
252         return m_string;
253     }
254
255     const String& toStringPreserveCapacity() const
256     {
257         RELEASE_ASSERT(!hasOverflowed());
258         if (m_string.isNull())
259             reifyString();
260         return m_string;
261     }
262
263     AtomString toAtomString() const
264     {
265         RELEASE_ASSERT(!hasOverflowed());
266         if (!m_length)
267             return emptyAtom();
268
269         // If the buffer is sufficiently over-allocated, make a new AtomString from a copy so its buffer is not so large.
270         if (canShrink()) {
271             if (is8Bit())
272                 return AtomString(characters8(), length());
273             return AtomString(characters16(), length());            
274         }
275
276         if (!m_string.isNull())
277             return AtomString(m_string);
278
279         ASSERT(m_buffer);
280         return AtomString(m_buffer.get(), 0, m_length.unsafeGet());
281     }
282
283     unsigned length() const
284     {
285         RELEASE_ASSERT(!hasOverflowed());
286         return m_length.unsafeGet();
287     }
288
289     bool isEmpty() const { return !m_length; }
290
291     WTF_EXPORT_PRIVATE void reserveCapacity(unsigned newCapacity);
292
293     unsigned capacity() const
294     {
295         RELEASE_ASSERT(!hasOverflowed());
296         return m_buffer ? m_buffer->length() : m_length.unsafeGet();
297     }
298
299     WTF_EXPORT_PRIVATE void resize(unsigned newSize);
300
301     WTF_EXPORT_PRIVATE bool canShrink() const;
302
303     WTF_EXPORT_PRIVATE void shrinkToFit();
304
305     UChar operator[](unsigned i) const
306     {
307         RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(!hasOverflowed() && i < m_length.unsafeGet<unsigned>());
308         if (m_is8Bit)
309             return characters8()[i];
310         return characters16()[i];
311     }
312
313     const LChar* characters8() const
314     {
315         ASSERT(m_is8Bit);
316         if (!m_length)
317             return nullptr;
318         if (!m_string.isNull())
319             return m_string.characters8();
320         ASSERT(m_buffer);
321         return m_buffer->characters8();
322     }
323
324     const UChar* characters16() const
325     {
326         ASSERT(!m_is8Bit);
327         if (!m_length)
328             return nullptr;
329         if (!m_string.isNull())
330             return m_string.characters16();
331         ASSERT(m_buffer);
332         return m_buffer->characters16();
333     }
334     
335     bool is8Bit() const { return m_is8Bit; }
336
337     void clear()
338     {
339         m_length = 0;
340         m_string = String();
341         m_buffer = nullptr;
342         m_bufferCharacters8 = nullptr;
343         m_is8Bit = true;
344     }
345
346     void swap(StringBuilder& stringBuilder)
347     {
348         std::swap(m_length, stringBuilder.m_length);
349         m_string.swap(stringBuilder.m_string);
350         m_buffer.swap(stringBuilder.m_buffer);
351         std::swap(m_is8Bit, stringBuilder.m_is8Bit);
352         std::swap(m_bufferCharacters8, stringBuilder.m_bufferCharacters8);
353         ASSERT(!m_buffer || hasOverflowed() || m_buffer->length() >= m_length.unsafeGet<unsigned>());
354     }
355
356 private:
357     void allocateBuffer(const LChar* currentCharacters, unsigned requiredLength);
358     void allocateBuffer(const UChar* currentCharacters, unsigned requiredLength);
359     void allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength);
360     template<typename CharacterType> void reallocateBuffer(unsigned requiredLength);
361     template<typename CharacterType> ALWAYS_INLINE CharacterType* appendUninitialized(unsigned additionalLength);
362     template<typename CharacterType> ALWAYS_INLINE CharacterType* appendUninitializedWithoutOverflowCheck(CheckedInt32 requiredLength);
363     template<typename CharacterType> CharacterType* appendUninitializedSlow(unsigned requiredLength);
364     
365     WTF_EXPORT_PRIVATE UChar* appendUninitializedWithoutOverflowCheckForUChar(CheckedInt32 requiredLength);
366     WTF_EXPORT_PRIVATE LChar* appendUninitializedWithoutOverflowCheckForLChar(CheckedInt32 requiredLength);
367     
368     template<typename CharacterType> ALWAYS_INLINE CharacterType* getBufferCharacters();
369     WTF_EXPORT_PRIVATE void reifyString() const;
370
371     template<typename... StringTypeAdapters> void flexibleAppendFromAdapters(StringTypeAdapters...);
372
373     mutable String m_string;
374     RefPtr<StringImpl> m_buffer;
375     union {
376         LChar* m_bufferCharacters8;
377         UChar* m_bufferCharacters16;
378     };
379     static_assert(String::MaxLength == std::numeric_limits<int32_t>::max(), "");
380     Checked<int32_t, ConditionalCrashOnOverflow> m_length;
381     bool m_is8Bit { true };
382 #if !ASSERT_DISABLED
383     mutable bool m_isReified { false };
384 #endif
385 };
386
387 template<>
388 ALWAYS_INLINE LChar* StringBuilder::getBufferCharacters<LChar>()
389 {
390     ASSERT(m_is8Bit);
391     return m_bufferCharacters8;
392 }
393
394 template<>
395 ALWAYS_INLINE UChar* StringBuilder::getBufferCharacters<UChar>()
396 {
397     ASSERT(!m_is8Bit);
398     return m_bufferCharacters16;
399 }
400
401 template<typename... StringTypeAdapters>
402 void StringBuilder::flexibleAppendFromAdapters(StringTypeAdapters... adapters)
403 {
404     auto requiredLength = checkedSum<int32_t>(m_length, adapters.length()...);
405     if (requiredLength.hasOverflowed()) {
406         didOverflow();
407         return;
408     }
409
410     if (m_is8Bit && are8Bit(adapters...)) {
411         LChar* dest = appendUninitializedWithoutOverflowCheckForLChar(requiredLength);
412         if (!dest) {
413             ASSERT(hasOverflowed());
414             return;
415         }
416         stringTypeAdapterAccumulator(dest, adapters...);
417     } else {
418         UChar* dest = appendUninitializedWithoutOverflowCheckForUChar(requiredLength);
419         if (!dest) {
420             ASSERT(hasOverflowed());
421             return;
422         }
423         stringTypeAdapterAccumulator(dest, adapters...);
424     }
425 }
426
427 template<typename... StringTypes>
428 void StringBuilder::flexibleAppend(StringTypes... strings)
429 {
430     flexibleAppendFromAdapters(StringTypeAdapter<StringTypes>(strings)...);
431 }
432
433 template<typename CharacterType>
434 bool equal(const StringBuilder& s, const CharacterType* buffer, unsigned length)
435 {
436     if (s.length() != length)
437         return false;
438
439     if (s.is8Bit())
440         return equal(s.characters8(), buffer, length);
441
442     return equal(s.characters16(), buffer, length);
443 }
444
445 template<typename StringType>
446 bool equal(const StringBuilder& a, const StringType& b)
447 {
448     if (a.length() != b.length())
449         return false;
450
451     if (!a.length())
452         return true;
453
454     if (a.is8Bit()) {
455         if (b.is8Bit())
456             return equal(a.characters8(), b.characters8(), a.length());
457         return equal(a.characters8(), b.characters16(), a.length());
458     }
459
460     if (b.is8Bit())
461         return equal(a.characters16(), b.characters8(), a.length());
462     return equal(a.characters16(), b.characters16(), a.length());
463 }
464
465 inline bool operator==(const StringBuilder& a, const StringBuilder& b) { return equal(a, b); }
466 inline bool operator!=(const StringBuilder& a, const StringBuilder& b) { return !equal(a, b); }
467 inline bool operator==(const StringBuilder& a, const String& b) { return equal(a, b); }
468 inline bool operator!=(const StringBuilder& a, const String& b) { return !equal(a, b); }
469 inline bool operator==(const String& a, const StringBuilder& b) { return equal(b, a); }
470 inline bool operator!=(const String& a, const StringBuilder& b) { return !equal(b, a); }
471
472 template<> struct IntegerToStringConversionTrait<StringBuilder> {
473     using ReturnType = void;
474     using AdditionalArgumentType = StringBuilder;
475     static void flush(LChar* characters, unsigned length, StringBuilder* stringBuilder) { stringBuilder->appendCharacters(characters, length); }
476 };
477
478 } // namespace WTF
479
480 using WTF::StringBuilder;