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