hphp/runtime/base/empty-array.cpp

   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 #include "hphp/runtime/base/empty-array.h"
  17
  18 #include <utility>
  19 #include <type_traits>
  20
  21 #include "hphp/util/assertions.h"
  22
  23 #include "hphp/runtime/base/array-init.h"
  24 #include "hphp/runtime/base/tv-helpers.h"
  25 #include "hphp/runtime/base/array-data.h"
  26 #include "hphp/runtime/base/type-variant.h"
  27 #include "hphp/runtime/base/hphp-array.h"
  28 #include "hphp/runtime/base/hphp-array-defs.h"
  29
  30 namespace HPHP {
  31
  32 //////////////////////////////////////////////////////////////////////
  33
  34 std::aligned_storage<
  35   sizeof(ArrayData),
  36   alignof(ArrayData)
  37 >::type s_theEmptyArray;
  38
  39 struct EmptyArray::Initializer {
  40   Initializer() {
  41     void* vpEmpty = &s_theEmptyArray;
  42
  43     auto const ad   = static_cast<ArrayData*>(vpEmpty);
  44     ad->m_kind      = ArrayData::kEmptyKind;
  45     ad->m_size      = 0;
  46     ad->m_pos       = ArrayData::invalid_index;
  47     ad->m_count     = 0;
  48     ad->setStatic();
  49   }
  50 };
  51 EmptyArray::Initializer EmptyArray::s_initializer;
  52
  53 //////////////////////////////////////////////////////////////////////
  54
  55 void EmptyArray::Release(ArrayData*) {
  56   always_assert(!"never try to free the empty array");
  57 }
  58
  59 /*
  60  * Used for NvGetInt, NvGetStr.  (We never contain the string or int.)
  61  *
  62  * Used for GetAPCHandle (we don't have one).
  63  */
  64 void* EmptyArray::ReturnNull(...) {
  65   return nullptr;
  66 }
  67
  68 /*
  69  * Used for ExistsInt, ExistsStr.  (We never contain the int or string.)
  70  */
  71 bool EmptyArray::ReturnFalse(...) {
  72   return false;
  73 }
  74
  75 /*
  76  * Used for IsVectorData (we're always trivially a vector).
  77  *
  78  * Used for Uksort, Usort, Uasort.  These functions return false only
  79  * if the user compare function modified they array, which it can't
  80  * here because we don't call it.
  81  */
  82 bool EmptyArray::ReturnTrue(...) {
  83   return true;
  84 }
  85
  86 void EmptyArray::NvGetKey(const ArrayData*, TypedValue* out, ssize_t pos) {
  87   // We have no valid positions---no one should call this function.
  88   not_reached();
  89 }
  90
  91 const Variant& EmptyArray::GetValueRef(const ArrayData* ad, ssize_t pos) {
  92   // We have no valid positions---no one should call this function.
  93   not_reached();
  94 }
  95
  96 /*
  97  * Used for RemoveInt, RemoveStr.  We don't every have the int or str,
  98  * so even if copy is true we can just return the same array.
  99  *
 100  * Used for EscalateForSort---we are already sorted by any imaginable
 101  * method of sorting, so the sort functions are no-ops, so we don't
 102  * need to copy.
 103  *
 104  * (TODO: verify nothing assumes that we /must/ copy when copy is
 105  * true.)
 106  */
 107 ArrayData* EmptyArray::ReturnFirstArg(ArrayData* a, ...) {
 108   return a;
 109 }
 110
 111 /*
 112  * Used for IterBegin and IterEnd.  We always return the invalid_index.
 113  */
 114 ssize_t EmptyArray::ReturnInvalidIndex(const ArrayData*) {
 115   return ArrayData::invalid_index;
 116 }
 117
 118 // Iterators can't be advanced or rewinded, because we have no valid
 119 // iterators.
 120 ssize_t EmptyArray::IterAdvance(const ArrayData*, ssize_t prev) {
 121   not_reached();
 122 }
 123 ssize_t EmptyArray::IterRewind(const ArrayData*, ssize_t prev) {
 124   not_reached();
 125 }
 126
 127 // Strong iterating the empty array doesn't give back any elements.
 128 bool EmptyArray::ValidMArrayIter(const ArrayData*, const MArrayIter& fp) {
 129   return false;
 130 }
 131 bool EmptyArray::AdvanceMArrayIter(ArrayData*, MArrayIter& fp) {
 132   not_reached();
 133 }
 134
 135 /*
 136  * Don't do anything.
 137  *
 138  * Used for Ksort, Sort, and Asort.  The empty array is already
 139  * sorted, and these functions have no other side-effects.
 140  *
 141  * Used for Renumber---we're trivially numbered properly.
 142  */
 143 void EmptyArray::NoOp(...) {}
 144
 145 // We're always already a static array.
 146 void EmptyArray::OnSetEvalScalar(ArrayData*) { not_reached(); }
 147 ArrayData* EmptyArray::NonSmartCopy(const ArrayData* ad) { not_reached(); }
 148
 149 //////////////////////////////////////////////////////////////////////
 150
 151 NEVER_INLINE
 152 ArrayData* EmptyArray::Copy(const ArrayData*) {
 153   auto const mask = HphpArray::SmallMask;            // 3
 154   auto const cap  = HphpArray::computeMaxElms(mask); // 3
 155   auto const ad   = smartAllocArray(cap, mask);
 156
 157   ad->m_kindAndSize = ArrayData::kPackedKind;
 158   ad->m_posAndCount = static_cast<uint32_t>(ArrayData::invalid_index);
 159   ad->m_capAndUsed  = cap;
 160   ad->m_tableMask   = mask;
 161
 162   assert(ad->m_kind == ArrayData::kPackedKind);
 163   assert(ad->m_size == 0);
 164   assert(ad->m_pos == ArrayData::invalid_index);
 165   assert(ad->m_count == 0);
 166   assert(ad->m_cap == cap);
 167   assert(ad->m_used == 0);
 168   assert(ad->checkInvariants());
 169   return ad;
 170 }
 171
 172 ArrayData* EmptyArray::CopyWithStrongIterators(const ArrayData* ad) {
 173   // We can never have strong iterators, so we don't need to do
 174   // anything extra.
 175   return Copy(ad);
 176 }
 177
 178 //////////////////////////////////////////////////////////////////////
 179
 180 /*
 181  * Note: if you try to tail-call these helper routines, gcc will
 182  * unfortunately still generate functions with frames and and makes a
 183  * call instead of a jump.  It's because of std::pair (and is still
 184  * the case if you return a custom struct).
 185  *
 186  * For now we're leaving this, because it's essentially free for these
 187  * routines to leave the lval pointer in the second return register,
 188  * and it seems questionable to clone the whole function just to avoid
 189  * the frame creation in these callers.  (It works to reinterpret_cast
 190  * these functions to one that returns ArrayData* instead of a pair in
 191  * the cases we don't need the second value, but this seems a tad too
 192  * sketchy for probably-unmeasurable benefits.  I'll admit I didn't
 193  * try to measure it though... ;)
 194  */
 195
 196 /*
 197  * Helper for empty array -> packed transitions.  Creates an array
 198  * with one element.  The element is transfered into the array (should
 199  * already be incref'd).
 200  */
 201 ALWAYS_INLINE
 202 std::pair<ArrayData*,TypedValue*> EmptyArray::MakePackedInl(TypedValue tv) {
 203   auto const mask = HphpArray::SmallMask;            // 3
 204   auto const cap  = HphpArray::computeMaxElms(mask); // 3
 205   auto const ad   = smartAllocArray(cap, mask);
 206
 207   ad->m_kindAndSize = uint64_t{1} << 32 | ArrayData::kPackedKind;
 208   ad->m_posAndCount = 0;
 209   ad->m_capAndUsed  = uint64_t{1} << 32 | cap;
 210   ad->m_tableMask   = mask;
 211
 212   auto& lval  = reinterpret_cast<HphpArray::Elm*>(ad + 1)[0].data;
 213   lval.m_data = tv.m_data;
 214   lval.m_type = tv.m_type;
 215
 216   assert(ad->m_kind == ArrayData::kPackedKind);
 217   assert(ad->m_size == 1);
 218   assert(ad->m_pos == 0);
 219   assert(ad->m_count == 0);
 220   assert(ad->m_cap == cap);
 221   assert(ad->m_used == 1);
 222   assert(ad->checkInvariants());
 223   return { ad, &lval };
 224 }
 225
 226 NEVER_INLINE
 227 std::pair<ArrayData*,TypedValue*> EmptyArray::MakePacked(TypedValue tv) {
 228   return MakePackedInl(tv);
 229 }
 230
 231 /*
 232  * Helper for creating a single-element mixed array with a string key.
 233  *
 234  * Note: the key is not already incref'd, but the value must be.
 235  */
 236 NEVER_INLINE
 237 std::pair<ArrayData*,TypedValue*>
 238 EmptyArray::MakeMixed(StringData* key, TypedValue val) {
 239   auto const mask = HphpArray::SmallMask;            // 3
 240   auto const cap  = HphpArray::computeMaxElms(mask); // 3
 241   auto const ad   = smartAllocArray(cap, mask);
 242
 243   ad->m_kindAndSize = uint64_t{1} << 32 | ArrayData::kMixedKind;
 244   ad->m_posAndCount = 0;
 245   ad->m_capAndUsed  = uint64_t{1} << 32 | cap;
 246   ad->m_tableMask   = mask;
 247   ad->m_nextKI      = 0;
 248   ad->m_hLoad       = 1;
 249
 250   auto const data = reinterpret_cast<HphpArray::Elm*>(ad + 1);
 251   auto const hash = reinterpret_cast<int32_t*>(data + cap);
 252
 253   assert(mask + 1 == 4);
 254   auto const emptyVal = int64_t{HphpArray::Empty};
 255   reinterpret_cast<int64_t*>(hash)[0] = emptyVal;
 256   reinterpret_cast<int64_t*>(hash)[1] = emptyVal;
 257
 258   auto const khash = key->hash();
 259   hash[khash & mask] = 0;
 260   data[0].setStrKey(key, khash);
 261
 262   auto& lval  = data[0].data;
 263   lval.m_data = val.m_data;
 264   lval.m_type = val.m_type;
 265
 266   assert(ad->m_kind == ArrayData::kMixedKind);
 267   assert(ad->m_size == 1);
 268   assert(ad->m_pos == 0);
 269   assert(ad->m_count == 0);
 270   assert(ad->m_cap == cap);
 271   assert(ad->m_used == 1);
 272   assert(ad->checkInvariants());
 273   return { ad, &lval };
 274 }
 275
 276 /*
 277  * Creating a single-element mixed array with a integer key.  The
 278  * value is already incref'd.
 279  */
 280 std::pair<ArrayData*,TypedValue*>
 281 EmptyArray::MakeMixed(int64_t key, TypedValue val) {
 282   auto const mask = HphpArray::SmallMask;            // 3
 283   auto const cap  = HphpArray::computeMaxElms(mask); // 3
 284   auto const ad   = smartAllocArray(cap, mask);
 285
 286   ad->m_kindAndSize = uint64_t{1} << 32 | ArrayData::kMixedKind;
 287   ad->m_posAndCount = 0;
 288   ad->m_capAndUsed  = uint64_t{1} << 32 | cap;
 289   ad->m_tableMask   = mask;
 290   ad->m_nextKI      = key + 1;
 291   ad->m_hLoad       = 1;
 292
 293   auto const data = reinterpret_cast<HphpArray::Elm*>(ad + 1);
 294   auto const hash = reinterpret_cast<int32_t*>(data + cap);
 295
 296   assert(mask + 1 == 4);
 297   auto const emptyVal = int64_t{HphpArray::Empty};
 298   reinterpret_cast<int64_t*>(hash)[0] = emptyVal;
 299   reinterpret_cast<int64_t*>(hash)[1] = emptyVal;
 300
 301   hash[key & mask] = 0;
 302   data[0].setIntKey(key);
 303
 304   auto& lval  = data[0].data;
 305   lval.m_data = val.m_data;
 306   lval.m_type = val.m_type;
 307
 308   assert(ad->m_kind == ArrayData::kMixedKind);
 309   assert(ad->m_size == 1);
 310   assert(ad->m_pos == 0);
 311   assert(ad->m_count == 0);
 312   assert(ad->m_cap == cap);
 313   assert(ad->m_used == 1);
 314   assert(ad->checkInvariants());
 315   return { ad, &lval };
 316 }
 317
 318 //////////////////////////////////////////////////////////////////////
 319
 320 ArrayData* EmptyArray::SetInt(ArrayData*, int64_t k, const Variant& v, bool) {
 321   auto c = *v.asCell();
 322   tvRefcountedIncRef(&c);
 323   auto const ret = k == 0 ? EmptyArray::MakePacked(c)
 324                           : EmptyArray::MakeMixed(k, c);
 325   return ret.first;
 326 }
 327
 328 ArrayData* EmptyArray::SetStr(ArrayData*,
 329                               StringData* k,
 330                               const Variant& v,
 331                               bool copy) {
 332   auto val = *v.asCell();
 333   tvRefcountedIncRef(&val);
 334   return EmptyArray::MakeMixed(k, val).first;
 335 }
 336
 337 ArrayData* EmptyArray::LvalInt(ArrayData*, int64_t k, Variant*& retVar, bool) {
 338   auto const ret = k == 0 ? EmptyArray::MakePacked(make_tv<KindOfNull>())
 339                           : EmptyArray::MakeMixed(k, make_tv<KindOfNull>());
 340   retVar = &tvAsVariant(ret.second);
 341   return ret.first;
 342 }
 343
 344 ArrayData* EmptyArray::LvalStr(ArrayData*,
 345                                StringData* k,
 346                                Variant*& retVar,
 347                                bool) {
 348   auto const ret = EmptyArray::MakeMixed(k, make_tv<KindOfNull>());
 349   retVar = &tvAsVariant(ret.second);
 350   return ret.first;
 351 }
 352
 353 ArrayData* EmptyArray::LvalNew(ArrayData*, Variant*& retVar, bool) {
 354   auto const ret = EmptyArray::MakePacked(make_tv<KindOfNull>());
 355   retVar = &tvAsVariant(ret.second);
 356   return ret.first;
 357 }
 358
 359 ArrayData* EmptyArray::SetRefInt(ArrayData*,
 360                                  int64_t k,
 361                                  const Variant& var,
 362                                  bool) {
 363   auto ref = *var.asRef();
 364   tvIncRef(&ref);
 365   auto const ret = k == 0 ? EmptyArray::MakePacked(ref)
 366                           : EmptyArray::MakeMixed(k, ref);
 367   return ret.first;
 368 }
 369
 370 ArrayData* EmptyArray::SetRefStr(ArrayData*,
 371                                  StringData* k,
 372                                  const Variant& var,
 373                                  bool) {
 374   auto ref = *var.asRef();
 375   tvIncRef(&ref);
 376   return EmptyArray::MakeMixed(k, ref).first;
 377 }
 378
 379 ArrayData* EmptyArray::Append(ArrayData*, const Variant& vin, bool copy) {
 380   auto cell = *vin.asCell();
 381   tvRefcountedIncRef(&cell);
 382   return EmptyArray::MakePackedInl(cell).first;
 383 }
 384
 385 ArrayData* EmptyArray::AppendRef(ArrayData*, const Variant& v, bool copy) {
 386   auto ref = *v.asRef();
 387   tvIncRef(&ref);
 388   return EmptyArray::MakePacked(ref).first;
 389 }
 390
 391 ArrayData* EmptyArray::AppendWithRef(ArrayData*, const Variant& v, bool copy) {
 392   auto tv = make_tv<KindOfNull>();
 393   tvAsVariant(&tv).setWithRef(v);
 394   return EmptyArray::MakePacked(tv).first;
 395 }
 396
 397 //////////////////////////////////////////////////////////////////////
 398
 399 ArrayData* EmptyArray::PlusEq(ArrayData*, const ArrayData* elems) {
 400   elems->incRefCount();
 401   return const_cast<ArrayData*>(elems);
 402 }
 403
 404 ArrayData* EmptyArray::Merge(ArrayData*, const ArrayData* elems) {
 405   auto const ret = HphpArray::MakeReserve(HphpArray::SmallSize);
 406   auto const tmp = HphpArray::Merge(ret, elems);
 407   ret->release();
 408   return tmp;
 409 }
 410
 411 ArrayData* EmptyArray::PopOrDequeue(ArrayData* ad, Variant& value) {
 412   value = uninit_null();
 413   return ad;
 414 }
 415
 416 ArrayData* EmptyArray::Prepend(ArrayData*, const Variant& vin, bool) {
 417   auto cell = *vin.asCell();
 418   tvRefcountedIncRef(&cell);
 419   return EmptyArray::MakePacked(cell).first;
 420 }
 421
 422 //////////////////////////////////////////////////////////////////////
 423
 424 ArrayData* EmptyArray::ZSetInt(ArrayData* ad, int64_t k, RefData* v) {
 425   auto const arr = HphpArray::MakeReserve(HphpArray::SmallSize);
 426   arr->m_count = 0;
 427   DEBUG_ONLY auto const tmp = arr->zSet(k, v);
 428   assert(tmp == arr);
 429   return arr;
 430 }
 431
 432 ArrayData* EmptyArray::ZSetStr(ArrayData* ad, StringData* k, RefData* v) {
 433   auto const arr = HphpArray::MakeReserve(HphpArray::SmallSize);
 434   arr->m_count = 0;
 435   DEBUG_ONLY auto const tmp = arr->zSet(k, v);
 436   assert(tmp == arr);
 437   return arr;
 438 }
 439
 440 ArrayData* EmptyArray::ZAppend(ArrayData* ad, RefData* v) {
 441   auto const arr = HphpArray::MakeReserve(HphpArray::SmallSize);
 442   arr->m_count = 0;
 443   DEBUG_ONLY auto const tmp = arr->zAppend(v);
 444   assert(tmp == arr);
 445   return arr;
 446 }
 447
 448 //////////////////////////////////////////////////////////////////////
 449
 450 }