Bug Summary

File:tools/clang/include/clang/Analysis/Support/BumpVector.h
Warning:line 38, 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-9/lib/clang/9.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-9~svn362543/build-llvm/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/StaticAnalyzer/Core -I /build/llvm-toolchain-snapshot-9~svn362543/tools/clang/include -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/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/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.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-9~svn362543/build-llvm/tools/clang/lib/StaticAnalyzer/Core -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -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-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

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

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

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

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h

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

/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/include/clang/Analysis/Support/BumpVector.h

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