/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp

Bug Summary

File:	src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp
Warning:	line 918, column 9 Forming reference to null pointer

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name PDBASTParser.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../include -I /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/obj -I /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -I /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/include -I /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source -I /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/clang/include -I /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/obj/../include/lldb/Plugins -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp

/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp

→

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//===----------------------------------------------------------------------===//

9#include "PDBASTParser.h"

11#include "SymbolFilePDB.h"

13#include "clang/AST/CharUnits.h"
14#include "clang/AST/Decl.h"
15#include "clang/AST/DeclCXX.h"

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"

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"

40#include "Plugins/Language/CPlusPlus/MSVCUndecoratedNameParser.h"

42using namespace lldb;
43using namespace lldb_private;
44using namespace llvm::pdb;

46static int TranslateUdtKind(PDB_UdtType pdb_kind) {
switch (pdb_kind) {
case PDB_UdtType::Class:
  return clang::TTK_Class;
case PDB_UdtType::Struct:
  return clang::TTK_Struct;
case PDB_UdtType::Union:
  return clang::TTK_Union;
case PDB_UdtType::Interface:
  return clang::TTK_Interface;
}
llvm_unreachable("unsuported PDB UDT type")__builtin_unreachable();
58}

60static lldb::Encoding TranslateBuiltinEncoding(PDB_BuiltinType type) {
switch (type) {
case PDB_BuiltinType::Float:
  return lldb::eEncodingIEEE754;
case PDB_BuiltinType::Int:
case PDB_BuiltinType::Long:
case PDB_BuiltinType::Char:
  return lldb::eEncodingSint;
case PDB_BuiltinType::Bool:
case PDB_BuiltinType::Char16:
case PDB_BuiltinType::Char32:
case PDB_BuiltinType::UInt:
case PDB_BuiltinType::ULong:
case PDB_BuiltinType::HResult:
case PDB_BuiltinType::WCharT:
  return lldb::eEncodingUint;
default:
  return lldb::eEncodingInvalid;
}
79}

81static lldb::Encoding TranslateEnumEncoding(PDB_VariantType type) {
switch (type) {
case PDB_VariantType::Int8:
case PDB_VariantType::Int16:
case PDB_VariantType::Int32:
case PDB_VariantType::Int64:
  return lldb::eEncodingSint;

case PDB_VariantType::UInt8:
case PDB_VariantType::UInt16:
case PDB_VariantType::UInt32:
case PDB_VariantType::UInt64:
  return lldb::eEncodingUint;

default:
  break;
}

return lldb::eEncodingSint;
100}

102static CompilerType
103GetBuiltinTypeForPDBEncodingAndBitSize(TypeSystemClang &clang_ast,
                                     const PDBSymbolTypeBuiltin &pdb_type,
                                     Encoding encoding, uint32_t width) {
clang::ASTContext &ast = clang_ast.getASTContext();

switch (pdb_type.getBuiltinType()) {
default:
  break;
case PDB_BuiltinType::None:
  return CompilerType();
case PDB_BuiltinType::Void:
  return clang_ast.GetBasicType(eBasicTypeVoid);
case PDB_BuiltinType::Char:
  return clang_ast.GetBasicType(eBasicTypeChar);
case PDB_BuiltinType::Bool:
  return clang_ast.GetBasicType(eBasicTypeBool);
case PDB_BuiltinType::Long:
  if (width == ast.getTypeSize(ast.LongTy))
    return CompilerType(&clang_ast, ast.LongTy.getAsOpaquePtr());
  if (width == ast.getTypeSize(ast.LongLongTy))
    return CompilerType(&clang_ast, ast.LongLongTy.getAsOpaquePtr());
  break;
case PDB_BuiltinType::ULong:
  if (width == ast.getTypeSize(ast.UnsignedLongTy))
    return CompilerType(&clang_ast, ast.UnsignedLongTy.getAsOpaquePtr());
  if (width == ast.getTypeSize(ast.UnsignedLongLongTy))
    return CompilerType(&clang_ast, ast.UnsignedLongLongTy.getAsOpaquePtr());
  break;
case PDB_BuiltinType::WCharT:
  if (width == ast.getTypeSize(ast.WCharTy))
    return CompilerType(&clang_ast, ast.WCharTy.getAsOpaquePtr());
  break;
case PDB_BuiltinType::Char16:
  return CompilerType(&clang_ast, ast.Char16Ty.getAsOpaquePtr());
case PDB_BuiltinType::Char32:
  return CompilerType(&clang_ast, ast.Char32Ty.getAsOpaquePtr());
case PDB_BuiltinType::Float:
  // Note: types `long double` and `double` have same bit size in MSVC and
  // there is no information in the PDB to distinguish them. So when falling
  // back to default search, the compiler type of `long double` will be
  // represented by the one generated for `double`.
  break;
}
// If there is no match on PDB_BuiltinType, fall back to default search by
// encoding and width only
return clang_ast.GetBuiltinTypeForEncodingAndBitSize(encoding, width);
149}

151static ConstString GetPDBBuiltinTypeName(const PDBSymbolTypeBuiltin &pdb_type,
                                       CompilerType &compiler_type) {
PDB_BuiltinType kind = pdb_type.getBuiltinType();
switch (kind) {
default:
  break;
case PDB_BuiltinType::Currency:
  return ConstString("CURRENCY");
case PDB_BuiltinType::Date:
  return ConstString("DATE");
case PDB_BuiltinType::Variant:
  return ConstString("VARIANT");
case PDB_BuiltinType::Complex:
  return ConstString("complex");
case PDB_BuiltinType::Bitfield:
  return ConstString("bitfield");
case PDB_BuiltinType::BSTR:
  return ConstString("BSTR");
case PDB_BuiltinType::HResult:
  return ConstString("HRESULT");
case PDB_BuiltinType::BCD:
  return ConstString("BCD");
case PDB_BuiltinType::Char16:
  return ConstString("char16_t");
case PDB_BuiltinType::Char32:
  return ConstString("char32_t");
case PDB_BuiltinType::None:
  return ConstString("...");
}
return compiler_type.GetTypeName();
181}

183static bool GetDeclarationForSymbol(const PDBSymbol &symbol,
                                  Declaration &decl) {
auto &raw_sym = symbol.getRawSymbol();
auto first_line_up = raw_sym.getSrcLineOnTypeDefn();

if (!first_line_up) {
  auto lines_up = symbol.getSession().findLineNumbersByAddress(
      raw_sym.getVirtualAddress(), raw_sym.getLength());
  if (!lines_up)
    return false;
  first_line_up = lines_up->getNext();
  if (!first_line_up)
    return false;
}
uint32_t src_file_id = first_line_up->getSourceFileId();
auto src_file_up = symbol.getSession().getSourceFileById(src_file_id);
if (!src_file_up)
  return false;

FileSpec spec(src_file_up->getFileName());
decl.SetFile(spec);
decl.SetColumn(first_line_up->getColumnNumber());
decl.SetLine(first_line_up->getLineNumber());
return true;
207}

209static AccessType TranslateMemberAccess(PDB_MemberAccess access) {
switch (access) {
case PDB_MemberAccess::Private:
  return eAccessPrivate;
case PDB_MemberAccess::Protected:
  return eAccessProtected;
case PDB_MemberAccess::Public:
  return eAccessPublic;
}
return eAccessNone;
219}

221static AccessType GetDefaultAccessibilityForUdtKind(PDB_UdtType udt_kind) {
switch (udt_kind) {
case PDB_UdtType::Struct:
case PDB_UdtType::Union:
  return eAccessPublic;
case PDB_UdtType::Class:
case PDB_UdtType::Interface:
  return eAccessPrivate;
}
llvm_unreachable("unsupported PDB UDT type")__builtin_unreachable();
231}

233static AccessType GetAccessibilityForUdt(const PDBSymbolTypeUDT &udt) {
AccessType access = TranslateMemberAccess(udt.getAccess());
if (access != lldb::eAccessNone || !udt.isNested())
  return access;

auto parent = udt.getClassParent();
if (!parent)
  return lldb::eAccessNone;

auto parent_udt = llvm::dyn_cast<PDBSymbolTypeUDT>(parent.get());
if (!parent_udt)
  return lldb::eAccessNone;

return GetDefaultAccessibilityForUdtKind(parent_udt->getUdtKind());
247}

249static clang::MSInheritanceAttr::Spelling
250GetMSInheritance(const PDBSymbolTypeUDT &udt) {
int base_count = 0;
bool has_virtual = false;

auto bases_enum = udt.findAllChildren<PDBSymbolTypeBaseClass>();
if (bases_enum) {
  while (auto base = bases_enum->getNext()) {
    base_count++;
    has_virtual |= base->isVirtualBaseClass();
  }
}

if (has_virtual)
  return clang::MSInheritanceAttr::Keyword_virtual_inheritance;
if (base_count > 1)
  return clang::MSInheritanceAttr::Keyword_multiple_inheritance;
return clang::MSInheritanceAttr::Keyword_single_inheritance;
267}

269static std::unique_ptr<llvm::pdb::PDBSymbol>
270GetClassOrFunctionParent(const llvm::pdb::PDBSymbol &symbol) {
const IPDBSession &session = symbol.getSession();
const IPDBRawSymbol &raw = symbol.getRawSymbol();
auto tag = symbol.getSymTag();

// For items that are nested inside of a class, return the class that it is
// nested inside of.
// Note that only certain items can be nested inside of classes.
switch (tag) {
case PDB_SymType::Function:
case PDB_SymType::Data:
case PDB_SymType::UDT:
case PDB_SymType::Enum:
case PDB_SymType::FunctionSig:
case PDB_SymType::Typedef:
case PDB_SymType::BaseClass:
case PDB_SymType::VTable: {
  auto class_parent_id = raw.getClassParentId();
  if (auto class_parent = session.getSymbolById(class_parent_id))
    return class_parent;
  break;
}
default:
  break;
}

// Otherwise, if it is nested inside of a function, return the function.
// Note that only certain items can be nested inside of functions.
switch (tag) {
case PDB_SymType::Block:
case PDB_SymType::Data: {
  auto lexical_parent_id = raw.getLexicalParentId();
  auto lexical_parent = session.getSymbolById(lexical_parent_id);
  if (!lexical_parent)
    return nullptr;

  auto lexical_parent_tag = lexical_parent->getSymTag();
  if (lexical_parent_tag == PDB_SymType::Function)
    return lexical_parent;
  if (lexical_parent_tag == PDB_SymType::Exe)
    return nullptr;

  return GetClassOrFunctionParent(*lexical_parent);
}
default:
  return nullptr;
}
317}

319static clang::NamedDecl *
320GetDeclFromContextByName(const clang::ASTContext &ast,
                       const clang::DeclContext &decl_context,
                       llvm::StringRef name) {
clang::IdentifierInfo &ident = ast.Idents.get(name);
clang::DeclarationName decl_name = ast.DeclarationNames.getIdentifier(&ident);
clang::DeclContext::lookup_result result = decl_context.lookup(decl_name);
if (result.empty())
  return nullptr;

return *result.begin();
330}

332static bool IsAnonymousNamespaceName(llvm::StringRef name) {
return name == "`anonymous namespace'" || name == "`anonymous-namespace'";
334}

336static clang::CallingConv TranslateCallingConvention(PDB_CallingConv pdb_cc) {
switch (pdb_cc) {
case llvm::codeview::CallingConvention::NearC:
  return clang::CC_C;
case llvm::codeview::CallingConvention::NearStdCall:
  return clang::CC_X86StdCall;
case llvm::codeview::CallingConvention::NearFast:
  return clang::CC_X86FastCall;
case llvm::codeview::CallingConvention::ThisCall:
  return clang::CC_X86ThisCall;
case llvm::codeview::CallingConvention::NearVector:
  return clang::CC_X86VectorCall;
case llvm::codeview::CallingConvention::NearPascal:
  return clang::CC_X86Pascal;
default:
  assert(false && "Unknown calling convention")((void)0);
  return clang::CC_C;
}
354}

356PDBASTParser::PDBASTParser(lldb_private::TypeSystemClang &ast) : m_ast(ast) {}

358PDBASTParser::~PDBASTParser() = default;

360// DebugInfoASTParser interface

362lldb::TypeSP PDBASTParser::CreateLLDBTypeFromPDBType(const PDBSymbol &type) {
Declaration decl;
switch (type.getSymTag()) {
case PDB_SymType::BaseClass: {
  auto symbol_file = m_ast.GetSymbolFile();
  if (!symbol_file)
    return nullptr;

  auto ty = symbol_file->ResolveTypeUID(type.getRawSymbol().getTypeId());
  return ty ? ty->shared_from_this() : nullptr;
} break;
case PDB_SymType::UDT: {
  auto udt = llvm::dyn_cast<PDBSymbolTypeUDT>(&type);
  assert(udt)((void)0);

  // Note that, unnamed UDT being typedef-ed is generated as a UDT symbol
  // other than a Typedef symbol in PDB. For example,
  //    typedef union { short Row; short Col; } Union;
  // is generated as a named UDT in PDB:
  //    union Union { short Row; short Col; }
  // Such symbols will be handled here.

  // Some UDT with trival ctor has zero length. Just ignore.
  if (udt->getLength() == 0)
    return nullptr;

  // Ignore unnamed-tag UDTs.
  std::string name =
      std::string(MSVCUndecoratedNameParser::DropScope(udt->getName()));
  if (name.empty())
    return nullptr;

  auto decl_context = GetDeclContextContainingSymbol(type);

  // Check if such an UDT already exists in the current context.
  // This may occur with const or volatile types. There are separate type
  // symbols in PDB for types with const or volatile modifiers, but we need
  // to create only one declaration for them all.
  Type::ResolveState type_resolve_state;
  CompilerType clang_type = m_ast.GetTypeForIdentifier<clang::CXXRecordDecl>(
      ConstString(name), decl_context);
  if (!clang_type.IsValid()) {
    auto access = GetAccessibilityForUdt(*udt);

    auto tag_type_kind = TranslateUdtKind(udt->getUdtKind());

    ClangASTMetadata metadata;
    metadata.SetUserID(type.getSymIndexId());
    metadata.SetIsDynamicCXXType(false);

    clang_type = m_ast.CreateRecordType(
        decl_context, OptionalClangModuleID(), access, name, tag_type_kind,
        lldb::eLanguageTypeC_plus_plus, &metadata);
    assert(clang_type.IsValid())((void)0);

    auto record_decl =
        m_ast.GetAsCXXRecordDecl(clang_type.GetOpaqueQualType());
    assert(record_decl)((void)0);
    m_uid_to_decl[type.getSymIndexId()] = record_decl;

    auto inheritance_attr = clang::MSInheritanceAttr::CreateImplicit(
        m_ast.getASTContext(), GetMSInheritance(*udt));
    record_decl->addAttr(inheritance_attr);

    TypeSystemClang::StartTagDeclarationDefinition(clang_type);

    auto children = udt->findAllChildren();
    if (!children || children->getChildCount() == 0) {
      // PDB does not have symbol of forwarder. We assume we get an udt w/o
      // any fields. Just complete it at this point.
      TypeSystemClang::CompleteTagDeclarationDefinition(clang_type);

      TypeSystemClang::SetHasExternalStorage(clang_type.GetOpaqueQualType(),
                                             false);

      type_resolve_state = Type::ResolveState::Full;
    } else {
      // Add the type to the forward declarations. It will help us to avoid
      // an endless recursion in CompleteTypeFromUdt function.
      m_forward_decl_to_uid[record_decl] = type.getSymIndexId();

      TypeSystemClang::SetHasExternalStorage(clang_type.GetOpaqueQualType(),
                                             true);

      type_resolve_state = Type::ResolveState::Forward;
    }
  } else
    type_resolve_state = Type::ResolveState::Forward;

  if (udt->isConstType())
    clang_type = clang_type.AddConstModifier();

  if (udt->isVolatileType())
    clang_type = clang_type.AddVolatileModifier();

  GetDeclarationForSymbol(type, decl);
  return std::make_shared<lldb_private::Type>(
      type.getSymIndexId(), m_ast.GetSymbolFile(), ConstString(name),
      udt->getLength(), nullptr, LLDB_INVALID_UID0xffffffffffffffffULL,
      lldb_private::Type::eEncodingIsUID, decl, clang_type,
      type_resolve_state);
} break;
case PDB_SymType::Enum: {
  auto enum_type = llvm::dyn_cast<PDBSymbolTypeEnum>(&type);
  assert(enum_type)((void)0);

  std::string name =
      std::string(MSVCUndecoratedNameParser::DropScope(enum_type->getName()));
  auto decl_context = GetDeclContextContainingSymbol(type);
  uint64_t bytes = enum_type->getLength();

  // Check if such an enum already exists in the current context
  CompilerType ast_enum = m_ast.GetTypeForIdentifier<clang::EnumDecl>(
      ConstString(name), decl_context);
  if (!ast_enum.IsValid()) {
    auto underlying_type_up = enum_type->getUnderlyingType();
    if (!underlying_type_up)
      return nullptr;

    lldb::Encoding encoding =
        TranslateBuiltinEncoding(underlying_type_up->getBuiltinType());
    // FIXME: Type of underlying builtin is always `Int`. We correct it with
    // the very first enumerator's encoding if any.
    auto first_child = enum_type->findOneChild<PDBSymbolData>();
    if (first_child)
      encoding = TranslateEnumEncoding(first_child->getValue().Type);

    CompilerType builtin_type;
    if (bytes > 0)
      builtin_type = GetBuiltinTypeForPDBEncodingAndBitSize(
          m_ast, *underlying_type_up, encoding, bytes * 8);
    else
      builtin_type = m_ast.GetBasicType(eBasicTypeInt);

    // FIXME: PDB does not have information about scoped enumeration (Enum
    // Class). Set it false for now.
    bool isScoped = false;

    ast_enum = m_ast.CreateEnumerationType(name.c_str(), decl_context,
                                           OptionalClangModuleID(), decl,
                                           builtin_type, isScoped);

    auto enum_decl = TypeSystemClang::GetAsEnumDecl(ast_enum);
    assert(enum_decl)((void)0);
    m_uid_to_decl[type.getSymIndexId()] = enum_decl;

    auto enum_values = enum_type->findAllChildren<PDBSymbolData>();
    if (enum_values) {
      while (auto enum_value = enum_values->getNext()) {
        if (enum_value->getDataKind() != PDB_DataKind::Constant)
          continue;
        AddEnumValue(ast_enum, *enum_value);
      }
    }

    if (TypeSystemClang::StartTagDeclarationDefinition(ast_enum))
      TypeSystemClang::CompleteTagDeclarationDefinition(ast_enum);
  }

  if (enum_type->isConstType())
    ast_enum = ast_enum.AddConstModifier();

  if (enum_type->isVolatileType())
    ast_enum = ast_enum.AddVolatileModifier();

  GetDeclarationForSymbol(type, decl);
  return std::make_shared<lldb_private::Type>(
      type.getSymIndexId(), m_ast.GetSymbolFile(), ConstString(name), bytes,
      nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, lldb_private::Type::eEncodingIsUID, decl,
      ast_enum, lldb_private::Type::ResolveState::Full);
} break;
case PDB_SymType::Typedef: {
  auto type_def = llvm::dyn_cast<PDBSymbolTypeTypedef>(&type);
  assert(type_def)((void)0);

  SymbolFile *symbol_file = m_ast.GetSymbolFile();
  if (!symbol_file)
    return nullptr;

  lldb_private::Type *target_type =
      symbol_file->ResolveTypeUID(type_def->getTypeId());
  if (!target_type)
    return nullptr;

  std::string name =
      std::string(MSVCUndecoratedNameParser::DropScope(type_def->getName()));
  auto decl_ctx = GetDeclContextContainingSymbol(type);

  // Check if such a typedef already exists in the current context
  CompilerType ast_typedef =
      m_ast.GetTypeForIdentifier<clang::TypedefNameDecl>(ConstString(name),
                                                         decl_ctx);
  if (!ast_typedef.IsValid()) {
    CompilerType target_ast_type = target_type->GetFullCompilerType();

    ast_typedef = target_ast_type.CreateTypedef(
        name.c_str(), m_ast.CreateDeclContext(decl_ctx), 0);
    if (!ast_typedef)
      return nullptr;

    auto typedef_decl = TypeSystemClang::GetAsTypedefDecl(ast_typedef);
    assert(typedef_decl)((void)0);
    m_uid_to_decl[type.getSymIndexId()] = typedef_decl;
  }

  if (type_def->isConstType())
    ast_typedef = ast_typedef.AddConstModifier();

  if (type_def->isVolatileType())
    ast_typedef = ast_typedef.AddVolatileModifier();

  GetDeclarationForSymbol(type, decl);
  llvm::Optional<uint64_t> size;
  if (type_def->getLength())
    size = type_def->getLength();
  return std::make_shared<lldb_private::Type>(
      type_def->getSymIndexId(), m_ast.GetSymbolFile(), ConstString(name),
      size, nullptr, target_type->GetID(),
      lldb_private::Type::eEncodingIsTypedefUID, decl, ast_typedef,
      lldb_private::Type::ResolveState::Full);
} break;
case PDB_SymType::Function:
case PDB_SymType::FunctionSig: {
  std::string name;
  PDBSymbolTypeFunctionSig *func_sig = nullptr;
  if (auto pdb_func = llvm::dyn_cast<PDBSymbolFunc>(&type)) {
    if (pdb_func->isCompilerGenerated())
      return nullptr;

    auto sig = pdb_func->getSignature();
    if (!sig)
      return nullptr;
    func_sig = sig.release();
    // Function type is named.
    name = std::string(
        MSVCUndecoratedNameParser::DropScope(pdb_func->getName()));
  } else if (auto pdb_func_sig =
                 llvm::dyn_cast<PDBSymbolTypeFunctionSig>(&type)) {
    func_sig = const_cast<PDBSymbolTypeFunctionSig *>(pdb_func_sig);
  } else
    llvm_unreachable("Unexpected PDB symbol!")__builtin_unreachable();

  auto arg_enum = func_sig->getArguments();
  uint32_t num_args = arg_enum->getChildCount();
  std::vector<CompilerType> arg_list;

  bool is_variadic = func_sig->isCVarArgs();
  // Drop last variadic argument.
  if (is_variadic)
    --num_args;
  for (uint32_t arg_idx = 0; arg_idx < num_args; arg_idx++) {
    auto arg = arg_enum->getChildAtIndex(arg_idx);
    if (!arg)
      break;

    SymbolFile *symbol_file = m_ast.GetSymbolFile();
    if (!symbol_file)
      return nullptr;

    lldb_private::Type *arg_type =
        symbol_file->ResolveTypeUID(arg->getSymIndexId());
    // If there's some error looking up one of the dependent types of this
    // function signature, bail.
    if (!arg_type)
      return nullptr;
    CompilerType arg_ast_type = arg_type->GetFullCompilerType();
    arg_list.push_back(arg_ast_type);
  }
  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);

  auto pdb_return_type = func_sig->getReturnType();
  SymbolFile *symbol_file = m_ast.GetSymbolFile();
  if (!symbol_file)
    return nullptr;

  lldb_private::Type *return_type =
      symbol_file->ResolveTypeUID(pdb_return_type->getSymIndexId());
  // If there's some error looking up one of the dependent types of this
  // function signature, bail.
  if (!return_type)
    return nullptr;
  CompilerType return_ast_type = return_type->GetFullCompilerType();
  uint32_t type_quals = 0;
  if (func_sig->isConstType())
    type_quals |= clang::Qualifiers::Const;
  if (func_sig->isVolatileType())
    type_quals |= clang::Qualifiers::Volatile;
  auto cc = TranslateCallingConvention(func_sig->getCallingConvention());
  CompilerType func_sig_ast_type =
      m_ast.CreateFunctionType(return_ast_type, arg_list.data(),
                               arg_list.size(), is_variadic, type_quals, cc);

  GetDeclarationForSymbol(type, decl);
  return std::make_shared<lldb_private::Type>(
      type.getSymIndexId(), m_ast.GetSymbolFile(), ConstString(name),
      llvm::None, nullptr, LLDB_INVALID_UID0xffffffffffffffffULL,
      lldb_private::Type::eEncodingIsUID, decl, func_sig_ast_type,
      lldb_private::Type::ResolveState::Full);
} break;
case PDB_SymType::ArrayType: {
  auto array_type = llvm::dyn_cast<PDBSymbolTypeArray>(&type);
  assert(array_type)((void)0);
  uint32_t num_elements = array_type->getCount();
  uint32_t element_uid = array_type->getElementTypeId();
  llvm::Optional<uint64_t> bytes;
  if (uint64_t size = array_type->getLength())
    bytes = size;

  SymbolFile *symbol_file = m_ast.GetSymbolFile();
  if (!symbol_file)
    return nullptr;

  // If array rank > 0, PDB gives the element type at N=0. So element type
  // will parsed in the order N=0, N=1,..., N=rank sequentially.
  lldb_private::Type *element_type = symbol_file->ResolveTypeUID(element_uid);
  if (!element_type)
    return nullptr;

  CompilerType element_ast_type = element_type->GetForwardCompilerType();
  // If element type is UDT, it needs to be complete.
  if (TypeSystemClang::IsCXXClassType(element_ast_type) &&
      !element_ast_type.GetCompleteType()) {
    if (TypeSystemClang::StartTagDeclarationDefinition(element_ast_type)) {
      TypeSystemClang::CompleteTagDeclarationDefinition(element_ast_type);
    } else {
      // We are not able to start defintion.
      return nullptr;
    }
  }
  CompilerType array_ast_type = m_ast.CreateArrayType(
      element_ast_type, num_elements, /*is_gnu_vector*/ false);
  TypeSP type_sp = std::make_shared<lldb_private::Type>(
      array_type->getSymIndexId(), m_ast.GetSymbolFile(), ConstString(),
      bytes, nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, lldb_private::Type::eEncodingIsUID,
      decl, array_ast_type, lldb_private::Type::ResolveState::Full);
  type_sp->SetEncodingType(element_type);
  return type_sp;
} break;
case PDB_SymType::BuiltinType: {
  auto *builtin_type = llvm::dyn_cast<PDBSymbolTypeBuiltin>(&type);
  assert(builtin_type)((void)0);
  PDB_BuiltinType builtin_kind = builtin_type->getBuiltinType();
  if (builtin_kind == PDB_BuiltinType::None)
    return nullptr;

  llvm::Optional<uint64_t> bytes;
  if (uint64_t size = builtin_type->getLength())
    bytes = size;
  Encoding encoding = TranslateBuiltinEncoding(builtin_kind);
  CompilerType builtin_ast_type = GetBuiltinTypeForPDBEncodingAndBitSize(
      m_ast, *builtin_type, encoding, bytes.getValueOr(0) * 8);

  if (builtin_type->isConstType())
    builtin_ast_type = builtin_ast_type.AddConstModifier();

  if (builtin_type->isVolatileType())
    builtin_ast_type = builtin_ast_type.AddVolatileModifier();

  auto type_name = GetPDBBuiltinTypeName(*builtin_type, builtin_ast_type);

  return std::make_shared<lldb_private::Type>(
      builtin_type->getSymIndexId(), m_ast.GetSymbolFile(), type_name, bytes,
      nullptr, LLDB_INVALID_UID0xffffffffffffffffULL, lldb_private::Type::eEncodingIsUID, decl,
      builtin_ast_type, lldb_private::Type::ResolveState::Full);
} break;
case PDB_SymType::PointerType: {
  auto *pointer_type = llvm::dyn_cast<PDBSymbolTypePointer>(&type);
  assert(pointer_type)((void)0);

  SymbolFile *symbol_file = m_ast.GetSymbolFile();
  if (!symbol_file)
    return nullptr;

  Type *pointee_type = symbol_file->ResolveTypeUID(
      pointer_type->getPointeeType()->getSymIndexId());
  if (!pointee_type)
    return nullptr;

  if (pointer_type->isPointerToDataMember() ||
      pointer_type->isPointerToMemberFunction()) {
    auto class_parent_uid = pointer_type->getRawSymbol().getClassParentId();
    auto class_parent_type = symbol_file->ResolveTypeUID(class_parent_uid);
    assert(class_parent_type)((void)0);

    CompilerType pointer_ast_type;
    pointer_ast_type = TypeSystemClang::CreateMemberPointerType(
        class_parent_type->GetLayoutCompilerType(),
        pointee_type->GetForwardCompilerType());
    assert(pointer_ast_type)((void)0);

    return std::make_shared<lldb_private::Type>(
        pointer_type->getSymIndexId(), m_ast.GetSymbolFile(), ConstString(),
        pointer_type->getLength(), nullptr, LLDB_INVALID_UID0xffffffffffffffffULL,
        lldb_private::Type::eEncodingIsUID, decl, pointer_ast_type,
        lldb_private::Type::ResolveState::Forward);
  }

  CompilerType pointer_ast_type;
  pointer_ast_type = pointee_type->GetFullCompilerType();
  if (pointer_type->isReference())
    pointer_ast_type = pointer_ast_type.GetLValueReferenceType();
  else if (pointer_type->isRValueReference())
    pointer_ast_type = pointer_ast_type.GetRValueReferenceType();
  else
    pointer_ast_type = pointer_ast_type.GetPointerType();

  if (pointer_type->isConstType())
    pointer_ast_type = pointer_ast_type.AddConstModifier();

  if (pointer_type->isVolatileType())
    pointer_ast_type = pointer_ast_type.AddVolatileModifier();

  if (pointer_type->isRestrictedType())
    pointer_ast_type = pointer_ast_type.AddRestrictModifier();

  return std::make_shared<lldb_private::Type>(
      pointer_type->getSymIndexId(), m_ast.GetSymbolFile(), ConstString(),
      pointer_type->getLength(), nullptr, LLDB_INVALID_UID0xffffffffffffffffULL,
      lldb_private::Type::eEncodingIsUID, decl, pointer_ast_type,
      lldb_private::Type::ResolveState::Full);
} break;
default:
  break;
}
return nullptr;
787}

789bool PDBASTParser::CompleteTypeFromPDB(
  lldb_private::CompilerType &compiler_type) {
if (GetClangASTImporter().CanImport(compiler_type))
  return GetClangASTImporter().CompleteType(compiler_type);

// Remove the type from the forward declarations to avoid
// an endless recursion for types like a linked list.
clang::CXXRecordDecl *record_decl =
    m_ast.GetAsCXXRecordDecl(compiler_type.GetOpaqueQualType());
auto uid_it = m_forward_decl_to_uid.find(record_decl);
if (uid_it == m_forward_decl_to_uid.end())
  return true;

auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile());
if (!symbol_file)
  return false;

std::unique_ptr<PDBSymbol> symbol =
    symbol_file->GetPDBSession().getSymbolById(uid_it->getSecond());
if (!symbol)
  return false;

m_forward_decl_to_uid.erase(uid_it);

TypeSystemClang::SetHasExternalStorage(compiler_type.GetOpaqueQualType(),
                                       false);

switch (symbol->getSymTag()) {
case PDB_SymType::UDT: {
  auto udt = llvm::dyn_cast<PDBSymbolTypeUDT>(symbol.get());
  if (!udt)
    return false;

  return CompleteTypeFromUDT(*symbol_file, compiler_type, *udt);
}
default:
  llvm_unreachable("not a forward clang type decl!")__builtin_unreachable();
}
827}

829clang::Decl *
830PDBASTParser::GetDeclForSymbol(const llvm::pdb::PDBSymbol &symbol) {
uint32_t sym_id = symbol.getSymIndexId();
auto it = m_uid_to_decl.find(sym_id);
if (it != m_uid_to_decl.end())
8
←
Taking false branch→
31
←
Calling 'operator!='→
37
←
Returning from 'operator!='→
38
←
Taking false branch→
  return it->second;

auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile());
if (!symbol_file)
9
←
Assuming 'symbol_file' is non-null→
10
←
Taking false branch→
39
←
Assuming 'symbol_file' is non-null→
40
←
Taking false branch→
  return nullptr;

// First of all, check if the symbol is a member of a class. Resolve the full
// class type and return the declaration from the cache if so.
auto tag = symbol.getSymTag();
if (tag == PDB_SymType::Data || tag == PDB_SymType::Function) {
11
←
Assuming 'tag' is not equal to Data→
12
←
Assuming 'tag' is not equal to Function→
13
←
Taking false branch→
41
←
Assuming 'tag' is not equal to Data→
42
←
Assuming 'tag' is not equal to Function→
43
←
Taking false branch→
  const IPDBSession &session = symbol.getSession();
  const IPDBRawSymbol &raw = symbol.getRawSymbol();

  auto class_parent_id = raw.getClassParentId();
  if (std::unique_ptr<PDBSymbol> class_parent =
          session.getSymbolById(class_parent_id)) {
    auto class_parent_type = symbol_file->ResolveTypeUID(class_parent_id);
    if (!class_parent_type)
      return nullptr;

    CompilerType class_parent_ct = class_parent_type->GetFullCompilerType();

    // Look a declaration up in the cache after completing the class
    clang::Decl *decl = m_uid_to_decl.lookup(sym_id);
    if (decl)
      return decl;

    // A declaration was not found in the cache. It means that the symbol
    // has the class parent, but the class doesn't have the symbol in its
    // children list.
    if (auto func = llvm::dyn_cast_or_null<PDBSymbolFunc>(&symbol)) {
      // Try to find a class child method with the same RVA and use its
      // declaration if found.
      if (uint32_t rva = func->getRelativeVirtualAddress()) {
        if (std::unique_ptr<ConcreteSymbolEnumerator<PDBSymbolFunc>>
                methods_enum =
                    class_parent->findAllChildren<PDBSymbolFunc>()) {
          while (std::unique_ptr<PDBSymbolFunc> method =
                     methods_enum->getNext()) {
            if (method->getRelativeVirtualAddress() == rva) {
              decl = m_uid_to_decl.lookup(method->getSymIndexId());
              if (decl)
                break;
            }
          }
        }
      }

      // If no class methods with the same RVA were found, then create a new
      // method. It is possible for template methods.
      if (!decl)
        decl = AddRecordMethod(*symbol_file, class_parent_ct, *func);
    }

    if (decl)
      m_uid_to_decl[sym_id] = decl;

    return decl;
  }
}

// If we are here, then the symbol is not belonging to a class and is not
// contained in the cache. So create a declaration for it.
switch (symbol.getSymTag()) {
14
←
Control jumps to 'case Function:'  at line 933→
44
←
Control jumps to 'case Data:'  at line 898→
case PDB_SymType::Data: {
  auto data = llvm::dyn_cast<PDBSymbolData>(&symbol);
45
←
Assuming the object is a 'PDBSymbolData'→
  assert(data)((void)0);

  auto decl_context = GetDeclContextContainingSymbol(symbol);
46
←
'decl_context' initialized here→
  assert(decl_context)((void)0);

  // May be the current context is a class really, but we haven't found
  // any class parent. This happens e.g. in the case of class static
  // variables - they has two symbols, one is a child of the class when
  // another is a child of the exe. So always complete the parent and use
  // an existing declaration if possible.
  if (auto parent_decl48.1
'parent_decl' is null
1
'parent_decl' is null
 = llvm::dyn_cast_or_null<clang::TagDecl>(decl_context))
47
←
Assuming null pointer is passed into cast→
48
←
Assuming pointer value is null→
49
←
Taking false branch→
    m_ast.GetCompleteDecl(parent_decl);

  std::string name =
      std::string(MSVCUndecoratedNameParser::DropScope(data->getName()));

  // Check if the current context already contains the symbol with the name.
  clang::Decl *decl =
      GetDeclFromContextByName(m_ast.getASTContext(), *decl_context, name);
50
←
Forming reference to null pointer
  if (!decl) {
    auto type = symbol_file->ResolveTypeUID(data->getTypeId());
    if (!type)
      return nullptr;

    decl = m_ast.CreateVariableDeclaration(
        decl_context, OptionalClangModuleID(), name.c_str(),
        ClangUtil::GetQualType(type->GetLayoutCompilerType()));
  }

  m_uid_to_decl[sym_id] = decl;

  return decl;
}
case PDB_SymType::Function: {
  auto func = llvm::dyn_cast<PDBSymbolFunc>(&symbol);
15
←
Assuming the object is not a 'PDBSymbolFunc'→
  assert(func)((void)0);

  auto decl_context = GetDeclContextContainingSymbol(symbol);
16
←
Calling 'PDBASTParser::GetDeclContextContainingSymbol'→
  assert(decl_context)((void)0);

  std::string name =
      std::string(MSVCUndecoratedNameParser::DropScope(func->getName()));

  Type *type = symbol_file->ResolveTypeUID(sym_id);
  if (!type)
    return nullptr;

  auto storage = func->isStatic() ? clang::StorageClass::SC_Static
                                  : clang::StorageClass::SC_None;

  auto decl = m_ast.CreateFunctionDeclaration(
      decl_context, OptionalClangModuleID(), name,
      type->GetForwardCompilerType(), storage, func->hasInlineAttribute());

  std::vector<clang::ParmVarDecl *> params;
  if (std::unique_ptr<PDBSymbolTypeFunctionSig> sig = func->getSignature()) {
    if (std::unique_ptr<ConcreteSymbolEnumerator<PDBSymbolTypeFunctionArg>>
            arg_enum = sig->findAllChildren<PDBSymbolTypeFunctionArg>()) {
      while (std::unique_ptr<PDBSymbolTypeFunctionArg> arg =
                 arg_enum->getNext()) {
        Type *arg_type = symbol_file->ResolveTypeUID(arg->getTypeId());
        if (!arg_type)
          continue;

        clang::ParmVarDecl *param = m_ast.CreateParameterDeclaration(
            decl, OptionalClangModuleID(), nullptr,
            arg_type->GetForwardCompilerType(), clang::SC_None, true);
        if (param)
          params.push_back(param);
      }
    }
  }
  if (params.size())
    m_ast.SetFunctionParameters(decl, params);

  m_uid_to_decl[sym_id] = decl;

  return decl;
}
default: {
  // It's not a variable and not a function, check if it's a type
  Type *type = symbol_file->ResolveTypeUID(sym_id);
  if (!type)
    return nullptr;

  return m_uid_to_decl.lookup(sym_id);
}
}
988}

990clang::DeclContext *
991PDBASTParser::GetDeclContextForSymbol(const llvm::pdb::PDBSymbol &symbol) {
if (symbol.getSymTag() == PDB_SymType::Function) {
28
←
Assuming the condition is true→
29
←
Taking true branch→
  clang::DeclContext *result =
      llvm::dyn_cast_or_null<clang::FunctionDecl>(GetDeclForSymbol(symbol));
30
←
Calling 'PDBASTParser::GetDeclForSymbol'→

  if (result)
    m_decl_context_to_uid[result] = symbol.getSymIndexId();

  return result;
}

auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile());
if (!symbol_file)
  return nullptr;

auto type = symbol_file->ResolveTypeUID(symbol.getSymIndexId());
if (!type)
  return nullptr;

clang::DeclContext *result =
    m_ast.GetDeclContextForType(type->GetForwardCompilerType());

if (result)
  m_decl_context_to_uid[result] = symbol.getSymIndexId();

return result;
1017}

1019clang::DeclContext *PDBASTParser::GetDeclContextContainingSymbol(
  const llvm::pdb::PDBSymbol &symbol) {
auto parent = GetClassOrFunctionParent(symbol);
while (parent) {
17
←
Loop condition is false. Execution continues on line 1036→
  if (auto parent_context = GetDeclContextForSymbol(*parent))
    return parent_context;

  parent = GetClassOrFunctionParent(*parent);
}

// We can't find any class or function parent of the symbol. So analyze
// the full symbol name. The symbol may be belonging to a namespace
// or function (or even to a class if it's e.g. a static variable symbol).

// TODO: Make clang to emit full names for variables in namespaces
// (as MSVC does)

std::string name(symbol.getRawSymbol().getName());
MSVCUndecoratedNameParser parser(name);
llvm::ArrayRef<MSVCUndecoratedNameSpecifier> specs = parser.GetSpecifiers();
if (specs.empty())
18
←
Assuming the condition is false→
19
←
Taking false branch→
  return m_ast.GetTranslationUnitDecl();

auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile());
if (!symbol_file)
20
←
Assuming 'symbol_file' is non-null→
21
←
Taking false branch→
  return m_ast.GetTranslationUnitDecl();

auto global = symbol_file->GetPDBSession().getGlobalScope();
if (!global)
22
←
Taking false branch→
  return m_ast.GetTranslationUnitDecl();

bool has_type_or_function_parent = false;
clang::DeclContext *curr_context = m_ast.GetTranslationUnitDecl();
for (std::size_t i = 0; i < specs.size() - 1; i++) {
23
←
Assuming the condition is true→
24
←
Loop condition is true.  Entering loop body→
  // Check if there is a function or a type with the current context's name.
  if (std::unique_ptr<IPDBEnumSymbols> children_enum = global->findChildren(
25
←
Taking true branch→
          PDB_SymType::None, specs[i].GetFullName(), NS_CaseSensitive)) {
    while (IPDBEnumChildren<PDBSymbol>::ChildTypePtr child =
26
←
Loop condition is true.  Entering loop body→
               children_enum->getNext()) {
      if (clang::DeclContext *child_context =
              GetDeclContextForSymbol(*child)) {
27
←
Calling 'PDBASTParser::GetDeclContextForSymbol'→
        // Note that `GetDeclContextForSymbol' retrieves
        // a declaration context for functions and types only,
        // so if we are here then `child_context' is guaranteed
        // a function or a type declaration context.
        has_type_or_function_parent = true;
        curr_context = child_context;
      }
    }
  }

  // If there were no functions or types above then retrieve a namespace with
  // the current context's name. There can be no namespaces inside a function
  // or a type. We check it to avoid fake namespaces such as `__l2':
  // `N0::N1::CClass::PrivateFunc::__l2::InnerFuncStruct'
  if (!has_type_or_function_parent) {
    std::string namespace_name = std::string(specs[i].GetBaseName());
    const char *namespace_name_c_str =
        IsAnonymousNamespaceName(namespace_name) ? nullptr
                                                 : namespace_name.data();
    clang::NamespaceDecl *namespace_decl =
        m_ast.GetUniqueNamespaceDeclaration(
            namespace_name_c_str, curr_context, OptionalClangModuleID());

    m_parent_to_namespaces[curr_context].insert(namespace_decl);
    m_namespaces.insert(namespace_decl);

    curr_context = namespace_decl;
  }
}

return curr_context;
1091}

1093void PDBASTParser::ParseDeclsForDeclContext(
  const clang::DeclContext *decl_context) {
auto symbol_file = static_cast<SymbolFilePDB *>(m_ast.GetSymbolFile());
if (!symbol_file)
1
Assuming 'symbol_file' is non-null→
2
←
Taking false branch→
  return;

IPDBSession &session = symbol_file->GetPDBSession();
auto symbol_up =
    session.getSymbolById(m_decl_context_to_uid.lookup(decl_context));
auto global_up = session.getGlobalScope();

PDBSymbol *symbol;
if (symbol_up)
3
←
Taking false branch→
  symbol = symbol_up.get();
else if (global_up)
4
←
Taking true branch→
  symbol = global_up.get();
else
  return;

if (auto children = symbol->findAllChildren())
5
←
Taking true branch→
  while (auto child = children->getNext())
6
←
Loop condition is true.  Entering loop body→
    GetDeclForSymbol(*child);
7
←
Calling 'PDBASTParser::GetDeclForSymbol'→
1115}

1117clang::NamespaceDecl *
1118PDBASTParser::FindNamespaceDecl(const clang::DeclContext *parent,
                              llvm::StringRef name) {
NamespacesSet *set;
if (parent) {
  auto pit = m_parent_to_namespaces.find(parent);
  if (pit == m_parent_to_namespaces.end())
    return nullptr;

  set = &pit->second;
} else {
  set = &m_namespaces;
}
assert(set)((void)0);

for (clang::NamespaceDecl *namespace_decl : *set)
  if (namespace_decl->getName().equals(name))
    return namespace_decl;

for (clang::NamespaceDecl *namespace_decl : *set)
  if (namespace_decl->isAnonymousNamespace())
    return FindNamespaceDecl(namespace_decl, name);

return nullptr;
1141}

1143bool PDBASTParser::AddEnumValue(CompilerType enum_type,
                              const PDBSymbolData &enum_value) {
Declaration decl;
Variant v = enum_value.getValue();
std::string name =
    std::string(MSVCUndecoratedNameParser::DropScope(enum_value.getName()));
int64_t raw_value;
switch (v.Type) {
case PDB_VariantType::Int8:
  raw_value = v.Value.Int8;
  break;
case PDB_VariantType::Int16:
  raw_value = v.Value.Int16;
  break;
case PDB_VariantType::Int32:
  raw_value = v.Value.Int32;
  break;
case PDB_VariantType::Int64:
  raw_value = v.Value.Int64;
  break;
case PDB_VariantType::UInt8:
  raw_value = v.Value.UInt8;
  break;
case PDB_VariantType::UInt16:
  raw_value = v.Value.UInt16;
  break;
case PDB_VariantType::UInt32:
  raw_value = v.Value.UInt32;
  break;
case PDB_VariantType::UInt64:
  raw_value = v.Value.UInt64;
  break;
default:
  return false;
}
CompilerType underlying_type = m_ast.GetEnumerationIntegerType(enum_type);
uint32_t byte_size = m_ast.getASTContext().getTypeSize(
    ClangUtil::GetQualType(underlying_type));
auto enum_constant_decl = m_ast.AddEnumerationValueToEnumerationType(
    enum_type, decl, name.c_str(), raw_value, byte_size * 8);
if (!enum_constant_decl)
  return false;

m_uid_to_decl[enum_value.getSymIndexId()] = enum_constant_decl;

return true;
1189}

1191bool PDBASTParser::CompleteTypeFromUDT(
  lldb_private::SymbolFile &symbol_file,
  lldb_private::CompilerType &compiler_type,
  llvm::pdb::PDBSymbolTypeUDT &udt) {
ClangASTImporter::LayoutInfo layout_info;
layout_info.bit_size = udt.getLength() * 8;

auto nested_enums = udt.findAllChildren<PDBSymbolTypeUDT>();
if (nested_enums)
  while (auto nested = nested_enums->getNext())
    symbol_file.ResolveTypeUID(nested->getSymIndexId());

auto bases_enum = udt.findAllChildren<PDBSymbolTypeBaseClass>();
if (bases_enum)
  AddRecordBases(symbol_file, compiler_type,
                 TranslateUdtKind(udt.getUdtKind()), *bases_enum,
                 layout_info);

auto members_enum = udt.findAllChildren<PDBSymbolData>();
if (members_enum)
  AddRecordMembers(symbol_file, compiler_type, *members_enum, layout_info);

auto methods_enum = udt.findAllChildren<PDBSymbolFunc>();
if (methods_enum)
  AddRecordMethods(symbol_file, compiler_type, *methods_enum);

m_ast.AddMethodOverridesForCXXRecordType(compiler_type.GetOpaqueQualType());
TypeSystemClang::BuildIndirectFields(compiler_type);
TypeSystemClang::CompleteTagDeclarationDefinition(compiler_type);

clang::CXXRecordDecl *record_decl =
    m_ast.GetAsCXXRecordDecl(compiler_type.GetOpaqueQualType());
if (!record_decl)
  return static_cast<bool>(compiler_type);

GetClangASTImporter().SetRecordLayout(record_decl, layout_info);

return static_cast<bool>(compiler_type);
1229}

1231void PDBASTParser::AddRecordMembers(
  lldb_private::SymbolFile &symbol_file,
  lldb_private::CompilerType &record_type,
  PDBDataSymbolEnumerator &members_enum,
  lldb_private::ClangASTImporter::LayoutInfo &layout_info) {
while (auto member = members_enum.getNext()) {
  if (member->isCompilerGenerated())
    continue;

  auto member_name = member->getName();

  auto member_type = symbol_file.ResolveTypeUID(member->getTypeId());
  if (!member_type)
    continue;

  auto member_comp_type = member_type->GetLayoutCompilerType();
  if (!member_comp_type.GetCompleteType()) {
    symbol_file.GetObjectFile()->GetModule()->ReportError(
        ":: Class '%s' has a member '%s' of type '%s' "
        "which does not have a complete definition.",
        record_type.GetTypeName().GetCString(), member_name.c_str(),
        member_comp_type.GetTypeName().GetCString());
    if (TypeSystemClang::StartTagDeclarationDefinition(member_comp_type))
      TypeSystemClang::CompleteTagDeclarationDefinition(member_comp_type);
  }

  auto access = TranslateMemberAccess(member->getAccess());

  switch (member->getDataKind()) {
  case PDB_DataKind::Member: {
    auto location_type = member->getLocationType();

    auto bit_size = member->getLength();
    if (location_type == PDB_LocType::ThisRel)
      bit_size *= 8;

    auto decl = TypeSystemClang::AddFieldToRecordType(
        record_type, member_name.c_str(), member_comp_type, access, bit_size);
    if (!decl)
      continue;

    m_uid_to_decl[member->getSymIndexId()] = decl;

    auto offset = member->getOffset() * 8;
    if (location_type == PDB_LocType::BitField)
      offset += member->getBitPosition();

    layout_info.field_offsets.insert(std::make_pair(decl, offset));

    break;
  }
  case PDB_DataKind::StaticMember: {
    auto decl = TypeSystemClang::AddVariableToRecordType(
        record_type, member_name.c_str(), member_comp_type, access);
    if (!decl)
      continue;

    // Static constant members may be a const[expr] declaration.
    // Query the symbol's value as the variable initializer if valid.
    if (member_comp_type.IsConst()) {
      auto value = member->getValue();
      clang::QualType qual_type = decl->getType();
      unsigned type_width = m_ast.getASTContext().getIntWidth(qual_type);
      unsigned constant_width = value.getBitWidth();

      if (qual_type->isIntegralOrEnumerationType()) {
        if (type_width >= constant_width) {
          TypeSystemClang::SetIntegerInitializerForVariable(
              decl, value.toAPSInt().extOrTrunc(type_width));
        } else {
          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)
                   "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)
                   "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)
                   "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)
                   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)
                   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)
                   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);
        }
      } else {
        switch (member_comp_type.GetBasicTypeEnumeration()) {
        case lldb::eBasicTypeFloat:
        case lldb::eBasicTypeDouble:
        case lldb::eBasicTypeLongDouble:
          if (type_width == constant_width) {
            TypeSystemClang::SetFloatingInitializerForVariable(
                decl, value.toAPFloat());
            decl->setConstexpr(true);
          } else {
            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)
                     "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)
                     "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)
                     "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)
                     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)
                     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)
                     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);
          }
          break;
        default:
          break;
        }
      }
    }

    m_uid_to_decl[member->getSymIndexId()] = decl;

    break;
  }
  default:
    llvm_unreachable("unsupported PDB data kind")__builtin_unreachable();
  }
}
1342}

1344void PDBASTParser::AddRecordBases(
  lldb_private::SymbolFile &symbol_file,
  lldb_private::CompilerType &record_type, int record_kind,
  PDBBaseClassSymbolEnumerator &bases_enum,
  lldb_private::ClangASTImporter::LayoutInfo &layout_info) const {
std::vector<std::unique_ptr<clang::CXXBaseSpecifier>> base_classes;

while (auto base = bases_enum.getNext()) {
  auto base_type = symbol_file.ResolveTypeUID(base->getTypeId());
  if (!base_type)
    continue;

  auto base_comp_type = base_type->GetFullCompilerType();
  if (!base_comp_type.GetCompleteType()) {
    symbol_file.GetObjectFile()->GetModule()->ReportError(
        ":: Class '%s' has a base class '%s' "
        "which does not have a complete definition.",
        record_type.GetTypeName().GetCString(),
        base_comp_type.GetTypeName().GetCString());
    if (TypeSystemClang::StartTagDeclarationDefinition(base_comp_type))
      TypeSystemClang::CompleteTagDeclarationDefinition(base_comp_type);
  }

  auto access = TranslateMemberAccess(base->getAccess());

  auto is_virtual = base->isVirtualBaseClass();

  std::unique_ptr<clang::CXXBaseSpecifier> base_spec =
      m_ast.CreateBaseClassSpecifier(base_comp_type.GetOpaqueQualType(),
                                     access, is_virtual,
                                     record_kind == clang::TTK_Class);
  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);

  base_classes.push_back(std::move(base_spec));

  if (is_virtual)
    continue;

  auto decl = m_ast.GetAsCXXRecordDecl(base_comp_type.GetOpaqueQualType());
  if (!decl)
    continue;

  auto offset = clang::CharUnits::fromQuantity(base->getOffset());
  layout_info.base_offsets.insert(std::make_pair(decl, offset));
}

m_ast.TransferBaseClasses(record_type.GetOpaqueQualType(),
                          std::move(base_classes));
1392}

1394void PDBASTParser::AddRecordMethods(lldb_private::SymbolFile &symbol_file,
                                  lldb_private::CompilerType &record_type,
                                  PDBFuncSymbolEnumerator &methods_enum) {
while (std::unique_ptr<PDBSymbolFunc> method = methods_enum.getNext())
  if (clang::CXXMethodDecl *decl =
          AddRecordMethod(symbol_file, record_type, *method))
    m_uid_to_decl[method->getSymIndexId()] = decl;
1401}

1403clang::CXXMethodDecl *
1404PDBASTParser::AddRecordMethod(lldb_private::SymbolFile &symbol_file,
                            lldb_private::CompilerType &record_type,
                            const llvm::pdb::PDBSymbolFunc &method) const {
std::string name =
    std::string(MSVCUndecoratedNameParser::DropScope(method.getName()));

Type *method_type = symbol_file.ResolveTypeUID(method.getSymIndexId());
// MSVC specific __vecDelDtor.
if (!method_type)
  return nullptr;

CompilerType method_comp_type = method_type->GetFullCompilerType();
if (!method_comp_type.GetCompleteType()) {
  symbol_file.GetObjectFile()->GetModule()->ReportError(
      ":: Class '%s' has a method '%s' whose type cannot be completed.",
      record_type.GetTypeName().GetCString(),
      method_comp_type.GetTypeName().GetCString());
  if (TypeSystemClang::StartTagDeclarationDefinition(method_comp_type))
    TypeSystemClang::CompleteTagDeclarationDefinition(method_comp_type);
}

AccessType access = TranslateMemberAccess(method.getAccess());
if (access == eAccessNone)
  access = eAccessPublic;

// TODO: get mangled name for the method.
return m_ast.AddMethodToCXXRecordType(
    record_type.GetOpaqueQualType(), name.c_str(),
    /*mangled_name*/ nullptr, method_comp_type, access, method.isVirtual(),
    method.isStatic(), method.hasInlineAttribute(),
    /*is_explicit*/ false, // FIXME: Need this field in CodeView.
    /*is_attr_used*/ false,
    /*is_artificial*/ method.isCompilerGenerated());
1437}

←

/usr/src/gnu/usr.bin/clang/liblldbPluginSymbolFile/../../../llvm/llvm/include/llvm/ADT/DenseMap.h

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//===----------------------------------------------------------------------===//

13#ifndef LLVM_ADT_DENSEMAP_H
14#define LLVM_ADT_DENSEMAP_H

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>

34namespace llvm {

36namespace detail {

38// We extend a pair to allow users to override the bucket type with their own
39// implementation without requiring two members.
40template <typename KeyT, typename ValueT>
41struct DenseMapPair : public std::pair<KeyT, ValueT> {
using std::pair<KeyT, ValueT>::pair;

KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
48};

50} // end namespace detail

52template <typename KeyT, typename ValueT,
        typename KeyInfoT = DenseMapInfo<KeyT>,
        typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
        bool IsConst = false>
56class DenseMapIterator;

58template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
        typename BucketT>
60class DenseMapBase : public DebugEpochBase {
template <typename T>
using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;

64public:
using size_type = unsigned;
using key_type = KeyT;
using mapped_type = ValueT;
using value_type = BucketT;

using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>;
using const_iterator =
    DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>;

inline iterator begin() {
  // When the map is empty, avoid the overhead of advancing/retreating past
  // empty buckets.
  if (empty())
    return end();
  if (shouldReverseIterate<KeyT>())
    return makeIterator(getBucketsEnd() - 1, getBuckets(), *this);
  return makeIterator(getBuckets(), getBucketsEnd(), *this);
}
inline iterator end() {
  return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
}
inline const_iterator begin() const {
  if (empty())
    return end();
  if (shouldReverseIterate<KeyT>())
    return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this);
  return makeConstIterator(getBuckets(), getBucketsEnd(), *this);
}
inline const_iterator end() const {
  return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
}

LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const {
  return getNumEntries() == 0;
}
unsigned size() const { return getNumEntries(); }

/// Grow the densemap so that it can contain at least \p NumEntries items
/// before resizing again.
void reserve(size_type NumEntries) {
  auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
  incrementEpoch();
  if (NumBuckets > getNumBuckets())
    grow(NumBuckets);
}

void clear() {
  incrementEpoch();
  if (getNumEntries() == 0 && getNumTombstones() == 0) return;

  // If the capacity of the array is huge, and the # elements used is small,
  // shrink the array.
  if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
    shrink_and_clear();
    return;
  }

  const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
  if (std::is_trivially_destructible<ValueT>::value) {
    // Use a simpler loop when values don't need destruction.
    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
      P->getFirst() = EmptyKey;
  } else {
    unsigned NumEntries = getNumEntries();
    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
      if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
        if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
          P->getSecond().~ValueT();
          --NumEntries;
        }
        P->getFirst() = EmptyKey;
      }
    }
    assert(NumEntries == 0 && "Node count imbalance!")((void)0);
  }
  setNumEntries(0);
  setNumTombstones(0);
}

/// Return 1 if the specified key is in the map, 0 otherwise.
size_type count(const_arg_type_t<KeyT> Val) const {
  const BucketT *TheBucket;
  return LookupBucketFor(Val, TheBucket) ? 1 : 0;
}

iterator find(const_arg_type_t<KeyT> Val) {
  BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return makeIterator(TheBucket,
                        shouldReverseIterate<KeyT>() ? getBuckets()
                                                     : getBucketsEnd(),
                        *this, true);
  return end();
}
const_iterator find(const_arg_type_t<KeyT> Val) const {
  const BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return makeConstIterator(TheBucket,
                             shouldReverseIterate<KeyT>() ? getBuckets()
                                                          : getBucketsEnd(),
                             *this, true);
  return end();
}

/// Alternate version of find() which allows a different, and possibly
/// less expensive, key type.
/// The DenseMapInfo is responsible for supplying methods
/// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
/// type used.
template<class LookupKeyT>
iterator find_as(const LookupKeyT &Val) {
  BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return makeIterator(TheBucket,
                        shouldReverseIterate<KeyT>() ? getBuckets()
                                                     : getBucketsEnd(),
                        *this, true);
  return end();
}
template<class LookupKeyT>
const_iterator find_as(const LookupKeyT &Val) const {
  const BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return makeConstIterator(TheBucket,
                             shouldReverseIterate<KeyT>() ? getBuckets()
                                                          : getBucketsEnd(),
                             *this, true);
  return end();
}

/// lookup - Return the entry for the specified key, or a default
/// constructed value if no such entry exists.
ValueT lookup(const_arg_type_t<KeyT> Val) const {
  const BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return TheBucket->getSecond();
  return ValueT();
}

// Inserts key,value pair into the map if the key isn't already in the map.
// If the key is already in the map, it returns false and doesn't update the
// value.
std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
  return try_emplace(KV.first, KV.second);
}

// Inserts key,value pair into the map if the key isn't already in the map.
// If the key is already in the map, it returns false and doesn't update the
// value.
std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
  return try_emplace(std::move(KV.first), std::move(KV.second));
}

// Inserts key,value pair into the map if the key isn't already in the map.
// The value is constructed in-place if the key is not in the map, otherwise
// it is not moved.
template <typename... Ts>
std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
  BucketT *TheBucket;
  if (LookupBucketFor(Key, TheBucket))
    return std::make_pair(makeIterator(TheBucket,
                                       shouldReverseIterate<KeyT>()
                                           ? getBuckets()
                                           : getBucketsEnd(),
                                       *this, true),
                          false); // Already in map.

  // Otherwise, insert the new element.
  TheBucket =
      InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
  return std::make_pair(makeIterator(TheBucket,
                                     shouldReverseIterate<KeyT>()
                                         ? getBuckets()
                                         : getBucketsEnd(),
                                     *this, true),
                        true);
}

// Inserts key,value pair into the map if the key isn't already in the map.
// The value is constructed in-place if the key is not in the map, otherwise
// it is not moved.
template <typename... Ts>
std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) {
  BucketT *TheBucket;
  if (LookupBucketFor(Key, TheBucket))
    return std::make_pair(makeIterator(TheBucket,
                                       shouldReverseIterate<KeyT>()
                                           ? getBuckets()
                                           : getBucketsEnd(),
                                       *this, true),
                          false); // Already in map.

  // Otherwise, insert the new element.
  TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
  return std::make_pair(makeIterator(TheBucket,
                                     shouldReverseIterate<KeyT>()
                                         ? getBuckets()
                                         : getBucketsEnd(),
                                     *this, true),
                        true);
}

/// Alternate version of insert() which allows a different, and possibly
/// less expensive, key type.
/// The DenseMapInfo is responsible for supplying methods
/// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
/// type used.
template <typename LookupKeyT>
std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
                                    const LookupKeyT &Val) {
  BucketT *TheBucket;
  if (LookupBucketFor(Val, TheBucket))
    return std::make_pair(makeIterator(TheBucket,
                                       shouldReverseIterate<KeyT>()
                                           ? getBuckets()
                                           : getBucketsEnd(),
                                       *this, true),
                          false); // Already in map.

  // Otherwise, insert the new element.
  TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
                                         std::move(KV.second), Val);
  return std::make_pair(makeIterator(TheBucket,
                                     shouldReverseIterate<KeyT>()
                                         ? getBuckets()
                                         : getBucketsEnd(),
                                     *this, true),
                        true);
}

/// insert - Range insertion of pairs.
template<typename InputIt>
void insert(InputIt I, InputIt E) {
  for (; I != E; ++I)
    insert(*I);
}

bool erase(const KeyT &Val) {
  BucketT *TheBucket;
  if (!LookupBucketFor(Val, TheBucket))
    return false; // not in map.

  TheBucket->getSecond().~ValueT();
  TheBucket->getFirst() = getTombstoneKey();
  decrementNumEntries();
  incrementNumTombstones();
  return true;
}
void erase(iterator I) {
  BucketT *TheBucket = &*I;
  TheBucket->getSecond().~ValueT();
  TheBucket->getFirst() = getTombstoneKey();
  decrementNumEntries();
  incrementNumTombstones();
}

value_type& FindAndConstruct(const KeyT &Key) {
  BucketT *TheBucket;
  if (LookupBucketFor(Key, TheBucket))
    return *TheBucket;

  return *InsertIntoBucket(TheBucket, Key);
}

ValueT &operator[](const KeyT &Key) {
  return FindAndConstruct(Key).second;
}

value_type& FindAndConstruct(KeyT &&Key) {
  BucketT *TheBucket;
  if (LookupBucketFor(Key, TheBucket))
    return *TheBucket;

  return *InsertIntoBucket(TheBucket, std::move(Key));
}

ValueT &operator[](KeyT &&Key) {
  return FindAndConstruct(std::move(Key)).second;
}

/// isPointerIntoBucketsArray - Return true if the specified pointer points
/// somewhere into the DenseMap's array of buckets (i.e. either to a key or
/// value in the DenseMap).
bool isPointerIntoBucketsArray(const void *Ptr) const {
  return Ptr >= getBuckets() && Ptr < getBucketsEnd();
}

/// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
/// array.  In conjunction with the previous method, this can be used to
/// determine whether an insertion caused the DenseMap to reallocate.
const void *getPointerIntoBucketsArray() const { return getBuckets(); }

357protected:
DenseMapBase() = default;

void destroyAll() {
  if (getNumBuckets() == 0) // Nothing to do.
    return;

  const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
  for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
    if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
        !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
      P->getSecond().~ValueT();
    P->getFirst().~KeyT();
  }
}

void initEmpty() {
  setNumEntries(0);
  setNumTombstones(0);

  assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&((void)0)
         "# initial buckets must be a power of two!")((void)0);
  const KeyT EmptyKey = getEmptyKey();
  for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
    ::new (&B->getFirst()) KeyT(EmptyKey);
}

/// Returns the number of buckets to allocate to ensure that the DenseMap can
/// accommodate \p NumEntries without need to grow().
unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
  // Ensure that "NumEntries * 4 < NumBuckets * 3"
  if (NumEntries == 0)
    return 0;
  // +1 is required because of the strict equality.
  // For example if NumEntries is 48, we need to return 401.
  return NextPowerOf2(NumEntries * 4 / 3 + 1);
}

void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
  initEmpty();

  // Insert all the old elements.
  const KeyT EmptyKey = getEmptyKey();
  const KeyT TombstoneKey = getTombstoneKey();
  for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
    if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
        !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
      // Insert the key/value into the new table.
      BucketT *DestBucket;
      bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
      (void)FoundVal; // silence warning.
      assert(!FoundVal && "Key already in new map?")((void)0);
      DestBucket->getFirst() = std::move(B->getFirst());
      ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
      incrementNumEntries();

      // Free the value.
      B->getSecond().~ValueT();
    }
    B->getFirst().~KeyT();
  }
}

template <typename OtherBaseT>
void copyFrom(
    const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
  assert(&other != this)((void)0);
  assert(getNumBuckets() == other.getNumBuckets())((void)0);

  setNumEntries(other.getNumEntries());
  setNumTombstones(other.getNumTombstones());

  if (std::is_trivially_copyable<KeyT>::value &&
      std::is_trivially_copyable<ValueT>::value)
    memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(),
           getNumBuckets() * sizeof(BucketT));
  else
    for (size_t i = 0; i < getNumBuckets(); ++i) {
      ::new (&getBuckets()[i].getFirst())
          KeyT(other.getBuckets()[i].getFirst());
      if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
          !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
        ::new (&getBuckets()[i].getSecond())
            ValueT(other.getBuckets()[i].getSecond());
    }
}

static unsigned getHashValue(const KeyT &Val) {
  return KeyInfoT::getHashValue(Val);
}

template<typename LookupKeyT>
static unsigned getHashValue(const LookupKeyT &Val) {
  return KeyInfoT::getHashValue(Val);
}

static const KeyT getEmptyKey() {
  static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
                "Must pass the derived type to this template!");
  return KeyInfoT::getEmptyKey();
}

static const KeyT getTombstoneKey() {
  return KeyInfoT::getTombstoneKey();
}

463private:
iterator makeIterator(BucketT *P, BucketT *E,
                      DebugEpochBase &Epoch,
                      bool NoAdvance=false) {
  if (shouldReverseIterate<KeyT>()) {
    BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
    return iterator(B, E, Epoch, NoAdvance);
  }
  return iterator(P, E, Epoch, NoAdvance);
}

const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
                                 const DebugEpochBase &Epoch,
                                 const bool NoAdvance=false) const {
  if (shouldReverseIterate<KeyT>()) {
    const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
    return const_iterator(B, E, Epoch, NoAdvance);
  }
  return const_iterator(P, E, Epoch, NoAdvance);
}

unsigned getNumEntries() const {
  return static_cast<const DerivedT *>(this)->getNumEntries();
}

void setNumEntries(unsigned Num) {
  static_cast<DerivedT *>(this)->setNumEntries(Num);
}

void incrementNumEntries() {
  setNumEntries(getNumEntries() + 1);
}

void decrementNumEntries() {
  setNumEntries(getNumEntries() - 1);
}

unsigned getNumTombstones() const {
  return static_cast<const DerivedT *>(this)->getNumTombstones();
}

void setNumTombstones(unsigned Num) {
  static_cast<DerivedT *>(this)->setNumTombstones(Num);
}

void incrementNumTombstones() {
  setNumTombstones(getNumTombstones() + 1);
}

void decrementNumTombstones() {
  setNumTombstones(getNumTombstones() - 1);
}

const BucketT *getBuckets() const {
  return static_cast<const DerivedT *>(this)->getBuckets();
}

BucketT *getBuckets() {
  return static_cast<DerivedT *>(this)->getBuckets();
}

unsigned getNumBuckets() const {
  return static_cast<const DerivedT *>(this)->getNumBuckets();
}

BucketT *getBucketsEnd() {
  return getBuckets() + getNumBuckets();
}

const BucketT *getBucketsEnd() const {
  return getBuckets() + getNumBuckets();
}

void grow(unsigned AtLeast) {
  static_cast<DerivedT *>(this)->grow(AtLeast);
}

void shrink_and_clear() {
  static_cast<DerivedT *>(this)->shrink_and_clear();
}

template <typename KeyArg, typename... ValueArgs>
BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
                          ValueArgs &&... Values) {
  TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);

  TheBucket->getFirst() = std::forward<KeyArg>(Key);
  ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
  return TheBucket;
}

template <typename LookupKeyT>
BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
                                    ValueT &&Value, LookupKeyT &Lookup) {
  TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);

  TheBucket->getFirst() = std::move(Key);
  ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
  return TheBucket;
}

template <typename LookupKeyT>
BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
                              BucketT *TheBucket) {
  incrementEpoch();

  // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
  // the buckets are empty (meaning that many are filled with tombstones),
  // grow the table.
  //
  // The later case is tricky.  For example, if we had one empty bucket with
  // tons of tombstones, failing lookups (e.g. for insertion) would have to
  // probe almost the entire table until it found the empty bucket.  If the
  // table completely filled with tombstones, no lookup would ever succeed,
  // causing infinite loops in lookup.
  unsigned NewNumEntries = getNumEntries() + 1;
  unsigned NumBuckets = getNumBuckets();
  if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)__builtin_expect((bool)(NewNumEntries * 4 >= NumBuckets * 3
), false)) {
    this->grow(NumBuckets * 2);
    LookupBucketFor(Lookup, TheBucket);
    NumBuckets = getNumBuckets();
  } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones
()) <= NumBuckets/8), false)
                           NumBuckets/8)__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones
()) <= NumBuckets/8), false)) {
    this->grow(NumBuckets);
    LookupBucketFor(Lookup, TheBucket);
  }
  assert(TheBucket)((void)0);

  // Only update the state after we've grown our bucket space appropriately
  // so that when growing buckets we have self-consistent entry count.
  incrementNumEntries();

  // If we are writing over a tombstone, remember this.
  const KeyT EmptyKey = getEmptyKey();
  if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
    decrementNumTombstones();

  return TheBucket;
}

/// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
/// FoundBucket.  If the bucket contains the key and a value, this returns
/// true, otherwise it returns a bucket with an empty marker or tombstone and
/// returns false.
template<typename LookupKeyT>
bool LookupBucketFor(const LookupKeyT &Val,
                     const BucketT *&FoundBucket) const {
  const BucketT *BucketsPtr = getBuckets();
  const unsigned NumBuckets = getNumBuckets();

  if (NumBuckets == 0) {
    FoundBucket = nullptr;
    return false;
  }

  // FoundTombstone - Keep track of whether we find a tombstone while probing.
  const BucketT *FoundTombstone = nullptr;
  const KeyT EmptyKey = getEmptyKey();
  const KeyT TombstoneKey = getTombstoneKey();
  assert(!KeyInfoT::isEqual(Val, EmptyKey) &&((void)0)
         !KeyInfoT::isEqual(Val, TombstoneKey) &&((void)0)
         "Empty/Tombstone value shouldn't be inserted into map!")((void)0);

  unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
  unsigned ProbeAmt = 1;
  while (true) {
    const BucketT *ThisBucket = BucketsPtr + BucketNo;
    // Found Val's bucket?  If so, return it.
    if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))__builtin_expect((bool)(KeyInfoT::isEqual(Val, ThisBucket->
getFirst())), true)) {
      FoundBucket = ThisBucket;
      return true;
    }

    // If we found an empty bucket, the key doesn't exist in the set.
    // Insert it and return the default value.
    if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))__builtin_expect((bool)(KeyInfoT::isEqual(ThisBucket->getFirst
(), EmptyKey)), true)) {
      // If we've already seen a tombstone while probing, fill it in instead
      // of the empty bucket we eventually probed to.
      FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
      return false;
    }

    // If this is a tombstone, remember it.  If Val ends up not in the map, we
    // prefer to return it than something that would require more probing.
    if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
        !FoundTombstone)
      FoundTombstone = ThisBucket;  // Remember the first tombstone found.

    // Otherwise, it's a hash collision or a tombstone, continue quadratic
    // probing.
    BucketNo += ProbeAmt++;
    BucketNo &= (NumBuckets-1);
  }
}

template <typename LookupKeyT>
bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
  const BucketT *ConstFoundBucket;
  bool Result = const_cast<const DenseMapBase *>(this)
    ->LookupBucketFor(Val, ConstFoundBucket);
  FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
  return Result;
}

667public:
/// Return the approximate size (in bytes) of the actual map.
/// This is just the raw memory used by DenseMap.
/// If entries are pointers to objects, the size of the referenced objects
/// are not included.
size_t getMemorySize() const {
  return getNumBuckets() * sizeof(BucketT);
}
675};

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).
683template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
        typename BucketT>
685bool operator==(
  const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
  const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
if (LHS.size() != RHS.size())
  return false;

for (auto &KV : LHS) {
  auto I = RHS.find(KV.first);
  if (I == RHS.end() || I->second != KV.second)
    return false;
}

return true;
698}

700/// Inequality comparison for DenseMap.
701///
702/// Equivalent to !(LHS == RHS). See operator== for performance notes.
703template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
        typename BucketT>
705bool operator!=(
  const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
  const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
return !(LHS == RHS);
709}

711template <typename KeyT, typename ValueT,
        typename KeyInfoT = DenseMapInfo<KeyT>,
        typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
714class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
                                   KeyT, ValueT, KeyInfoT, BucketT> {
friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

// Lift some types from the dependent base class into this class for
// simplicity of referring to them.
using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

BucketT *Buckets;
unsigned NumEntries;
unsigned NumTombstones;
unsigned NumBuckets;

727public:
/// Create a DenseMap with an optional \p InitialReserve that guarantee that
/// this number of elements can be inserted in the map without grow()
explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }

DenseMap(const DenseMap &other) : BaseT() {
  init(0);
  copyFrom(other);
}

DenseMap(DenseMap &&other) : BaseT() {
  init(0);
  swap(other);
}

template<typename InputIt>
DenseMap(const InputIt &I, const InputIt &E) {
  init(std::distance(I, E));
  this->insert(I, E);
}

DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
  init(Vals.size());
  this->insert(Vals.begin(), Vals.end());
}

~DenseMap() {
  this->destroyAll();
  deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
}

void swap(DenseMap& RHS) {
  this->incrementEpoch();
  RHS.incrementEpoch();
  std::swap(Buckets, RHS.Buckets);
  std::swap(NumEntries, RHS.NumEntries);
  std::swap(NumTombstones, RHS.NumTombstones);
  std::swap(NumBuckets, RHS.NumBuckets);
}

DenseMap& operator=(const DenseMap& other) {
  if (&other != this)
    copyFrom(other);
  return *this;
}

DenseMap& operator=(DenseMap &&other) {
  this->destroyAll();
  deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
  init(0);
  swap(other);
  return *this;
}

void copyFrom(const DenseMap& other) {
  this->destroyAll();
  deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT));
  if (allocateBuckets(other.NumBuckets)) {
    this->BaseT::copyFrom(other);
  } else {
    NumEntries = 0;
    NumTombstones = 0;
  }
}

void init(unsigned InitNumEntries) {
  auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
  if (allocateBuckets(InitBuckets)) {
    this->BaseT::initEmpty();
  } else {
    NumEntries = 0;
    NumTombstones = 0;
  }
}

void grow(unsigned AtLeast) {
  unsigned OldNumBuckets = NumBuckets;
  BucketT *OldBuckets = Buckets;

  allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1))));
  assert(Buckets)((void)0);
  if (!OldBuckets) {
    this->BaseT::initEmpty();
    return;
  }

  this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);

  // Free the old table.
  deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets,
                    alignof(BucketT));
}

void shrink_and_clear() {
  unsigned OldNumBuckets = NumBuckets;
  unsigned OldNumEntries = NumEntries;
  this->destroyAll();

  // Reduce the number of buckets.
  unsigned NewNumBuckets = 0;
  if (OldNumEntries)
    NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
  if (NewNumBuckets == NumBuckets) {
    this->BaseT::initEmpty();
    return;
  }

  deallocate_buffer(Buckets, sizeof(BucketT) * OldNumBuckets,
                    alignof(BucketT));
  init(NewNumBuckets);
}

839private:
unsigned getNumEntries() const {
  return NumEntries;
}

void setNumEntries(unsigned Num) {
  NumEntries = Num;
}

unsigned getNumTombstones() const {
  return NumTombstones;
}

void setNumTombstones(unsigned Num) {
  NumTombstones = Num;
}

BucketT *getBuckets() const {
  return Buckets;
}

unsigned getNumBuckets() const {
  return NumBuckets;
}

bool allocateBuckets(unsigned Num) {
  NumBuckets = Num;
  if (NumBuckets == 0) {
    Buckets = nullptr;
    return false;
  }

  Buckets = static_cast<BucketT *>(
      allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT)));
  return true;
}
875};

877template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
        typename KeyInfoT = DenseMapInfo<KeyT>,
        typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
880class SmallDenseMap
  : public DenseMapBase<
        SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
        ValueT, KeyInfoT, BucketT> {
friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

// Lift some types from the dependent base class into this class for
// simplicity of referring to them.
using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;

static_assert(isPowerOf2_64(InlineBuckets),
              "InlineBuckets must be a power of 2.");

unsigned Small : 1;
unsigned NumEntries : 31;
unsigned NumTombstones;

struct LargeRep {
  BucketT *Buckets;
  unsigned NumBuckets;
};

/// A "union" of an inline bucket array and the struct representing
/// a large bucket. This union will be discriminated by the 'Small' bit.
AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;

906public:
explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
  init(NumInitBuckets);
}

SmallDenseMap(const SmallDenseMap &other) : BaseT() {
  init(0);
  copyFrom(other);
}

SmallDenseMap(SmallDenseMap &&other) : BaseT() {
  init(0);
  swap(other);
}

template<typename InputIt>
SmallDenseMap(const InputIt &I, const InputIt &E) {
  init(NextPowerOf2(std::distance(I, E)));
  this->insert(I, E);
}

SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals)
    : SmallDenseMap(Vals.begin(), Vals.end()) {}

~SmallDenseMap() {
  this->destroyAll();
  deallocateBuckets();
}

void swap(SmallDenseMap& RHS) {
  unsigned TmpNumEntries = RHS.NumEntries;
  RHS.NumEntries = NumEntries;
  NumEntries = TmpNumEntries;
  std::swap(NumTombstones, RHS.NumTombstones);

  const KeyT EmptyKey = this->getEmptyKey();
  const KeyT TombstoneKey = this->getTombstoneKey();
  if (Small && RHS.Small) {
    // If we're swapping inline bucket arrays, we have to cope with some of
    // the tricky bits of DenseMap's storage system: the buckets are not
    // fully initialized. Thus we swap every key, but we may have
    // a one-directional move of the value.
    for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
      BucketT *LHSB = &getInlineBuckets()[i],
              *RHSB = &RHS.getInlineBuckets()[i];
      bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
                          !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
      bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
                          !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
      if (hasLHSValue && hasRHSValue) {
        // Swap together if we can...
        std::swap(*LHSB, *RHSB);
        continue;
      }
      // Swap separately and handle any asymmetry.
      std::swap(LHSB->getFirst(), RHSB->getFirst());
      if (hasLHSValue) {
        ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
        LHSB->getSecond().~ValueT();
      } else if (hasRHSValue) {
        ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
        RHSB->getSecond().~ValueT();
      }
    }
    return;
  }
  if (!Small && !RHS.Small) {
    std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets);
    std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets);
    return;
  }

  SmallDenseMap &SmallSide = Small ? *this : RHS;
  SmallDenseMap &LargeSide = Small ? RHS : *this;

  // First stash the large side's rep and move the small side across.
  LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
  LargeSide.getLargeRep()->~LargeRep();
  LargeSide.Small = true;
  // This is similar to the standard move-from-old-buckets, but the bucket
  // count hasn't actually rotated in this case. So we have to carefully
  // move construct the keys and values into their new locations, but there
  // is no need to re-hash things.
  for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
    BucketT *NewB = &LargeSide.getInlineBuckets()[i],
            *OldB = &SmallSide.getInlineBuckets()[i];
    ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
    OldB->getFirst().~KeyT();
    if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
        !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
      ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
      OldB->getSecond().~ValueT();
    }
  }

  // The hard part of moving the small buckets across is done, just move
  // the TmpRep into its new home.
  SmallSide.Small = false;
  new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
}

SmallDenseMap& operator=(const SmallDenseMap& other) {
  if (&other != this)
    copyFrom(other);
  return *this;
}

SmallDenseMap& operator=(SmallDenseMap &&other) {
  this->destroyAll();
  deallocateBuckets();
  init(0);
  swap(other);
  return *this;
}

void copyFrom(const SmallDenseMap& other) {
  this->destroyAll();
  deallocateBuckets();
  Small = true;
  if (other.getNumBuckets() > InlineBuckets) {
    Small = false;
    new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
  }
  this->BaseT::copyFrom(other);
}

void init(unsigned InitBuckets) {
  Small = true;
  if (InitBuckets > InlineBuckets) {
    Small = false;
    new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
  }
  this->BaseT::initEmpty();
}

void grow(unsigned AtLeast) {
  if (AtLeast > InlineBuckets)
    AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1));

  if (Small) {
    // First move the inline buckets into a temporary storage.
    AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;
    BucketT *TmpBegin = reinterpret_cast<BucketT *>(&TmpStorage);
    BucketT *TmpEnd = TmpBegin;

    // Loop over the buckets, moving non-empty, non-tombstones into the
    // temporary storage. Have the loop move the TmpEnd forward as it goes.
    const KeyT EmptyKey = this->getEmptyKey();
    const KeyT TombstoneKey = this->getTombstoneKey();
    for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
      if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
          !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
        assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&((void)0)
               "Too many inline buckets!")((void)0);
        ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
        ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
        ++TmpEnd;
        P->getSecond().~ValueT();
      }
      P->getFirst().~KeyT();
    }

    // AtLeast == InlineBuckets can happen if there are many tombstones,
    // and grow() is used to remove them. Usually we always switch to the
    // large rep here.
    if (AtLeast > InlineBuckets) {
      Small = false;
      new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
    }
    this->moveFromOldBuckets(TmpBegin, TmpEnd);
    return;
  }

  LargeRep OldRep = std::move(*getLargeRep());
  getLargeRep()->~LargeRep();
  if (AtLeast <= InlineBuckets) {
    Small = true;
  } else {
    new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
  }

  this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);

  // Free the old table.
  deallocate_buffer(OldRep.Buckets, sizeof(BucketT) * OldRep.NumBuckets,
                    alignof(BucketT));
}

void shrink_and_clear() {
  unsigned OldSize = this->size();
  this->destroyAll();

  // Reduce the number of buckets.
  unsigned NewNumBuckets = 0;
  if (OldSize) {
    NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1);
    if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
      NewNumBuckets = 64;
  }
  if ((Small && NewNumBuckets <= InlineBuckets) ||
      (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
    this->BaseT::initEmpty();
    return;
  }

  deallocateBuckets();
  init(NewNumBuckets);
}

1115private:
unsigned getNumEntries() const {
  return NumEntries;
}

void setNumEntries(unsigned Num) {
  // NumEntries is hardcoded to be 31 bits wide.
  assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries")((void)0);
  NumEntries = Num;
}

unsigned getNumTombstones() const {
  return NumTombstones;
}

void setNumTombstones(unsigned Num) {
  NumTombstones = Num;
}

const BucketT *getInlineBuckets() const {
  assert(Small)((void)0);
  // Note that this cast does not violate aliasing rules as we assert that
  // the memory's dynamic type is the small, inline bucket buffer, and the
  // 'storage' is a POD containing a char buffer.
  return reinterpret_cast<const BucketT *>(&storage);
}

BucketT *getInlineBuckets() {
  return const_cast<BucketT *>(
    const_cast<const SmallDenseMap *>(this)->getInlineBuckets());
}

const LargeRep *getLargeRep() const {
  assert(!Small)((void)0);
  // Note, same rule about aliasing as with getInlineBuckets.
  return reinterpret_cast<const LargeRep *>(&storage);
}

LargeRep *getLargeRep() {
  return const_cast<LargeRep *>(
    const_cast<const SmallDenseMap *>(this)->getLargeRep());
}

const BucketT *getBuckets() const {
  return Small ? getInlineBuckets() : getLargeRep()->Buckets;
}

BucketT *getBuckets() {
  return const_cast<BucketT *>(
    const_cast<const SmallDenseMap *>(this)->getBuckets());
}

unsigned getNumBuckets() const {
  return Small ? InlineBuckets : getLargeRep()->NumBuckets;
}

void deallocateBuckets() {
  if (Small)
    return;

  deallocate_buffer(getLargeRep()->Buckets,
                    sizeof(BucketT) * getLargeRep()->NumBuckets,
                    alignof(BucketT));
  getLargeRep()->~LargeRep();
}

LargeRep allocateBuckets(unsigned Num) {
  assert(Num > InlineBuckets && "Must allocate more buckets than are inline")((void)0);
  LargeRep Rep = {static_cast<BucketT *>(allocate_buffer(
                      sizeof(BucketT) * Num, alignof(BucketT))),
                  Num};
  return Rep;
}
1188};

1190template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
        bool IsConst>
1192class DenseMapIterator : DebugEpochBase::HandleBase {
friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;

1196public:
using difference_type = ptrdiff_t;
using value_type =
    typename std::conditional<IsConst, const Bucket, Bucket>::type;
using pointer = value_type *;
using reference = value_type &;
using iterator_category = std::forward_iterator_tag;

1204private:
pointer Ptr = nullptr;
pointer End = nullptr;

1208public:
DenseMapIterator() = default;

DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
                 bool NoAdvance = false)
    : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
  assert(isHandleInSync() && "invalid construction!")((void)0);

  if (NoAdvance) return;
  if (shouldReverseIterate<KeyT>()) {
    RetreatPastEmptyBuckets();
    return;
  }
  AdvancePastEmptyBuckets();
}

// Converting ctor from non-const iterators to const iterators. SFINAE'd out
// for const iterator destinations so it doesn't end up as a user defined copy
// constructor.
template <bool IsConstSrc,
          typename = std::enable_if_t<!IsConstSrc && IsConst>>
DenseMapIterator(
    const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
    : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}

reference operator*() const {
  assert(isHandleInSync() && "invalid iterator access!")((void)0);
  assert(Ptr != End && "dereferencing end() iterator")((void)0);
  if (shouldReverseIterate<KeyT>())
    return Ptr[-1];
  return *Ptr;
}
pointer operator->() const {
  assert(isHandleInSync() && "invalid iterator access!")((void)0);
  assert(Ptr != End && "dereferencing end() iterator")((void)0);
  if (shouldReverseIterate<KeyT>())
    return &(Ptr[-1]);
  return Ptr;
}

friend bool operator==(const DenseMapIterator &LHS,
                       const DenseMapIterator &RHS) {
  assert((!LHS.Ptr || LHS.isHandleInSync()) && "handle not in sync!")((void)0);
  assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!")((void)0);
  assert(LHS.getEpochAddress() == RHS.getEpochAddress() &&((void)0)
         "comparing incomparable iterators!")((void)0);
  return LHS.Ptr == RHS.Ptr;
33
←
Assuming 'LHS.Ptr' is equal to 'RHS.Ptr'→
34
←
Returning the value 1, which participates in a condition later→
}

friend bool operator!=(const DenseMapIterator &LHS,
                       const DenseMapIterator &RHS) {
  return !(LHS == RHS);
32
←
Calling 'operator=='→
35
←
Returning from 'operator=='→
36
←
Returning zero, which participates in a condition later→
}

inline DenseMapIterator& operator++() {  // Preincrement
  assert(isHandleInSync() && "invalid iterator access!")((void)0);
  assert(Ptr != End && "incrementing end() iterator")((void)0);
  if (shouldReverseIterate<KeyT>()) {
    --Ptr;
    RetreatPastEmptyBuckets();
    return *this;
  }
  ++Ptr;
  AdvancePastEmptyBuckets();
  return *this;
}
DenseMapIterator operator++(int) {  // Postincrement
  assert(isHandleInSync() && "invalid iterator access!")((void)0);
  DenseMapIterator tmp = *this; ++*this; return tmp;
}

1279private:
void AdvancePastEmptyBuckets() {
  assert(Ptr <= End)((void)0);
  const KeyT Empty = KeyInfoT::getEmptyKey();
  const KeyT Tombstone = KeyInfoT::getTombstoneKey();

  while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
                        KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
    ++Ptr;
}

void RetreatPastEmptyBuckets() {
  assert(Ptr >= End)((void)0);
  const KeyT Empty = KeyInfoT::getEmptyKey();
  const KeyT Tombstone = KeyInfoT::getTombstoneKey();

  while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
                        KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
    --Ptr;
}
1299};

1301template <typename KeyT, typename ValueT, typename KeyInfoT>
1302inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
return X.getMemorySize();
1304}

1306} // end namespace llvm

1308#endif // LLVM_ADT_DENSEMAP_H