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);
+        }
+}