Coverage Report

Created: 2020-09-19 12:23

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp
Line
Count
Source (jump to first uncovered line)
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/CallEvent.h"
16
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
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
2
  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
1.42k
                                    CheckerContext &C) const {
70
1.42k
  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
71
1.42k
  if (!CE)
72
184
    return false;
73
1.23k
74
1.23k
  const FnCheck *Handler = Callbacks.lookup(Call);
75
1.23k
  if (!Handler)
76
1.18k
    return false;
77
54
78
54
  return (this->**Handler)(C, CE);
79
54
}
80
81
bool STLAlgorithmModeling::evalFind(CheckerContext &C,
82
54
                                    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
54
  if (!isIteratorType(CE->getArg(1)->getType()))
88
0
    return false;
89
54
90
  // If no "execution policy" parameter is used then the first argument is the
91
  // beginning of the range.
92
54
  if (isIteratorType(CE->getArg(0)->getType())) {
93
32
    Find(C, CE, 0);
94
32
    return true;
95
32
  }
96
22
97
  // If "execution policy" parameter is used then the second argument is the
98
  // beginning of the range.
99
22
  if (isIteratorType(CE->getArg(2)->getType())) {
100
22
    Find(C, CE, 1);
101
22
    return true;
102
22
  }
103
0
104
0
  return false;
105
0
}
106
107
void STLAlgorithmModeling::Find(CheckerContext &C, const CallExpr *CE,
108
54
                                unsigned paramNum) const {
109
54
  auto State = C.getState();
110
54
  auto &SVB = C.getSValBuilder();
111
54
  const auto *LCtx = C.getLocationContext();
112
54
113
54
  SVal RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
114
54
  SVal Param = State->getSVal(CE->getArg(paramNum), LCtx);
115
54
116
54
  auto StateFound = State->BindExpr(CE, LCtx, RetVal);
117
54
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
54
  const auto *Pos = getIteratorPosition(State, Param);
123
54
  if (Pos) {
124
54
    StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
125
54
                                        CE, LCtx, C.blockCount());
126
54
    const auto *NewPos = getIteratorPosition(StateFound, RetVal);
127
54
    assert(NewPos && "Failed to create new iterator position.");
128
54
129
54
    SVal GreaterOrEqual = SVB.evalBinOp(StateFound, BO_GE,
130
54
                                        nonloc::SymbolVal(NewPos->getOffset()),
131
54
                                        nonloc::SymbolVal(Pos->getOffset()),
132
54
                                        SVB.getConditionType());
133
54
    assert(GreaterOrEqual.getAs<DefinedSVal>() &&
134
54
           "Symbol comparison must be a `DefinedSVal`");
135
54
    StateFound = StateFound->assume(GreaterOrEqual.castAs<DefinedSVal>(), true);
136
54
  }
137
54
138
54
  Param = State->getSVal(CE->getArg(paramNum + 1), LCtx);
139
54
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
54
  Pos = getIteratorPosition(State, Param);
145
54
  if (Pos) {
146
54
    StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
147
54
                                        CE, LCtx, C.blockCount());
148
54
    const auto *NewPos = getIteratorPosition(StateFound, RetVal);
149
54
    assert(NewPos && "Failed to create new iterator position.");
150
54
151
54
    SVal Less = SVB.evalBinOp(StateFound, BO_LT,
152
54
                              nonloc::SymbolVal(NewPos->getOffset()),
153
54
                              nonloc::SymbolVal(Pos->getOffset()),
154
54
                              SVB.getConditionType());
155
54
    assert(Less.getAs<DefinedSVal>() &&
156
54
           "Symbol comparison must be a `DefinedSVal`");
157
54
    StateFound = StateFound->assume(Less.castAs<DefinedSVal>(), true);
158
54
  }
159
54
160
54
  C.addTransition(StateFound);
161
54
162
54
  if (AggressiveStdFindModeling) {
163
27
    auto StateNotFound = State->BindExpr(CE, LCtx, Param);
164
27
    C.addTransition(StateNotFound);
165
27
  }
166
54
}
167
168
} // namespace
169
170
2
void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
171
2
  auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();
172
2
  Checker->AggressiveStdFindModeling =
173
2
      Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker,
174
2
                                                  "AggressiveStdFindModeling");
175
2
}
176
177
4
bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
178
4
  return true;
179
4
}
180