tabbreviations.cpp - sailfish-safe - Sailfish frontend for safe(1)
(HTM) git clone git://git.z3bra.org/sailfish-safe.git
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
tabbreviations.cpp (7509B)
---
1 /*
2 * Borrowed from KDevelop (kdevplatform/language/interfaces/abbreviations.cpp)
3 *
4 * Copyright 2014 Sven Brauch <svenbrauch@gmail.com>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB. If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 */
21
22 #include "abbreviations.h"
23
24 #include <QStringList>
25 #include <QVarLengthArray>
26
27 namespace {
28
29 // Taken and adapted for kdevelop from katecompletionmodel.cpp
30 static bool matchesAbbreviationHelper(const QStringRef &word, const QStringRef &typed,
31 const QVarLengthArray< int, 32 > &offsets,
32 int &depth, int atWord = -1, int i = 0)
33 {
34 int atLetter = 1;
35 for ( ; i < typed.size(); i++ ) {
36 const QChar c = typed.at(i).toLower();
37 bool haveNextWord = offsets.size() > atWord + 1;
38 bool canCompare = atWord != -1 && word.size() > offsets.at(atWord) + atLetter;
39 if (canCompare && c == word.at(offsets.at(atWord) + atLetter).toLower()) {
40 // the typed letter matches a letter after the current word beginning
41 if (!haveNextWord || c != word.at(offsets.at(atWord + 1)).toLower()) {
42 // good, simple case, no conflict
43 atLetter += 1;
44 continue;
45 }
46 // For maliciously crafted data, the code used here theoretically can have very high
47 // complexity. Thus ensure we don't run into this case, by limiting the amount of branches
48 // we walk through to 128.
49 depth++;
50 if (depth > 128) {
51 return false;
52 }
53 // the letter matches both the next word beginning and the next character in the word
54 if (haveNextWord && matchesAbbreviationHelper(word, typed, offsets, depth, atWord + 1, i + 1)) {
55 // resolving the conflict by taking the next word's first character worked, fine
56 return true;
57 }
58 // otherwise, continue by taking the next letter in the current word.
59 atLetter += 1;
60 continue;
61 } else if (haveNextWord && c == word.at(offsets.at(atWord + 1)).toLower()) {
62 // the typed letter matches the next word beginning
63 atWord++;
64 atLetter = 1;
65 continue;
66 }
67 // no match
68 return false;
69 }
70 // all characters of the typed word were matched
71 return true;
72 }
73
74 }
75
76 bool PlasmaPass::matchesAbbreviation(const QStringRef &word, const QStringRef &typed)
77 {
78 // A mismatch is very likely for random even for the first letter,
79 // thus this optimization makes sense.
80 if (word.at(0).toLower() != typed.at(0).toLower()) {
81 return false;
82 }
83
84 // First, check if all letters are contained in the word in the right order.
85 int atLetter = 0;
86 for (const auto c : typed) {
87 while (c.toLower() != word.at(atLetter).toLower()) {
88 atLetter += 1;
89 if (atLetter >= word.size()) {
90 return false;
91 }
92 }
93 }
94
95 bool haveUnderscore = true;
96 QVarLengthArray<int, 32> offsets;
97 // We want to make "KComplM" match "KateCompletionModel"; this means we need
98 // to allow parts of the typed text to be not part of the actual abbreviation,
99 // which consists only of the uppercased / underscored letters (so "KCM" in this case).
100 // However it might be ambigous whether a letter is part of such a word or part of
101 // the following abbreviation, so we need to find all possible word offsets first,
102 // then compare.
103 for (int i = 0; i < word.size(); ++i) {
104 const QChar c = word.at(i);
105 if (c == QLatin1Char('_') || c == QLatin1Char('-')) {
106 haveUnderscore = true;
107 } else if (haveUnderscore || c.isUpper()) {
108 offsets.append(i);
109 haveUnderscore = false;
110 }
111 }
112 int depth = 0;
113 return matchesAbbreviationHelper(word, typed, offsets, depth);
114 }
115
116 bool PlasmaPass::matchesPath(const QStringRef &path, const QStringRef &typed)
117 {
118 int consumed = 0;
119 int pos = 0;
120 // try to find all the characters in typed in the right order in the path;
121 // jumps are allowed everywhere
122 while (consumed < typed.size() && pos < path.size()) {
123 if (typed.at(consumed).toLower() == path.at(pos).toLower()) {
124 consumed++;
125 }
126 pos++;
127 }
128 return consumed == typed.size();
129 }
130
131 int PlasmaPass::matchPathFilter(const QVector<QStringRef> &toFilter, const QVector<QStringRef> &text)
132 {
133 enum PathFilterMatchQuality {
134 NoMatch = -1,
135 ExactMatch = 0,
136 StartMatch = 1,
137 OtherMatch = 2 // and anything higher than that
138 };
139 const auto segments = toFilter;
140
141 if (text.count() > segments.count()) {
142 // number of segments mismatches, thus item cannot match
143 return NoMatch;
144 }
145
146 bool allMatched = true;
147 int searchIndex = text.size() - 1;
148 int pathIndex = segments.size() - 1;
149 int lastMatchIndex = -1;
150 // stop early if more search fragments remain than available after path index
151 while (pathIndex >= 0 && searchIndex >= 0
152 && (pathIndex + text.size() - searchIndex - 1) < segments.size())
153 {
154 const auto &segment = segments.at(pathIndex);
155 const auto &typedSegment = text.at(searchIndex);
156 const int matchIndex = segment.indexOf(typedSegment, 0, Qt::CaseInsensitive);
157 const bool isLastPathSegment = pathIndex == segments.size() - 1;
158 const bool isLastSearchSegment = searchIndex == text.size() - 1;
159
160 // check for exact matches
161 allMatched &= matchIndex == 0 && segment.size() == typedSegment.size();
162
163 // check for fuzzy matches
164 bool isMatch = matchIndex != -1;
165 // do fuzzy path matching on the last segment
166 if (!isMatch && isLastPathSegment && isLastSearchSegment) {
167 isMatch = matchesPath(segment, typedSegment);
168 } else if (!isMatch) { // check other segments for abbreviations
169 isMatch = matchesAbbreviation(segment.mid(0), typedSegment);
170 }
171
172 if (!isMatch) {
173 // no match, try with next path segment
174 --pathIndex;
175 continue;
176 }
177 // else we matched
178 if (isLastPathSegment) {
179 lastMatchIndex = matchIndex;
180 }
181 --searchIndex;
182 --pathIndex;
183 }
184
185 if (searchIndex != -1) {
186 return NoMatch;
187 }
188
189 const int segmentMatchDistance = segments.size() - (pathIndex + 1);
190
191 if (allMatched) {
192 return ExactMatch;
193 } else if (lastMatchIndex == 0) {
194 // prefer matches whose last element starts with the filter
195 return StartMatch;
196 } else {
197 // prefer matches closer to the end of the path
198 return OtherMatch + segmentMatchDistance;
199 }
200 }