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 
13 #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
14 #include "clang/AST/Type.h"
15 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
16 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
19 #include "llvm/ADT/ScopeExit.h"
20 
21 using namespace clang;
22 using namespace ento;
23 
24 ConstraintManager::~ConstraintManager() = default;
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 
33 ConditionTruthVal ConstraintManager::checkNull(ProgramStateRef State,
34                                                SymbolRef Sym) {
35   QualType Ty = Sym->getType();
36   DefinedSVal V = Loc::isLocType(Ty) ? getLocFromSymbol(State, Sym)
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>
47 ConstraintManager::ProgramStatePair
48 ConstraintManager::assumeDualImpl(ProgramStateRef &State,
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 
92 ConstraintManager::ProgramStatePair
93 ConstraintManager::assumeDual(ProgramStateRef State, DefinedSVal Cond) {
94   auto AssumeFun = [&](bool Assumption) {
95     return assumeInternal(State, Cond, Assumption);
96   };
97   return assumeDualImpl(State, AssumeFun);
98 }
99 
100 ConstraintManager::ProgramStatePair
101 ConstraintManager::assumeInclusiveRangeDual(ProgramStateRef State, NonLoc Value,
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 
110 ProgramStateRef ConstraintManager::assume(ProgramStateRef State,
111                                           DefinedSVal Cond, bool Assumption) {
112   ConstraintManager::ProgramStatePair R = assumeDual(State, Cond);
113   return Assumption ? R.first : R.second;
114 }
115 
116 ProgramStateRef
117 ConstraintManager::assumeInclusiveRange(ProgramStateRef State, NonLoc Value,
118                                         const llvm::APSInt &From,
119                                         const llvm::APSInt &To, bool InBound) {
120   ConstraintManager::ProgramStatePair R =
121       assumeInclusiveRangeDual(State, Value, From, To);
122   return InBound ? R.first : R.second;
123 }
124