File: | tools/llvm-lto2/llvm-lto2.cpp |
Warning: | line 304, column 29 Potential leak of memory pointed to by field '_M_head_impl' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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 | ||||
29 | using namespace llvm; | |||
30 | using namespace lto; | |||
31 | ||||
32 | static 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 | ||||
37 | static 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 | ||||
42 | static cl::list<std::string> InputFilenames(cl::Positional, cl::OneOrMore, | |||
43 | cl::desc("<input bitcode files>")); | |||
44 | ||||
45 | static cl::opt<std::string> OutputFilename("o", cl::Required, | |||
46 | cl::desc("Output filename"), | |||
47 | cl::value_desc("filename")); | |||
48 | ||||
49 | static cl::opt<std::string> CacheDir("cache-dir", cl::desc("Cache Directory"), | |||
50 | cl::value_desc("directory")); | |||
51 | ||||
52 | static cl::opt<std::string> OptPipeline("opt-pipeline", | |||
53 | cl::desc("Optimizer Pipeline"), | |||
54 | cl::value_desc("pipeline")); | |||
55 | ||||
56 | static cl::opt<std::string> AAPipeline("aa-pipeline", | |||
57 | cl::desc("Alias Analysis Pipeline"), | |||
58 | cl::value_desc("aapipeline")); | |||
59 | ||||
60 | static cl::opt<bool> SaveTemps("save-temps", cl::desc("Save temporary files")); | |||
61 | ||||
62 | static 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 | ||||
68 | static cl::opt<int> Threads("thinlto-threads", | |||
69 | cl::init(llvm::heavyweight_hardware_concurrency())); | |||
70 | ||||
71 | static 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 | ||||
85 | static cl::opt<std::string> OverrideTriple( | |||
86 | "override-triple", | |||
87 | cl::desc("Replace target triples in input files with this triple")); | |||
88 | ||||
89 | static cl::opt<std::string> DefaultTriple( | |||
90 | "default-triple", | |||
91 | cl::desc( | |||
92 | "Replace unspecified target triples in input files with this triple")); | |||
93 | ||||
94 | static cl::opt<std::string> | |||
95 | OptRemarksOutput("pass-remarks-output", | |||
96 | cl::desc("YAML output file for optimization remarks")); | |||
97 | ||||
98 | static 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 | ||||
103 | static cl::opt<std::string> | |||
104 | SamplePGOFile("lto-sample-profile-file", | |||
105 | cl::desc("Specify a SamplePGO profile file")); | |||
106 | ||||
107 | static 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 | ||||
112 | static cl::opt<bool> | |||
113 | DebugPassManager("debug-pass-manager", cl::init(false), cl::Hidden, | |||
114 | cl::desc("Print pass management debugging information")); | |||
115 | ||||
116 | static 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 | ||||
125 | template <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 | ||||
132 | static void check(std::error_code EC, std::string Msg) { | |||
133 | check(errorCodeToError(EC), Msg); | |||
134 | } | |||
135 | ||||
136 | template <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 | ||||
143 | static int usage() { | |||
144 | errs() << "Available subcommands: dump-symtab run\n"; | |||
145 | return 1; | |||
146 | } | |||
147 | ||||
148 | static 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)); | |||
301 | }; | |||
302 | ||||
303 | auto AddBuffer = [&](size_t Task, std::unique_ptr<MemoryBuffer> MB) { | |||
304 | *AddStream(Task)->OS << MB->getBuffer(); | |||
| ||||
| ||||
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 | ||||
315 | static 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 | ||||
385 | int 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 | } |
1 | //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | // |
10 | // This file contains some templates that are useful if you are working with the |
11 | // STL at all. |
12 | // |
13 | // No library is required when using these functions. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef LLVM_ADT_STLEXTRAS_H |
18 | #define LLVM_ADT_STLEXTRAS_H |
19 | |
20 | #include "llvm/ADT/Optional.h" |
21 | #include "llvm/ADT/SmallVector.h" |
22 | #include "llvm/ADT/iterator.h" |
23 | #include "llvm/ADT/iterator_range.h" |
24 | #include "llvm/Support/ErrorHandling.h" |
25 | #include <algorithm> |
26 | #include <cassert> |
27 | #include <cstddef> |
28 | #include <cstdint> |
29 | #include <cstdlib> |
30 | #include <functional> |
31 | #include <initializer_list> |
32 | #include <iterator> |
33 | #include <limits> |
34 | #include <memory> |
35 | #include <tuple> |
36 | #include <type_traits> |
37 | #include <utility> |
38 | |
39 | namespace 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. |
43 | template <typename T, T> struct SameType; |
44 | |
45 | namespace detail { |
46 | |
47 | template <typename RangeT> |
48 | using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); |
49 | |
50 | template <typename RangeT> |
51 | using 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 | |
60 | template <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 | |
71 | template <class Ty> struct less_ptr { |
72 | bool operator()(const Ty* left, const Ty* right) const { |
73 | return *left < *right; |
74 | } |
75 | }; |
76 | |
77 | template <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. |
89 | template<typename Fn> class function_ref; |
90 | |
91 | template<typename Ret, typename ...Params> |
92 | class 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 | |
102 | public: |
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>); |
125 | template <class T> |
126 | inline void deleter(T *Ptr) { |
127 | delete Ptr; |
128 | } |
129 | |
130 | //===----------------------------------------------------------------------===// |
131 | // Extra additions to <iterator> |
132 | //===----------------------------------------------------------------------===// |
133 | |
134 | namespace adl_detail { |
135 | |
136 | using std::begin; |
137 | |
138 | template <typename ContainerTy> |
139 | auto adl_begin(ContainerTy &&container) |
140 | -> decltype(begin(std::forward<ContainerTy>(container))) { |
141 | return begin(std::forward<ContainerTy>(container)); |
142 | } |
143 | |
144 | using std::end; |
145 | |
146 | template <typename ContainerTy> |
147 | auto adl_end(ContainerTy &&container) |
148 | -> decltype(end(std::forward<ContainerTy>(container))) { |
149 | return end(std::forward<ContainerTy>(container)); |
150 | } |
151 | |
152 | using std::swap; |
153 | |
154 | template <typename T> |
155 | void 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 | |
162 | template <typename ContainerTy> |
163 | auto 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 | |
168 | template <typename ContainerTy> |
169 | auto 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 | |
174 | template <typename T> |
175 | void 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 | |
183 | template <typename ItTy, typename FuncTy, |
184 | typename FuncReturnTy = |
185 | decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))> |
186 | class 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> { |
191 | public: |
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 | |
199 | private: |
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... |
205 | template <class ItTy, class FuncTy> |
206 | inline 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(). |
211 | template <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 | |
221 | public: |
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(). |
226 | template <typename Ty> |
227 | struct 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. |
232 | template <typename ContainerTy> |
233 | auto 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. |
240 | template <typename IteratorTy> |
241 | std::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. |
248 | template <typename ContainerTy> |
249 | auto 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 |
270 | template <typename WrappedIteratorT, typename PredicateT> |
271 | class 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 | |
310 | public: |
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. |
331 | template <typename RangeT, typename PredicateT> |
332 | iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> |
333 | make_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 |
343 | template <typename R, typename UnaryPredicate> |
344 | bool all_of(R &&range, UnaryPredicate P); |
345 | |
346 | template <size_t... I> struct index_sequence; |
347 | |
348 | template <class... Ts> struct index_sequence_for; |
349 | |
350 | namespace detail { |
351 | |
352 | using 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. |
356 | template<typename... Iters> struct ZipTupleType { |
357 | using type = std::tuple<decltype(*declval<Iters>())...>; |
358 | }; |
359 | |
360 | template <typename ZipType, typename... Iters> |
361 | using 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 | |
376 | template <typename ZipType, typename... Iters> |
377 | struct 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 | |
383 | protected: |
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 | |
398 | public: |
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 | |
420 | template <typename... Iters> |
421 | struct 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 | |
431 | template <typename... Iters> |
432 | class 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 | |
440 | public: |
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 | |
450 | template <template <typename...> class ItType, typename... Args> class zippy { |
451 | public: |
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 | |
459 | private: |
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 | |
469 | public: |
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. |
479 | template <typename T, typename U, typename... Args> |
480 | detail::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. |
488 | template <typename T, typename U, typename... Args> |
489 | detail::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. |
505 | template <typename ValueT, typename... IterTs> |
506 | class 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 | |
576 | public: |
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 | |
599 | namespace 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. |
606 | template <typename ValueT, typename... RangeTs> class concat_range { |
607 | public: |
608 | using iterator = |
609 | concat_iterator<ValueT, |
610 | decltype(std::begin(std::declval<RangeTs &>()))...>; |
611 | |
612 | private: |
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 | |
623 | public: |
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. |
636 | template <typename ValueT, typename... RangeTs> |
637 | detail::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. |
650 | struct 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. |
658 | struct 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. |
667 | template <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. |
674 | template <size_t... I> |
675 | struct index_sequence : integer_sequence<std::size_t, I...> {}; |
676 | |
677 | template <std::size_t N, std::size_t... I> |
678 | struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; |
679 | template <std::size_t... I> |
680 | struct build_index_impl<0, I...> : index_sequence<I...> {}; |
681 | |
682 | /// \brief Creates a compile-time integer sequence for a parameter pack. |
683 | template <class... Ts> |
684 | struct 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. |
688 | template <int N> struct rank : rank<N - 1> {}; |
689 | template <> 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. |
693 | template <typename T, typename... Ts> struct is_one_of { |
694 | static const bool value = false; |
695 | }; |
696 | |
697 | template <typename T, typename U, typename... Ts> |
698 | struct 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. |
705 | template <typename T, typename... Ts> struct are_base_of { |
706 | static const bool value = true; |
707 | }; |
708 | |
709 | template <typename T, typename U, typename... Ts> |
710 | struct 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. |
720 | template <class T, std::size_t N> |
721 | constexpr inline size_t array_lengthof(T (&)[N]) { |
722 | return N; |
723 | } |
724 | |
725 | /// Adapt std::less<T> for array_pod_sort. |
726 | template<typename T> |
727 | inline 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. |
739 | template<typename T> |
740 | inline 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. |
759 | template<class IteratorTy> |
760 | inline 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 | |
768 | template <class IteratorTy> |
769 | inline 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. |
788 | template<typename Container> |
789 | void 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. |
797 | template<typename Container> |
798 | void 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. |
806 | template <typename R, typename UnaryPredicate> |
807 | UnaryPredicate 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. |
813 | template <typename R, typename UnaryPredicate> |
814 | bool 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. |
820 | template <typename R, typename UnaryPredicate> |
821 | bool 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. |
827 | template <typename R, typename UnaryPredicate> |
828 | bool 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. |
834 | template <typename R, typename T> |
835 | auto 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. |
841 | template <typename R, typename UnaryPredicate> |
842 | auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { |
843 | return std::find_if(adl_begin(Range), adl_end(Range), P); |
844 | } |
845 | |
846 | template <typename R, typename UnaryPredicate> |
847 | auto 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. |
853 | template <typename R, typename UnaryPredicate> |
854 | auto 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. |
860 | template <typename R, typename OutputIt, typename UnaryPredicate> |
861 | OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { |
862 | return std::copy_if(adl_begin(Range), adl_end(Range), Out, P); |
863 | } |
864 | |
865 | template <typename R, typename OutputIt> |
866 | OutputIt 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. |
872 | template <typename R, typename E> |
873 | bool 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. |
879 | template <typename R, typename E> |
880 | auto 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. |
887 | template <typename R, typename UnaryPredicate> |
888 | auto 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. |
895 | template <typename R, typename OutputIt, typename UnaryPredicate> |
896 | OutputIt 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. |
902 | template <typename R, typename UnaryPredicate> |
903 | auto 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. |
909 | template <typename R, typename ForwardIt> |
910 | auto 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. |
917 | template <unsigned Size, typename R> |
918 | SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size> |
919 | to_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. |
930 | template <typename Container, typename UnaryPredicate> |
931 | void 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); |
948 | template <class T, class... Args> |
949 | typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type |
950 | make_unique(Args &&... args) { |
951 | return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); |
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. |
962 | template <class T> |
963 | typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, |
964 | std::unique_ptr<T>>::type |
965 | make_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. |
970 | template <class T, class... Args> |
971 | typename std::enable_if<std::extent<T>::value != 0>::type |
972 | make_unique(Args &&...) = delete; |
973 | |
974 | struct FreeDeleter { |
975 | void operator()(void* v) { |
976 | ::free(v); |
977 | } |
978 | }; |
979 | |
980 | template<typename First, typename Second> |
981 | struct 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. |
988 | struct 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. |
995 | struct 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. |
1003 | template <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 | |
1017 | namespace detail { |
1018 | |
1019 | template <typename R> class enumerator_iter; |
1020 | |
1021 | template <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 | |
1038 | private: |
1039 | std::size_t Index = std::numeric_limits<std::size_t>::max(); |
1040 | IterOfRange<R> Iter; |
1041 | }; |
1042 | |
1043 | template <typename R> |
1044 | class 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 | |
1052 | public: |
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 | |
1081 | private: |
1082 | result_type Result; |
1083 | }; |
1084 | |
1085 | template <typename R> class enumerator { |
1086 | public: |
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 | |
1097 | private: |
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 | /// |
1118 | template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { |
1119 | return detail::enumerator<R>(std::forward<R>(TheRange)); |
1120 | } |
1121 | |
1122 | namespace detail { |
1123 | |
1124 | template <typename F, typename Tuple, std::size_t... I> |
1125 | auto 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. |
1135 | template <typename F, typename Tuple> |
1136 | auto 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 |