hphp/runtime/base/array-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 #include "hphp/runtime/base/array-data.h"
  17
  18 #include <vector>
  19 #include <array>
  20 #include <tbb/concurrent_unordered_set.h>
  21
  22 #include "hphp/runtime/base/array-common.h"
  23 #include "hphp/runtime/base/array-init.h"
  24 #include "hphp/runtime/base/array-iterator.h"
  25 #include "hphp/runtime/base/array-provenance.h"
  26 #include "hphp/runtime/base/bespoke-array.h"
  27 #include "hphp/runtime/base/builtin-functions.h"
  28 #include "hphp/runtime/base/comparisons.h"
  29 #include "hphp/runtime/base/memory-manager.h"
  30 #include "hphp/runtime/base/memory-manager-defs.h"
  31 #include "hphp/runtime/base/mixed-array.h"
  32 #include "hphp/runtime/base/packed-array.h"
  33 #include "hphp/runtime/base/request-info.h"
  34 #include "hphp/runtime/base/runtime-option.h"
  35 #include "hphp/runtime/base/set-array.h"
  36 #include "hphp/runtime/base/variable-serializer.h"
  37 #include "hphp/runtime/server/memory-stats.h"
  38 #include "hphp/runtime/vm/interp-helpers.h"
  39
  40 #include "hphp/util/exception.h"
  41
  42 #include "hphp/zend/zend-string.h"
  43
  44 namespace HPHP {
  45 ///////////////////////////////////////////////////////////////////////////////
  46
  47 const StaticString
  48   s_InvalidKeysetOperationMsg{"Invalid operation on keyset"},
  49   s_VarrayUnsetMsg{"varrays do not support unsetting non-end elements"},
  50   s_VecUnsetMsg{"Vecs do not support unsetting non-end elements"};
  51 ///////////////////////////////////////////////////////////////////////////////
  52
  53 __thread std::pair<const ArrayData*, size_t> s_cachedHash;
  54
  55 namespace {
  56 static_assert(
  57   sizeof(ArrayData) == 16,
  58   "Performance is sensitive to sizeof(ArrayData)."
  59   " Make sure you changed it with good reason and then update this assert.");
  60
  61 size_t hashArrayPortion(const ArrayData* arr) {
  62   assertx(arr->isVanilla());
  63
  64   auto hash = folly::hash::hash_128_to_64(arr->kind(), arr->isLegacyArray());
  65
  66   IterateKV(
  67     arr,
  68     [&](TypedValue k, TypedValue v) {
  69       assertx(tvIsString(k) || tvIsInt(k));
  70       assertx(IMPLIES(tvIsString(k), val(k).pstr->isStatic()));
  71       hash = folly::hash::hash_combine(
  72         hash,
  73         dt_with_persistence(k.m_type),
  74         k.m_data.num,
  75         v.m_type
  76       );
  77       switch (v.m_type) {
  78         case KindOfNull:
  79           break;
  80         case KindOfBoolean:
  81         case KindOfInt64:
  82         case KindOfDouble:
  83         case KindOfPersistentString:
  84         case KindOfPersistentVec:
  85         case KindOfPersistentDict:
  86         case KindOfPersistentKeyset:
  87           hash = folly::hash::hash_combine(hash, v.m_data.num);
  88           break;
  89         case KindOfLazyClass:
  90           assertx(v.m_data.plazyclass.name()->isStatic());
  91           hash = folly::hash::hash_combine(
  92             hash,
  93             (uintptr_t)v.m_data.plazyclass.name()
  94           );
  95           break;
  96         case KindOfUninit:
  97         case KindOfString:
  98         case KindOfVec:
  99         case KindOfDict:
 100         case KindOfKeyset:
 101         case KindOfObject:
 102         case KindOfResource:
 103         case KindOfRFunc:
 104         case KindOfFunc:
 105         case KindOfClass:
 106         case KindOfClsMeth:
 107         case KindOfRClsMeth:
 108         case KindOfRecord:
 109           always_assert(false);
 110       }
 111     }
 112   );
 113   return hash;
 114 }
 115
 116 bool compareArrayPortion(const ArrayData* ad1, const ArrayData* ad2) {
 117   assertx(ad1->isVanilla());
 118   assertx(ad2->isVanilla());
 119
 120   if (ad1 == ad2) return true;
 121   if (ad1->kind() != ad2->kind()) return false;
 122   if (ad1->size() != ad2->size()) return false;
 123   if (ad1->isLegacyArray() != ad2->isLegacyArray()) return false;
 124
 125   auto const check = [] (const TypedValue& tv1, const TypedValue& tv2) {
 126       if (tv1.m_type != tv2.m_type) {
 127         // String keys from arrays might be KindOfString, even when
 128         // the StringData is static.
 129         if (!isStringType(tv1.m_type) || !isStringType(tv2.m_type)) {
 130           return false;
 131         }
 132         assertx(tv1.m_data.pstr->isStatic());
 133         assertx(tv2.m_data.pstr->isStatic());
 134       }
 135       if (isNullType(tv1.m_type)) return true;
 136       return tv1.m_data.num == tv2.m_data.num;
 137     };
 138
 139   auto equal = true;
 140   ArrayIter iter2{ad2};
 141   IterateKV(
 142     ad1,
 143     [&](TypedValue k, TypedValue v) {
 144       if (!check(k, *iter2.first().asTypedValue()) ||
 145           !check(v, iter2.secondVal())) {
 146         equal = false;
 147         return true;
 148       }
 149       ++iter2;
 150       return false;
 151     }
 152   );
 153   return equal;
 154 }
 155
 156 struct ScalarHash {
 157   size_t operator()(ArrayData* arr) const {
 158     return s_cachedHash.first == arr
 159       ? s_cachedHash.second
 160       : hashArrayPortion(arr);
 161   }
 162   bool operator()(ArrayData* arr1, ArrayData* arr2) const {
 163     return compareArrayPortion(arr1, arr2);
 164   }
 165 };
 166
 167 using ArrayDataMap =
 168   tbb::concurrent_unordered_set<ArrayData*, ScalarHash, ScalarHash>;
 169 ArrayDataMap s_arrayDataMap;
 170
 171 }
 172
 173 size_t loadedStaticArrayCount() {
 174   return s_arrayDataMap.size();
 175 }
 176
 177 ///////////////////////////////////////////////////////////////////////////////
 178
 179 void ArrayData::GetScalarArray(ArrayData** parr) {
 180   auto const base = *parr;
 181   if (base->isStatic()) return;
 182
 183   auto const arr = [&]{
 184     if (base->isVanilla()) return base;
 185     *parr = BespokeArray::ToVanilla(base, "ArrayData::GetScalarArray");
 186     decRefArr(base);
 187     return *parr;
 188   }();
 189
 190   auto const replace = [&] (ArrayData* rep) {
 191     *parr = rep;
 192     decRefArr(arr);
 193     s_cachedHash.first = nullptr;
 194   };
 195
 196   if (arr->empty()) {
 197     return replace([&]{
 198       auto const legacy = arr->isLegacyArray();
 199       switch (arr->toDataType()) {
 200         case KindOfVec:    return ArrayData::CreateVec(legacy);
 201         case KindOfDict:   return ArrayData::CreateDict(legacy);
 202         case KindOfKeyset: return ArrayData::CreateKeyset();
 203         default: always_assert(false);
 204       }
 205     }());
 206   }
 207
 208   arr->onSetEvalScalar();
 209
 210   s_cachedHash.first = arr;
 211   s_cachedHash.second = hashArrayPortion(arr);
 212
 213   auto const lookup = [&] (ArrayData* a) -> ArrayData* {
 214     if (auto const it = s_arrayDataMap.find(a);
 215         it != s_arrayDataMap.end()) {
 216       return *it;
 217     }
 218     return nullptr;
 219   };
 220
 221   if (auto const a = lookup(arr)) return replace(a);
 222
 223   static std::array<std::mutex, 128> s_mutexes;
 224   std::lock_guard<std::mutex> g{
 225     s_mutexes[s_cachedHash.second % s_mutexes.size()]
 226   };
 227
 228   if (auto const a = lookup(arr)) return replace(a);
 229
 230   // We should clear the sampled bit in the new static array regardless of
 231   // whether the input array was sampled, because specializing the input is
 232   // not sufficient to specialize this new static array.
 233   auto const ad = arr->copyStatic();
 234   ad->m_aux16 &= ~kSampledArray;
 235   assertx(ad->isStatic());
 236
 237   // TODO(T68458896): allocSize rounds up to size class, which we shouldn't do.
 238   MemoryStats::LogAlloc(AllocKind::StaticArray, allocSize(ad));
 239
 240   s_cachedHash.first = ad;
 241   assertx(hashArrayPortion(ad) == s_cachedHash.second);
 242
 243   auto const DEBUG_ONLY inserted = s_arrayDataMap.insert(ad).second;
 244   assertx(inserted);
 245   return replace(ad);
 246 }
 247
 248 ArrayData* ArrayData::GetScalarArray(Array&& arr) {
 249   auto a = arr.detach();
 250   GetScalarArray(&a);
 251   return a;
 252 }
 253
 254 ArrayData* ArrayData::GetScalarArray(Variant&& arr) {
 255   assertx(arr.isArray());
 256   auto a = arr.detach().m_data.parr;
 257   GetScalarArray(&a);
 258   return a;
 259 }
 260
 261 //////////////////////////////////////////////////////////////////////
 262
 263 static_assert(ArrayFunctions::NK == ArrayData::ArrayKind::kNumKinds,
 264               "add new kinds here");
 265
 266 #define DISPATCH(entry)                           \
 267   { MixedArray::entry,       /* darray */         \
 268     BespokeArray::entry,     /* bespoke darray */ \
 269     PackedArray::entry,      /* varray */         \
 270     BespokeArray::entry,     /* bespoke varray */ \
 271     MixedArray::entry,       /* dict */           \
 272     BespokeArray::entry,     /* bespoke dict */   \
 273     PackedArray::entry,      /* vec */            \
 274     BespokeArray::entry,     /* bespoke vec */    \
 275     SetArray::entry,         /* keyset */         \
 276     BespokeArray::entry,     /* bespoke keyset */ \
 277   },
 278
 279 /*
 280  * "Copy/grow" semantics:
 281  *
 282  *   Many of the functions that mutate arrays return an ArrayData* and
 283  *   take a boolean parameter called 'copy'.  The semantics of these
 284  *   functions is the following:
 285  *
 286  *   If the `copy' argument is false, a COW is not required for
 287  *   language semantics.  The array may mutate itself in place and
 288  *   return the same pointer, or the array may allocate a new array
 289  *   and return that.  This is called "growing", since it may be used
 290  *   if an array is out of capacity for new elements---but it is also
 291  *   what happens if an array needs to change kinds and can't do that
 292  *   in-place.  If an array grows, the old array pointer may not be
 293  *   used for any more array operations except to eventually call
 294  *   Release---these grown-from arrays are sometimes described as
 295  *   being in "zombie" state.
 296  *
 297  *   If the `copy' argument is true, the returned array must be
 298  *   indistinguishable from an array that did a COW, in terms of the
 299  *   contents of the array.  Whether it is the same pointer value or
 300  *   not is not specified.  Note, for example, that this means an
 301  *   array doesn't have to copy if it was asked to remove an element
 302  *   that doesn't exist.
 303  *
 304  *   When a function with these semantics returns a new array, the new array is
 305  *   already incref'd. In a few cases, an existing array (different than the
 306  *   source array) may be returned. In this case, the array will already be
 307  *   incref'd.
 308  */
 309
 310 const ArrayFunctions g_array_funcs = {
 311   /*
 312    * void Release(ArrayData*)
 313    *
 314    *   Free memory associated with an array.  Generally called when
 315    *   the reference count on an array drops to zero.
 316    */
 317   DISPATCH(Release)
 318
 319   /*
 320    * TypedValue NvGetInt(const ArrayData*, int64_t key)
 321    * TypedValue NvGetStr(const ArrayData*, const StringData*)
 322    *
 323    *   Lookup a value in an array using an int or string key. Returns Uninit if
 324    *   the key is not in the array. This method does not inc-ref the result.
 325    */
 326   DISPATCH(NvGetInt)
 327   DISPATCH(NvGetStr)
 328
 329   /*
 330    * TypedValue GetPosKey(const ArrayData*, ssize_t pos)
 331    * TypedValue GetPosVal(const ArrayData*, ssize_t pos)
 332    *
 333    *   Look up the key or value at a valid iterator position in this array.
 334    *   Both of these methods return the result without inc-ref-ing it.
 335    */
 336   DISPATCH(GetPosKey)
 337   DISPATCH(GetPosVal)
 338
 339   /*
 340    * ArrayData* SetInt(ArrayData*, int64_t key, TypedValue v)
 341    *
 342    *   Set a value in the array for an integer key, with copies / escalation.
 343    *   SetIntMove is equivalent to SetInt, followed by a dec-ref of the value,
 344    *   followed by a dec-ref of the old array (if it was copied or escalated).
 345    */
 346   DISPATCH(SetIntMove)
 347
 348   /*
 349    * ArrayData* SetStr(ArrayData*, StringData*, TypedValue v)
 350    *
 351    *   Set a value in the array for a string key, with copies / escalation.
 352    *   SetStrMove is equivalent to SetStr, followed by a dec-ref of the value,
 353    *   followed by a dec-ref of the old array (if it was copied or escalated).
 354    */
 355   DISPATCH(SetStrMove)
 356
 357   /*
 358    * bool IsVectorData(const ArrayData*)
 359    *
 360    *   Return true if this array is empty, or if it has only contiguous integer
 361    *   keys and the first key is zero.  Determining this may be an O(N)
 362    *   operation.
 363    */
 364   DISPATCH(IsVectorData)
 365
 366   /*
 367    * bool ExistsInt(const ArrayData*, int64_t key)
 368    *
 369    *   Return true iff this array contains an element with the supplied integer
 370    *   key.
 371    */
 372   DISPATCH(ExistsInt)
 373
 374   /*
 375    * bool ExistsStr(const ArrayData*, const StringData*)
 376    *
 377    *   Return true iff this array contains an element with the supplied string
 378    *   key.  The string will not undergo intish-key cast.
 379    */
 380   DISPATCH(ExistsStr)
 381
 382   /*
 383    * arr_lval LvalInt(ArrayData*, int64_t k)
 384    * arr_lval LvalStr(ArrayData*, StringData* key)
 385    *
 386    *   Look up a value in the array by the supplied key, throwing if it doesn't
 387    *   exist, and return a reference to it.  This function has copy/grow
 388    *   semantics.
 389    */
 390   DISPATCH(LvalInt)
 391   DISPATCH(LvalStr)
 392
 393   /*
 394    * ArrayData* RemoveInt(ArrayData*, int64_t key)
 395    *
 396    *   Remove an array element with an integer key, copying or escalating
 397    *   as necessary. If there was no entry for that element, this function
 398    *   will not remove it, but it may still copy the array in that case.
 399    */
 400   DISPATCH(RemoveInt)
 401
 402   /*
 403    * ArrayData* RemoveStr(ArrayData*, const StringData*)
 404    *
 405    *   Remove an array element with a string key, copying or escalating
 406    *   as necessary. If there was no entry for that element, this function
 407    *   will not remove it, but it may still copy the array in that case.
 408    */
 409   DISPATCH(RemoveStr)
 410
 411   /*
 412    * ssize_t IterEnd(const ArrayData*)
 413    *
 414    *   Returns the canonical invalid position for this array.  Note
 415    *   that if elements are added or removed from the array, the value
 416    *   of the array's canonical invalid position may change.
 417    *
 418    * ssize_t IterBegin(const ArrayData*)
 419    *
 420    *   Returns the position of the first element, or the canonical
 421    *   invalid position if this array is empty.
 422    *
 423    * ssize_t IterLast(const ArrayData*)
 424    *
 425    *   Returns the position of the last element, or the canonical
 426    *   invalid position if this array is empty.
 427    */
 428   DISPATCH(IterBegin)
 429   DISPATCH(IterLast)
 430   DISPATCH(IterEnd)
 431
 432   /*
 433    * ssize_t IterAdvance(const ArrayData*, size_t pos)
 434    *
 435    *   Returns the position of the element that comes after pos, or the
 436    *   canonical invalid position if there are no more elements after pos.
 437    *   If pos is the canonical invalid position, this method will return
 438    *   the canonical invalid position.
 439    */
 440   DISPATCH(IterAdvance)
 441
 442   /*
 443    * ssize_t IterRewind(const ArrayData*, size_t pos)
 444    *
 445    *   Returns the position of the element that comes before pos, or the
 446    *   canonical invalid position if there are no elements before pos. If
 447    *   pos is the canonical invalid position, no guarantees are made about
 448    *   what this method returns.
 449    */
 450   DISPATCH(IterRewind)
 451
 452   /*
 453    * ArrayData* EscalateForSort(ArrayData*, SortFunction)
 454    *
 455    *   Must be called before calling any of the sort routines on an
 456    *   array. This gives arrays a chance to change to a kind that
 457    *   supports sorting.
 458    */
 459   DISPATCH(EscalateForSort)
 460
 461   /*
 462    * void Ksort(ArrayData*, int sort_flags, bool ascending)
 463    *
 464    *   Sort an array by its keys, keeping the values associated with
 465    *   their respective keys.
 466    */
 467   DISPATCH(Ksort)
 468
 469   /*
 470    * void Sort(ArrayData*, int sort_flags, bool ascending)
 471    *
 472    *   Sort an array, by values, and then assign new keys to the
 473    *   elements in the resulting array.
 474    */
 475   DISPATCH(Sort)
 476
 477   /*
 478    * void Asort(ArrayData*, int sort_flags, bool ascending)
 479    *
 480    *   Sort an array and maintain index association.  This means sort
 481    *   the array by values, but keep the keys associated with the
 482    *   values they used to be associated with.
 483    */
 484   DISPATCH(Asort)
 485
 486   /*
 487    * bool Uksort(ArrayData*, const Variant&)
 488    *
 489    *   Sort on keys with a user-defined compare function (in the
 490    *   variant argument).  Returns false if the user comparison
 491    *   function modifies the array we are sorting.
 492    */
 493   DISPATCH(Uksort)
 494
 495   /*
 496    * bool Usort(ArrayData*, const Variant&)
 497    *
 498    *   Sort the array by values with a user-defined comparison
 499    *   function (in the variant).  Returns false if the user-defined
 500    *   comparison function modifies the array we are sorting.
 501    */
 502   DISPATCH(Usort)
 503
 504   /*
 505    * bool Uasort(ArrayData*, const Variant&)
 506    *
 507    *   Sort array by values with a user-defined comparison function
 508    *   (in the variant arg), keeping the original indexes associated
 509    *   with the values.  Returns false if the user-defined comparison
 510    *   function modifies the array we are sorting.
 511    */
 512   DISPATCH(Uasort)
 513
 514   /*
 515    * ArrayData* CopyStatic(const ArrayData*)
 516    *
 517    *   Copy an array, allocating the new array with malloc() instead
 518    *   of from the request local allocator.  This function does
 519    *   guarantee the returned array is a new copy, but it may throw a
 520    *   fatal error if this cannot be accomplished.
 521    */
 522   DISPATCH(CopyStatic)
 523
 524   /*
 525    * ArrayData* Append(ArrayData*, TypedValue v);
 526    *
 527    *   Append a new value to the array, with the next available integer key,
 528    *   copying or escalating as necessary. If there is no available integer
 529    *   key, no value is appended, but this method may still copy the array.
 530    *
 531    *   AppendMove is equivalent to calling Append, dec-ref-ing the value,
 532    *   and (if copy or escalation was needed), dec-ref-ing the old array.
 533    */
 534   DISPATCH(AppendMove)
 535
 536   /*
 537    * ArrayData* Pop(ArrayData*, Variant& value);
 538    *
 539    *   Remove the last element from the array and assign it to `value'.  This
 540    *   function may return a new array if it decided to COW due to
 541    *   cowCheck().
 542    */
 543   DISPATCH(Pop)
 544
 545   /*
 546    * void OnSetEvalScalar(ArrayData*)
 547    *
 548    *   Go through an array and call Variant::setEvalScalar on each
 549    *   value, and make all string keys into static strings.
 550    */
 551   DISPATCH(OnSetEvalScalar)
 552 };
 553
 554 #undef DISPATCH
 555
 556 ///////////////////////////////////////////////////////////////////////////////
 557
 558 namespace {
 559
 560 DEBUG_ONLY void assertForCreate(TypedValue name) {
 561   always_assert(isIntType(name.m_type) || isStringType(name.m_type));
 562 }
 563
 564 }
 565
 566 // In general, arrays can contain int-valued-strings, even though plain array
 567 // access converts them to integers.  non-int-string assertions should go
 568 // upstream of the ArrayData api.
 569
 570 bool ArrayData::IsValidKey(TypedValue k) {
 571   return isIntType(k.m_type) ||
 572         (isStringType(k.m_type) && IsValidKey(k.m_data.pstr));
 573 }
 574
 575 bool ArrayData::IsValidKey(const Variant& k) {
 576   return IsValidKey(*k.asTypedValue());
 577 }
 578
 579 bool ArrayData::IsValidKey(const String& k) {
 580   return IsValidKey(k.get());
 581 }
 582
 583 ///////////////////////////////////////////////////////////////////////////////
 584 // reads
 585
 586 ALWAYS_INLINE
 587 bool ArrayData::EqualHelper(const ArrayData* ad1, const ArrayData* ad2,
 588                             bool strict) {
 589   if (ad1 == ad2) return true;
 590   if (ad1->size() != ad2->size()) return false;
 591
 592   // Prevent circular referenced objects/arrays or deep ones.
 593   check_recursion_error();
 594
 595   if (strict) {
 596     for (ArrayIter iter1{ad1}, iter2{ad2}; iter1; ++iter1, ++iter2) {
 597       assertx(iter2);
 598       if (!HPHP::same(iter1.first(), iter2.first()) ||
 599           !tvSame(iter1.secondVal(), iter2.secondVal())) {
 600         return false;
 601       }
 602     }
 603     return true;
 604   } else {
 605     bool equal = true;
 606     IterateKV(
 607       ad1,
 608       [&](TypedValue k, TypedValue v) {
 609         auto const v2 = ad2->get(k);
 610         if (!v2.is_init() || !tvEqual(v, v2)) {
 611           equal = false;
 612           return true;
 613         }
 614         return false;
 615       }
 616     );
 617     return equal;
 618   }
 619 }
 620
 621 ALWAYS_INLINE
 622 int64_t ArrayData::CompareHelper(const ArrayData* ad1, const ArrayData* ad2) {
 623   auto const size1 = ad1->size();
 624   auto const size2 = ad2->size();
 625   if (size1 < size2) return -1;
 626   if (size1 > size2) return 1;
 627
 628   // Prevent circular referenced objects/arrays or deep ones.
 629   check_recursion_error();
 630
 631   int result = 0;
 632   IterateKV(
 633     ad1,
 634     [&](TypedValue k, TypedValue v) {
 635       auto const v2 = ad2->get(k);
 636       if (!v2.is_init()) {
 637         result = 1;
 638         return true;
 639       }
 640       auto const cmp = tvCompare(v, v2);
 641       if (cmp != 0) {
 642         result = cmp;
 643         return true;
 644       }
 645       return false;
 646     }
 647   );
 648
 649   return result;
 650 }
 651
 652 bool ArrayData::Equal(const ArrayData* ad1, const ArrayData* ad2) {
 653   return EqualHelper(ad1, ad2, false);
 654 }
 655
 656 bool ArrayData::NotEqual(const ArrayData* ad1, const ArrayData* ad2) {
 657   return !EqualHelper(ad1, ad2, false);
 658 }
 659
 660 bool ArrayData::Same(const ArrayData* ad1, const ArrayData* ad2) {
 661   return EqualHelper(ad1, ad2, true);
 662 }
 663
 664 bool ArrayData::NotSame(const ArrayData* ad1, const ArrayData* ad2) {
 665   return !EqualHelper(ad1, ad2, true);
 666 }
 667
 668 bool ArrayData::Lt(const ArrayData* ad1, const ArrayData* ad2) {
 669   return CompareHelper(ad1, ad2) < 0;
 670 }
 671
 672 bool ArrayData::Lte(const ArrayData* ad1, const ArrayData* ad2) {
 673   return CompareHelper(ad1, ad2) <= 0;
 674 }
 675
 676 bool ArrayData::Gt(const ArrayData* ad1, const ArrayData* ad2) {
 677   return CompareHelper(ad1, ad2) > 0;
 678 }
 679
 680 bool ArrayData::Gte(const ArrayData* ad1, const ArrayData* ad2) {
 681   return CompareHelper(ad1, ad2) >= 0;
 682 }
 683
 684 int64_t ArrayData::Compare(const ArrayData* ad1, const ArrayData* ad2) {
 685   return CompareHelper(ad1, ad2);
 686 }
 687
 688 bool ArrayData::same(const ArrayData* v2) const {
 689   assertx(v2);
 690
 691   if (toDataType() != v2->toDataType()) {
 692     if (UNLIKELY(checkHACCompare())) {
 693       raiseHackArrCompatArrHackArrCmp();
 694     }
 695     return false;
 696   }
 697
 698   if (!bothVanilla(this, v2)) return Same(this, v2);
 699   if (isVanillaVec())  return PackedArray::VecSame(this, v2);
 700   if (isVanillaDict()) return MixedArray::DictSame(this, v2);
 701   return SetArray::Same(this, v2);
 702 }
 703
 704 ///////////////////////////////////////////////////////////////////////////////
 705 // helpers
 706
 707 void ArrayData::getNotFound(int64_t k) const {
 708   throwOOBArrayKeyException(k, this);
 709 }
 710
 711 void ArrayData::getNotFound(const StringData* k) const {
 712   if (isVecType()) throwInvalidArrayKeyException(k, this);
 713   throwOOBArrayKeyException(k, this);
 714 }
 715
 716 const char* ArrayData::kindToString(ArrayKind kind) {
 717   std::array<const char*, 10> names = {{
 718     "MixedKind",
 719     "BespokeDArrayKind",
 720     "PackedKind",
 721     "BespokeVArrayKind",
 722     "DictKind",
 723     "BespokeDictKind",
 724     "VecKind",
 725     "BespokeVecKind",
 726     "KeysetKind",
 727     "BespokeKeysetKind",
 728   }};
 729   static_assert(names.size() == kNumKinds, "add new kinds here");
 730   return names[kind];
 731 }
 732
 733 namespace {
 734
 735 ////////////////////////////////////////////////////////////////////////////////
 736
 737 std::string describeKeyType(const TypedValue* tv) {
 738   switch (tv->m_type) {
 739   case KindOfUninit:
 740   case KindOfNull:             return "null";
 741   case KindOfBoolean:          return "bool";
 742   case KindOfInt64:            return "int";
 743   case KindOfDouble:           return "double";
 744   case KindOfPersistentString:
 745   case KindOfString:           return "string";
 746   case KindOfPersistentVec:
 747   case KindOfVec:
 748     return val(*tv).parr->isLegacyArray() ? "array" : "vec";
 749   case KindOfPersistentDict:
 750   case KindOfDict:
 751     return val(*tv).parr->isLegacyArray() ? "array" : "dict";
 752   case KindOfPersistentKeyset:
 753   case KindOfKeyset:           return "keyset";
 754
 755   case KindOfResource:
 756     return tv->m_data.pres->data()->o_getClassName().toCppString();
 757
 758   case KindOfObject:
 759     return tv->m_data.pobj->getClassName().get()->toCppString();
 760
 761   case KindOfRecord:
 762     return tv->m_data.prec->record()->name()->toCppString();
 763
 764   case KindOfRFunc:           return "rfunc";
 765   case KindOfFunc:            return "func";
 766   case KindOfClass:           return "class";
 767   case KindOfLazyClass:       return "lclass";
 768   case KindOfClsMeth:         return "clsmeth";
 769   case KindOfRClsMeth:        return "rclsmeth";
 770   }
 771   not_reached();
 772 }
 773
 774 std::string describeKeyValue(TypedValue tv) {
 775   switch (tv.m_type) {
 776   case KindOfPersistentString:
 777   case KindOfString:
 778     return folly::sformat("\"{}\"", tv.m_data.pstr->data());
 779   case KindOfInt64:
 780     return folly::to<std::string>(tv.m_data.num);
 781   case KindOfUninit:
 782   case KindOfNull:
 783   case KindOfBoolean:
 784   case KindOfDouble:
 785   case KindOfPersistentVec:
 786   case KindOfVec:
 787   case KindOfPersistentDict:
 788   case KindOfDict:
 789   case KindOfPersistentKeyset:
 790   case KindOfKeyset:
 791   case KindOfResource:
 792   case KindOfObject:
 793   case KindOfRFunc:
 794   case KindOfFunc:
 795   case KindOfClass:
 796   case KindOfLazyClass:
 797   case KindOfClsMeth:
 798   case KindOfRClsMeth:
 799   case KindOfRecord:
 800     return "<invalid key type>";
 801   }
 802   not_reached();
 803 }
 804
 805 ////////////////////////////////////////////////////////////////////////////////
 806
 807 }
 808
 809 void throwInvalidArrayKeyException(const TypedValue* key, const ArrayData* ad) {
 810   std::pair<const char*, const char*> kind_type = [&]{
 811     if (ad->isVecType()) return std::make_pair("vec", "int");
 812     if (ad->isDictType()) return std::make_pair("dict", "int or string");
 813     assertx(ad->isKeysetType());
 814     return std::make_pair("keyset", "int or string");
 815   }();
 816   SystemLib::throwInvalidArgumentExceptionObject(
 817     folly::sformat(
 818       "Invalid {} key: expected a key of type {}, {} given",
 819       kind_type.first, kind_type.second, describeKeyType(key)
 820     )
 821   );
 822 }
 823
 824 void throwInvalidArrayKeyException(const StringData* key, const ArrayData* ad) {
 825   auto const tv = make_tv<KindOfString>(const_cast<StringData*>(key));
 826   throwInvalidArrayKeyException(&tv, ad);
 827 }
 828
 829 void throwFalseyPromoteException(const char* type) {
 830   SystemLib::throwOutOfBoundsExceptionObject(
 831     folly::sformat("Promoting {} to array", type)
 832   );
 833 }
 834
 835 void throwOOBArrayKeyException(TypedValue key, const ArrayData* ad) {
 836   SystemLib::throwOutOfBoundsExceptionObject(
 837     folly::sformat(
 838       "Out of bounds {} access: invalid index {}",
 839       getDataTypeString(ad->toDataType(), ad->isLegacyArray()).data(),
 840       describeKeyValue(key)
 841     )
 842   );
 843 }
 844
 845 void throwOOBArrayKeyException(int64_t key, const ArrayData* ad) {
 846   throwOOBArrayKeyException(make_tv<KindOfInt64>(key), ad);
 847 }
 848
 849 void throwOOBArrayKeyException(const StringData* key, const ArrayData* ad) {
 850   throwOOBArrayKeyException(
 851     make_tv<KindOfString>(const_cast<StringData*>(key)),
 852     ad
 853   );
 854 }
 855
 856 void throwInvalidKeysetOperation() {
 857   SystemLib::throwInvalidOperationExceptionObject(s_InvalidKeysetOperationMsg);
 858 }
 859
 860 void throwVarrayUnsetException() {
 861   SystemLib::throwInvalidOperationExceptionObject(s_VarrayUnsetMsg);
 862 }
 863
 864 void throwVecUnsetException() {
 865   SystemLib::throwInvalidOperationExceptionObject(s_VecUnsetMsg);
 866 }
 867
 868 ///////////////////////////////////////////////////////////////////////////////
 869
 870 void raiseHackArrCompatArrHackArrCmp() {
 871   raise_hac_compare_notice(Strings::HACKARR_COMPAT_ARR_HACK_ARR_CMP);
 872 }
 873
 874 ///////////////////////////////////////////////////////////////////////////////
 875
 876 ArrayData* ArrayData::toDictIntishCast(bool copy) {
 877   auto const base = toDict(copy);
 878   if (isVecType()) return base;
 879
 880   // Check if we need to intish-cast any string keys.
 881   int64_t i;
 882   auto intish = false;
 883   IterateKV(base, [&](TypedValue k, TypedValue) {
 884     return intish |= tvIsString(k) && val(k).pstr->isStrictlyInteger(i);
 885   });
 886   if (!intish) return base;
 887
 888   if (RO::EvalHackArrCompatIntishCastNotices) {
 889     raise_hackarr_compat_notice("triggered IntishCast for toDictIntishCast");
 890   }
 891
 892   // Create a new, plain PHP array with the casted keys.
 893   auto result = MixedArrayInit(base->size());
 894   IterateKV(base, [&](TypedValue k, TypedValue v) {
 895     result.setUnknownKey<IntishCast::Cast>(tvAsCVarRef(&k), tvAsCVarRef(&v));
 896   });
 897   if (base != this) decRefArr(base);
 898   auto ad = result.create();
 899   if (!isKeysetType()) return ad;
 900
 901   // When keysets are intish-casted, we cast the values, too. Do so in place.
 902   // This case is rare, so we keep the extra checks out of the loop above.
 903   assertx(ad->hasExactlyOneRef());
 904   auto elm = MixedArray::asMixed(ad)->data();
 905   for (auto const end = elm + ad->size(); elm != end; elm++) {
 906     if (tvIsString(elm->data) && elm->hasIntKey()) {
 907       decRefStr(val(elm->data).pstr);
 908       tvCopy(make_tv<KindOfInt64>(elm->intKey()), elm->data);
 909     }
 910   }
 911   return ad;
 912 }
 913
 914 bool ArrayData::intishCastKey(const StringData* key, int64_t& i) const {
 915   if (key->isStrictlyInteger(i)) {
 916     if (RO::EvalHackArrCompatIntishCastNotices) {
 917       raise_hackarr_compat_notice("triggered IntishCast for set");
 918     }
 919     return true;
 920   }
 921   return false;
 922 }
 923
 924 ArrayData* ArrayData::setLegacyArray(bool copy, bool legacy) {
 925   assertx(IMPLIES(cowCheck(), copy));
 926   assertx(isDictType() || isVecType());
 927
 928   if (legacy == isLegacyArray()) return this;
 929
 930   if (!isVanilla()) return BespokeArray::SetLegacyArray(this, copy, legacy);
 931
 932   auto const ad = [&]{
 933     if (!copy) return this;
 934     return isVanillaVec() ? PackedArray::Copy(this) : MixedArray::Copy(this);
 935   }();
 936   ad->setLegacyArrayInPlace(legacy);
 937   return ad;
 938 }
 939
 940 void ArrayData::setLegacyArrayInPlace(bool legacy) {
 941   assertx(hasExactlyOneRef());
 942   if (legacy) {
 943     m_aux16 |= kLegacyArray;
 944   } else {
 945     m_aux16 &= ~kLegacyArray;
 946   }
 947 }
 948
 949 ///////////////////////////////////////////////////////////////////////////////
 950
 951 ArrayData* ArrayData::toVec(bool copy) {
 952   assertx(IMPLIES(cowCheck(), copy));
 953   if (isVecType()) return this;
 954
 955   if (empty()) return ArrayData::CreateVec();
 956   VecInit init{size()};
 957   IterateV(this, [&](auto v) { init.append(v); });
 958   return init.create();
 959 }
 960
 961 ArrayData* ArrayData::toDict(bool copy) {
 962   assertx(IMPLIES(cowCheck(), copy));
 963   if (isDictType()) return this;
 964
 965   if (empty()) return ArrayData::CreateDict();
 966   DictInit init{size()};
 967   IterateKV(this, [&](auto k, auto v) { init.setValidKey(k, v); });
 968   return init.create();
 969 }
 970
 971 ArrayData* ArrayData::toKeyset(bool copy) {
 972   assertx(IMPLIES(cowCheck(), copy));
 973   if (isKeysetType()) return this;
 974   if (empty()) return ArrayData::CreateKeyset();
 975   KeysetInit init{size()};
 976   IterateV(this, [&](auto v) { init.add(v); });
 977   return init.create();
 978 }
 979
 980 ///////////////////////////////////////////////////////////////////////////////
 981
 982 }