Bug Summary

File:lib/ProfileData/Coverage/CoverageMappingReader.cpp
Warning:line 231, column 5
The right operand of '+' is a garbage value

Annotated Source Code

[?] Use j/k keys for keyboard navigation

/build/llvm-toolchain-snapshot-6.0~svn321639/lib/ProfileData/Coverage/CoverageMappingReader.cpp

1//===- CoverageMappingReader.cpp - Code coverage mapping reader -----------===//
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 support for reading coverage mapping data for
11// instrumentation based coverage.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/ADT/Triple.h"
22#include "llvm/Object/Binary.h"
23#include "llvm/Object/Error.h"
24#include "llvm/Object/MachOUniversal.h"
25#include "llvm/Object/ObjectFile.h"
26#include "llvm/ProfileData/InstrProf.h"
27#include "llvm/Support/Casting.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/Endian.h"
30#include "llvm/Support/Error.h"
31#include "llvm/Support/ErrorHandling.h"
32#include "llvm/Support/LEB128.h"
33#include "llvm/Support/MathExtras.h"
34#include "llvm/Support/raw_ostream.h"
35#include <vector>
36
37using namespace llvm;
38using namespace coverage;
39using namespace object;
40
41#define DEBUG_TYPE"coverage-mapping" "coverage-mapping"
42
43void CoverageMappingIterator::increment() {
44 if (ReadErr != coveragemap_error::success)
45 return;
46
47 // Check if all the records were read or if an error occurred while reading
48 // the next record.
49 if (auto E = Reader->readNextRecord(Record))
50 handleAllErrors(std::move(E), [&](const CoverageMapError &CME) {
51 if (CME.get() == coveragemap_error::eof)
52 *this = CoverageMappingIterator();
53 else
54 ReadErr = CME.get();
55 });
56}
57
58Error RawCoverageReader::readULEB128(uint64_t &Result) {
59 if (Data.empty())
39
Assuming the condition is true
40
Taking true branch
60 return make_error<CoverageMapError>(coveragemap_error::truncated);
41
Calling 'make_error'
48
Returning from 'make_error'
61 unsigned N = 0;
62 Result = decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
63 if (N > Data.size())
64 return make_error<CoverageMapError>(coveragemap_error::malformed);
65 Data = Data.substr(N);
66 return Error::success();
67}
68
69Error RawCoverageReader::readIntMax(uint64_t &Result, uint64_t MaxPlus1) {
70 if (auto Err = readULEB128(Result))
38
Calling 'RawCoverageReader::readULEB128'
49
Returning from 'RawCoverageReader::readULEB128'
50
Calling move constructor for 'Error'
74
Returning from move constructor for 'Error'
75
Calling 'Error::operator bool'
84
Returning from 'Error::operator bool'
85
Taking true branch
71 return Err;
86
Calling '~Error'
93
Returning from '~Error'
72 if (Result >= MaxPlus1)
73 return make_error<CoverageMapError>(coveragemap_error::malformed);
74 return Error::success();
75}
76
77Error RawCoverageReader::readSize(uint64_t &Result) {
78 if (auto Err = readULEB128(Result))
79 return Err;
80 // Sanity check the number.
81 if (Result > Data.size())
82 return make_error<CoverageMapError>(coveragemap_error::malformed);
83 return Error::success();
84}
85
86Error RawCoverageReader::readString(StringRef &Result) {
87 uint64_t Length;
88 if (auto Err = readSize(Length))
89 return Err;
90 Result = Data.substr(0, Length);
91 Data = Data.substr(Length);
92 return Error::success();
93}
94
95Error RawCoverageFilenamesReader::read() {
96 uint64_t NumFilenames;
97 if (auto Err = readSize(NumFilenames))
98 return Err;
99 for (size_t I = 0; I < NumFilenames; ++I) {
100 StringRef Filename;
101 if (auto Err = readString(Filename))
102 return Err;
103 Filenames.push_back(Filename);
104 }
105 return Error::success();
106}
107
108Error RawCoverageMappingReader::decodeCounter(unsigned Value, Counter &C) {
109 auto Tag = Value & Counter::EncodingTagMask;
110 switch (Tag) {
111 case Counter::Zero:
112 C = Counter::getZero();
113 return Error::success();
114 case Counter::CounterValueReference:
115 C = Counter::getCounter(Value >> Counter::EncodingTagBits);
116 return Error::success();
117 default:
118 break;
119 }
120 Tag -= Counter::Expression;
121 switch (Tag) {
122 case CounterExpression::Subtract:
123 case CounterExpression::Add: {
124 auto ID = Value >> Counter::EncodingTagBits;
125 if (ID >= Expressions.size())
126 return make_error<CoverageMapError>(coveragemap_error::malformed);
127 Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
128 C = Counter::getExpression(ID);
129 break;
130 }
131 default:
132 return make_error<CoverageMapError>(coveragemap_error::malformed);
133 }
134 return Error::success();
135}
136
137Error RawCoverageMappingReader::readCounter(Counter &C) {
138 uint64_t EncodedCounter;
139 if (auto Err =
140 readIntMax(EncodedCounter, std::numeric_limits<unsigned>::max()))
141 return Err;
142 if (auto Err = decodeCounter(EncodedCounter, C))
143 return Err;
144 return Error::success();
145}
146
147static const unsigned EncodingExpansionRegionBit = 1
148 << Counter::EncodingTagBits;
149
150/// \brief Read the sub-array of regions for the given inferred file id.
151/// \param NumFileIDs the number of file ids that are defined for this
152/// function.
153Error RawCoverageMappingReader::readMappingRegionsSubArray(
154 std::vector<CounterMappingRegion> &MappingRegions, unsigned InferredFileID,
155 size_t NumFileIDs) {
156 uint64_t NumRegions;
157 if (auto Err = readSize(NumRegions))
22
Taking false branch
158 return Err;
159 unsigned LineStart = 0;
160 for (size_t I = 0; I < NumRegions; ++I) {
23
Assuming 'I' is < 'NumRegions'
24
Loop condition is true. Entering loop body
161 Counter C;
162 CounterMappingRegion::RegionKind Kind = CounterMappingRegion::CodeRegion;
163
164 // Read the combined counter + region kind.
165 uint64_t EncodedCounterAndRegion;
166 if (auto Err = readIntMax(EncodedCounterAndRegion,
25
Taking false branch
167 std::numeric_limits<unsigned>::max()))
168 return Err;
169 unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
170 uint64_t ExpandedFileID = 0;
171 if (Tag != Counter::Zero) {
26
Assuming 'Tag' is equal to Zero
27
Taking false branch
172 if (auto Err = decodeCounter(EncodedCounterAndRegion, C))
173 return Err;
174 } else {
175 // Is it an expansion region?
176 if (EncodedCounterAndRegion & EncodingExpansionRegionBit) {
28
Assuming the condition is false
29
Taking false branch
177 Kind = CounterMappingRegion::ExpansionRegion;
178 ExpandedFileID = EncodedCounterAndRegion >>
179 Counter::EncodingCounterTagAndExpansionRegionTagBits;
180 if (ExpandedFileID >= NumFileIDs)
181 return make_error<CoverageMapError>(coveragemap_error::malformed);
182 } else {
183 switch (EncodedCounterAndRegion >>
30
Control jumps to 'case SkippedRegion:' at line 188
184 Counter::EncodingCounterTagAndExpansionRegionTagBits) {
185 case CounterMappingRegion::CodeRegion:
186 // Don't do anything when we have a code region with a zero counter.
187 break;
188 case CounterMappingRegion::SkippedRegion:
189 Kind = CounterMappingRegion::SkippedRegion;
190 break;
31
Execution continues on line 198
191 default:
192 return make_error<CoverageMapError>(coveragemap_error::malformed);
193 }
194 }
195 }
196
197 // Read the source range.
198 uint64_t LineStartDelta, ColumnStart, NumLines, ColumnEnd;
32
'NumLines' declared without an initial value
199 if (auto Err =
33
Taking false branch
200 readIntMax(LineStartDelta, std::numeric_limits<unsigned>::max()))
201 return Err;
202 if (auto Err = readULEB128(ColumnStart))
34
Taking false branch
203 return Err;
204 if (ColumnStart > std::numeric_limits<unsigned>::max())
35
Assuming the condition is false
36
Taking false branch
205 return make_error<CoverageMapError>(coveragemap_error::malformed);
206 if (auto Err = readIntMax(NumLines, std::numeric_limits<unsigned>::max()))
37
Calling 'RawCoverageReader::readIntMax'
94
Returning from 'RawCoverageReader::readIntMax'
95
Taking false branch
207 return Err;
208 if (auto Err = readIntMax(ColumnEnd, std::numeric_limits<unsigned>::max()))
96
Taking false branch
209 return Err;
210 LineStart += LineStartDelta;
211
212 // If the high bit of ColumnEnd is set, this is a gap region.
213 if (ColumnEnd & (1U << 31)) {
97
Assuming the condition is false
98
Taking false branch
214 Kind = CounterMappingRegion::GapRegion;
215 ColumnEnd &= ~(1U << 31);
216 }
217
218 // Adjust the column locations for the empty regions that are supposed to
219 // cover whole lines. Those regions should be encoded with the
220 // column range (1 -> std::numeric_limits<unsigned>::max()), but because
221 // the encoded std::numeric_limits<unsigned>::max() is several bytes long,
222 // we set the column range to (0 -> 0) to ensure that the column start and
223 // column end take up one byte each.
224 // The std::numeric_limits<unsigned>::max() is used to represent a column
225 // position at the end of the line without knowing the length of that line.
226 if (ColumnStart == 0 && ColumnEnd == 0) {
227 ColumnStart = 1;
228 ColumnEnd = std::numeric_limits<unsigned>::max();
229 }
230
231 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
99
Within the expansion of the macro 'DEBUG':
a
Assuming 'DebugFlag' is not equal to 0
b
Assuming the condition is true
c
The right operand of '+' is a garbage value
232 dbgs() << "Counter in file " << InferredFileID << " " << LineStart << ":"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
233 << ColumnStart << " -> " << (LineStart + NumLines) << ":"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
234 << ColumnEnd << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
235 if (Kind == CounterMappingRegion::ExpansionRegion)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
236 dbgs() << "Expands to file " << ExpandedFileID;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
237 elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
238 CounterMappingContext(Expressions).dump(C, dbgs());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
239 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
240 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { { dbgs() << "Counter in file " <<
InferredFileID << " " << LineStart << ":" <<
ColumnStart << " -> " << (LineStart + NumLines
) << ":" << ColumnEnd << ", "; if (Kind == CounterMappingRegion
::ExpansionRegion) dbgs() << "Expands to file " <<
ExpandedFileID; else CounterMappingContext(Expressions).dump
(C, dbgs()); dbgs() << "\n"; }; } } while (false)
;
241
242 auto CMR = CounterMappingRegion(C, InferredFileID, ExpandedFileID,
243 LineStart, ColumnStart,
244 LineStart + NumLines, ColumnEnd, Kind);
245 if (CMR.startLoc() > CMR.endLoc())
246 return make_error<CoverageMapError>(coveragemap_error::malformed);
247 MappingRegions.push_back(CMR);
248 }
249 return Error::success();
250}
251
252Error RawCoverageMappingReader::read() {
253 // Read the virtual file mapping.
254 SmallVector<unsigned, 8> VirtualFileMapping;
255 uint64_t NumFileMappings;
256 if (auto Err = readSize(NumFileMappings))
3
Taking false branch
257 return Err;
258 for (size_t I = 0; I < NumFileMappings; ++I) {
4
Assuming 'I' is >= 'NumFileMappings'
5
Loop condition is false. Execution continues on line 266
259 uint64_t FilenameIndex;
260 if (auto Err = readIntMax(FilenameIndex, TranslationUnitFilenames.size()))
261 return Err;
262 VirtualFileMapping.push_back(FilenameIndex);
263 }
264
265 // Construct the files using unique filenames and virtual file mapping.
266 for (auto I : VirtualFileMapping) {
6
Assuming '__begin' is equal to '__end'
267 Filenames.push_back(TranslationUnitFilenames[I]);
268 }
269
270 // Read the expressions.
271 uint64_t NumExpressions;
272 if (auto Err = readSize(NumExpressions))
7
Taking false branch
273 return Err;
274 // Create an array of dummy expressions that get the proper counters
275 // when the expressions are read, and the proper kinds when the counters
276 // are decoded.
277 Expressions.resize(
278 NumExpressions,
279 CounterExpression(CounterExpression::Subtract, Counter(), Counter()));
280 for (size_t I = 0; I < NumExpressions; ++I) {
8
Assuming 'I' is >= 'NumExpressions'
9
Loop condition is false. Execution continues on line 288
281 if (auto Err = readCounter(Expressions[I].LHS))
282 return Err;
283 if (auto Err = readCounter(Expressions[I].RHS))
284 return Err;
285 }
286
287 // Read the mapping regions sub-arrays.
288 for (unsigned InferredFileID = 0, S = VirtualFileMapping.size();
11
Loop condition is true. Entering loop body
14
Loop condition is true. Entering loop body
17
Loop condition is true. Entering loop body
20
Loop condition is true. Entering loop body
289 InferredFileID < S; ++InferredFileID) {
10
Assuming 'InferredFileID' is < 'S'
13
Assuming 'InferredFileID' is < 'S'
16
Assuming 'InferredFileID' is < 'S'
19
Assuming 'InferredFileID' is < 'S'
290 if (auto Err = readMappingRegionsSubArray(MappingRegions, InferredFileID,
12
Taking false branch
15
Taking false branch
18
Taking false branch
21
Calling 'RawCoverageMappingReader::readMappingRegionsSubArray'
291 VirtualFileMapping.size()))
292 return Err;
293 }
294
295 // Set the counters for the expansion regions.
296 // i.e. Counter of expansion region = counter of the first region
297 // from the expanded file.
298 // Perform multiple passes to correctly propagate the counters through
299 // all the nested expansion regions.
300 SmallVector<CounterMappingRegion *, 8> FileIDExpansionRegionMapping;
301 FileIDExpansionRegionMapping.resize(VirtualFileMapping.size(), nullptr);
302 for (unsigned Pass = 1, S = VirtualFileMapping.size(); Pass < S; ++Pass) {
303 for (auto &R : MappingRegions) {
304 if (R.Kind != CounterMappingRegion::ExpansionRegion)
305 continue;
306 assert(!FileIDExpansionRegionMapping[R.ExpandedFileID])(static_cast <bool> (!FileIDExpansionRegionMapping[R.ExpandedFileID
]) ? void (0) : __assert_fail ("!FileIDExpansionRegionMapping[R.ExpandedFileID]"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/ProfileData/Coverage/CoverageMappingReader.cpp"
, 306, __extension__ __PRETTY_FUNCTION__))
;
307 FileIDExpansionRegionMapping[R.ExpandedFileID] = &R;
308 }
309 for (auto &R : MappingRegions) {
310 if (FileIDExpansionRegionMapping[R.FileID]) {
311 FileIDExpansionRegionMapping[R.FileID]->Count = R.Count;
312 FileIDExpansionRegionMapping[R.FileID] = nullptr;
313 }
314 }
315 }
316
317 return Error::success();
318}
319
320Expected<bool> RawCoverageMappingDummyChecker::isDummy() {
321 // A dummy coverage mapping data consists of just one region with zero count.
322 uint64_t NumFileMappings;
323 if (Error Err = readSize(NumFileMappings))
324 return std::move(Err);
325 if (NumFileMappings != 1)
326 return false;
327 // We don't expect any specific value for the filename index, just skip it.
328 uint64_t FilenameIndex;
329 if (Error Err =
330 readIntMax(FilenameIndex, std::numeric_limits<unsigned>::max()))
331 return std::move(Err);
332 uint64_t NumExpressions;
333 if (Error Err = readSize(NumExpressions))
334 return std::move(Err);
335 if (NumExpressions != 0)
336 return false;
337 uint64_t NumRegions;
338 if (Error Err = readSize(NumRegions))
339 return std::move(Err);
340 if (NumRegions != 1)
341 return false;
342 uint64_t EncodedCounterAndRegion;
343 if (Error Err = readIntMax(EncodedCounterAndRegion,
344 std::numeric_limits<unsigned>::max()))
345 return std::move(Err);
346 unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
347 return Tag == Counter::Zero;
348}
349
350Error InstrProfSymtab::create(SectionRef &Section) {
351 if (auto EC = Section.getContents(Data))
352 return errorCodeToError(EC);
353 Address = Section.getAddress();
354 return Error::success();
355}
356
357StringRef InstrProfSymtab::getFuncName(uint64_t Pointer, size_t Size) {
358 if (Pointer < Address)
359 return StringRef();
360 auto Offset = Pointer - Address;
361 if (Offset + Size > Data.size())
362 return StringRef();
363 return Data.substr(Pointer - Address, Size);
364}
365
366// Check if the mapping data is a dummy, i.e. is emitted for an unused function.
367static Expected<bool> isCoverageMappingDummy(uint64_t Hash, StringRef Mapping) {
368 // The hash value of dummy mapping records is always zero.
369 if (Hash)
370 return false;
371 return RawCoverageMappingDummyChecker(Mapping).isDummy();
372}
373
374namespace {
375
376struct CovMapFuncRecordReader {
377 virtual ~CovMapFuncRecordReader() = default;
378
379 // The interface to read coverage mapping function records for a module.
380 //
381 // \p Buf points to the buffer containing the \c CovHeader of the coverage
382 // mapping data associated with the module.
383 //
384 // Returns a pointer to the next \c CovHeader if it exists, or a pointer
385 // greater than \p End if not.
386 virtual Expected<const char *> readFunctionRecords(const char *Buf,
387 const char *End) = 0;
388
389 template <class IntPtrT, support::endianness Endian>
390 static Expected<std::unique_ptr<CovMapFuncRecordReader>>
391 get(CovMapVersion Version, InstrProfSymtab &P,
392 std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
393 std::vector<StringRef> &F);
394};
395
396// A class for reading coverage mapping function records for a module.
397template <CovMapVersion Version, class IntPtrT, support::endianness Endian>
398class VersionedCovMapFuncRecordReader : public CovMapFuncRecordReader {
399 using FuncRecordType =
400 typename CovMapTraits<Version, IntPtrT>::CovMapFuncRecordType;
401 using NameRefType = typename CovMapTraits<Version, IntPtrT>::NameRefType;
402
403 // Maps function's name references to the indexes of their records
404 // in \c Records.
405 DenseMap<NameRefType, size_t> FunctionRecords;
406 InstrProfSymtab &ProfileNames;
407 std::vector<StringRef> &Filenames;
408 std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records;
409
410 // Add the record to the collection if we don't already have a record that
411 // points to the same function name. This is useful to ignore the redundant
412 // records for the functions with ODR linkage.
413 // In addition, prefer records with real coverage mapping data to dummy
414 // records, which were emitted for inline functions which were seen but
415 // not used in the corresponding translation unit.
416 Error insertFunctionRecordIfNeeded(const FuncRecordType *CFR,
417 StringRef Mapping, size_t FilenamesBegin) {
418 uint64_t FuncHash = CFR->template getFuncHash<Endian>();
419 NameRefType NameRef = CFR->template getFuncNameRef<Endian>();
420 auto InsertResult =
421 FunctionRecords.insert(std::make_pair(NameRef, Records.size()));
422 if (InsertResult.second) {
423 StringRef FuncName;
424 if (Error Err = CFR->template getFuncName<Endian>(ProfileNames, FuncName))
425 return Err;
426 if (FuncName.empty())
427 return make_error<InstrProfError>(instrprof_error::malformed);
428 Records.emplace_back(Version, FuncName, FuncHash, Mapping, FilenamesBegin,
429 Filenames.size() - FilenamesBegin);
430 return Error::success();
431 }
432 // Update the existing record if it's a dummy and the new record is real.
433 size_t OldRecordIndex = InsertResult.first->second;
434 BinaryCoverageReader::ProfileMappingRecord &OldRecord =
435 Records[OldRecordIndex];
436 Expected<bool> OldIsDummyExpected = isCoverageMappingDummy(
437 OldRecord.FunctionHash, OldRecord.CoverageMapping);
438 if (Error Err = OldIsDummyExpected.takeError())
439 return Err;
440 if (!*OldIsDummyExpected)
441 return Error::success();
442 Expected<bool> NewIsDummyExpected =
443 isCoverageMappingDummy(FuncHash, Mapping);
444 if (Error Err = NewIsDummyExpected.takeError())
445 return Err;
446 if (*NewIsDummyExpected)
447 return Error::success();
448 OldRecord.FunctionHash = FuncHash;
449 OldRecord.CoverageMapping = Mapping;
450 OldRecord.FilenamesBegin = FilenamesBegin;
451 OldRecord.FilenamesSize = Filenames.size() - FilenamesBegin;
452 return Error::success();
453 }
454
455public:
456 VersionedCovMapFuncRecordReader(
457 InstrProfSymtab &P,
458 std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
459 std::vector<StringRef> &F)
460 : ProfileNames(P), Filenames(F), Records(R) {}
461
462 ~VersionedCovMapFuncRecordReader() override = default;
463
464 Expected<const char *> readFunctionRecords(const char *Buf,
465 const char *End) override {
466 using namespace support;
467
468 if (Buf + sizeof(CovMapHeader) > End)
469 return make_error<CoverageMapError>(coveragemap_error::malformed);
470 auto CovHeader = reinterpret_cast<const CovMapHeader *>(Buf);
471 uint32_t NRecords = CovHeader->getNRecords<Endian>();
472 uint32_t FilenamesSize = CovHeader->getFilenamesSize<Endian>();
473 uint32_t CoverageSize = CovHeader->getCoverageSize<Endian>();
474 assert((CovMapVersion)CovHeader->getVersion<Endian>() == Version)(static_cast <bool> ((CovMapVersion)CovHeader->getVersion
<Endian>() == Version) ? void (0) : __assert_fail ("(CovMapVersion)CovHeader->getVersion<Endian>() == Version"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/ProfileData/Coverage/CoverageMappingReader.cpp"
, 474, __extension__ __PRETTY_FUNCTION__))
;
475 Buf = reinterpret_cast<const char *>(CovHeader + 1);
476
477 // Skip past the function records, saving the start and end for later.
478 const char *FunBuf = Buf;
479 Buf += NRecords * sizeof(FuncRecordType);
480 const char *FunEnd = Buf;
481
482 // Get the filenames.
483 if (Buf + FilenamesSize > End)
484 return make_error<CoverageMapError>(coveragemap_error::malformed);
485 size_t FilenamesBegin = Filenames.size();
486 RawCoverageFilenamesReader Reader(StringRef(Buf, FilenamesSize), Filenames);
487 if (auto Err = Reader.read())
488 return std::move(Err);
489 Buf += FilenamesSize;
490
491 // We'll read the coverage mapping records in the loop below.
492 const char *CovBuf = Buf;
493 Buf += CoverageSize;
494 const char *CovEnd = Buf;
495
496 if (Buf > End)
497 return make_error<CoverageMapError>(coveragemap_error::malformed);
498 // Each coverage map has an alignment of 8, so we need to adjust alignment
499 // before reading the next map.
500 Buf += alignmentAdjustment(Buf, 8);
501
502 auto CFR = reinterpret_cast<const FuncRecordType *>(FunBuf);
503 while ((const char *)CFR < FunEnd) {
504 // Read the function information
505 uint32_t DataSize = CFR->template getDataSize<Endian>();
506
507 // Now use that to read the coverage data.
508 if (CovBuf + DataSize > CovEnd)
509 return make_error<CoverageMapError>(coveragemap_error::malformed);
510 auto Mapping = StringRef(CovBuf, DataSize);
511 CovBuf += DataSize;
512
513 if (Error Err =
514 insertFunctionRecordIfNeeded(CFR, Mapping, FilenamesBegin))
515 return std::move(Err);
516 CFR++;
517 }
518 return Buf;
519 }
520};
521
522} // end anonymous namespace
523
524template <class IntPtrT, support::endianness Endian>
525Expected<std::unique_ptr<CovMapFuncRecordReader>> CovMapFuncRecordReader::get(
526 CovMapVersion Version, InstrProfSymtab &P,
527 std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
528 std::vector<StringRef> &F) {
529 using namespace coverage;
530
531 switch (Version) {
532 case CovMapVersion::Version1:
533 return llvm::make_unique<VersionedCovMapFuncRecordReader<
534 CovMapVersion::Version1, IntPtrT, Endian>>(P, R, F);
535 case CovMapVersion::Version2:
536 case CovMapVersion::Version3:
537 // Decompress the name data.
538 if (Error E = P.create(P.getNameData()))
539 return std::move(E);
540 if (Version == CovMapVersion::Version2)
541 return llvm::make_unique<VersionedCovMapFuncRecordReader<
542 CovMapVersion::Version2, IntPtrT, Endian>>(P, R, F);
543 else
544 return llvm::make_unique<VersionedCovMapFuncRecordReader<
545 CovMapVersion::Version3, IntPtrT, Endian>>(P, R, F);
546 }
547 llvm_unreachable("Unsupported version")::llvm::llvm_unreachable_internal("Unsupported version", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/ProfileData/Coverage/CoverageMappingReader.cpp"
, 547)
;
548}
549
550template <typename T, support::endianness Endian>
551static Error readCoverageMappingData(
552 InstrProfSymtab &ProfileNames, StringRef Data,
553 std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records,
554 std::vector<StringRef> &Filenames) {
555 using namespace coverage;
556
557 // Read the records in the coverage data section.
558 auto CovHeader =
559 reinterpret_cast<const CovMapHeader *>(Data.data());
560 CovMapVersion Version = (CovMapVersion)CovHeader->getVersion<Endian>();
561 if (Version > CovMapVersion::CurrentVersion)
562 return make_error<CoverageMapError>(coveragemap_error::unsupported_version);
563 Expected<std::unique_ptr<CovMapFuncRecordReader>> ReaderExpected =
564 CovMapFuncRecordReader::get<T, Endian>(Version, ProfileNames, Records,
565 Filenames);
566 if (Error E = ReaderExpected.takeError())
567 return E;
568 auto Reader = std::move(ReaderExpected.get());
569 for (const char *Buf = Data.data(), *End = Buf + Data.size(); Buf < End;) {
570 auto NextHeaderOrErr = Reader->readFunctionRecords(Buf, End);
571 if (auto E = NextHeaderOrErr.takeError())
572 return E;
573 Buf = NextHeaderOrErr.get();
574 }
575 return Error::success();
576}
577
578static const char *TestingFormatMagic = "llvmcovmtestdata";
579
580static Error loadTestingFormat(StringRef Data, InstrProfSymtab &ProfileNames,
581 StringRef &CoverageMapping,
582 uint8_t &BytesInAddress,
583 support::endianness &Endian) {
584 BytesInAddress = 8;
585 Endian = support::endianness::little;
586
587 Data = Data.substr(StringRef(TestingFormatMagic).size());
588 if (Data.empty())
589 return make_error<CoverageMapError>(coveragemap_error::truncated);
590 unsigned N = 0;
591 auto ProfileNamesSize =
592 decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
593 if (N > Data.size())
594 return make_error<CoverageMapError>(coveragemap_error::malformed);
595 Data = Data.substr(N);
596 if (Data.empty())
597 return make_error<CoverageMapError>(coveragemap_error::truncated);
598 N = 0;
599 uint64_t Address =
600 decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
601 if (N > Data.size())
602 return make_error<CoverageMapError>(coveragemap_error::malformed);
603 Data = Data.substr(N);
604 if (Data.size() < ProfileNamesSize)
605 return make_error<CoverageMapError>(coveragemap_error::malformed);
606 if (Error E = ProfileNames.create(Data.substr(0, ProfileNamesSize), Address))
607 return E;
608 CoverageMapping = Data.substr(ProfileNamesSize);
609 // Skip the padding bytes because coverage map data has an alignment of 8.
610 if (CoverageMapping.empty())
611 return make_error<CoverageMapError>(coveragemap_error::truncated);
612 size_t Pad = alignmentAdjustment(CoverageMapping.data(), 8);
613 if (CoverageMapping.size() < Pad)
614 return make_error<CoverageMapError>(coveragemap_error::malformed);
615 CoverageMapping = CoverageMapping.substr(Pad);
616 return Error::success();
617}
618
619static Expected<SectionRef> lookupSection(ObjectFile &OF, StringRef Name) {
620 StringRef FoundName;
621 for (const auto &Section : OF.sections()) {
622 if (auto EC = Section.getName(FoundName))
623 return errorCodeToError(EC);
624 if (FoundName == Name)
625 return Section;
626 }
627 return make_error<CoverageMapError>(coveragemap_error::no_data_found);
628}
629
630static Error loadBinaryFormat(MemoryBufferRef ObjectBuffer,
631 InstrProfSymtab &ProfileNames,
632 StringRef &CoverageMapping,
633 uint8_t &BytesInAddress,
634 support::endianness &Endian, StringRef Arch) {
635 auto BinOrErr = createBinary(ObjectBuffer);
636 if (!BinOrErr)
637 return BinOrErr.takeError();
638 auto Bin = std::move(BinOrErr.get());
639 std::unique_ptr<ObjectFile> OF;
640 if (auto *Universal = dyn_cast<MachOUniversalBinary>(Bin.get())) {
641 // If we have a universal binary, try to look up the object for the
642 // appropriate architecture.
643 auto ObjectFileOrErr = Universal->getObjectForArch(Arch);
644 if (!ObjectFileOrErr)
645 return ObjectFileOrErr.takeError();
646 OF = std::move(ObjectFileOrErr.get());
647 } else if (isa<ObjectFile>(Bin.get())) {
648 // For any other object file, upcast and take ownership.
649 OF.reset(cast<ObjectFile>(Bin.release()));
650 // If we've asked for a particular arch, make sure they match.
651 if (!Arch.empty() && OF->getArch() != Triple(Arch).getArch())
652 return errorCodeToError(object_error::arch_not_found);
653 } else
654 // We can only handle object files.
655 return make_error<CoverageMapError>(coveragemap_error::malformed);
656
657 // The coverage uses native pointer sizes for the object it's written in.
658 BytesInAddress = OF->getBytesInAddress();
659 Endian = OF->isLittleEndian() ? support::endianness::little
660 : support::endianness::big;
661
662 // Look for the sections that we are interested in.
663 auto ObjFormat = OF->getTripleObjectFormat();
664 auto NamesSection =
665 lookupSection(*OF, getInstrProfSectionName(IPSK_name, ObjFormat,
666 /*AddSegmentInfo=*/false));
667 if (auto E = NamesSection.takeError())
668 return E;
669 auto CoverageSection =
670 lookupSection(*OF, getInstrProfSectionName(IPSK_covmap, ObjFormat,
671 /*AddSegmentInfo=*/false));
672 if (auto E = CoverageSection.takeError())
673 return E;
674
675 // Get the contents of the given sections.
676 if (auto EC = CoverageSection->getContents(CoverageMapping))
677 return errorCodeToError(EC);
678 if (Error E = ProfileNames.create(*NamesSection))
679 return E;
680
681 return Error::success();
682}
683
684Expected<std::unique_ptr<BinaryCoverageReader>>
685BinaryCoverageReader::create(std::unique_ptr<MemoryBuffer> &ObjectBuffer,
686 StringRef Arch) {
687 std::unique_ptr<BinaryCoverageReader> Reader(new BinaryCoverageReader());
688
689 StringRef Coverage;
690 uint8_t BytesInAddress;
691 support::endianness Endian;
692 Error E = Error::success();
693 consumeError(std::move(E));
694 if (ObjectBuffer->getBuffer().startswith(TestingFormatMagic))
695 // This is a special format used for testing.
696 E = loadTestingFormat(ObjectBuffer->getBuffer(), Reader->ProfileNames,
697 Coverage, BytesInAddress, Endian);
698 else
699 E = loadBinaryFormat(ObjectBuffer->getMemBufferRef(), Reader->ProfileNames,
700 Coverage, BytesInAddress, Endian, Arch);
701 if (E)
702 return std::move(E);
703
704 if (BytesInAddress == 4 && Endian == support::endianness::little)
705 E = readCoverageMappingData<uint32_t, support::endianness::little>(
706 Reader->ProfileNames, Coverage, Reader->MappingRecords,
707 Reader->Filenames);
708 else if (BytesInAddress == 4 && Endian == support::endianness::big)
709 E = readCoverageMappingData<uint32_t, support::endianness::big>(
710 Reader->ProfileNames, Coverage, Reader->MappingRecords,
711 Reader->Filenames);
712 else if (BytesInAddress == 8 && Endian == support::endianness::little)
713 E = readCoverageMappingData<uint64_t, support::endianness::little>(
714 Reader->ProfileNames, Coverage, Reader->MappingRecords,
715 Reader->Filenames);
716 else if (BytesInAddress == 8 && Endian == support::endianness::big)
717 E = readCoverageMappingData<uint64_t, support::endianness::big>(
718 Reader->ProfileNames, Coverage, Reader->MappingRecords,
719 Reader->Filenames);
720 else
721 return make_error<CoverageMapError>(coveragemap_error::malformed);
722 if (E)
723 return std::move(E);
724 return std::move(Reader);
725}
726
727Error BinaryCoverageReader::readNextRecord(CoverageMappingRecord &Record) {
728 if (CurrentRecord >= MappingRecords.size())
1
Taking false branch
729 return make_error<CoverageMapError>(coveragemap_error::eof);
730
731 FunctionsFilenames.clear();
732 Expressions.clear();
733 MappingRegions.clear();
734 auto &R = MappingRecords[CurrentRecord];
735 RawCoverageMappingReader Reader(
736 R.CoverageMapping,
737 makeArrayRef(Filenames).slice(R.FilenamesBegin, R.FilenamesSize),
738 FunctionsFilenames, Expressions, MappingRegions);
739 if (auto Err = Reader.read())
2
Calling 'RawCoverageMappingReader::read'
740 return Err;
741
742 Record.FunctionName = R.FunctionName;
743 Record.FunctionHash = R.FunctionHash;
744 Record.Filenames = FunctionsFilenames;
745 Record.Expressions = Expressions;
746 Record.MappingRegions = MappingRegions;
747
748 ++CurrentRecord;
749 return Error::success();
750}

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

/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/STLExtras.h

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