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.

14 files changed, 233 insertions, 101 deletions

diff --git a/sway/commands/hide_edge_borders.c b/sway/commands/hide_edge_borders.c
index bb390f5f..d59c9fdb 100644
--- a/sway/commands/hide_edge_borders.c
+++ b/sway/commands/hide_edge_borders.c
@@ -31,7 +31,7 @@ struct cmd_results *cmd_hide_edge_borders(int argc, char **argv) {
                                 "<none|vertical|horizontal|both|smart>'");
         }
 
-        container_for_each_descendant(&root_container, _configure_view, NULL);
+        root_for_each_container(_configure_view, NULL);
 
         return cmd_results_new(CMD_SUCCESS, NULL, NULL);
 }
diff --git a/sway/commands/show_marks.c b/sway/commands/show_marks.c
index cf153a0a..dd7d170c 100644
--- a/sway/commands/show_marks.c
+++ b/sway/commands/show_marks.c
@@ -24,8 +24,7 @@ struct cmd_results *cmd_show_marks(int argc, char **argv) {
         config->show_marks = parse_boolean(argv[0], config->show_marks);
 
         if (config->show_marks) {
-                container_for_each_descendant(&root_container,
-                                rebuild_marks_iterator, NULL);
+                root_for_each_container(rebuild_marks_iterator, NULL);
         }
 
         for (int i = 0; i < root_container.children->length; ++i) {
diff --git a/sway/commands/swap.c b/sway/commands/swap.c
index 4e3a9cce..615e6b1d 100644
--- a/sway/commands/swap.c
+++ b/sway/commands/swap.c
@@ -50,13 +50,13 @@ struct cmd_results *cmd_swap(int argc, char **argv) {
         if (strcasecmp(argv[2], "id") == 0) {
 #ifdef HAVE_XWAYLAND
                 xcb_window_t id = strtol(value, NULL, 0);
-                other = container_find(&root_container, test_id, (void *)&id);
+                other = root_find_container(test_id, (void *)&id);
 #endif
         } else if (strcasecmp(argv[2], "con_id") == 0) {
                 size_t con_id = atoi(value);
-                other = container_find(&root_container, test_con_id, (void *)con_id);
+                other = root_find_container(test_con_id, (void *)con_id);
         } else if (strcasecmp(argv[2], "mark") == 0) {
-                other = container_find(&root_container, test_mark, (void *)value);
+                other = root_find_container(test_mark, (void *)value);
         } else {
                 free(value);
                 return cmd_results_new(CMD_INVALID, "swap", EXPECTED_SYNTAX);
diff --git a/sway/commands/unmark.c b/sway/commands/unmark.c
index 44ceccee..c183785b 100644
--- a/sway/commands/unmark.c
+++ b/sway/commands/unmark.c
@@ -52,8 +52,7 @@ struct cmd_results *cmd_unmark(int argc, char **argv) {
                 view_find_and_unmark(mark);
         } else {
                 // Remove all marks from all views
-                container_for_each_descendant(&root_container,
-                                remove_all_marks_iterator, NULL);
+                root_for_each_container(remove_all_marks_iterator, NULL);
         }
         free(mark);
 
diff --git a/sway/config.c b/sway/config.c
index bd14222a..642abbac 100644
--- a/sway/config.c
+++ b/sway/config.c
@@ -822,18 +822,7 @@ void config_update_font_height(bool recalculate) {
         size_t prev_max_height = config->font_height;
         config->font_height = 0;
 
-        container_for_each_descendant(&root_container,
-                        find_font_height_iterator, &recalculate);
-
-        // Also consider floating views
-        for (int i = 0; i < root_container.children->length; ++i) {
-                struct sway_container *output = root_container.children->items[i];
-                for (int j = 0; j < output->children->length; ++j) {
-                        struct sway_container *ws = output->children->items[j];
-                        container_for_each_descendant(ws->sway_workspace->floating,
-                                        find_font_height_iterator, &recalculate);
-                }
-        }
+        root_for_each_container(find_font_height_iterator, &recalculate);
 
         if (config->font_height != prev_max_height) {
                 arrange_windows(&root_container);
diff --git a/sway/criteria.c b/sway/criteria.c
index a5df1eef..81c2325a 100644
--- a/sway/criteria.c
+++ b/sway/criteria.c
@@ -167,8 +167,7 @@ static bool criteria_matches_view(struct criteria *criteria,
                         return false;
                 }
                 list_t *urgent_views = create_list();
-                container_for_each_descendant(&root_container,
-                                find_urgent_iterator, urgent_views);
+                root_for_each_container(find_urgent_iterator, urgent_views);
                 list_stable_sort(urgent_views, cmp_urgent);
                 struct sway_view *target;
                 if (criteria->urgent == 'o') { // oldest
@@ -228,17 +227,7 @@ list_t *criteria_get_views(struct criteria *criteria) {
                 .criteria = criteria,
                 .matches = matches,
         };
-        container_for_each_descendant(&root_container,
-                criteria_get_views_iterator, &data);
-
-        // Scratchpad items which are hidden are not in the tree.
-        for (int i = 0; i < root_container.sway_root->scratchpad->length; ++i) {
-                struct sway_container *con =
-                        root_container.sway_root->scratchpad->items[i];
-                if (!con->parent) {
-                        criteria_get_views_iterator(con, &data);
-                }
-        }
+        root_for_each_container(criteria_get_views_iterator, &data);
         return matches;
 }
 
diff --git a/sway/desktop/output.c b/sway/desktop/output.c
index 66747a3f..43ed9793 100644
--- a/sway/desktop/output.c
+++ b/sway/desktop/output.c
@@ -303,15 +303,14 @@ struct send_frame_done_data {
 
 static void send_frame_done_container_iterator(struct sway_container *con,
                 void *_data) {
-        struct send_frame_done_data *data = _data;
-        if (!sway_assert(con->type == C_VIEW, "expected a view")) {
+        if (con->type != C_VIEW) {
                 return;
         }
-
         if (!view_is_visible(con->sway_view)) {
                 return;
         }
 
+        struct send_frame_done_data *data = _data;
         output_view_for_each_surface(data->output, con->sway_view,
                 send_frame_done_iterator, data->when);
 }
@@ -322,8 +321,8 @@ static void send_frame_done_container(struct sway_output *output,
                 .output = output,
                 .when = when,
         };
-        container_descendants(con, C_VIEW,
-                send_frame_done_container_iterator, &data);
+        output_for_each_container(output->swayc,
+                        send_frame_done_container_iterator, &data);
 }
 
 static void send_frame_done(struct sway_output *output, struct timespec *when) {
diff --git a/sway/input/seat.c b/sway/input/seat.c
index 9d46e760..d35c62a0 100644
--- a/sway/input/seat.c
+++ b/sway/input/seat.c
@@ -313,9 +313,6 @@ static void handle_new_drag_icon(struct wl_listener *listener, void *data) {
 
 static void collect_focus_iter(struct sway_container *con, void *data) {
         struct sway_seat *seat = data;
-        if (con->type > C_WORKSPACE) {
-                return;
-        }
         struct sway_seat_container *seat_con =
                 seat_container_from_container(seat, con);
         if (!seat_con) {
@@ -349,7 +346,8 @@ struct sway_seat *seat_create(struct sway_input_manager *input,
         // init the focus stack
         wl_list_init(&seat->focus_stack);
 
-        container_for_each_descendant(&root_container, collect_focus_iter, seat);
+        root_for_each_workspace(collect_focus_iter, seat);
+        root_for_each_container(collect_focus_iter, seat);
 
         wl_signal_add(&root_container.sway_root->events.new_container,
                 &seat->new_container);
diff --git a/sway/ipc-server.c b/sway/ipc-server.c
index dad1f310..34e940ad 100644
--- a/sway/ipc-server.c
+++ b/sway/ipc-server.c
@@ -522,7 +522,7 @@ void ipc_client_disconnect(struct ipc_client *client) {
 
 static void ipc_get_workspaces_callback(struct sway_container *workspace,
                 void *data) {
-        if (workspace->type != C_WORKSPACE) {
+        if (!sway_assert(workspace->type == C_WORKSPACE, "Expected a workspace")) {
                 return;
         }
         json_object *workspace_json = ipc_json_describe_container(workspace);
@@ -631,8 +631,7 @@ void ipc_client_handle_command(struct ipc_client *client) {
         case IPC_GET_WORKSPACES:
         {
                 json_object *workspaces = json_object_new_array();
-                container_for_each_descendant(&root_container,
-                                ipc_get_workspaces_callback, workspaces);
+                root_for_each_workspace(ipc_get_workspaces_callback, workspaces);
                 const char *json_string = json_object_to_json_string(workspaces);
                 client_valid =
                         ipc_send_reply(client, json_string, (uint32_t)strlen(json_string));
@@ -729,8 +728,7 @@ void ipc_client_handle_command(struct ipc_client *client) {
         case IPC_GET_MARKS:
         {
                 json_object *marks = json_object_new_array();
-                container_descendants(&root_container, C_VIEW, ipc_get_marks_callback,
-                                marks);
+                root_for_each_container(ipc_get_marks_callback, marks);
                 const char *json_string = json_object_to_json_string(marks);
                 client_valid =
                         ipc_send_reply(client, json_string, (uint32_t)strlen(json_string));
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;