transactions: Amend pending transactions

The transaction system contains a necessary optimization where a popped
transaction is combined with later, similar transactions. This breaks
the chronological order of states, and can lead to desynchronized
geometries.

To fix this, we replace the queue with only 2 transactions: current and
pending. If a pending transaction exists, it is updated with new state
instead of creating additional transactions.

As we never have more than a single waiting transaction, we no longer
need the queue optimization that is causing problems.

Closes: https://github.com/swaywm/sway/issues/6012

3 files changed, 93 insertions, 85 deletions

diff --git a/include/sway/server.h b/include/sway/server.h
index 0f5e3ab2..5a2562b3 100644
--- a/include/sway/server.h
+++ b/include/sway/server.h
@@ -23,6 +23,8 @@
 #include "sway/xwayland.h"
 #endif
 
+struct sway_transaction;
+
 struct sway_server {
         struct wl_display *wl_display;
         struct wl_event_loop *wl_event_loop;
@@ -85,8 +87,22 @@ struct sway_server {
         struct wlr_text_input_manager_v3 *text_input;
         struct wlr_foreign_toplevel_manager_v1 *foreign_toplevel_manager;
 
+        // The timeout for transactions, after which a transaction is applied
+        // regardless of readiness.
         size_t txn_timeout_ms;
-        list_t *transactions;
+
+        // Stores a transaction after it has been committed, but is waiting for
+        // views to ack the new dimensions before being applied. A queued
+        // transaction is frozen and must not have new instructions added to it.
+        struct sway_transaction *queued_transaction;
+
+        // Stores a pending transaction that will be committed once the existing
+        // queued transaction is applied and freed. The pending transaction can be
+        // updated with new instructions as needed.
+        struct sway_transaction *pending_transaction;
+
+        // Stores the nodes that have been marked as "dirty" and will be put into
+        // the pending transaction.
         list_t *dirty_nodes;
 };
 
diff --git a/sway/desktop/transaction.c b/sway/desktop/transaction.c
index bea9d539..9f488963 100644
--- a/sway/desktop/transaction.c
+++ b/sway/desktop/transaction.c
@@ -87,7 +87,11 @@ static void transaction_destroy(struct sway_transaction *transaction) {
 static void copy_output_state(struct sway_output *output,
                 struct sway_transaction_instruction *instruction) {
         struct sway_output_state *state = &instruction->output_state;
-        state->workspaces = create_list();
+        if (state->workspaces) {
+                state->workspaces->length = 0;
+        } else {
+                state->workspaces = create_list();
+        }
         list_cat(state->workspaces, output->workspaces);
 
         state->active_workspace = output_get_active_workspace(output);
@@ -105,8 +109,16 @@ static void copy_workspace_state(struct sway_workspace *ws,
         state->layout = ws->layout;
 
         state->output = ws->output;
-        state->floating = create_list();
-        state->tiling = create_list();
+        if (state->floating) {
+                state->floating->length = 0;
+        } else {
+                state->floating = create_list();
+        }
+        if (state->tiling) {
+                state->tiling->length = 0;
+        } else {
+                state->tiling = create_list();
+        }
         list_cat(state->floating, ws->floating);
         list_cat(state->tiling, ws->tiling);
 
@@ -147,7 +159,11 @@ static void copy_container_state(struct sway_container *container,
         state->content_height = container->content_height;
 
         if (!container->view) {
-                state->children = create_list();
+                if (state->children) {
+                        state->children->length = 0;
+                } else {
+                        state->children = create_list();
+                }
                 list_cat(state->children, container->children);
         }
 
@@ -163,13 +179,32 @@ static void copy_container_state(struct sway_container *container,
 
 static void transaction_add_node(struct sway_transaction *transaction,
                 struct sway_node *node) {
-        struct sway_transaction_instruction *instruction =
-                calloc(1, sizeof(struct sway_transaction_instruction));
-        if (!sway_assert(instruction, "Unable to allocate instruction")) {
-                return;
+        struct sway_transaction_instruction *instruction = NULL;
+
+        // Check if we have an instruction for this node already, in which case we
+        // update that instead of creating a new one.
+        if (node->ntxnrefs > 0) {
+                for (int idx = 0; idx < transaction->instructions->length; idx++) {
+                        struct sway_transaction_instruction *other =
+                                transaction->instructions->items[idx];
+                        if (other->node == node) {
+                                instruction = other;
+                                break;
+                        }
+                }
+        }
+
+        if (!instruction) {
+                instruction = calloc(1, sizeof(struct sway_transaction_instruction));
+                if (!sway_assert(instruction, "Unable to allocate instruction")) {
+                        return;
+                }
+                instruction->transaction = transaction;
+                instruction->node = node;
+
+                list_add(transaction->instructions, instruction);
+                node->ntxnrefs++;
         }
-        instruction->transaction = transaction;
-        instruction->node = node;
 
         switch (node->type) {
         case N_ROOT:
@@ -184,9 +219,6 @@ static void transaction_add_node(struct sway_transaction *transaction,
                 copy_container_state(node->sway_container, instruction);
                 break;
         }
-
-        list_add(transaction->instructions, instruction);
-        node->ntxnrefs++;
 }
 
 static void apply_output_state(struct sway_output *output,
@@ -307,70 +339,25 @@ static void transaction_apply(struct sway_transaction *transaction) {
         cursor_rebase_all();
 }
 
-static void transaction_commit(struct sway_transaction *transaction);
+static void transaction_commit_pending(void);
 
-// Return true if both transactions operate on the same nodes
-static bool transaction_same_nodes(struct sway_transaction *a,
-                struct sway_transaction *b) {
-        if (a->instructions->length != b->instructions->length) {
-                return false;
-        }
-        for (int i = 0; i < a->instructions->length; ++i) {
-                struct sway_transaction_instruction *a_inst = a->instructions->items[i];
-                struct sway_transaction_instruction *b_inst = b->instructions->items[i];
-                if (a_inst->node != b_inst->node) {
-                        return false;
-                }
-        }
-        return true;
-}
-
-static void transaction_progress_queue(void) {
-        if (!server.transactions->length) {
+static void transaction_progress(void) {
+        if (!server.queued_transaction) {
                 return;
         }
-        // Only the first transaction in the queue is committed, so that's the one
-        // we try to process.
-        struct sway_transaction *transaction = server.transactions->items[0];
-        if (transaction->num_waiting) {
+        if (server.queued_transaction->num_waiting > 0) {
                 return;
         }
-        transaction_apply(transaction);
-        transaction_destroy(transaction);
-        list_del(server.transactions, 0);
+        transaction_apply(server.queued_transaction);
+        transaction_destroy(server.queued_transaction);
+        server.queued_transaction = NULL;
 
-        if (server.transactions->length == 0) {
-                // The transaction queue is empty, so we're done.
+        if (!server.pending_transaction) {
                 sway_idle_inhibit_v1_check_active(server.idle_inhibit_manager_v1);
                 return;
         }
 
-        // If there's a bunch of consecutive transactions which all apply to the
-        // same views, skip all except the last one.
-        while (server.transactions->length >= 2) {
-                struct sway_transaction *txn = server.transactions->items[0];
-                struct sway_transaction *dup = NULL;
-
-                for (int i = 1; i < server.transactions->length; i++) {
-                        struct sway_transaction *maybe_dup = server.transactions->items[i];
-                        if (transaction_same_nodes(txn, maybe_dup)) {
-                                dup = maybe_dup;
-                                break;
-                        }
-                }
-
-                if (dup) {
-                        list_del(server.transactions, 0);
-                        transaction_destroy(txn);
-                } else {
-                        break;
-                }
-        }
-
-        // We again commit the first transaction in the queue to process it.
-        transaction = server.transactions->items[0];
-        transaction_commit(transaction);
-        transaction_progress_queue();
+        transaction_commit_pending();
 }
 
 static int handle_timeout(void *data) {
@@ -378,7 +365,7 @@ static int handle_timeout(void *data) {
         sway_log(SWAY_DEBUG, "Transaction %p timed out (%zi waiting)",
                         transaction, transaction->num_waiting);
         transaction->num_waiting = 0;
-        transaction_progress_queue();
+        transaction_progress();
         return 0;
 }
 
@@ -479,6 +466,17 @@ static void transaction_commit(struct sway_transaction *transaction) {
         }
 }
 
+static void transaction_commit_pending(void) {
+        if (server.queued_transaction) {
+                return;
+        }
+        struct sway_transaction *transaction = server.pending_transaction;
+        server.pending_transaction = NULL;
+        server.queued_transaction = transaction;
+        transaction_commit(transaction);
+        transaction_progress();
+}
+
 static void set_instruction_ready(
                 struct sway_transaction_instruction *instruction) {
         struct sway_transaction *transaction = instruction->transaction;
@@ -504,7 +502,7 @@ static void set_instruction_ready(
         }
 
         instruction->node->instruction = NULL;
-        transaction_progress_queue();
+        transaction_progress();
 }
 
 void transaction_notify_view_ready_by_serial(struct sway_view *view,
@@ -541,24 +539,20 @@ void transaction_commit_dirty(void) {
         if (!server.dirty_nodes->length) {
                 return;
         }
-        struct sway_transaction *transaction = transaction_create();
-        if (!transaction) {
-                return;
+
+        if (!server.pending_transaction) {
+                server.pending_transaction = transaction_create();
+                if (!server.pending_transaction) {
+                        return;
+                }
         }
+
         for (int i = 0; i < server.dirty_nodes->length; ++i) {
                 struct sway_node *node = server.dirty_nodes->items[i];
-                transaction_add_node(transaction, node);
+                transaction_add_node(server.pending_transaction, node);
                 node->dirty = false;
         }
         server.dirty_nodes->length = 0;
 
-        list_add(server.transactions, transaction);
-
-        // We only commit the first transaction added to the queue.
-        if (server.transactions->length == 1) {
-                transaction_commit(transaction);
-                // Attempting to progress the queue here is useful
-                // if the transaction has nothing to wait for.
-                transaction_progress_queue();
-        }
+        transaction_commit_pending();
 }
diff --git a/sway/server.c b/sway/server.c
index f180da9a..278afd19 100644
--- a/sway/server.c
+++ b/sway/server.c
@@ -199,7 +199,6 @@ bool server_init(struct sway_server *server) {
         }
 
         server->dirty_nodes = create_list();
-        server->transactions = create_list();
 
         server->input = input_manager_create(server);
         input_manager_get_default_seat(); // create seat0
@@ -215,7 +214,6 @@ void server_fini(struct sway_server *server) {
         wl_display_destroy_clients(server->wl_display);
         wl_display_destroy(server->wl_display);
         list_free(server->dirty_nodes);
-        list_free(server->transactions);
 }
 
 bool server_start(struct sway_server *server) {