SMTConstraintManager.h

Go to the documentation of this file.

//== SMTConstraintManager.h -------------------------------------*- 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 a SMT generic API, which will be the base class for
//  every SMT solver specific class.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTCONSTRAINTMANAGER_H
#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTCONSTRAINTMANAGER_H
 
#include "clang/Basic/JsonSupport.h"
#include "clang/Basic/TargetInfo.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include <optional>
 
typedef llvm::ImmutableSet<
    std::pair<clang::ento::SymbolRef, const llvm::SMTExpr *>>
    ConstraintSMTType;
REGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintSMT, ConstraintSMTType)
 
namespace clang {
namespace ento {
 
class SMTConstraintManager : public clang::ento::SimpleConstraintManager {
  using ConstraintEntry = std::pair<SymbolRef, const llvm::SMTExpr *>;
  mutable llvm::SMTSolverRef Solver = llvm::CreateZ3Solver();
 
public:
  SMTConstraintManager(clang::ento::ExprEngine *EE,
                       clang::ento::SValBuilder &SB)
      : SimpleConstraintManager(EE, SB) {
    Solver->setBoolParam("model", true); // Enable model finding
    Solver->setUnsignedParam("timeout", 15000 /*milliseconds*/);
  }
  virtual ~SMTConstraintManager() = default;
 
  //===------------------------------------------------------------------===//
  // Implementation for interface from SimpleConstraintManager.
  //===------------------------------------------------------------------===//
 
  ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym,
                            bool Assumption) override {
    ASTContext &Ctx = getBasicVals().getContext();
 
    QualType RetTy;
    bool hasComparison;
 
    std::optional<llvm::SMTExprRef> Exp =
        SMTConv::getExpr(Solver, Ctx, Sym, RetTy, &hasComparison);
    if (!Exp)
      return assumeSymUnsupported(State, Sym, Assumption);
    // Create zero comparison for implicit boolean cast, with reversed
    // assumption
    if (!hasComparison && !RetTy->isBooleanType())
      return assumeExpr(
          State, Sym,
          SMTConv::getZeroExpr(Solver, Ctx, Exp.value(), RetTy, !Assumption));
 
    return assumeExpr(State, Sym,
                      Assumption ? Exp.value() : Solver->mkNot(Exp.value()));
  }
 
  ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym,
                                          const llvm::APSInt &From,
                                          const llvm::APSInt &To,
                                          bool InRange) override {
    ASTContext &Ctx = getBasicVals().getContext();
    std::optional<llvm::SMTExprRef> Expr =
        SMTConv::getRangeExpr(Solver, Ctx, Sym, From, To, InRange);
    if (!Expr)
      return assumeSymUnsupported(State, Sym, false);
    return assumeExpr(State, Sym, Expr.value());
  }
 
  ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym,
                                       bool Assumption) override {
    // Skip anything that is unsupported
    return State;
  }
 
  //===------------------------------------------------------------------===//
  // Implementation for interface from ConstraintManager.
  //===------------------------------------------------------------------===//
 
  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override {
    ASTContext &Ctx = getBasicVals().getContext();
 
    QualType RetTy;
    // The expression may be casted, so we cannot call getZ3DataExpr() directly
    std::optional<llvm::SMTExprRef> VarExp =
        SMTConv::getExpr(Solver, Ctx, Sym, RetTy);
    if (!VarExp)
      return ConditionTruthVal();
    llvm::SMTExprRef Exp = SMTConv::getZeroExpr(Solver, Ctx, VarExp.value(),
                                                RetTy, /*Assumption=*/true);
 
    // Negate the constraint
    llvm::SMTExprRef NotExp = SMTConv::getZeroExpr(Solver, Ctx, VarExp.value(),
                                                   RetTy, /*Assumption=*/false);
 
    ConditionTruthVal isSat = checkModel(State, Sym, Exp);
    ConditionTruthVal isNotSat = checkModel(State, Sym, NotExp);
 
    // Zero is the only possible solution
    if (isSat.isConstrainedTrue() && isNotSat.isConstrainedFalse())
      return true;
 
    // Zero is not a solution
    if (isSat.isConstrainedFalse() && isNotSat.isConstrainedTrue())
      return false;
 
    // Zero may be a solution
    return ConditionTruthVal();
  }
 
  const llvm::APSInt *getSymVal(ProgramStateRef State,
                                SymbolRef Sym) const override {
    BasicValueFactory &BVF = getBasicVals();
    ASTContext &Ctx = BVF.getContext();
 
    if (const SymbolData *SD = dyn_cast<SymbolData>(Sym)) {
      QualType Ty = Sym->getType();
      assert(!Ty->isRealFloatingType());
      llvm::APSInt Value(SMTConv::getSMTBitWidth(Ctx, Ty),
                         !Ty->isSignedIntegerOrEnumerationType());
 
      // TODO: this should call checkModel so we can use the cache, however,
      // this method tries to get the interpretation (the actual value) from
      // the solver, which is currently not cached.
 
      llvm::SMTExprRef Exp = SMTConv::fromData(Solver, Ctx, SD);
 
      Solver->reset();
      addStateConstraints(State);
 
      // Constraints are unsatisfiable
      std::optional<bool> isSat = Solver->check();
      if (!isSat || !*isSat)
        return nullptr;
 
      // Model does not assign interpretation
      if (!Solver->getInterpretation(Exp, Value))
        return nullptr;
 
      // A value has been obtained, check if it is the only value
      llvm::SMTExprRef NotExp = SMTConv::fromBinOp(
          Solver, Exp, BO_NE,
          Ty->isBooleanType() ? Solver->mkBoolean(Value.getBoolValue())
                              : Solver->mkBitvector(Value, Value.getBitWidth()),
          /*isSigned=*/false);
 
      Solver->addConstraint(NotExp);
 
      std::optional<bool> isNotSat = Solver->check();
      if (!isNotSat || *isNotSat)
        return nullptr;
 
      // This is the only solution, store it
      return BVF.getValue(Value).get();
    }
 
    if (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) {
      SymbolRef CastSym = SC->getOperand();
      QualType CastTy = SC->getType();
      // Skip the void type
      if (CastTy->isVoidType())
        return nullptr;
 
      const llvm::APSInt *Value;
      if (!(Value = getSymVal(State, CastSym)))
        return nullptr;
      return BVF.Convert(SC->getType(), *Value).get();
    }
 
    if (const auto *USE = dyn_cast<UnarySymExpr>(Sym)) {
      const llvm::APSInt *Value;
      if (!(Value = getSymVal(State, USE->getOperand())))
        return nullptr;
      std::optional<APSIntPtr> Res = BVF.evalAPSInt(USE->getOpcode(), *Value);
      return Res ? Res.value().get() : nullptr;
    }
 
    if (const BinarySymExpr *BSE = dyn_cast<BinarySymExpr>(Sym)) {
      const llvm::APSInt *LHS, *RHS;
      if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(BSE)) {
        LHS = getSymVal(State, SIE->getLHS());
        RHS = SIE->getRHS().get();
      } else if (const IntSymExpr *ISE = dyn_cast<IntSymExpr>(BSE)) {
        LHS = ISE->getLHS().get();
        RHS = getSymVal(State, ISE->getRHS());
      } else if (const SymSymExpr *SSM = dyn_cast<SymSymExpr>(BSE)) {
        // Early termination to avoid expensive call
        LHS = getSymVal(State, SSM->getLHS());
        RHS = LHS ? getSymVal(State, SSM->getRHS()) : nullptr;
      } else {
        llvm_unreachable("Unsupported binary expression to get symbol value!");
      }
 
      if (!LHS || !RHS)
        return nullptr;
 
      llvm::APSInt ConvertedLHS, ConvertedRHS;
      QualType LTy, RTy;
      std::tie(ConvertedLHS, LTy) = SMTConv::fixAPSInt(Ctx, *LHS);
      std::tie(ConvertedRHS, RTy) = SMTConv::fixAPSInt(Ctx, *RHS);
      SMTConv::doIntTypeConversion<llvm::APSInt, &SMTConv::castAPSInt>(
          Solver, Ctx, ConvertedLHS, LTy, ConvertedRHS, RTy);
      std::optional<APSIntPtr> Res =
          BVF.evalAPSInt(BSE->getOpcode(), ConvertedLHS, ConvertedRHS);
      return Res ? Res.value().get() : nullptr;
    }
 
    llvm_unreachable("Unsupported expression to get symbol value!");
  }
 
  ProgramStateRef removeDeadBindings(ProgramStateRef State,
                                     SymbolReaper &SymReaper) override {
    ConstraintSMTType CZ = State->get<ConstraintSMT>();
    ConstraintSMTType::Factory &CZFactory = State->get_context<ConstraintSMT>();
    llvm::SmallVector<ConstraintEntry> Constraints(CZ.begin(), CZ.end());
    llvm::DenseMap<SymbolRef, SmallVector<size_t>> ConstraintsBySym;
    llvm::DenseSet<SymbolRef> TraversedSymbols;
    llvm::SmallVector<SymbolRef> WorkList;
    llvm::BitVector RetainedConstraints(Constraints.size());
 
    for (auto [Idx, Entry] : llvm::enumerate(Constraints)) {
      for (auto Symbol : Entry.first->symbols()) {
        if (SymReaper.isLive(Symbol) && TraversedSymbols.insert(Symbol).second)
          WorkList.push_back(Symbol);
        ConstraintsBySym[Symbol].push_back(Idx);
      }
    }
 
    while (WorkList.size()) {
      SymbolRef Item = WorkList.pop_back_val();
      for (auto Idx : ConstraintsBySym[Item]) {
        if (RetainedConstraints.test(Idx))
          continue;
 
        RetainedConstraints.set(Idx);
 
        for (auto Symbol : Constraints[Idx].first->symbols()) {
          if (TraversedSymbols.insert(Symbol).second)
            WorkList.push_back(Symbol);
        }
      }
    }
 
    for (auto [Idx, Entry] : llvm::enumerate(Constraints)) {
      if (!RetainedConstraints.test(Idx))
        CZ = CZFactory.remove(CZ, Entry);
    }
 
    return State->set<ConstraintSMT>(CZ);
  }
 
  void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
                 unsigned int Space = 0, bool IsDot = false) const override {
    ConstraintSMTType Constraints = State->get<ConstraintSMT>();
 
    Indent(Out, Space, IsDot) << "\"constraints\": ";
    if (Constraints.isEmpty()) {
      Out << "null," << NL;
      return;
    }
 
    ++Space;
    Out << '[' << NL;
    for (ConstraintSMTType::iterator I = Constraints.begin();
         I != Constraints.end(); ++I) {
      Indent(Out, Space, IsDot)
          << "{ \"symbol\": \"" << I->first << "\", \"range\": \"";
      I->second->print(Out);
      Out << "\" }";
 
      if (std::next(I) != Constraints.end())
        Out << ',';
      Out << NL;
    }
 
    --Space;
    Indent(Out, Space, IsDot) << "],";
  }
 
  bool haveEqualConstraints(ProgramStateRef S1,
                            ProgramStateRef S2) const override {
    return S1->get<ConstraintSMT>() == S2->get<ConstraintSMT>();
  }
 
  bool canReasonAbout(SVal X) const override {
    const TargetInfo &TI = getBasicVals().getContext().getTargetInfo();
 
    std::optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
    if (!SymVal)
      return true;
 
    const SymExpr *Sym = SymVal->getSymbol();
    QualType Ty = Sym->getType();
 
    // Complex types are not modeled
    if (Ty->isComplexType() || Ty->isComplexIntegerType())
      return false;
 
    // Non-IEEE 754 floating-point types are not modeled
    if ((Ty->isSpecificBuiltinType(BuiltinType::LongDouble) &&
         (&TI.getLongDoubleFormat() == &llvm::APFloat::x87DoubleExtended() ||
          &TI.getLongDoubleFormat() == &llvm::APFloat::PPCDoubleDouble())))
      return false;
 
    if (Ty->isRealFloatingType())
      return Solver->isFPSupported();
 
    if (isa<SymbolData>(Sym))
      return true;
 
    SValBuilder &SVB = getSValBuilder();
 
    if (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
      return canReasonAbout(SVB.makeSymbolVal(SC->getOperand()));
 
    if (const auto *USE = dyn_cast<UnarySymExpr>(Sym))
      return canReasonAbout(SVB.makeSymbolVal(USE->getOperand()));
 
    if (const BinarySymExpr *BSE = dyn_cast<BinarySymExpr>(Sym)) {
      if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(BSE))
        return canReasonAbout(SVB.makeSymbolVal(SIE->getLHS()));
 
      if (const IntSymExpr *ISE = dyn_cast<IntSymExpr>(BSE))
        return canReasonAbout(SVB.makeSymbolVal(ISE->getRHS()));
 
      if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(BSE))
        return canReasonAbout(SVB.makeSymbolVal(SSE->getLHS())) &&
               canReasonAbout(SVB.makeSymbolVal(SSE->getRHS()));
    }
 
    llvm_unreachable("Unsupported expression to reason about!");
  }
 
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  /// Dumps SMT formula
  LLVM_DUMP_METHOD void dump() const { Solver->dump(); }
#endif
 
protected:
  // Check whether a new model is satisfiable, and update the program state.
  virtual ProgramStateRef assumeExpr(ProgramStateRef State, SymbolRef Sym,
                                     const llvm::SMTExprRef &Exp) {
    // Check the model, avoid simplifying AST to save time
    if (checkModel(State, Sym, Exp).isConstrainedTrue())
      return State->add<ConstraintSMT>(std::make_pair(Sym, Exp));
 
    return nullptr;
  }
 
  /// Given a program state, construct the logical conjunction and add it to
  /// the solver
  virtual void addStateConstraints(ProgramStateRef State) const {
    // TODO: Don't add all the constraints, only the relevant ones
    auto CZ = State->get<ConstraintSMT>();
    auto I = CZ.begin(), IE = CZ.end();
 
    // Construct the logical AND of all the constraints
    if (I != IE) {
      llvm::SMTExprRef Constraint = I++->second;
      while (I != IE) {
        Constraint = Solver->mkAnd(Constraint, I++->second);
      }
 
      Solver->addConstraint(Constraint);
    }
  }
 
  // Generate and check a Z3 model, using the given constraint.
  ConditionTruthVal checkModel(ProgramStateRef State, SymbolRef Sym,
                               const llvm::SMTExprRef &Exp) const {
    ProgramStateRef NewState =
        State->add<ConstraintSMT>(std::make_pair(Sym, Exp));
 
    llvm::FoldingSetNodeID ID;
    NewState->get<ConstraintSMT>().Profile(ID);
 
    unsigned hash = ID.ComputeHash();
    auto I = Cached.find(hash);
    if (I != Cached.end())
      return I->second;
 
    Solver->reset();
    addStateConstraints(NewState);
 
    std::optional<bool> res = Solver->check();
    return Cached[hash] = res ? ConditionTruthVal(*res) : ConditionTruthVal();
  }
 
  // Cache the result of an SMT query (true, false, unknown). The key is the
  // hash of the constraints in a state
  mutable llvm::DenseMap<unsigned, ConditionTruthVal> Cached;
}; // end class SMTConstraintManager
 
} // namespace ento
} // namespace clang
 
#endif