Fix T78084: Search does not accept text fragments everywhere

This was reported for the "Add Node" search functionality, but is
relevant in other searches as well.

So e.g. when searching for "Separate XYZ", typing "sep", then " " (with
the intention to type "X" next) would clear the search field. Now use
the same method (matching against all search words) as in F3 searching
('menu_search_update_fn') in other searches as well [searching IDs,
property objects, finding nodes,...]

This should give a much nicer search experience in general.

Note: this does not touch other searches in the Dopesheet, Outliner,
Filebrowser or User Preferences that have other search implementations.

Maniphest Tasks: T78084

Differential Revision: https://developer.blender.org/D8232

11 files changed, 93 insertions, 44 deletions

diff --git a/source/blender/blenlib/BLI_string.h b/source/blender/blenlib/BLI_string.h
index d1fab065959..4968b4ee159 100644
--- a/source/blender/blenlib/BLI_string.h
+++ b/source/blender/blenlib/BLI_string.h
@@ -133,6 +133,13 @@ size_t BLI_str_partition_ex(const char *str,
                             const char **suf,
                             const bool from_right) ATTR_NONNULL(1, 3, 4, 5);
 
+int BLI_string_max_possible_word_count(const int str_len);
+bool BLI_string_has_word_prefix(const char *haystack, const char *needle, size_t needle_len);
+bool BLI_string_all_words_matched(const char *name,
+                                  const char *str,
+                                  int (*words)[2],
+                                  const int words_len);
+
 int BLI_string_find_split_words(const char *str,
                                 const size_t len,
                                 const char delim,
diff --git a/source/blender/blenlib/intern/string.c b/source/blender/blenlib/intern/string.c
index 755637ac274..02d12d2df9b 100644
--- a/source/blender/blenlib/intern/string.c
+++ b/source/blender/blenlib/intern/string.c
@@ -524,6 +524,39 @@ char *BLI_strcasestr(const char *s, const char *find)
   return ((char *)s);
 }
 
+int BLI_string_max_possible_word_count(const int str_len)
+{
+  return (str_len / 2) + 1;
+}
+
+bool BLI_string_has_word_prefix(const char *haystack, const char *needle, size_t needle_len)
+{
+  const char *match = BLI_strncasestr(haystack, needle, needle_len);
+  if (match) {
+    if ((match == haystack) || (*(match - 1) == ' ') || ispunct(*(match - 1))) {
+      return true;
+    }
+    return BLI_string_has_word_prefix(match + 1, needle, needle_len);
+  }
+  return false;
+}
+
+bool BLI_string_all_words_matched(const char *name,
+                                  const char *str,
+                                  int (*words)[2],
+                                  const int words_len)
+{
+  int index;
+  for (index = 0; index < words_len; index++) {
+    if (!BLI_string_has_word_prefix(name, str + words[index][0], (size_t)words[index][1])) {
+      break;
+    }
+  }
+  const bool all_words_matched = (index == words_len);
+
+  return all_words_matched;
+}
+
 /**
  * Variation of #BLI_strcasestr with string length limited to \a len
  */
diff --git a/source/blender/blenlib/tests/BLI_string_test.cc b/source/blender/blenlib/tests/BLI_string_test.cc
index 1760b7966e3..a5fd3e31c31 100644
--- a/source/blender/blenlib/tests/BLI_string_test.cc
+++ b/source/blender/blenlib/tests/BLI_string_test.cc
@@ -570,6 +570,16 @@ TEST(string, StringStrncasestr)
   EXPECT_EQ(res, (void *)NULL);
 }
 
+/* BLI_string_max_possible_word_count */
+TEST(string, StringMaxPossibleWordCount)
+{
+  EXPECT_EQ(BLI_string_max_possible_word_count(0), 1);
+  EXPECT_EQ(BLI_string_max_possible_word_count(1), 1);
+  EXPECT_EQ(BLI_string_max_possible_word_count(2), 2);
+  EXPECT_EQ(BLI_string_max_possible_word_count(3), 2);
+  EXPECT_EQ(BLI_string_max_possible_word_count(10), 6);
+}
+
 /* BLI_string_is_decimal */
 TEST(string, StrIsDecimal)
 {
diff --git a/source/blender/editors/animation/anim_filter.c b/source/blender/editors/animation/anim_filter.c
index ddd389a5348..b75437fff45 100644
--- a/source/blender/editors/animation/anim_filter.c
+++ b/source/blender/editors/animation/anim_filter.c
@@ -1152,7 +1152,7 @@ static bool name_matches_dopesheet_filter(bDopeSheet *ads, char *name)
   if (ads->flag & ADS_FLAG_FUZZY_NAMES) {
     /* full fuzzy, multi-word, case insensitive matches */
     const size_t str_len = strlen(ads->searchstr);
-    const int words_max = (str_len / 2) + 1;
+    const int words_max = BLI_string_max_possible_word_count(str_len);
 
     int(*words)[2] = BLI_array_alloca(words, words_max);
     const int words_len = BLI_string_find_split_words(
diff --git a/source/blender/editors/interface/interface.c b/source/blender/editors/interface/interface.c
index bfa3f3a011c..d8330d62907 100644
--- a/source/blender/editors/interface/interface.c
+++ b/source/blender/editors/interface/interface.c
@@ -36,6 +36,7 @@
 #include "DNA_userdef_types.h"
 #include "DNA_workspace_types.h"
 
+#include "BLI_alloca.h"
 #include "BLI_listbase.h"
 #include "BLI_math.h"
 #include "BLI_rect.h"
@@ -6613,12 +6614,18 @@ static void operator_enum_search_update_fn(const struct bContext *C,
     const EnumPropertyItem *item, *item_array;
     bool do_free;
 
+    /* Prepare BLI_string_all_words_matched. */
+    const size_t str_len = strlen(str);
+    const int words_max = BLI_string_max_possible_word_count(str_len);
+    int(*words)[2] = BLI_array_alloca(words, words_max);
+    const int words_len = BLI_string_find_split_words(str, str_len, ' ', words, words_max);
+
     RNA_property_enum_items_gettexted((bContext *)C, ptr, prop, &item_array, NULL, &do_free);
 
     for (item = item_array; item->identifier; item++) {
       /* note: need to give the index rather than the
        * identifier because the enum can be freed */
-      if (BLI_strcasestr(item->name, str)) {
+      if (BLI_string_all_words_matched(item->name, str, words, words_len)) {
         if (!UI_search_item_add(
                 items, item->name, POINTER_FROM_INT(item->value), item->icon, 0, 0)) {
           break;
diff --git a/source/blender/editors/interface/interface_intern.h b/source/blender/editors/interface/interface_intern.h
index 87be3745f87..ec44d97c51b 100644
--- a/source/blender/editors/interface/interface_intern.h
+++ b/source/blender/editors/interface/interface_intern.h
@@ -1110,9 +1110,6 @@ void UI_OT_eyedropper_driver(struct wmOperatorType *ot);
 /* interface_eyedropper_gpencil_color.c */
 void UI_OT_eyedropper_gpencil_color(struct wmOperatorType *ot);
 
-/* interface_util.c */
-bool ui_str_has_word_prefix(const char *haystack, const char *needle, size_t needle_len);
-
 /**
  * For use with #ui_rna_collection_search_update_fn.
  */
diff --git a/source/blender/editors/interface/interface_template_search_menu.c b/source/blender/editors/interface/interface_template_search_menu.c
index d148ff70751..667dcfd935d 100644
--- a/source/blender/editors/interface/interface_template_search_menu.c
+++ b/source/blender/editors/interface/interface_template_search_menu.c
@@ -992,23 +992,15 @@ static void menu_search_update_fn(const bContext *UNUSED(C),
                                   uiSearchItems *items)
 {
   struct MenuSearch_Data *data = arg;
+
+  /* Prepare BLI_string_all_words_matched. */
   const size_t str_len = strlen(str);
-  const int words_max = (str_len / 2) + 1;
+  const int words_max = BLI_string_max_possible_word_count(str_len);
   int(*words)[2] = BLI_array_alloca(words, words_max);
-
   const int words_len = BLI_string_find_split_words(str, str_len, ' ', words, words_max);
 
   for (struct MenuSearch_Item *item = data->items.first; item; item = item->next) {
-    int index;
-
-    /* match name against all search words */
-    for (index = 0; index < words_len; index++) {
-      if (!ui_str_has_word_prefix(item->drawwstr_full, str + words[index][0], words[index][1])) {
-        break;
-      }
-    }
-
-    if (index == words_len) {
+    if (BLI_string_all_words_matched(item->drawwstr_full, str, words, words_len)) {
       if (!UI_search_item_add(items, item->drawwstr_full, item, item->icon, item->state, 0)) {
         break;
       }
diff --git a/source/blender/editors/interface/interface_template_search_operator.c b/source/blender/editors/interface/interface_template_search_operator.c
index 76a6abe22cb..21529a97c01 100644
--- a/source/blender/editors/interface/interface_template_search_operator.c
+++ b/source/blender/editors/interface/interface_template_search_operator.c
@@ -65,30 +65,23 @@ static void operator_search_update_fn(const bContext *C,
                                       uiSearchItems *items)
 {
   GHashIterator iter;
+
+  /* Prepare BLI_string_all_words_matched. */
   const size_t str_len = strlen(str);
-  const int words_max = (str_len / 2) + 1;
+  const int words_max = BLI_string_max_possible_word_count(str_len);
   int(*words)[2] = BLI_array_alloca(words, words_max);
-
   const int words_len = BLI_string_find_split_words(str, str_len, ' ', words, words_max);
 
   for (WM_operatortype_iter(&iter); !BLI_ghashIterator_done(&iter);
        BLI_ghashIterator_step(&iter)) {
     wmOperatorType *ot = BLI_ghashIterator_getValue(&iter);
     const char *ot_ui_name = CTX_IFACE_(ot->translation_context, ot->name);
-    int index;
 
     if ((ot->flag & OPTYPE_INTERNAL) && (G.debug & G_DEBUG_WM) == 0) {
       continue;
     }
 
-    /* match name against all search words */
-    for (index = 0; index < words_len; index++) {
-      if (!ui_str_has_word_prefix(ot_ui_name, str + words[index][0], words[index][1])) {
-        break;
-      }
-    }
-
-    if (index == words_len) {
+    if (BLI_string_all_words_matched(ot_ui_name, str, words, words_len)) {
       if (WM_operator_poll((bContext *)C, ot)) {
         char name[256];
         const int len = strlen(ot_ui_name);
diff --git a/source/blender/editors/interface/interface_templates.c b/source/blender/editors/interface/interface_templates.c
index f917b65be75..0440a1531c8 100644
--- a/source/blender/editors/interface/interface_templates.c
+++ b/source/blender/editors/interface/interface_templates.c
@@ -37,6 +37,7 @@
 #include "DNA_shader_fx_types.h"
 #include "DNA_texture_types.h"
 
+#include "BLI_alloca.h"
 #include "BLI_fnmatch.h"
 #include "BLI_listbase.h"
 #include "BLI_math.h"
@@ -356,7 +357,13 @@ static bool id_search_add(const bContext *C,
       }
     }
 
-    if (*str == '\0' || BLI_strcasestr(id->name + 2, str)) {
+    /* Prepare BLI_string_all_words_matched. */
+    const size_t str_len = strlen(str);
+    const int words_max = BLI_string_max_possible_word_count(str_len);
+    int(*words)[2] = BLI_array_alloca(words, words_max);
+    const int words_len = BLI_string_find_split_words(str, str_len, ' ', words, words_max);
+
+    if (*str == '\0' || BLI_string_all_words_matched(id->name + 2, str, words, words_len)) {
       /* +1 is needed because BKE_id_ui_prefix used 3 letter prefix
        * followed by ID_NAME-2 characters from id->name
        */
diff --git a/source/blender/editors/interface/interface_utils.c b/source/blender/editors/interface/interface_utils.c
index c413cac6023..690051ad735 100644
--- a/source/blender/editors/interface/interface_utils.c
+++ b/source/blender/editors/interface/interface_utils.c
@@ -30,6 +30,7 @@
 #include "DNA_object_types.h"
 #include "DNA_screen_types.h"
 
+#include "BLI_alloca.h"
 #include "BLI_listbase.h"
 #include "BLI_math.h"
 #include "BLI_string.h"
@@ -53,18 +54,6 @@
 
 #include "interface_intern.h"
 
-bool ui_str_has_word_prefix(const char *haystack, const char *needle, size_t needle_len)
-{
-  const char *match = BLI_strncasestr(haystack, needle, needle_len);
-  if (match) {
-    if ((match == haystack) || (*(match - 1) == ' ') || ispunct(*(match - 1))) {
-      return true;
-    }
-    return ui_str_has_word_prefix(match + 1, needle, needle_len);
-  }
-  return false;
-}
-
 /*************************** RNA Utilities ******************************/
 
 uiBut *uiDefAutoButR(uiBlock *block,
@@ -417,6 +406,12 @@ void ui_rna_collection_search_update_fn(const struct bContext *C,
   char *name;
   bool has_id_icon = false;
 
+  /* Prepare matching all words. */
+  const size_t str_len = strlen(str);
+  const int words_max = BLI_string_max_possible_word_count(str_len);
+  int(*words)[2] = BLI_array_alloca(words, words_max);
+  const int words_len = BLI_string_find_split_words(str, str_len, ' ', words, words_max);
+
   /* build a temporary list of relevant items first */
   RNA_PROP_BEGIN (&data->search_ptr, itemptr, data->search_prop) {
 
@@ -462,7 +457,8 @@ void ui_rna_collection_search_update_fn(const struct bContext *C,
     }
 
     if (name) {
-      if (skip_filter || BLI_strcasestr(name + name_prefix_offset, str)) {
+      if (skip_filter ||
+          BLI_string_all_words_matched(name + name_prefix_offset, str, words, words_len)) {
         cis = MEM_callocN(sizeof(CollItemSearch), "CollectionItemSearch");
         cis->data = itemptr.data;
         cis->name = BLI_strdup(name);
diff --git a/source/blender/editors/space_node/node_select.c b/source/blender/editors/space_node/node_select.c
index 90b824811d9..83ccfa65af3 100644
--- a/source/blender/editors/space_node/node_select.c
+++ b/source/blender/editors/space_node/node_select.c
@@ -26,6 +26,7 @@
 #include "DNA_node_types.h"
 #include "DNA_windowmanager_types.h"
 
+#include "BLI_alloca.h"
 #include "BLI_lasso_2d.h"
 #include "BLI_listbase.h"
 #include "BLI_math.h"
@@ -1171,9 +1172,15 @@ static void node_find_update_fn(const struct bContext *C,
   SpaceNode *snode = CTX_wm_space_node(C);
   bNode *node;
 
-  for (node = snode->edittree->nodes.first; node; node = node->next) {
+  /* Prepare BLI_string_all_words_matched. */
+  const size_t str_len = strlen(str);
+  const int words_max = BLI_string_max_possible_word_count(str_len);
+  int(*words)[2] = BLI_array_alloca(words, words_max);
+  const int words_len = BLI_string_find_split_words(str, str_len, ' ', words, words_max);
 
-    if (BLI_strcasestr(node->name, str) || BLI_strcasestr(node->label, str)) {
+  for (node = snode->edittree->nodes.first; node; node = node->next) {
+    if (BLI_string_all_words_matched(node->name, str, words, words_len) ||
+        BLI_string_all_words_matched(node->label, str, words, words_len)) {
       char name[256];
 
       if (node->label[0]) {