contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp

   1 //= CStringChecker.h - Checks calls to C string functions ----------*- 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 defines CStringChecker, which is an assortment of checks on calls
  11 // to functions in <string.h>.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "ClangSACheckers.h"
  16 #include "clang/StaticAnalyzer/Core/Checker.h"
  17 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  19 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h"
  21 #include "llvm/ADT/StringSwitch.h"
  22
  23 using namespace clang;
  24 using namespace ento;
  25
  26 namespace {
  27 class CStringChecker : public Checker< eval::Call,
  28                                          check::PreStmt<DeclStmt>,
  29                                          check::LiveSymbols,
  30                                          check::DeadSymbols,
  31                                          check::RegionChanges
  32                                          > {
  33   mutable llvm::OwningPtr<BugType> BT_Null, BT_Bounds,
  34                                    BT_Overlap, BT_NotCString,
  35                                    BT_AdditionOverflow;
  36   mutable const char *CurrentFunctionDescription;
  37
  38 public:
  39   static void *getTag() { static int tag; return &tag; }
  40
  41   bool evalCall(const CallExpr *CE, CheckerContext &C) const;
  42   void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
  43   void checkLiveSymbols(const GRState *state, SymbolReaper &SR) const;
  44   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
  45   bool wantsRegionChangeUpdate(const GRState *state) const;
  46
  47   const GRState *checkRegionChanges(const GRState *state,
  48                                     const StoreManager::InvalidatedSymbols *,
  49                                     const MemRegion * const *Begin,
  50                                     const MemRegion * const *End) const;
  51
  52   typedef void (CStringChecker::*FnCheck)(CheckerContext &,
  53                                           const CallExpr *) const;
  54
  55   void evalMemcpy(CheckerContext &C, const CallExpr *CE) const;
  56   void evalMempcpy(CheckerContext &C, const CallExpr *CE) const;
  57   void evalMemmove(CheckerContext &C, const CallExpr *CE) const;
  58   void evalBcopy(CheckerContext &C, const CallExpr *CE) const;
  59   void evalCopyCommon(CheckerContext &C, const CallExpr *CE,
  60                       const GRState *state,
  61                       const Expr *Size, const Expr *Source, const Expr *Dest,
  62                       bool Restricted = false,
  63                       bool IsMempcpy = false) const;
  64
  65   void evalMemcmp(CheckerContext &C, const CallExpr *CE) const;
  66
  67   void evalstrLength(CheckerContext &C, const CallExpr *CE) const;
  68   void evalstrnLength(CheckerContext &C, const CallExpr *CE) const;
  69   void evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
  70                            bool IsStrnlen = false) const;
  71
  72   void evalStrcpy(CheckerContext &C, const CallExpr *CE) const;
  73   void evalStrncpy(CheckerContext &C, const CallExpr *CE) const;
  74   void evalStpcpy(CheckerContext &C, const CallExpr *CE) const;
  75   void evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool returnEnd,
  76                         bool isBounded, bool isAppending) const;
  77
  78   void evalStrcat(CheckerContext &C, const CallExpr *CE) const;
  79   void evalStrncat(CheckerContext &C, const CallExpr *CE) const;
  80
  81   void evalStrcmp(CheckerContext &C, const CallExpr *CE) const;
  82   void evalStrncmp(CheckerContext &C, const CallExpr *CE) const;
  83   void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const;
  84   void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const;
  85   void evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
  86                         bool isBounded = false, bool ignoreCase = false) const;
  87
  88   // Utility methods
  89   std::pair<const GRState*, const GRState*>
  90   static assumeZero(CheckerContext &C,
  91                     const GRState *state, SVal V, QualType Ty);
  92
  93   static const GRState *setCStringLength(const GRState *state,
  94                                          const MemRegion *MR, SVal strLength);
  95   static SVal getCStringLengthForRegion(CheckerContext &C,
  96                                         const GRState *&state,
  97                                         const Expr *Ex, const MemRegion *MR,
  98                                         bool hypothetical);
  99   SVal getCStringLength(CheckerContext &C, const GRState *&state,
 100                         const Expr *Ex, SVal Buf,
 101                         bool hypothetical = false) const;
 102
 103   const StringLiteral *getCStringLiteral(CheckerContext &C,
 104                                          const GRState *&state,
 105                                          const Expr *expr,
 106                                          SVal val) const;
 107
 108   static const GRState *InvalidateBuffer(CheckerContext &C,
 109                                          const GRState *state,
 110                                          const Expr *Ex, SVal V);
 111
 112   static bool SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
 113                               const MemRegion *MR);
 114
 115   // Re-usable checks
 116   const GRState *checkNonNull(CheckerContext &C, const GRState *state,
 117                                const Expr *S, SVal l) const;
 118   const GRState *CheckLocation(CheckerContext &C, const GRState *state,
 119                                const Expr *S, SVal l,
 120                                const char *message = NULL) const;
 121   const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state,
 122                                    const Expr *Size,
 123                                    const Expr *FirstBuf,
 124                                    const Expr *SecondBuf,
 125                                    const char *firstMessage = NULL,
 126                                    const char *secondMessage = NULL,
 127                                    bool WarnAboutSize = false) const;
 128   const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state,
 129                                    const Expr *Size, const Expr *Buf,
 130                                    const char *message = NULL,
 131                                    bool WarnAboutSize = false) const {
 132     // This is a convenience override.
 133     return CheckBufferAccess(C, state, Size, Buf, NULL, message, NULL,
 134                              WarnAboutSize);
 135   }
 136   const GRState *CheckOverlap(CheckerContext &C, const GRState *state,
 137                               const Expr *Size, const Expr *First,
 138                               const Expr *Second) const;
 139   void emitOverlapBug(CheckerContext &C, const GRState *state,
 140                       const Stmt *First, const Stmt *Second) const;
 141   const GRState *checkAdditionOverflow(CheckerContext &C, const GRState *state,
 142                                        NonLoc left, NonLoc right) const;
 143 };
 144
 145 class CStringLength {
 146 public:
 147   typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap;
 148 };
 149 } //end anonymous namespace
 150
 151 namespace clang {
 152 namespace ento {
 153   template <>
 154   struct GRStateTrait<CStringLength>
 155     : public GRStatePartialTrait<CStringLength::EntryMap> {
 156     static void *GDMIndex() { return CStringChecker::getTag(); }
 157   };
 158 }
 159 }
 160
 161 //===----------------------------------------------------------------------===//
 162 // Individual checks and utility methods.
 163 //===----------------------------------------------------------------------===//
 164
 165 std::pair<const GRState*, const GRState*>
 166 CStringChecker::assumeZero(CheckerContext &C, const GRState *state, SVal V,
 167                            QualType Ty) {
 168   DefinedSVal *val = dyn_cast<DefinedSVal>(&V);
 169   if (!val)
 170     return std::pair<const GRState*, const GRState *>(state, state);
 171
 172   SValBuilder &svalBuilder = C.getSValBuilder();
 173   DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);
 174   return state->assume(svalBuilder.evalEQ(state, *val, zero));
 175 }
 176
 177 const GRState *CStringChecker::checkNonNull(CheckerContext &C,
 178                                             const GRState *state,
 179                                             const Expr *S, SVal l) const {
 180   // If a previous check has failed, propagate the failure.
 181   if (!state)
 182     return NULL;
 183
 184   const GRState *stateNull, *stateNonNull;
 185   llvm::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType());
 186
 187   if (stateNull && !stateNonNull) {
 188     ExplodedNode *N = C.generateSink(stateNull);
 189     if (!N)
 190       return NULL;
 191
 192     if (!BT_Null)
 193       BT_Null.reset(new BuiltinBug("API",
 194         "Null pointer argument in call to byte string function"));
 195
 196     llvm::SmallString<80> buf;
 197     llvm::raw_svector_ostream os(buf);
 198     assert(CurrentFunctionDescription);
 199     os << "Null pointer argument in call to " << CurrentFunctionDescription;
 200
 201     // Generate a report for this bug.
 202     BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null.get());
 203     EnhancedBugReport *report = new EnhancedBugReport(*BT, os.str(), N);
 204
 205     report->addRange(S->getSourceRange());
 206     report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, S);
 207     C.EmitReport(report);
 208     return NULL;
 209   }
 210
 211   // From here on, assume that the value is non-null.
 212   assert(stateNonNull);
 213   return stateNonNull;
 214 }
 215
 216 // FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
 217 const GRState *CStringChecker::CheckLocation(CheckerContext &C,
 218                                              const GRState *state,
 219                                              const Expr *S, SVal l,
 220                                              const char *warningMsg) const {
 221   // If a previous check has failed, propagate the failure.
 222   if (!state)
 223     return NULL;
 224
 225   // Check for out of bound array element access.
 226   const MemRegion *R = l.getAsRegion();
 227   if (!R)
 228     return state;
 229
 230   const ElementRegion *ER = dyn_cast<ElementRegion>(R);
 231   if (!ER)
 232     return state;
 233
 234   assert(ER->getValueType() == C.getASTContext().CharTy &&
 235     "CheckLocation should only be called with char* ElementRegions");
 236
 237   // Get the size of the array.
 238   const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
 239   SValBuilder &svalBuilder = C.getSValBuilder();
 240   SVal Extent =
 241     svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
 242   DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);
 243
 244   // Get the index of the accessed element.
 245   DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
 246
 247   const GRState *StInBound = state->assumeInBound(Idx, Size, true);
 248   const GRState *StOutBound = state->assumeInBound(Idx, Size, false);
 249   if (StOutBound && !StInBound) {
 250     ExplodedNode *N = C.generateSink(StOutBound);
 251     if (!N)
 252       return NULL;
 253
 254     if (!BT_Bounds) {
 255       BT_Bounds.reset(new BuiltinBug("Out-of-bound array access",
 256         "Byte string function accesses out-of-bound array element"));
 257     }
 258     BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds.get());
 259
 260     // Generate a report for this bug.
 261     RangedBugReport *report;
 262     if (warningMsg) {
 263       report = new RangedBugReport(*BT, warningMsg, N);
 264     } else {
 265       assert(CurrentFunctionDescription);
 266       assert(CurrentFunctionDescription[0] != '\0');
 267
 268       llvm::SmallString<80> buf;
 269       llvm::raw_svector_ostream os(buf);
 270       os << (char)toupper(CurrentFunctionDescription[0])
 271          << &CurrentFunctionDescription[1]
 272          << " accesses out-of-bound array element";
 273       report = new RangedBugReport(*BT, os.str(), N);
 274     }
 275
 276     // FIXME: It would be nice to eventually make this diagnostic more clear,
 277     // e.g., by referencing the original declaration or by saying *why* this
 278     // reference is outside the range.
 279
 280     report->addRange(S->getSourceRange());
 281     C.EmitReport(report);
 282     return NULL;
 283   }
 284
 285   // Array bound check succeeded.  From this point forward the array bound
 286   // should always succeed.
 287   return StInBound;
 288 }
 289
 290 const GRState *CStringChecker::CheckBufferAccess(CheckerContext &C,
 291                                                  const GRState *state,
 292                                                  const Expr *Size,
 293                                                  const Expr *FirstBuf,
 294                                                  const Expr *SecondBuf,
 295                                                  const char *firstMessage,
 296                                                  const char *secondMessage,
 297                                                  bool WarnAboutSize) const {
 298   // If a previous check has failed, propagate the failure.
 299   if (!state)
 300     return NULL;
 301
 302   SValBuilder &svalBuilder = C.getSValBuilder();
 303   ASTContext &Ctx = svalBuilder.getContext();
 304
 305   QualType sizeTy = Size->getType();
 306   QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
 307
 308   // Check that the first buffer is non-null.
 309   SVal BufVal = state->getSVal(FirstBuf);
 310   state = checkNonNull(C, state, FirstBuf, BufVal);
 311   if (!state)
 312     return NULL;
 313
 314   // Get the access length and make sure it is known.
 315   // FIXME: This assumes the caller has already checked that the access length
 316   // is positive. And that it's unsigned.
 317   SVal LengthVal = state->getSVal(Size);
 318   NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
 319   if (!Length)
 320     return state;
 321
 322   // Compute the offset of the last element to be accessed: size-1.
 323   NonLoc One = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
 324   NonLoc LastOffset = cast<NonLoc>(svalBuilder.evalBinOpNN(state, BO_Sub,
 325                                                     *Length, One, sizeTy));
 326
 327   // Check that the first buffer is sufficiently long.
 328   SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
 329   if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
 330     const Expr *warningExpr = (WarnAboutSize ? Size : FirstBuf);
 331
 332     SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
 333                                           LastOffset, PtrTy);
 334     state = CheckLocation(C, state, warningExpr, BufEnd, firstMessage);
 335
 336     // If the buffer isn't large enough, abort.
 337     if (!state)
 338       return NULL;
 339   }
 340
 341   // If there's a second buffer, check it as well.
 342   if (SecondBuf) {
 343     BufVal = state->getSVal(SecondBuf);
 344     state = checkNonNull(C, state, SecondBuf, BufVal);
 345     if (!state)
 346       return NULL;
 347
 348     BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType());
 349     if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
 350       const Expr *warningExpr = (WarnAboutSize ? Size : SecondBuf);
 351
 352       SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
 353                                             LastOffset, PtrTy);
 354       state = CheckLocation(C, state, warningExpr, BufEnd, secondMessage);
 355     }
 356   }
 357
 358   // Large enough or not, return this state!
 359   return state;
 360 }
 361
 362 const GRState *CStringChecker::CheckOverlap(CheckerContext &C,
 363                                             const GRState *state,
 364                                             const Expr *Size,
 365                                             const Expr *First,
 366                                             const Expr *Second) const {
 367   // Do a simple check for overlap: if the two arguments are from the same
 368   // buffer, see if the end of the first is greater than the start of the second
 369   // or vice versa.
 370
 371   // If a previous check has failed, propagate the failure.
 372   if (!state)
 373     return NULL;
 374
 375   const GRState *stateTrue, *stateFalse;
 376
 377   // Get the buffer values and make sure they're known locations.
 378   SVal firstVal = state->getSVal(First);
 379   SVal secondVal = state->getSVal(Second);
 380
 381   Loc *firstLoc = dyn_cast<Loc>(&firstVal);
 382   if (!firstLoc)
 383     return state;
 384
 385   Loc *secondLoc = dyn_cast<Loc>(&secondVal);
 386   if (!secondLoc)
 387     return state;
 388
 389   // Are the two values the same?
 390   SValBuilder &svalBuilder = C.getSValBuilder();
 391   llvm::tie(stateTrue, stateFalse) =
 392     state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));
 393
 394   if (stateTrue && !stateFalse) {
 395     // If the values are known to be equal, that's automatically an overlap.
 396     emitOverlapBug(C, stateTrue, First, Second);
 397     return NULL;
 398   }
 399
 400   // assume the two expressions are not equal.
 401   assert(stateFalse);
 402   state = stateFalse;
 403
 404   // Which value comes first?
 405   QualType cmpTy = svalBuilder.getConditionType();
 406   SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT,
 407                                          *firstLoc, *secondLoc, cmpTy);
 408   DefinedOrUnknownSVal *reverseTest = dyn_cast<DefinedOrUnknownSVal>(&reverse);
 409   if (!reverseTest)
 410     return state;
 411
 412   llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest);
 413   if (stateTrue) {
 414     if (stateFalse) {
 415       // If we don't know which one comes first, we can't perform this test.
 416       return state;
 417     } else {
 418       // Switch the values so that firstVal is before secondVal.
 419       Loc *tmpLoc = firstLoc;
 420       firstLoc = secondLoc;
 421       secondLoc = tmpLoc;
 422
 423       // Switch the Exprs as well, so that they still correspond.
 424       const Expr *tmpExpr = First;
 425       First = Second;
 426       Second = tmpExpr;
 427     }
 428   }
 429
 430   // Get the length, and make sure it too is known.
 431   SVal LengthVal = state->getSVal(Size);
 432   NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
 433   if (!Length)
 434     return state;
 435
 436   // Convert the first buffer's start address to char*.
 437   // Bail out if the cast fails.
 438   ASTContext &Ctx = svalBuilder.getContext();
 439   QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
 440   SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy,
 441                                          First->getType());
 442   Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart);
 443   if (!FirstStartLoc)
 444     return state;
 445
 446   // Compute the end of the first buffer. Bail out if THAT fails.
 447   SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add,
 448                                  *FirstStartLoc, *Length, CharPtrTy);
 449   Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd);
 450   if (!FirstEndLoc)
 451     return state;
 452
 453   // Is the end of the first buffer past the start of the second buffer?
 454   SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT,
 455                                 *FirstEndLoc, *secondLoc, cmpTy);
 456   DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap);
 457   if (!OverlapTest)
 458     return state;
 459
 460   llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);
 461
 462   if (stateTrue && !stateFalse) {
 463     // Overlap!
 464     emitOverlapBug(C, stateTrue, First, Second);
 465     return NULL;
 466   }
 467
 468   // assume the two expressions don't overlap.
 469   assert(stateFalse);
 470   return stateFalse;
 471 }
 472
 473 void CStringChecker::emitOverlapBug(CheckerContext &C, const GRState *state,
 474                                   const Stmt *First, const Stmt *Second) const {
 475   ExplodedNode *N = C.generateSink(state);
 476   if (!N)
 477     return;
 478
 479   if (!BT_Overlap)
 480     BT_Overlap.reset(new BugType("Unix API", "Improper arguments"));
 481
 482   // Generate a report for this bug.
 483   RangedBugReport *report =
 484     new RangedBugReport(*BT_Overlap,
 485       "Arguments must not be overlapping buffers", N);
 486   report->addRange(First->getSourceRange());
 487   report->addRange(Second->getSourceRange());
 488
 489   C.EmitReport(report);
 490 }
 491
 492 const GRState *CStringChecker::checkAdditionOverflow(CheckerContext &C,
 493                                                      const GRState *state,
 494                                                      NonLoc left,
 495                                                      NonLoc right) const {
 496   // If a previous check has failed, propagate the failure.
 497   if (!state)
 498     return NULL;
 499
 500   SValBuilder &svalBuilder = C.getSValBuilder();
 501   BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
 502
 503   QualType sizeTy = svalBuilder.getContext().getSizeType();
 504   const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);
 505   NonLoc maxVal = svalBuilder.makeIntVal(maxValInt);
 506
 507   SVal maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right,
 508                                                sizeTy);
 509
 510   if (maxMinusRight.isUnknownOrUndef()) {
 511     // Try switching the operands. (The order of these two assignments is
 512     // important!)
 513     maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left,
 514                                             sizeTy);
 515     left = right;
 516   }
 517
 518   if (NonLoc *maxMinusRightNL = dyn_cast<NonLoc>(&maxMinusRight)) {
 519     QualType cmpTy = svalBuilder.getConditionType();
 520     // If left > max - right, we have an overflow.
 521     SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left,
 522                                                 *maxMinusRightNL, cmpTy);
 523
 524     const GRState *stateOverflow, *stateOkay;
 525     llvm::tie(stateOverflow, stateOkay) =
 526       state->assume(cast<DefinedOrUnknownSVal>(willOverflow));
 527
 528     if (stateOverflow && !stateOkay) {
 529       // We have an overflow. Emit a bug report.
 530       ExplodedNode *N = C.generateSink(stateOverflow);
 531       if (!N)
 532         return NULL;
 533
 534       if (!BT_AdditionOverflow)
 535         BT_AdditionOverflow.reset(new BuiltinBug("API",
 536           "Sum of expressions causes overflow"));
 537
 538       // This isn't a great error message, but this should never occur in real
 539       // code anyway -- you'd have to create a buffer longer than a size_t can
 540       // represent, which is sort of a contradiction.
 541       const char *warning =
 542         "This expression will create a string whose length is too big to "
 543         "be represented as a size_t";
 544
 545       // Generate a report for this bug.
 546       BugReport *report = new BugReport(*BT_AdditionOverflow, warning, N);
 547       C.EmitReport(report);
 548
 549       return NULL;
 550     }
 551
 552     // From now on, assume an overflow didn't occur.
 553     assert(stateOkay);
 554     state = stateOkay;
 555   }
 556
 557   return state;
 558 }
 559
 560 const GRState *CStringChecker::setCStringLength(const GRState *state,
 561                                                 const MemRegion *MR,
 562                                                 SVal strLength) {
 563   assert(!strLength.isUndef() && "Attempt to set an undefined string length");
 564
 565   MR = MR->StripCasts();
 566
 567   switch (MR->getKind()) {
 568   case MemRegion::StringRegionKind:
 569     // FIXME: This can happen if we strcpy() into a string region. This is
 570     // undefined [C99 6.4.5p6], but we should still warn about it.
 571     return state;
 572
 573   case MemRegion::SymbolicRegionKind:
 574   case MemRegion::AllocaRegionKind:
 575   case MemRegion::VarRegionKind:
 576   case MemRegion::FieldRegionKind:
 577   case MemRegion::ObjCIvarRegionKind:
 578     // These are the types we can currently track string lengths for.
 579     break;
 580
 581   case MemRegion::ElementRegionKind:
 582     // FIXME: Handle element regions by upper-bounding the parent region's
 583     // string length.
 584     return state;
 585
 586   default:
 587     // Other regions (mostly non-data) can't have a reliable C string length.
 588     // For now, just ignore the change.
 589     // FIXME: These are rare but not impossible. We should output some kind of
 590     // warning for things like strcpy((char[]){'a', 0}, "b");
 591     return state;
 592   }
 593
 594   if (strLength.isUnknown())
 595     return state->remove<CStringLength>(MR);
 596
 597   return state->set<CStringLength>(MR, strLength);
 598 }
 599
 600 SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,
 601                                                const GRState *&state,
 602                                                const Expr *Ex,
 603                                                const MemRegion *MR,
 604                                                bool hypothetical) {
 605   if (!hypothetical) {
 606     // If there's a recorded length, go ahead and return it.
 607     const SVal *Recorded = state->get<CStringLength>(MR);
 608     if (Recorded)
 609       return *Recorded;
 610   }
 611
 612   // Otherwise, get a new symbol and update the state.
 613   unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 614   SValBuilder &svalBuilder = C.getSValBuilder();
 615   QualType sizeTy = svalBuilder.getContext().getSizeType();
 616   SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),
 617                                                     MR, Ex, sizeTy, Count);
 618
 619   if (!hypothetical)
 620     state = state->set<CStringLength>(MR, strLength);
 621
 622   return strLength;
 623 }
 624
 625 SVal CStringChecker::getCStringLength(CheckerContext &C, const GRState *&state,
 626                                       const Expr *Ex, SVal Buf,
 627                                       bool hypothetical) const {
 628   const MemRegion *MR = Buf.getAsRegion();
 629   if (!MR) {
 630     // If we can't get a region, see if it's something we /know/ isn't a
 631     // C string. In the context of locations, the only time we can issue such
 632     // a warning is for labels.
 633     if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
 634       if (ExplodedNode *N = C.generateNode(state)) {
 635         if (!BT_NotCString)
 636           BT_NotCString.reset(new BuiltinBug("API",
 637             "Argument is not a null-terminated string."));
 638
 639         llvm::SmallString<120> buf;
 640         llvm::raw_svector_ostream os(buf);
 641         assert(CurrentFunctionDescription);
 642         os << "Argument to " << CurrentFunctionDescription
 643            << " is the address of the label '" << Label->getLabel()->getName()
 644            << "', which is not a null-terminated string";
 645
 646         // Generate a report for this bug.
 647         EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
 648                                                           os.str(), N);
 649
 650         report->addRange(Ex->getSourceRange());
 651         C.EmitReport(report);
 652       }
 653
 654       return UndefinedVal();
 655     }
 656
 657     // If it's not a region and not a label, give up.
 658     return UnknownVal();
 659   }
 660
 661   // If we have a region, strip casts from it and see if we can figure out
 662   // its length. For anything we can't figure out, just return UnknownVal.
 663   MR = MR->StripCasts();
 664
 665   switch (MR->getKind()) {
 666   case MemRegion::StringRegionKind: {
 667     // Modifying the contents of string regions is undefined [C99 6.4.5p6],
 668     // so we can assume that the byte length is the correct C string length.
 669     SValBuilder &svalBuilder = C.getSValBuilder();
 670     QualType sizeTy = svalBuilder.getContext().getSizeType();
 671     const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();
 672     return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
 673   }
 674   case MemRegion::SymbolicRegionKind:
 675   case MemRegion::AllocaRegionKind:
 676   case MemRegion::VarRegionKind:
 677   case MemRegion::FieldRegionKind:
 678   case MemRegion::ObjCIvarRegionKind:
 679     return getCStringLengthForRegion(C, state, Ex, MR, hypothetical);
 680   case MemRegion::CompoundLiteralRegionKind:
 681     // FIXME: Can we track this? Is it necessary?
 682     return UnknownVal();
 683   case MemRegion::ElementRegionKind:
 684     // FIXME: How can we handle this? It's not good enough to subtract the
 685     // offset from the base string length; consider "123\x00567" and &a[5].
 686     return UnknownVal();
 687   default:
 688     // Other regions (mostly non-data) can't have a reliable C string length.
 689     // In this case, an error is emitted and UndefinedVal is returned.
 690     // The caller should always be prepared to handle this case.
 691     if (ExplodedNode *N = C.generateNode(state)) {
 692       if (!BT_NotCString)
 693         BT_NotCString.reset(new BuiltinBug("API",
 694           "Argument is not a null-terminated string."));
 695
 696       llvm::SmallString<120> buf;
 697       llvm::raw_svector_ostream os(buf);
 698
 699       assert(CurrentFunctionDescription);
 700       os << "Argument to " << CurrentFunctionDescription << " is ";
 701
 702       if (SummarizeRegion(os, C.getASTContext(), MR))
 703         os << ", which is not a null-terminated string";
 704       else
 705         os << "not a null-terminated string";
 706
 707       // Generate a report for this bug.
 708       EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
 709                                                         os.str(), N);
 710
 711       report->addRange(Ex->getSourceRange());
 712       C.EmitReport(report);
 713     }
 714
 715     return UndefinedVal();
 716   }
 717 }
 718
 719 const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,
 720   const GRState *&state, const Expr *expr, SVal val) const {
 721
 722   // Get the memory region pointed to by the val.
 723   const MemRegion *bufRegion = val.getAsRegion();
 724   if (!bufRegion)
 725     return NULL;
 726
 727   // Strip casts off the memory region.
 728   bufRegion = bufRegion->StripCasts();
 729
 730   // Cast the memory region to a string region.
 731   const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);
 732   if (!strRegion)
 733     return NULL;
 734
 735   // Return the actual string in the string region.
 736   return strRegion->getStringLiteral();
 737 }
 738
 739 const GRState *CStringChecker::InvalidateBuffer(CheckerContext &C,
 740                                                 const GRState *state,
 741                                                 const Expr *E, SVal V) {
 742   Loc *L = dyn_cast<Loc>(&V);
 743   if (!L)
 744     return state;
 745
 746   // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
 747   // some assumptions about the value that CFRefCount can't. Even so, it should
 748   // probably be refactored.
 749   if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) {
 750     const MemRegion *R = MR->getRegion()->StripCasts();
 751
 752     // Are we dealing with an ElementRegion?  If so, we should be invalidating
 753     // the super-region.
 754     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
 755       R = ER->getSuperRegion();
 756       // FIXME: What about layers of ElementRegions?
 757     }
 758
 759     // Invalidate this region.
 760     unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 761     return state->invalidateRegion(R, E, Count, NULL);
 762   }
 763
 764   // If we have a non-region value by chance, just remove the binding.
 765   // FIXME: is this necessary or correct? This handles the non-Region
 766   //  cases.  Is it ever valid to store to these?
 767   return state->unbindLoc(*L);
 768 }
 769
 770 bool CStringChecker::SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
 771                                      const MemRegion *MR) {
 772   const TypedRegion *TR = dyn_cast<TypedRegion>(MR);
 773   if (!TR)
 774     return false;
 775
 776   switch (TR->getKind()) {
 777   case MemRegion::FunctionTextRegionKind: {
 778     const FunctionDecl *FD = cast<FunctionTextRegion>(TR)->getDecl();
 779     if (FD)
 780       os << "the address of the function '" << FD << "'";
 781     else
 782       os << "the address of a function";
 783     return true;
 784   }
 785   case MemRegion::BlockTextRegionKind:
 786     os << "block text";
 787     return true;
 788   case MemRegion::BlockDataRegionKind:
 789     os << "a block";
 790     return true;
 791   case MemRegion::CXXThisRegionKind:
 792   case MemRegion::CXXTempObjectRegionKind:
 793     os << "a C++ temp object of type " << TR->getValueType().getAsString();
 794     return true;
 795   case MemRegion::VarRegionKind:
 796     os << "a variable of type" << TR->getValueType().getAsString();
 797     return true;
 798   case MemRegion::FieldRegionKind:
 799     os << "a field of type " << TR->getValueType().getAsString();
 800     return true;
 801   case MemRegion::ObjCIvarRegionKind:
 802     os << "an instance variable of type " << TR->getValueType().getAsString();
 803     return true;
 804   default:
 805     return false;
 806   }
 807 }
 808
 809 //===----------------------------------------------------------------------===//
 810 // evaluation of individual function calls.
 811 //===----------------------------------------------------------------------===//
 812
 813 void CStringChecker::evalCopyCommon(CheckerContext &C,
 814                                     const CallExpr *CE,
 815                                     const GRState *state,
 816                                     const Expr *Size, const Expr *Dest,
 817                                     const Expr *Source, bool Restricted,
 818                                     bool IsMempcpy) const {
 819   CurrentFunctionDescription = "memory copy function";
 820
 821   // See if the size argument is zero.
 822   SVal sizeVal = state->getSVal(Size);
 823   QualType sizeTy = Size->getType();
 824
 825   const GRState *stateZeroSize, *stateNonZeroSize;
 826   llvm::tie(stateZeroSize, stateNonZeroSize) =
 827     assumeZero(C, state, sizeVal, sizeTy);
 828
 829   // Get the value of the Dest.
 830   SVal destVal = state->getSVal(Dest);
 831
 832   // If the size is zero, there won't be any actual memory access, so
 833   // just bind the return value to the destination buffer and return.
 834   if (stateZeroSize) {
 835     stateZeroSize = stateZeroSize->BindExpr(CE, destVal);
 836     C.addTransition(stateZeroSize);
 837   }
 838
 839   // If the size can be nonzero, we have to check the other arguments.
 840   if (stateNonZeroSize) {
 841     state = stateNonZeroSize;
 842
 843     // Ensure the destination is not null. If it is NULL there will be a
 844     // NULL pointer dereference.
 845     state = checkNonNull(C, state, Dest, destVal);
 846     if (!state)
 847       return;
 848
 849     // Get the value of the Src.
 850     SVal srcVal = state->getSVal(Source);
 851
 852     // Ensure the source is not null. If it is NULL there will be a
 853     // NULL pointer dereference.
 854     state = checkNonNull(C, state, Source, srcVal);
 855     if (!state)
 856       return;
 857
 858     // Ensure the accesses are valid and that the buffers do not overlap.
 859     const char * const writeWarning =
 860       "Memory copy function overflows destination buffer";
 861     state = CheckBufferAccess(C, state, Size, Dest, Source,
 862                               writeWarning, /* sourceWarning = */ NULL);
 863     if (Restricted)
 864       state = CheckOverlap(C, state, Size, Dest, Source);
 865
 866     if (!state)
 867       return;
 868
 869     // If this is mempcpy, get the byte after the last byte copied and
 870     // bind the expr.
 871     if (IsMempcpy) {
 872       loc::MemRegionVal *destRegVal = dyn_cast<loc::MemRegionVal>(&destVal);
 873       assert(destRegVal && "Destination should be a known MemRegionVal here");
 874
 875       // Get the length to copy.
 876       NonLoc *lenValNonLoc = dyn_cast<NonLoc>(&sizeVal);
 877
 878       if (lenValNonLoc) {
 879         // Get the byte after the last byte copied.
 880         SVal lastElement = C.getSValBuilder().evalBinOpLN(state, BO_Add,
 881                                                           *destRegVal,
 882                                                           *lenValNonLoc,
 883                                                           Dest->getType());
 884
 885         // The byte after the last byte copied is the return value.
 886         state = state->BindExpr(CE, lastElement);
 887       } else {
 888         // If we don't know how much we copied, we can at least
 889         // conjure a return value for later.
 890         unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 891         SVal result =
 892           C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
 893         state = state->BindExpr(CE, result);
 894       }
 895
 896     } else {
 897       // All other copies return the destination buffer.
 898       // (Well, bcopy() has a void return type, but this won't hurt.)
 899       state = state->BindExpr(CE, destVal);
 900     }
 901
 902     // Invalidate the destination.
 903     // FIXME: Even if we can't perfectly model the copy, we should see if we
 904     // can use LazyCompoundVals to copy the source values into the destination.
 905     // This would probably remove any existing bindings past the end of the
 906     // copied region, but that's still an improvement over blank invalidation.
 907     state = InvalidateBuffer(C, state, Dest, state->getSVal(Dest));
 908     C.addTransition(state);
 909   }
 910 }
 911
 912
 913 void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const {
 914   // void *memcpy(void *restrict dst, const void *restrict src, size_t n);
 915   // The return value is the address of the destination buffer.
 916   const Expr *Dest = CE->getArg(0);
 917   const GRState *state = C.getState();
 918
 919   evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true);
 920 }
 921
 922 void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const {
 923   // void *mempcpy(void *restrict dst, const void *restrict src, size_t n);
 924   // The return value is a pointer to the byte following the last written byte.
 925   const Expr *Dest = CE->getArg(0);
 926   const GRState *state = C.getState();
 927
 928   evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true, true);
 929 }
 930
 931 void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const {
 932   // void *memmove(void *dst, const void *src, size_t n);
 933   // The return value is the address of the destination buffer.
 934   const Expr *Dest = CE->getArg(0);
 935   const GRState *state = C.getState();
 936
 937   evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1));
 938 }
 939
 940 void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const {
 941   // void bcopy(const void *src, void *dst, size_t n);
 942   evalCopyCommon(C, CE, C.getState(),
 943                  CE->getArg(2), CE->getArg(1), CE->getArg(0));
 944 }
 945
 946 void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const {
 947   // int memcmp(const void *s1, const void *s2, size_t n);
 948   CurrentFunctionDescription = "memory comparison function";
 949
 950   const Expr *Left = CE->getArg(0);
 951   const Expr *Right = CE->getArg(1);
 952   const Expr *Size = CE->getArg(2);
 953
 954   const GRState *state = C.getState();
 955   SValBuilder &svalBuilder = C.getSValBuilder();
 956
 957   // See if the size argument is zero.
 958   SVal sizeVal = state->getSVal(Size);
 959   QualType sizeTy = Size->getType();
 960
 961   const GRState *stateZeroSize, *stateNonZeroSize;
 962   llvm::tie(stateZeroSize, stateNonZeroSize) =
 963     assumeZero(C, state, sizeVal, sizeTy);
 964
 965   // If the size can be zero, the result will be 0 in that case, and we don't
 966   // have to check either of the buffers.
 967   if (stateZeroSize) {
 968     state = stateZeroSize;
 969     state = state->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
 970     C.addTransition(state);
 971   }
 972
 973   // If the size can be nonzero, we have to check the other arguments.
 974   if (stateNonZeroSize) {
 975     state = stateNonZeroSize;
 976     // If we know the two buffers are the same, we know the result is 0.
 977     // First, get the two buffers' addresses. Another checker will have already
 978     // made sure they're not undefined.
 979     DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(state->getSVal(Left));
 980     DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(state->getSVal(Right));
 981
 982     // See if they are the same.
 983     DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
 984     const GRState *StSameBuf, *StNotSameBuf;
 985     llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
 986
 987     // If the two arguments might be the same buffer, we know the result is 0,
 988     // and we only need to check one size.
 989     if (StSameBuf) {
 990       state = StSameBuf;
 991       state = CheckBufferAccess(C, state, Size, Left);
 992       if (state) {
 993         state = StSameBuf->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
 994         C.addTransition(state);
 995       }
 996     }
 997
 998     // If the two arguments might be different buffers, we have to check the
 999     // size of both of them.
1000     if (StNotSameBuf) {
1001       state = StNotSameBuf;
1002       state = CheckBufferAccess(C, state, Size, Left, Right);
1003       if (state) {
1004         // The return value is the comparison result, which we don't know.
1005         unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1006         SVal CmpV = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
1007         state = state->BindExpr(CE, CmpV);
1008         C.addTransition(state);
1009       }
1010     }
1011   }
1012 }
1013
1014 void CStringChecker::evalstrLength(CheckerContext &C,
1015                                    const CallExpr *CE) const {
1016   // size_t strlen(const char *s);
1017   evalstrLengthCommon(C, CE, /* IsStrnlen = */ false);
1018 }
1019
1020 void CStringChecker::evalstrnLength(CheckerContext &C,
1021                                     const CallExpr *CE) const {
1022   // size_t strnlen(const char *s, size_t maxlen);
1023   evalstrLengthCommon(C, CE, /* IsStrnlen = */ true);
1024 }
1025
1026 void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
1027                                          bool IsStrnlen) const {
1028   CurrentFunctionDescription = "string length function";
1029   const GRState *state = C.getState();
1030
1031   if (IsStrnlen) {
1032     const Expr *maxlenExpr = CE->getArg(1);
1033     SVal maxlenVal = state->getSVal(maxlenExpr);
1034
1035     const GRState *stateZeroSize, *stateNonZeroSize;
1036     llvm::tie(stateZeroSize, stateNonZeroSize) =
1037       assumeZero(C, state, maxlenVal, maxlenExpr->getType());
1038
1039     // If the size can be zero, the result will be 0 in that case, and we don't
1040     // have to check the string itself.
1041     if (stateZeroSize) {
1042       SVal zero = C.getSValBuilder().makeZeroVal(CE->getType());
1043       stateZeroSize = stateZeroSize->BindExpr(CE, zero);
1044       C.addTransition(stateZeroSize);
1045     }
1046
1047     // If the size is GUARANTEED to be zero, we're done!
1048     if (!stateNonZeroSize)
1049       return;
1050
1051     // Otherwise, record the assumption that the size is nonzero.
1052     state = stateNonZeroSize;
1053   }
1054
1055   // Check that the string argument is non-null.
1056   const Expr *Arg = CE->getArg(0);
1057   SVal ArgVal = state->getSVal(Arg);
1058
1059   state = checkNonNull(C, state, Arg, ArgVal);
1060
1061   if (!state)
1062     return;
1063
1064   SVal strLength = getCStringLength(C, state, Arg, ArgVal);
1065
1066   // If the argument isn't a valid C string, there's no valid state to
1067   // transition to.
1068   if (strLength.isUndef())
1069     return;
1070
1071   DefinedOrUnknownSVal result = UnknownVal();
1072
1073   // If the check is for strnlen() then bind the return value to no more than
1074   // the maxlen value.
1075   if (IsStrnlen) {
1076     QualType cmpTy = C.getSValBuilder().getConditionType();
1077
1078     // It's a little unfortunate to be getting this again,
1079     // but it's not that expensive...
1080     const Expr *maxlenExpr = CE->getArg(1);
1081     SVal maxlenVal = state->getSVal(maxlenExpr);
1082
1083     NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1084     NonLoc *maxlenValNL = dyn_cast<NonLoc>(&maxlenVal);
1085
1086     if (strLengthNL && maxlenValNL) {
1087       const GRState *stateStringTooLong, *stateStringNotTooLong;
1088
1089       // Check if the strLength is greater than the maxlen.
1090       llvm::tie(stateStringTooLong, stateStringNotTooLong) =
1091         state->assume(cast<DefinedOrUnknownSVal>
1092                       (C.getSValBuilder().evalBinOpNN(state, BO_GT,
1093                                                       *strLengthNL,
1094                                                       *maxlenValNL,
1095                                                       cmpTy)));
1096
1097       if (stateStringTooLong && !stateStringNotTooLong) {
1098         // If the string is longer than maxlen, return maxlen.
1099         result = *maxlenValNL;
1100       } else if (stateStringNotTooLong && !stateStringTooLong) {
1101         // If the string is shorter than maxlen, return its length.
1102         result = *strLengthNL;
1103       }
1104     }
1105
1106     if (result.isUnknown()) {
1107       // If we don't have enough information for a comparison, there's
1108       // no guarantee the full string length will actually be returned.
1109       // All we know is the return value is the min of the string length
1110       // and the limit. This is better than nothing.
1111       unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1112       result = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
1113       NonLoc *resultNL = cast<NonLoc>(&result);
1114
1115       if (strLengthNL) {
1116         state = state->assume(cast<DefinedOrUnknownSVal>
1117                               (C.getSValBuilder().evalBinOpNN(state, BO_LE,
1118                                                               *resultNL,
1119                                                               *strLengthNL,
1120                                                               cmpTy)), true);
1121       }
1122
1123       if (maxlenValNL) {
1124         state = state->assume(cast<DefinedOrUnknownSVal>
1125                               (C.getSValBuilder().evalBinOpNN(state, BO_LE,
1126                                                               *resultNL,
1127                                                               *maxlenValNL,
1128                                                               cmpTy)), true);
1129       }
1130     }
1131
1132   } else {
1133     // This is a plain strlen(), not strnlen().
1134     result = cast<DefinedOrUnknownSVal>(strLength);
1135
1136     // If we don't know the length of the string, conjure a return
1137     // value, so it can be used in constraints, at least.
1138     if (result.isUnknown()) {
1139       unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1140       result = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
1141     }
1142   }
1143
1144   // Bind the return value.
1145   assert(!result.isUnknown() && "Should have conjured a value by now");
1146   state = state->BindExpr(CE, result);
1147   C.addTransition(state);
1148 }
1149
1150 void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const {
1151   // char *strcpy(char *restrict dst, const char *restrict src);
1152   evalStrcpyCommon(C, CE,
1153                    /* returnEnd = */ false,
1154                    /* isBounded = */ false,
1155                    /* isAppending = */ false);
1156 }
1157
1158 void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const {
1159   // char *strncpy(char *restrict dst, const char *restrict src, size_t n);
1160   evalStrcpyCommon(C, CE,
1161                    /* returnEnd = */ false,
1162                    /* isBounded = */ true,
1163                    /* isAppending = */ false);
1164 }
1165
1166 void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const {
1167   // char *stpcpy(char *restrict dst, const char *restrict src);
1168   evalStrcpyCommon(C, CE,
1169                    /* returnEnd = */ true,
1170                    /* isBounded = */ false,
1171                    /* isAppending = */ false);
1172 }
1173
1174 void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const {
1175   //char *strcat(char *restrict s1, const char *restrict s2);
1176   evalStrcpyCommon(C, CE,
1177                    /* returnEnd = */ false,
1178                    /* isBounded = */ false,
1179                    /* isAppending = */ true);
1180 }
1181
1182 void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const {
1183   //char *strncat(char *restrict s1, const char *restrict s2, size_t n);
1184   evalStrcpyCommon(C, CE,
1185                    /* returnEnd = */ false,
1186                    /* isBounded = */ true,
1187                    /* isAppending = */ true);
1188 }
1189
1190 void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE,
1191                                       bool returnEnd, bool isBounded,
1192                                       bool isAppending) const {
1193   CurrentFunctionDescription = "string copy function";
1194   const GRState *state = C.getState();
1195
1196   // Check that the destination is non-null.
1197   const Expr *Dst = CE->getArg(0);
1198   SVal DstVal = state->getSVal(Dst);
1199
1200   state = checkNonNull(C, state, Dst, DstVal);
1201   if (!state)
1202     return;
1203
1204   // Check that the source is non-null.
1205   const Expr *srcExpr = CE->getArg(1);
1206   SVal srcVal = state->getSVal(srcExpr);
1207   state = checkNonNull(C, state, srcExpr, srcVal);
1208   if (!state)
1209     return;
1210
1211   // Get the string length of the source.
1212   SVal strLength = getCStringLength(C, state, srcExpr, srcVal);
1213
1214   // If the source isn't a valid C string, give up.
1215   if (strLength.isUndef())
1216     return;
1217
1218   SValBuilder &svalBuilder = C.getSValBuilder();
1219   QualType cmpTy = svalBuilder.getConditionType();
1220   QualType sizeTy = svalBuilder.getContext().getSizeType();
1221
1222   // These two values allow checking two kinds of errors:
1223   // - actual overflows caused by a source that doesn't fit in the destination
1224   // - potential overflows caused by a bound that could exceed the destination
1225   SVal amountCopied = UnknownVal();
1226   SVal maxLastElementIndex = UnknownVal();
1227   const char *boundWarning = NULL;
1228
1229   // If the function is strncpy, strncat, etc... it is bounded.
1230   if (isBounded) {
1231     // Get the max number of characters to copy.
1232     const Expr *lenExpr = CE->getArg(2);
1233     SVal lenVal = state->getSVal(lenExpr);
1234
1235     // Protect against misdeclared strncpy().
1236     lenVal = svalBuilder.evalCast(lenVal, sizeTy, lenExpr->getType());
1237
1238     NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1239     NonLoc *lenValNL = dyn_cast<NonLoc>(&lenVal);
1240
1241     // If we know both values, we might be able to figure out how much
1242     // we're copying.
1243     if (strLengthNL && lenValNL) {
1244       const GRState *stateSourceTooLong, *stateSourceNotTooLong;
1245
1246       // Check if the max number to copy is less than the length of the src.
1247       // If the bound is equal to the source length, strncpy won't null-
1248       // terminate the result!
1249       llvm::tie(stateSourceTooLong, stateSourceNotTooLong) =
1250         state->assume(cast<DefinedOrUnknownSVal>
1251                       (svalBuilder.evalBinOpNN(state, BO_GE, *strLengthNL,
1252                                                *lenValNL, cmpTy)));
1253
1254       if (stateSourceTooLong && !stateSourceNotTooLong) {
1255         // Max number to copy is less than the length of the src, so the actual
1256         // strLength copied is the max number arg.
1257         state = stateSourceTooLong;
1258         amountCopied = lenVal;
1259
1260       } else if (!stateSourceTooLong && stateSourceNotTooLong) {
1261         // The source buffer entirely fits in the bound.
1262         state = stateSourceNotTooLong;
1263         amountCopied = strLength;
1264       }
1265     }
1266
1267     // We still want to know if the bound is known to be too large.
1268     if (lenValNL) {
1269       if (isAppending) {
1270         // For strncat, the check is strlen(dst) + lenVal < sizeof(dst)
1271
1272         // Get the string length of the destination. If the destination is
1273         // memory that can't have a string length, we shouldn't be copying
1274         // into it anyway.
1275         SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1276         if (dstStrLength.isUndef())
1277           return;
1278
1279         if (NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength)) {
1280           maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Add,
1281                                                         *lenValNL,
1282                                                         *dstStrLengthNL,
1283                                                         sizeTy);
1284           boundWarning = "Size argument is greater than the free space in the "
1285                          "destination buffer";
1286         }
1287
1288       } else {
1289         // For strncpy, this is just checking that lenVal <= sizeof(dst)
1290         // (Yes, strncpy and strncat differ in how they treat termination.
1291         // strncat ALWAYS terminates, but strncpy doesn't.)
1292         NonLoc one = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
1293         maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL,
1294                                                       one, sizeTy);
1295         boundWarning = "Size argument is greater than the length of the "
1296                        "destination buffer";
1297       }
1298     }
1299
1300     // If we couldn't pin down the copy length, at least bound it.
1301     // FIXME: We should actually run this code path for append as well, but
1302     // right now it creates problems with constraints (since we can end up
1303     // trying to pass constraints from symbol to symbol).
1304     if (amountCopied.isUnknown() && !isAppending) {
1305       // Try to get a "hypothetical" string length symbol, which we can later
1306       // set as a real value if that turns out to be the case.
1307       amountCopied = getCStringLength(C, state, lenExpr, srcVal, true);
1308       assert(!amountCopied.isUndef());
1309
1310       if (NonLoc *amountCopiedNL = dyn_cast<NonLoc>(&amountCopied)) {
1311         if (lenValNL) {
1312           // amountCopied <= lenVal
1313           SVal copiedLessThanBound = svalBuilder.evalBinOpNN(state, BO_LE,
1314                                                              *amountCopiedNL,
1315                                                              *lenValNL,
1316                                                              cmpTy);
1317           state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanBound),
1318                                 true);
1319           if (!state)
1320             return;
1321         }
1322
1323         if (strLengthNL) {
1324           // amountCopied <= strlen(source)
1325           SVal copiedLessThanSrc = svalBuilder.evalBinOpNN(state, BO_LE,
1326                                                            *amountCopiedNL,
1327                                                            *strLengthNL,
1328                                                            cmpTy);
1329           state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanSrc),
1330                                 true);
1331           if (!state)
1332             return;
1333         }
1334       }
1335     }
1336
1337   } else {
1338     // The function isn't bounded. The amount copied should match the length
1339     // of the source buffer.
1340     amountCopied = strLength;
1341   }
1342
1343   assert(state);
1344
1345   // This represents the number of characters copied into the destination
1346   // buffer. (It may not actually be the strlen if the destination buffer
1347   // is not terminated.)
1348   SVal finalStrLength = UnknownVal();
1349
1350   // If this is an appending function (strcat, strncat...) then set the
1351   // string length to strlen(src) + strlen(dst) since the buffer will
1352   // ultimately contain both.
1353   if (isAppending) {
1354     // Get the string length of the destination. If the destination is memory
1355     // that can't have a string length, we shouldn't be copying into it anyway.
1356     SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1357     if (dstStrLength.isUndef())
1358       return;
1359
1360     NonLoc *srcStrLengthNL = dyn_cast<NonLoc>(&amountCopied);
1361     NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength);
1362
1363     // If we know both string lengths, we might know the final string length.
1364     if (srcStrLengthNL && dstStrLengthNL) {
1365       // Make sure the two lengths together don't overflow a size_t.
1366       state = checkAdditionOverflow(C, state, *srcStrLengthNL, *dstStrLengthNL);
1367       if (!state)
1368         return;
1369
1370       finalStrLength = svalBuilder.evalBinOpNN(state, BO_Add, *srcStrLengthNL,
1371                                                *dstStrLengthNL, sizeTy);
1372     }
1373
1374     // If we couldn't get a single value for the final string length,
1375     // we can at least bound it by the individual lengths.
1376     if (finalStrLength.isUnknown()) {
1377       // Try to get a "hypothetical" string length symbol, which we can later
1378       // set as a real value if that turns out to be the case.
1379       finalStrLength = getCStringLength(C, state, CE, DstVal, true);
1380       assert(!finalStrLength.isUndef());
1381
1382       if (NonLoc *finalStrLengthNL = dyn_cast<NonLoc>(&finalStrLength)) {
1383         if (srcStrLengthNL) {
1384           // finalStrLength >= srcStrLength
1385           SVal sourceInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1386                                                         *finalStrLengthNL,
1387                                                         *srcStrLengthNL,
1388                                                         cmpTy);
1389           state = state->assume(cast<DefinedOrUnknownSVal>(sourceInResult),
1390                                 true);
1391           if (!state)
1392             return;
1393         }
1394
1395         if (dstStrLengthNL) {
1396           // finalStrLength >= dstStrLength
1397           SVal destInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1398                                                       *finalStrLengthNL,
1399                                                       *dstStrLengthNL,
1400                                                       cmpTy);
1401           state = state->assume(cast<DefinedOrUnknownSVal>(destInResult),
1402                                 true);
1403           if (!state)
1404             return;
1405         }
1406       }
1407     }
1408
1409   } else {
1410     // Otherwise, this is a copy-over function (strcpy, strncpy, ...), and
1411     // the final string length will match the input string length.
1412     finalStrLength = amountCopied;
1413   }
1414
1415   // The final result of the function will either be a pointer past the last
1416   // copied element, or a pointer to the start of the destination buffer.
1417   SVal Result = (returnEnd ? UnknownVal() : DstVal);
1418
1419   assert(state);
1420
1421   // If the destination is a MemRegion, try to check for a buffer overflow and
1422   // record the new string length.
1423   if (loc::MemRegionVal *dstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) {
1424     QualType ptrTy = Dst->getType();
1425
1426     // If we have an exact value on a bounded copy, use that to check for
1427     // overflows, rather than our estimate about how much is actually copied.
1428     if (boundWarning) {
1429       if (NonLoc *maxLastNL = dyn_cast<NonLoc>(&maxLastElementIndex)) {
1430         SVal maxLastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1431                                                       *maxLastNL, ptrTy);
1432         state = CheckLocation(C, state, CE->getArg(2), maxLastElement,
1433                               boundWarning);
1434         if (!state)
1435           return;
1436       }
1437     }
1438
1439     // Then, if the final length is known...
1440     if (NonLoc *knownStrLength = dyn_cast<NonLoc>(&finalStrLength)) {
1441       SVal lastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1442                                                  *knownStrLength, ptrTy);
1443
1444       // ...and we haven't checked the bound, we'll check the actual copy.
1445       if (!boundWarning) {
1446         const char * const warningMsg =
1447           "String copy function overflows destination buffer";
1448         state = CheckLocation(C, state, Dst, lastElement, warningMsg);
1449         if (!state)
1450           return;
1451       }
1452
1453       // If this is a stpcpy-style copy, the last element is the return value.
1454       if (returnEnd)
1455         Result = lastElement;
1456     }
1457
1458     // Invalidate the destination. This must happen before we set the C string
1459     // length because invalidation will clear the length.
1460     // FIXME: Even if we can't perfectly model the copy, we should see if we
1461     // can use LazyCompoundVals to copy the source values into the destination.
1462     // This would probably remove any existing bindings past the end of the
1463     // string, but that's still an improvement over blank invalidation.
1464     state = InvalidateBuffer(C, state, Dst, *dstRegVal);
1465
1466     // Set the C string length of the destination, if we know it.
1467     if (isBounded && !isAppending) {
1468       // strncpy is annoying in that it doesn't guarantee to null-terminate
1469       // the result string. If the original string didn't fit entirely inside
1470       // the bound (including the null-terminator), we don't know how long the
1471       // result is.
1472       if (amountCopied != strLength)
1473         finalStrLength = UnknownVal();
1474     }
1475     state = setCStringLength(state, dstRegVal->getRegion(), finalStrLength);
1476   }
1477
1478   assert(state);
1479
1480   // If this is a stpcpy-style copy, but we were unable to check for a buffer
1481   // overflow, we still need a result. Conjure a return value.
1482   if (returnEnd && Result.isUnknown()) {
1483     unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1484     Result = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
1485   }
1486
1487   // Set the return value.
1488   state = state->BindExpr(CE, Result);
1489   C.addTransition(state);
1490 }
1491
1492 void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const {
1493   //int strcmp(const char *s1, const char *s2);
1494   evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ false);
1495 }
1496
1497 void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const {
1498   //int strncmp(const char *s1, const char *s2, size_t n);
1499   evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ false);
1500 }
1501
1502 void CStringChecker::evalStrcasecmp(CheckerContext &C,
1503                                     const CallExpr *CE) const {
1504   //int strcasecmp(const char *s1, const char *s2);
1505   evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ true);
1506 }
1507
1508 void CStringChecker::evalStrncasecmp(CheckerContext &C,
1509                                      const CallExpr *CE) const {
1510   //int strncasecmp(const char *s1, const char *s2, size_t n);
1511   evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ true);
1512 }
1513
1514 void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
1515                                       bool isBounded, bool ignoreCase) const {
1516   CurrentFunctionDescription = "string comparison function";
1517   const GRState *state = C.getState();
1518
1519   // Check that the first string is non-null
1520   const Expr *s1 = CE->getArg(0);
1521   SVal s1Val = state->getSVal(s1);
1522   state = checkNonNull(C, state, s1, s1Val);
1523   if (!state)
1524     return;
1525
1526   // Check that the second string is non-null.
1527   const Expr *s2 = CE->getArg(1);
1528   SVal s2Val = state->getSVal(s2);
1529   state = checkNonNull(C, state, s2, s2Val);
1530   if (!state)
1531     return;
1532
1533   // Get the string length of the first string or give up.
1534   SVal s1Length = getCStringLength(C, state, s1, s1Val);
1535   if (s1Length.isUndef())
1536     return;
1537
1538   // Get the string length of the second string or give up.
1539   SVal s2Length = getCStringLength(C, state, s2, s2Val);
1540   if (s2Length.isUndef())
1541     return;
1542
1543   // If we know the two buffers are the same, we know the result is 0.
1544   // First, get the two buffers' addresses. Another checker will have already
1545   // made sure they're not undefined.
1546   DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(s1Val);
1547   DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(s2Val);
1548
1549   // See if they are the same.
1550   SValBuilder &svalBuilder = C.getSValBuilder();
1551   DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
1552   const GRState *StSameBuf, *StNotSameBuf;
1553   llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
1554
1555   // If the two arguments might be the same buffer, we know the result is 0,
1556   // and we only need to check one size.
1557   if (StSameBuf) {
1558     StSameBuf = StSameBuf->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
1559     C.addTransition(StSameBuf);
1560
1561     // If the two arguments are GUARANTEED to be the same, we're done!
1562     if (!StNotSameBuf)
1563       return;
1564   }
1565
1566   assert(StNotSameBuf);
1567   state = StNotSameBuf;
1568
1569   // At this point we can go about comparing the two buffers.
1570   // For now, we only do this if they're both known string literals.
1571
1572   // Attempt to extract string literals from both expressions.
1573   const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val);
1574   const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val);
1575   bool canComputeResult = false;
1576
1577   if (s1StrLiteral && s2StrLiteral) {
1578     llvm::StringRef s1StrRef = s1StrLiteral->getString();
1579     llvm::StringRef s2StrRef = s2StrLiteral->getString();
1580
1581     if (isBounded) {
1582       // Get the max number of characters to compare.
1583       const Expr *lenExpr = CE->getArg(2);
1584       SVal lenVal = state->getSVal(lenExpr);
1585
1586       // If the length is known, we can get the right substrings.
1587       if (const llvm::APSInt *len = svalBuilder.getKnownValue(state, lenVal)) {
1588         // Create substrings of each to compare the prefix.
1589         s1StrRef = s1StrRef.substr(0, (size_t)len->getZExtValue());
1590         s2StrRef = s2StrRef.substr(0, (size_t)len->getZExtValue());
1591         canComputeResult = true;
1592       }
1593     } else {
1594       // This is a normal, unbounded strcmp.
1595       canComputeResult = true;
1596     }
1597
1598     if (canComputeResult) {
1599       // Real strcmp stops at null characters.
1600       size_t s1Term = s1StrRef.find('\0');
1601       if (s1Term != llvm::StringRef::npos)
1602         s1StrRef = s1StrRef.substr(0, s1Term);
1603
1604       size_t s2Term = s2StrRef.find('\0');
1605       if (s2Term != llvm::StringRef::npos)
1606         s2StrRef = s2StrRef.substr(0, s2Term);
1607
1608       // Use StringRef's comparison methods to compute the actual result.
1609       int result;
1610
1611       if (ignoreCase) {
1612         // Compare string 1 to string 2 the same way strcasecmp() does.
1613         result = s1StrRef.compare_lower(s2StrRef);
1614       } else {
1615         // Compare string 1 to string 2 the same way strcmp() does.
1616         result = s1StrRef.compare(s2StrRef);
1617       }
1618
1619       // Build the SVal of the comparison and bind the return value.
1620       SVal resultVal = svalBuilder.makeIntVal(result, CE->getType());
1621       state = state->BindExpr(CE, resultVal);
1622     }
1623   }
1624
1625   if (!canComputeResult) {
1626     // Conjure a symbolic value. It's the best we can do.
1627     unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1628     SVal resultVal = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
1629     state = state->BindExpr(CE, resultVal);
1630   }
1631
1632   // Record this as a possible path.
1633   C.addTransition(state);
1634 }
1635
1636 //===----------------------------------------------------------------------===//
1637 // The driver method, and other Checker callbacks.
1638 //===----------------------------------------------------------------------===//
1639
1640 bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
1641   // Get the callee.  All the functions we care about are C functions
1642   // with simple identifiers.
1643   const GRState *state = C.getState();
1644   const Expr *Callee = CE->getCallee();
1645   const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();
1646
1647   if (!FD)
1648     return false;
1649
1650   // Get the name of the callee. If it's a builtin, strip off the prefix.
1651   IdentifierInfo *II = FD->getIdentifier();
1652   if (!II)   // if no identifier, not a simple C function
1653     return false;
1654   llvm::StringRef Name = II->getName();
1655   if (Name.startswith("__builtin_"))
1656     Name = Name.substr(10);
1657
1658   FnCheck evalFunction = llvm::StringSwitch<FnCheck>(Name)
1659     .Cases("memcpy", "__memcpy_chk", &CStringChecker::evalMemcpy)
1660     .Cases("mempcpy", "__mempcpy_chk", &CStringChecker::evalMempcpy)
1661     .Cases("memcmp", "bcmp", &CStringChecker::evalMemcmp)
1662     .Cases("memmove", "__memmove_chk", &CStringChecker::evalMemmove)
1663     .Cases("strcpy", "__strcpy_chk", &CStringChecker::evalStrcpy)
1664     .Cases("strncpy", "__strncpy_chk", &CStringChecker::evalStrncpy)
1665     .Cases("stpcpy", "__stpcpy_chk", &CStringChecker::evalStpcpy)
1666     .Cases("strcat", "__strcat_chk", &CStringChecker::evalStrcat)
1667     .Cases("strncat", "__strncat_chk", &CStringChecker::evalStrncat)
1668     .Case("strlen", &CStringChecker::evalstrLength)
1669     .Case("strnlen", &CStringChecker::evalstrnLength)
1670     .Case("strcmp", &CStringChecker::evalStrcmp)
1671     .Case("strncmp", &CStringChecker::evalStrncmp)
1672     .Case("strcasecmp", &CStringChecker::evalStrcasecmp)
1673     .Case("strncasecmp", &CStringChecker::evalStrncasecmp)
1674     .Case("bcopy", &CStringChecker::evalBcopy)
1675     .Default(NULL);
1676
1677   // If the callee isn't a string function, let another checker handle it.
1678   if (!evalFunction)
1679     return false;
1680
1681   // Make sure each function sets its own description.
1682   // (But don't bother in a release build.)
1683   assert(!(CurrentFunctionDescription = NULL));
1684
1685   // Check and evaluate the call.
1686   (this->*evalFunction)(C, CE);
1687   return true;
1688 }
1689
1690 void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
1691   // Record string length for char a[] = "abc";
1692   const GRState *state = C.getState();
1693
1694   for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
1695        I != E; ++I) {
1696     const VarDecl *D = dyn_cast<VarDecl>(*I);
1697     if (!D)
1698       continue;
1699
1700     // FIXME: Handle array fields of structs.
1701     if (!D->getType()->isArrayType())
1702       continue;
1703
1704     const Expr *Init = D->getInit();
1705     if (!Init)
1706       continue;
1707     if (!isa<StringLiteral>(Init))
1708       continue;
1709
1710     Loc VarLoc = state->getLValue(D, C.getPredecessor()->getLocationContext());
1711     const MemRegion *MR = VarLoc.getAsRegion();
1712     if (!MR)
1713       continue;
1714
1715     SVal StrVal = state->getSVal(Init);
1716     assert(StrVal.isValid() && "Initializer string is unknown or undefined");
1717     DefinedOrUnknownSVal strLength
1718       = cast<DefinedOrUnknownSVal>(getCStringLength(C, state, Init, StrVal));
1719
1720     state = state->set<CStringLength>(MR, strLength);
1721   }
1722
1723   C.addTransition(state);
1724 }
1725
1726 bool CStringChecker::wantsRegionChangeUpdate(const GRState *state) const {
1727   CStringLength::EntryMap Entries = state->get<CStringLength>();
1728   return !Entries.isEmpty();
1729 }
1730
1731 const GRState *
1732 CStringChecker::checkRegionChanges(const GRState *state,
1733                                    const StoreManager::InvalidatedSymbols *,
1734                                    const MemRegion * const *Begin,
1735                                    const MemRegion * const *End) const {
1736   CStringLength::EntryMap Entries = state->get<CStringLength>();
1737   if (Entries.isEmpty())
1738     return state;
1739
1740   llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
1741   llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
1742
1743   // First build sets for the changed regions and their super-regions.
1744   for ( ; Begin != End; ++Begin) {
1745     const MemRegion *MR = *Begin;
1746     Invalidated.insert(MR);
1747
1748     SuperRegions.insert(MR);
1749     while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
1750       MR = SR->getSuperRegion();
1751       SuperRegions.insert(MR);
1752     }
1753   }
1754
1755   CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1756
1757   // Then loop over the entries in the current state.
1758   for (CStringLength::EntryMap::iterator I = Entries.begin(),
1759        E = Entries.end(); I != E; ++I) {
1760     const MemRegion *MR = I.getKey();
1761
1762     // Is this entry for a super-region of a changed region?
1763     if (SuperRegions.count(MR)) {
1764       Entries = F.remove(Entries, MR);
1765       continue;
1766     }
1767
1768     // Is this entry for a sub-region of a changed region?
1769     const MemRegion *Super = MR;
1770     while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
1771       Super = SR->getSuperRegion();
1772       if (Invalidated.count(Super)) {
1773         Entries = F.remove(Entries, MR);
1774         break;
1775       }
1776     }
1777   }
1778
1779   return state->set<CStringLength>(Entries);
1780 }
1781
1782 void CStringChecker::checkLiveSymbols(const GRState *state,
1783                                       SymbolReaper &SR) const {
1784   // Mark all symbols in our string length map as valid.
1785   CStringLength::EntryMap Entries = state->get<CStringLength>();
1786
1787   for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1788        I != E; ++I) {
1789     SVal Len = I.getData();
1790
1791     for (SVal::symbol_iterator si = Len.symbol_begin(), se = Len.symbol_end();
1792          si != se; ++si)
1793       SR.markInUse(*si);
1794   }
1795 }
1796
1797 void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
1798                                       CheckerContext &C) const {
1799   if (!SR.hasDeadSymbols())
1800     return;
1801
1802   const GRState *state = C.getState();
1803   CStringLength::EntryMap Entries = state->get<CStringLength>();
1804   if (Entries.isEmpty())
1805     return;
1806
1807   CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1808   for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1809        I != E; ++I) {
1810     SVal Len = I.getData();
1811     if (SymbolRef Sym = Len.getAsSymbol()) {
1812       if (SR.isDead(Sym))
1813         Entries = F.remove(Entries, I.getKey());
1814     }
1815   }
1816
1817   state = state->set<CStringLength>(Entries);
1818   C.generateNode(state);
1819 }
1820
1821 void ento::registerCStringChecker(CheckerManager &mgr) {
1822   mgr.registerChecker<CStringChecker>();
1823 }