//== 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/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" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> #include <iterator> #include <optional> usingnamespaceclang; usingnamespaceento; // This class can be extended with other tables which will help to reason // about ranges more precisely. class OperatorRelationsTable { … }; //===----------------------------------------------------------------------===// // RangeSet implementation //===----------------------------------------------------------------------===// RangeSet::ContainerType RangeSet::Factory::EmptySet{ … }; RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) { … } RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) { … } RangeSet RangeSet::Factory::add(RangeSet Original, const llvm::APSInt &Point) { … } RangeSet RangeSet::Factory::unite(RangeSet LHS, RangeSet RHS) { … } RangeSet RangeSet::Factory::unite(RangeSet Original, Range R) { … } RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) { … } RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt From, llvm::APSInt To) { … } template <typename T> void swapIterators(T &First, T &FirstEnd, T &Second, T &SecondEnd) { … } RangeSet::ContainerType RangeSet::Factory::unite(const ContainerType &LHS, const ContainerType &RHS) { … } RangeSet RangeSet::Factory::getRangeSet(Range From) { … } RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) { … } RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) { … } const llvm::APSInt &RangeSet::getMinValue() const { … } const llvm::APSInt &RangeSet::getMaxValue() const { … } bool clang::ento::RangeSet::isUnsigned() const { … } uint32_t clang::ento::RangeSet::getBitWidth() const { … } APSIntType clang::ento::RangeSet::getAPSIntType() const { … } bool RangeSet::containsImpl(llvm::APSInt &Point) const { … } bool RangeSet::pin(llvm::APSInt &Point) const { … } bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const { … } RangeSet RangeSet::Factory::intersect(RangeSet What, llvm::APSInt Lower, llvm::APSInt Upper) { … } RangeSet RangeSet::Factory::intersect(const RangeSet::ContainerType &LHS, const RangeSet::ContainerType &RHS) { … } RangeSet RangeSet::Factory::intersect(RangeSet LHS, RangeSet RHS) { … } RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) { … } RangeSet RangeSet::Factory::negate(RangeSet What) { … } // Convert range set to the given integral type using truncation and promotion. // This works similar to APSIntType::apply function but for the range set. RangeSet RangeSet::Factory::castTo(RangeSet What, APSIntType Ty) { … } RangeSet RangeSet::Factory::castTo(RangeSet What, QualType T) { … } RangeSet::ContainerType RangeSet::Factory::truncateTo(RangeSet What, APSIntType Ty) { … } // Divide the convertion into two phases (presented as loops here). // First phase(loop) works when casted values go in ascending order. // E.g. char{1,3,5,127} -> uint{1,3,5,127} // Interrupt the first phase and go to second one when casted values start // go in descending order. That means that we crossed over the middle of // the type value set (aka 0 for signeds and MAX/2+1 for unsigneds). // For instance: // 1: uchar{1,3,5,128,255} -> char{1,3,5,-128,-1} // Here we put {1,3,5} to one array and {-128, -1} to another // 2: char{-128,-127,-1,0,1,2} -> uchar{128,129,255,0,1,3} // Here we put {128,129,255} to one array and {0,1,3} to another. // After that we unite both arrays. // NOTE: We don't just concatenate the arrays, because they may have // adjacent ranges, e.g.: // 1: char(-128, 127) -> uchar -> arr1(128, 255), arr2(0, 127) -> // unite -> uchar(0, 255) // 2: uchar(0, 1)U(254, 255) -> char -> arr1(0, 1), arr2(-2, -1) -> // unite -> uchar(-2, 1) RangeSet::ContainerType RangeSet::Factory::convertTo(RangeSet What, APSIntType Ty) { … } /// Promotion from unsigneds to signeds/unsigneds left. RangeSet::ContainerType RangeSet::Factory::promoteTo(RangeSet What, APSIntType Ty) { … } RangeSet RangeSet::Factory::deletePoint(RangeSet From, const llvm::APSInt &Point) { … } LLVM_DUMP_METHOD void Range::dump(raw_ostream &OS) const { … } LLVM_DUMP_METHOD void Range::dump() const { … } LLVM_DUMP_METHOD void RangeSet::dump(raw_ostream &OS) const { … } LLVM_DUMP_METHOD void RangeSet::dump() const { … } REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(…) namespace { class EquivalenceClass; } // end anonymous namespace REGISTER_MAP_WITH_PROGRAMSTATE(…) REGISTER_MAP_WITH_PROGRAMSTATE(…) REGISTER_MAP_WITH_PROGRAMSTATE(…) REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(…) REGISTER_MAP_WITH_PROGRAMSTATE(…) 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 /// every member of the class separately. /// /// Main terminology: /// /// * "Equivalence class" is an object of this class, which can be efficiently /// compared to other classes. It represents the whole class without /// storing the actual in it. The members of the class however can be /// retrieved from the state. /// /// * "Class members" are the symbols corresponding to the class. This means /// that A == B for every member symbols A and B from the class. Members of /// each class are stored in the state. /// /// * "Trivial class" is a class that has and ever had only one same symbol. /// /// * "Merge operation" merges two classes into one. It is the main operation /// to produce non-trivial classes. /// If, at some point, we can assume that two symbols from two distinct /// classes are equal, we can merge these classes. class EquivalenceClass : public llvm::FoldingSetNode { … }; //===----------------------------------------------------------------------===// // Constraint functions //===----------------------------------------------------------------------===// [[nodiscard]] LLVM_ATTRIBUTE_UNUSED bool areFeasible(ConstraintRangeTy Constraints) { … } [[nodiscard]] inline const RangeSet *getConstraint(ProgramStateRef State, EquivalenceClass Class) { … } [[nodiscard]] inline const RangeSet *getConstraint(ProgramStateRef State, SymbolRef Sym) { … } [[nodiscard]] ProgramStateRef setConstraint(ProgramStateRef State, EquivalenceClass Class, RangeSet Constraint) { … } [[nodiscard]] ProgramStateRef setConstraints(ProgramStateRef State, ConstraintRangeTy Constraints) { … } //===----------------------------------------------------------------------===// // Equality/diseqiality abstraction //===----------------------------------------------------------------------===// /// A small helper function for detecting symbolic (dis)equality. /// /// Equality check can have different forms (like a == b or a - b) and this /// class encapsulates those away if the only thing the user wants to check - /// whether it's equality/diseqiality or not. /// /// \returns true if assuming this Sym to be true means equality of operands /// false if it means disequality of operands /// std::nullopt otherwise std::optional<bool> meansEquality(const SymSymExpr *Sym) { … } //===----------------------------------------------------------------------===// // Intersection functions //===----------------------------------------------------------------------===// template <class SecondTy, class... RestTy> [[nodiscard]] inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head, SecondTy Second, RestTy... Tail); template <class... RangeTy> struct IntersectionTraits; IntersectionTraits<RangeSet, TailTy...>; template <> struct IntersectionTraits<> { … }; IntersectionTraits<OptionalOrPointer, TailTy...>; template <class EndTy> [[nodiscard]] inline EndTy intersect(RangeSet::Factory &F, EndTy End) { … } [[nodiscard]] LLVM_ATTRIBUTE_UNUSED inline std::optional<RangeSet> intersect(RangeSet::Factory &F, const RangeSet *End) { … } template <class... RestTy> [[nodiscard]] inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head, RangeSet Second, RestTy... Tail) { … } template <class SecondTy, class... RestTy> [[nodiscard]] inline RangeSet intersect(RangeSet::Factory &F, RangeSet Head, SecondTy Second, RestTy... Tail) { … } /// Main generic intersect function. /// It intersects all of the given range sets. If some of the given arguments /// don't hold a range set (nullptr or std::nullopt), the function will skip /// them. /// /// Available representations for the arguments are: /// * RangeSet /// * std::optional<RangeSet> /// * RangeSet * /// Pointer to a RangeSet is automatically assumed to be nullable and will get /// checked as well as the optional version. If this behaviour is undesired, /// please dereference the pointer in the call. /// /// Return type depends on the arguments' types. If we can be sure in compile /// time that there will be a range set as a result, the returning type is /// simply RangeSet, in other cases we have to back off to /// std::optional<RangeSet>. /// /// Please, prefer optional range sets to raw pointers. If the last argument is /// a raw pointer and all previous arguments are std::nullopt, it will cost one /// additional check to convert RangeSet * into std::optional<RangeSet>. template <class HeadTy, class SecondTy, class... RestTy> [[nodiscard]] inline typename IntersectionTraits<HeadTy, SecondTy, RestTy...>::Type intersect(RangeSet::Factory &F, HeadTy Head, SecondTy Second, RestTy... Tail) { … } //===----------------------------------------------------------------------===// // Symbolic reasoning logic //===----------------------------------------------------------------------===// /// A little component aggregating all of the reasoning we have about /// the ranges of symbolic expressions. /// /// Even when we don't know the exact values of the operands, we still /// can get a pretty good estimate of the result's range. class SymbolicRangeInferrer : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> { … }; //===----------------------------------------------------------------------===// // Range-based reasoning about symbolic operations //===----------------------------------------------------------------------===// template <> RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_NE>(RangeSet LHS, RangeSet RHS, QualType T) { … } template <> RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS, QualType T) { … } template <> RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS, Range RHS, QualType T) { … } template <> RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS, Range RHS, QualType T) { … } RangeSet SymbolicRangeInferrer::VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op, RangeSet RHS, QualType T) { … } //===----------------------------------------------------------------------===// // Constraint manager implementation details //===----------------------------------------------------------------------===// class RangeConstraintManager : public RangedConstraintManager { … }; //===----------------------------------------------------------------------===// // Constraint assignment logic //===----------------------------------------------------------------------===// /// ConstraintAssignorBase is a small utility class that unifies visitor /// for ranges with a visitor for constraints (rangeset/range/constant). /// /// It is designed to have one derived class, but generally it can have more. /// Derived class can control which types we handle by defining methods of the /// following form: /// /// bool handle${SYMBOL}To${CONSTRAINT}(const SYMBOL *Sym, /// CONSTRAINT Constraint); /// /// where SYMBOL is the type of the symbol (e.g. SymSymExpr, SymbolCast, etc.) /// CONSTRAINT is the type of constraint (RangeSet/Range/Const) /// return value signifies whether we should try other handle methods /// (i.e. false would mean to stop right after calling this method) template <class Derived> class ConstraintAssignorBase { … } … }; /// A little component aggregating all of the reasoning we have about /// assigning new constraints to symbols. /// /// The main purpose of this class is to associate constraints to symbols, /// and impose additional constraints on other symbols, when we can imply /// them. /// /// It has a nice symmetry with SymbolicRangeInferrer. When the latter /// can provide more precise ranges by looking into the operands of the /// expression in question, ConstraintAssignor looks into the operands /// to see if we can imply more from the new constraint. class ConstraintAssignor : public ConstraintAssignorBase<ConstraintAssignor> { … }; bool ConstraintAssignor::assignSymExprToConst(const SymExpr *Sym, const llvm::APSInt &Constraint) { … } bool ConstraintAssignor::assignSymSymExprToRangeSet(const SymSymExpr *Sym, RangeSet Constraint) { … } } // end anonymous namespace std::unique_ptr<ConstraintManager> ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, ExprEngine *Eng) { … } ConstraintMap ento::getConstraintMap(ProgramStateRef State) { … } //===----------------------------------------------------------------------===// // EqualityClass implementation details //===----------------------------------------------------------------------===// LLVM_DUMP_METHOD void EquivalenceClass::dumpToStream(ProgramStateRef State, raw_ostream &os) const { … } inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State, SymbolRef Sym) { … } inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F, ProgramStateRef State, SymbolRef First, SymbolRef Second) { … } inline ProgramStateRef EquivalenceClass::merge(RangeSet::Factory &F, ProgramStateRef State, EquivalenceClass Other) { … } inline ProgramStateRef EquivalenceClass::mergeImpl(RangeSet::Factory &RangeFactory, ProgramStateRef State, SymbolSet MyMembers, EquivalenceClass Other, SymbolSet OtherMembers) { … } inline SymbolSet::Factory & EquivalenceClass::getMembersFactory(ProgramStateRef State) { … } SymbolSet EquivalenceClass::getClassMembers(ProgramStateRef State) const { … } bool EquivalenceClass::isTrivial(ProgramStateRef State) const { … } bool EquivalenceClass::isTriviallyDead(ProgramStateRef State, SymbolReaper &Reaper) const { … } inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF, ProgramStateRef State, SymbolRef First, SymbolRef Second) { … } inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF, ProgramStateRef State, EquivalenceClass First, EquivalenceClass Second) { … } inline ProgramStateRef EquivalenceClass::markDisequal(RangeSet::Factory &RF, ProgramStateRef State, EquivalenceClass Other) const { … } inline bool EquivalenceClass::addToDisequalityInfo( DisequalityMapTy &Info, ConstraintRangeTy &Constraints, RangeSet::Factory &RF, ProgramStateRef State, EquivalenceClass First, EquivalenceClass Second) { … } inline std::optional<bool> EquivalenceClass::areEqual(ProgramStateRef State, SymbolRef FirstSym, SymbolRef SecondSym) { … } inline std::optional<bool> EquivalenceClass::areEqual(ProgramStateRef State, EquivalenceClass First, EquivalenceClass Second) { … } [[nodiscard]] ProgramStateRef EquivalenceClass::removeMember(ProgramStateRef State, const SymbolRef Old) { … } // Re-evaluate an SVal with top-level `State->assume` logic. [[nodiscard]] ProgramStateRef reAssume(ProgramStateRef State, const RangeSet *Constraint, SVal TheValue) { … } // Iterate over all symbols and try to simplify them. Once a symbol is // simplified then we check if we can merge the simplified symbol's equivalence // class to this class. This way, we simplify not just the symbols but the // classes as well: we strive to keep the number of the classes to be the // absolute minimum. [[nodiscard]] ProgramStateRef EquivalenceClass::simplify(SValBuilder &SVB, RangeSet::Factory &F, ProgramStateRef State, EquivalenceClass Class) { … } inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State, SymbolRef Sym) { … } inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State) const { … } inline ClassSet EquivalenceClass::getDisequalClasses(DisequalityMapTy Map, ClassSet::Factory &Factory) const { … } bool EquivalenceClass::isClassDataConsistent(ProgramStateRef State) { … } //===----------------------------------------------------------------------===// // RangeConstraintManager implementation //===----------------------------------------------------------------------===// bool RangeConstraintManager::canReasonAbout(SVal X) const { … } ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, SymbolRef Sym) { … } const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, SymbolRef Sym) const { … } const llvm::APSInt *RangeConstraintManager::getSymMinVal(ProgramStateRef St, SymbolRef Sym) const { … } const llvm::APSInt *RangeConstraintManager::getSymMaxVal(ProgramStateRef St, SymbolRef Sym) const { … } //===----------------------------------------------------------------------===// // Remove dead symbols from existing constraints //===----------------------------------------------------------------------===// /// Scan all symbols referenced by the constraints. If the symbol is not alive /// as marked in LSymbols, mark it as dead in DSymbols. ProgramStateRef RangeConstraintManager::removeDeadBindings(ProgramStateRef State, SymbolReaper &SymReaper) { … } RangeSet RangeConstraintManager::getRange(ProgramStateRef State, SymbolRef Sym) { … } ProgramStateRef RangeConstraintManager::setRange(ProgramStateRef State, SymbolRef Sym, RangeSet Range) { … } //===------------------------------------------------------------------------=== // assumeSymX methods: protected interface for RangeConstraintManager. //===------------------------------------------------------------------------=== // The syntax for ranges below is mathematical, using [x, y] for closed ranges // and (x, y) for open ranges. These ranges are modular, corresponding with // a common treatment of C integer overflow. This means that these methods // do not have to worry about overflow; RangeSet::Intersect can handle such a // "wraparound" range. // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, // UINT_MAX, 0, 1, and 2. ProgramStateRef RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } ProgramStateRef RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } ProgramStateRef RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } ProgramStateRef RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } ProgramStateRef RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } RangeSet RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } ProgramStateRef RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { … } ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange( ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) { … } ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange( ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) { … } //===----------------------------------------------------------------------===// // Pretty-printing. //===----------------------------------------------------------------------===// void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State, const char *NL, unsigned int Space, bool IsDot) const { … } void RangeConstraintManager::printValue(raw_ostream &Out, ProgramStateRef State, SymbolRef Sym) { … } static std::string toString(const SymbolRef &Sym) { … } void RangeConstraintManager::printConstraints(raw_ostream &Out, ProgramStateRef State, const char *NL, unsigned int Space, bool IsDot) const { … } static std::string toString(ProgramStateRef State, EquivalenceClass Class) { … } void RangeConstraintManager::printEquivalenceClasses(raw_ostream &Out, ProgramStateRef State, const char *NL, unsigned int Space, bool IsDot) const { … } void RangeConstraintManager::printDisequalities(raw_ostream &Out, ProgramStateRef State, const char *NL, unsigned int Space, bool IsDot) const { … }
Codebase Browser
llvm