1f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek//===--- ParentMap.cpp - Mappings from Stmts to their Parents ---*- C++ -*-===// 2f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// 3f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// The LLVM Compiler Infrastructure 4f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// 5f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// This file is distributed under the University of Illinois Open Source 6f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// License. See LICENSE.TXT for details. 7f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// 8f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek//===----------------------------------------------------------------------===// 9f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// 10f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// This file defines the ParentMap class. 11f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek// 12f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek//===----------------------------------------------------------------------===// 13f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 14f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek#include "clang/AST/ParentMap.h" 15acc5f3e42334525bf28c86471551f83dfce222d5Daniel Dunbar#include "clang/AST/Decl.h" 16f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek#include "clang/AST/Expr.h" 17fb6f75feaa0fa6621282df1075677a26fdfde1b7Jordan Rose#include "clang/AST/ExprCXX.h" 18f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek#include "llvm/ADT/DenseMap.h" 19f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 20f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenekusing namespace clang; 21f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 22f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenektypedef llvm::DenseMap<Stmt*, Stmt*> MapTy; 23f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 241e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Roseenum OpaqueValueMode { 251e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose OV_Transparent, 261e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose OV_Opaque 271e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose}; 281e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 29bb518991ce4298d8662235fc8cb13813f011c18dJordan Rosestatic void BuildParentMap(MapTy& M, Stmt* S, 301e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose OpaqueValueMode OVMode = OV_Transparent) { 311e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 321e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose switch (S->getStmtClass()) { 331e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose case Stmt::PseudoObjectExprClass: { 341e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose assert(OVMode == OV_Transparent && "Should not appear alongside OVEs"); 351e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose PseudoObjectExpr *POE = cast<PseudoObjectExpr>(S); 361e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 37b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // If we are rebuilding the map, clear out any existing state. 38b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose if (M[POE->getSyntacticForm()]) 39b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose for (Stmt::child_range I = S->children(); I; ++I) 406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines M[*I] = nullptr; 41b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose 42bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose M[POE->getSyntacticForm()] = S; 43bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, POE->getSyntacticForm(), OV_Transparent); 441e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 451e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose for (PseudoObjectExpr::semantics_iterator I = POE->semantics_begin(), 461e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose E = POE->semantics_end(); 471e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose I != E; ++I) { 481e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[*I] = S; 49bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, *I, OV_Opaque); 501e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose } 511e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose break; 521e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose } 531e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose case Stmt::BinaryConditionalOperatorClass: { 541e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose assert(OVMode == OV_Transparent && "Should not appear alongside OVEs"); 551e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose BinaryConditionalOperator *BCO = cast<BinaryConditionalOperator>(S); 561e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 571e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[BCO->getCommon()] = S; 58bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, BCO->getCommon(), OV_Transparent); 591e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 601e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[BCO->getCond()] = S; 61bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, BCO->getCond(), OV_Opaque); 621e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 631e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[BCO->getTrueExpr()] = S; 64bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, BCO->getTrueExpr(), OV_Opaque); 651e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 661e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[BCO->getFalseExpr()] = S; 67bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, BCO->getFalseExpr(), OV_Transparent); 681e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 691e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose break; 701e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose } 71b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose case Stmt::OpaqueValueExprClass: { 72b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // FIXME: This isn't correct; it assumes that multiple OpaqueValueExprs 73b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // share a single source expression, but in the AST a single 74b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // OpaqueValueExpr is shared among multiple parent expressions. 75b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // The right thing to do is to give the OpaqueValueExpr its syntactic 76b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // parent, then not reassign that when traversing the semantic expressions. 77b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose OpaqueValueExpr *OVE = cast<OpaqueValueExpr>(S); 78fa047c580506041d1120023b10c6a3528c8016c6Serge Pavlov if (OVMode == OV_Transparent || !M[OVE->getSourceExpr()]) { 791e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[OVE->getSourceExpr()] = S; 80bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, OVE->getSourceExpr(), OV_Transparent); 811e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose } 821e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose break; 83b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose } 841e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose default: 851e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose for (Stmt::child_range I = S->children(); I; ++I) { 861e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose if (*I) { 871e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[*I] = S; 88bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, *I, OVMode); 892b1b025fa6e848ec36c0554924d7d63342aa80e4Jordan Rose } 90f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek } 911e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose break; 922b1b025fa6e848ec36c0554924d7d63342aa80e4Jordan Rose } 93f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek} 94f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen HinesParentMap::ParentMap(Stmt *S) : Impl(nullptr) { 96f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek if (S) { 97f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek MapTy *M = new MapTy(); 98bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(*M, S); 991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump Impl = M; 100f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek } 101f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek} 102f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 103f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed KremenekParentMap::~ParentMap() { 104f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek delete (MapTy*) Impl; 105f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek} 106f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 107d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenekvoid ParentMap::addStmt(Stmt* S) { 108d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenek if (S) { 109bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(*(MapTy*) Impl, S); 110d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenek } 111d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenek} 112d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenek 11349a246f4fad959888bb0164c624c3c2b03078e91Jordan Rosevoid ParentMap::setParent(const Stmt *S, const Stmt *Parent) { 11449a246f4fad959888bb0164c624c3c2b03078e91Jordan Rose assert(S); 11549a246f4fad959888bb0164c624c3c2b03078e91Jordan Rose assert(Parent); 11649a246f4fad959888bb0164c624c3c2b03078e91Jordan Rose MapTy *M = reinterpret_cast<MapTy *>(Impl); 11749a246f4fad959888bb0164c624c3c2b03078e91Jordan Rose M->insert(std::make_pair(const_cast<Stmt *>(S), const_cast<Stmt *>(Parent))); 11849a246f4fad959888bb0164c624c3c2b03078e91Jordan Rose} 11949a246f4fad959888bb0164c624c3c2b03078e91Jordan Rose 120f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed KremenekStmt* ParentMap::getParent(Stmt* S) const { 121f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek MapTy* M = (MapTy*) Impl; 122f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek MapTy::iterator I = M->find(S); 1236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return I == M->end() ? nullptr : I->second; 124f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek} 125b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek 126b1b9f680f5fc65230de877baccae50820a969a94Ted KremenekStmt *ParentMap::getParentIgnoreParens(Stmt *S) const { 127b1b9f680f5fc65230de877baccae50820a969a94Ted Kremenek do { S = getParent(S); } while (S && isa<ParenExpr>(S)); 128b1b9f680f5fc65230de877baccae50820a969a94Ted Kremenek return S; 129b1b9f680f5fc65230de877baccae50820a969a94Ted Kremenek} 130b1b9f680f5fc65230de877baccae50820a969a94Ted Kremenek 131f4e532b5a1683a9f6c842f361c7415bf3474315fTed KremenekStmt *ParentMap::getParentIgnoreParenCasts(Stmt *S) const { 132f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek do { 133f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek S = getParent(S); 134f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek } 135f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek while (S && (isa<ParenExpr>(S) || isa<CastExpr>(S))); 136f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek 137f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek return S; 138f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek} 139f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek 14018fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios KyrtzidisStmt *ParentMap::getParentIgnoreParenImpCasts(Stmt *S) const { 14118fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis do { 14218fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis S = getParent(S); 14318fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis } while (S && isa<Expr>(S) && cast<Expr>(S)->IgnoreParenImpCasts() != S); 14418fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis 14518fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis return S; 14618fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis} 14718fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis 148f85e193739c953358c865005855253af4f68a497John McCallStmt *ParentMap::getOuterParenParent(Stmt *S) const { 1496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Stmt *Paren = nullptr; 150f85e193739c953358c865005855253af4f68a497John McCall while (isa<ParenExpr>(S)) { 151f85e193739c953358c865005855253af4f68a497John McCall Paren = S; 152f85e193739c953358c865005855253af4f68a497John McCall S = getParent(S); 153f85e193739c953358c865005855253af4f68a497John McCall }; 154f85e193739c953358c865005855253af4f68a497John McCall return Paren; 155f85e193739c953358c865005855253af4f68a497John McCall} 156f85e193739c953358c865005855253af4f68a497John McCall 157b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenekbool ParentMap::isConsumedExpr(Expr* E) const { 158b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek Stmt *P = getParent(E); 159b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek Stmt *DirectChild = E; 1601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 161fb6f75feaa0fa6621282df1075677a26fdfde1b7Jordan Rose // Ignore parents that don't guarantee consumption. 162fb6f75feaa0fa6621282df1075677a26fdfde1b7Jordan Rose while (P && (isa<ParenExpr>(P) || isa<CastExpr>(P) || 163fb6f75feaa0fa6621282df1075677a26fdfde1b7Jordan Rose isa<ExprWithCleanups>(P))) { 164b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek DirectChild = P; 165b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek P = getParent(P); 166b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek } 1671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 168b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek if (!P) 169b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return false; 1701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 171b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek switch (P->getStmtClass()) { 172b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek default: 173b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return isa<Expr>(P); 174b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::DeclStmtClass: 175b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return true; 176b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::BinaryOperatorClass: { 177b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek BinaryOperator *BE = cast<BinaryOperator>(P); 17824ae89a5a25f8971c7436bb3b7663e66ed99b987Ted Kremenek // If it is a comma, only the right side is consumed. 179e42ac98bc2d50506216b6ef258594bdaa59c47c1Ted Kremenek // If it isn't a comma, both sides are consumed. 1802de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall return BE->getOpcode()!=BO_Comma ||DirectChild==BE->getRHS(); 181b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek } 182b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::ForStmtClass: 183b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<ForStmt>(P)->getCond(); 184b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::WhileStmtClass: 1851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return DirectChild == cast<WhileStmt>(P)->getCond(); 186b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::DoStmtClass: 187b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<DoStmt>(P)->getCond(); 188b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::IfStmtClass: 189b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<IfStmt>(P)->getCond(); 190b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::IndirectGotoStmtClass: 191b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<IndirectGotoStmt>(P)->getTarget(); 192b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::SwitchStmtClass: 193b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<SwitchStmt>(P)->getCond(); 194b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::ReturnStmtClass: 195b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return true; 196b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek } 197b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek} 198b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek 199