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