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