285 lines · cpp
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-exception6//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 potential17// intermediate non-Stmt nodes.18//19// In almost all cases, this function returns a single parent or no parents at20// all.21//22// The case that a Stmt has multiple parents is rare but does actually occur in23// the parts of the AST that we're interested in. Specifically, InitListExpr24// nodes cause ASTContext::getParent() to return multiple parents for certain25// nodes in their subtree because RecursiveASTVisitor visits both the syntactic26// and semantic forms of InitListExpr, and the parent-child relationships are27// 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 const 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 const 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 the91 // 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 const SmallVector<const Stmt *, 1> BeforeParents =99 getParentStmts(Before, Context);100 101 // Since C++17, the callee of a call expression is guaranteed to be sequenced102 // before all of the arguments.103 // We handle this as a special case rather than using the general104 // `getSequenceSuccessor` logic above because the callee expression doesn't105 // have an unambiguous successor; the order in which arguments are evaluated106 // is indeterminate.107 for (const Stmt *Parent : BeforeParents) {108 // Special case: If the callee is a `MemberExpr` with a `DeclRefExpr` as its109 // base, we consider it to be sequenced _after_ the arguments. This is110 // because the variable referenced in the base will only actually be111 // accessed when the call happens, i.e. once all of the arguments have been112 // evaluated. This has no basis in the C++ standard, but it reflects actual113 // behavior that is relevant to a use-after-move scenario:114 //115 // ```116 // a.bar(consumeA(std::move(a));117 // ```118 //119 // In this example, we end up accessing `a` after it has been moved from,120 // even though nominally the callee `a.bar` is evaluated before the argument121 // `consumeA(std::move(a))`. Note that this is not specific to C++17, so122 // we implement this logic unconditionally.123 if (const auto *Call = dyn_cast<CXXMemberCallExpr>(Parent)) {124 if (is_contained(Call->arguments(), Before) &&125 isa<DeclRefExpr>(126 Call->getImplicitObjectArgument()->IgnoreParenImpCasts()) &&127 isDescendantOrEqual(After, Call->getImplicitObjectArgument(),128 Context))129 return true;130 131 // We need this additional early exit so that we don't fall through to the132 // more general logic below.133 if (const auto *Member = dyn_cast<MemberExpr>(Before);134 Member && Call->getCallee() == Member &&135 isa<DeclRefExpr>(Member->getBase()->IgnoreParenImpCasts()) &&136 isDescendantOfArgs(After, Call, Context))137 return false;138 }139 140 if (!Context->getLangOpts().CPlusPlus17)141 continue;142 143 if (const auto *Call = dyn_cast<CallExpr>(Parent);144 Call && Call->getCallee() == Before &&145 isDescendantOfArgs(After, Call, Context))146 return true;147 }148 149 // If 'After' is a parent of 'Before' or is sequenced after one of these150 // parents, we know that it is sequenced after 'Before'.151 for (const Stmt *Parent : BeforeParents) {152 if (Parent == After || inSequence(Parent, After))153 return true;154 }155 156 return false;157}158 159bool ExprSequence::potentiallyAfter(const Stmt *After,160 const Stmt *Before) const {161 return !inSequence(After, Before);162}163 164const Stmt *ExprSequence::getSequenceSuccessor(const Stmt *S) const {165 for (const Stmt *Parent : getParentStmts(S, Context)) {166 // If a statement has multiple parents, make sure we're using the parent167 // that lies within the sub-tree under Root.168 if (!isDescendantOrEqual(Parent, Root, Context))169 continue;170 171 if (const auto *BO = dyn_cast<BinaryOperator>(Parent)) {172 // Comma operator: Right-hand side is sequenced after the left-hand side.173 if (BO->getLHS() == S && BO->getOpcode() == BO_Comma)174 return BO->getRHS();175 } else if (const auto *InitList = dyn_cast<InitListExpr>(Parent)) {176 // Initializer list: Each initializer clause is sequenced after the177 // clauses that precede it.178 for (const InitListExpr *Form : getAllInitListForms(InitList)) {179 for (unsigned I = 1; I < Form->getNumInits(); ++I) {180 if (Form->getInit(I - 1) == S) {181 return Form->getInit(I);182 }183 }184 }185 } else if (const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(Parent)) {186 // Constructor arguments are sequenced if the constructor call is written187 // as list-initialization.188 if (ConstructExpr->isListInitialization()) {189 for (unsigned I = 1; I < ConstructExpr->getNumArgs(); ++I) {190 if (ConstructExpr->getArg(I - 1) == S) {191 return ConstructExpr->getArg(I);192 }193 }194 }195 } else if (const auto *Compound = dyn_cast<CompoundStmt>(Parent)) {196 // Compound statement: Each sub-statement is sequenced after the197 // statements that precede it.198 const Stmt *Previous = nullptr;199 for (const auto *Child : Compound->body()) {200 if (Previous == S)201 return Child;202 Previous = Child;203 }204 } else if (const auto *TheDeclStmt = dyn_cast<DeclStmt>(Parent)) {205 // Declaration: Every initializer expression is sequenced after the206 // initializer expressions that precede it.207 const Expr *PreviousInit = nullptr;208 for (const Decl *TheDecl : TheDeclStmt->decls()) {209 if (const auto *TheVarDecl = dyn_cast<VarDecl>(TheDecl)) {210 if (const Expr *Init = TheVarDecl->getInit()) {211 if (PreviousInit == S)212 return Init;213 PreviousInit = Init;214 }215 }216 }217 } else if (const auto *ForRange = dyn_cast<CXXForRangeStmt>(Parent)) {218 // Range-based for: Loop variable declaration is sequenced before the219 // body. (We need this rule because these get placed in the same220 // CFGBlock.)221 if (S == ForRange->getLoopVarStmt())222 return ForRange->getBody();223 } else if (const auto *TheIfStmt = dyn_cast<IfStmt>(Parent)) {224 // If statement:225 // - Sequence init statement before variable declaration, if present;226 // before condition evaluation, otherwise.227 // - Sequence variable declaration (along with the expression used to228 // initialize it) before the evaluation of the condition.229 if (S == TheIfStmt->getInit()) {230 if (TheIfStmt->getConditionVariableDeclStmt() != nullptr)231 return TheIfStmt->getConditionVariableDeclStmt();232 return TheIfStmt->getCond();233 }234 if (S == TheIfStmt->getConditionVariableDeclStmt())235 return TheIfStmt->getCond();236 } else if (const auto *TheSwitchStmt = dyn_cast<SwitchStmt>(Parent)) {237 // Ditto for switch statements.238 if (S == TheSwitchStmt->getInit()) {239 if (TheSwitchStmt->getConditionVariableDeclStmt() != nullptr)240 return TheSwitchStmt->getConditionVariableDeclStmt();241 return TheSwitchStmt->getCond();242 }243 if (S == TheSwitchStmt->getConditionVariableDeclStmt())244 return TheSwitchStmt->getCond();245 } else if (const auto *TheWhileStmt = dyn_cast<WhileStmt>(Parent)) {246 // While statement: Sequence variable declaration (along with the247 // expression used to initialize it) before the evaluation of the248 // condition.249 if (S == TheWhileStmt->getConditionVariableDeclStmt())250 return TheWhileStmt->getCond();251 }252 }253 254 return nullptr;255}256 257const Stmt *ExprSequence::resolveSyntheticStmt(const Stmt *S) const {258 if (SyntheticStmtSourceMap.contains(S))259 return SyntheticStmtSourceMap.lookup(S);260 return S;261}262 263StmtToBlockMap::StmtToBlockMap(const CFG *TheCFG, ASTContext *TheContext)264 : Context(TheContext) {265 for (const auto *B : *TheCFG) {266 for (const auto &Elem : *B) {267 if (std::optional<CFGStmt> S = Elem.getAs<CFGStmt>())268 Map[S->getStmt()] = B;269 }270 }271}272 273const CFGBlock *StmtToBlockMap::blockContainingStmt(const Stmt *S) const {274 while (!Map.contains(S)) {275 SmallVector<const Stmt *, 1> Parents = getParentStmts(S, Context);276 if (Parents.empty())277 return nullptr;278 S = Parents[0];279 }280 281 return Map.lookup(S);282}283 284} // namespace clang::tidy::utils285