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 -analyzer-config-compatibility-mode=true -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 CLANG_VENDOR="Debian " -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-8~svn350071/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-8~svn350071/tools/clang/include -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn350071/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~svn350071/build-llvm/tools/clang/lib/StaticAnalyzer/Core -fdebug-prefix-map=/build/llvm-toolchain-snapshot-8~svn350071=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -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-12-27-042839-1215-1 -x c++ /build/llvm-toolchain-snapshot-8~svn350071/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn350071/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~svn350071/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~svn350071/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~svn350071/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~svn350071/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~svn350071/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~svn350071/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~svn350071/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~svn350071/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~svn350071/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~svn350071/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 return G->getAllocator().identifyKnownAlignedObject<ExplodedNode>(this);
288}
289
290bool ExplodedNode::isTrivial() const {
291 return pred_size() == 1 && succ_size() == 1 &&
292 getFirstPred()->getState()->getID() == getState()->getID() &&
293 getFirstPred()->succ_size() == 1;
294}
295
296ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
297 ProgramStateRef State,
298 bool IsSink,
299 bool* IsNew) {
300 // Profile 'State' to determine if we already have an existing node.
301 llvm::FoldingSetNodeID profile;
302 void *InsertPos = nullptr;
303
304 NodeTy::Profile(profile, L, State, IsSink);
305 NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
306
307 if (!V) {
308 if (!FreeNodes.empty()) {
309 V = FreeNodes.back();
310 FreeNodes.pop_back();
311 }
312 else {
313 // Allocate a new node.
314 V = (NodeTy*) getAllocator().Allocate<NodeTy>();
315 }
316
317 new (V) NodeTy(L, State, IsSink);
318
319 if (ReclaimNodeInterval)
320 ChangedNodes.push_back(V);
321
322 // Insert the node into the node set and return it.
323 Nodes.InsertNode(V, InsertPos);
324 ++NumNodes;
325
326 if (IsNew) *IsNew = true;
327 }
328 else
329 if (IsNew) *IsNew = false;
330
331 return V;
332}
333
334ExplodedNode *ExplodedGraph::createUncachedNode(const ProgramPoint &L,
335 ProgramStateRef State,
336 bool IsSink) {
337 NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
338 new (V) NodeTy(L, State, IsSink);
339 return V;
340}
341
342std::unique_ptr<ExplodedGraph>
343ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
344 InterExplodedGraphMap *ForwardMap,
345 InterExplodedGraphMap *InverseMap) const {
346 if (Nodes.empty())
1
Taking false branch
347 return nullptr;
348
349 using Pass1Ty = llvm::DenseSet<const ExplodedNode *>;
350 Pass1Ty Pass1;
351
352 using Pass2Ty = InterExplodedGraphMap;
353 InterExplodedGraphMap Pass2Scratch;
354 Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;
2
Assuming 'ForwardMap' is non-null
3
'?' condition is true
355
356 SmallVector<const ExplodedNode*, 10> WL1, WL2;
357
358 // ===- Pass 1 (reverse DFS) -===
359 for (const auto Sink : Sinks)
4
Assuming '__begin1' is equal to '__end1'
360 if (Sink)
361 WL1.push_back(Sink);
362
363 // Process the first worklist until it is empty.
364 while (!WL1.empty()) {
5
Loop condition is false. Execution continues on line 382
365 const ExplodedNode *N = WL1.pop_back_val();
366
367 // Have we already visited this node? If so, continue to the next one.
368 if (!Pass1.insert(N).second)
369 continue;
370
371 // If this is a root enqueue it to the second worklist.
372 if (N->Preds.empty()) {
373 WL2.push_back(N);
374 continue;
375 }
376
377 // Visit our predecessors and enqueue them.
378 WL1.append(N->Preds.begin(), N->Preds.end());
379 }
380
381 // We didn't hit a root? Return with a null pointer for the new graph.
382 if (WL2.empty())
6
Taking false branch
383 return nullptr;
384
385 // Create an empty graph.
386 std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
7
Calling 'ExplodedGraph::MakeEmptyGraph'
387
388 // ===- Pass 2 (forward DFS to construct the new graph) -===
389 while (!WL2.empty()) {
390 const ExplodedNode *N = WL2.pop_back_val();
391
392 // Skip this node if we have already processed it.
393 if (Pass2.find(N) != Pass2.end())
394 continue;
395
396 // Create the corresponding node in the new graph and record the mapping
397 // from the old node to the new node.
398 ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State, N->isSink());
399 Pass2[N] = NewN;
400
401 // Also record the reverse mapping from the new node to the old node.
402 if (InverseMap) (*InverseMap)[NewN] = N;
403
404 // If this node is a root, designate it as such in the graph.
405 if (N->Preds.empty())
406 G->addRoot(NewN);
407
408 // In the case that some of the intended predecessors of NewN have already
409 // been created, we should hook them up as predecessors.
410
411 // Walk through the predecessors of 'N' and hook up their corresponding
412 // nodes in the new graph (if any) to the freshly created node.
413 for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
414 I != E; ++I) {
415 Pass2Ty::iterator PI = Pass2.find(*I);
416 if (PI == Pass2.end())
417 continue;
418
419 NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
420 }
421
422 // In the case that some of the intended successors of NewN have already
423 // been created, we should hook them up as successors. Otherwise, enqueue
424 // the new nodes from the original graph that should have nodes created
425 // in the new graph.
426 for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
427 I != E; ++I) {
428 Pass2Ty::iterator PI = Pass2.find(*I);
429 if (PI != Pass2.end()) {
430 const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
431 continue;
432 }
433
434 // Enqueue nodes to the worklist that were marked during pass 1.
435 if (Pass1.count(*I))
436 WL2.push_back(*I);
437 }
438 }
439
440 return G;
441}

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

/build/llvm-toolchain-snapshot-8~svn350071/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~svn350071/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~svn350071/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~svn350071/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