Cinnamon/Muffin: stacking-aware, multi-monitor free-space window placement mode

[Michael-1]

Current behaviour

With placement-mode automatic, find_first_fit() in Muffin’s src/core/place.c tries three things, and only on the monitor Muffin picks for the window:

1. the centre of the work area
2. directly below each existing window
3. directly to the right of each existing window

A candidate is only accepted if it overlaps no other window at all. Otherwise the placement falls back to cascading. On a busy desktop that almost always means cascading, even when a large area is only covered by windows deep in the stack that you can barely see. It also never considers a second monitor that is empty.

Proposal

An opt-in placement mode (for example free-space) for normal, non-transient windows. Dialogs and other transients keep the current behaviour, so they still open over their parent:

1. Start with the free region = the work area of every monitor, each as its own rectangle, so a window never straddles a monitor seam or lands in space no monitor covers.
2. Walk the visible windows on the current workspace in stacking order, top to bottom, subtracting each one from the free region (maintained as a list of maximal rectangles).
3. Stop just before the step where no free rectangle can hold the new window any more.
4. Place the window centred in the largest rectangle that still fits at that step.
5. If the window does not fit anywhere even on an empty desktop, fall back to centring it on the current monitor’s work area.

The effect: a new window avoids the windows you can actually see (the top of the stack) and is allowed to cover windows that are buried anyway. Unlike first-fit, it doesn’t give up and cascade as soon as no completely empty spot exists.

Prototype

I’m running this as an external python-xlib daemon (Cinnamon 6.6.9 on X11) that moves windows right after Muffin maps them. To try it: sudo apt install python3-xlib, then run the script in a session. The maximal-rectangle subtraction (subtract()) is simple and cheap enough to run inside meta_window_place().

smart-placement.py

#!/usr/bin/env python3
# Places new top-level windows into the largest area left free by the windows above them
#
# Walks the stack top to bottom, subtracting each window from the free region of all
# monitors, and stops at the last step where the new window still fits. Transients, dialogs and
# other non-normal windows are left to Muffin, which puts them over their parent
#
# Work areas are computed here from monitors and Cinnamon's panel actors because Muffin's
# can go stale after a monitor hotplug. For the same reason Cinnamon's panel struts are
# recomputed after every RandR screen change, which also fixes maximizing and tiling

import json
import select
import subprocess
import sys
import time

from Xlib import X, display
from Xlib.ext import randr
from Xlib.error import XError
from Xlib.protocol import event

SETTLE_DELAY = 0.05
POLL_INTERVAL = 0.03
STRUT_REFRESH_DELAYS = (2, 6)
MAX_WAIT = 2.0
MIN_FREE = 40

d = display.Display()
root = d.screen().root
A = {n: d.intern_atom(n) for n in (
    "_NET_CLIENT_LIST", "_NET_CLIENT_LIST_STACKING", "_NET_WM_WINDOW_TYPE",
    "_NET_WM_WINDOW_TYPE_NORMAL", "_NET_WM_STATE", "_NET_WM_STATE_HIDDEN",
    "_NET_WM_STATE_MAXIMIZED_VERT", "_NET_WM_STATE_MAXIMIZED_HORZ",
    "_NET_WM_STATE_FULLSCREEN", "_NET_WM_DESKTOP", "_NET_CURRENT_DESKTOP",
    "_NET_FRAME_EXTENTS", "_GTK_FRAME_EXTENTS", "_NET_MOVERESIZE_WINDOW",
    "_NET_WM_WINDOW_TYPE_DOCK", "_NET_WM_WINDOW_TYPE_DESKTOP")}

PANEL_JS = ("JSON.stringify(Main.layoutManager._chrome._trackedActors.filter(a=>a.affectsStruts"
            "&&a.actor.visible).map(a=>{let [x,y]=a.actor.get_transformed_position();"
            "let [w,h]=a.actor.get_transformed_size();return [x,y,w,h].map(Math.round)}))")


def log(*a):
    print(*a, file=sys.stderr, flush=True)


def prop(win, name, typ=X.AnyPropertyType):
    try:
        p = win.get_full_property(A[name], typ)
    except XError:
        return None
    return list(p.value) if p else None


def cinnamon_eval(js):
    out = subprocess.run(
        ["gdbus", "call", "--session", "--dest", "org.Cinnamon", "--object-path",
         "/org/Cinnamon", "--method", "org.Cinnamon.Eval", js],
        capture_output=True, text=True, timeout=1).stdout
    # Output looks like (true, '"..."')
    return json.loads(out[out.index("'") + 1:out.rindex("'")])


def refresh_struts():
    try:
        cinnamon_eval("Main.layoutManager._chrome.updateRegions(); 'ok'")
    except Exception as e:
        log("strut refresh failed:", e)


_panels = []


def refresh_panels():
    # Cached because Cinnamon answers Eval on its main thread, which is busy while
    # new windows map
    global _panels
    try:
        _panels = json.loads(cinnamon_eval(PANEL_JS))
    except Exception as e:
        log("panel query failed:", e)


def panels():
    return _panels


def monitors():
    return [(m.x, m.y, m.width_in_pixels, m.height_in_pixels)
            for m in root.xrandr_get_monitors().monitors]


def overlaps(a, b):
    return a[0] < b[0] + b[2] and b[0] < a[0] + a[2] and a[1] < b[1] + b[3] and b[1] < a[1] + a[3]


def contains(a, b):
    return a[0] <= b[0] and a[1] <= b[1] and a[0] + a[2] >= b[0] + b[2] and a[1] + a[3] >= b[1] + b[3]


def subtract(free, r):
    # Maximal-rectangles subtraction: every free rect overlapping r splits into up to four
    # strips along r's edges, then rects contained in others are dropped
    out = []
    for f in free:
        if not overlaps(f, r):
            out.append(f)
            continue
        fx2, fy2, rx2, ry2 = f[0] + f[2], f[1] + f[3], r[0] + r[2], r[1] + r[3]
        if r[0] > f[0]:
            out.append((f[0], f[1], r[0] - f[0], f[3]))
        if rx2 < fx2:
            out.append((rx2, f[1], fx2 - rx2, f[3]))
        if r[1] > f[1]:
            out.append((f[0], f[1], f[2], r[1] - f[1]))
        if ry2 < fy2:
            out.append((f[0], ry2, f[2], fy2 - ry2))
    out = [f for f in set(out) if f[2] >= MIN_FREE and f[3] >= MIN_FREE]
    return [f for f in out if not any(g != f and contains(g, f) for g in out)]


def fitting(free, w, h):
    return [f for f in free if f[2] >= w and f[3] >= h]


class Win:
    # Geometry of the visible window: client area plus server-side decorations, minus
    # client-side shadows
    def __init__(self, wid):
        self.w = d.create_resource_object("window", wid)
        g = self.w.get_geometry()
        t = self.w.translate_coords(root, 0, 0)
        cx, cy = -t.x, -t.y
        fl, fr, ft, fb = prop(self.w, "_NET_FRAME_EXTENTS") or (0, 0, 0, 0)
        gl, gr, gt, gb = prop(self.w, "_GTK_FRAME_EXTENTS") or (0, 0, 0, 0)
        self.ready = (self.w.get_attributes().map_state == X.IsViewable
                      or prop(self.w, "_NET_FRAME_EXTENTS") is not None)
        self.gtk = (gl, gr, gt, gb)
        self.frame = (fl, ft)
        self.rect = (cx - fl + gl, cy - ft + gt,
                     g.width + fl + fr - gl - gr, g.height + ft + fb - gt - gb)

    def state(self):
        return set(prop(self.w, "_NET_WM_STATE") or [])

    def types(self):
        return prop(self.w, "_NET_WM_WINDOW_TYPE") or []

    def on_desktop(self, desk):
        v = prop(self.w, "_NET_WM_DESKTOP")
        return not v or v[0] in (desk, 0xFFFFFFFF)

    def move_visible_to(self, x, y):
        # NorthWest gravity positions the outer frame, which for CSD windows includes
        # the shadow margin
        gl, _, gt, _ = self.gtk
        flags = 1 | (1 << 8) | (1 << 9) | (2 << 12)
        ev = event.ClientMessage(window=self.w, client_type=A["_NET_MOVERESIZE_WINDOW"],
                                 data=(32, [flags, (x - gl) & 0xFFFFFFFF, (y - gt) & 0xFFFFFFFF, 0, 0]))
        root.send_event(ev, event_mask=X.SubstructureRedirectMask | X.SubstructureNotifyMask)
        d.flush()


def is_candidate(win):
    if win.w.get_wm_transient_for():
        return False
    types = win.types()
    if types and types[0] != A["_NET_WM_WINDOW_TYPE_NORMAL"]:
        return False
    return not win.state() & {A["_NET_WM_STATE_MAXIMIZED_VERT"], A["_NET_WM_STATE_MAXIMIZED_HORZ"],
                              A["_NET_WM_STATE_FULLSCREEN"], A["_NET_WM_STATE_HIDDEN"]}


def user_positioned(win):
    hints = win.w.get_wm_normal_hints()
    return bool(hints and hints.flags & 1)


def target_monitor(mons):
    p = root.query_pointer()
    for m in mons:
        if contains(m, (p.root_x, p.root_y, 1, 1)):
            return m
    return mons[0]


def place(wid, seen):
    win = Win(wid)
    if not is_candidate(win):
        return
    mons = monitors()
    on_screen = any(overlaps(m, win.rect) for m in mons)
    if user_positioned(win) and on_screen:
        return

    # Every monitor's work area is its own free rect, so windows never straddle the seam
    # or land in the dead space of the staggered layout
    free = list(mons)
    for p in panels():
        free = subtract(free, tuple(p))
    w, h = win.rect[2], win.rect[3]

    if not fitting(free, w, h):
        mon = target_monitor(mons)
        area = max((f for f in free if overlaps(f, mon)), key=lambda f: f[2] * f[3], default=mon)
        x = area[0] + max(0, (area[2] - w) // 2)
        y = area[1] + max(0, (area[3] - h) // 2)
    else:
        desk = (prop(root, "_NET_CURRENT_DESKTOP") or [0])[0]
        skip = {A["_NET_WM_WINDOW_TYPE_DOCK"], A["_NET_WM_WINDOW_TYPE_DESKTOP"]}
        for oid in reversed(prop(root, "_NET_CLIENT_LIST_STACKING") or []):
            if oid == wid:
                continue
            try:
                o = Win(oid)
                if (not o.on_desktop(desk) or A["_NET_WM_STATE_HIDDEN"] in o.state()
                        or set(o.types()) & skip):
                    continue
            except XError:
                continue
            nxt = subtract(free, o.rect)
            if not fitting(nxt, w, h):
                break
            free = nxt
        best = max(fitting(free, w, h), key=lambda f: f[2] * f[3])
        x = best[0] + (best[2] - w) // 2
        y = best[1] + (best[3] - h) // 2

    if (x, y) != win.rect[:2]:
        log(f"place {wid:#x} {win.rect} -> ({x}, {y}) after {time.monotonic() - seen:.2f}s")
        win.move_visible_to(x, y)


def main():
    root.change_attributes(event_mask=X.PropertyChangeMask)
    root.xrandr_select_input(randr.RRScreenChangeNotifyMask)
    known = set(prop(root, "_NET_CLIENT_LIST") or [])
    pending = {}
    first_seen = {}
    refresh_panels()
    refreshes = [time.monotonic() + t for t in STRUT_REFRESH_DELAYS]
    while True:
        now = time.monotonic()
        due_times = list(pending.values()) + refreshes
        timeout = max(0, min(due_times) - now) if due_times else None
        if not d.pending_events():
            select.select([d.fileno()], [], [], timeout)
        while d.pending_events():
            ev = d.next_event()
            if ev.type == X.PropertyNotify and ev.atom == A["_NET_CLIENT_LIST"]:
                cur = set(prop(root, "_NET_CLIENT_LIST") or [])
                for wid in cur - known:
                    pending[wid] = first_seen[wid] = time.monotonic() + SETTLE_DELAY
                known = cur
            elif ev.type == d.extension_event.ScreenChangeNotify:
                refreshes = [time.monotonic() + t for t in STRUT_REFRESH_DELAYS]
        now = time.monotonic()
        if refreshes and refreshes[0] <= now:
            refreshes.pop(0)
            refresh_struts()
            refresh_panels()
        for wid, due in list(pending.items()):
            if due > now:
                continue
            del pending[wid]
            first = first_seen.get(wid, now)
            if wid not in known:
                first_seen.pop(wid, None)
                continue
            try:
                win = Win(wid)
                # Wait until Muffin has framed the window (server-side decorations) or the
                # window is mapped (client-side decorations, which get no frame extents)
                if not win.ready and now - first < MAX_WAIT:
                    pending[wid] = now + POLL_INTERVAL
                    continue
                first_seen.pop(wid, None)
                place(wid, first - SETTLE_DELAY)
            except XError as e:
                log(f"skip {wid:#x}: {e}")
            except Exception as e:
                log(f"error {wid:#x}: {e!r}")


if __name__ == "__main__":
    main()

I’m willing to port it to C in place.c as a new MetaPlacementMode, plus the matching org.cinnamon.muffin placement-mode enum value and an entry in Cinnamon's window settings. The existing modes stay unchanged. Would you merge a PR along these lines?

Related

linuxmint/cinnamon#4313 and linuxmint/cinnamon#542 introduced the current placement modes; linuxmint/muffin#205 and linuxmint/muffin#857 describe shortcomings of automatic’s first-fit/cascade path.

Environment

Linux Mint, Cinnamon 6.680