Bug Summary

File:include/llvm/Support/Error.h
Warning:line 200, 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-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Object -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Object -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Object -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -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-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Object/COFFModuleDefinition.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn362543/lib/Object/COFFModuleDefinition.cpp

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

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h

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

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

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