Coverage Report

Created: 2021-01-19 06:58

/Users/buildslave/jenkins/workspace/coverage/llvm-project/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
505k
      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
31
505k
    assert(from <= to);
32
505k
  }
33
34
  Range(const llvm::APSInt &point)
35
0
      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&point, &point) {}
36
37
343k
  bool Includes(const llvm::APSInt &v) const {
38
343k
    return *first <= v && 
v <= *second337k
;
39
343k
  }
40
1.42M
  const llvm::APSInt &From() const { return *first; }
41
1.20M
  const llvm::APSInt &To() const { return *second; }
42
200k
  const llvm::APSInt *getConcreteValue() const {
43
143k
    return &From() == &To() ? 
&From()57.9k
: nullptr;
44
200k
  }
45
46
380k
  void Profile(llvm::FoldingSetNodeID &ID) const {
47
380k
    ID.AddPointer(&From());
48
380k
    ID.AddPointer(&To());
49
380k
  }
50
};
51
52
class RangeTrait : public llvm::ImutContainerInfo<Range> {
53
public:
54
  // When comparing if one Range is less than another, we should compare
55
  // the actual APSInt values instead of their pointers.  This keeps the order
56
  // consistent (instead of comparing by pointer values) and can potentially
57
  // be used to speed up some of the operations in RangeSet.
58
14.9k
  static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
59
14.9k
    return *lhs.first < *rhs.first ||
60
13.5k
           (!(*rhs.first < *lhs.first) && 
*lhs.second < *rhs.second0
);
61
14.9k
  }
62
};
63
64
/// RangeSet contains a set of ranges. If the set is empty, then
65
///  there the value of a symbol is overly constrained and there are no
66
///  possible values for that symbol.
67
class RangeSet {
68
  typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
69
  PrimRangeSet ranges; // no need to make const, since it is an
70
                       // ImmutableSet - this allows default operator=
71
                       // to work.
72
public:
73
  typedef PrimRangeSet::Factory Factory;
74
  typedef PrimRangeSet::iterator iterator;
75
76
232k
  RangeSet(PrimRangeSet RS) : ranges(RS) {}
77
78
  /// Create a new set with all ranges of this set and RS.
79
  /// Possible intersections are not checked here.
80
1.96k
  RangeSet addRange(Factory &F, const RangeSet &RS) {
81
1.96k
    PrimRangeSet Ranges(RS.ranges);
82
1.96k
    for (const auto &range : ranges)
83
1.33k
      Ranges = F.add(Ranges, range);
84
1.96k
    return RangeSet(Ranges);
85
1.96k
  }
86
87
606k
  iterator begin() const { return ranges.begin(); }
88
305k
  iterator end() const { return ranges.end(); }
89
90
1.18M
  bool isEmpty() const { return ranges.isEmpty(); }
91
92
  /// Construct a new RangeSet representing '{ [from, to] }'.
93
  RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
94
188k
      : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
95
96
  /// Construct a new RangeSet representing the given point as a range.
97
39.2k
  RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {}
Unexecuted instantiation: clang::ento::RangeSet::RangeSet(llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, llvm::APSInt const&)
clang::ento::RangeSet::RangeSet(llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, llvm::APSInt const&)
Line
Count
Source
97
39.2k
  RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {}
98
99
  /// Profile - Generates a hash profile of this RangeSet for use
100
  ///  by FoldingSet.
101
607k
  void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
102
103
  /// getConcreteValue - If a symbol is contrained to equal a specific integer
104
  ///  constant then this method returns that value.  Otherwise, it returns
105
  ///  NULL.
106
216k
  const llvm::APSInt *getConcreteValue() const {
107
200k
    return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : 
nullptr15.3k
;
108
216k
  }
109
110
  /// Get a minimal value covered by the ranges in the set
111
  const llvm::APSInt &getMinValue() const;
112
  /// Get a maximal value covered by the ranges in the set
113
  const llvm::APSInt &getMaxValue() const;
114
115
private:
116
  void IntersectInRange(BasicValueFactory &BV, Factory &F,
117
                        const llvm::APSInt &Lower, const llvm::APSInt &Upper,
118
                        PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
119
                        PrimRangeSet::iterator &e) const;
120
121
  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
122
123
public:
124
  RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
125
                     llvm::APSInt Upper) const;
126
  RangeSet Intersect(BasicValueFactory &BV, Factory &F,
127
                     const RangeSet &Other) const;
128
  RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
129
  RangeSet Delete(BasicValueFactory &BV, Factory &F,
130
                  const llvm::APSInt &Point) const;
131
132
  void print(raw_ostream &os) const;
133
134
654k
  bool operator==(const RangeSet &other) const {
135
654k
    return ranges == other.ranges;
136
654k
  }
137
};
138
139
using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>;
140
ConstraintMap getConstraintMap(ProgramStateRef State);
141
142
class RangedConstraintManager : public SimpleConstraintManager {
143
public:
144
  RangedConstraintManager(ExprEngine *EE, SValBuilder &SB)
145
13.7k
      : SimpleConstraintManager(EE, SB) {}
146
147
  ~RangedConstraintManager() override;
148
149
  //===------------------------------------------------------------------===//
150
  // Implementation for interface from SimpleConstraintManager.
151
  //===------------------------------------------------------------------===//
152
153
  ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym,
154
                            bool Assumption) override;
155
156
  ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym,
157
                                          const llvm::APSInt &From,
158
                                          const llvm::APSInt &To,
159
                                          bool InRange) override;
160
161
  ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym,
162
                                       bool Assumption) override;
163
164
protected:
165
  /// Assume a constraint between a symbolic expression and a concrete integer.
166
  virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym,
167
                                       BinaryOperator::Opcode op,
168
                                       const llvm::APSInt &Int);
169
170
  //===------------------------------------------------------------------===//
171
  // Interface that subclasses must implement.
172
  //===------------------------------------------------------------------===//
173
174
  // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison
175
  // operation for the method being invoked.
176
177
  virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
178
                                      const llvm::APSInt &V,
179
                                      const llvm::APSInt &Adjustment) = 0;
180
181
  virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
182
                                      const llvm::APSInt &V,
183
                                      const llvm::APSInt &Adjustment) = 0;
184
185
  virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
186
                                      const llvm::APSInt &V,
187
                                      const llvm::APSInt &Adjustment) = 0;
188
189
  virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
190
                                      const llvm::APSInt &V,
191
                                      const llvm::APSInt &Adjustment) = 0;
192
193
  virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
194
                                      const llvm::APSInt &V,
195
                                      const llvm::APSInt &Adjustment) = 0;
196
197
  virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
198
                                      const llvm::APSInt &V,
199
                                      const llvm::APSInt &Adjustment) = 0;
200
201
  virtual ProgramStateRef assumeSymWithinInclusiveRange(
202
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
203
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
204
205
  virtual ProgramStateRef assumeSymOutsideInclusiveRange(
206
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
207
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
208
209
  //===------------------------------------------------------------------===//
210
  // Internal implementation.
211
  //===------------------------------------------------------------------===//
212
private:
213
  static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment);
214
};
215
216
} // namespace ento
217
} // namespace clang
218
219
REGISTER_FACTORY_WITH_PROGRAMSTATE(ConstraintMap)
220
221
#endif