qmimeprovider.cpp

Go to the documentation of this file.

// Copyright (C) 2018 The Qt Company Ltd.
// Copyright (C) 2018 Klaralvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author David Faure <david.faure@kdab.com>
// Copyright (C) 2019 Intel Corporation.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:critical reason:data-parser
 
#include "qmimeprovider_p.h"
 
#include "qmimetypeparser_p.h"
#include <qstandardpaths.h>
#include "qmimemagicrulematcher_p.h"
 
#include <QXmlStreamReader>
#include <QBuffer>
#include <QDir>
#include <QFile>
#include <QByteArrayMatcher>
#include <QDebug>
#include <QDateTime>
#include <QtEndian>
 
#if QT_CONFIG(mimetype_database)
#  if defined(Q_CC_MSVC_ONLY)
#    pragma section(".qtmimedatabase", read, shared)
__declspec(allocate(".qtmimedatabase")) __declspec(align(4096))
#  elif defined(Q_OS_DARWIN)
__attribute__((section("__TEXT,.qtmimedatabase"), aligned(4096)))
#  elif (defined(Q_OF_ELF) || defined(Q_OS_WIN)) && defined(Q_CC_GNU)
__attribute__((section(".qtmimedatabase"), aligned(4096)))
#  endif
 
#  include "qmimeprovider_database.cpp"
 
#  ifdef MIME_DATABASE_IS_ZSTD
#    if !QT_CONFIG(zstd)
#      error "MIME database is zstd but no support compiled in!"
#    endif
#    include <zstd.h>
#  endif
#  ifdef MIME_DATABASE_IS_GZIP
#    ifdef QT_NO_COMPRESS
#      error "MIME database is zlib but no support compiled in!"
#    endif
#    define ZLIB_CONST
#    include <zconf.h>
#    include <zlib.h>
#  endif
#endif
 
QT_BEGIN_NAMESPACE
 
using namespace Qt::StringLiterals;
// Position of the "list offsets" values, at the beginning of the mime.cache file
enum {
    PosAliasListOffset = 4,
    PosParentListOffset = 8,
    PosLiteralListOffset = 12,
    PosReverseSuffixTreeOffset = 16,
    PosGlobListOffset = 20,
    PosMagicListOffset = 24,
    // PosNamespaceListOffset = 28,
    PosIconsListOffset = 32,
    PosGenericIconsListOffset = 36
};
 
// Size of one record of each of the lists, as defined by the mime.cache format
enum {
    AliasRecordSize = 8,
    ParentRecordSize = 8,
    GlobRecordSize = 12,
    IconRecordSize = 8,
    SuffixNodeSize = 12,
    MagicMatchSize = 16,
    MagicMatchletSize = 32
};
 
enum {
    PosFirstRootOffset = 4,
    PosFirstMatchOffset = 8
};
 
/*
   The depth limit protects the stack, but it does not limit the time. In a
   corrupt mime.cache, the child offset of a matchlet can point back to the
   list that contains it. For example, take a list of 2 matchlets where the
   children of each one are that same list. Each path still stops at
   MaxRecursionDepth, but there are 2^depth paths, and a file of a few
   hundred bytes is enough to describe them.
 
   So one findByMagic() or checkMagicRules() call also has a budget: the
   number of input data bytes it may scan, summed over all matchlets it
   checks. Each checked matchlet costs 1 + min(rangeLength, data.size())
   bytes: the input bytes it may compare, plus 1 so that no matchlet is free.
   When the budget is used up, the lookup stops and reports no match.
 
   Checking every matchlet in the shared-mime-info database costs about 76k
   bytes, so this limit is far above what a valid mime.cache needs.
 */
static constexpr qint64 MagicMatchBudget = 1 << 21;
 
/*
   A list of fixed-size records in the mime.cache file, whose bounds have been
   checked once: for any index below count, the whole record at
   recordOffset(index) is inside the file, so walking the list needs no further
   checking - read the fields with CacheFile::recordUint32(). An empty list
   means either a mime.cache is empty or corrupted.
 
   Anything reached by following an offset stored inside a record is still
   untrusted and has to be checked where it is used.
 */
class QMimeBinaryProvider::RecordList
{
public:
    // The lists whose offsets live in the first 40 bytes of the file are read
    // by these two functions, once, when the cache file is loaded.
    bool load(const CacheFile *cacheFile, quint64 posListOffset, quint32 stride);
    bool loadIndirect(const CacheFile *cacheFile, quint64 posListOffset,
                      quint64 firstRecordPos, quint32 stride);
 
    quint32 count() const { return m_count; } // N_ALIASES/N_ENTRIES/N_PARENTS/etc => CARD32 type
    quint32 stride() const { return m_stride; }
    quint64 firstRecord() const { return m_firstRecord; }
    quint64 recordOffset(quint32 index) const
    {
        Q_ASSERT(index < m_count);
        return m_firstRecord + quint64(index) * m_stride;
    }
 
private:
    // The state is private, and setRecords() is the only thing that writes it,
    // so a RecordList that is not empty has been bounds-checked.
    bool setRecords(const CacheFile *cacheFile, quint64 firstRecord,
                    quint32 count, quint32 stride);
 
    quint64 m_firstRecord = 0;
    quint32 m_stride = 0;
    quint32 m_count = 0;
};
 
struct QMimeBinaryProvider::CacheFile
{
    CacheFile(const QString &fileName);
    ~CacheFile();
 
    bool isValid() const { return m_valid; }
    inline std::optional<quint16> getUint16(quint64 offset) const
    {
        if (offset > m_fileSize || m_fileSize - offset < sizeof(quint16))
            return std::nullopt;
        return qFromBigEndian<quint16>(m_data + offset);
    }
    inline std::optional<quint32> getUint32(quint64 offset, quint64 extra = 0) const
    {
        if (offset > m_fileSize || extra > m_fileSize - offset)
            return std::nullopt;
        const quint64 pos = offset + extra;
        if (m_fileSize - pos < sizeof(quint32))
            return std::nullopt;
        return qFromBigEndian<quint32>(m_data + pos);
    }
    inline QLatin1StringView getLatin1String(quint64 offset) const
    {
        if (offset >= m_fileSize)
            return QLatin1StringView();
        const char *str = reinterpret_cast<const char *>(m_data + offset);
        const void *end = std::memchr(str, '\0', m_fileSize - offset);
        if (!end)
            return QLatin1StringView();
        return QLatin1StringView(str, static_cast<const char *>(end));
    }
    inline const char *getData(quint64 offset, quint64 length) const
    {
        if (offset > m_fileSize || length > m_fileSize - offset)
            return nullptr;
        return reinterpret_cast<const char *>(m_data + offset);
    }
    // Check base + headerSize + index * stride can not overflow.
    std::optional<quint64> safeRecordOffset(quint64 base, quint64 headerSize,
                                            quint32 index, quint32 stride) const
    {
        if (base > m_fileSize || headerSize > m_fileSize - base)
            return std::nullopt;
        const quint64 avail = m_fileSize - base - headerSize;
        // A zero stride would make every index alias the same record: corrupt cache.
        if (!stride || index >= avail / stride)
            return std::nullopt;
        return base + headerSize + quint64(index) * stride;
    }
    // A quint32 field of a record of a bounds-checked RecordList. load() has
    // verified that every record below list.count() lies inside the mapping.
    inline quint32 recordUint32(const RecordList &list, quint32 index, quint32 fieldOffset) const
    {
        // note: fieldOffset is in range: { 0, 4, 8, 12 }
        const quint64 pos = list.recordOffset(index) + fieldOffset;
        return qFromBigEndian<quint32>(m_data + pos);
    }
    bool load();
    bool reload();
 
    QFile m_file;
    uchar *m_data = nullptr;
    quint64 m_fileSize = 0;
    QDateTime m_mtime;
    bool m_valid = false;
 
    // The lists whose offsets are stored in the first 40 bytes of the file,
    // bounds-checked once by load() so that lookups don't have to.
    RecordList m_aliases;
    RecordList m_parents;
    RecordList m_literals;
    RecordList m_globs;
    RecordList m_suffixTreeRoots;
    RecordList m_magicMatches;
    RecordList m_icons;
    RecordList m_genericIcons;
};
 
// Leaves the list empty if the records don't all fit.
bool QMimeBinaryProvider::RecordList::setRecords(const CacheFile *cacheFile, quint64 firstRecord,
                                                 quint32 count, quint32 stride)
{
    if (!stride || (firstRecord > cacheFile->m_fileSize)) // corrupt cache
        return false;
    if (count > (cacheFile->m_fileSize - firstRecord) / stride)
        return false; // corrupt cache, or more records than can possibly fit
    m_firstRecord = firstRecord;
    m_stride = stride;
    m_count = count;
    return true;
}
 
// Reads the list header pointed to by the offset at posListOffset: the number
// of records sits at +0 and the records themselves follow at +4.
bool QMimeBinaryProvider::RecordList::load(const CacheFile *cacheFile, quint64 posListOffset,
                                           quint32 stride)
{
    const std::optional<quint32> listOffset = cacheFile->getUint32(posListOffset);
    if (!listOffset)
        return false; // corrupt cache
    const std::optional<quint32> n = cacheFile->getUint32(*listOffset);
    if (!n)
        return false; // corrupt cache
    return setRecords(cacheFile, quint64(*listOffset) + 4, *n, stride);
}
 
bool QMimeBinaryProvider::RecordList::loadIndirect(const CacheFile *cacheFile,
                                                   quint64 posListOffset, quint64 firstRecordPos,
                                                   quint32 stride)
{
    const std::optional<quint32> listOffset = cacheFile->getUint32(posListOffset);
    if (!listOffset)
        return false; // corrupt cache
    const std::optional<quint32> n = cacheFile->getUint32(*listOffset);
    const std::optional<quint32> first = cacheFile->getUint32(*listOffset + firstRecordPos);
    if (!n || !first)
        return false; // corrupt cache
    return setRecords(cacheFile, *first, *n, stride);
}
 
static inline void appendIfNew(QStringList &list, const QString &str)
{
    if (!list.contains(str))
        list.push_back(str);
}
 
QMimeProviderBase::QMimeProviderBase(QMimeDatabasePrivate *db, const QString &directory)
    : m_db(db), m_directory(directory)
{
}
 
QMimeProviderBase *QMimeProviderBase::overrideProvider() const
{
    return m_overrideProvider;
}
 
void QMimeProviderBase::setOverrideProvider(QMimeProviderBase *provider)
{
    m_overrideProvider = provider;
}
 
bool QMimeProviderBase::isMimeTypeGlobsExcluded(const QString &name) const
{
    if (m_overrideProvider) {
        if (m_overrideProvider->hasGlobDeleteAll(name))
            return true;
        return m_overrideProvider->isMimeTypeGlobsExcluded(name);
    }
    return false;
}
 
QMimeBinaryProvider::QMimeBinaryProvider(QMimeDatabasePrivate *db, const QString &directory)
    : QMimeProviderBase(db, directory), m_mimetypeListLoaded(false)
{
    ensureLoaded();
}
 
QMimeBinaryProvider::CacheFile::CacheFile(const QString &fileName)
    : m_file(fileName)
{
    load();
}
 
QMimeBinaryProvider::CacheFile::~CacheFile()
{
}
 
bool QMimeBinaryProvider::CacheFile::load()
{
    if (!m_file.open(QIODevice::ReadOnly))
        return false;
    const qint64 fileSize = m_file.size();
    m_fileSize = fileSize > 0 ? fileSize : 0;
    m_data = m_file.map(0, m_fileSize);
    if (m_data && m_fileSize >= 4) {
        const quint16 major = *getUint16(0);
        const quint16 minor = *getUint16(2);
        m_valid = (major == 1 && minor >= 1 && minor <= 2)
                && m_aliases.load(this, PosAliasListOffset, AliasRecordSize)
                && m_parents.load(this, PosParentListOffset, ParentRecordSize)
                && m_literals.load(this, PosLiteralListOffset, GlobRecordSize)
                && m_globs.load(this, PosGlobListOffset, GlobRecordSize)
                && m_icons.load(this, PosIconsListOffset, IconRecordSize)
                && m_genericIcons.load(this, PosGenericIconsListOffset, IconRecordSize)
                && m_suffixTreeRoots.loadIndirect(this, PosReverseSuffixTreeOffset,
                                                  PosFirstRootOffset, SuffixNodeSize)
                && m_magicMatches.loadIndirect(this, PosMagicListOffset, PosFirstMatchOffset,
                                               MagicMatchSize);
    }
    m_mtime = QFileInfo(m_file).lastModified(QTimeZone::UTC);
    return m_valid;
}
 
bool QMimeBinaryProvider::CacheFile::reload()
{
    m_valid = false;
    if (m_file.isOpen()) {
        m_file.close();
    }
    m_data = nullptr;
    m_fileSize = 0;
    m_aliases = RecordList();
    m_parents = RecordList();
    m_literals = RecordList();
    m_globs = RecordList();
    m_suffixTreeRoots = RecordList();
    m_magicMatches = RecordList();
    m_icons = RecordList();
    m_genericIcons = RecordList();
    return load();
}
 
QMimeBinaryProvider::~QMimeBinaryProvider() = default;
 
bool QMimeBinaryProvider::isValid()
{
    return m_cacheFile != nullptr;
}
 
bool QMimeBinaryProvider::isInternalDatabase() const
{
    return false;
}
 
bool QMimeBinaryProvider::checkCacheChanged()
{
    QFileInfo fileInfo(m_cacheFile->m_file);
    if (fileInfo.lastModified(QTimeZone::UTC) > m_cacheFile->m_mtime) {
        // Deletion can't happen by just running update-mime-database.
        // But the user could use rm -rf :-)
        m_cacheFile->reload(); // will mark itself as invalid on failure
        return true;
    }
    return false;
}
 
void QMimeBinaryProvider::ensureLoaded()
{
    if (!m_cacheFile) {
        const QString cacheFileName = m_directory + "/mime.cache"_L1;
        m_cacheFile = std::make_unique<CacheFile>(cacheFileName);
        m_mimetypeListLoaded = false;
        m_mimetypeExtra.clear();
    } else {
        if (checkCacheChanged()) {
            m_mimetypeListLoaded = false;
            m_mimetypeExtra.clear();
        } else {
            return; // nothing to do
        }
    }
    if (!m_cacheFile->isValid()) // verify existence and version
        m_cacheFile.reset();
}
 
bool QMimeBinaryProvider::knowsMimeType(const QString &name)
{
    if (!m_mimetypeListLoaded)
        loadMimeTypeList();
    return m_mimetypeNames.contains(name);
}
 
void QMimeBinaryProvider::addFileNameMatches(const QString &fileName, QMimeGlobMatchResult &result)
{
    if (fileName.isEmpty())
        return;
    Q_ASSERT(m_cacheFile);
    // Check literals (e.g. "Makefile")
    quint32 numMatches = matchGlobList(result, m_cacheFile.get(), m_cacheFile->m_literals, fileName);
    // Check the very common *.txt cases with the suffix tree
    if (numMatches == 0) {
        const QString lowerFileName = fileName.toLower();
        const RecordList &roots = m_cacheFile->m_suffixTreeRoots;
        if (matchSuffixTree(result, m_cacheFile.get(), roots.count(), roots.firstRecord(),
                            lowerFileName, lowerFileName.size() - 1, false)) {
            ++numMatches;
        } else if (matchSuffixTree(result, m_cacheFile.get(), roots.count(), roots.firstRecord(),
                                   fileName, fileName.size() - 1, true)) {
            ++numMatches;
        }
    }
    // Check complex globs (e.g. "callgrind.out[0-9]*" or "README*")
    if (numMatches == 0)
        matchGlobList(result, m_cacheFile.get(), m_cacheFile->m_globs, fileName);
}
 
quint32 QMimeBinaryProvider::matchGlobList(QMimeGlobMatchResult &result, CacheFile *cacheFile,
                                           const RecordList &globs, const QString &fileName)
{
    quint32 numMatches = 0;
    //qDebug() << "Loading" << globs.count() << "globs from" << cacheFile->m_file.fileName();
    for (quint32 i = 0; i < globs.count(); ++i) {
        const quint32 globOffset = cacheFile->recordUint32(globs, i, 0);
        const quint32 mimeTypeOffset = cacheFile->recordUint32(globs, i, 4);
        const quint32 flagsAndWeight = cacheFile->recordUint32(globs, i, 8);
        const quint32 weight = flagsAndWeight & 0xff;
        const bool caseSensitive = flagsAndWeight & 0x100;
        const Qt::CaseSensitivity qtCaseSensitive = caseSensitive ? Qt::CaseSensitive : Qt::CaseInsensitive;
        const QLatin1StringView patternL1 = cacheFile->getLatin1String(globOffset);
        const QLatin1StringView mimeType = cacheFile->getLatin1String(mimeTypeOffset);
        if (patternL1.isNull() || mimeType.isNull()) // corrupt cache: skip this record
            continue;
 
        //qDebug() << pattern << mimeType << weight << caseSensitive;
        if (isMimeTypeGlobsExcluded(mimeType))
            continue;
 
        const QString pattern = patternL1;
        QMimeGlobPattern glob(pattern, QString() /*unused*/, weight, qtCaseSensitive);
        if (glob.matchFileName(fileName)) {
            result.addMatch(mimeType, weight, pattern);
            ++numMatches;
        }
    }
    return numMatches;
}
 
bool QMimeBinaryProvider::matchSuffixTree(QMimeGlobMatchResult &result,
                                          QMimeBinaryProvider::CacheFile *cacheFile, quint32 numEntries,
                                          quint64 firstOffset, const QString &fileName,
                                          qsizetype charPos, bool caseSensitiveCheck)
{
    QChar fileChar = fileName[charPos];
    if (fileChar.isNull())
        return false;
    if (numEntries == 0)
        return false;
    quint32 min = 0;
    quint32 max = numEntries - 1;
    while (min <= max) {
        const quint32 mid = (min + max) / 2;
        const std::optional<quint64> off = cacheFile->safeRecordOffset(firstOffset, 0, mid, SuffixNodeSize);
        if (!off) // corrupt cache
            break;
        const std::optional<quint32> chValue = cacheFile->getUint32(*off);
        if (!chValue) // corrupt cache
            break;
        const QChar ch = char16_t(*chValue);
        if (ch < fileChar) {
            min = mid + 1;
        } else if (ch > fileChar) {
            if (!mid)
                break;
            max = mid - 1;
        } else {
            --charPos;
            const std::optional<quint32> numChildrenOpt = cacheFile->getUint32(*off, 4);
            const std::optional<quint32> childrenOffsetOpt = cacheFile->getUint32(*off, 8);
            if (!numChildrenOpt || !childrenOffsetOpt) // corrupt cache
                return false;
            const quint32 numChildren = *numChildrenOpt;
            const quint32 childrenOffset = *childrenOffsetOpt;
            bool success = false;
            if (charPos > 0)
                success = matchSuffixTree(result, cacheFile, numChildren, childrenOffset, fileName, charPos, caseSensitiveCheck);
            if (!success) {
                for (quint32 i = 0; i < numChildren; ++i) {
                    const std::optional<quint64> childOff =
                            cacheFile->safeRecordOffset(childrenOffset, 0, i, SuffixNodeSize);
                    if (!childOff) // corrupt cache, or numChildren bigger than can possibly fit
                        break;
                    const std::optional<quint32> mchOpt = cacheFile->getUint32(*childOff);
                    if (!mchOpt) // corrupt cache: no later record can be inside the file either
                        break;
                    if (*mchOpt != 0) // not a leaf entry: end of the leaf list
                        break;
                    const std::optional<quint32> mimeTypeOffset = cacheFile->getUint32(*childOff, 4);
                    const std::optional<quint32> flagsAndWeight = cacheFile->getUint32(*childOff, 8);
                    if (!mimeTypeOffset || !flagsAndWeight) // corrupt cache: nor is any later one
                        break;
                    const QLatin1StringView mimeType = cacheFile->getLatin1String(*mimeTypeOffset);
                    if (mimeType.isNull()) // corrupt cache: skip this record
                        continue;
                    if (isMimeTypeGlobsExcluded(mimeType))
                        continue;
                    const quint32 weight = *flagsAndWeight & 0xff;
                    const bool caseSensitive = *flagsAndWeight & 0x100;
                    if (caseSensitiveCheck || !caseSensitive) {
                        result.addMatch(mimeType, weight,
                                        u'*' + QStringView{ fileName }.mid(charPos + 1),
                                        fileName.size() - charPos - 2);
                        success = true;
                    }
                }
            }
            return success;
        }
    }
    return false;
}
 
bool QMimeBinaryProvider::matchMagicRule(QMimeBinaryProvider::CacheFile *cacheFile,
                                         quint32 numMatchlets, quint64 firstOffset,
                                         const QByteArray &data, int depth, qint64 &budget)
{
    // The child offsets come straight from the cache file, so a corrupt (or
    // hostile) mime.cache can describe a cyclic or unreasonably deep matchlet
    // tree. Stop following it instead of exhausting the stack.
    if (depth <= 0)
        return false;
 
    const char *dataPtr = data.constData();
    const qsizetype dataSize = data.size();
    for (quint32 matchlet = 0; matchlet < numMatchlets; ++matchlet) {
        const std::optional<quint64> off = cacheFile->safeRecordOffset(firstOffset, 0, matchlet, MagicMatchletSize);
        if (!off) // corrupt cache, or numMatchlets bigger than can possibly fit
            break;
        const std::optional<quint32> rangeStartOpt = cacheFile->getUint32(*off);
        const std::optional<quint32> rangeLengthOpt = cacheFile->getUint32(*off, 4);
        //const auto wordSize = cacheFile->getUint32(*off, 8);
        const std::optional<quint32> valueLengthOpt = cacheFile->getUint32(*off, 12);
        const std::optional<quint32> valueOffsetOpt = cacheFile->getUint32(*off, 16);
        const std::optional<quint32> maskOffsetOpt = cacheFile->getUint32(*off, 20);
        if (!rangeStartOpt || !rangeLengthOpt || !valueLengthOpt || !valueOffsetOpt
            || !maskOffsetOpt) // corrupt cache: no later matchlet can be inside the file either
            break;
        const quint32 rangeStart = *rangeStartOpt;
        const quint32 rangeLength = *rangeLengthOpt;
        const quint32 valueLength = *valueLengthOpt;
        const quint32 valueOffset = *valueOffsetOpt;
        const quint32 maskOffset = *maskOffsetOpt;
        budget -= 1 + qMin(quint64(rangeLength), quint64(dataSize));
        if (budget < 0) // corrupt cache: give up on this record
            return false;
        const char *value = cacheFile->getData(valueOffset, valueLength);
        const char *mask = maskOffset ? cacheFile->getData(maskOffset, valueLength) : nullptr;
        if (!value || (maskOffset && !mask)) // corrupt cache
            continue;
 
        if (!QMimeMagicRule::matchSubstring(dataPtr, dataSize, rangeStart, rangeLength, valueLength, value, mask))
            continue;
 
        const std::optional<quint32> numChildrenOpt = cacheFile->getUint32(*off, 24);
        const std::optional<quint32> firstChildOffsetOpt = cacheFile->getUint32(*off, 28);
        if (!numChildrenOpt || !firstChildOffsetOpt) // corrupt cache: nor is any later matchlet
            break;
        const quint32 numChildren = *numChildrenOpt;
        const quint32 firstChildOffset = *firstChildOffsetOpt;
        if (numChildren == 0) // No submatch? Then we are done.
            return true;
        // Check that one of the submatches matches too
        if (matchMagicRule(cacheFile, numChildren, firstChildOffset, data, depth - 1, budget))
            return true;
    }
    return false;
}
 
bool QMimeBinaryProvider::magicRecordMatches(quint32 index, const QByteArray &data,
                                             qint64 &budget) const
{
    const RecordList &matches = m_cacheFile->m_magicMatches;
    const quint32 numMatchlets = m_cacheFile->recordUint32(matches, index, 8);
    const quint32 firstMatchletOffset = m_cacheFile->recordUint32(matches, index, 12);
    return matchMagicRule(m_cacheFile.get(), numMatchlets, firstMatchletOffset, data,
                          QMimeMagicRule::MaxRecursionDepth, budget);
}
 
void QMimeBinaryProvider::findByMagic(const QByteArray &data, QMimeMagicResult &result)
{
    const RecordList &matches = m_cacheFile->m_magicMatches;
    qint64 budget = MagicMatchBudget;
    for (quint32 i = 0; i < matches.count() && budget >= 0; ++i) {
        if (magicRecordMatches(i, data, budget)) {
            const int accuracy = static_cast<int>(m_cacheFile->recordUint32(matches, i, 0));
            if (accuracy > result.accuracy) {
                const quint32 mimeTypeOffset = m_cacheFile->recordUint32(matches, i, 4);
                const QLatin1StringView candidate = m_cacheFile->getLatin1String(mimeTypeOffset);
                if (candidate.isNull()) // corrupt cache: skip this record
                    continue;
                result.accuracy = accuracy;
                result.candidate = candidate;
                // Return the first match, mime.cache is sorted
                return;
            }
        }
    }
}
 
QMimeMagicCheckResult
QMimeBinaryProvider::checkMagicRules(const QString &mime, const QByteArray &data) const
{
    QMimeMagicCheckResult result;
    const RecordList &matches = m_cacheFile->m_magicMatches;
    qint64 budget = MagicMatchBudget;
    for (quint32 i = 0; i < matches.count() && budget >= 0; ++i) {
        const quint32 mimeTypeOffset = m_cacheFile->recordUint32(matches, i, 4);
        if (m_cacheFile->getLatin1String(mimeTypeOffset) != mime)
            continue;
        result.hasRules = true;
        if (magicRecordMatches(i, data, budget)) {
            result.matched = true;
            break;
        }
    }
    return result;
}
 
void QMimeBinaryProvider::addParents(const QString &mime, QStringList &result)
{
    const RecordList &parentList = m_cacheFile->m_parents;
    const quint32 count = parentList.count();
    if (!count)
        return;
    quint32 begin = 0;
    quint32 end = count - 1;
    while (begin <= end) {
        const quint32 medium = (begin + end) / 2;
        const quint32 mimeOffset = m_cacheFile->recordUint32(parentList, medium, 0);
        const QLatin1StringView aMime = m_cacheFile->getLatin1String(mimeOffset);
        if (aMime.isNull()) // corrupt cache: the search cannot continue
            break;
        const int cmp = aMime.compare(mime);
        if (cmp < 0) {
            begin = medium + 1;
        } else if (cmp > 0) {
            if (!medium)
                break;
            end = medium - 1;
        } else {
            // The parent list is reached by following an offset stored in the
            // record, so it has to be bounds-checked here.
            const quint32 parentsOffset = m_cacheFile->recordUint32(parentList, medium, 4);
            const std::optional<quint32> numParentsOpt = m_cacheFile->getUint32(parentsOffset);
            if (!numParentsOpt) // corrupt cache
                break;
            const quint32 numParents = *numParentsOpt;
            for (quint32 i = 0; i < numParents; ++i) {
                const std::optional<quint64> parentOff =
                        m_cacheFile->safeRecordOffset(parentsOffset, 4, i, 4);
                if (!parentOff) // past end of file: no later index can be inside it
                    break;
                const std::optional<quint32> parentOffsetOpt = m_cacheFile->getUint32(*parentOff);
                if (!parentOffsetOpt) // corrupt cache: no later index can be inside the file either
                    break;
                const QLatin1StringView parentL1 = m_cacheFile->getLatin1String(*parentOffsetOpt);
                if (parentL1.isNull()) // corrupt cache: skip this record
                    break;
                appendIfNew(result, QString(parentL1));
            }
            break;
        }
    }
}
 
QString QMimeBinaryProvider::resolveAlias(const QString &name)
{
    const RecordList &aliases = m_cacheFile->m_aliases;
    quint32 begin = 0;
    const quint32 count = aliases.count();
    if (!count)
        return QString();
    quint32 end = count - 1;
    while (begin <= end) {
        const quint32 medium = (begin + end) / 2;
        const quint32 aliasOffset = m_cacheFile->recordUint32(aliases, medium, 0);
        const QLatin1StringView alias = m_cacheFile->getLatin1String(aliasOffset);
        if (alias.isNull()) // corrupt cache: the search cannot continue
            break;
        const int cmp = alias.compare(name);
        if (cmp < 0) {
            begin = medium + 1;
        } else if (cmp > 0) {
            if (!medium)
                break;
            end = medium - 1;
        } else {
            const quint32 mimeOffset = m_cacheFile->recordUint32(aliases, medium, 4);
            // if corrupt cache, returns QLatin1StringView(), which converts to a null QString
            return m_cacheFile->getLatin1String(mimeOffset);
        }
    }
    return QString();
}
 
void QMimeBinaryProvider::addAliases(const QString &name, QStringList &result)
{
    const RecordList &aliases = m_cacheFile->m_aliases;
    for (quint32 pos = 0; pos < aliases.count(); ++pos) {
        const quint32 mimeOffset = m_cacheFile->recordUint32(aliases, pos, 4);
        const QLatin1StringView mimeType = m_cacheFile->getLatin1String(mimeOffset);
        if (mimeType.isNull()) // corrupt cache: skip this record
            continue;
 
        if (name == QLatin1StringView(mimeType)) {
            const quint32 aliasOffset = m_cacheFile->recordUint32(aliases, pos, 0);
            const QLatin1StringView aliasL1 = m_cacheFile->getLatin1String(aliasOffset);
            if (aliasL1.isNull()) // corrupt cache: skip this record
                continue;
            appendIfNew(result, QString(aliasL1));
        }
    }
}
 
void QMimeBinaryProvider::loadMimeTypeList()
{
    if (!m_mimetypeListLoaded) {
        m_mimetypeListLoaded = true;
        m_mimetypeNames.clear();
        // Unfortunately mime.cache doesn't have a full list of all mimetypes.
        // So we have to parse the plain-text files called "types".
        QFile file(m_directory + QStringView(u"/types"));
        if (file.open(QIODevice::ReadOnly)) {
            QByteArray line;
            while (file.readLineInto(&line)) {
                auto lineView = QByteArrayView(line);
                if (lineView.endsWith('\n'))
                    lineView.chop(1);
                m_mimetypeNames.insert(QString::fromLatin1(lineView));
            }
        }
    }
}
 
void QMimeBinaryProvider::addAllMimeTypes(QList<QMimeType> &result)
{
    loadMimeTypeList();
    if (result.isEmpty()) {
        result.reserve(m_mimetypeNames.size());
        for (const QString &name : std::as_const(m_mimetypeNames))
            result.append(QMimeType(QMimeTypePrivate(name)));
    } else {
        for (const QString &name : std::as_const(m_mimetypeNames))
            if (std::find_if(result.constBegin(), result.constEnd(), [name](const QMimeType &mime) -> bool { return mime.name() == name; })
                    == result.constEnd())
                result.append(QMimeType(QMimeTypePrivate(name)));
    }
}
 
QMimeTypePrivate::LocaleHash QMimeBinaryProvider::localeComments(const QString &name)
{
    MimeTypeExtraMap::const_iterator it = loadMimeTypeExtra(name);
    if (it != m_mimetypeExtra.cend())
        return it->second.localeComments;
    return {};
}
 
bool QMimeBinaryProvider::hasGlobDeleteAll(const QString &name)
{
    MimeTypeExtraMap::const_iterator it = loadMimeTypeExtra(name);
    if (it != m_mimetypeExtra.cend())
        return it->second.hasGlobDeleteAll;
    return {};
}
 
QStringList QMimeBinaryProvider::globPatterns(const QString &name)
{
    MimeTypeExtraMap::const_iterator it = loadMimeTypeExtra(name);
    if (it != m_mimetypeExtra.cend())
        return it->second.globPatterns;
    return {};
}
 
QMimeBinaryProvider::MimeTypeExtraMap::const_iterator
QMimeBinaryProvider::loadMimeTypeExtra(const QString &mimeName)
{
#if QT_CONFIG(xmlstreamreader)
    auto [it, insertionOccurred] = m_mimetypeExtra.try_emplace(mimeName);
    if (insertionOccurred) {
        // load comment and globPatterns
 
        // shared-mime-info since 1.3 lowercases the xml files
        QFile qfile;
        const QString mimeFile = m_directory + u'/' + mimeName.toLower() + ".xml"_L1;
        qfile.setFileName(mimeFile);
        if (!qfile.open(QFile::ReadOnly)) {
            const QString fallbackMimeFile = m_directory + u'/' + mimeName + ".xml"_L1; // pre-1.3
            qfile.setFileName(fallbackMimeFile);
            if (!qfile.open(QFile::ReadOnly))
                return it;
        }
 
        MimeTypeExtra &extra = it->second;
        QString mainPattern;
 
        QXmlStreamReader xml(&qfile);
        if (xml.readNextStartElement()) {
            if (xml.name() != "mime-type"_L1) {
                return m_mimetypeExtra.cend();
            }
            const auto name = xml.attributes().value("type"_L1);
            if (name.isEmpty())
                return m_mimetypeExtra.cend();
            if (name.compare(mimeName, Qt::CaseInsensitive))
                qWarning() << "Got name" << name << "in file" << mimeFile << "expected" << mimeName;
 
            while (xml.readNextStartElement()) {
                const auto tag = xml.name();
                if (tag == "comment"_L1) {
                    QString lang = xml.attributes().value("xml:lang"_L1).toString();
                    const QString text = xml.readElementText();
                    if (lang.isEmpty()) {
                        lang = "default"_L1; // no locale attribute provided, treat it as default.
                    }
                    extra.localeComments.insert(lang, text);
                    continue; // we called readElementText, so we're at the EndElement already.
                } else if (tag == "glob-deleteall"_L1) { // as written out by shared-mime-info >= 0.70
                    extra.hasGlobDeleteAll = true;
                } else if (tag == "glob"_L1) { // as written out by shared-mime-info >= 0.70
                    const QString pattern = xml.attributes().value("pattern"_L1).toString();
                    if (mainPattern.isEmpty() && pattern.startsWith(u'*')) {
                        mainPattern = pattern;
                    }
                    appendIfNew(extra.globPatterns, pattern);
                }
                xml.skipCurrentElement();
            }
            Q_ASSERT(xml.name() == "mime-type"_L1);
        }
 
        // Let's assume that shared-mime-info is at least version 0.70
        // Otherwise we would need 1) a version check, and 2) code for parsing patterns from the globs file.
        if (!mainPattern.isEmpty() &&
                (extra.globPatterns.isEmpty() || extra.globPatterns.constFirst() != mainPattern)) {
            // ensure it's first in the list of patterns
            extra.globPatterns.removeAll(mainPattern);
            extra.globPatterns.prepend(mainPattern);
        }
    }
    return it;
#else
    Q_UNUSED(mimeName);
    qWarning("Cannot load mime type since QXmlStreamReader is not available.");
    return m_mimetypeExtra.cend();
#endif // feature xmlstreamreader
}
 
// Binary search in the icons or generic-icons list
QLatin1StringView QMimeBinaryProvider::iconForMime(CacheFile *cacheFile, const RecordList &icons,
                                                   QStringView inputMime)
{
    quint32 begin = 0;
    const quint32 count = icons.count();
    if (!count)
        return QLatin1StringView();
    quint32 end = count - 1;
    while (begin <= end) {
        const quint32 medium = (begin + end) / 2;
        const quint32 mimeOffset = cacheFile->recordUint32(icons, medium, 0);
        const QLatin1StringView mime = cacheFile->getLatin1String(mimeOffset);
        if (mime.isNull()) // corrupt cache: the search cannot continue
            break;
        const int cmp = mime.compare(inputMime);
        if (cmp < 0) {
            begin = medium + 1;
        } else if (cmp > 0) {
            if (!medium)
                break;
            end = medium - 1;
        } else {
            const quint32 iconOffset = cacheFile->recordUint32(icons, medium, 4);
            // if corrupt cache, returns QLatin1StringView()
            return cacheFile->getLatin1String(iconOffset);
        }
    }
    return QLatin1StringView();
}
 
QString QMimeBinaryProvider::icon(const QString &name)
{
    return iconForMime(m_cacheFile.get(), m_cacheFile->m_icons, name);
}
 
QString QMimeBinaryProvider::genericIcon(const QString &name)
{
    return iconForMime(m_cacheFile.get(), m_cacheFile->m_genericIcons, name);
}
 
////
 
#if QT_CONFIG(mimetype_database)
static QString internalMimeFileName()
{
    return QStringLiteral("<internal MIME data>");
}
 
QMimeXMLProvider::QMimeXMLProvider(QMimeDatabasePrivate *db, InternalDatabaseEnum)
    : QMimeProviderBase(db, internalMimeFileName())
{
    static_assert(sizeof(mimetype_database), "Bundled MIME database is empty");
    static_assert(sizeof(mimetype_database) <= MimeTypeDatabaseOriginalSize,
                      "Compressed MIME database is larger than the original size");
    static_assert(MimeTypeDatabaseOriginalSize <= 16*1024*1024,
                      "Bundled MIME database is too big");
    const char *data = reinterpret_cast<const char *>(mimetype_database);
    qsizetype size = MimeTypeDatabaseOriginalSize;
 
#ifdef MIME_DATABASE_IS_ZSTD
    // uncompress with libzstd
    std::unique_ptr<char []> uncompressed(new char[size]);
    size = ZSTD_decompress(uncompressed.get(), size, mimetype_database, sizeof(mimetype_database));
    Q_ASSERT(!ZSTD_isError(size));
    data = uncompressed.get();
#elif defined(MIME_DATABASE_IS_GZIP)
    std::unique_ptr<char []> uncompressed(new char[size]);
    z_stream zs = {};
    zs.next_in = const_cast<Bytef *>(mimetype_database);
    zs.avail_in = sizeof(mimetype_database);
    zs.next_out = reinterpret_cast<Bytef *>(uncompressed.get());
    zs.avail_out = size;
 
    int res = inflateInit2(&zs, MAX_WBITS | 32);
    Q_ASSERT(res == Z_OK);
    res = inflate(&zs, Z_FINISH);
    Q_ASSERT(res == Z_STREAM_END);
    res = inflateEnd(&zs);
    Q_ASSERT(res == Z_OK);
 
    data = uncompressed.get();
    size = zs.total_out;
#endif
 
    load(data, size);
    sortMagicMatchers();
}
#else // !QT_CONFIG(mimetype_database)
// never called in release mode, but some debug builds may need
// this to be defined.
QMimeXMLProvider::QMimeXMLProvider(QMimeDatabasePrivate *db, InternalDatabaseEnum)
    : QMimeProviderBase(db, QString())
{
    Q_UNREACHABLE();
}
#endif // QT_CONFIG(mimetype_database)
 
QMimeXMLProvider::QMimeXMLProvider(QMimeDatabasePrivate *db, const QString &directory)
    : QMimeProviderBase(db, directory)
{
    ensureLoaded();
}
 
QMimeXMLProvider::~QMimeXMLProvider()
{
}
 
bool QMimeXMLProvider::isValid()
{
    // If you change this method, adjust the logic in QMimeDatabasePrivate::loadProviders,
    // which assumes isValid==false is only possible in QMimeBinaryProvider.
    return true;
}
 
bool QMimeXMLProvider::isInternalDatabase() const
{
#if QT_CONFIG(mimetype_database)
    return m_directory == internalMimeFileName();
#else
    return false;
#endif
}
 
bool QMimeXMLProvider::knowsMimeType(const QString &name)
{
    return m_nameMimeTypeMap.contains(name);
}
 
void QMimeXMLProvider::addFileNameMatches(const QString &fileName, QMimeGlobMatchResult &result)
{
    auto filterFunc = [this](const QString &name) { return !isMimeTypeGlobsExcluded(name); };
    m_mimeTypeGlobs.matchingGlobs(fileName, result, filterFunc);
}
 
void QMimeXMLProvider::findByMagic(const QByteArray &data, QMimeMagicResult &result)
{
    for (const QMimeMagicRuleMatcher &matcher : std::as_const(m_magicMatchers)) {
        if (matcher.matches(data)) {
            const int priority = matcher.priority();
            if (priority > result.accuracy) {
                result.accuracy = priority;
                result.candidate = matcher.mimetype();
            }
        }
    }
}
 
QMimeMagicCheckResult
QMimeXMLProvider::checkMagicRules(const QString &mime, const QByteArray &data) const
{
    QMimeMagicCheckResult result;
    for (const QMimeMagicRuleMatcher &matcher : m_magicMatchers) {
        if (matcher.mimetype() != mime)
            continue;
        result.hasRules = true;
        if (matcher.matches(data)) {
            result.matched = true;
            break;
        }
    }
    return result;
}
 
void QMimeXMLProvider::ensureLoaded()
{
    QStringList allFiles;
    const QString packageDir = m_directory + QStringView(u"/packages");
    for (const auto &entry : QDirListing(packageDir, QDirListing::IteratorFlag::FilesOnly
                                         | QDirListing::IteratorFlag::ResolveSymlinks))
        allFiles.emplace_back(packageDir + u'/' + entry.fileName());
 
    if (m_allFiles == allFiles)
        return;
    m_allFiles = allFiles;
 
    m_nameMimeTypeMap.clear();
    m_aliases.clear();
    m_parents.clear();
    m_mimeTypeGlobs.clear();
    m_magicMatchers.clear();
 
    //qDebug() << "Loading" << m_allFiles;
 
    for (const QString &file : std::as_const(allFiles))
        load(file);
    sortMagicMatchers();
}
 
// Same order as in mime.cache: highest priority first, then by mimetype name,
// so that both providers pick the same mimetype when several rules match.
void QMimeXMLProvider::sortMagicMatchers()
{
    std::stable_sort(m_magicMatchers.begin(), m_magicMatchers.end(),
                     [](const QMimeMagicRuleMatcher &a, const QMimeMagicRuleMatcher &b) {
                         if (a.priority() != b.priority())
                             return a.priority() > b.priority();
                         return a.mimetype() < b.mimetype();
                     });
}
 
QMimeTypePrivate::LocaleHash QMimeXMLProvider::localeComments(const QString &name)
{
    return m_nameMimeTypeMap.value(name).localeComments;
}
 
bool QMimeXMLProvider::hasGlobDeleteAll(const QString &name)
{
    return m_nameMimeTypeMap.value(name).hasGlobDeleteAll;
}
 
QStringList QMimeXMLProvider::globPatterns(const QString &name)
{
    return m_nameMimeTypeMap.value(name).globPatterns;
}
 
QString QMimeXMLProvider::icon(const QString &name)
{
    return m_nameMimeTypeMap.value(name).iconName;
}
 
QString QMimeXMLProvider::genericIcon(const QString &name)
{
    return m_nameMimeTypeMap.value(name).genericIconName;
}
 
void QMimeXMLProvider::load(const QString &fileName)
{
    QString errorMessage;
    if (!load(fileName, &errorMessage))
        qWarning("QMimeDatabase: Error loading %ls\n%ls", qUtf16Printable(fileName), qUtf16Printable(errorMessage));
}
 
bool QMimeXMLProvider::load(const QString &fileName, QString *errorMessage)
{
    QFile file(fileName);
    if (!file.open(QIODevice::ReadOnly | QIODevice::Text)) {
        if (errorMessage)
            *errorMessage = "Cannot open "_L1 + fileName + ": "_L1 + file.errorString();
        return false;
    }
 
    if (errorMessage)
        errorMessage->clear();
 
    QMimeTypeParser parser(*this);
    return parser.parse(&file, fileName, errorMessage);
}
 
#if QT_CONFIG(mimetype_database)
void QMimeXMLProvider::load(const char *data, qsizetype len)
{
    QBuffer buffer;
    buffer.setData(QByteArray::fromRawData(data, len));
    buffer.open(QIODevice::ReadOnly);
    QString errorMessage;
    QMimeTypeParser parser(*this);
    if (!parser.parse(&buffer, internalMimeFileName(), &errorMessage))
        qWarning("QMimeDatabase: Error loading internal MIME data\n%s", qPrintable(errorMessage));
}
#endif
 
void QMimeXMLProvider::addGlobPattern(const QMimeGlobPattern &glob)
{
    m_mimeTypeGlobs.addGlob(glob);
}
 
void QMimeXMLProvider::addMimeType(const QMimeTypeXMLData &mt)
{
    m_nameMimeTypeMap.insert(mt.name, mt);
}
 
void QMimeXMLProvider::addParents(const QString &mime, QStringList &result)
{
    const QStringList parents = m_parents.value(mime);
    for (const QString &parent : parents) {
        if (!result.contains(parent))
            result.append(parent);
    }
}
 
void QMimeXMLProvider::addParent(const QString &child, const QString &parent)
{
    m_parents[child].append(parent);
}
 
void QMimeXMLProvider::addAliases(const QString &name, QStringList &result)
{
    // Iterate through the whole hash. This method is rarely used.
    for (const auto &[alias, mimeName] : std::as_const(m_aliases).asKeyValueRange()) {
        if (mimeName == name)
            appendIfNew(result, alias);
    }
}
 
QString QMimeXMLProvider::resolveAlias(const QString &name)
{
    return m_aliases.value(name);
}
 
void QMimeXMLProvider::addAlias(const QString &alias, const QString &name)
{
    m_aliases.insert(alias, name);
}
 
void QMimeXMLProvider::addAllMimeTypes(QList<QMimeType> &result)
{
    if (result.isEmpty()) { // fast path
        for (auto it = m_nameMimeTypeMap.constBegin(), end = m_nameMimeTypeMap.constEnd();
             it != end; ++it) {
            result.append(QMimeType(QMimeTypePrivate(it.value().name)));
        }
    } else {
        for (auto it = m_nameMimeTypeMap.constBegin(), end = m_nameMimeTypeMap.constEnd() ; it != end ; ++it) {
            const QString newMime = it.key();
            if (std::find_if(result.constBegin(), result.constEnd(), [newMime](const QMimeType &mime) -> bool { return mime.name() == newMime; })
                    == result.constEnd())
                result.append(QMimeType(QMimeTypePrivate(it.value().name)));
        }
    }
}
 
void QMimeXMLProvider::addMagicMatcher(const QMimeMagicRuleMatcher &matcher)
{
    m_magicMatchers.append(matcher);
}
 
QT_END_NAMESPACE