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