hphp/runtime/base/string-data.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/runtime/base/string-data.h"
  18
  19 #include <cmath>
  20 #include <utility>
  21
  22 #include "hphp/runtime/base/tv-conv-notice.h"
  23 #include "hphp/util/alloc.h"
  24 #include "hphp/util/safe-cast.h"
  25 #include "hphp/util/stack-trace.h"
  26
  27 #include "hphp/runtime/base/apc-handle-defs.h"
  28 #include "hphp/runtime/base/apc-string.h"
  29 #include "hphp/runtime/base/builtin-functions.h"
  30 #include "hphp/runtime/base/exceptions.h"
  31 #include "hphp/runtime/base/runtime-error.h"
  32 #include "hphp/runtime/base/runtime-option.h"
  33 #include "hphp/runtime/base/tv-uncounted.h"
  34 #include "hphp/runtime/base/zend-functions.h"
  35 #include "hphp/runtime/base/zend-string.h"
  36 #include "hphp/runtime/ext/apc/ext_apc.h"
  37
  38 #include "hphp/runtime/vm/unit-emitter.h"
  39
  40 #include "hphp/zend/zend-strtod.h"
  41
  42 namespace HPHP {
  43
  44 TRACE_SET_MOD(isame);
  45
  46 //////////////////////////////////////////////////////////////////////
  47
  48 bool isame_log(const StringData* input, const StringData* arg) {
  49   FTRACE(1, "isame collision {} != {}\n", input->slice(), arg->slice());
  50   auto const rate = RO::EvalIsameCollisionSampleRate;
  51   if (StructuredLog::coinflip(rate)) {
  52     StructuredLogEntry sample;
  53     sample.force_init = true;
  54     sample.setInt("sample_rate", rate);
  55     sample.setStr("lhs", input->slice());
  56     sample.setStr("rhs", arg->slice());
  57     StackTrace st(StackTrace::Force{});
  58     sample.setStackTrace("stack", st);
  59     StructuredLog::log("hhvm_isame_collisions", sample);
  60   }
  61   return true;
  62 }
  63
  64 NEVER_INLINE void raiseStringLengthExceededError(size_t len) {
  65   raise_error("String length exceeded: %zu > %u", len, StringData::MaxSize);
  66 }
  67
  68 // Allocate, initialize `m_data' and HeapObject, but not `m_lenAndHash'.
  69 ALWAYS_INLINE StringData* allocFlat(size_t len) {
  70   if (UNLIKELY(len > StringData::MaxSize)) {
  71     raiseStringLengthExceededError(len);
  72   }
  73   auto const sizeIndex = MemoryManager::size2Index(len + kStringOverhead);
  74   auto sd = static_cast<StringData*>(tl_heap->objMallocIndex(sizeIndex));
  75   // Refcount initialized to 1.
  76   sd->initHeader_16(HeaderKind::String, OneReference, sizeIndex);
  77   assertx(sd->capacity() >= len);
  78   return sd;
  79 }
  80
  81 //////////////////////////////////////////////////////////////////////
  82
  83 std::aligned_storage<
  84   kStringOverhead,
  85   alignof(StringData)
  86 >::type s_theEmptyString;
  87
  88 //////////////////////////////////////////////////////////////////////
  89
  90 namespace {
  91 std::atomic<bool> s_symbols_loaded;
  92
  93 SymbolPrefix* getSymbolPrefix(StringData* sd) {
  94   assertx(sd->isSymbol());
  95   return reinterpret_cast<SymbolPrefix*>(sd) - 1;
  96 }
  97 const SymbolPrefix* getSymbolPrefix(const StringData* sd) {
  98   assertx(sd->isSymbol());
  99   return getSymbolPrefix(const_cast<StringData*>(sd));
 100 }
 101 }
 102
 103 bool StringData::isSymbol() const {
 104   return (m_aux16 >> 8) & kIsSymbolMask;
 105 }
 106
 107 void StringData::markSymbolsLoaded() {
 108   s_symbols_loaded.store(true, std::memory_order_release);
 109 }
 110
 111 Class* StringData::getCachedClass() const {
 112   return getSymbolPrefix(this)->cls;
 113 }
 114
 115 NamedEntity* StringData::getNamedEntity() const {
 116   return getSymbolPrefix(this)->ne;
 117 }
 118
 119 void StringData::setCachedClass(Class* cls) {
 120   auto const prefix = getSymbolPrefix(this);
 121   assertx(IMPLIES(prefix->cls, prefix->cls == cls));
 122   prefix->cls = cls;
 123 }
 124
 125 void StringData::setNamedEntity(NamedEntity* ne) {
 126   auto const prefix = getSymbolPrefix(this);
 127   assertx(IMPLIES(prefix->ne, prefix->ne == ne));
 128   prefix->ne = ne;
 129 }
 130
 131 ptrdiff_t StringData::isSymbolOffset() {
 132   return offsetof(StringData, m_aux16) + 1;
 133 }
 134
 135 ptrdiff_t StringData::cachedClassOffset() {
 136   return offsetof(SymbolPrefix, cls) - sizeof(SymbolPrefix);
 137 }
 138
 139 //////////////////////////////////////////////////////////////////////
 140
 141 ptrdiff_t StringData::colorOffset() {
 142   return offsetof(StringData, m_aux16);
 143 }
 144
 145 uint16_t StringData::color() const {
 146   return m_aux16 & kColorMask;
 147 }
 148
 149 void StringData::setColor(uint16_t color) {
 150   assertx((color & ~kColorMask) == 0);
 151   m_aux16 |= color;
 152 }
 153
 154 //////////////////////////////////////////////////////////////////////
 155
 156 // Create either a static or an uncounted string.
 157 // Difference between static and uncounted is in the lifetime
 158 // of the string. Static are alive for the lifetime of the process.
 159 // Uncounted are not ref counted but will be deleted at some point.
 160 template <bool trueStatic> ALWAYS_INLINE
 161 MemBlock StringData::AllocateShared(folly::StringPiece sl) {
 162   if (UNLIKELY(sl.size() > StringData::MaxSize)) {
 163     raiseStringLengthExceededError(sl.size());
 164   }
 165
 166   auto const symbol =
 167     trueStatic && !s_symbols_loaded.load(std::memory_order_acquire);
 168
 169   auto const extra = symbol ? sizeof(SymbolPrefix) : 0;
 170   auto const bytes = sl.size() + kStringOverhead + extra;
 171   auto const ptr = trueStatic ? static_alloc(bytes) : AllocUncounted(bytes);
 172   return MemBlock{ptr, bytes};
 173 }
 174
 175 template <bool trueStatic> ALWAYS_INLINE
 176 StringData* StringData::MakeSharedAt(folly::StringPiece sl, MemBlock range) {
 177   assertx(range.size >= sl.size() + kStringOverhead);
 178   auto const symbol = trueStatic &&
 179     !s_symbols_loaded.load(std::memory_order_acquire) &&
 180     (range.size >= sl.size() + kStringOverhead + sizeof(SymbolPrefix));
 181   auto const extra = symbol ? sizeof(SymbolPrefix) : 0;
 182   StringData* sd = reinterpret_cast<StringData*>(
 183     reinterpret_cast<uintptr_t>(range.ptr) + extra
 184   );
 185   auto const data = reinterpret_cast<char*>(sd + 1);
 186
 187   auto const count = trueStatic ? StaticValue : UncountedValue;
 188   if (symbol) {
 189     auto constexpr aux = kIsSymbolMask << 8 | kInvalidColor;
 190     sd->initHeader_16(HeaderKind::String, count, aux);
 191     getSymbolPrefix(sd)->cls = nullptr;
 192     getSymbolPrefix(sd)->ne = nullptr;
 193   } else {
 194     sd->initHeader_16(HeaderKind::String, count, kInvalidColor);
 195   }
 196   sd->m_len = sl.size(); // m_hash is computed soon.
 197
 198   data[sl.size()] = 0;
 199   auto const mcret = memcpy(data, sl.data(), sl.size());
 200   auto const ret = reinterpret_cast<StringData*>(mcret) - 1;
 201   // Recalculating ret from mcret avoids a spill.
 202   ret->preCompute();                    // get m_hash right
 203
 204   assertx(ret == sd);
 205   assertx(trueStatic ? ret->isStatic() : ret->isUncounted());
 206   assertx(ret->isSymbol() == symbol);
 207   assertx(ret->checkSane());
 208   return ret;
 209 }
 210
 211 StringData* StringData::MakeStaticAt(folly::StringPiece sl, MemBlock range) {
 212   return MakeSharedAt<true>(sl, range);
 213 }
 214
 215 StringData* StringData::MakeStatic(folly::StringPiece sl) {
 216   assertx(StaticString::s_globalInit);
 217   return MakeStaticAt(sl, AllocateShared<true>(sl));
 218 }
 219
 220 StringData* StringData::MakeUncounted(folly::StringPiece sl) {
 221   return MakeSharedAt<false>(sl, AllocateShared<false>(sl));
 222 }
 223
 224 StringData* StringData::MakeEmpty() {
 225   return MakeStaticAt(folly::StringPiece{""},
 226                       MemBlock{&s_theEmptyString, sizeof(s_theEmptyString)});
 227 }
 228
 229 void StringData::destructStatic() {
 230   assertx(checkSane() && isStatic());
 231   if (isSymbol()) {
 232     static_try_free(reinterpret_cast<SymbolPrefix*>(this) - 1,
 233                     size() + kStringOverhead + sizeof(SymbolPrefix));
 234   } else {
 235     static_try_free(this, size() + kStringOverhead);
 236   }
 237 }
 238
 239 void StringData::ReleaseUncounted(StringData* str) {
 240   assertx(str->checkSane());
 241   assertx(!str->uncountedCowCheck());
 242   FreeUncounted(str, str->size() + kStringOverhead);
 243 }
 244
 245 //////////////////////////////////////////////////////////////////////
 246
 247 StringData* StringData::Make(const StringData* s, CopyStringMode) {
 248   auto const sd = allocFlat(s->m_len);
 249   sd->m_lenAndHash = s->m_lenAndHash;
 250   auto const data = static_cast<void*>(sd + 1);
 251   *memcpy8(data, s->data(), s->m_len) = 0;
 252
 253   assertx(sd->same(s));
 254   return sd;
 255 }
 256
 257 StringData* StringData::Make(folly::StringPiece sl, CopyStringMode) {
 258   auto const sd = allocFlat(sl.size());
 259   sd->m_lenAndHash = sl.size(); // hash=0
 260   auto const data = reinterpret_cast<char*>(sd + 1);
 261
 262   data[sl.size()] = 0;
 263   auto const mcret = memcpy(data, sl.data(), sl.size());
 264   auto const ret = reinterpret_cast<StringData*>(mcret) - 1;
 265   // Recalculating ret from mcret avoids a spill.
 266
 267   assertx(ret == sd);
 268   assertx(ret->m_len == sl.size());
 269   assertx(ret->hasExactlyOneRef());
 270   assertx(ret->m_hash == 0);
 271   assertx(ret->checkSane());
 272   return ret;
 273 }
 274
 275 StringData* StringData::Make(const char* data, size_t len, CopyStringMode) {
 276   if (UNLIKELY(len > StringData::MaxSize)) {
 277     raiseStringLengthExceededError(len);
 278   }
 279
 280   return Make(folly::StringPiece(data, len), CopyString);
 281 }
 282
 283 StringData* StringData::Make(size_t reserveLen) {
 284   auto const sd = allocFlat(reserveLen);
 285   sd->setSize(0);
 286
 287   assertx(sd->hasExactlyOneRef());
 288   assertx(sd->checkSane());
 289   return sd;
 290 }
 291
 292 StringData* StringData::Make() {
 293   return Make(SmallStringReserve);
 294 }
 295
 296 //////////////////////////////////////////////////////////////////////
 297
 298 StringData* StringData::Make(char* data, size_t len, AttachStringMode) {
 299   if (UNLIKELY(len > StringData::MaxSize)) {
 300     raiseStringLengthExceededError(len);
 301   }
 302   auto const sd = Make(folly::StringPiece(data, len), CopyString);
 303   free(data);
 304   assertx(sd->checkSane());
 305   return sd;
 306 }
 307
 308 StringData* StringData::Make(folly::StringPiece r1, folly::StringPiece r2) {
 309   // Undefined behavior if we pass nullptr strings into StringData::Make
 310   assertx(r1.data() && r2.data());
 311   auto const len = r1.size() + r2.size();
 312   auto const sd = allocFlat(len);
 313   sd->m_lenAndHash = len; // hash=0
 314
 315   auto const data = reinterpret_cast<char*>(sd + 1);
 316   memcpy(data,             r1.data(), r1.size());
 317   memcpy(data + r1.size(), r2.data(), r2.size());
 318   data[len] = 0;
 319
 320   assertx(sd->hasExactlyOneRef());
 321   assertx(sd->checkSane());
 322   return sd;
 323 }
 324
 325 StringData* StringData::Make(const StringData* s1, const StringData* s2) {
 326   auto const len = s1->m_len + s2->m_len;
 327   // `memcpy8()' could overrun the buffer by at most 7 bytes, so we allocate 6
 328   // more bytes here, which (together with the trailing 0) makes it safe.
 329   auto const sd = allocFlat(len + 6);
 330   sd->m_lenAndHash = len; // hash=0
 331
 332   auto const data = reinterpret_cast<char*>(sd + 1);
 333   auto const next = memcpy8(data, s1->data(), s1->m_len);
 334   *memcpy8(next, s2->data(), s2->m_len) = 0;
 335
 336   assertx(sd->hasExactlyOneRef());
 337   assertx(sd->checkSane());
 338   return sd;
 339 }
 340
 341 StringData* StringData::Make(folly::StringPiece s1, const char* lit2) {
 342   return Make(s1, folly::StringPiece(lit2, strlen(lit2)));
 343 }
 344
 345 StringData* StringData::Make(folly::StringPiece r1, folly::StringPiece r2,
 346                              folly::StringPiece r3) {
 347   auto const len = r1.size() + r2.size() + r3.size();
 348   auto const sd = allocFlat(len);
 349   sd->m_lenAndHash  = len; // hash=0
 350
 351   auto p = reinterpret_cast<char*>(sd + 1);
 352   p = static_cast<char*>(memcpy(p,             r1.data(), r1.size()));
 353   p = static_cast<char*>(memcpy(p + r1.size(), r2.data(), r2.size()));
 354   p = static_cast<char*>(memcpy(p + r2.size(), r3.data(), r3.size()));
 355   p[r3.size()] = 0;
 356
 357   assertx(sd->hasExactlyOneRef());
 358   assertx(sd->checkSane());
 359   return sd;
 360 }
 361
 362 StringData* StringData::Make(folly::StringPiece r1, folly::StringPiece r2,
 363                              folly::StringPiece r3, folly::StringPiece r4) {
 364   auto const len = r1.size() + r2.size() + r3.size() + r4.size();
 365   auto const sd = allocFlat(len);
 366   sd->m_lenAndHash = len; // hash=0
 367
 368   auto p = reinterpret_cast<char*>(sd + 1);
 369   p = static_cast<char*>(memcpy(p,             r1.data(), r1.size()));
 370   p = static_cast<char*>(memcpy(p + r1.size(), r2.data(), r2.size()));
 371   p = static_cast<char*>(memcpy(p + r2.size(), r3.data(), r3.size()));
 372   p = static_cast<char*>(memcpy(p + r3.size(), r4.data(), r4.size()));
 373   p[r4.size()] = 0;
 374
 375   assertx(sd->hasExactlyOneRef());
 376   assertx(sd->checkSane());
 377   return sd;
 378 }
 379
 380 //////////////////////////////////////////////////////////////////////
 381
 382 void StringData::release() noexcept {
 383   fixCountForRelease();
 384   assertx(isRefCounted());
 385   assertx(checkSane());
 386   tl_heap->objFreeIndex(this, m_aux16);
 387   AARCH64_WALKABLE_FRAME();
 388 }
 389
 390 //////////////////////////////////////////////////////////////////////
 391
 392 #define ALIASING_APPEND_ASSERT(ptr, len)                        \
 393   assertx(uintptr_t(ptr) <= uintptr_t(data()) ||                 \
 394          uintptr_t(ptr) >= uintptr_t(data() + capacity() + 1)); \
 395   assertx(ptr != data() || len <= m_len);
 396
 397 StringData* StringData::append(folly::StringPiece range) {
 398   assertx(!hasMultipleRefs());
 399
 400   auto s = range.data();
 401   auto const len = range.size();
 402   if (len == 0) return this;
 403   auto const newLen = size_t(m_len) + size_t(len);
 404
 405   if (UNLIKELY(newLen > MaxSize)) {
 406     raiseStringLengthExceededError(newLen);
 407   }
 408
 409   /*
 410    * We may have an aliasing append.  We don't allow appending with an
 411    * interior pointer, although we may be asked to append less than
 412    * the whole string in an aliasing situation.
 413    */
 414   ALIASING_APPEND_ASSERT(s, len);
 415
 416   auto const requestLen = static_cast<uint32_t>(newLen);
 417   auto const target = reserve(requestLen);
 418   memcpy(target->mutableData() + m_len, s, len);
 419   target->setSize(newLen);
 420   assertx(target->checkSane());
 421
 422   return target;
 423 }
 424
 425 StringData* StringData::append(folly::StringPiece r1, folly::StringPiece r2) {
 426   assertx(!hasMultipleRefs());
 427
 428   auto const len = r1.size() + r2.size();
 429
 430   if (len == 0) return this;
 431   if (UNLIKELY(size_t(m_len) + size_t(len) > MaxSize)) {
 432     raiseStringLengthExceededError(size_t(len) + size_t(m_len));
 433   }
 434
 435   auto const newLen = m_len + len;
 436
 437   /*
 438    * We may have an aliasing append.  We don't allow appending with an
 439    * interior pointer, although we may be asked to append less than
 440    * the whole string in an aliasing situation.
 441    */
 442   ALIASING_APPEND_ASSERT(r1.data(), r1.size());
 443   ALIASING_APPEND_ASSERT(r2.data(), r2.size());
 444   auto const target = reserve(newLen);
 445
 446   /*
 447    * memcpy is safe even if it's a self append---the regions will be
 448    * disjoint, since rN.data() can't point past the start of our source
 449    * pointer, and rN.size() is smaller than the old length.
 450    */
 451   void* p = target->mutableData();
 452   p = memcpy((char*)p + m_len,     r1.data(), r1.size());
 453       memcpy((char*)p + r1.size(), r2.data(), r2.size());
 454
 455   target->setSize(newLen);
 456   assertx(target->checkSane());
 457
 458   return target;
 459 }
 460
 461 StringData* StringData::append(folly::StringPiece r1,
 462                                folly::StringPiece r2,
 463                                folly::StringPiece r3) {
 464   assertx(!hasMultipleRefs());
 465
 466   auto const len = r1.size() + r2.size() + r3.size();
 467
 468   if (len == 0) return this;
 469   if (UNLIKELY(size_t(m_len) + size_t(len) > MaxSize)) {
 470     raiseStringLengthExceededError(size_t(len) + size_t(m_len));
 471   }
 472
 473   auto const newLen = m_len + len;
 474
 475   /*
 476    * We may have an aliasing append.  We don't allow appending with an
 477    * interior pointer, although we may be asked to append less than
 478    * the whole string in an aliasing situation.
 479    */
 480   ALIASING_APPEND_ASSERT(r1.data(), r1.size());
 481   ALIASING_APPEND_ASSERT(r2.data(), r2.size());
 482   ALIASING_APPEND_ASSERT(r3.data(), r3.size());
 483   auto const target = reserve(newLen);
 484
 485   /*
 486    * memcpy is safe even if it's a self append---the regions will be
 487    * disjoint, since rN.data() can't point past the start of our source
 488    * pointer, and rN.size() is smaller than the old length.
 489    */
 490   void* p = target->mutableData();
 491   p = memcpy((char*)p + m_len,     r1.data(), r1.size());
 492   p = memcpy((char*)p + r1.size(), r2.data(), r2.size());
 493       memcpy((char*)p + r2.size(), r3.data(), r3.size());
 494
 495   target->setSize(newLen);
 496   assertx(target->checkSane());
 497
 498   return target;
 499 }
 500
 501 #undef ALIASING_APPEND_ASSERT
 502
 503 //////////////////////////////////////////////////////////////////////
 504
 505 StringData* StringData::reserve(size_t cap) {
 506   assertx(!hasMultipleRefs());
 507
 508   if (cap <= capacity()) return this;
 509
 510   cap = std::min(cap + cap / 4, size_t(MaxSize));
 511   auto const sd = allocFlat(cap);
 512
 513   // Request-allocated StringData are always aligned at 16 bytes, thus it is
 514   // safe to copy in 16-byte groups.
 515   // layout: [header][m_lenAndHash][...data]
 516   sd->m_lenAndHash = m_lenAndHash;
 517   // This copies the characters (m_len bytes), and the trailing zero (1 byte)
 518   memcpy16_inline(sd+1, this+1, (m_len + 1 + 15) & ~0xF);
 519   assertx(reinterpret_cast<uintptr_t>(this+1) % 16 == 0);
 520
 521   assertx(sd->hasExactlyOneRef());
 522   assertx(sd->checkSane());
 523   return sd;
 524 }
 525
 526 StringData* StringData::shrinkImpl(size_t len) {
 527   assertx(!hasMultipleRefs());
 528   assertx(len <= capacity());
 529
 530   auto const sd = allocFlat(len);
 531   sd->m_lenAndHash = len;
 532   auto const src = static_cast<void*>(this + 1);
 533   auto const dst = static_cast<void*>(sd + 1);
 534   *memcpy8(dst, src, len) = 0;
 535
 536   assertx(sd->checkSane());
 537   return sd;
 538 }
 539
 540 void StringData::dump() const {
 541   auto s = slice();
 542
 543   printf("StringData(%d) (%s%s%d): [", m_count,
 544          isStatic() ? "static " : "",
 545          isUncounted() ? "uncounted " : "",
 546          static_cast<int>(s.size()));
 547   for (uint32_t i = 0; i < s.size(); i++) {
 548     char ch = s.data()[i];
 549     if (isprint(ch)) {
 550       printf("%c", ch);
 551     } else {
 552       printf("\\x%02x", ch);
 553     }
 554   }
 555   printf("]\n");
 556 }
 557
 558 StringData* StringData::getChar(int offset) const {
 559   if (offset >= 0 && offset < size()) {
 560     return makeStaticString(data()[offset]);
 561   }
 562   raise_notice("Uninitialized string offset: %d", offset);
 563   return staticEmptyString();
 564 }
 565
 566 StringData* StringData::increment() {
 567   assertx(!hasMultipleRefs());
 568   assertx(!empty());
 569   auto const sd = reserve(m_len + 1);
 570   sd->incrementHelper();
 571   return sd;
 572 }
 573
 574 void StringData::incrementHelper() {
 575   raise_notice("Increment on string '%s'", data());
 576   m_hash = 0;
 577
 578   enum class CharKind {
 579     UNKNOWN,
 580     LOWER_CASE,
 581     UPPER_CASE,
 582     NUMERIC
 583   };
 584
 585   auto const len = m_len;
 586   auto const s = mutableData();
 587   int carry = 0;
 588   int pos = len - 1;
 589   auto last = CharKind::UNKNOWN; // Shut up the compiler warning
 590   int ch;
 591
 592   while (pos >= 0) {
 593     ch = s[pos];
 594     if (ch >= 'a' && ch <= 'z') {
 595       if (ch == 'z') {
 596         s[pos] = 'a';
 597         carry=1;
 598       } else {
 599         s[pos]++;
 600         carry=0;
 601       }
 602       last = CharKind::LOWER_CASE;
 603     } else if (ch >= 'A' && ch <= 'Z') {
 604       if (ch == 'Z') {
 605         s[pos] = 'A';
 606         carry=1;
 607       } else {
 608         s[pos]++;
 609         carry=0;
 610       }
 611       last = CharKind::UPPER_CASE;
 612     } else if (ch >= '0' && ch <= '9') {
 613       if (ch == '9') {
 614         s[pos] = '0';
 615         carry=1;
 616       } else {
 617         s[pos]++;
 618         carry=0;
 619       }
 620       last = CharKind::NUMERIC;
 621     } else {
 622       carry=0;
 623       break;
 624     }
 625     if (carry == 0) {
 626       break;
 627     }
 628     pos--;
 629   }
 630
 631   if (carry) {
 632     if (UNLIKELY(len + 1 > MaxSize)) {
 633       raiseStringLengthExceededError(len + 1);
 634     }
 635
 636     assertx(len + 1 <= capacity());
 637     memmove(s + 1, s, len);
 638     s[len + 1] = '\0';
 639     m_len = len + 1;
 640
 641     switch (last) {
 642     case CharKind::NUMERIC:
 643       s[0] = '1';
 644       break;
 645     case CharKind::UPPER_CASE:
 646       s[0] = 'A';
 647       break;
 648     case CharKind::LOWER_CASE:
 649       s[0] = 'a';
 650       break;
 651     default:
 652       break;
 653     }
 654   }
 655 }
 656
 657 void StringData::preCompute() {
 658   auto s = slice();
 659   m_hash = hash_string_i_unsafe(s.data(), s.size());
 660   assertx(m_hash >= 0);
 661   if (s.size() > 0 &&
 662       (is_numeric_string(s.data(), s.size(), nullptr, nullptr,
 663                          1, nullptr) == KindOfNull)) {
 664     m_hash |= STRHASH_MSB;
 665   }
 666 }
 667
 668 #if !defined(USE_X86_STRING_HELPERS) && !defined(USE_ARM_STRING_HELPERS)
 669 // This function is implemented directly in ASM in string-data-*.S otherwise.
 670 NEVER_INLINE strhash_t StringData::hashHelper() const {
 671   strhash_t h = hash_string_i_unsafe(data(), m_len);
 672   assertx(h >= 0);
 673   m_hash |= h;
 674   return h;
 675 }
 676 #endif
 677
 678 ///////////////////////////////////////////////////////////////////////////////
 679 // type conversions
 680
 681 DataType StringData::isNumericWithVal(int64_t &lval, double &dval,
 682                                       int allow_errors, int* overflow) const {
 683   if (m_hash < 0) return KindOfNull;
 684   DataType ret = KindOfNull;
 685   auto s = slice();
 686   if (s.size()) {
 687     ret = is_numeric_string(
 688       s.data(),
 689       s.size(),
 690       &lval,
 691       &dval,
 692       allow_errors,
 693       overflow
 694     );
 695     if (ret == KindOfNull && allow_errors) {
 696       m_hash |= STRHASH_MSB;
 697     }
 698   }
 699   return ret;
 700 }
 701
 702 bool StringData::isNumeric() const {
 703   if (m_hash < 0) return false;
 704   int64_t lval; double dval;
 705   DataType ret = isNumericWithVal(lval, dval, 0);
 706   switch (ret) {
 707     case KindOfNull:
 708       return false;
 709     case KindOfInt64:
 710     case KindOfDouble:
 711       return true;
 712     case KindOfUninit:
 713     case KindOfBoolean:
 714     case KindOfPersistentString:
 715     case KindOfString:
 716     case KindOfPersistentVec:
 717     case KindOfVec:
 718     case KindOfPersistentDict:
 719     case KindOfDict:
 720     case KindOfPersistentKeyset:
 721     case KindOfKeyset:
 722     case KindOfObject:
 723     case KindOfResource:
 724     case KindOfRFunc:
 725     case KindOfFunc:
 726     case KindOfClass:
 727     case KindOfLazyClass:
 728     case KindOfClsMeth:
 729     case KindOfRClsMeth:
 730       break;
 731   }
 732   not_reached();
 733 }
 734
 735 bool StringData::toBoolean() const {
 736   return !empty() && !isZero();
 737 }
 738
 739 int64_t StringData::toInt64(int base /* = 10 */) const {
 740   return strtoll(data(), nullptr, base);
 741 }
 742
 743 double StringData::toDouble() const {
 744   auto s = slice();
 745   if (s.size()) return zend_strtod(s.data(), nullptr);
 746   return 0;
 747 }
 748
 749 DataType StringData::toNumeric(int64_t &lval, double &dval) const {
 750   if (m_hash < 0) return KindOfString;
 751   DataType ret = isNumericWithVal(lval, dval, 0);
 752   if (ret == KindOfInt64 || ret == KindOfDouble) return ret;
 753   return KindOfString;
 754 }
 755
 756 ///////////////////////////////////////////////////////////////////////////////
 757 // comparisons
 758
 759 bool StringData::equal(const StringData *s) const {
 760   assertx(s);
 761   if (s == this) return true;
 762   return same(s);
 763 }
 764
 765 int StringData::numericCompare(const StringData *v2) const {
 766   assertx(v2);
 767
 768   int oflow1, oflow2;
 769   int64_t lval1, lval2;
 770   double dval1, dval2;
 771   DataType ret1, ret2;
 772   if ((ret1 = isNumericWithVal(lval1, dval1, 0, &oflow1)) == KindOfNull ||
 773       (ret1 == KindOfDouble && !std::isfinite(dval1)) ||
 774       (ret2 = v2->isNumericWithVal(lval2, dval2, 0, &oflow2)) == KindOfNull ||
 775       (ret2 == KindOfDouble && !std::isfinite(dval2))) {
 776     return -2;
 777   }
 778   if (oflow1 && oflow1 == oflow2 && dval1 == dval2) {
 779     return -2; // overflow in same direction, comparison will be inaccurate
 780   }
 781   if (ret1 == KindOfInt64 && ret2 == KindOfInt64) {
 782     if (lval1 > lval2) return 1;
 783     if (lval1 == lval2) return 0;
 784     return -1;
 785   }
 786   if (ret1 == KindOfDouble && ret2 == KindOfDouble) {
 787     if (dval1 > dval2) return 1;
 788     if (dval1 == dval2) return 0;
 789     return -1;
 790   }
 791
 792   if (ret1 == KindOfDouble) {
 793     assertx(ret2 == KindOfInt64);
 794     if (oflow1) {
 795       return oflow1;
 796     }
 797     dval2 = (double)lval2;
 798   } else {
 799     assertx(ret1 == KindOfInt64);
 800     assertx(ret2 == KindOfDouble);
 801     if (oflow2) {
 802       return -oflow2;
 803     }
 804     dval1 = (double)lval1;
 805   }
 806
 807   if (dval1 > dval2) return 1;
 808   if (dval1 == dval2) return 0;
 809   return -1;
 810 }
 811
 812 int StringData::compare(const StringData *v2) const {
 813   assertx(v2);
 814
 815   if (v2 == this) return 0;
 816
 817   int ret = numericCompare(v2);
 818   if (ret < -1) {
 819     int len1 = size();
 820     int len2 = v2->size();
 821     int len = len1 < len2 ? len1 : len2;
 822     ret = memcmp(data(), v2->data(), len);
 823     if (ret) return ret;
 824     if (len1 == len2) return 0;
 825     return len < len1 ? 1 : -1;
 826   }
 827   return ret;
 828 }
 829
 830 StringData*
 831 StringData::substr(int start, int length /* = StringData::MaxSize */) {
 832   if (start < 0 || start >= size() || length <= 0) {
 833     return staticEmptyString();
 834   }
 835
 836   auto const max_len = size() - start;
 837   if (length > max_len) {
 838     length = max_len;
 839   }
 840
 841   assertx(length > 0);
 842   if (UNLIKELY(length == size())) {
 843     incRefCount();
 844     return this;
 845   }
 846   if (UNLIKELY(length == 1)) {
 847     return makeStaticString(data()[start]);
 848   }
 849   return StringData::Make(data() + start, length, CopyString);
 850 }
 851
 852 ///////////////////////////////////////////////////////////////////////////////
 853 // Serialization
 854
 855 __thread UnitEmitter* BlobEncoderHelper<const StringData*>::tl_unitEmitter{nullptr};
 856 __thread Unit* BlobEncoderHelper<const StringData*>::tl_unit{nullptr};
 857
 858 void BlobEncoderHelper<const StringData*>::serde(BlobEncoder& encoder,
 859                                                  const StringData* sd) {
 860   assertx(!tl_unit);
 861   if (auto const ue = tl_unitEmitter) {
 862     Id id = ue->mergeLitstr(sd);
 863     encoder(id);
 864     return;
 865   }
 866   if (!sd) {
 867     encoder(uint32_t(0));
 868     return;
 869   }
 870   auto const sz = sd->size();
 871   encoder(static_cast<uint32_t>(sz + 1));
 872   if (!sz) return;
 873   encoder.writeRaw(sd->data(), sz);
 874 }
 875
 876 void BlobEncoderHelper<const StringData*>::serde(BlobDecoder& decoder,
 877                                                  const StringData*& sd,
 878                                                  bool makeStatic) {
 879   if (auto const ue = tl_unitEmitter) {
 880     Id id;
 881     decoder(id);
 882     sd = ue->lookupLitstr(id);
 883     return;
 884   } else if (auto const u = tl_unit) {
 885     Id id;
 886     decoder(id);
 887     sd = u->lookupLitstrId(id);
 888     return;
 889   }
 890
 891   uint32_t size;
 892   decoder(size);
 893   if (size == 0) {
 894     sd = nullptr;
 895     return;
 896   }
 897   --size;
 898   if (size == 0) {
 899     sd = staticEmptyString();
 900     return;
 901   }
 902
 903   assertx(decoder.remaining() >= size);
 904   auto const data = decoder.data();
 905   sd = makeStatic
 906     ? makeStaticString((const char*)data, size)
 907     : StringData::Make((const char*)data, size, CopyString);
 908   decoder.advance(size);
 909 }
 910
 911 folly::StringPiece
 912 BlobEncoderHelper<const StringData*>::asStringPiece(BlobDecoder& decoder) {
 913   if (auto const ue = tl_unitEmitter) {
 914     Id id;
 915     decoder(id);
 916     auto const sd = ue->lookupLitstr(id);
 917     if (!sd) return { nullptr, size_t{0} };
 918     return sd->slice();
 919   }
 920
 921   uint32_t size;
 922   decoder(size);
 923   if (size == 0) return { (const char*)nullptr, size_t{0} };
 924   auto const data = reinterpret_cast<const char*>(decoder.data());
 925   if (size == 1) return { data, size_t{0} };
 926   --size;
 927   assertx(decoder.remaining() >= size);
 928   decoder.advance(size);
 929   return { data, size };
 930 }
 931
 932 void BlobEncoderHelper<const StringData*>::skip(BlobDecoder& decoder) {
 933   if (auto const ue = tl_unitEmitter) {
 934     Id id;
 935     decoder(id);
 936     return;
 937   }
 938
 939   uint32_t size;
 940   decoder(size);
 941   // Any size less than 2 has no data (0 is a nullptr, and 1 is an
 942   // empty string).
 943   if (size <= 1) return;
 944   --size;
 945   assertx(decoder.remaining() >= size);
 946   decoder.advance(size);
 947 }
 948
 949 size_t BlobEncoderHelper<const StringData*>::peekSize(BlobDecoder& decoder) {
 950   if (auto const ue = tl_unitEmitter) {
 951     auto const before = decoder.advanced();
 952     Id id;
 953     decoder(id);
 954     auto const size = decoder.advanced() - before;
 955     decoder.retreat(size);
 956     return size;
 957   }
 958
 959   auto const before = decoder.advanced();
 960   uint32_t size;
 961   decoder(size);
 962   auto const sizeBytes = decoder.advanced() - before;
 963   decoder.retreat(sizeBytes);
 964   if (size <= 1) return sizeBytes;
 965   --size;
 966   return sizeBytes + size;
 967 }
 968
 969 void BlobEncoderHelper<LowStringPtr>::serde(BlobEncoder& encoder,
 970                                             LowStringPtr s) {
 971   auto const sd = s.get();
 972   encoder(sd);
 973 }
 974
 975 void BlobEncoderHelper<LowStringPtr>::serde(BlobDecoder& decoder,
 976                                             LowStringPtr& s) {
 977   const StringData* sd;
 978   decoder(sd);
 979   s = sd;
 980 }
 981
 982 ///////////////////////////////////////////////////////////////////////////////
 983 // Debug
 984
 985 std::string StringData::toCppString() const {
 986   auto s = slice();
 987   return std::string(s.data(), s.size());
 988 }
 989
 990 bool StringData::checkSane() const {
 991   static_assert(sizeof(StringData) == 16);
 992   static_assert(size_t(MaxSize) <= size_t(INT_MAX), "Beware int wraparound");
 993   static_assert(sizeof(StringData) == SD_DATA, "");
 994   static_assert(offsetof(StringData, m_len) == SD_LEN, "");
 995   static_assert(offsetof(StringData, m_hash) == SD_HASH, "");
 996   assertx(kindIsValid());
 997   assertx(uint32_t(size()) <= MaxSize);
 998   assertx(size() >= 0);
 999   assertx(IMPLIES(isSymbol(), isStatic()));
1000   if (isRefCounted()) {
1001     assertx(size() <= capacity());
1002     assertx(capacity() <= MaxSize);
1003   }
1004   return true;
1005 }
1006
1007 //////////////////////////////////////////////////////////////////////
1008
1009 }