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