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