Bug Summary

File:tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
Warning:line 39, column 65
Potential memory leak

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ExplodedGraph.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -relaxed-aliasing -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn325874/build-llvm/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-7~svn325874/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-7~svn325874/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn325874/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn325874/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn325874/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/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-7~svn325874/build-llvm/tools/clang/lib/StaticAnalyzer/Core -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-02-23-163436-368-1 -x c++ /build/llvm-toolchain-snapshot-7~svn325874/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

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

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

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

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

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

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