JavaScriptCore/kjs/ustring.cpp

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