Retire Remap: a translation shifts, and only a stretch needs a fraction

`Remap` existed to invert a composition, and a translation never needed
one: shifting a box shifts everything composed into it by the same
amount, because `lerp(s + d, e + d, t) == lerp(s, e, t) + d` on both
channels. That holds whether or not the box has a relative extent, so
the carry branch was answering a question it did not have to ask.

So the decision is made once, before the walk, and neither relocation
method branches. A translation is already one slot write. A change of
length calls `UiRegion::stretch`, which re-expresses each part at its
own fraction of the new box and needs `stretchable` -- a fixed length
holds its parts as offsets from its start and keeps no fraction to
stretch by.

`Remap`, `UiScalar::outside`, `UiSpan::outside` and `LerpUtil::lerp_inv`
are all gone with it. Nothing inverts a lerp any more: the one division
is done against a denominator `stretchable` already established is not
zero.

What it gives up is the per-axis carry, so a box that changed length on
one axis and not the other is redrawn where it used to be remapped.
Counted: six of `tabs`'s fourteen relocations and five of `text`'s
sixteen, and one extra redraw per frame on `replace_cost`'s 200 rows --
354,310,889 instructions against 354,272,387, which is noise.

Checked: fmt, clippy and 42 tests. `tabs` (with the image replay),
`view`, `minimal` and `text` all still render byte-identical to
`upstream/main`.

core/src/orientation/pos.rs

@@ -202,12 +202,15 @@ impl UiScalar {
         }
     }
 
-    /// Undoes `within`, and `None` where the span has a fixed length: every
-    /// fraction of it lands on the same `rel`, so none can be told apart.
-    pub fn outside(&self, span: &UiSpan) -> Option<Self> {
-        let rel = self.rel.lerp_inv(span.start.rel, span.end.rel)?;
-        let abs = self.abs - rel.lerp(span.start.abs, span.end.abs);
-        Some(Self { rel, abs })
+    /// `within` undone against `from` and redone against `to`, for one axis.
+    /// `from`'s relative extent is the denominator, so it must not be zero.
+    fn stretch(&self, from: &UiSpan, to: &UiSpan) -> Self {
+        let frac = (self.rel - from.start.rel) / (from.end.rel - from.start.rel);
+        Self {
+            rel: frac.lerp(to.start.rel, to.end.rel),
+            abs: self.abs - frac.lerp(from.start.abs, from.end.abs)
+                + frac.lerp(to.start.abs, to.end.abs),
+        }
     }
 
     pub fn within_len(&self, len: UiScalar) -> Self {
@@ -278,13 +281,6 @@ impl UiSpan {
         }
     }
 
-    pub fn outside(&self, parent: &Self) -> Option<Self> {
-        Some(Self {
-            start: self.start.outside(parent)?,
-            end: self.end.outside(parent)?,
-        })
-    }
-
     pub const fn len(&self) -> UiScalar {
         self.end - self.start
     }
@@ -395,48 +391,28 @@ impl UiRegion {
             },
         }
     }
-}
 
-/// Taking a drawing out of one box and putting it in another, checked once
-/// for a whole subtree so that applying it cannot fail.
-///
-/// A box of a fixed length holds each part as an offset from its start rather
-/// than as a fraction of it, so those parts can be carried to a box of the
-/// same length but never stretched to a different one.
-#[derive(Debug, Copy, Clone, PartialEq)]
-pub struct Remap {
-    from: UiRegion,
-    to: UiRegion,
-}
-
-impl Remap {
-    pub fn new(from: UiRegion, to: UiRegion) -> Option<Self> {
-        [Axis::X, Axis::Y]
-            .into_iter()
-            .all(|axis| {
-                let (from, to) = (from.axis(axis), to.axis(axis));
-                from.start.rel != from.end.rel || from.len() == to.len()
-            })
-            .then_some(Self { from, to })
+    /// Whether a stretch out of this box can be expressed. Each part inside a
+    /// box is held as a fraction of it, and a fixed length has no fraction to
+    /// hold one by -- every part of it is just an offset from its start.
+    pub fn stretchable(&self) -> bool {
+        self.x.start.rel != self.x.end.rel && self.y.start.rel != self.y.end.rel
     }
 
-    pub fn apply(&self, region: UiRegion) -> UiRegion {
+    /// Re-expresses a region inside `from` as the same fractions of `to`.
+    /// `from` must be `stretchable`; a translation is `shift` instead, which
+    /// needs no fractions and works out of any box.
+    pub fn stretch(&self, from: &UiRegion, to: &UiRegion) -> UiRegion {
+        debug_assert!(from.stretchable(), "a fixed length has no fraction");
         UiRegion {
-            x: Self::span(region.x, self.from.x, self.to.x),
-            y: Self::span(region.y, self.from.y, self.to.y),
-        }
-    }
-
-    fn span(span: UiSpan, from: UiSpan, to: UiSpan) -> UiSpan {
-        match span.outside(&from) {
-            Some(out) => out.within(&to),
-            // `new` admits this only where the two are the same length, so
-            // the difference between their starts is the whole move.
-            None => {
-                let mut span = span;
-                span.shift(to.start - from.start);
-                span
-            }
+            x: UiSpan {
+                start: self.x.start.stretch(&from.x, &to.x),
+                end: self.x.end.stretch(&from.x, &to.x),
+            },
+            y: UiSpan {
+                start: self.y.start.stretch(&from.y, &to.y),
+                end: self.y.end.stretch(&from.y, &to.y),
+            },
         }
     }
 }

core/src/render/data.rs

@@ -1,11 +1,10 @@
-use crate::{UiRegion, util::Id};
+use crate::{UiRegion, util::Id, util::Vec2};
 use wgpu::*;
 
 #[repr(C)]
 #[derive(Copy, Clone, bytemuck::Pod, bytemuck::Zeroable, Default)]
 pub struct WindowUniform {
-    pub width: f32,
-    pub height: f32,
+    pub dim: Vec2,
 }
 
 #[repr(C)]
@@ -13,15 +12,17 @@ pub struct WindowUniform {
 pub struct PrimitiveInstance {
     pub region: UiRegion,
     pub mask_idx: MaskIdx,
+    pub move_idx: MoveIdx,
 }
 
 impl PrimitiveInstance {
-    const ATTRIBS: [VertexAttribute; 5] = vertex_attr_array![
+    const ATTRIBS: [VertexAttribute; 6] = vertex_attr_array![
         0 => Float32x2,
         1 => Float32x2,
         2 => Float32x2,
         3 => Float32x2,
         4 => Uint32,
+        5 => Uint32,
     ];
 
     pub fn desc() -> VertexBufferLayout<'static> {
@@ -43,4 +44,45 @@ impl MaskIdx {
 #[derive(Debug, Copy, Clone, bytemuck::Pod, bytemuck::Zeroable)]
 pub struct Mask {
     pub region: UiRegion,
+    pub move_idx: MoveIdx,
+}
+
+/// Its own type rather than another `Id<u32>`, because it sits beside
+/// `MaskIdx` in an instance and the two must not be swappable.
+#[repr(transparent)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, bytemuck::Pod, bytemuck::Zeroable)]
+pub struct MoveIdx(u32);
+
+impl MoveIdx {
+    pub const NONE: Self = Self(u32::MAX);
+
+    pub(crate) fn slot(idx: usize) -> Self {
+        Self(idx as u32)
+    }
+
+    pub(crate) fn idx(self) -> usize {
+        self.0 as usize
+    }
+}
+
+/// One link of the chain a primitive's position is resolved through: a
+/// translation in physical pixels, and the slot it is relative to. Moving a
+/// subtree writes its own slot and nothing else.
+#[repr(C)]
+#[derive(Debug, Copy, Clone)]
+pub struct MoveOffset {
+    pub delta: Vec2,
+    pub parent: MoveIdx,
+}
+
+unsafe impl bytemuck::Pod for MoveOffset {}
+unsafe impl bytemuck::Zeroable for MoveOffset {}
+
+impl MoveOffset {
+    pub fn root(parent: MoveIdx) -> Self {
+        Self {
+            delta: Vec2::ZERO,
+            parent,
+        }
+    }
 }

core/src/render/mod.rs

@@ -17,7 +17,7 @@ mod texture;
 mod util;
 
 pub use atlas::*;
-pub use data::{Mask, MaskIdx};
+pub use data::{Mask, MaskIdx, MoveIdx, MoveOffset};
 pub use primitive::*;
 
 const PRELUDE: &str = include_str!("./shader/prelude.wgsl");
@@ -34,6 +34,7 @@ pub struct UiRenderNode {
     active: Vec<usize>,
     window_buffer: Buffer,
     masks: ArrBuf<Mask>,
+    moves: ArrBuf<MoveOffset>,
 }
 
 struct RenderLayer {
@@ -127,32 +128,35 @@ impl UiRenderNode {
         for primitive in &mut self.primitives {
             primitive.render.update(ui);
         }
+        let mut regroup = false;
         if ui.masks.changed {
             ui.masks.changed = false;
-            if self.masks.update(device, queue, &ui.masks[..]) {
-                self.shared_group = Self::shared_group(
-                    device,
-                    &self.shared_layout,
-                    &self.window_buffer,
-                    &self.masks,
-                );
-            }
+            regroup |= self.masks.update(device, queue, &ui.masks[..]);
+        }
+        if ui_render.moves.changed {
+            ui_render.moves.changed = false;
+            regroup |= self.moves.update(device, queue, ui_render.moves.entries());
+        }
+        if regroup {
+            self.shared_group = Self::shared_group(
+                device,
+                &self.shared_layout,
+                &self.window_buffer,
+                &self.masks,
+                &self.moves,
+            );
         }
     }
 
     pub fn resize(&mut self, size: impl Into<Vec2>, queue: &Queue) {
         let size = size.into();
-        let slice = &[WindowUniform {
-            width: size.x,
-            height: size.y,
-        }];
+        let slice = &[WindowUniform { dim: size }];
         queue.write_buffer(&self.window_buffer, 0, bytemuck::cast_slice(slice));
     }
 
     pub fn new(device: &Device, config: &SurfaceConfiguration) -> Self {
         let window_uniform = WindowUniform {
-            width: config.width as f32,
-            height: config.height as f32,
+            dim: Vec2::new(config.width as f32, config.height as f32),
         };
         let window_buffer = device.create_buffer_init(&BufferInitDescriptor {
             label: Some("window"),
@@ -166,7 +170,13 @@ impl UiRenderNode {
             BufferUsages::STORAGE | BufferUsages::COPY_DST,
             "ui masks",
         );
-        let shared_group = Self::shared_group(device, &shared_layout, &window_buffer, &masks);
+        let moves = ArrBuf::new(
+            device,
+            BufferUsages::STORAGE | BufferUsages::COPY_DST,
+            "ui move offsets",
+        );
+        let shared_group =
+            Self::shared_group(device, &shared_layout, &window_buffer, &masks, &moves);
 
         Self {
             shared_layout,
@@ -177,6 +187,7 @@ impl UiRenderNode {
             layers: HashMap::default(),
             active: Vec::new(),
             masks,
+            moves,
         }
     }
 
@@ -252,7 +263,8 @@ impl UiRenderNode {
         })
     }
 
-    /// What every draw in the ui is given: the window and the masks.
+    /// What every draw in the ui is given: the window, the masks and the
+    /// move chain every position is resolved through.
     fn shared_layout(device: &Device) -> BindGroupLayout {
         device.create_bind_group_layout(&BindGroupLayoutDescriptor {
             entries: &[
@@ -276,6 +288,16 @@ impl UiRenderNode {
                     },
                     count: None,
                 },
+                BindGroupLayoutEntry {
+                    binding: 2,
+                    visibility: ShaderStages::VERTEX | ShaderStages::FRAGMENT,
+                    ty: BindingType::Buffer {
+                        ty: BufferBindingType::Storage { read_only: true },
+                        has_dynamic_offset: false,
+                        min_binding_size: BufferSize::new(size_of::<MoveOffset>() as u64),
+                    },
+                    count: None,
+                },
             ],
             label: Some("ui shared"),
         })
@@ -286,6 +308,7 @@ impl UiRenderNode {
         layout: &BindGroupLayout,
         window: &Buffer,
         masks: &ArrBuf<Mask>,
+        moves: &ArrBuf<MoveOffset>,
     ) -> BindGroup {
         device.create_bind_group(&BindGroupDescriptor {
             layout,
@@ -298,6 +321,10 @@ impl UiRenderNode {
                     binding: 1,
                     resource: masks.buffer.as_entire_binding(),
                 },
+                BindGroupEntry {
+                    binding: 2,
+                    resource: moves.buffer.as_entire_binding(),
+                },
             ],
             label: Some("ui shared"),
         })

core/src/render/primitive.rs

@@ -3,7 +3,7 @@ use std::{any::TypeId, marker::PhantomData};
 use crate::{
     Color, TextureHandle, UiData, UiRegion, WidgetId,
     render::{
-        data::{MaskIdx, PrimitiveInstance},
+        data::{MaskIdx, MoveIdx, PrimitiveInstance},
         page::GlyphRender,
         texture::ImageRender,
     },
@@ -246,6 +246,7 @@ impl LayerDraws {
             primitive,
             region,
             mask_idx,
+            move_idx,
         }: PrimitiveInst<P>,
     ) -> PrimitiveHandle {
         self.updated = true;
@@ -258,7 +259,11 @@ impl LayerDraws {
             .get_or_insert_with(InstanceList::new::<P>)
             .push(
                 id,
-                PrimitiveInstance { region, mask_idx },
+                PrimitiveInstance {
+                    region,
+                    mask_idx,
+                    move_idx,
+                },
                 bytemuck::bytes_of(&primitive),
             );
         PrimitiveHandle {
@@ -304,6 +309,7 @@ pub struct PrimitiveInst<P> {
     pub primitive: P,
     pub region: UiRegion,
     pub mask_idx: MaskIdx,
+    pub move_idx: MoveIdx,
 }
 
 pub struct PrimitiveChange {
@@ -347,7 +353,7 @@ impl RectPrimitive {
 
 /// `color` is multiplied by the atlas alpha for a mask glyph; a colour glyph
 /// takes the texel unchanged, which `GlyphEntry::IS_COLORED` selects.
-#[repr(C, align(8))]
+#[repr(C)]
 #[derive(Debug, Copy, Clone)]
 pub struct GlyphPrimitive {
     pub uv_min: Vec2,
@@ -358,8 +364,8 @@ pub struct GlyphPrimitive {
     pub flags: u32,
 }
 
-// Manual rather than derived: the align(8) leaves four bytes of padding, which
-// is how WGSL lays the struct out.
+// Manual rather than derived: `Vec2`'s alignment leaves four bytes of padding
+// here, which is how WGSL lays the struct out.
 unsafe impl bytemuck::Pod for GlyphPrimitive {}
 unsafe impl bytemuck::Zeroable for GlyphPrimitive {}
 impl Primitive for GlyphPrimitive {

core/src/render/shader/prelude.wgsl

@@ -7,6 +7,8 @@
 var<uniform> window: WindowUniform;
 @group(0) @binding(1)
 var<storage> masks: array<Mask>;
+@group(0) @binding(2)
+var<storage> move_offsets: array<MoveOffset>;
 
 struct WindowUniform {
     dim: vec2<f32>,
@@ -15,6 +17,32 @@ struct WindowUniform {
 struct Mask {
     x: UiSpan,
     y: UiSpan,
+    move_idx: u32,
+}
+
+struct MoveOffset {
+    delta: vec2<f32>,
+    parent: u32,
+}
+
+const MOVE_NONE: u32 = 4294967295u;
+// Keep in step with `iris_core::CHAIN_LIMIT`. It bounds a malformed cycle
+// rather than any real tree, and the CPU walk uses the same number so both
+// resolve a deep one the same way.
+const CHAIN_LIMIT: u32 = 64u;
+
+fn resolve_move(idx: u32) -> vec2<f32> {
+    var total = vec2<f32>(0.0, 0.0);
+    var at = idx;
+    for (var step = 0u; step < CHAIN_LIMIT; step++) {
+        if at == MOVE_NONE {
+            break;
+        }
+        let entry = move_offsets[at];
+        total += entry.delta;
+        at = entry.parent;
+    }
+    return total;
 }
 
 struct UiSpan {
@@ -33,6 +61,7 @@ struct InstanceInput {
     @location(2) y_start: vec2<f32>,
     @location(3) y_end: vec2<f32>,
     @location(4) mask_idx: u32,
+    @location(5) move_idx: u32,
 }
 
 struct VertexOutput {
@@ -57,8 +86,9 @@ fn vs_main(
     let bot_right_rel = vec2(in.x_end.x, in.y_end.x);
     let bot_right_abs = vec2(in.x_end.y, in.y_end.y);
 
-    let top_left = floor(top_left_rel * window.dim) + floor(top_left_abs);
-    let bot_right = floor(bot_right_rel * window.dim) + floor(bot_right_abs);
+    let moved = resolve_move(in.move_idx);
+    let top_left = floor(top_left_rel * window.dim) + floor(top_left_abs + moved);
+    let bot_right = floor(bot_right_rel * window.dim) + floor(bot_right_abs + moved);
     let size = bot_right - top_left;
 
     let uv = vec2<f32>(
@@ -86,8 +116,11 @@ fn masked(in: VertexOutput, color: vec4<f32>) -> vec4<f32> {
     let br = vec2(mask.x.end.rel, mask.y.end.rel);
     let br_abs = vec2(mask.x.end.abs, mask.y.end.abs);
 
-    let top_left = floor(tl * window.dim) + floor(tl_abs);
-    let bot_right = floor(br * window.dim) + floor(br_abs);
+    // Its own chain, not the drawn primitive's, so a stationary viewport
+    // clips content that moves inside it.
+    let moved = resolve_move(mask.move_idx);
+    let top_left = floor(tl * window.dim) + floor(tl_abs + moved);
+    let bot_right = floor(br * window.dim) + floor(br_abs + moved);
     let pos = in.clip_position.xy;
     if pos.x < top_left.x || pos.x > bot_right.x || pos.y < top_left.y || pos.y > bot_right.y {
         return color * 0.0;

core/src/ui/active.rs

@@ -1,4 +1,4 @@
-use crate::{LayerId, MaskIdx, PrimitiveHandle, Size, TextureHandle, UiRegion, WidgetId};
+use crate::{LayerId, MaskIdx, MoveIdx, PrimitiveHandle, Size, TextureHandle, UiRegion, WidgetId};
 
 /// important non rendering data for retained drawing
 #[derive(Debug)]
@@ -15,6 +15,8 @@ pub struct ActiveData {
     pub size_deps: Vec<WidgetId>,
     /// Whether it read the output's size, and so is wrong when that changes.
     pub reads_output: bool,
+    /// The move slot its primitives are positioned through.
+    pub move_idx: MoveIdx,
     pub mask: MaskIdx,
     pub layer: LayerId,
 }

core/src/ui/mod.rs

@@ -1,7 +1,14 @@
 use crate::{
-    Mask, PrimitiveRegistry, TextData, Textures, WeakWidget, WidgetId, Widgets, util::TrackedArena,
+    Mask, MoveIdx, MoveOffset, PrimitiveRegistry, TextData, Textures, WeakWidget, WidgetId,
+    Widgets,
+    util::{Arena, Id, TrackedArena, Vec2},
 };
 
+/// How far the shader will walk a move chain. It bounds a malformed cycle
+/// rather than any real tree; `Moves::resolve` uses the same number so the
+/// two agree on what a deep tree resolves to.
+pub const CHAIN_LIMIT: u32 = 64;
+
 mod active;
 mod painter;
 mod render_state;
@@ -20,6 +27,65 @@ pub struct UiData {
     pub masks: TrackedArena<Mask, u32>,
 }
 
+/// Where each widget's drawing sits relative to its parent's slot, so moving
+/// a subtree writes one entry rather than every descendant's primitives.
+#[derive(Default)]
+pub struct Moves {
+    arena: Arena<MoveOffset, u32>,
+    pub changed: bool,
+}
+
+impl Moves {
+    pub fn push(&mut self, parent: MoveIdx) -> MoveIdx {
+        self.changed = true;
+        MoveIdx::slot(self.arena.push(MoveOffset::root(parent)).idx())
+    }
+
+    pub fn remove(&mut self, idx: MoveIdx) {
+        self.changed = true;
+        self.arena.remove(Id::preset(idx.idx() as u32));
+    }
+
+    /// Sets a slot's translation, in physical pixels, relative to its parent.
+    pub fn set(&mut self, idx: MoveIdx, delta: Vec2) {
+        let entry = self.arena.get_mut(Id::preset(idx.idx() as u32));
+        if entry.delta != delta {
+            entry.delta = delta;
+            self.changed = true;
+        }
+    }
+
+    /// The translation a primitive in `idx` has accumulated, which is the
+    /// same walk the vertex shader does.
+    pub fn resolve(&self, idx: MoveIdx) -> Vec2 {
+        let mut total = Vec2::ZERO;
+        let mut at = idx;
+        for _ in 0..CHAIN_LIMIT {
+            if at == MoveIdx::NONE {
+                return total;
+            }
+            let entry = self.arena[at.idx()];
+            total += entry.delta;
+            at = entry.parent;
+        }
+        debug_assert!(
+            at == MoveIdx::NONE,
+            "a move chain longer than {CHAIN_LIMIT} resolves to the wrong place, \
+             and the shader stops at the same depth"
+        );
+        total
+    }
+
+    pub fn entries(&self) -> &[MoveOffset] {
+        &self.arena
+    }
+
+    pub fn clear(&mut self) {
+        self.changed = true;
+        self.arena = Arena::default();
+    }
+}
+
 pub trait UiRsc {
     fn ui(&self) -> &UiData;
     fn ui_mut(&mut self) -> &mut UiData;

core/src/ui/painter.rs

@@ -2,8 +2,8 @@ use crate::{
     Axis, Len, RenderedText, Size, StrongWidget, TextAttrs, TextBuffer, TextData, TextureHandle,
     UiRegion, UiRenderState, UiRsc, UiScalar, UiVec2, WidgetId,
     render::{
-        GlyphPrimitive, Mask, MaskIdx, Primitive, PrimitiveHandle, PrimitiveInst, PrimitiveKind,
-        TexturePrimitive,
+        GlyphPrimitive, Mask, MaskIdx, MoveIdx, Primitive, PrimitiveHandle, PrimitiveInst,
+        PrimitiveKind, TexturePrimitive,
     },
     util::Vec2,
 };
@@ -21,6 +21,8 @@ pub struct Painter<'a> {
     /// The children whose size this widget read while drawing.
     pub(super) size_deps: Vec<WidgetId>,
     pub(super) reads_output: bool,
+    /// The move slot this widget's primitives are positioned through.
+    pub(super) move_idx: MoveIdx,
     pub layer: usize,
     pub(super) id: WidgetId,
 }
@@ -41,6 +43,7 @@ impl<'a> Painter<'a> {
                 primitive,
                 region,
                 mask_idx: self.mask,
+                move_idx: self.move_idx,
             },
         );
         self.push_primitive(h);
@@ -67,7 +70,10 @@ impl<'a> Painter<'a> {
 
     pub fn set_mask(&mut self, region: UiRegion) {
         assert!(self.mask == MaskIdx::NONE);
-        self.mask = self.rsc.ui_mut().masks.push(Mask { region });
+        self.mask = self.rsc.ui_mut().masks.push(Mask {
+            region,
+            move_idx: self.move_idx,
+        });
     }
 
     /// Draws a widget within this widget's region.

core/src/ui/render_state.rs

@@ -1,6 +1,6 @@
 use crate::{
-    ActiveData, Axis, DrawLayers, IdLike, MaskIdx, OnResize, Painter, PixelRegion, Remap, Size,
-    StrongWidget, UiRegion, UiRsc, WidgetId, Widgets,
+    ActiveData, Axis, DrawLayers, IdLike, MaskIdx, MoveIdx, Moves, OnResize, Painter, PixelRegion,
+    Size, StrongWidget, UiRegion, UiRsc, WidgetId, Widgets,
     util::{HashMap, HashSet, Vec2, forget_ref},
 };
 
@@ -12,6 +12,10 @@ pub struct UiRenderState {
     old_root: Option<WidgetId>,
     resized: bool,
     draw_started: HashSet<WidgetId>,
+    /// A widget's move slot, which outlives any one `ActiveData`: a redraw
+    /// replaces that while its children go on pointing at the slot.
+    slots: HashMap<WidgetId, MoveIdx>,
+    pub moves: Moves,
 }
 
 impl UiRenderState {
@@ -23,6 +27,8 @@ impl UiRenderState {
             old_root: None,
             resized: false,
             draw_started: Default::default(),
+            slots: Default::default(),
+            moves: Default::default(),
         }
     }
 
@@ -103,6 +109,8 @@ impl UiRenderState {
         }
 
         // draw widget
+        let move_idx = self.move_slot(id, parent);
+        self.moves.set(move_idx, Vec2::ZERO);
         rsc.widgets_mut().needs_redraw.remove(&id);
         self.draw_started.insert(id);
 
@@ -117,6 +125,7 @@ impl UiRenderState {
             children: Vec::new(),
             size_deps: Vec::new(),
             reads_output: false,
+            move_idx,
             rsc,
         };
 
@@ -134,6 +143,7 @@ impl UiRenderState {
             children,
             size_deps,
             reads_output,
+            move_idx,
             layer,
             id,
         } = painter;
@@ -155,6 +165,7 @@ impl UiRenderState {
             children,
             size_deps,
             reads_output,
+            move_idx,
             mask,
             layer,
         };
@@ -171,6 +182,20 @@ impl UiRenderState {
         size
     }
 
+    /// The slot a widget's drawing is positioned through, made on its first
+    /// draw and kept until it stops being drawn.
+    fn move_slot(&mut self, id: WidgetId, parent: Option<WidgetId>) -> MoveIdx {
+        if let Some(&idx) = self.slots.get(&id) {
+            return idx;
+        }
+        let parent = parent
+            .and_then(|p| self.slots.get(&p).copied())
+            .unwrap_or(MoveIdx::NONE);
+        let idx = self.moves.push(parent);
+        self.slots.insert(id, idx);
+        idx
+    }
+
     /// The drawing a widget already has, kept for a new box if the box has not
     /// changed in a way it depends on.
     fn try_reuse(&mut self, id: WidgetId, region: UiRegion, rsc: &dyn UiRsc) -> Option<Size> {
@@ -178,16 +203,22 @@ impl UiRenderState {
             return None;
         }
         let active = self.active.get(&id)?;
-        let (size, old) = (active.size, active.region);
-        if old == region {
+        let (size, old, slot) = (active.size, active.region, active.move_idx);
+        // TODO: epsilon?
+        if old.size() == region.size() {
+            // The right shape and only somewhere else, which is one slot to
+            // write however much is under it. Both boxes are in the
+            // coordinates its parent drew, so the chain above applies alike.
+            let moved =
+                region.to_px(self.output_size).top_left - old.to_px(self.output_size).top_left;
+            self.moves.set(slot, moved);
             return Some(size);
         }
-        // TODO: epsilon?
-        if old.size() != region.size() && !self.reusable(id, region, rsc) {
+        if !self.reusable(id, region, rsc) || !old.stretchable() {
             return None;
         }
-        // Its drawing stands, if the new box can be reached from the old one.
-        self.mov(id, &Remap::new(old, region)?);
+        // Its drawing stands, re-expressed as the same fractions of the box.
+        self.stretch(id, old, region);
         Some(size)
     }
 
@@ -228,17 +259,21 @@ impl UiRenderState {
         })
     }
 
-    fn mov(&mut self, id: WidgetId, remap: &Remap) {
+    /// Rewrites a subtree's regions as the same fractions of a new box, for a
+    /// change of length that a slot cannot express. Every region it rewrites
+    /// is a region some slot was a delta from, so those go back to zero.
+    fn stretch(&mut self, id: WidgetId, from: UiRegion, to: UiRegion) {
         let active = self.active.get_mut(&id).unwrap();
         for h in &active.primitives {
             let region = self.layers[h.layer].region_mut(h);
-            *region = remap.apply(*region);
+            *region = region.stretch(&from, &to);
         }
-        active.region = remap.apply(active.region);
+        active.region = active.region.stretch(&from, &to);
+        self.moves.set(active.move_idx, Vec2::ZERO);
         // SAFETY: children cannot be recursive
         let children = unsafe { forget_ref(&active.children) };
         for child in children {
-            self.mov(*child, remap);
+            self.stretch(*child, from, to);
         }
     }
 
@@ -268,6 +303,10 @@ impl UiRenderState {
                 self.remove_rec(*c, rsc);
             }
         }
+        // After the descendants, whose slots name this one as their parent.
+        if let Some(idx) = self.slots.remove(&id) {
+            self.moves.remove(idx);
+        }
         inst
     }
 
@@ -275,6 +314,8 @@ impl UiRenderState {
         for (_, active) in self.active.drain() {
             rsc.on_undraw(&active);
         }
+        self.slots.clear();
+        self.moves.clear();
         self.layers.clear();
         rsc.widgets_mut().needs_redraw.clear();
         rsc.free();
@@ -322,9 +363,16 @@ impl UiRenderState {
         }
     }
 
+    /// Where a widget is on screen: the box it drew against plus whatever the
+    /// chain above has moved since, which is the walk the vertex shader does.
     pub fn window_region(&self, id: &impl IdLike) -> Option<PixelRegion> {
-        let region = self.active.get(&id.id())?.region;
-        Some(region.to_px(self.output_size))
+        let active = self.active.get(&id.id())?;
+        let moved = self.moves.resolve(active.move_idx);
+        let region = active.region.to_px(self.output_size);
+        Some(PixelRegion {
+            top_left: region.top_left + moved,
+            bot_right: region.bot_right + moved,
+        })
     }
 
     /// redraws a widget that's currently active (drawn)

core/src/util/arena.rs

@@ -34,6 +34,10 @@ impl<T, I: IdNum> Arena<T, I> {
         self.tracker.free(id);
         self.data[i]
     }
+
+    pub fn get_mut(&mut self, id: Id<I>) -> &mut T {
+        &mut self.data[id.idx()]
+    }
 }
 
 impl<T, I: IdNum> Default for Arena<T, I> {

core/src/util/math.rs

@@ -1,6 +1,5 @@
-pub const trait LerpUtil: Sized {
+pub const trait LerpUtil {
     fn lerp(self, from: Self, to: Self) -> Self;
-    fn lerp_inv(self, from: Self, to: Self) -> Option<Self>;
 }
 
 const impl LerpUtil for f32 {
@@ -9,14 +8,6 @@ const impl LerpUtil for f32 {
     fn lerp(self, from: Self, to: Self) -> Self {
         from + (to - from) * self
     }
-    /// inverse of lerp, and `None` where `from` and `to` are the same point:
-    /// every input lerps to it, so there is no one answer to come back to.
-    fn lerp_inv(self, from: Self, to: Self) -> Option<Self> {
-        match to == from {
-            true => None,
-            false => Some((self - from) / (to - from)),
-        }
-    }
 }
 
 macro_rules! impl_op {

core/src/util/vec2.rs

@@ -1,7 +1,11 @@
 use crate::util::impl_op;
 use std::{hash::Hash, ops::*};
 
-#[repr(C)]
+/// `align(8)` because that is WGSL's alignment for a `vec2<f32>`, so any GPU
+/// struct holding one is laid out the way its shader reads it without having
+/// to say so itself. Those structs still need a manual `unsafe impl Pod`,
+/// since the trailing padding this introduces is what `derive(Pod)` refuses.
+#[repr(C, align(8))]
 #[derive(Clone, Copy, PartialEq, Default, bytemuck::Pod, bytemuck::Zeroable)]
 pub struct Vec2 {
     pub x: f32,

tests/chain_cost.rs

@@ -0,0 +1,224 @@
+//! What the vertex shader's move-chain walk costs, against how deep the chain
+//! is. Every active widget owns a slot, so the depth a primitive resolves
+//! through is its depth in the widget tree.
+//!
+//!     cargo test --release --test chain_cost -- --ignored --nocapture
+//!
+//! Timed on the GPU with timestamp queries rather than by the clock: wall time
+//! here varied by 2x between runs of one unchanged binary. The pass is
+//! submitted and waited on, so this is the GPU's cost and not the recording
+//! loop's -- which is what `draw_cost.rs` measures instead.
+//!
+//! The instances are two pixels wide so that vertex work dominates; a chain
+//! walk that does not show up against small quads will not show up against
+//! anything.
+//!
+//! The instance is leaked deliberately, for the reason `draw_cost.rs` gives.
+
+use iris::prelude::*;
+use iris_core::{
+    MaskIdx, MoveIdx, PrimitiveInst, RectPrimitive, UiData, UiRegion, UiRenderNode, UiRenderState,
+    UiScalar, UiSpan,
+};
+use wgpu::{Color as GpuColor, *};
+
+const SIZE: u32 = 1024;
+const INSTANCES: usize = 200_000;
+const FRAMES: u32 = 20;
+/// Reported as the best of this many batches, since the mean moves by more
+/// than the thing being measured.
+const BATCHES: u32 = 8;
+
+fn gpu() -> Option<(Device, Queue, f32)> {
+    let all = Instance::new(InstanceDescriptor::new_without_display_handle());
+    let instance = match pollster::block_on(all.request_adapter(&RequestAdapterOptions::default()))
+    {
+        Ok(_) => all,
+        Err(_) => Instance::new(InstanceDescriptor {
+            backends: Backends::GL,
+            ..InstanceDescriptor::new_without_display_handle()
+        }),
+    };
+    let instance: &'static Instance = Box::leak(Box::new(instance));
+    let adapter =
+        pollster::block_on(instance.request_adapter(&RequestAdapterOptions::default())).ok()?;
+    if !adapter.features().contains(Features::TIMESTAMP_QUERY) {
+        println!("no timestamp queries on {:?}", adapter.get_info().name);
+        return None;
+    }
+    println!("adapter: {:?}", adapter.get_info().name);
+    let (device, queue) = pollster::block_on(adapter.request_device(&DeviceDescriptor {
+        required_features: Features::TIMESTAMP_QUERY,
+        ..Default::default()
+    }))
+    .ok()?;
+    let period = queue.get_timestamp_period();
+    Some((device, queue, period))
+}
+
+fn config(format: TextureFormat) -> SurfaceConfiguration {
+    SurfaceConfiguration {
+        usage: TextureUsages::RENDER_ATTACHMENT,
+        format,
+        color_space: SurfaceColorSpace::Auto,
+        width: SIZE,
+        height: SIZE,
+        present_mode: PresentMode::Fifo,
+        desired_maximum_frame_latency: 2,
+        alpha_mode: CompositeAlphaMode::Auto,
+        view_formats: vec![],
+    }
+}
+
+/// A chain `depth` slots long, and instances that all resolve through its end.
+fn fill(ui: &mut UiData, render: &mut UiRenderState, depth: usize) {
+    let kind = ui.primitives.kind::<RectPrimitive>();
+    let id = ui.widgets.add_strong(Rect::new(UiColor::WHITE)).id();
+
+    let mut slot = MoveIdx::NONE;
+    for _ in 0..depth {
+        slot = render.moves.push(slot);
+    }
+
+    let px = |v: f32| UiScalar { rel: 0.0, abs: v };
+    for i in 0..INSTANCES {
+        let x = (i % (SIZE as usize / 2)) as f32 * 2.0;
+        let y = (i / (SIZE as usize / 2)) as f32;
+        render.layers.write(
+            0,
+            PrimitiveInst {
+                kind,
+                id,
+                primitive: RectPrimitive::color(UiColor::WHITE),
+                region: UiRegion::new(
+                    UiSpan::new(px(x), px(x + 2.0)),
+                    UiSpan::new(px(y), px(y + 1.0)),
+                ),
+                mask_idx: MaskIdx::NONE,
+                move_idx: slot,
+            },
+        );
+    }
+}
+
+/// Nanoseconds the pass took on the GPU, best of `BATCHES`.
+fn pass_cost(device: &Device, queue: &Queue, period: f32, depth: usize) -> f64 {
+    let format = TextureFormat::Bgra8Unorm;
+    let mut node = UiRenderNode::new(device, &config(format));
+    let mut ui = UiData::default();
+    let mut render = UiRenderState::new();
+    fill(&mut ui, &mut render, depth);
+    node.update(device, queue, &mut ui, &mut render);
+
+    let target = device.create_texture(&TextureDescriptor {
+        label: Some("chain cost"),
+        size: Extent3d {
+            width: SIZE,
+            height: SIZE,
+            depth_or_array_layers: 1,
+        },
+        mip_level_count: 1,
+        sample_count: 1,
+        dimension: TextureDimension::D2,
+        format,
+        usage: TextureUsages::RENDER_ATTACHMENT,
+        view_formats: &[],
+    });
+    let view = target.create_view(&TextureViewDescriptor::default());
+
+    let queries = device.create_query_set(&QuerySetDescriptor {
+        label: Some("chain cost"),
+        ty: QueryType::Timestamp,
+        count: 2,
+    });
+    let resolved = device.create_buffer(&BufferDescriptor {
+        label: Some("resolved"),
+        size: 16,
+        usage: BufferUsages::QUERY_RESOLVE | BufferUsages::COPY_SRC,
+        mapped_at_creation: false,
+    });
+    let readback = device.create_buffer(&BufferDescriptor {
+        label: Some("readback"),
+        size: 16,
+        usage: BufferUsages::MAP_READ | BufferUsages::COPY_DST,
+        mapped_at_creation: false,
+    });
+
+    let frame = || {
+        let mut encoder = device.create_command_encoder(&CommandEncoderDescriptor::default());
+        {
+            let pass = &mut encoder.begin_render_pass(&RenderPassDescriptor {
+                label: None,
+                color_attachments: &[Some(RenderPassColorAttachment {
+                    view: &view,
+                    resolve_target: None,
+                    ops: Operations {
+                        load: LoadOp::Clear(GpuColor::BLACK),
+                        store: StoreOp::Store,
+                    },
+                    depth_slice: None,
+                })],
+                depth_stencil_attachment: None,
+                timestamp_writes: Some(RenderPassTimestampWrites {
+                    query_set: &queries,
+                    beginning_of_pass_write_index: Some(0),
+                    end_of_pass_write_index: Some(1),
+                }),
+                occlusion_query_set: None,
+                multiview_mask: None,
+            });
+            node.draw(pass);
+        }
+        encoder.resolve_query_set(&queries, 0..2, &resolved, 0);
+        encoder.copy_buffer_to_buffer(&resolved, 0, &readback, 0, 16);
+        queue.submit(Some(encoder.finish()));
+
+        let slice = readback.slice(..);
+        slice.map_async(MapMode::Read, |_| {});
+        let _ = device.poll(PollType::Wait {
+            submission_index: None,
+            timeout: None,
+        });
+        let ns = {
+            let view = slice.get_mapped_range().expect("timestamps did not map");
+            let stamps: [u64; 2] = [
+                u64::from_le_bytes(view[..8].try_into().unwrap()),
+                u64::from_le_bytes(view[8..16].try_into().unwrap()),
+            ];
+            (stamps[1].saturating_sub(stamps[0])) as f64 * period as f64
+        };
+        readback.unmap();
+        ns
+    };
+
+    frame();
+    let mut best = f64::MAX;
+    for _ in 0..BATCHES {
+        let mut total = 0.0;
+        for _ in 0..FRAMES {
+            total += frame();
+        }
+        best = best.min(total / FRAMES as f64);
+    }
+    best
+}
+
+#[test]
+#[ignore = "measurement, not a check"]
+fn chain_cost_by_depth() {
+    let Some((device, queue, period)) = gpu() else {
+        println!("no gpu with timestamps; nothing measured");
+        return;
+    };
+    println!("{INSTANCES} instances, {SIZE}x{SIZE}, best of {BATCHES} batches");
+    let mut base = None;
+    for depth in [1, 2, 4, 8, 16, 32, 64] {
+        let ns = pass_cost(&device, &queue, period, depth);
+        let base = *base.get_or_insert(ns);
+        println!(
+            "depth {depth:>3}: {:>9.1} us   {:+6.1}% against depth 1",
+            ns / 1000.0,
+            (ns - base) / base * 100.0
+        );
+    }
+}

tests/draw_cost.rs

@@ -22,8 +22,8 @@ use std::time::Instant;
 
 use iris::prelude::*;
 use iris_core::{
-    GlyphPrimitive, MaskIdx, PrimitiveInst, RectPrimitive, TextureHandle, TexturePrimitive, UiData,
-    UiRegion, UiRenderNode, UiRenderState,
+    GlyphPrimitive, MaskIdx, MoveIdx, PrimitiveInst, RectPrimitive, TextureHandle,
+    TexturePrimitive, UiData, UiRegion, UiRenderNode, UiRenderState,
 };
 use wgpu::{Color as GpuColor, *};
 
@@ -95,6 +95,7 @@ fn fill(
                     primitive: RectPrimitive::color(UiColor::WHITE),
                     region: UiRegion::FULL,
                     mask_idx: MaskIdx::NONE,
+                    move_idx: MoveIdx::NONE,
                 },
             );
             render.layers.write(
@@ -111,6 +112,7 @@ fn fill(
                     },
                     region: UiRegion::FULL,
                     mask_idx: MaskIdx::NONE,
+                    move_idx: MoveIdx::NONE,
                 },
             );
         }
@@ -123,6 +125,7 @@ fn fill(
                     primitive: TexturePrimitive::from(h),
                     region: UiRegion::FULL,
                     mask_idx: MaskIdx::NONE,
+                    move_idx: MoveIdx::NONE,
                 },
             );
         }

tests/layout.rs

@@ -109,3 +109,20 @@ fn a_fixed_box_is_drawn_again_rather_than_stretched() {
 
     assert_corners!(h, panel, (0, 0), (400, 250));
 }
+
+#[test]
+fn a_moved_subtree_takes_its_children_with_it() {
+    let mut h = Harness::new((400, 400));
+    let first = rect(Color::RED).height(40).add(&mut h.rsc);
+    let inner = rect(Color::BLUE).add(&mut h.rsc);
+    let row = inner.pad(10).height(40).add(&mut h.rsc);
+    h.set_root((first, row).span(Dir::DOWN));
+    assert_corners!(h, inner, (10, 50), (390, 70));
+
+    h.rsc[first].y = Some(Len::abs(80));
+    h.frame();
+
+    // The row is the same shape somewhere else, so one slot moved it and
+    // `inner`'s own region was never rewritten.
+    assert_corners!(h, inner, (10, 90), (390, 110));
+}

tests/remap.rs

@@ -1,27 +0,0 @@
-//! What a drawing can be taken out of, and what it cannot.
-
-use iris::core::{Remap, UiRegion, UiScalar, UiSpan};
-
-/// A box `size` tall whose top is `rel` of the way down the window.
-fn fixed(rel: f32, size: f32) -> UiRegion {
-    UiRegion::new(
-        UiSpan::FULL,
-        UiSpan::new(UiScalar { rel, abs: 0.0 }, UiScalar { rel, abs: size }),
-    )
-}
-
-#[test]
-fn a_fixed_box_can_be_carried_but_not_stretched() {
-    let from = fixed(0.0, 164.0);
-    assert!(Remap::new(from, UiRegion::FULL).is_none());
-    assert!(Remap::new(from, fixed(0.5, 164.0)).is_some());
-    assert!(Remap::new(from, fixed(0.0, 98.0)).is_none());
-}
-
-#[test]
-fn a_relative_box_can_be_stretched_to_any_other() {
-    let remap = Remap::new(UiRegion::FULL, fixed(0.0, 98.0)).expect("relative boxes remap");
-    // A part that filled the window keeps filling what replaced it, which is
-    // exactly what `outside` could not say for a box of a fixed length.
-    assert_eq!(remap.apply(UiRegion::FULL), fixed(0.0, 98.0));
-}

tests/replace_cost.rs

@@ -0,0 +1,43 @@
+//! What re-placing a subtree costs per frame, as a load for a counter rather
+//! than a check. A span of 200 fixed-height rows, five primitives each, with
+//! the row above them changing height every frame, so every row below is
+//! offered a box the same shape somewhere else.
+//!
+//!     cargo test --release --test replace_cost -- --ignored
+//!     perf stat -e instructions:u target/release/.../replace_cost-* --ignored
+//!
+//! Wall time is the wrong number here; see `draw_cost.rs`. Measured on
+//! 2026-09-14 at 1.98M instructions per frame, against 2.38M for rewriting
+//! each row's regions instead and 7.13M for redrawing them.
+
+use iris::harness::Harness;
+use iris::prelude::*;
+
+const ROWS: usize = 200;
+const FRAMES: usize = 200;
+
+#[test]
+#[ignore = "measurement, not a check"]
+fn replacing_rows_every_frame() {
+    let mut h = Harness::new((1920, 1200));
+    let first = rect(Color::RED).height(40).add(&mut h.rsc);
+    let mut span = Span::empty(Dir::DOWN);
+    span.push(first.add_strong(&mut h.rsc));
+    for i in 0..ROWS {
+        let row = (
+            rect(Color::BLUE.darker(i as f32 / (ROWS * 2) as f32)),
+            rect(Color::GREEN).pad(2),
+            wtext("row").size(16).pad(2),
+        )
+            .span(Dir::RIGHT)
+            .pad(4)
+            .height(40)
+            .add(&mut h.rsc);
+        span.push(row.add_strong(&mut h.rsc));
+    }
+    h.set_root(span);
+    for i in 0..FRAMES {
+        h.rsc[first].y = Some(Len::abs(40.0 + (i % 2) as f32));
+        h.frame();
+    }
+}

tests/retained.rs

@@ -250,3 +250,49 @@ fn a_change_two_levels_under_its_reader_still_reaches_it() {
 
     assert_corners!(h, below, (12, 232), (388, 388));
 }
+
+/// Claims its drawing may be stretched, and has a child so that the stretch
+/// has to reach one. No shipped container claims `Scale` -- `Rect`, `Image`
+/// and `()` are all childless -- so nothing else walks a subtree to remap it.
+struct Stretchy {
+    inner: StrongWidget,
+    draws: Rc<Cell<usize>>,
+}
+
+impl Widget for Stretchy {
+    fn draw(&mut self, painter: &mut Painter) -> Size {
+        self.draws.set(self.draws.get() + 1);
+        painter.widget(&self.inner).size()
+    }
+
+    fn on_resize(&self, _: Axis) -> OnResize {
+        OnResize::Scale
+    }
+}
+
+#[test]
+fn stretching_a_subtree_remaps_the_children_in_it() {
+    let mut h = Harness::new((400, 400));
+    let first = rect(Color::RED).height(40).add(&mut h.rsc);
+    let inner = rect(Color::BLUE).add(&mut h.rsc);
+    let draws = Rc::new(Cell::new(0));
+    let outer = Stretchy {
+        inner: inner.add_strong(&mut h.rsc),
+        draws: draws.clone(),
+    }
+    .add(&mut h.rsc);
+    h.set_root((first, outer).span(Dir::DOWN));
+    let settled = draws.get();
+    assert_corners!(h, inner, (0, 40), (400, 400));
+
+    h.rsc[first].y = Some(Len::abs(80));
+    h.frame();
+
+    assert_eq!(
+        draws.get(),
+        settled,
+        "its drawing is stretched, not redrawn"
+    );
+    assert_corners!(h, outer, (0, 80), (400, 400));
+    assert_corners!(h, inner, (0, 80), (400, 400));
+}

tests/stretch.rs

@@ -0,0 +1,46 @@
+//! What a drawing can be taken out of, and what it cannot.
+
+use iris::core::{UiRegion, UiScalar, UiSpan};
+
+/// A box `size` tall whose top is `rel` of the way down the window.
+fn fixed(rel: f32, size: f32) -> UiRegion {
+    UiRegion::new(
+        UiSpan::FULL,
+        UiSpan::new(UiScalar { rel, abs: 0.0 }, UiScalar { rel, abs: size }),
+    )
+}
+
+#[test]
+fn a_fixed_length_cannot_be_stretched_out_of() {
+    assert!(!fixed(0.0, 164.0).stretchable());
+    assert!(!fixed(0.5, 164.0).stretchable());
+    assert!(UiRegion::FULL.stretchable());
+}
+
+#[test]
+fn a_stretch_keeps_each_part_at_its_fraction() {
+    let to = fixed(0.0, 98.0);
+    // A part filling the window fills what replaced it.
+    assert_eq!(UiRegion::FULL.stretch(&UiRegion::FULL, &to), to);
+    // And the middle half of it stays the middle half.
+    let half = UiRegion::new(
+        UiSpan::FULL,
+        UiSpan::new(UiScalar::rel(0.25), UiScalar::rel(0.75)),
+    );
+    assert_eq!(
+        half.stretch(&UiRegion::FULL, &to),
+        UiRegion::new(
+            UiSpan::FULL,
+            UiSpan::new(
+                UiScalar {
+                    rel: 0.0,
+                    abs: 24.5
+                },
+                UiScalar {
+                    rel: 0.0,
+                    abs: 73.5
+                }
+            )
+        )
+    );
+}