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 for (const Stmt *Parent : getParentStmts(S: Descendant, Context)) {
59 if (isDescendantOrEqual(Descendant: Parent, Ancestor, Context))
60 return true;
61 }
62
63 return false;
64}
65
66llvm::SmallVector<const InitListExpr *>
67getAllInitListForms(const InitListExpr *InitList) {
68 llvm::SmallVector<const InitListExpr *> result = {InitList};
69 if (const InitListExpr *AltForm = InitList->getSyntacticForm())
70 result.push_back(Elt: AltForm);
71 if (const InitListExpr *AltForm = InitList->getSemanticForm())
72 result.push_back(Elt: AltForm);
73 return result;
74}
75
76} // namespace
77
78ExprSequence::ExprSequence(const CFG *TheCFG, const Stmt *Root,
79 ASTContext *TheContext)
80 : Context(TheContext), Root(Root) {
81 for (const auto &SyntheticStmt : TheCFG->synthetic_stmts()) {
82 SyntheticStmtSourceMap[SyntheticStmt.first] = SyntheticStmt.second;
83 }
84}
85
86bool ExprSequence::inSequence(const Stmt *Before, const Stmt *After) const {
87 Before = resolveSyntheticStmt(S: Before);
88 After = resolveSyntheticStmt(S: 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(S: Before); Successor;
93 Successor = getSequenceSuccessor(S: Successor)) {
94 if (isDescendantOrEqual(Descendant: After, Ancestor: Successor, Context))
95 return true;
96 }
97
98 // If 'After' is a parent of 'Before' or is sequenced after one of these
99 // parents, we know that it is sequenced after 'Before'.
100 for (const Stmt *Parent : getParentStmts(S: Before, Context)) {
101 if (Parent == After || inSequence(Before: Parent, After))
102 return true;
103 }
104
105 return false;
106}
107
108bool ExprSequence::potentiallyAfter(const Stmt *After,
109 const Stmt *Before) const {
110 return !inSequence(Before: After, After: Before);
111}
112
113const Stmt *ExprSequence::getSequenceSuccessor(const Stmt *S) const {
114 for (const Stmt *Parent : getParentStmts(S, Context)) {
115 // If a statement has multiple parents, make sure we're using the parent
116 // that lies within the sub-tree under Root.
117 if (!isDescendantOrEqual(Descendant: Parent, Ancestor: Root, Context))
118 continue;
119
120 if (const auto *BO = dyn_cast<BinaryOperator>(Val: Parent)) {
121 // Comma operator: Right-hand side is sequenced after the left-hand side.
122 if (BO->getLHS() == S && BO->getOpcode() == BO_Comma)
123 return BO->getRHS();
124 } else if (const auto *InitList = dyn_cast<InitListExpr>(Val: Parent)) {
125 // Initializer list: Each initializer clause is sequenced after the
126 // clauses that precede it.
127 for (const InitListExpr *Form : getAllInitListForms(InitList)) {
128 for (unsigned I = 1; I < Form->getNumInits(); ++I) {
129 if (Form->getInit(Init: I - 1) == S) {
130 return Form->getInit(Init: I);
131 }
132 }
133 }
134 } else if (const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(Val: Parent)) {
135 // Constructor arguments are sequenced if the constructor call is written
136 // as list-initialization.
137 if (ConstructExpr->isListInitialization()) {
138 for (unsigned I = 1; I < ConstructExpr->getNumArgs(); ++I) {
139 if (ConstructExpr->getArg(Arg: I - 1) == S) {
140 return ConstructExpr->getArg(Arg: I);
141 }
142 }
143 }
144 } else if (const auto *Compound = dyn_cast<CompoundStmt>(Val: Parent)) {
145 // Compound statement: Each sub-statement is sequenced after the
146 // statements that precede it.
147 const Stmt *Previous = nullptr;
148 for (const auto *Child : Compound->body()) {
149 if (Previous == S)
150 return Child;
151 Previous = Child;
152 }
153 } else if (const auto *TheDeclStmt = dyn_cast<DeclStmt>(Val: Parent)) {
154 // Declaration: Every initializer expression is sequenced after the
155 // initializer expressions that precede it.
156 const Expr *PreviousInit = nullptr;
157 for (const Decl *TheDecl : TheDeclStmt->decls()) {
158 if (const auto *TheVarDecl = dyn_cast<VarDecl>(Val: TheDecl)) {
159 if (const Expr *Init = TheVarDecl->getInit()) {
160 if (PreviousInit == S)
161 return Init;
162 PreviousInit = Init;
163 }
164 }
165 }
166 } else if (const auto *ForRange = dyn_cast<CXXForRangeStmt>(Val: Parent)) {
167 // Range-based for: Loop variable declaration is sequenced before the
168 // body. (We need this rule because these get placed in the same
169 // CFGBlock.)
170 if (S == ForRange->getLoopVarStmt())
171 return ForRange->getBody();
172 } else if (const auto *TheIfStmt = dyn_cast<IfStmt>(Val: Parent)) {
173 // If statement:
174 // - Sequence init statement before variable declaration, if present;
175 // before condition evaluation, otherwise.
176 // - Sequence variable declaration (along with the expression used to
177 // initialize it) before the evaluation of the condition.
178 if (S == TheIfStmt->getInit()) {
179 if (TheIfStmt->getConditionVariableDeclStmt() != nullptr)
180 return TheIfStmt->getConditionVariableDeclStmt();
181 return TheIfStmt->getCond();
182 }
183 if (S == TheIfStmt->getConditionVariableDeclStmt())
184 return TheIfStmt->getCond();
185 } else if (const auto *TheSwitchStmt = dyn_cast<SwitchStmt>(Val: Parent)) {
186 // Ditto for switch statements.
187 if (S == TheSwitchStmt->getInit()) {
188 if (TheSwitchStmt->getConditionVariableDeclStmt() != nullptr)
189 return TheSwitchStmt->getConditionVariableDeclStmt();
190 return TheSwitchStmt->getCond();
191 }
192 if (S == TheSwitchStmt->getConditionVariableDeclStmt())
193 return TheSwitchStmt->getCond();
194 } else if (const auto *TheWhileStmt = dyn_cast<WhileStmt>(Val: Parent)) {
195 // While statement: Sequence variable declaration (along with the
196 // expression used to initialize it) before the evaluation of the
197 // condition.
198 if (S == TheWhileStmt->getConditionVariableDeclStmt())
199 return TheWhileStmt->getCond();
200 }
201 }
202
203 return nullptr;
204}
205
206const Stmt *ExprSequence::resolveSyntheticStmt(const Stmt *S) const {
207 if (SyntheticStmtSourceMap.count(Val: S))
208 return SyntheticStmtSourceMap.lookup(Val: S);
209 return S;
210}
211
212StmtToBlockMap::StmtToBlockMap(const CFG *TheCFG, ASTContext *TheContext)
213 : Context(TheContext) {
214 for (const auto *B : *TheCFG) {
215 for (const auto &Elem : *B) {
216 if (std::optional<CFGStmt> S = Elem.getAs<CFGStmt>())
217 Map[S->getStmt()] = B;
218 }
219 }
220}
221
222const CFGBlock *StmtToBlockMap::blockContainingStmt(const Stmt *S) const {
223 while (!Map.count(Val: S)) {
224 SmallVector<const Stmt *, 1> Parents = getParentStmts(S, Context);
225 if (Parents.empty())
226 return nullptr;
227 S = Parents[0];
228 }
229
230 return Map.lookup(Val: S);
231}
232
233} // namespace clang::tidy::utils
234

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