1 //===------------- ExprSequence.h - 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 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_EXPRSEQUENCE_H 10 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_EXPRSEQUENCE_H 11 12 #include "clang/Analysis/CFG.h" 13 #include "clang/Lex/Lexer.h" 14 #include "llvm/ADT/DenseMap.h" 15 #include "llvm/ADT/SmallPtrSet.h" 16 #include "llvm/ADT/SmallVector.h" 17 18 #include "../ClangTidy.h" 19 20 namespace clang { 21 namespace tidy { 22 namespace utils { 23 24 /// Provides information about the evaluation order of (sub-)expressions within 25 /// a `CFGBlock`. 26 /// 27 /// While a `CFGBlock` does contain individual `CFGElement`s for some 28 /// sub-expressions, the order in which those `CFGElement`s appear reflects 29 /// only one possible order in which the sub-expressions may be evaluated. 30 /// However, we want to warn if any of the potential evaluation orders can lead 31 /// to a use-after-move, not just the one contained in the `CFGBlock`. 32 /// 33 /// This class implements only a simplified version of the C++ sequencing 34 /// rules. The main limitation is that we do not distinguish between value 35 /// computation and side effect -- see the "Implementation" section for more 36 /// details. 37 /// 38 /// Note: `SequenceChecker` from SemaChecking.cpp does a similar job (and much 39 /// more thoroughly), but using it would require 40 /// - Pulling `SequenceChecker` out into a header file (i.e. making it part of 41 /// the API), 42 /// - Removing the dependency of `SequenceChecker` on `Sema`, and 43 /// - (Probably) modifying `SequenceChecker` to make it suitable to be used in 44 /// this context. 45 /// For the moment, it seems preferable to re-implement our own version of 46 /// sequence checking that is special-cased to what we need here. 47 /// 48 /// Implementation 49 /// -------------- 50 /// 51 /// `ExprSequence` uses two types of sequencing edges between nodes in the AST: 52 /// 53 /// - Every `Stmt` is assumed to be sequenced after its children. This is 54 /// overly optimistic because the standard only states that value computations 55 /// of operands are sequenced before the value computation of the operator, 56 /// making no guarantees about side effects (in general). 57 /// 58 /// For our purposes, this rule is sufficient, however, because this check is 59 /// interested in operations on objects, which are generally performed through 60 /// function calls (whether explicit and implicit). Function calls guarantee 61 /// that the value computations and side effects for all function arguments 62 /// are sequenced before the execution of the function. 63 /// 64 /// - In addition, some `Stmt`s are known to be sequenced before or after 65 /// their siblings. For example, the `Stmt`s that make up a `CompoundStmt`are 66 /// all sequenced relative to each other. The function 67 /// `getSequenceSuccessor()` implements these sequencing rules. 68 class ExprSequence { 69 public: 70 /// Initializes this `ExprSequence` with sequence information for the given 71 /// `CFG`. `Root` is the root statement the CFG was built from. 72 ExprSequence(const CFG *TheCFG, const Stmt *Root, ASTContext *TheContext); 73 74 /// Returns whether \p Before is sequenced before \p After. 75 bool inSequence(const Stmt *Before, const Stmt *After) const; 76 77 /// Returns whether \p After can potentially be evaluated after \p Before. 78 /// This is exactly equivalent to `!inSequence(After, Before)` but makes some 79 /// conditions read more naturally. 80 bool potentiallyAfter(const Stmt *After, const Stmt *Before) const; 81 82 private: 83 // Returns the sibling of \p S (if any) that is directly sequenced after \p S, 84 // or nullptr if no such sibling exists. For example, if \p S is the child of 85 // a `CompoundStmt`, this would return the Stmt that directly follows \p S in 86 // the `CompoundStmt`. 87 // 88 // As the sequencing of many constructs that change control flow is already 89 // encoded in the `CFG`, this function only implements the sequencing rules 90 // for those constructs where sequencing cannot be inferred from the `CFG`. 91 const Stmt *getSequenceSuccessor(const Stmt *S) const; 92 93 const Stmt *resolveSyntheticStmt(const Stmt *S) const; 94 95 ASTContext *Context; 96 const Stmt *Root; 97 98 llvm::DenseMap<const Stmt *, const Stmt *> SyntheticStmtSourceMap; 99 }; 100 101 /// Maps `Stmt`s to the `CFGBlock` that contains them. Some `Stmt`s may be 102 /// contained in more than one `CFGBlock`; in this case, they are mapped to the 103 /// innermost block (i.e. the one that is furthest from the root of the tree). 104 class StmtToBlockMap { 105 public: 106 /// Initializes the map for the given `CFG`. 107 StmtToBlockMap(const CFG *TheCFG, ASTContext *TheContext); 108 109 /// Returns the block that \p S is contained in. Some `Stmt`s may be contained 110 /// in more than one `CFGBlock`; in this case, this function returns the 111 /// innermost block (i.e. the one that is furthest from the root of the tree). 112 const CFGBlock *blockContainingStmt(const Stmt *S) const; 113 114 private: 115 ASTContext *Context; 116 117 llvm::DenseMap<const Stmt *, const CFGBlock *> Map; 118 }; 119 120 } // namespace utils 121 } // namespace tidy 122 } // namespace clang 123 124 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_EXPRSEQUENCE_H 125