clang 19.0.0git
STLAlgorithmModeling.cpp
Go to the documentation of this file.
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
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 {{{"std", "find"}, 3}, &STLAlgorithmModeling::evalFind},
37 {{{"std", "find"}, 4}, &STLAlgorithmModeling::evalFind},
38 {{{"std", "find_if"}, 3}, &STLAlgorithmModeling::evalFind},
39 {{{"std", "find_if"}, 4}, &STLAlgorithmModeling::evalFind},
40 {{{"std", "find_if_not"}, 3}, &STLAlgorithmModeling::evalFind},
41 {{{"std", "find_if_not"}, 4}, &STLAlgorithmModeling::evalFind},
42 {{{"std", "find_first_of"}, 4}, &STLAlgorithmModeling::evalFind},
43 {{{"std", "find_first_of"}, 5}, &STLAlgorithmModeling::evalFind},
44 {{{"std", "find_first_of"}, 6}, &STLAlgorithmModeling::evalFind},
45 {{{"std", "find_end"}, 4}, &STLAlgorithmModeling::evalFind},
46 {{{"std", "find_end"}, 5}, &STLAlgorithmModeling::evalFind},
47 {{{"std", "find_end"}, 6}, &STLAlgorithmModeling::evalFind},
48 {{{"std", "lower_bound"}, 3}, &STLAlgorithmModeling::evalFind},
49 {{{"std", "lower_bound"}, 4}, &STLAlgorithmModeling::evalFind},
50 {{{"std", "upper_bound"}, 3}, &STLAlgorithmModeling::evalFind},
51 {{{"std", "upper_bound"}, 4}, &STLAlgorithmModeling::evalFind},
52 {{{"std", "search"}, 3}, &STLAlgorithmModeling::evalFind},
53 {{{"std", "search"}, 4}, &STLAlgorithmModeling::evalFind},
54 {{{"std", "search"}, 5}, &STLAlgorithmModeling::evalFind},
55 {{{"std", "search"}, 6}, &STLAlgorithmModeling::evalFind},
56 {{{"std", "search_n"}, 4}, &STLAlgorithmModeling::evalFind},
57 {{{"std", "search_n"}, 5}, &STLAlgorithmModeling::evalFind},
58 {{{"std", "search_n"}, 6}, &STLAlgorithmModeling::evalFind},
59 };
60
61public:
62 STLAlgorithmModeling() = default;
63
64 bool AggressiveStdFindModeling = false;
65
66 bool evalCall(const CallEvent &Call, CheckerContext &C) const;
67}; //
68
69bool STLAlgorithmModeling::evalCall(const CallEvent &Call,
70 CheckerContext &C) const {
71 const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
72 if (!CE)
73 return false;
74
75 const FnCheck *Handler = Callbacks.lookup(Call);
76 if (!Handler)
77 return false;
78
79 return (this->**Handler)(C, CE);
80}
81
82bool STLAlgorithmModeling::evalFind(CheckerContext &C,
83 const CallExpr *CE) const {
84 // std::find()-like functions either take their primary range in the first
85 // two parameters, or if the first parameter is "execution policy" then in
86 // the second and third. This means that the second parameter must always be
87 // an iterator.
88 if (!isIteratorType(CE->getArg(1)->getType()))
89 return false;
90
91 // If no "execution policy" parameter is used then the first argument is the
92 // beginning of the range.
93 if (isIteratorType(CE->getArg(0)->getType())) {
94 Find(C, CE, 0);
95 return true;
96 }
97
98 // If "execution policy" parameter is used then the second argument is the
99 // beginning of the range.
100 if (isIteratorType(CE->getArg(2)->getType())) {
101 Find(C, CE, 1);
102 return true;
103 }
104
105 return false;
106}
107
108void STLAlgorithmModeling::Find(CheckerContext &C, const CallExpr *CE,
109 unsigned paramNum) const {
110 auto State = C.getState();
111 auto &SVB = C.getSValBuilder();
112 const auto *LCtx = C.getLocationContext();
113
114 SVal RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
115 SVal Param = State->getSVal(CE->getArg(paramNum), LCtx);
116
117 auto StateFound = State->BindExpr(CE, LCtx, RetVal);
118
119 // If we have an iterator position for the range-begin argument then we can
120 // assume that in case of successful search the position of the found element
121 // is not ahead of it.
122 // FIXME: Reverse iterators
123 const auto *Pos = getIteratorPosition(State, Param);
124 if (Pos) {
125 StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
126 CE, LCtx, C.blockCount());
127 const auto *NewPos = getIteratorPosition(StateFound, RetVal);
128 assert(NewPos && "Failed to create new iterator position.");
129
130 SVal GreaterOrEqual = SVB.evalBinOp(StateFound, BO_GE,
131 nonloc::SymbolVal(NewPos->getOffset()),
132 nonloc::SymbolVal(Pos->getOffset()),
133 SVB.getConditionType());
134 assert(isa<DefinedSVal>(GreaterOrEqual) &&
135 "Symbol comparison must be a `DefinedSVal`");
136 StateFound = StateFound->assume(GreaterOrEqual.castAs<DefinedSVal>(), true);
137 }
138
139 Param = State->getSVal(CE->getArg(paramNum + 1), LCtx);
140
141 // If we have an iterator position for the range-end argument then we can
142 // assume that in case of successful search the position of the found element
143 // is ahead of it.
144 // FIXME: Reverse iterators
145 Pos = getIteratorPosition(State, Param);
146 if (Pos) {
147 StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
148 CE, LCtx, C.blockCount());
149 const auto *NewPos = getIteratorPosition(StateFound, RetVal);
150 assert(NewPos && "Failed to create new iterator position.");
151
152 SVal Less = SVB.evalBinOp(StateFound, BO_LT,
153 nonloc::SymbolVal(NewPos->getOffset()),
154 nonloc::SymbolVal(Pos->getOffset()),
155 SVB.getConditionType());
156 assert(isa<DefinedSVal>(Less) &&
157 "Symbol comparison must be a `DefinedSVal`");
158 StateFound = StateFound->assume(Less.castAs<DefinedSVal>(), true);
159 }
160
161 C.addTransition(StateFound);
162
163 if (AggressiveStdFindModeling) {
164 auto StateNotFound = State->BindExpr(CE, LCtx, Param);
165 C.addTransition(StateNotFound);
166 }
167}
168
169} // namespace
170
171void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
172 auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();
173 Checker->AggressiveStdFindModeling =
175 "AggressiveStdFindModeling");
176}
177
178bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
179 return true;
180}
181
bool getCheckerBooleanOption(StringRef CheckerName, StringRef OptionName, bool SearchInParents=false) const
Interprets an option's string value as a boolean.
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2820
Expr * getArg(unsigned Arg)
getArg - Return the specified argument.
Definition: Expr.h:3011
QualType getType() const
Definition: Expr.h:142
An immutable map from CallDescriptions to arbitrary data.
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:153
const AnalyzerOptions & getAnalyzerOptions() const
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:55
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
Definition: SVals.h:82
Represents symbolic expression that isn't a location.
Definition: SVals.h:284
const IteratorPosition * getIteratorPosition(ProgramStateRef State, SVal Val)
Definition: Iterator.cpp:184
bool isIteratorType(const QualType &Type)
Definition: Iterator.cpp:19
ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val, const MemRegion *Cont, const Stmt *S, const LocationContext *LCtx, unsigned blockCount)
Definition: Iterator.cpp:209
The JSON file list parser is used to communicate input to InstallAPI.
#define bool
Definition: stdbool.h:20