shiboken: Fix non-deterministic order of some SBK type indexes

Change underlying type of the type database from
a QHash<qualified_name, list of entries> to
a QMultiMap<qualified_name, entry>.

Previously, there was an allEntries() accessor and a function
named entries() building a QHash<qualified_name, entry>.
Simplify this so that there is only an entries() accessor
returning the QMultiMap.

Refactor the various Typedatabase::find() functions to operate on an
iterator range of the QMultiMap.

This unearthed some bugs:

1) In the generators, the call to findType(packageName()) would return
   the namespace entry for "sample" instead of the intended
   module type entry named "sample" due to the ordering.

   Add a new function to search for module type entries and assert
   that it finds it.

2) There was a duplicate, empty primitive type entry for
   QModelIndexList.

Task-number: PYSIDE-757
Change-Id: I1814e4ca67d306e1488398507707cfd07b3f2c78
Reviewed-by: Cristian Maureira-Fredes <cristian.maureira-fredes@qt.io>
Reviewed-by: Alexandru Croitor <alexandru.croitor@qt.io>

8 files changed, 122 insertions, 119 deletions

diff --git a/sources/pyside2/PySide2/QtCore/typesystem_core_common.xml b/sources/pyside2/PySide2/QtCore/typesystem_core_common.xml
index b17878bd0..cce9c7076 100644
--- a/sources/pyside2/PySide2/QtCore/typesystem_core_common.xml
+++ b/sources/pyside2/PySide2/QtCore/typesystem_core_common.xml
@@ -2128,7 +2128,6 @@
 
   <value-type name="QItemSelectionRange" hash-function="qHash">
   </value-type>
-  <primitive-type name="QModelIndexList"/>
   <object-type name="QAbstractProxyModel" polymorphic-id-expression="qobject_cast&lt;QAbstractProxyModel*&gt;(%1)">
     <extra-includes>
       <include file-name="QItemSelection" location="global"/>
diff --git a/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp b/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
index 5a2f75f31..ee1b690b7 100644
--- a/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
+++ b/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
@@ -187,10 +187,9 @@ static QString msgNoFunctionForModification(const QString &signature,
 
 void AbstractMetaBuilderPrivate::checkFunctionModifications()
 {
-    TypeDatabase *types = TypeDatabase::instance();
-    const SingleTypeEntryHash entryHash = types->entries();
+    const auto &entries = TypeDatabase::instance()->entries();
 
-    for (SingleTypeEntryHash::const_iterator it = entryHash.cbegin(), end = entryHash.cend(); it != end; ++it) {
+    for (auto it = entries.cbegin(), end = entries.cend(); it != end; ++it) {
         const TypeEntry *entry = it.value();
         if (!entry)
             continue;
@@ -580,13 +579,11 @@ void AbstractMetaBuilderPrivate::traverseDom(const FileModelItem &dom)
         if (cls->isAbstract() && !cls->isInterface())
             cls->typeEntry()->setLookupName(cls->typeEntry()->targetLangName() + QLatin1String("$ConcreteWrapper"));
     }
-    const TypeEntryHash allEntries = types->allEntries();
+    const auto &allEntries = types->entries();
     ReportHandler::progress(QLatin1String("Detecting inconsistencies in typesystem..."));
-    for (TypeEntryHash::const_iterator it = allEntries.cbegin(), end = allEntries.cend(); it != end; ++it) {
-        for (TypeEntry *entry : it.value()) {
-            if (entry->isPrimitive())
-                continue;
-
+    for (auto it = allEntries.cbegin(), end = allEntries.cend(); it != end; ++it) {
+        TypeEntry *entry = it.value();
+        if (!entry->isPrimitive()) {
             if ((entry->isValue() || entry->isObject())
                 && !entry->isString()
                 && !entry->isChar()
@@ -2183,8 +2180,8 @@ AbstractMetaType *AbstractMetaBuilderPrivate::translateType(const AddedFunction:
 
     if (!type) {
         QStringList candidates;
-        SingleTypeEntryHash entries = typeDb->entries();
-        for (SingleTypeEntryHash::const_iterator it = entries.cbegin(), end = entries.cend(); it != end; ++it) {
+        const auto &entries = typeDb->entries();
+        for (auto it = entries.cbegin(), end = entries.cend(); it != end; ++it) {
             // Let's try to find the type in different scopes.
             if (it.key().endsWith(colonColon() + typeName))
                 candidates.append(it.key());
diff --git a/sources/shiboken2/ApiExtractor/typedatabase.cpp b/sources/shiboken2/ApiExtractor/typedatabase.cpp
index f6072ea1b..88d7d6956 100644
--- a/sources/shiboken2/ApiExtractor/typedatabase.cpp
+++ b/sources/shiboken2/ApiExtractor/typedatabase.cpp
@@ -166,64 +166,69 @@ ContainerTypeEntry* TypeDatabase::findContainerType(const QString &name) const
     return 0;
 }
 
-FunctionTypeEntry* TypeDatabase::findFunctionType(const QString& name) const
+static bool inline useType(const TypeEntry *t)
 {
-    TypeEntry* entry = findType(name);
-    if (entry && entry->type() == TypeEntry::FunctionType)
-        return static_cast<FunctionTypeEntry*>(entry);
-    return 0;
+    return !t->isPrimitive()
+        || static_cast<const PrimitiveTypeEntry *>(t)->preferredTargetLangType();
 }
 
-TypeEntry* TypeDatabase::findType(const QString& name) const
+FunctionTypeEntry* TypeDatabase::findFunctionType(const QString& name) const
 {
-    const TypeEntryList &entries = findTypes(name);
+    const auto entries = findTypes(name);
     for (TypeEntry *entry : entries) {
-        if (entry &&
-            (!entry->isPrimitive() || static_cast<PrimitiveTypeEntry *>(entry)->preferredTargetLangType())) {
-            return entry;
-        }
+        if (entry->type() == TypeEntry::FunctionType && useType(entry))
+            return static_cast<FunctionTypeEntry*>(entry);
     }
     return 0;
 }
 
-TypeEntryList TypeDatabase::findTypes(const QString &name) const
+const TypeSystemTypeEntry *TypeDatabase::findTypeSystemType(const QString &name) const
 {
-    return m_entries.value(name);
+    const auto entries = findTypes(name);
+    for (const TypeEntry *entry : entries) {
+        if (entry->type() == TypeEntry::TypeSystemType)
+            return static_cast<const TypeSystemTypeEntry *>(entry);
+    }
+    return nullptr;
 }
 
-SingleTypeEntryHash TypeDatabase::entries() const
+TypeEntry* TypeDatabase::findType(const QString& name) const
 {
-    TypeEntryHash entries = allEntries();
-
-    SingleTypeEntryHash returned;
-    for (TypeEntryHash::const_iterator it = entries.cbegin(), end = entries.cend(); it != end; ++it)
-        returned.insert(it.key(), findType(it.key()));
+    const auto entries = findTypes(name);
+    for (TypeEntry *entry : entries) {
+        if (useType(entry))
+            return entry;
+    }
+    return nullptr;
+}
 
-    return returned;
+TypeEntryMultiMapConstIteratorRange TypeDatabase::findTypes(const QString &name) const
+{
+    const auto lower = m_entries.lowerBound(name);
+    const auto end = m_entries.constEnd();
+    return lower != end && lower.key() == name
+        ? TypeEntryMultiMapConstIteratorRange{lower, m_entries.upperBound(name)}
+        : TypeEntryMultiMapConstIteratorRange{end, end};
 }
 
 PrimitiveTypeEntryList TypeDatabase::primitiveTypes() const
 {
-    TypeEntryHash entries = allEntries();
     PrimitiveTypeEntryList returned;
-    for (TypeEntryHash::const_iterator it = entries.cbegin(), end = entries.cend(); it != end; ++it) {
-        for (TypeEntry *typeEntry : it.value()) {
-            if (typeEntry->isPrimitive())
-                returned.append(static_cast<PrimitiveTypeEntry *>(typeEntry));
-        }
+    for (auto it = m_entries.cbegin(), end = m_entries.cend(); it != end; ++it) {
+        TypeEntry *typeEntry = it.value();
+        if (typeEntry->isPrimitive())
+            returned.append(static_cast<PrimitiveTypeEntry *>(typeEntry));
     }
     return returned;
 }
 
 ContainerTypeEntryList TypeDatabase::containerTypes() const
 {
-    TypeEntryHash entries = allEntries();
     ContainerTypeEntryList returned;
-    for (TypeEntryHash::const_iterator it = entries.cbegin(), end = entries.cend(); it != end; ++it) {
-        for (TypeEntry *typeEntry : it.value()) {
-            if (typeEntry->isContainer())
-                returned.append(static_cast<ContainerTypeEntry *>(typeEntry));
-        }
+    for (auto it = m_entries.cbegin(), end = m_entries.cend(); it != end; ++it) {
+        TypeEntry *typeEntry = it.value();
+        if (typeEntry->isContainer())
+            returned.append(static_cast<ContainerTypeEntry *>(typeEntry));
     }
     return returned;
 }
@@ -307,7 +312,7 @@ bool TypeDatabase::isEnumRejected(const QString& className, const QString& enumN
 
 void TypeDatabase::addType(TypeEntry *e)
 {
-    m_entries[e->qualifiedCppName()].append(e);
+    m_entries.insert(e->qualifiedCppName(), e);
 }
 
 bool TypeDatabase::isFunctionRejected(const QString& className, const QString& functionName,
@@ -341,7 +346,7 @@ FlagsTypeEntry* TypeDatabase::findFlagsType(const QString &name) const
         fte = m_flagsEntries.value(name);
         if (!fte) {
             //last hope, search for flag without scope  inside of flags hash
-            for (SingleTypeEntryHash::const_iterator it = m_flagsEntries.cbegin(), end = m_flagsEntries.cend(); it != end; ++it) {
+            for (auto it = m_flagsEntries.cbegin(), end = m_flagsEntries.cend(); it != end; ++it) {
                 if (it.key().endsWith(name)) {
                     fte = it.value();
                     break;
@@ -528,11 +533,13 @@ bool TypeDatabase::parseFile(QIODevice* device, bool generate)
 
 PrimitiveTypeEntry *TypeDatabase::findPrimitiveType(const QString& name) const
 {
-    const TypeEntryList &entries = findTypes(name);
-
+    const auto entries = findTypes(name);
     for (TypeEntry *entry : entries) {
-        if (entry && entry->isPrimitive() && static_cast<PrimitiveTypeEntry*>(entry)->preferredTargetLangType())
-            return static_cast<PrimitiveTypeEntry*>(entry);
+        if (entry->isPrimitive()) {
+            PrimitiveTypeEntry *pe = static_cast<PrimitiveTypeEntry *>(entry);
+            if (pe->preferredTargetLangType())
+                return pe;
+        }
     }
 
     return 0;
@@ -540,9 +547,9 @@ PrimitiveTypeEntry *TypeDatabase::findPrimitiveType(const QString& name) const
 
 ComplexTypeEntry* TypeDatabase::findComplexType(const QString& name) const
 {
-    const TypeEntryList &entries = findTypes(name);
+    const auto entries = findTypes(name);
     for (TypeEntry *entry : entries) {
-        if (entry && entry->isComplex())
+        if (entry->isComplex() && useType(entry))
             return static_cast<ComplexTypeEntry*>(entry);
     }
     return 0;
@@ -550,9 +557,9 @@ ComplexTypeEntry* TypeDatabase::findComplexType(const QString& name) const
 
 ObjectTypeEntry* TypeDatabase::findObjectType(const QString& name) const
 {
-    const TypeEntryList &entries = findTypes(name);
+    const auto entries = findTypes(name);
     for (TypeEntry *entry : entries) {
-        if (entry && entry->isObject())
+        if (entry && entry->isObject() && useType(entry))
             return static_cast<ObjectTypeEntry*>(entry);
     }
     return 0;
@@ -560,9 +567,9 @@ ObjectTypeEntry* TypeDatabase::findObjectType(const QString& name) const
 
 NamespaceTypeEntry* TypeDatabase::findNamespaceType(const QString& name) const
 {
-    const TypeEntryList &entries = findTypes(name);
+    const auto entries = findTypes(name);
     for (TypeEntry *entry : entries) {
-        if (entry && entry->isNamespace())
+        if (entry->isNamespace() && useType(entry))
             return static_cast<NamespaceTypeEntry*>(entry);
     }
     return 0;
@@ -593,29 +600,26 @@ static bool typeEntryLessThan(const TypeEntry* t1, const TypeEntry* t2)
 static void _computeTypeIndexes()
 {
     TypeDatabase* tdb = TypeDatabase::instance();
-    typedef QMap<int, TypeEntryList> GroupedTypeEntries;
-    GroupedTypeEntries groupedEntries;
 
     TypeEntryList list;
 
     // Group type entries by revision numbers
-    const TypeEntryHash &allEntries = tdb->allEntries();
+    const auto &allEntries = tdb->entries();
     list.reserve(allEntries.size());
-    for (TypeEntryHash::const_iterator tit = allEntries.cbegin(), end = allEntries.cend(); tit != end; ++tit) {
-        for (TypeEntry *entry : tit.value()) {
-            if (entry->isPrimitive()
-                || entry->isContainer()
-                || entry->isFunction()
-                || !entry->generateCode()
-                || entry->isEnumValue()
-                || entry->isVarargs()
-                || entry->isTypeSystem()
-                || entry->isVoid()
-                || entry->isCustom())
-                continue;
-            if (!list.contains(entry)) // Remove duplicates
-                list.append(entry);
-        }
+    for (auto  tit = allEntries.cbegin(), end = allEntries.cend(); tit != end; ++tit) {
+        TypeEntry *entry = tit.value();
+        if (entry->isPrimitive()
+            || entry->isContainer()
+            || entry->isFunction()
+            || !entry->generateCode()
+            || entry->isEnumValue()
+            || entry->isVarargs()
+            || entry->isTypeSystem()
+            || entry->isVoid()
+            || entry->isCustom())
+            continue;
+        if (!list.contains(entry)) // Remove duplicates
+            list.append(entry);
     }
 
     // Sort the type entries by revision, name
@@ -797,25 +801,14 @@ QDebug operator<<(QDebug d, const TemplateEntry *te)
 
 void TypeDatabase::formatDebug(QDebug &d) const
 {
-    typedef TypeEntryHash::ConstIterator Eit;
-    typedef SingleTypeEntryHash::ConstIterator Sit;
-    typedef TemplateEntryHash::ConstIterator TplIt;
     d << "TypeDatabase("
       << "entries[" << m_entries.size() << "]=";
-    for (Eit it = m_entries.cbegin(), end = m_entries.cend(); it != end; ++it) {
-        const int count = it.value().size();
-        d << '"' << it.key() << "\" [" << count << "]: (";
-        for (int t = 0; t < count; ++t) {
-            if (t)
-                d << ", ";
-            d << it.value().at(t);
-        }
-        d << ")\n";
-    }
+    for (auto it = m_entries.cbegin(), end = m_entries.cend(); it != end; ++it)
+        d << "  " << it.value() << '\n';
     if (!m_templates.isEmpty()) {
         d << "templates[" << m_templates.size() << "]=(";
-        const TplIt begin = m_templates.cbegin();
-        for (TplIt it = begin, end = m_templates.cend(); it != end; ++it) {
+        const auto begin = m_templates.cbegin();
+        for (auto  it = begin, end = m_templates.cend(); it != end; ++it) {
             if (it != begin)
                 d << ", ";
             d << it.value();
@@ -824,8 +817,8 @@ void TypeDatabase::formatDebug(QDebug &d) const
     }
     if (!m_flagsEntries.isEmpty()) {
         d << "flags[" << m_flagsEntries.size() << "]=(";
-        const Sit begin = m_flagsEntries.cbegin();
-        for (Sit it = begin, end = m_flagsEntries.cend(); it != end; ++it) {
+        const auto begin = m_flagsEntries.cbegin();
+        for (auto it = begin, end = m_flagsEntries.cend(); it != end; ++it) {
             if (it != begin)
                 d << ", ";
             d << it.value();
diff --git a/sources/shiboken2/ApiExtractor/typedatabase.h b/sources/shiboken2/ApiExtractor/typedatabase.h
index 3664d76b7..b37efedc8 100644
--- a/sources/shiboken2/ApiExtractor/typedatabase.h
+++ b/sources/shiboken2/ApiExtractor/typedatabase.h
@@ -58,6 +58,8 @@ int getMaxTypeIndex();
 
 class ContainerTypeEntry;
 class PrimitiveTypeEntry;
+class TypeSystemTypeEntry;
+
 class TypeDatabase
 {
     TypeDatabase();
@@ -88,12 +90,11 @@ public:
     NamespaceTypeEntry* findNamespaceType(const QString& name) const;
     ContainerTypeEntry* findContainerType(const QString& name) const;
     FunctionTypeEntry* findFunctionType(const QString& name) const;
+    const TypeSystemTypeEntry *findTypeSystemType(const QString &name) const;
 
     TypeEntry* findType(const QString& name) const;
 
-    TypeEntryHash allEntries() const { return m_entries; }
-
-    SingleTypeEntryHash entries() const;
+    const TypeEntryMultiMap &entries() const { return m_entries; }
 
     PrimitiveTypeEntryList primitiveTypes() const;
 
@@ -160,12 +161,12 @@ public:
     void formatDebug(QDebug &d) const;
 #endif
 private:
-    TypeEntryList findTypes(const QString &name) const;
+    TypeEntryMultiMapConstIteratorRange findTypes(const QString &name) const;
 
     bool m_suppressWarnings;
-    TypeEntryHash m_entries;
-    SingleTypeEntryHash m_flagsEntries;
-    TemplateEntryHash m_templates;
+    TypeEntryMultiMap m_entries;
+    TypeEntryMap m_flagsEntries;
+    TemplateEntryMap m_templates;
     QVector<QRegularExpression> m_suppressedWarnings;
 
     AddedFunctionList m_globalUserFunctions;
diff --git a/sources/shiboken2/ApiExtractor/typedatabase_typedefs.h b/sources/shiboken2/ApiExtractor/typedatabase_typedefs.h
index 083602322..8d3862d9d 100644
--- a/sources/shiboken2/ApiExtractor/typedatabase_typedefs.h
+++ b/sources/shiboken2/ApiExtractor/typedatabase_typedefs.h
@@ -29,7 +29,7 @@
 #ifndef TYPEDATABASE_TYPEDEFS_H
 #define TYPEDATABASE_TYPEDEFS_H
 
-#include <QtCore/QHash>
+#include <QtCore/QMultiMap>
 #include <QtCore/QString>
 #include <QtCore/QVector>
 
@@ -39,9 +39,24 @@ class TemplateEntry;
 class TypeEntry;
 
 typedef QVector<TypeEntry *> TypeEntryList;
-typedef QHash<QString, TypeEntryList> TypeEntryHash;
-typedef QHash<QString, TypeEntry *> SingleTypeEntryHash;
-typedef QHash<QString, TemplateEntry *> TemplateEntryHash;
+typedef QMap<QString, TemplateEntry *> TemplateEntryMap;
+
+template <class Key, class Value>
+struct QMultiMapConstIteratorRange // A range of iterator for a range-based for loop
+{
+    using ConstIterator = typename QMultiMap<Key, Value>::const_iterator;
+
+    ConstIterator begin() const { return m_begin; }
+    ConstIterator end() const { return m_end; }
+
+    ConstIterator m_begin;
+    ConstIterator m_end;
+};
+
+typedef QMultiMap<QString, TypeEntry *> TypeEntryMultiMap;
+typedef QMultiMapConstIteratorRange<QString, TypeEntry *> TypeEntryMultiMapConstIteratorRange;
+
+typedef QMap<QString, TypeEntry *> TypeEntryMap;
 
 typedef QVector<const ContainerTypeEntry *> ContainerTypeEntryList;
 typedef QVector<const PrimitiveTypeEntry *> PrimitiveTypeEntryList;
diff --git a/sources/shiboken2/generator/generator.cpp b/sources/shiboken2/generator/generator.cpp
index 63700f2c5..7cf93edc5 100644
--- a/sources/shiboken2/generator/generator.cpp
+++ b/sources/shiboken2/generator/generator.cpp
@@ -66,17 +66,14 @@ Generator::~Generator()
 bool Generator::setup(const ApiExtractor& extractor)
 {
     m_d->apiextractor = &extractor;
-    TypeEntryHash allEntries = TypeDatabase::instance()->allEntries();
+    const auto &allEntries = TypeDatabase::instance()->entries();
     TypeEntry* entryFound = 0;
-    for (TypeEntryHash::const_iterator it = allEntries.cbegin(), end = allEntries.cend(); it != end; ++it) {
-        for (TypeEntry *entry : it.value()) {
-            if (entry->type() == TypeEntry::TypeSystemType && entry->generateCode()) {
-                entryFound = entry;
-                break;
-            }
-        }
-        if (entryFound)
+    for (auto it = allEntries.cbegin(), end = allEntries.cend(); it != end; ++it) {
+        TypeEntry *entry = it.value();
+        if (entry->type() == TypeEntry::TypeSystemType && entry->generateCode()) {
+            entryFound = entry;
             break;
+        }
     }
     if (entryFound)
         m_d->packageName = entryFound->name();
diff --git a/sources/shiboken2/generator/shiboken2/cppgenerator.cpp b/sources/shiboken2/generator/shiboken2/cppgenerator.cpp
index f230782d1..455b77c6e 100644
--- a/sources/shiboken2/generator/shiboken2/cppgenerator.cpp
+++ b/sources/shiboken2/generator/shiboken2/cppgenerator.cpp
@@ -5332,13 +5332,12 @@ bool CppGenerator::finishGeneration()
     }
 
     TypeDatabase* typeDb = TypeDatabase::instance();
-    TypeSystemTypeEntry* moduleEntry = static_cast<TypeSystemTypeEntry*>(typeDb->findType(packageName()));
+    const TypeSystemTypeEntry *moduleEntry = typeDb->findTypeSystemType(packageName());
+    Q_ASSERT(moduleEntry);
 
     //Extra includes
     s << endl << "// Extra includes" << endl;
-    QVector<Include> extraIncludes;
-    if (moduleEntry)
-        extraIncludes = moduleEntry->extraIncludes();
+    QVector<Include> extraIncludes = moduleEntry->extraIncludes();
     for (AbstractMetaEnum *cppEnum : qAsConst(globalEnums))
         extraIncludes.append(cppEnum->typeEntry()->extraIncludes());
     qSort(extraIncludes.begin(), extraIncludes.end());
@@ -5352,9 +5351,7 @@ bool CppGenerator::finishGeneration()
     s << "// Current module's converter array." << endl;
     s << "SbkConverter** " << convertersVariableName() << ';' << endl;
 
-    CodeSnipList snips;
-    if (moduleEntry)
-        snips = moduleEntry->codeSnips();
+    const CodeSnipList snips = moduleEntry->codeSnips();
 
     // module inject-code native/beginning
     if (!snips.isEmpty()) {
diff --git a/sources/shiboken2/generator/shiboken2/shibokengenerator.cpp b/sources/shiboken2/generator/shiboken2/shibokengenerator.cpp
index 16f5fafd3..a03c57e98 100644
--- a/sources/shiboken2/generator/shiboken2/shibokengenerator.cpp
+++ b/sources/shiboken2/generator/shiboken2/shibokengenerator.cpp
@@ -2483,7 +2483,11 @@ bool ShibokenGenerator::doSetup()
     const AbstractMetaClassList &classList = classes();
     for (const AbstractMetaClass *metaClass : classList)
         getCode(snips, metaClass->typeEntry());
-    getCode(snips, td->findType(packageName()));
+
+    const TypeSystemTypeEntry *moduleEntry = td->findTypeSystemType(packageName());
+    Q_ASSERT(moduleEntry);
+    getCode(snips, moduleEntry);
+
     const FunctionGroupMap &functionGroups = getFunctionGroups();
     for (FunctionGroupMapIt it = functionGroups.cbegin(), end = functionGroups.cend(); it != end; ++it) {
         for (AbstractMetaFunction *func : it.value())