<rdar://problem/15530080>

Rework data formatters matching algorithm
What happens now is that, for each category, the FormatNavigator generates all possible matches, and checks them one by one
Since the possible matches do not actually depend on the category (whether a match is accepted or not does, but that check can be shifted at a more convenient time),
it is actually feasible to generate every possible match upfront and then let individual categories just scan through those

This commit changes things by introducing a notion of formatters match candidate, and shifting responsibility for generating all of them given a (ValueObject,DynamicValueType) pair
from the FormatNavigator back to the FormatManager
A list of these candidates is then passed down to each category for matching
Candidates also need to remember whether they were generated by stripping pointers, references, typedefs, since this is something that individual formatters can choose to reject
This check, however, is conveniently only done once a "textual" match has been found, so that the list of candidates is truly category-independent

While the performance benefit is small (mostly, due to caching), this is much cleaner from a design perspective

llvm-svn: 195395

7 files changed, 128 insertions, 224 deletions

diff --git a/lldb/include/lldb/DataFormatters/CXXFormatterFunctions.h b/lldb/include/lldb/DataFormatters/CXXFormatterFunctions.h
index 433c2a3c407..415ef9be59e 100644
--- a/lldb/include/lldb/DataFormatters/CXXFormatterFunctions.h
+++ b/lldb/include/lldb/DataFormatters/CXXFormatterFunctions.h
@@ -17,6 +17,8 @@
 
 #include "lldb/Core/ConstString.h"
 #include "lldb/DataFormatters/FormatClasses.h"
+#include "lldb/DataFormatters/TypeSynthetic.h"
+#include "lldb/Target/ExecutionContext.h"
 #include "lldb/Target/Target.h"
 
 #include "clang/AST/ASTContext.h"
diff --git a/lldb/include/lldb/DataFormatters/FormatCache.h b/lldb/include/lldb/DataFormatters/FormatCache.h
index bd9e20ccc9e..1505d7c4618 100644
--- a/lldb/include/lldb/DataFormatters/FormatCache.h
+++ b/lldb/include/lldb/DataFormatters/FormatCache.h
@@ -18,6 +18,7 @@
 // Project includes
 #include "lldb/lldb-public.h"
 #include "lldb/Core/ConstString.h"
+#include "lldb/Host/Mutex.h"
 #include "lldb/DataFormatters/FormatClasses.h"
 
 namespace lldb_private {
diff --git a/lldb/include/lldb/DataFormatters/FormatClasses.h b/lldb/include/lldb/DataFormatters/FormatClasses.h
index 6d9a50e8f2c..651160371c6 100644
--- a/lldb/include/lldb/DataFormatters/FormatClasses.h
+++ b/lldb/include/lldb/DataFormatters/FormatClasses.h
@@ -10,9 +10,6 @@
 #ifndef lldb_FormatClasses_h_
 #define lldb_FormatClasses_h_
 
-// C Includes
-#include <stdint.h>
-
 // C++ Includes
 #include <string>
 #include <vector>
@@ -23,17 +20,86 @@
 #include "lldb/lldb-public.h"
 #include "lldb/lldb-enumerations.h"
 
-#include "lldb/Core/ValueObject.h"
-#include "lldb/Interpreter/ScriptInterpreterPython.h"
 #include "lldb/Symbol/ClangASTType.h"
 #include "lldb/Symbol/Type.h"
 
-#include "lldb/DataFormatters/TypeFormat.h"
-#include "lldb/DataFormatters/TypeSummary.h"
-#include "lldb/DataFormatters/TypeSynthetic.h"
-
 namespace lldb_private {
 
+class FormattersMatchCandidate
+{
+public:
+    
+    FormattersMatchCandidate (ConstString name,
+                              uint32_t reason,
+                              bool strip_ptr,
+                              bool strip_ref,
+                              bool strip_tydef) :
+    m_type_name(name),
+    m_reason(reason),
+    m_stripped_pointer(strip_ptr),
+    m_stripped_reference(strip_ref),
+    m_stripped_typedef(strip_tydef)
+    {
+    }
+    
+    ~FormattersMatchCandidate ()
+    {}
+    
+    ConstString
+    GetTypeName () const
+    {
+        return m_type_name;
+    }
+    
+    uint32_t
+    GetReason () const
+    {
+        return m_reason;
+    }
+    
+    bool
+    DidStripPointer () const
+    {
+        return m_stripped_pointer;
+    }
+    
+    bool
+    DidStripReference () const
+    {
+        return m_stripped_reference;
+    }
+    
+    bool
+    DidStripTypedef () const
+    {
+        return m_stripped_typedef;
+    }
+    
+    template <class Formatter>
+    bool
+    IsMatch (const std::shared_ptr<Formatter>& formatter_sp) const
+    {
+        if (!formatter_sp)
+            return false;
+        if (formatter_sp->Cascades() == false && DidStripTypedef())
+            return false;
+        if (formatter_sp->SkipsPointers() && DidStripPointer())
+            return false;
+        if (formatter_sp->SkipsReferences() && DidStripReference())
+            return false;
+        return true;
+    }
+    
+private:
+    ConstString m_type_name;
+    uint32_t m_reason;
+    bool m_stripped_pointer;
+    bool m_stripped_reference;
+    bool m_stripped_typedef;
+};
+
+typedef std::vector<FormattersMatchCandidate> FormattersMatchVector;
+    
 class TypeNameSpecifierImpl
 {
 public:
diff --git a/lldb/include/lldb/DataFormatters/FormatManager.h b/lldb/include/lldb/DataFormatters/FormatManager.h
index 3c90c993e0c..750e5300831 100644
--- a/lldb/include/lldb/DataFormatters/FormatManager.h
+++ b/lldb/include/lldb/DataFormatters/FormatManager.h
@@ -19,6 +19,7 @@
 #include "lldb/lldb-enumerations.h"
 
 #include "lldb/DataFormatters/FormatCache.h"
+#include "lldb/DataFormatters/FormatClasses.h"
 #include "lldb/DataFormatters/FormatNavigator.h"
 #include "lldb/DataFormatters/TypeCategory.h"
 #include "lldb/DataFormatters/TypeCategoryMap.h"
@@ -213,7 +214,36 @@ public:
     {
     }
     
+    static FormattersMatchVector
+    GetPossibleMatches (ValueObject& valobj,
+                        lldb::DynamicValueType use_dynamic)
+    {
+        FormattersMatchVector matches;
+        GetPossibleMatches (valobj,
+                            valobj.GetClangType(),
+                            lldb_private::eFormatterChoiceCriterionDirectChoice,
+                            use_dynamic,
+                            matches,
+                            false,
+                            false,
+                            false,
+                            true);
+        return matches;
+    }
+
 private:
+    
+    static void
+    GetPossibleMatches (ValueObject& valobj,
+                        ClangASTType clang_type,
+                        uint32_t reason,
+                        lldb::DynamicValueType use_dynamic,
+                        FormattersMatchVector& entries,
+                        bool did_strip_ptr,
+                        bool did_strip_ref,
+                        bool did_strip_typedef,
+                        bool root_level = false);
+    
     FormatCache m_format_cache;
     NamedSummariesMap m_named_summaries_map;
     std::atomic<uint32_t> m_last_revision;
diff --git a/lldb/include/lldb/DataFormatters/FormatNavigator.h b/lldb/include/lldb/DataFormatters/FormatNavigator.h
index cd5f6824e19..1b82776fb28 100644
--- a/lldb/include/lldb/DataFormatters/FormatNavigator.h
+++ b/lldb/include/lldb/DataFormatters/FormatNavigator.h
@@ -26,6 +26,9 @@
 #include "lldb/Core/ValueObject.h"
 
 #include "lldb/DataFormatters/FormatClasses.h"
+#include "lldb/DataFormatters/TypeFormat.h"
+#include "lldb/DataFormatters/TypeSummary.h"
+#include "lldb/DataFormatters/TypeSynthetic.h"
 
 #include "lldb/Symbol/ClangASTContext.h"
 #include "lldb/Symbol/ClangASTType.h"
@@ -459,228 +462,29 @@ protected:
         }
         return false;
     }
-    
-    bool
-    Get_BitfieldMatch (ValueObject& valobj,
-                       ConstString typeName,
-                       MapValueType& entry,
-                       uint32_t& reason)
-    {
-        Log *log(lldb_private::GetLogIfAllCategoriesSet (LIBLLDB_LOG_TYPES));
-        // for bitfields, append size to the typename so one can custom format them
-        StreamString sstring;
-        sstring.Printf("%s:%d",typeName.AsCString(),valobj.GetBitfieldBitSize());
-        ConstString bitfieldname = ConstString(sstring.GetData());
-        if (log)
-            log->Printf("[Get_BitfieldMatch] appended bitfield info, final result is %s", bitfieldname.GetCString());
-        if (Get(bitfieldname, entry))
-        {
-            if (log)
-                log->Printf("[Get_BitfieldMatch] bitfield direct match found, returning");
-            return true;
-        }
-        else
-        {
-            reason |= lldb_private::eFormatterChoiceCriterionStrippedBitField;
-            if (log)
-                log->Printf("[Get_BitfieldMatch] no bitfield direct match");
-            return false;
-        }
-    }
-    
-    bool Get_ObjC (ValueObject& valobj,
-                   MapValueType& entry)
-    {
-        Log *log(lldb_private::GetLogIfAllCategoriesSet (LIBLLDB_LOG_TYPES));
-        lldb::ProcessSP process_sp = valobj.GetProcessSP();
-        ObjCLanguageRuntime* runtime = process_sp->GetObjCLanguageRuntime();
-        if (runtime == NULL)
-        {
-            if (log)
-                log->Printf("[Get_ObjC] no valid ObjC runtime, skipping dynamic");
-            return false;
-        }
-        ObjCLanguageRuntime::ClassDescriptorSP objc_class_sp (runtime->GetClassDescriptor(valobj));
-        if (!objc_class_sp)
-        {
-            if (log)
-                log->Printf("[Get_ObjC] invalid ISA, skipping dynamic");
-            return false;
-        }
-        ConstString name (objc_class_sp->GetClassName());
-        if (log)
-            log->Printf("[Get_ObjC] dynamic type inferred is %s - looking for direct dynamic match", name.GetCString());
-        if (Get(name, entry))
-        {
-            if (log)
-                log->Printf("[Get_ObjC] direct dynamic match found, returning");
-            return true;
-        }
-        if (log)
-            log->Printf("[Get_ObjC] no dynamic match");
-        return false;
-    }
-    
+
     bool
-    Get_Impl (ValueObject& valobj,
-              ClangASTType clang_type,
-              MapValueType& entry,
-              lldb::DynamicValueType use_dynamic,
-              uint32_t& reason)
+    Get (const FormattersMatchVector& candidates,
+         MapValueType& entry,
+         uint32_t *reason)
     {
-        Log *log(lldb_private::GetLogIfAllCategoriesSet (LIBLLDB_LOG_TYPES));
-
-        if (!clang_type.IsValid())
-        {
-            if (log)
-                log->Printf("[Get_Impl] type is invalid, returning");
-            return false;
-        }
-        
-        clang_type = clang_type.RemoveFastQualifiers();
-
-        ConstString typeName(clang_type.GetConstTypeName());
-        
-        if (valobj.GetBitfieldBitSize() > 0)
+        for (const FormattersMatchCandidate& candidate : candidates)
         {
-            if (Get_BitfieldMatch(valobj, typeName, entry, reason))
-                return true;
-        }
-        
-        if (log)
-            log->Printf("[Get_Impl] trying to get %s for VO name %s of type %s",
-                        m_name.c_str(),
-                        valobj.GetName().AsCString(),
-                        typeName.AsCString());
-        
-        if (Get(typeName, entry))
-        {
-            if (log)
-                log->Printf("[Get] direct match found, returning");
-            return true;
-        }
-        if (log)
-            log->Printf("[Get_Impl] no direct match");
-        
-        // strip pointers and references and see if that helps
-        if (clang_type.IsReferenceType())
-        {
-            if (log)
-                log->Printf("[Get_Impl] stripping reference");
-            if (Get_Impl(valobj, clang_type.GetNonReferenceType(), entry, use_dynamic, reason) && !entry->SkipsReferences())
+            if (Get(candidate.GetTypeName(),entry))
             {
-                reason |= lldb_private::eFormatterChoiceCriterionStrippedPointerReference;
-                return true;
-            }
-        }
-        else if (clang_type.IsPointerType())
-        {
-            if (log)
-                log->Printf("[Get_Impl] stripping pointer");
-            if (Get_Impl(valobj, clang_type.GetPointeeType(), entry, use_dynamic, reason) && !entry->SkipsPointers())
-            {
-                reason |= lldb_private::eFormatterChoiceCriterionStrippedPointerReference;
-                return true;
-            }
-        }
-        
-        bool canBeObjCDynamic = valobj.GetClangType().IsPossibleDynamicType (NULL,
-                                                                             false, // no C++
-                                                                             true); // yes ObjC
-        
-        if (canBeObjCDynamic)
-        {
-            if (use_dynamic != lldb::eNoDynamicValues)
-            {
-                if (log)
-                    log->Printf("[Get_Impl] allowed to figure out dynamic ObjC type");
-                if (Get_ObjC(valobj,entry))
+                if (candidate.IsMatch(entry) == false)
                 {
-                    reason |= lldb_private::eFormatterChoiceCriterionDynamicObjCDiscovery;
-                    return true;
+                    entry.reset();
+                    continue;
                 }
-            }
-            if (log)
-                log->Printf("[Get_Impl] dynamic disabled or failed - stripping ObjC pointer");
-            if (Get_Impl(valobj, clang_type.GetPointeeType(), entry, use_dynamic, reason) && !entry->SkipsPointers())
-            {
-                reason |= lldb_private::eFormatterChoiceCriterionStrippedPointerReference;
-                return true;
-            }
-        }
-        
-        // try to strip typedef chains
-        if (clang_type.IsTypedefType())
-        {
-            if (log)
-                log->Printf("[Get_Impl] stripping typedef");
-            if ((Get_Impl(valobj, clang_type.GetTypedefedType(), entry, use_dynamic, reason)) && entry->Cascades())
-            {
-                reason |= lldb_private::eFormatterChoiceCriterionNavigatedTypedefs;
-                return true;
-            }
-        }
-        
-        // out of luck here
-        return false;
-    }
-    
-    // we are separately passing in valobj and type because the valobj is fixed (and is used for ObjC discovery and bitfield size)
-    // but the type can change (e.g. stripping pointers, ...)
-    bool Get (ValueObject& valobj,
-              ClangASTType clang_type,
-              MapValueType& entry,
-              lldb::DynamicValueType use_dynamic,
-              uint32_t& reason)
-    {
-        Log *log(lldb_private::GetLogIfAllCategoriesSet (LIBLLDB_LOG_TYPES));
-        
-        if (Get_Impl (valobj, clang_type, entry, use_dynamic, reason))
-            return true;
-        
-        // try going to the unqualified type
-        do {
-            if (log)
-                log->Printf("[Get] trying the unqualified type");
-            if (!clang_type.IsValid())
-                break;
-
-            ClangASTType unqual_clang_ast_type = clang_type.GetFullyUnqualifiedType();
-            if (!unqual_clang_ast_type.IsValid())
-            {
-                if (log)
-                    log->Printf("[Get] could not get the unqual_clang_ast_type");
-                break;
-            }
-            if (unqual_clang_ast_type.GetOpaqueQualType() != clang_type.GetOpaqueQualType())
-            {
-                if (log)
-                    log->Printf("[Get] unqualified type is there and is not the same, let's try");
-                if (Get_Impl (valobj, unqual_clang_ast_type,entry, use_dynamic, reason))
-                    return true;
-            }
-            else if (log)
-                log->Printf("[Get] unqualified type same as original type");
-        } while(false);
-        
-        // if all else fails, go to static type
-        if (valobj.IsDynamic())
-        {
-            if (log)
-                log->Printf("[Get] going to static value");
-            lldb::ValueObjectSP static_value_sp(valobj.GetStaticValue());
-            if (static_value_sp)
-            {
-                if (log)
-                    log->Printf("[Get] has a static value - actually use it");
-                if (Get(*static_value_sp.get(), static_value_sp->GetClangType(), entry, use_dynamic, reason))
+                else
                 {
-                    reason |= lldb_private::eFormatterChoiceCriterionWentToStaticValue;
+                    if(reason)
+                        *reason = candidate.GetReason();
                     return true;
                 }
             }
         }
-        
         return false;
     }
 };
diff --git a/lldb/include/lldb/DataFormatters/TypeCategory.h b/lldb/include/lldb/DataFormatters/TypeCategory.h
index 6461c4e97e4..082395a0461 100644
--- a/lldb/include/lldb/DataFormatters/TypeCategory.h
+++ b/lldb/include/lldb/DataFormatters/TypeCategory.h
@@ -18,6 +18,7 @@
 #include "lldb/lldb-public.h"
 #include "lldb/lldb-enumerations.h"
 
+#include "lldb/DataFormatters/FormatClasses.h"
 #include "lldb/DataFormatters/FormatNavigator.h"
 
 namespace lldb_private {    
@@ -177,23 +178,22 @@ namespace lldb_private {
                 return m_enabled_position;
         }
         
-        
         bool
         Get (ValueObject& valobj,
+             const FormattersMatchVector& candidates,
              lldb::TypeFormatImplSP& entry,
-             lldb::DynamicValueType use_dynamic,
              uint32_t* reason = NULL);
         
         bool
         Get (ValueObject& valobj,
+             const FormattersMatchVector& candidates,
              lldb::TypeSummaryImplSP& entry,
-             lldb::DynamicValueType use_dynamic,
              uint32_t* reason = NULL);
         
         bool
         Get (ValueObject& valobj,
+             const FormattersMatchVector& candidates,
              lldb::SyntheticChildrenSP& entry,
-             lldb::DynamicValueType use_dynamic,
              uint32_t* reason = NULL);
         
         void
diff --git a/lldb/include/lldb/lldb-forward.h b/lldb/include/lldb/lldb-forward.h
index a72e2e9303c..68d85f081e2 100644
--- a/lldb/include/lldb/lldb-forward.h
+++ b/lldb/include/lldb/lldb-forward.h
@@ -97,6 +97,7 @@ class   FileSpecList;
 class   Flags;
 class   TypeCategoryImpl;
 class   FormatManager;
+class   FormattersMatchCandidate;
 class   FuncUnwinders;
 class   Function;
 class   FunctionInfo;