blender::string_search Namespace Reference

Namespaces
namespace	tests

Classes
struct	InitialsMatch
struct	RecentCache
struct	SearchItem
class	StringSearch
class	StringSearchBase

Enumerations
enum class	MainWordsHeuristic { FirstGroup , LastGroup , All }

Functions
int	damerau_levenshtein_distance (StringRef a, StringRef b)
int	get_fuzzy_match_errors (StringRef query, StringRef full)
void	extract_normalized_words (StringRef str, LinearAllocator<> &allocator, Vector< StringRef, 64 > &r_words, Vector< int, 64 > &r_word_group_ids)
static int64_t	count_utf8_code_points (StringRef str)
static std::optional< InitialsMatch >	match_word_initials (StringRef query, const SearchItem &item, const Span< int > word_match_map, int start=0)
static int	get_best_word_index_that_startswith (StringRef query, const SearchItem &item, Span< int > word_match_map, Span< StringRef > remaining_query_words)
static int	get_word_index_that_fuzzy_matches (StringRef query, Span< StringRef > words, Span< int > word_match_map, int *r_error_count)
static std::optional< float >	score_query_against_words (Span< StringRef > query_words, const SearchItem &item)

Variables
static constexpr int	unused_word = -1

Enumeration Type Documentation

MainWordsHeuristic

enum class blender::string_search::MainWordsHeuristic

strong

Sometimes every search item has multiple parts. For example, when using menu search, each nested menu is a separate part. Usually, one of those parts is highlighted in the UI and should be prioritized in the search.

Enumerator
FirstGroup
LastGroup
All

Definition at line 56 of file BLI_string_search.hh.

Function Documentation

count_utf8_code_points()

static int64_t blender::string_search::count_utf8_code_points ( StringRef str )

static

Definition at line 22 of file string_search.cc.

References BLI_strnlen_utf8(), and str.

Referenced by damerau_levenshtein_distance(), and get_fuzzy_match_errors().

damerau_levenshtein_distance()

int blender::string_search::damerau_levenshtein_distance	(	StringRef	a,
		StringRef	b )

Computes the cost of transforming string a into b. The cost/distance is the minimal number of operations that need to be executed. Valid operations are deletion, insertion, substitution and transposition.

This function is utf8 aware in the sense that it works at the level of individual code points (1-4 bytes long) instead of on individual bytes.

Definition at line 27 of file string_search.cc.

References b, BLI_str_utf8_as_unicode_step_safe(), count_utf8_code_points(), blender::Array< T, InlineBufferCapacity, Allocator >::data(), blender::MutableSpan< T >::last(), and v2.

Referenced by get_fuzzy_match_errors(), and blender::string_search::tests::TEST().

extract_normalized_words()

void blender::string_search::extract_normalized_words	(	StringRef	str,
		LinearAllocator<> &	allocator,
		Vector< StringRef, 64 > &	r_words,
		Vector< int, 64 > &	r_word_group_ids )

Splits a string into words and normalizes them (currently that just means converting to lower case). The returned strings are allocated in the given allocator.

Definition at line 412 of file string_search.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, BLI_str_tolower_ascii(), BLI_str_utf8_as_unicode_safe(), BLI_str_utf8_as_unicode_step_safe(), blender::LinearAllocator< Allocator >::copy_string(), blender::StringRefBase::data(), blender::StringRef::drop_prefix(), ELEM, size(), str, blender::StringRefBase::substr(), UI_MENU_ARROW_SEP, and UI_MENU_ARROW_SEP_UNICODE.

Referenced by blender::string_search::StringSearchBase::add_impl(), blender::string_search::StringSearchBase::query_impl(), and blender::string_search::tests::TEST().

get_best_word_index_that_startswith()

static int blender::string_search::get_best_word_index_that_startswith ( StringRef query, const SearchItem & item, Span< int > word_match_map, Span< StringRef > remaining_query_words )

static

The "best" is chosen with combination of word weights and word length.

Definition at line 258 of file string_search.cc.

References INT32_MAX, blender::string_search::SearchItem::main_group_id, blender::string_search::SearchItem::normalized_words, blender::StringRefBase::size(), blender::StringRefBase::startswith(), unused_word, and blender::string_search::SearchItem::word_group_ids.

Referenced by score_query_against_words().

get_fuzzy_match_errors()

int blender::string_search::get_fuzzy_match_errors	(	StringRef	query,
		StringRef	full )

Returns -1 when this is no reasonably good match. Otherwise returns the number of errors in the match.

Definition at line 90 of file string_search.cc.

References BLI_assert, BLI_str_utf8_as_unicode_safe(), BLI_str_utf8_size_safe(), count_utf8_code_points(), damerau_levenshtein_distance(), blender::StringRefBase::data(), distance(), ELEM, blender::StringRefBase::not_found, and blender::StringRefBase::size().

Referenced by get_word_index_that_fuzzy_matches(), and blender::string_search::tests::TEST().

get_word_index_that_fuzzy_matches()

static int blender::string_search::get_word_index_that_fuzzy_matches ( StringRef query, Span< StringRef > words, Span< int > word_match_map, int * r_error_count )

static

Definition at line 314 of file string_search.cc.

References get_fuzzy_match_errors(), blender::Span< T >::index_range(), and unused_word.

Referenced by score_query_against_words().

match_word_initials()

static std::optional< InitialsMatch > blender::string_search::match_word_initials ( StringRef query, const SearchItem & item, const Span< int > word_match_map, int start = 0 )

static

Takes a query and tries to match it with the first characters of some words. For example, "msfv" matches "Mark Sharp from Vertices". Multiple letters of the beginning of a word can be matched as well. For example, "seboulo" matches "select boundary loop". The order of words is important. So "bose" does not match "select boundary". However, individual words can be skipped. For example, "rocc" matches "rotate edge ccw".

Definition at line 186 of file string_search.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, BLI_str_utf8_as_unicode_step_safe(), blender::StringRefBase::data(), match_word_initials(), blender::string_search::InitialsMatch::matched_word_indices, blender::string_search::SearchItem::normalized_words, blender::Span< T >::size(), blender::StringRefBase::size(), and unused_word.

Referenced by match_word_initials(), and score_query_against_words().

score_query_against_words()

static std::optional< float > blender::string_search::score_query_against_words ( Span< StringRef > query_words, const SearchItem & item )

static

Checks how well the query matches a result. If it does not match, -1 is returned. A positive return value indicates how good the match is. The higher the value, the better the match.

Definition at line 337 of file string_search.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), blender::Span< T >::drop_front(), get_best_word_index_that_startswith(), get_word_index_that_fuzzy_matches(), blender::Span< T >::index_range(), blender::string_search::SearchItem::is_deprecated, blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::string_search::SearchItem::main_group_id, match_word_initials(), blender::string_search::SearchItem::normalized_words, blender::Array< T, InlineBufferCapacity, Allocator >::size(), blender::Vector< T, InlineBufferCapacity, Allocator >::size(), unused_word, and blender::string_search::SearchItem::word_group_ids.

Variable Documentation

unused_word

int blender::string_search::unused_word = -1

staticconstexpr

Definition at line 157 of file string_search.cc.

Referenced by get_best_word_index_that_startswith(), get_word_index_that_fuzzy_matches(), match_word_initials(), and score_query_against_words().