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
evalCall(const CallEvent & Call,CheckerContext & C) const90 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
evalFind(CheckerContext & C,const CallExpr * CE) const103 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
Find(CheckerContext & C,const CallExpr * CE,unsigned paramNum) const129 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
registerSTLAlgorithmModeling(CheckerManager & Mgr)192 void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
193 auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();
194 Checker->AggressiveStdFindModeling =
195 Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker,
196 "AggressiveStdFindModeling");
197 }
198
shouldRegisterSTLAlgorithmModeling(const CheckerManager & mgr)199 bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
200 return true;
201 }
202
203