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