clang  15.0.0git
ConstraintManager.cpp
Go to the documentation of this file.
1 //===- ConstraintManager.cpp - Constraints on symbolic values. ------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defined the interface to manage constraints on symbolic values.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "clang/AST/Type.h"
19 #include "llvm/ADT/ScopeExit.h"
20 
21 using namespace clang;
22 using namespace ento;
23 
25 
26 static DefinedSVal getLocFromSymbol(const ProgramStateRef &State,
27  SymbolRef Sym) {
28  const MemRegion *R =
29  State->getStateManager().getRegionManager().getSymbolicRegion(Sym);
30  return loc::MemRegionVal(R);
31 }
32 
34  SymbolRef Sym) {
35  QualType Ty = Sym->getType();
37  : nonloc::SymbolVal(Sym);
38  const ProgramStatePair &P = assumeDual(State, V);
39  if (P.first && !P.second)
40  return ConditionTruthVal(false);
41  if (!P.first && P.second)
42  return ConditionTruthVal(true);
43  return {};
44 }
45 
46 template <typename AssumeFunction>
49  AssumeFunction &Assume) {
50  if (LLVM_UNLIKELY(State->isPosteriorlyOverconstrained()))
51  return {State, State};
52 
53  // Assume functions might recurse (see `reAssume` or `tryRearrange`). During
54  // the recursion the State might not change anymore, that means we reached a
55  // fixpoint.
56  // We avoid infinite recursion of assume calls by checking already visited
57  // States on the stack of assume function calls.
58  const ProgramState *RawSt = State.get();
59  if (LLVM_UNLIKELY(AssumeStack.contains(RawSt)))
60  return {State, State};
61  AssumeStack.push(RawSt);
62  auto AssumeStackBuilder =
63  llvm::make_scope_exit([this]() { AssumeStack.pop(); });
64 
65  ProgramStateRef StTrue = Assume(true);
66 
67  if (!StTrue) {
68  ProgramStateRef StFalse = Assume(false);
69  if (LLVM_UNLIKELY(!StFalse)) { // both infeasible
70  ProgramStateRef StInfeasible = State->cloneAsPosteriorlyOverconstrained();
71  assert(StInfeasible->isPosteriorlyOverconstrained());
72  // Checkers might rely on the API contract that both returned states
73  // cannot be null. Thus, we return StInfeasible for both branches because
74  // it might happen that a Checker uncoditionally uses one of them if the
75  // other is a nullptr. This may also happen with the non-dual and
76  // adjacent `assume(true)` and `assume(false)` calls. By implementing
77  // assume in therms of assumeDual, we can keep our API contract there as
78  // well.
79  return ProgramStatePair(StInfeasible, StInfeasible);
80  }
81  return ProgramStatePair(nullptr, StFalse);
82  }
83 
84  ProgramStateRef StFalse = Assume(false);
85  if (!StFalse) {
86  return ProgramStatePair(StTrue, nullptr);
87  }
88 
89  return ProgramStatePair(StTrue, StFalse);
90 }
91 
94  auto AssumeFun = [&](bool Assumption) {
95  return assumeInternal(State, Cond, Assumption);
96  };
97  return assumeDualImpl(State, AssumeFun);
98 }
99 
102  const llvm::APSInt &From,
103  const llvm::APSInt &To) {
104  auto AssumeFun = [&](bool Assumption) {
105  return assumeInclusiveRangeInternal(State, Value, From, To, Assumption);
106  };
107  return assumeDualImpl(State, AssumeFun);
108 }
109 
111  DefinedSVal Cond, bool Assumption) {
113  return Assumption ? R.first : R.second;
114 }
115 
118  const llvm::APSInt &From,
119  const llvm::APSInt &To, bool InBound) {
122  return InBound ? R.first : R.second;
123 }
clang::ento::ConstraintManager::assumeInclusiveRangeDual
ProgramStatePair assumeInclusiveRangeDual(ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, const llvm::APSInt &To)
Returns a pair of states (StInRange, StOutOfRange) where the given value is assumed to be in the rang...
Definition: ConstraintManager.cpp:101
clang::ento::Loc::isLocType
static bool isLocType(QualType T)
Definition: SVals.h:286
ConstraintManager.h
SVals.h
getLocFromSymbol
static DefinedSVal getLocFromSymbol(const ProgramStateRef &State, SymbolRef Sym)
Definition: ConstraintManager.cpp:26
clang::ento::NonLoc
Definition: SVals.h:262
clang::ento::ConstraintManager::ProgramStatePair
std::pair< ProgramStateRef, ProgramStateRef > ProgramStatePair
Definition: ConstraintManager.h:84
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:731
clang::ento::ConstraintManager::AssumeStackTy::contains
bool contains(const ProgramState *S) const
Definition: ConstraintManager.h:138
ProgramState_Fwd.h
clang::ento::SymbolRef
const SymExpr * SymbolRef
Definition: SymExpr.h:111
clang::ento::ConstraintManager::AssumeStackTy::push
void push(const ProgramState *S)
Definition: ConstraintManager.h:136
clang::ento::ConstraintManager::AssumeStackTy::pop
void pop()
Definition: ConstraintManager.h:137
clang::ento::ProgramState
Definition: ProgramState.h:72
clang::ento::ConstraintManager::AssumeStack
AssumeStackTy AssumeStack
Definition: ConstraintManager.h:145
clang::ento::ConditionTruthVal
Definition: ConstraintManager.h:38
APSInt
llvm::APSInt APSInt
Definition: ByteCodeEmitter.cpp:19
V
#define V(N, I)
Definition: ASTContext.h:3176
clang::ento::DefinedSVal
Definition: SVals.h:239
clang::ento::SymExpr::getType
virtual QualType getType() const =0
clang::ento::SymExpr
Symbolic value.
Definition: SymExpr.h:29
clang::ento::ConstraintManager::~ConstraintManager
virtual ~ConstraintManager()
Type.h
clang::ento::ConstraintManager::assume
ProgramStateRef assume(ProgramStateRef state, DefinedSVal Cond, bool Assumption)
Definition: ConstraintManager.cpp:110
clang::ento::ConstraintManager::assumeDualImpl
ProgramStatePair assumeDualImpl(ProgramStateRef &State, AssumeFunction &Assume)
clang::ento::ConstraintManager::assumeInclusiveRangeInternal
virtual ProgramStateRef assumeInclusiveRangeInternal(ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, const llvm::APSInt &To, bool InBound)=0
clang::ento::ConstraintManager::assumeDual
ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond)
Returns a pair of states (StTrue, StFalse) where the given condition is assumed to be true or false,...
Definition: ConstraintManager.cpp:93
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::ento::ConstraintManager::assumeInternal
virtual ProgramStateRef assumeInternal(ProgramStateRef state, DefinedSVal Cond, bool Assumption)=0
Value
Value
Definition: UninitializedValues.cpp:102
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1126
ProgramState.h
clang::ento::nonloc::SymbolVal
Represents symbolic expression that isn't a location.
Definition: SVals.h:301
clang
Definition: CalledOnceCheck.h:17
clang::ento::ConstraintManager::assumeInclusiveRange
ProgramStateRef assumeInclusiveRange(ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, const llvm::APSInt &To, bool InBound)
Definition: ConstraintManager.cpp:117
clang::ento::ConstraintManager::checkNull
virtual ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym)
Returns whether or not a symbol is known to be null ("true"), known to be non-null ("false"),...
Definition: ConstraintManager.cpp:33
MemRegion.h
llvm::IntrusiveRefCntPtr< const ProgramState >