File: | tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp |
Warning: | line 374, column 7 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- lib/ReaderWriter/MachO/CompactUnwindPass.cpp -------------*- C++ -*-===// | |||||||||
2 | // | |||||||||
3 | // The LLVM Linker | |||||||||
4 | // | |||||||||
5 | // This file is distributed under the University of Illinois Open Source | |||||||||
6 | // License. See LICENSE.TXT for details. | |||||||||
7 | // | |||||||||
8 | //===----------------------------------------------------------------------===// | |||||||||
9 | /// | |||||||||
10 | /// \file A pass to convert MachO's __compact_unwind sections into the final | |||||||||
11 | /// __unwind_info format used during runtime. See | |||||||||
12 | /// mach-o/compact_unwind_encoding.h for more details on the formats involved. | |||||||||
13 | /// | |||||||||
14 | //===----------------------------------------------------------------------===// | |||||||||
15 | ||||||||||
16 | #include "ArchHandler.h" | |||||||||
17 | #include "File.h" | |||||||||
18 | #include "MachONormalizedFileBinaryUtils.h" | |||||||||
19 | #include "MachOPasses.h" | |||||||||
20 | #include "lld/Common/LLVM.h" | |||||||||
21 | #include "lld/Core/DefinedAtom.h" | |||||||||
22 | #include "lld/Core/File.h" | |||||||||
23 | #include "lld/Core/Reference.h" | |||||||||
24 | #include "lld/Core/Simple.h" | |||||||||
25 | #include "llvm/ADT/DenseMap.h" | |||||||||
26 | #include "llvm/Support/Debug.h" | |||||||||
27 | #include "llvm/Support/Format.h" | |||||||||
28 | ||||||||||
29 | #define DEBUG_TYPE"macho-compact-unwind" "macho-compact-unwind" | |||||||||
30 | ||||||||||
31 | namespace lld { | |||||||||
32 | namespace mach_o { | |||||||||
33 | ||||||||||
34 | namespace { | |||||||||
35 | struct CompactUnwindEntry { | |||||||||
36 | const Atom *rangeStart; | |||||||||
37 | const Atom *personalityFunction; | |||||||||
38 | const Atom *lsdaLocation; | |||||||||
39 | const Atom *ehFrame; | |||||||||
40 | ||||||||||
41 | uint32_t rangeLength; | |||||||||
42 | ||||||||||
43 | // There are 3 types of compact unwind entry, distinguished by the encoding | |||||||||
44 | // value: 0 indicates a function with no unwind info; | |||||||||
45 | // _archHandler.dwarfCompactUnwindType() indicates that the entry defers to | |||||||||
46 | // __eh_frame, and that the ehFrame entry will be valid; any other value is a | |||||||||
47 | // real compact unwind entry -- personalityFunction will be set and | |||||||||
48 | // lsdaLocation may be. | |||||||||
49 | uint32_t encoding; | |||||||||
50 | ||||||||||
51 | CompactUnwindEntry(const DefinedAtom *function) | |||||||||
52 | : rangeStart(function), personalityFunction(nullptr), | |||||||||
53 | lsdaLocation(nullptr), ehFrame(nullptr), rangeLength(function->size()), | |||||||||
54 | encoding(0) {} | |||||||||
55 | ||||||||||
56 | CompactUnwindEntry() | |||||||||
57 | : rangeStart(nullptr), personalityFunction(nullptr), | |||||||||
58 | lsdaLocation(nullptr), ehFrame(nullptr), rangeLength(0), encoding(0) {} | |||||||||
59 | }; | |||||||||
60 | ||||||||||
61 | struct UnwindInfoPage { | |||||||||
62 | ArrayRef<CompactUnwindEntry> entries; | |||||||||
63 | }; | |||||||||
64 | } | |||||||||
65 | ||||||||||
66 | class UnwindInfoAtom : public SimpleDefinedAtom { | |||||||||
67 | public: | |||||||||
68 | UnwindInfoAtom(ArchHandler &archHandler, const File &file, bool isBig, | |||||||||
69 | std::vector<const Atom *> &personalities, | |||||||||
70 | std::vector<uint32_t> &commonEncodings, | |||||||||
71 | std::vector<UnwindInfoPage> &pages, uint32_t numLSDAs) | |||||||||
72 | : SimpleDefinedAtom(file), _archHandler(archHandler), | |||||||||
73 | _commonEncodingsOffset(7 * sizeof(uint32_t)), | |||||||||
74 | _personalityArrayOffset(_commonEncodingsOffset + | |||||||||
75 | commonEncodings.size() * sizeof(uint32_t)), | |||||||||
76 | _topLevelIndexOffset(_personalityArrayOffset + | |||||||||
77 | personalities.size() * sizeof(uint32_t)), | |||||||||
78 | _lsdaIndexOffset(_topLevelIndexOffset + | |||||||||
79 | 3 * (pages.size() + 1) * sizeof(uint32_t)), | |||||||||
80 | _firstPageOffset(_lsdaIndexOffset + 2 * numLSDAs * sizeof(uint32_t)), | |||||||||
81 | _isBig(isBig) { | |||||||||
82 | ||||||||||
83 | addHeader(commonEncodings.size(), personalities.size(), pages.size()); | |||||||||
84 | addCommonEncodings(commonEncodings); | |||||||||
85 | addPersonalityFunctions(personalities); | |||||||||
86 | addTopLevelIndexes(pages); | |||||||||
87 | addLSDAIndexes(pages, numLSDAs); | |||||||||
88 | addSecondLevelPages(pages); | |||||||||
89 | } | |||||||||
90 | ||||||||||
91 | ~UnwindInfoAtom() override = default; | |||||||||
92 | ||||||||||
93 | ContentType contentType() const override { | |||||||||
94 | return DefinedAtom::typeProcessedUnwindInfo; | |||||||||
95 | } | |||||||||
96 | ||||||||||
97 | Alignment alignment() const override { return 4; } | |||||||||
98 | ||||||||||
99 | uint64_t size() const override { return _contents.size(); } | |||||||||
100 | ||||||||||
101 | ContentPermissions permissions() const override { | |||||||||
102 | return DefinedAtom::permR__; | |||||||||
103 | } | |||||||||
104 | ||||||||||
105 | ArrayRef<uint8_t> rawContent() const override { return _contents; } | |||||||||
106 | ||||||||||
107 | void addHeader(uint32_t numCommon, uint32_t numPersonalities, | |||||||||
108 | uint32_t numPages) { | |||||||||
109 | using normalized::write32; | |||||||||
110 | ||||||||||
111 | uint32_t headerSize = 7 * sizeof(uint32_t); | |||||||||
112 | _contents.resize(headerSize); | |||||||||
113 | ||||||||||
114 | uint8_t *headerEntries = _contents.data(); | |||||||||
115 | // version | |||||||||
116 | write32(headerEntries, 1, _isBig); | |||||||||
117 | // commonEncodingsArraySectionOffset | |||||||||
118 | write32(headerEntries + sizeof(uint32_t), _commonEncodingsOffset, _isBig); | |||||||||
119 | // commonEncodingsArrayCount | |||||||||
120 | write32(headerEntries + 2 * sizeof(uint32_t), numCommon, _isBig); | |||||||||
121 | // personalityArraySectionOffset | |||||||||
122 | write32(headerEntries + 3 * sizeof(uint32_t), _personalityArrayOffset, | |||||||||
123 | _isBig); | |||||||||
124 | // personalityArrayCount | |||||||||
125 | write32(headerEntries + 4 * sizeof(uint32_t), numPersonalities, _isBig); | |||||||||
126 | // indexSectionOffset | |||||||||
127 | write32(headerEntries + 5 * sizeof(uint32_t), _topLevelIndexOffset, _isBig); | |||||||||
128 | // indexCount | |||||||||
129 | write32(headerEntries + 6 * sizeof(uint32_t), numPages + 1, _isBig); | |||||||||
130 | } | |||||||||
131 | ||||||||||
132 | /// Add the list of common encodings to the section; this is simply an array | |||||||||
133 | /// of uint32_t compact values. Size has already been specified in the header. | |||||||||
134 | void addCommonEncodings(std::vector<uint32_t> &commonEncodings) { | |||||||||
135 | using normalized::write32; | |||||||||
136 | ||||||||||
137 | _contents.resize(_commonEncodingsOffset + | |||||||||
138 | commonEncodings.size() * sizeof(uint32_t)); | |||||||||
139 | uint8_t *commonEncodingsArea = | |||||||||
140 | reinterpret_cast<uint8_t *>(_contents.data() + _commonEncodingsOffset); | |||||||||
141 | ||||||||||
142 | for (uint32_t encoding : commonEncodings) { | |||||||||
143 | write32(commonEncodingsArea, encoding, _isBig); | |||||||||
144 | commonEncodingsArea += sizeof(uint32_t); | |||||||||
145 | } | |||||||||
146 | } | |||||||||
147 | ||||||||||
148 | void addPersonalityFunctions(std::vector<const Atom *> personalities) { | |||||||||
149 | _contents.resize(_personalityArrayOffset + | |||||||||
150 | personalities.size() * sizeof(uint32_t)); | |||||||||
151 | ||||||||||
152 | for (unsigned i = 0; i < personalities.size(); ++i) | |||||||||
153 | addImageReferenceIndirect(_personalityArrayOffset + i * sizeof(uint32_t), | |||||||||
154 | personalities[i]); | |||||||||
155 | } | |||||||||
156 | ||||||||||
157 | void addTopLevelIndexes(std::vector<UnwindInfoPage> &pages) { | |||||||||
158 | using normalized::write32; | |||||||||
159 | ||||||||||
160 | uint32_t numIndexes = pages.size() + 1; | |||||||||
161 | _contents.resize(_topLevelIndexOffset + numIndexes * 3 * sizeof(uint32_t)); | |||||||||
162 | ||||||||||
163 | uint32_t pageLoc = _firstPageOffset; | |||||||||
164 | ||||||||||
165 | // The most difficult job here is calculating the LSDAs; everything else | |||||||||
166 | // follows fairly naturally, but we can't state where the first | |||||||||
167 | uint8_t *indexData = &_contents[_topLevelIndexOffset]; | |||||||||
168 | uint32_t numLSDAs = 0; | |||||||||
169 | for (unsigned i = 0; i < pages.size(); ++i) { | |||||||||
170 | // functionOffset | |||||||||
171 | addImageReference(_topLevelIndexOffset + 3 * i * sizeof(uint32_t), | |||||||||
172 | pages[i].entries[0].rangeStart); | |||||||||
173 | // secondLevelPagesSectionOffset | |||||||||
174 | write32(indexData + (3 * i + 1) * sizeof(uint32_t), pageLoc, _isBig); | |||||||||
175 | write32(indexData + (3 * i + 2) * sizeof(uint32_t), | |||||||||
176 | _lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t), _isBig); | |||||||||
177 | ||||||||||
178 | for (auto &entry : pages[i].entries) | |||||||||
179 | if (entry.lsdaLocation) | |||||||||
180 | ++numLSDAs; | |||||||||
181 | } | |||||||||
182 | ||||||||||
183 | // Finally, write out the final sentinel index | |||||||||
184 | auto &finalEntry = pages[pages.size() - 1].entries.back(); | |||||||||
185 | addImageReference(_topLevelIndexOffset + | |||||||||
186 | 3 * pages.size() * sizeof(uint32_t), | |||||||||
187 | finalEntry.rangeStart, finalEntry.rangeLength); | |||||||||
188 | // secondLevelPagesSectionOffset => 0 | |||||||||
189 | write32(indexData + (3 * pages.size() + 2) * sizeof(uint32_t), | |||||||||
190 | _lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t), _isBig); | |||||||||
191 | } | |||||||||
192 | ||||||||||
193 | void addLSDAIndexes(std::vector<UnwindInfoPage> &pages, uint32_t numLSDAs) { | |||||||||
194 | _contents.resize(_lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t)); | |||||||||
195 | ||||||||||
196 | uint32_t curOffset = _lsdaIndexOffset; | |||||||||
197 | for (auto &page : pages) { | |||||||||
198 | for (auto &entry : page.entries) { | |||||||||
199 | if (!entry.lsdaLocation) | |||||||||
200 | continue; | |||||||||
201 | ||||||||||
202 | addImageReference(curOffset, entry.rangeStart); | |||||||||
203 | addImageReference(curOffset + sizeof(uint32_t), entry.lsdaLocation); | |||||||||
204 | curOffset += 2 * sizeof(uint32_t); | |||||||||
205 | } | |||||||||
206 | } | |||||||||
207 | } | |||||||||
208 | ||||||||||
209 | void addSecondLevelPages(std::vector<UnwindInfoPage> &pages) { | |||||||||
210 | for (auto &page : pages) { | |||||||||
211 | addRegularSecondLevelPage(page); | |||||||||
212 | } | |||||||||
213 | } | |||||||||
214 | ||||||||||
215 | void addRegularSecondLevelPage(const UnwindInfoPage &page) { | |||||||||
216 | uint32_t curPageOffset = _contents.size(); | |||||||||
217 | const int16_t headerSize = sizeof(uint32_t) + 2 * sizeof(uint16_t); | |||||||||
218 | uint32_t curPageSize = | |||||||||
219 | headerSize + 2 * page.entries.size() * sizeof(uint32_t); | |||||||||
220 | _contents.resize(curPageOffset + curPageSize); | |||||||||
221 | ||||||||||
222 | using normalized::write32; | |||||||||
223 | using normalized::write16; | |||||||||
224 | // 2 => regular page | |||||||||
225 | write32(&_contents[curPageOffset], 2, _isBig); | |||||||||
226 | // offset of 1st entry | |||||||||
227 | write16(&_contents[curPageOffset + 4], headerSize, _isBig); | |||||||||
228 | write16(&_contents[curPageOffset + 6], page.entries.size(), _isBig); | |||||||||
229 | ||||||||||
230 | uint32_t pagePos = curPageOffset + headerSize; | |||||||||
231 | for (auto &entry : page.entries) { | |||||||||
232 | addImageReference(pagePos, entry.rangeStart); | |||||||||
233 | ||||||||||
234 | write32(_contents.data() + pagePos + sizeof(uint32_t), entry.encoding, | |||||||||
235 | _isBig); | |||||||||
236 | if ((entry.encoding & 0x0f000000U) == | |||||||||
237 | _archHandler.dwarfCompactUnwindType()) | |||||||||
238 | addEhFrameReference(pagePos + sizeof(uint32_t), entry.ehFrame); | |||||||||
239 | ||||||||||
240 | pagePos += 2 * sizeof(uint32_t); | |||||||||
241 | } | |||||||||
242 | } | |||||||||
243 | ||||||||||
244 | void addEhFrameReference(uint32_t offset, const Atom *dest, | |||||||||
245 | Reference::Addend addend = 0) { | |||||||||
246 | addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), | |||||||||
247 | _archHandler.unwindRefToEhFrameKind(), offset, dest, addend); | |||||||||
248 | } | |||||||||
249 | ||||||||||
250 | void addImageReference(uint32_t offset, const Atom *dest, | |||||||||
251 | Reference::Addend addend = 0) { | |||||||||
252 | addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), | |||||||||
253 | _archHandler.imageOffsetKind(), offset, dest, addend); | |||||||||
254 | } | |||||||||
255 | ||||||||||
256 | void addImageReferenceIndirect(uint32_t offset, const Atom *dest) { | |||||||||
257 | addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), | |||||||||
258 | _archHandler.imageOffsetKindIndirect(), offset, dest, 0); | |||||||||
259 | } | |||||||||
260 | ||||||||||
261 | private: | |||||||||
262 | mach_o::ArchHandler &_archHandler; | |||||||||
263 | std::vector<uint8_t> _contents; | |||||||||
264 | uint32_t _commonEncodingsOffset; | |||||||||
265 | uint32_t _personalityArrayOffset; | |||||||||
266 | uint32_t _topLevelIndexOffset; | |||||||||
267 | uint32_t _lsdaIndexOffset; | |||||||||
268 | uint32_t _firstPageOffset; | |||||||||
269 | bool _isBig; | |||||||||
270 | }; | |||||||||
271 | ||||||||||
272 | /// Pass for instantiating and optimizing GOT slots. | |||||||||
273 | /// | |||||||||
274 | class CompactUnwindPass : public Pass { | |||||||||
275 | public: | |||||||||
276 | CompactUnwindPass(const MachOLinkingContext &context) | |||||||||
277 | : _ctx(context), _archHandler(_ctx.archHandler()), | |||||||||
278 | _file(*_ctx.make_file<MachOFile>("<mach-o Compact Unwind Pass>")), | |||||||||
279 | _isBig(MachOLinkingContext::isBigEndian(_ctx.arch())) { | |||||||||
280 | _file.setOrdinal(_ctx.getNextOrdinalAndIncrement()); | |||||||||
281 | } | |||||||||
282 | ||||||||||
283 | private: | |||||||||
284 | llvm::Error perform(SimpleFile &mergedFile) override { | |||||||||
285 | LLVM_DEBUG(llvm::dbgs() << "MachO Compact Unwind pass\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << "MachO Compact Unwind pass\n" ; } } while (false); | |||||||||
286 | ||||||||||
287 | std::map<const Atom *, CompactUnwindEntry> unwindLocs; | |||||||||
288 | std::map<const Atom *, const Atom *> dwarfFrames; | |||||||||
289 | std::vector<const Atom *> personalities; | |||||||||
290 | uint32_t numLSDAs = 0; | |||||||||
291 | ||||||||||
292 | // First collect all __compact_unwind and __eh_frame entries, addressable by | |||||||||
293 | // the function referred to. | |||||||||
294 | collectCompactUnwindEntries(mergedFile, unwindLocs, personalities, | |||||||||
| ||||||||||
295 | numLSDAs); | |||||||||
296 | ||||||||||
297 | collectDwarfFrameEntries(mergedFile, dwarfFrames); | |||||||||
298 | ||||||||||
299 | // Skip rest of pass if no unwind info. | |||||||||
300 | if (unwindLocs.empty() && dwarfFrames.empty()) | |||||||||
301 | return llvm::Error::success(); | |||||||||
302 | ||||||||||
303 | // FIXME: if there are more than 4 personality functions then we need to | |||||||||
304 | // defer to DWARF info for the ones we don't put in the list. They should | |||||||||
305 | // also probably be sorted by frequency. | |||||||||
306 | assert(personalities.size() <= 4)((personalities.size() <= 4) ? static_cast<void> (0) : __assert_fail ("personalities.size() <= 4", "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 306, __PRETTY_FUNCTION__)); | |||||||||
307 | ||||||||||
308 | // TODO: Find commmon encodings for use by compressed pages. | |||||||||
309 | std::vector<uint32_t> commonEncodings; | |||||||||
310 | ||||||||||
311 | // Now sort the entries by final address and fixup the compact encoding to | |||||||||
312 | // its final form (i.e. set personality function bits & create DWARF | |||||||||
313 | // references where needed). | |||||||||
314 | std::vector<CompactUnwindEntry> unwindInfos = createUnwindInfoEntries( | |||||||||
315 | mergedFile, unwindLocs, personalities, dwarfFrames); | |||||||||
316 | ||||||||||
317 | // Remove any unused eh-frame atoms. | |||||||||
318 | pruneUnusedEHFrames(mergedFile, unwindInfos, unwindLocs, dwarfFrames); | |||||||||
319 | ||||||||||
320 | // Finally, we can start creating pages based on these entries. | |||||||||
321 | ||||||||||
322 | LLVM_DEBUG(llvm::dbgs() << " Splitting entries into pages\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Splitting entries into pages\n" ; } } while (false); | |||||||||
323 | // FIXME: we split the entries into pages naively: lots of 4k pages followed | |||||||||
324 | // by a small one. ld64 tried to minimize space and align them to real 4k | |||||||||
325 | // boundaries. That might be worth doing, or perhaps we could perform some | |||||||||
326 | // minor balancing for expected number of lookups. | |||||||||
327 | std::vector<UnwindInfoPage> pages; | |||||||||
328 | auto remainingInfos = llvm::makeArrayRef(unwindInfos); | |||||||||
329 | do { | |||||||||
330 | pages.push_back(UnwindInfoPage()); | |||||||||
331 | ||||||||||
332 | // FIXME: we only create regular pages at the moment. These can hold up to | |||||||||
333 | // 1021 entries according to the documentation. | |||||||||
334 | unsigned entriesInPage = std::min(1021U, (unsigned)remainingInfos.size()); | |||||||||
335 | ||||||||||
336 | pages.back().entries = remainingInfos.slice(0, entriesInPage); | |||||||||
337 | remainingInfos = remainingInfos.slice(entriesInPage); | |||||||||
338 | ||||||||||
339 | LLVM_DEBUG(llvm::dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Page from " << pages.back().entries[0].rangeStart->name() << " to " << pages.back().entries.back().rangeStart->name () << " + " << llvm::format("0x%x", pages.back(). entries.back().rangeLength) << " has " << entriesInPage << " entries\n"; } } while (false) | |||||||||
340 | << " Page from "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Page from " << pages.back().entries[0].rangeStart->name() << " to " << pages.back().entries.back().rangeStart->name () << " + " << llvm::format("0x%x", pages.back(). entries.back().rangeLength) << " has " << entriesInPage << " entries\n"; } } while (false) | |||||||||
341 | << pages.back().entries[0].rangeStart->name() << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Page from " << pages.back().entries[0].rangeStart->name() << " to " << pages.back().entries.back().rangeStart->name () << " + " << llvm::format("0x%x", pages.back(). entries.back().rangeLength) << " has " << entriesInPage << " entries\n"; } } while (false) | |||||||||
342 | << pages.back().entries.back().rangeStart->name() << " + "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Page from " << pages.back().entries[0].rangeStart->name() << " to " << pages.back().entries.back().rangeStart->name () << " + " << llvm::format("0x%x", pages.back(). entries.back().rangeLength) << " has " << entriesInPage << " entries\n"; } } while (false) | |||||||||
343 | << llvm::format("0x%x",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Page from " << pages.back().entries[0].rangeStart->name() << " to " << pages.back().entries.back().rangeStart->name () << " + " << llvm::format("0x%x", pages.back(). entries.back().rangeLength) << " has " << entriesInPage << " entries\n"; } } while (false) | |||||||||
344 | pages.back().entries.back().rangeLength)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Page from " << pages.back().entries[0].rangeStart->name() << " to " << pages.back().entries.back().rangeStart->name () << " + " << llvm::format("0x%x", pages.back(). entries.back().rangeLength) << " has " << entriesInPage << " entries\n"; } } while (false) | |||||||||
345 | << " has " << entriesInPage << " entries\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Page from " << pages.back().entries[0].rangeStart->name() << " to " << pages.back().entries.back().rangeStart->name () << " + " << llvm::format("0x%x", pages.back(). entries.back().rangeLength) << " has " << entriesInPage << " entries\n"; } } while (false); | |||||||||
346 | } while (!remainingInfos.empty()); | |||||||||
347 | ||||||||||
348 | auto *unwind = new (_file.allocator()) | |||||||||
349 | UnwindInfoAtom(_archHandler, _file, _isBig, personalities, | |||||||||
350 | commonEncodings, pages, numLSDAs); | |||||||||
351 | mergedFile.addAtom(*unwind); | |||||||||
352 | ||||||||||
353 | // Finally, remove all __compact_unwind atoms now that we've processed them. | |||||||||
354 | mergedFile.removeDefinedAtomsIf([](const DefinedAtom *atom) { | |||||||||
355 | return atom->contentType() == DefinedAtom::typeCompactUnwindInfo; | |||||||||
356 | }); | |||||||||
357 | ||||||||||
358 | return llvm::Error::success(); | |||||||||
359 | } | |||||||||
360 | ||||||||||
361 | void collectCompactUnwindEntries( | |||||||||
362 | const SimpleFile &mergedFile, | |||||||||
363 | std::map<const Atom *, CompactUnwindEntry> &unwindLocs, | |||||||||
364 | std::vector<const Atom *> &personalities, uint32_t &numLSDAs) { | |||||||||
365 | LLVM_DEBUG(llvm::dbgs() << " Collecting __compact_unwind entries\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Collecting __compact_unwind entries\n" ; } } while (false); | |||||||||
366 | ||||||||||
367 | for (const DefinedAtom *atom : mergedFile.defined()) { | |||||||||
368 | if (atom->contentType() != DefinedAtom::typeCompactUnwindInfo) | |||||||||
369 | continue; | |||||||||
370 | ||||||||||
371 | auto unwindEntry = extractCompactUnwindEntry(atom); | |||||||||
372 | unwindLocs.insert(std::make_pair(unwindEntry.rangeStart, unwindEntry)); | |||||||||
373 | ||||||||||
374 | LLVM_DEBUG(llvm::dbgs() << " Entry for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << unwindEntry.rangeStart->name() << ", encoding=" << llvm::format("0x%08x", unwindEntry.encoding); } } while (false) | |||||||||
| ||||||||||
375 | << unwindEntry.rangeStart->name() << ", encoding="do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << unwindEntry.rangeStart->name() << ", encoding=" << llvm::format("0x%08x", unwindEntry.encoding); } } while (false) | |||||||||
376 | << llvm::format("0x%08x", unwindEntry.encoding))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << unwindEntry.rangeStart->name() << ", encoding=" << llvm::format("0x%08x", unwindEntry.encoding); } } while (false); | |||||||||
377 | if (unwindEntry.personalityFunction) | |||||||||
378 | LLVM_DEBUG(llvm::dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << ", personality=" << unwindEntry.personalityFunction->name() << ", lsdaLoc=" << unwindEntry.lsdaLocation->name(); } } while (false) | |||||||||
379 | << ", personality="do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << ", personality=" << unwindEntry.personalityFunction->name() << ", lsdaLoc=" << unwindEntry.lsdaLocation->name(); } } while (false) | |||||||||
380 | << unwindEntry.personalityFunction->name()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << ", personality=" << unwindEntry.personalityFunction->name() << ", lsdaLoc=" << unwindEntry.lsdaLocation->name(); } } while (false) | |||||||||
381 | << ", lsdaLoc=" << unwindEntry.lsdaLocation->name())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << ", personality=" << unwindEntry.personalityFunction->name() << ", lsdaLoc=" << unwindEntry.lsdaLocation->name(); } } while (false); | |||||||||
382 | LLVM_DEBUG(llvm::dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << '\n'; } } while (false); | |||||||||
383 | ||||||||||
384 | // Count number of LSDAs we see, since we need to know how big the index | |||||||||
385 | // will be while laying out the section. | |||||||||
386 | if (unwindEntry.lsdaLocation) | |||||||||
387 | ++numLSDAs; | |||||||||
388 | ||||||||||
389 | // Gather the personality functions now, so that they're in deterministic | |||||||||
390 | // order (derived from the DefinedAtom order). | |||||||||
391 | if (unwindEntry.personalityFunction) { | |||||||||
392 | auto pFunc = std::find(personalities.begin(), personalities.end(), | |||||||||
393 | unwindEntry.personalityFunction); | |||||||||
394 | if (pFunc == personalities.end()) | |||||||||
395 | personalities.push_back(unwindEntry.personalityFunction); | |||||||||
396 | } | |||||||||
397 | } | |||||||||
398 | } | |||||||||
399 | ||||||||||
400 | CompactUnwindEntry extractCompactUnwindEntry(const DefinedAtom *atom) { | |||||||||
401 | CompactUnwindEntry entry; | |||||||||
402 | ||||||||||
403 | for (const Reference *ref : *atom) { | |||||||||
404 | switch (ref->offsetInAtom()) { | |||||||||
405 | case 0: | |||||||||
406 | // FIXME: there could legitimately be functions with multiple encoding | |||||||||
407 | // entries. However, nothing produces them at the moment. | |||||||||
408 | assert(ref->addend() == 0 && "unexpected offset into function")((ref->addend() == 0 && "unexpected offset into function" ) ? static_cast<void> (0) : __assert_fail ("ref->addend() == 0 && \"unexpected offset into function\"" , "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 408, __PRETTY_FUNCTION__)); | |||||||||
409 | entry.rangeStart = ref->target(); | |||||||||
410 | break; | |||||||||
411 | case 0x10: | |||||||||
412 | assert(ref->addend() == 0 && "unexpected offset into personality fn")((ref->addend() == 0 && "unexpected offset into personality fn" ) ? static_cast<void> (0) : __assert_fail ("ref->addend() == 0 && \"unexpected offset into personality fn\"" , "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 412, __PRETTY_FUNCTION__)); | |||||||||
413 | entry.personalityFunction = ref->target(); | |||||||||
414 | break; | |||||||||
415 | case 0x18: | |||||||||
416 | assert(ref->addend() == 0 && "unexpected offset into LSDA atom")((ref->addend() == 0 && "unexpected offset into LSDA atom" ) ? static_cast<void> (0) : __assert_fail ("ref->addend() == 0 && \"unexpected offset into LSDA atom\"" , "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 416, __PRETTY_FUNCTION__)); | |||||||||
417 | entry.lsdaLocation = ref->target(); | |||||||||
418 | break; | |||||||||
419 | } | |||||||||
420 | } | |||||||||
421 | ||||||||||
422 | if (atom->rawContent().size() < 4 * sizeof(uint32_t)) | |||||||||
423 | return entry; | |||||||||
424 | ||||||||||
425 | using normalized::read32; | |||||||||
426 | entry.rangeLength = | |||||||||
427 | read32(atom->rawContent().data() + 2 * sizeof(uint32_t), _isBig); | |||||||||
428 | entry.encoding = | |||||||||
429 | read32(atom->rawContent().data() + 3 * sizeof(uint32_t), _isBig); | |||||||||
430 | return entry; | |||||||||
431 | } | |||||||||
432 | ||||||||||
433 | void | |||||||||
434 | collectDwarfFrameEntries(const SimpleFile &mergedFile, | |||||||||
435 | std::map<const Atom *, const Atom *> &dwarfFrames) { | |||||||||
436 | for (const DefinedAtom *ehFrameAtom : mergedFile.defined()) { | |||||||||
437 | if (ehFrameAtom->contentType() != DefinedAtom::typeCFI) | |||||||||
438 | continue; | |||||||||
439 | if (ArchHandler::isDwarfCIE(_isBig, ehFrameAtom)) | |||||||||
440 | continue; | |||||||||
441 | ||||||||||
442 | if (const Atom *function = _archHandler.fdeTargetFunction(ehFrameAtom)) | |||||||||
443 | dwarfFrames[function] = ehFrameAtom; | |||||||||
444 | } | |||||||||
445 | } | |||||||||
446 | ||||||||||
447 | /// Every atom defined in __TEXT,__text needs an entry in the final | |||||||||
448 | /// __unwind_info section (in order). These comes from two sources: | |||||||||
449 | /// + Input __compact_unwind sections where possible (after adding the | |||||||||
450 | /// personality function offset which is only known now). | |||||||||
451 | /// + A synthesised reference to __eh_frame if there's no __compact_unwind | |||||||||
452 | /// or too many personality functions to be accommodated. | |||||||||
453 | std::vector<CompactUnwindEntry> createUnwindInfoEntries( | |||||||||
454 | const SimpleFile &mergedFile, | |||||||||
455 | const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, | |||||||||
456 | const std::vector<const Atom *> &personalities, | |||||||||
457 | const std::map<const Atom *, const Atom *> &dwarfFrames) { | |||||||||
458 | std::vector<CompactUnwindEntry> unwindInfos; | |||||||||
459 | ||||||||||
460 | LLVM_DEBUG(llvm::dbgs() << " Creating __unwind_info entries\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Creating __unwind_info entries\n" ; } } while (false); | |||||||||
461 | // The final order in the __unwind_info section must be derived from the | |||||||||
462 | // order of typeCode atoms, since that's how they'll be put into the object | |||||||||
463 | // file eventually (yuck!). | |||||||||
464 | for (const DefinedAtom *atom : mergedFile.defined()) { | |||||||||
465 | if (atom->contentType() != DefinedAtom::typeCode) | |||||||||
466 | continue; | |||||||||
467 | ||||||||||
468 | unwindInfos.push_back(finalizeUnwindInfoEntryForAtom( | |||||||||
469 | atom, unwindLocs, personalities, dwarfFrames)); | |||||||||
470 | ||||||||||
471 | LLVM_DEBUG(llvm::dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << atom->name() << ", final encoding=" << llvm::format("0x%08x", unwindInfos.back().encoding) << '\n'; } } while (false) | |||||||||
472 | << " Entry for " << atom->name() << ", final encoding="do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << atom->name() << ", final encoding=" << llvm::format("0x%08x", unwindInfos.back().encoding) << '\n'; } } while (false) | |||||||||
473 | << llvm::format("0x%08x", unwindInfos.back().encoding)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << atom->name() << ", final encoding=" << llvm::format("0x%08x", unwindInfos.back().encoding) << '\n'; } } while (false) | |||||||||
474 | << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << atom->name() << ", final encoding=" << llvm::format("0x%08x", unwindInfos.back().encoding) << '\n'; } } while (false); | |||||||||
475 | } | |||||||||
476 | ||||||||||
477 | return unwindInfos; | |||||||||
478 | } | |||||||||
479 | ||||||||||
480 | /// Remove unused EH frames. | |||||||||
481 | /// | |||||||||
482 | /// An EH frame is considered unused if there is a corresponding compact | |||||||||
483 | /// unwind atom that doesn't require the EH frame. | |||||||||
484 | void pruneUnusedEHFrames( | |||||||||
485 | SimpleFile &mergedFile, | |||||||||
486 | const std::vector<CompactUnwindEntry> &unwindInfos, | |||||||||
487 | const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, | |||||||||
488 | const std::map<const Atom *, const Atom *> &dwarfFrames) { | |||||||||
489 | ||||||||||
490 | // Worklist of all 'used' FDEs. | |||||||||
491 | std::vector<const DefinedAtom *> usedDwarfWorklist; | |||||||||
492 | ||||||||||
493 | // We have to check two conditions when building the worklist: | |||||||||
494 | // (1) EH frames used by compact unwind entries. | |||||||||
495 | for (auto &entry : unwindInfos) | |||||||||
496 | if (entry.ehFrame) | |||||||||
497 | usedDwarfWorklist.push_back(cast<DefinedAtom>(entry.ehFrame)); | |||||||||
498 | ||||||||||
499 | // (2) EH frames that reference functions with no corresponding compact | |||||||||
500 | // unwind info. | |||||||||
501 | for (auto &entry : dwarfFrames) | |||||||||
502 | if (!unwindLocs.count(entry.first)) | |||||||||
503 | usedDwarfWorklist.push_back(cast<DefinedAtom>(entry.second)); | |||||||||
504 | ||||||||||
505 | // Add all transitively referenced CFI atoms by processing the worklist. | |||||||||
506 | std::set<const Atom *> usedDwarfFrames; | |||||||||
507 | while (!usedDwarfWorklist.empty()) { | |||||||||
508 | const DefinedAtom *cfiAtom = usedDwarfWorklist.back(); | |||||||||
509 | usedDwarfWorklist.pop_back(); | |||||||||
510 | usedDwarfFrames.insert(cfiAtom); | |||||||||
511 | for (const auto *ref : *cfiAtom) { | |||||||||
512 | const DefinedAtom *cfiTarget = dyn_cast<DefinedAtom>(ref->target()); | |||||||||
513 | if (cfiTarget->contentType() == DefinedAtom::typeCFI) | |||||||||
514 | usedDwarfWorklist.push_back(cfiTarget); | |||||||||
515 | } | |||||||||
516 | } | |||||||||
517 | ||||||||||
518 | // Finally, delete all unreferenced CFI atoms. | |||||||||
519 | mergedFile.removeDefinedAtomsIf([&](const DefinedAtom *atom) { | |||||||||
520 | if ((atom->contentType() == DefinedAtom::typeCFI) && | |||||||||
521 | !usedDwarfFrames.count(atom)) | |||||||||
522 | return true; | |||||||||
523 | return false; | |||||||||
524 | }); | |||||||||
525 | } | |||||||||
526 | ||||||||||
527 | CompactUnwindEntry finalizeUnwindInfoEntryForAtom( | |||||||||
528 | const DefinedAtom *function, | |||||||||
529 | const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, | |||||||||
530 | const std::vector<const Atom *> &personalities, | |||||||||
531 | const std::map<const Atom *, const Atom *> &dwarfFrames) { | |||||||||
532 | auto unwindLoc = unwindLocs.find(function); | |||||||||
533 | ||||||||||
534 | CompactUnwindEntry entry; | |||||||||
535 | if (unwindLoc == unwindLocs.end()) { | |||||||||
536 | // Default entry has correct encoding (0 => no unwind), but we need to | |||||||||
537 | // synthesise the function. | |||||||||
538 | entry.rangeStart = function; | |||||||||
539 | entry.rangeLength = function->size(); | |||||||||
540 | } else | |||||||||
541 | entry = unwindLoc->second; | |||||||||
542 | ||||||||||
543 | ||||||||||
544 | // If there's no __compact_unwind entry, or it explicitly says to use | |||||||||
545 | // __eh_frame, we need to try and fill in the correct DWARF atom. | |||||||||
546 | if (entry.encoding == _archHandler.dwarfCompactUnwindType() || | |||||||||
547 | entry.encoding == 0) { | |||||||||
548 | auto dwarfFrame = dwarfFrames.find(function); | |||||||||
549 | if (dwarfFrame != dwarfFrames.end()) { | |||||||||
550 | entry.encoding = _archHandler.dwarfCompactUnwindType(); | |||||||||
551 | entry.ehFrame = dwarfFrame->second; | |||||||||
552 | } | |||||||||
553 | } | |||||||||
554 | ||||||||||
555 | auto personality = std::find(personalities.begin(), personalities.end(), | |||||||||
556 | entry.personalityFunction); | |||||||||
557 | uint32_t personalityIdx = personality == personalities.end() | |||||||||
558 | ? 0 | |||||||||
559 | : personality - personalities.begin() + 1; | |||||||||
560 | ||||||||||
561 | // FIXME: We should also use DWARF when there isn't enough room for the | |||||||||
562 | // personality function in the compact encoding. | |||||||||
563 | assert(personalityIdx < 4 && "too many personality functions")((personalityIdx < 4 && "too many personality functions" ) ? static_cast<void> (0) : __assert_fail ("personalityIdx < 4 && \"too many personality functions\"" , "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 563, __PRETTY_FUNCTION__)); | |||||||||
564 | ||||||||||
565 | entry.encoding |= personalityIdx << 28; | |||||||||
566 | ||||||||||
567 | if (entry.lsdaLocation) | |||||||||
568 | entry.encoding |= 1U << 30; | |||||||||
569 | ||||||||||
570 | return entry; | |||||||||
571 | } | |||||||||
572 | ||||||||||
573 | const MachOLinkingContext &_ctx; | |||||||||
574 | mach_o::ArchHandler &_archHandler; | |||||||||
575 | MachOFile &_file; | |||||||||
576 | bool _isBig; | |||||||||
577 | }; | |||||||||
578 | ||||||||||
579 | void addCompactUnwindPass(PassManager &pm, const MachOLinkingContext &ctx) { | |||||||||
580 | assert(ctx.needsCompactUnwindPass())((ctx.needsCompactUnwindPass()) ? static_cast<void> (0) : __assert_fail ("ctx.needsCompactUnwindPass()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 580, __PRETTY_FUNCTION__)); | |||||||||
581 | pm.add(llvm::make_unique<CompactUnwindPass>(ctx)); | |||||||||
582 | } | |||||||||
583 | ||||||||||
584 | } // end namesapce mach_o | |||||||||
585 | } // end namesapce lld |
1 | // Pair implementation -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2016 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,1997 |
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_pair.h |
52 | * This is an internal header file, included by other library headers. |
53 | * Do not attempt to use it directly. @headername{utility} |
54 | */ |
55 | |
56 | #ifndef _STL_PAIR_H1 |
57 | #define _STL_PAIR_H1 1 |
58 | |
59 | #include <bits/move.h> // for std::move / std::forward, and std::swap |
60 | |
61 | #if __cplusplus201103L >= 201103L |
62 | #include <type_traits> // for std::__decay_and_strip too |
63 | #endif |
64 | |
65 | namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default"))) |
66 | { |
67 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
68 | |
69 | /** |
70 | * @addtogroup utilities |
71 | * @{ |
72 | */ |
73 | |
74 | #if __cplusplus201103L >= 201103L |
75 | /// piecewise_construct_t |
76 | struct piecewise_construct_t { explicit piecewise_construct_t() = default; }; |
77 | |
78 | /// piecewise_construct |
79 | constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); |
80 | |
81 | // Forward declarations. |
82 | template<typename...> |
83 | class tuple; |
84 | |
85 | template<std::size_t...> |
86 | struct _Index_tuple; |
87 | |
88 | // Concept utility functions, reused in conditionally-explicit |
89 | // constructors. |
90 | // See PR 70437, don't look at is_constructible or |
91 | // is_convertible if the types are the same to |
92 | // avoid querying those properties for incomplete types. |
93 | template <bool, typename _T1, typename _T2> |
94 | struct _PCC |
95 | { |
96 | template <typename _U1, typename _U2> |
97 | static constexpr bool _ConstructiblePair() |
98 | { |
99 | return __and_<is_constructible<_T1, const _U1&>, |
100 | is_constructible<_T2, const _U2&>>::value; |
101 | } |
102 | |
103 | template <typename _U1, typename _U2> |
104 | static constexpr bool _ImplicitlyConvertiblePair() |
105 | { |
106 | return __and_<is_convertible<const _U1&, _T1>, |
107 | is_convertible<const _U2&, _T2>>::value; |
108 | } |
109 | |
110 | template <typename _U1, typename _U2> |
111 | static constexpr bool _MoveConstructiblePair() |
112 | { |
113 | return __and_<is_constructible<_T1, _U1&&>, |
114 | is_constructible<_T2, _U2&&>>::value; |
115 | } |
116 | |
117 | template <typename _U1, typename _U2> |
118 | static constexpr bool _ImplicitlyMoveConvertiblePair() |
119 | { |
120 | return __and_<is_convertible<_U1&&, _T1>, |
121 | is_convertible<_U2&&, _T2>>::value; |
122 | } |
123 | |
124 | template <bool __implicit, typename _U1, typename _U2> |
125 | static constexpr bool _CopyMovePair() |
126 | { |
127 | using __do_converts = __and_<is_convertible<const _U1&, _T1>, |
128 | is_convertible<_U2&&, _T2>>; |
129 | using __converts = typename conditional<__implicit, |
130 | __do_converts, |
131 | __not_<__do_converts>>::type; |
132 | return __and_<is_constructible<_T1, const _U1&>, |
133 | is_constructible<_T2, _U2&&>, |
134 | __converts |
135 | >::value; |
136 | } |
137 | |
138 | template <bool __implicit, typename _U1, typename _U2> |
139 | static constexpr bool _MoveCopyPair() |
140 | { |
141 | using __do_converts = __and_<is_convertible<_U1&&, _T1>, |
142 | is_convertible<const _U2&, _T2>>; |
143 | using __converts = typename conditional<__implicit, |
144 | __do_converts, |
145 | __not_<__do_converts>>::type; |
146 | return __and_<is_constructible<_T1, _U1&&>, |
147 | is_constructible<_T2, const _U2&&>, |
148 | __converts |
149 | >::value; |
150 | } |
151 | }; |
152 | |
153 | template <typename _T1, typename _T2> |
154 | struct _PCC<false, _T1, _T2> |
155 | { |
156 | template <typename _U1, typename _U2> |
157 | static constexpr bool _ConstructiblePair() |
158 | { |
159 | return false; |
160 | } |
161 | |
162 | template <typename _U1, typename _U2> |
163 | static constexpr bool _ImplicitlyConvertiblePair() |
164 | { |
165 | return false; |
166 | } |
167 | |
168 | template <typename _U1, typename _U2> |
169 | static constexpr bool _MoveConstructiblePair() |
170 | { |
171 | return false; |
172 | } |
173 | |
174 | template <typename _U1, typename _U2> |
175 | static constexpr bool _ImplicitlyMoveConvertiblePair() |
176 | { |
177 | return false; |
178 | } |
179 | }; |
180 | |
181 | struct __wrap_nonesuch : std::__nonesuch { |
182 | explicit __wrap_nonesuch(const __nonesuch&) = delete; |
183 | }; |
184 | |
185 | #endif |
186 | |
187 | /** |
188 | * @brief Struct holding two objects of arbitrary type. |
189 | * |
190 | * @tparam _T1 Type of first object. |
191 | * @tparam _T2 Type of second object. |
192 | */ |
193 | template<typename _T1, typename _T2> |
194 | struct pair |
195 | { |
196 | typedef _T1 first_type; /// @c first_type is the first bound type |
197 | typedef _T2 second_type; /// @c second_type is the second bound type |
198 | |
199 | _T1 first; /// @c first is a copy of the first object |
200 | _T2 second; /// @c second is a copy of the second object |
201 | |
202 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
203 | // 265. std::pair::pair() effects overly restrictive |
204 | /** The default constructor creates @c first and @c second using their |
205 | * respective default constructors. */ |
206 | #if __cplusplus201103L >= 201103L |
207 | template <typename _U1 = _T1, |
208 | typename _U2 = _T2, |
209 | typename enable_if<__and_< |
210 | __is_implicitly_default_constructible<_U1>, |
211 | __is_implicitly_default_constructible<_U2>> |
212 | ::value, bool>::type = true> |
213 | #endif |
214 | _GLIBCXX_CONSTEXPRconstexpr pair() |
215 | : first(), second() { } |
216 | |
217 | #if __cplusplus201103L >= 201103L |
218 | template <typename _U1 = _T1, |
219 | typename _U2 = _T2, |
220 | typename enable_if<__and_< |
221 | is_default_constructible<_U1>, |
222 | is_default_constructible<_U2>, |
223 | __not_< |
224 | __and_<__is_implicitly_default_constructible<_U1>, |
225 | __is_implicitly_default_constructible<_U2>>>> |
226 | ::value, bool>::type = false> |
227 | explicit constexpr pair() |
228 | : first(), second() { } |
229 | #endif |
230 | |
231 | /** Two objects may be passed to a @c pair constructor to be copied. */ |
232 | #if __cplusplus201103L < 201103L |
233 | pair(const _T1& __a, const _T2& __b) |
234 | : first(__a), second(__b) { } |
235 | #else |
236 | // Shortcut for constraining the templates that don't take pairs. |
237 | using _PCCP = _PCC<true, _T1, _T2>; |
238 | |
239 | template<typename _U1 = _T1, typename _U2=_T2, typename |
240 | enable_if<_PCCP::template |
241 | _ConstructiblePair<_U1, _U2>() |
242 | && _PCCP::template |
243 | _ImplicitlyConvertiblePair<_U1, _U2>(), |
244 | bool>::type=true> |
245 | constexpr pair(const _T1& __a, const _T2& __b) |
246 | : first(__a), second(__b) { } |
247 | |
248 | template<typename _U1 = _T1, typename _U2=_T2, typename |
249 | enable_if<_PCCP::template |
250 | _ConstructiblePair<_U1, _U2>() |
251 | && !_PCCP::template |
252 | _ImplicitlyConvertiblePair<_U1, _U2>(), |
253 | bool>::type=false> |
254 | explicit constexpr pair(const _T1& __a, const _T2& __b) |
255 | : first(__a), second(__b) { } |
256 | #endif |
257 | |
258 | /** There is also a templated copy ctor for the @c pair class itself. */ |
259 | #if __cplusplus201103L < 201103L |
260 | template<typename _U1, typename _U2> |
261 | pair(const pair<_U1, _U2>& __p) |
262 | : first(__p.first), second(__p.second) { } |
263 | #else |
264 | // Shortcut for constraining the templates that take pairs. |
265 | template <typename _U1, typename _U2> |
266 | using _PCCFP = _PCC<!is_same<_T1, _U1>::value |
267 | || !is_same<_T2, _U2>::value, |
268 | _T1, _T2>; |
269 | |
270 | template<typename _U1, typename _U2, typename |
271 | enable_if<_PCCFP<_U1, _U2>::template |
272 | _ConstructiblePair<_U1, _U2>() |
273 | && _PCCFP<_U1, _U2>::template |
274 | _ImplicitlyConvertiblePair<_U1, _U2>(), |
275 | bool>::type=true> |
276 | constexpr pair(const pair<_U1, _U2>& __p) |
277 | : first(__p.first), second(__p.second) { } |
278 | |
279 | template<typename _U1, typename _U2, typename |
280 | enable_if<_PCCFP<_U1, _U2>::template |
281 | _ConstructiblePair<_U1, _U2>() |
282 | && !_PCCFP<_U1, _U2>::template |
283 | _ImplicitlyConvertiblePair<_U1, _U2>(), |
284 | bool>::type=false> |
285 | explicit constexpr pair(const pair<_U1, _U2>& __p) |
286 | : first(__p.first), second(__p.second) { } |
287 | |
288 | constexpr pair(const pair&) = default; |
289 | constexpr pair(pair&&) = default; |
290 | |
291 | // DR 811. |
292 | template<typename _U1, typename |
293 | enable_if<_PCCP::template |
294 | _MoveCopyPair<true, _U1, _T2>(), |
295 | bool>::type=true> |
296 | constexpr pair(_U1&& __x, const _T2& __y) |
297 | : first(std::forward<_U1>(__x)), second(__y) { } |
298 | |
299 | template<typename _U1, typename |
300 | enable_if<_PCCP::template |
301 | _MoveCopyPair<false, _U1, _T2>(), |
302 | bool>::type=false> |
303 | explicit constexpr pair(_U1&& __x, const _T2& __y) |
304 | : first(std::forward<_U1>(__x)), second(__y) { } |
305 | |
306 | template<typename _U2, typename |
307 | enable_if<_PCCP::template |
308 | _CopyMovePair<true, _T1, _U2>(), |
309 | bool>::type=true> |
310 | constexpr pair(const _T1& __x, _U2&& __y) |
311 | : first(__x), second(std::forward<_U2>(__y)) { } |
312 | |
313 | template<typename _U2, typename |
314 | enable_if<_PCCP::template |
315 | _CopyMovePair<false, _T1, _U2>(), |
316 | bool>::type=false> |
317 | explicit pair(const _T1& __x, _U2&& __y) |
318 | : first(__x), second(std::forward<_U2>(__y)) { } |
319 | |
320 | template<typename _U1, typename _U2, typename |
321 | enable_if<_PCCP::template |
322 | _MoveConstructiblePair<_U1, _U2>() |
323 | && _PCCP::template |
324 | _ImplicitlyMoveConvertiblePair<_U1, _U2>(), |
325 | bool>::type=true> |
326 | constexpr pair(_U1&& __x, _U2&& __y) |
327 | : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { } |
328 | |
329 | template<typename _U1, typename _U2, typename |
330 | enable_if<_PCCP::template |
331 | _MoveConstructiblePair<_U1, _U2>() |
332 | && !_PCCP::template |
333 | _ImplicitlyMoveConvertiblePair<_U1, _U2>(), |
334 | bool>::type=false> |
335 | explicit constexpr pair(_U1&& __x, _U2&& __y) |
336 | : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { } |
337 | |
338 | |
339 | template<typename _U1, typename _U2, typename |
340 | enable_if<_PCCFP<_U1, _U2>::template |
341 | _MoveConstructiblePair<_U1, _U2>() |
342 | && _PCCFP<_U1, _U2>::template |
343 | _ImplicitlyMoveConvertiblePair<_U1, _U2>(), |
344 | bool>::type=true> |
345 | constexpr pair(pair<_U1, _U2>&& __p) |
346 | : first(std::forward<_U1>(__p.first)), |
347 | second(std::forward<_U2>(__p.second)) { } |
348 | |
349 | template<typename _U1, typename _U2, typename |
350 | enable_if<_PCCFP<_U1, _U2>::template |
351 | _MoveConstructiblePair<_U1, _U2>() |
352 | && !_PCCFP<_U1, _U2>::template |
353 | _ImplicitlyMoveConvertiblePair<_U1, _U2>(), |
354 | bool>::type=false> |
355 | explicit constexpr pair(pair<_U1, _U2>&& __p) |
356 | : first(std::forward<_U1>(__p.first)), |
357 | second(std::forward<_U2>(__p.second)) { } |
358 | |
359 | template<typename... _Args1, typename... _Args2> |
360 | pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>); |
361 | |
362 | pair& |
363 | operator=(typename conditional< |
364 | __and_<is_copy_assignable<_T1>, |
365 | is_copy_assignable<_T2>>::value, |
366 | const pair&, const __wrap_nonesuch&>::type __p) |
367 | { |
368 | first = __p.first; |
369 | second = __p.second; |
370 | return *this; |
371 | } |
372 | |
373 | pair& |
374 | operator=(typename conditional< |
375 | __not_<__and_<is_copy_assignable<_T1>, |
376 | is_copy_assignable<_T2>>>::value, |
377 | const pair&, const __wrap_nonesuch&>::type __p) = delete; |
378 | |
379 | pair& |
380 | operator=(typename conditional< |
381 | __and_<is_move_assignable<_T1>, |
382 | is_move_assignable<_T2>>::value, |
383 | pair&&, __wrap_nonesuch&&>::type __p) |
384 | noexcept(__and_<is_nothrow_move_assignable<_T1>, |
385 | is_nothrow_move_assignable<_T2>>::value) |
386 | { |
387 | first = std::forward<first_type>(__p.first); |
388 | second = std::forward<second_type>(__p.second); |
389 | return *this; |
390 | } |
391 | |
392 | template<typename _U1, typename _U2> |
393 | typename enable_if<__and_<is_assignable<_T1&, const _U1&>, |
394 | is_assignable<_T2&, const _U2&>>::value, |
395 | pair&>::type |
396 | operator=(const pair<_U1, _U2>& __p) |
397 | { |
398 | first = __p.first; |
399 | second = __p.second; |
400 | return *this; |
401 | } |
402 | |
403 | template<typename _U1, typename _U2> |
404 | typename enable_if<__and_<is_assignable<_T1&, _U1&&>, |
405 | is_assignable<_T2&, _U2&&>>::value, |
406 | pair&>::type |
407 | operator=(pair<_U1, _U2>&& __p) |
408 | { |
409 | first = std::forward<_U1>(__p.first); |
410 | second = std::forward<_U2>(__p.second); |
411 | return *this; |
412 | } |
413 | |
414 | void |
415 | swap(pair& __p) |
416 | noexcept(__is_nothrow_swappable<_T1>::value |
417 | && __is_nothrow_swappable<_T2>::value) |
418 | { |
419 | using std::swap; |
420 | swap(first, __p.first); |
421 | swap(second, __p.second); |
422 | } |
423 | |
424 | private: |
425 | template<typename... _Args1, std::size_t... _Indexes1, |
426 | typename... _Args2, std::size_t... _Indexes2> |
427 | pair(tuple<_Args1...>&, tuple<_Args2...>&, |
428 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); |
429 | #endif |
430 | }; |
431 | |
432 | /// Two pairs of the same type are equal iff their members are equal. |
433 | template<typename _T1, typename _T2> |
434 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
435 | operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
436 | { return __x.first == __y.first && __x.second == __y.second; } |
437 | |
438 | /// <http://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html> |
439 | template<typename _T1, typename _T2> |
440 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
441 | operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
442 | { return __x.first < __y.first |
443 | || (!(__y.first < __x.first) && __x.second < __y.second); } |
444 | |
445 | /// Uses @c operator== to find the result. |
446 | template<typename _T1, typename _T2> |
447 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
448 | operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
449 | { return !(__x == __y); } |
450 | |
451 | /// Uses @c operator< to find the result. |
452 | template<typename _T1, typename _T2> |
453 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
454 | operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
455 | { return __y < __x; } |
456 | |
457 | /// Uses @c operator< to find the result. |
458 | template<typename _T1, typename _T2> |
459 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
460 | operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
461 | { return !(__y < __x); } |
462 | |
463 | /// Uses @c operator< to find the result. |
464 | template<typename _T1, typename _T2> |
465 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
466 | operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
467 | { return !(__x < __y); } |
468 | |
469 | #if __cplusplus201103L >= 201103L |
470 | /// See std::pair::swap(). |
471 | // Note: no std::swap overloads in C++03 mode, this has performance |
472 | // implications, see, eg, libstdc++/38466. |
473 | template<typename _T1, typename _T2> |
474 | inline void |
475 | swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y) |
476 | noexcept(noexcept(__x.swap(__y))) |
477 | { __x.swap(__y); } |
478 | #endif |
479 | |
480 | /** |
481 | * @brief A convenience wrapper for creating a pair from two objects. |
482 | * @param __x The first object. |
483 | * @param __y The second object. |
484 | * @return A newly-constructed pair<> object of the appropriate type. |
485 | * |
486 | * The standard requires that the objects be passed by reference-to-const, |
487 | * but LWG issue #181 says they should be passed by const value. We follow |
488 | * the LWG by default. |
489 | */ |
490 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
491 | // 181. make_pair() unintended behavior |
492 | #if __cplusplus201103L >= 201103L |
493 | // NB: DR 706. |
494 | template<typename _T1, typename _T2> |
495 | constexpr pair<typename __decay_and_strip<_T1>::__type, |
496 | typename __decay_and_strip<_T2>::__type> |
497 | make_pair(_T1&& __x, _T2&& __y) |
498 | { |
499 | typedef typename __decay_and_strip<_T1>::__type __ds_type1; |
500 | typedef typename __decay_and_strip<_T2>::__type __ds_type2; |
501 | typedef pair<__ds_type1, __ds_type2> __pair_type; |
502 | return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y)); |
503 | } |
504 | #else |
505 | template<typename _T1, typename _T2> |
506 | inline pair<_T1, _T2> |
507 | make_pair(_T1 __x, _T2 __y) |
508 | { return pair<_T1, _T2>(__x, __y); } |
509 | #endif |
510 | |
511 | /// @} |
512 | |
513 | _GLIBCXX_END_NAMESPACE_VERSION |
514 | } // namespace std |
515 | |
516 | #endif /* _STL_PAIR_H */ |