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    {{{"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;
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 =
174      Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker,
175                                                  "AggressiveStdFindModeling");
176}
177
178bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
179  return true;
180}
181
182