Page MenuHome
Paste P1642

Fuzzy Property Search
ActivePublic

Authored by Jacques Lucke (JacquesLucke) on Sep 17 2020, 6:17 PM.
diff --git a/source/blender/blenlib/BLI_string_search.h b/source/blender/blenlib/BLI_string_search.h
index 8057e5b75cb..dbe4f33d51a 100644
--- a/source/blender/blenlib/BLI_string_search.h
+++ b/source/blender/blenlib/BLI_string_search.h
@@ -21,12 +21,24 @@ extern "C" {
#endif
typedef struct StringSearch StringSearch;
+typedef struct StringMatcher StringMatcher;
+/**
+ * StringSearch handles filtering and sorting of multiple possible search results.
+ */
StringSearch *BLI_string_search_new(void);
void BLI_string_search_add(StringSearch *search, const char *str, void *user_data);
int BLI_string_search_query(StringSearch *search, const char *query, void ***r_data);
void BLI_string_search_free(StringSearch *search);
+/**
+ * A StringMatcher can be used to match against multiple strings separately.
+ */
+StringMatcher *BLI_string_matcher_new(const char *query);
+bool BLI_string_matcher_is_fuzzy_match(StringMatcher *matcher, const char *str);
+bool BLI_string_matcher_has_empty_query(StringMatcher *matcher);
+void BLI_string_matcher_free(StringMatcher *matcher);
+
#ifdef __cplusplus
}
#endif
diff --git a/source/blender/blenlib/intern/string_search.cc b/source/blender/blenlib/intern/string_search.cc
index d64587b85b4..582ba7929f7 100644
--- a/source/blender/blenlib/intern/string_search.cc
+++ b/source/blender/blenlib/intern/string_search.cc
@@ -473,3 +473,50 @@ void BLI_string_search_free(StringSearch *string_search)
{
delete string_search;
}
+
+struct StringMatcher {
+ blender::LinearAllocator<> allocator;
+ blender::Span<blender::StringRef> query_words;
+ std::string query;
+};
+
+StringMatcher *BLI_string_matcher_new(const char *query)
+{
+ using namespace blender;
+ StringMatcher *matcher = new StringMatcher();
+ if (query != nullptr) {
+ matcher->query = query;
+
+ /* Split query words. */
+ Vector<StringRef, 64> query_words;
+ string_search::extract_normalized_words(query, matcher->allocator, query_words);
+ matcher->query_words = matcher->allocator.construct_array_copy(query_words.as_span());
+ }
+ return matcher;
+}
+
+bool BLI_string_matcher_is_fuzzy_match(StringMatcher *matcher, const char *str)
+{
+ using namespace blender;
+
+ /* Use a linear allocator with a buffer on the stack to avoid allocations. */
+ LinearAllocator<> allocator;
+ AlignedBuffer<1024, 8> buffer;
+ allocator.provide_buffer(buffer);
+
+ Vector<StringRef, 64> result_words;
+ string_search::extract_normalized_words(str, allocator, result_words);
+
+ const int score = string_search::score_query_against_words(matcher->query_words, result_words);
+ return score >= 0;
+}
+
+bool BLI_string_matcher_has_empty_query(StringMatcher *matcher)
+{
+ return matcher->query.empty();
+}
+
+void BLI_string_matcher_free(StringMatcher *matcher)
+{
+ delete matcher;
+}
diff --git a/source/blender/editors/include/UI_interface.h b/source/blender/editors/include/UI_interface.h
index 7628d8a37c6..b0682dfd90e 100644
--- a/source/blender/editors/include/UI_interface.h
+++ b/source/blender/editors/include/UI_interface.h
@@ -57,6 +57,7 @@ struct bNodeSocket;
struct bNodeTree;
struct bScreen;
struct rcti;
+struct StringMatcher;
struct uiButSearch;
struct uiFontStyle;
struct uiList;
@@ -676,7 +677,6 @@ char UI_block_emboss_get(uiBlock *block);
void UI_block_emboss_set(uiBlock *block, char emboss);
bool UI_block_is_search_only(const uiBlock *block);
void UI_block_set_search_only(uiBlock *block, bool search_only);
-void UI_block_set_search_filter(uiBlock *block, const char *search_filter);
void UI_block_free(const struct bContext *C, uiBlock *block);
void UI_blocklist_free(const struct bContext *C, struct ListBase *lb);
@@ -1870,7 +1870,7 @@ uiLayout *UI_block_layout(uiBlock *block,
void UI_block_layout_set_current(uiBlock *block, uiLayout *layout);
void UI_block_layout_resolve(uiBlock *block, int *r_x, int *r_y);
-bool UI_block_apply_search_filter(uiBlock *block);
+bool UI_block_apply_search_filter(uiBlock *block, struct StringMatcher *search_matcher);
void UI_region_message_subscribe(struct ARegion *region, struct wmMsgBus *mbus);
diff --git a/source/blender/editors/interface/interface.c b/source/blender/editors/interface/interface.c
index 11c7f68ae55..56c52b1a9d5 100644
--- a/source/blender/editors/interface/interface.c
+++ b/source/blender/editors/interface/interface.c
@@ -3559,11 +3559,6 @@ void UI_block_set_search_only(uiBlock *block, bool search_only)
SET_FLAG_FROM_TEST(block->flag, search_only, UI_BLOCK_SEARCH_ONLY);
}
-void UI_block_set_search_filter(uiBlock *block, const char *search_filter)
-{
- block->search_filter = search_filter;
-}
-
static void ui_but_build_drawstr_float(uiBut *but, double value)
{
size_t slen = 0;
diff --git a/source/blender/editors/interface/interface_intern.h b/source/blender/editors/interface/interface_intern.h
index d62b8a0258a..2f8e8109da8 100644
--- a/source/blender/editors/interface/interface_intern.h
+++ b/source/blender/editors/interface/interface_intern.h
@@ -522,12 +522,6 @@ struct uiBlock {
*/
char display_device[64];
- /**
- * Pointer to the space's property search string.
- * The block doesn't allocate this or change it.
- */
- const char *search_filter;
-
struct PieMenuData pie_data;
};
diff --git a/source/blender/editors/interface/interface_layout.c b/source/blender/editors/interface/interface_layout.c
index 704246621fb..fb77aa9578a 100644
--- a/source/blender/editors/interface/interface_layout.c
+++ b/source/blender/editors/interface/interface_layout.c
@@ -36,6 +36,7 @@
#include "BLI_math.h"
#include "BLI_rect.h"
#include "BLI_string.h"
+#include "BLI_string_search.h"
#include "BLI_utildefines.h"
#include "BLT_translation.h"
@@ -5161,10 +5162,10 @@ void uiLayoutRootSetSearchOnly(uiLayout *layout, bool search_only)
/* Disabled for performance reasons, but this could be turned on in the future. */
// #define PROPERTY_SEARCH_USE_TOOLTIPS
-static bool block_search_panel_label_matches(const uiBlock *block)
+static bool block_search_panel_label_matches(const uiBlock *block, StringMatcher *search_matcher)
{
if ((block->panel != NULL) && (block->panel->type != NULL)) {
- if (BLI_strcasestr(block->panel->type->label, block->search_filter)) {
+ if (BLI_string_matcher_is_fuzzy_match(search_matcher, block->panel->type->label)) {
return true;
}
}
@@ -5213,25 +5214,26 @@ static void block_search_remove_search_only_roots(uiBlock *block)
/**
* Returns true if a button or the data / operator it represents matches the search filter.
*/
-static bool button_matches_search_filter(uiBut *but, const char *search_filter)
+static bool button_matches_search_filter(uiBut *but, StringMatcher *search_matcher)
{
/* Do the shorter checks first for better performance in case there is a match. */
- if (BLI_strcasestr(but->str, search_filter)) {
+ if (BLI_string_matcher_is_fuzzy_match(search_matcher, but->str)) {
return true;
}
if (but->optype != NULL) {
- if (BLI_strcasestr(but->optype->name, search_filter)) {
+ if (BLI_string_matcher_is_fuzzy_match(search_matcher, but->optype->name)) {
return true;
}
}
if (but->rnaprop != NULL) {
- if (BLI_strcasestr(RNA_property_ui_name(but->rnaprop), search_filter)) {
+ if (BLI_string_matcher_is_fuzzy_match(search_matcher, RNA_property_ui_name(but->rnaprop))) {
return true;
}
#ifdef PROPERTY_SEARCH_USE_TOOLTIPS
- if (BLI_strcasestr(RNA_property_description(but->rnaprop), search_filter)) {
+ if (BLI_string_matcher_is_fuzzy_match(search_matcher,
+ RNA_property_description(but->rnaprop))) {
return true;
}
#endif
@@ -5257,7 +5259,7 @@ static bool button_matches_search_filter(uiBut *but, const char *search_filter)
if (items_array[i].name == NULL) {
continue;
}
- if (BLI_strcasestr(items_array[i].name, search_filter)) {
+ if (BLI_string_matcher_is_fuzzy_match(search_matcher, items_array[i].name)) {
return true;
}
}
@@ -5273,11 +5275,12 @@ static bool button_matches_search_filter(uiBut *but, const char *search_filter)
/**
* Test for a search result within a specific button group.
*/
-static bool button_group_has_search_match(uiButtonGroup *button_group, const char *search_filter)
+static bool button_group_has_search_match(uiButtonGroup *button_group,
+ StringMatcher *search_matcher)
{
LISTBASE_FOREACH (LinkData *, link, &button_group->buttons) {
uiBut *but = link->data;
- if (button_matches_search_filter(but, search_filter)) {
+ if (button_matches_search_filter(but, search_matcher)) {
return true;
}
}
@@ -5294,12 +5297,12 @@ static bool button_group_has_search_match(uiButtonGroup *button_group, const cha
*
* \return True if the block has any search results.
*/
-static bool block_search_filter_tag_buttons(uiBlock *block)
+static bool block_search_filter_tag_buttons(uiBlock *block, StringMatcher *search_matcher)
{
bool has_result = false;
LISTBASE_FOREACH (uiLayoutRoot *, root, &block->layouts) {
LISTBASE_FOREACH (uiButtonGroup *, button_group, &root->button_groups) {
- if (button_group_has_search_match(button_group, block->search_filter)) {
+ if (button_group_has_search_match(button_group, search_matcher)) {
LISTBASE_FOREACH (LinkData *, link, &button_group->buttons) {
uiBut *but = link->data;
but->flag |= UI_SEARCH_FILTER_MATCHES;
@@ -5325,15 +5328,17 @@ static void block_search_deactivate_buttons(uiBlock *block)
*
* \note Must not be run after #UI_block_layout_resolve.
*/
-bool UI_block_apply_search_filter(uiBlock *block)
+bool UI_block_apply_search_filter(uiBlock *block, StringMatcher *search_matcher)
{
- if (!(block->search_filter && block->search_filter[0])) {
+ if (search_matcher == NULL || BLI_string_matcher_has_empty_query(search_matcher)) {
return false;
}
- const bool panel_label_matches = block_search_panel_label_matches(block);
+ const bool panel_label_matches = block_search_panel_label_matches(block, search_matcher);
- const bool has_result = panel_label_matches ? true : block_search_filter_tag_buttons(block);
+ const bool has_result = panel_label_matches ?
+ true :
+ block_search_filter_tag_buttons(block, search_matcher);
block_search_remove_search_only_roots(block);
diff --git a/source/blender/editors/screen/area.c b/source/blender/editors/screen/area.c
index f06633c1c92..96dc73919dd 100644
--- a/source/blender/editors/screen/area.c
+++ b/source/blender/editors/screen/area.c
@@ -32,6 +32,7 @@
#include "BLI_linklist_stack.h"
#include "BLI_math.h"
#include "BLI_rand.h"
+#include "BLI_string_search.h"
#include "BLI_utildefines.h"
#include "BKE_context.h"
@@ -2593,7 +2594,7 @@ static void ed_panel_draw(const bContext *C,
int w,
int em,
char *unique_panel_str,
- const char *search_filter,
+ StringMatcher *search_matcher,
bool search_only)
{
const uiStyle *style = UI_style_get_dpi();
@@ -2607,13 +2608,13 @@ static void ed_panel_draw(const bContext *C,
strncat(block_name, unique_panel_str, INSTANCED_PANEL_UNIQUE_STR_LEN);
}
uiBlock *block = UI_block_begin(C, region, block_name, UI_EMBOSS);
- UI_block_set_search_filter(block, search_filter);
UI_block_set_search_only(block, search_only);
bool open;
panel = UI_panel_begin(region, lb, block, pt, panel, &open);
- const bool search_filter_active = search_filter != NULL && search_filter[0] != '\0';
+ const bool search_filter_active = search_matcher != NULL &&
+ !BLI_string_matcher_has_empty_query(search_matcher);
/* bad fixed values */
int xco, yco, h = 0;
@@ -2634,7 +2635,7 @@ static void ed_panel_draw(const bContext *C,
pt->draw_header_preset(C, panel);
- UI_block_apply_search_filter(block);
+ UI_block_apply_search_filter(block, search_matcher);
UI_block_layout_resolve(block, &xco, &yco);
UI_block_translate(block, headerend - xco, 0);
panel->layout = NULL;
@@ -2666,7 +2667,7 @@ static void ed_panel_draw(const bContext *C,
pt->draw_header(C, panel);
- UI_block_apply_search_filter(block);
+ UI_block_apply_search_filter(block, search_matcher);
UI_block_layout_resolve(block, &xco, &yco);
panel->labelofs = xco - labelx;
panel->layout = NULL;
@@ -2703,7 +2704,7 @@ static void ed_panel_draw(const bContext *C,
pt->draw(C, panel);
- UI_block_apply_search_filter(block);
+ UI_block_apply_search_filter(block, search_matcher);
UI_block_layout_resolve(block, &xco, &yco);
panel->layout = NULL;
@@ -2729,7 +2730,7 @@ static void ed_panel_draw(const bContext *C,
w,
em,
unique_panel_str,
- search_filter,
+ search_matcher,
!open);
}
}
@@ -2871,7 +2872,11 @@ void ED_region_panels_layout_ex(const bContext *C,
UI_panels_begin(C, region);
/* Get search string for property search. */
+ StringMatcher *search_matcher = NULL;
const char *search_filter = ED_area_region_search_filter_get(area, region);
+ if (search_filter != NULL) {
+ search_matcher = BLI_string_matcher_new(search_filter);
+ }
/* set view2d view matrix - UI_block_begin() stores it */
UI_view2d_view_ortho(v2d);
@@ -2905,7 +2910,7 @@ void ED_region_panels_layout_ex(const bContext *C,
(pt->flag & PNL_DRAW_BOX) ? w_box_panel : w,
em,
NULL,
- search_filter,
+ search_matcher,
false);
}
@@ -2940,11 +2945,15 @@ void ED_region_panels_layout_ex(const bContext *C,
(panel->type->flag & PNL_DRAW_BOX) ? w_box_panel : w,
em,
unique_panel_str,
- search_filter,
+ search_matcher,
false);
}
}
+ if (search_matcher != NULL) {
+ BLI_string_matcher_free(search_matcher);
+ }
+
/* align panels and return size */
UI_panels_end(C, region, &x, &y);