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