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