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::makeArrayRef(*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::makeArrayRef(*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 Tuple, std::size_t... Is> 269 auto tuple_pop_front_impl(const Tuple &tuple, std::index_sequence<Is...>) { 270 return std::make_tuple(std::get<1 + Is>(tuple)...); 271 } 272 273 template <typename Tuple> auto tuple_pop_front(const Tuple &tuple) { 274 return tuple_pop_front_impl( 275 tuple, std::make_index_sequence<std::tuple_size<Tuple>::value - 1>()); 276 } 277 278 template <typename T, typename... U> struct MatchParents { 279 static std::tuple<bool, DynTypedNodeList, const T *, const U *...> 280 match(const DynTypedNodeList &NodeList, 281 ParentMapContext::ParentMap *ParentMap) { 282 if (const auto *TypedNode = NodeList[0].get<T>()) { 283 auto NextParentList = 284 ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents); 285 if (NextParentList.size() == 1) { 286 auto TailTuple = MatchParents<U...>::match(NextParentList, ParentMap); 287 if (std::get<bool>(TailTuple)) { 288 return std::tuple_cat( 289 std::make_tuple(true, std::get<DynTypedNodeList>(TailTuple), 290 TypedNode), 291 tuple_pop_front(tuple_pop_front(TailTuple))); 292 } 293 } 294 } 295 return std::tuple_cat(std::make_tuple(false, NodeList), 296 std::tuple<const T *, const U *...>()); 297 } 298 }; 299 300 template <typename T> struct MatchParents<T> { 301 static std::tuple<bool, DynTypedNodeList, const T *> 302 match(const DynTypedNodeList &NodeList, 303 ParentMapContext::ParentMap *ParentMap) { 304 if (const auto *TypedNode = NodeList[0].get<T>()) { 305 auto NextParentList = 306 ParentMap->getDynNodeFromMap(TypedNode, ParentMap->PointerParents); 307 if (NextParentList.size() == 1) 308 return std::make_tuple(true, NodeList, TypedNode); 309 } 310 return std::make_tuple(false, NodeList, nullptr); 311 } 312 }; 313 314 template <typename T, typename... U> 315 std::tuple<bool, DynTypedNodeList, const T *, const U *...> 316 matchParents(const DynTypedNodeList &NodeList, 317 ParentMapContext::ParentMap *ParentMap) { 318 return MatchParents<T, U...>::match(NodeList, ParentMap); 319 } 320 321 /// Template specializations to abstract away from pointers and TypeLocs. 322 /// @{ 323 template <typename T> static DynTypedNode createDynTypedNode(const T &Node) { 324 return DynTypedNode::create(*Node); 325 } 326 template <> DynTypedNode createDynTypedNode(const TypeLoc &Node) { 327 return DynTypedNode::create(Node); 328 } 329 template <> 330 DynTypedNode createDynTypedNode(const NestedNameSpecifierLoc &Node) { 331 return DynTypedNode::create(Node); 332 } 333 /// @} 334 335 /// A \c RecursiveASTVisitor that builds a map from nodes to their 336 /// parents as defined by the \c RecursiveASTVisitor. 337 /// 338 /// Note that the relationship described here is purely in terms of AST 339 /// traversal - there are other relationships (for example declaration context) 340 /// in the AST that are better modeled by special matchers. 341 class ParentMapContext::ParentMap::ASTVisitor 342 : public RecursiveASTVisitor<ASTVisitor> { 343 public: 344 ASTVisitor(ParentMap &Map) : Map(Map) {} 345 346 private: 347 friend class RecursiveASTVisitor<ASTVisitor>; 348 349 using VisitorBase = RecursiveASTVisitor<ASTVisitor>; 350 351 bool shouldVisitTemplateInstantiations() const { return true; } 352 353 bool shouldVisitImplicitCode() const { return true; } 354 355 /// Record the parent of the node we're visiting. 356 /// MapNode is the child, the parent is on top of ParentStack. 357 /// Parents is the parent storage (either PointerParents or OtherParents). 358 template <typename MapNodeTy, typename MapTy> 359 void addParent(MapNodeTy MapNode, MapTy *Parents) { 360 if (ParentStack.empty()) 361 return; 362 363 // FIXME: Currently we add the same parent multiple times, but only 364 // when no memoization data is available for the type. 365 // For example when we visit all subexpressions of template 366 // instantiations; this is suboptimal, but benign: the only way to 367 // visit those is with hasAncestor / hasParent, and those do not create 368 // new matches. 369 // The plan is to enable DynTypedNode to be storable in a map or hash 370 // map. The main problem there is to implement hash functions / 371 // comparison operators for all types that DynTypedNode supports that 372 // do not have pointer identity. 373 auto &NodeOrVector = (*Parents)[MapNode]; 374 if (NodeOrVector.isNull()) { 375 if (const auto *D = ParentStack.back().get<Decl>()) 376 NodeOrVector = D; 377 else if (const auto *S = ParentStack.back().get<Stmt>()) 378 NodeOrVector = S; 379 else 380 NodeOrVector = new DynTypedNode(ParentStack.back()); 381 } else { 382 if (!NodeOrVector.template is<ParentVector *>()) { 383 auto *Vector = new ParentVector( 384 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); 385 delete NodeOrVector.template dyn_cast<DynTypedNode *>(); 386 NodeOrVector = Vector; 387 } 388 389 auto *Vector = NodeOrVector.template get<ParentVector *>(); 390 // Skip duplicates for types that have memoization data. 391 // We must check that the type has memoization data before calling 392 // llvm::is_contained() because DynTypedNode::operator== can't compare all 393 // types. 394 bool Found = ParentStack.back().getMemoizationData() && 395 llvm::is_contained(*Vector, ParentStack.back()); 396 if (!Found) 397 Vector->push_back(ParentStack.back()); 398 } 399 } 400 401 template <typename T, typename MapNodeTy, typename BaseTraverseFn, 402 typename MapTy> 403 bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, 404 MapTy *Parents) { 405 if (!Node) 406 return true; 407 addParent(MapNode, Parents); 408 ParentStack.push_back(createDynTypedNode(Node)); 409 bool Result = BaseTraverse(); 410 ParentStack.pop_back(); 411 return Result; 412 } 413 414 bool TraverseDecl(Decl *DeclNode) { 415 return TraverseNode( 416 DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); }, 417 &Map.PointerParents); 418 } 419 bool TraverseTypeLoc(TypeLoc TypeLocNode) { 420 return TraverseNode( 421 TypeLocNode, DynTypedNode::create(TypeLocNode), 422 [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); }, 423 &Map.OtherParents); 424 } 425 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { 426 return TraverseNode( 427 NNSLocNode, DynTypedNode::create(NNSLocNode), 428 [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }, 429 &Map.OtherParents); 430 } 431 bool TraverseAttr(Attr *AttrNode) { 432 return TraverseNode( 433 AttrNode, AttrNode, [&] { return VisitorBase::TraverseAttr(AttrNode); }, 434 &Map.PointerParents); 435 } 436 437 // Using generic TraverseNode for Stmt would prevent data-recursion. 438 bool dataTraverseStmtPre(Stmt *StmtNode) { 439 addParent(StmtNode, &Map.PointerParents); 440 ParentStack.push_back(DynTypedNode::create(*StmtNode)); 441 return true; 442 } 443 bool dataTraverseStmtPost(Stmt *StmtNode) { 444 ParentStack.pop_back(); 445 return true; 446 } 447 448 ParentMap ⤅ 449 llvm::SmallVector<DynTypedNode, 16> ParentStack; 450 }; 451 452 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) { 453 ASTVisitor(*this).TraverseAST(Ctx); 454 } 455 456 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) { 457 if (!Parents) 458 // We build the parent map for the traversal scope (usually whole TU), as 459 // hasAncestor can escape any subtree. 460 Parents = std::make_unique<ParentMap>(ASTCtx); 461 return Parents->getParents(getTraversalKind(), Node); 462 } 463