Coverage Report

Created: 2018-11-16 02:38

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
Line
Count
Source (jump to first uncovered line)
1
//== RangedConstraintManager.h ----------------------------------*- 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
//  Ranged constraint manager, built on SimpleConstraintManager.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
15
#define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
16
17
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h"
20
21
namespace clang {
22
23
namespace ento {
24
25
/// A Range represents the closed range [from, to].  The caller must
26
/// guarantee that from <= to.  Note that Range is immutable, so as not
27
/// to subvert RangeSet's immutability.
28
class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
29
public:
30
  Range(const llvm::APSInt &from, const llvm::APSInt &to)
31
271k
      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
32
271k
    assert(from <= to);
33
271k
  }
34
378k
  bool Includes(const llvm::APSInt &v) const {
35
378k
    return *first <= v && 
v <= *second375k
;
36
378k
  }
37
815k
  const llvm::APSInt &From() const { return *first; }
38
614k
  const llvm::APSInt &To() const { return *second; }
39
48.1k
  const llvm::APSInt *getConcreteValue() const {
40
48.1k
    return &From() == &To() ? 
&From()12.0k
:
nullptr36.0k
;
41
48.1k
  }
42
43
302k
  void Profile(llvm::FoldingSetNodeID &ID) const {
44
302k
    ID.AddPointer(&From());
45
302k
    ID.AddPointer(&To());
46
302k
  }
47
};
48
49
class RangeTrait : public llvm::ImutContainerInfo<Range> {
50
public:
51
  // When comparing if one Range is less than another, we should compare
52
  // the actual APSInt values instead of their pointers.  This keeps the order
53
  // consistent (instead of comparing by pointer values) and can potentially
54
  // be used to speed up some of the operations in RangeSet.
55
29.2k
  static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
56
29.2k
    return *lhs.first < *rhs.first ||
57
29.2k
           
(28.6k
!(*rhs.first < *lhs.first)28.6k
&&
*lhs.second < *rhs.second0
);
58
29.2k
  }
59
};
60
61
/// RangeSet contains a set of ranges. If the set is empty, then
62
///  there the value of a symbol is overly constrained and there are no
63
///  possible values for that symbol.
64
class RangeSet {
65
  typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
66
  PrimRangeSet ranges; // no need to make const, since it is an
67
                       // ImmutableSet - this allows default operator=
68
                       // to work.
69
public:
70
  typedef PrimRangeSet::Factory Factory;
71
  typedef PrimRangeSet::iterator iterator;
72
73
213k
  RangeSet(PrimRangeSet RS) : ranges(RS) {}
74
75
  /// Create a new set with all ranges of this set and RS.
76
  /// Possible intersections are not checked here.
77
1.26k
  RangeSet addRange(Factory &F, const RangeSet &RS) {
78
1.26k
    PrimRangeSet Ranges(RS.ranges);
79
1.26k
    for (const auto &range : ranges)
80
952
      Ranges = F.add(Ranges, range);
81
1.26k
    return RangeSet(Ranges);
82
1.26k
  }
83
84
211k
  iterator begin() const { return ranges.begin(); }
85
211k
  iterator end() const { return ranges.end(); }
86
87
171k
  bool isEmpty() const { return ranges.isEmpty(); }
88
89
  /// Construct a new RangeSet representing '{ [from, to] }'.
90
  RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
91
82.8k
      : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
92
93
  /// Profile - Generates a hash profile of this RangeSet for use
94
  ///  by FoldingSet.
95
668k
  void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
96
97
  /// getConcreteValue - If a symbol is contrained to equal a specific integer
98
  ///  constant then this method returns that value.  Otherwise, it returns
99
  ///  NULL.
100
51.6k
  const llvm::APSInt *getConcreteValue() const {
101
51.6k
    return ranges.isSingleton() ? 
ranges.begin()->getConcreteValue()48.1k
:
nullptr3.48k
;
102
51.6k
  }
103
104
private:
105
  void IntersectInRange(BasicValueFactory &BV, Factory &F,
106
                        const llvm::APSInt &Lower, const llvm::APSInt &Upper,
107
                        PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
108
                        PrimRangeSet::iterator &e) const;
109
110
  const llvm::APSInt &getMinValue() const;
111
112
  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
113
114
public:
115
  RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
116
                     llvm::APSInt Upper) const;
117
118
  RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
119
120
  void print(raw_ostream &os) const;
121
122
884k
  bool operator==(const RangeSet &other) const {
123
884k
    return ranges == other.ranges;
124
884k
  }
125
};
126
127
128
class ConstraintRange {};
129
using ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>;
130
131
template <>
132
struct ProgramStateTrait<ConstraintRange>
133
  : public ProgramStatePartialTrait<ConstraintRangeTy> {
134
  static void *GDMIndex();
135
};
136
137
138
class RangedConstraintManager : public SimpleConstraintManager {
139
public:
140
  RangedConstraintManager(SubEngine *SE, SValBuilder &SB)
141
9.80k
      : SimpleConstraintManager(SE, SB) {}
142
143
  ~RangedConstraintManager() override;
144
145
  //===------------------------------------------------------------------===//
146
  // Implementation for interface from SimpleConstraintManager.
147
  //===------------------------------------------------------------------===//
148
149
  ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym,
150
                            bool Assumption) override;
151
152
  ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym,
153
                                          const llvm::APSInt &From,
154
                                          const llvm::APSInt &To,
155
                                          bool InRange) override;
156
157
  ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym,
158
                                       bool Assumption) override;
159
160
protected:
161
  /// Assume a constraint between a symbolic expression and a concrete integer.
162
  virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym,
163
                               BinaryOperator::Opcode op,
164
                               const llvm::APSInt &Int);
165
166
  //===------------------------------------------------------------------===//
167
  // Interface that subclasses must implement.
168
  //===------------------------------------------------------------------===//
169
170
  // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison
171
  // operation for the method being invoked.
172
173
  virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
174
                                      const llvm::APSInt &V,
175
                                      const llvm::APSInt &Adjustment) = 0;
176
177
  virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
178
                                      const llvm::APSInt &V,
179
                                      const llvm::APSInt &Adjustment) = 0;
180
181
  virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
182
                                      const llvm::APSInt &V,
183
                                      const llvm::APSInt &Adjustment) = 0;
184
185
  virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
186
                                      const llvm::APSInt &V,
187
                                      const llvm::APSInt &Adjustment) = 0;
188
189
  virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
190
                                      const llvm::APSInt &V,
191
                                      const llvm::APSInt &Adjustment) = 0;
192
193
  virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
194
                                      const llvm::APSInt &V,
195
                                      const llvm::APSInt &Adjustment) = 0;
196
197
  virtual ProgramStateRef assumeSymWithinInclusiveRange(
198
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
199
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
200
201
  virtual ProgramStateRef assumeSymOutsideInclusiveRange(
202
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
203
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
204
205
  //===------------------------------------------------------------------===//
206
  // Internal implementation.
207
  //===------------------------------------------------------------------===//
208
private:
209
  static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment);
210
};
211
212
} // end GR namespace
213
214
} // end clang namespace
215
216
#endif