qcollator.cpp

Go to the documentation of this file.

// Copyright (C) 2021 The Qt Company Ltd.
// Copyright (C) 2013 Aleix Pol Gonzalez <aleixpol@kde.org>
// 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 "qcollator_p.h"
#include "qstringlist.h"
#include "qstring.h"
 
#include "qdebug.h"
#include "qlocale_p.h"
#include "qthreadstorage.h"
 
QT_BEGIN_NAMESPACE
QT_DEFINE_QESDP_SPECIALIZATION_DTOR(QCollatorSortKeyPrivate)
Q_LOGGING_CATEGORY(lcQCollator, "qt.core.qcollator")
 
namespace {
struct GenerationalCollator
{
    QCollator theCollator;
    int generation = QLocalePrivate::s_generation.loadRelaxed();
public:
    GenerationalCollator() = default;
    GenerationalCollator(const QCollator &copy) : theCollator(copy) {}
    QCollator &collator()
    {
        int currentGeneration = QLocalePrivate::s_generation.loadRelaxed();
        if (Q_UNLIKELY(generation != currentGeneration)) {
            // reinitialize the collator
            generation = currentGeneration;
            theCollator = QCollator();
        }
        return theCollator;
    }
};
class GenerationalCollatorHolder
    : QThreadStorage<GenerationalCollator>
{
public:
    ~GenerationalCollatorHolder()
    {
        // Delete local data when the Q_GLOBAL_STATIC is destroyed.
        // QThreadStorage's own cleanup for it runs too late, so we'd
        // "leak" in an appless program.
        clearLocalData();
    }
 
    using QThreadStorage<GenerationalCollator>::localData;
};
}
Q_GLOBAL_STATIC(GenerationalCollatorHolder, defaultCollator)
 
/*!
    \class QCollator
    \inmodule QtCore
    \brief The QCollator class compares strings according to a localized collation algorithm.
    \compares equality
 
    \since 5.2
 
    \reentrant
    \ingroup i18n
    \ingroup string-processing
    \ingroup shared
 
    QCollator is initialized with a QLocale. It can then be used to compare and
    sort strings by using the ordering appropriate for that locale.
 
    A QCollator object can be used together with template-based sorting
    algorithms, such as std::sort(), to sort a list with QString entries.
 
    \snippet code/src_corelib_text_qcollator.cpp 0
 
    In addition to the locale, several optional flags can be set that influence
    the result of the collation.
 
    \section1 POSIX fallback implementation
 
    On Unix systems, Qt is normally compiled to use ICU (except for \macos,
    where Qt defaults to using an equivalent Apple API). However, if ICU was
    not available at compile time or explicitly disabled, Qt will use a
    fallback backend that uses the POSIX API only. This backend has several
    limitations:
 
    \list
      \li Only the QLocale::c() and QLocale::system() locales are supported.
          Consult the POSIX and C Standard Library manuals for the
          \c{<locale.h>} header for more information on the system locale.
      \li caseSensitivity() is not supported: only case-sensitive collation
          can be performed.
      \li The options set via numericMode(), ignorePunctuation(), and
          options() are not supported.
    \endlist
 
    On Android systems, when not compiled to use an own copy of ICU Qt uses
    the platform-provided ICU on Android 33 and newer. On older Android versions
    it falls back to the Java Collator API, which has a few limitations:
 
    \list
      \li The IgnorePunctuation and NumericSort options are not supported.
      \li The DiacriticInsensitive option only has an effect in combination
          with CaseInsensitive also being set, using DiacriticInsensitive
          without CaseInsensitive is not supported.
    \endlist
 
    The use of any of the unsupported options will cause a warning to be
    printed to the application's output.
 
    \section1 WebAssembly implementation
 
    On WebAssembly, Qt uses the JavaScript \c{Intl.Collator} API as its
    collation backend (unless ICU is available). This supports arbitrary
    locales as well as numericMode(), caseSensitivity(), and ignorePunctuation().
    \c{Intl.Collator} provides no sort-key extraction, so sortKey() produces
    keys that delegate back to the collator when compared: their ordering
    matches compare(), but they offer none of the performance benefit that sort
    keys provide on the other backends (see QCollator::sortKey()).
*/
 
/*!
    \since 6.13
    \enum QCollator::CollationOption
 
    Options that control how strings are compared by \l QCollator.
 
    The \macos, Windows, and ICU backends support all options, with variations
    where indicated. On non-\macos Unix (including Linux), if ICU is not
    available a fallback (POSIX) backend is used, which supports none of
    these options.
 
    \value CaseInsensitive      Ignore case differences when comparing strings.
 
    \value IgnorePunctuation    Ignore punctuation and symbols when comparing strings.
 
    \value NumericSort          Sort strings containing numbers by their numeric value,
                                so that for example "file10" sorts after "file9"
                                instead of between "file1" and "file2".
 
    \value DiacriticInsensitive Ignore diacritical marks when comparing strings,
                                so that for example "e" and "é" compare as equal.
                                Depending on the locale, this may also include
                                ligature folding such as æ == ae.
                                See \l {DiacriticInsensitive behavior details}
                                below.
 
    \value WidthInsensitive     Treat CJK fullwidth and halfwidth forms of a
                                character as equivalent; for example, fullwidth
                                "Ａ１２３" and halfwidth "A123", or fullwidth
                                Katakana "カ" and halfwidth "ｶ".
                                See \l {WidthInsensitive behavior details} below.
 
    \section2 DiacriticInsensitive behavior details
 
    This option is primarily intended for search and matching, where the user
    may not type diacritics. For example, typing "resume" in a search field and
    expecting to find "résumé".
 
    The exact behavior depends on the locale and platform backend:
 
    \list
      \li Characters that are independent letters in a given alphabet are
          not treated as diacritic variants. For example, in Swedish "å",
          "ä" and "ö" are separate letters that sort after "z", so they
          do not compare equal to "a" or "o", even with this option set.
          Their position in the alphabet is also preserved. The same
          characters may behave differently in another locale: in German,
          "ö" and "ä" are treated as variants of "o" and "a" and do compare
          equal to them with this option set.
      \li Collation folding for locale-specific equivalences
          (such as å == aa in Norwegian) is locale-dependent and works
          consistently across backends. Note that this maps "å" to the
          digraph "aa", not to a single "a"; "å" is an independent letter
          and never folds to "a".
      \li Ligature folding (such as ß == ss and æ == ae) is applied on
          Windows and ICU, where the locale defines it; for example
          "æ" folds to "ae" in English but is an independent letter in
          Norwegian and does not fold. This folding is not supported by
          the \macos backend. On Windows, some ligature folding is applied
          implicitly, even without this option set.
    \endlist
 
    \section2 WidthInsensitive behavior details
 
    Chinese, Japanese and Korean (CJK) characters are wider than those of
    Latin-derived scripts. For compatibility, Unicode includes "fullwidth"
    forms of European characters that have the same width as CJK characters,
    as well as "halfwidth" forms of some CJK characters (for example,
    Katakana) that have the narrower European width. These width variants are
    formally separate characters in Unicode, but represent the same letter
    or symbol. Users may enter text using input methods that produce either
    form, and expect them to match when searching or comparing. This option
    makes the fullwidth and halfwidth forms of the same character compare
    as equal.
 
    The exact behavior depends on the platform backend:
 
    \list
      \li On ICU, width sensitivity and case sensitivity are controlled
          by the same collation strength level. As a result, in non-CJK
          locales, this option has no effect unless CaseInsensitive option
          is set. On the \macos and Windows backends, this option works
          independently of case sensitivity.
      \li In CJK locales, fullwidth and halfwidth forms may already
          compare as equal on \macos and ICU backends due to
          locale-specific collation rules, even without this option set.
          On Windows, this option must be set explicitly.
      \li The native Windows backend (without ICU) uses NLS
          (\l {https://learn.microsoft.com/en-us/windows/win32/intl/national-language-support}
          {National Language Support}) to handle language-specific sorting,
          which gives a different default ordering of fullwidth and halfwidth
          characters than
          \l {https://en.wikipedia.org/wiki/Unicode_collation_algorithm}
          {Unicode Collation Algorithm} based backends (\macos, ICU).
          Setting this option makes them compare as equal on both.
    \endlist
 
    \sa setOptions(), options()
*/
 
/*!
  \since 5.13
 
  Constructs a QCollator using the default locale's collation locale.
 
  The system locale, when used as default locale, may have a collation locale
  other than itself (e.g. on Unix, if LC_COLLATE is set differently to LANG in
  the environment). All other locales are their own collation locales.
 
  \sa setLocale(), QLocale::collation(), QLocale::setDefault()
*/
QCollator::QCollator()
    : d(nullptr)
{
}
 
/*!
    Constructs a QCollator using the given \a locale.
 
    \sa setLocale()
*/
QCollator::QCollator(const QLocale &locale)
    : d(new QCollatorPrivate(locale))
{
}
 
/*!
    Creates a copy of \a other.
*/
QCollator::QCollator(const QCollator &other)
    : d(other.d)
{
    if (d) {
        // Ensure clean, lest both copies try to init() at the same time:
        d->ensureInitialized();
        d->ref.ref();
    }
}
 
/*!
    Destroys this collator.
*/
QCollator::~QCollator()
{
    if (d && !d->ref.deref())
        delete d;
}
 
/*!
    Assigns \a other to this collator.
*/
QCollator &QCollator::operator=(const QCollator &other)
{
    if (this != &other) {
        if (d && !d->ref.deref())
            delete d;
        d = other.d;
        if (d) {
            // Ensure clean, lest both copies try to init() at the same time:
            d->ensureInitialized();
            d->ref.ref();
        }
    }
    return *this;
}
 
/*!
    \fn QCollator::QCollator(QCollator &&other)
 
    Move constructor. Moves from \a other into this collator.
 
//! [partially-formed]
    \note The moved-from object \a other is placed in a partially-formed state,
    in which the only valid operations are destruction and assignment of a new
    value.
//! [partially-formed]
*/
 
/*!
    \fn QCollator & QCollator::operator=(QCollator && other)
 
    Move-assigns \a other to this QCollator instance.
 
    \include qcollator.cpp partially-formed
*/
 
/*!
    \fn void QCollator::swap(QCollator &other)
    \memberswap{collator}
*/
 
/*!
    \fn bool QCollator::operator==(const QCollator &lhs, const QCollator &rhs) noexcept
    \fn bool QCollator::operator!=(const QCollator &lhs, const QCollator &rhs) noexcept
    \since 6.12
 
    Returns \c true if \a lhs and \a rhs use the same locale and collation
    options, otherwise returns \c false.
*/
 
bool comparesEqual(const QCollator &lhs, const QCollator &rhs) noexcept
{
    if (lhs.d == rhs.d)
        return true;
    if (!lhs.d || !rhs.d)
        return false;
 
    return lhs.d->options == rhs.d->options
        && lhs.d->locale == rhs.d->locale;
}
 
/*!
    \internal
*/
void QCollator::detach()
{
    if (!d) {
        d = new QCollatorPrivate(QLocale().collation());
        d->init();
    } else if (d->ref.loadRelaxed() != 1) {
        QCollatorPrivate *x = new QCollatorPrivate(d->locale);
        x->options = d->options;
        if (!d->ref.deref())
            delete d;
        d = x;
    }
    // All callers need this, because about to modify the object:
    d->dirty = true;
}
 
/*!
    Sets the locale of the collator to \a locale.
 
    \sa locale()
*/
void QCollator::setLocale(const QLocale &locale)
{
    if (locale == this->locale())
        return;
 
    detach();
    d->locale = locale;
}
 
/*!
    Returns the locale of the collator.
 
    Unless supplied to the constructor or by calling setLocale(), the system's
    default collation locale is used.
 
    \sa setLocale(), QLocale::collation()
*/
QLocale QCollator::locale() const
{
    return d ? d->locale : QLocale().collation();
}
 
/*!
    Sets the case-sensitivity of the collator to \a cs.
 
    \sa caseSensitivity()
*/
void QCollator::setCaseSensitivity(Qt::CaseSensitivity cs)
{
    if (cs == caseSensitivity())
        return;
 
    detach();
    d->options.setFlag(CollationOption::CaseInsensitive, cs == Qt::CaseInsensitive);
}
 
/*!
    Returns case sensitivity of the collator.
 
    This defaults to case-sensitive until set.
 
    \note In the C locale, when case-sensitive, all lower-case letters sort
    after all upper-case letters, where most locales sort each lower-case letter
    either immediately before or immediately after its upper-case partner.  Thus
    "Zap" sorts before "ape" in the C locale but after in most others.
 
    \sa setCaseSensitivity()
*/
Qt::CaseSensitivity QCollator::caseSensitivity() const
{
    return d && d->options.testFlag(CollationOption::CaseInsensitive) ? Qt::CaseInsensitive
                                                                      : Qt::CaseSensitive;
}
 
/*!
    Enables numeric sorting mode when \a on is \c true.
 
    \sa numericMode()
*/
void QCollator::setNumericMode(bool on)
{
    if (on == numericMode())
        return;
 
    detach();
    d->options.setFlag(CollationOption::NumericSort, on);
}
 
/*!
    Returns \c true if numeric sorting is enabled, \c false otherwise.
 
    When \c true, numerals are recognized as numbers and sorted in arithmetic
    order; for example, 100 sortes after 99. When \c false, numbers are sorted
    in lexical order, so that 100 sorts before 99 (because 1 is before 9). By
    default, this option is disabled.
 
    \sa setNumericMode()
*/
bool QCollator::numericMode() const
{
    return d && d->options.testFlag(CollationOption::NumericSort);
}
 
/*!
    Ignores punctuation and symbols if \a on is \c true, attends to them if \c false.
 
    \sa ignorePunctuation()
*/
void QCollator::setIgnorePunctuation(bool on)
{
    if (on == ignorePunctuation())
        return;
 
    detach();
    d->options.setFlag(CollationOption::IgnorePunctuation, on);
}
 
/*!
    Returns whether punctuation and symbols are ignored when collating.
 
    When \c true, strings are compared as if all punctuation and symbols were
    removed from each string.
 
    \sa setIgnorePunctuation()
*/
bool QCollator::ignorePunctuation() const
{
    return d && d->options.testFlag(CollationOption::IgnorePunctuation);
}
 
/*!
    \since 6.13
    Sets the collation options to \a options.
    This allows configuring multiple collation settings at once.
 
    \note In the C locale, the collation options have no effect.
    Use a specific locale to enable locale-aware collation.
 
    \sa options(), CollationOption
*/
void QCollator::setOptions(CollationOptions options)
{
    if (d && d->options == options)
        return;
    detach();
    d->options = options;
}
 
/*!
    \since 6.13
    Returns the collation options currently set on the collator.
 
    \sa setOptions(), CollationOption
*/
QCollator::CollationOptions QCollator::options() const
{
    return d ? d->options : CollationOptions{};
}
 
/*!
    \since 5.13
    \fn bool QCollator::operator()(QStringView s1, QStringView s2) const
 
    A QCollator can be used as the comparison function of a sorting algorithm.
    It returns \c true if \a s1 sorts before \a s2, otherwise \c false.
 
    \sa compare()
*/
 
/*!
    \since 5.13
    \fn int QCollator::compare(QStringView s1, QStringView s2) const
 
    Compares \a s1 with \a s2.
 
    Returns a negative integer if \a s1 is less than \a s2, a positive integer
    if it is greater than \a s2, and zero if they are equal.
*/
 
/*!
    \fn bool QCollator::operator()(const QString &s1, const QString &s2) const
    \overload
    \since 5.2
*/
 
/*!
    \fn int QCollator::compare(const QString &s1, const QString &s2) const
    \overload
    \since 5.2
*/
 
/*!
    \fn int QCollator::compare(const QChar *s1, qsizetype len1, const QChar *s2, qsizetype len2) const
    \overload
    \since 5.2
 
    Compares \a s1 with \a s2. \a len1 and \a len2 specify the lengths of the
    QChar arrays pointed to by \a s1 and \a s2.
 
    Returns a negative integer if \a s1 is less than \a s2, a positive integer
    if it is greater than \a s2, and zero if they are equal.
 
 
    \note In Qt versions prior to 6.4, the length arguments were of type
    \c{int}, not \c{qsizetype}.
*/
 
/*!
    \since 6.3
 
    Compares the strings \a s1 and \a s2, returning their sorting order. This
    function performs the same operation as compare() on a default-constructed
    QCollator object.
 
    \sa compare(), defaultSortKey()
*/
int QCollator::defaultCompare(QStringView s1, QStringView s2)
{
    return defaultCollator->localData().collator().compare(s1, s2);
}
 
/*!
    \since 6.3
 
    Returns the sort key for the string \a key. This function performs the same
    operation as sortKey() on a default-constructed QCollator object.
 
    \sa sortKey(), defaultCompare()
*/
QCollatorSortKey QCollator::defaultSortKey(QStringView key)
{
    return defaultCollator->localData().collator().sortKey(key.toString());
}
 
/*!
    \fn QCollatorSortKey QCollator::sortKey(const QString &string) const
 
    Returns a sortKey for \a string.
 
    Creating the sort key is usually somewhat slower, than using the compare()
    methods directly. But if the string is compared repeatedly (e.g. when
    sorting a whole list of strings), it's usually faster to create the sort
    keys for each string and then sort using the keys.
 
    \note Not supported with the C (a.k.a. POSIX) locale on Darwin.
    \note Does not provide a performance improvement on Qt for WebAssembly
    due to native API limitations.
*/
 
/*!
    \class QCollatorSortKey
    \inmodule QtCore
    \brief The QCollatorSortKey class can be used to speed up string collation.
    \compares weak
 
    \since 5.2
 
    The QCollatorSortKey class is always created by QCollator::sortKey() and is
    used for fast strings collation, for example when collating many strings.
 
    \reentrant
    \ingroup i18n
    \ingroup string-processing
    \ingroup shared
 
    \sa QCollator, QCollator::sortKey(), compare()
*/
 
/*!
    \internal
*/
QCollatorSortKey::QCollatorSortKey(QCollatorSortKeyPrivate *d)
    : d(d)
{
}
 
/*!
    Constructs a copy of the \a other collator key.
*/
QCollatorSortKey::QCollatorSortKey(const QCollatorSortKey &other)
    : d(other.d)
{
}
 
/*!
    \since 6.8
    \fn QCollatorSortKey::QCollatorSortKey(QCollatorSortKey &&other)
    Move-constructs a new QCollatorSortKey from \a other.
 
    \include qcollator.cpp partially-formed
*/
 
/*!
    Destroys the collator key.
*/
QCollatorSortKey::~QCollatorSortKey()
{
}
 
/*!
    Assigns \a other to this collator key.
*/
QCollatorSortKey& QCollatorSortKey::operator=(const QCollatorSortKey &other)
{
    if (this != &other) {
        d = other.d;
    }
    return *this;
}
 
/*!
    \fn QCollatorSortKey &QCollatorSortKey::operator=(QCollatorSortKey && other)
 
    Move-assigns \a other to this QCollatorSortKey instance.
 
    \include qcollator.cpp partially-formed
*/
 
/*!
    \fn bool QCollatorSortKey::operator<(const QCollatorSortKey &lhs, const QCollatorSortKey &rhs)
    \fn bool QCollatorSortKey::operator<=(const QCollatorSortKey &lhs, const QCollatorSortKey &rhs)
    \fn bool QCollatorSortKey::operator>(const QCollatorSortKey &lhs, const QCollatorSortKey &rhs)
    \fn bool QCollatorSortKey::operator>=(const QCollatorSortKey &lhs, const QCollatorSortKey &rhs)
    \fn bool QCollatorSortKey::operator==(const QCollatorSortKey &lhs, const QCollatorSortKey &rhs)
    \fn bool QCollatorSortKey::operator!=(const QCollatorSortKey &lhs, const QCollatorSortKey &rhs)
    \since 6.12
 
    Both keys must have been created by the same QCollator's sortKey(). Compares
    \a lhs and \a rhs according to the QCollator that created them.
 
    \sa QCollatorSortKey::compare()
*/
 
/*!
    \fn void QCollatorSortKey::swap(QCollatorSortKey & other)
    \memberswap{collator key}
*/
 
/*!
    \fn int QCollatorSortKey::compare(const QCollatorSortKey &otherKey) const noexcept
 
    Compares this key to \a otherKey, which must have been created by the same
    QCollator's sortKey() as this key. The comparison is performed in accordance
    with that QCollator's sort order.
 
    Returns a negative value if this key sorts before \a otherKey, 0 if the
    two keys are equal, or a positive value if this key sorts after \a otherKey.
 
    \sa operator==(), operator!=(), operator<(), operator<=(),
        operator>(), operator>=()
*/
 
QT_END_NAMESPACE