clang/lib/AST/ParentMapContext.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-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 &Map;
 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 }