205 lines · 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-exception6//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 21using namespace clang;22using namespace ento;23using namespace iterator;24 25namespace {26 27class 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 82public:83 STLAlgorithmModeling() = default;84 85 bool AggressiveStdFindModeling = false;86 87 bool evalCall(const CallEvent &Call, CheckerContext &C) const;88}; //89 90bool 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 103bool 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 first107 // two parameters, or if the first parameter is "execution policy" then in108 // the second and third. This means that the second parameter must always be109 // 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 the114 // 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 the121 // 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 130void 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 can144 // assume that in case of successful search the position of the found element145 // is not ahead of it.146 // FIXME: Reverse iterators147 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 can166 // assume that in case of successful search the position of the found element167 // is ahead of it.168 // FIXME: Reverse iterators169 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} // namespace194 195void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {196 auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();197 Checker->AggressiveStdFindModeling =198 Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker,199 "AggressiveStdFindModeling");200}201 202bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {203 return true;204}205