Bug Summary

File:include/llvm/ADT/STLExtras.h
Warning:line 1404, column 33
2nd function call argument is an uninitialized value

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name BTFDebug.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Target/BPF -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Target/BPF -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp

1//===- BTFDebug.cpp - BTF Generator ---------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains support for writing BTF debug info.
10//
11//===----------------------------------------------------------------------===//
12
13#include "BTFDebug.h"
14#include "llvm/BinaryFormat/ELF.h"
15#include "llvm/CodeGen/AsmPrinter.h"
16#include "llvm/CodeGen/MachineModuleInfo.h"
17#include "llvm/MC/MCContext.h"
18#include "llvm/MC/MCObjectFileInfo.h"
19#include "llvm/MC/MCSectionELF.h"
20#include "llvm/MC/MCStreamer.h"
21#include "llvm/Support/LineIterator.h"
22
23using namespace llvm;
24
25static const char *BTFKindStr[] = {
26#define HANDLE_BTF_KIND(ID, NAME) "BTF_KIND_" #NAME,
27#include "BTF.def"
28};
29
30/// Emit a BTF common type.
31void BTFTypeBase::emitType(MCStreamer &OS) {
32 OS.AddComment(std::string(BTFKindStr[Kind]) + "(id = " + std::to_string(Id) +
33 ")");
34 OS.EmitIntValue(BTFType.NameOff, 4);
35 OS.AddComment("0x" + Twine::utohexstr(BTFType.Info));
36 OS.EmitIntValue(BTFType.Info, 4);
37 OS.EmitIntValue(BTFType.Size, 4);
38}
39
40BTFTypeDerived::BTFTypeDerived(const DIDerivedType *DTy, unsigned Tag)
41 : DTy(DTy) {
42 switch (Tag) {
43 case dwarf::DW_TAG_pointer_type:
44 Kind = BTF::BTF_KIND_PTR;
45 break;
46 case dwarf::DW_TAG_const_type:
47 Kind = BTF::BTF_KIND_CONST;
48 break;
49 case dwarf::DW_TAG_volatile_type:
50 Kind = BTF::BTF_KIND_VOLATILE;
51 break;
52 case dwarf::DW_TAG_typedef:
53 Kind = BTF::BTF_KIND_TYPEDEF;
54 break;
55 case dwarf::DW_TAG_restrict_type:
56 Kind = BTF::BTF_KIND_RESTRICT;
57 break;
58 default:
59 llvm_unreachable("Unknown DIDerivedType Tag")::llvm::llvm_unreachable_internal("Unknown DIDerivedType Tag"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp"
, 59)
;
60 }
61 BTFType.Info = Kind << 24;
62}
63
64void BTFTypeDerived::completeType(BTFDebug &BDebug) {
65 BTFType.NameOff = BDebug.addString(DTy->getName());
66
67 // The base type for PTR/CONST/VOLATILE could be void.
68 const DIType *ResolvedType = DTy->getBaseType();
69 if (!ResolvedType) {
70 assert((Kind == BTF::BTF_KIND_PTR || Kind == BTF::BTF_KIND_CONST ||(((Kind == BTF::BTF_KIND_PTR || Kind == BTF::BTF_KIND_CONST ||
Kind == BTF::BTF_KIND_VOLATILE) && "Invalid null basetype"
) ? static_cast<void> (0) : __assert_fail ("(Kind == BTF::BTF_KIND_PTR || Kind == BTF::BTF_KIND_CONST || Kind == BTF::BTF_KIND_VOLATILE) && \"Invalid null basetype\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp"
, 72, __PRETTY_FUNCTION__))
71 Kind == BTF::BTF_KIND_VOLATILE) &&(((Kind == BTF::BTF_KIND_PTR || Kind == BTF::BTF_KIND_CONST ||
Kind == BTF::BTF_KIND_VOLATILE) && "Invalid null basetype"
) ? static_cast<void> (0) : __assert_fail ("(Kind == BTF::BTF_KIND_PTR || Kind == BTF::BTF_KIND_CONST || Kind == BTF::BTF_KIND_VOLATILE) && \"Invalid null basetype\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp"
, 72, __PRETTY_FUNCTION__))
72 "Invalid null basetype")(((Kind == BTF::BTF_KIND_PTR || Kind == BTF::BTF_KIND_CONST ||
Kind == BTF::BTF_KIND_VOLATILE) && "Invalid null basetype"
) ? static_cast<void> (0) : __assert_fail ("(Kind == BTF::BTF_KIND_PTR || Kind == BTF::BTF_KIND_CONST || Kind == BTF::BTF_KIND_VOLATILE) && \"Invalid null basetype\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp"
, 72, __PRETTY_FUNCTION__))
;
73 BTFType.Type = 0;
74 } else {
75 BTFType.Type = BDebug.getTypeId(ResolvedType);
76 }
77}
78
79void BTFTypeDerived::emitType(MCStreamer &OS) { BTFTypeBase::emitType(OS); }
80
81/// Represent a struct/union forward declaration.
82BTFTypeFwd::BTFTypeFwd(StringRef Name, bool IsUnion) : Name(Name) {
83 Kind = BTF::BTF_KIND_FWD;
84 BTFType.Info = IsUnion << 31 | Kind << 24;
85 BTFType.Type = 0;
86}
87
88void BTFTypeFwd::completeType(BTFDebug &BDebug) {
89 BTFType.NameOff = BDebug.addString(Name);
90}
91
92void BTFTypeFwd::emitType(MCStreamer &OS) { BTFTypeBase::emitType(OS); }
93
94BTFTypeInt::BTFTypeInt(uint32_t Encoding, uint32_t SizeInBits,
95 uint32_t OffsetInBits, StringRef TypeName)
96 : Name(TypeName) {
97 // Translate IR int encoding to BTF int encoding.
98 uint8_t BTFEncoding;
99 switch (Encoding) {
100 case dwarf::DW_ATE_boolean:
101 BTFEncoding = BTF::INT_BOOL;
102 break;
103 case dwarf::DW_ATE_signed:
104 case dwarf::DW_ATE_signed_char:
105 BTFEncoding = BTF::INT_SIGNED;
106 break;
107 case dwarf::DW_ATE_unsigned:
108 case dwarf::DW_ATE_unsigned_char:
109 BTFEncoding = 0;
110 break;
111 default:
112 llvm_unreachable("Unknown BTFTypeInt Encoding")::llvm::llvm_unreachable_internal("Unknown BTFTypeInt Encoding"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp"
, 112)
;
113 }
114
115 Kind = BTF::BTF_KIND_INT;
116 BTFType.Info = Kind << 24;
117 BTFType.Size = roundupToBytes(SizeInBits);
118 IntVal = (BTFEncoding << 24) | OffsetInBits << 16 | SizeInBits;
119}
120
121void BTFTypeInt::completeType(BTFDebug &BDebug) {
122 BTFType.NameOff = BDebug.addString(Name);
123}
124
125void BTFTypeInt::emitType(MCStreamer &OS) {
126 BTFTypeBase::emitType(OS);
127 OS.AddComment("0x" + Twine::utohexstr(IntVal));
128 OS.EmitIntValue(IntVal, 4);
129}
130
131BTFTypeEnum::BTFTypeEnum(const DICompositeType *ETy, uint32_t VLen) : ETy(ETy) {
132 Kind = BTF::BTF_KIND_ENUM;
133 BTFType.Info = Kind << 24 | VLen;
134 BTFType.Size = roundupToBytes(ETy->getSizeInBits());
135}
136
137void BTFTypeEnum::completeType(BTFDebug &BDebug) {
138 BTFType.NameOff = BDebug.addString(ETy->getName());
139
140 DINodeArray Elements = ETy->getElements();
141 for (const auto Element : Elements) {
142 const auto *Enum = cast<DIEnumerator>(Element);
143
144 struct BTF::BTFEnum BTFEnum;
145 BTFEnum.NameOff = BDebug.addString(Enum->getName());
146 // BTF enum value is 32bit, enforce it.
147 BTFEnum.Val = static_cast<uint32_t>(Enum->getValue());
148 EnumValues.push_back(BTFEnum);
149 }
150}
151
152void BTFTypeEnum::emitType(MCStreamer &OS) {
153 BTFTypeBase::emitType(OS);
154 for (const auto &Enum : EnumValues) {
155 OS.EmitIntValue(Enum.NameOff, 4);
156 OS.EmitIntValue(Enum.Val, 4);
157 }
158}
159
160BTFTypeArray::BTFTypeArray(uint32_t ElemTypeId, uint32_t NumElems) {
161 Kind = BTF::BTF_KIND_ARRAY;
162 BTFType.NameOff = 0;
163 BTFType.Info = Kind << 24;
164 BTFType.Size = 0;
165
166 ArrayInfo.ElemType = ElemTypeId;
167 ArrayInfo.Nelems = NumElems;
168}
169
170/// Represent a BTF array.
171void BTFTypeArray::completeType(BTFDebug &BDebug) {
172
173 // The IR does not really have a type for the index.
174 // A special type for array index should have been
175 // created during initial type traversal. Just
176 // retrieve that type id.
177 ArrayInfo.IndexType = BDebug.getArrayIndexTypeId();
178}
179
180void BTFTypeArray::emitType(MCStreamer &OS) {
181 BTFTypeBase::emitType(OS);
182 OS.EmitIntValue(ArrayInfo.ElemType, 4);
183 OS.EmitIntValue(ArrayInfo.IndexType, 4);
184 OS.EmitIntValue(ArrayInfo.Nelems, 4);
185}
186
187/// Represent either a struct or a union.
188BTFTypeStruct::BTFTypeStruct(const DICompositeType *STy, bool IsStruct,
189 bool HasBitField, uint32_t Vlen)
190 : STy(STy), HasBitField(HasBitField) {
191 Kind = IsStruct ? BTF::BTF_KIND_STRUCT : BTF::BTF_KIND_UNION;
192 BTFType.Size = roundupToBytes(STy->getSizeInBits());
193 BTFType.Info = (HasBitField << 31) | (Kind << 24) | Vlen;
194}
195
196void BTFTypeStruct::completeType(BTFDebug &BDebug) {
197 BTFType.NameOff = BDebug.addString(STy->getName());
198
199 // Add struct/union members.
200 const DINodeArray Elements = STy->getElements();
201 for (const auto *Element : Elements) {
202 struct BTF::BTFMember BTFMember;
203 const auto *DDTy = cast<DIDerivedType>(Element);
204
205 BTFMember.NameOff = BDebug.addString(DDTy->getName());
206 if (HasBitField) {
207 uint8_t BitFieldSize = DDTy->isBitField() ? DDTy->getSizeInBits() : 0;
208 BTFMember.Offset = BitFieldSize << 24 | DDTy->getOffsetInBits();
209 } else {
210 BTFMember.Offset = DDTy->getOffsetInBits();
211 }
212 BTFMember.Type = BDebug.getTypeId(DDTy->getBaseType());
213 Members.push_back(BTFMember);
214 }
215}
216
217void BTFTypeStruct::emitType(MCStreamer &OS) {
218 BTFTypeBase::emitType(OS);
219 for (const auto &Member : Members) {
220 OS.EmitIntValue(Member.NameOff, 4);
221 OS.EmitIntValue(Member.Type, 4);
222 OS.AddComment("0x" + Twine::utohexstr(Member.Offset));
223 OS.EmitIntValue(Member.Offset, 4);
224 }
225}
226
227/// The Func kind represents both subprogram and pointee of function
228/// pointers. If the FuncName is empty, it represents a pointee of function
229/// pointer. Otherwise, it represents a subprogram. The func arg names
230/// are empty for pointee of function pointer case, and are valid names
231/// for subprogram.
232BTFTypeFuncProto::BTFTypeFuncProto(
233 const DISubroutineType *STy, uint32_t VLen,
234 const std::unordered_map<uint32_t, StringRef> &FuncArgNames)
235 : STy(STy), FuncArgNames(FuncArgNames) {
236 Kind = BTF::BTF_KIND_FUNC_PROTO;
237 BTFType.Info = (Kind << 24) | VLen;
238}
239
240void BTFTypeFuncProto::completeType(BTFDebug &BDebug) {
241 DITypeRefArray Elements = STy->getTypeArray();
242 auto RetType = Elements[0];
243 BTFType.Type = RetType ? BDebug.getTypeId(RetType) : 0;
244 BTFType.NameOff = 0;
245
246 // For null parameter which is typically the last one
247 // to represent the vararg, encode the NameOff/Type to be 0.
248 for (unsigned I = 1, N = Elements.size(); I < N; ++I) {
249 struct BTF::BTFParam Param;
250 auto Element = Elements[I];
251 if (Element) {
252 Param.NameOff = BDebug.addString(FuncArgNames[I]);
253 Param.Type = BDebug.getTypeId(Element);
254 } else {
255 Param.NameOff = 0;
256 Param.Type = 0;
257 }
258 Parameters.push_back(Param);
259 }
260}
261
262void BTFTypeFuncProto::emitType(MCStreamer &OS) {
263 BTFTypeBase::emitType(OS);
264 for (const auto &Param : Parameters) {
265 OS.EmitIntValue(Param.NameOff, 4);
266 OS.EmitIntValue(Param.Type, 4);
267 }
268}
269
270BTFTypeFunc::BTFTypeFunc(StringRef FuncName, uint32_t ProtoTypeId)
271 : Name(FuncName) {
272 Kind = BTF::BTF_KIND_FUNC;
273 BTFType.Info = Kind << 24;
274 BTFType.Type = ProtoTypeId;
275}
276
277void BTFTypeFunc::completeType(BTFDebug &BDebug) {
278 BTFType.NameOff = BDebug.addString(Name);
279}
280
281void BTFTypeFunc::emitType(MCStreamer &OS) { BTFTypeBase::emitType(OS); }
282
283BTFKindVar::BTFKindVar(StringRef VarName, uint32_t TypeId, uint32_t VarInfo)
284 : Name(VarName) {
285 Kind = BTF::BTF_KIND_VAR;
286 BTFType.Info = Kind << 24;
287 BTFType.Type = TypeId;
288 Info = VarInfo;
289}
290
291void BTFKindVar::completeType(BTFDebug &BDebug) {
292 BTFType.NameOff = BDebug.addString(Name);
293}
294
295void BTFKindVar::emitType(MCStreamer &OS) {
296 BTFTypeBase::emitType(OS);
297 OS.EmitIntValue(Info, 4);
298}
299
300BTFKindDataSec::BTFKindDataSec(AsmPrinter *AsmPrt, std::string SecName)
301 : Asm(AsmPrt), Name(SecName) {
302 Kind = BTF::BTF_KIND_DATASEC;
303 BTFType.Info = Kind << 24;
304 BTFType.Size = 0;
305}
306
307void BTFKindDataSec::completeType(BTFDebug &BDebug) {
308 BTFType.NameOff = BDebug.addString(Name);
309 BTFType.Info |= Vars.size();
310}
311
312void BTFKindDataSec::emitType(MCStreamer &OS) {
313 BTFTypeBase::emitType(OS);
314
315 for (const auto &V : Vars) {
316 OS.EmitIntValue(std::get<0>(V), 4);
317 Asm->EmitLabelReference(std::get<1>(V), 4);
318 OS.EmitIntValue(std::get<2>(V), 4);
319 }
320}
321
322uint32_t BTFStringTable::addString(StringRef S) {
323 // Check whether the string already exists.
324 for (auto &OffsetM : OffsetToIdMap) {
325 if (Table[OffsetM.second] == S)
326 return OffsetM.first;
327 }
328 // Not find, add to the string table.
329 uint32_t Offset = Size;
330 OffsetToIdMap[Offset] = Table.size();
331 Table.push_back(S);
332 Size += S.size() + 1;
333 return Offset;
334}
335
336BTFDebug::BTFDebug(AsmPrinter *AP)
337 : DebugHandlerBase(AP), OS(*Asm->OutStreamer), SkipInstruction(false),
338 LineInfoGenerated(false), SecNameOff(0), ArrayIndexTypeId(0) {
339 addString("\0");
340}
341
342uint32_t BTFDebug::addType(std::unique_ptr<BTFTypeBase> TypeEntry,
343 const DIType *Ty) {
344 TypeEntry->setId(TypeEntries.size() + 1);
345 uint32_t Id = TypeEntry->getId();
346 DIToIdMap[Ty] = Id;
347 TypeEntries.push_back(std::move(TypeEntry));
348 return Id;
349}
350
351uint32_t BTFDebug::addType(std::unique_ptr<BTFTypeBase> TypeEntry) {
352 TypeEntry->setId(TypeEntries.size() + 1);
353 uint32_t Id = TypeEntry->getId();
354 TypeEntries.push_back(std::move(TypeEntry));
355 return Id;
356}
357
358void BTFDebug::visitBasicType(const DIBasicType *BTy, uint32_t &TypeId) {
359 // Only int types are supported in BTF.
360 uint32_t Encoding = BTy->getEncoding();
361 if (Encoding != dwarf::DW_ATE_boolean && Encoding != dwarf::DW_ATE_signed &&
362 Encoding != dwarf::DW_ATE_signed_char &&
363 Encoding != dwarf::DW_ATE_unsigned &&
364 Encoding != dwarf::DW_ATE_unsigned_char)
365 return;
366
367 // Create a BTF type instance for this DIBasicType and put it into
368 // DIToIdMap for cross-type reference check.
369 auto TypeEntry = llvm::make_unique<BTFTypeInt>(
370 Encoding, BTy->getSizeInBits(), BTy->getOffsetInBits(), BTy->getName());
371 TypeId = addType(std::move(TypeEntry), BTy);
372}
373
374/// Handle subprogram or subroutine types.
375void BTFDebug::visitSubroutineType(
376 const DISubroutineType *STy, bool ForSubprog,
377 const std::unordered_map<uint32_t, StringRef> &FuncArgNames,
378 uint32_t &TypeId) {
379 DITypeRefArray Elements = STy->getTypeArray();
380 uint32_t VLen = Elements.size() - 1;
381 if (VLen > BTF::MAX_VLEN)
5
Assuming 'VLen' is > MAX_VLEN
6
Taking true branch
382 return;
7
Returning without writing to 'TypeId'
383
384 // Subprogram has a valid non-zero-length name, and the pointee of
385 // a function pointer has an empty name. The subprogram type will
386 // not be added to DIToIdMap as it should not be referenced by
387 // any other types.
388 auto TypeEntry = llvm::make_unique<BTFTypeFuncProto>(STy, VLen, FuncArgNames);
389 if (ForSubprog)
390 TypeId = addType(std::move(TypeEntry)); // For subprogram
391 else
392 TypeId = addType(std::move(TypeEntry), STy); // For func ptr
393
394 // Visit return type and func arg types.
395 for (const auto Element : Elements) {
396 visitTypeEntry(Element);
397 }
398}
399
400/// Handle structure/union types.
401void BTFDebug::visitStructType(const DICompositeType *CTy, bool IsStruct,
402 uint32_t &TypeId) {
403 const DINodeArray Elements = CTy->getElements();
404 uint32_t VLen = Elements.size();
405 if (VLen > BTF::MAX_VLEN)
406 return;
407
408 // Check whether we have any bitfield members or not
409 bool HasBitField = false;
410 for (const auto *Element : Elements) {
411 auto E = cast<DIDerivedType>(Element);
412 if (E->isBitField()) {
413 HasBitField = true;
414 break;
415 }
416 }
417
418 auto TypeEntry =
419 llvm::make_unique<BTFTypeStruct>(CTy, IsStruct, HasBitField, VLen);
420 TypeId = addType(std::move(TypeEntry), CTy);
421
422 // Visit all struct members.
423 for (const auto *Element : Elements)
424 visitTypeEntry(cast<DIDerivedType>(Element));
425}
426
427void BTFDebug::visitArrayType(const DICompositeType *CTy, uint32_t &TypeId) {
428 // Visit array element type.
429 uint32_t ElemTypeId;
430 visitTypeEntry(CTy->getBaseType(), ElemTypeId);
431
432 if (!CTy->getSizeInBits()) {
433 auto TypeEntry = llvm::make_unique<BTFTypeArray>(ElemTypeId, 0);
434 ElemTypeId = addType(std::move(TypeEntry), CTy);
435 } else {
436 // Visit array dimensions.
437 DINodeArray Elements = CTy->getElements();
438 for (int I = Elements.size() - 1; I >= 0; --I) {
439 if (auto *Element = dyn_cast_or_null<DINode>(Elements[I]))
440 if (Element->getTag() == dwarf::DW_TAG_subrange_type) {
441 const DISubrange *SR = cast<DISubrange>(Element);
442 auto *CI = SR->getCount().dyn_cast<ConstantInt *>();
443 int64_t Count = CI->getSExtValue();
444
445 auto TypeEntry = llvm::make_unique<BTFTypeArray>(ElemTypeId, Count);
446 if (I == 0)
447 ElemTypeId = addType(std::move(TypeEntry), CTy);
448 else
449 ElemTypeId = addType(std::move(TypeEntry));
450 }
451 }
452 }
453
454 // The array TypeId is the type id of the outermost dimension.
455 TypeId = ElemTypeId;
456
457 // The IR does not have a type for array index while BTF wants one.
458 // So create an array index type if there is none.
459 if (!ArrayIndexTypeId) {
460 auto TypeEntry = llvm::make_unique<BTFTypeInt>(dwarf::DW_ATE_unsigned, 32,
461 0, "__ARRAY_SIZE_TYPE__");
462 ArrayIndexTypeId = addType(std::move(TypeEntry));
463 }
464}
465
466void BTFDebug::visitEnumType(const DICompositeType *CTy, uint32_t &TypeId) {
467 DINodeArray Elements = CTy->getElements();
468 uint32_t VLen = Elements.size();
469 if (VLen > BTF::MAX_VLEN)
470 return;
471
472 auto TypeEntry = llvm::make_unique<BTFTypeEnum>(CTy, VLen);
473 TypeId = addType(std::move(TypeEntry), CTy);
474 // No need to visit base type as BTF does not encode it.
475}
476
477/// Handle structure/union forward declarations.
478void BTFDebug::visitFwdDeclType(const DICompositeType *CTy, bool IsUnion,
479 uint32_t &TypeId) {
480 auto TypeEntry = llvm::make_unique<BTFTypeFwd>(CTy->getName(), IsUnion);
481 TypeId = addType(std::move(TypeEntry), CTy);
482}
483
484/// Handle structure, union, array and enumeration types.
485void BTFDebug::visitCompositeType(const DICompositeType *CTy,
486 uint32_t &TypeId) {
487 auto Tag = CTy->getTag();
488 if (Tag == dwarf::DW_TAG_structure_type || Tag == dwarf::DW_TAG_union_type) {
489 // Handle forward declaration differently as it does not have members.
490 if (CTy->isForwardDecl())
491 visitFwdDeclType(CTy, Tag == dwarf::DW_TAG_union_type, TypeId);
492 else
493 visitStructType(CTy, Tag == dwarf::DW_TAG_structure_type, TypeId);
494 } else if (Tag == dwarf::DW_TAG_array_type)
495 visitArrayType(CTy, TypeId);
496 else if (Tag == dwarf::DW_TAG_enumeration_type)
497 visitEnumType(CTy, TypeId);
498}
499
500/// Handle pointer, typedef, const, volatile, restrict and member types.
501void BTFDebug::visitDerivedType(const DIDerivedType *DTy, uint32_t &TypeId) {
502 unsigned Tag = DTy->getTag();
503
504 if (Tag == dwarf::DW_TAG_pointer_type || Tag == dwarf::DW_TAG_typedef ||
505 Tag == dwarf::DW_TAG_const_type || Tag == dwarf::DW_TAG_volatile_type ||
506 Tag == dwarf::DW_TAG_restrict_type) {
507 auto TypeEntry = llvm::make_unique<BTFTypeDerived>(DTy, Tag);
508 TypeId = addType(std::move(TypeEntry), DTy);
509 } else if (Tag != dwarf::DW_TAG_member) {
510 return;
511 }
512
513 // Visit base type of pointer, typedef, const, volatile, restrict or
514 // struct/union member.
515 uint32_t TempTypeId = 0;
516 visitTypeEntry(DTy->getBaseType(), TempTypeId);
517}
518
519void BTFDebug::visitTypeEntry(const DIType *Ty, uint32_t &TypeId) {
520 if (!Ty || DIToIdMap.find(Ty) != DIToIdMap.end()) {
521 TypeId = DIToIdMap[Ty];
522 return;
523 }
524
525 if (const auto *BTy = dyn_cast<DIBasicType>(Ty))
526 visitBasicType(BTy, TypeId);
527 else if (const auto *STy = dyn_cast<DISubroutineType>(Ty))
528 visitSubroutineType(STy, false, std::unordered_map<uint32_t, StringRef>(),
529 TypeId);
530 else if (const auto *CTy = dyn_cast<DICompositeType>(Ty))
531 visitCompositeType(CTy, TypeId);
532 else if (const auto *DTy = dyn_cast<DIDerivedType>(Ty))
533 visitDerivedType(DTy, TypeId);
534 else
535 llvm_unreachable("Unknown DIType")::llvm::llvm_unreachable_internal("Unknown DIType", "/build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp"
, 535)
;
536}
537
538void BTFDebug::visitTypeEntry(const DIType *Ty) {
539 uint32_t TypeId;
540 visitTypeEntry(Ty, TypeId);
541}
542
543/// Read file contents from the actual file or from the source
544std::string BTFDebug::populateFileContent(const DISubprogram *SP) {
545 auto File = SP->getFile();
546 std::string FileName;
547
548 if (!File->getFilename().startswith("/") && File->getDirectory().size())
549 FileName = File->getDirectory().str() + "/" + File->getFilename().str();
550 else
551 FileName = File->getFilename();
552
553 // No need to populate the contends if it has been populated!
554 if (FileContent.find(FileName) != FileContent.end())
555 return FileName;
556
557 std::vector<std::string> Content;
558 std::string Line;
559 Content.push_back(Line); // Line 0 for empty string
560
561 std::unique_ptr<MemoryBuffer> Buf;
562 auto Source = File->getSource();
563 if (Source)
564 Buf = MemoryBuffer::getMemBufferCopy(*Source);
565 else if (ErrorOr<std::unique_ptr<MemoryBuffer>> BufOrErr =
566 MemoryBuffer::getFile(FileName))
567 Buf = std::move(*BufOrErr);
568 if (Buf)
569 for (line_iterator I(*Buf, false), E; I != E; ++I)
570 Content.push_back(*I);
571
572 FileContent[FileName] = Content;
573 return FileName;
574}
575
576void BTFDebug::constructLineInfo(const DISubprogram *SP, MCSymbol *Label,
577 uint32_t Line, uint32_t Column) {
578 std::string FileName = populateFileContent(SP);
579 BTFLineInfo LineInfo;
580
581 LineInfo.Label = Label;
582 LineInfo.FileNameOff = addString(FileName);
583 // If file content is not available, let LineOff = 0.
584 if (Line < FileContent[FileName].size())
585 LineInfo.LineOff = addString(FileContent[FileName][Line]);
586 else
587 LineInfo.LineOff = 0;
588 LineInfo.LineNum = Line;
589 LineInfo.ColumnNum = Column;
590 LineInfoTable[SecNameOff].push_back(LineInfo);
591}
592
593void BTFDebug::emitCommonHeader() {
594 OS.AddComment("0x" + Twine::utohexstr(BTF::MAGIC));
595 OS.EmitIntValue(BTF::MAGIC, 2);
596 OS.EmitIntValue(BTF::VERSION, 1);
597 OS.EmitIntValue(0, 1);
598}
599
600void BTFDebug::emitBTFSection() {
601 // Do not emit section if no types and only "" string.
602 if (!TypeEntries.size() && StringTable.getSize() == 1)
603 return;
604
605 MCContext &Ctx = OS.getContext();
606 OS.SwitchSection(Ctx.getELFSection(".BTF", ELF::SHT_PROGBITS, 0));
607
608 // Emit header.
609 emitCommonHeader();
610 OS.EmitIntValue(BTF::HeaderSize, 4);
611
612 uint32_t TypeLen = 0, StrLen;
613 for (const auto &TypeEntry : TypeEntries)
614 TypeLen += TypeEntry->getSize();
615 StrLen = StringTable.getSize();
616
617 OS.EmitIntValue(0, 4);
618 OS.EmitIntValue(TypeLen, 4);
619 OS.EmitIntValue(TypeLen, 4);
620 OS.EmitIntValue(StrLen, 4);
621
622 // Emit type table.
623 for (const auto &TypeEntry : TypeEntries)
624 TypeEntry->emitType(OS);
625
626 // Emit string table.
627 uint32_t StringOffset = 0;
628 for (const auto &S : StringTable.getTable()) {
629 OS.AddComment("string offset=" + std::to_string(StringOffset));
630 OS.EmitBytes(S);
631 OS.EmitBytes(StringRef("\0", 1));
632 StringOffset += S.size() + 1;
633 }
634}
635
636void BTFDebug::emitBTFExtSection() {
637 // Do not emit section if empty FuncInfoTable and LineInfoTable.
638 if (!FuncInfoTable.size() && !LineInfoTable.size())
639 return;
640
641 MCContext &Ctx = OS.getContext();
642 OS.SwitchSection(Ctx.getELFSection(".BTF.ext", ELF::SHT_PROGBITS, 0));
643
644 // Emit header.
645 emitCommonHeader();
646 OS.EmitIntValue(BTF::ExtHeaderSize, 4);
647
648 // Account for FuncInfo/LineInfo record size as well.
649 uint32_t FuncLen = 4, LineLen = 4;
650 for (const auto &FuncSec : FuncInfoTable) {
651 FuncLen += BTF::SecFuncInfoSize;
652 FuncLen += FuncSec.second.size() * BTF::BPFFuncInfoSize;
653 }
654 for (const auto &LineSec : LineInfoTable) {
655 LineLen += BTF::SecLineInfoSize;
656 LineLen += LineSec.second.size() * BTF::BPFLineInfoSize;
657 }
658
659 OS.EmitIntValue(0, 4);
660 OS.EmitIntValue(FuncLen, 4);
661 OS.EmitIntValue(FuncLen, 4);
662 OS.EmitIntValue(LineLen, 4);
663
664 // Emit func_info table.
665 OS.AddComment("FuncInfo");
666 OS.EmitIntValue(BTF::BPFFuncInfoSize, 4);
667 for (const auto &FuncSec : FuncInfoTable) {
668 OS.AddComment("FuncInfo section string offset=" +
669 std::to_string(FuncSec.first));
670 OS.EmitIntValue(FuncSec.first, 4);
671 OS.EmitIntValue(FuncSec.second.size(), 4);
672 for (const auto &FuncInfo : FuncSec.second) {
673 Asm->EmitLabelReference(FuncInfo.Label, 4);
674 OS.EmitIntValue(FuncInfo.TypeId, 4);
675 }
676 }
677
678 // Emit line_info table.
679 OS.AddComment("LineInfo");
680 OS.EmitIntValue(BTF::BPFLineInfoSize, 4);
681 for (const auto &LineSec : LineInfoTable) {
682 OS.AddComment("LineInfo section string offset=" +
683 std::to_string(LineSec.first));
684 OS.EmitIntValue(LineSec.first, 4);
685 OS.EmitIntValue(LineSec.second.size(), 4);
686 for (const auto &LineInfo : LineSec.second) {
687 Asm->EmitLabelReference(LineInfo.Label, 4);
688 OS.EmitIntValue(LineInfo.FileNameOff, 4);
689 OS.EmitIntValue(LineInfo.LineOff, 4);
690 OS.AddComment("Line " + std::to_string(LineInfo.LineNum) + " Col " +
691 std::to_string(LineInfo.ColumnNum));
692 OS.EmitIntValue(LineInfo.LineNum << 10 | LineInfo.ColumnNum, 4);
693 }
694 }
695}
696
697void BTFDebug::beginFunctionImpl(const MachineFunction *MF) {
698 auto *SP = MF->getFunction().getSubprogram();
699 auto *Unit = SP->getUnit();
700
701 if (Unit->getEmissionKind() == DICompileUnit::NoDebug) {
1
Assuming the condition is false
2
Taking false branch
702 SkipInstruction = true;
703 return;
704 }
705 SkipInstruction = false;
706
707 // Collect all types locally referenced in this function.
708 // Use RetainedNodes so we can collect all argument names
709 // even if the argument is not used.
710 std::unordered_map<uint32_t, StringRef> FuncArgNames;
711 for (const DINode *DN : SP->getRetainedNodes()) {
712 if (const auto *DV = dyn_cast<DILocalVariable>(DN)) {
713 // Collect function arguments for subprogram func type.
714 uint32_t Arg = DV->getArg();
715 if (Arg) {
716 visitTypeEntry(DV->getType());
717 FuncArgNames[Arg] = DV->getName();
718 }
719 }
720 }
721
722 // Construct subprogram func proto type.
723 uint32_t ProtoTypeId;
3
'ProtoTypeId' declared without an initial value
724 visitSubroutineType(SP->getType(), true, FuncArgNames, ProtoTypeId);
4
Calling 'BTFDebug::visitSubroutineType'
8
Returning from 'BTFDebug::visitSubroutineType'
725
726 // Construct subprogram func type
727 auto FuncTypeEntry =
728 llvm::make_unique<BTFTypeFunc>(SP->getName(), ProtoTypeId);
9
Calling 'make_unique<llvm::BTFTypeFunc, llvm::StringRef, unsigned int &>'
729 uint32_t FuncTypeId = addType(std::move(FuncTypeEntry));
730
731 // Construct funcinfo and the first lineinfo for the function.
732 MCSymbol *FuncLabel = Asm->getFunctionBegin();
733 BTFFuncInfo FuncInfo;
734 FuncInfo.Label = FuncLabel;
735 FuncInfo.TypeId = FuncTypeId;
736 if (FuncLabel->isInSection()) {
737 MCSection &Section = FuncLabel->getSection();
738 const MCSectionELF *SectionELF = dyn_cast<MCSectionELF>(&Section);
739 assert(SectionELF && "Null section for Function Label")((SectionELF && "Null section for Function Label") ? static_cast
<void> (0) : __assert_fail ("SectionELF && \"Null section for Function Label\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Target/BPF/BTFDebug.cpp"
, 739, __PRETTY_FUNCTION__))
;
740 SecNameOff = addString(SectionELF->getSectionName());
741 } else {
742 SecNameOff = addString(".text");
743 }
744 FuncInfoTable[SecNameOff].push_back(FuncInfo);
745}
746
747void BTFDebug::endFunctionImpl(const MachineFunction *MF) {
748 SkipInstruction = false;
749 LineInfoGenerated = false;
750 SecNameOff = 0;
751}
752
753void BTFDebug::beginInstruction(const MachineInstr *MI) {
754 DebugHandlerBase::beginInstruction(MI);
755
756 if (SkipInstruction || MI->isMetaInstruction() ||
757 MI->getFlag(MachineInstr::FrameSetup))
758 return;
759
760 if (MI->isInlineAsm()) {
761 // Count the number of register definitions to find the asm string.
762 unsigned NumDefs = 0;
763 for (; MI->getOperand(NumDefs).isReg() && MI->getOperand(NumDefs).isDef();
764 ++NumDefs)
765 ;
766
767 // Skip this inline asm instruction if the asmstr is empty.
768 const char *AsmStr = MI->getOperand(NumDefs).getSymbolName();
769 if (AsmStr[0] == 0)
770 return;
771 }
772
773 // Skip this instruction if no DebugLoc or the DebugLoc
774 // is the same as the previous instruction.
775 const DebugLoc &DL = MI->getDebugLoc();
776 if (!DL || PrevInstLoc == DL) {
777 // This instruction will be skipped, no LineInfo has
778 // been generated, construct one based on function signature.
779 if (LineInfoGenerated == false) {
780 auto *S = MI->getMF()->getFunction().getSubprogram();
781 MCSymbol *FuncLabel = Asm->getFunctionBegin();
782 constructLineInfo(S, FuncLabel, S->getLine(), 0);
783 LineInfoGenerated = true;
784 }
785
786 return;
787 }
788
789 // Create a temporary label to remember the insn for lineinfo.
790 MCSymbol *LineSym = OS.getContext().createTempSymbol();
791 OS.EmitLabel(LineSym);
792
793 // Construct the lineinfo.
794 auto SP = DL.get()->getScope()->getSubprogram();
795 constructLineInfo(SP, LineSym, DL.getLine(), DL.getCol());
796
797 LineInfoGenerated = true;
798 PrevInstLoc = DL;
799}
800
801void BTFDebug::processGlobals() {
802 // Collect all types referenced by globals.
803 const Module *M = MMI->getModule();
804 for (const GlobalVariable &Global : M->globals()) {
805 // Ignore external globals for now.
806 if (!Global.hasInitializer() && Global.hasExternalLinkage())
807 continue;
808
809 SmallVector<DIGlobalVariableExpression *, 1> GVs;
810 Global.getDebugInfo(GVs);
811 uint32_t GVTypeId = 0;
812 for (auto *GVE : GVs) {
813 visitTypeEntry(GVE->getVariable()->getType(), GVTypeId);
814 break;
815 }
816
817 // Only support the following globals:
818 // . static variables
819 // . non-static global variables with section attributes
820 // Essentially means:
821 // . .bcc/.data/.rodata DataSec entities only contain static data
822 // . Other DataSec entities contain static or initialized global data.
823 // Initialized global data are mostly used for finding map key/value type
824 // id's. Whether DataSec is readonly or not can be found from
825 // corresponding ELF section flags.
826 auto Linkage = Global.getLinkage();
827 if (Linkage != GlobalValue::InternalLinkage &&
828 (Linkage != GlobalValue::ExternalLinkage || !Global.hasSection()))
829 continue;
830
831 uint32_t GVarInfo = Linkage == GlobalValue::ExternalLinkage
832 ? BTF::VAR_GLOBAL_ALLOCATED
833 : BTF::VAR_STATIC;
834 auto VarEntry =
835 llvm::make_unique<BTFKindVar>(Global.getName(), GVTypeId, GVarInfo);
836 uint32_t VarId = addType(std::move(VarEntry));
837
838 // Decide the section name.
839 std::string SecName;
840 if (Global.hasSection()) {
841 SecName = Global.getSection().str();
842 } else {
843 // data, bss, or readonly sections
844 if (Global.isConstant())
845 SecName += ".rodata";
846 else
847 SecName += Global.getInitializer()->isZeroValue() ? ".bss" : ".data";
848 }
849
850 // Find or create a DataSec
851 if (DataSecEntries.find(SecName) == DataSecEntries.end()) {
852 DataSecEntries[SecName] = llvm::make_unique<BTFKindDataSec>(Asm, SecName);
853 }
854
855 // Calculate symbol size
856 const DataLayout &DL = Global.getParent()->getDataLayout();
857 uint32_t Size = DL.getTypeAllocSize(Global.getType()->getElementType());
858
859 DataSecEntries[SecName]->addVar(VarId, Asm->getSymbol(&Global), Size);
860 }
861
862 for (auto &DataSec : DataSecEntries)
863 addType(std::move(DataSec.second));
864}
865
866void BTFDebug::endModule() {
867 // Collect all global types/variables.
868 processGlobals();
869
870 // Complete BTF type cross refereences.
871 for (const auto &TypeEntry : TypeEntries)
872 TypeEntry->completeType(*this);
873
874 // Emit BTF sections.
875 emitBTFSection();
876 emitBTFExtSection();
877}

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h

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

/usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/bits/move.h

1// Move, forward and identity for C++0x + swap -*- C++ -*-
2
3// Copyright (C) 2007-2016 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file bits/move.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{utility}
28 */
29
30#ifndef _MOVE_H1
31#define _MOVE_H1 1
32
33#include <bits/c++config.h>
34#include <bits/concept_check.h>
35
36namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
37{
38_GLIBCXX_BEGIN_NAMESPACE_VERSION
39
40 // Used, in C++03 mode too, by allocators, etc.
41 /**
42 * @brief Same as C++11 std::addressof
43 * @ingroup utilities
44 */
45 template<typename _Tp>
46 inline _Tp*
47 __addressof(_Tp& __r) _GLIBCXX_NOEXCEPTnoexcept
48 {
49 return reinterpret_cast<_Tp*>
50 (&const_cast<char&>(reinterpret_cast<const volatile char&>(__r)));
51 }
52
53_GLIBCXX_END_NAMESPACE_VERSION
54} // namespace
55
56#if __cplusplus201103L >= 201103L
57#include <type_traits> // Brings in std::declval too.
58
59namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
60{
61_GLIBCXX_BEGIN_NAMESPACE_VERSION
62
63 /**
64 * @addtogroup utilities
65 * @{
66 */
67
68 /**
69 * @brief Forward an lvalue.
70 * @return The parameter cast to the specified type.
71 *
72 * This function is used to implement "perfect forwarding".
73 */
74 template<typename _Tp>
75 constexpr _Tp&&
76 forward(typename std::remove_reference<_Tp>::type& __t) noexcept
77 { return static_cast<_Tp&&>(__t); }
12
Returning pointer (reference to 'ProtoTypeId')
78
79 /**
80 * @brief Forward an rvalue.
81 * @return The parameter cast to the specified type.
82 *
83 * This function is used to implement "perfect forwarding".
84 */
85 template<typename _Tp>
86 constexpr _Tp&&
87 forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
88 {
89 static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
90 " substituting _Tp is an lvalue reference type");
91 return static_cast<_Tp&&>(__t);
92 }
93
94 /**
95 * @brief Convert a value to an rvalue.
96 * @param __t A thing of arbitrary type.
97 * @return The parameter cast to an rvalue-reference to allow moving it.
98 */
99 template<typename _Tp>
100 constexpr typename std::remove_reference<_Tp>::type&&
101 move(_Tp&& __t) noexcept
102 { return static_cast<typename std::remove_reference<_Tp>::type&&>(__t); }
103
104
105 template<typename _Tp>
106 struct __move_if_noexcept_cond
107 : public __and_<__not_<is_nothrow_move_constructible<_Tp>>,
108 is_copy_constructible<_Tp>>::type { };
109
110 /**
111 * @brief Conditionally convert a value to an rvalue.
112 * @param __x A thing of arbitrary type.
113 * @return The parameter, possibly cast to an rvalue-reference.
114 *
115 * Same as std::move unless the type's move constructor could throw and the
116 * type is copyable, in which case an lvalue-reference is returned instead.
117 */
118 template<typename _Tp>
119 constexpr typename
120 conditional<__move_if_noexcept_cond<_Tp>::value, const _Tp&, _Tp&&>::type
121 move_if_noexcept(_Tp& __x) noexcept
122 { return std::move(__x); }
123
124 // declval, from type_traits.
125
126 /**
127 * @brief Returns the actual address of the object or function
128 * referenced by r, even in the presence of an overloaded
129 * operator&.
130 * @param __r Reference to an object or function.
131 * @return The actual address.
132 */
133 template<typename _Tp>
134 inline _Tp*
135 addressof(_Tp& __r) noexcept
136 { return std::__addressof(__r); }
137
138 // C++11 version of std::exchange for internal use.
139 template <typename _Tp, typename _Up = _Tp>
140 inline _Tp
141 __exchange(_Tp& __obj, _Up&& __new_val)
142 {
143 _Tp __old_val = std::move(__obj);
144 __obj = std::forward<_Up>(__new_val);
145 return __old_val;
146 }
147
148 /// @} group utilities
149_GLIBCXX_END_NAMESPACE_VERSION
150} // namespace
151
152#define _GLIBCXX_MOVE(__val)std::move(__val) std::move(__val)
153#define _GLIBCXX_FORWARD(_Tp, __val)std::forward<_Tp>(__val) std::forward<_Tp>(__val)
154#else
155#define _GLIBCXX_MOVE(__val)std::move(__val) (__val)
156#define _GLIBCXX_FORWARD(_Tp, __val)std::forward<_Tp>(__val) (__val)
157#endif
158
159namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
160{
161_GLIBCXX_BEGIN_NAMESPACE_VERSION
162
163 /**
164 * @addtogroup utilities
165 * @{
166 */
167
168 /**
169 * @brief Swaps two values.
170 * @param __a A thing of arbitrary type.
171 * @param __b Another thing of arbitrary type.
172 * @return Nothing.
173 */
174 template<typename _Tp>
175 inline
176#if __cplusplus201103L >= 201103L
177 typename enable_if<__and_<is_move_constructible<_Tp>,
178 is_move_assignable<_Tp>>::value>::type
179 swap(_Tp& __a, _Tp& __b)
180 noexcept(__and_<is_nothrow_move_constructible<_Tp>,
181 is_nothrow_move_assignable<_Tp>>::value)
182#else
183 void
184 swap(_Tp& __a, _Tp& __b)
185#endif
186 {
187 // concept requirements
188 __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)
189
190 _Tp __tmp = _GLIBCXX_MOVE(__a)std::move(__a);
191 __a = _GLIBCXX_MOVE(__b)std::move(__b);
192 __b = _GLIBCXX_MOVE(__tmp)std::move(__tmp);
193 }
194
195 // _GLIBCXX_RESOLVE_LIB_DEFECTS
196 // DR 809. std::swap should be overloaded for array types.
197 /// Swap the contents of two arrays.
198 template<typename _Tp, size_t _Nm>
199 inline
200#if __cplusplus201103L >= 201103L
201 typename enable_if<__is_swappable<_Tp>::value>::type
202 swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
203 noexcept(__is_nothrow_swappable<_Tp>::value)
204#else
205 void
206 swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
207#endif
208 {
209 for (size_t __n = 0; __n < _Nm; ++__n)
210 swap(__a[__n], __b[__n]);
211 }
212
213 /// @} group utilities
214_GLIBCXX_END_NAMESPACE_VERSION
215} // namespace
216
217#endif /* _MOVE_H */