UI: improve search results by using fuzzy and prefix matching

Blender does string based searching in many different places.
This patch updates four of these places to use the new string
search api in `BLI_string_search.h`.

In the future we probably want to update the other searches as well.

Reviewers: Severin, pablovazquez

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

4 files changed, 141 insertions, 97 deletions

diff --git a/source/blender/editors/interface/interface.c b/source/blender/editors/interface/interface.c
index ea64fb9cfcd..ce9db09e340 100644
--- a/source/blender/editors/interface/interface.c
+++ b/source/blender/editors/interface/interface.c
@@ -41,6 +41,7 @@
 #include "BLI_math.h"
 #include "BLI_rect.h"
 #include "BLI_string.h"
+#include "BLI_string_search.h"
 #include "BLI_string_utf8.h"
 
 #include "BLI_utildefines.h"
@@ -6651,30 +6652,34 @@ static void operator_enum_search_update_fn(const struct bContext *C,
   }
   else {
     PointerRNA *ptr = UI_but_operator_ptr_get(but); /* Will create it if needed! */
-    const EnumPropertyItem *item, *item_array;
+
     bool do_free;
+    const EnumPropertyItem *all_items;
+    RNA_property_enum_items_gettexted((bContext *)C, ptr, prop, &all_items, NULL, &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);
+    StringSearch *search = BLI_string_search_new();
+    for (const EnumPropertyItem *item = all_items; item->identifier; item++) {
+      BLI_string_search_add(search, item->name, (void *)item);
+    }
 
-    RNA_property_enum_items_gettexted((bContext *)C, ptr, prop, &item_array, NULL, &do_free);
+    const EnumPropertyItem **filtered_items;
+    int filtered_amount = BLI_string_search_query(search, str, (void ***)&filtered_items);
 
-    for (item = item_array; item->identifier; item++) {
+    for (int i = 0; i < filtered_amount; i++) {
+      const EnumPropertyItem *item = filtered_items[i];
       /* note: need to give the index rather than the
        * identifier because the enum can be freed */
-      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;
-        }
+      if (!UI_search_item_add(
+              items, item->name, POINTER_FROM_INT(item->value), item->icon, 0, 0)) {
+        break;
       }
     }
 
+    MEM_freeN(filtered_items);
+    BLI_string_search_free(search);
+
     if (do_free) {
-      MEM_freeN((void *)item_array);
+      MEM_freeN((void *)all_items);
     }
   }
 }
diff --git a/source/blender/editors/interface/interface_template_search_menu.c b/source/blender/editors/interface/interface_template_search_menu.c
index 667dcfd935d..5bde51846a8 100644
--- a/source/blender/editors/interface/interface_template_search_menu.c
+++ b/source/blender/editors/interface/interface_template_search_menu.c
@@ -41,6 +41,7 @@
 #include "BLI_math_matrix.h"
 #include "BLI_memarena.h"
 #include "BLI_string.h"
+#include "BLI_string_search.h"
 #include "BLI_string_utils.h"
 #include "BLI_utildefines.h"
 
@@ -993,19 +994,24 @@ static void menu_search_update_fn(const bContext *UNUSED(C),
 {
   struct MenuSearch_Data *data = arg;
 
-  /* 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);
+  StringSearch *search = BLI_string_search_new();
 
-  for (struct MenuSearch_Item *item = data->items.first; item; item = item->next) {
-    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;
-      }
+  LISTBASE_FOREACH (struct MenuSearch_Item *, item, &data->items) {
+    BLI_string_search_add(search, item->drawwstr_full, item);
+  }
+
+  struct MenuSearch_Item **filtered_items;
+  int filtered_amount = BLI_string_search_query(search, str, (void ***)&filtered_items);
+
+  for (int i = 0; i < filtered_amount; i++) {
+    struct MenuSearch_Item *item = filtered_items[i];
+    if (!UI_search_item_add(items, item->drawwstr_full, item, item->icon, item->state, 0)) {
+      break;
     }
   }
+
+  MEM_freeN(filtered_items);
+  BLI_string_search_free(search);
 }
 
 /** \} */
diff --git a/source/blender/editors/interface/interface_templates.c b/source/blender/editors/interface/interface_templates.c
index 5fbd26a4f5a..671a7865c6a 100644
--- a/source/blender/editors/interface/interface_templates.c
+++ b/source/blender/editors/interface/interface_templates.c
@@ -44,6 +44,7 @@
 #include "BLI_path_util.h"
 #include "BLI_rect.h"
 #include "BLI_string.h"
+#include "BLI_string_search.h"
 #include "BLI_timecode.h"
 #include "BLI_utildefines.h"
 
@@ -330,67 +331,61 @@ static void template_ID_set_property_exec_fn(bContext *C, void *arg_template, vo
   }
 }
 
-static bool id_search_add(const bContext *C,
-                          TemplateID *template_ui,
-                          const int flag,
-                          const char *str,
-                          uiSearchItems *items,
-                          ID *id)
+static bool id_search_allows_id(TemplateID *template_ui, const int flag, ID *id, const char *query)
 {
   ID *id_from = template_ui->ptr.owner_id;
 
-  if (!((flag & PROP_ID_SELF_CHECK) && id == id_from)) {
+  /* Do self check. */
+  if ((flag & PROP_ID_SELF_CHECK) && id == id_from) {
+    return false;
+  }
 
-    /* use filter */
-    if (RNA_property_type(template_ui->prop) == PROP_POINTER) {
-      PointerRNA ptr;
-      RNA_id_pointer_create(id, &ptr);
-      if (RNA_property_pointer_poll(&template_ui->ptr, template_ui->prop, &ptr) == 0) {
-        return true;
-      }
+  /* Use filter. */
+  if (RNA_property_type(template_ui->prop) == PROP_POINTER) {
+    PointerRNA ptr;
+    RNA_id_pointer_create(id, &ptr);
+    if (RNA_property_pointer_poll(&template_ui->ptr, template_ui->prop, &ptr) == 0) {
+      return false;
     }
+  }
 
-    /* hide dot-datablocks, but only if filter does not force it visible */
-    if (U.uiflag & USER_HIDE_DOT) {
-      if ((id->name[2] == '.') && (str[0] != '.')) {
-        return true;
-      }
+  /* Hide dot-datablocks, but only if filter does not force them visible. */
+  if (U.uiflag & USER_HIDE_DOT) {
+    if ((id->name[2] == '.') && (query[0] != '.')) {
+      return false;
     }
+  }
 
-    /* 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
-       */
-      char name_ui[MAX_ID_FULL_NAME_UI];
-      int iconid = ui_id_icon_get(C, id, template_ui->preview);
-      const bool use_lib_prefix = template_ui->preview || iconid;
-      const bool has_sep_char = (id->lib != NULL);
-
-      /* When using previews, the library hint (linked, overridden, missing) is added with a
-       * character prefix, otherwise we can use a icon. */
-      int name_prefix_offset;
-      BKE_id_full_name_ui_prefix_get(
-          name_ui, id, use_lib_prefix, UI_SEP_CHAR, &name_prefix_offset);
-      if (!use_lib_prefix) {
-        iconid = UI_library_icon_get(id);
-      }
+  return true;
+}
 
-      if (!UI_search_item_add(items,
-                              name_ui,
-                              id,
-                              iconid,
-                              has_sep_char ? UI_BUT_HAS_SEP_CHAR : 0,
-                              name_prefix_offset)) {
-        return false;
-      }
-    }
+static bool id_search_add(const bContext *C, TemplateID *template_ui, uiSearchItems *items, ID *id)
+{
+  /* +1 is needed because BKE_id_ui_prefix used 3 letter prefix
+   * followed by ID_NAME-2 characters from id->name
+   */
+  char name_ui[MAX_ID_FULL_NAME_UI];
+  int iconid = ui_id_icon_get(C, id, template_ui->preview);
+  const bool use_lib_prefix = template_ui->preview || iconid;
+  const bool has_sep_char = (id->lib != NULL);
+
+  /* When using previews, the library hint (linked, overridden, missing) is added with a
+   * character prefix, otherwise we can use a icon. */
+  int name_prefix_offset;
+  BKE_id_full_name_ui_prefix_get(name_ui, id, use_lib_prefix, UI_SEP_CHAR, &name_prefix_offset);
+  if (!use_lib_prefix) {
+    iconid = UI_library_icon_get(id);
+  }
+
+  if (!UI_search_item_add(items,
+                          name_ui,
+                          id,
+                          iconid,
+                          has_sep_char ? UI_BUT_HAS_SEP_CHAR : 0,
+                          name_prefix_offset)) {
+    return false;
   }
+
   return true;
 }
 
@@ -404,12 +399,26 @@ static void id_search_cb(const bContext *C,
   ListBase *lb = template_ui->idlb;
   const int flag = RNA_property_flag(template_ui->prop);
 
+  StringSearch *search = BLI_string_search_new();
+
   /* ID listbase */
   LISTBASE_FOREACH (ID *, id, lb) {
-    if (!id_search_add(C, template_ui, flag, str, items, id)) {
+    if (id_search_allows_id(template_ui, flag, id, str)) {
+      BLI_string_search_add(search, id->name + 2, id);
+    }
+  }
+
+  ID **filtered_ids;
+  int filtered_amount = BLI_string_search_query(search, str, (void ***)&filtered_ids);
+
+  for (int i = 0; i < filtered_amount; i++) {
+    if (!id_search_add(C, template_ui, items, filtered_ids[i])) {
       break;
     }
   }
+
+  MEM_freeN(filtered_ids);
+  BLI_string_search_free(search);
 }
 
 /**
@@ -424,15 +433,29 @@ static void id_search_cb_tagged(const bContext *C,
   ListBase *lb = template_ui->idlb;
   const int flag = RNA_property_flag(template_ui->prop);
 
+  StringSearch *search = BLI_string_search_new();
+
   /* ID listbase */
   LISTBASE_FOREACH (ID *, id, lb) {
     if (id->tag & LIB_TAG_DOIT) {
-      if (!id_search_add(C, template_ui, flag, str, items, id)) {
-        break;
+      if (id_search_allows_id(template_ui, flag, id, str)) {
+        BLI_string_search_add(search, id->name + 2, id);
       }
       id->tag &= ~LIB_TAG_DOIT;
     }
   }
+
+  ID **filtered_ids;
+  int filtered_amount = BLI_string_search_query(search, str, (void ***)&filtered_ids);
+
+  for (int i = 0; i < filtered_amount; i++) {
+    if (!id_search_add(C, template_ui, items, filtered_ids[i])) {
+      break;
+    }
+  }
+
+  MEM_freeN(filtered_ids);
+  BLI_string_search_free(search);
 }
 
 /**
diff --git a/source/blender/editors/space_node/node_select.c b/source/blender/editors/space_node/node_select.c
index 83ccfa65af3..5f3047fbdc2 100644
--- a/source/blender/editors/space_node/node_select.c
+++ b/source/blender/editors/space_node/node_select.c
@@ -32,6 +32,7 @@
 #include "BLI_math.h"
 #include "BLI_rect.h"
 #include "BLI_string.h"
+#include "BLI_string_search.h"
 #include "BLI_string_utf8.h"
 #include "BLI_utildefines.h"
 
@@ -1163,6 +1164,16 @@ void NODE_OT_select_same_type_step(wmOperatorType *ot)
 /** \name Find Node by Name Operator
  * \{ */
 
+static void node_find_create_label(const bNode *node, char *str, int maxlen)
+{
+  if (node->label[0]) {
+    BLI_snprintf(str, maxlen, "%s (%s)", node->name, node->label);
+  }
+  else {
+    BLI_strncpy(str, node->name, maxlen);
+  }
+}
+
 /* generic  search invoke */
 static void node_find_update_fn(const struct bContext *C,
                                 void *UNUSED(arg),
@@ -1170,30 +1181,29 @@ static void node_find_update_fn(const struct bContext *C,
                                 uiSearchItems *items)
 {
   SpaceNode *snode = CTX_wm_space_node(C);
-  bNode *node;
 
-  /* 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);
+  StringSearch *search = BLI_string_search_new();
 
-  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];
+  LISTBASE_FOREACH (bNode *, node, &snode->edittree->nodes) {
+    char name[256];
+    node_find_create_label(node, name, ARRAY_SIZE(name));
+    BLI_string_search_add(search, name, node);
+  }
 
-      if (node->label[0]) {
-        BLI_snprintf(name, 256, "%s (%s)", node->name, node->label);
-      }
-      else {
-        BLI_strncpy(name, node->name, 256);
-      }
-      if (!UI_search_item_add(items, name, node, ICON_NONE, 0, 0)) {
-        break;
-      }
+  bNode **filtered_nodes;
+  int filtered_amount = BLI_string_search_query(search, str, (void ***)&filtered_nodes);
+
+  for (int i = 0; i < filtered_amount; i++) {
+    bNode *node = filtered_nodes[i];
+    char name[256];
+    node_find_create_label(node, name, ARRAY_SIZE(name));
+    if (!UI_search_item_add(items, name, node, ICON_NONE, 0, 0)) {
+      break;
     }
   }
+
+  MEM_freeN(filtered_nodes);
+  BLI_string_search_free(search);
 }
 
 static void node_find_exec_fn(struct bContext *C, void *UNUSED(arg1), void *arg2)