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