DebugNamesDWARFIndex: Implement GetFunctions method

[labath]

Summary

This patch implements the non-regex variant of GetFunctions. To share
more code with the Apple implementation, I've extracted the common
filtering code from that class into a utility function on the DWARFIndex
base class.

The new implementation also searching the accelerator table multiple
times -- previously it could happen that the apple table would return
the same die more than once if one specified multiple search flags in
name_type_mask. This way, I separate table iteration from filtering, and
so we can be sure each die is inserted at most once.

lldb/trunk/lit/SymbolFile/DWARF/find-basic-function.cpp

 // RUN:   FileCheck --check-prefix=FULL %s
 // RUN: lldb-test symbols --name=_Z3fooi --find=function --function-flags=full %t | \
 // RUN:   FileCheck --check-prefix=FULL-MANGLED %s
 // RUN: lldb-test symbols --name=foo --context=context --find=function --function-flags=base %t | \
 // RUN:   FileCheck --check-prefix=CONTEXT %s
 // RUN: lldb-test symbols --name=not_there --find=function %t | \
 // RUN:   FileCheck --check-prefix=EMPTY %s
 
+// RUN: clang %s -g -c -emit-llvm -o - --target=x86_64-pc-linux | \
+// RUN:   llc -accel-tables=Dwarf -filetype=obj -o %t.o
+// RUN: ld.lld %t.o -o %t
+// RUN: lldb-test symbols --name=foo --find=function --function-flags=base %t | \
+// RUN:   FileCheck --check-prefix=BASE %s
+// RUN: lldb-test symbols --name=foo --find=function --function-flags=method %t | \
+// RUN:   FileCheck --check-prefix=METHOD %s
+// RUN: lldb-test symbols --name=foo --find=function --function-flags=full %t | \
+// RUN:   FileCheck --check-prefix=FULL %s
+// RUN: lldb-test symbols --name=_Z3fooi --find=function --function-flags=full %t | \
+// RUN:   FileCheck --check-prefix=FULL-MANGLED %s
+// RUN: lldb-test symbols --name=foo --context=context --find=function --function-flags=base %t | \
+// RUN:   FileCheck --check-prefix=CONTEXT %s
+// RUN: lldb-test symbols --name=not_there --find=function %t | \
+// RUN:   FileCheck --check-prefix=EMPTY %s
+
 // BASE: Found 4 functions:
 // BASE-DAG: name = "foo()", mangled = "_Z3foov"
 // BASE-DAG: name = "foo(int)", mangled = "_Z3fooi"
 // BASE-DAG: name = "bar::foo()", mangled = "_ZN3bar3fooEv"
 // BASE-DAG: name = "bar::baz::foo()", mangled = "_ZN3bar3baz3fooEv"
 
 // METHOD: Found 3 functions:
 // METHOD-DAG: name = "sbar::foo()", mangled = "_ZN4sbar3fooEv"

lldb/trunk/source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp

 //===-- AppleDWARFIndex.cpp ------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Plugins/SymbolFile/DWARF/AppleDWARFIndex.h"
 #include "Plugins/SymbolFile/DWARF/DWARFDebugInfo.h"
 #include "Plugins/SymbolFile/DWARF/DWARFDeclContext.h"
 #include "Plugins/SymbolFile/DWARF/DWARFUnit.h"
 #include "Plugins/SymbolFile/DWARF/LogChannelDWARF.h"
 
-#include "Plugins/Language/ObjC/ObjCLanguage.h"
 #include "lldb/Core/Module.h"
 #include "lldb/Symbol/Function.h"
 
 using namespace lldb_private;
 using namespace lldb;
 
 std::unique_ptr<AppleDWARFIndex> AppleDWARFIndex::Create(
     Module &module, DWARFDataExtractor apple_names,
if (has_tag && has_qualified_name_hash) {
     m_apple_types_up->FindByName(type_name.GetStringRef(), offsets);
 }
 
 void AppleDWARFIndex::GetNamespaces(ConstString name, DIEArray &offsets) {
   if (m_apple_namespaces_up)
     m_apple_namespaces_up->FindByName(name.GetStringRef(), offsets);
 }
 
-static bool KeepFunctionDIE(DWARFDIE die, uint32_t name_type_mask) {
-  bool looking_for_methods = name_type_mask & eFunctionNameTypeMethod;
-  bool looking_for_functions = name_type_mask & eFunctionNameTypeBase;
-  if (looking_for_methods && looking_for_functions)
-    return true;
-  return looking_for_methods == die.IsMethod();
-}
-
 void AppleDWARFIndex::GetFunctions(ConstString name, DWARFDebugInfo &info,
                                    const CompilerDeclContext &parent_decl_ctx,
                                    uint32_t name_type_mask,
                                    std::vector<DWARFDIE> &dies) {
-  if (name_type_mask & eFunctionNameTypeFull) {
-    // If they asked for the full name, match what they typed.  At some
-    // point we may want to canonicalize this (strip double spaces, etc.
-    // For now, we just add all the dies that we find by exact match.
-    DIEArray offsets;
-    m_apple_names_up->FindByName(name.GetStringRef(), offsets);
-    for (const DIERef &die_ref: offsets) {
-      DWARFDIE die = info.GetDIE(die_ref);
-      if (!die) {
-        ReportInvalidDIEOffset(die_ref.die_offset, name.GetStringRef());
-        continue;
-      }
-      if (SymbolFileDWARF::DIEInDeclContext(&parent_decl_ctx, die))
-        dies.push_back(die);
-    }
-  }
-  if (name_type_mask & eFunctionNameTypeSelector &&
-      !parent_decl_ctx.IsValid()) {
-    DIEArray offsets;
-    m_apple_names_up->FindByName(name.GetStringRef(), offsets);
-
-    // Now make sure these are actually ObjC methods.  In this case we can
-    // simply look up the name, and if it is an ObjC method name, we're
-    // good.
-    for (const DIERef &die_ref: offsets) {
-      DWARFDIE die = info.GetDIE(die_ref);
-      if (!die) {
-        ReportInvalidDIEOffset(die_ref.die_offset, name.GetStringRef());
-        continue;
-      }
-      const char *die_name = die.GetName();
-      if (ObjCLanguage::IsPossibleObjCMethodName(die_name))
-        dies.push_back(die);
-    }
-  }
-  if (((name_type_mask & eFunctionNameTypeMethod) &&
-       !parent_decl_ctx.IsValid()) ||
-      name_type_mask & eFunctionNameTypeBase) {
-    // The apple_names table stores just the "base name" of C++ methods in
-    // the table.  So we have to extract the base name, look that up, and
-    // if there is any other information in the name we were passed in we
-    // have to post-filter based on that.
-
-    DIEArray offsets;
-    m_apple_names_up->FindByName(name.GetStringRef(), offsets);
-
-    for (const DIERef &die_ref: offsets) {
-      DWARFDIE die = info.GetDIE(die_ref);
-      if (!die) {
-        ReportInvalidDIEOffset(die_ref.die_offset, name.GetStringRef());
-        continue;
-      }
-      if (SymbolFileDWARF::DIEInDeclContext(&parent_decl_ctx, die) &&
-          KeepFunctionDIE(die, name_type_mask))
-        dies.push_back(die);
-    }
+  for (const DIERef &die_ref : offsets) {
+    ProcessFunctionDIE(name.GetStringRef(), die_ref, info, parent_decl_ctx,
+                       name_type_mask, dies);
   }
 }
 
 void AppleDWARFIndex::GetFunctions(const RegularExpression &regex,
                                    DIEArray &offsets) {
   if (!m_apple_names_up)
     return;
 

lldb/trunk/source/Plugins/SymbolFile/DWARF/DIERef.h

struct DIERef {
   lldb::user_id_t GetUID(SymbolFileDWARF *dwarf) const;
 
   bool operator<(const DIERef &ref) const {
     return die_offset < ref.die_offset;
   }
 
   bool operator<(const DIERef &ref) { return die_offset < ref.die_offset; }
 
+  explicit operator bool() const {
+    return cu_offset != DW_INVALID_OFFSET || die_offset != DW_INVALID_OFFSET;
+  }
+
   dw_offset_t cu_offset = DW_INVALID_OFFSET;
   dw_offset_t die_offset = DW_INVALID_OFFSET;
 };
 
 typedef std::vector<DIERef> DIEArray;
 
 #endif // SymbolFileDWARF_DIERef_h_

lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFIndex.h

 //===-- DWARFIndex.h -------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_DWARFINDEX_H
 #define LLDB_DWARFINDEX_H
 
 #include "Plugins/SymbolFile/DWARF/DIERef.h"
+#include "Plugins/SymbolFile/DWARF/DWARFDIE.h"
 #include "Plugins/SymbolFile/DWARF/DWARFFormValue.h"
 
 class DWARFDebugInfo;
 class DWARFDeclContext;
 class DWARFDIE;
 
 namespace lldb_private {
 class DWARFIndex {
virtual void GetFunctions(const RegularExpression &regex,
                             DIEArray &offsets) = 0;
 
   virtual void ReportInvalidDIEOffset(dw_offset_t offset,
                                       llvm::StringRef name) = 0;
   virtual void Dump(Stream &s) = 0;
 
 protected:
   Module &m_module;
+
+  /// Helper function implementing common logic for processing function dies. If
+  /// the function given by "ref" matches search criteria given by
+  /// "parent_decl_ctx" and "name_type_mask", it is inserted into the "dies"
+  /// vector.
+  void ProcessFunctionDIE(llvm::StringRef name, DIERef ref,
+                          DWARFDebugInfo &info,
+                          const CompilerDeclContext &parent_decl_ctx,
+                          uint32_t name_type_mask, std::vector<DWARFDIE> &dies);
 };
 } // namespace lldb_private
 
 #endif // LLDB_DWARFINDEX_H

lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFIndex.cpp

 //===-- DWARFIndex.cpp -----------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Plugins/SymbolFile/DWARF/DWARFIndex.h"
 #include "Plugins/SymbolFile/DWARF/DWARFDIE.h"
 #include "Plugins/SymbolFile/DWARF/DWARFDebugInfo.h"
 
+#include "Plugins/Language/ObjC/ObjCLanguage.h"
+
 using namespace lldb_private;
 using namespace lldb;
 
 DWARFIndex::~DWARFIndex() = default;
+
+void DWARFIndex::ProcessFunctionDIE(llvm::StringRef name, DIERef ref,
+                                    DWARFDebugInfo &info,
+                                    const CompilerDeclContext &parent_decl_ctx,
+                                    uint32_t name_type_mask,
+                                    std::vector<DWARFDIE> &dies) {
+  DWARFDIE die = info.GetDIE(ref);
+  if (!die) {
+    ReportInvalidDIEOffset(ref.die_offset, name);
+    return;
+  }
+
+  // Exit early if we're searching exclusively for methods or selectors and
+  // we have a context specified (no methods in namespaces).
+  uint32_t looking_for_nonmethods =
+      name_type_mask & ~(eFunctionNameTypeMethod | eFunctionNameTypeSelector);
+  if (!looking_for_nonmethods && parent_decl_ctx.IsValid())
+    return;
+
+  // Otherwise, we need to also check that the context matches. If it does not
+  // match, we do nothing.
+  if (!SymbolFileDWARF::DIEInDeclContext(&parent_decl_ctx, die))
+    return;
+
+  // In case of a full match, we just insert everything we find.
+  if (name_type_mask & eFunctionNameTypeFull) {
+    dies.push_back(die);
+    return;
+  }
+
+  // If looking for ObjC selectors, we need to also check if the name is a
+  // possible selector.
+  if (name_type_mask & eFunctionNameTypeSelector &&
+      ObjCLanguage::IsPossibleObjCMethodName(die.GetName())) {
+    dies.push_back(die);
+    return;
+  }
+
+  bool looking_for_methods = name_type_mask & lldb::eFunctionNameTypeMethod;
+  bool looking_for_functions = name_type_mask & lldb::eFunctionNameTypeBase;
+  if (looking_for_methods || looking_for_functions) {
+    // If we're looking for either methods or functions, we definitely want this
+    // die. Otherwise, only keep it if the die type matches what we are
+    // searching for.
+    if ((looking_for_methods && looking_for_functions) ||
+        looking_for_methods == die.IsMethod())
+      dies.push_back(die);
+  }
+}

lldb/trunk/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h

public:
   void GetCompleteObjCClass(ConstString class_name, bool must_be_implementation,
                             DIEArray &offsets) override {}
   void GetTypes(ConstString name, DIEArray &offsets) override;
   void GetTypes(const DWARFDeclContext &context, DIEArray &offsets) override {}
   void GetNamespaces(ConstString name, DIEArray &offsets) override;
   void GetFunctions(ConstString name, DWARFDebugInfo &info,
                     const CompilerDeclContext &parent_decl_ctx,
                     uint32_t name_type_mask,
-                    std::vector<DWARFDIE> &dies) override {}
+                    std::vector<DWARFDIE> &dies) override;
   void GetFunctions(const RegularExpression &regex,
                     DIEArray &offsets) override {}
 
   void ReportInvalidDIEOffset(dw_offset_t offset,
                               llvm::StringRef name) override {}
   void Dump(Stream &s) override;
 
 private:
private:
   // track of the ownership here.
   DWARFDataExtractor m_debug_names_data;
   DWARFDataExtractor m_debug_str_data;
 
   using DebugNames = llvm::DWARFDebugNames;
   std::unique_ptr<DebugNames> m_debug_names_up;
   ManualDWARFIndex m_fallback;
 
-  void Append(const DebugNames::Entry &entry, DIEArray &offsets);
-  void MaybeLogLookupError(llvm::Error error, const DebugNames::NameIndex &ni,
+  static DIERef ToDIERef(const DebugNames::Entry &entry);
+  static void Append(const DebugNames::Entry &entry, DIEArray &offsets);
+  static void MaybeLogLookupError(llvm::Error error,
+                                  const DebugNames::NameIndex &ni,
                                   llvm::StringRef name);
 
   static llvm::DenseSet<dw_offset_t> GetUnits(const DebugNames &debug_names);
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_DEBUGNAMESDWARFINDEX_H

lldb/trunk/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp

 //===-- DebugNamesDWARFIndex.cpp -------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h"
+#include "Plugins/SymbolFile/DWARF/DWARFDebugInfo.h"
 #include "lldb/Utility/RegularExpression.h"
 #include "lldb/Utility/Stream.h"
 
 using namespace lldb_private;
 using namespace lldb;
 
 static llvm::DWARFDataExtractor ToLLVM(const DWARFDataExtractor &data) {
   return llvm::DWARFDataExtractor(
DebugNamesDWARFIndex::GetUnits(const DebugNames &debug_names) {
   llvm::DenseSet<dw_offset_t> result;
   for (const DebugNames::NameIndex &ni : debug_names) {
     for (uint32_t cu = 0; cu < ni.getCUCount(); ++cu)
       result.insert(ni.getCUOffset(cu));
   }
   return result;
 }
 
-void DebugNamesDWARFIndex::Append(const DebugNames::Entry &entry,
-                                  DIEArray &offsets) {
+DIERef DebugNamesDWARFIndex::ToDIERef(const DebugNames::Entry &entry) {
   llvm::Optional<uint64_t> cu_offset = entry.getCUOffset();
   llvm::Optional<uint64_t> die_offset = entry.getDIESectionOffset();
   if (cu_offset && die_offset)
-    offsets.emplace_back(*cu_offset, *die_offset);
+    return DIERef(*cu_offset, *die_offset);
+  return DIERef();
+}
+
+void DebugNamesDWARFIndex::Append(const DebugNames::Entry &entry,
+                                  DIEArray &offsets) {
+  if (DIERef ref = ToDIERef(entry))
+    offsets.push_back(ref);
 }
 
 void DebugNamesDWARFIndex::MaybeLogLookupError(llvm::Error error,
                                                const DebugNames::NameIndex &ni,
                                                llvm::StringRef name) {
   // Ignore SentinelErrors, log everything else.
   LLDB_LOG_ERROR(
       LogChannelDWARF::GetLogIfAll(DWARF_LOG_LOOKUPS),
void DebugNamesDWARFIndex::GetNamespaces(ConstString name, DIEArray &offsets) {
 
   for (const DebugNames::Entry &entry :
        m_debug_names_up->equal_range(name.GetStringRef())) {
     if (entry.tag() == DW_TAG_namespace)
       Append(entry, offsets);
   }
 }
 
+void DebugNamesDWARFIndex::GetFunctions(
+    ConstString name, DWARFDebugInfo &info,
+    const CompilerDeclContext &parent_decl_ctx, uint32_t name_type_mask,
+    std::vector<DWARFDIE> &dies) {
+
+  m_fallback.GetFunctions(name, info, parent_decl_ctx, name_type_mask, dies);
+
+  for (const DebugNames::Entry &entry :
+       m_debug_names_up->equal_range(name.GetStringRef())) {
+    Tag tag = entry.tag();
+    if (tag != DW_TAG_subprogram && tag != DW_TAG_inlined_subroutine)
+      continue;
+
+    if (DIERef ref = ToDIERef(entry))
+      ProcessFunctionDIE(name.GetStringRef(), ref, info, parent_decl_ctx,
+                         name_type_mask, dies);
+  }
+}
+
 void DebugNamesDWARFIndex::Dump(Stream &s) {
   m_fallback.Dump(s);
 
   std::string data;
   llvm::raw_string_ostream os(data);
   m_debug_names_up->dump(os);
   s.PutCString(os.str());
 }