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