blender::string_search Namespace Reference

Namespaces
	tests

Functions
static int64_t	count_utf8_code_points (StringRef str)
int	damerau_levenshtein_distance (StringRef a, StringRef b)
int	get_fuzzy_match_errors (StringRef query, StringRef full)
static bool	match_word_initials (StringRef query, Span< StringRef > words, Span< bool > word_is_usable, MutableSpan< bool > r_word_is_matched, int start=0)
static int	get_shortest_word_index_that_startswith (StringRef query, Span< StringRef > words, Span< bool > word_is_usable)
static int	get_word_index_that_fuzzy_matches (StringRef query, Span< StringRef > words, Span< bool > word_is_usable, int *r_error_count)
static int	score_query_against_words (Span< StringRef > query_words, Span< StringRef > result_words)
void	extract_normalized_words (StringRef str, LinearAllocator<> &allocator, Vector< StringRef, 64 > &r_words)

Function Documentation

count_utf8_code_points()

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

static

Definition at line 29 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 42 of file string_search.cc.

References Freestyle::a, BLI_str_utf8_as_unicode_and_size(), count_utf8_code_points(), blender::Array< T, InlineBufferCapacity, Allocator >::data(), blender::StringRefBase::data(), min, v1, 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
	)

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 349 of file string_search.cc.

References blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_str_tolower_ascii(), BLI_str_utf8_as_unicode(), BLI_str_utf8_as_unicode_and_size(), blender::LinearAllocator< Allocator >::copy_string(), blender::StringRefBase::data(), blender::StringRef::drop_prefix(), ELEM, size(), str, and blender::StringRefBase::substr().

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

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 109 of file string_search.cc.

References blender::StringRefBase::begin(), BLI_assert, BLI_str_utf8_as_unicode(), BLI_str_utf8_size(), count_utf8_code_points(), damerau_levenshtein_distance(), distance(), ELEM, blender::StringRefBase::end(), blender::StringRefBase::find(), max, min, blender::StringRefBase::not_found, and query.

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

get_shortest_word_index_that_startswith()

static int blender::string_search::get_shortest_word_index_that_startswith ( StringRef  query, Span< StringRef >  words, Span< bool >  word_is_usable  )

static

Definition at line 248 of file string_search.cc.

References blender::Span< T >::index_range(), INT32_MAX, query, blender::StringRefBase::size(), and blender::StringRefBase::startswith().

Referenced by score_query_against_words().

get_word_index_that_fuzzy_matches()

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

static

Definition at line 269 of file string_search.cc.

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

Referenced by score_query_against_words().

match_word_initials()

static bool blender::string_search::match_word_initials ( StringRef  query, Span< StringRef >  words, Span< bool >  word_is_usable, MutableSpan< bool >  r_word_is_matched, 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".

Returns

true when the match was successful. If it was successful, the used words are tagged in r_word_is_matched.

Definition at line 186 of file string_search.cc.

References BLI_assert, BLI_str_utf8_as_unicode_and_size(), blender::StringRefBase::data(), blender::MutableSpan< T >::fill(), query, blender::Span< T >::size(), and blender::StringRefBase::size().

Referenced by score_query_against_words().

score_query_against_words()

static int blender::string_search::score_query_against_words ( Span< StringRef >  query_words, Span< StringRef >  result_words  )

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 292 of file string_search.cc.

References get_shortest_word_index_that_startswith(), get_word_index_that_fuzzy_matches(), blender::Span< T >::index_range(), match_word_initials(), and blender::Span< T >::size().

Referenced by BLI_string_search_query().