1 // Copyright 2014 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef TOOLS_BLINK_GC_PLUGIN_EDGE_H_ 6 #define TOOLS_BLINK_GC_PLUGIN_EDGE_H_ 7 8 #include <cassert> 9 #include <deque> 10 #include <vector> 11 12 #include "TracingStatus.h" 13 14 class RecordInfo; 15 16 class Edge; 17 class Collection; 18 class CrossThreadPersistent; 19 class Iterator; 20 class Member; 21 class Persistent; 22 class RawPtr; 23 class RefPtr; 24 class UniquePtr; 25 class Value; 26 class WeakMember; 27 28 // Bare-bones visitor. 29 class EdgeVisitor { 30 public: 31 virtual ~EdgeVisitor() {} 32 virtual void VisitValue(Value*) {} 33 virtual void VisitRawPtr(RawPtr*) {} 34 virtual void VisitRefPtr(RefPtr*) {} 35 virtual void VisitUniquePtr(UniquePtr*) {} 36 virtual void VisitMember(Member*) {} 37 virtual void VisitWeakMember(WeakMember*) {} 38 virtual void VisitPersistent(Persistent*) {} 39 virtual void VisitCrossThreadPersistent(CrossThreadPersistent*) {} 40 virtual void VisitCollection(Collection*) {} 41 virtual void VisitIterator(Iterator*) {} 42 }; 43 44 // Recursive edge visitor. The traversed path is accessible in context. 45 class RecursiveEdgeVisitor : public EdgeVisitor { 46 public: 47 // Overrides that recursively walk the edges and record the path. 48 void VisitValue(Value*) override; 49 void VisitRawPtr(RawPtr*) override; 50 void VisitRefPtr(RefPtr*) override; 51 void VisitUniquePtr(UniquePtr*) override; 52 void VisitMember(Member*) override; 53 void VisitWeakMember(WeakMember*) override; 54 void VisitPersistent(Persistent*) override; 55 void VisitCrossThreadPersistent(CrossThreadPersistent*) override; 56 void VisitCollection(Collection*) override; 57 void VisitIterator(Iterator*) override; 58 59 protected: 60 typedef std::deque<Edge*> Context; 61 Context& context() { return context_; } 62 Edge* Parent() { return context_.empty() ? 0 : context_.front(); } 63 void Enter(Edge* e) { return context_.push_front(e); } 64 void Leave() { context_.pop_front(); } 65 66 // Default callback to overwrite in visitor subclass. 67 virtual void AtValue(Value*); 68 virtual void AtRawPtr(RawPtr*); 69 virtual void AtRefPtr(RefPtr*); 70 virtual void AtUniquePtr(UniquePtr*); 71 virtual void AtMember(Member*); 72 virtual void AtWeakMember(WeakMember*); 73 virtual void AtPersistent(Persistent*); 74 virtual void AtCrossThreadPersistent(CrossThreadPersistent*); 75 virtual void AtCollection(Collection*); 76 virtual void AtIterator(Iterator*); 77 78 private: 79 Context context_; 80 }; 81 82 // Base class for all edges. 83 class Edge { 84 public: 85 enum NeedsTracingOption { kRecursive, kNonRecursive }; 86 enum LivenessKind { kWeak, kStrong, kRoot }; 87 88 virtual ~Edge() {} 89 virtual LivenessKind Kind() = 0; 90 virtual void Accept(EdgeVisitor*) = 0; 91 virtual bool NeedsFinalization() = 0; 92 virtual TracingStatus NeedsTracing(NeedsTracingOption) { 93 return TracingStatus::Unknown(); 94 } 95 96 virtual bool IsValue() { return false; } 97 virtual bool IsRawPtr() { return false; } 98 virtual bool IsRefPtr() { return false; } 99 virtual bool IsUniquePtr() { return false; } 100 virtual bool IsMember() { return false; } 101 virtual bool IsWeakMember() { return false; } 102 virtual bool IsCollection() { return false; } 103 }; 104 105 // A value edge is a direct edge to some type, eg, part-object edges. 106 class Value : public Edge { 107 public: 108 explicit Value(RecordInfo* value) : value_(value) {}; 109 bool IsValue() override { return true; } 110 LivenessKind Kind() override { return kStrong; } 111 bool NeedsFinalization() override; 112 TracingStatus NeedsTracing(NeedsTracingOption) override; 113 void Accept(EdgeVisitor* visitor) override { visitor->VisitValue(this); } 114 RecordInfo* value() { return value_; } 115 116 private: 117 RecordInfo* value_; 118 }; 119 120 // Shared base for smart-pointer edges. 121 class PtrEdge : public Edge { 122 public: 123 ~PtrEdge() { delete ptr_; } 124 Edge* ptr() { return ptr_; } 125 protected: 126 PtrEdge(Edge* ptr) : ptr_(ptr) { 127 assert(ptr && "EdgePtr pointer must be non-null"); 128 } 129 private: 130 Edge* ptr_; 131 }; 132 133 class RawPtr : public PtrEdge { 134 public: 135 RawPtr(Edge* ptr, bool is_ref_type) 136 : PtrEdge(ptr) 137 , is_ref_type_(is_ref_type) 138 { 139 } 140 141 bool IsRawPtr() override { return true; } 142 LivenessKind Kind() override { return kWeak; } 143 bool NeedsFinalization() override { return false; } 144 TracingStatus NeedsTracing(NeedsTracingOption) override { 145 return TracingStatus::Illegal(); 146 } 147 void Accept(EdgeVisitor* visitor) override { visitor->VisitRawPtr(this); } 148 149 bool HasReferenceType() { return is_ref_type_; } 150 private: 151 bool is_ref_type_; 152 }; 153 154 class RefPtr : public PtrEdge { 155 public: 156 explicit RefPtr(Edge* ptr) : PtrEdge(ptr) { } 157 bool IsRefPtr() override { return true; } 158 LivenessKind Kind() override { return kStrong; } 159 bool NeedsFinalization() override { return true; } 160 TracingStatus NeedsTracing(NeedsTracingOption) override { 161 return TracingStatus::Illegal(); 162 } 163 void Accept(EdgeVisitor* visitor) override { visitor->VisitRefPtr(this); } 164 }; 165 166 class UniquePtr : public PtrEdge { 167 public: 168 explicit UniquePtr(Edge* ptr) : PtrEdge(ptr) { } 169 bool IsUniquePtr() override { return true; } 170 LivenessKind Kind() override { return kStrong; } 171 bool NeedsFinalization() override { return true; } 172 TracingStatus NeedsTracing(NeedsTracingOption) override { 173 return TracingStatus::Illegal(); 174 } 175 void Accept(EdgeVisitor* visitor) override { visitor->VisitUniquePtr(this); } 176 }; 177 178 class Member : public PtrEdge { 179 public: 180 explicit Member(Edge* ptr) : PtrEdge(ptr) { } 181 bool IsMember() override { return true; } 182 LivenessKind Kind() override { return kStrong; } 183 bool NeedsFinalization() override { return false; } 184 TracingStatus NeedsTracing(NeedsTracingOption) override { 185 return TracingStatus::Needed(); 186 } 187 void Accept(EdgeVisitor* visitor) override { visitor->VisitMember(this); } 188 }; 189 190 class WeakMember : public PtrEdge { 191 public: 192 explicit WeakMember(Edge* ptr) : PtrEdge(ptr) { } 193 bool IsWeakMember() override { return true; } 194 LivenessKind Kind() override { return kWeak; } 195 bool NeedsFinalization() override { return false; } 196 TracingStatus NeedsTracing(NeedsTracingOption) override { 197 return TracingStatus::Needed(); 198 } 199 void Accept(EdgeVisitor* visitor) override { visitor->VisitWeakMember(this); } 200 }; 201 202 class Persistent : public PtrEdge { 203 public: 204 explicit Persistent(Edge* ptr) : PtrEdge(ptr) { } 205 LivenessKind Kind() override { return kRoot; } 206 bool NeedsFinalization() override { return true; } 207 TracingStatus NeedsTracing(NeedsTracingOption) override { 208 return TracingStatus::Unneeded(); 209 } 210 void Accept(EdgeVisitor* visitor) override { visitor->VisitPersistent(this); } 211 }; 212 213 class CrossThreadPersistent : public PtrEdge { 214 public: 215 explicit CrossThreadPersistent(Edge* ptr) : PtrEdge(ptr) { } 216 LivenessKind Kind() override { return kRoot; } 217 bool NeedsFinalization() override { return true; } 218 TracingStatus NeedsTracing(NeedsTracingOption) override { 219 return TracingStatus::Illegal(); 220 } 221 void Accept(EdgeVisitor* visitor) override { 222 visitor->VisitCrossThreadPersistent(this); 223 } 224 }; 225 226 class Collection : public Edge { 227 public: 228 typedef std::vector<Edge*> Members; 229 Collection(RecordInfo* info, bool on_heap, bool is_root) 230 : info_(info), 231 on_heap_(on_heap), 232 is_root_(is_root) {} 233 ~Collection() { 234 for (Members::iterator it = members_.begin(); it != members_.end(); ++it) { 235 assert(*it && "Collection-edge members must be non-null"); 236 delete *it; 237 } 238 } 239 bool IsCollection() override { return true; } 240 LivenessKind Kind() override { return is_root_ ? kRoot : kStrong; } 241 bool on_heap() { return on_heap_; } 242 bool is_root() { return is_root_; } 243 Members& members() { return members_; } 244 void Accept(EdgeVisitor* visitor) override { visitor->VisitCollection(this); } 245 void AcceptMembers(EdgeVisitor* visitor) { 246 for (Members::iterator it = members_.begin(); it != members_.end(); ++it) 247 (*it)->Accept(visitor); 248 } 249 bool NeedsFinalization() override; 250 TracingStatus NeedsTracing(NeedsTracingOption) override { 251 if (is_root_) 252 return TracingStatus::Unneeded(); 253 if (on_heap_) 254 return TracingStatus::Needed(); 255 // For off-heap collections, determine tracing status of members. 256 TracingStatus status = TracingStatus::Unneeded(); 257 for (Members::iterator it = members_.begin(); it != members_.end(); ++it) { 258 // Do a non-recursive test here since members could equal the holder. 259 status = status.LUB((*it)->NeedsTracing(kNonRecursive)); 260 } 261 return status; 262 } 263 264 private: 265 RecordInfo* info_; 266 Members members_; 267 bool on_heap_; 268 bool is_root_; 269 }; 270 271 // An iterator edge is a direct edge to some iterator type. 272 class Iterator : public Edge { 273 public: 274 Iterator(RecordInfo* info, bool on_heap, bool is_unsafe) 275 : info_(info), on_heap_(on_heap), is_unsafe_(is_unsafe) {} 276 ~Iterator() {} 277 278 void Accept(EdgeVisitor* visitor) override { visitor->VisitIterator(this); } 279 LivenessKind Kind() override { return kStrong; } 280 bool NeedsFinalization() override { return false; } 281 TracingStatus NeedsTracing(NeedsTracingOption) override { 282 if (on_heap_) 283 return TracingStatus::Needed(); 284 return TracingStatus::Unneeded(); 285 } 286 287 RecordInfo* info() const { return info_; } 288 289 bool IsUnsafe() const { return is_unsafe_; } 290 291 private: 292 RecordInfo* info_; 293 bool on_heap_; 294 bool is_unsafe_; 295 }; 296 297 #endif // TOOLS_BLINK_GC_PLUGIN_EDGE_H_ 298