1 //===- ParentMapContext.cpp - Map of parents using DynTypedNode -*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Similar to ParentMap.cpp, but generalizes to non-Stmt nodes, which can have 10 // multiple parents. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/AST/ParentMapContext.h" 15 #include "clang/AST/RecursiveASTVisitor.h" 16 #include "clang/AST/Decl.h" 17 #include "clang/AST/Expr.h" 18 #include "clang/AST/TemplateBase.h" 19 20 using namespace clang; 21 22 ParentMapContext::ParentMapContext(ASTContext &Ctx) : ASTCtx(Ctx) {} 23 24 ParentMapContext::~ParentMapContext() = default; 25 26 void ParentMapContext::clear() { Parents.reset(); } 27 28 const Expr *ParentMapContext::traverseIgnored(const Expr *E) const { 29 return traverseIgnored(const_cast<Expr *>(E)); 30 } 31 32 Expr *ParentMapContext::traverseIgnored(Expr *E) const { 33 if (!E) 34 return nullptr; 35 36 switch (Traversal) { 37 case TK_AsIs: 38 return E; 39 case TK_IgnoreUnlessSpelledInSource: 40 return E->IgnoreUnlessSpelledInSource(); 41 } 42 llvm_unreachable("Invalid Traversal type!"); 43 } 44 45 DynTypedNode ParentMapContext::traverseIgnored(const DynTypedNode &N) const { 46 if (const auto *E = N.get<Expr>()) { 47 return DynTypedNode::create(*traverseIgnored(E)); 48 } 49 return N; 50 } 51 52 template <typename T, typename... U> 53 std::tuple<bool, DynTypedNodeList, const T *, const U *...> 54 matchParents(const DynTypedNodeList &NodeList, 55 ParentMapContext::ParentMap *ParentMap); 56 57 template <typename, typename...> struct MatchParents; 58 59 class ParentMapContext::ParentMap { 60 61 template <typename, typename...> friend struct ::MatchParents; 62 63 /// Contains parents of a node. 64 class ParentVector { 65 public: 66 ParentVector() = default; 67 explicit ParentVector(size_t N, const DynTypedNode &Value) { 68 Items.reserve(N); 69 for (; N > 0; --N) 70 push_back(Value); 71 } 72 bool contains(const DynTypedNode &Value) { 73 return Seen.contains(Value); 74 } 75 void push_back(const DynTypedNode &Value) { 76 if (!Value.getMemoizationData() || Seen.insert(Value).second) 77 Items.push_back(Value); 78 } 79 llvm::ArrayRef<DynTypedNode> view() const { return Items; } 80 private: 81 llvm::SmallVector<DynTypedNode, 2> Items; 82 llvm::SmallDenseSet<DynTypedNode, 2> Seen; 83 }; 84 85 /// Maps from a node to its parents. This is used for nodes that have 86 /// pointer identity only, which are more common and we can save space by 87 /// only storing a unique pointer to them. 88 using ParentMapPointers = 89 llvm::DenseMap<const void *, 90 llvm::PointerUnion<const Decl *, const Stmt *, 91 DynTypedNode *, ParentVector *>>; 92 93 /// Parent map for nodes without pointer identity. We store a full 94 /// DynTypedNode for all keys. 95 using ParentMapOtherNodes = 96 llvm::DenseMap<DynTypedNode, 97 llvm::PointerUnion<const Decl *, const Stmt *, 98 DynTypedNode *, ParentVector *>>; 99 100 ParentMapPointers PointerParents; 101 ParentMapOtherNodes OtherParents; 102 class ASTVisitor; 103 104 static DynTypedNode 105 getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) { 106 if (const auto *D = U.dyn_cast<const Decl *>()) 107 return DynTypedNode::create(*D); 108 if (const auto *S = U.dyn_cast<const Stmt *>()) 109 return DynTypedNode::create(*S); 110 return *U.get<DynTypedNode *>(); 111 } 112 113 template <typename NodeTy, typename MapTy> 114 static DynTypedNodeList getDynNodeFromMap(const NodeTy &Node, 115 const MapTy &Map) { 116 auto I = Map.find(Node); 117 if (I == Map.end()) { 118 return llvm::ArrayRef<DynTypedNode>(); 119 } 120 if (const auto *V = I->second.template dyn_cast<ParentVector *>()) { 121 return V->view(); 122 } 123 return getSingleDynTypedNodeFromParentMap(I->second); 124 } 125 126 public: 127 ParentMap(ASTContext &Ctx); 128 ~ParentMap() { 129 for (const auto &Entry : PointerParents) { 130 if (Entry.second.is<DynTypedNode *>()) { 131 delete Entry.second.get<DynTypedNode *>(); 132 } else if (Entry.second.is<ParentVector *>()) { 133 delete Entry.second.get<ParentVector *>(); 134 } 135 } 136 for (const auto &Entry : OtherParents) { 137 if (Entry.second.is<DynTypedNode *>()) { 138 delete Entry.second.get<DynTypedNode *>(); 139 } else if (Entry.second.is<ParentVector *>()) { 140 delete Entry.second.get<ParentVector *>(); 141 } 142 } 143 } 144 145 DynTypedNodeList getParents(TraversalKind TK, const DynTypedNode &Node) { 146 if (Node.getNodeKind().hasPointerIdentity()) { 147 auto ParentList = 148 getDynNodeFromMap(Node.getMemoizationData(), PointerParents); 149 if (ParentList.size() > 0 && TK == TK_IgnoreUnlessSpelledInSource) { 150 151 const auto *ChildExpr = Node.get<Expr>(); 152 153 { 154 // Don't match explicit node types because different stdlib 155 // implementations implement this in different ways and have 156 // different intermediate nodes. 157 // Look up 4 levels for a cxxRewrittenBinaryOperator as that is 158 // enough for the major stdlib implementations. 159 auto RewrittenBinOpParentsList = ParentList; 160 int I = 0; 161 while (ChildExpr && RewrittenBinOpParentsList.size() == 1 && 162 I++ < 4) { 163 const auto *S = RewrittenBinOpParentsList[0].get<Stmt>(); 164 if (!S) 165 break; 166 167 const auto *RWBO = dyn_cast<CXXRewrittenBinaryOperator>(S); 168 if (!RWBO) { 169 RewrittenBinOpParentsList = getDynNodeFromMap(S, PointerParents); 170 continue; 171 } 172 if (RWBO->getLHS()->IgnoreUnlessSpelledInSource() != ChildExpr && 173 RWBO->getRHS()->IgnoreUnlessSpelledInSource() != ChildExpr) 174 break; 175 return DynTypedNode::create(*RWBO); 176 } 177 } 178 179 const auto *ParentExpr = ParentList[0].get<Expr>(); 180 if (ParentExpr && ChildExpr) 181 return AscendIgnoreUnlessSpelledInSource(ParentExpr, ChildExpr); 182 183 { 184 auto AncestorNodes = 185 matchParents<DeclStmt, CXXForRangeStmt>(ParentList, this); 186 if (std::get<bool>(AncestorNodes) && 187 std::get<const CXXForRangeStmt *>(AncestorNodes) 188 ->getLoopVarStmt() == 189 std::get<const DeclStmt *>(AncestorNodes)) 190 return std::get<DynTypedNodeList>(AncestorNodes); 191 } 192 { 193 auto AncestorNodes = matchParents<VarDecl, DeclStmt, CXXForRangeStmt>( 194 ParentList, this); 195 if (std::get<bool>(AncestorNodes) && 196 std::get<const CXXForRangeStmt *>(AncestorNodes) 197 ->getRangeStmt() == 198 std::get<const DeclStmt *>(AncestorNodes)) 199 return std::get<DynTypedNodeList>(AncestorNodes); 200 } 201 { 202 auto AncestorNodes = 203 matchParents<CXXMethodDecl, CXXRecordDecl, LambdaExpr>(ParentList, 204 this); 205 if (std::get<bool>(AncestorNodes)) 206 return std::get<DynTypedNodeList>(AncestorNodes); 207 } 208 { 209 auto AncestorNodes = 210 matchParents<FunctionTemplateDecl, CXXRecordDecl, LambdaExpr>( 211 ParentList, this); 212 if (std::get<bool>(AncestorNodes)) 213 return std::get<DynTypedNodeList>(AncestorNodes); 214 } 215 } 216 return ParentList; 217 } 218 return getDynNodeFromMap(Node, OtherParents); 219 } 220 221 DynTypedNodeList AscendIgnoreUnlessSpelledInSource(const Expr *E, 222 const Expr *Child) { 223 224 auto ShouldSkip = [](const Expr *E, const Expr *Child) { 225 if (isa<ImplicitCastExpr>(E)) 226 return true; 227 228 if (isa<FullExpr>(E)) 229 return true; 230 231 if (isa<MaterializeTemporaryExpr>(E)) 232 return true; 233 234 if (isa<CXXBindTemporaryExpr>(E)) 235 return true; 236 237 if (isa<ParenExpr>(E)) 238 return true; 239 240 if (isa<ExprWithCleanups>(E)) 241 return true; 242 243 auto SR = Child->getSourceRange(); 244 245 if (const auto *C = dyn_cast<CXXFunctionalCastExpr>(E)) { 246 if (C->getSourceRange() == SR) 247 return true; 248 } 249 250 if (const auto *C = dyn_cast<CXXConstructExpr>(E)) { 251 if (C->getSourceRange() == SR || C->isElidable()) 252 return true; 253 } 254 255 if (const auto *C = dyn_cast<CXXMemberCallExpr>(E)) { 256 if (C->getSourceRange() == SR) 257 return true; 258 } 259 260 if (const auto *C = dyn_cast<MemberExpr>(E)) { 261 if (C->getSourceRange() == SR) 262 return true; 263 } 264 return false; 265 }; 266 267 while (ShouldSkip(E, Child)) { 268 auto It = PointerParents.find(E); 269 if (It == PointerParents.end()) 270 break; 271 const auto *S = It->second.dyn_cast<const Stmt *>(); 272 if (!S) { 273 if (auto *Vec = It->second.dyn_cast<ParentVector *>()) 274 return Vec->view(); 275 return getSingleDynTypedNodeFromParentMap(It->second); 276 } 277 const auto *P = dyn_cast<Expr>(S); 278 if (!P) 279 return DynTypedNode::create(*S); 280 Child = E; 281 E = P; 282 } 283 return DynTypedNode::create(*E); 284 } 285 }; 286 287 template <typename T, typename... U> struct MatchParents { 288 static std::tuple<bool, DynTypedNodeList, const T *, const U *...> 289 match(const DynTypedNodeList &NodeList, 290 ParentMapContext::ParentMap *ParentMap) { 291 if (const auto *TypedNode = NodeList[0].get<T>()) { 292 auto NextParentList = 293 ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents); 294 if (NextParentList.size() == 1) { 295 auto TailTuple = MatchParents<U...>::match(NextParentList, ParentMap); 296 if (std::get<bool>(TailTuple)) { 297 return std::apply( 298 [TypedNode](bool, DynTypedNodeList NodeList, auto... TupleTail) { 299 return std::make_tuple(true, NodeList, TypedNode, TupleTail...); 300 }, 301 TailTuple); 302 } 303 } 304 } 305 return std::tuple_cat(std::make_tuple(false, NodeList), 306 std::tuple<const T *, const U *...>()); 307 } 308 }; 309 310 template <typename T> struct MatchParents<T> { 311 static std::tuple<bool, DynTypedNodeList, const T *> 312 match(const DynTypedNodeList &NodeList, 313 ParentMapContext::ParentMap *ParentMap) { 314 if (const auto *TypedNode = NodeList[0].get<T>()) { 315 auto NextParentList = 316 ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents); 317 if (NextParentList.size() == 1) 318 return std::make_tuple(true, NodeList, TypedNode); 319 } 320 return std::make_tuple(false, NodeList, nullptr); 321 } 322 }; 323 324 template <typename T, typename... U> 325 std::tuple<bool, DynTypedNodeList, const T *, const U *...> 326 matchParents(const DynTypedNodeList &NodeList, 327 ParentMapContext::ParentMap *ParentMap) { 328 return MatchParents<T, U...>::match(NodeList, ParentMap); 329 } 330 331 /// Template specializations to abstract away from pointers and TypeLocs. 332 /// @{ 333 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) { 334 return DynTypedNode::create(*Node); 335 } 336 template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) { 337 return DynTypedNode::create(Node); 338 } 339 template <> 340 DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) { 341 return DynTypedNode::create(Node); 342 } 343 template <> DynTypedNode createDynTypedNode(const ObjCProtocolLoc &Node) { 344 return DynTypedNode::create(Node); 345 } 346 /// @} 347 348 /// A \c RecursiveASTVisitor that builds a map from nodes to their 349 /// parents as defined by the \c RecursiveASTVisitor. 350 /// 351 /// Note that the relationship described here is purely in terms of AST 352 /// traversal - there are other relationships (for example declaration context) 353 /// in the AST that are better modeled by special matchers. 354 class ParentMapContext::ParentMap::ASTVisitor 355 : public RecursiveASTVisitor<ASTVisitor> { 356 public: 357 ASTVisitor(ParentMap &Map) : Map(Map) {} 358 359 private: 360 friend class RecursiveASTVisitor<ASTVisitor>; 361 362 using VisitorBase = RecursiveASTVisitor<ASTVisitor>; 363 364 bool shouldVisitTemplateInstantiations() const { return true; } 365 366 bool shouldVisitImplicitCode() const { return true; } 367 368 /// Record the parent of the node we're visiting. 369 /// MapNode is the child, the parent is on top of ParentStack. 370 /// Parents is the parent storage (either PointerParents or OtherParents). 371 template <typename MapNodeTy, typename MapTy> 372 void addParent(MapNodeTy MapNode, MapTy *Parents) { 373 if (ParentStack.empty()) 374 return; 375 376 // FIXME: Currently we add the same parent multiple times, but only 377 // when no memoization data is available for the type. 378 // For example when we visit all subexpressions of template 379 // instantiations; this is suboptimal, but benign: the only way to 380 // visit those is with hasAncestor / hasParent, and those do not create 381 // new matches. 382 // The plan is to enable DynTypedNode to be storable in a map or hash 383 // map. The main problem there is to implement hash functions / 384 // comparison operators for all types that DynTypedNode supports that 385 // do not have pointer identity. 386 auto &NodeOrVector = (*Parents)[MapNode]; 387 if (NodeOrVector.isNull()) { 388 if (const auto *D = ParentStack.back().get<Decl>()) 389 NodeOrVector = D; 390 else if (const auto *S = ParentStack.back().get<Stmt>()) 391 NodeOrVector = S; 392 else 393 NodeOrVector = new DynTypedNode(ParentStack.back()); 394 } else { 395 if (!NodeOrVector.template is<ParentVector *>()) { 396 auto *Vector = new ParentVector( 397 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); 398 delete NodeOrVector.template dyn_cast<DynTypedNode *>(); 399 NodeOrVector = Vector; 400 } 401 402 auto *Vector = NodeOrVector.template get<ParentVector *>(); 403 // Skip duplicates for types that have memoization data. 404 // We must check that the type has memoization data before calling 405 // llvm::is_contained() because DynTypedNode::operator== can't compare all 406 // types. 407 bool Found = ParentStack.back().getMemoizationData() && 408 llvm::is_contained(*Vector, ParentStack.back()); 409 if (!Found) 410 Vector->push_back(ParentStack.back()); 411 } 412 } 413 414 template <typename T> static bool isNull(T Node) { return !Node; } 415 static bool isNull(ObjCProtocolLoc Node) { return false; } 416 417 template <typename T, typename MapNodeTy, typename BaseTraverseFn, 418 typename MapTy> 419 bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, 420 MapTy *Parents) { 421 if (isNull(Node)) 422 return true; 423 addParent(MapNode, Parents); 424 ParentStack.push_back(createDynTypedNode(Node)); 425 bool Result = BaseTraverse(); 426 ParentStack.pop_back(); 427 return Result; 428 } 429 430 bool TraverseDecl(Decl *DeclNode) { 431 return TraverseNode( 432 DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); }, 433 &Map.PointerParents); 434 } 435 bool TraverseTypeLoc(TypeLoc TypeLocNode) { 436 return TraverseNode( 437 TypeLocNode, DynTypedNode::create(TypeLocNode), 438 [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); }, 439 &Map.OtherParents); 440 } 441 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { 442 return TraverseNode( 443 NNSLocNode, DynTypedNode::create(NNSLocNode), 444 [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }, 445 &Map.OtherParents); 446 } 447 bool TraverseAttr(Attr *AttrNode) { 448 return TraverseNode( 449 AttrNode, AttrNode, [&] { return VisitorBase::TraverseAttr(AttrNode); }, 450 &Map.PointerParents); 451 } 452 bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLocNode) { 453 return TraverseNode( 454 ProtocolLocNode, DynTypedNode::create(ProtocolLocNode), 455 [&] { return VisitorBase::TraverseObjCProtocolLoc(ProtocolLocNode); }, 456 &Map.OtherParents); 457 } 458 459 // Using generic TraverseNode for Stmt would prevent data-recursion. 460 bool dataTraverseStmtPre(Stmt *StmtNode) { 461 addParent(StmtNode, &Map.PointerParents); 462 ParentStack.push_back(DynTypedNode::create(*StmtNode)); 463 return true; 464 } 465 bool dataTraverseStmtPost(Stmt *StmtNode) { 466 ParentStack.pop_back(); 467 return true; 468 } 469 470 ParentMap ⤅ 471 llvm::SmallVector<DynTypedNode, 16> ParentStack; 472 }; 473 474 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) { 475 ASTVisitor(*this).TraverseAST(Ctx); 476 } 477 478 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) { 479 if (!Parents) 480 // We build the parent map for the traversal scope (usually whole TU), as 481 // hasAncestor can escape any subtree. 482 Parents = std::make_unique<ParentMap>(ASTCtx); 483 return Parents->getParents(getTraversalKind(), Node); 484 } 485