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     {{{"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 
61 public:
62   STLAlgorithmModeling() = default;
63 
64   bool AggressiveStdFindModeling;
65 
66   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
67 }; //
68 
69 bool 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 
82 bool 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 
108 void 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 
171 void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
172   auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();
173   Checker->AggressiveStdFindModeling =
174       Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker,
175                                                   "AggressiveStdFindModeling");
176 }
177 
178 bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
179   return true;
180 }
181 
182