1	/****************************************************************************
2	**
3	** Copyright (C) 2016 The Qt Company Ltd.
4	** Contact: https://www.qt.io/licensing/
5	**
6	** This file is part of the QtWidgets module of the Qt Toolkit.
7	**
8	** $QT_BEGIN_LICENSE:LGPL$
9	** Commercial License Usage
10	** Licensees holding valid commercial Qt licenses may use this file in
11	** accordance with the commercial license agreement provided with the
12	** Software or, alternatively, in accordance with the terms contained in
13	** a written agreement between you and The Qt Company. For licensing terms
14	** and conditions see https://www.qt.io/terms-conditions. For further
15	** information use the contact form at https://www.qt.io/contact-us.
16	**
17	** GNU Lesser General Public License Usage
18	** Alternatively, this file may be used under the terms of the GNU Lesser
19	** General Public License version 3 as published by the Free Software
20	** Foundation and appearing in the file LICENSE.LGPL3 included in the
21	** packaging of this file. Please review the following information to
22	** ensure the GNU Lesser General Public License version 3 requirements
23	** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24	**
25	** GNU General Public License Usage
26	** Alternatively, this file may be used under the terms of the GNU
27	** General Public License version 2.0 or (at your option) the GNU General
28	** Public license version 3 or any later version approved by the KDE Free
29	** Qt Foundation. The licenses are as published by the Free Software
30	** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31	** included in the packaging of this file. Please review the following
32	** information to ensure the GNU General Public License requirements will
33	** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34	** https://www.gnu.org/licenses/gpl-3.0.html.
35	**
36	** $QT_END_LICENSE$
37	**
38	****************************************************************************/
39
40	/*!
41	\class QCompleter
42	\brief The QCompleter class provides completions based on an item model.
43	\since 4.2
44
45	\inmodule QtWidgets
46
47	You can use QCompleter to provide auto completions in any Qt
48	widget, such as QLineEdit and QComboBox.
49	When the user starts typing a word, QCompleter suggests possible ways of
50	completing the word, based on a word list. The word list is
51	provided as a QAbstractItemModel. (For simple applications, where
52	the word list is static, you can pass a QStringList to
53	QCompleter's constructor.)
54
55	\tableofcontents
56
57	\section1 Basic Usage
58
59	A QCompleter is used typically with a QLineEdit or QComboBox.
60	For example, here's how to provide auto completions from a simple
61	word list in a QLineEdit:
62
63	\snippet code/src_gui_util_qcompleter.cpp 0
64
65	A QFileSystemModel can be used to provide auto completion of file names.
66	For example:
67
68	\snippet code/src_gui_util_qcompleter.cpp 1
69
70	To set the model on which QCompleter should operate, call
71	setModel(). By default, QCompleter will attempt to match the \l
72	{completionPrefix}{completion prefix} (i.e., the word that the
73	user has started typing) against the Qt::EditRole data stored in
74	column 0 in the model case sensitively. This can be changed
75	using setCompletionRole(), setCompletionColumn(), and
76	setCaseSensitivity().
77
78	If the model is sorted on the column and role that are used for completion,
79	you can call setModelSorting() with either
80	QCompleter::CaseSensitivelySortedModel or
81	QCompleter::CaseInsensitivelySortedModel as the argument. On large models,
82	this can lead to significant performance improvements, because QCompleter
83	can then use binary search instead of linear search. The binary search only
84	works when the filterMode is Qt::MatchStartsWith.
85
86	The model can be a \l{QAbstractListModel}{list model},
87	a \l{QAbstractTableModel}{table model}, or a
88	\l{QAbstractItemModel}{tree model}. Completion on tree models
89	is slightly more involved and is covered in the \l{Handling
90	Tree Models} section below.
91
92	The completionMode() determines the mode used to provide completions to
93	the user.
94
95	\section1 Iterating Through Completions
96
97	To retrieve a single candidate string, call setCompletionPrefix()
98	with the text that needs to be completed and call
99	currentCompletion(). You can iterate through the list of
100	completions as below:
101
102	\snippet code/src_gui_util_qcompleter.cpp 2
103
104	completionCount() returns the total number of completions for the
105	current prefix. completionCount() should be avoided when possible,
106	since it requires a scan of the entire model.
107
108	\section1 The Completion Model
109
110	completionModel() return a list model that contains all possible
111	completions for the current completion prefix, in the order in which
112	they appear in the model. This model can be used to display the current
113	completions in a custom view. Calling setCompletionPrefix() automatically
114	refreshes the completion model.
115
116	\section1 Handling Tree Models
117
118	QCompleter can look for completions in tree models, assuming
119	that any item (or sub-item or sub-sub-item) can be unambiguously
120	represented as a string by specifying the path to the item. The
121	completion is then performed one level at a time.
122
123	Let's take the example of a user typing in a file system path.
124	The model is a (hierarchical) QFileSystemModel. The completion
125	occurs for every element in the path. For example, if the current
126	text is \c C:\Wind, QCompleter might suggest \c Windows to
127	complete the current path element. Similarly, if the current text
128	is \c C:\Windows\Sy, QCompleter might suggest \c System.
129
130	For this kind of completion to work, QCompleter needs to be able to
131	split the path into a list of strings that are matched at each level.
132	For \c C:\Windows\Sy, it needs to be split as "C:", "Windows" and "Sy".
133	The default implementation of splitPath(), splits the completionPrefix
134	using QDir::separator() if the model is a QFileSystemModel.
135
136	To provide completions, QCompleter needs to know the path from an index.
137	This is provided by pathFromIndex(). The default implementation of
138	pathFromIndex(), returns the data for the \l{Qt::EditRole}{edit role}
139	for list models and the absolute file path if the mode is a QFileSystemModel.
140
141	\sa QAbstractItemModel, QLineEdit, QComboBox, {Completer Example}
142	*/
143
144	#include "qcompleter_p.h"
145
146	#include "QtWidgets/qscrollbar.h"
147	#include "QtCore/qdir.h"
148	#if QT_CONFIG(stringlistmodel)
149	#include "QtCore/qstringlistmodel.h"
150	#endif
151	#if QT_CONFIG(dirmodel)
152	#include "QtWidgets/qdirmodel.h"
153	#endif
154	#if QT_CONFIG(filesystemmodel)
155	#include "QtWidgets/qfilesystemmodel.h"
156	#endif
157	#include "QtWidgets/qheaderview.h"
158	#if QT_CONFIG(listview)
159	#include "QtWidgets/qlistview.h"
160	#endif
161	#include "QtWidgets/qapplication.h"
162	#include "QtGui/qevent.h"
163	#include "QtWidgets/qdesktopwidget.h"
164	#include <private/qapplication_p.h>
165	#include <private/qdesktopwidget_p.h>
166	#if QT_CONFIG(lineedit)
167	#include "QtWidgets/qlineedit.h"
168	#endif
169	#include "QtCore/qdir.h"
170
171	QT_BEGIN_NAMESPACE
172
173	QCompletionModel::QCompletionModel(QCompleterPrivate *c, QObject *parent)
174	: QAbstractProxyModel(*new QCompletionModelPrivate, parent),
175	c(c), showAll(false)
176	{
177	createEngine();
178	}
179
180	int QCompletionModel::columnCount(const QModelIndex &) const
181	{
182	Q_D(const QCompletionModel);
183	return d->model->columnCount();
184	}
185
186	void QCompletionModel::setSourceModel(QAbstractItemModel *source)
187	{
188	bool hadModel = (sourceModel() != nullptr);
189
190	if (hadModel)
191	QObject::disconnect(sender: sourceModel(), signal: nullptr, receiver: this, member: nullptr);
192
193	QAbstractProxyModel::setSourceModel(source);
194
195	if (source) {
196	// TODO: Optimize updates in the source model
197	connect(sender: source, SIGNAL(modelReset()), receiver: this, SLOT(invalidate()));
198	connect(sender: source, SIGNAL(destroyed()), receiver: this, SLOT(modelDestroyed()));
199	connect(sender: source, SIGNAL(layoutChanged()), receiver: this, SLOT(invalidate()));
200	connect(sender: source, SIGNAL(rowsInserted(QModelIndex,int,int)), receiver: this, SLOT(rowsInserted()));
201	connect(sender: source, SIGNAL(rowsRemoved(QModelIndex,int,int)), receiver: this, SLOT(invalidate()));
202	connect(sender: source, SIGNAL(columnsInserted(QModelIndex,int,int)), receiver: this, SLOT(invalidate()));
203	connect(sender: source, SIGNAL(columnsRemoved(QModelIndex,int,int)), receiver: this, SLOT(invalidate()));
204	connect(sender: source, SIGNAL(dataChanged(QModelIndex,QModelIndex)), receiver: this, SLOT(invalidate()));
205	}
206
207	invalidate();
208	}
209
210	void QCompletionModel::createEngine()
211	{
212	bool sortedEngine = false;
213	if (c->filterMode == Qt::MatchStartsWith) {
214	switch (c->sorting) {
215	case QCompleter::UnsortedModel:
216	sortedEngine = false;
217	break;
218	case QCompleter::CaseSensitivelySortedModel:
219	sortedEngine = c->cs == Qt::CaseSensitive;
220	break;
221	case QCompleter::CaseInsensitivelySortedModel:
222	sortedEngine = c->cs == Qt::CaseInsensitive;
223	break;
224	}
225	}
226
227	if (sortedEngine)
228	engine.reset(other: new QSortedModelEngine(c));
229	else
230	engine.reset(other: new QUnsortedModelEngine(c));
231	}
232
233	QModelIndex QCompletionModel::mapToSource(const QModelIndex& index) const
234	{
235	Q_D(const QCompletionModel);
236	if (!index.isValid())
237	return engine->curParent;
238
239	int row;
240	QModelIndex parent = engine->curParent;
241	if (!showAll) {
242	if (!engine->matchCount())
243	return QModelIndex();
244	Q_ASSERT(index.row() < engine->matchCount());
245	QIndexMapper& rootIndices = engine->historyMatch.indices;
246	if (index.row() < rootIndices.count()) {
247	row = rootIndices[index.row()];
248	parent = QModelIndex();
249	} else {
250	row = engine->curMatch.indices[index.row() - rootIndices.count()];
251	}
252	} else {
253	row = index.row();
254	}
255
256	return d->model->index(row, column: index.column(), parent);
257	}
258
259	QModelIndex QCompletionModel::mapFromSource(const QModelIndex& idx) const
260	{
261	if (!idx.isValid())
262	return QModelIndex();
263
264	int row = -1;
265	if (!showAll) {
266	if (!engine->matchCount())
267	return QModelIndex();
268
269	QIndexMapper& rootIndices = engine->historyMatch.indices;
270	if (idx.parent().isValid()) {
271	if (idx.parent() != engine->curParent)
272	return QModelIndex();
273	} else {
274	row = rootIndices.indexOf(x: idx.row());
275	if (row == -1 && engine->curParent.isValid())
276	return QModelIndex(); // source parent and our parent don't match
277	}
278
279	if (row == -1) {
280	QIndexMapper& indices = engine->curMatch.indices;
281	engine->filterOnDemand(idx.row() - indices.last());
282	row = indices.indexOf(x: idx.row()) + rootIndices.count();
283	}
284
285	if (row == -1)
286	return QModelIndex();
287	} else {
288	if (idx.parent() != engine->curParent)
289	return QModelIndex();
290	row = idx.row();
291	}
292
293	return createIndex(arow: row, acolumn: idx.column());
294	}
295
296	bool QCompletionModel::setCurrentRow(int row)
297	{
298	if (row < 0 || !engine->matchCount())
299	return false;
300
301	if (row >= engine->matchCount())
302	engine->filterOnDemand(row + 1 - engine->matchCount());
303
304	if (row >= engine->matchCount()) // invalid row
305	return false;
306
307	engine->curRow = row;
308	return true;
309	}
310
311	QModelIndex QCompletionModel::currentIndex(bool sourceIndex) const
312	{
313	if (!engine->matchCount())
314	return QModelIndex();
315
316	int row = engine->curRow;
317	if (showAll)
318	row = engine->curMatch.indices[engine->curRow];
319
320	QModelIndex idx = createIndex(arow: row, acolumn: c->column);
321	if (!sourceIndex)
322	return idx;
323	return mapToSource(index: idx);
324	}
325
326	QModelIndex QCompletionModel::index(int row, int column, const QModelIndex& parent) const
327	{
328	Q_D(const QCompletionModel);
329	if (row < 0 || column < 0 || column >= columnCount(parent) || parent.isValid())
330	return QModelIndex();
331
332	if (!showAll) {
333	if (!engine->matchCount())
334	return QModelIndex();
335	if (row >= engine->historyMatch.indices.count()) {
336	int want = row + 1 - engine->matchCount();
337	if (want > 0)
338	engine->filterOnDemand(want);
339	if (row >= engine->matchCount())
340	return QModelIndex();
341	}
342	} else {
343	if (row >= d->model->rowCount(parent: engine->curParent))
344	return QModelIndex();
345	}
346
347	return createIndex(arow: row, acolumn: column);
348	}
349
350	int QCompletionModel::completionCount() const
351	{
352	if (!engine->matchCount())
353	return 0;
354
355	engine->filterOnDemand(INT_MAX);
356	return engine->matchCount();
357	}
358
359	int QCompletionModel::rowCount(const QModelIndex &parent) const
360	{
361	Q_D(const QCompletionModel);
362	if (parent.isValid())
363	return 0;
364
365	if (showAll) {
366	// Show all items below current parent, even if we have no valid matches
367	if (engine->curParts.count() != 1 && !engine->matchCount()
368	&& !engine->curParent.isValid())
369	return 0;
370	return d->model->rowCount(parent: engine->curParent);
371	}
372
373	return completionCount();
374	}
375
376	void QCompletionModel::setFiltered(bool filtered)
377	{
378	if (showAll == !filtered)
379	return;
380	beginResetModel();
381	showAll = !filtered;
382	endResetModel();
383	}
384
385	bool QCompletionModel::hasChildren(const QModelIndex &parent) const
386	{
387	Q_D(const QCompletionModel);
388	if (parent.isValid())
389	return false;
390
391	if (showAll)
392	return d->model->hasChildren(parent: mapToSource(index: parent));
393
394	if (!engine->matchCount())
395	return false;
396
397	return true;
398	}
399
400	QVariant QCompletionModel::data(const QModelIndex& index, int role) const
401	{
402	Q_D(const QCompletionModel);
403	return d->model->data(index: mapToSource(index), role);
404	}
405
406	void QCompletionModel::modelDestroyed()
407	{
408	QAbstractProxyModel::setSourceModel(nullptr); // switch to static empty model
409	invalidate();
410	}
411
412	void QCompletionModel::rowsInserted()
413	{
414	invalidate();
415	emit rowsAdded();
416	}
417
418	void QCompletionModel::invalidate()
419	{
420	engine->cache.clear();
421	filter(parts: engine->curParts);
422	}
423
424	void QCompletionModel::filter(const QStringList& parts)
425	{
426	Q_D(QCompletionModel);
427	beginResetModel();
428	engine->filter(parts);
429	endResetModel();
430
431	if (d->model->canFetchMore(parent: engine->curParent))
432	d->model->fetchMore(parent: engine->curParent);
433	}
434
435	//////////////////////////////////////////////////////////////////////////////
436	void QCompletionEngine::filter(const QStringList& parts)
437	{
438	const QAbstractItemModel *model = c->proxy->sourceModel();
439	curParts = parts;
440	if (curParts.isEmpty())
441	curParts.append(t: QString());
442
443	curRow = -1;
444	curParent = QModelIndex();
445	curMatch = QMatchData();
446	historyMatch = filterHistory();
447
448	if (!model)
449	return;
450
451	QModelIndex parent;
452	for (int i = 0; i < curParts.count() - 1; i++) {
453	QString part = curParts.at(i);
454	int emi = filter(part, parent, -1).exactMatchIndex;
455	if (emi == -1)
456	return;
457	parent = model->index(row: emi, column: c->column, parent);
458	}
459
460	// Note that we set the curParent to a valid parent, even if we have no matches
461	// When filtering is disabled, we show all the items under this parent
462	curParent = parent;
463	if (curParts.constLast().isEmpty())
464	curMatch = QMatchData(QIndexMapper(0, model->rowCount(parent: curParent) - 1), -1, false);
465	else
466	curMatch = filter(curParts.constLast(), curParent, 1); // build at least one
467	curRow = curMatch.isValid() ? 0 : -1;
468	}
469
470	QMatchData QCompletionEngine::filterHistory()
471	{
472	QAbstractItemModel *source = c->proxy->sourceModel();
473	if (curParts.count() <= 1 || c->proxy->showAll || !source)
474	return QMatchData();
475
476	#if QT_CONFIG(dirmodel) && QT_DEPRECATED_SINCE(5, 15)
477	const bool isDirModel = (qobject_cast<QDirModel *>(object: source) != nullptr);
478	#else
479	const bool isDirModel = false;
480	#endif
481	Q_UNUSED(isDirModel)
482	#if QT_CONFIG(filesystemmodel)
483	const bool isFsModel = (qobject_cast<QFileSystemModel *>(object: source) != nullptr);
484	#else
485	const bool isFsModel = false;
486	#endif
487	Q_UNUSED(isFsModel)
488	QVector<int> v;
489	QIndexMapper im(v);
490	QMatchData m(im, -1, true);
491
492	for (int i = 0; i < source->rowCount(); i++) {
493	QString str = source->index(row: i, column: c->column).data().toString();
494	if (str.startsWith(s: c->prefix, cs: c->cs)
495	#if !defined(Q_OS_WIN)
496	&& ((!isFsModel && !isDirModel) || QDir::toNativeSeparators(pathName: str) != QDir::separator())
497	#endif
498	)
499	m.indices.append(x: i);
500	}
501	return m;
502	}
503
504	// Returns a match hint from the cache by chopping the search string
505	bool QCompletionEngine::matchHint(const QString &part, const QModelIndex &parent, QMatchData *hint) const
506	{
507	if (part.isEmpty())
508	return false; // early out to avoid cache[parent] lookup costs
509
510	const auto cit = cache.find(akey: parent);
511	if (cit == cache.end())
512	return false;
513
514	const CacheItem& map = *cit;
515	const auto mapEnd = map.end();
516
517	QString key = c->cs == Qt::CaseInsensitive ? part.toLower() : part;
518
519	while (!key.isEmpty()) {
520	key.chop(n: 1);
521	const auto it = map.find(akey: key);
522	if (it != mapEnd) {
523	*hint = *it;
524	return true;
525	}
526	}
527
528	return false;
529	}
530
531	bool QCompletionEngine::lookupCache(const QString &part, const QModelIndex &parent, QMatchData *m) const
532	{
533	if (part.isEmpty())
534	return false; // early out to avoid cache[parent] lookup costs
535
536	const auto cit = cache.find(akey: parent);
537	if (cit == cache.end())
538	return false;
539
540	const CacheItem& map = *cit;
541
542	const QString key = c->cs == Qt::CaseInsensitive ? part.toLower() : part;
543
544	const auto it = map.find(akey: key);
545	if (it == map.end())
546	return false;
547
548	*m = it.value();
549	return true;
550	}
551
552	// When the cache size exceeds 1MB, it clears out about 1/2 of the cache.
553	void QCompletionEngine::saveInCache(QString part, const QModelIndex& parent, const QMatchData& m)
554	{
555	if (c->filterMode == Qt::MatchEndsWith)
556	return;
557	QMatchData old = cache[parent].take(akey: part);
558	cost = cost + m.indices.cost() - old.indices.cost();
559	if (cost * sizeof(int) > 1024 * 1024) {
560	QMap<QModelIndex, CacheItem>::iterator it1 = cache.begin();
561	while (it1 != cache.end()) {
562	CacheItem& ci = it1.value();
563	int sz = ci.count()/2;
564	QMap<QString, QMatchData>::iterator it2 = ci.begin();
565	int i = 0;
566	while (it2 != ci.end() && i < sz) {
567	cost -= it2.value().indices.cost();
568	it2 = ci.erase(it: it2);
569	i++;
570	}
571	if (ci.count() == 0) {
572	it1 = cache.erase(it: it1);
573	} else {
574	++it1;
575	}
576	}
577	}
578
579	if (c->cs == Qt::CaseInsensitive)
580	part = std::move(part).toLower();
581	cache[parent][part] = m;
582	}
583
584	///////////////////////////////////////////////////////////////////////////////////
585	QIndexMapper QSortedModelEngine::indexHint(QString part, const QModelIndex& parent, Qt::SortOrder order)
586	{
587	const QAbstractItemModel *model = c->proxy->sourceModel();
588
589	if (c->cs == Qt::CaseInsensitive)
590	part = std::move(part).toLower();
591
592	const CacheItem& map = cache[parent];
593
594	// Try to find a lower and upper bound for the search from previous results
595	int to = model->rowCount(parent) - 1;
596	int from = 0;
597	const CacheItem::const_iterator it = map.lowerBound(akey: part);
598
599	// look backward for first valid hint
600	for (CacheItem::const_iterator it1 = it; it1 != map.constBegin();) {
601	--it1;
602	const QMatchData& value = it1.value();
603	if (value.isValid()) {
604	if (order == Qt::AscendingOrder) {
605	from = value.indices.last() + 1;
606	} else {
607	to = value.indices.first() - 1;
608	}
609	break;
610	}
611	}
612
613	// look forward for first valid hint
614	for(CacheItem::const_iterator it2 = it; it2 != map.constEnd(); ++it2) {
615	const QMatchData& value = it2.value();
616	if (value.isValid() && !it2.key().startsWith(s: part)) {
617	if (order == Qt::AscendingOrder) {
618	to = value.indices.first() - 1;
619	} else {
620	from = value.indices.first() + 1;
621	}
622	break;
623	}
624	}
625
626	return QIndexMapper(from, to);
627	}
628
629	Qt::SortOrder QSortedModelEngine::sortOrder(const QModelIndex &parent) const
630	{
631	const QAbstractItemModel *model = c->proxy->sourceModel();
632
633	int rowCount = model->rowCount(parent);
634	if (rowCount < 2)
635	return Qt::AscendingOrder;
636	QString first = model->data(index: model->index(row: 0, column: c->column, parent), role: c->role).toString();
637	QString last = model->data(index: model->index(row: rowCount - 1, column: c->column, parent), role: c->role).toString();
638	return QString::compare(s1: first, s2: last, cs: c->cs) <= 0 ? Qt::AscendingOrder : Qt::DescendingOrder;
639	}
640
641	QMatchData QSortedModelEngine::filter(const QString& part, const QModelIndex& parent, int)
642	{
643	const QAbstractItemModel *model = c->proxy->sourceModel();
644
645	QMatchData hint;
646	if (lookupCache(part, parent, m: &hint))
647	return hint;
648
649	QIndexMapper indices;
650	Qt::SortOrder order = sortOrder(parent);
651
652	if (matchHint(part, parent, hint: &hint)) {
653	if (!hint.isValid())
654	return QMatchData();
655	indices = hint.indices;
656	} else {
657	indices = indexHint(part, parent, order);
658	}
659
660	// binary search the model within 'indices' for 'part' under 'parent'
661	int high = indices.to() + 1;
662	int low = indices.from() - 1;
663	int probe;
664	QModelIndex probeIndex;
665	QString probeData;
666
667	while (high - low > 1)
668	{
669	probe = (high + low) / 2;
670	probeIndex = model->index(row: probe, column: c->column, parent);
671	probeData = model->data(index: probeIndex, role: c->role).toString();
672	const int cmp = QString::compare(s1: probeData, s2: part, cs: c->cs);
673	if ((order == Qt::AscendingOrder && cmp >= 0)
674	|| (order == Qt::DescendingOrder && cmp < 0)) {
675	high = probe;
676	} else {
677	low = probe;
678	}
679	}
680
681	if ((order == Qt::AscendingOrder && low == indices.to())
682	|| (order == Qt::DescendingOrder && high == indices.from())) { // not found
683	saveInCache(part, parent, m: QMatchData());
684	return QMatchData();
685	}
686
687	probeIndex = model->index(row: order == Qt::AscendingOrder ? low+1 : high-1, column: c->column, parent);
688	probeData = model->data(index: probeIndex, role: c->role).toString();
689	if (!probeData.startsWith(s: part, cs: c->cs)) {
690	saveInCache(part, parent, m: QMatchData());
691	return QMatchData();
692	}
693
694	const bool exactMatch = QString::compare(s1: probeData, s2: part, cs: c->cs) == 0;
695	int emi = exactMatch ? (order == Qt::AscendingOrder ? low+1 : high-1) : -1;
696
697	int from = 0;
698	int to = 0;
699	if (order == Qt::AscendingOrder) {
700	from = low + 1;
701	high = indices.to() + 1;
702	low = from;
703	} else {
704	to = high - 1;
705	low = indices.from() - 1;
706	high = to;
707	}
708
709	while (high - low > 1)
710	{
711	probe = (high + low) / 2;
712	probeIndex = model->index(row: probe, column: c->column, parent);
713	probeData = model->data(index: probeIndex, role: c->role).toString();
714	const bool startsWith = probeData.startsWith(s: part, cs: c->cs);
715	if ((order == Qt::AscendingOrder && startsWith)
716	|| (order == Qt::DescendingOrder && !startsWith)) {
717	low = probe;
718	} else {
719	high = probe;
720	}
721	}
722
723	QMatchData m(order == Qt::AscendingOrder ? QIndexMapper(from, high - 1) : QIndexMapper(low+1, to), emi, false);
724	saveInCache(part, parent, m);
725	return m;
726	}
727
728	////////////////////////////////////////////////////////////////////////////////////////
729	int QUnsortedModelEngine::buildIndices(const QString& str, const QModelIndex& parent, int n,
730	const QIndexMapper& indices, QMatchData* m)
731	{
732	Q_ASSERT(m->partial);
733	Q_ASSERT(n != -1 || m->exactMatchIndex == -1);
734	const QAbstractItemModel *model = c->proxy->sourceModel();
735	int i, count = 0;
736
737	for (i = 0; i < indices.count() && count != n; ++i) {
738	QModelIndex idx = model->index(row: indices[i], column: c->column, parent);
739
740	if (!(model->flags(index: idx) & Qt::ItemIsSelectable))
741	continue;
742
743	QString data = model->data(index: idx, role: c->role).toString();
744
745	switch (c->filterMode) {
746	case Qt::MatchStartsWith:
747	if (!data.startsWith(s: str, cs: c->cs))
748	continue;
749	break;
750	case Qt::MatchContains:
751	if (!data.contains(s: str, cs: c->cs))
752	continue;
753	break;
754	case Qt::MatchEndsWith:
755	if (!data.endsWith(s: str, cs: c->cs))
756	continue;
757	break;
758	case Qt::MatchExactly:
759	case Qt::MatchFixedString:
760	case Qt::MatchCaseSensitive:
761	QT_WARNING_PUSH
762	QT_WARNING_DISABLE_DEPRECATED
763	case Qt::MatchRegExp:
764	QT_WARNING_POP
765	case Qt::MatchWildcard:
766	case Qt::MatchWrap:
767	case Qt::MatchRecursive:
768	Q_UNREACHABLE();
769	break;
770	}
771	m->indices.append(x: indices[i]);
772	++count;
773	if (m->exactMatchIndex == -1 && QString::compare(s1: data, s2: str, cs: c->cs) == 0) {
774	m->exactMatchIndex = indices[i];
775	if (n == -1)
776	return indices[i];
777	}
778	}
779	return indices[i-1];
780	}
781
782	void QUnsortedModelEngine::filterOnDemand(int n)
783	{
784	Q_ASSERT(matchCount());
785	if (!curMatch.partial)
786	return;
787	Q_ASSERT(n >= -1);
788	const QAbstractItemModel *model = c->proxy->sourceModel();
789	int lastRow = model->rowCount(parent: curParent) - 1;
790	QIndexMapper im(curMatch.indices.last() + 1, lastRow);
791	int lastIndex = buildIndices(str: curParts.constLast(), parent: curParent, n, indices: im, m: &curMatch);
792	curMatch.partial = (lastRow != lastIndex);
793	saveInCache(part: curParts.constLast(), parent: curParent, m: curMatch);
794	}
795
796	QMatchData QUnsortedModelEngine::filter(const QString& part, const QModelIndex& parent, int n)
797	{
798	QMatchData hint;
799
800	QVector<int> v;
801	QIndexMapper im(v);
802	QMatchData m(im, -1, true);
803
804	const QAbstractItemModel *model = c->proxy->sourceModel();
805	bool foundInCache = lookupCache(part, parent, m: &m);
806
807	if (!foundInCache) {
808	if (matchHint(part, parent, hint: &hint) && !hint.isValid())
809	return QMatchData();
810	}
811
812	if (!foundInCache && !hint.isValid()) {
813	const int lastRow = model->rowCount(parent) - 1;
814	QIndexMapper all(0, lastRow);
815	int lastIndex = buildIndices(str: part, parent, n, indices: all, m: &m);
816	m.partial = (lastIndex != lastRow);
817	} else {
818	if (!foundInCache) { // build from hint as much as we can
819	buildIndices(str: part, parent, INT_MAX, indices: hint.indices, m: &m);
820	m.partial = hint.partial;
821	}
822	if (m.partial && ((n == -1 && m.exactMatchIndex == -1) || (m.indices.count() < n))) {
823	// need more and have more
824	const int lastRow = model->rowCount(parent) - 1;
825	QIndexMapper rest(hint.indices.last() + 1, lastRow);
826	int want = n == -1 ? -1 : n - m.indices.count();
827	int lastIndex = buildIndices(str: part, parent, n: want, indices: rest, m: &m);
828	m.partial = (lastRow != lastIndex);
829	}
830	}
831
832	saveInCache(part, parent, m);
833	return m;
834	}
835
836	///////////////////////////////////////////////////////////////////////////////
837	QCompleterPrivate::QCompleterPrivate()
838	: widget(nullptr),
839	proxy(nullptr),
840	popup(nullptr),
841	filterMode(Qt::MatchStartsWith),
842	cs(Qt::CaseSensitive),
843	role(Qt::EditRole),
844	column(0),
845	maxVisibleItems(7),
846	sorting(QCompleter::UnsortedModel),
847	wrap(true),
848	eatFocusOut(true),
849	hiddenBecauseNoMatch(false)
850	{
851	}
852
853	void QCompleterPrivate::init(QAbstractItemModel *m)
854	{
855	Q_Q(QCompleter);
856	proxy = new QCompletionModel(this, q);
857	QObject::connect(sender: proxy, SIGNAL(rowsAdded()), receiver: q, SLOT(_q_autoResizePopup()));
858	q->setModel(m);
859	#if !QT_CONFIG(listview)
860	q->setCompletionMode(QCompleter::InlineCompletion);
861	#else
862	q->setCompletionMode(QCompleter::PopupCompletion);
863	#endif // QT_CONFIG(listview)
864	}
865
866	void QCompleterPrivate::setCurrentIndex(QModelIndex index, bool select)
867	{
868	Q_Q(QCompleter);
869	if (!q->popup())
870	return;
871	if (!select) {
872	popup->selectionModel()->setCurrentIndex(index, command: QItemSelectionModel::NoUpdate);
873	} else {
874	if (!index.isValid())
875	popup->selectionModel()->clear();
876	else
877	popup->selectionModel()->setCurrentIndex(index, command: QItemSelectionModel::Select
878	| QItemSelectionModel::Rows);
879	}
880	index = popup->selectionModel()->currentIndex();
881	if (!index.isValid())
882	popup->scrollToTop();
883	else
884	popup->scrollTo(index, hint: QAbstractItemView::PositionAtTop);
885	}
886
887	void QCompleterPrivate::_q_completionSelected(const QItemSelection& selection)
888	{
889	QModelIndex index;
890	if (!selection.indexes().isEmpty())
891	index = selection.indexes().first();
892
893	_q_complete(index, true);
894	}
895
896	void QCompleterPrivate::_q_complete(QModelIndex index, bool highlighted)
897	{
898	Q_Q(QCompleter);
899	QString completion;
900
901	if (!index.isValid() || (!proxy->showAll && (index.row() >= proxy->engine->matchCount()))) {
902	completion = prefix;
903	index = QModelIndex();
904	} else {
905	if (!(index.flags() & Qt::ItemIsEnabled))
906	return;
907	QModelIndex si = proxy->mapToSource(index);
908	si = si.sibling(arow: si.row(), acolumn: column); // for clicked()
909	completion = q->pathFromIndex(index: si);
910	#if QT_CONFIG(dirmodel) && QT_DEPRECATED_SINCE(5, 15)
911	// add a trailing separator in inline
912	if (mode == QCompleter::InlineCompletion) {
913	if (qobject_cast<QDirModel *>(object: proxy->sourceModel()) && QFileInfo(completion).isDir())
914	completion += QDir::separator();
915	}
916	#endif
917	#if QT_CONFIG(filesystemmodel)
918	// add a trailing separator in inline
919	if (mode == QCompleter::InlineCompletion) {
920	if (qobject_cast<QFileSystemModel *>(object: proxy->sourceModel()) && QFileInfo(completion).isDir())
921	completion += QDir::separator();
922	}
923	#endif
924	}
925
926	if (highlighted) {
927	emit q->highlighted(index);
928	emit q->highlighted(text: completion);
929	} else {
930	emit q->activated(index);
931	emit q->activated(text: completion);
932	}
933	}
934
935	void QCompleterPrivate::_q_autoResizePopup()
936	{
937	if (!popup || !popup->isVisible())
938	return;
939	showPopup(popupRect);
940	}
941
942	void QCompleterPrivate::showPopup(const QRect& rect)
943	{
944	const QRect screen = QDesktopWidgetPrivate::availableGeometry(widget);
945	Qt::LayoutDirection dir = widget->layoutDirection();
946	QPoint pos;
947	int rh, w;
948	int h = (popup->sizeHintForRow(row: 0) * qMin(a: maxVisibleItems, b: popup->model()->rowCount()) + 3) + 3;
949	QScrollBar *hsb = popup->horizontalScrollBar();
950	if (hsb && hsb->isVisible())
951	h += popup->horizontalScrollBar()->sizeHint().height();
952
953	if (rect.isValid()) {
954	rh = rect.height();
955	w = rect.width();
956	pos = widget->mapToGlobal(dir == Qt::RightToLeft ? rect.bottomRight() : rect.bottomLeft());
957	} else {
958	rh = widget->height();
959	pos = widget->mapToGlobal(QPoint(0, widget->height() - 2));
960	w = widget->width();
961	}
962
963	if (w > screen.width())
964	w = screen.width();
965	if ((pos.x() + w) > (screen.x() + screen.width()))
966	pos.setX(screen.x() + screen.width() - w);
967	if (pos.x() < screen.x())
968	pos.setX(screen.x());
969
970	int top = pos.y() - rh - screen.top() + 2;
971	int bottom = screen.bottom() - pos.y();
972	h = qMax(a: h, b: popup->minimumHeight());
973	if (h > bottom) {
974	h = qMin(a: qMax(a: top, b: bottom), b: h);
975
976	if (top > bottom)
977	pos.setY(pos.y() - h - rh + 2);
978	}
979
980	popup->setGeometry(ax: pos.x(), ay: pos.y(), aw: w, ah: h);
981
982	if (!popup->isVisible())
983	popup->show();
984	}
985
986	#if QT_CONFIG(filesystemmodel)
987	static bool isRoot(const QFileSystemModel *model, const QString &path)
988	{
989	const auto index = model->index(path);
990	return index.isValid() && model->fileInfo(index).isRoot();
991	}
992
993	static bool completeOnLoaded(const QFileSystemModel *model,
994	const QString &nativePrefix,
995	const QString &path,
996	Qt::CaseSensitivity caseSensitivity)
997	{
998	const auto pathSize = path.size();
999	const auto prefixSize = nativePrefix.size();
1000	if (prefixSize < pathSize)
1001	return false;
1002	const QString prefix = QDir::fromNativeSeparators(pathName: nativePrefix);
1003	if (prefixSize == pathSize)
1004	return path.compare(s: prefix, cs: caseSensitivity) == 0 && isRoot(model, path);
1005	// The user is typing something within that directory and is not in a subdirectory yet.
1006	const auto separator = QLatin1Char('/');
1007	return prefix.startsWith(s: path, cs: caseSensitivity) && prefix.at(i: pathSize) == separator
1008	&& !prefix.rightRef(n: prefixSize - pathSize - 1).contains(c: separator);
1009	}
1010
1011	void QCompleterPrivate::_q_fileSystemModelDirectoryLoaded(const QString &path)
1012	{
1013	Q_Q(QCompleter);
1014	// Slot called when QFileSystemModel has finished loading.
1015	// If we hide the popup because there was no match because the model was not loaded yet,
1016	// we re-start the completion when we get the results (unless triggered by
1017	// something else, see QTBUG-14292).
1018	if (hiddenBecauseNoMatch && widget) {
1019	if (auto model = qobject_cast<const QFileSystemModel *>(object: proxy->sourceModel())) {
1020	if (completeOnLoaded(model, nativePrefix: prefix, path, caseSensitivity: cs))
1021	q->complete();
1022	}
1023	}
1024	}
1025	#else // QT_CONFIG(filesystemmodel)
1026	void QCompleterPrivate::_q_fileSystemModelDirectoryLoaded(const QString &) {}
1027	#endif
1028
1029	/*!
1030	Constructs a completer object with the given \a parent.
1031	*/
1032	QCompleter::QCompleter(QObject *parent)
1033	: QObject(*new QCompleterPrivate(), parent)
1034	{
1035	Q_D(QCompleter);
1036	d->init();
1037	}
1038
1039	/*!
1040	Constructs a completer object with the given \a parent that provides completions
1041	from the specified \a model.
1042	*/
1043	QCompleter::QCompleter(QAbstractItemModel *model, QObject *parent)
1044	: QObject(*new QCompleterPrivate(), parent)
1045	{
1046	Q_D(QCompleter);
1047	d->init(m: model);
1048	}
1049
1050	#if QT_CONFIG(stringlistmodel)
1051	/*!
1052	Constructs a QCompleter object with the given \a parent that uses the specified
1053	\a list as a source of possible completions.
1054	*/
1055	QCompleter::QCompleter(const QStringList& list, QObject *parent)
1056	: QObject(*new QCompleterPrivate(), parent)
1057	{
1058	Q_D(QCompleter);
1059	d->init(m: new QStringListModel(list, this));
1060	}
1061	#endif // QT_CONFIG(stringlistmodel)
1062
1063	/*!
1064	Destroys the completer object.
1065	*/
1066	QCompleter::~QCompleter()
1067	{
1068	}
1069
1070	/*!
1071	Sets the widget for which completion are provided for to \a widget. This
1072	function is automatically called when a QCompleter is set on a QLineEdit
1073	using QLineEdit::setCompleter() or on a QComboBox using
1074	QComboBox::setCompleter(). The widget needs to be set explicitly when
1075	providing completions for custom widgets.
1076
1077	\sa widget(), setModel(), setPopup()
1078	*/
1079	void QCompleter::setWidget(QWidget *widget)
1080	{
1081	Q_D(QCompleter);
1082	if (widget == d->widget)
1083	return;
1084
1085	if (d->widget)
1086	d->widget->removeEventFilter(obj: this);
1087	d->widget = widget;
1088	if (d->widget)
1089	d->widget->installEventFilter(filterObj: this);
1090
1091	if (d->popup) {
1092	d->popup->hide();
1093	d->popup->setFocusProxy(d->widget);
1094	}
1095	}
1096
1097	/*!
1098	Returns the widget for which the completer object is providing completions.
1099
1100	\sa setWidget()
1101	*/
1102	QWidget *QCompleter::widget() const
1103	{
1104	Q_D(const QCompleter);
1105	return d->widget;
1106	}
1107
1108	/*!
1109	Sets the model which provides completions to \a model. The \a model can
1110	be list model or a tree model. If a model has been already previously set
1111	and it has the QCompleter as its parent, it is deleted.
1112
1113	For convenience, if \a model is a QFileSystemModel, QCompleter switches its
1114	caseSensitivity to Qt::CaseInsensitive on Windows and Qt::CaseSensitive
1115	on other platforms.
1116
1117	\sa completionModel(), modelSorting, {Handling Tree Models}
1118	*/
1119	void QCompleter::setModel(QAbstractItemModel *model)
1120	{
1121	Q_D(QCompleter);
1122	QAbstractItemModel *oldModel = d->proxy->sourceModel();
1123	if (oldModel == model)
1124	return;
1125	#if QT_CONFIG(filesystemmodel)
1126	if (qobject_cast<const QFileSystemModel *>(object: oldModel))
1127	setCompletionRole(Qt::EditRole); // QTBUG-54642, clear FileNameRole set by QFileSystemModel
1128	#endif
1129	d->proxy->setSourceModel(model);
1130	if (d->popup)
1131	setPopup(d->popup); // set the model and make new connections
1132	if (oldModel && oldModel->QObject::parent() == this)
1133	delete oldModel;
1134	#if QT_CONFIG(dirmodel) && QT_DEPRECATED_SINCE(5, 15)
1135	if (qobject_cast<QDirModel *>(object: model)) {
1136	#if defined(Q_OS_WIN)
1137	setCaseSensitivity(Qt::CaseInsensitive);
1138	#else
1139	setCaseSensitivity(Qt::CaseSensitive);
1140	#endif
1141	}
1142	#endif // QT_CONFIG(dirmodel)
1143	#if QT_CONFIG(filesystemmodel)
1144	QFileSystemModel *fsModel = qobject_cast<QFileSystemModel *>(object: model);
1145	if (fsModel) {
1146	#if defined(Q_OS_WIN)
1147	setCaseSensitivity(Qt::CaseInsensitive);
1148	#else
1149	setCaseSensitivity(Qt::CaseSensitive);
1150	#endif
1151	setCompletionRole(QFileSystemModel::FileNameRole);
1152	connect(sender: fsModel, SIGNAL(directoryLoaded(QString)), receiver: this, SLOT(_q_fileSystemModelDirectoryLoaded(QString)));
1153	}
1154	#endif // QT_CONFIG(filesystemmodel)
1155	}
1156
1157	/*!
1158	Returns the model that provides completion strings.
1159
1160	\sa completionModel()
1161	*/
1162	QAbstractItemModel *QCompleter::model() const
1163	{
1164	Q_D(const QCompleter);
1165	return d->proxy->sourceModel();
1166	}
1167
1168	/*!
1169	\enum QCompleter::CompletionMode
1170
1171	This enum specifies how completions are provided to the user.
1172
1173	\value PopupCompletion Current completions are displayed in a popup window.
1174	\value InlineCompletion Completions appear inline (as selected text).
1175	\value UnfilteredPopupCompletion All possible completions are displayed in a popup window with the most likely suggestion indicated as current.
1176
1177	\sa setCompletionMode()
1178	*/
1179
1180	/*!
1181	\property QCompleter::completionMode
1182	\brief how the completions are provided to the user
1183
1184	The default value is QCompleter::PopupCompletion.
1185	*/
1186	void QCompleter::setCompletionMode(QCompleter::CompletionMode mode)
1187	{
1188	Q_D(QCompleter);
1189	d->mode = mode;
1190	d->proxy->setFiltered(mode != QCompleter::UnfilteredPopupCompletion);
1191
1192	if (mode == QCompleter::InlineCompletion) {
1193	if (d->widget)
1194	d->widget->removeEventFilter(obj: this);
1195	if (d->popup) {
1196	d->popup->deleteLater();
1197	d->popup = nullptr;
1198	}
1199	} else {
1200	if (d->widget)
1201	d->widget->installEventFilter(filterObj: this);
1202	}
1203	}
1204
1205	QCompleter::CompletionMode QCompleter::completionMode() const
1206	{
1207	Q_D(const QCompleter);
1208	return d->mode;
1209	}
1210
1211	/*!
1212	\property QCompleter::filterMode
1213	\brief This property controls how filtering is performed.
1214	\since 5.2
1215
1216	If filterMode is set to Qt::MatchStartsWith, only those entries that start
1217	with the typed characters will be displayed. Qt::MatchContains will display
1218	the entries that contain the typed characters, and Qt::MatchEndsWith the
1219	ones that end with the typed characters.
1220
1221	Setting filterMode to any other Qt::MatchFlag will issue a warning, and no
1222	action will be performed. Because of this, the \c Qt::MatchCaseSensitive
1223	flag has no effect. Use the \l caseSensitivity property to control case
1224	sensitivity.
1225
1226	The default mode is Qt::MatchStartsWith.
1227
1228	\sa caseSensitivity
1229	*/
1230
1231	void QCompleter::setFilterMode(Qt::MatchFlags filterMode)
1232	{
1233	Q_D(QCompleter);
1234
1235	if (d->filterMode == filterMode)
1236	return;
1237
1238	if (Q_UNLIKELY(filterMode != Qt::MatchStartsWith &&
1239	filterMode != Qt::MatchContains &&
1240	filterMode != Qt::MatchEndsWith)) {
1241	qWarning(msg: "Unhandled QCompleter::filterMode flag is used.");
1242	return;
1243	}
1244
1245	d->filterMode = filterMode;
1246	d->proxy->createEngine();
1247	d->proxy->invalidate();
1248	}
1249
1250	Qt::MatchFlags QCompleter::filterMode() const
1251	{
1252	Q_D(const QCompleter);
1253	return d->filterMode;
1254	}
1255
1256	/*!
1257	Sets the popup used to display completions to \a popup. QCompleter takes
1258	ownership of the view.
1259
1260	A QListView is automatically created when the completionMode() is set to
1261	QCompleter::PopupCompletion or QCompleter::UnfilteredPopupCompletion. The
1262	default popup displays the completionColumn().
1263
1264	Ensure that this function is called before the view settings are modified.
1265	This is required since view's properties may require that a model has been
1266	set on the view (for example, hiding columns in the view requires a model
1267	to be set on the view).
1268
1269	\sa popup()
1270	*/
1271	void QCompleter::setPopup(QAbstractItemView *popup)
1272	{
1273	Q_D(QCompleter);
1274	Q_ASSERT(popup != nullptr);
1275	if (d->popup) {
1276	QObject::disconnect(sender: d->popup->selectionModel(), signal: nullptr, receiver: this, member: nullptr);
1277	QObject::disconnect(sender: d->popup, signal: nullptr, receiver: this, member: nullptr);
1278	}
1279	if (d->popup != popup)
1280	delete d->popup;
1281	if (popup->model() != d->proxy)
1282	popup->setModel(d->proxy);
1283	popup->hide();
1284
1285	Qt::FocusPolicy origPolicy = Qt::NoFocus;
1286	if (d->widget)
1287	origPolicy = d->widget->focusPolicy();
1288
1289	// Mark the widget window as a popup, so that if the last non-popup window is closed by the
1290	// user, the application should not be prevented from exiting. It needs to be set explicitly via
1291	// setWindowFlag(), because passing the flag via setParent(parent, windowFlags) does not call
1292	// QWidgetPrivate::adjustQuitOnCloseAttribute(), and causes an application not to exit if the
1293	// popup ends up being the last window.
1294	popup->setParent(nullptr);
1295	popup->setWindowFlag(Qt::Popup);
1296	popup->setFocusPolicy(Qt::NoFocus);
1297	if (d->widget)
1298	d->widget->setFocusPolicy(origPolicy);
1299
1300	popup->setFocusProxy(d->widget);
1301	popup->installEventFilter(filterObj: this);
1302	popup->setItemDelegate(new QCompleterItemDelegate(popup));
1303	#if QT_CONFIG(listview)
1304	if (QListView *listView = qobject_cast<QListView *>(object: popup)) {
1305	listView->setModelColumn(d->column);
1306	}
1307	#endif
1308
1309	QObject::connect(sender: popup, SIGNAL(clicked(QModelIndex)),
1310	receiver: this, SLOT(_q_complete(QModelIndex)));
1311	QObject::connect(sender: this, SIGNAL(activated(QModelIndex)),
1312	receiver: popup, SLOT(hide()));
1313
1314	QObject::connect(sender: popup->selectionModel(), SIGNAL(selectionChanged(QItemSelection,QItemSelection)),
1315	receiver: this, SLOT(_q_completionSelected(QItemSelection)));
1316	d->popup = popup;
1317	}
1318
1319	/*!
1320	Returns the popup used to display completions.
1321
1322	\sa setPopup()
1323	*/
1324	QAbstractItemView *QCompleter::popup() const
1325	{
1326	Q_D(const QCompleter);
1327	#if QT_CONFIG(listview)
1328	if (!d->popup && completionMode() != QCompleter::InlineCompletion) {
1329	QListView *listView = new QListView;
1330	listView->setEditTriggers(QAbstractItemView::NoEditTriggers);
1331	listView->setHorizontalScrollBarPolicy(Qt::ScrollBarAlwaysOff);
1332	listView->setSelectionBehavior(QAbstractItemView::SelectRows);
1333	listView->setSelectionMode(QAbstractItemView::SingleSelection);
1334	listView->setModelColumn(d->column);
1335	QCompleter *that = const_cast<QCompleter*>(this);
1336	that->setPopup(listView);
1337	}
1338	#endif // QT_CONFIG(listview)
1339	return d->popup;
1340	}
1341
1342	/*!
1343	\reimp
1344	*/
1345	bool QCompleter::event(QEvent *ev)
1346	{
1347	return QObject::event(event: ev);
1348	}
1349
1350	/*!
1351	\reimp
1352	*/
1353	bool QCompleter::eventFilter(QObject *o, QEvent *e)
1354	{
1355	Q_D(QCompleter);
1356
1357	if (d->eatFocusOut && o == d->widget && e->type() == QEvent::FocusOut) {
1358	d->hiddenBecauseNoMatch = false;
1359	if (d->popup && d->popup->isVisible())
1360	return true;
1361	}
1362
1363	if (o != d->popup)
1364	return QObject::eventFilter(watched: o, event: e);
1365
1366	switch (e->type()) {
1367	case QEvent::KeyPress: {
1368	QKeyEvent *ke = static_cast<QKeyEvent *>(e);
1369
1370	QModelIndex curIndex = d->popup->currentIndex();
1371	QModelIndexList selList = d->popup->selectionModel()->selectedIndexes();
1372
1373	const int key = ke->key();
1374	// In UnFilteredPopup mode, select the current item
1375	if ((key == Qt::Key_Up || key == Qt::Key_Down) && selList.isEmpty() && curIndex.isValid()
1376	&& d->mode == QCompleter::UnfilteredPopupCompletion) {
1377	d->setCurrentIndex(index: curIndex);
1378	return true;
1379	}
1380
1381	// Handle popup navigation keys. These are hardcoded because up/down might make the
1382	// widget do something else (lineedit cursor moves to home/end on mac, for instance)
1383	switch (key) {
1384	case Qt::Key_End:
1385	case Qt::Key_Home:
1386	if (ke->modifiers() & Qt::ControlModifier)
1387	return false;
1388	break;
1389
1390	case Qt::Key_Up:
1391	if (!curIndex.isValid()) {
1392	int rowCount = d->proxy->rowCount();
1393	QModelIndex lastIndex = d->proxy->index(row: rowCount - 1, column: d->column);
1394	d->setCurrentIndex(index: lastIndex);
1395	return true;
1396	} else if (curIndex.row() == 0) {
1397	if (d->wrap)
1398	d->setCurrentIndex(index: QModelIndex());
1399	return true;
1400	}
1401	return false;
1402
1403	case Qt::Key_Down:
1404	if (!curIndex.isValid()) {
1405	QModelIndex firstIndex = d->proxy->index(row: 0, column: d->column);
1406	d->setCurrentIndex(index: firstIndex);
1407	return true;
1408	} else if (curIndex.row() == d->proxy->rowCount() - 1) {
1409	if (d->wrap)
1410	d->setCurrentIndex(index: QModelIndex());
1411	return true;
1412	}
1413	return false;
1414
1415	case Qt::Key_PageUp:
1416	case Qt::Key_PageDown:
1417	return false;
1418	}
1419
1420	// Send the event to the widget. If the widget accepted the event, do nothing
1421	// If the widget did not accept the event, provide a default implementation
1422	d->eatFocusOut = false;
1423	(static_cast<QObject *>(d->widget))->event(event: ke);
1424	d->eatFocusOut = true;
1425	if (!d->widget || e->isAccepted() || !d->popup->isVisible()) {
1426	// widget lost focus, hide the popup
1427	if (d->widget && (!d->widget->hasFocus()
1428	#ifdef QT_KEYPAD_NAVIGATION
1429	|| (QApplicationPrivate::keypadNavigationEnabled() && !d->widget->hasEditFocus())
1430	#endif
1431	))
1432	d->popup->hide();
1433	if (e->isAccepted())
1434	return true;
1435	}
1436
1437	// default implementation for keys not handled by the widget when popup is open
1438	#if QT_CONFIG(shortcut)
1439	if (ke->matches(key: QKeySequence::Cancel)) {
1440	d->popup->hide();
1441	return true;
1442	}
1443	#endif
1444	switch (key) {
1445	#ifdef QT_KEYPAD_NAVIGATION
1446	case Qt::Key_Select:
1447	if (!QApplicationPrivate::keypadNavigationEnabled())
1448	break;
1449	#endif
1450	case Qt::Key_Return:
1451	case Qt::Key_Enter:
1452	case Qt::Key_Tab:
1453	d->popup->hide();
1454	if (curIndex.isValid())
1455	d->_q_complete(index: curIndex);
1456	break;
1457
1458	case Qt::Key_F4:
1459	if (ke->modifiers() & Qt::AltModifier)
1460	d->popup->hide();
1461	break;
1462
1463	case Qt::Key_Backtab:
1464	d->popup->hide();
1465	break;
1466
1467	default:
1468	break;
1469	}
1470
1471	return true;
1472	}
1473
1474	#ifdef QT_KEYPAD_NAVIGATION
1475	case QEvent::KeyRelease: {
1476	QKeyEvent *ke = static_cast<QKeyEvent *>(e);
1477	if (QApplicationPrivate::keypadNavigationEnabled() && ke->key() == Qt::Key_Back) {
1478	// Send the event to the 'widget'. This is what we did for KeyPress, so we need
1479	// to do the same for KeyRelease, in case the widget's KeyPress event set
1480	// up something (such as a timer) that is relying on also receiving the
1481	// key release. I see this as a bug in Qt, and should really set it up for all
1482	// the affected keys. However, it is difficult to tell how this will affect
1483	// existing code, and I can't test for every combination!
1484	d->eatFocusOut = false;
1485	static_cast<QObject *>(d->widget)->event(ke);
1486	d->eatFocusOut = true;
1487	}
1488	break;
1489	}
1490	#endif
1491
1492	case QEvent::MouseButtonPress: {
1493	#ifdef QT_KEYPAD_NAVIGATION
1494	if (QApplicationPrivate::keypadNavigationEnabled()) {
1495	// if we've clicked in the widget (or its descendant), let it handle the click
1496	QWidget *source = qobject_cast<QWidget *>(o);
1497	if (source) {
1498	QPoint pos = source->mapToGlobal((static_cast<QMouseEvent *>(e))->pos());
1499	QWidget *target = QApplication::widgetAt(pos);
1500	if (target && (d->widget->isAncestorOf(target) ||
1501	target == d->widget)) {
1502	d->eatFocusOut = false;
1503	static_cast<QObject *>(target)->event(e);
1504	d->eatFocusOut = true;
1505	return true;
1506	}
1507	}
1508	}
1509	#endif
1510	if (!d->popup->underMouse()) {
1511	d->popup->hide();
1512	return true;
1513	}
1514	}
1515	return false;
1516
1517	case QEvent::InputMethod:
1518	case QEvent::ShortcutOverride:
1519	QCoreApplication::sendEvent(receiver: d->widget, event: e);
1520	break;
1521
1522	default:
1523	return false;
1524	}
1525	return false;
1526	}
1527
1528	/*!
1529	For QCompleter::PopupCompletion and QCompletion::UnfilteredPopupCompletion
1530	modes, calling this function displays the popup displaying the current
1531	completions. By default, if \a rect is not specified, the popup is displayed
1532	on the bottom of the widget(). If \a rect is specified the popup is
1533	displayed on the left edge of the rectangle.
1534
1535	For QCompleter::InlineCompletion mode, the highlighted() signal is fired
1536	with the current completion.
1537	*/
1538	void QCompleter::complete(const QRect& rect)
1539	{
1540	Q_D(QCompleter);
1541	QModelIndex idx = d->proxy->currentIndex(sourceIndex: false);
1542	d->hiddenBecauseNoMatch = false;
1543	if (d->mode == QCompleter::InlineCompletion) {
1544	if (idx.isValid())
1545	d->_q_complete(index: idx, highlighted: true);
1546	return;
1547	}
1548
1549	Q_ASSERT(d->widget);
1550	if ((d->mode == QCompleter::PopupCompletion && !idx.isValid())
1551	|| (d->mode == QCompleter::UnfilteredPopupCompletion && d->proxy->rowCount() == 0)) {
1552	if (d->popup)
1553	d->popup->hide(); // no suggestion, hide
1554	d->hiddenBecauseNoMatch = true;
1555	return;
1556	}
1557
1558	popup();
1559	if (d->mode == QCompleter::UnfilteredPopupCompletion)
1560	d->setCurrentIndex(index: idx, select: false);
1561
1562	d->showPopup(rect);
1563	d->popupRect = rect;
1564	}
1565
1566	/*!
1567	Sets the current row to the \a row specified. Returns \c true if successful;
1568	otherwise returns \c false.
1569
1570	This function may be used along with currentCompletion() to iterate
1571	through all the possible completions.
1572
1573	\sa currentCompletion(), completionCount()
1574	*/
1575	bool QCompleter::setCurrentRow(int row)
1576	{
1577	Q_D(QCompleter);
1578	return d->proxy->setCurrentRow(row);
1579	}
1580
1581	/*!
1582	Returns the current row.
1583
1584	\sa setCurrentRow()
1585	*/
1586	int QCompleter::currentRow() const
1587	{
1588	Q_D(const QCompleter);
1589	return d->proxy->currentRow();
1590	}
1591
1592	/*!
1593	Returns the number of completions for the current prefix. For an unsorted
1594	model with a large number of items this can be expensive. Use setCurrentRow()
1595	and currentCompletion() to iterate through all the completions.
1596	*/
1597	int QCompleter::completionCount() const
1598	{
1599	Q_D(const QCompleter);
1600	return d->proxy->completionCount();
1601	}
1602
1603	/*!
1604	\enum QCompleter::ModelSorting
1605
1606	This enum specifies how the items in the model are sorted.
1607
1608	\value UnsortedModel The model is unsorted.
1609	\value CaseSensitivelySortedModel The model is sorted case sensitively.
1610	\value CaseInsensitivelySortedModel The model is sorted case insensitively.
1611
1612	\sa setModelSorting()
1613	*/
1614
1615	/*!
1616	\property QCompleter::modelSorting
1617	\brief the way the model is sorted
1618
1619	By default, no assumptions are made about the order of the items
1620	in the model that provides the completions.
1621
1622	If the model's data for the completionColumn() and completionRole() is sorted in
1623	ascending order, you can set this property to \l CaseSensitivelySortedModel
1624	or \l CaseInsensitivelySortedModel. On large models, this can lead to
1625	significant performance improvements because the completer object can
1626	then use a binary search algorithm instead of linear search algorithm.
1627
1628	The sort order (i.e ascending or descending order) of the model is determined
1629	dynamically by inspecting the contents of the model.
1630
1631	\b{Note:} The performance improvements described above cannot take place
1632	when the completer's \l caseSensitivity is different to the case sensitivity
1633	used by the model's when sorting.
1634
1635	\sa setCaseSensitivity(), QCompleter::ModelSorting
1636	*/
1637	void QCompleter::setModelSorting(QCompleter::ModelSorting sorting)
1638	{
1639	Q_D(QCompleter);
1640	if (d->sorting == sorting)
1641	return;
1642	d->sorting = sorting;
1643	d->proxy->createEngine();
1644	d->proxy->invalidate();
1645	}
1646
1647	QCompleter::ModelSorting QCompleter::modelSorting() const
1648	{
1649	Q_D(const QCompleter);
1650	return d->sorting;
1651	}
1652
1653	/*!
1654	\property QCompleter::completionColumn
1655	\brief the column in the model in which completions are searched for.
1656
1657	If the popup() is a QListView, it is automatically setup to display
1658	this column.
1659
1660	By default, the match column is 0.
1661
1662	\sa completionRole, caseSensitivity
1663	*/
1664	void QCompleter::setCompletionColumn(int column)
1665	{
1666	Q_D(QCompleter);
1667	if (d->column == column)
1668	return;
1669	#if QT_CONFIG(listview)
1670	if (QListView *listView = qobject_cast<QListView *>(object: d->popup))
1671	listView->setModelColumn(column);
1672	#endif
1673	d->column = column;
1674	d->proxy->invalidate();
1675	}
1676
1677	int QCompleter::completionColumn() const
1678	{
1679	Q_D(const QCompleter);
1680	return d->column;
1681	}
1682
1683	/*!
1684	\property QCompleter::completionRole
1685	\brief the item role to be used to query the contents of items for matching.
1686
1687	The default role is Qt::EditRole.
1688
1689	\sa completionColumn, caseSensitivity
1690	*/
1691	void QCompleter::setCompletionRole(int role)
1692	{
1693	Q_D(QCompleter);
1694	if (d->role == role)
1695	return;
1696	d->role = role;
1697	d->proxy->invalidate();
1698	}
1699
1700	int QCompleter::completionRole() const
1701	{
1702	Q_D(const QCompleter);
1703	return d->role;
1704	}
1705
1706	/*!
1707	\property QCompleter::wrapAround
1708	\brief the completions wrap around when navigating through items
1709	\since 4.3
1710
1711	The default is true.
1712	*/
1713	void QCompleter::setWrapAround(bool wrap)
1714	{
1715	Q_D(QCompleter);
1716	if (d->wrap == wrap)
1717	return;
1718	d->wrap = wrap;
1719	}
1720
1721	bool QCompleter::wrapAround() const
1722	{
1723	Q_D(const QCompleter);
1724	return d->wrap;
1725	}
1726
1727	/*!
1728	\property QCompleter::maxVisibleItems
1729	\brief the maximum allowed size on screen of the completer, measured in items
1730	\since 4.6
1731
1732	By default, this property has a value of 7.
1733	*/
1734	int QCompleter::maxVisibleItems() const
1735	{
1736	Q_D(const QCompleter);
1737	return d->maxVisibleItems;
1738	}
1739
1740	void QCompleter::setMaxVisibleItems(int maxItems)
1741	{
1742	Q_D(QCompleter);
1743	if (Q_UNLIKELY(maxItems < 0)) {
1744	qWarning(msg: "QCompleter::setMaxVisibleItems: "
1745	"Invalid max visible items (%d) must be >= 0", maxItems);
1746	return;
1747	}
1748	d->maxVisibleItems = maxItems;
1749	}
1750
1751	/*!
1752	\property QCompleter::caseSensitivity
1753	\brief the case sensitivity of the matching
1754
1755	The default value is \c Qt::CaseSensitive.
1756
1757	\sa completionColumn, completionRole, modelSorting, filterMode
1758	*/
1759	void QCompleter::setCaseSensitivity(Qt::CaseSensitivity cs)
1760	{
1761	Q_D(QCompleter);
1762	if (d->cs == cs)
1763	return;
1764	d->cs = cs;
1765	d->proxy->createEngine();
1766	d->proxy->invalidate();
1767	}
1768
1769	Qt::CaseSensitivity QCompleter::caseSensitivity() const
1770	{
1771	Q_D(const QCompleter);
1772	return d->cs;
1773	}
1774
1775	/*!
1776	\property QCompleter::completionPrefix
1777	\brief the completion prefix used to provide completions.
1778
1779	The completionModel() is updated to reflect the list of possible
1780	matches for \a prefix.
1781	*/
1782	void QCompleter::setCompletionPrefix(const QString &prefix)
1783	{
1784	Q_D(QCompleter);
1785	d->prefix = prefix;
1786	d->proxy->filter(parts: splitPath(path: prefix));
1787	}
1788
1789	QString QCompleter::completionPrefix() const
1790	{
1791	Q_D(const QCompleter);
1792	return d->prefix;
1793	}
1794
1795	/*!
1796	Returns the model index of the current completion in the completionModel().
1797
1798	\sa setCurrentRow(), currentCompletion(), model()
1799	*/
1800	QModelIndex QCompleter::currentIndex() const
1801	{
1802	Q_D(const QCompleter);
1803	return d->proxy->currentIndex(sourceIndex: false);
1804	}
1805
1806	/*!
1807	Returns the current completion string. This includes the \l completionPrefix.
1808	When used alongside setCurrentRow(), it can be used to iterate through
1809	all the matches.
1810
1811	\sa setCurrentRow(), currentIndex()
1812	*/
1813	QString QCompleter::currentCompletion() const
1814	{
1815	Q_D(const QCompleter);
1816	return pathFromIndex(index: d->proxy->currentIndex(sourceIndex: true));
1817	}
1818
1819	/*!
1820	Returns the completion model. The completion model is a read-only list model
1821	that contains all the possible matches for the current completion prefix.
1822	The completion model is auto-updated to reflect the current completions.
1823
1824	\note The return value of this function is defined to be an QAbstractItemModel
1825	purely for generality. This actual kind of model returned is an instance of an
1826	QAbstractProxyModel subclass.
1827
1828	\sa completionPrefix, model()
1829	*/
1830	QAbstractItemModel *QCompleter::completionModel() const
1831	{
1832	Q_D(const QCompleter);
1833	return d->proxy;
1834	}
1835
1836	/*!
1837	Returns the path for the given \a index. The completer object uses this to
1838	obtain the completion text from the underlying model.
1839
1840	The default implementation returns the \l{Qt::EditRole}{edit role} of the
1841	item for list models. It returns the absolute file path if the model is a
1842	QFileSystemModel.
1843
1844	\sa splitPath()
1845	*/
1846
1847	QString QCompleter::pathFromIndex(const QModelIndex& index) const
1848	{
1849	Q_D(const QCompleter);
1850	if (!index.isValid())
1851	return QString();
1852
1853	QAbstractItemModel *sourceModel = d->proxy->sourceModel();
1854	if (!sourceModel)
1855	return QString();
1856	bool isDirModel = false;
1857	bool isFsModel = false;
1858	#if QT_CONFIG(dirmodel) && QT_DEPRECATED_SINCE(5, 15)
1859	isDirModel = qobject_cast<QDirModel *>(object: d->proxy->sourceModel()) != nullptr;
1860	#endif
1861	#if QT_CONFIG(filesystemmodel)
1862	isFsModel = qobject_cast<QFileSystemModel *>(object: d->proxy->sourceModel()) != nullptr;
1863	#endif
1864	if (!isDirModel && !isFsModel)
1865	return sourceModel->data(index, role: d->role).toString();
1866
1867	QModelIndex idx = index;
1868	QStringList list;
1869	do {
1870	QString t;
1871	if (isDirModel)
1872	t = sourceModel->data(index: idx, role: Qt::EditRole).toString();
1873	#if QT_CONFIG(filesystemmodel)
1874	else
1875	t = sourceModel->data(index: idx, role: QFileSystemModel::FileNameRole).toString();
1876	#endif
1877	list.prepend(t);
1878	QModelIndex parent = idx.parent();
1879	idx = parent.sibling(arow: parent.row(), acolumn: index.column());
1880	} while (idx.isValid());
1881
1882	#if !defined(Q_OS_WIN)
1883	if (list.count() == 1) // only the separator or some other text
1884	return list[0];
1885	list[0].clear() ; // the join below will provide the separator
1886	#endif
1887
1888	return list.join(sep: QDir::separator());
1889	}
1890
1891	/*!
1892	Splits the given \a path into strings that are used to match at each level
1893	in the model().
1894
1895	The default implementation of splitPath() splits a file system path based on
1896	QDir::separator() when the sourceModel() is a QFileSystemModel.
1897
1898	When used with list models, the first item in the returned list is used for
1899	matching.
1900
1901	\sa pathFromIndex(), {Handling Tree Models}
1902	*/
1903	QStringList QCompleter::splitPath(const QString& path) const
1904	{
1905	bool isDirModel = false;
1906	bool isFsModel = false;
1907	#if QT_CONFIG(dirmodel) && QT_DEPRECATED_SINCE(5, 15)
1908	Q_D(const QCompleter);
1909	isDirModel = qobject_cast<QDirModel *>(object: d->proxy->sourceModel()) != nullptr;
1910	#endif
1911	#if QT_CONFIG(filesystemmodel)
1912	#if !QT_CONFIG(dirmodel)
1913	Q_D(const QCompleter);
1914	#endif
1915	isFsModel = qobject_cast<QFileSystemModel *>(object: d->proxy->sourceModel()) != nullptr;
1916	#endif
1917
1918	if ((!isDirModel && !isFsModel) || path.isEmpty())
1919	return QStringList(completionPrefix());
1920
1921	QString pathCopy = QDir::toNativeSeparators(pathName: path);
1922	#if defined(Q_OS_WIN)
1923	if (pathCopy == QLatin1String("\\") || pathCopy == QLatin1String("\\\\"))
1924	return QStringList(pathCopy);
1925	const bool startsWithDoubleSlash = pathCopy.startsWith(QLatin1String("\\\\"));
1926	if (startsWithDoubleSlash)
1927	pathCopy = pathCopy.mid(2);
1928	#endif
1929
1930	const QChar sep = QDir::separator();
1931	QStringList parts = pathCopy.split(sep);
1932
1933	#if defined(Q_OS_WIN)
1934	if (startsWithDoubleSlash)
1935	parts[0].prepend(QLatin1String("\\\\"));
1936	#else
1937	if (pathCopy[0] == sep) // readd the "/" at the beginning as the split removed it
1938	parts[0] = QLatin1Char('/');
1939	#endif
1940
1941	return parts;
1942	}
1943
1944	/*!
1945	\fn void QCompleter::activated(const QModelIndex& index)
1946
1947	This signal is sent when an item in the popup() is activated by the user.
1948	(by clicking or pressing return). The item's \a index in the completionModel()
1949	is given.
1950
1951	*/
1952
1953	/*!
1954	\fn void QCompleter::activated(const QString &text)
1955
1956	This signal is sent when an item in the popup() is activated by the user (by
1957	clicking or pressing return). The item's \a text is given.
1958
1959	*/
1960
1961	/*!
1962	\fn void QCompleter::highlighted(const QModelIndex& index)
1963
1964	This signal is sent when an item in the popup() is highlighted by
1965	the user. It is also sent if complete() is called with the completionMode()
1966	set to QCompleter::InlineCompletion. The item's \a index in the completionModel()
1967	is given.
1968	*/
1969
1970	/*!
1971	\fn void QCompleter::highlighted(const QString &text)
1972
1973	This signal is sent when an item in the popup() is highlighted by
1974	the user. It is also sent if complete() is called with the completionMode()
1975	set to QCompleter::InlineCompletion. The item's \a text is given.
1976	*/
1977
1978	QT_END_NAMESPACE
1979
1980	#include "moc_qcompleter.cpp"
1981
1982	#include "moc_qcompleter_p.cpp"
1983