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