hphp/runtime/base/type-array.h

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