SVals.h revision da9ae6088b9543134a6561a412b79530e290408d 
1//== SVals.h - Abstract Values for Static Analysis ---------*- C++ -*--==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines SVal, Loc, and NonLoc, classes that represent
11//  abstract r-values for use with path-sensitive value tracking.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_ANALYSIS_RVALUE_H
16#define LLVM_CLANG_ANALYSIS_RVALUE_H
17
18#include "clang/Analysis/PathSensitive/SymbolManager.h"
19#include "llvm/Support/Casting.h"
20#include "llvm/ADT/ImmutableList.h"
21
22//==------------------------------------------------------------------------==//
23//  Base SVal types.
24//==------------------------------------------------------------------------==//
25
26namespace clang {
27
28class CompoundValData;
29class BasicValueFactory;
30class MemRegion;
31class MemRegionManager;
32class GRStateManager;
33
34class SVal {
35public:
36  enum BaseKind { UndefinedKind, UnknownKind, LocKind, NonLocKind };
37  enum { BaseBits = 2, BaseMask = 0x3 };
38
39protected:
40  void* Data;
41  unsigned Kind;
42
43protected:
44  SVal(const void* d, bool isLoc, unsigned ValKind)
45  : Data(const_cast<void*>(d)),
46    Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
47
48  explicit SVal(BaseKind k, void* D = NULL)
49    : Data(D), Kind(k) {}
50
51public:
52  SVal() : Data(0), Kind(0) {}
53  ~SVal() {};
54
55  /// BufferTy - A temporary buffer to hold a set of SVals.
56  typedef llvm::SmallVector<SVal,5> BufferTy;
57
58  inline unsigned getRawKind() const { return Kind; }
59  inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
60  inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
61
62  inline void Profile(llvm::FoldingSetNodeID& ID) const {
63    ID.AddInteger((unsigned) getRawKind());
64    ID.AddPointer(reinterpret_cast<void*>(Data));
65  }
66
67  inline bool operator==(const SVal& R) const {
68    return getRawKind() == R.getRawKind() && Data == R.Data;
69  }
70
71  inline bool operator!=(const SVal& R) const {
72    return !(*this == R);
73  }
74
75  /// GetRValueSymbolVal - make a unique symbol for value of R.
76  static SVal GetRValueSymbolVal(SymbolManager& SymMgr, MemRegionManager& MRMgr,
77                                 const MemRegion* R);
78
79  static SVal GetConjuredSymbolVal(SymbolManager& SymMgr, const Expr *E,
80                                   unsigned Count);
81
82  inline bool isUnknown() const {
83    return getRawKind() == UnknownKind;
84  }
85
86  inline bool isUndef() const {
87    return getRawKind() == UndefinedKind;
88  }
89
90  inline bool isUnknownOrUndef() const {
91    return getRawKind() <= UnknownKind;
92  }
93
94  inline bool isValid() const {
95    return getRawKind() > UnknownKind;
96  }
97
98  static SVal MakeZero(BasicValueFactory &BasicVals, QualType T);
99
100  bool isZeroConstant() const;
101
102  /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and
103  ///  wraps a symbol, return that SymbolRef.  Otherwise return a SymbolData*
104  SymbolRef getAsLocSymbol() const;
105
106  /// getAsSymbol - If this Sval wraps a symbol return that SymbolRef.
107  ///  Otherwise return a SymbolRef where 'isValid()' returns false.
108  SymbolRef getAsSymbol() const;
109
110  /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
111  ///  return that expression.  Otherwise return NULL.
112  const SymExpr *getAsSymbolicExpression() const;
113
114  void print(std::ostream& OS) const;
115  void print(llvm::raw_ostream& OS) const;
116  void printStdErr() const;
117
118  // Iterators.
119  class symbol_iterator {
120    llvm::SmallVector<const SymExpr*, 5> itr;
121    void expand();
122  public:
123    symbol_iterator() {}
124    symbol_iterator(const SymExpr* SE);
125
126    symbol_iterator& operator++();
127    SymbolRef operator*();
128
129    bool operator==(const symbol_iterator& X) const;
130    bool operator!=(const symbol_iterator& X) const;
131  };
132
133  symbol_iterator symbol_begin() const {
134    const SymExpr *SE = getAsSymbolicExpression();
135    if (SE)
136      return symbol_iterator(SE);
137    else
138      return symbol_iterator();
139  }
140
141  symbol_iterator symbol_end() const { return symbol_iterator(); }
142
143  // Implement isa<T> support.
144  static inline bool classof(const SVal*) { return true; }
145};
146
147class UnknownVal : public SVal {
148public:
149  UnknownVal() : SVal(UnknownKind) {}
150
151  static inline bool classof(const SVal* V) {
152    return V->getBaseKind() == UnknownKind;
153  }
154};
155
156class UndefinedVal : public SVal {
157public:
158  UndefinedVal() : SVal(UndefinedKind) {}
159  UndefinedVal(void* D) : SVal(UndefinedKind, D) {}
160
161  static inline bool classof(const SVal* V) {
162    return V->getBaseKind() == UndefinedKind;
163  }
164
165  void* getData() const { return Data; }
166};
167
168class NonLoc : public SVal {
169protected:
170  NonLoc(unsigned SubKind, const void* d) : SVal(d, false, SubKind) {}
171
172public:
173  void print(llvm::raw_ostream& Out) const;
174
175  // Utility methods to create NonLocs.
176  static NonLoc MakeVal(SymbolRef sym);
177
178  static NonLoc MakeVal(SymbolManager& SymMgr, const SymExpr *lhs,
179                        BinaryOperator::Opcode op, const llvm::APSInt& rhs,
180                        QualType T);
181
182  static NonLoc MakeVal(SymbolManager& SymMgr, const SymExpr *lhs,
183                        BinaryOperator::Opcode op, const SymExpr *rhs,
184                        QualType T);
185
186  static NonLoc MakeIntVal(BasicValueFactory& BasicVals, uint64_t X,
187                           bool isUnsigned);
188
189  static NonLoc MakeVal(BasicValueFactory& BasicVals, uint64_t X,
190                        unsigned BitWidth, bool isUnsigned);
191
192  static NonLoc MakeVal(BasicValueFactory& BasicVals, uint64_t X, QualType T);
193
194  static NonLoc MakeVal(BasicValueFactory& BasicVals, IntegerLiteral* I);
195
196  static NonLoc MakeVal(BasicValueFactory& BasicVals, const llvm::APInt& I,
197                        bool isUnsigned);
198
199  static NonLoc MakeVal(BasicValueFactory& BasicVals, const llvm::APSInt& I);
200
201  static NonLoc MakeIntTruthVal(BasicValueFactory& BasicVals, bool b);
202
203  static NonLoc MakeCompoundVal(QualType T, llvm::ImmutableList<SVal> Vals,
204                                BasicValueFactory& BasicVals);
205
206  // Implement isa<T> support.
207  static inline bool classof(const SVal* V) {
208    return V->getBaseKind() == NonLocKind;
209  }
210};
211
212class Loc : public SVal {
213protected:
214  Loc(unsigned SubKind, const void* D)
215  : SVal(const_cast<void*>(D), true, SubKind) {}
216
217public:
218  void print(llvm::raw_ostream& Out) const;
219
220  Loc(const Loc& X) : SVal(X.Data, true, X.getSubKind()) {}
221  Loc& operator=(const Loc& X) { memcpy(this, &X, sizeof(Loc)); return *this; }
222
223  static Loc MakeVal(const MemRegion* R);
224
225  static Loc MakeVal(AddrLabelExpr* E);
226
227  static Loc MakeVal(SymbolRef sym);
228
229  static Loc MakeNull(BasicValueFactory &BasicVals);
230
231  // Implement isa<T> support.
232  static inline bool classof(const SVal* V) {
233    return V->getBaseKind() == LocKind;
234  }
235
236  static inline bool IsLocType(QualType T) {
237    return T->isPointerType() || T->isObjCQualifiedIdType()
238      || T->isBlockPointerType();
239  }
240};
241
242//==------------------------------------------------------------------------==//
243//  Subclasses of NonLoc.
244//==------------------------------------------------------------------------==//
245
246namespace nonloc {
247
248enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind,
249            LocAsIntegerKind, CompoundValKind };
250
251class SymbolVal : public NonLoc {
252public:
253  SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {}
254
255  SymbolRef getSymbol() const {
256    return (const SymbolData*) Data;
257  }
258
259  static inline bool classof(const SVal* V) {
260    return V->getBaseKind() == NonLocKind &&
261           V->getSubKind() == SymbolValKind;
262  }
263
264  static inline bool classof(const NonLoc* V) {
265    return V->getSubKind() == SymbolValKind;
266  }
267};
268
269class SymExprVal : public NonLoc {
270public:
271  SymExprVal(const SymExpr *SE)
272    : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {}
273
274  const SymExpr *getSymbolicExpression() const {
275    return reinterpret_cast<SymExpr*>(Data);
276  }
277
278  static inline bool classof(const SVal* V) {
279    return V->getBaseKind() == NonLocKind &&
280           V->getSubKind() == SymExprValKind;
281  }
282
283  static inline bool classof(const NonLoc* V) {
284    return V->getSubKind() == SymExprValKind;
285  }
286};
287
288class ConcreteInt : public NonLoc {
289public:
290  ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
291
292  const llvm::APSInt& getValue() const {
293    return *static_cast<llvm::APSInt*>(Data);
294  }
295
296  // Transfer functions for binary/unary operations on ConcreteInts.
297  SVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
298                 const ConcreteInt& R) const;
299
300  ConcreteInt EvalComplement(BasicValueFactory& BasicVals) const;
301
302  ConcreteInt EvalMinus(BasicValueFactory& BasicVals, UnaryOperator* U) const;
303
304  // Implement isa<T> support.
305  static inline bool classof(const SVal* V) {
306    return V->getBaseKind() == NonLocKind &&
307           V->getSubKind() == ConcreteIntKind;
308  }
309
310  static inline bool classof(const NonLoc* V) {
311    return V->getSubKind() == ConcreteIntKind;
312  }
313};
314
315class LocAsInteger : public NonLoc {
316  LocAsInteger(const std::pair<SVal, uintptr_t>& data) :
317    NonLoc(LocAsIntegerKind, &data) {
318      assert (isa<Loc>(data.first));
319    }
320
321public:
322
323  Loc getLoc() const {
324    return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first);
325  }
326
327  const Loc& getPersistentLoc() const {
328    const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first;
329    return cast<Loc>(V);
330  }
331
332  unsigned getNumBits() const {
333    return ((std::pair<SVal, unsigned>*) Data)->second;
334  }
335
336  // Implement isa<T> support.
337  static inline bool classof(const SVal* V) {
338    return V->getBaseKind() == NonLocKind &&
339           V->getSubKind() == LocAsIntegerKind;
340  }
341
342  static inline bool classof(const NonLoc* V) {
343    return V->getSubKind() == LocAsIntegerKind;
344  }
345
346  static LocAsInteger Make(BasicValueFactory& Vals, Loc V, unsigned Bits);
347};
348
349class CompoundVal : public NonLoc {
350  friend class NonLoc;
351
352  CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
353
354public:
355  const CompoundValData* getValue() const {
356    return static_cast<CompoundValData*>(Data);
357  }
358
359  typedef llvm::ImmutableList<SVal>::iterator iterator;
360  iterator begin() const;
361  iterator end() const;
362
363  static bool classof(const SVal* V) {
364    return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind;
365  }
366
367  static bool classof(const NonLoc* V) {
368    return V->getSubKind() == CompoundValKind;
369  }
370};
371
372} // end namespace clang::nonloc
373
374//==------------------------------------------------------------------------==//
375//  Subclasses of Loc.
376//==------------------------------------------------------------------------==//
377
378namespace loc {
379
380enum Kind { SymbolValKind, GotoLabelKind, MemRegionKind, FuncValKind,
381            ConcreteIntKind };
382
383class SymbolVal : public Loc {
384public:
385  SymbolVal(SymbolRef sym) : Loc(SymbolValKind, sym) {}
386
387  SymbolRef getSymbol() const { return (SymbolRef) Data; }
388
389  static inline bool classof(const SVal* V) {
390    return V->getBaseKind() == LocKind &&
391           V->getSubKind() == SymbolValKind;
392  }
393
394  static inline bool classof(const Loc* V) {
395    return V->getSubKind() == SymbolValKind;
396  }
397};
398
399class GotoLabel : public Loc {
400public:
401  GotoLabel(LabelStmt* Label) : Loc(GotoLabelKind, Label) {}
402
403  LabelStmt* getLabel() const {
404    return static_cast<LabelStmt*>(Data);
405  }
406
407  static inline bool classof(const SVal* V) {
408    return V->getBaseKind() == LocKind &&
409           V->getSubKind() == GotoLabelKind;
410  }
411
412  static inline bool classof(const Loc* V) {
413    return V->getSubKind() == GotoLabelKind;
414  }
415};
416
417
418class MemRegionVal : public Loc {
419public:
420  MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {}
421
422  const MemRegion* getRegion() const {
423    return static_cast<MemRegion*>(Data);
424  }
425
426  template <typename REGION>
427  const REGION* getRegionAs() const {
428    return llvm::dyn_cast<REGION>(getRegion());
429  }
430
431  inline bool operator==(const MemRegionVal& R) const {
432    return getRegion() == R.getRegion();
433  }
434
435  inline bool operator!=(const MemRegionVal& R) const {
436    return getRegion() != R.getRegion();
437  }
438
439  // Implement isa<T> support.
440  static inline bool classof(const SVal* V) {
441    return V->getBaseKind() == LocKind &&
442           V->getSubKind() == MemRegionKind;
443  }
444
445  static inline bool classof(const Loc* V) {
446    return V->getSubKind() == MemRegionKind;
447  }
448};
449
450class FuncVal : public Loc {
451public:
452  FuncVal(const FunctionDecl* fd) : Loc(FuncValKind, fd) {}
453
454  FunctionDecl* getDecl() const {
455    return static_cast<FunctionDecl*>(Data);
456  }
457
458  inline bool operator==(const FuncVal& R) const {
459    return getDecl() == R.getDecl();
460  }
461
462  inline bool operator!=(const FuncVal& R) const {
463    return getDecl() != R.getDecl();
464  }
465
466  // Implement isa<T> support.
467  static inline bool classof(const SVal* V) {
468    return V->getBaseKind() == LocKind &&
469           V->getSubKind() == FuncValKind;
470  }
471
472  static inline bool classof(const Loc* V) {
473    return V->getSubKind() == FuncValKind;
474  }
475};
476
477class ConcreteInt : public Loc {
478public:
479  ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
480
481  const llvm::APSInt& getValue() const {
482    return *static_cast<llvm::APSInt*>(Data);
483  }
484
485  // Transfer functions for binary/unary operations on ConcreteInts.
486  SVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
487                 const ConcreteInt& R) const;
488
489  // Implement isa<T> support.
490  static inline bool classof(const SVal* V) {
491    return V->getBaseKind() == LocKind &&
492           V->getSubKind() == ConcreteIntKind;
493  }
494
495  static inline bool classof(const Loc* V) {
496    return V->getSubKind() == ConcreteIntKind;
497  }
498};
499
500} // end clang::loc namespace
501} // end clang namespace
502
503#endif
504