UI: fuzzy search in collection search

This adds fuzzy search functionality to various input fields in Blender
where one can choose a value from many existing values (e.g. the
Vertex Group property in the Displace modifier).

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

1 files changed, 55 insertions, 47 deletions

diff --git a/source/blender/editors/interface/interface_utils.c b/source/blender/editors/interface/interface_utils.c
index 824fb6272f6..5311bb57da9 100644
--- a/source/blender/editors/interface/interface_utils.c
+++ b/source/blender/editors/interface/interface_utils.c
@@ -33,6 +33,7 @@
 #include "BLI_listbase.h"
 #include "BLI_math.h"
 #include "BLI_string.h"
+#include "BLI_string_search.h"
 #include "BLI_utildefines.h"
 
 #include "BLT_translation.h"
@@ -374,15 +375,31 @@ typedef struct CollItemSearch {
   uint has_sep_char : 1;
 } CollItemSearch;
 
-static int sort_search_items_list(const void *a, const void *b)
+static bool add_collection_search_item(CollItemSearch *cis,
+                                       const bool requires_exact_data_name,
+                                       const bool has_id_icon,
+                                       uiSearchItems *items)
 {
-  const CollItemSearch *cis1 = a;
-  const CollItemSearch *cis2 = b;
+  char name_buf[UI_MAX_DRAW_STR];
 
-  if (BLI_strcasecmp(cis1->name, cis2->name) > 0) {
-    return 1;
+  /* If no item has an own icon to display, libraries can use the library icons rather than the
+   * name prefix for showing the library status. */
+  int name_prefix_offset = cis->name_prefix_offset;
+  if (!has_id_icon && cis->is_id && !requires_exact_data_name) {
+    cis->iconid = UI_icon_from_library(cis->data);
+    /* No need to re-allocate, string should be shorter than before (lib status prefix is
+     * removed). */
+    BKE_id_full_name_ui_prefix_get(name_buf, cis->data, false, UI_SEP_CHAR, &name_prefix_offset);
+    BLI_assert(strlen(name_buf) <= MEM_allocN_len(cis->name));
+    strcpy(cis->name, name_buf);
   }
-  return 0;
+
+  return UI_search_item_add(items,
+                            cis->name,
+                            cis->data,
+                            cis->iconid,
+                            cis->has_sep_char ? UI_BUT_HAS_SEP_CHAR : 0,
+                            name_prefix_offset);
 }
 
 void ui_rna_collection_search_update_fn(const struct bContext *C,
@@ -392,9 +409,7 @@ void ui_rna_collection_search_update_fn(const struct bContext *C,
 {
   uiRNACollectionSearch *data = arg;
   const int flag = RNA_property_flag(data->target_prop);
-  int i = 0;
   ListBase *items_list = MEM_callocN(sizeof(ListBase), "items_list");
-  CollItemSearch *cis;
   const bool is_ptr_target = (RNA_property_type(data->target_prop) == PROP_POINTER);
   /* For non-pointer properties, UI code acts entirely based on the item's name. So the name has to
    * match the RNA name exactly. So only for pointer properties, the name can be modified to add
@@ -405,13 +420,10 @@ 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);
+  StringSearch *search = skip_filter ? NULL : BLI_string_search_new();
 
   /* build a temporary list of relevant items first */
+  int item_index = 0;
   RNA_PROP_BEGIN (&data->search_ptr, itemptr, data->search_prop) {
 
     if (flag & PROP_ID_SELF_CHECK) {
@@ -456,54 +468,50 @@ void ui_rna_collection_search_update_fn(const struct bContext *C,
     }
 
     if (name) {
-      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);
-        cis->index = i;
-        cis->iconid = iconid;
-        cis->is_id = is_id;
-        cis->name_prefix_offset = name_prefix_offset;
-        cis->has_sep_char = has_sep_char;
-        BLI_addtail(items_list, cis);
+      CollItemSearch *cis = MEM_callocN(sizeof(CollItemSearch), "CollectionItemSearch");
+      cis->data = itemptr.data;
+      cis->name = BLI_strdup(name);
+      cis->index = item_index;
+      cis->iconid = iconid;
+      cis->is_id = is_id;
+      cis->name_prefix_offset = name_prefix_offset;
+      cis->has_sep_char = has_sep_char;
+      if (!skip_filter) {
+        BLI_string_search_add(search, name, cis);
       }
+      BLI_addtail(items_list, cis);
       if (name != name_buf) {
         MEM_freeN(name);
       }
     }
 
-    i++;
+    item_index++;
   }
   RNA_PROP_END;
 
-  BLI_listbase_sort(items_list, sort_search_items_list);
-
-  /* add search items from temporary list */
-  for (cis = items_list->first; cis; cis = cis->next) {
-    /* If no item has an own icon to display, libraries can use the library icons rather than the
-     * name prefix for showing the library status. */
-    int name_prefix_offset = cis->name_prefix_offset;
-    if (!has_id_icon && cis->is_id && !requires_exact_data_name) {
-      cis->iconid = UI_icon_from_library(cis->data);
-      /* No need to re-allocate, string should be shorter than before (lib status prefix is
-       * removed). */
-      BKE_id_full_name_ui_prefix_get(name_buf, cis->data, false, UI_SEP_CHAR, &name_prefix_offset);
-      BLI_assert(strlen(name_buf) <= MEM_allocN_len(cis->name));
-      strcpy(cis->name, name_buf);
+  if (skip_filter) {
+    LISTBASE_FOREACH (CollItemSearch *, cis, items_list) {
+      if (!add_collection_search_item(cis, requires_exact_data_name, has_id_icon, items)) {
+        break;
+      }
     }
+  }
+  else {
+    CollItemSearch **filtered_items;
+    int filtered_amount = BLI_string_search_query(search, str, (void ***)&filtered_items);
 
-    if (!UI_search_item_add(items,
-                            cis->name,
-                            cis->data,
-                            cis->iconid,
-                            cis->has_sep_char ? UI_BUT_HAS_SEP_CHAR : 0,
-                            name_prefix_offset)) {
-      break;
+    for (int i = 0; i < filtered_amount; i++) {
+      CollItemSearch *cis = filtered_items[i];
+      if (!add_collection_search_item(cis, requires_exact_data_name, has_id_icon, items)) {
+        break;
+      }
     }
+
+    MEM_freeN(filtered_items);
+    BLI_string_search_free(search);
   }
 
-  for (cis = items_list->first; cis; cis = cis->next) {
+  LISTBASE_FOREACH (CollItemSearch *, cis, items_list) {
     MEM_freeN(cis->name);
   }
   BLI_freelistN(items_list);