Coverage Report

Created: 2019-02-20 07:29

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