blob: c60eca8fc0960b0ba231b5c379e497c327ac0e87 [file] [log] [blame]
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001//= 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 "GRExprEngineExperimentalChecks.h"
16#include "clang/Checker/BugReporter/BugType.h"
17#include "clang/Checker/PathSensitive/CheckerVisitor.h"
Jordy Rosea5261542010-08-14 21:02:52 +000018#include "clang/Checker/PathSensitive/GRStateTrait.h"
Jordy Roseccbf7ee2010-07-06 23:11:01 +000019#include "llvm/ADT/StringSwitch.h"
20
21using namespace clang;
22
23namespace {
24class CStringChecker : public CheckerVisitor<CStringChecker> {
Jordy Rosee64f3112010-08-16 07:51:42 +000025 BugType *BT_Null, *BT_Bounds, *BT_BoundsWrite, *BT_Overlap, *BT_NotCString;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000026public:
27 CStringChecker()
Jordy Rosee64f3112010-08-16 07:51:42 +000028 : BT_Null(0), BT_Bounds(0), BT_BoundsWrite(0), BT_Overlap(0), BT_NotCString(0)
29 {}
Jordy Roseccbf7ee2010-07-06 23:11:01 +000030 static void *getTag() { static int tag; return &tag; }
31
32 bool EvalCallExpr(CheckerContext &C, const CallExpr *CE);
Jordy Rosea5261542010-08-14 21:02:52 +000033 void PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS);
34 void MarkLiveSymbols(const GRState *state, SymbolReaper &SR);
35 void EvalDeadSymbols(CheckerContext &C, SymbolReaper &SR);
36 bool WantsRegionChangeUpdate(const GRState *state);
37
38 const GRState *EvalRegionChanges(const GRState *state,
39 const MemRegion * const *Begin,
40 const MemRegion * const *End,
41 bool*);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000042
Jordy Rosed325ffb2010-07-08 23:57:29 +000043 typedef void (CStringChecker::*FnCheck)(CheckerContext &, const CallExpr *);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000044
Jordy Rosed325ffb2010-07-08 23:57:29 +000045 void EvalMemcpy(CheckerContext &C, const CallExpr *CE);
46 void EvalMemmove(CheckerContext &C, const CallExpr *CE);
47 void EvalBcopy(CheckerContext &C, const CallExpr *CE);
48 void EvalCopyCommon(CheckerContext &C, const GRState *state,
49 const Expr *Size, const Expr *Source, const Expr *Dest,
50 bool Restricted = false);
51
52 void EvalMemcmp(CheckerContext &C, const CallExpr *CE);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000053
Jordy Rose19c5dd12010-07-27 01:37:31 +000054 void EvalStrlen(CheckerContext &C, const CallExpr *CE);
55
Jordy Rosee64f3112010-08-16 07:51:42 +000056 void EvalStrcpy(CheckerContext &C, const CallExpr *CE);
57 void EvalStpcpy(CheckerContext &C, const CallExpr *CE);
58 void EvalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool ReturnEnd);
59
Jordy Roseccbf7ee2010-07-06 23:11:01 +000060 // Utility methods
Jordy Rosed325ffb2010-07-08 23:57:29 +000061 std::pair<const GRState*, const GRState*>
62 AssumeZero(CheckerContext &C, const GRState *state, SVal V, QualType Ty);
63
Jordy Rosee64f3112010-08-16 07:51:42 +000064 const GRState *SetCStringLength(const GRState *state, const MemRegion *MR,
65 SVal StrLen);
Jordy Rosea5261542010-08-14 21:02:52 +000066 SVal GetCStringLengthForRegion(CheckerContext &C, const GRState *&state,
67 const Expr *Ex, const MemRegion *MR);
68 SVal GetCStringLength(CheckerContext &C, const GRState *&state,
Jordy Rose19c5dd12010-07-27 01:37:31 +000069 const Expr *Ex, SVal Buf);
70
Jordy Rosee64f3112010-08-16 07:51:42 +000071 const GRState *InvalidateBuffer(CheckerContext &C, const GRState *state,
72 const Expr *Ex, SVal V);
73
Jordy Rose19c5dd12010-07-27 01:37:31 +000074 bool SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
75 const MemRegion *MR);
76
77 // Re-usable checks
Jordy Rosea6b808c2010-07-07 07:48:06 +000078 const GRState *CheckNonNull(CheckerContext &C, const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +000079 const Expr *S, SVal l);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000080 const GRState *CheckLocation(CheckerContext &C, const GRState *state,
Jordy Rosee64f3112010-08-16 07:51:42 +000081 const Expr *S, SVal l,
82 bool IsDestination = false);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000083 const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state,
84 const Expr *Size,
85 const Expr *FirstBuf,
Jordy Rosee64f3112010-08-16 07:51:42 +000086 const Expr *SecondBuf = NULL,
87 bool FirstIsDestination = false);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000088 const GRState *CheckOverlap(CheckerContext &C, const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +000089 const Expr *Size, const Expr *First,
90 const Expr *Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000091 void EmitOverlapBug(CheckerContext &C, const GRState *state,
92 const Stmt *First, const Stmt *Second);
93};
Jordy Rosea5261542010-08-14 21:02:52 +000094
95class CStringLength {
96public:
97 typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap;
98};
Jordy Roseccbf7ee2010-07-06 23:11:01 +000099} //end anonymous namespace
100
Jordy Rosea5261542010-08-14 21:02:52 +0000101namespace clang {
102 template <>
103 struct GRStateTrait<CStringLength>
104 : public GRStatePartialTrait<CStringLength::EntryMap> {
105 static void *GDMIndex() { return CStringChecker::getTag(); }
106 };
107}
108
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000109void clang::RegisterCStringChecker(GRExprEngine &Eng) {
110 Eng.registerCheck(new CStringChecker());
111}
112
Jordy Rosed325ffb2010-07-08 23:57:29 +0000113//===----------------------------------------------------------------------===//
114// Individual checks and utility methods.
115//===----------------------------------------------------------------------===//
116
117std::pair<const GRState*, const GRState*>
118CStringChecker::AssumeZero(CheckerContext &C, const GRState *state, SVal V,
119 QualType Ty) {
120 DefinedSVal *Val = dyn_cast<DefinedSVal>(&V);
121 if (!Val)
122 return std::pair<const GRState*, const GRState *>(state, state);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000123
124 ValueManager &ValMgr = C.getValueManager();
Ted Kremenek846eabd2010-12-01 21:28:31 +0000125 SValBuilder &SV = ValMgr.getSValBuilder();
Jordy Rosea6b808c2010-07-07 07:48:06 +0000126
Jordy Rosed325ffb2010-07-08 23:57:29 +0000127 DefinedOrUnknownSVal Zero = ValMgr.makeZeroVal(Ty);
128 DefinedOrUnknownSVal ValIsZero = SV.EvalEQ(state, *Val, Zero);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000129
Jordy Rosed325ffb2010-07-08 23:57:29 +0000130 return state->Assume(ValIsZero);
131}
Jordy Rosea6b808c2010-07-07 07:48:06 +0000132
Jordy Rosed325ffb2010-07-08 23:57:29 +0000133const GRState *CStringChecker::CheckNonNull(CheckerContext &C,
134 const GRState *state,
135 const Expr *S, SVal l) {
136 // If a previous check has failed, propagate the failure.
137 if (!state)
138 return NULL;
139
140 const GRState *stateNull, *stateNonNull;
141 llvm::tie(stateNull, stateNonNull) = AssumeZero(C, state, l, S->getType());
142
143 if (stateNull && !stateNonNull) {
144 ExplodedNode *N = C.GenerateSink(stateNull);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000145 if (!N)
146 return NULL;
147
Jordy Rosed325ffb2010-07-08 23:57:29 +0000148 if (!BT_Null)
149 BT_Null = new BuiltinBug("API",
Jordy Rosea6b808c2010-07-07 07:48:06 +0000150 "Null pointer argument in call to byte string function");
151
152 // Generate a report for this bug.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000153 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000154 EnhancedBugReport *report = new EnhancedBugReport(*BT,
155 BT->getDescription(), N);
156
157 report->addRange(S->getSourceRange());
158 report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, S);
159 C.EmitReport(report);
160 return NULL;
161 }
162
163 // From here on, assume that the value is non-null.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000164 assert(stateNonNull);
165 return stateNonNull;
Jordy Rosea6b808c2010-07-07 07:48:06 +0000166}
167
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000168// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
169const GRState *CStringChecker::CheckLocation(CheckerContext &C,
170 const GRState *state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000171 const Expr *S, SVal l,
172 bool IsDestination) {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000173 // If a previous check has failed, propagate the failure.
174 if (!state)
175 return NULL;
176
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000177 // Check for out of bound array element access.
178 const MemRegion *R = l.getAsRegion();
179 if (!R)
180 return state;
181
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000182 const ElementRegion *ER = dyn_cast<ElementRegion>(R);
183 if (!ER)
184 return state;
185
Zhongxing Xu018220c2010-08-11 06:10:55 +0000186 assert(ER->getValueType() == C.getASTContext().CharTy &&
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000187 "CheckLocation should only be called with char* ElementRegions");
188
189 // Get the size of the array.
190 const SubRegion *Super = cast<SubRegion>(ER->getSuperRegion());
191 ValueManager &ValMgr = C.getValueManager();
192 SVal Extent = ValMgr.convertToArrayIndex(Super->getExtent(ValMgr));
193 DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);
194
195 // Get the index of the accessed element.
Gabor Greif89b06582010-09-09 10:51:37 +0000196 DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000197
198 const GRState *StInBound = state->AssumeInBound(Idx, Size, true);
199 const GRState *StOutBound = state->AssumeInBound(Idx, Size, false);
200 if (StOutBound && !StInBound) {
201 ExplodedNode *N = C.GenerateSink(StOutBound);
202 if (!N)
203 return NULL;
204
Jordy Rosee64f3112010-08-16 07:51:42 +0000205 BuiltinBug *BT;
206 if (IsDestination) {
207 if (!BT_BoundsWrite) {
208 BT_BoundsWrite = new BuiltinBug("Out-of-bound array access",
209 "Byte string function overflows destination buffer");
210 }
211 BT = static_cast<BuiltinBug*>(BT_BoundsWrite);
212 } else {
213 if (!BT_Bounds) {
214 BT_Bounds = new BuiltinBug("Out-of-bound array access",
215 "Byte string function accesses out-of-bound array element");
216 }
217 BT = static_cast<BuiltinBug*>(BT_Bounds);
218 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000219
220 // FIXME: It would be nice to eventually make this diagnostic more clear,
221 // e.g., by referencing the original declaration or by saying *why* this
222 // reference is outside the range.
223
224 // Generate a report for this bug.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000225 RangedBugReport *report = new RangedBugReport(*BT, BT->getDescription(), N);
226
227 report->addRange(S->getSourceRange());
228 C.EmitReport(report);
229 return NULL;
230 }
231
232 // Array bound check succeeded. From this point forward the array bound
233 // should always succeed.
234 return StInBound;
235}
236
237const GRState *CStringChecker::CheckBufferAccess(CheckerContext &C,
238 const GRState *state,
239 const Expr *Size,
240 const Expr *FirstBuf,
Jordy Rosee64f3112010-08-16 07:51:42 +0000241 const Expr *SecondBuf,
242 bool FirstIsDestination) {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000243 // If a previous check has failed, propagate the failure.
244 if (!state)
245 return NULL;
246
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000247 ValueManager &VM = C.getValueManager();
Ted Kremenek846eabd2010-12-01 21:28:31 +0000248 SValBuilder &SV = VM.getSValBuilder();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000249 ASTContext &Ctx = C.getASTContext();
250
Jordy Rose070f2f42010-08-16 23:25:19 +0000251 QualType SizeTy = Size->getType();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000252 QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
253
Jordy Rosea6b808c2010-07-07 07:48:06 +0000254 // Check that the first buffer is non-null.
255 SVal BufVal = state->getSVal(FirstBuf);
256 state = CheckNonNull(C, state, FirstBuf, BufVal);
257 if (!state)
258 return NULL;
259
Jordy Rosed325ffb2010-07-08 23:57:29 +0000260 // Get the access length and make sure it is known.
261 SVal LengthVal = state->getSVal(Size);
262 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
263 if (!Length)
264 return state;
265
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000266 // Compute the offset of the last element to be accessed: size-1.
267 NonLoc One = cast<NonLoc>(VM.makeIntVal(1, SizeTy));
John McCall2de56d12010-08-25 11:45:40 +0000268 NonLoc LastOffset = cast<NonLoc>(SV.EvalBinOpNN(state, BO_Sub,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000269 *Length, One, SizeTy));
270
Jordy Rosea6b808c2010-07-07 07:48:06 +0000271 // Check that the first buffer is sufficently long.
Jordy Roseb6a40262010-08-05 23:11:30 +0000272 SVal BufStart = SV.EvalCast(BufVal, PtrTy, FirstBuf->getType());
273 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
John McCall2de56d12010-08-25 11:45:40 +0000274 SVal BufEnd = SV.EvalBinOpLN(state, BO_Add, *BufLoc,
Jordy Roseb6a40262010-08-05 23:11:30 +0000275 LastOffset, PtrTy);
Jordy Rosee64f3112010-08-16 07:51:42 +0000276 state = CheckLocation(C, state, FirstBuf, BufEnd, FirstIsDestination);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000277
Jordy Roseb6a40262010-08-05 23:11:30 +0000278 // If the buffer isn't large enough, abort.
279 if (!state)
280 return NULL;
281 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000282
283 // If there's a second buffer, check it as well.
284 if (SecondBuf) {
285 BufVal = state->getSVal(SecondBuf);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000286 state = CheckNonNull(C, state, SecondBuf, BufVal);
287 if (!state)
288 return NULL;
289
Jordy Roseb6a40262010-08-05 23:11:30 +0000290 BufStart = SV.EvalCast(BufVal, PtrTy, SecondBuf->getType());
291 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
John McCall2de56d12010-08-25 11:45:40 +0000292 SVal BufEnd = SV.EvalBinOpLN(state, BO_Add, *BufLoc,
Jordy Roseb6a40262010-08-05 23:11:30 +0000293 LastOffset, PtrTy);
294 state = CheckLocation(C, state, SecondBuf, BufEnd);
295 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000296 }
297
298 // Large enough or not, return this state!
299 return state;
300}
301
302const GRState *CStringChecker::CheckOverlap(CheckerContext &C,
303 const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000304 const Expr *Size,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000305 const Expr *First,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000306 const Expr *Second) {
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000307 // Do a simple check for overlap: if the two arguments are from the same
308 // buffer, see if the end of the first is greater than the start of the second
309 // or vice versa.
310
Jordy Rosed325ffb2010-07-08 23:57:29 +0000311 // If a previous check has failed, propagate the failure.
312 if (!state)
313 return NULL;
314
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000315 ValueManager &VM = state->getStateManager().getValueManager();
Ted Kremenek846eabd2010-12-01 21:28:31 +0000316 SValBuilder &SV = VM.getSValBuilder();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000317 ASTContext &Ctx = VM.getContext();
318 const GRState *stateTrue, *stateFalse;
319
320 // Get the buffer values and make sure they're known locations.
321 SVal FirstVal = state->getSVal(First);
322 SVal SecondVal = state->getSVal(Second);
323
324 Loc *FirstLoc = dyn_cast<Loc>(&FirstVal);
325 if (!FirstLoc)
326 return state;
327
328 Loc *SecondLoc = dyn_cast<Loc>(&SecondVal);
329 if (!SecondLoc)
330 return state;
331
332 // Are the two values the same?
333 DefinedOrUnknownSVal EqualTest = SV.EvalEQ(state, *FirstLoc, *SecondLoc);
334 llvm::tie(stateTrue, stateFalse) = state->Assume(EqualTest);
335
336 if (stateTrue && !stateFalse) {
337 // If the values are known to be equal, that's automatically an overlap.
338 EmitOverlapBug(C, stateTrue, First, Second);
339 return NULL;
340 }
341
342 // Assume the two expressions are not equal.
343 assert(stateFalse);
344 state = stateFalse;
345
346 // Which value comes first?
347 QualType CmpTy = Ctx.IntTy;
John McCall2de56d12010-08-25 11:45:40 +0000348 SVal Reverse = SV.EvalBinOpLL(state, BO_GT,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000349 *FirstLoc, *SecondLoc, CmpTy);
350 DefinedOrUnknownSVal *ReverseTest = dyn_cast<DefinedOrUnknownSVal>(&Reverse);
351 if (!ReverseTest)
352 return state;
353
354 llvm::tie(stateTrue, stateFalse) = state->Assume(*ReverseTest);
355
356 if (stateTrue) {
357 if (stateFalse) {
358 // If we don't know which one comes first, we can't perform this test.
359 return state;
360 } else {
361 // Switch the values so that FirstVal is before SecondVal.
362 Loc *tmpLoc = FirstLoc;
363 FirstLoc = SecondLoc;
364 SecondLoc = tmpLoc;
365
366 // Switch the Exprs as well, so that they still correspond.
367 const Expr *tmpExpr = First;
368 First = Second;
369 Second = tmpExpr;
370 }
371 }
372
373 // Get the length, and make sure it too is known.
374 SVal LengthVal = state->getSVal(Size);
375 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
376 if (!Length)
377 return state;
378
379 // Convert the first buffer's start address to char*.
380 // Bail out if the cast fails.
381 QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
382 SVal FirstStart = SV.EvalCast(*FirstLoc, CharPtrTy, First->getType());
383 Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart);
384 if (!FirstStartLoc)
385 return state;
386
387 // Compute the end of the first buffer. Bail out if THAT fails.
John McCall2de56d12010-08-25 11:45:40 +0000388 SVal FirstEnd = SV.EvalBinOpLN(state, BO_Add,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000389 *FirstStartLoc, *Length, CharPtrTy);
390 Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd);
391 if (!FirstEndLoc)
392 return state;
393
394 // Is the end of the first buffer past the start of the second buffer?
John McCall2de56d12010-08-25 11:45:40 +0000395 SVal Overlap = SV.EvalBinOpLL(state, BO_GT,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000396 *FirstEndLoc, *SecondLoc, CmpTy);
397 DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap);
398 if (!OverlapTest)
399 return state;
400
401 llvm::tie(stateTrue, stateFalse) = state->Assume(*OverlapTest);
402
403 if (stateTrue && !stateFalse) {
404 // Overlap!
405 EmitOverlapBug(C, stateTrue, First, Second);
406 return NULL;
407 }
408
409 // Assume the two expressions don't overlap.
410 assert(stateFalse);
411 return stateFalse;
412}
413
414void CStringChecker::EmitOverlapBug(CheckerContext &C, const GRState *state,
415 const Stmt *First, const Stmt *Second) {
416 ExplodedNode *N = C.GenerateSink(state);
417 if (!N)
418 return;
419
420 if (!BT_Overlap)
421 BT_Overlap = new BugType("Unix API", "Improper arguments");
422
423 // Generate a report for this bug.
424 RangedBugReport *report =
425 new RangedBugReport(*BT_Overlap,
426 "Arguments must not be overlapping buffers", N);
427 report->addRange(First->getSourceRange());
428 report->addRange(Second->getSourceRange());
429
430 C.EmitReport(report);
431}
432
Jordy Rosee64f3112010-08-16 07:51:42 +0000433const GRState *CStringChecker::SetCStringLength(const GRState *state,
434 const MemRegion *MR,
435 SVal StrLen) {
436 assert(!StrLen.isUndef() && "Attempt to set an undefined string length");
437 if (StrLen.isUnknown())
438 return state;
439
440 MR = MR->StripCasts();
441
442 switch (MR->getKind()) {
443 case MemRegion::StringRegionKind:
444 // FIXME: This can happen if we strcpy() into a string region. This is
445 // undefined [C99 6.4.5p6], but we should still warn about it.
446 return state;
447
448 case MemRegion::SymbolicRegionKind:
449 case MemRegion::AllocaRegionKind:
450 case MemRegion::VarRegionKind:
451 case MemRegion::FieldRegionKind:
452 case MemRegion::ObjCIvarRegionKind:
453 return state->set<CStringLength>(MR, StrLen);
454
455 case MemRegion::ElementRegionKind:
456 // FIXME: Handle element regions by upper-bounding the parent region's
457 // string length.
458 return state;
459
460 default:
461 // Other regions (mostly non-data) can't have a reliable C string length.
462 // For now, just ignore the change.
463 // FIXME: These are rare but not impossible. We should output some kind of
464 // warning for things like strcpy((char[]){'a', 0}, "b");
465 return state;
466 }
467}
468
Jordy Rosea5261542010-08-14 21:02:52 +0000469SVal CStringChecker::GetCStringLengthForRegion(CheckerContext &C,
470 const GRState *&state,
471 const Expr *Ex,
472 const MemRegion *MR) {
473 // If there's a recorded length, go ahead and return it.
474 const SVal *Recorded = state->get<CStringLength>(MR);
475 if (Recorded)
476 return *Recorded;
477
478 // Otherwise, get a new symbol and update the state.
479 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
480 ValueManager &ValMgr = C.getValueManager();
481 QualType SizeTy = ValMgr.getContext().getSizeType();
482 SVal Strlen = ValMgr.getMetadataSymbolVal(getTag(), MR, Ex, SizeTy, Count);
483
484 state = state->set<CStringLength>(MR, Strlen);
485 return Strlen;
486}
487
488SVal CStringChecker::GetCStringLength(CheckerContext &C, const GRState *&state,
Jordy Rose19c5dd12010-07-27 01:37:31 +0000489 const Expr *Ex, SVal Buf) {
490 const MemRegion *MR = Buf.getAsRegion();
491 if (!MR) {
492 // If we can't get a region, see if it's something we /know/ isn't a
493 // C string. In the context of locations, the only time we can issue such
494 // a warning is for labels.
495 if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
Jordy Rosea5261542010-08-14 21:02:52 +0000496 if (ExplodedNode *N = C.GenerateNode(state)) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000497 if (!BT_NotCString)
498 BT_NotCString = new BuiltinBug("API",
499 "Argument is not a null-terminated string.");
500
501 llvm::SmallString<120> buf;
502 llvm::raw_svector_ostream os(buf);
503 os << "Argument to byte string function is the address of the label '"
504 << Label->getLabel()->getID()->getName()
505 << "', which is not a null-terminated string";
506
507 // Generate a report for this bug.
508 EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
509 os.str(), N);
510
511 report->addRange(Ex->getSourceRange());
512 C.EmitReport(report);
513 }
514
515 return UndefinedVal();
516 }
517
Jordy Rosea5261542010-08-14 21:02:52 +0000518 // If it's not a region and not a label, give up.
519 return UnknownVal();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000520 }
521
Jordy Rosea5261542010-08-14 21:02:52 +0000522 // If we have a region, strip casts from it and see if we can figure out
523 // its length. For anything we can't figure out, just return UnknownVal.
524 MR = MR->StripCasts();
525
526 switch (MR->getKind()) {
527 case MemRegion::StringRegionKind: {
528 // Modifying the contents of string regions is undefined [C99 6.4.5p6],
529 // so we can assume that the byte length is the correct C string length.
530 ValueManager &ValMgr = C.getValueManager();
531 QualType SizeTy = ValMgr.getContext().getSizeType();
532 const StringLiteral *Str = cast<StringRegion>(MR)->getStringLiteral();
533 return ValMgr.makeIntVal(Str->getByteLength(), SizeTy);
534 }
535 case MemRegion::SymbolicRegionKind:
536 case MemRegion::AllocaRegionKind:
537 case MemRegion::VarRegionKind:
538 case MemRegion::FieldRegionKind:
539 case MemRegion::ObjCIvarRegionKind:
540 return GetCStringLengthForRegion(C, state, Ex, MR);
541 case MemRegion::CompoundLiteralRegionKind:
542 // FIXME: Can we track this? Is it necessary?
543 return UnknownVal();
544 case MemRegion::ElementRegionKind:
545 // FIXME: How can we handle this? It's not good enough to subtract the
546 // offset from the base string length; consider "123\x00567" and &a[5].
547 return UnknownVal();
548 default:
549 // Other regions (mostly non-data) can't have a reliable C string length.
550 // In this case, an error is emitted and UndefinedVal is returned.
551 // The caller should always be prepared to handle this case.
552 if (ExplodedNode *N = C.GenerateNode(state)) {
553 if (!BT_NotCString)
554 BT_NotCString = new BuiltinBug("API",
555 "Argument is not a null-terminated string.");
556
557 llvm::SmallString<120> buf;
558 llvm::raw_svector_ostream os(buf);
559
560 os << "Argument to byte string function is ";
561
562 if (SummarizeRegion(os, C.getASTContext(), MR))
563 os << ", which is not a null-terminated string";
564 else
565 os << "not a null-terminated string";
566
567 // Generate a report for this bug.
568 EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
569 os.str(), N);
570
571 report->addRange(Ex->getSourceRange());
572 C.EmitReport(report);
573 }
574
575 return UndefinedVal();
576 }
Jordy Rose19c5dd12010-07-27 01:37:31 +0000577}
578
Jordy Rosee64f3112010-08-16 07:51:42 +0000579const GRState *CStringChecker::InvalidateBuffer(CheckerContext &C,
580 const GRState *state,
581 const Expr *E, SVal V) {
582 Loc *L = dyn_cast<Loc>(&V);
583 if (!L)
584 return state;
585
586 // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
587 // some assumptions about the value that CFRefCount can't. Even so, it should
588 // probably be refactored.
589 if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) {
590 const MemRegion *R = MR->getRegion()->StripCasts();
591
592 // Are we dealing with an ElementRegion? If so, we should be invalidating
593 // the super-region.
594 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
595 R = ER->getSuperRegion();
596 // FIXME: What about layers of ElementRegions?
597 }
598
599 // Invalidate this region.
600 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
601 return state->InvalidateRegion(R, E, Count, NULL);
602 }
603
604 // If we have a non-region value by chance, just remove the binding.
605 // FIXME: is this necessary or correct? This handles the non-Region
606 // cases. Is it ever valid to store to these?
607 return state->unbindLoc(*L);
608}
609
Jordy Rose19c5dd12010-07-27 01:37:31 +0000610bool CStringChecker::SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
611 const MemRegion *MR) {
612 const TypedRegion *TR = dyn_cast<TypedRegion>(MR);
613 if (!TR)
614 return false;
615
616 switch (TR->getKind()) {
617 case MemRegion::FunctionTextRegionKind: {
618 const FunctionDecl *FD = cast<FunctionTextRegion>(TR)->getDecl();
619 if (FD)
620 os << "the address of the function '" << FD << "'";
621 else
622 os << "the address of a function";
623 return true;
624 }
625 case MemRegion::BlockTextRegionKind:
626 os << "block text";
627 return true;
628 case MemRegion::BlockDataRegionKind:
629 os << "a block";
630 return true;
631 case MemRegion::CXXThisRegionKind:
Zhongxing Xu02fe28c2010-11-26 08:52:48 +0000632 case MemRegion::CXXTempObjectRegionKind:
633 os << "a C++ temp object of type " << TR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000634 return true;
635 case MemRegion::VarRegionKind:
Zhongxing Xu018220c2010-08-11 06:10:55 +0000636 os << "a variable of type" << TR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000637 return true;
638 case MemRegion::FieldRegionKind:
Zhongxing Xu018220c2010-08-11 06:10:55 +0000639 os << "a field of type " << TR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000640 return true;
641 case MemRegion::ObjCIvarRegionKind:
Zhongxing Xu018220c2010-08-11 06:10:55 +0000642 os << "an instance variable of type " << TR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000643 return true;
644 default:
645 return false;
646 }
647}
648
Jordy Rosed325ffb2010-07-08 23:57:29 +0000649//===----------------------------------------------------------------------===//
650// Evaluation of individual function calls.
651//===----------------------------------------------------------------------===//
652
653void CStringChecker::EvalCopyCommon(CheckerContext &C, const GRState *state,
654 const Expr *Size, const Expr *Dest,
655 const Expr *Source, bool Restricted) {
656 // See if the size argument is zero.
657 SVal SizeVal = state->getSVal(Size);
658 QualType SizeTy = Size->getType();
659
660 const GRState *StZeroSize, *StNonZeroSize;
661 llvm::tie(StZeroSize, StNonZeroSize) = AssumeZero(C, state, SizeVal, SizeTy);
662
663 // If the size is zero, there won't be any actual memory access.
664 if (StZeroSize)
665 C.addTransition(StZeroSize);
666
667 // If the size can be nonzero, we have to check the other arguments.
668 if (StNonZeroSize) {
669 state = StNonZeroSize;
Jordy Rosee64f3112010-08-16 07:51:42 +0000670 state = CheckBufferAccess(C, state, Size, Dest, Source,
671 /* FirstIsDst = */ true);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000672 if (Restricted)
673 state = CheckOverlap(C, state, Size, Dest, Source);
Jordy Rosee64f3112010-08-16 07:51:42 +0000674
675 if (state) {
676 // Invalidate the destination.
677 // FIXME: Even if we can't perfectly model the copy, we should see if we
678 // can use LazyCompoundVals to copy the source values into the destination.
679 // This would probably remove any existing bindings past the end of the
680 // copied region, but that's still an improvement over blank invalidation.
681 state = InvalidateBuffer(C, state, Dest, state->getSVal(Dest));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000682 C.addTransition(state);
Jordy Rosee64f3112010-08-16 07:51:42 +0000683 }
Jordy Rosed325ffb2010-07-08 23:57:29 +0000684 }
685}
686
687
688void CStringChecker::EvalMemcpy(CheckerContext &C, const CallExpr *CE) {
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000689 // void *memcpy(void *restrict dst, const void *restrict src, size_t n);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000690 // The return value is the address of the destination buffer.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000691 const Expr *Dest = CE->getArg(0);
692 const GRState *state = C.getState();
693 state = state->BindExpr(CE, state->getSVal(Dest));
694 EvalCopyCommon(C, state, CE->getArg(2), Dest, CE->getArg(1), true);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000695}
696
Jordy Rosed325ffb2010-07-08 23:57:29 +0000697void CStringChecker::EvalMemmove(CheckerContext &C, const CallExpr *CE) {
698 // void *memmove(void *dst, const void *src, size_t n);
699 // The return value is the address of the destination buffer.
700 const Expr *Dest = CE->getArg(0);
701 const GRState *state = C.getState();
702 state = state->BindExpr(CE, state->getSVal(Dest));
703 EvalCopyCommon(C, state, CE->getArg(2), Dest, CE->getArg(1));
704}
705
706void CStringChecker::EvalBcopy(CheckerContext &C, const CallExpr *CE) {
707 // void bcopy(const void *src, void *dst, size_t n);
708 EvalCopyCommon(C, C.getState(), CE->getArg(2), CE->getArg(1), CE->getArg(0));
709}
710
711void CStringChecker::EvalMemcmp(CheckerContext &C, const CallExpr *CE) {
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000712 // int memcmp(const void *s1, const void *s2, size_t n);
713 const Expr *Left = CE->getArg(0);
714 const Expr *Right = CE->getArg(1);
715 const Expr *Size = CE->getArg(2);
716
717 const GRState *state = C.getState();
718 ValueManager &ValMgr = C.getValueManager();
Ted Kremenek846eabd2010-12-01 21:28:31 +0000719 SValBuilder &SV = ValMgr.getSValBuilder();
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000720
Jordy Rosed325ffb2010-07-08 23:57:29 +0000721 // See if the size argument is zero.
722 SVal SizeVal = state->getSVal(Size);
723 QualType SizeTy = Size->getType();
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000724
Jordy Rosed325ffb2010-07-08 23:57:29 +0000725 const GRState *StZeroSize, *StNonZeroSize;
726 llvm::tie(StZeroSize, StNonZeroSize) = AssumeZero(C, state, SizeVal, SizeTy);
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000727
Jordy Rosed325ffb2010-07-08 23:57:29 +0000728 // If the size can be zero, the result will be 0 in that case, and we don't
729 // have to check either of the buffers.
730 if (StZeroSize) {
731 state = StZeroSize;
732 state = state->BindExpr(CE, ValMgr.makeZeroVal(CE->getType()));
733 C.addTransition(state);
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000734 }
735
Jordy Rosed325ffb2010-07-08 23:57:29 +0000736 // If the size can be nonzero, we have to check the other arguments.
737 if (StNonZeroSize) {
738 state = StNonZeroSize;
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000739
Jordy Rosed325ffb2010-07-08 23:57:29 +0000740 // If we know the two buffers are the same, we know the result is 0.
741 // First, get the two buffers' addresses. Another checker will have already
742 // made sure they're not undefined.
743 DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(state->getSVal(Left));
744 DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(state->getSVal(Right));
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000745
Jordy Rosed325ffb2010-07-08 23:57:29 +0000746 // See if they are the same.
747 DefinedOrUnknownSVal SameBuf = SV.EvalEQ(state, LV, RV);
748 const GRState *StSameBuf, *StNotSameBuf;
749 llvm::tie(StSameBuf, StNotSameBuf) = state->Assume(SameBuf);
750
751 // If the two arguments might be the same buffer, we know the result is zero,
752 // and we only need to check one size.
753 if (StSameBuf) {
754 state = StSameBuf;
755 state = CheckBufferAccess(C, state, Size, Left);
756 if (state) {
757 state = StSameBuf->BindExpr(CE, ValMgr.makeZeroVal(CE->getType()));
758 C.addTransition(state);
759 }
760 }
761
762 // If the two arguments might be different buffers, we have to check the
763 // size of both of them.
764 if (StNotSameBuf) {
765 state = StNotSameBuf;
766 state = CheckBufferAccess(C, state, Size, Left, Right);
767 if (state) {
768 // The return value is the comparison result, which we don't know.
769 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Jordy Rosee64f3112010-08-16 07:51:42 +0000770 SVal CmpV = ValMgr.getConjuredSymbolVal(NULL, CE, Count);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000771 state = state->BindExpr(CE, CmpV);
772 C.addTransition(state);
773 }
774 }
775 }
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000776}
777
Jordy Rose19c5dd12010-07-27 01:37:31 +0000778void CStringChecker::EvalStrlen(CheckerContext &C, const CallExpr *CE) {
779 // size_t strlen(const char *s);
780 const GRState *state = C.getState();
781 const Expr *Arg = CE->getArg(0);
782 SVal ArgVal = state->getSVal(Arg);
783
784 // Check that the argument is non-null.
785 state = CheckNonNull(C, state, Arg, ArgVal);
786
787 if (state) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000788 SVal StrLen = GetCStringLength(C, state, Arg, ArgVal);
Jordy Rosea5261542010-08-14 21:02:52 +0000789
790 // If the argument isn't a valid C string, there's no valid state to
791 // transition to.
792 if (StrLen.isUndef())
793 return;
794
795 // If GetCStringLength couldn't figure out the length, conjure a return
796 // value, so it can be used in constraints, at least.
797 if (StrLen.isUnknown()) {
798 ValueManager &ValMgr = C.getValueManager();
799 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Jordy Rosee64f3112010-08-16 07:51:42 +0000800 StrLen = ValMgr.getConjuredSymbolVal(NULL, CE, Count);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000801 }
Jordy Rosea5261542010-08-14 21:02:52 +0000802
803 // Bind the return value.
804 state = state->BindExpr(CE, StrLen);
805 C.addTransition(state);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000806 }
807}
808
Jordy Rosee64f3112010-08-16 07:51:42 +0000809void CStringChecker::EvalStrcpy(CheckerContext &C, const CallExpr *CE) {
810 // char *strcpy(char *restrict dst, const char *restrict src);
811 EvalStrcpyCommon(C, CE, /* ReturnEnd = */ false);
812}
813
814void CStringChecker::EvalStpcpy(CheckerContext &C, const CallExpr *CE) {
815 // char *stpcpy(char *restrict dst, const char *restrict src);
816 EvalStrcpyCommon(C, CE, /* ReturnEnd = */ true);
817}
818
819void CStringChecker::EvalStrcpyCommon(CheckerContext &C, const CallExpr *CE,
820 bool ReturnEnd) {
821 const GRState *state = C.getState();
822
823 // Check that the destination is non-null
824 const Expr *Dst = CE->getArg(0);
825 SVal DstVal = state->getSVal(Dst);
826
827 state = CheckNonNull(C, state, Dst, DstVal);
828 if (!state)
829 return;
830
831 // Check that the source is non-null.
832 const Expr *Src = CE->getArg(1);
833 SVal SrcVal = state->getSVal(Src);
834
835 state = CheckNonNull(C, state, Src, SrcVal);
836 if (!state)
837 return;
838
839 // Get the string length of the source.
840 SVal StrLen = GetCStringLength(C, state, Src, SrcVal);
841
842 // If the source isn't a valid C string, give up.
843 if (StrLen.isUndef())
844 return;
845
846 SVal Result = (ReturnEnd ? UnknownVal() : DstVal);
847
848 // If the destination is a MemRegion, try to check for a buffer overflow and
849 // record the new string length.
850 if (loc::MemRegionVal *DstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) {
851 // If the length is known, we can check for an overflow.
852 if (NonLoc *KnownStrLen = dyn_cast<NonLoc>(&StrLen)) {
Ted Kremenek846eabd2010-12-01 21:28:31 +0000853 SValBuilder &SV = C.getSValBuilder();
Jordy Rosee64f3112010-08-16 07:51:42 +0000854
John McCall2de56d12010-08-25 11:45:40 +0000855 SVal LastElement = SV.EvalBinOpLN(state, BO_Add,
Jordy Rosee64f3112010-08-16 07:51:42 +0000856 *DstRegVal, *KnownStrLen,
857 Dst->getType());
858
859 state = CheckLocation(C, state, Dst, LastElement, /* IsDst = */ true);
860 if (!state)
861 return;
862
863 // If this is a stpcpy-style copy, the last element is the return value.
864 if (ReturnEnd)
865 Result = LastElement;
866 }
867
868 // Invalidate the destination. This must happen before we set the C string
869 // length because invalidation will clear the length.
870 // FIXME: Even if we can't perfectly model the copy, we should see if we
871 // can use LazyCompoundVals to copy the source values into the destination.
872 // This would probably remove any existing bindings past the end of the
873 // string, but that's still an improvement over blank invalidation.
874 state = InvalidateBuffer(C, state, Dst, *DstRegVal);
875
876 // Set the C string length of the destination.
877 state = SetCStringLength(state, DstRegVal->getRegion(), StrLen);
878 }
879
880 // If this is a stpcpy-style copy, but we were unable to check for a buffer
881 // overflow, we still need a result. Conjure a return value.
882 if (ReturnEnd && Result.isUnknown()) {
883 ValueManager &ValMgr = C.getValueManager();
884 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
885 StrLen = ValMgr.getConjuredSymbolVal(NULL, CE, Count);
886 }
887
888 // Set the return value.
889 state = state->BindExpr(CE, Result);
890 C.addTransition(state);
891}
892
Jordy Rosed325ffb2010-07-08 23:57:29 +0000893//===----------------------------------------------------------------------===//
Jordy Rosea5261542010-08-14 21:02:52 +0000894// The driver method, and other Checker callbacks.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000895//===----------------------------------------------------------------------===//
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000896
897bool CStringChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) {
898 // Get the callee. All the functions we care about are C functions
899 // with simple identifiers.
900 const GRState *state = C.getState();
901 const Expr *Callee = CE->getCallee();
902 const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();
903
904 if (!FD)
905 return false;
906
907 // Get the name of the callee. If it's a builtin, strip off the prefix.
Douglas Gregor90d26a42010-11-01 23:16:05 +0000908 IdentifierInfo *II = FD->getIdentifier();
909 if (!II) // if no identifier, not a simple C function
910 return false;
911 llvm::StringRef Name = II->getName();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000912 if (Name.startswith("__builtin_"))
913 Name = Name.substr(10);
914
915 FnCheck EvalFunction = llvm::StringSwitch<FnCheck>(Name)
Jordy Rosea6b808c2010-07-07 07:48:06 +0000916 .Cases("memcpy", "__memcpy_chk", &CStringChecker::EvalMemcpy)
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000917 .Cases("memcmp", "bcmp", &CStringChecker::EvalMemcmp)
Jordy Rosea6b808c2010-07-07 07:48:06 +0000918 .Cases("memmove", "__memmove_chk", &CStringChecker::EvalMemmove)
Jordy Rosee64f3112010-08-16 07:51:42 +0000919 .Cases("strcpy", "__strcpy_chk", &CStringChecker::EvalStrcpy)
920 .Cases("stpcpy", "__stpcpy_chk", &CStringChecker::EvalStpcpy)
Jordy Rose19c5dd12010-07-27 01:37:31 +0000921 .Case("strlen", &CStringChecker::EvalStrlen)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000922 .Case("bcopy", &CStringChecker::EvalBcopy)
923 .Default(NULL);
924
Jordy Rosed325ffb2010-07-08 23:57:29 +0000925 // If the callee isn't a string function, let another checker handle it.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000926 if (!EvalFunction)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000927 return false;
928
Jordy Rosed325ffb2010-07-08 23:57:29 +0000929 // Check and evaluate the call.
930 (this->*EvalFunction)(C, CE);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000931 return true;
932}
Jordy Rosea5261542010-08-14 21:02:52 +0000933
934void CStringChecker::PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS) {
935 // Record string length for char a[] = "abc";
936 const GRState *state = C.getState();
937
938 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
939 I != E; ++I) {
940 const VarDecl *D = dyn_cast<VarDecl>(*I);
941 if (!D)
942 continue;
943
944 // FIXME: Handle array fields of structs.
945 if (!D->getType()->isArrayType())
946 continue;
947
948 const Expr *Init = D->getInit();
949 if (!Init)
950 continue;
951 if (!isa<StringLiteral>(Init))
952 continue;
953
954 Loc VarLoc = state->getLValue(D, C.getPredecessor()->getLocationContext());
955 const MemRegion *MR = VarLoc.getAsRegion();
956 if (!MR)
957 continue;
958
959 SVal StrVal = state->getSVal(Init);
960 assert(StrVal.isValid() && "Initializer string is unknown or undefined");
961 DefinedOrUnknownSVal StrLen
962 = cast<DefinedOrUnknownSVal>(GetCStringLength(C, state, Init, StrVal));
963
964 state = state->set<CStringLength>(MR, StrLen);
965 }
966
967 C.addTransition(state);
968}
969
970bool CStringChecker::WantsRegionChangeUpdate(const GRState *state) {
971 CStringLength::EntryMap Entries = state->get<CStringLength>();
972 return !Entries.isEmpty();
973}
974
975const GRState *CStringChecker::EvalRegionChanges(const GRState *state,
976 const MemRegion * const *Begin,
977 const MemRegion * const *End,
978 bool *) {
979 CStringLength::EntryMap Entries = state->get<CStringLength>();
980 if (Entries.isEmpty())
981 return state;
982
983 llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
984 llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
985
986 // First build sets for the changed regions and their super-regions.
987 for ( ; Begin != End; ++Begin) {
988 const MemRegion *MR = *Begin;
989 Invalidated.insert(MR);
990
991 SuperRegions.insert(MR);
992 while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
993 MR = SR->getSuperRegion();
994 SuperRegions.insert(MR);
995 }
996 }
997
998 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
999
1000 // Then loop over the entries in the current state.
1001 for (CStringLength::EntryMap::iterator I = Entries.begin(),
1002 E = Entries.end(); I != E; ++I) {
1003 const MemRegion *MR = I.getKey();
1004
1005 // Is this entry for a super-region of a changed region?
1006 if (SuperRegions.count(MR)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001007 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001008 continue;
1009 }
1010
1011 // Is this entry for a sub-region of a changed region?
1012 const MemRegion *Super = MR;
1013 while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
1014 Super = SR->getSuperRegion();
1015 if (Invalidated.count(Super)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001016 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001017 break;
1018 }
1019 }
1020 }
1021
1022 return state->set<CStringLength>(Entries);
1023}
1024
1025void CStringChecker::MarkLiveSymbols(const GRState *state, SymbolReaper &SR) {
1026 // Mark all symbols in our string length map as valid.
1027 CStringLength::EntryMap Entries = state->get<CStringLength>();
1028
1029 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1030 I != E; ++I) {
1031 SVal Len = I.getData();
1032 if (SymbolRef Sym = Len.getAsSymbol())
1033 SR.markInUse(Sym);
1034 }
1035}
1036
1037void CStringChecker::EvalDeadSymbols(CheckerContext &C, SymbolReaper &SR) {
1038 if (!SR.hasDeadSymbols())
1039 return;
1040
1041 const GRState *state = C.getState();
1042 CStringLength::EntryMap Entries = state->get<CStringLength>();
1043 if (Entries.isEmpty())
1044 return;
1045
1046 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1047 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1048 I != E; ++I) {
1049 SVal Len = I.getData();
1050 if (SymbolRef Sym = Len.getAsSymbol()) {
1051 if (SR.isDead(Sym))
Ted Kremenek3baf6722010-11-24 00:54:37 +00001052 Entries = F.remove(Entries, I.getKey());
Jordy Rosea5261542010-08-14 21:02:52 +00001053 }
1054 }
1055
1056 state = state->set<CStringLength>(Entries);
1057 C.GenerateNode(state);
1058}