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