public struct LayoutResult: Sendable, Equatable, Codable { public var frames: [WindowID: Rect] public var visibleWindows: [WindowID] public var cannotFit: [WindowID] public init(frames: [WindowID: Rect] = [:], visibleWindows: [WindowID] = [], cannotFit: [WindowID] = []) { self.frames = frames self.visibleWindows = visibleWindows self.cannotFit = cannotFit } } struct TileEdgeMinimums: Sendable { let first: Size let second: Size } public struct TileEdge: Sendable, Equatable, Codable { public enum Child: String, Sendable, Equatable, Hashable, Codable { case first, second } public struct Identity: Sendable, Hashable { public let workspace: WorkspaceKey public let path: [Child] public let firstWindows: [WindowID] public let secondWindows: [WindowID] } /// Geometry changes during a drag; membership and the tree path identify its divider. public var identity: Identity { Identity(workspace: workspace, path: path, firstWindows: firstWindows, secondWindows: secondWindows) } public let workspace: WorkspaceKey public let path: [Child] public let firstWindows: [WindowID] public let secondWindows: [WindowID] public let axis: Axis public let fraction: Double public let frame: Rect public let geometry: Rect public let gap: Double public let firstExtent: Double public let contentExtent: Double public let firstGapExtent: Double let topology: TileTree var minimums: TileEdgeMinimums? = nil private enum CodingKeys: String, CodingKey { case workspace, path, firstWindows, secondWindows, axis, fraction, frame, geometry, gap case firstExtent, contentExtent, firstGapExtent, topology } public static func == (lhs: TileEdge, rhs: TileEdge) -> Bool { lhs.workspace == rhs.workspace && lhs.path == rhs.path && lhs.topology == rhs.topology && lhs.hasSameGeometry(as: rhs) } public var affectedWindows: [WindowID] { firstWindows + secondWindows } public var hitFrame: Rect { frame } public var position: Double { axis == .horizontal ? frame.center.xCoordinate : frame.center.yCoordinate } public func hitArea(tolerance: Double = 0) -> Rect { precondition(tolerance.isFinite && tolerance >= 0, "An edge hit tolerance must be finite and nonnegative") if axis == .horizontal { let halfWidth = max(tolerance, frame.size.width / 2) return Rect(x: position - halfWidth, y: frame.minY, width: halfWidth * 2, height: frame.size.height) } let halfHeight = max(tolerance, frame.size.height / 2) return Rect(x: frame.minX, y: position - halfHeight, width: frame.size.width, height: halfHeight * 2) } public func contains(_ point: Point, tolerance: Double = 0) -> Bool { hitArea(tolerance: tolerance).contains(point) } public func fraction(forDelta delta: Double) -> Double? { guard delta.isFinite, contentExtent.isFinite, contentExtent > 0 else { return nil } // A minimum can move the edge without changing its stored fraction; cancellation restores that fraction. if delta == 0 { return fraction } let requested = (firstExtent + delta - firstGapExtent) / contentExtent return requested.isFinite ? requested : nil } func hasSameGeometry(as other: TileEdge) -> Bool { axis == other.axis && fraction == other.fraction && frame == other.frame && geometry == other.geometry && gap == other.gap && firstExtent == other.firstExtent && contentExtent == other.contentExtent && firstGapExtent == other.firstGapExtent && firstWindows == other.firstWindows && secondWindows == other.secondWindows } } public enum LayoutEngine { // Overlay geometry only; controls do not reserve window space. public static let stackControlHeight = 16.0 @TaskLocal static var arrangementObserver: (@Sendable () -> Void)? = nil @TaskLocal static var traversalObserver: (@Sendable () -> Void)? = nil public static func arrange( _ workspace: Workspace, in screen: Rect, windows: [WindowID: ManagedWindow] = [:] ) -> LayoutResult { arrangementObserver?() var result = arrangeUnrounded(workspace, in: screen, windows: windows) result.frames = result.frames.mapValues { $0.roundedToWholePoints() } return result } public static func edges( _ workspace: Workspace, in screen: Rect, windows: [WindowID: ManagedWindow] = [:] ) -> [TileEdge] { guard workspace.layout != .accordion else { return [] } return traverse(workspace, in: screen, windows: windows, mode: .edges).edges } static func edge( _ workspace: Workspace, at path: [TileEdge.Child], in screen: Rect, windows: [WindowID: ManagedWindow] = [:] ) -> TileEdge? { guard workspace.layout != .accordion else { return nil } return traverse(workspace, in: screen, windows: windows, mode: .edge(path)).edges.first } static func cannotFit( _ workspace: Workspace, within path: [TileEdge.Child], in screen: Rect, windows: [WindowID: ManagedWindow] ) -> [WindowID] { traverse(workspace, in: screen, windows: windows, mode: .cannotFit(path)).result.cannotFit.sorted() } static func arrangeUnrounded( _ workspace: Workspace, in screen: Rect, windows: [WindowID: ManagedWindow] ) -> LayoutResult { traverse(workspace, in: screen, windows: windows, mode: .frames).result } private enum PlacementMode { case frames, edges case edge([TileEdge.Child]) case cannotFit([TileEdge.Child]) var collectingEdges: Bool { switch self { case .edges, .edge: true case .frames, .cannotFit: false } } var targetPath: [TileEdge.Child]? { switch self { case .edge(let path), .cannotFit(let path): path case .frames, .edges: nil } } } private static func traverse( _ workspace: Workspace, in screen: Rect, windows: [WindowID: ManagedWindow], mode: PlacementMode ) -> (result: LayoutResult, edges: [TileEdge]) { traversalObserver?() guard screen.isValid, screen.size.width > 0, screen.size.height > 0 else { return (LayoutResult(), []) } guard let tree = workspace.tree else { return (LayoutResult(), []) } precondition( workspace.displaySize == screen.size, "Adapt the workspace to the exact usable screen before arranging frames or querying tile edges") let area = screen.inset(by: workspace.reservedEdges).inset(by: workspace.gaps.outer) let accordion = workspace.layout == .accordion var summaries: [PlacementSummary] = [] summaries.reserveCapacity(max(1, workspace.order.count * 2 - 1)) var visible: [WindowID] = [] if case .frames = mode { visible.reserveCapacity(workspace.order.count) } var membership = mode.collectingEdges ? EdgeMembership(capacity: workspace.order.count) : nil let focus = accordion ? (workspace.focus.flatMap { tree.contains($0) ? $0 : nil } ?? tree.firstStack.visible) : nil let root = summarize( tree, windows: windows, focus: focus, mode: mode, summaries: &summaries, visible: &visible, membership: &membership) let horizontalDividers = summaries[root].dividers(axis: .horizontal, accordion: accordion) let verticalDividers = summaries[root].dividers(axis: .vertical, accordion: accordion) let extra = accordion ? 1 : 0 var gap = max(0, workspace.gaps.inner) if horizontalDividers > 0 { gap = min(gap, area.size.width / Double(horizontalDividers + extra)) } if verticalDividers > 0 { gap = min(gap, area.size.height / Double(verticalDividers + extra)) } for index in summaries.indices.reversed() { if let children = summaries[index].children, let axis = summaries[index].axis { summaries[index].minimum = combinedMinimum( summaries[children.first].minimum, summaries[children.second].minimum, axis: axis, gap: gap) } } let context = PlacementContext( gap: gap, windows: windows, workspace: workspace.key, topology: tree, accordionFocus: focus, accordionWeight: Double(summaries[root].tileCount) * 4 * workspace.ratio.value / (1 - workspace.ratio.value), summaries: summaries, membership: membership) var placement = Placement( result: LayoutResult(visibleWindows: visible), edges: mode.collectingEdges ? [] : nil) if case .frames = mode { placement.result.frames.reserveCapacity(workspace.order.count) } if case .edges = mode { placement.edges?.reserveCapacity(max(0, summaries[root].tileCount - 1)) } place(tree, summary: root, in: area, context: context, mode: mode, placement: &placement) if case .frames = mode { placement.result.cannotFit = placement.failedWindows.sorted() } return (placement.result, placement.edges ?? []) } private static func balancingDividers(_ tree: TileTree, axis: Axis) -> Int { var pending: [(tree: TileTree, expanded: Bool)] = [(tree, false)] var values: [Int] = [] while let (node, expanded) = pending.popLast() { switch node { case .tile, .partition: values.append(0) case .split(let splitAxis, _, let first, let second): if expanded { let right = values.removeLast() let left = values.removeLast() values.append(splitAxis == axis ? left + right + 1 : max(left, right)) } else { pending.append((node, true)) pending.append((second, false)) pending.append((first, false)) } } } return values.removeLast() } static func balancedFraction(_ tree: TileTree) -> Double { switch tree { case .tile, .partition: return 0.5 case .split(let axis, _, let first, let second): let firstUnits = Double(balancingDividers(first, axis: axis) + 1) let secondUnits = Double(balancingDividers(second, axis: axis) + 1) return firstUnits / (firstUnits + secondUnits) } } static func minimum(_ tree: TileTree, gap: Double, windows: [WindowID: ManagedWindow]) -> Size { tree.fold( { stackMinimum($0, windows: windows) }, { node, first, second in switch node { case .tile: preconditionFailure("A branch must have children") case .split(let axis, _, _, _), .partition(let axis, _, _, _): return combinedMinimum(first, second, axis: axis, gap: gap) } }) } private static func stackMinimum(_ stack: WindowStack, windows: [WindowID: ManagedWindow]) -> Size { stack.windows.reduce(Size()) { size, window in let learned = windows[window]?.minimumSize ?? Size() return Size( width: max(size.width, learned.width.rounded(.up)), height: max(size.height, learned.height.rounded(.up))) } } private static func combinedMinimum(_ left: Size, _ right: Size, axis: Axis, gap: Double) -> Size { if axis == .horizontal { let reservedGap = left.width > 0 || right.width > 0 ? gap : 0 return Size(width: left.width + reservedGap + right.width, height: max(left.height, right.height)) } let reservedGap = left.height > 0 || right.height > 0 ? gap : 0 return Size(width: max(left.width, right.width), height: left.height + reservedGap + right.height) } private struct EdgeMembership { var windows: [WindowID] = [] var ranges: [Range] = [] init(capacity: Int) { windows.reserveCapacity(capacity) ranges.reserveCapacity(max(1, capacity * 2 - 1)) } } private struct PlacementSummary { var children: (first: Int, second: Int)? let axis: Axis? let balances: Bool let horizontal: Int let vertical: Int let balancedHorizontal: Int let balancedVertical: Int let tileCount: Int let containsFocus: Bool var minimum: Size func dividers(axis: Axis, accordion: Bool) -> Int { if accordion { return axis == .horizontal ? horizontal : vertical } return axis == .horizontal ? balancedHorizontal : balancedVertical } } private static func summarize( _ tree: TileTree, windows: [WindowID: ManagedWindow], focus: WindowID?, mode: PlacementMode, summaries: inout [PlacementSummary], visible: inout [WindowID], membership: inout EdgeMembership? ) -> Int { var pending: [(tree: TileTree, parent: Int?, second: Bool)] = [(tree, nil, false)] while let (node, parent, secondChild) = pending.popLast() { let index = summaries.count if let parent { guard let children = summaries[parent].children else { preconditionFailure("A parent must have child indices") } summaries[parent].children = secondChild ? (children.first, index) : (index, children.second) } switch node { case .tile(let stack): if case .frames = mode { visible.append(stack.visible) } if let start = membership?.windows.count { membership?.windows.append(contentsOf: stack.windows) membership?.ranges.append(start..<(start + stack.windows.count)) } summaries.append( PlacementSummary( children: nil, axis: nil, balances: false, horizontal: 0, vertical: 0, balancedHorizontal: 0, balancedVertical: 0, tileCount: 1, containsFocus: focus.map { stack.windows.contains($0) } ?? false, minimum: stackMinimum(stack, windows: windows))) case .split(let axis, _, let first, let second), .partition(let axis, _, let first, let second): let balances: Bool if case .split = node { balances = true } else { balances = false } summaries.append( PlacementSummary( children: (0, 0), axis: axis, balances: balances, horizontal: 0, vertical: 0, balancedHorizontal: 0, balancedVertical: 0, tileCount: 0, containsFocus: false, minimum: Size())) if let start = membership?.windows.count { membership?.ranges.append(start.. Size { var pending = [(index, false)] var values: [Size] = [] while let (current, expanded) = pending.popLast() { let summary = summaries[current] if let children = summary.children, let axis = summary.axis { if expanded { let second = values.removeLast() let first = values.removeLast() values.append(LayoutEngine.combinedMinimum(first, second, axis: axis, gap: gap)) } else { pending.append((current, true)) pending.append((children.second, false)) pending.append((children.first, false)) } } else { values.append(summary.minimum) } } guard let result = values.last else { preconditionFailure("A subtree must have a minimum") } return result } } private struct Placement { var result: LayoutResult var edges: [TileEdge]? var failedWindows: Set = [] } private static func place( _ tree: TileTree, summary: Int, in area: Rect, context: PlacementContext, mode: PlacementMode, placement: inout Placement ) { let gap = context.gap let windows = context.windows let accordionFocus = context.accordionFocus let accordionWeight = context.accordionWeight let targetPath = mode.targetPath var path: [TileEdge.Child] = [] var pending: [(tree: TileTree, summary: Int, area: Rect, depth: Int, child: TileEdge.Child?)] = [ (tree, summary, area, 0, nil) ] while let (tree, summary, area, depth, child) = pending.popLast() { switch tree { case .tile(let stack): if let targetPath, depth < targetPath.count { continue } switch mode { case .frames: let rounded = area.roundedToWholePoints() let minimum = context.summaries[summary].minimum let fits = rounded.size.width >= minimum.width && rounded.size.height >= minimum.height for window in stack.windows { placement.result.frames[window] = area if !fits, let minimum = windows[window]?.minimumSize, rounded.size.width < minimum.width || rounded.size.height < minimum.height { placement.failedWindows.insert(window) } else if !placement.failedWindows.isEmpty { placement.failedWindows.remove(window) } } case .cannotFit: let rounded = area.roundedToWholePoints() for window in stack.windows { if let minimum = windows[window]?.minimumSize, rounded.size.width < minimum.width || rounded.size.height < minimum.height { placement.result.cannotFit.append(window) } } case .edges, .edge: break } case .split(let axis, let fraction, let first, let second), .partition(let axis, let fraction, let first, let second): if case .edges = mode, let child { path.removeLast(path.count - (depth - 1)) path.append(child) } guard let children = context.summaries[summary].children else { preconditionFailure("A split must have child summaries") } let firstSummary = context.summaries[children.first] let secondSummary = context.summaries[children.second] let extent = axis == .horizontal ? area.size.width : area.size.height let dividerCount = context.summaries[summary].dividers(axis: axis, accordion: accordionFocus != nil) + (accordionFocus == nil ? 0 : 1) let localGap = min(gap, extent / Double(max(1, dividerCount))) let available = max(0, extent - localGap) let firstMinimum = localGap == gap ? firstSummary.minimum : context.minimum(summary: children.first, gap: localGap) let secondMinimum = localGap == gap ? secondSummary.minimum : context.minimum(summary: children.second, gap: localGap) let lower = axis == .horizontal ? firstMinimum.width : firstMinimum.height let upper = axis == .horizontal ? secondMinimum.width : secondMinimum.height let balancesContent: Bool if case .split = tree { balancesContent = true } else { balancesContent = false } let firstDividers = firstSummary.dividers(axis: axis, accordion: accordionFocus != nil) let secondDividers = secondSummary.dividers(axis: axis, accordion: accordionFocus != nil) let firstGaps = balancesContent || accordionFocus != nil ? Double(firstDividers) * localGap : 0 let secondGaps = balancesContent || accordionFocus != nil ? Double(secondDividers) * localGap : 0 let contentExtent = max(0, available - firstGaps - secondGaps) let effectiveFraction: Double if accordionFocus != nil { let firstWeight = Double(firstSummary.tileCount) + (firstSummary.containsFocus ? accordionWeight - 1 : 0) let secondWeight = Double(secondSummary.tileCount) + (secondSummary.containsFocus ? accordionWeight - 1 : 0) effectiveFraction = firstWeight / (firstWeight + secondWeight) } else { effectiveFraction = fraction } let desired = contentExtent * min(1, max(0, effectiveFraction)) + firstGaps let length: Double if lower + upper <= available { length = min(available - upper, max(lower, desired)) } else { // Conflicting minimums must not push any tile off-screen. let firstGapBudget = Double(firstSummary.dividers(axis: axis, accordion: true)) * localGap let secondGapBudget = Double(secondSummary.dividers(axis: axis, accordion: true)) * localGap let gapScale = firstGapBudget + secondGapBudget > 0 ? min(1, available / (firstGapBudget + secondGapBudget)) : 1 let requiredFirstGaps = firstGapBudget * gapScale let requiredSecondGaps = secondGapBudget * gapScale let content = max(0, available - requiredFirstGaps - requiredSecondGaps) let firstContent = max(0, lower - requiredFirstGaps) let totalContent = firstContent + max(0, upper - requiredSecondGaps) length = requiredFirstGaps + (totalContent > 0 ? content * firstContent / totalContent : 0) } let left: Rect let right: Rect if axis == .horizontal { left = Rect(x: area.minX, y: area.minY, width: length, height: area.size.height) right = Rect( x: area.minX + length + localGap, y: area.minY, width: max(0, available - length), height: area.size.height ) } else { left = Rect(x: area.minX, y: area.minY, width: area.size.width, height: length) right = Rect( x: area.minX, y: area.minY + length + localGap, width: area.size.width, height: max(0, available - length) ) } if mode.collectingEdges && (targetPath == nil || depth == targetPath?.count) { guard let membership = context.membership else { preconditionFailure("Edges need prepared membership") } let roundedArea = area.roundedToWholePoints() let roundedLeft = left.roundedToWholePoints() let roundedRight = right.roundedToWholePoints() let frame: Rect if axis == .horizontal { frame = Rect( x: roundedLeft.maxX, y: roundedArea.minY, width: roundedRight.minX - roundedLeft.maxX, height: roundedArea.size.height) } else { frame = Rect( x: roundedArea.minX, y: roundedLeft.maxY, width: roundedArea.size.width, height: roundedRight.minY - roundedLeft.maxY) } placement.edges?.append( TileEdge( workspace: context.workspace, path: targetPath ?? path, firstWindows: Array(membership.windows[membership.ranges[children.first]]), secondWindows: Array(membership.windows[membership.ranges[children.second]]), axis: axis, fraction: fraction, frame: frame, geometry: area, gap: localGap, firstExtent: length, contentExtent: contentExtent, firstGapExtent: firstGaps, topology: context.topology, minimums: TileEdgeMinimums(first: firstMinimum, second: secondMinimum) ) ) } if let targetPath, depth < targetPath.count { let child = targetPath[depth] pending.append( child == .first ? (first, children.first, left, depth + 1, child) : (second, children.second, right, depth + 1, child)) } else if case .edge = mode { return } else { pending.append((second, children.second, right, depth + 1, .second)) pending.append((first, children.first, left, depth + 1, .first)) } } } } }