1//=-- ExprEngineC.cpp - ExprEngine support for C expressions ----*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines ExprEngine's support for C expressions.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/AST/ExprCXX.h"
15#include "clang/StaticAnalyzer/Core/CheckerManager.h"
16#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
17
18using namespace clang;
19using namespace ento;
20using llvm::APSInt;
21
22void ExprEngine::VisitBinaryOperator(const BinaryOperator* B,
23                                     ExplodedNode *Pred,
24                                     ExplodedNodeSet &Dst) {
25
26  Expr *LHS = B->getLHS()->IgnoreParens();
27  Expr *RHS = B->getRHS()->IgnoreParens();
28
29  // FIXME: Prechecks eventually go in ::Visit().
30  ExplodedNodeSet CheckedSet;
31  ExplodedNodeSet Tmp2;
32  getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, B, *this);
33
34  // With both the LHS and RHS evaluated, process the operation itself.
35  for (ExplodedNodeSet::iterator it=CheckedSet.begin(), ei=CheckedSet.end();
36         it != ei; ++it) {
37
38    ProgramStateRef state = (*it)->getState();
39    const LocationContext *LCtx = (*it)->getLocationContext();
40    SVal LeftV = state->getSVal(LHS, LCtx);
41    SVal RightV = state->getSVal(RHS, LCtx);
42
43    BinaryOperator::Opcode Op = B->getOpcode();
44
45    if (Op == BO_Assign) {
46      // EXPERIMENTAL: "Conjured" symbols.
47      // FIXME: Handle structs.
48      if (RightV.isUnknown()) {
49        unsigned Count = currBldrCtx->blockCount();
50        RightV = svalBuilder.conjureSymbolVal(0, B->getRHS(), LCtx, Count);
51      }
52      // Simulate the effects of a "store":  bind the value of the RHS
53      // to the L-Value represented by the LHS.
54      SVal ExprVal = B->isGLValue() ? LeftV : RightV;
55      evalStore(Tmp2, B, LHS, *it, state->BindExpr(B, LCtx, ExprVal),
56                LeftV, RightV);
57      continue;
58    }
59
60    if (!B->isAssignmentOp()) {
61      StmtNodeBuilder Bldr(*it, Tmp2, *currBldrCtx);
62
63      if (B->isAdditiveOp()) {
64        // If one of the operands is a location, conjure a symbol for the other
65        // one (offset) if it's unknown so that memory arithmetic always
66        // results in an ElementRegion.
67        // TODO: This can be removed after we enable history tracking with
68        // SymSymExpr.
69        unsigned Count = currBldrCtx->blockCount();
70        if (LeftV.getAs<Loc>() &&
71            RHS->getType()->isIntegralOrEnumerationType() &&
72            RightV.isUnknown()) {
73          RightV = svalBuilder.conjureSymbolVal(RHS, LCtx, RHS->getType(),
74                                                Count);
75        }
76        if (RightV.getAs<Loc>() &&
77            LHS->getType()->isIntegralOrEnumerationType() &&
78            LeftV.isUnknown()) {
79          LeftV = svalBuilder.conjureSymbolVal(LHS, LCtx, LHS->getType(),
80                                               Count);
81        }
82      }
83
84      // Process non-assignments except commas or short-circuited
85      // logical expressions (LAnd and LOr).
86      SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType());
87      if (Result.isUnknown()) {
88        Bldr.generateNode(B, *it, state);
89        continue;
90      }
91
92      state = state->BindExpr(B, LCtx, Result);
93      Bldr.generateNode(B, *it, state);
94      continue;
95    }
96
97    assert (B->isCompoundAssignmentOp());
98
99    switch (Op) {
100      default:
101        llvm_unreachable("Invalid opcode for compound assignment.");
102      case BO_MulAssign: Op = BO_Mul; break;
103      case BO_DivAssign: Op = BO_Div; break;
104      case BO_RemAssign: Op = BO_Rem; break;
105      case BO_AddAssign: Op = BO_Add; break;
106      case BO_SubAssign: Op = BO_Sub; break;
107      case BO_ShlAssign: Op = BO_Shl; break;
108      case BO_ShrAssign: Op = BO_Shr; break;
109      case BO_AndAssign: Op = BO_And; break;
110      case BO_XorAssign: Op = BO_Xor; break;
111      case BO_OrAssign:  Op = BO_Or;  break;
112    }
113
114    // Perform a load (the LHS).  This performs the checks for
115    // null dereferences, and so on.
116    ExplodedNodeSet Tmp;
117    SVal location = LeftV;
118    evalLoad(Tmp, B, LHS, *it, state, location);
119
120    for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E;
121         ++I) {
122
123      state = (*I)->getState();
124      const LocationContext *LCtx = (*I)->getLocationContext();
125      SVal V = state->getSVal(LHS, LCtx);
126
127      // Get the computation type.
128      QualType CTy =
129        cast<CompoundAssignOperator>(B)->getComputationResultType();
130      CTy = getContext().getCanonicalType(CTy);
131
132      QualType CLHSTy =
133        cast<CompoundAssignOperator>(B)->getComputationLHSType();
134      CLHSTy = getContext().getCanonicalType(CLHSTy);
135
136      QualType LTy = getContext().getCanonicalType(LHS->getType());
137
138      // Promote LHS.
139      V = svalBuilder.evalCast(V, CLHSTy, LTy);
140
141      // Compute the result of the operation.
142      SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy),
143                                         B->getType(), CTy);
144
145      // EXPERIMENTAL: "Conjured" symbols.
146      // FIXME: Handle structs.
147
148      SVal LHSVal;
149
150      if (Result.isUnknown()) {
151        // The symbolic value is actually for the type of the left-hand side
152        // expression, not the computation type, as this is the value the
153        // LValue on the LHS will bind to.
154        LHSVal = svalBuilder.conjureSymbolVal(0, B->getRHS(), LCtx, LTy,
155                                              currBldrCtx->blockCount());
156        // However, we need to convert the symbol to the computation type.
157        Result = svalBuilder.evalCast(LHSVal, CTy, LTy);
158      }
159      else {
160        // The left-hand side may bind to a different value then the
161        // computation type.
162        LHSVal = svalBuilder.evalCast(Result, LTy, CTy);
163      }
164
165      // In C++, assignment and compound assignment operators return an
166      // lvalue.
167      if (B->isGLValue())
168        state = state->BindExpr(B, LCtx, location);
169      else
170        state = state->BindExpr(B, LCtx, Result);
171
172      evalStore(Tmp2, B, LHS, *I, state, location, LHSVal);
173    }
174  }
175
176  // FIXME: postvisits eventually go in ::Visit()
177  getCheckerManager().runCheckersForPostStmt(Dst, Tmp2, B, *this);
178}
179
180void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
181                                ExplodedNodeSet &Dst) {
182
183  CanQualType T = getContext().getCanonicalType(BE->getType());
184
185  // Get the value of the block itself.
186  SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T,
187                                       Pred->getLocationContext());
188
189  ProgramStateRef State = Pred->getState();
190
191  // If we created a new MemRegion for the block, we should explicitly bind
192  // the captured variables.
193  if (const BlockDataRegion *BDR =
194      dyn_cast_or_null<BlockDataRegion>(V.getAsRegion())) {
195
196    BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
197                                              E = BDR->referenced_vars_end();
198
199    for (; I != E; ++I) {
200      const MemRegion *capturedR = I.getCapturedRegion();
201      const MemRegion *originalR = I.getOriginalRegion();
202      if (capturedR != originalR) {
203        SVal originalV = State->getSVal(loc::MemRegionVal(originalR));
204        State = State->bindLoc(loc::MemRegionVal(capturedR), originalV);
205      }
206    }
207  }
208
209  ExplodedNodeSet Tmp;
210  StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
211  Bldr.generateNode(BE, Pred,
212                    State->BindExpr(BE, Pred->getLocationContext(), V),
213                    0, ProgramPoint::PostLValueKind);
214
215  // FIXME: Move all post/pre visits to ::Visit().
216  getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this);
217}
218
219void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,
220                           ExplodedNode *Pred, ExplodedNodeSet &Dst) {
221
222  ExplodedNodeSet dstPreStmt;
223  getCheckerManager().runCheckersForPreStmt(dstPreStmt, Pred, CastE, *this);
224
225  if (CastE->getCastKind() == CK_LValueToRValue) {
226    for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end();
227         I!=E; ++I) {
228      ExplodedNode *subExprNode = *I;
229      ProgramStateRef state = subExprNode->getState();
230      const LocationContext *LCtx = subExprNode->getLocationContext();
231      evalLoad(Dst, CastE, CastE, subExprNode, state, state->getSVal(Ex, LCtx));
232    }
233    return;
234  }
235
236  // All other casts.
237  QualType T = CastE->getType();
238  QualType ExTy = Ex->getType();
239
240  if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE))
241    T = ExCast->getTypeAsWritten();
242
243  StmtNodeBuilder Bldr(dstPreStmt, Dst, *currBldrCtx);
244  for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end();
245       I != E; ++I) {
246
247    Pred = *I;
248    ProgramStateRef state = Pred->getState();
249    const LocationContext *LCtx = Pred->getLocationContext();
250
251    switch (CastE->getCastKind()) {
252      case CK_LValueToRValue:
253        llvm_unreachable("LValueToRValue casts handled earlier.");
254      case CK_ToVoid:
255        continue;
256        // The analyzer doesn't do anything special with these casts,
257        // since it understands retain/release semantics already.
258      case CK_ARCProduceObject:
259      case CK_ARCConsumeObject:
260      case CK_ARCReclaimReturnedObject:
261      case CK_ARCExtendBlockObject: // Fall-through.
262      case CK_CopyAndAutoreleaseBlockObject:
263        // The analyser can ignore atomic casts for now, although some future
264        // checkers may want to make certain that you're not modifying the same
265        // value through atomic and nonatomic pointers.
266      case CK_AtomicToNonAtomic:
267      case CK_NonAtomicToAtomic:
268        // True no-ops.
269      case CK_NoOp:
270      case CK_ConstructorConversion:
271      case CK_UserDefinedConversion:
272      case CK_FunctionToPointerDecay:
273      case CK_BuiltinFnToFnPtr: {
274        // Copy the SVal of Ex to CastE.
275        ProgramStateRef state = Pred->getState();
276        const LocationContext *LCtx = Pred->getLocationContext();
277        SVal V = state->getSVal(Ex, LCtx);
278        state = state->BindExpr(CastE, LCtx, V);
279        Bldr.generateNode(CastE, Pred, state);
280        continue;
281      }
282      case CK_MemberPointerToBoolean:
283        // FIXME: For now, member pointers are represented by void *.
284        // FALLTHROUGH
285      case CK_Dependent:
286      case CK_ArrayToPointerDecay:
287      case CK_BitCast:
288      case CK_IntegralCast:
289      case CK_NullToPointer:
290      case CK_IntegralToPointer:
291      case CK_PointerToIntegral:
292      case CK_PointerToBoolean:
293      case CK_IntegralToBoolean:
294      case CK_IntegralToFloating:
295      case CK_FloatingToIntegral:
296      case CK_FloatingToBoolean:
297      case CK_FloatingCast:
298      case CK_FloatingRealToComplex:
299      case CK_FloatingComplexToReal:
300      case CK_FloatingComplexToBoolean:
301      case CK_FloatingComplexCast:
302      case CK_FloatingComplexToIntegralComplex:
303      case CK_IntegralRealToComplex:
304      case CK_IntegralComplexToReal:
305      case CK_IntegralComplexToBoolean:
306      case CK_IntegralComplexCast:
307      case CK_IntegralComplexToFloatingComplex:
308      case CK_CPointerToObjCPointerCast:
309      case CK_BlockPointerToObjCPointerCast:
310      case CK_AnyPointerToBlockPointerCast:
311      case CK_ObjCObjectLValueCast:
312      case CK_ZeroToOCLEvent:
313      case CK_LValueBitCast: {
314        // Delegate to SValBuilder to process.
315        SVal V = state->getSVal(Ex, LCtx);
316        V = svalBuilder.evalCast(V, T, ExTy);
317        state = state->BindExpr(CastE, LCtx, V);
318        Bldr.generateNode(CastE, Pred, state);
319        continue;
320      }
321      case CK_DerivedToBase:
322      case CK_UncheckedDerivedToBase: {
323        // For DerivedToBase cast, delegate to the store manager.
324        SVal val = state->getSVal(Ex, LCtx);
325        val = getStoreManager().evalDerivedToBase(val, CastE);
326        state = state->BindExpr(CastE, LCtx, val);
327        Bldr.generateNode(CastE, Pred, state);
328        continue;
329      }
330      // Handle C++ dyn_cast.
331      case CK_Dynamic: {
332        SVal val = state->getSVal(Ex, LCtx);
333
334        // Compute the type of the result.
335        QualType resultType = CastE->getType();
336        if (CastE->isGLValue())
337          resultType = getContext().getPointerType(resultType);
338
339        bool Failed = false;
340
341        // Check if the value being cast evaluates to 0.
342        if (val.isZeroConstant())
343          Failed = true;
344        // Else, evaluate the cast.
345        else
346          val = getStoreManager().evalDynamicCast(val, T, Failed);
347
348        if (Failed) {
349          if (T->isReferenceType()) {
350            // A bad_cast exception is thrown if input value is a reference.
351            // Currently, we model this, by generating a sink.
352            Bldr.generateSink(CastE, Pred, state);
353            continue;
354          } else {
355            // If the cast fails on a pointer, bind to 0.
356            state = state->BindExpr(CastE, LCtx, svalBuilder.makeNull());
357          }
358        } else {
359          // If we don't know if the cast succeeded, conjure a new symbol.
360          if (val.isUnknown()) {
361            DefinedOrUnknownSVal NewSym =
362              svalBuilder.conjureSymbolVal(0, CastE, LCtx, resultType,
363                                           currBldrCtx->blockCount());
364            state = state->BindExpr(CastE, LCtx, NewSym);
365          } else
366            // Else, bind to the derived region value.
367            state = state->BindExpr(CastE, LCtx, val);
368        }
369        Bldr.generateNode(CastE, Pred, state);
370        continue;
371      }
372      case CK_NullToMemberPointer: {
373        // FIXME: For now, member pointers are represented by void *.
374        SVal V = svalBuilder.makeNull();
375        state = state->BindExpr(CastE, LCtx, V);
376        Bldr.generateNode(CastE, Pred, state);
377        continue;
378      }
379      // Various C++ casts that are not handled yet.
380      case CK_ToUnion:
381      case CK_BaseToDerived:
382      case CK_BaseToDerivedMemberPointer:
383      case CK_DerivedToBaseMemberPointer:
384      case CK_ReinterpretMemberPointer:
385      case CK_VectorSplat: {
386        // Recover some path-sensitivty by conjuring a new value.
387        QualType resultType = CastE->getType();
388        if (CastE->isGLValue())
389          resultType = getContext().getPointerType(resultType);
390        SVal result = svalBuilder.conjureSymbolVal(0, CastE, LCtx,
391                                                   resultType,
392                                                   currBldrCtx->blockCount());
393        state = state->BindExpr(CastE, LCtx, result);
394        Bldr.generateNode(CastE, Pred, state);
395        continue;
396      }
397    }
398  }
399}
400
401void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,
402                                          ExplodedNode *Pred,
403                                          ExplodedNodeSet &Dst) {
404  StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
405
406  ProgramStateRef State = Pred->getState();
407  const LocationContext *LCtx = Pred->getLocationContext();
408
409  const Expr *Init = CL->getInitializer();
410  SVal V = State->getSVal(CL->getInitializer(), LCtx);
411
412  if (isa<CXXConstructExpr>(Init)) {
413    // No work needed. Just pass the value up to this expression.
414  } else {
415    assert(isa<InitListExpr>(Init));
416    Loc CLLoc = State->getLValue(CL, LCtx);
417    State = State->bindLoc(CLLoc, V);
418
419    // Compound literal expressions are a GNU extension in C++.
420    // Unlike in C, where CLs are lvalues, in C++ CLs are prvalues,
421    // and like temporary objects created by the functional notation T()
422    // CLs are destroyed at the end of the containing full-expression.
423    // HOWEVER, an rvalue of array type is not something the analyzer can
424    // reason about, since we expect all regions to be wrapped in Locs.
425    // So we treat array CLs as lvalues as well, knowing that they will decay
426    // to pointers as soon as they are used.
427    if (CL->isGLValue() || CL->getType()->isArrayType())
428      V = CLLoc;
429  }
430
431  B.generateNode(CL, Pred, State->BindExpr(CL, LCtx, V));
432}
433
434void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
435                               ExplodedNodeSet &Dst) {
436  // Assumption: The CFG has one DeclStmt per Decl.
437  const VarDecl *VD = dyn_cast_or_null<VarDecl>(*DS->decl_begin());
438
439  if (!VD) {
440    //TODO:AZ: remove explicit insertion after refactoring is done.
441    Dst.insert(Pred);
442    return;
443  }
444
445  // FIXME: all pre/post visits should eventually be handled by ::Visit().
446  ExplodedNodeSet dstPreVisit;
447  getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, DS, *this);
448
449  StmtNodeBuilder B(dstPreVisit, Dst, *currBldrCtx);
450  for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
451       I!=E; ++I) {
452    ExplodedNode *N = *I;
453    ProgramStateRef state = N->getState();
454    const LocationContext *LC = N->getLocationContext();
455
456    // Decls without InitExpr are not initialized explicitly.
457    if (const Expr *InitEx = VD->getInit()) {
458
459      // Note in the state that the initialization has occurred.
460      ExplodedNode *UpdatedN = N;
461      SVal InitVal = state->getSVal(InitEx, LC);
462
463      if (isa<CXXConstructExpr>(InitEx->IgnoreImplicit())) {
464        // We constructed the object directly in the variable.
465        // No need to bind anything.
466        B.generateNode(DS, UpdatedN, state);
467      } else {
468        // We bound the temp obj region to the CXXConstructExpr. Now recover
469        // the lazy compound value when the variable is not a reference.
470        if (AMgr.getLangOpts().CPlusPlus && VD->getType()->isRecordType() &&
471            !VD->getType()->isReferenceType()) {
472          if (Optional<loc::MemRegionVal> M =
473                  InitVal.getAs<loc::MemRegionVal>()) {
474            InitVal = state->getSVal(M->getRegion());
475            assert(InitVal.getAs<nonloc::LazyCompoundVal>());
476          }
477        }
478
479        // Recover some path-sensitivity if a scalar value evaluated to
480        // UnknownVal.
481        if (InitVal.isUnknown()) {
482          QualType Ty = InitEx->getType();
483          if (InitEx->isGLValue()) {
484            Ty = getContext().getPointerType(Ty);
485          }
486
487          InitVal = svalBuilder.conjureSymbolVal(0, InitEx, LC, Ty,
488                                                 currBldrCtx->blockCount());
489        }
490
491
492        B.takeNodes(UpdatedN);
493        ExplodedNodeSet Dst2;
494        evalBind(Dst2, DS, UpdatedN, state->getLValue(VD, LC), InitVal, true);
495        B.addNodes(Dst2);
496      }
497    }
498    else {
499      B.generateNode(DS, N, state);
500    }
501  }
502}
503
504void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
505                                  ExplodedNodeSet &Dst) {
506  assert(B->getOpcode() == BO_LAnd ||
507         B->getOpcode() == BO_LOr);
508
509  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
510  ProgramStateRef state = Pred->getState();
511
512  ExplodedNode *N = Pred;
513  while (!N->getLocation().getAs<BlockEntrance>()) {
514    ProgramPoint P = N->getLocation();
515    assert(P.getAs<PreStmt>()|| P.getAs<PreStmtPurgeDeadSymbols>());
516    (void) P;
517    assert(N->pred_size() == 1);
518    N = *N->pred_begin();
519  }
520  assert(N->pred_size() == 1);
521  N = *N->pred_begin();
522  BlockEdge BE = N->getLocation().castAs<BlockEdge>();
523  SVal X;
524
525  // Determine the value of the expression by introspecting how we
526  // got this location in the CFG.  This requires looking at the previous
527  // block we were in and what kind of control-flow transfer was involved.
528  const CFGBlock *SrcBlock = BE.getSrc();
529  // The only terminator (if there is one) that makes sense is a logical op.
530  CFGTerminator T = SrcBlock->getTerminator();
531  if (const BinaryOperator *Term = cast_or_null<BinaryOperator>(T.getStmt())) {
532    (void) Term;
533    assert(Term->isLogicalOp());
534    assert(SrcBlock->succ_size() == 2);
535    // Did we take the true or false branch?
536    unsigned constant = (*SrcBlock->succ_begin() == BE.getDst()) ? 1 : 0;
537    X = svalBuilder.makeIntVal(constant, B->getType());
538  }
539  else {
540    // If there is no terminator, by construction the last statement
541    // in SrcBlock is the value of the enclosing expression.
542    // However, we still need to constrain that value to be 0 or 1.
543    assert(!SrcBlock->empty());
544    CFGStmt Elem = SrcBlock->rbegin()->castAs<CFGStmt>();
545    const Expr *RHS = cast<Expr>(Elem.getStmt());
546    SVal RHSVal = N->getState()->getSVal(RHS, Pred->getLocationContext());
547
548    if (RHSVal.isUndef()) {
549      X = RHSVal;
550    } else {
551      DefinedOrUnknownSVal DefinedRHS = RHSVal.castAs<DefinedOrUnknownSVal>();
552      ProgramStateRef StTrue, StFalse;
553      llvm::tie(StTrue, StFalse) = N->getState()->assume(DefinedRHS);
554      if (StTrue) {
555        if (StFalse) {
556          // We can't constrain the value to 0 or 1.
557          // The best we can do is a cast.
558          X = getSValBuilder().evalCast(RHSVal, B->getType(), RHS->getType());
559        } else {
560          // The value is known to be true.
561          X = getSValBuilder().makeIntVal(1, B->getType());
562        }
563      } else {
564        // The value is known to be false.
565        assert(StFalse && "Infeasible path!");
566        X = getSValBuilder().makeIntVal(0, B->getType());
567      }
568    }
569  }
570  Bldr.generateNode(B, Pred, state->BindExpr(B, Pred->getLocationContext(), X));
571}
572
573void ExprEngine::VisitInitListExpr(const InitListExpr *IE,
574                                   ExplodedNode *Pred,
575                                   ExplodedNodeSet &Dst) {
576  StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
577
578  ProgramStateRef state = Pred->getState();
579  const LocationContext *LCtx = Pred->getLocationContext();
580  QualType T = getContext().getCanonicalType(IE->getType());
581  unsigned NumInitElements = IE->getNumInits();
582
583  if (!IE->isGLValue() &&
584      (T->isArrayType() || T->isRecordType() || T->isVectorType() ||
585       T->isAnyComplexType())) {
586    llvm::ImmutableList<SVal> vals = getBasicVals().getEmptySValList();
587
588    // Handle base case where the initializer has no elements.
589    // e.g: static int* myArray[] = {};
590    if (NumInitElements == 0) {
591      SVal V = svalBuilder.makeCompoundVal(T, vals);
592      B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V));
593      return;
594    }
595
596    for (InitListExpr::const_reverse_iterator it = IE->rbegin(),
597         ei = IE->rend(); it != ei; ++it) {
598      SVal V = state->getSVal(cast<Expr>(*it), LCtx);
599      if (dyn_cast_or_null<CXXTempObjectRegion>(V.getAsRegion()))
600        V = UnknownVal();
601      vals = getBasicVals().consVals(V, vals);
602    }
603
604    B.generateNode(IE, Pred,
605                   state->BindExpr(IE, LCtx,
606                                   svalBuilder.makeCompoundVal(T, vals)));
607    return;
608  }
609
610  // Handle scalars: int{5} and int{} and GLvalues.
611  // Note, if the InitListExpr is a GLvalue, it means that there is an address
612  // representing it, so it must have a single init element.
613  assert(NumInitElements <= 1);
614
615  SVal V;
616  if (NumInitElements == 0)
617    V = getSValBuilder().makeZeroVal(T);
618  else
619    V = state->getSVal(IE->getInit(0), LCtx);
620
621  B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V));
622}
623
624void ExprEngine::VisitGuardedExpr(const Expr *Ex,
625                                  const Expr *L,
626                                  const Expr *R,
627                                  ExplodedNode *Pred,
628                                  ExplodedNodeSet &Dst) {
629  assert(L && R);
630
631  StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
632  ProgramStateRef state = Pred->getState();
633  const LocationContext *LCtx = Pred->getLocationContext();
634  const CFGBlock *SrcBlock = 0;
635
636  // Find the predecessor block.
637  ProgramStateRef SrcState = state;
638  for (const ExplodedNode *N = Pred ; N ; N = *N->pred_begin()) {
639    ProgramPoint PP = N->getLocation();
640    if (PP.getAs<PreStmtPurgeDeadSymbols>() || PP.getAs<BlockEntrance>()) {
641      assert(N->pred_size() == 1);
642      continue;
643    }
644    SrcBlock = PP.castAs<BlockEdge>().getSrc();
645    SrcState = N->getState();
646    break;
647  }
648
649  assert(SrcBlock && "missing function entry");
650
651  // Find the last expression in the predecessor block.  That is the
652  // expression that is used for the value of the ternary expression.
653  bool hasValue = false;
654  SVal V;
655
656  for (CFGBlock::const_reverse_iterator I = SrcBlock->rbegin(),
657                                        E = SrcBlock->rend(); I != E; ++I) {
658    CFGElement CE = *I;
659    if (Optional<CFGStmt> CS = CE.getAs<CFGStmt>()) {
660      const Expr *ValEx = cast<Expr>(CS->getStmt());
661      ValEx = ValEx->IgnoreParens();
662
663      // For GNU extension '?:' operator, the left hand side will be an
664      // OpaqueValueExpr, so get the underlying expression.
665      if (const OpaqueValueExpr *OpaqueEx = dyn_cast<OpaqueValueExpr>(L))
666        L = OpaqueEx->getSourceExpr();
667
668      // If the last expression in the predecessor block matches true or false
669      // subexpression, get its the value.
670      if (ValEx == L->IgnoreParens() || ValEx == R->IgnoreParens()) {
671        hasValue = true;
672        V = SrcState->getSVal(ValEx, LCtx);
673      }
674      break;
675    }
676  }
677
678  if (!hasValue)
679    V = svalBuilder.conjureSymbolVal(0, Ex, LCtx, currBldrCtx->blockCount());
680
681  // Generate a new node with the binding from the appropriate path.
682  B.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V, true));
683}
684
685void ExprEngine::
686VisitOffsetOfExpr(const OffsetOfExpr *OOE,
687                  ExplodedNode *Pred, ExplodedNodeSet &Dst) {
688  StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
689  APSInt IV;
690  if (OOE->EvaluateAsInt(IV, getContext())) {
691    assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType()));
692    assert(OOE->getType()->isBuiltinType());
693    assert(OOE->getType()->getAs<BuiltinType>()->isInteger());
694    assert(IV.isSigned() == OOE->getType()->isSignedIntegerType());
695    SVal X = svalBuilder.makeIntVal(IV);
696    B.generateNode(OOE, Pred,
697                   Pred->getState()->BindExpr(OOE, Pred->getLocationContext(),
698                                              X));
699  }
700  // FIXME: Handle the case where __builtin_offsetof is not a constant.
701}
702
703
704void ExprEngine::
705VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
706                              ExplodedNode *Pred,
707                              ExplodedNodeSet &Dst) {
708  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
709
710  QualType T = Ex->getTypeOfArgument();
711
712  if (Ex->getKind() == UETT_SizeOf) {
713    if (!T->isIncompleteType() && !T->isConstantSizeType()) {
714      assert(T->isVariableArrayType() && "Unknown non-constant-sized type.");
715
716      // FIXME: Add support for VLA type arguments and VLA expressions.
717      // When that happens, we should probably refactor VLASizeChecker's code.
718      return;
719    }
720    else if (T->getAs<ObjCObjectType>()) {
721      // Some code tries to take the sizeof an ObjCObjectType, relying that
722      // the compiler has laid out its representation.  Just report Unknown
723      // for these.
724      return;
725    }
726  }
727
728  APSInt Value = Ex->EvaluateKnownConstInt(getContext());
729  CharUnits amt = CharUnits::fromQuantity(Value.getZExtValue());
730
731  ProgramStateRef state = Pred->getState();
732  state = state->BindExpr(Ex, Pred->getLocationContext(),
733                          svalBuilder.makeIntVal(amt.getQuantity(),
734                                                     Ex->getType()));
735  Bldr.generateNode(Ex, Pred, state);
736}
737
738void ExprEngine::VisitUnaryOperator(const UnaryOperator* U,
739                                    ExplodedNode *Pred,
740                                    ExplodedNodeSet &Dst) {
741  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
742  switch (U->getOpcode()) {
743    default: {
744      Bldr.takeNodes(Pred);
745      ExplodedNodeSet Tmp;
746      VisitIncrementDecrementOperator(U, Pred, Tmp);
747      Bldr.addNodes(Tmp);
748    }
749      break;
750    case UO_Real: {
751      const Expr *Ex = U->getSubExpr()->IgnoreParens();
752
753      // FIXME: We don't have complex SValues yet.
754      if (Ex->getType()->isAnyComplexType()) {
755        // Just report "Unknown."
756        break;
757      }
758
759      // For all other types, UO_Real is an identity operation.
760      assert (U->getType() == Ex->getType());
761      ProgramStateRef state = Pred->getState();
762      const LocationContext *LCtx = Pred->getLocationContext();
763      Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx,
764                                                 state->getSVal(Ex, LCtx)));
765      break;
766    }
767
768    case UO_Imag: {
769      const Expr *Ex = U->getSubExpr()->IgnoreParens();
770      // FIXME: We don't have complex SValues yet.
771      if (Ex->getType()->isAnyComplexType()) {
772        // Just report "Unknown."
773        break;
774      }
775      // For all other types, UO_Imag returns 0.
776      ProgramStateRef state = Pred->getState();
777      const LocationContext *LCtx = Pred->getLocationContext();
778      SVal X = svalBuilder.makeZeroVal(Ex->getType());
779      Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, X));
780      break;
781    }
782
783    case UO_Plus:
784      assert(!U->isGLValue());
785      // FALL-THROUGH.
786    case UO_Deref:
787    case UO_AddrOf:
788    case UO_Extension: {
789      // FIXME: We can probably just have some magic in Environment::getSVal()
790      // that propagates values, instead of creating a new node here.
791      //
792      // Unary "+" is a no-op, similar to a parentheses.  We still have places
793      // where it may be a block-level expression, so we need to
794      // generate an extra node that just propagates the value of the
795      // subexpression.
796      const Expr *Ex = U->getSubExpr()->IgnoreParens();
797      ProgramStateRef state = Pred->getState();
798      const LocationContext *LCtx = Pred->getLocationContext();
799      Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx,
800                                                 state->getSVal(Ex, LCtx)));
801      break;
802    }
803
804    case UO_LNot:
805    case UO_Minus:
806    case UO_Not: {
807      assert (!U->isGLValue());
808      const Expr *Ex = U->getSubExpr()->IgnoreParens();
809      ProgramStateRef state = Pred->getState();
810      const LocationContext *LCtx = Pred->getLocationContext();
811
812      // Get the value of the subexpression.
813      SVal V = state->getSVal(Ex, LCtx);
814
815      if (V.isUnknownOrUndef()) {
816        Bldr.generateNode(U, Pred, state->BindExpr(U, LCtx, V));
817        break;
818      }
819
820      switch (U->getOpcode()) {
821        default:
822          llvm_unreachable("Invalid Opcode.");
823        case UO_Not:
824          // FIXME: Do we need to handle promotions?
825          state = state->BindExpr(U, LCtx, evalComplement(V.castAs<NonLoc>()));
826          break;
827        case UO_Minus:
828          // FIXME: Do we need to handle promotions?
829          state = state->BindExpr(U, LCtx, evalMinus(V.castAs<NonLoc>()));
830          break;
831        case UO_LNot:
832          // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
833          //
834          //  Note: technically we do "E == 0", but this is the same in the
835          //    transfer functions as "0 == E".
836          SVal Result;
837          if (Optional<Loc> LV = V.getAs<Loc>()) {
838            Loc X = svalBuilder.makeNull();
839            Result = evalBinOp(state, BO_EQ, *LV, X, U->getType());
840          }
841          else if (Ex->getType()->isFloatingType()) {
842            // FIXME: handle floating point types.
843            Result = UnknownVal();
844          } else {
845            nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType()));
846            Result = evalBinOp(state, BO_EQ, V.castAs<NonLoc>(), X,
847                               U->getType());
848          }
849
850          state = state->BindExpr(U, LCtx, Result);
851          break;
852      }
853      Bldr.generateNode(U, Pred, state);
854      break;
855    }
856  }
857
858}
859
860void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U,
861                                                 ExplodedNode *Pred,
862                                                 ExplodedNodeSet &Dst) {
863  // Handle ++ and -- (both pre- and post-increment).
864  assert (U->isIncrementDecrementOp());
865  const Expr *Ex = U->getSubExpr()->IgnoreParens();
866
867  const LocationContext *LCtx = Pred->getLocationContext();
868  ProgramStateRef state = Pred->getState();
869  SVal loc = state->getSVal(Ex, LCtx);
870
871  // Perform a load.
872  ExplodedNodeSet Tmp;
873  evalLoad(Tmp, U, Ex, Pred, state, loc);
874
875  ExplodedNodeSet Dst2;
876  StmtNodeBuilder Bldr(Tmp, Dst2, *currBldrCtx);
877  for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end();I!=E;++I) {
878
879    state = (*I)->getState();
880    assert(LCtx == (*I)->getLocationContext());
881    SVal V2_untested = state->getSVal(Ex, LCtx);
882
883    // Propagate unknown and undefined values.
884    if (V2_untested.isUnknownOrUndef()) {
885      Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V2_untested));
886      continue;
887    }
888    DefinedSVal V2 = V2_untested.castAs<DefinedSVal>();
889
890    // Handle all other values.
891    BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add : BO_Sub;
892
893    // If the UnaryOperator has non-location type, use its type to create the
894    // constant value. If the UnaryOperator has location type, create the
895    // constant with int type and pointer width.
896    SVal RHS;
897
898    if (U->getType()->isAnyPointerType())
899      RHS = svalBuilder.makeArrayIndex(1);
900    else if (U->getType()->isIntegralOrEnumerationType())
901      RHS = svalBuilder.makeIntVal(1, U->getType());
902    else
903      RHS = UnknownVal();
904
905    SVal Result = evalBinOp(state, Op, V2, RHS, U->getType());
906
907    // Conjure a new symbol if necessary to recover precision.
908    if (Result.isUnknown()){
909      DefinedOrUnknownSVal SymVal =
910        svalBuilder.conjureSymbolVal(0, Ex, LCtx, currBldrCtx->blockCount());
911      Result = SymVal;
912
913      // If the value is a location, ++/-- should always preserve
914      // non-nullness.  Check if the original value was non-null, and if so
915      // propagate that constraint.
916      if (Loc::isLocType(U->getType())) {
917        DefinedOrUnknownSVal Constraint =
918        svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType()));
919
920        if (!state->assume(Constraint, true)) {
921          // It isn't feasible for the original value to be null.
922          // Propagate this constraint.
923          Constraint = svalBuilder.evalEQ(state, SymVal,
924                                       svalBuilder.makeZeroVal(U->getType()));
925
926
927          state = state->assume(Constraint, false);
928          assert(state);
929        }
930      }
931    }
932
933    // Since the lvalue-to-rvalue conversion is explicit in the AST,
934    // we bind an l-value if the operator is prefix and an lvalue (in C++).
935    if (U->isGLValue())
936      state = state->BindExpr(U, LCtx, loc);
937    else
938      state = state->BindExpr(U, LCtx, U->isPostfix() ? V2 : Result);
939
940    // Perform the store.
941    Bldr.takeNodes(*I);
942    ExplodedNodeSet Dst3;
943    evalStore(Dst3, U, U, *I, state, loc, Result);
944    Bldr.addNodes(Dst3);
945  }
946  Dst.insert(Dst2);
947}
948