27class STLAlgorithmModeling :
public Checker<eval::Call> {
28 bool evalFind(CheckerContext &
C,
const CallEvent &
Call)
const;
30 void Find(CheckerContext &
C,
const CallEvent &
Call,
unsigned paramNum)
const;
32 using FnCheck =
bool (STLAlgorithmModeling::*)(CheckerContext &,
33 const CallEvent &
Call)
const;
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},
83 STLAlgorithmModeling() =
default;
85 bool AggressiveStdFindModeling =
false;
87 bool evalCall(
const CallEvent &
Call, CheckerContext &
C)
const;
92 const auto *CE = dyn_cast_or_null<CallExpr>(
Call.getOriginExpr());
96 const FnCheck *Handler = Callbacks.lookup(
Call);
100 return (this->**Handler)(
C,
Call);
103bool STLAlgorithmModeling::evalFind(CheckerContext &
C,
104 const CallEvent &
Call)
const {
105 const auto *CE = dyn_cast<CallExpr>(
Call.getOriginExpr());
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();
138 SVal RetVal = SVB.conjureSymbolVal(
nullptr, Elem, LCtx,
C.blockCount());
139 SVal Param = State->getSVal(CE->getArg(paramNum), LCtx);
141 auto StateFound = State->BindExpr(CE, LCtx, RetVal);
150 Elem, LCtx,
C.blockCount());
152 assert(NewPos &&
"Failed to create new iterator position.");
154 SVal GreaterOrEqual = SVB.evalBinOp(StateFound, BO_GE,
155 nonloc::SymbolVal(NewPos->getOffset()),
156 nonloc::SymbolVal(Pos->getOffset()),
157 SVB.getConditionType());
159 "Symbol comparison must be a `DefinedSVal`");
160 StateFound = StateFound->assume(GreaterOrEqual.
castAs<DefinedSVal>(),
true);
163 Param = State->getSVal(CE->getArg(paramNum + 1), LCtx);
172 Elem, LCtx,
C.blockCount());
174 assert(NewPos &&
"Failed to create new iterator position.");
176 SVal
Less = SVB.evalBinOp(StateFound, BO_LT,
177 nonloc::SymbolVal(NewPos->getOffset()),
178 nonloc::SymbolVal(Pos->getOffset()),
179 SVB.getConditionType());
181 "Symbol comparison must be a `DefinedSVal`");
182 StateFound = StateFound->assume(
Less.castAs<DefinedSVal>(),
true);
185 C.addTransition(StateFound);
187 if (AggressiveStdFindModeling) {
188 auto StateNotFound = State->BindExpr(CE, LCtx, Param);
189 C.addTransition(StateNotFound);
195void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
197 Checker->AggressiveStdFindModeling =
199 "AggressiveStdFindModeling");
202bool ento::shouldRegisterSTLAlgorithmModeling(
const CheckerManager &mgr) {
Represents an abstract call to a function or method along a particular path.
const AnalyzerOptions & getAnalyzerOptions() const
CHECKER * registerChecker(AT &&...Args)
Register a single-part checker (derived from Checker): construct its singleton instance,...
Simple checker classes that implement one frontend (i.e.
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val, const MemRegion *Cont, ConstCFGElementRef Elem, const LocationContext *LCtx, unsigned blockCount)
const IteratorPosition * getIteratorPosition(ProgramStateRef State, SVal Val)
bool isIteratorType(const QualType &Type)
The JSON file list parser is used to communicate input to InstallAPI.
bool isa(CodeGen::Address addr)