diff --git a/kdevplatform/language/interfaces/abbreviations.cpp b/kdevplatform/language/interfaces/abbreviations.cpp index f22ad4855d..41a7243278 100644 --- a/kdevplatform/language/interfaces/abbreviations.cpp +++ b/kdevplatform/language/interfaces/abbreviations.cpp @@ -1,158 +1,218 @@ /* This file is part of KDevelop Copyright 2014 Sven Brauch This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; see the file COPYING.LIB. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "abbreviations.h" #include +#include namespace KDevelop { bool matchesAbbreviationHelper(const QStringRef &word, const QString &typed, const QVarLengthArray< int, 32 > &offsets, int &depth, int atWord, int i) { 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; foreach ( const QChar c, typed ) { while ( c.toLower() != word.at(atLetter).toLower() ) { atLetter += 1; if ( atLetter >= word.size() ) { return false; } } } bool haveUnderscore = true; QVarLengthArray 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 ambigous 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(); } +PathFilterMatchQuality matchPathFilter(const Path &toFilter, const QStringList &text, + const QString &joinedText) +{ + const QVector& segments = toFilter.segments(); + + if (text.count() > segments.count()) { + // number of segments mismatches, thus item cannot match + return PathFilterMatchQuality::NoMatch; + } + { + bool allMatched = true; + // try to put exact matches up front + for(int i = segments.count() - 1, j = text.count() - 1; + i >= 0 && j >= 0; --i, --j) + { + if (segments.at(i) != text.at(j)) { + allMatched = false; + break; + } + } + if (allMatched) { + return PathFilterMatchQuality::ExactMatch; + } + } + + int searchIndex = 0; + int pathIndex = 0; + int lastMatchIndex = -1; + // stop early if more search fragments remain than available after path index + while (pathIndex < segments.size() && searchIndex < text.size() + && (pathIndex + text.size() - searchIndex - 1) < segments.size() ) + { + const QString& segment = segments.at(pathIndex); + const QString& typedSegment = text.at(searchIndex); + lastMatchIndex = segment.indexOf(typedSegment, 0, Qt::CaseInsensitive); + if (lastMatchIndex == -1 && !matchesAbbreviation(segment.midRef(0), typedSegment)) { + // no match, try with next path segment + ++pathIndex; + continue; + } + // else we matched + ++searchIndex; + ++pathIndex; + } + + if (searchIndex != text.size()) { + if ( ! matchesPath(segments.last(), joinedText) ) { + return PathFilterMatchQuality::NoMatch; + } + } + + // prefer matches whose last element starts with the filter + if (pathIndex == segments.size() && lastMatchIndex == 0) { + return PathFilterMatchQuality::StartMatch; + } else { + return PathFilterMatchQuality::OtherMatch; + } +} + } // namespace KDevelop // kate: space-indent on; indent-width 2 diff --git a/kdevplatform/language/interfaces/abbreviations.h b/kdevplatform/language/interfaces/abbreviations.h index 209a3f148c..7659d6b17d 100644 --- a/kdevplatform/language/interfaces/abbreviations.h +++ b/kdevplatform/language/interfaces/abbreviations.h @@ -1,55 +1,70 @@ /* This file is part of KDevelop Copyright 2014 Sven Brauch This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; see the file COPYING.LIB. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KDEVPLATFORM_ABBREVIATIONS_H #define KDEVPLATFORM_ABBREVIATIONS_H #include #include class QStringList; class QStringRef; class QString; namespace KDevelop { +class Path; + // Taken and adapted for kdevelop from katecompletionmodel.cpp KDEVPLATFORMLANGUAGE_EXPORT bool matchesAbbreviationHelper(const QStringRef& word, const QString& typed, const QVarLengthArray& offsets, int& depth, int atWord = -1, int i = 0); KDEVPLATFORMLANGUAGE_EXPORT bool matchesAbbreviation(const QStringRef& word, const QString& typed); KDEVPLATFORMLANGUAGE_EXPORT bool matchesPath(const QString& path, const QString& typed); /** * @brief Matches a word against a list of search fragments. * The word will be split at separation characters (space, / and ::) and * the resulting fragments will be matched one-by-one against the typed fragments. * If all typed fragments can be matched against a fragment in word in the right order * (skipping is allowed), true will be returned. * @param word the word to search in * @param typedFragments the fragments which were typed * @return bool true if match, else false */ KDEVPLATFORMLANGUAGE_EXPORT bool matchesAbbreviationMulti(const QString& word, const QStringList& typedFragments); + +enum class PathFilterMatchQuality +{ + NoMatch, + ExactMatch, + StartMatch, + OtherMatch +}; +/** + * @brief Matches a path against a list of search fragments. + */ +KDEVPLATFORMLANGUAGE_EXPORT PathFilterMatchQuality matchPathFilter(const Path& toFilter, const QStringList& text, + const QString& joinedText); } #endif // kate: space-indent on; indent-width 2 diff --git a/kdevplatform/language/interfaces/quickopenfilter.h b/kdevplatform/language/interfaces/quickopenfilter.h index 12ddad33d8..33285fdc67 100644 --- a/kdevplatform/language/interfaces/quickopenfilter.h +++ b/kdevplatform/language/interfaces/quickopenfilter.h @@ -1,280 +1,236 @@ /* * This file is part of KDevelop * * Copyright 2007 David Nolden * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public * License along with this program; if not, write to the * Free Software Foundation, Inc., * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KDEVPLATFORM_QUICKOPEN_FILTER_H #define KDEVPLATFORM_QUICKOPEN_FILTER_H #include #include "abbreviations.h" #include namespace KDevelop { /** * This is a simple filter-implementation that helps you implementing own quickopen data-providers. * You should use it when possible, because that way additional features(like regexp filtering) can * be implemented in a central place. * * This implementation does incremental filtering while * typing text, so it quite efficient for the most common case. * * The simplest way of using this is by reimplementing your data-provider * based on QuickOpenDataProviderBase and KDevelop::Filter\. * * What you need to do to use it: * * Reimplement itemText(..) to provide the text filtering * should be performend on(This must be efficient). * * Call setItems(..) when starting a new quickopen session, or when the content * changes, to initialize the filter with your data. * * Call setFilter(..) with the text that should be filtered for on user-input. * * Use filteredItems() to provide data to quickopen. * * @tparam Item should be the type that holds all the information you need. * The filter will hold the data, and you can access it through "items()". */ template class Filter { public: virtual ~Filter() { } ///Clears the filter, but not the data. void clearFilter() { m_filtered = m_items; m_oldFilterText.clear(); } ///Clears the filter and sets new data. The filter-text will be lost. void setItems(const QVector& data) { m_items = data; clearFilter(); } const QVector& items() const { return m_items; } ///Returns the data that is left after the filtering const QVector& filteredItems() const { return m_filtered; } ///Changes the filter-text and refilters the data void setFilter( const QString& text ) { if (m_oldFilterText == text) { return; } if (text.isEmpty()) { clearFilter(); return; } QVector filterBase = m_filtered; if( !text.startsWith( m_oldFilterText ) ) { filterBase = m_items; //Start filtering based on the whole data } m_filtered.clear(); QStringList typedFragments = text.split(QStringLiteral("::"), QString::SkipEmptyParts); if (typedFragments.isEmpty()) { clearFilter(); return; } if ( typedFragments.last().endsWith(':') ) { // remove the trailing colon if there's only one; otherwise, // this breaks incremental filtering typedFragments.last().chop(1); } if (typedFragments.size() == 1 && typedFragments.last().isEmpty()) { clearFilter(); return; } foreach( const Item& data, filterBase ) { const QString& itemData = itemText( data ); if( itemData.contains(text, Qt::CaseInsensitive) || matchesAbbreviationMulti(itemData, typedFragments) ) { m_filtered << data; } } m_oldFilterText = text; } protected: ///Should return the text an item should be filtered by. virtual QString itemText( const Item& data ) const = 0; private: QString m_oldFilterText; QVector m_filtered; QVector m_items; }; -} - -namespace KDevelop { template class PathFilter { public: ///Clears the filter, but not the data. void clearFilter() { m_filtered = m_items; m_oldFilterText.clear(); } ///Clears the filter and sets new data. The filter-text will be lost. void setItems(const QVector& data) { m_items = data; clearFilter(); } const QVector& items() const { return m_items; } ///Returns the data that is left after the filtering const QVector& filteredItems() const { return m_filtered; } ///Changes the filter-text and refilters the data void setFilter( const QStringList& text ) { if (m_oldFilterText == text) { return; } if (text.isEmpty()) { clearFilter(); return; } const QString joinedText = text.join(QString()); QVector filterBase = m_filtered; if ( m_oldFilterText.isEmpty()) { filterBase = m_items; } else if (m_oldFilterText.mid(0, m_oldFilterText.count() - 1) == text.mid(0, text.count() - 1) && text.last().startsWith(m_oldFilterText.last())) { //Good, the prefix is the same, and the last item has been extended } else if (m_oldFilterText.size() == text.size() - 1 && m_oldFilterText == text.mid(0, text.size() - 1)) { //Good, an item has been added } else { //Start filtering based on the whole data, there was a big change to the filter filterBase = m_items; } // filterBase is correctly sorted, to keep it that way we add // exact matches to this list in sorted way and then prepend the whole list in one go. QVector exactMatches; // similar for starting matches QVector startMatches; - // all other matches + // all other matches are sorted by where they match, we prefer matches at the end QVector otherMatches; foreach( const Item& data, filterBase ) { - const Path toFilter = static_cast(this)->itemPath(data); - const QVector& segments = toFilter.segments(); - - if (text.count() > segments.count()) { - // number of segments mismatches, thus item cannot match - continue; - } - { - bool allMatched = true; - // try to put exact matches up front - for(int i = segments.count() - 1, j = text.count() - 1; - i >= 0 && j >= 0; --i, --j) - { - if (segments.at(i) != text.at(j)) { - allMatched = false; - break; - } - } - if (allMatched) { - exactMatches << data; - continue; - } - } - - int searchIndex = 0; - int pathIndex = 0; - int lastMatchIndex = -1; - // stop early if more search fragments remain than available after path index - while (pathIndex < segments.size() && searchIndex < text.size() - && (pathIndex + text.size() - searchIndex - 1) < segments.size() ) - { - const QString& segment = segments.at(pathIndex); - const QString& typedSegment = text.at(searchIndex); - lastMatchIndex = segment.indexOf(typedSegment, 0, Qt::CaseInsensitive); - if (lastMatchIndex == -1 && !matchesAbbreviation(segment.midRef(0), typedSegment)) { - // no match, try with next path segment - ++pathIndex; - continue; - } - // else we matched - ++searchIndex; - ++pathIndex; - } - - if (searchIndex != text.size()) { - if ( ! matchesPath(segments.last(), joinedText) ) { - continue; - } - } - - // prefer matches whose last element starts with the filter - if (pathIndex == segments.size() && lastMatchIndex == 0) { + const auto matchQuality = matchPathFilter(static_cast(this)->itemPath(data), + text, joinedText); + switch (matchQuality) { + case PathFilterMatchQuality::NoMatch: + break; + case PathFilterMatchQuality::ExactMatch: + exactMatches << data; + break; + case PathFilterMatchQuality::StartMatch: startMatches << data; - } else { + break; + case PathFilterMatchQuality::OtherMatch: otherMatches << data; + break; } } m_filtered = exactMatches + startMatches + otherMatches; m_oldFilterText = text; } private: QStringList m_oldFilterText; QVector m_filtered; QVector m_items; }; } #endif