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