hphp/runtime/ext/collections/ext_collections-vector.cpp

   1 #include "hphp/runtime/ext/collections/ext_collections-vector.h"
   2
   3 #include "hphp/runtime/ext/collections/ext_collections.h"
   4 #include "hphp/runtime/ext/collections/ext_collections-map.h"
   5 #include "hphp/runtime/ext/collections/ext_collections-pair.h"
   6 #include "hphp/runtime/ext/collections/ext_collections-set.h"
   7 #include "hphp/runtime/base/bespoke-array.h"
   8 #include "hphp/runtime/base/comparisons.h"
   9 #include "hphp/runtime/base/container-functions.h"
  10 #include "hphp/runtime/base/execution-context.h"
  11 #include "hphp/runtime/base/tv-refcount.h"
  12 #include "hphp/runtime/base/tv-type.h"
  13 #include "hphp/runtime/base/vanilla-vec.h"
  14 #include "hphp/runtime/vm/vm-regs.h"
  15 #include "hphp/zend/zend-math.h"
  16
  17 namespace HPHP { namespace collections {
  18 /////////////////////////////////////////////////////////////////////////////
  19
  20 const StaticString
  21   s_HH_Vector("HH\\Vector"),
  22   s_HH_ImmVector("HH\\ImmVector"),
  23   s_VectorIterator("VectorIterator");
  24
  25 /////////////////////////////////////////////////////////////////////////////
  26 // VectorIterator
  27
  28 static Variant HHVM_METHOD(VectorIterator, current) {
  29   return Native::data<VectorIterator>(this_)->current();
  30 }
  31
  32 static Variant HHVM_METHOD(VectorIterator, key) {
  33   return Native::data<VectorIterator>(this_)->key();
  34 }
  35
  36 static bool HHVM_METHOD(VectorIterator, valid) {
  37   return Native::data<VectorIterator>(this_)->valid();
  38 }
  39
  40 static void HHVM_METHOD(VectorIterator, next) {
  41   Native::data<VectorIterator>(this_)->next();
  42 }
  43
  44 static void HHVM_METHOD(VectorIterator, rewind) {
  45   Native::data<VectorIterator>(this_)->rewind();
  46 }
  47
  48 }
  49 /////////////////////////////////////////////////////////////////////////////
  50 // Helpers
  51
  52 NEVER_INLINE
  53 void BaseVector::throwBadKeyType() {
  54   SystemLib::throwInvalidArgumentExceptionObject(
  55              "Only integer keys may be used with Vectors");
  56 }
  57
  58 namespace {
  59
  60 void copySlice(ArrayData* from, ArrayData* to,
  61                int64_t from_pos, int64_t to_pos, int64_t size) {
  62   assertx(0 < size && from_pos + size <= from->size());
  63   assertx(from->isVanillaVec() && to->isVanillaVec());
  64   int64_t offset = from_pos - to_pos;
  65   int64_t to_end = to_pos + size;
  66   do {
  67     auto from_elm = VanillaVec::LvalUncheckedInt(from, to_pos + offset);
  68     auto to_elm = VanillaVec::LvalUncheckedInt(to, to_pos);
  69     tvDup(*from_elm, to_elm);
  70   } while (++to_pos < to_end);
  71 }
  72
  73 }  // namespace
  74
  75 /////////////////////////////////////////////////////////////////////////////
  76 // BaseVector
  77
  78 // Used by __construct for Vector and ImmVector
  79 // Used by addAll for Vector only
  80 void BaseVector::addAllImpl(const Variant& t) {
  81   if (t.isNull()) return;
  82   CoeffectsAutoGuard _;
  83
  84   auto ok = IterateV(
  85     *t.asTypedValue(),
  86     [&, this](ArrayData* adata) {
  87       if (adata->empty()) return true;
  88       if (m_size) {
  89         reserve(m_size + adata->size());
  90         return false;
  91       }
  92       // The ArrayData backing a Vector must be a vanilla, unmarked vec.
  93       // Do all three escalations here. Dec-ref any intermediate values we
  94       // create along the way, but do not dec-ref the original adata.
  95       auto array = adata;
  96       if (!array->isVanilla()) {
  97         array = BespokeArray::ToVanilla(array, "BaseVector::addAllImpl");
  98       }
  99       if (array->isVanillaVec() && array->isLegacyArray()) {
 100         auto const tmp = array->setLegacyArray(array->cowCheck(), false);
 101         if (array != adata && array != tmp) decRefArr(array);
 102         array = tmp;
 103       }
 104       if (!array->isVanillaVec()) {
 105         auto const vec = array->toVec(array->cowCheck());
 106         if (array != adata && array != vec) decRefArr(array);
 107         array = vec;
 108       }
 109       if (array == adata) {
 110         array->incRefCount();
 111       }
 112       dropImmCopy();
 113       decRefArr(arrayData());
 114       setArrayData(array);
 115       m_size = array->size();
 116       return true;
 117     },
 118     [this](TypedValue v) {
 119       addRaw(v);
 120     },
 121     [&, this](ObjectData* coll) {
 122       if (coll->collectionType() == CollectionType::Pair) {
 123         reserve(m_size + 2);
 124       }
 125     },
 126     [this](const TypedValue* item) {
 127       add(*item);
 128     });
 129
 130   if (UNLIKELY(!ok)) {
 131     throw_invalid_collection_parameter();
 132   }
 133 }
 134
 135 bool BaseVector::OffsetIsset(ObjectData* obj, const TypedValue* key) {
 136   if (UNLIKELY(key->m_type != KindOfInt64)) {
 137     throwBadKeyType();
 138     return false;
 139   }
 140   const auto vec = static_cast<BaseVector*>(obj);
 141   const auto result = vec->get(key->m_data.num);
 142   return result ? !tvIsNull(*result) : false;
 143 }
 144
 145 bool BaseVector::OffsetContains(ObjectData* obj, const TypedValue* key) {
 146   auto vec = static_cast<BaseVector*>(obj);
 147   if (key->m_type == KindOfInt64) {
 148     return vec->contains(key->m_data.num);
 149   } else {
 150     throwBadKeyType();
 151     return false;
 152   }
 153 }
 154
 155 bool BaseVector::Equals(const ObjectData* obj1, const ObjectData* obj2) {
 156   auto bv1 = static_cast<const BaseVector*>(obj1);
 157   auto bv2 = static_cast<const BaseVector*>(obj2);
 158   return VanillaVec::VecEqual(bv1->arrayData(), bv2->arrayData());
 159 }
 160
 161 void BaseVector::addFront(TypedValue tv) {
 162   dropImmCopy();
 163   auto oldAd = arrayData();
 164   setArrayData(VanillaVec::Prepend(oldAd, tv));
 165   if (arrayData() != oldAd) {
 166     decRefArr(oldAd);
 167   }
 168   m_size = arrayData()->m_size;
 169 }
 170
 171 Variant BaseVector::popFront() {
 172   if (UNLIKELY(m_size == 0)) {
 173     SystemLib::throwInvalidOperationExceptionObject("Cannot pop empty Vector");
 174   }
 175   const auto tv = removeKeyImpl(0);
 176   return Variant(tvAsCVarRef(&tv), Variant::TVCopy());
 177 }
 178
 179 TypedValue BaseVector::removeKeyImpl(int64_t k) {
 180   assertx(contains(k));
 181   mutate();
 182   const auto result = *lvalAt(k);
 183   if (k+1 < m_size) {
 184     if constexpr (VanillaVec::stores_unaligned_typed_values) {
 185       auto* data = VanillaVec::entries(arrayData());
 186       size_t bytes = (m_size-(k+1)) * sizeof(UnalignedTypedValue);
 187       std::memmove(&data[k], &data[k+1], bytes);
 188     } else {
 189       uint32_t i = k, end = m_size - 1;
 190       do {
 191         tvCopy(*lvalAt(i + 1), lvalAt(i));
 192       } while (++i < end);
 193     }
 194   }
 195   decSize();
 196   return result;
 197 }
 198
 199 void BaseVector::reserveImpl(uint32_t newCap) {
 200   auto oldAd = arrayData();
 201   auto const arr = VanillaVec::MakeReserveVec(newCap);
 202   setArrayData(arr);
 203   arr->m_size = m_size;
 204   if (LIKELY(!oldAd->cowCheck())) {
 205     assertx(oldAd->isVanillaVec());
 206     if (m_size > 0) {
 207       const size_t bytes = VanillaVec::capacityToSizeBytes(m_size);
 208       std::memcpy(arrayData() + 1, oldAd + 1, bytes - sizeof(ArrayData));
 209       // Mark oldAd as having 0 elements so that the array release logic doesn't
 210       // decRef the elements (since we teleported the elements to a new array)
 211       oldAd->m_size = 0;
 212     }
 213     decRefArr(oldAd);
 214   } else {
 215     if (m_size > 0) {
 216       copySlice(oldAd, arr, 0, 0, m_size);
 217     }
 218     assertx(!oldAd->decWillRelease());
 219     oldAd->decRefCount();
 220   }
 221 }
 222
 223 void BaseVector::reserve(uint32_t sz) {
 224   dropImmCopy();
 225   if (sz > VanillaVec::capacity(arrayData())) {
 226     reserveImpl(sz);
 227   } else if (!canMutateBuffer()) {
 228     mutateImpl();
 229   }
 230   assertx(canMutateBuffer());
 231 }
 232
 233 /**
 234  * Delegate the responsibility for freeing the buffer to the immutable copy,
 235  * if it exists.
 236  */
 237 BaseVector::~BaseVector() {
 238   // Avoid indirect call, as we know it is a vec array.
 239   auto const vec = arrayData();
 240   if (vec->decReleaseCheck()) VanillaVec::Release(vec);
 241 }
 242
 243 void BaseVector::mutateImpl() {
 244   auto oldAd = arrayData();
 245   setArrayData(VanillaVec::Copy(oldAd));
 246   assertx(!oldAd->decWillRelease());
 247   oldAd->decRefCount();
 248 }
 249
 250 template<class TVector>
 251 ALWAYS_INLINE typename std::enable_if<
 252   std::is_base_of<BaseVector, TVector>::value, TVector*>::type
 253 BaseVector::Clone(ObjectData* obj) {
 254   auto thiz = static_cast<TVector*>(obj);
 255   thiz->arrayData()->incRefCount();
 256   return req::make<TVector>(thiz->arrayData()).detach();
 257 }
 258
 259 // This function will create a immutable copy of this Vector (if it doesn't
 260 // already exist) and then return it
 261 Object BaseVector::getImmutableCopy() {
 262   if (m_immCopy.isNull()) {
 263     auto vec = req::make<c_ImmVector>(arrayData());
 264     arrayData()->incRefCount();
 265     m_immCopy = std::move(vec);
 266   }
 267   assertx(!m_immCopy.isNull());
 268   assertx(arrayData() ==
 269          static_cast<c_ImmVector*>(m_immCopy.get())->arrayData());
 270   assertx(!canMutateBuffer());
 271   return m_immCopy;
 272 }
 273
 274 Object BaseVector::getIterator() {
 275   auto iter = collections::VectorIterator::newInstance();
 276   Native::data<collections::VectorIterator>(iter)->setVector(this);
 277   return iter;
 278 }
 279
 280 //////////////////////////////////////////////////////////////////////////////
 281 // c_Vector
 282
 283 Class* c_Vector::s_cls;
 284
 285 void c_Vector::clear() {
 286   dropImmCopy();
 287   decRefArr(arrayData());
 288   setArrayData(ArrayData::CreateVec());
 289   m_size = 0;
 290 }
 291
 292 void c_Vector::removeKey(int64_t k) {
 293   if (!contains(k)) return;
 294   tvDecRefGen(removeKeyImpl(k));
 295 }
 296
 297 Variant c_Vector::pop() {
 298   if (UNLIKELY(m_size == 0)) {
 299     SystemLib::throwInvalidOperationExceptionObject("Cannot pop empty Vector");
 300   }
 301   mutate();
 302   decSize();
 303   const auto tv = *lvalAt(m_size);
 304   return Variant(tvAsCVarRef(&tv), Variant::TVCopy());
 305 }
 306
 307 void c_Vector::resize(uint32_t sz, const TypedValue* val) {
 308   if (sz == m_size) {
 309     return;
 310   }
 311   if (sz == 0) {
 312     dropImmCopy();
 313     decRefArr(arrayData());
 314     setArrayData(ArrayData::CreateVec());
 315     m_size = 0;
 316   } else if (m_size > sz) {
 317     // If there were any objects in the part that's being resized away, their
 318     // desctuctors may mutate this Vector (and need to see it in the fully
 319     // resized state). The easiest way to do this is to copy the part we're
 320     // keeping into a new vec, swap them, and decref the old one.
 321     dropImmCopy();
 322     auto oldAd = arrayData();
 323     auto const arr = VanillaVec::MakeReserveVec(sz);
 324     setArrayData(arr);
 325     copySlice(oldAd, arr, 0, 0, sz);
 326     arrayData()->m_size = m_size = sz;
 327     decRefArr(oldAd);
 328   } else {
 329     reserve(sz);
 330     uint32_t i = m_size;
 331     do {
 332       tvDup(*val, lvalAt(i));
 333     } while (++i < sz);
 334     setSize(sz);
 335   }
 336 }
 337
 338 void c_Vector::reverse() {
 339   if (m_size < 2) return;
 340   mutate();
 341   uint32_t i = 0;
 342   uint32_t j = m_size - 1;
 343   do {
 344     tvSwap(lvalAt(i), lvalAt(j));
 345   } while (++i < --j);
 346 }
 347
 348 void c_Vector::splice(int64_t startPos, int64_t endPos) {
 349   // If there were any objects in the part that's being spliced away, their
 350   // desctuctors may mutate this Vector (and need to see it in the fully
 351   // spliced state). The easiest way to do this is to copy the part we're
 352   // keeping into a new vec, swap them, and decref the old one.
 353   assertx(0 <= startPos && startPos < endPos && endPos <= m_size);
 354   uint32_t sz = m_size - (endPos - startPos);
 355   dropImmCopy();
 356   auto oldAd = arrayData();
 357   auto const arr = VanillaVec::MakeReserveVec(sz);
 358   setArrayData(arr);
 359   if (startPos > 0) {
 360     copySlice(oldAd, arr, 0, 0, startPos);
 361   }
 362   if (sz > startPos) {
 363     copySlice(oldAd, arr, endPos, startPos, sz - startPos);
 364   }
 365   arrayData()->m_size = m_size = sz;
 366   decRefArr(oldAd);
 367 }
 368
 369 void c_Vector::php_splice(const Variant& offset,
 370                           const Variant& len /* = null */,
 371                           const Variant& replacement /* = null */) {
 372   if (!offset.isInteger()) {
 373     SystemLib::throwInvalidArgumentExceptionObject(
 374       "Parameter offset must be an integer");
 375   }
 376   if (!len.isNull() && !len.isInteger()) {
 377     SystemLib::throwInvalidArgumentExceptionObject(
 378       "Parameter len must be null or an integer");
 379   }
 380   if (!replacement.isNull()) {
 381     SystemLib::throwInvalidOperationExceptionObject(
 382       "Vector::splice does not support replacement parameter");
 383   }
 384   auto sz = size();
 385   auto start = offset.toInt64();
 386   if (UNLIKELY(start >= sz)) return;
 387   if (start < 0) {
 388     start += sz;
 389     if (start < 0) { start = 0; }
 390   }
 391   int64_t end;
 392   if (!len.isNull()) {
 393     end = len.toInt64();
 394     if (LIKELY(end > 0)) {
 395       end += start;
 396       if ((uint64_t)end > (uint64_t)sz) end = sz;
 397     } else {
 398       if (!end) return;
 399       end += sz;
 400       if (end <= start) return;
 401     }
 402   } else {
 403     end = sz;
 404   }
 405   splice(start, end);
 406 }
 407
 408 void c_Vector::shuffle() {
 409   if (m_size < 2) {
 410     return;
 411   }
 412   mutate();
 413   uint32_t i = 1;
 414   do {
 415     const uint32_t j = math_mt_rand(0, i);
 416     tvSwap(lvalAt(i), lvalAt(j));
 417   } while (++i < m_size);
 418 }
 419
 420 c_Vector* c_Vector::Clone(ObjectData* obj) {
 421   return BaseVector::Clone<c_Vector>(obj);
 422 }
 423
 424 Object c_Vector::fromArray(const Class*, const Variant& arr) {
 425   if (!arr.isArray()) {
 426     SystemLib::throwInvalidArgumentExceptionObject(
 427       "Parameter arr must be an array");
 428   }
 429   auto ad = arr.getArrayData();
 430   uint32_t sz = ad->size();
 431   if (sz == 0) {
 432     return Object{req::make<c_Vector>()};
 433   }
 434   auto target = req::make<c_Vector>(sz);
 435   target->setSize(sz);
 436   uint32_t i = 0;
 437   ssize_t pos = ad->iter_begin();
 438   do {
 439     assertx(pos != ad->iter_end());
 440     tvDup(ad->nvGetVal(pos), target->lvalAt(i));
 441     pos = ad->iter_advance(pos);
 442   } while (++i < sz);
 443   return Object{std::move(target)};
 444 }
 445
 446 void c_Vector::OffsetSet(ObjectData* obj, const TypedValue* key,
 447                          const TypedValue* val) {
 448   static_cast<c_Vector*>(obj)->set(key, val);
 449 }
 450
 451 void c_Vector::OffsetUnset(ObjectData* /*obj*/, const TypedValue* /*key*/) {
 452   SystemLib::throwRuntimeExceptionObject(
 453     "Cannot unset an element of a Vector");
 454 }
 455
 456 /////////////////////////////////////////////////////////////////////////////
 457 // c_ImmVector
 458
 459 Class* c_ImmVector::s_cls;
 460
 461 c_ImmVector* c_ImmVector::Clone(ObjectData* obj) {
 462   return BaseVector::Clone<c_ImmVector>(obj);
 463 }
 464
 465 namespace collections {
 466
 467 void CollectionsExtension::initVector() {
 468   HHVM_ME(VectorIterator, current);
 469   HHVM_ME(VectorIterator, key);
 470   HHVM_ME(VectorIterator, valid);
 471   HHVM_ME(VectorIterator, next);
 472   HHVM_ME(VectorIterator, rewind);
 473
 474   Native::registerNativeDataInfo<VectorIterator>(
 475     s_VectorIterator.get(),
 476     Native::NDIFlags::NO_SWEEP
 477   );
 478
 479   // Common Vector/ImmVector
 480
 481 #define BASE_ME(mn, impl) \
 482   HHVM_NAMED_ME(HH\\Vector,    mn, impl); \
 483   HHVM_NAMED_ME(HH\\ImmVector, mn, impl);
 484   BASE_ME(__construct,  &BaseVector::init);
 485   BASE_ME(getIterator,  &BaseVector::getIterator);
 486 #undef BASE_ME
 487
 488   // Vector specific
 489   HHVM_NAMED_ME(HH\\Vector, pop,      &c_Vector::pop);
 490   HHVM_NAMED_ME(HH\\Vector, reverse,  &c_Vector::reverse);
 491   HHVM_NAMED_ME(HH\\Vector, shuffle,  &c_Vector::shuffle);
 492   HHVM_NAMED_ME(HH\\Vector, reserve,  &c_Vector::php_reserve);
 493   HHVM_NAMED_ME(HH\\Vector, resize,   &c_Vector::php_resize);
 494   HHVM_NAMED_ME(HH\\Vector, splice,   &c_Vector::php_splice);
 495
 496   // Vector specific functions that return `$this` in userland. These mutate
 497   // the underlying vector *then* return, with the mutation contained within
 498   // a `void` C++ function.
 499   HHVM_NAMED_ME(HH\\Vector, removeKeyNative,  &c_Vector::php_removeKey);
 500   HHVM_NAMED_ME(HH\\Vector, clearNative,      &c_Vector::clear);
 501
 502   Native::registerNativePropHandler<CollectionPropHandler>(s_HH_Vector);
 503   Native::registerNativePropHandler<CollectionPropHandler>(s_HH_ImmVector);
 504
 505   loadSystemlib("collections-vector");
 506
 507   c_Vector::s_cls = Class::lookup(s_HH_Vector.get());
 508   assertx(c_Vector::s_cls);
 509   finishClass<c_Vector>();
 510
 511   c_ImmVector::s_cls = Class::lookup(s_HH_ImmVector.get());
 512   assertx(c_ImmVector::s_cls);
 513   finishClass<c_ImmVector>();
 514 }
 515
 516 /////////////////////////////////////////////////////////////////////////////
 517 }}