T91406: Asset Library Indexing

Asset library indexing would store indexes of asset files to speed up
asset library browsing.

* Indexes are read when they are up to date
** Index should exist
** Index last modify data should be later than the file it indexes
** Index version should match
* The index of a file containing no assets can be load without opening
   the index file. The size of the file should be below a 32 bytes.
* Indexes are stored on a persistent cache folder.
* Unused index files are automatically removed.

The structure of the index files contains all data needed for browsing assets:
```
{
  "version": <file version number>,
  "entries": [{
    "name": "<asset name>",
    "catalog_id": "<catalog_id>",
    "catalog_name": "<catalog_name>",
    "description": "<description>",
    "author": "<author>",
    "tags": ["<tag>"]
  }]
}
```

Reviewed By: sybren, Severin

Maniphest Tasks: T91406

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

6 files changed, 310 insertions, 31 deletions

diff --git a/source/blender/editors/space_file/CMakeLists.txt b/source/blender/editors/space_file/CMakeLists.txt
index 4b508f16c1e..1651269869e 100644
--- a/source/blender/editors/space_file/CMakeLists.txt
+++ b/source/blender/editors/space_file/CMakeLists.txt
@@ -17,6 +17,7 @@
 
 set(INC
   ../include
+  ../asset
   ../../blenfont
   ../../blenkernel
   ../../blenlib
@@ -36,6 +37,7 @@ set(INC
 set(SRC
   asset_catalog_tree_view.cc
   file_draw.c
+  file_indexer.cc
   file_ops.c
   file_panels.c
   file_utils.c
@@ -44,6 +46,7 @@ set(SRC
   fsmenu.c
   space_file.c
 
+  file_indexer.h
   file_intern.h
   filelist.h
   fsmenu.h
diff --git a/source/blender/editors/space_file/file_indexer.cc b/source/blender/editors/space_file/file_indexer.cc
new file mode 100644
index 00000000000..95e0afd7a1e
--- /dev/null
+++ b/source/blender/editors/space_file/file_indexer.cc
@@ -0,0 +1,96 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup edfile
+ *
+ * This file implements the default file browser indexer and has some helper function to work with
+ * `FileIndexerEntries`.
+ */
+#include "file_indexer.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_linklist.h"
+#include "BLI_listbase.h"
+#include "BLI_string.h"
+#include "BLI_utildefines.h"
+
+namespace blender::ed::file::indexer {
+
+static eFileIndexerResult read_index(const char *UNUSED(file_name),
+                                     FileIndexerEntries *UNUSED(entries),
+                                     int *UNUSED(r_read_entries_len),
+                                     void *UNUSED(user_data))
+{
+  return FILE_INDEXER_NEEDS_UPDATE;
+}
+
+static void update_index(const char *UNUSED(file_name),
+                         FileIndexerEntries *UNUSED(entries),
+                         void *UNUSED(user_data))
+{
+}
+
+constexpr FileIndexerType default_indexer()
+{
+  FileIndexerType indexer = {nullptr};
+  indexer.read_index = read_index;
+  indexer.update_index = update_index;
+  return indexer;
+}
+
+static FileIndexerEntry *file_indexer_entry_create_from_datablock_info(
+    const BLODataBlockInfo *datablock_info, const int idcode)
+{
+  FileIndexerEntry *entry = static_cast<FileIndexerEntry *>(
+      MEM_mallocN(sizeof(FileIndexerEntry), __func__));
+  entry->datablock_info = *datablock_info;
+  entry->idcode = idcode;
+  return entry;
+}
+
+}  // namespace blender::ed::file::indexer
+
+extern "C" {
+
+void ED_file_indexer_entries_extend_from_datablock_infos(
+    FileIndexerEntries *indexer_entries,
+    const LinkNode * /* BLODataBlockInfo */ datablock_infos,
+    const int idcode)
+{
+  for (const LinkNode *ln = datablock_infos; ln; ln = ln->next) {
+    const BLODataBlockInfo *datablock_info = static_cast<const BLODataBlockInfo *>(ln->link);
+    FileIndexerEntry *file_indexer_entry =
+        blender::ed::file::indexer::file_indexer_entry_create_from_datablock_info(datablock_info,
+                                                                                  idcode);
+    BLI_linklist_prepend(&indexer_entries->entries, file_indexer_entry);
+  }
+}
+
+static void ED_file_indexer_entry_free(void *indexer_entry)
+{
+  MEM_freeN(indexer_entry);
+}
+
+void ED_file_indexer_entries_clear(FileIndexerEntries *indexer_entries)
+{
+  BLI_linklist_free(indexer_entries->entries, ED_file_indexer_entry_free);
+  indexer_entries->entries = nullptr;
+}
+
+const FileIndexerType file_indexer_noop = blender::ed::file::indexer::default_indexer();
+}
diff --git a/source/blender/editors/space_file/file_indexer.h b/source/blender/editors/space_file/file_indexer.h
new file mode 100644
index 00000000000..ea42f10498b
--- /dev/null
+++ b/source/blender/editors/space_file/file_indexer.h
@@ -0,0 +1,36 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup edfile
+ */
+#pragma once
+
+#include "ED_file_indexer.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * Default indexer to use when listing files. The implementation is a no-operation indexing. When
+ * set it won't use indexing. It is added to increase the code clarity.
+ */
+extern const FileIndexerType file_indexer_noop;
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/source/blender/editors/space_file/filelist.c b/source/blender/editors/space_file/filelist.c
index 045ebd10c0a..d4e9118960a 100644
--- a/source/blender/editors/space_file/filelist.c
+++ b/source/blender/editors/space_file/filelist.c
@@ -89,6 +89,7 @@
 
 #include "atomic_ops.h"
 
+#include "file_indexer.h"
 #include "file_intern.h"
 #include "filelist.h"
 
@@ -396,6 +397,11 @@ typedef struct FileList {
 
   FileListFilter filter_data;
 
+  /**
+   * File indexer to use. Attribute is always set.
+   */
+  const struct FileIndexerType *indexer;
+
   struct FileListIntern filelist_intern;
 
   struct FileListEntryCache filelist_cache;
@@ -1126,6 +1132,19 @@ void filelist_setfilter_options(FileList *filelist,
 }
 
 /**
+ * Set the indexer to be used by the filelist.
+ *
+ * The given indexer allocation should be handled by the caller or defined statically.
+ */
+void filelist_setindexer(FileList *filelist, const FileIndexerType *indexer)
+{
+  BLI_assert(filelist);
+  BLI_assert(indexer);
+
+  filelist->indexer = indexer;
+}
+
+/**
  * \param catalog_id: The catalog that should be filtered by if \a catalog_visibility is
  *                    #FILE_SHOW_ASSETS_FROM_CATALOG. May be NULL otherwise.
  */
@@ -1830,6 +1849,8 @@ FileList *filelist_new(short type)
   p->filelist.nbr_entries = FILEDIR_NBR_ENTRIES_UNSET;
   filelist_settype(p, type);
 
+  p->indexer = &file_indexer_noop;
+
   return p;
 }
 
@@ -3120,6 +3141,29 @@ static FileListInternEntry *filelist_readjob_list_lib_group_create(const int idc
   return entry;
 }
 
+static void filelist_readjob_list_lib_add_datablock(ListBase *entries,
+                                                    const BLODataBlockInfo *datablock_info,
+                                                    const bool prefix_relpath_with_group_name,
+                                                    const int idcode,
+                                                    const char *group_name)
+{
+  FileListInternEntry *entry = MEM_callocN(sizeof(*entry), __func__);
+  if (prefix_relpath_with_group_name) {
+    entry->relpath = BLI_sprintfN("%s/%s", group_name, datablock_info->name);
+  }
+  else {
+    entry->relpath = BLI_strdup(datablock_info->name);
+  }
+  entry->typeflag |= FILE_TYPE_BLENDERLIB;
+  if (datablock_info && datablock_info->asset_data) {
+    entry->typeflag |= FILE_TYPE_ASSET;
+    /* Moves ownership! */
+    entry->imported_asset_data = datablock_info->asset_data;
+  }
+  entry->blentype = idcode;
+  BLI_addtail(entries, entry);
+}
+
 static void filelist_readjob_list_lib_add_datablocks(ListBase *entries,
                                                      LinkNode *datablock_infos,
                                                      const bool prefix_relpath_with_group_name,
@@ -3127,29 +3171,71 @@ static void filelist_readjob_list_lib_add_datablocks(ListBase *entries,
                                                      const char *group_name)
 {
   for (LinkNode *ln = datablock_infos; ln; ln = ln->next) {
-    struct BLODataBlockInfo *info = ln->link;
-    FileListInternEntry *entry = MEM_callocN(sizeof(*entry), __func__);
-    if (prefix_relpath_with_group_name) {
-      entry->relpath = BLI_sprintfN("%s/%s", group_name, info->name);
-    }
-    else {
-      entry->relpath = BLI_strdup(info->name);
-    }
-    entry->typeflag |= FILE_TYPE_BLENDERLIB;
-    if (info && info->asset_data) {
-      entry->typeflag |= FILE_TYPE_ASSET;
-      /* Moves ownership! */
-      entry->imported_asset_data = info->asset_data;
-    }
-    entry->blentype = idcode;
+    struct BLODataBlockInfo *datablock_info = ln->link;
+    filelist_readjob_list_lib_add_datablock(
+        entries, datablock_info, prefix_relpath_with_group_name, idcode, group_name);
+  }
+}
+
+static void filelist_readjob_list_lib_add_from_indexer_entries(
+    ListBase *entries,
+    const FileIndexerEntries *indexer_entries,
+    const bool prefix_relpath_with_group_name)
+{
+  for (const LinkNode *ln = indexer_entries->entries; ln; ln = ln->next) {
+    const FileIndexerEntry *indexer_entry = (const FileIndexerEntry *)ln->link;
+    const char *group_name = BKE_idtype_idcode_to_name(indexer_entry->idcode);
+    filelist_readjob_list_lib_add_datablock(entries,
+                                            &indexer_entry->datablock_info,
+                                            prefix_relpath_with_group_name,
+                                            indexer_entry->idcode,
+                                            group_name);
+  }
+}
+
+static FileListInternEntry *filelist_readjob_list_lib_navigate_to_parent_entry_create(void)
+{
+  FileListInternEntry *entry = MEM_callocN(sizeof(*entry), __func__);
+  entry->relpath = BLI_strdup(FILENAME_PARENT);
+  entry->typeflag |= (FILE_TYPE_BLENDERLIB | FILE_TYPE_DIR);
+  return entry;
+}
+
+/**
+ * Structure to keep the file indexer and its user data together.
+ */
+typedef struct FileIndexer {
+  const FileIndexerType *callbacks;
+
+  /**
+   * User data. Contains the result of `callbacks.init_user_data`.
+   */
+  void *user_data;
+} FileIndexer;
+
+static int filelist_readjob_list_lib_populate_from_index(ListBase *entries,
+                                                         const ListLibOptions options,
+                                                         const int read_from_index,
+                                                         const FileIndexerEntries *indexer_entries)
+{
+  int navigate_to_parent_len = 0;
+  if (options & LIST_LIB_ADD_PARENT) {
+    FileListInternEntry *entry = filelist_readjob_list_lib_navigate_to_parent_entry_create();
     BLI_addtail(entries, entry);
+    navigate_to_parent_len = 1;
   }
+
+  filelist_readjob_list_lib_add_from_indexer_entries(entries, indexer_entries, true);
+  return read_from_index + navigate_to_parent_len;
 }
 
 static int filelist_readjob_list_lib(const char *root,
                                      ListBase *entries,
-                                     const ListLibOptions options)
+                                     const ListLibOptions options,
+                                     FileIndexer *indexer_runtime)
 {
+  BLI_assert(indexer_runtime);
+
   char dir[FILE_MAX_LIBEXTRA], *group;
 
   struct BlendHandle *libfiledata = NULL;
@@ -3157,13 +3243,37 @@ static int filelist_readjob_list_lib(const char *root,
   /* Check if the given root is actually a library. All folders are passed to
    * `filelist_readjob_list_lib` and based on the number of found entries `filelist_readjob_do`
    * will do a dir listing only when this function does not return any entries. */
-  /* TODO: We should consider introducing its own function to detect if it is a lib and
+  /* TODO(jbakker): We should consider introducing its own function to detect if it is a lib and
    * call it directly from `filelist_readjob_do` to increase readability. */
   const bool is_lib = BLO_library_path_explode(root, dir, &group, NULL);
   if (!is_lib) {
     return 0;
   }
 
+  const bool group_came_from_path = group != NULL;
+
+  /* Try read from indexer_runtime. */
+  /* Indexing returns all entries in a blend file. We should ignore the index when listing a group
+   * inside a blend file, so the `entries` isn't filled with undesired entries.
+   * This happens when linking or appending data-blocks, where you can navigate into a group (fe
+   * Materials/Objects) where you only want to work with partial indexes.
+   *
+   * Adding support for partial reading/updating indexes would increase the complexity.
+   */
+  const bool use_indexer = !group_came_from_path;
+  FileIndexerEntries indexer_entries = {NULL};
+  if (use_indexer) {
+    int read_from_index = 0;
+    eFileIndexerResult indexer_result = indexer_runtime->callbacks->read_index(
+        dir, &indexer_entries, &read_from_index, indexer_runtime->user_data);
+    if (indexer_result == FILE_INDEXER_ENTRIES_LOADED) {
+      int entries_read = filelist_readjob_list_lib_populate_from_index(
+          entries, options, read_from_index, &indexer_entries);
+      ED_file_indexer_entries_clear(&indexer_entries);
+      return entries_read;
+    }
+  }
+
   /* Open the library file. */
   BlendFileReadReport bf_reports = {.reports = NULL};
   libfiledata = BLO_blendhandle_from_file(dir, &bf_reports);
@@ -3172,18 +3282,18 @@ static int filelist_readjob_list_lib(const char *root,
   }
 
   /* Add current parent when requested. */
-  int parent_len = 0;
+  /* Is the navigate to previous level added to the list of entries. When added the return value
+   * should be increased to match the actual number of entries added. It is introduced to keep
+   * the code clean and readable and not counting in a single variable. */
+  int navigate_to_parent_len = 0;
   if (options & LIST_LIB_ADD_PARENT) {
-    FileListInternEntry *entry = MEM_callocN(sizeof(*entry), __func__);
-    entry->relpath = BLI_strdup(FILENAME_PARENT);
-    entry->typeflag |= (FILE_TYPE_BLENDERLIB | FILE_TYPE_DIR);
+    FileListInternEntry *entry = filelist_readjob_list_lib_navigate_to_parent_entry_create();
     BLI_addtail(entries, entry);
-    parent_len = 1;
+    navigate_to_parent_len = 1;
   }
 
   int group_len = 0;
   int datablock_len = 0;
-  const bool group_came_from_path = group != NULL;
   if (group_came_from_path) {
     const int idcode = groupname_to_code(group);
     LinkNode *datablock_infos = BLO_blendhandle_get_datablock_info(
@@ -3208,6 +3318,10 @@ static int filelist_readjob_list_lib(const char *root,
             libfiledata, idcode, options & LIST_LIB_ASSETS_ONLY, &group_datablock_len);
         filelist_readjob_list_lib_add_datablocks(
             entries, group_datablock_infos, true, idcode, group_name);
+        if (use_indexer) {
+          ED_file_indexer_entries_extend_from_datablock_infos(
+              &indexer_entries, group_datablock_infos, idcode);
+        }
         BLI_linklist_freeN(group_datablock_infos);
         datablock_len += group_datablock_len;
       }
@@ -3218,8 +3332,14 @@ static int filelist_readjob_list_lib(const char *root,
 
   BLO_blendhandle_close(libfiledata);
 
+  /* Update the index. */
+  if (use_indexer) {
+    indexer_runtime->callbacks->update_index(dir, &indexer_entries, indexer_runtime->user_data);
+    ED_file_indexer_entries_clear(&indexer_entries);
+  }
+
   /* Return the number of items added to entries. */
-  int added_entries_len = group_len + datablock_len + parent_len;
+  int added_entries_len = group_len + datablock_len + navigate_to_parent_len;
   return added_entries_len;
 }
 
@@ -3411,11 +3531,11 @@ typedef struct FileListReadJob {
    * The job system calls #filelist_readjob_update which moves any read file from #tmp_filelist
    * into #filelist in a thread-safe way.
    *
-   * #tmp_filelist also keeps an `AssetLibrary *` so that it can be loaded in the same thread, and
-   * moved to #filelist once all categories are loaded.
+   * #tmp_filelist also keeps an `AssetLibrary *` so that it can be loaded in the same thread,
+   * and moved to #filelist once all categories are loaded.
    *
-   * NOTE: #tmp_filelist is freed in #filelist_readjob_free, so any copied pointers need to be set
-   * to NULL to avoid double-freeing them. */
+   * NOTE: #tmp_filelist is freed in #filelist_readjob_free, so any copied pointers need to be
+   * set to NULL to avoid double-freeing them. */
   struct FileList *tmp_filelist;
 } FileListReadJob;
 
@@ -3452,8 +3572,8 @@ static bool filelist_readjob_should_recurse_into_entry(const int max_recursion,
     /* No more levels of recursion left. */
     return false;
   }
-  /* Show entries when recursion is set to `Blend file` even when `current_recursion_level` exceeds
-   * `max_recursion`. */
+  /* Show entries when recursion is set to `Blend file` even when `current_recursion_level`
+   * exceeds `max_recursion`. */
   if (!is_lib && (current_recursion_level >= max_recursion) &&
       ((entry->typeflag & (FILE_TYPE_BLENDER | FILE_TYPE_BLENDER_BACKUP)) == 0)) {
     return false;
@@ -3501,6 +3621,12 @@ static void filelist_readjob_recursive_dir_add_items(const bool do_lib,
   BLI_path_normalize_dir(job_params->main_name, dir);
   td_dir->dir = BLI_strdup(dir);
 
+  /* Init the file indexer. */
+  FileIndexer indexer_runtime = {.callbacks = filelist->indexer};
+  if (indexer_runtime.callbacks->init_user_data) {
+    indexer_runtime.user_data = indexer_runtime.callbacks->init_user_data(dir, sizeof(dir));
+  }
+
   while (!BLI_stack_is_empty(todo_dirs) && !(*stop)) {
     FileListInternEntry *entry;
     int nbr_entries = 0;
@@ -3543,7 +3669,8 @@ static void filelist_readjob_recursive_dir_add_items(const bool do_lib,
       if (filelist->asset_library_ref) {
         list_lib_options |= LIST_LIB_ASSETS_ONLY;
       }
-      nbr_entries = filelist_readjob_list_lib(subdir, &entries, list_lib_options);
+      nbr_entries = filelist_readjob_list_lib(
+          subdir, &entries, list_lib_options, &indexer_runtime);
       if (nbr_entries > 0) {
         is_lib = true;
       }
@@ -3585,6 +3712,15 @@ static void filelist_readjob_recursive_dir_add_items(const bool do_lib,
     MEM_freeN(subdir);
   }
 
+  /* Finalize and free indexer. */
+  if (indexer_runtime.callbacks->filelist_finished && BLI_stack_is_empty(todo_dirs)) {
+    indexer_runtime.callbacks->filelist_finished(indexer_runtime.user_data);
+  }
+  if (indexer_runtime.callbacks->free_user_data && indexer_runtime.user_data) {
+    indexer_runtime.callbacks->free_user_data(indexer_runtime.user_data);
+    indexer_runtime.user_data = NULL;
+  }
+
   /* If we were interrupted by stop, stack may not be empty and we need to free
    * pending dir paths. */
   while (!BLI_stack_is_empty(todo_dirs)) {
diff --git a/source/blender/editors/space_file/filelist.h b/source/blender/editors/space_file/filelist.h
index 0048a349dca..e7cda106224 100644
--- a/source/blender/editors/space_file/filelist.h
+++ b/source/blender/editors/space_file/filelist.h
@@ -29,6 +29,7 @@ extern "C" {
 
 struct AssetLibraryReference;
 struct BlendHandle;
+struct FileIndexerType;
 struct FileList;
 struct FileSelection;
 struct bUUID;
@@ -72,6 +73,7 @@ void filelist_setfilter_options(struct FileList *filelist,
                                 const bool filter_assets_only,
                                 const char *filter_glob,
                                 const char *filter_search);
+void filelist_setindexer(struct FileList *filelist, const struct FileIndexerType *indexer);
 void filelist_set_asset_catalog_filter_options(
     struct FileList *filelist,
     eFileSel_Params_AssetCatalogVisibility catalog_visibility,
diff --git a/source/blender/editors/space_file/space_file.c b/source/blender/editors/space_file/space_file.c
index ef503708335..f2a01c9db6b 100644
--- a/source/blender/editors/space_file/space_file.c
+++ b/source/blender/editors/space_file/space_file.c
@@ -27,6 +27,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_blenlib.h"
+#include "BLI_linklist.h"
 #include "BLI_utildefines.h"
 
 #include "BKE_appdir.h"
@@ -43,6 +44,7 @@
 #include "WM_message.h"
 #include "WM_types.h"
 
+#include "ED_asset_indexer.h"
 #include "ED_asset.h"
 #include "ED_fileselect.h"
 #include "ED_screen.h"
@@ -353,6 +355,10 @@ static void file_refresh(const bContext *C, ScrArea *area)
         sfile->files, asset_params->asset_catalog_visibility, &asset_params->catalog_id);
   }
 
+  if (ED_fileselect_is_asset_browser(sfile)) {
+    filelist_setindexer(sfile->files, &file_indexer_asset);
+  }
+
   /* Update the active indices of bookmarks & co. */
   sfile->systemnr = fsmenu_get_active_indices(fsmenu, FS_CATEGORY_SYSTEM, params->dir);
   sfile->system_bookmarknr = fsmenu_get_active_indices(