Coverage Report

Created: 2021-04-17 09:42

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SValBuilder.cpp - Basic class for all SValBuilder implementations --===//
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
//  This file defines SValBuilder, the base class for all (complete) SValBuilder
10
//  implementations.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
15
#include "clang/AST/ASTContext.h"
16
#include "clang/AST/Decl.h"
17
#include "clang/AST/DeclCXX.h"
18
#include "clang/AST/ExprCXX.h"
19
#include "clang/AST/ExprObjC.h"
20
#include "clang/AST/Stmt.h"
21
#include "clang/AST/Type.h"
22
#include "clang/Basic/LLVM.h"
23
#include "clang/Analysis/AnalysisDeclContext.h"
24
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
25
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
26
#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
27
#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
28
#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
29
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
30
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
31
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
32
#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
33
#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
34
#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
35
#include "llvm/ADT/APSInt.h"
36
#include "llvm/ADT/None.h"
37
#include "llvm/ADT/Optional.h"
38
#include "llvm/Support/Casting.h"
39
#include "llvm/Support/Compiler.h"
40
#include <cassert>
41
#include <tuple>
42
43
using namespace clang;
44
using namespace ento;
45
46
//===----------------------------------------------------------------------===//
47
// Basic SVal creation.
48
//===----------------------------------------------------------------------===//
49
50
0
void SValBuilder::anchor() {}
51
52
9.05k
DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) {
53
9.05k
  if (Loc::isLocType(type))
54
3.94k
    return makeNull();
55
56
5.10k
  if (type->isIntegralOrEnumerationType())
57
5.08k
    return makeIntVal(0, type);
58
59
23
  if (type->isArrayType() || 
type->isRecordType()12
||
type->isVectorType()7
||
60
23
      
type->isAnyComplexType()7
)
61
16
    return makeCompoundVal(type, BasicVals.getEmptySValList());
62
63
  // FIXME: Handle floats.
64
7
  return UnknownVal();
65
23
}
66
67
NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
68
174k
                                const llvm::APSInt& rhs, QualType type) {
69
  // The Environment ensures we always get a persistent APSInt in
70
  // BasicValueFactory, so we don't need to get the APSInt from
71
  // BasicValueFactory again.
72
174k
  assert(lhs);
73
0
  assert(!Loc::isLocType(type));
74
0
  return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type));
75
174k
}
76
77
NonLoc SValBuilder::makeNonLoc(const llvm::APSInt& lhs,
78
                               BinaryOperator::Opcode op, const SymExpr *rhs,
79
199
                               QualType type) {
80
199
  assert(rhs);
81
0
  assert(!Loc::isLocType(type));
82
0
  return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type));
83
199
}
84
85
NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
86
9.94k
                               const SymExpr *rhs, QualType type) {
87
9.94k
  assert(lhs && rhs);
88
0
  assert(!Loc::isLocType(type));
89
0
  return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type));
90
9.94k
}
91
92
NonLoc SValBuilder::makeNonLoc(const SymExpr *operand,
93
45
                               QualType fromTy, QualType toTy) {
94
45
  assert(operand);
95
0
  assert(!Loc::isLocType(toTy));
96
0
  return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy));
97
45
}
98
99
19.4k
SVal SValBuilder::convertToArrayIndex(SVal val) {
100
19.4k
  if (val.isUnknownOrUndef())
101
0
    return val;
102
103
  // Common case: we have an appropriately sized integer.
104
19.4k
  if (Optional<nonloc::ConcreteInt> CI = val.getAs<nonloc::ConcreteInt>()) {
105
8.00k
    const llvm::APSInt& I = CI->getValue();
106
8.00k
    if (I.getBitWidth() == ArrayIndexWidth && 
I.isSigned()2.33k
)
107
1.22k
      return val;
108
8.00k
  }
109
110
18.2k
  return evalCast(val, ArrayIndexTy, QualType{});
111
19.4k
}
112
113
3.22k
nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){
114
3.22k
  return makeTruthVal(boolean->getValue());
115
3.22k
}
116
117
DefinedOrUnknownSVal
118
111k
SValBuilder::getRegionValueSymbolVal(const TypedValueRegion *region) {
119
111k
  QualType T = region->getValueType();
120
121
111k
  if (T->isNullPtrType())
122
0
    return makeZeroVal(T);
123
124
111k
  if (!SymbolManager::canSymbolicate(T))
125
2.19k
    return UnknownVal();
126
127
109k
  SymbolRef sym = SymMgr.getRegionValueSymbol(region);
128
129
109k
  if (Loc::isLocType(T))
130
50.8k
    return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
131
132
58.7k
  return nonloc::SymbolVal(sym);
133
109k
}
134
135
DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *SymbolTag,
136
                                                   const Expr *Ex,
137
                                                   const LocationContext *LCtx,
138
3.58k
                                                   unsigned Count) {
139
3.58k
  QualType T = Ex->getType();
140
141
3.58k
  if (T->isNullPtrType())
142
0
    return makeZeroVal(T);
143
144
  // Compute the type of the result. If the expression is not an R-value, the
145
  // result should be a location.
146
3.58k
  QualType ExType = Ex->getType();
147
3.58k
  if (Ex->isGLValue())
148
2
    T = LCtx->getAnalysisDeclContext()->getASTContext().getPointerType(ExType);
149
150
3.58k
  return conjureSymbolVal(SymbolTag, Ex, LCtx, T, Count);
151
3.58k
}
152
153
DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag,
154
                                                   const Expr *expr,
155
                                                   const LocationContext *LCtx,
156
                                                   QualType type,
157
123k
                                                   unsigned count) {
158
123k
  if (type->isNullPtrType())
159
1
    return makeZeroVal(type);
160
161
123k
  if (!SymbolManager::canSymbolicate(type))
162
6.95k
    return UnknownVal();
163
164
116k
  SymbolRef sym = SymMgr.conjureSymbol(expr, LCtx, type, count, symbolTag);
165
166
116k
  if (Loc::isLocType(type))
167
5.76k
    return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
168
169
110k
  return nonloc::SymbolVal(sym);
170
116k
}
171
172
DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const Stmt *stmt,
173
                                                   const LocationContext *LCtx,
174
                                                   QualType type,
175
671
                                                   unsigned visitCount) {
176
671
  if (type->isNullPtrType())
177
0
    return makeZeroVal(type);
178
179
671
  if (!SymbolManager::canSymbolicate(type))
180
47
    return UnknownVal();
181
182
624
  SymbolRef sym = SymMgr.conjureSymbol(stmt, LCtx, type, visitCount);
183
184
624
  if (Loc::isLocType(type))
185
17
    return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
186
187
607
  return nonloc::SymbolVal(sym);
188
624
}
189
190
DefinedOrUnknownSVal
191
SValBuilder::getConjuredHeapSymbolVal(const Expr *E,
192
                                      const LocationContext *LCtx,
193
1.37k
                                      unsigned VisitCount) {
194
1.37k
  QualType T = E->getType();
195
1.37k
  assert(Loc::isLocType(T));
196
0
  assert(SymbolManager::canSymbolicate(T));
197
1.37k
  if (T->isNullPtrType())
198
0
    return makeZeroVal(T);
199
200
1.37k
  SymbolRef sym = SymMgr.conjureSymbol(E, LCtx, T, VisitCount);
201
1.37k
  return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym));
202
1.37k
}
203
204
DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag,
205
                                              const MemRegion *region,
206
                                              const Expr *expr, QualType type,
207
                                              const LocationContext *LCtx,
208
597
                                              unsigned count) {
209
597
  assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type");
210
211
0
  SymbolRef sym =
212
597
      SymMgr.getMetadataSymbol(region, expr, type, LCtx, count, symbolTag);
213
214
597
  if (Loc::isLocType(type))
215
0
    return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
216
217
597
  return nonloc::SymbolVal(sym);
218
597
}
219
220
DefinedOrUnknownSVal
221
SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol,
222
13.0k
                                             const TypedValueRegion *region) {
223
13.0k
  QualType T = region->getValueType();
224
225
13.0k
  if (T->isNullPtrType())
226
10
    return makeZeroVal(T);
227
228
12.9k
  if (!SymbolManager::canSymbolicate(T))
229
100
    return UnknownVal();
230
231
12.8k
  SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region);
232
233
12.8k
  if (Loc::isLocType(T))
234
8.57k
    return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
235
236
4.31k
  return nonloc::SymbolVal(sym);
237
12.8k
}
238
239
64
DefinedSVal SValBuilder::getMemberPointer(const NamedDecl *ND) {
240
64
  assert(!ND || isa<CXXMethodDecl>(ND) || isa<FieldDecl>(ND) ||
241
64
         isa<IndirectFieldDecl>(ND));
242
243
64
  if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(ND)) {
244
    // Sema treats pointers to static member functions as have function pointer
245
    // type, so return a function pointer for the method.
246
    // We don't need to play a similar trick for static member fields
247
    // because these are represented as plain VarDecls and not FieldDecls
248
    // in the AST.
249
26
    if (MD->isStatic())
250
1
      return getFunctionPointer(MD);
251
26
  }
252
253
63
  return nonloc::PointerToMember(ND);
254
64
}
255
256
69.6k
DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) {
257
69.6k
  return loc::MemRegionVal(MemMgr.getFunctionCodeRegion(func));
258
69.6k
}
259
260
DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block,
261
                                         CanQualType locTy,
262
                                         const LocationContext *locContext,
263
384
                                         unsigned blockCount) {
264
384
  const BlockCodeRegion *BC =
265
384
    MemMgr.getBlockCodeRegion(block, locTy, locContext->getAnalysisDeclContext());
266
384
  const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext,
267
384
                                                        blockCount);
268
384
  return loc::MemRegionVal(BD);
269
384
}
270
271
/// Return a memory region for the 'this' object reference.
272
loc::MemRegionVal SValBuilder::getCXXThis(const CXXMethodDecl *D,
273
58.0k
                                          const StackFrameContext *SFC) {
274
58.0k
  return loc::MemRegionVal(
275
58.0k
      getRegionManager().getCXXThisRegion(D->getThisType(), SFC));
276
58.0k
}
277
278
/// Return a memory region for the 'this' object reference.
279
loc::MemRegionVal SValBuilder::getCXXThis(const CXXRecordDecl *D,
280
8.81k
                                          const StackFrameContext *SFC) {
281
8.81k
  const Type *T = D->getTypeForDecl();
282
8.81k
  QualType PT = getContext().getPointerType(QualType(T, 0));
283
8.81k
  return loc::MemRegionVal(getRegionManager().getCXXThisRegion(PT, SFC));
284
8.81k
}
285
286
84.3k
Optional<SVal> SValBuilder::getConstantVal(const Expr *E) {
287
84.3k
  E = E->IgnoreParens();
288
289
84.3k
  switch (E->getStmtClass()) {
290
  // Handle expressions that we treat differently from the AST's constant
291
  // evaluator.
292
80
  case Stmt::AddrLabelExprClass:
293
80
    return makeLoc(cast<AddrLabelExpr>(E));
294
295
114
  case Stmt::CXXScalarValueInitExprClass:
296
197
  case Stmt::ImplicitValueInitExprClass:
297
197
    return makeZeroVal(E->getType());
298
299
1.11k
  case Stmt::ObjCStringLiteralClass: {
300
1.11k
    const auto *SL = cast<ObjCStringLiteral>(E);
301
1.11k
    return makeLoc(getRegionManager().getObjCStringRegion(SL));
302
114
  }
303
304
7.89k
  case Stmt::StringLiteralClass: {
305
7.89k
    const auto *SL = cast<StringLiteral>(E);
306
7.89k
    return makeLoc(getRegionManager().getStringRegion(SL));
307
114
  }
308
309
900
  case Stmt::PredefinedExprClass: {
310
900
    const auto *PE = cast<PredefinedExpr>(E);
311
900
    assert(PE->getFunctionName() &&
312
900
           "Since we analyze only instantiated functions, PredefinedExpr "
313
900
           "should have a function name.");
314
0
    return makeLoc(getRegionManager().getStringRegion(PE->getFunctionName()));
315
114
  }
316
317
  // Fast-path some expressions to avoid the overhead of going through the AST's
318
  // constant evaluator
319
1.09k
  case Stmt::CharacterLiteralClass: {
320
1.09k
    const auto *C = cast<CharacterLiteral>(E);
321
1.09k
    return makeIntVal(C->getValue(), C->getType());
322
114
  }
323
324
3.22k
  case Stmt::CXXBoolLiteralExprClass:
325
3.22k
    return makeBoolVal(cast<CXXBoolLiteralExpr>(E));
326
327
9
  case Stmt::TypeTraitExprClass: {
328
9
    const auto *TE = cast<TypeTraitExpr>(E);
329
9
    return makeTruthVal(TE->getValue(), TE->getType());
330
114
  }
331
332
66.7k
  case Stmt::IntegerLiteralClass:
333
66.7k
    return makeIntVal(cast<IntegerLiteral>(E));
334
335
244
  case Stmt::ObjCBoolLiteralExprClass:
336
244
    return makeBoolVal(cast<ObjCBoolLiteralExpr>(E));
337
338
135
  case Stmt::CXXNullPtrLiteralExprClass:
339
135
    return makeNull();
340
341
235
  case Stmt::CStyleCastExprClass:
342
270
  case Stmt::CXXFunctionalCastExprClass:
343
305
  case Stmt::CXXConstCastExprClass:
344
340
  case Stmt::CXXReinterpretCastExprClass:
345
377
  case Stmt::CXXStaticCastExprClass:
346
838
  case Stmt::ImplicitCastExprClass: {
347
838
    const auto *CE = cast<CastExpr>(E);
348
838
    switch (CE->getCastKind()) {
349
416
    default:
350
416
      break;
351
416
    case CK_ArrayToPointerDecay:
352
314
    case CK_IntegralToPointer:
353
420
    case CK_NoOp:
354
422
    case CK_BitCast: {
355
422
      const Expr *SE = CE->getSubExpr();
356
422
      Optional<SVal> Val = getConstantVal(SE);
357
422
      if (!Val)
358
35
        return None;
359
387
      return evalCast(*Val, CE->getType(), SE->getType());
360
422
    }
361
838
    }
362
    // FALLTHROUGH
363
838
    
LLVM_FALLTHROUGH416
;
364
416
  }
365
366
  // If we don't have a special case, fall back to the AST's constant evaluator.
367
2.26k
  default: {
368
    // Don't try to come up with a value for materialized temporaries.
369
2.26k
    if (E->isGLValue())
370
0
      return None;
371
372
2.26k
    ASTContext &Ctx = getContext();
373
2.26k
    Expr::EvalResult Result;
374
2.26k
    if (E->EvaluateAsInt(Result, Ctx))
375
566
      return makeIntVal(Result.Val.getInt());
376
377
1.70k
    if (Loc::isLocType(E->getType()))
378
176
      if (E->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull))
379
163
        return makeNull();
380
381
1.53k
    return None;
382
1.70k
  }
383
84.3k
  }
384
84.3k
}
385
386
SVal SValBuilder::makeSymExprValNN(BinaryOperator::Opcode Op,
387
                                   NonLoc LHS, NonLoc RHS,
388
9.69k
                                   QualType ResultTy) {
389
9.69k
  SymbolRef symLHS = LHS.getAsSymbol();
390
9.69k
  SymbolRef symRHS = RHS.getAsSymbol();
391
392
  // TODO: When the Max Complexity is reached, we should conjure a symbol
393
  // instead of generating an Unknown value and propagate the taint info to it.
394
9.69k
  const unsigned MaxComp = StateMgr.getOwningEngine()
395
9.69k
                               .getAnalysisManager()
396
9.69k
                               .options.MaxSymbolComplexity;
397
398
9.69k
  if (symLHS && 
symRHS9.49k
&&
399
9.69k
      
(symLHS->computeComplexity() + symRHS->computeComplexity()) < MaxComp9.49k
)
400
9.39k
    return makeNonLoc(symLHS, Op, symRHS, ResultTy);
401
402
305
  if (symLHS && 
symLHS->computeComplexity() < MaxComp105
)
403
105
    if (Optional<nonloc::ConcreteInt> rInt = RHS.getAs<nonloc::ConcreteInt>())
404
0
      return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy);
405
406
305
  if (symRHS && 
symRHS->computeComplexity() < MaxComp302
)
407
302
    if (Optional<nonloc::ConcreteInt> lInt = LHS.getAs<nonloc::ConcreteInt>())
408
199
      return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy);
409
410
106
  return UnknownVal();
411
305
}
412
413
SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
414
96.5k
                            SVal lhs, SVal rhs, QualType type) {
415
96.5k
  if (lhs.isUndef() || 
rhs.isUndef()90.9k
)
416
5.87k
    return UndefinedVal();
417
418
90.7k
  if (lhs.isUnknown() || 
rhs.isUnknown()89.9k
)
419
808
    return UnknownVal();
420
421
89.8k
  if (lhs.getAs<nonloc::LazyCompoundVal>() ||
422
89.8k
      
rhs.getAs<nonloc::LazyCompoundVal>()89.6k
) {
423
202
    return UnknownVal();
424
202
  }
425
426
89.6k
  if (op == BinaryOperatorKind::BO_Cmp) {
427
    // We can't reason about C++20 spaceship operator yet.
428
    //
429
    // FIXME: Support C++20 spaceship operator.
430
    //        The main problem here is that the result is not integer.
431
1
    return UnknownVal();
432
1
  }
433
434
89.6k
  if (Optional<Loc> LV = lhs.getAs<Loc>()) {
435
30.6k
    if (Optional<Loc> RV = rhs.getAs<Loc>())
436
19.6k
      return evalBinOpLL(state, op, *LV, *RV, type);
437
438
11.0k
    return evalBinOpLN(state, op, *LV, rhs.castAs<NonLoc>(), type);
439
30.6k
  }
440
441
59.0k
  if (Optional<Loc> RV = rhs.getAs<Loc>()) {
442
    // Support pointer arithmetic where the addend is on the left
443
    // and the pointer on the right.
444
23
    assert(op == BO_Add);
445
446
    // Commute the operands.
447
0
    return evalBinOpLN(state, op, *RV, lhs.castAs<NonLoc>(), type);
448
23
  }
449
450
59.0k
  return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), rhs.castAs<NonLoc>(),
451
59.0k
                     type);
452
59.0k
}
453
454
ConditionTruthVal SValBuilder::areEqual(ProgramStateRef state, SVal lhs,
455
21.6k
                                        SVal rhs) {
456
21.6k
  return state->isNonNull(evalEQ(state, lhs, rhs));
457
21.6k
}
458
459
28.5k
SVal SValBuilder::evalEQ(ProgramStateRef state, SVal lhs, SVal rhs) {
460
28.5k
  return evalBinOp(state, BO_EQ, lhs, rhs, getConditionType());
461
28.5k
}
462
463
DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state,
464
                                         DefinedOrUnknownSVal lhs,
465
6.95k
                                         DefinedOrUnknownSVal rhs) {
466
6.95k
  return evalEQ(state, static_cast<SVal>(lhs), static_cast<SVal>(rhs))
467
6.95k
      .castAs<DefinedOrUnknownSVal>();
468
6.95k
}
469
470
/// Recursively check if the pointer types are equal modulo const, volatile,
471
/// and restrict qualifiers. Also, assume that all types are similar to 'void'.
472
/// Assumes the input types are canonical.
473
static bool shouldBeModeledWithNoOp(ASTContext &Context, QualType ToTy,
474
684k
                                                         QualType FromTy) {
475
1.38M
  while (Context.UnwrapSimilarTypes(ToTy, FromTy)) {
476
696k
    Qualifiers Quals1, Quals2;
477
696k
    ToTy = Context.getUnqualifiedArrayType(ToTy, Quals1);
478
696k
    FromTy = Context.getUnqualifiedArrayType(FromTy, Quals2);
479
480
    // Make sure that non-cvr-qualifiers the other qualifiers (e.g., address
481
    // spaces) are identical.
482
696k
    Quals1.removeCVRQualifiers();
483
696k
    Quals2.removeCVRQualifiers();
484
696k
    if (Quals1 != Quals2)
485
1
      return false;
486
696k
  }
487
488
  // If we are casting to void, the 'From' value can be used to represent the
489
  // 'To' value.
490
  //
491
  // FIXME: Doing this after unwrapping the types doesn't make any sense. A
492
  // cast from 'int**' to 'void**' is not special in the way that a cast from
493
  // 'int*' to 'void*' is.
494
684k
  if (ToTy->isVoidType())
495
3.00k
    return true;
496
497
681k
  if (ToTy != FromTy)
498
681k
    return false;
499
500
1
  return true;
501
681k
}
502
503
// Handles casts of type CK_IntegralCast.
504
// At the moment, this function will redirect to evalCast, except when the range
505
// of the original value is known to be greater than the max of the target type.
506
SVal SValBuilder::evalIntegralCast(ProgramStateRef state, SVal val,
507
32.9k
                                   QualType castTy, QualType originalTy) {
508
  // No truncations if target type is big enough.
509
32.9k
  if (getContext().getTypeSize(castTy) >= getContext().getTypeSize(originalTy))
510
30.4k
    return evalCast(val, castTy, originalTy);
511
512
2.47k
  SymbolRef se = val.getAsSymbol();
513
2.47k
  if (!se) // Let evalCast handle non symbolic expressions.
514
1.23k
    return evalCast(val, castTy, originalTy);
515
516
  // Find the maximum value of the target type.
517
1.23k
  APSIntType ToType(getContext().getTypeSize(castTy),
518
1.23k
                    castTy->isUnsignedIntegerType());
519
1.23k
  llvm::APSInt ToTypeMax = ToType.getMaxValue();
520
1.23k
  NonLoc ToTypeMaxVal =
521
1.23k
      makeIntVal(ToTypeMax.isUnsigned() ? 
ToTypeMax.getZExtValue()44
522
1.23k
                                        : 
ToTypeMax.getSExtValue()1.19k
,
523
1.23k
                 castTy)
524
1.23k
          .castAs<NonLoc>();
525
  // Check the range of the symbol being casted against the maximum value of the
526
  // target type.
527
1.23k
  NonLoc FromVal = val.castAs<NonLoc>();
528
1.23k
  QualType CmpTy = getConditionType();
529
1.23k
  NonLoc CompVal =
530
1.23k
      evalBinOpNN(state, BO_LE, FromVal, ToTypeMaxVal, CmpTy).castAs<NonLoc>();
531
1.23k
  ProgramStateRef IsNotTruncated, IsTruncated;
532
1.23k
  std::tie(IsNotTruncated, IsTruncated) = state->assume(CompVal);
533
1.23k
  if (!IsNotTruncated && 
IsTruncated21
) {
534
    // Symbol is truncated so we evaluate it as a cast.
535
21
    NonLoc CastVal = makeNonLoc(se, originalTy, castTy);
536
21
    return CastVal;
537
21
  }
538
1.21k
  return evalCast(val, castTy, originalTy);
539
1.23k
}
540
541
//===----------------------------------------------------------------------===//
542
// Cast methods.
543
// `evalCast` is the main method
544
// `evalCastKind` and `evalCastSubKind` are helpers
545
//===----------------------------------------------------------------------===//
546
547
/// Cast a given SVal to another SVal using given QualType's.
548
/// \param V -- SVal that should be casted.
549
/// \param CastTy -- QualType that V should be casted according to.
550
/// \param OriginalTy -- QualType which is associated to V. It provides
551
/// additional information about what type the cast performs from.
552
/// \returns the most appropriate casted SVal.
553
/// Note: Many cases don't use an exact OriginalTy. It can be extracted
554
/// from SVal or the cast can performs unconditionaly. Always pass OriginalTy!
555
/// It can be crucial in certain cases and generates different results.
556
/// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy
557
/// only. This behavior is uncertain and should be improved.
558
1.10M
SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) {
559
1.10M
  if (CastTy.isNull())
560
0
    return V;
561
562
1.10M
  CastTy = Context.getCanonicalType(CastTy);
563
564
1.10M
  const bool IsUnknownOriginalType = OriginalTy.isNull();
565
1.10M
  if (!IsUnknownOriginalType) {
566
688k
    OriginalTy = Context.getCanonicalType(OriginalTy);
567
568
688k
    if (CastTy == OriginalTy)
569
4.32k
      return V;
570
571
    // FIXME: Move this check to the most appropriate
572
    // evalCastKind/evalCastSubKind function. For const casts, casts to void,
573
    // just propagate the value.
574
684k
    if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType())
575
684k
      if (shouldBeModeledWithNoOp(Context, Context.getPointerType(CastTy),
576
684k
                                  Context.getPointerType(OriginalTy)))
577
3.00k
        return V;
578
684k
  }
579
580
  // Cast SVal according to kinds.
581
1.10M
  switch (V.getBaseKind()) {
582
75.8k
  case SVal::UndefinedValKind:
583
75.8k
    return evalCastKind(V.castAs<UndefinedVal>(), CastTy, OriginalTy);
584
10.4k
  case SVal::UnknownValKind:
585
10.4k
    return evalCastKind(V.castAs<UnknownVal>(), CastTy, OriginalTy);
586
820k
  case SVal::LocKind:
587
820k
    return evalCastKind(V.castAs<Loc>(), CastTy, OriginalTy);
588
193k
  case SVal::NonLocKind:
589
193k
    return evalCastKind(V.castAs<NonLoc>(), CastTy, OriginalTy);
590
1.10M
  }
591
592
1.10M
  
llvm_unreachable0
("Unknown SVal kind");
593
1.10M
}
594
595
SVal SValBuilder::evalCastKind(UndefinedVal V, QualType CastTy,
596
75.8k
                               QualType OriginalTy) {
597
75.8k
  return V;
598
75.8k
}
599
600
SVal SValBuilder::evalCastKind(UnknownVal V, QualType CastTy,
601
10.4k
                               QualType OriginalTy) {
602
10.4k
  return V;
603
10.4k
}
604
605
820k
SVal SValBuilder::evalCastKind(Loc V, QualType CastTy, QualType OriginalTy) {
606
820k
  switch (V.getSubKind()) {
607
39.9k
  case loc::ConcreteIntKind:
608
39.9k
    return evalCastSubKind(V.castAs<loc::ConcreteInt>(), CastTy, OriginalTy);
609
31
  case loc::GotoLabelKind:
610
31
    return evalCastSubKind(V.castAs<loc::GotoLabel>(), CastTy, OriginalTy);
611
781k
  case loc::MemRegionValKind:
612
781k
    return evalCastSubKind(V.castAs<loc::MemRegionVal>(), CastTy, OriginalTy);
613
820k
  }
614
615
820k
  
llvm_unreachable0
("Unknown SVal kind");
616
820k
}
617
618
193k
SVal SValBuilder::evalCastKind(NonLoc V, QualType CastTy, QualType OriginalTy) {
619
193k
  switch (V.getSubKind()) {
620
10
  case nonloc::CompoundValKind:
621
10
    return evalCastSubKind(V.castAs<nonloc::CompoundVal>(), CastTy, OriginalTy);
622
54.4k
  case nonloc::ConcreteIntKind:
623
54.4k
    return evalCastSubKind(V.castAs<nonloc::ConcreteInt>(), CastTy, OriginalTy);
624
9
  case nonloc::LazyCompoundValKind:
625
9
    return evalCastSubKind(V.castAs<nonloc::LazyCompoundVal>(), CastTy,
626
9
                           OriginalTy);
627
253
  case nonloc::LocAsIntegerKind:
628
253
    return evalCastSubKind(V.castAs<nonloc::LocAsInteger>(), CastTy,
629
253
                           OriginalTy);
630
138k
  case nonloc::SymbolValKind:
631
138k
    return evalCastSubKind(V.castAs<nonloc::SymbolVal>(), CastTy, OriginalTy);
632
84
  case nonloc::PointerToMemberKind:
633
84
    return evalCastSubKind(V.castAs<nonloc::PointerToMember>(), CastTy,
634
84
                           OriginalTy);
635
193k
  }
636
637
193k
  
llvm_unreachable0
("Unknown SVal kind");
638
193k
}
639
640
SVal SValBuilder::evalCastSubKind(loc::ConcreteInt V, QualType CastTy,
641
39.9k
                                  QualType OriginalTy) {
642
  // Pointer to bool.
643
39.9k
  if (CastTy->isBooleanType())
644
1.41k
    return makeTruthVal(V.getValue().getBoolValue(), CastTy);
645
646
  // Pointer to integer.
647
38.5k
  if (CastTy->isIntegralOrEnumerationType()) {
648
30
    llvm::APSInt Value = V.getValue();
649
30
    BasicVals.getAPSIntType(CastTy).apply(Value);
650
30
    return makeIntVal(Value);
651
30
  }
652
653
  // Pointer to any pointer.
654
38.4k
  if (Loc::isLocType(CastTy))
655
38.4k
    return V;
656
657
  // Pointer to whatever else.
658
8
  return UnknownVal();
659
38.4k
}
660
661
SVal SValBuilder::evalCastSubKind(loc::GotoLabel V, QualType CastTy,
662
31
                                  QualType OriginalTy) {
663
  // Pointer to bool.
664
31
  if (CastTy->isBooleanType())
665
    // Labels are always true.
666
14
    return makeTruthVal(true, CastTy);
667
668
  // Pointer to integer.
669
17
  if (CastTy->isIntegralOrEnumerationType()) {
670
0
    const unsigned BitWidth = Context.getIntWidth(CastTy);
671
0
    return makeLocAsInteger(V, BitWidth);
672
0
  }
673
674
17
  const bool IsUnknownOriginalType = OriginalTy.isNull();
675
17
  if (!IsUnknownOriginalType) {
676
    // Array to pointer.
677
15
    if (isa<ArrayType>(OriginalTy))
678
0
      if (CastTy->isPointerType() || CastTy->isReferenceType())
679
0
        return UnknownVal();
680
15
  }
681
682
  // Pointer to any pointer.
683
17
  if (Loc::isLocType(CastTy))
684
17
    return V;
685
686
  // Pointer to whatever else.
687
0
  return UnknownVal();
688
17
}
689
690
44.1k
static bool hasSameUnqualifiedPointeeType(QualType ty1, QualType ty2) {
691
44.1k
  return ty1->getPointeeType().getCanonicalType().getTypePtr() ==
692
44.1k
         ty2->getPointeeType().getCanonicalType().getTypePtr();
693
44.1k
}
694
695
SVal SValBuilder::evalCastSubKind(loc::MemRegionVal V, QualType CastTy,
696
781k
                                  QualType OriginalTy) {
697
  // Pointer to bool.
698
781k
  if (CastTy->isBooleanType()) {
699
604k
    const MemRegion *R = V.getRegion();
700
604k
    if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
701
132k
      if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl()))
702
132k
        if (FD->isWeak())
703
          // FIXME: Currently we are using an extent symbol here,
704
          // because there are no generic region address metadata
705
          // symbols to use, only content metadata.
706
27
          return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR));
707
708
604k
    if (const SymbolicRegion *SymR = R->getSymbolicBase())
709
100k
      return makeNonLoc(SymR->getSymbol(), BO_NE,
710
100k
                        BasicVals.getZeroWithPtrWidth(), CastTy);
711
    // Non-symbolic memory regions are always true.
712
504k
    return makeTruthVal(true, CastTy);
713
604k
  }
714
715
176k
  const bool IsUnknownOriginalType = OriginalTy.isNull();
716
  // Try to cast to array
717
176k
  const auto *ArrayTy =
718
176k
      IsUnknownOriginalType
719
176k
          ? 
nullptr157k
720
176k
          : 
dyn_cast<ArrayType>(OriginalTy.getCanonicalType())18.4k
;
721
722
  // Pointer to integer.
723
176k
  if (CastTy->isIntegralOrEnumerationType()) {
724
149
    SVal Val = V;
725
    // Array to integer.
726
149
    if (ArrayTy) {
727
      // We will always decay to a pointer.
728
0
      QualType ElemTy = ArrayTy->getElementType();
729
0
      Val = StateMgr.ArrayToPointer(V, ElemTy);
730
      // FIXME: Keep these here for now in case we decide soon that we
731
      // need the original decayed type.
732
      //    QualType elemTy = cast<ArrayType>(originalTy)->getElementType();
733
      //    QualType pointerTy = C.getPointerType(elemTy);
734
0
    }
735
149
    const unsigned BitWidth = Context.getIntWidth(CastTy);
736
149
    return makeLocAsInteger(Val.castAs<Loc>(), BitWidth);
737
149
  }
738
739
  // Pointer to pointer.
740
176k
  if (Loc::isLocType(CastTy)) {
741
742
176k
    if (IsUnknownOriginalType) {
743
      // When retrieving symbolic pointer and expecting a non-void pointer,
744
      // wrap them into element regions of the expected type if necessary.
745
      // It is necessary to make sure that the retrieved value makes sense,
746
      // because there's no other cast in the AST that would tell us to cast
747
      // it to the correct pointer type. We might need to do that for non-void
748
      // pointers as well.
749
      // FIXME: We really need a single good function to perform casts for us
750
      // correctly every time we need it.
751
157k
      if (CastTy->isPointerType() && 
!CastTy->isVoidPointerType()113k
) {
752
108k
        const MemRegion *R = V.getRegion();
753
108k
        if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
754
44.1k
          QualType SRTy = SR->getSymbol()->getType();
755
44.1k
          if (!hasSameUnqualifiedPointeeType(SRTy, CastTy)) {
756
13
            R = StateMgr.getStoreManager().castRegion(SR, CastTy);
757
13
            return loc::MemRegionVal(R);
758
13
          }
759
44.1k
        }
760
108k
      }
761
157k
      return V;
762
157k
    }
763
764
18.3k
    if (OriginalTy->isIntegralOrEnumerationType() ||
765
18.3k
        OriginalTy->isBlockPointerType() || 
OriginalTy->isFunctionPointerType()18.2k
)
766
133
      return V;
767
768
    // Array to pointer.
769
18.1k
    if (ArrayTy) {
770
      // Are we casting from an array to a pointer?  If so just pass on
771
      // the decayed value.
772
9.33k
      if (CastTy->isPointerType() || 
CastTy->isReferenceType()0
) {
773
        // We will always decay to a pointer.
774
9.33k
        QualType ElemTy = ArrayTy->getElementType();
775
9.33k
        return StateMgr.ArrayToPointer(V, ElemTy);
776
9.33k
      }
777
      // Are we casting from an array to an integer?  If so, cast the decayed
778
      // pointer value to an integer.
779
0
      assert(CastTy->isIntegralOrEnumerationType());
780
0
    }
781
782
    // Other pointer to pointer.
783
8.85k
    assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
784
8.85k
           CastTy->isReferenceType());
785
786
    // We get a symbolic function pointer for a dereference of a function
787
    // pointer, but it is of function type. Example:
788
789
    //  struct FPRec {
790
    //    void (*my_func)(int * x);
791
    //  };
792
    //
793
    //  int bar(int x);
794
    //
795
    //  int f1_a(struct FPRec* foo) {
796
    //    int x;
797
    //    (*foo->my_func)(&x);
798
    //    return bar(x)+1; // no-warning
799
    //  }
800
801
    // Get the result of casting a region to a different type.
802
0
    const MemRegion *R = V.getRegion();
803
8.85k
    if ((R = StateMgr.getStoreManager().castRegion(R, CastTy)))
804
8.84k
      return loc::MemRegionVal(R);
805
8.85k
  }
806
807
  // Pointer to whatever else.
808
  // FIXME: There can be gross cases where one casts the result of a
809
  // function (that returns a pointer) to some other value that happens to
810
  // fit within that pointer value.  We currently have no good way to model
811
  // such operations.  When this happens, the underlying operation is that
812
  // the caller is reasoning about bits.  Conceptually we are layering a
813
  // "view" of a location on top of those bits.  Perhaps we need to be more
814
  // lazy about mutual possible views, even on an SVal?  This may be
815
  // necessary for bit-level reasoning as well.
816
24
  return UnknownVal();
817
176k
}
818
819
SVal SValBuilder::evalCastSubKind(nonloc::CompoundVal V, QualType CastTy,
820
10
                                  QualType OriginalTy) {
821
  // Compound to whatever.
822
10
  return UnknownVal();
823
10
}
824
825
SVal SValBuilder::evalCastSubKind(nonloc::ConcreteInt V, QualType CastTy,
826
54.4k
                                  QualType OriginalTy) {
827
54.4k
  auto CastedValue = [V, CastTy, this]() {
828
52.3k
    llvm::APSInt Value = V.getValue();
829
52.3k
    BasicVals.getAPSIntType(CastTy).apply(Value);
830
52.3k
    return Value;
831
52.3k
  };
832
833
  // Integer to bool.
834
54.4k
  if (CastTy->isBooleanType())
835
1.91k
    return makeTruthVal(V.getValue().getBoolValue(), CastTy);
836
837
  // Integer to pointer.
838
52.5k
  if (CastTy->isIntegralOrEnumerationType())
839
51.9k
    return makeIntVal(CastedValue());
840
841
  // Integer to pointer.
842
585
  if (Loc::isLocType(CastTy))
843
364
    return makeIntLocVal(CastedValue());
844
845
  // Pointer to whatever else.
846
221
  return UnknownVal();
847
585
}
848
849
SVal SValBuilder::evalCastSubKind(nonloc::LazyCompoundVal V, QualType CastTy,
850
9
                                  QualType OriginalTy) {
851
  // Compound to whatever.
852
9
  return UnknownVal();
853
9
}
854
855
SVal SValBuilder::evalCastSubKind(nonloc::LocAsInteger V, QualType CastTy,
856
253
                                  QualType OriginalTy) {
857
253
  Loc L = V.getLoc();
858
859
  // Pointer as integer to bool.
860
253
  if (CastTy->isBooleanType())
861
    // Pass to Loc function.
862
1
    return evalCastKind(L, CastTy, OriginalTy);
863
864
252
  const bool IsUnknownOriginalType = OriginalTy.isNull();
865
  // Pointer as integer to pointer.
866
252
  if (!IsUnknownOriginalType && 
Loc::isLocType(CastTy)39
&&
867
252
      
OriginalTy->isIntegralOrEnumerationType()30
) {
868
30
    if (const MemRegion *R = L.getAsRegion())
869
30
      if ((R = StateMgr.getStoreManager().castRegion(R, CastTy)))
870
30
        return loc::MemRegionVal(R);
871
0
    return L;
872
30
  }
873
874
  // Pointer as integer with region to integer/pointer.
875
222
  const MemRegion *R = L.getAsRegion();
876
222
  if (!IsUnknownOriginalType && 
R9
) {
877
9
    if (CastTy->isIntegralOrEnumerationType())
878
7
      return evalCastSubKind(loc::MemRegionVal(R), CastTy, OriginalTy);
879
880
2
    if (Loc::isLocType(CastTy)) {
881
0
      assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() ||
882
0
             CastTy->isReferenceType());
883
      // Delegate to store manager to get the result of casting a region to a
884
      // different type. If the MemRegion* returned is NULL, this expression
885
      // Evaluates to UnknownVal.
886
0
      if ((R = StateMgr.getStoreManager().castRegion(R, CastTy)))
887
0
        return loc::MemRegionVal(R);
888
0
    }
889
213
  } else {
890
213
    if (Loc::isLocType(CastTy)) {
891
18
      if (IsUnknownOriginalType)
892
18
        return evalCastSubKind(loc::MemRegionVal(R), CastTy, OriginalTy);
893
0
      return L;
894
18
    }
895
896
195
    SymbolRef SE = nullptr;
897
195
    if (R) {
898
195
      if (const SymbolicRegion *SR =
899
195
              dyn_cast<SymbolicRegion>(R->StripCasts())) {
900
161
        SE = SR->getSymbol();
901
161
      }
902
195
    }
903
904
195
    if (!CastTy->isFloatingType() || 
!SE0
||
SE->getType()->isFloatingType()0
) {
905
      // FIXME: Correctly support promotions/truncations.
906
195
      const unsigned CastSize = Context.getIntWidth(CastTy);
907
195
      if (CastSize == V.getNumBits())
908
194
        return V;
909
910
1
      return makeLocAsInteger(L, CastSize);
911
195
    }
912
195
  }
913
914
  // Pointer as integer to whatever else.
915
2
  return UnknownVal();
916
222
}
917
918
SVal SValBuilder::evalCastSubKind(nonloc::SymbolVal V, QualType CastTy,
919
138k
                                  QualType OriginalTy) {
920
138k
  SymbolRef SE = V.getSymbol();
921
922
138k
  const bool IsUnknownOriginalType = OriginalTy.isNull();
923
  // Symbol to bool.
924
138k
  if (!IsUnknownOriginalType && 
CastTy->isBooleanType()44.1k
) {
925
    // Non-float to bool.
926
23.3k
    if (Loc::isLocType(OriginalTy) ||
927
23.3k
        OriginalTy->isIntegralOrEnumerationType() ||
928
23.3k
        
OriginalTy->isMemberPointerType()2
) {
929
23.3k
      BasicValueFactory &BVF = getBasicValueFactory();
930
23.3k
      return makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy);
931
23.3k
    }
932
115k
  } else {
933
    // Symbol to integer, float.
934
115k
    QualType T = Context.getCanonicalType(SE->getType());
935
    // If types are the same or both are integers, ignore the cast.
936
    // FIXME: Remove this hack when we support symbolic truncation/extension.
937
    // HACK: If both castTy and T are integers, ignore the cast.  This is
938
    // not a permanent solution.  Eventually we want to precisely handle
939
    // extension/truncation of symbolic integers.  This prevents us from losing
940
    // precision when we assign 'x = y' and 'y' is symbolic and x and y are
941
    // different integer types.
942
115k
    if (haveSameType(T, CastTy))
943
114k
      return V;
944
185
    if (!Loc::isLocType(CastTy))
945
39
      if (!IsUnknownOriginalType || 
!CastTy->isFloatingType()16
||
946
39
          
T->isFloatingType()15
)
947
24
        return makeNonLoc(SE, T, CastTy);
948
185
  }
949
950
  // Symbol to pointer and whatever else.
951
163
  return UnknownVal();
952
138k
}
953
954
SVal SValBuilder::evalCastSubKind(nonloc::PointerToMember V, QualType CastTy,
955
84
                                  QualType OriginalTy) {
956
  // Member pointer to whatever.
957
84
  return V;
958
84
}