Improve looking up functions with equivalent mangled names.

[sivachandra]

Summary

This, in a way, extends the existing "workaroud" by matching function
argument type names individually [instead of just matching "(args1...)"
with "(args2...)"]. For type name matching, a new method
CPlusPlusLanguage::TypeNamesEqual has been added. For now, this method
can only handle variations like:

<typename> * vs <typename>*
const <typename> vs <typename> const
const <typename> * const vs <typename> const * const

We can extend it to handle more complex name formats as needed.

The immediate benefit of this change is with evaluating std::map's
subscript operator when producer is GCC. Consider the following:

std::map<std::string, std::string> m;
std::string s("1");
m[s] = "one";
... ; // Break here

The command "expr m[s]" fails without this change if the producer is
GCC.

[sivachandra]

Fix a comment in file, fix formatting in another.

[sivachandra]

Add more gtest unittests.

[clayborg]

Sean should be the one to OK this.

[spyffe]

I'm concerned about the performance implications here, because FindBestAlternateMangledName is invoked for every C++ symbol lookup, not just for ones that would fail unless we did this workaround.

We have a ColectFallbackNames function in IRExecutionUnit.cpp to try hackier approaches if the simple approaches don't work. Would it be feasible to make this farily heavyweight search part of the fallback names mechanism?

include/lldb/Symbol/SymbolFile.h

public:
     virtual uint32_t        ResolveSymbolContext (const FileSpec& file_spec, uint32_t line, bool check_inlines, uint32_t resolve_scope, SymbolContextList& sc_list);
     virtual uint32_t        FindGlobalVariables (const ConstString &name, const CompilerDeclContext *parent_decl_ctx, bool append, uint32_t max_matches, VariableList& variables);
     virtual uint32_t        FindGlobalVariables (const RegularExpression& regex, bool append, uint32_t max_matches, VariableList& variables);
     virtual uint32_t        FindFunctions (const ConstString &name, const CompilerDeclContext *parent_decl_ctx, uint32_t name_type_mask, bool include_inlines, bool append, SymbolContextList& sc_list);
     virtual uint32_t        FindFunctions (const RegularExpression& regex, bool include_inlines, bool append, SymbolContextList& sc_list);
     virtual uint32_t        FindTypes (const SymbolContext& sc, const ConstString &name, const CompilerDeclContext *parent_decl_ctx, bool append, uint32_t max_matches, llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files, TypeMap& types);
     virtual size_t          FindTypes (const std::vector<CompilerContext> &context, bool append, TypeMap& types);
 
-    virtual void            GetMangledNamesForFunction(const std::string &scope_qualified_name, std::vector<ConstString> &mangled_names);
+    virtual void            GetMangledNamesForFunction(const SymbolContext& sc, const std::string &scope_qualified_name, const std::vector<std::string> &arguments, std::vector<ConstString> &mangled_names);
 //  virtual uint32_t        FindTypes (const SymbolContext& sc, const RegularExpression& regex, bool append, uint32_t max_matches, TypeList& types) = 0;
     virtual TypeList *      GetTypeList ();
     virtual size_t          GetTypes (lldb_private::SymbolContextScope *sc_scope,
                                       uint32_t type_mask,
                                       lldb_private::TypeList &type_list) = 0;
 
     virtual lldb_private::TypeSystem *
                             GetTypeSystemForLanguage (lldb::LanguageType language);

packages/Python/lldbsuite/test/lang/cpp/stl/TestSTL.py

class STLTestCase(TestBase):
 
     def setUp(self):
         # Call super's setUp().
         TestBase.setUp(self)
         # Find the line number to break inside main().
         self.source = 'main.cpp'
         self.line = line_number(self.source, '// Set break point at this line.')
 
+    def test_string_maps(self):
+        self.build()
+        exe = os.path.join(os.getcwd(), "a.out")
+
+        self.runCmd("file " + exe, CURRENT_EXECUTABLE_SET)
+
+        lldbutil.run_break_set_by_file_and_line (self, "main.cpp", self.line, num_expected_locations=1, loc_exact=True)
+        self.runCmd("run", RUN_SUCCEEDED)
+        self.expect("thread list", STOPPED_DUE_TO_BREAKPOINT,
+            substrs = ['main.cpp:%d' % self.line,
+                       'stop reason = breakpoint'])
+
+        self.expect('expr associative_array[hello_world]',
+            substrs = [' = 1'])
+        self.expect('expr ssmap[str]',
+            substrs = [' = "Hello World!"'])
+
     # rdar://problem/10400981
     @unittest2.expectedFailure
     def test(self):
         """Test some expressions involving STL data types."""
         self.build()
         exe = os.path.join(os.getcwd(), "a.out")
 
         # The following two lines, if uncommented, will enable loggings.

packages/Python/lldbsuite/test/lang/cpp/stl/main.cpp

 //===-- main.cpp ------------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include <cstdio>
 #include <iostream>
 #include <string>
 #include <map>
 int main (int argc, char const *argv[])
 {
     std::string hello_world ("Hello World!");
+    std::string str("a_string");
     std::cout << hello_world << std::endl;
     std::cout << hello_world.length() << std::endl;
     std::cout << hello_world[11] << std::endl;
 
     std::map<std::string, int> associative_array;
+    std::map<std::string, std::string> ssmap;
+    ssmap[str] = hello_world;
     std::cout << "size of upon construction associative_array: " << associative_array.size() << std::endl;
     associative_array[hello_world] = 1;
     associative_array["hello"] = 2;
     associative_array["world"] = 3;
 
     std::cout << "size of associative_array: " << associative_array.size() << std::endl;
     printf("associative_array[\"hello\"]=%d\n", associative_array["hello"]);
 
     printf("before returning....\n"); // Set break point at this line.
 }

source/Expression/IRExecutionUnit.cpp

 
 static ConstString
 FindBestAlternateMangledName(const ConstString &demangled,
                              const lldb::LanguageType &lang_type,
                              const SymbolContext &sym_ctx)
 {
     CPlusPlusLanguage::MethodName cpp_name(demangled);
     std::string scope_qualified_name = cpp_name.GetScopeQualifiedName();
+    const std::vector<std::string> &arguments = cpp_name.GetArguments();
 
     if (!scope_qualified_name.size())
         return ConstString();
 
     if (!sym_ctx.module_sp)
         return ConstString();
 
     SymbolVendor *sym_vendor = sym_ctx.module_sp->GetSymbolVendor();
     if (!sym_vendor)
         return ConstString();
 
     lldb_private::SymbolFile *sym_file = sym_vendor->GetSymbolFile();
     if (!sym_file)
         return ConstString();
 
     std::vector<ConstString> alternates;
-    sym_file->GetMangledNamesForFunction(scope_qualified_name, alternates);
+    sym_file->GetMangledNamesForFunction(sym_ctx, scope_qualified_name, arguments, alternates);
 
     std::vector<ConstString> param_and_qual_matches;
     std::vector<ConstString> param_matches;
     for (size_t i = 0; i < alternates.size(); i++)
     {
         ConstString alternate_mangled_name = alternates[i];
         Mangled mangled(alternate_mangled_name, true);
         ConstString demangled = mangled.GetDemangledName(lang_type);
 
         CPlusPlusLanguage::MethodName alternate_cpp_name(demangled);
         if (!cpp_name.IsValid())
             continue;
 
-        if (alternate_cpp_name.GetArguments() == cpp_name.GetArguments())
-        {
             if (alternate_cpp_name.GetQualifiers() == cpp_name.GetQualifiers())
                 param_and_qual_matches.push_back(alternate_mangled_name);
             else
                 param_matches.push_back(alternate_mangled_name);
-        }
-    }
 
     if (param_and_qual_matches.size())
         return param_and_qual_matches[0]; // It is assumed that there will be only one!
     else if (param_matches.size())
         return param_matches[0]; // Return one of them as a best match
     else
         return ConstString();
 }

source/Plugins/Language/CPlusPlus/CPlusPlusLanguage.h

public:
         GetScopeQualifiedName ();
         
         llvm::StringRef
         GetBasename ();
 
         llvm::StringRef
         GetContext ();
         
-        llvm::StringRef
+        const std::vector<std::string> &
         GetArguments ();
         
         llvm::StringRef
         GetQualifiers ();
 
     protected:
         void
         Parse();
     
+        void
+        SetArguments(const llvm::StringRef &arg_string);
+
         ConstString     m_full;         // Full name:    "lldb::SBTarget::GetBreakpointAtIndex(unsigned int) const"
         llvm::StringRef m_basename;     // Basename:     "GetBreakpointAtIndex"
         llvm::StringRef m_context;      // Decl context: "lldb::SBTarget"
-        llvm::StringRef m_arguments;    // Arguments:    "(unsigned int)"
+        std::vector<std::string> m_arguments;    // Arguments:    "(unsigned int)"
         llvm::StringRef m_qualifiers;   // Qualifiers:   "const"
         Type m_type;
         bool m_parsed;
         bool m_parse_error;
     };
 
     CPlusPlusLanguage() = default;
 
     ~CPlusPlusLanguage() override = default;
 
     lldb::LanguageType
     GetLanguageType () const override
     {
         return lldb::eLanguageTypeC_plus_plus;
     }
     
     lldb::TypeCategoryImplSP
     GetFormatters () override;
     
     HardcodedFormatters::HardcodedSummaryFinder
     GetHardcodedSummaries () override;
     
     HardcodedFormatters::HardcodedSyntheticFinder
     GetHardcodedSynthetics () override;
-    
     //------------------------------------------------------------------
     // Static Functions
     //------------------------------------------------------------------
     static void
     Initialize();
     
     static void
     Terminate();
public:
     // CPlusPlusLanguage::MethodName which has to have a fully qualified C++ name with parens and arguments.
     // If the name is a lone C identifier (e.g. C) or a qualified C identifier (e.g. A::B::C) it will return true,
     // and identifier will be the identifier (C and C respectively) and the context will be "" and "A::B::" respectively.
     // If the name fails the heuristic matching for a qualified or unqualified C/C++ identifier, then it will return false
     // and identifier and context will be unchanged.
 
     static bool
     ExtractContextAndIdentifier (const char *name, llvm::StringRef &context, llvm::StringRef &identifier);
-    
+    static bool
+    TypeNamesEqual(const llvm::StringRef &t1, const llvm::StringRef &t2);
+    
     // in some cases, compilers will output different names for one same type. when that happens, it might be impossible
     // to construct SBType objects for a valid type, because the name that is available is not the same as the name that
     // can be used as a search key in FindTypes(). the equivalents map here is meant to return possible alternative names
     // for a type through which a search can be conducted. Currently, this is only enabled for C++ but can be extended
     // to ObjC or other languages if necessary
     static uint32_t
     FindEquivalentNames(ConstString type_name, std::vector<ConstString>& equivalents);
 

source/Plugins/Language/CPlusPlus/CPlusPlusLanguage.cpp

 }
 
 void
 CPlusPlusLanguage::MethodName::Clear()
 {
     m_full.Clear();
     m_basename = llvm::StringRef();
     m_context = llvm::StringRef();
-    m_arguments = llvm::StringRef();
+    m_arguments = std::vector<std::string>();
     m_qualifiers = llvm::StringRef();
     m_type = eTypeInvalid;
     m_parsed = false;
     m_parse_error = false;
 }
 
 bool
 ReverseFindMatchingChars (const llvm::StringRef &s,
//            printf ("   mangled = '%s'\n", mangled.GetCString());
         m_parse_error = false;
         m_parsed = true;
         llvm::StringRef full (m_full.GetCString());
         
         size_t arg_start, arg_end;
         llvm::StringRef parens("()", 2);
         if (ReverseFindMatchingChars (full, parens, arg_start, arg_end))
         {
-            m_arguments = full.substr(arg_start, arg_end - arg_start + 1);
+            SetArguments(full.substr(arg_start, arg_end - arg_start + 1));
             if (arg_end + 1 < full.size())
                 m_qualifiers = full.substr(arg_end + 1);
             if (arg_start > 0)
             {
                 size_t basename_end = arg_start;
                 size_t context_start = 0;
                 size_t context_end = llvm::StringRef::npos;
                 if (basename_end > 0 && full[basename_end-1] == '>')
//            printf ("   mangled = '%s'\n", mangled.GetCString());
             }
 
             if (!IsValidBasename(m_basename))
             {
                 // The C++ basename doesn't match our regular expressions so this can't
                 // be a valid C++ method, clear everything out and indicate an error
                 m_context = llvm::StringRef();
                 m_basename = llvm::StringRef();
-                m_arguments = llvm::StringRef();
+                m_arguments = std::vector<std::string>();
                 m_qualifiers = llvm::StringRef();
                 m_parse_error = true;
             }
         }
         else
         {
             m_parse_error = true;
         }

 llvm::StringRef
 CPlusPlusLanguage::MethodName::GetContext ()
 {
     if (!m_parsed)
         Parse();
     return m_context;
 }
 
-llvm::StringRef
+const std::vector<std::string> &
 CPlusPlusLanguage::MethodName::GetArguments ()
 {
     if (!m_parsed)
         Parse();
     return m_arguments;
 }
 
+void
+CPlusPlusLanguage::MethodName::SetArguments(const llvm::StringRef &arg_str)
+{
+    // Remove the open and close parenthesis.
+    llvm::StringRef input = arg_str.substr(1, arg_str.size() - 2);
+    int paren_count = 0;
+    int angle_count = 0;
+
+    std::string arg;
+    for (size_t i = 0; i < input.size(); i++)
+    {
+        char c = input[i];
+        switch (c)
+        {
+        case ',':
+            if (paren_count == 0 && angle_count == 0)
+            {
+                m_arguments.push_back(arg.substr());
+                arg.erase();
+                continue;
+            }
+        case '(':
+            paren_count++;
+            break;
+        case '<':
+            angle_count++;
+            break;
+        case ')':
+            paren_count--;
+            break;
+        case '>':
+            angle_count--;
+            break;
+        case ' ':
+            if (arg.size() == 0)
+                continue;
+        default:
+            break;
+        }
+
+        arg.push_back(c);
+    }
+
+    if (arg.size() > 0)
+        m_arguments.push_back(arg);
+}
+
 llvm::StringRef
 CPlusPlusLanguage::MethodName::GetQualifiers ()
 {
     if (!m_parsed)
         Parse();
     return m_qualifiers;
 }
 
 std::string
 CPlusPlusLanguage::MethodName::GetScopeQualifiedName ()
 {
     if (!m_parsed)
         Parse();
     if (m_basename.empty() || m_context.empty())
         return std::string();
 
     std::string res;
     res += m_context;
     res += "::";
     res += m_basename;
 
     return res;
 }
 
+bool CPlusPlusLanguage::TypeNamesEqual (const llvm::StringRef &t1, const llvm::StringRef &t2)
+{
+    llvm::StringRef r1 = t1.trim();
+    llvm::StringRef r2 = t2.trim();
+
+    if (r1 == r2)
+        return true;
+
+    char last = r1.back();
+    if (last == '&' || last == '*')
+    {
+        if (r2.back() != last)
+            return false;
+
+        return CPlusPlusLanguage::TypeNamesEqual(r1.drop_back(), r2.drop_back());
+    }
+
+    if (r1.endswith("const"))
+    {
+        // If both end with "const", drop strlen("const") from the back and compare.
+        if (r2.endswith("const"))
+            return CPlusPlusLanguage::TypeNamesEqual(r1.drop_back(5), r2.drop_back(5));
+
+        // If r2 starts with "const", then drop strlen("const") from its front and
+        // compare with r1 after dropping strlen("const") from its back.
+        if (r2.startswith("const"))
+            return CPlusPlusLanguage::TypeNamesEqual(r1.drop_back(5), r2.drop_front(5));
+
+        return false;
+    }
+
+    if (r1.startswith("const"))
+    {
+        // If both start with "const", drop strlen("const") from the front and compare.
+        if (r2.startswith("const"))
+            return CPlusPlusLanguage::TypeNamesEqual(r1.drop_front(5), r2.drop_front(5));
+
+        // If r2 ends with "const", then drop strlen("const") from its back and
+        // compare with r1 after dropping strlen("const") from its front.
+        if (r2.endswith("const"))
+            return CPlusPlusLanguage::TypeNamesEqual(r1.drop_front(5), r2.drop_back(5));
+
+        return false;
+    }
+
+    return false;
+}
+
 bool
 CPlusPlusLanguage::IsCPPMangledName (const char *name)
 {
     // FIXME, we should really run through all the known C++ Language plugins and ask each one if
     // this is a C++ mangled name, but we can put that off till there is actually more than one
     // we care about.
     
     if (name && name[0] == '_' && name[1] == 'Z')

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

public:
 
     uint32_t
     FindFunctions (const lldb_private::RegularExpression& regex,
                    bool include_inlines,
                    bool append,
                    lldb_private::SymbolContextList& sc_list) override;
 
     void
-    GetMangledNamesForFunction (const std::string &scope_qualified_name,
+    GetMangledNamesForFunction (const lldb_private::SymbolContext& sc,
+                                const std::string &scope_qualified_name,
+                                const std::vector<std::string> &arguments,
                                 std::vector<lldb_private::ConstString> &mangled_names) override;
 
     uint32_t
     FindTypes (const lldb_private::SymbolContext& sc,
                const lldb_private::ConstString &name,
                const lldb_private::CompilerDeclContext *parent_decl_ctx,
                bool append,
                uint32_t max_matches,

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

else
         FindFunctions (regex, m_function_fullname_index, include_inlines, sc_list);
     }
 
     // Return the number of variable that were appended to the list
     return sc_list.GetSize() - original_size;
 }
 
 void
-SymbolFileDWARF::GetMangledNamesForFunction (const std::string &scope_qualified_name,
+SymbolFileDWARF::GetMangledNamesForFunction (const SymbolContext& sc,
+                                             const std::string &scope_qualified_name,
+                                             const std::vector<std::string> &arguments,
                                              std::vector<ConstString> &mangled_names)
 {
     DWARFDebugInfo* info = DebugInfo();
     uint32_t num_comp_units = 0;
     if (info)
         num_comp_units = info->GetNumCompileUnits();
 
     for (uint32_t i = 0; i < num_comp_units; i++)
     {
         DWARFCompileUnit *cu = info->GetCompileUnitAtIndex(i);
         if (cu == nullptr)
             continue;
 
         SymbolFileDWARFDwo *dwo = cu->GetDwoSymbolFile();
         if (dwo)
-            dwo->GetMangledNamesForFunction(scope_qualified_name, mangled_names);
+            dwo->GetMangledNamesForFunction(sc, scope_qualified_name, arguments, mangled_names);
     }
 
     NameToOffsetMap::iterator iter = m_function_scope_qualified_name_map.find(scope_qualified_name);
     if (iter == m_function_scope_qualified_name_map.end())
         return;
 
+    size_t arg_count = arguments.size();
     DIERefSetSP set_sp = (*iter).second;
     std::set<DIERef>::iterator set_iter;
     for (set_iter = set_sp->begin(); set_iter != set_sp->end(); set_iter++)
     {
         DWARFDIE die = DebugInfo()->GetDIE (*set_iter);
+
+        Log *log = LogChannelDWARF::GetLogIfAll(DWARF_LOG_DEBUG_INFO);
+        TypeSystem *type_system = GetTypeSystemForLanguage(die.GetCU()->GetLanguageType());
+        DWARFASTParser *dwarf_ast = type_system->GetDWARFParser();
+        TypeSP type_sp = dwarf_ast->ParseTypeFromDWARF (sc, die, log, NULL);
+        CompilerType compiler_type = type_sp->GetFullCompilerType();
+
+        if (compiler_type.GetNumberOfFunctionArguments() != arg_count)
+            continue;
+
+        size_t match_count = 0;
+        for (size_t i = 0; i < compiler_type.GetNumberOfFunctionArguments(); i++)
+        {
+            std::string arg_type = compiler_type.GetFunctionArgumentAtIndex(i).GetTypeName().AsCString();
+            if (CPlusPlusLanguage::TypeNamesEqual(llvm::StringRef(arguments[i]), llvm::StringRef(arg_type)))
+                match_count++;
+            else
+                break;
+        }
+
+        if (match_count != arg_count)
+            continue;
+
         mangled_names.push_back(ConstString(die.GetMangledName()));
     }
 }
 
 
 uint32_t
 SymbolFileDWARF::FindTypes (const SymbolContext& sc, 
                             const ConstString &name, 

source/Symbol/SymbolFile.cpp

 SymbolFile::FindFunctions (const RegularExpression& regex, bool include_inlines, bool append, SymbolContextList& sc_list)
 {
     if (!append)
         sc_list.Clear();
     return 0;
 }
 
 void
-SymbolFile::GetMangledNamesForFunction(const std::string &scope_qualified_name, std::vector<ConstString> &mangled_names)
+SymbolFile::GetMangledNamesForFunction(const SymbolContext &sc,
+                                       const std::string &scope_qualified_name,
+                                       const std::vector<std::string> &arguments,
+                                       std::vector<ConstString> &mangled_names)
 {
     return;
 }
 
 uint32_t
 SymbolFile::FindTypes (const SymbolContext& sc, const ConstString &name, const CompilerDeclContext *parent_decl_ctx, bool append, uint32_t max_matches, llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files, TypeMap& types)
 {
     if (!append)

unittests/CMakeLists.txt

function(add_lldb_unittest test_name)
   llvm_config(${test_name} ${LLVM_LINK_COMPONENTS})
 endfunction()
 
 add_subdirectory(Core)
 add_subdirectory(Editline)
 add_subdirectory(Expression)
 add_subdirectory(Host)
 add_subdirectory(Interpreter)
+add_subdirectory(Language)
 add_subdirectory(ScriptInterpreter)
 add_subdirectory(Utility)

unittests/Language/CMakeLists.txt

+add_subdirectory(CPlusPlus)

unittests/Language/CPlusPlus/CMakeLists.txt

+add_lldb_unittest(LLDBCPlusCPlusLanguageTests
+  TypeNamesEqualityTest.cpp
+  )
+
+  target_link_libraries(lldbPluginCPlusPlusLanguage)

unittests/Language/CPlusPlus/TypeNamesEqualityTest.cpp

+//===-- ScalarTest.cpp ------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+
+#include "Plugins/Language/CPlusPlus/CPlusPlusLanguage.h"
+
+using namespace lldb_private;
+
+TEST(TypeNamesEqualTest, Equality)
+{
+    ASSERT_TRUE(CPlusPlusLanguage::TypeNamesEqual("int *", "int*"));
+    ASSERT_TRUE(CPlusPlusLanguage::TypeNamesEqual("unsigned int *", "unsigned int*"));
+    ASSERT_TRUE(CPlusPlusLanguage::TypeNamesEqual("const unsigned int", "unsigned int const"));
+    ASSERT_TRUE(CPlusPlusLanguage::TypeNamesEqual("const unsigned int *", "unsigned int const *"));
+    ASSERT_TRUE(CPlusPlusLanguage::TypeNamesEqual("unsigned int * const", "unsigned int * const"));
+}
+
+TEST(TypeNamesEqualTest, InEquality)
+{
+    ASSERT_FALSE(CPlusPlusLanguage::TypeNamesEqual("int *", "short int*"));
+    ASSERT_FALSE(CPlusPlusLanguage::TypeNamesEqual("unsigned int *", "unsigned int"));
+    ASSERT_FALSE(CPlusPlusLanguage::TypeNamesEqual("const unsigned int", "int const"));
+    ASSERT_FALSE(CPlusPlusLanguage::TypeNamesEqual("const unsigned int *", "unsigned int * const"));
+    ASSERT_FALSE(CPlusPlusLanguage::TypeNamesEqual("unsigned int const *", "unsigned int * const"));
+}