Bug Summary

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

/build/llvm-toolchain-snapshot-7~svn326551/tools/llvm-lto2/llvm-lto2.cpp

1//===-- llvm-lto2: test harness for the resolution-based LTO interface ----===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This program takes in a list of bitcode files, links them and performs
11// link-time optimization according to the provided symbol resolutions using the
12// resolution-based LTO interface, and outputs one or more object files.
13//
14// This program is intended to eventually replace llvm-lto which uses the legacy
15// LTO interface.
16//
17//===----------------------------------------------------------------------===//
18
19#include "llvm/Bitcode/BitcodeReader.h"
20#include "llvm/CodeGen/CommandFlags.def"
21#include "llvm/IR/DiagnosticPrinter.h"
22#include "llvm/LTO/Caching.h"
23#include "llvm/LTO/LTO.h"
24#include "llvm/Support/CommandLine.h"
25#include "llvm/Support/FileSystem.h"
26#include "llvm/Support/TargetSelect.h"
27#include "llvm/Support/Threading.h"
28
29using namespace llvm;
30using namespace lto;
31
32static cl::opt<char>
33 OptLevel("O", cl::desc("Optimization level. [-O0, -O1, -O2, or -O3] "
34 "(default = '-O2')"),
35 cl::Prefix, cl::ZeroOrMore, cl::init('2'));
36
37static cl::opt<char> CGOptLevel(
38 "cg-opt-level",
39 cl::desc("Codegen optimization level (0, 1, 2 or 3, default = '2')"),
40 cl::init('2'));
41
42static cl::list<std::string> InputFilenames(cl::Positional, cl::OneOrMore,
43 cl::desc("<input bitcode files>"));
44
45static cl::opt<std::string> OutputFilename("o", cl::Required,
46 cl::desc("Output filename"),
47 cl::value_desc("filename"));
48
49static cl::opt<std::string> CacheDir("cache-dir", cl::desc("Cache Directory"),
50 cl::value_desc("directory"));
51
52static cl::opt<std::string> OptPipeline("opt-pipeline",
53 cl::desc("Optimizer Pipeline"),
54 cl::value_desc("pipeline"));
55
56static cl::opt<std::string> AAPipeline("aa-pipeline",
57 cl::desc("Alias Analysis Pipeline"),
58 cl::value_desc("aapipeline"));
59
60static cl::opt<bool> SaveTemps("save-temps", cl::desc("Save temporary files"));
61
62static cl::opt<bool>
63 ThinLTODistributedIndexes("thinlto-distributed-indexes", cl::init(false),
64 cl::desc("Write out individual index and "
65 "import files for the "
66 "distributed backend case"));
67
68static cl::opt<int> Threads("thinlto-threads",
69 cl::init(llvm::heavyweight_hardware_concurrency()));
70
71static cl::list<std::string> SymbolResolutions(
72 "r",
73 cl::desc("Specify a symbol resolution: filename,symbolname,resolution\n"
74 "where \"resolution\" is a sequence (which may be empty) of the\n"
75 "following characters:\n"
76 " p - prevailing: the linker has chosen this definition of the\n"
77 " symbol\n"
78 " l - local: the definition of this symbol is unpreemptable at\n"
79 " runtime and is known to be in this linkage unit\n"
80 " x - externally visible: the definition of this symbol is\n"
81 " visible outside of the LTO unit\n"
82 "A resolution for each symbol must be specified."),
83 cl::ZeroOrMore);
84
85static cl::opt<std::string> OverrideTriple(
86 "override-triple",
87 cl::desc("Replace target triples in input files with this triple"));
88
89static cl::opt<std::string> DefaultTriple(
90 "default-triple",
91 cl::desc(
92 "Replace unspecified target triples in input files with this triple"));
93
94static cl::opt<std::string>
95 OptRemarksOutput("pass-remarks-output",
96 cl::desc("YAML output file for optimization remarks"));
97
98static cl::opt<bool> OptRemarksWithHotness(
99 "pass-remarks-with-hotness",
100 cl::desc("Whether to include hotness informations in the remarks.\n"
101 "Has effect only if -pass-remarks-output is specified."));
102
103static cl::opt<std::string>
104 SamplePGOFile("lto-sample-profile-file",
105 cl::desc("Specify a SamplePGO profile file"));
106
107static cl::opt<bool>
108 UseNewPM("use-new-pm",
109 cl::desc("Run LTO passes using the new pass manager"),
110 cl::init(false), cl::Hidden);
111
112static cl::opt<bool>
113 DebugPassManager("debug-pass-manager", cl::init(false), cl::Hidden,
114 cl::desc("Print pass management debugging information"));
115
116static void check(Error E, std::string Msg) {
117 if (!E)
118 return;
119 handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {
120 errs() << "llvm-lto2: " << Msg << ": " << EIB.message().c_str() << '\n';
121 });
122 exit(1);
123}
124
125template <typename T> static T check(Expected<T> E, std::string Msg) {
126 if (E)
127 return std::move(*E);
128 check(E.takeError(), Msg);
129 return T();
130}
131
132static void check(std::error_code EC, std::string Msg) {
133 check(errorCodeToError(EC), Msg);
134}
135
136template <typename T> static T check(ErrorOr<T> E, std::string Msg) {
137 if (E)
138 return std::move(*E);
139 check(E.getError(), Msg);
140 return T();
141}
142
143static int usage() {
144 errs() << "Available subcommands: dump-symtab run\n";
145 return 1;
146}
147
148static int run(int argc, char **argv) {
149 cl::ParseCommandLineOptions(argc, argv, "Resolution-based LTO test harness");
150
151 // FIXME: Workaround PR30396 which means that a symbol can appear
152 // more than once if it is defined in module-level assembly and
153 // has a GV declaration. We allow (file, symbol) pairs to have multiple
154 // resolutions and apply them in the order observed.
155 std::map<std::pair<std::string, std::string>, std::list<SymbolResolution>>
156 CommandLineResolutions;
157 for (std::string R : SymbolResolutions) {
158 StringRef Rest = R;
159 StringRef FileName, SymbolName;
160 std::tie(FileName, Rest) = Rest.split(',');
161 if (Rest.empty()) {
162 llvm::errs() << "invalid resolution: " << R << '\n';
163 return 1;
164 }
165 std::tie(SymbolName, Rest) = Rest.split(',');
166 SymbolResolution Res;
167 for (char C : Rest) {
168 if (C == 'p')
169 Res.Prevailing = true;
170 else if (C == 'l')
171 Res.FinalDefinitionInLinkageUnit = true;
172 else if (C == 'x')
173 Res.VisibleToRegularObj = true;
174 else if (C == 'r')
175 Res.LinkerRedefined = true;
176 else {
177 llvm::errs() << "invalid character " << C << " in resolution: " << R
178 << '\n';
179 return 1;
180 }
181 }
182 CommandLineResolutions[{FileName, SymbolName}].push_back(Res);
183 }
184
185 std::vector<std::unique_ptr<MemoryBuffer>> MBs;
186
187 Config Conf;
188 Conf.DiagHandler = [](const DiagnosticInfo &DI) {
189 DiagnosticPrinterRawOStream DP(errs());
190 DI.print(DP);
191 errs() << '\n';
192 exit(1);
193 };
194
195 Conf.CPU = MCPU;
196 Conf.Options = InitTargetOptionsFromCodeGenFlags();
197 Conf.MAttrs = MAttrs;
198 if (auto RM = getRelocModel())
199 Conf.RelocModel = *RM;
200 Conf.CodeModel = getCodeModel();
201
202 Conf.DebugPassManager = DebugPassManager;
203
204 if (SaveTemps)
205 check(Conf.addSaveTemps(OutputFilename + "."),
206 "Config::addSaveTemps failed");
207
208 // Optimization remarks.
209 Conf.RemarksFilename = OptRemarksOutput;
210 Conf.RemarksWithHotness = OptRemarksWithHotness;
211
212 Conf.SampleProfile = SamplePGOFile;
213
214 // Run a custom pipeline, if asked for.
215 Conf.OptPipeline = OptPipeline;
216 Conf.AAPipeline = AAPipeline;
217
218 Conf.OptLevel = OptLevel - '0';
219 Conf.UseNewPM = UseNewPM;
220 switch (CGOptLevel) {
221 case '0':
222 Conf.CGOptLevel = CodeGenOpt::None;
223 break;
224 case '1':
225 Conf.CGOptLevel = CodeGenOpt::Less;
226 break;
227 case '2':
228 Conf.CGOptLevel = CodeGenOpt::Default;
229 break;
230 case '3':
231 Conf.CGOptLevel = CodeGenOpt::Aggressive;
232 break;
233 default:
234 llvm::errs() << "invalid cg optimization level: " << CGOptLevel << '\n';
235 return 1;
236 }
237
238 if (FileType.getNumOccurrences())
239 Conf.CGFileType = FileType;
240
241 Conf.OverrideTriple = OverrideTriple;
242 Conf.DefaultTriple = DefaultTriple;
243
244 ThinBackend Backend;
245 if (ThinLTODistributedIndexes)
246 Backend = createWriteIndexesThinBackend(/* OldPrefix */ "",
247 /* NewPrefix */ "",
248 /* ShouldEmitImportsFiles */ true,
249 /* LinkedObjectsFile */ nullptr,
250 /* OnWrite */ {});
251 else
252 Backend = createInProcessThinBackend(Threads);
253 LTO Lto(std::move(Conf), std::move(Backend));
254
255 bool HasErrors = false;
256 for (std::string F : InputFilenames) {
257 std::unique_ptr<MemoryBuffer> MB = check(MemoryBuffer::getFile(F), F);
258 std::unique_ptr<InputFile> Input =
259 check(InputFile::create(MB->getMemBufferRef()), F);
260
261 std::vector<SymbolResolution> Res;
262 for (const InputFile::Symbol &Sym : Input->symbols()) {
263 auto I = CommandLineResolutions.find({F, Sym.getName()});
264 if (I == CommandLineResolutions.end()) {
265 llvm::errs() << argv[0] << ": missing symbol resolution for " << F
266 << ',' << Sym.getName() << '\n';
267 HasErrors = true;
268 } else {
269 Res.push_back(I->second.front());
270 I->second.pop_front();
271 if (I->second.empty())
272 CommandLineResolutions.erase(I);
273 }
274 }
275
276 if (HasErrors)
277 continue;
278
279 MBs.push_back(std::move(MB));
280 check(Lto.add(std::move(Input), Res), F);
281 }
282
283 if (!CommandLineResolutions.empty()) {
284 HasErrors = true;
285 for (auto UnusedRes : CommandLineResolutions)
286 llvm::errs() << argv[0] << ": unused symbol resolution for "
287 << UnusedRes.first.first << ',' << UnusedRes.first.second
288 << '\n';
289 }
290 if (HasErrors)
291 return 1;
292
293 auto AddStream =
294 [&](size_t Task) -> std::unique_ptr<lto::NativeObjectStream> {
295 std::string Path = OutputFilename + "." + utostr(Task);
296
297 std::error_code EC;
298 auto S = llvm::make_unique<raw_fd_ostream>(Path, EC, sys::fs::F_None);
299 check(EC, Path);
300 return llvm::make_unique<lto::NativeObjectStream>(std::move(S));
2
Calling 'make_unique'
4
Returned allocated memory
301 };
302
303 auto AddBuffer = [&](size_t Task, std::unique_ptr<MemoryBuffer> MB) {
304 *AddStream(Task)->OS << MB->getBuffer();
1
Calling 'operator()'
5
Returned allocated memory
6
Potential leak of memory pointed to by field '_M_head_impl'
305 };
306
307 NativeObjectCache Cache;
308 if (!CacheDir.empty())
309 Cache = check(localCache(CacheDir, AddBuffer), "failed to create cache");
310
311 check(Lto.run(AddStream, Cache), "LTO::run failed");
312 return 0;
313}
314
315static int dumpSymtab(int argc, char **argv) {
316 for (StringRef F : make_range(argv + 1, argv + argc)) {
317 std::unique_ptr<MemoryBuffer> MB = check(MemoryBuffer::getFile(F), F);
318 BitcodeFileContents BFC = check(getBitcodeFileContents(*MB), F);
319
320 if (BFC.Symtab.size() >= sizeof(irsymtab::storage::Header)) {
321 auto *Hdr = reinterpret_cast<const irsymtab::storage::Header *>(
322 BFC.Symtab.data());
323 outs() << "version: " << Hdr->Version << '\n';
324 if (Hdr->Version == irsymtab::storage::Header::kCurrentVersion)
325 outs() << "producer: " << Hdr->Producer.get(BFC.StrtabForSymtab)
326 << '\n';
327 }
328
329 std::unique_ptr<InputFile> Input =
330 check(InputFile::create(MB->getMemBufferRef()), F);
331
332 outs() << "target triple: " << Input->getTargetTriple() << '\n';
333 Triple TT(Input->getTargetTriple());
334
335 outs() << "source filename: " << Input->getSourceFileName() << '\n';
336
337 if (TT.isOSBinFormatCOFF())
338 outs() << "linker opts: " << Input->getCOFFLinkerOpts() << '\n';
339
340 std::vector<StringRef> ComdatTable = Input->getComdatTable();
341 for (const InputFile::Symbol &Sym : Input->symbols()) {
342 switch (Sym.getVisibility()) {
343 case GlobalValue::HiddenVisibility:
344 outs() << 'H';
345 break;
346 case GlobalValue::ProtectedVisibility:
347 outs() << 'P';
348 break;
349 case GlobalValue::DefaultVisibility:
350 outs() << 'D';
351 break;
352 }
353
354 auto PrintBool = [&](char C, bool B) { outs() << (B ? C : '-'); };
355 PrintBool('U', Sym.isUndefined());
356 PrintBool('C', Sym.isCommon());
357 PrintBool('W', Sym.isWeak());
358 PrintBool('I', Sym.isIndirect());
359 PrintBool('O', Sym.canBeOmittedFromSymbolTable());
360 PrintBool('T', Sym.isTLS());
361 PrintBool('X', Sym.isExecutable());
362 outs() << ' ' << Sym.getName() << '\n';
363
364 if (Sym.isCommon())
365 outs() << " size " << Sym.getCommonSize() << " align "
366 << Sym.getCommonAlignment() << '\n';
367
368 int Comdat = Sym.getComdatIndex();
369 if (Comdat != -1)
370 outs() << " comdat " << ComdatTable[Comdat] << '\n';
371
372 if (TT.isOSBinFormatCOFF() && Sym.isWeak() && Sym.isIndirect())
373 outs() << " fallback " << Sym.getCOFFWeakExternalFallback() << '\n';
374
375 if (!Sym.getSectionName().empty())
376 outs() << " section " << Sym.getSectionName() << "\n";
377 }
378
379 outs() << '\n';
380 }
381
382 return 0;
383}
384
385int main(int argc, char **argv) {
386 InitializeAllTargets();
387 InitializeAllTargetMCs();
388 InitializeAllAsmPrinters();
389 InitializeAllAsmParsers();
390
391 // FIXME: This should use llvm::cl subcommands, but it isn't currently
392 // possible to pass an argument not associated with a subcommand to a
393 // subcommand (e.g. -use-new-pm).
394 if (argc < 2)
395 return usage();
396
397 StringRef Subcommand = argv[1];
398 // Ensure that argv[0] is correct after adjusting argv/argc.
399 argv[1] = argv[0];
400 if (Subcommand == "dump-symtab")
401 return dumpSymtab(argc - 1, argv + 1);
402 if (Subcommand == "run")
403 return run(argc - 1, argv + 1);
404 return usage();
405}

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

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