js/public/GCVector.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef js_GCVector_h
   8 #define js_GCVector_h
   9
  10 #include "mozilla/Assertions.h"       // MOZ_ASSERT
  11 #include "mozilla/Attributes.h"       // MOZ_STACK_CLASS
  12 #include "mozilla/MemoryReporting.h"  // MallocSizeOf
  13 #include "mozilla/Span.h"
  14 #include "mozilla/Vector.h"
  15
  16 #include <stddef.h>  // size_t
  17 #include <utility>   // forward, move
  18
  19 #include "js/AllocPolicy.h"
  20 #include "js/GCPolicyAPI.h"
  21 #include "js/RootingAPI.h"
  22
  23 class JSTracer;
  24 struct JSContext;
  25
  26 namespace JS {
  27
  28 // A GCVector is a Vector with an additional trace method that knows how
  29 // to visit all of the items stored in the Vector. For vectors that contain GC
  30 // things, this is usually more convenient than manually iterating and marking
  31 // the contents.
  32 //
  33 // Most types of GC pointers as keys and values can be traced with no extra
  34 // infrastructure. For structs and non-gc-pointer members, ensure that there is
  35 // a specialization of GCPolicy<T> with an appropriate trace method available
  36 // to handle the custom type. Generic helpers can be found in
  37 // js/public/TracingAPI.h.
  38 //
  39 // Note that although this Vector's trace will deal correctly with moved items,
  40 // it does not itself know when to barrier or trace items. To function properly
  41 // it must either be used with Rooted, or barriered and traced manually.
  42 template <typename T, size_t MinInlineCapacity = 0,
  43           typename AllocPolicy = js::TempAllocPolicy>
  44 class GCVector {
  45   mozilla::Vector<T, MinInlineCapacity, AllocPolicy> vector;
  46
  47  public:
  48   using ElementType = T;
  49   static constexpr size_t InlineLength = decltype(vector)::InlineLength;
  50
  51   explicit GCVector(AllocPolicy alloc) : vector(std::move(alloc)) {}
  52   GCVector() : GCVector(AllocPolicy()) {}
  53
  54   GCVector(GCVector&& vec) : vector(std::move(vec.vector)) {}
  55
  56   GCVector& operator=(GCVector&& vec) {
  57     vector = std::move(vec.vector);
  58     return *this;
  59   }
  60
  61   size_t length() const { return vector.length(); }
  62   bool empty() const { return vector.empty(); }
  63   size_t capacity() const { return vector.capacity(); }
  64
  65   T* begin() { return vector.begin(); }
  66   const T* begin() const { return vector.begin(); }
  67
  68   T* end() { return vector.end(); }
  69   const T* end() const { return vector.end(); }
  70
  71   T& operator[](size_t i) { return vector[i]; }
  72   const T& operator[](size_t i) const { return vector[i]; }
  73
  74   T& back() { return vector.back(); }
  75   const T& back() const { return vector.back(); }
  76
  77   operator mozilla::Span<T>() { return vector; }
  78   operator mozilla::Span<const T>() const { return vector; }
  79
  80   bool initCapacity(size_t cap) { return vector.initCapacity(cap); }
  81   [[nodiscard]] bool reserve(size_t req) { return vector.reserve(req); }
  82   void shrinkBy(size_t amount) { return vector.shrinkBy(amount); }
  83   void shrinkTo(size_t newLen) { return vector.shrinkTo(newLen); }
  84   [[nodiscard]] bool growBy(size_t amount) { return vector.growBy(amount); }
  85   [[nodiscard]] bool resize(size_t newLen) { return vector.resize(newLen); }
  86
  87   void clear() { return vector.clear(); }
  88   void clearAndFree() { return vector.clearAndFree(); }
  89
  90   template <typename U>
  91   bool append(U&& item) {
  92     return vector.append(std::forward<U>(item));
  93   }
  94
  95   void erase(T* it) { vector.erase(it); }
  96   void erase(T* begin, T* end) { vector.erase(begin, end); }
  97   template <typename Pred>
  98   void eraseIf(Pred pred) {
  99     vector.eraseIf(pred);
 100   }
 101   template <typename U>
 102   void eraseIfEqual(const U& u) {
 103     vector.eraseIfEqual(u);
 104   }
 105
 106   template <typename... Args>
 107   [[nodiscard]] bool emplaceBack(Args&&... args) {
 108     return vector.emplaceBack(std::forward<Args>(args)...);
 109   }
 110
 111   template <typename... Args>
 112   void infallibleEmplaceBack(Args&&... args) {
 113     vector.infallibleEmplaceBack(std::forward<Args>(args)...);
 114   }
 115
 116   template <typename U>
 117   void infallibleAppend(U&& aU) {
 118     return vector.infallibleAppend(std::forward<U>(aU));
 119   }
 120   void infallibleAppendN(const T& aT, size_t aN) {
 121     return vector.infallibleAppendN(aT, aN);
 122   }
 123   template <typename U>
 124   void infallibleAppend(const U* aBegin, const U* aEnd) {
 125     return vector.infallibleAppend(aBegin, aEnd);
 126   }
 127   template <typename U>
 128   void infallibleAppend(const U* aBegin, size_t aLength) {
 129     return vector.infallibleAppend(aBegin, aLength);
 130   }
 131
 132   template <typename U>
 133   [[nodiscard]] bool appendAll(const U& aU) {
 134     return vector.append(aU.begin(), aU.end());
 135   }
 136   template <typename T2, size_t MinInlineCapacity2, typename AllocPolicy2>
 137   [[nodiscard]] bool appendAll(
 138       GCVector<T2, MinInlineCapacity2, AllocPolicy2>&& aU) {
 139     return vector.appendAll(aU.begin(), aU.end());
 140   }
 141
 142   [[nodiscard]] bool appendN(const T& val, size_t count) {
 143     return vector.appendN(val, count);
 144   }
 145
 146   template <typename U>
 147   [[nodiscard]] bool append(const U* aBegin, const U* aEnd) {
 148     return vector.append(aBegin, aEnd);
 149   }
 150   template <typename U>
 151   [[nodiscard]] bool append(const U* aBegin, size_t aLength) {
 152     return vector.append(aBegin, aLength);
 153   }
 154
 155   void popBack() { return vector.popBack(); }
 156   T popCopy() { return vector.popCopy(); }
 157
 158   size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 159     return vector.sizeOfExcludingThis(mallocSizeOf);
 160   }
 161
 162   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 163     return vector.sizeOfIncludingThis(mallocSizeOf);
 164   }
 165
 166   void trace(JSTracer* trc) {
 167     for (auto& elem : vector) {
 168       GCPolicy<T>::trace(trc, &elem, "vector element");
 169     }
 170   }
 171
 172   bool traceWeak(JSTracer* trc) {
 173     mutableEraseIf(
 174         [trc](T& elem) { return !GCPolicy<T>::traceWeak(trc, &elem); });
 175     return !empty();
 176   }
 177
 178   // Like eraseIf, but may mutate the contents of the vector. Iterates from
 179   // |startIndex| to the last element of the vector.
 180   template <typename Pred>
 181   void mutableEraseIf(Pred pred, size_t startIndex = 0) {
 182     MOZ_ASSERT(startIndex <= length());
 183
 184     T* src = begin() + startIndex;
 185     T* dst = src;
 186     while (src != end()) {
 187       if (!pred(*src)) {
 188         if (src != dst) {
 189           *dst = std::move(*src);
 190         }
 191         dst++;
 192       }
 193       src++;
 194     }
 195
 196     MOZ_ASSERT(dst <= end());
 197     shrinkBy(end() - dst);
 198   }
 199 };
 200
 201 // AllocPolicy is optional. It has a default value declared in TypeDecls.h
 202 template <typename T, typename AllocPolicy>
 203 class MOZ_STACK_CLASS StackGCVector : public GCVector<T, 8, AllocPolicy> {
 204  public:
 205   using Base = GCVector<T, 8, AllocPolicy>;
 206
 207  private:
 208   // Inherit constructor from GCVector.
 209   using Base::Base;
 210 };
 211
 212 }  // namespace JS
 213
 214 namespace js {
 215
 216 template <typename Wrapper, typename T, size_t Capacity, typename AllocPolicy>
 217 class WrappedPtrOperations<JS::GCVector<T, Capacity, AllocPolicy>, Wrapper> {
 218   using Vec = JS::GCVector<T, Capacity, AllocPolicy>;
 219   const Vec& vec() const { return static_cast<const Wrapper*>(this)->get(); }
 220
 221  public:
 222   const AllocPolicy& allocPolicy() const { return vec().allocPolicy(); }
 223   size_t length() const { return vec().length(); }
 224   bool empty() const { return vec().empty(); }
 225   size_t capacity() const { return vec().capacity(); }
 226   const T* begin() const { return vec().begin(); }
 227   const T* end() const { return vec().end(); }
 228   const T& back() const { return vec().back(); }
 229
 230   JS::Handle<T> operator[](size_t aIndex) const {
 231     return JS::Handle<T>::fromMarkedLocation(&vec().operator[](aIndex));
 232   }
 233 };
 234
 235 template <typename Wrapper, typename T, size_t Capacity, typename AllocPolicy>
 236 class MutableWrappedPtrOperations<JS::GCVector<T, Capacity, AllocPolicy>,
 237                                   Wrapper>
 238     : public WrappedPtrOperations<JS::GCVector<T, Capacity, AllocPolicy>,
 239                                   Wrapper> {
 240   using Vec = JS::GCVector<T, Capacity, AllocPolicy>;
 241   const Vec& vec() const { return static_cast<const Wrapper*>(this)->get(); }
 242   Vec& vec() { return static_cast<Wrapper*>(this)->get(); }
 243
 244  public:
 245   const AllocPolicy& allocPolicy() const { return vec().allocPolicy(); }
 246   AllocPolicy& allocPolicy() { return vec().allocPolicy(); }
 247   const T* begin() const { return vec().begin(); }
 248   T* begin() { return vec().begin(); }
 249   const T* end() const { return vec().end(); }
 250   T* end() { return vec().end(); }
 251   const T& back() const { return vec().back(); }
 252   T& back() { return vec().back(); }
 253
 254   JS::Handle<T> operator[](size_t aIndex) const {
 255     return JS::Handle<T>::fromMarkedLocation(&vec().operator[](aIndex));
 256   }
 257   JS::MutableHandle<T> operator[](size_t aIndex) {
 258     return JS::MutableHandle<T>::fromMarkedLocation(&vec().operator[](aIndex));
 259   }
 260
 261   [[nodiscard]] bool initCapacity(size_t aRequest) {
 262     return vec().initCapacity(aRequest);
 263   }
 264   [[nodiscard]] bool reserve(size_t aRequest) {
 265     return vec().reserve(aRequest);
 266   }
 267   void shrinkBy(size_t aIncr) { vec().shrinkBy(aIncr); }
 268   [[nodiscard]] bool growBy(size_t aIncr) { return vec().growBy(aIncr); }
 269   [[nodiscard]] bool resize(size_t aNewLength) {
 270     return vec().resize(aNewLength);
 271   }
 272   void clear() { vec().clear(); }
 273   void clearAndFree() { vec().clearAndFree(); }
 274   template <typename U>
 275   [[nodiscard]] bool append(U&& aU) {
 276     return vec().append(std::forward<U>(aU));
 277   }
 278   template <typename... Args>
 279   [[nodiscard]] bool emplaceBack(Args&&... aArgs) {
 280     return vec().emplaceBack(std::forward<Args>(aArgs)...);
 281   }
 282   template <typename... Args>
 283   void infallibleEmplaceBack(Args&&... args) {
 284     vec().infallibleEmplaceBack(std::forward<Args>(args)...);
 285   }
 286   template <typename U>
 287   [[nodiscard]] bool appendAll(U&& aU) {
 288     return vec().appendAll(aU);
 289   }
 290   [[nodiscard]] bool appendN(const T& aT, size_t aN) {
 291     return vec().appendN(aT, aN);
 292   }
 293   template <typename U>
 294   [[nodiscard]] bool append(const U* aBegin, const U* aEnd) {
 295     return vec().append(aBegin, aEnd);
 296   }
 297   template <typename U>
 298   [[nodiscard]] bool append(const U* aBegin, size_t aLength) {
 299     return vec().append(aBegin, aLength);
 300   }
 301   template <typename U>
 302   void infallibleAppend(U&& aU) {
 303     vec().infallibleAppend(std::forward<U>(aU));
 304   }
 305   void infallibleAppendN(const T& aT, size_t aN) {
 306     vec().infallibleAppendN(aT, aN);
 307   }
 308   template <typename U>
 309   void infallibleAppend(const U* aBegin, const U* aEnd) {
 310     vec().infallibleAppend(aBegin, aEnd);
 311   }
 312   template <typename U>
 313   void infallibleAppend(const U* aBegin, size_t aLength) {
 314     vec().infallibleAppend(aBegin, aLength);
 315   }
 316   void popBack() { vec().popBack(); }
 317   T popCopy() { return vec().popCopy(); }
 318   void erase(T* aT) { vec().erase(aT); }
 319   void erase(T* aBegin, T* aEnd) { vec().erase(aBegin, aEnd); }
 320   template <typename Pred>
 321   void eraseIf(Pred pred) {
 322     vec().eraseIf(pred);
 323   }
 324   template <typename U>
 325   void eraseIfEqual(const U& u) {
 326     vec().eraseIfEqual(u);
 327   }
 328 };
 329
 330 template <typename Wrapper, typename T, typename AllocPolicy>
 331 class WrappedPtrOperations<JS::StackGCVector<T, AllocPolicy>, Wrapper>
 332     : public WrappedPtrOperations<
 333           typename JS::StackGCVector<T, AllocPolicy>::Base, Wrapper> {};
 334
 335 template <typename Wrapper, typename T, typename AllocPolicy>
 336 class MutableWrappedPtrOperations<JS::StackGCVector<T, AllocPolicy>, Wrapper>
 337     : public MutableWrappedPtrOperations<
 338           typename JS::StackGCVector<T, AllocPolicy>::Base, Wrapper> {};
 339
 340 }  // namespace js
 341
 342 namespace JS {
 343
 344 // An automatically rooted GCVector for stack use.
 345 template <typename T>
 346 class RootedVector : public Rooted<StackGCVector<T>> {
 347   using Vec = StackGCVector<T>;
 348   using Base = Rooted<Vec>;
 349
 350  public:
 351   explicit RootedVector(JSContext* cx) : Base(cx, Vec(cx)) {}
 352 };
 353
 354 // For use in rust code, an analog to RootedVector that doesn't require
 355 // instances to be destroyed in LIFO order.
 356 template <typename T>
 357 class PersistentRootedVector : public PersistentRooted<StackGCVector<T>> {
 358   using Vec = StackGCVector<T>;
 359   using Base = PersistentRooted<Vec>;
 360
 361  public:
 362   explicit PersistentRootedVector(JSContext* cx) : Base(cx, Vec(cx)) {}
 363 };
 364
 365 }  // namespace JS
 366
 367 #endif  // js_GCVector_h