Revision control
Copy as Markdown
// 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 ©) : 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