hphp/runtime/base/array/array_data.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 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_DATA_H_
  18 #define incl_HPHP_ARRAY_DATA_H_
  19
  20 #include "hphp/runtime/base/util/countable.h"
  21 #include "hphp/runtime/base/types.h"
  22 #include "hphp/runtime/base/macros.h"
  23 #include <climits>
  24
  25 namespace HPHP {
  26 ///////////////////////////////////////////////////////////////////////////////
  27
  28 class SharedVariant;
  29 struct TypedValue;
  30 class HphpArray;
  31
  32 /**
  33  * Base class/interface for all types of specialized array data.
  34  */
  35 class ArrayData : public Countable {
  36  public:
  37   enum class AllocationMode : bool { smart, nonSmart };
  38
  39   // enum of possible array types, so we can guard nonvirtual
  40   // fast paths in runtime code.
  41   enum class ArrayKind : uint8_t {
  42     kHphpArray,
  43     kSharedMap,
  44     kNameValueTableWrapper,
  45     kArrayShell,
  46   };
  47
  48 public:
  49   static const ssize_t invalid_index = -1;
  50
  51   explicit ArrayData(ArrayKind kind)
  52     : m_size(-1)
  53     , m_strongIterators(nullptr)
  54     , m_pos(0)
  55     , m_kind(kind)
  56     , m_allocMode(AllocationMode::smart)
  57   {}
  58
  59   explicit ArrayData(ArrayKind kind, AllocationMode m)
  60       : m_size(-1)
  61       , m_strongIterators(nullptr)
  62       , m_pos(0)
  63       , m_kind(kind)
  64       , m_allocMode(m)
  65   {}
  66
  67   ArrayData(ArrayKind kind, AllocationMode m, uint size)
  68       : m_size(size)
  69       , m_strongIterators(nullptr)
  70       , m_pos(size ? 0 : ArrayData::invalid_index)
  71       , m_kind(kind)
  72       , m_allocMode(m)
  73   {}
  74
  75   ArrayData(const ArrayData *src, ArrayKind kind,
  76             AllocationMode m = AllocationMode::smart)
  77     : m_strongIterators(nullptr)
  78     , m_pos(src->m_pos)
  79     , m_kind(src->m_kind)
  80     , m_allocMode(m)
  81   {}
  82
  83   static HphpArray* Make(uint capacity);
  84   static HphpArray* Make(uint size, const TypedValue*);
  85
  86   virtual ~ArrayData() {
  87     // If there are any strong iterators pointing to this array, they need
  88     // to be invalidated.
  89     freeStrongIterators();
  90   }
  91
  92   /**
  93    * Create a new ArrayData with specified array element(s).
  94    */
  95   static ArrayData *Create();
  96   static ArrayData *Create(CVarRef value);
  97   static ArrayData *Create(CVarRef name, CVarRef value);
  98   static ArrayData *CreateRef(CVarRef value);
  99   static ArrayData *CreateRef(CVarRef name, CVarRef value);
 100
 101   /**
 102    * Type conversion functions. All other types are handled inside Array class.
 103    */
 104   Object toObject() const;
 105
 106   /**
 107    * Array interface functions.
 108    *
 109    * 1. For functions that return ArrayData pointers, these are the ones that
 110    *    can potentially escalate into a different ArrayData type. Return NULL
 111    *    if no escalation is needed.
 112    *
 113    * 2. All functions with a "key" parameter are type-specialized.
 114    */
 115
 116   /**
 117    * For SmartAllocator.
 118    *
 119    *   NB: *Not* virtual. ArrayData knows about its only subclasses.
 120    */
 121   void release();
 122
 123   /**
 124    * Whether this array has any element.
 125    */
 126   bool empty() const {
 127     return size() == 0;
 128   }
 129
 130   /**
 131    * return the array kind for fast typechecks
 132    */
 133   ArrayKind kind() const {
 134     return (ArrayKind)m_kind;
 135   }
 136
 137   /**
 138    * Number of elements this array has.
 139    */
 140   ssize_t size() const {
 141     if (UNLIKELY((int)m_size) < 0) return vsize();
 142     return m_size;
 143   }
 144
 145   /**
 146    * Number of elements this array has.
 147    */
 148   virtual ssize_t vsize() const = 0;
 149
 150   /**
 151    * For ArrayIter to work. Get key or value at position "pos".
 152    */
 153   virtual Variant getKey(ssize_t pos) const = 0;
 154   virtual Variant getValue(ssize_t pos) const = 0;
 155
 156   /**
 157    * getValueRef() gets a reference to value at position "pos".
 158    */
 159   virtual CVarRef getValueRef(ssize_t pos) const = 0;
 160
 161   /*
 162    * Return true for array types that don't have COW semantics.
 163    */
 164   virtual bool noCopyOnWrite() const { return false; }
 165
 166   /*
 167    * Specific derived class type querying operators.
 168    */
 169   bool isArrayShell() const { return m_kind == ArrayKind::kArrayShell; }
 170   bool isHphpArray() const { return m_kind == ArrayKind::kHphpArray; }
 171   bool isSharedMap() const { return m_kind == ArrayKind::kSharedMap; }
 172   bool isNameValueTableWrapper() const {
 173     return m_kind == ArrayKind::kNameValueTableWrapper;
 174   }
 175
 176
 177   /*
 178    * Returns whether or not this array contains "vector-like" data.
 179    * I.e. all the keys are contiguous increasing integers.
 180    */
 181   virtual bool isVectorData() const = 0;
 182
 183   /**
 184    * Whether or not this array has a referenced Variant or Object appearing
 185    * twice. This is mainly for APC to decide whether to serialize an array.
 186    * Also used for detecting whether there is serializable object in the tree.
 187    */
 188   bool hasInternalReference(PointerSet &seen,
 189                             bool detectSerializable = false) const;
 190
 191   /**
 192    * Position-based iterations.
 193    */
 194   virtual Variant reset();
 195   virtual Variant prev();
 196   virtual Variant current() const;
 197   virtual Variant next();
 198   virtual Variant end();
 199   virtual Variant key() const;
 200   virtual Variant value(int32_t &pos) const;
 201   virtual Variant each();
 202
 203   bool isHead()            const { return m_pos == iter_begin(); }
 204   bool isTail()            const { return m_pos == iter_end(); }
 205   virtual bool isInvalid() const { return m_pos == invalid_index; }
 206
 207   /**
 208    * Testing whether a key exists.
 209    */
 210   virtual bool exists(int64_t k) const = 0;
 211   virtual bool exists(const StringData* k) const = 0;
 212
 213   /**
 214    * Getting value at specified key.
 215    */
 216   virtual CVarRef get(int64_t k, bool error = false) const = 0;
 217   virtual CVarRef get(const StringData* k, bool error = false) const = 0;
 218
 219   /**
 220    * Interface for VM helpers.  ArrayData implements generic versions
 221    * using the other ArrayData api; subclasses may do better.
 222    */
 223   virtual TypedValue* nvGet(int64_t k) const;
 224   virtual TypedValue* nvGet(const StringData* k) const;
 225   virtual void nvGetKey(TypedValue* out, ssize_t pos);
 226   virtual TypedValue* nvGetValueRef(ssize_t pos);
 227   virtual TypedValue* nvGetCell(int64_t ki) const;
 228   virtual TypedValue* nvGetCell(const StringData* k) const;
 229
 230   /**
 231    * Getting l-value (that Variant pointer) at specified key. Return NULL if
 232    * escalation is not needed, or an escalated array data.
 233    */
 234   virtual ArrayData *lval(int64_t k, Variant *&ret, bool copy,
 235                           bool checkExist = false) = 0;
 236   virtual ArrayData *lval(StringData* k, Variant *&ret, bool copy,
 237                           bool checkExist = false) = 0;
 238
 239   /**
 240    * Getting l-value (that Variant pointer) of a new element with the next
 241    * available integer key. Return NULL if escalation is not needed, or an
 242    * escalated array data. Note that adding a new element with the next
 243    * available integer key may fail, in which case ret is set to point to
 244    * the lval blackhole (see Variant::lvalBlackHole() for details).
 245    */
 246   virtual ArrayData *lvalNew(Variant *&ret, bool copy) = 0;
 247
 248   /**
 249    * Helper functions used for getting a reference to elements of
 250    * the dynamic property array in ObjectData or the local cache array
 251    * in ShardMap.
 252    */
 253   virtual ArrayData *createLvalPtr(StringData* k, Variant *&ret, bool copy);
 254   virtual ArrayData *getLvalPtr(StringData* k, Variant *&ret, bool copy);
 255
 256   /**
 257    * Setting a value at specified key. If "copy" is true, make a copy first
 258    * then set the value. Return NULL if escalation is not needed, or an
 259    * escalated array data.
 260    */
 261   virtual ArrayData *set(int64_t k, CVarRef v, bool copy) = 0;
 262   virtual ArrayData *set(StringData* k, CVarRef v, bool copy) = 0;
 263
 264   virtual ArrayData *setRef(int64_t k, CVarRef v, bool copy) = 0;
 265   virtual ArrayData *setRef(StringData* k, CVarRef v, bool copy) = 0;
 266
 267   /**
 268    * The same as set(), but with the precondition that the key does
 269    * not already exist in this array.  (This is to allow more
 270    * efficient implementation of this case in some derived classes.)
 271    */
 272   virtual ArrayData *add(int64_t k, CVarRef v, bool copy);
 273   virtual ArrayData *add(StringData* k, CVarRef v, bool copy);
 274
 275   /*
 276    * Same semantics as lval(), except with the precondition that the
 277    * key doesn't already exist in the array.
 278    */
 279   virtual ArrayData *addLval(int64_t k, Variant *&ret, bool copy);
 280   virtual ArrayData *addLval(StringData* k, Variant *&ret, bool copy);
 281
 282   /**
 283    * Remove a value at specified key. If "copy" is true, make a copy first
 284    * then remove the value. Return NULL if escalation is not needed, or an
 285    * escalated array data.
 286    */
 287   virtual ArrayData *remove(int64_t k, bool copy) = 0;
 288   virtual ArrayData *remove(const StringData* k, bool copy) = 0;
 289
 290   /**
 291    * Inline accessors that convert keys to StringData* before delegating to
 292    * the virtual method.
 293    */
 294   bool exists(CStrRef k) const;
 295   bool exists(CVarRef k) const;
 296   CVarRef get(CStrRef k, bool error = false) const;
 297   CVarRef get(CVarRef k, bool error = false) const;
 298   ArrayData *lval(CStrRef k, Variant *&ret, bool copy, bool checkExist=false);
 299   ArrayData *lval(CVarRef k, Variant *&ret, bool copy, bool checkExist=false);
 300   ArrayData *createLvalPtr(CStrRef k, Variant *&ret, bool copy);
 301   ArrayData *getLvalPtr(CStrRef k, Variant *&ret, bool copy);
 302   ArrayData *set(CStrRef k, CVarRef v, bool copy);
 303   ArrayData *set(CVarRef k, CVarRef v, bool copy);
 304   ArrayData *setRef(CStrRef k, CVarRef v, bool copy);
 305   ArrayData *setRef(CVarRef k, CVarRef v, bool copy);
 306   ArrayData *add(CStrRef k, CVarRef v, bool copy);
 307   ArrayData *add(CVarRef k, CVarRef v, bool copy);
 308   ArrayData *addLval(CStrRef k, Variant *&ret, bool copy);
 309   ArrayData *addLval(CVarRef k, Variant *&ret, bool copy);
 310   ArrayData *remove(CStrRef k, bool copy);
 311   ArrayData *remove(CVarRef k, bool copy);
 312
 313   virtual ssize_t iter_begin() const;
 314   virtual ssize_t iter_end() const;
 315   virtual ssize_t iter_advance(ssize_t prev) const;
 316   virtual ssize_t iter_rewind(ssize_t prev) const;
 317
 318   /**
 319    * Mutable iteration APIs
 320    *
 321    * The following six methods are used for mutable iteration. For all methods
 322    * except newFullPos(), it is the caller's responsibility to ensure that the
 323    * specified FullPos 'fp' is registered with this array and hasn't already
 324    * been freed.
 325    */
 326
 327   /**
 328    * Create a new mutable iterator and register it with this array (the mutable
 329    * iterator will be stored in 'fp'). The new iterator will point to whatever
 330    * element the array's internal cursor currently points to. Note that the
 331    * array keeps track of all mutable iterators that have registered with it.
 332    *
 333    * A mutable iterator remains live until one of the following happens:
 334    *   (1) The mutable iterator is freed by calling the freeFullPos() method.
 335    *   (2) The array's refcount drops to 0 and the array frees all mutable
 336    *       iterators that were registered with it.
 337    *   (3) Some other kind of "invalidation" event happens to the array that
 338    *       causes it to free all mutable iterators that were registered with
 339    *       it (ex. array_shift() is called on the array).
 340    */
 341   void newFullPos(FullPos &fp);
 342
 343   /**
 344    * Frees a mutable iterator that was registered with this array.
 345    */
 346   void freeFullPos(FullPos &fp);
 347
 348   /**
 349    * Checks if a mutable iterator points to a valid element within this array.
 350    * This will return false if the iterator points past the last element, or
 351    * if the iterator points before the first element.
 352    */
 353   virtual bool validFullPos(const FullPos& fp) const;
 354
 355   /**
 356    * Advances the mutable iterator to the next element in the array. Returns
 357    * false if the iterator has moved past the last element, otherwise returns
 358    * true.
 359    */
 360   virtual bool advanceFullPos(FullPos& fp);
 361
 362   virtual CVarRef endRef();
 363
 364   virtual ArrayData* escalateForSort();
 365   virtual void ksort(int sort_flags, bool ascending);
 366   virtual void sort(int sort_flags, bool ascending);
 367   virtual void asort(int sort_flags, bool ascending);
 368   virtual void uksort(CVarRef cmp_function);
 369   virtual void usort(CVarRef cmp_function);
 370   virtual void uasort(CVarRef cmp_function);
 371
 372   /**
 373    * Make a copy of myself.
 374    *
 375    * The nonSmartCopy() version means not to use the smart allocator.
 376    * Is only implemented for array types that need to be able to go
 377    * into the static array list.
 378    */
 379   virtual ArrayData *copy() const = 0;
 380   virtual ArrayData *copyWithStrongIterators() const;
 381   virtual ArrayData *nonSmartCopy() const;
 382
 383   /**
 384    * Append a value to the array. If "copy" is true, make a copy first
 385    * then append the value. Return NULL if escalation is not needed, or an
 386    * escalated array data.
 387    */
 388   virtual ArrayData *append(CVarRef v, bool copy) = 0;
 389   virtual ArrayData *appendRef(CVarRef v, bool copy) = 0;
 390
 391   /**
 392    * Similar to append(v, copy), with reference in v preserved.
 393    */
 394   virtual ArrayData *appendWithRef(CVarRef v, bool copy) = 0;
 395
 396   /**
 397    * Implementing array appending and merging. If "copy" is true, make a copy
 398    * first then append/merge arrays. Return NULL if escalation is not needed,
 399    * or an escalated array data.
 400    */
 401   virtual ArrayData *plus(const ArrayData *elems, bool copy) = 0;
 402   virtual ArrayData *merge(const ArrayData *elems, bool copy) = 0;
 403
 404   /**
 405    * Stack function: pop the last item and return it.
 406    */
 407   virtual ArrayData *pop(Variant &value);
 408
 409   /**
 410    * Queue function: remove the 1st item and return it.
 411    */
 412   virtual ArrayData *dequeue(Variant &value);
 413
 414   /**
 415    * Array function: prepend a new item.
 416    */
 417   virtual ArrayData *prepend(CVarRef v, bool copy) = 0;
 418
 419   /**
 420    * Only map classes need this. Re-index all numeric keys to start from 0.
 421    */
 422   virtual void renumber() {}
 423
 424   virtual void onSetEvalScalar() { assert(false);}
 425
 426   /**
 427    * Serialize this array. We could have made this virtual function to ask
 428    * sub-classes to implement it specifically, but since this is not a critical
 429    * function to optimize, we implement it in a generic way in this base class.
 430    * Then all the sudden we find out all Zend HashTable functions are similar
 431    * to implementing array functions in this base class than utilizing a type
 432    * specialized implementation, which is normally more optimized.
 433    */
 434   void serialize(VariableSerializer *serializer,
 435                  bool skipNestCheck = false) const;
 436
 437   virtual void dump();
 438   virtual void dump(std::string &out);
 439   virtual void dump(std::ostream &os);
 440
 441   /**
 442    * Comparisons.
 443    */
 444   int compare(const ArrayData *v2) const;
 445   bool equal(const ArrayData *v2, bool strict) const;
 446
 447   void setPosition(ssize_t p) { m_pos = p; }
 448
 449   virtual ArrayData *escalate() const {
 450     return const_cast<ArrayData *>(this);
 451   }
 452
 453   static ArrayData *GetScalarArray(ArrayData *arr,
 454                                    const StringData *key = nullptr);
 455  private:
 456   void serializeImpl(VariableSerializer *serializer) const;
 457   static void compileTimeAssertions() {
 458     static_assert(offsetof(ArrayData, _count) == FAST_REFCOUNT_OFFSET,
 459                   "Offset of _count in ArrayData must be FAST_REFCOUNT_OFFSET");
 460   }
 461  protected:
 462   void freeStrongIterators();
 463   static void moveStrongIterators(ArrayData* dest, ArrayData* src);
 464   FullPos* strongIterators() const {
 465     return m_strongIterators;
 466   }
 467   void setStrongIterators(FullPos* p) {
 468     m_strongIterators = p;
 469   }
 470   // error-handling helpers
 471   static CVarRef getNotFound(int64_t k);
 472   static CVarRef getNotFound(const StringData* k);
 473   static CVarRef getNotFound(CStrRef k);
 474   static CVarRef getNotFound(CVarRef k);
 475   static TypedValue* nvGetNotFound(int64_t k);
 476   static TypedValue* nvGetNotFound(const StringData* k);
 477
 478   static bool IsValidKey(CStrRef k);
 479   static bool IsValidKey(CVarRef k);
 480   static bool IsValidKey(const StringData* k) { return k; }
 481
 482  protected:
 483   // Layout starts with 64 bits for vtable, then 32 bits for m_count
 484   // from Countable base, then...
 485   uint m_size;
 486 private:
 487   FullPos* m_strongIterators; // head of linked list
 488 protected:
 489   int32_t m_pos;
 490   const ArrayKind m_kind;
 491   const AllocationMode m_allocMode;
 492
 493  public: // for the JIT
 494   static uint32_t getKindOff() {
 495     return (uintptr_t)&((ArrayData*)0)->m_kind;
 496   }
 497 };
 498
 499 ALWAYS_INLINE inline
 500 void decRefArr(ArrayData* arr) {
 501   if (arr->decRefCount() == 0) arr->release();
 502 }
 503
 504 ///////////////////////////////////////////////////////////////////////////////
 505 }
 506
 507 #endif // incl_HPHP_ARRAY_DATA_H_