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
21using namespace clang;
22using namespace ento;
23
24ConstraintManager::~ConstraintManager() = default;
25
26static 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
33ConditionTruthVal ConstraintManager::checkNull(ProgramStateRef State,
34 SymbolRef Sym) {
35 QualType Ty = Sym->getType();
36 DefinedSVal V = Loc::isLocType(T: Ty) ? getLocFromSymbol(State, Sym)
37 : nonloc::SymbolVal(Sym);
38 const ProgramStatePair &P = assumeDual(State, Cond: 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
46template <typename AssumeFunction>
47ConstraintManager::ProgramStatePair
48ConstraintManager::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(S: RawSt);
62 llvm::scope_exit AssumeStackBuilder([this]() { AssumeStack.pop(); });
63
64 ProgramStateRef StTrue = Assume(true);
65
66 if (!StTrue) {
67 ProgramStateRef StFalse = Assume(false);
68 if (LLVM_UNLIKELY(!StFalse)) { // both infeasible
69 ProgramStateRef StInfeasible = State->cloneAsPosteriorlyOverconstrained();
70 assert(StInfeasible->isPosteriorlyOverconstrained());
71 // Checkers might rely on the API contract that both returned states
72 // cannot be null. Thus, we return StInfeasible for both branches because
73 // it might happen that a Checker uncoditionally uses one of them if the
74 // other is a nullptr. This may also happen with the non-dual and
75 // adjacent `assume(true)` and `assume(false)` calls. By implementing
76 // assume in therms of assumeDual, we can keep our API contract there as
77 // well.
78 return ProgramStatePair(StInfeasible, StInfeasible);
79 }
80 return ProgramStatePair(nullptr, StFalse);
81 }
82
83 ProgramStateRef StFalse = Assume(false);
84 if (!StFalse) {
85 return ProgramStatePair(StTrue, nullptr);
86 }
87
88 return ProgramStatePair(StTrue, StFalse);
89}
90
91ConstraintManager::ProgramStatePair
92ConstraintManager::assumeDual(ProgramStateRef State, DefinedSVal Cond) {
93 auto AssumeFun = [&, Cond](bool Assumption) {
94 return assumeInternal(state: State, Cond, Assumption);
95 };
96 return assumeDualImpl(State, Assume&: AssumeFun);
97}
98
99ConstraintManager::ProgramStatePair
100ConstraintManager::assumeInclusiveRangeDual(ProgramStateRef State, NonLoc Value,
101 const llvm::APSInt &From,
102 const llvm::APSInt &To) {
103 auto AssumeFun = [&](bool Assumption) {
104 return assumeInclusiveRangeInternal(State, Value, From, To, InBound: Assumption);
105 };
106 return assumeDualImpl(State, Assume&: AssumeFun);
107}
108
109ProgramStateRef ConstraintManager::assume(ProgramStateRef State,
110 DefinedSVal Cond, bool Assumption) {
111 ConstraintManager::ProgramStatePair R = assumeDual(State, Cond);
112 return Assumption ? R.first : R.second;
113}
114
115ProgramStateRef
116ConstraintManager::assumeInclusiveRange(ProgramStateRef State, NonLoc Value,
117 const llvm::APSInt &From,
118 const llvm::APSInt &To, bool InBound) {
119 ConstraintManager::ProgramStatePair R =
120 assumeInclusiveRangeDual(State, Value, From, To);
121 return InBound ? R.first : R.second;
122}
123