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