Coverage Report

Created: 2019-02-20 07:29

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
Line
Count
Source (jump to first uncovered line)
1
//===- ConstraintManager.h - Constraints on symbolic values. ----*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
//  This file defined the interface to manage constraints on symbolic values.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CONSTRAINTMANAGER_H
14
#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CONSTRAINTMANAGER_H
15
16
#include "clang/Basic/LLVM.h"
17
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
20
#include "llvm/ADT/Optional.h"
21
#include "llvm/Support/SaveAndRestore.h"
22
#include <memory>
23
#include <utility>
24
25
namespace llvm {
26
27
class APSInt;
28
29
} // namespace llvm
30
31
namespace clang {
32
namespace ento {
33
34
class ProgramStateManager;
35
class SubEngine;
36
class SymbolReaper;
37
38
0
class ConditionTruthVal {
39
  Optional<bool> Val;
40
41
public:
42
  /// Construct a ConditionTruthVal indicating the constraint is constrained
43
  /// to either true or false, depending on the boolean value provided.
44
42.5k
  ConditionTruthVal(bool constraint) : Val(constraint) {}
45
46
  /// Construct a ConstraintVal indicating the constraint is underconstrained.
47
26.3k
  ConditionTruthVal() = default;
48
49
  /// \return Stored value, assuming that the value is known.
50
  /// Crashes otherwise.
51
8.88k
  bool getValue() const {
52
8.88k
    return *Val;
53
8.88k
  }
54
55
  /// Return true if the constraint is perfectly constrained to 'true'.
56
54.3k
  bool isConstrainedTrue() const {
57
54.3k
    return Val.hasValue() && 
Val.getValue()28.6k
;
58
54.3k
  }
59
60
  /// Return true if the constraint is perfectly constrained to 'false'.
61
1.46k
  bool isConstrainedFalse() const {
62
1.46k
    return Val.hasValue() && 
!Val.getValue()653
;
63
1.46k
  }
64
65
  /// Return true if the constrained is perfectly constrained.
66
  bool isConstrained() const {
67
    return Val.hasValue();
68
  }
69
70
  /// Return true if the constrained is underconstrained and we do not know
71
  /// if the constraint is true of value.
72
17.4k
  bool isUnderconstrained() const {
73
17.4k
    return !Val.hasValue();
74
17.4k
  }
75
};
76
77
class ConstraintManager {
78
public:
79
10.5k
  ConstraintManager() = default;
80
  virtual ~ConstraintManager();
81
82
  virtual ProgramStateRef assume(ProgramStateRef state,
83
                                 DefinedSVal Cond,
84
                                 bool Assumption) = 0;
85
86
  using ProgramStatePair = std::pair<ProgramStateRef, ProgramStateRef>;
87
88
  /// Returns a pair of states (StTrue, StFalse) where the given condition is
89
  /// assumed to be true or false, respectively.
90
286k
  ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond) {
91
286k
    ProgramStateRef StTrue = assume(State, Cond, true);
92
286k
93
286k
    // If StTrue is infeasible, asserting the falseness of Cond is unnecessary
94
286k
    // because the existing constraints already establish this.
95
286k
    if (!StTrue) {
96
14.9k
#ifndef __OPTIMIZE__
97
14.9k
      // This check is expensive and should be disabled even in Release+Asserts
98
14.9k
      // builds.
99
14.9k
      // FIXME: __OPTIMIZE__ is a GNU extension that Clang implements but MSVC
100
14.9k
      // does not. Is there a good equivalent there?
101
14.9k
      assert(assume(State, Cond, false) && "System is over constrained.");
102
14.9k
#endif
103
14.9k
      return ProgramStatePair((ProgramStateRef)nullptr, State);
104
14.9k
    }
105
271k
106
271k
    ProgramStateRef StFalse = assume(State, Cond, false);
107
271k
    if (!StFalse) {
108
232k
      // We are careful to return the original state, /not/ StTrue,
109
232k
      // because we want to avoid having callers generate a new node
110
232k
      // in the ExplodedGraph.
111
232k
      return ProgramStatePair(State, (ProgramStateRef)nullptr);
112
232k
    }
113
39.0k
114
39.0k
    return ProgramStatePair(StTrue, StFalse);
115
39.0k
  }
116
117
  virtual ProgramStateRef assumeInclusiveRange(ProgramStateRef State,
118
                                               NonLoc Value,
119
                                               const llvm::APSInt &From,
120
                                               const llvm::APSInt &To,
121
                                               bool InBound) = 0;
122
123
  virtual ProgramStatePair assumeInclusiveRangeDual(ProgramStateRef State,
124
                                                    NonLoc Value,
125
                                                    const llvm::APSInt &From,
126
485
                                                    const llvm::APSInt &To) {
127
485
    ProgramStateRef StInRange =
128
485
        assumeInclusiveRange(State, Value, From, To, true);
129
485
130
485
    // If StTrue is infeasible, asserting the falseness of Cond is unnecessary
131
485
    // because the existing constraints already establish this.
132
485
    if (!StInRange)
133
117
      return ProgramStatePair((ProgramStateRef)nullptr, State);
134
368
135
368
    ProgramStateRef StOutOfRange =
136
368
        assumeInclusiveRange(State, Value, From, To, false);
137
368
    if (!StOutOfRange) {
138
78
      // We are careful to return the original state, /not/ StTrue,
139
78
      // because we want to avoid having callers generate a new node
140
78
      // in the ExplodedGraph.
141
78
      return ProgramStatePair(State, (ProgramStateRef)nullptr);
142
78
    }
143
290
144
290
    return ProgramStatePair(StInRange, StOutOfRange);
145
290
  }
146
147
  /// If a symbol is perfectly constrained to a constant, attempt
148
  /// to return the concrete value.
149
  ///
150
  /// Note that a ConstraintManager is not obligated to return a concretized
151
  /// value for a symbol, even if it is perfectly constrained.
152
  virtual const llvm::APSInt* getSymVal(ProgramStateRef state,
153
0
                                        SymbolRef sym) const {
154
0
    return nullptr;
155
0
  }
156
157
  /// Scan all symbols referenced by the constraints. If the symbol is not
158
  /// alive, remove it.
159
  virtual ProgramStateRef removeDeadBindings(ProgramStateRef state,
160
                                                 SymbolReaper& SymReaper) = 0;
161
162
  virtual void print(ProgramStateRef state,
163
                     raw_ostream &Out,
164
                     const char* nl,
165
                     const char *sep) = 0;
166
167
53.3k
  virtual void EndPath(ProgramStateRef state) {}
168
169
  /// Convenience method to query the state to see if a symbol is null or
170
  /// not null, or if neither assumption can be made.
171
45.3k
  ConditionTruthVal isNull(ProgramStateRef State, SymbolRef Sym) {
172
45.3k
    SaveAndRestore<bool> DisableNotify(NotifyAssumeClients, false);
173
45.3k
174
45.3k
    return checkNull(State, Sym);
175
45.3k
  }
176
177
protected:
178
  /// A flag to indicate that clients should be notified of assumptions.
179
  /// By default this is the case, but sometimes this needs to be restricted
180
  /// to avoid infinite recursions within the ConstraintManager.
181
  ///
182
  /// Note that this flag allows the ConstraintManager to be re-entrant,
183
  /// but not thread-safe.
184
  bool NotifyAssumeClients = true;
185
186
  /// canReasonAbout - Not all ConstraintManagers can accurately reason about
187
  ///  all SVal values.  This method returns true if the ConstraintManager can
188
  ///  reasonably handle a given SVal value.  This is typically queried by
189
  ///  ExprEngine to determine if the value should be replaced with a
190
  ///  conjured symbolic value in order to recover some precision.
191
  virtual bool canReasonAbout(SVal X) const = 0;
192
193
  /// Returns whether or not a symbol is known to be null ("true"), known to be
194
  /// non-null ("false"), or may be either ("underconstrained").
195
  virtual ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym);
196
};
197
198
std::unique_ptr<ConstraintManager>
199
CreateRangeConstraintManager(ProgramStateManager &statemgr,
200
                             SubEngine *subengine);
201
202
std::unique_ptr<ConstraintManager>
203
CreateZ3ConstraintManager(ProgramStateManager &statemgr, SubEngine *subengine);
204
205
} // namespace ento
206
} // namespace clang
207
208
#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CONSTRAINTMANAGER_H