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
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>(Val: 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>(Val: 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(Type: CE->getArg(Arg: 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(Type: CE->getArg(Arg: 0)->getType())) {
116 Find(C, Call, paramNum: 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(Type: CE->getArg(Arg: 2)->getType())) {
123 Find(C, Call, paramNum: 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>(Val: 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(symbolTag: nullptr, elem: Elem, LCtx, count: C.blockCount());
139 SVal Param = State->getSVal(Ex: CE->getArg(Arg: paramNum), LCtx);
140
141 auto StateFound = State->BindExpr(S: CE, LCtx, V: 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, Val: Param);
148 if (Pos) {
149 StateFound = createIteratorPosition(State: StateFound, Val: RetVal, Cont: Pos->getContainer(),
150 Elem, LCtx, blockCount: C.blockCount());
151 const auto *NewPos = getIteratorPosition(State: StateFound, Val: RetVal);
152 assert(NewPos && "Failed to create new iterator position.");
153
154 SVal GreaterOrEqual = SVB.evalBinOp(state: StateFound, op: BO_GE,
155 lhs: nonloc::SymbolVal(NewPos->getOffset()),
156 rhs: nonloc::SymbolVal(Pos->getOffset()),
157 type: SVB.getConditionType());
158 assert(isa<DefinedSVal>(GreaterOrEqual) &&
159 "Symbol comparison must be a `DefinedSVal`");
160 StateFound = StateFound->assume(Cond: GreaterOrEqual.castAs<DefinedSVal>(), Assumption: true);
161 }
162
163 Param = State->getSVal(Ex: CE->getArg(Arg: 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, Val: Param);
170 if (Pos) {
171 StateFound = createIteratorPosition(State: StateFound, Val: RetVal, Cont: Pos->getContainer(),
172 Elem, LCtx, blockCount: C.blockCount());
173 const auto *NewPos = getIteratorPosition(State: StateFound, Val: RetVal);
174 assert(NewPos && "Failed to create new iterator position.");
175
176 SVal Less = SVB.evalBinOp(state: StateFound, op: BO_LT,
177 lhs: nonloc::SymbolVal(NewPos->getOffset()),
178 rhs: nonloc::SymbolVal(Pos->getOffset()),
179 type: SVB.getConditionType());
180 assert(isa<DefinedSVal>(Less) &&
181 "Symbol comparison must be a `DefinedSVal`");
182 StateFound = StateFound->assume(Cond: Less.castAs<DefinedSVal>(), Assumption: true);
183 }
184
185 C.addTransition(State: StateFound);
186
187 if (AggressiveStdFindModeling) {
188 auto StateNotFound = State->BindExpr(S: CE, LCtx, V: Param);
189 C.addTransition(State: StateNotFound);
190 }
191}
192
193} // namespace
194
195void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
196 auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();
197 Checker->AggressiveStdFindModeling =
198 Mgr.getAnalyzerOptions().getCheckerBooleanOption(C: Checker,
199 OptionName: "AggressiveStdFindModeling");
200}
201
202bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
203 return true;
204}
205