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

source code of clang-tools-extra/clang-tidy/utils/ExprSequence.cpp