[analyzer] Prepare structures for integral cast feature introducing

[ASDenysPetrov]

Summary

Change structures of storing bindings between Symbols and Equivalent Classes.
Add a Bitwidth characteristic as a common feature of integral Symbol to make (char)(int x) and (uchar)(int x) treated under the same Equivalent Class.

The link Symbol - Class was direct and now it depends on the effective (minimal) Bitwidth of the Symbol.
The link Class - Symbol stays as previously.

effective bitwidth - a bitwidth which is enough to hold all feasible values of the symbol. E.g. for (unsigned short)(char)(int)x, the symbol has a type of unsigned short but in range [0, 255] because it is restricted by the size of char during casting.

Some test cases are affected by regression for the sake of the next patch which will fix it.

This patch does not introduce integral casts but prepares the field for the core patch.

[steakhal]

I spent some time on this patch. But I'm left thinking about why we need the extra indirection?
Couldn't we just use a std::pair<sym,width> pair as a key instead?
You mention effective bitwidths in your summary, but the code does not mention this concept.
Maybe you could elaborate on what effective bitwidth means in this context and how this changes the eqclass lookups.
In addition to this, I'd be curious about an informal proof of the correctness.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

 //== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines RangeConstraintManager, a class that tracks simple
 //  equality and inequality constraints on symbolic values of ProgramState.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Basic/JsonSupport.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"

 
 LLVM_DUMP_METHOD void RangeSet::dump(raw_ostream &OS) const {
   OS << "{ ";
   llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(OS); });
   OS << " }";
 }
 LLVM_DUMP_METHOD void RangeSet::dump() const { dump(llvm::errs()); }
 
-REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
-
 namespace {
 class EquivalenceClass;
+using BitWidthType = uint32_t;
 } // end anonymous namespace
 
-REGISTER_MAP_WITH_PROGRAMSTATE(ClassMap, SymbolRef, EquivalenceClass)
+REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
+REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass)
+REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(ClassMap, BitWidthType, EquivalenceClass)
+
+REGISTER_MAP_WITH_PROGRAMSTATE(SymClassMap, SymbolRef, ClassMap)
 REGISTER_MAP_WITH_PROGRAMSTATE(ClassMembers, EquivalenceClass, SymbolSet)
 REGISTER_MAP_WITH_PROGRAMSTATE(ConstraintRange, EquivalenceClass, RangeSet)
-
-REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass)
 REGISTER_MAP_WITH_PROGRAMSTATE(DisequalityMap, EquivalenceClass, ClassSet)
 
 namespace {
 /// This class encapsulates a set of symbols equal to each other.
 ///
 /// The main idea of the approach requiring such classes is in narrowing
 /// and sharing constraints between symbols within the class.  Also we can
 /// conclude that there is no practical need in storing constraints for
public:
   /// Check equivalence data for consistency.
   [[nodiscard]] LLVM_ATTRIBUTE_UNUSED static bool
   isClassDataConsistent(ProgramStateRef State);
 
   [[nodiscard]] QualType getType() const {
     return getRepresentativeSymbol()->getType();
   }
 
-  EquivalenceClass() = delete;
+  EquivalenceClass() = default;
   EquivalenceClass(const EquivalenceClass &) = default;
-  EquivalenceClass &operator=(const EquivalenceClass &) = delete;
-  EquivalenceClass(EquivalenceClass &&) = default;
-  EquivalenceClass &operator=(EquivalenceClass &&) = delete;
+  EquivalenceClass(SymbolRef Sym) : ID(reinterpret_cast<uintptr_t>(Sym)) {}
+  EquivalenceClass &operator=(const EquivalenceClass &) = default;
 
   bool operator==(const EquivalenceClass &Other) const {
     return ID == Other.ID;
   }
   bool operator<(const EquivalenceClass &Other) const { return ID < Other.ID; }
   bool operator!=(const EquivalenceClass &Other) const {
     return !operator==(Other);
   }
 
   static void Profile(llvm::FoldingSetNodeID &ID, uintptr_t CID) {
     ID.AddInteger(CID);
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, this->ID); }
 
 private:
-  /* implicit */ EquivalenceClass(SymbolRef Sym)
-      : ID(reinterpret_cast<uintptr_t>(Sym)) {}
-
   /// This function is intended to be used ONLY within the class.
   /// The fact that ID is a pointer to a symbol is an implementation detail
   /// and should stay that way.
   /// In the current implementation, we use it to retrieve the only member
   /// of the trivial class.
   SymbolRef getRepresentativeSymbol() const {
     return reinterpret_cast<SymbolRef>(ID);
   }
   static inline SymbolSet::Factory &getMembersFactory(ProgramStateRef State);
 
   inline ProgramStateRef mergeImpl(RangeSet::Factory &F, ProgramStateRef State,
                                    SymbolSet Members, EquivalenceClass Other,
                                    SymbolSet OtherMembers);
 
   static inline bool
   addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
                        RangeSet::Factory &F, ProgramStateRef State,
                        EquivalenceClass First, EquivalenceClass Second);
 
   /// This is a unique identifier of the class.
-  uintptr_t ID;
+  uintptr_t ID = 0;
 };
 
+using MinBitWidthAndSymbolRoot = std::pair<BitWidthType, SymbolRef>;
+static MinBitWidthAndSymbolRoot parseSymbolCast(ProgramStateRef State,
+                                                SymbolRef Sym) {
+  ASTContext &C = State->getStateManager().getContext();
+  const QualType Ty = Sym->getType();
+  BitWidthType MinBitWidth = C.getIntWidth(Ty);
+  while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) {
+    Sym = SC->getOperand();
+    const QualType Ty = Sym->getType();
+    const BitWidthType BitWidth = C.getIntWidth(Ty);
+    if (MinBitWidth > BitWidth)
+      MinBitWidth = BitWidth;
+  }
+  return {MinBitWidth, Sym};
+}
+
 //===----------------------------------------------------------------------===//
 //                             Constraint functions
 //===----------------------------------------------------------------------===//
 
 [[nodiscard]] LLVM_ATTRIBUTE_UNUSED bool
 areFeasible(ConstraintRangeTy Constraints) {
   return llvm::none_of(
       Constraints,
ConstraintAssignor(ProgramStateRef State, SValBuilder &Builder,
                      RangeSet::Factory &F)
       : State(State), Builder(Builder), RangeFactory(F) {}
   using Base = ConstraintAssignorBase<ConstraintAssignor>;
 
   /// Base method for handling new constraints for symbols.
   [[nodiscard]] ProgramStateRef assign(SymbolRef Sym, RangeSet NewConstraint) {
     // All constraints are actually associated with equivalence classes, and
     // that's what we are going to do first.
-    State = assign(EquivalenceClass::find(State, Sym), NewConstraint);
+    ClassMap::Factory &CMF = State->get_context<ClassMap>();
+    MinBitWidthAndSymbolRoot MBWSR = parseSymbolCast(State, Sym);
+    const ClassMap *CMPtr = State->get<SymClassMap>(MBWSR.second);
+    const EquivalenceClass *ECPtr =
+        CMPtr ? CMPtr->lookup(MBWSR.first) : nullptr;
+    ClassMap CM = CMPtr ? *CMPtr : CMF.getEmptyMap();
+    EquivalenceClass EC;
+    if (!CMPtr || !ECPtr) {
+      EC = EquivalenceClass{Sym};
+      CM = CMF.add(CM, MBWSR.first, EC);
+      State = State->set<SymClassMap>(MBWSR.second, CM);
+    } else {
+      EC = *ECPtr;
+    }
+
+    State = assign(EC, NewConstraint);
     if (!State)
       return nullptr;
 
     // And after that we can check what other things we can get from this
     // constraint.
     Base::assign(Sym, NewConstraint);
     return State;
   }
for (const SymbolRef &MemberSym : ClassMembers) {
     os << "\n";
   }
 }
 
 inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State,
                                                SymbolRef Sym) {
   assert(State && "State should not be null");
   assert(Sym && "Symbol should not be null");
+  MinBitWidthAndSymbolRoot MBWSR = parseSymbolCast(State, Sym);
   // We store far from all Symbol -> Class mappings
-  if (const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))
-    return *NontrivialClass;
+  if (const ClassMap *CM = State->get<SymClassMap>(MBWSR.second))
+    if (const EquivalenceClass *EC = CM->lookup(MBWSR.first))
+      return *EC;
 
   // This is a trivial class of Sym.
   return Sym;
 }
 
 inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F,
                                                ProgramStateRef State,
                                                SymbolRef First,
if (Optional<RangeSet> NewClassConstraint =
 
     assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "
                                        "a state with infeasible constraints");
 
     State = State->set<ConstraintRange>(Constraints);
   }
 
   // 2. Get ALL equivalence-related maps
-  ClassMapTy Classes = State->get<ClassMap>();
-  ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
+  ClassMap::Factory &CMF = State->get_context<ClassMap>();
 
   ClassMembersTy Members = State->get<ClassMembers>();
   ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();
 
   DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
   DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>();
 
   ClassSet::Factory &CF = State->get_context<ClassSet>();
   SymbolSet::Factory &F = getMembersFactory(State);
 
   // 2. Merge members of the Other class into the current class.
   SymbolSet NewClassMembers = MyMembers;
+
+  auto AccociateSymWithThisClass = [&](SymbolRef Sym) {
+    MinBitWidthAndSymbolRoot MBWSR = parseSymbolCast(State, Sym);
+    const ClassMap *CM = State->get<SymClassMap>(MBWSR.second);
+    ClassMap NewCM = CM ? *CM : CMF.getEmptyMap();
+    NewCM = CMF.add(NewCM, MBWSR.first, *this);
+    State = State->set<SymClassMap>(MBWSR.second, NewCM);
+  };
+
+  // This is the last time we see this class trivial.
+  if (isTrivial(State))
+    AccociateSymWithThisClass(getRepresentativeSymbol());
+
   for (SymbolRef Sym : OtherMembers) {
     NewClassMembers = F.add(NewClassMembers, Sym);
-    // *this is now the class for all these new symbols.
-    Classes = CMF.add(Classes, Sym, *this);
+    AccociateSymWithThisClass(Sym);
   }
 
   // 3. Adjust member mapping.
   //
   // No need in tracking members of a now-dissolved class.
   Members = MF.remove(Members, Other);
   // Now only the current class is mapped to all the symbols.
   Members = MF.add(Members, *this, NewClassMembers);
for (EquivalenceClass DisequalClass : DisequalToOther) {
       DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);
     }
 
     DisequalityInfo = DF.add(DisequalityInfo, *this, DisequalToThis);
     State = State->set<DisequalityMap>(DisequalityInfo);
   }
 
   // 5. Update the state
-  State = State->set<ClassMap>(Classes);
   State = State->set<ClassMembers>(Members);
 
   return State;
 }
 
 inline SymbolSet::Factory &
 EquivalenceClass::getMembersFactory(ProgramStateRef State) {
   return State->get_context<SymbolSet>();
EquivalenceClass::removeMember(ProgramStateRef State, const SymbolRef Old) {
   assert(!ClsMembers.isEmpty() &&
          "Class should have had at least two members before member removal");
   // Overwrite the existing members assigned to this class.
   ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
   ClassMembersMap = EMFactory.add(ClassMembersMap, *this, ClsMembers);
   State = State->set<ClassMembers>(ClassMembersMap);
 
   // Remove `Old`'s Sym->Class relation.
-  ClassMapTy Classes = State->get<ClassMap>();
-  ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
-  Classes = CMF.remove(Classes, Old);
-  State = State->set<ClassMap>(Classes);
+  ClassMap::Factory &CMF = State->get_context<ClassMap>();
+  MinBitWidthAndSymbolRoot MBWSR = parseSymbolCast(State, Old);
+  if (const ClassMap *CM = State->get<SymClassMap>(MBWSR.second)) {
+    ClassMap NewCM = CMF.remove(*CM, MBWSR.first);
+    State = State->set<SymClassMap>(MBWSR.second, NewCM);
+  }
 
   return State;
 }
 
 // Re-evaluate an SVal with top-level `State->assume` logic.
 [[nodiscard]] ProgramStateRef
 reAssume(ProgramStateRef State, const RangeSet *Constraint, SVal TheValue) {
   if (!Constraint)
RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
   ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
   SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>();
 
   ConstraintRangeTy Constraints = State->get<ConstraintRange>();
   ConstraintRangeTy NewConstraints = Constraints;
   ConstraintRangeTy::Factory &ConstraintFactory =
       State->get_context<ConstraintRange>();
 
-  ClassMapTy Map = State->get<ClassMap>();
-  ClassMapTy NewMap = Map;
-  ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();
+  SymClassMapTy SCM = State->get<SymClassMap>();
+  SymClassMapTy NewSCM = SCM;
+  SymClassMapTy::Factory &SCMFactory = State->get_context<SymClassMap>();
 
   DisequalityMapTy Disequalities = State->get<DisequalityMap>();
   DisequalityMapTy::Factory &DisequalityFactory =
       State->get_context<DisequalityMap>();
   ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();
 
-  bool ClassMapChanged = false;
+  bool SymClassMapChanged = false;
   bool MembersMapChanged = false;
   bool ConstraintMapChanged = false;
   bool DisequalitiesChanged = false;
 
   auto removeDeadClass = [&](EquivalenceClass Class) {
     // Remove associated constraint ranges.
     Constraints = ConstraintFactory.remove(Constraints, Class);
     ConstraintMapChanged = true;
for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :
     EquivalenceClass Class = ClassConstraintPair.first;
     if (Class.isTriviallyDead(State, SymReaper)) {
       // If this class is trivial, we can remove its constraints right away.
       removeDeadClass(Class);
     }
   }
 
   // 2. We don't need to track classes for dead symbols.
-  for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {
+  AnalyzerOptions &Opts = State->getAnalysisManager().getAnalyzerOptions();
+  if (!Opts.ShouldSupportSymbolicIntegerCasts)
+    for (std::pair<SymbolRef, ClassMap> SymbolClassPair : SCM) {
       SymbolRef Sym = SymbolClassPair.first;
 
       if (SymReaper.isDead(Sym)) {
-      ClassMapChanged = true;
-      NewMap = ClassFactory.remove(NewMap, Sym);
-    }
+        SymClassMapChanged = true;
+        NewSCM = SCMFactory.remove(NewSCM, Sym);
       }
+    };
 
   // 3. Remove dead members from classes and remove dead non-trivial classes
   //    and their constraints.
   for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :
        ClassMembersMap) {
     EquivalenceClass Class = ClassMembersPair.first;
     SymbolSet LiveMembers = ClassMembersPair.second;
     bool MembersChanged = false;
if (LiveMembers.isEmpty()) {
       NewClassMembersMap =
           EMFactory.add(NewClassMembersMap, Class, LiveMembers);
     }
   }
 
   // 4. Update the state with new maps.
   //
   // Here we try to be humble and update a map only if it really changed.
-  if (ClassMapChanged)
-    State = State->set<ClassMap>(NewMap);
+  if (SymClassMapChanged)
+    State = State->set<SymClassMap>(NewSCM);
 
   if (MembersMapChanged)
     State = State->set<ClassMembers>(NewClassMembersMap);
 
   if (ConstraintMapChanged)
     State = State->set<ConstraintRange>(Constraints);
 
   if (DisequalitiesChanged)

clang/test/Analysis/svalbuilder-casts.cpp

void test1(int x, int y) {
   static_assert((short)65536 == 0, "");
   static_assert((short)-65536 == 0, "");
   static_assert((short)131072 == 0, "");
   static_assert((short)-131072 == 0, "");
   clang_analyzer_eval(x == 0);       // expected-warning{{UNKNOWN}}
 
   // These are not truncated to short as zero.
   static_assert((short)1 != 0, "");
-  clang_analyzer_eval(x == 1);       // expected-warning{{FALSE}}
+  clang_analyzer_eval(x == 1);       // expected-warning{{UNKNOWN}}
   static_assert((short)-1 != 0, "");
-  clang_analyzer_eval(x == -1);      // expected-warning{{FALSE}}
+  clang_analyzer_eval(x == -1);      // expected-warning{{UNKNOWN}}
   static_assert((short)65537 != 0, "");
-  clang_analyzer_eval(x == 65537);   // expected-warning{{FALSE}}
+  clang_analyzer_eval(x == 65537);   // expected-warning{{UNKNOWN}}
   static_assert((short)-65537 != 0, "");
-  clang_analyzer_eval(x == -65537);  // expected-warning{{FALSE}}
+  clang_analyzer_eval(x == -65537);  // expected-warning{{UNKNOWN}}
   static_assert((short)131073 != 0, "");
-  clang_analyzer_eval(x == 131073);  // expected-warning{{FALSE}}
+  clang_analyzer_eval(x == 131073);  // expected-warning{{UNKNOWN}}
   static_assert((short)-131073 != 0, "");
-  clang_analyzer_eval(x == -131073); // expected-warning{{FALSE}}
+  clang_analyzer_eval(x == -131073); // expected-warning{{UNKNOWN}}
 
   // Check for implicit cast.
   short s = y;
   assert(s == 0);
   clang_analyzer_eval(y == 0); // expected-warning{{UNKNOWN}}
 }