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