clang-tools-extra/clang-tidy/utils/ExprSequence.cpp

   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
  14 namespace 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.
  28 static 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
  52 namespace {
  53
  54 bool isDescendantOrEqual(const Stmt *Descendant, const Stmt *Ancestor,
  55                          ASTContext *Context) {
  56   if (Descendant == Ancestor)
  57     return true;
  58   for (const Stmt *Parent : getParentStmts(Descendant, Context)) {
  59     if (isDescendantOrEqual(Parent, Ancestor, Context))
  60       return true;
  61   }
  62
  63   return false;
  64 }
  65
  66 llvm::SmallVector<const InitListExpr *>
  67 getAllInitListForms(const InitListExpr *InitList) {
  68   llvm::SmallVector<const InitListExpr *> result = {InitList};
  69   if (const InitListExpr *AltForm = InitList->getSyntacticForm())
  70     result.push_back(AltForm);
  71   if (const InitListExpr *AltForm = InitList->getSemanticForm())
  72     result.push_back(AltForm);
  73   return result;
  74 }
  75
  76 } // namespace
  77
  78 ExprSequence::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
  86 bool 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   // 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(Before, Context)) {
 101     if (Parent == After || inSequence(Parent, After))
 102       return true;
 103   }
 104
 105   return false;
 106 }
 107
 108 bool ExprSequence::potentiallyAfter(const Stmt *After,
 109                                     const Stmt *Before) const {
 110   return !inSequence(After, Before);
 111 }
 112
 113 const 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(Parent, Root, Context))
 118       continue;
 119
 120     if (const auto *BO = dyn_cast<BinaryOperator>(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>(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(I - 1) == S) {
 130             return Form->getInit(I);
 131           }
 132         }
 133       }
 134     } else if (const auto *ConstructExpr = dyn_cast<CXXConstructExpr>(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(I - 1) == S) {
 140             return ConstructExpr->getArg(I);
 141           }
 142         }
 143       }
 144     } else if (const auto *Compound = dyn_cast<CompoundStmt>(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>(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>(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>(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>(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>(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>(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
 206 const Stmt *ExprSequence::resolveSyntheticStmt(const Stmt *S) const {
 207   if (SyntheticStmtSourceMap.count(S))
 208     return SyntheticStmtSourceMap.lookup(S);
 209   return S;
 210 }
 211
 212 StmtToBlockMap::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
 222 const CFGBlock *StmtToBlockMap::blockContainingStmt(const Stmt *S) const {
 223   while (!Map.count(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(S);
 231 }
 232
 233 } // namespace clang::tidy::utils