qstaticlatin1stringmatcher.h

Go to the documentation of this file.

// Copyright (C) 2023 The Qt Company Ltd.
// 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
 
#ifndef QSTATICLATIN1STRINGMATCHER_H
#define QSTATICLATIN1STRINGMATCHER_H
 
#include <functional>
#include <iterator>
#include <limits>
 
#include <QtCore/q20algorithm.h>
#include <QtCore/qlatin1stringmatcher.h>
#include <QtCore/qstring.h>
 
QT_BEGIN_NAMESPACE
 
#ifdef Q_CC_GHS
#  define QT_STATIC_BOYER_MOORE_NOT_SUPPORTED
#else
namespace QtPrivate {
template <class RandomIt1,
          class Hash = std::hash<typename std::iterator_traits<RandomIt1>::value_type>,
          class BinaryPredicate = std::equal_to<>>
class q_boyer_moore_searcher
{
public:
    constexpr q_boyer_moore_searcher(RandomIt1 pat_first, RandomIt1 pat_last) : m_skiptable{}
    {
        const size_t n = std::distance(pat_first, pat_last);
        constexpr auto uchar_max = (std::numeric_limits<uchar>::max)();
        uchar max = n > uchar_max ? uchar_max : uchar(n);
        q20::fill(std::begin(m_skiptable), std::end(m_skiptable), max);
        Hash hf;
        RandomIt1 pattern = std::next(pat_first, n - max);
        while (max--)
            m_skiptable[hf(*pattern++)] = max;
    }
 
    template <class RandomIt2>
    constexpr auto operator()(RandomIt2 first, RandomIt2 last, RandomIt1 pat_first,
                              RandomIt1 pat_last) const
    {
        struct R
        {
            RandomIt2 begin, end;
        };
        Hash hf;
        BinaryPredicate pred;
        auto pat_length = std::distance(pat_first, pat_last);
        if (pat_length == 0)
            return R{ first, first };
 
        auto haystack_length = std::distance(first, last);
        if (haystack_length < pat_length)
            return R{ last, last };
 
        const qsizetype pl_minus_one = qsizetype(pat_length - 1);
        RandomIt2 current = first + pl_minus_one;
 
        qsizetype skip = 0;
        while (current < last - skip) {
            current += skip;
            skip = m_skiptable[hf(*current)];
            if (!skip) {
                // possible match
                while (skip < pat_length) {
                    if (!pred(hf(*(current - skip)), hf(pat_first[pl_minus_one - skip])))
                        break;
                    skip++;
                }
                if (skip > pl_minus_one) { // we have a match
                    auto match = current + 1 - skip;
                    return R{ match, match + pat_length };
                }
 
                // If we don't have a match we are a bit inefficient as we only skip by one
                // when we have the non matching char in the string.
                if (m_skiptable[hf(*(current - skip))] == pat_length)
                    skip = pat_length - skip;
                else
                    skip = 1;
            }
        }
 
        return R{ last, last };
    }
 
private:
    alignas(16) uchar m_skiptable[256];
};
} // namespace QtPrivate
 
template <Qt::CaseSensitivity CS, size_t N>
class QStaticLatin1StringMatcher
{
    static_assert(N > 2,
                  "QStaticLatin1StringMatcher makes no sense for finding a single-char pattern");
 
    QLatin1StringView m_pattern;
    using Hasher = std::conditional_t<CS == Qt::CaseSensitive, QtPrivate::QCaseSensitiveLatin1Hash,
                                      QtPrivate::QCaseInsensitiveLatin1Hash>;
    QtPrivate::q_boyer_moore_searcher<const char *, Hasher> m_searcher;
 
public:
    explicit constexpr QStaticLatin1StringMatcher(QLatin1StringView patternToMatch) noexcept
        : m_pattern(patternToMatch),
          m_searcher(patternToMatch.begin(), patternToMatch.begin() + N - 1)
    {
    }
 
    constexpr qsizetype indexIn(QLatin1StringView haystack, qsizetype from = 0) const noexcept
    { return indexIn_helper(haystack, from); }
 
    constexpr qsizetype indexIn(QStringView haystack, qsizetype from = 0) const noexcept
    { return indexIn_helper(haystack, from); }
 
private:
    template <typename String>
    constexpr qsizetype indexIn_helper(String haystack, qsizetype from = 0) const noexcept
    {
        static_assert(QtPrivate::isLatin1OrUtf16View<String>);
 
        if (from >= haystack.size())
            return -1;
 
        const auto start = [haystack]() constexpr {
            if constexpr (std::is_same_v<String, QStringView>)
                return haystack.utf16();
            else
                return haystack.begin();
        }();
        const auto begin = start + from;
        const auto end = start + haystack.size();
        const auto r = m_searcher(begin, end, m_pattern.begin(), m_pattern.end());
        return r.begin == end ? -1 : std::distance(start, r.begin);
    }
};
 
template <size_t N>
constexpr auto qMakeStaticCaseSensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
{
    return QStaticLatin1StringMatcher<Qt::CaseSensitive, N>(
            QLatin1StringView(patternToMatch, qsizetype(N) - 1));
}
 
template <size_t N>
constexpr auto
qMakeStaticCaseInsensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
{
    return QStaticLatin1StringMatcher<Qt::CaseInsensitive, N>(
            QLatin1StringView(patternToMatch, qsizetype(N) - 1));
}
#endif
 
QT_END_NAMESPACE
 
#endif // QSTATICLATIN1STRINGMATCHER_H