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 template <> DynTypedNode createDynTypedNode(const ObjCProtocolLoc &Node) { 334 return DynTypedNode::create(Node); 335 } 336 /// @} 337 338 /// A \c RecursiveASTVisitor that builds a map from nodes to their 339 /// parents as defined by the \c RecursiveASTVisitor. 340 /// 341 /// Note that the relationship described here is purely in terms of AST 342 /// traversal - there are other relationships (for example declaration context) 343 /// in the AST that are better modeled by special matchers. 344 class ParentMapContext::ParentMap::ASTVisitor 345 : public RecursiveASTVisitor<ASTVisitor> { 346 public: 347 ASTVisitor(ParentMap &Map) : Map(Map) {} 348 349 private: 350 friend class RecursiveASTVisitor<ASTVisitor>; 351 352 using VisitorBase = RecursiveASTVisitor<ASTVisitor>; 353 354 bool shouldVisitTemplateInstantiations() const { return true; } 355 356 bool shouldVisitImplicitCode() const { return true; } 357 358 /// Record the parent of the node we're visiting. 359 /// MapNode is the child, the parent is on top of ParentStack. 360 /// Parents is the parent storage (either PointerParents or OtherParents). 361 template <typename MapNodeTy, typename MapTy> 362 void addParent(MapNodeTy MapNode, MapTy *Parents) { 363 if (ParentStack.empty()) 364 return; 365 366 // FIXME: Currently we add the same parent multiple times, but only 367 // when no memoization data is available for the type. 368 // For example when we visit all subexpressions of template 369 // instantiations; this is suboptimal, but benign: the only way to 370 // visit those is with hasAncestor / hasParent, and those do not create 371 // new matches. 372 // The plan is to enable DynTypedNode to be storable in a map or hash 373 // map. The main problem there is to implement hash functions / 374 // comparison operators for all types that DynTypedNode supports that 375 // do not have pointer identity. 376 auto &NodeOrVector = (*Parents)[MapNode]; 377 if (NodeOrVector.isNull()) { 378 if (const auto *D = ParentStack.back().get<Decl>()) 379 NodeOrVector = D; 380 else if (const auto *S = ParentStack.back().get<Stmt>()) 381 NodeOrVector = S; 382 else 383 NodeOrVector = new DynTypedNode(ParentStack.back()); 384 } else { 385 if (!NodeOrVector.template is<ParentVector *>()) { 386 auto *Vector = new ParentVector( 387 1, getSingleDynTypedNodeFromParentMap(NodeOrVector)); 388 delete NodeOrVector.template dyn_cast<DynTypedNode *>(); 389 NodeOrVector = Vector; 390 } 391 392 auto *Vector = NodeOrVector.template get<ParentVector *>(); 393 // Skip duplicates for types that have memoization data. 394 // We must check that the type has memoization data before calling 395 // llvm::is_contained() because DynTypedNode::operator== can't compare all 396 // types. 397 bool Found = ParentStack.back().getMemoizationData() && 398 llvm::is_contained(*Vector, ParentStack.back()); 399 if (!Found) 400 Vector->push_back(ParentStack.back()); 401 } 402 } 403 404 template <typename T> static bool isNull(T Node) { return !Node; } 405 static bool isNull(ObjCProtocolLoc Node) { return false; } 406 407 template <typename T, typename MapNodeTy, typename BaseTraverseFn, 408 typename MapTy> 409 bool TraverseNode(T Node, MapNodeTy MapNode, BaseTraverseFn BaseTraverse, 410 MapTy *Parents) { 411 if (isNull(Node)) 412 return true; 413 addParent(MapNode, Parents); 414 ParentStack.push_back(createDynTypedNode(Node)); 415 bool Result = BaseTraverse(); 416 ParentStack.pop_back(); 417 return Result; 418 } 419 420 bool TraverseDecl(Decl *DeclNode) { 421 return TraverseNode( 422 DeclNode, DeclNode, [&] { return VisitorBase::TraverseDecl(DeclNode); }, 423 &Map.PointerParents); 424 } 425 bool TraverseTypeLoc(TypeLoc TypeLocNode) { 426 return TraverseNode( 427 TypeLocNode, DynTypedNode::create(TypeLocNode), 428 [&] { return VisitorBase::TraverseTypeLoc(TypeLocNode); }, 429 &Map.OtherParents); 430 } 431 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSLocNode) { 432 return TraverseNode( 433 NNSLocNode, DynTypedNode::create(NNSLocNode), 434 [&] { return VisitorBase::TraverseNestedNameSpecifierLoc(NNSLocNode); }, 435 &Map.OtherParents); 436 } 437 bool TraverseAttr(Attr *AttrNode) { 438 return TraverseNode( 439 AttrNode, AttrNode, [&] { return VisitorBase::TraverseAttr(AttrNode); }, 440 &Map.PointerParents); 441 } 442 bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLocNode) { 443 return TraverseNode( 444 ProtocolLocNode, DynTypedNode::create(ProtocolLocNode), 445 [&] { return VisitorBase::TraverseObjCProtocolLoc(ProtocolLocNode); }, 446 &Map.OtherParents); 447 } 448 449 // Using generic TraverseNode for Stmt would prevent data-recursion. 450 bool dataTraverseStmtPre(Stmt *StmtNode) { 451 addParent(StmtNode, &Map.PointerParents); 452 ParentStack.push_back(DynTypedNode::create(*StmtNode)); 453 return true; 454 } 455 bool dataTraverseStmtPost(Stmt *StmtNode) { 456 ParentStack.pop_back(); 457 return true; 458 } 459 460 ParentMap ⤅ 461 llvm::SmallVector<DynTypedNode, 16> ParentStack; 462 }; 463 464 ParentMapContext::ParentMap::ParentMap(ASTContext &Ctx) { 465 ASTVisitor(*this).TraverseAST(Ctx); 466 } 467 468 DynTypedNodeList ParentMapContext::getParents(const DynTypedNode &Node) { 469 if (!Parents) 470 // We build the parent map for the traversal scope (usually whole TU), as 471 // hasAncestor can escape any subtree. 472 Parents = std::make_unique<ParentMap>(ASTCtx); 473 return Parents->getParents(getTraversalKind(), Node); 474 } 475