| 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 |
} |