qmlimportscanner: Improve performance using caches continued

Cache module details (plugin path, components, etc) for each
processed module.
Cache recursive dependency module details for each processed
module.
Skip self dependencies.
Discard duplicates when merging module details.

Use a custom hasher object to store QVariantMaps in
std::unordered_set / std::unordered_map because QVariant does not
provide a qHash overload.

With the improvements above, for a project that has 100 qml files,
each importing QtQuick.Controls and QtQuick as many times
as the file index (file 100 imports QtQuick and Controls 100 times),
the execution time is reduced ~7x times.

Before 1.52s user 0.22s system 99% cpu 1.741 total
After  0.22s user 0.03s system 97% cpu 0.248 total

For the examples/quickcontrols2/gallery project, the stats are

Before 0.81s user 0.13s system 96% cpu 0.968 total debug
After  0.17s user 0.03s system 75% cpu 0.266 total debug
Before 0.15s user 0.09s system 95% cpu 0.251 total release
After  0.05s user 0.03s system 54% cpu 0.138 total release

That's a ~5x improvement for a debug build of qmlimportscanner
and a ~3x improvement for a release build of qmlimportscanner.

Benched on a 16" Intel macbook pro 2019 with a USB SSD.

Fixes: QTBUG-103187
Change-Id: I730d762ff99b52918568fdf119eb68201a7d6c4a
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
(cherry picked from commit 2ee7ec4d2411d29c4ca4540cc107146e05450b7f)
Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>

1 files changed, 168 insertions, 48 deletions

diff --git a/tools/qmlimportscanner/main.cpp b/tools/qmlimportscanner/main.cpp
index e28419aea1..755542fe23 100644
--- a/tools/qmlimportscanner/main.cpp
+++ b/tools/qmlimportscanner/main.cpp
@@ -54,6 +54,8 @@
 
 #include <iostream>
 #include <algorithm>
+#include <unordered_map>
+#include <unordered_set>
 
 QT_USE_NAMESPACE
 
@@ -342,62 +344,178 @@ QPair<QString, QString> resolveImportPath(const QString &uri, const QString &ver
     return candidate;
 }
 
-// Find absolute file system paths and plugins for a list of modules.
-QVariantList findPathsForModuleImports(
-        const QVariantList &imports,
+// Provides a hasher for module details stored in a QVariantMap disguised as a QVariant..
+// Only supports a subset of types.
+struct ImportVariantHasher {
+   std::size_t operator()(const QVariant &importVariant) const
+   {
+       size_t computedHash = 0;
+       QVariantMap importMap = qvariant_cast<QVariantMap>(importVariant);
+       for (auto it = importMap.constKeyValueBegin(); it != importMap.constKeyValueEnd(); ++it) {
+           const QString &key = it->first;
+           const QVariant &value = it->second;
+
+           if (!value.isValid() || value.isNull()) {
+               computedHash = qHashMulti(computedHash, key, 0);
+               continue;
+           }
+
+           const auto valueTypeId = value.typeId();
+           switch (valueTypeId) {
+           case QMetaType::QString:
+               computedHash = qHashMulti(computedHash, key, value.toString());
+               break;
+           case QMetaType::Bool:
+               computedHash = qHashMulti(computedHash, key, value.toBool());
+               break;
+           case QMetaType::QStringList:
+               computedHash = qHashMulti(computedHash, key, value.toStringList());
+               break;
+           default:
+               Q_ASSERT_X(valueTypeId, "ImportVariantHasher", "Invalid variant type detected");
+               break;
+           }
+       }
+
+       return computedHash;
+   }
+};
+
+using ImportDetailsAndDeps = QPair<QVariantMap, QStringList>;
+
+// Returns the import information as it will be written out to the json / .cmake file.
+// The dependencies are not stored in the same QVariantMap because we don't currently need that
+// information in the output file.
+ImportDetailsAndDeps
+getImportDetails(const QVariant &inputImport,
+                 FileImportsWithoutDepsCache &fileImportsWithoutDepsCache) {
+
+    using Cache = std::unordered_map<QVariant, ImportDetailsAndDeps, ImportVariantHasher>;
+    static Cache cache;
+
+    const Cache::const_iterator it = cache.find(inputImport);
+    if (it != cache.end()) {
+        return it->second;
+    }
+
+    QVariantMap import = qvariant_cast<QVariantMap>(inputImport);
+    QStringList dependencies;
+    if (import.value(typeLiteral()) == moduleLiteral()) {
+        const QString version = import.value(versionLiteral()).toString();
+        const QPair<QString, QString> paths =
+            resolveImportPath(import.value(nameLiteral()).toString(), version);
+        QVariantMap plugininfo;
+        if (!paths.first.isEmpty()) {
+            import.insert(pathLiteral(), paths.first);
+            import.insert(relativePathLiteral(), paths.second);
+            plugininfo = pluginsForModulePath(paths.first,
+                                              version,
+                                              fileImportsWithoutDepsCache);
+        }
+        QString linkTarget = plugininfo.value(linkTargetLiteral()).toString();
+        QString plugins = plugininfo.value(pluginsLiteral()).toString();
+        bool isOptional = plugininfo.value(pluginIsOptionalLiteral(), QVariant(false)).toBool();
+        QString classnames = plugininfo.value(classnamesLiteral()).toString();
+        if (!linkTarget.isEmpty())
+            import.insert(linkTargetLiteral(), linkTarget);
+        if (!plugins.isEmpty())
+            import.insert(QStringLiteral("plugin"), plugins);
+        if (isOptional)
+            import.insert(pluginIsOptionalLiteral(), true);
+        if (!classnames.isEmpty())
+            import.insert(QStringLiteral("classname"), classnames);
+        if (plugininfo.contains(dependenciesLiteral())) {
+            dependencies = plugininfo.value(dependenciesLiteral()).toStringList();
+        }
+    }
+    import.remove(versionLiteral());
+
+    const ImportDetailsAndDeps result = {import, dependencies};
+    cache.insert({inputImport, result});
+    return result;
+}
+
+// Parse a dependency string line into a QVariantMap, to be used as a key when processing imports
+// in getGetDetailedModuleImportsIncludingDependencies.
+QVariantMap dependencyStringToImport(const QString &line) {
+    const auto dep = QStringView{line}.split(QLatin1Char(' '), Qt::SkipEmptyParts);
+    const QString name = dep[0].toString();
+    QVariantMap depImport;
+    depImport[typeLiteral()] = moduleLiteral();
+    depImport[nameLiteral()] = name;
+    if (dep.length() > 1)
+        depImport[versionLiteral()] = dep[1].toString();
+    return depImport;
+}
+
+// Returns details of given input import and its recursive module dependencies.
+// The details include absolute file system paths for the the module plugin, components,
+// etc.
+// An internal cache is used to prevent repeated computation for the same input module.
+QVariantList getGetDetailedModuleImportsIncludingDependencies(
+        const QVariant &inputImport,
         FileImportsWithoutDepsCache &fileImportsWithoutDepsCache)
 {
+    using Cache = std::unordered_map<QVariant, QVariantList, ImportVariantHasher>;
+    static Cache importsCacheWithDeps;
+
+    const Cache::const_iterator it = importsCacheWithDeps.find(inputImport);
+    if (it != importsCacheWithDeps.end()) {
+        return it->second;
+    }
+
     QVariantList done;
-    QVariantList importsCopy(imports);
-
-    for (int i = 0; i < importsCopy.length(); ++i) {
-        QVariantMap import = qvariant_cast<QVariantMap>(importsCopy.at(i));
-        if (import.value(typeLiteral()) == moduleLiteral()) {
-            const QString version = import.value(versionLiteral()).toString();
-            const QPair<QString, QString> paths =
-                resolveImportPath(import.value(nameLiteral()).toString(), version);
-            QVariantMap plugininfo;
-            if (!paths.first.isEmpty()) {
-                import.insert(pathLiteral(), paths.first);
-                import.insert(relativePathLiteral(), paths.second);
-                plugininfo = pluginsForModulePath(paths.first,
-                                                  version,
-                                                  fileImportsWithoutDepsCache);
-            }
-            QString linkTarget = plugininfo.value(linkTargetLiteral()).toString();
-            QString plugins = plugininfo.value(pluginsLiteral()).toString();
-            bool isOptional = plugininfo.value(pluginIsOptionalLiteral(), QVariant(false)).toBool();
-            QString classnames = plugininfo.value(classnamesLiteral()).toString();
-            if (!linkTarget.isEmpty())
-                import.insert(linkTargetLiteral(), linkTarget);
-            if (!plugins.isEmpty())
-                import.insert(QStringLiteral("plugin"), plugins);
-            if (isOptional)
-                import.insert(pluginIsOptionalLiteral(), true);
-            if (!classnames.isEmpty())
-                import.insert(QStringLiteral("classname"), classnames);
-            if (plugininfo.contains(dependenciesLiteral())) {
-                const QStringList dependencies = plugininfo.value(dependenciesLiteral()).toStringList();
-                for (const QString &line : dependencies) {
-                    const auto dep = QStringView{line}.split(QLatin1Char(' '), Qt::SkipEmptyParts);
-                    const QString name = dep[0].toString();
-                    QVariantMap depImport;
-                    depImport[typeLiteral()] = moduleLiteral();
-                    depImport[nameLiteral()] = name;
-                    if (dep.length() > 1)
-                        depImport[versionLiteral()] = dep[1].toString();
-
-                    if (!importsCopy.contains(depImport))
-                        importsCopy.append(depImport);
+    QVariantList importsToProcess;
+    std::unordered_set<QVariant, ImportVariantHasher> importsSeen;
+    importsToProcess.append(inputImport);
+
+    for (int i = 0; i < importsToProcess.length(); ++i) {
+        const QVariant importToProcess = importsToProcess.at(i);
+        auto [details, deps] = getImportDetails(importToProcess, fileImportsWithoutDepsCache);
+        if (details.value(typeLiteral()) == moduleLiteral()) {
+            for (const QString &line : deps) {
+                const QVariantMap depImport = dependencyStringToImport(line);
+
+                // Skip self-dependencies.
+                if (depImport == importToProcess)
+                    continue;
+
+                if (importsSeen.find(depImport) == importsSeen.end()) {
+                    importsToProcess.append(depImport);
+                    importsSeen.insert(depImport);
                 }
             }
         }
-        import.remove(versionLiteral());
-        done.append(import);
+        done.append(details);
     }
+
+    importsCacheWithDeps.insert({inputImport, done});
     return done;
 }
 
+QVariantList mergeImports(const QVariantList &a, const QVariantList &b);
+
+// Returns details of given input imports and their recursive module dependencies.
+QVariantList getGetDetailedModuleImportsIncludingDependencies(
+        const QVariantList &inputImports,
+        FileImportsWithoutDepsCache &fileImportsWithoutDepsCache)
+{
+    QVariantList result;
+
+    // Get rid of duplicates in input module list.
+    QVariantList inputImportsCopy;
+    inputImportsCopy = mergeImports(inputImportsCopy, inputImports);
+
+    // Collect recursive dependencies for each input module and merge into result, discarding
+    // duplicates.
+    for (auto it = inputImportsCopy.begin(); it != inputImportsCopy.end(); ++it) {
+        QVariantList imports = getGetDetailedModuleImportsIncludingDependencies(
+                    *it, fileImportsWithoutDepsCache);
+        result = mergeImports(result, imports);
+    }
+    return result;
+}
+
 // Scan a single qml file for import statements
 QVariantList findQmlImportsInQmlCode(const QString &filePath, const QString &code)
 {
@@ -544,8 +662,8 @@ QVariantList findQmlImportsInFile(const QString &filePath,
 
     qCDebug(lcImportScanner) << "Finding module paths for imported modules in" << filePath
                              << "TS:" << pathsTimeBegin.toMSecsSinceEpoch();
-    QVariantList importPaths = findPathsForModuleImports(imports,
-                                                         fileImportsWithoutDepsCache);
+    QVariantList importPaths = getGetDetailedModuleImportsIncludingDependencies(
+                imports, fileImportsWithoutDepsCache);
 
     const auto pathsTimeEnd = QDateTime::currentDateTime();
     const auto duration = pathsTimeBegin.msecsTo(pathsTimeEnd);
@@ -558,6 +676,8 @@ QVariantList findQmlImportsInFile(const QString &filePath,
 }
 
 // Merge two lists of imports, discard duplicates.
+// Empirical tests show that for a small amount of values, the n^2 QVariantList comparison
+// is still faster than using an unordered_set + hashing a complex QVariantMap.
 QVariantList mergeImports(const QVariantList &a, const QVariantList &b)
 {
     QVariantList merged = a;