JavaScriptCore/kjs/ustring.cpp

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