Coverage Report

Created: 2021-04-13 08:44

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