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