clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp

   1 //===-- STLAlgorithmModeling.cpp -----------------------------------*- C++ -*--//
   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 // Models STL algorithms.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  14 #include "clang/StaticAnalyzer/Core/Checker.h"
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  18
  19 #include "Iterator.h"
  20
  21 using namespace clang;
  22 using namespace ento;
  23 using namespace iterator;
  24
  25 namespace {
  26
  27 class STLAlgorithmModeling : public Checker<eval::Call> {
  28   bool evalFind(CheckerContext &C, const CallExpr *CE) const;
  29
  30   void Find(CheckerContext &C, const CallExpr *CE, unsigned paramNum) const;
  31
  32   using FnCheck = bool (STLAlgorithmModeling::*)(CheckerContext &,
  33                                                 const CallExpr *) const;
  34
  35   const CallDescriptionMap<FnCheck> Callbacks = {
  36     {{{"std", "find"}, 3}, &STLAlgorithmModeling::evalFind},
  37     {{{"std", "find"}, 4}, &STLAlgorithmModeling::evalFind},
  38     {{{"std", "find_if"}, 3}, &STLAlgorithmModeling::evalFind},
  39     {{{"std", "find_if"}, 4}, &STLAlgorithmModeling::evalFind},
  40     {{{"std", "find_if_not"}, 3}, &STLAlgorithmModeling::evalFind},
  41     {{{"std", "find_if_not"}, 4}, &STLAlgorithmModeling::evalFind},
  42     {{{"std", "find_first_of"}, 4}, &STLAlgorithmModeling::evalFind},
  43     {{{"std", "find_first_of"}, 5}, &STLAlgorithmModeling::evalFind},
  44     {{{"std", "find_first_of"}, 6}, &STLAlgorithmModeling::evalFind},
  45     {{{"std", "find_end"}, 4}, &STLAlgorithmModeling::evalFind},
  46     {{{"std", "find_end"}, 5}, &STLAlgorithmModeling::evalFind},
  47     {{{"std", "find_end"}, 6}, &STLAlgorithmModeling::evalFind},
  48     {{{"std", "lower_bound"}, 3}, &STLAlgorithmModeling::evalFind},
  49     {{{"std", "lower_bound"}, 4}, &STLAlgorithmModeling::evalFind},
  50     {{{"std", "upper_bound"}, 3}, &STLAlgorithmModeling::evalFind},
  51     {{{"std", "upper_bound"}, 4}, &STLAlgorithmModeling::evalFind},
  52     {{{"std", "search"}, 3}, &STLAlgorithmModeling::evalFind},
  53     {{{"std", "search"}, 4}, &STLAlgorithmModeling::evalFind},
  54     {{{"std", "search"}, 5}, &STLAlgorithmModeling::evalFind},
  55     {{{"std", "search"}, 6}, &STLAlgorithmModeling::evalFind},
  56     {{{"std", "search_n"}, 4}, &STLAlgorithmModeling::evalFind},
  57     {{{"std", "search_n"}, 5}, &STLAlgorithmModeling::evalFind},
  58     {{{"std", "search_n"}, 6}, &STLAlgorithmModeling::evalFind},
  59   };
  60
  61 public:
  62   STLAlgorithmModeling() = default;
  63
  64   bool AggressiveStdFindModeling = false;
  65
  66   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
  67 }; //
  68
  69 bool STLAlgorithmModeling::evalCall(const CallEvent &Call,
  70                                     CheckerContext &C) const {
  71   const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
  72   if (!CE)
  73     return false;
  74
  75   const FnCheck *Handler = Callbacks.lookup(Call);
  76   if (!Handler)
  77     return false;
  78
  79   return (this->**Handler)(C, CE);
  80 }
  81
  82 bool STLAlgorithmModeling::evalFind(CheckerContext &C,
  83                                     const CallExpr *CE) const {
  84   // std::find()-like functions either take their primary range in the first
  85   // two parameters, or if the first parameter is "execution policy" then in
  86   // the second and third. This means that the second parameter must always be
  87   // an iterator.
  88   if (!isIteratorType(CE->getArg(1)->getType()))
  89     return false;
  90
  91   // If no "execution policy" parameter is used then the first argument is the
  92   // beginning of the range.
  93   if (isIteratorType(CE->getArg(0)->getType())) {
  94     Find(C, CE, 0);
  95     return true;
  96   }
  97
  98   // If "execution policy" parameter is used then the second argument is the
  99   // beginning of the range.
 100   if (isIteratorType(CE->getArg(2)->getType())) {
 101     Find(C, CE, 1);
 102     return true;
 103   }
 104
 105   return false;
 106 }
 107
 108 void STLAlgorithmModeling::Find(CheckerContext &C, const CallExpr *CE,
 109                                 unsigned paramNum) const {
 110   auto State = C.getState();
 111   auto &SVB = C.getSValBuilder();
 112   const auto *LCtx = C.getLocationContext();
 113
 114   SVal RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
 115   SVal Param = State->getSVal(CE->getArg(paramNum), LCtx);
 116
 117   auto StateFound = State->BindExpr(CE, LCtx, RetVal);
 118
 119   // If we have an iterator position for the range-begin argument then we can
 120   // assume that in case of successful search the position of the found element
 121   // is not ahead of it.
 122   // FIXME: Reverse iterators
 123   const auto *Pos = getIteratorPosition(State, Param);
 124   if (Pos) {
 125     StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
 126                                         CE, LCtx, C.blockCount());
 127     const auto *NewPos = getIteratorPosition(StateFound, RetVal);
 128     assert(NewPos && "Failed to create new iterator position.");
 129
 130     SVal GreaterOrEqual = SVB.evalBinOp(StateFound, BO_GE,
 131                                         nonloc::SymbolVal(NewPos->getOffset()),
 132                                         nonloc::SymbolVal(Pos->getOffset()),
 133                                         SVB.getConditionType());
 134     assert(isa<DefinedSVal>(GreaterOrEqual) &&
 135            "Symbol comparison must be a `DefinedSVal`");
 136     StateFound = StateFound->assume(GreaterOrEqual.castAs<DefinedSVal>(), true);
 137   }
 138
 139   Param = State->getSVal(CE->getArg(paramNum + 1), LCtx);
 140
 141   // If we have an iterator position for the range-end argument then we can
 142   // assume that in case of successful search the position of the found element
 143   // is ahead of it.
 144   // FIXME: Reverse iterators
 145   Pos = getIteratorPosition(State, Param);
 146   if (Pos) {
 147     StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
 148                                         CE, LCtx, C.blockCount());
 149     const auto *NewPos = getIteratorPosition(StateFound, RetVal);
 150     assert(NewPos && "Failed to create new iterator position.");
 151
 152     SVal Less = SVB.evalBinOp(StateFound, BO_LT,
 153                               nonloc::SymbolVal(NewPos->getOffset()),
 154                               nonloc::SymbolVal(Pos->getOffset()),
 155                               SVB.getConditionType());
 156     assert(isa<DefinedSVal>(Less) &&
 157            "Symbol comparison must be a `DefinedSVal`");
 158     StateFound = StateFound->assume(Less.castAs<DefinedSVal>(), true);
 159   }
 160
 161   C.addTransition(StateFound);
 162
 163   if (AggressiveStdFindModeling) {
 164     auto StateNotFound = State->BindExpr(CE, LCtx, Param);
 165     C.addTransition(StateNotFound);
 166   }
 167 }
 168
 169 } // namespace
 170
 171 void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
 172   auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();
 173   Checker->AggressiveStdFindModeling =
 174       Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker,
 175                                                   "AggressiveStdFindModeling");
 176 }
 177
 178 bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
 179   return true;
 180 }
 181