d6204401f013334251d8b9715700034a211395d9
[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 append(UChar c)
166     {
167         if (hasOverflowed())
168             return;
169         unsigned length = m_length.unsafeGet<unsigned>();
170         if (m_buffer && length < m_buffer->length() && m_string.isNull()) {
171             if (!m_is8Bit) {
172                 m_bufferCharacters16[length] = c;
173                 m_length++;
174                 return;
175             }
176
177             if (!(c & ~0xff)) {
178                 m_bufferCharacters8[length] = static_cast<LChar>(c);
179                 m_length++;
180                 return;
181             }
182         }
183         appendCharacters(&c, 1);
184     }
185
186     void append(LChar c)
187     {
188         if (hasOverflowed())
189             return;
190         unsigned length = m_length.unsafeGet<unsigned>();
191         if (m_buffer && length < m_buffer->length() && m_string.isNull()) {
192             if (m_is8Bit)
193                 m_bufferCharacters8[length] = c;
194             else
195                 m_bufferCharacters16[length] = c;
196             m_length++;
197         } else
198             appendCharacters(&c, 1);
199     }
200
201     void append(char c)
202     {
203         append(static_cast<LChar>(c));
204     }
205
206     void append(UChar32 c)
207     {
208         if (U_IS_BMP(c)) {
209             append(static_cast<UChar>(c));
210             return;
211         }
212         append(U16_LEAD(c));
213         append(U16_TRAIL(c));
214     }
215
216     WTF_EXPORT_PRIVATE void appendQuotedJSONString(const String&);
217
218     template<unsigned characterCount>
219     ALWAYS_INLINE void appendLiteral(const char (&characters)[characterCount]) { appendCharacters(characters, characterCount - 1); }
220
221     WTF_EXPORT_PRIVATE void appendNumber(int);
222     WTF_EXPORT_PRIVATE void appendNumber(unsigned);
223     WTF_EXPORT_PRIVATE void appendNumber(long);
224     WTF_EXPORT_PRIVATE void appendNumber(unsigned long);
225     WTF_EXPORT_PRIVATE void appendNumber(long long);
226     WTF_EXPORT_PRIVATE void appendNumber(unsigned long long);
227     WTF_EXPORT_PRIVATE void appendNumber(float);
228     WTF_EXPORT_PRIVATE void appendNumber(double);
229
230     WTF_EXPORT_PRIVATE void appendFixedPrecisionNumber(float, unsigned precision = 6, TrailingZerosTruncatingPolicy = TruncateTrailingZeros);
231     WTF_EXPORT_PRIVATE void appendFixedPrecisionNumber(double, unsigned precision = 6, TrailingZerosTruncatingPolicy = TruncateTrailingZeros);
232     WTF_EXPORT_PRIVATE void appendFixedWidthNumber(float, unsigned decimalPlaces);
233     WTF_EXPORT_PRIVATE void appendFixedWidthNumber(double, unsigned decimalPlaces);
234
235     // FIXME: Rename to append(...) after renaming any overloads of append that take more than one argument.
236     template<typename... StringTypes> void flexibleAppend(StringTypes...);
237
238     String toString()
239     {
240         if (!m_string.isNull()) {
241             ASSERT(!m_buffer || m_isReified);
242             ASSERT(!hasOverflowed());
243             return m_string;
244         }
245
246         RELEASE_ASSERT(!hasOverflowed());
247         shrinkToFit();
248         reifyString();
249         return m_string;
250     }
251
252     const String& toStringPreserveCapacity() const
253     {
254         RELEASE_ASSERT(!hasOverflowed());
255         if (m_string.isNull())
256             reifyString();
257         return m_string;
258     }
259
260     AtomString toAtomString() const
261     {
262         RELEASE_ASSERT(!hasOverflowed());
263         if (!m_length)
264             return emptyAtom();
265
266         // If the buffer is sufficiently over-allocated, make a new AtomString from a copy so its buffer is not so large.
267         if (canShrink()) {
268             if (is8Bit())
269                 return AtomString(characters8(), length());
270             return AtomString(characters16(), length());            
271         }
272
273         if (!m_string.isNull())
274             return AtomString(m_string);
275
276         ASSERT(m_buffer);
277         return AtomString(m_buffer.get(), 0, m_length.unsafeGet());
278     }
279
280     unsigned length() const
281     {
282         RELEASE_ASSERT(!hasOverflowed());
283         return m_length.unsafeGet();
284     }
285
286     bool isEmpty() const { return !m_length; }
287
288     WTF_EXPORT_PRIVATE void reserveCapacity(unsigned newCapacity);
289
290     unsigned capacity() const
291     {
292         RELEASE_ASSERT(!hasOverflowed());
293         return m_buffer ? m_buffer->length() : m_length.unsafeGet();
294     }
295
296     WTF_EXPORT_PRIVATE void resize(unsigned newSize);
297
298     WTF_EXPORT_PRIVATE bool canShrink() const;
299
300     WTF_EXPORT_PRIVATE void shrinkToFit();
301
302     UChar operator[](unsigned i) const
303     {
304         RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(!hasOverflowed() && i < m_length.unsafeGet<unsigned>());
305         if (m_is8Bit)
306             return characters8()[i];
307         return characters16()[i];
308     }
309
310     const LChar* characters8() const
311     {
312         ASSERT(m_is8Bit);
313         if (!m_length)
314             return nullptr;
315         if (!m_string.isNull())
316             return m_string.characters8();
317         ASSERT(m_buffer);
318         return m_buffer->characters8();
319     }
320
321     const UChar* characters16() const
322     {
323         ASSERT(!m_is8Bit);
324         if (!m_length)
325             return nullptr;
326         if (!m_string.isNull())
327             return m_string.characters16();
328         ASSERT(m_buffer);
329         return m_buffer->characters16();
330     }
331     
332     bool is8Bit() const { return m_is8Bit; }
333
334     void clear()
335     {
336         m_length = 0;
337         m_string = String();
338         m_buffer = nullptr;
339         m_bufferCharacters8 = nullptr;
340         m_is8Bit = true;
341     }
342
343     void swap(StringBuilder& stringBuilder)
344     {
345         std::swap(m_length, stringBuilder.m_length);
346         m_string.swap(stringBuilder.m_string);
347         m_buffer.swap(stringBuilder.m_buffer);
348         std::swap(m_is8Bit, stringBuilder.m_is8Bit);
349         std::swap(m_bufferCharacters8, stringBuilder.m_bufferCharacters8);
350         ASSERT(!m_buffer || hasOverflowed() || m_buffer->length() >= m_length.unsafeGet<unsigned>());
351     }
352
353 private:
354     void allocateBuffer(const LChar* currentCharacters, unsigned requiredLength);
355     void allocateBuffer(const UChar* currentCharacters, unsigned requiredLength);
356     void allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength);
357     template<typename CharacterType> void reallocateBuffer(unsigned requiredLength);
358     template<typename CharacterType> ALWAYS_INLINE CharacterType* appendUninitialized(unsigned additionalLength);
359     template<typename CharacterType> ALWAYS_INLINE CharacterType* appendUninitializedWithoutOverflowCheck(CheckedInt32 requiredLength);
360     template<typename CharacterType> CharacterType* appendUninitializedSlow(unsigned requiredLength);
361     
362     WTF_EXPORT_PRIVATE UChar* appendUninitializedWithoutOverflowCheckForUChar(CheckedInt32 requiredLength);
363     WTF_EXPORT_PRIVATE LChar* appendUninitializedWithoutOverflowCheckForLChar(CheckedInt32 requiredLength);
364     
365     template<typename CharacterType> ALWAYS_INLINE CharacterType* getBufferCharacters();
366     WTF_EXPORT_PRIVATE void reifyString() const;
367
368     template<typename... StringTypeAdapters> void flexibleAppendFromAdapters(StringTypeAdapters...);
369
370     mutable String m_string;
371     RefPtr<StringImpl> m_buffer;
372     union {
373         LChar* m_bufferCharacters8;
374         UChar* m_bufferCharacters16;
375     };
376     static_assert(String::MaxLength == std::numeric_limits<int32_t>::max(), "");
377     Checked<int32_t, ConditionalCrashOnOverflow> m_length;
378     bool m_is8Bit { true };
379 #if !ASSERT_DISABLED
380     mutable bool m_isReified { false };
381 #endif
382 };
383
384 template<>
385 ALWAYS_INLINE LChar* StringBuilder::getBufferCharacters<LChar>()
386 {
387     ASSERT(m_is8Bit);
388     return m_bufferCharacters8;
389 }
390
391 template<>
392 ALWAYS_INLINE UChar* StringBuilder::getBufferCharacters<UChar>()
393 {
394     ASSERT(!m_is8Bit);
395     return m_bufferCharacters16;
396 }
397
398 template<typename... StringTypeAdapters>
399 void StringBuilder::flexibleAppendFromAdapters(StringTypeAdapters... adapters)
400 {
401     auto requiredLength = checkedSum<int32_t>(m_length, adapters.length()...);
402     if (requiredLength.hasOverflowed()) {
403         didOverflow();
404         return;
405     }
406
407     if (m_is8Bit && are8Bit(adapters...)) {
408         LChar* dest = appendUninitializedWithoutOverflowCheckForLChar(requiredLength);
409         if (!dest) {
410             ASSERT(hasOverflowed());
411             return;
412         }
413         stringTypeAdapterAccumulator(dest, adapters...);
414     } else {
415         UChar* dest = appendUninitializedWithoutOverflowCheckForUChar(requiredLength);
416         if (!dest) {
417             ASSERT(hasOverflowed());
418             return;
419         }
420         stringTypeAdapterAccumulator(dest, adapters...);
421     }
422 }
423
424 template<typename... StringTypes>
425 void StringBuilder::flexibleAppend(StringTypes... strings)
426 {
427     flexibleAppendFromAdapters(StringTypeAdapter<StringTypes>(strings)...);
428 }
429
430 template<typename CharacterType>
431 bool equal(const StringBuilder& s, const CharacterType* buffer, unsigned length)
432 {
433     if (s.length() != length)
434         return false;
435
436     if (s.is8Bit())
437         return equal(s.characters8(), buffer, length);
438
439     return equal(s.characters16(), buffer, length);
440 }
441
442 template<typename StringType>
443 bool equal(const StringBuilder& a, const StringType& b)
444 {
445     if (a.length() != b.length())
446         return false;
447
448     if (!a.length())
449         return true;
450
451     if (a.is8Bit()) {
452         if (b.is8Bit())
453             return equal(a.characters8(), b.characters8(), a.length());
454         return equal(a.characters8(), b.characters16(), a.length());
455     }
456
457     if (b.is8Bit())
458         return equal(a.characters16(), b.characters8(), a.length());
459     return equal(a.characters16(), b.characters16(), a.length());
460 }
461
462 inline bool operator==(const StringBuilder& a, const StringBuilder& b) { return equal(a, b); }
463 inline bool operator!=(const StringBuilder& a, const StringBuilder& b) { return !equal(a, b); }
464 inline bool operator==(const StringBuilder& a, const String& b) { return equal(a, b); }
465 inline bool operator!=(const StringBuilder& a, const String& b) { return !equal(a, b); }
466 inline bool operator==(const String& a, const StringBuilder& b) { return equal(b, a); }
467 inline bool operator!=(const String& a, const StringBuilder& b) { return !equal(b, a); }
468
469 template<> struct IntegerToStringConversionTrait<StringBuilder> {
470     using ReturnType = void;
471     using AdditionalArgumentType = StringBuilder;
472     static void flush(LChar* characters, unsigned length, StringBuilder* stringBuilder) { stringBuilder->appendCharacters(characters, length); }
473 };
474
475 } // namespace WTF
476
477 using WTF::StringBuilder;