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(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
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(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
92ConstraintManager::ProgramStatePair
93ConstraintManager::assumeDual(ProgramStateRef State, DefinedSVal Cond) {
94  auto AssumeFun = [&, Cond](bool Assumption) {
95    return assumeInternal(State, Cond, Assumption);
96  };
97  return assumeDualImpl(State, AssumeFun);
98}
99
100ConstraintManager::ProgramStatePair
101ConstraintManager::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
110ProgramStateRef 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
116ProgramStateRef
117ConstraintManager::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