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