AppleDWARFIndex: Get function method-ness directly from debug info

[labath]

Summary

When searching for methods only, we need to do extra work to make sure
the functions we get from the apple tables are indeed methods.
Previously we were resolving the DIE into a SymbolContext and then
checked whether the enclosing CompilerDeclContext is a
class (or struct, or union).

This patch changes that to operate on the debug info directly. This
should be:

• simpler
• faster
• more consistent with the ManualDWARFIndex (which does the same check, only at indexing time).

What we lose this ways is for the language plugin to have a say in what
it considers to be a "class", but that's probably more flexibility than
we need (and if we really wanted to do that in the future, we could
implement a more direct way to consult the plugin about this).

This also fixes the find-method-local-struct test, which was failing
because we were not able to construct a CompilerDeclContext for a local
struct correctly.

As a drive-by, I rename the DWARFDIE's IsStructClassOrUnion method to
match the name on the CompilerDeclContext class.

[JDevlieghere]

Thanks Pavel, LGTM.

[clayborg]

source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp

153

move up to line 150 and use this variable in the if statement instead of repeating "name_type_mask & eFunctionNameTypeMethod" twice?

source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

236

I can never remember when a DW_AT_abstract_origin might be used. Might be nice to have a DWARFDIE method:

DWARFDIE DWARFDIE::GetAbstractOriginOrSpecification();

this would return either the the DW_AT_specification or the DW_AT_abstract_origin. If we go that route the this coce would become:

GetAbstractOriginOrSpecification().GetParent().IsStructUnionOrClass();

[labath]

source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

236

How would this method know which DIE to return? In case of inlined methods you can have a chain of DIEs:
DIE1 --- DW_AT_abstract_origin --> DIE2 --- DW_AT_specification --> DIE3
Each of these dies will have a different parent.

The current function will check for the parent of DIE1 and DIE3 (this is what the manual index does) though to be fully correct maybe we should check all three of them (?) Or do you think checking the last DIE in that list should be always enough? That would seem to be the case for the dwarf I've seen, but I'm not sure if that is always correct..

[clayborg]

source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

236

Yeah, unfortunately I can't elaborate too much without seeing a bad example. If anything in the chain has a parent that is a struct/union or class might be enough, so we could ask each DIE in the specification or abstract origin chain if its parent is a struct/union/class and just return true if so?

[clayborg]

So my previous code suggestion might not work as we would want to recurse through the specification or abstract origin chain.

[labath]

Implement recursive search in IsMethod()

[labath]

source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp

153

Done. I've created variables for both enum values, as having just one of them in the if statement looked weird.

source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

236

I've reimplemented the function to do a proper recursive search for the parent, including a infinite-recursion guard.

[JDevlieghere]

source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

236

Looks good, we have almost the exact same implementation in findRecursively in llvm.

[labath]

source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

236

It should be. I copied it from there. :)

[clayborg]

Very nice

[clayborg]

After seeing this, it might be nice to put the recursion that follows the DW_AT_specification and DW_AT_abstract_origin and avoids infinite recursion into a DWARFDIE function that takes a callback:

typedef bool (*DIECallback)(DWARFDIE &die);
void DWARFDIE::VisitAbstractOriginsAndSpecifications(DIECallback callback);

The contents would be very similar to the DWARFDIE::IsMethod() function, but it would listen to the "bool" return value from calling the "callback" function and stop recursing if true or false is returned so we can stop the recursion if we find what we need. Then we can re-use this function for more

[labath]

I have a feeling we are starting to over-engineer this. Visiting referenced dies
sounds like a useful utility in general, though I think most of the users will
be content with just visiting the attributes of those dies (and that's a
functionality we already have). Nonetheless, I implemented something like that.
I made it an iterator-based api, as callback-based apis are generally more
complicated to use.

[labath]

ps: the specificationsAndAbstractOrigins sounded like too big of a mouthful. I've invented the name "elaborating dies" for that.

[clayborg]

I can't think of a better name, looks good. Thanks for taking the time, this will be great.

lit/SymbolFile/DWARF/find-method-local-struct.cpp

-// llvm.org/pr37537
-// XFAIL: *
-
 // RUN: clang %s -g -c -o %t --target=x86_64-apple-macosx
 // RUN: lldb-test symbols --name=foo --find=function --function-flags=method %t | \
 // RUN:   FileCheck %s
 
 // CHECK-DAG: name = "sbar::foo()", mangled = "_ZN4sbar3fooEv"
 // CHECK-DAG: name = "ffbar()::sbar::foo()", mangled = "_ZZ5ffbarvEN4sbar3fooEv"
 
 struct sbar {

source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp

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,
     llvm::function_ref<bool(const DWARFDIE &die, bool include_inlines,
                             lldb_private::SymbolContextList &sc_list)>
         resolve_function,
     llvm::function_ref<CompilerDeclContext(lldb::user_id_t type_uid)>
         get_decl_context_containing_uid,
     const CompilerDeclContext *parent_decl_ctx, uint32_t name_type_mask,
if (((name_type_mask & eFunctionNameTypeMethod) && !parent_decl_ctx) ||
 
     for (uint32_t i = 0; i < num_matches; i++) {
       const DIERef &die_ref = offsets[i];
       DWARFDIE die = info.GetDIE(die_ref);
       if (die) {
         if (!SymbolFileDWARF::DIEInDeclContext(parent_decl_ctx, die))
           continue; // The containing decl contexts don't match
 
+        if (!KeepFunctionDIE(die, name_type_mask))
+          continue;
+
+        if (resolved_dies.find(die.GetDIE()) != resolved_dies.end())
+          continue;
+
         // If we get to here, the die is good, and we should add it:
-        if (resolved_dies.find(die.GetDIE()) == resolved_dies.end() &&
-            resolve_function(die, include_inlines, sc_list)) {
-          bool keep_die = true;
-          if ((name_type_mask &
-               (eFunctionNameTypeBase | eFunctionNameTypeMethod)) !=
-              (eFunctionNameTypeBase | eFunctionNameTypeMethod)) {
-            // We are looking for either basenames or methods, so we need
-            // to trim out the ones we won't want by looking at the type
-            SymbolContext sc;
-            if (sc_list.GetLastContext(sc)) {
-              if (sc.block) {
-                // We have an inlined function
-              } else if (sc.function) {
-                Type *type = sc.function->GetType();
-
-                if (type) {
-                  CompilerDeclContext decl_ctx =
-                      get_decl_context_containing_uid(type->GetID());
-                  if (decl_ctx.IsStructUnionOrClass()) {
-                    if (name_type_mask & eFunctionNameTypeBase) {
-                      sc_list.RemoveContextAtIndex(sc_list.GetSize() - 1);
-                      keep_die = false;
-                    }
-                  } else {
-                    if (name_type_mask & eFunctionNameTypeMethod) {
-                      sc_list.RemoveContextAtIndex(sc_list.GetSize() - 1);
-                      keep_die = false;
-                    }
-                  }
-                } else {
-                  m_module.ReportWarning(
-                      "function at die offset 0x%8.8x had no function type",
-                      die_ref.die_offset);
-                }
-              }
-            }
-          }
-          if (keep_die)
-            resolved_dies.insert(die.GetDIE());
-        }
+        if (resolve_function(die, include_inlines, sc_list))
       } else
         ReportInvalidDIEOffset(die_ref.die_offset, name.GetStringRef());
     }
     offsets.clear();
   }
 }
 
 void AppleDWARFIndex::GetFunctions(

source/Plugins/SymbolFile/DWARF/DWARFDIE.h

 //===-- DWARFDIE.h ----------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SymbolFileDWARF_DWARFDIE_h_
 #define SymbolFileDWARF_DWARFDIE_h_
 
 #include "DWARFBaseDIE.h"
+#include "llvm/ADT/SmallSet.h"
 
 class DWARFDIE : public DWARFBaseDIE {
 public:
+  class ElaboratingDIEIterator;
+
   using DWARFBaseDIE::DWARFBaseDIE;
 
   //----------------------------------------------------------------------
   // Tests
   //----------------------------------------------------------------------
-  bool IsStructClassOrUnion() const;
+  bool IsStructUnionOrClass() const;
+
+  bool IsMethod() const;
 
   //----------------------------------------------------------------------
   // Accessors
   //----------------------------------------------------------------------
   lldb::ModuleSP GetContainingDWOModule() const;
 
   DWARFDIE
   GetContainingDWOModuleDIE() const;
 
+  inline llvm::iterator_range<ElaboratingDIEIterator> elaborating_dies() const;
+
   //----------------------------------------------------------------------
   // Accessing information about a DIE
   //----------------------------------------------------------------------
   const char *GetMangledName() const;
 
   const char *GetPubname() const;
 
   const char *GetQualifiedName(std::string &storage) const;
public:
 
   lldb_private::CompilerDecl GetDecl() const;
 
   lldb_private::CompilerDeclContext GetDeclContext() const;
 
   lldb_private::CompilerDeclContext GetContainingDeclContext() const;
 };
 
+/// Iterate through all DIEs elaborating (i.e. reachable by a chain of
+/// DW_AT_specification and DW_AT_abstract_origin attributes) a given DIE. For
+/// convenience, the starting die is included in the sequence as the first
+/// item.
+class DWARFDIE::ElaboratingDIEIterator
+    : public std::iterator<std::input_iterator_tag, DWARFDIE> {
+
+  // The operating invariant is: top of m_worklist contains the "current" item
+  // and the rest of the list are items yet to be visited. An empty worklist
+  // means we've reached the end.
+  // Infinite recursion is prevented by maintaining a list of seen DIEs.
+  // Container sizes are optimized for the case of following DW_AT_specification
+  // and DW_AT_abstract_origin just once.
+  llvm::SmallVector<DWARFDIE, 2> m_worklist;
+  llvm::SmallSet<lldb::user_id_t, 3> m_seen;
+
+  void Next();
+
+public:
+  /// An iterator starting at die d.
+  explicit ElaboratingDIEIterator(DWARFDIE d) : m_worklist(1, d) {}
+
+  /// End marker
+  ElaboratingDIEIterator() {}
+
+  const DWARFDIE &operator*() const { return m_worklist.back(); }
+  ElaboratingDIEIterator &operator++() {
+    Next();
+    return *this;
+  }
+  ElaboratingDIEIterator operator++(int) {
+    ElaboratingDIEIterator I = *this;
+    Next();
+    return I;
+  }
+
+  friend bool operator==(const ElaboratingDIEIterator &a,
+                         const ElaboratingDIEIterator &b) {
+    if (a.m_worklist.empty() || b.m_worklist.empty())
+      return a.m_worklist.empty() == b.m_worklist.empty();
+    return a.m_worklist.back() == b.m_worklist.back();
+  }
+  friend bool operator!=(const ElaboratingDIEIterator &a,
+                         const ElaboratingDIEIterator &b) {
+    return !(a == b);
+  }
+};
+
+llvm::iterator_range<DWARFDIE::ElaboratingDIEIterator>
+DWARFDIE::elaborating_dies() const {
+  return llvm::make_range(ElaboratingDIEIterator(*this),
+                          ElaboratingDIEIterator());
+}
+
 #endif // SymbolFileDWARF_DWARFDIE_h_

source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

 //===-- DWARFDIE.cpp --------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "DWARFDIE.h"
 
 #include "DWARFASTParser.h"
-#include "DWARFUnit.h"
 #include "DWARFDIECollection.h"
 #include "DWARFDebugInfo.h"
-#include "DWARFDeclContext.h"
-
 #include "DWARFDebugInfoEntry.h"
+#include "DWARFDeclContext.h"
+#include "DWARFUnit.h"
 
 using namespace lldb_private;
 
+void DWARFDIE::ElaboratingDIEIterator::Next() {
+  assert(!m_worklist.empty() && "Incrementing end iterator?");
+
+  // Pop the current item from the list.
+  DWARFDIE die = m_worklist.back();
+  m_worklist.pop_back();
+
+  // And add back any items that elaborate it.
+  for (dw_attr_t attr : {DW_AT_specification, DW_AT_abstract_origin}) {
+    if (DWARFDIE d = die.GetReferencedDIE(attr))
+      if (m_seen.insert(die.GetID()).second)
+        m_worklist.push_back(d);
+  }
+}
+
 DWARFDIE
 DWARFDIE::GetParent() const {
   if (IsValid())
     return DWARFDIE(m_cu, m_die->GetParent());
   else
     return DWARFDIE();
 }
 

 DWARFDIE
 DWARFDIE::GetParentDeclContextDIE() const {
   if (IsValid())
     return m_die->GetParentDeclContextDIE(GetDWARF(), m_cu);
   else
     return DWARFDIE();
 }
 
-bool DWARFDIE::IsStructClassOrUnion() const {
+bool DWARFDIE::IsStructUnionOrClass() const {
   const dw_tag_t tag = Tag();
   return tag == DW_TAG_class_type || tag == DW_TAG_structure_type ||
          tag == DW_TAG_union_type;
 }
 
+bool DWARFDIE::IsMethod() const {
+  for (DWARFDIE d: elaborating_dies())
+    if (d.GetParent().IsStructUnionOrClass())
+      return true;
+  return false;
+}
+
 DWARFDIE
 DWARFDIE::GetContainingDWOModuleDIE() const {
   if (IsValid()) {
     DWARFDIE top_module_die;
     // Now make sure this DIE is scoped in a DW_TAG_module tag and return true
     // if so
     for (DWARFDIE parent = GetParent(); parent.IsValid();
          parent = parent.GetParent()) {

source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.cpp

case DW_TAG_subprogram:
               set.function_selectors.Insert(objc_selector_name,
                                             DIERef(cu_offset, die.GetOffset()));
             if (objc_fullname_no_category_name)
               set.function_fullnames.Insert(objc_fullname_no_category_name,
                                             DIERef(cu_offset, die.GetOffset()));
           }
           // If we have a mangled name, then the DW_AT_name attribute is
           // usually the method name without the class or any parameters
-          const DWARFDebugInfoEntry *parent = die.GetParent();
-          bool is_method = false;
-          if (parent) {
-            DWARFDIE parent_die(&unit, parent);
-            if (parent_die.IsStructClassOrUnion())
-              is_method = true;
-            else {
-              if (specification_die_form.IsValid()) {
-                DWARFDIE specification_die =
-                    unit.GetSymbolFileDWARF()->DebugInfo()->GetDIE(
-                        DIERef(specification_die_form));
-                if (specification_die.GetParent().IsStructClassOrUnion())
-                  is_method = true;
-              }
-            }
-          }
+          bool is_method = DWARFDIE(&unit, &die).IsMethod();
 
           if (is_method)
             set.function_methods.Insert(ConstString(name),
                                         DIERef(cu_offset, die.GetOffset()));
           else
             set.function_basenames.Insert(ConstString(name),
                                           DIERef(cu_offset, die.GetOffset()));