1/*
2 This file is part of the KDE libraries
3
4 SPDX-FileCopyrightText: 2017 Forrest Smith <forrestthewoods@gmail.com>
5 SPDX-FileCopyrightText: 2021 Waqar Ahmed <waqar.17a@gmail.com>
6
7 SPDX-License-Identifier: LGPL-2.0-or-later
8*/
9#ifndef KFUZZYMATCHER_H
10#define KFUZZYMATCHER_H
11
12#include <kcoreaddons_export.h>
13
14#include <QtContainerFwd>
15#include <QtGlobal>
16
17class QString;
18class QStringView;
19
20/**
21 * This namespace contains functions for fuzzy matching a list of strings
22 * against a pattern.
23 *
24 * This code is ported to Qt from lib_fts:
25 * https://github.com/forrestthewoods/lib_fts
26 * which tries to replicate SublimeText like fuzzy matching.
27 *
28 * @note
29 * All character matches will happen sequentially. That means that this function is not
30 * typo tolerant i.e., "gti" will not match "git", but "gt" will. All methods in here are
31 * stateless i.e., the input string will not be modified. Also note that strings in all the
32 * functions in this namespace will be matched case-insensitively.
33 *
34 * Limitations:
35 * - Currently this will match only strings with length < 256 correctly. This is because we
36 * intend on matching a pattern against words / short strings and not paragraphs.
37 * - No more than 256 matches will happen.
38 *
39 * If you are using this with @c QSortFilterProxyModel, you need to override both
40 * @c QSortFilterProxyModel::lessThan and @c QSortFilterProxyModel::filterAcceptsRow.
41 * A simple example:
42 *
43 * \code
44 bool filterAcceptsRow(int sourceRow, const QModelIndex &sourceParent) const override
45 {
46 int score = 0;
47 const auto idx = sourceModel()->index(sourceRow, 0, sourceParent);
48 const auto actionName = idx.data().toString().splitRef(QLatin1Char(':')).at(1);
49 const bool res = kfts::fuzzy_match_sequential(m_pattern, actionName, score);
50 // store the score in the source model
51 sourceModel()->setData(idx, score, ScoreRole);
52 return res;
53 }
54
55 bool lessThan(const QModelIndex &sourceLeft, const QModelIndex &sourceRight) const override
56 {
57 // use the score here to sort
58 const int l = sourceLeft.data(ScoreRole).toInt();
59 const int r = sourceRight.data(ScoreRole).toInt();
60 return l < r;
61 }
62 * \endcode
63 *
64 * Additionally you must not use @c invalidateFilter() if you go with the above approach. Instead
65 * use @c beginResetModel()/@c endResetModel():
66 *
67 * \code
68 * Q_SLOT void setFilterString(const QString &string)
69 {
70 beginResetModel();
71 m_pattern = string;
72 endResetModel();
73 }
74 * \endcode
75 *
76 * @short Namespace for fuzzy matching of strings
77 * @author Waqar Ahmed <waqar.17a@gmail.com>
78 */
79namespace KFuzzyMatcher
80{
81/**
82 * @brief The result of a fuzzy match
83 */
84struct KCOREADDONS_EXPORT Result {
85 /**
86 * Score of this match. This can be negative.if matched is @c false
87 * then the score will be zero.
88 */
89 int score = 0;
90 /** @c true if match was successful */
91 bool matched = false;
92};
93
94/**
95 * @brief A range representing a matched sequence in a string
96 *
97 * @since 5.84
98 */
99struct KCOREADDONS_EXPORT Range {
100 int start;
101 int length;
102};
103
104/**
105 * @brief The type of matches to consider when requesting for ranges.
106 * @see matchedRanges
107 *
108 * @since 5.84
109 */
110enum class RangeType : unsigned char {
111 /**
112 * We want ranges only where the pattern fully matches the user
113 * supplied string
114 */
115 FullyMatched,
116 /**
117 * We want ranges for all matches, even if the pattern partially
118 * matched the user supplied string
119 */
120 All
121};
122
123/**
124 * @brief Simple fuzzy matching of chars in @p pattern with chars in @p str
125 * sequentially. If there is a match, it will return true and false otherwise.
126 * There is no scoring. You should use this if score is not important for you
127 * and only matching is important.
128 *
129 * If @p pattern is empty, the function will return @c true
130 *
131 * @param pattern to search for. For e.g., text entered by a user to filter a
132 * list
133 * @param str the current string from your list of strings
134 * @return @c true on sucessful match
135 *
136 * @since 5.79
137 */
138KCOREADDONS_EXPORT bool matchSimple(QStringView pattern, QStringView str);
139
140/**
141 * @brief This is the main function which does scored fuzzy matching.
142 *
143 * The return value of this function contains Result#score which should be used to
144 * sort the results. Without sorting of the results this function won't very effective.
145 *
146 * If @p pattern is empty, the function will return @c true
147 *
148 * @param pattern to search for. For e.g., text entered by a user to filter a
149 * list or model
150 * @param str the current string from your list of strings
151 * @return A Result type with score of this match and whether the match was
152 * successful. If there is no match, score is zero. If the match is successful,
153 * score must be used to sort the results.
154 *
155 * @since 5.79
156 */
157KCOREADDONS_EXPORT Result match(QStringView pattern, QStringView str);
158
159/**
160 * @brief A function which returns the positions + lengths where the @p pattern matched
161 * inside the @p str. The resulting ranges can then be utilized to show the user where
162 * the matches occurred. Example:
163 *
164 * @code
165 * String: hello
166 * Pattern: Hlo
167 *
168 * Output: [Range{0, 1}, Range{3, 2}]
169 * @endcode
170 *
171 * In the above example @c "Hlo" matched inside the string @c "hello" in two places i.e.,
172 * position 0 and position 3. At position 0 it matched 'h', and at position 3 it
173 * matched 'lo'.
174 *
175 * The ranges themeselves can't do much so you will have to make the result useful
176 * in your own way. Some possible uses can be:
177 * - Transform the result into a vector of @c QTextLayout::FormatRange and then paint
178 * them in the view
179 * - Use the result to transform the string into html, for example conver the string from
180 * above example to "\<b\>H\</b\>el\<b\>lo\</b\>, and then use @c QTextDocument
181 * to paint it into your view.
182 *
183 * Example with the first method:
184 * @code
185 * auto ranges = KFuzzyMatcher::matchedRanges(pattern, string);
186 * QList<QTextLayout::FormatRange> out;
187 * std::transform(ranges.begin(), ranges.end(), std::back_inserter(out), [](const KFuzzyMatcher::Range &fr){
188 * return QTextLayout::FormatRange{fr.start, fr.length, QTextCharFormat()};
189 * });
190 *
191 * QTextLayout layout(text, font);
192 * layout.beginLayout();
193 * QTextLine line = layout.createLine();
194 * //...
195 * layout.endLayout();
196 *
197 * layout.setFormats(layout.formats() + out);
198 * layout.draw(painter, position);
199 * @endcode
200 *
201 * If @p pattern is empty, the function will return an empty vector
202 *
203 * if @p type is @c RangeType::All, the function will try to get ranges even if
204 * the pattern didn't fully match. For example:
205 * @code
206 * pattern: "git"
207 * string: "gti"
208 * RangeType: All
209 *
210 * Output: [Range{0, 1}, Range{2, 1}]
211 * @endcode
212 *
213 * @param pattern to search for. For e.g., text entered by a user to filter a
214 * list or model
215 * @param str the current string from your list of strings
216 * @param type whether to consider ranges from full matches only or all matches including partial matches
217 * @return A vector of ranges containing positions and lengths where the pattern
218 * matched. If there was no match, the vector will be empty
219 *
220 * @since 5.84
221 */
222KCOREADDONS_EXPORT QList<KFuzzyMatcher::Range> matchedRanges(QStringView pattern, QStringView str, RangeType type = RangeType::FullyMatched);
223
224} // namespace KFuzzyMatcher
225
226Q_DECLARE_TYPEINFO(KFuzzyMatcher::Range, Q_PRIMITIVE_TYPE);
227
228#endif // KFUZZYMATCHER_H
229

source code of kcoreaddons/src/lib/text/kfuzzymatcher.h