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

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