File indexing completed on 2024-05-12 11:47:08
0001 /* 0002 This file is part of the KDE libraries 0003 SPDX-FileCopyrightText: 1999, 2000, 2001 Carsten Pfeiffer <pfeiffer@kde.org> 0004 0005 SPDX-License-Identifier: LGPL-2.0-or-later 0006 */ 0007 0008 #include "kcompletion.h" 0009 #include "kcompletion_p.h" 0010 #include <kcompletion_debug.h> 0011 0012 #include <QCollator> 0013 0014 void KCompletionPrivate::addWeightedItem(const QString &item) 0015 { 0016 Q_Q(KCompletion); 0017 if (order != KCompletion::Weighted) { 0018 q->addItem(item, 0); 0019 return; 0020 } 0021 0022 int len = item.length(); 0023 uint weight = 0; 0024 0025 // find out the weighting of this item (appended to the string as ":num") 0026 int index = item.lastIndexOf(QLatin1Char(':')); 0027 if (index > 0) { 0028 bool ok; 0029 #if QT_VERSION >= QT_VERSION_CHECK(6, 0, 0) 0030 weight = QStringView(item).mid(index + 1).toUInt(&ok); 0031 #else 0032 weight = item.midRef(index + 1).toUInt(&ok); 0033 #endif 0034 if (!ok) { 0035 weight = 0; 0036 } 0037 0038 len = index; // only insert until the ':' 0039 } 0040 0041 q->addItem(item.left(len), weight); 0042 return; 0043 } 0044 0045 // tries to complete "string" from the tree-root 0046 QString KCompletionPrivate::findCompletion(const QString &string) 0047 { 0048 QString completion; 0049 const KCompTreeNode *node = m_treeRoot.get(); 0050 0051 // start at the tree-root and try to find the search-string 0052 for (const auto ch : string) { 0053 node = node->find(ch); 0054 0055 if (node) { 0056 completion += ch; 0057 } else { 0058 return QString(); // no completion 0059 } 0060 } 0061 0062 // Now we have the last node of the to be completed string. 0063 // Follow it as long as it has exactly one child (= longest possible 0064 // completion) 0065 0066 while (node->childrenCount() == 1) { 0067 node = node->firstChild(); 0068 if (!node->isNull()) { 0069 completion += *node; 0070 } 0071 } 0072 // if multiple matches and auto-completion mode 0073 // -> find the first complete match 0074 if (node && node->childrenCount() > 1) { 0075 hasMultipleMatches = true; 0076 0077 if (completionMode == KCompletion::CompletionAuto) { 0078 rotationIndex = 1; 0079 if (order != KCompletion::Weighted) { 0080 while ((node = node->firstChild())) { 0081 if (!node->isNull()) { 0082 completion += *node; 0083 } else { 0084 break; 0085 } 0086 } 0087 } else { 0088 // don't just find the "first" match, but the one with the 0089 // highest priority 0090 0091 const KCompTreeNode *temp_node = nullptr; 0092 while (1) { 0093 int count = node->childrenCount(); 0094 temp_node = node->firstChild(); 0095 uint weight = temp_node->weight(); 0096 const KCompTreeNode *hit = temp_node; 0097 for (int i = 1; i < count; i++) { 0098 temp_node = node->childAt(i); 0099 if (temp_node->weight() > weight) { 0100 hit = temp_node; 0101 weight = hit->weight(); 0102 } 0103 } 0104 // 0x0 has the highest priority -> we have the best match 0105 if (hit->isNull()) { 0106 break; 0107 } 0108 0109 node = hit; 0110 completion += *node; 0111 } 0112 } 0113 } 0114 } 0115 0116 return completion; 0117 } 0118 0119 void KCompletionPrivate::defaultSort(QStringList &stringList) 0120 { 0121 QCollator c; 0122 c.setCaseSensitivity(Qt::CaseSensitive); 0123 std::stable_sort(stringList.begin(), stringList.end(), c); 0124 } 0125 0126 KCompletion::KCompletion() 0127 : d_ptr(new KCompletionPrivate(this)) 0128 { 0129 setOrder(Insertion); 0130 } 0131 0132 KCompletion::~KCompletion() 0133 { 0134 } 0135 0136 void KCompletion::setOrder(CompOrder order) 0137 { 0138 Q_D(KCompletion); 0139 d->order = order; 0140 d->matches.setSorting(order); 0141 } 0142 0143 KCompletion::CompOrder KCompletion::order() const 0144 { 0145 Q_D(const KCompletion); 0146 return d->order; 0147 } 0148 0149 void KCompletion::setIgnoreCase(bool ignoreCase) 0150 { 0151 Q_D(KCompletion); 0152 d->ignoreCase = ignoreCase; 0153 } 0154 0155 bool KCompletion::ignoreCase() const 0156 { 0157 Q_D(const KCompletion); 0158 return d->ignoreCase; 0159 } 0160 0161 void KCompletion::setItems(const QStringList &itemList) 0162 { 0163 clear(); 0164 insertItems(itemList); 0165 } 0166 0167 void KCompletion::insertItems(const QStringList &items) 0168 { 0169 Q_D(KCompletion); 0170 for (const auto &str : items) { 0171 if (d->order == Weighted) { 0172 d->addWeightedItem(str); 0173 } else { 0174 addItem(str, 0); 0175 } 0176 } 0177 } 0178 0179 QStringList KCompletion::items() const 0180 { 0181 Q_D(const KCompletion); 0182 KCompletionMatchesWrapper list(d->sorterFunction); // unsorted 0183 list.extractStringsFromNode(d->m_treeRoot.get(), QString(), d->order == Weighted); 0184 return list.list(); 0185 } 0186 0187 bool KCompletion::isEmpty() const 0188 { 0189 Q_D(const KCompletion); 0190 return (d->m_treeRoot->childrenCount() == 0); 0191 } 0192 0193 void KCompletion::postProcessMatch(QString *) const 0194 { 0195 } 0196 0197 void KCompletion::postProcessMatches(QStringList *) const 0198 { 0199 } 0200 0201 void KCompletion::postProcessMatches(KCompletionMatches *) const 0202 { 0203 } 0204 0205 void KCompletion::addItem(const QString &item) 0206 { 0207 Q_D(KCompletion); 0208 d->matches.clear(); 0209 d->rotationIndex = 0; 0210 d->lastString.clear(); 0211 0212 addItem(item, 0); 0213 } 0214 0215 void KCompletion::addItem(const QString &item, uint weight) 0216 { 0217 Q_D(KCompletion); 0218 if (item.isEmpty()) { 0219 return; 0220 } 0221 0222 KCompTreeNode *node = d->m_treeRoot.get(); 0223 int len = item.length(); 0224 0225 bool sorted = (d->order == Sorted); 0226 bool weighted = ((d->order == Weighted) && weight > 1); 0227 0228 // knowing the weight of an item, we simply add this weight to all of its 0229 // nodes. 0230 0231 for (int i = 0; i < len; i++) { 0232 node = node->insert(item.at(i), sorted); 0233 if (weighted) { 0234 node->confirm(weight - 1); // node->insert() sets weighting to 1 0235 } 0236 } 0237 0238 // add 0x0-item as delimiter with evtl. weight 0239 node = node->insert(QChar(0x0), true); 0240 if (weighted) { 0241 node->confirm(weight - 1); 0242 } 0243 // qDebug("*** added: %s (%i)", item.toLatin1().constData(), node->weight()); 0244 } 0245 0246 void KCompletion::removeItem(const QString &item) 0247 { 0248 Q_D(KCompletion); 0249 d->matches.clear(); 0250 d->rotationIndex = 0; 0251 d->lastString.clear(); 0252 0253 d->m_treeRoot->remove(item); 0254 } 0255 0256 void KCompletion::clear() 0257 { 0258 Q_D(KCompletion); 0259 d->matches.clear(); 0260 d->rotationIndex = 0; 0261 d->lastString.clear(); 0262 0263 d->m_treeRoot.reset(new KCompTreeNode); 0264 } 0265 0266 QString KCompletion::makeCompletion(const QString &string) 0267 { 0268 Q_D(KCompletion); 0269 if (d->completionMode == CompletionNone) { 0270 return QString(); 0271 } 0272 0273 // qDebug() << "KCompletion: completing: " << string; 0274 0275 d->matches.clear(); 0276 d->rotationIndex = 0; 0277 d->hasMultipleMatches = false; 0278 d->lastMatch = d->currentMatch; 0279 0280 // in Shell-completion-mode, emit all matches when we get the same 0281 // complete-string twice 0282 if (d->completionMode == CompletionShell && string == d->lastString) { 0283 // Don't use d->matches since calling postProcessMatches() 0284 // on d->matches here would interfere with call to 0285 // postProcessMatch() during rotation 0286 0287 d->matches.findAllCompletions(d->m_treeRoot.get(), string, d->ignoreCase, d->hasMultipleMatches); 0288 QStringList l = d->matches.list(); 0289 postProcessMatches(&l); 0290 Q_EMIT matches(l); 0291 0292 return QString(); 0293 } 0294 0295 QString completion; 0296 // in case-insensitive popup mode, we search all completions at once 0297 if (d->completionMode == CompletionPopup || d->completionMode == CompletionPopupAuto) { 0298 d->matches.findAllCompletions(d->m_treeRoot.get(), string, d->ignoreCase, d->hasMultipleMatches); 0299 if (!d->matches.isEmpty()) { 0300 completion = d->matches.first(); 0301 } 0302 } else { 0303 completion = d->findCompletion(string); 0304 } 0305 0306 if (d->hasMultipleMatches) { 0307 Q_EMIT multipleMatches(); 0308 } 0309 0310 d->lastString = string; 0311 d->currentMatch = completion; 0312 0313 postProcessMatch(&completion); 0314 0315 if (!string.isEmpty()) { // only emit match when string is not empty 0316 // qDebug() << "KCompletion: Match: " << completion; 0317 Q_EMIT match(completion); 0318 } 0319 0320 return completion; 0321 } 0322 0323 QStringList KCompletion::substringCompletion(const QString &string) const 0324 { 0325 Q_D(const KCompletion); 0326 // get all items in the tree, eventually in sorted order 0327 KCompletionMatchesWrapper allItems(d->sorterFunction, d->order); 0328 allItems.extractStringsFromNode(d->m_treeRoot.get(), QString(), false); 0329 0330 QStringList list = allItems.list(); 0331 0332 // subStringMatches is invoked manually, via a shortcut 0333 if (list.isEmpty()) { 0334 return list; 0335 } 0336 0337 if (!string.isEmpty()) { // If it's empty, nothing to compare 0338 auto it = std::remove_if(list.begin(), list.end(), [&string](const QString &item) { 0339 return !item.contains(string, Qt::CaseInsensitive); // always case insensitive 0340 }); 0341 list.erase(it, list.end()); 0342 } 0343 0344 postProcessMatches(&list); 0345 return list; 0346 } 0347 0348 void KCompletion::setCompletionMode(CompletionMode mode) 0349 { 0350 Q_D(KCompletion); 0351 d->completionMode = mode; 0352 } 0353 0354 KCompletion::CompletionMode KCompletion::completionMode() const 0355 { 0356 Q_D(const KCompletion); 0357 return d->completionMode; 0358 } 0359 0360 void KCompletion::setShouldAutoSuggest(const bool shouldAutoSuggest) 0361 { 0362 Q_D(KCompletion); 0363 d->shouldAutoSuggest = shouldAutoSuggest; 0364 } 0365 0366 bool KCompletion::shouldAutoSuggest() const 0367 { 0368 Q_D(const KCompletion); 0369 return d->shouldAutoSuggest; 0370 } 0371 0372 void KCompletion::setSorterFunction(SorterFunction sortFunc) 0373 { 0374 Q_D(KCompletion); 0375 d->sorterFunction = sortFunc ? sortFunc : KCompletionPrivate::defaultSort; 0376 } 0377 0378 QStringList KCompletion::allMatches() 0379 { 0380 Q_D(KCompletion); 0381 // Don't use d->matches since calling postProcessMatches() 0382 // on d->matches here would interfere with call to 0383 // postProcessMatch() during rotation 0384 KCompletionMatchesWrapper matches(d->sorterFunction, d->order); 0385 bool dummy; 0386 matches.findAllCompletions(d->m_treeRoot.get(), d->lastString, d->ignoreCase, dummy); 0387 QStringList l = matches.list(); 0388 postProcessMatches(&l); 0389 return l; 0390 } 0391 0392 KCompletionMatches KCompletion::allWeightedMatches() 0393 { 0394 Q_D(KCompletion); 0395 // Don't use d->matches since calling postProcessMatches() 0396 // on d->matches here would interfere with call to 0397 // postProcessMatch() during rotation 0398 KCompletionMatchesWrapper matches(d->sorterFunction, d->order); 0399 bool dummy; 0400 matches.findAllCompletions(d->m_treeRoot.get(), d->lastString, d->ignoreCase, dummy); 0401 KCompletionMatches ret(matches); 0402 postProcessMatches(&ret); 0403 return ret; 0404 } 0405 0406 QStringList KCompletion::allMatches(const QString &string) 0407 { 0408 Q_D(KCompletion); 0409 KCompletionMatchesWrapper matches(d->sorterFunction, d->order); 0410 bool dummy; 0411 matches.findAllCompletions(d->m_treeRoot.get(), string, d->ignoreCase, dummy); 0412 QStringList l = matches.list(); 0413 postProcessMatches(&l); 0414 return l; 0415 } 0416 0417 KCompletionMatches KCompletion::allWeightedMatches(const QString &string) 0418 { 0419 Q_D(KCompletion); 0420 KCompletionMatchesWrapper matches(d->sorterFunction, d->order); 0421 bool dummy; 0422 matches.findAllCompletions(d->m_treeRoot.get(), string, d->ignoreCase, dummy); 0423 KCompletionMatches ret(matches); 0424 postProcessMatches(&ret); 0425 return ret; 0426 } 0427 0428 void KCompletion::setSoundsEnabled(bool enable) 0429 { 0430 Q_D(KCompletion); 0431 d->beep = enable; 0432 } 0433 0434 bool KCompletion::soundsEnabled() const 0435 { 0436 Q_D(const KCompletion); 0437 return d->beep; 0438 } 0439 0440 bool KCompletion::hasMultipleMatches() const 0441 { 0442 Q_D(const KCompletion); 0443 return d->hasMultipleMatches; 0444 } 0445 0446 ///////////////////////////////////////////////////// 0447 ///////////////// tree operations /////////////////// 0448 0449 QString KCompletion::nextMatch() 0450 { 0451 Q_D(KCompletion); 0452 QString completion; 0453 d->lastMatch = d->currentMatch; 0454 0455 if (d->matches.isEmpty()) { 0456 d->matches.findAllCompletions(d->m_treeRoot.get(), d->lastString, d->ignoreCase, d->hasMultipleMatches); 0457 if (!d->matches.isEmpty()) { 0458 completion = d->matches.first(); 0459 } 0460 d->currentMatch = completion; 0461 d->rotationIndex = 0; 0462 postProcessMatch(&completion); 0463 Q_EMIT match(completion); 0464 return completion; 0465 } 0466 0467 QStringList matches = d->matches.list(); 0468 d->lastMatch = matches[d->rotationIndex++]; 0469 0470 if (d->rotationIndex == matches.count()) { 0471 d->rotationIndex = 0; 0472 } 0473 0474 completion = matches[d->rotationIndex]; 0475 d->currentMatch = completion; 0476 postProcessMatch(&completion); 0477 Q_EMIT match(completion); 0478 return completion; 0479 } 0480 0481 const QString &KCompletion::lastMatch() const 0482 { 0483 Q_D(const KCompletion); 0484 return d->lastMatch; 0485 } 0486 0487 QString KCompletion::previousMatch() 0488 { 0489 Q_D(KCompletion); 0490 QString completion; 0491 d->lastMatch = d->currentMatch; 0492 0493 if (d->matches.isEmpty()) { 0494 d->matches.findAllCompletions(d->m_treeRoot.get(), d->lastString, d->ignoreCase, d->hasMultipleMatches); 0495 if (!d->matches.isEmpty()) { 0496 completion = d->matches.last(); 0497 } 0498 d->currentMatch = completion; 0499 d->rotationIndex = 0; 0500 postProcessMatch(&completion); 0501 Q_EMIT match(completion); 0502 return completion; 0503 } 0504 0505 QStringList matches = d->matches.list(); 0506 d->lastMatch = matches[d->rotationIndex]; 0507 0508 if (d->rotationIndex == 0) { 0509 d->rotationIndex = matches.count(); 0510 } 0511 0512 d->rotationIndex--; 0513 0514 completion = matches[d->rotationIndex]; 0515 d->currentMatch = completion; 0516 postProcessMatch(&completion); 0517 Q_EMIT match(completion); 0518 return completion; 0519 } 0520 0521 QSharedPointer<KZoneAllocator> KCompTreeNode::m_alloc(new KZoneAllocator(8 * 1024)); 0522 0523 #include "moc_kcompletion.cpp"