hphp/runtime/base/bespoke/monotype-vec.cpp

   1 /*
   2
   3   +----------------------------------------------------------------------+
   4   | HipHop for PHP                                                       |
   5   +----------------------------------------------------------------------+
   6   | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   7   +----------------------------------------------------------------------+
   8   | This source file is subject to version 3.01 of the PHP license,      |
   9   | that is bundled with this package in the file LICENSE, and is        |
  10   | available through the world-wide-web at the following url:           |
  11   | http://www.php.net/license/3_01.txt                                  |
  12   | If you did not receive a copy of the PHP license and are unable to   |
  13   | obtain it through the world-wide-web, please send a note to          |
  14   | license@php.net so we can mail you a copy immediately.               |
  15   +----------------------------------------------------------------------+
  16 */
  17
  18 #include "hphp/runtime/base/bespoke/monotype-vec.h"
  19
  20 #include "hphp/runtime/base/bespoke/entry-types.h"
  21 #include "hphp/runtime/base/array-init.h"
  22 #include "hphp/runtime/base/memory-manager.h"
  23 #include "hphp/runtime/base/mixed-array-defs.h"
  24 #include "hphp/runtime/base/type-variant.h"
  25 #include "hphp/runtime/base/tv-refcount.h"
  26
  27 #include "hphp/runtime/vm/jit/type.h"
  28
  29 #include "hphp/util/word-mem.h"
  30
  31 namespace HPHP { namespace bespoke {
  32
  33 namespace {
  34
  35 //////////////////////////////////////////////////////////////////////////////
  36
  37 uint16_t packSizeIndexAndAuxBits(uint8_t idx, uint8_t aux) {
  38   return (static_cast<uint16_t>(idx) << 8) | aux;
  39 }
  40
  41 inline constexpr uint32_t sizeClassParams2MonotypeVecCapacity(
  42   size_t index,
  43   size_t lg_grp,
  44   size_t lg_delta,
  45   size_t ndelta
  46 ) {
  47   static_assert(sizeof(MonotypeVec) <=
  48                 kSizeIndex2Size[MonotypeVec::kMinSizeIndex]);
  49
  50   if (index < MonotypeVec::kMinSizeIndex) return 0;
  51   return (((size_t{1} << lg_grp) + (ndelta << lg_delta)) - sizeof(MonotypeVec))
  52       / sizeof(Value);
  53 }
  54
  55 alignas(64) constexpr uint32_t kSizeIndex2MonotypeVecCapacity[] = {
  56 #define SIZE_CLASS(index, lg_grp, lg_delta, ndelta, lg_delta_lookup, ncontig) \
  57   sizeClassParams2MonotypeVecCapacity(index, lg_grp, lg_delta, ndelta),
  58   SIZE_CLASSES
  59 #undef SIZE_CLASS
  60 };
  61
  62 //////////////////////////////////////////////////////////////////////////////
  63
  64 }
  65
  66 //////////////////////////////////////////////////////////////////////////////
  67 // Static initialization
  68 //////////////////////////////////////////////////////////////////////////////
  69
  70 namespace {
  71
  72 using StaticVec = std::aligned_storage<sizeof(EmptyMonotypeVec), 16>::type;
  73
  74 StaticVec s_emptyMonotypeVec;
  75 StaticVec s_emptyMonotypeVArray;
  76 StaticVec s_emptyMonotypeVecMarked;
  77 StaticVec s_emptyMonotypeVArrayMarked;
  78
  79 static_assert(sizeof(DataType) == 1);
  80 constexpr LayoutIndex kBaseLayoutIndex = {1 << 9};
  81 auto const s_monotypeVecVtable = fromArray<MonotypeVec>();
  82 auto const s_emptyMonotypeVecVtable = fromArray<EmptyMonotypeVec>();
  83
  84 constexpr DataType kEmptyDataType = static_cast<DataType>(1);
  85 constexpr DataType kAbstractDataTypeMask = static_cast<DataType>(0x80);
  86
  87 constexpr LayoutIndex getLayoutIndex(DataType type) {
  88   return LayoutIndex{uint16_t(kBaseLayoutIndex.raw + uint8_t(type))};
  89 }
  90
  91 constexpr LayoutIndex getEmptyLayoutIndex() {
  92   auto constexpr offset = (1 << 8);
  93   return LayoutIndex{uint16_t(kBaseLayoutIndex.raw) + offset};
  94 }
  95
  96 Layout::LayoutSet getAllEmptyOrMonotypeVecLayouts() {
  97   Layout::LayoutSet result;
  98 #define DT(name, value) {                                   \
  99     auto const type = KindOf##name;                         \
 100     if (type == dt_modulo_persistence(type)) {              \
 101       result.insert(EmptyOrMonotypeVecLayout::Index(type)); \
 102     }                                                       \
 103   }
 104   DATATYPES
 105 #undef DT
 106   return result;
 107 }
 108
 109 LayoutIndex getMonotypeParentLayout(DataType dt) {
 110   if (!hasPersistentFlavor(dt) || isRefcountedType(dt)) {
 111     return EmptyOrMonotypeVecLayout::Index(dt_modulo_persistence(dt));
 112   }
 113
 114   return MonotypeVecLayout::Index(dt_modulo_persistence(dt));
 115 }
 116
 117 }
 118
 119 //////////////////////////////////////////////////////////////////////////////
 120 // EmptyMonotypeVec
 121 //////////////////////////////////////////////////////////////////////////////
 122
 123 EmptyMonotypeVec* EmptyMonotypeVec::As(ArrayData* ad) {
 124   auto const ead = reinterpret_cast<EmptyMonotypeVec*>(ad);
 125   assertx(ead->checkInvariants());
 126   return ead;
 127 }
 128
 129 const EmptyMonotypeVec* EmptyMonotypeVec::As(const ArrayData* ad) {
 130   return EmptyMonotypeVec::As(const_cast<ArrayData*>(ad));
 131 }
 132
 133 EmptyMonotypeVec* EmptyMonotypeVec::GetVec(bool legacy) {
 134   auto const src = legacy ? &s_emptyMonotypeVecMarked : &s_emptyMonotypeVec;
 135   return reinterpret_cast<EmptyMonotypeVec*>(src);
 136 }
 137
 138 EmptyMonotypeVec* EmptyMonotypeVec::GetVArray(bool legacy) {
 139   auto const src = legacy ? &s_emptyMonotypeVArrayMarked
 140                           : &s_emptyMonotypeVArray;
 141   return reinterpret_cast<EmptyMonotypeVec*>(src);
 142 }
 143
 144 bool EmptyMonotypeVec::checkInvariants() const {
 145   assertx(isStatic());
 146   assertx(kindIsValid());
 147   assertx(size() == 0);
 148   assertx(isVecType() || isVArray());
 149   assertx(layoutIndex() == getEmptyLayoutIndex());
 150
 151   return true;
 152 }
 153
 154 size_t EmptyMonotypeVec::HeapSize(const EmptyMonotypeVec* ead) {
 155   return sizeof(EmptyMonotypeVec);
 156 }
 157
 158 void EmptyMonotypeVec::Scan(const EmptyMonotypeVec* ead, type_scan::Scanner&) {
 159 }
 160
 161 ArrayData* EmptyMonotypeVec::EscalateToVanilla(const EmptyMonotypeVec* ead,
 162                                                const char* reason) {
 163   auto const legacy = ead->isLegacyArray();
 164   return ead->isVecType()
 165     ? (legacy ? staticEmptyMarkedVec() : staticEmptyVec())
 166     : (legacy ? staticEmptyMarkedVArray() : staticEmptyVArray());
 167 }
 168
 169 void EmptyMonotypeVec::ConvertToUncounted(EmptyMonotypeVec*,
 170                                           DataWalker::PointerMap*) {
 171 }
 172
 173 void EmptyMonotypeVec::ReleaseUncounted(EmptyMonotypeVec* ead) {
 174 }
 175
 176 void EmptyMonotypeVec::Release(EmptyMonotypeVec* ead) {
 177   // All EmptyMonotypeVecs are static, and should therefore never be released.
 178   always_assert(false);
 179 }
 180
 181 bool EmptyMonotypeVec::IsVectorData(const EmptyMonotypeVec*) {
 182   return true;
 183 }
 184
 185 TypedValue EmptyMonotypeVec::NvGetInt(const EmptyMonotypeVec*, int64_t) {
 186   return make_tv<KindOfUninit>();
 187 }
 188
 189 TypedValue EmptyMonotypeVec::NvGetStr(const EmptyMonotypeVec*,
 190                                     const StringData*) {
 191   return make_tv<KindOfUninit>();
 192 }
 193
 194 TypedValue EmptyMonotypeVec::GetPosKey(const EmptyMonotypeVec*, ssize_t) {
 195   always_assert(false);
 196 }
 197
 198 TypedValue EmptyMonotypeVec::GetPosVal(const EmptyMonotypeVec*, ssize_t) {
 199   always_assert(false);
 200 }
 201
 202 ssize_t EmptyMonotypeVec::GetIntPos(const EmptyMonotypeVec* ead, int64_t k) {
 203   return 0;
 204 }
 205
 206 ssize_t EmptyMonotypeVec::GetStrPos(const EmptyMonotypeVec* ead,
 207                                     const StringData*) {
 208   return ead->size();
 209 }
 210
 211 arr_lval EmptyMonotypeVec::LvalInt(EmptyMonotypeVec* ead, int64_t k) {
 212   throwOOBArrayKeyException(k, ead);
 213 }
 214
 215 arr_lval EmptyMonotypeVec::LvalStr(EmptyMonotypeVec* ead, StringData* k) {
 216   throwInvalidArrayKeyException(k, ead);
 217 }
 218
 219 tv_lval EmptyMonotypeVec::ElemInt(
 220     tv_lval lval, int64_t k, bool throwOnMissing) {
 221   if (throwOnMissing) throwOOBArrayKeyException(k, lval.val().parr);
 222   return const_cast<TypedValue*>(&immutable_null_base);
 223 }
 224
 225 tv_lval EmptyMonotypeVec::ElemStr(
 226     tv_lval lval, StringData* k, bool throwOnMissing) {
 227   if (throwOnMissing) throwInvalidArrayKeyException(k, lval.val().parr);
 228   return const_cast<TypedValue*>(&immutable_null_base);
 229 }
 230
 231 ArrayData* EmptyMonotypeVec::SetInt(EmptyMonotypeVec* eadIn, int64_t k,
 232                                     TypedValue) {
 233   throwOOBArrayKeyException(k, eadIn);
 234 }
 235
 236 ArrayData* EmptyMonotypeVec::SetStr(EmptyMonotypeVec* eadIn, StringData* k,
 237                                     TypedValue) {
 238   throwInvalidArrayKeyException(k, eadIn);
 239 }
 240
 241 ArrayData* EmptyMonotypeVec::SetIntMove(EmptyMonotypeVec* eadIn, int64_t k,
 242                                         TypedValue) {
 243   throwOOBArrayKeyException(k, eadIn);
 244 }
 245
 246 ArrayData* EmptyMonotypeVec::SetStrMove(EmptyMonotypeVec* eadIn, StringData* k,
 247                                         TypedValue) {
 248   throwInvalidArrayKeyException(k, eadIn);
 249 }
 250
 251 ArrayData* EmptyMonotypeVec::RemoveInt(EmptyMonotypeVec* eadIn, int64_t) {
 252   return eadIn;
 253 }
 254
 255 ArrayData* EmptyMonotypeVec::RemoveStr(EmptyMonotypeVec* eadIn,
 256                                        const StringData*) {
 257   return eadIn;
 258 }
 259
 260 ssize_t EmptyMonotypeVec::IterBegin(const EmptyMonotypeVec*) {
 261   return 0;
 262 }
 263
 264 ssize_t EmptyMonotypeVec::IterLast(const EmptyMonotypeVec*) {
 265   return 0;
 266 }
 267
 268 ssize_t EmptyMonotypeVec::IterEnd(const EmptyMonotypeVec*) {
 269   return 0;
 270 }
 271
 272 ssize_t EmptyMonotypeVec::IterAdvance(const EmptyMonotypeVec*, ssize_t) {
 273   return 0;
 274 }
 275
 276 ssize_t EmptyMonotypeVec::IterRewind(const EmptyMonotypeVec*, ssize_t pos) {
 277   return 0;
 278 }
 279
 280 ArrayData* EmptyMonotypeVec::Append(EmptyMonotypeVec* ead, TypedValue v) {
 281   auto const mad = MonotypeVec::MakeReserve(
 282       ead->m_kind, ead->isLegacyArray(), 1, type(v));
 283   auto const res = MonotypeVec::Append(mad, v);
 284   assertx(mad == res);
 285   return res;
 286 }
 287
 288 ArrayData* EmptyMonotypeVec::AppendMove(EmptyMonotypeVec* ead, TypedValue v) {
 289   auto const mad = MonotypeVec::MakeReserve(
 290       ead->m_kind, ead->isLegacyArray(), 1, type(v));
 291   auto const res = MonotypeVec::AppendMove(mad, v);
 292   assertx(mad == res);
 293   return res;
 294 }
 295
 296 ArrayData* EmptyMonotypeVec::Pop(EmptyMonotypeVec* ead, Variant& value) {
 297   value = uninit_null();
 298   return ead;
 299 }
 300
 301 ArrayData* EmptyMonotypeVec::ToDVArray(EmptyMonotypeVec* eadIn, bool copy) {
 302   assertx(copy);
 303   assertx(eadIn->isVecType());
 304   return GetVArray(eadIn->isLegacyArray());
 305 }
 306
 307 ArrayData* EmptyMonotypeVec::ToHackArr(EmptyMonotypeVec* eadIn, bool copy) {
 308   assertx(copy);
 309   assertx(eadIn->isVArray());
 310   return GetVec(false);
 311 }
 312
 313 ArrayData* EmptyMonotypeVec::PreSort(EmptyMonotypeVec* ead, SortFunction sf) {
 314   always_assert(false);
 315 }
 316
 317 ArrayData* EmptyMonotypeVec::PostSort(EmptyMonotypeVec* ead, ArrayData* vad) {
 318   always_assert(false);
 319 }
 320
 321 ArrayData* EmptyMonotypeVec::SetLegacyArray(EmptyMonotypeVec* eadIn,
 322                                             bool copy, bool legacy) {
 323   if (eadIn->isVecType()) {
 324     return GetVec(legacy);
 325   } else {
 326     assertx(eadIn->isVArray());
 327     return GetVArray(legacy);
 328   }
 329 }
 330
 331
 332 //////////////////////////////////////////////////////////////////////////////
 333 // MonotypeVec
 334 //////////////////////////////////////////////////////////////////////////////
 335
 336 template <typename CountableFn, typename MaybeCountableFn>
 337 void MonotypeVec::forEachCountableValue(CountableFn c, MaybeCountableFn mc) {
 338   auto const dt = type();
 339   if (isRefcountedType(dt)) {
 340     if (hasPersistentFlavor(dt)) {
 341       for (auto i = 0; i < m_size; i++) {
 342         mc(dt, valueRefUnchecked(i).pcnt);
 343       }
 344     } else {
 345       for (auto i = 0; i < m_size; i++) {
 346         c(dt, reinterpret_cast<Countable*>(valueRefUnchecked(i).pcnt));
 347       }
 348     }
 349   }
 350 }
 351
 352 void MonotypeVec::decRefValues() {
 353   forEachCountableValue(
 354     [&](auto t, auto v) { if (v->decReleaseCheck()) destructorForType(t)(v); },
 355     [&](auto t, auto v) { if (v->decReleaseCheck()) destructorForType(t)(v); }
 356   );
 357 }
 358
 359 void MonotypeVec::incRefValues() {
 360   forEachCountableValue(
 361     [&](auto t, auto v) { v->incRefCount(); },
 362     [&](auto t, auto v) { v->incRefCount(); }
 363   );
 364 }
 365
 366 template <bool Static>
 367 MonotypeVec* MonotypeVec::MakeReserve(
 368     HeaderKind hk, bool legacy, uint32_t capacity, DataType dt) {
 369   auto const bytes = sizeof(MonotypeVec) + capacity * sizeof(Value);
 370   auto const index = std::max(MemoryManager::size2Index(bytes), kMinSizeIndex);
 371   auto const alloc = [&]{
 372     if (!Static) return tl_heap->objMallocIndex(index);
 373     auto const size = MemoryManager::sizeIndex2Size(index);
 374     return RO::EvalLowStaticArrays ? low_malloc(size) : uncounted_malloc(size);
 375   }();
 376
 377   auto const mad = static_cast<MonotypeVec*>(alloc);
 378   auto const aux = packSizeIndexAndAuxBits(
 379       index, legacy ? ArrayData::kLegacyArray : 0);
 380
 381   mad->initHeader_16(hk, OneReference, aux);
 382   mad->setLayoutIndex(getLayoutIndex(dt));
 383   mad->m_size = 0;
 384
 385   assertx(mad->checkInvariants());
 386   return mad;
 387 }
 388
 389 MonotypeVec* MonotypeVec::MakeFromVanilla(ArrayData* ad, DataType dt) {
 390   assertx(ad->hasVanillaPackedLayout());
 391   auto const kind = ad->isVArray() ? HeaderKind::BespokeVArray
 392                                    : HeaderKind::BespokeVec;
 393   auto result = ad->isStatic()
 394     ? MakeReserve<true>(kind, ad->isLegacyArray(), ad->size(), dt)
 395     : MakeReserve<false>(kind, ad->isLegacyArray(), ad->size(), dt);
 396
 397   PackedArray::IterateVNoInc(ad, [&](auto v) {
 398     auto const next = Append(result, v);
 399     assertx(result == next);
 400     result = As(next);
 401   });
 402
 403   if (ad->isStatic()) {
 404     auto const aux = packSizeIndexAndAuxBits(
 405       result->sizeIndex(), result->auxBits());
 406     result->initHeader_16(kind, StaticValue, aux);
 407   }
 408
 409   assertx(result->checkInvariants());
 410   return result;
 411 }
 412
 413 Value* MonotypeVec::rawData() {
 414   return reinterpret_cast<Value*>(this + 1);
 415 }
 416
 417 const Value* MonotypeVec::rawData() const {
 418   return const_cast<MonotypeVec*>(this)->rawData();
 419 }
 420
 421 Value& MonotypeVec::valueRefUnchecked(uint32_t idx) {
 422   return rawData()[idx];
 423 }
 424
 425 const Value& MonotypeVec::valueRefUnchecked(uint32_t idx) const {
 426   return const_cast<MonotypeVec*>(this)->valueRefUnchecked(idx);
 427 }
 428
 429 TypedValue MonotypeVec::typedValueUnchecked(uint32_t idx) const {
 430   return make_tv_of_type(valueRefUnchecked(idx), type());
 431 }
 432
 433 uint8_t MonotypeVec::sizeIndex() const {
 434   return m_aux16 >> 8;
 435 }
 436
 437 size_t MonotypeVec::capacity() const {
 438   return kSizeIndex2MonotypeVecCapacity[sizeIndex()];
 439 }
 440
 441 MonotypeVec* MonotypeVec::copyHelper(uint8_t newSizeIndex, bool incRef) const {
 442   auto const mad =
 443     static_cast<MonotypeVec*>(tl_heap->objMallocIndex(newSizeIndex));
 444
 445   // Copy elements 16 bytes at a time. We may copy an extra value this way,
 446   // but our heap allocations are in multiples of 16 bytes, so it is safe.
 447   assertx(HeapSize(this) % 16 == 0);
 448   auto const bytes = sizeof(MonotypeVec) + m_size * sizeof(Value);
 449   memcpy16_inline(mad, this, size_t(bytes + 15) & ~size_t(15));
 450
 451   mad->initHeader_16(m_kind, OneReference,
 452                      packSizeIndexAndAuxBits(newSizeIndex, auxBits()));
 453
 454   if (incRef) mad->incRefValues();
 455
 456   return mad;
 457 }
 458
 459 MonotypeVec* MonotypeVec::copy() const {
 460   return copyHelper(sizeIndex(), true);
 461 }
 462
 463 MonotypeVec* MonotypeVec::grow() {
 464   auto const cow = cowCheck();
 465   auto const mad = copyHelper(sizeIndex() + kSizeClassesPerDoubling, cow);
 466   if (!cow) m_size = 0;
 467   return mad;
 468 }
 469
 470 DataType MonotypeVec::type() const {
 471   return DataType(int8_t(m_extra_hi16 & 0xff));
 472 }
 473
 474 MonotypeVec* MonotypeVec::prepareForInsert() {
 475   if (m_size == capacity()) return grow();
 476   if (cowCheck()) return copy();
 477   return this;
 478 }
 479
 480 /*
 481  * Escalates the MonotypeVec to a vanilla PackedArray with the contents of the
 482  * current array and the specified capacity. The new array will match the
 483  * MonotypeVec in size, contents, and legacy bit status.
 484  */
 485 ArrayData* MonotypeVec::escalateWithCapacity(size_t capacity) const {
 486   assertx(capacity >= size());
 487   auto const ad = isVecType() ? PackedArray::MakeReserveVec(capacity)
 488                               : PackedArray::MakeReserveVArray(capacity);
 489   for (uint32_t i = 0; i < size(); i++) {
 490     auto const tv = typedValueUnchecked(i);
 491     tvCopy(tv, PackedArray::LvalUncheckedInt(ad, i));
 492     tvIncRefGen(tv);
 493   }
 494   ad->setLegacyArrayInPlace(isLegacyArray());
 495   ad->m_size = size();
 496   return ad;
 497 }
 498
 499 bool MonotypeVec::checkInvariants() const {
 500   assertx(kindIsValid());
 501   assertx(isVecType() || isVArray());
 502   assertx(size() <= capacity());
 503   assertx(sizeIndex() >= kMinSizeIndex);
 504   assertx(layoutIndex() != getEmptyLayoutIndex());
 505   assertx(layoutIndex() == getLayoutIndex(type()));
 506   assertx(isRealType(type()));
 507   if (size() > 0) {
 508     assertx(tvIsPlausible(typedValueUnchecked(0)));
 509   }
 510
 511   return true;
 512 }
 513
 514 MonotypeVec* MonotypeVec::As(ArrayData* ad) {
 515   auto const mad = reinterpret_cast<MonotypeVec*>(ad);
 516   assertx(mad->checkInvariants());
 517   return mad;
 518 }
 519
 520 const MonotypeVec* MonotypeVec::As(const ArrayData* ad) {
 521   auto const mad = reinterpret_cast<const MonotypeVec*>(ad);
 522   assertx(mad->checkInvariants());
 523   return mad;
 524 }
 525
 526 size_t MonotypeVec::HeapSize(const MonotypeVec* mad) {
 527   return MemoryManager::sizeIndex2Size(mad->sizeIndex());
 528 }
 529
 530 void MonotypeVec::Scan(const MonotypeVec* mad, type_scan::Scanner& scan) {
 531   if (isRefcountedType(mad->type())) {
 532     static_assert(sizeof(MaybeCountable*) == sizeof(Value));
 533     scan.scan(mad->rawData()->pcnt, mad->size() * sizeof(Value));
 534   }
 535 }
 536
 537 ArrayData* MonotypeVec::EscalateToVanilla(const MonotypeVec* mad,
 538                                           const char* reason) {
 539   return mad->escalateWithCapacity(mad->size());
 540 }
 541
 542 void MonotypeVec::ConvertToUncounted(MonotypeVec* madIn,
 543                                      DataWalker::PointerMap* seen) {
 544   auto const oldType = madIn->type();
 545   for (uint32_t i = 0; i < madIn->size(); i++) {
 546     DataType dt = oldType;
 547     auto const lval = tv_lval(&dt, &madIn->rawData()[i]);
 548     ConvertTvToUncounted(lval, seen);
 549     assertx(equivDataTypes(dt, madIn->type()));
 550   }
 551   auto const newType = hasPersistentFlavor(oldType)
 552     ? dt_with_persistence(oldType)
 553     : oldType;
 554   madIn->setLayoutIndex(getLayoutIndex(newType));
 555 }
 556
 557 void MonotypeVec::ReleaseUncounted(MonotypeVec* mad) {
 558   for (uint32_t i = 0; i < mad->size(); i++) {
 559     auto tv = mad->typedValueUnchecked(i);
 560     ReleaseUncountedTv(&tv);
 561   }
 562 }
 563
 564 void MonotypeVec::Release(MonotypeVec* mad) {
 565   mad->fixCountForRelease();
 566   assertx(mad->isRefCounted());
 567   assertx(mad->hasExactlyOneRef());
 568   mad->decRefValues();
 569   tl_heap->objFreeIndex(mad, mad->sizeIndex());
 570 }
 571
 572 bool MonotypeVec::IsVectorData(const MonotypeVec* mad) {
 573   return true;
 574 }
 575
 576 TypedValue MonotypeVec::NvGetInt(const MonotypeVec* mad, int64_t k) {
 577   if (size_t(k) >= mad->size()) return make_tv<KindOfUninit>();
 578   return mad->typedValueUnchecked(k);
 579 }
 580
 581 TypedValue MonotypeVec::NvGetStr(const MonotypeVec* mad, const StringData*) {
 582   return make_tv<KindOfUninit>();
 583 }
 584
 585 TypedValue MonotypeVec::GetPosKey(const MonotypeVec* mad, ssize_t pos) {
 586   assertx(pos < mad->size());
 587   return make_tv<KindOfInt64>(pos);
 588 }
 589
 590 TypedValue MonotypeVec::GetPosVal(const MonotypeVec* mad, ssize_t pos) {
 591   assertx(size_t(pos) < mad->size());
 592   return mad->typedValueUnchecked(pos);
 593 }
 594
 595 ssize_t MonotypeVec::GetIntPos(const MonotypeVec* mad, int64_t k) {
 596   return LIKELY(size_t(k) < mad->size()) ? k : mad->size();
 597 }
 598
 599 ssize_t MonotypeVec::GetStrPos(const MonotypeVec* mad, const StringData*) {
 600   return mad->size();
 601 }
 602
 603 arr_lval MonotypeVec::LvalInt(MonotypeVec* mad, int64_t k) {
 604   auto const vad = EscalateToVanilla(mad, __func__);
 605   auto const res = vad->lval(k);
 606   assertx(res.arr == vad);
 607   return res;
 608 }
 609
 610 arr_lval MonotypeVec::LvalStr(MonotypeVec* mad, StringData* k) {
 611   throwInvalidArrayKeyException(k, mad);
 612 }
 613
 614 arr_lval MonotypeVec::elemImpl(int64_t k, bool throwOnMissing) {
 615   if (size_t(k) >= size()) {
 616     if (throwOnMissing) throwOOBArrayKeyException(k, this);
 617     return {this, const_cast<TypedValue*>(&immutable_null_base)};
 618   }
 619
 620   auto const dt = type();
 621   if (dt == KindOfClsMeth) return LvalInt(this, k);
 622
 623   auto const cow = cowCheck();
 624   auto const mad = cow ? copy() : this;
 625   mad->setLayoutIndex(getLayoutIndex(dt_modulo_persistence(dt)));
 626
 627   static_assert(folly::kIsLittleEndian);
 628   auto const type_ptr = reinterpret_cast<DataType*>(&mad->m_extra_hi16);
 629   assertx(*type_ptr == mad->type());
 630   return arr_lval{mad, type_ptr, &mad->valueRefUnchecked(k)};
 631 }
 632
 633 tv_lval MonotypeVec::ElemInt(tv_lval lvalIn, int64_t k, bool throwOnMissing) {
 634   auto const madIn = As(lvalIn.val().parr);
 635   auto const lval = madIn->elemImpl(k, throwOnMissing);
 636   if (lval.arr != madIn) {
 637     lvalIn.type() = dt_with_rc(lvalIn.type());
 638     lvalIn.val().parr = lval.arr;
 639     if (madIn->decReleaseCheck()) Release(madIn);
 640   }
 641   return lval;
 642 }
 643
 644 tv_lval MonotypeVec::ElemStr(tv_lval lval, StringData* k, bool throwOnMissing) {
 645   if (throwOnMissing) throwInvalidArrayKeyException(k, lval.val().parr);
 646   return const_cast<TypedValue*>(&immutable_null_base);
 647 }
 648
 649 template <bool Move>
 650 ArrayData* MonotypeVec::setIntImpl(int64_t k, TypedValue v) {
 651   assertx(cowCheck() || notCyclic(v));
 652
 653   if (UNLIKELY(size_t(k) >= size())) {
 654     throwOOBArrayKeyException(k, this);
 655   }
 656
 657   auto const dt = type();
 658   if (!equivDataTypes(dt, v.type())) {
 659     auto const vad = EscalateToVanilla(this, __func__);
 660     auto const res = vad->set(k, v);
 661     assertx(vad == res);
 662     if constexpr (Move) {
 663       if (decReleaseCheck()) Release(this);
 664       tvDecRefGen(v);
 665     }
 666     return res;
 667   }
 668
 669   if constexpr (!Move) {
 670     tvIncRefGen(v);
 671   }
 672   auto const cow = cowCheck();
 673   auto const mad = cow ? copy() : this;
 674   if (dt != v.type()) {
 675     mad->setLayoutIndex(getLayoutIndex(dt_with_rc(dt)));
 676   }
 677   mad->valueRefUnchecked(k) = val(v);
 678   if constexpr (Move) {
 679     if (cow && decReleaseCheck()) Release(this);
 680   }
 681   return mad;
 682 }
 683
 684 ArrayData* MonotypeVec::SetInt(MonotypeVec* madIn, int64_t k, TypedValue v) {
 685   return madIn->setIntImpl<false>(k, v);
 686 }
 687
 688 ArrayData* MonotypeVec::SetIntMove(MonotypeVec* madIn, int64_t k, TypedValue v) {
 689   return madIn->setIntImpl<true>(k, v);
 690 }
 691
 692 ArrayData* MonotypeVec::SetStr(MonotypeVec* madIn, StringData* k, TypedValue) {
 693   throwInvalidArrayKeyException(k, madIn);
 694 }
 695
 696 ArrayData* MonotypeVec::SetStrMove(MonotypeVec* madIn, StringData* k, TypedValue) {
 697   throwInvalidArrayKeyException(k, madIn);
 698 }
 699
 700 ArrayData* MonotypeVec::RemoveInt(MonotypeVec* madIn, int64_t k) {
 701   if (UNLIKELY(size_t(k) >= madIn->m_size)) return madIn;
 702   if (LIKELY(size_t(k) + 1 == madIn->m_size)) {
 703     auto const mad = madIn->cowCheck() ? madIn->copy() : madIn;
 704     mad->m_size--;
 705     tvDecRefGen(mad->typedValueUnchecked(mad->m_size));
 706     return mad;
 707   }
 708
 709   if (madIn->isVecType()) {
 710     throwVecUnsetException();
 711   } else {
 712     throwVarrayUnsetException();
 713   }
 714 }
 715
 716 ArrayData* MonotypeVec::RemoveStr(MonotypeVec* madIn, const StringData*) {
 717   return madIn;
 718 }
 719
 720 ssize_t MonotypeVec::IterBegin(const MonotypeVec* mad) {
 721   return 0;
 722 }
 723
 724 ssize_t MonotypeVec::IterLast(const MonotypeVec* mad) {
 725   return mad->size() > 0 ? mad->size() - 1 : 0;
 726 }
 727
 728 ssize_t MonotypeVec::IterEnd(const MonotypeVec* mad) {
 729   return mad->size();
 730 }
 731
 732 ssize_t MonotypeVec::IterAdvance(const MonotypeVec* mad, ssize_t pos) {
 733   return pos < mad->size() ? pos + 1 : pos;
 734 }
 735
 736 ssize_t MonotypeVec::IterRewind(const MonotypeVec* mad, ssize_t pos) {
 737   return pos > 0 ? pos - 1 : mad->size();
 738 }
 739
 740 template <bool Move>
 741 ArrayData* MonotypeVec::appendImpl(TypedValue v) {
 742   auto const dt = type();
 743   if (!equivDataTypes(dt, v.type())) {
 744     auto const ad = escalateWithCapacity(size() + 1);
 745     auto const result = PackedArray::Append(ad, v);
 746     assertx(ad == result);
 747     return result;
 748   }
 749
 750   auto const mad = prepareForInsert();
 751   if (dt != v.type()) {
 752     mad->setLayoutIndex(getLayoutIndex(dt_with_rc(dt)));
 753   }
 754   mad->valueRefUnchecked(mad->m_size++) = val(v);
 755
 756   if constexpr (Move) {
 757     if (mad != this && decReleaseCheck()) Release(this);
 758   } else {
 759     tvIncRefGen(v);
 760   }
 761
 762   return mad;
 763 }
 764
 765 ArrayData* MonotypeVec::Append(MonotypeVec* madIn, TypedValue v) {
 766   return madIn->appendImpl<false>(v);
 767 }
 768
 769 ArrayData* MonotypeVec::AppendMove(MonotypeVec* madIn, TypedValue v) {
 770   return madIn->appendImpl<true>(v);
 771 }
 772
 773 ArrayData* MonotypeVec::Pop(MonotypeVec* madIn, Variant& value) {
 774   auto const mad = madIn->cowCheck() ? madIn->copy() : madIn;
 775   if (UNLIKELY(mad->m_size) == 0) {
 776     value = uninit_null();
 777     return mad;
 778   }
 779
 780   auto const newSize = mad->size() - 1;
 781   value = Variant::attach(mad->typedValueUnchecked(newSize));
 782   mad->m_size = newSize;
 783
 784   return mad;
 785 }
 786
 787 ArrayData* MonotypeVec::ToDVArray(MonotypeVec* madIn, bool copy) {
 788   if (madIn->isVArray()) return madIn;
 789   auto const mad = copy ? madIn->copy() : madIn;
 790   mad->m_kind = HeaderKind::BespokeVArray;
 791   assertx(mad->checkInvariants());
 792
 793   return mad;
 794 }
 795
 796 ArrayData* MonotypeVec::ToHackArr(MonotypeVec* madIn, bool copy) {
 797   if (madIn->isVecType()) return madIn;
 798   auto const mad = copy ? madIn->copy() : madIn;
 799   mad->setLegacyArrayInPlace(false);
 800   mad->m_kind = HeaderKind::BespokeVec;
 801   assertx(mad->checkInvariants());
 802
 803   return mad;
 804 }
 805
 806 ArrayData* MonotypeVec::PreSort(MonotypeVec* mad, SortFunction sf) {
 807   return mad->escalateWithCapacity(mad->size());
 808 }
 809
 810 ArrayData* MonotypeVec::PostSort(MonotypeVec* mad, ArrayData* vad) {
 811   auto const result = MakeFromVanilla(vad, mad->type());
 812   PackedArray::Release(vad);
 813   return result;
 814 }
 815
 816 ArrayData* MonotypeVec::SetLegacyArray(MonotypeVec* madIn,
 817                                        bool copy, bool legacy) {
 818   auto const mad = copy ? madIn->copy() : madIn;
 819   mad->setLegacyArrayInPlace(legacy);
 820   return mad;
 821 }
 822
 823 //////////////////////////////////////////////////////////////////////////////
 824
 825 using namespace jit;
 826
 827 std::pair<Type, bool> EmptyMonotypeVecLayout::elemType(Type key) const {
 828   return {TBottom, false};
 829 }
 830
 831 std::pair<Type, bool> EmptyMonotypeVecLayout::firstLastType(
 832     bool isFirst, bool isKey) const {
 833   return {TBottom, false};
 834 }
 835
 836 Type EmptyMonotypeVecLayout::iterPosType(Type pos, bool isKey) const {
 837   return TBottom;
 838 }
 839
 840 std::pair<Type, bool> MonotypeVecLayout::elemType(Type key) const {
 841   return {Type(m_fixedType), false};
 842 }
 843
 844 std::pair<Type, bool> MonotypeVecLayout::firstLastType(
 845     bool isFirst, bool isKey) const {
 846   return {isKey ? TInt : Type(m_fixedType), false};
 847 }
 848
 849 Type MonotypeVecLayout::iterPosType(Type pos, bool isKey) const {
 850   return isKey ? TInt : Type(m_fixedType);
 851 }
 852
 853
 854 std::pair<Type, bool> EmptyOrMonotypeVecLayout::elemType(Type key) const {
 855   return {Type(m_fixedType), false};
 856 }
 857
 858 std::pair<Type, bool> EmptyOrMonotypeVecLayout::firstLastType(
 859     bool isFirst, bool isKey) const {
 860   return {isKey ? TInt : Type(m_fixedType), false};
 861 }
 862
 863 Type EmptyOrMonotypeVecLayout::iterPosType(Type pos, bool isKey) const {
 864   return isKey ? TInt : Type(m_fixedType);
 865 }
 866
 867 //////////////////////////////////////////////////////////////////////////////
 868 // Layout creation and usage API
 869 //////////////////////////////////////////////////////////////////////////////
 870
 871 void MonotypeVec::InitializeLayouts() {
 872   auto const base = Layout::ReserveIndices(1 << 9);
 873   always_assert(base == kBaseLayoutIndex);
 874
 875   new TopMonotypeVecLayout();
 876
 877 #define DT(name, value) {                      \
 878     auto const type = KindOf##name;            \
 879     if (type == dt_modulo_persistence(type)) { \
 880       new EmptyOrMonotypeVecLayout(type);      \
 881     }                                          \
 882   }
 883   DATATYPES
 884 #undef DT
 885
 886   new EmptyMonotypeVecLayout();
 887
 888   // Create all the potentially internal concrete layouts first
 889 #define DT(name, value) {                      \
 890     auto const type = KindOf##name;            \
 891     if (type == dt_modulo_persistence(type)) { \
 892       new MonotypeVecLayout(type);             \
 893     }                                          \
 894   }
 895   DATATYPES
 896 #undef DT
 897
 898 #define DT(name, value) {                      \
 899     auto const type = KindOf##name;            \
 900     if (type != dt_modulo_persistence(type)) { \
 901       new MonotypeVecLayout(type);             \
 902     }                                          \
 903   }
 904   DATATYPES
 905 #undef DT
 906
 907   auto const init = [&](EmptyMonotypeVec* ead, HeaderKind hk, bool legacy) {
 908     auto const aux =
 909       packSizeIndexAndAuxBits(0, legacy ? ArrayData::kLegacyArray : 0);
 910     ead->initHeader_16(hk, StaticValue, aux);
 911     ead->m_size = 0;
 912     ead->setLayoutIndex(getEmptyLayoutIndex());
 913     assertx(ead->checkInvariants());
 914   };
 915
 916   init(EmptyMonotypeVec::GetVec(false), HeaderKind::BespokeVec, false);
 917   init(EmptyMonotypeVec::GetVArray(false), HeaderKind::BespokeVArray, false);
 918   init(EmptyMonotypeVec::GetVec(true), HeaderKind::BespokeVec, true);
 919   init(EmptyMonotypeVec::GetVArray(true), HeaderKind::BespokeVArray, true);
 920 }
 921
 922 TopMonotypeVecLayout::TopMonotypeVecLayout()
 923   : AbstractLayout(
 924       Index(), "MonotypeVec<Top>",
 925       {AbstractLayout::GetBespokeTopIndex()})
 926 {}
 927
 928 LayoutIndex TopMonotypeVecLayout::Index() {
 929   auto const t = int8_t(kEmptyDataType) ^ int8_t(kAbstractDataTypeMask);
 930   return MonotypeVecLayout::Index(static_cast<DataType>(t));
 931 }
 932
 933 EmptyOrMonotypeVecLayout::EmptyOrMonotypeVecLayout(DataType type)
 934   : AbstractLayout(
 935       Index(type), folly::sformat("MonotypeVec<Empty|{}>", tname(type)),
 936       {TopMonotypeVecLayout::Index()}),
 937     m_fixedType(type)
 938 {}
 939
 940 LayoutIndex EmptyOrMonotypeVecLayout::Index(DataType type) {
 941   assertx(type == dt_modulo_persistence(type));
 942   auto const t = int8_t(type) ^ int8_t(kAbstractDataTypeMask);
 943   return MonotypeVecLayout::Index(static_cast<DataType>(t));
 944 }
 945
 946 EmptyMonotypeVecLayout::EmptyMonotypeVecLayout()
 947   : ConcreteLayout(
 948       Index(), "MonotypeVec<Empty>", &s_emptyMonotypeVecVtable,
 949       {getAllEmptyOrMonotypeVecLayouts()})
 950 {}
 951
 952 LayoutIndex EmptyMonotypeVecLayout::Index() {
 953   return getEmptyLayoutIndex();
 954 }
 955
 956 MonotypeVecLayout::MonotypeVecLayout(DataType type)
 957   : ConcreteLayout(
 958       Index(type),
 959       folly::sformat("MonotypeVec<{}>", tname(type)),
 960       &s_monotypeVecVtable,
 961       {getMonotypeParentLayout(type)})
 962   , m_fixedType(type)
 963 {}
 964
 965 LayoutIndex MonotypeVecLayout::Index(DataType type) {
 966   return getLayoutIndex(type);
 967 }
 968
 969 bool isMonotypeVecLayout(LayoutIndex index) {
 970   return kBaseLayoutIndex.raw <= index.raw &&
 971          index.raw < 2 * kBaseLayoutIndex.raw;
 972 }
 973
 974 }}