Coverage Report

Created: 2022-07-15 13:45

/home/neon/workspace/llvm/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/ADT/SmallSet.h"
24
#include "llvm/ADT/StringExtras.h"
25
#include "llvm/Support/Compiler.h"
26
#include "llvm/Support/raw_ostream.h"
27
#include <algorithm>
28
#include <iterator>
29
30
using namespace clang;
31
using namespace ento;
32
33
// This class can be extended with other tables which will help to reason
34
// about ranges more precisely.
35
class OperatorRelationsTable {
36
  static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE &&
37
                    BO_GE < BO_EQ && BO_EQ < BO_NE,
38
                "This class relies on operators order. Rework it otherwise.");
39
40
public:
41
  enum TriStateKind {
42
    False = 0,
43
    True,
44
    Unknown,
45
  };
46
47
private:
48
  // CmpOpTable holds states which represent the corresponding range for
49
  // branching an exploded graph. We can reason about the branch if there is
50
  // a previously known fact of the existence of a comparison expression with
51
  // operands used in the current expression.
52
  // E.g. assuming (x < y) is true that means (x != y) is surely true.
53
  // if (x previous_operation y)  // <    | !=      | >
54
  //   if (x operation y)         // !=   | >       | <
55
  //     tristate                 // True | Unknown | False
56
  //
57
  // CmpOpTable represents next:
58
  // __|< |> |<=|>=|==|!=|UnknownX2|
59
  // < |1 |0 |* |0 |0 |* |1        |
60
  // > |0 |1 |0 |* |0 |* |1        |
61
  // <=|1 |0 |1 |* |1 |* |0        |
62
  // >=|0 |1 |* |1 |1 |* |0        |
63
  // ==|0 |0 |* |* |1 |0 |1        |
64
  // !=|1 |1 |* |* |0 |1 |0        |
65
  //
66
  // Columns stands for a previous operator.
67
  // Rows stands for a current operator.
68
  // Each row has exactly two `Unknown` cases.
69
  // UnknownX2 means that both `Unknown` previous operators are met in code,
70
  // and there is a special column for that, for example:
71
  // if (x >= y)
72
  //   if (x != y)
73
  //     if (x <= y)
74
  //       False only
75
  static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1;
76
  const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = {
77
      // <      >      <=     >=     ==     !=    UnknownX2
78
      {True, False, Unknown, False, False, Unknown, True}, // <
79
      {False, True, False, Unknown, False, Unknown, True}, // >
80
      {True, False, True, Unknown, True, Unknown, False},  // <=
81
      {False, True, Unknown, True, True, Unknown, False},  // >=
82
      {False, False, Unknown, Unknown, True, False, True}, // ==
83
      {True, True, Unknown, Unknown, False, True, False},  // !=
84
  };
85
86
0
  static size_t getIndexFromOp(BinaryOperatorKind OP) {
87
0
    return static_cast<size_t>(OP - BO_LT);
88
0
  }
89
90
public:
91
0
  constexpr size_t getCmpOpCount() const { return CmpOpCount; }
92
93
0
  static BinaryOperatorKind getOpFromIndex(size_t Index) {
94
0
    return static_cast<BinaryOperatorKind>(Index + BO_LT);
95
0
  }
96
97
  TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
98
0
                             BinaryOperatorKind QueriedOP) const {
99
0
    return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
100
0
  }
101
102
0
  TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const {
103
0
    return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];
104
0
  }
105
};
106
107
//===----------------------------------------------------------------------===//
108
//                           RangeSet implementation
109
//===----------------------------------------------------------------------===//
110
111
RangeSet::ContainerType RangeSet::Factory::EmptySet{};
112
113
0
RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
114
0
  ContainerType Result;
115
0
  Result.reserve(LHS.size() + RHS.size());
116
0
  std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),
117
0
             std::back_inserter(Result));
118
0
  return makePersistent(std::move(Result));
119
0
}
120
121
0
RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) {
122
0
  ContainerType Result;
123
0
  Result.reserve(Original.size() + 1);
124
125
0
  const_iterator Lower = llvm::lower_bound(Original, Element);
126
0
  Result.insert(Result.end(), Original.begin(), Lower);
127
0
  Result.push_back(Element);
128
0
  Result.insert(Result.end(), Lower, Original.end());
129
130
0
  return makePersistent(std::move(Result));
131
0
}
132
133
0
RangeSet RangeSet::Factory::add(RangeSet Original, const llvm::APSInt &Point) {
134
0
  return add(Original, Range(Point));
135
0
}
136
137
0
RangeSet RangeSet::Factory::unite(RangeSet LHS, RangeSet RHS) {
138
0
  ContainerType Result = unite(*LHS.Impl, *RHS.Impl);
139
0
  return makePersistent(std::move(Result));
140
0
}
141
142
0
RangeSet RangeSet::Factory::unite(RangeSet Original, Range R) {
143
0
  ContainerType Result;
144
0
  Result.push_back(R);
145
0
  Result = unite(*Original.Impl, Result);
146
0
  return makePersistent(std::move(Result));
147
0
}
148
149
0
RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) {
150
0
  return unite(Original, Range(ValueFactory.getValue(Point)));
151
0
}
152
153
RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt From,
154
0
                                  llvm::APSInt To) {
155
0
  return unite(Original,
156
0
               Range(ValueFactory.getValue(From), ValueFactory.getValue(To)));
157
0
}
158
159
template <typename T>
160
23
void swapIterators(T &First, T &FirstEnd, T &Second, T &SecondEnd) {
161
23
  std::swap(First, Second);
162
23
  std::swap(FirstEnd, SecondEnd);
163
23
}
164
165
RangeSet::ContainerType RangeSet::Factory::unite(const ContainerType &LHS,
166
0
                                                 const ContainerType &RHS) {
167
0
  if (LHS.empty())
168
0
    return RHS;
169
0
  if (RHS.empty())
170
0
    return LHS;
171
172
0
  using llvm::APSInt;
173
0
  using iterator = ContainerType::const_iterator;
174
175
0
  iterator First = LHS.begin();
176
0
  iterator FirstEnd = LHS.end();
177
0
  iterator Second = RHS.begin();
178
0
  iterator SecondEnd = RHS.end();
179
0
  APSIntType Ty = APSIntType(First->From());
180
0
  const APSInt Min = Ty.getMinValue();
181
182
  // Handle a corner case first when both range sets start from MIN.
183
  // This helps to avoid complicated conditions below. Specifically, this
184
  // particular check for `MIN` is not needed in the loop below every time
185
  // when we do `Second->From() - One` operation.
186
0
  if (Min == First->From() && Min == Second->From()) {
187
0
    if (First->To() > Second->To()) {
188
      //    [ First    ]--->
189
      //    [ Second ]----->
190
      // MIN^
191
      // The Second range is entirely inside the First one.
192
193
      // Check if Second is the last in its RangeSet.
194
0
      if (++Second == SecondEnd)
195
        //    [ First     ]--[ First + 1 ]--->
196
        //    [ Second ]--------------------->
197
        // MIN^
198
        // The Union is equal to First's RangeSet.
199
0
        return LHS;
200
0
    } else {
201
      // case 1: [ First ]----->
202
      // case 2: [ First   ]--->
203
      //         [ Second  ]--->
204
      //      MIN^
205
      // The First range is entirely inside or equal to the Second one.
206
207
      // Check if First is the last in its RangeSet.
208
0
      if (++First == FirstEnd)
209
        //    [ First ]----------------------->
210
        //    [ Second  ]--[ Second + 1 ]---->
211
        // MIN^
212
        // The Union is equal to Second's RangeSet.
213
0
        return RHS;
214
0
    }
215
0
  }
216
217
0
  const APSInt One = Ty.getValue(1);
218
0
  ContainerType Result;
219
220
  // This is called when there are no ranges left in one of the ranges.
221
  // Append the rest of the ranges from another range set to the Result
222
  // and return with that.
223
0
  const auto AppendTheRest = [&Result](iterator I, iterator E) {
224
0
    Result.append(I, E);
225
0
    return Result;
226
0
  };
227
228
0
  while (true) {
229
    // We want to keep the following invariant at all times:
230
    // ---[ First ------>
231
    // -----[ Second --->
232
0
    if (First->From() > Second->From())
233
0
      swapIterators(First, FirstEnd, Second, SecondEnd);
234
235
    // The Union definitely starts with First->From().
236
    // ----------[ First ------>
237
    // ------------[ Second --->
238
    // ----------[ Union ------>
239
    // UnionStart^
240
0
    const llvm::APSInt &UnionStart = First->From();
241
242
    // Loop where the invariant holds.
243
0
    while (true) {
244
      // Skip all enclosed ranges.
245
      // ---[                  First                     ]--->
246
      // -----[ Second ]--[ Second + 1 ]--[ Second + N ]----->
247
0
      while (First->To() >= Second->To()) {
248
        // Check if Second is the last in its RangeSet.
249
0
        if (++Second == SecondEnd) {
250
          // Append the Union.
251
          // ---[ Union      ]--->
252
          // -----[ Second ]----->
253
          // --------[ First ]--->
254
          //         UnionEnd^
255
0
          Result.emplace_back(UnionStart, First->To());
256
          // ---[ Union ]----------------->
257
          // --------------[ First + 1]--->
258
          // Append all remaining ranges from the First's RangeSet.
259
0
          return AppendTheRest(++First, FirstEnd);
260
0
        }
261
0
      }
262
263
      // Check if First and Second are disjoint. It means that we find
264
      // the end of the Union. Exit the loop and append the Union.
265
      // ---[ First ]=------------->
266
      // ------------=[ Second ]--->
267
      // ----MinusOne^
268
0
      if (First->To() < Second->From() - One)
269
0
        break;
270
271
      // First is entirely inside the Union. Go next.
272
      // ---[ Union ----------->
273
      // ---- [ First ]-------->
274
      // -------[ Second ]----->
275
      // Check if First is the last in its RangeSet.
276
0
      if (++First == FirstEnd) {
277
        // Append the Union.
278
        // ---[ Union       ]--->
279
        // -----[ First ]------->
280
        // --------[ Second ]--->
281
        //          UnionEnd^
282
0
        Result.emplace_back(UnionStart, Second->To());
283
        // ---[ Union ]------------------>
284
        // --------------[ Second + 1]--->
285
        // Append all remaining ranges from the Second's RangeSet.
286
0
        return AppendTheRest(++Second, SecondEnd);
287
0
      }
288
289
      // We know that we are at one of the two cases:
290
      // case 1: --[ First ]--------->
291
      // case 2: ----[ First ]------->
292
      // --------[ Second ]---------->
293
      // In both cases First starts after Second->From().
294
      // Make sure that the loop invariant holds.
295
0
      swapIterators(First, FirstEnd, Second, SecondEnd);
296
0
    }
297
298
    // Here First and Second are disjoint.
299
    // Append the Union.
300
    // ---[ Union    ]--------------->
301
    // -----------------[ Second ]--->
302
    // ------[ First ]--------------->
303
    //       UnionEnd^
304
0
    Result.emplace_back(UnionStart, First->To());
305
306
    // Check if First is the last in its RangeSet.
307
0
    if (++First == FirstEnd)
308
      // ---[ Union ]--------------->
309
      // --------------[ Second ]--->
310
      // Append all remaining ranges from the Second's RangeSet.
311
0
      return AppendTheRest(Second, SecondEnd);
312
0
  }
313
314
0
  llvm_unreachable("Normally, we should not reach here");
315
0
}
316
317
18
RangeSet RangeSet::Factory::getRangeSet(Range From) {
318
18
  ContainerType Result;
319
18
  Result.push_back(From);
320
18
  return makePersistent(std::move(Result));
321
18
}
322
323
47
RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) {
324
47
  llvm::FoldingSetNodeID ID;
325
47
  void *InsertPos;
326
327
47
  From.Profile(ID);
328
47
  ContainerType *Result = Cache.FindNodeOrInsertPos(ID, InsertPos);
329
330
47
  if (!Result) {
331
    // It is cheaper to fully construct the resulting range on stack
332
    // and move it to the freshly allocated buffer if we don't have
333
    // a set like this already.
334
14
    Result = construct(std::move(From));
335
14
    Cache.InsertNode(Result, InsertPos);
336
14
  }
337
338
47
  return Result;
339
47
}
340
341
14
RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) {
342
14
  void *Buffer = Arena.Allocate();
343
14
  return new (Buffer) ContainerType(std::move(From));
344
14
}
345
346
65
const llvm::APSInt &RangeSet::getMinValue() const {
347
65
  assert(!isEmpty());
348
0
  return begin()->From();
349
65
}
350
351
42
const llvm::APSInt &RangeSet::getMaxValue() const {
352
42
  assert(!isEmpty());
353
0
  return std::prev(end())->To();
354
42
}
355
356
0
bool clang::ento::RangeSet::isUnsigned() const {
357
0
  assert(!isEmpty());
358
0
  return begin()->From().isUnsigned();
359
0
}
360
361
0
uint32_t clang::ento::RangeSet::getBitWidth() const {
362
0
  assert(!isEmpty());
363
0
  return begin()->From().getBitWidth();
364
0
}
365
366
0
APSIntType clang::ento::RangeSet::getAPSIntType() const {
367
0
  assert(!isEmpty());
368
0
  return APSIntType(begin()->From());
369
0
}
370
371
6
bool RangeSet::containsImpl(llvm::APSInt &Point) const {
372
6
  if (isEmpty() || !pin(Point))
373
0
    return false;
374
375
6
  Range Dummy(Point);
376
6
  const_iterator It = llvm::upper_bound(*this, Dummy);
377
6
  if (It == begin())
378
0
    return false;
379
380
6
  return std::prev(It)->Includes(Point);
381
6
}
382
383
6
bool RangeSet::pin(llvm::APSInt &Point) const {
384
6
  APSIntType Type(getMinValue());
385
6
  if (Type.testInRange(Point, true) != APSIntType::RTR_Within)
386
0
    return false;
387
388
6
  Type.apply(Point);
389
6
  return true;
390
6
}
391
392
18
bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
393
  // This function has nine cases, the cartesian product of range-testing
394
  // both the upper and lower bounds against the symbol's type.
395
  // Each case requires a different pinning operation.
396
  // The function returns false if the described range is entirely outside
397
  // the range of values for the associated symbol.
398
18
  APSIntType Type(getMinValue());
399
18
  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
400
18
  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
401
402
18
  switch (LowerTest) {
403
0
  case APSIntType::RTR_Below:
404
0
    switch (UpperTest) {
405
0
    case APSIntType::RTR_Below:
406
      // The entire range is outside the symbol's set of possible values.
407
      // If this is a conventionally-ordered range, the state is infeasible.
408
0
      if (Lower <= Upper)
409
0
        return false;
410
411
      // However, if the range wraps around, it spans all possible values.
412
0
      Lower = Type.getMinValue();
413
0
      Upper = Type.getMaxValue();
414
0
      break;
415
0
    case APSIntType::RTR_Within:
416
      // The range starts below what's possible but ends within it. Pin.
417
0
      Lower = Type.getMinValue();
418
0
      Type.apply(Upper);
419
0
      break;
420
0
    case APSIntType::RTR_Above:
421
      // The range spans all possible values for the symbol. Pin.
422
0
      Lower = Type.getMinValue();
423
0
      Upper = Type.getMaxValue();
424
0
      break;
425
0
    }
426
0
    break;
427
18
  case APSIntType::RTR_Within:
428
18
    switch (UpperTest) {
429
0
    case APSIntType::RTR_Below:
430
      // The range wraps around, but all lower values are not possible.
431
0
      Type.apply(Lower);
432
0
      Upper = Type.getMaxValue();
433
0
      break;
434
18
    case APSIntType::RTR_Within:
435
      // The range may or may not wrap around, but both limits are valid.
436
18
      Type.apply(Lower);
437
18
      Type.apply(Upper);
438
18
      break;
439
0
    case APSIntType::RTR_Above:
440
      // The range starts within what's possible but ends above it. Pin.
441
0
      Type.apply(Lower);
442
0
      Upper = Type.getMaxValue();
443
0
      break;
444
18
    }
445
18
    break;
446
18
  case APSIntType::RTR_Above:
447
0
    switch (UpperTest) {
448
0
    case APSIntType::RTR_Below:
449
      // The range wraps but is outside the symbol's set of possible values.
450
0
      return false;
451
0
    case APSIntType::RTR_Within:
452
      // The range starts above what's possible but ends within it (wrap).
453
0
      Lower = Type.getMinValue();
454
0
      Type.apply(Upper);
455
0
      break;
456
0
    case APSIntType::RTR_Above:
457
      // The entire range is outside the symbol's set of possible values.
458
      // If this is a conventionally-ordered range, the state is infeasible.
459
0
      if (Lower <= Upper)
460
0
        return false;
461
462
      // However, if the range wraps around, it spans all possible values.
463
0
      Lower = Type.getMinValue();
464
0
      Upper = Type.getMaxValue();
465
0
      break;
466
0
    }
467
0
    break;
468
18
  }
469
470
18
  return true;
471
18
}
472
473
RangeSet RangeSet::Factory::intersect(RangeSet What, llvm::APSInt Lower,
474
18
                                      llvm::APSInt Upper) {
475
18
  if (What.isEmpty() || !What.pin(Lower, Upper))
476
0
    return getEmptySet();
477
478
18
  ContainerType DummyContainer;
479
480
18
  if (Lower <= Upper) {
481
    // [Lower, Upper] is a regular range.
482
    //
483
    // Shortcut: check that there is even a possibility of the intersection
484
    //           by checking the two following situations:
485
    //
486
    //               <---[  What  ]---[------]------>
487
    //                              Lower  Upper
488
    //                            -or-
489
    //               <----[------]----[  What  ]---->
490
    //                  Lower  Upper
491
18
    if (What.getMaxValue() < Lower || Upper < What.getMinValue())
492
1
      return getEmptySet();
493
494
17
    DummyContainer.push_back(
495
17
        Range(ValueFactory.getValue(Lower), ValueFactory.getValue(Upper)));
496
17
  } else {
497
    // [Lower, Upper] is an inverted range, i.e. [MIN, Upper] U [Lower, MAX]
498
    //
499
    // Shortcut: check that there is even a possibility of the intersection
500
    //           by checking the following situation:
501
    //
502
    //               <------]---[  What  ]---[------>
503
    //                    Upper             Lower
504
0
    if (What.getMaxValue() < Lower && Upper < What.getMinValue())
505
0
      return getEmptySet();
506
507
0
    DummyContainer.push_back(
508
0
        Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper)));
509
0
    DummyContainer.push_back(
510
0
        Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower)));
511
0
  }
512
513
17
  return intersect(*What.Impl, DummyContainer);
514
18
}
515
516
RangeSet RangeSet::Factory::intersect(const RangeSet::ContainerType &LHS,
517
29
                                      const RangeSet::ContainerType &RHS) {
518
29
  ContainerType Result;
519
29
  Result.reserve(std::max(LHS.size(), RHS.size()));
520
521
29
  const_iterator First = LHS.begin(), Second = RHS.begin(),
522
29
                 FirstEnd = LHS.end(), SecondEnd = RHS.end();
523
524
  // If we ran out of ranges in one set, but not in the other,
525
  // it means that those elements are definitely not in the
526
  // intersection.
527
58
  while (First != FirstEnd && Second != SecondEnd) {
528
    // We want to keep the following invariant at all times:
529
    //
530
    //    ----[ First ---------------------->
531
    //    --------[ Second ----------------->
532
29
    if (Second->From() < First->From())
533
15
      swapIterators(First, FirstEnd, Second, SecondEnd);
534
535
    // Loop where the invariant holds:
536
29
    do {
537
      // Check for the following situation:
538
      //
539
      //    ----[ First ]--------------------->
540
      //    ---------------[ Second ]--------->
541
      //
542
      // which means that...
543
29
      if (Second->From() > First->To()) {
544
        // ...First is not in the intersection.
545
        //
546
        // We should move on to the next range after First and break out of the
547
        // loop because the invariant might not be true.
548
0
        ++First;
549
0
        break;
550
0
      }
551
552
      // We have a guaranteed intersection at this point!
553
      // And this is the current situation:
554
      //
555
      //    ----[   First   ]----------------->
556
      //    -------[ Second ------------------>
557
      //
558
      // Additionally, it definitely starts with Second->From().
559
29
      const llvm::APSInt &IntersectionStart = Second->From();
560
561
      // It is important to know which of the two ranges' ends
562
      // is greater.  That "longer" range might have some other
563
      // intersections, while the "shorter" range might not.
564
29
      if (Second->To() > First->To()) {
565
        // Here we make a decision to keep First as the "longer"
566
        // range.
567
8
        swapIterators(First, FirstEnd, Second, SecondEnd);
568
8
      }
569
570
      // At this point, we have the following situation:
571
      //
572
      //    ---- First      ]-------------------->
573
      //    ---- Second ]--[  Second+1 ---------->
574
      //
575
      // We don't know the relationship between First->From and
576
      // Second->From and we don't know whether Second+1 intersects
577
      // with First.
578
      //
579
      // However, we know that [IntersectionStart, Second->To] is
580
      // a part of the intersection...
581
29
      Result.push_back(Range(IntersectionStart, Second->To()));
582
29
      ++Second;
583
      // ...and that the invariant will hold for a valid Second+1
584
      // because First->From <= Second->To < (Second+1)->From.
585
29
    } while (Second != SecondEnd);
586
29
  }
587
588
29
  if (Result.empty())
589
0
    return getEmptySet();
590
591
29
  return makePersistent(std::move(Result));
592
29
}
593
594
12
RangeSet RangeSet::Factory::intersect(RangeSet LHS, RangeSet RHS) {
595
  // Shortcut: let's see if the intersection is even possible.
596
12
  if (LHS.isEmpty() || RHS.isEmpty() || LHS.getMaxValue() < RHS.getMinValue() ||
597
12
      RHS.getMaxValue() < LHS.getMinValue())
598
0
    return getEmptySet();
599
600
12
  return intersect(*LHS.Impl, *RHS.Impl);
601
12
}
602
603
0
RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) {
604
0
  if (LHS.containsImpl(Point))
605
0
    return getRangeSet(ValueFactory.getValue(Point));
606
607
0
  return getEmptySet();
608
0
}
609
610
0
RangeSet RangeSet::Factory::negate(RangeSet What) {
611
0
  if (What.isEmpty())
612
0
    return getEmptySet();
613
614
0
  const llvm::APSInt SampleValue = What.getMinValue();
615
0
  const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
616
0
  const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);
617
618
0
  ContainerType Result;
619
0
  Result.reserve(What.size() + (SampleValue == MIN));
620
621
  // Handle a special case for MIN value.
622
0
  const_iterator It = What.begin();
623
0
  const_iterator End = What.end();
624
625
0
  const llvm::APSInt &From = It->From();
626
0
  const llvm::APSInt &To = It->To();
627
628
0
  if (From == MIN) {
629
    // If the range [From, To] is [MIN, MAX], then result is also [MIN, MAX].
630
0
    if (To == MAX) {
631
0
      return What;
632
0
    }
633
634
0
    const_iterator Last = std::prev(End);
635
636
    // Try to find and unite the following ranges:
637
    // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
638
0
    if (Last->To() == MAX) {
639
      // It means that in the original range we have ranges
640
      //   [MIN, A], ... , [B, MAX]
641
      // And the result should be [MIN, -B], ..., [-A, MAX]
642
0
      Result.emplace_back(MIN, ValueFactory.getValue(-Last->From()));
643
      // We already negated Last, so we can skip it.
644
0
      End = Last;
645
0
    } else {
646
      // Add a separate range for the lowest value.
647
0
      Result.emplace_back(MIN, MIN);
648
0
    }
649
650
    // Skip adding the second range in case when [From, To] are [MIN, MIN].
651
0
    if (To != MIN) {
652
0
      Result.emplace_back(ValueFactory.getValue(-To), MAX);
653
0
    }
654
655
    // Skip the first range in the loop.
656
0
    ++It;
657
0
  }
658
659
  // Negate all other ranges.
660
0
  for (; It != End; ++It) {
661
    // Negate int values.
662
0
    const llvm::APSInt &NewFrom = ValueFactory.getValue(-It->To());
663
0
    const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From());
664
665
    // Add a negated range.
666
0
    Result.emplace_back(NewFrom, NewTo);
667
0
  }
668
669
0
  llvm::sort(Result);
670
0
  return makePersistent(std::move(Result));
671
0
}
672
673
// Convert range set to the given integral type using truncation and promotion.
674
// This works similar to APSIntType::apply function but for the range set.
675
0
RangeSet RangeSet::Factory::castTo(RangeSet What, APSIntType Ty) {
676
  // Set is empty or NOOP (aka cast to the same type).
677
0
  if (What.isEmpty() || What.getAPSIntType() == Ty)
678
0
    return What;
679
680
0
  const bool IsConversion = What.isUnsigned() != Ty.isUnsigned();
681
0
  const bool IsTruncation = What.getBitWidth() > Ty.getBitWidth();
682
0
  const bool IsPromotion = What.getBitWidth() < Ty.getBitWidth();
683
684
0
  if (IsTruncation)
685
0
    return makePersistent(truncateTo(What, Ty));
686
687
  // Here we handle 2 cases:
688
  // - IsConversion && !IsPromotion.
689
  //   In this case we handle changing a sign with same bitwidth: char -> uchar,
690
  //   uint -> int. Here we convert negatives to positives and positives which
691
  //   is out of range to negatives. We use convertTo function for that.
692
  // - IsConversion && IsPromotion && !What.isUnsigned().
693
  //   In this case we handle changing a sign from signeds to unsigneds with
694
  //   higher bitwidth: char -> uint, int-> uint64. The point is that we also
695
  //   need convert negatives to positives and use convertTo function as well.
696
  //   For example, we don't need such a convertion when converting unsigned to
697
  //   signed with higher bitwidth, because all the values of unsigned is valid
698
  //   for the such signed.
699
0
  if (IsConversion && (!IsPromotion || !What.isUnsigned()))
700
0
    return makePersistent(convertTo(What, Ty));
701
702
0
  assert(IsPromotion && "Only promotion operation from unsigneds left.");
703
0
  return makePersistent(promoteTo(What, Ty));
704
0
}
705
706
0
RangeSet RangeSet::Factory::castTo(RangeSet What, QualType T) {
707
0
  assert(T->isIntegralOrEnumerationType() && "T shall be an integral type.");
708
0
  return castTo(What, ValueFactory.getAPSIntType(T));
709
0
}
710
711
RangeSet::ContainerType RangeSet::Factory::truncateTo(RangeSet What,
712
0
                                                      APSIntType Ty) {
713
0
  using llvm::APInt;
714
0
  using llvm::APSInt;
715
0
  ContainerType Result;
716
0
  ContainerType Dummy;
717
  // CastRangeSize is an amount of all possible values of cast type.
718
  // Example: `char` has 256 values; `short` has 65536 values.
719
  // But in fact we use `amount of values` - 1, because
720
  // we can't keep `amount of values of UINT64` inside uint64_t.
721
  // E.g. 256 is an amount of all possible values of `char` and we can't keep
722
  // it inside `char`.
723
  // And it's OK, it's enough to do correct calculations.
724
0
  uint64_t CastRangeSize = APInt::getMaxValue(Ty.getBitWidth()).getZExtValue();
725
0
  for (const Range &R : What) {
726
    // Get bounds of the given range.
727
0
    APSInt FromInt = R.From();
728
0
    APSInt ToInt = R.To();
729
    // CurrentRangeSize is an amount of all possible values of the current
730
    // range minus one.
731
0
    uint64_t CurrentRangeSize = (ToInt - FromInt).getZExtValue();
732
    // This is an optimization for a specific case when this Range covers
733
    // the whole range of the target type.
734
0
    Dummy.clear();
735
0
    if (CurrentRangeSize >= CastRangeSize) {
736
0
      Dummy.emplace_back(ValueFactory.getMinValue(Ty),
737
0
                         ValueFactory.getMaxValue(Ty));
738
0
      Result = std::move(Dummy);
739
0
      break;
740
0
    }
741
    // Cast the bounds.
742
0
    Ty.apply(FromInt);
743
0
    Ty.apply(ToInt);
744
0
    const APSInt &PersistentFrom = ValueFactory.getValue(FromInt);
745
0
    const APSInt &PersistentTo = ValueFactory.getValue(ToInt);
746
0
    if (FromInt > ToInt) {
747
0
      Dummy.emplace_back(ValueFactory.getMinValue(Ty), PersistentTo);
748
0
      Dummy.emplace_back(PersistentFrom, ValueFactory.getMaxValue(Ty));
749
0
    } else
750
0
      Dummy.emplace_back(PersistentFrom, PersistentTo);
751
    // Every range retrieved after truncation potentialy has garbage values.
752
    // So, we have to unite every next range with the previouses.
753
0
    Result = unite(Result, Dummy);
754
0
  }
755
756
0
  return Result;
757
0
}
758
759
// Divide the convertion into two phases (presented as loops here).
760
// First phase(loop) works when casted values go in ascending order.
761
// E.g. char{1,3,5,127} -> uint{1,3,5,127}
762
// Interrupt the first phase and go to second one when casted values start
763
// go in descending order. That means that we crossed over the middle of
764
// the type value set (aka 0 for signeds and MAX/2+1 for unsigneds).
765
// For instance:
766
// 1: uchar{1,3,5,128,255} -> char{1,3,5,-128,-1}
767
//    Here we put {1,3,5} to one array and {-128, -1} to another
768
// 2: char{-128,-127,-1,0,1,2} -> uchar{128,129,255,0,1,3}
769
//    Here we put {128,129,255} to one array and {0,1,3} to another.
770
// After that we unite both arrays.
771
// NOTE: We don't just concatenate the arrays, because they may have
772
// adjacent ranges, e.g.:
773
// 1: char(-128, 127) -> uchar -> arr1(128, 255), arr2(0, 127) ->
774
//    unite -> uchar(0, 255)
775
// 2: uchar(0, 1)U(254, 255) -> char -> arr1(0, 1), arr2(-2, -1) ->
776
//    unite -> uchar(-2, 1)
777
RangeSet::ContainerType RangeSet::Factory::convertTo(RangeSet What,
778
0
                                                     APSIntType Ty) {
779
0
  using llvm::APInt;
780
0
  using llvm::APSInt;
781
0
  using Bounds = std::pair<const APSInt &, const APSInt &>;
782
0
  ContainerType AscendArray;
783
0
  ContainerType DescendArray;
784
0
  auto CastRange = [Ty, &VF = ValueFactory](const Range &R) -> Bounds {
785
    // Get bounds of the given range.
786
0
    APSInt FromInt = R.From();
787
0
    APSInt ToInt = R.To();
788
    // Cast the bounds.
789
0
    Ty.apply(FromInt);
790
0
    Ty.apply(ToInt);
791
0
    return {VF.getValue(FromInt), VF.getValue(ToInt)};
792
0
  };
793
  // Phase 1. Fill the first array.
794
0
  APSInt LastConvertedInt = Ty.getMinValue();
795
0
  const auto *It = What.begin();
796
0
  const auto *E = What.end();
797
0
  while (It != E) {
798
0
    Bounds NewBounds = CastRange(*(It++));
799
    // If values stop going acsending order, go to the second phase(loop).
800
0
    if (NewBounds.first < LastConvertedInt) {
801
0
      DescendArray.emplace_back(NewBounds.first, NewBounds.second);
802
0
      break;
803
0
    }
804
    // If the range contains a midpoint, then split the range.
805
    // E.g. char(-5, 5) -> uchar(251, 5)
806
    // Here we shall add a range (251, 255) to the first array and (0, 5) to the
807
    // second one.
808
0
    if (NewBounds.first > NewBounds.second) {
809
0
      DescendArray.emplace_back(ValueFactory.getMinValue(Ty), NewBounds.second);
810
0
      AscendArray.emplace_back(NewBounds.first, ValueFactory.getMaxValue(Ty));
811
0
    } else
812
      // Values are going acsending order.
813
0
      AscendArray.emplace_back(NewBounds.first, NewBounds.second);
814
0
    LastConvertedInt = NewBounds.first;
815
0
  }
816
  // Phase 2. Fill the second array.
817
0
  while (It != E) {
818
0
    Bounds NewBounds = CastRange(*(It++));
819
0
    DescendArray.emplace_back(NewBounds.first, NewBounds.second);
820
0
  }
821
  // Unite both arrays.
822
0
  return unite(AscendArray, DescendArray);
823
0
}
824
825
/// Promotion from unsigneds to signeds/unsigneds left.
826
RangeSet::ContainerType RangeSet::Factory::promoteTo(RangeSet What,
827
0
                                                     APSIntType Ty) {
828
0
  ContainerType Result;
829
  // We definitely know the size of the result set.
830
0
  Result.reserve(What.size());
831
832
  // Each unsigned value fits every larger type without any changes,
833
  // whether the larger type is signed or unsigned. So just promote and push
834
  // back each range one by one.
835
0
  for (const Range &R : What) {
836
    // Get bounds of the given range.
837
0
    llvm::APSInt FromInt = R.From();
838
0
    llvm::APSInt ToInt = R.To();
839
    // Cast the bounds.
840
0
    Ty.apply(FromInt);
841
0
    Ty.apply(ToInt);
842
0
    Result.emplace_back(ValueFactory.getValue(FromInt),
843
0
                        ValueFactory.getValue(ToInt));
844
0
  }
845
0
  return Result;
846
0
}
847
848
RangeSet RangeSet::Factory::deletePoint(RangeSet From,
849
0
                                        const llvm::APSInt &Point) {
850
0
  if (!From.contains(Point))
851
0
    return From;
852
853
0
  llvm::APSInt Upper = Point;
854
0
  llvm::APSInt Lower = Point;
855
856
0
  ++Upper;
857
0
  --Lower;
858
859
  // Notice that the lower bound is greater than the upper bound.
860
0
  return intersect(From, Upper, Lower);
861
0
}
862
863
0
LLVM_DUMP_METHOD void Range::dump(raw_ostream &OS) const {
864
0
  OS << '[' << toString(From(), 10) << ", " << toString(To(), 10) << ']';
865
0
}
866
0
LLVM_DUMP_METHOD void Range::dump() const { dump(llvm::errs()); }
867
868
0
LLVM_DUMP_METHOD void RangeSet::dump(raw_ostream &OS) const {
869
0
  OS << "{ ";
870
0
  llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(OS); });
871
0
  OS << " }";
872
0
}
873
0
LLVM_DUMP_METHOD void RangeSet::dump() const { dump(llvm::errs()); }
874
875
REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
876
877
namespace {
878
class EquivalenceClass;
879
} // end anonymous namespace
880
881
REGISTER_MAP_WITH_PROGRAMSTATE(ClassMap, SymbolRef, EquivalenceClass)
882
REGISTER_MAP_WITH_PROGRAMSTATE(ClassMembers, EquivalenceClass, SymbolSet)
883
REGISTER_MAP_WITH_PROGRAMSTATE(ConstraintRange, EquivalenceClass, RangeSet)
884
885
REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass)
886
REGISTER_MAP_WITH_PROGRAMSTATE(DisequalityMap, EquivalenceClass, ClassSet)
887
888
namespace {
889
/// This class encapsulates a set of symbols equal to each other.
890
///
891
/// The main idea of the approach requiring such classes is in narrowing
892
/// and sharing constraints between symbols within the class.  Also we can
893
/// conclude that there is no practical need in storing constraints for
894
/// every member of the class separately.
895
///
896
/// Main terminology:
897
///
898
///   * "Equivalence class" is an object of this class, which can be efficiently
899
///     compared to other classes.  It represents the whole class without
900
///     storing the actual in it.  The members of the class however can be
901
///     retrieved from the state.
902
///
903
///   * "Class members" are the symbols corresponding to the class.  This means
904
///     that A == B for every member symbols A and B from the class.  Members of
905
///     each class are stored in the state.
906
///
907
///   * "Trivial class" is a class that has and ever had only one same symbol.
908
///
909
///   * "Merge operation" merges two classes into one.  It is the main operation
910
///     to produce non-trivial classes.
911
///     If, at some point, we can assume that two symbols from two distinct
912
///     classes are equal, we can merge these classes.
913
class EquivalenceClass : public llvm::FoldingSetNode {
914
public:
915
  /// Find equivalence class for the given symbol in the given state.
916
  LLVM_NODISCARD static inline EquivalenceClass find(ProgramStateRef State,
917
                                                     SymbolRef Sym);
918
919
  /// Merge classes for the given symbols and return a new state.
920
  LLVM_NODISCARD static inline ProgramStateRef merge(RangeSet::Factory &F,
921
                                                     ProgramStateRef State,
922
                                                     SymbolRef First,
923
                                                     SymbolRef Second);
924
  // Merge this class with the given class and return a new state.
925
  LLVM_NODISCARD inline ProgramStateRef
926
  merge(RangeSet::Factory &F, ProgramStateRef State, EquivalenceClass Other);
927
928
  /// Return a set of class members for the given state.
929
  LLVM_NODISCARD inline SymbolSet getClassMembers(ProgramStateRef State) const;
930
931
  /// Return true if the current class is trivial in the given state.
932
  /// A class is trivial if and only if there is not any member relations stored
933
  /// to it in State/ClassMembers.
934
  /// An equivalence class with one member might seem as it does not hold any
935
  /// meaningful information, i.e. that is a tautology. However, during the
936
  /// removal of dead symbols we do not remove classes with one member for
937
  /// resource and performance reasons. Consequently, a class with one member is
938
  /// not necessarily trivial. It could happen that we have a class with two
939
  /// members and then during the removal of dead symbols we remove one of its
940
  /// members. In this case, the class is still non-trivial (it still has the
941
  /// mappings in ClassMembers), even though it has only one member.
942
  LLVM_NODISCARD inline bool isTrivial(ProgramStateRef State) const;
943
944
  /// Return true if the current class is trivial and its only member is dead.
945
  LLVM_NODISCARD inline bool isTriviallyDead(ProgramStateRef State,
946
                                             SymbolReaper &Reaper) const;
947
948
  LLVM_NODISCARD static inline ProgramStateRef
949
  markDisequal(RangeSet::Factory &F, ProgramStateRef State, SymbolRef First,
950
               SymbolRef Second);
951
  LLVM_NODISCARD static inline ProgramStateRef
952
  markDisequal(RangeSet::Factory &F, ProgramStateRef State,
953
               EquivalenceClass First, EquivalenceClass Second);
954
  LLVM_NODISCARD inline ProgramStateRef
955
  markDisequal(RangeSet::Factory &F, ProgramStateRef State,
956
               EquivalenceClass Other) const;
957
  LLVM_NODISCARD static inline ClassSet
958
  getDisequalClasses(ProgramStateRef State, SymbolRef Sym);
959
  LLVM_NODISCARD inline ClassSet
960
  getDisequalClasses(ProgramStateRef State) const;
961
  LLVM_NODISCARD inline ClassSet
962
  getDisequalClasses(DisequalityMapTy Map, ClassSet::Factory &Factory) const;
963
964
  LLVM_NODISCARD static inline Optional<bool> areEqual(ProgramStateRef State,
965
                                                       EquivalenceClass First,
966
                                                       EquivalenceClass Second);
967
  LLVM_NODISCARD static inline Optional<bool>
968
  areEqual(ProgramStateRef State, SymbolRef First, SymbolRef Second);
969
970
  /// Remove one member from the class.
971
  LLVM_NODISCARD ProgramStateRef removeMember(ProgramStateRef State,
972
                                              const SymbolRef Old);
973
974
  /// Iterate over all symbols and try to simplify them.
975
  LLVM_NODISCARD static inline ProgramStateRef simplify(SValBuilder &SVB,
976
                                                        RangeSet::Factory &F,
977
                                                        ProgramStateRef State,
978
                                                        EquivalenceClass Class);
979
980
  void dumpToStream(ProgramStateRef State, raw_ostream &os) const;
981
0
  LLVM_DUMP_METHOD void dump(ProgramStateRef State) const {
982
0
    dumpToStream(State, llvm::errs());
983
0
  }
984
985
  /// Check equivalence data for consistency.
986
  LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED static bool
987
  isClassDataConsistent(ProgramStateRef State);
988
989
0
  LLVM_NODISCARD QualType getType() const {
990
0
    return getRepresentativeSymbol()->getType();
991
0
  }
992
993
  EquivalenceClass() = delete;
994
  EquivalenceClass(const EquivalenceClass &) = default;
995
  EquivalenceClass &operator=(const EquivalenceClass &) = delete;
996
  EquivalenceClass(EquivalenceClass &&) = default;
997
  EquivalenceClass &operator=(EquivalenceClass &&) = delete;
998
999
172
  bool operator==(const EquivalenceClass &Other) const {
1000
172
    return ID == Other.ID;
1001
172
  }
1002
69
  bool operator<(const EquivalenceClass &Other) const { return ID < Other.ID; }
1003
0
  bool operator!=(const EquivalenceClass &Other) const {
1004
0
    return !operator==(Other);
1005
0
  }
1006
1007
28
  static void Profile(llvm::FoldingSetNodeID &ID, uintptr_t CID) {
1008
28
    ID.AddInteger(CID);
1009
28
  }
1010
1011
28
  void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, this->ID); }
1012
1013
private:
1014
  /* implicit */ EquivalenceClass(SymbolRef Sym)
1015
118
      : ID(reinterpret_cast<uintptr_t>(Sym)) {}
1016
1017
  /// This function is intended to be used ONLY within the class.
1018
  /// The fact that ID is a pointer to a symbol is an implementation detail
1019
  /// and should stay that way.
1020
  /// In the current implementation, we use it to retrieve the only member
1021
  /// of the trivial class.
1022
37
  SymbolRef getRepresentativeSymbol() const {
1023
37
    return reinterpret_cast<SymbolRef>(ID);
1024
37
  }
1025
  static inline SymbolSet::Factory &getMembersFactory(ProgramStateRef State);
1026
1027
  inline ProgramStateRef mergeImpl(RangeSet::Factory &F, ProgramStateRef State,
1028
                                   SymbolSet Members, EquivalenceClass Other,
1029
                                   SymbolSet OtherMembers);
1030
1031
  static inline bool
1032
  addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
1033
                       RangeSet::Factory &F, ProgramStateRef State,
1034
                       EquivalenceClass First, EquivalenceClass Second);
1035
1036
  /// This is a unique identifier of the class.
1037
  uintptr_t ID;
1038
};
1039
1040
//===----------------------------------------------------------------------===//
1041
//                             Constraint functions
1042
//===----------------------------------------------------------------------===//
1043
1044
LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED bool
1045
4
areFeasible(ConstraintRangeTy Constraints) {
1046
4
  return llvm::none_of(
1047
4
      Constraints,
1048
6
      [](const std::pair<EquivalenceClass, RangeSet> &ClassConstraint) {
1049
6
        return ClassConstraint.second.isEmpty();
1050
6
      });
1051
4
}
1052
1053
LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State,
1054
107
                                                    EquivalenceClass Class) {
1055
107
  return State->get<ConstraintRange>(Class);
1056
107
}
1057
1058
LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State,
1059
101
                                                    SymbolRef Sym) {
1060
101
  return getConstraint(State, EquivalenceClass::find(State, Sym));
1061
101
}
1062
1063
LLVM_NODISCARD ProgramStateRef setConstraint(ProgramStateRef State,
1064
                                             EquivalenceClass Class,
1065
13
                                             RangeSet Constraint) {
1066
13
  return State->set<ConstraintRange>(Class, Constraint);
1067
13
}
1068
1069
LLVM_NODISCARD ProgramStateRef setConstraints(ProgramStateRef State,
1070
4
                                              ConstraintRangeTy Constraints) {
1071
4
  return State->set<ConstraintRange>(Constraints);
1072
4
}
1073
1074
//===----------------------------------------------------------------------===//
1075
//                       Equality/diseqiality abstraction
1076
//===----------------------------------------------------------------------===//
1077
1078
/// A small helper function for detecting symbolic (dis)equality.
1079
///
1080
/// Equality check can have different forms (like a == b or a - b) and this
1081
/// class encapsulates those away if the only thing the user wants to check -
1082
/// whether it's equality/diseqiality or not.
1083
///
1084
/// \returns true if assuming this Sym to be true means equality of operands
1085
///          false if it means disequality of operands
1086
///          None otherwise
1087
0
Optional<bool> meansEquality(const SymSymExpr *Sym) {
1088
0
  switch (Sym->getOpcode()) {
1089
0
  case BO_Sub:
1090
    // This case is: A - B != 0 -> disequality check.
1091
0
    return false;
1092
0
  case BO_EQ:
1093
    // This case is: A == B != 0 -> equality check.
1094
0
    return true;
1095
0
  case BO_NE:
1096
    // This case is: A != B != 0 -> diseqiality check.
1097
0
    return false;
1098
0
  default:
1099
0
    return llvm::None;
1100
0
  }
1101
0
}
1102
1103
//===----------------------------------------------------------------------===//
1104
//                            Intersection functions
1105
//===----------------------------------------------------------------------===//
1106
1107
template <class SecondTy, class... RestTy>
1108
LLVM_NODISCARD inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head,
1109
                                         SecondTy Second, RestTy... Tail);
1110
1111
template <class... RangeTy> struct IntersectionTraits;
1112
1113
template <class... TailTy> struct IntersectionTraits<RangeSet, TailTy...> {
1114
  // Found RangeSet, no need to check any further
1115
  using Type = RangeSet;
1116
};
1117
1118
template <> struct IntersectionTraits<> {
1119
  // We ran out of types, and we didn't find any RangeSet, so the result should
1120
  // be optional.
1121
  using Type = Optional<RangeSet>;
1122
};
1123
1124
template <class OptionalOrPointer, class... TailTy>
1125
struct IntersectionTraits<OptionalOrPointer, TailTy...> {
1126
  // If current type is Optional or a raw pointer, we should keep looking.
1127
  using Type = typename IntersectionTraits<TailTy...>::Type;
1128
};
1129
1130
template <class EndTy>
1131
18
LLVM_NODISCARD inline EndTy intersect(RangeSet::Factory &F, EndTy End) {
1132
  // If the list contains only RangeSet or Optional<RangeSet>, simply return
1133
  // that range set.
1134
18
  return End;
1135
18
}
1136
1137
LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional<RangeSet>
1138
0
intersect(RangeSet::Factory &F, const RangeSet *End) {
1139
  // This is an extraneous conversion from a raw pointer into Optional<RangeSet>
1140
0
  if (End) {
1141
0
    return *End;
1142
0
  }
1143
0
  return llvm::None;
1144
0
}
1145
1146
template <class... RestTy>
1147
LLVM_NODISCARD inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head,
1148
12
                                         RangeSet Second, RestTy... Tail) {
1149
  // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
1150
  // of the function and can be sure that the result is RangeSet.
1151
12
  return intersect(F, F.intersect(Head, Second), Tail...);
1152
12
}
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>(clang::ento::RangeSet::Factory&, clang::ento::RangeSet, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<clang::ento::RangeSet>(clang::ento::RangeSet::Factory&, clang::ento::RangeSet, clang::ento::RangeSet, clang::ento::RangeSet)
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<>(clang::ento::RangeSet::Factory&, clang::ento::RangeSet, clang::ento::RangeSet)
Line
Count
Source
1148
12
                                         RangeSet Second, RestTy... Tail) {
1149
  // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
1150
  // of the function and can be sure that the result is RangeSet.
1151
12
  return intersect(F, F.intersect(Head, Second), Tail...);
1152
12
}
1153
1154
template <class SecondTy, class... RestTy>
1155
LLVM_NODISCARD inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head,
1156
24
                                         SecondTy Second, RestTy... Tail) {
1157
24
  if (Second) {
1158
    // Here we call the <RangeSet,RangeSet,...> version of the function...
1159
0
    return intersect(F, Head, *Second, Tail...);
1160
0
  }
1161
  // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which
1162
  // means that the result is definitely RangeSet.
1163
24
  return intersect(F, Head, Tail...);
1164
24
}
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>(clang::ento::RangeSet::Factory&, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet)
Line
Count
Source
1156
12
                                         SecondTy Second, RestTy... Tail) {
1157
12
  if (Second) {
1158
    // Here we call the <RangeSet,RangeSet,...> version of the function...
1159
0
    return intersect(F, Head, *Second, Tail...);
1160
0
  }
1161
  // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which
1162
  // means that the result is definitely RangeSet.
1163
12
  return intersect(F, Head, Tail...);
1164
12
}
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>(clang::ento::RangeSet::Factory&, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet)
Line
Count
Source
1156
12
                                         SecondTy Second, RestTy... Tail) {
1157
12
  if (Second) {
1158
    // Here we call the <RangeSet,RangeSet,...> version of the function...
1159
0
    return intersect(F, Head, *Second, Tail...);
1160
0
  }
1161
  // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which
1162
  // means that the result is definitely RangeSet.
1163
12
  return intersect(F, Head, Tail...);
1164
12
}
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<clang::ento::RangeSet const*>(clang::ento::RangeSet::Factory&, clang::ento::RangeSet, clang::ento::RangeSet const*)
1165
1166
/// Main generic intersect function.
1167
/// It intersects all of the given range sets.  If some of the given arguments
1168
/// don't hold a range set (nullptr or llvm::None), the function will skip them.
1169
///
1170
/// Available representations for the arguments are:
1171
///   * RangeSet
1172
///   * Optional<RangeSet>
1173
///   * RangeSet *
1174
/// Pointer to a RangeSet is automatically assumed to be nullable and will get
1175
/// checked as well as the optional version.  If this behaviour is undesired,
1176
/// please dereference the pointer in the call.
1177
///
1178
/// Return type depends on the arguments' types.  If we can be sure in compile
1179
/// time that there will be a range set as a result, the returning type is
1180
/// simply RangeSet, in other cases we have to back off to Optional<RangeSet>.
1181
///
1182
/// Please, prefer optional range sets to raw pointers.  If the last argument is
1183
/// a raw pointer and all previous arguments are None, it will cost one
1184
/// additional check to convert RangeSet * into Optional<RangeSet>.
1185
template <class HeadTy, class SecondTy, class... RestTy>
1186
LLVM_NODISCARD inline
1187
    typename IntersectionTraits<HeadTy, SecondTy, RestTy...>::Type
1188
    intersect(RangeSet::Factory &F, HeadTy Head, SecondTy Second,
1189
30
              RestTy... Tail) {
1190
30
  if (Head) {
1191
12
    return intersect(F, *Head, Second, Tail...);
1192
12
  }
1193
18
  return intersect(F, Second, Tail...);
1194
30
}
RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>::Type (anonymous namespace)::intersect<clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>(clang::ento::RangeSet::Factory&, clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet)
Line
Count
Source
1189
18
              RestTy... Tail) {
1190
18
  if (Head) {
1191
12
    return intersect(F, *Head, Second, Tail...);
1192
12
  }
1193
6
  return intersect(F, Second, Tail...);
1194
18
}
RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>::Type (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>(clang::ento::RangeSet::Factory&, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet)
Line
Count
Source
1189
6
              RestTy... Tail) {
1190
6
  if (Head) {
1191
0
    return intersect(F, *Head, Second, Tail...);
1192
0
  }
1193
6
  return intersect(F, Second, Tail...);
1194
6
}
RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>::Type (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet>(clang::ento::RangeSet::Factory&, llvm::Optional<clang::ento::RangeSet>, clang::ento::RangeSet)
Line
Count
Source
1189
6
              RestTy... Tail) {
1190
6
  if (Head) {
1191
0
    return intersect(F, *Head, Second, Tail...);
1192
0
  }
1193
6
  return intersect(F, Second, Tail...);
1194
6
}
Unexecuted instantiation: 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::RangeSet::Factory&, clang::ento::RangeSet const*, clang::ento::RangeSet const*)
1195
1196
//===----------------------------------------------------------------------===//
1197
//                           Symbolic reasoning logic
1198
//===----------------------------------------------------------------------===//
1199
1200
/// A little component aggregating all of the reasoning we have about
1201
/// the ranges of symbolic expressions.
1202
///
1203
/// Even when we don't know the exact values of the operands, we still
1204
/// can get a pretty good estimate of the result's range.
1205
class SymbolicRangeInferrer
1206
    : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> {
1207
public:
1208
  template <class SourceType>
1209
  static RangeSet inferRange(RangeSet::Factory &F, ProgramStateRef State,
1210
18
                             SourceType Origin) {
1211
18
    SymbolicRangeInferrer Inferrer(F, State);
1212
18
    return Inferrer.infer(Origin);
1213
18
  }
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::inferRange<clang::ento::SymExpr const*>(clang::ento::RangeSet::Factory&, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*)
Line
Count
Source
1210
18
                             SourceType Origin) {
1211
18
    SymbolicRangeInferrer Inferrer(F, State);
1212
18
    return Inferrer.infer(Origin);
1213
18
  }
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::inferRange<(anonymous namespace)::EquivalenceClass>(clang::ento::RangeSet::Factory&, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, (anonymous namespace)::EquivalenceClass)
1214
1215
18
  RangeSet VisitSymExpr(SymbolRef Sym) {
1216
    // If we got to this function, the actual type of the symbolic
1217
    // expression is not supported for advanced inference.
1218
    // In this case, we simply backoff to the default "let's simply
1219
    // infer the range from the expression's type".
1220
18
    return infer(Sym->getType());
1221
18
  }
1222
1223
0
  RangeSet VisitSymIntExpr(const SymIntExpr *Sym) {
1224
0
    return VisitBinaryOperator(Sym);
1225
0
  }
1226
1227
0
  RangeSet VisitIntSymExpr(const IntSymExpr *Sym) {
1228
0
    return VisitBinaryOperator(Sym);
1229
0
  }
1230
1231
0
  RangeSet VisitSymSymExpr(const SymSymExpr *Sym) {
1232
0
    return intersect(
1233
0
        RangeFactory,
1234
        // If Sym is (dis)equality, we might have some information
1235
        // on that in our equality classes data structure.
1236
0
        getRangeForEqualities(Sym),
1237
        // And we should always check what we can get from the operands.
1238
0
        VisitBinaryOperator(Sym));
1239
0
  }
1240
1241
private:
1242
  SymbolicRangeInferrer(RangeSet::Factory &F, ProgramStateRef S)
1243
18
      : ValueFactory(F.getValueFactory()), RangeFactory(F), State(S) {}
1244
1245
  /// Infer range information from the given integer constant.
1246
  ///
1247
  /// It's not a real "inference", but is here for operating with
1248
  /// sub-expressions in a more polymorphic manner.
1249
0
  RangeSet inferAs(const llvm::APSInt &Val, QualType) {
1250
0
    return {RangeFactory, Val};
1251
0
  }
1252
1253
  /// Infer range information from symbol in the context of the given type.
1254
0
  RangeSet inferAs(SymbolRef Sym, QualType DestType) {
1255
0
    QualType ActualType = Sym->getType();
1256
    // Check that we can reason about the symbol at all.
1257
0
    if (ActualType->isIntegralOrEnumerationType() ||
1258
0
        Loc::isLocType(ActualType)) {
1259
0
      return infer(Sym);
1260
0
    }
1261
    // Otherwise, let's simply infer from the destination type.
1262
    // We couldn't figure out nothing else about that expression.
1263
0
    return infer(DestType);
1264
0
  }
1265
1266
18
  RangeSet infer(SymbolRef Sym) {
1267
18
    return intersect(
1268
18
        RangeFactory,
1269
        // Of course, we should take the constraint directly associated with
1270
        // this symbol into consideration.
1271
18
        getConstraint(State, Sym),
1272
        // If Sym is a difference of symbols A - B, then maybe we have range
1273
        // set stored for B - A.
1274
        //
1275
        // If we have range set stored for both A - B and B - A then
1276
        // calculate the effective range set by intersecting the range set
1277
        // for A - B and the negated range set of B - A.
1278
18
        getRangeForNegatedSub(Sym),
1279
        // If Sym is a comparison expression (except <=>),
1280
        // find any other comparisons with the same operands.
1281
        // See function description.
1282
18
        getRangeForComparisonSymbol(Sym),
1283
        // Apart from the Sym itself, we can infer quite a lot if we look
1284
        // into subexpressions of Sym.
1285
18
        Visit(Sym));
1286
18
  }
1287
1288
0
  RangeSet infer(EquivalenceClass Class) {
1289
0
    if (const RangeSet *AssociatedConstraint = getConstraint(State, Class))
1290
0
      return *AssociatedConstraint;
1291
1292
0
    return infer(Class.getType());
1293
0
  }
1294
1295
  /// Infer range information solely from the type.
1296
18
  RangeSet infer(QualType T) {
1297
    // Lazily generate a new RangeSet representing all possible values for the
1298
    // given symbol type.
1299
18
    RangeSet Result(RangeFactory, ValueFactory.getMinValue(T),
1300
18
                    ValueFactory.getMaxValue(T));
1301
1302
    // References are known to be non-zero.
1303
18
    if (T->isReferenceType())
1304
0
      return assumeNonZero(Result, T);
1305
1306
18
    return Result;
1307
18
  }
1308
1309
  template <class BinarySymExprTy>
1310
0
  RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {
1311
    // TODO #1: VisitBinaryOperator implementation might not make a good
1312
    // use of the inferred ranges.  In this case, we might be calculating
1313
    // everything for nothing.  This being said, we should introduce some
1314
    // sort of laziness mechanism here.
1315
    //
1316
    // TODO #2: We didn't go into the nested expressions before, so it
1317
    // might cause us spending much more time doing the inference.
1318
    // This can be a problem for deeply nested expressions that are
1319
    // involved in conditions and get tested continuously.  We definitely
1320
    // need to address this issue and introduce some sort of caching
1321
    // in here.
1322
0
    QualType ResultType = Sym->getType();
1323
0
    return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
1324
0
                               Sym->getOpcode(),
1325
0
                               inferAs(Sym->getRHS(), ResultType), ResultType);
1326
0
  }
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)1> >(clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)1> const*)
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)2> >(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)2> const*)
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)3> >(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)3> const*)
1327
1328
  RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op,
1329
                               RangeSet RHS, QualType T);
1330
1331
  //===----------------------------------------------------------------------===//
1332
  //                         Ranges and operators
1333
  //===----------------------------------------------------------------------===//
1334
1335
  /// Return a rough approximation of the given range set.
1336
  ///
1337
  /// For the range set:
1338
  ///   { [x_0, y_0], [x_1, y_1], ... , [x_N, y_N] }
1339
  /// it will return the range [x_0, y_N].
1340
0
  static Range fillGaps(RangeSet Origin) {
1341
0
    assert(!Origin.isEmpty());
1342
0
    return {Origin.getMinValue(), Origin.getMaxValue()};
1343
0
  }
1344
1345
  /// Try to convert given range into the given type.
1346
  ///
1347
  /// It will return llvm::None only when the trivial conversion is possible.
1348
0
  llvm::Optional<Range> convert(const Range &Origin, APSIntType To) {
1349
0
    if (To.testInRange(Origin.From(), false) != APSIntType::RTR_Within ||
1350
0
        To.testInRange(Origin.To(), false) != APSIntType::RTR_Within) {
1351
0
      return llvm::None;
1352
0
    }
1353
0
    return Range(ValueFactory.Convert(To, Origin.From()),
1354
0
                 ValueFactory.Convert(To, Origin.To()));
1355
0
  }
1356
1357
  template <BinaryOperator::Opcode Op>
1358
0
  RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) {
1359
    // We should propagate information about unfeasbility of one of the
1360
    // operands to the resulting range.
1361
0
    if (LHS.isEmpty() || RHS.isEmpty()) {
1362
0
      return RangeFactory.getEmptySet();
1363
0
    }
1364
1365
0
    Range CoarseLHS = fillGaps(LHS);
1366
0
    Range CoarseRHS = fillGaps(RHS);
1367
1368
0
    APSIntType ResultType = ValueFactory.getAPSIntType(T);
1369
1370
    // We need to convert ranges to the resulting type, so we can compare values
1371
    // and combine them in a meaningful (in terms of the given operation) way.
1372
0
    auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
1373
0
    auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
1374
1375
    // It is hard to reason about ranges when conversion changes
1376
    // borders of the ranges.
1377
0
    if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
1378
0
      return infer(T);
1379
0
    }
1380
1381
0
    return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
1382
0
  }
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)18>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType)
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)16>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType)
Unexecuted instantiation: RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)4>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType)
1383
1384
  template <BinaryOperator::Opcode Op>
1385
  RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) {
1386
    return infer(T);
1387
  }
1388
1389
  /// Return a symmetrical range for the given range and type.
1390
  ///
1391
  /// If T is signed, return the smallest range [-x..x] that covers the original
1392
  /// range, or [-min(T), max(T)] if the aforementioned symmetric range doesn't
1393
  /// exist due to original range covering min(T)).
1394
  ///
1395
  /// If T is unsigned, return the smallest range [0..x] that covers the
1396
  /// original range.
1397
0
  Range getSymmetricalRange(Range Origin, QualType T) {
1398
0
    APSIntType RangeType = ValueFactory.getAPSIntType(T);
1399
1400
0
    if (RangeType.isUnsigned()) {
1401
0
      return Range(ValueFactory.getMinValue(RangeType), Origin.To());
1402
0
    }
1403
1404
0
    if (Origin.From().isMinSignedValue()) {
1405
      // If mini is a minimal signed value, absolute value of it is greater
1406
      // than the maximal signed value.  In order to avoid these
1407
      // complications, we simply return the whole range.
1408
0
      return {ValueFactory.getMinValue(RangeType),
1409
0
              ValueFactory.getMaxValue(RangeType)};
1410
0
    }
1411
1412
    // At this point, we are sure that the type is signed and we can safely
1413
    // use unary - operator.
1414
    //
1415
    // While calculating absolute maximum, we can use the following formula
1416
    // because of these reasons:
1417
    //   * If From >= 0 then To >= From and To >= -From.
1418
    //     AbsMax == To == max(To, -From)
1419
    //   * If To <= 0 then -From >= -To and -From >= From.
1420
    //     AbsMax == -From == max(-From, To)
1421
    //   * Otherwise, From <= 0, To >= 0, and
1422
    //     AbsMax == max(abs(From), abs(To))
1423
0
    llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To());
1424
1425
    // Intersection is guaranteed to be non-empty.
1426
0
    return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};
1427
0
  }
1428
1429
  /// Return a range set subtracting zero from \p Domain.
1430
0
  RangeSet assumeNonZero(RangeSet Domain, QualType T) {
1431
0
    APSIntType IntType = ValueFactory.getAPSIntType(T);
1432
0
    return RangeFactory.deletePoint(Domain, IntType.getZeroValue());
1433
0
  }
1434
1435
18
  Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) {
1436
    // Do not negate if the type cannot be meaningfully negated.
1437
18
    if (!Sym->getType()->isUnsignedIntegerOrEnumerationType() &&
1438
18
        !Sym->getType()->isSignedIntegerOrEnumerationType())
1439
0
      return llvm::None;
1440
1441
18
    const RangeSet *NegatedRange = nullptr;
1442
18
    SymbolManager &SymMgr = State->getSymbolManager();
1443
18
    if (const auto *USE = dyn_cast<UnarySymExpr>(Sym)) {
1444
0
      if (USE->getOpcode() == UO_Minus) {
1445
        // Just get the operand when we negate a symbol that is already negated.
1446
        // -(-a) == a
1447
0
        NegatedRange = getConstraint(State, USE->getOperand());
1448
0
      }
1449
18
    } else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
1450
0
      if (SSE->getOpcode() == BO_Sub) {
1451
0
        QualType T = Sym->getType();
1452
0
        SymbolRef NegatedSym =
1453
0
            SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
1454
0
        NegatedRange = getConstraint(State, NegatedSym);
1455
0
      }
1456
18
    } else {
1457
18
      SymbolRef NegatedSym =
1458
18
          SymMgr.getUnarySymExpr(Sym, UO_Minus, Sym->getType());
1459
18
      NegatedRange = getConstraint(State, NegatedSym);
1460
18
    }
1461
1462
18
    if (NegatedRange)
1463
0
      return RangeFactory.negate(*NegatedRange);
1464
18
    return llvm::None;
1465
18
  }
1466
1467
  // Returns ranges only for binary comparison operators (except <=>)
1468
  // when left and right operands are symbolic values.
1469
  // Finds any other comparisons with the same operands.
1470
  // Then do logical calculations and refuse impossible branches.
1471
  // E.g. (x < y) and (x > y) at the same time are impossible.
1472
  // E.g. (x >= y) and (x != y) at the same time makes (x > y) true only.
1473
  // E.g. (x == y) and (y == x) are just reversed but the same.
1474
  // It covers all possible combinations (see CmpOpTable description).
1475
  // Note that `x` and `y` can also stand for subexpressions,
1476
  // not only for actual symbols.
1477
18
  Optional<RangeSet> getRangeForComparisonSymbol(SymbolRef Sym) {
1478
18
    const auto *SSE = dyn_cast<SymSymExpr>(Sym);
1479
18
    if (!SSE)
1480
18
      return llvm::None;
1481
1482
0
    const BinaryOperatorKind CurrentOP = SSE->getOpcode();
1483
1484
    // We currently do not support <=> (C++20).
1485
0
    if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp))
1486
0
      return llvm::None;
1487
1488
0
    static const OperatorRelationsTable CmpOpTable{};
1489
1490
0
    const SymExpr *LHS = SSE->getLHS();
1491
0
    const SymExpr *RHS = SSE->getRHS();
1492
0
    QualType T = SSE->getType();
1493
1494
0
    SymbolManager &SymMgr = State->getSymbolManager();
1495
1496
    // We use this variable to store the last queried operator (`QueriedOP`)
1497
    // for which the `getCmpOpState` returned with `Unknown`. If there are two
1498
    // different OPs that returned `Unknown` then we have to query the special
1499
    // `UnknownX2` column. We assume that `getCmpOpState(CurrentOP, CurrentOP)`
1500
    // never returns `Unknown`, so `CurrentOP` is a good initial value.
1501
0
    BinaryOperatorKind LastQueriedOpToUnknown = CurrentOP;
1502
1503
    // Loop goes through all of the columns exept the last one ('UnknownX2').
1504
    // We treat `UnknownX2` column separately at the end of the loop body.
1505
0
    for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) {
1506
1507
      // Let's find an expression e.g. (x < y).
1508
0
      BinaryOperatorKind QueriedOP = OperatorRelationsTable::getOpFromIndex(i);
1509
0
      const SymSymExpr *SymSym = SymMgr.getSymSymExpr(LHS, QueriedOP, RHS, T);
1510
0
      const RangeSet *QueriedRangeSet = getConstraint(State, SymSym);
1511
1512
      // If ranges were not previously found,
1513
      // try to find a reversed expression (y > x).
1514
0
      if (!QueriedRangeSet) {
1515
0
        const BinaryOperatorKind ROP =
1516
0
            BinaryOperator::reverseComparisonOp(QueriedOP);
1517
0
        SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T);
1518
0
        QueriedRangeSet = getConstraint(State, SymSym);
1519
0
      }
1520
1521
0
      if (!QueriedRangeSet || QueriedRangeSet->isEmpty())
1522
0
        continue;
1523
1524
0
      const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue();
1525
0
      const bool isInFalseBranch =
1526
0
          ConcreteValue ? (*ConcreteValue == 0) : false;
1527
1528
      // If it is a false branch, we shall be guided by opposite operator,
1529
      // because the table is made assuming we are in the true branch.
1530
      // E.g. when (x <= y) is false, then (x > y) is true.
1531
0
      if (isInFalseBranch)
1532
0
        QueriedOP = BinaryOperator::negateComparisonOp(QueriedOP);
1533
1534
0
      OperatorRelationsTable::TriStateKind BranchState =
1535
0
          CmpOpTable.getCmpOpState(CurrentOP, QueriedOP);
1536
1537
0
      if (BranchState == OperatorRelationsTable::Unknown) {
1538
0
        if (LastQueriedOpToUnknown != CurrentOP &&
1539
0
            LastQueriedOpToUnknown != QueriedOP) {
1540
          // If we got the Unknown state for both different operators.
1541
          // if (x <= y)    // assume true
1542
          //   if (x != y)  // assume true
1543
          //     if (x < y) // would be also true
1544
          // Get a state from `UnknownX2` column.
1545
0
          BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP);
1546
0
        } else {
1547
0
          LastQueriedOpToUnknown = QueriedOP;
1548
0
          continue;
1549
0
        }
1550
0
      }
1551
1552
0
      return (BranchState == OperatorRelationsTable::True) ? getTrueRange(T)
1553
0
                                                           : getFalseRange(T);
1554
0
    }
1555
1556
0
    return llvm::None;
1557
0
  }
1558
1559
0
  Optional<RangeSet> getRangeForEqualities(const SymSymExpr *Sym) {
1560
0
    Optional<bool> Equality = meansEquality(Sym);
1561
1562
0
    if (!Equality)
1563
0
      return llvm::None;
1564
1565
0
    if (Optional<bool> AreEqual =
1566
0
            EquivalenceClass::areEqual(State, Sym->getLHS(), Sym->getRHS())) {
1567
      // Here we cover two cases at once:
1568
      //   * if Sym is equality and its operands are known to be equal -> true
1569
      //   * if Sym is disequality and its operands are disequal -> true
1570
0
      if (*AreEqual == *Equality) {
1571
0
        return getTrueRange(Sym->getType());
1572
0
      }
1573
      // Opposite combinations result in false.
1574
0
      return getFalseRange(Sym->getType());
1575
0
    }
1576
1577
0
    return llvm::None;
1578
0
  }
1579
1580
0
  RangeSet getTrueRange(QualType T) {
1581
0
    RangeSet TypeRange = infer(T);
1582
0
    return assumeNonZero(TypeRange, T);
1583
0
  }
1584
1585
0
  RangeSet getFalseRange(QualType T) {
1586
0
    const llvm::APSInt &Zero = ValueFactory.getValue(0, T);
1587
0
    return RangeSet(RangeFactory, Zero);
1588
0
  }
1589
1590
  BasicValueFactory &ValueFactory;
1591
  RangeSet::Factory &RangeFactory;
1592
  ProgramStateRef State;
1593
};
1594
1595
//===----------------------------------------------------------------------===//
1596
//               Range-based reasoning about symbolic operations
1597
//===----------------------------------------------------------------------===//
1598
1599
template <>
1600
RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_NE>(RangeSet LHS,
1601
                                                           RangeSet RHS,
1602
0
                                                           QualType T) {
1603
1604
  // We must check for empty RangeSets. This gets done via VisitBinaryOperator
1605
  // for other operators, but BO_NE is handled specifically.
1606
0
  if (LHS.isEmpty() || RHS.isEmpty()) {
1607
0
    return RangeFactory.getEmptySet();
1608
0
  }
1609
1610
0
  Range CoarseLHS = fillGaps(LHS);
1611
0
  Range CoarseRHS = fillGaps(RHS);
1612
1613
0
  APSIntType ResultType = ValueFactory.getAPSIntType(T);
1614
1615
0
  auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
1616
0
  auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
1617
1618
0
  if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
1619
0
    return infer(T);
1620
0
  }
1621
1622
  // When both the Ranges are non-overlapping then all possible pairs of (x, y)
1623
  // in ConvertedLHS, ConvertedRHS respectively, will satisfy expression
1624
  // (x != y).
1625
0
  if ((ConvertedCoarseLHS->To() < ConvertedCoarseRHS->From()) ||
1626
0
      (ConvertedCoarseLHS->From() > ConvertedCoarseRHS->To())) {
1627
0
    return getTrueRange(T);
1628
0
  }
1629
1630
  // If both Ranges contain only one Point which is equal, then the expression
1631
  // will always return true.
1632
0
  if (ConvertedCoarseLHS->getConcreteValue() &&
1633
0
      ConvertedCoarseLHS->getConcreteValue() ==
1634
0
          ConvertedCoarseRHS->getConcreteValue()) {
1635
0
    return getFalseRange(T);
1636
0
  }
1637
1638
  // In all other cases, the resulting range cannot be deduced.
1639
0
  return infer(T);
1640
0
}
1641
1642
template <>
1643
RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS,
1644
0
                                                           QualType T) {
1645
0
  APSIntType ResultType = ValueFactory.getAPSIntType(T);
1646
0
  llvm::APSInt Zero = ResultType.getZeroValue();
1647
1648
0
  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1649
0
  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1650
1651
0
  bool IsLHSNegative = LHS.To() < Zero;
1652
0
  bool IsRHSNegative = RHS.To() < Zero;
1653
1654
  // Check if both ranges have the same sign.
1655
0
  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
1656
0
      (IsLHSNegative && IsRHSNegative)) {
1657
    // The result is definitely greater or equal than any of the operands.
1658
0
    const llvm::APSInt &Min = std::max(LHS.From(), RHS.From());
1659
1660
    // We estimate maximal value for positives as the maximal value for the
1661
    // given type.  For negatives, we estimate it with -1 (e.g. 0x11111111).
1662
    //
1663
    // TODO: We basically, limit the resulting range from below, but don't do
1664
    //       anything with the upper bound.
1665
    //
1666
    //       For positive operands, it can be done as follows: for the upper
1667
    //       bound of LHS and RHS we calculate the most significant bit set.
1668
    //       Let's call it the N-th bit.  Then we can estimate the maximal
1669
    //       number to be 2^(N+1)-1, i.e. the number with all the bits up to
1670
    //       the N-th bit set.
1671
0
    const llvm::APSInt &Max = IsLHSNegative
1672
0
                                  ? ValueFactory.getValue(--Zero)
1673
0
                                  : ValueFactory.getMaxValue(ResultType);
1674
1675
0
    return {RangeFactory, ValueFactory.getValue(Min), Max};
1676
0
  }
1677
1678
  // Otherwise, let's check if at least one of the operands is negative.
1679
0
  if (IsLHSNegative || IsRHSNegative) {
1680
    // This means that the result is definitely negative as well.
1681
0
    return {RangeFactory, ValueFactory.getMinValue(ResultType),
1682
0
            ValueFactory.getValue(--Zero)};
1683
0
  }
1684
1685
0
  RangeSet DefaultRange = infer(T);
1686
1687
  // It is pretty hard to reason about operands with different signs
1688
  // (and especially with possibly different signs).  We simply check if it
1689
  // can be zero.  In order to conclude that the result could not be zero,
1690
  // at least one of the operands should be definitely not zero itself.
1691
0
  if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) {
1692
0
    return assumeNonZero(DefaultRange, T);
1693
0
  }
1694
1695
  // Nothing much else to do here.
1696
0
  return DefaultRange;
1697
0
}
1698
1699
template <>
1700
RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS,
1701
                                                            Range RHS,
1702
0
                                                            QualType T) {
1703
0
  APSIntType ResultType = ValueFactory.getAPSIntType(T);
1704
0
  llvm::APSInt Zero = ResultType.getZeroValue();
1705
1706
0
  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1707
0
  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1708
1709
0
  bool IsLHSNegative = LHS.To() < Zero;
1710
0
  bool IsRHSNegative = RHS.To() < Zero;
1711
1712
  // Check if both ranges have the same sign.
1713
0
  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
1714
0
      (IsLHSNegative && IsRHSNegative)) {
1715
    // The result is definitely less or equal than any of the operands.
1716
0
    const llvm::APSInt &Max = std::min(LHS.To(), RHS.To());
1717
1718
    // We conservatively estimate lower bound to be the smallest positive
1719
    // or negative value corresponding to the sign of the operands.
1720
0
    const llvm::APSInt &Min = IsLHSNegative
1721
0
                                  ? ValueFactory.getMinValue(ResultType)
1722
0
                                  : ValueFactory.getValue(Zero);
1723
1724
0
    return {RangeFactory, Min, Max};
1725
0
  }
1726
1727
  // Otherwise, let's check if at least one of the operands is positive.
1728
0
  if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) {
1729
    // This makes result definitely positive.
1730
    //
1731
    // We can also reason about a maximal value by finding the maximal
1732
    // value of the positive operand.
1733
0
    const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To() : RHS.To();
1734
1735
    // The minimal value on the other hand is much harder to reason about.
1736
    // The only thing we know for sure is that the result is positive.
1737
0
    return {RangeFactory, ValueFactory.getValue(Zero),
1738
0
            ValueFactory.getValue(Max)};
1739
0
  }
1740
1741
  // Nothing much else to do here.
1742
0
  return infer(T);
1743
0
}
1744
1745
template <>
1746
RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS,
1747
                                                            Range RHS,
1748
0
                                                            QualType T) {
1749
0
  llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue();
1750
1751
0
  Range ConservativeRange = getSymmetricalRange(RHS, T);
1752
1753
0
  llvm::APSInt Max = ConservativeRange.To();
1754
0
  llvm::APSInt Min = ConservativeRange.From();
1755
1756
0
  if (Max == Zero) {
1757
    // It's an undefined behaviour to divide by 0 and it seems like we know
1758
    // for sure that RHS is 0.  Let's say that the resulting range is
1759
    // simply infeasible for that matter.
1760
0
    return RangeFactory.getEmptySet();
1761
0
  }
1762
1763
  // At this point, our conservative range is closed.  The result, however,
1764
  // couldn't be greater than the RHS' maximal absolute value.  Because of
1765
  // this reason, we turn the range into open (or half-open in case of
1766
  // unsigned integers).
1767
  //
1768
  // While we operate on integer values, an open interval (a, b) can be easily
1769
  // represented by the closed interval [a + 1, b - 1].  And this is exactly
1770
  // what we do next.
1771
  //
1772
  // If we are dealing with unsigned case, we shouldn't move the lower bound.
1773
0
  if (Min.isSigned()) {
1774
0
    ++Min;
1775
0
  }
1776
0
  --Max;
1777
1778
0
  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
1779
0
  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
1780
1781
  // Remainder operator results with negative operands is implementation
1782
  // defined.  Positive cases are much easier to reason about though.
1783
0
  if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) {
1784
    // If maximal value of LHS is less than maximal value of RHS,
1785
    // the result won't get greater than LHS.To().
1786
0
    Max = std::min(LHS.To(), Max);
1787
    // We want to check if it is a situation similar to the following:
1788
    //
1789
    // <------------|---[  LHS  ]--------[  RHS  ]----->
1790
    //  -INF        0                              +INF
1791
    //
1792
    // In this situation, we can conclude that (LHS / RHS) == 0 and
1793
    // (LHS % RHS) == LHS.
1794
0
    Min = LHS.To() < RHS.From() ? LHS.From() : Zero;
1795
0
  }
1796
1797
  // Nevertheless, the symmetrical range for RHS is a conservative estimate
1798
  // for any sign of either LHS, or RHS.
1799
0
  return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)};
1800
0
}
1801
1802
RangeSet SymbolicRangeInferrer::VisitBinaryOperator(RangeSet LHS,
1803
                                                    BinaryOperator::Opcode Op,
1804
0
                                                    RangeSet RHS, QualType T) {
1805
0
  switch (Op) {
1806
0
  case BO_NE:
1807
0
    return VisitBinaryOperator<BO_NE>(LHS, RHS, T);
1808
0
  case BO_Or:
1809
0
    return VisitBinaryOperator<BO_Or>(LHS, RHS, T);
1810
0
  case BO_And:
1811
0
    return VisitBinaryOperator<BO_And>(LHS, RHS, T);
1812
0
  case BO_Rem:
1813
0
    return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);
1814
0
  default:
1815
0
    return infer(T);
1816
0
  }
1817
0
}
1818
1819
//===----------------------------------------------------------------------===//
1820
//                  Constraint manager implementation details
1821
//===----------------------------------------------------------------------===//
1822
1823
class RangeConstraintManager : public RangedConstraintManager {
1824
public:
1825
  RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
1826
1
      : RangedConstraintManager(EE, SVB), F(getBasicVals()) {}
1827
1828
  //===------------------------------------------------------------------===//
1829
  // Implementation for interface from ConstraintManager.
1830
  //===------------------------------------------------------------------===//
1831
1832
  bool haveEqualConstraints(ProgramStateRef S1,
1833
10
                            ProgramStateRef S2) const override {
1834
    // NOTE: ClassMembers are as simple as back pointers for ClassMap,
1835
    //       so comparing constraint ranges and class maps should be
1836
    //       sufficient.
1837
10
    return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() &&
1838
10
           S1->get<ClassMap>() == S2->get<ClassMap>();
1839
10
  }
1840
1841
  bool canReasonAbout(SVal X) const override;
1842
1843
  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
1844
1845
  const llvm::APSInt *getSymVal(ProgramStateRef State,
1846
                                SymbolRef Sym) const override;
1847
1848
  ProgramStateRef removeDeadBindings(ProgramStateRef State,
1849
                                     SymbolReaper &SymReaper) override;
1850
1851
  void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
1852
                 unsigned int Space = 0, bool IsDot = false) const override;
1853
  void printConstraints(raw_ostream &Out, ProgramStateRef State,
1854
                        const char *NL = "\n", unsigned int Space = 0,
1855
                        bool IsDot = false) const;
1856
  void printEquivalenceClasses(raw_ostream &Out, ProgramStateRef State,
1857
                               const char *NL = "\n", unsigned int Space = 0,
1858
                               bool IsDot = false) const;
1859
  void printDisequalities(raw_ostream &Out, ProgramStateRef State,
1860
                          const char *NL = "\n", unsigned int Space = 0,
1861
                          bool IsDot = false) const;
1862
1863
  //===------------------------------------------------------------------===//
1864
  // Implementation for interface from RangedConstraintManager.
1865
  //===------------------------------------------------------------------===//
1866
1867
  ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
1868
                              const llvm::APSInt &V,
1869
                              const llvm::APSInt &Adjustment) override;
1870
1871
  ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
1872
                              const llvm::APSInt &V,
1873
                              const llvm::APSInt &Adjustment) override;
1874
1875
  ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
1876
                              const llvm::APSInt &V,
1877
                              const llvm::APSInt &Adjustment) override;
1878
1879
  ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
1880
                              const llvm::APSInt &V,
1881
                              const llvm::APSInt &Adjustment) override;
1882
1883
  ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
1884
                              const llvm::APSInt &V,
1885
                              const llvm::APSInt &Adjustment) override;
1886
1887
  ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
1888
                              const llvm::APSInt &V,
1889
                              const llvm::APSInt &Adjustment) override;
1890
1891
  ProgramStateRef assumeSymWithinInclusiveRange(
1892
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
1893
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
1894
1895
  ProgramStateRef assumeSymOutsideInclusiveRange(
1896
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
1897
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
1898
1899
private:
1900
  RangeSet::Factory F;
1901
1902
  RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
1903
  RangeSet getRange(ProgramStateRef State, EquivalenceClass Class);
1904
  ProgramStateRef setRange(ProgramStateRef State, SymbolRef Sym,
1905
                           RangeSet Range);
1906
  ProgramStateRef setRange(ProgramStateRef State, EquivalenceClass Class,
1907
                           RangeSet Range);
1908
1909
  RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
1910
                         const llvm::APSInt &Int,
1911
                         const llvm::APSInt &Adjustment);
1912
  RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
1913
                         const llvm::APSInt &Int,
1914
                         const llvm::APSInt &Adjustment);
1915
  RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
1916
                         const llvm::APSInt &Int,
1917
                         const llvm::APSInt &Adjustment);
1918
  RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
1919
                         const llvm::APSInt &Int,
1920
                         const llvm::APSInt &Adjustment);
1921
  RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
1922
                         const llvm::APSInt &Int,
1923
                         const llvm::APSInt &Adjustment);
1924
};
1925
1926
//===----------------------------------------------------------------------===//
1927
//                         Constraint assignment logic
1928
//===----------------------------------------------------------------------===//
1929
1930
/// ConstraintAssignorBase is a small utility class that unifies visitor
1931
/// for ranges with a visitor for constraints (rangeset/range/constant).
1932
///
1933
/// It is designed to have one derived class, but generally it can have more.
1934
/// Derived class can control which types we handle by defining methods of the
1935
/// following form:
1936
///
1937
///   bool handle${SYMBOL}To${CONSTRAINT}(const SYMBOL *Sym,
1938
///                                       CONSTRAINT Constraint);
1939
///
1940
/// where SYMBOL is the type of the symbol (e.g. SymSymExpr, SymbolCast, etc.)
1941
///       CONSTRAINT is the type of constraint (RangeSet/Range/Const)
1942
///       return value signifies whether we should try other handle methods
1943
///          (i.e. false would mean to stop right after calling this method)
1944
template <class Derived> class ConstraintAssignorBase {
1945
public:
1946
  using Const = const llvm::APSInt &;
1947
1948
34
#define DISPATCH(CLASS) return assign##CLASS##Impl(cast<CLASS>(Sym), Constraint)
1949
1950
#define ASSIGN(CLASS, TO, SYM, CONSTRAINT)                                     \
1951
114
  if (!static_cast<Derived *>(this)->assign##CLASS##To##TO(SYM, CONSTRAINT))   \
1952
114
  return false
1953
1954
17
  void assign(SymbolRef Sym, RangeSet Constraint) {
1955
17
    assignImpl(Sym, Constraint);
1956
17
  }
1957
1958
17
  bool assignImpl(SymbolRef Sym, RangeSet Constraint) {
1959
17
    switch (Sym->getKind()) {
1960
0
#define SYMBOL(Id, Parent)                                                     \
1961
17
  case SymExpr::Id##Kind:                                                      \
1962
17
    DISPATCH(Id);
1963
17
#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
1964
17
    }
1965
0
    llvm_unreachable("Unknown SymExpr kind!");
1966
0
  }
1967
1968
#define DEFAULT_ASSIGN(Id)                                                     \
1969
51
  bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) {          \
1970
51
    return true;                                                               \
1971
51
  }                                                                            \
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignUnarySymExprToRangeSet(clang::ento::UnarySymExpr const*, clang::ento::RangeSet)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymExprToRangeSet(clang::ento::SymExpr const*, clang::ento::RangeSet)
Line
Count
Source
1969
17
  bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) {          \
1970
17
    return true;                                                               \
1971
17
  }                                                                            \
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignIntSymExprToRangeSet(clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)1> const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignBinarySymExprToRangeSet(clang::ento::BinarySymExpr const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolCastToRangeSet(clang::ento::SymbolCast const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolConjuredToRangeSet(clang::ento::SymbolConjured const*, clang::ento::RangeSet)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolDataToRangeSet(clang::ento::SymbolData const*, clang::ento::RangeSet)
Line
Count
Source
1969
17
  bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) {          \
1970
17
    return true;                                                               \
1971
17
  }                                                                            \
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolDerivedToRangeSet(clang::ento::SymbolDerived const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolExtentToRangeSet(clang::ento::SymbolExtent const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolMetadataToRangeSet(clang::ento::SymbolMetadata const*, clang::ento::RangeSet)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolRegionValueToRangeSet(clang::ento::SymbolRegionValue const*, clang::ento::RangeSet)
Line
Count
Source
1969
17
  bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) {          \
1970
17
    return true;                                                               \
1971
17
  }                                                                            \
1972
51
  bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignUnarySymExprToRange(clang::ento::UnarySymExpr const*, clang::ento::Range)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymExprToRange(clang::ento::SymExpr const*, clang::ento::Range)
Line
Count
Source
1972
17
  bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignIntSymExprToRange(clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)1> const*, clang::ento::Range)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignBinarySymExprToRange(clang::ento::BinarySymExpr const*, clang::ento::Range)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymIntExprToRange(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)2> const*, clang::ento::Range)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymSymExprToRange(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)3> const*, clang::ento::Range)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolCastToRange(clang::ento::SymbolCast const*, clang::ento::Range)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolConjuredToRange(clang::ento::SymbolConjured const*, clang::ento::Range)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolDataToRange(clang::ento::SymbolData const*, clang::ento::Range)
Line
Count
Source
1972
17
  bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolDerivedToRange(clang::ento::SymbolDerived const*, clang::ento::Range)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolExtentToRange(clang::ento::SymbolExtent const*, clang::ento::Range)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolMetadataToRange(clang::ento::SymbolMetadata const*, clang::ento::Range)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolRegionValueToRange(clang::ento::SymbolRegionValue const*, clang::ento::Range)
Line
Count
Source
1972
17
  bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \
1973
8
  bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignUnarySymExprToConst(clang::ento::UnarySymExpr const*, llvm::APSInt const&)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignIntSymExprToConst(clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)1> const*, llvm::APSInt const&)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignBinarySymExprToConst(clang::ento::BinarySymExpr const*, llvm::APSInt const&)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymIntExprToConst(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)2> const*, llvm::APSInt const&)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymSymExprToConst(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)3> const*, llvm::APSInt const&)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolCastToConst(clang::ento::SymbolCast const*, llvm::APSInt const&)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolConjuredToConst(clang::ento::SymbolConjured const*, llvm::APSInt const&)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolDataToConst(clang::ento::SymbolData const*, llvm::APSInt const&)
Line
Count
Source
1973
4
  bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolDerivedToConst(clang::ento::SymbolDerived const*, llvm::APSInt const&)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolExtentToConst(clang::ento::SymbolExtent const*, llvm::APSInt const&)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolMetadataToConst(clang::ento::SymbolMetadata const*, llvm::APSInt const&)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolRegionValueToConst(clang::ento::SymbolRegionValue const*, llvm::APSInt const&)
Line
Count
Source
1973
4
  bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }
1974
1975
  // When we dispatch for constraint types, we first try to check
1976
  // if the new constraint is the constant and try the corresponding
1977
  // assignor methods.  If it didn't interrupt, we can proceed to the
1978
  // range, and finally to the range set.
1979
#define CONSTRAINT_DISPATCH(Id)                                                \
1980
51
  if (const llvm::APSInt *Const = Constraint.getConcreteValue()) {             \
1981
12
    ASSIGN(Id, Const, Sym, *Const);                                            \
1982
12
  }                                                                            \
1983
51
  if (Constraint.size() == 1) {                                                \
1984
51
    ASSIGN(Id, Range, Sym, *Constraint.begin());                               \
1985
51
  }                                                                            \
1986
51
  ASSIGN(Id, RangeSet, Sym, Constraint)
1987
1988
  // Our internal assign method first tries to call assignor methods for all
1989
  // constraint types that apply.  And if not interrupted, continues with its
1990
  // parent class.
1991
#define SYMBOL(Id, Parent)                                                     \
1992
34
  bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) {                  \
1993
68
    CONSTRAINT_DISPATCH(Id);                                                   \
1994
68
    DISPATCH(Parent);                                                          \
1995
68
  }                                                                            \
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignUnarySymExprImpl(clang::ento::UnarySymExpr const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignIntSymExprImpl(clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)1> const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignBinarySymExprImpl(clang::ento::BinarySymExpr const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymIntExprImpl(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)2> const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymSymExprImpl(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)3> const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolCastImpl(clang::ento::SymbolCast const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolConjuredImpl(clang::ento::SymbolConjured const*, clang::ento::RangeSet)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolDataImpl(clang::ento::SymbolData const*, clang::ento::RangeSet)
Line
Count
Source
1992
17
  bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) {                  \
1993
34
    CONSTRAINT_DISPATCH(Id);                                                   \
1994
34
    DISPATCH(Parent);                                                          \
1995
34
  }                                                                            \
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolDerivedImpl(clang::ento::SymbolDerived const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolExtentImpl(clang::ento::SymbolExtent const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolMetadataImpl(clang::ento::SymbolMetadata const*, clang::ento::RangeSet)
RangeConstraintManager.cpp:(anonymous namespace)::ConstraintAssignorBase<(anonymous namespace)::ConstraintAssignor>::assignSymbolRegionValueImpl(clang::ento::SymbolRegionValue const*, clang::ento::RangeSet)
Line
Count
Source
1992
17
  bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) {                  \
1993
34
    CONSTRAINT_DISPATCH(Id);                                                   \
1994
34
    DISPATCH(Parent);                                                          \
1995
34
  }                                                                            \
1996
  DEFAULT_ASSIGN(Id)
1997
#define ABSTRACT_SYMBOL(Id, Parent) SYMBOL(Id, Parent)
1998
#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
1999
2000
  // Default implementations for the top class that doesn't have parents.
2001
17
  bool assignSymExprImpl(const SymExpr *Sym, RangeSet Constraint) {
2002
34
    CONSTRAINT_DISPATCH(SymExpr);
2003
17
    return true;
2004
34
  }
2005
  DEFAULT_ASSIGN(SymExpr);
2006
2007
#undef DISPATCH
2008
#undef CONSTRAINT_DISPATCH
2009
#undef DEFAULT_ASSIGN
2010
#undef ASSIGN
2011
};
2012
2013
/// A little component aggregating all of the reasoning we have about
2014
/// assigning new constraints to symbols.
2015
///
2016
/// The main purpose of this class is to associate constraints to symbols,
2017
/// and impose additional constraints on other symbols, when we can imply
2018
/// them.
2019
///
2020
/// It has a nice symmetry with SymbolicRangeInferrer.  When the latter
2021
/// can provide more precise ranges by looking into the operands of the
2022
/// expression in question, ConstraintAssignor looks into the operands
2023
/// to see if we can imply more from the new constraint.
2024
class ConstraintAssignor : public ConstraintAssignorBase<ConstraintAssignor> {
2025
public:
2026
  template <class ClassOrSymbol>
2027
  LLVM_NODISCARD static ProgramStateRef
2028
  assign(ProgramStateRef State, SValBuilder &Builder, RangeSet::Factory &F,
2029
18
         ClassOrSymbol CoS, RangeSet NewConstraint) {
2030
18
    if (!State || NewConstraint.isEmpty())
2031
1
      return nullptr;
2032
2033
17
    ConstraintAssignor Assignor{State, Builder, F};
2034
17
    return Assignor.assign(CoS, NewConstraint);
2035
18
  }
2036
2037
  /// Handle expressions like: a % b != 0.
2038
  template <typename SymT>
2039
0
  bool handleRemainderOp(const SymT *Sym, RangeSet Constraint) {
2040
0
    if (Sym->getOpcode() != BO_Rem)
2041
0
      return true;
2042
    // a % b != 0 implies that a != 0.
2043
0
    if (!Constraint.containsZero()) {
2044
0
      SVal SymSVal = Builder.makeSymbolVal(Sym->getLHS());
2045
0
      if (auto NonLocSymSVal = SymSVal.getAs<nonloc::SymbolVal>()) {
2046
0
        State = State->assume(*NonLocSymSVal, true);
2047
0
        if (!State)
2048
0
          return false;
2049
0
      }
2050
0
    }
2051
0
    return true;
2052
0
  }
Unexecuted instantiation: RangeConstraintManager.cpp:bool (anonymous namespace)::ConstraintAssignor::handleRemainderOp<clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)2> >(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)2> const*, clang::ento::RangeSet)
Unexecuted instantiation: RangeConstraintManager.cpp:bool (anonymous namespace)::ConstraintAssignor::handleRemainderOp<clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)3> >(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)3> const*, clang::ento::RangeSet)
2053
2054
  inline bool assignSymExprToConst(const SymExpr *Sym, Const Constraint);
2055
  inline bool assignSymIntExprToRangeSet(const SymIntExpr *Sym,
2056
0
                                         RangeSet Constraint) {
2057
0
    return handleRemainderOp(Sym, Constraint);
2058
0
  }
2059
  inline bool assignSymSymExprToRangeSet(const SymSymExpr *Sym,
2060
                                         RangeSet Constraint);
2061
2062
private:
2063
  ConstraintAssignor(ProgramStateRef State, SValBuilder &Builder,
2064
                     RangeSet::Factory &F)
2065
17
      : State(State), Builder(Builder), RangeFactory(F) {}
2066
  using Base = ConstraintAssignorBase<ConstraintAssignor>;
2067
2068
  /// Base method for handling new constraints for symbols.
2069
17
  LLVM_NODISCARD ProgramStateRef assign(SymbolRef Sym, RangeSet NewConstraint) {
2070
    // All constraints are actually associated with equivalence classes, and
2071
    // that's what we are going to do first.
2072
17
    State = assign(EquivalenceClass::find(State, Sym), NewConstraint);
2073
17
    if (!State)
2074
0
      return nullptr;
2075
2076
    // And after that we can check what other things we can get from this
2077
    // constraint.
2078
17
    Base::assign(Sym, NewConstraint);
2079
17
    return State;
2080
17
  }
2081
2082
  /// Base method for handling new constraints for classes.
2083
  LLVM_NODISCARD ProgramStateRef assign(EquivalenceClass Class,
2084
17
                                        RangeSet NewConstraint) {
2085
    // There is a chance that we might need to update constraints for the
2086
    // classes that are known to be disequal to Class.
2087
    //
2088
    // In order for this to be even possible, the new constraint should
2089
    // be simply a constant because we can't reason about range disequalities.
2090
17
    if (const llvm::APSInt *Point = NewConstraint.getConcreteValue()) {
2091
2092
4
      ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2093
4
      ConstraintRangeTy::Factory &CF = State->get_context<ConstraintRange>();
2094
2095
      // Add new constraint.
2096
4
      Constraints = CF.add(Constraints, Class, NewConstraint);
2097
2098
4
      for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) {
2099
0
        RangeSet UpdatedConstraint = SymbolicRangeInferrer::inferRange(
2100
0
            RangeFactory, State, DisequalClass);
2101
2102
0
        UpdatedConstraint = RangeFactory.deletePoint(UpdatedConstraint, *Point);
2103
2104
        // If we end up with at least one of the disequal classes to be
2105
        // constrained with an empty range-set, the state is infeasible.
2106
0
        if (UpdatedConstraint.isEmpty())
2107
0
          return nullptr;
2108
2109
0
        Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint);
2110
0
      }
2111
4
      assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "
2112
4
                                         "a state with infeasible constraints");
2113
2114
0
      return setConstraints(State, Constraints);
2115
4
    }
2116
2117
13
    return setConstraint(State, Class, NewConstraint);
2118
17
  }
2119
2120
  ProgramStateRef trackDisequality(ProgramStateRef State, SymbolRef LHS,
2121
0
                                   SymbolRef RHS) {
2122
0
    return EquivalenceClass::markDisequal(RangeFactory, State, LHS, RHS);
2123
0
  }
2124
2125
  ProgramStateRef trackEquality(ProgramStateRef State, SymbolRef LHS,
2126
0
                                SymbolRef RHS) {
2127
0
    return EquivalenceClass::merge(RangeFactory, State, LHS, RHS);
2128
0
  }
2129
2130
0
  LLVM_NODISCARD Optional<bool> interpreteAsBool(RangeSet Constraint) {
2131
0
    assert(!Constraint.isEmpty() && "Empty ranges shouldn't get here");
2132
2133
0
    if (Constraint.getConcreteValue())
2134
0
      return !Constraint.getConcreteValue()->isZero();
2135
2136
0
    if (!Constraint.containsZero())
2137
0
      return true;
2138
2139
0
    return llvm::None;
2140
0
  }
2141
2142
  ProgramStateRef State;
2143
  SValBuilder &Builder;
2144
  RangeSet::Factory &RangeFactory;
2145
};
2146
2147
bool ConstraintAssignor::assignSymExprToConst(const SymExpr *Sym,
2148
4
                                              const llvm::APSInt &Constraint) {
2149
4
  llvm::SmallSet<EquivalenceClass, 4> SimplifiedClasses;
2150
  // Iterate over all equivalence classes and try to simplify them.
2151
4
  ClassMembersTy Members = State->get<ClassMembers>();
2152
4
  for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members) {
2153
0
    EquivalenceClass Class = ClassToSymbolSet.first;
2154
0
    State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2155
0
    if (!State)
2156
0
      return false;
2157
0
    SimplifiedClasses.insert(Class);
2158
0
  }
2159
2160
  // Trivial equivalence classes (those that have only one symbol member) are
2161
  // not stored in the State. Thus, we must skim through the constraints as
2162
  // well. And we try to simplify symbols in the constraints.
2163
4
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2164
6
  for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2165
6
    EquivalenceClass Class = ClassConstraint.first;
2166
6
    if (SimplifiedClasses.count(Class)) // Already simplified.
2167
0
      continue;
2168
6
    State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2169
6
    if (!State)
2170
0
      return false;
2171
6
  }
2172
2173
  // We may have trivial equivalence classes in the disequality info as
2174
  // well, and we need to simplify them.
2175
4
  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2176
4
  for (std::pair<EquivalenceClass, ClassSet> DisequalityEntry :
2177
4
       DisequalityInfo) {
2178
0
    EquivalenceClass Class = DisequalityEntry.first;
2179
0
    ClassSet DisequalClasses = DisequalityEntry.second;
2180
0
    State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2181
0
    if (!State)
2182
0
      return false;
2183
0
  }
2184
2185
4
  return true;
2186
4
}
2187
2188
bool ConstraintAssignor::assignSymSymExprToRangeSet(const SymSymExpr *Sym,
2189
0
                                                    RangeSet Constraint) {
2190
0
  if (!handleRemainderOp(Sym, Constraint))
2191
0
    return false;
2192
2193
0
  Optional<bool> ConstraintAsBool = interpreteAsBool(Constraint);
2194
2195
0
  if (!ConstraintAsBool)
2196
0
    return true;
2197
2198
0
  if (Optional<bool> Equality = meansEquality(Sym)) {
2199
    // Here we cover two cases:
2200
    //   * if Sym is equality and the new constraint is true -> Sym's operands
2201
    //     should be marked as equal
2202
    //   * if Sym is disequality and the new constraint is false -> Sym's
2203
    //     operands should be also marked as equal
2204
0
    if (*Equality == *ConstraintAsBool) {
2205
0
      State = trackEquality(State, Sym->getLHS(), Sym->getRHS());
2206
0
    } else {
2207
      // Other combinations leave as with disequal operands.
2208
0
      State = trackDisequality(State, Sym->getLHS(), Sym->getRHS());
2209
0
    }
2210
2211
0
    if (!State)
2212
0
      return false;
2213
0
  }
2214
2215
0
  return true;
2216
0
}
2217
2218
} // end anonymous namespace
2219
2220
std::unique_ptr<ConstraintManager>
2221
ento::CreateRangeConstraintManager(ProgramStateManager &StMgr,
2222
1
                                   ExprEngine *Eng) {
2223
1
  return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
2224
1
}
2225
2226
0
ConstraintMap ento::getConstraintMap(ProgramStateRef State) {
2227
0
  ConstraintMap::Factory &F = State->get_context<ConstraintMap>();
2228
0
  ConstraintMap Result = F.getEmptyMap();
2229
2230
0
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2231
0
  for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2232
0
    EquivalenceClass Class = ClassConstraint.first;
2233
0
    SymbolSet ClassMembers = Class.getClassMembers(State);
2234
0
    assert(!ClassMembers.isEmpty() &&
2235
0
           "Class must always have at least one member!");
2236
2237
0
    SymbolRef Representative = *ClassMembers.begin();
2238
0
    Result = F.add(Result, Representative, ClassConstraint.second);
2239
0
  }
2240
2241
0
  return Result;
2242
0
}
2243
2244
//===----------------------------------------------------------------------===//
2245
//                     EqualityClass implementation details
2246
//===----------------------------------------------------------------------===//
2247
2248
LLVM_DUMP_METHOD void EquivalenceClass::dumpToStream(ProgramStateRef State,
2249
0
                                                     raw_ostream &os) const {
2250
0
  SymbolSet ClassMembers = getClassMembers(State);
2251
0
  for (const SymbolRef &MemberSym : ClassMembers) {
2252
0
    MemberSym->dump();
2253
0
    os << "\n";
2254
0
  }
2255
0
}
2256
2257
inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State,
2258
118
                                               SymbolRef Sym) {
2259
118
  assert(State && "State should not be null");
2260
0
  assert(Sym && "Symbol should not be null");
2261
  // We store far from all Symbol -> Class mappings
2262
118
  if (const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))
2263
0
    return *NontrivialClass;
2264
2265
  // This is a trivial class of Sym.
2266
118
  return Sym;
2267
118
}
2268
2269
inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F,
2270
                                               ProgramStateRef State,
2271
                                               SymbolRef First,
2272
0
                                               SymbolRef Second) {
2273
0
  EquivalenceClass FirstClass = find(State, First);
2274
0
  EquivalenceClass SecondClass = find(State, Second);
2275
2276
0
  return FirstClass.merge(F, State, SecondClass);
2277
0
}
2278
2279
inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F,
2280
                                               ProgramStateRef State,
2281
0
                                               EquivalenceClass Other) {
2282
  // It is already the same class.
2283
0
  if (*this == Other)
2284
0
    return State;
2285
2286
  // FIXME: As of now, we support only equivalence classes of the same type.
2287
  //        This limitation is connected to the lack of explicit casts in
2288
  //        our symbolic expression model.
2289
  //
2290
  //        That means that for `int x` and `char y` we don't distinguish
2291
  //        between these two very different cases:
2292
  //          * `x == y`
2293
  //          * `(char)x == y`
2294
  //
2295
  //        The moment we introduce symbolic casts, this restriction can be
2296
  //        lifted.
2297
0
  if (getType() != Other.getType())
2298
0
    return State;
2299
2300
0
  SymbolSet Members = getClassMembers(State);
2301
0
  SymbolSet OtherMembers = Other.getClassMembers(State);
2302
2303
  // We estimate the size of the class by the height of tree containing
2304
  // its members.  Merging is not a trivial operation, so it's easier to
2305
  // merge the smaller class into the bigger one.
2306
0
  if (Members.getHeight() >= OtherMembers.getHeight()) {
2307
0
    return mergeImpl(F, State, Members, Other, OtherMembers);
2308
0
  } else {
2309
0
    return Other.mergeImpl(F, State, OtherMembers, *this, Members);
2310
0
  }
2311
0
}
2312
2313
inline ProgramStateRef
2314
EquivalenceClass::mergeImpl(RangeSet::Factory &RangeFactory,
2315
                            ProgramStateRef State, SymbolSet MyMembers,
2316
0
                            EquivalenceClass Other, SymbolSet OtherMembers) {
2317
  // Essentially what we try to recreate here is some kind of union-find
2318
  // data structure.  It does have certain limitations due to persistence
2319
  // and the need to remove elements from classes.
2320
  //
2321
  // In this setting, EquialityClass object is the representative of the class
2322
  // or the parent element.  ClassMap is a mapping of class members to their
2323
  // parent. Unlike the union-find structure, they all point directly to the
2324
  // class representative because we don't have an opportunity to actually do
2325
  // path compression when dealing with immutability.  This means that we
2326
  // compress paths every time we do merges.  It also means that we lose
2327
  // the main amortized complexity benefit from the original data structure.
2328
0
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2329
0
  ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2330
2331
  // 1. If the merged classes have any constraints associated with them, we
2332
  //    need to transfer them to the class we have left.
2333
  //
2334
  // Intersection here makes perfect sense because both of these constraints
2335
  // must hold for the whole new class.
2336
0
  if (Optional<RangeSet> NewClassConstraint =
2337
0
          intersect(RangeFactory, getConstraint(State, *this),
2338
0
                    getConstraint(State, Other))) {
2339
    // NOTE: Essentially, NewClassConstraint should NEVER be infeasible because
2340
    //       range inferrer shouldn't generate ranges incompatible with
2341
    //       equivalence classes. However, at the moment, due to imperfections
2342
    //       in the solver, it is possible and the merge function can also
2343
    //       return infeasible states aka null states.
2344
0
    if (NewClassConstraint->isEmpty())
2345
      // Infeasible state
2346
0
      return nullptr;
2347
2348
    // No need in tracking constraints of a now-dissolved class.
2349
0
    Constraints = CRF.remove(Constraints, Other);
2350
    // Assign new constraints for this class.
2351
0
    Constraints = CRF.add(Constraints, *this, *NewClassConstraint);
2352
2353
0
    assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "
2354
0
                                       "a state with infeasible constraints");
2355
2356
0
    State = State->set<ConstraintRange>(Constraints);
2357
0
  }
2358
2359
  // 2. Get ALL equivalence-related maps
2360
0
  ClassMapTy Classes = State->get<ClassMap>();
2361
0
  ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2362
2363
0
  ClassMembersTy Members = State->get<ClassMembers>();
2364
0
  ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();
2365
2366
0
  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2367
0
  DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>();
2368
2369
0
  ClassSet::Factory &CF = State->get_context<ClassSet>();
2370
0
  SymbolSet::Factory &F = getMembersFactory(State);
2371
2372
  // 2. Merge members of the Other class into the current class.
2373
0
  SymbolSet NewClassMembers = MyMembers;
2374
0
  for (SymbolRef Sym : OtherMembers) {
2375
0
    NewClassMembers = F.add(NewClassMembers, Sym);
2376
    // *this is now the class for all these new symbols.
2377
0
    Classes = CMF.add(Classes, Sym, *this);
2378
0
  }
2379
2380
  // 3. Adjust member mapping.
2381
  //
2382
  // No need in tracking members of a now-dissolved class.
2383
0
  Members = MF.remove(Members, Other);
2384
  // Now only the current class is mapped to all the symbols.
2385
0
  Members = MF.add(Members, *this, NewClassMembers);
2386
2387
  // 4. Update disequality relations
2388
0
  ClassSet DisequalToOther = Other.getDisequalClasses(DisequalityInfo, CF);
2389
  // We are about to merge two classes but they are already known to be
2390
  // non-equal. This is a contradiction.
2391
0
  if (DisequalToOther.contains(*this))
2392
0
    return nullptr;
2393
2394
0
  if (!DisequalToOther.isEmpty()) {
2395
0
    ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo, CF);
2396
0
    DisequalityInfo = DF.remove(DisequalityInfo, Other);
2397
2398
0
    for (EquivalenceClass DisequalClass : DisequalToOther) {
2399
0
      DisequalToThis = CF.add(DisequalToThis, DisequalClass);
2400
2401
      // Disequality is a symmetric relation meaning that if
2402
      // DisequalToOther not null then the set for DisequalClass is not
2403
      // empty and has at least Other.
2404
0
      ClassSet OriginalSetLinkedToOther =
2405
0
          *DisequalityInfo.lookup(DisequalClass);
2406
2407
      // Other will be eliminated and we should replace it with the bigger
2408
      // united class.
2409
0
      ClassSet NewSet = CF.remove(OriginalSetLinkedToOther, Other);
2410
0
      NewSet = CF.add(NewSet, *this);
2411
2412
0
      DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);
2413
0
    }
2414
2415
0
    DisequalityInfo = DF.add(DisequalityInfo, *this, DisequalToThis);
2416
0
    State = State->set<DisequalityMap>(DisequalityInfo);
2417
0
  }
2418
2419
  // 5. Update the state
2420
0
  State = State->set<ClassMap>(Classes);
2421
0
  State = State->set<ClassMembers>(Members);
2422
2423
0
  return State;
2424
0
}
2425
2426
inline SymbolSet::Factory &
2427
6
EquivalenceClass::getMembersFactory(ProgramStateRef State) {
2428
6
  return State->get_context<SymbolSet>();
2429
6
}
2430
2431
6
SymbolSet EquivalenceClass::getClassMembers(ProgramStateRef State) const {
2432
6
  if (const SymbolSet *Members = State->get<ClassMembers>(*this))
2433
0
    return *Members;
2434
2435
  // This class is trivial, so we need to construct a set
2436
  // with just that one symbol from the class.
2437
6
  SymbolSet::Factory &F = getMembersFactory(State);
2438
6
  return F.add(F.getEmptySet(), getRepresentativeSymbol());
2439
6
}
2440
2441
31
bool EquivalenceClass::isTrivial(ProgramStateRef State) const {
2442
31
  return State->get<ClassMembers>(*this) == nullptr;
2443
31
}
2444
2445
bool EquivalenceClass::isTriviallyDead(ProgramStateRef State,
2446
31
                                       SymbolReaper &Reaper) const {
2447
31
  return isTrivial(State) && Reaper.isDead(getRepresentativeSymbol());
2448
31
}
2449
2450
inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF,
2451
                                                      ProgramStateRef State,
2452
                                                      SymbolRef First,
2453
0
                                                      SymbolRef Second) {
2454
0
  return markDisequal(RF, State, find(State, First), find(State, Second));
2455
0
}
2456
2457
inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF,
2458
                                                      ProgramStateRef State,
2459
                                                      EquivalenceClass First,
2460
0
                                                      EquivalenceClass Second) {
2461
0
  return First.markDisequal(RF, State, Second);
2462
0
}
2463
2464
inline ProgramStateRef
2465
EquivalenceClass::markDisequal(RangeSet::Factory &RF, ProgramStateRef State,
2466
0
                               EquivalenceClass Other) const {
2467
  // If we know that two classes are equal, we can only produce an infeasible
2468
  // state.
2469
0
  if (*this == Other) {
2470
0
    return nullptr;
2471
0
  }
2472
2473
0
  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2474
0
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2475
2476
  // Disequality is a symmetric relation, so if we mark A as disequal to B,
2477
  // we should also mark B as disequalt to A.
2478
0
  if (!addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, *this,
2479
0
                            Other) ||
2480
0
      !addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, Other,
2481
0
                            *this))
2482
0
    return nullptr;
2483
2484
0
  assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "
2485
0
                                     "a state with infeasible constraints");
2486
2487
0
  State = State->set<DisequalityMap>(DisequalityInfo);
2488
0
  State = State->set<ConstraintRange>(Constraints);
2489
2490
0
  return State;
2491
0
}
2492
2493
inline bool EquivalenceClass::addToDisequalityInfo(
2494
    DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
2495
    RangeSet::Factory &RF, ProgramStateRef State, EquivalenceClass First,
2496
0
    EquivalenceClass Second) {
2497
2498
  // 1. Get all of the required factories.
2499
0
  DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>();
2500
0
  ClassSet::Factory &CF = State->get_context<ClassSet>();
2501
0
  ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2502
2503
  // 2. Add Second to the set of classes disequal to First.
2504
0
  const ClassSet *CurrentSet = Info.lookup(First);
2505
0
  ClassSet NewSet = CurrentSet ? *CurrentSet : CF.getEmptySet();
2506
0
  NewSet = CF.add(NewSet, Second);
2507
2508
0
  Info = F.add(Info, First, NewSet);
2509
2510
  // 3. If Second is known to be a constant, we can delete this point
2511
  //    from the constraint asociated with First.
2512
  //
2513
  //    So, if Second == 10, it means that First != 10.
2514
  //    At the same time, the same logic does not apply to ranges.
2515
0
  if (const RangeSet *SecondConstraint = Constraints.lookup(Second))
2516
0
    if (const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {
2517
2518
0
      RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
2519
0
          RF, State, First.getRepresentativeSymbol());
2520
2521
0
      FirstConstraint = RF.deletePoint(FirstConstraint, *Point);
2522
2523
      // If the First class is about to be constrained with an empty
2524
      // range-set, the state is infeasible.
2525
0
      if (FirstConstraint.isEmpty())
2526
0
        return false;
2527
2528
0
      Constraints = CRF.add(Constraints, First, FirstConstraint);
2529
0
    }
2530
2531
0
  return true;
2532
0
}
2533
2534
inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State,
2535
                                                 SymbolRef FirstSym,
2536
0
                                                 SymbolRef SecondSym) {
2537
0
  return EquivalenceClass::areEqual(State, find(State, FirstSym),
2538
0
                                    find(State, SecondSym));
2539
0
}
2540
2541
inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State,
2542
                                                 EquivalenceClass First,
2543
0
                                                 EquivalenceClass Second) {
2544
  // The same equivalence class => symbols are equal.
2545
0
  if (First == Second)
2546
0
    return true;
2547
2548
  // Let's check if we know anything about these two classes being not equal to
2549
  // each other.
2550
0
  ClassSet DisequalToFirst = First.getDisequalClasses(State);
2551
0
  if (DisequalToFirst.contains(Second))
2552
0
    return false;
2553
2554
  // It is not clear.
2555
0
  return llvm::None;
2556
0
}
2557
2558
LLVM_NODISCARD ProgramStateRef
2559
0
EquivalenceClass::removeMember(ProgramStateRef State, const SymbolRef Old) {
2560
2561
0
  SymbolSet ClsMembers = getClassMembers(State);
2562
0
  assert(ClsMembers.contains(Old));
2563
2564
  // Remove `Old`'s Class->Sym relation.
2565
0
  SymbolSet::Factory &F = getMembersFactory(State);
2566
0
  ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2567
0
  ClsMembers = F.remove(ClsMembers, Old);
2568
  // Ensure another precondition of the removeMember function (we can check
2569
  // this only with isEmpty, thus we have to do the remove first).
2570
0
  assert(!ClsMembers.isEmpty() &&
2571
0
         "Class should have had at least two members before member removal");
2572
  // Overwrite the existing members assigned to this class.
2573
0
  ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2574
0
  ClassMembersMap = EMFactory.add(ClassMembersMap, *this, ClsMembers);
2575
0
  State = State->set<ClassMembers>(ClassMembersMap);
2576
2577
  // Remove `Old`'s Sym->Class relation.
2578
0
  ClassMapTy Classes = State->get<ClassMap>();
2579
0
  ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2580
0
  Classes = CMF.remove(Classes, Old);
2581
0
  State = State->set<ClassMap>(Classes);
2582
2583
0
  return State;
2584
0
}
2585
2586
// Re-evaluate an SVal with top-level `State->assume` logic.
2587
LLVM_NODISCARD ProgramStateRef reAssume(ProgramStateRef State,
2588
                                        const RangeSet *Constraint,
2589
0
                                        SVal TheValue) {
2590
0
  if (!Constraint)
2591
0
    return State;
2592
2593
0
  const auto DefinedVal = TheValue.castAs<DefinedSVal>();
2594
2595
  // If the SVal is 0, we can simply interpret that as `false`.
2596
0
  if (Constraint->encodesFalseRange())
2597
0
    return State->assume(DefinedVal, false);
2598
2599
  // If the constraint does not encode 0 then we can interpret that as `true`
2600
  // AND as a Range(Set).
2601
0
  if (Constraint->encodesTrueRange()) {
2602
0
    State = State->assume(DefinedVal, true);
2603
0
    if (!State)
2604
0
      return nullptr;
2605
    // Fall through, re-assume based on the range values as well.
2606
0
  }
2607
  // Overestimate the individual Ranges with the RangeSet' lowest and
2608
  // highest values.
2609
0
  return State->assumeInclusiveRange(DefinedVal, Constraint->getMinValue(),
2610
0
                                     Constraint->getMaxValue(), true);
2611
0
}
2612
2613
// Iterate over all symbols and try to simplify them. Once a symbol is
2614
// simplified then we check if we can merge the simplified symbol's equivalence
2615
// class to this class. This way, we simplify not just the symbols but the
2616
// classes as well: we strive to keep the number of the classes to be the
2617
// absolute minimum.
2618
LLVM_NODISCARD ProgramStateRef
2619
EquivalenceClass::simplify(SValBuilder &SVB, RangeSet::Factory &F,
2620
6
                           ProgramStateRef State, EquivalenceClass Class) {
2621
6
  SymbolSet ClassMembers = Class.getClassMembers(State);
2622
6
  for (const SymbolRef &MemberSym : ClassMembers) {
2623
2624
6
    const SVal SimplifiedMemberVal = simplifyToSVal(State, MemberSym);
2625
6
    const SymbolRef SimplifiedMemberSym = SimplifiedMemberVal.getAsSymbol();
2626
2627
    // The symbol is collapsed to a constant, check if the current State is
2628
    // still feasible.
2629
6
    if (const auto CI = SimplifiedMemberVal.getAs<nonloc::ConcreteInt>()) {
2630
6
      const llvm::APSInt &SV = CI->getValue();
2631
6
      const RangeSet *ClassConstraint = getConstraint(State, Class);
2632
      // We have found a contradiction.
2633
6
      if (ClassConstraint && !ClassConstraint->contains(SV))
2634
0
        return nullptr;
2635
6
    }
2636
2637
6
    if (SimplifiedMemberSym && MemberSym != SimplifiedMemberSym) {
2638
      // The simplified symbol should be the member of the original Class,
2639
      // however, it might be in another existing class at the moment. We
2640
      // have to merge these classes.
2641
0
      ProgramStateRef OldState = State;
2642
0
      State = merge(F, State, MemberSym, SimplifiedMemberSym);
2643
0
      if (!State)
2644
0
        return nullptr;
2645
      // No state change, no merge happened actually.
2646
0
      if (OldState == State)
2647
0
        continue;
2648
2649
0
      assert(find(State, MemberSym) == find(State, SimplifiedMemberSym));
2650
      // Remove the old and more complex symbol.
2651
0
      State = find(State, MemberSym).removeMember(State, MemberSym);
2652
2653
      // Query the class constraint again b/c that may have changed during the
2654
      // merge above.
2655
0
      const RangeSet *ClassConstraint = getConstraint(State, Class);
2656
2657
      // Re-evaluate an SVal with top-level `State->assume`, this ignites
2658
      // a RECURSIVE algorithm that will reach a FIXPOINT.
2659
      //
2660
      // About performance and complexity: Let us assume that in a State we
2661
      // have N non-trivial equivalence classes and that all constraints and
2662
      // disequality info is related to non-trivial classes. In the worst case,
2663
      // we can simplify only one symbol of one class in each iteration. The
2664
      // number of symbols in one class cannot grow b/c we replace the old
2665
      // symbol with the simplified one. Also, the number of the equivalence
2666
      // classes can decrease only, b/c the algorithm does a merge operation
2667
      // optionally. We need N iterations in this case to reach the fixpoint.
2668
      // Thus, the steps needed to be done in the worst case is proportional to
2669
      // N*N.
2670
      //
2671
      // This worst case scenario can be extended to that case when we have
2672
      // trivial classes in the constraints and in the disequality map. This
2673
      // case can be reduced to the case with a State where there are only
2674
      // non-trivial classes. This is because a merge operation on two trivial
2675
      // classes results in one non-trivial class.
2676
0
      State = reAssume(State, ClassConstraint, SimplifiedMemberVal);
2677
0
      if (!State)
2678
0
        return nullptr;
2679
0
    }
2680
6
  }
2681
6
  return State;
2682
6
}
2683
2684
inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State,
2685
0
                                                     SymbolRef Sym) {
2686
0
  return find(State, Sym).getDisequalClasses(State);
2687
0
}
2688
2689
inline ClassSet
2690
4
EquivalenceClass::getDisequalClasses(ProgramStateRef State) const {
2691
4
  return getDisequalClasses(State->get<DisequalityMap>(),
2692
4
                            State->get_context<ClassSet>());
2693
4
}
2694
2695
inline ClassSet
2696
EquivalenceClass::getDisequalClasses(DisequalityMapTy Map,
2697
17
                                     ClassSet::Factory &Factory) const {
2698
17
  if (const ClassSet *DisequalClasses = Map.lookup(*this))
2699
0
    return *DisequalClasses;
2700
2701
17
  return Factory.getEmptySet();
2702
17
}
2703
2704
23
bool EquivalenceClass::isClassDataConsistent(ProgramStateRef State) {
2705
23
  ClassMembersTy Members = State->get<ClassMembers>();
2706
2707
23
  for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) {
2708
0
    for (SymbolRef Member : ClassMembersPair.second) {
2709
      // Every member of the class should have a mapping back to the class.
2710
0
      if (find(State, Member) == ClassMembersPair.first) {
2711
0
        continue;
2712
0
      }
2713
2714
0
      return false;
2715
0
    }
2716
0
  }
2717
2718
23
  DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2719
23
  for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) {
2720
0
    EquivalenceClass Class = DisequalityInfo.first;
2721
0
    ClassSet DisequalClasses = DisequalityInfo.second;
2722
2723
    // There is no use in keeping empty sets in the map.
2724
0
    if (DisequalClasses.isEmpty())
2725
0
      return false;
2726
2727
    // Disequality is symmetrical, i.e. for every Class A and B that A != B,
2728
    // B != A should also be true.
2729
0
    for (EquivalenceClass DisequalClass : DisequalClasses) {
2730
0
      const ClassSet *DisequalToDisequalClasses =
2731
0
          Disequalities.lookup(DisequalClass);
2732
2733
      // It should be a set of at least one element: Class
2734
0
      if (!DisequalToDisequalClasses ||
2735
0
          !DisequalToDisequalClasses->contains(Class))
2736
0
        return false;
2737
0
    }
2738
0
  }
2739
2740
23
  return true;
2741
23
}
2742
2743
//===----------------------------------------------------------------------===//
2744
//                    RangeConstraintManager implementation
2745
//===----------------------------------------------------------------------===//
2746
2747
56
bool RangeConstraintManager::canReasonAbout(SVal X) const {
2748
56
  Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
2749
56
  if (SymVal && SymVal->isExpression()) {
2750
18
    const SymExpr *SE = SymVal->getSymbol();
2751
2752
18
    if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
2753
18
      switch (SIE->getOpcode()) {
2754
      // We don't reason yet about bitwise-constraints on symbolic values.
2755
0
      case BO_And:
2756
0
      case BO_Or:
2757
0
      case BO_Xor:
2758
0
        return false;
2759
      // We don't reason yet about these arithmetic constraints on
2760
      // symbolic values.
2761
0
      case BO_Mul:
2762
0
      case BO_Div:
2763
0
      case BO_Rem:
2764
0
      case BO_Shl:
2765
0
      case BO_Shr:
2766
0
        return false;
2767
      // All other cases.
2768
18
      default:
2769
18
        return true;
2770
18
      }
2771
18
    }
2772
2773
0
    if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
2774
      // FIXME: Handle <=> here.
2775
0
      if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
2776
0
          BinaryOperator::isRelationalOp(SSE->getOpcode())) {
2777
        // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
2778
        // We've recently started producing Loc <> NonLoc comparisons (that
2779
        // result from casts of one of the operands between eg. intptr_t and
2780
        // void *), but we can't reason about them yet.
2781
0
        if (Loc::isLocType(SSE->getLHS()->getType())) {
2782
0
          return Loc::isLocType(SSE->getRHS()->getType());
2783
0
        }
2784
0
      }
2785
0
    }
2786
2787
0
    return false;
2788
0
  }
2789
2790
38
  return true;
2791
56
}
2792
2793
ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
2794
0
                                                    SymbolRef Sym) {
2795
0
  const RangeSet *Ranges = getConstraint(State, Sym);
2796
2797
  // If we don't have any information about this symbol, it's underconstrained.
2798
0
  if (!Ranges)
2799
0
    return ConditionTruthVal();
2800
2801
  // If we have a concrete value, see if it's zero.
2802
0
  if (const llvm::APSInt *Value = Ranges->getConcreteValue())
2803
0
    return *Value == 0;
2804
2805
0
  BasicValueFactory &BV = getBasicVals();
2806
0
  APSIntType IntType = BV.getAPSIntType(Sym->getType());
2807
0
  llvm::APSInt Zero = IntType.getZeroValue();
2808
2809
  // Check if zero is in the set of possible values.
2810
0
  if (!Ranges->contains(Zero))
2811
0
    return false;
2812
2813
  // Zero is a possible value, but it is not the /only/ possible value.
2814
0
  return ConditionTruthVal();
2815
0
}
2816
2817
const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
2818
65
                                                      SymbolRef Sym) const {
2819
65
  const RangeSet *T = getConstraint(St, Sym);
2820
65
  return T ? T->getConcreteValue() : nullptr;
2821
65
}
2822
2823
//===----------------------------------------------------------------------===//
2824
//                Remove dead symbols from existing constraints
2825
//===----------------------------------------------------------------------===//
2826
2827
/// Scan all symbols referenced by the constraints. If the symbol is not alive
2828
/// as marked in LSymbols, mark it as dead in DSymbols.
2829
ProgramStateRef
2830
RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
2831
23
                                           SymbolReaper &SymReaper) {
2832
23
  ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2833
23
  ClassMembersTy NewClassMembersMap = ClassMembersMap;
2834
23
  ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2835
23
  SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>();
2836
2837
23
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2838
23
  ConstraintRangeTy NewConstraints = Constraints;
2839
23
  ConstraintRangeTy::Factory &ConstraintFactory =
2840
23
      State->get_context<ConstraintRange>();
2841
2842
23
  ClassMapTy Map = State->get<ClassMap>();
2843
23
  ClassMapTy NewMap = Map;
2844
23
  ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();
2845
2846
23
  DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2847
23
  DisequalityMapTy::Factory &DisequalityFactory =
2848
23
      State->get_context<DisequalityMap>();
2849
23
  ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();
2850
2851
23
  bool ClassMapChanged = false;
2852
23
  bool MembersMapChanged = false;
2853
23
  bool ConstraintMapChanged = false;
2854
23
  bool DisequalitiesChanged = false;
2855
2856
23
  auto removeDeadClass = [&](EquivalenceClass Class) {
2857
    // Remove associated constraint ranges.
2858
13
    Constraints = ConstraintFactory.remove(Constraints, Class);
2859
13
    ConstraintMapChanged = true;
2860
2861
    // Update disequality information to not hold any information on the
2862
    // removed class.
2863
13
    ClassSet DisequalClasses =
2864
13
        Class.getDisequalClasses(Disequalities, ClassSetFactory);
2865
13
    if (!DisequalClasses.isEmpty()) {
2866
0
      for (EquivalenceClass DisequalClass : DisequalClasses) {
2867
0
        ClassSet DisequalToDisequalSet =
2868
0
            DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory);
2869
        // DisequalToDisequalSet is guaranteed to be non-empty for consistent
2870
        // disequality info.
2871
0
        assert(!DisequalToDisequalSet.isEmpty());
2872
0
        ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet, Class);
2873
2874
        // No need in keeping an empty set.
2875
0
        if (NewSet.isEmpty()) {
2876
0
          Disequalities =
2877
0
              DisequalityFactory.remove(Disequalities, DisequalClass);
2878
0
        } else {
2879
0
          Disequalities =
2880
0
              DisequalityFactory.add(Disequalities, DisequalClass, NewSet);
2881
0
        }
2882
0
      }
2883
      // Remove the data for the class
2884
0
      Disequalities = DisequalityFactory.remove(Disequalities, Class);
2885
0
      DisequalitiesChanged = true;
2886
0
    }
2887
13
  };
2888
2889
  // 1. Let's see if dead symbols are trivial and have associated constraints.
2890
23
  for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :
2891
31
       Constraints) {
2892
31
    EquivalenceClass Class = ClassConstraintPair.first;
2893
31
    if (Class.isTriviallyDead(State, SymReaper)) {
2894
      // If this class is trivial, we can remove its constraints right away.
2895
13
      removeDeadClass(Class);
2896
13
    }
2897
31
  }
2898
2899
  // 2. We don't need to track classes for dead symbols.
2900
23
  for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {
2901
0
    SymbolRef Sym = SymbolClassPair.first;
2902
2903
0
    if (SymReaper.isDead(Sym)) {
2904
0
      ClassMapChanged = true;
2905
0
      NewMap = ClassFactory.remove(NewMap, Sym);
2906
0
    }
2907
0
  }
2908
2909
  // 3. Remove dead members from classes and remove dead non-trivial classes
2910
  //    and their constraints.
2911
23
  for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :
2912
23
       ClassMembersMap) {
2913
0
    EquivalenceClass Class = ClassMembersPair.first;
2914
0
    SymbolSet LiveMembers = ClassMembersPair.second;
2915
0
    bool MembersChanged = false;
2916
2917
0
    for (SymbolRef Member : ClassMembersPair.second) {
2918
0
      if (SymReaper.isDead(Member)) {
2919
0
        MembersChanged = true;
2920
0
        LiveMembers = SetFactory.remove(LiveMembers, Member);
2921
0
      }
2922
0
    }
2923
2924
    // Check if the class changed.
2925
0
    if (!MembersChanged)
2926
0
      continue;
2927
2928
0
    MembersMapChanged = true;
2929
2930
0
    if (LiveMembers.isEmpty()) {
2931
      // The class is dead now, we need to wipe it out of the members map...
2932
0
      NewClassMembersMap = EMFactory.remove(NewClassMembersMap, Class);
2933
2934
      // ...and remove all of its constraints.
2935
0
      removeDeadClass(Class);
2936
0
    } else {
2937
      // We need to change the members associated with the class.
2938
0
      NewClassMembersMap =
2939
0
          EMFactory.add(NewClassMembersMap, Class, LiveMembers);
2940
0
    }
2941
0
  }
2942
2943
  // 4. Update the state with new maps.
2944
  //
2945
  // Here we try to be humble and update a map only if it really changed.
2946
23
  if (ClassMapChanged)
2947
0
    State = State->set<ClassMap>(NewMap);
2948
2949
23
  if (MembersMapChanged)
2950
0
    State = State->set<ClassMembers>(NewClassMembersMap);
2951
2952
23
  if (ConstraintMapChanged)
2953
10
    State = State->set<ConstraintRange>(Constraints);
2954
2955
23
  if (DisequalitiesChanged)
2956
0
    State = State->set<DisequalityMap>(Disequalities);
2957
2958
23
  assert(EquivalenceClass::isClassDataConsistent(State));
2959
2960
0
  return State;
2961
23
}
2962
2963
RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
2964
18
                                          SymbolRef Sym) {
2965
18
  return SymbolicRangeInferrer::inferRange(F, State, Sym);
2966
18
}
2967
2968
ProgramStateRef RangeConstraintManager::setRange(ProgramStateRef State,
2969
                                                 SymbolRef Sym,
2970
18
                                                 RangeSet Range) {
2971
18
  return ConstraintAssignor::assign(State, getSValBuilder(), F, Sym, Range);
2972
18
}
2973
2974
//===------------------------------------------------------------------------===
2975
// assumeSymX methods: protected interface for RangeConstraintManager.
2976
//===------------------------------------------------------------------------===/
2977
2978
// The syntax for ranges below is mathematical, using [x, y] for closed ranges
2979
// and (x, y) for open ranges. These ranges are modular, corresponding with
2980
// a common treatment of C integer overflow. This means that these methods
2981
// do not have to worry about overflow; RangeSet::Intersect can handle such a
2982
// "wraparound" range.
2983
// As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
2984
// UINT_MAX, 0, 1, and 2.
2985
2986
ProgramStateRef
2987
RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
2988
                                    const llvm::APSInt &Int,
2989
0
                                    const llvm::APSInt &Adjustment) {
2990
  // Before we do any real work, see if the value can even show up.
2991
0
  APSIntType AdjustmentType(Adjustment);
2992
0
  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
2993
0
    return St;
2994
2995
0
  llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
2996
0
  RangeSet New = getRange(St, Sym);
2997
0
  New = F.deletePoint(New, Point);
2998
2999
0
  return setRange(St, Sym, New);
3000
0
}
3001
3002
ProgramStateRef
3003
RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
3004
                                    const llvm::APSInt &Int,
3005
0
                                    const llvm::APSInt &Adjustment) {
3006
  // Before we do any real work, see if the value can even show up.
3007
0
  APSIntType AdjustmentType(Adjustment);
3008
0
  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
3009
0
    return nullptr;
3010
3011
  // [Int-Adjustment, Int-Adjustment]
3012
0
  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
3013
0
  RangeSet New = getRange(St, Sym);
3014
0
  New = F.intersect(New, AdjInt);
3015
3016
0
  return setRange(St, Sym, New);
3017
0
}
3018
3019
RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
3020
                                               SymbolRef Sym,
3021
                                               const llvm::APSInt &Int,
3022
4
                                               const llvm::APSInt &Adjustment) {
3023
  // Before we do any real work, see if the value can even show up.
3024
4
  APSIntType AdjustmentType(Adjustment);
3025
4
  switch (AdjustmentType.testInRange(Int, true)) {
3026
0
  case APSIntType::RTR_Below:
3027
0
    return F.getEmptySet();
3028
4
  case APSIntType::RTR_Within:
3029
4
    break;
3030
0
  case APSIntType::RTR_Above:
3031
0
    return getRange(St, Sym);
3032
4
  }
3033
3034
  // Special case for Int == Min. This is always false.
3035
4
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3036
4
  llvm::APSInt Min = AdjustmentType.getMinValue();
3037
4
  if (ComparisonVal == Min)
3038
0
    return F.getEmptySet();
3039
3040
4
  llvm::APSInt Lower = Min - Adjustment;
3041
4
  llvm::APSInt Upper = ComparisonVal - Adjustment;
3042
4
  --Upper;
3043
3044
4
  RangeSet Result = getRange(St, Sym);
3045
4
  return F.intersect(Result, Lower, Upper);
3046
4
}
3047
3048
ProgramStateRef
3049
RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
3050
                                    const llvm::APSInt &Int,
3051
4
                                    const llvm::APSInt &Adjustment) {
3052
4
  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
3053
4
  return setRange(St, Sym, New);
3054
4
}
3055
3056
RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
3057
                                               SymbolRef Sym,
3058
                                               const llvm::APSInt &Int,
3059
5
                                               const llvm::APSInt &Adjustment) {
3060
  // Before we do any real work, see if the value can even show up.
3061
5
  APSIntType AdjustmentType(Adjustment);
3062
5
  switch (AdjustmentType.testInRange(Int, true)) {
3063
0
  case APSIntType::RTR_Below:
3064
0
    return getRange(St, Sym);
3065
5
  case APSIntType::RTR_Within:
3066
5
    break;
3067
0
  case APSIntType::RTR_Above:
3068
0
    return F.getEmptySet();
3069
5
  }
3070
3071
  // Special case for Int == Max. This is always false.
3072
5
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3073
5
  llvm::APSInt Max = AdjustmentType.getMaxValue();
3074
5
  if (ComparisonVal == Max)
3075
0
    return F.getEmptySet();
3076
3077
5
  llvm::APSInt Lower = ComparisonVal - Adjustment;
3078
5
  llvm::APSInt Upper = Max - Adjustment;
3079
5
  ++Lower;
3080
3081
5
  RangeSet SymRange = getRange(St, Sym);
3082
5
  return F.intersect(SymRange, Lower, Upper);
3083
5
}
3084
3085
ProgramStateRef
3086
RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
3087
                                    const llvm::APSInt &Int,
3088
5
                                    const llvm::APSInt &Adjustment) {
3089
5
  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
3090
5
  return setRange(St, Sym, New);
3091
5
}
3092
3093
RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
3094
                                               SymbolRef Sym,
3095
                                               const llvm::APSInt &Int,
3096
4
                                               const llvm::APSInt &Adjustment) {
3097
  // Before we do any real work, see if the value can even show up.
3098
4
  APSIntType AdjustmentType(Adjustment);
3099
4
  switch (AdjustmentType.testInRange(Int, true)) {
3100
0
  case APSIntType::RTR_Below:
3101
0
    return getRange(St, Sym);
3102
4
  case APSIntType::RTR_Within:
3103
4
    break;
3104
0
  case APSIntType::RTR_Above:
3105
0
    return F.getEmptySet();
3106
4
  }
3107
3108
  // Special case for Int == Min. This is always feasible.
3109
4
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3110
4
  llvm::APSInt Min = AdjustmentType.getMinValue();
3111
4
  if (ComparisonVal == Min)
3112
0
    return getRange(St, Sym);
3113
3114
4
  llvm::APSInt Max = AdjustmentType.getMaxValue();
3115
4
  llvm::APSInt Lower = ComparisonVal - Adjustment;
3116
4
  llvm::APSInt Upper = Max - Adjustment;
3117
3118
4
  RangeSet SymRange = getRange(St, Sym);
3119
4
  return F.intersect(SymRange, Lower, Upper);
3120
4
}
3121
3122
ProgramStateRef
3123
RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
3124
                                    const llvm::APSInt &Int,
3125
4
                                    const llvm::APSInt &Adjustment) {
3126
4
  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
3127
4
  return setRange(St, Sym, New);
3128
4
}
3129
3130
RangeSet
3131
RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS,
3132
                                      const llvm::APSInt &Int,
3133
5
                                      const llvm::APSInt &Adjustment) {
3134
  // Before we do any real work, see if the value can even show up.
3135
5
  APSIntType AdjustmentType(Adjustment);
3136
5
  switch (AdjustmentType.testInRange(Int, true)) {
3137
0
  case APSIntType::RTR_Below:
3138
0
    return F.getEmptySet();
3139
5
  case APSIntType::RTR_Within:
3140
5
    break;
3141
0
  case APSIntType::RTR_Above:
3142
0
    return RS();
3143
5
  }
3144
3145
  // Special case for Int == Max. This is always feasible.
3146
5
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3147
5
  llvm::APSInt Max = AdjustmentType.getMaxValue();
3148
5
  if (ComparisonVal == Max)
3149
0
    return RS();
3150
3151
5
  llvm::APSInt Min = AdjustmentType.getMinValue();
3152
5
  llvm::APSInt Lower = Min - Adjustment;
3153
5
  llvm::APSInt Upper = ComparisonVal - Adjustment;
3154
3155
5
  RangeSet Default = RS();
3156
5
  return F.intersect(Default, Lower, Upper);
3157
5
}
3158
3159
RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
3160
                                               SymbolRef Sym,
3161
                                               const llvm::APSInt &Int,
3162
5
                                               const llvm::APSInt &Adjustment) {
3163
5
  return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);
3164
5
}
3165
3166
ProgramStateRef
3167
RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
3168
                                    const llvm::APSInt &Int,
3169
5
                                    const llvm::APSInt &Adjustment) {
3170
5
  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
3171
5
  return setRange(St, Sym, New);
3172
5
}
3173
3174
ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
3175
    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
3176
0
    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
3177
0
  RangeSet New = getSymGERange(State, Sym, From, Adjustment);
3178
0
  if (New.isEmpty())
3179
0
    return nullptr;
3180
0
  RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
3181
0
  return setRange(State, Sym, Out);
3182
0
}
3183
3184
ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
3185
    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
3186
0
    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
3187
0
  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
3188
0
  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
3189
0
  RangeSet New(F.add(RangeLT, RangeGT));
3190
0
  return setRange(State, Sym, New);
3191
0
}
3192
3193
//===----------------------------------------------------------------------===//
3194
// Pretty-printing.
3195
//===----------------------------------------------------------------------===//
3196
3197
void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,
3198
                                       const char *NL, unsigned int Space,
3199
0
                                       bool IsDot) const {
3200
0
  printConstraints(Out, State, NL, Space, IsDot);
3201
0
  printEquivalenceClasses(Out, State, NL, Space, IsDot);
3202
0
  printDisequalities(Out, State, NL, Space, IsDot);
3203
0
}
3204
3205
0
static std::string toString(const SymbolRef &Sym) {
3206
0
  std::string S;
3207
0
  llvm::raw_string_ostream O(S);
3208
0
  Sym->dumpToStream(O);
3209
0
  return O.str();
3210
0
}
3211
3212
void RangeConstraintManager::printConstraints(raw_ostream &Out,
3213
                                              ProgramStateRef State,
3214
                                              const char *NL,
3215
                                              unsigned int Space,
3216
0
                                              bool IsDot) const {
3217
0
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
3218
3219
0
  Indent(Out, Space, IsDot) << "\"constraints\": ";
3220
0
  if (Constraints.isEmpty()) {
3221
0
    Out << "null," << NL;
3222
0
    return;
3223
0
  }
3224
3225
0
  std::map<std::string, RangeSet> OrderedConstraints;
3226
0
  for (std::pair<EquivalenceClass, RangeSet> P : Constraints) {
3227
0
    SymbolSet ClassMembers = P.first.getClassMembers(State);
3228
0
    for (const SymbolRef &ClassMember : ClassMembers) {
3229
0
      bool insertion_took_place;
3230
0
      std::tie(std::ignore, insertion_took_place) =
3231
0
          OrderedConstraints.insert({toString(ClassMember), P.second});
3232
0
      assert(insertion_took_place &&
3233
0
             "two symbols should not have the same dump");
3234
0
    }
3235
0
  }
3236
3237
0
  ++Space;
3238
0
  Out << '[' << NL;
3239
0
  bool First = true;
3240
0
  for (std::pair<std::string, RangeSet> P : OrderedConstraints) {
3241
0
    if (First) {
3242
0
      First = false;
3243
0
    } else {
3244
0
      Out << ',';
3245
0
      Out << NL;
3246
0
    }
3247
0
    Indent(Out, Space, IsDot)
3248
0
        << "{ \"symbol\": \"" << P.first << "\", \"range\": \"";
3249
0
    P.second.dump(Out);
3250
0
    Out << "\" }";
3251
0
  }
3252
0
  Out << NL;
3253
3254
0
  --Space;
3255
0
  Indent(Out, Space, IsDot) << "]," << NL;
3256
0
}
3257
3258
0
static std::string toString(ProgramStateRef State, EquivalenceClass Class) {
3259
0
  SymbolSet ClassMembers = Class.getClassMembers(State);
3260
0
  llvm::SmallVector<SymbolRef, 8> ClassMembersSorted(ClassMembers.begin(),
3261
0
                                                     ClassMembers.end());
3262
0
  llvm::sort(ClassMembersSorted,
3263
0
             [](const SymbolRef &LHS, const SymbolRef &RHS) {
3264
0
               return toString(LHS) < toString(RHS);
3265
0
             });
3266
3267
0
  bool FirstMember = true;
3268
3269
0
  std::string Str;
3270
0
  llvm::raw_string_ostream Out(Str);
3271
0
  Out << "[ ";
3272
0
  for (SymbolRef ClassMember : ClassMembersSorted) {
3273
0
    if (FirstMember)
3274
0
      FirstMember = false;
3275
0
    else
3276
0
      Out << ", ";
3277
0
    Out << "\"" << ClassMember << "\"";
3278
0
  }
3279
0
  Out << " ]";
3280
0
  return Out.str();
3281
0
}
3282
3283
void RangeConstraintManager::printEquivalenceClasses(raw_ostream &Out,
3284
                                                     ProgramStateRef State,
3285
                                                     const char *NL,
3286
                                                     unsigned int Space,
3287
0
                                                     bool IsDot) const {
3288
0
  ClassMembersTy Members = State->get<ClassMembers>();
3289
3290
0
  Indent(Out, Space, IsDot) << "\"equivalence_classes\": ";
3291
0
  if (Members.isEmpty()) {
3292
0
    Out << "null," << NL;
3293
0
    return;
3294
0
  }
3295
3296
0
  std::set<std::string> MembersStr;
3297
0
  for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members)
3298
0
    MembersStr.insert(toString(State, ClassToSymbolSet.first));
3299
3300
0
  ++Space;
3301
0
  Out << '[' << NL;
3302
0
  bool FirstClass = true;
3303
0
  for (const std::string &Str : MembersStr) {
3304
0
    if (FirstClass) {
3305
0
      FirstClass = false;
3306
0
    } else {
3307
0
      Out << ',';
3308
0
      Out << NL;
3309
0
    }
3310
0
    Indent(Out, Space, IsDot);
3311
0
    Out << Str;
3312
0
  }
3313
0
  Out << NL;
3314
3315
0
  --Space;
3316
0
  Indent(Out, Space, IsDot) << "]," << NL;
3317
0
}
3318
3319
void RangeConstraintManager::printDisequalities(raw_ostream &Out,
3320
                                                ProgramStateRef State,
3321
                                                const char *NL,
3322
                                                unsigned int Space,
3323
0
                                                bool IsDot) const {
3324
0
  DisequalityMapTy Disequalities = State->get<DisequalityMap>();
3325
3326
0
  Indent(Out, Space, IsDot) << "\"disequality_info\": ";
3327
0
  if (Disequalities.isEmpty()) {
3328
0
    Out << "null," << NL;
3329
0
    return;
3330
0
  }
3331
3332
  // Transform the disequality info to an ordered map of
3333
  // [string -> (ordered set of strings)]
3334
0
  using EqClassesStrTy = std::set<std::string>;
3335
0
  using DisequalityInfoStrTy = std::map<std::string, EqClassesStrTy>;
3336
0
  DisequalityInfoStrTy DisequalityInfoStr;
3337
0
  for (std::pair<EquivalenceClass, ClassSet> ClassToDisEqSet : Disequalities) {
3338
0
    EquivalenceClass Class = ClassToDisEqSet.first;
3339
0
    ClassSet DisequalClasses = ClassToDisEqSet.second;
3340
0
    EqClassesStrTy MembersStr;
3341
0
    for (EquivalenceClass DisEqClass : DisequalClasses)
3342
0
      MembersStr.insert(toString(State, DisEqClass));
3343
0
    DisequalityInfoStr.insert({toString(State, Class), MembersStr});
3344
0
  }
3345
3346
0
  ++Space;
3347
0
  Out << '[' << NL;
3348
0
  bool FirstClass = true;
3349
0
  for (std::pair<std::string, EqClassesStrTy> ClassToDisEqSet :
3350
0
       DisequalityInfoStr) {
3351
0
    const std::string &Class = ClassToDisEqSet.first;
3352
0
    if (FirstClass) {
3353
0
      FirstClass = false;
3354
0
    } else {
3355
0
      Out << ',';
3356
0
      Out << NL;
3357
0
    }
3358
0
    Indent(Out, Space, IsDot) << "{" << NL;
3359
0
    unsigned int DisEqSpace = Space + 1;
3360
0
    Indent(Out, DisEqSpace, IsDot) << "\"class\": ";
3361
0
    Out << Class;
3362
0
    const EqClassesStrTy &DisequalClasses = ClassToDisEqSet.second;
3363
0
    if (!DisequalClasses.empty()) {
3364
0
      Out << "," << NL;
3365
0
      Indent(Out, DisEqSpace, IsDot) << "\"disequal_to\": [" << NL;
3366
0
      unsigned int DisEqClassSpace = DisEqSpace + 1;
3367
0
      Indent(Out, DisEqClassSpace, IsDot);
3368
0
      bool FirstDisEqClass = true;
3369
0
      for (const std::string &DisEqClass : DisequalClasses) {
3370
0
        if (FirstDisEqClass) {
3371
0
          FirstDisEqClass = false;
3372
0
        } else {
3373
0
          Out << ',' << NL;
3374
0
          Indent(Out, DisEqClassSpace, IsDot);
3375
0
        }
3376
0
        Out << DisEqClass;
3377
0
      }
3378
0
      Out << "]" << NL;
3379
0
    }
3380
0
    Indent(Out, Space, IsDot) << "}";
3381
0
  }
3382
0
  Out << NL;
3383
3384
0
  --Space;
3385
0
  Indent(Out, Space, IsDot) << "]," << NL;
3386
0
}