UI: Support drag & drop reordering of collections

This adds initial support for reordering collections from the Outliner
using drag & drop.
Although drag & drop support is limited to collections for now, this
lays most foundations for general drag & drop reordering support in the
Outliner. There are some design questions to be answered though:
* Would reordering of other data types (like objects) be a purely visual change or would it affect the order in which they are stored? (Would that make a difference for the user?)
* Should/can we allow mixing of different data types? (e.g. mixing render layers with objects)
* How could we realize this technically?

Notes:
* "Sort Alphabetically" has to be disabled to use this ("View" menu).
* Reordering only works with collections on the same hierarchy level.
* Added some visual feedback that should work quite well, it's by far not a final design though: {F493806}
* Modified collection orders are stored in .blends.
* Reordering can be undone.
* Did minor cleanups here and there.

4 files changed, 101 insertions, 5 deletions

diff --git a/source/blender/blenkernel/BKE_collection.h b/source/blender/blenkernel/BKE_collection.h
index 4d5de723dce..644bcef6226 100644
--- a/source/blender/blenkernel/BKE_collection.h
+++ b/source/blender/blenkernel/BKE_collection.h
@@ -44,7 +44,7 @@ struct Scene;
 
 struct SceneCollection *BKE_collection_add(struct Scene *scene, struct SceneCollection *sc_parent, const char *name);
 bool BKE_collection_remove(struct Scene *scene, struct SceneCollection *sc);
-struct SceneCollection *BKE_collection_master(struct Scene *scene);
+struct SceneCollection *BKE_collection_master(const struct Scene *scene);
 void BKE_collection_master_free(struct Scene *scene);
 void BKE_collection_object_add(struct Scene *scene, struct SceneCollection *sc, struct Object *object);
 void BKE_collection_object_add_from(struct Scene *scene, struct Object *ob_src, struct Object *ob_dst);
diff --git a/source/blender/blenkernel/BKE_layer.h b/source/blender/blenkernel/BKE_layer.h
index 641cc969e71..d208cee5b4b 100644
--- a/source/blender/blenkernel/BKE_layer.h
+++ b/source/blender/blenkernel/BKE_layer.h
@@ -54,7 +54,7 @@ struct Scene;
 struct SceneCollection;
 struct SceneLayer;
 
-struct SceneLayer *BKE_scene_layer_render_active(struct Scene *scene);
+struct SceneLayer *BKE_scene_layer_render_active(const struct Scene *scene);
 struct SceneLayer *BKE_scene_layer_context_active(struct Scene *scene);
 struct SceneLayer *BKE_scene_layer_add(struct Scene *scene, const char *name);
 
@@ -84,6 +84,8 @@ struct LayerCollection *BKE_layer_collection_active(struct SceneLayer *sl);
 int BKE_layer_collection_count(struct SceneLayer *sl);
 
 int BKE_layer_collection_findindex(struct SceneLayer *sl, struct LayerCollection *lc);
+void BKE_layer_collection_reinsert_after(const struct Scene *scene, struct SceneLayer *sl,
+                                         struct LayerCollection *lc_reinsert, struct LayerCollection *lc_after);
 
 struct LayerCollection *BKE_collection_link(struct SceneLayer *sl, struct SceneCollection *sc);
 
diff --git a/source/blender/blenkernel/intern/collection.c b/source/blender/blenkernel/intern/collection.c
index 100cbf2dd45..24f97c00afb 100644
--- a/source/blender/blenkernel/intern/collection.c
+++ b/source/blender/blenkernel/intern/collection.c
@@ -44,6 +44,9 @@
 
 #include "MEM_guardedalloc.h"
 
+bool collection_remlink(SceneCollection *, SceneCollection *);
+bool collection_insert_after(SceneCollection *, SceneCollection *, SceneCollection *);
+
 /**
  * Add a collection to a collection ListBase and syncronize all render layers
  * The ListBase is NULL when the collection is to be added to the master collection
@@ -95,7 +98,7 @@ static void collection_free(SceneCollection *sc)
  * Unlink the collection recursively
  * return true if unlinked
  */
-static bool collection_remlink(SceneCollection *sc_parent, SceneCollection *sc_gone)
+bool collection_remlink(SceneCollection *sc_parent, SceneCollection *sc_gone)
 {
 	for (SceneCollection *sc = sc_parent->scene_collections.first; sc; sc = sc->next)
 	{
@@ -174,9 +177,35 @@ bool BKE_collection_remove(Scene *scene, SceneCollection *sc)
 }
 
 /**
+ * Lookup the parent listbase of \a sc_insert_after and insert \a sc_insert after it.
+ * \param sc_after: If this is NULL, \a sc_insert will be inserted as first collection in \a parent.
+ */
+bool collection_insert_after(
+        SceneCollection *parent, SceneCollection *sc_insert, SceneCollection *sc_after)
+{
+	if (sc_after == NULL) {
+		BLI_addhead(&parent->scene_collections, sc_insert);
+		return true;
+	}
+
+	for (SceneCollection *sc = parent->scene_collections.first; sc; sc = sc->next) {
+		if (sc == sc_after) {
+			BLI_insertlinkafter(&parent->scene_collections, sc_after, sc_insert);
+			return true;
+		}
+
+		if (collection_insert_after(sc, sc_insert, sc_after)) {
+			return true;
+		}
+	}
+
+	return false;
+}
+
+/**
  * Returns the master collection
  */
-SceneCollection *BKE_collection_master(Scene *scene)
+SceneCollection *BKE_collection_master(const Scene *scene)
 {
 	return scene->collection;
 }
diff --git a/source/blender/blenkernel/intern/layer.c b/source/blender/blenkernel/intern/layer.c
index 621ac51aba3..3653a9ac651 100644
--- a/source/blender/blenkernel/intern/layer.c
+++ b/source/blender/blenkernel/intern/layer.c
@@ -66,7 +66,7 @@ static void object_bases_Iterator_next(Iterator *iter, const int flag);
  * Returns the SceneLayer to be used for rendering
  * Most of the time BKE_scene_layer_context_active should be used instead
  */
-SceneLayer *BKE_scene_layer_render_active(Scene *scene)
+SceneLayer *BKE_scene_layer_render_active(const Scene *scene)
 {
 	SceneLayer *sl = BLI_findlink(&scene->render_layers, scene->active_layer);
 	BLI_assert(sl);
@@ -492,6 +492,71 @@ int BKE_layer_collection_findindex(SceneLayer *sl, LayerCollection *lc)
 }
 
 /**
+ * \param lc_after: Can be NULL to insert \a lc_after as first collection in \a lb.
+ */
+static bool layer_collection_insert_after(ListBase *lb, LayerCollection *lc_insert, LayerCollection *lc_after)
+{
+	if (lc_after == NULL) {
+		BLI_addhead(lb, lc_insert);
+		return true;
+	}
+
+	for (LayerCollection *lc = lb->first; lc; lc = lc->next) {
+		if (lc == lc_after) {
+			BLI_insertlinkafter(lb, lc_after, lc_insert);
+			return true;
+		}
+
+		if (layer_collection_insert_after(&lc->layer_collections, lc_insert, lc_after)) {
+			return true;
+		}
+	}
+
+	return false;
+}
+
+static bool layer_collection_remlink(ListBase *lb, LayerCollection *lc)
+{
+	for (LayerCollection *lc_iter = lb->first; lc_iter; lc_iter = lc_iter->next) {
+		if (lc_iter == lc) {
+			BLI_remlink(lb, lc);
+			return true;
+		}
+
+		if (layer_collection_remlink(&lc_iter->layer_collections, lc)) {
+			return true;
+		}
+	}
+
+	return false;
+}
+
+/**
+ * Move \a lc_reinsert so that it follows \a lc_after. After this, both \a lc_reinsert
+ * and \a lc_after should be stored in the same list.
+ *
+ * \param lc_after: Can be NULL to insert \a lc_after as first collection in \a sl.
+ */
+void BKE_layer_collection_reinsert_after(
+        const Scene *scene, SceneLayer *sl, LayerCollection *lc_reinsert, LayerCollection *lc_after)
+{
+	/* XXX maybe worth having a BKE internal header file for this? */
+	extern bool collection_remlink(SceneCollection *, SceneCollection *);
+	extern bool collection_insert_after(SceneCollection *, SceneCollection *, SceneCollection *);
+
+	SceneCollection *sc_master = BKE_collection_master(scene);
+
+	layer_collection_remlink(&sl->layer_collections, lc_reinsert);
+	collection_remlink(sc_master, lc_reinsert->scene_collection);
+
+	layer_collection_insert_after(&sl->layer_collections, lc_reinsert, lc_after);
+	collection_insert_after(sc_master, lc_reinsert->scene_collection, lc_after ? lc_after->scene_collection : NULL);
+
+	BKE_scene_layer_base_flag_recalculate(sl);
+	BKE_scene_layer_engine_settings_collection_recalculate(sl, lc_reinsert);
+}
+
+/**
  * Link a collection to a renderlayer
  * The collection needs to be created separately
  */