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

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