Bug Summary

File:tools/llvm-objdump/llvm-objdump.cpp
Warning:line 2265, column 23
Called C++ object pointer is null

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-objdump.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~svn338205/build-llvm/tools/llvm-objdump -I /build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/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/lib/gcc/x86_64-linux-gnu/8/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-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/tools/llvm-objdump -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp -faddrsig

/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp

1//===-- llvm-objdump.cpp - Object file dumping utility for llvm -----------===//
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 is a utility that works like binutils "objdump", that is, it
11// dumps out a plethora of information about an object file depending on the
12// flags.
13//
14// The flags and output of this program should be near identical to those of
15// binutils objdump.
16//
17//===----------------------------------------------------------------------===//
18
19#include "llvm-objdump.h"
20#include "llvm/ADT/Optional.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/StringExtras.h"
23#include "llvm/ADT/StringSet.h"
24#include "llvm/ADT/Triple.h"
25#include "llvm/CodeGen/FaultMaps.h"
26#include "llvm/DebugInfo/DWARF/DWARFContext.h"
27#include "llvm/DebugInfo/Symbolize/Symbolize.h"
28#include "llvm/Demangle/Demangle.h"
29#include "llvm/MC/MCAsmInfo.h"
30#include "llvm/MC/MCContext.h"
31#include "llvm/MC/MCDisassembler/MCDisassembler.h"
32#include "llvm/MC/MCDisassembler/MCRelocationInfo.h"
33#include "llvm/MC/MCInst.h"
34#include "llvm/MC/MCInstPrinter.h"
35#include "llvm/MC/MCInstrAnalysis.h"
36#include "llvm/MC/MCInstrInfo.h"
37#include "llvm/MC/MCObjectFileInfo.h"
38#include "llvm/MC/MCRegisterInfo.h"
39#include "llvm/MC/MCSubtargetInfo.h"
40#include "llvm/Object/Archive.h"
41#include "llvm/Object/COFF.h"
42#include "llvm/Object/COFFImportFile.h"
43#include "llvm/Object/ELFObjectFile.h"
44#include "llvm/Object/MachO.h"
45#include "llvm/Object/ObjectFile.h"
46#include "llvm/Object/Wasm.h"
47#include "llvm/Support/Casting.h"
48#include "llvm/Support/CommandLine.h"
49#include "llvm/Support/Debug.h"
50#include "llvm/Support/Errc.h"
51#include "llvm/Support/FileSystem.h"
52#include "llvm/Support/Format.h"
53#include "llvm/Support/GraphWriter.h"
54#include "llvm/Support/Host.h"
55#include "llvm/Support/InitLLVM.h"
56#include "llvm/Support/MemoryBuffer.h"
57#include "llvm/Support/SourceMgr.h"
58#include "llvm/Support/TargetRegistry.h"
59#include "llvm/Support/TargetSelect.h"
60#include "llvm/Support/raw_ostream.h"
61#include <algorithm>
62#include <cctype>
63#include <cstring>
64#include <system_error>
65#include <unordered_map>
66#include <utility>
67
68using namespace llvm;
69using namespace object;
70
71cl::opt<bool>
72 llvm::AllHeaders("all-headers",
73 cl::desc("Display all available header information"));
74static cl::alias AllHeadersShort("x", cl::desc("Alias for --all-headers"),
75 cl::aliasopt(AllHeaders));
76
77static cl::list<std::string>
78InputFilenames(cl::Positional, cl::desc("<input object files>"),cl::ZeroOrMore);
79
80cl::opt<bool>
81llvm::Disassemble("disassemble",
82 cl::desc("Display assembler mnemonics for the machine instructions"));
83static cl::alias
84Disassembled("d", cl::desc("Alias for --disassemble"),
85 cl::aliasopt(Disassemble));
86
87cl::opt<bool>
88llvm::DisassembleAll("disassemble-all",
89 cl::desc("Display assembler mnemonics for the machine instructions"));
90static cl::alias
91DisassembleAlld("D", cl::desc("Alias for --disassemble-all"),
92 cl::aliasopt(DisassembleAll));
93
94cl::opt<std::string> llvm::Demangle("demangle",
95 cl::desc("Demangle symbols names"),
96 cl::ValueOptional, cl::init("none"));
97
98static cl::alias DemangleShort("C", cl::desc("Alias for --demangle"),
99 cl::aliasopt(Demangle));
100
101static cl::list<std::string>
102DisassembleFunctions("df",
103 cl::CommaSeparated,
104 cl::desc("List of functions to disassemble"));
105static StringSet<> DisasmFuncsSet;
106
107cl::opt<bool>
108llvm::Relocations("r", cl::desc("Display the relocation entries in the file"));
109
110cl::opt<bool>
111llvm::DynamicRelocations("dynamic-reloc",
112 cl::desc("Display the dynamic relocation entries in the file"));
113static cl::alias
114DynamicRelocationsd("R", cl::desc("Alias for --dynamic-reloc"),
115 cl::aliasopt(DynamicRelocations));
116
117cl::opt<bool>
118llvm::SectionContents("s", cl::desc("Display the content of each section"));
119
120cl::opt<bool>
121llvm::SymbolTable("t", cl::desc("Display the symbol table"));
122
123cl::opt<bool>
124llvm::ExportsTrie("exports-trie", cl::desc("Display mach-o exported symbols"));
125
126cl::opt<bool>
127llvm::Rebase("rebase", cl::desc("Display mach-o rebasing info"));
128
129cl::opt<bool>
130llvm::Bind("bind", cl::desc("Display mach-o binding info"));
131
132cl::opt<bool>
133llvm::LazyBind("lazy-bind", cl::desc("Display mach-o lazy binding info"));
134
135cl::opt<bool>
136llvm::WeakBind("weak-bind", cl::desc("Display mach-o weak binding info"));
137
138cl::opt<bool>
139llvm::RawClangAST("raw-clang-ast",
140 cl::desc("Dump the raw binary contents of the clang AST section"));
141
142static cl::opt<bool>
143MachOOpt("macho", cl::desc("Use MachO specific object file parser"));
144static cl::alias
145MachOm("m", cl::desc("Alias for --macho"), cl::aliasopt(MachOOpt));
146
147cl::opt<std::string>
148llvm::TripleName("triple", cl::desc("Target triple to disassemble for, "
149 "see -version for available targets"));
150
151cl::opt<std::string>
152llvm::MCPU("mcpu",
153 cl::desc("Target a specific cpu type (-mcpu=help for details)"),
154 cl::value_desc("cpu-name"),
155 cl::init(""));
156
157cl::opt<std::string>
158llvm::ArchName("arch-name", cl::desc("Target arch to disassemble for, "
159 "see -version for available targets"));
160
161cl::opt<bool>
162llvm::SectionHeaders("section-headers", cl::desc("Display summaries of the "
163 "headers for each section."));
164static cl::alias
165SectionHeadersShort("headers", cl::desc("Alias for --section-headers"),
166 cl::aliasopt(SectionHeaders));
167static cl::alias
168SectionHeadersShorter("h", cl::desc("Alias for --section-headers"),
169 cl::aliasopt(SectionHeaders));
170
171cl::list<std::string>
172llvm::FilterSections("section", cl::desc("Operate on the specified sections only. "
173 "With -macho dump segment,section"));
174cl::alias
175static FilterSectionsj("j", cl::desc("Alias for --section"),
176 cl::aliasopt(llvm::FilterSections));
177
178cl::list<std::string>
179llvm::MAttrs("mattr",
180 cl::CommaSeparated,
181 cl::desc("Target specific attributes"),
182 cl::value_desc("a1,+a2,-a3,..."));
183
184cl::opt<bool>
185llvm::NoShowRawInsn("no-show-raw-insn", cl::desc("When disassembling "
186 "instructions, do not print "
187 "the instruction bytes."));
188cl::opt<bool>
189llvm::NoLeadingAddr("no-leading-addr", cl::desc("Print no leading address"));
190
191cl::opt<bool>
192llvm::UnwindInfo("unwind-info", cl::desc("Display unwind information"));
193
194static cl::alias
195UnwindInfoShort("u", cl::desc("Alias for --unwind-info"),
196 cl::aliasopt(UnwindInfo));
197
198cl::opt<bool>
199llvm::PrivateHeaders("private-headers",
200 cl::desc("Display format specific file headers"));
201
202cl::opt<bool>
203llvm::FirstPrivateHeader("private-header",
204 cl::desc("Display only the first format specific file "
205 "header"));
206
207static cl::alias
208PrivateHeadersShort("p", cl::desc("Alias for --private-headers"),
209 cl::aliasopt(PrivateHeaders));
210
211cl::opt<bool> llvm::FileHeaders(
212 "file-headers",
213 cl::desc("Display the contents of the overall file header"));
214
215static cl::alias FileHeadersShort("f", cl::desc("Alias for --file-headers"),
216 cl::aliasopt(FileHeaders));
217
218cl::opt<bool>
219 llvm::ArchiveHeaders("archive-headers",
220 cl::desc("Display archive header information"));
221
222cl::alias
223ArchiveHeadersShort("a", cl::desc("Alias for --archive-headers"),
224 cl::aliasopt(ArchiveHeaders));
225
226cl::opt<bool>
227 llvm::PrintImmHex("print-imm-hex",
228 cl::desc("Use hex format for immediate values"));
229
230cl::opt<bool> PrintFaultMaps("fault-map-section",
231 cl::desc("Display contents of faultmap section"));
232
233cl::opt<DIDumpType> llvm::DwarfDumpType(
234 "dwarf", cl::init(DIDT_Null), cl::desc("Dump of dwarf debug sections:"),
235 cl::values(clEnumValN(DIDT_DebugFrame, "frames", ".debug_frame")llvm::cl::OptionEnumValue { "frames", int(DIDT_DebugFrame), ".debug_frame"
}
));
236
237cl::opt<bool> PrintSource(
238 "source",
239 cl::desc(
240 "Display source inlined with disassembly. Implies disassemble object"));
241
242cl::alias PrintSourceShort("S", cl::desc("Alias for -source"),
243 cl::aliasopt(PrintSource));
244
245cl::opt<bool> PrintLines("line-numbers",
246 cl::desc("Display source line numbers with "
247 "disassembly. Implies disassemble object"));
248
249cl::alias PrintLinesShort("l", cl::desc("Alias for -line-numbers"),
250 cl::aliasopt(PrintLines));
251
252cl::opt<unsigned long long>
253 StartAddress("start-address", cl::desc("Disassemble beginning at address"),
254 cl::value_desc("address"), cl::init(0));
255cl::opt<unsigned long long>
256 StopAddress("stop-address", cl::desc("Stop disassembly at address"),
257 cl::value_desc("address"), cl::init(UINT64_MAX(18446744073709551615UL)));
258static StringRef ToolName;
259
260typedef std::vector<std::tuple<uint64_t, StringRef, uint8_t>> SectionSymbolsTy;
261
262namespace {
263typedef std::function<bool(llvm::object::SectionRef const &)> FilterPredicate;
264
265class SectionFilterIterator {
266public:
267 SectionFilterIterator(FilterPredicate P,
268 llvm::object::section_iterator const &I,
269 llvm::object::section_iterator const &E)
270 : Predicate(std::move(P)), Iterator(I), End(E) {
271 ScanPredicate();
272 }
273 const llvm::object::SectionRef &operator*() const { return *Iterator; }
274 SectionFilterIterator &operator++() {
275 ++Iterator;
276 ScanPredicate();
277 return *this;
278 }
279 bool operator!=(SectionFilterIterator const &Other) const {
280 return Iterator != Other.Iterator;
281 }
282
283private:
284 void ScanPredicate() {
285 while (Iterator != End && !Predicate(*Iterator)) {
286 ++Iterator;
287 }
288 }
289 FilterPredicate Predicate;
290 llvm::object::section_iterator Iterator;
291 llvm::object::section_iterator End;
292};
293
294class SectionFilter {
295public:
296 SectionFilter(FilterPredicate P, llvm::object::ObjectFile const &O)
297 : Predicate(std::move(P)), Object(O) {}
298 SectionFilterIterator begin() {
299 return SectionFilterIterator(Predicate, Object.section_begin(),
300 Object.section_end());
301 }
302 SectionFilterIterator end() {
303 return SectionFilterIterator(Predicate, Object.section_end(),
304 Object.section_end());
305 }
306
307private:
308 FilterPredicate Predicate;
309 llvm::object::ObjectFile const &Object;
310};
311SectionFilter ToolSectionFilter(llvm::object::ObjectFile const &O) {
312 return SectionFilter(
313 [](llvm::object::SectionRef const &S) {
314 if (FilterSections.empty())
315 return true;
316 llvm::StringRef String;
317 std::error_code error = S.getName(String);
318 if (error)
319 return false;
320 return is_contained(FilterSections, String);
321 },
322 O);
323}
324}
325
326void llvm::error(std::error_code EC) {
327 if (!EC)
328 return;
329
330 errs() << ToolName << ": error reading file: " << EC.message() << ".\n";
331 errs().flush();
332 exit(1);
333}
334
335LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void llvm::error(Twine Message) {
336 errs() << ToolName << ": " << Message << ".\n";
337 errs().flush();
338 exit(1);
339}
340
341void llvm::warn(StringRef Message) {
342 errs() << ToolName << ": warning: " << Message << ".\n";
343 errs().flush();
344}
345
346LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void llvm::report_error(StringRef File,
347 Twine Message) {
348 errs() << ToolName << ": '" << File << "': " << Message << ".\n";
349 exit(1);
350}
351
352LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void llvm::report_error(StringRef File,
353 std::error_code EC) {
354 assert(EC)(static_cast <bool> (EC) ? void (0) : __assert_fail ("EC"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 354, __extension__ __PRETTY_FUNCTION__))
;
355 errs() << ToolName << ": '" << File << "': " << EC.message() << ".\n";
356 exit(1);
357}
358
359LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void llvm::report_error(StringRef File,
360 llvm::Error E) {
361 assert(E)(static_cast <bool> (E) ? void (0) : __assert_fail ("E"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 361, __extension__ __PRETTY_FUNCTION__))
;
362 std::string Buf;
363 raw_string_ostream OS(Buf);
364 logAllUnhandledErrors(std::move(E), OS, "");
365 OS.flush();
366 errs() << ToolName << ": '" << File << "': " << Buf;
367 exit(1);
368}
369
370LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void llvm::report_error(StringRef ArchiveName,
371 StringRef FileName,
372 llvm::Error E,
373 StringRef ArchitectureName) {
374 assert(E)(static_cast <bool> (E) ? void (0) : __assert_fail ("E"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 374, __extension__ __PRETTY_FUNCTION__))
;
375 errs() << ToolName << ": ";
376 if (ArchiveName != "")
377 errs() << ArchiveName << "(" << FileName << ")";
378 else
379 errs() << "'" << FileName << "'";
380 if (!ArchitectureName.empty())
381 errs() << " (for architecture " << ArchitectureName << ")";
382 std::string Buf;
383 raw_string_ostream OS(Buf);
384 logAllUnhandledErrors(std::move(E), OS, "");
385 OS.flush();
386 errs() << ": " << Buf;
387 exit(1);
388}
389
390LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void llvm::report_error(StringRef ArchiveName,
391 const object::Archive::Child &C,
392 llvm::Error E,
393 StringRef ArchitectureName) {
394 Expected<StringRef> NameOrErr = C.getName();
395 // TODO: if we have a error getting the name then it would be nice to print
396 // the index of which archive member this is and or its offset in the
397 // archive instead of "???" as the name.
398 if (!NameOrErr) {
399 consumeError(NameOrErr.takeError());
400 llvm::report_error(ArchiveName, "???", std::move(E), ArchitectureName);
401 } else
402 llvm::report_error(ArchiveName, NameOrErr.get(), std::move(E),
403 ArchitectureName);
404}
405
406static const Target *getTarget(const ObjectFile *Obj = nullptr) {
407 // Figure out the target triple.
408 llvm::Triple TheTriple("unknown-unknown-unknown");
409 if (TripleName.empty()) {
410 if (Obj) {
411 TheTriple = Obj->makeTriple();
412 }
413 } else {
414 TheTriple.setTriple(Triple::normalize(TripleName));
415
416 // Use the triple, but also try to combine with ARM build attributes.
417 if (Obj) {
418 auto Arch = Obj->getArch();
419 if (Arch == Triple::arm || Arch == Triple::armeb) {
420 Obj->setARMSubArch(TheTriple);
421 }
422 }
423 }
424
425 // Get the target specific parser.
426 std::string Error;
427 const Target *TheTarget = TargetRegistry::lookupTarget(ArchName, TheTriple,
428 Error);
429 if (!TheTarget) {
430 if (Obj)
431 report_error(Obj->getFileName(), "can't find target: " + Error);
432 else
433 error("can't find target: " + Error);
434 }
435
436 // Update the triple name and return the found target.
437 TripleName = TheTriple.getTriple();
438 return TheTarget;
439}
440
441bool llvm::RelocAddressLess(RelocationRef a, RelocationRef b) {
442 return a.getOffset() < b.getOffset();
443}
444
445template <class ELFT>
446static std::error_code getRelocationValueString(const ELFObjectFile<ELFT> *Obj,
447 const RelocationRef &RelRef,
448 SmallVectorImpl<char> &Result) {
449 DataRefImpl Rel = RelRef.getRawDataRefImpl();
450
451 typedef typename ELFObjectFile<ELFT>::Elf_Sym Elf_Sym;
452 typedef typename ELFObjectFile<ELFT>::Elf_Shdr Elf_Shdr;
453 typedef typename ELFObjectFile<ELFT>::Elf_Rela Elf_Rela;
454
455 const ELFFile<ELFT> &EF = *Obj->getELFFile();
456
457 auto SecOrErr = EF.getSection(Rel.d.a);
458 if (!SecOrErr)
459 return errorToErrorCode(SecOrErr.takeError());
460 const Elf_Shdr *Sec = *SecOrErr;
461 auto SymTabOrErr = EF.getSection(Sec->sh_link);
462 if (!SymTabOrErr)
463 return errorToErrorCode(SymTabOrErr.takeError());
464 const Elf_Shdr *SymTab = *SymTabOrErr;
465 assert(SymTab->sh_type == ELF::SHT_SYMTAB ||(static_cast <bool> (SymTab->sh_type == ELF::SHT_SYMTAB
|| SymTab->sh_type == ELF::SHT_DYNSYM) ? void (0) : __assert_fail
("SymTab->sh_type == ELF::SHT_SYMTAB || SymTab->sh_type == ELF::SHT_DYNSYM"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 466, __extension__ __PRETTY_FUNCTION__))
466 SymTab->sh_type == ELF::SHT_DYNSYM)(static_cast <bool> (SymTab->sh_type == ELF::SHT_SYMTAB
|| SymTab->sh_type == ELF::SHT_DYNSYM) ? void (0) : __assert_fail
("SymTab->sh_type == ELF::SHT_SYMTAB || SymTab->sh_type == ELF::SHT_DYNSYM"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 466, __extension__ __PRETTY_FUNCTION__))
;
467 auto StrTabSec = EF.getSection(SymTab->sh_link);
468 if (!StrTabSec)
469 return errorToErrorCode(StrTabSec.takeError());
470 auto StrTabOrErr = EF.getStringTable(*StrTabSec);
471 if (!StrTabOrErr)
472 return errorToErrorCode(StrTabOrErr.takeError());
473 StringRef StrTab = *StrTabOrErr;
474 int64_t addend = 0;
475 // If there is no Symbol associated with the relocation, we set the undef
476 // boolean value to 'true'. This will prevent us from calling functions that
477 // requires the relocation to be associated with a symbol.
478 bool undef = false;
479 switch (Sec->sh_type) {
480 default:
481 return object_error::parse_failed;
482 case ELF::SHT_REL: {
483 // TODO: Read implicit addend from section data.
484 break;
485 }
486 case ELF::SHT_RELA: {
487 const Elf_Rela *ERela = Obj->getRela(Rel);
488 addend = ERela->r_addend;
489 undef = ERela->getSymbol(false) == 0;
490 break;
491 }
492 }
493 StringRef Target;
494 if (!undef) {
495 symbol_iterator SI = RelRef.getSymbol();
496 const Elf_Sym *symb = Obj->getSymbol(SI->getRawDataRefImpl());
497 if (symb->getType() == ELF::STT_SECTION) {
498 Expected<section_iterator> SymSI = SI->getSection();
499 if (!SymSI)
500 return errorToErrorCode(SymSI.takeError());
501 const Elf_Shdr *SymSec = Obj->getSection((*SymSI)->getRawDataRefImpl());
502 auto SecName = EF.getSectionName(SymSec);
503 if (!SecName)
504 return errorToErrorCode(SecName.takeError());
505 Target = *SecName;
506 } else {
507 Expected<StringRef> SymName = symb->getName(StrTab);
508 if (!SymName)
509 return errorToErrorCode(SymName.takeError());
510 Target = *SymName;
511 }
512 } else
513 Target = "*ABS*";
514
515 // Default scheme is to print Target, as well as "+ <addend>" for nonzero
516 // addend. Should be acceptable for all normal purposes.
517 std::string fmtbuf;
518 raw_string_ostream fmt(fmtbuf);
519 fmt << Target;
520 if (addend != 0)
521 fmt << (addend < 0 ? "" : "+") << addend;
522 fmt.flush();
523 Result.append(fmtbuf.begin(), fmtbuf.end());
524 return std::error_code();
525}
526
527static std::error_code getRelocationValueString(const ELFObjectFileBase *Obj,
528 const RelocationRef &Rel,
529 SmallVectorImpl<char> &Result) {
530 if (auto *ELF32LE = dyn_cast<ELF32LEObjectFile>(Obj))
531 return getRelocationValueString(ELF32LE, Rel, Result);
532 if (auto *ELF64LE = dyn_cast<ELF64LEObjectFile>(Obj))
533 return getRelocationValueString(ELF64LE, Rel, Result);
534 if (auto *ELF32BE = dyn_cast<ELF32BEObjectFile>(Obj))
535 return getRelocationValueString(ELF32BE, Rel, Result);
536 auto *ELF64BE = cast<ELF64BEObjectFile>(Obj);
537 return getRelocationValueString(ELF64BE, Rel, Result);
538}
539
540static std::error_code getRelocationValueString(const COFFObjectFile *Obj,
541 const RelocationRef &Rel,
542 SmallVectorImpl<char> &Result) {
543 symbol_iterator SymI = Rel.getSymbol();
544 Expected<StringRef> SymNameOrErr = SymI->getName();
545 if (!SymNameOrErr)
546 return errorToErrorCode(SymNameOrErr.takeError());
547 StringRef SymName = *SymNameOrErr;
548 Result.append(SymName.begin(), SymName.end());
549 return std::error_code();
550}
551
552static void printRelocationTargetName(const MachOObjectFile *O,
553 const MachO::any_relocation_info &RE,
554 raw_string_ostream &fmt) {
555 bool IsScattered = O->isRelocationScattered(RE);
556
557 // Target of a scattered relocation is an address. In the interest of
558 // generating pretty output, scan through the symbol table looking for a
559 // symbol that aligns with that address. If we find one, print it.
560 // Otherwise, we just print the hex address of the target.
561 if (IsScattered) {
562 uint32_t Val = O->getPlainRelocationSymbolNum(RE);
563
564 for (const SymbolRef &Symbol : O->symbols()) {
565 std::error_code ec;
566 Expected<uint64_t> Addr = Symbol.getAddress();
567 if (!Addr)
568 report_error(O->getFileName(), Addr.takeError());
569 if (*Addr != Val)
570 continue;
571 Expected<StringRef> Name = Symbol.getName();
572 if (!Name)
573 report_error(O->getFileName(), Name.takeError());
574 fmt << *Name;
575 return;
576 }
577
578 // If we couldn't find a symbol that this relocation refers to, try
579 // to find a section beginning instead.
580 for (const SectionRef &Section : ToolSectionFilter(*O)) {
581 std::error_code ec;
582
583 StringRef Name;
584 uint64_t Addr = Section.getAddress();
585 if (Addr != Val)
586 continue;
587 if ((ec = Section.getName(Name)))
588 report_error(O->getFileName(), ec);
589 fmt << Name;
590 return;
591 }
592
593 fmt << format("0x%x", Val);
594 return;
595 }
596
597 StringRef S;
598 bool isExtern = O->getPlainRelocationExternal(RE);
599 uint64_t Val = O->getPlainRelocationSymbolNum(RE);
600
601 if (O->getAnyRelocationType(RE) == MachO::ARM64_RELOC_ADDEND) {
602 fmt << format("0x%0" PRIx64"l" "x", Val);
603 return;
604 } else if (isExtern) {
605 symbol_iterator SI = O->symbol_begin();
606 advance(SI, Val);
607 Expected<StringRef> SOrErr = SI->getName();
608 if (!SOrErr)
609 report_error(O->getFileName(), SOrErr.takeError());
610 S = *SOrErr;
611 } else {
612 section_iterator SI = O->section_begin();
613 // Adjust for the fact that sections are 1-indexed.
614 if (Val == 0) {
615 fmt << "0 (?,?)";
616 return;
617 }
618 uint32_t i = Val - 1;
619 while (i != 0 && SI != O->section_end()) {
620 i--;
621 advance(SI, 1);
622 }
623 if (SI == O->section_end())
624 fmt << Val << " (?,?)";
625 else
626 SI->getName(S);
627 }
628
629 fmt << S;
630}
631
632static std::error_code getRelocationValueString(const WasmObjectFile *Obj,
633 const RelocationRef &RelRef,
634 SmallVectorImpl<char> &Result) {
635 const wasm::WasmRelocation& Rel = Obj->getWasmRelocation(RelRef);
636 symbol_iterator SI = RelRef.getSymbol();
637 std::string fmtbuf;
638 raw_string_ostream fmt(fmtbuf);
639 if (SI == Obj->symbol_end()) {
640 // Not all wasm relocations have symbols associated with them.
641 // In particular R_WEBASSEMBLY_TYPE_INDEX_LEB.
642 fmt << Rel.Index;
643 } else {
644 Expected<StringRef> SymNameOrErr = SI->getName();
645 if (!SymNameOrErr)
646 return errorToErrorCode(SymNameOrErr.takeError());
647 StringRef SymName = *SymNameOrErr;
648 Result.append(SymName.begin(), SymName.end());
649 }
650 fmt << (Rel.Addend < 0 ? "" : "+") << Rel.Addend;
651 fmt.flush();
652 Result.append(fmtbuf.begin(), fmtbuf.end());
653 return std::error_code();
654}
655
656static std::error_code getRelocationValueString(const MachOObjectFile *Obj,
657 const RelocationRef &RelRef,
658 SmallVectorImpl<char> &Result) {
659 DataRefImpl Rel = RelRef.getRawDataRefImpl();
660 MachO::any_relocation_info RE = Obj->getRelocation(Rel);
661
662 unsigned Arch = Obj->getArch();
663
664 std::string fmtbuf;
665 raw_string_ostream fmt(fmtbuf);
666 unsigned Type = Obj->getAnyRelocationType(RE);
667 bool IsPCRel = Obj->getAnyRelocationPCRel(RE);
668
669 // Determine any addends that should be displayed with the relocation.
670 // These require decoding the relocation type, which is triple-specific.
671
672 // X86_64 has entirely custom relocation types.
673 if (Arch == Triple::x86_64) {
674 bool isPCRel = Obj->getAnyRelocationPCRel(RE);
675
676 switch (Type) {
677 case MachO::X86_64_RELOC_GOT_LOAD:
678 case MachO::X86_64_RELOC_GOT: {
679 printRelocationTargetName(Obj, RE, fmt);
680 fmt << "@GOT";
681 if (isPCRel)
682 fmt << "PCREL";
683 break;
684 }
685 case MachO::X86_64_RELOC_SUBTRACTOR: {
686 DataRefImpl RelNext = Rel;
687 Obj->moveRelocationNext(RelNext);
688 MachO::any_relocation_info RENext = Obj->getRelocation(RelNext);
689
690 // X86_64_RELOC_SUBTRACTOR must be followed by a relocation of type
691 // X86_64_RELOC_UNSIGNED.
692 // NOTE: Scattered relocations don't exist on x86_64.
693 unsigned RType = Obj->getAnyRelocationType(RENext);
694 if (RType != MachO::X86_64_RELOC_UNSIGNED)
695 report_error(Obj->getFileName(), "Expected X86_64_RELOC_UNSIGNED after "
696 "X86_64_RELOC_SUBTRACTOR.");
697
698 // The X86_64_RELOC_UNSIGNED contains the minuend symbol;
699 // X86_64_RELOC_SUBTRACTOR contains the subtrahend.
700 printRelocationTargetName(Obj, RENext, fmt);
701 fmt << "-";
702 printRelocationTargetName(Obj, RE, fmt);
703 break;
704 }
705 case MachO::X86_64_RELOC_TLV:
706 printRelocationTargetName(Obj, RE, fmt);
707 fmt << "@TLV";
708 if (isPCRel)
709 fmt << "P";
710 break;
711 case MachO::X86_64_RELOC_SIGNED_1:
712 printRelocationTargetName(Obj, RE, fmt);
713 fmt << "-1";
714 break;
715 case MachO::X86_64_RELOC_SIGNED_2:
716 printRelocationTargetName(Obj, RE, fmt);
717 fmt << "-2";
718 break;
719 case MachO::X86_64_RELOC_SIGNED_4:
720 printRelocationTargetName(Obj, RE, fmt);
721 fmt << "-4";
722 break;
723 default:
724 printRelocationTargetName(Obj, RE, fmt);
725 break;
726 }
727 // X86 and ARM share some relocation types in common.
728 } else if (Arch == Triple::x86 || Arch == Triple::arm ||
729 Arch == Triple::ppc) {
730 // Generic relocation types...
731 switch (Type) {
732 case MachO::GENERIC_RELOC_PAIR: // prints no info
733 return std::error_code();
734 case MachO::GENERIC_RELOC_SECTDIFF: {
735 DataRefImpl RelNext = Rel;
736 Obj->moveRelocationNext(RelNext);
737 MachO::any_relocation_info RENext = Obj->getRelocation(RelNext);
738
739 // X86 sect diff's must be followed by a relocation of type
740 // GENERIC_RELOC_PAIR.
741 unsigned RType = Obj->getAnyRelocationType(RENext);
742
743 if (RType != MachO::GENERIC_RELOC_PAIR)
744 report_error(Obj->getFileName(), "Expected GENERIC_RELOC_PAIR after "
745 "GENERIC_RELOC_SECTDIFF.");
746
747 printRelocationTargetName(Obj, RE, fmt);
748 fmt << "-";
749 printRelocationTargetName(Obj, RENext, fmt);
750 break;
751 }
752 }
753
754 if (Arch == Triple::x86 || Arch == Triple::ppc) {
755 switch (Type) {
756 case MachO::GENERIC_RELOC_LOCAL_SECTDIFF: {
757 DataRefImpl RelNext = Rel;
758 Obj->moveRelocationNext(RelNext);
759 MachO::any_relocation_info RENext = Obj->getRelocation(RelNext);
760
761 // X86 sect diff's must be followed by a relocation of type
762 // GENERIC_RELOC_PAIR.
763 unsigned RType = Obj->getAnyRelocationType(RENext);
764 if (RType != MachO::GENERIC_RELOC_PAIR)
765 report_error(Obj->getFileName(), "Expected GENERIC_RELOC_PAIR after "
766 "GENERIC_RELOC_LOCAL_SECTDIFF.");
767
768 printRelocationTargetName(Obj, RE, fmt);
769 fmt << "-";
770 printRelocationTargetName(Obj, RENext, fmt);
771 break;
772 }
773 case MachO::GENERIC_RELOC_TLV: {
774 printRelocationTargetName(Obj, RE, fmt);
775 fmt << "@TLV";
776 if (IsPCRel)
777 fmt << "P";
778 break;
779 }
780 default:
781 printRelocationTargetName(Obj, RE, fmt);
782 }
783 } else { // ARM-specific relocations
784 switch (Type) {
785 case MachO::ARM_RELOC_HALF:
786 case MachO::ARM_RELOC_HALF_SECTDIFF: {
787 // Half relocations steal a bit from the length field to encode
788 // whether this is an upper16 or a lower16 relocation.
789 bool isUpper = (Obj->getAnyRelocationLength(RE) & 0x1) == 1;
790
791 if (isUpper)
792 fmt << ":upper16:(";
793 else
794 fmt << ":lower16:(";
795 printRelocationTargetName(Obj, RE, fmt);
796
797 DataRefImpl RelNext = Rel;
798 Obj->moveRelocationNext(RelNext);
799 MachO::any_relocation_info RENext = Obj->getRelocation(RelNext);
800
801 // ARM half relocs must be followed by a relocation of type
802 // ARM_RELOC_PAIR.
803 unsigned RType = Obj->getAnyRelocationType(RENext);
804 if (RType != MachO::ARM_RELOC_PAIR)
805 report_error(Obj->getFileName(), "Expected ARM_RELOC_PAIR after "
806 "ARM_RELOC_HALF");
807
808 // NOTE: The half of the target virtual address is stashed in the
809 // address field of the secondary relocation, but we can't reverse
810 // engineer the constant offset from it without decoding the movw/movt
811 // instruction to find the other half in its immediate field.
812
813 // ARM_RELOC_HALF_SECTDIFF encodes the second section in the
814 // symbol/section pointer of the follow-on relocation.
815 if (Type == MachO::ARM_RELOC_HALF_SECTDIFF) {
816 fmt << "-";
817 printRelocationTargetName(Obj, RENext, fmt);
818 }
819
820 fmt << ")";
821 break;
822 }
823 default: { printRelocationTargetName(Obj, RE, fmt); }
824 }
825 }
826 } else
827 printRelocationTargetName(Obj, RE, fmt);
828
829 fmt.flush();
830 Result.append(fmtbuf.begin(), fmtbuf.end());
831 return std::error_code();
832}
833
834static std::error_code getRelocationValueString(const RelocationRef &Rel,
835 SmallVectorImpl<char> &Result) {
836 const ObjectFile *Obj = Rel.getObject();
837 if (auto *ELF = dyn_cast<ELFObjectFileBase>(Obj))
838 return getRelocationValueString(ELF, Rel, Result);
839 if (auto *COFF = dyn_cast<COFFObjectFile>(Obj))
840 return getRelocationValueString(COFF, Rel, Result);
841 if (auto *Wasm = dyn_cast<WasmObjectFile>(Obj))
842 return getRelocationValueString(Wasm, Rel, Result);
843 if (auto *MachO = dyn_cast<MachOObjectFile>(Obj))
844 return getRelocationValueString(MachO, Rel, Result);
845 llvm_unreachable("unknown object file format")::llvm::llvm_unreachable_internal("unknown object file format"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 845)
;
846}
847
848/// Indicates whether this relocation should hidden when listing
849/// relocations, usually because it is the trailing part of a multipart
850/// relocation that will be printed as part of the leading relocation.
851static bool getHidden(RelocationRef RelRef) {
852 const ObjectFile *Obj = RelRef.getObject();
853 auto *MachO = dyn_cast<MachOObjectFile>(Obj);
854 if (!MachO)
855 return false;
856
857 unsigned Arch = MachO->getArch();
858 DataRefImpl Rel = RelRef.getRawDataRefImpl();
859 uint64_t Type = MachO->getRelocationType(Rel);
860
861 // On arches that use the generic relocations, GENERIC_RELOC_PAIR
862 // is always hidden.
863 if (Arch == Triple::x86 || Arch == Triple::arm || Arch == Triple::ppc) {
864 if (Type == MachO::GENERIC_RELOC_PAIR)
865 return true;
866 } else if (Arch == Triple::x86_64) {
867 // On x86_64, X86_64_RELOC_UNSIGNED is hidden only when it follows
868 // an X86_64_RELOC_SUBTRACTOR.
869 if (Type == MachO::X86_64_RELOC_UNSIGNED && Rel.d.a > 0) {
870 DataRefImpl RelPrev = Rel;
871 RelPrev.d.a--;
872 uint64_t PrevType = MachO->getRelocationType(RelPrev);
873 if (PrevType == MachO::X86_64_RELOC_SUBTRACTOR)
874 return true;
875 }
876 }
877
878 return false;
879}
880
881namespace {
882class SourcePrinter {
883protected:
884 DILineInfo OldLineInfo;
885 const ObjectFile *Obj = nullptr;
886 std::unique_ptr<symbolize::LLVMSymbolizer> Symbolizer;
887 // File name to file contents of source
888 std::unordered_map<std::string, std::unique_ptr<MemoryBuffer>> SourceCache;
889 // Mark the line endings of the cached source
890 std::unordered_map<std::string, std::vector<StringRef>> LineCache;
891
892private:
893 bool cacheSource(const DILineInfo& LineInfoFile);
894
895public:
896 SourcePrinter() = default;
897 SourcePrinter(const ObjectFile *Obj, StringRef DefaultArch) : Obj(Obj) {
898 symbolize::LLVMSymbolizer::Options SymbolizerOpts(
899 DILineInfoSpecifier::FunctionNameKind::None, true, false, false,
900 DefaultArch);
901 Symbolizer.reset(new symbolize::LLVMSymbolizer(SymbolizerOpts));
902 }
903 virtual ~SourcePrinter() = default;
904 virtual void printSourceLine(raw_ostream &OS, uint64_t Address,
905 StringRef Delimiter = "; ");
906};
907
908bool SourcePrinter::cacheSource(const DILineInfo &LineInfo) {
909 std::unique_ptr<MemoryBuffer> Buffer;
910 if (LineInfo.Source) {
911 Buffer = MemoryBuffer::getMemBuffer(*LineInfo.Source);
912 } else {
913 auto BufferOrError = MemoryBuffer::getFile(LineInfo.FileName);
914 if (!BufferOrError)
915 return false;
916 Buffer = std::move(*BufferOrError);
917 }
918 // Chomp the file to get lines
919 size_t BufferSize = Buffer->getBufferSize();
920 const char *BufferStart = Buffer->getBufferStart();
921 for (const char *Start = BufferStart, *End = BufferStart;
922 End < BufferStart + BufferSize; End++)
923 if (*End == '\n' || End == BufferStart + BufferSize - 1 ||
924 (*End == '\r' && *(End + 1) == '\n')) {
925 LineCache[LineInfo.FileName].push_back(StringRef(Start, End - Start));
926 if (*End == '\r')
927 End++;
928 Start = End + 1;
929 }
930 SourceCache[LineInfo.FileName] = std::move(Buffer);
931 return true;
932}
933
934void SourcePrinter::printSourceLine(raw_ostream &OS, uint64_t Address,
935 StringRef Delimiter) {
936 if (!Symbolizer)
937 return;
938 DILineInfo LineInfo = DILineInfo();
939 auto ExpectecLineInfo =
940 Symbolizer->symbolizeCode(Obj->getFileName(), Address);
941 if (!ExpectecLineInfo)
942 consumeError(ExpectecLineInfo.takeError());
943 else
944 LineInfo = *ExpectecLineInfo;
945
946 if ((LineInfo.FileName == "<invalid>") || OldLineInfo.Line == LineInfo.Line ||
947 LineInfo.Line == 0)
948 return;
949
950 if (PrintLines)
951 OS << Delimiter << LineInfo.FileName << ":" << LineInfo.Line << "\n";
952 if (PrintSource) {
953 if (SourceCache.find(LineInfo.FileName) == SourceCache.end())
954 if (!cacheSource(LineInfo))
955 return;
956 auto FileBuffer = SourceCache.find(LineInfo.FileName);
957 if (FileBuffer != SourceCache.end()) {
958 auto LineBuffer = LineCache.find(LineInfo.FileName);
959 if (LineBuffer != LineCache.end()) {
960 if (LineInfo.Line > LineBuffer->second.size())
961 return;
962 // Vector begins at 0, line numbers are non-zero
963 OS << Delimiter << LineBuffer->second[LineInfo.Line - 1].ltrim()
964 << "\n";
965 }
966 }
967 }
968 OldLineInfo = LineInfo;
969}
970
971static bool isArmElf(const ObjectFile *Obj) {
972 return (Obj->isELF() &&
973 (Obj->getArch() == Triple::aarch64 ||
974 Obj->getArch() == Triple::aarch64_be ||
975 Obj->getArch() == Triple::arm || Obj->getArch() == Triple::armeb ||
976 Obj->getArch() == Triple::thumb ||
977 Obj->getArch() == Triple::thumbeb));
978}
979
980class PrettyPrinter {
981public:
982 virtual ~PrettyPrinter() = default;
983 virtual void printInst(MCInstPrinter &IP, const MCInst *MI,
984 ArrayRef<uint8_t> Bytes, uint64_t Address,
985 raw_ostream &OS, StringRef Annot,
986 MCSubtargetInfo const &STI, SourcePrinter *SP,
987 std::vector<RelocationRef> *Rels = nullptr) {
988 if (SP && (PrintSource || PrintLines))
989 SP->printSourceLine(OS, Address);
990 if (!NoLeadingAddr)
991 OS << format("%8" PRIx64"l" "x" ":", Address);
992 if (!NoShowRawInsn) {
993 OS << "\t";
994 dumpBytes(Bytes, OS);
995 }
996 if (MI)
997 IP.printInst(MI, OS, "", STI);
998 else
999 OS << " <unknown>";
1000 }
1001};
1002PrettyPrinter PrettyPrinterInst;
1003class HexagonPrettyPrinter : public PrettyPrinter {
1004public:
1005 void printLead(ArrayRef<uint8_t> Bytes, uint64_t Address,
1006 raw_ostream &OS) {
1007 uint32_t opcode =
1008 (Bytes[3] << 24) | (Bytes[2] << 16) | (Bytes[1] << 8) | Bytes[0];
1009 if (!NoLeadingAddr)
1010 OS << format("%8" PRIx64"l" "x" ":", Address);
1011 if (!NoShowRawInsn) {
1012 OS << "\t";
1013 dumpBytes(Bytes.slice(0, 4), OS);
1014 OS << format("%08" PRIx32"x", opcode);
1015 }
1016 }
1017 void printInst(MCInstPrinter &IP, const MCInst *MI, ArrayRef<uint8_t> Bytes,
1018 uint64_t Address, raw_ostream &OS, StringRef Annot,
1019 MCSubtargetInfo const &STI, SourcePrinter *SP,
1020 std::vector<RelocationRef> *Rels) override {
1021 if (SP && (PrintSource || PrintLines))
1022 SP->printSourceLine(OS, Address, "");
1023 if (!MI) {
1024 printLead(Bytes, Address, OS);
1025 OS << " <unknown>";
1026 return;
1027 }
1028 std::string Buffer;
1029 {
1030 raw_string_ostream TempStream(Buffer);
1031 IP.printInst(MI, TempStream, "", STI);
1032 }
1033 StringRef Contents(Buffer);
1034 // Split off bundle attributes
1035 auto PacketBundle = Contents.rsplit('\n');
1036 // Split off first instruction from the rest
1037 auto HeadTail = PacketBundle.first.split('\n');
1038 auto Preamble = " { ";
1039 auto Separator = "";
1040 StringRef Fmt = "\t\t\t%08" PRIx64"l" "x" ": ";
1041 std::vector<RelocationRef>::const_iterator rel_cur = Rels->begin();
1042 std::vector<RelocationRef>::const_iterator rel_end = Rels->end();
1043
1044 // Hexagon's packets require relocations to be inline rather than
1045 // clustered at the end of the packet.
1046 auto PrintReloc = [&]() -> void {
1047 while ((rel_cur != rel_end) && (rel_cur->getOffset() <= Address)) {
1048 if (rel_cur->getOffset() == Address) {
1049 SmallString<16> name;
1050 SmallString<32> val;
1051 rel_cur->getTypeName(name);
1052 error(getRelocationValueString(*rel_cur, val));
1053 OS << Separator << format(Fmt.data(), Address) << name << "\t" << val
1054 << "\n";
1055 return;
1056 }
1057 rel_cur++;
1058 }
1059 };
1060
1061 while(!HeadTail.first.empty()) {
1062 OS << Separator;
1063 Separator = "\n";
1064 if (SP && (PrintSource || PrintLines))
1065 SP->printSourceLine(OS, Address, "");
1066 printLead(Bytes, Address, OS);
1067 OS << Preamble;
1068 Preamble = " ";
1069 StringRef Inst;
1070 auto Duplex = HeadTail.first.split('\v');
1071 if(!Duplex.second.empty()){
1072 OS << Duplex.first;
1073 OS << "; ";
1074 Inst = Duplex.second;
1075 }
1076 else
1077 Inst = HeadTail.first;
1078 OS << Inst;
1079 HeadTail = HeadTail.second.split('\n');
1080 if (HeadTail.first.empty())
1081 OS << " } " << PacketBundle.second;
1082 PrintReloc();
1083 Bytes = Bytes.slice(4);
1084 Address += 4;
1085 }
1086 }
1087};
1088HexagonPrettyPrinter HexagonPrettyPrinterInst;
1089
1090class AMDGCNPrettyPrinter : public PrettyPrinter {
1091public:
1092 void printInst(MCInstPrinter &IP, const MCInst *MI, ArrayRef<uint8_t> Bytes,
1093 uint64_t Address, raw_ostream &OS, StringRef Annot,
1094 MCSubtargetInfo const &STI, SourcePrinter *SP,
1095 std::vector<RelocationRef> *Rels) override {
1096 if (SP && (PrintSource || PrintLines))
1097 SP->printSourceLine(OS, Address);
1098
1099 typedef support::ulittle32_t U32;
1100
1101 if (MI) {
1102 SmallString<40> InstStr;
1103 raw_svector_ostream IS(InstStr);
1104
1105 IP.printInst(MI, IS, "", STI);
1106
1107 OS << left_justify(IS.str(), 60);
1108 } else {
1109 // an unrecognized encoding - this is probably data so represent it
1110 // using the .long directive, or .byte directive if fewer than 4 bytes
1111 // remaining
1112 if (Bytes.size() >= 4) {
1113 OS << format("\t.long 0x%08" PRIx32"x" " ",
1114 static_cast<uint32_t>(*reinterpret_cast<const U32*>(Bytes.data())));
1115 OS.indent(42);
1116 } else {
1117 OS << format("\t.byte 0x%02" PRIx8"x", Bytes[0]);
1118 for (unsigned int i = 1; i < Bytes.size(); i++)
1119 OS << format(", 0x%02" PRIx8"x", Bytes[i]);
1120 OS.indent(55 - (6 * Bytes.size()));
1121 }
1122 }
1123
1124 OS << format("// %012" PRIX64"l" "X" ": ", Address);
1125 if (Bytes.size() >=4) {
1126 for (auto D : makeArrayRef(reinterpret_cast<const U32*>(Bytes.data()),
1127 Bytes.size() / sizeof(U32)))
1128 // D should be explicitly casted to uint32_t here as it is passed
1129 // by format to snprintf as vararg.
1130 OS << format("%08" PRIX32"X" " ", static_cast<uint32_t>(D));
1131 } else {
1132 for (unsigned int i = 0; i < Bytes.size(); i++)
1133 OS << format("%02" PRIX8"X" " ", Bytes[i]);
1134 }
1135
1136 if (!Annot.empty())
1137 OS << "// " << Annot;
1138 }
1139};
1140AMDGCNPrettyPrinter AMDGCNPrettyPrinterInst;
1141
1142class BPFPrettyPrinter : public PrettyPrinter {
1143public:
1144 void printInst(MCInstPrinter &IP, const MCInst *MI, ArrayRef<uint8_t> Bytes,
1145 uint64_t Address, raw_ostream &OS, StringRef Annot,
1146 MCSubtargetInfo const &STI, SourcePrinter *SP,
1147 std::vector<RelocationRef> *Rels) override {
1148 if (SP && (PrintSource || PrintLines))
1149 SP->printSourceLine(OS, Address);
1150 if (!NoLeadingAddr)
1151 OS << format("%8" PRId64"l" "d" ":", Address / 8);
1152 if (!NoShowRawInsn) {
1153 OS << "\t";
1154 dumpBytes(Bytes, OS);
1155 }
1156 if (MI)
1157 IP.printInst(MI, OS, "", STI);
1158 else
1159 OS << " <unknown>";
1160 }
1161};
1162BPFPrettyPrinter BPFPrettyPrinterInst;
1163
1164PrettyPrinter &selectPrettyPrinter(Triple const &Triple) {
1165 switch(Triple.getArch()) {
1166 default:
1167 return PrettyPrinterInst;
1168 case Triple::hexagon:
1169 return HexagonPrettyPrinterInst;
1170 case Triple::amdgcn:
1171 return AMDGCNPrettyPrinterInst;
1172 case Triple::bpfel:
1173 case Triple::bpfeb:
1174 return BPFPrettyPrinterInst;
1175 }
1176}
1177}
1178
1179static uint8_t getElfSymbolType(const ObjectFile *Obj, const SymbolRef &Sym) {
1180 assert(Obj->isELF())(static_cast <bool> (Obj->isELF()) ? void (0) : __assert_fail
("Obj->isELF()", "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 1180, __extension__ __PRETTY_FUNCTION__))
;
1181 if (auto *Elf32LEObj = dyn_cast<ELF32LEObjectFile>(Obj))
1182 return Elf32LEObj->getSymbol(Sym.getRawDataRefImpl())->getType();
1183 if (auto *Elf64LEObj = dyn_cast<ELF64LEObjectFile>(Obj))
1184 return Elf64LEObj->getSymbol(Sym.getRawDataRefImpl())->getType();
1185 if (auto *Elf32BEObj = dyn_cast<ELF32BEObjectFile>(Obj))
1186 return Elf32BEObj->getSymbol(Sym.getRawDataRefImpl())->getType();
1187 if (auto *Elf64BEObj = cast<ELF64BEObjectFile>(Obj))
1188 return Elf64BEObj->getSymbol(Sym.getRawDataRefImpl())->getType();
1189 llvm_unreachable("Unsupported binary format")::llvm::llvm_unreachable_internal("Unsupported binary format"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 1189)
;
1190}
1191
1192template <class ELFT> static void
1193addDynamicElfSymbols(const ELFObjectFile<ELFT> *Obj,
1194 std::map<SectionRef, SectionSymbolsTy> &AllSymbols) {
1195 for (auto Symbol : Obj->getDynamicSymbolIterators()) {
1196 uint8_t SymbolType = Symbol.getELFType();
1197 if (SymbolType != ELF::STT_FUNC || Symbol.getSize() == 0)
1198 continue;
1199
1200 Expected<uint64_t> AddressOrErr = Symbol.getAddress();
1201 if (!AddressOrErr)
1202 report_error(Obj->getFileName(), AddressOrErr.takeError());
1203 uint64_t Address = *AddressOrErr;
1204
1205 Expected<StringRef> Name = Symbol.getName();
1206 if (!Name)
1207 report_error(Obj->getFileName(), Name.takeError());
1208 if (Name->empty())
1209 continue;
1210
1211 Expected<section_iterator> SectionOrErr = Symbol.getSection();
1212 if (!SectionOrErr)
1213 report_error(Obj->getFileName(), SectionOrErr.takeError());
1214 section_iterator SecI = *SectionOrErr;
1215 if (SecI == Obj->section_end())
1216 continue;
1217
1218 AllSymbols[*SecI].emplace_back(Address, *Name, SymbolType);
1219 }
1220}
1221
1222static void
1223addDynamicElfSymbols(const ObjectFile *Obj,
1224 std::map<SectionRef, SectionSymbolsTy> &AllSymbols) {
1225 assert(Obj->isELF())(static_cast <bool> (Obj->isELF()) ? void (0) : __assert_fail
("Obj->isELF()", "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 1225, __extension__ __PRETTY_FUNCTION__))
;
1226 if (auto *Elf32LEObj = dyn_cast<ELF32LEObjectFile>(Obj))
1227 addDynamicElfSymbols(Elf32LEObj, AllSymbols);
1228 else if (auto *Elf64LEObj = dyn_cast<ELF64LEObjectFile>(Obj))
1229 addDynamicElfSymbols(Elf64LEObj, AllSymbols);
1230 else if (auto *Elf32BEObj = dyn_cast<ELF32BEObjectFile>(Obj))
1231 addDynamicElfSymbols(Elf32BEObj, AllSymbols);
1232 else if (auto *Elf64BEObj = cast<ELF64BEObjectFile>(Obj))
1233 addDynamicElfSymbols(Elf64BEObj, AllSymbols);
1234 else
1235 llvm_unreachable("Unsupported binary format")::llvm::llvm_unreachable_internal("Unsupported binary format"
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/llvm-objdump/llvm-objdump.cpp"
, 1235)
;
1236}
1237
1238static void DisassembleObject(const ObjectFile *Obj, bool InlineRelocs) {
1239 if (StartAddress > StopAddress)
1240 error("Start address should be less than stop address");
1241
1242 const Target *TheTarget = getTarget(Obj);
1243
1244 // Package up features to be passed to target/subtarget
1245 SubtargetFeatures Features = Obj->getFeatures();
1246 if (MAttrs.size()) {
1247 for (unsigned i = 0; i != MAttrs.size(); ++i)
1248 Features.AddFeature(MAttrs[i]);
1249 }
1250
1251 std::unique_ptr<const MCRegisterInfo> MRI(
1252 TheTarget->createMCRegInfo(TripleName));
1253 if (!MRI)
1254 report_error(Obj->getFileName(), "no register info for target " +
1255 TripleName);
1256
1257 // Set up disassembler.
1258 std::unique_ptr<const MCAsmInfo> AsmInfo(
1259 TheTarget->createMCAsmInfo(*MRI, TripleName));
1260 if (!AsmInfo)
1261 report_error(Obj->getFileName(), "no assembly info for target " +
1262 TripleName);
1263 std::unique_ptr<const MCSubtargetInfo> STI(
1264 TheTarget->createMCSubtargetInfo(TripleName, MCPU, Features.getString()));
1265 if (!STI)
1266 report_error(Obj->getFileName(), "no subtarget info for target " +
1267 TripleName);
1268 std::unique_ptr<const MCInstrInfo> MII(TheTarget->createMCInstrInfo());
1269 if (!MII)
1270 report_error(Obj->getFileName(), "no instruction info for target " +
1271 TripleName);
1272 MCObjectFileInfo MOFI;
1273 MCContext Ctx(AsmInfo.get(), MRI.get(), &MOFI);
1274 // FIXME: for now initialize MCObjectFileInfo with default values
1275 MOFI.InitMCObjectFileInfo(Triple(TripleName), false, Ctx);
1276
1277 std::unique_ptr<MCDisassembler> DisAsm(
1278 TheTarget->createMCDisassembler(*STI, Ctx));
1279 if (!DisAsm)
1280 report_error(Obj->getFileName(), "no disassembler for target " +
1281 TripleName);
1282
1283 std::unique_ptr<const MCInstrAnalysis> MIA(
1284 TheTarget->createMCInstrAnalysis(MII.get()));
1285
1286 int AsmPrinterVariant = AsmInfo->getAssemblerDialect();
1287 std::unique_ptr<MCInstPrinter> IP(TheTarget->createMCInstPrinter(
1288 Triple(TripleName), AsmPrinterVariant, *AsmInfo, *MII, *MRI));
1289 if (!IP)
1290 report_error(Obj->getFileName(), "no instruction printer for target " +
1291 TripleName);
1292 IP->setPrintImmHex(PrintImmHex);
1293 PrettyPrinter &PIP = selectPrettyPrinter(Triple(TripleName));
1294
1295 StringRef Fmt = Obj->getBytesInAddress() > 4 ? "\t\t%016" PRIx64"l" "x" ": " :
1296 "\t\t\t%08" PRIx64"l" "x" ": ";
1297
1298 SourcePrinter SP(Obj, TheTarget->getName());
1299
1300 // Create a mapping, RelocSecs = SectionRelocMap[S], where sections
1301 // in RelocSecs contain the relocations for section S.
1302 std::error_code EC;
1303 std::map<SectionRef, SmallVector<SectionRef, 1>> SectionRelocMap;
1304 for (const SectionRef &Section : ToolSectionFilter(*Obj)) {
1305 section_iterator Sec2 = Section.getRelocatedSection();
1306 if (Sec2 != Obj->section_end())
1307 SectionRelocMap[*Sec2].push_back(Section);
1308 }
1309
1310 // Create a mapping from virtual address to symbol name. This is used to
1311 // pretty print the symbols while disassembling.
1312 std::map<SectionRef, SectionSymbolsTy> AllSymbols;
1313 SectionSymbolsTy AbsoluteSymbols;
1314 for (const SymbolRef &Symbol : Obj->symbols()) {
1315 Expected<uint64_t> AddressOrErr = Symbol.getAddress();
1316 if (!AddressOrErr)
1317 report_error(Obj->getFileName(), AddressOrErr.takeError());
1318 uint64_t Address = *AddressOrErr;
1319
1320 Expected<StringRef> Name = Symbol.getName();
1321 if (!Name)
1322 report_error(Obj->getFileName(), Name.takeError());
1323 if (Name->empty())
1324 continue;
1325
1326 Expected<section_iterator> SectionOrErr = Symbol.getSection();
1327 if (!SectionOrErr)
1328 report_error(Obj->getFileName(), SectionOrErr.takeError());
1329
1330 uint8_t SymbolType = ELF::STT_NOTYPE;
1331 if (Obj->isELF())
1332 SymbolType = getElfSymbolType(Obj, Symbol);
1333
1334 section_iterator SecI = *SectionOrErr;
1335 if (SecI != Obj->section_end())
1336 AllSymbols[*SecI].emplace_back(Address, *Name, SymbolType);
1337 else
1338 AbsoluteSymbols.emplace_back(Address, *Name, SymbolType);
1339
1340
1341 }
1342 if (AllSymbols.empty() && Obj->isELF())
1343 addDynamicElfSymbols(Obj, AllSymbols);
1344
1345 // Create a mapping from virtual address to section.
1346 std::vector<std::pair<uint64_t, SectionRef>> SectionAddresses;
1347 for (SectionRef Sec : Obj->sections())
1348 SectionAddresses.emplace_back(Sec.getAddress(), Sec);
1349 array_pod_sort(SectionAddresses.begin(), SectionAddresses.end());
1350
1351 // Linked executables (.exe and .dll files) typically don't include a real
1352 // symbol table but they might contain an export table.
1353 if (const auto *COFFObj = dyn_cast<COFFObjectFile>(Obj)) {
1354 for (const auto &ExportEntry : COFFObj->export_directories()) {
1355 StringRef Name;
1356 error(ExportEntry.getSymbolName(Name));
1357 if (Name.empty())
1358 continue;
1359 uint32_t RVA;
1360 error(ExportEntry.getExportRVA(RVA));
1361
1362 uint64_t VA = COFFObj->getImageBase() + RVA;
1363 auto Sec = std::upper_bound(
1364 SectionAddresses.begin(), SectionAddresses.end(), VA,
1365 [](uint64_t LHS, const std::pair<uint64_t, SectionRef> &RHS) {
1366 return LHS < RHS.first;
1367 });
1368 if (Sec != SectionAddresses.begin())
1369 --Sec;
1370 else
1371 Sec = SectionAddresses.end();
1372
1373 if (Sec != SectionAddresses.end())
1374 AllSymbols[Sec->second].emplace_back(VA, Name, ELF::STT_NOTYPE);
1375 else
1376 AbsoluteSymbols.emplace_back(VA, Name, ELF::STT_NOTYPE);
1377 }
1378 }
1379
1380 // Sort all the symbols, this allows us to use a simple binary search to find
1381 // a symbol near an address.
1382 for (std::pair<const SectionRef, SectionSymbolsTy> &SecSyms : AllSymbols)
1383 array_pod_sort(SecSyms.second.begin(), SecSyms.second.end());
1384 array_pod_sort(AbsoluteSymbols.begin(), AbsoluteSymbols.end());
1385
1386 for (const SectionRef &Section : ToolSectionFilter(*Obj)) {
1387 if (!DisassembleAll && (!Section.isText() || Section.isVirtual()))
1388 continue;
1389
1390 uint64_t SectionAddr = Section.getAddress();
1391 uint64_t SectSize = Section.getSize();
1392 if (!SectSize)
1393 continue;
1394
1395 // Get the list of all the symbols in this section.
1396 SectionSymbolsTy &Symbols = AllSymbols[Section];
1397 std::vector<uint64_t> DataMappingSymsAddr;
1398 std::vector<uint64_t> TextMappingSymsAddr;
1399 if (isArmElf(Obj)) {
1400 for (const auto &Symb : Symbols) {
1401 uint64_t Address = std::get<0>(Symb);
1402 StringRef Name = std::get<1>(Symb);
1403 if (Name.startswith("$d"))
1404 DataMappingSymsAddr.push_back(Address - SectionAddr);
1405 if (Name.startswith("$x"))
1406 TextMappingSymsAddr.push_back(Address - SectionAddr);
1407 if (Name.startswith("$a"))
1408 TextMappingSymsAddr.push_back(Address - SectionAddr);
1409 if (Name.startswith("$t"))
1410 TextMappingSymsAddr.push_back(Address - SectionAddr);
1411 }
1412 }
1413
1414 llvm::sort(DataMappingSymsAddr.begin(), DataMappingSymsAddr.end());
1415 llvm::sort(TextMappingSymsAddr.begin(), TextMappingSymsAddr.end());
1416
1417 if (Obj->isELF() && Obj->getArch() == Triple::amdgcn) {
1418 // AMDGPU disassembler uses symbolizer for printing labels
1419 std::unique_ptr<MCRelocationInfo> RelInfo(
1420 TheTarget->createMCRelocationInfo(TripleName, Ctx));
1421 if (RelInfo) {
1422 std::unique_ptr<MCSymbolizer> Symbolizer(
1423 TheTarget->createMCSymbolizer(
1424 TripleName, nullptr, nullptr, &Symbols, &Ctx, std::move(RelInfo)));
1425 DisAsm->setSymbolizer(std::move(Symbolizer));
1426 }
1427 }
1428
1429 // Make a list of all the relocations for this section.
1430 std::vector<RelocationRef> Rels;
1431 if (InlineRelocs) {
1432 for (const SectionRef &RelocSec : SectionRelocMap[Section]) {
1433 for (const RelocationRef &Reloc : RelocSec.relocations()) {
1434 Rels.push_back(Reloc);
1435 }
1436 }
1437 }
1438
1439 // Sort relocations by address.
1440 llvm::sort(Rels.begin(), Rels.end(), RelocAddressLess);
1441
1442 StringRef SegmentName = "";
1443 if (const MachOObjectFile *MachO = dyn_cast<const MachOObjectFile>(Obj)) {
1444 DataRefImpl DR = Section.getRawDataRefImpl();
1445 SegmentName = MachO->getSectionFinalSegmentName(DR);
1446 }
1447 StringRef SectionName;
1448 error(Section.getName(SectionName));
1449
1450 // If the section has no symbol at the start, just insert a dummy one.
1451 if (Symbols.empty() || std::get<0>(Symbols[0]) != 0) {
1452 Symbols.insert(
1453 Symbols.begin(),
1454 std::make_tuple(SectionAddr, SectionName,
1455 Section.isText() ? ELF::STT_FUNC : ELF::STT_OBJECT));
1456 }
1457
1458 SmallString<40> Comments;
1459 raw_svector_ostream CommentStream(Comments);
1460
1461 StringRef BytesStr;
1462 error(Section.getContents(BytesStr));
1463 ArrayRef<uint8_t> Bytes(reinterpret_cast<const uint8_t *>(BytesStr.data()),
1464 BytesStr.size());
1465
1466 uint64_t Size;
1467 uint64_t Index;
1468 bool PrintedSection = false;
1469
1470 std::vector<RelocationRef>::const_iterator rel_cur = Rels.begin();
1471 std::vector<RelocationRef>::const_iterator rel_end = Rels.end();
1472 // Disassemble symbol by symbol.
1473 for (unsigned si = 0, se = Symbols.size(); si != se; ++si) {
1474 uint64_t Start = std::get<0>(Symbols[si]) - SectionAddr;
1475 // The end is either the section end or the beginning of the next
1476 // symbol.
1477 uint64_t End =
1478 (si == se - 1) ? SectSize : std::get<0>(Symbols[si + 1]) - SectionAddr;
1479 // Don't try to disassemble beyond the end of section contents.
1480 if (End > SectSize)
1481 End = SectSize;
1482 // If this symbol has the same address as the next symbol, then skip it.
1483 if (Start >= End)
1484 continue;
1485
1486 // Check if we need to skip symbol
1487 // Skip if the symbol's data is not between StartAddress and StopAddress
1488 if (End + SectionAddr < StartAddress ||
1489 Start + SectionAddr > StopAddress) {
1490 continue;
1491 }
1492
1493 /// Skip if user requested specific symbols and this is not in the list
1494 if (!DisasmFuncsSet.empty() &&
1495 !DisasmFuncsSet.count(std::get<1>(Symbols[si])))
1496 continue;
1497
1498 if (!PrintedSection) {
1499 PrintedSection = true;
1500 outs() << "Disassembly of section ";
1501 if (!SegmentName.empty())
1502 outs() << SegmentName << ",";
1503 outs() << SectionName << ':';
1504 }
1505
1506 // Stop disassembly at the stop address specified
1507 if (End + SectionAddr > StopAddress)
1508 End = StopAddress - SectionAddr;
1509
1510 if (Obj->isELF() && Obj->getArch() == Triple::amdgcn) {
1511 if (std::get<2>(Symbols[si]) == ELF::STT_AMDGPU_HSA_KERNEL) {
1512 // skip amd_kernel_code_t at the begining of kernel symbol (256 bytes)
1513 Start += 256;
1514 }
1515 if (si == se - 1 ||
1516 std::get<2>(Symbols[si + 1]) == ELF::STT_AMDGPU_HSA_KERNEL) {
1517 // cut trailing zeroes at the end of kernel
1518 // cut up to 256 bytes
1519 const uint64_t EndAlign = 256;
1520 const auto Limit = End - (std::min)(EndAlign, End - Start);
1521 while (End > Limit &&
1522 *reinterpret_cast<const support::ulittle32_t*>(&Bytes[End - 4]) == 0)
1523 End -= 4;
1524 }
1525 }
1526
1527 auto PrintSymbol = [](StringRef Name) {
1528 outs() << '\n' << Name << ":\n";
1529 };
1530 StringRef SymbolName = std::get<1>(Symbols[si]);
1531 if (Demangle.getValue() == "" || Demangle.getValue() == "itanium") {
1532 char *DemangledSymbol = nullptr;
1533 size_t Size = 0;
1534 int Status;
1535 DemangledSymbol =
1536 itaniumDemangle(SymbolName.data(), DemangledSymbol, &Size, &Status);
1537 if (Status == 0)
1538 PrintSymbol(StringRef(DemangledSymbol));
1539 else
1540 PrintSymbol(SymbolName);
1541
1542 if (Size != 0)
1543 free(DemangledSymbol);
1544 } else
1545 PrintSymbol(SymbolName);
1546
1547 // Don't print raw contents of a virtual section. A virtual section
1548 // doesn't have any contents in the file.
1549 if (Section.isVirtual()) {
1550 outs() << "...\n";
1551 continue;
1552 }
1553
1554#ifndef NDEBUG
1555 raw_ostream &DebugOut = DebugFlag ? dbgs() : nulls();
1556#else
1557 raw_ostream &DebugOut = nulls();
1558#endif
1559
1560 for (Index = Start; Index < End; Index += Size) {
1561 MCInst Inst;
1562
1563 if (Index + SectionAddr < StartAddress ||
1564 Index + SectionAddr > StopAddress) {
1565 // skip byte by byte till StartAddress is reached
1566 Size = 1;
1567 continue;
1568 }
1569 // AArch64 ELF binaries can interleave data and text in the
1570 // same section. We rely on the markers introduced to
1571 // understand what we need to dump. If the data marker is within a
1572 // function, it is denoted as a word/short etc
1573 if (isArmElf(Obj) && std::get<2>(Symbols[si]) != ELF::STT_OBJECT &&
1574 !DisassembleAll) {
1575 uint64_t Stride = 0;
1576
1577 auto DAI = std::lower_bound(DataMappingSymsAddr.begin(),
1578 DataMappingSymsAddr.end(), Index);
1579 if (DAI != DataMappingSymsAddr.end() && *DAI == Index) {
1580 // Switch to data.
1581 while (Index < End) {
1582 outs() << format("%8" PRIx64"l" "x" ":", SectionAddr + Index);
1583 outs() << "\t";
1584 if (Index + 4 <= End) {
1585 Stride = 4;
1586 dumpBytes(Bytes.slice(Index, 4), outs());
1587 outs() << "\t.word\t";
1588 uint32_t Data = 0;
1589 if (Obj->isLittleEndian()) {
1590 const auto Word =
1591 reinterpret_cast<const support::ulittle32_t *>(
1592 Bytes.data() + Index);
1593 Data = *Word;
1594 } else {
1595 const auto Word = reinterpret_cast<const support::ubig32_t *>(
1596 Bytes.data() + Index);
1597 Data = *Word;
1598 }
1599 outs() << "0x" << format("%08" PRIx32"x", Data);
1600 } else if (Index + 2 <= End) {
1601 Stride = 2;
1602 dumpBytes(Bytes.slice(Index, 2), outs());
1603 outs() << "\t\t.short\t";
1604 uint16_t Data = 0;
1605 if (Obj->isLittleEndian()) {
1606 const auto Short =
1607 reinterpret_cast<const support::ulittle16_t *>(
1608 Bytes.data() + Index);
1609 Data = *Short;
1610 } else {
1611 const auto Short =
1612 reinterpret_cast<const support::ubig16_t *>(Bytes.data() +
1613 Index);
1614 Data = *Short;
1615 }
1616 outs() << "0x" << format("%04" PRIx16"x", Data);
1617 } else {
1618 Stride = 1;
1619 dumpBytes(Bytes.slice(Index, 1), outs());
1620 outs() << "\t\t.byte\t";
1621 outs() << "0x" << format("%02" PRIx8"x", Bytes.slice(Index, 1)[0]);
1622 }
1623 Index += Stride;
1624 outs() << "\n";
1625 auto TAI = std::lower_bound(TextMappingSymsAddr.begin(),
1626 TextMappingSymsAddr.end(), Index);
1627 if (TAI != TextMappingSymsAddr.end() && *TAI == Index)
1628 break;
1629 }
1630 }
1631 }
1632
1633 // If there is a data symbol inside an ELF text section and we are only
1634 // disassembling text (applicable all architectures),
1635 // we are in a situation where we must print the data and not
1636 // disassemble it.
1637 if (Obj->isELF() && std::get<2>(Symbols[si]) == ELF::STT_OBJECT &&
1638 !DisassembleAll && Section.isText()) {
1639 // print out data up to 8 bytes at a time in hex and ascii
1640 uint8_t AsciiData[9] = {'\0'};
1641 uint8_t Byte;
1642 int NumBytes = 0;
1643
1644 for (Index = Start; Index < End; Index += 1) {
1645 if (((SectionAddr + Index) < StartAddress) ||
1646 ((SectionAddr + Index) > StopAddress))
1647 continue;
1648 if (NumBytes == 0) {
1649 outs() << format("%8" PRIx64"l" "x" ":", SectionAddr + Index);
1650 outs() << "\t";
1651 }
1652 Byte = Bytes.slice(Index)[0];
1653 outs() << format(" %02x", Byte);
1654 AsciiData[NumBytes] = isPrint(Byte) ? Byte : '.';
1655
1656 uint8_t IndentOffset = 0;
1657 NumBytes++;
1658 if (Index == End - 1 || NumBytes > 8) {
1659 // Indent the space for less than 8 bytes data.
1660 // 2 spaces for byte and one for space between bytes
1661 IndentOffset = 3 * (8 - NumBytes);
1662 for (int Excess = 8 - NumBytes; Excess < 8; Excess++)
1663 AsciiData[Excess] = '\0';
1664 NumBytes = 8;
1665 }
1666 if (NumBytes == 8) {
1667 AsciiData[8] = '\0';
1668 outs() << std::string(IndentOffset, ' ') << " ";
1669 outs() << reinterpret_cast<char *>(AsciiData);
1670 outs() << '\n';
1671 NumBytes = 0;
1672 }
1673 }
1674 }
1675 if (Index >= End)
1676 break;
1677
1678 // Disassemble a real instruction or a data when disassemble all is
1679 // provided
1680 bool Disassembled = DisAsm->getInstruction(Inst, Size, Bytes.slice(Index),
1681 SectionAddr + Index, DebugOut,
1682 CommentStream);
1683 if (Size == 0)
1684 Size = 1;
1685
1686 PIP.printInst(*IP, Disassembled ? &Inst : nullptr,
1687 Bytes.slice(Index, Size), SectionAddr + Index, outs(), "",
1688 *STI, &SP, &Rels);
1689 outs() << CommentStream.str();
1690 Comments.clear();
1691
1692 // Try to resolve the target of a call, tail call, etc. to a specific
1693 // symbol.
1694 if (MIA && (MIA->isCall(Inst) || MIA->isUnconditionalBranch(Inst) ||
1695 MIA->isConditionalBranch(Inst))) {
1696 uint64_t Target;
1697 if (MIA->evaluateBranch(Inst, SectionAddr + Index, Size, Target)) {
1698 // In a relocatable object, the target's section must reside in
1699 // the same section as the call instruction or it is accessed
1700 // through a relocation.
1701 //
1702 // In a non-relocatable object, the target may be in any section.
1703 //
1704 // N.B. We don't walk the relocations in the relocatable case yet.
1705 auto *TargetSectionSymbols = &Symbols;
1706 if (!Obj->isRelocatableObject()) {
1707 auto SectionAddress = std::upper_bound(
1708 SectionAddresses.begin(), SectionAddresses.end(), Target,
1709 [](uint64_t LHS,
1710 const std::pair<uint64_t, SectionRef> &RHS) {
1711 return LHS < RHS.first;
1712 });
1713 if (SectionAddress != SectionAddresses.begin()) {
1714 --SectionAddress;
1715 TargetSectionSymbols = &AllSymbols[SectionAddress->second];
1716 } else {
1717 TargetSectionSymbols = &AbsoluteSymbols;
1718 }
1719 }
1720
1721 // Find the first symbol in the section whose offset is less than
1722 // or equal to the target. If there isn't a section that contains
1723 // the target, find the nearest preceding absolute symbol.
1724 auto TargetSym = std::upper_bound(
1725 TargetSectionSymbols->begin(), TargetSectionSymbols->end(),
1726 Target, [](uint64_t LHS,
1727 const std::tuple<uint64_t, StringRef, uint8_t> &RHS) {
1728 return LHS < std::get<0>(RHS);
1729 });
1730 if (TargetSym == TargetSectionSymbols->begin()) {
1731 TargetSectionSymbols = &AbsoluteSymbols;
1732 TargetSym = std::upper_bound(
1733 AbsoluteSymbols.begin(), AbsoluteSymbols.end(),
1734 Target, [](uint64_t LHS,
1735 const std::tuple<uint64_t, StringRef, uint8_t> &RHS) {
1736 return LHS < std::get<0>(RHS);
1737 });
1738 }
1739 if (TargetSym != TargetSectionSymbols->begin()) {
1740 --TargetSym;
1741 uint64_t TargetAddress = std::get<0>(*TargetSym);
1742 StringRef TargetName = std::get<1>(*TargetSym);
1743 outs() << " <" << TargetName;
1744 uint64_t Disp = Target - TargetAddress;
1745 if (Disp)
1746 outs() << "+0x" << Twine::utohexstr(Disp);
1747 outs() << '>';
1748 }
1749 }
1750 }
1751 outs() << "\n";
1752
1753 // Hexagon does this in pretty printer
1754 if (Obj->getArch() != Triple::hexagon)
1755 // Print relocation for instruction.
1756 while (rel_cur != rel_end) {
1757 bool hidden = getHidden(*rel_cur);
1758 uint64_t addr = rel_cur->getOffset();
1759 SmallString<16> name;
1760 SmallString<32> val;
1761
1762 // If this relocation is hidden, skip it.
1763 if (hidden || ((SectionAddr + addr) < StartAddress)) {
1764 ++rel_cur;
1765 continue;
1766 }
1767
1768 // Stop when rel_cur's address is past the current instruction.
1769 if (addr >= Index + Size) break;
1770 rel_cur->getTypeName(name);
1771 error(getRelocationValueString(*rel_cur, val));
1772 outs() << format(Fmt.data(), SectionAddr + addr) << name
1773 << "\t" << val << "\n";
1774 ++rel_cur;
1775 }
1776 }
1777 }
1778 }
1779}
1780
1781void llvm::PrintRelocations(const ObjectFile *Obj) {
1782 StringRef Fmt = Obj->getBytesInAddress() > 4 ? "%016" PRIx64"l" "x" :
1783 "%08" PRIx64"l" "x";
1784 // Regular objdump doesn't print relocations in non-relocatable object
1785 // files.
1786 if (!Obj->isRelocatableObject())
1787 return;
1788
1789 for (const SectionRef &Section : ToolSectionFilter(*Obj)) {
1790 if (Section.relocation_begin() == Section.relocation_end())
1791 continue;
1792 StringRef secname;
1793 error(Section.getName(secname));
1794 outs() << "RELOCATION RECORDS FOR [" << secname << "]:\n";
1795 for (const RelocationRef &Reloc : Section.relocations()) {
1796 bool hidden = getHidden(Reloc);
1797 uint64_t address = Reloc.getOffset();
1798 SmallString<32> relocname;
1799 SmallString<32> valuestr;
1800 if (address < StartAddress || address > StopAddress || hidden)
1801 continue;
1802 Reloc.getTypeName(relocname);
1803 error(getRelocationValueString(Reloc, valuestr));
1804 outs() << format(Fmt.data(), address) << " " << relocname << " "
1805 << valuestr << "\n";
1806 }
1807 outs() << "\n";
1808 }
1809}
1810
1811void llvm::PrintDynamicRelocations(const ObjectFile *Obj) {
1812
1813 // For the moment, this option is for ELF only
1814 if (!Obj->isELF())
1815 return;
1816
1817 const auto *Elf = dyn_cast<ELFObjectFileBase>(Obj);
1818
1819 if (!Elf || Elf->getEType() != ELF::ET_DYN) {
1820 error("not a dynamic object");
1821 return;
1822 }
1823
1824 StringRef Fmt = Obj->getBytesInAddress() > 4 ? "%016" PRIx64"l" "x" : "%08" PRIx64"l" "x";
1825
1826 std::vector<SectionRef> DynRelSec = Obj->dynamic_relocation_sections();
1827 if (DynRelSec.empty())
1828 return;
1829
1830 outs() << "DYNAMIC RELOCATION RECORDS\n";
1831 for (const SectionRef &Section : DynRelSec) {
1832 if (Section.relocation_begin() == Section.relocation_end())
1833 continue;
1834 for (const RelocationRef &Reloc : Section.relocations()) {
1835 uint64_t address = Reloc.getOffset();
1836 SmallString<32> relocname;
1837 SmallString<32> valuestr;
1838 Reloc.getTypeName(relocname);
1839 error(getRelocationValueString(Reloc, valuestr));
1840 outs() << format(Fmt.data(), address) << " " << relocname << " "
1841 << valuestr << "\n";
1842 }
1843 }
1844}
1845
1846void llvm::PrintSectionHeaders(const ObjectFile *Obj) {
1847 outs() << "Sections:\n"
1848 "Idx Name Size Address Type\n";
1849 for (const SectionRef &Section : ToolSectionFilter(*Obj)) {
1850 StringRef Name;
1851 error(Section.getName(Name));
1852 uint64_t Address = Section.getAddress();
1853 uint64_t Size = Section.getSize();
1854 bool Text = Section.isText();
1855 bool Data = Section.isData();
1856 bool BSS = Section.isBSS();
1857 std::string Type = (std::string(Text ? "TEXT " : "") +
1858 (Data ? "DATA " : "") + (BSS ? "BSS" : ""));
1859 outs() << format("%3d %-13s %08" PRIx64"l" "x" " %016" PRIx64"l" "x" " %s\n",
1860 (unsigned)Section.getIndex(), Name.str().c_str(), Size,
1861 Address, Type.c_str());
1862 }
1863}
1864
1865void llvm::PrintSectionContents(const ObjectFile *Obj) {
1866 std::error_code EC;
1867 for (const SectionRef &Section : ToolSectionFilter(*Obj)) {
1868 StringRef Name;
1869 StringRef Contents;
1870 error(Section.getName(Name));
1871 uint64_t BaseAddr = Section.getAddress();
1872 uint64_t Size = Section.getSize();
1873 if (!Size)
1874 continue;
1875
1876 outs() << "Contents of section " << Name << ":\n";
1877 if (Section.isBSS()) {
1878 outs() << format("<skipping contents of bss section at [%04" PRIx64"l" "x"
1879 ", %04" PRIx64"l" "x" ")>\n",
1880 BaseAddr, BaseAddr + Size);
1881 continue;
1882 }
1883
1884 error(Section.getContents(Contents));
1885
1886 // Dump out the content as hex and printable ascii characters.
1887 for (std::size_t addr = 0, end = Contents.size(); addr < end; addr += 16) {
1888 outs() << format(" %04" PRIx64"l" "x" " ", BaseAddr + addr);
1889 // Dump line of hex.
1890 for (std::size_t i = 0; i < 16; ++i) {
1891 if (i != 0 && i % 4 == 0)
1892 outs() << ' ';
1893 if (addr + i < end)
1894 outs() << hexdigit((Contents[addr + i] >> 4) & 0xF, true)
1895 << hexdigit(Contents[addr + i] & 0xF, true);
1896 else
1897 outs() << " ";
1898 }
1899 // Print ascii.
1900 outs() << " ";
1901 for (std::size_t i = 0; i < 16 && addr + i < end; ++i) {
1902 if (isPrint(static_cast<unsigned char>(Contents[addr + i]) & 0xFF))
1903 outs() << Contents[addr + i];
1904 else
1905 outs() << ".";
1906 }
1907 outs() << "\n";
1908 }
1909 }
1910}
1911
1912void llvm::PrintSymbolTable(const ObjectFile *o, StringRef ArchiveName,
1913 StringRef ArchitectureName) {
1914 outs() << "SYMBOL TABLE:\n";
1915
1916 if (const COFFObjectFile *coff = dyn_cast<const COFFObjectFile>(o)) {
1917 printCOFFSymbolTable(coff);
1918 return;
1919 }
1920 for (const SymbolRef &Symbol : o->symbols()) {
1921 Expected<uint64_t> AddressOrError = Symbol.getAddress();
1922 if (!AddressOrError)
1923 report_error(ArchiveName, o->getFileName(), AddressOrError.takeError(),
1924 ArchitectureName);
1925 uint64_t Address = *AddressOrError;
1926 if ((Address < StartAddress) || (Address > StopAddress))
1927 continue;
1928 Expected<SymbolRef::Type> TypeOrError = Symbol.getType();
1929 if (!TypeOrError)
1930 report_error(ArchiveName, o->getFileName(), TypeOrError.takeError(),
1931 ArchitectureName);
1932 SymbolRef::Type Type = *TypeOrError;
1933 uint32_t Flags = Symbol.getFlags();
1934 Expected<section_iterator> SectionOrErr = Symbol.getSection();
1935 if (!SectionOrErr)
1936 report_error(ArchiveName, o->getFileName(), SectionOrErr.takeError(),
1937 ArchitectureName);
1938 section_iterator Section = *SectionOrErr;
1939 StringRef Name;
1940 if (Type == SymbolRef::ST_Debug && Section != o->section_end()) {
1941 Section->getName(Name);
1942 } else {
1943 Expected<StringRef> NameOrErr = Symbol.getName();
1944 if (!NameOrErr)
1945 report_error(ArchiveName, o->getFileName(), NameOrErr.takeError(),
1946 ArchitectureName);
1947 Name = *NameOrErr;
1948 }
1949
1950 bool Global = Flags & SymbolRef::SF_Global;
1951 bool Weak = Flags & SymbolRef::SF_Weak;
1952 bool Absolute = Flags & SymbolRef::SF_Absolute;
1953 bool Common = Flags & SymbolRef::SF_Common;
1954 bool Hidden = Flags & SymbolRef::SF_Hidden;
1955
1956 char GlobLoc = ' ';
1957 if (Type != SymbolRef::ST_Unknown)
1958 GlobLoc = Global ? 'g' : 'l';
1959 char Debug = (Type == SymbolRef::ST_Debug || Type == SymbolRef::ST_File)
1960 ? 'd' : ' ';
1961 char FileFunc = ' ';
1962 if (Type == SymbolRef::ST_File)
1963 FileFunc = 'f';
1964 else if (Type == SymbolRef::ST_Function)
1965 FileFunc = 'F';
1966
1967 const char *Fmt = o->getBytesInAddress() > 4 ? "%016" PRIx64"l" "x" :
1968 "%08" PRIx64"l" "x";
1969
1970 outs() << format(Fmt, Address) << " "
1971 << GlobLoc // Local -> 'l', Global -> 'g', Neither -> ' '
1972 << (Weak ? 'w' : ' ') // Weak?
1973 << ' ' // Constructor. Not supported yet.
1974 << ' ' // Warning. Not supported yet.
1975 << ' ' // Indirect reference to another symbol.
1976 << Debug // Debugging (d) or dynamic (D) symbol.
1977 << FileFunc // Name of function (F), file (f) or object (O).
1978 << ' ';
1979 if (Absolute) {
1980 outs() << "*ABS*";
1981 } else if (Common) {
1982 outs() << "*COM*";
1983 } else if (Section == o->section_end()) {
1984 outs() << "*UND*";
1985 } else {
1986 if (const MachOObjectFile *MachO =
1987 dyn_cast<const MachOObjectFile>(o)) {
1988 DataRefImpl DR = Section->getRawDataRefImpl();
1989 StringRef SegmentName = MachO->getSectionFinalSegmentName(DR);
1990 outs() << SegmentName << ",";
1991 }
1992 StringRef SectionName;
1993 error(Section->getName(SectionName));
1994 outs() << SectionName;
1995 }
1996
1997 outs() << '\t';
1998 if (Common || isa<ELFObjectFileBase>(o)) {
1999 uint64_t Val =
2000 Common ? Symbol.getAlignment() : ELFSymbolRef(Symbol).getSize();
2001 outs() << format("\t %08" PRIx64"l" "x" " ", Val);
2002 }
2003
2004 if (Hidden) {
2005 outs() << ".hidden ";
2006 }
2007 outs() << Name
2008 << '\n';
2009 }
2010}
2011
2012static void PrintUnwindInfo(const ObjectFile *o) {
2013 outs() << "Unwind info:\n\n";
2014
2015 if (const COFFObjectFile *coff = dyn_cast<COFFObjectFile>(o)) {
2016 printCOFFUnwindInfo(coff);
2017 } else if (const MachOObjectFile *MachO = dyn_cast<MachOObjectFile>(o))
2018 printMachOUnwindInfo(MachO);
2019 else {
2020 // TODO: Extract DWARF dump tool to objdump.
2021 errs() << "This operation is only currently supported "
2022 "for COFF and MachO object files.\n";
2023 return;
2024 }
2025}
2026
2027void llvm::printExportsTrie(const ObjectFile *o) {
2028 outs() << "Exports trie:\n";
2029 if (const MachOObjectFile *MachO = dyn_cast<MachOObjectFile>(o))
2030 printMachOExportsTrie(MachO);
2031 else {
2032 errs() << "This operation is only currently supported "
2033 "for Mach-O executable files.\n";
2034 return;
2035 }
2036}
2037
2038void llvm::printRebaseTable(ObjectFile *o) {
2039 outs() << "Rebase table:\n";
2040 if (MachOObjectFile *MachO = dyn_cast<MachOObjectFile>(o))
2041 printMachORebaseTable(MachO);
2042 else {
2043 errs() << "This operation is only currently supported "
2044 "for Mach-O executable files.\n";
2045 return;
2046 }
2047}
2048
2049void llvm::printBindTable(ObjectFile *o) {
2050 outs() << "Bind table:\n";
2051 if (MachOObjectFile *MachO = dyn_cast<MachOObjectFile>(o))
2052 printMachOBindTable(MachO);
2053 else {
2054 errs() << "This operation is only currently supported "
2055 "for Mach-O executable files.\n";
2056 return;
2057 }
2058}
2059
2060void llvm::printLazyBindTable(ObjectFile *o) {
2061 outs() << "Lazy bind table:\n";
2062 if (MachOObjectFile *MachO = dyn_cast<MachOObjectFile>(o))
2063 printMachOLazyBindTable(MachO);
2064 else {
2065 errs() << "This operation is only currently supported "
2066 "for Mach-O executable files.\n";
2067 return;
2068 }
2069}
2070
2071void llvm::printWeakBindTable(ObjectFile *o) {
2072 outs() << "Weak bind table:\n";
2073 if (MachOObjectFile *MachO = dyn_cast<MachOObjectFile>(o))
2074 printMachOWeakBindTable(MachO);
2075 else {
2076 errs() << "This operation is only currently supported "
2077 "for Mach-O executable files.\n";
2078 return;
2079 }
2080}
2081
2082/// Dump the raw contents of the __clangast section so the output can be piped
2083/// into llvm-bcanalyzer.
2084void llvm::printRawClangAST(const ObjectFile *Obj) {
2085 if (outs().is_displayed()) {
2086 errs() << "The -raw-clang-ast option will dump the raw binary contents of "
2087 "the clang ast section.\n"
2088 "Please redirect the output to a file or another program such as "
2089 "llvm-bcanalyzer.\n";
2090 return;
2091 }
2092
2093 StringRef ClangASTSectionName("__clangast");
2094 if (isa<COFFObjectFile>(Obj)) {
2095 ClangASTSectionName = "clangast";
2096 }
2097
2098 Optional<object::SectionRef> ClangASTSection;
2099 for (auto Sec : ToolSectionFilter(*Obj)) {
2100 StringRef Name;
2101 Sec.getName(Name);
2102 if (Name == ClangASTSectionName) {
2103 ClangASTSection = Sec;
2104 break;
2105 }
2106 }
2107 if (!ClangASTSection)
2108 return;
2109
2110 StringRef ClangASTContents;
2111 error(ClangASTSection.getValue().getContents(ClangASTContents));
2112 outs().write(ClangASTContents.data(), ClangASTContents.size());
2113}
2114
2115static void printFaultMaps(const ObjectFile *Obj) {
2116 const char *FaultMapSectionName = nullptr;
2117
2118 if (isa<ELFObjectFileBase>(Obj)) {
2119 FaultMapSectionName = ".llvm_faultmaps";
2120 } else if (isa<MachOObjectFile>(Obj)) {
2121 FaultMapSectionName = "__llvm_faultmaps";
2122 } else {
2123 errs() << "This operation is only currently supported "
2124 "for ELF and Mach-O executable files.\n";
2125 return;
2126 }
2127
2128 Optional<object::SectionRef> FaultMapSection;
2129
2130 for (auto Sec : ToolSectionFilter(*Obj)) {
2131 StringRef Name;
2132 Sec.getName(Name);
2133 if (Name == FaultMapSectionName) {
2134 FaultMapSection = Sec;
2135 break;
2136 }
2137 }
2138
2139 outs() << "FaultMap table:\n";
2140
2141 if (!FaultMapSection.hasValue()) {
2142 outs() << "<not found>\n";
2143 return;
2144 }
2145
2146 StringRef FaultMapContents;
2147 error(FaultMapSection.getValue().getContents(FaultMapContents));
2148
2149 FaultMapParser FMP(FaultMapContents.bytes_begin(),
2150 FaultMapContents.bytes_end());
2151
2152 outs() << FMP;
2153}
2154
2155static void printPrivateFileHeaders(const ObjectFile *o, bool onlyFirst) {
2156 if (o->isELF()) {
2157 printELFFileHeader(o);
2158 return printELFDynamicSection(o);
2159 }
2160 if (o->isCOFF())
2161 return printCOFFFileHeader(o);
2162 if (o->isWasm())
2163 return printWasmFileHeader(o);
2164 if (o->isMachO()) {
2165 printMachOFileHeader(o);
2166 if (!onlyFirst)
2167 printMachOLoadCommands(o);
2168 return;
2169 }
2170 report_error(o->getFileName(), "Invalid/Unsupported object file format");
2171}
2172
2173static void printFileHeaders(const ObjectFile *o) {
2174 if (!o->isELF() && !o->isCOFF())
2175 report_error(o->getFileName(), "Invalid/Unsupported object file format");
2176
2177 Triple::ArchType AT = o->getArch();
2178 outs() << "architecture: " << Triple::getArchTypeName(AT) << "\n";
2179 Expected<uint64_t> StartAddrOrErr = o->getStartAddress();
2180 if (!StartAddrOrErr)
2181 report_error(o->getFileName(), StartAddrOrErr.takeError());
2182 outs() << "start address: "
2183 << format("0x%0*x", o->getBytesInAddress(), StartAddrOrErr.get())
2184 << "\n";
2185}
2186
2187static void printArchiveChild(StringRef Filename, const Archive::Child &C) {
2188 Expected<sys::fs::perms> ModeOrErr = C.getAccessMode();
2189 if (!ModeOrErr) {
2190 errs() << "ill-formed archive entry.\n";
2191 consumeError(ModeOrErr.takeError());
2192 return;
2193 }
2194 sys::fs::perms Mode = ModeOrErr.get();
2195 outs() << ((Mode & sys::fs::owner_read) ? "r" : "-");
2196 outs() << ((Mode & sys::fs::owner_write) ? "w" : "-");
2197 outs() << ((Mode & sys::fs::owner_exe) ? "x" : "-");
2198 outs() << ((Mode & sys::fs::group_read) ? "r" : "-");
2199 outs() << ((Mode & sys::fs::group_write) ? "w" : "-");
2200 outs() << ((Mode & sys::fs::group_exe) ? "x" : "-");
2201 outs() << ((Mode & sys::fs::others_read) ? "r" : "-");
2202 outs() << ((Mode & sys::fs::others_write) ? "w" : "-");
2203 outs() << ((Mode & sys::fs::others_exe) ? "x" : "-");
2204
2205 outs() << " ";
2206
2207 Expected<unsigned> UIDOrErr = C.getUID();
2208 if (!UIDOrErr)
2209 report_error(Filename, UIDOrErr.takeError());
2210 unsigned UID = UIDOrErr.get();
2211 outs() << format("%d/", UID);
2212
2213 Expected<unsigned> GIDOrErr = C.getGID();
2214 if (!GIDOrErr)
2215 report_error(Filename, GIDOrErr.takeError());
2216 unsigned GID = GIDOrErr.get();
2217 outs() << format("%-d ", GID);
2218
2219 Expected<uint64_t> Size = C.getRawSize();
2220 if (!Size)
2221 report_error(Filename, Size.takeError());
2222 outs() << format("%6" PRId64"l" "d", Size.get()) << " ";
2223
2224 StringRef RawLastModified = C.getRawLastModified();
2225 unsigned Seconds;
2226 if (RawLastModified.getAsInteger(10, Seconds))
2227 outs() << "(date: \"" << RawLastModified
2228 << "\" contains non-decimal chars) ";
2229 else {
2230 // Since ctime(3) returns a 26 character string of the form:
2231 // "Sun Sep 16 01:03:52 1973\n\0"
2232 // just print 24 characters.
2233 time_t t = Seconds;
2234 outs() << format("%.24s ", ctime(&t));
2235 }
2236
2237 StringRef Name = "";
2238 Expected<StringRef> NameOrErr = C.getName();
2239 if (!NameOrErr) {
2240 consumeError(NameOrErr.takeError());
2241 Expected<StringRef> RawNameOrErr = C.getRawName();
2242 if (!RawNameOrErr)
2243 report_error(Filename, NameOrErr.takeError());
2244 Name = RawNameOrErr.get();
2245 } else {
2246 Name = NameOrErr.get();
2247 }
2248 outs() << Name << "\n";
2249}
2250
2251static void DumpObject(ObjectFile *o, const Archive *a = nullptr,
2252 const Archive::Child *c = nullptr) {
2253 StringRef ArchiveName = a != nullptr ? a->getFileName() : "";
20
'?' condition is false
2254 // Avoid other output when using a raw option.
2255 if (!RawClangAST) {
21
Assuming the condition is false
22
Taking false branch
2256 outs() << '\n';
2257 if (a)
2258 outs() << a->getFileName() << "(" << o->getFileName() << ")";
2259 else
2260 outs() << o->getFileName();
2261 outs() << ":\tfile format " << o->getFileFormatName() << "\n\n";
2262 }
2263
2264 if (ArchiveHeaders && !MachOOpt)
23
Assuming the condition is true
24
Assuming the condition is true
25
Taking true branch
2265 printArchiveChild(a->getFileName(), *c);
26
Called C++ object pointer is null
2266 if (Disassemble)
2267 DisassembleObject(o, Relocations);
2268 if (Relocations && !Disassemble)
2269 PrintRelocations(o);
2270 if (DynamicRelocations)
2271 PrintDynamicRelocations(o);
2272 if (SectionHeaders)
2273 PrintSectionHeaders(o);
2274 if (SectionContents)
2275 PrintSectionContents(o);
2276 if (SymbolTable)
2277 PrintSymbolTable(o, ArchiveName);
2278 if (UnwindInfo)
2279 PrintUnwindInfo(o);
2280 if (PrivateHeaders || FirstPrivateHeader)
2281 printPrivateFileHeaders(o, FirstPrivateHeader);
2282 if (FileHeaders)
2283 printFileHeaders(o);
2284 if (ExportsTrie)
2285 printExportsTrie(o);
2286 if (Rebase)
2287 printRebaseTable(o);
2288 if (Bind)
2289 printBindTable(o);
2290 if (LazyBind)
2291 printLazyBindTable(o);
2292 if (WeakBind)
2293 printWeakBindTable(o);
2294 if (RawClangAST)
2295 printRawClangAST(o);
2296 if (PrintFaultMaps)
2297 printFaultMaps(o);
2298 if (DwarfDumpType != DIDT_Null) {
2299 std::unique_ptr<DIContext> DICtx = DWARFContext::create(*o);
2300 // Dump the complete DWARF structure.
2301 DIDumpOptions DumpOpts;
2302 DumpOpts.DumpType = DwarfDumpType;
2303 DICtx->dump(outs(), DumpOpts);
2304 }
2305}
2306
2307static void DumpObject(const COFFImportFile *I, const Archive *A,
2308 const Archive::Child *C = nullptr) {
2309 StringRef ArchiveName = A ? A->getFileName() : "";
2310
2311 // Avoid other output when using a raw option.
2312 if (!RawClangAST)
2313 outs() << '\n'
2314 << ArchiveName << "(" << I->getFileName() << ")"
2315 << ":\tfile format COFF-import-file"
2316 << "\n\n";
2317
2318 if (ArchiveHeaders && !MachOOpt)
2319 printArchiveChild(A->getFileName(), *C);
2320 if (SymbolTable)
2321 printCOFFSymbolTable(I);
2322}
2323
2324/// Dump each object file in \a a;
2325static void DumpArchive(const Archive *a) {
2326 Error Err = Error::success();
2327 for (auto &C : a->children(Err)) {
2328 Expected<std::unique_ptr<Binary>> ChildOrErr = C.getAsBinary();
2329 if (!ChildOrErr) {
2330 if (auto E = isNotObjectErrorInvalidFileType(ChildOrErr.takeError()))
2331 report_error(a->getFileName(), C, std::move(E));
2332 continue;
2333 }
2334 if (ObjectFile *o = dyn_cast<ObjectFile>(&*ChildOrErr.get()))
2335 DumpObject(o, a, &C);
2336 else if (COFFImportFile *I = dyn_cast<COFFImportFile>(&*ChildOrErr.get()))
2337 DumpObject(I, a, &C);
2338 else
2339 report_error(a->getFileName(), object_error::invalid_file_type);
2340 }
2341 if (Err)
2342 report_error(a->getFileName(), std::move(Err));
2343}
2344
2345/// Open file and figure out how to dump it.
2346static void DumpInput(StringRef file) {
2347
2348 // If we are using the Mach-O specific object file parser, then let it parse
2349 // the file and process the command line options. So the -arch flags can
2350 // be used to select specific slices, etc.
2351 if (MachOOpt) {
12
Assuming the condition is false
13
Taking false branch
2352 ParseInputMachO(file);
2353 return;
2354 }
2355
2356 // Attempt to open the binary.
2357 Expected<OwningBinary<Binary>> BinaryOrErr = createBinary(file);
2358 if (!BinaryOrErr)
14
Taking false branch
2359 report_error(file, BinaryOrErr.takeError());
2360 Binary &Binary = *BinaryOrErr.get().getBinary();
2361
2362 if (Archive *a = dyn_cast<Archive>(&Binary))
15
Taking false branch
2363 DumpArchive(a);
2364 else if (ObjectFile *o = dyn_cast<ObjectFile>(&Binary))
16
Assuming 'o' is non-null
17
Taking true branch
2365 DumpObject(o);
18
Passing null pointer value via 2nd parameter 'a'
19
Calling 'DumpObject'
2366 else
2367 report_error(file, object_error::invalid_file_type);
2368}
2369
2370int main(int argc, char **argv) {
2371 InitLLVM X(argc, argv);
2372
2373 // Initialize targets and assembly printers/parsers.
2374 llvm::InitializeAllTargetInfos();
2375 llvm::InitializeAllTargetMCs();
2376 llvm::InitializeAllDisassemblers();
2377
2378 // Register the target printer for --version.
2379 cl::AddExtraVersionPrinter(TargetRegistry::printRegisteredTargetsForVersion);
2380
2381 cl::ParseCommandLineOptions(argc, argv, "llvm object file dumper\n");
2382 TripleName = Triple::normalize(TripleName);
2383
2384 ToolName = argv[0];
2385
2386 // Defaults to a.out if no filenames specified.
2387 if (InputFilenames.size() == 0)
1
Assuming the condition is false
2
Taking false branch
2388 InputFilenames.push_back("a.out");
2389
2390 if (AllHeaders)
3
Assuming the condition is false
4
Taking false branch
2391 PrivateHeaders = Relocations = SectionHeaders = SymbolTable = true;
2392
2393 if (DisassembleAll || PrintSource || PrintLines)
5
Assuming the condition is true
2394 Disassemble = true;
2395
2396 if (Demangle.getValue() != "none" && Demangle.getValue() != "" &&
6
Taking true branch
2397 Demangle.getValue() != "itanium")
2398 warn("Unsupported demangling style");
2399
2400 if (!Disassemble
7
Assuming the condition is false
2401 && !Relocations
2402 && !DynamicRelocations
2403 && !SectionHeaders
2404 && !SectionContents
2405 && !SymbolTable
2406 && !UnwindInfo
2407 && !PrivateHeaders
2408 && !FileHeaders
2409 && !FirstPrivateHeader
2410 && !ExportsTrie
2411 && !Rebase
2412 && !Bind
2413 && !LazyBind
2414 && !WeakBind
2415 && !RawClangAST
2416 && !(UniversalHeaders && MachOOpt)
2417 && !ArchiveHeaders
2418 && !(IndirectSymbols && MachOOpt)
2419 && !(DataInCode && MachOOpt)
2420 && !(LinkOptHints && MachOOpt)
2421 && !(InfoPlist && MachOOpt)
2422 && !(DylibsUsed && MachOOpt)
2423 && !(DylibId && MachOOpt)
2424 && !(ObjcMetaData && MachOOpt)
2425 && !(FilterSections.size() != 0 && MachOOpt)
2426 && !PrintFaultMaps
2427 && DwarfDumpType == DIDT_Null) {
2428 cl::PrintHelpMessage();
2429 return 2;
2430 }
2431
2432 DisasmFuncsSet.insert(DisassembleFunctions.begin(),
2433 DisassembleFunctions.end());
2434
2435 llvm::for_each(InputFilenames, DumpInput);
8
Calling 'for_each<llvm::cl::list<std::__cxx11::basic_string<char>, bool, llvm::cl::parser<std::string> > &, void (*)(llvm::StringRef)>'
2436
2437 return EXIT_SUCCESS0;
2438}

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

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

/usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_algo.h

<
1// Algorithm implementation -*- C++ -*-
2
3// Copyright (C) 2001-2018 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_algo.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{algorithm}
54 */
55
56#ifndef _STL_ALGO_H1
57#define _STL_ALGO_H1 1
58
59#include <cstdlib> // for rand
60#include <bits/algorithmfwd.h>
61#include <bits/stl_heap.h>
62#include <bits/stl_tempbuf.h> // for _Temporary_buffer
63#include <bits/predefined_ops.h>
64
65#if __cplusplus201103L >= 201103L
66#include <bits/uniform_int_dist.h>
67#endif
68
69// See concept_check.h for the __glibcxx_*_requires macros.
70
71namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
72{
73_GLIBCXX_BEGIN_NAMESPACE_VERSION
74
75 /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
76 template<typename _Iterator, typename _Compare>
77 void
78 __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
79 _Iterator __c, _Compare __comp)
80 {
81 if (__comp(__a, __b))
82 {
83 if (__comp(__b, __c))
84 std::iter_swap(__result, __b);
85 else if (__comp(__a, __c))
86 std::iter_swap(__result, __c);
87 else
88 std::iter_swap(__result, __a);
89 }
90 else if (__comp(__a, __c))
91 std::iter_swap(__result, __a);
92 else if (__comp(__b, __c))
93 std::iter_swap(__result, __c);
94 else
95 std::iter_swap(__result, __b);
96 }
97
98 /// This is an overload used by find algos for the Input Iterator case.
99 template<typename _InputIterator, typename _Predicate>
100 inline _InputIterator
101 __find_if(_InputIterator __first, _InputIterator __last,
102 _Predicate __pred, input_iterator_tag)
103 {
104 while (__first != __last && !__pred(__first))
105 ++__first;
106 return __first;
107 }
108
109 /// This is an overload used by find algos for the RAI case.
110 template<typename _RandomAccessIterator, typename _Predicate>
111 _RandomAccessIterator
112 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
113 _Predicate __pred, random_access_iterator_tag)
114 {
115 typename iterator_traits<_RandomAccessIterator>::difference_type
116 __trip_count = (__last - __first) >> 2;
117
118 for (; __trip_count > 0; --__trip_count)
119 {
120 if (__pred(__first))
121 return __first;
122 ++__first;
123
124 if (__pred(__first))
125 return __first;
126 ++__first;
127
128 if (__pred(__first))
129 return __first;
130 ++__first;
131
132 if (__pred(__first))
133 return __first;
134 ++__first;
135 }
136
137 switch (__last - __first)
138 {
139 case 3:
140 if (__pred(__first))
141 return __first;
142 ++__first;
143 case 2:
144 if (__pred(__first))
145 return __first;
146 ++__first;
147 case 1:
148 if (__pred(__first))
149 return __first;
150 ++__first;
151 case 0:
152 default:
153 return __last;
154 }
155 }
156
157 template<typename _Iterator, typename _Predicate>
158 inline _Iterator
159 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
160 {
161 return __find_if(__first, __last, __pred,
162 std::__iterator_category(__first));
163 }
164
165 /// Provided for stable_partition to use.
166 template<typename _InputIterator, typename _Predicate>
167 inline _InputIterator
168 __find_if_not(_InputIterator __first, _InputIterator __last,
169 _Predicate __pred)
170 {
171 return std::__find_if(__first, __last,
172 __gnu_cxx::__ops::__negate(__pred),
173 std::__iterator_category(__first));
174 }
175
176 /// Like find_if_not(), but uses and updates a count of the
177 /// remaining range length instead of comparing against an end
178 /// iterator.
179 template<typename _InputIterator, typename _Predicate, typename _Distance>
180 _InputIterator
181 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
182 {
183 for (; __len; --__len, (void) ++__first)
184 if (!__pred(__first))
185 break;
186 return __first;
187 }
188
189 // set_difference
190 // set_intersection
191 // set_symmetric_difference
192 // set_union
193 // for_each
194 // find
195 // find_if
196 // find_first_of
197 // adjacent_find
198 // count
199 // count_if
200 // search
201
202 template<typename _ForwardIterator1, typename _ForwardIterator2,
203 typename _BinaryPredicate>
204 _ForwardIterator1
205 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
206 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
207 _BinaryPredicate __predicate)
208 {
209 // Test for empty ranges
210 if (__first1 == __last1 || __first2 == __last2)
211 return __first1;
212
213 // Test for a pattern of length 1.
214 _ForwardIterator2 __p1(__first2);
215 if (++__p1 == __last2)
216 return std::__find_if(__first1, __last1,
217 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
218
219 // General case.
220 _ForwardIterator2 __p;
221 _ForwardIterator1 __current = __first1;
222
223 for (;;)
224 {
225 __first1 =
226 std::__find_if(__first1, __last1,
227 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
228
229 if (__first1 == __last1)
230 return __last1;
231
232 __p = __p1;
233 __current = __first1;
234 if (++__current == __last1)
235 return __last1;
236
237 while (__predicate(__current, __p))
238 {
239 if (++__p == __last2)
240 return __first1;
241 if (++__current == __last1)
242 return __last1;
243 }
244 ++__first1;
245 }
246 return __first1;
247 }
248
249 // search_n
250
251 /**
252 * This is an helper function for search_n overloaded for forward iterators.
253 */
254 template<typename _ForwardIterator, typename _Integer,
255 typename _UnaryPredicate>
256 _ForwardIterator
257 __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
258 _Integer __count, _UnaryPredicate __unary_pred,
259 std::forward_iterator_tag)
260 {
261 __first = std::__find_if(__first, __last, __unary_pred);
262 while (__first != __last)
263 {
264 typename iterator_traits<_ForwardIterator>::difference_type
265 __n = __count;
266 _ForwardIterator __i = __first;
267 ++__i;
268 while (__i != __last && __n != 1 && __unary_pred(__i))
269 {
270 ++__i;
271 --__n;
272 }
273 if (__n == 1)
274 return __first;
275 if (__i == __last)
276 return __last;
277 __first = std::__find_if(++__i, __last, __unary_pred);
278 }
279 return __last;
280 }
281
282 /**
283 * This is an helper function for search_n overloaded for random access
284 * iterators.
285 */
286 template<typename _RandomAccessIter, typename _Integer,
287 typename _UnaryPredicate>
288 _RandomAccessIter
289 __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
290 _Integer __count, _UnaryPredicate __unary_pred,
291 std::random_access_iterator_tag)
292 {
293 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
294 _DistanceType;
295
296 _DistanceType __tailSize = __last - __first;
297 _DistanceType __remainder = __count;
298
299 while (__remainder <= __tailSize) // the main loop...
300 {
301 __first += __remainder;
302 __tailSize -= __remainder;
303 // __first here is always pointing to one past the last element of
304 // next possible match.
305 _RandomAccessIter __backTrack = __first;
306 while (__unary_pred(--__backTrack))
307 {
308 if (--__remainder == 0)
309 return (__first - __count); // Success
310 }
311 __remainder = __count + 1 - (__first - __backTrack);
312 }
313 return __last; // Failure
314 }
315
316 template<typename _ForwardIterator, typename _Integer,
317 typename _UnaryPredicate>
318 _ForwardIterator
319 __search_n(_ForwardIterator __first, _ForwardIterator __last,
320 _Integer __count,
321 _UnaryPredicate __unary_pred)
322 {
323 if (__count <= 0)
324 return __first;
325
326 if (__count == 1)
327 return std::__find_if(__first, __last, __unary_pred);
328
329 return std::__search_n_aux(__first, __last, __count, __unary_pred,
330 std::__iterator_category(__first));
331 }
332
333 // find_end for forward iterators.
334 template<typename _ForwardIterator1, typename _ForwardIterator2,
335 typename _BinaryPredicate>
336 _ForwardIterator1
337 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
338 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
339 forward_iterator_tag, forward_iterator_tag,
340 _BinaryPredicate __comp)
341 {
342 if (__first2 == __last2)
343 return __last1;
344
345 _ForwardIterator1 __result = __last1;
346 while (1)
347 {
348 _ForwardIterator1 __new_result
349 = std::__search(__first1, __last1, __first2, __last2, __comp);
350 if (__new_result == __last1)
351 return __result;
352 else
353 {
354 __result = __new_result;
355 __first1 = __new_result;
356 ++__first1;
357 }
358 }
359 }
360
361 // find_end for bidirectional iterators (much faster).
362 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
363 typename _BinaryPredicate>
364 _BidirectionalIterator1
365 __find_end(_BidirectionalIterator1 __first1,
366 _BidirectionalIterator1 __last1,
367 _BidirectionalIterator2 __first2,
368 _BidirectionalIterator2 __last2,
369 bidirectional_iterator_tag, bidirectional_iterator_tag,
370 _BinaryPredicate __comp)
371 {
372 // concept requirements
373 __glibcxx_function_requires(_BidirectionalIteratorConcept<
374 _BidirectionalIterator1>)
375 __glibcxx_function_requires(_BidirectionalIteratorConcept<
376 _BidirectionalIterator2>)
377
378 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
379 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
380
381 _RevIterator1 __rlast1(__first1);
382 _RevIterator2 __rlast2(__first2);
383 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
384 _RevIterator2(__last2), __rlast2,
385 __comp);
386
387 if (__rresult == __rlast1)
388 return __last1;
389 else
390 {
391 _BidirectionalIterator1 __result = __rresult.base();
392 std::advance(__result, -std::distance(__first2, __last2));
393 return __result;
394 }
395 }
396
397 /**
398 * @brief Find last matching subsequence in a sequence.
399 * @ingroup non_mutating_algorithms
400 * @param __first1 Start of range to search.
401 * @param __last1 End of range to search.
402 * @param __first2 Start of sequence to match.
403 * @param __last2 End of sequence to match.
404 * @return The last iterator @c i in the range
405 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
406 * @p *(__first2+N) for each @c N in the range @p
407 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
408 *
409 * Searches the range @p [__first1,__last1) for a sub-sequence that
410 * compares equal value-by-value with the sequence given by @p
411 * [__first2,__last2) and returns an iterator to the __first
412 * element of the sub-sequence, or @p __last1 if the sub-sequence
413 * is not found. The sub-sequence will be the last such
414 * subsequence contained in [__first1,__last1).
415 *
416 * Because the sub-sequence must lie completely within the range @p
417 * [__first1,__last1) it must start at a position less than @p
418 * __last1-(__last2-__first2) where @p __last2-__first2 is the
419 * length of the sub-sequence. This means that the returned
420 * iterator @c i will be in the range @p
421 * [__first1,__last1-(__last2-__first2))
422 */
423 template<typename _ForwardIterator1, typename _ForwardIterator2>
424 inline _ForwardIterator1
425 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
426 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
427 {
428 // concept requirements
429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
430 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
431 __glibcxx_function_requires(_EqualOpConcept<
432 typename iterator_traits<_ForwardIterator1>::value_type,
433 typename iterator_traits<_ForwardIterator2>::value_type>)
434 __glibcxx_requires_valid_range(__first1, __last1);
435 __glibcxx_requires_valid_range(__first2, __last2);
436
437 return std::__find_end(__first1, __last1, __first2, __last2,
438 std::__iterator_category(__first1),
439 std::__iterator_category(__first2),
440 __gnu_cxx::__ops::__iter_equal_to_iter());
441 }
442
443 /**
444 * @brief Find last matching subsequence in a sequence using a predicate.
445 * @ingroup non_mutating_algorithms
446 * @param __first1 Start of range to search.
447 * @param __last1 End of range to search.
448 * @param __first2 Start of sequence to match.
449 * @param __last2 End of sequence to match.
450 * @param __comp The predicate to use.
451 * @return The last iterator @c i in the range @p
452 * [__first1,__last1-(__last2-__first2)) such that @c
453 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
454 * range @p [0,__last2-__first2), or @p __last1 if no such iterator
455 * exists.
456 *
457 * Searches the range @p [__first1,__last1) for a sub-sequence that
458 * compares equal value-by-value with the sequence given by @p
459 * [__first2,__last2) using comp as a predicate and returns an
460 * iterator to the first element of the sub-sequence, or @p __last1
461 * if the sub-sequence is not found. The sub-sequence will be the
462 * last such subsequence contained in [__first,__last1).
463 *
464 * Because the sub-sequence must lie completely within the range @p
465 * [__first1,__last1) it must start at a position less than @p
466 * __last1-(__last2-__first2) where @p __last2-__first2 is the
467 * length of the sub-sequence. This means that the returned
468 * iterator @c i will be in the range @p
469 * [__first1,__last1-(__last2-__first2))
470 */
471 template<typename _ForwardIterator1, typename _ForwardIterator2,
472 typename _BinaryPredicate>
473 inline _ForwardIterator1
474 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
475 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
476 _BinaryPredicate __comp)
477 {
478 // concept requirements
479 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
481 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
482 typename iterator_traits<_ForwardIterator1>::value_type,
483 typename iterator_traits<_ForwardIterator2>::value_type>)
484 __glibcxx_requires_valid_range(__first1, __last1);
485 __glibcxx_requires_valid_range(__first2, __last2);
486
487 return std::__find_end(__first1, __last1, __first2, __last2,
488 std::__iterator_category(__first1),
489 std::__iterator_category(__first2),
490 __gnu_cxx::__ops::__iter_comp_iter(__comp));
491 }
492
493#if __cplusplus201103L >= 201103L
494 /**
495 * @brief Checks that a predicate is true for all the elements
496 * of a sequence.
497 * @ingroup non_mutating_algorithms
498 * @param __first An input iterator.
499 * @param __last An input iterator.
500 * @param __pred A predicate.
501 * @return True if the check is true, false otherwise.
502 *
503 * Returns true if @p __pred is true for each element in the range
504 * @p [__first,__last), and false otherwise.
505 */
506 template<typename _InputIterator, typename _Predicate>
507 inline bool
508 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
509 { return __last == std::find_if_not(__first, __last, __pred); }
510
511 /**
512 * @brief Checks that a predicate is false for all the elements
513 * of a sequence.
514 * @ingroup non_mutating_algorithms
515 * @param __first An input iterator.
516 * @param __last An input iterator.
517 * @param __pred A predicate.
518 * @return True if the check is true, false otherwise.
519 *
520 * Returns true if @p __pred is false for each element in the range
521 * @p [__first,__last), and false otherwise.
522 */
523 template<typename _InputIterator, typename _Predicate>
524 inline bool
525 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
526 { return __last == _GLIBCXX_STD_Astd::find_if(__first, __last, __pred); }
527
528 /**
529 * @brief Checks that a predicate is false for at least an element
530 * of a sequence.
531 * @ingroup non_mutating_algorithms
532 * @param __first An input iterator.
533 * @param __last An input iterator.
534 * @param __pred A predicate.
535 * @return True if the check is true, false otherwise.
536 *
537 * Returns true if an element exists in the range @p
538 * [__first,__last) such that @p __pred is true, and false
539 * otherwise.
540 */
541 template<typename _InputIterator, typename _Predicate>
542 inline bool
543 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
544 { return !std::none_of(__first, __last, __pred); }
545
546 /**
547 * @brief Find the first element in a sequence for which a
548 * predicate is false.
549 * @ingroup non_mutating_algorithms
550 * @param __first An input iterator.
551 * @param __last An input iterator.
552 * @param __pred A predicate.
553 * @return The first iterator @c i in the range @p [__first,__last)
554 * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
555 */
556 template<typename _InputIterator, typename _Predicate>
557 inline _InputIterator
558 find_if_not(_InputIterator __first, _InputIterator __last,
559 _Predicate __pred)
560 {
561 // concept requirements
562 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
563 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
564 typename iterator_traits<_InputIterator>::value_type>)
565 __glibcxx_requires_valid_range(__first, __last);
566 return std::__find_if_not(__first, __last,
567 __gnu_cxx::__ops::__pred_iter(__pred));
568 }
569
570 /**
571 * @brief Checks whether the sequence is partitioned.
572 * @ingroup mutating_algorithms
573 * @param __first An input iterator.
574 * @param __last An input iterator.
575 * @param __pred A predicate.
576 * @return True if the range @p [__first,__last) is partioned by @p __pred,
577 * i.e. if all elements that satisfy @p __pred appear before those that
578 * do not.
579 */
580 template<typename _InputIterator, typename _Predicate>
581 inline bool
582 is_partitioned(_InputIterator __first, _InputIterator __last,
583 _Predicate __pred)
584 {
585 __first = std::find_if_not(__first, __last, __pred);
586 if (__first == __last)
587 return true;
588 ++__first;
589 return std::none_of(__first, __last, __pred);
590 }
591
592 /**
593 * @brief Find the partition point of a partitioned range.
594 * @ingroup mutating_algorithms
595 * @param __first An iterator.
596 * @param __last Another iterator.
597 * @param __pred A predicate.
598 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
599 * and @p none_of(mid, __last, __pred) are both true.
600 */
601 template<typename _ForwardIterator, typename _Predicate>
602 _ForwardIterator
603 partition_point(_ForwardIterator __first, _ForwardIterator __last,
604 _Predicate __pred)
605 {
606 // concept requirements
607 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
608 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
609 typename iterator_traits<_ForwardIterator>::value_type>)
610
611 // A specific debug-mode test will be necessary...
612 __glibcxx_requires_valid_range(__first, __last);
613
614 typedef typename iterator_traits<_ForwardIterator>::difference_type
615 _DistanceType;
616
617 _DistanceType __len = std::distance(__first, __last);
618 _DistanceType __half;
619 _ForwardIterator __middle;
620
621 while (__len > 0)
622 {
623 __half = __len >> 1;
624 __middle = __first;
625 std::advance(__middle, __half);
626 if (__pred(*__middle))
627 {
628 __first = __middle;
629 ++__first;
630 __len = __len - __half - 1;
631 }
632 else
633 __len = __half;
634 }
635 return __first;
636 }
637#endif
638
639 template<typename _InputIterator, typename _OutputIterator,
640 typename _Predicate>
641 _OutputIterator
642 __remove_copy_if(_InputIterator __first, _InputIterator __last,
643 _OutputIterator __result, _Predicate __pred)
644 {
645 for (; __first != __last; ++__first)
646 if (!__pred(__first))
647 {
648 *__result = *__first;
649 ++__result;
650 }
651 return __result;
652 }
653
654 /**
655 * @brief Copy a sequence, removing elements of a given value.
656 * @ingroup mutating_algorithms
657 * @param __first An input iterator.
658 * @param __last An input iterator.
659 * @param __result An output iterator.
660 * @param __value The value to be removed.
661 * @return An iterator designating the end of the resulting sequence.
662 *
663 * Copies each element in the range @p [__first,__last) not equal
664 * to @p __value to the range beginning at @p __result.
665 * remove_copy() is stable, so the relative order of elements that
666 * are copied is unchanged.
667 */
668 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
669 inline _OutputIterator
670 remove_copy(_InputIterator __first, _InputIterator __last,
671 _OutputIterator __result, const _Tp& __value)
672 {
673 // concept requirements
674 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
675 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
676 typename iterator_traits<_InputIterator>::value_type>)
677 __glibcxx_function_requires(_EqualOpConcept<
678 typename iterator_traits<_InputIterator>::value_type, _Tp>)
679 __glibcxx_requires_valid_range(__first, __last);
680
681 return std::__remove_copy_if(__first, __last, __result,
682 __gnu_cxx::__ops::__iter_equals_val(__value));
683 }
684
685 /**
686 * @brief Copy a sequence, removing elements for which a predicate is true.
687 * @ingroup mutating_algorithms
688 * @param __first An input iterator.
689 * @param __last An input iterator.
690 * @param __result An output iterator.
691 * @param __pred A predicate.
692 * @return An iterator designating the end of the resulting sequence.
693 *
694 * Copies each element in the range @p [__first,__last) for which
695 * @p __pred returns false to the range beginning at @p __result.
696 *
697 * remove_copy_if() is stable, so the relative order of elements that are
698 * copied is unchanged.
699 */
700 template<typename _InputIterator, typename _OutputIterator,
701 typename _Predicate>
702 inline _OutputIterator
703 remove_copy_if(_InputIterator __first, _InputIterator __last,
704 _OutputIterator __result, _Predicate __pred)
705 {
706 // concept requirements
707 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
708 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
709 typename iterator_traits<_InputIterator>::value_type>)
710 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
711 typename iterator_traits<_InputIterator>::value_type>)
712 __glibcxx_requires_valid_range(__first, __last);
713
714 return std::__remove_copy_if(__first, __last, __result,
715 __gnu_cxx::__ops::__pred_iter(__pred));
716 }
717
718#if __cplusplus201103L >= 201103L
719 /**
720 * @brief Copy the elements of a sequence for which a predicate is true.
721 * @ingroup mutating_algorithms
722 * @param __first An input iterator.
723 * @param __last An input iterator.
724 * @param __result An output iterator.
725 * @param __pred A predicate.
726 * @return An iterator designating the end of the resulting sequence.
727 *
728 * Copies each element in the range @p [__first,__last) for which
729 * @p __pred returns true to the range beginning at @p __result.
730 *
731 * copy_if() is stable, so the relative order of elements that are
732 * copied is unchanged.
733 */
734 template<typename _InputIterator, typename _OutputIterator,
735 typename _Predicate>
736 _OutputIterator
737 copy_if(_InputIterator __first, _InputIterator __last,
738 _OutputIterator __result, _Predicate __pred)
739 {
740 // concept requirements
741 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
742 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
743 typename iterator_traits<_InputIterator>::value_type>)
744 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
745 typename iterator_traits<_InputIterator>::value_type>)
746 __glibcxx_requires_valid_range(__first, __last);
747
748 for (; __first != __last; ++__first)
749 if (__pred(*__first))
750 {
751 *__result = *__first;
752 ++__result;
753 }
754 return __result;
755 }
756
757 template<typename _InputIterator, typename _Size, typename _OutputIterator>
758 _OutputIterator
759 __copy_n(_InputIterator __first, _Size __n,
760 _OutputIterator __result, input_iterator_tag)
761 {
762 if (__n > 0)
763 {
764 while (true)
765 {
766 *__result = *__first;
767 ++__result;
768 if (--__n > 0)
769 ++__first;
770 else
771 break;
772 }
773 }
774 return __result;
775 }
776
777 template<typename _RandomAccessIterator, typename _Size,
778 typename _OutputIterator>
779 inline _OutputIterator
780 __copy_n(_RandomAccessIterator __first, _Size __n,
781 _OutputIterator __result, random_access_iterator_tag)
782 { return std::copy(__first, __first + __n, __result); }
783
784 /**
785 * @brief Copies the range [first,first+n) into [result,result+n).
786 * @ingroup mutating_algorithms
787 * @param __first An input iterator.
788 * @param __n The number of elements to copy.
789 * @param __result An output iterator.
790 * @return result+n.
791 *
792 * This inline function will boil down to a call to @c memmove whenever
793 * possible. Failing that, if random access iterators are passed, then the
794 * loop count will be known (and therefore a candidate for compiler
795 * optimizations such as unrolling).
796 */
797 template<typename _InputIterator, typename _Size, typename _OutputIterator>
798 inline _OutputIterator
799 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
800 {
801 // concept requirements
802 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
803 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
804 typename iterator_traits<_InputIterator>::value_type>)
805
806 return std::__copy_n(__first, __n, __result,
807 std::__iterator_category(__first));
808 }
809
810 /**
811 * @brief Copy the elements of a sequence to separate output sequences
812 * depending on the truth value of a predicate.
813 * @ingroup mutating_algorithms
814 * @param __first An input iterator.
815 * @param __last An input iterator.
816 * @param __out_true An output iterator.
817 * @param __out_false An output iterator.
818 * @param __pred A predicate.
819 * @return A pair designating the ends of the resulting sequences.
820 *
821 * Copies each element in the range @p [__first,__last) for which
822 * @p __pred returns true to the range beginning at @p out_true
823 * and each element for which @p __pred returns false to @p __out_false.
824 */
825 template<typename _InputIterator, typename _OutputIterator1,
826 typename _OutputIterator2, typename _Predicate>
827 pair<_OutputIterator1, _OutputIterator2>
828 partition_copy(_InputIterator __first, _InputIterator __last,
829 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
830 _Predicate __pred)
831 {
832 // concept requirements
833 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
834 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
835 typename iterator_traits<_InputIterator>::value_type>)
836 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
837 typename iterator_traits<_InputIterator>::value_type>)
838 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
839 typename iterator_traits<_InputIterator>::value_type>)
840 __glibcxx_requires_valid_range(__first, __last);
841
842 for (; __first != __last; ++__first)
843 if (__pred(*__first))
844 {
845 *__out_true = *__first;
846 ++__out_true;
847 }
848 else
849 {
850 *__out_false = *__first;
851 ++__out_false;
852 }
853
854 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
855 }
856#endif
857
858 template<typename _ForwardIterator, typename _Predicate>
859 _ForwardIterator
860 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
861 _Predicate __pred)
862 {
863 __first = std::__find_if(__first, __last, __pred);
864 if (__first == __last)
865 return __first;
866 _ForwardIterator __result = __first;
867 ++__first;
868 for (; __first != __last; ++__first)
869 if (!__pred(__first))
870 {
871 *__result = _GLIBCXX_MOVE(*__first)std::move(*__first);
872 ++__result;
873 }
874 return __result;
875 }
876
877 /**
878 * @brief Remove elements from a sequence.
879 * @ingroup mutating_algorithms
880 * @param __first An input iterator.
881 * @param __last An input iterator.
882 * @param __value The value to be removed.
883 * @return An iterator designating the end of the resulting sequence.
884 *
885 * All elements equal to @p __value are removed from the range
886 * @p [__first,__last).
887 *
888 * remove() is stable, so the relative order of elements that are
889 * not removed is unchanged.
890 *
891 * Elements between the end of the resulting sequence and @p __last
892 * are still present, but their value is unspecified.
893 */
894 template<typename _ForwardIterator, typename _Tp>
895 inline _ForwardIterator
896 remove(_ForwardIterator __first, _ForwardIterator __last,
897 const _Tp& __value)
898 {
899 // concept requirements
900 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
901 _ForwardIterator>)
902 __glibcxx_function_requires(_EqualOpConcept<
903 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
904 __glibcxx_requires_valid_range(__first, __last);
905
906 return std::__remove_if(__first, __last,
907 __gnu_cxx::__ops::__iter_equals_val(__value));
908 }
909
910 /**
911 * @brief Remove elements from a sequence using a predicate.
912 * @ingroup mutating_algorithms
913 * @param __first A forward iterator.
914 * @param __last A forward iterator.
915 * @param __pred A predicate.
916 * @return An iterator designating the end of the resulting sequence.
917 *
918 * All elements for which @p __pred returns true are removed from the range
919 * @p [__first,__last).
920 *
921 * remove_if() is stable, so the relative order of elements that are
922 * not removed is unchanged.
923 *
924 * Elements between the end of the resulting sequence and @p __last
925 * are still present, but their value is unspecified.
926 */
927 template<typename _ForwardIterator, typename _Predicate>
928 inline _ForwardIterator
929 remove_if(_ForwardIterator __first, _ForwardIterator __last,
930 _Predicate __pred)
931 {
932 // concept requirements
933 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
934 _ForwardIterator>)
935 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
936 typename iterator_traits<_ForwardIterator>::value_type>)
937 __glibcxx_requires_valid_range(__first, __last);
938
939 return std::__remove_if(__first, __last,
940 __gnu_cxx::__ops::__pred_iter(__pred));
941 }
942
943 template<typename _ForwardIterator, typename _BinaryPredicate>
944 _ForwardIterator
945 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
946 _BinaryPredicate __binary_pred)
947 {
948 if (__first == __last)
949 return __last;
950 _ForwardIterator __next = __first;
951 while (++__next != __last)
952 {
953 if (__binary_pred(__first, __next))
954 return __first;
955 __first = __next;
956 }
957 return __last;
958 }
959
960 template<typename _ForwardIterator, typename _BinaryPredicate>
961 _ForwardIterator
962 __unique(_ForwardIterator __first, _ForwardIterator __last,
963 _BinaryPredicate __binary_pred)
964 {
965 // Skip the beginning, if already unique.
966 __first = std::__adjacent_find(__first, __last, __binary_pred);
967 if (__first == __last)
968 return __last;
969
970 // Do the real copy work.
971 _ForwardIterator __dest = __first;
972 ++__first;
973 while (++__first != __last)
974 if (!__binary_pred(__dest, __first))
975 *++__dest = _GLIBCXX_MOVE(*__first)std::move(*__first);
976 return ++__dest;
977 }
978
979 /**
980 * @brief Remove consecutive duplicate values from a sequence.
981 * @ingroup mutating_algorithms
982 * @param __first A forward iterator.
983 * @param __last A forward iterator.
984 * @return An iterator designating the end of the resulting sequence.
985 *
986 * Removes all but the first element from each group of consecutive
987 * values that compare equal.
988 * unique() is stable, so the relative order of elements that are
989 * not removed is unchanged.
990 * Elements between the end of the resulting sequence and @p __last
991 * are still present, but their value is unspecified.
992 */
993 template<typename _ForwardIterator>
994 inline _ForwardIterator
995 unique(_ForwardIterator __first, _ForwardIterator __last)
996 {
997 // concept requirements
998 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
999 _ForwardIterator>)
1000 __glibcxx_function_requires(_EqualityComparableConcept<
1001 typename iterator_traits<_ForwardIterator>::value_type>)
1002 __glibcxx_requires_valid_range(__first, __last);
1003
1004 return std::__unique(__first, __last,
1005 __gnu_cxx::__ops::__iter_equal_to_iter());
1006 }
1007
1008 /**
1009 * @brief Remove consecutive values from a sequence using a predicate.
1010 * @ingroup mutating_algorithms
1011 * @param __first A forward iterator.
1012 * @param __last A forward iterator.
1013 * @param __binary_pred A binary predicate.
1014 * @return An iterator designating the end of the resulting sequence.
1015 *
1016 * Removes all but the first element from each group of consecutive
1017 * values for which @p __binary_pred returns true.
1018 * unique() is stable, so the relative order of elements that are
1019 * not removed is unchanged.
1020 * Elements between the end of the resulting sequence and @p __last
1021 * are still present, but their value is unspecified.
1022 */
1023 template<typename _ForwardIterator, typename _BinaryPredicate>
1024 inline _ForwardIterator
1025 unique(_ForwardIterator __first, _ForwardIterator __last,
1026 _BinaryPredicate __binary_pred)
1027 {
1028 // concept requirements
1029 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1030 _ForwardIterator>)
1031 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1032 typename iterator_traits<_ForwardIterator>::value_type,
1033 typename iterator_traits<_ForwardIterator>::value_type>)
1034 __glibcxx_requires_valid_range(__first, __last);
1035
1036 return std::__unique(__first, __last,
1037 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1038 }
1039
1040 /**
1041 * This is an uglified
1042 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1043 * _BinaryPredicate)
1044 * overloaded for forward iterators and output iterator as result.
1045 */
1046 template<typename _ForwardIterator, typename _OutputIterator,
1047 typename _BinaryPredicate>
1048 _OutputIterator
1049 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1050 _OutputIterator __result, _BinaryPredicate __binary_pred,
1051 forward_iterator_tag, output_iterator_tag)
1052 {
1053 // concept requirements -- iterators already checked
1054 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1055 typename iterator_traits<_ForwardIterator>::value_type,
1056 typename iterator_traits<_ForwardIterator>::value_type>)
1057
1058 _ForwardIterator __next = __first;
1059 *__result = *__first;
1060 while (++__next != __last)
1061 if (!__binary_pred(__first, __next))
1062 {
1063 __first = __next;
1064 *++__result = *__first;
1065 }
1066 return ++__result;
1067 }
1068
1069 /**
1070 * This is an uglified
1071 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1072 * _BinaryPredicate)
1073 * overloaded for input iterators and output iterator as result.
1074 */
1075 template<typename _InputIterator, typename _OutputIterator,
1076 typename _BinaryPredicate>
1077 _OutputIterator
1078 __unique_copy(_InputIterator __first, _InputIterator __last,
1079 _OutputIterator __result, _BinaryPredicate __binary_pred,
1080 input_iterator_tag, output_iterator_tag)
1081 {
1082 // concept requirements -- iterators already checked
1083 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1084 typename iterator_traits<_InputIterator>::value_type,
1085 typename iterator_traits<_InputIterator>::value_type>)
1086
1087 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1088 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1089 __rebound_pred
1090 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1091 *__result = __value;
1092 while (++__first != __last)
1093 if (!__rebound_pred(__first, __value))
1094 {
1095 __value = *__first;
1096 *++__result = __value;
1097 }
1098 return ++__result;
1099 }
1100
1101 /**
1102 * This is an uglified
1103 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1104 * _BinaryPredicate)
1105 * overloaded for input iterators and forward iterator as result.
1106 */
1107 template<typename _InputIterator, typename _ForwardIterator,
1108 typename _BinaryPredicate>
1109 _ForwardIterator
1110 __unique_copy(_InputIterator __first, _InputIterator __last,
1111 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1112 input_iterator_tag, forward_iterator_tag)
1113 {
1114 // concept requirements -- iterators already checked
1115 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1116 typename iterator_traits<_ForwardIterator>::value_type,
1117 typename iterator_traits<_InputIterator>::value_type>)
1118 *__result = *__first;
1119 while (++__first != __last)
1120 if (!__binary_pred(__result, __first))
1121 *++__result = *__first;
1122 return ++__result;
1123 }
1124
1125 /**
1126 * This is an uglified reverse(_BidirectionalIterator,
1127 * _BidirectionalIterator)
1128 * overloaded for bidirectional iterators.
1129 */
1130 template<typename _BidirectionalIterator>
1131 void
1132 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1133 bidirectional_iterator_tag)
1134 {
1135 while (true)
1136 if (__first == __last || __first == --__last)
1137 return;
1138 else
1139 {
1140 std::iter_swap(__first, __last);
1141 ++__first;
1142 }
1143 }
1144
1145 /**
1146 * This is an uglified reverse(_BidirectionalIterator,
1147 * _BidirectionalIterator)
1148 * overloaded for random access iterators.
1149 */
1150 template<typename _RandomAccessIterator>
1151 void
1152 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1153 random_access_iterator_tag)
1154 {
1155 if (__first == __last)
1156 return;
1157 --__last;
1158 while (__first < __last)
1159 {
1160 std::iter_swap(__first, __last);
1161 ++__first;
1162 --__last;
1163 }
1164 }
1165
1166 /**
1167 * @brief Reverse a sequence.
1168 * @ingroup mutating_algorithms
1169 * @param __first A bidirectional iterator.
1170 * @param __last A bidirectional iterator.
1171 * @return reverse() returns no value.
1172 *
1173 * Reverses the order of the elements in the range @p [__first,__last),
1174 * so that the first element becomes the last etc.
1175 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1176 * swaps @p *(__first+i) and @p *(__last-(i+1))
1177 */
1178 template<typename _BidirectionalIterator>
1179 inline void
1180 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1181 {
1182 // concept requirements
1183 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1184 _BidirectionalIterator>)
1185 __glibcxx_requires_valid_range(__first, __last);
1186 std::__reverse(__first, __last, std::__iterator_category(__first));
1187 }
1188
1189 /**
1190 * @brief Copy a sequence, reversing its elements.
1191 * @ingroup mutating_algorithms
1192 * @param __first A bidirectional iterator.
1193 * @param __last A bidirectional iterator.
1194 * @param __result An output iterator.
1195 * @return An iterator designating the end of the resulting sequence.
1196 *
1197 * Copies the elements in the range @p [__first,__last) to the
1198 * range @p [__result,__result+(__last-__first)) such that the
1199 * order of the elements is reversed. For every @c i such that @p
1200 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1201 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1202 * The ranges @p [__first,__last) and @p
1203 * [__result,__result+(__last-__first)) must not overlap.
1204 */
1205 template<typename _BidirectionalIterator, typename _OutputIterator>
1206 _OutputIterator
1207 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1208 _OutputIterator __result)
1209 {
1210 // concept requirements
1211 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1212 _BidirectionalIterator>)
1213 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1214 typename iterator_traits<_BidirectionalIterator>::value_type>)
1215 __glibcxx_requires_valid_range(__first, __last);
1216
1217 while (__first != __last)
1218 {
1219 --__last;
1220 *__result = *__last;
1221 ++__result;
1222 }
1223 return __result;
1224 }
1225
1226 /**
1227 * This is a helper function for the rotate algorithm specialized on RAIs.
1228 * It returns the greatest common divisor of two integer values.
1229 */
1230 template<typename _EuclideanRingElement>
1231 _EuclideanRingElement
1232 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1233 {
1234 while (__n != 0)
1235 {
1236 _EuclideanRingElement __t = __m % __n;
1237 __m = __n;
1238 __n = __t;
1239 }
1240 return __m;
1241 }
1242
1243 inline namespace _V2
1244 {
1245
1246 /// This is a helper function for the rotate algorithm.
1247 template<typename _ForwardIterator>
1248 _ForwardIterator
1249 __rotate(_ForwardIterator __first,
1250 _ForwardIterator __middle,
1251 _ForwardIterator __last,
1252 forward_iterator_tag)
1253 {
1254 if (__first == __middle)
1255 return __last;
1256 else if (__last == __middle)
1257 return __first;
1258
1259 _ForwardIterator __first2 = __middle;
1260 do
1261 {
1262 std::iter_swap(__first, __first2);
1263 ++__first;
1264 ++__first2;
1265 if (__first == __middle)
1266 __middle = __first2;
1267 }
1268 while (__first2 != __last);
1269
1270 _ForwardIterator __ret = __first;
1271
1272 __first2 = __middle;
1273
1274 while (__first2 != __last)
1275 {
1276 std::iter_swap(__first, __first2);
1277 ++__first;
1278 ++__first2;
1279 if (__first == __middle)
1280 __middle = __first2;
1281 else if (__first2 == __last)
1282 __first2 = __middle;
1283 }
1284 return __ret;
1285 }
1286
1287 /// This is a helper function for the rotate algorithm.
1288 template<typename _BidirectionalIterator>
1289 _BidirectionalIterator
1290 __rotate(_BidirectionalIterator __first,
1291 _BidirectionalIterator __middle,
1292 _BidirectionalIterator __last,
1293 bidirectional_iterator_tag)
1294 {
1295 // concept requirements
1296 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1297 _BidirectionalIterator>)
1298
1299 if (__first == __middle)
1300 return __last;
1301 else if (__last == __middle)
1302 return __first;
1303
1304 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1305 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1306
1307 while (__first != __middle && __middle != __last)
1308 {
1309 std::iter_swap(__first, --__last);
1310 ++__first;
1311 }
1312
1313 if (__first == __middle)
1314 {
1315 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1316 return __last;
1317 }
1318 else
1319 {
1320 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1321 return __first;
1322 }
1323 }
1324
1325 /// This is a helper function for the rotate algorithm.
1326 template<typename _RandomAccessIterator>
1327 _RandomAccessIterator
1328 __rotate(_RandomAccessIterator __first,
1329 _RandomAccessIterator __middle,
1330 _RandomAccessIterator __last,
1331 random_access_iterator_tag)
1332 {
1333 // concept requirements
1334 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1335 _RandomAccessIterator>)
1336
1337 if (__first == __middle)
1338 return __last;
1339 else if (__last == __middle)
1340 return __first;
1341
1342 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1343 _Distance;
1344 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1345 _ValueType;
1346
1347 _Distance __n = __last - __first;
1348 _Distance __k = __middle - __first;
1349
1350 if (__k == __n - __k)
1351 {
1352 std::swap_ranges(__first, __middle, __middle);
1353 return __middle;
1354 }
1355
1356 _RandomAccessIterator __p = __first;
1357 _RandomAccessIterator __ret = __first + (__last - __middle);
1358
1359 for (;;)
1360 {
1361 if (__k < __n - __k)
1362 {
1363 if (__is_pod(_ValueType) && __k == 1)
1364 {
1365 _ValueType __t = _GLIBCXX_MOVE(*__p)std::move(*__p);
1366 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p)std::move(__p + 1, __p + __n, __p);
1367 *(__p + __n - 1) = _GLIBCXX_MOVE(__t)std::move(__t);
1368 return __ret;
1369 }
1370 _RandomAccessIterator __q = __p + __k;
1371 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1372 {
1373 std::iter_swap(__p, __q);
1374 ++__p;
1375 ++__q;
1376 }
1377 __n %= __k;
1378 if (__n == 0)
1379 return __ret;
1380 std::swap(__n, __k);
1381 __k = __n - __k;
1382 }
1383 else
1384 {
1385 __k = __n - __k;
1386 if (__is_pod(_ValueType) && __k == 1)
1387 {
1388 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1))std::move(*(__p + __n - 1));
1389 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n)std::move_backward(__p, __p + __n - 1, __p + __n);
1390 *__p = _GLIBCXX_MOVE(__t)std::move(__t);
1391 return __ret;
1392 }
1393 _RandomAccessIterator __q = __p + __n;
1394 __p = __q - __k;
1395 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1396 {
1397 --__p;
1398 --__q;
1399 std::iter_swap(__p, __q);
1400 }
1401 __n %= __k;
1402 if (__n == 0)
1403 return __ret;
1404 std::swap(__n, __k);
1405 }
1406 }
1407 }
1408
1409 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1410 // DR 488. rotate throws away useful information
1411 /**
1412 * @brief Rotate the elements of a sequence.
1413 * @ingroup mutating_algorithms
1414 * @param __first A forward iterator.
1415 * @param __middle A forward iterator.
1416 * @param __last A forward iterator.
1417 * @return first + (last - middle).
1418 *
1419 * Rotates the elements of the range @p [__first,__last) by
1420 * @p (__middle - __first) positions so that the element at @p __middle
1421 * is moved to @p __first, the element at @p __middle+1 is moved to
1422 * @p __first+1 and so on for each element in the range
1423 * @p [__first,__last).
1424 *
1425 * This effectively swaps the ranges @p [__first,__middle) and
1426 * @p [__middle,__last).
1427 *
1428 * Performs
1429 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1430 * for each @p n in the range @p [0,__last-__first).
1431 */
1432 template<typename _ForwardIterator>
1433 inline _ForwardIterator
1434 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1435 _ForwardIterator __last)
1436 {
1437 // concept requirements
1438 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1439 _ForwardIterator>)
1440 __glibcxx_requires_valid_range(__first, __middle);
1441 __glibcxx_requires_valid_range(__middle, __last);
1442
1443 return std::__rotate(__first, __middle, __last,
1444 std::__iterator_category(__first));
1445 }
1446
1447 } // namespace _V2
1448
1449 /**
1450 * @brief Copy a sequence, rotating its elements.
1451 * @ingroup mutating_algorithms
1452 * @param __first A forward iterator.
1453 * @param __middle A forward iterator.
1454 * @param __last A forward iterator.
1455 * @param __result An output iterator.
1456 * @return An iterator designating the end of the resulting sequence.
1457 *
1458 * Copies the elements of the range @p [__first,__last) to the
1459 * range beginning at @result, rotating the copied elements by
1460 * @p (__middle-__first) positions so that the element at @p __middle
1461 * is moved to @p __result, the element at @p __middle+1 is moved
1462 * to @p __result+1 and so on for each element in the range @p
1463 * [__first,__last).
1464 *
1465 * Performs
1466 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1467 * for each @p n in the range @p [0,__last-__first).
1468 */
1469 template<typename _ForwardIterator, typename _OutputIterator>
1470 inline _OutputIterator
1471 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1472 _ForwardIterator __last, _OutputIterator __result)
1473 {
1474 // concept requirements
1475 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1477 typename iterator_traits<_ForwardIterator>::value_type>)
1478 __glibcxx_requires_valid_range(__first, __middle);
1479 __glibcxx_requires_valid_range(__middle, __last);
1480
1481 return std::copy(__first, __middle,
1482 std::copy(__middle, __last, __result));
1483 }
1484
1485 /// This is a helper function...
1486 template<typename _ForwardIterator, typename _Predicate>
1487 _ForwardIterator
1488 __partition(_ForwardIterator __first, _ForwardIterator __last,
1489 _Predicate __pred, forward_iterator_tag)
1490 {
1491 if (__first == __last)
1492 return __first;
1493
1494 while (__pred(*__first))
1495 if (++__first == __last)
1496 return __first;
1497
1498 _ForwardIterator __next = __first;
1499
1500 while (++__next != __last)
1501 if (__pred(*__next))
1502 {
1503 std::iter_swap(__first, __next);
1504 ++__first;
1505 }
1506
1507 return __first;
1508 }
1509
1510 /// This is a helper function...
1511 template<typename _BidirectionalIterator, typename _Predicate>
1512 _BidirectionalIterator
1513 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1514 _Predicate __pred, bidirectional_iterator_tag)
1515 {
1516 while (true)
1517 {
1518 while (true)
1519 if (__first == __last)
1520 return __first;
1521 else if (__pred(*__first))
1522 ++__first;
1523 else
1524 break;
1525 --__last;
1526 while (true)
1527 if (__first == __last)
1528 return __first;
1529 else if (!bool(__pred(*__last)))
1530 --__last;
1531 else
1532 break;
1533 std::iter_swap(__first, __last);
1534 ++__first;
1535 }
1536 }
1537
1538 // partition
1539
1540 /// This is a helper function...
1541 /// Requires __first != __last and !__pred(__first)
1542 /// and __len == distance(__first, __last).
1543 ///
1544 /// !__pred(__first) allows us to guarantee that we don't
1545 /// move-assign an element onto itself.
1546 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1547 typename _Distance>
1548 _ForwardIterator
1549 __stable_partition_adaptive(_ForwardIterator __first,
1550 _ForwardIterator __last,
1551 _Predicate __pred, _Distance __len,
1552 _Pointer __buffer,
1553 _Distance __buffer_size)
1554 {
1555 if (__len == 1)
1556 return __first;
1557
1558 if (__len <= __buffer_size)
1559 {
1560 _ForwardIterator __result1 = __first;
1561 _Pointer __result2 = __buffer;
1562
1563 // The precondition guarantees that !__pred(__first), so
1564 // move that element to the buffer before starting the loop.
1565 // This ensures that we only call __pred once per element.
1566 *__result2 = _GLIBCXX_MOVE(*__first)std::move(*__first);
1567 ++__result2;
1568 ++__first;
1569 for (; __first != __last; ++__first)
1570 if (__pred(__first))
1571 {
1572 *__result1 = _GLIBCXX_MOVE(*__first)std::move(*__first);
1573 ++__result1;
1574 }
1575 else
1576 {
1577 *__result2 = _GLIBCXX_MOVE(*__first)std::move(*__first);
1578 ++__result2;
1579 }
1580
1581 _GLIBCXX_MOVE3(__buffer, __result2, __result1)std::move(__buffer, __result2, __result1);
1582 return __result1;
1583 }
1584
1585 _ForwardIterator __middle = __first;
1586 std::advance(__middle, __len / 2);
1587 _ForwardIterator __left_split =
1588 std::__stable_partition_adaptive(__first, __middle, __pred,
1589 __len / 2, __buffer,
1590 __buffer_size);
1591
1592 // Advance past true-predicate values to satisfy this
1593 // function's preconditions.
1594 _Distance __right_len = __len - __len / 2;
1595 _ForwardIterator __right_split =
1596 std::__find_if_not_n(__middle, __right_len, __pred);
1597
1598 if (__right_len)
1599 __right_split =
1600 std::__stable_partition_adaptive(__right_split, __last, __pred,
1601 __right_len,
1602 __buffer, __buffer_size);
1603
1604 std::rotate(__left_split, __middle, __right_split);
1605 std::advance(__left_split, std::distance(__middle, __right_split));
1606 return __left_split;
1607 }
1608
1609 template<typename _ForwardIterator, typename _Predicate>
1610 _ForwardIterator
1611 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1612 _Predicate __pred)
1613 {
1614 __first = std::__find_if_not(__first, __last, __pred);
1615
1616 if (__first == __last)
1617 return __first;
1618
1619 typedef typename iterator_traits<_ForwardIterator>::value_type
1620 _ValueType;
1621 typedef typename iterator_traits<_ForwardIterator>::difference_type
1622 _DistanceType;
1623
1624 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
1625 return
1626 std::__stable_partition_adaptive(__first, __last, __pred,
1627 _DistanceType(__buf.requested_size()),
1628 __buf.begin(),
1629 _DistanceType(__buf.size()));
1630 }
1631
1632 /**
1633 * @brief Move elements for which a predicate is true to the beginning
1634 * of a sequence, preserving relative ordering.
1635 * @ingroup mutating_algorithms
1636 * @param __first A forward iterator.
1637 * @param __last A forward iterator.
1638 * @param __pred A predicate functor.
1639 * @return An iterator @p middle such that @p __pred(i) is true for each
1640 * iterator @p i in the range @p [first,middle) and false for each @p i
1641 * in the range @p [middle,last).
1642 *
1643 * Performs the same function as @p partition() with the additional
1644 * guarantee that the relative ordering of elements in each group is
1645 * preserved, so any two elements @p x and @p y in the range
1646 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1647 * relative ordering after calling @p stable_partition().
1648 */
1649 template<typename _ForwardIterator, typename _Predicate>
1650 inline _ForwardIterator
1651 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1652 _Predicate __pred)
1653 {
1654 // concept requirements
1655 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1656 _ForwardIterator>)
1657 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1658 typename iterator_traits<_ForwardIterator>::value_type>)
1659 __glibcxx_requires_valid_range(__first, __last);
1660
1661 return std::__stable_partition(__first, __last,
1662 __gnu_cxx::__ops::__pred_iter(__pred));
1663 }
1664
1665 /// This is a helper function for the sort routines.
1666 template<typename _RandomAccessIterator, typename _Compare>
1667 void
1668 __heap_select(_RandomAccessIterator __first,
1669 _RandomAccessIterator __middle,
1670 _RandomAccessIterator __last, _Compare __comp)
1671 {
1672 std::__make_heap(__first, __middle, __comp);
1673 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1674 if (__comp(__i, __first))
1675 std::__pop_heap(__first, __middle, __i, __comp);
1676 }
1677
1678 // partial_sort
1679
1680 template<typename _InputIterator, typename _RandomAccessIterator,
1681 typename _Compare>
1682 _RandomAccessIterator
1683 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1684 _RandomAccessIterator __result_first,
1685 _RandomAccessIterator __result_last,
1686 _Compare __comp)
1687 {
1688 typedef typename iterator_traits<_InputIterator>::value_type
1689 _InputValueType;
1690 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1691 typedef typename _RItTraits::difference_type _DistanceType;
1692
1693 if (__result_first == __result_last)
1694 return __result_last;
1695 _RandomAccessIterator __result_real_last = __result_first;
1696 while (__first != __last && __result_real_last != __result_last)
1697 {
1698 *__result_real_last = *__first;
1699 ++__result_real_last;
1700 ++__first;
1701 }
1702
1703 std::__make_heap(__result_first, __result_real_last, __comp);
1704 while (__first != __last)
1705 {
1706 if (__comp(__first, __result_first))
1707 std::__adjust_heap(__result_first, _DistanceType(0),
1708 _DistanceType(__result_real_last
1709 - __result_first),
1710 _InputValueType(*__first), __comp);
1711 ++__first;
1712 }
1713 std::__sort_heap(__result_first, __result_real_last, __comp);
1714 return __result_real_last;
1715 }
1716
1717 /**
1718 * @brief Copy the smallest elements of a sequence.
1719 * @ingroup sorting_algorithms
1720 * @param __first An iterator.
1721 * @param __last Another iterator.
1722 * @param __result_first A random-access iterator.
1723 * @param __result_last Another random-access iterator.
1724 * @return An iterator indicating the end of the resulting sequence.
1725 *
1726 * Copies and sorts the smallest N values from the range @p [__first,__last)
1727 * to the range beginning at @p __result_first, where the number of
1728 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1729 * @p (__result_last-__result_first).
1730 * After the sort if @e i and @e j are iterators in the range
1731 * @p [__result_first,__result_first+N) such that i precedes j then
1732 * *j<*i is false.
1733 * The value returned is @p __result_first+N.
1734 */
1735 template<typename _InputIterator, typename _RandomAccessIterator>
1736 inline _RandomAccessIterator
1737 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1738 _RandomAccessIterator __result_first,
1739 _RandomAccessIterator __result_last)
1740 {
1741#ifdef _GLIBCXX_CONCEPT_CHECKS
1742 typedef typename iterator_traits<_InputIterator>::value_type
1743 _InputValueType;
1744 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1745 _OutputValueType;
1746#endif
1747
1748 // concept requirements
1749 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1750 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1751 _OutputValueType>)
1752 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1753 _OutputValueType>)
1754 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1755 __glibcxx_requires_valid_range(__first, __last);
1756 __glibcxx_requires_irreflexive(__first, __last);
1757 __glibcxx_requires_valid_range(__result_first, __result_last);
1758
1759 return std::__partial_sort_copy(__first, __last,
1760 __result_first, __result_last,
1761 __gnu_cxx::__ops::__iter_less_iter());
1762 }
1763
1764 /**
1765 * @brief Copy the smallest elements of a sequence using a predicate for
1766 * comparison.
1767 * @ingroup sorting_algorithms
1768 * @param __first An input iterator.
1769 * @param __last Another input iterator.
1770 * @param __result_first A random-access iterator.
1771 * @param __result_last Another random-access iterator.
1772 * @param __comp A comparison functor.
1773 * @return An iterator indicating the end of the resulting sequence.
1774 *
1775 * Copies and sorts the smallest N values from the range @p [__first,__last)
1776 * to the range beginning at @p result_first, where the number of
1777 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1778 * @p (__result_last-__result_first).
1779 * After the sort if @e i and @e j are iterators in the range
1780 * @p [__result_first,__result_first+N) such that i precedes j then
1781 * @p __comp(*j,*i) is false.
1782 * The value returned is @p __result_first+N.
1783 */
1784 template<typename _InputIterator, typename _RandomAccessIterator,
1785 typename _Compare>
1786 inline _RandomAccessIterator
1787 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1788 _RandomAccessIterator __result_first,
1789 _RandomAccessIterator __result_last,
1790 _Compare __comp)
1791 {
1792#ifdef _GLIBCXX_CONCEPT_CHECKS
1793 typedef typename iterator_traits<_InputIterator>::value_type
1794 _InputValueType;
1795 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1796 _OutputValueType;
1797#endif
1798
1799 // concept requirements
1800 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1801 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1802 _RandomAccessIterator>)
1803 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1804 _OutputValueType>)
1805 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1806 _InputValueType, _OutputValueType>)
1807 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1808 _OutputValueType, _OutputValueType>)
1809 __glibcxx_requires_valid_range(__first, __last);
1810 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1811 __glibcxx_requires_valid_range(__result_first, __result_last);
1812
1813 return std::__partial_sort_copy(__first, __last,
1814 __result_first, __result_last,
1815 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1816 }
1817
1818 /// This is a helper function for the sort routine.
1819 template<typename _RandomAccessIterator, typename _Compare>
1820 void
1821 __unguarded_linear_insert(_RandomAccessIterator __last,
1822 _Compare __comp)
1823 {
1824 typename iterator_traits<_RandomAccessIterator>::value_type
1825 __val = _GLIBCXX_MOVE(*__last)std::move(*__last);
1826 _RandomAccessIterator __next = __last;
1827 --__next;
1828 while (__comp(__val, __next))
1829 {
1830 *__last = _GLIBCXX_MOVE(*__next)std::move(*__next);
1831 __last = __next;
1832 --__next;
1833 }
1834 *__last = _GLIBCXX_MOVE(__val)std::move(__val);
1835 }
1836
1837 /// This is a helper function for the sort routine.
1838 template<typename _RandomAccessIterator, typename _Compare>
1839 void
1840 __insertion_sort(_RandomAccessIterator __first,
1841 _RandomAccessIterator __last, _Compare __comp)
1842 {
1843 if (__first == __last) return;
1844
1845 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1846 {
1847 if (__comp(__i, __first))
1848 {
1849 typename iterator_traits<_RandomAccessIterator>::value_type
1850 __val = _GLIBCXX_MOVE(*__i)std::move(*__i);
1851 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1)std::move_backward(__first, __i, __i + 1);
1852 *__first = _GLIBCXX_MOVE(__val)std::move(__val);
1853 }
1854 else
1855 std::__unguarded_linear_insert(__i,
1856 __gnu_cxx::__ops::__val_comp_iter(__comp));
1857 }
1858 }
1859
1860 /// This is a helper function for the sort routine.
1861 template<typename _RandomAccessIterator, typename _Compare>
1862 inline void
1863 __unguarded_insertion_sort(_RandomAccessIterator __first,
1864 _RandomAccessIterator __last, _Compare __comp)
1865 {
1866 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1867 std::__unguarded_linear_insert(__i,
1868 __gnu_cxx::__ops::__val_comp_iter(__comp));
1869 }
1870
1871 /**
1872 * @doctodo
1873 * This controls some aspect of the sort routines.
1874 */
1875 enum { _S_threshold = 16 };
1876
1877 /// This is a helper function for the sort routine.
1878 template<typename _RandomAccessIterator, typename _Compare>
1879 void
1880 __final_insertion_sort(_RandomAccessIterator __first,
1881 _RandomAccessIterator __last, _Compare __comp)
1882 {
1883 if (__last - __first > int(_S_threshold))
1884 {
1885 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1886 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1887 __comp);
1888 }
1889 else
1890 std::__insertion_sort(__first, __last, __comp);
1891 }
1892
1893 /// This is a helper function...
1894 template<typename _RandomAccessIterator, typename _Compare>
1895 _RandomAccessIterator
1896 __unguarded_partition(_RandomAccessIterator __first,
1897 _RandomAccessIterator __last,
1898 _RandomAccessIterator __pivot, _Compare __comp)
1899 {
1900 while (true)
1901 {
1902 while (__comp(__first, __pivot))
1903 ++__first;
1904 --__last;
1905 while (__comp(__pivot, __last))
1906 --__last;
1907 if (!(__first < __last))
1908 return __first;
1909 std::iter_swap(__first, __last);
1910 ++__first;
1911 }
1912 }
1913
1914 /// This is a helper function...
1915 template<typename _RandomAccessIterator, typename _Compare>
1916 inline _RandomAccessIterator
1917 __unguarded_partition_pivot(_RandomAccessIterator __first,
1918 _RandomAccessIterator __last, _Compare __comp)
1919 {
1920 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1921 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
1922 __comp);
1923 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1924 }
1925
1926 template<typename _RandomAccessIterator, typename _Compare>
1927 inline void
1928 __partial_sort(_RandomAccessIterator __first,
1929 _RandomAccessIterator __middle,
1930 _RandomAccessIterator __last,
1931 _Compare __comp)
1932 {
1933 std::__heap_select(__first, __middle, __last, __comp);
1934 std::__sort_heap(__first, __middle, __comp);
1935 }
1936
1937 /// This is a helper function for the sort routine.
1938 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1939 void
1940 __introsort_loop(_RandomAccessIterator __first,
1941 _RandomAccessIterator __last,
1942 _Size __depth_limit, _Compare __comp)
1943 {
1944 while (__last - __first > int(_S_threshold))
1945 {
1946 if (__depth_limit == 0)
1947 {
1948 std::__partial_sort(__first, __last, __last, __comp);
1949 return;
1950 }
1951 --__depth_limit;
1952 _RandomAccessIterator __cut =
1953 std::__unguarded_partition_pivot(__first, __last, __comp);
1954 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1955 __last = __cut;
1956 }
1957 }
1958
1959 // sort
1960
1961 template<typename _RandomAccessIterator, typename _Compare>
1962 inline void
1963 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1964 _Compare __comp)
1965 {
1966 if (__first != __last)
1967 {
1968 std::__introsort_loop(__first, __last,
1969 std::__lg(__last - __first) * 2,
1970 __comp);
1971 std::__final_insertion_sort(__first, __last, __comp);
1972 }
1973 }
1974
1975 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1976 void
1977 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1978 _RandomAccessIterator __last, _Size __depth_limit,
1979 _Compare __comp)
1980 {
1981 while (__last - __first > 3)
1982 {
1983 if (__depth_limit == 0)
1984 {
1985 std::__heap_select(__first, __nth + 1, __last, __comp);
1986 // Place the nth largest element in its final position.
1987 std::iter_swap(__first, __nth);
1988 return;
1989 }
1990 --__depth_limit;
1991 _RandomAccessIterator __cut =
1992 std::__unguarded_partition_pivot(__first, __last, __comp);
1993 if (__cut <= __nth)
1994 __first = __cut;
1995 else
1996 __last = __cut;
1997 }
1998 std::__insertion_sort(__first, __last, __comp);
1999 }
2000
2001 // nth_element
2002
2003 // lower_bound moved to stl_algobase.h
2004
2005 /**
2006 * @brief Finds the first position in which @p __val could be inserted
2007 * without changing the ordering.
2008 * @ingroup binary_search_algorithms
2009 * @param __first An iterator.
2010 * @param __last Another iterator.
2011 * @param __val The search term.
2012 * @param __comp A functor to use for comparisons.
2013 * @return An iterator pointing to the first element <em>not less
2014 * than</em> @p __val, or end() if every element is less
2015 * than @p __val.
2016 * @ingroup binary_search_algorithms
2017 *
2018 * The comparison function should have the same effects on ordering as
2019 * the function used for the initial sort.
2020 */
2021 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2022 inline _ForwardIterator
2023 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2024 const _Tp& __val, _Compare __comp)
2025 {
2026 // concept requirements
2027 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2028 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2029 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2030 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2031 __val, __comp);
2032
2033 return std::__lower_bound(__first, __last, __val,
2034 __gnu_cxx::__ops::__iter_comp_val(__comp));
2035 }
2036
2037 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2038 _ForwardIterator
2039 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2040 const _Tp& __val, _Compare __comp)
2041 {
2042 typedef typename iterator_traits<_ForwardIterator>::difference_type
2043 _DistanceType;
2044
2045 _DistanceType __len = std::distance(__first, __last);
2046
2047 while (__len > 0)
2048 {
2049 _DistanceType __half = __len >> 1;
2050 _ForwardIterator __middle = __first;
2051 std::advance(__middle, __half);
2052 if (__comp(__val, __middle))
2053 __len = __half;
2054 else
2055 {
2056 __first = __middle;
2057 ++__first;
2058 __len = __len - __half - 1;
2059 }
2060 }
2061 return __first;
2062 }
2063
2064 /**
2065 * @brief Finds the last position in which @p __val could be inserted
2066 * without changing the ordering.
2067 * @ingroup binary_search_algorithms
2068 * @param __first An iterator.
2069 * @param __last Another iterator.
2070 * @param __val The search term.
2071 * @return An iterator pointing to the first element greater than @p __val,
2072 * or end() if no elements are greater than @p __val.
2073 * @ingroup binary_search_algorithms
2074 */
2075 template<typename _ForwardIterator, typename _Tp>
2076 inline _ForwardIterator
2077 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2078 const _Tp& __val)
2079 {
2080 // concept requirements
2081 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2082 __glibcxx_function_requires(_LessThanOpConcept<
2083 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2084 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2085
2086 return std::__upper_bound(__first, __last, __val,
2087 __gnu_cxx::__ops::__val_less_iter());
2088 }
2089
2090 /**
2091 * @brief Finds the last position in which @p __val could be inserted
2092 * without changing the ordering.
2093 * @ingroup binary_search_algorithms
2094 * @param __first An iterator.
2095 * @param __last Another iterator.
2096 * @param __val The search term.
2097 * @param __comp A functor to use for comparisons.
2098 * @return An iterator pointing to the first element greater than @p __val,
2099 * or end() if no elements are greater than @p __val.
2100 * @ingroup binary_search_algorithms
2101 *
2102 * The comparison function should have the same effects on ordering as
2103 * the function used for the initial sort.
2104 */
2105 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2106 inline _ForwardIterator
2107 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2108 const _Tp& __val, _Compare __comp)
2109 {
2110 // concept requirements
2111 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2112 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2113 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2114 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2115 __val, __comp);
2116
2117 return std::__upper_bound(__first, __last, __val,
2118 __gnu_cxx::__ops::__val_comp_iter(__comp));
2119 }
2120
2121 template<typename _ForwardIterator, typename _Tp,
2122 typename _CompareItTp, typename _CompareTpIt>
2123 pair<_ForwardIterator, _ForwardIterator>
2124 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2125 const _Tp& __val,
2126 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2127 {
2128 typedef typename iterator_traits<_ForwardIterator>::difference_type
2129 _DistanceType;
2130
2131 _DistanceType __len = std::distance(__first, __last);
2132
2133 while (__len > 0)
2134 {
2135 _DistanceType __half = __len >> 1;
2136 _ForwardIterator __middle = __first;
2137 std::advance(__middle, __half);
2138 if (__comp_it_val(__middle, __val))
2139 {
2140 __first = __middle;
2141 ++__first;
2142 __len = __len - __half - 1;
2143 }
2144 else if (__comp_val_it(__val, __middle))
2145 __len = __half;
2146 else
2147 {
2148 _ForwardIterator __left
2149 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2150 std::advance(__first, __len);
2151 _ForwardIterator __right
2152 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2153 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2154 }
2155 }
2156 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2157 }
2158
2159 /**
2160 * @brief Finds the largest subrange in which @p __val could be inserted
2161 * at any place in it without changing the ordering.
2162 * @ingroup binary_search_algorithms
2163 * @param __first An iterator.
2164 * @param __last Another iterator.
2165 * @param __val The search term.
2166 * @return An pair of iterators defining the subrange.
2167 * @ingroup binary_search_algorithms
2168 *
2169 * This is equivalent to
2170 * @code
2171 * std::make_pair(lower_bound(__first, __last, __val),
2172 * upper_bound(__first, __last, __val))
2173 * @endcode
2174 * but does not actually call those functions.
2175 */
2176 template<typename _ForwardIterator, typename _Tp>
2177 inline pair<_ForwardIterator, _ForwardIterator>
2178 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2179 const _Tp& __val)
2180 {
2181 // concept requirements
2182 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2183 __glibcxx_function_requires(_LessThanOpConcept<
2184 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2185 __glibcxx_function_requires(_LessThanOpConcept<
2186 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2187 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2188 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2189
2190 return std::__equal_range(__first, __last, __val,
2191 __gnu_cxx::__ops::__iter_less_val(),
2192 __gnu_cxx::__ops::__val_less_iter());
2193 }
2194
2195 /**
2196 * @brief Finds the largest subrange in which @p __val could be inserted
2197 * at any place in it without changing the ordering.
2198 * @param __first An iterator.
2199 * @param __last Another iterator.
2200 * @param __val The search term.
2201 * @param __comp A functor to use for comparisons.
2202 * @return An pair of iterators defining the subrange.
2203 * @ingroup binary_search_algorithms
2204 *
2205 * This is equivalent to
2206 * @code
2207 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2208 * upper_bound(__first, __last, __val, __comp))
2209 * @endcode
2210 * but does not actually call those functions.
2211 */
2212 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2213 inline pair<_ForwardIterator, _ForwardIterator>
2214 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2215 const _Tp& __val, _Compare __comp)
2216 {
2217 // concept requirements
2218 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2219 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2220 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2221 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2222 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2223 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2224 __val, __comp);
2225 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2226 __val, __comp);
2227
2228 return std::__equal_range(__first, __last, __val,
2229 __gnu_cxx::__ops::__iter_comp_val(__comp),
2230 __gnu_cxx::__ops::__val_comp_iter(__comp));
2231 }
2232
2233 /**
2234 * @brief Determines whether an element exists in a range.
2235 * @ingroup binary_search_algorithms
2236 * @param __first An iterator.
2237 * @param __last Another iterator.
2238 * @param __val The search term.
2239 * @return True if @p __val (or its equivalent) is in [@p
2240 * __first,@p __last ].
2241 *
2242 * Note that this does not actually return an iterator to @p __val. For
2243 * that, use std::find or a container's specialized find member functions.
2244 */
2245 template<typename _ForwardIterator, typename _Tp>
2246 bool
2247 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2248 const _Tp& __val)
2249 {
2250 // concept requirements
2251 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2252 __glibcxx_function_requires(_LessThanOpConcept<
2253 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2254 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2255 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2256
2257 _ForwardIterator __i
2258 = std::__lower_bound(__first, __last, __val,
2259 __gnu_cxx::__ops::__iter_less_val());
2260 return __i != __last && !(__val < *__i);
2261 }
2262
2263 /**
2264 * @brief Determines whether an element exists in a range.
2265 * @ingroup binary_search_algorithms
2266 * @param __first An iterator.
2267 * @param __last Another iterator.
2268 * @param __val The search term.
2269 * @param __comp A functor to use for comparisons.
2270 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2271 *
2272 * Note that this does not actually return an iterator to @p __val. For
2273 * that, use std::find or a container's specialized find member functions.
2274 *
2275 * The comparison function should have the same effects on ordering as
2276 * the function used for the initial sort.
2277 */
2278 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2279 bool
2280 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2281 const _Tp& __val, _Compare __comp)
2282 {
2283 // concept requirements
2284 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2285 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2286 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2287 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2288 __val, __comp);
2289 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2290 __val, __comp);
2291
2292 _ForwardIterator __i
2293 = std::__lower_bound(__first, __last, __val,
2294 __gnu_cxx::__ops::__iter_comp_val(__comp));
2295 return __i != __last && !bool(__comp(__val, *__i));
2296 }
2297
2298 // merge
2299
2300 /// This is a helper function for the __merge_adaptive routines.
2301 template<typename _InputIterator1, typename _InputIterator2,
2302 typename _OutputIterator, typename _Compare>
2303 void
2304 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2305 _InputIterator2 __first2, _InputIterator2 __last2,
2306 _OutputIterator __result, _Compare __comp)
2307 {
2308 while (__first1 != __last1 && __first2 != __last2)
2309 {
2310 if (__comp(__first2, __first1))
2311 {
2312 *__result = _GLIBCXX_MOVE(*__first2)std::move(*__first2);
2313 ++__first2;
2314 }
2315 else
2316 {
2317 *__result = _GLIBCXX_MOVE(*__first1)std::move(*__first1);
2318 ++__first1;
2319 }
2320 ++__result;
2321 }
2322 if (__first1 != __last1)
2323 _GLIBCXX_MOVE3(__first1, __last1, __result)std::move(__first1, __last1, __result);
2324 }
2325
2326 /// This is a helper function for the __merge_adaptive routines.
2327 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2328 typename _BidirectionalIterator3, typename _Compare>
2329 void
2330 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2331 _BidirectionalIterator1 __last1,
2332 _BidirectionalIterator2 __first2,
2333 _BidirectionalIterator2 __last2,
2334 _BidirectionalIterator3 __result,
2335 _Compare __comp)
2336 {
2337 if (__first1 == __last1)
2338 {
2339 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result)std::move_backward(__first2, __last2, __result);
2340 return;
2341 }
2342 else if (__first2 == __last2)
2343 return;
2344
2345 --__last1;
2346 --__last2;
2347 while (true)
2348 {
2349 if (__comp(__last2, __last1))
2350 {
2351 *--__result = _GLIBCXX_MOVE(*__last1)std::move(*__last1);
2352 if (__first1 == __last1)
2353 {
2354 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result)std::move_backward(__first2, ++__last2, __result);
2355 return;
2356 }
2357 --__last1;
2358 }
2359 else
2360 {
2361 *--__result = _GLIBCXX_MOVE(*__last2)std::move(*__last2);
2362 if (__first2 == __last2)
2363 return;
2364 --__last2;
2365 }
2366 }
2367 }
2368
2369 /// This is a helper function for the merge routines.
2370 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2371 typename _Distance>
2372 _BidirectionalIterator1
2373 __rotate_adaptive(_BidirectionalIterator1 __first,
2374 _BidirectionalIterator1 __middle,
2375 _BidirectionalIterator1 __last,
2376 _Distance __len1, _Distance __len2,
2377 _BidirectionalIterator2 __buffer,
2378 _Distance __buffer_size)
2379 {
2380 _BidirectionalIterator2 __buffer_end;
2381 if (__len1 > __len2 && __len2 <= __buffer_size)
2382 {
2383 if (__len2)
2384 {
2385 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer)std::move(__middle, __last, __buffer);
2386 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last)std::move_backward(__first, __middle, __last);
2387 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first)std::move(__buffer, __buffer_end, __first);
2388 }
2389 else
2390 return __first;
2391 }
2392 else if (__len1 <= __buffer_size)
2393 {
2394 if (__len1)
2395 {
2396 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer)std::move(__first, __middle, __buffer);
2397 _GLIBCXX_MOVE3(__middle, __last, __first)std::move(__middle, __last, __first);
2398 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last)std::move_backward(__buffer, __buffer_end, __last);
2399 }
2400 else
2401 return __last;
2402 }
2403 else
2404 {
2405 std::rotate(__first, __middle, __last);
2406 std::advance(__first, std::distance(__middle, __last));
2407 return __first;
2408 }
2409 }
2410
2411 /// This is a helper function for the merge routines.
2412 template<typename _BidirectionalIterator, typename _Distance,
2413 typename _Pointer, typename _Compare>
2414 void
2415 __merge_adaptive(_BidirectionalIterator __first,
2416 _BidirectionalIterator __middle,
2417 _BidirectionalIterator __last,
2418 _Distance __len1, _Distance __len2,
2419 _Pointer __buffer, _Distance __buffer_size,
2420 _Compare __comp)
2421 {
2422 if (__len1 <= __len2 && __len1 <= __buffer_size)
2423 {
2424 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer)std::move(__first, __middle, __buffer);
2425 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2426 __first, __comp);
2427 }
2428 else if (__len2 <= __buffer_size)
2429 {
2430 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer)std::move(__middle, __last, __buffer);
2431 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2432 __buffer_end, __last, __comp);
2433 }
2434 else
2435 {
2436 _BidirectionalIterator __first_cut = __first;
2437 _BidirectionalIterator __second_cut = __middle;
2438 _Distance __len11 = 0;
2439 _Distance __len22 = 0;
2440 if (__len1 > __len2)
2441 {
2442 __len11 = __len1 / 2;
2443 std::advance(__first_cut, __len11);
2444 __second_cut
2445 = std::__lower_bound(__middle, __last, *__first_cut,
2446 __gnu_cxx::__ops::__iter_comp_val(__comp));
2447 __len22 = std::distance(__middle, __second_cut);
2448 }
2449 else
2450 {
2451 __len22 = __len2 / 2;
2452 std::advance(__second_cut, __len22);
2453 __first_cut
2454 = std::__upper_bound(__first, __middle, *__second_cut,
2455 __gnu_cxx::__ops::__val_comp_iter(__comp));
2456 __len11 = std::distance(__first, __first_cut);
2457 }
2458
2459 _BidirectionalIterator __new_middle
2460 = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2461 __len1 - __len11, __len22, __buffer,
2462 __buffer_size);
2463 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2464 __len22, __buffer, __buffer_size, __comp);
2465 std::__merge_adaptive(__new_middle, __second_cut, __last,
2466 __len1 - __len11,
2467 __len2 - __len22, __buffer,
2468 __buffer_size, __comp);
2469 }
2470 }
2471
2472 /// This is a helper function for the merge routines.
2473 template<typename _BidirectionalIterator, typename _Distance,
2474 typename _Compare>
2475 void
2476 __merge_without_buffer(_BidirectionalIterator __first,
2477 _BidirectionalIterator __middle,
2478 _BidirectionalIterator __last,
2479 _Distance __len1, _Distance __len2,
2480 _Compare __comp)
2481 {
2482 if (__len1 == 0 || __len2 == 0)
2483 return;
2484
2485 if (__len1 + __len2 == 2)
2486 {
2487 if (__comp(__middle, __first))
2488 std::iter_swap(__first, __middle);
2489 return;
2490 }
2491
2492 _BidirectionalIterator __first_cut = __first;
2493 _BidirectionalIterator __second_cut = __middle;
2494 _Distance __len11 = 0;
2495 _Distance __len22 = 0;
2496 if (__len1 > __len2)
2497 {