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