surface: add synced objects

Also see individual commits.

Closes #1546 (closed)

Supersedes !2977 (closed), !1685 (closed) (?)

Fixes #3235 (closed)

State squashing

Squashing refers to an action of combining a state with the state right before it in the queue. The older state becomes a "sum" of two states, and the newer state becomes empty.

Data structure

This MR introduces wlr_surface_synced and wlr_surface_synced_state to keep track of objects synchronized with the surface state flow. At any given moment, a surface has a current state, a pending state, and optionally a number of cached states. Thus, the following data structure is maintained:

This setup allows to perform state caching and squashing in O(k) time, where k is the number of surface-synced objects. When a state is cached, a column of cachedn+1 states is added right before the last one (pending).

Creation of a surface-synced object adds a row of syncedk+1 states and is done in O(n), where n is the number of cached states at the moment; most of the time, n is 0. Note that rows have undefined order; wlr_surface::synced and wlr_surface_state::synced must be treated as unordered sets.

Progress

• wl_subsurface
• xdg_surface
• xdg_toplevel
• xdg_popup
• zwlr_layer_surface_v1
• zxdg_toplevel_decoration
• zwp_pointer_constraints_v1
• wp_presentation_feedback

There are objects which only have current state which is updated on surface commit; those don't need to be surface-synced.

Notes

• wlr_surface.current.seq is meaningless and is always 0. It can't be set to the sequence number of the state being committed.

Consider the following situation: current ⇄ A(seq 1) ⇄ B(seq 2) ⇄ pending. If A is unlocked and then B is unlocked, wlr_surface.current.seq is set to 1 and then 2. However, if B is unlocked first, it's squashed into A. A.seq can't be updated to 2, because whatever locked A still has the old sequence number. After unlocking A, wlr_surface.current.seq will be 1. To avoid this inconsistency, sequence numbers aren't updated at all and assumed to be only used for state locking. Note that this could be fixed in a non-breaking way by introducing wlr_surface_state.lock_seq and updating wlr_surface_state.seq on squash, if required.

• While wlr_surface_synced_interface.precommit is called right before the current state update, wlr_surface_role.precommit is called on wl_surface.commit request. This is a bug and will be fixed in another PR. Fixed by !3191 (merged).

• *.current.committed now indicates which parts of the current state were modified by the most recent commit. Related: #2098

Breaking changes

This is (supposed to be) a purely internal change and shouldn't require any action from compositor developers.