qt/qtbase/src/corelib/text/qcollator.cpp

Revision control

++ // 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
++ {National Language Support}) to handle language-specific sorting,
++ which gives a different default ordering of fullwidth and halfwidth
++ characters than
++ {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