brintos / llvm-project-archived public Read only

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-exception6//7//===----------------------------------------------------------------------===//8//9//  This file defines RangeConstraintManager, a class that tracks simple10//  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 reason35// 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 for50  // branching an exploded graph. We can reason about the branch if there is51  // a previously known fact of the existence of a comparison expression with52  // 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 | False57  //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 only76  static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1;77  const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = {78      // <      >      <=     >=     ==     !=    UnknownX279      {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(CurrentOP)][getIndexFromOp(QueriedOP)];101  }102 103  TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const {104    return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];105  }106};107 108//===----------------------------------------------------------------------===//109//                           RangeSet implementation110//===----------------------------------------------------------------------===//111 112RangeSet::ContainerType RangeSet::Factory::EmptySet{};113 114RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {115  ContainerType Result;116  Result.reserve(LHS.size() + RHS.size());117  std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),118             std::back_inserter(Result));119  return makePersistent(std::move(Result));120}121 122RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) {123  ContainerType Result;124  Result.reserve(Original.size() + 1);125 126  const_iterator Lower = llvm::lower_bound(Original, Element);127  Result.insert(Result.end(), Original.begin(), Lower);128  Result.push_back(Element);129  Result.insert(Result.end(), Lower, Original.end());130 131  return makePersistent(std::move(Result));132}133 134RangeSet RangeSet::Factory::add(RangeSet Original, const llvm::APSInt &Point) {135  return add(Original, Range(Point));136}137 138RangeSet RangeSet::Factory::unite(RangeSet LHS, RangeSet RHS) {139  ContainerType Result = unite(*LHS.Impl, *RHS.Impl);140  return makePersistent(std::move(Result));141}142 143RangeSet RangeSet::Factory::unite(RangeSet Original, Range R) {144  ContainerType Result;145  Result.push_back(R);146  Result = unite(*Original.Impl, Result);147  return makePersistent(std::move(Result));148}149 150RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) {151  return unite(Original, Range(ValueFactory.getValue(Point)));152}153 154RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt From,155                                  llvm::APSInt To) {156  return unite(Original,157               Range(ValueFactory.getValue(From), ValueFactory.getValue(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, this185  // particular check for `MIN` is not needed in the loop below every time186  // 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(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 Result223  // and return with that.224  const auto AppendTheRest = [&Result](iterator I, iterator E) {225    Result.append(I, 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(UnionStart, 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 find265      // 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(UnionStart, 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(UnionStart, 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(From);321  return makePersistent(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 stack333    // and move it to the freshly allocated buffer if we don't have334    // a set like this already.335    Result = construct(std::move(From));336    Cache.InsertNode(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(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(*this, Dummy);378  if (It == begin())379    return false;380 381  return std::prev(It)->Includes(Point);382}383 384bool RangeSet::pin(llvm::APSInt &Point) const {385  APSIntType Type(getMinValue());386  if (Type.testInRange(Point, true) != APSIntType::RTR_Within)387    return false;388 389  Type.apply(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-testing395  // 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 outside398  // the range of values for the associated symbol.399  APSIntType Type(getMinValue());400  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);401  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, 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(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(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(Lower);438      Type.apply(Upper);439      break;440    case APSIntType::RTR_Above:441      // The range starts within what's possible but ends above it. Pin.442      Type.apply(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(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 intersection485    //           by checking the two following situations:486    //487    //               <---[  What  ]---[------]------>488    //                              Lower  Upper489    //                            -or-490    //               <----[------]----[  What  ]---->491    //                  Lower  Upper492    if (What.getMaxValue() < Lower || Upper < What.getMinValue())493      return getEmptySet();494 495    DummyContainer.push_back(496        Range(ValueFactory.getValue(Lower), ValueFactory.getValue(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 intersection501    //           by checking the following situation:502    //503    //               <------]---[  What  ]---[------>504    //                    Upper             Lower505    if (What.getMaxValue() < Lower && Upper < What.getMinValue())506      return getEmptySet();507 508    DummyContainer.push_back(509        Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper)));510    DummyContainer.push_back(511        Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower)));512  }513 514  return intersect(*What.Impl, DummyContainer);515}516 517RangeSet RangeSet::Factory::intersect(const RangeSet::ContainerType &LHS,518                                      const RangeSet::ContainerType &RHS) {519  ContainerType Result;520  Result.reserve(std::max(LHS.size(), 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 the527  // 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 the548        // 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' ends563      // is greater.  That "longer" range might have some other564      // 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 and577      // Second->From and we don't know whether Second+1 intersects578      // with First.579      //580      // However, we know that [IntersectionStart, Second->To] is581      // a part of the intersection...582      Result.push_back(Range(IntersectionStart, Second->To()));583      ++Second;584      // ...and that the invariant will hold for a valid Second+1585      // 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(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.Impl, *RHS.Impl);602}603 604RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) {605  if (LHS.containsImpl(Point))606    return getRangeSet(ValueFactory.getValue(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(SampleValue);617  const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);618 619  ContainerType Result;620  Result.reserve(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(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 ranges641      //   [MIN, A], ... , [B, MAX]642      // And the result should be [MIN, -B], ..., [-A, MAX]643      Result.emplace_back(MIN, ValueFactory.getValue(-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(MIN, 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(ValueFactory.getValue(-To), 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(-It->To());664    const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From());665 666    // Add a negated range.667    Result.emplace_back(NewFrom, NewTo);668  }669 670  llvm::sort(Result);671  return makePersistent(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(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 which692  //   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 with695  //   higher bitwidth: char -> uint, int-> uint64. The point is that we also696  //   need convert negatives to positives and use convertTo function as well.697  //   For example, we don't need such a convertion when converting unsigned to698  //   signed with higher bitwidth, because all the values of unsigned is valid699  //   for the such signed.700  if (IsConversion && (!IsPromotion || !What.isUnsigned()))701    return makePersistent(convertTo(What, Ty));702 703  assert(IsPromotion && "Only promotion operation from unsigneds left.");704  return makePersistent(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, 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, because721  // 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 keep723  // it inside `char`.724  // And it's OK, it's enough to do correct calculations.725  uint64_t CastRangeSize = APInt::getMaxValue(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 current731    // range minus one.732    uint64_t CurrentRangeSize = (ToInt - FromInt).getZExtValue();733    // This is an optimization for a specific case when this Range covers734    // the whole range of the target type.735    Dummy.clear();736    if (CurrentRangeSize >= CastRangeSize) {737      Dummy.emplace_back(ValueFactory.getMinValue(Ty),738                         ValueFactory.getMaxValue(Ty));739      Result = std::move(Dummy);740      break;741    }742    // Cast the bounds.743    Ty.apply(FromInt);744    Ty.apply(ToInt);745    const APSInt &PersistentFrom = ValueFactory.getValue(FromInt);746    const APSInt &PersistentTo = ValueFactory.getValue(ToInt);747    if (FromInt > ToInt) {748      Dummy.emplace_back(ValueFactory.getMinValue(Ty), PersistentTo);749      Dummy.emplace_back(PersistentFrom, ValueFactory.getMaxValue(Ty));750    } else751      Dummy.emplace_back(PersistentFrom, 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(Result, 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 start764// go in descending order. That means that we crossed over the middle of765// 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 another769// 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 have773// 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(FromInt);791    Ty.apply(ToInt);792    return {VF.getValue(FromInt), VF.getValue(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(NewBounds.first, 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 the808    // second one.809    if (NewBounds.first > NewBounds.second) {810      DescendArray.emplace_back(ValueFactory.getMinValue(Ty), NewBounds.second);811      AscendArray.emplace_back(NewBounds.first, ValueFactory.getMaxValue(Ty));812    } else813      // Values are going acsending order.814      AscendArray.emplace_back(NewBounds.first, 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(NewBounds.first, NewBounds.second);821  }822  // Unite both arrays.823  return unite(AscendArray, 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(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 push835  // 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(FromInt);842    Ty.apply(ToInt);843    Result.emplace_back(ValueFactory.getValue(FromInt),844                        ValueFactory.getValue(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(From, Upper, Lower);862}863 864LLVM_DUMP_METHOD void Range::dump(raw_ostream &OS) const {865  OS << '[' << toString(From(), 10) << ", " << toString(To(), 10) << ']';866}867LLVM_DUMP_METHOD void Range::dump() const { dump(llvm::errs()); }868 869LLVM_DUMP_METHOD void RangeSet::dump(raw_ostream &OS) const {870  OS << "{ ";871  llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(OS); });872  OS << " }";873}874LLVM_DUMP_METHOD void RangeSet::dump() const { dump(llvm::errs()); }875 876REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)877 878namespace {879class EquivalenceClass;880} // end anonymous namespace881 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 narrowing893/// and sharing constraints between symbols within the class.  Also we can894/// conclude that there is no practical need in storing constraints for895/// every member of the class separately.896///897/// Main terminology:898///899///   * "Equivalence class" is an object of this class, which can be efficiently900///     compared to other classes.  It represents the whole class without901///     storing the actual in it.  The members of the class however can be902///     retrieved from the state.903///904///   * "Class members" are the symbols corresponding to the class.  This means905///     that A == B for every member symbols A and B from the class.  Members of906///     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 operation911///     to produce non-trivial classes.912///     If, at some point, we can assume that two symbols from two distinct913///     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 ProgramStateRef927  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 stored934  /// to it in State/ClassMembers.935  /// An equivalence class with one member might seem as it does not hold any936  /// meaningful information, i.e. that is a tautology. However, during the937  /// removal of dead symbols we do not remove classes with one member for938  /// resource and performance reasons. Consequently, a class with one member is939  /// not necessarily trivial. It could happen that we have a class with two940  /// members and then during the removal of dead symbols we remove one of its941  /// members. In this case, the class is still non-trivial (it still has the942  /// 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 ProgramStateRef950  markDisequal(RangeSet::Factory &F, ProgramStateRef State, SymbolRef First,951               SymbolRef Second);952  [[nodiscard]] static inline ProgramStateRef953  markDisequal(RangeSet::Factory &F, ProgramStateRef State,954               EquivalenceClass First, EquivalenceClass Second);955  [[nodiscard]] inline ProgramStateRef956  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 ClassSet962  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, llvm::errs());983  }984 985  /// Check equivalence data for consistency.986  [[nodiscard]] [[maybe_unused]] static bool987  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(CID);1009  }1010 1011  void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, 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 detail1019  /// and should stay that way.1020  /// In the current implementation, we use it to retrieve the only member1021  /// 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 bool1032  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 functions1042//===----------------------------------------------------------------------===//1043 1044[[nodiscard]] [[maybe_unused]] bool areFeasible(ConstraintRangeTy Constraints) {1045  return llvm::none_of(1046      Constraints,1047      [](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>(Class);1055}1056 1057[[nodiscard]] inline const RangeSet *getConstraint(ProgramStateRef State,1058                                                   SymbolRef Sym) {1059  return getConstraint(State, EquivalenceClass::find(State, Sym));1060}1061 1062[[nodiscard]] ProgramStateRef setConstraint(ProgramStateRef State,1063                                            EquivalenceClass Class,1064                                            RangeSet Constraint) {1065  return State->set<ConstraintRange>(Class, Constraint);1066}1067 1068[[nodiscard]] ProgramStateRef setConstraints(ProgramStateRef State,1069                                             ConstraintRangeTy Constraints) {1070  return State->set<ConstraintRange>(Constraints);1071}1072 1073//===----------------------------------------------------------------------===//1074//                       Equality/diseqiality abstraction1075//===----------------------------------------------------------------------===//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 this1080/// 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 operands1084///          false if it means disequality of operands1085///          std::nullopt otherwise1086std::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 functions1104//===----------------------------------------------------------------------===//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 further1114  using Type = RangeSet;1115};1116 1117template <> struct IntersectionTraits<> {1118  // We ran out of types, and we didn't find any RangeSet, so the result should1119  // 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>, simply1132  // 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 into1139  // 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,...> version1150  // of the function and can be sure that the result is RangeSet.1151  return intersect(F, F.intersect(Head, 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,...>, which1162  // 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 arguments1168/// don't hold a range set (nullptr or std::nullopt), the function will skip1169/// them.1170///1171/// Available representations for the arguments are:1172///   * RangeSet1173///   * std::optional<RangeSet>1174///   * RangeSet *1175/// Pointer to a RangeSet is automatically assumed to be nullable and will get1176/// 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 compile1180/// time that there will be a range set as a result, the returning type is1181/// simply RangeSet, in other cases we have to back off to1182/// std::optional<RangeSet>.1183///1184/// Please, prefer optional range sets to raw pointers.  If the last argument is1185/// a raw pointer and all previous arguments are std::nullopt, it will cost one1186/// additional check to convert RangeSet * into std::optional<RangeSet>.1187template <class HeadTy, class SecondTy, class... RestTy>1188[[nodiscard]] inline1189    typename IntersectionTraits<HeadTy, SecondTy, RestTy...>::Type1190    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 logic1200//===----------------------------------------------------------------------===//1201 1202/// A little component aggregating all of the reasoning we have about1203/// the ranges of symbolic expressions.1204///1205/// Even when we don't know the exact values of the operands, we still1206/// can get a pretty good estimate of the result's range.1207class SymbolicRangeInferrer1208    : 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 symbolic1221    // expression is not supported for advanced inference.1222    // In this case, we simply backoff to the default "let's simply1223    // infer the range from the expression's type".1224    return infer(Sym->getType());1225  }1226 1227  RangeSet VisitUnarySymExpr(const UnarySymExpr *USE) {1228    if (std::optional<RangeSet> RS = getRangeForNegatedUnarySym(USE))1229      return *RS;1230    return infer(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        RangeFactory,1244        // If Sym is a difference of symbols A - B, then maybe we have range1245        // set stored for B - A.1246        //1247        // If we have range set stored for both A - B and B - A then1248        // calculate the effective range set by intersecting the range set1249        // for A - B and the negated range set of B - A.1250        getRangeForNegatedSymSym(SSE),1251        // If commutative, we may have constaints for the commuted variant.1252        getRangeCommutativeSymSym(SSE),1253        // If Sym is a comparison expression (except <=>),1254        // find any other comparisons with the same operands.1255        // See function description.1256        getRangeForComparisonSymbol(SSE),1257        // If Sym is (dis)equality, we might have some information1258        // on that in our equality classes data structure.1259        getRangeForEqualities(SSE),1260        // And we should always check what we can get from the operands.1261        VisitBinaryOperator(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 with1271  /// 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(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(DestType);1287  }1288 1289  RangeSet infer(SymbolRef Sym) {1290    return intersect(RangeFactory,1291                     // Of course, we should take the constraint directly1292                     // associated with this symbol into consideration.1293                     getConstraint(State, Sym),1294                     // Apart from the Sym itself, we can infer quite a lot if1295                     // we look into subexpressions of Sym.1296                     Visit(Sym));1297  }1298 1299  RangeSet infer(EquivalenceClass Class) {1300    if (const RangeSet *AssociatedConstraint = getConstraint(State, Class))1301      return *AssociatedConstraint;1302 1303    return infer(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 the1309    // 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(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 good1323    // use of the inferred ranges.  In this case, we might be calculating1324    // everything for nothing.  This being said, we should introduce some1325    // sort of laziness mechanism here.1326    //1327    // TODO #2: We didn't go into the nested expressions before, so it1328    // might cause us spending much more time doing the inference.1329    // This can be a problem for deeply nested expressions that are1330    // involved in conditions and get tested continuously.  We definitely1331    // need to address this issue and introduce some sort of caching1332    // 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 operators1344  //===----------------------------------------------------------------------===//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(Origin.From(), false) != APSIntType::RTR_Within ||1361        To.testInRange(Origin.To(), false) != APSIntType::RTR_Within) {1362      return std::nullopt;1363    }1364    return Range(ValueFactory.Convert(To, Origin.From()),1365                 ValueFactory.Convert(To, 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(LHS);1373    Range CoarseRHS = fillGaps(RHS);1374 1375    APSIntType ResultType = ValueFactory.getAPSIntType(T);1376 1377    // We need to convert ranges to the resulting type, so we can compare values1378    // and combine them in a meaningful (in terms of the given operation) way.1379    auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);1380    auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);1381 1382    // It is hard to reason about ranges when conversion changes1383    // 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  /// Return a symmetrical range for the given range and type.1397  ///1398  /// If T is signed, return the smallest range [-x..x] that covers the original1399  /// range, or [-min(T), max(T)] if the aforementioned symmetric range doesn't1400  /// exist due to original range covering min(T)).1401  ///1402  /// If T is unsigned, return the smallest range [0..x] that covers the1403  /// original range.1404  Range getSymmetricalRange(Range Origin, QualType T) {1405    APSIntType RangeType = ValueFactory.getAPSIntType(T);1406 1407    if (RangeType.isUnsigned()) {1408      return Range(ValueFactory.getMinValue(RangeType), Origin.To());1409    }1410 1411    if (Origin.From().isMinSignedValue()) {1412      // If mini is a minimal signed value, absolute value of it is greater1413      // than the maximal signed value.  In order to avoid these1414      // complications, we simply return the whole range.1415      return {ValueFactory.getMinValue(RangeType),1416              ValueFactory.getMaxValue(RangeType)};1417    }1418 1419    // At this point, we are sure that the type is signed and we can safely1420    // use unary - operator.1421    //1422    // While calculating absolute maximum, we can use the following formula1423    // because of these reasons:1424    //   * If From >= 0 then To >= From and To >= -From.1425    //     AbsMax == To == max(To, -From)1426    //   * If To <= 0 then -From >= -To and -From >= From.1427    //     AbsMax == -From == max(-From, To)1428    //   * Otherwise, From <= 0, To >= 0, and1429    //     AbsMax == max(abs(From), abs(To))1430    llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To());1431 1432    // Intersection is guaranteed to be non-empty.1433    return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};1434  }1435 1436  /// Return a range set subtracting zero from \p Domain.1437  RangeSet assumeNonZero(RangeSet Domain, QualType T) {1438    APSIntType IntType = ValueFactory.getAPSIntType(T);1439    return RangeFactory.deletePoint(Domain, IntType.getZeroValue());1440  }1441 1442  template <typename ProduceNegatedSymFunc>1443  std::optional<RangeSet> getRangeForNegatedExpr(ProduceNegatedSymFunc F,1444                                                 QualType T) {1445    // Do not negate if the type cannot be meaningfully negated.1446    if (!T->isUnsignedIntegerOrEnumerationType() &&1447        !T->isSignedIntegerOrEnumerationType())1448      return std::nullopt;1449 1450    if (SymbolRef NegatedSym = F())1451      if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym))1452        return RangeFactory.negate(*NegatedRange);1453 1454    return std::nullopt;1455  }1456 1457  std::optional<RangeSet> getRangeForNegatedUnarySym(const UnarySymExpr *USE) {1458    // Just get the operand when we negate a symbol that is already negated.1459    // -(-a) == a1460    return getRangeForNegatedExpr(1461        [USE]() -> SymbolRef {1462          if (USE->getOpcode() == UO_Minus)1463            return USE->getOperand();1464          return nullptr;1465        },1466        USE->getType());1467  }1468 1469  std::optional<RangeSet> getRangeForNegatedSymSym(const SymSymExpr *SSE) {1470    return getRangeForNegatedExpr(1471        [SSE, State = this->State]() -> SymbolRef {1472          if (SSE->getOpcode() == BO_Sub)1473            return State->getSymbolManager().acquire<SymSymExpr>(1474                SSE->getRHS(), BO_Sub, SSE->getLHS(), SSE->getType());1475          return nullptr;1476        },1477        SSE->getType());1478  }1479 1480  std::optional<RangeSet> getRangeForNegatedSym(SymbolRef Sym) {1481    return getRangeForNegatedExpr(1482        [Sym, State = this->State]() {1483          return State->getSymbolManager().acquire<UnarySymExpr>(1484              Sym, UO_Minus, Sym->getType());1485        },1486        Sym->getType());1487  }1488 1489  std::optional<RangeSet> getRangeCommutativeSymSym(const SymSymExpr *SSE) {1490    auto Op = SSE->getOpcode();1491    bool IsCommutative = llvm::is_contained(1492        // ==, !=, |, &, +, *, ^1493        {BO_EQ, BO_NE, BO_Or, BO_And, BO_Add, BO_Mul, BO_Xor}, Op);1494    if (!IsCommutative)1495      return std::nullopt;1496 1497    SymbolRef Commuted = State->getSymbolManager().acquire<SymSymExpr>(1498        SSE->getRHS(), Op, SSE->getLHS(), SSE->getType());1499    if (const RangeSet *Range = getConstraint(State, Commuted))1500      return *Range;1501    return std::nullopt;1502  }1503 1504  // Returns ranges only for binary comparison operators (except <=>)1505  // when left and right operands are symbolic values.1506  // Finds any other comparisons with the same operands.1507  // Then do logical calculations and refuse impossible branches.1508  // E.g. (x < y) and (x > y) at the same time are impossible.1509  // E.g. (x >= y) and (x != y) at the same time makes (x > y) true only.1510  // E.g. (x == y) and (y == x) are just reversed but the same.1511  // It covers all possible combinations (see CmpOpTable description).1512  // Note that `x` and `y` can also stand for subexpressions,1513  // not only for actual symbols.1514  std::optional<RangeSet> getRangeForComparisonSymbol(const SymSymExpr *SSE) {1515    const BinaryOperatorKind CurrentOP = SSE->getOpcode();1516 1517    // We currently do not support <=> (C++20).1518    if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp))1519      return std::nullopt;1520 1521    static const OperatorRelationsTable CmpOpTable{};1522 1523    const SymExpr *LHS = SSE->getLHS();1524    const SymExpr *RHS = SSE->getRHS();1525    QualType T = SSE->getType();1526 1527    SymbolManager &SymMgr = State->getSymbolManager();1528 1529    // We use this variable to store the last queried operator (`QueriedOP`)1530    // for which the `getCmpOpState` returned with `Unknown`. If there are two1531    // different OPs that returned `Unknown` then we have to query the special1532    // `UnknownX2` column. We assume that `getCmpOpState(CurrentOP, CurrentOP)`1533    // never returns `Unknown`, so `CurrentOP` is a good initial value.1534    BinaryOperatorKind LastQueriedOpToUnknown = CurrentOP;1535 1536    // Loop goes through all of the columns exept the last one ('UnknownX2').1537    // We treat `UnknownX2` column separately at the end of the loop body.1538    for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) {1539 1540      // Let's find an expression e.g. (x < y).1541      BinaryOperatorKind QueriedOP = OperatorRelationsTable::getOpFromIndex(i);1542      const SymSymExpr *SymSym =1543          SymMgr.acquire<SymSymExpr>(LHS, QueriedOP, RHS, T);1544      const RangeSet *QueriedRangeSet = getConstraint(State, SymSym);1545 1546      // If ranges were not previously found,1547      // try to find a reversed expression (y > x).1548      if (!QueriedRangeSet) {1549        const BinaryOperatorKind ROP =1550            BinaryOperator::reverseComparisonOp(QueriedOP);1551        SymSym = SymMgr.acquire<SymSymExpr>(RHS, ROP, LHS, T);1552        QueriedRangeSet = getConstraint(State, SymSym);1553      }1554 1555      if (!QueriedRangeSet || QueriedRangeSet->isEmpty())1556        continue;1557 1558      const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue();1559      const bool isInFalseBranch =1560          ConcreteValue ? (*ConcreteValue == 0) : false;1561 1562      // If it is a false branch, we shall be guided by opposite operator,1563      // because the table is made assuming we are in the true branch.1564      // E.g. when (x <= y) is false, then (x > y) is true.1565      if (isInFalseBranch)1566        QueriedOP = BinaryOperator::negateComparisonOp(QueriedOP);1567 1568      OperatorRelationsTable::TriStateKind BranchState =1569          CmpOpTable.getCmpOpState(CurrentOP, QueriedOP);1570 1571      if (BranchState == OperatorRelationsTable::Unknown) {1572        if (LastQueriedOpToUnknown != CurrentOP &&1573            LastQueriedOpToUnknown != QueriedOP) {1574          // If we got the Unknown state for both different operators.1575          // if (x <= y)    // assume true1576          //   if (x != y)  // assume true1577          //     if (x < y) // would be also true1578          // Get a state from `UnknownX2` column.1579          BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP);1580        } else {1581          LastQueriedOpToUnknown = QueriedOP;1582          continue;1583        }1584      }1585 1586      return (BranchState == OperatorRelationsTable::True) ? getTrueRange(T)1587                                                           : getFalseRange(T);1588    }1589 1590    return std::nullopt;1591  }1592 1593  std::optional<RangeSet> getRangeForEqualities(const SymSymExpr *Sym) {1594    std::optional<bool> Equality = meansEquality(Sym);1595 1596    if (!Equality)1597      return std::nullopt;1598 1599    if (std::optional<bool> AreEqual =1600            EquivalenceClass::areEqual(State, Sym->getLHS(), Sym->getRHS())) {1601      // Here we cover two cases at once:1602      //   * if Sym is equality and its operands are known to be equal -> true1603      //   * if Sym is disequality and its operands are disequal -> true1604      if (*AreEqual == *Equality) {1605        return getTrueRange(Sym->getType());1606      }1607      // Opposite combinations result in false.1608      return getFalseRange(Sym->getType());1609    }1610 1611    return std::nullopt;1612  }1613 1614  RangeSet getTrueRange(QualType T) {1615    RangeSet TypeRange = infer(T);1616    return assumeNonZero(TypeRange, T);1617  }1618 1619  RangeSet getFalseRange(QualType T) {1620    const llvm::APSInt &Zero = ValueFactory.getValue(0, T);1621    return RangeSet(RangeFactory, Zero);1622  }1623 1624  BasicValueFactory &ValueFactory;1625  RangeSet::Factory &RangeFactory;1626  ProgramStateRef State;1627};1628 1629//===----------------------------------------------------------------------===//1630//               Range-based reasoning about symbolic operations1631//===----------------------------------------------------------------------===//1632 1633template <>1634RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_NE>(RangeSet LHS,1635                                                           RangeSet RHS,1636                                                           QualType T) {1637  assert(!LHS.isEmpty() && !RHS.isEmpty());1638 1639  if (LHS.getAPSIntType() == RHS.getAPSIntType()) {1640    if (intersect(RangeFactory, LHS, RHS).isEmpty())1641      return getTrueRange(T);1642 1643  } else {1644    // We can only lose information if we are casting smaller signed type to1645    // bigger unsigned type. For e.g.,1646    //    LHS (unsigned short): [2, USHRT_MAX]1647    //    RHS   (signed short): [SHRT_MIN, 0]1648    //1649    // Casting RHS to LHS type will leave us with overlapping values1650    //    CastedRHS : [0, 0] U [SHRT_MAX + 1, USHRT_MAX]1651    //1652    // We can avoid this by checking if signed type's maximum value is lesser1653    // than unsigned type's minimum value.1654 1655    // If both have different signs then only we can get more information.1656    if (LHS.isUnsigned() != RHS.isUnsigned()) {1657      if (LHS.isUnsigned() && (LHS.getBitWidth() >= RHS.getBitWidth())) {1658        if (RHS.getMaxValue().isNegative() ||1659            LHS.getAPSIntType().convert(RHS.getMaxValue()) < LHS.getMinValue())1660          return getTrueRange(T);1661 1662      } else if (RHS.isUnsigned() && (LHS.getBitWidth() <= RHS.getBitWidth())) {1663        if (LHS.getMaxValue().isNegative() ||1664            RHS.getAPSIntType().convert(LHS.getMaxValue()) < RHS.getMinValue())1665          return getTrueRange(T);1666      }1667    }1668 1669    // Both RangeSets should be casted to bigger unsigned type.1670    APSIntType CastingType(std::max(LHS.getBitWidth(), RHS.getBitWidth()),1671                           LHS.isUnsigned() || RHS.isUnsigned());1672 1673    RangeSet CastedLHS = RangeFactory.castTo(LHS, CastingType);1674    RangeSet CastedRHS = RangeFactory.castTo(RHS, CastingType);1675 1676    if (intersect(RangeFactory, CastedLHS, CastedRHS).isEmpty())1677      return getTrueRange(T);1678  }1679 1680  // In all other cases, the resulting range cannot be deduced.1681  return infer(T);1682}1683 1684template <>1685RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS,1686                                                           QualType T) {1687  APSIntType ResultType = ValueFactory.getAPSIntType(T);1688  llvm::APSInt Zero = ResultType.getZeroValue();1689 1690  bool IsLHSPositiveOrZero = LHS.From() >= Zero;1691  bool IsRHSPositiveOrZero = RHS.From() >= Zero;1692 1693  bool IsLHSNegative = LHS.To() < Zero;1694  bool IsRHSNegative = RHS.To() < Zero;1695 1696  // Check if both ranges have the same sign.1697  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||1698      (IsLHSNegative && IsRHSNegative)) {1699    // The result is definitely greater or equal than any of the operands.1700    const llvm::APSInt &Min = std::max(LHS.From(), RHS.From());1701 1702    // We estimate maximal value for positives as the maximal value for the1703    // given type.  For negatives, we estimate it with -1 (e.g. 0x11111111).1704    //1705    // TODO: We basically, limit the resulting range from below, but don't do1706    //       anything with the upper bound.1707    //1708    //       For positive operands, it can be done as follows: for the upper1709    //       bound of LHS and RHS we calculate the most significant bit set.1710    //       Let's call it the N-th bit.  Then we can estimate the maximal1711    //       number to be 2^(N+1)-1, i.e. the number with all the bits up to1712    //       the N-th bit set.1713    const llvm::APSInt &Max = IsLHSNegative1714                                  ? ValueFactory.getValue(--Zero)1715                                  : ValueFactory.getMaxValue(ResultType);1716 1717    return {RangeFactory, ValueFactory.getValue(Min), Max};1718  }1719 1720  // Otherwise, let's check if at least one of the operands is negative.1721  if (IsLHSNegative || IsRHSNegative) {1722    // This means that the result is definitely negative as well.1723    return {RangeFactory, ValueFactory.getMinValue(ResultType),1724            ValueFactory.getValue(--Zero)};1725  }1726 1727  RangeSet DefaultRange = infer(T);1728 1729  // It is pretty hard to reason about operands with different signs1730  // (and especially with possibly different signs).  We simply check if it1731  // can be zero.  In order to conclude that the result could not be zero,1732  // at least one of the operands should be definitely not zero itself.1733  if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) {1734    return assumeNonZero(DefaultRange, T);1735  }1736 1737  // Nothing much else to do here.1738  return DefaultRange;1739}1740 1741template <>1742RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS,1743                                                            Range RHS,1744                                                            QualType T) {1745  APSIntType ResultType = ValueFactory.getAPSIntType(T);1746  llvm::APSInt Zero = ResultType.getZeroValue();1747 1748  bool IsLHSPositiveOrZero = LHS.From() >= Zero;1749  bool IsRHSPositiveOrZero = RHS.From() >= Zero;1750 1751  bool IsLHSNegative = LHS.To() < Zero;1752  bool IsRHSNegative = RHS.To() < Zero;1753 1754  // Check if both ranges have the same sign.1755  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||1756      (IsLHSNegative && IsRHSNegative)) {1757    // The result is definitely less or equal than any of the operands.1758    const llvm::APSInt &Max = std::min(LHS.To(), RHS.To());1759 1760    // We conservatively estimate lower bound to be the smallest positive1761    // or negative value corresponding to the sign of the operands.1762    const llvm::APSInt &Min = IsLHSNegative1763                                  ? ValueFactory.getMinValue(ResultType)1764                                  : ValueFactory.getValue(Zero);1765 1766    return {RangeFactory, Min, Max};1767  }1768 1769  // Otherwise, let's check if at least one of the operands is positive.1770  if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) {1771    // This makes result definitely positive.1772    //1773    // We can also reason about a maximal value by finding the maximal1774    // value of the positive operand.1775    const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To() : RHS.To();1776 1777    // The minimal value on the other hand is much harder to reason about.1778    // The only thing we know for sure is that the result is positive.1779    return {RangeFactory, ValueFactory.getValue(Zero),1780            ValueFactory.getValue(Max)};1781  }1782 1783  // Nothing much else to do here.1784  return infer(T);1785}1786 1787template <>1788RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS,1789                                                            Range RHS,1790                                                            QualType T) {1791  llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue();1792 1793  Range ConservativeRange = getSymmetricalRange(RHS, T);1794 1795  llvm::APSInt Max = ConservativeRange.To();1796  llvm::APSInt Min = ConservativeRange.From();1797 1798  if (Max == Zero) {1799    // It's an undefined behaviour to divide by 0 and it seems like we know1800    // for sure that RHS is 0.  Let's say that the resulting range is1801    // simply infeasible for that matter.1802    return RangeFactory.getEmptySet();1803  }1804 1805  // At this point, our conservative range is closed.  The result, however,1806  // couldn't be greater than the RHS' maximal absolute value.  Because of1807  // this reason, we turn the range into open (or half-open in case of1808  // unsigned integers).1809  //1810  // While we operate on integer values, an open interval (a, b) can be easily1811  // represented by the closed interval [a + 1, b - 1].  And this is exactly1812  // what we do next.1813  //1814  // If we are dealing with unsigned case, we shouldn't move the lower bound.1815  if (Min.isSigned()) {1816    ++Min;1817  }1818  --Max;1819 1820  bool IsLHSPositiveOrZero = LHS.From() >= Zero;1821  bool IsRHSPositiveOrZero = RHS.From() >= Zero;1822 1823  // Remainder operator results with negative operands is implementation1824  // defined.  Positive cases are much easier to reason about though.1825  if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) {1826    // If maximal value of LHS is less than maximal value of RHS,1827    // the result won't get greater than LHS.To().1828    Max = std::min(LHS.To(), Max);1829    // We want to check if it is a situation similar to the following:1830    //1831    // <------------|---[  LHS  ]--------[  RHS  ]----->1832    //  -INF        0                              +INF1833    //1834    // In this situation, we can conclude that (LHS / RHS) == 0 and1835    // (LHS % RHS) == LHS.1836    Min = LHS.To() < RHS.From() ? LHS.From() : Zero;1837  }1838 1839  // Nevertheless, the symmetrical range for RHS is a conservative estimate1840  // for any sign of either LHS, or RHS.1841  return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)};1842}1843 1844RangeSet SymbolicRangeInferrer::VisitBinaryOperator(RangeSet LHS,1845                                                    BinaryOperator::Opcode Op,1846                                                    RangeSet RHS, QualType T) {1847  // We should propagate information about unfeasbility of one of the1848  // operands to the resulting range.1849  if (LHS.isEmpty() || RHS.isEmpty()) {1850    return RangeFactory.getEmptySet();1851  }1852 1853  switch (Op) {1854  case BO_NE:1855    return VisitBinaryOperator<BO_NE>(LHS, RHS, T);1856  case BO_Or:1857    return VisitBinaryOperator<BO_Or>(LHS, RHS, T);1858  case BO_And:1859    return VisitBinaryOperator<BO_And>(LHS, RHS, T);1860  case BO_Rem:1861    return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);1862  default:1863    return infer(T);1864  }1865}1866 1867//===----------------------------------------------------------------------===//1868//                  Constraint manager implementation details1869//===----------------------------------------------------------------------===//1870 1871class RangeConstraintManager : public RangedConstraintManager {1872public:1873  RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)1874      : RangedConstraintManager(EE, SVB), F(getBasicVals()) {}1875 1876  //===------------------------------------------------------------------===//1877  // Implementation for interface from ConstraintManager.1878  //===------------------------------------------------------------------===//1879 1880  bool haveEqualConstraints(ProgramStateRef S1,1881                            ProgramStateRef S2) const override {1882    // NOTE: ClassMembers are as simple as back pointers for ClassMap,1883    //       so comparing constraint ranges and class maps should be1884    //       sufficient.1885    return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() &&1886           S1->get<ClassMap>() == S2->get<ClassMap>();1887  }1888 1889  bool canReasonAbout(SVal X) const override;1890 1891  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;1892 1893  const llvm::APSInt *getSymVal(ProgramStateRef State,1894                                SymbolRef Sym) const override;1895 1896  const llvm::APSInt *getSymMinVal(ProgramStateRef State,1897                                   SymbolRef Sym) const override;1898 1899  const llvm::APSInt *getSymMaxVal(ProgramStateRef State,1900                                   SymbolRef Sym) const override;1901 1902  ProgramStateRef removeDeadBindings(ProgramStateRef State,1903                                     SymbolReaper &SymReaper) override;1904 1905  void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",1906                 unsigned int Space = 0, bool IsDot = false) const override;1907  void printValue(raw_ostream &Out, ProgramStateRef State,1908                  SymbolRef Sym) override;1909  void printConstraints(raw_ostream &Out, ProgramStateRef State,1910                        const char *NL = "\n", unsigned int Space = 0,1911                        bool IsDot = false) const;1912  void printEquivalenceClasses(raw_ostream &Out, ProgramStateRef State,1913                               const char *NL = "\n", unsigned int Space = 0,1914                               bool IsDot = false) const;1915  void printDisequalities(raw_ostream &Out, ProgramStateRef State,1916                          const char *NL = "\n", unsigned int Space = 0,1917                          bool IsDot = false) const;1918 1919  //===------------------------------------------------------------------===//1920  // Implementation for interface from RangedConstraintManager.1921  //===------------------------------------------------------------------===//1922 1923  ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,1924                              const llvm::APSInt &V,1925                              const llvm::APSInt &Adjustment) override;1926 1927  ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,1928                              const llvm::APSInt &V,1929                              const llvm::APSInt &Adjustment) override;1930 1931  ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,1932                              const llvm::APSInt &V,1933                              const llvm::APSInt &Adjustment) override;1934 1935  ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,1936                              const llvm::APSInt &V,1937                              const llvm::APSInt &Adjustment) override;1938 1939  ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,1940                              const llvm::APSInt &V,1941                              const llvm::APSInt &Adjustment) override;1942 1943  ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,1944                              const llvm::APSInt &V,1945                              const llvm::APSInt &Adjustment) override;1946 1947  ProgramStateRef assumeSymWithinInclusiveRange(1948      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,1949      const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;1950 1951  ProgramStateRef assumeSymOutsideInclusiveRange(1952      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,1953      const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;1954 1955private:1956  mutable RangeSet::Factory F;1957 1958  RangeSet getRange(ProgramStateRef State, SymbolRef Sym) const;1959  ProgramStateRef setRange(ProgramStateRef State, SymbolRef Sym,1960                           RangeSet Range);1961 1962  RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,1963                         const llvm::APSInt &Int,1964                         const llvm::APSInt &Adjustment) const;1965  RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,1966                         const llvm::APSInt &Int,1967                         const llvm::APSInt &Adjustment) const;1968  RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,1969                         const llvm::APSInt &Int,1970                         const llvm::APSInt &Adjustment) const;1971  RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,1972                         const llvm::APSInt &Int,1973                         const llvm::APSInt &Adjustment) const;1974  RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,1975                         const llvm::APSInt &Int,1976                         const llvm::APSInt &Adjustment) const;1977};1978 1979//===----------------------------------------------------------------------===//1980//                         Constraint assignment logic1981//===----------------------------------------------------------------------===//1982 1983/// ConstraintAssignorBase is a small utility class that unifies visitor1984/// for ranges with a visitor for constraints (rangeset/range/constant).1985///1986/// It is designed to have one derived class, but generally it can have more.1987/// Derived class can control which types we handle by defining methods of the1988/// following form:1989///1990///   bool handle${SYMBOL}To${CONSTRAINT}(const SYMBOL *Sym,1991///                                       CONSTRAINT Constraint);1992///1993/// where SYMBOL is the type of the symbol (e.g. SymSymExpr, SymbolCast, etc.)1994///       CONSTRAINT is the type of constraint (RangeSet/Range/Const)1995///       return value signifies whether we should try other handle methods1996///          (i.e. false would mean to stop right after calling this method)1997template <class Derived> class ConstraintAssignorBase {1998public:1999  using Const = const llvm::APSInt &;2000 2001#define DISPATCH(CLASS) return assign##CLASS##Impl(cast<CLASS>(Sym), Constraint)2002 2003#define ASSIGN(CLASS, TO, SYM, CONSTRAINT)                                     \2004  if (!static_cast<Derived *>(this)->assign##CLASS##To##TO(SYM, CONSTRAINT))   \2005  return false2006 2007  void assign(SymbolRef Sym, RangeSet Constraint) {2008    assignImpl(Sym, Constraint);2009  }2010 2011  bool assignImpl(SymbolRef Sym, RangeSet Constraint) {2012    switch (Sym->getKind()) {2013#define SYMBOL(Id, Parent)                                                     \2014  case SymExpr::Id##Kind:                                                      \2015    DISPATCH(Id);2016#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"2017    }2018    llvm_unreachable("Unknown SymExpr kind!");2019  }2020 2021#define DEFAULT_ASSIGN(Id)                                                     \2022  bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) {          \2023    return true;                                                               \2024  }                                                                            \2025  bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \2026  bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }2027 2028  // When we dispatch for constraint types, we first try to check2029  // if the new constraint is the constant and try the corresponding2030  // assignor methods.  If it didn't interrupt, we can proceed to the2031  // range, and finally to the range set.2032#define CONSTRAINT_DISPATCH(Id)                                                \2033  if (const llvm::APSInt *Const = Constraint.getConcreteValue()) {             \2034    ASSIGN(Id, Const, Sym, *Const);                                            \2035  }                                                                            \2036  if (Constraint.size() == 1) {                                                \2037    ASSIGN(Id, Range, Sym, *Constraint.begin());                               \2038  }                                                                            \2039  ASSIGN(Id, RangeSet, Sym, Constraint)2040 2041  // Our internal assign method first tries to call assignor methods for all2042  // constraint types that apply.  And if not interrupted, continues with its2043  // parent class.2044#define SYMBOL(Id, Parent)                                                     \2045  bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) {                  \2046    CONSTRAINT_DISPATCH(Id);                                                   \2047    DISPATCH(Parent);                                                          \2048  }                                                                            \2049  DEFAULT_ASSIGN(Id)2050#define ABSTRACT_SYMBOL(Id, Parent) SYMBOL(Id, Parent)2051#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"2052 2053  // Default implementations for the top class that doesn't have parents.2054  bool assignSymExprImpl(const SymExpr *Sym, RangeSet Constraint) {2055    CONSTRAINT_DISPATCH(SymExpr);2056    return true;2057  }2058  DEFAULT_ASSIGN(SymExpr);2059 2060#undef DISPATCH2061#undef CONSTRAINT_DISPATCH2062#undef DEFAULT_ASSIGN2063#undef ASSIGN2064};2065 2066/// A little component aggregating all of the reasoning we have about2067/// assigning new constraints to symbols.2068///2069/// The main purpose of this class is to associate constraints to symbols,2070/// and impose additional constraints on other symbols, when we can imply2071/// them.2072///2073/// It has a nice symmetry with SymbolicRangeInferrer.  When the latter2074/// can provide more precise ranges by looking into the operands of the2075/// expression in question, ConstraintAssignor looks into the operands2076/// to see if we can imply more from the new constraint.2077class ConstraintAssignor : public ConstraintAssignorBase<ConstraintAssignor> {2078public:2079  template <class ClassOrSymbol>2080  [[nodiscard]] static ProgramStateRef2081  assign(ProgramStateRef State, SValBuilder &Builder, RangeSet::Factory &F,2082         ClassOrSymbol CoS, RangeSet NewConstraint) {2083    if (!State || NewConstraint.isEmpty())2084      return nullptr;2085 2086    ConstraintAssignor Assignor{State, Builder, F};2087    return Assignor.assign(CoS, NewConstraint);2088  }2089 2090  /// Handle expressions like: a % b != 0.2091  template <typename SymT>2092  bool handleRemainderOp(const SymT *Sym, RangeSet Constraint) {2093    if (Sym->getOpcode() != BO_Rem)2094      return true;2095    // a % b != 0 implies that a != 0.2096    if (!Constraint.containsZero()) {2097      SVal SymSVal = Builder.makeSymbolVal(Sym->getLHS());2098      if (auto NonLocSymSVal = SymSVal.getAs<nonloc::SymbolVal>()) {2099        State = State->assume(*NonLocSymSVal, true);2100        if (!State)2101          return false;2102      }2103    }2104    return true;2105  }2106 2107  inline bool assignSymExprToConst(const SymExpr *Sym, Const Constraint);2108  inline bool assignSymIntExprToRangeSet(const SymIntExpr *Sym,2109                                         RangeSet Constraint) {2110    return handleRemainderOp(Sym, Constraint);2111  }2112  inline bool assignSymSymExprToRangeSet(const SymSymExpr *Sym,2113                                         RangeSet Constraint);2114 2115private:2116  ConstraintAssignor(ProgramStateRef State, SValBuilder &Builder,2117                     RangeSet::Factory &F)2118      : State(State), Builder(Builder), RangeFactory(F) {}2119  using Base = ConstraintAssignorBase<ConstraintAssignor>;2120 2121  /// Base method for handling new constraints for symbols.2122  [[nodiscard]] ProgramStateRef assign(SymbolRef Sym, RangeSet NewConstraint) {2123    // All constraints are actually associated with equivalence classes, and2124    // that's what we are going to do first.2125    State = assign(EquivalenceClass::find(State, Sym), NewConstraint);2126    if (!State)2127      return nullptr;2128 2129    // And after that we can check what other things we can get from this2130    // constraint.2131    Base::assign(Sym, NewConstraint);2132    return State;2133  }2134 2135  /// Base method for handling new constraints for classes.2136  [[nodiscard]] ProgramStateRef assign(EquivalenceClass Class,2137                                       RangeSet NewConstraint) {2138    // There is a chance that we might need to update constraints for the2139    // classes that are known to be disequal to Class.2140    //2141    // In order for this to be even possible, the new constraint should2142    // be simply a constant because we can't reason about range disequalities.2143    if (const llvm::APSInt *Point = NewConstraint.getConcreteValue()) {2144 2145      ConstraintRangeTy Constraints = State->get<ConstraintRange>();2146      ConstraintRangeTy::Factory &CF = State->get_context<ConstraintRange>();2147 2148      // Add new constraint.2149      Constraints = CF.add(Constraints, Class, NewConstraint);2150 2151      for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) {2152        RangeSet UpdatedConstraint = SymbolicRangeInferrer::inferRange(2153            RangeFactory, State, DisequalClass);2154 2155        UpdatedConstraint = RangeFactory.deletePoint(UpdatedConstraint, *Point);2156 2157        // If we end up with at least one of the disequal classes to be2158        // constrained with an empty range-set, the state is infeasible.2159        if (UpdatedConstraint.isEmpty())2160          return nullptr;2161 2162        Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint);2163      }2164      assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "2165                                         "a state with infeasible constraints");2166 2167      return setConstraints(State, Constraints);2168    }2169 2170    return setConstraint(State, Class, NewConstraint);2171  }2172 2173  ProgramStateRef trackDisequality(ProgramStateRef State, SymbolRef LHS,2174                                   SymbolRef RHS) {2175    return EquivalenceClass::markDisequal(RangeFactory, State, LHS, RHS);2176  }2177 2178  ProgramStateRef trackEquality(ProgramStateRef State, SymbolRef LHS,2179                                SymbolRef RHS) {2180    return EquivalenceClass::merge(RangeFactory, State, LHS, RHS);2181  }2182 2183  [[nodiscard]] std::optional<bool> interpreteAsBool(RangeSet Constraint) {2184    assert(!Constraint.isEmpty() && "Empty ranges shouldn't get here");2185 2186    if (Constraint.getConcreteValue())2187      return !Constraint.getConcreteValue()->isZero();2188 2189    if (!Constraint.containsZero())2190      return true;2191 2192    return std::nullopt;2193  }2194 2195  ProgramStateRef State;2196  SValBuilder &Builder;2197  RangeSet::Factory &RangeFactory;2198};2199 2200bool ConstraintAssignor::assignSymExprToConst(const SymExpr *Sym,2201                                              const llvm::APSInt &Constraint) {2202  llvm::SmallSet<EquivalenceClass, 4> SimplifiedClasses;2203  // Iterate over all equivalence classes and try to simplify them.2204  ClassMembersTy Members = State->get<ClassMembers>();2205  for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members) {2206    EquivalenceClass Class = ClassToSymbolSet.first;2207    State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);2208    if (!State)2209      return false;2210    SimplifiedClasses.insert(Class);2211  }2212 2213  // Trivial equivalence classes (those that have only one symbol member) are2214  // not stored in the State. Thus, we must skim through the constraints as2215  // well. And we try to simplify symbols in the constraints.2216  ConstraintRangeTy Constraints = State->get<ConstraintRange>();2217  for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {2218    EquivalenceClass Class = ClassConstraint.first;2219    if (SimplifiedClasses.count(Class)) // Already simplified.2220      continue;2221    State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);2222    if (!State)2223      return false;2224  }2225 2226  // We may have trivial equivalence classes in the disequality info as2227  // well, and we need to simplify them.2228  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();2229  for (std::pair<EquivalenceClass, ClassSet> DisequalityEntry :2230       DisequalityInfo) {2231    EquivalenceClass Class = DisequalityEntry.first;2232    ClassSet DisequalClasses = DisequalityEntry.second;2233    State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);2234    if (!State)2235      return false;2236  }2237 2238  return true;2239}2240 2241bool ConstraintAssignor::assignSymSymExprToRangeSet(const SymSymExpr *Sym,2242                                                    RangeSet Constraint) {2243  if (!handleRemainderOp(Sym, Constraint))2244    return false;2245 2246  std::optional<bool> ConstraintAsBool = interpreteAsBool(Constraint);2247 2248  if (!ConstraintAsBool)2249    return true;2250 2251  if (std::optional<bool> Equality = meansEquality(Sym)) {2252    // Here we cover two cases:2253    //   * if Sym is equality and the new constraint is true -> Sym's operands2254    //     should be marked as equal2255    //   * if Sym is disequality and the new constraint is false -> Sym's2256    //     operands should be also marked as equal2257    if (*Equality == *ConstraintAsBool) {2258      State = trackEquality(State, Sym->getLHS(), Sym->getRHS());2259    } else {2260      // Other combinations leave as with disequal operands.2261      State = trackDisequality(State, Sym->getLHS(), Sym->getRHS());2262    }2263 2264    if (!State)2265      return false;2266  }2267 2268  return true;2269}2270 2271} // end anonymous namespace2272 2273std::unique_ptr<ConstraintManager>2274ento::CreateRangeConstraintManager(ProgramStateManager &StMgr,2275                                   ExprEngine *Eng) {2276  return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());2277}2278 2279ConstraintMap ento::getConstraintMap(ProgramStateRef State) {2280  ConstraintMap::Factory &F = State->get_context<ConstraintMap>();2281  ConstraintMap Result = F.getEmptyMap();2282 2283  ConstraintRangeTy Constraints = State->get<ConstraintRange>();2284  for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {2285    EquivalenceClass Class = ClassConstraint.first;2286    SymbolSet ClassMembers = Class.getClassMembers(State);2287    assert(!ClassMembers.isEmpty() &&2288           "Class must always have at least one member!");2289 2290    SymbolRef Representative = *ClassMembers.begin();2291    Result = F.add(Result, Representative, ClassConstraint.second);2292  }2293 2294  return Result;2295}2296 2297//===----------------------------------------------------------------------===//2298//                     EqualityClass implementation details2299//===----------------------------------------------------------------------===//2300 2301LLVM_DUMP_METHOD void EquivalenceClass::dumpToStream(ProgramStateRef State,2302                                                     raw_ostream &os) const {2303  SymbolSet ClassMembers = getClassMembers(State);2304  for (const SymbolRef &MemberSym : ClassMembers) {2305    MemberSym->dump();2306    os << "\n";2307  }2308}2309 2310inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State,2311                                               SymbolRef Sym) {2312  assert(State && "State should not be null");2313  assert(Sym && "Symbol should not be null");2314  // We store far from all Symbol -> Class mappings2315  if (const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))2316    return *NontrivialClass;2317 2318  // This is a trivial class of Sym.2319  return Sym;2320}2321 2322inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F,2323                                               ProgramStateRef State,2324                                               SymbolRef First,2325                                               SymbolRef Second) {2326  EquivalenceClass FirstClass = find(State, First);2327  EquivalenceClass SecondClass = find(State, Second);2328 2329  return FirstClass.merge(F, State, SecondClass);2330}2331 2332inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F,2333                                               ProgramStateRef State,2334                                               EquivalenceClass Other) {2335  // It is already the same class.2336  if (*this == Other)2337    return State;2338 2339  // FIXME: As of now, we support only equivalence classes of the same type.2340  //        This limitation is connected to the lack of explicit casts in2341  //        our symbolic expression model.2342  //2343  //        That means that for `int x` and `char y` we don't distinguish2344  //        between these two very different cases:2345  //          * `x == y`2346  //          * `(char)x == y`2347  //2348  //        The moment we introduce symbolic casts, this restriction can be2349  //        lifted.2350  if (getType()->getCanonicalTypeUnqualified() !=2351      Other.getType()->getCanonicalTypeUnqualified())2352    return State;2353 2354  SymbolSet Members = getClassMembers(State);2355  SymbolSet OtherMembers = Other.getClassMembers(State);2356 2357  // We estimate the size of the class by the height of tree containing2358  // its members.  Merging is not a trivial operation, so it's easier to2359  // merge the smaller class into the bigger one.2360  if (Members.getHeight() >= OtherMembers.getHeight()) {2361    return mergeImpl(F, State, Members, Other, OtherMembers);2362  } else {2363    return Other.mergeImpl(F, State, OtherMembers, *this, Members);2364  }2365}2366 2367inline ProgramStateRef2368EquivalenceClass::mergeImpl(RangeSet::Factory &RangeFactory,2369                            ProgramStateRef State, SymbolSet MyMembers,2370                            EquivalenceClass Other, SymbolSet OtherMembers) {2371  // Essentially what we try to recreate here is some kind of union-find2372  // data structure.  It does have certain limitations due to persistence2373  // and the need to remove elements from classes.2374  //2375  // In this setting, EquialityClass object is the representative of the class2376  // or the parent element.  ClassMap is a mapping of class members to their2377  // parent. Unlike the union-find structure, they all point directly to the2378  // class representative because we don't have an opportunity to actually do2379  // path compression when dealing with immutability.  This means that we2380  // compress paths every time we do merges.  It also means that we lose2381  // the main amortized complexity benefit from the original data structure.2382  ConstraintRangeTy Constraints = State->get<ConstraintRange>();2383  ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();2384 2385  // 1. If the merged classes have any constraints associated with them, we2386  //    need to transfer them to the class we have left.2387  //2388  // Intersection here makes perfect sense because both of these constraints2389  // must hold for the whole new class.2390  if (std::optional<RangeSet> NewClassConstraint =2391          intersect(RangeFactory, getConstraint(State, *this),2392                    getConstraint(State, Other))) {2393    // NOTE: Essentially, NewClassConstraint should NEVER be infeasible because2394    //       range inferrer shouldn't generate ranges incompatible with2395    //       equivalence classes. However, at the moment, due to imperfections2396    //       in the solver, it is possible and the merge function can also2397    //       return infeasible states aka null states.2398    if (NewClassConstraint->isEmpty())2399      // Infeasible state2400      return nullptr;2401 2402    // No need in tracking constraints of a now-dissolved class.2403    Constraints = CRF.remove(Constraints, Other);2404    // Assign new constraints for this class.2405    Constraints = CRF.add(Constraints, *this, *NewClassConstraint);2406 2407    assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "2408                                       "a state with infeasible constraints");2409 2410    State = State->set<ConstraintRange>(Constraints);2411  }2412 2413  // 2. Get ALL equivalence-related maps2414  ClassMapTy Classes = State->get<ClassMap>();2415  ClassMapTy::Factory &CMF = State->get_context<ClassMap>();2416 2417  ClassMembersTy Members = State->get<ClassMembers>();2418  ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();2419 2420  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();2421  DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>();2422 2423  ClassSet::Factory &CF = State->get_context<ClassSet>();2424  SymbolSet::Factory &F = getMembersFactory(State);2425 2426  // 2. Merge members of the Other class into the current class.2427  SymbolSet NewClassMembers = MyMembers;2428  for (SymbolRef Sym : OtherMembers) {2429    NewClassMembers = F.add(NewClassMembers, Sym);2430    // *this is now the class for all these new symbols.2431    Classes = CMF.add(Classes, Sym, *this);2432  }2433 2434  // 3. Adjust member mapping.2435  //2436  // No need in tracking members of a now-dissolved class.2437  Members = MF.remove(Members, Other);2438  // Now only the current class is mapped to all the symbols.2439  Members = MF.add(Members, *this, NewClassMembers);2440 2441  // 4. Update disequality relations2442  ClassSet DisequalToOther = Other.getDisequalClasses(DisequalityInfo, CF);2443  // We are about to merge two classes but they are already known to be2444  // non-equal. This is a contradiction.2445  if (DisequalToOther.contains(*this))2446    return nullptr;2447 2448  if (!DisequalToOther.isEmpty()) {2449    ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo, CF);2450    DisequalityInfo = DF.remove(DisequalityInfo, Other);2451 2452    for (EquivalenceClass DisequalClass : DisequalToOther) {2453      DisequalToThis = CF.add(DisequalToThis, DisequalClass);2454 2455      // Disequality is a symmetric relation meaning that if2456      // DisequalToOther not null then the set for DisequalClass is not2457      // empty and has at least Other.2458      ClassSet OriginalSetLinkedToOther =2459          *DisequalityInfo.lookup(DisequalClass);2460 2461      // Other will be eliminated and we should replace it with the bigger2462      // united class.2463      ClassSet NewSet = CF.remove(OriginalSetLinkedToOther, Other);2464      NewSet = CF.add(NewSet, *this);2465 2466      DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);2467    }2468 2469    DisequalityInfo = DF.add(DisequalityInfo, *this, DisequalToThis);2470    State = State->set<DisequalityMap>(DisequalityInfo);2471  }2472 2473  // 5. Update the state2474  State = State->set<ClassMap>(Classes);2475  State = State->set<ClassMembers>(Members);2476 2477  return State;2478}2479 2480inline SymbolSet::Factory &2481EquivalenceClass::getMembersFactory(ProgramStateRef State) {2482  return State->get_context<SymbolSet>();2483}2484 2485SymbolSet EquivalenceClass::getClassMembers(ProgramStateRef State) const {2486  if (const SymbolSet *Members = State->get<ClassMembers>(*this))2487    return *Members;2488 2489  // This class is trivial, so we need to construct a set2490  // with just that one symbol from the class.2491  SymbolSet::Factory &F = getMembersFactory(State);2492  return F.add(F.getEmptySet(), getRepresentativeSymbol());2493}2494 2495bool EquivalenceClass::isTrivial(ProgramStateRef State) const {2496  return State->get<ClassMembers>(*this) == nullptr;2497}2498 2499bool EquivalenceClass::isTriviallyDead(ProgramStateRef State,2500                                       SymbolReaper &Reaper) const {2501  return isTrivial(State) && Reaper.isDead(getRepresentativeSymbol());2502}2503 2504inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF,2505                                                      ProgramStateRef State,2506                                                      SymbolRef First,2507                                                      SymbolRef Second) {2508  return markDisequal(RF, State, find(State, First), find(State, Second));2509}2510 2511inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF,2512                                                      ProgramStateRef State,2513                                                      EquivalenceClass First,2514                                                      EquivalenceClass Second) {2515  return First.markDisequal(RF, State, Second);2516}2517 2518inline ProgramStateRef2519EquivalenceClass::markDisequal(RangeSet::Factory &RF, ProgramStateRef State,2520                               EquivalenceClass Other) const {2521  // If we know that two classes are equal, we can only produce an infeasible2522  // state.2523  if (*this == Other) {2524    return nullptr;2525  }2526 2527  DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();2528  ConstraintRangeTy Constraints = State->get<ConstraintRange>();2529 2530  // Disequality is a symmetric relation, so if we mark A as disequal to B,2531  // we should also mark B as disequalt to A.2532  if (!addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, *this,2533                            Other) ||2534      !addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, Other,2535                            *this))2536    return nullptr;2537 2538  assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "2539                                     "a state with infeasible constraints");2540 2541  State = State->set<DisequalityMap>(DisequalityInfo);2542  State = State->set<ConstraintRange>(Constraints);2543 2544  return State;2545}2546 2547inline bool EquivalenceClass::addToDisequalityInfo(2548    DisequalityMapTy &Info, ConstraintRangeTy &Constraints,2549    RangeSet::Factory &RF, ProgramStateRef State, EquivalenceClass First,2550    EquivalenceClass Second) {2551 2552  // 1. Get all of the required factories.2553  DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>();2554  ClassSet::Factory &CF = State->get_context<ClassSet>();2555  ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();2556 2557  // 2. Add Second to the set of classes disequal to First.2558  const ClassSet *CurrentSet = Info.lookup(First);2559  ClassSet NewSet = CurrentSet ? *CurrentSet : CF.getEmptySet();2560  NewSet = CF.add(NewSet, Second);2561 2562  Info = F.add(Info, First, NewSet);2563 2564  // 3. If Second is known to be a constant, we can delete this point2565  //    from the constraint asociated with First.2566  //2567  //    So, if Second == 10, it means that First != 10.2568  //    At the same time, the same logic does not apply to ranges.2569  if (const RangeSet *SecondConstraint = Constraints.lookup(Second))2570    if (const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {2571 2572      RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(2573          RF, State, First.getRepresentativeSymbol());2574 2575      FirstConstraint = RF.deletePoint(FirstConstraint, *Point);2576 2577      // If the First class is about to be constrained with an empty2578      // range-set, the state is infeasible.2579      if (FirstConstraint.isEmpty())2580        return false;2581 2582      Constraints = CRF.add(Constraints, First, FirstConstraint);2583    }2584 2585  return true;2586}2587 2588inline std::optional<bool> EquivalenceClass::areEqual(ProgramStateRef State,2589                                                      SymbolRef FirstSym,2590                                                      SymbolRef SecondSym) {2591  return EquivalenceClass::areEqual(State, find(State, FirstSym),2592                                    find(State, SecondSym));2593}2594 2595inline std::optional<bool> EquivalenceClass::areEqual(ProgramStateRef State,2596                                                      EquivalenceClass First,2597                                                      EquivalenceClass Second) {2598  // The same equivalence class => symbols are equal.2599  if (First == Second)2600    return true;2601 2602  // Let's check if we know anything about these two classes being not equal to2603  // each other.2604  ClassSet DisequalToFirst = First.getDisequalClasses(State);2605  if (DisequalToFirst.contains(Second))2606    return false;2607 2608  // It is not clear.2609  return std::nullopt;2610}2611 2612[[nodiscard]] ProgramStateRef2613EquivalenceClass::removeMember(ProgramStateRef State, const SymbolRef Old) {2614 2615  SymbolSet ClsMembers = getClassMembers(State);2616  assert(ClsMembers.contains(Old));2617 2618  // Remove `Old`'s Class->Sym relation.2619  SymbolSet::Factory &F = getMembersFactory(State);2620  ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();2621  ClsMembers = F.remove(ClsMembers, Old);2622  // Ensure another precondition of the removeMember function (we can check2623  // this only with isEmpty, thus we have to do the remove first).2624  assert(!ClsMembers.isEmpty() &&2625         "Class should have had at least two members before member removal");2626  // Overwrite the existing members assigned to this class.2627  ClassMembersTy ClassMembersMap = State->get<ClassMembers>();2628  ClassMembersMap = EMFactory.add(ClassMembersMap, *this, ClsMembers);2629  State = State->set<ClassMembers>(ClassMembersMap);2630 2631  // Remove `Old`'s Sym->Class relation.2632  ClassMapTy Classes = State->get<ClassMap>();2633  ClassMapTy::Factory &CMF = State->get_context<ClassMap>();2634  Classes = CMF.remove(Classes, Old);2635  State = State->set<ClassMap>(Classes);2636 2637  return State;2638}2639 2640// Re-evaluate an SVal with top-level `State->assume` logic.2641[[nodiscard]] static ProgramStateRef2642reAssume(ProgramStateRef State, const RangeSet *Constraint, SVal TheValue) {2643  if (!Constraint)2644    return State;2645 2646  const auto DefinedVal = TheValue.castAs<DefinedSVal>();2647 2648  // If the SVal is 0, we can simply interpret that as `false`.2649  if (Constraint->encodesFalseRange())2650    return State->assume(DefinedVal, false);2651 2652  // If the constraint does not encode 0 then we can interpret that as `true`2653  // AND as a Range(Set).2654  if (Constraint->encodesTrueRange()) {2655    State = State->assume(DefinedVal, true);2656    if (!State)2657      return nullptr;2658    // Fall through, re-assume based on the range values as well.2659  }2660  // Overestimate the individual Ranges with the RangeSet' lowest and2661  // highest values.2662  return State->assumeInclusiveRange(DefinedVal, Constraint->getMinValue(),2663                                     Constraint->getMaxValue(), true);2664}2665 2666// Iterate over all symbols and try to simplify them. Once a symbol is2667// simplified then we check if we can merge the simplified symbol's equivalence2668// class to this class. This way, we simplify not just the symbols but the2669// classes as well: we strive to keep the number of the classes to be the2670// absolute minimum.2671[[nodiscard]] ProgramStateRef2672EquivalenceClass::simplify(SValBuilder &SVB, RangeSet::Factory &F,2673                           ProgramStateRef State, EquivalenceClass Class) {2674  SymbolSet ClassMembers = Class.getClassMembers(State);2675  for (const SymbolRef &MemberSym : ClassMembers) {2676 2677    const SVal SimplifiedMemberVal = simplifyToSVal(State, MemberSym);2678    const SymbolRef SimplifiedMemberSym = SimplifiedMemberVal.getAsSymbol();2679 2680    // The symbol is collapsed to a constant, check if the current State is2681    // still feasible.2682    if (const auto CI = SimplifiedMemberVal.getAs<nonloc::ConcreteInt>()) {2683      const llvm::APSInt &SV = CI->getValue();2684      const RangeSet *ClassConstraint = getConstraint(State, Class);2685      // We have found a contradiction.2686      if (ClassConstraint && !ClassConstraint->contains(SV))2687        return nullptr;2688    }2689 2690    if (SimplifiedMemberSym && MemberSym != SimplifiedMemberSym) {2691      // The simplified symbol should be the member of the original Class,2692      // however, it might be in another existing class at the moment. We2693      // have to merge these classes.2694      ProgramStateRef OldState = State;2695      State = merge(F, State, MemberSym, SimplifiedMemberSym);2696      if (!State)2697        return nullptr;2698      // No state change, no merge happened actually.2699      if (OldState == State)2700        continue;2701 2702      // Be aware that `SimplifiedMemberSym` might refer to an already dead2703      // symbol. In that case, the eqclass of that might not be the same as the2704      // eqclass of `MemberSym`. This is because the dead symbols are not2705      // preserved in the `ClassMap`, hence2706      // `find(State, SimplifiedMemberSym)` will result in a trivial eqclass2707      // compared to the eqclass of `MemberSym`.2708      // These eqclasses should be the same if `SimplifiedMemberSym` is alive.2709      // --> assert(find(State, MemberSym) == find(State, SimplifiedMemberSym))2710      //2711      // Note that `MemberSym` must be alive here since that is from the2712      // `ClassMembers` where all the symbols are alive.2713 2714      // Remove the old and more complex symbol.2715      State = find(State, MemberSym).removeMember(State, MemberSym);2716 2717      // Query the class constraint again b/c that may have changed during the2718      // merge above.2719      const RangeSet *ClassConstraint = getConstraint(State, Class);2720 2721      // Re-evaluate an SVal with top-level `State->assume`, this ignites2722      // a RECURSIVE algorithm that will reach a FIXPOINT.2723      //2724      // About performance and complexity: Let us assume that in a State we2725      // have N non-trivial equivalence classes and that all constraints and2726      // disequality info is related to non-trivial classes. In the worst case,2727      // we can simplify only one symbol of one class in each iteration. The2728      // number of symbols in one class cannot grow b/c we replace the old2729      // symbol with the simplified one. Also, the number of the equivalence2730      // classes can decrease only, b/c the algorithm does a merge operation2731      // optionally. We need N iterations in this case to reach the fixpoint.2732      // Thus, the steps needed to be done in the worst case is proportional to2733      // N*N.2734      //2735      // This worst case scenario can be extended to that case when we have2736      // trivial classes in the constraints and in the disequality map. This2737      // case can be reduced to the case with a State where there are only2738      // non-trivial classes. This is because a merge operation on two trivial2739      // classes results in one non-trivial class.2740      State = reAssume(State, ClassConstraint, SimplifiedMemberVal);2741      if (!State)2742        return nullptr;2743    }2744  }2745  return State;2746}2747 2748inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State,2749                                                     SymbolRef Sym) {2750  return find(State, Sym).getDisequalClasses(State);2751}2752 2753inline ClassSet2754EquivalenceClass::getDisequalClasses(ProgramStateRef State) const {2755  return getDisequalClasses(State->get<DisequalityMap>(),2756                            State->get_context<ClassSet>());2757}2758 2759inline ClassSet2760EquivalenceClass::getDisequalClasses(DisequalityMapTy Map,2761                                     ClassSet::Factory &Factory) const {2762  if (const ClassSet *DisequalClasses = Map.lookup(*this))2763    return *DisequalClasses;2764 2765  return Factory.getEmptySet();2766}2767 2768bool EquivalenceClass::isClassDataConsistent(ProgramStateRef State) {2769  ClassMembersTy Members = State->get<ClassMembers>();2770 2771  for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) {2772    for (SymbolRef Member : ClassMembersPair.second) {2773      // Every member of the class should have a mapping back to the class.2774      if (find(State, Member) == ClassMembersPair.first) {2775        continue;2776      }2777 2778      return false;2779    }2780  }2781 2782  DisequalityMapTy Disequalities = State->get<DisequalityMap>();2783  for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) {2784    EquivalenceClass Class = DisequalityInfo.first;2785    ClassSet DisequalClasses = DisequalityInfo.second;2786 2787    // There is no use in keeping empty sets in the map.2788    if (DisequalClasses.isEmpty())2789      return false;2790 2791    // Disequality is symmetrical, i.e. for every Class A and B that A != B,2792    // B != A should also be true.2793    for (EquivalenceClass DisequalClass : DisequalClasses) {2794      const ClassSet *DisequalToDisequalClasses =2795          Disequalities.lookup(DisequalClass);2796 2797      // It should be a set of at least one element: Class2798      if (!DisequalToDisequalClasses ||2799          !DisequalToDisequalClasses->contains(Class))2800        return false;2801    }2802  }2803 2804  return true;2805}2806 2807//===----------------------------------------------------------------------===//2808//                    RangeConstraintManager implementation2809//===----------------------------------------------------------------------===//2810 2811bool RangeConstraintManager::canReasonAbout(SVal X) const {2812  std::optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();2813  if (SymVal && SymVal->isExpression()) {2814    const SymExpr *SE = SymVal->getSymbol();2815 2816    if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {2817      switch (SIE->getOpcode()) {2818      // We don't reason yet about bitwise-constraints on symbolic values.2819      case BO_And:2820      case BO_Or:2821      case BO_Xor:2822        return false;2823      // We don't reason yet about these arithmetic constraints on2824      // symbolic values.2825      case BO_Mul:2826      case BO_Div:2827      case BO_Rem:2828      case BO_Shl:2829      case BO_Shr:2830        return false;2831      // All other cases.2832      default:2833        return true;2834      }2835    }2836 2837    if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {2838      // FIXME: Handle <=> here.2839      if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||2840          BinaryOperator::isRelationalOp(SSE->getOpcode())) {2841        // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.2842        // We've recently started producing Loc <> NonLoc comparisons (that2843        // result from casts of one of the operands between eg. intptr_t and2844        // void *), but we can't reason about them yet.2845        if (Loc::isLocType(SSE->getLHS()->getType())) {2846          return Loc::isLocType(SSE->getRHS()->getType());2847        }2848      }2849    }2850 2851    return false;2852  }2853 2854  return true;2855}2856 2857ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,2858                                                    SymbolRef Sym) {2859  const RangeSet *Ranges = getConstraint(State, Sym);2860 2861  // If we don't have any information about this symbol, it's underconstrained.2862  if (!Ranges)2863    return ConditionTruthVal();2864 2865  // If we have a concrete value, see if it's zero.2866  if (const llvm::APSInt *Value = Ranges->getConcreteValue())2867    return *Value == 0;2868 2869  BasicValueFactory &BV = getBasicVals();2870  APSIntType IntType = BV.getAPSIntType(Sym->getType());2871  llvm::APSInt Zero = IntType.getZeroValue();2872 2873  // Check if zero is in the set of possible values.2874  if (!Ranges->contains(Zero))2875    return false;2876 2877  // Zero is a possible value, but it is not the /only/ possible value.2878  return ConditionTruthVal();2879}2880 2881const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,2882                                                      SymbolRef Sym) const {2883  return getRange(St, Sym).getConcreteValue();2884}2885 2886const llvm::APSInt *RangeConstraintManager::getSymMinVal(ProgramStateRef St,2887                                                         SymbolRef Sym) const {2888  RangeSet Range = getRange(St, Sym);2889  return Range.isEmpty() ? nullptr : &Range.getMinValue();2890}2891 2892const llvm::APSInt *RangeConstraintManager::getSymMaxVal(ProgramStateRef St,2893                                                         SymbolRef Sym) const {2894  RangeSet Range = getRange(St, Sym);2895  return Range.isEmpty() ? nullptr : &Range.getMaxValue();2896}2897 2898//===----------------------------------------------------------------------===//2899//                Remove dead symbols from existing constraints2900//===----------------------------------------------------------------------===//2901 2902/// Scan all symbols referenced by the constraints. If the symbol is not alive2903/// as marked in LSymbols, mark it as dead in DSymbols.2904ProgramStateRef2905RangeConstraintManager::removeDeadBindings(ProgramStateRef State,2906                                           SymbolReaper &SymReaper) {2907  ClassMembersTy ClassMembersMap = State->get<ClassMembers>();2908  ClassMembersTy NewClassMembersMap = ClassMembersMap;2909  ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();2910  SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>();2911 2912  ConstraintRangeTy Constraints = State->get<ConstraintRange>();2913  ConstraintRangeTy NewConstraints = Constraints;2914  ConstraintRangeTy::Factory &ConstraintFactory =2915      State->get_context<ConstraintRange>();2916 2917  ClassMapTy Map = State->get<ClassMap>();2918  ClassMapTy NewMap = Map;2919  ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();2920 2921  DisequalityMapTy Disequalities = State->get<DisequalityMap>();2922  DisequalityMapTy::Factory &DisequalityFactory =2923      State->get_context<DisequalityMap>();2924  ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();2925 2926  bool ClassMapChanged = false;2927  bool MembersMapChanged = false;2928  bool ConstraintMapChanged = false;2929  bool DisequalitiesChanged = false;2930 2931  auto removeDeadClass = [&](EquivalenceClass Class) {2932    // Remove associated constraint ranges.2933    Constraints = ConstraintFactory.remove(Constraints, Class);2934    ConstraintMapChanged = true;2935 2936    // Update disequality information to not hold any information on the2937    // removed class.2938    ClassSet DisequalClasses =2939        Class.getDisequalClasses(Disequalities, ClassSetFactory);2940    if (!DisequalClasses.isEmpty()) {2941      for (EquivalenceClass DisequalClass : DisequalClasses) {2942        ClassSet DisequalToDisequalSet =2943            DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory);2944        // DisequalToDisequalSet is guaranteed to be non-empty for consistent2945        // disequality info.2946        assert(!DisequalToDisequalSet.isEmpty());2947        ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet, Class);2948 2949        // No need in keeping an empty set.2950        if (NewSet.isEmpty()) {2951          Disequalities =2952              DisequalityFactory.remove(Disequalities, DisequalClass);2953        } else {2954          Disequalities =2955              DisequalityFactory.add(Disequalities, DisequalClass, NewSet);2956        }2957      }2958      // Remove the data for the class2959      Disequalities = DisequalityFactory.remove(Disequalities, Class);2960      DisequalitiesChanged = true;2961    }2962  };2963 2964  // 1. Let's see if dead symbols are trivial and have associated constraints.2965  for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :2966       Constraints) {2967    EquivalenceClass Class = ClassConstraintPair.first;2968    if (Class.isTriviallyDead(State, SymReaper)) {2969      // If this class is trivial, we can remove its constraints right away.2970      removeDeadClass(Class);2971    }2972  }2973 2974  // 2. We don't need to track classes for dead symbols.2975  for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {2976    SymbolRef Sym = SymbolClassPair.first;2977 2978    if (SymReaper.isDead(Sym)) {2979      ClassMapChanged = true;2980      NewMap = ClassFactory.remove(NewMap, Sym);2981    }2982  }2983 2984  // 3. Remove dead members from classes and remove dead non-trivial classes2985  //    and their constraints.2986  for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :2987       ClassMembersMap) {2988    EquivalenceClass Class = ClassMembersPair.first;2989    SymbolSet LiveMembers = ClassMembersPair.second;2990    bool MembersChanged = false;2991 2992    for (SymbolRef Member : ClassMembersPair.second) {2993      if (SymReaper.isDead(Member)) {2994        MembersChanged = true;2995        LiveMembers = SetFactory.remove(LiveMembers, Member);2996      }2997    }2998 2999    // Check if the class changed.3000    if (!MembersChanged)3001      continue;3002 3003    MembersMapChanged = true;3004 3005    if (LiveMembers.isEmpty()) {3006      // The class is dead now, we need to wipe it out of the members map...3007      NewClassMembersMap = EMFactory.remove(NewClassMembersMap, Class);3008 3009      // ...and remove all of its constraints.3010      removeDeadClass(Class);3011    } else {3012      // We need to change the members associated with the class.3013      NewClassMembersMap =3014          EMFactory.add(NewClassMembersMap, Class, LiveMembers);3015    }3016  }3017 3018  // 4. Update the state with new maps.3019  //3020  // Here we try to be humble and update a map only if it really changed.3021  if (ClassMapChanged)3022    State = State->set<ClassMap>(NewMap);3023 3024  if (MembersMapChanged)3025    State = State->set<ClassMembers>(NewClassMembersMap);3026 3027  if (ConstraintMapChanged)3028    State = State->set<ConstraintRange>(Constraints);3029 3030  if (DisequalitiesChanged)3031    State = State->set<DisequalityMap>(Disequalities);3032 3033  assert(EquivalenceClass::isClassDataConsistent(State));3034 3035  return State;3036}3037 3038RangeSet RangeConstraintManager::getRange(ProgramStateRef State,3039                                          SymbolRef Sym) const {3040  return SymbolicRangeInferrer::inferRange(F, State, Sym);3041}3042 3043ProgramStateRef RangeConstraintManager::setRange(ProgramStateRef State,3044                                                 SymbolRef Sym,3045                                                 RangeSet Range) {3046  return ConstraintAssignor::assign(State, getSValBuilder(), F, Sym, Range);3047}3048 3049//===------------------------------------------------------------------------===3050// assumeSymX methods: protected interface for RangeConstraintManager.3051//===------------------------------------------------------------------------===3052 3053// The syntax for ranges below is mathematical, using [x, y] for closed ranges3054// and (x, y) for open ranges. These ranges are modular, corresponding with3055// a common treatment of C integer overflow. This means that these methods3056// do not have to worry about overflow; RangeSet::Intersect can handle such a3057// "wraparound" range.3058// As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,3059// UINT_MAX, 0, 1, and 2.3060 3061ProgramStateRef3062RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,3063                                    const llvm::APSInt &Int,3064                                    const llvm::APSInt &Adjustment) {3065  // Before we do any real work, see if the value can even show up.3066  APSIntType AdjustmentType(Adjustment);3067  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)3068    return St;3069 3070  llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;3071  RangeSet New = getRange(St, Sym);3072  New = F.deletePoint(New, Point);3073 3074  return setRange(St, Sym, New);3075}3076 3077ProgramStateRef3078RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,3079                                    const llvm::APSInt &Int,3080                                    const llvm::APSInt &Adjustment) {3081  // Before we do any real work, see if the value can even show up.3082  APSIntType AdjustmentType(Adjustment);3083  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)3084    return nullptr;3085 3086  // [Int-Adjustment, Int-Adjustment]3087  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;3088  RangeSet New = getRange(St, Sym);3089  New = F.intersect(New, AdjInt);3090 3091  return setRange(St, Sym, New);3092}3093 3094RangeSet3095RangeConstraintManager::getSymLTRange(ProgramStateRef St, SymbolRef Sym,3096                                      const llvm::APSInt &Int,3097                                      const llvm::APSInt &Adjustment) const {3098  // Before we do any real work, see if the value can even show up.3099  APSIntType AdjustmentType(Adjustment);3100  switch (AdjustmentType.testInRange(Int, true)) {3101  case APSIntType::RTR_Below:3102    return F.getEmptySet();3103  case APSIntType::RTR_Within:3104    break;3105  case APSIntType::RTR_Above:3106    return getRange(St, Sym);3107  }3108 3109  // Special case for Int == Min. This is always false.3110  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);3111  llvm::APSInt Min = AdjustmentType.getMinValue();3112  if (ComparisonVal == Min)3113    return F.getEmptySet();3114 3115  llvm::APSInt Lower = Min - Adjustment;3116  llvm::APSInt Upper = ComparisonVal - Adjustment;3117  --Upper;3118 3119  RangeSet Result = getRange(St, Sym);3120  return F.intersect(Result, Lower, Upper);3121}3122 3123ProgramStateRef3124RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,3125                                    const llvm::APSInt &Int,3126                                    const llvm::APSInt &Adjustment) {3127  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);3128  return setRange(St, Sym, New);3129}3130 3131RangeSet3132RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym,3133                                      const llvm::APSInt &Int,3134                                      const llvm::APSInt &Adjustment) const {3135  // Before we do any real work, see if the value can even show up.3136  APSIntType AdjustmentType(Adjustment);3137  switch (AdjustmentType.testInRange(Int, true)) {3138  case APSIntType::RTR_Below:3139    return getRange(St, Sym);3140  case APSIntType::RTR_Within:3141    break;3142  case APSIntType::RTR_Above:3143    return F.getEmptySet();3144  }3145 3146  // Special case for Int == Max. This is always false.3147  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);3148  llvm::APSInt Max = AdjustmentType.getMaxValue();3149  if (ComparisonVal == Max)3150    return F.getEmptySet();3151 3152  llvm::APSInt Lower = ComparisonVal - Adjustment;3153  llvm::APSInt Upper = Max - Adjustment;3154  ++Lower;3155 3156  RangeSet SymRange = getRange(St, Sym);3157  return F.intersect(SymRange, Lower, Upper);3158}3159 3160ProgramStateRef3161RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,3162                                    const llvm::APSInt &Int,3163                                    const llvm::APSInt &Adjustment) {3164  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);3165  return setRange(St, Sym, New);3166}3167 3168RangeSet3169RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym,3170                                      const llvm::APSInt &Int,3171                                      const llvm::APSInt &Adjustment) const {3172  // Before we do any real work, see if the value can even show up.3173  APSIntType AdjustmentType(Adjustment);3174  switch (AdjustmentType.testInRange(Int, true)) {3175  case APSIntType::RTR_Below:3176    return getRange(St, Sym);3177  case APSIntType::RTR_Within:3178    break;3179  case APSIntType::RTR_Above:3180    return F.getEmptySet();3181  }3182 3183  // Special case for Int == Min. This is always feasible.3184  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);3185  llvm::APSInt Min = AdjustmentType.getMinValue();3186  if (ComparisonVal == Min)3187    return getRange(St, Sym);3188 3189  llvm::APSInt Max = AdjustmentType.getMaxValue();3190  llvm::APSInt Lower = ComparisonVal - Adjustment;3191  llvm::APSInt Upper = Max - Adjustment;3192 3193  RangeSet SymRange = getRange(St, Sym);3194  return F.intersect(SymRange, Lower, Upper);3195}3196 3197ProgramStateRef3198RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,3199                                    const llvm::APSInt &Int,3200                                    const llvm::APSInt &Adjustment) {3201  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);3202  return setRange(St, Sym, New);3203}3204 3205RangeSet3206RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS,3207                                      const llvm::APSInt &Int,3208                                      const llvm::APSInt &Adjustment) const {3209  // Before we do any real work, see if the value can even show up.3210  APSIntType AdjustmentType(Adjustment);3211  switch (AdjustmentType.testInRange(Int, true)) {3212  case APSIntType::RTR_Below:3213    return F.getEmptySet();3214  case APSIntType::RTR_Within:3215    break;3216  case APSIntType::RTR_Above:3217    return RS();3218  }3219 3220  // Special case for Int == Max. This is always feasible.3221  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);3222  llvm::APSInt Max = AdjustmentType.getMaxValue();3223  if (ComparisonVal == Max)3224    return RS();3225 3226  llvm::APSInt Min = AdjustmentType.getMinValue();3227  llvm::APSInt Lower = Min - Adjustment;3228  llvm::APSInt Upper = ComparisonVal - Adjustment;3229 3230  RangeSet Default = RS();3231  return F.intersect(Default, Lower, Upper);3232}3233 3234RangeSet3235RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym,3236                                      const llvm::APSInt &Int,3237                                      const llvm::APSInt &Adjustment) const {3238  return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);3239}3240 3241ProgramStateRef3242RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,3243                                    const llvm::APSInt &Int,3244                                    const llvm::APSInt &Adjustment) {3245  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);3246  return setRange(St, Sym, New);3247}3248 3249ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(3250    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,3251    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {3252  RangeSet New = getSymGERange(State, Sym, From, Adjustment);3253  if (New.isEmpty())3254    return nullptr;3255  RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);3256  return setRange(State, Sym, Out);3257}3258 3259ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(3260    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,3261    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {3262  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);3263  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);3264  RangeSet New(F.add(RangeLT, RangeGT));3265  return setRange(State, Sym, New);3266}3267 3268//===----------------------------------------------------------------------===//3269// Pretty-printing.3270//===----------------------------------------------------------------------===//3271 3272void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,3273                                       const char *NL, unsigned int Space,3274                                       bool IsDot) const {3275  printConstraints(Out, State, NL, Space, IsDot);3276  printEquivalenceClasses(Out, State, NL, Space, IsDot);3277  printDisequalities(Out, State, NL, Space, IsDot);3278}3279 3280void RangeConstraintManager::printValue(raw_ostream &Out, ProgramStateRef State,3281                                        SymbolRef Sym) {3282  const RangeSet RS = getRange(State, Sym);3283  if (RS.isEmpty()) {3284    Out << "<empty rangeset>";3285    return;3286  }3287  Out << RS.getBitWidth() << (RS.isUnsigned() ? "u:" : "s:");3288  RS.dump(Out);3289}3290 3291static std::string toString(const SymbolRef &Sym) {3292  std::string S;3293  llvm::raw_string_ostream O(S);3294  Sym->dumpToStream(O);3295  return S;3296}3297 3298void RangeConstraintManager::printConstraints(raw_ostream &Out,3299                                              ProgramStateRef State,3300                                              const char *NL,3301                                              unsigned int Space,3302                                              bool IsDot) const {3303  ConstraintRangeTy Constraints = State->get<ConstraintRange>();3304 3305  Indent(Out, Space, IsDot) << "\"constraints\": ";3306  if (Constraints.isEmpty()) {3307    Out << "null," << NL;3308    return;3309  }3310 3311  std::map<std::string, RangeSet> OrderedConstraints;3312  for (std::pair<EquivalenceClass, RangeSet> P : Constraints) {3313    SymbolSet ClassMembers = P.first.getClassMembers(State);3314    for (const SymbolRef &ClassMember : ClassMembers) {3315      bool insertion_took_place;3316      std::tie(std::ignore, insertion_took_place) =3317          OrderedConstraints.insert({toString(ClassMember), P.second});3318      assert(insertion_took_place &&3319             "two symbols should not have the same dump");3320    }3321  }3322 3323  ++Space;3324  Out << '[' << NL;3325  bool First = true;3326  for (std::pair<std::string, RangeSet> P : OrderedConstraints) {3327    if (First) {3328      First = false;3329    } else {3330      Out << ',';3331      Out << NL;3332    }3333    Indent(Out, Space, IsDot)3334        << "{ \"symbol\": \"" << P.first << "\", \"range\": \"";3335    P.second.dump(Out);3336    Out << "\" }";3337  }3338  Out << NL;3339 3340  --Space;3341  Indent(Out, Space, IsDot) << "]," << NL;3342}3343 3344static std::string toString(ProgramStateRef State, EquivalenceClass Class) {3345  SymbolSet ClassMembers = Class.getClassMembers(State);3346  llvm::SmallVector<SymbolRef, 8> ClassMembersSorted(ClassMembers.begin(),3347                                                     ClassMembers.end());3348  llvm::sort(ClassMembersSorted,3349             [](const SymbolRef &LHS, const SymbolRef &RHS) {3350               return toString(LHS) < toString(RHS);3351             });3352 3353  bool FirstMember = true;3354 3355  std::string Str;3356  llvm::raw_string_ostream Out(Str);3357  Out << "[ ";3358  for (SymbolRef ClassMember : ClassMembersSorted) {3359    if (FirstMember)3360      FirstMember = false;3361    else3362      Out << ", ";3363    Out << "\"" << ClassMember << "\"";3364  }3365  Out << " ]";3366  return Str;3367}3368 3369void RangeConstraintManager::printEquivalenceClasses(raw_ostream &Out,3370                                                     ProgramStateRef State,3371                                                     const char *NL,3372                                                     unsigned int Space,3373                                                     bool IsDot) const {3374  ClassMembersTy Members = State->get<ClassMembers>();3375 3376  Indent(Out, Space, IsDot) << "\"equivalence_classes\": ";3377  if (Members.isEmpty()) {3378    Out << "null," << NL;3379    return;3380  }3381 3382  std::set<std::string> MembersStr;3383  for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members)3384    MembersStr.insert(toString(State, ClassToSymbolSet.first));3385 3386  ++Space;3387  Out << '[' << NL;3388  bool FirstClass = true;3389  for (const std::string &Str : MembersStr) {3390    if (FirstClass) {3391      FirstClass = false;3392    } else {3393      Out << ',';3394      Out << NL;3395    }3396    Indent(Out, Space, IsDot);3397    Out << Str;3398  }3399  Out << NL;3400 3401  --Space;3402  Indent(Out, Space, IsDot) << "]," << NL;3403}3404 3405void RangeConstraintManager::printDisequalities(raw_ostream &Out,3406                                                ProgramStateRef State,3407                                                const char *NL,3408                                                unsigned int Space,3409                                                bool IsDot) const {3410  DisequalityMapTy Disequalities = State->get<DisequalityMap>();3411 3412  Indent(Out, Space, IsDot) << "\"disequality_info\": ";3413  if (Disequalities.isEmpty()) {3414    Out << "null," << NL;3415    return;3416  }3417 3418  // Transform the disequality info to an ordered map of3419  // [string -> (ordered set of strings)]3420  using EqClassesStrTy = std::set<std::string>;3421  using DisequalityInfoStrTy = std::map<std::string, EqClassesStrTy>;3422  DisequalityInfoStrTy DisequalityInfoStr;3423  for (std::pair<EquivalenceClass, ClassSet> ClassToDisEqSet : Disequalities) {3424    EquivalenceClass Class = ClassToDisEqSet.first;3425    ClassSet DisequalClasses = ClassToDisEqSet.second;3426    EqClassesStrTy MembersStr;3427    for (EquivalenceClass DisEqClass : DisequalClasses)3428      MembersStr.insert(toString(State, DisEqClass));3429    DisequalityInfoStr.insert({toString(State, Class), MembersStr});3430  }3431 3432  ++Space;3433  Out << '[' << NL;3434  bool FirstClass = true;3435  for (std::pair<std::string, EqClassesStrTy> ClassToDisEqSet :3436       DisequalityInfoStr) {3437    const std::string &Class = ClassToDisEqSet.first;3438    if (FirstClass) {3439      FirstClass = false;3440    } else {3441      Out << ',';3442      Out << NL;3443    }3444    Indent(Out, Space, IsDot) << "{" << NL;3445    unsigned int DisEqSpace = Space + 1;3446    Indent(Out, DisEqSpace, IsDot) << "\"class\": ";3447    Out << Class;3448    const EqClassesStrTy &DisequalClasses = ClassToDisEqSet.second;3449    if (!DisequalClasses.empty()) {3450      Out << "," << NL;3451      Indent(Out, DisEqSpace, IsDot) << "\"disequal_to\": [" << NL;3452      unsigned int DisEqClassSpace = DisEqSpace + 1;3453      Indent(Out, DisEqClassSpace, IsDot);3454      bool FirstDisEqClass = true;3455      for (const std::string &DisEqClass : DisequalClasses) {3456        if (FirstDisEqClass) {3457          FirstDisEqClass = false;3458        } else {3459          Out << ',' << NL;3460          Indent(Out, DisEqClassSpace, IsDot);3461        }3462        Out << DisEqClass;3463      }3464      Out << "]" << NL;3465    }3466    Indent(Out, Space, IsDot) << "}";3467  }3468  Out << NL;3469 3470  --Space;3471  Indent(Out, Space, IsDot) << "]," << NL;3472}3473