hphp/runtime/base/type-array.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_ARRAY_H_
  18 #define incl_HPHP_ARRAY_H_
  19
  20 #include "hphp/runtime/base/array-data.h"
  21 #include "hphp/runtime/base/datatype.h"
  22 #include "hphp/runtime/base/req-ptr.h"
  23 #include "hphp/runtime/base/tv-type.h"
  24 #include "hphp/runtime/base/tv-val.h"
  25 #include "hphp/runtime/base/tv-variant.h"
  26 #include "hphp/runtime/base/types.h"
  27
  28 #include <algorithm>
  29 #include <vector>
  30
  31 namespace HPHP {
  32 ///////////////////////////////////////////////////////////////////////////////
  33
  34 // Forward declare to avoid including tv-conversions.h and creating a cycle.
  35 template <IntishCast IC = IntishCast::None>
  36 ArrayData* tvCastToArrayLikeData(TypedValue tv);
  37
  38 struct ArrayIter;
  39 struct VariableUnserializer;
  40
  41 ////////////////////////////////////////////////////////////////////////////////
  42
  43 enum class AccessFlags {
  44   None     = 0,
  45   Error    = 1,
  46   Key      = 2,
  47   ErrorKey = Error | Key,
  48 };
  49
  50 inline AccessFlags operator&(AccessFlags a, AccessFlags b) {
  51   return static_cast<AccessFlags>(static_cast<int>(a) & static_cast<int>(b));
  52 }
  53
  54 constexpr bool any(AccessFlags a) {
  55   return a != AccessFlags::None;
  56 }
  57
  58 ////////////////////////////////////////////////////////////////////////////////
  59
  60 /*
  61  * Array type wrapping ArrayData to implement reference counting, copy-on-write
  62  * and ArrayData escalation.
  63  *
  64  * "Escalation" happens when an underlying ArrayData cannot handle an operation
  65  * and instead it needs to "upgrade" itself to be a more general (but slower)
  66  * type of ArrayData to accomplish the task.
  67  */
  68 struct Array {
  69 private:
  70   using Ptr = req::ptr<ArrayData>;
  71   using NoIncRef = Ptr::NoIncRef;
  72   using NonNull = Ptr::NonNull;
  73
  74   using Flags = AccessFlags;
  75
  76 public:
  77   /*
  78    * Create an empty array.
  79    */
  80   static Array Create() {
  81     return Array(ArrayData::Create(), NoIncRef{});
  82   }
  83
  84   /*
  85    * There are existing callsites that we intentionally want to create a
  86    * "traditional" PHP array with no specialization. Array::CreatePHPArray()
  87    * are calls that have been audited and determined that the callsite should
  88    * never be converted.
  89    */
  90   static constexpr auto CreatePHPArray = &Create;
  91
  92   static Array CreateVec() {
  93     return Array(ArrayData::CreateVec(), NoIncRef{});
  94   }
  95
  96   static Array CreateDict() {
  97     return Array(ArrayData::CreateDict(), NoIncRef{});
  98   }
  99
 100   static Array CreateKeyset() {
 101     return Array(ArrayData::CreateKeyset(), NoIncRef{});
 102   }
 103
 104   static Array CreateVArray() {
 105     return Array(ArrayData::CreateVArray(), NoIncRef{});
 106   }
 107
 108   static Array CreateDArray() {
 109     return Array(ArrayData::CreateDArray(), NoIncRef{});
 110   }
 111
 112   /////////////////////////////////////////////////////////////////////////////
 113
 114   Array() {}
 115   ~Array();
 116
 117   /*
 118    * Take ownership of `ad'.
 119    */
 120   static ALWAYS_INLINE Array attach(ArrayData* ad) {
 121     return Array(ad, NoIncRef{});
 122   }
 123
 124   /*
 125    * Transfer ownership of our underlying ArrayData.
 126    */
 127   ArrayData* detach() { return m_arr.detach(); }
 128
 129   /*
 130    * Get or null out the underlying ArrayData pointer.
 131    */
 132   ArrayData* get() const { return m_arr.get(); }
 133   void reset(ArrayData* arr = nullptr) { m_arr.reset(arr); }
 134
 135   /*
 136    * Delegate to the underlying ArrayData.
 137    *
 138    * Deliberately doesn't throw_null_pointer_exception as a perf optimization.
 139    */
 140   ArrayData* operator->() const { return m_arr.get(); }
 141
 142   /*
 143    * "Copy" constructors.
 144    */
 145   explicit Array(ArrayData* data) : m_arr(data) { }
 146   Array(const Array& arr) : m_arr(arr.m_arr) { }
 147
 148   /*
 149    * Special constructor for use from ArrayInit that creates an Array without a
 150    * null check and without an inc-ref.
 151    */
 152   enum class ArrayInitCtor { Tag };
 153   explicit Array(ArrayData* ad, ArrayInitCtor)
 154     : m_arr(ad, NoIncRef{})
 155   {}
 156
 157   /*
 158    * Move constructor.
 159    */
 160   Array(Array&& src) noexcept : m_arr(std::move(src.m_arr)) { }
 161
 162   /*
 163    * Assignment.
 164    */
 165   Array& operator=(ArrayData* data) {
 166     m_arr = data;
 167     return *this;
 168   }
 169   Array& operator=(const Array& arr) {
 170     m_arr = arr.m_arr;
 171     return *this;
 172   }
 173   Array& operator=(const Variant& v);
 174
 175   /*
 176    * Move assignment.
 177    */
 178   Array& operator=(Array&& src) {
 179     m_arr = std::move(src.m_arr);
 180     return *this;
 181   }
 182   Array& operator=(Variant&& v);
 183
 184   #define COPY_BODY(meth, def)                                          \
 185     if (!m_arr) return def;                                             \
 186     auto new_arr = m_arr->meth;                                         \
 187     return new_arr != m_arr ? Array{new_arr, NoIncRef{}} : Array{*this};
 188
 189   /*
 190    * Make a copy of this array.
 191    *
 192    * Like the underlying ArrayData::copy operation, the returned Array may
 193    * point to the same underlying array as the original, or a new one.
 194    */
 195   Array copy() const { COPY_BODY(copy(), Array{}) }
 196   Array toVec() const { COPY_BODY(toVec(true), CreateVec()) }
 197   Array toDict() const { COPY_BODY(toDict(true), CreateDict()) }
 198   Array toKeyset() const { COPY_BODY(toKeyset(true), CreateKeyset()) }
 199   Array toPHPArray() const { COPY_BODY(toPHPArray(true), Array{}) }
 200   Array toPHPArrayIntishCast() const {
 201     COPY_BODY(toPHPArrayIntishCast(true), Array{})
 202   }
 203   Array toVArray() const { COPY_BODY(toVArray(true), CreateVArray()) }
 204   Array toDArray() const { COPY_BODY(toDArray(true), CreateDArray()) }
 205
 206   #undef COPY_BODY
 207
 208   /////////////////////////////////////////////////////////////////////////////
 209
 210   /*
 211    * Nullability.
 212    */
 213   bool isNull() const { return !m_arr; }
 214
 215   /*
 216    * Size.
 217    */
 218   bool empty() const { return !m_arr || m_arr->empty(); }
 219   ssize_t size() const { return m_arr ? m_arr->size() : 0; }
 220   ssize_t length() const { return m_arr ? m_arr->size() : 0; }
 221
 222   /*
 223    * Array kind.
 224    */
 225   bool isVecArray() const { return m_arr && m_arr->isVecArrayType(); }
 226   bool isDict() const { return m_arr && m_arr->isDictType(); }
 227   bool isKeyset() const { return m_arr && m_arr->isKeysetType(); }
 228   bool isHackArray() const { return m_arr && m_arr->isHackArrayType(); }
 229   bool isPHPArray() const { return !m_arr || m_arr->isPHPArrayType(); }
 230   bool isVArray() const { return m_arr && m_arr->isVArray(); }
 231   bool isDArray() const { return m_arr && m_arr->isDArray(); }
 232   bool isVecOrVArray() const { return m_arr && m_arr->isVecOrVArray(); }
 233   bool isDictOrDArray() const { return m_arr && m_arr->isDictOrDArray(); }
 234
 235   /////////////////////////////////////////////////////////////////////////////
 236
 237   /*
 238    * Start iterator.
 239    *
 240    * See array-iterator.h for end() and next().
 241    */
 242   ArrayIter begin(const String& context = null_string) const;
 243
 244   /*
 245    * Converts `k' to a valid key for this array kind.
 246    */
 247   template <IntishCast IC = IntishCast::None>
 248   TypedValue convertKey(TypedValue k) const;
 249   template <IntishCast IC = IntishCast::None>
 250   TypedValue convertKey(const Variant& k) const;
 251
 252   /*
 253    * Should int-like string keys be implicitly converted to integers before they
 254    * are inserted?
 255    */
 256   bool useWeakKeys() const {
 257     // If array isn't set we may implicitly create a mixed array, which uses
 258     // weak keys.  We never implicitly create a Hack array.
 259     return !m_arr || m_arr->useWeakKeys();
 260   }
 261
 262   /*
 263    * Convert the underlying ArrayData to a static copy of itself.
 264    */
 265   void setEvalScalar() const;
 266
 267   /////////////////////////////////////////////////////////////////////////////
 268   // PHP operations.
 269
 270   /*
 271    * PHP array union operator.
 272    */
 273   Array  operator+(ArrayData* data) const;
 274   Array  operator+(const Array& v) const;
 275   Array  operator+(const Variant& v) const = delete;
 276   Array& operator+=(ArrayData* data);
 277   Array& operator+=(const Array& v);
 278   Array& operator+=(const Variant& v);
 279
 280   /*
 281    * Implementation of array_merge().
 282    *
 283    * This is different from operator+(), where existing keys' values are NOT
 284    * modified.  This function will actually override with new values.
 285    *
 286    * When merging a packed array with another packed array, new elements are
 287    * always appended, and this is also different from operator+() where
 288    * existing numeric indices are not modified.
 289    */
 290   Array& merge(const Array& arr);
 291
 292   /*
 293    * Comparison function for array operations.
 294    */
 295   using PFUNC_CMP = int (*)(const Variant& v1, const Variant& v2,
 296                             const void* data);
 297
 298   /*
 299    * Return the entries that have keys and/or values that are (intersect), or
 300    * are not (diff) present in `array'.
 301    *
 302    * Keys and values can be compared by user supplied functions and `key_data'
 303    * or `value_data' will be passed into the corresponding `cmp_function' as
 304    * the `data' parameter.  Otherwise, equal() will be called for comparisons.
 305    * If both `by_key' and `by_value' are true, both keys and values have to
 306    * match to be included (intersect) or excluded (diff).
 307    */
 308   Array diff(const Variant& array, bool by_key, bool by_value,
 309              PFUNC_CMP key_cmp_function = nullptr,
 310              const void* key_data = nullptr,
 311              PFUNC_CMP value_cmp_function = nullptr,
 312              const void* value_data = nullptr) const;
 313   Array intersect(const Variant& array, bool by_key, bool by_value,
 314                   PFUNC_CMP key_cmp_function = nullptr,
 315                   const void* key_data = nullptr,
 316                   PFUNC_CMP value_cmp_function = nullptr,
 317                   const void* value_data = nullptr) const;
 318
 319   /*
 320    * Sorting.
 321    */
 322   static int SortRegularAscending(const Variant& v1, const Variant& v2,
 323                                   const void* data);
 324   static int SortNumericAscending(const Variant& v1, const Variant& v2,
 325                                   const void* data);
 326   static int SortStringAscending(const Variant& v1, const Variant& v2,
 327                                  const void* data);
 328   static int SortStringAscendingCase(const Variant& v1, const Variant& v2,
 329                                      const void* data);
 330   static int SortLocaleStringAscending(const Variant& v1, const Variant& v2,
 331                                        const void* data);
 332
 333   static int SortRegularDescending(const Variant& v1, const Variant& v2,
 334                                    const void* data);
 335   static int SortNumericDescending(const Variant& v1, const Variant& v2,
 336                                    const void* data);
 337   static int SortStringDescending(const Variant& v1, const Variant& v2,
 338                                   const void* data);
 339   static int SortStringDescendingCase(const Variant& v1, const Variant& v2,
 340                                       const void* data);
 341   static int SortLocaleStringDescending(const Variant& v1, const Variant& v2,
 342                                         const void* data);
 343
 344   static int SortNaturalAscending(const Variant& v1, const Variant& v2,
 345                                   const void* data);
 346   static int SortNaturalDescending(const Variant& v1, const Variant& v2,
 347                                    const void* data);
 348   static int SortNaturalCaseAscending(const Variant& v1, const Variant& v2,
 349                                       const void* data);
 350   static int SortNaturalCaseDescending(const Variant& v1, const Variant& v2,
 351                                        const void* data);
 352
 353   void sort(PFUNC_CMP cmp_func, bool by_key, bool renumber,
 354             const void* data = nullptr);
 355
 356   /*
 357    * Sort multiple arrays at once similar to how ORDER BY clause works in SQL.
 358    */
 359   struct SortData {
 360     Variant* original;
 361     const Array*   array;
 362     bool           by_key;
 363     PFUNC_CMP      cmp_func;
 364     const void*    data;
 365     std::vector<ssize_t> positions;
 366   };
 367   static bool MultiSort(std::vector<SortData>& data);
 368
 369   static void SortImpl(std::vector<int>& indices, const Array& source,
 370                        Array::SortData& opaque,
 371                        Array::PFUNC_CMP cmp_func,
 372                        bool by_key, const void* data = nullptr);
 373
 374   /*
 375    * Type conversions.
 376    */
 377   bool toBoolean() const { return m_arr && !m_arr->empty(); }
 378   int8_t  toByte()  const { return toBoolean() ? 1 : 0; }
 379   int16_t toInt16() const { return toBoolean() ? 1 : 0; }
 380   int32_t toInt32() const { return toBoolean() ? 1 : 0; }
 381   int64_t toInt64() const { return toBoolean() ? 1 : 0; }
 382   double toDouble() const { return toBoolean() ? 1.0 : 0.0; }
 383   String toString() const;
 384
 385   /*
 386    * Enable the legacy behavior bit on this array
 387    */
 388   void setLegacyArray(bool);
 389
 390   /*
 391    * Comparisons.
 392    */
 393   bool same(const Array& v2) const;
 394   bool equal(const Array& v2) const;
 395   bool less(const Array& v2, bool flip = false) const;
 396   bool less(const Variant& v2) const;
 397   bool more(const Array& v2, bool flip = true) const;
 398   bool more(const Variant& v2) const;
 399   int compare(const Array& v2, bool flip = false) const;
 400
 401   /////////////////////////////////////////////////////////////////////////////
 402   // Element rval/lval.
 403
 404 #define FOR_EACH_KEY_TYPE(...)    \
 405   C(TypedValue, __VA_ARGS__)            \
 406   I(int, __VA_ARGS__)             \
 407   I(int64_t, __VA_ARGS__)         \
 408   V(const String&, __VA_ARGS__)   \
 409   V(const Variant&, __VA_ARGS__)  \
 410   D(double, __VA_ARGS__)
 411
 412   /*
 413    * Get a refcounted copy of the element at `key'.
 414    */
 415   Variant operator[](TypedValue key) const;
 416   Variant operator[](int key) const;
 417   Variant operator[](int64_t key) const;
 418   Variant operator[](const String& key) const;
 419   Variant operator[](const Variant& key) const;
 420   Variant operator[](double key) const = delete;
 421   Variant operator[](const char*) const = delete;
 422
 423 #define C(key_t, name, ret_t, cns) \
 424   ret_t name(key_t, Flags = Flags::None) cns;
 425 #define V C
 426 #define I V
 427 #define D(key_t, name, ret_t, cns) \
 428   ret_t name(key_t, Flags = Flags::None) cns = delete;
 429
 430   /*
 431    * Get an rval to the element at `key'.
 432    */
 433   FOR_EACH_KEY_TYPE(rval, tv_rval, const)
 434
 435   /*
 436    * Get an lval to the element at `key'.
 437    *
 438    * This is ArrayData::lval, with COW and escalation handled internally.
 439    *
 440    * lvalForce() has the legacy lval() behavior---if the key is not present,
 441    * it writes null, then returns the lval.
 442    */
 443   FOR_EACH_KEY_TYPE(lval, tv_lval, )
 444   FOR_EACH_KEY_TYPE(lvalForce, tv_lval, )
 445
 446 #undef D
 447 #undef I
 448 #undef V
 449 #undef C
 450
 451   /////////////////////////////////////////////////////////////////////////////
 452   // Element access and mutation.
 453
 454 #define C(key_t, ret_t, name, cns)  ret_t name(key_t, bool isKey = false) cns;
 455 #define V C
 456 #define I(key_t, ret_t, name, cns)  ret_t name(key_t) cns;
 457 #define D(key_t, ret_t, name, cns)  ret_t name(key_t) cns = delete;
 458
 459   /*
 460    * Membership.
 461    */
 462   FOR_EACH_KEY_TYPE(bool, exists, const)
 463
 464   /*
 465    * Remove an element.
 466    */
 467   FOR_EACH_KEY_TYPE(void, remove, )
 468
 469 #undef D
 470 #undef I
 471 #undef V
 472 #undef C
 473
 474 #define C(key_t, name, value_t) \
 475   void name(key_t k, value_t v, bool isKey = false);
 476 #define V C
 477 #define I(key_t, name, value_t) void name(key_t k, value_t v);
 478 #define D(key_t, name, value_t) void name(key_t k, value_t v) = delete;
 479
 480   /*
 481    * Set an element to `v'.
 482    */
 483   FOR_EACH_KEY_TYPE(set, TypedValue)
 484
 485 #undef D
 486 #undef I
 487 #undef V
 488 #undef C
 489
 490 #define C(key_t, name, value_t)
 491 #define V(key_t, name, value_t) \
 492   void name(key_t k, value_t v, bool isKey = false);
 493 #define I(key_t, name, value_t) void name(key_t k, value_t v);
 494 #define D(key_t, name, value_t) void name(key_t k, value_t v) = delete;
 495
 496   /*
 497    * Variant overloads.
 498    */
 499   FOR_EACH_KEY_TYPE(set, const Variant&)
 500
 501 #undef D
 502 #undef I
 503 #undef V
 504 #undef C
 505
 506   /*
 507    * Append or prepend an element, with semantics like set().
 508    */
 509   void append(TypedValue v);
 510   void append(const Variant& v);
 511   void prepend(TypedValue v);
 512   void prepend(const Variant& v);
 513
 514   /*
 515    * Remove all elements.
 516    */
 517   void clear() { operator=(Create()); }
 518
 519   /*
 520    * Stack/queue-like functions.
 521    */
 522   Variant pop();
 523   Variant dequeue();
 524
 525 #undef FOR_EACH_KEY_TYPE
 526
 527   /////////////////////////////////////////////////////////////////////////////
 528
 529 private:
 530   Array(ArrayData* ad, NoIncRef) : m_arr(ad, NoIncRef{}) {}
 531
 532   Array& plusImpl(ArrayData* data);
 533   Array& mergeImpl(ArrayData* data);
 534   Array diffImpl(const Array& array, bool by_key, bool by_value, bool match,
 535                  PFUNC_CMP key_cmp_function, const void* key_data,
 536                  PFUNC_CMP value_cmp_function, const void* value_data) const;
 537
 538   template<typename T> tv_rval rvalImpl(const T& key, Flags) const;
 539   template<typename T> tv_lval lvalImpl(const T& key, Flags);
 540   template<typename T> tv_lval lvalForceImpl(const T& key, Flags);
 541
 542   template<typename T> bool existsImpl(const T& key) const;
 543   template<typename T> void removeImpl(const T& key);
 544   template<typename T> void setImpl(const T& key, TypedValue v);
 545
 546   static void compileTimeAssertions();
 547
 548   /////////////////////////////////////////////////////////////////////////////
 549
 550 private:
 551   Ptr m_arr;
 552 };
 553
 554 ///////////////////////////////////////////////////////////////////////////////
 555
 556 struct ArrNR {
 557   explicit ArrNR(ArrayData* data = nullptr) { m_px = data; }
 558   explicit ArrNR(const ArrayData *ad) : m_px(const_cast<ArrayData*>(ad)) {}
 559
 560   ArrNR(const ArrNR& a) { m_px = a.m_px; }
 561
 562   ~ArrNR() {
 563     if (debug) {
 564       m_px = reinterpret_cast<ArrayData*>(0xdeadbeeffaceb004);
 565     }
 566   }
 567
 568   ArrayData* get() const { return m_px; }
 569
 570   operator const Array&() const { return asArray(); }
 571
 572   Array& asArray() {
 573     return *reinterpret_cast<Array*>(this); // XXX
 574   }
 575   const Array& asArray() const {
 576     return const_cast<ArrNR*>(this)->asArray();
 577   }
 578
 579 private:
 580   static void compileTimeAssertions();
 581
 582 private:
 583   ArrayData* m_px;
 584 };
 585
 586 ///////////////////////////////////////////////////////////////////////////////
 587
 588 /*
 589  * An Array wrapper that doesn't run a destructor unless you
 590  * explicitly ask it to.
 591  *
 592  * This is used for the dynPropTable in ExecutionContext, so that at
 593  * sweep time we don't run these destructors.
 594  */
 595 struct ArrayNoDtor {
 596   /* implicit */ ArrayNoDtor(ArrayData* table) { new (&m_arr) Array(table); }
 597   ArrayNoDtor() { new (&m_arr) Array(); }
 598   ArrayNoDtor(ArrayNoDtor&& o) noexcept {
 599     new (&m_arr) Array(std::move(o.m_arr));
 600   }
 601   ~ArrayNoDtor() {}
 602   Array& arr() { return m_arr; }
 603   const Array& arr() const { return m_arr; }
 604   void destroy() { m_arr.~Array(); }
 605 private:
 606   union { Array m_arr; };
 607 };
 608
 609 ///////////////////////////////////////////////////////////////////////////////
 610
 611 ALWAYS_INLINE Array empty_array() {
 612   return Array::attach(ArrayData::Create());
 613 }
 614
 615 ALWAYS_INLINE Array empty_varray() {
 616   return Array::attach(ArrayData::CreateVArray());
 617 }
 618
 619 ALWAYS_INLINE Array empty_darray() {
 620   return Array::attach(ArrayData::CreateDArray());
 621 }
 622
 623 ALWAYS_INLINE Array empty_vec_array() {
 624   return Array::attach(ArrayData::CreateVec());
 625 }
 626
 627 ALWAYS_INLINE Array empty_dict_array() {
 628   return Array::attach(ArrayData::CreateDict());
 629 }
 630
 631 ALWAYS_INLINE Array empty_keyset() {
 632   return Array::attach(ArrayData::CreateKeyset());
 633 }
 634
 635 ///////////////////////////////////////////////////////////////////////////////
 636
 637 /*
 638  * Type-pun a referenced ArrayData* as an Array&.
 639  *
 640  * This lets us take advantage of Array's CoW and escalation machinery to
 641  * possibly mutate `ad', without the overhead or behavioral change of
 642  * refcounting.
 643  *
 644  * asArrRef() unconditionally removes Persistent bits from the referenced type.
 645  */
 646 ALWAYS_INLINE Array& asArrRef(tv_lval tv) {
 647   assertx(tvIsArrayLike(tv));
 648   tv.type() = tv.val().parr->toDataType();
 649   return *reinterpret_cast<Array*>(&val(tv).parr);
 650 }
 651
 652 ALWAYS_INLINE const Array& asCArrRef(tv_rval tv) {
 653   assertx(tvIsArrayLike(tv));
 654   return *reinterpret_cast<const Array*>(&val(tv).parr);
 655 }
 656
 657 template <IntishCast IC = IntishCast::None>
 658 ALWAYS_INLINE Array toArray(tv_rval rval) {
 659   if (isArrayLikeType(type(rval))) {
 660     return Array{assert_not_null(val(rval).parr)};
 661   }
 662   return Array::attach(tvCastToArrayLikeData<IC>(*rval));
 663 }
 664
 665 ///////////////////////////////////////////////////////////////////////////////
 666 }
 667
 668 #endif