QIconLoader: Use the GTK+ icon caches

Loading icons is quite slow because we need to stat many files in many directories.
That's why gtk adds a cache in the icon theme directory so it avoids stating lots
of files.

The cache file can be generated with gtk-update-icon-cache utility on a theme
directory. If the cache is not present, corrupted, or outdated, the normal slow lookup
is still run.

[ChangeLog][QtGui][QIcon] fromTheme gained the ability to use the GTK icon cache
to speed up lookups.

Change-Id: I3ab8a9910be67a34034556023be61a86789a7893
Reviewed-by: David Faure <david.faure@kdab.com>

6 files changed, 234 insertions, 3 deletions

diff --git a/src/gui/image/qicon.cpp b/src/gui/image/qicon.cpp
index ee41efc3e7..7ae081adfb 100644
--- a/src/gui/image/qicon.cpp
+++ b/src/gui/image/qicon.cpp
@@ -1162,6 +1162,10 @@ QString QIcon::themeName()
     compliant theme in one of your themeSearchPaths() and set the
     appropriate themeName().
 
+    \note Qt will make use of GTK's icon-theme.cache if present to speed up
+    the lookup. These caches can be generated using gtk-update-icon-cache:
+    \l{https://developer.gnome.org/gtk3/stable/gtk-update-icon-cache.html}.
+
     \sa themeName(), setThemeName(), themeSearchPaths()
 */
 QIcon QIcon::fromTheme(const QString &name)
diff --git a/src/gui/image/qiconloader.cpp b/src/gui/image/qiconloader.cpp
index 3fd1f57ac4..ecce7f9967 100644
--- a/src/gui/image/qiconloader.cpp
+++ b/src/gui/image/qiconloader.cpp
@@ -155,6 +155,141 @@ QStringList QIconLoader::themeSearchPaths() const
     return m_iconDirs;
 }
 
+/*!
+    \class QIconCacheGtkReader
+    \internal
+    Helper class that reads and looks up into the icon-theme.cache generated with
+    gtk-update-icon-cache. If at any point we detect a corruption in the file
+    (because the offsets point at wrong locations for example), the reader
+    is marked as invalid.
+*/
+class QIconCacheGtkReader
+{
+public:
+    explicit QIconCacheGtkReader(const QString &themeDir);
+    QVector<const char *> lookup(const QString &);
+    bool isValid() const { return m_isValid; }
+private:
+    QFile m_file;
+    const unsigned char *m_data;
+    quint64 m_size;
+    bool m_isValid;
+
+    quint16 read16(uint offset)
+    {
+        if (offset > m_size - 2 || (offset & 0x1)) {
+            m_isValid = false;
+            return 0;
+        }
+        return m_data[offset+1] | m_data[offset] << 8;
+    }
+    quint32 read32(uint offset)
+    {
+        if (offset > m_size - 4 || (offset & 0x3)) {
+            m_isValid = false;
+            return 0;
+        }
+        return m_data[offset+3] | m_data[offset+2] << 8
+            | m_data[offset+1] << 16 | m_data[offset] << 24;
+    }
+};
+
+
+QIconCacheGtkReader::QIconCacheGtkReader(const QString &dirName)
+    : m_isValid(false)
+{
+    QFileInfo info(dirName + QLatin1Literal("/icon-theme.cache"));
+    if (!info.exists() || info.lastModified() < QFileInfo(dirName).lastModified())
+        return;
+    m_file.setFileName(info.absoluteFilePath());
+    if (!m_file.open(QFile::ReadOnly))
+        return;
+    m_size = m_file.size();
+    m_data = m_file.map(0, m_size);
+    if (!m_data)
+        return;
+    if (read16(0) != 1) // VERSION_MAJOR
+        return;
+
+    m_isValid = true;
+
+    // Check that all the directories are older than the cache
+    auto lastModified = info.lastModified();
+    quint32 dirListOffset = read32(8);
+    quint32 dirListLen = read32(dirListOffset);
+    for (uint i = 0; i < dirListLen; ++i) {
+        quint32 offset = read32(dirListOffset + 4 + 4 * i);
+        if (!m_isValid || offset >= m_size || lastModified < QFileInfo(dirName + QLatin1Char('/')
+                + QString::fromUtf8(reinterpret_cast<const char*>(m_data + offset))).lastModified()) {
+            m_isValid = false;
+            return;
+        }
+    }
+}
+
+static quint32 icon_name_hash(const char *p)
+{
+    quint32 h = static_cast<signed char>(*p);
+    for (p += 1; *p != '\0'; p++)
+        h = (h << 5) - h + *p;
+    return h;
+}
+
+/*! \internal
+    lookup the icon name and return the list of subdirectories in which an icon
+    with this name is present. The char* are pointers to the mapped data.
+    For example, this would return { "32x32/apps", "24x24/apps" , ... }
+ */
+QVector<const char *> QIconCacheGtkReader::lookup(const QString &name)
+{
+    QVector<const char *> ret;
+    if (!isValid())
+        return ret;
+
+    QByteArray nameUtf8 = name.toUtf8();
+    quint32 hash = icon_name_hash(nameUtf8);
+
+    quint32 hashOffset = read32(4);
+    quint32 hashBucketCount = read32(hashOffset);
+
+    if (!isValid() || hashBucketCount == 0) {
+        m_isValid = false;
+        return ret;
+    }
+
+    quint32 bucketIndex = hash % hashBucketCount;
+    quint32 bucketOffset = read32(hashOffset + 4 + bucketIndex * 4);
+    while (bucketOffset > 0 && bucketOffset <= m_size - 12) {
+        quint32 nameOff = read32(bucketOffset + 4);
+        if (nameOff < m_size && strcmp(reinterpret_cast<const char*>(m_data + nameOff), nameUtf8) == 0) {
+            quint32 dirListOffset = read32(8);
+            quint32 dirListLen = read32(dirListOffset);
+
+            quint32 listOffset = read32(bucketOffset+8);
+            quint32 listLen = read32(listOffset);
+
+            if (!m_isValid || listOffset + 4 + 8 * listLen > m_size) {
+                m_isValid = false;
+                return ret;
+            }
+
+            ret.reserve(listLen);
+            for (uint j = 0; j < listLen && m_isValid; ++j) {
+                quint32 dirIndex = read16(listOffset + 4 + 8 * j);
+                quint32 o = read32(dirListOffset + 4 + dirIndex*4);
+                if (!m_isValid || dirIndex >= dirListLen || o >= m_size) {
+                    m_isValid = false;
+                    return ret;
+                }
+                ret.append(reinterpret_cast<const char*>(m_data) + o);
+            }
+            return ret;
+        }
+        bucketOffset = read32(bucketOffset);
+    }
+    return ret;
+}
+
 QIconTheme::QIconTheme(const QString &themeName)
         : m_valid(false)
 {
@@ -166,8 +301,10 @@ QIconTheme::QIconTheme(const QString &themeName)
         QString themeDir = iconDir.path() + QLatin1Char('/') + themeName;
         QFileInfo themeDirInfo(themeDir);
 
-        if (themeDirInfo.isDir())
+        if (themeDirInfo.isDir()) {
             m_contentDirs << themeDir;
+            m_gtkCaches << QSharedPointer<QIconCacheGtkReader>::create(themeDir);
+        }
 
         if (!m_valid) {
             themeIndex.setFileName(themeDir + QLatin1String("/index.theme"));
@@ -257,7 +394,6 @@ QThemeIconInfo QIconLoader::findIconHelper(const QString &themeName,
     }
 
     const QStringList contentDirs = theme.contentDirs();
-    const QVector<QIconDirInfo> subDirs = theme.keyList();
 
     QString iconNameFallback = iconName;
 
@@ -268,6 +404,29 @@ QThemeIconInfo QIconLoader::findIconHelper(const QString &themeName,
 
         // Add all relevant files
         for (int i = 0; i < contentDirs.size(); ++i) {
+            QVector<QIconDirInfo> subDirs = theme.keyList();
+
+            // Try to reduce the amount of subDirs by looking in the GTK+ cache in order to save
+            // a massive amount of file stat (especially if the icon is not there)
+            auto cache = theme.m_gtkCaches.at(i);
+            if (cache->isValid()) {
+                auto result = cache->lookup(iconNameFallback);
+                if (cache->isValid()) {
+                    const QVector<QIconDirInfo> subDirsCopy = subDirs;
+                    subDirs.clear();
+                    subDirs.reserve(result.count());
+                    foreach (const char *s, result) {
+                        QString path = QString::fromUtf8(s);
+                        auto it = std::find_if(subDirsCopy.cbegin(), subDirsCopy.cend(),
+                                               [&](const QIconDirInfo &info) {
+                                                   return info.path == path; } );
+                        if (it != subDirsCopy.cend()) {
+                            subDirs.append(*it);
+                        }
+                    }
+                }
+            }
+
             QString contentDir = contentDirs.at(i) + QLatin1Char('/');
             for (int j = 0; j < subDirs.size() ; ++j) {
                 const QIconDirInfo &dirInfo = subDirs.at(j);
diff --git a/src/gui/image/qiconloader_p.h b/src/gui/image/qiconloader_p.h
index ccf0a9d438..193154e44e 100644
--- a/src/gui/image/qiconloader_p.h
+++ b/src/gui/image/qiconloader_p.h
@@ -139,6 +139,8 @@ private:
     friend class QIconLoader;
 };
 
+class QIconCacheGtkReader;
+
 class QIconTheme
 {
 public:
@@ -148,12 +150,13 @@ public:
     QVector<QIconDirInfo> keyList() { return m_keyList; }
     QStringList contentDirs() { return m_contentDirs; }
     bool isValid() { return m_valid; }
-
 private:
     QStringList m_contentDirs;
     QVector<QIconDirInfo> m_keyList;
     QStringList m_parents;
     bool m_valid;
+public:
+    QVector<QSharedPointer<QIconCacheGtkReader>> m_gtkCaches;
 };
 
 class Q_GUI_EXPORT QIconLoader
diff --git a/tests/auto/gui/image/qicon/icons/themeparent/icon-theme.cache b/tests/auto/gui/image/qicon/icons/themeparent/icon-theme.cache
new file mode 100644
index 0000000000..a323875989
--- /dev/null
+++ b/tests/auto/gui/image/qicon/icons/themeparent/icon-theme.cache
diff --git a/tests/auto/gui/image/qicon/tst_qicon.cpp b/tests/auto/gui/image/qicon/tst_qicon.cpp
index 9ed3873682..afa72f6922 100644
--- a/tests/auto/gui/image/qicon/tst_qicon.cpp
+++ b/tests/auto/gui/image/qicon/tst_qicon.cpp
@@ -63,6 +63,7 @@ private slots:
     void streamAvailableSizes_data();
     void streamAvailableSizes();
     void fromTheme();
+    void fromThemeCache();
 
 #ifndef QT_NO_WIDGETS
     void task184901_badCache();
@@ -633,6 +634,69 @@ void tst_QIcon::fromTheme()
     QVERIFY(abIcon.isNull());
 }
 
+void tst_QIcon::fromThemeCache()
+{
+    QTemporaryDir dir;
+    QVERIFY(QDir().mkpath(dir.path() + QLatin1String("/testcache/16x16/actions")));
+    QVERIFY(QFile(QStringLiteral(":/styles/commonstyle/images/standardbutton-open-16.png"))
+        .copy( dir.path() + QLatin1String("/testcache/16x16/actions/button-open.png")));
+
+    {
+        QFile index(dir.path() + QLatin1String("/testcache/index.theme"));
+        QVERIFY(index.open(QFile::WriteOnly));
+        index.write("[Icon Theme]\nDirectories=16x16/actions\n[16x16/actions]\nSize=16\nContext=Actions\nType=Fixed\n");
+    }
+    QIcon::setThemeSearchPaths(QStringList() << dir.path());
+    QIcon::setThemeName("testcache");
+
+    // We just created a theme with that icon, it must exist
+    QVERIFY(!QIcon::fromTheme("button-open").isNull());
+
+    QString cacheName = dir.path() + QLatin1String("/testcache/icon-theme.cache");
+
+    // An invalid cache should not prevent lookup
+    {
+        QFile cacheFile(cacheName);
+        QVERIFY(cacheFile.open(QFile::WriteOnly));
+        QDataStream(&cacheFile) << quint16(1) << quint16(0) << "invalid corrupted stuff in there\n";
+    }
+    QIcon::setThemeSearchPaths(QStringList() << dir.path()); // reload themes
+    QVERIFY(!QIcon::fromTheme("button-open").isNull());
+
+    // An empty cache should prevent the lookup
+    {
+        QFile cacheFile(cacheName);
+        QVERIFY(cacheFile.open(QFile::WriteOnly));
+        QDataStream ds(&cacheFile);
+        ds << quint16(1) << quint16(0); // 0: version
+        ds << quint32(12) << quint32(20); // 4: hash offset / dir list offset
+        ds << quint32(1) << quint32(0xffffffff); // 12: one empty bucket
+        ds << quint32(1) << quint32(28); // 20: list with one element
+        ds.writeRawData("16x16/actions", sizeof("16x16/actions")); // 28
+    }
+    QIcon::setThemeSearchPaths(QStringList() << dir.path()); // reload themes
+    QVERIFY(QIcon::fromTheme("button-open").isNull()); // The icon was not in the cache, it should not be found
+
+    // Adding an icon should be changing the modification date of one sub directory which should make the cache ignored
+    QTest::qWait(1000); // wait enough to have a different modification time in seconds
+    QVERIFY(QFile(QStringLiteral(":/styles/commonstyle/images/standardbutton-save-16.png"))
+        .copy(dir.path() + QLatin1String("/testcache/16x16/actions/button-save.png")));
+    QVERIFY(QFileInfo(cacheName).lastModified() < QFileInfo(dir.path() + QLatin1String("/testcache/16x16/actions")).lastModified());
+    QIcon::setThemeSearchPaths(QStringList() << dir.path()); // reload themes
+    QVERIFY(!QIcon::fromTheme("button-open").isNull());
+
+    // Try to run the actual gtk-update-icon-cache and make sure that icons are still found
+    QProcess process;
+    process.start(QStringLiteral("gtk-update-icon-cache"),
+                  QStringList() << QStringLiteral("-f") << QStringLiteral("-t") << (dir.path() + QLatin1String("/testcache")));
+    if (!process.waitForFinished())
+        QSKIP("gtk-update-icon-cache not run");
+    QVERIFY(QFileInfo(cacheName).lastModified() >= QFileInfo(dir.path() + QLatin1String("/testcache/16x16/actions")).lastModified());
+    QIcon::setThemeSearchPaths(QStringList() << dir.path()); // reload themes
+    QVERIFY(!QIcon::fromTheme("button-open").isNull());
+    QVERIFY(!QIcon::fromTheme("button-open-fallback").isNull());
+    QVERIFY(QIcon::fromTheme("notexist-fallback").isNull());
+}
 
 void tst_QIcon::task223279_inconsistentAddFile()
 {
diff --git a/tests/auto/gui/image/qicon/tst_qicon.qrc b/tests/auto/gui/image/qicon/tst_qicon.qrc
index 1505ca925b..3c8fbba7c2 100644
--- a/tests/auto/gui/image/qicon/tst_qicon.qrc
+++ b/tests/auto/gui/image/qicon/tst_qicon.qrc
@@ -15,6 +15,7 @@
 <file>./icons/themeparent/32x32/actions/address-book-new.png</file>
 <file>./icons/themeparent/32x32/actions/appointment-new.png</file>
 <file>./icons/themeparent/index.theme</file>
+<file>./icons/themeparent/icon-theme.cache</file>
 <file>./icons/themeparent/scalable/actions/address-book-new.svg</file>
 <file>./icons/themeparent/scalable/actions/appointment-new.svg</file>
 <file>./styles/commonstyle/images/standardbutton-open-16.png</file>