clang  15.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 
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 
CallDescription.h
clang::ento::iterator::isIteratorType
bool isIteratorType(const QualType &Type)
Definition: Iterator.cpp:19
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:55
clang::index::SymbolRole::Call
@ Call
CallEvent.h
clang::ento::iterator::createIteratorPosition
ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, const MemRegion *Cont, const Stmt *S, const LocationContext *LCtx, unsigned blockCount)
Definition: Iterator.cpp:210
BuiltinCheckerRegistration.h
clang::CallExpr::getArg
Expr * getArg(unsigned Arg)
getArg - Return the specified argument.
Definition: Expr.h:2992
clang::ento::iterator::getIteratorPosition
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
Definition: Iterator.cpp:184
clang::ComparisonCategoryResult::Less
@ Less
bool
#define bool
Definition: stdbool.h:20
Iterator.h
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1126
CheckerContext.h
Checker.h
clang
Definition: CalledOnceCheck.h:17
clang::Expr::getType
QualType getType() const
Definition: Expr.h:141
clang::CallExpr
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2801