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