File: | src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp |
Warning: | line 941, column 58 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===-- PDBASTParser.cpp --------------------------------------------------===// | |||
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 | #include "PDBASTParser.h" | |||
10 | ||||
11 | #include "SymbolFilePDB.h" | |||
12 | ||||
13 | #include "clang/AST/CharUnits.h" | |||
14 | #include "clang/AST/Decl.h" | |||
15 | #include "clang/AST/DeclCXX.h" | |||
16 | ||||
17 | #include "Plugins/ExpressionParser/Clang/ClangASTMetadata.h" | |||
18 | #include "Plugins/ExpressionParser/Clang/ClangUtil.h" | |||
19 | #include "Plugins/TypeSystem/Clang/TypeSystemClang.h" | |||
20 | #include "lldb/Core/Declaration.h" | |||
21 | #include "lldb/Core/Module.h" | |||
22 | #include "lldb/Symbol/SymbolFile.h" | |||
23 | #include "lldb/Symbol/TypeMap.h" | |||
24 | #include "lldb/Symbol/TypeSystem.h" | |||
25 | ||||
26 | #include "llvm/DebugInfo/PDB/IPDBLineNumber.h" | |||
27 | #include "llvm/DebugInfo/PDB/IPDBSourceFile.h" | |||
28 | #include "llvm/DebugInfo/PDB/PDBSymbol.h" | |||
29 | #include "llvm/DebugInfo/PDB/PDBSymbolData.h" | |||
30 | #include "llvm/DebugInfo/PDB/PDBSymbolFunc.h" | |||
31 | #include "llvm/DebugInfo/PDB/PDBSymbolTypeArray.h" | |||
32 | #include "llvm/DebugInfo/PDB/PDBSymbolTypeBuiltin.h" | |||
33 | #include "llvm/DebugInfo/PDB/PDBSymbolTypeEnum.h" | |||
34 | #include "llvm/DebugInfo/PDB/PDBSymbolTypeFunctionArg.h" | |||
35 | #include "llvm/DebugInfo/PDB/PDBSymbolTypeFunctionSig.h" | |||
36 | #include "llvm/DebugInfo/PDB/PDBSymbolTypePointer.h" | |||
37 | #include "llvm/DebugInfo/PDB/PDBSymbolTypeTypedef.h" | |||
38 | #include "llvm/DebugInfo/PDB/PDBSymbolTypeUDT.h" | |||
39 | ||||
40 | #include "Plugins/Language/CPlusPlus/MSVCUndecoratedNameParser.h" | |||
41 | ||||
42 | using namespace lldb; | |||
43 | using namespace lldb_private; | |||
44 | using namespace llvm::pdb; | |||
45 | ||||
46 | static int TranslateUdtKind(PDB_UdtType pdb_kind) { | |||
47 | switch (pdb_kind) { | |||
48 | case PDB_UdtType::Class: | |||
49 | return clang::TTK_Class; | |||
50 | case PDB_UdtType::Struct: | |||
51 | return clang::TTK_Struct; | |||
52 | case PDB_UdtType::Union: | |||
53 | return clang::TTK_Union; | |||
54 | case PDB_UdtType::Interface: | |||
55 | return clang::TTK_Interface; | |||
56 | } | |||
57 | llvm_unreachable("unsuported PDB UDT type")__builtin_unreachable(); | |||
58 | } | |||
59 | ||||
60 | static lldb::Encoding TranslateBuiltinEncoding(PDB_BuiltinType type) { | |||
61 | switch (type) { | |||
62 | case PDB_BuiltinType::Float: | |||
63 | return lldb::eEncodingIEEE754; | |||
64 | case PDB_BuiltinType::Int: | |||
65 | case PDB_BuiltinType::Long: | |||
66 | case PDB_BuiltinType::Char: | |||
67 | return lldb::eEncodingSint; | |||
68 | case PDB_BuiltinType::Bool: | |||
69 | case PDB_BuiltinType::Char16: | |||
70 | case PDB_BuiltinType::Char32: | |||
71 | case PDB_BuiltinType::UInt: | |||
72 | case PDB_BuiltinType::ULong: | |||
73 | case PDB_BuiltinType::HResult: | |||
74 | case PDB_BuiltinType::WCharT: | |||
75 | return lldb::eEncodingUint; | |||
76 | default: | |||
77 | return lldb::eEncodingInvalid; | |||
78 | } | |||
79 | } | |||
80 | ||||
81 | static lldb::Encoding TranslateEnumEncoding(PDB_VariantType type) { | |||
82 | switch (type) { | |||
83 | case PDB_VariantType::Int8: | |||
84 | case PDB_VariantType::Int16: | |||
85 | case PDB_VariantType::Int32: | |||
86 | case PDB_VariantType::Int64: | |||
87 | return lldb::eEncodingSint; | |||
88 | ||||
89 | case PDB_VariantType::UInt8: | |||
90 | case PDB_VariantType::UInt16: | |||
91 | case PDB_VariantType::UInt32: | |||
92 | case PDB_VariantType::UInt64: | |||
93 | return lldb::eEncodingUint; | |||
94 | ||||
95 | default: | |||
96 | break; | |||
97 | } | |||
98 | ||||
99 | return lldb::eEncodingSint; | |||
100 | } | |||
101 | ||||
102 | static CompilerType | |||
103 | GetBuiltinTypeForPDBEncodingAndBitSize(TypeSystemClang &clang_ast, | |||
104 | const PDBSymbolTypeBuiltin &pdb_type, | |||
105 | Encoding encoding, uint32_t width) { | |||
106 | clang::ASTContext &ast = clang_ast.getASTContext(); | |||
107 | ||||
108 | switch (pdb_type.getBuiltinType()) { | |||
109 | default: | |||
110 | break; | |||
111 | case PDB_BuiltinType::None: | |||
112 | return CompilerType(); | |||
113 | case PDB_BuiltinType::Void: | |||
114 | return clang_ast.GetBasicType(eBasicTypeVoid); | |||
115 | case PDB_BuiltinType::Char: | |||
116 | return clang_ast.GetBasicType(eBasicTypeChar); | |||
117 | case PDB_BuiltinType::Bool: | |||
118 | return clang_ast.GetBasicType(eBasicTypeBool); | |||
119 | case PDB_BuiltinType::Long: | |||
120 | if (width == ast.getTypeSize(ast.LongTy)) | |||
121 | return CompilerType(&clang_ast, ast.LongTy.getAsOpaquePtr()); | |||
122 | if (width == ast.getTypeSize(ast.LongLongTy)) | |||
123 | return CompilerType(&clang_ast, ast.LongLongTy.getAsOpaquePtr()); | |||
124 | break; | |||
125 | case PDB_BuiltinType::ULong: | |||
126 | if (width == ast.getTypeSize(ast.UnsignedLongTy)) | |||
127 | return CompilerType(&clang_ast, ast.UnsignedLongTy.getAsOpaquePtr()); | |||
128 | if (width == ast.getTypeSize(ast.UnsignedLongLongTy)) | |||
129 | return CompilerType(&clang_ast, ast.UnsignedLongLongTy.getAsOpaquePtr()); | |||
130 | break; | |||
131 | case PDB_BuiltinType::WCharT: | |||
132 | if (width == ast.getTypeSize(ast.WCharTy)) | |||
133 | return CompilerType(&clang_ast, ast.WCharTy.getAsOpaquePtr()); | |||
134 | break; | |||
135 | case PDB_BuiltinType::Char16: | |||
136 | return CompilerType(&clang_ast, ast.Char16Ty.getAsOpaquePtr()); | |||
137 | case PDB_BuiltinType::Char32: | |||
138 | return CompilerType(&clang_ast, ast.Char32Ty.getAsOpaquePtr()); | |||
139 | case PDB_BuiltinType::Float: | |||
140 | // Note: types `long double` and `double` have same bit size in MSVC and | |||
141 | // there is no information in the PDB to distinguish them. So when falling | |||
142 | // back to default search, the compiler type of `long double` will be | |||
143 | // represented by the one generated for `double`. | |||
144 | break; | |||
145 | } | |||
146 | // If there is no match on PDB_BuiltinType, fall back to default search by | |||
147 | // encoding and width only | |||
148 | return clang_ast.GetBuiltinTypeForEncodingAndBitSize(encoding, width); | |||
149 | } | |||
150 | ||||
151 | static ConstString GetPDBBuiltinTypeName(const PDBSymbolTypeBuiltin &pdb_type, | |||
152 | CompilerType &compiler_type) { | |||
153 | PDB_BuiltinType kind = pdb_type.getBuiltinType(); | |||
154 | switch (kind) { | |||
155 | default: | |||
156 | break; | |||
157 | case PDB_BuiltinType::Currency: | |||
158 | return ConstString("CURRENCY"); | |||
159 | case PDB_BuiltinType::Date: | |||
160 | return ConstString("DATE"); | |||
161 | case PDB_BuiltinType::Variant: | |||
162 | return ConstString("VARIANT"); | |||
163 | case PDB_BuiltinType::Complex: | |||
164 | return ConstString("complex"); | |||
165 | case PDB_BuiltinType::Bitfield: | |||
166 | return ConstString("bitfield"); | |||
167 | case PDB_BuiltinType::BSTR: | |||
168 | return ConstString("BSTR"); | |||
169 | case PDB_BuiltinType::HResult: | |||
170 | return ConstString("HRESULT"); | |||
171 | case PDB_BuiltinType::BCD: | |||
172 | return ConstString("BCD"); | |||
173 | case PDB_BuiltinType::Char16: | |||
174 | return ConstString("char16_t"); | |||
175 | case PDB_BuiltinType::Char32: | |||
176 | return ConstString("char32_t"); | |||
177 | case PDB_BuiltinType::None: | |||
178 | return ConstString("..."); | |||
179 | } | |||
180 | return compiler_type.GetTypeName(); | |||
181 | } | |||
182 | ||||
183 | static bool GetDeclarationForSymbol(const PDBSymbol &symbol, | |||
184 | Declaration &decl) { | |||
185 | auto &raw_sym = symbol.getRawSymbol(); | |||
186 | auto first_line_up = raw_sym.getSrcLineOnTypeDefn(); | |||
187 | ||||
188 | if (!first_line_up) { | |||
189 | auto lines_up = symbol.getSession().findLineNumbersByAddress( | |||
190 | raw_sym.getVirtualAddress(), raw_sym.getLength()); | |||
191 | if (!lines_up) | |||
192 | return false; | |||
193 | first_line_up = lines_up->getNext(); | |||
194 | if (!first_line_up) | |||
195 | return false; | |||
196 | } | |||
197 | uint32_t src_file_id = first_line_up->getSourceFileId(); | |||
198 | auto src_file_up = symbol.getSession().getSourceFileById(src_file_id); | |||
199 | if (!src_file_up) | |||
200 | return false; | |||
201 | ||||
202 | FileSpec spec(src_file_up->getFileName()); | |||
203 | decl.SetFile(spec); | |||
204 | decl.SetColumn(first_line_up->getColumnNumber()); | |||
205 | decl.SetLine(first_line_up->getLineNumber()); | |||
206 | return true; | |||
207 | } | |||
208 | ||||
209 | static AccessType TranslateMemberAccess(PDB_MemberAccess access) { | |||
210 | switch (access) { | |||
211 | case PDB_MemberAccess::Private: | |||
212 | return eAccessPrivate; | |||
213 | case PDB_MemberAccess::Protected: | |||
214 | return eAccessProtected; | |||
215 | case PDB_MemberAccess::Public: | |||
216 | return eAccessPublic; | |||
217 | } | |||
218 | return eAccessNone; | |||
219 | } | |||
220 | ||||
221 | static AccessType GetDefaultAccessibilityForUdtKind(PDB_UdtType udt_kind) { | |||
222 | switch (udt_kind) { | |||
223 | case PDB_UdtType::Struct: | |||
224 | case PDB_UdtType::Union: | |||
225 | return eAccessPublic; | |||
226 | case PDB_UdtType::Class: | |||
227 | case PDB_UdtType::Interface: | |||
228 | return eAccessPrivate; | |||
229 | } | |||
230 | llvm_unreachable("unsupported PDB UDT type")__builtin_unreachable(); | |||
231 | } | |||
232 | ||||
233 | static AccessType GetAccessibilityForUdt(const PDBSymbolTypeUDT &udt) { | |||
234 | AccessType access = TranslateMemberAccess(udt.getAccess()); | |||
235 | if (access != lldb::eAccessNone || !udt.isNested()) | |||
236 | return access; | |||
237 | ||||
238 | auto parent = udt.getClassParent(); | |||
239 | if (!parent) | |||
240 | return lldb::eAccessNone; | |||
241 | ||||
242 | auto parent_udt = llvm::dyn_cast<PDBSymbolTypeUDT>(parent.get()); | |||
243 | if (!parent_udt) | |||
244 | return lldb::eAccessNone; | |||
245 | ||||
246 | return GetDefaultAccessibilityForUdtKind(parent_udt->getUdtKind()); | |||
247 | } | |||
248 | ||||
249 | static clang::MSInheritanceAttr::Spelling | |||
250 | GetMSInheritance(const PDBSymbolTypeUDT &udt) { | |||
251 | int base_count = 0; | |||
252 | bool has_virtual = false; | |||
253 | ||||
254 | auto bases_enum = udt.findAllChildren<PDBSymbolTypeBaseClass>(); | |||
255 | if (bases_enum) { | |||
256 | while (auto base = bases_enum->getNext()) { | |||
257 | base_count++; | |||
258 | has_virtual |= base->isVirtualBaseClass(); | |||
259 | } | |||
260 | } | |||
261 | ||||
262 | if (has_virtual) | |||
263 | return clang::MSInheritanceAttr::Keyword_virtual_inheritance; | |||
264 | if (base_count > 1) | |||
265 | return clang::MSInheritanceAttr::Keyword_multiple_inheritance; | |||
266 | return clang::MSInheritanceAttr::Keyword_single_inheritance; | |||
267 | } | |||
268 | ||||
269 | static std::unique_ptr<llvm::pdb::PDBSymbol> | |||
270 | GetClassOrFunctionParent(const llvm::pdb::PDBSymbol &symbol) { | |||
271 | const IPDBSession &session = symbol.getSession(); | |||
272 | const IPDBRawSymbol &raw = symbol.getRawSymbol(); | |||
273 | auto tag = symbol.getSymTag(); | |||
274 | ||||
275 | // For items that are nested inside of a class, return the class that it is | |||
276 | // nested inside of. | |||
277 | // Note that only certain items can be nested inside of classes. | |||
278 | switch (tag) { | |||
279 | case PDB_SymType::Function: | |||
280 | case PDB_SymType::Data: | |||
281 | case PDB_SymType::UDT: | |||
282 | case PDB_SymType::Enum: | |||
283 | case PDB_SymType::FunctionSig: | |||
284 | case PDB_SymType::Typedef: | |||
285 | case PDB_SymType::BaseClass: | |||
286 | case PDB_SymType::VTable: { | |||
287 | auto class_parent_id = raw.getClassParentId(); | |||
288 | if (auto class_parent = session.getSymbolById(class_parent_id)) | |||
289 | return class_parent; | |||
290 | break; | |||
291 | } | |||
292 | default: | |||
293 | break; | |||
294 | } | |||
295 | ||||
296 | // Otherwise, if it is nested inside of a function, return the function. | |||
297 | // Note that only certain items can be nested inside of functions. | |||
298 | switch (tag) { | |||
299 | case PDB_SymType::Block: | |||
300 | case PDB_SymType::Data: { | |||
301 | auto lexical_parent_id = raw.getLexicalParentId(); | |||
302 | auto lexical_parent = session.getSymbolById(lexical_parent_id); | |||
303 | if (!lexical_parent) | |||
304 | return nullptr; | |||
305 | ||||
306 | auto lexical_parent_tag = lexical_parent->getSymTag(); | |||
307 | if (lexical_parent_tag == PDB_SymType::Function) | |||
308 | return lexical_parent; | |||
309 | if (lexical_parent_tag == PDB_SymType::Exe) | |||
310 | return nullptr; | |||
311 | ||||
312 | return GetClassOrFunctionParent(*lexical_parent); | |||
313 | } | |||
314 | default: | |||
315 | return nullptr; | |||
316 | } | |||
317 | } | |||
318 | ||||
319 | static clang::NamedDecl * | |||
320 | GetDeclFromContextByName(const clang::ASTContext &ast, | |||
321 | const clang::DeclContext &decl_context, | |||
322 | llvm::StringRef name) { | |||
323 | clang::IdentifierInfo &ident = ast.Idents.get(name); | |||
324 | clang::DeclarationName decl_name = ast.DeclarationNames.getIdentifier(&ident); | |||
325 | clang::DeclContext::lookup_result result = decl_context.lookup(decl_name); | |||
326 | if (result.empty()) | |||
327 | return nullptr; | |||
328 | ||||
329 | return *result.begin(); | |||
330 | } | |||
331 | ||||
332 | static bool IsAnonymousNamespaceName(llvm::StringRef name) { | |||
333 | return name == "`anonymous namespace'" || name == "`anonymous-namespace'"; | |||
334 | } | |||
335 | ||||
336 | static clang::CallingConv TranslateCallingConvention(PDB_CallingConv pdb_cc) { | |||
337 | switch (pdb_cc) { | |||
338 | case llvm::codeview::CallingConvention::NearC: | |||
339 | return clang::CC_C; | |||
340 | case llvm::codeview::CallingConvention::NearStdCall: | |||
341 | return clang::CC_X86StdCall; | |||
342 | case llvm::codeview::CallingConvention::NearFast: | |||
343 | return clang::CC_X86FastCall; | |||
344 | case llvm::codeview::CallingConvention::ThisCall: | |||
345 | return clang::CC_X86ThisCall; | |||
346 | case llvm::codeview::CallingConvention::NearVector: | |||
347 | return clang::CC_X86VectorCall; | |||
348 | case llvm::codeview::CallingConvention::NearPascal: | |||
349 | return clang::CC_X86Pascal; | |||
350 | default: | |||
351 | assert(false && "Unknown calling convention")((void)0); | |||
352 | return clang::CC_C; | |||
353 | } | |||
354 | } | |||
355 | ||||
356 | PDBASTParser::PDBASTParser(lldb_private::TypeSystemClang &ast) : m_ast(ast) {} | |||
357 | ||||
358 | PDBASTParser::~PDBASTParser() = default; | |||
359 | ||||
360 | // DebugInfoASTParser interface | |||
361 | ||||
362 | lldb::TypeSP PDBASTParser::CreateLLDBTypeFromPDBType(const PDBSymbol &type) { | |||
363 | Declaration decl; | |||
364 | switch (type.getSymTag()) { | |||
365 | case PDB_SymType::BaseClass: { | |||
366 | auto symbol_file = m_ast.GetSymbolFile(); | |||
367 | if (!symbol_file) | |||
368 | return nullptr; | |||
369 | ||||
370 | auto ty = symbol_file->ResolveTypeUID(type.getRawSymbol().getTypeId()); | |||
371 | return ty ? ty->shared_from_this() : nullptr; | |||
372 | } break; | |||
373 | case PDB_SymType::UDT: { | |||
374 | auto udt = llvm::dyn_cast<PDBSymbolTypeUDT>(&type); | |||
375 | assert(udt)((void)0); | |||
376 | ||||
377 | // Note that, unnamed UDT being typedef-ed is generated as a UDT symbol | |||
378 | // other than a Typedef symbol in PDB. For example, | |||
379 | // typedef union { short Row; short Col; } Union; | |||
380 | // is generated as a named UDT in PDB: | |||
381 | // union Union { short Row; short Col; } | |||
382 | // Such symbols will be handled here. | |||
383 | ||||
384 | // Some UDT with trival ctor has zero length. Just ignore. | |||
385 | if (udt->getLength() == 0) | |||
386 | return nullptr; | |||
387 | ||||
388 | // Ignore unnamed-tag UDTs. | |||
389 | std::string name = | |||
390 | std::string(MSVCUndecoratedNameParser::DropScope(udt->getName())); | |||
391 | if (name.empty()) | |||
392 | return nullptr; | |||
393 | ||||
394 | auto decl_context = GetDeclContextContainingSymbol(type); | |||
395 | ||||
396 | // Check if such an UDT already exists in the current context. | |||
397 | // This may occur with const or volatile types. There are separate type | |||
398 | // symbols in PDB for types with const or volatile modifiers, but we need | |||
399 | // to create only one declaration for them all. | |||
400 | Type::ResolveState type_resolve_state; | |||
401 | CompilerType clang_type = m_ast.GetTypeForIdentifier<clang::CXXRecordDecl>( | |||
402 | ConstString(name), decl_context); | |||
403 | if (!clang_type.IsValid()) { | |||
404 | auto access = GetAccessibilityForUdt(*udt); | |||
405 | ||||
406 | auto tag_type_kind = TranslateUdtKind(udt->getUdtKind()); | |||
407 | ||||
408 | ClangASTMetadata metadata; | |||
409 | metadata.SetUserID(type.getSymIndexId()); | |||
410 | metadata.SetIsDynamicCXXType(false); | |||
411 | ||||
412 | clang_type = m_ast.CreateRecordType( | |||
413 | decl_context, OptionalClangModuleID(), access, name, tag_type_kind, | |||
414 | lldb::eLanguageTypeC_plus_plus, &metadata); | |||
415 | assert(clang_type.IsValid())((void)0); | |||
416 | ||||
417 | auto record_decl = | |||
418 | m_ast.GetAsCXXRecordDecl(clang_type.GetOpaqueQualType()); | |||
419 | assert(record_decl)((void)0); | |||
420 | m_uid_to_decl[type.getSymIndexId()] = record_decl; | |||
421 | ||||
422 | auto inheritance_attr = clang::MSInheritanceAttr::CreateImplicit( | |||
423 | m_ast.getASTContext(), GetMSInheritance(*udt)); | |||
424 | record_decl->addAttr(inheritance_attr); | |||
425 | ||||
426 | TypeSystemClang::StartTagDeclarationDefinition(clang_type); | |||
427 | ||||
428 | auto children = udt->findAllChildren(); | |||
429 | if (!children || children->getChildCount() == 0) { | |||
430 | // PDB does not have symbol of forwarder. We assume we get an udt w/o | |||
431 | // any fields. Just complete it at this point. | |||
432 | TypeSystemClang::CompleteTagDeclarationDefinition(clang_type); | |||
433 | ||||
434 | TypeSystemClang::SetHasExternalStorage(clang_type.GetOpaqueQualType(), | |||
435 | false); | |||
436 | ||||
437 | type_resolve_state = Type::ResolveState::Full; | |||
438 | } else { | |||
439 | // Add the type to the forward declarations. It will help us to avoid | |||
440 | // an endless recursion in CompleteTypeFromUdt function. | |||
441 | m_forward_decl_to_uid[record_decl] = type.getSymIndexId(); | |||
442 | ||||
443 | TypeSystemClang::SetHasExternalStorage(clang_type.GetOpaqueQualType(), | |||
444 | true); | |||
445 | ||||
446 | type_resolve_state = Type::ResolveState::Forward; | |||
447 | } | |||
448 | } else | |||
449 | type_resolve_state = Type::ResolveState::Forward; | |||
450 | ||||
451 | if (udt->isConstType()) | |||
452 | clang_type = clang_type.AddConstModifier(); | |||
453 | ||||
454 | if (udt->isVolatileType()) | |||
455 | clang_type = clang_type.AddVolatileModifier(); | |||
456 | ||||
457 | GetDeclarationForSymbol(type, decl); | |||
458 | return std::make_shared<lldb_private::Type>( | |||
459 | type.getSymIndexId(), m_ast.GetSymbolFile(), ConstString(name), | |||
460 | udt->getLength(), nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, | |||
461 | lldb_private::Type::eEncodingIsUID, decl, clang_type, | |||
462 | type_resolve_state); | |||
463 | } break; | |||
464 | case PDB_SymType::Enum: { | |||
465 | auto enum_type = llvm::dyn_cast<PDBSymbolTypeEnum>(&type); | |||
466 | assert(enum_type)((void)0); | |||
467 | ||||
468 | std::string name = | |||
469 | std::string(MSVCUndecoratedNameParser::DropScope(enum_type->getName())); | |||
470 | auto decl_context = GetDeclContextContainingSymbol(type); | |||
471 | uint64_t bytes = enum_type->getLength(); | |||
472 | ||||
473 | // Check if such an enum already exists in the current context | |||
474 | CompilerType ast_enum = m_ast.GetTypeForIdentifier<clang::EnumDecl>( | |||
475 | ConstString(name), decl_context); | |||
476 | if (!ast_enum.IsValid()) { | |||
477 | auto underlying_type_up = enum_type->getUnderlyingType(); | |||
478 | if (!underlying_type_up) | |||
479 | return nullptr; | |||
480 | ||||
481 | lldb::Encoding encoding = | |||
482 | TranslateBuiltinEncoding(underlying_type_up->getBuiltinType()); | |||
483 | // FIXME: Type of underlying builtin is always `Int`. We correct it with | |||
484 | // the very first enumerator's encoding if any. | |||
485 | auto first_child = enum_type->findOneChild<PDBSymbolData>(); | |||
486 | if (first_child) | |||
487 | encoding = TranslateEnumEncoding(first_child->getValue().Type); | |||
488 | ||||
489 | CompilerType builtin_type; | |||
490 | if (bytes > 0) | |||
491 | builtin_type = GetBuiltinTypeForPDBEncodingAndBitSize( | |||
492 | m_ast, *underlying_type_up, encoding, bytes * 8); | |||
493 | else | |||
494 | builtin_type = m_ast.GetBasicType(eBasicTypeInt); | |||
495 | ||||
496 | // FIXME: PDB does not have information about scoped enumeration (Enum | |||
497 | // Class). Set it false for now. | |||
498 | bool isScoped = false; | |||
499 | ||||
500 | ast_enum = m_ast.CreateEnumerationType(name.c_str(), decl_context, | |||
501 | OptionalClangModuleID(), decl, | |||
502 | builtin_type, isScoped); | |||
503 | ||||
504 | auto enum_decl = TypeSystemClang::GetAsEnumDecl(ast_enum); | |||
505 | assert(enum_decl)((void)0); | |||
506 | m_uid_to_decl[type.getSymIndexId()] = enum_decl; | |||
507 | ||||
508 | auto enum_values = enum_type->findAllChildren<PDBSymbolData>(); | |||
509 | if (enum_values) { | |||
510 | while (auto enum_value = enum_values->getNext()) { | |||
511 | if (enum_value->getDataKind() != PDB_DataKind::Constant) | |||
512 | continue; | |||
513 | AddEnumValue(ast_enum, *enum_value); | |||
514 | } | |||
515 | } | |||
516 | ||||
517 | if (TypeSystemClang::StartTagDeclarationDefinition(ast_enum)) | |||
518 | TypeSystemClang::CompleteTagDeclarationDefinition(ast_enum); | |||
519 | } | |||
520 | ||||
521 | if (enum_type->isConstType()) | |||
522 | ast_enum = ast_enum.AddConstModifier(); | |||
523 | ||||
524 | if (enum_type->isVolatileType()) | |||
525 | ast_enum = ast_enum.AddVolatileModifier(); | |||
526 | ||||
527 | GetDeclarationForSymbol(type, decl); | |||
528 | return std::make_shared<lldb_private::Type>( | |||
529 | type.getSymIndexId(), m_ast.GetSymbolFile(), ConstString(name), bytes, | |||
530 | nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, lldb_private::Type::eEncodingIsUID, decl, | |||
531 | ast_enum, lldb_private::Type::ResolveState::Full); | |||
532 | } break; | |||
533 | case PDB_SymType::Typedef: { | |||
534 | auto type_def = llvm::dyn_cast<PDBSymbolTypeTypedef>(&type); | |||
535 | assert(type_def)((void)0); | |||
536 | ||||
537 | SymbolFile *symbol_file = m_ast.GetSymbolFile(); | |||
538 | if (!symbol_file) | |||
539 | return nullptr; | |||
540 | ||||
541 | lldb_private::Type *target_type = | |||
542 | symbol_file->ResolveTypeUID(type_def->getTypeId()); | |||
543 | if (!target_type) | |||
544 | return nullptr; | |||
545 | ||||
546 | std::string name = | |||
547 | std::string(MSVCUndecoratedNameParser::DropScope(type_def->getName())); | |||
548 | auto decl_ctx = GetDeclContextContainingSymbol(type); | |||
549 | ||||
550 | // Check if such a typedef already exists in the current context | |||
551 | CompilerType ast_typedef = | |||
552 | m_ast.GetTypeForIdentifier<clang::TypedefNameDecl>(ConstString(name), | |||
553 | decl_ctx); | |||
554 | if (!ast_typedef.IsValid()) { | |||
555 | CompilerType target_ast_type = target_type->GetFullCompilerType(); | |||
556 | ||||
557 | ast_typedef = target_ast_type.CreateTypedef( | |||
558 | name.c_str(), m_ast.CreateDeclContext(decl_ctx), 0); | |||
559 | if (!ast_typedef) | |||
560 | return nullptr; | |||
561 | ||||
562 | auto typedef_decl = TypeSystemClang::GetAsTypedefDecl(ast_typedef); | |||
563 | assert(typedef_decl)((void)0); | |||
564 | m_uid_to_decl[type.getSymIndexId()] = typedef_decl; | |||
565 | } | |||
566 | ||||
567 | if (type_def->isConstType()) | |||
568 | ast_typedef = ast_typedef.AddConstModifier(); | |||
569 | ||||
570 | if (type_def->isVolatileType()) | |||
571 | ast_typedef = ast_typedef.AddVolatileModifier(); | |||
572 | ||||
573 | GetDeclarationForSymbol(type, decl); | |||
574 | llvm::Optional<uint64_t> size; | |||
575 | if (type_def->getLength()) | |||
576 | size = type_def->getLength(); | |||
577 | return std::make_shared<lldb_private::Type>( | |||
578 | type_def->getSymIndexId(), m_ast.GetSymbolFile(), ConstString(name), | |||
579 | size, nullptr, target_type->GetID(), | |||
580 | lldb_private::Type::eEncodingIsTypedefUID, decl, ast_typedef, | |||
581 | lldb_private::Type::ResolveState::Full); | |||
582 | } break; | |||
583 | case PDB_SymType::Function: | |||
584 | case PDB_SymType::FunctionSig: { | |||
585 | std::string name; | |||
586 | PDBSymbolTypeFunctionSig *func_sig = nullptr; | |||
587 | if (auto pdb_func = llvm::dyn_cast<PDBSymbolFunc>(&type)) { | |||
588 | if (pdb_func->isCompilerGenerated()) | |||
589 | return nullptr; | |||
590 | ||||
591 | auto sig = pdb_func->getSignature(); | |||
592 | if (!sig) | |||
593 | return nullptr; | |||
594 | func_sig = sig.release(); | |||
595 | // Function type is named. | |||
596 | name = std::string( | |||
597 | MSVCUndecoratedNameParser::DropScope(pdb_func->getName())); | |||
598 | } else if (auto pdb_func_sig = | |||
599 | llvm::dyn_cast<PDBSymbolTypeFunctionSig>(&type)) { | |||
600 | func_sig = const_cast<PDBSymbolTypeFunctionSig *>(pdb_func_sig); | |||
601 | } else | |||
602 | llvm_unreachable("Unexpected PDB symbol!")__builtin_unreachable(); | |||
603 | ||||
604 | auto arg_enum = func_sig->getArguments(); | |||
605 | uint32_t num_args = arg_enum->getChildCount(); | |||
606 | std::vector<CompilerType> arg_list; | |||
607 | ||||
608 | bool is_variadic = func_sig->isCVarArgs(); | |||
609 | // Drop last variadic argument. | |||
610 | if (is_variadic) | |||
611 | --num_args; | |||
612 | for (uint32_t arg_idx = 0; arg_idx < num_args; arg_idx++) { | |||
613 | auto arg = arg_enum->getChildAtIndex(arg_idx); | |||
614 | if (!arg) | |||
615 | break; | |||
616 | ||||
617 | SymbolFile *symbol_file = m_ast.GetSymbolFile(); | |||
618 | if (!symbol_file) | |||
619 | return nullptr; | |||
620 | ||||
621 | lldb_private::Type *arg_type = | |||
622 | symbol_file->ResolveTypeUID(arg->getSymIndexId()); | |||
623 | // If there's some error looking up one of the dependent types of this | |||
624 | // function signature, bail. | |||
625 | if (!arg_type) | |||
626 | return nullptr; | |||
627 | CompilerType arg_ast_type = arg_type->GetFullCompilerType(); | |||
628 | arg_list.push_back(arg_ast_type); | |||
629 | } | |||
630 | lldbassert(arg_list.size() <= num_args)lldb_private::lldb_assert(static_cast<bool>(arg_list.size () <= num_args), "arg_list.size() <= num_args", __FUNCTION__ , "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , 630); | |||
631 | ||||
632 | auto pdb_return_type = func_sig->getReturnType(); | |||
633 | SymbolFile *symbol_file = m_ast.GetSymbolFile(); | |||
634 | if (!symbol_file) | |||
635 | return nullptr; | |||
636 | ||||
637 | lldb_private::Type *return_type = | |||
638 | symbol_file->ResolveTypeUID(pdb_return_type->getSymIndexId()); | |||
639 | // If there's some error looking up one of the dependent types of this | |||
640 | // function signature, bail. | |||
641 | if (!return_type) | |||
642 | return nullptr; | |||
643 | CompilerType return_ast_type = return_type->GetFullCompilerType(); | |||
644 | uint32_t type_quals = 0; | |||
645 | if (func_sig->isConstType()) | |||
646 | type_quals |= clang::Qualifiers::Const; | |||
647 | if (func_sig->isVolatileType()) | |||
648 | type_quals |= clang::Qualifiers::Volatile; | |||
649 | auto cc = TranslateCallingConvention(func_sig->getCallingConvention()); | |||
650 | CompilerType func_sig_ast_type = | |||
651 | m_ast.CreateFunctionType(return_ast_type, arg_list.data(), | |||
652 | arg_list.size(), is_variadic, type_quals, cc); | |||
653 | ||||
654 | GetDeclarationForSymbol(type, decl); | |||
655 | return std::make_shared<lldb_private::Type>( | |||
656 | type.getSymIndexId(), m_ast.GetSymbolFile(), ConstString(name), | |||
657 | llvm::None, nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, | |||
658 | lldb_private::Type::eEncodingIsUID, decl, func_sig_ast_type, | |||
659 | lldb_private::Type::ResolveState::Full); | |||
660 | } break; | |||
661 | case PDB_SymType::ArrayType: { | |||
662 | auto array_type = llvm::dyn_cast<PDBSymbolTypeArray>(&type); | |||
663 | assert(array_type)((void)0); | |||
664 | uint32_t num_elements = array_type->getCount(); | |||
665 | uint32_t element_uid = array_type->getElementTypeId(); | |||
666 | llvm::Optional<uint64_t> bytes; | |||
667 | if (uint64_t size = array_type->getLength()) | |||
668 | bytes = size; | |||
669 | ||||
670 | SymbolFile *symbol_file = m_ast.GetSymbolFile(); | |||
671 | if (!symbol_file) | |||
672 | return nullptr; | |||
673 | ||||
674 | // If array rank > 0, PDB gives the element type at N=0. So element type | |||
675 | // will parsed in the order N=0, N=1,..., N=rank sequentially. | |||
676 | lldb_private::Type *element_type = symbol_file->ResolveTypeUID(element_uid); | |||
677 | if (!element_type) | |||
678 | return nullptr; | |||
679 | ||||
680 | CompilerType element_ast_type = element_type->GetForwardCompilerType(); | |||
681 | // If element type is UDT, it needs to be complete. | |||
682 | if (TypeSystemClang::IsCXXClassType(element_ast_type) && | |||
683 | !element_ast_type.GetCompleteType()) { | |||
684 | if (TypeSystemClang::StartTagDeclarationDefinition(element_ast_type)) { | |||
685 | TypeSystemClang::CompleteTagDeclarationDefinition(element_ast_type); | |||
686 | } else { | |||
687 | // We are not able to start defintion. | |||
688 | return nullptr; | |||
689 | } | |||
690 | } | |||
691 | CompilerType array_ast_type = m_ast.CreateArrayType( | |||
692 | element_ast_type, num_elements, /*is_gnu_vector*/ false); | |||
693 | TypeSP type_sp = std::make_shared<lldb_private::Type>( | |||
694 | array_type->getSymIndexId(), m_ast.GetSymbolFile(), ConstString(), | |||
695 | bytes, nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, lldb_private::Type::eEncodingIsUID, | |||
696 | decl, array_ast_type, lldb_private::Type::ResolveState::Full); | |||
697 | type_sp->SetEncodingType(element_type); | |||
698 | return type_sp; | |||
699 | } break; | |||
700 | case PDB_SymType::BuiltinType: { | |||
701 | auto *builtin_type = llvm::dyn_cast<PDBSymbolTypeBuiltin>(&type); | |||
702 | assert(builtin_type)((void)0); | |||
703 | PDB_BuiltinType builtin_kind = builtin_type->getBuiltinType(); | |||
704 | if (builtin_kind == PDB_BuiltinType::None) | |||
705 | return nullptr; | |||
706 | ||||
707 | llvm::Optional<uint64_t> bytes; | |||
708 | if (uint64_t size = builtin_type->getLength()) | |||
709 | bytes = size; | |||
710 | Encoding encoding = TranslateBuiltinEncoding(builtin_kind); | |||
711 | CompilerType builtin_ast_type = GetBuiltinTypeForPDBEncodingAndBitSize( | |||
712 | m_ast, *builtin_type, encoding, bytes.getValueOr(0) * 8); | |||
713 | ||||
714 | if (builtin_type->isConstType()) | |||
715 | builtin_ast_type = builtin_ast_type.AddConstModifier(); | |||
716 | ||||
717 | if (builtin_type->isVolatileType()) | |||
718 | builtin_ast_type = builtin_ast_type.AddVolatileModifier(); | |||
719 | ||||
720 | auto type_name = GetPDBBuiltinTypeName(*builtin_type, builtin_ast_type); | |||
721 | ||||
722 | return std::make_shared<lldb_private::Type>( | |||
723 | builtin_type->getSymIndexId(), m_ast.GetSymbolFile(), type_name, bytes, | |||
724 | nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, lldb_private::Type::eEncodingIsUID, decl, | |||
725 | builtin_ast_type, lldb_private::Type::ResolveState::Full); | |||
726 | } break; | |||
727 | case PDB_SymType::PointerType: { | |||
728 | auto *pointer_type = llvm::dyn_cast<PDBSymbolTypePointer>(&type); | |||
729 | assert(pointer_type)((void)0); | |||
730 | ||||
731 | SymbolFile *symbol_file = m_ast.GetSymbolFile(); | |||
732 | if (!symbol_file) | |||
733 | return nullptr; | |||
734 | ||||
735 | Type *pointee_type = symbol_file->ResolveTypeUID( | |||
736 | pointer_type->getPointeeType()->getSymIndexId()); | |||
737 | if (!pointee_type) | |||
738 | return nullptr; | |||
739 | ||||
740 | if (pointer_type->isPointerToDataMember() || | |||
741 | pointer_type->isPointerToMemberFunction()) { | |||
742 | auto class_parent_uid = pointer_type->getRawSymbol().getClassParentId(); | |||
743 | auto class_parent_type = symbol_file->ResolveTypeUID(class_parent_uid); | |||
744 | assert(class_parent_type)((void)0); | |||
745 | ||||
746 | CompilerType pointer_ast_type; | |||
747 | pointer_ast_type = TypeSystemClang::CreateMemberPointerType( | |||
748 | class_parent_type->GetLayoutCompilerType(), | |||
749 | pointee_type->GetForwardCompilerType()); | |||
750 | assert(pointer_ast_type)((void)0); | |||
751 | ||||
752 | return std::make_shared<lldb_private::Type>( | |||
753 | pointer_type->getSymIndexId(), m_ast.GetSymbolFile(), ConstString(), | |||
754 | pointer_type->getLength(), nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, | |||
755 | lldb_private::Type::eEncodingIsUID, decl, pointer_ast_type, | |||
756 | lldb_private::Type::ResolveState::Forward); | |||
757 | } | |||
758 | ||||
759 | CompilerType pointer_ast_type; | |||
760 | pointer_ast_type = pointee_type->GetFullCompilerType(); | |||
761 | if (pointer_type->isReference()) | |||
762 | pointer_ast_type = pointer_ast_type.GetLValueReferenceType(); | |||
763 | else if (pointer_type->isRValueReference()) | |||
764 | pointer_ast_type = pointer_ast_type.GetRValueReferenceType(); | |||
765 | else | |||
766 | pointer_ast_type = pointer_ast_type.GetPointerType(); | |||
767 | ||||
768 | if (pointer_type->isConstType()) | |||
769 | pointer_ast_type = pointer_ast_type.AddConstModifier(); | |||
770 | ||||
771 | if (pointer_type->isVolatileType()) | |||
772 | pointer_ast_type = pointer_ast_type.AddVolatileModifier(); | |||
773 | ||||
774 | if (pointer_type->isRestrictedType()) | |||
775 | pointer_ast_type = pointer_ast_type.AddRestrictModifier(); | |||
776 | ||||
777 | return std::make_shared<lldb_private::Type>( | |||
778 | pointer_type->getSymIndexId(), m_ast.GetSymbolFile(), ConstString(), | |||
779 | pointer_type->getLength(), nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, | |||
780 | lldb_private::Type::eEncodingIsUID, decl, pointer_ast_type, | |||
781 | lldb_private::Type::ResolveState::Full); | |||
782 | } break; | |||
783 | default: | |||
784 | break; | |||
785 | } | |||
786 | return nullptr; | |||
787 | } | |||
788 | ||||
789 | bool PDBASTParser::CompleteTypeFromPDB( | |||
790 | lldb_private::CompilerType &compiler_type) { | |||
791 | if (GetClangASTImporter().CanImport(compiler_type)) | |||
792 | return GetClangASTImporter().CompleteType(compiler_type); | |||
793 | ||||
794 | // Remove the type from the forward declarations to avoid | |||
795 | // an endless recursion for types like a linked list. | |||
796 | clang::CXXRecordDecl *record_decl = | |||
797 | m_ast.GetAsCXXRecordDecl(compiler_type.GetOpaqueQualType()); | |||
798 | auto uid_it = m_forward_decl_to_uid.find(record_decl); | |||
799 | if (uid_it == m_forward_decl_to_uid.end()) | |||
800 | return true; | |||
801 | ||||
802 | auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile()); | |||
803 | if (!symbol_file) | |||
804 | return false; | |||
805 | ||||
806 | std::unique_ptr<PDBSymbol> symbol = | |||
807 | symbol_file->GetPDBSession().getSymbolById(uid_it->getSecond()); | |||
808 | if (!symbol) | |||
809 | return false; | |||
810 | ||||
811 | m_forward_decl_to_uid.erase(uid_it); | |||
812 | ||||
813 | TypeSystemClang::SetHasExternalStorage(compiler_type.GetOpaqueQualType(), | |||
814 | false); | |||
815 | ||||
816 | switch (symbol->getSymTag()) { | |||
817 | case PDB_SymType::UDT: { | |||
818 | auto udt = llvm::dyn_cast<PDBSymbolTypeUDT>(symbol.get()); | |||
819 | if (!udt) | |||
820 | return false; | |||
821 | ||||
822 | return CompleteTypeFromUDT(*symbol_file, compiler_type, *udt); | |||
823 | } | |||
824 | default: | |||
825 | llvm_unreachable("not a forward clang type decl!")__builtin_unreachable(); | |||
826 | } | |||
827 | } | |||
828 | ||||
829 | clang::Decl * | |||
830 | PDBASTParser::GetDeclForSymbol(const llvm::pdb::PDBSymbol &symbol) { | |||
831 | uint32_t sym_id = symbol.getSymIndexId(); | |||
832 | auto it = m_uid_to_decl.find(sym_id); | |||
833 | if (it != m_uid_to_decl.end()) | |||
834 | return it->second; | |||
835 | ||||
836 | auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile()); | |||
837 | if (!symbol_file) | |||
838 | return nullptr; | |||
839 | ||||
840 | // First of all, check if the symbol is a member of a class. Resolve the full | |||
841 | // class type and return the declaration from the cache if so. | |||
842 | auto tag = symbol.getSymTag(); | |||
843 | if (tag == PDB_SymType::Data || tag == PDB_SymType::Function) { | |||
844 | const IPDBSession &session = symbol.getSession(); | |||
845 | const IPDBRawSymbol &raw = symbol.getRawSymbol(); | |||
846 | ||||
847 | auto class_parent_id = raw.getClassParentId(); | |||
848 | if (std::unique_ptr<PDBSymbol> class_parent = | |||
849 | session.getSymbolById(class_parent_id)) { | |||
850 | auto class_parent_type = symbol_file->ResolveTypeUID(class_parent_id); | |||
851 | if (!class_parent_type) | |||
852 | return nullptr; | |||
853 | ||||
854 | CompilerType class_parent_ct = class_parent_type->GetFullCompilerType(); | |||
855 | ||||
856 | // Look a declaration up in the cache after completing the class | |||
857 | clang::Decl *decl = m_uid_to_decl.lookup(sym_id); | |||
858 | if (decl) | |||
859 | return decl; | |||
860 | ||||
861 | // A declaration was not found in the cache. It means that the symbol | |||
862 | // has the class parent, but the class doesn't have the symbol in its | |||
863 | // children list. | |||
864 | if (auto func = llvm::dyn_cast_or_null<PDBSymbolFunc>(&symbol)) { | |||
865 | // Try to find a class child method with the same RVA and use its | |||
866 | // declaration if found. | |||
867 | if (uint32_t rva = func->getRelativeVirtualAddress()) { | |||
868 | if (std::unique_ptr<ConcreteSymbolEnumerator<PDBSymbolFunc>> | |||
869 | methods_enum = | |||
870 | class_parent->findAllChildren<PDBSymbolFunc>()) { | |||
871 | while (std::unique_ptr<PDBSymbolFunc> method = | |||
872 | methods_enum->getNext()) { | |||
873 | if (method->getRelativeVirtualAddress() == rva) { | |||
874 | decl = m_uid_to_decl.lookup(method->getSymIndexId()); | |||
875 | if (decl) | |||
876 | break; | |||
877 | } | |||
878 | } | |||
879 | } | |||
880 | } | |||
881 | ||||
882 | // If no class methods with the same RVA were found, then create a new | |||
883 | // method. It is possible for template methods. | |||
884 | if (!decl) | |||
885 | decl = AddRecordMethod(*symbol_file, class_parent_ct, *func); | |||
886 | } | |||
887 | ||||
888 | if (decl) | |||
889 | m_uid_to_decl[sym_id] = decl; | |||
890 | ||||
891 | return decl; | |||
892 | } | |||
893 | } | |||
894 | ||||
895 | // If we are here, then the symbol is not belonging to a class and is not | |||
896 | // contained in the cache. So create a declaration for it. | |||
897 | switch (symbol.getSymTag()) { | |||
898 | case PDB_SymType::Data: { | |||
899 | auto data = llvm::dyn_cast<PDBSymbolData>(&symbol); | |||
900 | assert(data)((void)0); | |||
901 | ||||
902 | auto decl_context = GetDeclContextContainingSymbol(symbol); | |||
903 | assert(decl_context)((void)0); | |||
904 | ||||
905 | // May be the current context is a class really, but we haven't found | |||
906 | // any class parent. This happens e.g. in the case of class static | |||
907 | // variables - they has two symbols, one is a child of the class when | |||
908 | // another is a child of the exe. So always complete the parent and use | |||
909 | // an existing declaration if possible. | |||
910 | if (auto parent_decl = llvm::dyn_cast_or_null<clang::TagDecl>(decl_context)) | |||
911 | m_ast.GetCompleteDecl(parent_decl); | |||
912 | ||||
913 | std::string name = | |||
914 | std::string(MSVCUndecoratedNameParser::DropScope(data->getName())); | |||
915 | ||||
916 | // Check if the current context already contains the symbol with the name. | |||
917 | clang::Decl *decl = | |||
918 | GetDeclFromContextByName(m_ast.getASTContext(), *decl_context, name); | |||
919 | if (!decl) { | |||
920 | auto type = symbol_file->ResolveTypeUID(data->getTypeId()); | |||
921 | if (!type) | |||
922 | return nullptr; | |||
923 | ||||
924 | decl = m_ast.CreateVariableDeclaration( | |||
925 | decl_context, OptionalClangModuleID(), name.c_str(), | |||
926 | ClangUtil::GetQualType(type->GetLayoutCompilerType())); | |||
927 | } | |||
928 | ||||
929 | m_uid_to_decl[sym_id] = decl; | |||
930 | ||||
931 | return decl; | |||
932 | } | |||
933 | case PDB_SymType::Function: { | |||
934 | auto func = llvm::dyn_cast<PDBSymbolFunc>(&symbol); | |||
935 | assert(func)((void)0); | |||
936 | ||||
937 | auto decl_context = GetDeclContextContainingSymbol(symbol); | |||
938 | assert(decl_context)((void)0); | |||
939 | ||||
940 | std::string name = | |||
941 | std::string(MSVCUndecoratedNameParser::DropScope(func->getName())); | |||
| ||||
942 | ||||
943 | Type *type = symbol_file->ResolveTypeUID(sym_id); | |||
944 | if (!type) | |||
945 | return nullptr; | |||
946 | ||||
947 | auto storage = func->isStatic() ? clang::StorageClass::SC_Static | |||
948 | : clang::StorageClass::SC_None; | |||
949 | ||||
950 | auto decl = m_ast.CreateFunctionDeclaration( | |||
951 | decl_context, OptionalClangModuleID(), name, | |||
952 | type->GetForwardCompilerType(), storage, func->hasInlineAttribute()); | |||
953 | ||||
954 | std::vector<clang::ParmVarDecl *> params; | |||
955 | if (std::unique_ptr<PDBSymbolTypeFunctionSig> sig = func->getSignature()) { | |||
956 | if (std::unique_ptr<ConcreteSymbolEnumerator<PDBSymbolTypeFunctionArg>> | |||
957 | arg_enum = sig->findAllChildren<PDBSymbolTypeFunctionArg>()) { | |||
958 | while (std::unique_ptr<PDBSymbolTypeFunctionArg> arg = | |||
959 | arg_enum->getNext()) { | |||
960 | Type *arg_type = symbol_file->ResolveTypeUID(arg->getTypeId()); | |||
961 | if (!arg_type) | |||
962 | continue; | |||
963 | ||||
964 | clang::ParmVarDecl *param = m_ast.CreateParameterDeclaration( | |||
965 | decl, OptionalClangModuleID(), nullptr, | |||
966 | arg_type->GetForwardCompilerType(), clang::SC_None, true); | |||
967 | if (param) | |||
968 | params.push_back(param); | |||
969 | } | |||
970 | } | |||
971 | } | |||
972 | if (params.size()) | |||
973 | m_ast.SetFunctionParameters(decl, params); | |||
974 | ||||
975 | m_uid_to_decl[sym_id] = decl; | |||
976 | ||||
977 | return decl; | |||
978 | } | |||
979 | default: { | |||
980 | // It's not a variable and not a function, check if it's a type | |||
981 | Type *type = symbol_file->ResolveTypeUID(sym_id); | |||
982 | if (!type) | |||
983 | return nullptr; | |||
984 | ||||
985 | return m_uid_to_decl.lookup(sym_id); | |||
986 | } | |||
987 | } | |||
988 | } | |||
989 | ||||
990 | clang::DeclContext * | |||
991 | PDBASTParser::GetDeclContextForSymbol(const llvm::pdb::PDBSymbol &symbol) { | |||
992 | if (symbol.getSymTag() == PDB_SymType::Function) { | |||
993 | clang::DeclContext *result = | |||
994 | llvm::dyn_cast_or_null<clang::FunctionDecl>(GetDeclForSymbol(symbol)); | |||
995 | ||||
996 | if (result) | |||
997 | m_decl_context_to_uid[result] = symbol.getSymIndexId(); | |||
998 | ||||
999 | return result; | |||
1000 | } | |||
1001 | ||||
1002 | auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile()); | |||
1003 | if (!symbol_file) | |||
1004 | return nullptr; | |||
1005 | ||||
1006 | auto type = symbol_file->ResolveTypeUID(symbol.getSymIndexId()); | |||
1007 | if (!type) | |||
1008 | return nullptr; | |||
1009 | ||||
1010 | clang::DeclContext *result = | |||
1011 | m_ast.GetDeclContextForType(type->GetForwardCompilerType()); | |||
1012 | ||||
1013 | if (result) | |||
1014 | m_decl_context_to_uid[result] = symbol.getSymIndexId(); | |||
1015 | ||||
1016 | return result; | |||
1017 | } | |||
1018 | ||||
1019 | clang::DeclContext *PDBASTParser::GetDeclContextContainingSymbol( | |||
1020 | const llvm::pdb::PDBSymbol &symbol) { | |||
1021 | auto parent = GetClassOrFunctionParent(symbol); | |||
1022 | while (parent) { | |||
1023 | if (auto parent_context = GetDeclContextForSymbol(*parent)) | |||
1024 | return parent_context; | |||
1025 | ||||
1026 | parent = GetClassOrFunctionParent(*parent); | |||
1027 | } | |||
1028 | ||||
1029 | // We can't find any class or function parent of the symbol. So analyze | |||
1030 | // the full symbol name. The symbol may be belonging to a namespace | |||
1031 | // or function (or even to a class if it's e.g. a static variable symbol). | |||
1032 | ||||
1033 | // TODO: Make clang to emit full names for variables in namespaces | |||
1034 | // (as MSVC does) | |||
1035 | ||||
1036 | std::string name(symbol.getRawSymbol().getName()); | |||
1037 | MSVCUndecoratedNameParser parser(name); | |||
1038 | llvm::ArrayRef<MSVCUndecoratedNameSpecifier> specs = parser.GetSpecifiers(); | |||
1039 | if (specs.empty()) | |||
1040 | return m_ast.GetTranslationUnitDecl(); | |||
1041 | ||||
1042 | auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile()); | |||
1043 | if (!symbol_file) | |||
1044 | return m_ast.GetTranslationUnitDecl(); | |||
1045 | ||||
1046 | auto global = symbol_file->GetPDBSession().getGlobalScope(); | |||
1047 | if (!global) | |||
1048 | return m_ast.GetTranslationUnitDecl(); | |||
1049 | ||||
1050 | bool has_type_or_function_parent = false; | |||
1051 | clang::DeclContext *curr_context = m_ast.GetTranslationUnitDecl(); | |||
1052 | for (std::size_t i = 0; i < specs.size() - 1; i++) { | |||
1053 | // Check if there is a function or a type with the current context's name. | |||
1054 | if (std::unique_ptr<IPDBEnumSymbols> children_enum = global->findChildren( | |||
1055 | PDB_SymType::None, specs[i].GetFullName(), NS_CaseSensitive)) { | |||
1056 | while (IPDBEnumChildren<PDBSymbol>::ChildTypePtr child = | |||
1057 | children_enum->getNext()) { | |||
1058 | if (clang::DeclContext *child_context = | |||
1059 | GetDeclContextForSymbol(*child)) { | |||
1060 | // Note that `GetDeclContextForSymbol' retrieves | |||
1061 | // a declaration context for functions and types only, | |||
1062 | // so if we are here then `child_context' is guaranteed | |||
1063 | // a function or a type declaration context. | |||
1064 | has_type_or_function_parent = true; | |||
1065 | curr_context = child_context; | |||
1066 | } | |||
1067 | } | |||
1068 | } | |||
1069 | ||||
1070 | // If there were no functions or types above then retrieve a namespace with | |||
1071 | // the current context's name. There can be no namespaces inside a function | |||
1072 | // or a type. We check it to avoid fake namespaces such as `__l2': | |||
1073 | // `N0::N1::CClass::PrivateFunc::__l2::InnerFuncStruct' | |||
1074 | if (!has_type_or_function_parent) { | |||
1075 | std::string namespace_name = std::string(specs[i].GetBaseName()); | |||
1076 | const char *namespace_name_c_str = | |||
1077 | IsAnonymousNamespaceName(namespace_name) ? nullptr | |||
1078 | : namespace_name.data(); | |||
1079 | clang::NamespaceDecl *namespace_decl = | |||
1080 | m_ast.GetUniqueNamespaceDeclaration( | |||
1081 | namespace_name_c_str, curr_context, OptionalClangModuleID()); | |||
1082 | ||||
1083 | m_parent_to_namespaces[curr_context].insert(namespace_decl); | |||
1084 | m_namespaces.insert(namespace_decl); | |||
1085 | ||||
1086 | curr_context = namespace_decl; | |||
1087 | } | |||
1088 | } | |||
1089 | ||||
1090 | return curr_context; | |||
1091 | } | |||
1092 | ||||
1093 | void PDBASTParser::ParseDeclsForDeclContext( | |||
1094 | const clang::DeclContext *decl_context) { | |||
1095 | auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile()); | |||
1096 | if (!symbol_file) | |||
| ||||
1097 | return; | |||
1098 | ||||
1099 | IPDBSession &session = symbol_file->GetPDBSession(); | |||
1100 | auto symbol_up = | |||
1101 | session.getSymbolById(m_decl_context_to_uid.lookup(decl_context)); | |||
1102 | auto global_up = session.getGlobalScope(); | |||
1103 | ||||
1104 | PDBSymbol *symbol; | |||
1105 | if (symbol_up) | |||
1106 | symbol = symbol_up.get(); | |||
1107 | else if (global_up) | |||
1108 | symbol = global_up.get(); | |||
1109 | else | |||
1110 | return; | |||
1111 | ||||
1112 | if (auto children = symbol->findAllChildren()) | |||
1113 | while (auto child = children->getNext()) | |||
1114 | GetDeclForSymbol(*child); | |||
1115 | } | |||
1116 | ||||
1117 | clang::NamespaceDecl * | |||
1118 | PDBASTParser::FindNamespaceDecl(const clang::DeclContext *parent, | |||
1119 | llvm::StringRef name) { | |||
1120 | NamespacesSet *set; | |||
1121 | if (parent) { | |||
1122 | auto pit = m_parent_to_namespaces.find(parent); | |||
1123 | if (pit == m_parent_to_namespaces.end()) | |||
1124 | return nullptr; | |||
1125 | ||||
1126 | set = &pit->second; | |||
1127 | } else { | |||
1128 | set = &m_namespaces; | |||
1129 | } | |||
1130 | assert(set)((void)0); | |||
1131 | ||||
1132 | for (clang::NamespaceDecl *namespace_decl : *set) | |||
1133 | if (namespace_decl->getName().equals(name)) | |||
1134 | return namespace_decl; | |||
1135 | ||||
1136 | for (clang::NamespaceDecl *namespace_decl : *set) | |||
1137 | if (namespace_decl->isAnonymousNamespace()) | |||
1138 | return FindNamespaceDecl(namespace_decl, name); | |||
1139 | ||||
1140 | return nullptr; | |||
1141 | } | |||
1142 | ||||
1143 | bool PDBASTParser::AddEnumValue(CompilerType enum_type, | |||
1144 | const PDBSymbolData &enum_value) { | |||
1145 | Declaration decl; | |||
1146 | Variant v = enum_value.getValue(); | |||
1147 | std::string name = | |||
1148 | std::string(MSVCUndecoratedNameParser::DropScope(enum_value.getName())); | |||
1149 | int64_t raw_value; | |||
1150 | switch (v.Type) { | |||
1151 | case PDB_VariantType::Int8: | |||
1152 | raw_value = v.Value.Int8; | |||
1153 | break; | |||
1154 | case PDB_VariantType::Int16: | |||
1155 | raw_value = v.Value.Int16; | |||
1156 | break; | |||
1157 | case PDB_VariantType::Int32: | |||
1158 | raw_value = v.Value.Int32; | |||
1159 | break; | |||
1160 | case PDB_VariantType::Int64: | |||
1161 | raw_value = v.Value.Int64; | |||
1162 | break; | |||
1163 | case PDB_VariantType::UInt8: | |||
1164 | raw_value = v.Value.UInt8; | |||
1165 | break; | |||
1166 | case PDB_VariantType::UInt16: | |||
1167 | raw_value = v.Value.UInt16; | |||
1168 | break; | |||
1169 | case PDB_VariantType::UInt32: | |||
1170 | raw_value = v.Value.UInt32; | |||
1171 | break; | |||
1172 | case PDB_VariantType::UInt64: | |||
1173 | raw_value = v.Value.UInt64; | |||
1174 | break; | |||
1175 | default: | |||
1176 | return false; | |||
1177 | } | |||
1178 | CompilerType underlying_type = m_ast.GetEnumerationIntegerType(enum_type); | |||
1179 | uint32_t byte_size = m_ast.getASTContext().getTypeSize( | |||
1180 | ClangUtil::GetQualType(underlying_type)); | |||
1181 | auto enum_constant_decl = m_ast.AddEnumerationValueToEnumerationType( | |||
1182 | enum_type, decl, name.c_str(), raw_value, byte_size * 8); | |||
1183 | if (!enum_constant_decl) | |||
1184 | return false; | |||
1185 | ||||
1186 | m_uid_to_decl[enum_value.getSymIndexId()] = enum_constant_decl; | |||
1187 | ||||
1188 | return true; | |||
1189 | } | |||
1190 | ||||
1191 | bool PDBASTParser::CompleteTypeFromUDT( | |||
1192 | lldb_private::SymbolFile &symbol_file, | |||
1193 | lldb_private::CompilerType &compiler_type, | |||
1194 | llvm::pdb::PDBSymbolTypeUDT &udt) { | |||
1195 | ClangASTImporter::LayoutInfo layout_info; | |||
1196 | layout_info.bit_size = udt.getLength() * 8; | |||
1197 | ||||
1198 | auto nested_enums = udt.findAllChildren<PDBSymbolTypeUDT>(); | |||
1199 | if (nested_enums) | |||
1200 | while (auto nested = nested_enums->getNext()) | |||
1201 | symbol_file.ResolveTypeUID(nested->getSymIndexId()); | |||
1202 | ||||
1203 | auto bases_enum = udt.findAllChildren<PDBSymbolTypeBaseClass>(); | |||
1204 | if (bases_enum) | |||
1205 | AddRecordBases(symbol_file, compiler_type, | |||
1206 | TranslateUdtKind(udt.getUdtKind()), *bases_enum, | |||
1207 | layout_info); | |||
1208 | ||||
1209 | auto members_enum = udt.findAllChildren<PDBSymbolData>(); | |||
1210 | if (members_enum) | |||
1211 | AddRecordMembers(symbol_file, compiler_type, *members_enum, layout_info); | |||
1212 | ||||
1213 | auto methods_enum = udt.findAllChildren<PDBSymbolFunc>(); | |||
1214 | if (methods_enum) | |||
1215 | AddRecordMethods(symbol_file, compiler_type, *methods_enum); | |||
1216 | ||||
1217 | m_ast.AddMethodOverridesForCXXRecordType(compiler_type.GetOpaqueQualType()); | |||
1218 | TypeSystemClang::BuildIndirectFields(compiler_type); | |||
1219 | TypeSystemClang::CompleteTagDeclarationDefinition(compiler_type); | |||
1220 | ||||
1221 | clang::CXXRecordDecl *record_decl = | |||
1222 | m_ast.GetAsCXXRecordDecl(compiler_type.GetOpaqueQualType()); | |||
1223 | if (!record_decl) | |||
1224 | return static_cast<bool>(compiler_type); | |||
1225 | ||||
1226 | GetClangASTImporter().SetRecordLayout(record_decl, layout_info); | |||
1227 | ||||
1228 | return static_cast<bool>(compiler_type); | |||
1229 | } | |||
1230 | ||||
1231 | void PDBASTParser::AddRecordMembers( | |||
1232 | lldb_private::SymbolFile &symbol_file, | |||
1233 | lldb_private::CompilerType &record_type, | |||
1234 | PDBDataSymbolEnumerator &members_enum, | |||
1235 | lldb_private::ClangASTImporter::LayoutInfo &layout_info) { | |||
1236 | while (auto member = members_enum.getNext()) { | |||
1237 | if (member->isCompilerGenerated()) | |||
1238 | continue; | |||
1239 | ||||
1240 | auto member_name = member->getName(); | |||
1241 | ||||
1242 | auto member_type = symbol_file.ResolveTypeUID(member->getTypeId()); | |||
1243 | if (!member_type) | |||
1244 | continue; | |||
1245 | ||||
1246 | auto member_comp_type = member_type->GetLayoutCompilerType(); | |||
1247 | if (!member_comp_type.GetCompleteType()) { | |||
1248 | symbol_file.GetObjectFile()->GetModule()->ReportError( | |||
1249 | ":: Class '%s' has a member '%s' of type '%s' " | |||
1250 | "which does not have a complete definition.", | |||
1251 | record_type.GetTypeName().GetCString(), member_name.c_str(), | |||
1252 | member_comp_type.GetTypeName().GetCString()); | |||
1253 | if (TypeSystemClang::StartTagDeclarationDefinition(member_comp_type)) | |||
1254 | TypeSystemClang::CompleteTagDeclarationDefinition(member_comp_type); | |||
1255 | } | |||
1256 | ||||
1257 | auto access = TranslateMemberAccess(member->getAccess()); | |||
1258 | ||||
1259 | switch (member->getDataKind()) { | |||
1260 | case PDB_DataKind::Member: { | |||
1261 | auto location_type = member->getLocationType(); | |||
1262 | ||||
1263 | auto bit_size = member->getLength(); | |||
1264 | if (location_type == PDB_LocType::ThisRel) | |||
1265 | bit_size *= 8; | |||
1266 | ||||
1267 | auto decl = TypeSystemClang::AddFieldToRecordType( | |||
1268 | record_type, member_name.c_str(), member_comp_type, access, bit_size); | |||
1269 | if (!decl) | |||
1270 | continue; | |||
1271 | ||||
1272 | m_uid_to_decl[member->getSymIndexId()] = decl; | |||
1273 | ||||
1274 | auto offset = member->getOffset() * 8; | |||
1275 | if (location_type == PDB_LocType::BitField) | |||
1276 | offset += member->getBitPosition(); | |||
1277 | ||||
1278 | layout_info.field_offsets.insert(std::make_pair(decl, offset)); | |||
1279 | ||||
1280 | break; | |||
1281 | } | |||
1282 | case PDB_DataKind::StaticMember: { | |||
1283 | auto decl = TypeSystemClang::AddVariableToRecordType( | |||
1284 | record_type, member_name.c_str(), member_comp_type, access); | |||
1285 | if (!decl) | |||
1286 | continue; | |||
1287 | ||||
1288 | // Static constant members may be a const[expr] declaration. | |||
1289 | // Query the symbol's value as the variable initializer if valid. | |||
1290 | if (member_comp_type.IsConst()) { | |||
1291 | auto value = member->getValue(); | |||
1292 | clang::QualType qual_type = decl->getType(); | |||
1293 | unsigned type_width = m_ast.getASTContext().getIntWidth(qual_type); | |||
1294 | unsigned constant_width = value.getBitWidth(); | |||
1295 | ||||
1296 | if (qual_type->isIntegralOrEnumerationType()) { | |||
1297 | if (type_width >= constant_width) { | |||
1298 | TypeSystemClang::SetIntegerInitializerForVariable( | |||
1299 | decl, value.toAPSInt().extOrTrunc(type_width)); | |||
1300 | } else { | |||
1301 | LLDB_LOG(GetLogIfAllCategoriesSet(LIBLLDB_LOG_AST),do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} bits) " "which resolves to a wider constant value ({4} bits). " "Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1302 | "Class '{0}' has a member '{1}' of type '{2}' ({3} bits) "do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} bits) " "which resolves to a wider constant value ({4} bits). " "Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1303 | "which resolves to a wider constant value ({4} bits). "do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} bits) " "which resolves to a wider constant value ({4} bits). " "Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1304 | "Ignoring constant.",do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} bits) " "which resolves to a wider constant value ({4} bits). " "Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1305 | record_type.GetTypeName(), member_name,do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} bits) " "which resolves to a wider constant value ({4} bits). " "Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1306 | member_comp_type.GetTypeName(), type_width,do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} bits) " "which resolves to a wider constant value ({4} bits). " "Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1307 | constant_width)do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} bits) " "which resolves to a wider constant value ({4} bits). " "Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0); | |||
1308 | } | |||
1309 | } else { | |||
1310 | switch (member_comp_type.GetBasicTypeEnumeration()) { | |||
1311 | case lldb::eBasicTypeFloat: | |||
1312 | case lldb::eBasicTypeDouble: | |||
1313 | case lldb::eBasicTypeLongDouble: | |||
1314 | if (type_width == constant_width) { | |||
1315 | TypeSystemClang::SetFloatingInitializerForVariable( | |||
1316 | decl, value.toAPFloat()); | |||
1317 | decl->setConstexpr(true); | |||
1318 | } else { | |||
1319 | LLDB_LOG(GetLogIfAllCategoriesSet(LIBLLDB_LOG_AST),do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} " "bits) which resolves to a constant value of mismatched " "width ({4} bits). Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1320 | "Class '{0}' has a member '{1}' of type '{2}' ({3} "do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} " "bits) which resolves to a constant value of mismatched " "width ({4} bits). Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1321 | "bits) which resolves to a constant value of mismatched "do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} " "bits) which resolves to a constant value of mismatched " "width ({4} bits). Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1322 | "width ({4} bits). Ignoring constant.",do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} " "bits) which resolves to a constant value of mismatched " "width ({4} bits). Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1323 | record_type.GetTypeName(), member_name,do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} " "bits) which resolves to a constant value of mismatched " "width ({4} bits). Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1324 | member_comp_type.GetTypeName(), type_width,do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} " "bits) which resolves to a constant value of mismatched " "width ({4} bits). Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0) | |||
1325 | constant_width)do { ::lldb_private::Log *log_private = (GetLogIfAllCategoriesSet ((1u << 31))); if (log_private) log_private->Format( "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , __func__, "Class '{0}' has a member '{1}' of type '{2}' ({3} " "bits) which resolves to a constant value of mismatched " "width ({4} bits). Ignoring constant." , record_type.GetTypeName(), member_name, member_comp_type.GetTypeName (), type_width, constant_width); } while (0); | |||
1326 | } | |||
1327 | break; | |||
1328 | default: | |||
1329 | break; | |||
1330 | } | |||
1331 | } | |||
1332 | } | |||
1333 | ||||
1334 | m_uid_to_decl[member->getSymIndexId()] = decl; | |||
1335 | ||||
1336 | break; | |||
1337 | } | |||
1338 | default: | |||
1339 | llvm_unreachable("unsupported PDB data kind")__builtin_unreachable(); | |||
1340 | } | |||
1341 | } | |||
1342 | } | |||
1343 | ||||
1344 | void PDBASTParser::AddRecordBases( | |||
1345 | lldb_private::SymbolFile &symbol_file, | |||
1346 | lldb_private::CompilerType &record_type, int record_kind, | |||
1347 | PDBBaseClassSymbolEnumerator &bases_enum, | |||
1348 | lldb_private::ClangASTImporter::LayoutInfo &layout_info) const { | |||
1349 | std::vector<std::unique_ptr<clang::CXXBaseSpecifier>> base_classes; | |||
1350 | ||||
1351 | while (auto base = bases_enum.getNext()) { | |||
1352 | auto base_type = symbol_file.ResolveTypeUID(base->getTypeId()); | |||
1353 | if (!base_type) | |||
1354 | continue; | |||
1355 | ||||
1356 | auto base_comp_type = base_type->GetFullCompilerType(); | |||
1357 | if (!base_comp_type.GetCompleteType()) { | |||
1358 | symbol_file.GetObjectFile()->GetModule()->ReportError( | |||
1359 | ":: Class '%s' has a base class '%s' " | |||
1360 | "which does not have a complete definition.", | |||
1361 | record_type.GetTypeName().GetCString(), | |||
1362 | base_comp_type.GetTypeName().GetCString()); | |||
1363 | if (TypeSystemClang::StartTagDeclarationDefinition(base_comp_type)) | |||
1364 | TypeSystemClang::CompleteTagDeclarationDefinition(base_comp_type); | |||
1365 | } | |||
1366 | ||||
1367 | auto access = TranslateMemberAccess(base->getAccess()); | |||
1368 | ||||
1369 | auto is_virtual = base->isVirtualBaseClass(); | |||
1370 | ||||
1371 | std::unique_ptr<clang::CXXBaseSpecifier> base_spec = | |||
1372 | m_ast.CreateBaseClassSpecifier(base_comp_type.GetOpaqueQualType(), | |||
1373 | access, is_virtual, | |||
1374 | record_kind == clang::TTK_Class); | |||
1375 | lldbassert(base_spec)lldb_private::lldb_assert(static_cast<bool>(base_spec), "base_spec", __FUNCTION__, "/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp" , 1375); | |||
1376 | ||||
1377 | base_classes.push_back(std::move(base_spec)); | |||
1378 | ||||
1379 | if (is_virtual) | |||
1380 | continue; | |||
1381 | ||||
1382 | auto decl = m_ast.GetAsCXXRecordDecl(base_comp_type.GetOpaqueQualType()); | |||
1383 | if (!decl) | |||
1384 | continue; | |||
1385 | ||||
1386 | auto offset = clang::CharUnits::fromQuantity(base->getOffset()); | |||
1387 | layout_info.base_offsets.insert(std::make_pair(decl, offset)); | |||
1388 | } | |||
1389 | ||||
1390 | m_ast.TransferBaseClasses(record_type.GetOpaqueQualType(), | |||
1391 | std::move(base_classes)); | |||
1392 | } | |||
1393 | ||||
1394 | void PDBASTParser::AddRecordMethods(lldb_private::SymbolFile &symbol_file, | |||
1395 | lldb_private::CompilerType &record_type, | |||
1396 | PDBFuncSymbolEnumerator &methods_enum) { | |||
1397 | while (std::unique_ptr<PDBSymbolFunc> method = methods_enum.getNext()) | |||
1398 | if (clang::CXXMethodDecl *decl = | |||
1399 | AddRecordMethod(symbol_file, record_type, *method)) | |||
1400 | m_uid_to_decl[method->getSymIndexId()] = decl; | |||
1401 | } | |||
1402 | ||||
1403 | clang::CXXMethodDecl * | |||
1404 | PDBASTParser::AddRecordMethod(lldb_private::SymbolFile &symbol_file, | |||
1405 | lldb_private::CompilerType &record_type, | |||
1406 | const llvm::pdb::PDBSymbolFunc &method) const { | |||
1407 | std::string name = | |||
1408 | std::string(MSVCUndecoratedNameParser::DropScope(method.getName())); | |||
1409 | ||||
1410 | Type *method_type = symbol_file.ResolveTypeUID(method.getSymIndexId()); | |||
1411 | // MSVC specific __vecDelDtor. | |||
1412 | if (!method_type) | |||
1413 | return nullptr; | |||
1414 | ||||
1415 | CompilerType method_comp_type = method_type->GetFullCompilerType(); | |||
1416 | if (!method_comp_type.GetCompleteType()) { | |||
1417 | symbol_file.GetObjectFile()->GetModule()->ReportError( | |||
1418 | ":: Class '%s' has a method '%s' whose type cannot be completed.", | |||
1419 | record_type.GetTypeName().GetCString(), | |||
1420 | method_comp_type.GetTypeName().GetCString()); | |||
1421 | if (TypeSystemClang::StartTagDeclarationDefinition(method_comp_type)) | |||
1422 | TypeSystemClang::CompleteTagDeclarationDefinition(method_comp_type); | |||
1423 | } | |||
1424 | ||||
1425 | AccessType access = TranslateMemberAccess(method.getAccess()); | |||
1426 | if (access == eAccessNone) | |||
1427 | access = eAccessPublic; | |||
1428 | ||||
1429 | // TODO: get mangled name for the method. | |||
1430 | return m_ast.AddMethodToCXXRecordType( | |||
1431 | record_type.GetOpaqueQualType(), name.c_str(), | |||
1432 | /*mangled_name*/ nullptr, method_comp_type, access, method.isVirtual(), | |||
1433 | method.isStatic(), method.hasInlineAttribute(), | |||
1434 | /*is_explicit*/ false, // FIXME: Need this field in CodeView. | |||
1435 | /*is_attr_used*/ false, | |||
1436 | /*is_artificial*/ method.isCompilerGenerated()); | |||
1437 | } |
1 | //===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- 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 defines the DenseMap class. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_ADT_DENSEMAP_H |
14 | #define LLVM_ADT_DENSEMAP_H |
15 | |
16 | #include "llvm/ADT/DenseMapInfo.h" |
17 | #include "llvm/ADT/EpochTracker.h" |
18 | #include "llvm/Support/AlignOf.h" |
19 | #include "llvm/Support/Compiler.h" |
20 | #include "llvm/Support/MathExtras.h" |
21 | #include "llvm/Support/MemAlloc.h" |
22 | #include "llvm/Support/ReverseIteration.h" |
23 | #include "llvm/Support/type_traits.h" |
24 | #include <algorithm> |
25 | #include <cassert> |
26 | #include <cstddef> |
27 | #include <cstring> |
28 | #include <initializer_list> |
29 | #include <iterator> |
30 | #include <new> |
31 | #include <type_traits> |
32 | #include <utility> |
33 | |
34 | namespace llvm { |
35 | |
36 | namespace detail { |
37 | |
38 | // We extend a pair to allow users to override the bucket type with their own |
39 | // implementation without requiring two members. |
40 | template <typename KeyT, typename ValueT> |
41 | struct DenseMapPair : public std::pair<KeyT, ValueT> { |
42 | using std::pair<KeyT, ValueT>::pair; |
43 | |
44 | KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; } |
45 | const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; } |
46 | ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; } |
47 | const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; } |
48 | }; |
49 | |
50 | } // end namespace detail |
51 | |
52 | template <typename KeyT, typename ValueT, |
53 | typename KeyInfoT = DenseMapInfo<KeyT>, |
54 | typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>, |
55 | bool IsConst = false> |
56 | class DenseMapIterator; |
57 | |
58 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
59 | typename BucketT> |
60 | class DenseMapBase : public DebugEpochBase { |
61 | template <typename T> |
62 | using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; |
63 | |
64 | public: |
65 | using size_type = unsigned; |
66 | using key_type = KeyT; |
67 | using mapped_type = ValueT; |
68 | using value_type = BucketT; |
69 | |
70 | using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>; |
71 | using const_iterator = |
72 | DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>; |
73 | |
74 | inline iterator begin() { |
75 | // When the map is empty, avoid the overhead of advancing/retreating past |
76 | // empty buckets. |
77 | if (empty()) |
78 | return end(); |
79 | if (shouldReverseIterate<KeyT>()) |
80 | return makeIterator(getBucketsEnd() - 1, getBuckets(), *this); |
81 | return makeIterator(getBuckets(), getBucketsEnd(), *this); |
82 | } |
83 | inline iterator end() { |
84 | return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true); |
85 | } |
86 | inline const_iterator begin() const { |
87 | if (empty()) |
88 | return end(); |
89 | if (shouldReverseIterate<KeyT>()) |
90 | return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this); |
91 | return makeConstIterator(getBuckets(), getBucketsEnd(), *this); |
92 | } |
93 | inline const_iterator end() const { |
94 | return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true); |
95 | } |
96 | |
97 | LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { |
98 | return getNumEntries() == 0; |
99 | } |
100 | unsigned size() const { return getNumEntries(); } |
101 | |
102 | /// Grow the densemap so that it can contain at least \p NumEntries items |
103 | /// before resizing again. |
104 | void reserve(size_type NumEntries) { |
105 | auto NumBuckets = getMinBucketToReserveForEntries(NumEntries); |
106 | incrementEpoch(); |
107 | if (NumBuckets > getNumBuckets()) |
108 | grow(NumBuckets); |
109 | } |
110 | |
111 | void clear() { |
112 | incrementEpoch(); |
113 | if (getNumEntries() == 0 && getNumTombstones() == 0) return; |
114 | |
115 | // If the capacity of the array is huge, and the # elements used is small, |
116 | // shrink the array. |
117 | if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { |
118 | shrink_and_clear(); |
119 | return; |
120 | } |
121 | |
122 | const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); |
123 | if (std::is_trivially_destructible<ValueT>::value) { |
124 | // Use a simpler loop when values don't need destruction. |
125 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) |
126 | P->getFirst() = EmptyKey; |
127 | } else { |
128 | unsigned NumEntries = getNumEntries(); |
129 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { |
130 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) { |
131 | if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { |
132 | P->getSecond().~ValueT(); |
133 | --NumEntries; |
134 | } |
135 | P->getFirst() = EmptyKey; |
136 | } |
137 | } |
138 | assert(NumEntries == 0 && "Node count imbalance!")((void)0); |
139 | } |
140 | setNumEntries(0); |
141 | setNumTombstones(0); |
142 | } |
143 | |
144 | /// Return 1 if the specified key is in the map, 0 otherwise. |
145 | size_type count(const_arg_type_t<KeyT> Val) const { |
146 | const BucketT *TheBucket; |
147 | return LookupBucketFor(Val, TheBucket) ? 1 : 0; |
148 | } |
149 | |
150 | iterator find(const_arg_type_t<KeyT> Val) { |
151 | BucketT *TheBucket; |
152 | if (LookupBucketFor(Val, TheBucket)) |
153 | return makeIterator(TheBucket, |
154 | shouldReverseIterate<KeyT>() ? getBuckets() |
155 | : getBucketsEnd(), |
156 | *this, true); |
157 | return end(); |
158 | } |
159 | const_iterator find(const_arg_type_t<KeyT> Val) const { |
160 | const BucketT *TheBucket; |
161 | if (LookupBucketFor(Val, TheBucket)) |
162 | return makeConstIterator(TheBucket, |
163 | shouldReverseIterate<KeyT>() ? getBuckets() |
164 | : getBucketsEnd(), |
165 | *this, true); |
166 | return end(); |
167 | } |
168 | |
169 | /// Alternate version of find() which allows a different, and possibly |
170 | /// less expensive, key type. |
171 | /// The DenseMapInfo is responsible for supplying methods |
172 | /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key |
173 | /// type used. |
174 | template<class LookupKeyT> |
175 | iterator find_as(const LookupKeyT &Val) { |
176 | BucketT *TheBucket; |
177 | if (LookupBucketFor(Val, TheBucket)) |
178 | return makeIterator(TheBucket, |
179 | shouldReverseIterate<KeyT>() ? getBuckets() |
180 | : getBucketsEnd(), |
181 | *this, true); |
182 | return end(); |
183 | } |
184 | template<class LookupKeyT> |
185 | const_iterator find_as(const LookupKeyT &Val) const { |
186 | const BucketT *TheBucket; |
187 | if (LookupBucketFor(Val, TheBucket)) |
188 | return makeConstIterator(TheBucket, |
189 | shouldReverseIterate<KeyT>() ? getBuckets() |
190 | : getBucketsEnd(), |
191 | *this, true); |
192 | return end(); |
193 | } |
194 | |
195 | /// lookup - Return the entry for the specified key, or a default |
196 | /// constructed value if no such entry exists. |
197 | ValueT lookup(const_arg_type_t<KeyT> Val) const { |
198 | const BucketT *TheBucket; |
199 | if (LookupBucketFor(Val, TheBucket)) |
200 | return TheBucket->getSecond(); |
201 | return ValueT(); |
202 | } |
203 | |
204 | // Inserts key,value pair into the map if the key isn't already in the map. |
205 | // If the key is already in the map, it returns false and doesn't update the |
206 | // value. |
207 | std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { |
208 | return try_emplace(KV.first, KV.second); |
209 | } |
210 | |
211 | // Inserts key,value pair into the map if the key isn't already in the map. |
212 | // If the key is already in the map, it returns false and doesn't update the |
213 | // value. |
214 | std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { |
215 | return try_emplace(std::move(KV.first), std::move(KV.second)); |
216 | } |
217 | |
218 | // Inserts key,value pair into the map if the key isn't already in the map. |
219 | // The value is constructed in-place if the key is not in the map, otherwise |
220 | // it is not moved. |
221 | template <typename... Ts> |
222 | std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) { |
223 | BucketT *TheBucket; |
224 | if (LookupBucketFor(Key, TheBucket)) |
225 | return std::make_pair(makeIterator(TheBucket, |
226 | shouldReverseIterate<KeyT>() |
227 | ? getBuckets() |
228 | : getBucketsEnd(), |
229 | *this, true), |
230 | false); // Already in map. |
231 | |
232 | // Otherwise, insert the new element. |
233 | TheBucket = |
234 | InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...); |
235 | return std::make_pair(makeIterator(TheBucket, |
236 | shouldReverseIterate<KeyT>() |
237 | ? getBuckets() |
238 | : getBucketsEnd(), |
239 | *this, true), |
240 | true); |
241 | } |
242 | |
243 | // Inserts key,value pair into the map if the key isn't already in the map. |
244 | // The value is constructed in-place if the key is not in the map, otherwise |
245 | // it is not moved. |
246 | template <typename... Ts> |
247 | std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) { |
248 | BucketT *TheBucket; |
249 | if (LookupBucketFor(Key, TheBucket)) |
250 | return std::make_pair(makeIterator(TheBucket, |
251 | shouldReverseIterate<KeyT>() |
252 | ? getBuckets() |
253 | : getBucketsEnd(), |
254 | *this, true), |
255 | false); // Already in map. |
256 | |
257 | // Otherwise, insert the new element. |
258 | TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...); |
259 | return std::make_pair(makeIterator(TheBucket, |
260 | shouldReverseIterate<KeyT>() |
261 | ? getBuckets() |
262 | : getBucketsEnd(), |
263 | *this, true), |
264 | true); |
265 | } |
266 | |
267 | /// Alternate version of insert() which allows a different, and possibly |
268 | /// less expensive, key type. |
269 | /// The DenseMapInfo is responsible for supplying methods |
270 | /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key |
271 | /// type used. |
272 | template <typename LookupKeyT> |
273 | std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV, |
274 | const LookupKeyT &Val) { |
275 | BucketT *TheBucket; |
276 | if (LookupBucketFor(Val, TheBucket)) |
277 | return std::make_pair(makeIterator(TheBucket, |
278 | shouldReverseIterate<KeyT>() |
279 | ? getBuckets() |
280 | : getBucketsEnd(), |
281 | *this, true), |
282 | false); // Already in map. |
283 | |
284 | // Otherwise, insert the new element. |
285 | TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first), |
286 | std::move(KV.second), Val); |
287 | return std::make_pair(makeIterator(TheBucket, |
288 | shouldReverseIterate<KeyT>() |
289 | ? getBuckets() |
290 | : getBucketsEnd(), |
291 | *this, true), |
292 | true); |
293 | } |
294 | |
295 | /// insert - Range insertion of pairs. |
296 | template<typename InputIt> |
297 | void insert(InputIt I, InputIt E) { |
298 | for (; I != E; ++I) |
299 | insert(*I); |
300 | } |
301 | |
302 | bool erase(const KeyT &Val) { |
303 | BucketT *TheBucket; |
304 | if (!LookupBucketFor(Val, TheBucket)) |
305 | return false; // not in map. |
306 | |
307 | TheBucket->getSecond().~ValueT(); |
308 | TheBucket->getFirst() = getTombstoneKey(); |
309 | decrementNumEntries(); |
310 | incrementNumTombstones(); |
311 | return true; |
312 | } |
313 | void erase(iterator I) { |
314 | BucketT *TheBucket = &*I; |
315 | TheBucket->getSecond().~ValueT(); |
316 | TheBucket->getFirst() = getTombstoneKey(); |
317 | decrementNumEntries(); |
318 | incrementNumTombstones(); |
319 | } |
320 | |
321 | value_type& FindAndConstruct(const KeyT &Key) { |
322 | BucketT *TheBucket; |
323 | if (LookupBucketFor(Key, TheBucket)) |
324 | return *TheBucket; |
325 | |
326 | return *InsertIntoBucket(TheBucket, Key); |
327 | } |
328 | |
329 | ValueT &operator[](const KeyT &Key) { |
330 | return FindAndConstruct(Key).second; |
331 | } |
332 | |
333 | value_type& FindAndConstruct(KeyT &&Key) { |
334 | BucketT *TheBucket; |
335 | if (LookupBucketFor(Key, TheBucket)) |
336 | return *TheBucket; |
337 | |
338 | return *InsertIntoBucket(TheBucket, std::move(Key)); |
339 | } |
340 | |
341 | ValueT &operator[](KeyT &&Key) { |
342 | return FindAndConstruct(std::move(Key)).second; |
343 | } |
344 | |
345 | /// isPointerIntoBucketsArray - Return true if the specified pointer points |
346 | /// somewhere into the DenseMap's array of buckets (i.e. either to a key or |
347 | /// value in the DenseMap). |
348 | bool isPointerIntoBucketsArray(const void *Ptr) const { |
349 | return Ptr >= getBuckets() && Ptr < getBucketsEnd(); |
350 | } |
351 | |
352 | /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets |
353 | /// array. In conjunction with the previous method, this can be used to |
354 | /// determine whether an insertion caused the DenseMap to reallocate. |
355 | const void *getPointerIntoBucketsArray() const { return getBuckets(); } |
356 | |
357 | protected: |
358 | DenseMapBase() = default; |
359 | |
360 | void destroyAll() { |
361 | if (getNumBuckets() == 0) // Nothing to do. |
362 | return; |
363 | |
364 | const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); |
365 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { |
366 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && |
367 | !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) |
368 | P->getSecond().~ValueT(); |
369 | P->getFirst().~KeyT(); |
370 | } |
371 | } |
372 | |
373 | void initEmpty() { |
374 | setNumEntries(0); |
375 | setNumTombstones(0); |
376 | |
377 | assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&((void)0) |
378 | "# initial buckets must be a power of two!")((void)0); |
379 | const KeyT EmptyKey = getEmptyKey(); |
380 | for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) |
381 | ::new (&B->getFirst()) KeyT(EmptyKey); |
382 | } |
383 | |
384 | /// Returns the number of buckets to allocate to ensure that the DenseMap can |
385 | /// accommodate \p NumEntries without need to grow(). |
386 | unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { |
387 | // Ensure that "NumEntries * 4 < NumBuckets * 3" |
388 | if (NumEntries == 0) |
389 | return 0; |
390 | // +1 is required because of the strict equality. |
391 | // For example if NumEntries is 48, we need to return 401. |
392 | return NextPowerOf2(NumEntries * 4 / 3 + 1); |
393 | } |
394 | |
395 | void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { |
396 | initEmpty(); |
397 | |
398 | // Insert all the old elements. |
399 | const KeyT EmptyKey = getEmptyKey(); |
400 | const KeyT TombstoneKey = getTombstoneKey(); |
401 | for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { |
402 | if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) && |
403 | !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) { |
404 | // Insert the key/value into the new table. |
405 | BucketT *DestBucket; |
406 | bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket); |
407 | (void)FoundVal; // silence warning. |
408 | assert(!FoundVal && "Key already in new map?")((void)0); |
409 | DestBucket->getFirst() = std::move(B->getFirst()); |
410 | ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond())); |
411 | incrementNumEntries(); |
412 | |
413 | // Free the value. |
414 | B->getSecond().~ValueT(); |
415 | } |
416 | B->getFirst().~KeyT(); |
417 | } |
418 | } |
419 | |
420 | template <typename OtherBaseT> |
421 | void copyFrom( |
422 | const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) { |
423 | assert(&other != this)((void)0); |
424 | assert(getNumBuckets() == other.getNumBuckets())((void)0); |
425 | |
426 | setNumEntries(other.getNumEntries()); |
427 | setNumTombstones(other.getNumTombstones()); |
428 | |
429 | if (std::is_trivially_copyable<KeyT>::value && |
430 | std::is_trivially_copyable<ValueT>::value) |
431 | memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(), |
432 | getNumBuckets() * sizeof(BucketT)); |
433 | else |
434 | for (size_t i = 0; i < getNumBuckets(); ++i) { |
435 | ::new (&getBuckets()[i].getFirst()) |
436 | KeyT(other.getBuckets()[i].getFirst()); |
437 | if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) && |
438 | !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey())) |
439 | ::new (&getBuckets()[i].getSecond()) |
440 | ValueT(other.getBuckets()[i].getSecond()); |
441 | } |
442 | } |
443 | |
444 | static unsigned getHashValue(const KeyT &Val) { |
445 | return KeyInfoT::getHashValue(Val); |
446 | } |
447 | |
448 | template<typename LookupKeyT> |
449 | static unsigned getHashValue(const LookupKeyT &Val) { |
450 | return KeyInfoT::getHashValue(Val); |
451 | } |
452 | |
453 | static const KeyT getEmptyKey() { |
454 | static_assert(std::is_base_of<DenseMapBase, DerivedT>::value, |
455 | "Must pass the derived type to this template!"); |
456 | return KeyInfoT::getEmptyKey(); |
457 | } |
458 | |
459 | static const KeyT getTombstoneKey() { |
460 | return KeyInfoT::getTombstoneKey(); |
461 | } |
462 | |
463 | private: |
464 | iterator makeIterator(BucketT *P, BucketT *E, |
465 | DebugEpochBase &Epoch, |
466 | bool NoAdvance=false) { |
467 | if (shouldReverseIterate<KeyT>()) { |
468 | BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1; |
469 | return iterator(B, E, Epoch, NoAdvance); |
470 | } |
471 | return iterator(P, E, Epoch, NoAdvance); |
472 | } |
473 | |
474 | const_iterator makeConstIterator(const BucketT *P, const BucketT *E, |
475 | const DebugEpochBase &Epoch, |
476 | const bool NoAdvance=false) const { |
477 | if (shouldReverseIterate<KeyT>()) { |
478 | const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1; |
479 | return const_iterator(B, E, Epoch, NoAdvance); |
480 | } |
481 | return const_iterator(P, E, Epoch, NoAdvance); |
482 | } |
483 | |
484 | unsigned getNumEntries() const { |
485 | return static_cast<const DerivedT *>(this)->getNumEntries(); |
486 | } |
487 | |
488 | void setNumEntries(unsigned Num) { |
489 | static_cast<DerivedT *>(this)->setNumEntries(Num); |
490 | } |
491 | |
492 | void incrementNumEntries() { |
493 | setNumEntries(getNumEntries() + 1); |
494 | } |
495 | |
496 | void decrementNumEntries() { |
497 | setNumEntries(getNumEntries() - 1); |
498 | } |
499 | |
500 | unsigned getNumTombstones() const { |
501 | return static_cast<const DerivedT *>(this)->getNumTombstones(); |
502 | } |
503 | |
504 | void setNumTombstones(unsigned Num) { |
505 | static_cast<DerivedT *>(this)->setNumTombstones(Num); |
506 | } |
507 | |
508 | void incrementNumTombstones() { |
509 | setNumTombstones(getNumTombstones() + 1); |
510 | } |
511 | |
512 | void decrementNumTombstones() { |
513 | setNumTombstones(getNumTombstones() - 1); |
514 | } |
515 | |
516 | const BucketT *getBuckets() const { |
517 | return static_cast<const DerivedT *>(this)->getBuckets(); |
518 | } |
519 | |
520 | BucketT *getBuckets() { |
521 | return static_cast<DerivedT *>(this)->getBuckets(); |
522 | } |
523 | |
524 | unsigned getNumBuckets() const { |
525 | return static_cast<const DerivedT *>(this)->getNumBuckets(); |
526 | } |
527 | |
528 | BucketT *getBucketsEnd() { |
529 | return getBuckets() + getNumBuckets(); |
530 | } |
531 | |
532 | const BucketT *getBucketsEnd() const { |
533 | return getBuckets() + getNumBuckets(); |
534 | } |
535 | |
536 | void grow(unsigned AtLeast) { |
537 | static_cast<DerivedT *>(this)->grow(AtLeast); |
538 | } |
539 | |
540 | void shrink_and_clear() { |
541 | static_cast<DerivedT *>(this)->shrink_and_clear(); |
542 | } |
543 | |
544 | template <typename KeyArg, typename... ValueArgs> |
545 | BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key, |
546 | ValueArgs &&... Values) { |
547 | TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket); |
548 | |
549 | TheBucket->getFirst() = std::forward<KeyArg>(Key); |
550 | ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...); |
551 | return TheBucket; |
552 | } |
553 | |
554 | template <typename LookupKeyT> |
555 | BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key, |
556 | ValueT &&Value, LookupKeyT &Lookup) { |
557 | TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket); |
558 | |
559 | TheBucket->getFirst() = std::move(Key); |
560 | ::new (&TheBucket->getSecond()) ValueT(std::move(Value)); |
561 | return TheBucket; |
562 | } |
563 | |
564 | template <typename LookupKeyT> |
565 | BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup, |
566 | BucketT *TheBucket) { |
567 | incrementEpoch(); |
568 | |
569 | // If the load of the hash table is more than 3/4, or if fewer than 1/8 of |
570 | // the buckets are empty (meaning that many are filled with tombstones), |
571 | // grow the table. |
572 | // |
573 | // The later case is tricky. For example, if we had one empty bucket with |
574 | // tons of tombstones, failing lookups (e.g. for insertion) would have to |
575 | // probe almost the entire table until it found the empty bucket. If the |
576 | // table completely filled with tombstones, no lookup would ever succeed, |
577 | // causing infinite loops in lookup. |
578 | unsigned NewNumEntries = getNumEntries() + 1; |
579 | unsigned NumBuckets = getNumBuckets(); |
580 | if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)__builtin_expect((bool)(NewNumEntries * 4 >= NumBuckets * 3 ), false)) { |
581 | this->grow(NumBuckets * 2); |
582 | LookupBucketFor(Lookup, TheBucket); |
583 | NumBuckets = getNumBuckets(); |
584 | } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones ()) <= NumBuckets/8), false) |
585 | NumBuckets/8)__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones ()) <= NumBuckets/8), false)) { |
586 | this->grow(NumBuckets); |
587 | LookupBucketFor(Lookup, TheBucket); |
588 | } |
589 | assert(TheBucket)((void)0); |
590 | |
591 | // Only update the state after we've grown our bucket space appropriately |
592 | // so that when growing buckets we have self-consistent entry count. |
593 | incrementNumEntries(); |
594 | |
595 | // If we are writing over a tombstone, remember this. |
596 | const KeyT EmptyKey = getEmptyKey(); |
597 | if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey)) |
598 | decrementNumTombstones(); |
599 | |
600 | return TheBucket; |
601 | } |
602 | |
603 | /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in |
604 | /// FoundBucket. If the bucket contains the key and a value, this returns |
605 | /// true, otherwise it returns a bucket with an empty marker or tombstone and |
606 | /// returns false. |
607 | template<typename LookupKeyT> |
608 | bool LookupBucketFor(const LookupKeyT &Val, |
609 | const BucketT *&FoundBucket) const { |
610 | const BucketT *BucketsPtr = getBuckets(); |
611 | const unsigned NumBuckets = getNumBuckets(); |
612 | |
613 | if (NumBuckets == 0) { |
614 | FoundBucket = nullptr; |
615 | return false; |
616 | } |
617 | |
618 | // FoundTombstone - Keep track of whether we find a tombstone while probing. |
619 | const BucketT *FoundTombstone = nullptr; |
620 | const KeyT EmptyKey = getEmptyKey(); |
621 | const KeyT TombstoneKey = getTombstoneKey(); |
622 | assert(!KeyInfoT::isEqual(Val, EmptyKey) &&((void)0) |
623 | !KeyInfoT::isEqual(Val, TombstoneKey) &&((void)0) |
624 | "Empty/Tombstone value shouldn't be inserted into map!")((void)0); |
625 | |
626 | unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); |
627 | unsigned ProbeAmt = 1; |
628 | while (true) { |
629 | const BucketT *ThisBucket = BucketsPtr + BucketNo; |
630 | // Found Val's bucket? If so, return it. |
631 | if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))__builtin_expect((bool)(KeyInfoT::isEqual(Val, ThisBucket-> getFirst())), true)) { |
632 | FoundBucket = ThisBucket; |
633 | return true; |
634 | } |
635 | |
636 | // If we found an empty bucket, the key doesn't exist in the set. |
637 | // Insert it and return the default value. |
638 | if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))__builtin_expect((bool)(KeyInfoT::isEqual(ThisBucket->getFirst (), EmptyKey)), true)) { |
639 | // If we've already seen a tombstone while probing, fill it in instead |
640 | // of the empty bucket we eventually probed to. |
641 | FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; |
642 | return false; |
643 | } |
644 | |
645 | // If this is a tombstone, remember it. If Val ends up not in the map, we |
646 | // prefer to return it than something that would require more probing. |
647 | if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) && |
648 | !FoundTombstone) |
649 | FoundTombstone = ThisBucket; // Remember the first tombstone found. |
650 | |
651 | // Otherwise, it's a hash collision or a tombstone, continue quadratic |
652 | // probing. |
653 | BucketNo += ProbeAmt++; |
654 | BucketNo &= (NumBuckets-1); |
655 | } |
656 | } |
657 | |
658 | template <typename LookupKeyT> |
659 | bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { |
660 | const BucketT *ConstFoundBucket; |
661 | bool Result = const_cast<const DenseMapBase *>(this) |
662 | ->LookupBucketFor(Val, ConstFoundBucket); |
663 | FoundBucket = const_cast<BucketT *>(ConstFoundBucket); |
664 | return Result; |
665 | } |
666 | |
667 | public: |
668 | /// Return the approximate size (in bytes) of the actual map. |
669 | /// This is just the raw memory used by DenseMap. |
670 | /// If entries are pointers to objects, the size of the referenced objects |
671 | /// are not included. |
672 | size_t getMemorySize() const { |
673 | return getNumBuckets() * sizeof(BucketT); |
674 | } |
675 | }; |
676 | |
677 | /// Equality comparison for DenseMap. |
678 | /// |
679 | /// Iterates over elements of LHS confirming that each (key, value) pair in LHS |
680 | /// is also in RHS, and that no additional pairs are in RHS. |
681 | /// Equivalent to N calls to RHS.find and N value comparisons. Amortized |
682 | /// complexity is linear, worst case is O(N^2) (if every hash collides). |
683 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
684 | typename BucketT> |
685 | bool operator==( |
686 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS, |
687 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) { |
688 | if (LHS.size() != RHS.size()) |
689 | return false; |
690 | |
691 | for (auto &KV : LHS) { |
692 | auto I = RHS.find(KV.first); |
693 | if (I == RHS.end() || I->second != KV.second) |
694 | return false; |
695 | } |
696 | |
697 | return true; |
698 | } |
699 | |
700 | /// Inequality comparison for DenseMap. |
701 | /// |
702 | /// Equivalent to !(LHS == RHS). See operator== for performance notes. |
703 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
704 | typename BucketT> |
705 | bool operator!=( |
706 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS, |
707 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) { |
708 | return !(LHS == RHS); |
709 | } |
710 | |
711 | template <typename KeyT, typename ValueT, |
712 | typename KeyInfoT = DenseMapInfo<KeyT>, |
713 | typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>> |
714 | class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>, |
715 | KeyT, ValueT, KeyInfoT, BucketT> { |
716 | friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
717 | |
718 | // Lift some types from the dependent base class into this class for |
719 | // simplicity of referring to them. |
720 | using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
721 | |
722 | BucketT *Buckets; |
723 | unsigned NumEntries; |
724 | unsigned NumTombstones; |
725 | unsigned NumBuckets; |
726 | |
727 | public: |
728 | /// Create a DenseMap with an optional \p InitialReserve that guarantee that |
729 | /// this number of elements can be inserted in the map without grow() |
730 | explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); } |
731 | |
732 | DenseMap(const DenseMap &other) : BaseT() { |
733 | init(0); |
734 | copyFrom(other); |
735 | } |
736 | |
737 | DenseMap(DenseMap &&other) : BaseT() { |
738 | init(0); |
739 | swap(other); |
740 | } |
741 | |
742 | template<typename InputIt> |
743 | DenseMap(const InputIt &I, const InputIt &E) { |
744 | init(std::distance(I, E)); |
745 | this->insert(I, E); |
746 | } |
747 | |
748 | DenseMap(std::initializer_list<typename BaseT::value_type> Vals) { |
749 | init(Vals.size()); |
750 | this->insert(Vals.begin(), Vals.end()); |
751 | } |
752 | |
753 | ~DenseMap() { |
754 | this->destroyAll(); |
755 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
756 | } |
757 | |
758 | void swap(DenseMap& RHS) { |
759 | this->incrementEpoch(); |
760 | RHS.incrementEpoch(); |
761 | std::swap(Buckets, RHS.Buckets); |
762 | std::swap(NumEntries, RHS.NumEntries); |
763 | std::swap(NumTombstones, RHS.NumTombstones); |
764 | std::swap(NumBuckets, RHS.NumBuckets); |
765 | } |
766 | |
767 | DenseMap& operator=(const DenseMap& other) { |
768 | if (&other != this) |
769 | copyFrom(other); |
770 | return *this; |
771 | } |
772 | |
773 | DenseMap& operator=(DenseMap &&other) { |
774 | this->destroyAll(); |
775 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
776 | init(0); |
777 | swap(other); |
778 | return *this; |
779 | } |
780 | |
781 | void copyFrom(const DenseMap& other) { |
782 | this->destroyAll(); |
783 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
784 | if (allocateBuckets(other.NumBuckets)) { |
785 | this->BaseT::copyFrom(other); |
786 | } else { |
787 | NumEntries = 0; |
788 | NumTombstones = 0; |
789 | } |
790 | } |
791 | |
792 | void init(unsigned InitNumEntries) { |
793 | auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries); |
794 | if (allocateBuckets(InitBuckets)) { |
795 | this->BaseT::initEmpty(); |
796 | } else { |
797 | NumEntries = 0; |
798 | NumTombstones = 0; |
799 | } |
800 | } |
801 | |
802 | void grow(unsigned AtLeast) { |
803 | unsigned OldNumBuckets = NumBuckets; |
804 | BucketT *OldBuckets = Buckets; |
805 | |
806 | allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1)))); |
807 | assert(Buckets)((void)0); |
808 | if (!OldBuckets) { |
809 | this->BaseT::initEmpty(); |
810 | return; |
811 | } |
812 | |
813 | this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); |
814 | |
815 | // Free the old table. |
816 | deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets, |
817 | alignof(BucketT)); |
818 | } |
819 | |
820 | void shrink_and_clear() { |
821 | unsigned OldNumBuckets = NumBuckets; |
822 | unsigned OldNumEntries = NumEntries; |
823 | this->destroyAll(); |
824 | |
825 | // Reduce the number of buckets. |
826 | unsigned NewNumBuckets = 0; |
827 | if (OldNumEntries) |
828 | NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); |
829 | if (NewNumBuckets == NumBuckets) { |
830 | this->BaseT::initEmpty(); |
831 | return; |
832 | } |
833 | |
834 | deallocate_buffer(Buckets, sizeof(BucketT) * OldNumBuckets, |
835 | alignof(BucketT)); |
836 | init(NewNumBuckets); |
837 | } |
838 | |
839 | private: |
840 | unsigned getNumEntries() const { |
841 | return NumEntries; |
842 | } |
843 | |
844 | void setNumEntries(unsigned Num) { |
845 | NumEntries = Num; |
846 | } |
847 | |
848 | unsigned getNumTombstones() const { |
849 | return NumTombstones; |
850 | } |
851 | |
852 | void setNumTombstones(unsigned Num) { |
853 | NumTombstones = Num; |
854 | } |
855 | |
856 | BucketT *getBuckets() const { |
857 | return Buckets; |
858 | } |
859 | |
860 | unsigned getNumBuckets() const { |
861 | return NumBuckets; |
862 | } |
863 | |
864 | bool allocateBuckets(unsigned Num) { |
865 | NumBuckets = Num; |
866 | if (NumBuckets == 0) { |
867 | Buckets = nullptr; |
868 | return false; |
869 | } |
870 | |
871 | Buckets = static_cast<BucketT *>( |
872 | allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT))); |
873 | return true; |
874 | } |
875 | }; |
876 | |
877 | template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4, |
878 | typename KeyInfoT = DenseMapInfo<KeyT>, |
879 | typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>> |
880 | class SmallDenseMap |
881 | : public DenseMapBase< |
882 | SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT, |
883 | ValueT, KeyInfoT, BucketT> { |
884 | friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
885 | |
886 | // Lift some types from the dependent base class into this class for |
887 | // simplicity of referring to them. |
888 | using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
889 | |
890 | static_assert(isPowerOf2_64(InlineBuckets), |
891 | "InlineBuckets must be a power of 2."); |
892 | |
893 | unsigned Small : 1; |
894 | unsigned NumEntries : 31; |
895 | unsigned NumTombstones; |
896 | |
897 | struct LargeRep { |
898 | BucketT *Buckets; |
899 | unsigned NumBuckets; |
900 | }; |
901 | |
902 | /// A "union" of an inline bucket array and the struct representing |
903 | /// a large bucket. This union will be discriminated by the 'Small' bit. |
904 | AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; |
905 | |
906 | public: |
907 | explicit SmallDenseMap(unsigned NumInitBuckets = 0) { |
908 | init(NumInitBuckets); |
909 | } |
910 | |
911 | SmallDenseMap(const SmallDenseMap &other) : BaseT() { |
912 | init(0); |
913 | copyFrom(other); |
914 | } |
915 | |
916 | SmallDenseMap(SmallDenseMap &&other) : BaseT() { |
917 | init(0); |
918 | swap(other); |
919 | } |
920 | |
921 | template<typename InputIt> |
922 | SmallDenseMap(const InputIt &I, const InputIt &E) { |
923 | init(NextPowerOf2(std::distance(I, E))); |
924 | this->insert(I, E); |
925 | } |
926 | |
927 | SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals) |
928 | : SmallDenseMap(Vals.begin(), Vals.end()) {} |
929 | |
930 | ~SmallDenseMap() { |
931 | this->destroyAll(); |
932 | deallocateBuckets(); |
933 | } |
934 | |
935 | void swap(SmallDenseMap& RHS) { |
936 | unsigned TmpNumEntries = RHS.NumEntries; |
937 | RHS.NumEntries = NumEntries; |
938 | NumEntries = TmpNumEntries; |
939 | std::swap(NumTombstones, RHS.NumTombstones); |
940 | |
941 | const KeyT EmptyKey = this->getEmptyKey(); |
942 | const KeyT TombstoneKey = this->getTombstoneKey(); |
943 | if (Small && RHS.Small) { |
944 | // If we're swapping inline bucket arrays, we have to cope with some of |
945 | // the tricky bits of DenseMap's storage system: the buckets are not |
946 | // fully initialized. Thus we swap every key, but we may have |
947 | // a one-directional move of the value. |
948 | for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { |
949 | BucketT *LHSB = &getInlineBuckets()[i], |
950 | *RHSB = &RHS.getInlineBuckets()[i]; |
951 | bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) && |
952 | !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey)); |
953 | bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) && |
954 | !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey)); |
955 | if (hasLHSValue && hasRHSValue) { |
956 | // Swap together if we can... |
957 | std::swap(*LHSB, *RHSB); |
958 | continue; |
959 | } |
960 | // Swap separately and handle any asymmetry. |
961 | std::swap(LHSB->getFirst(), RHSB->getFirst()); |
962 | if (hasLHSValue) { |
963 | ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond())); |
964 | LHSB->getSecond().~ValueT(); |
965 | } else if (hasRHSValue) { |
966 | ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond())); |
967 | RHSB->getSecond().~ValueT(); |
968 | } |
969 | } |
970 | return; |
971 | } |
972 | if (!Small && !RHS.Small) { |
973 | std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); |
974 | std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); |
975 | return; |
976 | } |
977 | |
978 | SmallDenseMap &SmallSide = Small ? *this : RHS; |
979 | SmallDenseMap &LargeSide = Small ? RHS : *this; |
980 | |
981 | // First stash the large side's rep and move the small side across. |
982 | LargeRep TmpRep = std::move(*LargeSide.getLargeRep()); |
983 | LargeSide.getLargeRep()->~LargeRep(); |
984 | LargeSide.Small = true; |
985 | // This is similar to the standard move-from-old-buckets, but the bucket |
986 | // count hasn't actually rotated in this case. So we have to carefully |
987 | // move construct the keys and values into their new locations, but there |
988 | // is no need to re-hash things. |
989 | for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { |
990 | BucketT *NewB = &LargeSide.getInlineBuckets()[i], |
991 | *OldB = &SmallSide.getInlineBuckets()[i]; |
992 | ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst())); |
993 | OldB->getFirst().~KeyT(); |
994 | if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) && |
995 | !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) { |
996 | ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond())); |
997 | OldB->getSecond().~ValueT(); |
998 | } |
999 | } |
1000 | |
1001 | // The hard part of moving the small buckets across is done, just move |
1002 | // the TmpRep into its new home. |
1003 | SmallSide.Small = false; |
1004 | new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep)); |
1005 | } |
1006 | |
1007 | SmallDenseMap& operator=(const SmallDenseMap& other) { |
1008 | if (&other != this) |
1009 | copyFrom(other); |
1010 | return *this; |
1011 | } |
1012 | |
1013 | SmallDenseMap& operator=(SmallDenseMap &&other) { |
1014 | this->destroyAll(); |
1015 | deallocateBuckets(); |
1016 | init(0); |
1017 | swap(other); |
1018 | return *this; |
1019 | } |
1020 | |
1021 | void copyFrom(const SmallDenseMap& other) { |
1022 | this->destroyAll(); |
1023 | deallocateBuckets(); |
1024 | Small = true; |
1025 | if (other.getNumBuckets() > InlineBuckets) { |
1026 | Small = false; |
1027 | new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets())); |
1028 | } |
1029 | this->BaseT::copyFrom(other); |
1030 | } |
1031 | |
1032 | void init(unsigned InitBuckets) { |
1033 | Small = true; |
1034 | if (InitBuckets > InlineBuckets) { |
1035 | Small = false; |
1036 | new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); |
1037 | } |
1038 | this->BaseT::initEmpty(); |
1039 | } |
1040 | |
1041 | void grow(unsigned AtLeast) { |
1042 | if (AtLeast > InlineBuckets) |
1043 | AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); |
1044 | |
1045 | if (Small) { |
1046 | // First move the inline buckets into a temporary storage. |
1047 | AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; |
1048 | BucketT *TmpBegin = reinterpret_cast<BucketT *>(&TmpStorage); |
1049 | BucketT *TmpEnd = TmpBegin; |
1050 | |
1051 | // Loop over the buckets, moving non-empty, non-tombstones into the |
1052 | // temporary storage. Have the loop move the TmpEnd forward as it goes. |
1053 | const KeyT EmptyKey = this->getEmptyKey(); |
1054 | const KeyT TombstoneKey = this->getTombstoneKey(); |
1055 | for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { |
1056 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && |
1057 | !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { |
1058 | assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&((void)0) |
1059 | "Too many inline buckets!")((void)0); |
1060 | ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst())); |
1061 | ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond())); |
1062 | ++TmpEnd; |
1063 | P->getSecond().~ValueT(); |
1064 | } |
1065 | P->getFirst().~KeyT(); |
1066 | } |
1067 | |
1068 | // AtLeast == InlineBuckets can happen if there are many tombstones, |
1069 | // and grow() is used to remove them. Usually we always switch to the |
1070 | // large rep here. |
1071 | if (AtLeast > InlineBuckets) { |
1072 | Small = false; |
1073 | new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); |
1074 | } |
1075 | this->moveFromOldBuckets(TmpBegin, TmpEnd); |
1076 | return; |
1077 | } |
1078 | |
1079 | LargeRep OldRep = std::move(*getLargeRep()); |
1080 | getLargeRep()->~LargeRep(); |
1081 | if (AtLeast <= InlineBuckets) { |
1082 | Small = true; |
1083 | } else { |
1084 | new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); |
1085 | } |
1086 | |
1087 | this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); |
1088 | |
1089 | // Free the old table. |
1090 | deallocate_buffer(OldRep.Buckets, sizeof(BucketT) * OldRep.NumBuckets, |
1091 | alignof(BucketT)); |
1092 | } |
1093 | |
1094 | void shrink_and_clear() { |
1095 | unsigned OldSize = this->size(); |
1096 | this->destroyAll(); |
1097 | |
1098 | // Reduce the number of buckets. |
1099 | unsigned NewNumBuckets = 0; |
1100 | if (OldSize) { |
1101 | NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); |
1102 | if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) |
1103 | NewNumBuckets = 64; |
1104 | } |
1105 | if ((Small && NewNumBuckets <= InlineBuckets) || |
1106 | (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { |
1107 | this->BaseT::initEmpty(); |
1108 | return; |
1109 | } |
1110 | |
1111 | deallocateBuckets(); |
1112 | init(NewNumBuckets); |
1113 | } |
1114 | |
1115 | private: |
1116 | unsigned getNumEntries() const { |
1117 | return NumEntries; |
1118 | } |
1119 | |
1120 | void setNumEntries(unsigned Num) { |
1121 | // NumEntries is hardcoded to be 31 bits wide. |
1122 | assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries")((void)0); |
1123 | NumEntries = Num; |
1124 | } |
1125 | |
1126 | unsigned getNumTombstones() const { |
1127 | return NumTombstones; |
1128 | } |
1129 | |
1130 | void setNumTombstones(unsigned Num) { |
1131 | NumTombstones = Num; |
1132 | } |
1133 | |
1134 | const BucketT *getInlineBuckets() const { |
1135 | assert(Small)((void)0); |
1136 | // Note that this cast does not violate aliasing rules as we assert that |
1137 | // the memory's dynamic type is the small, inline bucket buffer, and the |
1138 | // 'storage' is a POD containing a char buffer. |
1139 | return reinterpret_cast<const BucketT *>(&storage); |
1140 | } |
1141 | |
1142 | BucketT *getInlineBuckets() { |
1143 | return const_cast<BucketT *>( |
1144 | const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); |
1145 | } |
1146 | |
1147 | const LargeRep *getLargeRep() const { |
1148 | assert(!Small)((void)0); |
1149 | // Note, same rule about aliasing as with getInlineBuckets. |
1150 | return reinterpret_cast<const LargeRep *>(&storage); |
1151 | } |
1152 | |
1153 | LargeRep *getLargeRep() { |
1154 | return const_cast<LargeRep *>( |
1155 | const_cast<const SmallDenseMap *>(this)->getLargeRep()); |
1156 | } |
1157 | |
1158 | const BucketT *getBuckets() const { |
1159 | return Small ? getInlineBuckets() : getLargeRep()->Buckets; |
1160 | } |
1161 | |
1162 | BucketT *getBuckets() { |
1163 | return const_cast<BucketT *>( |
1164 | const_cast<const SmallDenseMap *>(this)->getBuckets()); |
1165 | } |
1166 | |
1167 | unsigned getNumBuckets() const { |
1168 | return Small ? InlineBuckets : getLargeRep()->NumBuckets; |
1169 | } |
1170 | |
1171 | void deallocateBuckets() { |
1172 | if (Small) |
1173 | return; |
1174 | |
1175 | deallocate_buffer(getLargeRep()->Buckets, |
1176 | sizeof(BucketT) * getLargeRep()->NumBuckets, |
1177 | alignof(BucketT)); |
1178 | getLargeRep()->~LargeRep(); |
1179 | } |
1180 | |
1181 | LargeRep allocateBuckets(unsigned Num) { |
1182 | assert(Num > InlineBuckets && "Must allocate more buckets than are inline")((void)0); |
1183 | LargeRep Rep = {static_cast<BucketT *>(allocate_buffer( |
1184 | sizeof(BucketT) * Num, alignof(BucketT))), |
1185 | Num}; |
1186 | return Rep; |
1187 | } |
1188 | }; |
1189 | |
1190 | template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket, |
1191 | bool IsConst> |
1192 | class DenseMapIterator : DebugEpochBase::HandleBase { |
1193 | friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>; |
1194 | friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>; |
1195 | |
1196 | public: |
1197 | using difference_type = ptrdiff_t; |
1198 | using value_type = |
1199 | typename std::conditional<IsConst, const Bucket, Bucket>::type; |
1200 | using pointer = value_type *; |
1201 | using reference = value_type &; |
1202 | using iterator_category = std::forward_iterator_tag; |
1203 | |
1204 | private: |
1205 | pointer Ptr = nullptr; |
1206 | pointer End = nullptr; |
1207 | |
1208 | public: |
1209 | DenseMapIterator() = default; |
1210 | |
1211 | DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, |
1212 | bool NoAdvance = false) |
1213 | : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { |
1214 | assert(isHandleInSync() && "invalid construction!")((void)0); |
1215 | |
1216 | if (NoAdvance) return; |
1217 | if (shouldReverseIterate<KeyT>()) { |
1218 | RetreatPastEmptyBuckets(); |
1219 | return; |
1220 | } |
1221 | AdvancePastEmptyBuckets(); |
1222 | } |
1223 | |
1224 | // Converting ctor from non-const iterators to const iterators. SFINAE'd out |
1225 | // for const iterator destinations so it doesn't end up as a user defined copy |
1226 | // constructor. |
1227 | template <bool IsConstSrc, |
1228 | typename = std::enable_if_t<!IsConstSrc && IsConst>> |
1229 | DenseMapIterator( |
1230 | const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I) |
1231 | : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {} |
1232 | |
1233 | reference operator*() const { |
1234 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
1235 | assert(Ptr != End && "dereferencing end() iterator")((void)0); |
1236 | if (shouldReverseIterate<KeyT>()) |
1237 | return Ptr[-1]; |
1238 | return *Ptr; |
1239 | } |
1240 | pointer operator->() const { |
1241 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
1242 | assert(Ptr != End && "dereferencing end() iterator")((void)0); |
1243 | if (shouldReverseIterate<KeyT>()) |
1244 | return &(Ptr[-1]); |
1245 | return Ptr; |
1246 | } |
1247 | |
1248 | friend bool operator==(const DenseMapIterator &LHS, |
1249 | const DenseMapIterator &RHS) { |
1250 | assert((!LHS.Ptr || LHS.isHandleInSync()) && "handle not in sync!")((void)0); |
1251 | assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!")((void)0); |
1252 | assert(LHS.getEpochAddress() == RHS.getEpochAddress() &&((void)0) |
1253 | "comparing incomparable iterators!")((void)0); |
1254 | return LHS.Ptr == RHS.Ptr; |
1255 | } |
1256 | |
1257 | friend bool operator!=(const DenseMapIterator &LHS, |
1258 | const DenseMapIterator &RHS) { |
1259 | return !(LHS == RHS); |
1260 | } |
1261 | |
1262 | inline DenseMapIterator& operator++() { // Preincrement |
1263 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
1264 | assert(Ptr != End && "incrementing end() iterator")((void)0); |
1265 | if (shouldReverseIterate<KeyT>()) { |
1266 | --Ptr; |
1267 | RetreatPastEmptyBuckets(); |
1268 | return *this; |
1269 | } |
1270 | ++Ptr; |
1271 | AdvancePastEmptyBuckets(); |
1272 | return *this; |
1273 | } |
1274 | DenseMapIterator operator++(int) { // Postincrement |
1275 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
1276 | DenseMapIterator tmp = *this; ++*this; return tmp; |
1277 | } |
1278 | |
1279 | private: |
1280 | void AdvancePastEmptyBuckets() { |
1281 | assert(Ptr <= End)((void)0); |
1282 | const KeyT Empty = KeyInfoT::getEmptyKey(); |
1283 | const KeyT Tombstone = KeyInfoT::getTombstoneKey(); |
1284 | |
1285 | while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) || |
1286 | KeyInfoT::isEqual(Ptr->getFirst(), Tombstone))) |
1287 | ++Ptr; |
1288 | } |
1289 | |
1290 | void RetreatPastEmptyBuckets() { |
1291 | assert(Ptr >= End)((void)0); |
1292 | const KeyT Empty = KeyInfoT::getEmptyKey(); |
1293 | const KeyT Tombstone = KeyInfoT::getTombstoneKey(); |
1294 | |
1295 | while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) || |
1296 | KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone))) |
1297 | --Ptr; |
1298 | } |
1299 | }; |
1300 | |
1301 | template <typename KeyT, typename ValueT, typename KeyInfoT> |
1302 | inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { |
1303 | return X.getMemorySize(); |
1304 | } |
1305 | |
1306 | } // end namespace llvm |
1307 | |
1308 | #endif // LLVM_ADT_DENSEMAP_H |