clang  14.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 
17 
18 #include "Iterator.h"
19 
20 using namespace clang;
21 using namespace ento;
22 using namespace iterator;
23 
24 namespace {
25 
26 class STLAlgorithmModeling : public Checker<eval::Call> {
27  bool evalFind(CheckerContext &C, const CallExpr *CE) const;
28 
29  void Find(CheckerContext &C, const CallExpr *CE, unsigned paramNum) const;
30 
31  using FnCheck = bool (STLAlgorithmModeling::*)(CheckerContext &,
32  const CallExpr *) const;
33 
34  const CallDescriptionMap<FnCheck> Callbacks = {
35  {{{"std", "find"}, 3}, &STLAlgorithmModeling::evalFind},
36  {{{"std", "find"}, 4}, &STLAlgorithmModeling::evalFind},
37  {{{"std", "find_if"}, 3}, &STLAlgorithmModeling::evalFind},
38  {{{"std", "find_if"}, 4}, &STLAlgorithmModeling::evalFind},
39  {{{"std", "find_if_not"}, 3}, &STLAlgorithmModeling::evalFind},
40  {{{"std", "find_if_not"}, 4}, &STLAlgorithmModeling::evalFind},
41  {{{"std", "find_first_of"}, 4}, &STLAlgorithmModeling::evalFind},
42  {{{"std", "find_first_of"}, 5}, &STLAlgorithmModeling::evalFind},
43  {{{"std", "find_first_of"}, 6}, &STLAlgorithmModeling::evalFind},
44  {{{"std", "find_end"}, 4}, &STLAlgorithmModeling::evalFind},
45  {{{"std", "find_end"}, 5}, &STLAlgorithmModeling::evalFind},
46  {{{"std", "find_end"}, 6}, &STLAlgorithmModeling::evalFind},
47  {{{"std", "lower_bound"}, 3}, &STLAlgorithmModeling::evalFind},
48  {{{"std", "lower_bound"}, 4}, &STLAlgorithmModeling::evalFind},
49  {{{"std", "upper_bound"}, 3}, &STLAlgorithmModeling::evalFind},
50  {{{"std", "upper_bound"}, 4}, &STLAlgorithmModeling::evalFind},
51  {{{"std", "search"}, 3}, &STLAlgorithmModeling::evalFind},
52  {{{"std", "search"}, 4}, &STLAlgorithmModeling::evalFind},
53  {{{"std", "search"}, 5}, &STLAlgorithmModeling::evalFind},
54  {{{"std", "search"}, 6}, &STLAlgorithmModeling::evalFind},
55  {{{"std", "search_n"}, 4}, &STLAlgorithmModeling::evalFind},
56  {{{"std", "search_n"}, 5}, &STLAlgorithmModeling::evalFind},
57  {{{"std", "search_n"}, 6}, &STLAlgorithmModeling::evalFind},
58  };
59 
60 public:
61  STLAlgorithmModeling() = default;
62 
63  bool AggressiveStdFindModeling;
64 
65  bool evalCall(const CallEvent &Call, CheckerContext &C) const;
66 }; //
67 
68 bool STLAlgorithmModeling::evalCall(const CallEvent &Call,
69  CheckerContext &C) const {
70  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
71  if (!CE)
72  return false;
73 
74  const FnCheck *Handler = Callbacks.lookup(Call);
75  if (!Handler)
76  return false;
77 
78  return (this->**Handler)(C, CE);
79 }
80 
81 bool STLAlgorithmModeling::evalFind(CheckerContext &C,
82  const CallExpr *CE) const {
83  // std::find()-like functions either take their primary range in the first
84  // two parameters, or if the first parameter is "execution policy" then in
85  // the second and third. This means that the second parameter must always be
86  // an iterator.
87  if (!isIteratorType(CE->getArg(1)->getType()))
88  return false;
89 
90  // If no "execution policy" parameter is used then the first argument is the
91  // beginning of the range.
92  if (isIteratorType(CE->getArg(0)->getType())) {
93  Find(C, CE, 0);
94  return true;
95  }
96 
97  // If "execution policy" parameter is used then the second argument is the
98  // beginning of the range.
99  if (isIteratorType(CE->getArg(2)->getType())) {
100  Find(C, CE, 1);
101  return true;
102  }
103 
104  return false;
105 }
106 
107 void STLAlgorithmModeling::Find(CheckerContext &C, const CallExpr *CE,
108  unsigned paramNum) const {
109  auto State = C.getState();
110  auto &SVB = C.getSValBuilder();
111  const auto *LCtx = C.getLocationContext();
112 
113  SVal RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
114  SVal Param = State->getSVal(CE->getArg(paramNum), LCtx);
115 
116  auto StateFound = State->BindExpr(CE, LCtx, RetVal);
117 
118  // If we have an iterator position for the range-begin argument then we can
119  // assume that in case of successful search the position of the found element
120  // is not ahead of it.
121  // FIXME: Reverse iterators
122  const auto *Pos = getIteratorPosition(State, Param);
123  if (Pos) {
124  StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
125  CE, LCtx, C.blockCount());
126  const auto *NewPos = getIteratorPosition(StateFound, RetVal);
127  assert(NewPos && "Failed to create new iterator position.");
128 
129  SVal GreaterOrEqual = SVB.evalBinOp(StateFound, BO_GE,
130  nonloc::SymbolVal(NewPos->getOffset()),
131  nonloc::SymbolVal(Pos->getOffset()),
132  SVB.getConditionType());
133  assert(GreaterOrEqual.getAs<DefinedSVal>() &&
134  "Symbol comparison must be a `DefinedSVal`");
135  StateFound = StateFound->assume(GreaterOrEqual.castAs<DefinedSVal>(), true);
136  }
137 
138  Param = State->getSVal(CE->getArg(paramNum + 1), LCtx);
139 
140  // If we have an iterator position for the range-end argument then we can
141  // assume that in case of successful search the position of the found element
142  // is ahead of it.
143  // FIXME: Reverse iterators
144  Pos = getIteratorPosition(State, Param);
145  if (Pos) {
146  StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
147  CE, LCtx, C.blockCount());
148  const auto *NewPos = getIteratorPosition(StateFound, RetVal);
149  assert(NewPos && "Failed to create new iterator position.");
150 
151  SVal Less = SVB.evalBinOp(StateFound, BO_LT,
152  nonloc::SymbolVal(NewPos->getOffset()),
153  nonloc::SymbolVal(Pos->getOffset()),
154  SVB.getConditionType());
155  assert(Less.getAs<DefinedSVal>() &&
156  "Symbol comparison must be a `DefinedSVal`");
157  StateFound = StateFound->assume(Less.castAs<DefinedSVal>(), true);
158  }
159 
160  C.addTransition(StateFound);
161 
162  if (AggressiveStdFindModeling) {
163  auto StateNotFound = State->BindExpr(CE, LCtx, Param);
164  C.addTransition(StateNotFound);
165  }
166 }
167 
168 } // namespace
169 
170 void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
171  auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();
172  Checker->AggressiveStdFindModeling =
173  Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker,
174  "AggressiveStdFindModeling");
175 }
176 
177 bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
178  return true;
179 }
180 
clang::ento::iterator::isIteratorType
bool isIteratorType(const QualType &Type)
Definition: Iterator.cpp:19
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:54
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:2986
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:15
Iterator.h
State
LineState State
Definition: UnwrappedLineFormatter.cpp:986
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:2795