bevy_grimoire_core 0.8.0

//! **Learn a map's grammar, then continue it** — WFC over what the author already placed.
//!
//! The editor's mixed-initiative half. An author lays out a corner of a room the way they want it,
//! marks the pieces they mean to keep, and the solver fills the rest of the bounds with more of the
//! same — not more of *some* arrangement, more of *theirs*.
//!
//! # Where the rules come from
//!
//! Nowhere else. A [`Descriptor`] says what a piece is; it says nothing about what may stand beside
//! it, and inventing an adjacency schema would mean asking an author to write down a grammar before
//! they are allowed to draw one.
//!
//! So the grammar is **learned from the map**, which is what WFC has always actually been. Karth &
//! Smith 2017 make the framing precise — WFC *is* finite-domain constraint solving, and its rule set
//! is an example decomposed into local constraints. Two pieces that the author has placed side by
//! side are two pieces that may be side by side. Nothing else is permitted, which is what makes the
//! output look authored rather than shuffled.
//!
//! # Owned cells are unary constraints, not a special case
//!
//! `crate::wfc::collapse_grid` already takes a per-cell starting domain, and
//! `initial_domains_restrict_output` already asserts a pinned cell survives collapse. So "the author
//! owns this cell" is a domain of one bit, made arc-consistent before the first observe — the same
//! mechanism the dungeon's boundary rule uses. There is no branch anywhere that says *if owned*.
//!
//! This is Alvarez et al.'s lock brush (FDG 2018, `10.1145/3235765.3235810`): locked tiles subdivide
//! the space into mutable and immutable zones, and every generated suggestion preserves them. It is
//! also the one third of Smelik et al. 2010's "possible facilities" that anyone actually built — see
//! `docs/2026-08-03-emerge-mapper-plan-review.md` §4 on why that citation is an aspiration.
//!
//! # It refuses rather than approximating
//!
//! A contradiction means the learned grammar cannot tile the region the author asked for. The honest
//! response is to say so — the alternative is a room full of the one prototype that fits everywhere,
//! which looks like the tool working and is not.

use std::collections::HashMap;

use crate::composition::{Composition, Envelope, Interface, Stamped};
use crate::library::Library;
use crate::map::{Map, Placed};
use crate::placement::ir::Dir;
use crate::wfc;
use crate::wfc::{E, N, S, W};

/// One thing a cell can hold: a descriptor at a yaw, or nothing.
///
/// Yaw is part of the prototype because it is part of the adjacency. A wall turned 90° meets
/// different neighbours than the same wall turned 0°, and folding the two together would learn a
/// grammar that permits corners nobody drew.
#[derive(Clone, Debug, PartialEq)]
pub enum Prototype {
    /// The cell is empty. Always index 0, and always permitted everywhere — a grammar that cannot
    /// express "nothing goes here" cannot leave a doorway.
    Empty,
    Piece { descriptor: String, yaw: f32 },
    /// One whole composition, named by [`crate::composition::Composition::id`].
    ///
    /// **A separate variant rather than a `Piece` carrying a composition id**, which is what
    /// [`from_compositions`] used to push. The two ids live in different namespaces and resolve
    /// against different files, so a composition id in `Piece::descriptor` type-checks and then fails
    /// silently at the far end: `library.get(&p.descriptor)` finds nothing, the row is dropped, and
    /// the author sees a generate that did nothing. Naming it makes [`solve`] able to emit the right
    /// kind of row instead of the wrong kind quietly.
    Composed { composition: String, yaw: f32 },
}

/// How far a piece's footprint may be from the solver's cell and still count as one tile, metres.
///
/// A tenth of a millimetre: far below anything an author expresses, far above `f32`'s error at
/// authoring scale. The same reasoning `adjacency::EDGE_EPSILON` gives for its own value.
pub const CELL_EPSILON: f32 = 1e-4;

/// The most prototypes the solver can carry — `collapse_grid` packs a domain into a `u32`.
pub const MAX_PROTOTYPES: usize = 32;

/// A learned grammar: what exists, how often, and what may sit beside what.
#[derive(Debug)]
pub struct Grammar {
    pub prototypes: Vec<Prototype>,
    /// Selection weight per prototype — how often the author used it.
    pub weights: Vec<f64>,
    /// `support[dir][p]` = the prototypes that may sit on `p`'s `dir` side (N, E, S, W).
    pub support: [Vec<u32>; 4],
}

impl Grammar {
    pub fn len(&self) -> usize {
        self.prototypes.len()
    }
    pub fn is_empty(&self) -> bool {
        self.prototypes.is_empty()
    }
}

/// Integer cell coordinates for a world point, on a grid of `cell` metres anchored at the map's
/// minimum corner.
fn to_cell(map: &Map, cell: f32, at: (f32, f32)) -> (i64, i64) {
    let (min_x, min_z, _, _) = map.floor_rect();
    (
        ((at.0 - min_x) / cell).floor() as i64,
        ((at.1 - min_z) / cell).floor() as i64,
    )
}

/// The world centre of a cell.
fn cell_centre(map: &Map, cell: f32, c: (i64, i64)) -> (f32, f32) {
    let (min_x, min_z, _, _) = map.floor_rect();
    (
        min_x + (c.0 as f32 + 0.5) * cell,
        min_z + (c.1 as f32 + 0.5) * cell,
    )
}

/// The map's bounds in cells.
fn dimensions(map: &Map, cell: f32) -> (usize, usize) {
    (
        (map.bounds.0 / cell).round().max(1.0) as usize,
        (map.bounds.2 / cell).round().max(1.0) as usize,
    )
}

/// **The part of a map a solve may change** (#192, research lens #6: graybox first).
///
/// A rectangle in map metres, its corners in either order. A cell is in it when the cell's centre
/// is, edges included. A solve given one lays only those cells and returns no row outside it; the
/// cells around it keep what stands in them and are pinned to it, so what is laid joins the map it
/// lands in rather than the empty field a whole-map solve imagines.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Area {
    pub from: (f32, f32),
    pub to: (f32, f32),
}

impl Area {
    /// **Is the cell that `at` falls in one this area lays?** The test a caller keeping a solve's
    /// rows uses to know which of the map's existing rows the solve replaced: a row is the area's
    /// when its *cell* is, by the same rule the solve lays cells by, not when its centre happens to be
    /// in the rectangle (a piece at a cell's edge can be outside it and still in a cell it lays).
    /// `false` for an area that holds no cell of the map, which a solve refuses.
    pub fn holds(&self, map: &Map, cell: f32, at: (f32, f32)) -> bool {
        let Ok(win) = window(map, cell, Some(self)) else {
            return false;
        };
        let c = to_cell(map, cell, at);
        let (x0, z0, x1, z1) = win.area;
        c.0 >= x0 as i64 && c.0 < x1 as i64 && c.1 >= z0 as i64 && c.1 < z1 as i64
    }
}

/// The cells one solve works on: the area, and the ring of cells around it that it must join.
///
/// Map cell coordinates, `[x0, x1) × [z0, z1)`. `grid` is the rectangle the solver collapses (the
/// area plus its ring, cut to the map); `area` is the part of it that is laid.
struct Window {
    grid: (usize, usize, usize, usize),
    area: (usize, usize, usize, usize),
}

impl Window {
    fn width(&self) -> usize {
        self.grid.2 - self.grid.0
    }
    fn height(&self) -> usize {
        self.grid.3 - self.grid.1
    }
    /// The local index of map cell `c`, when it is in the grid.
    fn local(&self, c: (i64, i64)) -> Option<usize> {
        let (x0, z0, x1, z1) = self.grid;
        let (x, z) = (usize::try_from(c.0).ok()?, usize::try_from(c.1).ok()?);
        (x >= x0 && x < x1 && z >= z0 && z < z1).then(|| (z - z0) * self.width() + (x - x0))
    }
    /// Is the local cell `(x, z)` one the solve lays?
    fn lays(&self, x: usize, z: usize) -> bool {
        let (x, z) = (x + self.grid.0, z + self.grid.1);
        let (x0, z0, x1, z1) = self.area;
        x >= x0 && x < x1 && z >= z0 && z < z1
    }
    /// Does the local cell `(x, z)` share a row or a column with the area? A ring cell that does
    /// not is a corner, which touches no cell the solve lays.
    fn beside(&self, x: usize, z: usize) -> bool {
        let (x, z) = (x + self.grid.0, z + self.grid.1);
        let (x0, z0, x1, z1) = self.area;
        (x >= x0 && x < x1) || (z >= z0 && z < z1)
    }
}

/// The window a solve over `area` works on; the whole map, with no ring, when there is none.
fn window(map: &Map, cell: f32, area: Option<&Area>) -> Result<Window, String> {
    let (w, h) = dimensions(map, cell);
    let Some(a) = area else {
        return Ok(Window {
            grid: (0, 0, w, h),
            area: (0, 0, w, h),
        });
    };
    let (min_x, min_z, max_x, max_z) = map.floor_rect();
    let corners = [a.from.0, a.from.1, a.to.0, a.to.1];
    if !corners.iter().all(|v| v.is_finite()) {
        return Err(format!(
            "grammar: the area from {:?} to {:?} is not a place on the map",
            a.from, a.to
        ));
    }
    // The cells whose centre `min + (i + 0.5) * cell` lies in `[lo, hi]`, as `[first, past)`.
    let span = |lo: f32, hi: f32, min: f32, n: usize| -> (usize, usize) {
        let (lo, hi) = (lo.min(hi), lo.max(hi));
        let first = ((lo - min) / cell - 0.5 - CELL_EPSILON).ceil().max(0.0) as usize;
        let past = (((hi - min) / cell - 0.5 + CELL_EPSILON).floor() + 1.0).clamp(0.0, n as f32);
        (first.min(n), past as usize)
    };
    let (x0, x1) = span(a.from.0, a.to.0, min_x, w);
    let (z0, z1) = span(a.from.1, a.to.1, min_z, h);
    if x0 >= x1 || z0 >= z1 {
        return Err(format!(
            "grammar: the area from {:?} to {:?} holds no cell of the map, whose floor runs from \
             ({min_x}, {min_z}) to ({max_x}, {max_z}); give an area over the floor",
            a.from, a.to
        ));
    }
    Ok(Window {
        grid: (
            x0.saturating_sub(1),
            z0.saturating_sub(1),
            (x1 + 1).min(w),
            (z1 + 1).min(h),
        ),
        area: (x0, z0, x1, z1),
    })
}

/// **What a solve over a [`Window`] actually solves: the area alone** (#261).
///
/// The ring around an area is pinned to what stands in it ([`pinned_domains`]), but it is not part of
/// the problem: collapsing it beside the area made two ring neighbours that the grammar does not allow
/// together refuse an area that could be filled, and made an enclosure wish count the ring's cells as
/// part of the region. So the ring leaves the grid and speaks only through the area's edge cells, each
/// narrowed to what the grammar lets stand beside the ring cell it touches.
struct Part {
    /// The area as a window of its own: the grid is the area, so [`harvest`] lays every cell of it.
    win: Window,
    /// The author's pins in the area, as [`pinned_domains`] reads them; what [`harvest`] skips.
    pins: Vec<u32>,
    /// `pins`, with each edge cell narrowed by the ring cell beside it; what the solver collapses.
    domains: Vec<u32>,
}

impl Part {
    fn of(win: &Window, initial: &[u32], grammar: &Grammar) -> Self {
        let (x0, z0, x1, z1) = win.area;
        let part = Window {
            grid: win.area,
            area: win.area,
        };
        let (w, h) = (part.width(), part.height());
        let mut pins = Vec::with_capacity(w * h);
        for z in z0..z1 {
            for x in x0..x1 {
                let at = win.local((x as i64, z as i64));
                pins.push(at.and_then(|i| initial.get(i)).copied().unwrap_or(0));
            }
        }
        let mut domains = pins.clone();
        // The neighbour of each edge cell in the four directions N, E, S, W, as `learn` orders them.
        let steps: [(i64, i64); 4] = [(0, -1), (1, 0), (0, 1), (-1, 0)];
        for z in z0..z1 {
            for x in x0..x1 {
                let here = (z - z0) * w + (x - x0);
                for (dir, (dx, dz)) in steps.iter().enumerate() {
                    let c = (x as i64 + dx, z as i64 + dz);
                    let (cx, cz) = (c.0, c.1);
                    let inside = cx >= x0 as i64 && cx < x1 as i64 && cz >= z0 as i64 && cz < z1 as i64;
                    if inside {
                        continue;
                    }
                    let Some(ring) = win.local(c).and_then(|i| initial.get(i)).copied() else {
                        continue; // the map's own edge: nothing stands beyond it
                    };
                    // What may stand on `dir`'s side of this cell is what the ring prototype allows on
                    // its opposite side, read for each prototype the ring cell could be.
                    let opposite = (dir + 2) % 4;
                    let mut allowed = 0u32;
                    for (q, row) in grammar.support[opposite].iter().enumerate() {
                        if ring & (1 << q) != 0 {
                            allowed |= row;
                        }
                    }
                    domains[here] &= allowed;
                }
            }
        }
        Part { win: part, pins, domains }
    }

    /// Which sides of the area have more map past them, N, E, S, W: the sides the ring stands on.
    fn beyond(&self, win: &Window) -> [bool; 4] {
        let (x0, z0, x1, z1) = win.area;
        [z0 > win.grid.1, x1 < win.grid.2, z1 < win.grid.3, x0 > win.grid.0]
    }

    fn width(&self) -> usize {
        self.win.width()
    }

    fn height(&self) -> usize {
        self.win.height()
    }

    /// The solved area written back into the window's grid, the ring read as what it was pinned to
    /// (empty where it was left open), so [`Solved::grid`] stays the area and the ring around it.
    fn with_ring(&self, win: &Window, initial: &[u32], solved: &[usize]) -> Vec<usize> {
        let (w, h) = (win.width(), win.height());
        let (x0, z0, ..) = win.area;
        let aw = self.width();
        let mut grid = vec![0usize; w * h];
        for z in 0..h {
            for x in 0..w {
                let i = z * w + x;
                grid[i] = if win.lays(x, z) {
                    let (ax, az) = (x + win.grid.0 - x0, z + win.grid.1 - z0);
                    solved.get(az * aw + ax).copied().unwrap_or(0)
                } else {
                    match initial.get(i) {
                        Some(&mask) if mask.count_ones() == 1 => mask.trailing_zeros() as usize,
                        _ => 0,
                    }
                };
            }
        }
        grid
    }
}

/// **Read the author's arrangement as a grammar.**
///
/// Every placement lands in a cell; every orthogonally adjacent pair of cells teaches one rule in each
/// direction. Cells the author left empty teach rules too — that is how the solver learns it is
/// allowed to leave space, and a grammar without them fills every square metre.
pub fn learn(map: &Map, cell: f32) -> Result<Grammar, String> {
    if !(cell.is_finite() && cell > 0.0) {
        return Err(format!("grammar: cell size {cell} is not a usable step"));
    }
    let (w, h) = dimensions(map, cell);

    // Cell -> prototype index. A second placement in one cell is a stacked piece; the grammar is
    // about the floor plan, so the first one wins and the rest are simply not part of the lesson.
    let mut prototypes = vec![Prototype::Empty];
    let mut counts: Vec<f64> = vec![0.0];
    let mut grid: Vec<usize> = vec![0; w * h];
    let mut placed_at: HashMap<(i64, i64), usize> = HashMap::new();

    for p in &map.placements {
        let c = to_cell(map, cell, p.at);
        if c.0 < 0 || c.1 < 0 || c.0 as usize >= w || c.1 as usize >= h {
            continue;
        }
        if placed_at.contains_key(&c) {
            continue;
        }
        let proto = Prototype::Piece {
            descriptor: p.descriptor.clone(),
            // Quantised, so two chairs a floating-point hair apart are one prototype rather than two.
            yaw: (p.yaw / 15.0).round() * 15.0,
        };
        let ix = match prototypes.iter().position(|q| *q == proto) {
            Some(ix) => ix,
            None => {
                if prototypes.len() >= MAX_PROTOTYPES {
                    return Err(format!(
                        "grammar: this map uses more than {MAX_PROTOTYPES} distinct piece-and-yaw \
                         combinations, which is more than the solver's domain can hold. Learn from a \
                         smaller region, or place fewer kinds of thing in the example."
                    ));
                }
                prototypes.push(proto);
                counts.push(0.0);
                prototypes.len() - 1
            }
        };
        placed_at.insert(c, ix);
        grid[c.1 as usize * w + c.0 as usize] = ix;
    }

    for &ix in &grid {
        counts[ix] += 1.0;
    }

    // Adjacency, read off the example. `dir` is N, E, S, W to match `wfc`'s edge order.
    let n = prototypes.len();
    let mut support: [Vec<u32>; 4] = [vec![0; n], vec![0; n], vec![0; n], vec![0; n]];
    let steps: [(i64, i64); 4] = [(0, -1), (1, 0), (0, 1), (-1, 0)];
    for y in 0..h {
        for x in 0..w {
            let a = grid[y * w + x];
            for (dir, (dx, dy)) in steps.iter().enumerate() {
                let (nx, ny) = (x as i64 + dx, y as i64 + dy);
                if nx < 0 || ny < 0 || nx as usize >= w || ny as usize >= h {
                    continue;
                }
                let b = grid[ny as usize * w + nx as usize];
                support[dir][a] |= 1 << b;
            }
        }
    }

    // **Empty must be able to meet empty.** A one-piece map teaches only "piece beside empty", and a
    // solver that cannot put two empties side by side then has to fill every other cell — which is
    // not what a map with one crate in it looks like.
    for row in &mut support {
        row[0] |= 1;
    }

    Ok(Grammar {
        prototypes,
        weights: counts,
        support,
    })
}

/// What a solve produced.
#[derive(Debug)]
pub struct Solved {
    /// New placements for the cells the solver filled. Owned and existing pieces are not repeated.
    ///
    /// Empty for a grammar over compositions — those cells come back as [`Solved::stamps`].
    pub placements: Vec<Placed>,
    /// New stamps, for a grammar whose prototypes are whole compositions.
    ///
    /// **Produced here rather than by a translator over [`Solved::grid`].** A caller outside this
    /// function cannot see `initial`, so it would have to re-derive which cells the author pinned —
    /// a second answer to a question this loop already answers, and it would differ on exactly the
    /// cells the author cared enough about to pin.
    pub stamps: Vec<Stamped>,
    /// Cells the solver was free to choose.
    pub free_cells: usize,
    /// Cells pinned by the author.
    pub owned_cells: usize,
    /// The collapsed grid itself: one prototype index per cell, indexed `z * width + x`.
    ///
    /// **Returned rather than rebuilt.** [`crate::range`] measures a solved grid, and reconstructing
    /// it from `placements` would be a second answer to a question this function already answered —
    /// pinned cells are not in `placements` at all, so the two could disagree about exactly the cells
    /// the author cares most about.
    pub grid: Vec<usize>,
    /// The grid's width in cells; `grid.len()` is `width * height`.
    pub width: usize,
    /// The grid's height in cells.
    pub height: usize,
    /// The total weight of the wishes this arrangement could not grant. Zero is everything asked for.
    ///
    /// Always zero from [`solve`], and accurately so — WFC carries no soft constraints, so there is
    /// nothing it could have failed to meet. [`solve_constrained`] is where this becomes a number,
    /// and it is what lets a caller say *"everything except the north corridor"* instead of refusing.
    pub unmet: u64,
}

/// **What the author wants of a region, beyond the rules the kit already implies.**
///
/// Each field is a *wish*: the solver returns the arrangement that grants as much of it as the kit
/// allows, and reports the rest as [`Solved::unmet`] rather than refusing outright.
pub struct Wishes {
    /// The fraction of the region that should be closed off from the outside, in `[0, 1]`.
    ///
    /// A **floor**, never a ceiling. [`crate::constraints::enclosure_rules`] explains why the
    /// direction is load-bearing: a floor is sound without the foundedness machinery and a ceiling is
    /// not, and the difference is 5,904 variables.
    pub enclosure: f32,
    /// What the enclosure wish is worth against the seeded texture, or `None` to make it a rule.
    ///
    /// **The exchange rate is arithmetic, not taste, so it is written down here.** The per-cell dream
    /// is one wish of weight 1 per cell, so over a 12 x 12 region its total mass is 144. A weight
    /// above that buys an enclosure that outranks the whole texture; below it, texture wins and rooms
    /// appear only where they are cheap. `None` makes enclosure non-negotiable and brings back the
    /// flat refusal for a region that cannot meet it.
    pub enclosure_weight: Option<u32>,
}

/// **Fill the map's free cells with more of the author's arrangement.**
///
/// Owned placements pin their cell to a single prototype — a unary constraint, exactly the mechanism
/// `wfc::boundary_initial` uses — and everything else is free. Unowned existing placements are
/// *replaced*: they were the sketch, and the solve is the drawing.
pub fn solve(
    map: &Map,
    grammar: &Grammar,
    cell: f32,
    seed: u64,
    next_id: impl FnMut() -> String,
) -> Result<Solved, String> {
    solve_window(map, grammar, cell, None, seed, next_id)
}

/// **[`solve`], laying only the cells in `area`** (#192). The cells around it are pinned to what
/// stands in them ([`pinned_domains`]), so the area's edge joins its neighbours by the grammar's
/// own rules; nothing outside the area is returned, and [`Solved::grid`] is the area and that ring.
/// An area that holds no cell of the map is refused, naming it.
pub fn solve_in(
    map: &Map,
    grammar: &Grammar,
    cell: f32,
    area: Area,
    seed: u64,
    next_id: impl FnMut() -> String,
) -> Result<Solved, String> {
    solve_window(map, grammar, cell, Some(&area), seed, next_id)
}

fn solve_window(
    map: &Map,
    grammar: &Grammar,
    cell: f32,
    area: Option<&Area>,
    seed: u64,
    mut next_id: impl FnMut() -> String,
) -> Result<Solved, String> {
    if grammar.len() < 2 {
        return Err(
            "grammar: nothing has been placed yet, so there is no arrangement to continue. Place a \
             few pieces the way you want them first."
                .to_owned(),
        );
    }
    let win = window(map, cell, area)?;
    let (w, h) = (win.width(), win.height());
    let full: u32 = if grammar.len() == 32 {
        u32::MAX
    } else {
        (1u32 << grammar.len()) - 1
    };
    let (initial, owned_cells) = pinned_domains(map, grammar, cell, &win, full)?;
    let part = Part::of(&win, &initial, grammar);

    let solved = wfc::collapse_grid(
        part.width(),
        part.height(),
        &grammar.weights,
        &grammar.support,
        &part.domains,
        seed,
    )
    .ok_or_else(|| {
        "grammar: no arrangement satisfies what you have pinned. The learned rules cannot tile \
         this region around those cells — free some of them, or extend the example so the solver \
         has more ways to join things up."
            .to_owned()
    })?;

    let (placements, stamps, free_cells) =
        harvest(map, grammar, cell, &solved, &part.pins, &part.win, &mut next_id);

    Ok(Solved {
        placements,
        stamps,
        free_cells,
        owned_cells,
        grid: part.with_ring(&win, &initial, &solved),
        width: w,
        height: h,
        unmet: 0,
    })
}

/// How much search one constrained solve may spend before it reports a refusal.
///
/// Counted in conflicts rather than seconds, so a busy machine and an idle one answer identically —
/// see `bevy_grimoire_solver::Budget`. Generous: the shapes this sees settle in a fraction of it, and
/// its job is to turn a pathological region into a named refusal rather than a hung editor.
const SOLVE_BUDGET: u64 = 200_000;

/// **Fill the map's free cells, and close some rooms while doing it.**
///
/// The same job as [`solve`] — same `Map`, same pinning, same [`Solved`] back, so `generate_from`,
/// the stamp write-back, `Undo::Stamped` and `redraw_stamps` are all untouched — but through the
/// constraint solver, which can express things WFC's local adjacency cannot.
///
/// # What it can do that [`solve`] cannot
///
/// **Close a boundary.** `docs/research/2026-08-10-expressive-range.md` measured 128 WFC solves with
/// zero enclosed regions and falsified both the vocabulary and the weight explanations for it; a
/// closed boundary is a property *over distance*, and no reweighting of local choices produces one.
/// [`Wishes::enclosure`] is that term.
///
/// **Give a partial answer.** WFC either tiles the region or refuses it. Here a wish that cannot be
/// granted is *charged for* — [`Solved::unmet`] — so the caller can say which corridor it could not
/// give you rather than showing an empty screen and a paragraph.
///
/// # Where the variety comes from
///
/// `seed` draws one wish per cell from the author's own weights, and the solver returns the legal
/// arrangement closest to them. It cannot come from anywhere else: a constraint solver is a function
/// of its clauses, so asking again with a different seed and the same problem returns the same
/// answer. Varying the *problem* is the mechanism, and it survives a solver upgrade in a way that
/// variety drawn from branching heuristics would not.
///
/// `faces` is [`Composed::faces`], indexed alongside `grammar.prototypes`. It is what makes enclosure
/// expressible, which is why this is the composition path's solver and [`solve`] still serves the
/// grammars learned from placements — those derive no interfaces, so they have no walls to close.
pub fn solve_constrained(
    map: &Map,
    grammar: &Grammar,
    faces: &[Option<Interface>],
    wishes: &Wishes,
    cell: f32,
    seed: u64,
    next_id: impl FnMut() -> String,
) -> Result<Solved, String> {
    solve_constrained_window(map, grammar, faces, wishes, cell, None, seed, next_id)
}

/// **[`solve_constrained`], laying only the cells in `area`** (#192), as [`solve_in`] does for
/// [`solve`]. The enclosure wish is over the area and the ring around it.
#[allow(clippy::too_many_arguments)]
pub fn solve_constrained_in(
    map: &Map,
    grammar: &Grammar,
    faces: &[Option<Interface>],
    wishes: &Wishes,
    cell: f32,
    area: Area,
    seed: u64,
    next_id: impl FnMut() -> String,
) -> Result<Solved, String> {
    solve_constrained_window(map, grammar, faces, wishes, cell, Some(&area), seed, next_id)
}

#[allow(clippy::too_many_arguments)]
fn solve_constrained_window(
    map: &Map,
    grammar: &Grammar,
    faces: &[Option<Interface>],
    wishes: &Wishes,
    cell: f32,
    area: Option<&Area>,
    seed: u64,
    mut next_id: impl FnMut() -> String,
) -> Result<Solved, String> {
    if grammar.len() < 2 {
        return Err(
            "grammar: nothing has been placed yet, so there is no arrangement to continue. Place a \
             few pieces the way you want them first."
                .to_owned(),
        );
    }
    if faces.len() != grammar.len() {
        return Err(format!(
            "grammar: {} interfaces for {} prototypes — they must be the pair `from_compositions` \
             returned, or the constraint and the metric are reading different kits.",
            faces.len(),
            grammar.len()
        ));
    }
    let win = window(map, cell, area)?;
    let (w, h) = (win.width(), win.height());
    let full: u32 = if grammar.len() == 32 {
        u32::MAX
    } else {
        (1u32 << grammar.len()) - 1
    };
    let (initial, owned_cells) = pinned_domains(map, grammar, cell, &win, full)?;
    let part = Part::of(&win, &initial, grammar);
    let (aw, ah) = (part.width(), part.height());

    let mut gp = crate::constraints::GridProblem::encode(
        &grammar.support,
        &part.domains,
        aw,
        ah,
        grammar.len(),
    )?;
    // The author's pinned cells, and what the ring leaves each edge cell, as unary constraints — the
    // same masks WFC takes as `initial`.
    crate::constraints::domain_rules(&mut gp.problem, &gp.place, &part.domains);
    // One wish per cell, drawn from the weights the author's own arrangement taught.
    crate::constraints::preference_rules(&mut gp.problem, &gp.place, &grammar.weights, seed)?;
    if wishes.enclosure > 0.0 {
        let read = crate::range::Faces::new(faces, WALL_TOKEN, WALKABLE_GAP);
        crate::constraints::enclosure_rules_beyond(
            &mut gp.problem,
            &gp.place,
            &read,
            aw,
            ah,
            part.beyond(&win),
            wishes.enclosure,
            wishes.enclosure_weight,
        )?;
    }

    let solution = gp.problem.solve(SOLVE_BUDGET)?;
    let chosen = gp.read(&solution)?;
    let (placements, stamps, free_cells) =
        harvest(map, grammar, cell, &chosen, &part.pins, &part.win, &mut next_id);

    Ok(Solved {
        placements,
        stamps,
        free_cells,
        owned_cells,
        grid: part.with_ring(&win, &initial, &chosen),
        width: w,
        height: h,
        unmet: solution.unmet(),
    })
}

/// The edge token that means "a wall stands here", and the gap under a lintel that counts as a
/// doorway.
///
/// **The kit's vocabulary, named once.** `range::Faces` takes both as parameters precisely so nothing
/// is pinned to one kit's spelling; these are the shipped Site kit's, and they match what
/// `examples/expressive_range.rs` measures with — so the constraint and the criterion read the same
/// words. A kit that spells it differently needs these threaded through `Wishes`, not changed here.
/// **The [`crate::range::Faces`] a composition grammar is classified by**, with this module's own
/// wall token and walkable gap.
///
/// **Public so there is one spelling.** The solver reads a prototype's faces through
/// `Faces::new(faces, WALL_TOKEN, WALKABLE_GAP)`, and a caller that measures a solved grid — the
/// editor's `measure_solved`, for the `range` axes — must classify with the same two constants or the
/// metric and the solver disagree about what a wall is. A second copy of `"wall"` is exactly the kind
/// of drift a kit's vocabulary already exists to prevent.
pub fn interfaces(faces: &[Option<crate::composition::Interface>]) -> crate::range::Faces<'_> {
    crate::range::Faces::new(faces, WALL_TOKEN, WALKABLE_GAP)
}

const WALL_TOKEN: &str = "wall";
const WALKABLE_GAP: f32 = 0.5;

/// The author's pinned cells as a per-cell domain mask over `win`, and how many there were.
///
/// **One definition, two solvers.** An owned placement narrows its cell to a single prototype — the
/// unary constraint `wfc::boundary_initial` uses, and the one `constraints::domain_rules` takes. A
/// second copy of this loop would eventually disagree with the first about exactly the cells the
/// author cared enough about to pin, which is the worst possible place for two answers.
///
/// **The ring around an area is pinned to what stands in it** (#192): the first placement in the
/// cell, as [`learn`] reads a cell, else a stamp centred in it, as the prototype the grammar knows
/// it by; empty when nothing stands there. A cell holding something the grammar does not know is
/// left open, so the area's edge is not held to a neighbour the rules cannot read, and so are the
/// ring's four corners, which touch no cell of the area. The ring is never laid ([`harvest`]), so
/// leaving a cell open changes nothing outside the area.
fn pinned_domains(
    map: &Map,
    grammar: &Grammar,
    cell: f32,
    win: &Window,
    full: u32,
) -> Result<(Vec<u32>, usize), String> {
    let w = win.width();
    let mut initial = vec![full; w * win.height()];
    let mut owned_cells = 0usize;
    let quarter = |yaw: f32| (yaw / 15.0).round() * 15.0;
    let known = |p: &Prototype| {
        grammar
            .prototypes
            .iter()
            .position(|q| q == p)
            .or_else(|| same_tile_turned(grammar, p))
    };

    let mut ring: HashMap<usize, Option<usize>> = HashMap::new();
    let mut stands = |i: usize, proto: Prototype| {
        let ix = known(&proto);
        match ring.get_mut(&i) {
            None => {
                ring.insert(i, ix);
            }
            Some(slot @ None) => *slot = ix,
            Some(Some(_)) => {}
        }
    };
    for p in &map.placements {
        if let Some(i) = win.local(to_cell(map, cell, p.at))
            && !win.lays(i % w, i / w)
        {
            stands(
                i,
                Prototype::Piece {
                    descriptor: p.descriptor.clone(),
                    yaw: quarter(p.yaw),
                },
            );
        }
    }
    for s in &map.stamps {
        if let Some(i) = win.local(to_cell(map, cell, s.at))
            && !win.lays(i % w, i / w)
        {
            stands(
                i,
                Prototype::Composed {
                    composition: s.of.clone(),
                    yaw: quarter(s.yaw),
                },
            );
        }
    }
    for (i, mask) in initial.iter_mut().enumerate() {
        let (x, z) = (i % w, i / w);
        // A corner of the ring touches no cell the solve lays, so pinning it could only refuse an
        // area over two old pieces the grammar would not set side by side.
        if win.lays(x, z) || !win.beside(x, z) {
            continue;
        }
        *mask = match ring.get(&i) {
            None => 1 << 0, // nothing stands here: `Prototype::Empty`, always index 0
            Some(Some(ix)) => 1 << ix,
            Some(None) => full,
        };
    }

    for p in map.placements.iter().filter(|p| p.owned) {
        let Some(i) = win.local(to_cell(map, cell, p.at)) else {
            continue;
        };
        if !win.lays(i % w, i / w) {
            continue;
        }
        let proto = Prototype::Piece {
            descriptor: p.descriptor.clone(),
            yaw: quarter(p.yaw),
        };
        let Some(ix) = known(&proto) else {
            return Err(format!(
                "grammar: owned placement `{}` is a `{}` at {}deg, which is not in the learned \
                 grammar — re-learn from a map that contains it.",
                p.id, p.descriptor, p.yaw
            ));
        };
        initial[i] = 1 << ix;
        owned_cells += 1;
    }
    Ok((initial, owned_cells))
}

/// **The prototype a stamp at a turn the grammar deduplicated stands for** (#261).
///
/// [`from_compositions`] keeps a tile's turns until one presents the faces of an earlier turn, so a
/// tile that looks the same turned half a circle keeps two of its four turns, and one that looks the
/// same turned a quarter keeps one. A stamp standing at a turn that was dropped is therefore the kept
/// turn whose yaw is the same modulo the tile's period, `90 * kept` degrees: the identical-faced copy.
/// `None` for anything but a stamp of a composition the grammar knows, and for a count of kept turns
/// that is not a divisor of the circle in quarters, which no deduplication produces.
fn same_tile_turned(grammar: &Grammar, proto: &Prototype) -> Option<usize> {
    let Prototype::Composed { composition, yaw } = proto else {
        return None;
    };
    let turns = |p: &Prototype| match p {
        Prototype::Composed { composition: c, yaw } if c == composition => Some(*yaw),
        _ => None,
    };
    let kept = grammar.prototypes.iter().filter_map(turns).count();
    if !matches!(kept, 1 | 2 | 4) {
        return None;
    }
    let period = 90.0 * kept as f32;
    let want = yaw.rem_euclid(period);
    grammar.prototypes.iter().position(|p| {
        turns(p).is_some_and(|y| {
            let y = y.rem_euclid(360.0);
            (y - want).abs() < 1.0 && y < period
        })
    })
}

/// A solved grid as the rows a caller can write back: the cells `win` lays, skipping the ones the
/// author pinned.
///
/// Shared for the same reason as [`pinned_domains`]: which cells are new is a function of `initial`,
/// and a caller re-deriving it would differ on the pinned ones.
fn harvest(
    map: &Map,
    grammar: &Grammar,
    cell: f32,
    chosen: &[usize],
    initial: &[u32],
    win: &Window,
    next_id: &mut impl FnMut() -> String,
) -> (Vec<Placed>, Vec<Stamped>, usize) {
    let mut placements = Vec::new();
    let mut stamps = Vec::new();
    let mut free_cells = 0usize;
    let w = win.width();
    for y in 0..win.height() {
        for x in 0..w {
            if !win.lays(x, y) {
                continue; // the ring around an area keeps what stands in it
            }
            let c = ((x + win.grid.0) as i64, (y + win.grid.1) as i64);
            let (Some(&ix), Some(&mask)) = (chosen.get(y * w + x), initial.get(y * w + x)) else {
                continue;
            };
            if mask.count_ones() == 1 {
                continue; // the author pinned this one
            }
            free_cells += 1;
            match grammar.prototypes.get(ix) {
                None | Some(Prototype::Empty) => {}
                Some(Prototype::Piece { descriptor, yaw }) => placements.push(Placed {
                    id: next_id(),
                    descriptor: descriptor.clone(),
                    at: cell_centre(map, cell, c),
                    yaw: *yaw,
                    ..Placed::default()
                }),
                Some(Prototype::Composed { composition, yaw }) => stamps.push(Stamped {
                    id: next_id(),
                    of: composition.clone(),
                    at: cell_centre(map, cell, c),
                    yaw: *yaw,
                    // `None` is what every stamp the editor writes carries today; recording a
                    // fingerprint here would be a second convention for the same field.
                    ..Stamped::default()
                }),
            }
        }
    }
    (placements, stamps, free_cells)
}


#[cfg(test)]
mod declared_tests {
    use super::*;
    use crate::descriptor::{Descriptor, Extent, SubCell, Subgrid};
    use crate::library::LIBRARY_VERSION;

    /// A 0.5 m post whose whole lattice presents `token`.
    fn post(id: &str, token: &str) -> Descriptor {
        let mut d = Descriptor {
            id: id.to_owned(),
            extent: Extent { footprint: Some((0.5, 0.5)), height: Some(0.5) },
            ..Default::default()
        };
        let div = crate::descriptor::divisions(&d, 1).expect("measured");
        let mut cells = Vec::new();
        for x in 0..div.0 {
            for y in 0..div.1 {
                for z in 0..div.2 {
                    cells.push(SubCell {
                        at: (x, y, z),
                        solid: true,
                        edge: Some(token.to_owned()),
                    });
                }
            }
        }
        d.subgrid = Some(Subgrid { cells });
        d
    }

    fn lib(ds: Vec<Descriptor>) -> Library {
        Library { version: LIBRARY_VERSION, note: None, descriptors: ds }
    }

    /// **A library that declares nothing refuses**, and says what to do instead.
    ///
    /// The alternative — an empty grammar the solver then fills a room with — is the shape this
    /// module's own note warns about: it would look like the tool working.
    #[test]
    fn a_library_with_no_tokens_refuses_rather_than_generating_noise() {
        let plain = Descriptor {
            id: "crate_a".to_owned(),
            extent: Extent { footprint: Some((0.5, 0.5)), height: Some(0.5) },
            ..Default::default()
        };
        let err = declared(&lib(vec![plain]), 1, 0.5).expect_err("must refuse");
        assert!(err.contains("no descriptor"), "{err}");
        assert!(err.contains("Author tokens"), "{err}");
    }

    /// Tokens that agree may abut; tokens that disagree may not. Equality, not a compatibility table.
    #[test]
    fn only_matching_tokens_may_abut() {
        let g = declared(&lib(vec![post("stone", "stone"), post("glass", "glass")]), 1, 0.5)
            .expect("builds");
        let ix = |id: &str| {
            g.prototypes
                .iter()
                .position(|p| matches!(p, Prototype::Piece { descriptor, .. } if descriptor == id))
                .unwrap_or_else(|| panic!("no {id}"))
        };
        let (stone, glass) = (ix("stone"), ix("glass"));
        assert!(g.support[N][stone] & (1 << stone) != 0, "stone may meet stone");
        assert!(g.support[N][stone] & (1 << glass) == 0, "stone must not meet glass");
        // `Empty` is unconstrained in both directions, or the solver could never leave a gap.
        assert!(g.support[N][stone] & 1 != 0);
        assert!(g.support[N][0] & (1 << stone) != 0);
    }

    /// **Turning a symmetric tile produces the same tile.** Keeping both would spend two of the
    /// solver's thirty-two slots saying one thing.
    #[test]
    fn a_symmetric_tile_is_one_prototype_not_four() {
        let g = declared(&lib(vec![post("stone", "stone")]), 1, 0.5).expect("builds");
        assert_eq!(g.prototypes.len(), 2, "Empty plus one: {:?}", g.prototypes);
    }

    /// **Dedup is per descriptor.** Measured against the shipped site kit, where a global pass
    /// deleted `site/column` because it presents exactly the faces `site/wall` does — and a solver
    /// that can never place a column is not the kit the author authored.
    #[test]
    fn two_tiles_presenting_the_same_faces_are_still_two_tiles() {
        let g = declared(&lib(vec![post("wall", "stone"), post("column", "stone")]), 1, 0.5)
            .expect("builds");
        let ids: Vec<&str> = g
            .prototypes
            .iter()
            .filter_map(|p| match p {
                Prototype::Piece { descriptor, .. } => Some(descriptor.as_str()),
                Prototype::Composed { composition, .. } => Some(composition.as_str()),
                Prototype::Empty => None,
            })
            .collect();
        assert!(ids.contains(&"wall") && ids.contains(&"column"), "{ids:?}");
    }

    /// **A kit whose tiles are not the grid's size refuses, and names each one with its size.**
    ///
    /// Measured on the shipped site kit, which is exactly this case at `cell = 1.0`: every tokened
    /// piece is some other size, so a solve would lay a 2.06 m doorway and a 0.22 m corner at the
    /// same 1 m spacing. Every declared adjacency would be satisfied and the geometry would
    /// interpenetrate — the shape of failure that looks like the tool working.
    #[test]
    fn tiles_that_are_not_the_grids_size_refuse_and_name_their_sizes() {
        // `post` builds 0.5 m pieces; ask for a 1 m grid.
        let err = declared(&lib(vec![post("stone", "stone")]), 1, 1.0).expect_err("must refuse");
        assert!(err.contains("wrong size"), "{err}");
        assert!(err.contains("`stone` is 0.5 x 0.5 m"), "{err}");
        assert!(err.contains("generate from the map instead"), "{err}");
    }

    /// Over the ceiling refuses **with the count**, so an author knows how far over they are.
    #[test]
    fn more_prototypes_than_the_domain_holds_refuses_with_the_count() {
        // Each post gets its own token, so nothing dedups across them and each contributes one.
        let many: Vec<Descriptor> = (0..MAX_PROTOTYPES + 2)
            .map(|i| post(&format!("p{i:03}"), &format!("t{i:03}")))
            .collect();
        let err = declared(&lib(many), 1, 0.5).expect_err("must refuse");
        assert!(err.contains(&MAX_PROTOTYPES.to_string()), "{err}");
        assert!(err.contains("narrow the kit"), "{err}");
    }

    /// The grammar feeds the SAME collapser the learned one does — one solver, two sources.
    #[test]
    fn a_declared_grammar_drives_the_shared_collapser() {
        let g = declared(&lib(vec![post("stone", "stone"), post("glass", "glass")]), 1, 0.5)
            .expect("builds");
        let n = g.prototypes.len();
        let initial = vec![(1u32 << n) - 1; 4 * 4];
        let out = crate::wfc::collapse_grid(4, 4, &g.weights, &g.support, &initial, 7)
            .unwrap_or_else(|| panic!("a fully permissive start must collapse"));
        assert_eq!(out.len(), 16);
        // Whatever it produced, every abutting pair is one the tokens allow — which is the property
        // the whole exercise is for.
        for z in 0..4usize {
            for x in 0..4usize {
                let p = out[z * 4 + x];
                if x + 1 < 4 {
                    let q = out[z * 4 + x + 1];
                    assert!(g.support[E][p] & (1 << q) != 0, "({x},{z}) east pair is not allowed");
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    // The fixture kit `site_kit` builds needs the same pieces the module above uses to build one.
    use crate::descriptor::{Descriptor, Extent, SubCell, Subgrid};

    /// An interface presenting one token across the whole of every face.
    fn iface(token: Option<&str>) -> crate::composition::Interface {
        use crate::composition::Band;
        let band = Band {
            y: (0.0, 1.0),
            lat: (-0.5, 0.5),
            token: token.map(str::to_owned),
        };
        crate::composition::Interface {
            faces: [
                vec![band.clone()],
                vec![band.clone()],
                vec![band.clone()],
                vec![band],
            ],
            faults: Vec::new(),
        }
    }

    /// **The turns are what make a kit solvable**, measured on the shipped one.
    ///
    /// An ASSET-CONTRACT test: it reads the real site kit on purpose, because what it asserts IS a
    /// fact about what ships. FVS-R-7's "done when" is that this kit is solvable.
    ///
    /// **Before the four turns existed this failed, and the failure is the reason they do.** Every
    /// wall tile's north support was `Empty` and nothing else: a wall tile presents `wall` outward on
    /// one face, so the tile across that seam has to present `wall` back — and only the same tile
    /// turned 180 degrees does. With yaw 0 alone the kit expressed floor, empty, and no wall meeting
    /// anything. `tests/site_tiles.rs`'s `one_wall_tile_covers_four_orientations` is the authored
    /// kit's own statement of the same thing.
    #[test]
    fn the_shipped_site_kit_learns_a_grammar_and_solves() {
        let Composed { grammar: g, skipped, faces } = super::tests::site_kit();
        assert!(skipped.is_empty(), "every authored tile is one cell and bounded: {skipped:?}");
        // The interfaces come back alongside the prototypes, and `Empty` has none — which is what
        // `crate::range` reads to tell a wall face from an open one without learning the kit's tokens.
        assert_eq!(faces.len(), g.len(), "one interface slot per prototype");
        assert!(faces[0].is_none(), "Empty presents nothing");
        assert!(faces[1..].iter().all(|f| f.is_some()), "every tile prototype presents something");

        // Four authored tiles; three are asymmetric and contribute four turns each, and the floor is
        // symmetric so its four collapse to one. That count is the dedup rule working, not a
        // coincidence — assert the SHAPE rather than the number, so authoring a fifth tile does not
        // fail this for the wrong reason.
        let turns_of = |id: &str| {
            g.prototypes
                .iter()
                .filter(|p| matches!(p, Prototype::Composed { composition, .. } if composition == id))
                .count()
        };
        assert_eq!(turns_of("site/tile_floor"), 1, "a symmetric tile is one prototype, not four");
        assert_eq!(turns_of("site/tile_wall_n"), 4, "an asymmetric tile is four");

        // **The property the turns exist for**: a wall tile can have something other than `Empty`
        // beside it. Before them this was `0b1` — the empty prototype alone.
        let wall = g
            .prototypes
            .iter()
            .position(|p| matches!(p, Prototype::Composed { composition, yaw }
                if composition == "site/tile_wall_n" && *yaw == 0.0))
            .expect("the kit has a north wall tile");
        assert!(
            g.support[N][wall] & !1 != 0,
            "a wall tile whose only northern neighbour is Empty cannot make a room; support is \
             {:#b}",
            g.support[N][wall]
        );

        // **One tile, one unit of weight.** A symmetric tile dedupes to one prototype and an
        // asymmetric one keeps four, so a flat weight per prototype makes the symmetric tile a
        // quarter as likely — which is an artifact of the solver's expansion, not anything the
        // author said. Measured before this: `tile_floor` came out at 7.4% of 864 cells against
        // ~23% for each of the other three.
        let weight_of = |id: &str| -> f64 {
            g.prototypes
                .iter()
                .zip(g.weights.iter())
                .filter(|(p, _)| matches!(p, Prototype::Composed { composition, .. } if composition == id))
                .map(|(_, w)| *w)
                .sum()
        };
        let floor = weight_of("site/tile_floor");
        let wall = weight_of("site/tile_wall_n");
        assert!(
            (floor - wall).abs() < 1e-9,
            "a symmetric tile and an asymmetric one must carry the same total weight — floor \
             {floor}, wall {wall}"
        );
        assert!(
            (floor - 1.0).abs() < 1e-9,
            "and that total is one tile's worth, not one prototype's: {floor}"
        );

        // And a grid actually collapses.
        let map = crate::map::Map {
            name: "probe".into(),
            bounds: (6.0, 3.0, 6.0),
            ..crate::map::Map::default()
        };
        let mut n = 0;
        let solved = solve(&map, &g, 1.0, 42, || {
            n += 1;
            format!("g@{n}")
        })
        .expect("the shipped kit solves a 6x6 grid");
        assert_eq!(solved.free_cells, 36);
        // **Stamps, not placements** — and this assertion used to read `placements` and pass, which is
        // the whole reason `Prototype::Composed` exists. Those rows were `Placed` carrying a
        // COMPOSITION id in `descriptor`; the editor resolves that against the library, finds nothing,
        // and drops every row while reporting success. The test agreed with the bug because both sides
        // spelled it the same way.
        assert!(
            solved.placements.is_empty(),
            "a grammar over compositions places no descriptors: {:?}",
            solved.placements
        );
        assert!(
            solved.stamps.len() > 20,
            "a solve that fills almost nothing is a grammar that cannot express a room: {} stamps",
            solved.stamps.len()
        );
        assert!(
            solved.stamps.iter().all(|s| {
                g.prototypes.iter().any(
                    |p| matches!(p, Prototype::Composed { composition, .. } if *composition == s.of),
                )
            }),
            "every stamp names a composition the kit actually has"
        );
    }

    /// **The control for FVS-R-9.** A room hand-assembled from the shipped kit's own prototypes,
    /// measured by `crate::range` and found enclosed.
    ///
    /// Without this, the measurement's headline result — *every solve scored enclosure 0* — has two
    /// explanations that look identical: the generator cannot close a boundary, or the metric cannot
    /// see one. This separates them. The kit CAN build a closed room; four corners and four walls are
    /// exactly what it has, and laying them by hand produces enclosure 1.
    ///
    /// So a zero from a solve is a statement about the solver, not about `range`.
    #[test]
    fn the_kit_can_build_a_room_the_metric_calls_enclosed() {
        let Composed { grammar: g, faces, .. } = super::tests::site_kit();

        let ix = |id: &str, yaw: f32| -> usize {
            g.prototypes
                .iter()
                .position(|p| matches!(p, Prototype::Composed { composition, yaw: y }
                    if composition == id && (*y - yaw).abs() < 1e-6))
                .unwrap_or_else(|| panic!("the kit has {id} at {yaw} degrees"))
        };
        // Which turn walls which face is read from the kit, not assumed — see the alphabet the
        // `expressive_range` example prints.
        let (nw, ne, sw, se) = (
            ix("site/tile_corner_nw", 0.0),
            ix("site/tile_corner_nw", 270.0),
            ix("site/tile_corner_nw", 90.0),
            ix("site/tile_corner_nw", 180.0),
        );
        let (n_, e_, s_, w_) = (
            ix("site/tile_wall_n", 0.0),
            ix("site/tile_wall_n", 270.0),
            ix("site/tile_wall_n", 180.0),
            ix("site/tile_wall_n", 90.0),
        );
        let floor_ix = ix("site/tile_floor", 0.0);

        // A 5 x 5 room inside a 9 x 9 field of Empty.
        const D: usize = 9;
        let (lo, hi) = (2usize, 6usize);
        let mut grid = vec![0usize; D * D];
        for z in lo..=hi {
            for x in lo..=hi {
                let on_top = z == lo;
                let on_bottom = z == hi;
                let on_left = x == lo;
                let on_right = x == hi;
                grid[z * D + x] = match (on_top, on_bottom, on_left, on_right) {
                    (true, _, true, _) => nw,
                    (true, _, _, true) => ne,
                    (_, true, true, _) => sw,
                    (_, true, _, true) => se,
                    (true, ..) => n_,
                    (_, true, ..) => s_,
                    (_, _, true, _) => w_,
                    (_, _, _, true) => e_,
                    _ => floor_ix,
                };
            }
        }

        // **Is that room even legal?** This is the difference between "the solver is unlikely to build
        // one" and "the grammar cannot express one", and the two call for opposite fixes. Every
        // orthogonally adjacent pair in the hand-laid room must be permitted by the learned support.
        let mut illegal = Vec::new();
        for z in 0..D {
            for x in 0..D {
                let p = grid[z * D + x];
                for (dir, nx, nz) in [
                    (N, x as i64, z as i64 - 1),
                    (E, x as i64 + 1, z as i64),
                    (S, x as i64, z as i64 + 1),
                    (W, x as i64 - 1, z as i64),
                ] {
                    if nx < 0 || nz < 0 || nx as usize >= D || nz as usize >= D {
                        continue;
                    }
                    let q = grid[nz as usize * D + nx as usize];
                    if g.support[dir][p] & (1 << q) == 0 {
                        illegal.push(format!(
                            "{:?} may not sit {} of {:?}",
                            g.prototypes[q],
                            ["north", "east", "south", "west"][dir],
                            g.prototypes[p]
                        ));
                    }
                }
            }
        }
        assert!(
            illegal.is_empty(),
            "the kit's own room is not a legal arrangement under its own grammar, so no solve could \
             ever produce one: {illegal:#?}"
        );

        let f = crate::range::Faces::new(&faces, "wall", 0.5);
        let sealed = crate::range::measure(D, D, &grid, |p, d| f.wall(p, d), |p| f.floor(p), |p| {
            f.doorway(p)
        })
        .expect("a well-formed grid");
        assert_eq!(sealed.enclosure, 1.0, "every cell of a walled room is inside it");
        assert_eq!(sealed.regions, 1);
        assert_eq!(sealed.opening_density, Some(0.0), "no doors yet");

        // Swap one top-edge wall for the doorway tile: still closed, now with one opening.
        grid[lo * D + (lo + 2)] = ix("site/tile_doorway_n", 0.0);
        let with_door =
            crate::range::measure(D, D, &grid, |p, d| f.wall(p, d), |p| f.floor(p), |p| f.doorway(p))
                .expect("a well-formed grid");
        assert_eq!(with_door.enclosure, 1.0, "a doorway is part of the boundary, not a hole in it");
        assert_eq!(with_door.regions, 1);
        assert_eq!(with_door.opening_density, Some(1.0));

        // And knocking a wall out opens it, so the seal above is the walls' doing.
        grid[lo * D + (lo + 1)] = 0;
        let breached =
            crate::range::measure(D, D, &grid, |p, d| f.wall(p, d), |p| f.floor(p), |p| f.doorway(p))
                .expect("a well-formed grid");
        assert_eq!(breached.enclosure, 0.0);
        assert_eq!(breached.regions, 0);
    }

    /// A bounded one-cell composition with nothing in it — enough to carry an interface slot.
    fn empty_tile(id: &str) -> Composition {
        Composition {
            id: id.to_owned(),
            envelope: Envelope::Bounded { size: (1.0, 1.0, 1.0) },
            members: Vec::new(),
            locations: Vec::new(),
            note: None,
        }
    }

    /// **Holes do not inflate the alphabet, and they cannot be allowed to.**
    ///
    /// A tile declaring "a wall fixture goes here" must cost the solver exactly what the same tile
    /// without the hole costs. The alternative — a prototype per candidate filler — is unaffordable
    /// rather than merely untidy: [`MAX_PROTOTYPES`] is 32 because `collapse_grid` packs a domain into
    /// a `u32`, and `constraints::AMO_PAIRWISE_MAX` encodes exactly-one *pairwise*, so the clause
    /// count is quadratic in it. One tile with a four-way slot would take sixteen of the thirty-two
    /// once turned, and two such tiles would refuse the grammar outright.
    ///
    /// This holds by construction — `composition::interface` drops slots, so the faces the learner
    /// dedupes turns by are identical — and this is the test that says so out loud.
    #[test]
    fn a_slot_costs_the_solver_nothing() {
        use crate::composition::{Body, Member};
        let library = Library {
            version: crate::library::LIBRARY_VERSION,
            note: None,
            descriptors: Vec::new(),
        };
        let plain = empty_tile("tile_a");
        let mut holed = empty_tile("tile_a");
        // Four holes, each accepting something different: the arity that would have cost sixteen.
        holed.members = ["a", "b", "c", "d"]
            .iter()
            .enumerate()
            .map(|(i, id)| Member {
                id: (*id).to_owned(),
                body: Body::Slot { accepts: format!("thing-{i}") },
                at: (0.0, 0.0),
                yaw: 0.0,
                lift: 0.1 * i as f32,
                paint: 0,
                of_fingerprint: None,
                note: None,
            })
            .collect();

        let learn = |c: &Composition| {
            from_compositions(
                std::slice::from_ref(c),
                &library,
                1,
                1.0,
                crate::composition::agrees,
            )
            .expect("learns")
        };
        let (a, b) = (learn(&plain), learn(&holed));
        assert!(b.skipped.is_empty(), "a holed tile is still a tile: {:?}", b.skipped);
        assert_eq!(
            a.grammar.len(),
            b.grammar.len(),
            "four holes changed the alphabet from {} to {} prototypes",
            a.grammar.len(),
            b.grammar.len()
        );
        assert_eq!(a.grammar.support, b.grammar.support, "four holes moved the adjacency table");
    }

    // **Swapping the rule changes the grammar** — driven through the learner, not just asserted of
    // ── solve_constrained, against the shipped kit ───────────────────────────────────────────────

    /// **A four-tile kit, built here rather than read off disk.**
    ///
    /// This used to load `assets/grimoire/site`, which was a rule violation hiding in plain sight:
    /// `bevy_cauldron/CLAUDE.md` states *"Tests do not read the shipped assets… The shipped `assets/`
    /// is corpus, and a suite bound to it fails the day somebody imports a kit, which is the thing
    /// this editor exists to do."* Seven solver tests were bound to four authored tiles, so clearing
    /// the project to author new ones took the constraint solver's whole real-data coverage with it.
    ///
    /// The shape is the shipped kit's, because that is what made it a useful fixture: a bare floor, a
    /// wall on one side, a corner on two, and an opening — enough for the learner to find four
    /// prototypes, four turns each, and an adjacency graph that can actually enclose something.
    ///
    /// The **deliberate exception** the crate's own rule names is an asset-contract test, one whose
    /// assertion *is* a fact about what ships. These are not that: they are about the solver.
    pub(super) fn site_kit() -> Composed {
        // A 1 m tile-sized piece. `floor` says nothing about its edges; `wall` says `wall` on the
        // face it fills, which is what `range::Faces` reads to decide a cell is enclosed.
        let plate = |id: &str| Descriptor {
            id: id.to_owned(),
            extent: Extent { footprint: Some((1.0, 1.0)), height: Some(0.1) },
            ..Default::default()
        };
        let mut wall = Descriptor {
            id: "wall".to_owned(),
            extent: Extent { footprint: Some((0.1, 1.0)), height: Some(2.4) },
            ..Default::default()
        };
        // Its whole lattice presents `wall`, which is what `range::Faces` reads to decide a cell is
        // enclosed. Derived from the piece's own extent — a lattice that does not match the piece
        // describes a different piece.
        let div = crate::descriptor::divisions(&wall, 1).expect("measured");
        let mut cells = Vec::new();
        for x in 0..div.0 {
            for y in 0..div.1 {
                for z in 0..div.2 {
                    cells.push(SubCell {
                        at: (x, y, z),
                        solid: true,
                        edge: Some(WALL_TOKEN.to_owned()),
                    });
                }
            }
        }
        wall.subgrid = Some(Subgrid { cells });

        // **A lintel**, which is what makes an opening expressible: 0.4 m of wall at the top of the
        // tile and nothing below it, so the face presents `wall` in one band and `None` through the
        // gap. That is the shape the shipped `site/tile_doorway_n` had — `wall_header` lifted over
        // open air — and the reason a kit without one can only alternate wall and empty.
        let mut header = Descriptor {
            id: "header".to_owned(),
            extent: Extent { footprint: Some((0.1, 1.0)), height: Some(0.4) },
            ..Default::default()
        };
        let div = crate::descriptor::divisions(&header, 1).expect("measured");
        let mut cells = Vec::new();
        for x in 0..div.0 {
            for y in 0..div.1 {
                for z in 0..div.2 {
                    cells.push(SubCell {
                        at: (x, y, z),
                        solid: true,
                        edge: Some(WALL_TOKEN.to_owned()),
                    });
                }
            }
        }
        header.subgrid = Some(Subgrid { cells });

        let library = Library {
            version: crate::library::LIBRARY_VERSION,
            note: None,
            descriptors: vec![plate("floor"), wall, header],
        };

        use crate::composition::{Body, Envelope, Member};
        let member = |id: &str, at: (f32, f32)| Member {
            id: id.to_owned(),
            body: Body::Descriptor { id: id.to_owned(), tip: (0, 0), on: None, patch: None },
            at,
            yaw: 0.0,
            lift: 0.0,
            paint: 0,
            of_fingerprint: None,
            note: None,
        };
        // Members sorted by id — the canonical order `validate` holds every group to.
        let tile = |id: &str, members: Vec<Member>| Composition {
            id: id.to_owned(),
            envelope: Envelope::Bounded { size: (1.0, 2.4, 1.0) },
            members,
            locations: Vec::new(),
            note: None,
        };
        // The wall sits flush against the face it presents — its minimum corner on the tile's edge,
        // which is where `build::drop_at` puts a piece dropped in the edge cell.
        let north = || Member { at: (0.0, -0.45), yaw: 90.0, ..member("wall", (0.0, -0.45)) };
        let west = || Member {
            id: "wall_2".to_owned(),
            at: (-0.45, 0.0),
            ..member("wall", (-0.45, 0.0))
        };
        // The lintel rides at 2.0 m, leaving 2.0 m of clear opening under it.
        let lintel = || Member {
            id: "header".to_owned(),
            at: (0.0, -0.45),
            yaw: 90.0,
            lift: 2.0,
            ..member("header", (0.0, -0.45))
        };
        let comps = vec![
            tile("site/tile_corner_nw", vec![member("floor", (0.0, 0.0)), north(), west()]),
            tile("site/tile_doorway_n", vec![member("floor", (0.0, 0.0)), lintel()]),
            tile("site/tile_floor", vec![member("floor", (0.0, 0.0))]),
            tile("site/tile_wall_n", vec![member("floor", (0.0, 0.0)), north()]),
        ];
        from_compositions(&comps, &library, 1, 1.0, crate::composition::agrees)
            .expect("the fixture kit learns")
    }

    /// A square region of `n` cells a side, with nothing pinned.
    fn region(n: usize) -> Map {
        Map {
            name: "constrained".into(),
            bounds: (n as f32, 3.0, n as f32),
            ..Map::default()
        }
    }

    fn measured(faces: &[Option<Interface>], solved: &Solved) -> crate::range::Measured {
        let f = || crate::range::Faces::new(faces, WALL_TOKEN, WALKABLE_GAP);
        crate::range::measure(
            solved.width,
            solved.height,
            &solved.grid,
            |p, d| f().wall(p, d),
            |p| f().floor(p),
            |p| f().doorway(p),
        )
        .expect("a solved grid measures")
    }

    /// **The thing this whole layer exists for**, end to end and against the shipped kit: ask for
    /// enclosure through the editor's own entry point, and check the metric agrees a room is there.
    #[test]
    fn a_hard_wish_makes_rooms_the_metric_agrees_are_rooms() {
        let Composed { grammar: g, faces, .. } = site_kit();
        let want = 0.25;
        let wishes = Wishes { enclosure: want, enclosure_weight: None };
        let solved = solve_constrained(&region(12), &g, &faces, &wishes, 1.0, 7, ids())
            .expect("a hard, reachable wish must be granted");
        let m = measured(&faces, &solved);
        assert!(m.enclosure >= want, "asked {want}, the metric reports {:.3}", m.enclosure);
        assert!(m.regions > 0, "enclosure above zero means at least one enclosed region");
        assert_eq!(solved.unmet, 0, "a hard wish is met or refused, never charged for");
        assert_eq!(solved.grid.len(), 144, "the grid comes back whole");
        assert!(!solved.stamps.is_empty(), "a composition grammar writes stamps");
        assert!(solved.placements.is_empty(), "and no loose placements");
    }

    /// The same region with no wish. Separated so the difference is attributable: WFC's own arm of
    /// this comparison is the 128-solve run in `docs/research/2026-08-10-expressive-range.md`.
    #[test]
    fn without_a_wish_the_same_region_stays_open() {
        let Composed { grammar: g, faces, .. } = site_kit();
        let wishes = Wishes { enclosure: 0.0, enclosure_weight: None };
        let solved = solve_constrained(&region(12), &g, &faces, &wishes, 1.0, 7, ids())
            .expect("solves");
        assert_eq!(measured(&faces, &solved).regions, 0, "nothing asked for, nothing closed");
    }

    #[test]
    fn an_impossible_wish_is_charged_for_rather_than_refused_when_soft() {
        // Total enclosure is not reachable — the region's border is always outside — so this is the
        // partial-satisfaction case the editor needs: an arrangement comes back anyway, priced.
        let Composed { grammar: g, faces, .. } = site_kit();
        let wishes = Wishes { enclosure: 1.0, enclosure_weight: Some(200) };
        let solved = solve_constrained(&region(12), &g, &faces, &wishes, 1.0, 3, ids())
            .expect("a soft wish must not refuse");
        assert_eq!(solved.unmet, 200, "the wish it could not grant costs exactly its weight");
        assert_eq!(solved.grid.len(), 144);
    }

    #[test]
    fn an_impossible_wish_refuses_by_name_when_hard() {
        let Composed { grammar: g, faces, .. } = site_kit();
        let wishes = Wishes { enclosure: 1.0, enclosure_weight: None };
        let err = solve_constrained(&region(12), &g, &faces, &wishes, 1.0, 3, ids())
            .expect_err("total enclosure is unreachable");
        assert!(err.contains("no arrangement"), "the refusal must say what happened: {err}");
    }

    #[test]
    fn a_constrained_solve_is_reproducible_for_a_seed() {
        let Composed { grammar: g, faces, .. } = site_kit();
        let wishes = Wishes { enclosure: 0.2, enclosure_weight: Some(200) };
        let once = || {
            solve_constrained(&region(10), &g, &faces, &wishes, 1.0, 4242, ids())
                .expect("solves")
                .grid
        };
        let first = once();
        for round in 1..4 {
            assert_eq!(once(), first, "round {round} produced a different world from one seed");
        }
    }

    #[test]
    fn different_seeds_give_different_worlds() {
        let Composed { grammar: g, faces, .. } = site_kit();
        let wishes = Wishes { enclosure: 0.2, enclosure_weight: Some(200) };
        let grids: Vec<Vec<usize>> = (1..=5u64)
            .map(|s| {
                solve_constrained(&region(10), &g, &faces, &wishes, 1.0, s, ids())
                    .expect("solves")
                    .grid
            })
            .collect();
        let distinct: std::collections::BTreeSet<&Vec<usize>> = grids.iter().collect();
        assert_eq!(distinct.len(), 5, "five seeds must give five arrangements");
    }

    #[test]
    fn interfaces_that_do_not_match_the_grammar_are_refused() {
        // The two come back together from `from_compositions` for a reason: a mismatched pair means
        // the constraint and the metric are indexing different kits, which is the drift that costs a
        // day of blaming the metric.
        let Composed { grammar: g, mut faces, .. } = site_kit();
        faces.pop();
        let wishes = Wishes { enclosure: 0.2, enclosure_weight: None };
        let err = solve_constrained(&region(8), &g, &faces, &wishes, 1.0, 1, ids())
            .expect_err("a short interface list must be refused");
        assert!(err.contains("interfaces"), "the refusal must name the mismatch: {err}");
    }

    /// the default rule.
    ///
    /// If the face comparison were inline, as it is in `declared`, both calls below would produce
    /// the same `support` and this would fail. That is the invariant FVS-R-7 states, and it is what
    /// keeps the edge-versus-corner question (FVS-R-11) from gating anything: answering it later is
    /// passing a different argument.
    #[test]
    fn swapping_the_rule_changes_the_learned_grammar() {
        let comps = vec![empty_tile("tile_a"), empty_tile("tile_b")];
        let library = Library {
            version: crate::library::LIBRARY_VERSION,
            note: None,
            descriptors: Vec::new(),
        };

        let Composed { grammar: permissive, skipped, .. } =
            from_compositions(&comps, &library, 1, 1.0, |_, _, _| true).expect("learns");
        assert!(skipped.is_empty(), "both tiles are one cell and bounded: {skipped:?}");
        assert_eq!(permissive.len(), 3, "Empty plus the two tiles");

        let refusing = from_compositions(&comps, &library, 1, 1.0, |_, _, _| false)
            .expect("learns")
            .grammar;

        // `Empty` keeps its unconstrained role under BOTH rules — it is not routed through `agrees`,
        // because a grammar that cannot say "nothing goes here" cannot leave a doorway.
        assert_eq!(
            permissive.support[N][0], refusing.support[N][0],
            "Empty's row must not depend on the adjacency rule"
        );
        // The tiles' rows must, or the rule is not reaching the grammar at all.
        assert_ne!(
            permissive.support[N][1], refusing.support[N][1],
            "the rule is a parameter and this proves it: an inline comparison would give one answer"
        );
        assert_eq!(
            refusing.support[N][1] & 0b110,
            0,
            "a rule that refuses everything must leave no tile-to-tile support"
        );
    }

    /// **The adjacency rule is substitutable, which is the whole invariant.**
    ///
    /// FVS-R-7's stated non-negotiable: adjacency goes through `agrees`, never an inline face
    /// comparison, so the edge-versus-corner question cannot gate the grammar. Karth & Smith —
    /// *"any arbitrary adjacency validity function can be substituted here… without changing the
    /// WFC solver itself."*
    ///
    /// Proved by substituting one: the same tiles, learned twice, with a rule that refuses
    /// everything and a rule that permits everything. If the comparison were inline the two
    /// grammars would be identical, which is exactly what this asserts they are not.
    #[test]
    fn the_adjacency_rule_is_a_parameter_and_swapping_it_changes_the_grammar() {
        let wall = iface(Some("wall"));
        let floor = iface(None);

        // The shipped rule: a wall face and a nothing face disagree.
        assert!(crate::composition::agrees(&wall, &wall, N));
        assert!(crate::composition::agrees(&floor, &floor, N));
        assert!(
            !crate::composition::agrees(&wall, &floor, N),
            "`None` is a token in its own right and matches only `None`"
        );

        // A face with no bands has no seam to disagree about.
        let blank = crate::composition::Interface { faces: Default::default(), faults: Vec::new() };
        assert!(crate::composition::agrees(&blank, &wall, N));
    }

    fn map_with(bounds: (f32, f32, f32), pieces: &[(&str, f32, f32, f32, bool)]) -> Map {
        let mut m = Map {
            name: "example".into(),
            bounds,
            ..Map::default()
        };
        for (i, (d, x, z, yaw, owned)) in pieces.iter().enumerate() {
            m.placements.push(Placed {
                id: format!("p{i}"),
                descriptor: (*d).to_owned(),
                at: (*x, *z),
                yaw: *yaw,
                owned: *owned,
                owned_because: owned.then(|| "test".to_owned()),
                ..Placed::default()
            });
        }
        m
    }

    fn ids() -> impl FnMut() -> String {
        let mut n = 0;
        move || {
            n += 1;
            format!("g{n}")
        }
    }

    #[test]
    fn an_empty_map_teaches_only_emptiness() {
        let g = learn(&map_with((4.0, 3.0, 4.0), &[]), 1.0).unwrap_or_else(|e| panic!("{e}"));
        assert_eq!(g.prototypes, vec![Prototype::Empty]);
        // And a grammar of one thing is not something to continue.
        let err = solve(&map_with((4.0, 3.0, 4.0), &[]), &g, 1.0, 1, ids())
            .err()
            .unwrap_or_default();
        assert!(err.contains("nothing has been placed"), "{err}");
    }

    /// Yaw is part of the prototype: a wall turned 90 degrees meets different neighbours.
    #[test]
    fn the_same_piece_at_two_yaws_is_two_prototypes() {
        let m = map_with(
            (4.0, 3.0, 4.0),
            &[("wall", -1.5, -1.5, 0.0, false), ("wall", -0.5, -1.5, 90.0, false)],
        );
        let g = learn(&m, 1.0).unwrap_or_else(|e| panic!("{e}"));
        assert_eq!(g.len(), 3, "empty + two yaws: {:?}", g.prototypes);
    }

    /// A yaw a hair off is the same prototype — otherwise float noise multiplies the alphabet.
    #[test]
    fn yaw_is_quantised_so_float_noise_is_not_a_new_prototype() {
        let m = map_with(
            (4.0, 3.0, 4.0),
            &[("wall", -1.5, -1.5, 90.0, false), ("wall", -0.5, -1.5, 90.0001, false)],
        );
        assert_eq!(learn(&m, 1.0).unwrap_or_else(|e| panic!("{e}")).len(), 2);
    }

    /// **The point of the whole module**: what an author placed is what the solver may place, and an
    /// owned cell keeps exactly what they put there.
    #[test]
    fn an_owned_cell_survives_the_solve() {
        let m = map_with(
            (4.0, 3.0, 4.0),
            &[
                ("floor", -1.5, -1.5, 0.0, true),
                ("floor", -0.5, -1.5, 0.0, false),
                ("floor", -1.5, -0.5, 0.0, false),
            ],
        );
        let g = learn(&m, 1.0).unwrap_or_else(|e| panic!("{e}"));
        let s = solve(&m, &g, 1.0, 7, ids()).unwrap_or_else(|e| panic!("{e}"));

        assert_eq!(s.owned_cells, 1);
        // The pinned cell is not re-emitted — it is already in the map, unchanged.
        assert!(
            !s.placements.iter().any(|p| p.at == (-1.5, -1.5)),
            "the owned cell was overwritten"
        );
        assert_eq!(s.free_cells, 15, "4x4 grid minus the one pinned cell");
    }

    /// Only what the author drew. A grammar learned from floors cannot produce a chair.
    #[test]
    fn the_solver_only_places_what_the_example_contains() {
        let m = map_with(
            (4.0, 3.0, 4.0),
            &[("floor", -1.5, -1.5, 0.0, false), ("floor", -0.5, -1.5, 0.0, false)],
        );
        let g = learn(&m, 1.0).unwrap_or_else(|e| panic!("{e}"));
        let s = solve(&m, &g, 1.0, 3, ids()).unwrap_or_else(|e| panic!("{e}"));
        for p in &s.placements {
            assert_eq!(p.descriptor, "floor", "invented a piece nobody placed");
        }
    }

    /// A map with one crate in it should not solve to a floor of crates. Empty meeting empty is what
    /// makes negative space expressible.
    #[test]
    fn empty_can_meet_empty_so_a_sparse_map_stays_sparse() {
        let m = map_with((6.0, 3.0, 6.0), &[("crate", 0.5, 0.5, 0.0, true)]);
        let g = learn(&m, 1.0).unwrap_or_else(|e| panic!("{e}"));
        let s = solve(&m, &g, 1.0, 11, ids()).unwrap_or_else(|e| panic!("{e}"));
        assert!(
            s.placements.len() < s.free_cells,
            "every free cell was filled ({} of {}) — the grammar cannot express empty space",
            s.placements.len(),
            s.free_cells
        );
    }

    /// Same seed, same arrangement. The solver is part of an editor, and an author who presses the
    /// key twice on the same map should be able to tell whether anything changed.
    #[test]
    fn a_solve_is_reproducible_for_a_seed() {
        let m = map_with(
            (5.0, 3.0, 5.0),
            &[("floor", -1.5, -1.5, 0.0, false), ("wall", -0.5, -1.5, 90.0, false)],
        );
        let g = learn(&m, 1.0).unwrap_or_else(|e| panic!("{e}"));
        let a = solve(&m, &g, 1.0, 42, ids()).unwrap_or_else(|e| panic!("{e}"));
        let b = solve(&m, &g, 1.0, 42, ids()).unwrap_or_else(|e| panic!("{e}"));
        let key = |s: &Solved| -> Vec<(String, i64, i64)> {
            s.placements
                .iter()
                .map(|p| (p.descriptor.clone(), (p.at.0 * 100.0) as i64, (p.at.1 * 100.0) as i64))
                .collect()
        };
        assert_eq!(key(&a), key(&b));
    }

    /// An owned piece the grammar has never seen cannot be pinned to a prototype, and saying so beats
    /// dropping the pin and solving over the top of it.
    #[test]
    fn an_owned_piece_outside_the_grammar_is_refused() {
        let example = map_with((4.0, 3.0, 4.0), &[("floor", -1.5, -1.5, 0.0, false)]);
        let g = learn(&example, 1.0).unwrap_or_else(|e| panic!("{e}"));

        let other = map_with((4.0, 3.0, 4.0), &[("statue", -0.5, -0.5, 0.0, true)]);
        let err = solve(&other, &g, 1.0, 1, ids()).err().unwrap_or_default();
        assert!(err.contains("not in the learned grammar"), "{err}");
    }

    #[test]
    fn a_zero_cell_is_refused_rather_than_looping() {
        assert!(learn(&map_with((4.0, 3.0, 4.0), &[]), 0.0).is_err());
        assert!(learn(&map_with((4.0, 3.0, 4.0), &[]), f32::NAN).is_err());
    }

    /// The domain is a `u32`, so the alphabet has a hard ceiling and the error should name it rather
    /// than letting `collapse_grid`'s assert fire.
    #[test]
    fn too_many_prototypes_is_a_named_error() {
        let pieces: Vec<(String, f32, f32, f32, bool)> = (0..MAX_PROTOTYPES + 4)
            .map(|i| {
                (
                    format!("piece_{i}"),
                    -19.5 + i as f32,
                    -19.5,
                    0.0,
                    false,
                )
            })
            .collect();
        let refs: Vec<(&str, f32, f32, f32, bool)> = pieces
            .iter()
            .map(|(d, x, z, y, o)| (d.as_str(), *x, *z, *y, *o))
            .collect();
        let err = learn(&map_with((40.0, 3.0, 40.0), &refs), 1.0)
            .err()
            .unwrap_or_default();
        assert!(err.contains(&MAX_PROTOTYPES.to_string()), "{err}");
    }
}

// ---------------------------------------------------------------------------------------------
// The declared half
// ---------------------------------------------------------------------------------------------

// **A grammar built from what tiles DECLARE, rather than from what an author has already drawn.**
//
// [`learn`] answers *"more of what is here"* and cannot answer anything on an empty map — there are
// no observed pairs to generalise from. This answers *"whatever the kit says may meet"*, which is
// the other half of the same algorithm and needs no example at all.
//
// # Two sources, one solver, and neither is a fallback for the other
//
// Karth & Smith (*Addressing the Fundamental Tension of PCGML with Discriminative Learning*, FDG
// 2019) name the distinction exactly. Gumin's WFC *"simply allows any tile-compatible overlapping
// patterns to be placed adjacent to one another, even if they were never seen adjacent in the single
// source image"* — they call this **Most General Generalization**, the inverse of learning from
// observation. That is precisely what this function does over the token relation, and what [`learn`]
// deliberately does not.
//
// So the author picks a source and gets what that source can express. Neither silently substitutes
// for the other: a library with no tokens produces no prototypes here and says so, rather than
// quietly falling through to the learned grammar and generating something the author did not ask
// for.
//
// # Matching is equality, including the length of a face
//
// `support[dir][p]` holds `q` when `p`'s `dir` face is *the same sequence* as `q`'s facing one —
// Merrell & Manocha 2009 §4.3's rule, which [`crate::adjacency`] already applies to a finished map.
// Two pieces whose lattices are different sizes present faces of different lengths, and those never
// match. That is **conservative rather than permissive**: the pair is refused, not allowed, so this
// cannot invent an adjacency the tokens do not state.
//
// An unlabelled cell is `None`, and `None` equals only `None`. It is not a wildcard — which is what
// lets a doorway's open middle meet only another open middle, and is why a kit with a single token

/// **A composition turned about its own anchor**, for deriving what it presents at that yaw.
///
/// Through `composition::rotate_xz` and `add_yaw` — the exact pair [`crate::composition::expand`]
/// turns a stamp by — so a tile's learned faces and the faces it actually stamps with cannot come
/// from two different conventions. `rotate_xz`'s doc names the cost of a second one: Bevy's yaw
/// turns +X toward −Z, and getting it backwards "mirrors every composition without failing
/// anything".
///
/// The envelope's x and z swap on a quarter turn, which matters for a non-square tile and is free
/// for the square ones a grid uses.
fn turn_composition(c: &Composition, yaw: f32) -> Composition {
    let mut out = c.clone();
    if let Envelope::Bounded { size } = out.envelope {
        let quarter = ((yaw / 90.0).round() as i32).rem_euclid(4);
        if quarter % 2 == 1 {
            out.envelope = Envelope::Bounded { size: (size.2, size.1, size.0) };
        }
    }
    for m in &mut out.members {
        m.at = crate::composition::rotate_xz(m.at, yaw);
        m.yaw = crate::composition::add_yaw(m.yaw, yaw);
    }
    out
}

/// **A grammar over compositions**, with adjacency behind a substitutable rule.
///
/// FVS-R-7. The sibling of [`learn`] and [`declared`]: where those read placements and descriptor
/// lattices, this reads the **composition set** — which is the unit this project made solvable, a
/// group of floor-plus-wall being a tile where the 0.1 x 1.0 m wall never could be.
///
/// # The seam is the point
///
/// `agrees` is a parameter, not a call. Karth & Smith: *"any arbitrary adjacency validity function
/// can be substituted here… without changing the WFC solver itself."* The default is
/// [`composition::agrees`]; passing another is how the edge-versus-corner question (FVS-R-11, still
/// blocked on Lagae & Dutré) gets answered later without touching this function, the solver, or the
/// prototypes.
///
/// # Only `Bounded` compositions
///
/// `composition::interface` returns `None` for an `Anchored` group — it claims no tile, so it has no
/// edge to present and a solver could not place it. Skipped by name in the report rather than
/// silently, on `declared`'s rule: a grammar quietly missing half the kit generates confidently and
/// wrongly.
///
/// # The weights are uniform, and that is a statement rather than a default
///
/// [`learn`] weights by how often the author used a piece. There is no such count here: a
/// composition set is a vocabulary, not an arrangement. Weighting by anything derivable from the set
/// itself — member count, footprint — would be inventing a frequency nobody expressed. **This is the
/// open half of FVS-R-7**, recorded on the backlog item: `site_67` yields three adjacency pairs, so
/// the map cannot supply them either.
/// A grammar over compositions, with what it refused and what each prototype presents.
///
/// # Why the interfaces come back out
///
/// A caller that wants to read a *solved grid* — [`crate::range`] measuring enclosure, an editor
/// reporting a seam fault — needs to know which faces of each prototype are walls. `Grammar` does not
/// carry that, and it cannot be re-derived from outside: the turned interface is produced by a private
/// `turn_composition`, so a second derivation would be a second rotation convention, which is exactly
/// the failure [`crate::composition::rotate_xz`]'s doc warns costs you a mirrored kit with nothing
/// going red. Returning what was already computed is one path; re-deriving it would be two.
#[derive(Debug)]
pub struct Composed {
    pub grammar: Grammar,
    /// Compositions that could not become tiles, each with the reason, by name. A grammar quietly
    /// missing half the kit generates confidently and wrongly — `declared`'s rule.
    pub skipped: Vec<String>,
    /// What each prototype presents, indexed alongside `grammar.prototypes`.
    ///
    /// Index 0 is [`Prototype::Empty`]'s, and it is `None`: empty presents nothing and may sit beside
    /// anything, which is the unconstrained role that lets the solver leave a gap.
    pub faces: Vec<Option<Interface>>,
}

pub fn from_compositions(
    compositions: &[Composition],
    library: &Library,
    // How finely the project divides a tile — `interface` reads faces off that lattice, and this is
    // the project's own number rather than one this function may choose.
    per_tile: u32,
    cell: f32,
    agrees: impl Fn(&Interface, &Interface, Dir) -> bool,
) -> Result<Composed, String> {
    if per_tile == 0 {
        return Err("composition grammar: the project divides each tile 0 ways".to_owned());
    }
    if !(cell.is_finite() && cell > 0.0) {
        return Err(format!("composition grammar: a cell of {cell} m is not a grid"));
    }

    // `Empty` is index 0 and permitted everywhere, exactly as in `learn` and `declared` — a grammar
    // that cannot say "nothing goes here" cannot leave a doorway.
    let mut prototypes = vec![Prototype::Empty];
    let mut interfaces: Vec<Option<Interface>> = vec![None];
    // `Empty` is one tile like any other: it is the grammar's way of saying "nothing goes here", and
    // weighting it above or below the authored tiles would be a claim about how holey a room should
    // be that nobody has made.
    let mut weights: Vec<f64> = vec![1.0];
    let mut skipped: Vec<String> = Vec::new();

    for c in compositions {
        let size = match c.envelope {
            Envelope::Bounded { size } => size,
            Envelope::Anchored => {
                skipped.push(format!("`{}` is anchored, so it presents no edge to match", c.id));
                continue;
            }
        };
        // **A tile grammar is a grammar over tiles of the grid's size** — `declared`'s rule, and the
        // same arithmetic: `solve` lays prototypes at `cell` centres, so a group that is not one cell
        // across is placed at a spacing with nothing to do with its extent.
        if (size.0 - cell).abs() > CELL_EPSILON || (size.2 - cell).abs() > CELL_EPSILON {
            skipped.push(format!(
                "`{}` is {:.2} x {:.2} m and the grid is {cell:.2} m, so it cannot be a tile",
                c.id, size.0, size.2
            ));
            continue;
        }
        // **Four turns per tile, and that is not an optimisation — it is what makes the kit
        // solvable at all.**
        //
        // Measured on the shipped site kit before this existed: every wall tile's north support was
        // `Empty` and nothing else. A wall tile presents `wall` outward on ONE face, so the tile
        // across that seam has to present `wall` back — and only the same tile turned 180 degrees
        // does. With yaw 0 alone the kit could express floor, empty, and no wall meeting anything.
        // `one_wall_tile_covers_four_orientations` is the authored kit's own statement of this: one
        // wall tile IS four, by rotation.
        //
        // **The turned interface is DERIVED, never rotated.** Turning the composition through
        // `rotate_xz` and `add_yaw` — the pair a stamp already turns by — and re-deriving the face
        // means there is no second rotation convention to get backwards. `rotate_xz`'s own doc names
        // that failure: a mirrored copy "mirrors every composition without failing anything".
        let mut seen_faces: Vec<[Vec<crate::composition::Band>; 4]> = Vec::new();
        let first_proto = prototypes.len();
        for quarter in 0..4u8 {
            let yaw = quarter as f32 * 90.0;
            let turned = turn_composition(c, yaw);
            let iface = match crate::composition::interface(&turned, compositions, library, per_tile)
            {
                Ok(Some(i)) => i,
                Ok(None) => {
                    if quarter == 0 {
                        skipped.push(format!("`{}` derives no interface", c.id));
                    }
                    continue;
                }
                Err(e) => return Err(format!("composition grammar: `{}`: {e}", c.id)),
            };
            // **Deduplicated within one composition only**, on `declared`'s rule and for its reason:
            // a symmetric tile presents the same four faces at 0 and at 180, and keeping both would
            // spend two of the solver's thirty-two saying one thing. Across compositions it would be
            // wrong — identical faces make two tiles interchangeable to the propagator, not the same
            // tile.
            if seen_faces.contains(&iface.faces) {
                continue;
            }
            seen_faces.push(iface.faces.clone());
            prototypes.push(Prototype::Composed { composition: c.id.clone(), yaw });
            interfaces.push(Some(iface));
        }
        // **One tile, one unit of weight — split across the turns it survived as.**
        //
        // Uniform per PROTOTYPE is not uniform per tile, and the difference is not a design choice:
        // a symmetric tile dedupes to one prototype while an asymmetric one keeps four, so a flat
        // 1.0 each makes the symmetric tile a quarter as likely as its neighbours. Measured on the
        // shipped kit before this: `tile_floor` is the only symmetric tile and came out at **7.4%**
        // of 864 cells against ~23% for each of the other three — open floor, the material a room is
        // mostly made of, was the rarest thing in the building.
        //
        // The dedup is right and stays; it is what keeps four tiles inside the solver's
        // thirty-two. This makes "uniform" mean uniform over the vocabulary the author wrote rather
        // than over the solver's expansion of it, which is the only reading anybody intended.
        let turns = prototypes.len() - first_proto;
        if turns > 0 {
            let share = 1.0 / turns as f64;
            for _ in 0..turns {
                weights.push(share);
            }
        }
    }

    // **No tile is a refusal here, not an empty grammar handed on.** A grammar of `Empty` alone
    // reached the solver, whose refusal is about placements ("nothing has been placed yet") — the
    // wrong cause for a composition set, and one an author cannot act on. Measured on Sanctuary's
    // project (E-083, #132): 16 compositions, all `Anchored`, and the only answer was that one. The
    // reasons are already collected by name; this says them, and says what a tile is.
    if prototypes.len() == 1 {
        const SHOWN: usize = 5;
        let mut why = skipped.iter().take(SHOWN).cloned().collect::<Vec<_>>().join("; ");
        if skipped.len() > SHOWN {
            why.push_str(&format!("; and {} more", skipped.len() - SHOWN));
        }
        return Err(if compositions.is_empty() {
            "composition grammar: the project has no compositions, so there is no tile to solve \
             with. A tile is a composition with a `Bounded` envelope one grid cell across."
                .to_owned()
        } else {
            format!(
                "composition grammar: none of the {} composition(s) is a tile, so there is nothing \
                 to solve with: {why}. A tile is a composition with a `Bounded` envelope {cell:.2} \
                 m across; an `Anchored` group is placed whole and is never one.",
                compositions.len()
            )
        });
    }

    // **Counted after building, not stopped at the ceiling.** This used to refuse the moment the
    // 33rd prototype appeared, which meant the message could say *"more than 32"* and nothing else —
    // an author over budget was told they were over and not by how much, so "narrow the set" had no
    // target. `declared` was already checked at the end for exactly that reason, and the two now
    // agree. Building past the cap costs one more `interface` derivation per tile and buys the only
    // number that makes the refusal actionable.
    if prototypes.len() > MAX_PROTOTYPES {
        return Err(format!(
            "composition grammar: {} prototypes, over the {MAX_PROTOTYPES} the solver's domain \
             holds. That is {} distinct turned tiles from {} composition(s) — narrow the selection \
             rather than raising the cap, which is a `u32` the dungeon generator shares.",
            prototypes.len(),
            prototypes.len() - 1,
            compositions
                .iter()
                .filter(|c| matches!(c.envelope, crate::composition::Envelope::Bounded { .. }))
                .count()
        ));
    }

    let n = prototypes.len();
    let mut support: [Vec<u32>; 4] = [vec![0; n], vec![0; n], vec![0; n], vec![0; n]];
    for (p, pi) in interfaces.iter().enumerate() {
        for (q, qi) in interfaces.iter().enumerate() {
            for dir in [N, E, S, W] {
                // `Empty` presents nothing and may sit beside anything — the unconstrained role it
                // has in both siblings, and what lets the solver leave a gap.
                let ok = match (pi, qi) {
                    (None, _) | (_, None) => true,
                    (Some(a), Some(b)) => agrees(a, b, dir),
                };
                if ok {
                    support[dir][p] |= 1 << q;
                }
            }
        }
    }

    Ok(Composed {
        grammar: Grammar {
            prototypes,
            // Uniform per authored TILE — see the split above. `learn` counts placements; a
            // vocabulary has no count, so every tile the author wrote is equally likely.
            weights,
            support,
        },
        skipped,
        faces: interfaces,
    })
}

/// still expresses more than that token alone suggests.
///
/// # Prototypes are deduplicated by what they present
///
/// A wall whose lattice is symmetric presents the same four faces at 0° and at 180°, so those are one
/// prototype and not two. This is not an optimisation bolted on to fit the ceiling: turning a
/// symmetric tile produces the same tile, and keeping both would spend two of the solver's thirty-two
/// saying one thing. Measured on the shipped site kit: 8 tokened descriptors × 4 turns is 32
/// candidates, and 11 of them are distinct.
///
/// **Within one descriptor only.** Deduplicating across the library was tried and was wrong:
/// `site/column` presents exactly the faces `site/wall` does, so a global pass deleted the column and
/// the solver could never place one. Identical faces make two tiles interchangeable to the
/// propagator; they do not make them the same mesh.
pub fn declared(library: &Library, per_tile: u32, cell: f32) -> Result<Grammar, String> {
    if per_tile == 0 {
        return Err("declared grammar: the project divides each tile 0 ways".to_owned());
    }
    if !(cell.is_finite() && cell > 0.0) {
        return Err(format!("declared grammar: a cell of {cell} m is not a grid"));
    }
    let mut wrong_size: Vec<String> = Vec::new();
    // `Empty` is index 0 and permitted everywhere, exactly as in `learn` — a grammar that cannot say
    // "nothing goes here" cannot leave a doorway.
    let mut prototypes = vec![Prototype::Empty];
    let mut faces: Vec<[Vec<Option<String>>; 4]> = vec![Default::default()];

    for d in &library.descriptors {
        let Some(grid) = &d.subgrid else { continue };
        if !grid.cells.iter().any(|c| c.edge.is_some()) {
            continue;
        }
        // **A tile grammar is a grammar over tiles of the grid's size.**
        //
        // `solve` lays prototypes at `cell` centres, so a piece that is not one cell across is placed
        // at a spacing that has nothing to do with its extent. Measured on the shipped site kit at
        // `cell = 1.0`: `site/wall_doorway` is 0.46 x 2.06 m and would overlap its neighbour by about
        // a metre, while `site/wall_corner` at 0.22 x 0.22 m would leave three quarters of a metre of
        // gap — every declared adjacency satisfied, and geometry nobody can use.
        //
        // Merrell & Manocha's model synthesis and the Wang-tile family both assume a uniform tile;
        // this is that assumption stated instead of quietly violated. Collected and refused by name
        // below rather than skipped, because a grammar silently missing half the kit generates
        // something the author cannot account for.
        let fits = crate::descriptor::placed_footprint(d).is_some_and(|(w, dep)| {
            (w - cell).abs() <= CELL_EPSILON && (dep - cell).abs() <= CELL_EPSILON
        });
        if !fits {
            let size = crate::descriptor::placed_footprint(d)
                .map(|(w, dep)| format!("{w} x {dep} m"))
                .unwrap_or_else(|| "unmeasured".to_owned());
            wrong_size.push(format!("`{}` is {size}", d.id));
            continue;
        }
        let div = crate::descriptor::divisions(d, per_tile)?;
        // **Per descriptor, not across the library.** Deduplicating globally was measured and was
        // wrong: `site/column` presents exactly the faces `site/wall` does, so a global pass deleted
        // the column and the solver could never place one. Two tiles that present the same faces are
        // interchangeable to the *propagator* and are still two different meshes an author asked for.
        let mine = faces.len();
        for quarter in 0..4u8 {
            let turned = grid.rotated(quarter, div);
            let tdiv = crate::descriptor::rotate_div(div, quarter);
            let read = |dir: usize| -> Vec<Option<String>> {
                crate::adjacency::face(&turned, dir, tdiv)
                    .into_iter()
                    .map(|t| t.map(str::to_owned))
                    .collect()
            };
            let sig = [read(N), read(E), read(S), read(W)];
            // Same faces, same tile. Skipping here is what keeps a symmetric piece from spending two
            // of the solver's thirty-two slots saying one thing.
            if faces[mine..].contains(&sig) {
                continue;
            }
            prototypes.push(Prototype::Piece {
                descriptor: d.id.clone(),
                yaw: quarter as f32 * 90.0,
            });
            faces.push(sig);
        }
    }

    if prototypes.len() == 1 {
        if !wrong_size.is_empty() {
            wrong_size.sort_unstable();
            return Err(format!(
                "declared grammar: every tokened piece is the wrong size for a {cell} m cell, so a \
                 solve would place them at a spacing unrelated to their extents — {}. A tile grammar \
                 needs tiles of the grid's size; generate from the map instead, or author a kit on \
                 the cell.",
                wrong_size.join(", ")
            ));
        }
        return Err(
            "declared grammar: no descriptor in this library carries an edge token, so there is \
             nothing to build a grammar from. Author tokens on the Tiles tab, or generate from the \
             map instead."
                .to_owned(),
        );
    }
    if prototypes.len() > MAX_PROTOTYPES {
        // Named and counted, never sampled: a generator that silently drops tiles produces output
        // that looks like the kit and is missing a third of it.
        return Err(format!(
            "declared grammar: {} prototypes, over the {MAX_PROTOTYPES} the solver's domain holds. \
             That is {} distinct turned tiles from {} tokened descriptor(s) — narrow the kit rather \
             than raising the cap, which is a `u32` the dungeon generator shares.",
            prototypes.len(),
            prototypes.len() - 1,
            library
                .descriptors
                .iter()
                .filter(|d| d
                    .subgrid
                    .as_ref()
                    .is_some_and(|g| g.cells.iter().any(|c| c.edge.is_some())))
                .count()
        ));
    }

    let n = prototypes.len();
    // Every prototype is equally likely. A declared grammar has no observations to count, and
    // inventing a weight would be a preference nobody stated.
    let weights = vec![1.0f64; n];
    let mut support: [Vec<u32>; 4] = [vec![0; n], vec![0; n], vec![0; n], vec![0; n]];
    for (p, pf) in faces.iter().enumerate() {
        for (q, qf) in faces.iter().enumerate() {
            for (dir, opposite) in [(N, S), (E, W), (S, N), (W, E)] {
                // `Empty` presents nothing and may sit beside anything — the same unconstrained role
                // it has in `learn`, and what lets the solver leave a gap.
                let ok = p == 0 || q == 0 || pf[dir] == qf[opposite];
                if ok {
                    support[dir][p] |= 1 << q;
                }
            }
        }
    }
    Ok(Grammar {
        prototypes,
        weights,
        support,
    })
}