File: | include/llvm/ADT/STLExtras.h |
Warning: | line 1404, column 33 2nd function call argument is an uninitialized value |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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 | ||||
23 | using namespace llvm; | |||
24 | ||||
25 | static 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. | |||
31 | void 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 | ||||
40 | BTFTypeDerived::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 | ||||
64 | void 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 | ||||
79 | void BTFTypeDerived::emitType(MCStreamer &OS) { BTFTypeBase::emitType(OS); } | |||
80 | ||||
81 | /// Represent a struct/union forward declaration. | |||
82 | BTFTypeFwd::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 | ||||
88 | void BTFTypeFwd::completeType(BTFDebug &BDebug) { | |||
89 | BTFType.NameOff = BDebug.addString(Name); | |||
90 | } | |||
91 | ||||
92 | void BTFTypeFwd::emitType(MCStreamer &OS) { BTFTypeBase::emitType(OS); } | |||
93 | ||||
94 | BTFTypeInt::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 | ||||
121 | void BTFTypeInt::completeType(BTFDebug &BDebug) { | |||
122 | BTFType.NameOff = BDebug.addString(Name); | |||
123 | } | |||
124 | ||||
125 | void BTFTypeInt::emitType(MCStreamer &OS) { | |||
126 | BTFTypeBase::emitType(OS); | |||
127 | OS.AddComment("0x" + Twine::utohexstr(IntVal)); | |||
128 | OS.EmitIntValue(IntVal, 4); | |||
129 | } | |||
130 | ||||
131 | BTFTypeEnum::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 | ||||
137 | void 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 | ||||
152 | void 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 | ||||
160 | BTFTypeArray::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. | |||
171 | void 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 | ||||
180 | void 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. | |||
188 | BTFTypeStruct::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 | ||||
196 | void 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 | ||||
217 | void 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. | |||
232 | BTFTypeFuncProto::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 | ||||
240 | void 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 | ||||
262 | void 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 | ||||
270 | BTFTypeFunc::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 | ||||
277 | void BTFTypeFunc::completeType(BTFDebug &BDebug) { | |||
278 | BTFType.NameOff = BDebug.addString(Name); | |||
279 | } | |||
280 | ||||
281 | void BTFTypeFunc::emitType(MCStreamer &OS) { BTFTypeBase::emitType(OS); } | |||
282 | ||||
283 | BTFKindVar::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 | ||||
291 | void BTFKindVar::completeType(BTFDebug &BDebug) { | |||
292 | BTFType.NameOff = BDebug.addString(Name); | |||
293 | } | |||
294 | ||||
295 | void BTFKindVar::emitType(MCStreamer &OS) { | |||
296 | BTFTypeBase::emitType(OS); | |||
297 | OS.EmitIntValue(Info, 4); | |||
298 | } | |||
299 | ||||
300 | BTFKindDataSec::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 | ||||
307 | void BTFKindDataSec::completeType(BTFDebug &BDebug) { | |||
308 | BTFType.NameOff = BDebug.addString(Name); | |||
309 | BTFType.Info |= Vars.size(); | |||
310 | } | |||
311 | ||||
312 | void 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 | ||||
322 | uint32_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 | ||||
336 | BTFDebug::BTFDebug(AsmPrinter *AP) | |||
337 | : DebugHandlerBase(AP), OS(*Asm->OutStreamer), SkipInstruction(false), | |||
338 | LineInfoGenerated(false), SecNameOff(0), ArrayIndexTypeId(0) { | |||
339 | addString("\0"); | |||
340 | } | |||
341 | ||||
342 | uint32_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 | ||||
351 | uint32_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 | ||||
358 | void 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. | |||
375 | void 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) | |||
382 | return; | |||
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. | |||
401 | void 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 | ||||
427 | void 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 | ||||
466 | void 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. | |||
478 | void 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. | |||
485 | void 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. | |||
501 | void 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 | ||||
519 | void 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 | ||||
538 | void 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 | |||
544 | std::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 | ||||
576 | void 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 | ||||
593 | void 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 | ||||
600 | void 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 | ||||
636 | void 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 | ||||
697 | void BTFDebug::beginFunctionImpl(const MachineFunction *MF) { | |||
698 | auto *SP = MF->getFunction().getSubprogram(); | |||
699 | auto *Unit = SP->getUnit(); | |||
700 | ||||
701 | if (Unit->getEmissionKind() == DICompileUnit::NoDebug) { | |||
| ||||
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; | |||
724 | visitSubroutineType(SP->getType(), true, FuncArgNames, ProtoTypeId); | |||
725 | ||||
726 | // Construct subprogram func type | |||
727 | auto FuncTypeEntry = | |||
728 | llvm::make_unique<BTFTypeFunc>(SP->getName(), ProtoTypeId); | |||
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 | ||||
747 | void BTFDebug::endFunctionImpl(const MachineFunction *MF) { | |||
748 | SkipInstruction = false; | |||
749 | LineInfoGenerated = false; | |||
750 | SecNameOff = 0; | |||
751 | } | |||
752 | ||||
753 | void 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 | ||||
801 | void 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 | ||||
866 | void 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 | } |
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 | ||||
43 | namespace 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. | |||
47 | template <typename T, T> struct SameType; | |||
48 | ||||
49 | namespace detail { | |||
50 | ||||
51 | template <typename RangeT> | |||
52 | using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); | |||
53 | ||||
54 | template <typename RangeT> | |||
55 | using 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 | ||||
64 | template <typename T> | |||
65 | struct negation : std::integral_constant<bool, !bool(T::value)> {}; | |||
66 | ||||
67 | template <typename...> struct conjunction : std::true_type {}; | |||
68 | template <typename B1> struct conjunction<B1> : B1 {}; | |||
69 | template <typename B1, typename... Bn> | |||
70 | struct conjunction<B1, Bn...> | |||
71 | : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {}; | |||
72 | ||||
73 | template <typename T> struct make_const_ptr { | |||
74 | using type = | |||
75 | typename std::add_pointer<typename std::add_const<T>::type>::type; | |||
76 | }; | |||
77 | ||||
78 | template <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 | ||||
87 | template <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 | ||||
98 | template <class Ty> struct less_ptr { | |||
99 | bool operator()(const Ty* left, const Ty* right) const { | |||
100 | return *left < *right; | |||
101 | } | |||
102 | }; | |||
103 | ||||
104 | template <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. | |||
116 | template<typename Fn> class function_ref; | |||
117 | ||||
118 | template<typename Ret, typename ...Params> | |||
119 | class 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 | ||||
129 | public: | |||
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>); | |||
152 | template <class T> | |||
153 | inline void deleter(T *Ptr) { | |||
154 | delete Ptr; | |||
155 | } | |||
156 | ||||
157 | //===----------------------------------------------------------------------===// | |||
158 | // Extra additions to <iterator> | |||
159 | //===----------------------------------------------------------------------===// | |||
160 | ||||
161 | namespace adl_detail { | |||
162 | ||||
163 | using std::begin; | |||
164 | ||||
165 | template <typename ContainerTy> | |||
166 | auto adl_begin(ContainerTy &&container) | |||
167 | -> decltype(begin(std::forward<ContainerTy>(container))) { | |||
168 | return begin(std::forward<ContainerTy>(container)); | |||
169 | } | |||
170 | ||||
171 | using std::end; | |||
172 | ||||
173 | template <typename ContainerTy> | |||
174 | auto adl_end(ContainerTy &&container) | |||
175 | -> decltype(end(std::forward<ContainerTy>(container))) { | |||
176 | return end(std::forward<ContainerTy>(container)); | |||
177 | } | |||
178 | ||||
179 | using std::swap; | |||
180 | ||||
181 | template <typename T> | |||
182 | void 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 | ||||
189 | template <typename ContainerTy> | |||
190 | auto 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 | ||||
195 | template <typename ContainerTy> | |||
196 | auto 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 | ||||
201 | template <typename T> | |||
202 | void 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. | |||
208 | template <typename T> | |||
209 | constexpr 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 | ||||
216 | template <typename ItTy, typename FuncTy, | |||
217 | typename FuncReturnTy = | |||
218 | decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))> | |||
219 | class 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> { | |||
224 | public: | |||
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 | ||||
232 | private: | |||
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... | |||
238 | template <class ItTy, class FuncTy> | |||
239 | inline 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(). | |||
244 | template <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 | ||||
254 | public: | |||
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(). | |||
259 | template <typename Ty> | |||
260 | struct 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. | |||
265 | template <typename ContainerTy> | |||
266 | auto 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. | |||
273 | template <typename IteratorTy> | |||
274 | std::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. | |||
281 | template <typename ContainerTy> | |||
282 | auto 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. | |||
307 | template <typename WrappedIteratorT, typename PredicateT, typename IterTag> | |||
308 | class 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 | ||||
322 | protected: | |||
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 | ||||
340 | public: | |||
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. | |||
351 | template <typename WrappedIteratorT, typename PredicateT, | |||
352 | typename IterTag = std::forward_iterator_tag> | |||
353 | class filter_iterator_impl | |||
354 | : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> { | |||
355 | using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>; | |||
356 | ||||
357 | public: | |||
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. | |||
364 | template <typename WrappedIteratorT, typename PredicateT> | |||
365 | class 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 | ||||
376 | public: | |||
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 | ||||
390 | namespace detail { | |||
391 | ||||
392 | template <bool is_bidirectional> struct fwd_or_bidi_tag_impl { | |||
393 | using type = std::forward_iterator_tag; | |||
394 | }; | |||
395 | ||||
396 | template <> 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. | |||
403 | template <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. | |||
413 | template <typename WrappedIteratorT, typename PredicateT> | |||
414 | using 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. | |||
425 | template <typename RangeT, typename PredicateT> | |||
426 | iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> | |||
427 | make_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. | |||
454 | template <typename WrappedIteratorT> | |||
455 | class 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 | ||||
464 | protected: | |||
465 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 | |||
466 | bool IsEarlyIncremented = false; | |||
467 | #endif | |||
468 | ||||
469 | public: | |||
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. | |||
511 | template <typename RangeT> | |||
512 | iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>> | |||
513 | make_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 | |||
521 | template <typename R, typename UnaryPredicate> | |||
522 | bool all_of(R &&range, UnaryPredicate P); | |||
523 | template <typename R, typename UnaryPredicate> | |||
524 | bool any_of(R &&range, UnaryPredicate P); | |||
525 | ||||
526 | template <size_t... I> struct index_sequence; | |||
527 | ||||
528 | template <class... Ts> struct index_sequence_for; | |||
529 | ||||
530 | namespace detail { | |||
531 | ||||
532 | using 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. | |||
536 | template<typename... Iters> struct ZipTupleType { | |||
537 | using type = std::tuple<decltype(*declval<Iters>())...>; | |||
538 | }; | |||
539 | ||||
540 | template <typename ZipType, typename... Iters> | |||
541 | using 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 | ||||
556 | template <typename ZipType, typename... Iters> | |||
557 | struct 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 | ||||
563 | protected: | |||
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 | ||||
578 | public: | |||
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 | ||||
600 | template <typename... Iters> | |||
601 | struct 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 | ||||
611 | template <typename... Iters> | |||
612 | class 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 | ||||
620 | public: | |||
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 | ||||
630 | template <template <typename...> class ItType, typename... Args> class zippy { | |||
631 | public: | |||
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 | ||||
639 | private: | |||
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 | ||||
649 | public: | |||
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. | |||
659 | template <typename T, typename U, typename... Args> | |||
660 | detail::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. | |||
668 | template <typename T, typename U, typename... Args> | |||
669 | detail::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 | ||||
675 | namespace detail { | |||
676 | template <typename Iter> | |||
677 | static Iter next_or_end(const Iter &I, const Iter &End) { | |||
678 | if (I == End) | |||
679 | return End; | |||
680 | return std::next(I); | |||
681 | } | |||
682 | ||||
683 | template <typename Iter> | |||
684 | static 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 | ||||
692 | template <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 | ||||
698 | template <typename... Iters> struct ZipLongestTupleType { | |||
699 | using type = std::tuple<typename ZipLongestItemType<Iters>::type...>; | |||
700 | }; | |||
701 | ||||
702 | template <typename... Iters> | |||
703 | class 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> { | |||
714 | public: | |||
715 | using value_type = typename ZipLongestTupleType<Iters...>::type; | |||
716 | ||||
717 | private: | |||
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 | ||||
741 | public: | |||
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 | ||||
760 | template <typename... Args> class zip_longest_range { | |||
761 | public: | |||
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 | ||||
770 | private: | |||
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 | ||||
783 | public: | |||
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. | |||
794 | template <typename T, typename U, typename... Args> | |||
795 | detail::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. | |||
811 | template <typename ValueT, typename... IterTs> | |||
812 | class 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 | ||||
885 | public: | |||
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 | ||||
908 | namespace 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. | |||
915 | template <typename ValueT, typename... RangeTs> class concat_range { | |||
916 | public: | |||
917 | using iterator = | |||
918 | concat_iterator<ValueT, | |||
919 | decltype(std::begin(std::declval<RangeTs &>()))...>; | |||
920 | ||||
921 | private: | |||
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 | ||||
932 | public: | |||
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. | |||
945 | template <typename ValueT, typename... RangeTs> | |||
946 | detail::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. | |||
959 | struct 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. | |||
967 | struct 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. | |||
975 | template<typename FuncTy> | |||
976 | struct 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. | |||
989 | template <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. | |||
996 | template <size_t... I> | |||
997 | struct index_sequence : integer_sequence<std::size_t, I...> {}; | |||
998 | ||||
999 | template <std::size_t N, std::size_t... I> | |||
1000 | struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; | |||
1001 | template <std::size_t... I> | |||
1002 | struct build_index_impl<0, I...> : index_sequence<I...> {}; | |||
1003 | ||||
1004 | /// Creates a compile-time integer sequence for a parameter pack. | |||
1005 | template <class... Ts> | |||
1006 | struct 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. | |||
1010 | template <int N> struct rank : rank<N - 1> {}; | |||
1011 | template <> 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. | |||
1015 | template <typename T, typename... Ts> struct is_one_of { | |||
1016 | static const bool value = false; | |||
1017 | }; | |||
1018 | ||||
1019 | template <typename T, typename U, typename... Ts> | |||
1020 | struct 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. | |||
1027 | template <typename T, typename... Ts> struct are_base_of { | |||
1028 | static const bool value = true; | |||
1029 | }; | |||
1030 | ||||
1031 | template <typename T, typename U, typename... Ts> | |||
1032 | struct 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. | |||
1042 | template <class T, std::size_t N> | |||
1043 | constexpr inline size_t array_lengthof(T (&)[N]) { | |||
1044 | return N; | |||
1045 | } | |||
1046 | ||||
1047 | /// Adapt std::less<T> for array_pod_sort. | |||
1048 | template<typename T> | |||
1049 | inline 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. | |||
1061 | template<typename T> | |||
1062 | inline 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. | |||
1081 | template<class IteratorTy> | |||
1082 | inline 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 | ||||
1094 | template <class IteratorTy> | |||
1095 | inline 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). | |||
1114 | template <typename IteratorTy> | |||
1115 | inline 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 | ||||
1123 | template <typename Container> inline void sort(Container &&C) { | |||
1124 | llvm::sort(adl_begin(C), adl_end(C)); | |||
1125 | } | |||
1126 | ||||
1127 | template <typename IteratorTy, typename Compare> | |||
1128 | inline 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 | ||||
1136 | template <typename Container, typename Compare> | |||
1137 | inline 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. | |||
1147 | template<typename Container> | |||
1148 | void 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. | |||
1156 | template<typename Container> | |||
1157 | void 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). | |||
1165 | template <typename R> | |||
1166 | auto 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. | |||
1177 | template <typename R, typename UnaryPredicate> | |||
1178 | UnaryPredicate 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. | |||
1184 | template <typename R, typename UnaryPredicate> | |||
1185 | bool 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. | |||
1191 | template <typename R, typename UnaryPredicate> | |||
1192 | bool 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. | |||
1198 | template <typename R, typename UnaryPredicate> | |||
1199 | bool 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. | |||
1205 | template <typename R, typename T> | |||
1206 | auto 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. | |||
1212 | template <typename R, typename UnaryPredicate> | |||
1213 | auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { | |||
1214 | return std::find_if(adl_begin(Range), adl_end(Range), P); | |||
1215 | } | |||
1216 | ||||
1217 | template <typename R, typename UnaryPredicate> | |||
1218 | auto 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. | |||
1224 | template <typename R, typename UnaryPredicate> | |||
1225 | auto 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. | |||
1231 | template <typename R, typename OutputIt, typename UnaryPredicate> | |||
1232 | OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { | |||
1233 | return std::copy_if(adl_begin(Range), adl_end(Range), Out, P); | |||
1234 | } | |||
1235 | ||||
1236 | template <typename R, typename OutputIt> | |||
1237 | OutputIt 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. | |||
1243 | template <typename R, typename E> | |||
1244 | bool 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. | |||
1250 | template <typename R, typename E> | |||
1251 | auto 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. | |||
1258 | template <typename R, typename UnaryPredicate> | |||
1259 | auto 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. | |||
1266 | template <typename R, typename OutputIt, typename UnaryPredicate> | |||
1267 | OutputIt 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. | |||
1273 | template <typename R, typename UnaryPredicate> | |||
1274 | auto 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. | |||
1280 | template <typename R, typename T> | |||
1281 | auto 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 | ||||
1286 | template <typename R, typename T, typename Compare> | |||
1287 | auto 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. | |||
1295 | template <typename R, typename T> | |||
1296 | auto 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 | ||||
1301 | template <typename R, typename T, typename Compare> | |||
1302 | auto 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 | ||||
1308 | template <typename R> | |||
1309 | void stable_sort(R &&Range) { | |||
1310 | std::stable_sort(adl_begin(Range), adl_end(Range)); | |||
1311 | } | |||
1312 | ||||
1313 | template <typename R, typename Compare> | |||
1314 | void 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! | |||
1328 | template <typename Predicate> | |||
1329 | size_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. | |||
1344 | template <typename It, typename Predicate, | |||
1345 | typename Val = decltype(*std::declval<It>())> | |||
1346 | It 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. | |||
1353 | template <typename R, typename Predicate> | |||
1354 | auto 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. | |||
1360 | template <typename R> | |||
1361 | bool 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. | |||
1370 | template <unsigned Size, typename R> | |||
1371 | SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size> | |||
1372 | to_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. | |||
1383 | template <typename Container, typename UnaryPredicate> | |||
1384 | void 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); | |||
1401 | template <class T, class... Args> | |||
1402 | typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type | |||
1403 | make_unique(Args &&... args) { | |||
1404 | return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); | |||
| ||||
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. | |||
1415 | template <class T> | |||
1416 | typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, | |||
1417 | std::unique_ptr<T>>::type | |||
1418 | make_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. | |||
1423 | template <class T, class... Args> | |||
1424 | typename std::enable_if<std::extent<T>::value != 0>::type | |||
1425 | make_unique(Args &&...) = delete; | |||
1426 | ||||
1427 | struct FreeDeleter { | |||
1428 | void operator()(void* v) { | |||
1429 | ::free(v); | |||
1430 | } | |||
1431 | }; | |||
1432 | ||||
1433 | template<typename First, typename Second> | |||
1434 | struct 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. | |||
1441 | struct 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. | |||
1448 | struct 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. | |||
1456 | template <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 | ||||
1470 | namespace detail { | |||
1471 | ||||
1472 | template <typename R> class enumerator_iter; | |||
1473 | ||||
1474 | template <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 | ||||
1491 | private: | |||
1492 | std::size_t Index = std::numeric_limits<std::size_t>::max(); | |||
1493 | IterOfRange<R> Iter; | |||
1494 | }; | |||
1495 | ||||
1496 | template <typename R> | |||
1497 | class 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 | ||||
1505 | public: | |||
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 | ||||
1534 | private: | |||
1535 | result_type Result; | |||
1536 | }; | |||
1537 | ||||
1538 | template <typename R> class enumerator { | |||
1539 | public: | |||
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 | ||||
1550 | private: | |||
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 | /// | |||
1571 | template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { | |||
1572 | return detail::enumerator<R>(std::forward<R>(TheRange)); | |||
1573 | } | |||
1574 | ||||
1575 | namespace detail { | |||
1576 | ||||
1577 | template <typename F, typename Tuple, std::size_t... I> | |||
1578 | auto 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. | |||
1588 | template <typename F, typename Tuple> | |||
1589 | auto 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. | |||
1602 | template <typename IterTy> | |||
1603 | bool 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. | |||
1619 | template <typename IterTy> | |||
1620 | bool 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. | |||
1642 | template <class Ptr> auto to_address(const Ptr &P) -> decltype(P.operator->()) { | |||
1643 | return P.operator->(); | |||
1644 | } | |||
1645 | template <class T> constexpr T *to_address(T *P) { return P; } | |||
1646 | ||||
1647 | } // end namespace llvm | |||
1648 | ||||
1649 | #endif // LLVM_ADT_STLEXTRAS_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 | |
36 | namespace 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 | |
59 | namespace 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); } |
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 | |
159 | namespace 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 */ |