ParentMap.cpp revision fa047c580506041d1120023b10c6a3528c8016c6
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" 17f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek#include "llvm/ADT/DenseMap.h" 18f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 19f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenekusing namespace clang; 20f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 21f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenektypedef llvm::DenseMap<Stmt*, Stmt*> MapTy; 22f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 231e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Roseenum OpaqueValueMode { 241e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose OV_Transparent, 251e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose OV_Opaque 261e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose}; 271e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 28bb518991ce4298d8662235fc8cb13813f011c18dJordan Rosestatic void BuildParentMap(MapTy& M, Stmt* S, 291e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose OpaqueValueMode OVMode = OV_Transparent) { 301e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 311e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose switch (S->getStmtClass()) { 321e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose case Stmt::PseudoObjectExprClass: { 331e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose assert(OVMode == OV_Transparent && "Should not appear alongside OVEs"); 341e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose PseudoObjectExpr *POE = cast<PseudoObjectExpr>(S); 351e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 36b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // If we are rebuilding the map, clear out any existing state. 37b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose if (M[POE->getSyntacticForm()]) 38b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose for (Stmt::child_range I = S->children(); I; ++I) 39b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose M[*I] = 0; 40b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose 41bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose M[POE->getSyntacticForm()] = S; 42bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, POE->getSyntacticForm(), OV_Transparent); 431e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 441e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose for (PseudoObjectExpr::semantics_iterator I = POE->semantics_begin(), 451e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose E = POE->semantics_end(); 461e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose I != E; ++I) { 471e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[*I] = S; 48bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, *I, OV_Opaque); 491e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose } 501e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose break; 511e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose } 521e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose case Stmt::BinaryConditionalOperatorClass: { 531e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose assert(OVMode == OV_Transparent && "Should not appear alongside OVEs"); 541e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose BinaryConditionalOperator *BCO = cast<BinaryConditionalOperator>(S); 551e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 561e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[BCO->getCommon()] = S; 57bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, BCO->getCommon(), OV_Transparent); 581e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 591e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[BCO->getCond()] = S; 60bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, BCO->getCond(), OV_Opaque); 611e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 621e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[BCO->getTrueExpr()] = S; 63bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, BCO->getTrueExpr(), OV_Opaque); 641e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 651e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[BCO->getFalseExpr()] = S; 66bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, BCO->getFalseExpr(), OV_Transparent); 671e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose 681e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose break; 691e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose } 70b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose case Stmt::OpaqueValueExprClass: { 71b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // FIXME: This isn't correct; it assumes that multiple OpaqueValueExprs 72b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // share a single source expression, but in the AST a single 73b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // OpaqueValueExpr is shared among multiple parent expressions. 74b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // The right thing to do is to give the OpaqueValueExpr its syntactic 75b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose // parent, then not reassign that when traversing the semantic expressions. 76b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose OpaqueValueExpr *OVE = cast<OpaqueValueExpr>(S); 77fa047c580506041d1120023b10c6a3528c8016c6Serge Pavlov if (OVMode == OV_Transparent || !M[OVE->getSourceExpr()]) { 781e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[OVE->getSourceExpr()] = S; 79bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, OVE->getSourceExpr(), OV_Transparent); 801e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose } 811e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose break; 82b9fdfb50983012b3460e3c27737ec8cdfdb8627dJordan Rose } 831e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose default: 841e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose for (Stmt::child_range I = S->children(); I; ++I) { 851e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose if (*I) { 861e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose M[*I] = S; 87bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(M, *I, OVMode); 882b1b025fa6e848ec36c0554924d7d63342aa80e4Jordan Rose } 89f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek } 901e5101e1e52729564b6fc8d7bf146cef33bc31caJordan Rose break; 912b1b025fa6e848ec36c0554924d7d63342aa80e4Jordan Rose } 92f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek} 93f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 94bb518991ce4298d8662235fc8cb13813f011c18dJordan RoseParentMap::ParentMap(Stmt* S) : Impl(0) { 95f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek if (S) { 96f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek MapTy *M = new MapTy(); 97bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(*M, S); 981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump Impl = M; 99f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek } 100f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek} 101f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 102f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed KremenekParentMap::~ParentMap() { 103f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek delete (MapTy*) Impl; 104f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek} 105f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek 106d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenekvoid ParentMap::addStmt(Stmt* S) { 107d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenek if (S) { 108bb518991ce4298d8662235fc8cb13813f011c18dJordan Rose BuildParentMap(*(MapTy*) Impl, S); 109d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenek } 110d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenek} 111d6543f8bbac18cdb678a67da2a676c30c2941ecaTed Kremenek 112f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed KremenekStmt* ParentMap::getParent(Stmt* S) const { 113f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek MapTy* M = (MapTy*) Impl; 114f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek MapTy::iterator I = M->find(S); 115f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek return I == M->end() ? 0 : I->second; 116f8e32cf062f39fff1a00aff748cb6b5dc0abc2feTed Kremenek} 117b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek 118b1b9f680f5fc65230de877baccae50820a969a94Ted KremenekStmt *ParentMap::getParentIgnoreParens(Stmt *S) const { 119b1b9f680f5fc65230de877baccae50820a969a94Ted Kremenek do { S = getParent(S); } while (S && isa<ParenExpr>(S)); 120b1b9f680f5fc65230de877baccae50820a969a94Ted Kremenek return S; 121b1b9f680f5fc65230de877baccae50820a969a94Ted Kremenek} 122b1b9f680f5fc65230de877baccae50820a969a94Ted Kremenek 123f4e532b5a1683a9f6c842f361c7415bf3474315fTed KremenekStmt *ParentMap::getParentIgnoreParenCasts(Stmt *S) const { 124f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek do { 125f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek S = getParent(S); 126f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek } 127f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek while (S && (isa<ParenExpr>(S) || isa<CastExpr>(S))); 128f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek 129f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek return S; 130f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek} 131f4e532b5a1683a9f6c842f361c7415bf3474315fTed Kremenek 13218fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios KyrtzidisStmt *ParentMap::getParentIgnoreParenImpCasts(Stmt *S) const { 13318fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis do { 13418fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis S = getParent(S); 13518fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis } while (S && isa<Expr>(S) && cast<Expr>(S)->IgnoreParenImpCasts() != S); 13618fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis 13718fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis return S; 13818fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis} 13918fd0c6915b45c4daafe18e3cd324c13306f913fArgyrios Kyrtzidis 140f85e193739c953358c865005855253af4f68a497John McCallStmt *ParentMap::getOuterParenParent(Stmt *S) const { 141f85e193739c953358c865005855253af4f68a497John McCall Stmt *Paren = 0; 142f85e193739c953358c865005855253af4f68a497John McCall while (isa<ParenExpr>(S)) { 143f85e193739c953358c865005855253af4f68a497John McCall Paren = S; 144f85e193739c953358c865005855253af4f68a497John McCall S = getParent(S); 145f85e193739c953358c865005855253af4f68a497John McCall }; 146f85e193739c953358c865005855253af4f68a497John McCall return Paren; 147f85e193739c953358c865005855253af4f68a497John McCall} 148f85e193739c953358c865005855253af4f68a497John McCall 149b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenekbool ParentMap::isConsumedExpr(Expr* E) const { 150b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek Stmt *P = getParent(E); 151b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek Stmt *DirectChild = E; 1521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 153b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek // Ignore parents that are parentheses or casts. 154ade9ecaba935489840fa74aaf5b4c640d6589e33Ted Kremenek while (P && (isa<ParenExpr>(P) || isa<CastExpr>(P))) { 155b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek DirectChild = P; 156b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek P = getParent(P); 157b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek } 1581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 159b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek if (!P) 160b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return false; 1611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 162b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek switch (P->getStmtClass()) { 163b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek default: 164b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return isa<Expr>(P); 165b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::DeclStmtClass: 166b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return true; 167b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::BinaryOperatorClass: { 168b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek BinaryOperator *BE = cast<BinaryOperator>(P); 16924ae89a5a25f8971c7436bb3b7663e66ed99b987Ted Kremenek // If it is a comma, only the right side is consumed. 170e42ac98bc2d50506216b6ef258594bdaa59c47c1Ted Kremenek // If it isn't a comma, both sides are consumed. 1712de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall return BE->getOpcode()!=BO_Comma ||DirectChild==BE->getRHS(); 172b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek } 173b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::ForStmtClass: 174b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<ForStmt>(P)->getCond(); 175b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::WhileStmtClass: 1761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return DirectChild == cast<WhileStmt>(P)->getCond(); 177b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::DoStmtClass: 178b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<DoStmt>(P)->getCond(); 179b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::IfStmtClass: 180b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<IfStmt>(P)->getCond(); 181b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::IndirectGotoStmtClass: 182b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<IndirectGotoStmt>(P)->getTarget(); 183b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::SwitchStmtClass: 184b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return DirectChild == cast<SwitchStmt>(P)->getCond(); 185b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek case Stmt::ReturnStmtClass: 186b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek return true; 187b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek } 188b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek} 189b930d7adb7cb7642c9c49b39df04ebd5cbfa713aTed Kremenek 190