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/empty-array.h"
  30 #include "hphp/runtime/base/memory-manager.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/globals-array.h"
  39 #include "hphp/runtime/vm/interp-helpers.h"
  40
  41 #include "hphp/util/exception.h"
  42
  43 #include "hphp/zend/zend-string.h"
  44
  45 namespace HPHP {
  46 ///////////////////////////////////////////////////////////////////////////////
  47
  48 const StaticString
  49   s_InvalidKeysetOperationMsg{"Invalid operation on keyset"},
  50   s_VarrayUnsetMsg{"varrays do not support unsetting non-end elements"},
  51   s_VecUnsetMsg{"Vecs do not support unsetting non-end elements"};
  52 ///////////////////////////////////////////////////////////////////////////////
  53
  54 __thread std::pair<const ArrayData*, size_t> s_cachedHash;
  55
  56 namespace {
  57 static_assert(
  58   sizeof(ArrayData) == 16,
  59   "Performance is sensitive to sizeof(ArrayData)."
  60   " Make sure you changed it with good reason and then update this assert.");
  61
  62 struct ScalarHash {
  63   size_t operator()(const ArrayData* arr) const {
  64     return hash(arr);
  65   }
  66   size_t operator()(const ArrayData* ad1, const ArrayData* ad2) const {
  67     return equal(ad1, ad2);
  68   }
  69   size_t hash(const ArrayData* arr) const {
  70     if (arr == s_cachedHash.first) return s_cachedHash.second;
  71     return raw_hash(arr);
  72   }
  73   size_t raw_hash(const ArrayData* arr, arrprov::Tag tag = {}) const {
  74     auto ret = uint64_t{
  75       arr->isHackArrayType()
  76       ? arr->kind()
  77       : ArrayData::ArrayKind::kMixedKind
  78     };
  79     ret |= (uint64_t{arr->dvArray()} << 32);
  80     ret |= (uint64_t{arr->isLegacyArray()} << 33);
  81
  82     if (RuntimeOption::EvalArrayProvenance) {
  83       if (!tag.valid()) tag = arrprov::getTag(arr);
  84       if (tag.valid()) {
  85         ret = folly::hash::hash_combine(ret, static_cast<int>(tag.kind()));
  86         ret = folly::hash::hash_combine(ret, tag.line());
  87         ret = folly::hash::hash_combine(ret, tag.filename());
  88       }
  89     }
  90     IterateKV(
  91       arr,
  92       [&](TypedValue k, TypedValue v) {
  93         assertx(!isRefcountedType(k.m_type) ||
  94                 (k.m_type == KindOfString && k.m_data.pstr->isStatic()));
  95         assertx(!isRefcountedType(v.m_type));
  96         ret = folly::hash::hash_combine(
  97           ret,
  98           static_cast<int>(k.m_type), k.m_data.num,
  99           static_cast<int>(v.m_type));
 100         switch (v.m_type) {
 101           case KindOfNull:
 102             break;
 103           case KindOfBoolean:
 104           case KindOfInt64:
 105           case KindOfDouble:
 106           case KindOfPersistentString:
 107           case KindOfPersistentDArray:
 108           case KindOfPersistentVArray:
 109           case KindOfPersistentArray:
 110           case KindOfPersistentVec:
 111           case KindOfPersistentDict:
 112           case KindOfPersistentKeyset:
 113             ret = folly::hash::hash_combine(ret, v.m_data.num);
 114             break;
 115           case KindOfUninit:
 116           case KindOfString:
 117           case KindOfDArray:
 118           case KindOfVArray:
 119           case KindOfArray:
 120           case KindOfVec:
 121           case KindOfDict:
 122           case KindOfKeyset:
 123           case KindOfObject:
 124           case KindOfResource:
 125           case KindOfRFunc:
 126           case KindOfFunc:
 127           case KindOfClass:
 128           case KindOfClsMeth:
 129           case KindOfRecord:
 130             always_assert(false);
 131         }
 132       }
 133     );
 134     return ret;
 135   }
 136   bool equal(const ArrayData* ad1, const ArrayData* ad2) const {
 137     if (ad1 == ad2) return true;
 138     if (ad1->size() != ad2->size()) return false;
 139     if (!ArrayData::dvArrayEqual(ad1, ad2)) return false;
 140     if (ad1->isHackArrayType()) {
 141       if (!ad2->isHackArrayType()) return false;
 142       if (ad1->kind() != ad2->kind()) return false;
 143     } else if (ad2->isHackArrayType()) {
 144       return false;
 145     }
 146
 147     if (ad1->isLegacyArray() != ad2->isLegacyArray()) return false;
 148
 149     if (UNLIKELY(RuntimeOption::EvalArrayProvenance) &&
 150         arrprov::getTag(ad1) != arrprov::getTag(ad2)) {
 151       return false;
 152     }
 153
 154     auto check = [] (const TypedValue& tv1, const TypedValue& tv2) {
 155       if (tv1.m_type != tv2.m_type) {
 156         // String keys from arrays might be KindOfString, even when
 157         // the StringData is static.
 158         if (!isStringType(tv1.m_type) || !isStringType(tv2.m_type)) {
 159           return false;
 160         }
 161         assertx(tv1.m_data.pstr->isStatic());
 162       }
 163       if (isNullType(tv1.m_type)) return true;
 164       return tv1.m_data.num == tv2.m_data.num;
 165     };
 166
 167     bool equal = true;
 168     ArrayIter iter2{ad2};
 169     IterateKV(
 170       ad1,
 171       [&](TypedValue k, TypedValue v) {
 172         if (!check(k, *iter2.first().asTypedValue()) ||
 173             !check(v, iter2.secondVal())) {
 174           equal = false;
 175           return true;
 176         }
 177         ++iter2;
 178         return false;
 179       }
 180     );
 181     return equal;
 182   }
 183 };
 184
 185 using ArrayDataMap = tbb::concurrent_unordered_set<ArrayData*,
 186                                                    ScalarHash,
 187                                                    ScalarHash>;
 188 ArrayDataMap s_arrayDataMap;
 189
 190 }
 191
 192 size_t loadedStaticArrayCount() {
 193   return s_arrayDataMap.size();
 194 }
 195
 196 ///////////////////////////////////////////////////////////////////////////////
 197
 198 size_t ArrayData::allocSize() const {
 199   if (hasVanillaMixedLayout()) return MixedArray::asMixed(this)->heapSize();
 200   if (isKeysetKind()) return SetArray::asSet(this)->heapSize();
 201   return PackedArray::heapSize(this);
 202 }
 203
 204 void ArrayData::GetScalarArray(ArrayData** parr, arrprov::Tag tag) {
 205   auto const arr = *parr;
 206   auto const requested_tag = RuntimeOption::EvalArrayProvenance && tag.valid();
 207
 208   if (arr->isStatic() && LIKELY(!requested_tag)) return;
 209
 210   auto replace = [&] (ArrayData* rep) {
 211     *parr = rep;
 212     decRefArr(arr);
 213     s_cachedHash.first = nullptr;
 214   };
 215
 216   if (arr->empty() && LIKELY(!requested_tag)) {
 217     if (arr->isKeysetType())   return replace(staticEmptyKeysetArray());
 218     if (arr->isVArray())       return replace(staticEmptyVArray());
 219     if (arr->isDArray())       return replace(staticEmptyDArray());
 220     if (arr->isVecArrayType()) return replace(staticEmptyVecArray());
 221     if (arr->isDictType())     return replace(staticEmptyDictArray());
 222     return replace(staticEmptyArray());
 223   }
 224
 225   arr->onSetEvalScalar();
 226
 227   s_cachedHash.first = arr;
 228   s_cachedHash.second = ScalarHash{}.raw_hash(arr, tag);
 229
 230   // See documentation for `tl_tag_override`.
 231   auto it = s_arrayDataMap.find(arr);
 232   if (it != s_arrayDataMap.end()) return replace(*it);
 233
 234   static std::array<std::mutex, 128> s_mutexes;
 235
 236   std::lock_guard<std::mutex> g {
 237     s_mutexes[
 238       s_cachedHash.second % s_mutexes.size()
 239     ]
 240   };
 241   it = s_arrayDataMap.find(arr);
 242   if (it != s_arrayDataMap.end()) return replace(*it);
 243
 244   ArrayData* ad;
 245   if (((arr->isMixedKind() && !arr->isDArray()) || arr->isGlobalsArrayKind()) &&
 246       arr->isVectorData()) {
 247     ad = PackedArray::ConvertStatic(arr);
 248   } else {
 249     ad = arr->copyStatic();
 250   }
 251   assertx(ad->isStatic());
 252   MemoryStats::LogAlloc(AllocKind::StaticArray, ad->allocSize());
 253
 254   s_cachedHash.first = ad;
 255   assertx(ScalarHash{}.raw_hash(ad) == s_cachedHash.second);
 256   auto const DEBUG_ONLY inserted = s_arrayDataMap.insert(ad).second;
 257   assertx(inserted);
 258
 259   if (tag.valid()) arrprov::setTag<arrprov::Mode::Emplace>(ad, tag);
 260   return replace(ad);
 261 }
 262
 263 ArrayData* ArrayData::GetScalarArray(Array&& arr) {
 264   auto a = arr.detach();
 265   GetScalarArray(&a);
 266   return a;
 267 }
 268
 269 ArrayData* ArrayData::GetScalarArray(Variant&& arr) {
 270   assertx(arr.isArray());
 271   auto a = arr.detach().m_data.parr;
 272   GetScalarArray(&a);
 273   return a;
 274 }
 275
 276 //////////////////////////////////////////////////////////////////////
 277
 278 static_assert(ArrayFunctions::NK == ArrayData::ArrayKind::kNumKinds,
 279               "add new kinds here");
 280
 281 #define DISPATCH(entry)                         \
 282   { PackedArray::entry,                         \
 283     MixedArray::entry,                          \
 284     EmptyArray::entry,                          \
 285     GlobalsArray::entry,                        \
 286     RecordArray::entry,                         \
 287     MixedArray::entry##Dict,   /* Dict */       \
 288     PackedArray::entry##Vec,   /* Vec */        \
 289     SetArray::entry,           /* Keyset */     \
 290     BespokeArray::entry, /* bespoke array */    \
 291     BespokeArray::entry, /* bespoke dict */     \
 292     BespokeArray::entry, /* bespoke vec */      \
 293     BespokeArray::entry, /* bespoke keyset */   \
 294   },
 295
 296 /*
 297  * "Copy/grow" semantics:
 298  *
 299  *   Many of the functions that mutate arrays return an ArrayData* and
 300  *   take a boolean parameter called 'copy'.  The semantics of these
 301  *   functions is the following:
 302  *
 303  *   If the `copy' argument is false, a COW is not required for
 304  *   language semantics.  The array may mutate itself in place and
 305  *   return the same pointer, or the array may allocate a new array
 306  *   and return that.  This is called "growing", since it may be used
 307  *   if an array is out of capacity for new elements---but it is also
 308  *   what happens if an array needs to change kinds and can't do that
 309  *   in-place.  If an array grows, the old array pointer may not be
 310  *   used for any more array operations except to eventually call
 311  *   Release---these grown-from arrays are sometimes described as
 312  *   being in "zombie" state.
 313  *
 314  *   If the `copy' argument is true, the returned array must be
 315  *   indistinguishable from an array that did a COW, in terms of the
 316  *   contents of the array.  Whether it is the same pointer value or
 317  *   not is not specified.  Note, for example, that this means an
 318  *   array doesn't have to copy if it was asked to remove an element
 319  *   that doesn't exist.
 320  *
 321  *   When a function with these semantics returns a new array, the new array is
 322  *   already incref'd. In a few cases, an existing array (different than the
 323  *   source array) may be returned. In this case, the array will already be
 324  *   incref'd.
 325  */
 326
 327 const ArrayFunctions g_array_funcs = {
 328   /*
 329    * void Release(ArrayData*)
 330    *
 331    *   Free memory associated with an array.  Generally called when
 332    *   the reference count on an array drops to zero.
 333    */
 334   DISPATCH(Release)
 335
 336   /*
 337    * TypedValue NvGetInt(const ArrayData*, int64_t key)
 338    * TypedValue NvGetStr(const ArrayData*, const StringData*)
 339    *
 340    *   Lookup a value in an array using an int or string key. Returns Uninit if
 341    *   the key is not in the array. This method does not inc-ref the result.
 342    */
 343   DISPATCH(NvGetInt)
 344   DISPATCH(NvGetStr)
 345
 346   /*
 347    * ssize_t NvGetIntPos(const ArrayData*, int64_t k)
 348    * ssize_t NvGetStrPos(const ArrayData*, const StringData* k)
 349    *
 350    *   Lookup the position of an int or string key in the array.  Returns the
 351    *   canonical invalid position if the key is not in the array.
 352    */
 353   DISPATCH(NvGetIntPos)
 354   DISPATCH(NvGetStrPos)
 355
 356   /*
 357    * TypedValue GetPosKey(const ArrayData*, ssize_t pos)
 358    * TypedValue GetPosVal(const ArrayData*, ssize_t pos)
 359    *
 360    *   Look up the key or value at a valid iterator position in this array.
 361    *   Both of these methods return the result without inc-ref-ing it.
 362    */
 363   DISPATCH(GetPosKey)
 364   DISPATCH(GetPosVal)
 365
 366   /*
 367    * ArrayData* SetInt(ArrayData*, int64_t key, TypedValue v)
 368    *
 369    *   Set a value in the array for an integer key, with copies / escalation.
 370    *   SetIntMove is equivalent to SetInt, followed by a dec-ref of the value,
 371    *   followed by a dec-ref of the old array (if it was copied or escalated).
 372    */
 373   DISPATCH(SetInt)
 374   DISPATCH(SetIntMove)
 375
 376   /*
 377    * ArrayData* SetStr(ArrayData*, StringData*, TypedValue v)
 378    *
 379    *   Set a value in the array for a string key, with copies / escalation.
 380    *   SetStrMove is equivalent to SetStr, followed by a dec-ref of the value,
 381    *   followed by a dec-ref of the old array (if it was copied or escalated).
 382    */
 383   DISPATCH(SetStr)
 384   DISPATCH(SetStrMove)
 385
 386   /*
 387    * size_t Vsize(const ArrayData*)
 388    *
 389    *   This entry point essentially is only for GlobalsArray;
 390    *   all the other cases are not_reached().
 391    *
 392    *   Because of particulars of how GlobalsArray works,
 393    *   determining the size of the array is an O(N) operation---we set
 394    *   the size field in the generic ArrayData header to -1 in that
 395    *   case and dispatch through this entry point.
 396    */
 397   DISPATCH(Vsize)
 398
 399   /*
 400    * bool IsVectorData(const ArrayData*)
 401    *
 402    *   Return true if this array is empty, or if it has only contiguous integer
 403    *   keys and the first key is zero.  Determining this may be an O(N)
 404    *   operation.
 405    */
 406   DISPATCH(IsVectorData)
 407
 408   /*
 409    * bool ExistsInt(const ArrayData*, int64_t key)
 410    *
 411    *   Return true iff this array contains an element with the supplied integer
 412    *   key.
 413    */
 414   DISPATCH(ExistsInt)
 415
 416   /*
 417    * bool ExistsStr(const ArrayData*, const StringData*)
 418    *
 419    *   Return true iff this array contains an element with the supplied string
 420    *   key.  The string will not undergo intish-key cast.
 421    */
 422   DISPATCH(ExistsStr)
 423
 424   /*
 425    * arr_lval LvalInt(ArrayData*, int64_t k)
 426    * arr_lval LvalStr(ArrayData*, StringData* key)
 427    *
 428    *   Look up a value in the array by the supplied key, throwing if it doesn't
 429    *   exist, and return a reference to it.  This function has copy/grow
 430    *   semantics.
 431    */
 432   DISPATCH(LvalInt)
 433   DISPATCH(LvalStr)
 434
 435   /*
 436    * ArrayData* RemoveInt(ArrayData*, int64_t key)
 437    *
 438    *   Remove an array element with an integer key, copying or escalating
 439    *   as necessary. If there was no entry for that element, this function
 440    *   will not remove it, but it may still copy the array in that case.
 441    */
 442   DISPATCH(RemoveInt)
 443
 444   /*
 445    * ArrayData* RemoveStr(ArrayData*, const StringData*)
 446    *
 447    *   Remove an array element with a string key, copying or escalating
 448    *   as necessary. If there was no entry for that element, this function
 449    *   will not remove it, but it may still copy the array in that case.
 450    */
 451   DISPATCH(RemoveStr)
 452
 453   /*
 454    * ssize_t IterEnd(const ArrayData*)
 455    *
 456    *   Returns the canonical invalid position for this array.  Note
 457    *   that if elements are added or removed from the array, the value
 458    *   of the array's canonical invalid position may change.
 459    *
 460    * ssize_t IterBegin(const ArrayData*)
 461    *
 462    *   Returns the position of the first element, or the canonical
 463    *   invalid position if this array is empty.
 464    *
 465    * ssize_t IterLast(const ArrayData*)
 466    *
 467    *   Returns the position of the last element, or the canonical
 468    *   invalid position if this array is empty.
 469    */
 470   DISPATCH(IterBegin)
 471   DISPATCH(IterLast)
 472   DISPATCH(IterEnd)
 473
 474   /*
 475    * ssize_t IterAdvance(const ArrayData*, size_t pos)
 476    *
 477    *   Returns the position of the element that comes after pos, or the
 478    *   canonical invalid position if there are no more elements after pos.
 479    *   If pos is the canonical invalid position, this method will return
 480    *   the canonical invalid position.
 481    */
 482   DISPATCH(IterAdvance)
 483
 484   /*
 485    * ssize_t IterRewind(const ArrayData*, size_t pos)
 486    *
 487    *   Returns the position of the element that comes before pos, or the
 488    *   canonical invalid position if there are no elements before pos. If
 489    *   pos is the canonical invalid position, no guarantees are made about
 490    *   what this method returns.
 491    */
 492   DISPATCH(IterRewind)
 493
 494   /*
 495    * ArrayData* EscalateForSort(ArrayData*, SortFunction)
 496    *
 497    *   Must be called before calling any of the sort routines on an
 498    *   array. This gives arrays a chance to change to a kind that
 499    *   supports sorting.
 500    */
 501   DISPATCH(EscalateForSort)
 502
 503   /*
 504    * void Ksort(ArrayData*, int sort_flags, bool ascending)
 505    *
 506    *   Sort an array by its keys, keeping the values associated with
 507    *   their respective keys.
 508    */
 509   DISPATCH(Ksort)
 510
 511   /*
 512    * void Sort(ArrayData*, int sort_flags, bool ascending)
 513    *
 514    *   Sort an array, by values, and then assign new keys to the
 515    *   elements in the resulting array.
 516    */
 517   DISPATCH(Sort)
 518
 519   /*
 520    * void Asort(ArrayData*, int sort_flags, bool ascending)
 521    *
 522    *   Sort an array and maintain index association.  This means sort
 523    *   the array by values, but keep the keys associated with the
 524    *   values they used to be associated with.
 525    */
 526   DISPATCH(Asort)
 527
 528   /*
 529    * bool Uksort(ArrayData*, const Variant&)
 530    *
 531    *   Sort on keys with a user-defined compare function (in the
 532    *   variant argument).  Returns false if the user comparison
 533    *   function modifies the array we are sorting.
 534    */
 535   DISPATCH(Uksort)
 536
 537   /*
 538    * bool Usort(ArrayData*, const Variant&)
 539    *
 540    *   Sort the array by values with a user-defined comparison
 541    *   function (in the variant).  Returns false if the user-defined
 542    *   comparison function modifies the array we are sorting.
 543    */
 544   DISPATCH(Usort)
 545
 546   /*
 547    * bool Uasort(ArrayData*, const Variant&)
 548    *
 549    *   Sort array by values with a user-defined comparison function
 550    *   (in the variant arg), keeping the original indexes associated
 551    *   with the values.  Returns false if the user-defined comparison
 552    *   function modifies the array we are sorting.
 553    */
 554   DISPATCH(Uasort)
 555
 556   /*
 557    * ArrayData* Copy(const ArrayData*)
 558    *
 559    *   Explicitly request that an array be copied.  This API does
 560    *   /not/ actually guarantee a copy occurs.
 561    *
 562    *   (E.g. GlobalsArray doesn't copy here.)
 563    */
 564   DISPATCH(Copy)
 565
 566   /*
 567    * ArrayData* CopyStatic(const ArrayData*)
 568    *
 569    *   Copy an array, allocating the new array with malloc() instead
 570    *   of from the request local allocator.  This function does
 571    *   guarantee the returned array is a new copy---but it may throw a
 572    *   fatal error if this cannot be accomplished (e.g. for $GLOBALS).
 573    */
 574   DISPATCH(CopyStatic)
 575
 576   /*
 577    * ArrayData* Append(ArrayData*, TypedValue v);
 578    *
 579    *   Append a new value to the array, with the next available integer key,
 580    *   copying or escalating as necessary. If there is no available integer
 581    *   key, no value is appended, but this method may still copy the array.
 582    */
 583   DISPATCH(Append)
 584
 585   /*
 586    * ArrayData* PlusEq(ArrayData*, const ArrayData* elems)
 587    *
 588    *    Performs array addition, logically mutating the first array.
 589    *    It may return a new array if the array needed to grow, or if
 590    *    it needed to COW because cowCheck() was true.
 591    */
 592   DISPATCH(PlusEq)
 593
 594   /*
 595    * ArrayData* Merge(ArrayData*, const ArrayData* elems)
 596    *
 597    *   Perform part of the semantics of the php function array_merge.
 598    *   (Renumbering keys is not done by this routine currently.)
 599    */
 600   DISPATCH(Merge)
 601
 602   /*
 603    * ArrayData* Pop(ArrayData*, Variant& value);
 604    *
 605    *   Remove the last element from the array and assign it to `value'.  This
 606    *   function may return a new array if it decided to COW due to
 607    *   cowCheck().
 608    */
 609   DISPATCH(Pop)
 610
 611   /*
 612    * ArrayData* Dequeue(ArrayData*, Variant& value)
 613    *
 614    *   Remove the first element from the array and assign it to `value'.  This
 615    *   function may return a new array if it decided to COW due to
 616    *   cowCheck().
 617    */
 618   DISPATCH(Dequeue)
 619
 620   /*
 621    * ArrayData* Prepend(ArrayData*, TypedValue v)
 622    *
 623    *   Insert `v' as the first element of the array.  Then renumber
 624    *   integer keys.  This function has copy/grow semantics.  `v' must
 625    *   not be KindOfUninit.
 626    */
 627   DISPATCH(Prepend)
 628
 629   /*
 630    * ArrayData* Renumber(ArrayData*)
 631    *
 632    *   Renumber integer keys on the array. This method will operate in place
 633    *   if possible, but it returns a new array if we need copy / escalation.
 634    */
 635   DISPATCH(Renumber)
 636
 637   /*
 638    * void OnSetEvalScalar(ArrayData*)
 639    *
 640    *   Go through an array and call Variant::setEvalScalar on each
 641    *   value, and make all string keys into static strings.
 642    */
 643   DISPATCH(OnSetEvalScalar)
 644
 645    /*
 646    * ArrayData* ToPHPArray(ArrayData*, bool)
 647    *
 648    *   Convert to a PHP array. If already a PHP array, it will be returned
 649    *   unchange (without copying). If copy is false, it may be converted in
 650    *   place.
 651    */
 652   DISPATCH(ToPHPArray)
 653   DISPATCH(ToPHPArrayIntishCast)
 654
 655    /*
 656    * ArrayData* ToDict(ArrayData*, bool)
 657    *
 658    *   Convert to a dict. If already a dict, it will be returned unchange
 659    *   (without copying). If copy is false, it may be converted in place. If the
 660    *   input array contains references, an exception will be thrown.
 661    */
 662   DISPATCH(ToDict)
 663
 664   /*
 665    * ArrayData* ToVec(ArrayData*, bool)
 666    *
 667    *   Convert to a vec. Keys will be discarded and the vec will contain the
 668    *   values in iteration order. If already a vec, it will be returned
 669    *   unchanged (without copying). If copy is false, it may be converted in
 670    *   place. If the input array contains references, an exception will be
 671    *   thrown.
 672    */
 673   DISPATCH(ToVec)
 674
 675    /*
 676    * ArrayData* ToKeyset(ArrayData*, bool)
 677    *
 678    *   Convert to a keyset. Keys will be discarded and the keyset will contain
 679    *   just the values in iteration order. If already a keyset, it will be
 680    *   returned unchange (without copying). If copy is false, it may be
 681    *   converted in place. If the input array contains references, or if the
 682    *   input contains values that are neither integers or strings, an exception
 683    *   will be thrown.
 684    */
 685   DISPATCH(ToKeyset)
 686
 687   /*
 688    * ArrayData* ToVArray(ArrayData*, bool)
 689    *
 690    * Convert to a varray (vector-like array). The array will be converted to a
 691    * packed array, discarding keys. If already a packed array, it will be
 692    * returned with the elements unchanged, but with the DVArray flag updated. If
 693    * copy is false, it may be converted in place.
 694    */
 695   DISPATCH(ToVArray)
 696
 697   /*
 698    * ArrayData* ToDArray(ArrayData*, bool)
 699    *
 700    * Convert to a darray (dict-like array). The array will be converted to a
 701    * mixed array. If already a mixed array, it will be returned with the
 702    * elements unchanged, but with the DVArray flag updated. If copy is false, it
 703    * may be converted in place.
 704    */
 705   DISPATCH(ToDArray)
 706 };
 707
 708 #undef DISPATCH
 709
 710 ///////////////////////////////////////////////////////////////////////////////
 711
 712 __attribute__((__always_inline__))
 713 DataType ArrayData::toDataType() const {
 714   if (UNLIKELY(RuntimeOption::EvalEmitDVArray)) {
 715     if (isVArray()) {
 716       assertx(isPackedKind());
 717       return KindOfVArray;
 718     } else if (isDArray()) {
 719       assertx(isMixedKind());
 720       return KindOfDArray;
 721     }
 722   }
 723   switch (kind()) {
 724     case kPackedKind:
 725     case kMixedKind:
 726     case kEmptyKind:
 727     case kGlobalsKind:
 728     case kRecordKind:
 729       return KindOfArray;
 730
 731     case kDictKind:    return KindOfDict;
 732     case kVecKind:     return KindOfVec;
 733     case kKeysetKind:  return KindOfKeyset;
 734     case kBespokeArrayKind: return KindOfArray;
 735     case kBespokeDictKind: return KindOfDict;
 736     case kBespokeVecKind: return KindOfVec;
 737     case kBespokeKeysetKind: return KindOfKeyset;
 738     case kNumKinds:   not_reached();
 739   }
 740   not_reached();
 741 }
 742
 743 __attribute__((__always_inline__))
 744 DataType ArrayData::toPersistentDataType() const {
 745   if (UNLIKELY(RuntimeOption::EvalEmitDVArray)) {
 746     if (isVArray()) {
 747       assertx(isPackedKind());
 748       return KindOfPersistentVArray;
 749     } else if (isDArray()) {
 750       assertx(isMixedKind());
 751       return KindOfPersistentDArray;
 752     }
 753   }
 754   switch (kind()) {
 755     case kPackedKind:
 756     case kMixedKind:
 757     case kEmptyKind:
 758     case kGlobalsKind:
 759     case kRecordKind:
 760       return KindOfPersistentArray;
 761
 762     case kDictKind:   return KindOfPersistentDict;
 763     case kVecKind:    return KindOfPersistentVec;
 764     case kKeysetKind: return KindOfPersistentKeyset;
 765     case kBespokeArrayKind: return KindOfPersistentArray;
 766     case kBespokeDictKind: return KindOfPersistentDict;
 767     case kBespokeVecKind: return KindOfPersistentVec;
 768     case kBespokeKeysetKind: return KindOfPersistentKeyset;
 769     case kNumKinds:   not_reached();
 770   }
 771   not_reached();
 772 }
 773
 774 namespace {
 775
 776 DEBUG_ONLY void assertForCreate(TypedValue name) {
 777   always_assert(isIntType(name.m_type) || isStringType(name.m_type));
 778 }
 779
 780 }
 781
 782 // In general, arrays can contain int-valued-strings, even though plain array
 783 // access converts them to integers.  non-int-string assertions should go
 784 // upstream of the ArrayData api.
 785
 786 bool ArrayData::IsValidKey(TypedValue k) {
 787   return isIntType(k.m_type) ||
 788         (isStringType(k.m_type) && IsValidKey(k.m_data.pstr));
 789 }
 790
 791 bool ArrayData::IsValidKey(const Variant& k) {
 792   return IsValidKey(*k.asTypedValue());
 793 }
 794
 795 bool ArrayData::IsValidKey(const String& k) {
 796   return IsValidKey(k.get());
 797 }
 798
 799 ArrayData* ArrayData::Create(TypedValue value) {
 800   PackedArrayInit pai(1);
 801   pai.append(value);
 802   return pai.create();
 803 }
 804
 805 ArrayData* ArrayData::Create(TypedValue name, TypedValue value) {
 806   if (debug) assertForCreate(name);
 807
 808   ArrayInit init(1, ArrayInit::Map{});
 809   init.setValidKey(name, value);
 810   return init.create();
 811 }
 812
 813 ///////////////////////////////////////////////////////////////////////////////
 814 // reads
 815
 816 ALWAYS_INLINE
 817 bool ArrayData::EqualHelper(const ArrayData* ad1, const ArrayData* ad2,
 818                             bool strict) {
 819   assertx(ad1->isPHPArrayType());
 820   assertx(ad2->isPHPArrayType());
 821
 822   if (ad1 == ad2) return true;
 823
 824   if (!ArrayData::dvArrayEqual(ad1, ad2)) {
 825     if (RO::EvalHackArrCompatSpecialization) return false;
 826     if (RO::EvalHackArrCompatDVCmpNotices) {
 827       raiseHackArrCompatDVArrCmp(ad1, ad2, /* is relational */ false);
 828     }
 829   }
 830
 831   if (ad1->size() != ad2->size()) return false;
 832
 833   // Prevent circular referenced objects/arrays or deep ones.
 834   check_recursion_error();
 835
 836   if (strict) {
 837     for (ArrayIter iter1{ad1}, iter2{ad2}; iter1; ++iter1, ++iter2) {
 838       assertx(iter2);
 839       if (!same(iter1.first(), iter2.first()) ||
 840           !tvSame(iter1.secondVal(), iter2.secondVal())) {
 841         return false;
 842       }
 843     }
 844     return true;
 845   } else {
 846     bool equal = true;
 847     IterateKV(
 848       ad1,
 849       [&](TypedValue k, TypedValue v) {
 850         auto const v2 = ad2->get(k);
 851         if (!v2.is_init() || !tvEqual(v, v2)) {
 852           equal = false;
 853           return true;
 854         }
 855         return false;
 856       }
 857     );
 858     return equal;
 859   }
 860 }
 861
 862 ALWAYS_INLINE
 863 int64_t ArrayData::CompareHelper(const ArrayData* ad1, const ArrayData* ad2) {
 864   assertx(ad1->isPHPArrayType());
 865   assertx(ad2->isPHPArrayType());
 866
 867   if (!ArrayData::dvArrayEqual(ad1, ad2)) {
 868     if (RO::EvalHackArrCompatSpecialization) {
 869       if (ad1->isVArray()) throw_varray_compare_exception();
 870       if (ad1->isDArray()) throw_darray_compare_exception();
 871       if (ad2->isVArray()) throw_varray_compare_exception();
 872       if (ad2->isDArray()) throw_darray_compare_exception();
 873       always_assert(false);
 874     } else if (RO::EvalHackArrCompatDVCmpNotices) {
 875       raiseHackArrCompatDVArrCmp(ad1, ad2, /* is relational */ true);
 876     }
 877   } else if (ad1->isDArray()) {
 878     if (RO::EvalHackArrCompatSpecialization) {
 879       throw_darray_compare_exception();
 880     } else if (RO::EvalHackArrCompatDVCmpNotices) {
 881       raise_hackarr_compat_notice("Comparing two darrays relationally");
 882     }
 883   }
 884
 885   auto const size1 = ad1->size();
 886   auto const size2 = ad2->size();
 887   if (size1 < size2) return -1;
 888   if (size1 > size2) return 1;
 889
 890   // Prevent circular referenced objects/arrays or deep ones.
 891   check_recursion_error();
 892
 893   int result = 0;
 894   IterateKV(
 895     ad1,
 896     [&](TypedValue k, TypedValue v) {
 897       auto const v2 = ad2->get(k);
 898       if (!v2.is_init()) {
 899         result = 1;
 900         return true;
 901       }
 902       auto const cmp = tvCompare(v, v2);
 903       if (cmp != 0) {
 904         result = cmp;
 905         return true;
 906       }
 907       return false;
 908     }
 909   );
 910
 911   return result;
 912 }
 913
 914 bool ArrayData::Equal(const ArrayData* ad1, const ArrayData* ad2) {
 915   return EqualHelper(ad1, ad2, false);
 916 }
 917
 918 bool ArrayData::NotEqual(const ArrayData* ad1, const ArrayData* ad2) {
 919   return !EqualHelper(ad1, ad2, false);
 920 }
 921
 922 bool ArrayData::Same(const ArrayData* ad1, const ArrayData* ad2) {
 923   return EqualHelper(ad1, ad2, true);
 924 }
 925
 926 bool ArrayData::NotSame(const ArrayData* ad1, const ArrayData* ad2) {
 927   return !EqualHelper(ad1, ad2, true);
 928 }
 929
 930 bool ArrayData::Lt(const ArrayData* ad1, const ArrayData* ad2) {
 931   return CompareHelper(ad1, ad2) < 0;
 932 }
 933
 934 bool ArrayData::Lte(const ArrayData* ad1, const ArrayData* ad2) {
 935   return CompareHelper(ad1, ad2) <= 0;
 936 }
 937
 938 bool ArrayData::Gt(const ArrayData* ad1, const ArrayData* ad2) {
 939   return 0 > CompareHelper(ad2, ad1); // Not symmetric; Order matters here.
 940 }
 941
 942 bool ArrayData::Gte(const ArrayData* ad1, const ArrayData* ad2) {
 943   return 0 >= CompareHelper(ad2, ad1); // Not symmetric; Order matters here.
 944 }
 945
 946 int64_t ArrayData::Compare(const ArrayData* ad1, const ArrayData* ad2) {
 947   return CompareHelper(ad1, ad2);
 948 }
 949
 950 int ArrayData::compare(const ArrayData* v2) const {
 951   assertx(v2);
 952
 953   if (isPHPArrayType()) {
 954     if (UNLIKELY(!v2->isPHPArrayType())) {
 955       if (UNLIKELY(checkHACCompare())) {
 956         raiseHackArrCompatArrHackArrCmp();
 957       }
 958       if (v2->isVecArrayType()) throw_vec_compare_exception();
 959       if (v2->isDictType()) throw_dict_compare_exception();
 960       if (v2->isKeysetType()) throw_keyset_compare_exception();
 961       not_reached();
 962     }
 963     return Compare(this, v2);
 964   }
 965
 966   if (isVecArrayType()) {
 967     if (UNLIKELY(!v2->isVecArrayType())) {
 968       if (UNLIKELY(checkHACCompare() && v2->isPHPArrayType())) {
 969         raiseHackArrCompatArrHackArrCmp();
 970       }
 971       throw_vec_compare_exception();
 972     }
 973     assertx(isVecArrayKind() && v2->isVecArrayKind());
 974     return PackedArray::VecCmp(this, v2);
 975   }
 976
 977   if (UNLIKELY(checkHACCompare() && v2->isPHPArrayType())) {
 978     raiseHackArrCompatArrHackArrCmp();
 979   }
 980
 981   if (isDictType()) throw_dict_compare_exception();
 982   if (isKeysetType()) throw_keyset_compare_exception();
 983
 984   not_reached();
 985 }
 986
 987 bool ArrayData::equal(const ArrayData* v2, bool strict) const {
 988   assertx(v2);
 989
 990   auto const mixed = [&]{
 991     if (UNLIKELY(checkHACCompare() && v2->isHackArrayType())) {
 992       raiseHackArrCompatArrHackArrCmp();
 993     }
 994     return false;
 995   };
 996
 997   if (isPHPArrayType()) {
 998     if (UNLIKELY(!v2->isPHPArrayType())) return mixed();
 999     return strict ? Same(this, v2) : Equal(this, v2);
1000   }
1001
1002   if (isVecArrayKind()) {
1003     if (UNLIKELY(!v2->isVecArrayKind())) return mixed();
1004     return strict
1005       ? PackedArray::VecSame(this, v2) : PackedArray::VecEqual(this, v2);
1006   }
1007
1008   if (isDictKind()) {
1009     if (UNLIKELY(!v2->isDictKind())) return mixed();
1010     return strict
1011       ? MixedArray::DictSame(this, v2) : MixedArray::DictEqual(this, v2);
1012   }
1013
1014   if (isKeysetKind()) {
1015     if (UNLIKELY(!v2->isKeysetKind())) return mixed();
1016     return strict ? SetArray::Same(this, v2) : SetArray::Equal(this, v2);
1017   }
1018
1019   not_reached();
1020 }
1021
1022 Variant ArrayData::reset() {
1023   setPosition(iter_begin());
1024   return m_pos != iter_end() ? getValue(m_pos) : Variant(false);
1025 }
1026
1027 Variant ArrayData::next() {
1028   // We call iter_advance() without checking if m_pos is the canonical invalid
1029   // position. This is okay, since all IterAdvance() impls handle this
1030   // correctly, but it means that EmptyArray::IterAdvance() is reachable.
1031   setPosition(iter_advance(m_pos));
1032   return m_pos != iter_end() ? getValue(m_pos) : Variant(false);
1033 }
1034
1035 Variant ArrayData::prev() {
1036   // We only call iter_rewind() if m_pos is not the canonical invalid position.
1037   // Thus, EmptyArray::IterRewind() is not reachable.
1038   auto pos_limit = iter_end();
1039   if (m_pos != pos_limit) {
1040     setPosition(iter_rewind(m_pos));
1041     if (m_pos != pos_limit) {
1042       return getValue(m_pos);
1043     }
1044   }
1045   return Variant(false);
1046 }
1047
1048 Variant ArrayData::end() {
1049   setPosition(iter_last());
1050   return m_pos != iter_end() ? getValue(m_pos) : Variant(false);
1051 }
1052
1053 Variant ArrayData::key() const {
1054   return m_pos != iter_end() ? getKey(m_pos) : uninit_null();
1055 }
1056
1057 Variant ArrayData::value(int32_t pos) const {
1058   return pos != iter_end() ? getValue(pos) : Variant(false);
1059 }
1060
1061 Variant ArrayData::current() const {
1062   return m_pos != iter_end() ? getValue(m_pos) : Variant(false);
1063 }
1064
1065 const StaticString
1066   s_value("value"),
1067   s_key("key");
1068
1069 Variant ArrayData::each() {
1070   if (m_pos != iter_end()) {
1071     ArrayInit ret(4, ArrayInit::Mixed{});
1072     Variant key(getKey(m_pos));
1073     Variant value(getValue(m_pos));
1074     ret.set(1, value);
1075     ret.set(s_value, value);
1076     ret.set(0, key);
1077     ret.set(s_key, key);
1078     setPosition(iter_advance(m_pos));
1079     return ret.toVariant();
1080   }
1081   return Variant(false);
1082 }
1083
1084 ///////////////////////////////////////////////////////////////////////////////
1085 // helpers
1086
1087 void ArrayData::getNotFound(int64_t k) const {
1088   assertx(kind() != kGlobalsKind);
1089   if (isHackArrayType()) throwOOBArrayKeyException(k, this);
1090   throwArrayIndexException(k, false);
1091 }
1092
1093 void ArrayData::getNotFound(const StringData* k) const {
1094   assertx(kind() != kGlobalsKind);
1095   if (isVecArrayType()) throwInvalidArrayKeyException(k, this);
1096   if (isHackArrayType()) throwOOBArrayKeyException(k, this);
1097   throwArrayKeyException(k, false);
1098 }
1099
1100 const char* ArrayData::kindToString(ArrayKind kind) {
1101   std::array<const char*, 12> names = {{
1102     "PackedKind",
1103     "MixedKind",
1104     "EmptyKind",
1105     "GlobalsKind",
1106     "RecordKind",
1107     "DictKind",
1108     "VecKind",
1109     "KeysetKind",
1110     "BespokeArrayKind",
1111     "BespokeDictKind",
1112     "BespokeVecKind",
1113     "BespokeKeysetKind",
1114   }};
1115   static_assert(names.size() == kNumKinds, "add new kinds here");
1116   return names[kind];
1117 }
1118
1119 namespace {
1120
1121 ////////////////////////////////////////////////////////////////////////////////
1122
1123 std::string describeKeyType(const TypedValue* tv) {
1124   switch (tv->m_type) {
1125   case KindOfUninit:
1126   case KindOfNull:             return "null";
1127   case KindOfBoolean:          return "bool";
1128   case KindOfInt64:            return "int";
1129   case KindOfDouble:           return "double";
1130   case KindOfPersistentString:
1131   case KindOfString:           return "string";
1132   case KindOfPersistentVec:
1133   case KindOfVec:              return "vec";
1134   case KindOfPersistentDict:
1135   case KindOfDict:             return "dict";
1136   case KindOfPersistentKeyset:
1137   case KindOfKeyset:           return "keyset";
1138   case KindOfPersistentDArray:
1139   case KindOfDArray:
1140     return UNLIKELY(RuntimeOption::EvalSpecializeDVArray) ? "darray" : "array";
1141   case KindOfPersistentVArray:
1142   case KindOfVArray:
1143     return UNLIKELY(RuntimeOption::EvalSpecializeDVArray) ? "varray" : "array";
1144   case KindOfPersistentArray:
1145   case KindOfArray:            return "array";
1146   case KindOfResource:
1147     return tv->m_data.pres->data()->o_getClassName().toCppString();
1148
1149   case KindOfObject:
1150     return tv->m_data.pobj->getClassName().get()->toCppString();
1151
1152   case KindOfRecord:
1153     return tv->m_data.prec->record()->name()->toCppString();
1154
1155   case KindOfRFunc:           return "rfunc";
1156   case KindOfFunc:            return "func";
1157   case KindOfClass:           return "class";
1158   case KindOfClsMeth:         return "clsmeth";
1159   }
1160   not_reached();
1161 }
1162
1163 std::string describeKeyValue(TypedValue tv) {
1164   switch (tv.m_type) {
1165   case KindOfPersistentString:
1166   case KindOfString:
1167     return folly::sformat("\"{}\"", tv.m_data.pstr->data());
1168   case KindOfInt64:
1169     return folly::to<std::string>(tv.m_data.num);
1170   case KindOfUninit:
1171   case KindOfNull:
1172   case KindOfBoolean:
1173   case KindOfDouble:
1174   case KindOfPersistentVec:
1175   case KindOfVec:
1176   case KindOfPersistentDict:
1177   case KindOfDict:
1178   case KindOfPersistentKeyset:
1179   case KindOfKeyset:
1180   case KindOfPersistentDArray:
1181   case KindOfDArray:
1182   case KindOfPersistentVArray:
1183   case KindOfVArray:
1184   case KindOfPersistentArray:
1185   case KindOfArray:
1186   case KindOfResource:
1187   case KindOfObject:
1188   case KindOfRFunc:
1189   case KindOfFunc:
1190   case KindOfClass:
1191   case KindOfClsMeth:
1192   case KindOfRecord:
1193     return "<invalid key type>";
1194   }
1195   not_reached();
1196 }
1197
1198 ////////////////////////////////////////////////////////////////////////////////
1199
1200 }
1201
1202 void throwInvalidArrayKeyException(const TypedValue* key, const ArrayData* ad) {
1203   std::pair<const char*, const char*> kind_type = [&]{
1204     if (ad->isVecArrayType()) return std::make_pair("vec", "int");
1205     if (ad->isDictType()) return std::make_pair("dict", "int or string");
1206     if (ad->isKeysetType()) return std::make_pair("keyset", "int or string");
1207     assertx(ad->isPHPArrayType());
1208     if (RO::EvalHackArrCompatSpecialization) {
1209       if (ad->isVArray()) return std::make_pair("varray", "int");
1210       if (ad->isDArray()) return std::make_pair("darray", "int or string");
1211     }
1212     return std::make_pair("array", "int or string");
1213   }();
1214   SystemLib::throwInvalidArgumentExceptionObject(
1215     folly::sformat(
1216       "Invalid {} key: expected a key of type {}, {} given",
1217       kind_type.first, kind_type.second, describeKeyType(key)
1218     )
1219   );
1220 }
1221
1222 void throwInvalidArrayKeyException(const StringData* key, const ArrayData* ad) {
1223   auto const tv = make_tv<KindOfString>(const_cast<StringData*>(key));
1224   throwInvalidArrayKeyException(&tv, ad);
1225 }
1226
1227 void throwFalseyPromoteException(const char* type) {
1228   SystemLib::throwOutOfBoundsExceptionObject(
1229     folly::sformat("Promoting {} to array", type)
1230   );
1231 }
1232
1233 void throwMissingElementException(const char* op) {
1234   SystemLib::throwOutOfBoundsExceptionObject(
1235     folly::sformat("{} on missing array element", op)
1236   );
1237 }
1238
1239 void throwOOBArrayKeyException(TypedValue key, const ArrayData* ad) {
1240   const char* type = [&]{
1241     if (ad->isVecArrayType()) return "vec";
1242     if (ad->isDictType()) return "dict";
1243     if (ad->isKeysetType()) return "keyset";
1244     assertx(ad->isPHPArrayType());
1245     return "array";
1246   }();
1247   SystemLib::throwOutOfBoundsExceptionObject(
1248     folly::sformat(
1249       "Out of bounds {} access: invalid index {}",
1250       type, describeKeyValue(key)
1251     )
1252   );
1253 }
1254
1255 void throwOOBArrayKeyException(int64_t key, const ArrayData* ad) {
1256   throwOOBArrayKeyException(make_tv<KindOfInt64>(key), ad);
1257 }
1258
1259 void throwOOBArrayKeyException(const StringData* key, const ArrayData* ad) {
1260   throwOOBArrayKeyException(
1261     make_tv<KindOfString>(const_cast<StringData*>(key)),
1262     ad
1263   );
1264 }
1265
1266 void throwInvalidKeysetOperation() {
1267   SystemLib::throwInvalidOperationExceptionObject(s_InvalidKeysetOperationMsg);
1268 }
1269
1270 void throwInvalidAdditionException(const ArrayData* ad) {
1271   assertx(ad->isHackArrayType());
1272   const char* type = [&]{
1273     if (ad->isVecArrayType()) return "Vecs";
1274     if (ad->isDictType()) return "Dicts";
1275     if (ad->isKeysetType()) return "Keysets";
1276     not_reached();
1277   }();
1278   SystemLib::throwInvalidOperationExceptionObject(
1279     folly::sformat("{} do not support the + operator", type)
1280   );
1281 }
1282
1283 void throwVarrayUnsetException() {
1284   SystemLib::throwInvalidOperationExceptionObject(s_VarrayUnsetMsg);
1285 }
1286
1287 void throwVecUnsetException() {
1288   SystemLib::throwInvalidOperationExceptionObject(s_VecUnsetMsg);
1289 }
1290
1291 ///////////////////////////////////////////////////////////////////////////////
1292
1293 void raiseHackArrCompatAdd() {
1294   raise_hac_array_plus_notice("Using + operator on arrays");
1295 }
1296
1297 void raiseHackArrCompatArrHackArrCmp() {
1298   raise_hac_compare_notice(Strings::HACKARR_COMPAT_ARR_HACK_ARR_CMP);
1299 }
1300
1301 void raiseHackArrCompatDVArrCmp(const ArrayData* ad1,
1302                                 const ArrayData* ad2,
1303                                 bool is_relational) {
1304   if (UNLIKELY(RID().getSuppressHACCompareNotices())) return;
1305   auto const type = [](const ArrayData* a) {
1306     if (a->isVArray()) return "varray";
1307     if (a->isDArray()) return "darray";
1308     return "array";
1309   };
1310   raise_hackarr_compat_notice(
1311     folly::sformat("Comparing {} and {}{}",
1312                    type(ad1),
1313                    type(ad2),
1314                    is_relational ? " relationally" : "")
1315   );
1316 }
1317
1318 std::string makeHackArrCompatImplicitArrayKeyMsg(const TypedValue* key) {
1319   return folly::sformat(
1320     "Implicit conversion of {} to array key",
1321     describeKeyType(key)
1322   );
1323 }
1324
1325 void raiseHackArrCompatImplicitArrayKey(const TypedValue* key) {
1326   raise_hac_array_key_cast_notice(makeHackArrCompatImplicitArrayKeyMsg(key));
1327 }
1328
1329 ///////////////////////////////////////////////////////////////////////////////
1330
1331 namespace arrprov_detail {
1332
1333 template<typename SrcArr>
1334 ArrayData* tagArrProvImpl(ArrayData* ad, const SrcArr* src) {
1335   assertx(RuntimeOption::EvalArrayProvenance);
1336   assertx(ad->hasExactlyOneRef() || !ad->isRefCounted());
1337
1338   if (!arrprov::arrayWantsTag(ad)) return ad;
1339
1340   auto const do_tag = [] (ArrayData* ad, arrprov::Tag tag) {
1341     if (ad->isStatic()) return tagStaticArr(ad, tag);
1342
1343     arrprov::setTag<arrprov::Mode::Emplace>(ad, tag);
1344     return ad;
1345   };
1346
1347   if (src != nullptr) {
1348     if (auto const tag = arrprov::getTag(src)) return do_tag(ad, tag);
1349   }
1350   if (auto const tag = arrprov::tagFromPC()) return do_tag(ad, tag);
1351
1352   return ad;
1353 }
1354
1355 template ArrayData* tagArrProvImpl<ArrayData>(ArrayData*, const ArrayData*);
1356 template ArrayData* tagArrProvImpl<APCArray>(ArrayData*, const APCArray*);
1357
1358 }
1359
1360 ///////////////////////////////////////////////////////////////////////////////
1361
1362 }