Bug Summary

File:include/llvm/Support/Error.h
Warning:line 201, column 5
Potential leak of memory pointed to by 'Payload._M_t._M_head_impl'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name MetadataLoader.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -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-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/lib/Bitcode/Reader -I /build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/lib/Bitcode/Reader -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-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp

1//===- MetadataLoader.cpp - Internal BitcodeReader implementation ---------===//
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#include "MetadataLoader.h"
11#include "ValueList.h"
12
13#include "llvm/ADT/APFloat.h"
14#include "llvm/ADT/APInt.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/None.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallString.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/ADT/Twine.h"
25#include "llvm/Bitcode/BitcodeReader.h"
26#include "llvm/Bitcode/BitstreamReader.h"
27#include "llvm/Bitcode/LLVMBitCodes.h"
28#include "llvm/IR/Argument.h"
29#include "llvm/IR/Attributes.h"
30#include "llvm/IR/AutoUpgrade.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/CallingConv.h"
33#include "llvm/IR/Comdat.h"
34#include "llvm/IR/Constant.h"
35#include "llvm/IR/Constants.h"
36#include "llvm/IR/DebugInfo.h"
37#include "llvm/IR/DebugInfoMetadata.h"
38#include "llvm/IR/DebugLoc.h"
39#include "llvm/IR/DerivedTypes.h"
40#include "llvm/IR/DiagnosticPrinter.h"
41#include "llvm/IR/Function.h"
42#include "llvm/IR/GVMaterializer.h"
43#include "llvm/IR/GlobalAlias.h"
44#include "llvm/IR/GlobalIFunc.h"
45#include "llvm/IR/GlobalIndirectSymbol.h"
46#include "llvm/IR/GlobalObject.h"
47#include "llvm/IR/GlobalValue.h"
48#include "llvm/IR/GlobalVariable.h"
49#include "llvm/IR/InlineAsm.h"
50#include "llvm/IR/InstrTypes.h"
51#include "llvm/IR/Instruction.h"
52#include "llvm/IR/Instructions.h"
53#include "llvm/IR/IntrinsicInst.h"
54#include "llvm/IR/Intrinsics.h"
55#include "llvm/IR/LLVMContext.h"
56#include "llvm/IR/Module.h"
57#include "llvm/IR/ModuleSummaryIndex.h"
58#include "llvm/IR/OperandTraits.h"
59#include "llvm/IR/TrackingMDRef.h"
60#include "llvm/IR/Type.h"
61#include "llvm/IR/ValueHandle.h"
62#include "llvm/Support/AtomicOrdering.h"
63#include "llvm/Support/Casting.h"
64#include "llvm/Support/CommandLine.h"
65#include "llvm/Support/Compiler.h"
66#include "llvm/Support/Debug.h"
67#include "llvm/Support/Error.h"
68#include "llvm/Support/ErrorHandling.h"
69#include "llvm/Support/ManagedStatic.h"
70#include "llvm/Support/MemoryBuffer.h"
71#include "llvm/Support/raw_ostream.h"
72#include <algorithm>
73#include <cassert>
74#include <cstddef>
75#include <cstdint>
76#include <deque>
77#include <limits>
78#include <map>
79#include <memory>
80#include <string>
81#include <system_error>
82#include <tuple>
83#include <utility>
84#include <vector>
85
86using namespace llvm;
87
88#define DEBUG_TYPE"bitcode-reader" "bitcode-reader"
89
90STATISTIC(NumMDStringLoaded, "Number of MDStrings loaded")static llvm::Statistic NumMDStringLoaded = {"bitcode-reader",
"NumMDStringLoaded", "Number of MDStrings loaded", {0}, {false
}}
;
91STATISTIC(NumMDNodeTemporary, "Number of MDNode::Temporary created")static llvm::Statistic NumMDNodeTemporary = {"bitcode-reader"
, "NumMDNodeTemporary", "Number of MDNode::Temporary created"
, {0}, {false}}
;
92STATISTIC(NumMDRecordLoaded, "Number of Metadata records loaded")static llvm::Statistic NumMDRecordLoaded = {"bitcode-reader",
"NumMDRecordLoaded", "Number of Metadata records loaded", {0
}, {false}}
;
93
94/// Flag whether we need to import full type definitions for ThinLTO.
95/// Currently needed for Darwin and LLDB.
96static cl::opt<bool> ImportFullTypeDefinitions(
97 "import-full-type-definitions", cl::init(false), cl::Hidden,
98 cl::desc("Import full type definitions for ThinLTO."));
99
100static cl::opt<bool> DisableLazyLoading(
101 "disable-ondemand-mds-loading", cl::init(false), cl::Hidden,
102 cl::desc("Force disable the lazy-loading on-demand of metadata when "
103 "loading bitcode for importing."));
104
105namespace {
106
107static int64_t unrotateSign(uint64_t U) { return U & 1 ? ~(U >> 1) : U >> 1; }
108
109class BitcodeReaderMetadataList {
110 /// Array of metadata references.
111 ///
112 /// Don't use std::vector here. Some versions of libc++ copy (instead of
113 /// move) on resize, and TrackingMDRef is very expensive to copy.
114 SmallVector<TrackingMDRef, 1> MetadataPtrs;
115
116 /// The set of indices in MetadataPtrs above of forward references that were
117 /// generated.
118 SmallDenseSet<unsigned, 1> ForwardReference;
119
120 /// The set of indices in MetadataPtrs above of Metadata that need to be
121 /// resolved.
122 SmallDenseSet<unsigned, 1> UnresolvedNodes;
123
124 /// Structures for resolving old type refs.
125 struct {
126 SmallDenseMap<MDString *, TempMDTuple, 1> Unknown;
127 SmallDenseMap<MDString *, DICompositeType *, 1> Final;
128 SmallDenseMap<MDString *, DICompositeType *, 1> FwdDecls;
129 SmallVector<std::pair<TrackingMDRef, TempMDTuple>, 1> Arrays;
130 } OldTypeRefs;
131
132 LLVMContext &Context;
133
134public:
135 BitcodeReaderMetadataList(LLVMContext &C) : Context(C) {}
136
137 // vector compatibility methods
138 unsigned size() const { return MetadataPtrs.size(); }
139 void resize(unsigned N) { MetadataPtrs.resize(N); }
140 void push_back(Metadata *MD) { MetadataPtrs.emplace_back(MD); }
141 void clear() { MetadataPtrs.clear(); }
142 Metadata *back() const { return MetadataPtrs.back(); }
143 void pop_back() { MetadataPtrs.pop_back(); }
144 bool empty() const { return MetadataPtrs.empty(); }
145
146 Metadata *operator[](unsigned i) const {
147 assert(i < MetadataPtrs.size())((i < MetadataPtrs.size()) ? static_cast<void> (0) :
__assert_fail ("i < MetadataPtrs.size()", "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 147, __PRETTY_FUNCTION__))
;
148 return MetadataPtrs[i];
149 }
150
151 Metadata *lookup(unsigned I) const {
152 if (I < MetadataPtrs.size())
153 return MetadataPtrs[I];
154 return nullptr;
155 }
156
157 void shrinkTo(unsigned N) {
158 assert(N <= size() && "Invalid shrinkTo request!")((N <= size() && "Invalid shrinkTo request!") ? static_cast
<void> (0) : __assert_fail ("N <= size() && \"Invalid shrinkTo request!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 158, __PRETTY_FUNCTION__))
;
159 assert(ForwardReference.empty() && "Unexpected forward refs")((ForwardReference.empty() && "Unexpected forward refs"
) ? static_cast<void> (0) : __assert_fail ("ForwardReference.empty() && \"Unexpected forward refs\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 159, __PRETTY_FUNCTION__))
;
160 assert(UnresolvedNodes.empty() && "Unexpected unresolved node")((UnresolvedNodes.empty() && "Unexpected unresolved node"
) ? static_cast<void> (0) : __assert_fail ("UnresolvedNodes.empty() && \"Unexpected unresolved node\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 160, __PRETTY_FUNCTION__))
;
161 MetadataPtrs.resize(N);
162 }
163
164 /// Return the given metadata, creating a replaceable forward reference if
165 /// necessary.
166 Metadata *getMetadataFwdRef(unsigned Idx);
167
168 /// Return the given metadata only if it is fully resolved.
169 ///
170 /// Gives the same result as \a lookup(), unless \a MDNode::isResolved()
171 /// would give \c false.
172 Metadata *getMetadataIfResolved(unsigned Idx);
173
174 MDNode *getMDNodeFwdRefOrNull(unsigned Idx);
175 void assignValue(Metadata *MD, unsigned Idx);
176 void tryToResolveCycles();
177 bool hasFwdRefs() const { return !ForwardReference.empty(); }
178 int getNextFwdRef() {
179 assert(hasFwdRefs())((hasFwdRefs()) ? static_cast<void> (0) : __assert_fail
("hasFwdRefs()", "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 179, __PRETTY_FUNCTION__))
;
180 return *ForwardReference.begin();
181 }
182
183 /// Upgrade a type that had an MDString reference.
184 void addTypeRef(MDString &UUID, DICompositeType &CT);
185
186 /// Upgrade a type that had an MDString reference.
187 Metadata *upgradeTypeRef(Metadata *MaybeUUID);
188
189 /// Upgrade a type ref array that may have MDString references.
190 Metadata *upgradeTypeRefArray(Metadata *MaybeTuple);
191
192private:
193 Metadata *resolveTypeRefArray(Metadata *MaybeTuple);
194};
195
196void BitcodeReaderMetadataList::assignValue(Metadata *MD, unsigned Idx) {
197 if (auto *MDN = dyn_cast<MDNode>(MD))
198 if (!MDN->isResolved())
199 UnresolvedNodes.insert(Idx);
200
201 if (Idx == size()) {
202 push_back(MD);
203 return;
204 }
205
206 if (Idx >= size())
207 resize(Idx + 1);
208
209 TrackingMDRef &OldMD = MetadataPtrs[Idx];
210 if (!OldMD) {
211 OldMD.reset(MD);
212 return;
213 }
214
215 // If there was a forward reference to this value, replace it.
216 TempMDTuple PrevMD(cast<MDTuple>(OldMD.get()));
217 PrevMD->replaceAllUsesWith(MD);
218 ForwardReference.erase(Idx);
219}
220
221Metadata *BitcodeReaderMetadataList::getMetadataFwdRef(unsigned Idx) {
222 if (Idx >= size())
223 resize(Idx + 1);
224
225 if (Metadata *MD = MetadataPtrs[Idx])
226 return MD;
227
228 // Track forward refs to be resolved later.
229 ForwardReference.insert(Idx);
230
231 // Create and return a placeholder, which will later be RAUW'd.
232 ++NumMDNodeTemporary;
233 Metadata *MD = MDNode::getTemporary(Context, None).release();
234 MetadataPtrs[Idx].reset(MD);
235 return MD;
236}
237
238Metadata *BitcodeReaderMetadataList::getMetadataIfResolved(unsigned Idx) {
239 Metadata *MD = lookup(Idx);
240 if (auto *N = dyn_cast_or_null<MDNode>(MD))
241 if (!N->isResolved())
242 return nullptr;
243 return MD;
244}
245
246MDNode *BitcodeReaderMetadataList::getMDNodeFwdRefOrNull(unsigned Idx) {
247 return dyn_cast_or_null<MDNode>(getMetadataFwdRef(Idx));
248}
249
250void BitcodeReaderMetadataList::tryToResolveCycles() {
251 if (!ForwardReference.empty())
252 // Still forward references... can't resolve cycles.
253 return;
254
255 // Give up on finding a full definition for any forward decls that remain.
256 for (const auto &Ref : OldTypeRefs.FwdDecls)
257 OldTypeRefs.Final.insert(Ref);
258 OldTypeRefs.FwdDecls.clear();
259
260 // Upgrade from old type ref arrays. In strange cases, this could add to
261 // OldTypeRefs.Unknown.
262 for (const auto &Array : OldTypeRefs.Arrays)
263 Array.second->replaceAllUsesWith(resolveTypeRefArray(Array.first.get()));
264 OldTypeRefs.Arrays.clear();
265
266 // Replace old string-based type refs with the resolved node, if possible.
267 // If we haven't seen the node, leave it to the verifier to complain about
268 // the invalid string reference.
269 for (const auto &Ref : OldTypeRefs.Unknown) {
270 if (DICompositeType *CT = OldTypeRefs.Final.lookup(Ref.first))
271 Ref.second->replaceAllUsesWith(CT);
272 else
273 Ref.second->replaceAllUsesWith(Ref.first);
274 }
275 OldTypeRefs.Unknown.clear();
276
277 if (UnresolvedNodes.empty())
278 // Nothing to do.
279 return;
280
281 // Resolve any cycles.
282 for (unsigned I : UnresolvedNodes) {
283 auto &MD = MetadataPtrs[I];
284 auto *N = dyn_cast_or_null<MDNode>(MD);
285 if (!N)
286 continue;
287
288 assert(!N->isTemporary() && "Unexpected forward reference")((!N->isTemporary() && "Unexpected forward reference"
) ? static_cast<void> (0) : __assert_fail ("!N->isTemporary() && \"Unexpected forward reference\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 288, __PRETTY_FUNCTION__))
;
289 N->resolveCycles();
290 }
291
292 // Make sure we return early again until there's another unresolved ref.
293 UnresolvedNodes.clear();
294}
295
296void BitcodeReaderMetadataList::addTypeRef(MDString &UUID,
297 DICompositeType &CT) {
298 assert(CT.getRawIdentifier() == &UUID && "Mismatched UUID")((CT.getRawIdentifier() == &UUID && "Mismatched UUID"
) ? static_cast<void> (0) : __assert_fail ("CT.getRawIdentifier() == &UUID && \"Mismatched UUID\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 298, __PRETTY_FUNCTION__))
;
299 if (CT.isForwardDecl())
300 OldTypeRefs.FwdDecls.insert(std::make_pair(&UUID, &CT));
301 else
302 OldTypeRefs.Final.insert(std::make_pair(&UUID, &CT));
303}
304
305Metadata *BitcodeReaderMetadataList::upgradeTypeRef(Metadata *MaybeUUID) {
306 auto *UUID = dyn_cast_or_null<MDString>(MaybeUUID);
307 if (LLVM_LIKELY(!UUID)__builtin_expect((bool)(!UUID), true))
308 return MaybeUUID;
309
310 if (auto *CT = OldTypeRefs.Final.lookup(UUID))
311 return CT;
312
313 auto &Ref = OldTypeRefs.Unknown[UUID];
314 if (!Ref)
315 Ref = MDNode::getTemporary(Context, None);
316 return Ref.get();
317}
318
319Metadata *BitcodeReaderMetadataList::upgradeTypeRefArray(Metadata *MaybeTuple) {
320 auto *Tuple = dyn_cast_or_null<MDTuple>(MaybeTuple);
321 if (!Tuple || Tuple->isDistinct())
322 return MaybeTuple;
323
324 // Look through the array immediately if possible.
325 if (!Tuple->isTemporary())
326 return resolveTypeRefArray(Tuple);
327
328 // Create and return a placeholder to use for now. Eventually
329 // resolveTypeRefArrays() will be resolve this forward reference.
330 OldTypeRefs.Arrays.emplace_back(
331 std::piecewise_construct, std::forward_as_tuple(Tuple),
332 std::forward_as_tuple(MDTuple::getTemporary(Context, None)));
333 return OldTypeRefs.Arrays.back().second.get();
334}
335
336Metadata *BitcodeReaderMetadataList::resolveTypeRefArray(Metadata *MaybeTuple) {
337 auto *Tuple = dyn_cast_or_null<MDTuple>(MaybeTuple);
338 if (!Tuple || Tuple->isDistinct())
339 return MaybeTuple;
340
341 // Look through the DITypeRefArray, upgrading each DITypeRef.
342 SmallVector<Metadata *, 32> Ops;
343 Ops.reserve(Tuple->getNumOperands());
344 for (Metadata *MD : Tuple->operands())
345 Ops.push_back(upgradeTypeRef(MD));
346
347 return MDTuple::get(Context, Ops);
348}
349
350namespace {
351
352class PlaceholderQueue {
353 // Placeholders would thrash around when moved, so store in a std::deque
354 // instead of some sort of vector.
355 std::deque<DistinctMDOperandPlaceholder> PHs;
356
357public:
358 ~PlaceholderQueue() {
359 assert(empty() && "PlaceholderQueue hasn't been flushed before being destroyed")((empty() && "PlaceholderQueue hasn't been flushed before being destroyed"
) ? static_cast<void> (0) : __assert_fail ("empty() && \"PlaceholderQueue hasn't been flushed before being destroyed\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 359, __PRETTY_FUNCTION__))
;
360 }
361 bool empty() { return PHs.empty(); }
362 DistinctMDOperandPlaceholder &getPlaceholderOp(unsigned ID);
363 void flush(BitcodeReaderMetadataList &MetadataList);
364
365 /// Return the list of temporaries nodes in the queue, these need to be
366 /// loaded before we can flush the queue.
367 void getTemporaries(BitcodeReaderMetadataList &MetadataList,
368 DenseSet<unsigned> &Temporaries) {
369 for (auto &PH : PHs) {
370 auto ID = PH.getID();
371 auto *MD = MetadataList.lookup(ID);
372 if (!MD) {
373 Temporaries.insert(ID);
374 continue;
375 }
376 auto *N = dyn_cast_or_null<MDNode>(MD);
377 if (N && N->isTemporary())
378 Temporaries.insert(ID);
379 }
380 }
381};
382
383} // end anonymous namespace
384
385DistinctMDOperandPlaceholder &PlaceholderQueue::getPlaceholderOp(unsigned ID) {
386 PHs.emplace_back(ID);
387 return PHs.back();
388}
389
390void PlaceholderQueue::flush(BitcodeReaderMetadataList &MetadataList) {
391 while (!PHs.empty()) {
392 auto *MD = MetadataList.lookup(PHs.front().getID());
393 assert(MD && "Flushing placeholder on unassigned MD")((MD && "Flushing placeholder on unassigned MD") ? static_cast
<void> (0) : __assert_fail ("MD && \"Flushing placeholder on unassigned MD\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 393, __PRETTY_FUNCTION__))
;
394#ifndef NDEBUG
395 if (auto *MDN = dyn_cast<MDNode>(MD))
396 assert(MDN->isResolved() &&((MDN->isResolved() && "Flushing Placeholder while cycles aren't resolved"
) ? static_cast<void> (0) : __assert_fail ("MDN->isResolved() && \"Flushing Placeholder while cycles aren't resolved\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 397, __PRETTY_FUNCTION__))
397 "Flushing Placeholder while cycles aren't resolved")((MDN->isResolved() && "Flushing Placeholder while cycles aren't resolved"
) ? static_cast<void> (0) : __assert_fail ("MDN->isResolved() && \"Flushing Placeholder while cycles aren't resolved\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 397, __PRETTY_FUNCTION__))
;
398#endif
399 PHs.front().replaceUseWith(MD);
400 PHs.pop_front();
401 }
402}
403
404} // anonynous namespace
405
406static Error error(const Twine &Message) {
407 return make_error<StringError>(
5
Calling 'make_error<llvm::StringError, const llvm::Twine &, std::error_code>'
408 Message, make_error_code(BitcodeError::CorruptedBitcode));
409}
410
411class MetadataLoader::MetadataLoaderImpl {
412 BitcodeReaderMetadataList MetadataList;
413 BitcodeReaderValueList &ValueList;
414 BitstreamCursor &Stream;
415 LLVMContext &Context;
416 Module &TheModule;
417 std::function<Type *(unsigned)> getTypeByID;
418
419 /// Cursor associated with the lazy-loading of Metadata. This is the easy way
420 /// to keep around the right "context" (Abbrev list) to be able to jump in
421 /// the middle of the metadata block and load any record.
422 BitstreamCursor IndexCursor;
423
424 /// Index that keeps track of MDString values.
425 std::vector<StringRef> MDStringRef;
426
427 /// On-demand loading of a single MDString. Requires the index above to be
428 /// populated.
429 MDString *lazyLoadOneMDString(unsigned Idx);
430
431 /// Index that keeps track of where to find a metadata record in the stream.
432 std::vector<uint64_t> GlobalMetadataBitPosIndex;
433
434 /// Populate the index above to enable lazily loading of metadata, and load
435 /// the named metadata as well as the transitively referenced global
436 /// Metadata.
437 Expected<bool> lazyLoadModuleMetadataBlock();
438
439 /// On-demand loading of a single metadata. Requires the index above to be
440 /// populated.
441 void lazyLoadOneMetadata(unsigned Idx, PlaceholderQueue &Placeholders);
442
443 // Keep mapping of seens pair of old-style CU <-> SP, and update pointers to
444 // point from SP to CU after a block is completly parsed.
445 std::vector<std::pair<DICompileUnit *, Metadata *>> CUSubprograms;
446
447 /// Functions that need to be matched with subprograms when upgrading old
448 /// metadata.
449 SmallDenseMap<Function *, DISubprogram *, 16> FunctionsWithSPs;
450
451 // Map the bitcode's custom MDKind ID to the Module's MDKind ID.
452 DenseMap<unsigned, unsigned> MDKindMap;
453
454 bool StripTBAA = false;
455 bool HasSeenOldLoopTags = false;
456 bool NeedUpgradeToDIGlobalVariableExpression = false;
457 bool NeedDeclareExpressionUpgrade = false;
458
459 /// True if metadata is being parsed for a module being ThinLTO imported.
460 bool IsImporting = false;
461
462 Error parseOneMetadata(SmallVectorImpl<uint64_t> &Record, unsigned Code,
463 PlaceholderQueue &Placeholders, StringRef Blob,
464 unsigned &NextMetadataNo);
465 Error parseMetadataStrings(ArrayRef<uint64_t> Record, StringRef Blob,
466 function_ref<void(StringRef)> CallBack);
467 Error parseGlobalObjectAttachment(GlobalObject &GO,
468 ArrayRef<uint64_t> Record);
469 Error parseMetadataKindRecord(SmallVectorImpl<uint64_t> &Record);
470
471 void resolveForwardRefsAndPlaceholders(PlaceholderQueue &Placeholders);
472
473 /// Upgrade old-style CU <-> SP pointers to point from SP to CU.
474 void upgradeCUSubprograms() {
475 for (auto CU_SP : CUSubprograms)
476 if (auto *SPs = dyn_cast_or_null<MDTuple>(CU_SP.second))
477 for (auto &Op : SPs->operands())
478 if (auto *SP = dyn_cast_or_null<DISubprogram>(Op))
479 SP->replaceUnit(CU_SP.first);
480 CUSubprograms.clear();
481 }
482
483 /// Upgrade old-style bare DIGlobalVariables to DIGlobalVariableExpressions.
484 void upgradeCUVariables() {
485 if (!NeedUpgradeToDIGlobalVariableExpression)
486 return;
487
488 // Upgrade list of variables attached to the CUs.
489 if (NamedMDNode *CUNodes = TheModule.getNamedMetadata("llvm.dbg.cu"))
490 for (unsigned I = 0, E = CUNodes->getNumOperands(); I != E; ++I) {
491 auto *CU = cast<DICompileUnit>(CUNodes->getOperand(I));
492 if (auto *GVs = dyn_cast_or_null<MDTuple>(CU->getRawGlobalVariables()))
493 for (unsigned I = 0; I < GVs->getNumOperands(); I++)
494 if (auto *GV =
495 dyn_cast_or_null<DIGlobalVariable>(GVs->getOperand(I))) {
496 auto *DGVE = DIGlobalVariableExpression::getDistinct(
497 Context, GV, DIExpression::get(Context, {}));
498 GVs->replaceOperandWith(I, DGVE);
499 }
500 }
501
502 // Upgrade variables attached to globals.
503 for (auto &GV : TheModule.globals()) {
504 SmallVector<MDNode *, 1> MDs;
505 GV.getMetadata(LLVMContext::MD_dbg, MDs);
506 GV.eraseMetadata(LLVMContext::MD_dbg);
507 for (auto *MD : MDs)
508 if (auto *DGV = dyn_cast_or_null<DIGlobalVariable>(MD)) {
509 auto *DGVE = DIGlobalVariableExpression::getDistinct(
510 Context, DGV, DIExpression::get(Context, {}));
511 GV.addMetadata(LLVMContext::MD_dbg, *DGVE);
512 } else
513 GV.addMetadata(LLVMContext::MD_dbg, *MD);
514 }
515 }
516
517 /// Remove a leading DW_OP_deref from DIExpressions in a dbg.declare that
518 /// describes a function argument.
519 void upgradeDeclareExpressions(Function &F) {
520 if (!NeedDeclareExpressionUpgrade)
521 return;
522
523 for (auto &BB : F)
524 for (auto &I : BB)
525 if (auto *DDI = dyn_cast<DbgDeclareInst>(&I))
526 if (auto *DIExpr = DDI->getExpression())
527 if (DIExpr->startsWithDeref() &&
528 dyn_cast_or_null<Argument>(DDI->getAddress())) {
529 SmallVector<uint64_t, 8> Ops;
530 Ops.append(std::next(DIExpr->elements_begin()),
531 DIExpr->elements_end());
532 auto *E = DIExpression::get(Context, Ops);
533 DDI->setOperand(2, MetadataAsValue::get(Context, E));
534 }
535 }
536
537 /// Upgrade the expression from previous versions.
538 Error upgradeDIExpression(uint64_t FromVersion,
539 MutableArrayRef<uint64_t> &Expr,
540 SmallVectorImpl<uint64_t> &Buffer) {
541 auto N = Expr.size();
542 switch (FromVersion) {
543 default:
544 return error("Invalid record");
545 case 0:
546 if (N >= 3 && Expr[N - 3] == dwarf::DW_OP_bit_piece)
547 Expr[N - 3] = dwarf::DW_OP_LLVM_fragment;
548 LLVM_FALLTHROUGH[[clang::fallthrough]];
549 case 1:
550 // Move DW_OP_deref to the end.
551 if (N && Expr[0] == dwarf::DW_OP_deref) {
552 auto End = Expr.end();
553 if (Expr.size() >= 3 &&
554 *std::prev(End, 3) == dwarf::DW_OP_LLVM_fragment)
555 End = std::prev(End, 3);
556 std::move(std::next(Expr.begin()), End, Expr.begin());
557 *std::prev(End) = dwarf::DW_OP_deref;
558 }
559 NeedDeclareExpressionUpgrade = true;
560 LLVM_FALLTHROUGH[[clang::fallthrough]];
561 case 2: {
562 // Change DW_OP_plus to DW_OP_plus_uconst.
563 // Change DW_OP_minus to DW_OP_uconst, DW_OP_minus
564 auto SubExpr = ArrayRef<uint64_t>(Expr);
565 while (!SubExpr.empty()) {
566 // Skip past other operators with their operands
567 // for this version of the IR, obtained from
568 // from historic DIExpression::ExprOperand::getSize().
569 size_t HistoricSize;
570 switch (SubExpr.front()) {
571 default:
572 HistoricSize = 1;
573 break;
574 case dwarf::DW_OP_constu:
575 case dwarf::DW_OP_minus:
576 case dwarf::DW_OP_plus:
577 HistoricSize = 2;
578 break;
579 case dwarf::DW_OP_LLVM_fragment:
580 HistoricSize = 3;
581 break;
582 }
583
584 // If the expression is malformed, make sure we don't
585 // copy more elements than we should.
586 HistoricSize = std::min(SubExpr.size(), HistoricSize);
587 ArrayRef<uint64_t> Args = SubExpr.slice(1, HistoricSize-1);
588
589 switch (SubExpr.front()) {
590 case dwarf::DW_OP_plus:
591 Buffer.push_back(dwarf::DW_OP_plus_uconst);
592 Buffer.append(Args.begin(), Args.end());
593 break;
594 case dwarf::DW_OP_minus:
595 Buffer.push_back(dwarf::DW_OP_constu);
596 Buffer.append(Args.begin(), Args.end());
597 Buffer.push_back(dwarf::DW_OP_minus);
598 break;
599 default:
600 Buffer.push_back(*SubExpr.begin());
601 Buffer.append(Args.begin(), Args.end());
602 break;
603 }
604
605 // Continue with remaining elements.
606 SubExpr = SubExpr.slice(HistoricSize);
607 }
608 Expr = MutableArrayRef<uint64_t>(Buffer);
609 LLVM_FALLTHROUGH[[clang::fallthrough]];
610 }
611 case 3:
612 // Up-to-date!
613 break;
614 }
615
616 return Error::success();
617 }
618
619 void upgradeDebugInfo() {
620 upgradeCUSubprograms();
621 upgradeCUVariables();
622 }
623
624public:
625 MetadataLoaderImpl(BitstreamCursor &Stream, Module &TheModule,
626 BitcodeReaderValueList &ValueList,
627 std::function<Type *(unsigned)> getTypeByID,
628 bool IsImporting)
629 : MetadataList(TheModule.getContext()), ValueList(ValueList),
630 Stream(Stream), Context(TheModule.getContext()), TheModule(TheModule),
631 getTypeByID(std::move(getTypeByID)), IsImporting(IsImporting) {}
632
633 Error parseMetadata(bool ModuleLevel);
634
635 bool hasFwdRefs() const { return MetadataList.hasFwdRefs(); }
636
637 Metadata *getMetadataFwdRefOrLoad(unsigned ID) {
638 if (ID < MDStringRef.size())
639 return lazyLoadOneMDString(ID);
640 if (auto *MD = MetadataList.lookup(ID))
641 return MD;
642 // If lazy-loading is enabled, we try recursively to load the operand
643 // instead of creating a temporary.
644 if (ID < (MDStringRef.size() + GlobalMetadataBitPosIndex.size())) {
645 PlaceholderQueue Placeholders;
646 lazyLoadOneMetadata(ID, Placeholders);
647 resolveForwardRefsAndPlaceholders(Placeholders);
648 return MetadataList.lookup(ID);
649 }
650 return MetadataList.getMetadataFwdRef(ID);
651 }
652
653 MDNode *getMDNodeFwdRefOrNull(unsigned Idx) {
654 return MetadataList.getMDNodeFwdRefOrNull(Idx);
655 }
656
657 DISubprogram *lookupSubprogramForFunction(Function *F) {
658 return FunctionsWithSPs.lookup(F);
659 }
660
661 bool hasSeenOldLoopTags() { return HasSeenOldLoopTags; }
662
663 Error parseMetadataAttachment(
664 Function &F, const SmallVectorImpl<Instruction *> &InstructionList);
665
666 Error parseMetadataKinds();
667
668 void setStripTBAA(bool Value) { StripTBAA = Value; }
669 bool isStrippingTBAA() { return StripTBAA; }
670
671 unsigned size() const { return MetadataList.size(); }
672 void shrinkTo(unsigned N) { MetadataList.shrinkTo(N); }
673 void upgradeDebugIntrinsics(Function &F) { upgradeDeclareExpressions(F); }
674};
675
676Expected<bool>
677MetadataLoader::MetadataLoaderImpl::lazyLoadModuleMetadataBlock() {
678 IndexCursor = Stream;
679 SmallVector<uint64_t, 64> Record;
680 // Get the abbrevs, and preload record positions to make them lazy-loadable.
681 while (true) {
682 BitstreamEntry Entry = IndexCursor.advanceSkippingSubblocks(
683 BitstreamCursor::AF_DontPopBlockAtEnd);
684 switch (Entry.Kind) {
685 case BitstreamEntry::SubBlock: // Handled for us already.
686 case BitstreamEntry::Error:
687 return error("Malformed block");
688 case BitstreamEntry::EndBlock: {
689 return true;
690 }
691 case BitstreamEntry::Record: {
692 // The interesting case.
693 ++NumMDRecordLoaded;
694 uint64_t CurrentPos = IndexCursor.GetCurrentBitNo();
695 auto Code = IndexCursor.skipRecord(Entry.ID);
696 switch (Code) {
697 case bitc::METADATA_STRINGS: {
698 // Rewind and parse the strings.
699 IndexCursor.JumpToBit(CurrentPos);
700 StringRef Blob;
701 Record.clear();
702 IndexCursor.readRecord(Entry.ID, Record, &Blob);
703 unsigned NumStrings = Record[0];
704 MDStringRef.reserve(NumStrings);
705 auto IndexNextMDString = [&](StringRef Str) {
706 MDStringRef.push_back(Str);
707 };
708 if (auto Err = parseMetadataStrings(Record, Blob, IndexNextMDString))
709 return std::move(Err);
710 break;
711 }
712 case bitc::METADATA_INDEX_OFFSET: {
713 // This is the offset to the index, when we see this we skip all the
714 // records and load only an index to these.
715 IndexCursor.JumpToBit(CurrentPos);
716 Record.clear();
717 IndexCursor.readRecord(Entry.ID, Record);
718 if (Record.size() != 2)
719 return error("Invalid record");
720 auto Offset = Record[0] + (Record[1] << 32);
721 auto BeginPos = IndexCursor.GetCurrentBitNo();
722 IndexCursor.JumpToBit(BeginPos + Offset);
723 Entry = IndexCursor.advanceSkippingSubblocks(
724 BitstreamCursor::AF_DontPopBlockAtEnd);
725 assert(Entry.Kind == BitstreamEntry::Record &&((Entry.Kind == BitstreamEntry::Record && "Corrupted bitcode: Expected `Record` when trying to find the "
"Metadata index") ? static_cast<void> (0) : __assert_fail
("Entry.Kind == BitstreamEntry::Record && \"Corrupted bitcode: Expected `Record` when trying to find the \" \"Metadata index\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 727, __PRETTY_FUNCTION__))
726 "Corrupted bitcode: Expected `Record` when trying to find the "((Entry.Kind == BitstreamEntry::Record && "Corrupted bitcode: Expected `Record` when trying to find the "
"Metadata index") ? static_cast<void> (0) : __assert_fail
("Entry.Kind == BitstreamEntry::Record && \"Corrupted bitcode: Expected `Record` when trying to find the \" \"Metadata index\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 727, __PRETTY_FUNCTION__))
727 "Metadata index")((Entry.Kind == BitstreamEntry::Record && "Corrupted bitcode: Expected `Record` when trying to find the "
"Metadata index") ? static_cast<void> (0) : __assert_fail
("Entry.Kind == BitstreamEntry::Record && \"Corrupted bitcode: Expected `Record` when trying to find the \" \"Metadata index\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 727, __PRETTY_FUNCTION__))
;
728 Record.clear();
729 auto Code = IndexCursor.readRecord(Entry.ID, Record);
730 (void)Code;
731 assert(Code == bitc::METADATA_INDEX && "Corrupted bitcode: Expected "((Code == bitc::METADATA_INDEX && "Corrupted bitcode: Expected "
"`METADATA_INDEX` when trying " "to find the Metadata index"
) ? static_cast<void> (0) : __assert_fail ("Code == bitc::METADATA_INDEX && \"Corrupted bitcode: Expected \" \"`METADATA_INDEX` when trying \" \"to find the Metadata index\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 733, __PRETTY_FUNCTION__))
732 "`METADATA_INDEX` when trying "((Code == bitc::METADATA_INDEX && "Corrupted bitcode: Expected "
"`METADATA_INDEX` when trying " "to find the Metadata index"
) ? static_cast<void> (0) : __assert_fail ("Code == bitc::METADATA_INDEX && \"Corrupted bitcode: Expected \" \"`METADATA_INDEX` when trying \" \"to find the Metadata index\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 733, __PRETTY_FUNCTION__))
733 "to find the Metadata index")((Code == bitc::METADATA_INDEX && "Corrupted bitcode: Expected "
"`METADATA_INDEX` when trying " "to find the Metadata index"
) ? static_cast<void> (0) : __assert_fail ("Code == bitc::METADATA_INDEX && \"Corrupted bitcode: Expected \" \"`METADATA_INDEX` when trying \" \"to find the Metadata index\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 733, __PRETTY_FUNCTION__))
;
734
735 // Delta unpack
736 auto CurrentValue = BeginPos;
737 GlobalMetadataBitPosIndex.reserve(Record.size());
738 for (auto &Elt : Record) {
739 CurrentValue += Elt;
740 GlobalMetadataBitPosIndex.push_back(CurrentValue);
741 }
742 break;
743 }
744 case bitc::METADATA_INDEX:
745 // We don't expect to get there, the Index is loaded when we encounter
746 // the offset.
747 return error("Corrupted Metadata block");
748 case bitc::METADATA_NAME: {
749 // Named metadata need to be materialized now and aren't deferred.
750 IndexCursor.JumpToBit(CurrentPos);
751 Record.clear();
752 unsigned Code = IndexCursor.readRecord(Entry.ID, Record);
753 assert(Code == bitc::METADATA_NAME)((Code == bitc::METADATA_NAME) ? static_cast<void> (0) :
__assert_fail ("Code == bitc::METADATA_NAME", "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 753, __PRETTY_FUNCTION__))
;
754
755 // Read name of the named metadata.
756 SmallString<8> Name(Record.begin(), Record.end());
757 Code = IndexCursor.ReadCode();
758
759 // Named Metadata comes in two parts, we expect the name to be followed
760 // by the node
761 Record.clear();
762 unsigned NextBitCode = IndexCursor.readRecord(Code, Record);
763 assert(NextBitCode == bitc::METADATA_NAMED_NODE)((NextBitCode == bitc::METADATA_NAMED_NODE) ? static_cast<
void> (0) : __assert_fail ("NextBitCode == bitc::METADATA_NAMED_NODE"
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 763, __PRETTY_FUNCTION__))
;
764 (void)NextBitCode;
765
766 // Read named metadata elements.
767 unsigned Size = Record.size();
768 NamedMDNode *NMD = TheModule.getOrInsertNamedMetadata(Name);
769 for (unsigned i = 0; i != Size; ++i) {
770 // FIXME: We could use a placeholder here, however NamedMDNode are
771 // taking MDNode as operand and not using the Metadata infrastructure.
772 // It is acknowledged by 'TODO: Inherit from Metadata' in the
773 // NamedMDNode class definition.
774 MDNode *MD = MetadataList.getMDNodeFwdRefOrNull(Record[i]);
775 assert(MD && "Invalid record")((MD && "Invalid record") ? static_cast<void> (
0) : __assert_fail ("MD && \"Invalid record\"", "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 775, __PRETTY_FUNCTION__))
;
776 NMD->addOperand(MD);
777 }
778 break;
779 }
780 case bitc::METADATA_GLOBAL_DECL_ATTACHMENT: {
781 // FIXME: we need to do this early because we don't materialize global
782 // value explicitly.
783 IndexCursor.JumpToBit(CurrentPos);
784 Record.clear();
785 IndexCursor.readRecord(Entry.ID, Record);
786 if (Record.size() % 2 == 0)
787 return error("Invalid record");
788 unsigned ValueID = Record[0];
789 if (ValueID >= ValueList.size())
790 return error("Invalid record");
791 if (auto *GO = dyn_cast<GlobalObject>(ValueList[ValueID]))
792 if (Error Err = parseGlobalObjectAttachment(
793 *GO, ArrayRef<uint64_t>(Record).slice(1)))
794 return std::move(Err);
795 break;
796 }
797 case bitc::METADATA_KIND:
798 case bitc::METADATA_STRING_OLD:
799 case bitc::METADATA_OLD_FN_NODE:
800 case bitc::METADATA_OLD_NODE:
801 case bitc::METADATA_VALUE:
802 case bitc::METADATA_DISTINCT_NODE:
803 case bitc::METADATA_NODE:
804 case bitc::METADATA_LOCATION:
805 case bitc::METADATA_GENERIC_DEBUG:
806 case bitc::METADATA_SUBRANGE:
807 case bitc::METADATA_ENUMERATOR:
808 case bitc::METADATA_BASIC_TYPE:
809 case bitc::METADATA_DERIVED_TYPE:
810 case bitc::METADATA_COMPOSITE_TYPE:
811 case bitc::METADATA_SUBROUTINE_TYPE:
812 case bitc::METADATA_MODULE:
813 case bitc::METADATA_FILE:
814 case bitc::METADATA_COMPILE_UNIT:
815 case bitc::METADATA_SUBPROGRAM:
816 case bitc::METADATA_LEXICAL_BLOCK:
817 case bitc::METADATA_LEXICAL_BLOCK_FILE:
818 case bitc::METADATA_NAMESPACE:
819 case bitc::METADATA_MACRO:
820 case bitc::METADATA_MACRO_FILE:
821 case bitc::METADATA_TEMPLATE_TYPE:
822 case bitc::METADATA_TEMPLATE_VALUE:
823 case bitc::METADATA_GLOBAL_VAR:
824 case bitc::METADATA_LOCAL_VAR:
825 case bitc::METADATA_LABEL:
826 case bitc::METADATA_EXPRESSION:
827 case bitc::METADATA_OBJC_PROPERTY:
828 case bitc::METADATA_IMPORTED_ENTITY:
829 case bitc::METADATA_GLOBAL_VAR_EXPR:
830 // We don't expect to see any of these, if we see one, give up on
831 // lazy-loading and fallback.
832 MDStringRef.clear();
833 GlobalMetadataBitPosIndex.clear();
834 return false;
835 }
836 break;
837 }
838 }
839 }
840}
841
842/// Parse a METADATA_BLOCK. If ModuleLevel is true then we are parsing
843/// module level metadata.
844Error MetadataLoader::MetadataLoaderImpl::parseMetadata(bool ModuleLevel) {
845 if (!ModuleLevel && MetadataList.hasFwdRefs())
846 return error("Invalid metadata: fwd refs into function blocks");
847
848 // Record the entry position so that we can jump back here and efficiently
849 // skip the whole block in case we lazy-load.
850 auto EntryPos = Stream.GetCurrentBitNo();
851
852 if (Stream.EnterSubBlock(bitc::METADATA_BLOCK_ID))
853 return error("Invalid record");
854
855 SmallVector<uint64_t, 64> Record;
856 PlaceholderQueue Placeholders;
857
858 // We lazy-load module-level metadata: we build an index for each record, and
859 // then load individual record as needed, starting with the named metadata.
860 if (ModuleLevel && IsImporting && MetadataList.empty() &&
861 !DisableLazyLoading) {
862 auto SuccessOrErr = lazyLoadModuleMetadataBlock();
863 if (!SuccessOrErr)
864 return SuccessOrErr.takeError();
865 if (SuccessOrErr.get()) {
866 // An index was successfully created and we will be able to load metadata
867 // on-demand.
868 MetadataList.resize(MDStringRef.size() +
869 GlobalMetadataBitPosIndex.size());
870
871 // Reading the named metadata created forward references and/or
872 // placeholders, that we flush here.
873 resolveForwardRefsAndPlaceholders(Placeholders);
874 upgradeDebugInfo();
875 // Return at the beginning of the block, since it is easy to skip it
876 // entirely from there.
877 Stream.ReadBlockEnd(); // Pop the abbrev block context.
878 Stream.JumpToBit(EntryPos);
879 if (Stream.SkipBlock())
880 return error("Invalid record");
881 return Error::success();
882 }
883 // Couldn't load an index, fallback to loading all the block "old-style".
884 }
885
886 unsigned NextMetadataNo = MetadataList.size();
887
888 // Read all the records.
889 while (true) {
890 BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
891
892 switch (Entry.Kind) {
893 case BitstreamEntry::SubBlock: // Handled for us already.
894 case BitstreamEntry::Error:
895 return error("Malformed block");
896 case BitstreamEntry::EndBlock:
897 resolveForwardRefsAndPlaceholders(Placeholders);
898 upgradeDebugInfo();
899 return Error::success();
900 case BitstreamEntry::Record:
901 // The interesting case.
902 break;
903 }
904
905 // Read a record.
906 Record.clear();
907 StringRef Blob;
908 ++NumMDRecordLoaded;
909 unsigned Code = Stream.readRecord(Entry.ID, Record, &Blob);
910 if (Error Err =
911 parseOneMetadata(Record, Code, Placeholders, Blob, NextMetadataNo))
912 return Err;
913 }
914}
915
916MDString *MetadataLoader::MetadataLoaderImpl::lazyLoadOneMDString(unsigned ID) {
917 ++NumMDStringLoaded;
918 if (Metadata *MD = MetadataList.lookup(ID))
919 return cast<MDString>(MD);
920 auto MDS = MDString::get(Context, MDStringRef[ID]);
921 MetadataList.assignValue(MDS, ID);
922 return MDS;
923}
924
925void MetadataLoader::MetadataLoaderImpl::lazyLoadOneMetadata(
926 unsigned ID, PlaceholderQueue &Placeholders) {
927 assert(ID < (MDStringRef.size()) + GlobalMetadataBitPosIndex.size())((ID < (MDStringRef.size()) + GlobalMetadataBitPosIndex.size
()) ? static_cast<void> (0) : __assert_fail ("ID < (MDStringRef.size()) + GlobalMetadataBitPosIndex.size()"
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 927, __PRETTY_FUNCTION__))
;
928 assert(ID >= MDStringRef.size() && "Unexpected lazy-loading of MDString")((ID >= MDStringRef.size() && "Unexpected lazy-loading of MDString"
) ? static_cast<void> (0) : __assert_fail ("ID >= MDStringRef.size() && \"Unexpected lazy-loading of MDString\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 928, __PRETTY_FUNCTION__))
;
929 // Lookup first if the metadata hasn't already been loaded.
930 if (auto *MD = MetadataList.lookup(ID)) {
931 auto *N = dyn_cast_or_null<MDNode>(MD);
932 if (!N->isTemporary())
933 return;
934 }
935 SmallVector<uint64_t, 64> Record;
936 StringRef Blob;
937 IndexCursor.JumpToBit(GlobalMetadataBitPosIndex[ID - MDStringRef.size()]);
938 auto Entry = IndexCursor.advanceSkippingSubblocks();
939 ++NumMDRecordLoaded;
940 unsigned Code = IndexCursor.readRecord(Entry.ID, Record, &Blob);
941 if (Error Err = parseOneMetadata(Record, Code, Placeholders, Blob, ID))
942 report_fatal_error("Can't lazyload MD");
943}
944
945/// Ensure that all forward-references and placeholders are resolved.
946/// Iteratively lazy-loading metadata on-demand if needed.
947void MetadataLoader::MetadataLoaderImpl::resolveForwardRefsAndPlaceholders(
948 PlaceholderQueue &Placeholders) {
949 DenseSet<unsigned> Temporaries;
950 while (1) {
951 // Populate Temporaries with the placeholders that haven't been loaded yet.
952 Placeholders.getTemporaries(MetadataList, Temporaries);
953
954 // If we don't have any temporary, or FwdReference, we're done!
955 if (Temporaries.empty() && !MetadataList.hasFwdRefs())
956 break;
957
958 // First, load all the temporaries. This can add new placeholders or
959 // forward references.
960 for (auto ID : Temporaries)
961 lazyLoadOneMetadata(ID, Placeholders);
962 Temporaries.clear();
963
964 // Second, load the forward-references. This can also add new placeholders
965 // or forward references.
966 while (MetadataList.hasFwdRefs())
967 lazyLoadOneMetadata(MetadataList.getNextFwdRef(), Placeholders);
968 }
969 // At this point we don't have any forward reference remaining, or temporary
970 // that haven't been loaded. We can safely drop RAUW support and mark cycles
971 // as resolved.
972 MetadataList.tryToResolveCycles();
973
974 // Finally, everything is in place, we can replace the placeholders operands
975 // with the final node they refer to.
976 Placeholders.flush(MetadataList);
977}
978
979Error MetadataLoader::MetadataLoaderImpl::parseOneMetadata(
980 SmallVectorImpl<uint64_t> &Record, unsigned Code,
981 PlaceholderQueue &Placeholders, StringRef Blob, unsigned &NextMetadataNo) {
982
983 bool IsDistinct = false;
984 auto getMD = [&](unsigned ID) -> Metadata * {
985 if (ID < MDStringRef.size())
986 return lazyLoadOneMDString(ID);
987 if (!IsDistinct) {
988 if (auto *MD = MetadataList.lookup(ID))
989 return MD;
990 // If lazy-loading is enabled, we try recursively to load the operand
991 // instead of creating a temporary.
992 if (ID < (MDStringRef.size() + GlobalMetadataBitPosIndex.size())) {
993 // Create a temporary for the node that is referencing the operand we
994 // will lazy-load. It is needed before recursing in case there are
995 // uniquing cycles.
996 MetadataList.getMetadataFwdRef(NextMetadataNo);
997 lazyLoadOneMetadata(ID, Placeholders);
998 return MetadataList.lookup(ID);
999 }
1000 // Return a temporary.
1001 return MetadataList.getMetadataFwdRef(ID);
1002 }
1003 if (auto *MD = MetadataList.getMetadataIfResolved(ID))
1004 return MD;
1005 return &Placeholders.getPlaceholderOp(ID);
1006 };
1007 auto getMDOrNull = [&](unsigned ID) -> Metadata * {
1008 if (ID)
1009 return getMD(ID - 1);
1010 return nullptr;
1011 };
1012 auto getMDOrNullWithoutPlaceholders = [&](unsigned ID) -> Metadata * {
1013 if (ID)
1014 return MetadataList.getMetadataFwdRef(ID - 1);
1015 return nullptr;
1016 };
1017 auto getMDString = [&](unsigned ID) -> MDString * {
1018 // This requires that the ID is not really a forward reference. In
1019 // particular, the MDString must already have been resolved.
1020 auto MDS = getMDOrNull(ID);
1021 return cast_or_null<MDString>(MDS);
1022 };
1023
1024 // Support for old type refs.
1025 auto getDITypeRefOrNull = [&](unsigned ID) {
1026 return MetadataList.upgradeTypeRef(getMDOrNull(ID));
1027 };
1028
1029#define GET_OR_DISTINCT(CLASS, ARGS) \
1030 (IsDistinct ? CLASS::getDistinct ARGS : CLASS::get ARGS)
1031
1032 switch (Code) {
1033 default: // Default behavior: ignore.
1034 break;
1035 case bitc::METADATA_NAME: {
1036 // Read name of the named metadata.
1037 SmallString<8> Name(Record.begin(), Record.end());
1038 Record.clear();
1039 Code = Stream.ReadCode();
1040
1041 ++NumMDRecordLoaded;
1042 unsigned NextBitCode = Stream.readRecord(Code, Record);
1043 if (NextBitCode != bitc::METADATA_NAMED_NODE)
1044 return error("METADATA_NAME not followed by METADATA_NAMED_NODE");
1045
1046 // Read named metadata elements.
1047 unsigned Size = Record.size();
1048 NamedMDNode *NMD = TheModule.getOrInsertNamedMetadata(Name);
1049 for (unsigned i = 0; i != Size; ++i) {
1050 MDNode *MD = MetadataList.getMDNodeFwdRefOrNull(Record[i]);
1051 if (!MD)
1052 return error("Invalid record");
1053 NMD->addOperand(MD);
1054 }
1055 break;
1056 }
1057 case bitc::METADATA_OLD_FN_NODE: {
1058 // FIXME: Remove in 4.0.
1059 // This is a LocalAsMetadata record, the only type of function-local
1060 // metadata.
1061 if (Record.size() % 2 == 1)
1062 return error("Invalid record");
1063
1064 // If this isn't a LocalAsMetadata record, we're dropping it. This used
1065 // to be legal, but there's no upgrade path.
1066 auto dropRecord = [&] {
1067 MetadataList.assignValue(MDNode::get(Context, None), NextMetadataNo);
1068 NextMetadataNo++;
1069 };
1070 if (Record.size() != 2) {
1071 dropRecord();
1072 break;
1073 }
1074
1075 Type *Ty = getTypeByID(Record[0]);
1076 if (Ty->isMetadataTy() || Ty->isVoidTy()) {
1077 dropRecord();
1078 break;
1079 }
1080
1081 MetadataList.assignValue(
1082 LocalAsMetadata::get(ValueList.getValueFwdRef(Record[1], Ty)),
1083 NextMetadataNo);
1084 NextMetadataNo++;
1085 break;
1086 }
1087 case bitc::METADATA_OLD_NODE: {
1088 // FIXME: Remove in 4.0.
1089 if (Record.size() % 2 == 1)
1090 return error("Invalid record");
1091
1092 unsigned Size = Record.size();
1093 SmallVector<Metadata *, 8> Elts;
1094 for (unsigned i = 0; i != Size; i += 2) {
1095 Type *Ty = getTypeByID(Record[i]);
1096 if (!Ty)
1097 return error("Invalid record");
1098 if (Ty->isMetadataTy())
1099 Elts.push_back(getMD(Record[i + 1]));
1100 else if (!Ty->isVoidTy()) {
1101 auto *MD =
1102 ValueAsMetadata::get(ValueList.getValueFwdRef(Record[i + 1], Ty));
1103 assert(isa<ConstantAsMetadata>(MD) &&((isa<ConstantAsMetadata>(MD) && "Expected non-function-local metadata"
) ? static_cast<void> (0) : __assert_fail ("isa<ConstantAsMetadata>(MD) && \"Expected non-function-local metadata\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 1104, __PRETTY_FUNCTION__))
1104 "Expected non-function-local metadata")((isa<ConstantAsMetadata>(MD) && "Expected non-function-local metadata"
) ? static_cast<void> (0) : __assert_fail ("isa<ConstantAsMetadata>(MD) && \"Expected non-function-local metadata\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 1104, __PRETTY_FUNCTION__))
;
1105 Elts.push_back(MD);
1106 } else
1107 Elts.push_back(nullptr);
1108 }
1109 MetadataList.assignValue(MDNode::get(Context, Elts), NextMetadataNo);
1110 NextMetadataNo++;
1111 break;
1112 }
1113 case bitc::METADATA_VALUE: {
1114 if (Record.size() != 2)
1115 return error("Invalid record");
1116
1117 Type *Ty = getTypeByID(Record[0]);
1118 if (Ty->isMetadataTy() || Ty->isVoidTy())
1119 return error("Invalid record");
1120
1121 MetadataList.assignValue(
1122 ValueAsMetadata::get(ValueList.getValueFwdRef(Record[1], Ty)),
1123 NextMetadataNo);
1124 NextMetadataNo++;
1125 break;
1126 }
1127 case bitc::METADATA_DISTINCT_NODE:
1128 IsDistinct = true;
1129 LLVM_FALLTHROUGH[[clang::fallthrough]];
1130 case bitc::METADATA_NODE: {
1131 SmallVector<Metadata *, 8> Elts;
1132 Elts.reserve(Record.size());
1133 for (unsigned ID : Record)
1134 Elts.push_back(getMDOrNull(ID));
1135 MetadataList.assignValue(IsDistinct ? MDNode::getDistinct(Context, Elts)
1136 : MDNode::get(Context, Elts),
1137 NextMetadataNo);
1138 NextMetadataNo++;
1139 break;
1140 }
1141 case bitc::METADATA_LOCATION: {
1142 if (Record.size() != 5 && Record.size() != 6)
1143 return error("Invalid record");
1144
1145 IsDistinct = Record[0];
1146 unsigned Line = Record[1];
1147 unsigned Column = Record[2];
1148 Metadata *Scope = getMD(Record[3]);
1149 Metadata *InlinedAt = getMDOrNull(Record[4]);
1150 bool ImplicitCode = Record.size() == 6 && Record[5];
1151 MetadataList.assignValue(
1152 GET_OR_DISTINCT(DILocation, (Context, Line, Column, Scope, InlinedAt,
1153 ImplicitCode)),
1154 NextMetadataNo);
1155 NextMetadataNo++;
1156 break;
1157 }
1158 case bitc::METADATA_GENERIC_DEBUG: {
1159 if (Record.size() < 4)
1160 return error("Invalid record");
1161
1162 IsDistinct = Record[0];
1163 unsigned Tag = Record[1];
1164 unsigned Version = Record[2];
1165
1166 if (Tag >= 1u << 16 || Version != 0)
1167 return error("Invalid record");
1168
1169 auto *Header = getMDString(Record[3]);
1170 SmallVector<Metadata *, 8> DwarfOps;
1171 for (unsigned I = 4, E = Record.size(); I != E; ++I)
1172 DwarfOps.push_back(getMDOrNull(Record[I]));
1173 MetadataList.assignValue(
1174 GET_OR_DISTINCT(GenericDINode, (Context, Tag, Header, DwarfOps)),
1175 NextMetadataNo);
1176 NextMetadataNo++;
1177 break;
1178 }
1179 case bitc::METADATA_SUBRANGE: {
1180 Metadata *Val = nullptr;
1181 // Operand 'count' is interpreted as:
1182 // - Signed integer (version 0)
1183 // - Metadata node (version 1)
1184 switch (Record[0] >> 1) {
1185 case 0:
1186 Val = GET_OR_DISTINCT(DISubrange,
1187 (Context, Record[1], unrotateSign(Record.back())));
1188 break;
1189 case 1:
1190 Val = GET_OR_DISTINCT(DISubrange, (Context, getMDOrNull(Record[1]),
1191 unrotateSign(Record.back())));
1192 break;
1193 default:
1194 return error("Invalid record: Unsupported version of DISubrange");
1195 }
1196
1197 MetadataList.assignValue(Val, NextMetadataNo);
1198 IsDistinct = Record[0] & 1;
1199 NextMetadataNo++;
1200 break;
1201 }
1202 case bitc::METADATA_ENUMERATOR: {
1203 if (Record.size() != 3)
1204 return error("Invalid record");
1205
1206 IsDistinct = Record[0] & 1;
1207 bool IsUnsigned = Record[0] & 2;
1208 MetadataList.assignValue(
1209 GET_OR_DISTINCT(DIEnumerator, (Context, unrotateSign(Record[1]),
1210 IsUnsigned, getMDString(Record[2]))),
1211 NextMetadataNo);
1212 NextMetadataNo++;
1213 break;
1214 }
1215 case bitc::METADATA_BASIC_TYPE: {
1216 if (Record.size() < 6 || Record.size() > 7)
1217 return error("Invalid record");
1218
1219 IsDistinct = Record[0];
1220 DINode::DIFlags Flags = (Record.size() > 6) ?
1221 static_cast<DINode::DIFlags>(Record[6]) : DINode::FlagZero;
1222
1223 MetadataList.assignValue(
1224 GET_OR_DISTINCT(DIBasicType,
1225 (Context, Record[1], getMDString(Record[2]), Record[3],
1226 Record[4], Record[5], Flags)),
1227 NextMetadataNo);
1228 NextMetadataNo++;
1229 break;
1230 }
1231 case bitc::METADATA_DERIVED_TYPE: {
1232 if (Record.size() < 12 || Record.size() > 13)
1233 return error("Invalid record");
1234
1235 // DWARF address space is encoded as N->getDWARFAddressSpace() + 1. 0 means
1236 // that there is no DWARF address space associated with DIDerivedType.
1237 Optional<unsigned> DWARFAddressSpace;
1238 if (Record.size() > 12 && Record[12])
1239 DWARFAddressSpace = Record[12] - 1;
1240
1241 IsDistinct = Record[0];
1242 DINode::DIFlags Flags = static_cast<DINode::DIFlags>(Record[10]);
1243 MetadataList.assignValue(
1244 GET_OR_DISTINCT(DIDerivedType,
1245 (Context, Record[1], getMDString(Record[2]),
1246 getMDOrNull(Record[3]), Record[4],
1247 getDITypeRefOrNull(Record[5]),
1248 getDITypeRefOrNull(Record[6]), Record[7], Record[8],
1249 Record[9], DWARFAddressSpace, Flags,
1250 getDITypeRefOrNull(Record[11]))),
1251 NextMetadataNo);
1252 NextMetadataNo++;
1253 break;
1254 }
1255 case bitc::METADATA_COMPOSITE_TYPE: {
1256 if (Record.size() < 16 || Record.size() > 17)
1257 return error("Invalid record");
1258
1259 // If we have a UUID and this is not a forward declaration, lookup the
1260 // mapping.
1261 IsDistinct = Record[0] & 0x1;
1262 bool IsNotUsedInTypeRef = Record[0] >= 2;
1263 unsigned Tag = Record[1];
1264 MDString *Name = getMDString(Record[2]);
1265 Metadata *File = getMDOrNull(Record[3]);
1266 unsigned Line = Record[4];
1267 Metadata *Scope = getDITypeRefOrNull(Record[5]);
1268 Metadata *BaseType = nullptr;
1269 uint64_t SizeInBits = Record[7];
1270 if (Record[8] > (uint64_t)std::numeric_limits<uint32_t>::max())
1271 return error("Alignment value is too large");
1272 uint32_t AlignInBits = Record[8];
1273 uint64_t OffsetInBits = 0;
1274 DINode::DIFlags Flags = static_cast<DINode::DIFlags>(Record[10]);
1275 Metadata *Elements = nullptr;
1276 unsigned RuntimeLang = Record[12];
1277 Metadata *VTableHolder = nullptr;
1278 Metadata *TemplateParams = nullptr;
1279 Metadata *Discriminator = nullptr;
1280 auto *Identifier = getMDString(Record[15]);
1281 // If this module is being parsed so that it can be ThinLTO imported
1282 // into another module, composite types only need to be imported
1283 // as type declarations (unless full type definitions requested).
1284 // Create type declarations up front to save memory. Also, buildODRType
1285 // handles the case where this is type ODRed with a definition needed
1286 // by the importing module, in which case the existing definition is
1287 // used.
1288 if (IsImporting && !ImportFullTypeDefinitions && Identifier &&
1289 (Tag == dwarf::DW_TAG_enumeration_type ||
1290 Tag == dwarf::DW_TAG_class_type ||
1291 Tag == dwarf::DW_TAG_structure_type ||
1292 Tag == dwarf::DW_TAG_union_type)) {
1293 Flags = Flags | DINode::FlagFwdDecl;
1294 } else {
1295 BaseType = getDITypeRefOrNull(Record[6]);
1296 OffsetInBits = Record[9];
1297 Elements = getMDOrNull(Record[11]);
1298 VTableHolder = getDITypeRefOrNull(Record[13]);
1299 TemplateParams = getMDOrNull(Record[14]);
1300 if (Record.size() > 16)
1301 Discriminator = getMDOrNull(Record[16]);
1302 }
1303 DICompositeType *CT = nullptr;
1304 if (Identifier)
1305 CT = DICompositeType::buildODRType(
1306 Context, *Identifier, Tag, Name, File, Line, Scope, BaseType,
1307 SizeInBits, AlignInBits, OffsetInBits, Flags, Elements, RuntimeLang,
1308 VTableHolder, TemplateParams, Discriminator);
1309
1310 // Create a node if we didn't get a lazy ODR type.
1311 if (!CT)
1312 CT = GET_OR_DISTINCT(DICompositeType,
1313 (Context, Tag, Name, File, Line, Scope, BaseType,
1314 SizeInBits, AlignInBits, OffsetInBits, Flags,
1315 Elements, RuntimeLang, VTableHolder, TemplateParams,
1316 Identifier, Discriminator));
1317 if (!IsNotUsedInTypeRef && Identifier)
1318 MetadataList.addTypeRef(*Identifier, *cast<DICompositeType>(CT));
1319
1320 MetadataList.assignValue(CT, NextMetadataNo);
1321 NextMetadataNo++;
1322 break;
1323 }
1324 case bitc::METADATA_SUBROUTINE_TYPE: {
1325 if (Record.size() < 3 || Record.size() > 4)
1326 return error("Invalid record");
1327 bool IsOldTypeRefArray = Record[0] < 2;
1328 unsigned CC = (Record.size() > 3) ? Record[3] : 0;
1329
1330 IsDistinct = Record[0] & 0x1;
1331 DINode::DIFlags Flags = static_cast<DINode::DIFlags>(Record[1]);
1332 Metadata *Types = getMDOrNull(Record[2]);
1333 if (LLVM_UNLIKELY(IsOldTypeRefArray)__builtin_expect((bool)(IsOldTypeRefArray), false))
1334 Types = MetadataList.upgradeTypeRefArray(Types);
1335
1336 MetadataList.assignValue(
1337 GET_OR_DISTINCT(DISubroutineType, (Context, Flags, CC, Types)),
1338 NextMetadataNo);
1339 NextMetadataNo++;
1340 break;
1341 }
1342
1343 case bitc::METADATA_MODULE: {
1344 if (Record.size() != 6)
1345 return error("Invalid record");
1346
1347 IsDistinct = Record[0];
1348 MetadataList.assignValue(
1349 GET_OR_DISTINCT(DIModule,
1350 (Context, getMDOrNull(Record[1]),
1351 getMDString(Record[2]), getMDString(Record[3]),
1352 getMDString(Record[4]), getMDString(Record[5]))),
1353 NextMetadataNo);
1354 NextMetadataNo++;
1355 break;
1356 }
1357
1358 case bitc::METADATA_FILE: {
1359 if (Record.size() != 3 && Record.size() != 5 && Record.size() != 6)
1360 return error("Invalid record");
1361
1362 IsDistinct = Record[0];
1363 Optional<DIFile::ChecksumInfo<MDString *>> Checksum;
1364 // The BitcodeWriter writes null bytes into Record[3:4] when the Checksum
1365 // is not present. This matches up with the old internal representation,
1366 // and the old encoding for CSK_None in the ChecksumKind. The new
1367 // representation reserves the value 0 in the ChecksumKind to continue to
1368 // encode None in a backwards-compatible way.
1369 if (Record.size() > 4 && Record[3] && Record[4])
1370 Checksum.emplace(static_cast<DIFile::ChecksumKind>(Record[3]),
1371 getMDString(Record[4]));
1372 MetadataList.assignValue(
1373 GET_OR_DISTINCT(
1374 DIFile,
1375 (Context, getMDString(Record[1]), getMDString(Record[2]), Checksum,
1376 Record.size() > 5 ? Optional<MDString *>(getMDString(Record[5]))
1377 : None)),
1378 NextMetadataNo);
1379 NextMetadataNo++;
1380 break;
1381 }
1382 case bitc::METADATA_COMPILE_UNIT: {
1383 if (Record.size() < 14 || Record.size() > 19)
1384 return error("Invalid record");
1385
1386 // Ignore Record[0], which indicates whether this compile unit is
1387 // distinct. It's always distinct.
1388 IsDistinct = true;
1389 auto *CU = DICompileUnit::getDistinct(
1390 Context, Record[1], getMDOrNull(Record[2]), getMDString(Record[3]),
1391 Record[4], getMDString(Record[5]), Record[6], getMDString(Record[7]),
1392 Record[8], getMDOrNull(Record[9]), getMDOrNull(Record[10]),
1393 getMDOrNull(Record[12]), getMDOrNull(Record[13]),
1394 Record.size() <= 15 ? nullptr : getMDOrNull(Record[15]),
1395 Record.size() <= 14 ? 0 : Record[14],
1396 Record.size() <= 16 ? true : Record[16],
1397 Record.size() <= 17 ? false : Record[17],
1398 Record.size() <= 18 ? 0 : Record[18]);
1399
1400 MetadataList.assignValue(CU, NextMetadataNo);
1401 NextMetadataNo++;
1402
1403 // Move the Upgrade the list of subprograms.
1404 if (Metadata *SPs = getMDOrNullWithoutPlaceholders(Record[11]))
1405 CUSubprograms.push_back({CU, SPs});
1406 break;
1407 }
1408 case bitc::METADATA_SUBPROGRAM: {
1409 if (Record.size() < 18 || Record.size() > 21)
1410 return error("Invalid record");
1411
1412 IsDistinct =
1413 (Record[0] & 1) || Record[8]; // All definitions should be distinct.
1414 // Version 1 has a Function as Record[15].
1415 // Version 2 has removed Record[15].
1416 // Version 3 has the Unit as Record[15].
1417 // Version 4 added thisAdjustment.
1418 bool HasUnit = Record[0] >= 2;
1419 if (HasUnit && Record.size() < 19)
1420 return error("Invalid record");
1421 Metadata *CUorFn = getMDOrNull(Record[15]);
1422 unsigned Offset = Record.size() >= 19 ? 1 : 0;
1423 bool HasFn = Offset && !HasUnit;
1424 bool HasThisAdj = Record.size() >= 20;
1425 bool HasThrownTypes = Record.size() >= 21;
1426 DISubprogram *SP = GET_OR_DISTINCT(
1427 DISubprogram,
1428 (Context,
1429 getDITypeRefOrNull(Record[1]), // scope
1430 getMDString(Record[2]), // name
1431 getMDString(Record[3]), // linkageName
1432 getMDOrNull(Record[4]), // file
1433 Record[5], // line
1434 getMDOrNull(Record[6]), // type
1435 Record[7], // isLocal
1436 Record[8], // isDefinition
1437 Record[9], // scopeLine
1438 getDITypeRefOrNull(Record[10]), // containingType
1439 Record[11], // virtuality
1440 Record[12], // virtualIndex
1441 HasThisAdj ? Record[19] : 0, // thisAdjustment
1442 static_cast<DINode::DIFlags>(Record[13]), // flags
1443 Record[14], // isOptimized
1444 HasUnit ? CUorFn : nullptr, // unit
1445 getMDOrNull(Record[15 + Offset]), // templateParams
1446 getMDOrNull(Record[16 + Offset]), // declaration
1447 getMDOrNull(Record[17 + Offset]), // retainedNodes
1448 HasThrownTypes ? getMDOrNull(Record[20]) : nullptr // thrownTypes
1449 ));
1450 MetadataList.assignValue(SP, NextMetadataNo);
1451 NextMetadataNo++;
1452
1453 // Upgrade sp->function mapping to function->sp mapping.
1454 if (HasFn) {
1455 if (auto *CMD = dyn_cast_or_null<ConstantAsMetadata>(CUorFn))
1456 if (auto *F = dyn_cast<Function>(CMD->getValue())) {
1457 if (F->isMaterializable())
1458 // Defer until materialized; unmaterialized functions may not have
1459 // metadata.
1460 FunctionsWithSPs[F] = SP;
1461 else if (!F->empty())
1462 F->setSubprogram(SP);
1463 }
1464 }
1465 break;
1466 }
1467 case bitc::METADATA_LEXICAL_BLOCK: {
1468 if (Record.size() != 5)
1469 return error("Invalid record");
1470
1471 IsDistinct = Record[0];
1472 MetadataList.assignValue(
1473 GET_OR_DISTINCT(DILexicalBlock,
1474 (Context, getMDOrNull(Record[1]),
1475 getMDOrNull(Record[2]), Record[3], Record[4])),
1476 NextMetadataNo);
1477 NextMetadataNo++;
1478 break;
1479 }
1480 case bitc::METADATA_LEXICAL_BLOCK_FILE: {
1481 if (Record.size() != 4)
1482 return error("Invalid record");
1483
1484 IsDistinct = Record[0];
1485 MetadataList.assignValue(
1486 GET_OR_DISTINCT(DILexicalBlockFile,
1487 (Context, getMDOrNull(Record[1]),
1488 getMDOrNull(Record[2]), Record[3])),
1489 NextMetadataNo);
1490 NextMetadataNo++;
1491 break;
1492 }
1493 case bitc::METADATA_NAMESPACE: {
1494 // Newer versions of DINamespace dropped file and line.
1495 MDString *Name;
1496 if (Record.size() == 3)
1497 Name = getMDString(Record[2]);
1498 else if (Record.size() == 5)
1499 Name = getMDString(Record[3]);
1500 else
1501 return error("Invalid record");
1502
1503 IsDistinct = Record[0] & 1;
1504 bool ExportSymbols = Record[0] & 2;
1505 MetadataList.assignValue(
1506 GET_OR_DISTINCT(DINamespace,
1507 (Context, getMDOrNull(Record[1]), Name, ExportSymbols)),
1508 NextMetadataNo);
1509 NextMetadataNo++;
1510 break;
1511 }
1512 case bitc::METADATA_MACRO: {
1513 if (Record.size() != 5)
1514 return error("Invalid record");
1515
1516 IsDistinct = Record[0];
1517 MetadataList.assignValue(
1518 GET_OR_DISTINCT(DIMacro,
1519 (Context, Record[1], Record[2], getMDString(Record[3]),
1520 getMDString(Record[4]))),
1521 NextMetadataNo);
1522 NextMetadataNo++;
1523 break;
1524 }
1525 case bitc::METADATA_MACRO_FILE: {
1526 if (Record.size() != 5)
1527 return error("Invalid record");
1528
1529 IsDistinct = Record[0];
1530 MetadataList.assignValue(
1531 GET_OR_DISTINCT(DIMacroFile,
1532 (Context, Record[1], Record[2], getMDOrNull(Record[3]),
1533 getMDOrNull(Record[4]))),
1534 NextMetadataNo);
1535 NextMetadataNo++;
1536 break;
1537 }
1538 case bitc::METADATA_TEMPLATE_TYPE: {
1539 if (Record.size() != 3)
1540 return error("Invalid record");
1541
1542 IsDistinct = Record[0];
1543 MetadataList.assignValue(GET_OR_DISTINCT(DITemplateTypeParameter,
1544 (Context, getMDString(Record[1]),
1545 getDITypeRefOrNull(Record[2]))),
1546 NextMetadataNo);
1547 NextMetadataNo++;
1548 break;
1549 }
1550 case bitc::METADATA_TEMPLATE_VALUE: {
1551 if (Record.size() != 5)
1552 return error("Invalid record");
1553
1554 IsDistinct = Record[0];
1555 MetadataList.assignValue(
1556 GET_OR_DISTINCT(DITemplateValueParameter,
1557 (Context, Record[1], getMDString(Record[2]),
1558 getDITypeRefOrNull(Record[3]),
1559 getMDOrNull(Record[4]))),
1560 NextMetadataNo);
1561 NextMetadataNo++;
1562 break;
1563 }
1564 case bitc::METADATA_GLOBAL_VAR: {
1565 if (Record.size() < 11 || Record.size() > 13)
1566 return error("Invalid record");
1567
1568 IsDistinct = Record[0] & 1;
1569 unsigned Version = Record[0] >> 1;
1570
1571 if (Version == 2) {
1572 MetadataList.assignValue(
1573 GET_OR_DISTINCT(
1574 DIGlobalVariable,
1575 (Context, getMDOrNull(Record[1]), getMDString(Record[2]),
1576 getMDString(Record[3]), getMDOrNull(Record[4]), Record[5],
1577 getDITypeRefOrNull(Record[6]), Record[7], Record[8],
1578 getMDOrNull(Record[9]), getMDOrNull(Record[10]), Record[11])),
1579 NextMetadataNo);
1580
1581 NextMetadataNo++;
1582 } else if (Version == 1) {
1583 // No upgrade necessary. A null field will be introduced to indicate
1584 // that no parameter information is available.
1585 MetadataList.assignValue(
1586 GET_OR_DISTINCT(DIGlobalVariable,
1587 (Context, getMDOrNull(Record[1]),
1588 getMDString(Record[2]), getMDString(Record[3]),
1589 getMDOrNull(Record[4]), Record[5],
1590 getDITypeRefOrNull(Record[6]), Record[7], Record[8],
1591 getMDOrNull(Record[10]), nullptr, Record[11])),
1592 NextMetadataNo);
1593
1594 NextMetadataNo++;
1595 } else if (Version == 0) {
1596 // Upgrade old metadata, which stored a global variable reference or a
1597 // ConstantInt here.
1598 NeedUpgradeToDIGlobalVariableExpression = true;
1599 Metadata *Expr = getMDOrNull(Record[9]);
1600 uint32_t AlignInBits = 0;
1601 if (Record.size() > 11) {
1602 if (Record[11] > (uint64_t)std::numeric_limits<uint32_t>::max())
1603 return error("Alignment value is too large");
1604 AlignInBits = Record[11];
1605 }
1606 GlobalVariable *Attach = nullptr;
1607 if (auto *CMD = dyn_cast_or_null<ConstantAsMetadata>(Expr)) {
1608 if (auto *GV = dyn_cast<GlobalVariable>(CMD->getValue())) {
1609 Attach = GV;
1610 Expr = nullptr;
1611 } else if (auto *CI = dyn_cast<ConstantInt>(CMD->getValue())) {
1612 Expr = DIExpression::get(Context,
1613 {dwarf::DW_OP_constu, CI->getZExtValue(),
1614 dwarf::DW_OP_stack_value});
1615 } else {
1616 Expr = nullptr;
1617 }
1618 }
1619 DIGlobalVariable *DGV = GET_OR_DISTINCT(
1620 DIGlobalVariable,
1621 (Context, getMDOrNull(Record[1]), getMDString(Record[2]),
1622 getMDString(Record[3]), getMDOrNull(Record[4]), Record[5],
1623 getDITypeRefOrNull(Record[6]), Record[7], Record[8],
1624 getMDOrNull(Record[10]), nullptr, AlignInBits));
1625
1626 DIGlobalVariableExpression *DGVE = nullptr;
1627 if (Attach || Expr)
1628 DGVE = DIGlobalVariableExpression::getDistinct(
1629 Context, DGV, Expr ? Expr : DIExpression::get(Context, {}));
1630 if (Attach)
1631 Attach->addDebugInfo(DGVE);
1632
1633 auto *MDNode = Expr ? cast<Metadata>(DGVE) : cast<Metadata>(DGV);
1634 MetadataList.assignValue(MDNode, NextMetadataNo);
1635 NextMetadataNo++;
1636 } else
1637 return error("Invalid record");
1638
1639 break;
1640 }
1641 case bitc::METADATA_LOCAL_VAR: {
1642 // 10th field is for the obseleted 'inlinedAt:' field.
1643 if (Record.size() < 8 || Record.size() > 10)
1644 return error("Invalid record");
1645
1646 IsDistinct = Record[0] & 1;
1647 bool HasAlignment = Record[0] & 2;
1648 // 2nd field used to be an artificial tag, either DW_TAG_auto_variable or
1649 // DW_TAG_arg_variable, if we have alignment flag encoded it means, that
1650 // this is newer version of record which doesn't have artificial tag.
1651 bool HasTag = !HasAlignment && Record.size() > 8;
1652 DINode::DIFlags Flags = static_cast<DINode::DIFlags>(Record[7 + HasTag]);
1653 uint32_t AlignInBits = 0;
1654 if (HasAlignment) {
1655 if (Record[8 + HasTag] > (uint64_t)std::numeric_limits<uint32_t>::max())
1656 return error("Alignment value is too large");
1657 AlignInBits = Record[8 + HasTag];
1658 }
1659 MetadataList.assignValue(
1660 GET_OR_DISTINCT(DILocalVariable,
1661 (Context, getMDOrNull(Record[1 + HasTag]),
1662 getMDString(Record[2 + HasTag]),
1663 getMDOrNull(Record[3 + HasTag]), Record[4 + HasTag],
1664 getDITypeRefOrNull(Record[5 + HasTag]),
1665 Record[6 + HasTag], Flags, AlignInBits)),
1666 NextMetadataNo);
1667 NextMetadataNo++;
1668 break;
1669 }
1670 case bitc::METADATA_LABEL: {
1671 if (Record.size() != 5)
1672 return error("Invalid record");
1673
1674 IsDistinct = Record[0] & 1;
1675 MetadataList.assignValue(
1676 GET_OR_DISTINCT(DILabel,
1677 (Context, getMDOrNull(Record[1]),
1678 getMDString(Record[2]),
1679 getMDOrNull(Record[3]), Record[4])),
1680 NextMetadataNo);
1681 NextMetadataNo++;
1682 break;
1683 }
1684 case bitc::METADATA_EXPRESSION: {
1685 if (Record.size() < 1)
1686 return error("Invalid record");
1687
1688 IsDistinct = Record[0] & 1;
1689 uint64_t Version = Record[0] >> 1;
1690 auto Elts = MutableArrayRef<uint64_t>(Record).slice(1);
1691
1692 SmallVector<uint64_t, 6> Buffer;
1693 if (Error Err = upgradeDIExpression(Version, Elts, Buffer))
1694 return Err;
1695
1696 MetadataList.assignValue(
1697 GET_OR_DISTINCT(DIExpression, (Context, Elts)), NextMetadataNo);
1698 NextMetadataNo++;
1699 break;
1700 }
1701 case bitc::METADATA_GLOBAL_VAR_EXPR: {
1702 if (Record.size() != 3)
1703 return error("Invalid record");
1704
1705 IsDistinct = Record[0];
1706 Metadata *Expr = getMDOrNull(Record[2]);
1707 if (!Expr)
1708 Expr = DIExpression::get(Context, {});
1709 MetadataList.assignValue(
1710 GET_OR_DISTINCT(DIGlobalVariableExpression,
1711 (Context, getMDOrNull(Record[1]), Expr)),
1712 NextMetadataNo);
1713 NextMetadataNo++;
1714 break;
1715 }
1716 case bitc::METADATA_OBJC_PROPERTY: {
1717 if (Record.size() != 8)
1718 return error("Invalid record");
1719
1720 IsDistinct = Record[0];
1721 MetadataList.assignValue(
1722 GET_OR_DISTINCT(DIObjCProperty,
1723 (Context, getMDString(Record[1]),
1724 getMDOrNull(Record[2]), Record[3],
1725 getMDString(Record[4]), getMDString(Record[5]),
1726 Record[6], getDITypeRefOrNull(Record[7]))),
1727 NextMetadataNo);
1728 NextMetadataNo++;
1729 break;
1730 }
1731 case bitc::METADATA_IMPORTED_ENTITY: {
1732 if (Record.size() != 6 && Record.size() != 7)
1733 return error("Invalid record");
1734
1735 IsDistinct = Record[0];
1736 bool HasFile = (Record.size() == 7);
1737 MetadataList.assignValue(
1738 GET_OR_DISTINCT(DIImportedEntity,
1739 (Context, Record[1], getMDOrNull(Record[2]),
1740 getDITypeRefOrNull(Record[3]),
1741 HasFile ? getMDOrNull(Record[6]) : nullptr,
1742 HasFile ? Record[4] : 0, getMDString(Record[5]))),
1743 NextMetadataNo);
1744 NextMetadataNo++;
1745 break;
1746 }
1747 case bitc::METADATA_STRING_OLD: {
1748 std::string String(Record.begin(), Record.end());
1749
1750 // Test for upgrading !llvm.loop.
1751 HasSeenOldLoopTags |= mayBeOldLoopAttachmentTag(String);
1752 ++NumMDStringLoaded;
1753 Metadata *MD = MDString::get(Context, String);
1754 MetadataList.assignValue(MD, NextMetadataNo);
1755 NextMetadataNo++;
1756 break;
1757 }
1758 case bitc::METADATA_STRINGS: {
1759 auto CreateNextMDString = [&](StringRef Str) {
1760 ++NumMDStringLoaded;
1761 MetadataList.assignValue(MDString::get(Context, Str), NextMetadataNo);
1762 NextMetadataNo++;
1763 };
1764 if (Error Err = parseMetadataStrings(Record, Blob, CreateNextMDString))
1765 return Err;
1766 break;
1767 }
1768 case bitc::METADATA_GLOBAL_DECL_ATTACHMENT: {
1769 if (Record.size() % 2 == 0)
1770 return error("Invalid record");
1771 unsigned ValueID = Record[0];
1772 if (ValueID >= ValueList.size())
1773 return error("Invalid record");
1774 if (auto *GO = dyn_cast<GlobalObject>(ValueList[ValueID]))
1775 if (Error Err = parseGlobalObjectAttachment(
1776 *GO, ArrayRef<uint64_t>(Record).slice(1)))
1777 return Err;
1778 break;
1779 }
1780 case bitc::METADATA_KIND: {
1781 // Support older bitcode files that had METADATA_KIND records in a
1782 // block with METADATA_BLOCK_ID.
1783 if (Error Err = parseMetadataKindRecord(Record))
1784 return Err;
1785 break;
1786 }
1787 }
1788 return Error::success();
1789#undef GET_OR_DISTINCT
1790}
1791
1792Error MetadataLoader::MetadataLoaderImpl::parseMetadataStrings(
1793 ArrayRef<uint64_t> Record, StringRef Blob,
1794 function_ref<void(StringRef)> CallBack) {
1795 // All the MDStrings in the block are emitted together in a single
1796 // record. The strings are concatenated and stored in a blob along with
1797 // their sizes.
1798 if (Record.size() != 2)
1799 return error("Invalid record: metadata strings layout");
1800
1801 unsigned NumStrings = Record[0];
1802 unsigned StringsOffset = Record[1];
1803 if (!NumStrings)
1804 return error("Invalid record: metadata strings with no strings");
1805 if (StringsOffset > Blob.size())
1806 return error("Invalid record: metadata strings corrupt offset");
1807
1808 StringRef Lengths = Blob.slice(0, StringsOffset);
1809 SimpleBitstreamCursor R(Lengths);
1810
1811 StringRef Strings = Blob.drop_front(StringsOffset);
1812 do {
1813 if (R.AtEndOfStream())
1814 return error("Invalid record: metadata strings bad length");
1815
1816 unsigned Size = R.ReadVBR(6);
1817 if (Strings.size() < Size)
1818 return error("Invalid record: metadata strings truncated chars");
1819
1820 CallBack(Strings.slice(0, Size));
1821 Strings = Strings.drop_front(Size);
1822 } while (--NumStrings);
1823
1824 return Error::success();
1825}
1826
1827Error MetadataLoader::MetadataLoaderImpl::parseGlobalObjectAttachment(
1828 GlobalObject &GO, ArrayRef<uint64_t> Record) {
1829 assert(Record.size() % 2 == 0)((Record.size() % 2 == 0) ? static_cast<void> (0) : __assert_fail
("Record.size() % 2 == 0", "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 1829, __PRETTY_FUNCTION__))
;
1830 for (unsigned I = 0, E = Record.size(); I != E; I += 2) {
1831 auto K = MDKindMap.find(Record[I]);
1832 if (K == MDKindMap.end())
1833 return error("Invalid ID");
1834 MDNode *MD = MetadataList.getMDNodeFwdRefOrNull(Record[I + 1]);
1835 if (!MD)
1836 return error("Invalid metadata attachment");
1837 GO.addMetadata(K->second, *MD);
1838 }
1839 return Error::success();
1840}
1841
1842/// Parse metadata attachments.
1843Error MetadataLoader::MetadataLoaderImpl::parseMetadataAttachment(
1844 Function &F, const SmallVectorImpl<Instruction *> &InstructionList) {
1845 if (Stream.EnterSubBlock(bitc::METADATA_ATTACHMENT_ID))
2
Assuming the condition is true
3
Taking true branch
1846 return error("Invalid record");
4
Calling 'error'
1847
1848 SmallVector<uint64_t, 64> Record;
1849 PlaceholderQueue Placeholders;
1850
1851 while (true) {
1852 BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1853
1854 switch (Entry.Kind) {
1855 case BitstreamEntry::SubBlock: // Handled for us already.
1856 case BitstreamEntry::Error:
1857 return error("Malformed block");
1858 case BitstreamEntry::EndBlock:
1859 resolveForwardRefsAndPlaceholders(Placeholders);
1860 return Error::success();
1861 case BitstreamEntry::Record:
1862 // The interesting case.
1863 break;
1864 }
1865
1866 // Read a metadata attachment record.
1867 Record.clear();
1868 ++NumMDRecordLoaded;
1869 switch (Stream.readRecord(Entry.ID, Record)) {
1870 default: // Default behavior: ignore.
1871 break;
1872 case bitc::METADATA_ATTACHMENT: {
1873 unsigned RecordLength = Record.size();
1874 if (Record.empty())
1875 return error("Invalid record");
1876 if (RecordLength % 2 == 0) {
1877 // A function attachment.
1878 if (Error Err = parseGlobalObjectAttachment(F, Record))
1879 return Err;
1880 continue;
1881 }
1882
1883 // An instruction attachment.
1884 Instruction *Inst = InstructionList[Record[0]];
1885 for (unsigned i = 1; i != RecordLength; i = i + 2) {
1886 unsigned Kind = Record[i];
1887 DenseMap<unsigned, unsigned>::iterator I = MDKindMap.find(Kind);
1888 if (I == MDKindMap.end())
1889 return error("Invalid ID");
1890 if (I->second == LLVMContext::MD_tbaa && StripTBAA)
1891 continue;
1892
1893 auto Idx = Record[i + 1];
1894 if (Idx < (MDStringRef.size() + GlobalMetadataBitPosIndex.size()) &&
1895 !MetadataList.lookup(Idx)) {
1896 // Load the attachment if it is in the lazy-loadable range and hasn't
1897 // been loaded yet.
1898 lazyLoadOneMetadata(Idx, Placeholders);
1899 resolveForwardRefsAndPlaceholders(Placeholders);
1900 }
1901
1902 Metadata *Node = MetadataList.getMetadataFwdRef(Idx);
1903 if (isa<LocalAsMetadata>(Node))
1904 // Drop the attachment. This used to be legal, but there's no
1905 // upgrade path.
1906 break;
1907 MDNode *MD = dyn_cast_or_null<MDNode>(Node);
1908 if (!MD)
1909 return error("Invalid metadata attachment");
1910
1911 if (HasSeenOldLoopTags && I->second == LLVMContext::MD_loop)
1912 MD = upgradeInstructionLoopAttachment(*MD);
1913
1914 if (I->second == LLVMContext::MD_tbaa) {
1915 assert(!MD->isTemporary() && "should load MDs before attachments")((!MD->isTemporary() && "should load MDs before attachments"
) ? static_cast<void> (0) : __assert_fail ("!MD->isTemporary() && \"should load MDs before attachments\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Bitcode/Reader/MetadataLoader.cpp"
, 1915, __PRETTY_FUNCTION__))
;
1916 MD = UpgradeTBAANode(*MD);
1917 }
1918 Inst->setMetadata(I->second, MD);
1919 }
1920 break;
1921 }
1922 }
1923 }
1924}
1925
1926/// Parse a single METADATA_KIND record, inserting result in MDKindMap.
1927Error MetadataLoader::MetadataLoaderImpl::parseMetadataKindRecord(
1928 SmallVectorImpl<uint64_t> &Record) {
1929 if (Record.size() < 2)
1930 return error("Invalid record");
1931
1932 unsigned Kind = Record[0];
1933 SmallString<8> Name(Record.begin() + 1, Record.end());
1934
1935 unsigned NewKind = TheModule.getMDKindID(Name.str());
1936 if (!MDKindMap.insert(std::make_pair(Kind, NewKind)).second)
1937 return error("Conflicting METADATA_KIND records");
1938 return Error::success();
1939}
1940
1941/// Parse the metadata kinds out of the METADATA_KIND_BLOCK.
1942Error MetadataLoader::MetadataLoaderImpl::parseMetadataKinds() {
1943 if (Stream.EnterSubBlock(bitc::METADATA_KIND_BLOCK_ID))
1944 return error("Invalid record");
1945
1946 SmallVector<uint64_t, 64> Record;
1947
1948 // Read all the records.
1949 while (true) {
1950 BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
1951
1952 switch (Entry.Kind) {
1953 case BitstreamEntry::SubBlock: // Handled for us already.
1954 case BitstreamEntry::Error:
1955 return error("Malformed block");
1956 case BitstreamEntry::EndBlock:
1957 return Error::success();
1958 case BitstreamEntry::Record:
1959 // The interesting case.
1960 break;
1961 }
1962
1963 // Read a record.
1964 Record.clear();
1965 ++NumMDRecordLoaded;
1966 unsigned Code = Stream.readRecord(Entry.ID, Record);
1967 switch (Code) {
1968 default: // Default behavior: ignore.
1969 break;
1970 case bitc::METADATA_KIND: {
1971 if (Error Err = parseMetadataKindRecord(Record))
1972 return Err;
1973 break;
1974 }
1975 }
1976 }
1977}
1978
1979MetadataLoader &MetadataLoader::operator=(MetadataLoader &&RHS) {
1980 Pimpl = std::move(RHS.Pimpl);
1981 return *this;
1982}
1983MetadataLoader::MetadataLoader(MetadataLoader &&RHS)
1984 : Pimpl(std::move(RHS.Pimpl)) {}
1985
1986MetadataLoader::~MetadataLoader() = default;
1987MetadataLoader::MetadataLoader(BitstreamCursor &Stream, Module &TheModule,
1988 BitcodeReaderValueList &ValueList,
1989 bool IsImporting,
1990 std::function<Type *(unsigned)> getTypeByID)
1991 : Pimpl(llvm::make_unique<MetadataLoaderImpl>(
1992 Stream, TheModule, ValueList, std::move(getTypeByID), IsImporting)) {}
1993
1994Error MetadataLoader::parseMetadata(bool ModuleLevel) {
1995 return Pimpl->parseMetadata(ModuleLevel);
1996}
1997
1998bool MetadataLoader::hasFwdRefs() const { return Pimpl->hasFwdRefs(); }
1999
2000/// Return the given metadata, creating a replaceable forward reference if
2001/// necessary.
2002Metadata *MetadataLoader::getMetadataFwdRefOrLoad(unsigned Idx) {
2003 return Pimpl->getMetadataFwdRefOrLoad(Idx);
2004}
2005
2006MDNode *MetadataLoader::getMDNodeFwdRefOrNull(unsigned Idx) {
2007 return Pimpl->getMDNodeFwdRefOrNull(Idx);
2008}
2009
2010DISubprogram *MetadataLoader::lookupSubprogramForFunction(Function *F) {
2011 return Pimpl->lookupSubprogramForFunction(F);
2012}
2013
2014Error MetadataLoader::parseMetadataAttachment(
2015 Function &F, const SmallVectorImpl<Instruction *> &InstructionList) {
2016 return Pimpl->parseMetadataAttachment(F, InstructionList);
1
Calling 'MetadataLoaderImpl::parseMetadataAttachment'
2017}
2018
2019Error MetadataLoader::parseMetadataKinds() {
2020 return Pimpl->parseMetadataKinds();
2021}
2022
2023void MetadataLoader::setStripTBAA(bool StripTBAA) {
2024 return Pimpl->setStripTBAA(StripTBAA);
2025}
2026
2027bool MetadataLoader::isStrippingTBAA() { return Pimpl->isStrippingTBAA(); }
2028
2029unsigned MetadataLoader::size() const { return Pimpl->size(); }
2030void MetadataLoader::shrinkTo(unsigned N) { return Pimpl->shrinkTo(N); }
2031
2032void MetadataLoader::upgradeDebugIntrinsics(Function &F) {
2033 return Pimpl->upgradeDebugIntrinsics(F);
2034}

/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h

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

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