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 CallEvent &Call) const; 29 30 void Find(CheckerContext &C, const CallEvent &Call, unsigned paramNum) const; 31 32 using FnCheck = bool (STLAlgorithmModeling::*)(CheckerContext &, 33 const CallEvent &Call) 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, Call); 101 } 102 103 bool STLAlgorithmModeling::evalFind(CheckerContext &C, 104 const CallEvent &Call) const { 105 const auto *CE = dyn_cast<CallExpr>(Call.getOriginExpr()); 106 // std::find()-like functions either take their primary range in the first 107 // two parameters, or if the first parameter is "execution policy" then in 108 // the second and third. This means that the second parameter must always be 109 // an iterator. 110 if (!isIteratorType(CE->getArg(1)->getType())) 111 return false; 112 113 // If no "execution policy" parameter is used then the first argument is the 114 // beginning of the range. 115 if (isIteratorType(CE->getArg(0)->getType())) { 116 Find(C, Call, 0); 117 return true; 118 } 119 120 // If "execution policy" parameter is used then the second argument is the 121 // beginning of the range. 122 if (isIteratorType(CE->getArg(2)->getType())) { 123 Find(C, Call, 1); 124 return true; 125 } 126 127 return false; 128 } 129 130 void STLAlgorithmModeling::Find(CheckerContext &C, const CallEvent &Call, 131 unsigned paramNum) const { 132 const auto *CE = dyn_cast<CallExpr>(Call.getOriginExpr()); 133 const auto &Elem = Call.getCFGElementRef(); 134 auto State = C.getState(); 135 auto &SVB = C.getSValBuilder(); 136 const auto *LCtx = C.getLocationContext(); 137 138 SVal RetVal = SVB.conjureSymbolVal(nullptr, Elem, LCtx, C.blockCount()); 139 SVal Param = State->getSVal(CE->getArg(paramNum), LCtx); 140 141 auto StateFound = State->BindExpr(CE, LCtx, RetVal); 142 143 // If we have an iterator position for the range-begin argument then we can 144 // assume that in case of successful search the position of the found element 145 // is not ahead of it. 146 // FIXME: Reverse iterators 147 const auto *Pos = getIteratorPosition(State, Param); 148 if (Pos) { 149 StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(), 150 Elem, LCtx, C.blockCount()); 151 const auto *NewPos = getIteratorPosition(StateFound, RetVal); 152 assert(NewPos && "Failed to create new iterator position."); 153 154 SVal GreaterOrEqual = SVB.evalBinOp(StateFound, BO_GE, 155 nonloc::SymbolVal(NewPos->getOffset()), 156 nonloc::SymbolVal(Pos->getOffset()), 157 SVB.getConditionType()); 158 assert(isa<DefinedSVal>(GreaterOrEqual) && 159 "Symbol comparison must be a `DefinedSVal`"); 160 StateFound = StateFound->assume(GreaterOrEqual.castAs<DefinedSVal>(), true); 161 } 162 163 Param = State->getSVal(CE->getArg(paramNum + 1), LCtx); 164 165 // If we have an iterator position for the range-end argument then we can 166 // assume that in case of successful search the position of the found element 167 // is ahead of it. 168 // FIXME: Reverse iterators 169 Pos = getIteratorPosition(State, Param); 170 if (Pos) { 171 StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(), 172 Elem, LCtx, C.blockCount()); 173 const auto *NewPos = getIteratorPosition(StateFound, RetVal); 174 assert(NewPos && "Failed to create new iterator position."); 175 176 SVal Less = SVB.evalBinOp(StateFound, BO_LT, 177 nonloc::SymbolVal(NewPos->getOffset()), 178 nonloc::SymbolVal(Pos->getOffset()), 179 SVB.getConditionType()); 180 assert(isa<DefinedSVal>(Less) && 181 "Symbol comparison must be a `DefinedSVal`"); 182 StateFound = StateFound->assume(Less.castAs<DefinedSVal>(), true); 183 } 184 185 C.addTransition(StateFound); 186 187 if (AggressiveStdFindModeling) { 188 auto StateNotFound = State->BindExpr(CE, LCtx, Param); 189 C.addTransition(StateNotFound); 190 } 191 } 192 193 } // namespace 194 195 void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) { 196 auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>(); 197 Checker->AggressiveStdFindModeling = 198 Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker, 199 "AggressiveStdFindModeling"); 200 } 201 202 bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) { 203 return true; 204 } 205