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