diff --git a/kdevplatform/language/interfaces/abbreviations.cpp b/kdevplatform/language/interfaces/abbreviations.cpp index 7530a1c779..69f64a92b8 100644 --- a/kdevplatform/language/interfaces/abbreviations.cpp +++ b/kdevplatform/language/interfaces/abbreviations.cpp @@ -1,227 +1,233 @@ /* 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 { // 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; 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) +int matchPathFilter(const Path &toFilter, const QStringList &text) { + enum PathFilterMatchQuality { + NoMatch = -1, + ExactMatch = 0, + StartMatch = 1, + OtherMatch = 2 // and anything higher than that + }; const QVector& segments = toFilter.segments(); if (text.count() > segments.count()) { // number of segments mismatches, thus item cannot match - return PathFilterMatchQuality::NoMatch; + return 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; + return 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); bool isMatch = lastMatchIndex != -1; // do fuzzy path matching on the last segment if (!isMatch && searchIndex == text.size() - 1 && pathIndex == segments.size() - 1) { isMatch = matchesPath(segment, typedSegment); } else if (!isMatch) { isMatch = matchesAbbreviation(segment.midRef(0), typedSegment); } if (!isMatch) { // no match, try with next path segment ++pathIndex; continue; } // else we matched ++searchIndex; ++pathIndex; } if (searchIndex != text.size()) { - return PathFilterMatchQuality::NoMatch; + return NoMatch; } // prefer matches whose last element starts with the filter if (pathIndex == segments.size() && lastMatchIndex == 0) { - return PathFilterMatchQuality::StartMatch; + return StartMatch; } else { - return PathFilterMatchQuality::OtherMatch; + return 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 edef277a0f..a72b802a08 100644 --- a/kdevplatform/language/interfaces/abbreviations.h +++ b/kdevplatform/language/interfaces/abbreviations.h @@ -1,65 +1,59 @@ /* 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; 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. + * @return -1 when no match is found, otherwise a positive integer, higher values mean lower quality */ -KDEVPLATFORMLANGUAGE_EXPORT PathFilterMatchQuality matchPathFilter(const Path& toFilter, const QStringList& text); +KDEVPLATFORMLANGUAGE_EXPORT int matchPathFilter(const Path& toFilter, const QStringList& text); } #endif // kate: space-indent on; indent-width 2 diff --git a/kdevplatform/language/interfaces/quickopenfilter.h b/kdevplatform/language/interfaces/quickopenfilter.h index 6ee4a10f22..9ea6dd7400 100644 --- a/kdevplatform/language/interfaces/quickopenfilter.h +++ b/kdevplatform/language/interfaces/quickopenfilter.h @@ -1,233 +1,227 @@ /* * 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; }; 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; } 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 are sorted by where they match, we prefer matches at the end - QVector otherMatches; - foreach( const Item& data, filterBase ) { + QVector> matches; + for (int i = 0, c = filterBase.size(); i < c; ++i) { + const auto& data = filterBase.at(i); const auto matchQuality = matchPathFilter(static_cast(this)->itemPath(data), text); - switch (matchQuality) { - case PathFilterMatchQuality::NoMatch: - break; - case PathFilterMatchQuality::ExactMatch: - exactMatches << data; - break; - case PathFilterMatchQuality::StartMatch: - startMatches << data; - break; - case PathFilterMatchQuality::OtherMatch: - otherMatches << data; - break; + if (matchQuality == -1) { + continue; } + matches.push_back({matchQuality, i}); } - - m_filtered = exactMatches + startMatches + otherMatches; + std::sort(matches.begin(), matches.end(), + [](const QPair& lhs, const QPair& rhs) + { + return lhs.first < rhs.first; + }); + m_filtered.resize(matches.size()); + std::transform(matches.begin(), matches.end(), m_filtered.begin(), + [&filterBase](const QPair& match) { + return filterBase.at(match.second); + }); m_oldFilterText = text; } private: QStringList m_oldFilterText; QVector m_filtered; QVector m_items; }; } #endif