Coverage Report

Created: 2020-09-19 12:23

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Line
Count
Source (jump to first uncovered line)
1
//== RangeConstraintManager.cpp - Manage range constraints.------*- 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 defines RangeConstraintManager, a class that tracks simple
10
//  equality and inequality constraints on symbolic values of ProgramState.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/Basic/JsonSupport.h"
15
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
16
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
17
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
20
#include "llvm/ADT/FoldingSet.h"
21
#include "llvm/ADT/ImmutableSet.h"
22
#include "llvm/Support/raw_ostream.h"
23
24
using namespace clang;
25
using namespace ento;
26
27
// This class can be extended with other tables which will help to reason
28
// about ranges more precisely.
29
class OperatorRelationsTable {
30
  static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE &&
31
                    BO_GE < BO_EQ && BO_EQ < BO_NE,
32
                "This class relies on operators order. Rework it otherwise.");
33
34
public:
35
  enum TriStateKind {
36
    False = 0,
37
    True,
38
    Unknown,
39
  };
40
41
private:
42
  // CmpOpTable holds states which represent the corresponding range for
43
  // branching an exploded graph. We can reason about the branch if there is
44
  // a previously known fact of the existence of a comparison expression with
45
  // operands used in the current expression.
46
  // E.g. assuming (x < y) is true that means (x != y) is surely true.
47
  // if (x previous_operation y)  // <    | !=      | >
48
  //   if (x operation y)         // !=   | >       | <
49
  //     tristate                 // True | Unknown | False
50
  //
51
  // CmpOpTable represents next:
52
  // __|< |> |<=|>=|==|!=|UnknownX2|
53
  // < |1 |0 |* |0 |0 |* |1        |
54
  // > |0 |1 |0 |* |0 |* |1        |
55
  // <=|1 |0 |1 |* |1 |* |0        |
56
  // >=|0 |1 |* |1 |1 |* |0        |
57
  // ==|0 |0 |* |* |1 |0 |1        |
58
  // !=|1 |1 |* |* |0 |1 |0        |
59
  //
60
  // Columns stands for a previous operator.
61
  // Rows stands for a current operator.
62
  // Each row has exactly two `Unknown` cases.
63
  // UnknownX2 means that both `Unknown` previous operators are met in code,
64
  // and there is a special column for that, for example:
65
  // if (x >= y)
66
  //   if (x != y)
67
  //     if (x <= y)
68
  //       False only
69
  static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1;
70
  const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = {
71
      // <      >      <=     >=     ==     !=    UnknownX2
72
      {True, False, Unknown, False, False, Unknown, True}, // <
73
      {False, True, False, Unknown, False, Unknown, True}, // >
74
      {True, False, True, Unknown, True, Unknown, False},  // <=
75
      {False, True, Unknown, True, True, Unknown, False},  // >=
76
      {False, False, Unknown, Unknown, True, False, True}, // ==
77
      {True, True, Unknown, Unknown, False, True, False},  // !=
78
  };
79
80
1.04k
  static size_t getIndexFromOp(BinaryOperatorKind OP) {
81
1.04k
    return static_cast<size_t>(OP - BO_LT);
82
1.04k
  }
83
84
public:
85
18.4k
  constexpr size_t getCmpOpCount() const { return CmpOpCount; }
86
87
15.9k
  static BinaryOperatorKind getOpFromIndex(size_t Index) {
88
15.9k
    return static_cast<BinaryOperatorKind>(Index + BO_LT);
89
15.9k
  }
90
91
  TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
92
494
                             BinaryOperatorKind QueriedOP) const {
93
494
    return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
94
494
  }
95
96
54
  TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const {
97
54
    return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];
98
54
  }
99
};
100
//===----------------------------------------------------------------------===//
101
//                           RangeSet implementation
102
//===----------------------------------------------------------------------===//
103
104
void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
105
                                const llvm::APSInt &Lower,
106
                                const llvm::APSInt &Upper,
107
                                PrimRangeSet &newRanges,
108
                                PrimRangeSet::iterator &i,
109
256k
                                PrimRangeSet::iterator &e) const {
110
  // There are six cases for each range R in the set:
111
  //   1. R is entirely before the intersection range.
112
  //   2. R is entirely after the intersection range.
113
  //   3. R contains the entire intersection range.
114
  //   4. R starts before the intersection range and ends in the middle.
115
  //   5. R starts in the middle of the intersection range and ends after it.
116
  //   6. R is entirely contained in the intersection range.
117
  // These correspond to each of the conditions below.
118
291k
  for (/* i = begin(), e = end() */; i != e; 
++i35.2k
) {
119
261k
    if (i->To() < Lower) {
120
10.1k
      continue;
121
10.1k
    }
122
250k
    if (i->From() > Upper) {
123
80.0k
      break;
124
80.0k
    }
125
170k
126
170k
    if (i->Includes(Lower)) {
127
165k
      if (i->Includes(Upper)) {
128
142k
        newRanges =
129
142k
            F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
130
142k
        break;
131
142k
      } else
132
23.2k
        newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
133
5.17k
    } else {
134
5.17k
      if (i->Includes(Upper)) {
135
3.32k
        newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
136
3.32k
        break;
137
3.32k
      } else
138
1.85k
        newRanges = F.add(newRanges, *i);
139
5.17k
    }
140
170k
  }
141
256k
}
142
143
300k
const llvm::APSInt &RangeSet::getMinValue() const {
144
300k
  assert(!isEmpty());
145
300k
  return begin()->From();
146
300k
}
147
148
73.0k
const llvm::APSInt &RangeSet::getMaxValue() const {
149
73.0k
  assert(!isEmpty());
150
  // NOTE: It's a shame that we can't implement 'getMaxValue' without scanning
151
  //       the whole tree to get to the last element.
152
  //       llvm::ImmutableSet should support decrement for 'end' iterators
153
  //       or reverse order iteration.
154
73.0k
  auto It = begin();
155
73.1k
  for (auto End = end(); std::next(It) != End; 
++It88
) {
156
88
  }
157
73.0k
  return It->To();
158
73.0k
}
159
160
226k
bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
161
226k
  if (isEmpty()) {
162
    // This range is already infeasible.
163
0
    return false;
164
0
  }
165
226k
166
  // This function has nine cases, the cartesian product of range-testing
167
  // both the upper and lower bounds against the symbol's type.
168
  // Each case requires a different pinning operation.
169
  // The function returns false if the described range is entirely outside
170
  // the range of values for the associated symbol.
171
226k
  APSIntType Type(getMinValue());
172
226k
  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
173
226k
  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
174
226k
175
226k
  switch (LowerTest) {
176
24
  case APSIntType::RTR_Below:
177
24
    switch (UpperTest) {
178
4
    case APSIntType::RTR_Below:
179
      // The entire range is outside the symbol's set of possible values.
180
      // If this is a conventionally-ordered range, the state is infeasible.
181
4
      if (Lower <= Upper)
182
3
        return false;
183
1
184
      // However, if the range wraps around, it spans all possible values.
185
1
      Lower = Type.getMinValue();
186
1
      Upper = Type.getMaxValue();
187
1
      break;
188
16
    case APSIntType::RTR_Within:
189
      // The range starts below what's possible but ends within it. Pin.
190
16
      Lower = Type.getMinValue();
191
16
      Type.apply(Upper);
192
16
      break;
193
4
    case APSIntType::RTR_Above:
194
      // The range spans all possible values for the symbol. Pin.
195
4
      Lower = Type.getMinValue();
196
4
      Upper = Type.getMaxValue();
197
4
      break;
198
21
    }
199
21
    break;
200
226k
  case APSIntType::RTR_Within:
201
226k
    switch (UpperTest) {
202
33
    case APSIntType::RTR_Below:
203
      // The range wraps around, but all lower values are not possible.
204
33
      Type.apply(Lower);
205
33
      Upper = Type.getMaxValue();
206
33
      break;
207
226k
    case APSIntType::RTR_Within:
208
      // The range may or may not wrap around, but both limits are valid.
209
226k
      Type.apply(Lower);
210
226k
      Type.apply(Upper);
211
226k
      break;
212
6
    case APSIntType::RTR_Above:
213
      // The range starts within what's possible but ends above it. Pin.
214
6
      Type.apply(Lower);
215
6
      Upper = Type.getMaxValue();
216
6
      break;
217
226k
    }
218
226k
    break;
219
13
  case APSIntType::RTR_Above:
220
13
    switch (UpperTest) {
221
4
    case APSIntType::RTR_Below:
222
      // The range wraps but is outside the symbol's set of possible values.
223
4
      return false;
224
6
    case APSIntType::RTR_Within:
225
      // The range starts above what's possible but ends within it (wrap).
226
6
      Lower = Type.getMinValue();
227
6
      Type.apply(Upper);
228
6
      break;
229
3
    case APSIntType::RTR_Above:
230
      // The entire range is outside the symbol's set of possible values.
231
      // If this is a conventionally-ordered range, the state is infeasible.
232
3
      if (Lower <= Upper)
233
2
        return false;
234
1
235
      // However, if the range wraps around, it spans all possible values.
236
1
      Lower = Type.getMinValue();
237
1
      Upper = Type.getMaxValue();
238
1
      break;
239
7
    }
240
7
    break;
241
226k
  }
242
226k
243
226k
  return true;
244
226k
}
245
246
// Returns a set containing the values in the receiving set, intersected with
247
// the closed range [Lower, Upper]. Unlike the Range type, this range uses
248
// modular arithmetic, corresponding to the common treatment of C integer
249
// overflow. Thus, if the Lower bound is greater than the Upper bound, the
250
// range is taken to wrap around. This is equivalent to taking the
251
// intersection with the two ranges [Min, Upper] and [Lower, Max],
252
// or, alternatively, /removing/ all integers between Upper and Lower.
253
RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
254
226k
                             llvm::APSInt Lower, llvm::APSInt Upper) const {
255
226k
  PrimRangeSet newRanges = F.getEmptySet();
256
226k
257
226k
  if (isEmpty() || !pin(Lower, Upper))
258
9
    return newRanges;
259
226k
260
226k
  PrimRangeSet::iterator i = begin(), e = end();
261
226k
  if (Lower <= Upper)
262
196k
    IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
263
29.6k
  else {
264
    // The order of the next two statements is important!
265
    // IntersectInRange() does not reset the iteration state for i and e.
266
    // Therefore, the lower range most be handled first.
267
29.6k
    IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
268
29.6k
    IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
269
29.6k
  }
270
226k
271
226k
  return newRanges;
272
226k
}
273
274
// Returns a set containing the values in the receiving set, intersected with
275
// the range set passed as parameter.
276
RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
277
1.59k
                             const RangeSet &Other) const {
278
1.59k
  PrimRangeSet newRanges = F.getEmptySet();
279
1.59k
280
4.41k
  for (iterator i = Other.begin(), e = Other.end(); i != e; 
++i2.82k
) {
281
2.82k
    RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
282
5.16k
    for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; 
++j2.34k
) {
283
2.34k
      newRanges = F.add(newRanges, *j);
284
2.34k
    }
285
2.82k
  }
286
1.59k
287
1.59k
  return newRanges;
288
1.59k
}
289
290
// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
291
// operation under the values of the type.
292
//
293
// We also handle MIN because applying unary minus to MIN does not change it.
294
// Example 1:
295
// char x = -128;        // -128 is a MIN value in a range of 'char'
296
// char y = -x;          // y: -128
297
// Example 2:
298
// unsigned char x = 0;  // 0 is a MIN value in a range of 'unsigned char'
299
// unsigned char y = -x; // y: 0
300
//
301
// And it makes us to separate the range
302
// like [MIN, N] to [MIN, MIN] U [-N,MAX].
303
// For instance, whole range is {-128..127} and subrange is [-128,-126],
304
// thus [-128,-127,-126,.....] negates to [-128,.....,126,127].
305
//
306
// Negate restores disrupted ranges on bounds,
307
// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B].
308
634
RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
309
634
  PrimRangeSet newRanges = F.getEmptySet();
310
634
311
634
  if (isEmpty())
312
0
    return newRanges;
313
634
314
634
  const llvm::APSInt sampleValue = getMinValue();
315
634
  const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
316
634
  const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
317
634
318
  // Handle a special case for MIN value.
319
634
  iterator i = begin();
320
634
  const llvm::APSInt &from = i->From();
321
634
  const llvm::APSInt &to = i->To();
322
634
  if (from == MIN) {
323
    // If [from, to] are [MIN, MAX], then just return the same [MIN, MAX].
324
172
    if (to == MAX) {
325
16
      newRanges = ranges;
326
156
    } else {
327
      // Add separate range for the lowest value.
328
156
      newRanges = F.add(newRanges, Range(MIN, MIN));
329
      // Skip adding the second range in case when [from, to] are [MIN, MIN].
330
156
      if (to != MIN) {
331
104
        newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX));
332
104
      }
333
156
    }
334
    // Skip the first range in the loop.
335
172
    ++i;
336
172
  }
337
634
338
  // Negate all other ranges.
339
1.55k
  for (iterator e = end(); i != e; 
++i921
) {
340
    // Negate int values.
341
921
    const llvm::APSInt &newFrom = BV.getValue(-i->To());
342
921
    const llvm::APSInt &newTo = BV.getValue(-i->From());
343
    // Add a negated range.
344
921
    newRanges = F.add(newRanges, Range(newFrom, newTo));
345
921
  }
346
634
347
634
  if (newRanges.isSingleton())
348
151
    return newRanges;
349
483
350
  // Try to find and unite next ranges:
351
  // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
352
483
  iterator iter1 = newRanges.begin();
353
483
  iterator iter2 = std::next(iter1);
354
483
355
483
  if (iter1->To() == MIN && 
(iter2->From() - 1) == MIN148
) {
356
90
    const llvm::APSInt &to = iter2->To();
357
    // remove adjacent ranges
358
90
    newRanges = F.remove(newRanges, *iter1);
359
90
    newRanges = F.remove(newRanges, *newRanges.begin());
360
    // add united range
361
90
    newRanges = F.add(newRanges, Range(MIN, to));
362
90
  }
363
483
364
483
  return newRanges;
365
483
}
366
367
RangeSet RangeSet::Delete(BasicValueFactory &BV, Factory &F,
368
100k
                          const llvm::APSInt &Point) const {
369
100k
  llvm::APSInt Upper = Point;
370
100k
  llvm::APSInt Lower = Point;
371
100k
372
100k
  ++Upper;
373
100k
  --Lower;
374
100k
375
  // Notice that the lower bound is greater than the upper bound.
376
100k
  return Intersect(BV, F, Upper, Lower);
377
100k
}
378
379
46
void RangeSet::print(raw_ostream &os) const {
380
46
  bool isFirst = true;
381
46
  os << "{ ";
382
92
  for (iterator i = begin(), e = end(); i != e; 
++i46
) {
383
46
    if (isFirst)
384
46
      isFirst = false;
385
0
    else
386
0
      os << ", ";
387
46
388
46
    os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
389
46
       << ']';
390
46
  }
391
46
  os << " }";
392
46
}
393
394
REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
395
396
namespace {
397
class EquivalenceClass;
398
} // end anonymous namespace
399
400
REGISTER_MAP_WITH_PROGRAMSTATE(ClassMap, SymbolRef, EquivalenceClass)
401
REGISTER_MAP_WITH_PROGRAMSTATE(ClassMembers, EquivalenceClass, SymbolSet)
402
REGISTER_MAP_WITH_PROGRAMSTATE(ConstraintRange, EquivalenceClass, RangeSet)
403
404
REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass)
405
REGISTER_MAP_WITH_PROGRAMSTATE(DisequalityMap, EquivalenceClass, ClassSet)
406
407
namespace {
408
/// This class encapsulates a set of symbols equal to each other.
409
///
410
/// The main idea of the approach requiring such classes is in narrowing
411
/// and sharing constraints between symbols within the class.  Also we can
412
/// conclude that there is no practical need in storing constraints for
413
/// every member of the class separately.
414
///
415
/// Main terminology:
416
///
417
///   * "Equivalence class" is an object of this class, which can be efficiently
418
///     compared to other classes.  It represents the whole class without
419
///     storing the actual in it.  The members of the class however can be
420
///     retrieved from the state.
421
///
422
///   * "Class members" are the symbols corresponding to the class.  This means
423
///     that A == B for every member symbols A and B from the class.  Members of
424
///     each class are stored in the state.
425
///
426
///   * "Trivial class" is a class that has and ever had only one same symbol.
427
///
428
///   * "Merge operation" merges two classes into one.  It is the main operation
429
///     to produce non-trivial classes.
430
///     If, at some point, we can assume that two symbols from two distinct
431
///     classes are equal, we can merge these classes.
432
class EquivalenceClass : public llvm::FoldingSetNode {
433
public:
434
  /// Find equivalence class for the given symbol in the given state.
435
  LLVM_NODISCARD static inline EquivalenceClass find(ProgramStateRef State,
436
                                                     SymbolRef Sym);
437
438
  /// Merge classes for the given symbols and return a new state.
439
  LLVM_NODISCARD static inline ProgramStateRef
440
  merge(BasicValueFactory &BV, RangeSet::Factory &F, ProgramStateRef State,
441
        SymbolRef First, SymbolRef Second);
442
  // Merge this class with the given class and return a new state.
443
  LLVM_NODISCARD inline ProgramStateRef merge(BasicValueFactory &BV,
444
                                              RangeSet::Factory &F,
445
                                              ProgramStateRef State,
446
                                              EquivalenceClass Other);
447
448
  /// Return a set of class members for the given state.
449
  LLVM_NODISCARD inline SymbolSet getClassMembers(ProgramStateRef State);
450
  /// Return true if the current class is trivial in the given state.
451
  LLVM_NODISCARD inline bool isTrivial(ProgramStateRef State);
452
  /// Return true if the current class is trivial and its only member is dead.
453
  LLVM_NODISCARD inline bool isTriviallyDead(ProgramStateRef State,
454
                                             SymbolReaper &Reaper);
455
456
  LLVM_NODISCARD static inline ProgramStateRef
457
  markDisequal(BasicValueFactory &BV, RangeSet::Factory &F,
458
               ProgramStateRef State, SymbolRef First, SymbolRef Second);
459
  LLVM_NODISCARD static inline ProgramStateRef
460
  markDisequal(BasicValueFactory &BV, RangeSet::Factory &F,
461
               ProgramStateRef State, EquivalenceClass First,
462
               EquivalenceClass Second);
463
  LLVM_NODISCARD inline ProgramStateRef
464
  markDisequal(BasicValueFactory &BV, RangeSet::Factory &F,
465
               ProgramStateRef State, EquivalenceClass Other) const;
466
  LLVM_NODISCARD static inline ClassSet
467
  getDisequalClasses(ProgramStateRef State, SymbolRef Sym);
468
  LLVM_NODISCARD inline ClassSet
469
  getDisequalClasses(ProgramStateRef State) const;
470
  LLVM_NODISCARD inline ClassSet
471
  getDisequalClasses(DisequalityMapTy Map, ClassSet::Factory &Factory) const;
472
473
  LLVM_NODISCARD static inline Optional<bool>
474
  areEqual(ProgramStateRef State, SymbolRef First, SymbolRef Second);
475
476
  /// Check equivalence data for consistency.
477
  LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED static bool
478
  isClassDataConsistent(ProgramStateRef State);
479
480
1.37k
  LLVM_NODISCARD QualType getType() const {
481
1.37k
    return getRepresentativeSymbol()->getType();
482
1.37k
  }
483
484
  EquivalenceClass() = delete;
485
  EquivalenceClass(const EquivalenceClass &) = default;
486
  EquivalenceClass &operator=(const EquivalenceClass &) = delete;
487
  EquivalenceClass(EquivalenceClass &&) = default;
488
  EquivalenceClass &operator=(EquivalenceClass &&) = delete;
489
490
2.97M
  bool operator==(const EquivalenceClass &Other) const {
491
2.97M
    return ID == Other.ID;
492
2.97M
  }
493
1.99M
  bool operator<(const EquivalenceClass &Other) const { return ID < Other.ID; }
494
0
  bool operator!=(const EquivalenceClass &Other) const {
495
0
    return !operator==(Other);
496
0
  }
497
498
608k
  static void Profile(llvm::FoldingSetNodeID &ID, uintptr_t CID) {
499
608k
    ID.AddInteger(CID);
500
608k
  }
501
502
608k
  void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, this->ID); }
503
504
private:
505
  /* implicit */ EquivalenceClass(SymbolRef Sym)
506
701k
      : ID(reinterpret_cast<uintptr_t>(Sym)) {}
507
508
  /// This function is intended to be used ONLY within the class.
509
  /// The fact that ID is a pointer to a symbol is an implementation detail
510
  /// and should stay that way.
511
  /// In the current implementation, we use it to retrieve the only member
512
  /// of the trivial class.
513
1.87M
  SymbolRef getRepresentativeSymbol() const {
514
1.87M
    return reinterpret_cast<SymbolRef>(ID);
515
1.87M
  }
516
  static inline SymbolSet::Factory &getMembersFactory(ProgramStateRef State);
517
518
  inline ProgramStateRef mergeImpl(BasicValueFactory &BV, RangeSet::Factory &F,
519
                                   ProgramStateRef State, SymbolSet Members,
520
                                   EquivalenceClass Other,
521
                                   SymbolSet OtherMembers);
522
  static inline void
523
  addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
524
                       BasicValueFactory &BV, RangeSet::Factory &F,
525
                       ProgramStateRef State, EquivalenceClass First,
526
                       EquivalenceClass Second);
527
528
  /// This is a unique identifier of the class.
529
  uintptr_t ID;
530
};
531
532
//===----------------------------------------------------------------------===//
533
//                             Constraint functions
534
//===----------------------------------------------------------------------===//
535
536
LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State,
537
550k
                                                    EquivalenceClass Class) {
538
550k
  return State->get<ConstraintRange>(Class);
539
550k
}
540
541
LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State,
542
549k
                                                    SymbolRef Sym) {
543
549k
  return getConstraint(State, EquivalenceClass::find(State, Sym));
544
549k
}
545
546
//===----------------------------------------------------------------------===//
547
//                       Equality/diseqiality abstraction
548
//===----------------------------------------------------------------------===//
549
550
/// A small helper structure representing symbolic equality.
551
///
552
/// Equality check can have different forms (like a == b or a - b) and this
553
/// class encapsulates those away if the only thing the user wants to check -
554
/// whether it's equality/diseqiality or not and have an easy access to the
555
/// compared symbols.
556
struct EqualityInfo {
557
public:
558
  SymbolRef Left, Right;
559
  // true for equality and false for disequality.
560
  bool IsEquality = true;
561
562
648
  void invert() { IsEquality = !IsEquality; }
563
  /// Extract equality information from the given symbol and the constants.
564
  ///
565
  /// This function assumes the following expression Sym + Adjustment != Int.
566
  /// It is a default because the most widespread case of the equality check
567
  /// is (A == B) + 0 != 0.
568
  static Optional<EqualityInfo> extract(SymbolRef Sym, const llvm::APSInt &Int,
569
121k
                                        const llvm::APSInt &Adjustment) {
570
    // As of now, the only equality form supported is Sym + 0 != 0.
571
121k
    if (!Int.isNullValue() || 
!Adjustment.isNullValue()117k
)
572
4.57k
      return llvm::None;
573
116k
574
116k
    return extract(Sym);
575
116k
  }
576
  /// Extract equality information from the given symbol.
577
360k
  static Optional<EqualityInfo> extract(SymbolRef Sym) {
578
360k
    return EqualityExtractor().Visit(Sym);
579
360k
  }
580
581
private:
582
  class EqualityExtractor
583
      : public SymExprVisitor<EqualityExtractor, Optional<EqualityInfo>> {
584
  public:
585
10.7k
    Optional<EqualityInfo> VisitSymSymExpr(const SymSymExpr *Sym) const {
586
10.7k
      switch (Sym->getOpcode()) {
587
4.53k
      case BO_Sub:
588
        // This case is: A - B != 0 -> disequality check.
589
4.53k
        return EqualityInfo{Sym->getLHS(), Sym->getRHS(), false};
590
754
      case BO_EQ:
591
        // This case is: A == B != 0 -> equality check.
592
754
        return EqualityInfo{Sym->getLHS(), Sym->getRHS(), true};
593
131
      case BO_NE:
594
        // This case is: A != B != 0 -> diseqiality check.
595
131
        return EqualityInfo{Sym->getLHS(), Sym->getRHS(), false};
596
5.28k
      default:
597
5.28k
        return llvm::None;
598
10.7k
      }
599
10.7k
    }
600
  };
601
};
602
603
//===----------------------------------------------------------------------===//
604
//                            Intersection functions
605
//===----------------------------------------------------------------------===//
606
607
template <class SecondTy, class... RestTy>
608
LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV,
609
                                         RangeSet::Factory &F, RangeSet Head,
610
                                         SecondTy Second, RestTy... Tail);
611
612
template <class... RangeTy> struct IntersectionTraits;
613
614
template <class... TailTy> struct IntersectionTraits<RangeSet, TailTy...> {
615
  // Found RangeSet, no need to check any further
616
  using Type = RangeSet;
617
};
618
619
template <> struct IntersectionTraits<> {
620
  // We ran out of types, and we didn't find any RangeSet, so the result should
621
  // be optional.
622
  using Type = Optional<RangeSet>;
623
};
624
625
template <class OptionalOrPointer, class... TailTy>
626
struct IntersectionTraits<OptionalOrPointer, TailTy...> {
627
  // If current type is Optional or a raw pointer, we should keep looking.
628
  using Type = typename IntersectionTraits<TailTy...>::Type;
629
};
630
631
template <class EndTy>
632
LLVM_NODISCARD inline EndTy intersect(BasicValueFactory &BV,
633
243k
                                      RangeSet::Factory &F, EndTy End) {
634
  // If the list contains only RangeSet or Optional<RangeSet>, simply return
635
  // that range set.
636
243k
  return End;
637
243k
}
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<clang::ento::RangeSet>(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, clang::ento::RangeSet)
Line
Count
Source
633
95.6k
                                      RangeSet::Factory &F, EndTy End) {
634
  // If the list contains only RangeSet or Optional<RangeSet>, simply return
635
  // that range set.
636
95.6k
  return End;
637
95.6k
}
RangeConstraintManager.cpp:llvm::Optional<clang::ento::RangeSet> (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, llvm::Optional<clang::ento::RangeSet>)
Line
Count
Source
633
147k
                                      RangeSet::Factory &F, EndTy End) {
634
  // If the list contains only RangeSet or Optional<RangeSet>, simply return
635
  // that range set.
636
147k
  return End;
637
147k
}
638
639
LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional<RangeSet>
640
374
intersect(BasicValueFactory &BV, RangeSet::Factory &F, const RangeSet *End) {
641
  // This is an extraneous conversion from a raw pointer into Optional<RangeSet>
642
374
  if (End) {
643
72
    return *End;
644
72
  }
645
302
  return llvm::None;
646
302
}
647
648
template <class... RestTy>
649
LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV,
650
                                         RangeSet::Factory &F, RangeSet Head,
651
1.59k
                                         RangeSet Second, RestTy... Tail) {
652
  // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
653
  // of the function and can be sure that the result is RangeSet.
654
1.59k
  return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
655
1.59k
}
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, clang::ento::RangeSet, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>)
Line
Count
Source
651
274
                                         RangeSet Second, RestTy... Tail) {
652
  // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
653
  // of the function and can be sure that the result is RangeSet.
654
274
  return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
655
274
}
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<>(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, clang::ento::RangeSet, clang::ento::RangeSet)
Line
Count
Source
651
1.32k
                                         RangeSet Second, RestTy... Tail) {
652
  // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
653
  // of the function and can be sure that the result is RangeSet.
654
1.32k
  return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
655
1.32k
}
656
657
template <class SecondTy, class... RestTy>
658
LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV,
659
                                         RangeSet::Factory &F, RangeSet Head,
660
190k
                                         SecondTy Second, RestTy... Tail) {
661
190k
  if (Second) {
662
    // Here we call the <RangeSet,RangeSet,...> version of the function...
663
1.59k
    return intersect(BV, F, Head, *Second, Tail...);
664
1.59k
  }
665
  // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which
666
  // means that the result is definitely RangeSet.
667
189k
  return intersect(BV, F, Head, Tail...);
668
189k
}
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>)
Line
Count
Source
660
95.3k
                                         SecondTy Second, RestTy... Tail) {
661
95.3k
  if (Second) {
662
    // Here we call the <RangeSet,RangeSet,...> version of the function...
663
274
    return intersect(BV, F, Head, *Second, Tail...);
664
274
  }
665
  // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which
666
  // means that the result is definitely RangeSet.
667
95.0k
  return intersect(BV, F, Head, Tail...);
668
95.0k
}
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>)
Line
Count
Source
660
95.5k
                                         SecondTy Second, RestTy... Tail) {
661
95.5k
  if (Second) {
662
    // Here we call the <RangeSet,RangeSet,...> version of the function...
663
1.18k
    return intersect(BV, F, Head, *Second, Tail...);
664
1.18k
  }
665
  // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which
666
  // means that the result is definitely RangeSet.
667
94.3k
  return intersect(BV, F, Head, Tail...);
668
94.3k
}
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<clang::ento::RangeSet const*>(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, clang::ento::RangeSet, clang::ento::RangeSet const*)
Line
Count
Source
660
135
                                         SecondTy Second, RestTy... Tail) {
661
135
  if (Second) {
662
    // Here we call the <RangeSet,RangeSet,...> version of the function...
663
132
    return intersect(BV, F, Head, *Second, Tail...);
664
132
  }
665
  // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which
666
  // means that the result is definitely RangeSet.
667
3
  return intersect(BV, F, Head, Tail...);
668
3
}
669
670
/// Main generic intersect function.
671
/// It intersects all of the given range sets.  If some of the given arguments
672
/// don't hold a range set (nullptr or llvm::None), the function will skip them.
673
///
674
/// Available representations for the arguments are:
675
///   * RangeSet
676
///   * Optional<RangeSet>
677
///   * RangeSet *
678
/// Pointer to a RangeSet is automatically assumed to be nullable and will get
679
/// checked as well as the optional version.  If this behaviour is undesired,
680
/// please dereference the pointer in the call.
681
///
682
/// Return type depends on the arguments' types.  If we can be sure in compile
683
/// time that there will be a range set as a result, the returning type is
684
/// simply RangeSet, in other cases we have to back off to Optional<RangeSet>.
685
///
686
/// Please, prefer optional range sets to raw pointers.  If the last argument is
687
/// a raw pointer and all previous arguments are None, it will cost one
688
/// additional check to convert RangeSet * into Optional<RangeSet>.
689
template <class HeadTy, class SecondTy, class... RestTy>
690
LLVM_NODISCARD inline
691
    typename IntersectionTraits<HeadTy, SecondTy, RestTy...>::Type
692
    intersect(BasicValueFactory &BV, RangeSet::Factory &F, HeadTy Head,
693
391k
              SecondTy Second, RestTy... Tail) {
694
391k
  if (Head) {
695
95.6k
    return intersect(BV, F, *Head, Second, Tail...);
696
95.6k
  }
697
296k
  return intersect(BV, F, Second, Tail...);
698
296k
}
RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >::Type (anonymous namespace)::intersect<clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>)
Line
Count
Source
693
243k
              SecondTy Second, RestTy... Tail) {
694
243k
  if (Head) {
695
95.3k
    return intersect(BV, F, *Head, Second, Tail...);
696
95.3k
  }
697
147k
  return intersect(BV, F, Second, Tail...);
698
147k
}
RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >::Type (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>)
Line
Count
Source
693
147k
              SecondTy Second, RestTy... Tail) {
694
147k
  if (Head) {
695
136
    return intersect(BV, F, *Head, Second, Tail...);
696
136
  }
697
147k
  return intersect(BV, F, Second, Tail...);
698
147k
}
RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<clang::ento::RangeSet const*, clang::ento::RangeSet const*>::Type (anonymous namespace)::intersect<clang::ento::RangeSet const*, clang::ento::RangeSet const*>(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, clang::ento::RangeSet const*, clang::ento::RangeSet const*)
Line
Count
Source
693
509
              SecondTy Second, RestTy... Tail) {
694
509
  if (Head) {
695
135
    return intersect(BV, F, *Head, Second, Tail...);
696
135
  }
697
374
  return intersect(BV, F, Second, Tail...);
698
374
}
699
700
//===----------------------------------------------------------------------===//
701
//                           Symbolic reasoning logic
702
//===----------------------------------------------------------------------===//
703
704
/// A little component aggregating all of the reasoning we have about
705
/// the ranges of symbolic expressions.
706
///
707
/// Even when we don't know the exact values of the operands, we still
708
/// can get a pretty good estimate of the result's range.
709
class SymbolicRangeInferrer
710
    : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> {
711
public:
712
  template <class SourceType>
713
  static RangeSet inferRange(BasicValueFactory &BV, RangeSet::Factory &F,
714
194k
                             ProgramStateRef State, SourceType Origin) {
715
194k
    SymbolicRangeInferrer Inferrer(BV, F, State);
716
194k
    return Inferrer.infer(Origin);
717
194k
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::inferRange<clang::ento::SymExpr const*>(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*)
Line
Count
Source
714
194k
                             ProgramStateRef State, SourceType Origin) {
715
194k
    SymbolicRangeInferrer Inferrer(BV, F, State);
716
194k
    return Inferrer.infer(Origin);
717
194k
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::inferRange<(anonymous namespace)::EquivalenceClass>(clang::ento::BasicValueFactory&, llvm::ImmutableSet<clang::ento::Range, clang::ento::RangeTrait>::Factory&, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, (anonymous namespace)::EquivalenceClass)
Line
Count
Source
714
36
                             ProgramStateRef State, SourceType Origin) {
715
36
    SymbolicRangeInferrer Inferrer(BV, F, State);
716
36
    return Inferrer.infer(Origin);
717
36
  }
718
719
103k
  RangeSet VisitSymExpr(SymbolRef Sym) {
720
    // If we got to this function, the actual type of the symbolic
721
    // expression is not supported for advanced inference.
722
    // In this case, we simply backoff to the default "let's simply
723
    // infer the range from the expression's type".
724
103k
    return infer(Sym->getType());
725
103k
  }
726
727
38.7k
  RangeSet VisitSymIntExpr(const SymIntExpr *Sym) {
728
38.7k
    return VisitBinaryOperator(Sym);
729
38.7k
  }
730
731
172
  RangeSet VisitIntSymExpr(const IntSymExpr *Sym) {
732
172
    return VisitBinaryOperator(Sym);
733
172
  }
734
735
4.83k
  RangeSet VisitSymSymExpr(const SymSymExpr *Sym) {
736
4.83k
    return VisitBinaryOperator(Sym);
737
4.83k
  }
738
739
private:
740
  SymbolicRangeInferrer(BasicValueFactory &BV, RangeSet::Factory &F,
741
                        ProgramStateRef S)
742
194k
      : ValueFactory(BV), RangeFactory(F), State(S) {}
743
744
  /// Infer range information from the given integer constant.
745
  ///
746
  /// It's not a real "inference", but is here for operating with
747
  /// sub-expressions in a more polymorphic manner.
748
38.9k
  RangeSet inferAs(const llvm::APSInt &Val, QualType) {
749
38.9k
    return {RangeFactory, Val};
750
38.9k
  }
751
752
  /// Infer range information from symbol in the context of the given type.
753
48.5k
  RangeSet inferAs(SymbolRef Sym, QualType DestType) {
754
48.5k
    QualType ActualType = Sym->getType();
755
    // Check that we can reason about the symbol at all.
756
48.5k
    if (ActualType->isIntegralOrEnumerationType() ||
757
48.5k
        
Loc::isLocType(ActualType)1.60k
) {
758
48.5k
      return infer(Sym);
759
48.5k
    }
760
    // Otherwise, let's simply infer from the destination type.
761
    // We couldn't figure out nothing else about that expression.
762
4
    return infer(DestType);
763
4
  }
764
765
243k
  RangeSet infer(SymbolRef Sym) {
766
243k
    if (Optional<RangeSet> ConstraintBasedRange = intersect(
767
95.5k
            ValueFactory, RangeFactory, getConstraint(State, Sym),
768
            // If Sym is a difference of symbols A - B, then maybe we have range
769
            // set stored for B - A.
770
            //
771
            // If we have range set stored for both A - B and B - A then
772
            // calculate the effective range set by intersecting the range set
773
            // for A - B and the negated range set of B - A.
774
95.5k
            getRangeForNegatedSub(Sym), getRangeForEqualities(Sym))) {
775
95.5k
      return *ConstraintBasedRange;
776
95.5k
    }
777
147k
778
    // If Sym is a comparison expression (except <=>),
779
    // find any other comparisons with the same operands.
780
    // See function description.
781
147k
    if (Optional<RangeSet> CmpRangeSet = getRangeForComparisonSymbol(Sym)) {
782
307
      return *CmpRangeSet;
783
307
    }
784
147k
785
147k
    return Visit(Sym);
786
147k
  }
787
788
36
  RangeSet infer(EquivalenceClass Class) {
789
36
    if (const RangeSet *AssociatedConstraint = getConstraint(State, Class))
790
16
      return *AssociatedConstraint;
791
20
792
20
    return infer(Class.getType());
793
20
  }
794
795
  /// Infer range information solely from the type.
796
112k
  RangeSet infer(QualType T) {
797
    // Lazily generate a new RangeSet representing all possible values for the
798
    // given symbol type.
799
112k
    RangeSet Result(RangeFactory, ValueFactory.getMinValue(T),
800
112k
                    ValueFactory.getMaxValue(T));
801
112k
802
    // References are known to be non-zero.
803
112k
    if (T->isReferenceType())
804
15.5k
      return assumeNonZero(Result, T);
805
96.6k
806
96.6k
    return Result;
807
96.6k
  }
808
809
  template <class BinarySymExprTy>
810
43.7k
  RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {
811
    // TODO #1: VisitBinaryOperator implementation might not make a good
812
    // use of the inferred ranges.  In this case, we might be calculating
813
    // everything for nothing.  This being said, we should introduce some
814
    // sort of laziness mechanism here.
815
    //
816
    // TODO #2: We didn't go into the nested expressions before, so it
817
    // might cause us spending much more time doing the inference.
818
    // This can be a problem for deeply nested expressions that are
819
    // involved in conditions and get tested continuously.  We definitely
820
    // need to address this issue and introduce some sort of caching
821
    // in here.
822
43.7k
    QualType ResultType = Sym->getType();
823
43.7k
    return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
824
43.7k
                               Sym->getOpcode(),
825
43.7k
                               inferAs(Sym->getRHS(), ResultType), ResultType);
826
43.7k
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0> >(clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0> const*)
Line
Count
Source
810
172
  RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {
811
    // TODO #1: VisitBinaryOperator implementation might not make a good
812
    // use of the inferred ranges.  In this case, we might be calculating
813
    // everything for nothing.  This being said, we should introduce some
814
    // sort of laziness mechanism here.
815
    //
816
    // TODO #2: We didn't go into the nested expressions before, so it
817
    // might cause us spending much more time doing the inference.
818
    // This can be a problem for deeply nested expressions that are
819
    // involved in conditions and get tested continuously.  We definitely
820
    // need to address this issue and introduce some sort of caching
821
    // in here.
822
172
    QualType ResultType = Sym->getType();
823
172
    return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
824
172
                               Sym->getOpcode(),
825
172
                               inferAs(Sym->getRHS(), ResultType), ResultType);
826
172
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1> >(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1> const*)
Line
Count
Source
810
38.7k
  RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {
811
    // TODO #1: VisitBinaryOperator implementation might not make a good
812
    // use of the inferred ranges.  In this case, we might be calculating
813
    // everything for nothing.  This being said, we should introduce some
814
    // sort of laziness mechanism here.
815
    //
816
    // TODO #2: We didn't go into the nested expressions before, so it
817
    // might cause us spending much more time doing the inference.
818
    // This can be a problem for deeply nested expressions that are
819
    // involved in conditions and get tested continuously.  We definitely
820
    // need to address this issue and introduce some sort of caching
821
    // in here.
822
38.7k
    QualType ResultType = Sym->getType();
823
38.7k
    return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
824
38.7k
                               Sym->getOpcode(),
825
38.7k
                               inferAs(Sym->getRHS(), ResultType), ResultType);
826
38.7k
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2> >(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2> const*)
Line
Count
Source
810
4.83k
  RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {
811
    // TODO #1: VisitBinaryOperator implementation might not make a good
812
    // use of the inferred ranges.  In this case, we might be calculating
813
    // everything for nothing.  This being said, we should introduce some
814
    // sort of laziness mechanism here.
815
    //
816
    // TODO #2: We didn't go into the nested expressions before, so it
817
    // might cause us spending much more time doing the inference.
818
    // This can be a problem for deeply nested expressions that are
819
    // involved in conditions and get tested continuously.  We definitely
820
    // need to address this issue and introduce some sort of caching
821
    // in here.
822
4.83k
    QualType ResultType = Sym->getType();
823
4.83k
    return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
824
4.83k
                               Sym->getOpcode(),
825
4.83k
                               inferAs(Sym->getRHS(), ResultType), ResultType);
826
4.83k
  }
827
828
  RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op,
829
43.7k
                               RangeSet RHS, QualType T) {
830
43.7k
    switch (Op) {
831
85
    case BO_Or:
832
85
      return VisitBinaryOperator<BO_Or>(LHS, RHS, T);
833
36.2k
    case BO_And:
834
36.2k
      return VisitBinaryOperator<BO_And>(LHS, RHS, T);
835
242
    case BO_Rem:
836
242
      return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);
837
7.22k
    default:
838
7.22k
      return infer(T);
839
43.7k
    }
840
43.7k
  }
841
842
  //===----------------------------------------------------------------------===//
843
  //                         Ranges and operators
844
  //===----------------------------------------------------------------------===//
845
846
  /// Return a rough approximation of the given range set.
847
  ///
848
  /// For the range set:
849
  ///   { [x_0, y_0], [x_1, y_1], ... , [x_N, y_N] }
850
  /// it will return the range [x_0, y_N].
851
73.0k
  static Range fillGaps(RangeSet Origin) {
852
73.0k
    assert(!Origin.isEmpty());
853
73.0k
    return {Origin.getMinValue(), Origin.getMaxValue()};
854
73.0k
  }
855
856
  /// Try to convert given range into the given type.
857
  ///
858
  /// It will return llvm::None only when the trivial conversion is possible.
859
73.0k
  llvm::Optional<Range> convert(const Range &Origin, APSIntType To) {
860
73.0k
    if (To.testInRange(Origin.From(), false) != APSIntType::RTR_Within ||
861
73.0k
        To.testInRange(Origin.To(), false) != APSIntType::RTR_Within) {
862
28
      return llvm::None;
863
28
    }
864
73.0k
    return Range(ValueFactory.Convert(To, Origin.From()),
865
73.0k
                 ValueFactory.Convert(To, Origin.To()));
866
73.0k
  }
867
868
  template <BinaryOperator::Opcode Op>
869
36.5k
  RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) {
870
    // We should propagate information about unfeasbility of one of the
871
    // operands to the resulting range.
872
36.5k
    if (LHS.isEmpty() || RHS.isEmpty()) {
873
0
      return RangeFactory.getEmptySet();
874
0
    }
875
36.5k
876
36.5k
    Range CoarseLHS = fillGaps(LHS);
877
36.5k
    Range CoarseRHS = fillGaps(RHS);
878
36.5k
879
36.5k
    APSIntType ResultType = ValueFactory.getAPSIntType(T);
880
36.5k
881
    // We need to convert ranges to the resulting type, so we can compare values
882
    // and combine them in a meaningful (in terms of the given operation) way.
883
36.5k
    auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
884
36.5k
    auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
885
36.5k
886
    // It is hard to reason about ranges when conversion changes
887
    // borders of the ranges.
888
36.5k
    if (!ConvertedCoarseLHS || 
!ConvertedCoarseRHS36.5k
) {
889
28
      return infer(T);
890
28
    }
891
36.5k
892
36.5k
    return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
893
36.5k
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)18>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType)
Line
Count
Source
869
85
  RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) {
870
    // We should propagate information about unfeasbility of one of the
871
    // operands to the resulting range.
872
85
    if (LHS.isEmpty() || RHS.isEmpty()) {
873
0
      return RangeFactory.getEmptySet();
874
0
    }
875
85
876
85
    Range CoarseLHS = fillGaps(LHS);
877
85
    Range CoarseRHS = fillGaps(RHS);
878
85
879
85
    APSIntType ResultType = ValueFactory.getAPSIntType(T);
880
85
881
    // We need to convert ranges to the resulting type, so we can compare values
882
    // and combine them in a meaningful (in terms of the given operation) way.
883
85
    auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
884
85
    auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
885
85
886
    // It is hard to reason about ranges when conversion changes
887
    // borders of the ranges.
888
85
    if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
889
0
      return infer(T);
890
0
    }
891
85
892
85
    return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
893
85
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)16>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType)
Line
Count
Source
869
36.2k
  RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) {
870
    // We should propagate information about unfeasbility of one of the
871
    // operands to the resulting range.
872
36.2k
    if (LHS.isEmpty() || RHS.isEmpty()) {
873
0
      return RangeFactory.getEmptySet();
874
0
    }
875
36.2k
876
36.2k
    Range CoarseLHS = fillGaps(LHS);
877
36.2k
    Range CoarseRHS = fillGaps(RHS);
878
36.2k
879
36.2k
    APSIntType ResultType = ValueFactory.getAPSIntType(T);
880
36.2k
881
    // We need to convert ranges to the resulting type, so we can compare values
882
    // and combine them in a meaningful (in terms of the given operation) way.
883
36.2k
    auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
884
36.2k
    auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
885
36.2k
886
    // It is hard to reason about ranges when conversion changes
887
    // borders of the ranges.
888
36.2k
    if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
889
0
      return infer(T);
890
0
    }
891
36.2k
892
36.2k
    return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
893
36.2k
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)4>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType)
Line
Count
Source
869
242
  RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) {
870
    // We should propagate information about unfeasbility of one of the
871
    // operands to the resulting range.
872
242
    if (LHS.isEmpty() || RHS.isEmpty()) {
873
0
      return RangeFactory.getEmptySet();
874
0
    }
875
242
876
242
    Range CoarseLHS = fillGaps(LHS);
877
242
    Range CoarseRHS = fillGaps(RHS);
878
242
879
242
    APSIntType ResultType = ValueFactory.getAPSIntType(T);
880
242
881
    // We need to convert ranges to the resulting type, so we can compare values
882
    // and combine them in a meaningful (in terms of the given operation) way.
883
242
    auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
884
242
    auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
885
242
886
    // It is hard to reason about ranges when conversion changes
887
    // borders of the ranges.
888
242
    if (!ConvertedCoarseLHS || 
!ConvertedCoarseRHS226
) {
889
28
      return infer(T);
890
28
    }
891
214
892
214
    return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
893
214
  }
894
895
  template <BinaryOperator::Opcode Op>
896
  RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) {
897
    return infer(T);
898
  }
899
900
  /// Return a symmetrical range for the given range and type.
901
  ///
902
  /// If T is signed, return the smallest range [-x..x] that covers the original
903
  /// range, or [-min(T), max(T)] if the aforementioned symmetric range doesn't
904
  /// exist due to original range covering min(T)).
905
  ///
906
  /// If T is unsigned, return the smallest range [0..x] that covers the
907
  /// original range.
908
214
  Range getSymmetricalRange(Range Origin, QualType T) {
909
214
    APSIntType RangeType = ValueFactory.getAPSIntType(T);
910
214
911
214
    if (RangeType.isUnsigned()) {
912
48
      return Range(ValueFactory.getMinValue(RangeType), Origin.To());
913
48
    }
914
166
915
166
    if (Origin.From().isMinSignedValue()) {
916
      // If mini is a minimal signed value, absolute value of it is greater
917
      // than the maximal signed value.  In order to avoid these
918
      // complications, we simply return the whole range.
919
14
      return {ValueFactory.getMinValue(RangeType),
920
14
              ValueFactory.getMaxValue(RangeType)};
921
14
    }
922
152
923
    // At this point, we are sure that the type is signed and we can safely
924
    // use unary - operator.
925
    //
926
    // While calculating absolute maximum, we can use the following formula
927
    // because of these reasons:
928
    //   * If From >= 0 then To >= From and To >= -From.
929
    //     AbsMax == To == max(To, -From)
930
    //   * If To <= 0 then -From >= -To and -From >= From.
931
    //     AbsMax == -From == max(-From, To)
932
    //   * Otherwise, From <= 0, To >= 0, and
933
    //     AbsMax == max(abs(From), abs(To))
934
152
    llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To());
935
152
936
    // Intersection is guaranteed to be non-empty.
937
152
    return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};
938
152
  }
939
940
  /// Return a range set subtracting zero from \p Domain.
941
16.7k
  RangeSet assumeNonZero(RangeSet Domain, QualType T) {
942
16.7k
    APSIntType IntType = ValueFactory.getAPSIntType(T);
943
16.7k
    return Domain.Delete(ValueFactory, RangeFactory, IntType.getZeroValue());
944
16.7k
  }
945
946
  // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
947
  //        obtain the negated symbolic expression instead of constructing the
948
  //        symbol manually. This will allow us to support finding ranges of not
949
  //        only negated SymSymExpr-type expressions, but also of other, simpler
950
  //        expressions which we currently do not know how to negate.
951
243k
  Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) {
952
243k
    if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
953
6.91k
      if (SSE->getOpcode() == BO_Sub) {
954
3.43k
        QualType T = Sym->getType();
955
3.43k
956
        // Do not negate unsigned ranges
957
3.43k
        if (!T->isUnsignedIntegerOrEnumerationType() &&
958
3.37k
            !T->isSignedIntegerOrEnumerationType())
959
0
          return llvm::None;
960
3.43k
961
3.43k
        SymbolManager &SymMgr = State->getSymbolManager();
962
3.43k
        SymbolRef NegatedSym =
963
3.43k
            SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
964
3.43k
965
3.43k
        if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) {
966
410
          return NegatedRange->Negate(ValueFactory, RangeFactory);
967
410
        }
968
242k
      }
969
6.91k
    }
970
242k
    return llvm::None;
971
242k
  }
972
973
  // Returns ranges only for binary comparison operators (except <=>)
974
  // when left and right operands are symbolic values.
975
  // Finds any other comparisons with the same operands.
976
  // Then do logical calculations and refuse impossible branches.
977
  // E.g. (x < y) and (x > y) at the same time are impossible.
978
  // E.g. (x >= y) and (x != y) at the same time makes (x > y) true only.
979
  // E.g. (x == y) and (y == x) are just reversed but the same.
980
  // It covers all possible combinations (see CmpOpTable description).
981
  // Note that `x` and `y` can also stand for subexpressions,
982
  // not only for actual symbols.
983
147k
  Optional<RangeSet> getRangeForComparisonSymbol(SymbolRef Sym) {
984
147k
    const auto *SSE = dyn_cast<SymSymExpr>(Sym);
985
147k
    if (!SSE)
986
142k
      return llvm::None;
987
5.14k
988
5.14k
    BinaryOperatorKind CurrentOP = SSE->getOpcode();
989
5.14k
990
    // We currently do not support <=> (C++20).
991
5.14k
    if (!BinaryOperator::isComparisonOp(CurrentOP) || 
(CurrentOP == BO_Cmp)2.82k
)
992
2.31k
      return llvm::None;
993
2.82k
994
2.82k
    static const OperatorRelationsTable CmpOpTable{};
995
2.82k
996
2.82k
    const SymExpr *LHS = SSE->getLHS();
997
2.82k
    const SymExpr *RHS = SSE->getRHS();
998
2.82k
    QualType T = SSE->getType();
999
2.82k
1000
2.82k
    SymbolManager &SymMgr = State->getSymbolManager();
1001
2.82k
1002
2.82k
    int UnknownStates = 0;
1003
2.82k
1004
    // Loop goes through all of the columns exept the last one ('UnknownX2').
1005
    // We treat `UnknownX2` column separately at the end of the loop body.
1006
18.4k
    for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); 
++i15.6k
) {
1007
15.9k
1008
      // Let's find an expression e.g. (x < y).
1009
15.9k
      BinaryOperatorKind QueriedOP = OperatorRelationsTable::getOpFromIndex(i);
1010
15.9k
      const SymSymExpr *SymSym = SymMgr.getSymSymExpr(LHS, QueriedOP, RHS, T);
1011
15.9k
      const RangeSet *QueriedRangeSet = getConstraint(State, SymSym);
1012
15.9k
1013
      // If ranges were not previously found,
1014
      // try to find a reversed expression (y > x).
1015
15.9k
      if (!QueriedRangeSet) {
1016
15.6k
        const BinaryOperatorKind ROP =
1017
15.6k
            BinaryOperator::reverseComparisonOp(QueriedOP);
1018
15.6k
        SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T);
1019
15.6k
        QueriedRangeSet = getConstraint(State, SymSym);
1020
15.6k
      }
1021
15.9k
1022
15.9k
      if (!QueriedRangeSet || 
QueriedRangeSet->isEmpty()494
)
1023
15.4k
        continue;
1024
494
1025
494
      const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue();
1026
494
      const bool isInFalseBranch =
1027
444
          ConcreteValue ? (*ConcreteValue == 0) : 
false50
;
1028
494
1029
      // If it is a false branch, we shall be guided by opposite operator,
1030
      // because the table is made assuming we are in the true branch.
1031
      // E.g. when (x <= y) is false, then (x > y) is true.
1032
494
      if (isInFalseBranch)
1033
256
        QueriedOP = BinaryOperator::negateComparisonOp(QueriedOP);
1034
494
1035
494
      OperatorRelationsTable::TriStateKind BranchState =
1036
494
          CmpOpTable.getCmpOpState(CurrentOP, QueriedOP);
1037
494
1038
494
      if (BranchState == OperatorRelationsTable::Unknown) {
1039
241
        if (++UnknownStates == 2)
1040
          // If we met both Unknown states.
1041
          // if (x <= y)    // assume true
1042
          //   if (x != y)  // assume true
1043
          //     if (x < y) // would be also true
1044
          // Get a state from `UnknownX2` column.
1045
54
          BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP);
1046
187
        else
1047
187
          continue;
1048
307
      }
1049
307
1050
307
      return (BranchState == OperatorRelationsTable::True) ? 
getTrueRange(T)180
1051
127
                                                           : getFalseRange(T);
1052
307
    }
1053
2.82k
1054
2.51k
    return llvm::None;
1055
2.82k
  }
1056
1057
243k
  Optional<RangeSet> getRangeForEqualities(SymbolRef Sym) {
1058
243k
    Optional<EqualityInfo> Equality = EqualityInfo::extract(Sym);
1059
243k
1060
243k
    if (!Equality)
1061
239k
      return llvm::None;
1062
3.92k
1063
3.92k
    if (Optional<bool> AreEqual = EquivalenceClass::areEqual(
1064
1.24k
            State, Equality->Left, Equality->Right)) {
1065
1.24k
      if (*AreEqual == Equality->IsEquality) {
1066
1.01k
        return getTrueRange(Sym->getType());
1067
1.01k
      }
1068
234
      return getFalseRange(Sym->getType());
1069
234
    }
1070
2.68k
1071
2.68k
    return llvm::None;
1072
2.68k
  }
1073
1074
1.19k
  RangeSet getTrueRange(QualType T) {
1075
1.19k
    RangeSet TypeRange = infer(T);
1076
1.19k
    return assumeNonZero(TypeRange, T);
1077
1.19k
  }
1078
1079
361
  RangeSet getFalseRange(QualType T) {
1080
361
    const llvm::APSInt &Zero = ValueFactory.getValue(0, T);
1081
361
    return RangeSet(RangeFactory, Zero);
1082
361
  }
1083
1084
  BasicValueFactory &ValueFactory;
1085
  RangeSet::Factory &RangeFactory;
1086
  ProgramStateRef State;
1087
};
1088
1089
//===----------------------------------------------------------------------===//
1090
//               Range-based reasoning about symbolic operations
1091
//===----------------------------------------------------------------------===//
1092
1093
template <>
1094
RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS,
1095
85
                                                           QualType T) {
1096
85
  APSIntType ResultType = ValueFactory.getAPSIntType(T);
1097
85
  llvm::APSInt Zero = ResultType.getZeroValue();
1098
85
1099
85
  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1100
85
  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1101
85
1102
85
  bool IsLHSNegative = LHS.To() < Zero;
1103
85
  bool IsRHSNegative = RHS.To() < Zero;
1104
85
1105
  // Check if both ranges have the same sign.
1106
85
  if ((IsLHSPositiveOrZero && 
IsRHSPositiveOrZero49
) ||
1107
69
      
(36
IsLHSNegative36
&&
IsRHSNegative28
)) {
1108
    // The result is definitely greater or equal than any of the operands.
1109
69
    const llvm::APSInt &Min = std::max(LHS.From(), RHS.From());
1110
69
1111
    // We estimate maximal value for positives as the maximal value for the
1112
    // given type.  For negatives, we estimate it with -1 (e.g. 0x11111111).
1113
    //
1114
    // TODO: We basically, limit the resulting range from below, but don't do
1115
    //       anything with the upper bound.
1116
    //
1117
    //       For positive operands, it can be done as follows: for the upper
1118
    //       bound of LHS and RHS we calculate the most significant bit set.
1119
    //       Let's call it the N-th bit.  Then we can estimate the maximal
1120
    //       number to be 2^(N+1)-1, i.e. the number with all the bits up to
1121
    //       the N-th bit set.
1122
69
    const llvm::APSInt &Max = IsLHSNegative
1123
20
                                  ? ValueFactory.getValue(--Zero)
1124
49
                                  : ValueFactory.getMaxValue(ResultType);
1125
69
1126
69
    return {RangeFactory, ValueFactory.getValue(Min), Max};
1127
69
  }
1128
16
1129
  // Otherwise, let's check if at least one of the operands is negative.
1130
16
  if (IsLHSNegative || 
IsRHSNegative8
) {
1131
    // This means that the result is definitely negative as well.
1132
10
    return {RangeFactory, ValueFactory.getMinValue(ResultType),
1133
10
            ValueFactory.getValue(--Zero)};
1134
10
  }
1135
6
1136
6
  RangeSet DefaultRange = infer(T);
1137
6
1138
  // It is pretty hard to reason about operands with different signs
1139
  // (and especially with possibly different signs).  We simply check if it
1140
  // can be zero.  In order to conclude that the result could not be zero,
1141
  // at least one of the operands should be definitely not zero itself.
1142
6
  if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) {
1143
4
    return assumeNonZero(DefaultRange, T);
1144
4
  }
1145
2
1146
  // Nothing much else to do here.
1147
2
  return DefaultRange;
1148
2
}
1149
1150
template <>
1151
RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS,
1152
                                                            Range RHS,
1153
36.2k
                                                            QualType T) {
1154
36.2k
  APSIntType ResultType = ValueFactory.getAPSIntType(T);
1155
36.2k
  llvm::APSInt Zero = ResultType.getZeroValue();
1156
36.2k
1157
36.2k
  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1158
36.2k
  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1159
36.2k
1160
36.2k
  bool IsLHSNegative = LHS.To() < Zero;
1161
36.2k
  bool IsRHSNegative = RHS.To() < Zero;
1162
36.2k
1163
  // Check if both ranges have the same sign.
1164
36.2k
  if ((IsLHSPositiveOrZero && 
IsRHSPositiveOrZero53
) ||
1165
36.1k
      (IsLHSNegative && 
IsRHSNegative12
)) {
1166
    // The result is definitely less or equal than any of the operands.
1167
47
    const llvm::APSInt &Max = std::min(LHS.To(), RHS.To());
1168
47
1169
    // We conservatively estimate lower bound to be the smallest positive
1170
    // or negative value corresponding to the sign of the operands.
1171
47
    const llvm::APSInt &Min = IsLHSNegative
1172
10
                                  ? ValueFactory.getMinValue(ResultType)
1173
37
                                  : ValueFactory.getValue(Zero);
1174
47
1175
47
    return {RangeFactory, Min, Max};
1176
47
  }
1177
36.1k
1178
  // Otherwise, let's check if at least one of the operands is positive.
1179
36.1k
  if (IsLHSPositiveOrZero || 
IsRHSPositiveOrZero36.1k
) {
1180
    // This makes result definitely positive.
1181
    //
1182
    // We can also reason about a maximal value by finding the maximal
1183
    // value of the positive operand.
1184
36.0k
    const llvm::APSInt &Max = IsLHSPositiveOrZero ? 
LHS.To()16
: RHS.To();
1185
36.0k
1186
    // The minimal value on the other hand is much harder to reason about.
1187
    // The only thing we know for sure is that the result is positive.
1188
36.0k
    return {RangeFactory, ValueFactory.getValue(Zero),
1189
36.0k
            ValueFactory.getValue(Max)};
1190
36.0k
  }
1191
137
1192
  // Nothing much else to do here.
1193
137
  return infer(T);
1194
137
}
1195
1196
template <>
1197
RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS,
1198
                                                            Range RHS,
1199
214
                                                            QualType T) {
1200
214
  llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue();
1201
214
1202
214
  Range ConservativeRange = getSymmetricalRange(RHS, T);
1203
214
1204
214
  llvm::APSInt Max = ConservativeRange.To();
1205
214
  llvm::APSInt Min = ConservativeRange.From();
1206
214
1207
214
  if (Max == Zero) {
1208
    // It's an undefined behaviour to divide by 0 and it seems like we know
1209
    // for sure that RHS is 0.  Let's say that the resulting range is
1210
    // simply infeasible for that matter.
1211
0
    return RangeFactory.getEmptySet();
1212
0
  }
1213
214
1214
  // At this point, our conservative range is closed.  The result, however,
1215
  // couldn't be greater than the RHS' maximal absolute value.  Because of
1216
  // this reason, we turn the range into open (or half-open in case of
1217
  // unsigned integers).
1218
  //
1219
  // While we operate on integer values, an open interval (a, b) can be easily
1220
  // represented by the closed interval [a + 1, b - 1].  And this is exactly
1221
  // what we do next.
1222
  //
1223
  // If we are dealing with unsigned case, we shouldn't move the lower bound.
1224
214
  if (Min.isSigned()) {
1225
166
    ++Min;
1226
166
  }
1227
214
  --Max;
1228
214
1229
214
  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1230
214
  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1231
214
1232
  // Remainder operator results with negative operands is implementation
1233
  // defined.  Positive cases are much easier to reason about though.
1234
214
  if (IsLHSPositiveOrZero && 
IsRHSPositiveOrZero132
) {
1235
    // If maximal value of LHS is less than maximal value of RHS,
1236
    // the result won't get greater than LHS.To().
1237
98
    Max = std::min(LHS.To(), Max);
1238
    // We want to check if it is a situation similar to the following:
1239
    //
1240
    // <------------|---[  LHS  ]--------[  RHS  ]----->
1241
    //  -INF        0                              +INF
1242
    //
1243
    // In this situation, we can conclude that (LHS / RHS) == 0 and
1244
    // (LHS % RHS) == LHS.
1245
84
    Min = LHS.To() < RHS.From() ? 
LHS.From()14
: Zero;
1246
98
  }
1247
214
1248
  // Nevertheless, the symmetrical range for RHS is a conservative estimate
1249
  // for any sign of either LHS, or RHS.
1250
214
  return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)};
1251
214
}
1252
1253
//===----------------------------------------------------------------------===//
1254
//                  Constraint manager implementation details
1255
//===----------------------------------------------------------------------===//
1256
1257
class RangeConstraintManager : public RangedConstraintManager {
1258
public:
1259
  RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
1260
13.6k
      : RangedConstraintManager(EE, SVB) {}
1261
1262
  //===------------------------------------------------------------------===//
1263
  // Implementation for interface from ConstraintManager.
1264
  //===------------------------------------------------------------------===//
1265
1266
  bool haveEqualConstraints(ProgramStateRef S1,
1267
8.42k
                            ProgramStateRef S2) const override {
1268
    // NOTE: ClassMembers are as simple as back pointers for ClassMap,
1269
    //       so comparing constraint ranges and class maps should be
1270
    //       sufficient.
1271
8.42k
    return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() &&
1272
3.80k
           S1->get<ClassMap>() == S2->get<ClassMap>();
1273
8.42k
  }
1274
1275
  bool canReasonAbout(SVal X) const override;
1276
1277
  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
1278
1279
  const llvm::APSInt *getSymVal(ProgramStateRef State,
1280
                                SymbolRef Sym) const override;
1281
1282
  ProgramStateRef removeDeadBindings(ProgramStateRef State,
1283
                                     SymbolReaper &SymReaper) override;
1284
1285
  void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
1286
                 unsigned int Space = 0, bool IsDot = false) const override;
1287
1288
  //===------------------------------------------------------------------===//
1289
  // Implementation for interface from RangedConstraintManager.
1290
  //===------------------------------------------------------------------===//
1291
1292
  ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
1293
                              const llvm::APSInt &V,
1294
                              const llvm::APSInt &Adjustment) override;
1295
1296
  ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
1297
                              const llvm::APSInt &V,
1298
                              const llvm::APSInt &Adjustment) override;
1299
1300
  ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
1301
                              const llvm::APSInt &V,
1302
                              const llvm::APSInt &Adjustment) override;
1303
1304
  ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
1305
                              const llvm::APSInt &V,
1306
                              const llvm::APSInt &Adjustment) override;
1307
1308
  ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
1309
                              const llvm::APSInt &V,
1310
                              const llvm::APSInt &Adjustment) override;
1311
1312
  ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
1313
                              const llvm::APSInt &V,
1314
                              const llvm::APSInt &Adjustment) override;
1315
1316
  ProgramStateRef assumeSymWithinInclusiveRange(
1317
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
1318
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
1319
1320
  ProgramStateRef assumeSymOutsideInclusiveRange(
1321
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
1322
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
1323
1324
private:
1325
  RangeSet::Factory F;
1326
1327
  RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
1328
  RangeSet getRange(ProgramStateRef State, EquivalenceClass Class);
1329
1330
  RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
1331
                         const llvm::APSInt &Int,
1332
                         const llvm::APSInt &Adjustment);
1333
  RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
1334
                         const llvm::APSInt &Int,
1335
                         const llvm::APSInt &Adjustment);
1336
  RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
1337
                         const llvm::APSInt &Int,
1338
                         const llvm::APSInt &Adjustment);
1339
  RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
1340
                         const llvm::APSInt &Int,
1341
                         const llvm::APSInt &Adjustment);
1342
  RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
1343
                         const llvm::APSInt &Int,
1344
                         const llvm::APSInt &Adjustment);
1345
1346
  //===------------------------------------------------------------------===//
1347
  // Equality tracking implementation
1348
  //===------------------------------------------------------------------===//
1349
1350
  ProgramStateRef trackEQ(ProgramStateRef State, SymbolRef Sym,
1351
                          const llvm::APSInt &Int,
1352
38.1k
                          const llvm::APSInt &Adjustment) {
1353
38.1k
    if (auto Equality = EqualityInfo::extract(Sym, Int, Adjustment)) {
1354
      // Extract function assumes that we gave it Sym + Adjustment != Int,
1355
      // so the result should be opposite.
1356
648
      Equality->invert();
1357
648
      return track(State, *Equality);
1358
648
    }
1359
37.5k
1360
37.5k
    return State;
1361
37.5k
  }
1362
1363
  ProgramStateRef trackNE(ProgramStateRef State, SymbolRef Sym,
1364
                          const llvm::APSInt &Int,
1365
83.2k
                          const llvm::APSInt &Adjustment) {
1366
83.2k
    if (auto Equality = EqualityInfo::extract(Sym, Int, Adjustment)) {
1367
850
      return track(State, *Equality);
1368
850
    }
1369
82.4k
1370
82.4k
    return State;
1371
82.4k
  }
1372
1373
1.49k
  ProgramStateRef track(ProgramStateRef State, EqualityInfo ToTrack) {
1374
1.49k
    if (ToTrack.IsEquality) {
1375
715
      return trackEquality(State, ToTrack.Left, ToTrack.Right);
1376
715
    }
1377
783
    return trackDisequality(State, ToTrack.Left, ToTrack.Right);
1378
783
  }
1379
1380
  ProgramStateRef trackDisequality(ProgramStateRef State, SymbolRef LHS,
1381
783
                                   SymbolRef RHS) {
1382
783
    return EquivalenceClass::markDisequal(getBasicVals(), F, State, LHS, RHS);
1383
783
  }
1384
1385
  ProgramStateRef trackEquality(ProgramStateRef State, SymbolRef LHS,
1386
715
                                SymbolRef RHS) {
1387
715
    return EquivalenceClass::merge(getBasicVals(), F, State, LHS, RHS);
1388
715
  }
1389
1390
  LLVM_NODISCARD inline ProgramStateRef setConstraint(ProgramStateRef State,
1391
                                                      EquivalenceClass Class,
1392
138k
                                                      RangeSet Constraint) {
1393
138k
    ConstraintRangeTy Constraints = State->get<ConstraintRange>();
1394
138k
    ConstraintRangeTy::Factory &CF = State->get_context<ConstraintRange>();
1395
138k
1396
    // Add new constraint.
1397
138k
    Constraints = CF.add(Constraints, Class, Constraint);
1398
138k
1399
    // There is a chance that we might need to update constraints for the
1400
    // classes that are known to be disequal to Class.
1401
    //
1402
    // In order for this to be even possible, the new constraint should
1403
    // be simply a constant because we can't reason about range disequalities.
1404
138k
    if (const llvm::APSInt *Point = Constraint.getConcreteValue())
1405
40.9k
      for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) {
1406
36
        RangeSet UpdatedConstraint =
1407
36
            getRange(State, DisequalClass).Delete(getBasicVals(), F, *Point);
1408
36
        Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint);
1409
36
      }
1410
138k
1411
138k
    return State->set<ConstraintRange>(Constraints);
1412
138k
  }
1413
1414
  LLVM_NODISCARD inline ProgramStateRef
1415
138k
  setConstraint(ProgramStateRef State, SymbolRef Sym, RangeSet Constraint) {
1416
138k
    return setConstraint(State, EquivalenceClass::find(State, Sym), Constraint);
1417
138k
  }
1418
};
1419
1420
} // end anonymous namespace
1421
1422
std::unique_ptr<ConstraintManager>
1423
ento::CreateRangeConstraintManager(ProgramStateManager &StMgr,
1424
13.6k
                                   ExprEngine *Eng) {
1425
13.6k
  return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
1426
13.6k
}
1427
1428
0
ConstraintMap ento::getConstraintMap(ProgramStateRef State) {
1429
0
  ConstraintMap::Factory &F = State->get_context<ConstraintMap>();
1430
0
  ConstraintMap Result = F.getEmptyMap();
1431
0
1432
0
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
1433
0
  for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
1434
0
    EquivalenceClass Class = ClassConstraint.first;
1435
0
    SymbolSet ClassMembers = Class.getClassMembers(State);
1436
0
    assert(!ClassMembers.isEmpty() &&
1437
0
           "Class must always have at least one member!");
1438
0
1439
0
    SymbolRef Representative = *ClassMembers.begin();
1440
0
    Result = F.add(Result, Representative, ClassConstraint.second);
1441
0
  }
1442
0
1443
0
  return Result;
1444
0
}
1445
1446
//===----------------------------------------------------------------------===//
1447
//                     EqualityClass implementation details
1448
//===----------------------------------------------------------------------===//
1449
1450
inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State,
1451
703k
                                               SymbolRef Sym) {
1452
  // We store far from all Symbol -> Class mappings
1453
703k
  if (const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))
1454
2.15k
    return *NontrivialClass;
1455
701k
1456
  // This is a trivial class of Sym.
1457
701k
  return Sym;
1458
701k
}
1459
1460
inline ProgramStateRef EquivalenceClass::merge(BasicValueFactory &BV,
1461
                                               RangeSet::Factory &F,
1462
                                               ProgramStateRef State,
1463
                                               SymbolRef First,
1464
715
                                               SymbolRef Second) {
1465
715
  EquivalenceClass FirstClass = find(State, First);
1466
715
  EquivalenceClass SecondClass = find(State, Second);
1467
715
1468
715
  return FirstClass.merge(BV, F, State, SecondClass);
1469
715
}
1470
1471
inline ProgramStateRef EquivalenceClass::merge(BasicValueFactory &BV,
1472
                                               RangeSet::Factory &F,
1473
                                               ProgramStateRef State,
1474
715
                                               EquivalenceClass Other) {
1475
  // It is already the same class.
1476
715
  if (*this == Other)
1477
38
    return State;
1478
677
1479
  // FIXME: As of now, we support only equivalence classes of the same type.
1480
  //        This limitation is connected to the lack of explicit casts in
1481
  //        our symbolic expression model.
1482
  //
1483
  //        That means that for `int x` and `char y` we don't distinguish
1484
  //        between these two very different cases:
1485
  //          * `x == y`
1486
  //          * `(char)x == y`
1487
  //
1488
  //        The moment we introduce symbolic casts, this restriction can be
1489
  //        lifted.
1490
677
  if (getType() != Other.getType())
1491
168
    return State;
1492
509
1493
509
  SymbolSet Members = getClassMembers(State);
1494
509
  SymbolSet OtherMembers = Other.getClassMembers(State);
1495
509
1496
  // We estimate the size of the class by the height of tree containing
1497
  // its members.  Merging is not a trivial operation, so it's easier to
1498
  // merge the smaller class into the bigger one.
1499
509
  if (Members.getHeight() >= OtherMembers.getHeight()) {
1500
508
    return mergeImpl(BV, F, State, Members, Other, OtherMembers);
1501
1
  } else {
1502
1
    return Other.mergeImpl(BV, F, State, OtherMembers, *this, Members);
1503
1
  }
1504
509
}
1505
1506
inline ProgramStateRef
1507
EquivalenceClass::mergeImpl(BasicValueFactory &ValueFactory,
1508
                            RangeSet::Factory &RangeFactory,
1509
                            ProgramStateRef State, SymbolSet MyMembers,
1510
509
                            EquivalenceClass Other, SymbolSet OtherMembers) {
1511
  // Essentially what we try to recreate here is some kind of union-find
1512
  // data structure.  It does have certain limitations due to persistence
1513
  // and the need to remove elements from classes.
1514
  //
1515
  // In this setting, EquialityClass object is the representative of the class
1516
  // or the parent element.  ClassMap is a mapping of class members to their
1517
  // parent. Unlike the union-find structure, they all point directly to the
1518
  // class representative because we don't have an opportunity to actually do
1519
  // path compression when dealing with immutability.  This means that we
1520
  // compress paths every time we do merges.  It also means that we lose
1521
  // the main amortized complexity benefit from the original data structure.
1522
509
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
1523
509
  ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
1524
509
1525
  // 1. If the merged classes have any constraints associated with them, we
1526
  //    need to transfer them to the class we have left.
1527
  //
1528
  // Intersection here makes perfect sense because both of these constraints
1529
  // must hold for the whole new class.
1530
509
  if (Optional<RangeSet> NewClassConstraint =
1531
207
          intersect(ValueFactory, RangeFactory, getConstraint(State, *this),
1532
207
                    getConstraint(State, Other))) {
1533
    // NOTE: Essentially, NewClassConstraint should NEVER be infeasible because
1534
    //       range inferrer shouldn't generate ranges incompatible with
1535
    //       equivalence classes. However, at the moment, due to imperfections
1536
    //       in the solver, it is possible and the merge function can also
1537
    //       return infeasible states aka null states.
1538
207
    if (NewClassConstraint->isEmpty())
1539
      // Infeasible state
1540
3
      return nullptr;
1541
204
1542
    // No need in tracking constraints of a now-dissolved class.
1543
204
    Constraints = CRF.remove(Constraints, Other);
1544
    // Assign new constraints for this class.
1545
204
    Constraints = CRF.add(Constraints, *this, *NewClassConstraint);
1546
204
1547
204
    State = State->set<ConstraintRange>(Constraints);
1548
204
  }
1549
509
1550
  // 2. Get ALL equivalence-related maps
1551
506
  ClassMapTy Classes = State->get<ClassMap>();
1552
506
  ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
1553
506
1554
506
  ClassMembersTy Members = State->get<ClassMembers>();
1555
506
  ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();
1556
506
1557
506
  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
1558
506
  DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>();
1559
506
1560
506
  ClassSet::Factory &CF = State->get_context<ClassSet>();
1561
506
  SymbolSet::Factory &F = getMembersFactory(State);
1562
506
1563
  // 2. Merge members of the Other class into the current class.
1564
506
  SymbolSet NewClassMembers = MyMembers;
1565
507
  for (SymbolRef Sym : OtherMembers) {
1566
507
    NewClassMembers = F.add(NewClassMembers, Sym);
1567
    // *this is now the class for all these new symbols.
1568
507
    Classes = CMF.add(Classes, Sym, *this);
1569
507
  }
1570
506
1571
  // 3. Adjust member mapping.
1572
  //
1573
  // No need in tracking members of a now-dissolved class.
1574
506
  Members = MF.remove(Members, Other);
1575
  // Now only the current class is mapped to all the symbols.
1576
506
  Members = MF.add(Members, *this, NewClassMembers);
1577
506
1578
  // 4. Update disequality relations
1579
506
  ClassSet DisequalToOther = Other.getDisequalClasses(DisequalityInfo, CF);
1580
506
  if (!DisequalToOther.isEmpty()) {
1581
19
    ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo, CF);
1582
19
    DisequalityInfo = DF.remove(DisequalityInfo, Other);
1583
19
1584
37
    for (EquivalenceClass DisequalClass : DisequalToOther) {
1585
37
      DisequalToThis = CF.add(DisequalToThis, DisequalClass);
1586
37
1587
      // Disequality is a symmetric relation meaning that if
1588
      // DisequalToOther not null then the set for DisequalClass is not
1589
      // empty and has at least Other.
1590
37
      ClassSet OriginalSetLinkedToOther =
1591
37
          *DisequalityInfo.lookup(DisequalClass);
1592
37
1593
      // Other will be eliminated and we should replace it with the bigger
1594
      // united class.
1595
37
      ClassSet NewSet = CF.remove(OriginalSetLinkedToOther, Other);
1596
37
      NewSet = CF.add(NewSet, *this);
1597
37
1598
37
      DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);
1599
37
    }
1600
19
1601
19
    DisequalityInfo = DF.add(DisequalityInfo, *this, DisequalToThis);
1602
19
    State = State->set<DisequalityMap>(DisequalityInfo);
1603
19
  }
1604
506
1605
  // 5. Update the state
1606
506
  State = State->set<ClassMap>(Classes);
1607
506
  State = State->set<ClassMembers>(Members);
1608
506
1609
506
  return State;
1610
509
}
1611
1612
inline SymbolSet::Factory &
1613
1.56k
EquivalenceClass::getMembersFactory(ProgramStateRef State) {
1614
1.56k
  return State->get_context<SymbolSet>();
1615
1.56k
}
1616
1617
1.06k
SymbolSet EquivalenceClass::getClassMembers(ProgramStateRef State) {
1618
1.06k
  if (const SymbolSet *Members = State->get<ClassMembers>(*this))
1619
6
    return *Members;
1620
1.05k
1621
  // This class is trivial, so we need to construct a set
1622
  // with just that one symbol from the class.
1623
1.05k
  SymbolSet::Factory &F = getMembersFactory(State);
1624
1.05k
  return F.add(F.getEmptySet(), getRepresentativeSymbol());
1625
1.05k
}
1626
1627
1.87M
bool EquivalenceClass::isTrivial(ProgramStateRef State) {
1628
1.87M
  return State->get<ClassMembers>(*this) == nullptr;
1629
1.87M
}
1630
1631
bool EquivalenceClass::isTriviallyDead(ProgramStateRef State,
1632
1.87M
                                       SymbolReaper &Reaper) {
1633
1.87M
  return isTrivial(State) && 
Reaper.isDead(getRepresentativeSymbol())1.87M
;
1634
1.87M
}
1635
1636
inline ProgramStateRef EquivalenceClass::markDisequal(BasicValueFactory &VF,
1637
                                                      RangeSet::Factory &RF,
1638
                                                      ProgramStateRef State,
1639
                                                      SymbolRef First,
1640
783
                                                      SymbolRef Second) {
1641
783
  return markDisequal(VF, RF, State, find(State, First), find(State, Second));
1642
783
}
1643
1644
inline ProgramStateRef EquivalenceClass::markDisequal(BasicValueFactory &VF,
1645
                                                      RangeSet::Factory &RF,
1646
                                                      ProgramStateRef State,
1647
                                                      EquivalenceClass First,
1648
783
                                                      EquivalenceClass Second) {
1649
783
  return First.markDisequal(VF, RF, State, Second);
1650
783
}
1651
1652
inline ProgramStateRef
1653
EquivalenceClass::markDisequal(BasicValueFactory &VF, RangeSet::Factory &RF,
1654
                               ProgramStateRef State,
1655
783
                               EquivalenceClass Other) const {
1656
  // If we know that two classes are equal, we can only produce an infeasible
1657
  // state.
1658
783
  if (*this == Other) {
1659
0
    return nullptr;
1660
0
  }
1661
783
1662
783
  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
1663
783
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
1664
783
1665
  // Disequality is a symmetric relation, so if we mark A as disequal to B,
1666
  // we should also mark B as disequalt to A.
1667
783
  addToDisequalityInfo(DisequalityInfo, Constraints, VF, RF, State, *this,
1668
783
                       Other);
1669
783
  addToDisequalityInfo(DisequalityInfo, Constraints, VF, RF, State, Other,
1670
783
                       *this);
1671
783
1672
783
  State = State->set<DisequalityMap>(DisequalityInfo);
1673
783
  State = State->set<ConstraintRange>(Constraints);
1674
783
1675
783
  return State;
1676
783
}
1677
1678
inline void EquivalenceClass::addToDisequalityInfo(
1679
    DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
1680
    BasicValueFactory &VF, RangeSet::Factory &RF, ProgramStateRef State,
1681
1.56k
    EquivalenceClass First, EquivalenceClass Second) {
1682
1.56k
1683
  // 1. Get all of the required factories.
1684
1.56k
  DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>();
1685
1.56k
  ClassSet::Factory &CF = State->get_context<ClassSet>();
1686
1.56k
  ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
1687
1.56k
1688
  // 2. Add Second to the set of classes disequal to First.
1689
1.56k
  const ClassSet *CurrentSet = Info.lookup(First);
1690
1.38k
  ClassSet NewSet = CurrentSet ? 
*CurrentSet183
: CF.getEmptySet();
1691
1.56k
  NewSet = CF.add(NewSet, Second);
1692
1.56k
1693
1.56k
  Info = F.add(Info, First, NewSet);
1694
1.56k
1695
  // 3. If Second is known to be a constant, we can delete this point
1696
  //    from the constraint asociated with First.
1697
  //
1698
  //    So, if Second == 10, it means that First != 10.
1699
  //    At the same time, the same logic does not apply to ranges.
1700
1.56k
  if (const RangeSet *SecondConstraint = Constraints.lookup(Second))
1701
699
    if (const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {
1702
0
1703
0
      RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
1704
0
          VF, RF, State, First.getRepresentativeSymbol());
1705
0
1706
0
      FirstConstraint = FirstConstraint.Delete(VF, RF, *Point);
1707
0
      Constraints = CRF.add(Constraints, First, FirstConstraint);
1708
0
    }
1709
1.56k
}
1710
1711
inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State,
1712
                                                 SymbolRef FirstSym,
1713
3.92k
                                                 SymbolRef SecondSym) {
1714
3.92k
  EquivalenceClass First = find(State, FirstSym);
1715
3.92k
  EquivalenceClass Second = find(State, SecondSym);
1716
3.92k
1717
  // The same equivalence class => symbols are equal.
1718
3.92k
  if (First == Second)
1719
244
    return true;
1720
3.68k
1721
  // Let's check if we know anything about these two classes being not equal to
1722
  // each other.
1723
3.68k
  ClassSet DisequalToFirst = First.getDisequalClasses(State);
1724
3.68k
  if (DisequalToFirst.contains(Second))
1725
1.00k
    return false;
1726
2.68k
1727
  // It is not clear.
1728
2.68k
  return llvm::None;
1729
2.68k
}
1730
1731
inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State,
1732
0
                                                     SymbolRef Sym) {
1733
0
  return find(State, Sym).getDisequalClasses(State);
1734
0
}
1735
1736
inline ClassSet
1737
44.6k
EquivalenceClass::getDisequalClasses(ProgramStateRef State) const {
1738
44.6k
  return getDisequalClasses(State->get<DisequalityMap>(),
1739
44.6k
                            State->get_context<ClassSet>());
1740
44.6k
}
1741
1742
inline ClassSet
1743
EquivalenceClass::getDisequalClasses(DisequalityMapTy Map,
1744
98.1k
                                     ClassSet::Factory &Factory) const {
1745
98.1k
  if (const ClassSet *DisequalClasses = Map.lookup(*this))
1746
1.95k
    return *DisequalClasses;
1747
96.2k
1748
96.2k
  return Factory.getEmptySet();
1749
96.2k
}
1750
1751
360k
bool EquivalenceClass::isClassDataConsistent(ProgramStateRef State) {
1752
360k
  ClassMembersTy Members = State->get<ClassMembers>();
1753
360k
1754
3.38k
  for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) {
1755
4.56k
    for (SymbolRef Member : ClassMembersPair.second) {
1756
      // Every member of the class should have a mapping back to the class.
1757
4.56k
      if (find(State, Member) == ClassMembersPair.first) {
1758
4.56k
        continue;
1759
4.56k
      }
1760
0
1761
0
      return false;
1762
0
    }
1763
3.38k
  }
1764
360k
1765
360k
  DisequalityMapTy Disequalities = State->get<DisequalityMap>();
1766
21.4k
  for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) {
1767
21.4k
    EquivalenceClass Class = DisequalityInfo.first;
1768
21.4k
    ClassSet DisequalClasses = DisequalityInfo.second;
1769
21.4k
1770
    // There is no use in keeping empty sets in the map.
1771
21.4k
    if (DisequalClasses.isEmpty())
1772
0
      return false;
1773
21.4k
1774
    // Disequality is symmetrical, i.e. for every Class A and B that A != B,
1775
    // B != A should also be true.
1776
23.4k
    
for (EquivalenceClass DisequalClass : DisequalClasses)21.4k
{
1777
23.4k
      const ClassSet *DisequalToDisequalClasses =
1778
23.4k
          Disequalities.lookup(DisequalClass);
1779
23.4k
1780
      // It should be a set of at least one element: Class
1781
23.4k
      if (!DisequalToDisequalClasses ||
1782
23.4k
          !DisequalToDisequalClasses->contains(Class))
1783
0
        return false;
1784
23.4k
    }
1785
21.4k
  }
1786
360k
1787
360k
  return true;
1788
360k
}
1789
1790
//===----------------------------------------------------------------------===//
1791
//                    RangeConstraintManager implementation
1792
//===----------------------------------------------------------------------===//
1793
1794
739k
bool RangeConstraintManager::canReasonAbout(SVal X) const {
1795
739k
  Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
1796
739k
  if (SymVal && 
SymVal->isExpression()193k
) {
1797
187k
    const SymExpr *SE = SymVal->getSymbol();
1798
187k
1799
187k
    if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
1800
183k
      switch (SIE->getOpcode()) {
1801
      // We don't reason yet about bitwise-constraints on symbolic values.
1802
33
      case BO_And:
1803
33
      case BO_Or:
1804
33
      case BO_Xor:
1805
33
        return false;
1806
      // We don't reason yet about these arithmetic constraints on
1807
      // symbolic values.
1808
28
      case BO_Mul:
1809
28
      case BO_Div:
1810
28
      case BO_Rem:
1811
28
      case BO_Shl:
1812
28
      case BO_Shr:
1813
28
        return false;
1814
      // All other cases.
1815
183k
      default:
1816
183k
        return true;
1817
3.89k
      }
1818
3.89k
    }
1819
3.89k
1820
3.89k
    if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
1821
      // FIXME: Handle <=> here.
1822
3.88k
      if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
1823
3.84k
          
BinaryOperator::isRelationalOp(SSE->getOpcode())2.56k
) {
1824
        // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
1825
        // We've recently started producing Loc <> NonLoc comparisons (that
1826
        // result from casts of one of the operands between eg. intptr_t and
1827
        // void *), but we can't reason about them yet.
1828
3.84k
        if (Loc::isLocType(SSE->getLHS()->getType())) {
1829
924
          return Loc::isLocType(SSE->getRHS()->getType());
1830
924
        }
1831
2.97k
      }
1832
3.88k
    }
1833
2.97k
1834
2.97k
    return false;
1835
2.97k
  }
1836
551k
1837
551k
  return true;
1838
551k
}
1839
1840
ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
1841
57.1k
                                                    SymbolRef Sym) {
1842
57.1k
  const RangeSet *Ranges = getConstraint(State, Sym);
1843
57.1k
1844
  // If we don't have any information about this symbol, it's underconstrained.
1845
57.1k
  if (!Ranges)
1846
31.1k
    return ConditionTruthVal();
1847
26.0k
1848
  // If we have a concrete value, see if it's zero.
1849
26.0k
  if (const llvm::APSInt *Value = Ranges->getConcreteValue())
1850
14.2k
    return *Value == 0;
1851
11.8k
1852
11.8k
  BasicValueFactory &BV = getBasicVals();
1853
11.8k
  APSIntType IntType = BV.getAPSIntType(Sym->getType());
1854
11.8k
  llvm::APSInt Zero = IntType.getZeroValue();
1855
11.8k
1856
  // Check if zero is in the set of possible values.
1857
11.8k
  if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
1858
11.8k
    return false;
1859
4
1860
  // Zero is a possible value, but it is not the /only/ possible value.
1861
4
  return ConditionTruthVal();
1862
4
}
1863
1864
const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
1865
214k
                                                      SymbolRef Sym) const {
1866
214k
  const RangeSet *T = getConstraint(St, Sym);
1867
165k
  return T ? 
T->getConcreteValue()49.1k
: nullptr;
1868
214k
}
1869
1870
//===----------------------------------------------------------------------===//
1871
//                Remove dead symbols from existing constraints
1872
//===----------------------------------------------------------------------===//
1873
1874
/// Scan all symbols referenced by the constraints. If the symbol is not alive
1875
/// as marked in LSymbols, mark it as dead in DSymbols.
1876
ProgramStateRef
1877
RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
1878
360k
                                           SymbolReaper &SymReaper) {
1879
360k
  ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
1880
360k
  ClassMembersTy NewClassMembersMap = ClassMembersMap;
1881
360k
  ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
1882
360k
  SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>();
1883
360k
1884
360k
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
1885
360k
  ConstraintRangeTy NewConstraints = Constraints;
1886
360k
  ConstraintRangeTy::Factory &ConstraintFactory =
1887
360k
      State->get_context<ConstraintRange>();
1888
360k
1889
360k
  ClassMapTy Map = State->get<ClassMap>();
1890
360k
  ClassMapTy NewMap = Map;
1891
360k
  ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();
1892
360k
1893
360k
  DisequalityMapTy Disequalities = State->get<DisequalityMap>();
1894
360k
  DisequalityMapTy::Factory &DisequalityFactory =
1895
360k
      State->get_context<DisequalityMap>();
1896
360k
  ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();
1897
360k
1898
360k
  bool ClassMapChanged = false;
1899
360k
  bool MembersMapChanged = false;
1900
360k
  bool ConstraintMapChanged = false;
1901
360k
  bool DisequalitiesChanged = false;
1902
360k
1903
52.6k
  auto removeDeadClass = [&](EquivalenceClass Class) {
1904
    // Remove associated constraint ranges.
1905
52.6k
    Constraints = ConstraintFactory.remove(Constraints, Class);
1906
52.6k
    ConstraintMapChanged = true;
1907
52.6k
1908
    // Update disequality information to not hold any information on the
1909
    // removed class.
1910
52.6k
    ClassSet DisequalClasses =
1911
52.6k
        Class.getDisequalClasses(Disequalities, ClassSetFactory);
1912
52.6k
    if (!DisequalClasses.isEmpty()) {
1913
361
      for (EquivalenceClass DisequalClass : DisequalClasses) {
1914
361
        ClassSet DisequalToDisequalSet =
1915
361
            DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory);
1916
        // DisequalToDisequalSet is guaranteed to be non-empty for consistent
1917
        // disequality info.
1918
361
        assert(!DisequalToDisequalSet.isEmpty());
1919
361
        ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet, Class);
1920
361
1921
        // No need in keeping an empty set.
1922
361
        if (NewSet.isEmpty()) {
1923
361
          Disequalities =
1924
361
              DisequalityFactory.remove(Disequalities, DisequalClass);
1925
0
        } else {
1926
0
          Disequalities =
1927
0
              DisequalityFactory.add(Disequalities, DisequalClass, NewSet);
1928
0
        }
1929
361
      }
1930
      // Remove the data for the class
1931
343
      Disequalities = DisequalityFactory.remove(Disequalities, Class);
1932
343
      DisequalitiesChanged = true;
1933
343
    }
1934
52.6k
  };
1935
360k
1936
  // 1. Let's see if dead symbols are trivial and have associated constraints.
1937
360k
  for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :
1938
1.87M
       Constraints) {
1939
1.87M
    EquivalenceClass Class = ClassConstraintPair.first;
1940
1.87M
    if (Class.isTriviallyDead(State, SymReaper)) {
1941
      // If this class is trivial, we can remove its constraints right away.
1942
52.3k
      removeDeadClass(Class);
1943
52.3k
    }
1944
1.87M
  }
1945
360k
1946
  // 2. We don't need to track classes for dead symbols.
1947
1.56k
  for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {
1948
1.56k
    SymbolRef Sym = SymbolClassPair.first;
1949
1.56k
1950
1.56k
    if (SymReaper.isDead(Sym)) {
1951
276
      ClassMapChanged = true;
1952
276
      NewMap = ClassFactory.remove(NewMap, Sym);
1953
276
    }
1954
1.56k
  }
1955
360k
1956
  // 3. Remove dead members from classes and remove dead non-trivial classes
1957
  //    and their constraints.
1958
360k
  for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :
1959
3.65k
       ClassMembersMap) {
1960
3.65k
    EquivalenceClass Class = ClassMembersPair.first;
1961
3.65k
    SymbolSet LiveMembers = ClassMembersPair.second;
1962
3.65k
    bool MembersChanged = false;
1963
3.65k
1964
5.13k
    for (SymbolRef Member : ClassMembersPair.second) {
1965
5.13k
      if (SymReaper.isDead(Member)) {
1966
571
        MembersChanged = true;
1967
571
        LiveMembers = SetFactory.remove(LiveMembers, Member);
1968
571
      }
1969
5.13k
    }
1970
3.65k
1971
    // Check if the class changed.
1972
3.65k
    if (!MembersChanged)
1973
3.24k
      continue;
1974
411
1975
411
    MembersMapChanged = true;
1976
411
1977
411
    if (LiveMembers.isEmpty()) {
1978
      // The class is dead now, we need to wipe it out of the members map...
1979
269
      NewClassMembersMap = EMFactory.remove(NewClassMembersMap, Class);
1980
269
1981
      // ...and remove all of its constraints.
1982
269
      removeDeadClass(Class);
1983
142
    } else {
1984
      // We need to change the members associated with the class.
1985
142
      NewClassMembersMap =
1986
142
          EMFactory.add(NewClassMembersMap, Class, LiveMembers);
1987
142
    }
1988
411
  }
1989
360k
1990
  // 4. Update the state with new maps.
1991
  //
1992
  // Here we try to be humble and update a map only if it really changed.
1993
360k
  if (ClassMapChanged)
1994
269
    State = State->set<ClassMap>(NewMap);
1995
360k
1996
360k
  if (MembersMapChanged)
1997
403
    State = State->set<ClassMembers>(NewClassMembersMap);
1998
360k
1999
360k
  if (ConstraintMapChanged)
2000
29.1k
    State = State->set<ConstraintRange>(Constraints);
2001
360k
2002
360k
  if (DisequalitiesChanged)
2003
301
    State = State->set<DisequalityMap>(Disequalities);
2004
360k
2005
360k
  assert(EquivalenceClass::isClassDataConsistent(State));
2006
360k
2007
360k
  return State;
2008
360k
}
2009
2010
RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
2011
194k
                                          SymbolRef Sym) {
2012
194k
  return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Sym);
2013
194k
}
2014
2015
RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
2016
36
                                          EquivalenceClass Class) {
2017
36
  return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Class);
2018
36
}
2019
2020
//===------------------------------------------------------------------------===
2021
// assumeSymX methods: protected interface for RangeConstraintManager.
2022
//===------------------------------------------------------------------------===/
2023
2024
// The syntax for ranges below is mathematical, using [x, y] for closed ranges
2025
// and (x, y) for open ranges. These ranges are modular, corresponding with
2026
// a common treatment of C integer overflow. This means that these methods
2027
// do not have to worry about overflow; RangeSet::Intersect can handle such a
2028
// "wraparound" range.
2029
// As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
2030
// UINT_MAX, 0, 1, and 2.
2031
2032
ProgramStateRef
2033
RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
2034
                                    const llvm::APSInt &Int,
2035
83.8k
                                    const llvm::APSInt &Adjustment) {
2036
  // Before we do any real work, see if the value can even show up.
2037
83.8k
  APSIntType AdjustmentType(Adjustment);
2038
83.8k
  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
2039
3
    return St;
2040
83.8k
2041
83.8k
  llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
2042
83.8k
2043
83.8k
  RangeSet New = getRange(St, Sym).Delete(getBasicVals(), F, Point);
2044
83.8k
2045
83.8k
  if (New.isEmpty())
2046
    // this is infeasible assumption
2047
575
    return nullptr;
2048
83.2k
2049
83.2k
  ProgramStateRef NewState = setConstraint(St, Sym, New);
2050
83.2k
  return trackNE(NewState, Sym, Int, Adjustment);
2051
83.2k
}
2052
2053
ProgramStateRef
2054
RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
2055
                                    const llvm::APSInt &Int,
2056
82.0k
                                    const llvm::APSInt &Adjustment) {
2057
  // Before we do any real work, see if the value can even show up.
2058
82.0k
  APSIntType AdjustmentType(Adjustment);
2059
82.0k
  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
2060
3
    return nullptr;
2061
82.0k
2062
  // [Int-Adjustment, Int-Adjustment]
2063
82.0k
  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
2064
82.0k
  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
2065
82.0k
2066
82.0k
  if (New.isEmpty())
2067
    // this is infeasible assumption
2068
43.9k
    return nullptr;
2069
38.1k
2070
38.1k
  ProgramStateRef NewState = setConstraint(St, Sym, New);
2071
38.1k
  return trackEQ(NewState, Sym, Int, Adjustment);
2072
38.1k
}
2073
2074
RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
2075
                                               SymbolRef Sym,
2076
                                               const llvm::APSInt &Int,
2077
8.55k
                                               const llvm::APSInt &Adjustment) {
2078
  // Before we do any real work, see if the value can even show up.
2079
8.55k
  APSIntType AdjustmentType(Adjustment);
2080
8.55k
  switch (AdjustmentType.testInRange(Int, true)) {
2081
2
  case APSIntType::RTR_Below:
2082
2
    return F.getEmptySet();
2083
8.54k
  case APSIntType::RTR_Within:
2084
8.54k
    break;
2085
2
  case APSIntType::RTR_Above:
2086
2
    return getRange(St, Sym);
2087
8.54k
  }
2088
8.54k
2089
  // Special case for Int == Min. This is always false.
2090
8.54k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
2091
8.54k
  llvm::APSInt Min = AdjustmentType.getMinValue();
2092
8.54k
  if (ComparisonVal == Min)
2093
492
    return F.getEmptySet();
2094
8.05k
2095
8.05k
  llvm::APSInt Lower = Min - Adjustment;
2096
8.05k
  llvm::APSInt Upper = ComparisonVal - Adjustment;
2097
8.05k
  --Upper;
2098
8.05k
2099
8.05k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
2100
8.05k
}
2101
2102
ProgramStateRef
2103
RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
2104
                                    const llvm::APSInt &Int,
2105
6.93k
                                    const llvm::APSInt &Adjustment) {
2106
6.93k
  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
2107
5.04k
  return New.isEmpty() ? nullptr : 
setConstraint(St, Sym, New)1.89k
;
2108
6.93k
}
2109
2110
RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
2111
                                               SymbolRef Sym,
2112
                                               const llvm::APSInt &Int,
2113
9.52k
                                               const llvm::APSInt &Adjustment) {
2114
  // Before we do any real work, see if the value can even show up.
2115
9.52k
  APSIntType AdjustmentType(Adjustment);
2116
9.52k
  switch (AdjustmentType.testInRange(Int, true)) {
2117
2
  case APSIntType::RTR_Below:
2118
2
    return getRange(St, Sym);
2119
9.52k
  case APSIntType::RTR_Within:
2120
9.52k
    break;
2121
2
  case APSIntType::RTR_Above:
2122
2
    return F.getEmptySet();
2123
9.52k
  }
2124
9.52k
2125
  // Special case for Int == Max. This is always false.
2126
9.52k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
2127
9.52k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
2128
9.52k
  if (ComparisonVal == Max)
2129
413
    return F.getEmptySet();
2130
9.11k
2131
9.11k
  llvm::APSInt Lower = ComparisonVal - Adjustment;
2132
9.11k
  llvm::APSInt Upper = Max - Adjustment;
2133
9.11k
  ++Lower;
2134
9.11k
2135
9.11k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
2136
9.11k
}
2137
2138
ProgramStateRef
2139
RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
2140
                                    const llvm::APSInt &Int,
2141
7.91k
                                    const llvm::APSInt &Adjustment) {
2142
7.91k
  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
2143
4.84k
  return New.isEmpty() ? nullptr : 
setConstraint(St, Sym, New)3.06k
;
2144
7.91k
}
2145
2146
RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
2147
                                               SymbolRef Sym,
2148
                                               const llvm::APSInt &Int,
2149
5.13k
                                               const llvm::APSInt &Adjustment) {
2150
  // Before we do any real work, see if the value can even show up.
2151
5.13k
  APSIntType AdjustmentType(Adjustment);
2152
5.13k
  switch (AdjustmentType.testInRange(Int, true)) {
2153
2
  case APSIntType::RTR_Below:
2154
2
    return getRange(St, Sym);
2155
5.13k
  case APSIntType::RTR_Within:
2156
5.13k
    break;
2157
2
  case APSIntType::RTR_Above:
2158
2
    return F.getEmptySet();
2159
5.13k
  }
2160
5.13k
2161
  // Special case for Int == Min. This is always feasible.
2162
5.13k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
2163
5.13k
  llvm::APSInt Min = AdjustmentType.getMinValue();
2164
5.13k
  if (ComparisonVal == Min)
2165
54
    return getRange(St, Sym);
2166
5.08k
2167
5.08k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
2168
5.08k
  llvm::APSInt Lower = ComparisonVal - Adjustment;
2169
5.08k
  llvm::APSInt Upper = Max - Adjustment;
2170
5.08k
2171
5.08k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
2172
5.08k
}
2173
2174
ProgramStateRef
2175
RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
2176
                                    const llvm::APSInt &Int,
2177
4.64k
                                    const llvm::APSInt &Adjustment) {
2178
4.64k
  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
2179
4.27k
  return New.isEmpty() ? 
nullptr364
: setConstraint(St, Sym, New);
2180
4.64k
}
2181
2182
RangeSet
2183
RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS,
2184
                                      const llvm::APSInt &Int,
2185
6.82k
                                      const llvm::APSInt &Adjustment) {
2186
  // Before we do any real work, see if the value can even show up.
2187
6.82k
  APSIntType AdjustmentType(Adjustment);
2188
6.82k
  switch (AdjustmentType.testInRange(Int, true)) {
2189
2
  case APSIntType::RTR_Below:
2190
2
    return F.getEmptySet();
2191
6.82k
  case APSIntType::RTR_Within:
2192
6.82k
    break;
2193
2
  case APSIntType::RTR_Above:
2194
2
    return RS();
2195
6.82k
  }
2196
6.82k
2197
  // Special case for Int == Max. This is always feasible.
2198
6.82k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
2199
6.82k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
2200
6.82k
  if (ComparisonVal == Max)
2201
22
    return RS();
2202
6.80k
2203
6.80k
  llvm::APSInt Min = AdjustmentType.getMinValue();
2204
6.80k
  llvm::APSInt Lower = Min - Adjustment;
2205
6.80k
  llvm::APSInt Upper = ComparisonVal - Adjustment;
2206
6.80k
2207
6.80k
  return RS().Intersect(getBasicVals(), F, Lower, Upper);
2208
6.80k
}
2209
2210
RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
2211
                                               SymbolRef Sym,
2212
                                               const llvm::APSInt &Int,
2213
6.41k
                                               const llvm::APSInt &Adjustment) {
2214
6.41k
  return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);
2215
6.41k
}
2216
2217
ProgramStateRef
2218
RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
2219
                                    const llvm::APSInt &Int,
2220
6.41k
                                    const llvm::APSInt &Adjustment) {
2221
6.41k
  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
2222
6.14k
  return New.isEmpty() ? 
nullptr275
: setConstraint(St, Sym, New);
2223
6.41k
}
2224
2225
ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
2226
    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
2227
499
    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
2228
499
  RangeSet New = getSymGERange(State, Sym, From, Adjustment);
2229
499
  if (New.isEmpty())
2230
87
    return nullptr;
2231
412
  RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
2232
360
  return Out.isEmpty() ? 
nullptr52
: setConstraint(State, Sym, Out);
2233
412
}
2234
2235
ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
2236
    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
2237
1.61k
    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
2238
1.61k
  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
2239
1.61k
  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
2240
1.61k
  RangeSet New(RangeLT.addRange(F, RangeGT));
2241
1.53k
  return New.isEmpty() ? 
nullptr77
: setConstraint(State, Sym, New);
2242
1.61k
}
2243
2244
//===----------------------------------------------------------------------===//
2245
// Pretty-printing.
2246
//===----------------------------------------------------------------------===//
2247
2248
void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,
2249
                                       const char *NL, unsigned int Space,
2250
126
                                       bool IsDot) const {
2251
126
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2252
126
2253
126
  Indent(Out, Space, IsDot) << "\"constraints\": ";
2254
126
  if (Constraints.isEmpty()) {
2255
89
    Out << "null," << NL;
2256
89
    return;
2257
89
  }
2258
37
2259
37
  ++Space;
2260
37
  Out << '[' << NL;
2261
37
  bool First = true;
2262
46
  for (std::pair<EquivalenceClass, RangeSet> P : Constraints) {
2263
46
    SymbolSet ClassMembers = P.first.getClassMembers(State);
2264
46
2265
    // We can print the same constraint for every class member.
2266
46
    for (SymbolRef ClassMember : ClassMembers) {
2267
46
      if (First) {
2268
37
        First = false;
2269
9
      } else {
2270
9
        Out << ',';
2271
9
        Out << NL;
2272
9
      }
2273
46
      Indent(Out, Space, IsDot)
2274
46
          << "{ \"symbol\": \"" << ClassMember << "\", \"range\": \"";
2275
46
      P.second.print(Out);
2276
46
      Out << "\" }";
2277
46
    }
2278
46
  }
2279
37
  Out << NL;
2280
37
2281
37
  --Space;
2282
37
  Indent(Out, Space, IsDot) << "]," << NL;
2283
37
}