File: | tools/clang/lib/StaticAnalyzer/Checkers/NonNullParamChecker.cpp |
Warning: | line 178, column 1 Potential leak of memory pointed to by 'AttrNonNull.X' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===--- NonNullParamChecker.cpp - Undefined arguments checker -*- 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 | // This defines NonNullParamChecker, which checks for arguments expected not to | |||
10 | // be null due to: | |||
11 | // - the corresponding parameters being declared to have nonnull attribute | |||
12 | // - the corresponding parameters being references; since the call would form | |||
13 | // a reference to a null pointer | |||
14 | // | |||
15 | //===----------------------------------------------------------------------===// | |||
16 | ||||
17 | #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" | |||
18 | #include "clang/AST/Attr.h" | |||
19 | #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" | |||
20 | #include "clang/StaticAnalyzer/Core/Checker.h" | |||
21 | #include "clang/StaticAnalyzer/Core/CheckerManager.h" | |||
22 | #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" | |||
23 | #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" | |||
24 | ||||
25 | using namespace clang; | |||
26 | using namespace ento; | |||
27 | ||||
28 | namespace { | |||
29 | class NonNullParamChecker | |||
30 | : public Checker< check::PreCall, EventDispatcher<ImplicitNullDerefEvent> > { | |||
31 | mutable std::unique_ptr<BugType> BTAttrNonNull; | |||
32 | mutable std::unique_ptr<BugType> BTNullRefArg; | |||
33 | ||||
34 | public: | |||
35 | ||||
36 | void checkPreCall(const CallEvent &Call, CheckerContext &C) const; | |||
37 | ||||
38 | std::unique_ptr<BugReport> | |||
39 | genReportNullAttrNonNull(const ExplodedNode *ErrorN, const Expr *ArgE) const; | |||
40 | std::unique_ptr<BugReport> | |||
41 | genReportReferenceToNullPointer(const ExplodedNode *ErrorN, | |||
42 | const Expr *ArgE) const; | |||
43 | }; | |||
44 | } // end anonymous namespace | |||
45 | ||||
46 | /// \return Bitvector marking non-null attributes. | |||
47 | static llvm::SmallBitVector getNonNullAttrs(const CallEvent &Call) { | |||
48 | const Decl *FD = Call.getDecl(); | |||
49 | unsigned NumArgs = Call.getNumArgs(); | |||
50 | llvm::SmallBitVector AttrNonNull(NumArgs); | |||
51 | for (const auto *NonNull : FD->specific_attrs<NonNullAttr>()) { | |||
52 | if (!NonNull->args_size()) { | |||
53 | AttrNonNull.set(0, NumArgs); | |||
54 | break; | |||
55 | } | |||
56 | for (const ParamIdx &Idx : NonNull->args()) { | |||
57 | unsigned IdxAST = Idx.getASTIndex(); | |||
58 | if (IdxAST >= NumArgs) | |||
59 | continue; | |||
60 | AttrNonNull.set(IdxAST); | |||
61 | } | |||
62 | } | |||
63 | return AttrNonNull; | |||
64 | } | |||
65 | ||||
66 | void NonNullParamChecker::checkPreCall(const CallEvent &Call, | |||
67 | CheckerContext &C) const { | |||
68 | if (!Call.getDecl()) | |||
| ||||
69 | return; | |||
70 | ||||
71 | llvm::SmallBitVector AttrNonNull = getNonNullAttrs(Call); | |||
72 | unsigned NumArgs = Call.getNumArgs(); | |||
73 | ||||
74 | ProgramStateRef state = C.getState(); | |||
75 | ArrayRef<ParmVarDecl*> parms = Call.parameters(); | |||
76 | ||||
77 | for (unsigned idx = 0; idx < NumArgs; ++idx) { | |||
78 | // For vararg functions, a corresponding parameter decl may not exist. | |||
79 | bool HasParam = idx < parms.size(); | |||
80 | ||||
81 | // Check if the parameter is a reference. We want to report when reference | |||
82 | // to a null pointer is passed as a parameter. | |||
83 | bool haveRefTypeParam = | |||
84 | HasParam ? parms[idx]->getType()->isReferenceType() : false; | |||
85 | bool haveAttrNonNull = AttrNonNull[idx]; | |||
86 | ||||
87 | // Check if the parameter is also marked 'nonnull'. | |||
88 | if (!haveAttrNonNull && HasParam) | |||
89 | haveAttrNonNull = parms[idx]->hasAttr<NonNullAttr>(); | |||
90 | ||||
91 | if (!haveAttrNonNull && !haveRefTypeParam) | |||
92 | continue; | |||
93 | ||||
94 | // If the value is unknown or undefined, we can't perform this check. | |||
95 | const Expr *ArgE = Call.getArgExpr(idx); | |||
96 | SVal V = Call.getArgSVal(idx); | |||
97 | auto DV = V.getAs<DefinedSVal>(); | |||
98 | if (!DV) | |||
99 | continue; | |||
100 | ||||
101 | assert(!haveRefTypeParam || DV->getAs<Loc>())((!haveRefTypeParam || DV->getAs<Loc>()) ? static_cast <void> (0) : __assert_fail ("!haveRefTypeParam || DV->getAs<Loc>()" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/StaticAnalyzer/Checkers/NonNullParamChecker.cpp" , 101, __PRETTY_FUNCTION__)); | |||
102 | ||||
103 | // Process the case when the argument is not a location. | |||
104 | if (haveAttrNonNull && !DV->getAs<Loc>()) { | |||
105 | // If the argument is a union type, we want to handle a potential | |||
106 | // transparent_union GCC extension. | |||
107 | if (!ArgE) | |||
108 | continue; | |||
109 | ||||
110 | QualType T = ArgE->getType(); | |||
111 | const RecordType *UT = T->getAsUnionType(); | |||
112 | if (!UT || !UT->getDecl()->hasAttr<TransparentUnionAttr>()) | |||
113 | continue; | |||
114 | ||||
115 | auto CSV = DV->getAs<nonloc::CompoundVal>(); | |||
116 | ||||
117 | // FIXME: Handle LazyCompoundVals? | |||
118 | if (!CSV) | |||
119 | continue; | |||
120 | ||||
121 | V = *(CSV->begin()); | |||
122 | DV = V.getAs<DefinedSVal>(); | |||
123 | assert(++CSV->begin() == CSV->end())((++CSV->begin() == CSV->end()) ? static_cast<void> (0) : __assert_fail ("++CSV->begin() == CSV->end()", "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/StaticAnalyzer/Checkers/NonNullParamChecker.cpp" , 123, __PRETTY_FUNCTION__)); | |||
124 | // FIXME: Handle (some_union){ some_other_union_val }, which turns into | |||
125 | // a LazyCompoundVal inside a CompoundVal. | |||
126 | if (!V.getAs<Loc>()) | |||
127 | continue; | |||
128 | ||||
129 | // Retrieve the corresponding expression. | |||
130 | if (const auto *CE = dyn_cast<CompoundLiteralExpr>(ArgE)) | |||
131 | if (const auto *IE = dyn_cast<InitListExpr>(CE->getInitializer())) | |||
132 | ArgE = dyn_cast<Expr>(*(IE->begin())); | |||
133 | } | |||
134 | ||||
135 | ConstraintManager &CM = C.getConstraintManager(); | |||
136 | ProgramStateRef stateNotNull, stateNull; | |||
137 | std::tie(stateNotNull, stateNull) = CM.assumeDual(state, *DV); | |||
138 | ||||
139 | // Generate an error node. Check for a null node in case | |||
140 | // we cache out. | |||
141 | if (stateNull && !stateNotNull) { | |||
142 | if (ExplodedNode *errorNode = C.generateErrorNode(stateNull)) { | |||
143 | ||||
144 | std::unique_ptr<BugReport> R; | |||
145 | if (haveAttrNonNull) | |||
146 | R = genReportNullAttrNonNull(errorNode, ArgE); | |||
147 | else if (haveRefTypeParam) | |||
148 | R = genReportReferenceToNullPointer(errorNode, ArgE); | |||
149 | ||||
150 | // Highlight the range of the argument that was null. | |||
151 | R->addRange(Call.getArgSourceRange(idx)); | |||
152 | ||||
153 | // Emit the bug report. | |||
154 | C.emitReport(std::move(R)); | |||
155 | } | |||
156 | ||||
157 | // Always return. Either we cached out or we just emitted an error. | |||
158 | return; | |||
159 | } | |||
160 | ||||
161 | if (stateNull) { | |||
162 | if (ExplodedNode *N = C.generateSink(stateNull, C.getPredecessor())) { | |||
163 | ImplicitNullDerefEvent event = { | |||
164 | V, false, N, &C.getBugReporter(), | |||
165 | /*IsDirectDereference=*/haveRefTypeParam}; | |||
166 | dispatchEvent(event); | |||
167 | } | |||
168 | } | |||
169 | ||||
170 | // If a pointer value passed the check we should assume that it is | |||
171 | // indeed not null from this point forward. | |||
172 | state = stateNotNull; | |||
173 | } | |||
174 | ||||
175 | // If we reach here all of the arguments passed the nonnull check. | |||
176 | // If 'state' has been updated generated a new node. | |||
177 | C.addTransition(state); | |||
178 | } | |||
| ||||
179 | ||||
180 | std::unique_ptr<BugReport> | |||
181 | NonNullParamChecker::genReportNullAttrNonNull(const ExplodedNode *ErrorNode, | |||
182 | const Expr *ArgE) const { | |||
183 | // Lazily allocate the BugType object if it hasn't already been | |||
184 | // created. Ownership is transferred to the BugReporter object once | |||
185 | // the BugReport is passed to 'EmitWarning'. | |||
186 | if (!BTAttrNonNull) | |||
187 | BTAttrNonNull.reset(new BugType( | |||
188 | this, "Argument with 'nonnull' attribute passed null", "API")); | |||
189 | ||||
190 | auto R = llvm::make_unique<BugReport>( | |||
191 | *BTAttrNonNull, | |||
192 | "Null pointer passed as an argument to a 'nonnull' parameter", ErrorNode); | |||
193 | if (ArgE) | |||
194 | bugreporter::trackExpressionValue(ErrorNode, ArgE, *R); | |||
195 | ||||
196 | return R; | |||
197 | } | |||
198 | ||||
199 | std::unique_ptr<BugReport> NonNullParamChecker::genReportReferenceToNullPointer( | |||
200 | const ExplodedNode *ErrorNode, const Expr *ArgE) const { | |||
201 | if (!BTNullRefArg) | |||
202 | BTNullRefArg.reset(new BuiltinBug(this, "Dereference of null pointer")); | |||
203 | ||||
204 | auto R = llvm::make_unique<BugReport>( | |||
205 | *BTNullRefArg, "Forming reference to null pointer", ErrorNode); | |||
206 | if (ArgE) { | |||
207 | const Expr *ArgEDeref = bugreporter::getDerefExpr(ArgE); | |||
208 | if (!ArgEDeref) | |||
209 | ArgEDeref = ArgE; | |||
210 | bugreporter::trackExpressionValue(ErrorNode, ArgEDeref, *R); | |||
211 | } | |||
212 | return R; | |||
213 | ||||
214 | } | |||
215 | ||||
216 | void ento::registerNonNullParamChecker(CheckerManager &mgr) { | |||
217 | mgr.registerChecker<NonNullParamChecker>(); | |||
218 | } | |||
219 | ||||
220 | bool ento::shouldRegisterNonNullParamChecker(const LangOptions &LO) { | |||
221 | return true; | |||
222 | } |
1 | //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- 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 | // This file implements the SmallBitVector class. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_ADT_SMALLBITVECTOR_H |
14 | #define LLVM_ADT_SMALLBITVECTOR_H |
15 | |
16 | #include "llvm/ADT/BitVector.h" |
17 | #include "llvm/ADT/iterator_range.h" |
18 | #include "llvm/Support/MathExtras.h" |
19 | #include <algorithm> |
20 | #include <cassert> |
21 | #include <climits> |
22 | #include <cstddef> |
23 | #include <cstdint> |
24 | #include <limits> |
25 | #include <utility> |
26 | |
27 | namespace llvm { |
28 | |
29 | /// This is a 'bitvector' (really, a variable-sized bit array), optimized for |
30 | /// the case when the array is small. It contains one pointer-sized field, which |
31 | /// is directly used as a plain collection of bits when possible, or as a |
32 | /// pointer to a larger heap-allocated array when necessary. This allows normal |
33 | /// "small" cases to be fast without losing generality for large inputs. |
34 | class SmallBitVector { |
35 | // TODO: In "large" mode, a pointer to a BitVector is used, leading to an |
36 | // unnecessary level of indirection. It would be more efficient to use a |
37 | // pointer to memory containing size, allocation size, and the array of bits. |
38 | uintptr_t X = 1; |
39 | |
40 | enum { |
41 | // The number of bits in this class. |
42 | NumBaseBits = sizeof(uintptr_t) * CHAR_BIT8, |
43 | |
44 | // One bit is used to discriminate between small and large mode. The |
45 | // remaining bits are used for the small-mode representation. |
46 | SmallNumRawBits = NumBaseBits - 1, |
47 | |
48 | // A few more bits are used to store the size of the bit set in small mode. |
49 | // Theoretically this is a ceil-log2. These bits are encoded in the most |
50 | // significant bits of the raw bits. |
51 | SmallNumSizeBits = (NumBaseBits == 32 ? 5 : |
52 | NumBaseBits == 64 ? 6 : |
53 | SmallNumRawBits), |
54 | |
55 | // The remaining bits are used to store the actual set in small mode. |
56 | SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits |
57 | }; |
58 | |
59 | static_assert(NumBaseBits == 64 || NumBaseBits == 32, |
60 | "Unsupported word size"); |
61 | |
62 | public: |
63 | using size_type = unsigned; |
64 | |
65 | // Encapsulation of a single bit. |
66 | class reference { |
67 | SmallBitVector &TheVector; |
68 | unsigned BitPos; |
69 | |
70 | public: |
71 | reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} |
72 | |
73 | reference(const reference&) = default; |
74 | |
75 | reference& operator=(reference t) { |
76 | *this = bool(t); |
77 | return *this; |
78 | } |
79 | |
80 | reference& operator=(bool t) { |
81 | if (t) |
82 | TheVector.set(BitPos); |
83 | else |
84 | TheVector.reset(BitPos); |
85 | return *this; |
86 | } |
87 | |
88 | operator bool() const { |
89 | return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); |
90 | } |
91 | }; |
92 | |
93 | private: |
94 | BitVector *getPointer() const { |
95 | assert(!isSmall())((!isSmall()) ? static_cast<void> (0) : __assert_fail ( "!isSmall()", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 95, __PRETTY_FUNCTION__)); |
96 | return reinterpret_cast<BitVector *>(X); |
97 | } |
98 | |
99 | void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { |
100 | X = 1; |
101 | setSmallSize(NewSize); |
102 | setSmallBits(NewSmallBits); |
103 | } |
104 | |
105 | void switchToLarge(BitVector *BV) { |
106 | X = reinterpret_cast<uintptr_t>(BV); |
107 | assert(!isSmall() && "Tried to use an unaligned pointer")((!isSmall() && "Tried to use an unaligned pointer") ? static_cast<void> (0) : __assert_fail ("!isSmall() && \"Tried to use an unaligned pointer\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 107, __PRETTY_FUNCTION__)); |
108 | } |
109 | |
110 | // Return all the bits used for the "small" representation; this includes |
111 | // bits for the size as well as the element bits. |
112 | uintptr_t getSmallRawBits() const { |
113 | assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 113, __PRETTY_FUNCTION__)); |
114 | return X >> 1; |
115 | } |
116 | |
117 | void setSmallRawBits(uintptr_t NewRawBits) { |
118 | assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 118, __PRETTY_FUNCTION__)); |
119 | X = (NewRawBits << 1) | uintptr_t(1); |
120 | } |
121 | |
122 | // Return the size. |
123 | size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; } |
124 | |
125 | void setSmallSize(size_t Size) { |
126 | setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); |
127 | } |
128 | |
129 | // Return the element bits. |
130 | uintptr_t getSmallBits() const { |
131 | return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); |
132 | } |
133 | |
134 | void setSmallBits(uintptr_t NewBits) { |
135 | setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | |
136 | (getSmallSize() << SmallNumDataBits)); |
137 | } |
138 | |
139 | public: |
140 | /// Creates an empty bitvector. |
141 | SmallBitVector() = default; |
142 | |
143 | /// Creates a bitvector of specified number of bits. All bits are initialized |
144 | /// to the specified value. |
145 | explicit SmallBitVector(unsigned s, bool t = false) { |
146 | if (s <= SmallNumDataBits) |
147 | switchToSmall(t ? ~uintptr_t(0) : 0, s); |
148 | else |
149 | switchToLarge(new BitVector(s, t)); |
150 | } |
151 | |
152 | /// SmallBitVector copy ctor. |
153 | SmallBitVector(const SmallBitVector &RHS) { |
154 | if (RHS.isSmall()) |
155 | X = RHS.X; |
156 | else |
157 | switchToLarge(new BitVector(*RHS.getPointer())); |
158 | } |
159 | |
160 | SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { |
161 | RHS.X = 1; |
162 | } |
163 | |
164 | ~SmallBitVector() { |
165 | if (!isSmall()) |
166 | delete getPointer(); |
167 | } |
168 | |
169 | using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>; |
170 | using set_iterator = const_set_bits_iterator; |
171 | |
172 | const_set_bits_iterator set_bits_begin() const { |
173 | return const_set_bits_iterator(*this); |
174 | } |
175 | |
176 | const_set_bits_iterator set_bits_end() const { |
177 | return const_set_bits_iterator(*this, -1); |
178 | } |
179 | |
180 | iterator_range<const_set_bits_iterator> set_bits() const { |
181 | return make_range(set_bits_begin(), set_bits_end()); |
182 | } |
183 | |
184 | bool isSmall() const { return X & uintptr_t(1); } |
185 | |
186 | /// Tests whether there are no bits in this bitvector. |
187 | bool empty() const { |
188 | return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); |
189 | } |
190 | |
191 | /// Returns the number of bits in this bitvector. |
192 | size_t size() const { |
193 | return isSmall() ? getSmallSize() : getPointer()->size(); |
194 | } |
195 | |
196 | /// Returns the number of bits which are set. |
197 | size_type count() const { |
198 | if (isSmall()) { |
199 | uintptr_t Bits = getSmallBits(); |
200 | return countPopulation(Bits); |
201 | } |
202 | return getPointer()->count(); |
203 | } |
204 | |
205 | /// Returns true if any bit is set. |
206 | bool any() const { |
207 | if (isSmall()) |
208 | return getSmallBits() != 0; |
209 | return getPointer()->any(); |
210 | } |
211 | |
212 | /// Returns true if all bits are set. |
213 | bool all() const { |
214 | if (isSmall()) |
215 | return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; |
216 | return getPointer()->all(); |
217 | } |
218 | |
219 | /// Returns true if none of the bits are set. |
220 | bool none() const { |
221 | if (isSmall()) |
222 | return getSmallBits() == 0; |
223 | return getPointer()->none(); |
224 | } |
225 | |
226 | /// Returns the index of the first set bit, -1 if none of the bits are set. |
227 | int find_first() const { |
228 | if (isSmall()) { |
229 | uintptr_t Bits = getSmallBits(); |
230 | if (Bits == 0) |
231 | return -1; |
232 | return countTrailingZeros(Bits); |
233 | } |
234 | return getPointer()->find_first(); |
235 | } |
236 | |
237 | int find_last() const { |
238 | if (isSmall()) { |
239 | uintptr_t Bits = getSmallBits(); |
240 | if (Bits == 0) |
241 | return -1; |
242 | return NumBaseBits - countLeadingZeros(Bits) - 1; |
243 | } |
244 | return getPointer()->find_last(); |
245 | } |
246 | |
247 | /// Returns the index of the first unset bit, -1 if all of the bits are set. |
248 | int find_first_unset() const { |
249 | if (isSmall()) { |
250 | if (count() == getSmallSize()) |
251 | return -1; |
252 | |
253 | uintptr_t Bits = getSmallBits(); |
254 | return countTrailingOnes(Bits); |
255 | } |
256 | return getPointer()->find_first_unset(); |
257 | } |
258 | |
259 | int find_last_unset() const { |
260 | if (isSmall()) { |
261 | if (count() == getSmallSize()) |
262 | return -1; |
263 | |
264 | uintptr_t Bits = getSmallBits(); |
265 | // Set unused bits. |
266 | Bits |= ~uintptr_t(0) << getSmallSize(); |
267 | return NumBaseBits - countLeadingOnes(Bits) - 1; |
268 | } |
269 | return getPointer()->find_last_unset(); |
270 | } |
271 | |
272 | /// Returns the index of the next set bit following the "Prev" bit. |
273 | /// Returns -1 if the next set bit is not found. |
274 | int find_next(unsigned Prev) const { |
275 | if (isSmall()) { |
276 | uintptr_t Bits = getSmallBits(); |
277 | // Mask off previous bits. |
278 | Bits &= ~uintptr_t(0) << (Prev + 1); |
279 | if (Bits == 0 || Prev + 1 >= getSmallSize()) |
280 | return -1; |
281 | return countTrailingZeros(Bits); |
282 | } |
283 | return getPointer()->find_next(Prev); |
284 | } |
285 | |
286 | /// Returns the index of the next unset bit following the "Prev" bit. |
287 | /// Returns -1 if the next unset bit is not found. |
288 | int find_next_unset(unsigned Prev) const { |
289 | if (isSmall()) { |
290 | ++Prev; |
291 | uintptr_t Bits = getSmallBits(); |
292 | // Mask in previous bits. |
293 | uintptr_t Mask = (1 << Prev) - 1; |
294 | Bits |= Mask; |
295 | |
296 | if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize()) |
297 | return -1; |
298 | return countTrailingOnes(Bits); |
299 | } |
300 | return getPointer()->find_next_unset(Prev); |
301 | } |
302 | |
303 | /// find_prev - Returns the index of the first set bit that precedes the |
304 | /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. |
305 | int find_prev(unsigned PriorTo) const { |
306 | if (isSmall()) { |
307 | if (PriorTo == 0) |
308 | return -1; |
309 | |
310 | --PriorTo; |
311 | uintptr_t Bits = getSmallBits(); |
312 | Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1); |
313 | if (Bits == 0) |
314 | return -1; |
315 | |
316 | return NumBaseBits - countLeadingZeros(Bits) - 1; |
317 | } |
318 | return getPointer()->find_prev(PriorTo); |
319 | } |
320 | |
321 | /// Clear all bits. |
322 | void clear() { |
323 | if (!isSmall()) |
324 | delete getPointer(); |
325 | switchToSmall(0, 0); |
326 | } |
327 | |
328 | /// Grow or shrink the bitvector. |
329 | void resize(unsigned N, bool t = false) { |
330 | if (!isSmall()) { |
331 | getPointer()->resize(N, t); |
332 | } else if (SmallNumDataBits >= N) { |
333 | uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; |
334 | setSmallSize(N); |
335 | setSmallBits(NewBits | getSmallBits()); |
336 | } else { |
337 | BitVector *BV = new BitVector(N, t); |
338 | uintptr_t OldBits = getSmallBits(); |
339 | for (size_t i = 0, e = getSmallSize(); i != e; ++i) |
340 | (*BV)[i] = (OldBits >> i) & 1; |
341 | switchToLarge(BV); |
342 | } |
343 | } |
344 | |
345 | void reserve(unsigned N) { |
346 | if (isSmall()) { |
347 | if (N > SmallNumDataBits) { |
348 | uintptr_t OldBits = getSmallRawBits(); |
349 | size_t SmallSize = getSmallSize(); |
350 | BitVector *BV = new BitVector(SmallSize); |
351 | for (size_t i = 0; i < SmallSize; ++i) |
352 | if ((OldBits >> i) & 1) |
353 | BV->set(i); |
354 | BV->reserve(N); |
355 | switchToLarge(BV); |
356 | } |
357 | } else { |
358 | getPointer()->reserve(N); |
359 | } |
360 | } |
361 | |
362 | // Set, reset, flip |
363 | SmallBitVector &set() { |
364 | if (isSmall()) |
365 | setSmallBits(~uintptr_t(0)); |
366 | else |
367 | getPointer()->set(); |
368 | return *this; |
369 | } |
370 | |
371 | SmallBitVector &set(unsigned Idx) { |
372 | if (isSmall()) { |
373 | assert(Idx <= static_cast<unsigned>(((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 375, __PRETTY_FUNCTION__)) |
374 | std::numeric_limits<uintptr_t>::digits) &&((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 375, __PRETTY_FUNCTION__)) |
375 | "undefined behavior")((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 375, __PRETTY_FUNCTION__)); |
376 | setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); |
377 | } |
378 | else |
379 | getPointer()->set(Idx); |
380 | return *this; |
381 | } |
382 | |
383 | /// Efficiently set a range of bits in [I, E) |
384 | SmallBitVector &set(unsigned I, unsigned E) { |
385 | assert(I <= E && "Attempted to set backwards range!")((I <= E && "Attempted to set backwards range!") ? static_cast<void> (0) : __assert_fail ("I <= E && \"Attempted to set backwards range!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 385, __PRETTY_FUNCTION__)); |
386 | assert(E <= size() && "Attempted to set out-of-bounds range!")((E <= size() && "Attempted to set out-of-bounds range!" ) ? static_cast<void> (0) : __assert_fail ("E <= size() && \"Attempted to set out-of-bounds range!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 386, __PRETTY_FUNCTION__)); |
387 | if (I == E) return *this; |
388 | if (isSmall()) { |
389 | uintptr_t EMask = ((uintptr_t)1) << E; |
390 | uintptr_t IMask = ((uintptr_t)1) << I; |
391 | uintptr_t Mask = EMask - IMask; |
392 | setSmallBits(getSmallBits() | Mask); |
393 | } else |
394 | getPointer()->set(I, E); |
395 | return *this; |
396 | } |
397 | |
398 | SmallBitVector &reset() { |
399 | if (isSmall()) |
400 | setSmallBits(0); |
401 | else |
402 | getPointer()->reset(); |
403 | return *this; |
404 | } |
405 | |
406 | SmallBitVector &reset(unsigned Idx) { |
407 | if (isSmall()) |
408 | setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); |
409 | else |
410 | getPointer()->reset(Idx); |
411 | return *this; |
412 | } |
413 | |
414 | /// Efficiently reset a range of bits in [I, E) |
415 | SmallBitVector &reset(unsigned I, unsigned E) { |
416 | assert(I <= E && "Attempted to reset backwards range!")((I <= E && "Attempted to reset backwards range!") ? static_cast<void> (0) : __assert_fail ("I <= E && \"Attempted to reset backwards range!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 416, __PRETTY_FUNCTION__)); |
417 | assert(E <= size() && "Attempted to reset out-of-bounds range!")((E <= size() && "Attempted to reset out-of-bounds range!" ) ? static_cast<void> (0) : __assert_fail ("E <= size() && \"Attempted to reset out-of-bounds range!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 417, __PRETTY_FUNCTION__)); |
418 | if (I == E) return *this; |
419 | if (isSmall()) { |
420 | uintptr_t EMask = ((uintptr_t)1) << E; |
421 | uintptr_t IMask = ((uintptr_t)1) << I; |
422 | uintptr_t Mask = EMask - IMask; |
423 | setSmallBits(getSmallBits() & ~Mask); |
424 | } else |
425 | getPointer()->reset(I, E); |
426 | return *this; |
427 | } |
428 | |
429 | SmallBitVector &flip() { |
430 | if (isSmall()) |
431 | setSmallBits(~getSmallBits()); |
432 | else |
433 | getPointer()->flip(); |
434 | return *this; |
435 | } |
436 | |
437 | SmallBitVector &flip(unsigned Idx) { |
438 | if (isSmall()) |
439 | setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); |
440 | else |
441 | getPointer()->flip(Idx); |
442 | return *this; |
443 | } |
444 | |
445 | // No argument flip. |
446 | SmallBitVector operator~() const { |
447 | return SmallBitVector(*this).flip(); |
448 | } |
449 | |
450 | // Indexing. |
451 | reference operator[](unsigned Idx) { |
452 | assert(Idx < size() && "Out-of-bounds Bit access.")((Idx < size() && "Out-of-bounds Bit access.") ? static_cast <void> (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 452, __PRETTY_FUNCTION__)); |
453 | return reference(*this, Idx); |
454 | } |
455 | |
456 | bool operator[](unsigned Idx) const { |
457 | assert(Idx < size() && "Out-of-bounds Bit access.")((Idx < size() && "Out-of-bounds Bit access.") ? static_cast <void> (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 457, __PRETTY_FUNCTION__)); |
458 | if (isSmall()) |
459 | return ((getSmallBits() >> Idx) & 1) != 0; |
460 | return getPointer()->operator[](Idx); |
461 | } |
462 | |
463 | bool test(unsigned Idx) const { |
464 | return (*this)[Idx]; |
465 | } |
466 | |
467 | // Push single bit to end of vector. |
468 | void push_back(bool Val) { |
469 | resize(size() + 1, Val); |
470 | } |
471 | |
472 | /// Test if any common bits are set. |
473 | bool anyCommon(const SmallBitVector &RHS) const { |
474 | if (isSmall() && RHS.isSmall()) |
475 | return (getSmallBits() & RHS.getSmallBits()) != 0; |
476 | if (!isSmall() && !RHS.isSmall()) |
477 | return getPointer()->anyCommon(*RHS.getPointer()); |
478 | |
479 | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
480 | if (test(i) && RHS.test(i)) |
481 | return true; |
482 | return false; |
483 | } |
484 | |
485 | // Comparison operators. |
486 | bool operator==(const SmallBitVector &RHS) const { |
487 | if (size() != RHS.size()) |
488 | return false; |
489 | if (isSmall() && RHS.isSmall()) |
490 | return getSmallBits() == RHS.getSmallBits(); |
491 | else if (!isSmall() && !RHS.isSmall()) |
492 | return *getPointer() == *RHS.getPointer(); |
493 | else { |
494 | for (size_t i = 0, e = size(); i != e; ++i) { |
495 | if ((*this)[i] != RHS[i]) |
496 | return false; |
497 | } |
498 | return true; |
499 | } |
500 | } |
501 | |
502 | bool operator!=(const SmallBitVector &RHS) const { |
503 | return !(*this == RHS); |
504 | } |
505 | |
506 | // Intersection, union, disjoint union. |
507 | // FIXME BitVector::operator&= does not resize the LHS but this does |
508 | SmallBitVector &operator&=(const SmallBitVector &RHS) { |
509 | resize(std::max(size(), RHS.size())); |
510 | if (isSmall() && RHS.isSmall()) |
511 | setSmallBits(getSmallBits() & RHS.getSmallBits()); |
512 | else if (!isSmall() && !RHS.isSmall()) |
513 | getPointer()->operator&=(*RHS.getPointer()); |
514 | else { |
515 | size_t i, e; |
516 | for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
517 | (*this)[i] = test(i) && RHS.test(i); |
518 | for (e = size(); i != e; ++i) |
519 | reset(i); |
520 | } |
521 | return *this; |
522 | } |
523 | |
524 | /// Reset bits that are set in RHS. Same as *this &= ~RHS. |
525 | SmallBitVector &reset(const SmallBitVector &RHS) { |
526 | if (isSmall() && RHS.isSmall()) |
527 | setSmallBits(getSmallBits() & ~RHS.getSmallBits()); |
528 | else if (!isSmall() && !RHS.isSmall()) |
529 | getPointer()->reset(*RHS.getPointer()); |
530 | else |
531 | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
532 | if (RHS.test(i)) |
533 | reset(i); |
534 | |
535 | return *this; |
536 | } |
537 | |
538 | /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). |
539 | bool test(const SmallBitVector &RHS) const { |
540 | if (isSmall() && RHS.isSmall()) |
541 | return (getSmallBits() & ~RHS.getSmallBits()) != 0; |
542 | if (!isSmall() && !RHS.isSmall()) |
543 | return getPointer()->test(*RHS.getPointer()); |
544 | |
545 | unsigned i, e; |
546 | for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
547 | if (test(i) && !RHS.test(i)) |
548 | return true; |
549 | |
550 | for (e = size(); i != e; ++i) |
551 | if (test(i)) |
552 | return true; |
553 | |
554 | return false; |
555 | } |
556 | |
557 | SmallBitVector &operator|=(const SmallBitVector &RHS) { |
558 | resize(std::max(size(), RHS.size())); |
559 | if (isSmall() && RHS.isSmall()) |
560 | setSmallBits(getSmallBits() | RHS.getSmallBits()); |
561 | else if (!isSmall() && !RHS.isSmall()) |
562 | getPointer()->operator|=(*RHS.getPointer()); |
563 | else { |
564 | for (size_t i = 0, e = RHS.size(); i != e; ++i) |
565 | (*this)[i] = test(i) || RHS.test(i); |
566 | } |
567 | return *this; |
568 | } |
569 | |
570 | SmallBitVector &operator^=(const SmallBitVector &RHS) { |
571 | resize(std::max(size(), RHS.size())); |
572 | if (isSmall() && RHS.isSmall()) |
573 | setSmallBits(getSmallBits() ^ RHS.getSmallBits()); |
574 | else if (!isSmall() && !RHS.isSmall()) |
575 | getPointer()->operator^=(*RHS.getPointer()); |
576 | else { |
577 | for (size_t i = 0, e = RHS.size(); i != e; ++i) |
578 | (*this)[i] = test(i) != RHS.test(i); |
579 | } |
580 | return *this; |
581 | } |
582 | |
583 | SmallBitVector &operator<<=(unsigned N) { |
584 | if (isSmall()) |
585 | setSmallBits(getSmallBits() << N); |
586 | else |
587 | getPointer()->operator<<=(N); |
588 | return *this; |
589 | } |
590 | |
591 | SmallBitVector &operator>>=(unsigned N) { |
592 | if (isSmall()) |
593 | setSmallBits(getSmallBits() >> N); |
594 | else |
595 | getPointer()->operator>>=(N); |
596 | return *this; |
597 | } |
598 | |
599 | // Assignment operator. |
600 | const SmallBitVector &operator=(const SmallBitVector &RHS) { |
601 | if (isSmall()) { |
602 | if (RHS.isSmall()) |
603 | X = RHS.X; |
604 | else |
605 | switchToLarge(new BitVector(*RHS.getPointer())); |
606 | } else { |
607 | if (!RHS.isSmall()) |
608 | *getPointer() = *RHS.getPointer(); |
609 | else { |
610 | delete getPointer(); |
611 | X = RHS.X; |
612 | } |
613 | } |
614 | return *this; |
615 | } |
616 | |
617 | const SmallBitVector &operator=(SmallBitVector &&RHS) { |
618 | if (this != &RHS) { |
619 | clear(); |
620 | swap(RHS); |
621 | } |
622 | return *this; |
623 | } |
624 | |
625 | void swap(SmallBitVector &RHS) { |
626 | std::swap(X, RHS.X); |
627 | } |
628 | |
629 | /// Add '1' bits from Mask to this vector. Don't resize. |
630 | /// This computes "*this |= Mask". |
631 | void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
632 | if (isSmall()) |
633 | applyMask<true, false>(Mask, MaskWords); |
634 | else |
635 | getPointer()->setBitsInMask(Mask, MaskWords); |
636 | } |
637 | |
638 | /// Clear any bits in this vector that are set in Mask. Don't resize. |
639 | /// This computes "*this &= ~Mask". |
640 | void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
641 | if (isSmall()) |
642 | applyMask<false, false>(Mask, MaskWords); |
643 | else |
644 | getPointer()->clearBitsInMask(Mask, MaskWords); |
645 | } |
646 | |
647 | /// Add a bit to this vector for every '0' bit in Mask. Don't resize. |
648 | /// This computes "*this |= ~Mask". |
649 | void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
650 | if (isSmall()) |
651 | applyMask<true, true>(Mask, MaskWords); |
652 | else |
653 | getPointer()->setBitsNotInMask(Mask, MaskWords); |
654 | } |
655 | |
656 | /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. |
657 | /// This computes "*this &= Mask". |
658 | void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
659 | if (isSmall()) |
660 | applyMask<false, true>(Mask, MaskWords); |
661 | else |
662 | getPointer()->clearBitsNotInMask(Mask, MaskWords); |
663 | } |
664 | |
665 | private: |
666 | template <bool AddBits, bool InvertMask> |
667 | void applyMask(const uint32_t *Mask, unsigned MaskWords) { |
668 | assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!")((MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!" ) ? static_cast<void> (0) : __assert_fail ("MaskWords <= sizeof(uintptr_t) && \"Mask is larger than base!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 668, __PRETTY_FUNCTION__)); |
669 | uintptr_t M = Mask[0]; |
670 | if (NumBaseBits == 64) |
671 | M |= uint64_t(Mask[1]) << 32; |
672 | if (InvertMask) |
673 | M = ~M; |
674 | if (AddBits) |
675 | setSmallBits(getSmallBits() | M); |
676 | else |
677 | setSmallBits(getSmallBits() & ~M); |
678 | } |
679 | }; |
680 | |
681 | inline SmallBitVector |
682 | operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
683 | SmallBitVector Result(LHS); |
684 | Result &= RHS; |
685 | return Result; |
686 | } |
687 | |
688 | inline SmallBitVector |
689 | operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
690 | SmallBitVector Result(LHS); |
691 | Result |= RHS; |
692 | return Result; |
693 | } |
694 | |
695 | inline SmallBitVector |
696 | operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
697 | SmallBitVector Result(LHS); |
698 | Result ^= RHS; |
699 | return Result; |
700 | } |
701 | |
702 | } // end namespace llvm |
703 | |
704 | namespace std { |
705 | |
706 | /// Implement std::swap in terms of BitVector swap. |
707 | inline void |
708 | swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { |
709 | LHS.swap(RHS); |
710 | } |
711 | |
712 | } // end namespace std |
713 | |
714 | #endif // LLVM_ADT_SMALLBITVECTOR_H |