clang-tools 22.0.0git
ExprSequence.cpp
Go to the documentation of this file.
1//===----------------------------------------------------------------------===//
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#include "ExprSequence.h"
10#include "clang/AST/ParentMapContext.h"
11#include "llvm/ADT/SmallVector.h"
12#include <optional>
13
14namespace clang::tidy::utils {
15
16// Returns the Stmt nodes that are parents of 'S', skipping any potential
17// intermediate non-Stmt nodes.
18//
19// In almost all cases, this function returns a single parent or no parents at
20// all.
21//
22// The case that a Stmt has multiple parents is rare but does actually occur in
23// the parts of the AST that we're interested in. Specifically, InitListExpr
24// nodes cause ASTContext::getParent() to return multiple parents for certain
25// nodes in their subtree because RecursiveASTVisitor visits both the syntactic
26// and semantic forms of InitListExpr, and the parent-child relationships are
27// different between the two forms.
28static SmallVector<const Stmt *, 1> getParentStmts(const Stmt *S,
29 ASTContext *Context) {
30 SmallVector<const Stmt *, 1> Result;
31
32 TraversalKindScope RAII(*Context, TK_AsIs);
33 DynTypedNodeList Parents = Context->getParents(*S);
34
35 SmallVector<DynTypedNode, 1> NodesToProcess(Parents.begin(), Parents.end());
36
37 while (!NodesToProcess.empty()) {
38 DynTypedNode Node = NodesToProcess.back();
39 NodesToProcess.pop_back();
40
41 if (const auto *S = Node.get<Stmt>()) {
42 Result.push_back(S);
43 } else {
44 Parents = Context->getParents(Node);
45 NodesToProcess.append(Parents.begin(), Parents.end());
46 }
47 }
48
49 return Result;
50}
51
52static bool isDescendantOrEqual(const Stmt *Descendant, const Stmt *Ancestor,
53 ASTContext *Context) {
54 if (Descendant == Ancestor)
55 return true;
56 return llvm::any_of(getParentStmts(Descendant, Context),
57 [Ancestor, Context](const Stmt *Parent) {
58 return isDescendantOrEqual(Parent, Ancestor, Context);
59 });
60}
61
62static bool isDescendantOfArgs(const Stmt *Descendant, const CallExpr *Call,
63 ASTContext *Context) {
64 return llvm::any_of(Call->arguments(),
65 [Descendant, Context](const Expr *Arg) {
66 return isDescendantOrEqual(Descendant, Arg, Context);
67 });
68}
69
70static llvm::SmallVector<const InitListExpr *>
71getAllInitListForms(const InitListExpr *InitList) {
72 llvm::SmallVector<const InitListExpr *> Result = {InitList};
73 if (const InitListExpr *AltForm = InitList->getSyntacticForm())
74 Result.push_back(AltForm);
75 if (const InitListExpr *AltForm = InitList->getSemanticForm())
76 Result.push_back(AltForm);
77 return Result;
78}
79
80ExprSequence::ExprSequence(const CFG *TheCFG, const Stmt *Root,
81 ASTContext *TheContext)
82 : Context(TheContext), Root(Root) {
83 SyntheticStmtSourceMap.insert_range(TheCFG->synthetic_stmts());
84}
85
86bool ExprSequence::inSequence(const Stmt *Before, const Stmt *After) const {
87 Before = resolveSyntheticStmt(Before);
88 After = resolveSyntheticStmt(After);
89
90 // If 'After' is in the subtree of the siblings that follow 'Before' in the
91 // chain of successors, we know that 'After' is sequenced after 'Before'.
92 for (const Stmt *Successor = getSequenceSuccessor(Before); Successor;
93 Successor = getSequenceSuccessor(Successor)) {
94 if (isDescendantOrEqual(After, Successor, Context))
95 return true;
96 }
97
98 SmallVector<const Stmt *, 1> BeforeParents = getParentStmts(Before, Context);
99
100 // Since C++17, the callee of a call expression is guaranteed to be sequenced
101 // before all of the arguments.
102 // We handle this as a special case rather than using the general
103 // `getSequenceSuccessor` logic above because the callee expression doesn't
104 // have an unambiguous successor; the order in which arguments are evaluated
105 // is indeterminate.
106 for (const Stmt *Parent : BeforeParents) {
107 // Special case: If the callee is a `MemberExpr` with a `DeclRefExpr` as its
108 // base, we consider it to be sequenced _after_ the arguments. This is
109 // because the variable referenced in the base will only actually be
110 // accessed when the call happens, i.e. once all of the arguments have been
111 // evaluated. This has no basis in the C++ standard, but it reflects actual
112 // behavior that is relevant to a use-after-move scenario:
113 //
114 // ```
115 // a.bar(consumeA(std::move(a));
116 // ```
117 //
118 // In this example, we end up accessing `a` after it has been moved from,
119 // even though nominally the callee `a.bar` is evaluated before the argument
120 // `consumeA(std::move(a))`. Note that this is not specific to C++17, so
121 // we implement this logic unconditionally.
122 if (const auto *Call = dyn_cast<CXXMemberCallExpr>(Parent)) {
123 if (is_contained(Call->arguments(), Before) &&
124 isa<DeclRefExpr>(
125 Call->getImplicitObjectArgument()->IgnoreParenImpCasts()) &&
126 isDescendantOrEqual(After, Call->getImplicitObjectArgument(),
127 Context))
128 return true;
129
130 // We need this additional early exit so that we don't fall through to the
131 // more general logic below.
132 if (const auto *Member = dyn_cast<MemberExpr>(Before);
133 Member && Call->getCallee() == Member &&
134 isa<DeclRefExpr>(Member->getBase()->IgnoreParenImpCasts()) &&
135 isDescendantOfArgs(After, Call, Context))
136 return false;
137 }
138
139 if (!Context->getLangOpts().CPlusPlus17)
140 continue;
141
142 if (const auto *Call = dyn_cast<CallExpr>(Parent);
143 Call && Call->getCallee() == Before &&
144 isDescendantOfArgs(After, Call, Context))
145 return true;
146 }
147
148 // If 'After' is a parent of 'Before' or is sequenced after one of these
149 // parents, we know that it is sequenced after 'Before'.
150 for (const Stmt *Parent : BeforeParents) {
151 if (Parent == After || inSequence(Parent, After))
152 return true;
153 }
154
155 return false;
156}
157
158bool ExprSequence::potentiallyAfter(const Stmt *After,
159 const Stmt *Before) const {
160 return !inSequence(After, Before);
161}
162
163const Stmt *ExprSequence::getSequenceSuccessor(const Stmt *S) const {
164 for (const Stmt *Parent : getParentStmts(S, Context)) {
165 // If a statement has multiple parents, make sure we're using the parent
166 // that lies within the sub-tree under Root.
167 if (!isDescendantOrEqual(Parent, Root, Context))
168 continue;
169
170 if (const auto *BO = dyn_cast<BinaryOperator>(Parent)) {
171 // Comma operator: Right-hand side is sequenced after the left-hand side.
172 if (BO->getLHS() == S && BO->getOpcode() == BO_Comma)
173 return BO->getRHS();
174 } else if (const auto *InitList = dyn_cast<InitListExpr>(Parent)) {
175 // Initializer list: Each initializer clause is sequenced after the
176 // clauses that precede it.
177 for (const InitListExpr *Form : getAllInitListForms(InitList)) {
178 for (unsigned I = 1; I < Form->getNumInits(); ++I) {
179 if (Form->getInit(I - 1) == S) {
180 return Form->getInit(I);
181 }
182 }
183 }
184 } else if (const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(Parent)) {
185 // Constructor arguments are sequenced if the constructor call is written
186 // as list-initialization.
187 if (ConstructExpr->isListInitialization()) {
188 for (unsigned I = 1; I < ConstructExpr->getNumArgs(); ++I) {
189 if (ConstructExpr->getArg(I - 1) == S) {
190 return ConstructExpr->getArg(I);
191 }
192 }
193 }
194 } else if (const auto *Compound = dyn_cast<CompoundStmt>(Parent)) {
195 // Compound statement: Each sub-statement is sequenced after the
196 // statements that precede it.
197 const Stmt *Previous = nullptr;
198 for (const auto *Child : Compound->body()) {
199 if (Previous == S)
200 return Child;
201 Previous = Child;
202 }
203 } else if (const auto *TheDeclStmt = dyn_cast<DeclStmt>(Parent)) {
204 // Declaration: Every initializer expression is sequenced after the
205 // initializer expressions that precede it.
206 const Expr *PreviousInit = nullptr;
207 for (const Decl *TheDecl : TheDeclStmt->decls()) {
208 if (const auto *TheVarDecl = dyn_cast<VarDecl>(TheDecl)) {
209 if (const Expr *Init = TheVarDecl->getInit()) {
210 if (PreviousInit == S)
211 return Init;
212 PreviousInit = Init;
213 }
214 }
215 }
216 } else if (const auto *ForRange = dyn_cast<CXXForRangeStmt>(Parent)) {
217 // Range-based for: Loop variable declaration is sequenced before the
218 // body. (We need this rule because these get placed in the same
219 // CFGBlock.)
220 if (S == ForRange->getLoopVarStmt())
221 return ForRange->getBody();
222 } else if (const auto *TheIfStmt = dyn_cast<IfStmt>(Parent)) {
223 // If statement:
224 // - Sequence init statement before variable declaration, if present;
225 // before condition evaluation, otherwise.
226 // - Sequence variable declaration (along with the expression used to
227 // initialize it) before the evaluation of the condition.
228 if (S == TheIfStmt->getInit()) {
229 if (TheIfStmt->getConditionVariableDeclStmt() != nullptr)
230 return TheIfStmt->getConditionVariableDeclStmt();
231 return TheIfStmt->getCond();
232 }
233 if (S == TheIfStmt->getConditionVariableDeclStmt())
234 return TheIfStmt->getCond();
235 } else if (const auto *TheSwitchStmt = dyn_cast<SwitchStmt>(Parent)) {
236 // Ditto for switch statements.
237 if (S == TheSwitchStmt->getInit()) {
238 if (TheSwitchStmt->getConditionVariableDeclStmt() != nullptr)
239 return TheSwitchStmt->getConditionVariableDeclStmt();
240 return TheSwitchStmt->getCond();
241 }
242 if (S == TheSwitchStmt->getConditionVariableDeclStmt())
243 return TheSwitchStmt->getCond();
244 } else if (const auto *TheWhileStmt = dyn_cast<WhileStmt>(Parent)) {
245 // While statement: Sequence variable declaration (along with the
246 // expression used to initialize it) before the evaluation of the
247 // condition.
248 if (S == TheWhileStmt->getConditionVariableDeclStmt())
249 return TheWhileStmt->getCond();
250 }
251 }
252
253 return nullptr;
254}
255
256const Stmt *ExprSequence::resolveSyntheticStmt(const Stmt *S) const {
257 if (SyntheticStmtSourceMap.contains(S))
258 return SyntheticStmtSourceMap.lookup(S);
259 return S;
260}
261
262StmtToBlockMap::StmtToBlockMap(const CFG *TheCFG, ASTContext *TheContext)
263 : Context(TheContext) {
264 for (const auto *B : *TheCFG) {
265 for (const auto &Elem : *B) {
266 if (std::optional<CFGStmt> S = Elem.getAs<CFGStmt>())
267 Map[S->getStmt()] = B;
268 }
269 }
270}
271
272const CFGBlock *StmtToBlockMap::blockContainingStmt(const Stmt *S) const {
273 while (!Map.contains(S)) {
274 SmallVector<const Stmt *, 1> Parents = getParentStmts(S, Context);
275 if (Parents.empty())
276 return nullptr;
277 S = Parents[0];
278 }
279
280 return Map.lookup(S);
281}
282
283} // namespace clang::tidy::utils
bool potentiallyAfter(const Stmt *After, const Stmt *Before) const
Returns whether After can potentially be evaluated after Before.
ExprSequence(const CFG *TheCFG, const Stmt *Root, ASTContext *TheContext)
Initializes this ExprSequence with sequence information for the given CFG.
bool inSequence(const Stmt *Before, const Stmt *After) const
Returns whether Before is sequenced before After.
StmtToBlockMap(const CFG *TheCFG, ASTContext *TheContext)
Initializes the map for the given CFG.
const CFGBlock * blockContainingStmt(const Stmt *S) const
Returns the block that S is contained in.
static bool isDescendantOrEqual(const Stmt *Descendant, const Stmt *Ancestor, ASTContext *Context)
static bool isDescendantOfArgs(const Stmt *Descendant, const CallExpr *Call, ASTContext *Context)
static SmallVector< const Stmt *, 1 > getParentStmts(const Stmt *S, ASTContext *Context)
static llvm::SmallVector< const InitListExpr * > getAllInitListForms(const InitListExpr *InitList)