JavaScriptCore/kjs/ustring.cpp

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