Coverage Report

Created: 2020-10-24 06:27

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
Line
Count
Source (jump to first uncovered line)
1
//=== Iterator.cpp - Common functions for iterator checkers. -------*- 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 common functions to be used by the itertor checkers .
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "Iterator.h"
14
15
namespace clang {
16
namespace ento {
17
namespace iterator {
18
19
18.9k
bool isIteratorType(const QualType &Type) {
20
18.9k
  if (Type->isPointerType())
21
1.85k
    return true;
22
23
17.0k
  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
24
17.0k
  return isIterator(CRD);
25
17.0k
}
26
27
17.0k
bool isIterator(const CXXRecordDecl *CRD) {
28
17.0k
  if (!CRD)
29
9.43k
    return false;
30
31
7.63k
  const auto Name = CRD->getName();
32
7.63k
  if (!(Name.endswith_lower("iterator") || 
Name.endswith_lower("iter")209
||
33
209
        Name.endswith_lower("it")))
34
209
    return false;
35
36
7.42k
  bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
37
7.42k
       HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
38
142k
  for (const auto *Method : CRD->methods()) {
39
142k
    if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
40
26.0k
      if (Ctor->isCopyConstructor()) {
41
7.42k
        HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
42
7.42k
      }
43
26.0k
      continue;
44
26.0k
    }
45
116k
    if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
46
7.42k
      HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
47
7.42k
      continue;
48
7.42k
    }
49
109k
    if (Method->isCopyAssignmentOperator()) {
50
12
      HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
51
12
      continue;
52
12
    }
53
109k
    if (!Method->isOverloadedOperator())
54
7.41k
      continue;
55
101k
    const auto OPK = Method->getOverloadedOperator();
56
101k
    if (OPK == OO_PlusPlus) {
57
14.8k
      HasPreIncrOp = HasPreIncrOp || 
(Method->getNumParams() == 0)7.42k
;
58
14.8k
      HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
59
14.8k
      continue;
60
14.8k
    }
61
87.0k
    if (OPK == OO_Star) {
62
7.42k
      HasDerefOp = (Method->getNumParams() == 0);
63
7.42k
      continue;
64
7.42k
    }
65
87.0k
  }
66
67
7.42k
  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
68
7.42k
         HasPostIncrOp && HasDerefOp;
69
7.42k
}
70
71
46
bool isComparisonOperator(OverloadedOperatorKind OK) {
72
46
  return OK == OO_EqualEqual || 
OK == OO_ExclaimEqual42
||
OK == OO_Less32
||
73
32
         OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
74
46
}
75
76
208
bool isInsertCall(const FunctionDecl *Func) {
77
208
  const auto *IdInfo = Func->getIdentifier();
78
208
  if (!IdInfo)
79
36
    return false;
80
172
  if (Func->getNumParams() < 2 || 
Func->getNumParams() > 326
)
81
146
    return false;
82
26
  if (!isIteratorType(Func->getParamDecl(0)->getType()))
83
0
    return false;
84
26
  return IdInfo->getName() == "insert";
85
26
}
86
87
186
bool isEmplaceCall(const FunctionDecl *Func) {
88
186
  const auto *IdInfo = Func->getIdentifier();
89
186
  if (!IdInfo)
90
36
    return false;
91
150
  if (Func->getNumParams() < 2)
92
146
    return false;
93
4
  if (!isIteratorType(Func->getParamDecl(0)->getType()))
94
0
    return false;
95
4
  return IdInfo->getName() == "emplace";
96
4
}
97
98
222
bool isEraseCall(const FunctionDecl *Func) {
99
222
  const auto *IdInfo = Func->getIdentifier();
100
222
  if (!IdInfo)
101
36
    return false;
102
186
  if (Func->getNumParams() < 1 || 
Func->getNumParams() > 240
)
103
158
    return false;
104
28
  if (!isIteratorType(Func->getParamDecl(0)->getType()))
105
0
    return false;
106
28
  if (Func->getNumParams() == 2 &&
107
22
      !isIteratorType(Func->getParamDecl(1)->getType()))
108
14
    return false;
109
14
  return IdInfo->getName() == "erase";
110
14
}
111
112
208
bool isEraseAfterCall(const FunctionDecl *Func) {
113
208
  const auto *IdInfo = Func->getIdentifier();
114
208
  if (!IdInfo)
115
36
    return false;
116
172
  if (Func->getNumParams() < 1 || 
Func->getNumParams() > 226
)
117
158
    return false;
118
14
  if (!isIteratorType(Func->getParamDecl(0)->getType()))
119
0
    return false;
120
14
  if (Func->getNumParams() == 2 &&
121
14
      !isIteratorType(Func->getParamDecl(1)->getType()))
122
14
    return false;
123
0
  return IdInfo->getName() == "erase_after";
124
0
}
125
126
48
bool isAccessOperator(OverloadedOperatorKind OK) {
127
48
  return isDereferenceOperator(OK) || 
isIncrementOperator(OK)40
||
128
24
         isDecrementOperator(OK) || 
isRandomIncrOrDecrOperator(OK)16
;
129
48
}
130
131
20
bool isAccessOperator(UnaryOperatorKind OK) {
132
20
  return isDereferenceOperator(OK) || 
isIncrementOperator(OK)16
||
133
6
         isDecrementOperator(OK);
134
20
}
135
136
17
bool isAccessOperator(BinaryOperatorKind OK) {
137
17
  return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK);
138
17
}
139
140
94
bool isDereferenceOperator(OverloadedOperatorKind OK) {
141
94
  return OK == OO_Star || 
OK == OO_Arrow78
||
OK == OO_ArrowStar74
||
142
74
         OK == OO_Subscript;
143
94
}
144
145
235
bool isDereferenceOperator(UnaryOperatorKind OK) {
146
235
  return OK == UO_Deref;
147
235
}
148
149
114
bool isDereferenceOperator(BinaryOperatorKind OK) {
150
114
  return OK == BO_PtrMemI;
151
114
}
152
153
1.12k
bool isIncrementOperator(OverloadedOperatorKind OK) {
154
1.12k
  return OK == OO_PlusPlus;
155
1.12k
}
156
157
1.47k
bool isIncrementOperator(UnaryOperatorKind OK) {
158
1.47k
  return OK == UO_PreInc || 
OK == UO_PostInc1.15k
;
159
1.47k
}
160
161
739
bool isDecrementOperator(OverloadedOperatorKind OK) {
162
739
  return OK == OO_MinusMinus;
163
739
}
164
165
991
bool isDecrementOperator(UnaryOperatorKind OK) {
166
991
  return OK == UO_PreDec || 
OK == UO_PostDec801
;
167
991
}
168
169
1.17k
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
170
1.17k
  return OK == OO_Plus || 
OK == OO_PlusEqual1.12k
||
OK == OO_Minus839
||
171
795
         OK == OO_MinusEqual;
172
1.17k
}
173
174
622
bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) {
175
622
  return OK == BO_Add || 
OK == BO_AddAssign538
||
176
390
         OK == BO_Sub || 
OK == BO_SubAssign348
;
177
622
}
178
179
const ContainerData *getContainerData(ProgramStateRef State,
180
9.13k
                                      const MemRegion *Cont) {
181
9.13k
  return State->get<ContainerMap>(Cont);
182
9.13k
}
183
184
const IteratorPosition *getIteratorPosition(ProgramStateRef State,
185
29.6k
                                            const SVal &Val) {
186
29.6k
  if (auto Reg = Val.getAsRegion()) {
187
15.6k
    Reg = Reg->getMostDerivedObjectRegion();
188
15.6k
    return State->get<IteratorRegionMap>(Reg);
189
13.9k
  } else if (const auto Sym = Val.getAsSymbol()) {
190
736
    return State->get<IteratorSymbolMap>(Sym);
191
13.2k
  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
192
13.0k
    return State->get<IteratorRegionMap>(LCVal->getRegion());
193
13.0k
  }
194
169
  return nullptr;
195
169
}
196
197
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
198
10.6k
                                    const IteratorPosition &Pos) {
199
10.6k
  if (auto Reg = Val.getAsRegion()) {
200
6.73k
    Reg = Reg->getMostDerivedObjectRegion();
201
6.73k
    return State->set<IteratorRegionMap>(Reg, Pos);
202
3.94k
  } else if (const auto Sym = Val.getAsSymbol()) {
203
227
    return State->set<IteratorSymbolMap>(Sym, Pos);
204
3.71k
  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
205
3.70k
    return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
206
3.70k
  }
207
12
  return nullptr;
208
12
}
209
210
ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val,
211
                                       const MemRegion *Cont, const Stmt* S,
212
                                       const LocationContext *LCtx,
213
459
                                       unsigned blockCount) {
214
459
  auto &StateMgr = State->getStateManager();
215
459
  auto &SymMgr = StateMgr.getSymbolManager();
216
459
  auto &ACtx = StateMgr.getContext();
217
218
459
  auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount);
219
459
  State = assumeNoOverflow(State, Sym, 4);
220
459
  return setIteratorPosition(State, Val,
221
459
                             IteratorPosition::getPosition(Cont, Sym));
222
459
}
223
224
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter,
225
                                OverloadedOperatorKind Op,
226
1.55k
                                const SVal &Distance) {
227
1.55k
  const auto *Pos = getIteratorPosition(State, Iter);
228
1.55k
  if (!Pos)
229
145
    return nullptr;
230
231
1.41k
  auto &SymMgr = State->getStateManager().getSymbolManager();
232
1.41k
  auto &SVB = State->getStateManager().getSValBuilder();
233
1.41k
  auto &BVF = State->getStateManager().getBasicVals();
234
235
1.41k
  assert ((Op == OO_Plus || Op == OO_PlusEqual ||
236
1.41k
           Op == OO_Minus || Op == OO_MinusEqual) &&
237
1.41k
          "Advance operator must be one of +, -, += and -=.");
238
1.41k
  auto BinOp = (Op == OO_Plus || 
Op == OO_PlusEqual916
) ?
BO_Add896
:
BO_Sub518
;
239
1.41k
  const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
240
1.41k
  if (!IntDistOp)
241
10
    return nullptr;
242
243
  // For concrete integers we can calculate the new position
244
1.40k
  nonloc::ConcreteInt IntDist = *IntDistOp;
245
246
1.40k
  if (IntDist.getValue().isNegative()) {
247
218
    IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue()));
248
186
    BinOp = (BinOp == BO_Add) ? BO_Sub : 
BO_Add32
;
249
218
  }
250
1.40k
  const auto NewPos =
251
1.40k
    Pos->setTo(SVB.evalBinOp(State, BinOp,
252
1.40k
                             nonloc::SymbolVal(Pos->getOffset()),
253
1.40k
                             IntDist, SymMgr.getType(Pos->getOffset()))
254
1.40k
               .getAsSymbol());
255
1.40k
  return setIteratorPosition(State, Iter, NewPos);
256
1.40k
}
257
258
// This function tells the analyzer's engine that symbols produced by our
259
// checker, most notably iterator positions, are relatively small.
260
// A distance between items in the container should not be very large.
261
// By assuming that it is within around 1/8 of the address space,
262
// we can help the analyzer perform operations on these symbols
263
// without being afraid of integer overflows.
264
// FIXME: Should we provide it as an API, so that all checkers could use it?
265
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
266
2.77k
                                 long Scale) {
267
2.77k
  SValBuilder &SVB = State->getStateManager().getSValBuilder();
268
2.77k
  BasicValueFactory &BV = SVB.getBasicValueFactory();
269
270
2.77k
  QualType T = Sym->getType();
271
2.77k
  assert(T->isSignedIntegerOrEnumerationType());
272
2.77k
  APSIntType AT = BV.getAPSIntType(T);
273
274
2.77k
  ProgramStateRef NewState = State;
275
276
2.77k
  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
277
2.77k
  SVal IsCappedFromAbove =
278
2.77k
      SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
279
2.77k
                      nonloc::ConcreteInt(Max), SVB.getConditionType());
280
2.77k
  if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
281
2.77k
    NewState = NewState->assume(*DV, true);
282
2.77k
    if (!NewState)
283
0
      return State;
284
2.77k
  }
285
286
2.77k
  llvm::APSInt Min = -Max;
287
2.77k
  SVal IsCappedFromBelow =
288
2.77k
      SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
289
2.77k
                      nonloc::ConcreteInt(Min), SVB.getConditionType());
290
2.77k
  if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
291
2.77k
    NewState = NewState->assume(*DV, true);
292
2.77k
    if (!NewState)
293
0
      return State;
294
2.77k
  }
295
296
2.77k
  return NewState;
297
2.77k
}
298
299
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
300
2.09k
             BinaryOperator::Opcode Opc) {
301
2.09k
  return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
302
2.09k
}
303
304
bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
305
2.83k
             BinaryOperator::Opcode Opc) {
306
2.83k
  auto &SVB = State->getStateManager().getSValBuilder();
307
308
2.83k
  const auto comparison =
309
2.83k
    SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
310
311
2.83k
  assert(comparison.getAs<DefinedSVal>() &&
312
2.83k
    "Symbol comparison must be a `DefinedSVal`");
313
314
2.83k
  return !State->assume(comparison.castAs<DefinedSVal>(), false);
315
2.83k
}
316
317
} // namespace iterator
318
} // namespace ento
319
} // namespace clang