3 files changed, 361 insertions, 39 deletions

diff --git a/sway/tree/container.c b/sway/tree/container.c
index 48aabd86..fafbdb03 100644
--- a/sway/tree/container.c
+++ b/sway/tree/container.c
@@ -17,6 +17,21 @@
 #include "sway/workspace.h"
 #include "log.h"
 
+static list_t *bfs_queue;
+
+static list_t *get_bfs_queue() {
+	if (!bfs_queue) {
+		bfs_queue = create_list();
+		if (!bfs_queue) {
+			wlr_log(L_ERROR, "could not allocate list for bfs queue");
+			return NULL;
+		}
+	}
+	bfs_queue->length = 0;
+
+	return bfs_queue;
+}
+
 swayc_t *swayc_by_test(swayc_t *container,
 		bool (*test)(swayc_t *view, void *data), void *data) {
 	if (!container->children) {
@@ -151,19 +166,16 @@ swayc_t *new_output(struct sway_output *sway_output) {
 	char *ws_name = workspace_next_name(output->name);
 	wlr_log(L_DEBUG, "Creating default workspace %s", ws_name);
 	swayc_t *ws = new_workspace(output, ws_name);
-	output->focused = ws;
 	// Set each seat's focus if not already set
-	// TODO FOCUS: this is probably stupid, we shouldn't define focus in two
-	// places. We should probably put the active workspace on the sway_output
-	// struct instead of trying to do focus semantics like this
 	struct sway_seat *seat = NULL;
 	wl_list_for_each(seat, &input_manager->seats, link) {
-		if (!seat->focus) {
-			seat->focus = ws;
+		if (!seat->has_focus) {
+			sway_seat_set_focus(seat, ws);
 		}
 	}
 
 	free(ws_name);
+	wl_signal_emit(&root_container.sway_root->events.new_container, output);
 	return output;
 }
 
@@ -185,6 +197,7 @@ swayc_t *new_workspace(swayc_t *output, const char *name) {
 
 	add_child(output, workspace);
 	sort_workspaces(output);
+	wl_signal_emit(&root_container.sway_root->events.new_container, workspace);
 	return workspace;
 }
 
@@ -207,9 +220,9 @@ swayc_t *new_view(swayc_t *sibling, struct sway_view *sway_view) {
 		add_child(sibling, swayc);
 	} else {
 		// Regular case, create as sibling of current container
-		// TODO WLR
-		//add_sibling(sibling, swayc);
+		add_sibling(sibling, swayc);
 	}
+	wl_signal_emit(&root_container.sway_root->events.new_container, swayc);
 	return swayc;
 }
 
@@ -235,6 +248,8 @@ swayc_t *destroy_output(swayc_t *output) {
 		}
 	}
 
+	wl_list_remove(&output->sway_output->output_destroy.link);
+
 	wlr_log(L_DEBUG, "OUTPUT: Destroying output '%s'", output->name);
 	free_swayc(output);
 
@@ -273,7 +288,11 @@ swayc_t *swayc_parent_by_type(swayc_t *container, enum swayc_types type) {
 
 swayc_t *swayc_at(swayc_t *parent, double lx, double ly,
 		struct wlr_surface **surface, double *sx, double *sy) {
-	list_t *queue = create_list();
+	list_t *queue = get_bfs_queue();
+	if (!queue) {
+		return NULL;
+	}
+
 	list_add(queue, parent);
 
 	swayc_t *swayc = NULL;
@@ -313,7 +332,6 @@ swayc_t *swayc_at(swayc_t *parent, double lx, double ly,
 						*sx = view_sx - popup_sx;
 						*sy = view_sy - popup_sy;
 						*surface = popup->surface;
-						list_free(queue);
 						return swayc;
 					}
 					break;
@@ -332,7 +350,6 @@ swayc_t *swayc_at(swayc_t *parent, double lx, double ly,
 				*sx = view_sx - sub_x;
 				*sy = view_sy - sub_y;
 				*surface = subsurface->surface;
-				list_free(queue);
 				return swayc;
 			}
 
@@ -344,7 +361,6 @@ swayc_t *swayc_at(swayc_t *parent, double lx, double ly,
 				*sx = view_sx;
 				*sy = view_sy;
 				*surface = swayc->sway_view->surface;
-				list_free(queue);
 				return swayc;
 			}
 		} else {
@@ -352,8 +368,6 @@ swayc_t *swayc_at(swayc_t *parent, double lx, double ly,
 		}
 	}
 
-	list_free(queue);
-
 	return NULL;
 }
 
@@ -378,3 +392,39 @@ void container_map(swayc_t *container, void (*f)(swayc_t *view, void *data), voi
 		f(container, data);
 	}
 }
+
+void container_for_each_bfs(swayc_t *con, void (*f)(swayc_t *con, void *data),
+		void *data) {
+	list_t *queue = get_bfs_queue();
+	if (!queue) {
+		return;
+	}
+
+	if (queue == NULL) {
+		wlr_log(L_ERROR, "could not allocate list");
+		return;
+	}
+
+	list_add(queue, con);
+
+	swayc_t *current = NULL;
+	while (queue->length) {
+		current = queue->items[0];
+		list_del(queue, 0);
+		f(current, data);
+		// TODO floating containers
+		list_cat(queue, current->children);
+	}
+}
+
+swayc_t *swayc_change_layout(swayc_t *container, enum swayc_layouts layout) {
+	if (container->type == C_WORKSPACE) {
+		container->workspace_layout = layout;
+		if (layout == L_HORIZ || layout == L_VERT) {
+			container->layout = layout;
+		}
+	} else {
+		container->layout = layout;
+	}
+	return container;
+}
diff --git a/sway/tree/layout.c b/sway/tree/layout.c
index 41ff81b2..3d04a1a7 100644
--- a/sway/tree/layout.c
+++ b/sway/tree/layout.c
@@ -10,6 +10,7 @@
 #include "sway/layout.h"
 #include "sway/output.h"
 #include "sway/view.h"
+#include "sway/input/seat.h"
 #include "list.h"
 #include "log.h"
 
@@ -48,10 +49,12 @@ void init_layout(void) {
 	root_container.layout = L_NONE;
 	root_container.name = strdup("root");
 	root_container.children = create_list();
+	wl_signal_init(&root_container.events.destroy);
 
 	root_container.sway_root = calloc(1, sizeof(*root_container.sway_root));
 	root_container.sway_root->output_layout = wlr_output_layout_create();
 	wl_list_init(&root_container.sway_root->unmanaged_views);
+	wl_signal_init(&root_container.sway_root->events.new_container);
 
 	root_container.sway_root->output_layout_change.notify =
 		output_layout_change_notify;
@@ -59,6 +62,32 @@ void init_layout(void) {
 		&root_container.sway_root->output_layout_change);
 }
 
+static int index_child(const swayc_t *child) {
+	// TODO handle floating
+	swayc_t *parent = child->parent;
+	int i, len;
+	len = parent->children->length;
+	for (i = 0; i < len; ++i) {
+		if (parent->children->items[i] == child) {
+			break;
+		}
+	}
+
+	if (!sway_assert(i < len, "Stray container")) {
+		return -1;
+	}
+	return i;
+}
+
+swayc_t *add_sibling(swayc_t *fixed, swayc_t *active) {
+	// TODO handle floating
+	swayc_t *parent = fixed->parent;
+	int i = index_child(fixed);
+	list_insert(parent->children, i + 1, active);
+	active->parent = parent;
+	return active->parent;
+}
+
 void add_child(swayc_t *parent, swayc_t *child) {
 	wlr_log(L_DEBUG, "Adding %p (%d, %fx%f) to %p (%d, %fx%f)",
 			child, child->type, child->width, child->height,
@@ -66,9 +95,6 @@ void add_child(swayc_t *parent, swayc_t *child) {
 	list_add(parent->children, child);
 	child->parent = parent;
 	// set focus for this container
-	if (!parent->focused) {
-		parent->focused = child;
-	}
 	/* TODO WLR
 	if (parent->type == C_WORKSPACE && child->type == C_VIEW && (parent->workspace_layout == L_TABBED || parent->workspace_layout == L_STACKED)) {
 		child = new_container(child, parent->workspace_layout);
@@ -147,8 +173,8 @@ void arrange_windows(swayc_t *container, double width, double height) {
 	height = floor(height);
 
 	wlr_log(L_DEBUG, "Arranging layout for %p %s %fx%f+%f,%f", container,
-		 container->name, container->width, container->height, container->x,
-		 container->y);
+		container->name, container->width, container->height, container->x,
+		container->y);
 
 	double x = 0, y = 0;
 	switch (container->type) {
@@ -249,8 +275,8 @@ static void apply_horiz_layout(swayc_t *container,
 		for (int i = start; i < end; ++i) {
 			swayc_t *child = container->children->items[i];
 			wlr_log(L_DEBUG,
-				 "Calculating arrangement for %p:%d (will scale %f by %f)",
-				 child, child->type, width, scale);
+				"Calculating arrangement for %p:%d (will scale %f by %f)",
+				child, child->type, width, scale);
 			view_set_position(child->sway_view, child_x, y);
 
 			if (i == end - 1) {
@@ -299,8 +325,8 @@ void apply_vert_layout(swayc_t *container,
 		for (i = start; i < end; ++i) {
 			swayc_t *child = container->children->items[i];
 			wlr_log(L_DEBUG,
-				 "Calculating arrangement for %p:%d (will scale %f by %f)",
-				 child, child->type, height, scale);
+				"Calculating arrangement for %p:%d (will scale %f by %f)",
+				child, child->type, height, scale);
 			view_set_position(child->sway_view, x, child_y);
 
 			if (i == end - 1) {
@@ -321,3 +347,244 @@ void apply_vert_layout(swayc_t *container,
 		*/
 	}
 }
+
+/**
+ * Get swayc in the direction of newly entered output.
+ */
+static swayc_t *get_swayc_in_output_direction(swayc_t *output,
+		enum movement_direction dir, struct sway_seat *seat) {
+	if (!output) {
+		return NULL;
+	}
+
+	swayc_t *ws = sway_seat_get_focus_inactive(seat, output);
+	if (ws->type != C_WORKSPACE) {
+		ws = swayc_parent_by_type(ws, C_WORKSPACE);
+	}
+
+	if (ws == NULL) {
+		wlr_log(L_ERROR, "got an output without a workspace");
+		return NULL;
+	}
+
+	if (ws->children->length > 0) {
+		switch (dir) {
+		case MOVE_LEFT:
+			// get most right child of new output
+			return ws->children->items[ws->children->length-1];
+		case MOVE_RIGHT:
+			// get most left child of new output
+			return ws->children->items[0];
+		case MOVE_UP:
+		case MOVE_DOWN: {
+			swayc_t *focused = sway_seat_get_focus_inactive(seat, ws);
+			if (focused && focused->parent) {
+				swayc_t *parent = focused->parent;
+				if (parent->layout == L_VERT) {
+					if (dir == MOVE_UP) {
+						// get child furthest down on new output
+						return parent->children->items[parent->children->length-1];
+					} else if (dir == MOVE_DOWN) {
+						// get child furthest up on new output
+						return parent->children->items[0];
+					}
+				}
+				return focused;
+			}
+			break;
+		}
+		default:
+			break;
+		}
+	}
+
+	return ws;
+}
+
+static void get_layout_center_position(swayc_t *container, int *x, int *y) {
+	// FIXME view coords are inconsistently referred to in layout/output systems
+	if (container->type == C_OUTPUT) {
+		*x = container->x + container->width/2;
+		*y = container->y + container->height/2;
+	} else {
+		swayc_t *output = swayc_parent_by_type(container, C_OUTPUT);
+		if (container->type == C_WORKSPACE) {
+			// Workspace coordinates are actually wrong/arbitrary, but should
+			// be same as output.
+			*x = output->x;
+			*y = output->y;
+		} else {
+			*x = output->x + container->x;
+			*y = output->y + container->y;
+		}
+	}
+}
+
+static bool sway_dir_to_wlr(enum movement_direction dir, enum wlr_direction *out) {
+	switch (dir) {
+	case MOVE_UP:
+		*out = WLR_DIRECTION_UP;
+		break;
+	case MOVE_DOWN:
+		*out = WLR_DIRECTION_DOWN;
+		break;
+	case MOVE_LEFT:
+		*out = WLR_DIRECTION_LEFT;
+		break;
+	case MOVE_RIGHT:
+		*out = WLR_DIRECTION_RIGHT;
+		break;
+	default:
+		return false;
+	}
+
+	return true;
+}
+
+static swayc_t *sway_output_from_wlr(struct wlr_output *output) {
+	if (output == NULL) {
+		return NULL;
+	}
+	for (int i = 0; i < root_container.children->length; ++i) {
+		swayc_t *o = root_container.children->items[i];
+		if (o->type == C_OUTPUT && o->sway_output->wlr_output == output) {
+			return o;
+		}
+	}
+	return NULL;
+}
+
+static swayc_t *get_swayc_in_direction_under(swayc_t *container,
+		enum movement_direction dir, struct sway_seat *seat, swayc_t *limit) {
+	if (dir == MOVE_CHILD) {
+		return sway_seat_get_focus_inactive(seat, container);
+	}
+
+	swayc_t *parent = container->parent;
+	if (dir == MOVE_PARENT) {
+		if (parent->type == C_OUTPUT) {
+			return NULL;
+		} else {
+			return parent;
+		}
+	}
+
+	if (dir == MOVE_PREV || dir == MOVE_NEXT) {
+		int focused_idx = index_child(container);
+		if (focused_idx == -1) {
+			return NULL;
+		} else {
+			int desired = (focused_idx + (dir == MOVE_NEXT ? 1 : -1)) %
+				parent->children->length;
+			if (desired < 0) {
+				desired += parent->children->length;
+			}
+			return parent->children->items[desired];
+		}
+	}
+
+	// If moving to an adjacent output we need a starting position (since this
+	// output might border to multiple outputs).
+	//struct wlc_point abs_pos;
+	//get_layout_center_position(container, &abs_pos);
+
+
+	// TODO WLR fullscreen
+	/*
+	if (container->type == C_VIEW && swayc_is_fullscreen(container)) {
+		wlr_log(L_DEBUG, "Moving from fullscreen view, skipping to output");
+		container = swayc_parent_by_type(container, C_OUTPUT);
+		get_layout_center_position(container, &abs_pos);
+		swayc_t *output = swayc_adjacent_output(container, dir, &abs_pos, true);
+		return get_swayc_in_output_direction(output, dir);
+	}
+	if (container->type == C_WORKSPACE && container->fullscreen) {
+		sway_log(L_DEBUG, "Moving to fullscreen view");
+		return container->fullscreen;
+	}
+	*/
+
+	swayc_t *wrap_candidate = NULL;
+	while (true) {
+		// Test if we can even make a difference here
+		bool can_move = false;
+		int desired;
+		int idx = index_child(container);
+		if (parent->type == C_ROOT) {
+			enum wlr_direction wlr_dir = 0;
+			if (!sway_assert(sway_dir_to_wlr(dir, &wlr_dir),
+						"got invalid direction: %d", dir)) {
+				return NULL;
+			}
+			int lx, ly;
+			get_layout_center_position(container, &lx, &ly);
+			struct wlr_output_layout *layout = root_container.sway_root->output_layout;
+			struct wlr_output *wlr_adjacent =
+				wlr_output_layout_adjacent_output(layout, wlr_dir,
+					container->sway_output->wlr_output, lx, ly);
+			swayc_t *adjacent = sway_output_from_wlr(wlr_adjacent);
+
+			if (!adjacent || adjacent == container) {
+				return wrap_candidate;
+			}
+			swayc_t *next = get_swayc_in_output_direction(adjacent, dir, seat);
+			if (next == NULL) {
+				return NULL;
+			}
+			if (next->children && next->children->length) {
+				// TODO consider floating children as well
+				return sway_seat_get_focus_inactive(seat, next);
+			} else {
+				return next;
+			}
+		} else {
+			if (dir == MOVE_LEFT || dir == MOVE_RIGHT) {
+				if (parent->layout == L_HORIZ || parent->layout == L_TABBED) {
+					can_move = true;
+					desired = idx + (dir == MOVE_LEFT ? -1 : 1);
+				}
+			} else {
+				if (parent->layout == L_VERT || parent->layout == L_STACKED) {
+					can_move = true;
+					desired = idx + (dir == MOVE_UP ? -1 : 1);
+				}
+			}
+		}
+
+		if (can_move) {
+			// TODO handle floating
+			if (desired < 0 || desired >= parent->children->length) {
+				can_move = false;
+				int len = parent->children->length;
+				if (!wrap_candidate && len > 1) {
+					if (desired < 0) {
+						wrap_candidate = parent->children->items[len-1];
+					} else {
+						wrap_candidate = parent->children->items[0];
+					}
+					if (config->force_focus_wrapping) {
+						return wrap_candidate;
+					}
+				}
+			} else {
+				wlr_log(L_DEBUG, "%s cont %d-%p dir %i sibling %d: %p", __func__,
+						idx, container, dir, desired, parent->children->items[desired]);
+				return parent->children->items[desired];
+			}
+		}
+
+		if (!can_move) {
+			container = parent;
+			parent = parent->parent;
+			if (!parent || container == limit) {
+				// wrapping is the last chance
+				return wrap_candidate;
+			}
+		}
+	}
+}
+
+swayc_t *get_swayc_in_direction(swayc_t *container, struct sway_seat *seat,
+		enum movement_direction dir) {
+	return get_swayc_in_direction_under(container, dir, seat, NULL);
+}
diff --git a/sway/tree/workspace.c b/sway/tree/workspace.c
index 23c630b6..861fda4d 100644
--- a/sway/tree/workspace.c
+++ b/sway/tree/workspace.c
@@ -63,9 +63,10 @@ static bool _workspace_by_name(swayc_t *view, void *data) {
 swayc_t *workspace_by_name(const char *name) {
 	struct sway_seat *seat = input_manager_current_seat(input_manager);
 	swayc_t *current_workspace = NULL, *current_output = NULL;
-	if (seat->focus) {
-		current_workspace = swayc_parent_by_type(seat->focus, C_WORKSPACE);
-		current_output = swayc_parent_by_type(seat->focus, C_OUTPUT);
+	swayc_t *focus = sway_seat_get_focus(seat);
+	if (focus) {
+		current_workspace = swayc_parent_by_type(focus, C_WORKSPACE);
+		current_output = swayc_parent_by_type(focus, C_OUTPUT);
 	}
 	if (strcmp(name, "prev") == 0) {
 		return workspace_prev(current_workspace);
@@ -102,7 +103,8 @@ swayc_t *workspace_create(const char *name) {
 	}
 	// Otherwise create a new one
 	struct sway_seat *seat = input_manager_current_seat(input_manager);
-	parent = seat->focus;
+	swayc_t *focus = sway_seat_get_focus_inactive(seat, &root_container);
+	parent = focus;
 	parent = swayc_parent_by_type(parent, C_OUTPUT);
 	return new_workspace(parent, name);
 }
@@ -118,9 +120,15 @@ swayc_t *workspace_output_prev_next_impl(swayc_t *output, bool next) {
 		return NULL;
 	}
 
+	struct sway_seat *seat = input_manager_current_seat(input_manager);
+	swayc_t *focus = sway_seat_get_focus_inactive(seat, output);
+	swayc_t *workspace = (focus->type == C_WORKSPACE ?
+			focus :
+			swayc_parent_by_type(focus, C_WORKSPACE));
+
 	int i;
 	for (i = 0; i < output->children->length; i++) {
-		if (output->children->items[i] == output->focused) {
+		if (output->children->items[i] == workspace) {
 			return output->children->items[
 				wrap(i + (next ? 1 : -1), output->children->length)];
 		}
@@ -193,12 +201,13 @@ bool workspace_switch(swayc_t *workspace) {
 		return false;
 	}
 	struct sway_seat *seat = input_manager_current_seat(input_manager);
-	if (!seat || !seat->focus) {
+	swayc_t *focus = sway_seat_get_focus_inactive(seat, &root_container);
+	if (!seat || !focus) {
 		return false;
 	}
-	swayc_t *active_ws = seat->focus;
+	swayc_t *active_ws = focus;
 	if (active_ws->type != C_WORKSPACE) {
-		swayc_parent_by_type(seat->focus, C_WORKSPACE);
+		swayc_parent_by_type(focus, C_WORKSPACE);
 	}
 
 	if (config->auto_back_and_forth
@@ -222,16 +231,12 @@ bool workspace_switch(swayc_t *workspace) {
 	// TODO: Deal with sticky containers
 
 	wlr_log(L_DEBUG, "Switching to workspace %p:%s", workspace, workspace->name);
-	// TODO FOCUS: Focus the last view this seat had focused on this workspace
-	if (workspace->children->length) {
-		// TODO FOCUS: This is really fucking stupid
-		sway_seat_set_focus(seat, workspace->children->items[0]);
-	} else {
-		sway_seat_set_focus(seat, workspace);
+	swayc_t *next = sway_seat_get_focus_inactive(seat, workspace);
+	if (next == NULL) {
+		next = workspace;
 	}
+	sway_seat_set_focus(seat, next);
 	swayc_t *output = swayc_parent_by_type(workspace, C_OUTPUT);
-	// TODO FOCUS: take a look at this
-	output->focused = workspace;
 	arrange_windows(output, -1, -1);
 	return true;
 }