Implement iterators per container type

This introduces the following `for_each` functions:

* root_for_each_workspace
* root_for_each_container
* output_for_each_workspace
* output_for_each_container
* workspace_for_each_container

And introduces the following `find` functions:

* root_find_output
* root_find_workspace
* root_find_container
* output_find_workspace
* output_find_container
* workspace_find_container
* container_find_child

And removes the following functions:

* container_descendants
* container_for_each_descendant
* container_find

This change is preparing the way for demoting sway_container. Eventually
these functions will accept and return sway_outputs, sway_workspaces and
sway_containers (meaning a C_CONTAINER or C_VIEW).

This change also makes it easy to handle abnormalities like the
workspace floating list, root's scratchpad list and (once implemented)
root's saved workspaces list for when there's no connected outputs.

5 files changed, 215 insertions, 54 deletions

diff --git a/sway/tree/container.c b/sway/tree/container.c
index 337245fd..1ceae175 100644
--- a/sway/tree/container.c
+++ b/sway/tree/container.c
@@ -432,8 +432,10 @@ struct sway_container *container_close(struct sway_container *con) {
 
         if (con->type == C_VIEW) {
                 view_close(con->sway_view);
-        } else {
-                container_for_each_descendant(con, container_close_func, NULL);
+        } else if (con->type == C_CONTAINER) {
+                container_for_each_child(con, container_close_func, NULL);
+        } else if (con->type == C_WORKSPACE) {
+                workspace_for_each_container(con, container_close_func, NULL);
         }
 
         return parent;
@@ -465,23 +467,12 @@ struct sway_container *container_view_create(struct sway_container *sibling,
         return swayc;
 }
 
-void container_descendants(struct sway_container *root,
-                enum sway_container_type type,
-                void (*func)(struct sway_container *item, void *data), void *data) {
-        if (!root->children || !root->children->length) {
-                return;
-        }
-        for (int i = 0; i < root->children->length; ++i) {
-                struct sway_container *item = root->children->items[i];
-                if (item->type == type) {
-                        func(item, data);
-                }
-                container_descendants(item, type, func, data);
-        }
-}
-
-struct sway_container *container_find(struct sway_container *container,
+struct sway_container *container_find_child(struct sway_container *container,
                 bool (*test)(struct sway_container *view, void *data), void *data) {
+        if (!sway_assert(container->type == C_CONTAINER ||
+                                container->type == C_VIEW, "Expected a container or view")) {
+                return NULL;
+        }
         if (!container->children) {
                 return NULL;
         }
@@ -489,15 +480,11 @@ struct sway_container *container_find(struct sway_container *container,
                 struct sway_container *child = container->children->items[i];
                 if (test(child, data)) {
                         return child;
-                } else {
-                        struct sway_container *res = container_find(child, test, data);
-                        if (res) {
-                                return res;
-                        }
                 }
-        }
-        if (container->type == C_WORKSPACE) {
-                return container_find(container->sway_workspace->floating, test, data);
+                struct sway_container *res = container_find_child(child, test, data);
+                if (res) {
+                        return res;
+                }
         }
         return NULL;
 }
@@ -743,26 +730,20 @@ struct sway_container *container_at(struct sway_container *workspace,
         return NULL;
 }
 
-void container_for_each_descendant(struct sway_container *container,
+void container_for_each_child(struct sway_container *container,
                 void (*f)(struct sway_container *container, void *data),
                 void *data) {
-        if (!container) {
+        if (!sway_assert(container->type == C_CONTAINER ||
+                                container->type == C_VIEW, "Expected a container or view")) {
                 return;
         }
+        f(container, data);
         if (container->children)  {
                 for (int i = 0; i < container->children->length; ++i) {
                         struct sway_container *child = container->children->items[i];
-                        container_for_each_descendant(child, f, data);
+                        container_for_each_child(child, f, data);
                 }
         }
-        if (container->type == C_WORKSPACE)  {
-                struct sway_container *floating = container->sway_workspace->floating;
-                for (int i = 0; i < floating->children->length; ++i) {
-                        struct sway_container *child = floating->children->items[i];
-                        container_for_each_descendant(child, f, data);
-                }
-        }
-        f(container, data);
 }
 
 bool container_has_ancestor(struct sway_container *descendant,
@@ -1198,13 +1179,12 @@ void container_set_dirty(struct sway_container *container) {
         list_add(server.dirty_containers, container);
 }
 
-static bool find_urgent_iterator(struct sway_container *con,
-                void *data) {
+static bool find_urgent_iterator(struct sway_container *con, void *data) {
         return con->type == C_VIEW && view_is_urgent(con->sway_view);
 }
 
 bool container_has_urgent_child(struct sway_container *container) {
-        return container_find(container, find_urgent_iterator, NULL);
+        return container_find_child(container, find_urgent_iterator, NULL);
 }
 
 void container_end_mouse_operation(struct sway_container *container) {
@@ -1236,7 +1216,7 @@ void container_set_fullscreen(struct sway_container *container, bool enable) {
                 container_set_fullscreen(workspace->sway_workspace->fullscreen, false);
         }
 
-        container_for_each_descendant(container, set_fullscreen_iterator, &enable);
+        container_for_each_child(container, set_fullscreen_iterator, &enable);
 
         container->is_fullscreen = enable;
 
diff --git a/sway/tree/output.c b/sway/tree/output.c
index ab955359..6da63064 100644
--- a/sway/tree/output.c
+++ b/sway/tree/output.c
@@ -103,6 +103,57 @@ struct sway_container *output_create(
         return output;
 }
 
+void output_for_each_workspace(struct sway_container *output,
+                void (*f)(struct sway_container *con, void *data), void *data) {
+        if (!sway_assert(output->type == C_OUTPUT, "Expected an output")) {
+                return;
+        }
+        for (int i = 0; i < output->children->length; ++i) {
+                struct sway_container *workspace = output->children->items[i];
+                f(workspace, data);
+        }
+}
+
+void output_for_each_container(struct sway_container *output,
+                void (*f)(struct sway_container *con, void *data), void *data) {
+        if (!sway_assert(output->type == C_OUTPUT, "Expected an output")) {
+                return;
+        }
+        for (int i = 0; i < output->children->length; ++i) {
+                struct sway_container *workspace = output->children->items[i];
+                workspace_for_each_container(workspace, f, data);
+        }
+}
+
+struct sway_container *output_find_workspace(struct sway_container *output,
+                bool (*test)(struct sway_container *con, void *data), void *data) {
+        if (!sway_assert(output->type == C_OUTPUT, "Expected an output")) {
+                return NULL;
+        }
+        for (int i = 0; i < output->children->length; ++i) {
+                struct sway_container *workspace = output->children->items[i];
+                if (test(workspace, data)) {
+                        return workspace;
+                }
+        }
+        return NULL;
+}
+
+struct sway_container *output_find_container(struct sway_container *output,
+                bool (*test)(struct sway_container *con, void *data), void *data) {
+        if (!sway_assert(output->type == C_OUTPUT, "Expected an output")) {
+                return NULL;
+        }
+        struct sway_container *result = NULL;
+        for (int i = 0; i < output->children->length; ++i) {
+                struct sway_container *workspace = output->children->items[i];
+                if ((result = workspace_find_container(workspace, test, data))) {
+                        return result;
+                }
+        }
+        return NULL;
+}
+
 static int sort_workspace_cmp_qsort(const void *_a, const void *_b) {
         struct sway_container *a = *(void **)_a;
         struct sway_container *b = *(void **)_b;
@@ -122,4 +173,3 @@ static int sort_workspace_cmp_qsort(const void *_a, const void *_b) {
 void output_sort_workspaces(struct sway_container *output) {
         list_stable_sort(output->children, sort_workspace_cmp_qsort);
 }
-
diff --git a/sway/tree/root.c b/sway/tree/root.c
index fc908cc1..8d8f42dc 100644
--- a/sway/tree/root.c
+++ b/sway/tree/root.c
@@ -256,3 +256,81 @@ void root_record_workspace_pid(pid_t pid) {
                         &pw->output_destroy);
         wl_list_insert(&pid_workspaces, &pw->link);
 }
+
+void root_for_each_workspace(void (*f)(struct sway_container *con, void *data),
+                void *data) {
+        for (int i = 0; i < root_container.children->length; ++i) {
+                struct sway_container *output = root_container.children->items[i];
+                output_for_each_workspace(output, f, data);
+        }
+}
+
+void root_for_each_container(void (*f)(struct sway_container *con, void *data),
+                void *data) {
+        for (int i = 0; i < root_container.children->length; ++i) {
+                struct sway_container *output = root_container.children->items[i];
+                output_for_each_container(output, f, data);
+        }
+
+        // Scratchpad
+        for (int i = 0; i < root_container.sway_root->scratchpad->length; ++i) {
+                struct sway_container *container =
+                        root_container.sway_root->scratchpad->items[i];
+                // If the container has a parent then it's visible on a workspace
+                // and will have been iterated in the previous for loop. So we only
+                // iterate the hidden scratchpad containers here.
+                if (!container->parent) {
+                        f(container, data);
+                        container_for_each_child(container, f, data);
+                }
+        }
+}
+
+struct sway_container *root_find_output(
+                bool (*test)(struct sway_container *con, void *data), void *data) {
+        for (int i = 0; i < root_container.children->length; ++i) {
+                struct sway_container *output = root_container.children->items[i];
+                if (test(output, data)) {
+                        return output;
+                }
+        }
+        return NULL;
+}
+
+struct sway_container *root_find_workspace(
+                bool (*test)(struct sway_container *con, void *data), void *data) {
+        struct sway_container *result = NULL;
+        for (int i = 0; i < root_container.children->length; ++i) {
+                struct sway_container *output = root_container.children->items[i];
+                if ((result = output_find_workspace(output, test, data))) {
+                        return result;
+                }
+        }
+        return NULL;
+}
+
+struct sway_container *root_find_container(
+                bool (*test)(struct sway_container *con, void *data), void *data) {
+        struct sway_container *result = NULL;
+        for (int i = 0; i < root_container.children->length; ++i) {
+                struct sway_container *output = root_container.children->items[i];
+                if ((result = output_find_container(output, test, data))) {
+                        return result;
+                }
+        }
+
+        // Scratchpad
+        for (int i = 0; i < root_container.sway_root->scratchpad->length; ++i) {
+                struct sway_container *container =
+                        root_container.sway_root->scratchpad->items[i];
+                if (!container->parent) {
+                        if (test(container, data)) {
+                                return container;
+                        }
+                        if ((result = container_find_child(container, test, data))) {
+                                return result;
+                        }
+                }
+        }
+        return NULL;
+}
diff --git a/sway/tree/view.c b/sway/tree/view.c
index 950494d8..4495c150 100644
--- a/sway/tree/view.c
+++ b/sway/tree/view.c
@@ -899,8 +899,8 @@ static bool find_by_mark_iterator(struct sway_container *con,
 }
 
 struct sway_view *view_find_mark(char *mark) {
-        struct sway_container *container = container_find(&root_container,
-                find_by_mark_iterator, mark);
+        struct sway_container *container = root_find_container(
+                        find_by_mark_iterator, mark);
         if (!container) {
                 return NULL;
         }
@@ -908,7 +908,7 @@ struct sway_view *view_find_mark(char *mark) {
 }
 
 bool view_find_and_unmark(char *mark) {
-        struct sway_container *container = container_find(&root_container,
+        struct sway_container *container = root_find_container(
                 find_by_mark_iterator, mark);
         if (!container) {
                 return false;
diff --git a/sway/tree/workspace.c b/sway/tree/workspace.c
index 1c0e6515..b7090de6 100644
--- a/sway/tree/workspace.c
+++ b/sway/tree/workspace.c
@@ -244,8 +244,7 @@ struct sway_container *workspace_by_number(const char* name) {
         if (wbnd.len <= 0) {
                 return NULL;
         }
-        return container_find(&root_container,
-                        _workspace_by_number, (void *) &wbnd);
+        return root_find_workspace(_workspace_by_number, (void *) &wbnd);
 }
 
 static bool _workspace_by_name(struct sway_container *view, void *data) {
@@ -274,11 +273,11 @@ struct sway_container *workspace_by_name(const char *name) {
         } else if (strcmp(name, "current") == 0) {
                 return current_workspace;
         } else if (strcasecmp(name, "back_and_forth") == 0) {
-                return prev_workspace_name ? container_find(&root_container,
-                                _workspace_by_name, (void *)prev_workspace_name) : NULL;
+                return prev_workspace_name ?
+                        root_find_workspace(_workspace_by_name, (void*)prev_workspace_name)
+                        : NULL;
         } else {
-                return container_find(&root_container, _workspace_by_name,
-                                (void *)name);
+                return root_find_workspace(_workspace_by_name, (void*)name);
         }
 }
 
@@ -518,8 +517,7 @@ struct sway_container *workspace_output_get_highest_available(
                         continue;
                 }
 
-                struct sway_container *output = container_find(&root_container,
-                                _output_by_name, name);
+                struct sway_container *output = root_find_output(_output_by_name, name);
                 if (output) {
                         return output;
                 }
@@ -528,8 +526,13 @@ struct sway_container *workspace_output_get_highest_available(
         return NULL;
 }
 
+static bool find_urgent_iterator(struct sway_container *con, void *data) {
+        return con->type == C_VIEW && view_is_urgent(con->sway_view);
+}
+
 void workspace_detect_urgent(struct sway_container *workspace) {
-        bool new_urgent = container_has_urgent_child(workspace);
+        bool new_urgent = (bool)workspace_find_container(workspace,
+                        find_urgent_iterator, NULL);
 
         if (workspace->sway_workspace->urgent != new_urgent) {
                 workspace->sway_workspace->urgent = new_urgent;
@@ -538,6 +541,56 @@ void workspace_detect_urgent(struct sway_container *workspace) {
         }
 }
 
+void workspace_for_each_container(struct sway_container *ws,
+                void (*f)(struct sway_container *con, void *data), void *data) {
+        if (!sway_assert(ws->type == C_WORKSPACE, "Expected a workspace")) {
+                return;
+        }
+        // Tiling
+        for (int i = 0; i < ws->children->length; ++i) {
+                struct sway_container *container = ws->children->items[i];
+                f(container, data);
+                container_for_each_child(container, f, data);
+        }
+        // Floating
+        for (int i = 0; i < ws->sway_workspace->floating->children->length; ++i) {
+                struct sway_container *container =
+                        ws->sway_workspace->floating->children->items[i];
+                f(container, data);
+                container_for_each_child(container, f, data);
+        }
+}
+
+struct sway_container *workspace_find_container(struct sway_container *ws,
+                bool (*test)(struct sway_container *con, void *data), void *data) {
+        if (!sway_assert(ws->type == C_WORKSPACE, "Expected a workspace")) {
+                return NULL;
+        }
+        struct sway_container *result = NULL;
+        // Tiling
+        for (int i = 0; i < ws->children->length; ++i) {
+                struct sway_container *child = ws->children->items[i];
+                if (test(child, data)) {
+                        return child;
+                }
+                if ((result = container_find_child(child, test, data))) {
+                        return result;
+                }
+        }
+        // Floating
+        for (int i = 0; i < ws->sway_workspace->floating->children->length; ++i) {
+                struct sway_container *child =
+                        ws->sway_workspace->floating->children->items[i];
+                if (test(child, data)) {
+                        return child;
+                }
+                if ((result = container_find_child(child, test, data))) {
+                        return result;
+                }
+        }
+        return NULL;
+}
+
 struct sway_container *workspace_wrap_children(struct sway_container *ws) {
         struct sway_container *middle = container_create(C_CONTAINER);
         middle->layout = ws->layout;