Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 1 | //===--- ParentMap.cpp - Mappings from Stmts to their Parents ---*- C++ -*-===// |
| 2 | // |
Chandler Carruth | 324f918 | 2019-01-19 08:50:56 +0000 | [diff] [blame] | 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 |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // This file defines the ParentMap class. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "clang/AST/ParentMap.h" |
Daniel Dunbar | acc5f3e | 2008-08-11 06:23:49 +0000 | [diff] [blame] | 14 | #include "clang/AST/Decl.h" |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 15 | #include "clang/AST/Expr.h" |
Jordan Rose | fb6f75f | 2013-06-06 01:57:24 +0000 | [diff] [blame] | 16 | #include "clang/AST/ExprCXX.h" |
George Karpenkov | ab58e02 | 2018-03-08 02:53:39 +0000 | [diff] [blame] | 17 | #include "clang/AST/StmtObjC.h" |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/DenseMap.h" |
| 19 | |
| 20 | using namespace clang; |
| 21 | |
| 22 | typedef llvm::DenseMap<Stmt*, Stmt*> MapTy; |
| 23 | |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 24 | enum OpaqueValueMode { |
| 25 | OV_Transparent, |
| 26 | OV_Opaque |
| 27 | }; |
| 28 | |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 29 | static void BuildParentMap(MapTy& M, Stmt* S, |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 30 | OpaqueValueMode OVMode = OV_Transparent) { |
Argyrios Kyrtzidis | a874687 | 2016-07-14 20:21:16 +0000 | [diff] [blame] | 31 | if (!S) |
| 32 | return; |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 33 | |
| 34 | switch (S->getStmtClass()) { |
| 35 | case Stmt::PseudoObjectExprClass: { |
| 36 | assert(OVMode == OV_Transparent && "Should not appear alongside OVEs"); |
| 37 | PseudoObjectExpr *POE = cast<PseudoObjectExpr>(S); |
| 38 | |
Jordan Rose | b9fdfb5 | 2013-05-18 02:27:09 +0000 | [diff] [blame] | 39 | // If we are rebuilding the map, clear out any existing state. |
| 40 | if (M[POE->getSyntacticForm()]) |
Benjamin Kramer | 247b5bd | 2015-07-02 21:03:14 +0000 | [diff] [blame] | 41 | for (Stmt *SubStmt : S->children()) |
| 42 | M[SubStmt] = nullptr; |
Jordan Rose | b9fdfb5 | 2013-05-18 02:27:09 +0000 | [diff] [blame] | 43 | |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 44 | M[POE->getSyntacticForm()] = S; |
| 45 | BuildParentMap(M, POE->getSyntacticForm(), OV_Transparent); |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 46 | |
| 47 | for (PseudoObjectExpr::semantics_iterator I = POE->semantics_begin(), |
| 48 | E = POE->semantics_end(); |
| 49 | I != E; ++I) { |
| 50 | M[*I] = S; |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 51 | BuildParentMap(M, *I, OV_Opaque); |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 52 | } |
| 53 | break; |
| 54 | } |
| 55 | case Stmt::BinaryConditionalOperatorClass: { |
| 56 | assert(OVMode == OV_Transparent && "Should not appear alongside OVEs"); |
| 57 | BinaryConditionalOperator *BCO = cast<BinaryConditionalOperator>(S); |
| 58 | |
| 59 | M[BCO->getCommon()] = S; |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 60 | BuildParentMap(M, BCO->getCommon(), OV_Transparent); |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 61 | |
| 62 | M[BCO->getCond()] = S; |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 63 | BuildParentMap(M, BCO->getCond(), OV_Opaque); |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 64 | |
| 65 | M[BCO->getTrueExpr()] = S; |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 66 | BuildParentMap(M, BCO->getTrueExpr(), OV_Opaque); |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 67 | |
| 68 | M[BCO->getFalseExpr()] = S; |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 69 | BuildParentMap(M, BCO->getFalseExpr(), OV_Transparent); |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 70 | |
| 71 | break; |
| 72 | } |
Jordan Rose | b9fdfb5 | 2013-05-18 02:27:09 +0000 | [diff] [blame] | 73 | case Stmt::OpaqueValueExprClass: { |
| 74 | // FIXME: This isn't correct; it assumes that multiple OpaqueValueExprs |
| 75 | // share a single source expression, but in the AST a single |
| 76 | // OpaqueValueExpr is shared among multiple parent expressions. |
| 77 | // The right thing to do is to give the OpaqueValueExpr its syntactic |
| 78 | // parent, then not reassign that when traversing the semantic expressions. |
| 79 | OpaqueValueExpr *OVE = cast<OpaqueValueExpr>(S); |
Serge Pavlov | fa047c5 | 2013-05-18 04:32:15 +0000 | [diff] [blame] | 80 | if (OVMode == OV_Transparent || !M[OVE->getSourceExpr()]) { |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 81 | M[OVE->getSourceExpr()] = S; |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 82 | BuildParentMap(M, OVE->getSourceExpr(), OV_Transparent); |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 83 | } |
| 84 | break; |
Jordan Rose | b9fdfb5 | 2013-05-18 02:27:09 +0000 | [diff] [blame] | 85 | } |
Alexey Bataev | 2688e58 | 2019-07-17 18:03:39 +0000 | [diff] [blame] | 86 | case Stmt::CapturedStmtClass: |
| 87 | for (Stmt *SubStmt : S->children()) { |
| 88 | if (SubStmt) { |
| 89 | M[SubStmt] = S; |
| 90 | BuildParentMap(M, SubStmt, OVMode); |
| 91 | } |
| 92 | } |
| 93 | if (Stmt *SubStmt = cast<CapturedStmt>(S)->getCapturedStmt()) { |
| 94 | M[SubStmt] = S; |
| 95 | BuildParentMap(M, SubStmt, OVMode); |
| 96 | } |
| 97 | break; |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 98 | default: |
Benjamin Kramer | 247b5bd | 2015-07-02 21:03:14 +0000 | [diff] [blame] | 99 | for (Stmt *SubStmt : S->children()) { |
| 100 | if (SubStmt) { |
| 101 | M[SubStmt] = S; |
| 102 | BuildParentMap(M, SubStmt, OVMode); |
Jordan Rose | 2b1b025 | 2012-08-06 21:28:11 +0000 | [diff] [blame] | 103 | } |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 104 | } |
Jordan Rose | 1e5101e | 2012-10-06 01:19:36 +0000 | [diff] [blame] | 105 | break; |
Jordan Rose | 2b1b025 | 2012-08-06 21:28:11 +0000 | [diff] [blame] | 106 | } |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 107 | } |
| 108 | |
Craig Topper | 613c4e1 | 2014-05-12 05:36:57 +0000 | [diff] [blame] | 109 | ParentMap::ParentMap(Stmt *S) : Impl(nullptr) { |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 110 | if (S) { |
| 111 | MapTy *M = new MapTy(); |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 112 | BuildParentMap(*M, S); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 113 | Impl = M; |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 114 | } |
| 115 | } |
| 116 | |
| 117 | ParentMap::~ParentMap() { |
| 118 | delete (MapTy*) Impl; |
| 119 | } |
| 120 | |
Ted Kremenek | d6543f8 | 2010-11-15 20:54:24 +0000 | [diff] [blame] | 121 | void ParentMap::addStmt(Stmt* S) { |
| 122 | if (S) { |
Jordan Rose | bb51899 | 2013-05-18 02:26:50 +0000 | [diff] [blame] | 123 | BuildParentMap(*(MapTy*) Impl, S); |
Ted Kremenek | d6543f8 | 2010-11-15 20:54:24 +0000 | [diff] [blame] | 124 | } |
| 125 | } |
| 126 | |
Jordan Rose | 49a246f | 2013-06-06 21:53:45 +0000 | [diff] [blame] | 127 | void ParentMap::setParent(const Stmt *S, const Stmt *Parent) { |
| 128 | assert(S); |
| 129 | assert(Parent); |
| 130 | MapTy *M = reinterpret_cast<MapTy *>(Impl); |
| 131 | M->insert(std::make_pair(const_cast<Stmt *>(S), const_cast<Stmt *>(Parent))); |
| 132 | } |
| 133 | |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 134 | Stmt* ParentMap::getParent(Stmt* S) const { |
| 135 | MapTy* M = (MapTy*) Impl; |
| 136 | MapTy::iterator I = M->find(S); |
Craig Topper | 613c4e1 | 2014-05-12 05:36:57 +0000 | [diff] [blame] | 137 | return I == M->end() ? nullptr : I->second; |
Ted Kremenek | f8e32cf | 2008-06-20 21:40:36 +0000 | [diff] [blame] | 138 | } |
Ted Kremenek | b930d7a | 2009-04-01 06:52:48 +0000 | [diff] [blame] | 139 | |
Ted Kremenek | b1b9f68 | 2009-05-11 19:49:27 +0000 | [diff] [blame] | 140 | Stmt *ParentMap::getParentIgnoreParens(Stmt *S) const { |
| 141 | do { S = getParent(S); } while (S && isa<ParenExpr>(S)); |
| 142 | return S; |
| 143 | } |
| 144 | |
Ted Kremenek | f4e532b | 2011-02-12 00:17:19 +0000 | [diff] [blame] | 145 | Stmt *ParentMap::getParentIgnoreParenCasts(Stmt *S) const { |
| 146 | do { |
| 147 | S = getParent(S); |
| 148 | } |
| 149 | while (S && (isa<ParenExpr>(S) || isa<CastExpr>(S))); |
| 150 | |
Fangrui Song | abdbb60 | 2018-07-30 19:24:48 +0000 | [diff] [blame] | 151 | return S; |
Ted Kremenek | f4e532b | 2011-02-12 00:17:19 +0000 | [diff] [blame] | 152 | } |
| 153 | |
Argyrios Kyrtzidis | 18fd0c6 | 2011-07-27 05:28:18 +0000 | [diff] [blame] | 154 | Stmt *ParentMap::getParentIgnoreParenImpCasts(Stmt *S) const { |
| 155 | do { |
| 156 | S = getParent(S); |
| 157 | } while (S && isa<Expr>(S) && cast<Expr>(S)->IgnoreParenImpCasts() != S); |
| 158 | |
| 159 | return S; |
| 160 | } |
| 161 | |
John McCall | f85e193 | 2011-06-15 23:02:42 +0000 | [diff] [blame] | 162 | Stmt *ParentMap::getOuterParenParent(Stmt *S) const { |
Craig Topper | 613c4e1 | 2014-05-12 05:36:57 +0000 | [diff] [blame] | 163 | Stmt *Paren = nullptr; |
John McCall | f85e193 | 2011-06-15 23:02:42 +0000 | [diff] [blame] | 164 | while (isa<ParenExpr>(S)) { |
| 165 | Paren = S; |
| 166 | S = getParent(S); |
| 167 | }; |
| 168 | return Paren; |
| 169 | } |
| 170 | |
Ted Kremenek | b930d7a | 2009-04-01 06:52:48 +0000 | [diff] [blame] | 171 | bool ParentMap::isConsumedExpr(Expr* E) const { |
| 172 | Stmt *P = getParent(E); |
| 173 | Stmt *DirectChild = E; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 174 | |
Jordan Rose | fb6f75f | 2013-06-06 01:57:24 +0000 | [diff] [blame] | 175 | // Ignore parents that don't guarantee consumption. |
| 176 | while (P && (isa<ParenExpr>(P) || isa<CastExpr>(P) || |
Bill Wendling | 0680f97 | 2018-10-31 03:48:47 +0000 | [diff] [blame] | 177 | isa<FullExpr>(P))) { |
Ted Kremenek | b930d7a | 2009-04-01 06:52:48 +0000 | [diff] [blame] | 178 | DirectChild = P; |
| 179 | P = getParent(P); |
| 180 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 181 | |
Ted Kremenek | b930d7a | 2009-04-01 06:52:48 +0000 | [diff] [blame] | 182 | if (!P) |
| 183 | return false; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 184 | |
Ted Kremenek | b930d7a | 2009-04-01 06:52:48 +0000 | [diff] [blame] | 185 | switch (P->getStmtClass()) { |
| 186 | default: |
| 187 | return isa<Expr>(P); |
| 188 | case Stmt::DeclStmtClass: |
| 189 | return true; |
| 190 | case Stmt::BinaryOperatorClass: { |
| 191 | BinaryOperator *BE = cast<BinaryOperator>(P); |
Ted Kremenek | 24ae89a | 2009-04-09 05:34:31 +0000 | [diff] [blame] | 192 | // If it is a comma, only the right side is consumed. |
Ted Kremenek | e42ac98 | 2009-04-08 18:49:36 +0000 | [diff] [blame] | 193 | // If it isn't a comma, both sides are consumed. |
John McCall | 2de56d1 | 2010-08-25 11:45:40 +0000 | [diff] [blame] | 194 | return BE->getOpcode()!=BO_Comma ||DirectChild==BE->getRHS(); |
Ted Kremenek | b930d7a | 2009-04-01 06:52:48 +0000 | [diff] [blame] | 195 | } |
| 196 | case Stmt::ForStmtClass: |
| 197 | return DirectChild == cast<ForStmt>(P)->getCond(); |
| 198 | case Stmt::WhileStmtClass: |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 199 | return DirectChild == cast<WhileStmt>(P)->getCond(); |
Ted Kremenek | b930d7a | 2009-04-01 06:52:48 +0000 | [diff] [blame] | 200 | case Stmt::DoStmtClass: |
| 201 | return DirectChild == cast<DoStmt>(P)->getCond(); |
| 202 | case Stmt::IfStmtClass: |
| 203 | return DirectChild == cast<IfStmt>(P)->getCond(); |
| 204 | case Stmt::IndirectGotoStmtClass: |
| 205 | return DirectChild == cast<IndirectGotoStmt>(P)->getTarget(); |
| 206 | case Stmt::SwitchStmtClass: |
| 207 | return DirectChild == cast<SwitchStmt>(P)->getCond(); |
George Karpenkov | ab58e02 | 2018-03-08 02:53:39 +0000 | [diff] [blame] | 208 | case Stmt::ObjCForCollectionStmtClass: |
| 209 | return DirectChild == cast<ObjCForCollectionStmt>(P)->getCollection(); |
Ted Kremenek | b930d7a | 2009-04-01 06:52:48 +0000 | [diff] [blame] | 210 | case Stmt::ReturnStmtClass: |
| 211 | return true; |
| 212 | } |
| 213 | } |
| 214 | |