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

   1 #pragma once
   2
   3 #include "hphp/runtime/ext/collections/ext_collections.h"
   4 #include "hphp/runtime/ext/collections/hash-collection.h"
   5 #include "hphp/runtime/base/builtin-functions.h"
   6 #include "hphp/runtime/base/container-functions.h"
   7 #include "hphp/runtime/vm/native-data.h"
   8 #include "hphp/system/systemlib.h"
   9
  10 namespace HPHP {
  11 /////////////////////////////////////////////////////////////////////////////
  12 // BaseSet
  13
  14 struct BaseVector;
  15
  16 namespace collections {
  17 struct SetIterator;
  18 }
  19
  20 /**
  21  * BaseSet is a hash-table implementation of the Set ADT. It doesn't represent
  22  * any PHP-land class. That job is delegated to its c_-prefixed child classes.
  23  */
  24 struct BaseSet : HashCollection {
  25   void addAllKeysOf(TypedValue container);
  26   void addAll(const Variant& t);
  27
  28   void init(const Variant& t) {
  29     assertx(m_size == 0);
  30     addAll(t);
  31   }
  32
  33 protected:
  34   template<bool raw> void addImpl(int64_t k);
  35   template<bool raw> void addImpl(StringData* k);
  36
  37   void addRaw(int64_t k);
  38   void addRaw(StringData* k);
  39   void addRaw(TypedValue tv) {
  40     tv = tvClassToString(tv);
  41     if (tv.m_type == KindOfInt64) {
  42       addRaw(tv.m_data.num);
  43     } else if (isStringType(tv.m_type)) {
  44       addRaw(tv.m_data.pstr);
  45     } else {
  46       throwBadValueType();
  47     }
  48   }
  49   void addRaw(const Variant& v) { addRaw(*v.asTypedValue()); }
  50
  51 public:
  52   /*
  53    * Append an element to the Set, increffing it if it's refcounted.
  54    */
  55   void add(int64_t k);
  56   void add(StringData* k);
  57   void add(TypedValue tv) {
  58     tv = tvClassToString(tv);
  59     if (tv.m_type == KindOfInt64) {
  60       add(tv.m_data.num);
  61     } else if (isStringType(tv.m_type)) {
  62       add(tv.m_data.pstr);
  63     } else {
  64       throwBadValueType();
  65     }
  66   }
  67   void add(const Variant& v) { add(*v.asTypedValue()); }
  68
  69   /*
  70    * Append an element to the Set, increffing it if it's refcounted.
  71    *
  72    * When there is a conflict, the add() API is supposed to replace the
  73    * existing element with the new element in place. However since Sets
  74    * currently only support integer and string elements, there is no way
  75    * user code can really tell whether the existing element was replaced
  76    * so for efficiency we do nothing.
  77    */
  78   void SetIntMoveSkipConflict(int64_t k, TypedValue v);
  79   void SetStrMoveSkipConflict(StringData* k, TypedValue v);
  80
  81   /*
  82    * Prepend an element to the Set, increffing it if it's refcounted.
  83    */
  84   void addFront(int64_t k);
  85   void addFront(StringData* k);
  86   void addFront(TypedValue tv) {
  87     tv = tvClassToString(tv);
  88     if (tv.m_type == KindOfInt64) {
  89       addFront(tv.m_data.num);
  90     } else if (isStringType(tv.m_type)) {
  91       addFront(tv.m_data.pstr);
  92     } else {
  93       throwBadValueType();
  94     }
  95   }
  96
  97   Variant firstValue();
  98   Variant lastValue();
  99   Variant pop();
 100   Variant popFront();
 101
 102   template<class TSet>
 103   typename std::enable_if<
 104     std::is_base_of<BaseSet, TSet>::value, TSet*>::type
 105   static Clone(ObjectData* obj);
 106
 107   template <IntishCast intishCast = IntishCast::None>
 108   static Array ToArray(const ObjectData* obj) {
 109     check_collection_cast_to_array();
 110     return const_cast<BaseSet*>(
 111       static_cast<const BaseSet*>(obj)
 112     )->toPHPArrayImpl<intishCast>();
 113   }
 114
 115   static bool ToBool(const ObjectData* obj);
 116
 117   template <bool throwOnMiss>
 118   static TypedValue* OffsetAt(ObjectData* obj, const TypedValue* key) {
 119     auto set = static_cast<BaseSet*>(obj);
 120     auto const ktv = tvClassToString(*key);
 121     ssize_t p;
 122     if (ktv.m_type == KindOfInt64) {
 123       p = set->find(ktv.m_data.num, hash_int64(ktv.m_data.num));
 124     } else if (isStringType(ktv.m_type)) {
 125       p = set->find(ktv.m_data.pstr, ktv.m_data.pstr->hash());
 126     } else {
 127       BaseSet::throwBadValueType();
 128     }
 129     if (LIKELY(p != Empty)) {
 130       return reinterpret_cast<TypedValue*>(&set->data()[p].data);
 131     }
 132     if (!throwOnMiss) {
 133       return nullptr;
 134     }
 135     if (ktv.m_type == KindOfInt64) {
 136       collections::throwUndef(ktv.m_data.num);
 137     } else {
 138       assertx(isStringType(ktv.m_type));
 139       collections::throwUndef(ktv.m_data.pstr);
 140     }
 141   }
 142   static bool OffsetIsset(ObjectData* obj, const TypedValue* key);
 143   static bool OffsetContains(ObjectData* obj, const TypedValue* key);
 144   static void OffsetUnset(ObjectData* obj, const TypedValue* key);
 145
 146   static bool Equals(const ObjectData* obj1, const ObjectData* obj2);
 147
 148 protected:
 149   template<class TVector>
 150   Object php_values() {
 151     auto vec = req::make<TVector>();
 152     vec->init(VarNR(this));
 153     return Object{std::move(vec)};
 154   }
 155
 156   template<class TSet>
 157   typename std::enable_if<
 158     std::is_base_of<BaseSet, TSet>::value, Object>::type
 159   php_zip(const Variant& iterable);
 160
 161   template<class TSet>
 162   typename std::enable_if<
 163     std::is_base_of<BaseSet, TSet>::value, Object>::type
 164   php_take(const Variant& n);
 165
 166   template<class TSet>
 167   typename std::enable_if<
 168     std::is_base_of<BaseSet, TSet>::value, Object>::type
 169   php_skip(const Variant& n);
 170
 171   template<class TSet>
 172   typename std::enable_if<
 173     std::is_base_of<BaseSet, TSet>::value, Object>::type
 174   php_slice(const Variant& start, const Variant& len);
 175
 176   template<class TVector>
 177   typename std::enable_if<
 178     std::is_base_of<BaseVector, TVector>::value, Object>::type
 179   php_concat(const Variant& iterable);
 180
 181   template<class TSet>
 182   static typename std::enable_if<
 183     std::is_base_of<BaseSet, TSet>::value, Object>::type
 184   fromItems(const Class*, const Variant& iterable) {
 185     auto set = req::make<TSet>();
 186     set->addAll(iterable);
 187     return Object(std::move(set));
 188   }
 189
 190   template<class TSet>
 191   static typename std::enable_if<
 192     std::is_base_of<BaseSet, TSet>::value, Object>::type
 193   fromKeysOf(const Class*, const Variant& container) {
 194     if (container.isNull()) {
 195       return Object(req::make<TSet>());
 196     }
 197     auto const& cellContainer = container_as_tv(container);
 198     auto target = req::make<TSet>();
 199     target->addAllKeysOf(cellContainer);
 200     return Object(std::move(target));
 201   }
 202
 203   template<class TSet>
 204   static typename std::enable_if<
 205     std::is_base_of<BaseSet, TSet>::value, Object>::type
 206   fromArray(const Class*, const Variant& arr) {
 207     if (!arr.isArray()) {
 208       SystemLib::throwInvalidArgumentExceptionObject(
 209         "Parameter arr must be an array");
 210     }
 211     auto set = req::make<TSet>();
 212     ArrayData* ad = arr.getArrayData();
 213     auto oldCap = set->cap();
 214     set->reserve(ad->size()); // presume minimum collisions ...
 215     ssize_t pos_limit = ad->iter_end();
 216     for (ssize_t pos = ad->iter_begin(); pos != pos_limit;
 217          pos = ad->iter_advance(pos)) {
 218       set->addRaw(ad->nvGetVal(pos));
 219     }
 220     set->shrinkIfCapacityTooHigh(oldCap); // ... and shrink if we were wrong
 221     return Object(std::move(set));
 222   }
 223
 224   Object getIterator();
 225   bool php_contains(const Variant& key) {
 226     auto const ktv = tvClassToString(*key.asTypedValue());
 227     DataType t = type(ktv);
 228     if (t == KindOfInt64) {
 229       return contains(ktv.m_data.num);
 230     }
 231     if (isStringType(t)) {
 232       return contains(ktv.m_data.pstr);
 233     }
 234     throwBadValueType();
 235   }
 236
 237 public:
 238   [[noreturn]] static void throwNoMutableIndexAccess();
 239   [[noreturn]] static void throwBadValueType();
 240
 241 protected:
 242   // BaseSet is an abstract class with no additional member needing
 243   // initialization.
 244   using HashCollection::HashCollection;
 245
 246   ~BaseSet();
 247
 248 private:
 249
 250   friend struct collections::CollectionsExtension;
 251   friend struct collections::SetIterator;
 252   friend struct c_Vector;
 253   friend struct c_Set;
 254   friend struct c_Map;
 255
 256   static void compileTimeAssertions() {
 257     // For performance, all native collection classes have their m_size field
 258     // at the same offset.
 259     static_assert(offsetof(BaseSet, m_size) ==
 260                   collections::FAST_SIZE_OFFSET, "");
 261   }
 262 };
 263
 264 /////////////////////////////////////////////////////////////////////////////
 265 // c_Set
 266
 267 struct c_Set : BaseSet {
 268   DECLARE_COLLECTIONS_CLASS(Set)
 269
 270  public:
 271   // PHP-land methods.
 272   explicit c_Set()
 273     : BaseSet(c_Set::classof(), HeaderKind::Set) { }
 274   explicit c_Set(ArrayData* arr)
 275     : BaseSet(c_Set::classof(), HeaderKind::Set, arr) { }
 276   explicit c_Set(uint32_t cap)
 277     : BaseSet(c_Set::classof(), HeaderKind::Set, cap) { }
 278
 279   void clear();
 280   static c_Set* Clone(ObjectData* obj);
 281
 282  protected:
 283   friend struct collections::CollectionsExtension;
 284
 285   Object getImmutableCopy();
 286   Object php_add(const Variant& val) {
 287     add(val);
 288     return Object{this};
 289   }
 290   Object php_addAll(const Variant& it) {
 291     addAll(it);
 292     return Object{this};
 293   }
 294   Object php_addAllKeysOf(const Variant& container) {
 295     if (!container.isNull()) {
 296       auto const& containerCell = container_as_tv(container);
 297       addAllKeysOf(containerCell);
 298     }
 299     return Object{this};
 300   }
 301   Object php_clear() {
 302     clear();
 303     return Object{this};
 304   }
 305   Object php_remove(const Variant& key) {
 306     auto const ktv = tvClassToString(*key.asTypedValue());
 307     DataType t = type(ktv);
 308     if (t == KindOfInt64) {
 309       remove(ktv.m_data.num);
 310     } else if (isStringType(t)) {
 311       remove(ktv.m_data.pstr);
 312     } else {
 313       throwBadValueType();
 314     }
 315     return Object{this};
 316   }
 317   Object php_removeAll(const Variant& it) {
 318     size_t sz;
 319     ArrayIter iter = getArrayIterHelper(it, sz);
 320     for (; iter; ++iter) {
 321       Variant v = iter.second();
 322       auto const vtv = tvClassToString(*v.asTypedValue());
 323       if (type(vtv) == KindOfInt64) {
 324         remove(vtv.m_data.num);
 325       } else if (isStringType(type(vtv))) {
 326         remove(vtv.m_data.pstr);
 327       } else {
 328         throwBadValueType();
 329       }
 330     }
 331     return Object{this};
 332   }
 333   void php_reserve(int64_t cap) {
 334     if (UNLIKELY(cap < 0)) {
 335       SystemLib::throwInvalidArgumentExceptionObject(
 336         "Parameter sz must be a non-negative integer"
 337       );
 338     }
 339     reserve(cap);
 340   }
 341 };
 342
 343 ///////////////////////////////////////////////////////////////////////////////
 344 // class ImmSet
 345
 346 struct c_ImmSet : BaseSet {
 347   DECLARE_COLLECTIONS_CLASS(ImmSet)
 348
 349   explicit c_ImmSet()
 350     : BaseSet(c_ImmSet::classof(), HeaderKind::ImmSet) { }
 351   explicit c_ImmSet(ArrayData* arr)
 352     : BaseSet(c_ImmSet::classof(), HeaderKind::ImmSet, arr) { }
 353   explicit c_ImmSet(uint32_t cap)
 354     : BaseSet(c_ImmSet::classof(), HeaderKind::ImmSet, cap) { }
 355
 356   static c_ImmSet* Clone(ObjectData* obj);
 357 };
 358
 359 namespace collections {
 360 /////////////////////////////////////////////////////////////////////////////
 361
 362 extern const StaticString
 363   s_SetIterator;
 364
 365 struct SetIterator {
 366   SetIterator() {}
 367   SetIterator(const SetIterator& src) = delete;
 368   SetIterator& operator=(const SetIterator& src) {
 369     m_obj = src.m_obj;
 370     m_pos = src.m_pos;
 371     return *this;
 372   }
 373   ~SetIterator() {}
 374
 375   static Object newInstance() {
 376     static Class* cls = Class::lookup(s_SetIterator.get());
 377     assertx(cls);
 378     return Object{cls};
 379   }
 380
 381   void setSet(BaseSet* mp) {
 382     m_obj = mp;
 383     m_pos = mp->iter_begin();
 384   }
 385
 386   Variant current() const {
 387     auto st = m_obj.get();
 388     if (!st->iter_valid_and_not_tombstone(m_pos)) {
 389       throw_iterator_not_valid();
 390     }
 391     return tvAsCVarRef(st->iter_value(m_pos));
 392   }
 393
 394   Variant key() const { return current(); }
 395
 396   bool valid() const {
 397     return m_obj->iter_valid_and_not_tombstone(m_pos);
 398   }
 399
 400   void next() {
 401     auto st = m_obj.get();
 402     m_pos = st->iter_next(m_pos);
 403   }
 404
 405   void rewind() {
 406     auto st = m_obj.get();
 407     m_pos = st->iter_begin();
 408   }
 409
 410  private:
 411   req::ptr<BaseSet> m_obj;
 412   uint32_t m_pos{0};
 413 };
 414
 415 /////////////////////////////////////////////////////////////////////////////
 416 }}