• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //== ConstraintManager.h - Constraints on symbolic values.-------*- 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 defined the interface to manage constraints on symbolic values.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CONSTRAINTMANAGER_H
15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CONSTRAINTMANAGER_H
16 
17 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
19 #include "llvm/Support/SaveAndRestore.h"
20 
21 namespace llvm {
22 class APSInt;
23 }
24 
25 namespace clang {
26 namespace ento {
27 
28 class SubEngine;
29 
30 class ConditionTruthVal {
31   Optional<bool> Val;
32 public:
33   /// Construct a ConditionTruthVal indicating the constraint is constrained
34   /// to either true or false, depending on the boolean value provided.
ConditionTruthVal(bool constraint)35   ConditionTruthVal(bool constraint) : Val(constraint) {}
36 
37   /// Construct a ConstraintVal indicating the constraint is underconstrained.
ConditionTruthVal()38   ConditionTruthVal() {}
39 
40   /// Return true if the constraint is perfectly constrained to 'true'.
isConstrainedTrue()41   bool isConstrainedTrue() const {
42     return Val.hasValue() && Val.getValue();
43   }
44 
45   /// Return true if the constraint is perfectly constrained to 'false'.
isConstrainedFalse()46   bool isConstrainedFalse() const {
47     return Val.hasValue() && !Val.getValue();
48   }
49 
50   /// Return true if the constrained is perfectly constrained.
isConstrained()51   bool isConstrained() const {
52     return Val.hasValue();
53   }
54 
55   /// Return true if the constrained is underconstrained and we do not know
56   /// if the constraint is true of value.
isUnderconstrained()57   bool isUnderconstrained() const {
58     return !Val.hasValue();
59   }
60 };
61 
62 class ConstraintManager {
63 public:
ConstraintManager()64   ConstraintManager() : NotifyAssumeClients(true) {}
65 
66   virtual ~ConstraintManager();
67   virtual ProgramStateRef assume(ProgramStateRef state,
68                                  DefinedSVal Cond,
69                                  bool Assumption) = 0;
70 
71   typedef std::pair<ProgramStateRef, ProgramStateRef> ProgramStatePair;
72 
73   /// Returns a pair of states (StTrue, StFalse) where the given condition is
74   /// assumed to be true or false, respectively.
assumeDual(ProgramStateRef State,DefinedSVal Cond)75   ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond) {
76     ProgramStateRef StTrue = assume(State, Cond, true);
77 
78     // If StTrue is infeasible, asserting the falseness of Cond is unnecessary
79     // because the existing constraints already establish this.
80     if (!StTrue) {
81 #ifndef __OPTIMIZE__
82       // This check is expensive and should be disabled even in Release+Asserts
83       // builds.
84       // FIXME: __OPTIMIZE__ is a GNU extension that Clang implements but MSVC
85       // does not. Is there a good equivalent there?
86       assert(assume(State, Cond, false) && "System is over constrained.");
87 #endif
88       return ProgramStatePair((ProgramStateRef)nullptr, State);
89     }
90 
91     ProgramStateRef StFalse = assume(State, Cond, false);
92     if (!StFalse) {
93       // We are careful to return the original state, /not/ StTrue,
94       // because we want to avoid having callers generate a new node
95       // in the ExplodedGraph.
96       return ProgramStatePair(State, (ProgramStateRef)nullptr);
97     }
98 
99     return ProgramStatePair(StTrue, StFalse);
100   }
101 
102   virtual ProgramStateRef assumeWithinInclusiveRange(ProgramStateRef State,
103                                                      NonLoc Value,
104                                                      const llvm::APSInt &From,
105                                                      const llvm::APSInt &To,
106                                                      bool InBound) = 0;
107 
assumeWithinInclusiveRangeDual(ProgramStateRef State,NonLoc Value,const llvm::APSInt & From,const llvm::APSInt & To)108   virtual ProgramStatePair assumeWithinInclusiveRangeDual(
109       ProgramStateRef State, NonLoc Value, const llvm::APSInt &From,
110       const llvm::APSInt &To) {
111     ProgramStateRef StInRange = assumeWithinInclusiveRange(State, Value, From,
112                                                            To, true);
113 
114     // If StTrue is infeasible, asserting the falseness of Cond is unnecessary
115     // because the existing constraints already establish this.
116     if (!StInRange)
117       return ProgramStatePair((ProgramStateRef)nullptr, State);
118 
119     ProgramStateRef StOutOfRange = assumeWithinInclusiveRange(State, Value,
120                                                               From, To, false);
121     if (!StOutOfRange) {
122       // We are careful to return the original state, /not/ StTrue,
123       // because we want to avoid having callers generate a new node
124       // in the ExplodedGraph.
125       return ProgramStatePair(State, (ProgramStateRef)nullptr);
126     }
127 
128     return ProgramStatePair(StInRange, StOutOfRange);
129   }
130 
131   /// \brief If a symbol is perfectly constrained to a constant, attempt
132   /// to return the concrete value.
133   ///
134   /// Note that a ConstraintManager is not obligated to return a concretized
135   /// value for a symbol, even if it is perfectly constrained.
getSymVal(ProgramStateRef state,SymbolRef sym)136   virtual const llvm::APSInt* getSymVal(ProgramStateRef state,
137                                         SymbolRef sym) const {
138     return nullptr;
139   }
140 
141   virtual ProgramStateRef removeDeadBindings(ProgramStateRef state,
142                                                  SymbolReaper& SymReaper) = 0;
143 
144   virtual void print(ProgramStateRef state,
145                      raw_ostream &Out,
146                      const char* nl,
147                      const char *sep) = 0;
148 
EndPath(ProgramStateRef state)149   virtual void EndPath(ProgramStateRef state) {}
150 
151   /// Convenience method to query the state to see if a symbol is null or
152   /// not null, or if neither assumption can be made.
isNull(ProgramStateRef State,SymbolRef Sym)153   ConditionTruthVal isNull(ProgramStateRef State, SymbolRef Sym) {
154     SaveAndRestore<bool> DisableNotify(NotifyAssumeClients, false);
155 
156     return checkNull(State, Sym);
157   }
158 
159 protected:
160   /// A flag to indicate that clients should be notified of assumptions.
161   /// By default this is the case, but sometimes this needs to be restricted
162   /// to avoid infinite recursions within the ConstraintManager.
163   ///
164   /// Note that this flag allows the ConstraintManager to be re-entrant,
165   /// but not thread-safe.
166   bool NotifyAssumeClients;
167 
168   /// canReasonAbout - Not all ConstraintManagers can accurately reason about
169   ///  all SVal values.  This method returns true if the ConstraintManager can
170   ///  reasonably handle a given SVal value.  This is typically queried by
171   ///  ExprEngine to determine if the value should be replaced with a
172   ///  conjured symbolic value in order to recover some precision.
173   virtual bool canReasonAbout(SVal X) const = 0;
174 
175   /// Returns whether or not a symbol is known to be null ("true"), known to be
176   /// non-null ("false"), or may be either ("underconstrained").
177   virtual ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym);
178 };
179 
180 std::unique_ptr<ConstraintManager>
181 CreateRangeConstraintManager(ProgramStateManager &statemgr,
182                              SubEngine *subengine);
183 
184 } // end GR namespace
185 
186 } // end clang namespace
187 
188 #endif
189