blob: b0eeca81e01953389d1a7926ed4be21cb92e7a09 [file] [log] [blame]
Ted Kremeneka90ccfe2008-01-31 19:34:24 +00001//= RValues.cpp - Abstract RValues for Path-Sens. Value Tracking -*- 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//
Zhongxing Xu1c96b242008-10-17 05:57:07 +000010// This file defines SVal, Loc, and NonLoc, classes that represent
Ted Kremeneka90ccfe2008-01-31 19:34:24 +000011// abstract r-values for use with path-sensitive value tracking.
12//
13//===----------------------------------------------------------------------===//
14
Ted Kremenek1309f9a2010-01-25 04:41:41 +000015#include "clang/Checker/PathSensitive/GRState.h"
Daniel Dunbarc4a1dea2008-08-11 05:35:13 +000016#include "clang/Basic/IdentifierTable.h"
Ted Kremeneka90ccfe2008-01-31 19:34:24 +000017
18using namespace clang;
19using llvm::dyn_cast;
20using llvm::cast;
21using llvm::APSInt;
22
23//===----------------------------------------------------------------------===//
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +000024// Symbol iteration within an SVal.
Ted Kremenek90e14812008-02-14 23:25:54 +000025//===----------------------------------------------------------------------===//
Ted Kremeneka6e4d212008-02-01 06:36:40 +000026
Ted Kremenek718c4f72008-04-29 22:17:41 +000027
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +000028//===----------------------------------------------------------------------===//
29// Utility methods.
30//===----------------------------------------------------------------------===//
Ted Kremeneka6e4d212008-02-01 06:36:40 +000031
Zhongxing Xu264e9372009-05-12 10:10:00 +000032bool SVal::hasConjuredSymbol() const {
33 if (const nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(this)) {
34 SymbolRef sym = SV->getSymbol();
35 if (isa<SymbolConjured>(sym))
36 return true;
37 }
38
39 if (const loc::MemRegionVal *RV = dyn_cast<loc::MemRegionVal>(this)) {
40 const MemRegion *R = RV->getRegion();
41 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
42 SymbolRef sym = SR->getSymbol();
43 if (isa<SymbolConjured>(sym))
44 return true;
Zhongxing Xu264e9372009-05-12 10:10:00 +000045 }
46 }
47
48 return false;
49}
50
Ted Kremenekabd46e12009-08-28 04:49:15 +000051const FunctionDecl *SVal::getAsFunctionDecl() const {
Zhongxing Xu369f4472009-04-20 05:24:46 +000052 if (const loc::MemRegionVal* X = dyn_cast<loc::MemRegionVal>(this)) {
53 const MemRegion* R = X->getRegion();
Ted Kremenekeb1c7a02009-11-25 01:32:22 +000054 if (const FunctionTextRegion *CTR = R->getAs<FunctionTextRegion>())
Ted Kremenekabd46e12009-08-28 04:49:15 +000055 return CTR->getDecl();
Zhongxing Xu369f4472009-04-20 05:24:46 +000056 }
57
Ted Kremenekabd46e12009-08-28 04:49:15 +000058 return NULL;
Zhongxing Xu369f4472009-04-20 05:24:46 +000059}
60
Mike Stump1eb44332009-09-09 15:08:12 +000061/// getAsLocSymbol - If this SVal is a location (subclasses Loc) and
Zhongxing Xu369f4472009-04-20 05:24:46 +000062/// wraps a symbol, return that SymbolRef. Otherwise return 0.
63// FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
Ted Kremenek94c96982009-03-03 22:06:47 +000064SymbolRef SVal::getAsLocSymbol() const {
Zhongxing Xu46d1a4f2010-08-21 11:00:26 +000065 if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this))
66 return X->getLoc().getAsLocSymbol();
67
Ted Kremenek94c96982009-03-03 22:06:47 +000068 if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this)) {
Zhongxing Xu479529e2009-11-10 02:17:20 +000069 const MemRegion *R = X->StripCasts();
Ted Kremenekf7a0cf42009-07-29 21:43:22 +000070 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
71 return SymR->getSymbol();
Ted Kremenek94c96982009-03-03 22:06:47 +000072 }
Ted Kremenekf7a0cf42009-07-29 21:43:22 +000073 return NULL;
Ted Kremenek94c96982009-03-03 22:06:47 +000074}
75
Zhongxing Xuc8023782010-03-10 04:58:55 +000076/// Get the symbol in the SVal or its base region.
77SymbolRef SVal::getLocSymbolInBase() const {
78 const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this);
79
80 if (!X)
81 return 0;
82
83 const MemRegion *R = X->getRegion();
84
85 while (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
86 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR))
87 return SymR->getSymbol();
88 else
89 R = SR->getSuperRegion();
90 }
91
92 return 0;
93}
94
Ted Kremenek94c96982009-03-03 22:06:47 +000095/// getAsSymbol - If this Sval wraps a symbol return that SymbolRef.
Zhongxing Xu369f4472009-04-20 05:24:46 +000096/// Otherwise return 0.
97// FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
Ted Kremenek94c96982009-03-03 22:06:47 +000098SymbolRef SVal::getAsSymbol() const {
99 if (const nonloc::SymbolVal *X = dyn_cast<nonloc::SymbolVal>(this))
100 return X->getSymbol();
Mike Stump1eb44332009-09-09 15:08:12 +0000101
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000102 if (const nonloc::SymExprVal *X = dyn_cast<nonloc::SymExprVal>(this))
103 if (SymbolRef Y = dyn_cast<SymbolData>(X->getSymbolicExpression()))
104 return Y;
Mike Stump1eb44332009-09-09 15:08:12 +0000105
Ted Kremenek94c96982009-03-03 22:06:47 +0000106 return getAsLocSymbol();
107}
108
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000109/// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
110/// return that expression. Otherwise return NULL.
111const SymExpr *SVal::getAsSymbolicExpression() const {
112 if (const nonloc::SymExprVal *X = dyn_cast<nonloc::SymExprVal>(this))
113 return X->getSymbolicExpression();
Mike Stump1eb44332009-09-09 15:08:12 +0000114
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000115 return getAsSymbol();
116}
117
Zhongxing Xuedb883c2009-06-30 11:52:40 +0000118const MemRegion *SVal::getAsRegion() const {
119 if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this))
120 return X->getRegion();
121
Zhongxing Xu604848a2010-01-11 06:52:53 +0000122 if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this)) {
123 return X->getLoc().getAsRegion();
124 }
125
Zhongxing Xuedb883c2009-06-30 11:52:40 +0000126 return 0;
127}
128
Zhongxing Xu479529e2009-11-10 02:17:20 +0000129const MemRegion *loc::MemRegionVal::StripCasts() const {
Ted Kremenek0e3ec3f2009-07-29 18:14:27 +0000130 const MemRegion *R = getRegion();
Zhongxing Xu479529e2009-11-10 02:17:20 +0000131 return R ? R->StripCasts() : NULL;
Ted Kremenek0e3ec3f2009-07-29 18:14:27 +0000132}
133
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000134bool SVal::symbol_iterator::operator==(const symbol_iterator &X) const {
135 return itr == X.itr;
136}
137
138bool SVal::symbol_iterator::operator!=(const symbol_iterator &X) const {
139 return itr != X.itr;
140}
141
142SVal::symbol_iterator::symbol_iterator(const SymExpr *SE) {
143 itr.push_back(SE);
Mike Stump1eb44332009-09-09 15:08:12 +0000144 while (!isa<SymbolData>(itr.back())) expand();
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000145}
146
147SVal::symbol_iterator& SVal::symbol_iterator::operator++() {
148 assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
149 assert(isa<SymbolData>(itr.back()));
Mike Stump1eb44332009-09-09 15:08:12 +0000150 itr.pop_back();
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000151 if (!itr.empty())
152 while (!isa<SymbolData>(itr.back())) expand();
153 return *this;
154}
155
156SymbolRef SVal::symbol_iterator::operator*() {
157 assert(!itr.empty() && "attempting to dereference an 'end' iterator");
158 return cast<SymbolData>(itr.back());
159}
160
161void SVal::symbol_iterator::expand() {
162 const SymExpr *SE = itr.back();
163 itr.pop_back();
Mike Stump1eb44332009-09-09 15:08:12 +0000164
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000165 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
166 itr.push_back(SIE->getLHS());
167 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000168 }
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000169 else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
170 itr.push_back(SSE->getLHS());
171 itr.push_back(SSE->getRHS());
172 return;
173 }
Mike Stump1eb44332009-09-09 15:08:12 +0000174
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000175 assert(false && "unhandled expansion case");
176}
177
Zhongxing Xubfcaf802010-02-05 02:26:30 +0000178const void *nonloc::LazyCompoundVal::getStore() const {
179 return static_cast<const LazyCompoundValData*>(Data)->getStore();
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000180}
181
182const TypedRegion *nonloc::LazyCompoundVal::getRegion() const {
183 return static_cast<const LazyCompoundValData*>(Data)->getRegion();
184}
185
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000186//===----------------------------------------------------------------------===//
Ted Kremeneka6fac4e2008-10-30 18:01:28 +0000187// Other Iterators.
188//===----------------------------------------------------------------------===//
189
190nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
191 return getValue()->begin();
192}
193
194nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
195 return getValue()->end();
196}
197
198//===----------------------------------------------------------------------===//
Ted Kremenek40fc5c72008-07-18 15:54:51 +0000199// Useful predicates.
200//===----------------------------------------------------------------------===//
201
Zhongxing Xub10a7c22009-11-09 06:52:44 +0000202bool SVal::isConstant() const {
203 return isa<nonloc::ConcreteInt>(this) || isa<loc::ConcreteInt>(this);
204}
205
Tom Caredb2fa8a2010-07-06 21:43:29 +0000206bool SVal::isConstant(int I) const {
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000207 if (isa<loc::ConcreteInt>(*this))
Tom Caredb2fa8a2010-07-06 21:43:29 +0000208 return cast<loc::ConcreteInt>(*this).getValue() == I;
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000209 else if (isa<nonloc::ConcreteInt>(*this))
Tom Caredb2fa8a2010-07-06 21:43:29 +0000210 return cast<nonloc::ConcreteInt>(*this).getValue() == I;
Ted Kremenek40fc5c72008-07-18 15:54:51 +0000211 else
212 return false;
213}
214
Tom Caredb2fa8a2010-07-06 21:43:29 +0000215bool SVal::isZeroConstant() const {
216 return isConstant(0);
217}
218
Ted Kremenek40fc5c72008-07-18 15:54:51 +0000219
220//===----------------------------------------------------------------------===//
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000221// Transfer function dispatch for Non-Locs.
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000222//===----------------------------------------------------------------------===//
Ted Kremeneka6e4d212008-02-01 06:36:40 +0000223
Ted Kremenek6c07bdb2009-06-26 00:05:51 +0000224SVal nonloc::ConcreteInt::evalBinOp(ValueManager &ValMgr,
225 BinaryOperator::Opcode Op,
Mike Stump1eb44332009-09-09 15:08:12 +0000226 const nonloc::ConcreteInt& R) const {
Ted Kremenek75b0a1c2008-07-18 15:59:33 +0000227 const llvm::APSInt* X =
Ted Kremenek9c149532010-12-01 21:57:22 +0000228 ValMgr.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
Mike Stump1eb44332009-09-09 15:08:12 +0000229
Ted Kremenek8cc13ea2008-02-28 20:32:03 +0000230 if (X)
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000231 return nonloc::ConcreteInt(*X);
Ted Kremenek8cc13ea2008-02-28 20:32:03 +0000232 else
233 return UndefinedVal();
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000234}
235
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000236nonloc::ConcreteInt
Ted Kremenek6c07bdb2009-06-26 00:05:51 +0000237nonloc::ConcreteInt::evalComplement(ValueManager &ValMgr) const {
238 return ValMgr.makeIntVal(~getValue());
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000239}
240
Ted Kremenek6c07bdb2009-06-26 00:05:51 +0000241nonloc::ConcreteInt nonloc::ConcreteInt::evalMinus(ValueManager &ValMgr) const {
242 return ValMgr.makeIntVal(-getValue());
Ted Kremenekc5d3b4c2008-02-04 16:58:30 +0000243}
244
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000245//===----------------------------------------------------------------------===//
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000246// Transfer function dispatch for Locs.
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000247//===----------------------------------------------------------------------===//
248
Ted Kremenek9c149532010-12-01 21:57:22 +0000249SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
Ted Kremenekccaad9d2008-10-30 17:53:23 +0000250 BinaryOperator::Opcode Op,
251 const loc::ConcreteInt& R) const {
Mike Stump1eb44332009-09-09 15:08:12 +0000252
John McCall2de56d12010-08-25 11:45:40 +0000253 assert (Op == BO_Add || Op == BO_Sub ||
254 (Op >= BO_LT && Op <= BO_NE));
Mike Stump1eb44332009-09-09 15:08:12 +0000255
Ted Kremenek9c149532010-12-01 21:57:22 +0000256 const llvm::APSInt* X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
Mike Stump1eb44332009-09-09 15:08:12 +0000257
Ted Kremenek8cc13ea2008-02-28 20:32:03 +0000258 if (X)
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000259 return loc::ConcreteInt(*X);
Ted Kremenek8cc13ea2008-02-28 20:32:03 +0000260 else
261 return UndefinedVal();
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000262}
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000263
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000264//===----------------------------------------------------------------------===//
265// Pretty-Printing.
266//===----------------------------------------------------------------------===//
267
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000268void SVal::dump() const { dumpToStream(llvm::errs()); }
Ted Kremenek2a502572008-02-12 21:37:56 +0000269
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000270void SVal::dumpToStream(llvm::raw_ostream& os) const {
Mike Stump1eb44332009-09-09 15:08:12 +0000271 switch (getBaseKind()) {
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000272 case UnknownKind:
Ted Kremenek02282ac2010-09-15 03:13:30 +0000273 os << "Unknown";
Mike Stump1eb44332009-09-09 15:08:12 +0000274 break;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000275 case NonLocKind:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000276 cast<NonLoc>(this)->dumpToStream(os);
Mike Stump1eb44332009-09-09 15:08:12 +0000277 break;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000278 case LocKind:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000279 cast<Loc>(this)->dumpToStream(os);
Mike Stump1eb44332009-09-09 15:08:12 +0000280 break;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000281 case UndefinedKind:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000282 os << "Undefined";
Mike Stump1eb44332009-09-09 15:08:12 +0000283 break;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000284 default:
285 assert (false && "Invalid SVal.");
286 }
287}
288
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000289void NonLoc::dumpToStream(llvm::raw_ostream& os) const {
Mike Stump1eb44332009-09-09 15:08:12 +0000290 switch (getSubKind()) {
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000291 case nonloc::ConcreteIntKind:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000292 os << cast<nonloc::ConcreteInt>(this)->getValue().getZExtValue();
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000293 if (cast<nonloc::ConcreteInt>(this)->getValue().isUnsigned())
Mike Stump1eb44332009-09-09 15:08:12 +0000294 os << 'U';
295 break;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000296 case nonloc::SymbolValKind:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000297 os << '$' << cast<nonloc::SymbolVal>(this)->getSymbol();
Mike Stump1eb44332009-09-09 15:08:12 +0000298 break;
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000299 case nonloc::SymExprValKind: {
300 const nonloc::SymExprVal& C = *cast<nonloc::SymExprVal>(this);
301 const SymExpr *SE = C.getSymbolicExpression();
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000302 os << SE;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000303 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000304 }
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000305 case nonloc::LocAsIntegerKind: {
306 const nonloc::LocAsInteger& C = *cast<nonloc::LocAsInteger>(this);
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000307 os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000308 break;
309 }
Ted Kremeneka6fac4e2008-10-30 18:01:28 +0000310 case nonloc::CompoundValKind: {
311 const nonloc::CompoundVal& C = *cast<nonloc::CompoundVal>(this);
Ted Kremenek7b679522009-07-14 20:21:36 +0000312 os << "compoundVal{";
Ted Kremenekb8b41612008-10-30 18:35:10 +0000313 bool first = true;
314 for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +0000315 if (first) {
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000316 os << ' '; first = false;
317 }
318 else
319 os << ", ";
320
321 (*I).dumpToStream(os);
Ted Kremenekb8b41612008-10-30 18:35:10 +0000322 }
Ted Kremenek7b679522009-07-14 20:21:36 +0000323 os << "}";
Ted Kremeneka6fac4e2008-10-30 18:01:28 +0000324 break;
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000325 }
326 case nonloc::LazyCompoundValKind: {
327 const nonloc::LazyCompoundVal &C = *cast<nonloc::LazyCompoundVal>(this);
Dan Gohmancb421fa2010-04-19 16:39:44 +0000328 os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
329 << ',' << C.getRegion()
Ted Kremeneka5e81f12009-08-06 01:20:57 +0000330 << '}';
331 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000332 }
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000333 default:
334 assert (false && "Pretty-printed not implemented for this NonLoc.");
335 break;
336 }
337}
338
Mike Stump1eb44332009-09-09 15:08:12 +0000339void Loc::dumpToStream(llvm::raw_ostream& os) const {
340 switch (getSubKind()) {
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000341 case loc::ConcreteIntKind:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000342 os << cast<loc::ConcreteInt>(this)->getValue().getZExtValue() << " (Loc)";
Mike Stump1eb44332009-09-09 15:08:12 +0000343 break;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000344 case loc::GotoLabelKind:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000345 os << "&&" << cast<loc::GotoLabel>(this)->getLabel()->getID()->getName();
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000346 break;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000347 case loc::MemRegionKind:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000348 os << '&' << cast<loc::MemRegionVal>(this)->getRegion()->getString();
Mike Stump1eb44332009-09-09 15:08:12 +0000349 break;
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000350 default:
Ted Kremenek6f9b3a42009-07-13 23:53:06 +0000351 assert(false && "Pretty-printing not implemented for this Loc.");
Zhongxing Xu9012bff2008-10-24 06:00:12 +0000352 break;
353 }
354}