ebaf73e6ef790c8269ab9a012d425488c57b1e11
[WebKit.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/AtomicString.h>
31 #include <wtf/text/IntegerToStringConversion.h>
32 #include <wtf/text/StringView.h>
33 #include <wtf/text/WTFString.h>
34
35 namespace WTF {
36
37 // StringBuilder currently uses a Checked<int32_t, ConditionalCrashOnOverflow> for m_length.
38 // Ideally, we would want to make StringBuilder a template with an OverflowHandler parameter, and
39 // m_length can be instantiated based on that OverflowHandler instead. However, currently, we're
40 // not able to get clang to export explicitly instantiated template methods (which would be needed
41 // if we templatize StringBuilder). As a workaround, we use the ConditionalCrashOnOverflow handler
42 // instead to do a runtime check on whether it should crash on overflows or not.
43 //
44 // When clang is able to export explicitly instantiated template methods, we can templatize
45 // StringBuilder and do away with ConditionalCrashOnOverflow.
46 // See https://bugs.webkit.org/show_bug.cgi?id=191050.
47
48 class StringBuilder {
49     // Disallow copying since it's expensive and we don't want code to do it by accident.
50     WTF_MAKE_NONCOPYABLE(StringBuilder);
51
52 public:
53     enum class OverflowHandler {
54         CrashOnOverflow,
55         RecordOverflow
56     };
57
58     StringBuilder(OverflowHandler handler = OverflowHandler::CrashOnOverflow)
59         : m_bufferCharacters8(nullptr)
60     {
61         m_length.setShouldCrashOnOverflow(handler == OverflowHandler::CrashOnOverflow);
62     }
63     StringBuilder(StringBuilder&&) = default;
64     StringBuilder& operator=(StringBuilder&&) = default;
65
66     ALWAYS_INLINE void didOverflow() { m_length.overflowed(); }
67     ALWAYS_INLINE bool hasOverflowed() const { return m_length.hasOverflowed(); }
68     ALWAYS_INLINE bool crashesOnOverflow() const { return m_length.shouldCrashOnOverflow(); }
69
70     WTF_EXPORT_PRIVATE void append(const UChar*, unsigned);
71     WTF_EXPORT_PRIVATE void append(const LChar*, unsigned);
72
73     ALWAYS_INLINE void append(const char* characters, unsigned length) { append(reinterpret_cast<const LChar*>(characters), length); }
74
75     void append(const AtomicString& atomicString)
76     {
77         append(atomicString.string());
78     }
79
80     void append(const String& string)
81     {
82         if (hasOverflowed())
83             return;
84
85         if (!string.length())
86             return;
87
88         // If we're appending to an empty string, and there is not a buffer (reserveCapacity has not been called)
89         // then just retain the string.
90         if (!m_length && !m_buffer) {
91             m_string = string;
92             m_length = string.length();
93             m_is8Bit = m_string.is8Bit();
94             return;
95         }
96
97         if (string.is8Bit())
98             append(string.characters8(), string.length());
99         else
100             append(string.characters16(), string.length());
101     }
102
103     void append(const StringBuilder& other)
104     {
105         if (hasOverflowed())
106             return;
107         if (other.hasOverflowed())
108             return didOverflow();
109
110         if (!other.m_length)
111             return;
112
113         // If we're appending to an empty string, and there is not a buffer (reserveCapacity has not been called)
114         // then just retain the string.
115         if (!m_length && !m_buffer && !other.m_string.isNull()) {
116             m_string = other.m_string;
117             m_length = other.m_length;
118             m_is8Bit = other.m_is8Bit;
119             return;
120         }
121
122         if (other.is8Bit())
123             append(other.characters8(), other.m_length.unsafeGet());
124         else
125             append(other.characters16(), other.m_length.unsafeGet());
126     }
127
128     void append(StringView stringView)
129     {
130         if (stringView.is8Bit())
131             append(stringView.characters8(), stringView.length());
132         else
133             append(stringView.characters16(), stringView.length());
134     }
135
136 #if USE(CF)
137     WTF_EXPORT_PRIVATE void append(CFStringRef);
138 #endif
139 #if USE(CF) && defined(__OBJC__)
140     void append(NSString *string) { append((__bridge CFStringRef)string); }
141 #endif
142     
143     void append(const String& string, unsigned offset, unsigned length)
144     {
145         if (!string.length())
146             return;
147
148         if ((offset + length) > string.length())
149             return;
150
151         if (string.is8Bit())
152             append(string.characters8() + offset, length);
153         else
154             append(string.characters16() + offset, length);
155     }
156
157     void append(const char* characters)
158     {
159         if (characters)
160             append(characters, strlen(characters));
161     }
162
163     void append(UChar c)
164     {
165         if (hasOverflowed())
166             return;
167         unsigned length = m_length.unsafeGet<unsigned>();
168         if (m_buffer && length < m_buffer->length() && m_string.isNull()) {
169             if (!m_is8Bit) {
170                 m_bufferCharacters16[length] = c;
171                 m_length++;
172                 return;
173             }
174
175             if (!(c & ~0xff)) {
176                 m_bufferCharacters8[length] = static_cast<LChar>(c);
177                 m_length++;
178                 return;
179             }
180         }
181         append(&c, 1);
182     }
183
184     void append(LChar c)
185     {
186         if (hasOverflowed())
187             return;
188         unsigned length = m_length.unsafeGet<unsigned>();
189         if (m_buffer && length < m_buffer->length() && m_string.isNull()) {
190             if (m_is8Bit)
191                 m_bufferCharacters8[length] = c;
192             else
193                 m_bufferCharacters16[length] = c;
194             m_length++;
195         } else
196             append(&c, 1);
197     }
198
199     void append(char c)
200     {
201         append(static_cast<LChar>(c));
202     }
203
204     void append(UChar32 c)
205     {
206         if (U_IS_BMP(c)) {
207             append(static_cast<UChar>(c));
208             return;
209         }
210         append(U16_LEAD(c));
211         append(U16_TRAIL(c));
212     }
213
214     WTF_EXPORT_PRIVATE void appendQuotedJSONString(const String&);
215
216     template<unsigned characterCount>
217     ALWAYS_INLINE void appendLiteral(const char (&characters)[characterCount]) { append(characters, characterCount - 1); }
218
219     WTF_EXPORT_PRIVATE void appendNumber(int);
220     WTF_EXPORT_PRIVATE void appendNumber(unsigned);
221     WTF_EXPORT_PRIVATE void appendNumber(long);
222     WTF_EXPORT_PRIVATE void appendNumber(unsigned long);
223     WTF_EXPORT_PRIVATE void appendNumber(long long);
224     WTF_EXPORT_PRIVATE void appendNumber(unsigned long long);
225     // FIXME: Change to call appendShortestFormNumber.
226     void appendNumber(float) = delete;
227     void appendNumber(double) = delete;
228
229     WTF_EXPORT_PRIVATE void appendShortestFormNumber(float);
230     WTF_EXPORT_PRIVATE void appendShortestFormNumber(double);
231     WTF_EXPORT_PRIVATE void appendFixedPrecisionNumber(float, unsigned precision = 6, TrailingZerosTruncatingPolicy = TruncateTrailingZeros);
232     WTF_EXPORT_PRIVATE void appendFixedPrecisionNumber(double, unsigned precision = 6, TrailingZerosTruncatingPolicy = TruncateTrailingZeros);
233     WTF_EXPORT_PRIVATE void appendFixedWidthNumber(float, unsigned decimalPlaces);
234     WTF_EXPORT_PRIVATE void appendFixedWidthNumber(double, unsigned decimalPlaces);
235
236     // FIXME: Delete in favor of the name appendShortestFormNumber or just appendNumber.
237     void appendECMAScriptNumber(float) = delete;
238     void appendECMAScriptNumber(double);
239
240     String toString()
241     {
242         if (!m_string.isNull()) {
243             ASSERT(!m_buffer || m_isReified);
244             ASSERT(!hasOverflowed());
245             return m_string;
246         }
247
248         RELEASE_ASSERT(!hasOverflowed());
249         shrinkToFit();
250         reifyString();
251         return m_string;
252     }
253
254     const String& toStringPreserveCapacity() const
255     {
256         RELEASE_ASSERT(!hasOverflowed());
257         if (m_string.isNull())
258             reifyString();
259         return m_string;
260     }
261
262     AtomicString toAtomicString() const
263     {
264         RELEASE_ASSERT(!hasOverflowed());
265         if (!m_length)
266             return emptyAtom();
267
268         // If the buffer is sufficiently over-allocated, make a new AtomicString from a copy so its buffer is not so large.
269         if (canShrink()) {
270             if (is8Bit())
271                 return AtomicString(characters8(), length());
272             return AtomicString(characters16(), length());            
273         }
274
275         if (!m_string.isNull())
276             return AtomicString(m_string);
277
278         ASSERT(m_buffer);
279         return AtomicString(m_buffer.get(), 0, m_length.unsafeGet());
280     }
281
282     unsigned length() const
283     {
284         RELEASE_ASSERT(!hasOverflowed());
285         return m_length.unsafeGet();
286     }
287
288     bool isEmpty() const { return !m_length; }
289
290     WTF_EXPORT_PRIVATE void reserveCapacity(unsigned newCapacity);
291
292     unsigned capacity() const
293     {
294         RELEASE_ASSERT(!hasOverflowed());
295         return m_buffer ? m_buffer->length() : m_length.unsafeGet();
296     }
297
298     WTF_EXPORT_PRIVATE void resize(unsigned newSize);
299
300     WTF_EXPORT_PRIVATE bool canShrink() const;
301
302     WTF_EXPORT_PRIVATE void shrinkToFit();
303
304     UChar operator[](unsigned i) const
305     {
306         RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(!hasOverflowed() && i < m_length.unsafeGet<unsigned>());
307         if (m_is8Bit)
308             return characters8()[i];
309         return characters16()[i];
310     }
311
312     const LChar* characters8() const
313     {
314         ASSERT(m_is8Bit);
315         if (!m_length)
316             return nullptr;
317         if (!m_string.isNull())
318             return m_string.characters8();
319         ASSERT(m_buffer);
320         return m_buffer->characters8();
321     }
322
323     const UChar* characters16() const
324     {
325         ASSERT(!m_is8Bit);
326         if (!m_length)
327             return nullptr;
328         if (!m_string.isNull())
329             return m_string.characters16();
330         ASSERT(m_buffer);
331         return m_buffer->characters16();
332     }
333     
334     bool is8Bit() const { return m_is8Bit; }
335
336     void clear()
337     {
338         m_length = 0;
339         m_string = String();
340         m_buffer = nullptr;
341         m_bufferCharacters8 = nullptr;
342         m_is8Bit = true;
343     }
344
345     void swap(StringBuilder& stringBuilder)
346     {
347         std::swap(m_length, stringBuilder.m_length);
348         m_string.swap(stringBuilder.m_string);
349         m_buffer.swap(stringBuilder.m_buffer);
350         std::swap(m_is8Bit, stringBuilder.m_is8Bit);
351         std::swap(m_bufferCharacters8, stringBuilder.m_bufferCharacters8);
352         ASSERT(!m_buffer || hasOverflowed() || m_buffer->length() >= m_length.unsafeGet<unsigned>());
353     }
354
355 private:
356     void allocateBuffer(const LChar* currentCharacters, unsigned requiredLength);
357     void allocateBuffer(const UChar* currentCharacters, unsigned requiredLength);
358     void allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength);
359     template <typename CharType>
360     void reallocateBuffer(unsigned requiredLength);
361     template <typename CharType>
362     ALWAYS_INLINE CharType* appendUninitialized(unsigned length);
363     template <typename CharType>
364     CharType* appendUninitializedSlow(unsigned length);
365     template <typename CharType>
366     ALWAYS_INLINE CharType * getBufferCharacters();
367     WTF_EXPORT_PRIVATE void reifyString() const;
368
369     mutable String m_string;
370     RefPtr<StringImpl> m_buffer;
371     union {
372         LChar* m_bufferCharacters8;
373         UChar* m_bufferCharacters16;
374     };
375     static_assert(String::MaxLength == std::numeric_limits<int32_t>::max(), "");
376     Checked<int32_t, ConditionalCrashOnOverflow> m_length;
377     bool m_is8Bit { true };
378 #if !ASSERT_DISABLED
379     mutable bool m_isReified { false };
380 #endif
381 };
382
383 template <>
384 ALWAYS_INLINE LChar* StringBuilder::getBufferCharacters<LChar>()
385 {
386     ASSERT(m_is8Bit);
387     return m_bufferCharacters8;
388 }
389
390 template <>
391 ALWAYS_INLINE UChar* StringBuilder::getBufferCharacters<UChar>()
392 {
393     ASSERT(!m_is8Bit);
394     return m_bufferCharacters16;
395 }
396
397 inline void StringBuilder::appendECMAScriptNumber(double number)
398 {
399     appendShortestFormNumber(number);
400 }
401
402 template <typename CharType>
403 bool equal(const StringBuilder& s, const CharType* buffer, unsigned length)
404 {
405     if (s.length() != length)
406         return false;
407
408     if (s.is8Bit())
409         return equal(s.characters8(), buffer, length);
410
411     return equal(s.characters16(), buffer, length);
412 }
413
414 template <typename StringType>
415 bool equal(const StringBuilder& a, const StringType& b)
416 {
417     if (a.length() != b.length())
418         return false;
419
420     if (!a.length())
421         return true;
422
423     if (a.is8Bit()) {
424         if (b.is8Bit())
425             return equal(a.characters8(), b.characters8(), a.length());
426         return equal(a.characters8(), b.characters16(), a.length());
427     }
428
429     if (b.is8Bit())
430         return equal(a.characters16(), b.characters8(), a.length());
431     return equal(a.characters16(), b.characters16(), a.length());
432 }
433
434 inline bool operator==(const StringBuilder& a, const StringBuilder& b) { return equal(a, b); }
435 inline bool operator!=(const StringBuilder& a, const StringBuilder& b) { return !equal(a, b); }
436 inline bool operator==(const StringBuilder& a, const String& b) { return equal(a, b); }
437 inline bool operator!=(const StringBuilder& a, const String& b) { return !equal(a, b); }
438 inline bool operator==(const String& a, const StringBuilder& b) { return equal(b, a); }
439 inline bool operator!=(const String& a, const StringBuilder& b) { return !equal(b, a); }
440
441 template<> struct IntegerToStringConversionTrait<StringBuilder> {
442     using ReturnType = void;
443     using AdditionalArgumentType = StringBuilder;
444     static void flush(LChar* characters, unsigned length, StringBuilder* stringBuilder) { stringBuilder->append(characters, length); }
445 };
446
447 } // namespace WTF
448
449 using WTF::StringBuilder;