1/*
2 This file is part of the KDE libraries
3 SPDX-FileCopyrightText: 1999, 2000, 2001 Carsten Pfeiffer <pfeiffer@kde.org>
4
5 SPDX-License-Identifier: LGPL-2.0-or-later
6*/
7
8#include "kcompletion.h"
9#include "kcompletion_p.h"
10#include <kcompletion_debug.h>
11
12#include <QCollator>
13
14void KCompletionPrivate::addWeightedItem(const QString &item)
15{
16 Q_Q(KCompletion);
17 if (order != KCompletion::Weighted) {
18 q->addItem(item, weight: 0);
19 return;
20 }
21
22 int len = item.length();
23 uint weight = 0;
24
25 // find out the weighting of this item (appended to the string as ":num")
26 int index = item.lastIndexOf(c: QLatin1Char(':'));
27 if (index > 0) {
28 bool ok;
29 weight = QStringView(item).mid(pos: index + 1).toUInt(ok: &ok);
30 if (!ok) {
31 weight = 0;
32 }
33
34 len = index; // only insert until the ':'
35 }
36
37 q->addItem(item: item.left(n: len), weight);
38 return;
39}
40
41// tries to complete "string" from the tree-root
42QString KCompletionPrivate::findCompletion(const QString &string)
43{
44 QString completion;
45 const KCompTreeNode *node = m_treeRoot.get();
46
47 // start at the tree-root and try to find the search-string
48 for (const auto ch : string) {
49 node = node->find(ch);
50
51 if (node) {
52 completion += ch;
53 } else {
54 return QString(); // no completion
55 }
56 }
57
58 // Now we have the last node of the to be completed string.
59 // Follow it as long as it has exactly one child (= longest possible
60 // completion)
61
62 while (node->childrenCount() == 1) {
63 node = node->firstChild();
64 if (!node->isNull()) {
65 completion += *node;
66 }
67 }
68 // if multiple matches and auto-completion mode
69 // -> find the first complete match
70 if (node && node->childrenCount() > 1) {
71 hasMultipleMatches = true;
72
73 if (completionMode == KCompletion::CompletionAuto) {
74 rotationIndex = 1;
75 if (order != KCompletion::Weighted) {
76 while ((node = node->firstChild())) {
77 if (!node->isNull()) {
78 completion += *node;
79 } else {
80 break;
81 }
82 }
83 } else {
84 // don't just find the "first" match, but the one with the
85 // highest priority
86
87 const KCompTreeNode *temp_node = nullptr;
88 while (1) {
89 int count = node->childrenCount();
90 temp_node = node->firstChild();
91 uint weight = temp_node->weight();
92 const KCompTreeNode *hit = temp_node;
93 for (int i = 1; i < count; i++) {
94 temp_node = node->childAt(index: i);
95 if (temp_node->weight() > weight) {
96 hit = temp_node;
97 weight = hit->weight();
98 }
99 }
100 // 0x0 has the highest priority -> we have the best match
101 if (hit->isNull()) {
102 break;
103 }
104
105 node = hit;
106 completion += *node;
107 }
108 }
109 }
110 }
111
112 return completion;
113}
114
115void KCompletionPrivate::defaultSort(QStringList &stringList)
116{
117 QCollator c;
118 c.setCaseSensitivity(Qt::CaseSensitive);
119 std::stable_sort(first: stringList.begin(), last: stringList.end(), comp: c);
120}
121
122KCompletion::KCompletion()
123 : d_ptr(new KCompletionPrivate(this))
124{
125 setOrder(Insertion);
126}
127
128KCompletion::~KCompletion()
129{
130}
131
132void KCompletion::setOrder(CompOrder order)
133{
134 Q_D(KCompletion);
135 d->order = order;
136 d->matches.setSorting(order);
137}
138
139KCompletion::CompOrder KCompletion::order() const
140{
141 Q_D(const KCompletion);
142 return d->order;
143}
144
145void KCompletion::setIgnoreCase(bool ignoreCase)
146{
147 Q_D(KCompletion);
148 d->ignoreCase = ignoreCase;
149}
150
151bool KCompletion::ignoreCase() const
152{
153 Q_D(const KCompletion);
154 return d->ignoreCase;
155}
156
157void KCompletion::setItems(const QStringList &itemList)
158{
159 clear();
160 insertItems(items: itemList);
161}
162
163void KCompletion::insertItems(const QStringList &items)
164{
165 Q_D(KCompletion);
166 for (const auto &str : items) {
167 if (d->order == Weighted) {
168 d->addWeightedItem(item: str);
169 } else {
170 addItem(item: str, weight: 0);
171 }
172 }
173}
174
175QStringList KCompletion::items() const
176{
177 Q_D(const KCompletion);
178 KCompletionMatchesWrapper list(d->sorterFunction); // unsorted
179 list.extractStringsFromNode(node: d->m_treeRoot.get(), beginning: QString(), addWeight: d->order == Weighted);
180 return list.list();
181}
182
183bool KCompletion::isEmpty() const
184{
185 Q_D(const KCompletion);
186 return (d->m_treeRoot->childrenCount() == 0);
187}
188
189void KCompletion::postProcessMatch(QString *) const
190{
191}
192
193void KCompletion::postProcessMatches(QStringList *) const
194{
195}
196
197void KCompletion::postProcessMatches(KCompletionMatches *) const
198{
199}
200
201void KCompletion::addItem(const QString &item)
202{
203 Q_D(KCompletion);
204 d->matches.clear();
205 d->rotationIndex = 0;
206 d->lastString.clear();
207
208 addItem(item, weight: 0);
209}
210
211void KCompletion::addItem(const QString &item, uint weight)
212{
213 Q_D(KCompletion);
214 if (item.isEmpty()) {
215 return;
216 }
217
218 KCompTreeNode *node = d->m_treeRoot.get();
219 int len = item.length();
220
221 bool sorted = (d->order == Sorted);
222 bool weighted = ((d->order == Weighted) && weight > 1);
223
224 // knowing the weight of an item, we simply add this weight to all of its
225 // nodes.
226
227 for (int i = 0; i < len; i++) {
228 node = node->insert(ch: item.at(i), sorted);
229 if (weighted) {
230 node->confirm(w: weight - 1); // node->insert() sets weighting to 1
231 }
232 }
233
234 // add 0x0-item as delimiter with evtl. weight
235 node = node->insert(ch: QChar(0x0), sorted: true);
236 if (weighted) {
237 node->confirm(w: weight - 1);
238 }
239 // qDebug("*** added: %s (%i)", item.toLatin1().constData(), node->weight());
240}
241
242void KCompletion::removeItem(const QString &item)
243{
244 Q_D(KCompletion);
245 d->matches.clear();
246 d->rotationIndex = 0;
247 d->lastString.clear();
248
249 d->m_treeRoot->remove(str: item);
250}
251
252void KCompletion::clear()
253{
254 Q_D(KCompletion);
255 d->matches.clear();
256 d->rotationIndex = 0;
257 d->lastString.clear();
258
259 d->m_treeRoot.reset(p: new KCompTreeNode);
260}
261
262QString KCompletion::makeCompletion(const QString &string)
263{
264 Q_D(KCompletion);
265 if (d->completionMode == CompletionNone) {
266 return QString();
267 }
268
269 // qDebug() << "KCompletion: completing: " << string;
270
271 d->matches.clear();
272 d->rotationIndex = 0;
273 d->hasMultipleMatches = false;
274 d->lastMatch = d->currentMatch;
275
276 // in Shell-completion-mode, emit all matches when we get the same
277 // complete-string twice
278 if (d->completionMode == CompletionShell && string == d->lastString) {
279 // Don't use d->matches since calling postProcessMatches()
280 // on d->matches here would interfere with call to
281 // postProcessMatch() during rotation
282
283 d->matches.findAllCompletions(treeRoot: d->m_treeRoot.get(), string, ignoreCase: d->ignoreCase, hasMultipleMatches&: d->hasMultipleMatches);
284 QStringList l = d->matches.list();
285 postProcessMatches(&l);
286 Q_EMIT matches(matchlist: l);
287
288 return QString();
289 }
290
291 QString completion;
292 // in case-insensitive popup mode, we search all completions at once
293 if (d->completionMode == CompletionPopup || d->completionMode == CompletionPopupAuto) {
294 d->matches.findAllCompletions(treeRoot: d->m_treeRoot.get(), string, ignoreCase: d->ignoreCase, hasMultipleMatches&: d->hasMultipleMatches);
295 if (!d->matches.isEmpty()) {
296 completion = d->matches.first();
297 }
298 } else {
299 completion = d->findCompletion(string);
300 }
301
302 if (d->hasMultipleMatches) {
303 Q_EMIT multipleMatches();
304 }
305
306 d->lastString = string;
307 d->currentMatch = completion;
308
309 postProcessMatch(&completion);
310
311 if (!string.isEmpty()) { // only emit match when string is not empty
312 // qDebug() << "KCompletion: Match: " << completion;
313 Q_EMIT match(item: completion);
314 }
315
316 return completion;
317}
318
319QStringList KCompletion::substringCompletion(const QString &string) const
320{
321 Q_D(const KCompletion);
322 // get all items in the tree, eventually in sorted order
323 KCompletionMatchesWrapper allItems(d->sorterFunction, d->order);
324 allItems.extractStringsFromNode(node: d->m_treeRoot.get(), beginning: QString(), addWeight: false);
325
326 QStringList list = allItems.list();
327
328 // subStringMatches is invoked manually, via a shortcut
329 if (list.isEmpty()) {
330 return list;
331 }
332
333 if (!string.isEmpty()) { // If it's empty, nothing to compare
334 auto it = std::remove_if(first: list.begin(), last: list.end(), pred: [&string](const QString &item) {
335 return !item.contains(s: string, cs: Qt::CaseInsensitive); // always case insensitive
336 });
337 list.erase(abegin: it, aend: list.end());
338 }
339
340 postProcessMatches(&list);
341 return list;
342}
343
344void KCompletion::setCompletionMode(CompletionMode mode)
345{
346 Q_D(KCompletion);
347 d->completionMode = mode;
348}
349
350KCompletion::CompletionMode KCompletion::completionMode() const
351{
352 Q_D(const KCompletion);
353 return d->completionMode;
354}
355
356void KCompletion::setShouldAutoSuggest(const bool shouldAutoSuggest)
357{
358 Q_D(KCompletion);
359 d->shouldAutoSuggest = shouldAutoSuggest;
360}
361
362bool KCompletion::shouldAutoSuggest() const
363{
364 Q_D(const KCompletion);
365 return d->shouldAutoSuggest;
366}
367
368void KCompletion::setSorterFunction(SorterFunction sortFunc)
369{
370 Q_D(KCompletion);
371 d->sorterFunction = sortFunc ? sortFunc : KCompletionPrivate::defaultSort;
372}
373
374QStringList KCompletion::allMatches()
375{
376 Q_D(KCompletion);
377 // Don't use d->matches since calling postProcessMatches()
378 // on d->matches here would interfere with call to
379 // postProcessMatch() during rotation
380 KCompletionMatchesWrapper matches(d->sorterFunction, d->order);
381 bool dummy;
382 matches.findAllCompletions(treeRoot: d->m_treeRoot.get(), string: d->lastString, ignoreCase: d->ignoreCase, hasMultipleMatches&: dummy);
383 QStringList l = matches.list();
384 postProcessMatches(&l);
385 return l;
386}
387
388KCompletionMatches KCompletion::allWeightedMatches()
389{
390 Q_D(KCompletion);
391 // Don't use d->matches since calling postProcessMatches()
392 // on d->matches here would interfere with call to
393 // postProcessMatch() during rotation
394 KCompletionMatchesWrapper matches(d->sorterFunction, d->order);
395 bool dummy;
396 matches.findAllCompletions(treeRoot: d->m_treeRoot.get(), string: d->lastString, ignoreCase: d->ignoreCase, hasMultipleMatches&: dummy);
397 KCompletionMatches ret(matches);
398 postProcessMatches(&ret);
399 return ret;
400}
401
402QStringList KCompletion::allMatches(const QString &string)
403{
404 Q_D(KCompletion);
405 KCompletionMatchesWrapper matches(d->sorterFunction, d->order);
406 bool dummy;
407 matches.findAllCompletions(treeRoot: d->m_treeRoot.get(), string, ignoreCase: d->ignoreCase, hasMultipleMatches&: dummy);
408 QStringList l = matches.list();
409 postProcessMatches(&l);
410 return l;
411}
412
413KCompletionMatches KCompletion::allWeightedMatches(const QString &string)
414{
415 Q_D(KCompletion);
416 KCompletionMatchesWrapper matches(d->sorterFunction, d->order);
417 bool dummy;
418 matches.findAllCompletions(treeRoot: d->m_treeRoot.get(), string, ignoreCase: d->ignoreCase, hasMultipleMatches&: dummy);
419 KCompletionMatches ret(matches);
420 postProcessMatches(&ret);
421 return ret;
422}
423
424#if KCOMPLETION_BUILD_DEPRECATED_SINCE(6, 11)
425void KCompletion::setSoundsEnabled(bool enable)
426{
427 Q_D(KCompletion);
428 d->beep = enable;
429}
430#endif
431
432#if KCOMPLETION_BUILD_DEPRECATED_SINCE(6, 11)
433bool KCompletion::soundsEnabled() const
434{
435 Q_D(const KCompletion);
436 return d->beep;
437}
438#endif
439
440bool KCompletion::hasMultipleMatches() const
441{
442 Q_D(const KCompletion);
443 return d->hasMultipleMatches;
444}
445
446/////////////////////////////////////////////////////
447///////////////// tree operations ///////////////////
448
449QString KCompletion::nextMatch()
450{
451 Q_D(KCompletion);
452 QString completion;
453 d->lastMatch = d->currentMatch;
454
455 if (d->matches.isEmpty()) {
456 d->matches.findAllCompletions(treeRoot: d->m_treeRoot.get(), string: d->lastString, ignoreCase: d->ignoreCase, hasMultipleMatches&: d->hasMultipleMatches);
457 if (!d->matches.isEmpty()) {
458 completion = d->matches.first();
459 }
460 d->currentMatch = completion;
461 d->rotationIndex = 0;
462 postProcessMatch(&completion);
463 Q_EMIT match(item: completion);
464 return completion;
465 }
466
467 QStringList matches = d->matches.list();
468 d->lastMatch = matches[d->rotationIndex++];
469
470 if (d->rotationIndex == matches.count()) {
471 d->rotationIndex = 0;
472 }
473
474 completion = matches[d->rotationIndex];
475 d->currentMatch = completion;
476 postProcessMatch(&completion);
477 Q_EMIT match(item: completion);
478 return completion;
479}
480
481const QString &KCompletion::lastMatch() const
482{
483 Q_D(const KCompletion);
484 return d->lastMatch;
485}
486
487QString KCompletion::previousMatch()
488{
489 Q_D(KCompletion);
490 QString completion;
491 d->lastMatch = d->currentMatch;
492
493 if (d->matches.isEmpty()) {
494 d->matches.findAllCompletions(treeRoot: d->m_treeRoot.get(), string: d->lastString, ignoreCase: d->ignoreCase, hasMultipleMatches&: d->hasMultipleMatches);
495 if (!d->matches.isEmpty()) {
496 completion = d->matches.last();
497 }
498 d->currentMatch = completion;
499 d->rotationIndex = 0;
500 postProcessMatch(&completion);
501 Q_EMIT match(item: completion);
502 return completion;
503 }
504
505 QStringList matches = d->matches.list();
506 d->lastMatch = matches[d->rotationIndex];
507
508 if (d->rotationIndex == 0) {
509 d->rotationIndex = matches.count();
510 }
511
512 d->rotationIndex--;
513
514 completion = matches[d->rotationIndex];
515 d->currentMatch = completion;
516 postProcessMatch(&completion);
517 Q_EMIT match(item: completion);
518 return completion;
519}
520
521QSharedPointer<KZoneAllocator> KCompTreeNode::m_alloc(new KZoneAllocator(8 * 1024));
522
523#include "moc_kcompletion.cpp"
524

source code of kcompletion/src/kcompletion.cpp