introduce workspace_squash

workspace_squash is container_flatten in the reverse
direction. Instead of eliminating redundant splits that are
parents of the target container, it eliminates pairs of
redundant H/V splits that are children of the workspace.

Splits are redundant if a con and its grandchild have the
same layout, and the immediate child has the opposite split.

For example, layouts are transformed like:

    H[V[H[app1 app2]] app3] -> H[app1 app2 app3]

i3 uses this operation to simplify the tree after moving
heavily nested containers to a higher level in the tree via
an orthogonal move.

4 files changed, 109 insertions, 7 deletions

diff --git a/include/sway/tree/container.h b/include/sway/tree/container.h
index c9290108..7e9df59f 100644
--- a/include/sway/tree/container.h
+++ b/include/sway/tree/container.h
@@ -374,4 +374,17 @@ bool container_is_sticky(struct sway_container *con);
 
 bool container_is_sticky_or_child(struct sway_container *con);
 
+/**
+ * This will destroy pairs of redundant H/V splits
+ * e.g. H[V[H[app app]] app] -> H[app app app]
+ * The middle "V[H[" are eliminated by a call to container_squash
+ * on the V[ con. It's grandchildren are added to it's parent.
+ *
+ * This function is roughly equivalent to i3's tree_flatten here:
+ * https://github.com/i3/i3/blob/1f0c628cde40cf87371481041b7197344e0417c6/src/tree.c#L651
+ *
+ * Returns the number of new containers added to the parent
+ */
+int container_squash(struct sway_container *con);
+
 #endif
diff --git a/include/sway/tree/workspace.h b/include/sway/tree/workspace.h
index 3c9f93ed..fdd92f64 100644
--- a/include/sway/tree/workspace.h
+++ b/include/sway/tree/workspace.h
@@ -116,6 +116,13 @@ struct sway_container *workspace_add_tiling(struct sway_workspace *workspace,
 void workspace_add_floating(struct sway_workspace *workspace,
 		struct sway_container *con);
 
+/**
+ * Adds a tiling container to the workspace without considering
+ * the workspace_layout, so the con will not be split.
+ */
+void workspace_insert_tiling_direct(struct sway_workspace *workspace,
+		struct sway_container *con, int index);
+
 struct sway_container *workspace_insert_tiling(struct sway_workspace *workspace,
 		struct sway_container *con, int index);
 
@@ -134,4 +141,12 @@ size_t workspace_num_tiling_views(struct sway_workspace *ws);
 
 size_t workspace_num_sticky_containers(struct sway_workspace *ws);
 
+/**
+ * workspace_squash is container_flatten in the reverse
+ * direction. Instead of eliminating redundant splits that are
+ * parents of the target container, it eliminates pairs of
+ * redundant H/V splits that are children of the workspace.
+ */
+void workspace_squash(struct sway_workspace *workspace);
+
 #endif
diff --git a/sway/tree/container.c b/sway/tree/container.c
index 23b6c997..4c573e83 100644
--- a/sway/tree/container.c
+++ b/sway/tree/container.c
@@ -1630,3 +1630,65 @@ bool container_is_sticky(struct sway_container *con) {
 bool container_is_sticky_or_child(struct sway_container *con) {
 	return container_is_sticky(container_toplevel_ancestor(con));
 }
+
+static bool is_parallel(enum sway_container_layout first,
+		enum sway_container_layout second) {
+	switch (first) {
+	case L_TABBED:
+	case L_HORIZ:
+		return second == L_TABBED || second == L_HORIZ;
+	case L_STACKED:
+	case L_VERT:
+		return second == L_STACKED || second == L_VERT;
+	default:
+		return false;
+	}
+}
+
+static bool container_is_squashable(struct sway_container *con,
+		struct sway_container *child) {
+	enum sway_container_layout gp_layout = container_parent_layout(con);
+	return (con->layout == L_HORIZ || con->layout == L_VERT) &&
+		(child->layout == L_HORIZ || child->layout == L_VERT) &&
+		!is_parallel(con->layout, child->layout) &&
+		is_parallel(gp_layout, child->layout);
+}
+
+static void container_squash_children(struct sway_container *con) {
+	for (int i = 0; i < con->children->length; i++) {
+		struct sway_container *child = con->children->items[i];
+		i += container_squash(child);
+	}
+}
+
+int container_squash(struct sway_container *con) {
+	if (!con->children) {
+		return 0;
+	}
+	if (con->children->length != 1) {
+		container_squash_children(con);
+		return 0;
+	}
+	struct sway_container *child = con->children->items[0];
+	int idx = container_sibling_index(con);
+	int change = 0;
+	if (container_is_squashable(con, child)) {
+		// con and child are a redundant H/V pair. Destroy them.
+		while (child->children->length) {
+			struct sway_container *current = child->children->items[0];
+			container_detach(current);
+			if (con->parent) {
+				container_insert_child(con->parent, current, idx);
+			} else {
+				workspace_insert_tiling_direct(con->workspace, current, idx);
+			}
+			change++;
+		}
+		// This will also destroy con because child was its only child
+		container_reap_empty(child);
+		change--;
+	} else {
+		container_squash_children(con);
+	}
+	return change;
+}
diff --git a/sway/tree/workspace.c b/sway/tree/workspace.c
index e40792ae..62549434 100644
--- a/sway/tree/workspace.c
+++ b/sway/tree/workspace.c
@@ -714,14 +714,8 @@ void workspace_add_floating(struct sway_workspace *workspace,
 	node_set_dirty(&con->node);
 }
 
-struct sway_container *workspace_insert_tiling(struct sway_workspace *workspace,
+void workspace_insert_tiling_direct(struct sway_workspace *workspace,
 		struct sway_container *con, int index) {
-	if (con->workspace) {
-		container_detach(con);
-	}
-	if (config->default_layout != L_NONE) {
-		con = container_split(con, config->default_layout);
-	}
 	list_insert(workspace->tiling, index, con);
 	con->workspace = workspace;
 	container_for_each_child(con, set_workspace, NULL);
@@ -729,6 +723,17 @@ struct sway_container *workspace_insert_tiling(struct sway_workspace *workspace,
 	workspace_update_representation(workspace);
 	node_set_dirty(&workspace->node);
 	node_set_dirty(&con->node);
+}
+
+struct sway_container *workspace_insert_tiling(struct sway_workspace *workspace,
+		struct sway_container *con, int index) {
+	if (con->workspace) {
+		container_detach(con);
+	}
+	if (config->default_layout != L_NONE) {
+		con = container_split(con, config->default_layout);
+	}
+	workspace_insert_tiling_direct(workspace, con, index);
 	return con;
 }
 
@@ -846,3 +851,10 @@ size_t workspace_num_sticky_containers(struct sway_workspace *ws) {
 	workspace_for_each_container(ws, count_sticky_containers, &count);
 	return count;
 }
+
+void workspace_squash(struct sway_workspace *workspace) {
+	for (int i = 0; i < workspace->tiling->length; i++) {
+		struct sway_container *child = workspace->tiling->items[i];
+		i += container_squash(child);
+	}
+}