src/third_party/WebKit/Source/platform/heap/Visitor.h

   1 /*
   2  * Copyright (C) 2013 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #ifndef Visitor_h
  32 #define Visitor_h
  33
  34 #include "platform/PlatformExport.h"
  35 #include "platform/heap/ThreadState.h"
  36 #include "wtf/Assertions.h"
  37 #include "wtf/Deque.h"
  38 #include "wtf/Forward.h"
  39 #include "wtf/HashCountedSet.h"
  40 #include "wtf/HashMap.h"
  41 #include "wtf/HashSet.h"
  42 #include "wtf/HashTraits.h"
  43 #include "wtf/InstanceCounter.h"
  44 #include "wtf/LinkedHashSet.h"
  45 #include "wtf/ListHashSet.h"
  46 #include "wtf/OwnPtr.h"
  47 #include "wtf/RefPtr.h"
  48 #include "wtf/TypeTraits.h"
  49 #include "wtf/WeakPtr.h"
  50 #if ENABLE(GC_TRACING)
  51 #include "wtf/text/WTFString.h"
  52 #endif
  53
  54 #ifndef NDEBUG
  55 #define DEBUG_ONLY(x) x
  56 #else
  57 #define DEBUG_ONLY(x)
  58 #endif
  59
  60 namespace WebCore {
  61
  62 class FinalizedHeapObjectHeader;
  63 template<typename T> class GarbageCollectedFinalized;
  64 class HeapObjectHeader;
  65 template<typename T> class Member;
  66 template<typename T> class WeakMember;
  67 class Visitor;
  68
  69 enum ShouldWeakPointersBeMarkedStrongly {
  70     WeakPointersActStrong,
  71     WeakPointersActWeak
  72 };
  73
  74 template<bool needsTracing, bool isWeak, ShouldWeakPointersBeMarkedStrongly strongify, typename T, typename Traits> struct CollectionBackingTraceTrait;
  75
  76 // The TraceMethodDelegate is used to convert a trace method for type T to a TraceCallback.
  77 // This allows us to pass a type's trace method as a parameter to the PersistentNode
  78 // constructor. The PersistentNode constructor needs the specific trace method due an issue
  79 // with the Windows compiler which instantiates even unused variables. This causes problems
  80 // in header files where we have only forward declarations of classes.
  81 template<typename T, void (T::*method)(Visitor*)>
  82 struct TraceMethodDelegate {
  83     static void trampoline(Visitor* visitor, void* self) { (reinterpret_cast<T*>(self)->*method)(visitor); }
  84 };
  85
  86 // GCInfo contains meta-data associated with objects allocated in the
  87 // Blink heap. This meta-data consists of a function pointer used to
  88 // trace the pointers in the object during garbage collection, an
  89 // indication of whether or not the object needs a finalization
  90 // callback, and a function pointer used to finalize the object when
  91 // the garbage collector determines that the object is no longer
  92 // reachable. There is a GCInfo struct for each class that directly
  93 // inherits from GarbageCollected or GarbageCollectedFinalized.
  94 struct GCInfo {
  95     bool hasFinalizer() const { return m_nonTrivialFinalizer; }
  96     bool hasVTable() const { return m_hasVTable; }
  97     TraceCallback m_trace;
  98     FinalizationCallback m_finalize;
  99     bool m_nonTrivialFinalizer;
 100     bool m_hasVTable;
 101 #if ENABLE(GC_TRACING)
 102     // |m_className| is held as a reference to prevent dtor being called at exit.
 103     const String& m_className;
 104 #endif
 105 };
 106
 107 // The FinalizerTraitImpl specifies how to finalize objects. Object
 108 // that inherit from GarbageCollectedFinalized are finalized by
 109 // calling their 'finalize' method which by default will call the
 110 // destructor on the object.
 111 template<typename T, bool isGarbageCollectedFinalized>
 112 struct FinalizerTraitImpl;
 113
 114 template<typename T>
 115 struct FinalizerTraitImpl<T, true> {
 116     static void finalize(void* obj) { static_cast<T*>(obj)->finalizeGarbageCollectedObject(); };
 117 };
 118
 119 template<typename T>
 120 struct FinalizerTraitImpl<T, false> {
 121     static void finalize(void* obj) { };
 122 };
 123
 124 // The FinalizerTrait is used to determine if a type requires
 125 // finalization and what finalization means.
 126 //
 127 // By default classes that inherit from GarbageCollectedFinalized need
 128 // finalization and finalization means calling the 'finalize' method
 129 // of the object. The FinalizerTrait can be specialized if the default
 130 // behavior is not desired.
 131 template<typename T>
 132 struct FinalizerTrait {
 133     static const bool nonTrivialFinalizer = WTF::IsSubclassOfTemplate<T, GarbageCollectedFinalized>::value;
 134     static void finalize(void* obj) { FinalizerTraitImpl<T, nonTrivialFinalizer>::finalize(obj); }
 135 };
 136
 137 // The VTableTrait is used to determine if a type has at least one virtual method.
 138 template<typename T>
 139 struct VTableTrait {
 140     static const bool hasVTable = __is_polymorphic(T);
 141 };
 142
 143 // Trait to get the GCInfo structure for types that have their
 144 // instances allocated in the Blink garbage-collected heap.
 145 template<typename T> struct GCInfoTrait;
 146
 147 template<typename T> class GarbageCollected;
 148 class GarbageCollectedMixin;
 149 template<typename T, bool = WTF::IsSubclassOfTemplate<T, GarbageCollected>::value> class NeedsAdjustAndMark;
 150
 151 template<typename T>
 152 class NeedsAdjustAndMark<T, true> {
 153 public:
 154     static const bool value = false;
 155 };
 156
 157 template<typename T>
 158 class NeedsAdjustAndMark<T, false> {
 159 public:
 160     static const bool value = WTF::IsSubclass<T, GarbageCollectedMixin>::value;
 161 };
 162
 163 template<typename T, bool = NeedsAdjustAndMark<T>::value> class DefaultTraceTrait;
 164
 165 // The TraceTrait is used to specify how to mark an object pointer and
 166 // how to trace all of the pointers in the object.
 167 //
 168 // By default, the 'trace' method implemented on an object itself is
 169 // used to trace the pointers to other heap objects inside the object.
 170 //
 171 // However, the TraceTrait can be specialized to use a different
 172 // implementation. A common case where a TraceTrait specialization is
 173 // needed is when multiple inheritance leads to pointers that are not
 174 // to the start of the object in the Blink garbage-collected heap. In
 175 // that case the pointer has to be adjusted before marking.
 176 template<typename T>
 177 class TraceTrait {
 178 public:
 179     // Default implementation of TraceTrait<T>::trace just statically
 180     // dispatches to the trace method of the class T.
 181     static void trace(Visitor* visitor, void* self)
 182     {
 183         static_cast<T*>(self)->trace(visitor);
 184     }
 185
 186     static void mark(Visitor* visitor, const T* t)
 187     {
 188         DefaultTraceTrait<T>::mark(visitor, t);
 189     }
 190
 191 #ifndef NDEBUG
 192     static void checkGCInfo(Visitor* visitor, const T* t)
 193     {
 194         DefaultTraceTrait<T>::checkGCInfo(visitor, t);
 195     }
 196 #endif
 197 };
 198
 199 template<typename T> class TraceTrait<const T> : public TraceTrait<T> { };
 200
 201 template<typename Collection>
 202 struct OffHeapCollectionTraceTrait;
 203
 204 template<typename T>
 205 struct ObjectAliveTrait {
 206     static bool isAlive(Visitor*, T*);
 207 };
 208
 209 // Visitor is used to traverse the Blink object graph. Used for the
 210 // marking phase of the mark-sweep garbage collector.
 211 //
 212 // Pointers are marked and pushed on the marking stack by calling the
 213 // |mark| method with the pointer as an argument.
 214 //
 215 // Pointers within objects are traced by calling the |trace| methods
 216 // with the object as an argument. Tracing objects will mark all of the
 217 // contained pointers and push them on the marking stack.
 218 class PLATFORM_EXPORT Visitor {
 219 public:
 220     virtual ~Visitor() { }
 221
 222     // One-argument templated mark method. This uses the static type of
 223     // the argument to get the TraceTrait. By default, the mark method
 224     // of the TraceTrait just calls the virtual two-argument mark method on this
 225     // visitor, where the second argument is the static trace method of the trait.
 226     template<typename T>
 227     void mark(T* t)
 228     {
 229         if (!t)
 230             return;
 231 #ifndef NDEBUG
 232         TraceTrait<T>::checkGCInfo(this, t);
 233 #endif
 234         TraceTrait<T>::mark(this, t);
 235     }
 236
 237     // Member version of the one-argument templated trace method.
 238     template<typename T>
 239     void trace(const Member<T>& t)
 240     {
 241         t.verifyTypeIsGarbageCollected();
 242         mark(t.get());
 243     }
 244
 245     // Fallback method used only when we need to trace raw pointers of T.
 246     // This is the case when a member is a union where we do not support members.
 247     template<typename T>
 248     void trace(T* t)
 249     {
 250         mark(t);
 251     }
 252
 253     // WeakMember version of the templated trace method. It doesn't keep
 254     // the traced thing alive, but will write null to the WeakMember later
 255     // if the pointed-to object is dead.
 256     template<typename T>
 257     void trace(const WeakMember<T>& t)
 258     {
 259         registerWeakCell(t.cell());
 260     }
 261
 262     // Fallback trace method for part objects to allow individual
 263     // trace methods to trace through a part object with
 264     // visitor->trace(m_partObject).
 265     template<typename T>
 266     void trace(const T& t)
 267     {
 268         const_cast<T&>(t).trace(this);
 269     }
 270
 271     // The following trace methods are for off-heap collections.
 272     template<typename T, size_t inlineCapacity>
 273     void trace(const Vector<T, inlineCapacity, WTF::DefaultAllocator>& vector)
 274     {
 275         OffHeapCollectionTraceTrait<Vector<T, inlineCapacity, WTF::DefaultAllocator> >::trace(this, vector);
 276     }
 277
 278     template<typename T, typename U, typename V>
 279     void trace(const HashSet<T, U, V, WTF::DefaultAllocator>& hashSet)
 280     {
 281         OffHeapCollectionTraceTrait<HashSet<T, U, V, WTF::DefaultAllocator> >::trace(this, hashSet);
 282     }
 283
 284     template<typename T, size_t inlineCapacity, typename U>
 285     void trace(const ListHashSet<T, inlineCapacity, U>& hashSet)
 286     {
 287         OffHeapCollectionTraceTrait<ListHashSet<T, inlineCapacity, U> >::trace(this, hashSet);
 288     }
 289
 290     template<typename T, typename U>
 291     void trace(const LinkedHashSet<T, U>& hashSet)
 292     {
 293         OffHeapCollectionTraceTrait<LinkedHashSet<T, U> >::trace(this, hashSet);
 294     }
 295
 296     template<typename T, size_t N>
 297     void trace(const Deque<T, N>& deque)
 298     {
 299         OffHeapCollectionTraceTrait<Deque<T, N> >::trace(this, deque);
 300     }
 301
 302     template<typename T, typename U, typename V>
 303     void trace(const HashCountedSet<T, U, V>& set)
 304     {
 305         OffHeapCollectionTraceTrait<HashCountedSet<T, U, V> >::trace(this, set);
 306     }
 307
 308     template<typename T, typename U, typename V, typename W, typename X>
 309     void trace(const HashMap<T, U, V, W, X, WTF::DefaultAllocator>& map)
 310     {
 311         OffHeapCollectionTraceTrait<HashMap<T, U, V, W, X, WTF::DefaultAllocator> >::trace(this, map);
 312     }
 313
 314     // OwnPtrs that are traced are treated as part objects and the
 315     // trace method of the owned object is called.
 316     template<typename T>
 317     void trace(const OwnPtr<T>& t)
 318     {
 319         if (t)
 320             t->trace(this);
 321     }
 322
 323     // This trace method is to trace a RefPtrWillBeMember when ENABLE(OILPAN)
 324     // is not enabled.
 325     // Remove this once we remove RefPtrWillBeMember.
 326     template<typename T>
 327     void trace(const RefPtr<T>&)
 328     {
 329 #if ENABLE(OILPAN)
 330         // RefPtrs should never be traced.
 331         ASSERT_NOT_REACHED();
 332 #endif
 333     }
 334
 335 #if !ENABLE(OILPAN)
 336     // Similarly, this trace method is to trace a RawPtrWillBeMember
 337     // when ENABLE(OILPAN) is not enabled.
 338     // Remove this once we remove RawPtrWillBeMember.
 339     template<typename T>
 340     void trace(const RawPtr<T>&)
 341     {
 342     }
 343 #endif
 344
 345     // This trace method is to trace a WeakPtrWillBeMember when ENABLE(OILPAN)
 346     // is not enabled.
 347     // Remove this once we remove WeakPtrWillBeMember.
 348     template<typename T>
 349     void trace(const WeakPtr<T>&)
 350     {
 351 #if ENABLE(OILPAN)
 352         // WeakPtrs should never be traced.
 353         ASSERT_NOT_REACHED();
 354 #endif
 355     }
 356
 357     // This method marks an object and adds it to the set of objects
 358     // that should have their trace method called. Since not all
 359     // objects have vtables we have to have the callback as an
 360     // explicit argument, but we can use the templated one-argument
 361     // mark method above to automatically provide the callback
 362     // function.
 363     virtual void mark(const void*, TraceCallback) = 0;
 364     virtual void markNoTracing(const void* pointer) { mark(pointer, reinterpret_cast<TraceCallback>(0)); }
 365
 366     // Used to mark objects during conservative scanning.
 367     virtual void mark(HeapObjectHeader*, TraceCallback) = 0;
 368     virtual void mark(FinalizedHeapObjectHeader*, TraceCallback) = 0;
 369     virtual void markConservatively(HeapObjectHeader*) = 0;
 370     virtual void markConservatively(FinalizedHeapObjectHeader*) = 0;
 371
 372     // If the object calls this during the regular trace callback, then the
 373     // WeakPointerCallback argument may be called later, when the strong roots
 374     // have all been found. The WeakPointerCallback will normally use isAlive
 375     // to find out whether some pointers are pointing to dying objects. When
 376     // the WeakPointerCallback is done the object must have purged all pointers
 377     // to objects where isAlive returned false. In the weak callback it is not
 378     // allowed to touch other objects (except using isAlive) or to allocate on
 379     // the GC heap. Note that even removing things from HeapHashSet or
 380     // HeapHashMap can cause an allocation if the backing store resizes, but
 381     // these collections know to remove WeakMember elements safely.
 382     //
 383     // The weak pointer callbacks are run on the thread that owns the
 384     // object and other threads are not stopped during the
 385     // callbacks. Since isAlive is used in the callback to determine
 386     // if objects pointed to are alive it is crucial that the object
 387     // pointed to belong to the same thread as the object receiving
 388     // the weak callback. Since other threads have been resumed the
 389     // mark bits are not valid for objects from other threads.
 390     virtual void registerWeakMembers(const void* object, WeakPointerCallback callback) { registerWeakMembers(object, object, callback); }
 391     virtual void registerWeakMembers(const void*, const void*, WeakPointerCallback) = 0;
 392
 393     template<typename T, void (T::*method)(Visitor*)>
 394     void registerWeakMembers(const T* obj)
 395     {
 396         registerWeakMembers(obj, &TraceMethodDelegate<T, method>::trampoline);
 397     }
 398
 399     // For simple cases where you just want to zero out a cell when the thing
 400     // it is pointing at is garbage, you can use this. This will register a
 401     // callback for each cell that needs to be zeroed, so if you have a lot of
 402     // weak cells in your object you should still consider using
 403     // registerWeakMembers above.
 404     //
 405     // In contrast to registerWeakMembers, the weak cell callbacks are
 406     // run on the thread performing garbage collection. Therefore, all
 407     // threads are stopped during weak cell callbacks.
 408     template<typename T>
 409     void registerWeakCell(T** cell)
 410     {
 411         registerWeakCell(reinterpret_cast<void**>(cell), &handleWeakCell<T>);
 412     }
 413
 414     virtual bool isMarked(const void*) = 0;
 415
 416     template<typename T> inline bool isAlive(T* obj)
 417     {
 418         return !!obj && ObjectAliveTrait<T>::isAlive(this, obj);
 419     }
 420     template<typename T> inline bool isAlive(const Member<T>& member)
 421     {
 422         return isAlive(member.get());
 423     }
 424     template<typename T> inline bool isAlive(RawPtr<T> ptr)
 425     {
 426         return isAlive(ptr.get());
 427     }
 428
 429 #ifndef NDEBUG
 430     void checkGCInfo(const void*, const GCInfo*);
 431 #endif
 432
 433     // Macro to declare methods needed for each typed heap.
 434 #define DECLARE_VISITOR_METHODS(Type)                                  \
 435     DEBUG_ONLY(void checkGCInfo(const Type*, const GCInfo*);)          \
 436     virtual void mark(const Type*, TraceCallback) = 0;                 \
 437     virtual bool isMarked(const Type*) = 0;
 438
 439     FOR_EACH_TYPED_HEAP(DECLARE_VISITOR_METHODS)
 440 #undef DECLARE_VISITOR_METHODS
 441
 442 #if ENABLE(GC_TRACING)
 443     void setHostInfo(void* object, const String& name)
 444     {
 445         m_hostObject = object;
 446         m_hostName = name;
 447     }
 448 #endif
 449
 450 protected:
 451     virtual void registerWeakCell(void**, WeakPointerCallback) = 0;
 452 #if ENABLE(GC_TRACING)
 453     void* m_hostObject;
 454     String m_hostName;
 455 #endif
 456
 457 private:
 458     template<typename T>
 459     static void handleWeakCell(Visitor* self, void* obj)
 460     {
 461         T** cell = reinterpret_cast<T**>(obj);
 462         if (*cell && !self->isAlive(*cell))
 463             *cell = 0;
 464     }
 465 };
 466
 467 template<typename T, typename HashFunctions, typename Traits>
 468 struct OffHeapCollectionTraceTrait<WTF::HashSet<T, HashFunctions, Traits, WTF::DefaultAllocator> > {
 469     typedef WTF::HashSet<T, HashFunctions, Traits, WTF::DefaultAllocator> HashSet;
 470
 471     static void trace(Visitor* visitor, const HashSet& set)
 472     {
 473         if (set.isEmpty())
 474             return;
 475         if (WTF::ShouldBeTraced<Traits>::value) {
 476             HashSet& iterSet = const_cast<HashSet&>(set);
 477             for (typename HashSet::iterator it = iterSet.begin(), end = iterSet.end(); it != end; ++it)
 478                 CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, WeakPointersActWeak, T, Traits>::trace(visitor, *it);
 479         }
 480         COMPILE_ASSERT(!Traits::isWeak, WeakOffHeapCollectionsConsideredDangerous0);
 481     }
 482 };
 483
 484 template<typename T, size_t inlineCapacity, typename HashFunctions>
 485 struct OffHeapCollectionTraceTrait<ListHashSet<T, inlineCapacity, HashFunctions> > {
 486     typedef WTF::ListHashSet<T, inlineCapacity, HashFunctions> ListHashSet;
 487
 488     static void trace(Visitor* visitor, const ListHashSet& set)
 489     {
 490         if (set.isEmpty())
 491             return;
 492         ListHashSet& iterSet = const_cast<ListHashSet&>(set);
 493         for (typename ListHashSet::iterator it = iterSet.begin(), end = iterSet.end(); it != end; ++it)
 494             visitor->trace(*it);
 495     }
 496 };
 497
 498 template<typename T, typename HashFunctions>
 499 struct OffHeapCollectionTraceTrait<WTF::LinkedHashSet<T, HashFunctions> > {
 500     typedef WTF::LinkedHashSet<T, HashFunctions> LinkedHashSet;
 501
 502     static void trace(Visitor* visitor, const LinkedHashSet& set)
 503     {
 504         if (set.isEmpty())
 505             return;
 506         LinkedHashSet& iterSet = const_cast<LinkedHashSet&>(set);
 507         for (typename LinkedHashSet::iterator it = iterSet.begin(), end = iterSet.end(); it != end; ++it)
 508             visitor->trace(*it);
 509     }
 510 };
 511
 512 template<typename Key, typename Value, typename HashFunctions, typename KeyTraits, typename ValueTraits>
 513 struct OffHeapCollectionTraceTrait<WTF::HashMap<Key, Value, HashFunctions, KeyTraits, ValueTraits, WTF::DefaultAllocator> > {
 514     typedef WTF::HashMap<Key, Value, HashFunctions, KeyTraits, ValueTraits, WTF::DefaultAllocator> HashMap;
 515
 516     static void trace(Visitor* visitor, const HashMap& map)
 517     {
 518         if (map.isEmpty())
 519             return;
 520         if (WTF::ShouldBeTraced<KeyTraits>::value || WTF::ShouldBeTraced<ValueTraits>::value) {
 521             HashMap& iterMap = const_cast<HashMap&>(map);
 522             for (typename HashMap::iterator it = iterMap.begin(), end = iterMap.end(); it != end; ++it) {
 523                 CollectionBackingTraceTrait<WTF::ShouldBeTraced<KeyTraits>::value, KeyTraits::isWeak, WeakPointersActWeak, Key, KeyTraits>::trace(visitor, it->key);
 524                 CollectionBackingTraceTrait<WTF::ShouldBeTraced<ValueTraits>::value, ValueTraits::isWeak, WeakPointersActWeak, Value, ValueTraits>::trace(visitor, it->value);
 525             }
 526         }
 527         COMPILE_ASSERT(!KeyTraits::isWeak, WeakOffHeapCollectionsConsideredDangerous1);
 528         COMPILE_ASSERT(!ValueTraits::isWeak, WeakOffHeapCollectionsConsideredDangerous2);
 529     }
 530 };
 531
 532 // We trace vectors by using the trace trait on each element, which means you
 533 // can have vectors of general objects (not just pointers to objects) that can
 534 // be traced.
 535 template<typename T, size_t N>
 536 struct OffHeapCollectionTraceTrait<WTF::Vector<T, N, WTF::DefaultAllocator> > {
 537     typedef WTF::Vector<T, N, WTF::DefaultAllocator> Vector;
 538
 539     static void trace(Visitor* visitor, const Vector& vector)
 540     {
 541         if (vector.isEmpty())
 542             return;
 543         for (typename Vector::const_iterator it = vector.begin(), end = vector.end(); it != end; ++it)
 544             TraceTrait<T>::trace(visitor, const_cast<T*>(it));
 545     }
 546 };
 547
 548 template<typename T, size_t N>
 549 struct OffHeapCollectionTraceTrait<WTF::Deque<T, N> > {
 550     typedef WTF::Deque<T, N> Deque;
 551
 552     static void trace(Visitor* visitor, const Deque& deque)
 553     {
 554         if (deque.isEmpty())
 555             return;
 556         for (typename Deque::const_iterator it = deque.begin(), end = deque.end(); it != end; ++it)
 557             TraceTrait<T>::trace(visitor, const_cast<T*>(&(*it)));
 558     }
 559 };
 560
 561 template<typename T, typename U, typename V>
 562 struct OffHeapCollectionTraceTrait<WTF::HashCountedSet<T, U, V> > {
 563     typedef WTF::HashCountedSet<T, U, V> Set;
 564
 565     static void trace(Visitor* visitor, const Set& set)
 566     {
 567         if (set.isEmpty())
 568             return;
 569         for (typename Set::const_iterator it = set.begin(), end = set.end(); it != end; ++it)
 570             TraceTrait<T>::trace(visitor, const_cast<T*>(&(it->key)));
 571     }
 572 };
 573
 574 template<typename T, typename Traits = WTF::VectorTraits<T> >
 575 class HeapVectorBacking;
 576
 577 template<typename Table>
 578 class HeapHashTableBacking {
 579 public:
 580     static void finalize(void* pointer);
 581 };
 582
 583 template<typename T>
 584 class DefaultTraceTrait<T, false> {
 585 public:
 586     static void mark(Visitor* visitor, const T* t)
 587     {
 588         // Default mark method of the trait just calls the two-argument mark
 589         // method on the visitor. The second argument is the static trace method
 590         // of the trait, which by default calls the instance method
 591         // trace(Visitor*) on the object.
 592         visitor->mark(const_cast<T*>(t), &TraceTrait<T>::trace);
 593     }
 594
 595 #ifndef NDEBUG
 596     static void checkGCInfo(Visitor* visitor, const T* t)
 597     {
 598         visitor->checkGCInfo(const_cast<T*>(t), GCInfoTrait<T>::get());
 599     }
 600 #endif
 601 };
 602
 603 template<typename T>
 604 class DefaultTraceTrait<T, true> {
 605 public:
 606     static void mark(Visitor* visitor, const T* self)
 607     {
 608         self->adjustAndMark(visitor);
 609     }
 610
 611 #ifndef NDEBUG
 612     static void checkGCInfo(Visitor*, const T*) { }
 613 #endif
 614 };
 615
 616 template<typename T, bool = NeedsAdjustAndMark<T>::value> class DefaultObjectAliveTrait;
 617
 618 template<typename T>
 619 class DefaultObjectAliveTrait<T, false> {
 620 public:
 621     static bool isAlive(Visitor* visitor, T* obj)
 622     {
 623         return visitor->isMarked(obj);
 624     }
 625 };
 626
 627 template<typename T>
 628 class DefaultObjectAliveTrait<T, true> {
 629 public:
 630     static bool isAlive(Visitor* visitor, T* obj)
 631     {
 632         return obj->isAlive(visitor);
 633     }
 634 };
 635
 636 template<typename T> bool ObjectAliveTrait<T>::isAlive(Visitor* visitor, T* obj)
 637 {
 638     return DefaultObjectAliveTrait<T>::isAlive(visitor, obj);
 639 }
 640
 641 // The GarbageCollectedMixin interface and helper macro
 642 // USING_GARBAGE_COLLECTED_MIXIN can be used to automatically define
 643 // TraceTrait/ObjectAliveTrait on non-leftmost deriving classes
 644 // which need to be garbage collected.
 645 //
 646 // Consider the following case:
 647 // class B {};
 648 // class A : public GarbageCollected, public B {};
 649 //
 650 // We can't correctly handle "Member<B> p = &a" as we can't compute addr of
 651 // object header statically. This can be solved by using GarbageCollectedMixin:
 652 // class B : public GarbageCollectedMixin {};
 653 // class A : public GarbageCollected, public B {
 654 //   USING_GARBAGE_COLLECTED_MIXIN(A)
 655 // };
 656 //
 657 // With the helper, as long as we are using Member<B>, TypeTrait<B> will
 658 // dispatch adjustAndMark dynamically to find collect addr of the object header.
 659 // Note that this is only enabled for Member<B>. For Member<A> which we can
 660 // compute the object header addr statically, this dynamic dispatch is not used.
 661
 662 class GarbageCollectedMixin {
 663 public:
 664     virtual void adjustAndMark(Visitor*) const = 0;
 665     virtual bool isAlive(Visitor*) const = 0;
 666 };
 667
 668 #define USING_GARBAGE_COLLECTED_MIXIN(TYPE) \
 669 public: \
 670     virtual void adjustAndMark(WebCore::Visitor* visitor) const OVERRIDE    \
 671     { \
 672         typedef WTF::IsSubclassOfTemplate<TYPE, WebCore::GarbageCollected> IsSubclassOfGarbageCollected; \
 673         COMPILE_ASSERT(IsSubclassOfGarbageCollected::value, OnlyGarbageCollectedObjectsCanHaveGarbageCollectedMixins); \
 674         visitor->mark(this, &WebCore::TraceTrait<TYPE>::trace); \
 675     } \
 676     virtual bool isAlive(WebCore::Visitor* visitor) const OVERRIDE  \
 677     { \
 678         return visitor->isAlive(this); \
 679     }
 680
 681 #if ENABLE(OILPAN)
 682 #define WILL_BE_USING_GARBAGE_COLLECTED_MIXIN(TYPE) USING_GARBAGE_COLLECTED_MIXIN(TYPE)
 683 #else
 684 #define WILL_BE_USING_GARBAGE_COLLECTED_MIXIN(TYPE)
 685 #endif
 686
 687 #if ENABLE(GC_TRACING)
 688 template<typename T>
 689 struct TypenameStringTrait {
 690     static const String& get()
 691     {
 692         DEFINE_STATIC_LOCAL(String, typenameString, (WTF::extractTypeNameFromFunctionName(WTF::extractNameFunction<T>())));
 693         return typenameString;
 694     }
 695 };
 696 #endif
 697
 698 template<typename T>
 699 struct GCInfoAtBase {
 700     static const GCInfo* get()
 701     {
 702         static const GCInfo gcInfo = {
 703             TraceTrait<T>::trace,
 704             FinalizerTrait<T>::finalize,
 705             FinalizerTrait<T>::nonTrivialFinalizer,
 706             VTableTrait<T>::hasVTable,
 707 #if ENABLE(GC_TRACING)
 708             TypenameStringTrait<T>::get()
 709 #endif
 710         };
 711         return &gcInfo;
 712     }
 713 };
 714
 715 template<typename T> class GarbageCollected;
 716 template<typename T, bool = WTF::IsSubclassOfTemplate<T, GarbageCollected>::value> struct GetGarbageCollectedBase;
 717
 718 template<typename T>
 719 struct GetGarbageCollectedBase<T, true> {
 720     typedef typename T::GarbageCollectedBase type;
 721 };
 722
 723 template<typename T>
 724 struct GetGarbageCollectedBase<T, false> {
 725     typedef T type;
 726 };
 727
 728 template<typename T>
 729 struct GCInfoTrait {
 730     static const GCInfo* get()
 731     {
 732         return GCInfoAtBase<typename GetGarbageCollectedBase<T>::type>::get();
 733     }
 734 };
 735
 736 }
 737
 738 #endif