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-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-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/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-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn345461/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-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp -faddrsig

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

/build/llvm-toolchain-snapshot-8~svn345461/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)((getFlag() == Flag) ? static_cast<void> (0) : __assert_fail
("getFlag() == Flag", "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
, 93, __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)((isSink() == IsSink) ? static_cast<void> (0) : __assert_fail
("isSink() == IsSink", "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
, 139, __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 ExplodedNode *getFirstSucc() {
214 return succ_empty() ? nullptr : *(succ_begin());
215 }
216
217 const ExplodedNode *getFirstSucc() const {
218 return const_cast<ExplodedNode*>(this)->getFirstSucc();
219 }
220
221 // Iterators over successor and predecessor vertices.
222 using succ_iterator = ExplodedNode * const *;
223 using const_succ_iterator = const ExplodedNode * const *;
224 using pred_iterator = ExplodedNode * const *;
225 using const_pred_iterator = const ExplodedNode * const *;
226
227 pred_iterator pred_begin() { return Preds.begin(); }
228 pred_iterator pred_end() { return Preds.end(); }
229
230 const_pred_iterator pred_begin() const {
231 return const_cast<ExplodedNode*>(this)->pred_begin();
232 }
233 const_pred_iterator pred_end() const {
234 return const_cast<ExplodedNode*>(this)->pred_end();
235 }
236
237 succ_iterator succ_begin() { return Succs.begin(); }
238 succ_iterator succ_end() { return Succs.end(); }
239
240 const_succ_iterator succ_begin() const {
241 return const_cast<ExplodedNode*>(this)->succ_begin();
242 }
243 const_succ_iterator succ_end() const {
244 return const_cast<ExplodedNode*>(this)->succ_end();
245 }
246
247 int64_t getID(ExplodedGraph *G) const;
248
249 /// The node is trivial if it has only one successor, only one predecessor,
250 /// it's predecessor has only one successor,
251 /// and its program state is the same as the program state of the previous
252 /// node.
253 /// Trivial nodes may be skipped while printing exploded graph.
254 bool isTrivial() const;
255
256private:
257 void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
258 void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
259};
260
261using InterExplodedGraphMap =
262 llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
263
264class ExplodedGraph {
265protected:
266 friend class CoreEngine;
267
268 // Type definitions.
269 using NodeVector = std::vector<ExplodedNode *>;
270
271 /// The roots of the simulation graph. Usually there will be only
272 /// one, but clients are free to establish multiple subgraphs within a single
273 /// SimulGraph. Moreover, these subgraphs can often merge when paths from
274 /// different roots reach the same state at the same program location.
275 NodeVector Roots;
276
277 /// The nodes in the simulation graph which have been
278 /// specially marked as the endpoint of an abstract simulation path.
279 NodeVector EndNodes;
280
281 /// Nodes - The nodes in the graph.
282 llvm::FoldingSet<ExplodedNode> Nodes;
283
284 /// BVC - Allocator and context for allocating nodes and their predecessor
285 /// and successor groups.
286 BumpVectorContext BVC;
287
288 /// NumNodes - The number of nodes in the graph.
289 unsigned NumNodes = 0;
290
291 /// A list of recently allocated nodes that can potentially be recycled.
292 NodeVector ChangedNodes;
293
294 /// A list of nodes that can be reused.
295 NodeVector FreeNodes;
296
297 /// Determines how often nodes are reclaimed.
298 ///
299 /// If this is 0, nodes will never be reclaimed.
300 unsigned ReclaimNodeInterval = 0;
301
302 /// Counter to determine when to reclaim nodes.
303 unsigned ReclaimCounter;
304
305public:
306 ExplodedGraph();
307 ~ExplodedGraph();
308
309 /// Retrieve the node associated with a (Location,State) pair,
310 /// where the 'Location' is a ProgramPoint in the CFG. If no node for
311 /// this pair exists, it is created. IsNew is set to true if
312 /// the node was freshly created.
313 ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
314 bool IsSink = false,
315 bool* IsNew = nullptr);
316
317 /// Create a node for a (Location, State) pair,
318 /// but don't store it for deduplication later. This
319 /// is useful when copying an already completed
320 /// ExplodedGraph for further processing.
321 ExplodedNode *createUncachedNode(const ProgramPoint &L,
322 ProgramStateRef State,
323 bool IsSink = false);
324
325 std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
326 return llvm::make_unique<ExplodedGraph>();
8
Calling 'make_unique<clang::ento::ExplodedGraph, >'
327 }
328
329 /// addRoot - Add an untyped node to the set of roots.
330 ExplodedNode *addRoot(ExplodedNode *V) {
331 Roots.push_back(V);
332 return V;
333 }
334
335 /// addEndOfPath - Add an untyped node to the set of EOP nodes.
336 ExplodedNode *addEndOfPath(ExplodedNode *V) {
337 EndNodes.push_back(V);
338 return V;
339 }
340
341 unsigned num_roots() const { return Roots.size(); }
342 unsigned num_eops() const { return EndNodes.size(); }
343
344 bool empty() const { return NumNodes == 0; }
345 unsigned size() const { return NumNodes; }
346
347 void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
348
349 // Iterators.
350 using NodeTy = ExplodedNode;
351 using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
352 using roots_iterator = NodeVector::iterator;
353 using const_roots_iterator = NodeVector::const_iterator;
354 using eop_iterator = NodeVector::iterator;
355 using const_eop_iterator = NodeVector::const_iterator;
356 using node_iterator = AllNodesTy::iterator;
357 using const_node_iterator = AllNodesTy::const_iterator;
358
359 node_iterator nodes_begin() { return Nodes.begin(); }
360
361 node_iterator nodes_end() { return Nodes.end(); }
362
363 const_node_iterator nodes_begin() const { return Nodes.begin(); }
364
365 const_node_iterator nodes_end() const { return Nodes.end(); }
366
367 roots_iterator roots_begin() { return Roots.begin(); }
368
369 roots_iterator roots_end() { return Roots.end(); }
370
371 const_roots_iterator roots_begin() const { return Roots.begin(); }
372
373 const_roots_iterator roots_end() const { return Roots.end(); }
374
375 eop_iterator eop_begin() { return EndNodes.begin(); }
376
377 eop_iterator eop_end() { return EndNodes.end(); }
378
379 const_eop_iterator eop_begin() const { return EndNodes.begin(); }
380
381 const_eop_iterator eop_end() const { return EndNodes.end(); }
382
383 llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
384 BumpVectorContext &getNodeAllocator() { return BVC; }
385
386 using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
387
388 /// Creates a trimmed version of the graph that only contains paths leading
389 /// to the given nodes.
390 ///
391 /// \param Nodes The nodes which must appear in the final graph. Presumably
392 /// these are end-of-path nodes (i.e. they have no successors).
393 /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
394 /// the returned graph.
395 /// \param[out] InverseMap An optional map from nodes in the returned graph to
396 /// nodes in this graph.
397 /// \returns The trimmed graph
398 std::unique_ptr<ExplodedGraph>
399 trim(ArrayRef<const NodeTy *> Nodes,
400 InterExplodedGraphMap *ForwardMap = nullptr,
401 InterExplodedGraphMap *InverseMap = nullptr) const;
402
403 /// Enable tracking of recently allocated nodes for potential reclamation
404 /// when calling reclaimRecentlyAllocatedNodes().
405 void enableNodeReclamation(unsigned Interval) {
406 ReclaimCounter = ReclaimNodeInterval = Interval;
407 }
408
409 /// Reclaim "uninteresting" nodes created since the last time this method
410 /// was called.
411 void reclaimRecentlyAllocatedNodes();
412
413 /// Returns true if nodes for the given expression kind are always
414 /// kept around.
415 static bool isInterestingLValueExpr(const Expr *Ex);
416
417private:
418 bool shouldCollect(const ExplodedNode *node);
419 void collectNode(ExplodedNode *node);
420};
421
422class ExplodedNodeSet {
423 using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
424 ImplTy Impl;
425
426public:
427 ExplodedNodeSet(ExplodedNode *N) {
428 assert(N && !static_cast<ExplodedNode*>(N)->isSink())((N && !static_cast<ExplodedNode*>(N)->isSink
()) ? static_cast<void> (0) : __assert_fail ("N && !static_cast<ExplodedNode*>(N)->isSink()"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
, 428, __PRETTY_FUNCTION__))
;
429 Impl.insert(N);
430 }
431
432 ExplodedNodeSet() = default;
433
434 void Add(ExplodedNode *N) {
435 if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
436 }
437
438 using iterator = ImplTy::iterator;
439 using const_iterator = ImplTy::const_iterator;
440
441 unsigned size() const { return Impl.size(); }
442 bool empty() const { return Impl.empty(); }
443 bool erase(ExplodedNode *N) { return Impl.remove(N); }
444
445 void clear() { Impl.clear(); }
446
447 void insert(const ExplodedNodeSet &S) {
448 assert(&S != this)((&S != this) ? static_cast<void> (0) : __assert_fail
("&S != this", "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
, 448, __PRETTY_FUNCTION__))
;
449 if (empty())
450 Impl = S.Impl;
451 else
452 Impl.insert(S.begin(), S.end());
453 }
454
455 iterator begin() { return Impl.begin(); }
456 iterator end() { return Impl.end(); }
457
458 const_iterator begin() const { return Impl.begin(); }
459 const_iterator end() const { return Impl.end(); }
460};
461
462} // namespace ento
463
464} // namespace clang
465
466// GraphTraits
467
468namespace llvm {
469 template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
470 using GraphTy = clang::ento::ExplodedGraph *;
471 using NodeRef = clang::ento::ExplodedNode *;
472 using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
473 using nodes_iterator = llvm::df_iterator<GraphTy>;
474
475 static NodeRef getEntryNode(const GraphTy G) {
476 return *G->roots_begin();
477 }
478
479 static bool predecessorOfTrivial(NodeRef N) {
480 return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
481 }
482
483 static ChildIteratorType child_begin(NodeRef N) {
484 if (predecessorOfTrivial(N))
485 return child_begin(*N->succ_begin());
486 return N->succ_begin();
487 }
488
489 static ChildIteratorType child_end(NodeRef N) {
490 if (predecessorOfTrivial(N))
491 return child_end(N->getFirstSucc());
492 return N->succ_end();
493 }
494
495 static nodes_iterator nodes_begin(const GraphTy G) {
496 return df_begin(G);
497 }
498
499 static nodes_iterator nodes_end(const GraphTy G) {
500 return df_end(G);
501 }
502 };
503} // namespace llvm
504
505#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H

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

/build/llvm-toolchain-snapshot-8~svn345461/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)((Begin + idx < End) ? static_cast<void> (0) : __assert_fail
("Begin + idx < End", "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include/clang/Analysis/Support/BumpVector.h"
, 110, __PRETTY_FUNCTION__))
;
111 return Begin[idx];
112 }
113 const_reference operator[](unsigned idx) const {
114 assert(Begin + idx < End)((Begin + idx < End) ? static_cast<void> (0) : __assert_fail
("Begin + idx < End", "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include/clang/Analysis/Support/BumpVector.h"
, 114, __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.")((I >= Begin && I <= End && "Iterator out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= Begin && I <= End && \"Iterator out of bounds.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include/clang/Analysis/Support/BumpVector.h"
, 175, __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