d21af1d3b27923c4986cdc35cdab56b5db553f79
[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::append(const UString &t)
610 {
611   int thisSize = size();
612   int thisOffset = rep->offset;
613   int tSize = t.size();
614   int length = thisSize + tSize;
615
616   // possible cases:
617   if (thisSize == 0) {
618     // this is empty
619     *this = t;
620   } else if (tSize == 0) {
621     // t is empty
622   } else if (!rep->baseString && rep->rc == 1) {
623     // this is direct and has refcount of 1 (so we can just alter it directly)
624     expandCapacity(thisOffset + length);
625     memcpy(const_cast<UChar *>(data() + thisSize), t.data(), tSize * sizeof(UChar));
626     rep->len = length;
627     rep->_hash = 0;
628   } else if (thisOffset + thisSize == usedCapacity()) {
629     // this reaches the end of the buffer - extend it
630     expandCapacity(thisOffset + length);
631     memcpy(const_cast<UChar *>(data() + thisSize), t.data(), tSize * sizeof(UChar));
632     Rep *newRep = Rep::create(rep, 0, length);
633     release();
634     rep = newRep;
635   } else {
636     // this is shared with someone using more capacity, gotta make a whole new string
637     int newCapacity = expandedSize(length, 0);
638     UChar *d = static_cast<UChar *>(malloc(sizeof(UChar) * newCapacity));
639     memcpy(d, data(), thisSize * sizeof(UChar));
640     memcpy(const_cast<UChar *>(d + thisSize), t.data(), tSize * sizeof(UChar));
641     release();
642     rep = Rep::create(d, length);
643     rep->capacity = newCapacity;
644   }
645
646   return *this;
647 }
648
649 UString &UString::append(const char *t)
650 {
651   int thisSize = size();
652   int thisOffset = rep->offset;
653   int tSize = strlen(t);
654   int length = thisSize + tSize;
655
656   // possible cases:
657   if (thisSize == 0) {
658     // this is empty
659     *this = t;
660   } else if (tSize == 0) {
661     // t is empty, we'll just return *this below.
662   } else if (!rep->baseString && rep->rc == 1) {
663     // this is direct and has refcount of 1 (so we can just alter it directly)
664     expandCapacity(thisOffset + length);
665     UChar *d = const_cast<UChar *>(data());
666     for (int i = 0; i < tSize; ++i)
667       d[thisSize+i] = t[i];
668     rep->len = length;
669     rep->_hash = 0;
670   } else if (thisOffset + thisSize == usedCapacity()) {
671     // this string reaches the end of the buffer - extend it
672     expandCapacity(thisOffset + length);
673     UChar *d = const_cast<UChar *>(data());
674     for (int i = 0; i < tSize; ++i)
675       d[thisSize+i] = t[i];
676     Rep *newRep = Rep::create(rep, 0, length);
677     release();
678     rep = newRep;
679   } else {
680     // this is shared with someone using more capacity, gotta make a whole new string
681     int newCapacity = expandedSize(length, 0);
682     UChar *d = static_cast<UChar *>(malloc(sizeof(UChar) * newCapacity));
683     memcpy(d, data(), thisSize * sizeof(UChar));
684     for (int i = 0; i < tSize; ++i)
685       d[thisSize+i] = t[i];
686     release();
687     rep = Rep::create(d, length);
688     rep->capacity = newCapacity;
689   }
690
691   return *this;
692 }
693
694 UString &UString::append(unsigned short c)
695 {
696   int thisOffset = rep->offset;
697   int length = size();
698
699   // possible cases:
700   if (length == 0) {
701     // this is empty - must make a new rep because we don't want to pollute the shared empty one 
702     int newCapacity = expandedSize(1, 0);
703     UChar *d = static_cast<UChar *>(malloc(sizeof(UChar) * newCapacity));
704     d[0] = c;
705     release();
706     rep = Rep::create(d, 1);
707     rep->capacity = newCapacity;
708   } else if (!rep->baseString && rep->rc == 1) {
709     // this is direct and has refcount of 1 (so we can just alter it directly)
710     expandCapacity(thisOffset + length + 1);
711     UChar *d = const_cast<UChar *>(data());
712     d[length] = c;
713     rep->len = length + 1;
714     rep->_hash = 0;
715   } else if (thisOffset + length == usedCapacity()) {
716     // this reaches the end of the string - extend it and share
717     expandCapacity(thisOffset + length + 1);
718     UChar *d = const_cast<UChar *>(data());
719     d[length] = c;
720     Rep *newRep = Rep::create(rep, 0, length + 1);
721     release();
722     rep = newRep;
723   } else {
724     // this is shared with someone using more capacity, gotta make a whole new string
725     int newCapacity = expandedSize((length + 1), 0);
726     UChar *d = static_cast<UChar *>(malloc(sizeof(UChar) * newCapacity));
727     memcpy(d, data(), length * sizeof(UChar));
728     d[length] = c;
729     release();
730     rep = Rep::create(d, length);
731     rep->capacity = newCapacity;
732   }
733
734   return *this;
735 }
736
737 CString UString::cstring() const
738 {
739   return ascii();
740 }
741
742 char *UString::ascii() const
743 {
744   // Never make the buffer smaller than normalStatBufferSize.
745   // Thus we almost never need to reallocate.
746   int length = size();
747   int neededSize = length + 1;
748   if (neededSize < normalStatBufferSize) {
749     neededSize = normalStatBufferSize;
750   }
751   if (neededSize != statBufferSize) {
752     delete [] statBuffer;
753     statBuffer = new char [neededSize];
754     statBufferSize = neededSize;
755   }
756   
757   const UChar *p = data();
758   char *q = statBuffer;
759   const UChar *limit = p + length;
760   while (p != limit) {
761     *q = p->uc;
762     ++p;
763     ++q;
764   }
765   *q = '\0';
766
767   return statBuffer;
768 }
769
770 #ifdef KJS_DEBUG_MEM
771 void UString::globalClear()
772 {
773   delete [] statBuffer;
774   statBuffer = 0;
775   statBufferSize = 0;
776 }
777 #endif
778
779 UString &UString::operator=(const char *c)
780 {
781   int l = c ? strlen(c) : 0;
782   UChar *d;
783   if (rep->rc == 1 && l <= rep->capacity && !rep->baseString && rep->offset == 0 && rep->preCapacity == 0) {
784     d = rep->buf;
785     rep->_hash = 0;
786   } else {
787     release();
788     d = static_cast<UChar *>(malloc(sizeof(UChar) * l));
789     rep = Rep::create(d, l);
790   }
791   for (int i = 0; i < l; i++)
792     d[i].uc = c[i];
793
794   return *this;
795 }
796
797 UString &UString::operator=(const UString &str)
798 {
799   str.rep->ref();
800   release();
801   rep = str.rep;
802
803   return *this;
804 }
805
806 bool UString::is8Bit() const
807 {
808   const UChar *u = data();
809   const UChar *limit = u + size();
810   while (u < limit) {
811     if (u->uc > 0xFF)
812       return false;
813     ++u;
814   }
815
816   return true;
817 }
818
819 UChar UString::operator[](int pos) const
820 {
821   if (pos >= size())
822     return '\0';
823   return data()[pos];
824 }
825
826 UCharReference UString::operator[](int pos)
827 {
828   /* TODO: boundary check */
829   return UCharReference(this, pos);
830 }
831
832 double UString::toDouble(bool tolerateTrailingJunk, bool tolerateEmptyString) const
833 {
834   double d;
835
836   // FIXME: If tolerateTrailingJunk is true, then we want to tolerate non-8-bit junk
837   // after the number, so is8Bit is too strict a check.
838   if (!is8Bit())
839     return NaN;
840
841   const char *c = ascii();
842
843   // skip leading white space
844   while (isspace(*c))
845     c++;
846
847   // empty string ?
848   if (*c == '\0')
849     return tolerateEmptyString ? 0.0 : NaN;
850
851   // hex number ?
852   if (*c == '0' && (*(c+1) == 'x' || *(c+1) == 'X')) {
853     c++;
854     d = 0.0;
855     while (*(++c)) {
856       if (*c >= '0' && *c <= '9')
857         d = d * 16.0 + *c - '0';
858       else if ((*c >= 'A' && *c <= 'F') || (*c >= 'a' && *c <= 'f'))
859         d = d * 16.0 + (*c & 0xdf) - 'A' + 10.0;
860       else
861         break;
862     }
863   } else {
864     // regular number ?
865     char *end;
866     d = kjs_strtod(c, &end);
867     if ((d != 0.0 || end != c) && d != HUGE_VAL && d != -HUGE_VAL) {
868       c = end;
869     } else {
870       // infinity ?
871       d = 1.0;
872       if (*c == '+')
873         c++;
874       else if (*c == '-') {
875         d = -1.0;
876         c++;
877       }
878       if (strncmp(c, "Infinity", 8) != 0)
879         return NaN;
880       d = d * Inf;
881       c += 8;
882     }
883   }
884
885   // allow trailing white space
886   while (isspace(*c))
887     c++;
888   // don't allow anything after - unless tolerant=true
889   if (!tolerateTrailingJunk && *c != '\0')
890     d = NaN;
891
892   return d;
893 }
894
895 double UString::toDouble(bool tolerateTrailingJunk) const
896 {
897   return toDouble(tolerateTrailingJunk, true);
898 }
899
900 double UString::toDouble() const
901 {
902   return toDouble(false, true);
903 }
904
905 unsigned long UString::toULong(bool *ok, bool tolerateEmptyString) const
906 {
907   double d = toDouble(false, tolerateEmptyString);
908   bool b = true;
909
910   if (isNaN(d) || d != static_cast<unsigned long>(d)) {
911     b = false;
912     d = 0;
913   }
914
915   if (ok)
916     *ok = b;
917
918   return static_cast<unsigned long>(d);
919 }
920
921 unsigned long UString::toULong(bool *ok) const
922 {
923   return toULong(ok, true);
924 }
925
926 uint32_t UString::toUInt32(bool *ok) const
927 {
928   double d = toDouble();
929   bool b = true;
930
931   if (isNaN(d) || d != static_cast<uint32_t>(d)) {
932     b = false;
933     d = 0;
934   }
935
936   if (ok)
937     *ok = b;
938
939   return static_cast<uint32_t>(d);
940 }
941
942 uint32_t UString::toStrictUInt32(bool *ok) const
943 {
944   if (ok)
945     *ok = false;
946
947   // Empty string is not OK.
948   int len = rep->len;
949   if (len == 0)
950     return 0;
951   const UChar *p = rep->data();
952   unsigned short c = p->unicode();
953
954   // If the first digit is 0, only 0 itself is OK.
955   if (c == '0') {
956     if (len == 1 && ok)
957       *ok = true;
958     return 0;
959   }
960   
961   // Convert to UInt32, checking for overflow.
962   uint32_t i = 0;
963   while (1) {
964     // Process character, turning it into a digit.
965     if (c < '0' || c > '9')
966       return 0;
967     const unsigned d = c - '0';
968     
969     // Multiply by 10, checking for overflow out of 32 bits.
970     if (i > 0xFFFFFFFFU / 10)
971       return 0;
972     i *= 10;
973     
974     // Add in the digit, checking for overflow out of 32 bits.
975     const unsigned max = 0xFFFFFFFFU - d;
976     if (i > max)
977         return 0;
978     i += d;
979     
980     // Handle end of string.
981     if (--len == 0) {
982       if (ok)
983         *ok = true;
984       return i;
985     }
986     
987     // Get next character.
988     c = (++p)->unicode();
989   }
990 }
991
992 // Rule from ECMA 15.2 about what an array index is.
993 // Must exactly match string form of an unsigned integer, and be less than 2^32 - 1.
994 unsigned UString::toArrayIndex(bool *ok) const
995 {
996   unsigned i = toStrictUInt32(ok);
997   if (i >= 0xFFFFFFFFU && ok)
998     *ok = false;
999   return i;
1000 }
1001
1002 int UString::find(const UString &f, int pos) const
1003 {
1004   int sz = size();
1005   int fsz = f.size();
1006   if (sz < fsz)
1007     return -1;
1008   if (pos < 0)
1009     pos = 0;
1010   if (fsz == 0)
1011     return pos;
1012   const UChar *end = data() + sz - fsz;
1013   long fsizeminusone = (fsz - 1) * sizeof(UChar);
1014   const UChar *fdata = f.data();
1015   for (const UChar *c = data() + pos; c <= end; c++)
1016     if (*c == *fdata && !memcmp(c + 1, fdata + 1, fsizeminusone))
1017       return (c-data());
1018
1019   return -1;
1020 }
1021
1022 int UString::find(UChar ch, int pos) const
1023 {
1024   if (pos < 0)
1025     pos = 0;
1026   const UChar *end = data() + size();
1027   for (const UChar *c = data() + pos; c < end; c++)
1028     if (*c == ch)
1029       return (c-data());
1030
1031   return -1;
1032 }
1033
1034 int UString::rfind(const UString &f, int pos) const
1035 {
1036   int sz = size();
1037   int fsz = f.size();
1038   if (sz < fsz)
1039     return -1;
1040   if (pos < 0)
1041     pos = 0;
1042   if (pos > sz - fsz)
1043     pos = sz - fsz;
1044   if (fsz == 0)
1045     return pos;
1046   long fsizeminusone = (fsz - 1) * sizeof(UChar);
1047   const UChar *fdata = f.data();
1048   for (const UChar *c = data() + pos; c >= data(); c--) {
1049     if (*c == *fdata && !memcmp(c + 1, fdata + 1, fsizeminusone))
1050       return (c-data());
1051   }
1052
1053   return -1;
1054 }
1055
1056 int UString::rfind(UChar ch, int pos) const
1057 {
1058   if (isEmpty())
1059     return -1;
1060   if (pos + 1 >= size())
1061     pos = size() - 1;
1062   for (const UChar *c = data() + pos; c >= data(); c--) {
1063     if (*c == ch)
1064       return (c-data());
1065   }
1066
1067   return -1;
1068 }
1069
1070 UString UString::substr(int pos, int len) const
1071 {
1072   int s = size();
1073
1074   if (pos < 0)
1075     pos = 0;
1076   else if (pos >= s)
1077     pos = s;
1078   if (len < 0)
1079     len = s;
1080   if (pos + len >= s)
1081     len = s - pos;
1082
1083   if (pos == 0 && len == s)
1084     return *this;
1085
1086   UString::Rep *newRep = Rep::create(rep, pos, len);
1087   UString result(newRep);
1088   newRep->deref();
1089
1090   return result;
1091 }
1092
1093 void UString::attach(Rep *r)
1094 {
1095   rep = r;
1096   rep->ref();
1097 }
1098
1099 void UString::detach()
1100 {
1101   if (rep->rc > 1 || rep->baseString) {
1102     int l = size();
1103     UChar *n = static_cast<UChar *>(malloc(sizeof(UChar) * l));
1104     memcpy(n, data(), l * sizeof(UChar));
1105     release();
1106     rep = Rep::create(n, l);
1107   }
1108 }
1109
1110 void UString::release()
1111 {
1112   rep->deref();
1113 }
1114
1115 bool KJS::operator==(const UString& s1, const UString& s2)
1116 {
1117   if (s1.rep->len != s2.rep->len)
1118     return false;
1119
1120   return (memcmp(s1.rep->data(), s2.rep->data(),
1121                  s1.rep->len * sizeof(UChar)) == 0);
1122 }
1123
1124 bool KJS::operator==(const UString& s1, const char *s2)
1125 {
1126   if (s2 == 0) {
1127     return s1.isEmpty();
1128   }
1129
1130   const UChar *u = s1.data();
1131   const UChar *uend = u + s1.size();
1132   while (u != uend && *s2) {
1133     if (u->uc != (unsigned char)*s2)
1134       return false;
1135     s2++;
1136     u++;
1137   }
1138
1139   return u == uend && *s2 == 0;
1140 }
1141
1142 bool KJS::operator<(const UString& s1, const UString& s2)
1143 {
1144   const int l1 = s1.size();
1145   const int l2 = s2.size();
1146   const int lmin = l1 < l2 ? l1 : l2;
1147   const UChar *c1 = s1.data();
1148   const UChar *c2 = s2.data();
1149   int l = 0;
1150   while (l < lmin && *c1 == *c2) {
1151     c1++;
1152     c2++;
1153     l++;
1154   }
1155   if (l < lmin)
1156     return (c1->uc < c2->uc);
1157
1158   return (l1 < l2);
1159 }
1160
1161 int KJS::compare(const UString& s1, const UString& s2)
1162 {
1163   const int l1 = s1.size();
1164   const int l2 = s2.size();
1165   const int lmin = l1 < l2 ? l1 : l2;
1166   const UChar *c1 = s1.data();
1167   const UChar *c2 = s2.data();
1168   int l = 0;
1169   while (l < lmin && *c1 == *c2) {
1170     c1++;
1171     c2++;
1172     l++;
1173   }
1174   if (l < lmin)
1175     return (c1->uc > c2->uc) ? 1 : -1;
1176
1177   if (l1 == l2) {
1178     return 0;
1179   }
1180   return (l1 < l2) ? 1 : -1;
1181 }
1182
1183 inline int inlineUTF8SequenceLengthNonASCII(char b0)
1184 {
1185   if ((b0 & 0xC0) != 0xC0)
1186     return 0;
1187   if ((b0 & 0xE0) == 0xC0)
1188     return 2;
1189   if ((b0 & 0xF0) == 0xE0)
1190     return 3;
1191   if ((b0 & 0xF8) == 0xF0)
1192     return 4;
1193   return 0;
1194 }
1195
1196 int UTF8SequenceLengthNonASCII(char b0)
1197 {
1198   return inlineUTF8SequenceLengthNonASCII(b0);
1199 }
1200
1201 inline int inlineUTF8SequenceLength(char b0)
1202 {
1203   return (b0 & 0x80) == 0 ? 1 : UTF8SequenceLengthNonASCII(b0);
1204 }
1205
1206 // Given a first byte, gives the length of the UTF-8 sequence it begins.
1207 // Returns 0 for bytes that are not legal starts of UTF-8 sequences.
1208 // Only allows sequences of up to 4 bytes, since that works for all Unicode characters (U-00000000 to U-0010FFFF).
1209 int UTF8SequenceLength(char b0)
1210 {
1211   return (b0 & 0x80) == 0 ? 1 : inlineUTF8SequenceLengthNonASCII(b0);
1212 }
1213
1214 // Takes a null-terminated C-style string with a UTF-8 sequence in it and converts it to a character.
1215 // Only allows Unicode characters (U-00000000 to U-0010FFFF).
1216 // Returns -1 if the sequence is not valid (including presence of extra bytes).
1217 int decodeUTF8Sequence(const char *sequence)
1218 {
1219   // Handle 0-byte sequences (never valid).
1220   const unsigned char b0 = sequence[0];
1221   const int length = inlineUTF8SequenceLength(b0);
1222   if (length == 0)
1223     return -1;
1224
1225   // Handle 1-byte sequences (plain ASCII).
1226   const unsigned char b1 = sequence[1];
1227   if (length == 1) {
1228     if (b1)
1229       return -1;
1230     return b0;
1231   }
1232
1233   // Handle 2-byte sequences.
1234   if ((b1 & 0xC0) != 0x80)
1235     return -1;
1236   const unsigned char b2 = sequence[2];
1237   if (length == 2) {
1238     if (b2)
1239       return -1;
1240     const int c = ((b0 & 0x1F) << 6) | (b1 & 0x3F);
1241     if (c < 0x80)
1242       return -1;
1243     return c;
1244   }
1245
1246   // Handle 3-byte sequences.
1247   if ((b2 & 0xC0) != 0x80)
1248     return -1;
1249   const unsigned char b3 = sequence[3];
1250   if (length == 3) {
1251     if (b3)
1252       return -1;
1253     const int c = ((b0 & 0xF) << 12) | ((b1 & 0x3F) << 6) | (b2 & 0x3F);
1254     if (c < 0x800)
1255       return -1;
1256     // UTF-16 surrogates should never appear in UTF-8 data.
1257     if (c >= 0xD800 && c <= 0xDFFF)
1258       return -1;
1259     // Backwards BOM and U+FFFF should never appear in UTF-8 data.
1260     if (c == 0xFFFE || c == 0xFFFF)
1261       return -1;
1262     return c;
1263   }
1264
1265   // Handle 4-byte sequences.
1266   if ((b3 & 0xC0) != 0x80)
1267     return -1;
1268   const unsigned char b4 = sequence[4];
1269   if (length == 4) {
1270     if (b4)
1271       return -1;
1272     const int c = ((b0 & 0x7) << 18) | ((b1 & 0x3F) << 12) | ((b2 & 0x3F) << 6) | (b3 & 0x3F);
1273     if (c < 0x10000 || c > 0x10FFFF)
1274       return -1;
1275     return c;
1276   }
1277
1278   return -1;
1279 }
1280
1281 CString UString::UTF8String() const
1282 {
1283   // Allocate a buffer big enough to hold all the characters.
1284   const int length = size();
1285   const unsigned bufferSize = length * 3;
1286   char fixedSizeBuffer[1024];
1287   char *buffer;
1288   if (bufferSize > sizeof(fixedSizeBuffer)) {
1289     buffer = new char [bufferSize];
1290   } else {
1291     buffer = fixedSizeBuffer;
1292   }
1293
1294   // Convert to runs of 8-bit characters.
1295   char *p = buffer;
1296   const UChar *d = data();
1297   for (int i = 0; i != length; ++i) {
1298     unsigned short c = d[i].unicode();
1299     if (c < 0x80) {
1300       *p++ = (char)c;
1301     } else if (c < 0x800) {
1302       *p++ = (char)((c >> 6) | 0xC0); // C0 is the 2-byte flag for UTF-8
1303       *p++ = (char)((c | 0x80) & 0xBF); // next 6 bits, with high bit set
1304     } else if (c >= 0xD800 && c <= 0xDBFF && i < length && d[i+1].uc >= 0xDC00 && d[i+2].uc <= 0xDFFF) {
1305       unsigned sc = 0x10000 + (((c & 0x3FF) << 10) | (d[i+1].uc & 0x3FF));
1306       *p++ = (char)((sc >> 18) | 0xF0); // F0 is the 4-byte flag for UTF-8
1307       *p++ = (char)(((sc >> 12) | 0x80) & 0xBF); // next 6 bits, with high bit set
1308       *p++ = (char)(((sc >> 6) | 0x80) & 0xBF); // next 6 bits, with high bit set
1309       *p++ = (char)((sc | 0x80) & 0xBF); // next 6 bits, with high bit set
1310       ++i;
1311     } else {
1312       *p++ = (char)((c >> 12) | 0xE0); // E0 is the 3-byte flag for UTF-8
1313       *p++ = (char)(((c >> 6) | 0x80) & 0xBF); // next 6 bits, with high bit set
1314       *p++ = (char)((c | 0x80) & 0xBF); // next 6 bits, with high bit set
1315     }
1316   }
1317
1318   // Return the result as a C string.
1319   CString result(buffer, p - buffer);
1320   if (buffer != fixedSizeBuffer) {
1321     delete [] buffer;
1322   }
1323   return result;
1324 }
1325
1326 } // namespace KJS