RangedConstraintManager.h revision 360660 
1//== RangedConstraintManager.h ----------------------------------*- C++ -*--==//
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//  Ranged constraint manager, built on SimpleConstraintManager.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
14#define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
15
16#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
17#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h"
19
20namespace clang {
21
22namespace ento {
23
24/// A Range represents the closed range [from, to].  The caller must
25/// guarantee that from <= to.  Note that Range is immutable, so as not
26/// to subvert RangeSet's immutability.
27class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
28public:
29  Range(const llvm::APSInt &from, const llvm::APSInt &to)
30      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
31    assert(from <= to);
32  }
33  bool Includes(const llvm::APSInt &v) const {
34    return *first <= v && v <= *second;
35  }
36  const llvm::APSInt &From() const { return *first; }
37  const llvm::APSInt &To() const { return *second; }
38  const llvm::APSInt *getConcreteValue() const {
39    return &From() == &To() ? &From() : nullptr;
40  }
41
42  void Profile(llvm::FoldingSetNodeID &ID) const {
43    ID.AddPointer(&From());
44    ID.AddPointer(&To());
45  }
46};
47
48class RangeTrait : public llvm::ImutContainerInfo<Range> {
49public:
50  // When comparing if one Range is less than another, we should compare
51  // the actual APSInt values instead of their pointers.  This keeps the order
52  // consistent (instead of comparing by pointer values) and can potentially
53  // be used to speed up some of the operations in RangeSet.
54  static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
55    return *lhs.first < *rhs.first ||
56           (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second);
57  }
58};
59
60/// RangeSet contains a set of ranges. If the set is empty, then
61///  there the value of a symbol is overly constrained and there are no
62///  possible values for that symbol.
63class RangeSet {
64  typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
65  PrimRangeSet ranges; // no need to make const, since it is an
66                       // ImmutableSet - this allows default operator=
67                       // to work.
68public:
69  typedef PrimRangeSet::Factory Factory;
70  typedef PrimRangeSet::iterator iterator;
71
72  RangeSet(PrimRangeSet RS) : ranges(RS) {}
73
74  /// Create a new set with all ranges of this set and RS.
75  /// Possible intersections are not checked here.
76  RangeSet addRange(Factory &F, const RangeSet &RS) {
77    PrimRangeSet Ranges(RS.ranges);
78    for (const auto &range : ranges)
79      Ranges = F.add(Ranges, range);
80    return RangeSet(Ranges);
81  }
82
83  iterator begin() const { return ranges.begin(); }
84  iterator end() const { return ranges.end(); }
85
86  bool isEmpty() const { return ranges.isEmpty(); }
87
88  /// Construct a new RangeSet representing '{ [from, to] }'.
89  RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
90      : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
91
92  /// Profile - Generates a hash profile of this RangeSet for use
93  ///  by FoldingSet.
94  void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
95
96  /// getConcreteValue - If a symbol is contrained to equal a specific integer
97  ///  constant then this method returns that value.  Otherwise, it returns
98  ///  NULL.
99  const llvm::APSInt *getConcreteValue() const {
100    return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
101  }
102
103private:
104  void IntersectInRange(BasicValueFactory &BV, Factory &F,
105                        const llvm::APSInt &Lower, const llvm::APSInt &Upper,
106                        PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
107                        PrimRangeSet::iterator &e) const;
108
109  const llvm::APSInt &getMinValue() const;
110
111  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
112
113public:
114  RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
115                     llvm::APSInt Upper) const;
116  RangeSet Intersect(BasicValueFactory &BV, Factory &F,
117                     const RangeSet &Other) const;
118  RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
119
120  void print(raw_ostream &os) const;
121
122  bool operator==(const RangeSet &other) const {
123    return ranges == other.ranges;
124  }
125};
126
127
128class ConstraintRange {};
129using ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>;
130
131template <>
132struct ProgramStateTrait<ConstraintRange>
133  : public ProgramStatePartialTrait<ConstraintRangeTy> {
134  static void *GDMIndex();
135};
136
137
138class RangedConstraintManager : public SimpleConstraintManager {
139public:
140  RangedConstraintManager(SubEngine *SE, SValBuilder &SB)
141      : SimpleConstraintManager(SE, SB) {}
142
143  ~RangedConstraintManager() override;
144
145  //===------------------------------------------------------------------===//
146  // Implementation for interface from SimpleConstraintManager.
147  //===------------------------------------------------------------------===//
148
149  ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym,
150                            bool Assumption) override;
151
152  ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym,
153                                          const llvm::APSInt &From,
154                                          const llvm::APSInt &To,
155                                          bool InRange) override;
156
157  ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym,
158                                       bool Assumption) override;
159
160protected:
161  /// Assume a constraint between a symbolic expression and a concrete integer.
162  virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym,
163                               BinaryOperator::Opcode op,
164                               const llvm::APSInt &Int);
165
166  //===------------------------------------------------------------------===//
167  // Interface that subclasses must implement.
168  //===------------------------------------------------------------------===//
169
170  // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison
171  // operation for the method being invoked.
172
173  virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
174                                      const llvm::APSInt &V,
175                                      const llvm::APSInt &Adjustment) = 0;
176
177  virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
178                                      const llvm::APSInt &V,
179                                      const llvm::APSInt &Adjustment) = 0;
180
181  virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
182                                      const llvm::APSInt &V,
183                                      const llvm::APSInt &Adjustment) = 0;
184
185  virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
186                                      const llvm::APSInt &V,
187                                      const llvm::APSInt &Adjustment) = 0;
188
189  virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
190                                      const llvm::APSInt &V,
191                                      const llvm::APSInt &Adjustment) = 0;
192
193  virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
194                                      const llvm::APSInt &V,
195                                      const llvm::APSInt &Adjustment) = 0;
196
197  virtual ProgramStateRef assumeSymWithinInclusiveRange(
198      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
199      const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
200
201  virtual ProgramStateRef assumeSymOutsideInclusiveRange(
202      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
203      const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;
204
205  //===------------------------------------------------------------------===//
206  // Internal implementation.
207  //===------------------------------------------------------------------===//
208private:
209  static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment);
210};
211
212} // end GR namespace
213
214} // end clang namespace
215
216#endif
217