Bug Summary

File:tools/clang/include/clang/Analysis/Support/BumpVector.h
Warning:line 39, column 65
Potential memory leak

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ExplodedGraph.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -relaxed-aliasing -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/tools/clang/lib/StaticAnalyzer/Core -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp -faddrsig

/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

1//===- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the template classes ExplodedNode and ExplodedGraph,
11// which represent a path-sensitive, intra-procedural "exploded graph."
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
16#include "clang/AST/Expr.h"
17#include "clang/AST/ExprObjC.h"
18#include "clang/AST/ParentMap.h"
19#include "clang/AST/Stmt.h"
20#include "clang/Analysis/ProgramPoint.h"
21#include "clang/Analysis/Support/BumpVector.h"
22#include "clang/Basic/LLVM.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
26#include "llvm/ADT/DenseSet.h"
27#include "llvm/ADT/FoldingSet.h"
28#include "llvm/ADT/Optional.h"
29#include "llvm/ADT/PointerUnion.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/Support/Casting.h"
32#include <cassert>
33#include <memory>
34
35using namespace clang;
36using namespace ento;
37
38//===----------------------------------------------------------------------===//
39// Node auditing.
40//===----------------------------------------------------------------------===//
41
42// An out of line virtual method to provide a home for the class vtable.
43ExplodedNode::Auditor::~Auditor() = default;
44
45#ifndef NDEBUG
46static ExplodedNode::Auditor* NodeAuditor = nullptr;
47#endif
48
49void ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) {
50#ifndef NDEBUG
51 NodeAuditor = A;
52#endif
53}
54
55//===----------------------------------------------------------------------===//
56// Cleanup.
57//===----------------------------------------------------------------------===//
58
59ExplodedGraph::ExplodedGraph() = default;
10
Calling default constructor for 'BumpVectorContext'
60
61ExplodedGraph::~ExplodedGraph() = default;
62
63//===----------------------------------------------------------------------===//
64// Node reclamation.
65//===----------------------------------------------------------------------===//
66
67bool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) {
68 if (!Ex->isLValue())
69 return false;
70 return isa<DeclRefExpr>(Ex) ||
71 isa<MemberExpr>(Ex) ||
72 isa<ObjCIvarRefExpr>(Ex);
73}
74
75bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {
76 // First, we only consider nodes for reclamation of the following
77 // conditions apply:
78 //
79 // (1) 1 predecessor (that has one successor)
80 // (2) 1 successor (that has one predecessor)
81 //
82 // If a node has no successor it is on the "frontier", while a node
83 // with no predecessor is a root.
84 //
85 // After these prerequisites, we discard all "filler" nodes that
86 // are used only for intermediate processing, and are not essential
87 // for analyzer history:
88 //
89 // (a) PreStmtPurgeDeadSymbols
90 //
91 // We then discard all other nodes where *all* of the following conditions
92 // apply:
93 //
94 // (3) The ProgramPoint is for a PostStmt, but not a PostStore.
95 // (4) There is no 'tag' for the ProgramPoint.
96 // (5) The 'store' is the same as the predecessor.
97 // (6) The 'GDM' is the same as the predecessor.
98 // (7) The LocationContext is the same as the predecessor.
99 // (8) Expressions that are *not* lvalue expressions.
100 // (9) The PostStmt isn't for a non-consumed Stmt or Expr.
101 // (10) The successor is neither a CallExpr StmtPoint nor a CallEnter or
102 // PreImplicitCall (so that we would be able to find it when retrying a
103 // call with no inlining).
104 // FIXME: It may be safe to reclaim PreCall and PostCall nodes as well.
105
106 // Conditions 1 and 2.
107 if (node->pred_size() != 1 || node->succ_size() != 1)
108 return false;
109
110 const ExplodedNode *pred = *(node->pred_begin());
111 if (pred->succ_size() != 1)
112 return false;
113
114 const ExplodedNode *succ = *(node->succ_begin());
115 if (succ->pred_size() != 1)
116 return false;
117
118 // Now reclaim any nodes that are (by definition) not essential to
119 // analysis history and are not consulted by any client code.
120 ProgramPoint progPoint = node->getLocation();
121 if (progPoint.getAs<PreStmtPurgeDeadSymbols>())
122 return !progPoint.getTag();
123
124 // Condition 3.
125 if (!progPoint.getAs<PostStmt>() || progPoint.getAs<PostStore>())
126 return false;
127
128 // Condition 4.
129 if (progPoint.getTag())
130 return false;
131
132 // Conditions 5, 6, and 7.
133 ProgramStateRef state = node->getState();
134 ProgramStateRef pred_state = pred->getState();
135 if (state->store != pred_state->store || state->GDM != pred_state->GDM ||
136 progPoint.getLocationContext() != pred->getLocationContext())
137 return false;
138
139 // All further checks require expressions. As per #3, we know that we have
140 // a PostStmt.
141 const Expr *Ex = dyn_cast<Expr>(progPoint.castAs<PostStmt>().getStmt());
142 if (!Ex)
143 return false;
144
145 // Condition 8.
146 // Do not collect nodes for "interesting" lvalue expressions since they are
147 // used extensively for generating path diagnostics.
148 if (isInterestingLValueExpr(Ex))
149 return false;
150
151 // Condition 9.
152 // Do not collect nodes for non-consumed Stmt or Expr to ensure precise
153 // diagnostic generation; specifically, so that we could anchor arrows
154 // pointing to the beginning of statements (as written in code).
155 ParentMap &PM = progPoint.getLocationContext()->getParentMap();
156 if (!PM.isConsumedExpr(Ex))
157 return false;
158
159 // Condition 10.
160 const ProgramPoint SuccLoc = succ->getLocation();
161 if (Optional<StmtPoint> SP = SuccLoc.getAs<StmtPoint>())
162 if (CallEvent::isCallStmt(SP->getStmt()))
163 return false;
164
165 // Condition 10, continuation.
166 if (SuccLoc.getAs<CallEnter>() || SuccLoc.getAs<PreImplicitCall>())
167 return false;
168
169 return true;
170}
171
172void ExplodedGraph::collectNode(ExplodedNode *node) {
173 // Removing a node means:
174 // (a) changing the predecessors successor to the successor of this node
175 // (b) changing the successors predecessor to the predecessor of this node
176 // (c) Putting 'node' onto freeNodes.
177 assert(node->pred_size() == 1 || node->succ_size() == 1)(static_cast <bool> (node->pred_size() == 1 || node->
succ_size() == 1) ? void (0) : __assert_fail ("node->pred_size() == 1 || node->succ_size() == 1"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 177, __extension__ __PRETTY_FUNCTION__))
;
178 ExplodedNode *pred = *(node->pred_begin());
179 ExplodedNode *succ = *(node->succ_begin());
180 pred->replaceSuccessor(succ);
181 succ->replacePredecessor(pred);
182 FreeNodes.push_back(node);
183 Nodes.RemoveNode(node);
184 --NumNodes;
185 node->~ExplodedNode();
186}
187
188void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
189 if (ChangedNodes.empty())
190 return;
191
192 // Only periodically reclaim nodes so that we can build up a set of
193 // nodes that meet the reclamation criteria. Freshly created nodes
194 // by definition have no successor, and thus cannot be reclaimed (see below).
195 assert(ReclaimCounter > 0)(static_cast <bool> (ReclaimCounter > 0) ? void (0) :
__assert_fail ("ReclaimCounter > 0", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 195, __extension__ __PRETTY_FUNCTION__))
;
196 if (--ReclaimCounter != 0)
197 return;
198 ReclaimCounter = ReclaimNodeInterval;
199
200 for (const auto node : ChangedNodes)
201 if (shouldCollect(node))
202 collectNode(node);
203 ChangedNodes.clear();
204}
205
206//===----------------------------------------------------------------------===//
207// ExplodedNode.
208//===----------------------------------------------------------------------===//
209
210// An NodeGroup's storage type is actually very much like a TinyPtrVector:
211// it can be either a pointer to a single ExplodedNode, or a pointer to a
212// BumpVector allocated with the ExplodedGraph's allocator. This allows the
213// common case of single-node NodeGroups to be implemented with no extra memory.
214//
215// Consequently, each of the NodeGroup methods have up to four cases to handle:
216// 1. The flag is set and this group does not actually contain any nodes.
217// 2. The group is empty, in which case the storage value is null.
218// 3. The group contains a single node.
219// 4. The group contains more than one node.
220using ExplodedNodeVector = BumpVector<ExplodedNode *>;
221using GroupStorage = llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *>;
222
223void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) {
224 assert(!V->isSink())(static_cast <bool> (!V->isSink()) ? void (0) : __assert_fail
("!V->isSink()", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 224, __extension__ __PRETTY_FUNCTION__))
;
225 Preds.addNode(V, G);
226 V->Succs.addNode(this, G);
227#ifndef NDEBUG
228 if (NodeAuditor) NodeAuditor->AddEdge(V, this);
229#endif
230}
231
232void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
233 assert(!getFlag())(static_cast <bool> (!getFlag()) ? void (0) : __assert_fail
("!getFlag()", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 233, __extension__ __PRETTY_FUNCTION__))
;
234
235 GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
236 assert(Storage.is<ExplodedNode *>())(static_cast <bool> (Storage.is<ExplodedNode *>()
) ? void (0) : __assert_fail ("Storage.is<ExplodedNode *>()"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 236, __extension__ __PRETTY_FUNCTION__))
;
237 Storage = node;
238 assert(Storage.is<ExplodedNode *>())(static_cast <bool> (Storage.is<ExplodedNode *>()
) ? void (0) : __assert_fail ("Storage.is<ExplodedNode *>()"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 238, __extension__ __PRETTY_FUNCTION__))
;
239}
240
241void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
242 assert(!getFlag())(static_cast <bool> (!getFlag()) ? void (0) : __assert_fail
("!getFlag()", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 242, __extension__ __PRETTY_FUNCTION__))
;
243
244 GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
245 if (Storage.isNull()) {
246 Storage = N;
247 assert(Storage.is<ExplodedNode *>())(static_cast <bool> (Storage.is<ExplodedNode *>()
) ? void (0) : __assert_fail ("Storage.is<ExplodedNode *>()"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 247, __extension__ __PRETTY_FUNCTION__))
;
248 return;
249 }
250
251 ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>();
252
253 if (!V) {
254 // Switch from single-node to multi-node representation.
255 ExplodedNode *Old = Storage.get<ExplodedNode *>();
256
257 BumpVectorContext &Ctx = G.getNodeAllocator();
258 V = G.getAllocator().Allocate<ExplodedNodeVector>();
259 new (V) ExplodedNodeVector(Ctx, 4);
260 V->push_back(Old, Ctx);
261
262 Storage = V;
263 assert(!getFlag())(static_cast <bool> (!getFlag()) ? void (0) : __assert_fail
("!getFlag()", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 263, __extension__ __PRETTY_FUNCTION__))
;
264 assert(Storage.is<ExplodedNodeVector *>())(static_cast <bool> (Storage.is<ExplodedNodeVector *
>()) ? void (0) : __assert_fail ("Storage.is<ExplodedNodeVector *>()"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp"
, 264, __extension__ __PRETTY_FUNCTION__))
;
265 }
266
267 V->push_back(N, G.getNodeAllocator());
268}
269
270unsigned ExplodedNode::NodeGroup::size() const {
271 if (getFlag())
272 return 0;
273
274 const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
275 if (Storage.isNull())
276 return 0;
277 if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
278 return V->size();
279 return 1;
280}
281
282ExplodedNode * const *ExplodedNode::NodeGroup::begin() const {
283 if (getFlag())
284 return nullptr;
285
286 const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
287 if (Storage.isNull())
288 return nullptr;
289 if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
290 return V->begin();
291 return Storage.getAddrOfPtr1();
292}
293
294ExplodedNode * const *ExplodedNode::NodeGroup::end() const {
295 if (getFlag())
296 return nullptr;
297
298 const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
299 if (Storage.isNull())
300 return nullptr;
301 if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
302 return V->end();
303 return Storage.getAddrOfPtr1() + 1;
304}
305
306ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
307 ProgramStateRef State,
308 bool IsSink,
309 bool* IsNew) {
310 // Profile 'State' to determine if we already have an existing node.
311 llvm::FoldingSetNodeID profile;
312 void *InsertPos = nullptr;
313
314 NodeTy::Profile(profile, L, State, IsSink);
315 NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
316
317 if (!V) {
318 if (!FreeNodes.empty()) {
319 V = FreeNodes.back();
320 FreeNodes.pop_back();
321 }
322 else {
323 // Allocate a new node.
324 V = (NodeTy*) getAllocator().Allocate<NodeTy>();
325 }
326
327 new (V) NodeTy(L, State, IsSink);
328
329 if (ReclaimNodeInterval)
330 ChangedNodes.push_back(V);
331
332 // Insert the node into the node set and return it.
333 Nodes.InsertNode(V, InsertPos);
334 ++NumNodes;
335
336 if (IsNew) *IsNew = true;
337 }
338 else
339 if (IsNew) *IsNew = false;
340
341 return V;
342}
343
344ExplodedNode *ExplodedGraph::createUncachedNode(const ProgramPoint &L,
345 ProgramStateRef State,
346 bool IsSink) {
347 NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
348 new (V) NodeTy(L, State, IsSink);
349 return V;
350}
351
352std::unique_ptr<ExplodedGraph>
353ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
354 InterExplodedGraphMap *ForwardMap,
355 InterExplodedGraphMap *InverseMap) const {
356 if (Nodes.empty())
1
Taking false branch
357 return nullptr;
358
359 using Pass1Ty = llvm::DenseSet<const ExplodedNode *>;
360 Pass1Ty Pass1;
361
362 using Pass2Ty = InterExplodedGraphMap;
363 InterExplodedGraphMap Pass2Scratch;
364 Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;
2
Assuming 'ForwardMap' is null
3
'?' condition is false
365
366 SmallVector<const ExplodedNode*, 10> WL1, WL2;
367
368 // ===- Pass 1 (reverse DFS) -===
369 for (const auto Sink : Sinks)
4
Assuming '__begin1' is equal to '__end1'
370 if (Sink)
371 WL1.push_back(Sink);
372
373 // Process the first worklist until it is empty.
374 while (!WL1.empty()) {
5
Loop condition is false. Execution continues on line 392
375 const ExplodedNode *N = WL1.pop_back_val();
376
377 // Have we already visited this node? If so, continue to the next one.
378 if (!Pass1.insert(N).second)
379 continue;
380
381 // If this is a root enqueue it to the second worklist.
382 if (N->Preds.empty()) {
383 WL2.push_back(N);
384 continue;
385 }
386
387 // Visit our predecessors and enqueue them.
388 WL1.append(N->Preds.begin(), N->Preds.end());
389 }
390
391 // We didn't hit a root? Return with a null pointer for the new graph.
392 if (WL2.empty())
6
Taking false branch
393 return nullptr;
394
395 // Create an empty graph.
396 std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
7
Calling 'ExplodedGraph::MakeEmptyGraph'
397
398 // ===- Pass 2 (forward DFS to construct the new graph) -===
399 while (!WL2.empty()) {
400 const ExplodedNode *N = WL2.pop_back_val();
401
402 // Skip this node if we have already processed it.
403 if (Pass2.find(N) != Pass2.end())
404 continue;
405
406 // Create the corresponding node in the new graph and record the mapping
407 // from the old node to the new node.
408 ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State, N->isSink());
409 Pass2[N] = NewN;
410
411 // Also record the reverse mapping from the new node to the old node.
412 if (InverseMap) (*InverseMap)[NewN] = N;
413
414 // If this node is a root, designate it as such in the graph.
415 if (N->Preds.empty())
416 G->addRoot(NewN);
417
418 // In the case that some of the intended predecessors of NewN have already
419 // been created, we should hook them up as predecessors.
420
421 // Walk through the predecessors of 'N' and hook up their corresponding
422 // nodes in the new graph (if any) to the freshly created node.
423 for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
424 I != E; ++I) {
425 Pass2Ty::iterator PI = Pass2.find(*I);
426 if (PI == Pass2.end())
427 continue;
428
429 NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
430 }
431
432 // In the case that some of the intended successors of NewN have already
433 // been created, we should hook them up as successors. Otherwise, enqueue
434 // the new nodes from the original graph that should have nodes created
435 // in the new graph.
436 for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
437 I != E; ++I) {
438 Pass2Ty::iterator PI = Pass2.find(*I);
439 if (PI != Pass2.end()) {
440 const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
441 continue;
442 }
443
444 // Enqueue nodes to the worklist that were marked during pass 1.
445 if (Pass1.count(*I))
446 WL2.push_back(*I);
447 }
448 }
449
450 return G;
451}

/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

1//===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the template classes ExplodedNode and ExplodedGraph,
11// which represent a path-sensitive, intra-procedural "exploded graph."
12// See "Precise interprocedural dataflow analysis via graph reachability"
13// by Reps, Horwitz, and Sagiv
14// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an
15// exploded graph.
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
20#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
21
22#include "clang/Analysis/AnalysisDeclContext.h"
23#include "clang/Analysis/ProgramPoint.h"
24#include "clang/Analysis/Support/BumpVector.h"
25#include "clang/Basic/LLVM.h"
26#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
27#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
28#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
29#include "llvm/ADT/ArrayRef.h"
30#include "llvm/ADT/DenseMap.h"
31#include "llvm/ADT/DepthFirstIterator.h"
32#include "llvm/ADT/FoldingSet.h"
33#include "llvm/ADT/GraphTraits.h"
34#include "llvm/ADT/Optional.h"
35#include "llvm/ADT/STLExtras.h"
36#include "llvm/ADT/SetVector.h"
37#include "llvm/Support/Allocator.h"
38#include "llvm/Support/Compiler.h"
39#include <cassert>
40#include <cstdint>
41#include <memory>
42#include <utility>
43#include <vector>
44
45namespace clang {
46
47class CFG;
48class Decl;
49class Expr;
50class ParentMap;
51class Stmt;
52
53namespace ento {
54
55class ExplodedGraph;
56
57//===----------------------------------------------------------------------===//
58// ExplodedGraph "implementation" classes. These classes are not typed to
59// contain a specific kind of state. Typed-specialized versions are defined
60// on top of these classes.
61//===----------------------------------------------------------------------===//
62
63// ExplodedNode is not constified all over the engine because we need to add
64// successors to it at any time after creating it.
65
66class ExplodedNode : public llvm::FoldingSetNode {
67 friend class BranchNodeBuilder;
68 friend class CoreEngine;
69 friend class EndOfFunctionNodeBuilder;
70 friend class ExplodedGraph;
71 friend class IndirectGotoNodeBuilder;
72 friend class NodeBuilder;
73 friend class SwitchNodeBuilder;
74
75 /// Efficiently stores a list of ExplodedNodes, or an optional flag.
76 ///
77 /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
78 /// for the case when there is only one node in the group. This is a fairly
79 /// common case in an ExplodedGraph, where most nodes have only one
80 /// predecessor and many have only one successor. It can also be used to
81 /// store a flag rather than a node list, which ExplodedNode uses to mark
82 /// whether a node is a sink. If the flag is set, the group is implicitly
83 /// empty and no nodes may be added.
84 class NodeGroup {
85 // Conceptually a discriminated union. If the low bit is set, the node is
86 // a sink. If the low bit is not set, the pointer refers to the storage
87 // for the nodes in the group.
88 // This is not a PointerIntPair in order to keep the storage type opaque.
89 uintptr_t P;
90
91 public:
92 NodeGroup(bool Flag = false) : P(Flag) {
93 assert(getFlag() == Flag)(static_cast <bool> (getFlag() == Flag) ? void (0) : __assert_fail
("getFlag() == Flag", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
, 93, __extension__ __PRETTY_FUNCTION__))
;
94 }
95
96 ExplodedNode * const *begin() const;
97
98 ExplodedNode * const *end() const;
99
100 unsigned size() const;
101
102 bool empty() const { return P == 0 || getFlag() != 0; }
103
104 /// Adds a node to the list.
105 ///
106 /// The group must not have been created with its flag set.
107 void addNode(ExplodedNode *N, ExplodedGraph &G);
108
109 /// Replaces the single node in this group with a new node.
110 ///
111 /// Note that this should only be used when you know the group was not
112 /// created with its flag set, and that the group is empty or contains
113 /// only a single node.
114 void replaceNode(ExplodedNode *node);
115
116 /// Returns whether this group was created with its flag set.
117 bool getFlag() const {
118 return (P & 1);
119 }
120 };
121
122 /// Location - The program location (within a function body) associated
123 /// with this node.
124 const ProgramPoint Location;
125
126 /// State - The state associated with this node.
127 ProgramStateRef State;
128
129 /// Preds - The predecessors of this node.
130 NodeGroup Preds;
131
132 /// Succs - The successors of this node.
133 NodeGroup Succs;
134
135public:
136 explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
137 bool IsSink)
138 : Location(loc), State(std::move(state)), Succs(IsSink) {
139 assert(isSink() == IsSink)(static_cast <bool> (isSink() == IsSink) ? void (0) : __assert_fail
("isSink() == IsSink", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
, 139, __extension__ __PRETTY_FUNCTION__))
;
140 }
141
142 /// getLocation - Returns the edge associated with the given node.
143 ProgramPoint getLocation() const { return Location; }
144
145 const LocationContext *getLocationContext() const {
146 return getLocation().getLocationContext();
147 }
148
149 const StackFrameContext *getStackFrame() const {
150 return getLocation().getStackFrame();
151 }
152
153 const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
154
155 CFG &getCFG() const { return *getLocationContext()->getCFG(); }
156
157 ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
158
159 template <typename T>
160 T &getAnalysis() const {
161 return *getLocationContext()->getAnalysis<T>();
162 }
163
164 const ProgramStateRef &getState() const { return State; }
165
166 template <typename T>
167 Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION& {
168 return Location.getAs<T>();
169 }
170
171 /// Get the value of an arbitrary expression at this node.
172 SVal getSVal(const Stmt *S) const {
173 return getState()->getSVal(S, getLocationContext());
174 }
175
176 static void Profile(llvm::FoldingSetNodeID &ID,
177 const ProgramPoint &Loc,
178 const ProgramStateRef &state,
179 bool IsSink) {
180 ID.Add(Loc);
181 ID.AddPointer(state.get());
182 ID.AddBoolean(IsSink);
183 }
184
185 void Profile(llvm::FoldingSetNodeID& ID) const {
186 // We avoid copy constructors by not using accessors.
187 Profile(ID, Location, State, isSink());
188 }
189
190 /// addPredeccessor - Adds a predecessor to the current node, and
191 /// in tandem add this node as a successor of the other node.
192 void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
193
194 unsigned succ_size() const { return Succs.size(); }
195 unsigned pred_size() const { return Preds.size(); }
196 bool succ_empty() const { return Succs.empty(); }
197 bool pred_empty() const { return Preds.empty(); }
198
199 bool isSink() const { return Succs.getFlag(); }
200
201 bool hasSinglePred() const {
202 return (pred_size() == 1);
203 }
204
205 ExplodedNode *getFirstPred() {
206 return pred_empty() ? nullptr : *(pred_begin());
207 }
208
209 const ExplodedNode *getFirstPred() const {
210 return const_cast<ExplodedNode*>(this)->getFirstPred();
211 }
212
213 const ExplodedNode *getFirstSucc() const {
214 return succ_empty() ? nullptr : *(succ_begin());
215 }
216
217 // Iterators over successor and predecessor vertices.
218 using succ_iterator = ExplodedNode * const *;
219 using const_succ_iterator = const ExplodedNode * const *;
220 using pred_iterator = ExplodedNode * const *;
221 using const_pred_iterator = const ExplodedNode * const *;
222
223 pred_iterator pred_begin() { return Preds.begin(); }
224 pred_iterator pred_end() { return Preds.end(); }
225
226 const_pred_iterator pred_begin() const {
227 return const_cast<ExplodedNode*>(this)->pred_begin();
228 }
229 const_pred_iterator pred_end() const {
230 return const_cast<ExplodedNode*>(this)->pred_end();
231 }
232
233 succ_iterator succ_begin() { return Succs.begin(); }
234 succ_iterator succ_end() { return Succs.end(); }
235
236 const_succ_iterator succ_begin() const {
237 return const_cast<ExplodedNode*>(this)->succ_begin();
238 }
239 const_succ_iterator succ_end() const {
240 return const_cast<ExplodedNode*>(this)->succ_end();
241 }
242
243 // For debugging.
244
245public:
246 class Auditor {
247 public:
248 virtual ~Auditor();
249
250 virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0;
251 };
252
253 static void SetAuditor(Auditor* A);
254
255private:
256 void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
257 void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
258};
259
260using InterExplodedGraphMap =
261 llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
262
263class ExplodedGraph {
264protected:
265 friend class CoreEngine;
266
267 // Type definitions.
268 using NodeVector = std::vector<ExplodedNode *>;
269
270 /// The roots of the simulation graph. Usually there will be only
271 /// one, but clients are free to establish multiple subgraphs within a single
272 /// SimulGraph. Moreover, these subgraphs can often merge when paths from
273 /// different roots reach the same state at the same program location.
274 NodeVector Roots;
275
276 /// The nodes in the simulation graph which have been
277 /// specially marked as the endpoint of an abstract simulation path.
278 NodeVector EndNodes;
279
280 /// Nodes - The nodes in the graph.
281 llvm::FoldingSet<ExplodedNode> Nodes;
282
283 /// BVC - Allocator and context for allocating nodes and their predecessor
284 /// and successor groups.
285 BumpVectorContext BVC;
286
287 /// NumNodes - The number of nodes in the graph.
288 unsigned NumNodes = 0;
289
290 /// A list of recently allocated nodes that can potentially be recycled.
291 NodeVector ChangedNodes;
292
293 /// A list of nodes that can be reused.
294 NodeVector FreeNodes;
295
296 /// Determines how often nodes are reclaimed.
297 ///
298 /// If this is 0, nodes will never be reclaimed.
299 unsigned ReclaimNodeInterval = 0;
300
301 /// Counter to determine when to reclaim nodes.
302 unsigned ReclaimCounter;
303
304public:
305 ExplodedGraph();
306 ~ExplodedGraph();
307
308 /// Retrieve the node associated with a (Location,State) pair,
309 /// where the 'Location' is a ProgramPoint in the CFG. If no node for
310 /// this pair exists, it is created. IsNew is set to true if
311 /// the node was freshly created.
312 ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
313 bool IsSink = false,
314 bool* IsNew = nullptr);
315
316 /// Create a node for a (Location, State) pair,
317 /// but don't store it for deduplication later. This
318 /// is useful when copying an already completed
319 /// ExplodedGraph for further processing.
320 ExplodedNode *createUncachedNode(const ProgramPoint &L,
321 ProgramStateRef State,
322 bool IsSink = false);
323
324 std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
325 return llvm::make_unique<ExplodedGraph>();
8
Calling 'make_unique<clang::ento::ExplodedGraph, >'
326 }
327
328 /// addRoot - Add an untyped node to the set of roots.
329 ExplodedNode *addRoot(ExplodedNode *V) {
330 Roots.push_back(V);
331 return V;
332 }
333
334 /// addEndOfPath - Add an untyped node to the set of EOP nodes.
335 ExplodedNode *addEndOfPath(ExplodedNode *V) {
336 EndNodes.push_back(V);
337 return V;
338 }
339
340 unsigned num_roots() const { return Roots.size(); }
341 unsigned num_eops() const { return EndNodes.size(); }
342
343 bool empty() const { return NumNodes == 0; }
344 unsigned size() const { return NumNodes; }
345
346 void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
347
348 // Iterators.
349 using NodeTy = ExplodedNode;
350 using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
351 using roots_iterator = NodeVector::iterator;
352 using const_roots_iterator = NodeVector::const_iterator;
353 using eop_iterator = NodeVector::iterator;
354 using const_eop_iterator = NodeVector::const_iterator;
355 using node_iterator = AllNodesTy::iterator;
356 using const_node_iterator = AllNodesTy::const_iterator;
357
358 node_iterator nodes_begin() { return Nodes.begin(); }
359
360 node_iterator nodes_end() { return Nodes.end(); }
361
362 const_node_iterator nodes_begin() const { return Nodes.begin(); }
363
364 const_node_iterator nodes_end() const { return Nodes.end(); }
365
366 roots_iterator roots_begin() { return Roots.begin(); }
367
368 roots_iterator roots_end() { return Roots.end(); }
369
370 const_roots_iterator roots_begin() const { return Roots.begin(); }
371
372 const_roots_iterator roots_end() const { return Roots.end(); }
373
374 eop_iterator eop_begin() { return EndNodes.begin(); }
375
376 eop_iterator eop_end() { return EndNodes.end(); }
377
378 const_eop_iterator eop_begin() const { return EndNodes.begin(); }
379
380 const_eop_iterator eop_end() const { return EndNodes.end(); }
381
382 llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
383 BumpVectorContext &getNodeAllocator() { return BVC; }
384
385 using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
386
387 /// Creates a trimmed version of the graph that only contains paths leading
388 /// to the given nodes.
389 ///
390 /// \param Nodes The nodes which must appear in the final graph. Presumably
391 /// these are end-of-path nodes (i.e. they have no successors).
392 /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
393 /// the returned graph.
394 /// \param[out] InverseMap An optional map from nodes in the returned graph to
395 /// nodes in this graph.
396 /// \returns The trimmed graph
397 std::unique_ptr<ExplodedGraph>
398 trim(ArrayRef<const NodeTy *> Nodes,
399 InterExplodedGraphMap *ForwardMap = nullptr,
400 InterExplodedGraphMap *InverseMap = nullptr) const;
401
402 /// Enable tracking of recently allocated nodes for potential reclamation
403 /// when calling reclaimRecentlyAllocatedNodes().
404 void enableNodeReclamation(unsigned Interval) {
405 ReclaimCounter = ReclaimNodeInterval = Interval;
406 }
407
408 /// Reclaim "uninteresting" nodes created since the last time this method
409 /// was called.
410 void reclaimRecentlyAllocatedNodes();
411
412 /// Returns true if nodes for the given expression kind are always
413 /// kept around.
414 static bool isInterestingLValueExpr(const Expr *Ex);
415
416private:
417 bool shouldCollect(const ExplodedNode *node);
418 void collectNode(ExplodedNode *node);
419};
420
421class ExplodedNodeSet {
422 using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
423 ImplTy Impl;
424
425public:
426 ExplodedNodeSet(ExplodedNode *N) {
427 assert(N && !static_cast<ExplodedNode*>(N)->isSink())(static_cast <bool> (N && !static_cast<ExplodedNode
*>(N)->isSink()) ? void (0) : __assert_fail ("N && !static_cast<ExplodedNode*>(N)->isSink()"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
, 427, __extension__ __PRETTY_FUNCTION__))
;
428 Impl.insert(N);
429 }
430
431 ExplodedNodeSet() = default;
432
433 void Add(ExplodedNode *N) {
434 if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
435 }
436
437 using iterator = ImplTy::iterator;
438 using const_iterator = ImplTy::const_iterator;
439
440 unsigned size() const { return Impl.size(); }
441 bool empty() const { return Impl.empty(); }
442 bool erase(ExplodedNode *N) { return Impl.remove(N); }
443
444 void clear() { Impl.clear(); }
445
446 void insert(const ExplodedNodeSet &S) {
447 assert(&S != this)(static_cast <bool> (&S != this) ? void (0) : __assert_fail
("&S != this", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
, 447, __extension__ __PRETTY_FUNCTION__))
;
448 if (empty())
449 Impl = S.Impl;
450 else
451 Impl.insert(S.begin(), S.end());
452 }
453
454 iterator begin() { return Impl.begin(); }
455 iterator end() { return Impl.end(); }
456
457 const_iterator begin() const { return Impl.begin(); }
458 const_iterator end() const { return Impl.end(); }
459};
460
461} // namespace ento
462
463} // namespace clang
464
465// GraphTraits
466
467namespace llvm {
468
469 template<> struct GraphTraits<clang::ento::ExplodedNode*> {
470 using NodeRef = clang::ento::ExplodedNode *;
471 using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
472 using nodes_iterator = llvm::df_iterator<NodeRef>;
473
474 static NodeRef getEntryNode(NodeRef N) { return N; }
475
476 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
477
478 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
479
480 static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
481
482 static nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
483 };
484
485 template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
486 using NodeRef = const clang::ento::ExplodedNode *;
487 using ChildIteratorType = clang::ento::ExplodedNode::const_succ_iterator;
488 using nodes_iterator = llvm::df_iterator<NodeRef>;
489
490 static NodeRef getEntryNode(NodeRef N) { return N; }
491
492 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
493
494 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
495
496 static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
497
498 static nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
499 };
500
501} // namespace llvm
502
503#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H

/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains some templates that are useful if you are working with the
11// STL at all.
12//
13// No library is required when using these functions.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_STLEXTRAS_H
18#define LLVM_ADT_STLEXTRAS_H
19
20#include "llvm/ADT/Optional.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/iterator.h"
23#include "llvm/ADT/iterator_range.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdint>
29#include <cstdlib>
30#include <functional>
31#include <initializer_list>
32#include <iterator>
33#include <limits>
34#include <memory>
35#include <tuple>
36#include <type_traits>
37#include <utility>
38
39#ifdef EXPENSIVE_CHECKS
40#include <random> // for std::mt19937
41#endif
42
43namespace llvm {
44
45// Only used by compiler if both template types are the same. Useful when
46// using SFINAE to test for the existence of member functions.
47template <typename T, T> struct SameType;
48
49namespace detail {
50
51template <typename RangeT>
52using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
53
54template <typename RangeT>
55using ValueOfRange = typename std::remove_reference<decltype(
56 *std::begin(std::declval<RangeT &>()))>::type;
57
58} // end namespace detail
59
60//===----------------------------------------------------------------------===//
61// Extra additions to <type_traits>
62//===----------------------------------------------------------------------===//
63
64template <typename T>
65struct negation : std::integral_constant<bool, !bool(T::value)> {};
66
67template <typename...> struct conjunction : std::true_type {};
68template <typename B1> struct conjunction<B1> : B1 {};
69template <typename B1, typename... Bn>
70struct conjunction<B1, Bn...>
71 : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
72
73//===----------------------------------------------------------------------===//
74// Extra additions to <functional>
75//===----------------------------------------------------------------------===//
76
77template <class Ty> struct identity {
78 using argument_type = Ty;
79
80 Ty &operator()(Ty &self) const {
81 return self;
82 }
83 const Ty &operator()(const Ty &self) const {
84 return self;
85 }
86};
87
88template <class Ty> struct less_ptr {
89 bool operator()(const Ty* left, const Ty* right) const {
90 return *left < *right;
91 }
92};
93
94template <class Ty> struct greater_ptr {
95 bool operator()(const Ty* left, const Ty* right) const {
96 return *right < *left;
97 }
98};
99
100/// An efficient, type-erasing, non-owning reference to a callable. This is
101/// intended for use as the type of a function parameter that is not used
102/// after the function in question returns.
103///
104/// This class does not own the callable, so it is not in general safe to store
105/// a function_ref.
106template<typename Fn> class function_ref;
107
108template<typename Ret, typename ...Params>
109class function_ref<Ret(Params...)> {
110 Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
111 intptr_t callable;
112
113 template<typename Callable>
114 static Ret callback_fn(intptr_t callable, Params ...params) {
115 return (*reinterpret_cast<Callable*>(callable))(
116 std::forward<Params>(params)...);
117 }
118
119public:
120 function_ref() = default;
121 function_ref(std::nullptr_t) {}
122
123 template <typename Callable>
124 function_ref(Callable &&callable,
125 typename std::enable_if<
126 !std::is_same<typename std::remove_reference<Callable>::type,
127 function_ref>::value>::type * = nullptr)
128 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
129 callable(reinterpret_cast<intptr_t>(&callable)) {}
130
131 Ret operator()(Params ...params) const {
132 return callback(callable, std::forward<Params>(params)...);
133 }
134
135 operator bool() const { return callback; }
136};
137
138// deleter - Very very very simple method that is used to invoke operator
139// delete on something. It is used like this:
140//
141// for_each(V.begin(), B.end(), deleter<Interval>);
142template <class T>
143inline void deleter(T *Ptr) {
144 delete Ptr;
145}
146
147//===----------------------------------------------------------------------===//
148// Extra additions to <iterator>
149//===----------------------------------------------------------------------===//
150
151namespace adl_detail {
152
153using std::begin;
154
155template <typename ContainerTy>
156auto adl_begin(ContainerTy &&container)
157 -> decltype(begin(std::forward<ContainerTy>(container))) {
158 return begin(std::forward<ContainerTy>(container));
159}
160
161using std::end;
162
163template <typename ContainerTy>
164auto adl_end(ContainerTy &&container)
165 -> decltype(end(std::forward<ContainerTy>(container))) {
166 return end(std::forward<ContainerTy>(container));
167}
168
169using std::swap;
170
171template <typename T>
172void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
173 std::declval<T>()))) {
174 swap(std::forward<T>(lhs), std::forward<T>(rhs));
175}
176
177} // end namespace adl_detail
178
179template <typename ContainerTy>
180auto adl_begin(ContainerTy &&container)
181 -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
182 return adl_detail::adl_begin(std::forward<ContainerTy>(container));
183}
184
185template <typename ContainerTy>
186auto adl_end(ContainerTy &&container)
187 -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
188 return adl_detail::adl_end(std::forward<ContainerTy>(container));
189}
190
191template <typename T>
192void adl_swap(T &&lhs, T &&rhs) noexcept(
193 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
194 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
195}
196
197// mapped_iterator - This is a simple iterator adapter that causes a function to
198// be applied whenever operator* is invoked on the iterator.
199
200template <typename ItTy, typename FuncTy,
201 typename FuncReturnTy =
202 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
203class mapped_iterator
204 : public iterator_adaptor_base<
205 mapped_iterator<ItTy, FuncTy>, ItTy,
206 typename std::iterator_traits<ItTy>::iterator_category,
207 typename std::remove_reference<FuncReturnTy>::type> {
208public:
209 mapped_iterator(ItTy U, FuncTy F)
210 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
211
212 ItTy getCurrent() { return this->I; }
213
214 FuncReturnTy operator*() { return F(*this->I); }
215
216private:
217 FuncTy F;
218};
219
220// map_iterator - Provide a convenient way to create mapped_iterators, just like
221// make_pair is useful for creating pairs...
222template <class ItTy, class FuncTy>
223inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
224 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
225}
226
227/// Helper to determine if type T has a member called rbegin().
228template <typename Ty> class has_rbegin_impl {
229 using yes = char[1];
230 using no = char[2];
231
232 template <typename Inner>
233 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
234
235 template <typename>
236 static no& test(...);
237
238public:
239 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
240};
241
242/// Metafunction to determine if T& or T has a member called rbegin().
243template <typename Ty>
244struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
245};
246
247// Returns an iterator_range over the given container which iterates in reverse.
248// Note that the container must have rbegin()/rend() methods for this to work.
249template <typename ContainerTy>
250auto reverse(ContainerTy &&C,
251 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
252 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
253 return make_range(C.rbegin(), C.rend());
254}
255
256// Returns a std::reverse_iterator wrapped around the given iterator.
257template <typename IteratorTy>
258std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
259 return std::reverse_iterator<IteratorTy>(It);
260}
261
262// Returns an iterator_range over the given container which iterates in reverse.
263// Note that the container must have begin()/end() methods which return
264// bidirectional iterators for this to work.
265template <typename ContainerTy>
266auto reverse(
267 ContainerTy &&C,
268 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
269 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
270 llvm::make_reverse_iterator(std::begin(C)))) {
271 return make_range(llvm::make_reverse_iterator(std::end(C)),
272 llvm::make_reverse_iterator(std::begin(C)));
273}
274
275/// An iterator adaptor that filters the elements of given inner iterators.
276///
277/// The predicate parameter should be a callable object that accepts the wrapped
278/// iterator's reference type and returns a bool. When incrementing or
279/// decrementing the iterator, it will call the predicate on each element and
280/// skip any where it returns false.
281///
282/// \code
283/// int A[] = { 1, 2, 3, 4 };
284/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
285/// // R contains { 1, 3 }.
286/// \endcode
287///
288/// Note: filter_iterator_base implements support for forward iteration.
289/// filter_iterator_impl exists to provide support for bidirectional iteration,
290/// conditional on whether the wrapped iterator supports it.
291template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
292class filter_iterator_base
293 : public iterator_adaptor_base<
294 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
295 WrappedIteratorT,
296 typename std::common_type<
297 IterTag, typename std::iterator_traits<
298 WrappedIteratorT>::iterator_category>::type> {
299 using BaseT = iterator_adaptor_base<
300 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
301 WrappedIteratorT,
302 typename std::common_type<
303 IterTag, typename std::iterator_traits<
304 WrappedIteratorT>::iterator_category>::type>;
305
306protected:
307 WrappedIteratorT End;
308 PredicateT Pred;
309
310 void findNextValid() {
311 while (this->I != End && !Pred(*this->I))
312 BaseT::operator++();
313 }
314
315 // Construct the iterator. The begin iterator needs to know where the end
316 // is, so that it can properly stop when it gets there. The end iterator only
317 // needs the predicate to support bidirectional iteration.
318 filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
319 PredicateT Pred)
320 : BaseT(Begin), End(End), Pred(Pred) {
321 findNextValid();
322 }
323
324public:
325 using BaseT::operator++;
326
327 filter_iterator_base &operator++() {
328 BaseT::operator++();
329 findNextValid();
330 return *this;
331 }
332};
333
334/// Specialization of filter_iterator_base for forward iteration only.
335template <typename WrappedIteratorT, typename PredicateT,
336 typename IterTag = std::forward_iterator_tag>
337class filter_iterator_impl
338 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
339 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
340
341public:
342 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
343 PredicateT Pred)
344 : BaseT(Begin, End, Pred) {}
345};
346
347/// Specialization of filter_iterator_base for bidirectional iteration.
348template <typename WrappedIteratorT, typename PredicateT>
349class filter_iterator_impl<WrappedIteratorT, PredicateT,
350 std::bidirectional_iterator_tag>
351 : public filter_iterator_base<WrappedIteratorT, PredicateT,
352 std::bidirectional_iterator_tag> {
353 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
354 std::bidirectional_iterator_tag>;
355 void findPrevValid() {
356 while (!this->Pred(*this->I))
357 BaseT::operator--();
358 }
359
360public:
361 using BaseT::operator--;
362
363 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
364 PredicateT Pred)
365 : BaseT(Begin, End, Pred) {}
366
367 filter_iterator_impl &operator--() {
368 BaseT::operator--();
369 findPrevValid();
370 return *this;
371 }
372};
373
374namespace detail {
375
376template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
377 using type = std::forward_iterator_tag;
378};
379
380template <> struct fwd_or_bidi_tag_impl<true> {
381 using type = std::bidirectional_iterator_tag;
382};
383
384/// Helper which sets its type member to forward_iterator_tag if the category
385/// of \p IterT does not derive from bidirectional_iterator_tag, and to
386/// bidirectional_iterator_tag otherwise.
387template <typename IterT> struct fwd_or_bidi_tag {
388 using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
389 std::bidirectional_iterator_tag,
390 typename std::iterator_traits<IterT>::iterator_category>::value>::type;
391};
392
393} // namespace detail
394
395/// Defines filter_iterator to a suitable specialization of
396/// filter_iterator_impl, based on the underlying iterator's category.
397template <typename WrappedIteratorT, typename PredicateT>
398using filter_iterator = filter_iterator_impl<
399 WrappedIteratorT, PredicateT,
400 typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
401
402/// Convenience function that takes a range of elements and a predicate,
403/// and return a new filter_iterator range.
404///
405/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
406/// lifetime of that temporary is not kept by the returned range object, and the
407/// temporary is going to be dropped on the floor after the make_iterator_range
408/// full expression that contains this function call.
409template <typename RangeT, typename PredicateT>
410iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
411make_filter_range(RangeT &&Range, PredicateT Pred) {
412 using FilterIteratorT =
413 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
414 return make_range(
415 FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
416 std::end(std::forward<RangeT>(Range)), Pred),
417 FilterIteratorT(std::end(std::forward<RangeT>(Range)),
418 std::end(std::forward<RangeT>(Range)), Pred));
419}
420
421// forward declarations required by zip_shortest/zip_first
422template <typename R, typename UnaryPredicate>
423bool all_of(R &&range, UnaryPredicate P);
424
425template <size_t... I> struct index_sequence;
426
427template <class... Ts> struct index_sequence_for;
428
429namespace detail {
430
431using std::declval;
432
433// We have to alias this since inlining the actual type at the usage site
434// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
435template<typename... Iters> struct ZipTupleType {
436 using type = std::tuple<decltype(*declval<Iters>())...>;
437};
438
439template <typename ZipType, typename... Iters>
440using zip_traits = iterator_facade_base<
441 ZipType, typename std::common_type<std::bidirectional_iterator_tag,
442 typename std::iterator_traits<
443 Iters>::iterator_category...>::type,
444 // ^ TODO: Implement random access methods.
445 typename ZipTupleType<Iters...>::type,
446 typename std::iterator_traits<typename std::tuple_element<
447 0, std::tuple<Iters...>>::type>::difference_type,
448 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
449 // inner iterators have the same difference_type. It would fail if, for
450 // instance, the second field's difference_type were non-numeric while the
451 // first is.
452 typename ZipTupleType<Iters...>::type *,
453 typename ZipTupleType<Iters...>::type>;
454
455template <typename ZipType, typename... Iters>
456struct zip_common : public zip_traits<ZipType, Iters...> {
457 using Base = zip_traits<ZipType, Iters...>;
458 using value_type = typename Base::value_type;
459
460 std::tuple<Iters...> iterators;
461
462protected:
463 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
464 return value_type(*std::get<Ns>(iterators)...);
465 }
466
467 template <size_t... Ns>
468 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
469 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
470 }
471
472 template <size_t... Ns>
473 decltype(iterators) tup_dec(index_sequence<Ns...>) const {
474 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
475 }
476
477public:
478 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
479
480 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
481
482 const value_type operator*() const {
483 return deref(index_sequence_for<Iters...>{});
484 }
485
486 ZipType &operator++() {
487 iterators = tup_inc(index_sequence_for<Iters...>{});
488 return *reinterpret_cast<ZipType *>(this);
489 }
490
491 ZipType &operator--() {
492 static_assert(Base::IsBidirectional,
493 "All inner iterators must be at least bidirectional.");
494 iterators = tup_dec(index_sequence_for<Iters...>{});
495 return *reinterpret_cast<ZipType *>(this);
496 }
497};
498
499template <typename... Iters>
500struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
501 using Base = zip_common<zip_first<Iters...>, Iters...>;
502
503 bool operator==(const zip_first<Iters...> &other) const {
504 return std::get<0>(this->iterators) == std::get<0>(other.iterators);
505 }
506
507 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
508};
509
510template <typename... Iters>
511class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
512 template <size_t... Ns>
513 bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
514 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
515 std::get<Ns>(other.iterators)...},
516 identity<bool>{});
517 }
518
519public:
520 using Base = zip_common<zip_shortest<Iters...>, Iters...>;
521
522 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
523
524 bool operator==(const zip_shortest<Iters...> &other) const {
525 return !test(other, index_sequence_for<Iters...>{});
526 }
527};
528
529template <template <typename...> class ItType, typename... Args> class zippy {
530public:
531 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
532 using iterator_category = typename iterator::iterator_category;
533 using value_type = typename iterator::value_type;
534 using difference_type = typename iterator::difference_type;
535 using pointer = typename iterator::pointer;
536 using reference = typename iterator::reference;
537
538private:
539 std::tuple<Args...> ts;
540
541 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
542 return iterator(std::begin(std::get<Ns>(ts))...);
543 }
544 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
545 return iterator(std::end(std::get<Ns>(ts))...);
546 }
547
548public:
549 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
550
551 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
552 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
553};
554
555} // end namespace detail
556
557/// zip iterator for two or more iteratable types.
558template <typename T, typename U, typename... Args>
559detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
560 Args &&... args) {
561 return detail::zippy<detail::zip_shortest, T, U, Args...>(
562 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
563}
564
565/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
566/// be the shortest.
567template <typename T, typename U, typename... Args>
568detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
569 Args &&... args) {
570 return detail::zippy<detail::zip_first, T, U, Args...>(
571 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
572}
573
574/// Iterator wrapper that concatenates sequences together.
575///
576/// This can concatenate different iterators, even with different types, into
577/// a single iterator provided the value types of all the concatenated
578/// iterators expose `reference` and `pointer` types that can be converted to
579/// `ValueT &` and `ValueT *` respectively. It doesn't support more
580/// interesting/customized pointer or reference types.
581///
582/// Currently this only supports forward or higher iterator categories as
583/// inputs and always exposes a forward iterator interface.
584template <typename ValueT, typename... IterTs>
585class concat_iterator
586 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
587 std::forward_iterator_tag, ValueT> {
588 using BaseT = typename concat_iterator::iterator_facade_base;
589
590 /// We store both the current and end iterators for each concatenated
591 /// sequence in a tuple of pairs.
592 ///
593 /// Note that something like iterator_range seems nice at first here, but the
594 /// range properties are of little benefit and end up getting in the way
595 /// because we need to do mutation on the current iterators.
596 std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
597
598 /// Attempts to increment a specific iterator.
599 ///
600 /// Returns true if it was able to increment the iterator. Returns false if
601 /// the iterator is already at the end iterator.
602 template <size_t Index> bool incrementHelper() {
603 auto &IterPair = std::get<Index>(IterPairs);
604 if (IterPair.first == IterPair.second)
605 return false;
606
607 ++IterPair.first;
608 return true;
609 }
610
611 /// Increments the first non-end iterator.
612 ///
613 /// It is an error to call this with all iterators at the end.
614 template <size_t... Ns> void increment(index_sequence<Ns...>) {
615 // Build a sequence of functions to increment each iterator if possible.
616 bool (concat_iterator::*IncrementHelperFns[])() = {
617 &concat_iterator::incrementHelper<Ns>...};
618
619 // Loop over them, and stop as soon as we succeed at incrementing one.
620 for (auto &IncrementHelperFn : IncrementHelperFns)
621 if ((this->*IncrementHelperFn)())
622 return;
623
624 llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/ADT/STLExtras.h"
, 624)
;
625 }
626
627 /// Returns null if the specified iterator is at the end. Otherwise,
628 /// dereferences the iterator and returns the address of the resulting
629 /// reference.
630 template <size_t Index> ValueT *getHelper() const {
631 auto &IterPair = std::get<Index>(IterPairs);
632 if (IterPair.first == IterPair.second)
633 return nullptr;
634
635 return &*IterPair.first;
636 }
637
638 /// Finds the first non-end iterator, dereferences, and returns the resulting
639 /// reference.
640 ///
641 /// It is an error to call this with all iterators at the end.
642 template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
643 // Build a sequence of functions to get from iterator if possible.
644 ValueT *(concat_iterator::*GetHelperFns[])() const = {
645 &concat_iterator::getHelper<Ns>...};
646
647 // Loop over them, and return the first result we find.
648 for (auto &GetHelperFn : GetHelperFns)
649 if (ValueT *P = (this->*GetHelperFn)())
650 return *P;
651
652 llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!"
, "/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/ADT/STLExtras.h"
, 652)
;
653 }
654
655public:
656 /// Constructs an iterator from a squence of ranges.
657 ///
658 /// We need the full range to know how to switch between each of the
659 /// iterators.
660 template <typename... RangeTs>
661 explicit concat_iterator(RangeTs &&... Ranges)
662 : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
663
664 using BaseT::operator++;
665
666 concat_iterator &operator++() {
667 increment(index_sequence_for<IterTs...>());
668 return *this;
669 }
670
671 ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
672
673 bool operator==(const concat_iterator &RHS) const {
674 return IterPairs == RHS.IterPairs;
675 }
676};
677
678namespace detail {
679
680/// Helper to store a sequence of ranges being concatenated and access them.
681///
682/// This is designed to facilitate providing actual storage when temporaries
683/// are passed into the constructor such that we can use it as part of range
684/// based for loops.
685template <typename ValueT, typename... RangeTs> class concat_range {
686public:
687 using iterator =
688 concat_iterator<ValueT,
689 decltype(std::begin(std::declval<RangeTs &>()))...>;
690
691private:
692 std::tuple<RangeTs...> Ranges;
693
694 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
695 return iterator(std::get<Ns>(Ranges)...);
696 }
697 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
698 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
699 std::end(std::get<Ns>(Ranges)))...);
700 }
701
702public:
703 concat_range(RangeTs &&... Ranges)
704 : Ranges(std::forward<RangeTs>(Ranges)...) {}
705
706 iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
707 iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
708};
709
710} // end namespace detail
711
712/// Concatenated range across two or more ranges.
713///
714/// The desired value type must be explicitly specified.
715template <typename ValueT, typename... RangeTs>
716detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
717 static_assert(sizeof...(RangeTs) > 1,
718 "Need more than one range to concatenate!");
719 return detail::concat_range<ValueT, RangeTs...>(
720 std::forward<RangeTs>(Ranges)...);
721}
722
723//===----------------------------------------------------------------------===//
724// Extra additions to <utility>
725//===----------------------------------------------------------------------===//
726
727/// Function object to check whether the first component of a std::pair
728/// compares less than the first component of another std::pair.
729struct less_first {
730 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
731 return lhs.first < rhs.first;
732 }
733};
734
735/// Function object to check whether the second component of a std::pair
736/// compares less than the second component of another std::pair.
737struct less_second {
738 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
739 return lhs.second < rhs.second;
740 }
741};
742
743// A subset of N3658. More stuff can be added as-needed.
744
745/// Represents a compile-time sequence of integers.
746template <class T, T... I> struct integer_sequence {
747 using value_type = T;
748
749 static constexpr size_t size() { return sizeof...(I); }
750};
751
752/// Alias for the common case of a sequence of size_ts.
753template <size_t... I>
754struct index_sequence : integer_sequence<std::size_t, I...> {};
755
756template <std::size_t N, std::size_t... I>
757struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
758template <std::size_t... I>
759struct build_index_impl<0, I...> : index_sequence<I...> {};
760
761/// Creates a compile-time integer sequence for a parameter pack.
762template <class... Ts>
763struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
764
765/// Utility type to build an inheritance chain that makes it easy to rank
766/// overload candidates.
767template <int N> struct rank : rank<N - 1> {};
768template <> struct rank<0> {};
769
770/// traits class for checking whether type T is one of any of the given
771/// types in the variadic list.
772template <typename T, typename... Ts> struct is_one_of {
773 static const bool value = false;
774};
775
776template <typename T, typename U, typename... Ts>
777struct is_one_of<T, U, Ts...> {
778 static const bool value =
779 std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
780};
781
782/// traits class for checking whether type T is a base class for all
783/// the given types in the variadic list.
784template <typename T, typename... Ts> struct are_base_of {
785 static const bool value = true;
786};
787
788template <typename T, typename U, typename... Ts>
789struct are_base_of<T, U, Ts...> {
790 static const bool value =
791 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
792};
793
794//===----------------------------------------------------------------------===//
795// Extra additions for arrays
796//===----------------------------------------------------------------------===//
797
798/// Find the length of an array.
799template <class T, std::size_t N>
800constexpr inline size_t array_lengthof(T (&)[N]) {
801 return N;
802}
803
804/// Adapt std::less<T> for array_pod_sort.
805template<typename T>
806inline int array_pod_sort_comparator(const void *P1, const void *P2) {
807 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
808 *reinterpret_cast<const T*>(P2)))
809 return -1;
810 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
811 *reinterpret_cast<const T*>(P1)))
812 return 1;
813 return 0;
814}
815
816/// get_array_pod_sort_comparator - This is an internal helper function used to
817/// get type deduction of T right.
818template<typename T>
819inline int (*get_array_pod_sort_comparator(const T &))
820 (const void*, const void*) {
821 return array_pod_sort_comparator<T>;
822}
823
824/// array_pod_sort - This sorts an array with the specified start and end
825/// extent. This is just like std::sort, except that it calls qsort instead of
826/// using an inlined template. qsort is slightly slower than std::sort, but
827/// most sorts are not performance critical in LLVM and std::sort has to be
828/// template instantiated for each type, leading to significant measured code
829/// bloat. This function should generally be used instead of std::sort where
830/// possible.
831///
832/// This function assumes that you have simple POD-like types that can be
833/// compared with std::less and can be moved with memcpy. If this isn't true,
834/// you should use std::sort.
835///
836/// NOTE: If qsort_r were portable, we could allow a custom comparator and
837/// default to std::less.
838template<class IteratorTy>
839inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
840 // Don't inefficiently call qsort with one element or trigger undefined
841 // behavior with an empty sequence.
842 auto NElts = End - Start;
843 if (NElts <= 1) return;
844#ifdef EXPENSIVE_CHECKS
845 std::mt19937 Generator(std::random_device{}());
846 std::shuffle(Start, End, Generator);
847#endif
848 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
849}
850
851template <class IteratorTy>
852inline void array_pod_sort(
853 IteratorTy Start, IteratorTy End,
854 int (*Compare)(
855 const typename std::iterator_traits<IteratorTy>::value_type *,
856 const typename std::iterator_traits<IteratorTy>::value_type *)) {
857 // Don't inefficiently call qsort with one element or trigger undefined
858 // behavior with an empty sequence.
859 auto NElts = End - Start;
860 if (NElts <= 1) return;
861#ifdef EXPENSIVE_CHECKS
862 std::mt19937 Generator(std::random_device{}());
863 std::shuffle(Start, End, Generator);
864#endif
865 qsort(&*Start, NElts, sizeof(*Start),
866 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
867}
868
869// Provide wrappers to std::sort which shuffle the elements before sorting
870// to help uncover non-deterministic behavior (PR35135).
871template <typename IteratorTy>
872inline void sort(IteratorTy Start, IteratorTy End) {
873#ifdef EXPENSIVE_CHECKS
874 std::mt19937 Generator(std::random_device{}());
875 std::shuffle(Start, End, Generator);
876#endif
877 std::sort(Start, End);
878}
879
880template <typename IteratorTy, typename Compare>
881inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
882#ifdef EXPENSIVE_CHECKS
883 std::mt19937 Generator(std::random_device{}());
884 std::shuffle(Start, End, Generator);
885#endif
886 std::sort(Start, End, Comp);
887}
888
889//===----------------------------------------------------------------------===//
890// Extra additions to <algorithm>
891//===----------------------------------------------------------------------===//
892
893/// For a container of pointers, deletes the pointers and then clears the
894/// container.
895template<typename Container>
896void DeleteContainerPointers(Container &C) {
897 for (auto V : C)
898 delete V;
899 C.clear();
900}
901
902/// In a container of pairs (usually a map) whose second element is a pointer,
903/// deletes the second elements and then clears the container.
904template<typename Container>
905void DeleteContainerSeconds(Container &C) {
906 for (auto &V : C)
907 delete V.second;
908 C.clear();
909}
910
911/// Provide wrappers to std::for_each which take ranges instead of having to
912/// pass begin/end explicitly.
913template <typename R, typename UnaryPredicate>
914UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
915 return std::for_each(adl_begin(Range), adl_end(Range), P);
916}
917
918/// Provide wrappers to std::all_of which take ranges instead of having to pass
919/// begin/end explicitly.
920template <typename R, typename UnaryPredicate>
921bool all_of(R &&Range, UnaryPredicate P) {
922 return std::all_of(adl_begin(Range), adl_end(Range), P);
923}
924
925/// Provide wrappers to std::any_of which take ranges instead of having to pass
926/// begin/end explicitly.
927template <typename R, typename UnaryPredicate>
928bool any_of(R &&Range, UnaryPredicate P) {
929 return std::any_of(adl_begin(Range), adl_end(Range), P);
930}
931
932/// Provide wrappers to std::none_of which take ranges instead of having to pass
933/// begin/end explicitly.
934template <typename R, typename UnaryPredicate>
935bool none_of(R &&Range, UnaryPredicate P) {
936 return std::none_of(adl_begin(Range), adl_end(Range), P);
937}
938
939/// Provide wrappers to std::find which take ranges instead of having to pass
940/// begin/end explicitly.
941template <typename R, typename T>
942auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
943 return std::find(adl_begin(Range), adl_end(Range), Val);
944}
945
946/// Provide wrappers to std::find_if which take ranges instead of having to pass
947/// begin/end explicitly.
948template <typename R, typename UnaryPredicate>
949auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
950 return std::find_if(adl_begin(Range), adl_end(Range), P);
951}
952
953template <typename R, typename UnaryPredicate>
954auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
955 return std::find_if_not(adl_begin(Range), adl_end(Range), P);
956}
957
958/// Provide wrappers to std::remove_if which take ranges instead of having to
959/// pass begin/end explicitly.
960template <typename R, typename UnaryPredicate>
961auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
962 return std::remove_if(adl_begin(Range), adl_end(Range), P);
963}
964
965/// Provide wrappers to std::copy_if which take ranges instead of having to
966/// pass begin/end explicitly.
967template <typename R, typename OutputIt, typename UnaryPredicate>
968OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
969 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
970}
971
972template <typename R, typename OutputIt>
973OutputIt copy(R &&Range, OutputIt Out) {
974 return std::copy(adl_begin(Range), adl_end(Range), Out);
975}
976
977/// Wrapper function around std::find to detect if an element exists
978/// in a container.
979template <typename R, typename E>
980bool is_contained(R &&Range, const E &Element) {
981 return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
982}
983
984/// Wrapper function around std::count to count the number of times an element
985/// \p Element occurs in the given range \p Range.
986template <typename R, typename E>
987auto count(R &&Range, const E &Element) ->
988 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
989 return std::count(adl_begin(Range), adl_end(Range), Element);
990}
991
992/// Wrapper function around std::count_if to count the number of times an
993/// element satisfying a given predicate occurs in a range.
994template <typename R, typename UnaryPredicate>
995auto count_if(R &&Range, UnaryPredicate P) ->
996 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
997 return std::count_if(adl_begin(Range), adl_end(Range), P);
998}
999
1000/// Wrapper function around std::transform to apply a function to a range and
1001/// store the result elsewhere.
1002template <typename R, typename OutputIt, typename UnaryPredicate>
1003OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1004 return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1005}
1006
1007/// Provide wrappers to std::partition which take ranges instead of having to
1008/// pass begin/end explicitly.
1009template <typename R, typename UnaryPredicate>
1010auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1011 return std::partition(adl_begin(Range), adl_end(Range), P);
1012}
1013
1014/// Provide wrappers to std::lower_bound which take ranges instead of having to
1015/// pass begin/end explicitly.
1016template <typename R, typename ForwardIt>
1017auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1018 return std::lower_bound(adl_begin(Range), adl_end(Range), I);
1019}
1020
1021/// Given a range of type R, iterate the entire range and return a
1022/// SmallVector with elements of the vector. This is useful, for example,
1023/// when you want to iterate a range and then sort the results.
1024template <unsigned Size, typename R>
1025SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
1026to_vector(R &&Range) {
1027 return {adl_begin(Range), adl_end(Range)};
1028}
1029
1030/// Provide a container algorithm similar to C++ Library Fundamentals v2's
1031/// `erase_if` which is equivalent to:
1032///
1033/// C.erase(remove_if(C, pred), C.end());
1034///
1035/// This version works for any container with an erase method call accepting
1036/// two iterators.
1037template <typename Container, typename UnaryPredicate>
1038void erase_if(Container &C, UnaryPredicate P) {
1039 C.erase(remove_if(C, P), C.end());
1040}
1041
1042/// Get the size of a range. This is a wrapper function around std::distance
1043/// which is only enabled when the operation is O(1).
1044template <typename R>
1045auto size(R &&Range, typename std::enable_if<
1046 std::is_same<typename std::iterator_traits<decltype(
1047 Range.begin())>::iterator_category,
1048 std::random_access_iterator_tag>::value,
1049 void>::type * = nullptr)
1050 -> decltype(std::distance(Range.begin(), Range.end())) {
1051 return std::distance(Range.begin(), Range.end());
1052}
1053
1054//===----------------------------------------------------------------------===//
1055// Extra additions to <memory>
1056//===----------------------------------------------------------------------===//
1057
1058// Implement make_unique according to N3656.
1059
1060/// Constructs a `new T()` with the given args and returns a
1061/// `unique_ptr<T>` which owns the object.
1062///
1063/// Example:
1064///
1065/// auto p = make_unique<int>();
1066/// auto p = make_unique<std::tuple<int, int>>(0, 1);
1067template <class T, class... Args>
1068typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1069make_unique(Args &&... args) {
1070 return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
9
Calling default constructor for 'ExplodedGraph'
1071}
1072
1073/// Constructs a `new T[n]` with the given args and returns a
1074/// `unique_ptr<T[]>` which owns the object.
1075///
1076/// \param n size of the new array.
1077///
1078/// Example:
1079///
1080/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
1081template <class T>
1082typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1083 std::unique_ptr<T>>::type
1084make_unique(size_t n) {
1085 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
1086}
1087
1088/// This function isn't used and is only here to provide better compile errors.
1089template <class T, class... Args>
1090typename std::enable_if<std::extent<T>::value != 0>::type
1091make_unique(Args &&...) = delete;
1092
1093struct FreeDeleter {
1094 void operator()(void* v) {
1095 ::free(v);
1096 }
1097};
1098
1099template<typename First, typename Second>
1100struct pair_hash {
1101 size_t operator()(const std::pair<First, Second> &P) const {
1102 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1103 }
1104};
1105
1106/// A functor like C++14's std::less<void> in its absence.
1107struct less {
1108 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1109 return std::forward<A>(a) < std::forward<B>(b);
1110 }
1111};
1112
1113/// A functor like C++14's std::equal<void> in its absence.
1114struct equal {
1115 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1116 return std::forward<A>(a) == std::forward<B>(b);
1117 }
1118};
1119
1120/// Binary functor that adapts to any other binary functor after dereferencing
1121/// operands.
1122template <typename T> struct deref {
1123 T func;
1124
1125 // Could be further improved to cope with non-derivable functors and
1126 // non-binary functors (should be a variadic template member function
1127 // operator()).
1128 template <typename A, typename B>
1129 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1130 assert(lhs)(static_cast <bool> (lhs) ? void (0) : __assert_fail ("lhs"
, "/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/ADT/STLExtras.h"
, 1130, __extension__ __PRETTY_FUNCTION__))
;
1131 assert(rhs)(static_cast <bool> (rhs) ? void (0) : __assert_fail ("rhs"
, "/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/ADT/STLExtras.h"
, 1131, __extension__ __PRETTY_FUNCTION__))
;
1132 return func(*lhs, *rhs);
1133 }
1134};
1135
1136namespace detail {
1137
1138template <typename R> class enumerator_iter;
1139
1140template <typename R> struct result_pair {
1141 friend class enumerator_iter<R>;
1142
1143 result_pair() = default;
1144 result_pair(std::size_t Index, IterOfRange<R> Iter)
1145 : Index(Index), Iter(Iter) {}
1146
1147 result_pair<R> &operator=(const result_pair<R> &Other) {
1148 Index = Other.Index;
1149 Iter = Other.Iter;
1150 return *this;
1151 }
1152
1153 std::size_t index() const { return Index; }
1154 const ValueOfRange<R> &value() const { return *Iter; }
1155 ValueOfRange<R> &value() { return *Iter; }
1156
1157private:
1158 std::size_t Index = std::numeric_limits<std::size_t>::max();
1159 IterOfRange<R> Iter;
1160};
1161
1162template <typename R>
1163class enumerator_iter
1164 : public iterator_facade_base<
1165 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1166 typename std::iterator_traits<IterOfRange<R>>::difference_type,
1167 typename std::iterator_traits<IterOfRange<R>>::pointer,
1168 typename std::iterator_traits<IterOfRange<R>>::reference> {
1169 using result_type = result_pair<R>;
1170
1171public:
1172 explicit enumerator_iter(IterOfRange<R> EndIter)
1173 : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1174
1175 enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1176 : Result(Index, Iter) {}
1177
1178 result_type &operator*() { return Result; }
1179 const result_type &operator*() const { return Result; }
1180
1181 enumerator_iter<R> &operator++() {
1182 assert(Result.Index != std::numeric_limits<size_t>::max())(static_cast <bool> (Result.Index != std::numeric_limits
<size_t>::max()) ? void (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()"
, "/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/ADT/STLExtras.h"
, 1182, __extension__ __PRETTY_FUNCTION__))
;
1183 ++Result.Iter;
1184 ++Result.Index;
1185 return *this;
1186 }
1187
1188 bool operator==(const enumerator_iter<R> &RHS) const {
1189 // Don't compare indices here, only iterators. It's possible for an end
1190 // iterator to have different indices depending on whether it was created
1191 // by calling std::end() versus incrementing a valid iterator.
1192 return Result.Iter == RHS.Result.Iter;
1193 }
1194
1195 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1196 Result = Other.Result;
1197 return *this;
1198 }
1199
1200private:
1201 result_type Result;
1202};
1203
1204template <typename R> class enumerator {
1205public:
1206 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1207
1208 enumerator_iter<R> begin() {
1209 return enumerator_iter<R>(0, std::begin(TheRange));
1210 }
1211
1212 enumerator_iter<R> end() {
1213 return enumerator_iter<R>(std::end(TheRange));
1214 }
1215
1216private:
1217 R TheRange;
1218};
1219
1220} // end namespace detail
1221
1222/// Given an input range, returns a new range whose values are are pair (A,B)
1223/// such that A is the 0-based index of the item in the sequence, and B is
1224/// the value from the original sequence. Example:
1225///
1226/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1227/// for (auto X : enumerate(Items)) {
1228/// printf("Item %d - %c\n", X.index(), X.value());
1229/// }
1230///
1231/// Output:
1232/// Item 0 - A
1233/// Item 1 - B
1234/// Item 2 - C
1235/// Item 3 - D
1236///
1237template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1238 return detail::enumerator<R>(std::forward<R>(TheRange));
1239}
1240
1241namespace detail {
1242
1243template <typename F, typename Tuple, std::size_t... I>
1244auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1245 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1246 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1247}
1248
1249} // end namespace detail
1250
1251/// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1252/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1253/// return the result.
1254template <typename F, typename Tuple>
1255auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1256 std::forward<F>(f), std::forward<Tuple>(t),
1257 build_index_impl<
1258 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1259 using Indices = build_index_impl<
1260 std::tuple_size<typename std::decay<Tuple>::type>::value>;
1261
1262 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1263 Indices{});
1264}
1265
1266} // end namespace llvm
1267
1268#endif // LLVM_ADT_STLEXTRAS_H

/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/Analysis/Support/BumpVector.h

1//===- BumpVector.h - Vector-like ADT that uses bump allocation -*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file provides BumpVector, a vector-like ADT whose contents are
11// allocated from a BumpPtrAllocator.
12//
13//===----------------------------------------------------------------------===//
14
15// FIXME: Most of this is copy-and-paste from SmallVector.h. We can
16// refactor this core logic into something common that is shared between
17// the two. The main thing that is different is the allocation strategy.
18
19#ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
20#define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
21
22#include "llvm/ADT/PointerIntPair.h"
23#include "llvm/Support/Allocator.h"
24#include <cassert>
25#include <cstddef>
26#include <cstring>
27#include <iterator>
28#include <memory>
29#include <type_traits>
30
31namespace clang {
32
33class BumpVectorContext {
34 llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
35
36public:
37 /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator
38 /// and destroys it when the BumpVectorContext object is destroyed.
39 BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {}
11
Memory is allocated
12
Potential memory leak
40
41 BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) {
42 Other.Alloc.setInt(false);
43 Other.Alloc.setPointer(nullptr);
44 }
45
46 /// Construct a new BumpVectorContext that reuses an existing
47 /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the
48 /// BumpVectorContext object is destroyed.
49 BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {}
50
51 ~BumpVectorContext() {
52 if (Alloc.getInt())
53 delete Alloc.getPointer();
54 }
55
56 llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
57};
58
59template<typename T>
60class BumpVector {
61 T *Begin = nullptr;
62 T *End = nullptr;
63 T *Capacity = nullptr;
64
65public:
66 // Default ctor - Initialize to empty.
67 explicit BumpVector(BumpVectorContext &C, unsigned N) {
68 reserve(C, N);
69 }
70
71 ~BumpVector() {
72 if (std::is_class<T>::value) {
73 // Destroy the constructed elements in the vector.
74 destroy_range(Begin, End);
75 }
76 }
77
78 using size_type = size_t;
79 using difference_type = ptrdiff_t;
80 using value_type = T;
81 using iterator = T *;
82 using const_iterator = const T *;
83
84 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
85 using reverse_iterator = std::reverse_iterator<iterator>;
86
87 using reference = T &;
88 using const_reference = const T &;
89 using pointer = T *;
90 using const_pointer = const T *;
91
92 // forward iterator creation methods.
93 iterator begin() { return Begin; }
94 const_iterator begin() const { return Begin; }
95 iterator end() { return End; }
96 const_iterator end() const { return End; }
97
98 // reverse iterator creation methods.
99 reverse_iterator rbegin() { return reverse_iterator(end()); }
100 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
101 reverse_iterator rend() { return reverse_iterator(begin()); }
102 const_reverse_iterator rend() const {
103 return const_reverse_iterator(begin());
104 }
105
106 bool empty() const { return Begin == End; }
107 size_type size() const { return End-Begin; }
108
109 reference operator[](unsigned idx) {
110 assert(Begin + idx < End)(static_cast <bool> (Begin + idx < End) ? void (0) :
__assert_fail ("Begin + idx < End", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/Analysis/Support/BumpVector.h"
, 110, __extension__ __PRETTY_FUNCTION__))
;
111 return Begin[idx];
112 }
113 const_reference operator[](unsigned idx) const {
114 assert(Begin + idx < End)(static_cast <bool> (Begin + idx < End) ? void (0) :
__assert_fail ("Begin + idx < End", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/Analysis/Support/BumpVector.h"
, 114, __extension__ __PRETTY_FUNCTION__))
;
115 return Begin[idx];
116 }
117
118 reference front() {
119 return begin()[0];
120 }
121 const_reference front() const {
122 return begin()[0];
123 }
124
125 reference back() {
126 return end()[-1];
127 }
128 const_reference back() const {
129 return end()[-1];
130 }
131
132 void pop_back() {
133 --End;
134 End->~T();
135 }
136
137 T pop_back_val() {
138 T Result = back();
139 pop_back();
140 return Result;
141 }
142
143 void clear() {
144 if (std::is_class<T>::value) {
145 destroy_range(Begin, End);
146 }
147 End = Begin;
148 }
149
150 /// data - Return a pointer to the vector's buffer, even if empty().
151 pointer data() {
152 return pointer(Begin);
153 }
154
155 /// data - Return a pointer to the vector's buffer, even if empty().
156 const_pointer data() const {
157 return const_pointer(Begin);
158 }
159
160 void push_back(const_reference Elt, BumpVectorContext &C) {
161 if (End < Capacity) {
162 Retry:
163 new (End) T(Elt);
164 ++End;
165 return;
166 }
167 grow(C);
168 goto Retry;
169 }
170
171 /// insert - Insert some number of copies of element into a position. Return
172 /// iterator to position after last inserted copy.
173 iterator insert(iterator I, size_t Cnt, const_reference E,
174 BumpVectorContext &C) {
175 assert(I >= Begin && I <= End && "Iterator out of bounds.")(static_cast <bool> (I >= Begin && I <= End
&& "Iterator out of bounds.") ? void (0) : __assert_fail
("I >= Begin && I <= End && \"Iterator out of bounds.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include/clang/Analysis/Support/BumpVector.h"
, 175, __extension__ __PRETTY_FUNCTION__))
;
176 if (End + Cnt <= Capacity) {
177 Retry:
178 move_range_right(I, End, Cnt);
179 construct_range(I, I + Cnt, E);
180 End += Cnt;
181 return I + Cnt;
182 }
183 ptrdiff_t D = I - Begin;
184 grow(C, size() + Cnt);
185 I = Begin + D;
186 goto Retry;
187 }
188
189 void reserve(BumpVectorContext &C, unsigned N) {
190 if (unsigned(Capacity-Begin) < N)
191 grow(C, N);
192 }
193
194 /// capacity - Return the total number of elements in the currently allocated
195 /// buffer.
196 size_t capacity() const { return Capacity - Begin; }
197
198private:
199 /// grow - double the size of the allocated memory, guaranteeing space for at
200 /// least one more element or MinSize if specified.
201 void grow(BumpVectorContext &C, size_type MinSize = 1);
202
203 void construct_range(T *S, T *E, const T &Elt) {
204 for (; S != E; ++S)
205 new (S) T(Elt);
206 }
207
208 void destroy_range(T *S, T *E) {
209 while (S != E) {
210 --E;
211 E->~T();
212 }
213 }
214
215 void move_range_right(T *S, T *E, size_t D) {
216 for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) {
217 --E;
218 new (I) T(*E);
219 E->~T();
220 }
221 }
222};
223
224// Define this out-of-line to dissuade the C++ compiler from inlining it.
225template <typename T>
226void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) {
227 size_t CurCapacity = Capacity-Begin;
228 size_t CurSize = size();
229 size_t NewCapacity = 2*CurCapacity;
230 if (NewCapacity < MinSize)
231 NewCapacity = MinSize;
232
233 // Allocate the memory from the BumpPtrAllocator.
234 T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity);
235
236 // Copy the elements over.
237 if (Begin != End) {
238 if (std::is_class<T>::value) {
239 std::uninitialized_copy(Begin, End, NewElts);
240 // Destroy the original elements.
241 destroy_range(Begin, End);
242 } else {
243 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
244 memcpy(NewElts, Begin, CurSize * sizeof(T));
245 }
246 }
247
248 // For now, leak 'Begin'. We can add it back to a freelist in
249 // BumpVectorContext.
250 Begin = NewElts;
251 End = NewElts+CurSize;
252 Capacity = Begin+NewCapacity;
253}
254
255} // namespace clang
256
257#endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H