Coverage Report

Created: 2021-08-24 07:12

/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
#include "llvm/ADT/APSInt.h"
20
#include "llvm/Support/Allocator.h"
21
22
namespace clang {
23
24
namespace ento {
25
26
/// A Range represents the closed range [from, to].  The caller must
27
/// guarantee that from <= to.  Note that Range is immutable, so as not
28
/// to subvert RangeSet's immutability.
29
class Range {
30
public:
31
909k
  Range(const llvm::APSInt &From, const llvm::APSInt &To) : Impl(&From, &To) {
32
909k
    assert(From <= To);
33
909k
  }
34
35
169k
  Range(const llvm::APSInt &Point) : Range(Point, Point) {}
Unexecuted instantiation: clang::ento::Range::Range(llvm::APSInt const&)
clang::ento::Range::Range(llvm::APSInt const&)
Line
Count
Source
35
169k
  Range(const llvm::APSInt &Point) : Range(Point, Point) {}
36
37
86.0k
  bool Includes(const llvm::APSInt &Point) const {
38
86.0k
    return From() <= Point && 
Point <= To()86.0k
;
39
86.0k
  }
40
3.92M
  const llvm::APSInt &From() const { return *Impl.first; }
41
3.18M
  const llvm::APSInt &To() const { return *Impl.second; }
42
682k
  const llvm::APSInt *getConcreteValue() const {
43
682k
    return &From() == &To() ? 
&From()202k
:
nullptr480k
;
44
682k
  }
45
46
1.05M
  void Profile(llvm::FoldingSetNodeID &ID) const {
47
1.05M
    ID.AddPointer(&From());
48
1.05M
    ID.AddPointer(&To());
49
1.05M
  }
50
  void dump(raw_ostream &OS) const;
51
52
  // In order to keep non-overlapping ranges sorted, we can compare only From
53
  // points.
54
175k
  bool operator<(const Range &RHS) const { return From() < RHS.From(); }
55
56
656k
  bool operator==(const Range &RHS) const { return Impl == RHS.Impl; }
57
0
  bool operator!=(const Range &RHS) const { return !operator==(RHS); }
58
59
private:
60
  std::pair<const llvm::APSInt *, const llvm::APSInt *> Impl;
61
};
62
63
/// @class RangeSet is a persistent set of non-overlapping ranges.
64
///
65
/// New RangeSet objects can be ONLY produced by RangeSet::Factory object, which
66
/// also supports the most common operations performed on range sets.
67
///
68
/// Empty set corresponds to an overly constrained symbol meaning that there
69
/// are no possible values for that symbol.
70
class RangeSet {
71
public:
72
  class Factory;
73
74
private:
75
  // We use llvm::SmallVector as the underlying container for the following
76
  // reasons:
77
  //
78
  //   * Range sets are usually very simple, 1 or 2 ranges.
79
  //     That's why llvm::ImmutableSet is not perfect.
80
  //
81
  //   * Ranges in sets are NOT overlapping, so it is natural to keep them
82
  //     sorted for efficient operations and queries.  For this reason,
83
  //     llvm::SmallSet doesn't fit the requirements, it is not sorted when it
84
  //     is a vector.
85
  //
86
  //   * Range set operations usually a bit harder than add/remove a range.
87
  //     Complex operations might do many of those for just one range set.
88
  //     Formerly it used to be llvm::ImmutableSet, which is inefficient for our
89
  //     purposes as we want to make these operations BOTH immutable AND
90
  //     efficient.
91
  //
92
  //   * Iteration over ranges is widespread and a more cache-friendly
93
  //     structure is preferred.
94
  using ImplType = llvm::SmallVector<Range, 4>;
95
96
  struct ContainerType : public ImplType, public llvm::FoldingSetNode {
97
1.00M
    void Profile(llvm::FoldingSetNodeID &ID) const {
98
1.05M
      for (const Range &It : *this) {
99
1.05M
        It.Profile(ID);
100
1.05M
      }
101
1.00M
    }
102
  };
103
  // This is a non-owning pointer to an actual container.
104
  // The memory is fully managed by the factory and is alive as long as the
105
  // factory itself is alive.
106
  // It is a pointer as opposed to a reference, so we can easily reassign
107
  // RangeSet objects.
108
  using UnderlyingType = const ContainerType *;
109
  UnderlyingType Impl;
110
111
public:
112
  using const_iterator = ImplType::const_iterator;
113
114
1.95M
  const_iterator begin() const { return Impl->begin(); }
115
528k
  const_iterator end() const { return Impl->end(); }
116
398k
  size_t size() const { return Impl->size(); }
117
118
2.16M
  bool isEmpty() const { return Impl->empty(); }
119
120
  class Factory {
121
  public:
122
14.3k
    Factory(BasicValueFactory &BV) : ValueFactory(BV) {}
123
124
    /// Create a new set with all ranges from both LHS and RHS.
125
    /// Possible intersections are not checked here.
126
    ///
127
    /// Complexity: O(N + M)
128
    ///             where N = size(LHS), M = size(RHS)
129
    RangeSet add(RangeSet LHS, RangeSet RHS);
130
    /// Create a new set with all ranges from the original set plus the new one.
131
    /// Possible intersections are not checked here.
132
    ///
133
    /// Complexity: O(N)
134
    ///             where N = size(Original)
135
    RangeSet add(RangeSet Original, Range Element);
136
    /// Create a new set with all ranges from the original set plus the point.
137
    /// Possible intersections are not checked here.
138
    ///
139
    /// Complexity: O(N)
140
    ///             where N = size(Original)
141
    RangeSet add(RangeSet Original, const llvm::APSInt &Point);
142
143
50.1k
    RangeSet getEmptySet() { return &EmptySet; }
144
145
    /// Create a new set with just one range.
146
    /// @{
147
    RangeSet getRangeSet(Range Origin);
148
314k
    RangeSet getRangeSet(const llvm::APSInt &From, const llvm::APSInt &To) {
149
314k
      return getRangeSet(Range(From, To));
150
314k
    }
151
77.3k
    RangeSet getRangeSet(const llvm::APSInt &Origin) {
152
77.3k
      return getRangeSet(Origin, Origin);
153
77.3k
    }
154
    /// @}
155
156
    /// Intersect the given range sets.
157
    ///
158
    /// Complexity: O(N + M)
159
    ///             where N = size(LHS), M = size(RHS)
160
    RangeSet intersect(RangeSet LHS, RangeSet RHS);
161
    /// Intersect the given set with the closed range [Lower, Upper].
162
    ///
163
    /// Unlike the Range type, this range uses modular arithmetic, corresponding
164
    /// to the common treatment of C integer overflow. Thus, if the Lower bound
165
    /// is greater than the Upper bound, the range is taken to wrap around. This
166
    /// is equivalent to taking the intersection with the two ranges [Min,
167
    /// Upper] and [Lower, Max], or, alternatively, /removing/ all integers
168
    /// between Upper and Lower.
169
    ///
170
    /// Complexity: O(N)
171
    ///             where N = size(What)
172
    RangeSet intersect(RangeSet What, llvm::APSInt Lower, llvm::APSInt Upper);
173
    /// Intersect the given range with the given point.
174
    ///
175
    /// The result can be either an empty set or a set containing the given
176
    /// point depending on whether the point is in the range set.
177
    ///
178
    /// Complexity: O(logN)
179
    ///             where N = size(What)
180
    RangeSet intersect(RangeSet What, llvm::APSInt Point);
181
182
    /// Delete the given point from the range set.
183
    ///
184
    /// Complexity: O(N)
185
    ///             where N = size(From)
186
    RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point);
187
    /// Negate the given range set.
188
    ///
189
    /// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
190
    /// operation under the values of the type.
191
    ///
192
    /// We also handle MIN because applying unary minus to MIN does not change
193
    /// it.
194
    /// Example 1:
195
    /// char x = -128;        // -128 is a MIN value in a range of 'char'
196
    /// char y = -x;          // y: -128
197
    ///
198
    /// Example 2:
199
    /// unsigned char x = 0;  // 0 is a MIN value in a range of 'unsigned char'
200
    /// unsigned char y = -x; // y: 0
201
    ///
202
    /// And it makes us to separate the range
203
    /// like [MIN, N] to [MIN, MIN] U [-N, MAX].
204
    /// For instance, whole range is {-128..127} and subrange is [-128,-126],
205
    /// thus [-128,-127,-126,...] negates to [-128,...,126,127].
206
    ///
207
    /// Negate restores disrupted ranges on bounds,
208
    /// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B].
209
    ///
210
    /// Negate is a self-inverse function, i.e. negate(negate(R)) == R.
211
    ///
212
    /// Complexity: O(N)
213
    ///             where N = size(What)
214
    RangeSet negate(RangeSet What);
215
216
    /// Return associated value factory.
217
180k
    BasicValueFactory &getValueFactory() const { return ValueFactory; }
218
219
  private:
220
    /// Return a persistent version of the given container.
221
    RangeSet makePersistent(ContainerType &&From);
222
    /// Construct a new persistent version of the given container.
223
    ContainerType *construct(ContainerType &&From);
224
225
    RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS);
226
227
    // Many operations include producing new APSInt values and that's why
228
    // we need this factory.
229
    BasicValueFactory &ValueFactory;
230
    // Allocator for all the created containers.
231
    // Containers might own their own memory and that's why it is specific
232
    // for the type, so it calls container destructors upon deletion.
233
    llvm::SpecificBumpPtrAllocator<ContainerType> Arena;
234
    // Usually we deal with the same ranges and range sets over and over.
235
    // Here we track all created containers and try not to repeat ourselves.
236
    llvm::FoldingSet<ContainerType> Cache;
237
    static ContainerType EmptySet;
238
  };
239
240
  RangeSet(const RangeSet &) = default;
241
  RangeSet &operator=(const RangeSet &) = default;
242
  RangeSet(RangeSet &&) = default;
243
  RangeSet &operator=(RangeSet &&) = default;
244
  ~RangeSet() = default;
245
246
  /// Construct a new RangeSet representing '{ [From, To] }'.
247
  RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)
248
237k
      : RangeSet(F.getRangeSet(From, To)) {}
Unexecuted instantiation: clang::ento::RangeSet::RangeSet(clang::ento::RangeSet::Factory&, llvm::APSInt const&, llvm::APSInt const&)
clang::ento::RangeSet::RangeSet(clang::ento::RangeSet::Factory&, llvm::APSInt const&, llvm::APSInt const&)
Line
Count
Source
248
237k
      : RangeSet(F.getRangeSet(From, To)) {}
249
250
  /// Construct a new RangeSet representing the given point as a range.
251
  RangeSet(Factory &F, const llvm::APSInt &Point)
252
39.7k
      : RangeSet(F.getRangeSet(Point)) {}
Unexecuted instantiation: clang::ento::RangeSet::RangeSet(clang::ento::RangeSet::Factory&, llvm::APSInt const&)
clang::ento::RangeSet::RangeSet(clang::ento::RangeSet::Factory&, llvm::APSInt const&)
Line
Count
Source
252
39.7k
      : RangeSet(F.getRangeSet(Point)) {}
253
254
589k
  static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS) {
255
589k
    ID.AddPointer(RS.Impl);
256
589k
  }
257
258
  /// Profile - Generates a hash profile of this RangeSet for use
259
  ///  by FoldingSet.
260
589k
  void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, *this); }
261
262
  /// getConcreteValue - If a symbol is constrained to equal a specific integer
263
  ///  constant then this method returns that value.  Otherwise, it returns
264
  ///  NULL.
265
742k
  const llvm::APSInt *getConcreteValue() const {
266
742k
    return Impl->size() == 1 ? 
begin()->getConcreteValue()682k
:
nullptr59.8k
;
267
742k
  }
268
269
  /// Get the minimal value covered by the ranges in the set.
270
  ///
271
  /// Complexity: O(1)
272
  const llvm::APSInt &getMinValue() const;
273
  /// Get the maximal value covered by the ranges in the set.
274
  ///
275
  /// Complexity: O(1)
276
  const llvm::APSInt &getMaxValue() const;
277
278
  /// Test whether the given point is contained by any of the ranges.
279
  ///
280
  /// Complexity: O(logN)
281
  ///             where N = size(this)
282
95.0k
  bool contains(llvm::APSInt Point) const { return containsImpl(Point); }
283
284
  void dump(raw_ostream &OS) const;
285
286
643k
  bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; }
287
0
  bool operator!=(const RangeSet &Other) const { return !(*this == Other); }
288
289
private:
290
532k
  /* implicit */ RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {}
291
0
  /* implicit */ RangeSet(UnderlyingType Ptr) : Impl(Ptr) {}
292
293
  /// Pin given points to the type represented by the current range set.
294
  ///
295
  /// This makes parameter points to be in-out parameters.
296
  /// In order to maintain consistent types across all of the ranges in the set
297
  /// and to keep all the operations to compare ONLY points of the same type, we
298
  /// need to pin every point before any operation.
299
  ///
300
  /// @Returns true if the given points can be converted to the target type
301
  ///          without changing the values (i.e. trivially) and false otherwise.
302
  /// @{
303
  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
304
  bool pin(llvm::APSInt &Point) const;
305
  /// @}
306
307
  // This version of this function modifies its arguments (pins it).
308
  bool containsImpl(llvm::APSInt &Point) const;
309
310
  friend class Factory;
311
};
312
313
using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>;
314
ConstraintMap getConstraintMap(ProgramStateRef State);
315
316
class RangedConstraintManager : public SimpleConstraintManager {
317
public:
318
  RangedConstraintManager(ExprEngine *EE, SValBuilder &SB)
319
14.3k
      : SimpleConstraintManager(EE, SB) {}
320
321
  ~RangedConstraintManager() override;
322
323
  //===------------------------------------------------------------------===//
324
  // Implementation for interface from SimpleConstraintManager.
325
  //===------------------------------------------------------------------===//
326
327
  ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym,
328
                            bool Assumption) override;
329
330
  ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym,
331
                                          const llvm::APSInt &From,
332
                                          const llvm::APSInt &To,
333
                                          bool InRange) override;
334
335
  ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym,
336
                                       bool Assumption) override;
337
338
protected:
339
  /// Assume a constraint between a symbolic expression and a concrete integer.
340
  virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym,
341
                                       BinaryOperator::Opcode op,
342
                                       const llvm::APSInt &Int);
343
344
  //===------------------------------------------------------------------===//
345
  // Interface that subclasses must implement.
346
  //===------------------------------------------------------------------===//
347
348
  // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison
349
  // operation for the method being invoked.
350
351
  virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
352
                                      const llvm::APSInt &V,
353
                                      const llvm::APSInt &Adjustment) = 0;
354
355
  virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
356
                                      const llvm::APSInt &V,
357
                                      const llvm::APSInt &Adjustment) = 0;
358
359
  virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
360
                                      const llvm::APSInt &V,
361
                                      const llvm::APSInt &Adjustment) = 0;
362
363
  virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
364
                                      const llvm::APSInt &V,
365
                                      const llvm::APSInt &Adjustment) = 0;
366
367
  virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
368
                                      const llvm::APSInt &V,
369
                                      const llvm::APSInt &Adjustment) = 0;
370
371
  virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
372
                                      const llvm::APSInt &V,
373
                                      const llvm::APSInt &Adjustment) = 0;
374
375
  virtual ProgramStateRef assumeSymWithinInclusiveRange(
376
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
377
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
378
379
  virtual ProgramStateRef assumeSymOutsideInclusiveRange(
380
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
381
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
382
383
  //===------------------------------------------------------------------===//
384
  // Internal implementation.
385
  //===------------------------------------------------------------------===//
386
private:
387
  static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment);
388
};
389
390
/// Try to simplify a given symbolic expression's associated value based on the
391
/// constraints in State. This is needed because the Environment bindings are
392
/// not getting updated when a new constraint is added to the State.
393
SymbolRef simplify(ProgramStateRef State, SymbolRef Sym);
394
395
} // namespace ento
396
} // namespace clang
397
398
REGISTER_FACTORY_WITH_PROGRAMSTATE(ConstraintMap)
399
400
#endif