Coverage Report

Created: 2022-01-22 13:19

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- MismatchedIteratorChecker.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
// Defines a checker for mistakenly applying a foreign iterator on a container
10
// and for using iterators of two different containers in a context where
11
// iterators of the same container should be used.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17
#include "clang/StaticAnalyzer/Core/Checker.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
20
21
22
#include "Iterator.h"
23
24
using namespace clang;
25
using namespace ento;
26
using namespace iterator;
27
28
namespace {
29
30
class MismatchedIteratorChecker
31
  : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {
32
33
  std::unique_ptr<BugType> MismatchedBugType;
34
35
  void verifyMatch(CheckerContext &C, const SVal &Iter,
36
                   const MemRegion *Cont) const;
37
  void verifyMatch(CheckerContext &C, const SVal &Iter1,
38
                   const SVal &Iter2) const;
39
  void reportBug(const StringRef &Message, const SVal &Val1,
40
                 const SVal &Val2, CheckerContext &C,
41
                 ExplodedNode *ErrNode) const;
42
  void reportBug(const StringRef &Message, const SVal &Val,
43
                 const MemRegion *Reg, CheckerContext &C,
44
                 ExplodedNode *ErrNode) const;
45
46
public:
47
  MismatchedIteratorChecker();
48
49
  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
50
  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
51
52
};
53
54
} // namespace
55
56
2
MismatchedIteratorChecker::MismatchedIteratorChecker() {
57
2
  MismatchedBugType.reset(
58
2
      new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
59
2
                  /*SuppressOnSink=*/true));
60
2
}
61
62
void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
63
370
                                             CheckerContext &C) const {
64
  // Check for iterator mismatches
65
370
  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
66
370
  if (!Func)
67
0
    return;
68
69
370
  if (Func->isOverloadedOperator() &&
70
370
      
isComparisonOperator(Func->getOverloadedOperator())46
) {
71
    // Check for comparisons of iterators of different containers
72
14
    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
73
14
      if (Call.getNumArgs() < 1)
74
0
        return;
75
76
14
      if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
77
14
          !isIteratorType(Call.getArgExpr(0)->getType()))
78
0
        return;
79
80
14
      verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
81
14
    } else {
82
0
      if (Call.getNumArgs() < 2)
83
0
        return;
84
85
0
      if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
86
0
          !isIteratorType(Call.getArgExpr(1)->getType()))
87
0
        return;
88
89
0
      verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
90
0
    }
91
356
  } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
92
222
    const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
93
222
    if (!ContReg)
94
0
      return;
95
    // Check for erase, insert and emplace using iterator of another container
96
222
    if (isEraseCall(Func) || 
isEraseAfterCall(Func)208
) {
97
14
      verifyMatch(C, Call.getArgSVal(0),
98
14
                  InstCall->getCXXThisVal().getAsRegion());
99
14
      if (Call.getNumArgs() == 2) {
100
8
        verifyMatch(C, Call.getArgSVal(1),
101
8
                    InstCall->getCXXThisVal().getAsRegion());
102
8
      }
103
208
    } else if (isInsertCall(Func)) {
104
22
      verifyMatch(C, Call.getArgSVal(0),
105
22
                  InstCall->getCXXThisVal().getAsRegion());
106
22
      if (Call.getNumArgs() == 3 &&
107
22
          
isIteratorType(Call.getArgExpr(1)->getType())12
&&
108
22
          
isIteratorType(Call.getArgExpr(2)->getType())8
) {
109
8
        verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
110
8
      }
111
186
    } else if (isEmplaceCall(Func)) {
112
4
      verifyMatch(C, Call.getArgSVal(0),
113
4
                  InstCall->getCXXThisVal().getAsRegion());
114
4
    }
115
222
  } else 
if (134
isa<CXXConstructorCall>(&Call)134
) {
116
    // Check match of first-last iterator pair in a constructor of a container
117
108
    if (Call.getNumArgs() < 2)
118
104
      return;
119
120
4
    const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
121
4
    if (Ctr->getNumParams() < 2)
122
0
      return;
123
124
4
    if (Ctr->getParamDecl(0)->getName() != "first" ||
125
4
        Ctr->getParamDecl(1)->getName() != "last")
126
0
      return;
127
128
4
    if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
129
4
        !isIteratorType(Call.getArgExpr(1)->getType()))
130
0
      return;
131
132
4
    verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
133
26
  } else {
134
    // The main purpose of iterators is to abstract away from different
135
    // containers and provide a (maybe limited) uniform access to them.
136
    // This implies that any correctly written template function that
137
    // works on multiple containers using iterators takes different
138
    // template parameters for different containers. So we can safely
139
    // assume that passing iterators of different containers as arguments
140
    // whose type replaces the same template parameter is a bug.
141
    //
142
    // Example:
143
    // template<typename I1, typename I2>
144
    // void f(I1 first1, I1 last1, I2 first2, I2 last2);
145
    //
146
    // In this case the first two arguments to f() must be iterators must belong
147
    // to the same container and the last to also to the same container but
148
    // not necessarily to the same as the first two.
149
150
26
    const auto *Templ = Func->getPrimaryTemplate();
151
26
    if (!Templ)
152
8
      return;
153
154
18
    const auto *TParams = Templ->getTemplateParameters();
155
18
    const auto *TArgs = Func->getTemplateSpecializationArgs();
156
157
    // Iterate over all the template parameters
158
54
    for (size_t I = 0; I < TParams->size(); 
++I36
) {
159
36
      const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
160
36
      if (!TPDecl)
161
0
        continue;
162
163
36
      if (TPDecl->isParameterPack())
164
0
        continue;
165
166
36
      const auto TAType = TArgs->get(I).getAsType();
167
36
      if (!isIteratorType(TAType))
168
6
        continue;
169
170
30
      SVal LHS = UndefinedVal();
171
172
      // For every template parameter which is an iterator type in the
173
      // instantiation look for all functions' parameters' type by it and
174
      // check whether they belong to the same container
175
132
      for (auto J = 0U; J < Func->getNumParams(); 
++J102
) {
176
102
        const auto *Param = Func->getParamDecl(J);
177
102
        const auto *ParamType =
178
102
            Param->getType()->getAs<SubstTemplateTypeParmType>();
179
102
        if (!ParamType ||
180
102
            
ParamType->getReplacedParameter()->getDecl() != TPDecl96
)
181
48
          continue;
182
54
        if (LHS.isUndef()) {
183
30
          LHS = Call.getArgSVal(J);
184
30
        } else {
185
24
          verifyMatch(C, LHS, Call.getArgSVal(J));
186
24
        }
187
54
      }
188
30
    }
189
18
  }
190
370
}
191
192
void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
193
25
                                             CheckerContext &C) const {
194
25
  if (!BO->isComparisonOp())
195
16
    return;
196
197
9
  ProgramStateRef State = C.getState();
198
9
  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
199
9
  SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
200
9
  verifyMatch(C, LVal, RVal);
201
9
}
202
203
void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
204
48
                                            const MemRegion *Cont) const {
205
  // Verify match between a container and the container of an iterator
206
48
  Cont = Cont->getMostDerivedObjectRegion();
207
208
48
  if (const auto *ContSym = Cont->getSymbolicBase()) {
209
48
    if (isa<SymbolConjured>(ContSym->getSymbol()))
210
2
      return;
211
48
  }
212
213
46
  auto State = C.getState();
214
46
  const auto *Pos = getIteratorPosition(State, Iter);
215
46
  if (!Pos)
216
0
    return;
217
218
46
  const auto *IterCont = Pos->getContainer();
219
220
  // Skip symbolic regions based on conjured symbols. Two conjured symbols
221
  // may or may not be the same. For example, the same function can return
222
  // the same or a different container but we get different conjured symbols
223
  // for each call. This may cause false positives so omit them from the check.
224
46
  if (const auto *ContSym = IterCont->getSymbolicBase()) {
225
46
    if (isa<SymbolConjured>(ContSym->getSymbol()))
226
0
      return;
227
46
  }
228
229
46
  if (IterCont != Cont) {
230
20
    auto *N = C.generateNonFatalErrorNode(State);
231
20
    if (!N) {
232
2
      return;
233
2
    }
234
18
    reportBug("Container accessed using foreign iterator argument.",
235
18
                        Iter, Cont, C, N);
236
18
  }
237
46
}
238
239
void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,
240
                                            const SVal &Iter1,
241
59
                                            const SVal &Iter2) const {
242
  // Verify match between the containers of two iterators
243
59
  auto State = C.getState();
244
59
  const auto *Pos1 = getIteratorPosition(State, Iter1);
245
59
  if (!Pos1)
246
7
    return;
247
248
52
  const auto *IterCont1 = Pos1->getContainer();
249
250
  // Skip symbolic regions based on conjured symbols. Two conjured symbols
251
  // may or may not be the same. For example, the same function can return
252
  // the same or a different container but we get different conjured symbols
253
  // for each call. This may cause false positives so omit them from the check.
254
52
  if (const auto *ContSym = IterCont1->getSymbolicBase()) {
255
52
    if (isa<SymbolConjured>(ContSym->getSymbol()))
256
2
      return;
257
52
  }
258
259
50
  const auto *Pos2 = getIteratorPosition(State, Iter2);
260
50
  if (!Pos2)
261
0
    return;
262
263
50
  const auto *IterCont2 = Pos2->getContainer();
264
50
  if (const auto *ContSym = IterCont2->getSymbolicBase()) {
265
50
    if (isa<SymbolConjured>(ContSym->getSymbol()))
266
0
      return;
267
50
  }
268
269
50
  if (IterCont1 != IterCont2) {
270
16
    auto *N = C.generateNonFatalErrorNode(State);
271
16
    if (!N)
272
0
      return;
273
16
    reportBug("Iterators of different containers used where the "
274
16
                        "same container is expected.", Iter1, Iter2, C, N);
275
16
  }
276
50
}
277
278
void MismatchedIteratorChecker::reportBug(const StringRef &Message,
279
                                          const SVal &Val1,
280
                                          const SVal &Val2,
281
                                          CheckerContext &C,
282
16
                                          ExplodedNode *ErrNode) const {
283
16
  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
284
16
                                                    ErrNode);
285
16
  R->markInteresting(Val1);
286
16
  R->markInteresting(Val2);
287
16
  C.emitReport(std::move(R));
288
16
}
289
290
void MismatchedIteratorChecker::reportBug(const StringRef &Message,
291
                                          const SVal &Val, const MemRegion *Reg,
292
                                          CheckerContext &C,
293
18
                                          ExplodedNode *ErrNode) const {
294
18
  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
295
18
                                                    ErrNode);
296
18
  R->markInteresting(Val);
297
18
  R->markInteresting(Reg);
298
18
  C.emitReport(std::move(R));
299
18
}
300
301
2
void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
302
2
  mgr.registerChecker<MismatchedIteratorChecker>();
303
2
}
304
305
4
bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
306
4
  return true;
307
4
}