Refactor BMain relations temp data.

`bmain.relations` is used to store temp data of relations between IDs,
to speed-up some complex processes heavily relying on such information.

Previous implementation was failry unclear/confusing, and required a
not-so-nice hack to 'tag' some ID as processed.

New code changes as such:
* Using `from`/`to` naming (instead of `user`/`used`).
* More clear separation between `to` `id_pointer` and `from` one,
  using an union instead of hacking around difference between `ID *` and
  `ID **` pointers.
* Adds storage of `session_uuid` informations (mainly useful as
  debug/ensuring proper consistency of data currently).
* Adds a structure per ID in the mapping. This enables possibility of
  storing tags (and potentially more  data in the future) per-ID,
  without polluting the IDs themselves with very short-life info.

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

5 files changed, 138 insertions, 108 deletions

diff --git a/source/blender/blenkernel/BKE_main.h b/source/blender/blenkernel/BKE_main.h
index 8106607572b..0768423fc5f 100644
--- a/source/blender/blenkernel/BKE_main.h
+++ b/source/blender/blenkernel/BKE_main.h
@@ -60,22 +60,52 @@ typedef struct BlendThumbnail {
 } BlendThumbnail;
 
 /* Structs caching relations between data-blocks in a given Main. */
+typedef struct MainIDRelationsEntryItem {
+  struct MainIDRelationsEntryItem *next;
+
+  union {
+    /* For `from_ids` list, a user of the hashed ID. */
+    struct ID *from;
+    /* For `to_ids` list, an ID used by the hashed ID. */
+    struct ID **to;
+  } id_pointer;
+  /* Session uuid of the `id_pointer`. */
+  uint session_uuid;
+
+  int usage_flag; /* Using IDWALK_ enums, defined in BKE_lib_query.h */
+} MainIDRelationsEntryItem;
+
 typedef struct MainIDRelationsEntry {
-  struct MainIDRelationsEntry *next;
-  /* WARNING! for user_to_used,
-   * that pointer is really an ID** one, but for used_to_user, it’s only an ID* one! */
-  struct ID **id_pointer;
-  int usage_flag; /* Using IDWALK_ enums, in BKE_lib_query.h */
+  /* Linked list of IDs using that ID. */
+  struct MainIDRelationsEntryItem *from_ids;
+  /* Linked list of IDs used by that ID. */
+  struct MainIDRelationsEntryItem *to_ids;
+
+  /* Session uuid of the ID matching that entry. */
+  uint session_uuid;
+
+  /* Runtime tags, users should ensure those are reset after usage. */
+  uint tags;
 } MainIDRelationsEntry;
 
+/* MainIDRelationsEntry.tags */
+typedef enum MainIDRelationsEntryTags {
+  /* Generic tag marking the entry as to be processed. */
+  MAINIDRELATIONS_ENTRY_TAGS_DOIT = 1 << 0,
+  /* Generic tag marking the entry as processed. */
+  MAINIDRELATIONS_ENTRY_TAGS_PROCESSED = 1 << 1,
+} MainIDRelationsEntryTags;
+
 typedef struct MainIDRelations {
-  struct GHash *id_user_to_used;
-  struct GHash *id_used_to_user;
+  /* Mapping from an ID pointer to all of its parents (IDs using it) and children (IDs it uses).
+   * Values are `MainIDRelationsEntry` pointers. */
+  struct GHash *relations_from_pointers;
+  /* Note: we could add more mappings when needed (e.g. from session uuid?). */
 
   short flag;
 
   /* Private... */
-  struct BLI_mempool *entry_pool;
+  struct BLI_mempool *entry_items_pool;
 } MainIDRelations;
 
 enum {
@@ -172,7 +202,6 @@ void BKE_main_unlock(struct Main *bmain);
 
 void BKE_main_relations_create(struct Main *bmain, const short flag);
 void BKE_main_relations_free(struct Main *bmain);
-void BKE_main_relations_ID_remove(struct Main *bmain, struct ID *id);
 
 struct GSet *BKE_main_gset_create(struct Main *bmain, struct GSet *gset);
 
diff --git a/source/blender/blenkernel/intern/lib_id.c b/source/blender/blenkernel/intern/lib_id.c
index 838f3046ed0..54c2f5f5565 100644
--- a/source/blender/blenkernel/intern/lib_id.c
+++ b/source/blender/blenkernel/intern/lib_id.c
@@ -1795,32 +1795,31 @@ static void library_make_local_copying_check(ID *id,
     return; /* Already checked, nothing else to do. */
   }
 
-  MainIDRelationsEntry *entry = BLI_ghash_lookup(id_relations->id_used_to_user, id);
+  MainIDRelationsEntry *entry = BLI_ghash_lookup(id_relations->relations_from_pointers, id);
   BLI_gset_insert(loop_tags, id);
-  for (; entry != NULL; entry = entry->next) {
-
-    /* Used_to_user stores ID pointer, not pointer to ID pointer. */
-    ID *par_id = (ID *)entry->id_pointer;
-
+  for (MainIDRelationsEntryItem *from_id_entry = entry->from_ids; from_id_entry != NULL;
+       from_id_entry = from_id_entry->next) {
     /* Our oh-so-beloved 'from' pointers... Those should always be ignored here, since the actual
      * relation we want to check is in the other way around. */
-    if (entry->usage_flag & IDWALK_CB_LOOPBACK) {
+    if (from_id_entry->usage_flag & IDWALK_CB_LOOPBACK) {
       continue;
     }
 
+    ID *from_id = from_id_entry->id_pointer.from;
+
     /* Shape-keys are considered 'private' to their owner ID here, and never tagged
      * (since they cannot be linked), so we have to switch effective parent to their owner.
      */
-    if (GS(par_id->name) == ID_KE) {
-      par_id = ((Key *)par_id)->from;
+    if (GS(from_id->name) == ID_KE) {
+      from_id = ((Key *)from_id)->from;
     }
 
-    if (par_id->lib == NULL) {
+    if (from_id->lib == NULL) {
       /* Local user, early out to avoid some gset querying... */
       continue;
     }
-    if (!BLI_gset_haskey(done_ids, par_id)) {
-      if (BLI_gset_haskey(loop_tags, par_id)) {
+    if (!BLI_gset_haskey(done_ids, from_id)) {
+      if (BLI_gset_haskey(loop_tags, from_id)) {
         /* We are in a 'dependency loop' of IDs, this does not say us anything, skip it.
          * Note that this is the situation that can lead to archipelagoes of linked data-blocks
          * (since all of them have non-local users, they would all be duplicated,
@@ -1829,10 +1828,10 @@ static void library_make_local_copying_check(ID *id,
         continue;
       }
       /* Else, recursively check that user ID. */
-      library_make_local_copying_check(par_id, loop_tags, id_relations, done_ids);
+      library_make_local_copying_check(from_id, loop_tags, id_relations, done_ids);
     }
 
-    if (par_id->tag & LIB_TAG_DOIT) {
+    if (from_id->tag & LIB_TAG_DOIT) {
       /* This user will be fully local in future, so far so good,
        * nothing to do here but check next user. */
     }
diff --git a/source/blender/blenkernel/intern/lib_override.c b/source/blender/blenkernel/intern/lib_override.c
index a7e2394e7ad..388f50e12cf 100644
--- a/source/blender/blenkernel/intern/lib_override.c
+++ b/source/blender/blenkernel/intern/lib_override.c
@@ -374,9 +374,15 @@ static bool lib_override_hierarchy_recursive_tag(Main *bmain,
                                                  const uint missing_tag,
                                                  Library *override_group_lib_reference)
 {
-  void **entry_vp = BLI_ghash_lookup_p(bmain->relations->id_user_to_used, id);
+  void **entry_vp = BLI_ghash_lookup_p(bmain->relations->relations_from_pointers, id);
   if (entry_vp == NULL) {
-    /* Already processed. */
+    /* This ID is not used by nor using any other ID. */
+    return (id->tag & tag) != 0;
+  }
+
+  MainIDRelationsEntry *entry = *entry_vp;
+  if (entry->tags & MAINIDRELATIONS_ENTRY_TAGS_PROCESSED) {
+    /* This ID has already been processed. */
     return (id->tag & tag) != 0;
   }
 
@@ -393,22 +399,21 @@ static bool lib_override_hierarchy_recursive_tag(Main *bmain,
   }
 
   /* This way we won't process again that ID, should we encounter it again through another
-   * relationship hierarchy.
-   * Note that this does not free any memory from relations, so we can still use the entries.
-   */
-  BKE_main_relations_ID_remove(bmain, id);
+   * relationship hierarchy. */
+  entry->tags |= MAINIDRELATIONS_ENTRY_TAGS_PROCESSED;
 
-  for (MainIDRelationsEntry *entry = *entry_vp; entry != NULL; entry = entry->next) {
-    if ((entry->usage_flag & IDWALK_CB_LOOPBACK) != 0) {
+  for (MainIDRelationsEntryItem *to_id_entry = entry->to_ids; to_id_entry != NULL;
+       to_id_entry = to_id_entry->next) {
+    if ((to_id_entry->usage_flag & IDWALK_CB_LOOPBACK) != 0) {
       /* Never consider 'loop back' relationships ('from', 'parents', 'owner' etc. pointers) as
        * actual dependencies. */
       continue;
     }
     /* We only consider IDs from the same library. */
-    if (entry->id_pointer != NULL && (*entry->id_pointer)->lib == id->lib) {
-      if (lib_override_hierarchy_recursive_tag(
-              bmain, *entry->id_pointer, tag, missing_tag, override_group_lib_reference) &&
-          override_group_lib_reference == NULL) {
+    if (*to_id_entry->id_pointer.to != NULL && (*to_id_entry->id_pointer.to)->lib == id->lib) {
+      const bool needs_tag = lib_override_hierarchy_recursive_tag(
+          bmain, *to_id_entry->id_pointer.to, tag, missing_tag, override_group_lib_reference);
+      if (needs_tag && override_group_lib_reference == NULL) {
         id->tag |= tag;
       }
     }
@@ -1619,31 +1624,37 @@ static void lib_override_library_id_hierarchy_recursive_reset(Main *bmain, ID *i
     return;
   }
 
-  void **entry_pp = BLI_ghash_lookup(bmain->relations->id_user_to_used, id_root);
-  if (entry_pp == NULL) {
-    /* Already processed. */
+  void **entry_vp = BLI_ghash_lookup_p(bmain->relations->relations_from_pointers, id_root);
+  if (entry_vp == NULL) {
+    /* This ID is not used by nor using any other ID. */
+    lib_override_library_id_reset_do(bmain, id_root);
+    return;
+  }
+
+  MainIDRelationsEntry *entry = *entry_vp;
+  if (entry->tags & MAINIDRELATIONS_ENTRY_TAGS_PROCESSED) {
+    /* This ID has already been processed. */
     return;
   }
 
   lib_override_library_id_reset_do(bmain, id_root);
 
   /* This way we won't process again that ID, should we encounter it again through another
-   * relationship hierarchy.
-   * Note that this does not free any memory from relations, so we can still use the entries.
-   */
-  BKE_main_relations_ID_remove(bmain, id_root);
+   * relationship hierarchy. */
+  entry->tags |= MAINIDRELATIONS_ENTRY_TAGS_PROCESSED;
 
-  for (MainIDRelationsEntry *entry = *entry_pp; entry != NULL; entry = entry->next) {
-    if ((entry->usage_flag & IDWALK_CB_LOOPBACK) != 0) {
+  for (MainIDRelationsEntryItem *to_id_entry = entry->to_ids; to_id_entry != NULL;
+       to_id_entry = to_id_entry->next) {
+    if ((to_id_entry->usage_flag & IDWALK_CB_LOOPBACK) != 0) {
       /* Never consider 'loop back' relationships ('from', 'parents', 'owner' etc. pointers) as
        * actual dependencies. */
       continue;
     }
     /* We only consider IDs from the same library. */
-    if (entry->id_pointer != NULL) {
-      ID *id_entry = *entry->id_pointer;
-      if (id_entry->override_library != NULL) {
-        lib_override_library_id_hierarchy_recursive_reset(bmain, id_entry);
+    if (*to_id_entry->id_pointer.to != NULL) {
+      ID *to_id = *to_id_entry->id_pointer.to;
+      if (to_id->override_library != NULL) {
+        lib_override_library_id_hierarchy_recursive_reset(bmain, to_id);
       }
     }
   }
diff --git a/source/blender/blenkernel/intern/lib_query.c b/source/blender/blenkernel/intern/lib_query.c
index e687e94073d..8be26fc8547 100644
--- a/source/blender/blenkernel/intern/lib_query.c
+++ b/source/blender/blenkernel/intern/lib_query.c
@@ -237,9 +237,12 @@ static void library_foreach_ID_link(Main *bmain,
        * but we might as well use it (Main->relations is always assumed valid,
        * it's responsibility of code creating it to free it,
        * especially if/when it starts modifying Main database). */
-      MainIDRelationsEntry *entry = BLI_ghash_lookup(bmain->relations->id_user_to_used, id);
-      for (; entry != NULL; entry = entry->next) {
-        BKE_lib_query_foreachid_process(&data, entry->id_pointer, entry->usage_flag);
+      MainIDRelationsEntry *entry = BLI_ghash_lookup(bmain->relations->relations_from_pointers,
+                                                     id);
+      for (MainIDRelationsEntryItem *to_id_entry = entry->to_ids; to_id_entry != NULL;
+           to_id_entry = to_id_entry->next) {
+        BKE_lib_query_foreachid_process(
+            &data, to_id_entry->id_pointer.to, to_id_entry->usage_flag);
       }
       continue;
     }
diff --git a/source/blender/blenkernel/intern/main.c b/source/blender/blenkernel/intern/main.c
index 5afa5890f14..e55b05ce797 100644
--- a/source/blender/blenkernel/intern/main.c
+++ b/source/blender/blenkernel/intern/main.c
@@ -217,29 +217,45 @@ static int main_relations_create_idlink_cb(LibraryIDLinkCallbackData *cb_data)
   const int cb_flag = cb_data->cb_flag;
 
   if (*id_pointer) {
-    MainIDRelationsEntry *entry, **entry_p;
-
-    entry = BLI_mempool_alloc(bmain_relations->entry_pool);
-    if (BLI_ghash_ensure_p(bmain_relations->id_user_to_used, id_self, (void ***)&entry_p)) {
-      entry->next = *entry_p;
-    }
-    else {
-      entry->next = NULL;
+    MainIDRelationsEntry **entry_p;
+
+    /* Add `id_pointer` as child of `id_self`. */
+    {
+      if (!BLI_ghash_ensure_p(
+              bmain_relations->relations_from_pointers, id_self, (void ***)&entry_p)) {
+        *entry_p = MEM_callocN(sizeof(**entry_p), __func__);
+        (*entry_p)->session_uuid = id_self->session_uuid;
+      }
+      else {
+        BLI_assert((*entry_p)->session_uuid == id_self->session_uuid);
+      }
+      MainIDRelationsEntryItem *to_id_entry = BLI_mempool_alloc(bmain_relations->entry_items_pool);
+      to_id_entry->next = (*entry_p)->to_ids;
+      to_id_entry->id_pointer.to = id_pointer;
+      to_id_entry->session_uuid = (*id_pointer != NULL) ? (*id_pointer)->session_uuid :
+                                                          MAIN_ID_SESSION_UUID_UNSET;
+      to_id_entry->usage_flag = cb_flag;
+      (*entry_p)->to_ids = to_id_entry;
     }
-    entry->id_pointer = id_pointer;
-    entry->usage_flag = cb_flag;
-    *entry_p = entry;
 
-    entry = BLI_mempool_alloc(bmain_relations->entry_pool);
-    if (BLI_ghash_ensure_p(bmain_relations->id_used_to_user, *id_pointer, (void ***)&entry_p)) {
-      entry->next = *entry_p;
-    }
-    else {
-      entry->next = NULL;
+    /* Add `id_self` as parent of `id_pointer`. */
+    if (*id_pointer != NULL) {
+      if (!BLI_ghash_ensure_p(
+              bmain_relations->relations_from_pointers, *id_pointer, (void ***)&entry_p)) {
+        *entry_p = MEM_callocN(sizeof(**entry_p), __func__);
+        (*entry_p)->session_uuid = (*id_pointer)->session_uuid;
+      }
+      else {
+        BLI_assert((*entry_p)->session_uuid == (*id_pointer)->session_uuid);
+      }
+      MainIDRelationsEntryItem *from_id_entry = BLI_mempool_alloc(
+          bmain_relations->entry_items_pool);
+      from_id_entry->next = (*entry_p)->from_ids;
+      from_id_entry->id_pointer.from = id_self;
+      from_id_entry->session_uuid = id_self->session_uuid;
+      from_id_entry->usage_flag = cb_flag;
+      (*entry_p)->from_ids = from_id_entry;
     }
-    entry->id_pointer = (ID **)id_self;
-    entry->usage_flag = cb_flag;
-    *entry_p = entry;
   }
 
   return IDWALK_RET_NOP;
@@ -253,12 +269,12 @@ void BKE_main_relations_create(Main *bmain, const short flag)
   }
 
   bmain->relations = MEM_mallocN(sizeof(*bmain->relations), __func__);
-  bmain->relations->id_used_to_user = BLI_ghash_new(
-      BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, __func__);
-  bmain->relations->id_user_to_used = BLI_ghash_new(
+  bmain->relations->relations_from_pointers = BLI_ghash_new(
       BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, __func__);
-  bmain->relations->entry_pool = BLI_mempool_create(
-      sizeof(MainIDRelationsEntry), 128, 128, BLI_MEMPOOL_NOP);
+  bmain->relations->entry_items_pool = BLI_mempool_create(
+      sizeof(MainIDRelationsEntryItem), 128, 128, BLI_MEMPOOL_NOP);
+
+  bmain->relations->flag = flag;
 
   ID *id;
   FOREACH_MAIN_ID_BEGIN (bmain, id) {
@@ -268,49 +284,21 @@ void BKE_main_relations_create(Main *bmain, const short flag)
         NULL, id, main_relations_create_idlink_cb, bmain->relations, idwalk_flag);
   }
   FOREACH_MAIN_ID_END;
-
-  bmain->relations->flag = flag;
 }
 
 void BKE_main_relations_free(Main *bmain)
 {
-  if (bmain->relations) {
-    if (bmain->relations->id_used_to_user) {
-      BLI_ghash_free(bmain->relations->id_used_to_user, NULL, NULL);
-    }
-    if (bmain->relations->id_user_to_used) {
-      BLI_ghash_free(bmain->relations->id_user_to_used, NULL, NULL);
+  if (bmain->relations != NULL) {
+    if (bmain->relations->relations_from_pointers != NULL) {
+      BLI_ghash_free(bmain->relations->relations_from_pointers, NULL, MEM_freeN);
     }
-    BLI_mempool_destroy(bmain->relations->entry_pool);
+    BLI_mempool_destroy(bmain->relations->entry_items_pool);
     MEM_freeN(bmain->relations);
     bmain->relations = NULL;
   }
 }
 
 /**
- * Remove an ID from the relations (the two entries for that ID, not the ID from entries in other
- * IDs' relationships).
- *
- * Does not free any allocated memory.
- * Allows to use those relations as a way to mark an ID as already processed, without requiring any
- * additional tagging or GSet.
- * Obviously, relations should be freed after use then, since this will make them fully invalid.
- */
-void BKE_main_relations_ID_remove(Main *bmain, ID *id)
-{
-  if (bmain->relations) {
-    /* Note: we do not free the entries from the mempool, those will be dealt with when finally
-     * freeing the whole relations. */
-    if (bmain->relations->id_used_to_user) {
-      BLI_ghash_remove(bmain->relations->id_used_to_user, id, NULL, NULL);
-    }
-    if (bmain->relations->id_user_to_used) {
-      BLI_ghash_remove(bmain->relations->id_user_to_used, id, NULL, NULL);
-    }
-  }
-}
-
-/**
  * Create a GSet storing all IDs present in given \a bmain, by their pointers.
  *
  * \param gset: If not NULL, given GSet will be extended with IDs from given \a bmain,