Fix the type resolver algorithm.

The new algorithm do the following:

- Try to use type_info on the object the get the object real name.
- Try to find a type resolver with the name returned by type_info.
- If a type resolver was found, get the python type.
- Else, ask binding manager to resolve the type walking on all possible
  subclasses found in the inheritance tree.

The binding manager has a graph representing the class inheritance tree.

Note: This commit break the libshiboken ABI, but not the API.

Reviewer: Luciano Wolf <luciano.wolf@openbossa.org>
          Renato Araújo <renato.araujo@openbossa.org>

5 files changed, 91 insertions, 32 deletions

diff --git a/libshiboken/basewrapper.cpp b/libshiboken/basewrapper.cpp
index e5e6d3dc4..304080c91 100644
--- a/libshiboken/basewrapper.cpp
+++ b/libshiboken/basewrapper.cpp
@@ -264,11 +264,19 @@ void destroyParentInfo(SbkBaseWrapper* obj, bool removeFromParent)
 PyObject* SbkBaseWrapper_New(SbkBaseWrapperType* instanceType,
                              void* cptr,
                              bool hasOwnership,
-                             bool isExactType)
+                             bool isExactType, const char* typeName)
 {
     // Try to find the exact type of cptr.
-    if (!isExactType && instanceType->type_discovery)
-        instanceType = instanceType->type_discovery->getType(cptr, instanceType);
+    if (!isExactType) {
+        TypeResolver* tr = 0;
+        if (typeName) {
+            tr = TypeResolver::get(typeName);
+            if (tr)
+                instanceType = reinterpret_cast<SbkBaseWrapperType*>(tr->pythonType());
+        }
+        if (!tr)
+            instanceType = BindingManager::instance().resolveType(cptr, instanceType);
+    }
 
     SbkBaseWrapper* self = reinterpret_cast<SbkBaseWrapper*>(SbkBaseWrapper_TpNew(reinterpret_cast<PyTypeObject*>(instanceType), 0, 0));
     self->cptr[0] = cptr;
@@ -613,22 +621,6 @@ void setErrorAboutWrongArguments(PyObject* args, const char* funcName, const cha
 
 }
 
-SbkBaseWrapperType* TypeDiscovery::getType(const void* cptr, SbkBaseWrapperType* instanceType) const
-{
-    TypeDiscoveryFuncList::const_reverse_iterator it = m_discoveryFunctions.rbegin();
-    for (; it != m_discoveryFunctions.rend(); ++it) {
-        SbkBaseWrapperType* type = (*it)(const_cast<void*>(cptr), instanceType);
-        if (type)
-            return type;
-    }
-    return instanceType;
-}
-
-void TypeDiscovery::addTypeDiscoveryFunction(Shiboken::TypeDiscoveryFunc func)
-{
-    m_discoveryFunctions.push_back(func);
-}
-
 class FindBaseTypeVisitor : public HierarchyVisitor
 {
     public:
diff --git a/libshiboken/basewrapper.h b/libshiboken/basewrapper.h
index 703c46532..e65a5b3fa 100644
--- a/libshiboken/basewrapper.h
+++ b/libshiboken/basewrapper.h
@@ -56,6 +56,7 @@ extern "C"
 /// Function signature for the multiple inheritance information initializers that should be provided by classes with multiple inheritance.
 typedef int* (*MultipleInheritanceInitFunction)(const void*);
 struct SbkBaseWrapperType;
+
 /**
 *   Special cast function is used to correctly cast an object when it's
 *   part of a multiple inheritance hierarchy.
@@ -64,7 +65,6 @@ struct SbkBaseWrapperType;
 typedef void* (*SpecialCastFunction)(void*, SbkBaseWrapperType*);
 typedef void* (*ObjectCopierFunction)(const void*);
 typedef SbkBaseWrapperType* (*TypeDiscoveryFunc)(void*, SbkBaseWrapperType*);
-typedef std::list<TypeDiscoveryFunc> TypeDiscoveryFuncList;
 
 typedef void* (*ExtendedToCppFunc)(PyObject*);
 typedef bool (*ExtendedIsConvertibleFunc)(PyObject*);
@@ -75,14 +75,6 @@ typedef void (*DeleteUserDataFunc)(void*);
 extern LIBSHIBOKEN_API PyTypeObject SbkBaseWrapperType_Type;
 extern LIBSHIBOKEN_API SbkBaseWrapperType SbkBaseWrapper_Type;
 
-class LIBSHIBOKEN_API TypeDiscovery {
-public:
-    SbkBaseWrapperType* getType(const void* cptr, SbkBaseWrapperType* instanceType) const;
-    void addTypeDiscoveryFunction(TypeDiscoveryFunc func);
-private:
-    TypeDiscoveryFuncList m_discoveryFunctions;
-};
-
 /// PyTypeObject extended with C++ multiple inheritance information.
 struct LIBSHIBOKEN_API SbkBaseWrapperType
 {
@@ -91,7 +83,7 @@ struct LIBSHIBOKEN_API SbkBaseWrapperType
     MultipleInheritanceInitFunction mi_init;
     /// Special cast function, null if this class doesn't have multiple inheritance.
     SpecialCastFunction mi_specialcast;
-    TypeDiscovery* type_discovery;
+    TypeDiscoveryFunc type_discovery;
     ObjectCopierFunction obj_copier;
     /// Extended "isConvertible" function to be used when a conversion operator is defined in another module.
     ExtendedIsConvertibleFunc ext_isconvertible;
@@ -221,7 +213,8 @@ LIBSHIBOKEN_API PyObject*
 SbkBaseWrapper_New(SbkBaseWrapperType* instanceType,
                    void* cptr,
                    bool hasOwnership = true,
-                   bool isExactType = false);
+                   bool isExactType = false,
+                   const char* typeName = 0);
 
 LIBSHIBOKEN_API PyObject*
 SbkBaseWrapper_TpNew(PyTypeObject* subtype, PyObject*, PyObject*);
diff --git a/libshiboken/bindingmanager.cpp b/libshiboken/bindingmanager.cpp
index 7bd402725..33e9f3ad6 100644
--- a/libshiboken/bindingmanager.cpp
+++ b/libshiboken/bindingmanager.cpp
@@ -33,16 +33,71 @@
  */
 
 #include "basewrapper.h"
+#include <cstddef>
+#include <fstream>
 #include "basewrapper_p.h"
 #include "bindingmanager.h"
 #include "google/dense_hash_map"
-#include <cstddef>
+#include "sbkdbg.h"
 
 namespace Shiboken
 {
 
 typedef google::dense_hash_map<const void*, PyObject*> WrapperMap;
 
+class Graph
+{
+public:
+    typedef std::list<SbkBaseWrapperType*> NodeList;
+    typedef google::dense_hash_map<SbkBaseWrapperType*, NodeList> Edges;
+
+    Edges m_edges;
+
+    Graph()
+    {
+        m_edges.set_empty_key(0);
+    }
+
+    void addEdge(SbkBaseWrapperType* from, SbkBaseWrapperType* to)
+    {
+        m_edges[from].push_back(to);
+    }
+
+#ifndef NDEBUG
+    void dumpDotGraph()
+    {
+        std::ofstream file("/tmp/shiboken_graph.dot");
+
+        file << "digraph D {\n";
+
+        Edges::const_iterator i = m_edges.begin();
+        for (; i != m_edges.end(); ++i) {
+            SbkBaseWrapperType* node1 = i->first;
+            const NodeList& nodeList = i->second;
+            NodeList::const_iterator j = nodeList.begin();
+            for (; j != nodeList.end(); ++j)
+                file << '"' << (*j)->super.ht_type.tp_name << "\" -> \"" << node1->super.ht_type.tp_name << "\"\n";
+        }
+        file << "}\n";
+    }
+#endif
+
+    SbkBaseWrapperType* identifyType(void* cptr, SbkBaseWrapperType* type, SbkBaseWrapperType* baseType) const
+    {
+        Edges::const_iterator edgesIt = m_edges.find(type);
+        if (edgesIt != m_edges.end()) {
+            const NodeList& adjNodes = m_edges.find(type)->second;
+            NodeList::const_iterator i = adjNodes.begin();
+            for (; i != adjNodes.end(); ++i) {
+                SbkBaseWrapperType* newType = identifyType(cptr, *i, baseType);
+                if (newType)
+                    return newType;
+            }
+        }
+        return type->type_discovery ? type->type_discovery(cptr, baseType) : 0;
+    }
+};
+
 
 #ifndef NDEBUG
 static void showWrapperMap(const WrapperMap& wrapperMap)
@@ -58,6 +113,7 @@ static void showWrapperMap(const WrapperMap& wrapperMap)
 
 struct BindingManager::BindingManagerPrivate {
     WrapperMap wrapperMapper;
+    Graph classHierarchy;
     void releaseWrapper(void* cptr);
     void assignWrapper(PyObject* wrapper, const void* cptr);
 };
@@ -230,5 +286,16 @@ void BindingManager::transferOwnershipToCpp(SbkBaseWrapper* wrapper)
         invalidateWrapper(wrapper);
 }
 
+void BindingManager::addClassInheritance(Shiboken::SbkBaseWrapperType* parent, Shiboken::SbkBaseWrapperType* child)
+{
+    m_d->classHierarchy.addEdge(parent, child);
+}
+
+SbkBaseWrapperType* BindingManager::resolveType(void* cptr, Shiboken::SbkBaseWrapperType* type)
+{
+    SbkBaseWrapperType* identifiedType = m_d->classHierarchy.identifyType(cptr, type, type);
+    return identifiedType ? identifiedType : type;
+}
+
 } // namespace Shiboken
 
diff --git a/libshiboken/bindingmanager.h b/libshiboken/bindingmanager.h
index 150baa90a..dd18dcdc1 100644
--- a/libshiboken/bindingmanager.h
+++ b/libshiboken/bindingmanager.h
@@ -42,6 +42,7 @@ namespace Shiboken
 {
 
 struct SbkBaseWrapper;
+struct SbkBaseWrapperType;
 
 class LIBSHIBOKEN_API BindingManager
 {
@@ -73,6 +74,8 @@ public:
         transferOwnershipToCpp(reinterpret_cast<SbkBaseWrapper*>(wrapper));
     }
 
+    void addClassInheritance(SbkBaseWrapperType* parent, SbkBaseWrapperType* child);
+    SbkBaseWrapperType* resolveType(void* cptr, SbkBaseWrapperType* type);
 private:
     ~BindingManager();
     // disable copy
diff --git a/libshiboken/conversions.h b/libshiboken/conversions.h
index 6247c55d8..8caa56c84 100644
--- a/libshiboken/conversions.h
+++ b/libshiboken/conversions.h
@@ -38,6 +38,7 @@
 #include <Python.h>
 #include <limits>
 #include <memory>
+#include <typeinfo>
 
 #include "pyenum.h"
 #include "basewrapper.h"
@@ -119,8 +120,11 @@ struct CppObjectCopier<T, true>
 template<typename T>
 inline PyObject* createWrapper(const T* cppobj, bool hasOwnership = false, bool isExactType = false)
 {
+    const char* typeName = 0;
+    if (!isExactType)
+        typeName = typeid(*const_cast<T*>(cppobj)).name();
     return SbkBaseWrapper_New(reinterpret_cast<SbkBaseWrapperType*>(SbkType<T>()),
-                              const_cast<T*>(cppobj), hasOwnership, isExactType);
+                              const_cast<T*>(cppobj), hasOwnership, isExactType, typeName);
 }
 
 // Base Conversions ----------------------------------------------------------