Bug Summary

File:tools/clang/lib/Frontend/CacheTokens.cpp
Warning:line 603, column 3
Use of memory after it is freed

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 CacheTokens.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -relaxed-aliasing -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/clang/lib/Frontend -I /build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend -I /build/llvm-toolchain-snapshot-7~svn329677/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/clang/lib/Frontend -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp

/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp

1//===--- CacheTokens.cpp - Caching of lexer tokens for PTH support --------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This provides a possible implementation of PTH support for Clang that is
11// based on caching lexed tokens and identifiers.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/Basic/Diagnostic.h"
16#include "clang/Basic/FileManager.h"
17#include "clang/Basic/FileSystemStatCache.h"
18#include "clang/Basic/IdentifierTable.h"
19#include "clang/Basic/SourceManager.h"
20#include "clang/Frontend/Utils.h"
21#include "clang/Lex/Lexer.h"
22#include "clang/Lex/PTHManager.h"
23#include "clang/Lex/Preprocessor.h"
24#include "llvm/ADT/StringMap.h"
25#include "llvm/Support/DJB.h"
26#include "llvm/Support/EndianStream.h"
27#include "llvm/Support/FileSystem.h"
28#include "llvm/Support/MemoryBuffer.h"
29#include "llvm/Support/OnDiskHashTable.h"
30#include "llvm/Support/Path.h"
31
32// FIXME: put this somewhere else?
33#ifndef S_ISDIR
34#define S_ISDIR(x)(((x)&_S_IFDIR)!=0) (((x)&_S_IFDIR)!=0)
35#endif
36
37using namespace clang;
38
39//===----------------------------------------------------------------------===//
40// PTH-specific stuff.
41//===----------------------------------------------------------------------===//
42
43typedef uint32_t Offset;
44
45namespace {
46class PTHEntry {
47 Offset TokenData, PPCondData;
48
49public:
50 PTHEntry() {}
51
52 PTHEntry(Offset td, Offset ppcd)
53 : TokenData(td), PPCondData(ppcd) {}
54
55 Offset getTokenOffset() const { return TokenData; }
56 Offset getPPCondTableOffset() const { return PPCondData; }
57};
58
59
60class PTHEntryKeyVariant {
61 union {
62 const FileEntry *FE;
63 // FIXME: Use "StringRef Path;" when MSVC 2013 is dropped.
64 const char *PathPtr;
65 };
66 size_t PathSize;
67 enum { IsFE = 0x1, IsDE = 0x2, IsNoExist = 0x0 } Kind;
68 FileData *Data;
69
70public:
71 PTHEntryKeyVariant(const FileEntry *fe) : FE(fe), Kind(IsFE), Data(nullptr) {}
72
73 PTHEntryKeyVariant(FileData *Data, StringRef Path)
74 : PathPtr(Path.data()), PathSize(Path.size()), Kind(IsDE),
75 Data(new FileData(*Data)) {}
76
77 explicit PTHEntryKeyVariant(StringRef Path)
78 : PathPtr(Path.data()), PathSize(Path.size()), Kind(IsNoExist),
79 Data(nullptr) {}
80
81 bool isFile() const { return Kind == IsFE; }
82
83 StringRef getString() const {
84 return Kind == IsFE ? FE->getName() : StringRef(PathPtr, PathSize);
85 }
86
87 unsigned getKind() const { return (unsigned) Kind; }
88
89 void EmitData(raw_ostream& Out) {
90 using namespace llvm::support;
91 endian::Writer<little> LE(Out);
92 switch (Kind) {
93 case IsFE: {
94 // Emit stat information.
95 llvm::sys::fs::UniqueID UID = FE->getUniqueID();
96 LE.write<uint64_t>(UID.getFile());
97 LE.write<uint64_t>(UID.getDevice());
98 LE.write<uint64_t>(FE->getModificationTime());
99 LE.write<uint64_t>(FE->getSize());
100 } break;
101 case IsDE:
102 // Emit stat information.
103 LE.write<uint64_t>(Data->UniqueID.getFile());
104 LE.write<uint64_t>(Data->UniqueID.getDevice());
105 LE.write<uint64_t>(Data->ModTime);
106 LE.write<uint64_t>(Data->Size);
107 delete Data;
108 break;
109 default:
110 break;
111 }
112 }
113
114 unsigned getRepresentationLength() const {
115 return Kind == IsNoExist ? 0 : 4 * 8;
116 }
117};
118
119class FileEntryPTHEntryInfo {
120public:
121 typedef PTHEntryKeyVariant key_type;
122 typedef key_type key_type_ref;
123
124 typedef PTHEntry data_type;
125 typedef const PTHEntry& data_type_ref;
126
127 typedef unsigned hash_value_type;
128 typedef unsigned offset_type;
129
130 static hash_value_type ComputeHash(PTHEntryKeyVariant V) {
131 return llvm::djbHash(V.getString());
132 }
133
134 static std::pair<unsigned,unsigned>
135 EmitKeyDataLength(raw_ostream& Out, PTHEntryKeyVariant V,
136 const PTHEntry& E) {
137 using namespace llvm::support;
138 endian::Writer<little> LE(Out);
139
140 unsigned n = V.getString().size() + 1 + 1;
141 LE.write<uint16_t>(n);
142
143 unsigned m = V.getRepresentationLength() + (V.isFile() ? 4 + 4 : 0);
144 LE.write<uint8_t>(m);
145
146 return std::make_pair(n, m);
147 }
148
149 static void EmitKey(raw_ostream& Out, PTHEntryKeyVariant V, unsigned n){
150 using namespace llvm::support;
151 // Emit the entry kind.
152 endian::Writer<little>(Out).write<uint8_t>((unsigned)V.getKind());
153 // Emit the string.
154 Out.write(V.getString().data(), n - 1);
155 }
156
157 static void EmitData(raw_ostream& Out, PTHEntryKeyVariant V,
158 const PTHEntry& E, unsigned) {
159 using namespace llvm::support;
160 endian::Writer<little> LE(Out);
161
162 // For file entries emit the offsets into the PTH file for token data
163 // and the preprocessor blocks table.
164 if (V.isFile()) {
165 LE.write<uint32_t>(E.getTokenOffset());
166 LE.write<uint32_t>(E.getPPCondTableOffset());
167 }
168
169 // Emit any other data associated with the key (i.e., stat information).
170 V.EmitData(Out);
171 }
172};
173
174class OffsetOpt {
175 bool valid;
176 Offset off;
177public:
178 OffsetOpt() : valid(false) {}
179 bool hasOffset() const { return valid; }
180 Offset getOffset() const { assert(valid)(static_cast <bool> (valid) ? void (0) : __assert_fail (
"valid", "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 180, __extension__ __PRETTY_FUNCTION__))
; return off; }
181 void setOffset(Offset o) { off = o; valid = true; }
182};
183} // end anonymous namespace
184
185typedef llvm::OnDiskChainedHashTableGenerator<FileEntryPTHEntryInfo> PTHMap;
186
187namespace {
188class PTHWriter {
189 typedef llvm::DenseMap<const IdentifierInfo*,uint32_t> IDMap;
190 typedef llvm::StringMap<OffsetOpt, llvm::BumpPtrAllocator> CachedStrsTy;
191
192 raw_pwrite_stream &Out;
193 Preprocessor& PP;
194 IDMap IM;
195 std::vector<llvm::StringMapEntry<OffsetOpt>*> StrEntries;
196 PTHMap PM;
197 CachedStrsTy CachedStrs;
198 uint32_t idcount;
199 Offset CurStrOffset;
200
201 //// Get the persistent id for the given IdentifierInfo*.
202 uint32_t ResolveID(const IdentifierInfo* II);
203
204 /// Emit a token to the PTH file.
205 void EmitToken(const Token& T);
206
207 void Emit8(uint32_t V) {
208 using namespace llvm::support;
209 endian::Writer<little>(Out).write<uint8_t>(V);
210 }
211
212 void Emit16(uint32_t V) {
213 using namespace llvm::support;
214 endian::Writer<little>(Out).write<uint16_t>(V);
215 }
216
217 void Emit32(uint32_t V) {
218 using namespace llvm::support;
219 endian::Writer<little>(Out).write<uint32_t>(V);
220 }
221
222 void EmitBuf(const char *Ptr, unsigned NumBytes) {
223 Out.write(Ptr, NumBytes);
224 }
225
226 void EmitString(StringRef V) {
227 using namespace llvm::support;
228 endian::Writer<little>(Out).write<uint16_t>(V.size());
229 EmitBuf(V.data(), V.size());
230 }
231
232 /// EmitIdentifierTable - Emits two tables to the PTH file. The first is
233 /// a hashtable mapping from identifier strings to persistent IDs.
234 /// The second is a straight table mapping from persistent IDs to string data
235 /// (the keys of the first table).
236 std::pair<Offset, Offset> EmitIdentifierTable();
237
238 /// EmitFileTable - Emit a table mapping from file name strings to PTH
239 /// token data.
240 Offset EmitFileTable() { return PM.Emit(Out); }
241
242 PTHEntry LexTokens(Lexer& L);
243 Offset EmitCachedSpellings();
244
245public:
246 PTHWriter(raw_pwrite_stream &out, Preprocessor &pp)
247 : Out(out), PP(pp), idcount(0), CurStrOffset(0) {}
248
249 PTHMap &getPM() { return PM; }
250 void GeneratePTH(StringRef MainFile);
251};
252} // end anonymous namespace
253
254uint32_t PTHWriter::ResolveID(const IdentifierInfo* II) {
255 // Null IdentifierInfo's map to the persistent ID 0.
256 if (!II)
257 return 0;
258
259 IDMap::iterator I = IM.find(II);
260 if (I != IM.end())
261 return I->second; // We've already added 1.
262
263 IM[II] = ++idcount; // Pre-increment since '0' is reserved for NULL.
264 return idcount;
265}
266
267void PTHWriter::EmitToken(const Token& T) {
268 // Emit the token kind, flags, and length.
269 Emit32(((uint32_t) T.getKind()) | ((((uint32_t) T.getFlags())) << 8)|
270 (((uint32_t) T.getLength()) << 16));
271
272 if (!T.isLiteral()) {
273 Emit32(ResolveID(T.getIdentifierInfo()));
274 } else {
275 // We cache *un-cleaned* spellings. This gives us 100% fidelity with the
276 // source code.
277 StringRef s(T.getLiteralData(), T.getLength());
278
279 // Get the string entry.
280 auto &E = *CachedStrs.insert(std::make_pair(s, OffsetOpt())).first;
281
282 // If this is a new string entry, bump the PTH offset.
283 if (!E.second.hasOffset()) {
284 E.second.setOffset(CurStrOffset);
285 StrEntries.push_back(&E);
286 CurStrOffset += s.size() + 1;
287 }
288
289 // Emit the relative offset into the PTH file for the spelling string.
290 Emit32(E.second.getOffset());
291 }
292
293 // Emit the offset into the original source file of this token so that we
294 // can reconstruct its SourceLocation.
295 Emit32(PP.getSourceManager().getFileOffset(T.getLocation()));
296}
297
298PTHEntry PTHWriter::LexTokens(Lexer& L) {
299 // Pad 0's so that we emit tokens to a 4-byte alignment.
300 // This speed up reading them back in.
301 using namespace llvm::support;
302 endian::Writer<little> LE(Out);
303 uint32_t TokenOff = Out.tell();
304 for (uint64_t N = llvm::OffsetToAlignment(TokenOff, 4); N; --N, ++TokenOff)
305 LE.write<uint8_t>(0);
306
307 // Keep track of matching '#if' ... '#endif'.
308 typedef std::vector<std::pair<Offset, unsigned> > PPCondTable;
309 PPCondTable PPCond;
310 std::vector<unsigned> PPStartCond;
311 bool ParsingPreprocessorDirective = false;
312 Token Tok;
313
314 do {
315 L.LexFromRawLexer(Tok);
316 NextToken:
317
318 if ((Tok.isAtStartOfLine() || Tok.is(tok::eof)) &&
319 ParsingPreprocessorDirective) {
320 // Insert an eod token into the token cache. It has the same
321 // position as the next token that is not on the same line as the
322 // preprocessor directive. Observe that we continue processing
323 // 'Tok' when we exit this branch.
324 Token Tmp = Tok;
325 Tmp.setKind(tok::eod);
326 Tmp.clearFlag(Token::StartOfLine);
327 Tmp.setIdentifierInfo(nullptr);
328 EmitToken(Tmp);
329 ParsingPreprocessorDirective = false;
330 }
331
332 if (Tok.is(tok::raw_identifier)) {
333 PP.LookUpIdentifierInfo(Tok);
334 EmitToken(Tok);
335 continue;
336 }
337
338 if (Tok.is(tok::hash) && Tok.isAtStartOfLine()) {
339 // Special processing for #include. Store the '#' token and lex
340 // the next token.
341 assert(!ParsingPreprocessorDirective)(static_cast <bool> (!ParsingPreprocessorDirective) ? void
(0) : __assert_fail ("!ParsingPreprocessorDirective", "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 341, __extension__ __PRETTY_FUNCTION__))
;
342 Offset HashOff = (Offset) Out.tell();
343
344 // Get the next token.
345 Token NextTok;
346 L.LexFromRawLexer(NextTok);
347
348 // If we see the start of line, then we had a null directive "#". In
349 // this case, discard both tokens.
350 if (NextTok.isAtStartOfLine())
351 goto NextToken;
352
353 // The token is the start of a directive. Emit it.
354 EmitToken(Tok);
355 Tok = NextTok;
356
357 // Did we see 'include'/'import'/'include_next'?
358 if (Tok.isNot(tok::raw_identifier)) {
359 EmitToken(Tok);
360 continue;
361 }
362
363 IdentifierInfo* II = PP.LookUpIdentifierInfo(Tok);
364 tok::PPKeywordKind K = II->getPPKeywordID();
365
366 ParsingPreprocessorDirective = true;
367
368 switch (K) {
369 case tok::pp_not_keyword:
370 // Invalid directives "#foo" can occur in #if 0 blocks etc, just pass
371 // them through.
372 default:
373 break;
374
375 case tok::pp_include:
376 case tok::pp_import:
377 case tok::pp_include_next: {
378 // Save the 'include' token.
379 EmitToken(Tok);
380 // Lex the next token as an include string.
381 L.setParsingPreprocessorDirective(true);
382 L.LexIncludeFilename(Tok);
383 L.setParsingPreprocessorDirective(false);
384 assert(!Tok.isAtStartOfLine())(static_cast <bool> (!Tok.isAtStartOfLine()) ? void (0)
: __assert_fail ("!Tok.isAtStartOfLine()", "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 384, __extension__ __PRETTY_FUNCTION__))
;
385 if (Tok.is(tok::raw_identifier))
386 PP.LookUpIdentifierInfo(Tok);
387
388 break;
389 }
390 case tok::pp_if:
391 case tok::pp_ifdef:
392 case tok::pp_ifndef: {
393 // Add an entry for '#if' and friends. We initially set the target
394 // index to 0. This will get backpatched when we hit #endif.
395 PPStartCond.push_back(PPCond.size());
396 PPCond.push_back(std::make_pair(HashOff, 0U));
397 break;
398 }
399 case tok::pp_endif: {
400 // Add an entry for '#endif'. We set the target table index to itself.
401 // This will later be set to zero when emitting to the PTH file. We
402 // use 0 for uninitialized indices because that is easier to debug.
403 unsigned index = PPCond.size();
404 // Backpatch the opening '#if' entry.
405 assert(!PPStartCond.empty())(static_cast <bool> (!PPStartCond.empty()) ? void (0) :
__assert_fail ("!PPStartCond.empty()", "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 405, __extension__ __PRETTY_FUNCTION__))
;
406 assert(PPCond.size() > PPStartCond.back())(static_cast <bool> (PPCond.size() > PPStartCond.back
()) ? void (0) : __assert_fail ("PPCond.size() > PPStartCond.back()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 406, __extension__ __PRETTY_FUNCTION__))
;
407 assert(PPCond[PPStartCond.back()].second == 0)(static_cast <bool> (PPCond[PPStartCond.back()].second ==
0) ? void (0) : __assert_fail ("PPCond[PPStartCond.back()].second == 0"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 407, __extension__ __PRETTY_FUNCTION__))
;
408 PPCond[PPStartCond.back()].second = index;
409 PPStartCond.pop_back();
410 // Add the new entry to PPCond.
411 PPCond.push_back(std::make_pair(HashOff, index));
412 EmitToken(Tok);
413
414 // Some files have gibberish on the same line as '#endif'.
415 // Discard these tokens.
416 do
417 L.LexFromRawLexer(Tok);
418 while (Tok.isNot(tok::eof) && !Tok.isAtStartOfLine());
419 // We have the next token in hand.
420 // Don't immediately lex the next one.
421 goto NextToken;
422 }
423 case tok::pp_elif:
424 case tok::pp_else: {
425 // Add an entry for #elif or #else.
426 // This serves as both a closing and opening of a conditional block.
427 // This means that its entry will get backpatched later.
428 unsigned index = PPCond.size();
429 // Backpatch the previous '#if' entry.
430 assert(!PPStartCond.empty())(static_cast <bool> (!PPStartCond.empty()) ? void (0) :
__assert_fail ("!PPStartCond.empty()", "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 430, __extension__ __PRETTY_FUNCTION__))
;
431 assert(PPCond.size() > PPStartCond.back())(static_cast <bool> (PPCond.size() > PPStartCond.back
()) ? void (0) : __assert_fail ("PPCond.size() > PPStartCond.back()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 431, __extension__ __PRETTY_FUNCTION__))
;
432 assert(PPCond[PPStartCond.back()].second == 0)(static_cast <bool> (PPCond[PPStartCond.back()].second ==
0) ? void (0) : __assert_fail ("PPCond[PPStartCond.back()].second == 0"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 432, __extension__ __PRETTY_FUNCTION__))
;
433 PPCond[PPStartCond.back()].second = index;
434 PPStartCond.pop_back();
435 // Now add '#elif' as a new block opening.
436 PPCond.push_back(std::make_pair(HashOff, 0U));
437 PPStartCond.push_back(index);
438 break;
439 }
440 }
441 }
442
443 EmitToken(Tok);
444 }
445 while (Tok.isNot(tok::eof));
446
447 assert(PPStartCond.empty() && "Error: imblanced preprocessor conditionals.")(static_cast <bool> (PPStartCond.empty() && "Error: imblanced preprocessor conditionals."
) ? void (0) : __assert_fail ("PPStartCond.empty() && \"Error: imblanced preprocessor conditionals.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 447, __extension__ __PRETTY_FUNCTION__))
;
448
449 // Next write out PPCond.
450 Offset PPCondOff = (Offset) Out.tell();
451
452 // Write out the size of PPCond so that clients can identifer empty tables.
453 Emit32(PPCond.size());
454
455 for (unsigned i = 0, e = PPCond.size(); i!=e; ++i) {
456 Emit32(PPCond[i].first - TokenOff);
457 uint32_t x = PPCond[i].second;
458 assert(x != 0 && "PPCond entry not backpatched.")(static_cast <bool> (x != 0 && "PPCond entry not backpatched."
) ? void (0) : __assert_fail ("x != 0 && \"PPCond entry not backpatched.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 458, __extension__ __PRETTY_FUNCTION__))
;
459 // Emit zero for #endifs. This allows us to do checking when
460 // we read the PTH file back in.
461 Emit32(x == i ? 0 : x);
462 }
463
464 return PTHEntry(TokenOff, PPCondOff);
465}
466
467Offset PTHWriter::EmitCachedSpellings() {
468 // Write each cached strings to the PTH file.
469 Offset SpellingsOff = Out.tell();
470
471 for (std::vector<llvm::StringMapEntry<OffsetOpt>*>::iterator
472 I = StrEntries.begin(), E = StrEntries.end(); I!=E; ++I)
473 EmitBuf((*I)->getKeyData(), (*I)->getKeyLength()+1 /*nul included*/);
474
475 return SpellingsOff;
476}
477
478static uint32_t swap32le(uint32_t X) {
479 return llvm::support::endian::byte_swap<uint32_t, llvm::support::little>(X);
480}
481
482static void pwrite32le(raw_pwrite_stream &OS, uint32_t Val, uint64_t &Off) {
483 uint32_t LEVal = swap32le(Val);
484 OS.pwrite(reinterpret_cast<const char *>(&LEVal), 4, Off);
485 Off += 4;
486}
487
488void PTHWriter::GeneratePTH(StringRef MainFile) {
489 // Generate the prologue.
490 Out << "cfe-pth" << '\0';
491 Emit32(PTHManager::Version);
492
493 // Leave 4 words for the prologue.
494 Offset PrologueOffset = Out.tell();
495 for (unsigned i = 0; i < 4; ++i)
496 Emit32(0);
497
498 // Write the name of the MainFile.
499 if (!MainFile.empty()) {
500 EmitString(MainFile);
501 } else {
502 // String with 0 bytes.
503 Emit16(0);
504 }
505 Emit8(0);
506
507 // Iterate over all the files in SourceManager. Create a lexer
508 // for each file and cache the tokens.
509 SourceManager &SM = PP.getSourceManager();
510 const LangOptions &LOpts = PP.getLangOpts();
511
512 for (SourceManager::fileinfo_iterator I = SM.fileinfo_begin(),
513 E = SM.fileinfo_end(); I != E; ++I) {
514 const SrcMgr::ContentCache &C = *I->second;
515 const FileEntry *FE = C.OrigEntry;
516
517 // FIXME: Handle files with non-absolute paths.
518 if (llvm::sys::path::is_relative(FE->getName()))
519 continue;
520
521 const llvm::MemoryBuffer *B = C.getBuffer(PP.getDiagnostics(), SM);
522 if (!B) continue;
523
524 FileID FID = SM.createFileID(FE, SourceLocation(), SrcMgr::C_User);
525 const llvm::MemoryBuffer *FromFile = SM.getBuffer(FID);
526 Lexer L(FID, FromFile, SM, LOpts);
527 PM.insert(FE, LexTokens(L));
528 }
529
530 // Write out the identifier table.
531 const std::pair<Offset,Offset> &IdTableOff = EmitIdentifierTable();
532
533 // Write out the cached strings table.
534 Offset SpellingOff = EmitCachedSpellings();
535
536 // Write out the file table.
537 Offset FileTableOff = EmitFileTable();
538
539 // Finally, write the prologue.
540 uint64_t Off = PrologueOffset;
541 pwrite32le(Out, IdTableOff.first, Off);
542 pwrite32le(Out, IdTableOff.second, Off);
543 pwrite32le(Out, FileTableOff, Off);
544 pwrite32le(Out, SpellingOff, Off);
545}
546
547namespace {
548/// StatListener - A simple "interpose" object used to monitor stat calls
549/// invoked by FileManager while processing the original sources used
550/// as input to PTH generation. StatListener populates the PTHWriter's
551/// file map with stat information for directories as well as negative stats.
552/// Stat information for files are populated elsewhere.
553class StatListener : public FileSystemStatCache {
554 PTHMap &PM;
555public:
556 StatListener(PTHMap &pm) : PM(pm) {}
557 ~StatListener() override {}
558
559 LookupResult getStat(StringRef Path, FileData &Data, bool isFile,
560 std::unique_ptr<vfs::File> *F,
561 vfs::FileSystem &FS) override {
562 LookupResult Result = statChained(Path, Data, isFile, F, FS);
563
564 if (Result == CacheMissing) // Failed 'stat'.
565 PM.insert(PTHEntryKeyVariant(Path), PTHEntry());
566 else if (Data.IsDirectory) {
567 // Only cache directories with absolute paths.
568 if (llvm::sys::path::is_relative(Path))
569 return Result;
570
571 PM.insert(PTHEntryKeyVariant(&Data, Path), PTHEntry());
572 }
573
574 return Result;
575 }
576};
577} // end anonymous namespace
578
579void clang::CacheTokens(Preprocessor &PP, raw_pwrite_stream *OS) {
580 // Get the name of the main file.
581 const SourceManager &SrcMgr = PP.getSourceManager();
582 const FileEntry *MainFile = SrcMgr.getFileEntryForID(SrcMgr.getMainFileID());
583 SmallString<128> MainFilePath(MainFile->getName());
584
585 llvm::sys::fs::make_absolute(MainFilePath);
586
587 // Create the PTHWriter.
588 PTHWriter PW(*OS, PP);
589
590 // Install the 'stat' system call listener in the FileManager.
591 auto StatCacheOwner = llvm::make_unique<StatListener>(PW.getPM());
1
Calling 'make_unique'
3
Returned allocated memory
592 StatListener *StatCache = StatCacheOwner.get();
593 PP.getFileManager().addStatCache(std::move(StatCacheOwner),
4
Calling '~unique_ptr'
9
Returning from '~unique_ptr'
594 /*AtBeginning=*/true);
595
596 // Lex through the entire file. This will populate SourceManager with
597 // all of the header information.
598 Token Tok;
599 PP.EnterMainSourceFile();
600 do { PP.Lex(Tok); } while (Tok.isNot(tok::eof));
10
Loop condition is false. Exiting loop
601
602 // Generate the PTH file.
603 PP.getFileManager().removeStatCache(StatCache);
11
Use of memory after it is freed
604 PW.GeneratePTH(MainFilePath.str());
605}
606
607//===----------------------------------------------------------------------===//
608
609namespace {
610class PTHIdKey {
611public:
612 const IdentifierInfo* II;
613 uint32_t FileOffset;
614};
615
616class PTHIdentifierTableTrait {
617public:
618 typedef PTHIdKey* key_type;
619 typedef key_type key_type_ref;
620
621 typedef uint32_t data_type;
622 typedef data_type data_type_ref;
623
624 typedef unsigned hash_value_type;
625 typedef unsigned offset_type;
626
627 static hash_value_type ComputeHash(PTHIdKey* key) {
628 return llvm::djbHash(key->II->getName());
629 }
630
631 static std::pair<unsigned,unsigned>
632 EmitKeyDataLength(raw_ostream& Out, const PTHIdKey* key, uint32_t) {
633 using namespace llvm::support;
634 unsigned n = key->II->getLength() + 1;
635 endian::Writer<little>(Out).write<uint16_t>(n);
636 return std::make_pair(n, sizeof(uint32_t));
637 }
638
639 static void EmitKey(raw_ostream& Out, PTHIdKey* key, unsigned n) {
640 // Record the location of the key data. This is used when generating
641 // the mapping from persistent IDs to strings.
642 key->FileOffset = Out.tell();
643 Out.write(key->II->getNameStart(), n);
644 }
645
646 static void EmitData(raw_ostream& Out, PTHIdKey*, uint32_t pID,
647 unsigned) {
648 using namespace llvm::support;
649 endian::Writer<little>(Out).write<uint32_t>(pID);
650 }
651};
652} // end anonymous namespace
653
654/// EmitIdentifierTable - Emits two tables to the PTH file. The first is
655/// a hashtable mapping from identifier strings to persistent IDs. The second
656/// is a straight table mapping from persistent IDs to string data (the
657/// keys of the first table).
658///
659std::pair<Offset,Offset> PTHWriter::EmitIdentifierTable() {
660 // Build two maps:
661 // (1) an inverse map from persistent IDs -> (IdentifierInfo*,Offset)
662 // (2) a map from (IdentifierInfo*, Offset)* -> persistent IDs
663
664 // Note that we use 'calloc', so all the bytes are 0.
665 PTHIdKey *IIDMap = static_cast<PTHIdKey*>(
666 llvm::safe_calloc(idcount, sizeof(PTHIdKey)));
667
668 // Create the hashtable.
669 llvm::OnDiskChainedHashTableGenerator<PTHIdentifierTableTrait> IIOffMap;
670
671 // Generate mapping from persistent IDs -> IdentifierInfo*.
672 for (IDMap::iterator I = IM.begin(), E = IM.end(); I != E; ++I) {
673 // Decrement by 1 because we are using a vector for the lookup and
674 // 0 is reserved for NULL.
675 assert(I->second > 0)(static_cast <bool> (I->second > 0) ? void (0) : __assert_fail
("I->second > 0", "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 675, __extension__ __PRETTY_FUNCTION__))
;
676 assert(I->second-1 < idcount)(static_cast <bool> (I->second-1 < idcount) ? void
(0) : __assert_fail ("I->second-1 < idcount", "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Frontend/CacheTokens.cpp"
, 676, __extension__ __PRETTY_FUNCTION__))
;
677 unsigned idx = I->second-1;
678
679 // Store the mapping from persistent ID to IdentifierInfo*
680 IIDMap[idx].II = I->first;
681
682 // Store the reverse mapping in a hashtable.
683 IIOffMap.insert(&IIDMap[idx], I->second);
684 }
685
686 // Write out the inverse map first. This causes the PCIDKey entries to
687 // record PTH file offsets for the string data. This is used to write
688 // the second table.
689 Offset StringTableOffset = IIOffMap.Emit(Out);
690
691 // Now emit the table mapping from persistent IDs to PTH file offsets.
692 Offset IDOff = Out.tell();
693 Emit32(idcount); // Emit the number of identifiers.
694 for (unsigned i = 0 ; i < idcount; ++i)
695 Emit32(IIDMap[i].FileOffset);
696
697 // Finally, release the inverse map.
698 free(IIDMap);
699
700 return std::make_pair(IDOff, StringTableOffset);
701}

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

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

/usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/bits/unique_ptr.h

1// unique_ptr implementation -*- C++ -*-
2
3// Copyright (C) 2008-2017 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file bits/unique_ptr.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{memory}
28 */
29
30#ifndef _UNIQUE_PTR_H1
31#define _UNIQUE_PTR_H1 1
32
33#include <bits/c++config.h>
34#include <debug/assertions.h>
35#include <type_traits>
36#include <utility>
37#include <tuple>
38#include <bits/stl_function.h>
39#include <bits/functional_hash.h>
40
41namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
42{
43_GLIBCXX_BEGIN_NAMESPACE_VERSION
44
45 /**
46 * @addtogroup pointer_abstractions
47 * @{
48 */
49
50#if _GLIBCXX_USE_DEPRECATED1
51 template<typename> class auto_ptr;
52#endif
53
54 /// Primary template of default_delete, used by unique_ptr
55 template<typename _Tp>
56 struct default_delete
57 {
58 /// Default constructor
59 constexpr default_delete() noexcept = default;
60
61 /** @brief Converting constructor.
62 *
63 * Allows conversion from a deleter for arrays of another type, @p _Up,
64 * only if @p _Up* is convertible to @p _Tp*.
65 */
66 template<typename _Up, typename = typename
67 enable_if<is_convertible<_Up*, _Tp*>::value>::type>
68 default_delete(const default_delete<_Up>&) noexcept { }
69
70 /// Calls @c delete @p __ptr
71 void
72 operator()(_Tp* __ptr) const
73 {
74 static_assert(!is_void<_Tp>::value,
75 "can't delete pointer to incomplete type");
76 static_assert(sizeof(_Tp)>0,
77 "can't delete pointer to incomplete type");
78 delete __ptr;
7
Memory is released
79 }
80 };
81
82 // _GLIBCXX_RESOLVE_LIB_DEFECTS
83 // DR 740 - omit specialization for array objects with a compile time length
84 /// Specialization for arrays, default_delete.
85 template<typename _Tp>
86 struct default_delete<_Tp[]>
87 {
88 public:
89 /// Default constructor
90 constexpr default_delete() noexcept = default;
91
92 /** @brief Converting constructor.
93 *
94 * Allows conversion from a deleter for arrays of another type, such as
95 * a const-qualified version of @p _Tp.
96 *
97 * Conversions from types derived from @c _Tp are not allowed because
98 * it is unsafe to @c delete[] an array of derived types through a
99 * pointer to the base type.
100 */
101 template<typename _Up, typename = typename
102 enable_if<is_convertible<_Up(*)[], _Tp(*)[]>::value>::type>
103 default_delete(const default_delete<_Up[]>&) noexcept { }
104
105 /// Calls @c delete[] @p __ptr
106 template<typename _Up>
107 typename enable_if<is_convertible<_Up(*)[], _Tp(*)[]>::value>::type
108 operator()(_Up* __ptr) const
109 {
110 static_assert(sizeof(_Tp)>0,
111 "can't delete pointer to incomplete type");
112 delete [] __ptr;
113 }
114 };
115
116 template <typename _Tp, typename _Dp>
117 class __uniq_ptr_impl
118 {
119 template <typename _Up, typename _Ep, typename = void>
120 struct _Ptr
121 {
122 using type = _Up*;
123 };
124
125 template <typename _Up, typename _Ep>
126 struct
127 _Ptr<_Up, _Ep, __void_t<typename remove_reference<_Ep>::type::pointer>>
128 {
129 using type = typename remove_reference<_Ep>::type::pointer;
130 };
131
132 public:
133 using _DeleterConstraint = enable_if<
134 __and_<__not_<is_pointer<_Dp>>,
135 is_default_constructible<_Dp>>::value>;
136
137 using pointer = typename _Ptr<_Tp, _Dp>::type;
138
139 __uniq_ptr_impl() = default;
140 __uniq_ptr_impl(pointer __p) : _M_t() { _M_ptr() = __p; }
141
142 template<typename _Del>
143 __uniq_ptr_impl(pointer __p, _Del&& __d)
144 : _M_t(__p, std::forward<_Del>(__d)) { }
145
146 pointer& _M_ptr() { return std::get<0>(_M_t); }
147 pointer _M_ptr() const { return std::get<0>(_M_t); }
148 _Dp& _M_deleter() { return std::get<1>(_M_t); }
149 const _Dp& _M_deleter() const { return std::get<1>(_M_t); }
150
151 private:
152 tuple<pointer, _Dp> _M_t;
153 };
154
155 /// 20.7.1.2 unique_ptr for single objects.
156 template <typename _Tp, typename _Dp = default_delete<_Tp>>
157 class unique_ptr
158 {
159 template <class _Up>
160 using _DeleterConstraint =
161 typename __uniq_ptr_impl<_Tp, _Up>::_DeleterConstraint::type;
162
163 __uniq_ptr_impl<_Tp, _Dp> _M_t;
164
165 public:
166 using pointer = typename __uniq_ptr_impl<_Tp, _Dp>::pointer;
167 using element_type = _Tp;
168 using deleter_type = _Dp;
169
170 // helper template for detecting a safe conversion from another
171 // unique_ptr
172 template<typename _Up, typename _Ep>
173 using __safe_conversion_up = __and_<
174 is_convertible<typename unique_ptr<_Up, _Ep>::pointer, pointer>,
175 __not_<is_array<_Up>>,
176 __or_<__and_<is_reference<deleter_type>,
177 is_same<deleter_type, _Ep>>,
178 __and_<__not_<is_reference<deleter_type>>,
179 is_convertible<_Ep, deleter_type>>
180 >
181 >;
182
183 // Constructors.
184
185 /// Default constructor, creates a unique_ptr that owns nothing.
186 template <typename _Up = _Dp,
187 typename = _DeleterConstraint<_Up>>
188 constexpr unique_ptr() noexcept
189 : _M_t()
190 { }
191
192 /** Takes ownership of a pointer.
193 *
194 * @param __p A pointer to an object of @c element_type
195 *
196 * The deleter will be value-initialized.
197 */
198 template <typename _Up = _Dp,
199 typename = _DeleterConstraint<_Up>>
200 explicit
201 unique_ptr(pointer __p) noexcept
202 : _M_t(__p)
203 { }
204
205 /** Takes ownership of a pointer.
206 *
207 * @param __p A pointer to an object of @c element_type
208 * @param __d A reference to a deleter.
209 *
210 * The deleter will be initialized with @p __d
211 */
212 unique_ptr(pointer __p,
213 typename conditional<is_reference<deleter_type>::value,
214 deleter_type, const deleter_type&>::type __d) noexcept
215 : _M_t(__p, __d) { }
216
217 /** Takes ownership of a pointer.
218 *
219 * @param __p A pointer to an object of @c element_type
220 * @param __d An rvalue reference to a deleter.
221 *
222 * The deleter will be initialized with @p std::move(__d)
223 */
224 unique_ptr(pointer __p,
225 typename remove_reference<deleter_type>::type&& __d) noexcept
226 : _M_t(std::move(__p), std::move(__d))
227 { static_assert(!std::is_reference<deleter_type>::value,
228 "rvalue deleter bound to reference"); }
229
230 /// Creates a unique_ptr that owns nothing.
231 template <typename _Up = _Dp,
232 typename = _DeleterConstraint<_Up>>
233 constexpr unique_ptr(nullptr_t) noexcept : unique_ptr() { }
234
235 // Move constructors.
236
237 /// Move constructor.
238 unique_ptr(unique_ptr&& __u) noexcept
239 : _M_t(__u.release(), std::forward<deleter_type>(__u.get_deleter())) { }
240
241 /** @brief Converting constructor from another type
242 *
243 * Requires that the pointer owned by @p __u is convertible to the
244 * type of pointer owned by this object, @p __u does not own an array,
245 * and @p __u has a compatible deleter type.
246 */
247 template<typename _Up, typename _Ep, typename = _Require<
248 __safe_conversion_up<_Up, _Ep>,
249 typename conditional<is_reference<_Dp>::value,
250 is_same<_Ep, _Dp>,
251 is_convertible<_Ep, _Dp>>::type>>
252 unique_ptr(unique_ptr<_Up, _Ep>&& __u) noexcept
253 : _M_t(__u.release(), std::forward<_Ep>(__u.get_deleter()))
254 { }
255
256#if _GLIBCXX_USE_DEPRECATED1
257 /// Converting constructor from @c auto_ptr
258 template<typename _Up, typename = _Require<
259 is_convertible<_Up*, _Tp*>, is_same<_Dp, default_delete<_Tp>>>>
260 unique_ptr(auto_ptr<_Up>&& __u) noexcept;
261#endif
262
263 /// Destructor, invokes the deleter if the stored pointer is not null.
264 ~unique_ptr() noexcept
265 {
266 auto& __ptr = _M_t._M_ptr();
267 if (__ptr != nullptr)
5
Taking true branch
268 get_deleter()(__ptr);
6
Calling 'default_delete::operator()'
8
Returning; memory was released via 2nd parameter
269 __ptr = pointer();
270 }
271
272 // Assignment.
273
274 /** @brief Move assignment operator.
275 *
276 * @param __u The object to transfer ownership from.
277 *
278 * Invokes the deleter first if this object owns a pointer.
279 */
280 unique_ptr&
281 operator=(unique_ptr&& __u) noexcept
282 {
283 reset(__u.release());
284 get_deleter() = std::forward<deleter_type>(__u.get_deleter());
285 return *this;
286 }
287
288 /** @brief Assignment from another type.
289 *
290 * @param __u The object to transfer ownership from, which owns a
291 * convertible pointer to a non-array object.
292 *
293 * Invokes the deleter first if this object owns a pointer.
294 */
295 template<typename _Up, typename _Ep>
296 typename enable_if< __and_<
297 __safe_conversion_up<_Up, _Ep>,
298 is_assignable<deleter_type&, _Ep&&>
299 >::value,
300 unique_ptr&>::type
301 operator=(unique_ptr<_Up, _Ep>&& __u) noexcept
302 {
303 reset(__u.release());
304 get_deleter() = std::forward<_Ep>(__u.get_deleter());
305 return *this;
306 }
307
308 /// Reset the %unique_ptr to empty, invoking the deleter if necessary.
309 unique_ptr&
310 operator=(nullptr_t) noexcept
311 {
312 reset();
313 return *this;
314 }
315
316 // Observers.
317
318 /// Dereference the stored pointer.
319 typename add_lvalue_reference<element_type>::type
320 operator*() const
321 {
322 __glibcxx_assert(get() != pointer());
323 return *get();
324 }
325
326 /// Return the stored pointer.
327 pointer
328 operator->() const noexcept
329 {
330 _GLIBCXX_DEBUG_PEDASSERT(get() != pointer());
331 return get();
332 }
333
334 /// Return the stored pointer.
335 pointer
336 get() const noexcept
337 { return _M_t._M_ptr(); }
338
339 /// Return a reference to the stored deleter.
340 deleter_type&
341 get_deleter() noexcept
342 { return _M_t._M_deleter(); }
343
344 /// Return a reference to the stored deleter.
345 const deleter_type&
346 get_deleter() const noexcept
347 { return _M_t._M_deleter(); }
348
349 /// Return @c true if the stored pointer is not null.
350 explicit operator bool() const noexcept
351 { return get() == pointer() ? false : true; }
352
353 // Modifiers.
354
355 /// Release ownership of any stored pointer.
356 pointer
357 release() noexcept
358 {
359 pointer __p = get();
360 _M_t._M_ptr() = pointer();
361 return __p;
362 }
363
364 /** @brief Replace the stored pointer.
365 *
366 * @param __p The new pointer to store.
367 *
368 * The deleter will be invoked if a pointer is already owned.
369 */
370 void
371 reset(pointer __p = pointer()) noexcept
372 {
373 using std::swap;
374 swap(_M_t._M_ptr(), __p);
375 if (__p != pointer())
376 get_deleter()(__p);
377 }
378
379 /// Exchange the pointer and deleter with another object.
380 void
381 swap(unique_ptr& __u) noexcept
382 {
383 using std::swap;
384 swap(_M_t, __u._M_t);
385 }
386
387 // Disable copy from lvalue.
388 unique_ptr(const unique_ptr&) = delete;
389 unique_ptr& operator=(const unique_ptr&) = delete;
390 };
391
392 /// 20.7.1.3 unique_ptr for array objects with a runtime length
393 // [unique.ptr.runtime]
394 // _GLIBCXX_RESOLVE_LIB_DEFECTS
395 // DR 740 - omit specialization for array objects with a compile time length
396 template<typename _Tp, typename _Dp>
397 class unique_ptr<_Tp[], _Dp>
398 {
399 template <typename _Up>
400 using _DeleterConstraint =
401 typename __uniq_ptr_impl<_Tp, _Up>::_DeleterConstraint::type;
402
403 __uniq_ptr_impl<_Tp, _Dp> _M_t;
404
405 template<typename _Up>
406 using __remove_cv = typename remove_cv<_Up>::type;
407
408 // like is_base_of<_Tp, _Up> but false if unqualified types are the same
409 template<typename _Up>
410 using __is_derived_Tp
411 = __and_< is_base_of<_Tp, _Up>,
412 __not_<is_same<__remove_cv<_Tp>, __remove_cv<_Up>>> >;
413
414 public:
415 using pointer = typename __uniq_ptr_impl<_Tp, _Dp>::pointer;
416 using element_type = _Tp;
417 using deleter_type = _Dp;
418
419 // helper template for detecting a safe conversion from another
420 // unique_ptr
421 template<typename _Up, typename _Ep,
422 typename _Up_up = unique_ptr<_Up, _Ep>,
423 typename _Up_element_type = typename _Up_up::element_type>
424 using __safe_conversion_up = __and_<
425 is_array<_Up>,
426 is_same<pointer, element_type*>,
427 is_same<typename _Up_up::pointer, _Up_element_type*>,
428 is_convertible<_Up_element_type(*)[], element_type(*)[]>,
429 __or_<__and_<is_reference<deleter_type>, is_same<deleter_type, _Ep>>,
430 __and_<__not_<is_reference<deleter_type>>,
431 is_convertible<_Ep, deleter_type>>>
432 >;
433
434 // helper template for detecting a safe conversion from a raw pointer
435 template<typename _Up>
436 using __safe_conversion_raw = __and_<
437 __or_<__or_<is_same<_Up, pointer>,
438 is_same<_Up, nullptr_t>>,
439 __and_<is_pointer<_Up>,
440 is_same<pointer, element_type*>,
441 is_convertible<
442 typename remove_pointer<_Up>::type(*)[],
443 element_type(*)[]>
444 >
445 >
446 >;
447
448 // Constructors.
449
450 /// Default constructor, creates a unique_ptr that owns nothing.
451 template <typename _Up = _Dp,
452 typename = _DeleterConstraint<_Up>>
453 constexpr unique_ptr() noexcept
454 : _M_t()
455 { }
456
457 /** Takes ownership of a pointer.
458 *
459 * @param __p A pointer to an array of a type safely convertible
460 * to an array of @c element_type
461 *
462 * The deleter will be value-initialized.
463 */
464 template<typename _Up,
465 typename _Vp = _Dp,
466 typename = _DeleterConstraint<_Vp>,
467 typename = typename enable_if<
468 __safe_conversion_raw<_Up>::value, bool>::type>
469 explicit
470 unique_ptr(_Up __p) noexcept
471 : _M_t(__p)
472 { }
473
474 /** Takes ownership of a pointer.
475 *
476 * @param __p A pointer to an array of a type safely convertible
477 * to an array of @c element_type
478 * @param __d A reference to a deleter.
479 *
480 * The deleter will be initialized with @p __d
481 */
482 template<typename _Up,
483 typename = typename enable_if<
484 __safe_conversion_raw<_Up>::value, bool>::type>
485 unique_ptr(_Up __p,
486 typename conditional<is_reference<deleter_type>::value,
487 deleter_type, const deleter_type&>::type __d) noexcept
488 : _M_t(__p, __d) { }
489
490 /** Takes ownership of a pointer.
491 *
492 * @param __p A pointer to an array of a type safely convertible
493 * to an array of @c element_type
494 * @param __d A reference to a deleter.
495 *
496 * The deleter will be initialized with @p std::move(__d)
497 */
498 template<typename _Up,
499 typename = typename enable_if<
500 __safe_conversion_raw<_Up>::value, bool>::type>
501 unique_ptr(_Up __p, typename
502 remove_reference<deleter_type>::type&& __d) noexcept
503 : _M_t(std::move(__p), std::move(__d))
504 { static_assert(!is_reference<deleter_type>::value,
505 "rvalue deleter bound to reference"); }
506
507 /// Move constructor.
508 unique_ptr(unique_ptr&& __u) noexcept
509 : _M_t(__u.release(), std::forward<deleter_type>(__u.get_deleter())) { }
510
511 /// Creates a unique_ptr that owns nothing.
512 template <typename _Up = _Dp,
513 typename = _DeleterConstraint<_Up>>
514 constexpr unique_ptr(nullptr_t) noexcept : unique_ptr() { }
515
516 template<typename _Up, typename _Ep,
517 typename = _Require<__safe_conversion_up<_Up, _Ep>>>
518 unique_ptr(unique_ptr<_Up, _Ep>&& __u) noexcept
519 : _M_t(__u.release(), std::forward<_Ep>(__u.get_deleter()))
520 { }
521
522 /// Destructor, invokes the deleter if the stored pointer is not null.
523 ~unique_ptr()
524 {
525 auto& __ptr = _M_t._M_ptr();
526 if (__ptr != nullptr)
527 get_deleter()(__ptr);
528 __ptr = pointer();
529 }
530
531 // Assignment.
532
533 /** @brief Move assignment operator.
534 *
535 * @param __u The object to transfer ownership from.
536 *
537 * Invokes the deleter first if this object owns a pointer.
538 */
539 unique_ptr&
540 operator=(unique_ptr&& __u) noexcept
541 {
542 reset(__u.release());
543 get_deleter() = std::forward<deleter_type>(__u.get_deleter());
544 return *this;
545 }
546
547 /** @brief Assignment from another type.
548 *
549 * @param __u The object to transfer ownership from, which owns a
550 * convertible pointer to an array object.
551 *
552 * Invokes the deleter first if this object owns a pointer.
553 */
554 template<typename _Up, typename _Ep>
555 typename
556 enable_if<__and_<__safe_conversion_up<_Up, _Ep>,
557 is_assignable<deleter_type&, _Ep&&>
558 >::value,
559 unique_ptr&>::type
560 operator=(unique_ptr<_Up, _Ep>&& __u) noexcept
561 {
562 reset(__u.release());
563 get_deleter() = std::forward<_Ep>(__u.get_deleter());
564 return *this;
565 }
566
567 /// Reset the %unique_ptr to empty, invoking the deleter if necessary.
568 unique_ptr&
569 operator=(nullptr_t) noexcept
570 {
571 reset();
572 return *this;
573 }
574
575 // Observers.
576
577 /// Access an element of owned array.
578 typename std::add_lvalue_reference<element_type>::type
579 operator[](size_t __i) const
580 {
581 __glibcxx_assert(get() != pointer());
582 return get()[__i];
583 }
584
585 /// Return the stored pointer.
586 pointer
587 get() const noexcept
588 { return _M_t._M_ptr(); }
589
590 /// Return a reference to the stored deleter.
591 deleter_type&
592 get_deleter() noexcept
593 { return _M_t._M_deleter(); }
594
595 /// Return a reference to the stored deleter.
596 const deleter_type&
597 get_deleter() const noexcept
598 { return _M_t._M_deleter(); }
599
600 /// Return @c true if the stored pointer is not null.
601 explicit operator bool() const noexcept
602 { return get() == pointer() ? false : true; }
603
604 // Modifiers.
605
606 /// Release ownership of any stored pointer.
607 pointer
608 release() noexcept
609 {
610 pointer __p = get();
611 _M_t._M_ptr() = pointer();
612 return __p;
613 }
614
615 /** @brief Replace the stored pointer.
616 *
617 * @param __p The new pointer to store.
618 *
619 * The deleter will be invoked if a pointer is already owned.
620 */
621 template <typename _Up,
622 typename = _Require<
623 __or_<is_same<_Up, pointer>,
624 __and_<is_same<pointer, element_type*>,
625 is_pointer<_Up>,
626 is_convertible<
627 typename remove_pointer<_Up>::type(*)[],
628 element_type(*)[]
629 >
630 >
631 >
632 >>
633 void
634 reset(_Up __p) noexcept
635 {
636 pointer __ptr = __p;
637 using std::swap;
638 swap(_M_t._M_ptr(), __ptr);
639 if (__ptr != nullptr)
640 get_deleter()(__ptr);
641 }
642
643 void reset(nullptr_t = nullptr) noexcept
644 {
645 reset(pointer());
646 }
647
648 /// Exchange the pointer and deleter with another object.
649 void
650 swap(unique_ptr& __u) noexcept
651 {
652 using std::swap;
653 swap(_M_t, __u._M_t);
654 }
655
656 // Disable copy from lvalue.
657 unique_ptr(const unique_ptr&) = delete;
658 unique_ptr& operator=(const unique_ptr&) = delete;
659 };
660
661 template<typename _Tp, typename _Dp>
662 inline
663#if __cplusplus201103L > 201402L || !defined(__STRICT_ANSI__1) // c++1z or gnu++11
664 // Constrained free swap overload, see p0185r1
665 typename enable_if<__is_swappable<_Dp>::value>::type
666#else
667 void
668#endif
669 swap(unique_ptr<_Tp, _Dp>& __x,
670 unique_ptr<_Tp, _Dp>& __y) noexcept
671 { __x.swap(__y); }
672
673#if __cplusplus201103L > 201402L || !defined(__STRICT_ANSI__1) // c++1z or gnu++11
674 template<typename _Tp, typename _Dp>
675 typename enable_if<!__is_swappable<_Dp>::value>::type
676 swap(unique_ptr<_Tp, _Dp>&,
677 unique_ptr<_Tp, _Dp>&) = delete;
678#endif
679
680 template<typename _Tp, typename _Dp,
681 typename _Up, typename _Ep>
682 inline bool
683 operator==(const unique_ptr<_Tp, _Dp>& __x,
684 const unique_ptr<_Up, _Ep>& __y)
685 { return __x.get() == __y.get(); }
686
687 template<typename _Tp, typename _Dp>
688 inline bool
689 operator==(const unique_ptr<_Tp, _Dp>& __x, nullptr_t) noexcept
690 { return !__x; }
691
692 template<typename _Tp, typename _Dp>
693 inline bool
694 operator==(nullptr_t, const unique_ptr<_Tp, _Dp>& __x) noexcept
695 { return !__x; }
696
697 template<typename _Tp, typename _Dp,
698 typename _Up, typename _Ep>
699 inline bool
700 operator!=(const unique_ptr<_Tp, _Dp>& __x,
701 const unique_ptr<_Up, _Ep>& __y)
702 { return __x.get() != __y.get(); }
703
704 template<typename _Tp, typename _Dp>
705 inline bool
706 operator!=(const unique_ptr<_Tp, _Dp>& __x, nullptr_t) noexcept
707 { return (bool)__x; }
708
709 template<typename _Tp, typename _Dp>
710 inline bool
711 operator!=(nullptr_t, const unique_ptr<_Tp, _Dp>& __x) noexcept
712 { return (bool)__x; }
713
714 template<typename _Tp, typename _Dp,
715 typename _Up, typename _Ep>
716 inline bool
717 operator<(const unique_ptr<_Tp, _Dp>& __x,
718 const unique_ptr<_Up, _Ep>& __y)
719 {
720 typedef typename
721 std::common_type<typename unique_ptr<_Tp, _Dp>::pointer,
722 typename unique_ptr<_Up, _Ep>::pointer>::type _CT;
723 return std::less<_CT>()(__x.get(), __y.get());
724 }
725
726 template<typename _Tp, typename _Dp>
727 inline bool
728 operator<(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
729 { return std::less<typename unique_ptr<_Tp, _Dp>::pointer>()(__x.get(),
730 nullptr); }
731
732 template<typename _Tp, typename _Dp>
733 inline bool
734 operator<(nullptr_t, const unique_ptr<_Tp, _Dp>& __x)
735 { return std::less<typename unique_ptr<_Tp, _Dp>::pointer>()(nullptr,
736 __x.get()); }
737
738 template<typename _Tp, typename _Dp,
739 typename _Up, typename _Ep>
740 inline bool
741 operator<=(const unique_ptr<_Tp, _Dp>& __x,
742 const unique_ptr<_Up, _Ep>& __y)
743 { return !(__y < __x); }
744
745 template<typename _Tp, typename _Dp>
746 inline bool
747 operator<=(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
748 { return !(nullptr < __x); }
749
750 template<typename _Tp, typename _Dp>
751 inline bool
752 operator<=(nullptr_t, const unique_ptr<_Tp, _Dp>& __x)
753 { return !(__x < nullptr); }
754
755 template<typename _Tp, typename _Dp,
756 typename _Up, typename _Ep>
757 inline bool
758 operator>(const unique_ptr<_Tp, _Dp>& __x,
759 const unique_ptr<_Up, _Ep>& __y)
760 { return (__y < __x); }
761
762 template<typename _Tp, typename _Dp>
763 inline bool
764 operator>(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
765 { return std::less<typename unique_ptr<_Tp, _Dp>::pointer>()(nullptr,
766 __x.get()); }
767
768 template<typename _Tp, typename _Dp>
769 inline bool
770 operator>(nullptr_t, const unique_ptr<_Tp, _Dp>& __x)
771 { return std::less<typename unique_ptr<_Tp, _Dp>::pointer>()(__x.get(),
772 nullptr); }
773
774 template<typename _Tp, typename _Dp,
775 typename _Up, typename _Ep>
776 inline bool
777 operator>=(const unique_ptr<_Tp, _Dp>& __x,
778 const unique_ptr<_Up, _Ep>& __y)
779 { return !(__x < __y); }
780
781 template<typename _Tp, typename _Dp>
782 inline bool
783 operator>=(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
784 { return !(__x < nullptr); }
785
786 template<typename _Tp, typename _Dp>
787 inline bool
788 operator>=(nullptr_t, const unique_ptr<_Tp, _Dp>& __x)
789 { return !(nullptr < __x); }
790
791 /// std::hash specialization for unique_ptr.
792 template<typename _Tp, typename _Dp>
793 struct hash<unique_ptr<_Tp, _Dp>>
794 : public __hash_base<size_t, unique_ptr<_Tp, _Dp>>,
795 private __poison_hash<typename unique_ptr<_Tp, _Dp>::pointer>
796 {
797 size_t
798 operator()(const unique_ptr<_Tp, _Dp>& __u) const noexcept
799 {
800 typedef unique_ptr<_Tp, _Dp> _UP;
801 return std::hash<typename _UP::pointer>()(__u.get());
802 }
803 };
804
805#if __cplusplus201103L > 201103L
806
807#define __cpp_lib_make_unique 201304
808
809 template<typename _Tp>
810 struct _MakeUniq
811 { typedef unique_ptr<_Tp> __single_object; };
812
813 template<typename _Tp>
814 struct _MakeUniq<_Tp[]>
815 { typedef unique_ptr<_Tp[]> __array; };
816
817 template<typename _Tp, size_t _Bound>
818 struct _MakeUniq<_Tp[_Bound]>
819 { struct __invalid_type { }; };
820
821 /// std::make_unique for single objects
822 template<typename _Tp, typename... _Args>
823 inline typename _MakeUniq<_Tp>::__single_object
824 make_unique(_Args&&... __args)
825 { return unique_ptr<_Tp>(new _Tp(std::forward<_Args>(__args)...)); }
826
827 /// std::make_unique for arrays of unknown bound
828 template<typename _Tp>
829 inline typename _MakeUniq<_Tp>::__array
830 make_unique(size_t __num)
831 { return unique_ptr<_Tp>(new remove_extent_t<_Tp>[__num]()); }
832
833 /// Disable std::make_unique for arrays of known bound
834 template<typename _Tp, typename... _Args>
835 inline typename _MakeUniq<_Tp>::__invalid_type
836 make_unique(_Args&&...) = delete;
837#endif
838
839 // @} group pointer_abstractions
840
841_GLIBCXX_END_NAMESPACE_VERSION
842} // namespace
843
844#endif /* _UNIQUE_PTR_H */