Outliner: Delete all selected collections, not just active one

There were some issues with how we store outliner tree elements:
Apparently the only removable elements have been data-blocks so far.
When recreating the TreeElements, their TreeStoreElem instances were
mainly identified by their ID pointer. However non-data-blocks mostly
depend on an index. For collections, such an index isn't a reliable
measure though if we want to allow removing items. Depending on it for
identifying the TreeStoreElem instance would cause some quite noticeable
glitches (wrong highlights, two elements sharing highlight, etc).

For now I've solved that by actually removing the TreeStoreElem that
represents the removed element. A little limitation of this is that
after undoing the removal, some information might get lost, like
flags to store selection, or opened/closed state.
A better solution that would also fix this issue would be having a real
unique identifier for each non-data-block element, like an idname or even
its data-pointer. Not sure if we can get those to work reliable with
file read/write though, would have to investigate...

Also added a general Outliner tree traversal utility.

8 files changed, 155 insertions, 37 deletions

diff --git a/source/blender/blenkernel/BKE_outliner_treehash.h b/source/blender/blenkernel/BKE_outliner_treehash.h
index 454edb40c4e..b82bc692402 100644
--- a/source/blender/blenkernel/BKE_outliner_treehash.h
+++ b/source/blender/blenkernel/BKE_outliner_treehash.h
@@ -36,8 +36,9 @@ void *BKE_outliner_treehash_create_from_treestore(struct BLI_mempool *treestore)
 /* full rebuild for already allocated hashtable */
 void *BKE_outliner_treehash_rebuild_from_treestore(void *treehash, struct BLI_mempool *treestore);
 
-/* full rebuild for already allocated hashtable */
+/* Add/remove hashtable elements */
 void BKE_outliner_treehash_add_element(void *treehash, struct TreeStoreElem *elem);
+void BKE_outliner_treehash_remove_element(void *treehash, struct TreeStoreElem *elem);
 
 /* find first unused element with specific type, nr and id */
 struct TreeStoreElem *BKE_outliner_treehash_lookup_unused(void *treehash, short type, short nr, struct ID *id);
diff --git a/source/blender/blenkernel/intern/outliner_treehash.c b/source/blender/blenkernel/intern/outliner_treehash.c
index f31ba34a984..3e99dbe37ca 100644
--- a/source/blender/blenkernel/intern/outliner_treehash.c
+++ b/source/blender/blenkernel/intern/outliner_treehash.c
@@ -27,6 +27,7 @@
  */
 
 #include <stdlib.h>
+#include <string.h>
 
 #include "BKE_outliner_treehash.h"
 
@@ -56,7 +57,7 @@ static TseGroup *tse_group_create(void)
 	return tse_group;
 }
 
-static void tse_group_add(TseGroup *tse_group, TreeStoreElem *elem)
+static void tse_group_add_element(TseGroup *tse_group, TreeStoreElem *elem)
 {
 	if (UNLIKELY(tse_group->size == tse_group->allocated)) {
 		tse_group->allocated *= 2;
@@ -66,6 +67,26 @@ static void tse_group_add(TseGroup *tse_group, TreeStoreElem *elem)
 	tse_group->size++;
 }
 
+static void tse_group_remove_element(TseGroup *tse_group, TreeStoreElem *elem)
+{
+	int min_allocated = MAX2(1, tse_group->allocated / 2);
+	BLI_assert(tse_group->allocated == 1 || (tse_group->allocated % 2) == 0);
+
+	tse_group->size--;
+	BLI_assert(tse_group->size >= 0);
+	for (int i = 0; i < tse_group->size; i++) {
+		if (tse_group->elems[i] == elem) {
+			memcpy(tse_group->elems[i], tse_group->elems[i + 1], (tse_group->size - (i + 1)) * sizeof(TreeStoreElem *));
+			break;
+		}
+	}
+
+	if (UNLIKELY(tse_group->size > 0 && tse_group->size <= min_allocated)) {
+		tse_group->allocated = min_allocated;
+		tse_group->elems = MEM_reallocN(tse_group->elems, sizeof(TreeStoreElem *) * tse_group->allocated);
+	}
+}
+
 static void tse_group_free(TseGroup *tse_group)
 {
 	MEM_freeN(tse_group->elems);
@@ -140,7 +161,21 @@ void BKE_outliner_treehash_add_element(void *treehash, TreeStoreElem *elem)
 		*val_p = tse_group_create();
 	}
 	group = *val_p;
-	tse_group_add(group, elem);
+	tse_group_add_element(group, elem);
+}
+
+void BKE_outliner_treehash_remove_element(void *treehash, TreeStoreElem *elem)
+{
+	TseGroup *group = BLI_ghash_lookup(treehash, elem);
+
+	BLI_assert(group != NULL);
+	if (group->size <= 1) {
+		/* one element -> remove group completely */
+		BLI_ghash_remove(treehash, elem, NULL, free_treehash_group);
+	}
+	else {
+		tse_group_remove_element(group, elem);
+	}
 }
 
 static TseGroup *BKE_outliner_treehash_lookup_group(GHash *th, short type, short nr, struct ID *id)
diff --git a/source/blender/blenloader/intern/versioning_280.c b/source/blender/blenloader/intern/versioning_280.c
index 9d575c8f6d2..f63d20f3a37 100644
--- a/source/blender/blenloader/intern/versioning_280.c
+++ b/source/blender/blenloader/intern/versioning_280.c
@@ -32,6 +32,7 @@
 #include "DNA_layer_types.h"
 #include "DNA_material_types.h"
 #include "DNA_scene_types.h"
+#include "DNA_screen_types.h"
 #include "DNA_genfile.h"
 
 #include "BKE_collection.h"
diff --git a/source/blender/editors/space_outliner/outliner_collections.c b/source/blender/editors/space_outliner/outliner_collections.c
index cf63e17870f..889fb6dd36f 100644
--- a/source/blender/editors/space_outliner/outliner_collections.c
+++ b/source/blender/editors/space_outliner/outliner_collections.c
@@ -54,12 +54,14 @@ static LayerCollection *outliner_collection_active(bContext *C)
 	return CTX_data_layer_collection(C);
 }
 
+#if 0
 static CollectionOverride *outliner_override_active(bContext *UNUSED(C))
 {
 	TODO_LAYER_OPERATORS;
 	TODO_LAYER_OVERRIDE;
 	return NULL;
 }
+#endif
 
 /* -------------------------------------------------------------------- */
 /* collection manager operators */
@@ -283,55 +285,61 @@ void OUTLINER_OT_collection_override_new(wmOperatorType *ot)
 	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
 }
 
-/**
- * Returns true if selected element is a collection
- * or an override, but not a master collection
- */
-static int collection_delete_poll(bContext *C)
+struct CollectionDeleteData {
+	Scene *scene;
+	SpaceOops *soops;
+};
+
+static TreeTraversalReturn collection_delete_cb(TreeElement *te, void *customdata)
 {
-	LayerCollection *lc = outliner_collection_active(C);
+	struct CollectionDeleteData *data = customdata;
+	TreeStoreElem *tselem = TREESTORE(te);
+	LayerCollection *lc = te->directdata;
 
-	if (lc == NULL) {
-		/* try override */
-		return outliner_override_active(C) ? 1 : 0;
+	if (tselem->type != TSE_LAYER_COLLECTION) {
+		/* skip */
+	}
+	else if (lc->scene_collection == BKE_collection_master(data->scene)) {
+		/* skip - showing warning/error message might be missleading
+		 * when deleting multiple collections, so just do nothing */
+	}
+	else {
+		/* XXX removing the treestore element shouldn't be done, it makes us loose information after
+		 * undo/file-read. We do need it here however, because non-ID elements don't have an ID pointer
+		 * that can be used to lookup the TreeStoreElem when recreating the TreeElement. This index
+		 * won't be correct after removing a collection from the list though.
+		 * This works as workaround, but having a proper way to find the TreeStoreElem for a recreated
+		 * TreeElement would be better. It could use an idname or the directdata pointer for that. */
+		outliner_remove_treestore_element(data->soops, tselem);
+		BKE_collection_remove(data->scene, lc->scene_collection);
 	}
 
-	return  (lc->scene_collection == BKE_collection_master(CTX_data_scene(C))) ? 0 : 1;
+	return TRAVERSE_CONTINUE;
 }
 
-static int collection_delete_exec(bContext *C, wmOperator *op)
+static int collection_delete_exec(bContext *C, wmOperator *UNUSED(op))
 {
 	Scene *scene = CTX_data_scene(C);
-	LayerCollection *lc = outliner_collection_active(C);
+	SpaceOops *soops = CTX_wm_space_outliner(C);
+	struct CollectionDeleteData data = {.scene = scene, .soops = soops};
 
 	TODO_LAYER_OVERRIDE; /* handle operators */
-
-	if (lc == NULL) {
-		BKE_report(op->reports, RPT_ERROR, "Active element is not a collection");
-		return OPERATOR_CANCELLED;
-	}
-
-	if (lc->scene_collection == BKE_collection_master(scene)) {
-		BKE_report(op->reports, RPT_ERROR, "You cannot delete the master collection, try unliking it instead");
-		return OPERATOR_CANCELLED;
-	}
-
-	BKE_collection_remove(scene, lc->scene_collection);
+	outliner_tree_traverse(soops, &soops->tree, 0, TSE_SELECTED, collection_delete_cb, &data);
 
 	WM_main_add_notifier(NC_SCENE | ND_LAYER, NULL);
+
 	return OPERATOR_FINISHED;
 }
 
-void OUTLINER_OT_collection_delete(wmOperatorType *ot)
+void OUTLINER_OT_collections_delete(wmOperatorType *ot)
 {
 	/* identifiers */
 	ot->name = "Delete";
-	ot->idname = "OUTLINER_OT_collection_delete";
-	ot->description = "Delete active override or collection";
+	ot->idname = "OUTLINER_OT_collections_delete";
+	ot->description = "Delete selected overrides or collections";
 
 	/* api callbacks */
 	ot->exec = collection_delete_exec;
-	ot->poll = collection_delete_poll;
 
 	/* flags */
 	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
diff --git a/source/blender/editors/space_outliner/outliner_edit.c b/source/blender/editors/space_outliner/outliner_edit.c
index 7d801318c33..2ab506ea746 100644
--- a/source/blender/editors/space_outliner/outliner_edit.c
+++ b/source/blender/editors/space_outliner/outliner_edit.c
@@ -198,6 +198,50 @@ TreeElement *outliner_find_item_at_x_in_row(const SpaceOops *soops, const TreeEl
 	return (TreeElement *)parent_te;
 }
 
+/**
+ * Iterate over all tree elements (pre-order traversal), executing \a func callback for
+ * each tree element matching the optional filters.
+ *
+ * \param filter_te_flag: If not 0, only TreeElements with this flag will be visited.
+ * \param filter_tselem_flag: Same as \a filter_te_flag, but for the TreeStoreElem.
+ * \param func: Custom callback to execute for each visited item.
+ */
+bool outliner_tree_traverse(const SpaceOops *soops, ListBase *tree, int filter_te_flag, int filter_tselem_flag,
+                            TreeTraversalFunc func, void *customdata)
+{
+	for (TreeElement *te = tree->first, *te_next; te; te = te_next) {
+		TreeTraversalReturn func_retval = TRAVERSE_CONTINUE;
+		/* in case te is freed in callback */
+		TreeStoreElem *tselem = TREESTORE(te);
+		ListBase subtree = te->subtree;
+		te_next = te->next;
+
+		if (filter_te_flag && (te->flag & filter_te_flag) == 0) {
+			/* skip */
+		}
+		else if (filter_tselem_flag && (tselem->flag & filter_tselem_flag) == 0) {
+			/* skip */
+		}
+		else {
+			func_retval = func(te, customdata);
+		}
+		/* Don't access te or tselem from now on! Might've been freed... */
+
+		if (func_retval == TRAVERSE_BREAK) {
+			return false;
+		}
+
+		if (func_retval == TRAVERSE_SKIP_CHILDS) {
+			/* skip */
+		}
+		else if (!outliner_tree_traverse(soops, &subtree, filter_te_flag, filter_tselem_flag, func, customdata)) {
+			return false;
+		}
+	}
+
+	return true;
+}
+
 
 /* ************************************************************** */
 
diff --git a/source/blender/editors/space_outliner/outliner_intern.h b/source/blender/editors/space_outliner/outliner_intern.h
index 6a4d53449e9..6787146fc46 100644
--- a/source/blender/editors/space_outliner/outliner_intern.h
+++ b/source/blender/editors/space_outliner/outliner_intern.h
@@ -47,12 +47,24 @@ struct Object;
 struct bPoseChannel;
 struct EditBone;
 
+
+typedef enum TreeTraversalReturn {
+	/* Continue traversal regularly, don't skip children. */
+	TRAVERSE_CONTINUE = 0,
+	/* Stop traversal */
+	TRAVERSE_BREAK,
+	/* Continue traversal, but skip childs of traversed element */
+	TRAVERSE_SKIP_CHILDS,
+} TreeTraversalReturn;
+
 /**
  * Callback type for reinserting elements at a different position, used to allow user customizable element order.
  * Passing scene right now, may be better to allow some custom data.
  */
 typedef void (*TreeElementReinsertFunc)(const struct Scene *scene, struct TreeElement *insert_element,
                                         struct TreeElement *insert_after);
+typedef TreeTraversalReturn (*TreeTraversalFunc)(struct TreeElement *te, void *customdata);
+
 
 typedef struct TreeElement {
 	struct TreeElement *next, *prev, *parent;
@@ -150,6 +162,7 @@ typedef enum {
 
 void outliner_free_tree(ListBase *lb);
 void outliner_cleanup_tree(struct SpaceOops *soops);
+void outliner_remove_treestore_element(struct SpaceOops *soops, TreeStoreElem *tselem);
 
 TreeElement *outliner_find_tse(struct SpaceOops *soops, const TreeStoreElem *tse);
 TreeElement *outliner_find_tree_element(ListBase *lb, const TreeStoreElem *store_elem);
@@ -233,6 +246,9 @@ TreeElement *outliner_dropzone_find(const struct SpaceOops *soops, const float f
 TreeElement *outliner_find_item_at_y(const SpaceOops *soops, const ListBase *tree, float view_co_y);
 TreeElement *outliner_find_item_at_x_in_row(const SpaceOops *soops, const TreeElement *parent_te, float view_co_x);
 
+bool outliner_tree_traverse(const SpaceOops *soops, ListBase *tree, int filter_te_flag, int filter_tselem_flag,
+                            TreeTraversalFunc func, void *customdata);
+
 /* ...................................................... */
 
 void OUTLINER_OT_highlight_update(struct wmOperatorType *ot);
@@ -293,7 +309,7 @@ void outliner_keymap(struct wmKeyConfig *keyconf);
 
 /* outliner_collections.c */
 
-void OUTLINER_OT_collection_delete(struct wmOperatorType *ot);
+void OUTLINER_OT_collections_delete(struct wmOperatorType *ot);
 void OUTLINER_OT_collection_select(struct wmOperatorType *ot);
 void OUTLINER_OT_collection_link(struct wmOperatorType *ot);
 void OUTLINER_OT_collection_unlink(struct wmOperatorType *ot);
diff --git a/source/blender/editors/space_outliner/outliner_ops.c b/source/blender/editors/space_outliner/outliner_ops.c
index 459095b830e..5187cc66f58 100644
--- a/source/blender/editors/space_outliner/outliner_ops.c
+++ b/source/blender/editors/space_outliner/outliner_ops.c
@@ -268,7 +268,7 @@ void outliner_operatortypes(void)
 	WM_operatortype_append(OUTLINER_OT_group_link);
 
 	/* collections */
-	WM_operatortype_append(OUTLINER_OT_collection_delete);
+	WM_operatortype_append(OUTLINER_OT_collections_delete);
 	WM_operatortype_append(OUTLINER_OT_collection_select);
 	WM_operatortype_append(OUTLINER_OT_collection_link);
 	WM_operatortype_append(OUTLINER_OT_collection_unlink);
diff --git a/source/blender/editors/space_outliner/outliner_tree.c b/source/blender/editors/space_outliner/outliner_tree.c
index b0b99692405..7fb6eacb731 100644
--- a/source/blender/editors/space_outliner/outliner_tree.c
+++ b/source/blender/editors/space_outliner/outliner_tree.c
@@ -1240,6 +1240,15 @@ static TreeElement *outliner_add_element(SpaceOops *soops, ListBase *lb, void *i
 	return te;
 }
 
+/**
+ * \note Really only removes \a tselem, not it's TreeElement instance or any children.
+ */
+void outliner_remove_treestore_element(SpaceOops *soops, TreeStoreElem *tselem)
+{
+	BKE_outliner_treehash_remove_element(soops->treehash, tselem);
+	BLI_mempool_free(soops->treestore, tselem);
+}
+
 /* ======================================================= */
 /* Sequencer mode tree building */
 
@@ -1387,10 +1396,12 @@ static void outliner_collections_reorder(const Scene *scene, TreeElement *insert
 }
 
 static void outliner_add_layer_collections_recursive(SpaceOops *soops, ListBase *tree, Scene *scene,
-                                                     ListBase *layer_collections, TreeElement *parent_ten)
+                                                     ListBase *layer_collections, TreeElement *parent_ten,
+                                                     int *io_collection_counter)
 {
 	for (LayerCollection *collection = layer_collections->first; collection; collection = collection->next) {
-		TreeElement *ten = outliner_add_element(soops, tree, scene, parent_ten, TSE_LAYER_COLLECTION, 0);
+		TreeElement *ten = outliner_add_element(soops, tree, scene, parent_ten, TSE_LAYER_COLLECTION,
+		                                        (*io_collection_counter)++);
 
 		ten->name = collection->scene_collection->name;
 		ten->directdata = collection;
@@ -1401,12 +1412,14 @@ static void outliner_add_layer_collections_recursive(SpaceOops *soops, ListBase
 		}
 		outliner_make_hierarchy(&ten->subtree);
 
-		outliner_add_layer_collections_recursive(soops, &ten->subtree, scene, &collection->layer_collections, ten);
+		outliner_add_layer_collections_recursive(soops, &ten->subtree, scene, &collection->layer_collections, ten,
+		                                         io_collection_counter);
 	}
 }
 static void outliner_add_collections_act_layer(SpaceOops *soops, SceneLayer *layer, Scene *scene)
 {
-	outliner_add_layer_collections_recursive(soops, &soops->tree, scene, &layer->layer_collections, NULL);
+	int collection_counter = 0;
+	outliner_add_layer_collections_recursive(soops, &soops->tree, scene, &layer->layer_collections, NULL, &collection_counter);
 }
 
 static void outliner_add_scene_collection_init(TreeElement *te, SceneCollection *collection)