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

   1 #include "hphp/runtime/ext/collections/ext_collections-set.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-vector.h"
   7 #include "hphp/runtime/ext/collections/hash-collection.h"
   8 #include "hphp/runtime/base/container-functions.h"
   9 #include "hphp/runtime/base/execution-context.h"
  10 #include "hphp/runtime/base/mixed-array.h"
  11 #include "hphp/runtime/vm/vm-regs.h"
  12
  13 namespace HPHP {
  14 /////////////////////////////////////////////////////////////////////////////
  15
  16 Class* c_Set::s_cls;
  17 Class* c_ImmSet::s_cls;
  18
  19 inline
  20 bool invokeAndCastToBool(const CallCtx& ctx, int argc,
  21                          const TypedValue* argv) {
  22   auto ret = Variant::attach(
  23     g_context->invokeFuncFew(ctx, argc, argv)
  24   );
  25   return ret.toBoolean();
  26 }
  27
  28 /////////////////////////////////////////////////////////////////////////////
  29 // BaseSet
  30
  31 void BaseSet::addAllKeysOf(const Cell container) {
  32   assert(isContainer(container));
  33
  34   decltype(cap()) oldCap = 0;
  35   bool ok =
  36     IterateKV(container,
  37               [&](ArrayData* adata) {
  38                 auto sz = adata->size();
  39                 if (!sz) return true;
  40                 if (m_size) {
  41                   oldCap = cap(); // assume minimal collisions
  42                 }
  43                 reserve(m_size + sz);
  44                 mutateAndBump();
  45                 return false;
  46               },
  47               [this](Cell k, TypedValue /*v*/) { addRaw(k); },
  48               [this](ObjectData* coll) {
  49                 if (!m_size && coll->collectionType() == CollectionType::Set) {
  50                   auto hc = static_cast<HashCollection*>(coll);
  51                   replaceArray(hc->arrayData());
  52                   return true;
  53                 }
  54                 if (coll->collectionType() == CollectionType::Pair) {
  55                   mutateAndBump();
  56                 }
  57                 return false;
  58               });
  59
  60   if (UNLIKELY(!ok)) {
  61     throw_invalid_collection_parameter();
  62   }
  63   // ... and shrink back if that was incorrect
  64   if (oldCap) shrinkIfCapacityTooHigh(oldCap);
  65 }
  66
  67 void BaseSet::addAll(const Variant& t) {
  68   if (t.isNull()) { return; } // nothing to do
  69
  70   decltype(cap()) oldCap = 0;
  71   bool ok = IterateV(
  72     *t.asTypedValue(),
  73     [&](ArrayData* adata) {
  74       auto sz = adata->size();
  75       if (!sz) return true;
  76       if (m_size) {
  77         oldCap = cap(); // assume minimal collisions
  78       }
  79       reserve(m_size + sz);
  80       mutateAndBump();
  81       return false;
  82     },
  83     [this](TypedValue v) {
  84       addRaw(tvToCell(v));
  85     },
  86     [this](ObjectData* coll) {
  87       if (!m_size && coll->collectionType() == CollectionType::Set) {
  88         auto hc = static_cast<HashCollection*>(coll);
  89         replaceArray(hc->arrayData());
  90         return true;
  91       }
  92       if (coll->collectionType() == CollectionType::Pair) {
  93         mutateAndBump();
  94       }
  95       return false;
  96     },
  97     [this](const TypedValue* value) {
  98       add(tvAsCVarRef(value));
  99     });
 100
 101   if (UNLIKELY(!ok)) {
 102     throw_invalid_collection_parameter();
 103   }
 104   // ... and shrink back if that was incorrect
 105   if (oldCap) shrinkIfCapacityTooHigh(oldCap);
 106 }
 107
 108 template<bool raw>
 109 ALWAYS_INLINE
 110 void BaseSet::addImpl(int64_t k) {
 111   if (!raw) {
 112     mutate();
 113   }
 114   auto h = hash_int64(k);
 115   auto p = findForInsert(k, h);
 116   assert(MixedArray::isValidIns(p));
 117   if (MixedArray::isValidPos(*p)) {
 118     // When there is a conflict, the add() API is supposed to replace the
 119     // existing element with the new element in place. However since Sets
 120     // currently only support integer and string elements, there is no way
 121     // user code can really tell whether the existing element was replaced
 122     // so for efficiency we do nothing.
 123     return;
 124   }
 125   if (UNLIKELY(isFull())) {
 126     makeRoom();
 127     p = findForInsert(k, h);
 128   }
 129   auto& e = allocElm(p);
 130   e.setIntKey(k, h);
 131   e.data.m_type = KindOfInt64;
 132   e.data.m_data.num = k;
 133   updateNextKI(k);
 134   if (!raw) {
 135     ++m_version;
 136   }
 137 }
 138
 139 template<bool raw>
 140 ALWAYS_INLINE
 141 void BaseSet::addImpl(StringData *key) {
 142   if (!raw) {
 143     mutate();
 144   }
 145   strhash_t h = key->hash();
 146   auto p = findForInsert(key, h);
 147   assert(MixedArray::isValidIns(p));
 148   if (MixedArray::isValidPos(*p)) {
 149     return;
 150   }
 151   if (UNLIKELY(isFull())) {
 152     makeRoom();
 153     p = findForInsert(key, h);
 154   }
 155   auto& e = allocElm(p);
 156   // This increments the string's refcount twice, once for
 157   // the key and once for the value
 158   e.setStrKey(key, h);
 159   cellDup(make_tv<KindOfString>(key), e.data);
 160   if (!raw) {
 161     ++m_version;
 162   }
 163 }
 164
 165 void BaseSet::addRaw(int64_t k) {
 166   addImpl<true>(k);
 167 }
 168
 169 void BaseSet::addRaw(StringData *key) {
 170   addImpl<true>(key);
 171 }
 172
 173 void BaseSet::add(int64_t k) {
 174   addImpl<false>(k);
 175 }
 176
 177 void BaseSet::add(StringData *key) {
 178   addImpl<false>(key);
 179 }
 180
 181 void BaseSet::addFront(int64_t k) {
 182   mutate();
 183   auto h = hash_int64(k);
 184   auto p = findForInsert(k, h);
 185   assert(MixedArray::isValidIns(p));
 186   if (MixedArray::isValidPos(*p)) {
 187     // When there is a conflict, the addFront() API is supposed to replace
 188     // the existing element with the new element in place. However since
 189     // Sets currently only support integer and string elements, there is
 190     // no way user code can really tell whether the existing element was
 191     // replaced so for efficiency we do nothing.
 192     return;
 193   }
 194   if (UNLIKELY(isFull())) {
 195     makeRoom();
 196     p = findForInsert(k, h);
 197   }
 198   auto& e = allocElmFront(p);
 199   e.setIntKey(k, h);
 200   e.data.m_type = KindOfInt64;
 201   e.data.m_data.num = k;
 202   updateNextKI(k);
 203   ++m_version;
 204 }
 205
 206 void BaseSet::addFront(StringData *key) {
 207   mutate();
 208   strhash_t h = key->hash();
 209   auto p = findForInsert(key, h);
 210   assert(MixedArray::isValidIns(p));
 211   if (MixedArray::isValidPos(*p)) {
 212     return;
 213   }
 214   if (UNLIKELY(isFull())) {
 215     makeRoom();
 216     p = findForInsert(key, h);
 217   }
 218   auto& e = allocElmFront(p);
 219   // This increments the string's refcount twice, once for
 220   // the key and once for the value
 221   e.setStrKey(key, h);
 222   cellDup(make_tv<KindOfString>(key), e.data);
 223   ++m_version;
 224 }
 225
 226 Variant BaseSet::pop() {
 227   if (UNLIKELY(m_size == 0)) {
 228     SystemLib::throwInvalidOperationExceptionObject("Cannot pop empty Set");
 229   }
 230   mutateAndBump();
 231   auto e = elmLimit() - 1;
 232   for (;; --e) {
 233     assert(e >= data());
 234     if (!isTombstone(e)) break;
 235   }
 236   Variant ret = tvAsCVarRef(&e->data);
 237   auto h = e->hash();
 238   auto ei = e->hasIntKey() ? findForRemove(e->ikey, h) :
 239             findForRemove(e->skey, h);
 240   erase(ei);
 241   return ret;
 242 }
 243
 244 Variant BaseSet::popFront() {
 245   if (UNLIKELY(m_size == 0)) {
 246     SystemLib::throwInvalidOperationExceptionObject("Cannot pop empty Set");
 247   }
 248   mutateAndBump();
 249   auto e = data();
 250   for (;; ++e) {
 251     assert(e != elmLimit());
 252     if (!isTombstone(e)) break;
 253   }
 254   Variant ret = tvAsCVarRef(&e->data);
 255   auto h = e->hash();
 256   auto ei = e->hasIntKey() ? findForRemove(e->ikey, h) :
 257             findForRemove(e->skey, h);
 258   erase(ei);
 259   return ret;
 260 }
 261
 262 Variant BaseSet::firstValue() {
 263   if (!m_size) return init_null();
 264   auto e = firstElm();
 265   assert(e != elmLimit());
 266   return tvAsCVarRef(&e->data);
 267 }
 268
 269 Variant BaseSet::lastValue() {
 270   if (!m_size) return init_null();
 271   // TODO Task# 4281431: If nthElmPos(n) is optimized to
 272   // walk backward from the end when n > m_size/2, then
 273   // we could use that here instead of having to use a
 274   // manual while loop.
 275   uint32_t pos = posLimit() - 1;
 276   while (isTombstone(pos)) {
 277     assert(pos > 0);
 278     --pos;
 279   }
 280   return tvAsCVarRef(&data()[pos].data);
 281 }
 282
 283 void BaseSet::throwNoMutableIndexAccess() {
 284   SystemLib::throwInvalidOperationExceptionObject(
 285     "[] operator cannot be used to modify elements of a Set");
 286 }
 287
 288 Array BaseSet::ToArray(const ObjectData* obj) {
 289   check_collection_cast_to_array();
 290   return const_cast<BaseSet*>(static_cast<const BaseSet*>(obj))->toArray();
 291 }
 292
 293 bool BaseSet::ToBool(const ObjectData* obj) {
 294   return static_cast<const BaseSet*>(obj)->toBoolImpl();
 295 }
 296
 297 // This function will create a immutable copy of this Set (if it doesn't
 298 // already exist) and then return it
 299 Object c_Set::getImmutableCopy() {
 300   if (m_immCopy.isNull()) {
 301     auto set = req::make<c_ImmSet>();
 302     set->m_size = m_size;
 303     set->m_version = m_version;
 304     set->m_arr = m_arr;
 305     m_immCopy = std::move(set);
 306     arrayData()->incRefCount();
 307   }
 308   assert(!m_immCopy.isNull());
 309   assert(data() == static_cast<c_ImmSet*>(m_immCopy.get())->data());
 310   assert(arrayData()->hasMultipleRefs());
 311   return m_immCopy;
 312 }
 313
 314 bool BaseSet::Equals(const ObjectData* obj1, const ObjectData* obj2) {
 315   auto st1 = static_cast<const BaseSet*>(obj1);
 316   auto st2 = static_cast<const BaseSet*>(obj2);
 317   return MixedArray::DictEqual(st1->arrayData(), st2->arrayData());
 318 }
 319
 320 BaseSet::~BaseSet() {
 321   auto const mixed = MixedArray::asMixed(arrayData());
 322   // Avoid indirect call, as we know it is a MixedArray
 323   if (mixed->decReleaseCheck()) MixedArray::ReleaseDict(mixed);
 324 }
 325
 326 void BaseSet::throwBadValueType() {
 327   SystemLib::throwInvalidArgumentExceptionObject(
 328     "Only integer values and string values may be used with Sets");
 329 }
 330
 331 template<class TSet>
 332 typename std::enable_if<
 333   std::is_base_of<BaseSet, TSet>::value, TSet*>::type
 334 BaseSet::Clone(ObjectData* obj) {
 335   auto thiz = static_cast<TSet*>(obj);
 336   auto target = req::make<TSet>();
 337   if (!thiz->m_size) {
 338     return target.detach();
 339   }
 340   thiz->arrayData()->incRefCount();
 341   target->m_size = thiz->m_size;
 342   target->m_arr = thiz->m_arr;
 343   return target.detach();
 344 }
 345
 346 bool BaseSet::OffsetIsset(ObjectData* obj, const TypedValue* key) {
 347   assert(key->m_type != KindOfRef);
 348   auto set = static_cast<BaseSet*>(obj);
 349   if (key->m_type == KindOfInt64) {
 350     return set->contains(key->m_data.num);
 351   }
 352   if (isStringType(key->m_type)) {
 353     return set->contains(key->m_data.pstr);
 354   }
 355   throwBadValueType();
 356   return false;
 357 }
 358
 359 bool BaseSet::OffsetEmpty(ObjectData* obj, const TypedValue* key) {
 360   assert(key->m_type != KindOfRef);
 361   auto set = static_cast<BaseSet*>(obj);
 362   if (key->m_type == KindOfInt64) {
 363     return set->contains(key->m_data.num) ? !cellToBool(*key) : true;
 364   }
 365   if (isStringType(key->m_type)) {
 366     return set->contains(key->m_data.pstr) ? !cellToBool(*key) : true;
 367   }
 368   throwBadValueType();
 369   return true;
 370 }
 371
 372 bool BaseSet::OffsetContains(ObjectData* obj, const TypedValue* key) {
 373   assert(key->m_type != KindOfRef);
 374   auto set = static_cast<BaseSet*>(obj);
 375   if (key->m_type == KindOfInt64) {
 376     return set->contains(key->m_data.num);
 377   }
 378   if (isStringType(key->m_type)) {
 379     return set->contains(key->m_data.pstr);
 380   }
 381   throwBadValueType();
 382   return false;
 383 }
 384
 385 void BaseSet::OffsetUnset(ObjectData* obj, const TypedValue* key) {
 386   assert(key->m_type != KindOfRef);
 387   auto set = static_cast<BaseSet*>(obj);
 388   if (key->m_type == KindOfInt64) {
 389     set->remove(key->m_data.num);
 390     return;
 391   }
 392   if (isStringType(key->m_type)) {
 393     set->remove(key->m_data.pstr);
 394     return;
 395   }
 396   throwBadValueType();
 397 }
 398
 399 template<typename TSet, bool useKey>
 400 typename std::enable_if<
 401   std::is_base_of<BaseSet, TSet>::value, Object>::type
 402 BaseSet::php_map(const Variant& callback) {
 403   VMRegGuard _;
 404   CallCtx ctx;
 405   vm_decode_function(callback, nullptr, false, ctx);
 406   if (!ctx.func) {
 407     SystemLib::throwInvalidArgumentExceptionObject(
 408       "Parameter must be a valid callback");
 409   }
 410   auto set = req::make<TSet>();
 411   if (!m_size) return Object{std::move(set)};
 412   assert(posLimit() != 0);
 413   assert(set->arrayData() == staticEmptyDictArrayAsMixed());
 414   auto oldCap = set->cap();
 415   set->reserve(posLimit()); // presume minimum collisions ...
 416   assert(set->canMutateBuffer());
 417   constexpr int64_t argc = useKey ? 2 : 1;
 418   TypedValue argv[argc];
 419   for (ssize_t pos = iter_begin(); iter_valid(pos); pos = iter_next(pos)) {
 420     auto e = iter_elm(pos);
 421     int32_t pVer = m_version;
 422     if (useKey) {
 423       argv[0] = e->data;
 424     }
 425     argv[argc-1] = e->data;
 426     auto cbRet = Variant::attach(
 427       g_context->invokeFuncFew(ctx, argc, argv)
 428     );
 429     if (UNLIKELY(m_version != pVer)) throw_collection_modified();
 430     set->addRaw(*cbRet.asTypedValue());
 431   }
 432   // ... and shrink back if that was incorrect
 433   set->shrinkIfCapacityTooHigh(oldCap);
 434   return Object{std::move(set)};
 435 }
 436
 437 template<typename TSet, bool useKey>
 438 typename std::enable_if<
 439   std::is_base_of<BaseSet, TSet>::value, Object>::type
 440 BaseSet::php_filter(const Variant& callback) {
 441   VMRegGuard _;
 442   CallCtx ctx;
 443   vm_decode_function(callback, nullptr, false, ctx);
 444   if (!ctx.func) {
 445     SystemLib::throwInvalidArgumentExceptionObject(
 446       "Parameter must be a valid callback");
 447   }
 448   auto set = req::make<TSet>();
 449   if (!m_size) return Object(std::move(set));
 450   // we don't reserve(), because we don't know how selective callback will be
 451   set->mutate();
 452   int32_t version = m_version;
 453   constexpr int64_t argc = useKey ? 2 : 1;
 454   TypedValue argv[argc];
 455   for (ssize_t pos = iter_begin(); iter_valid(pos); pos = iter_next(pos)) {
 456     auto e = iter_elm(pos);
 457     if (useKey) {
 458       argv[0] = e->data;
 459     }
 460     argv[argc-1] = e->data;
 461     bool b = invokeAndCastToBool(ctx, argc, argv);
 462     if (UNLIKELY(version != m_version)) {
 463       throw_collection_modified();
 464     }
 465     if (!b) continue;
 466     e = iter_elm(pos);
 467     if (e->hasIntKey()) {
 468       set->addRaw(e->data.m_data.num);
 469     } else {
 470       assert(e->hasStrKey());
 471       set->addRaw(e->data.m_data.pstr);
 472     }
 473   }
 474   return Object(std::move(set));
 475 }
 476
 477 template<class TSet>
 478 typename std::enable_if<
 479   std::is_base_of<BaseSet, TSet>::value, Object>::type
 480 BaseSet::php_zip(const Variant& iterable) {
 481   size_t sz;
 482   ArrayIter iter = getArrayIterHelper(iterable, sz);
 483   if (m_size && iter) {
 484     // At present, BaseSets only support int values and string values,
 485     // so if this BaseSet is non empty and the iterable is non empty
 486     // the zip operation will always fail
 487     throwBadValueType();
 488   }
 489   return Object(req::make<TSet>());
 490 }
 491
 492 template<bool useKey>
 493 Object BaseSet::php_retain(const Variant& callback) {
 494   CallCtx ctx;
 495   vm_decode_function(callback, nullptr, false, ctx);
 496   if (!ctx.func) {
 497     SystemLib::throwInvalidArgumentExceptionObject(
 498                "Parameter must be a valid callback");
 499   }
 500   auto size = m_size;
 501   if (!size) { return Object{this}; }
 502   constexpr int64_t argc = useKey ? 2 : 1;
 503   TypedValue argv[argc];
 504   for (ssize_t pos = iter_begin(); iter_valid(pos); pos = iter_next(pos)) {
 505     int32_t version = m_version;
 506     auto e = iter_elm(pos);
 507     if (useKey) {
 508       argv[0] = e->data;
 509     }
 510     argv[argc-1] = e->data;
 511     bool b = invokeAndCastToBool(ctx, argc, argv);
 512     if (UNLIKELY(version != m_version)) {
 513       throw_collection_modified();
 514     }
 515     if (b) { continue; }
 516     mutateAndBump();
 517     version = m_version;
 518     e = iter_elm(pos);
 519     auto h = e->hash();
 520     auto pp = e->hasIntKey() ? findForRemove(e->ikey, h) :
 521               findForRemove(e->skey, h);
 522     eraseNoCompact(pp);
 523     if (UNLIKELY(version != m_version)) {
 524       throw_collection_modified();
 525     }
 526   }
 527   assert(m_size <= size);
 528   compactOrShrinkIfDensityTooLow();
 529   return Object{this};
 530 }
 531
 532 template<class TSet>
 533 typename std::enable_if<
 534   std::is_base_of<BaseSet, TSet>::value, Object>::type
 535 BaseSet::php_take(const Variant& n) {
 536   if (!n.isInteger()) {
 537     SystemLib::throwInvalidArgumentExceptionObject(
 538       "Parameter n must be an integer");
 539   }
 540   int64_t len = n.toInt64();
 541   if (len >= int64_t(m_size)) {
 542     // We know the result Set will simply be a copy of this Set,
 543     // so we can just call Clone() and return early here.
 544     return Object::attach(TSet::Clone(this));
 545   }
 546   auto set = req::make<TSet>();
 547   if (len <= 0) {
 548     // We know the resulting Set will be empty, so we can return
 549     // early here.
 550     return Object{std::move(set)};
 551   }
 552   size_t sz = size_t(len);
 553   set->reserve(sz);
 554   set->setSize(sz);
 555   set->setPosLimit(sz);
 556   auto table = set->hashTab();
 557   auto mask = set->tableMask();
 558   for (uint32_t frPos = 0, toPos = 0; toPos < sz; ++toPos, ++frPos) {
 559     frPos = skipTombstonesNoBoundsCheck(frPos);
 560     auto& toE = set->data()[toPos];
 561     dupElm(data()[frPos], toE);
 562     *findForNewInsert(table, mask, toE.probe()) = toPos;
 563     if (toE.hasIntKey()) {
 564       set->updateNextKI(toE.ikey);
 565     } else {
 566       assert(toE.hasStrKey());
 567     }
 568   }
 569   return Object{std::move(set)};
 570 }
 571
 572 template<class TSet>
 573 typename std::enable_if<
 574   std::is_base_of<BaseSet, TSet>::value, Object>::type
 575 BaseSet::php_takeWhile(const Variant& fn) {
 576   CallCtx ctx;
 577   vm_decode_function(fn, nullptr, false, ctx);
 578   if (!ctx.func) {
 579     SystemLib::throwInvalidArgumentExceptionObject(
 580                "Parameter must be a valid callback");
 581   }
 582   auto set = req::make<TSet>();
 583   if (!m_size) return Object(std::move(set));
 584   set->mutate();
 585   int32_t version UNUSED;
 586   if (std::is_same<c_Set, TSet>::value) {
 587     version = m_version;
 588   }
 589   uint32_t used = posLimit();
 590   for (uint32_t i = 0; i < used; ++i) {
 591     if (isTombstone(i)) continue;
 592     Elm* e = &data()[i];
 593     bool b = invokeAndCastToBool(ctx, 1, &e->data);
 594     if (std::is_same<c_Set, TSet>::value) {
 595       if (UNLIKELY(version != m_version)) {
 596         throw_collection_modified();
 597       }
 598     }
 599     if (!b) break;
 600     e = &data()[i];
 601     if (e->hasIntKey()) {
 602       set->addRaw(e->data.m_data.num);
 603     } else {
 604       assert(e->hasStrKey());
 605       set->addRaw(e->data.m_data.pstr);
 606     }
 607   }
 608   return Object(std::move(set));
 609 }
 610
 611 template<class TSet>
 612 typename std::enable_if<
 613   std::is_base_of<BaseSet, TSet>::value, Object>::type
 614 BaseSet::php_skip(const Variant& n) {
 615   if (!n.isInteger()) {
 616     SystemLib::throwInvalidArgumentExceptionObject(
 617       "Parameter n must be an integer");
 618   }
 619   int64_t len = n.toInt64();
 620   if (len <= 0) {
 621     // We know the resulting Set will simply be a copy of this Set,
 622     // so we can just call Clone() and return early here.
 623     return Object::attach(TSet::Clone(this));
 624   }
 625   auto set = req::make<TSet>();
 626   if (len >= m_size) {
 627     // We know the resulting Set will be empty, so we can return
 628     // early here.
 629     return Object{std::move(set)};
 630   }
 631   size_t sz = size_t(m_size) - size_t(len);
 632   assert(sz);
 633   set->reserve(sz);
 634   set->setSize(sz);
 635   set->setPosLimit(sz);
 636   uint32_t frPos = nthElmPos(len);
 637   auto table = set->hashTab();
 638   auto mask = set->tableMask();
 639   for (uint32_t toPos = 0; toPos < sz; ++toPos, ++frPos) {
 640     while (isTombstone(frPos)) {
 641       assert(frPos + 1 < posLimit());
 642       ++frPos;
 643     }
 644     auto& toE = set->data()[toPos];
 645     dupElm(data()[frPos], toE);
 646     *findForNewInsert(table, mask, toE.probe()) = toPos;
 647     if (toE.hasIntKey()) {
 648       set->updateNextKI(toE.ikey);
 649     } else {
 650       assert(toE.hasStrKey());
 651     }
 652   }
 653   return Object{std::move(set)};
 654 }
 655
 656 template<class TSet>
 657 typename std::enable_if<
 658   std::is_base_of<BaseSet, TSet>::value, Object>::type
 659 BaseSet::php_skipWhile(const Variant& fn) {
 660   CallCtx ctx;
 661   vm_decode_function(fn, nullptr, false, ctx);
 662   if (!ctx.func) {
 663     SystemLib::throwInvalidArgumentExceptionObject(
 664                "Parameter must be a valid callback");
 665   }
 666   auto set = req::make<TSet>();
 667   if (!m_size) return Object(std::move(set));
 668   // we don't reserve(), because we don't know how selective fn will be
 669   set->mutate();
 670   int32_t version UNUSED;
 671   if (std::is_same<c_Set, TSet>::value) {
 672     version = m_version;
 673   }
 674   uint32_t used = posLimit();
 675   uint32_t i = 0;
 676   for (; i < used; ++i) {
 677     if (isTombstone(i)) continue;
 678     Elm& e = data()[i];
 679     bool b = invokeAndCastToBool(ctx, 1, &e.data);
 680     if (std::is_same<c_Set, TSet>::value) {
 681       if (UNLIKELY(version != m_version)) {
 682         throw_collection_modified();
 683       }
 684     }
 685     if (!b) break;
 686   }
 687   for (; i < used; ++i) {
 688     if (isTombstone(i)) continue;
 689     Elm& e = data()[i];
 690     if (e.hasIntKey()) {
 691       set->addRaw(e.data.m_data.num);
 692     } else {
 693       assert(e.hasStrKey());
 694       set->addRaw(e.data.m_data.pstr);
 695     }
 696   }
 697   return Object(std::move(set));
 698 }
 699
 700 template<class TSet>
 701 typename std::enable_if<
 702   std::is_base_of<BaseSet, TSet>::value, Object>::type
 703 BaseSet::php_slice(const Variant& start, const Variant& len) {
 704   int64_t istart;
 705   int64_t ilen;
 706   if (!start.isInteger() || (istart = start.toInt64()) < 0) {
 707     SystemLib::throwInvalidArgumentExceptionObject(
 708       "Parameter start must be a non-negative integer");
 709   }
 710   if (!len.isInteger() || (ilen = len.toInt64()) < 0) {
 711     SystemLib::throwInvalidArgumentExceptionObject(
 712       "Parameter len must be a non-negative integer");
 713   }
 714   size_t skipAmt = std::min<size_t>(istart, m_size);
 715   size_t sz = std::min<size_t>(ilen, size_t(m_size) - skipAmt);
 716   auto set = req::make<TSet>();
 717   set->reserve(sz);
 718   set->setSize(sz);
 719   set->setPosLimit(sz);
 720   uint32_t frPos = nthElmPos(skipAmt);
 721   auto table = set->hashTab();
 722   auto mask = set->tableMask();
 723   for (uint32_t toPos = 0; toPos < sz; ++toPos, ++frPos) {
 724     frPos = skipTombstonesNoBoundsCheck(frPos);
 725     auto& toE = set->data()[toPos];
 726     dupElm(data()[frPos], toE);
 727     *findForNewInsert(table, mask, toE.probe()) = toPos;
 728     if (toE.hasIntKey()) {
 729       set->updateNextKI(toE.ikey);
 730     } else {
 731       assert(toE.hasStrKey());
 732     }
 733   }
 734   return Object{std::move(set)};
 735 }
 736
 737 template<class TVector>
 738 typename std::enable_if<
 739   std::is_base_of<BaseVector, TVector>::value, Object>::type
 740 BaseSet::php_concat(const Variant& iterable) {
 741   size_t itSize;
 742   ArrayIter iter = getArrayIterHelper(iterable, itSize);
 743   auto vec = req::make<TVector>();
 744   uint32_t sz = m_size;
 745   vec->reserve((size_t)sz + itSize);
 746   assert(vec->canMutateBuffer());
 747   vec->setSize(sz);
 748
 749   uint32_t used = posLimit();
 750   for (uint32_t i = 0, j = 0; i < used; ++i) {
 751     if (isTombstone(i)) {
 752       continue;
 753     }
 754     cellDup(data()[i].data, vec->data()[j]);
 755     ++j;
 756   }
 757   for (; iter; ++iter) {
 758     vec->addRaw(iter.second());
 759   }
 760   return Object{std::move(vec)};
 761 }
 762
 763 Object BaseSet::getIterator() {
 764   auto iter = collections::SetIterator::newInstance();
 765   Native::data<collections::SetIterator>(iter)->setSet(this);
 766   return iter;
 767 }
 768
 769 ///////////////////////////////////////////////////////////////////////////////
 770 // Set
 771
 772 void c_Set::clear() {
 773   ++m_version;
 774   dropImmCopy();
 775   decRefArr(arrayData());
 776   m_arr = staticEmptyDictArrayAsMixed();
 777   m_size = 0;
 778 }
 779
 780 c_Set* c_Set::Clone(ObjectData* obj) {
 781   return BaseSet::Clone<c_Set>(obj);
 782 }
 783
 784 ///////////////////////////////////////////////////////////////////////////////
 785 // ImmSet
 786
 787 c_ImmSet* c_ImmSet::Clone(ObjectData* obj) {
 788   return BaseSet::Clone<c_ImmSet>(obj);
 789 }
 790
 791 namespace collections {
 792 /////////////////////////////////////////////////////////////////////////////
 793
 794 const StaticString
 795   s_HH_Set("HH\\Set"),
 796   s_HH_ImmSet("HH\\ImmSet"),
 797   s_SetIterator("SetIterator");
 798
 799 /////////////////////////////////////////////////////////////////////////////
 800 // SetIterator
 801
 802 static Variant HHVM_METHOD(SetIterator, current) {
 803   return Native::data<SetIterator>(this_)->current();
 804 }
 805
 806 static Variant HHVM_METHOD(SetIterator, key) {
 807   return Native::data<SetIterator>(this_)->key();
 808 }
 809
 810 static bool HHVM_METHOD(SetIterator, valid) {
 811   return Native::data<SetIterator>(this_)->valid();
 812 }
 813
 814 static void HHVM_METHOD(SetIterator, next) {
 815   Native::data<SetIterator>(this_)->next();
 816 }
 817
 818 static void HHVM_METHOD(SetIterator, rewind) {
 819   Native::data<SetIterator>(this_)->rewind();
 820 }
 821
 822 /////////////////////////////////////////////////////////////////////////////
 823
 824 void CollectionsExtension::initSet() {
 825   HHVM_ME(SetIterator, current);
 826   HHVM_ME(SetIterator, key);
 827   HHVM_ME(SetIterator, valid);
 828   HHVM_ME(SetIterator, next);
 829   HHVM_ME(SetIterator, rewind);
 830
 831   Native::registerNativeDataInfo<SetIterator>(
 832     s_SetIterator.get(),
 833     Native::NDIFlags::NO_SWEEP
 834   );
 835
 836 #define BASE_ME(mn, impl) \
 837   HHVM_NAMED_ME(HH\\Set,    mn, impl); \
 838   HHVM_NAMED_ME(HH\\ImmSet, mn, impl);
 839   BASE_ME(__construct,   &BaseSet::init);
 840   BASE_ME(count,         &BaseSet::size);
 841   BASE_ME(contains,      &BaseSet::php_contains);
 842   BASE_ME(toArray,       &BaseSet::toArray);
 843   BASE_ME(toKeysArray,   &BaseSet::toKeysArray);
 844   BASE_ME(toValuesArray, &BaseSet::toValuesArray);
 845   BASE_ME(getIterator,   &BaseSet::getIterator);
 846   BASE_ME(firstValue,    &BaseSet::firstValue);
 847   BASE_ME(lastValue,     &BaseSet::lastValue);
 848 #undef BASE_ME
 849
 850 #define TMPL_STATIC_ME(mn) \
 851   HHVM_NAMED_STATIC_ME(HH\\Set,    mn, BaseSet::mn<c_Set>); \
 852   HHVM_NAMED_STATIC_ME(HH\\ImmSet, mn, BaseSet::mn<c_ImmSet>);
 853   TMPL_STATIC_ME(fromItems);
 854   TMPL_STATIC_ME(fromKeysOf);
 855   TMPL_STATIC_ME(fromArray);
 856 #undef TMPL_STATIC_ME
 857
 858 #define TMPL_ME(mn, impl, ret) \
 859   HHVM_NAMED_ME(HH\\Set,    mn, impl<c_##ret>); \
 860   HHVM_NAMED_ME(HH\\ImmSet, mn, impl<c_Imm##ret>);
 861   TMPL_ME(zip,       &BaseSet::php_zip,       Set);
 862   TMPL_ME(take,      &BaseSet::php_take,      Set);
 863   TMPL_ME(takeWhile, &BaseSet::php_takeWhile, Set);
 864   TMPL_ME(skip,      &BaseSet::php_skip,      Set);
 865   TMPL_ME(skipWhile, &BaseSet::php_skipWhile, Set);
 866   TMPL_ME(slice,     &BaseSet::php_slice,     Set);
 867   TMPL_ME(values,    &BaseSet::php_values,    Vector);
 868   TMPL_ME(concat,    &BaseSet::php_concat,    Vector);
 869 #undef TMPL_ME
 870
 871   auto const m     = &BaseSet::php_map<c_Set, false>;
 872   auto const mk    = &BaseSet::php_map<c_Set, true>;
 873   auto const immm  = &BaseSet::php_map<c_ImmSet, false>;
 874   auto const immmk = &BaseSet::php_map<c_ImmSet, true>;
 875   HHVM_NAMED_ME(HH\\Set,    map,        m);
 876   HHVM_NAMED_ME(HH\\Set,    mapWithKey, mk);
 877   HHVM_NAMED_ME(HH\\ImmSet, map,        immm);
 878   HHVM_NAMED_ME(HH\\ImmSet, mapWithKey, immmk);
 879
 880   auto const f     = &BaseSet::php_filter<c_Set, false>;
 881   auto const fk    = &BaseSet::php_filter<c_Set, true>;
 882   auto const immf  = &BaseSet::php_filter<c_ImmSet, false>;
 883   auto const immfk = &BaseSet::php_filter<c_ImmSet, true>;
 884   HHVM_NAMED_ME(HH\\Set,    filter,        f);
 885   HHVM_NAMED_ME(HH\\Set,    filterWithKey, fk);
 886   HHVM_NAMED_ME(HH\\ImmSet, filter,        immf);
 887   HHVM_NAMED_ME(HH\\ImmSet, filterWithKey, immfk);
 888
 889   HHVM_NAMED_ME(HH\\Set,    toVector,    materialize<c_Vector>);
 890   HHVM_NAMED_ME(HH\\Set,    toImmVector, materialize<c_ImmVector>);
 891   HHVM_NAMED_ME(HH\\Set,    toMap,       materialize<c_Map>);
 892   HHVM_NAMED_ME(HH\\Set,    toImmMap,    materialize<c_ImmMap>);
 893   HHVM_NAMED_ME(HH\\ImmSet, toVector,    materialize<c_Vector>);
 894   HHVM_NAMED_ME(HH\\ImmSet, toImmVector, materialize<c_ImmVector>);
 895   HHVM_NAMED_ME(HH\\ImmSet, toMap,       materialize<c_Map>);
 896   HHVM_NAMED_ME(HH\\ImmSet, toImmMap,    materialize<c_ImmMap>);
 897   HHVM_NAMED_ME(HH\\ImmSet, toSet,       materialize<c_Set>);
 898
 899   HHVM_NAMED_ME(HH\\Set, add,            &c_Set::php_add);
 900   HHVM_NAMED_ME(HH\\Set, addAll,         &c_Set::php_addAll);
 901   HHVM_NAMED_ME(HH\\Set, addAllKeysOf,   &c_Set::php_addAllKeysOf);
 902   HHVM_NAMED_ME(HH\\Set, clear,          &c_Set::php_clear);
 903   HHVM_NAMED_ME(HH\\Set, remove,         &c_Set::php_remove);
 904   HHVM_NAMED_ME(HH\\Set, removeAll,      &c_Set::php_removeAll);
 905   HHVM_NAMED_ME(HH\\Set, reserve,        &c_Set::php_reserve);
 906   HHVM_NAMED_ME(HH\\Set, retain,         &c_Set::php_retain<false>);
 907   HHVM_NAMED_ME(HH\\Set, retainWithKey,  &c_Set::php_retain<true>);
 908   HHVM_NAMED_ME(HH\\Set, toImmSet,       &c_Set::getImmutableCopy);
 909
 910   loadSystemlib("collections-set");
 911
 912   c_Set::s_cls = Unit::lookupClass(s_HH_Set.get());
 913   assertx(c_Set::s_cls);
 914   finishClass<c_Set>();
 915
 916   c_ImmSet::s_cls = Unit::lookupClass(s_HH_ImmSet.get());
 917   assertx(c_ImmSet::s_cls);
 918   finishClass<c_ImmSet>();
 919 }
 920
 921 /////////////////////////////////////////////////////////////////////////////
 922 }}