Reviewed by Eric Seidel.
[WebKit-https.git] / JavaScriptCore / kjs / ustring.cpp
1 // -*- c-basic-offset: 2 -*-
2 /*
3  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
4  *  Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
5  *  Copyright (C) 2007 Cameron Zwarich (cwzwarich@uwaterloo.ca)
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 "JSLock.h"
28 #include "collector.h"
29 #include "dtoa.h"
30 #include "function.h"
31 #include "identifier.h"
32 #include "operations.h"
33 #include <ctype.h>
34 #include <float.h>
35 #include <limits.h>
36 #include <math.h>
37 #include <stdio.h>
38 #include <stdlib.h>
39 #include <wtf/Assertions.h>
40 #include <wtf/ASCIICType.h>
41 #include <wtf/MathExtras.h>
42 #include <wtf/Vector.h>
43 #include <wtf/unicode/UTF8.h>
44
45 #if HAVE(STRING_H)
46 #include <string.h>
47 #endif
48 #if HAVE(STRINGS_H)
49 #include <strings.h>
50 #endif
51
52 using namespace WTF;
53 using namespace WTF::Unicode;
54 using namespace std;
55
56 namespace KJS {
57
58 extern const double NaN;
59 extern const double Inf;
60
61 static inline const size_t overflowIndicator() { return std::numeric_limits<size_t>::max(); }
62 static inline const size_t maxUChars() { return std::numeric_limits<size_t>::max() / sizeof(UChar); }
63
64 static inline UChar* allocChars(size_t length)
65 {
66     ASSERT(length);
67     if (length > maxUChars())
68         return 0;
69     return static_cast<UChar*>(fastMalloc(sizeof(UChar) * length));
70 }
71
72 static inline UChar* reallocChars(UChar* buffer, size_t length)
73 {
74     ASSERT(length);
75     if (length > maxUChars())
76         return 0;
77     return static_cast<UChar*>(fastRealloc(buffer, sizeof(UChar) * length));
78 }
79
80 // we'd rather not do shared substring append for small strings, since
81 // this runs too much risk of a tiny initial string holding down a
82 // huge buffer. This is also tuned to match the extra cost size, so we
83 // don't ever share a buffer that wouldn't be over the extra cost
84 // threshold already.
85 // FIXME: this should be size_t but that would cause warnings until we
86 // fix UString sizes to be size_t instad of int
87 static const int minShareSize = Collector::minExtraCostSize / sizeof(UChar);
88
89 COMPILE_ASSERT(sizeof(UChar) == 2, uchar_is_2_bytes)
90
91 CString::CString(const char *c)
92 {
93   length = strlen(c);
94   data = new char[length+1];
95   memcpy(data, c, length + 1);
96 }
97
98 CString::CString(const char *c, size_t len)
99 {
100   length = len;
101   data = new char[len+1];
102   memcpy(data, c, len);
103   data[len] = 0;
104 }
105
106 CString::CString(const CString &b)
107 {
108   length = b.length;
109   if (b.data) {
110     data = new char[length+1];
111     memcpy(data, b.data, length + 1);
112   }
113   else
114     data = 0;
115 }
116
117 CString::~CString()
118 {
119   delete [] data;
120 }
121
122 CString &CString::append(const CString &t)
123 {
124   char *n;
125   n = new char[length+t.length+1];
126   if (length)
127     memcpy(n, data, length);
128   if (t.length)
129     memcpy(n+length, t.data, t.length);
130   length += t.length;
131   n[length] = 0;
132
133   delete [] data;
134   data = n;
135
136   return *this;
137 }
138
139 CString &CString::operator=(const char *c)
140 {
141   if (data)
142     delete [] data;
143   length = strlen(c);
144   data = new char[length+1];
145   memcpy(data, c, length + 1);
146
147   return *this;
148 }
149
150 CString &CString::operator=(const CString &str)
151 {
152   if (this == &str)
153     return *this;
154
155   if (data)
156     delete [] data;
157   length = str.length;
158   if (str.data) {
159     data = new char[length + 1];
160     memcpy(data, str.data, length + 1);
161   }
162   else
163     data = 0;
164
165   return *this;
166 }
167
168 bool operator==(const CString& c1, const CString& c2)
169 {
170   size_t len = c1.size();
171   return len == c2.size() && (len == 0 || memcmp(c1.c_str(), c2.c_str(), len) == 0);
172 }
173
174 // Hack here to avoid a global with a constructor; point to an unsigned short instead of a UChar.
175 static unsigned short almostUChar;
176 UString::Rep UString::Rep::null = { 0, 0, 1, 0, 0, &UString::Rep::null, 0, 0, 0, 0, 0 };
177 UString::Rep UString::Rep::empty = { 0, 0, 1, 0, 0, &UString::Rep::empty, reinterpret_cast<UChar*>(&almostUChar), 0, 0, 0, 0 };
178 const int normalStatBufferSize = 4096;
179 static char *statBuffer = 0; // FIXME: This buffer is never deallocated.
180 static int statBufferSize = 0;
181
182 PassRefPtr<UString::Rep> UString::Rep::createCopying(const UChar *d, int l)
183 {
184   ASSERT(JSLock::lockCount() > 0);
185
186   int sizeInBytes = l * sizeof(UChar);
187   UChar *copyD = static_cast<UChar *>(fastMalloc(sizeInBytes));
188   memcpy(copyD, d, sizeInBytes);
189
190   return create(copyD, l);
191 }
192
193 PassRefPtr<UString::Rep> UString::Rep::create(UChar *d, int l)
194 {
195   ASSERT(JSLock::lockCount() > 0);
196
197   Rep* r = new Rep;
198   r->offset = 0;
199   r->len = l;
200   r->rc = 1;
201   r->_hash = 0;
202   r->isIdentifier = 0;
203   r->baseString = r;
204   r->buf = d;
205   r->usedCapacity = l;
206   r->capacity = l;
207   r->usedPreCapacity = 0;
208   r->preCapacity = 0;
209
210   // steal the single reference this Rep was created with
211   return adoptRef(r);
212 }
213
214 PassRefPtr<UString::Rep> UString::Rep::create(PassRefPtr<Rep> base, int offset, int length)
215 {
216   ASSERT(JSLock::lockCount() > 0);
217   ASSERT(base);
218
219   int baseOffset = base->offset;
220
221   base = base->baseString;
222
223   ASSERT(-(offset + baseOffset) <= base->usedPreCapacity);
224   ASSERT(offset + baseOffset + length <= base->usedCapacity);
225
226   Rep *r = new Rep;
227   r->offset = baseOffset + offset;
228   r->len = length;
229   r->rc = 1;
230   r->_hash = 0;
231   r->isIdentifier = 0;
232   r->baseString = base.releaseRef();
233   r->buf = 0;
234   r->usedCapacity = 0;
235   r->capacity = 0;
236   r->usedPreCapacity = 0;
237   r->preCapacity = 0;
238
239   // steal the single reference this Rep was created with
240   return adoptRef(r);
241 }
242
243 void UString::Rep::destroy()
244 {
245   ASSERT(JSLock::lockCount() > 0);
246
247   if (isIdentifier)
248     Identifier::remove(this);
249   if (baseString != this) {
250     baseString->deref();
251   } else {
252     fastFree(buf);
253   }
254   delete this;
255 }
256
257 // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
258 // or anything like that.
259 const unsigned PHI = 0x9e3779b9U;
260
261 // Paul Hsieh's SuperFastHash
262 // http://www.azillionmonkeys.com/qed/hash.html
263 unsigned UString::Rep::computeHash(const UChar *s, int len)
264 {
265   unsigned l = len;
266   uint32_t hash = PHI;
267   uint32_t tmp;
268
269   int rem = l & 1;
270   l >>= 1;
271
272   // Main loop
273   for (; l > 0; l--) {
274     hash += s[0].uc;
275     tmp = (s[1].uc << 11) ^ hash;
276     hash = (hash << 16) ^ tmp;
277     s += 2;
278     hash += hash >> 11;
279   }
280
281   // Handle end case
282   if (rem) {
283     hash += s[0].uc;
284     hash ^= hash << 11;
285     hash += hash >> 17;
286   }
287
288   // Force "avalanching" of final 127 bits
289   hash ^= hash << 3;
290   hash += hash >> 5;
291   hash ^= hash << 2;
292   hash += hash >> 15;
293   hash ^= hash << 10;
294
295   // this avoids ever returning a hash code of 0, since that is used to
296   // signal "hash not computed yet", using a value that is likely to be
297   // effectively the same as 0 when the low bits are masked
298   if (hash == 0)
299     hash = 0x80000000;
300
301   return hash;
302 }
303
304 // Paul Hsieh's SuperFastHash
305 // http://www.azillionmonkeys.com/qed/hash.html
306 unsigned UString::Rep::computeHash(const char *s)
307 {
308   // This hash is designed to work on 16-bit chunks at a time. But since the normal case
309   // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
310   // were 16-bit chunks, which should give matching results
311
312   uint32_t hash = PHI;
313   uint32_t tmp;
314   size_t l = strlen(s);
315   
316   size_t rem = l & 1;
317   l >>= 1;
318
319   // Main loop
320   for (; l > 0; l--) {
321     hash += (unsigned char)s[0];
322     tmp = ((unsigned char)s[1] << 11) ^ hash;
323     hash = (hash << 16) ^ tmp;
324     s += 2;
325     hash += hash >> 11;
326   }
327
328   // Handle end case
329   if (rem) {
330     hash += (unsigned char)s[0];
331     hash ^= hash << 11;
332     hash += hash >> 17;
333   }
334
335   // Force "avalanching" of final 127 bits
336   hash ^= hash << 3;
337   hash += hash >> 5;
338   hash ^= hash << 2;
339   hash += hash >> 15;
340   hash ^= hash << 10;
341   
342   // this avoids ever returning a hash code of 0, since that is used to
343   // signal "hash not computed yet", using a value that is likely to be
344   // effectively the same as 0 when the low bits are masked
345   if (hash == 0)
346     hash = 0x80000000;
347
348   return hash;
349 }
350
351 // put these early so they can be inlined
352 inline size_t UString::expandedSize(size_t size, size_t otherSize) const
353 {
354     // Do the size calculation in two parts, returning overflowIndicator if
355     // we overflow the maximum value that we can handle.
356
357     if (size > maxUChars())
358         return overflowIndicator();
359
360     size_t expandedSize = ((size + 10) / 10 * 11) + 1;
361     if (maxUChars() - expandedSize < otherSize)
362         return overflowIndicator();
363
364     return expandedSize + otherSize;
365 }
366
367 inline int UString::usedCapacity() const
368 {
369   return m_rep->baseString->usedCapacity;
370 }
371
372 inline int UString::usedPreCapacity() const
373 {
374   return m_rep->baseString->usedPreCapacity;
375 }
376
377 void UString::expandCapacity(int requiredLength)
378 {
379   Rep* r = m_rep->baseString;
380
381   if (requiredLength > r->capacity) {
382     size_t newCapacity = expandedSize(requiredLength, r->preCapacity);
383     UChar* oldBuf = r->buf;
384     r->buf = reallocChars(r->buf, newCapacity);
385     if (!r->buf) {
386         r->buf = oldBuf;
387         m_rep = &Rep::null;
388         return;
389     }
390     r->capacity = newCapacity - r->preCapacity;
391   }
392   if (requiredLength > r->usedCapacity) {
393     r->usedCapacity = requiredLength;
394   }
395 }
396
397 void UString::expandPreCapacity(int requiredPreCap)
398 {
399   Rep* r = m_rep->baseString;
400
401   if (requiredPreCap > r->preCapacity) {
402     size_t newCapacity = expandedSize(requiredPreCap, r->capacity);
403     int delta = newCapacity - r->capacity - r->preCapacity;
404
405     UChar* newBuf = allocChars(newCapacity);
406     if (!newBuf) {
407         m_rep = &Rep::null;
408         return;
409     }
410     memcpy(newBuf + delta, r->buf, (r->capacity + r->preCapacity) * sizeof(UChar));
411     fastFree(r->buf);
412     r->buf = newBuf;
413
414     r->preCapacity = newCapacity - r->capacity;
415   }
416   if (requiredPreCap > r->usedPreCapacity) {
417     r->usedPreCapacity = requiredPreCap;
418   }
419 }
420
421 UString::UString(const char *c)
422 {
423   if (!c) {
424     m_rep = &Rep::null;
425     return;
426   }
427
428   if (!c[0]) {
429     m_rep = &Rep::empty;
430     return;
431   }
432
433   size_t length = strlen(c);
434   UChar *d = allocChars(length);
435   if (!d)
436       m_rep = &Rep::null;
437   else {
438       for (size_t i = 0; i < length; i++)
439           d[i].uc = c[i];
440       m_rep = Rep::create(d, static_cast<int>(length));
441   }
442 }
443
444 UString::UString(const UChar *c, int length)
445 {
446   if (length == 0) 
447     m_rep = &Rep::empty;
448   else
449     m_rep = Rep::createCopying(c, length);
450 }
451
452 UString::UString(UChar *c, int length, bool copy)
453 {
454   if (length == 0)
455     m_rep = &Rep::empty;
456   else if (copy)
457     m_rep = Rep::createCopying(c, length);
458   else
459     m_rep = Rep::create(c, length);
460 }
461
462 UString::UString(const UString &a, const UString &b)
463 {
464   int aSize = a.size();
465   int aOffset = a.m_rep->offset;
466   int bSize = b.size();
467   int bOffset = b.m_rep->offset;
468   int length = aSize + bSize;
469
470   // possible cases:
471  
472   if (aSize == 0) {
473     // a is empty
474     m_rep = b.m_rep;
475   } else if (bSize == 0) {
476     // b is empty
477     m_rep = a.m_rep;
478   } else if (aOffset + aSize == a.usedCapacity() && aSize >= minShareSize && 4 * aSize >= bSize &&
479              (-bOffset != b.usedPreCapacity() || aSize >= bSize)) {
480     // - a reaches the end of its buffer so it qualifies for shared append
481     // - also, it's at least a quarter the length of b - appending to a much shorter
482     //   string does more harm than good
483     // - however, if b qualifies for prepend and is longer than a, we'd rather prepend
484     UString x(a);
485     x.expandCapacity(aOffset + length);
486     if (a.data() && x.data()) {
487         memcpy(const_cast<UChar *>(a.data() + aSize), b.data(), bSize * sizeof(UChar));
488         m_rep = Rep::create(a.m_rep, 0, length);
489     } else
490         m_rep = &Rep::null;
491   } else if (-bOffset == b.usedPreCapacity() && bSize >= minShareSize && 4 * bSize >= aSize) {
492     // - b reaches the beginning of its buffer so it qualifies for shared prepend
493     // - also, it's at least a quarter the length of a - prepending to a much shorter
494     //   string does more harm than good
495     UString y(b);
496     y.expandPreCapacity(-bOffset + aSize);
497     if (b.data() && y.data()) {
498         memcpy(const_cast<UChar *>(b.data() - aSize), a.data(), aSize * sizeof(UChar));
499         m_rep = Rep::create(b.m_rep, -aSize, length);
500     } else
501         m_rep = &Rep::null;
502   } else {
503     // a does not qualify for append, and b does not qualify for prepend, gotta make a whole new string
504     size_t newCapacity = expandedSize(length, 0);
505     UChar* d = allocChars(newCapacity);
506     if (!d)
507         m_rep = &Rep::null;
508     else {
509         memcpy(d, a.data(), aSize * sizeof(UChar));
510         memcpy(d + aSize, b.data(), bSize * sizeof(UChar));
511         m_rep = Rep::create(d, length);
512         m_rep->capacity = newCapacity;
513     }
514   }
515 }
516
517 const UString& UString::null()
518 {
519   static UString* n = new UString;
520   return *n;
521 }
522
523 UString UString::from(int i)
524 {
525   UChar buf[1 + sizeof(i) * 3];
526   UChar *end = buf + sizeof(buf) / sizeof(UChar);
527   UChar *p = end;
528   
529   if (i == 0) {
530     *--p = '0';
531   } else if (i == INT_MIN) {
532     char minBuf[1 + sizeof(i) * 3];
533     sprintf(minBuf, "%d", INT_MIN);
534     return UString(minBuf);
535   } else {
536     bool negative = false;
537     if (i < 0) {
538       negative = true;
539       i = -i;
540     }
541     while (i) {
542       *--p = (unsigned short)((i % 10) + '0');
543       i /= 10;
544     }
545     if (negative) {
546       *--p = '-';
547     }
548   }
549   
550   return UString(p, static_cast<int>(end - p));
551 }
552
553 UString UString::from(unsigned int u)
554 {
555   UChar buf[sizeof(u) * 3];
556   UChar *end = buf + sizeof(buf) / sizeof(UChar);
557   UChar *p = end;
558   
559   if (u == 0) {
560     *--p = '0';
561   } else {
562     while (u) {
563       *--p = (unsigned short)((u % 10) + '0');
564       u /= 10;
565     }
566   }
567   
568   return UString(p, static_cast<int>(end - p));
569 }
570
571 UString UString::from(long l)
572 {
573   UChar buf[1 + sizeof(l) * 3];
574   UChar *end = buf + sizeof(buf) / sizeof(UChar);
575   UChar *p = end;
576   
577   if (l == 0) {
578     *--p = '0';
579   } else if (l == LONG_MIN) {
580     char minBuf[1 + sizeof(l) * 3];
581     sprintf(minBuf, "%ld", LONG_MIN);
582     return UString(minBuf);
583   } else {
584     bool negative = false;
585     if (l < 0) {
586       negative = true;
587       l = -l;
588     }
589     while (l) {
590       *--p = (unsigned short)((l % 10) + '0');
591       l /= 10;
592     }
593     if (negative) {
594       *--p = '-';
595     }
596   }
597   
598   return UString(p, static_cast<int>(end - p));
599 }
600
601 UString UString::from(double d)
602 {
603   // avoid ever printing -NaN, in JS conceptually there is only one NaN value
604   if (isnan(d))
605     return "NaN";
606
607   char buf[80];
608   int decimalPoint;
609   int sign;
610   
611   char *result = kjs_dtoa(d, 0, 0, &decimalPoint, &sign, NULL);
612   int length = static_cast<int>(strlen(result));
613   
614   int i = 0;
615   if (sign) {
616     buf[i++] = '-';
617   }
618   
619   if (decimalPoint <= 0 && decimalPoint > -6) {
620     buf[i++] = '0';
621     buf[i++] = '.';
622     for (int j = decimalPoint; j < 0; j++) {
623       buf[i++] = '0';
624     }
625     strcpy(buf + i, result);
626   } else if (decimalPoint <= 21 && decimalPoint > 0) {
627     if (length <= decimalPoint) {
628       strcpy(buf + i, result);
629       i += length;
630       for (int j = 0; j < decimalPoint - length; j++) {
631         buf[i++] = '0';
632       }
633       buf[i] = '\0';
634     } else {
635       strncpy(buf + i, result, decimalPoint);
636       i += decimalPoint;
637       buf[i++] = '.';
638       strcpy(buf + i, result + decimalPoint);
639     }
640   } else if (result[0] < '0' || result[0] > '9') {
641     strcpy(buf + i, result);
642   } else {
643     buf[i++] = result[0];
644     if (length > 1) {
645       buf[i++] = '.';
646       strcpy(buf + i, result + 1);
647       i += length - 1;
648     }
649     
650     buf[i++] = 'e';
651     buf[i++] = (decimalPoint >= 0) ? '+' : '-';
652     // decimalPoint can't be more than 3 digits decimal given the
653     // nature of float representation
654     int exponential = decimalPoint - 1;
655     if (exponential < 0)
656       exponential = -exponential;
657     if (exponential >= 100)
658       buf[i++] = static_cast<char>('0' + exponential / 100);
659     if (exponential >= 10)
660       buf[i++] = static_cast<char>('0' + (exponential % 100) / 10);
661     buf[i++] = static_cast<char>('0' + exponential % 10);
662     buf[i++] = '\0';
663   }
664   
665   kjs_freedtoa(result);
666   
667   return UString(buf);
668 }
669
670 UString UString::spliceSubstringsWithSeparators(const Range* substringRanges, int rangeCount, const UString* separators, int separatorCount) const
671 {
672   if (rangeCount == 1 && separatorCount == 0) {
673     int thisSize = size();
674     int position = substringRanges[0].position;
675     int length = substringRanges[0].length;
676     if (position <= 0 && length >= thisSize)
677       return *this;
678     return UString::Rep::create(m_rep, max(0, position), min(thisSize, length));
679   }
680
681   int totalLength = 0;
682   for (int i = 0; i < rangeCount; i++)
683     totalLength += substringRanges[i].length;
684   for (int i = 0; i < separatorCount; i++)
685     totalLength += separators[i].size();
686
687   if (totalLength == 0)
688     return "";
689
690   UChar* buffer = allocChars(totalLength);
691   if (!buffer)
692       return null();
693
694   int maxCount = max(rangeCount, separatorCount);
695   int bufferPos = 0;
696   for (int i = 0; i < maxCount; i++) {
697     if (i < rangeCount) {
698       memcpy(buffer + bufferPos, data() + substringRanges[i].position, substringRanges[i].length * sizeof(UChar));
699       bufferPos += substringRanges[i].length;
700     }
701     if (i < separatorCount) {
702       memcpy(buffer + bufferPos, separators[i].data(), separators[i].size() * sizeof(UChar));
703       bufferPos += separators[i].size();
704     }
705   }
706
707   return UString::Rep::create(buffer, totalLength);
708 }
709
710 UString &UString::append(const UString &t)
711 {
712   int thisSize = size();
713   int thisOffset = m_rep->offset;
714   int tSize = t.size();
715   int length = thisSize + tSize;
716
717   // possible cases:
718   if (thisSize == 0) {
719     // this is empty
720     *this = t;
721   } else if (tSize == 0) {
722     // t is empty
723   } else if (m_rep->baseIsSelf() && m_rep->rc == 1) {
724     // this is direct and has refcount of 1 (so we can just alter it directly)
725     expandCapacity(thisOffset + length);
726     if (data()) {
727         memcpy(const_cast<UChar*>(data() + thisSize), t.data(), tSize * sizeof(UChar));
728         m_rep->len = length;
729         m_rep->_hash = 0;
730     }
731   } else if (thisOffset + thisSize == usedCapacity() && thisSize >= minShareSize) {
732     // this reaches the end of the buffer - extend it if it's long enough to append to
733     expandCapacity(thisOffset + length);
734     if (data()) {
735         memcpy(const_cast<UChar*>(data() + thisSize), t.data(), tSize * sizeof(UChar));
736         m_rep = Rep::create(m_rep, 0, length);
737     }
738   } else {
739     // this is shared with someone using more capacity, gotta make a whole new string
740     size_t newCapacity = expandedSize(length, 0);
741     UChar* d = allocChars(newCapacity);
742     if (!d)
743         m_rep = &Rep::null;
744     else {
745         memcpy(d, data(), thisSize * sizeof(UChar));
746         memcpy(const_cast<UChar*>(d + thisSize), t.data(), tSize * sizeof(UChar));
747         m_rep = Rep::create(d, length);
748         m_rep->capacity = newCapacity;
749     }
750   }
751
752   return *this;
753 }
754
755 UString &UString::append(const char *t)
756 {
757   int thisSize = size();
758   int thisOffset = m_rep->offset;
759   int tSize = static_cast<int>(strlen(t));
760   int length = thisSize + tSize;
761
762   // possible cases:
763   if (thisSize == 0) {
764     // this is empty
765     *this = t;
766   } else if (tSize == 0) {
767     // t is empty, we'll just return *this below.
768   } else if (m_rep->baseIsSelf() && m_rep->rc == 1) {
769     // this is direct and has refcount of 1 (so we can just alter it directly)
770     expandCapacity(thisOffset + length);
771     UChar *d = const_cast<UChar *>(data());
772     if (d) {
773         for (int i = 0; i < tSize; ++i)
774             d[thisSize + i] = t[i];
775         m_rep->len = length;
776         m_rep->_hash = 0;
777     }
778   } else if (thisOffset + thisSize == usedCapacity() && thisSize >= minShareSize) {
779     // this string reaches the end of the buffer - extend it
780     expandCapacity(thisOffset + length);
781     UChar *d = const_cast<UChar *>(data());
782     if (d) {
783         for (int i = 0; i < tSize; ++i)
784             d[thisSize + i] = t[i];
785         m_rep = Rep::create(m_rep, 0, length);
786     }
787   } else {
788     // this is shared with someone using more capacity, gotta make a whole new string
789     size_t newCapacity = expandedSize(length, 0);
790     UChar* d = allocChars(newCapacity);
791     if (!d)
792         m_rep = &Rep::null;
793     else {
794         memcpy(d, data(), thisSize * sizeof(UChar));
795         for (int i = 0; i < tSize; ++i)
796             d[thisSize + i] = t[i];
797         m_rep = Rep::create(d, length);
798         m_rep->capacity = newCapacity;
799     }
800   }
801
802   return *this;
803 }
804
805 UString &UString::append(unsigned short c)
806 {
807   int thisOffset = m_rep->offset;
808   int length = size();
809
810   // possible cases:
811   if (length == 0) {
812     // this is empty - must make a new m_rep because we don't want to pollute the shared empty one 
813     size_t newCapacity = expandedSize(1, 0);
814     UChar* d = allocChars(newCapacity);
815     if (!d)
816         m_rep = &Rep::null;
817     else {
818         d[0] = c;
819         m_rep = Rep::create(d, 1);
820         m_rep->capacity = newCapacity;
821     }
822   } else if (m_rep->baseIsSelf() && m_rep->rc == 1) {
823     // this is direct and has refcount of 1 (so we can just alter it directly)
824     expandCapacity(thisOffset + length + 1);
825     UChar *d = const_cast<UChar *>(data());
826     if (d) {
827         d[length] = c;
828         m_rep->len = length + 1;
829         m_rep->_hash = 0;
830     }
831   } else if (thisOffset + length == usedCapacity() && length >= minShareSize) {
832     // this reaches the end of the string - extend it and share
833     expandCapacity(thisOffset + length + 1);
834     UChar *d = const_cast<UChar *>(data());
835     if (d) {
836         d[length] = c;
837         m_rep = Rep::create(m_rep, 0, length + 1);
838     }
839   } else {
840     // this is shared with someone using more capacity, gotta make a whole new string
841     size_t newCapacity = expandedSize(length + 1, 0);
842     UChar* d = allocChars(newCapacity);
843     if (!d)
844         m_rep = &Rep::null;
845     else {
846         memcpy(d, data(), length * sizeof(UChar));
847         d[length] = c;
848         m_rep = Rep::create(d, length + 1);
849         m_rep->capacity = newCapacity;
850     }
851   }
852
853   return *this;
854 }
855
856 CString UString::cstring() const
857 {
858   return ascii();
859 }
860
861 char *UString::ascii() const
862 {
863   // Never make the buffer smaller than normalStatBufferSize.
864   // Thus we almost never need to reallocate.
865   int length = size();
866   int neededSize = length + 1;
867   if (neededSize < normalStatBufferSize) {
868     neededSize = normalStatBufferSize;
869   }
870   if (neededSize != statBufferSize) {
871     delete [] statBuffer;
872     statBuffer = new char [neededSize];
873     statBufferSize = neededSize;
874   }
875   
876   const UChar *p = data();
877   char *q = statBuffer;
878   const UChar *limit = p + length;
879   while (p != limit) {
880     *q = static_cast<char>(p->uc);
881     ++p;
882     ++q;
883   }
884   *q = '\0';
885
886   return statBuffer;
887 }
888
889 UString &UString::operator=(const char *c)
890 {
891     if (!c) {
892         m_rep = &Rep::null;
893         return *this;
894     }
895
896     if (!c[0]) {
897         m_rep = &Rep::empty;
898         return *this;
899     }
900
901   int l = static_cast<int>(strlen(c));
902   UChar *d;
903   if (m_rep->rc == 1 && l <= m_rep->capacity && m_rep->baseIsSelf() && m_rep->offset == 0 && m_rep->preCapacity == 0) {
904     d = m_rep->buf;
905     m_rep->_hash = 0;
906     m_rep->len = l;
907   } else {
908     d = allocChars(l);
909     if (!d) {
910         m_rep = &Rep::null;
911         return *this;
912     }
913     m_rep = Rep::create(d, l);
914   }
915   for (int i = 0; i < l; i++)
916     d[i].uc = c[i];
917
918   return *this;
919 }
920
921 bool UString::is8Bit() const
922 {
923   const UChar *u = data();
924   const UChar *limit = u + size();
925   while (u < limit) {
926     if (u->uc > 0xFF)
927       return false;
928     ++u;
929   }
930
931   return true;
932 }
933
934 const UChar UString::operator[](int pos) const
935 {
936   if (pos >= size())
937     return '\0';
938   return data()[pos];
939 }
940
941 double UString::toDouble(bool tolerateTrailingJunk, bool tolerateEmptyString) const
942 {
943   double d;
944
945   // FIXME: If tolerateTrailingJunk is true, then we want to tolerate non-8-bit junk
946   // after the number, so is8Bit is too strict a check.
947   if (!is8Bit())
948     return NaN;
949
950   const char *c = ascii();
951
952   // skip leading white space
953   while (isASCIISpace(*c))
954     c++;
955
956   // empty string ?
957   if (*c == '\0')
958     return tolerateEmptyString ? 0.0 : NaN;
959
960   // hex number ?
961   if (*c == '0' && (*(c+1) == 'x' || *(c+1) == 'X')) {
962     const char* firstDigitPosition = c + 2;
963     c++;
964     d = 0.0;
965     while (*(++c)) {
966       if (*c >= '0' && *c <= '9')
967         d = d * 16.0 + *c - '0';
968       else if ((*c >= 'A' && *c <= 'F') || (*c >= 'a' && *c <= 'f'))
969         d = d * 16.0 + (*c & 0xdf) - 'A' + 10.0;
970       else
971         break;
972     }
973
974     if (d >= mantissaOverflowLowerBound)
975         d = parseIntOverflow(firstDigitPosition, c - firstDigitPosition, 16);
976   } else {
977     // regular number ?
978     char *end;
979     d = kjs_strtod(c, &end);
980     if ((d != 0.0 || end != c) && d != Inf && d != -Inf) {
981       c = end;
982     } else {
983       double sign = 1.0;
984
985       if (*c == '+')
986         c++;
987       else if (*c == '-') {
988         sign = -1.0;
989         c++;
990       }
991
992       // We used strtod() to do the conversion. However, strtod() handles
993       // infinite values slightly differently than JavaScript in that it
994       // converts the string "inf" with any capitalization to infinity,
995       // whereas the ECMA spec requires that it be converted to NaN.
996
997       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') {
998         d = sign * Inf;
999         c += 8;
1000       } else if ((d == Inf || d == -Inf) && *c != 'I' && *c != 'i')
1001         c = end;
1002       else
1003         return NaN;
1004     }
1005   }
1006
1007   // allow trailing white space
1008   while (isASCIISpace(*c))
1009     c++;
1010   // don't allow anything after - unless tolerant=true
1011   if (!tolerateTrailingJunk && *c != '\0')
1012     d = NaN;
1013
1014   return d;
1015 }
1016
1017 double UString::toDouble(bool tolerateTrailingJunk) const
1018 {
1019   return toDouble(tolerateTrailingJunk, true);
1020 }
1021
1022 double UString::toDouble() const
1023 {
1024   return toDouble(false, true);
1025 }
1026
1027 uint32_t UString::toUInt32(bool *ok) const
1028 {
1029   double d = toDouble();
1030   bool b = true;
1031
1032   if (d != static_cast<uint32_t>(d)) {
1033     b = false;
1034     d = 0;
1035   }
1036
1037   if (ok)
1038     *ok = b;
1039
1040   return static_cast<uint32_t>(d);
1041 }
1042
1043 uint32_t UString::toUInt32(bool *ok, bool tolerateEmptyString) const
1044 {
1045   double d = toDouble(false, tolerateEmptyString);
1046   bool b = true;
1047
1048   if (d != static_cast<uint32_t>(d)) {
1049     b = false;
1050     d = 0;
1051   }
1052
1053   if (ok)
1054     *ok = b;
1055
1056   return static_cast<uint32_t>(d);
1057 }
1058
1059 uint32_t UString::toStrictUInt32(bool *ok) const
1060 {
1061   if (ok)
1062     *ok = false;
1063
1064   // Empty string is not OK.
1065   int len = m_rep->len;
1066   if (len == 0)
1067     return 0;
1068   const UChar *p = m_rep->data();
1069   unsigned short c = p->unicode();
1070
1071   // If the first digit is 0, only 0 itself is OK.
1072   if (c == '0') {
1073     if (len == 1 && ok)
1074       *ok = true;
1075     return 0;
1076   }
1077   
1078   // Convert to UInt32, checking for overflow.
1079   uint32_t i = 0;
1080   while (1) {
1081     // Process character, turning it into a digit.
1082     if (c < '0' || c > '9')
1083       return 0;
1084     const unsigned d = c - '0';
1085     
1086     // Multiply by 10, checking for overflow out of 32 bits.
1087     if (i > 0xFFFFFFFFU / 10)
1088       return 0;
1089     i *= 10;
1090     
1091     // Add in the digit, checking for overflow out of 32 bits.
1092     const unsigned max = 0xFFFFFFFFU - d;
1093     if (i > max)
1094         return 0;
1095     i += d;
1096     
1097     // Handle end of string.
1098     if (--len == 0) {
1099       if (ok)
1100         *ok = true;
1101       return i;
1102     }
1103     
1104     // Get next character.
1105     c = (++p)->unicode();
1106   }
1107 }
1108
1109 int UString::find(const UString &f, int pos) const
1110 {
1111   int sz = size();
1112   int fsz = f.size();
1113   if (sz < fsz)
1114     return -1;
1115   if (pos < 0)
1116     pos = 0;
1117   if (fsz == 0)
1118     return pos;
1119   const UChar *end = data() + sz - fsz;
1120   int fsizeminusone = (fsz - 1) * sizeof(UChar);
1121   const UChar *fdata = f.data();
1122   unsigned short fchar = fdata->uc;
1123   ++fdata;
1124   for (const UChar *c = data() + pos; c <= end; c++)
1125     if (c->uc == fchar && !memcmp(c + 1, fdata, fsizeminusone))
1126       return static_cast<int>(c - data());
1127
1128   return -1;
1129 }
1130
1131 int UString::find(UChar ch, int pos) const
1132 {
1133   if (pos < 0)
1134     pos = 0;
1135   const UChar *end = data() + size();
1136   for (const UChar *c = data() + pos; c < end; c++)
1137     if (*c == ch)
1138       return static_cast<int>(c - data());
1139
1140   return -1;
1141 }
1142
1143 int UString::rfind(const UString &f, int pos) const
1144 {
1145   int sz = size();
1146   int fsz = f.size();
1147   if (sz < fsz)
1148     return -1;
1149   if (pos < 0)
1150     pos = 0;
1151   if (pos > sz - fsz)
1152     pos = sz - fsz;
1153   if (fsz == 0)
1154     return pos;
1155   int fsizeminusone = (fsz - 1) * sizeof(UChar);
1156   const UChar *fdata = f.data();
1157   for (const UChar *c = data() + pos; c >= data(); c--) {
1158     if (*c == *fdata && !memcmp(c + 1, fdata + 1, fsizeminusone))
1159       return static_cast<int>(c - data());
1160   }
1161
1162   return -1;
1163 }
1164
1165 int UString::rfind(UChar ch, int pos) const
1166 {
1167   if (isEmpty())
1168     return -1;
1169   if (pos + 1 >= size())
1170     pos = size() - 1;
1171   for (const UChar *c = data() + pos; c >= data(); c--) {
1172     if (*c == ch)
1173       return static_cast<int>(c-data());
1174   }
1175
1176   return -1;
1177 }
1178
1179 UString UString::substr(int pos, int len) const
1180 {
1181   int s = size();
1182
1183   if (pos < 0)
1184     pos = 0;
1185   else if (pos >= s)
1186     pos = s;
1187   if (len < 0)
1188     len = s;
1189   if (pos + len >= s)
1190     len = s - pos;
1191
1192   if (pos == 0 && len == s)
1193     return *this;
1194
1195   return UString(Rep::create(m_rep, pos, len));
1196 }
1197
1198 bool operator==(const UString& s1, const UString& s2)
1199 {
1200   if (s1.m_rep->len != s2.m_rep->len)
1201     return false;
1202
1203   return (memcmp(s1.m_rep->data(), s2.m_rep->data(),
1204                  s1.m_rep->len * sizeof(UChar)) == 0);
1205 }
1206
1207 bool operator==(const UString& s1, const char *s2)
1208 {
1209   if (s2 == 0) {
1210     return s1.isEmpty();
1211   }
1212
1213   const UChar *u = s1.data();
1214   const UChar *uend = u + s1.size();
1215   while (u != uend && *s2) {
1216     if (u->uc != (unsigned char)*s2)
1217       return false;
1218     s2++;
1219     u++;
1220   }
1221
1222   return u == uend && *s2 == 0;
1223 }
1224
1225 bool operator<(const UString& s1, const UString& s2)
1226 {
1227   const int l1 = s1.size();
1228   const int l2 = s2.size();
1229   const int lmin = l1 < l2 ? l1 : l2;
1230   const UChar *c1 = s1.data();
1231   const UChar *c2 = s2.data();
1232   int l = 0;
1233   while (l < lmin && *c1 == *c2) {
1234     c1++;
1235     c2++;
1236     l++;
1237   }
1238   if (l < lmin)
1239     return (c1->uc < c2->uc);
1240
1241   return (l1 < l2);
1242 }
1243
1244 int compare(const UString& s1, const UString& s2)
1245 {
1246   const int l1 = s1.size();
1247   const int l2 = s2.size();
1248   const int lmin = l1 < l2 ? l1 : l2;
1249   const UChar *c1 = s1.data();
1250   const UChar *c2 = s2.data();
1251   int l = 0;
1252   while (l < lmin && *c1 == *c2) {
1253     c1++;
1254     c2++;
1255     l++;
1256   }
1257
1258   if (l < lmin)
1259     return (c1->uc > c2->uc) ? 1 : -1;
1260
1261   if (l1 == l2)
1262     return 0;
1263
1264   return (l1 > l2) ? 1 : -1;
1265 }
1266
1267 CString UString::UTF8String(bool strict) const
1268 {
1269   // Allocate a buffer big enough to hold all the characters.
1270   const int length = size();
1271   Vector<char, 1024> buffer(length * 3);
1272
1273   // Convert to runs of 8-bit characters.
1274   char* p = buffer.data();
1275   const ::UChar* d = reinterpret_cast<const ::UChar*>(&data()->uc);
1276   ConversionResult result = convertUTF16ToUTF8(&d, d + length, &p, p + buffer.size(), strict);
1277   if (result != conversionOK)
1278     return CString();
1279
1280   return CString(buffer.data(), p - buffer.data());
1281 }
1282
1283
1284 } // namespace KJS