1//===--- ParentMap.cpp - Mappings from Stmts to their Parents ---*- 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// This file defines the ParentMap class.
10//
11//===----------------------------------------------------------------------===//
12
13#include "clang/AST/ParentMap.h"
14#include "clang/AST/Decl.h"
15#include "clang/AST/Expr.h"
16#include "clang/AST/StmtObjC.h"
17#include "llvm/ADT/DenseMap.h"
18
19using namespace clang;
20
21typedef llvm::DenseMap<Stmt*, Stmt*> MapTy;
22
23enum OpaqueValueMode {
24 OV_Transparent,
25 OV_Opaque
26};
27
28static void BuildParentMap(MapTy& M, Stmt* S,
29 OpaqueValueMode OVMode = OV_Transparent) {
30 if (!S)
31 return;
32
33 switch (S->getStmtClass()) {
34 case Stmt::PseudoObjectExprClass: {
35 PseudoObjectExpr *POE = cast<PseudoObjectExpr>(Val: S);
36 Expr *SF = POE->getSyntacticForm();
37
38 auto [Iter, Inserted] = M.try_emplace(Key: SF, Args&: S);
39 if (!Inserted) {
40 // Nothing more to do in opaque mode if we are updating an existing map.
41 if (OVMode == OV_Opaque)
42 break;
43 // Update the entry in transparent mode, and clear existing state.
44 Iter->second = S;
45 for (Stmt *SubStmt : S->children())
46 M.erase(Val: SubStmt);
47 }
48 BuildParentMap(M, S: SF, OVMode: OV_Transparent);
49
50 for (PseudoObjectExpr::semantics_iterator I = POE->semantics_begin(),
51 E = POE->semantics_end();
52 I != E; ++I) {
53 M[*I] = S;
54 BuildParentMap(M, S: *I, OVMode: OV_Opaque);
55 }
56 break;
57 }
58 case Stmt::BinaryConditionalOperatorClass: {
59 assert(OVMode == OV_Transparent && "Should not appear alongside OVEs");
60 BinaryConditionalOperator *BCO = cast<BinaryConditionalOperator>(Val: S);
61
62 M[BCO->getCommon()] = S;
63 BuildParentMap(M, S: BCO->getCommon(), OVMode: OV_Transparent);
64
65 M[BCO->getCond()] = S;
66 BuildParentMap(M, S: BCO->getCond(), OVMode: OV_Opaque);
67
68 M[BCO->getTrueExpr()] = S;
69 BuildParentMap(M, S: BCO->getTrueExpr(), OVMode: OV_Opaque);
70
71 M[BCO->getFalseExpr()] = S;
72 BuildParentMap(M, S: BCO->getFalseExpr(), OVMode: OV_Transparent);
73
74 break;
75 }
76 case Stmt::OpaqueValueExprClass: {
77 // FIXME: This isn't correct; it assumes that multiple OpaqueValueExprs
78 // share a single source expression, but in the AST a single
79 // OpaqueValueExpr is shared among multiple parent expressions.
80 // The right thing to do is to give the OpaqueValueExpr its syntactic
81 // parent, then not reassign that when traversing the semantic expressions.
82 OpaqueValueExpr *OVE = cast<OpaqueValueExpr>(Val: S);
83 Expr *SrcExpr = OVE->getSourceExpr();
84 auto [Iter, Inserted] = M.try_emplace(Key: SrcExpr, Args&: S);
85 // Force update in transparent mode.
86 if (!Inserted && OVMode == OV_Transparent) {
87 Iter->second = S;
88 Inserted = true;
89 }
90 if (Inserted)
91 BuildParentMap(M, S: SrcExpr, OVMode: OV_Transparent);
92 break;
93 }
94 case Stmt::CapturedStmtClass:
95 for (Stmt *SubStmt : S->children()) {
96 if (SubStmt) {
97 M[SubStmt] = S;
98 BuildParentMap(M, S: SubStmt, OVMode);
99 }
100 }
101 if (Stmt *SubStmt = cast<CapturedStmt>(Val: S)->getCapturedStmt()) {
102 M[SubStmt] = S;
103 BuildParentMap(M, S: SubStmt, OVMode);
104 }
105 break;
106 default:
107 for (Stmt *SubStmt : S->children()) {
108 if (SubStmt) {
109 M[SubStmt] = S;
110 BuildParentMap(M, S: SubStmt, OVMode);
111 }
112 }
113 break;
114 }
115}
116
117ParentMap::ParentMap(Stmt *S) : Impl(nullptr) {
118 if (S) {
119 MapTy *M = new MapTy();
120 BuildParentMap(M&: *M, S);
121 Impl = M;
122 }
123}
124
125ParentMap::~ParentMap() {
126 delete (MapTy*) Impl;
127}
128
129void ParentMap::addStmt(Stmt* S) {
130 if (S) {
131 BuildParentMap(M&: *(MapTy*) Impl, S);
132 }
133}
134
135void ParentMap::setParent(const Stmt *S, const Stmt *Parent) {
136 assert(S);
137 assert(Parent);
138 MapTy *M = reinterpret_cast<MapTy *>(Impl);
139 M->insert(KV: std::make_pair(x: const_cast<Stmt *>(S), y: const_cast<Stmt *>(Parent)));
140}
141
142Stmt* ParentMap::getParent(Stmt* S) const {
143 MapTy* M = (MapTy*) Impl;
144 return M->lookup(Val: S);
145}
146
147Stmt *ParentMap::getParentIgnoreParens(Stmt *S) const {
148 do {
149 S = getParent(S);
150 } while (isa_and_nonnull<ParenExpr>(Val: S));
151 return S;
152}
153
154Stmt *ParentMap::getParentIgnoreParenCasts(Stmt *S) const {
155 do {
156 S = getParent(S);
157 }
158 while (S && (isa<ParenExpr>(Val: S) || isa<CastExpr>(Val: S)));
159
160 return S;
161}
162
163Stmt *ParentMap::getParentIgnoreParenImpCasts(Stmt *S) const {
164 do {
165 S = getParent(S);
166 } while (isa_and_nonnull<Expr>(Val: S) &&
167 cast<Expr>(Val: S)->IgnoreParenImpCasts() != S);
168
169 return S;
170}
171
172Stmt *ParentMap::getOuterParenParent(Stmt *S) const {
173 Stmt *Paren = nullptr;
174 while (isa<ParenExpr>(Val: S)) {
175 Paren = S;
176 S = getParent(S);
177 };
178 return Paren;
179}
180
181bool ParentMap::isConsumedExpr(Expr* E) const {
182 Stmt *P = getParent(S: E);
183 Stmt *DirectChild = E;
184
185 // Ignore parents that don't guarantee consumption.
186 while (P && (isa<ParenExpr>(Val: P) || isa<CastExpr>(Val: P) ||
187 isa<FullExpr>(Val: P))) {
188 DirectChild = P;
189 P = getParent(S: P);
190 }
191
192 if (!P)
193 return false;
194
195 switch (P->getStmtClass()) {
196 default:
197 return isa<Expr>(Val: P);
198 case Stmt::DeclStmtClass:
199 return true;
200 case Stmt::BinaryOperatorClass: {
201 BinaryOperator *BE = cast<BinaryOperator>(Val: P);
202 // If it is a comma, only the right side is consumed.
203 // If it isn't a comma, both sides are consumed.
204 return BE->getOpcode()!=BO_Comma ||DirectChild==BE->getRHS();
205 }
206 case Stmt::ForStmtClass:
207 return DirectChild == cast<ForStmt>(Val: P)->getCond();
208 case Stmt::WhileStmtClass:
209 return DirectChild == cast<WhileStmt>(Val: P)->getCond();
210 case Stmt::DoStmtClass:
211 return DirectChild == cast<DoStmt>(Val: P)->getCond();
212 case Stmt::IfStmtClass:
213 return DirectChild == cast<IfStmt>(Val: P)->getCond();
214 case Stmt::IndirectGotoStmtClass:
215 return DirectChild == cast<IndirectGotoStmt>(Val: P)->getTarget();
216 case Stmt::SwitchStmtClass:
217 return DirectChild == cast<SwitchStmt>(Val: P)->getCond();
218 case Stmt::ObjCForCollectionStmtClass:
219 return DirectChild == cast<ObjCForCollectionStmt>(Val: P)->getCollection();
220 case Stmt::ReturnStmtClass:
221 return true;
222 }
223}
224
225