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