2009-11-19 Laszlo Gombos <laszlo.1.gombos@nokia.com>
[WebKit-https.git] / JavaScriptCore / runtime / UString.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
4  *  Copyright (C) 2007 Cameron Zwarich (cwzwarich@uwaterloo.ca)
5  *  Copyright (C) 2009 Google Inc. All rights reserved.
6  *
7  *  This library is free software; you can redistribute it and/or
8  *  modify it under the terms of the GNU Library General Public
9  *  License as published by the Free Software Foundation; either
10  *  version 2 of the License, or (at your option) any later version.
11  *
12  *  This library is distributed in the hope that it will be useful,
13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  *  Library General Public License for more details.
16  *
17  *  You should have received a copy of the GNU Library General Public License
18  *  along with this library; see the file COPYING.LIB.  If not, write to
19  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  *  Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #include "config.h"
25 #include "UString.h"
26
27 #include "JSGlobalObjectFunctions.h"
28 #include "Collector.h"
29 #include "dtoa.h"
30 #include "Identifier.h"
31 #include "Operations.h"
32 #include <ctype.h>
33 #include <limits.h>
34 #include <limits>
35 #include <math.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39 #include <wtf/ASCIICType.h>
40 #include <wtf/Assertions.h>
41 #include <wtf/MathExtras.h>
42 #include <wtf/StringExtras.h>
43 #include <wtf/Vector.h>
44 #include <wtf/unicode/UTF8.h>
45 #include <wtf/StringExtras.h>
46
47 #if HAVE(STRINGS_H)
48 #include <strings.h>
49 #endif
50
51 using namespace WTF;
52 using namespace WTF::Unicode;
53 using namespace std;
54
55 // This can be tuned differently per platform by putting platform #ifs right here.
56 // If you don't define this macro at all, then copyChars will just call directly
57 // to memcpy.
58 #define USTRING_COPY_CHARS_INLINE_CUTOFF 20
59
60 namespace JSC {
61  
62 extern const double NaN;
63 extern const double Inf;
64
65 // This number must be at least 2 to avoid sharing empty, null as well as 1 character strings from SmallStrings.
66 static const int minLengthToShare = 10;
67
68 static inline size_t overflowIndicator() { return std::numeric_limits<size_t>::max(); }
69 static inline size_t maxUChars() { return std::numeric_limits<size_t>::max() / sizeof(UChar); }
70
71 static inline PossiblyNull<UChar*> allocChars(size_t length)
72 {
73     ASSERT(length);
74     if (length > maxUChars())
75         return 0;
76     return tryFastMalloc(sizeof(UChar) * length);
77 }
78
79 static inline PossiblyNull<UChar*> reallocChars(UChar* buffer, size_t length)
80 {
81     ASSERT(length);
82     if (length > maxUChars())
83         return 0;
84     return tryFastRealloc(buffer, sizeof(UChar) * length);
85 }
86
87 static inline void copyChars(UChar* destination, const UChar* source, unsigned numCharacters)
88 {
89 #ifdef USTRING_COPY_CHARS_INLINE_CUTOFF
90     if (numCharacters <= USTRING_COPY_CHARS_INLINE_CUTOFF) {
91         for (unsigned i = 0; i < numCharacters; ++i)
92             destination[i] = source[i];
93         return;
94     }
95 #endif
96     memcpy(destination, source, numCharacters * sizeof(UChar));
97 }
98
99 COMPILE_ASSERT(sizeof(UChar) == 2, uchar_is_2_bytes);
100
101 CString::CString(const char* c)
102     : m_length(strlen(c))
103     , m_data(new char[m_length + 1])
104 {
105     memcpy(m_data, c, m_length + 1);
106 }
107
108 CString::CString(const char* c, size_t length)
109     : m_length(length)
110     , m_data(new char[length + 1])
111 {
112     memcpy(m_data, c, m_length);
113     m_data[m_length] = 0;
114 }
115
116 CString::CString(const CString& b)
117 {
118     m_length = b.m_length;
119     if (b.m_data) {
120         m_data = new char[m_length + 1];
121         memcpy(m_data, b.m_data, m_length + 1);
122     } else
123         m_data = 0;
124 }
125
126 CString::~CString()
127 {
128     delete [] m_data;
129 }
130
131 CString CString::adopt(char* c, size_t length)
132 {
133     CString s;
134     s.m_data = c;
135     s.m_length = length;
136     return s;
137 }
138
139 CString& CString::append(const CString& t)
140 {
141     char* n;
142     n = new char[m_length + t.m_length + 1];
143     if (m_length)
144         memcpy(n, m_data, m_length);
145     if (t.m_length)
146         memcpy(n + m_length, t.m_data, t.m_length);
147     m_length += t.m_length;
148     n[m_length] = 0;
149
150     delete [] m_data;
151     m_data = n;
152
153     return *this;
154 }
155
156 CString& CString::operator=(const char* c)
157 {
158     if (m_data)
159         delete [] m_data;
160     m_length = strlen(c);
161     m_data = new char[m_length + 1];
162     memcpy(m_data, c, m_length + 1);
163
164     return *this;
165 }
166
167 CString& CString::operator=(const CString& str)
168 {
169     if (this == &str)
170         return *this;
171
172     if (m_data)
173         delete [] m_data;
174     m_length = str.m_length;
175     if (str.m_data) {
176         m_data = new char[m_length + 1];
177         memcpy(m_data, str.m_data, m_length + 1);
178     } else
179         m_data = 0;
180
181     return *this;
182 }
183
184 bool operator==(const CString& c1, const CString& c2)
185 {
186     size_t len = c1.size();
187     return len == c2.size() && (len == 0 || memcmp(c1.c_str(), c2.c_str(), len) == 0);
188 }
189
190 // These static strings are immutable, except for rc, whose initial value is chosen to 
191 // reduce the possibility of it becoming zero due to ref/deref not being thread-safe.
192 static UChar sharedEmptyChar;
193 UString::BaseString* UString::Rep::nullBaseString;
194 UString::BaseString* UString::Rep::emptyBaseString;
195 UString* UString::nullUString;
196
197 static void initializeStaticBaseString(UString::BaseString& base)
198 {
199     base.rc = INT_MAX / 2;
200     base.m_identifierTableAndFlags.setFlag(UString::Rep::StaticFlag);
201     base.checkConsistency();
202 }
203
204 void initializeUString()
205 {
206     UString::Rep::nullBaseString = new UString::BaseString(0, 0);
207     initializeStaticBaseString(*UString::Rep::nullBaseString);
208
209     UString::Rep::emptyBaseString = new UString::BaseString(&sharedEmptyChar, 0);
210     initializeStaticBaseString(*UString::Rep::emptyBaseString);
211
212     UString::nullUString = new UString;
213 }
214
215 static char* statBuffer = 0; // Only used for debugging via UString::ascii().
216
217 PassRefPtr<UString::Rep> UString::Rep::createCopying(const UChar* d, int l)
218 {
219     UChar* copyD = static_cast<UChar*>(fastMalloc(l * sizeof(UChar)));
220     copyChars(copyD, d, l);
221     return create(copyD, l);
222 }
223
224 PassRefPtr<UString::Rep> UString::Rep::createFromUTF8(const char* string)
225 {
226     if (!string)
227         return &UString::Rep::null();
228
229     size_t length = strlen(string);
230     Vector<UChar, 1024> buffer(length);
231     UChar* p = buffer.data();
232     if (conversionOK != convertUTF8ToUTF16(&string, string + length, &p, p + length))
233         return &UString::Rep::null();
234
235     return UString::Rep::createCopying(buffer.data(), p - buffer.data());
236 }
237
238 PassRefPtr<UString::Rep> UString::Rep::create(UChar* string, int length, PassRefPtr<UString::SharedUChar> sharedBuffer)
239 {
240     PassRefPtr<UString::Rep> rep = create(string, length);
241     rep->baseString()->setSharedBuffer(sharedBuffer);
242     rep->checkConsistency();
243     return rep;
244 }
245
246 UString::SharedUChar* UString::Rep::sharedBuffer()
247 {
248     UString::BaseString* base = baseString();
249     if (len < minLengthToShare)
250         return 0;
251
252     return base->sharedBuffer();
253 }
254
255 void UString::Rep::destroy()
256 {
257     checkConsistency();
258
259     // Static null and empty strings can never be destroyed, but we cannot rely on 
260     // reference counting, because ref/deref are not thread-safe.
261     if (!isStatic()) {
262         if (identifierTable())
263             Identifier::remove(this);
264
265         UString::BaseString* base = baseString();
266         if (base == this) {
267             if (m_sharedBuffer)
268                 m_sharedBuffer->deref();
269             else
270                 fastFree(base->buf);
271         } else
272             base->deref();
273
274         delete this;
275     }
276 }
277
278 // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
279 // or anything like that.
280 const unsigned PHI = 0x9e3779b9U;
281
282 // Paul Hsieh's SuperFastHash
283 // http://www.azillionmonkeys.com/qed/hash.html
284 unsigned UString::Rep::computeHash(const UChar* s, int len)
285 {
286     unsigned l = len;
287     uint32_t hash = PHI;
288     uint32_t tmp;
289
290     int rem = l & 1;
291     l >>= 1;
292
293     // Main loop
294     for (; l > 0; l--) {
295         hash += s[0];
296         tmp = (s[1] << 11) ^ hash;
297         hash = (hash << 16) ^ tmp;
298         s += 2;
299         hash += hash >> 11;
300     }
301
302     // Handle end case
303     if (rem) {
304         hash += s[0];
305         hash ^= hash << 11;
306         hash += hash >> 17;
307     }
308
309     // Force "avalanching" of final 127 bits
310     hash ^= hash << 3;
311     hash += hash >> 5;
312     hash ^= hash << 2;
313     hash += hash >> 15;
314     hash ^= hash << 10;
315
316     // this avoids ever returning a hash code of 0, since that is used to
317     // signal "hash not computed yet", using a value that is likely to be
318     // effectively the same as 0 when the low bits are masked
319     if (hash == 0)
320         hash = 0x80000000;
321
322     return hash;
323 }
324
325 // Paul Hsieh's SuperFastHash
326 // http://www.azillionmonkeys.com/qed/hash.html
327 unsigned UString::Rep::computeHash(const char* s, int l)
328 {
329     // This hash is designed to work on 16-bit chunks at a time. But since the normal case
330     // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
331     // were 16-bit chunks, which should give matching results
332
333     uint32_t hash = PHI;
334     uint32_t tmp;
335
336     size_t rem = l & 1;
337     l >>= 1;
338
339     // Main loop
340     for (; l > 0; l--) {
341         hash += static_cast<unsigned char>(s[0]);
342         tmp = (static_cast<unsigned char>(s[1]) << 11) ^ hash;
343         hash = (hash << 16) ^ tmp;
344         s += 2;
345         hash += hash >> 11;
346     }
347
348     // Handle end case
349     if (rem) {
350         hash += static_cast<unsigned char>(s[0]);
351         hash ^= hash << 11;
352         hash += hash >> 17;
353     }
354
355     // Force "avalanching" of final 127 bits
356     hash ^= hash << 3;
357     hash += hash >> 5;
358     hash ^= hash << 2;
359     hash += hash >> 15;
360     hash ^= hash << 10;
361
362     // this avoids ever returning a hash code of 0, since that is used to
363     // signal "hash not computed yet", using a value that is likely to be
364     // effectively the same as 0 when the low bits are masked
365     if (hash == 0)
366         hash = 0x80000000;
367
368     return hash;
369 }
370
371 #ifndef NDEBUG
372 void UString::Rep::checkConsistency() const
373 {
374     const UString::BaseString* base = baseString();
375
376     // There is no recursion for base strings.
377     ASSERT(base == base->baseString());
378
379     if (isStatic()) {
380         // There are only two static strings: null and empty.
381         ASSERT(!len);
382
383         // Static strings cannot get in identifier tables, because they are globally shared.
384         ASSERT(!identifierTable());
385     }
386
387     // The string fits in buffer.
388     ASSERT(base->usedPreCapacity <= base->preCapacity);
389     ASSERT(base->usedCapacity <= base->capacity);
390     ASSERT(-offset <= base->usedPreCapacity);
391     ASSERT(offset + len <= base->usedCapacity);
392 }
393 #endif
394
395 UString::SharedUChar* UString::BaseString::sharedBuffer()
396 {
397     if (!m_sharedBuffer)
398         setSharedBuffer(SharedUChar::create(new OwnFastMallocPtr<UChar>(buf)));
399     return m_sharedBuffer;
400 }
401
402 void UString::BaseString::setSharedBuffer(PassRefPtr<UString::SharedUChar> sharedBuffer)
403 {
404     // The manual steps below are because m_sharedBuffer can't be a RefPtr. m_sharedBuffer
405     // is in a union with another variable to avoid making BaseString any larger.
406     if (m_sharedBuffer)
407         m_sharedBuffer->deref();
408     m_sharedBuffer = sharedBuffer.releaseRef();
409 }
410
411 bool UString::BaseString::slowIsBufferReadOnly()
412 {
413     // The buffer may not be modified as soon as the underlying data has been shared with another class.
414     if (m_sharedBuffer->isShared())
415         return true;
416
417     // At this point, we know it that the underlying buffer isn't shared outside of this base class,
418     // so get rid of m_sharedBuffer.
419     OwnPtr<OwnFastMallocPtr<UChar> > mallocPtr(m_sharedBuffer->release());
420     UChar* unsharedBuf = const_cast<UChar*>(mallocPtr->release());
421     setSharedBuffer(0);
422     preCapacity += (buf - unsharedBuf);
423     buf = unsharedBuf;
424     return false;
425 }
426
427 // Put these early so they can be inlined.
428 static inline size_t expandedSize(size_t capacitySize, size_t precapacitySize)
429 {
430     // Combine capacitySize & precapacitySize to produce a single size to allocate,
431     // check that doing so does not result in overflow.
432     size_t size = capacitySize + precapacitySize;
433     if (size < capacitySize)
434         return overflowIndicator();
435
436     // Small Strings (up to 4 pages):
437     // Expand the allocation size to 112.5% of the amount requested.  This is largely sicking
438     // to our previous policy, however 112.5% is cheaper to calculate.
439     if (size < 0x4000) {
440         size_t expandedSize = ((size + (size >> 3)) | 15) + 1;
441         // Given the limited range within which we calculate the expansion in this
442         // fashion the above calculation should never overflow.
443         ASSERT(expandedSize >= size);
444         ASSERT(expandedSize < maxUChars());
445         return expandedSize;
446     }
447
448     // Medium Strings (up to 128 pages):
449     // For pages covering multiple pages over-allocation is less of a concern - any unused
450     // space will not be paged in if it is not used, so this is purely a VM overhead.  For
451     // these strings allocate 2x the requested size.
452     if (size < 0x80000) {
453         size_t expandedSize = ((size + size) | 0xfff) + 1;
454         // Given the limited range within which we calculate the expansion in this
455         // fashion the above calculation should never overflow.
456         ASSERT(expandedSize >= size);
457         ASSERT(expandedSize < maxUChars());
458         return expandedSize;
459     }
460
461     // Large Strings (to infinity and beyond!):
462     // Revert to our 112.5% policy - probably best to limit the amount of unused VM we allow
463     // any individual string be responsible for.
464     size_t expandedSize = ((size + (size >> 3)) | 0xfff) + 1;
465
466     // Check for overflow - any result that is at least as large as requested (but
467     // still below the limit) is okay.
468     if ((expandedSize >= size) && (expandedSize < maxUChars()))
469         return expandedSize;
470     return overflowIndicator();
471 }
472
473 static inline bool expandCapacity(UString::Rep* rep, int requiredLength)
474 {
475     rep->checkConsistency();
476     ASSERT(!rep->baseString()->isBufferReadOnly());
477
478     UString::BaseString* base = rep->baseString();
479
480     if (requiredLength > base->capacity) {
481         size_t newCapacity = expandedSize(requiredLength, base->preCapacity);
482         UChar* oldBuf = base->buf;
483         if (!reallocChars(base->buf, newCapacity).getValue(base->buf)) {
484             base->buf = oldBuf;
485             return false;
486         }
487         base->capacity = newCapacity - base->preCapacity;
488     }
489     if (requiredLength > base->usedCapacity)
490         base->usedCapacity = requiredLength;
491
492     rep->checkConsistency();
493     return true;
494 }
495
496 bool UString::Rep::reserveCapacity(int capacity)
497 {
498     // If this is an empty string there is no point 'growing' it - just allocate a new one.
499     // If the BaseString is shared with another string that is using more capacity than this
500     // string is, then growing the buffer won't help.
501     // If the BaseString's buffer is readonly, then it isn't allowed to grow.
502     UString::BaseString* base = baseString();
503     if (!base->buf || !base->capacity || (offset + len) != base->usedCapacity || base->isBufferReadOnly())
504         return false;
505     
506     // If there is already sufficient capacity, no need to grow!
507     if (capacity <= base->capacity)
508         return true;
509
510     checkConsistency();
511
512     size_t newCapacity = expandedSize(capacity, base->preCapacity);
513     UChar* oldBuf = base->buf;
514     if (!reallocChars(base->buf, newCapacity).getValue(base->buf)) {
515         base->buf = oldBuf;
516         return false;
517     }
518     base->capacity = newCapacity - base->preCapacity;
519
520     checkConsistency();
521     return true;
522 }
523
524 void UString::expandCapacity(int requiredLength)
525 {
526     if (!JSC::expandCapacity(m_rep.get(), requiredLength))
527         makeNull();
528 }
529
530 void UString::expandPreCapacity(int requiredPreCap)
531 {
532     m_rep->checkConsistency();
533     ASSERT(!m_rep->baseString()->isBufferReadOnly());
534
535     BaseString* base = m_rep->baseString();
536
537     if (requiredPreCap > base->preCapacity) {
538         size_t newCapacity = expandedSize(requiredPreCap, base->capacity);
539         int delta = newCapacity - base->capacity - base->preCapacity;
540
541         UChar* newBuf;
542         if (!allocChars(newCapacity).getValue(newBuf)) {
543             makeNull();
544             return;
545         }
546         copyChars(newBuf + delta, base->buf, base->capacity + base->preCapacity);
547         fastFree(base->buf);
548         base->buf = newBuf;
549
550         base->preCapacity = newCapacity - base->capacity;
551     }
552     if (requiredPreCap > base->usedPreCapacity)
553         base->usedPreCapacity = requiredPreCap;
554
555     m_rep->checkConsistency();
556 }
557
558 static PassRefPtr<UString::Rep> createRep(const char* c)
559 {
560     if (!c)
561         return &UString::Rep::null();
562
563     if (!c[0])
564         return &UString::Rep::empty();
565
566     size_t length = strlen(c);
567     UChar* d;
568     if (!allocChars(length).getValue(d))
569         return &UString::Rep::null();
570     else {
571         for (size_t i = 0; i < length; i++)
572             d[i] = static_cast<unsigned char>(c[i]); // use unsigned char to zero-extend instead of sign-extend
573         return UString::Rep::create(d, static_cast<int>(length));
574     }
575
576 }
577
578 static inline PassRefPtr<UString::Rep> createRep(const char* c, int length)
579 {
580     if (!c)
581         return &UString::Rep::null();
582
583     if (!length)
584         return &UString::Rep::empty();
585
586     UChar* d;
587     if (!allocChars(length).getValue(d))
588         return &UString::Rep::null();
589
590     for (int i = 0; i < length; i++)
591         d[i] = static_cast<unsigned char>(c[i]); // use unsigned char to zero-extend instead of sign-extend
592     return UString::Rep::create(d, length);
593 }
594
595 UString::UString(const char* c)
596     : m_rep(createRep(c))
597 {
598 }
599
600 UString::UString(const char* c, int length)
601     : m_rep(createRep(c, length))
602 {
603 }
604
605 UString::UString(const UChar* c, int length)
606 {
607     if (length == 0) 
608         m_rep = &Rep::empty();
609     else
610         m_rep = Rep::createCopying(c, length);
611 }
612
613 UString::UString(UChar* c, int length, bool copy)
614 {
615     if (length == 0)
616         m_rep = &Rep::empty();
617     else if (copy)
618         m_rep = Rep::createCopying(c, length);
619     else
620         m_rep = Rep::create(c, length);
621 }
622
623 UString::UString(const Vector<UChar>& buffer)
624 {
625     if (!buffer.size())
626         m_rep = &Rep::empty();
627     else
628         m_rep = Rep::createCopying(buffer.data(), buffer.size());
629 }
630
631 static ALWAYS_INLINE int newCapacityWithOverflowCheck(const int currentCapacity, const int extendLength, const bool plusOne = false)
632 {
633     ASSERT_WITH_MESSAGE(extendLength >= 0, "extendedLength = %d", extendLength);
634
635     const int plusLength = plusOne ? 1 : 0;
636     if (currentCapacity > std::numeric_limits<int>::max() - extendLength - plusLength)
637         CRASH();
638
639     return currentCapacity + extendLength + plusLength;
640 }
641
642 static ALWAYS_INLINE PassRefPtr<UString::Rep> concatenate(PassRefPtr<UString::Rep> r, const UChar* tData, int tSize)
643 {
644     RefPtr<UString::Rep> rep = r;
645
646     rep->checkConsistency();
647
648     int thisSize = rep->size();
649     int thisOffset = rep->offset;
650     int length = thisSize + tSize;
651     UString::BaseString* base = rep->baseString();
652
653     // possible cases:
654     if (tSize == 0) {
655         // t is empty
656     } else if (thisSize == 0) {
657         // this is empty
658         rep = UString::Rep::createCopying(tData, tSize);
659     } else if (rep == base && !base->isShared()) {
660         // this is direct and has refcount of 1 (so we can just alter it directly)
661         if (!expandCapacity(rep.get(), newCapacityWithOverflowCheck(thisOffset, length)))
662             rep = &UString::Rep::null();
663         if (rep->data()) {
664             copyChars(rep->data() + thisSize, tData, tSize);
665             rep->len = length;
666             rep->_hash = 0;
667         }
668     } else if (thisOffset + thisSize == base->usedCapacity && thisSize >= minShareSize && !base->isBufferReadOnly()) {
669         // this reaches the end of the buffer - extend it if it's long enough to append to
670         if (!expandCapacity(rep.get(), newCapacityWithOverflowCheck(thisOffset, length)))
671             rep = &UString::Rep::null();
672         if (rep->data()) {
673             copyChars(rep->data() + thisSize, tData, tSize);
674             rep = UString::Rep::create(rep, 0, length);
675         }
676     } else {
677         // This is shared in some way that prevents us from modifying base, so we must make a whole new string.
678         size_t newCapacity = expandedSize(length, 0);
679         UChar* d;
680         if (!allocChars(newCapacity).getValue(d))
681             rep = &UString::Rep::null();
682         else {
683             copyChars(d, rep->data(), thisSize);
684             copyChars(d + thisSize, tData, tSize);
685             rep = UString::Rep::create(d, length);
686             rep->baseString()->capacity = newCapacity;
687         }
688     }
689
690     rep->checkConsistency();
691
692     return rep.release();
693 }
694
695 static ALWAYS_INLINE PassRefPtr<UString::Rep> concatenate(PassRefPtr<UString::Rep> r, const char* t)
696 {
697     RefPtr<UString::Rep> rep = r;
698
699     rep->checkConsistency();
700
701     int thisSize = rep->size();
702     int thisOffset = rep->offset;
703     int tSize = static_cast<int>(strlen(t));
704     int length = thisSize + tSize;
705     UString::BaseString* base = rep->baseString();
706
707     // possible cases:
708     if (thisSize == 0) {
709         // this is empty
710         rep = createRep(t);
711     } else if (tSize == 0) {
712         // t is empty, we'll just return *this below.
713     } else if (rep == base && !base->isShared()) {
714         // this is direct and has refcount of 1 (so we can just alter it directly)
715         expandCapacity(rep.get(), newCapacityWithOverflowCheck(thisOffset, length));
716         UChar* d = rep->data();
717         if (d) {
718             for (int i = 0; i < tSize; ++i)
719                 d[thisSize + i] = static_cast<unsigned char>(t[i]); // use unsigned char to zero-extend instead of sign-extend
720             rep->len = length;
721             rep->_hash = 0;
722         }
723     } else if (thisOffset + thisSize == base->usedCapacity && thisSize >= minShareSize && !base->isBufferReadOnly()) {
724         // this string reaches the end of the buffer - extend it
725         expandCapacity(rep.get(), newCapacityWithOverflowCheck(thisOffset, length));
726         UChar* d = rep->data();
727         if (d) {
728             for (int i = 0; i < tSize; ++i)
729                 d[thisSize + i] = static_cast<unsigned char>(t[i]); // use unsigned char to zero-extend instead of sign-extend
730             rep = UString::Rep::create(rep, 0, length);
731         }
732     } else {
733         // This is shared in some way that prevents us from modifying base, so we must make a whole new string.
734         size_t newCapacity = expandedSize(length, 0);
735         UChar* d;
736         if (!allocChars(newCapacity).getValue(d))
737             rep = &UString::Rep::null();
738         else {
739             copyChars(d, rep->data(), thisSize);
740             for (int i = 0; i < tSize; ++i)
741                 d[thisSize + i] = static_cast<unsigned char>(t[i]); // use unsigned char to zero-extend instead of sign-extend
742             rep = UString::Rep::create(d, length);
743             rep->baseString()->capacity = newCapacity;
744         }
745     }
746
747     rep->checkConsistency();
748
749     return rep.release();
750 }
751
752 PassRefPtr<UString::Rep> concatenate(UString::Rep* a, UString::Rep* b)
753 {
754     a->checkConsistency();
755     b->checkConsistency();
756
757     int aSize = a->size();
758     int bSize = b->size();
759     int aOffset = a->offset;
760
761     // possible cases:
762
763     UString::BaseString* aBase = a->baseString();
764     if (bSize == 1 && aOffset + aSize == aBase->usedCapacity && aOffset + aSize < aBase->capacity && !aBase->isBufferReadOnly()) {
765         // b is a single character (common fast case)
766         ++aBase->usedCapacity;
767         a->data()[aSize] = b->data()[0];
768         return UString::Rep::create(a, 0, aSize + 1);
769     }
770
771     // a is empty
772     if (aSize == 0)
773         return b;
774     // b is empty
775     if (bSize == 0)
776         return a;
777
778     int bOffset = b->offset;
779     int length = aSize + bSize;
780
781     UString::BaseString* bBase = b->baseString();
782     if (aOffset + aSize == aBase->usedCapacity && aSize >= minShareSize && 4 * aSize >= bSize
783         && (-bOffset != bBase->usedPreCapacity || aSize >= bSize) && !aBase->isBufferReadOnly()) {
784         // - a reaches the end of its buffer so it qualifies for shared append
785         // - also, it's at least a quarter the length of b - appending to a much shorter
786         //   string does more harm than good
787         // - however, if b qualifies for prepend and is longer than a, we'd rather prepend
788         
789         UString x(a);
790         x.expandCapacity(newCapacityWithOverflowCheck(aOffset, length));
791         if (!a->data() || !x.data())
792             return 0;
793         copyChars(a->data() + aSize, b->data(), bSize);
794         PassRefPtr<UString::Rep> result = UString::Rep::create(a, 0, length);
795
796         a->checkConsistency();
797         b->checkConsistency();
798         result->checkConsistency();
799
800         return result;
801     }
802
803     if (-bOffset == bBase->usedPreCapacity && bSize >= minShareSize && 4 * bSize >= aSize && !bBase->isBufferReadOnly()) {
804         // - b reaches the beginning of its buffer so it qualifies for shared prepend
805         // - also, it's at least a quarter the length of a - prepending to a much shorter
806         //   string does more harm than good
807         UString y(b);
808         y.expandPreCapacity(-bOffset + aSize);
809         if (!b->data() || !y.data())
810             return 0;
811         copyChars(b->data() - aSize, a->data(), aSize);
812         PassRefPtr<UString::Rep> result = UString::Rep::create(b, -aSize, length);
813
814         a->checkConsistency();
815         b->checkConsistency();
816         result->checkConsistency();
817
818         return result;
819     }
820
821     // a does not qualify for append, and b does not qualify for prepend, gotta make a whole new string
822     size_t newCapacity = expandedSize(length, 0);
823     UChar* d;
824     if (!allocChars(newCapacity).getValue(d))
825         return 0;
826     copyChars(d, a->data(), aSize);
827     copyChars(d + aSize, b->data(), bSize);
828     PassRefPtr<UString::Rep> result = UString::Rep::create(d, length);
829     result->baseString()->capacity = newCapacity;
830
831     a->checkConsistency();
832     b->checkConsistency();
833     result->checkConsistency();
834
835     return result;
836 }
837
838 PassRefPtr<UString::Rep> concatenate(UString::Rep* rep, int i)
839 {
840     UChar buf[1 + sizeof(i) * 3];
841     UChar* end = buf + sizeof(buf) / sizeof(UChar);
842     UChar* p = end;
843   
844     if (i == 0)
845         *--p = '0';
846     else if (i == INT_MIN) {
847         char minBuf[1 + sizeof(i) * 3];
848         sprintf(minBuf, "%d", INT_MIN);
849         return concatenate(rep, minBuf);
850     } else {
851         bool negative = false;
852         if (i < 0) {
853             negative = true;
854             i = -i;
855         }
856         while (i) {
857             *--p = static_cast<unsigned short>((i % 10) + '0');
858             i /= 10;
859         }
860         if (negative)
861             *--p = '-';
862     }
863
864     return concatenate(rep, p, static_cast<int>(end - p));
865
866 }
867
868 PassRefPtr<UString::Rep> concatenate(UString::Rep* rep, double d)
869 {
870     // avoid ever printing -NaN, in JS conceptually there is only one NaN value
871     if (isnan(d))
872         return concatenate(rep, "NaN");
873
874     if (d == 0.0) // stringify -0 as 0
875         d = 0.0;
876
877     char buf[80];
878     int decimalPoint;
879     int sign;
880
881     char result[80];
882     WTF::dtoa(result, d, 0, &decimalPoint, &sign, NULL);
883     int length = static_cast<int>(strlen(result));
884   
885     int i = 0;
886     if (sign)
887         buf[i++] = '-';
888   
889     if (decimalPoint <= 0 && decimalPoint > -6) {
890         buf[i++] = '0';
891         buf[i++] = '.';
892         for (int j = decimalPoint; j < 0; j++)
893             buf[i++] = '0';
894         strcpy(buf + i, result);
895     } else if (decimalPoint <= 21 && decimalPoint > 0) {
896         if (length <= decimalPoint) {
897             strcpy(buf + i, result);
898             i += length;
899             for (int j = 0; j < decimalPoint - length; j++)
900                 buf[i++] = '0';
901             buf[i] = '\0';
902         } else {
903             strncpy(buf + i, result, decimalPoint);
904             i += decimalPoint;
905             buf[i++] = '.';
906             strcpy(buf + i, result + decimalPoint);
907         }
908     } else if (result[0] < '0' || result[0] > '9')
909         strcpy(buf + i, result);
910     else {
911         buf[i++] = result[0];
912         if (length > 1) {
913             buf[i++] = '.';
914             strcpy(buf + i, result + 1);
915             i += length - 1;
916         }
917         
918         buf[i++] = 'e';
919         buf[i++] = (decimalPoint >= 0) ? '+' : '-';
920         // decimalPoint can't be more than 3 digits decimal given the
921         // nature of float representation
922         int exponential = decimalPoint - 1;
923         if (exponential < 0)
924             exponential = -exponential;
925         if (exponential >= 100)
926             buf[i++] = static_cast<char>('0' + exponential / 100);
927         if (exponential >= 10)
928             buf[i++] = static_cast<char>('0' + (exponential % 100) / 10);
929         buf[i++] = static_cast<char>('0' + exponential % 10);
930         buf[i++] = '\0';
931     }
932     
933     return concatenate(rep, buf);
934 }
935
936 UString UString::from(int i)
937 {
938     UChar buf[1 + sizeof(i) * 3];
939     UChar* end = buf + sizeof(buf) / sizeof(UChar);
940     UChar* p = end;
941   
942     if (i == 0)
943         *--p = '0';
944     else if (i == INT_MIN) {
945         char minBuf[1 + sizeof(i) * 3];
946         sprintf(minBuf, "%d", INT_MIN);
947         return UString(minBuf);
948     } else {
949         bool negative = false;
950         if (i < 0) {
951             negative = true;
952             i = -i;
953         }
954         while (i) {
955             *--p = static_cast<unsigned short>((i % 10) + '0');
956             i /= 10;
957         }
958         if (negative)
959             *--p = '-';
960     }
961
962     return UString(p, static_cast<int>(end - p));
963 }
964
965 UString UString::from(long long i)
966 {
967     UChar buf[1 + sizeof(i) * 3];
968     UChar* end = buf + sizeof(buf) / sizeof(UChar);
969     UChar* p = end;
970
971     if (i == 0)
972         *--p = '0';
973     else if (i == std::numeric_limits<long long>::min()) {
974         char minBuf[1 + sizeof(i) * 3];
975 #if PLATFORM(WIN_OS)
976         snprintf(minBuf, sizeof(minBuf) - 1, "%I64d", std::numeric_limits<long long>::min());
977 #else
978         snprintf(minBuf, sizeof(minBuf) - 1, "%lld", std::numeric_limits<long long>::min());
979 #endif
980         return UString(minBuf);
981     } else {
982         bool negative = false;
983         if (i < 0) {
984             negative = true;
985             i = -i;
986         }
987         while (i) {
988             *--p = static_cast<unsigned short>((i % 10) + '0');
989             i /= 10;
990         }
991         if (negative)
992             *--p = '-';
993     }
994
995     return UString(p, static_cast<int>(end - p));
996 }
997
998 UString UString::from(unsigned int u)
999 {
1000     UChar buf[sizeof(u) * 3];
1001     UChar* end = buf + sizeof(buf) / sizeof(UChar);
1002     UChar* p = end;
1003     
1004     if (u == 0)
1005         *--p = '0';
1006     else {
1007         while (u) {
1008             *--p = static_cast<unsigned short>((u % 10) + '0');
1009             u /= 10;
1010         }
1011     }
1012     
1013     return UString(p, static_cast<int>(end - p));
1014 }
1015
1016 UString UString::from(long l)
1017 {
1018     UChar buf[1 + sizeof(l) * 3];
1019     UChar* end = buf + sizeof(buf) / sizeof(UChar);
1020     UChar* p = end;
1021
1022     if (l == 0)
1023         *--p = '0';
1024     else if (l == LONG_MIN) {
1025         char minBuf[1 + sizeof(l) * 3];
1026         sprintf(minBuf, "%ld", LONG_MIN);
1027         return UString(minBuf);
1028     } else {
1029         bool negative = false;
1030         if (l < 0) {
1031             negative = true;
1032             l = -l;
1033         }
1034         while (l) {
1035             *--p = static_cast<unsigned short>((l % 10) + '0');
1036             l /= 10;
1037         }
1038         if (negative)
1039             *--p = '-';
1040     }
1041
1042     return UString(p, static_cast<int>(end - p));
1043 }
1044
1045 UString UString::from(double d)
1046 {
1047     DtoaBuffer buffer;
1048     unsigned length;
1049     doubleToStringInJavaScriptFormat(d, buffer, &length);
1050     return UString(buffer, length);
1051 }
1052
1053 UString UString::spliceSubstringsWithSeparators(const Range* substringRanges, int rangeCount, const UString* separators, int separatorCount) const
1054 {
1055     m_rep->checkConsistency();
1056
1057     if (rangeCount == 1 && separatorCount == 0) {
1058         int thisSize = size();
1059         int position = substringRanges[0].position;
1060         int length = substringRanges[0].length;
1061         if (position <= 0 && length >= thisSize)
1062             return *this;
1063         return UString::Rep::create(m_rep, max(0, position), min(thisSize, length));
1064     }
1065
1066     int totalLength = 0;
1067     for (int i = 0; i < rangeCount; i++)
1068         totalLength += substringRanges[i].length;
1069     for (int i = 0; i < separatorCount; i++)
1070         totalLength += separators[i].size();
1071
1072     if (totalLength == 0)
1073         return "";
1074
1075     UChar* buffer;
1076     if (!allocChars(totalLength).getValue(buffer))
1077         return null();
1078
1079     int maxCount = max(rangeCount, separatorCount);
1080     int bufferPos = 0;
1081     for (int i = 0; i < maxCount; i++) {
1082         if (i < rangeCount) {
1083             copyChars(buffer + bufferPos, data() + substringRanges[i].position, substringRanges[i].length);
1084             bufferPos += substringRanges[i].length;
1085         }
1086         if (i < separatorCount) {
1087             copyChars(buffer + bufferPos, separators[i].data(), separators[i].size());
1088             bufferPos += separators[i].size();
1089         }
1090     }
1091
1092     return UString::Rep::create(buffer, totalLength);
1093 }
1094
1095 UString UString::replaceRange(int rangeStart, int rangeLength, const UString& replacement) const
1096 {
1097     m_rep->checkConsistency();
1098
1099     int replacementLength = replacement.size();
1100     int totalLength = size() - rangeLength + replacementLength;
1101     if (totalLength == 0)
1102         return "";
1103
1104     UChar* buffer;
1105     if (!allocChars(totalLength).getValue(buffer))
1106         return null();
1107
1108     copyChars(buffer, data(), rangeStart);
1109     copyChars(buffer + rangeStart, replacement.data(), replacementLength);
1110     int rangeEnd = rangeStart + rangeLength;
1111     copyChars(buffer + rangeStart + replacementLength, data() + rangeEnd, size() - rangeEnd);
1112
1113     return UString::Rep::create(buffer, totalLength);
1114 }
1115
1116
1117 UString& UString::append(const UString &t)
1118 {
1119     m_rep->checkConsistency();
1120     t.rep()->checkConsistency();
1121
1122     int thisSize = size();
1123     int thisOffset = m_rep->offset;
1124     int tSize = t.size();
1125     int length = thisSize + tSize;
1126     BaseString* base = m_rep->baseString();
1127
1128     // possible cases:
1129     if (thisSize == 0) {
1130         // this is empty
1131         *this = t;
1132     } else if (tSize == 0) {
1133         // t is empty
1134     } else if (m_rep == base && !base->isShared()) {
1135         // this is direct and has refcount of 1 (so we can just alter it directly)
1136         expandCapacity(newCapacityWithOverflowCheck(thisOffset, length));
1137         if (data()) {
1138             copyChars(m_rep->data() + thisSize, t.data(), tSize);
1139             m_rep->len = length;
1140             m_rep->_hash = 0;
1141         }
1142     } else if (thisOffset + thisSize == base->usedCapacity && thisSize >= minShareSize && !base->isBufferReadOnly()) {
1143         // this reaches the end of the buffer - extend it if it's long enough to append to
1144         expandCapacity(newCapacityWithOverflowCheck(thisOffset, length));
1145         if (data()) {
1146             copyChars(m_rep->data() + thisSize, t.data(), tSize);
1147             m_rep = Rep::create(m_rep, 0, length);
1148         }
1149     } else {
1150         // This is shared in some way that prevents us from modifying base, so we must make a whole new string.
1151         size_t newCapacity = expandedSize(length, 0);
1152         UChar* d;
1153         if (!allocChars(newCapacity).getValue(d))
1154             makeNull();
1155         else {
1156             copyChars(d, data(), thisSize);
1157             copyChars(d + thisSize, t.data(), tSize);
1158             m_rep = Rep::create(d, length);
1159             m_rep->baseString()->capacity = newCapacity;
1160         }
1161     }
1162
1163     m_rep->checkConsistency();
1164     t.rep()->checkConsistency();
1165
1166     return *this;
1167 }
1168
1169 UString& UString::append(const UChar* tData, int tSize)
1170 {
1171     m_rep = concatenate(m_rep.release(), tData, tSize);
1172     return *this;
1173 }
1174
1175 UString& UString::append(const char* t)
1176 {
1177     m_rep = concatenate(m_rep.release(), t);
1178     return *this;
1179 }
1180
1181 UString& UString::append(UChar c)
1182 {
1183     m_rep->checkConsistency();
1184
1185     int thisOffset = m_rep->offset;
1186     int length = size();
1187     BaseString* base = m_rep->baseString();
1188
1189     // possible cases:
1190     if (length == 0) {
1191         // this is empty - must make a new m_rep because we don't want to pollute the shared empty one 
1192         size_t newCapacity = expandedSize(1, 0);
1193         UChar* d;
1194         if (!allocChars(newCapacity).getValue(d))
1195             makeNull();
1196         else {
1197             d[0] = c;
1198             m_rep = Rep::create(d, 1);
1199             m_rep->baseString()->capacity = newCapacity;
1200         }
1201     } else if (m_rep == base && !base->isShared()) {
1202         // this is direct and has refcount of 1 (so we can just alter it directly)
1203         expandCapacity(newCapacityWithOverflowCheck(thisOffset, length, true));
1204         UChar* d = m_rep->data();
1205         if (d) {
1206             d[length] = c;
1207             m_rep->len = length + 1;
1208             m_rep->_hash = 0;
1209         }
1210     } else if (thisOffset + length == base->usedCapacity && length >= minShareSize && !base->isBufferReadOnly()) {
1211         // this reaches the end of the string - extend it and share
1212         expandCapacity(newCapacityWithOverflowCheck(thisOffset, length, true));
1213         UChar* d = m_rep->data();
1214         if (d) {
1215             d[length] = c;
1216             m_rep = Rep::create(m_rep, 0, length + 1);
1217         }
1218     } else {
1219         // This is shared in some way that prevents us from modifying base, so we must make a whole new string.
1220         size_t newCapacity = expandedSize(length + 1, 0);
1221         UChar* d;
1222         if (!allocChars(newCapacity).getValue(d))
1223             makeNull();
1224         else {
1225             copyChars(d, data(), length);
1226             d[length] = c;
1227             m_rep = Rep::create(d, length + 1);
1228             m_rep->baseString()->capacity = newCapacity;
1229         }
1230     }
1231
1232     m_rep->checkConsistency();
1233
1234     return *this;
1235 }
1236
1237 bool UString::getCString(CStringBuffer& buffer) const
1238 {
1239     int length = size();
1240     int neededSize = length + 1;
1241     buffer.resize(neededSize);
1242     char* buf = buffer.data();
1243
1244     UChar ored = 0;
1245     const UChar* p = data();
1246     char* q = buf;
1247     const UChar* limit = p + length;
1248     while (p != limit) {
1249         UChar c = p[0];
1250         ored |= c;
1251         *q = static_cast<char>(c);
1252         ++p;
1253         ++q;
1254     }
1255     *q = '\0';
1256
1257     return !(ored & 0xFF00);
1258 }
1259
1260 char* UString::ascii() const
1261 {
1262     int length = size();
1263     int neededSize = length + 1;
1264     delete[] statBuffer;
1265     statBuffer = new char[neededSize];
1266
1267     const UChar* p = data();
1268     char* q = statBuffer;
1269     const UChar* limit = p + length;
1270     while (p != limit) {
1271         *q = static_cast<char>(p[0]);
1272         ++p;
1273         ++q;
1274     }
1275     *q = '\0';
1276
1277     return statBuffer;
1278 }
1279
1280 UString& UString::operator=(const char* c)
1281 {
1282     if (!c) {
1283         m_rep = &Rep::null();
1284         return *this;
1285     }
1286
1287     if (!c[0]) {
1288         m_rep = &Rep::empty();
1289         return *this;
1290     }
1291
1292     int l = static_cast<int>(strlen(c));
1293     UChar* d;
1294     BaseString* base = m_rep->baseString();
1295     if (!base->isShared() && l <= base->capacity && m_rep == base && m_rep->offset == 0 && base->preCapacity == 0) {
1296         d = base->buf;
1297         m_rep->_hash = 0;
1298         m_rep->len = l;
1299     } else {
1300         if (!allocChars(l).getValue(d)) {
1301             makeNull();
1302             return *this;
1303         }
1304         m_rep = Rep::create(d, l);
1305     }
1306     for (int i = 0; i < l; i++)
1307         d[i] = static_cast<unsigned char>(c[i]); // use unsigned char to zero-extend instead of sign-extend
1308
1309     return *this;
1310 }
1311
1312 bool UString::is8Bit() const
1313 {
1314     const UChar* u = data();
1315     const UChar* limit = u + size();
1316     while (u < limit) {
1317         if (u[0] > 0xFF)
1318             return false;
1319         ++u;
1320     }
1321
1322     return true;
1323 }
1324
1325 UChar UString::operator[](int pos) const
1326 {
1327     if (pos >= size())
1328         return '\0';
1329     return data()[pos];
1330 }
1331
1332 double UString::toDouble(bool tolerateTrailingJunk, bool tolerateEmptyString) const
1333 {
1334     if (size() == 1) {
1335         UChar c = data()[0];
1336         if (isASCIIDigit(c))
1337             return c - '0';
1338         if (isASCIISpace(c) && tolerateEmptyString)
1339             return 0;
1340         return NaN;
1341     }
1342
1343     // FIXME: If tolerateTrailingJunk is true, then we want to tolerate non-8-bit junk
1344     // after the number, so this is too strict a check.
1345     CStringBuffer s;
1346     if (!getCString(s))
1347         return NaN;
1348     const char* c = s.data();
1349
1350     // skip leading white space
1351     while (isASCIISpace(*c))
1352         c++;
1353
1354     // empty string ?
1355     if (*c == '\0')
1356         return tolerateEmptyString ? 0.0 : NaN;
1357
1358     double d;
1359
1360     // hex number ?
1361     if (*c == '0' && (*(c + 1) == 'x' || *(c + 1) == 'X')) {
1362         const char* firstDigitPosition = c + 2;
1363         c++;
1364         d = 0.0;
1365         while (*(++c)) {
1366             if (*c >= '0' && *c <= '9')
1367                 d = d * 16.0 + *c - '0';
1368             else if ((*c >= 'A' && *c <= 'F') || (*c >= 'a' && *c <= 'f'))
1369                 d = d * 16.0 + (*c & 0xdf) - 'A' + 10.0;
1370             else
1371                 break;
1372         }
1373
1374         if (d >= mantissaOverflowLowerBound)
1375             d = parseIntOverflow(firstDigitPosition, c - firstDigitPosition, 16);
1376     } else {
1377         // regular number ?
1378         char* end;
1379         d = WTF::strtod(c, &end);
1380         if ((d != 0.0 || end != c) && d != Inf && d != -Inf) {
1381             c = end;
1382         } else {
1383             double sign = 1.0;
1384
1385             if (*c == '+')
1386                 c++;
1387             else if (*c == '-') {
1388                 sign = -1.0;
1389                 c++;
1390             }
1391
1392             // We used strtod() to do the conversion. However, strtod() handles
1393             // infinite values slightly differently than JavaScript in that it
1394             // converts the string "inf" with any capitalization to infinity,
1395             // whereas the ECMA spec requires that it be converted to NaN.
1396
1397             if (c[0] == 'I' && c[1] == 'n' && c[2] == 'f' && c[3] == 'i' && c[4] == 'n' && c[5] == 'i' && c[6] == 't' && c[7] == 'y') {
1398                 d = sign * Inf;
1399                 c += 8;
1400             } else if ((d == Inf || d == -Inf) && *c != 'I' && *c != 'i')
1401                 c = end;
1402             else
1403                 return NaN;
1404         }
1405     }
1406
1407     // allow trailing white space
1408     while (isASCIISpace(*c))
1409         c++;
1410     // don't allow anything after - unless tolerant=true
1411     if (!tolerateTrailingJunk && *c != '\0')
1412         d = NaN;
1413
1414     return d;
1415 }
1416
1417 double UString::toDouble(bool tolerateTrailingJunk) const
1418 {
1419     return toDouble(tolerateTrailingJunk, true);
1420 }
1421
1422 double UString::toDouble() const
1423 {
1424     return toDouble(false, true);
1425 }
1426
1427 uint32_t UString::toUInt32(bool* ok) const
1428 {
1429     double d = toDouble();
1430     bool b = true;
1431
1432     if (d != static_cast<uint32_t>(d)) {
1433         b = false;
1434         d = 0;
1435     }
1436
1437     if (ok)
1438         *ok = b;
1439
1440     return static_cast<uint32_t>(d);
1441 }
1442
1443 uint32_t UString::toUInt32(bool* ok, bool tolerateEmptyString) const
1444 {
1445     double d = toDouble(false, tolerateEmptyString);
1446     bool b = true;
1447
1448     if (d != static_cast<uint32_t>(d)) {
1449         b = false;
1450         d = 0;
1451     }
1452
1453     if (ok)
1454         *ok = b;
1455
1456     return static_cast<uint32_t>(d);
1457 }
1458
1459 uint32_t UString::toStrictUInt32(bool* ok) const
1460 {
1461     if (ok)
1462         *ok = false;
1463
1464     // Empty string is not OK.
1465     int len = m_rep->len;
1466     if (len == 0)
1467         return 0;
1468     const UChar* p = m_rep->data();
1469     unsigned short c = p[0];
1470
1471     // If the first digit is 0, only 0 itself is OK.
1472     if (c == '0') {
1473         if (len == 1 && ok)
1474             *ok = true;
1475         return 0;
1476     }
1477
1478     // Convert to UInt32, checking for overflow.
1479     uint32_t i = 0;
1480     while (1) {
1481         // Process character, turning it into a digit.
1482         if (c < '0' || c > '9')
1483             return 0;
1484         const unsigned d = c - '0';
1485
1486         // Multiply by 10, checking for overflow out of 32 bits.
1487         if (i > 0xFFFFFFFFU / 10)
1488             return 0;
1489         i *= 10;
1490
1491         // Add in the digit, checking for overflow out of 32 bits.
1492         const unsigned max = 0xFFFFFFFFU - d;
1493         if (i > max)
1494             return 0;
1495         i += d;
1496
1497         // Handle end of string.
1498         if (--len == 0) {
1499             if (ok)
1500                 *ok = true;
1501             return i;
1502         }
1503
1504         // Get next character.
1505         c = *(++p);
1506     }
1507 }
1508
1509 int UString::find(const UString& f, int pos) const
1510 {
1511     int fsz = f.size();
1512
1513     if (pos < 0)
1514         pos = 0;
1515
1516     if (fsz == 1) {
1517         UChar ch = f[0];
1518         const UChar* end = data() + size();
1519         for (const UChar* c = data() + pos; c < end; c++) {
1520             if (*c == ch)
1521                 return static_cast<int>(c - data());
1522         }
1523         return -1;
1524     }
1525
1526     int sz = size();
1527     if (sz < fsz)
1528         return -1;
1529     if (fsz == 0)
1530         return pos;
1531     const UChar* end = data() + sz - fsz;
1532     int fsizeminusone = (fsz - 1) * sizeof(UChar);
1533     const UChar* fdata = f.data();
1534     unsigned short fchar = fdata[0];
1535     ++fdata;
1536     for (const UChar* c = data() + pos; c <= end; c++) {
1537         if (c[0] == fchar && !memcmp(c + 1, fdata, fsizeminusone))
1538             return static_cast<int>(c - data());
1539     }
1540
1541     return -1;
1542 }
1543
1544 int UString::find(UChar ch, int pos) const
1545 {
1546     if (pos < 0)
1547         pos = 0;
1548     const UChar* end = data() + size();
1549     for (const UChar* c = data() + pos; c < end; c++) {
1550         if (*c == ch)
1551             return static_cast<int>(c - data());
1552     }
1553     
1554     return -1;
1555 }
1556
1557 int UString::rfind(const UString& f, int pos) const
1558 {
1559     int sz = size();
1560     int fsz = f.size();
1561     if (sz < fsz)
1562         return -1;
1563     if (pos < 0)
1564         pos = 0;
1565     if (pos > sz - fsz)
1566         pos = sz - fsz;
1567     if (fsz == 0)
1568         return pos;
1569     int fsizeminusone = (fsz - 1) * sizeof(UChar);
1570     const UChar* fdata = f.data();
1571     for (const UChar* c = data() + pos; c >= data(); c--) {
1572         if (*c == *fdata && !memcmp(c + 1, fdata + 1, fsizeminusone))
1573             return static_cast<int>(c - data());
1574     }
1575
1576     return -1;
1577 }
1578
1579 int UString::rfind(UChar ch, int pos) const
1580 {
1581     if (isEmpty())
1582         return -1;
1583     if (pos + 1 >= size())
1584         pos = size() - 1;
1585     for (const UChar* c = data() + pos; c >= data(); c--) {
1586         if (*c == ch)
1587             return static_cast<int>(c - data());
1588     }
1589
1590     return -1;
1591 }
1592
1593 UString UString::substr(int pos, int len) const
1594 {
1595     int s = size();
1596
1597     if (pos < 0)
1598         pos = 0;
1599     else if (pos >= s)
1600         pos = s;
1601     if (len < 0)
1602         len = s;
1603     if (pos + len >= s)
1604         len = s - pos;
1605
1606     if (pos == 0 && len == s)
1607         return *this;
1608
1609     return UString(Rep::create(m_rep, pos, len));
1610 }
1611
1612 bool operator==(const UString& s1, const char *s2)
1613 {
1614     if (s2 == 0)
1615         return s1.isEmpty();
1616
1617     const UChar* u = s1.data();
1618     const UChar* uend = u + s1.size();
1619     while (u != uend && *s2) {
1620         if (u[0] != (unsigned char)*s2)
1621             return false;
1622         s2++;
1623         u++;
1624     }
1625
1626     return u == uend && *s2 == 0;
1627 }
1628
1629 bool operator<(const UString& s1, const UString& s2)
1630 {
1631     const int l1 = s1.size();
1632     const int l2 = s2.size();
1633     const int lmin = l1 < l2 ? l1 : l2;
1634     const UChar* c1 = s1.data();
1635     const UChar* c2 = s2.data();
1636     int l = 0;
1637     while (l < lmin && *c1 == *c2) {
1638         c1++;
1639         c2++;
1640         l++;
1641     }
1642     if (l < lmin)
1643         return (c1[0] < c2[0]);
1644
1645     return (l1 < l2);
1646 }
1647
1648 bool operator>(const UString& s1, const UString& s2)
1649 {
1650     const int l1 = s1.size();
1651     const int l2 = s2.size();
1652     const int lmin = l1 < l2 ? l1 : l2;
1653     const UChar* c1 = s1.data();
1654     const UChar* c2 = s2.data();
1655     int l = 0;
1656     while (l < lmin && *c1 == *c2) {
1657         c1++;
1658         c2++;
1659         l++;
1660     }
1661     if (l < lmin)
1662         return (c1[0] > c2[0]);
1663
1664     return (l1 > l2);
1665 }
1666
1667 int compare(const UString& s1, const UString& s2)
1668 {
1669     const int l1 = s1.size();
1670     const int l2 = s2.size();
1671     const int lmin = l1 < l2 ? l1 : l2;
1672     const UChar* c1 = s1.data();
1673     const UChar* c2 = s2.data();
1674     int l = 0;
1675     while (l < lmin && *c1 == *c2) {
1676         c1++;
1677         c2++;
1678         l++;
1679     }
1680
1681     if (l < lmin)
1682         return (c1[0] > c2[0]) ? 1 : -1;
1683
1684     if (l1 == l2)
1685         return 0;
1686
1687     return (l1 > l2) ? 1 : -1;
1688 }
1689
1690 bool equal(const UString::Rep* r, const UString::Rep* b)
1691 {
1692     int length = r->len;
1693     if (length != b->len)
1694         return false;
1695     const UChar* d = r->data();
1696     const UChar* s = b->data();
1697     for (int i = 0; i != length; ++i) {
1698         if (d[i] != s[i])
1699             return false;
1700     }
1701     return true;
1702 }
1703
1704 CString UString::UTF8String(bool strict) const
1705 {
1706     // Allocate a buffer big enough to hold all the characters.
1707     const int length = size();
1708     Vector<char, 1024> buffer(length * 3);
1709
1710     // Convert to runs of 8-bit characters.
1711     char* p = buffer.data();
1712     const UChar* d = reinterpret_cast<const UChar*>(&data()[0]);
1713     ConversionResult result = convertUTF16ToUTF8(&d, d + length, &p, p + buffer.size(), strict);
1714     if (result != conversionOK)
1715         return CString();
1716
1717     return CString(buffer.data(), p - buffer.data());
1718 }
1719
1720 // For use in error handling code paths -- having this not be inlined helps avoid PIC branches to fetch the global on Mac OS X.
1721 NEVER_INLINE void UString::makeNull()
1722 {
1723     m_rep = &Rep::null();
1724 }
1725
1726 // For use in error handling code paths -- having this not be inlined helps avoid PIC branches to fetch the global on Mac OS X.
1727 NEVER_INLINE UString::Rep* UString::nullRep()
1728 {
1729     return &Rep::null();
1730 }
1731
1732 } // namespace JSC