Bug Summary

File:include/llvm/Support/Error.h
Warning:line 201, column 5
Potential leak of memory pointed to by 'Payload._M_t._M_head_impl'

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

/build/llvm-toolchain-snapshot-8~svn350071/lib/Object/COFFModuleDefinition.cpp

1//===--- COFFModuleDefinition.cpp - Simple DEF parser ---------------------===//
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// Windows-specific.
11// A parser for the module-definition file (.def file).
12//
13// The format of module-definition files are described in this document:
14// https://msdn.microsoft.com/en-us/library/28d6s79h.aspx
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/Object/COFFModuleDefinition.h"
19#include "llvm/ADT/StringRef.h"
20#include "llvm/ADT/StringSwitch.h"
21#include "llvm/Object/COFF.h"
22#include "llvm/Object/COFFImportFile.h"
23#include "llvm/Object/Error.h"
24#include "llvm/Support/Error.h"
25#include "llvm/Support/Path.h"
26#include "llvm/Support/raw_ostream.h"
27
28using namespace llvm::COFF;
29using namespace llvm;
30
31namespace llvm {
32namespace object {
33
34enum Kind {
35 Unknown,
36 Eof,
37 Identifier,
38 Comma,
39 Equal,
40 EqualEqual,
41 KwBase,
42 KwConstant,
43 KwData,
44 KwExports,
45 KwHeapsize,
46 KwLibrary,
47 KwName,
48 KwNoname,
49 KwPrivate,
50 KwStacksize,
51 KwVersion,
52};
53
54struct Token {
55 explicit Token(Kind T = Unknown, StringRef S = "") : K(T), Value(S) {}
56 Kind K;
57 StringRef Value;
58};
59
60static bool isDecorated(StringRef Sym, bool MingwDef) {
61 // In def files, the symbols can either be listed decorated or undecorated.
62 //
63 // - For cdecl symbols, only the undecorated form is allowed.
64 // - For fastcall and vectorcall symbols, both fully decorated or
65 // undecorated forms can be present.
66 // - For stdcall symbols in non-MinGW environments, the decorated form is
67 // fully decorated with leading underscore and trailing stack argument
68 // size - like "_Func@0".
69 // - In MinGW def files, a decorated stdcall symbol does not include the
70 // leading underscore though, like "Func@0".
71
72 // This function controls whether a leading underscore should be added to
73 // the given symbol name or not. For MinGW, treat a stdcall symbol name such
74 // as "Func@0" as undecorated, i.e. a leading underscore must be added.
75 // For non-MinGW, look for '@' in the whole string and consider "_Func@0"
76 // as decorated, i.e. don't add any more leading underscores.
77 // We can't check for a leading underscore here, since function names
78 // themselves can start with an underscore, while a second one still needs
79 // to be added.
80 return Sym.startswith("@") || Sym.contains("@@") || Sym.startswith("?") ||
81 (!MingwDef && Sym.contains('@'));
82}
83
84static Error createError(const Twine &Err) {
85 return make_error<StringError>(StringRef(Err.str()),
10
Calling 'make_error<llvm::StringError, llvm::StringRef, llvm::object::object_error>'
86 object_error::parse_failed);
87}
88
89class Lexer {
90public:
91 Lexer(StringRef S) : Buf(S) {}
92
93 Token lex() {
94 Buf = Buf.trim();
95 if (Buf.empty())
96 return Token(Eof);
97
98 switch (Buf[0]) {
99 case '\0':
100 return Token(Eof);
101 case ';': {
102 size_t End = Buf.find('\n');
103 Buf = (End == Buf.npos) ? "" : Buf.drop_front(End);
104 return lex();
105 }
106 case '=':
107 Buf = Buf.drop_front();
108 if (Buf.startswith("=")) {
109 Buf = Buf.drop_front();
110 return Token(EqualEqual, "==");
111 }
112 return Token(Equal, "=");
113 case ',':
114 Buf = Buf.drop_front();
115 return Token(Comma, ",");
116 case '"': {
117 StringRef S;
118 std::tie(S, Buf) = Buf.substr(1).split('"');
119 return Token(Identifier, S);
120 }
121 default: {
122 size_t End = Buf.find_first_of("=,;\r\n \t\v");
123 StringRef Word = Buf.substr(0, End);
124 Kind K = llvm::StringSwitch<Kind>(Word)
125 .Case("BASE", KwBase)
126 .Case("CONSTANT", KwConstant)
127 .Case("DATA", KwData)
128 .Case("EXPORTS", KwExports)
129 .Case("HEAPSIZE", KwHeapsize)
130 .Case("LIBRARY", KwLibrary)
131 .Case("NAME", KwName)
132 .Case("NONAME", KwNoname)
133 .Case("PRIVATE", KwPrivate)
134 .Case("STACKSIZE", KwStacksize)
135 .Case("VERSION", KwVersion)
136 .Default(Identifier);
137 Buf = (End == Buf.npos) ? "" : Buf.drop_front(End);
138 return Token(K, Word);
139 }
140 }
141 }
142
143private:
144 StringRef Buf;
145};
146
147class Parser {
148public:
149 explicit Parser(StringRef S, MachineTypes M, bool B)
150 : Lex(S), Machine(M), MingwDef(B) {}
151
152 Expected<COFFModuleDefinition> parse() {
153 do {
154 if (Error Err = parseOne())
2
Calling 'Parser::parseOne'
155 return std::move(Err);
156 } while (Tok.K != Eof);
157 return Info;
158 }
159
160private:
161 void read() {
162 if (Stack.empty()) {
163 Tok = Lex.lex();
164 return;
165 }
166 Tok = Stack.back();
167 Stack.pop_back();
168 }
169
170 Error readAsInt(uint64_t *I) {
171 read();
172 if (Tok.K != Identifier || Tok.Value.getAsInteger(10, *I))
6
Assuming the condition is false
7
Assuming the condition is true
8
Taking true branch
173 return createError("integer expected");
9
Calling 'createError'
174 return Error::success();
175 }
176
177 Error expect(Kind Expected, StringRef Msg) {
178 read();
179 if (Tok.K != Expected)
180 return createError(Msg);
181 return Error::success();
182 }
183
184 void unget() { Stack.push_back(Tok); }
185
186 Error parseOne() {
187 read();
188 switch (Tok.K) {
3
Control jumps to 'case KwHeapsize:' at line 201
189 case Eof:
190 return Error::success();
191 case KwExports:
192 for (;;) {
193 read();
194 if (Tok.K != Identifier) {
195 unget();
196 return Error::success();
197 }
198 if (Error Err = parseExport())
199 return Err;
200 }
201 case KwHeapsize:
202 return parseNumbers(&Info.HeapReserve, &Info.HeapCommit);
4
Calling 'Parser::parseNumbers'
203 case KwStacksize:
204 return parseNumbers(&Info.StackReserve, &Info.StackCommit);
205 case KwLibrary:
206 case KwName: {
207 bool IsDll = Tok.K == KwLibrary; // Check before parseName.
208 std::string Name;
209 if (Error Err = parseName(&Name, &Info.ImageBase))
210 return Err;
211
212 Info.ImportName = Name;
213
214 // Set the output file, but don't override /out if it was already passed.
215 if (Info.OutputFile.empty()) {
216 Info.OutputFile = Name;
217 // Append the appropriate file extension if not already present.
218 if (!sys::path::has_extension(Name))
219 Info.OutputFile += IsDll ? ".dll" : ".exe";
220 }
221
222 return Error::success();
223 }
224 case KwVersion:
225 return parseVersion(&Info.MajorImageVersion, &Info.MinorImageVersion);
226 default:
227 return createError("unknown directive: " + Tok.Value);
228 }
229 }
230
231 Error parseExport() {
232 COFFShortExport E;
233 E.Name = Tok.Value;
234 read();
235 if (Tok.K == Equal) {
236 read();
237 if (Tok.K != Identifier)
238 return createError("identifier expected, but got " + Tok.Value);
239 E.ExtName = E.Name;
240 E.Name = Tok.Value;
241 } else {
242 unget();
243 }
244
245 if (Machine == IMAGE_FILE_MACHINE_I386) {
246 if (!isDecorated(E.Name, MingwDef))
247 E.Name = (std::string("_").append(E.Name));
248 if (!E.ExtName.empty() && !isDecorated(E.ExtName, MingwDef))
249 E.ExtName = (std::string("_").append(E.ExtName));
250 }
251
252 for (;;) {
253 read();
254 if (Tok.K == Identifier && Tok.Value[0] == '@') {
255 if (Tok.Value == "@") {
256 // "foo @ 10"
257 read();
258 Tok.Value.getAsInteger(10, E.Ordinal);
259 } else if (Tok.Value.drop_front().getAsInteger(10, E.Ordinal)) {
260 // "foo \n @bar" - Not an ordinal modifier at all, but the next
261 // export (fastcall decorated) - complete the current one.
262 unget();
263 Info.Exports.push_back(E);
264 return Error::success();
265 }
266 // "foo @10"
267 read();
268 if (Tok.K == KwNoname) {
269 E.Noname = true;
270 } else {
271 unget();
272 }
273 continue;
274 }
275 if (Tok.K == KwData) {
276 E.Data = true;
277 continue;
278 }
279 if (Tok.K == KwConstant) {
280 E.Constant = true;
281 continue;
282 }
283 if (Tok.K == KwPrivate) {
284 E.Private = true;
285 continue;
286 }
287 if (Tok.K == EqualEqual) {
288 read();
289 E.AliasTarget = Tok.Value;
290 if (Machine == IMAGE_FILE_MACHINE_I386 && !isDecorated(E.AliasTarget, MingwDef))
291 E.AliasTarget = std::string("_").append(E.AliasTarget);
292 continue;
293 }
294 unget();
295 Info.Exports.push_back(E);
296 return Error::success();
297 }
298 }
299
300 // HEAPSIZE/STACKSIZE reserve[,commit]
301 Error parseNumbers(uint64_t *Reserve, uint64_t *Commit) {
302 if (Error Err = readAsInt(Reserve))
5
Calling 'Parser::readAsInt'
303 return Err;
304 read();
305 if (Tok.K != Comma) {
306 unget();
307 Commit = nullptr;
308 return Error::success();
309 }
310 if (Error Err = readAsInt(Commit))
311 return Err;
312 return Error::success();
313 }
314
315 // NAME outputPath [BASE=address]
316 Error parseName(std::string *Out, uint64_t *Baseaddr) {
317 read();
318 if (Tok.K == Identifier) {
319 *Out = Tok.Value;
320 } else {
321 *Out = "";
322 unget();
323 return Error::success();
324 }
325 read();
326 if (Tok.K == KwBase) {
327 if (Error Err = expect(Equal, "'=' expected"))
328 return Err;
329 if (Error Err = readAsInt(Baseaddr))
330 return Err;
331 } else {
332 unget();
333 *Baseaddr = 0;
334 }
335 return Error::success();
336 }
337
338 // VERSION major[.minor]
339 Error parseVersion(uint32_t *Major, uint32_t *Minor) {
340 read();
341 if (Tok.K != Identifier)
342 return createError("identifier expected, but got " + Tok.Value);
343 StringRef V1, V2;
344 std::tie(V1, V2) = Tok.Value.split('.');
345 if (V1.getAsInteger(10, *Major))
346 return createError("integer expected, but got " + Tok.Value);
347 if (V2.empty())
348 *Minor = 0;
349 else if (V2.getAsInteger(10, *Minor))
350 return createError("integer expected, but got " + Tok.Value);
351 return Error::success();
352 }
353
354 Lexer Lex;
355 Token Tok;
356 std::vector<Token> Stack;
357 MachineTypes Machine;
358 COFFModuleDefinition Info;
359 bool MingwDef;
360};
361
362Expected<COFFModuleDefinition> parseCOFFModuleDefinition(MemoryBufferRef MB,
363 MachineTypes Machine,
364 bool MingwDef) {
365 return Parser(MB.getBuffer(), Machine, MingwDef).parse();
1
Calling 'Parser::parse'
366}
367
368} // namespace object
369} // namespace llvm

/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h

1//===- llvm/Support/Error.h - Recoverable error handling --------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines an API used to report recoverable errors.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_SUPPORT_ERROR_H
15#define LLVM_SUPPORT_ERROR_H
16
17#include "llvm-c/Error.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/StringExtras.h"
21#include "llvm/ADT/Twine.h"
22#include "llvm/Config/abi-breaking.h"
23#include "llvm/Support/AlignOf.h"
24#include "llvm/Support/Compiler.h"
25#include "llvm/Support/Debug.h"
26#include "llvm/Support/ErrorHandling.h"
27#include "llvm/Support/ErrorOr.h"
28#include "llvm/Support/Format.h"
29#include "llvm/Support/raw_ostream.h"
30#include <algorithm>
31#include <cassert>
32#include <cstdint>
33#include <cstdlib>
34#include <functional>
35#include <memory>
36#include <new>
37#include <string>
38#include <system_error>
39#include <type_traits>
40#include <utility>
41#include <vector>
42
43namespace llvm {
44
45class ErrorSuccess;
46
47/// Base class for error info classes. Do not extend this directly: Extend
48/// the ErrorInfo template subclass instead.
49class ErrorInfoBase {
50public:
51 virtual ~ErrorInfoBase() = default;
52
53 /// Print an error message to an output stream.
54 virtual void log(raw_ostream &OS) const = 0;
55
56 /// Return the error message as a string.
57 virtual std::string message() const {
58 std::string Msg;
59 raw_string_ostream OS(Msg);
60 log(OS);
61 return OS.str();
62 }
63
64 /// Convert this error to a std::error_code.
65 ///
66 /// This is a temporary crutch to enable interaction with code still
67 /// using std::error_code. It will be removed in the future.
68 virtual std::error_code convertToErrorCode() const = 0;
69
70 // Returns the class ID for this type.
71 static const void *classID() { return &ID; }
72
73 // Returns the class ID for the dynamic type of this ErrorInfoBase instance.
74 virtual const void *dynamicClassID() const = 0;
75
76 // Check whether this instance is a subclass of the class identified by
77 // ClassID.
78 virtual bool isA(const void *const ClassID) const {
79 return ClassID == classID();
80 }
81
82 // Check whether this instance is a subclass of ErrorInfoT.
83 template <typename ErrorInfoT> bool isA() const {
84 return isA(ErrorInfoT::classID());
85 }
86
87private:
88 virtual void anchor();
89
90 static char ID;
91};
92
93/// Lightweight error class with error context and mandatory checking.
94///
95/// Instances of this class wrap a ErrorInfoBase pointer. Failure states
96/// are represented by setting the pointer to a ErrorInfoBase subclass
97/// instance containing information describing the failure. Success is
98/// represented by a null pointer value.
99///
100/// Instances of Error also contains a 'Checked' flag, which must be set
101/// before the destructor is called, otherwise the destructor will trigger a
102/// runtime error. This enforces at runtime the requirement that all Error
103/// instances be checked or returned to the caller.
104///
105/// There are two ways to set the checked flag, depending on what state the
106/// Error instance is in. For Error instances indicating success, it
107/// is sufficient to invoke the boolean conversion operator. E.g.:
108///
109/// @code{.cpp}
110/// Error foo(<...>);
111///
112/// if (auto E = foo(<...>))
113/// return E; // <- Return E if it is in the error state.
114/// // We have verified that E was in the success state. It can now be safely
115/// // destroyed.
116/// @endcode
117///
118/// A success value *can not* be dropped. For example, just calling 'foo(<...>)'
119/// without testing the return value will raise a runtime error, even if foo
120/// returns success.
121///
122/// For Error instances representing failure, you must use either the
123/// handleErrors or handleAllErrors function with a typed handler. E.g.:
124///
125/// @code{.cpp}
126/// class MyErrorInfo : public ErrorInfo<MyErrorInfo> {
127/// // Custom error info.
128/// };
129///
130/// Error foo(<...>) { return make_error<MyErrorInfo>(...); }
131///
132/// auto E = foo(<...>); // <- foo returns failure with MyErrorInfo.
133/// auto NewE =
134/// handleErrors(E,
135/// [](const MyErrorInfo &M) {
136/// // Deal with the error.
137/// },
138/// [](std::unique_ptr<OtherError> M) -> Error {
139/// if (canHandle(*M)) {
140/// // handle error.
141/// return Error::success();
142/// }
143/// // Couldn't handle this error instance. Pass it up the stack.
144/// return Error(std::move(M));
145/// );
146/// // Note - we must check or return NewE in case any of the handlers
147/// // returned a new error.
148/// @endcode
149///
150/// The handleAllErrors function is identical to handleErrors, except
151/// that it has a void return type, and requires all errors to be handled and
152/// no new errors be returned. It prevents errors (assuming they can all be
153/// handled) from having to be bubbled all the way to the top-level.
154///
155/// *All* Error instances must be checked before destruction, even if
156/// they're moved-assigned or constructed from Success values that have already
157/// been checked. This enforces checking through all levels of the call stack.
158class LLVM_NODISCARD[[clang::warn_unused_result]] Error {
159 // Both ErrorList and FileError need to be able to yank ErrorInfoBase
160 // pointers out of this class to add to the error list.
161 friend class ErrorList;
162 friend class FileError;
163
164 // handleErrors needs to be able to set the Checked flag.
165 template <typename... HandlerTs>
166 friend Error handleErrors(Error E, HandlerTs &&... Handlers);
167
168 // Expected<T> needs to be able to steal the payload when constructed from an
169 // error.
170 template <typename T> friend class Expected;
171
172 // wrap needs to be able to steal the payload.
173 friend LLVMErrorRef wrap(Error);
174
175protected:
176 /// Create a success value. Prefer using 'Error::success()' for readability
177 Error() {
178 setPtr(nullptr);
179 setChecked(false);
180 }
181
182public:
183 /// Create a success value.
184 static ErrorSuccess success();
185
186 // Errors are not copy-constructable.
187 Error(const Error &Other) = delete;
188
189 /// Move-construct an error value. The newly constructed error is considered
190 /// unchecked, even if the source error had been checked. The original error
191 /// becomes a checked Success value, regardless of its original state.
192 Error(Error &&Other) {
193 setChecked(true);
194 *this = std::move(Other);
195 }
196
197 /// Create an error value. Prefer using the 'make_error' function, but
198 /// this constructor can be useful when "re-throwing" errors from handlers.
199 Error(std::unique_ptr<ErrorInfoBase> Payload) {
200 setPtr(Payload.release());
201 setChecked(false);
15
Potential leak of memory pointed to by 'Payload._M_t._M_head_impl'
202 }
203
204 // Errors are not copy-assignable.
205 Error &operator=(const Error &Other) = delete;
206
207 /// Move-assign an error value. The current error must represent success, you
208 /// you cannot overwrite an unhandled error. The current error is then
209 /// considered unchecked. The source error becomes a checked success value,
210 /// regardless of its original state.
211 Error &operator=(Error &&Other) {
212 // Don't allow overwriting of unchecked values.
213 assertIsChecked();
214 setPtr(Other.getPtr());
215
216 // This Error is unchecked, even if the source error was checked.
217 setChecked(false);
218
219 // Null out Other's payload and set its checked bit.
220 Other.setPtr(nullptr);
221 Other.setChecked(true);
222
223 return *this;
224 }
225
226 /// Destroy a Error. Fails with a call to abort() if the error is
227 /// unchecked.
228 ~Error() {
229 assertIsChecked();
230 delete getPtr();
231 }
232
233 /// Bool conversion. Returns true if this Error is in a failure state,
234 /// and false if it is in an accept state. If the error is in a Success state
235 /// it will be considered checked.
236 explicit operator bool() {
237 setChecked(getPtr() == nullptr);
238 return getPtr() != nullptr;
239 }
240
241 /// Check whether one error is a subclass of another.
242 template <typename ErrT> bool isA() const {
243 return getPtr() && getPtr()->isA(ErrT::classID());
244 }
245
246 /// Returns the dynamic class id of this error, or null if this is a success
247 /// value.
248 const void* dynamicClassID() const {
249 if (!getPtr())
250 return nullptr;
251 return getPtr()->dynamicClassID();
252 }
253
254private:
255#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
256 // assertIsChecked() happens very frequently, but under normal circumstances
257 // is supposed to be a no-op. So we want it to be inlined, but having a bunch
258 // of debug prints can cause the function to be too large for inlining. So
259 // it's important that we define this function out of line so that it can't be
260 // inlined.
261 LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn))
262 void fatalUncheckedError() const;
263#endif
264
265 void assertIsChecked() {
266#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
267 if (LLVM_UNLIKELY(!getChecked() || getPtr())__builtin_expect((bool)(!getChecked() || getPtr()), false))
268 fatalUncheckedError();
269#endif
270 }
271
272 ErrorInfoBase *getPtr() const {
273 return reinterpret_cast<ErrorInfoBase*>(
274 reinterpret_cast<uintptr_t>(Payload) &
275 ~static_cast<uintptr_t>(0x1));
276 }
277
278 void setPtr(ErrorInfoBase *EI) {
279#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
280 Payload = reinterpret_cast<ErrorInfoBase*>(
281 (reinterpret_cast<uintptr_t>(EI) &
282 ~static_cast<uintptr_t>(0x1)) |
283 (reinterpret_cast<uintptr_t>(Payload) & 0x1));
284#else
285 Payload = EI;
286#endif
287 }
288
289 bool getChecked() const {
290#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
291 return (reinterpret_cast<uintptr_t>(Payload) & 0x1) == 0;
292#else
293 return true;
294#endif
295 }
296
297 void setChecked(bool V) {
298 Payload = reinterpret_cast<ErrorInfoBase*>(
299 (reinterpret_cast<uintptr_t>(Payload) &
300 ~static_cast<uintptr_t>(0x1)) |
301 (V ? 0 : 1));
302 }
303
304 std::unique_ptr<ErrorInfoBase> takePayload() {
305 std::unique_ptr<ErrorInfoBase> Tmp(getPtr());
306 setPtr(nullptr);
307 setChecked(true);
308 return Tmp;
309 }
310
311 friend raw_ostream &operator<<(raw_ostream &OS, const Error &E) {
312 if (auto P = E.getPtr())
313 P->log(OS);
314 else
315 OS << "success";
316 return OS;
317 }
318
319 ErrorInfoBase *Payload = nullptr;
320};
321
322/// Subclass of Error for the sole purpose of identifying the success path in
323/// the type system. This allows to catch invalid conversion to Expected<T> at
324/// compile time.
325class ErrorSuccess final : public Error {};
326
327inline ErrorSuccess Error::success() { return ErrorSuccess(); }
328
329/// Make a Error instance representing failure using the given error info
330/// type.
331template <typename ErrT, typename... ArgTs> Error make_error(ArgTs &&... Args) {
332 return Error(llvm::make_unique<ErrT>(std::forward<ArgTs>(Args)...));
11
Calling 'make_unique<llvm::StringError, llvm::StringRef, llvm::object::object_error>'
13
Returned allocated memory
14
Calling constructor for 'Error'
333}
334
335/// Base class for user error types. Users should declare their error types
336/// like:
337///
338/// class MyError : public ErrorInfo<MyError> {
339/// ....
340/// };
341///
342/// This class provides an implementation of the ErrorInfoBase::kind
343/// method, which is used by the Error RTTI system.
344template <typename ThisErrT, typename ParentErrT = ErrorInfoBase>
345class ErrorInfo : public ParentErrT {
346public:
347 using ParentErrT::ParentErrT; // inherit constructors
348
349 static const void *classID() { return &ThisErrT::ID; }
350
351 const void *dynamicClassID() const override { return &ThisErrT::ID; }
352
353 bool isA(const void *const ClassID) const override {
354 return ClassID == classID() || ParentErrT::isA(ClassID);
355 }
356};
357
358/// Special ErrorInfo subclass representing a list of ErrorInfos.
359/// Instances of this class are constructed by joinError.
360class ErrorList final : public ErrorInfo<ErrorList> {
361 // handleErrors needs to be able to iterate the payload list of an
362 // ErrorList.
363 template <typename... HandlerTs>
364 friend Error handleErrors(Error E, HandlerTs &&... Handlers);
365
366 // joinErrors is implemented in terms of join.
367 friend Error joinErrors(Error, Error);
368
369public:
370 void log(raw_ostream &OS) const override {
371 OS << "Multiple errors:\n";
372 for (auto &ErrPayload : Payloads) {
373 ErrPayload->log(OS);
374 OS << "\n";
375 }
376 }
377
378 std::error_code convertToErrorCode() const override;
379
380 // Used by ErrorInfo::classID.
381 static char ID;
382
383private:
384 ErrorList(std::unique_ptr<ErrorInfoBase> Payload1,
385 std::unique_ptr<ErrorInfoBase> Payload2) {
386 assert(!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() &&((!Payload1->isA<ErrorList>() && !Payload2->
isA<ErrorList>() && "ErrorList constructor payloads should be singleton errors"
) ? static_cast<void> (0) : __assert_fail ("!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() && \"ErrorList constructor payloads should be singleton errors\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 387, __PRETTY_FUNCTION__))
387 "ErrorList constructor payloads should be singleton errors")((!Payload1->isA<ErrorList>() && !Payload2->
isA<ErrorList>() && "ErrorList constructor payloads should be singleton errors"
) ? static_cast<void> (0) : __assert_fail ("!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() && \"ErrorList constructor payloads should be singleton errors\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 387, __PRETTY_FUNCTION__))
;
388 Payloads.push_back(std::move(Payload1));
389 Payloads.push_back(std::move(Payload2));
390 }
391
392 static Error join(Error E1, Error E2) {
393 if (!E1)
394 return E2;
395 if (!E2)
396 return E1;
397 if (E1.isA<ErrorList>()) {
398 auto &E1List = static_cast<ErrorList &>(*E1.getPtr());
399 if (E2.isA<ErrorList>()) {
400 auto E2Payload = E2.takePayload();
401 auto &E2List = static_cast<ErrorList &>(*E2Payload);
402 for (auto &Payload : E2List.Payloads)
403 E1List.Payloads.push_back(std::move(Payload));
404 } else
405 E1List.Payloads.push_back(E2.takePayload());
406
407 return E1;
408 }
409 if (E2.isA<ErrorList>()) {
410 auto &E2List = static_cast<ErrorList &>(*E2.getPtr());
411 E2List.Payloads.insert(E2List.Payloads.begin(), E1.takePayload());
412 return E2;
413 }
414 return Error(std::unique_ptr<ErrorList>(
415 new ErrorList(E1.takePayload(), E2.takePayload())));
416 }
417
418 std::vector<std::unique_ptr<ErrorInfoBase>> Payloads;
419};
420
421/// Concatenate errors. The resulting Error is unchecked, and contains the
422/// ErrorInfo(s), if any, contained in E1, followed by the
423/// ErrorInfo(s), if any, contained in E2.
424inline Error joinErrors(Error E1, Error E2) {
425 return ErrorList::join(std::move(E1), std::move(E2));
426}
427
428/// Tagged union holding either a T or a Error.
429///
430/// This class parallels ErrorOr, but replaces error_code with Error. Since
431/// Error cannot be copied, this class replaces getError() with
432/// takeError(). It also adds an bool errorIsA<ErrT>() method for testing the
433/// error class type.
434template <class T> class LLVM_NODISCARD[[clang::warn_unused_result]] Expected {
435 template <class T1> friend class ExpectedAsOutParameter;
436 template <class OtherT> friend class Expected;
437
438 static const bool isRef = std::is_reference<T>::value;
439
440 using wrap = std::reference_wrapper<typename std::remove_reference<T>::type>;
441
442 using error_type = std::unique_ptr<ErrorInfoBase>;
443
444public:
445 using storage_type = typename std::conditional<isRef, wrap, T>::type;
446 using value_type = T;
447
448private:
449 using reference = typename std::remove_reference<T>::type &;
450 using const_reference = const typename std::remove_reference<T>::type &;
451 using pointer = typename std::remove_reference<T>::type *;
452 using const_pointer = const typename std::remove_reference<T>::type *;
453
454public:
455 /// Create an Expected<T> error value from the given Error.
456 Expected(Error Err)
457 : HasError(true)
458#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
459 // Expected is unchecked upon construction in Debug builds.
460 , Unchecked(true)
461#endif
462 {
463 assert(Err && "Cannot create Expected<T> from Error success value.")((Err && "Cannot create Expected<T> from Error success value."
) ? static_cast<void> (0) : __assert_fail ("Err && \"Cannot create Expected<T> from Error success value.\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 463, __PRETTY_FUNCTION__))
;
464 new (getErrorStorage()) error_type(Err.takePayload());
465 }
466
467 /// Forbid to convert from Error::success() implicitly, this avoids having
468 /// Expected<T> foo() { return Error::success(); } which compiles otherwise
469 /// but triggers the assertion above.
470 Expected(ErrorSuccess) = delete;
471
472 /// Create an Expected<T> success value from the given OtherT value, which
473 /// must be convertible to T.
474 template <typename OtherT>
475 Expected(OtherT &&Val,
476 typename std::enable_if<std::is_convertible<OtherT, T>::value>::type
477 * = nullptr)
478 : HasError(false)
479#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
480 // Expected is unchecked upon construction in Debug builds.
481 , Unchecked(true)
482#endif
483 {
484 new (getStorage()) storage_type(std::forward<OtherT>(Val));
485 }
486
487 /// Move construct an Expected<T> value.
488 Expected(Expected &&Other) { moveConstruct(std::move(Other)); }
489
490 /// Move construct an Expected<T> value from an Expected<OtherT>, where OtherT
491 /// must be convertible to T.
492 template <class OtherT>
493 Expected(Expected<OtherT> &&Other,
494 typename std::enable_if<std::is_convertible<OtherT, T>::value>::type
495 * = nullptr) {
496 moveConstruct(std::move(Other));
497 }
498
499 /// Move construct an Expected<T> value from an Expected<OtherT>, where OtherT
500 /// isn't convertible to T.
501 template <class OtherT>
502 explicit Expected(
503 Expected<OtherT> &&Other,
504 typename std::enable_if<!std::is_convertible<OtherT, T>::value>::type * =
505 nullptr) {
506 moveConstruct(std::move(Other));
507 }
508
509 /// Move-assign from another Expected<T>.
510 Expected &operator=(Expected &&Other) {
511 moveAssign(std::move(Other));
512 return *this;
513 }
514
515 /// Destroy an Expected<T>.
516 ~Expected() {
517 assertIsChecked();
518 if (!HasError)
519 getStorage()->~storage_type();
520 else
521 getErrorStorage()->~error_type();
522 }
523
524 /// Return false if there is an error.
525 explicit operator bool() {
526#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
527 Unchecked = HasError;
528#endif
529 return !HasError;
530 }
531
532 /// Returns a reference to the stored T value.
533 reference get() {
534 assertIsChecked();
535 return *getStorage();
536 }
537
538 /// Returns a const reference to the stored T value.
539 const_reference get() const {
540 assertIsChecked();
541 return const_cast<Expected<T> *>(this)->get();
542 }
543
544 /// Check that this Expected<T> is an error of type ErrT.
545 template <typename ErrT> bool errorIsA() const {
546 return HasError && (*getErrorStorage())->template isA<ErrT>();
547 }
548
549 /// Take ownership of the stored error.
550 /// After calling this the Expected<T> is in an indeterminate state that can
551 /// only be safely destructed. No further calls (beside the destructor) should
552 /// be made on the Expected<T> vaule.
553 Error takeError() {
554#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
555 Unchecked = false;
556#endif
557 return HasError ? Error(std::move(*getErrorStorage())) : Error::success();
558 }
559
560 /// Returns a pointer to the stored T value.
561 pointer operator->() {
562 assertIsChecked();
563 return toPointer(getStorage());
564 }
565
566 /// Returns a const pointer to the stored T value.
567 const_pointer operator->() const {
568 assertIsChecked();
569 return toPointer(getStorage());
570 }
571
572 /// Returns a reference to the stored T value.
573 reference operator*() {
574 assertIsChecked();
575 return *getStorage();
576 }
577
578 /// Returns a const reference to the stored T value.
579 const_reference operator*() const {
580 assertIsChecked();
581 return *getStorage();
582 }
583
584private:
585 template <class T1>
586 static bool compareThisIfSameType(const T1 &a, const T1 &b) {
587 return &a == &b;
588 }
589
590 template <class T1, class T2>
591 static bool compareThisIfSameType(const T1 &a, const T2 &b) {
592 return false;
593 }
594
595 template <class OtherT> void moveConstruct(Expected<OtherT> &&Other) {
596 HasError = Other.HasError;
597#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
598 Unchecked = true;
599 Other.Unchecked = false;
600#endif
601
602 if (!HasError)
603 new (getStorage()) storage_type(std::move(*Other.getStorage()));
604 else
605 new (getErrorStorage()) error_type(std::move(*Other.getErrorStorage()));
606 }
607
608 template <class OtherT> void moveAssign(Expected<OtherT> &&Other) {
609 assertIsChecked();
610
611 if (compareThisIfSameType(*this, Other))
612 return;
613
614 this->~Expected();
615 new (this) Expected(std::move(Other));
616 }
617
618 pointer toPointer(pointer Val) { return Val; }
619
620 const_pointer toPointer(const_pointer Val) const { return Val; }
621
622 pointer toPointer(wrap *Val) { return &Val->get(); }
623
624 const_pointer toPointer(const wrap *Val) const { return &Val->get(); }
625
626 storage_type *getStorage() {
627 assert(!HasError && "Cannot get value when an error exists!")((!HasError && "Cannot get value when an error exists!"
) ? static_cast<void> (0) : __assert_fail ("!HasError && \"Cannot get value when an error exists!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 627, __PRETTY_FUNCTION__))
;
628 return reinterpret_cast<storage_type *>(TStorage.buffer);
629 }
630
631 const storage_type *getStorage() const {
632 assert(!HasError && "Cannot get value when an error exists!")((!HasError && "Cannot get value when an error exists!"
) ? static_cast<void> (0) : __assert_fail ("!HasError && \"Cannot get value when an error exists!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 632, __PRETTY_FUNCTION__))
;
633 return reinterpret_cast<const storage_type *>(TStorage.buffer);
634 }
635
636 error_type *getErrorStorage() {
637 assert(HasError && "Cannot get error when a value exists!")((HasError && "Cannot get error when a value exists!"
) ? static_cast<void> (0) : __assert_fail ("HasError && \"Cannot get error when a value exists!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 637, __PRETTY_FUNCTION__))
;
638 return reinterpret_cast<error_type *>(ErrorStorage.buffer);
639 }
640
641 const error_type *getErrorStorage() const {
642 assert(HasError && "Cannot get error when a value exists!")((HasError && "Cannot get error when a value exists!"
) ? static_cast<void> (0) : __assert_fail ("HasError && \"Cannot get error when a value exists!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 642, __PRETTY_FUNCTION__))
;
643 return reinterpret_cast<const error_type *>(ErrorStorage.buffer);
644 }
645
646 // Used by ExpectedAsOutParameter to reset the checked flag.
647 void setUnchecked() {
648#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
649 Unchecked = true;
650#endif
651 }
652
653#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
654 LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn))
655 LLVM_ATTRIBUTE_NOINLINE__attribute__((noinline))
656 void fatalUncheckedExpected() const {
657 dbgs() << "Expected<T> must be checked before access or destruction.\n";
658 if (HasError) {
659 dbgs() << "Unchecked Expected<T> contained error:\n";
660 (*getErrorStorage())->log(dbgs());
661 } else
662 dbgs() << "Expected<T> value was in success state. (Note: Expected<T> "
663 "values in success mode must still be checked prior to being "
664 "destroyed).\n";
665 abort();
666 }
667#endif
668
669 void assertIsChecked() {
670#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
671 if (LLVM_UNLIKELY(Unchecked)__builtin_expect((bool)(Unchecked), false))
672 fatalUncheckedExpected();
673#endif
674 }
675
676 union {
677 AlignedCharArrayUnion<storage_type> TStorage;
678 AlignedCharArrayUnion<error_type> ErrorStorage;
679 };
680 bool HasError : 1;
681#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
682 bool Unchecked : 1;
683#endif
684};
685
686/// Report a serious error, calling any installed error handler. See
687/// ErrorHandling.h.
688LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void report_fatal_error(Error Err,
689 bool gen_crash_diag = true);
690
691/// Report a fatal error if Err is a failure value.
692///
693/// This function can be used to wrap calls to fallible functions ONLY when it
694/// is known that the Error will always be a success value. E.g.
695///
696/// @code{.cpp}
697/// // foo only attempts the fallible operation if DoFallibleOperation is
698/// // true. If DoFallibleOperation is false then foo always returns
699/// // Error::success().
700/// Error foo(bool DoFallibleOperation);
701///
702/// cantFail(foo(false));
703/// @endcode
704inline void cantFail(Error Err, const char *Msg = nullptr) {
705 if (Err) {
706 if (!Msg)
707 Msg = "Failure value returned from cantFail wrapped call";
708 llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 708)
;
709 }
710}
711
712/// Report a fatal error if ValOrErr is a failure value, otherwise unwraps and
713/// returns the contained value.
714///
715/// This function can be used to wrap calls to fallible functions ONLY when it
716/// is known that the Error will always be a success value. E.g.
717///
718/// @code{.cpp}
719/// // foo only attempts the fallible operation if DoFallibleOperation is
720/// // true. If DoFallibleOperation is false then foo always returns an int.
721/// Expected<int> foo(bool DoFallibleOperation);
722///
723/// int X = cantFail(foo(false));
724/// @endcode
725template <typename T>
726T cantFail(Expected<T> ValOrErr, const char *Msg = nullptr) {
727 if (ValOrErr)
728 return std::move(*ValOrErr);
729 else {
730 if (!Msg)
731 Msg = "Failure value returned from cantFail wrapped call";
732 llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 732)
;
733 }
734}
735
736/// Report a fatal error if ValOrErr is a failure value, otherwise unwraps and
737/// returns the contained reference.
738///
739/// This function can be used to wrap calls to fallible functions ONLY when it
740/// is known that the Error will always be a success value. E.g.
741///
742/// @code{.cpp}
743/// // foo only attempts the fallible operation if DoFallibleOperation is
744/// // true. If DoFallibleOperation is false then foo always returns a Bar&.
745/// Expected<Bar&> foo(bool DoFallibleOperation);
746///
747/// Bar &X = cantFail(foo(false));
748/// @endcode
749template <typename T>
750T& cantFail(Expected<T&> ValOrErr, const char *Msg = nullptr) {
751 if (ValOrErr)
752 return *ValOrErr;
753 else {
754 if (!Msg)
755 Msg = "Failure value returned from cantFail wrapped call";
756 llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 756)
;
757 }
758}
759
760/// Helper for testing applicability of, and applying, handlers for
761/// ErrorInfo types.
762template <typename HandlerT>
763class ErrorHandlerTraits
764 : public ErrorHandlerTraits<decltype(
765 &std::remove_reference<HandlerT>::type::operator())> {};
766
767// Specialization functions of the form 'Error (const ErrT&)'.
768template <typename ErrT> class ErrorHandlerTraits<Error (&)(ErrT &)> {
769public:
770 static bool appliesTo(const ErrorInfoBase &E) {
771 return E.template isA<ErrT>();
772 }
773
774 template <typename HandlerT>
775 static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
776 assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 776, __PRETTY_FUNCTION__))
;
777 return H(static_cast<ErrT &>(*E));
778 }
779};
780
781// Specialization functions of the form 'void (const ErrT&)'.
782template <typename ErrT> class ErrorHandlerTraits<void (&)(ErrT &)> {
783public:
784 static bool appliesTo(const ErrorInfoBase &E) {
785 return E.template isA<ErrT>();
786 }
787
788 template <typename HandlerT>
789 static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
790 assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 790, __PRETTY_FUNCTION__))
;
791 H(static_cast<ErrT &>(*E));
792 return Error::success();
793 }
794};
795
796/// Specialization for functions of the form 'Error (std::unique_ptr<ErrT>)'.
797template <typename ErrT>
798class ErrorHandlerTraits<Error (&)(std::unique_ptr<ErrT>)> {
799public:
800 static bool appliesTo(const ErrorInfoBase &E) {
801 return E.template isA<ErrT>();
802 }
803
804 template <typename HandlerT>
805 static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
806 assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 806, __PRETTY_FUNCTION__))
;
807 std::unique_ptr<ErrT> SubE(static_cast<ErrT *>(E.release()));
808 return H(std::move(SubE));
809 }
810};
811
812/// Specialization for functions of the form 'void (std::unique_ptr<ErrT>)'.
813template <typename ErrT>
814class ErrorHandlerTraits<void (&)(std::unique_ptr<ErrT>)> {
815public:
816 static bool appliesTo(const ErrorInfoBase &E) {
817 return E.template isA<ErrT>();
818 }
819
820 template <typename HandlerT>
821 static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
822 assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 822, __PRETTY_FUNCTION__))
;
823 std::unique_ptr<ErrT> SubE(static_cast<ErrT *>(E.release()));
824 H(std::move(SubE));
825 return Error::success();
826 }
827};
828
829// Specialization for member functions of the form 'RetT (const ErrT&)'.
830template <typename C, typename RetT, typename ErrT>
831class ErrorHandlerTraits<RetT (C::*)(ErrT &)>
832 : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
833
834// Specialization for member functions of the form 'RetT (const ErrT&) const'.
835template <typename C, typename RetT, typename ErrT>
836class ErrorHandlerTraits<RetT (C::*)(ErrT &) const>
837 : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
838
839// Specialization for member functions of the form 'RetT (const ErrT&)'.
840template <typename C, typename RetT, typename ErrT>
841class ErrorHandlerTraits<RetT (C::*)(const ErrT &)>
842 : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
843
844// Specialization for member functions of the form 'RetT (const ErrT&) const'.
845template <typename C, typename RetT, typename ErrT>
846class ErrorHandlerTraits<RetT (C::*)(const ErrT &) const>
847 : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
848
849/// Specialization for member functions of the form
850/// 'RetT (std::unique_ptr<ErrT>)'.
851template <typename C, typename RetT, typename ErrT>
852class ErrorHandlerTraits<RetT (C::*)(std::unique_ptr<ErrT>)>
853 : public ErrorHandlerTraits<RetT (&)(std::unique_ptr<ErrT>)> {};
854
855/// Specialization for member functions of the form
856/// 'RetT (std::unique_ptr<ErrT>) const'.
857template <typename C, typename RetT, typename ErrT>
858class ErrorHandlerTraits<RetT (C::*)(std::unique_ptr<ErrT>) const>
859 : public ErrorHandlerTraits<RetT (&)(std::unique_ptr<ErrT>)> {};
860
861inline Error handleErrorImpl(std::unique_ptr<ErrorInfoBase> Payload) {
862 return Error(std::move(Payload));
863}
864
865template <typename HandlerT, typename... HandlerTs>
866Error handleErrorImpl(std::unique_ptr<ErrorInfoBase> Payload,
867 HandlerT &&Handler, HandlerTs &&... Handlers) {
868 if (ErrorHandlerTraits<HandlerT>::appliesTo(*Payload))
869 return ErrorHandlerTraits<HandlerT>::apply(std::forward<HandlerT>(Handler),
870 std::move(Payload));
871 return handleErrorImpl(std::move(Payload),
872 std::forward<HandlerTs>(Handlers)...);
873}
874
875/// Pass the ErrorInfo(s) contained in E to their respective handlers. Any
876/// unhandled errors (or Errors returned by handlers) are re-concatenated and
877/// returned.
878/// Because this function returns an error, its result must also be checked
879/// or returned. If you intend to handle all errors use handleAllErrors
880/// (which returns void, and will abort() on unhandled errors) instead.
881template <typename... HandlerTs>
882Error handleErrors(Error E, HandlerTs &&... Hs) {
883 if (!E)
884 return Error::success();
885
886 std::unique_ptr<ErrorInfoBase> Payload = E.takePayload();
887
888 if (Payload->isA<ErrorList>()) {
889 ErrorList &List = static_cast<ErrorList &>(*Payload);
890 Error R;
891 for (auto &P : List.Payloads)
892 R = ErrorList::join(
893 std::move(R),
894 handleErrorImpl(std::move(P), std::forward<HandlerTs>(Hs)...));
895 return R;
896 }
897
898 return handleErrorImpl(std::move(Payload), std::forward<HandlerTs>(Hs)...);
899}
900
901/// Behaves the same as handleErrors, except that by contract all errors
902/// *must* be handled by the given handlers (i.e. there must be no remaining
903/// errors after running the handlers, or llvm_unreachable is called).
904template <typename... HandlerTs>
905void handleAllErrors(Error E, HandlerTs &&... Handlers) {
906 cantFail(handleErrors(std::move(E), std::forward<HandlerTs>(Handlers)...));
907}
908
909/// Check that E is a non-error, then drop it.
910/// If E is an error, llvm_unreachable will be called.
911inline void handleAllErrors(Error E) {
912 cantFail(std::move(E));
913}
914
915/// Handle any errors (if present) in an Expected<T>, then try a recovery path.
916///
917/// If the incoming value is a success value it is returned unmodified. If it
918/// is a failure value then it the contained error is passed to handleErrors.
919/// If handleErrors is able to handle the error then the RecoveryPath functor
920/// is called to supply the final result. If handleErrors is not able to
921/// handle all errors then the unhandled errors are returned.
922///
923/// This utility enables the follow pattern:
924///
925/// @code{.cpp}
926/// enum FooStrategy { Aggressive, Conservative };
927/// Expected<Foo> foo(FooStrategy S);
928///
929/// auto ResultOrErr =
930/// handleExpected(
931/// foo(Aggressive),
932/// []() { return foo(Conservative); },
933/// [](AggressiveStrategyError&) {
934/// // Implicitly conusme this - we'll recover by using a conservative
935/// // strategy.
936/// });
937///
938/// @endcode
939template <typename T, typename RecoveryFtor, typename... HandlerTs>
940Expected<T> handleExpected(Expected<T> ValOrErr, RecoveryFtor &&RecoveryPath,
941 HandlerTs &&... Handlers) {
942 if (ValOrErr)
943 return ValOrErr;
944
945 if (auto Err = handleErrors(ValOrErr.takeError(),
946 std::forward<HandlerTs>(Handlers)...))
947 return std::move(Err);
948
949 return RecoveryPath();
950}
951
952/// Log all errors (if any) in E to OS. If there are any errors, ErrorBanner
953/// will be printed before the first one is logged. A newline will be printed
954/// after each error.
955///
956/// This function is compatible with the helpers from Support/WithColor.h. You
957/// can pass any of them as the OS. Please consider using them instead of
958/// including 'error: ' in the ErrorBanner.
959///
960/// This is useful in the base level of your program to allow clean termination
961/// (allowing clean deallocation of resources, etc.), while reporting error
962/// information to the user.
963void logAllUnhandledErrors(Error E, raw_ostream &OS, Twine ErrorBanner = {});
964
965/// Write all error messages (if any) in E to a string. The newline character
966/// is used to separate error messages.
967inline std::string toString(Error E) {
968 SmallVector<std::string, 2> Errors;
969 handleAllErrors(std::move(E), [&Errors](const ErrorInfoBase &EI) {
970 Errors.push_back(EI.message());
971 });
972 return join(Errors.begin(), Errors.end(), "\n");
973}
974
975/// Consume a Error without doing anything. This method should be used
976/// only where an error can be considered a reasonable and expected return
977/// value.
978///
979/// Uses of this method are potentially indicative of design problems: If it's
980/// legitimate to do nothing while processing an "error", the error-producer
981/// might be more clearly refactored to return an Optional<T>.
982inline void consumeError(Error Err) {
983 handleAllErrors(std::move(Err), [](const ErrorInfoBase &) {});
984}
985
986/// Helper for converting an Error to a bool.
987///
988/// This method returns true if Err is in an error state, or false if it is
989/// in a success state. Puts Err in a checked state in both cases (unlike
990/// Error::operator bool(), which only does this for success states).
991inline bool errorToBool(Error Err) {
992 bool IsError = static_cast<bool>(Err);
993 if (IsError)
994 consumeError(std::move(Err));
995 return IsError;
996}
997
998/// Helper for Errors used as out-parameters.
999///
1000/// This helper is for use with the Error-as-out-parameter idiom, where an error
1001/// is passed to a function or method by reference, rather than being returned.
1002/// In such cases it is helpful to set the checked bit on entry to the function
1003/// so that the error can be written to (unchecked Errors abort on assignment)
1004/// and clear the checked bit on exit so that clients cannot accidentally forget
1005/// to check the result. This helper performs these actions automatically using
1006/// RAII:
1007///
1008/// @code{.cpp}
1009/// Result foo(Error &Err) {
1010/// ErrorAsOutParameter ErrAsOutParam(&Err); // 'Checked' flag set
1011/// // <body of foo>
1012/// // <- 'Checked' flag auto-cleared when ErrAsOutParam is destructed.
1013/// }
1014/// @endcode
1015///
1016/// ErrorAsOutParameter takes an Error* rather than Error& so that it can be
1017/// used with optional Errors (Error pointers that are allowed to be null). If
1018/// ErrorAsOutParameter took an Error reference, an instance would have to be
1019/// created inside every condition that verified that Error was non-null. By
1020/// taking an Error pointer we can just create one instance at the top of the
1021/// function.
1022class ErrorAsOutParameter {
1023public:
1024 ErrorAsOutParameter(Error *Err) : Err(Err) {
1025 // Raise the checked bit if Err is success.
1026 if (Err)
1027 (void)!!*Err;
1028 }
1029
1030 ~ErrorAsOutParameter() {
1031 // Clear the checked bit.
1032 if (Err && !*Err)
1033 *Err = Error::success();
1034 }
1035
1036private:
1037 Error *Err;
1038};
1039
1040/// Helper for Expected<T>s used as out-parameters.
1041///
1042/// See ErrorAsOutParameter.
1043template <typename T>
1044class ExpectedAsOutParameter {
1045public:
1046 ExpectedAsOutParameter(Expected<T> *ValOrErr)
1047 : ValOrErr(ValOrErr) {
1048 if (ValOrErr)
1049 (void)!!*ValOrErr;
1050 }
1051
1052 ~ExpectedAsOutParameter() {
1053 if (ValOrErr)
1054 ValOrErr->setUnchecked();
1055 }
1056
1057private:
1058 Expected<T> *ValOrErr;
1059};
1060
1061/// This class wraps a std::error_code in a Error.
1062///
1063/// This is useful if you're writing an interface that returns a Error
1064/// (or Expected) and you want to call code that still returns
1065/// std::error_codes.
1066class ECError : public ErrorInfo<ECError> {
1067 friend Error errorCodeToError(std::error_code);
1068
1069public:
1070 void setErrorCode(std::error_code EC) { this->EC = EC; }
1071 std::error_code convertToErrorCode() const override { return EC; }
1072 void log(raw_ostream &OS) const override { OS << EC.message(); }
1073
1074 // Used by ErrorInfo::classID.
1075 static char ID;
1076
1077protected:
1078 ECError() = default;
1079 ECError(std::error_code EC) : EC(EC) {}
1080
1081 std::error_code EC;
1082};
1083
1084/// The value returned by this function can be returned from convertToErrorCode
1085/// for Error values where no sensible translation to std::error_code exists.
1086/// It should only be used in this situation, and should never be used where a
1087/// sensible conversion to std::error_code is available, as attempts to convert
1088/// to/from this error will result in a fatal error. (i.e. it is a programmatic
1089///error to try to convert such a value).
1090std::error_code inconvertibleErrorCode();
1091
1092/// Helper for converting an std::error_code to a Error.
1093Error errorCodeToError(std::error_code EC);
1094
1095/// Helper for converting an ECError to a std::error_code.
1096///
1097/// This method requires that Err be Error() or an ECError, otherwise it
1098/// will trigger a call to abort().
1099std::error_code errorToErrorCode(Error Err);
1100
1101/// Convert an ErrorOr<T> to an Expected<T>.
1102template <typename T> Expected<T> errorOrToExpected(ErrorOr<T> &&EO) {
1103 if (auto EC = EO.getError())
1104 return errorCodeToError(EC);
1105 return std::move(*EO);
1106}
1107
1108/// Convert an Expected<T> to an ErrorOr<T>.
1109template <typename T> ErrorOr<T> expectedToErrorOr(Expected<T> &&E) {
1110 if (auto Err = E.takeError())
1111 return errorToErrorCode(std::move(Err));
1112 return std::move(*E);
1113}
1114
1115/// This class wraps a string in an Error.
1116///
1117/// StringError is useful in cases where the client is not expected to be able
1118/// to consume the specific error message programmatically (for example, if the
1119/// error message is to be presented to the user).
1120///
1121/// StringError can also be used when additional information is to be printed
1122/// along with a error_code message. Depending on the constructor called, this
1123/// class can either display:
1124/// 1. the error_code message (ECError behavior)
1125/// 2. a string
1126/// 3. the error_code message and a string
1127///
1128/// These behaviors are useful when subtyping is required; for example, when a
1129/// specific library needs an explicit error type. In the example below,
1130/// PDBError is derived from StringError:
1131///
1132/// @code{.cpp}
1133/// Expected<int> foo() {
1134/// return llvm::make_error<PDBError>(pdb_error_code::dia_failed_loading,
1135/// "Additional information");
1136/// }
1137/// @endcode
1138///
1139class StringError : public ErrorInfo<StringError> {
1140public:
1141 static char ID;
1142
1143 // Prints EC + S and converts to EC
1144 StringError(std::error_code EC, const Twine &S = Twine());
1145
1146 // Prints S and converts to EC
1147 StringError(const Twine &S, std::error_code EC);
1148
1149 void log(raw_ostream &OS) const override;
1150 std::error_code convertToErrorCode() const override;
1151
1152 const std::string &getMessage() const { return Msg; }
1153
1154private:
1155 std::string Msg;
1156 std::error_code EC;
1157 const bool PrintMsgOnly = false;
1158};
1159
1160/// Create formatted StringError object.
1161template <typename... Ts>
1162Error createStringError(std::error_code EC, char const *Fmt,
1163 const Ts &... Vals) {
1164 std::string Buffer;
1165 raw_string_ostream Stream(Buffer);
1166 Stream << format(Fmt, Vals...);
1167 return make_error<StringError>(Stream.str(), EC);
1168}
1169
1170Error createStringError(std::error_code EC, char const *Msg);
1171
1172/// This class wraps a filename and another Error.
1173///
1174/// In some cases, an error needs to live along a 'source' name, in order to
1175/// show more detailed information to the user.
1176class FileError final : public ErrorInfo<FileError> {
1177
1178 friend Error createFileError(std::string, Error);
1179
1180public:
1181 void log(raw_ostream &OS) const override {
1182 assert(Err && !FileName.empty() && "Trying to log after takeError().")((Err && !FileName.empty() && "Trying to log after takeError()."
) ? static_cast<void> (0) : __assert_fail ("Err && !FileName.empty() && \"Trying to log after takeError().\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 1182, __PRETTY_FUNCTION__))
;
1183 OS << "'" << FileName << "': ";
1184 Err->log(OS);
1185 }
1186
1187 Error takeError() { return Error(std::move(Err)); }
1188
1189 std::error_code convertToErrorCode() const override;
1190
1191 // Used by ErrorInfo::classID.
1192 static char ID;
1193
1194private:
1195 FileError(std::string F, std::unique_ptr<ErrorInfoBase> E) {
1196 assert(E && "Cannot create FileError from Error success value.")((E && "Cannot create FileError from Error success value."
) ? static_cast<void> (0) : __assert_fail ("E && \"Cannot create FileError from Error success value.\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 1196, __PRETTY_FUNCTION__))
;
1197 assert(!F.empty() &&((!F.empty() && "The file name provided to FileError must not be empty."
) ? static_cast<void> (0) : __assert_fail ("!F.empty() && \"The file name provided to FileError must not be empty.\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 1198, __PRETTY_FUNCTION__))
1198 "The file name provided to FileError must not be empty.")((!F.empty() && "The file name provided to FileError must not be empty."
) ? static_cast<void> (0) : __assert_fail ("!F.empty() && \"The file name provided to FileError must not be empty.\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Support/Error.h"
, 1198, __PRETTY_FUNCTION__))
;
1199 FileName = F;
1200 Err = std::move(E);
1201 }
1202
1203 static Error build(std::string F, Error E) {
1204 return Error(std::unique_ptr<FileError>(new FileError(F, E.takePayload())));
1205 }
1206
1207 std::string FileName;
1208 std::unique_ptr<ErrorInfoBase> Err;
1209};
1210
1211/// Concatenate a source file path and/or name with an Error. The resulting
1212/// Error is unchecked.
1213inline Error createFileError(std::string F, Error E) {
1214 return FileError::build(F, std::move(E));
1215}
1216
1217Error createFileError(std::string F, ErrorSuccess) = delete;
1218
1219/// Helper for check-and-exit error handling.
1220///
1221/// For tool use only. NOT FOR USE IN LIBRARY CODE.
1222///
1223class ExitOnError {
1224public:
1225 /// Create an error on exit helper.
1226 ExitOnError(std::string Banner = "", int DefaultErrorExitCode = 1)
1227 : Banner(std::move(Banner)),
1228 GetExitCode([=](const Error &) { return DefaultErrorExitCode; }) {}
1229
1230 /// Set the banner string for any errors caught by operator().
1231 void setBanner(std::string Banner) { this->Banner = std::move(Banner); }
1232
1233 /// Set the exit-code mapper function.
1234 void setExitCodeMapper(std::function<int(const Error &)> GetExitCode) {
1235 this->GetExitCode = std::move(GetExitCode);
1236 }
1237
1238 /// Check Err. If it's in a failure state log the error(s) and exit.
1239 void operator()(Error Err) const { checkError(std::move(Err)); }
1240
1241 /// Check E. If it's in a success state then return the contained value. If
1242 /// it's in a failure state log the error(s) and exit.
1243 template <typename T> T operator()(Expected<T> &&E) const {
1244 checkError(E.takeError());
1245 return std::move(*E);
1246 }
1247
1248 /// Check E. If it's in a success state then return the contained reference. If
1249 /// it's in a failure state log the error(s) and exit.
1250 template <typename T> T& operator()(Expected<T&> &&E) const {
1251 checkError(E.takeError());
1252 return *E;
1253 }
1254
1255private:
1256 void checkError(Error Err) const {
1257 if (Err) {
1258 int ExitCode = GetExitCode(Err);
1259 logAllUnhandledErrors(std::move(Err), errs(), Banner);
1260 exit(ExitCode);
1261 }
1262 }
1263
1264 std::string Banner;
1265 std::function<int(const Error &)> GetExitCode;
1266};
1267
1268/// Conversion from Error to LLVMErrorRef for C error bindings.
1269inline LLVMErrorRef wrap(Error Err) {
1270 return reinterpret_cast<LLVMErrorRef>(Err.takePayload().release());
1271}
1272
1273/// Conversion from LLVMErrorRef to Error for C error bindings.
1274inline Error unwrap(LLVMErrorRef ErrRef) {
1275 return Error(std::unique_ptr<ErrorInfoBase>(
1276 reinterpret_cast<ErrorInfoBase *>(ErrRef)));
1277}
1278
1279} // end namespace llvm
1280
1281#endif // LLVM_SUPPORT_ERROR_H

/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/STLExtras.h

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