File indexing completed on 2024-05-12 04:38:07

 /*
     SPDX-FileCopyrightText: 2014 Sven Brauch <svenbrauch@gmail.com>
 
     SPDX-License-Identifier: LGPL-2.0-or-later
 */
 
 #include "abbreviations.h"
 
 #include <QStringList>
 #include <util/path.h>
 
 namespace KDevelop {
 // Taken and adapted for kdevelop from katecompletionmodel.cpp
 static bool matchesAbbreviationHelper(const QStringRef& word, const QString& typed,
                                       const QVarLengthArray<int, 32>& offsets,
                                       int& depth, int atWord = -1, int i = 0)
 {
     int atLetter = 1;
     for (; i < typed.size(); i++) {
         const QChar c = typed.at(i).toLower();
         bool haveNextWord = offsets.size() > atWord + 1;
         bool canCompare = atWord != -1 && word.size() > offsets.at(atWord) + atLetter;
         if (canCompare && c == word.at(offsets.at(atWord) + atLetter).toLower()) {
             // the typed letter matches a letter after the current word beginning
             if (!haveNextWord || c != word.at(offsets.at(atWord + 1)).toLower()) {
                 // good, simple case, no conflict
                 atLetter += 1;
                 continue;
             }
             // For maliciously crafted data, the code used here theoretically can have very high
             // complexity. Thus ensure we don't run into this case, by limiting the amount of branches
             // we walk through to 128.
             depth++;
             if (depth > 128) {
                 return false;
             }
             // the letter matches both the next word beginning and the next character in the word
             if (haveNextWord && matchesAbbreviationHelper(word, typed, offsets, depth, atWord + 1, i + 1)) {
                 // resolving the conflict by taking the next word's first character worked, fine
                 return true;
             }
             // otherwise, continue by taking the next letter in the current word.
             atLetter += 1;
             continue;
         } else if (haveNextWord && c == word.at(offsets.at(atWord + 1)).toLower()) {
             // the typed letter matches the next word beginning
             atWord++;
             atLetter = 1;
             continue;
         }
         // no match
         return false;
     }
 
     // all characters of the typed word were matched
     return true;
 }
 
 bool matchesAbbreviation(const QStringRef& word, const QString& typed)
 {
     // A mismatch is very likely for random even for the first letter,
     // thus this optimization makes sense.
     if (word.at(0).toLower() != typed.at(0).toLower()) {
         return false;
     }
 
     // First, check if all letters are contained in the word in the right order.
     int atLetter = 0;
     for (const QChar c : typed) {
         while (c.toLower() != word.at(atLetter).toLower()) {
             atLetter += 1;
             if (atLetter >= word.size()) {
                 return false;
             }
         }
     }
 
     bool haveUnderscore = true;
     QVarLengthArray<int, 32> offsets;
     // We want to make "KComplM" match "KateCompletionModel"; this means we need
     // to allow parts of the typed text to be not part of the actual abbreviation,
     // which consists only of the uppercased / underscored letters (so "KCM" in this case).
     // However it might be ambiguous whether a letter is part of such a word or part of
     // the following abbreviation, so we need to find all possible word offsets first,
     // then compare.
     for (int i = 0; i < word.size(); i++) {
         const QChar c = word.at(i);
         if (c == QLatin1Char('_') || c == QLatin1Char('-')) {
             haveUnderscore = true;
         } else if (haveUnderscore || c.isUpper()) {
             offsets.append(i);
             haveUnderscore = false;
         }
     }
 
     int depth = 0;
     return matchesAbbreviationHelper(word, typed, offsets, depth);
 }
 
 bool matchesPath(const QString& path, const QString& typed)
 {
     int consumed = 0;
     int pos = 0;
     // try to find all the characters in typed in the right order in the path;
     // jumps are allowed everywhere
     while (consumed < typed.size() && pos < path.size()) {
         if (typed.at(consumed).toLower() == path.at(pos).toLower()) {
             consumed++;
         }
         pos++;
     }
     return consumed == typed.size();
 }
 
 bool matchesAbbreviationMulti(const QString& word, const QStringList& typedFragments)
 {
     if (word.size() == 0) {
         return true;
     }
     int lastSpace = 0;
     int matchedFragments = 0;
     for (int i = 0; i < word.size(); i++) {
         const QChar& c = word.at(i);
         bool isDoubleColon = false;
         // if it's not a separation char, walk over it.
         if (c != QLatin1Char(' ') && c != QLatin1Char('/') && i != word.size() - 1) {
             if (c != QLatin1Char(':') && i < word.size() - 1 && word.at(i + 1) != QLatin1Char(':')) {
                 continue;
             }
             isDoubleColon = true;
             i++;
         }
         // if it's '/', ' ' or '::', split the word here and check the next sub-word.
         const QStringRef wordFragment = word.midRef(lastSpace, i - lastSpace);
         const QString& typedFragment = typedFragments.at(matchedFragments);
         Q_ASSERT(!typedFragment.isEmpty());
         if (!wordFragment.isEmpty() && matchesAbbreviation(wordFragment, typedFragment)) {
             matchedFragments += 1;
             if (matchedFragments == typedFragments.size()) {
                 break;
             }
         }
         lastSpace = isDoubleColon ? i : i + 1;
     }
 
     return matchedFragments == typedFragments.size();
 }
 
 int matchPathFilter(const Path& toFilter, const QStringList& text, const Path& prefixPath)
 {
     enum PathFilterMatchQuality {
         NoMatch = -1,
         ExactMatch = 0,
         StartMatch = 1,
         OtherMatch = 2 // and anything higher than that
     };
     const QVector<QString>& segments = toFilter.segments();
 
     if (text.count() > segments.count()) {
         // number of segments mismatches, thus item cannot match
         return NoMatch;
     }
 
     bool allMatched = true;
     int searchIndex = text.size() - 1;
     int pathIndex = segments.size() - 1;
     int lastMatchIndex = -1;
     // stop early if more search fragments remain than available after path index
     while (pathIndex >= 0 && searchIndex >= 0
            && (pathIndex + text.size() - searchIndex - 1) < segments.size()) {
         const QString& segment = segments.at(pathIndex);
         const QString& typedSegment = text.at(searchIndex);
         const int matchIndex = segment.indexOf(typedSegment, 0, Qt::CaseInsensitive);
         const bool isLastPathSegment = pathIndex == segments.size() - 1;
         const bool isLastSearchSegment = searchIndex == text.size() - 1;
 
         // check for exact matches
         allMatched &= matchIndex == 0 && segment.size() == typedSegment.size();
 
         // check for fuzzy matches
         bool isMatch = matchIndex != -1;
         // do fuzzy path matching on the last segment
         if (!isMatch && isLastPathSegment && isLastSearchSegment) {
             isMatch = matchesPath(segment, typedSegment);
         } else if (!isMatch) { // check other segments for abbreviations
             isMatch = matchesAbbreviation(segment.midRef(0), typedSegment);
         }
 
         if (!isMatch) {
             // no match, try with next path segment
             --pathIndex;
             continue;
         }
         // else we matched
         if (isLastPathSegment) {
             lastMatchIndex = matchIndex;
         }
         --searchIndex;
         --pathIndex;
     }
 
     if (searchIndex != -1) {
         return NoMatch;
     }
 
     const int segmentMatchDistance = segments.size() - (pathIndex + 1);
     const bool inPrefixPath = segmentMatchDistance > (segments.size() - prefixPath.segments().size())
                               && prefixPath.isParentOf(toFilter);
     // penalize matches that fall into the shared suffix
     const int penalty = (inPrefixPath) ? 1024 : 0;
 
     if (allMatched && !inPrefixPath) {
         return ExactMatch + penalty;
     } else if (lastMatchIndex == 0) {
         // prefer matches whose last element starts with the filter
         return StartMatch + penalty;
     } else {
         // prefer matches closer to the end of the path
         return OtherMatch + segmentMatchDistance + penalty;
     }
 }
 } // namespace KDevelop