Blender  V3.3
string_search.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include "BLI_array.hh"
5 #include "BLI_multi_value_map.hh"
6 #include "BLI_span.hh"
7 #include "BLI_string.h"
8 #include "BLI_string_ref.hh"
9 #include "BLI_string_search.h"
10 #include "BLI_string_utf8.h"
11 #include "BLI_timeit.hh"
12 
13 /* Right arrow, keep in sync with #UI_MENU_ARROW_SEP in `UI_interface.h`. */
14 #define UI_MENU_ARROW_SEP "\xe2\x96\xb6"
15 #define UI_MENU_ARROW_SEP_UNICODE 0x25b6
16 
18 
20 {
21  return static_cast<int64_t>(BLI_strnlen_utf8(str.data(), static_cast<size_t>(str.size())));
22 }
23 
25 {
26  constexpr int deletion_cost = 1;
27  constexpr int insertion_cost = 1;
28  constexpr int substitution_cost = 1;
29  constexpr int transposition_cost = 1;
30 
31  const int size_a = count_utf8_code_points(a);
32  const int size_b = count_utf8_code_points(b);
33 
34  /* Instead of keeping the entire table in memory, only keep three rows. The algorithm only
35  * accesses these rows and nothing older.
36  * All three rows are usually allocated on the stack. At most a single heap allocation is done,
37  * if the reserved stack space is too small. */
38  const int row_length = size_b + 1;
39  Array<int, 64> rows(row_length * 3);
40 
41  /* Store rows as spans so that it is cheap to swap them. */
42  MutableSpan v0{rows.data() + row_length * 0, row_length};
43  MutableSpan v1{rows.data() + row_length * 1, row_length};
44  MutableSpan v2{rows.data() + row_length * 2, row_length};
45 
46  /* Only v1 needs to be initialized. */
47  for (const int i : IndexRange(row_length)) {
48  v1[i] = i * insertion_cost;
49  }
50 
51  uint32_t prev_unicode_a;
52  size_t offset_a = 0;
53  for (const int i : IndexRange(size_a)) {
54  v2[0] = (i + 1) * deletion_cost;
55 
56  const uint32_t unicode_a = BLI_str_utf8_as_unicode_step(a.data(), a.size(), &offset_a);
57 
58  uint32_t prev_unicode_b;
59  size_t offset_b = 0;
60  for (const int j : IndexRange(size_b)) {
61  const uint32_t unicode_b = BLI_str_utf8_as_unicode_step(b.data(), b.size(), &offset_b);
62 
63  /* Check how costly the different operations would be and pick the cheapest - the one with
64  * minimal cost. */
65  int new_cost = std::min({v1[j + 1] + deletion_cost,
66  v2[j] + insertion_cost,
67  v1[j] + (unicode_a != unicode_b) * substitution_cost});
68  if (i > 0 && j > 0) {
69  if (unicode_a == prev_unicode_b && prev_unicode_a == unicode_b) {
70  new_cost = std::min(new_cost, v0[j - 1] + transposition_cost);
71  }
72  }
73 
74  v2[j + 1] = new_cost;
75  prev_unicode_b = unicode_b;
76  }
77 
78  /* Swap the three rows, so that the next row can be computed. */
79  std::tie(v0, v1, v2) = std::tuple<MutableSpan<int>, MutableSpan<int>, MutableSpan<int>>(
80  v1, v2, v0);
81  prev_unicode_a = unicode_a;
82  }
83 
84  return v1.last();
85 }
86 
88 {
89  /* If it is a perfect partial match, return immediately. */
90  if (full.find(query) != StringRef::not_found) {
91  return 0;
92  }
93 
94  const int query_size = count_utf8_code_points(query);
95  const int full_size = count_utf8_code_points(full);
96 
97  /* If there is only a single character which is not in the full string, this is not a match. */
98  if (query_size == 1) {
99  return -1;
100  }
101  BLI_assert(query.size() >= 2);
102 
103  /* Allow more errors when the size grows larger. */
104  const int max_errors = query_size <= 1 ? 0 : query_size / 8 + 1;
105 
106  /* If the query is too large, this cannot be a match. */
107  if (query_size - full_size > max_errors) {
108  return -1;
109  }
110 
111  const uint32_t query_first_unicode = BLI_str_utf8_as_unicode(query.data());
112  const uint32_t query_second_unicode = BLI_str_utf8_as_unicode(query.data() +
113  BLI_str_utf8_size(query.data()));
114 
115  const char *full_begin = full.begin();
116  const char *full_end = full.end();
117 
118  const char *window_begin = full_begin;
119  const char *window_end = window_begin;
120  const int window_size = std::min(query_size + max_errors, full_size);
121  const int extra_chars = window_size - query_size;
122  const int max_acceptable_distance = max_errors + extra_chars;
123 
124  for (int i = 0; i < window_size; i++) {
125  window_end += BLI_str_utf8_size(window_end);
126  }
127 
128  while (true) {
129  StringRef window{window_begin, window_end};
130  const uint32_t window_begin_unicode = BLI_str_utf8_as_unicode(window_begin);
131  int distance = 0;
132  /* Expect that the first or second character of the query is correct. This helps to avoid
133  * computing the more expensive distance function. */
134  if (ELEM(window_begin_unicode, query_first_unicode, query_second_unicode)) {
136  if (distance <= max_acceptable_distance) {
137  return distance;
138  }
139  }
140  if (window_end == full_end) {
141  return -1;
142  }
143 
144  /* When the distance is way too large, we can skip a couple of code points, because the
145  * distance can't possibly become as short as required. */
146  const int window_offset = std::max(1, distance / 2);
147  for (int i = 0; i < window_offset && window_end < full_end; i++) {
148  window_begin += BLI_str_utf8_size(window_begin);
149  window_end += BLI_str_utf8_size(window_end);
150  }
151  }
152 }
153 
154 static constexpr int unused_word = -1;
155 
167  Span<StringRef> words,
168  Span<int> word_match_map,
169  MutableSpan<bool> r_word_is_matched,
170  int start = 0)
171 {
172  if (start >= words.size()) {
173  return false;
174  }
175 
176  r_word_is_matched.fill(false);
177 
178  size_t query_index = 0;
179  int word_index = start;
180  size_t char_index = 0;
181 
182  int first_found_word_index = -1;
183 
184  while (query_index < query.size()) {
185  const uint query_unicode = BLI_str_utf8_as_unicode_step(
186  query.data(), query.size(), &query_index);
187  while (true) {
188  /* We are at the end of words, no complete match has been found yet. */
189  if (word_index >= words.size()) {
190  if (first_found_word_index >= 0) {
191  /* Try starting to match at another word. In some cases one can still find matches this
192  * way. */
193  return match_word_initials(
194  query, words, word_match_map, r_word_is_matched, first_found_word_index + 1);
195  }
196  return false;
197  }
198 
199  /* Skip words that the caller does not want us to use. */
200  if (word_match_map[word_index] != unused_word) {
201  word_index++;
202  BLI_assert(char_index == 0);
203  continue;
204  }
205 
206  StringRef word = words[word_index];
207  /* Try to match the current character with the current word. */
208  if (static_cast<int>(char_index) < word.size()) {
209  const uint32_t char_unicode = BLI_str_utf8_as_unicode_step(
210  word.data(), word.size(), &char_index);
211  if (query_unicode == char_unicode) {
212  r_word_is_matched[word_index] = true;
213  if (first_found_word_index == -1) {
214  first_found_word_index = word_index;
215  }
216  break;
217  }
218  }
219 
220  /* Could not find a match in the current word, go to the beginning of the next word. */
221  word_index += 1;
222  char_index = 0;
223  }
224  }
225  return true;
226 }
227 
229  Span<StringRef> words,
230  Span<int> word_match_map)
231 {
232  int best_word_size = INT32_MAX;
233  int best_word_index = -1;
234  for (const int i : words.index_range()) {
235  if (word_match_map[i] != unused_word) {
236  continue;
237  }
238  StringRef word = words[i];
239  if (word.startswith(query)) {
240  if (word.size() < best_word_size) {
241  best_word_index = i;
242  best_word_size = word.size();
243  }
244  }
245  }
246  return best_word_index;
247 }
248 
250  Span<StringRef> words,
251  Span<int> word_match_map,
252  int *r_error_count)
253 {
254  for (const int i : words.index_range()) {
255  if (word_match_map[i] != unused_word) {
256  continue;
257  }
258  StringRef word = words[i];
259  const int error_count = get_fuzzy_match_errors(query, word);
260  if (error_count >= 0) {
261  *r_error_count = error_count;
262  return i;
263  }
264  }
265  return -1;
266 }
267 
272 static int score_query_against_words(Span<StringRef> query_words, Span<StringRef> result_words)
273 {
274  /* A mapping from #result_words to #query_words. It's mainly used to determine if a word has been
275  * matched already to avoid matching it again. */
276  Array<int, 64> word_match_map(result_words.size(), unused_word);
277 
278  /* Start with some high score, because otherwise the final score might become negative. */
279  int total_match_score = 1000;
280 
281  for (const int query_word_index : query_words.index_range()) {
282  const StringRef query_word = query_words[query_word_index];
283  {
284  /* Check if any result word begins with the query word. */
285  const int word_index = get_shortest_word_index_that_startswith(
286  query_word, result_words, word_match_map);
287  if (word_index >= 0) {
288  total_match_score += 10;
289  word_match_map[word_index] = query_word_index;
290  continue;
291  }
292  }
293  {
294  /* Try to match against word initials. */
295  Array<bool, 64> matched_words(result_words.size());
296  const bool success = match_word_initials(
297  query_word, result_words, word_match_map, matched_words);
298  if (success) {
299  total_match_score += 3;
300  for (const int i : result_words.index_range()) {
301  if (matched_words[i]) {
302  word_match_map[i] = query_word_index;
303  }
304  }
305  continue;
306  }
307  }
308  {
309  /* Fuzzy match against words. */
310  int error_count = 0;
311  const int word_index = get_word_index_that_fuzzy_matches(
312  query_word, result_words, word_match_map, &error_count);
313  if (word_index >= 0) {
314  total_match_score += 3 - error_count;
315  word_match_map[word_index] = query_word_index;
316  continue;
317  }
318  }
319 
320  /* Couldn't match query word with anything. */
321  return -1;
322  }
323 
324  {
325  /* Add penalty when query words are not in the correct order. */
326  Vector<int> match_indices;
327  for (const int index : word_match_map) {
328  if (index != unused_word) {
329  match_indices.append(index);
330  }
331  }
332  if (!match_indices.is_empty()) {
333  for (const int i : IndexRange(match_indices.size() - 1)) {
334  if (match_indices[i] > match_indices[i + 1]) {
335  total_match_score -= 1;
336  }
337  }
338  }
339  }
340 
341  return total_match_score;
342 }
343 
345  LinearAllocator<> &allocator,
346  Vector<StringRef, 64> &r_words)
347 {
348  const uint32_t unicode_space = (uint32_t)' ';
349  const uint32_t unicode_right_triangle = UI_MENU_ARROW_SEP_UNICODE;
350 
351  BLI_assert(unicode_space == BLI_str_utf8_as_unicode(" "));
352  BLI_assert(unicode_right_triangle == BLI_str_utf8_as_unicode(UI_MENU_ARROW_SEP));
353 
354  auto is_separator = [&](uint32_t unicode) {
355  return ELEM(unicode, unicode_space, unicode_right_triangle);
356  };
357 
358  /* Make a copy of the string so that we can edit it. */
359  StringRef str_copy = allocator.copy_string(str);
360  char *mutable_copy = const_cast<char *>(str_copy.data());
361  const size_t str_size_in_bytes = static_cast<size_t>(str.size());
362  BLI_str_tolower_ascii(mutable_copy, str_size_in_bytes);
363 
364  /* Iterate over all unicode code points to split individual words. */
365  bool is_in_word = false;
366  size_t word_start = 0;
367  size_t offset = 0;
368  while (offset < str_size_in_bytes) {
369  size_t size = offset;
370  uint32_t unicode = BLI_str_utf8_as_unicode_step(str.data(), str.size(), &size);
371  size -= offset;
372  if (is_separator(unicode)) {
373  if (is_in_word) {
374  r_words.append(
375  str_copy.substr(static_cast<int>(word_start), static_cast<int>(offset - word_start)));
376  is_in_word = false;
377  }
378  }
379  else {
380  if (!is_in_word) {
381  word_start = offset;
382  is_in_word = true;
383  }
384  }
385  offset += size;
386  }
387  /* If the last word is not followed by a separator, it has to be handled separately. */
388  if (is_in_word) {
389  r_words.append(str_copy.drop_prefix(static_cast<int>(word_start)));
390  }
391 }
392 
393 } // namespace blender::string_search
394 
395 struct SearchItem {
397  int length;
398  void *user_data;
399  int weight;
400 };
401 
402 struct StringSearch {
405 };
406 
408 {
409  return new StringSearch();
410 }
411 
413  const char *str,
414  void *user_data,
415  const int weight)
416 {
417  using namespace blender;
418  Vector<StringRef, 64> words;
419  StringRef str_ref{str};
420  string_search::extract_normalized_words(str_ref, search->allocator, words);
421  search->items.append({search->allocator.construct_array_copy(words.as_span()),
422  (int)str_ref.size(),
423  user_data,
424  weight});
425 }
426 
427 int BLI_string_search_query(StringSearch *search, const char *query, void ***r_data)
428 {
429  using namespace blender;
430 
431  const StringRef query_str = query;
432 
433  LinearAllocator<> allocator;
434  Vector<StringRef, 64> query_words;
435  string_search::extract_normalized_words(query_str, allocator, query_words);
436 
437  /* Compute score of every result. */
438  MultiValueMap<int, int> result_indices_by_score;
439  for (const int result_index : search->items.index_range()) {
441  query_words, search->items[result_index].normalized_words);
442  if (score >= 0) {
443  result_indices_by_score.add(score, result_index);
444  }
445  }
446 
447  Vector<int> found_scores;
448  for (const int score : result_indices_by_score.keys()) {
449  found_scores.append(score);
450  }
451  std::sort(found_scores.begin(), found_scores.end(), std::greater<>());
452 
453  /* Add results to output vector in correct order. First come the results with the best match
454  * score. Results with the same score are in the order they have been added to the search. */
455  Vector<int> sorted_result_indices;
456  for (const int score : found_scores) {
457  MutableSpan<int> indices = result_indices_by_score.lookup(score);
458  if (score == found_scores[0] && !query_str.is_empty()) {
459  /* Sort items with best score by length. Shorter items are more likely the ones you are
460  * looking for. This also ensures that exact matches will be at the top, even if the query is
461  * a substring of another item. */
462  std::sort(indices.begin(), indices.end(), [&](int a, int b) {
463  return search->items[a].length < search->items[b].length;
464  });
465  /* Prefer items with larger weights. Use `stable_sort` so that if the weights are the same,
466  * the order won't be changed. */
467  std::stable_sort(indices.begin(), indices.end(), [&](int a, int b) {
468  return search->items[a].weight > search->items[b].weight;
469  });
470  }
471  sorted_result_indices.extend(indices);
472  }
473 
474  void **sorted_data = static_cast<void **>(
475  MEM_malloc_arrayN(static_cast<size_t>(sorted_result_indices.size()), sizeof(void *), AT));
476  for (const int i : sorted_result_indices.index_range()) {
477  const int result_index = sorted_result_indices[i];
478  SearchItem &item = search->items[result_index];
479  sorted_data[i] = item.user_data;
480  }
481 
482  *r_data = sorted_data;
483 
484  return sorted_result_indices.size();
485 }
486 
488 {
489  delete string_search;
490 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
void BLI_str_tolower_ascii(char *str, size_t len) ATTR_NONNULL()
Definition: string.c:927
struct StringSearch StringSearch
int BLI_str_utf8_size(const char *p) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: string_utf8.c:452
unsigned int BLI_str_utf8_as_unicode(const char *p) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: string_utf8.c:478
size_t size_t BLI_strnlen_utf8(const char *strc, size_t maxlen) ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT
Definition: string_utf8.c:342
unsigned int BLI_str_utf8_as_unicode_step(const char *__restrict p, size_t p_len, size_t *__restrict index) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1
unsigned int uint
Definition: BLI_sys_types.h:67
#define ELEM(...)
#define AT
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum query
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
const T * data() const
Definition: BLI_array.hh:300
MutableSpan< T > construct_array_copy(Span< T > src)
StringRefNull copy_string(StringRef str)
MapType::KeyIterator keys() const
Span< Value > lookup(const Key &key) const
void add(const Key &key, const Value &value)
constexpr void fill(const T &value)
Definition: BLI_span.hh:527
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr IndexRange index_range() const
Definition: BLI_span.hh:401
static constexpr int64_t not_found
constexpr int64_t find(char c, int64_t pos=0) const
constexpr const char * begin() const
constexpr const char * end() const
constexpr bool is_empty() const
constexpr StringRef substr(int64_t start, int64_t size) const
constexpr bool startswith(StringRef prefix) const
constexpr int64_t size() const
constexpr const char * data() const
constexpr StringRef drop_prefix(int64_t n) const
int64_t size() const
Definition: BLI_vector.hh:694
void append(const T &value)
Definition: BLI_vector.hh:433
Span< T > as_span() const
Definition: BLI_vector.hh:325
bool is_empty() const
Definition: BLI_vector.hh:706
IndexRange index_range() const
Definition: BLI_vector.hh:920
void extend(Span< T > array)
Definition: BLI_vector.hh:530
void * user_data
#define str(s)
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
ccl_gpu_kernel_postfix int ccl_global int * indices
void *(* MEM_malloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:34
static unsigned a[3]
Definition: RandGen.cpp:78
T distance(const T &a, const T &b)
void extract_normalized_words(StringRef str, LinearAllocator<> &allocator, Vector< StringRef, 64 > &r_words)
static int64_t count_utf8_code_points(StringRef str)
static bool match_word_initials(StringRef query, Span< StringRef > words, Span< int > word_match_map, MutableSpan< bool > r_word_is_matched, int start=0)
static constexpr int unused_word
int get_fuzzy_match_errors(StringRef query, StringRef full)
static int score_query_against_words(Span< StringRef > query_words, Span< StringRef > result_words)
int damerau_levenshtein_distance(StringRef a, StringRef b)
static int get_word_index_that_fuzzy_matches(StringRef query, Span< StringRef > words, Span< int > word_match_map, int *r_error_count)
static int get_shortest_word_index_that_startswith(StringRef query, Span< StringRef > words, Span< int > word_match_map)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
#define min(a, b)
Definition: sort.c:35
#define INT32_MAX
Definition: stdint.h:137
unsigned int uint32_t
Definition: stdint.h:80
__int64 int64_t
Definition: stdint.h:89
#define UI_MENU_ARROW_SEP
void BLI_string_search_add(StringSearch *search, const char *str, void *user_data, const int weight)
StringSearch * BLI_string_search_new()
int BLI_string_search_query(StringSearch *search, const char *query, void ***r_data)
void BLI_string_search_free(StringSearch *string_search)
#define UI_MENU_ARROW_SEP_UNICODE
void * user_data
blender::Span< blender::StringRef > normalized_words
blender::Vector< SearchItem > items
blender::LinearAllocator allocator
float max