Fix T66282: Make Instances Real: Keep Hierarchy option broken with recursive instancing.

Preserving/rebuilding relashionships in recursive instancing was simply
not supported at all, code handling that was assuming a single level of
instancing.

This commit makes the following changes:
* Mixing DupliCollection and DupliVerts/Faces in the recursive chain is
now supported (by using a same GHash in all cases, differences of
persistent_id handling in hashing and comparison is now down inside the
relevant functions).
* When both "keep hierarchy" and "parent" options are enabled, code will
attempt to parent new objects to their version of instancer (instead of
parenting them systematically to the root object). This will preserve
the hierarchy much better.
* Collection is removed from dupli empties that have been made 'real'
(the duplication flag itself was already cleared, but the link to the
instantiated collection was kept).

source/blender/editors/object/object_add.c

@@ -1658,61 +1658,57 @@ static void copy_object_set_idnew(bContext *C)
 /** \name Make Instanced Objects Real Operator
  * \{ */
 
+/* XXX TODO That whole hierarchy handling based on persistent_id tricks is
+ * very confusing and convoluted, and it will fail in many cases besides basic ones.
+ * Think this should be replaced by a proper tree-like representation of the instantiations,
+ * should help a lot in both readability, and precise consistent rebuilding of hierarchy.
+ */
+
+/**
+ * \note regarding hashing dupli-objects which come from OB_DUPLICOLLECTION,
+ * skip the first member of #DupliObject.persistent_id
+ * since its a unique index and we only want to know if the group objects are from the same
+ * dupli-group instance.
+ *
+ * \note regarding hashing dupli-objects which come from non-OB_DUPLICOLLECTION,
+ * include the first member of #DupliObject.persistent_id
+ * since its the index of the vertex/face the object is instantiated on and we want to identify
+ * objects on the same vertex/face.
+ * In other words, we consider each group of objects from a same item as being
+ * the 'local group' where to check for parents.
+ */
+static unsigned int dupliobject_hash(const void *ptr)
+{
+  const DupliObject *dob = ptr;
+  unsigned int hash = BLI_ghashutil_ptrhash(dob->ob);
+
+  if (dob->type == OB_DUPLICOLLECTION) {
+    for (int i = 1; (i < MAX_DUPLI_RECUR) && dob->persistent_id[i] != INT_MAX; i++) {
+      hash ^= (dob->persistent_id[i] ^ i);
+    }
+  }
+  else {
+    hash ^= (dob->persistent_id[0] ^ 0);
+  }
+  return hash;
+}
+
 /**
  * \note regarding hashing dupli-objects when using OB_DUPLICOLLECTION,
  * skip the first member of #DupliObject.persistent_id
  * since its a unique index and we only want to know if the group objects are from the same
  * dupli-group instance.
  */
-static unsigned int dupliobject_group_hash(const void *ptr)
+static unsigned int dupliobject_instancer_hash(const void *ptr)
 {
   const DupliObject *dob = ptr;
-  unsigned int hash = BLI_ghashutil_ptrhash(dob->ob);
-  unsigned int i;
-  for (i = 1; (i < MAX_DUPLI_RECUR) && dob->persistent_id[i] != INT_MAX; i++) {
+  unsigned int hash = BLI_ghashutil_inthash(dob->persistent_id[0]);
+  for (int i = 1; (i < MAX_DUPLI_RECUR) && dob->persistent_id[i] != INT_MAX; i++) {
     hash ^= (dob->persistent_id[i] ^ i);
   }
   return hash;
 }
 
-/**
- * \note regarding hashing dupli-objects when NOT using OB_DUPLICOLLECTION,
- * include the first member of #DupliObject.persistent_id
- * since its the index of the vertex/face the object is instantiated on and we want to identify
- * objects on the same vertex/face.
- */
-static unsigned int dupliobject_hash(const void *ptr)
-{
-  const DupliObject *dob = ptr;
-  unsigned int hash = BLI_ghashutil_ptrhash(dob->ob);
-  hash ^= (dob->persistent_id[0] ^ 0);
-  return hash;
-}
-
-/* Compare function that matches dupliobject_group_hash */
-static bool dupliobject_group_cmp(const void *a_, const void *b_)
-{
-  const DupliObject *a = a_;
-  const DupliObject *b = b_;
-  unsigned int i;
-
-  if (a->ob != b->ob) {
-    return true;
-  }
-
-  for (i = 1; (i < MAX_DUPLI_RECUR); i++) {
-    if (a->persistent_id[i] != b->persistent_id[i]) {
-      return true;
-    }
-    else if (a->persistent_id[i] == INT_MAX) {
-      break;
-    }
-  }
-
-  /* matching */
-  return false;
-}
-
 /* Compare function that matches dupliobject_hash */
 static bool dupliobject_cmp(const void *a_, const void *b_)
 {
@@ -1723,8 +1719,39 @@ static bool dupliobject_cmp(const void *a_, const void *b_)
     return true;
   }
 
-  if (a->persistent_id[0] != b->persistent_id[0]) {
-    return true;
+  if (ELEM(a->type, b->type, OB_DUPLICOLLECTION)) {
+    for (int i = 1; (i < MAX_DUPLI_RECUR); i++) {
+      if (a->persistent_id[i] != b->persistent_id[i]) {
+        return true;
+      }
+      else if (a->persistent_id[i] == INT_MAX) {
+        break;
+      }
+    }
+  }
+  else {
+    if (a->persistent_id[0] != b->persistent_id[0]) {
+      return true;
+    }
+  }
+
+  /* matching */
+  return false;
+}
+
+/* Compare function that matches dupliobject_instancer_hash. */
+static bool dupliobject_instancer_cmp(const void *a_, const void *b_)
+{
+  const DupliObject *a = a_;
+  const DupliObject *b = b_;
+
+  for (int i = 0; (i < MAX_DUPLI_RECUR); i++) {
+    if (a->persistent_id[i] != b->persistent_id[i]) {
+      return true;
+    }
+    else if (a->persistent_id[i] == INT_MAX) {
+      break;
+    }
   }
 
   /* matching */
@@ -1739,7 +1766,7 @@ static void make_object_duplilist_real(
   Depsgraph *depsgraph = CTX_data_depsgraph(C);
   ListBase *lb_duplis;
   DupliObject *dob;
-  GHash *dupli_gh, *parent_gh = NULL;
+  GHash *dupli_gh, *parent_gh = NULL, *instancer_gh = NULL;
 
   if (!(base->object->transflag & OB_DUPLI)) {
     return;
@@ -1750,11 +1777,11 @@ static void make_object_duplilist_real(
 
   dupli_gh = BLI_ghash_ptr_new(__func__);
   if (use_hierarchy) {
-    if (base->object->transflag & OB_DUPLICOLLECTION) {
-      parent_gh = BLI_ghash_new(dupliobject_group_hash, dupliobject_group_cmp, __func__);
-    }
-    else {
-      parent_gh = BLI_ghash_new(dupliobject_hash, dupliobject_cmp, __func__);
+    parent_gh = BLI_ghash_new(dupliobject_hash, dupliobject_cmp, __func__);
+
+    if (use_base_parent) {
+      instancer_gh = BLI_ghash_new(
+          dupliobject_instancer_hash, dupliobject_instancer_cmp, __func__);
     }
   }
 
@@ -1788,7 +1815,12 @@ static void make_object_duplilist_real(
     ob_dst->parent = NULL;
     BKE_constraints_free(&ob_dst->constraints);
     ob_dst->runtime.curve_cache = NULL;
+    const bool is_dupli_instancer = (ob_dst->transflag & OB_DUPLI) != 0;
     ob_dst->transflag &= ~OB_DUPLI;
+    /* Remove instantiated collection, it's annoying to keep it here
+     * (and get potentially a lot of usages of it then...). */
+    id_us_min((ID *)ob_dst->instance_collection);
+    ob_dst->instance_collection = NULL;
 
     copy_m4_m4(ob_dst->obmat, dob->mat);
     BKE_object_apply_mat4(ob_dst, ob_dst->obmat, false, false);
@@ -1802,6 +1834,13 @@ static void make_object_duplilist_real(
       if (!BLI_ghash_ensure_p(parent_gh, dob, &val)) {
         *val = ob_dst;
       }
+
+      if (is_dupli_instancer && instancer_gh) {
+        /* Same as above, we may have several 'hits'. */
+        if (!BLI_ghash_ensure_p(instancer_gh, dob, &val)) {
+          *val = ob_dst;
+        }
+      }
     }
   }
 
@@ -1825,7 +1864,8 @@ static void make_object_duplilist_real(
          * they won't be read, this is simply for a hash lookup. */
         DupliObject dob_key;
         dob_key.ob = ob_src_par;
-        if (base->object->transflag & OB_DUPLICOLLECTION) {
+        dob_key.type = dob->type;
+        if (dob->type == OB_DUPLICOLLECTION) {
           memcpy(&dob_key.persistent_id[1],
                  &dob->persistent_id[1],
                  sizeof(dob->persistent_id[1]) * (MAX_DUPLI_RECUR - 1));
@@ -1848,15 +1888,30 @@ static void make_object_duplilist_real(
 
         ob_dst->parent = ob_dst_par;
       }
-      else if (use_base_parent) {
-        ob_dst->parent = base->object;
-        ob_dst->partype = PAROBJECT;
-      }
     }
-    else if (use_base_parent) {
-      /* since we are ignoring the internal hierarchy - parent all to the
-       * base object */
-      ob_dst->parent = base->object;
+    if (use_base_parent && ob_dst->parent == NULL) {
+      Object *ob_dst_par = NULL;
+
+      if (instancer_gh != NULL) {
+        /* OK to keep most of the members uninitialized,
+         * they won't be read, this is simply for a hash lookup. */
+        DupliObject dob_key;
+        /* We are looking one step upper in hierarchy, so we need to 'shift' the persitent_id,
+         * ignoring the first item.
+         * We only check on persistent_id here, since we have no idea what object it might be. */
+        memcpy(&dob_key.persistent_id[0],
+               &dob->persistent_id[1],
+               sizeof(dob_key.persistent_id[0]) * (MAX_DUPLI_RECUR - 1));
+        ob_dst_par = BLI_ghash_lookup(instancer_gh, &dob_key);
+      }
+
+      if (ob_dst_par == NULL) {
+        /* Default to parenting to root object...
+         * Always the case when use_hierarchy is false. */
+        ob_dst_par = base->object;
+      }
+
+      ob_dst->parent = ob_dst_par;
       ob_dst->partype = PAROBJECT;
     }
 
@@ -1885,6 +1940,9 @@ static void make_object_duplilist_real(
   if (parent_gh) {
     BLI_ghash_free(parent_gh, NULL, NULL);
   }
+  if (instancer_gh) {
+    BLI_ghash_free(instancer_gh, NULL, NULL);
+  }
 
   free_object_duplilist(lb_duplis);