Skip to content

SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.

159 KB
Raw Blame
//! The constraint solver.
//!
//! Unknowns are the coordinates of every non-fixed point and the radius of every circle. Each
//! constraint contributes residuals (zero when satisfied, in millimetres so that all rows have a
//! comparable scale). The system is split into connected components and each is solved with a
//! damped Gauss–Newton (Levenberg–Marquardt) iteration on a dense Jacobian built from local
//! central differences. Small steps from the current positions are preferred, so
//! under-constrained sketches move as little as possible. Afterwards the rank of the Jacobian
//! gives the remaining degrees of freedom and which points are fully determined.
//!
//! Unknowns the constraints pin down one after another from the constants (a point at the
//! crossing of two loci on known points, see [`pinned`]) are eliminated exactly, without
//! the dense matrices: values the constructive seed placed stay constants for LM, and the rank
//! analysis runs only on what remains.

use serde::{Deserialize, Serialize};
use solidcore_record::{Seg2, Vec2};
use solidcraft_geom::prelude::*;

use crate::decompose::Budget;
use crate::linalg::{Mat, determined_vars, solve as lin_solve};
use crate::model::{ConstraintKind, CurveKind, Sketch, TwoCircles};
#[cfg(feature = "solver-profiling")]
use crate::profiling::{self, Decision, Phase, StopReason};
use crate::union_find::{find, union};

#[path = "cursor.rs"]
mod cursor;
pub use cursor::{move_line_towards, move_point_towards};

#[path = "redundancy.rs"]
mod redundancy;
pub use redundancy::{CONSISTENT, constraint_residual, determined_by};

const MAX_ITERS: usize = 500;
/// Variables in one connected component. Each component is solved as a dense system: an n by n
/// matrix for the Levenberg-Marquardt step, rows by n for the Jacobian. 4,000 variables is a
/// 128 MB matrix; past that the request grows to gigabytes and an allocation failure aborts the
/// process, which no panic guard can intercept. A component this size is reported as failed and
/// its geometry left alone.
pub const MAX_COMPONENT_VARS: usize = 4_000;
/// Converged when every residual is below this (mm).
const TOL: f64 = 1e-9;
/// A solution is accepted when every residual is below this (mm).
const ACCEPT: f64 = 1e-6;
/// A solve that only asks whether it succeeds ([`Analysis::StatusOnly`], the held solves of a
/// drag) gives up on a component once LM has stalled far from a solution: over the last
/// `STALL_ITERS` iterations the sum of squared residuals fell by at most `STALL_DECREASE` of
/// itself, and the largest residual is still above `STALL_RESIDUAL` (mm). Such a run sits in a
/// least-squares valley of constraints that conflict, crawling until `MAX_ITERS`, and a held
/// solve runs LM up to three times (#6606). Measured on about 62,000 LM runs that succeeded
/// (the sketch and engine tests and 120 generated sketch scripts with 2,900 drags), the slowest
/// still fell by 1.4e-3 of itself over any 20 iterations while it was that far off: some cross
/// a plateau for dozens of iterations and then converge, so the threshold stays a hundred times
/// below that. Other solves keep iterating: their report names what a failure leaves violated.
const STALL_ITERS: usize = 20;
const STALL_DECREASE: f64 = 1e-5;
const STALL_RESIDUAL: f64 = 1e-4;
/// How much less it costs a solve to move a point held on a curve than any other point: such a
/// point is placed relative to the curve, so it follows the curve rather than the curve it.
const SLIDE_WEIGHT: f64 = 0.01;

#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum SolveStatus {
    /// All constraints satisfied.
    Solved,
    /// The constraints conflict (or the solver could not satisfy them); geometry was left as it
    /// was before solving.
    Failed,
}

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct SolveReport {
    pub status: SolveStatus,
    /// Remaining degrees of freedom (0 = fully constrained).
    pub dof: usize,
    pub iterations: usize,
    pub max_residual: f64,
    /// Constraints still violated after a failed solve, and the ones in `folded`.
    pub failing: Vec<String>,
    /// Constraints whose orientation (a triangle's turn, an offset's side) the solve for edited
    /// driving values flipped relative to the stored solved state, where continuation could
    /// not keep it. The solve keeps that best result (an evaluation shows it with a warning);
    /// a command that changes values refuses it.
    #[serde(default)]
    pub folded: Vec<String>,
    /// Components this solve stepped from the stored solved state to the edited values.
    #[serde(default)]
    pub continuations: usize,
    /// Per point: fully determined by constraints (fixed points count as determined).
    pub point_determined: Vec<bool>,
    /// Per curve: all of its defining values determined.
    pub curve_determined: Vec<bool>,
    /// Constraints that remove no degree of freedom: everything they ask for is already implied
    /// by the constraints before them (a second "vertical" on a side two rectangles share).
    /// They hold, so they are not a conflict; they are shown as redundant. Only from a full
    /// analysis, and only for components of at most a few hundred variables.
    #[serde(default)]
    pub redundant: Vec<String>,
    /// The unknowns of the largest connected group too large to solve ([`MAX_COMPONENT_VARS`]):
    /// the solve fails without a conflicting constraint to name (#5280).
    #[serde(default)]
    pub oversized: Option<usize>,
}

impl SolveReport {
    pub fn ok(&self) -> bool {
        self.status == SolveStatus::Solved
    }
    pub fn fully_constrained(&self) -> bool {
        self.dof == 0
    }
    /// Solved, and no orientation of the stored state flipped: what a value edit accepts.
    pub fn keeps_orientation(&self) -> bool {
        self.ok() && self.folded.is_empty()
    }
    /// Why a solve failed or turned over: the constraints whose orientation the edit flips,
    /// or else `conflict` of the constraints still violated (listed, comma-separated).
    pub fn failure(&self, conflict: impl FnOnce(&str) -> String) -> String {
        if let Some(n) = self.oversized {
            return format!(
                "the sketch joins {n} unknowns (point coordinates and radii) in one connected group, more than the {MAX_COMPONENT_VARS} the solver takes at once; a pattern joins all its copies: make fewer copies, or split them over several patterns or sketches"
            );
        }
        if self.folded.is_empty() {
            conflict(&self.failing.join(", "))
        } else {
            format!("the new values would flip the sketch over ({} would change orientation)", self.folded.join(", "))
        }
    }
}

/// Variable layout: point → (x var, y var), circle → radius var. The point coordinates come
/// first, in pairs (variables `0..points`), then the radii.
struct Layout {
    pvar: Vec<Option<usize>>,
    rvar: Vec<Option<usize>>,
    n: usize,
    /// The point coordinates' variables: `0..points`.
    points: usize,
    /// Per variable: a coordinate of a point held on a curve (point on curve, midpoint), which
    /// a solve slides along it before moving the curve (see [`SLIDE_WEIGHT`]).
    slide: Vec<bool>,
}

impl Layout {
    /// The variable is a point coordinate.
    fn is_point(&self, v: usize) -> bool {
        v < self.points
    }
    /// The first variable of the unknown `v` belongs to: its point's x, or the radius itself.
    fn unit(&self, v: usize) -> usize {
        if self.is_point(v) { v & !1 } else { v }
    }
    /// The variables of the unknown starting at `first`.
    fn width(&self, first: usize) -> usize {
        if self.is_point(first) { 2 } else { 1 }
    }
}

/// Geometry held in place for one solve: point indices and curves whose radius is held.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Hold {
    pub points: Vec<usize>,
    pub radii: Vec<usize>,
}

/// Per point: a constant for this solve (locked — fixed, fixed by a constraint, a point of a
/// fixed curve, linked — or held).
pub(crate) fn held_points(sk: &Sketch, hold: &Hold) -> Vec<bool> {
    let mut fixed = sk.locked_points();
    for p in &hold.points {
        if let Some(f) = fixed.get_mut(*p) {
            *f = true;
        }
    }
    fixed
}

fn layout(sk: &Sketch, hold: &Hold) -> Layout {
    let mut n = 0;
    let pvar: Vec<Option<usize>> = held_points(sk, hold)
        .iter()
        .map(|f| {
            if *f {
                None
            } else {
                n += 2;
                Some(n - 2)
            }
        })
        .collect();
    let points = n;
    let rvar = sk
        .curves
        .iter()
        .enumerate()
        .map(|(i, c)| match c.kind {
            CurveKind::Circle { .. } | CurveKind::Ellipse { .. }
                if c.link.is_none() && !c.fixed && !hold.radii.contains(&i) && !sk.offset_circle_follows_source(i) =>
            {
                n += 1;
                Some(n - 1)
            }
            _ => None,
        })
        .collect();
    let mut slide = vec![false; n];
    for c in &sk.constraints {
        if let ConstraintKind::PointOnCurve { p, .. } | ConstraintKind::PointAlong { p, .. } | ConstraintKind::Midpoint { p, .. } = c.kind
            && let Some(Some(v)) = pvar.get(p)
        {
            for k in [*v, *v + 1] {
                if let Some(s) = slide.get_mut(k) {
                    *s = true;
                }
            }
        }
    }
    Layout { pvar, rvar, n, points, slide }
}

/// Read-only view of the sketch with variable values substituted.
struct State<'a> {
    sk: &'a Sketch,
    lay: &'a Layout,
    x: &'a [f64],
}

impl State<'_> {
    fn p(&self, i: usize) -> Vec2 {
        match self.lay.pvar.get(i).copied().flatten() {
            Some(v) => Vec2::new(self.x.get(v).copied().unwrap_or(0.0), self.x.get(v + 1).copied().unwrap_or(0.0)),
            None => self.sk.points.get(i).map(|p| p.pos).unwrap_or_default(),
        }
    }
    fn line(&self, l: usize) -> (Vec2, Vec2) {
        match self.sk.curves.get(l).map(|c| &c.kind) {
            Some(CurveKind::Line { a, b }) => (self.p(*a), self.p(*b)),
            _ => (Vec2::ZERO, Vec2::X),
        }
    }
    /// Centre and radius of a circle or arc.
    fn round(&self, c: usize) -> (Vec2, f64) {
        match self.sk.curves.get(c).map(|c| &c.kind) {
            Some(CurveKind::Circle { c: ci, r }) => {
                let r = match self.lay.rvar.get(c).copied().flatten() {
                    Some(v) => self.x.get(v).copied().unwrap_or(*r),
                    None => *r,
                };
                (self.p(*ci), r)
            }
            Some(CurveKind::Arc { c: ci, a, .. }) => {
                let cc = self.p(*ci);
                (cc, cc.dist(self.p(*a)))
            }
            _ => (Vec2::ZERO, 0.0),
        }
    }
    fn is_line(&self, c: usize) -> bool {
        matches!(self.sk.curves.get(c).map(|c| &c.kind), Some(CurveKind::Line { .. }))
    }
    fn is_freeform(&self, c: usize) -> bool {
        self.sk.curves.get(c).is_some_and(|c| c.kind.is_freeform())
    }
    /// Polyline of a free-form curve with trial values.
    fn poly(&self, c: usize) -> Vec<Vec2> {
        match self.sk.curves.get(c).map(|c| &c.kind) {
            Some(CurveKind::Ellipse { c: ci, m, r }) => {
                let r = match self.lay.rvar.get(c).copied().flatten() {
                    Some(v) => self.x.get(v).copied().unwrap_or(*r),
                    None => *r,
                };
                crate::curves::ellipse_polyline(self.p(*ci), self.p(*m), r)
            }
            Some(CurveKind::Spline { pts, control, degree, periodic, nurbs }) => {
                let p = self.spline_points(pts, *periodic);
                crate::curves::spline_polyline_mode(&p, *control, *degree, *periodic, nurbs.as_ref())
            }
            Some(CurveKind::Conic { a, b, apex, rho }) => crate::curves::conic_polyline(self.p(*a), self.p(*apex), self.p(*b), *rho),
            _ => Vec::new(),
        }
    }
    /// Point-on-curve constraints use the exact shape. A polyline residual would move an
    /// exact crossing onto its chord, changing geometry merely by splitting it.
    fn spline_points(&self, pts: &[usize], periodic: bool) -> Vec<Vec2> {
        let mut points: Vec<Vec2> = pts.iter().map(|i| self.p(*i)).collect();
        if periodic
            && let Some(first) = points.first().copied()
            && let Some(last) = points.last_mut()
        {
            *last = first;
        }
        points
    }
    fn freeform_dist(&self, c: usize, q: Vec2) -> f64 {
        let segs: Vec<Seg2> = match self.sk.curves.get(c).map(|c| &c.kind) {
            Some(CurveKind::Ellipse { c: ci, m, .. }) => {
                let center = self.p(*ci);
                let u = self.p(*m) - center;
                let a = u.len();
                let r = self.radius_of(c);
                if a <= 1e-12 || r <= 1e-12 {
                    return q.dist(center);
                }
                let delta = q - center;
                let x = delta.dot(u) / (a * a);
                let y = delta.cross(u) / (a * r);
                return (x.hypot(y) - 1.0) * a.min(r);
            }
            Some(CurveKind::Spline { pts, periodic, .. }) => {
                let p = self.spline_points(pts, *periodic);
                if p.len() < 2 {
                    return q.dist(p.first().copied().unwrap_or_default());
                }
                self.segs(c)
            }
            Some(CurveKind::Conic { .. }) => self.segs(c),
            _ => Vec::new(),
        };
        segs.iter()
            .map(|seg| {
                let t = seg.closest_param(q);
                let delta = q - seg.point_at(t);
                let d = delta.len();
                (d, if seg.derivative(t).cross(delta) >= 0.0 { d } else { -d })
            })
            .min_by(|a, b| a.0.total_cmp(&b.0))
            .map(|(_, signed)| signed)
            .unwrap_or_else(|| crate::curves::polyline_signed_dist(&self.poly(c), q))
    }
    /// The exact pieces of any curve with trial values, from its start: a circle from sketch +X
    /// and an ellipse from its major-axis end, both counter-clockwise, an ellipse as four exact
    /// conic quarters.
    fn segs(&self, c: usize) -> Vec<Seg2> {
        match self.sk.curves.get(c).map(|c| &c.kind) {
            Some(CurveKind::Line { a, b }) => vec![Seg2::Line { a: self.p(*a), b: self.p(*b) }],
            Some(CurveKind::Circle { .. }) => {
                let (center, radius) = self.round(c);
                vec![Seg2::Arc { center, radius, start: 0.0, sweep: std::f64::consts::TAU }]
            }
            Some(CurveKind::Arc { c: ci, a, .. }) => {
                let (center, radius) = self.round(c);
                let start = (self.p(*a) - self.p(*ci)).angle();
                let mut sweep = self.arc_sweep(c).abs();
                if sweep <= 1e-12 {
                    sweep = std::f64::consts::TAU;
                }
                vec![Seg2::Arc { center, radius, start, sweep }]
            }
            Some(CurveKind::Ellipse { c: ci, m, .. }) => {
                let center = self.p(*ci);
                let u = self.p(*m) - center;
                let v = u.perp().normalized().unwrap_or(Vec2::ZERO) * self.radius_of(c);
                let corner = [u, v, -u, -v, u];
                corner
                    .windows(2)
                    .filter_map(|w| match w {
                        [x, y] => Some(Seg2::Conic { a: center + *x, apex: center + *x + *y, b: center + *y, w: std::f64::consts::FRAC_1_SQRT_2 }),
                        _ => None,
                    })
                    .collect()
            }
            Some(CurveKind::Spline { pts, control, degree, periodic, nurbs }) => {
                let p = self.spline_points(pts, *periodic);
                if p.len() < 2 {
                    return Vec::new();
                }
                if let Some(nurbs) = nurbs {
                    nurbs.segs(&p, *degree).unwrap_or_default()
                } else if *control {
                    let k = (*degree as usize).min(solidcore_record::MAX_BEZIER_DEGREE).min(p.len().saturating_sub(1)).max(1);
                    crate::curves::bspline_beziers(&p, k).iter().filter_map(|span| solidcraft_geom::bezier(span)).collect()
                } else {
                    crate::curves::fit_beziers_mode(&p, *periodic)
                        .unwrap_or_default()
                        .into_iter()
                        .map(|[p0, p1, p2, p3]| Seg2::Cubic { p0, p1, p2, p3 })
                        .collect()
                }
            }
            Some(CurveKind::Conic { a, b, apex, rho }) => {
                vec![Seg2::Conic { a: self.p(*a), b: self.p(*b), apex: self.p(*apex), w: rho / (1.0 - rho).max(1e-9) }]
            }
            None => Vec::new(),
        }
    }
    /// Where a point at share `at` of curve `c`'s length lies, with trial values.
    fn along(&self, c: usize, at: f64) -> Vec2 {
        crate::curves::point_along(&self.segs(c), at).unwrap_or_default()
    }
    /// Radius of a circle or arc; an ellipse's minor radius.
    fn radius_of(&self, c: usize) -> f64 {
        match self.sk.curves.get(c).map(|x| &x.kind) {
            Some(CurveKind::Ellipse { r, .. }) => match self.lay.rvar.get(c).copied().flatten() {
                Some(v) => self.x.get(v).copied().unwrap_or(*r),
                None => *r,
            },
            _ => self.round(c).1,
        }
    }
    fn ends(&self, c: usize) -> Option<(usize, usize)> {
        self.sk.curves.get(c)?.kind.ends()
    }
    /// Length along an arc (counter-clockwise from its start).
    fn arc_length(&self, c: usize) -> f64 {
        match self.sk.curves.get(c).map(|c| &c.kind) {
            Some(CurveKind::Arc { c: ci, a, b }) => {
                let (cc, pa, pb) = (self.p(*ci), self.p(*a), self.p(*b));
                let mut sw = (pb - cc).angle() - (pa - cc).angle();
                while sw <= 1e-12 {
                    sw += std::f64::consts::TAU;
                }
                cc.dist(pa) * sw
            }
            _ => 0.0,
        }
    }
    fn arc_sweep(&self, c: usize) -> f64 {
        let Some(curve) = self.sk.curves.get(c) else { return 0.0 };
        let CurveKind::Arc { c: cp, a, b } = curve.kind else { return 0.0 };
        let sweep = ((self.p(b) - self.p(cp)).angle() - (self.p(a) - self.p(cp)).angle()).rem_euclid(std::f64::consts::TAU);
        if curve.reversed { -sweep } else { sweep }
    }
    /// What a line-to-circle distance measures: the gap from line `l` to the edge of circle or
    /// arc `c`, or (`inside`) how far the edge reaches past the line.
    fn line_circle_gap(&self, l: usize, c: usize, inside: bool) -> f64 {
        let (a, b) = self.line(l);
        let (cc, r) = self.round(c);
        let d = line_dist(cc, a, b).abs();
        if inside { r - d } else { d - r }
    }
    /// What a point-to-circle distance measures: the gap from point `p` to the edge of circle
    /// or arc `c`, or (`inside`) how far within the edge the point lies.
    fn point_circle_gap(&self, p: usize, c: usize, inside: bool) -> f64 {
        let (cc, r) = self.round(c);
        let d = self.p(p).dist(cc);
        if inside { r - d } else { d - r }
    }
    /// What a distance between two circles or arcs measures, as they lie (`circles`).
    fn circle_circle_gap(&self, a: usize, b: usize, circles: TwoCircles) -> f64 {
        let (ca, ra) = self.round(a);
        let (cb, rb) = self.round(b);
        circles.gap(ca.dist(cb), ra, rb)
    }
    fn slot_length(&self, a: usize, b: usize) -> f64 {
        let (ca, ra) = self.round(a);
        let (cb, rb) = self.round(b);
        ca.dist(cb) + ra + rb
    }
    /// Curvature vector of a curve at its point `p` (towards the centre of curvature).
    fn curvature_at(&self, c: usize, p: usize) -> Vec2 {
        let Some(kind) = self.sk.curves.get(c).map(|c| &c.kind) else { return Vec2::ZERO };
        match kind {
            CurveKind::Line { .. } | CurveKind::Ellipse { .. } => Vec2::ZERO,
            CurveKind::Circle { .. } | CurveKind::Arc { .. } => {
                let (cc, r) = self.round(c);
                (cc - self.p(p)) / (r * r).max(1e-24)
            }
            CurveKind::Spline { pts, control, degree, periodic, nurbs } => {
                let q = self.spline_points(pts, *periodic);
                let at_end = pts.last() == Some(&p) && pts.first() != Some(&p);
                crate::curves::end_curvature(&|t| crate::curves::spline_point_mode(&q, *control, *degree, *periodic, nurbs.as_ref(), t), at_end)
            }
            CurveKind::Conic { a, b, apex, rho } => {
                let (pa, pb, px) = (self.p(*a), self.p(*b), self.p(*apex));
                crate::curves::end_curvature(&|t| crate::curves::conic_point(pa, px, pb, *rho, t), p == *b)
            }
        }
    }
    /// Unit tangent of any curve at its point `p` (an end point for open free-form curves).
    fn tangent_at(&self, c: usize, p: usize) -> Option<Vec2> {
        match self.sk.curves.get(c).map(|c| &c.kind)? {
            CurveKind::Line { a, b } => (self.p(*b) - self.p(*a)).normalized(),
            CurveKind::Circle { .. } | CurveKind::Arc { .. } => (self.p(p) - self.round(c).0).perp().normalized(),
            CurveKind::Spline { pts, control, periodic, .. } => {
                let q = self.spline_points(pts, *periodic);
                crate::curves::spline_end_tangent_mode(&q, *control, *periodic, pts.last() == Some(&p) && pts.first() != Some(&p))
            }
            CurveKind::Conic { a, b, apex, .. } => {
                if p == *a {
                    (self.p(*apex) - self.p(*a)).normalized()
                } else if p == *b {
                    (self.p(*b) - self.p(*apex)).normalized()
                } else {
                    None
                }
            }
            CurveKind::Ellipse { .. } => {
                let poly = self.poly(c);
                let q = self.p(p);
                let k = (0..poly.len().saturating_sub(1)).min_by(|i, j| poly[*i].dist(q).total_cmp(&poly[*j].dist(q)))?;
                (*poly.get(k + 1)? - *poly.get(k)?).normalized()
            }
        }
    }
}

fn wrap_angle(a: f64) -> f64 {
    let t = std::f64::consts::TAU;
    let mut a = a % t;
    if a > std::f64::consts::PI {
        a -= t;
    } else if a <= -std::f64::consts::PI {
        a += t;
    }
    a
}

/// Put every pierced point where the curve of the other sketch crosses this sketch's plane
/// (#3599). The point is held there (it is locked), so the solve keeps it: the crossing is a
/// fact about the two sketches, not something the iteration works out.
fn place_pierced_points(sk: &mut Sketch) {
    let places: Vec<(usize, Vec2)> = sk
        .constraints
        .iter()
        .filter_map(|c| match &c.kind {
            ConstraintKind::Pierce { p, plane, world, .. } => crate::pierce::pierce_point_world(plane, world).map(|at| (*p, at)),
            _ => None,
        })
        .collect();
    for (p, at) in places {
        if let Some(point) = sk.points.get_mut(p) {
            point.pos = at;
        }
    }
}

/// Distance from `p` to the infinite line through `a`, `b` (signed by side).
/// What a tangent to a free-form curve has to bring to zero, from the signed gaps of the curve's
/// samples to the other curve (`closed`: the samples run round): the extremum of the gap nearest
/// zero, refined between the samples by the parabola through its neighbours. Curves that cross
/// have a zero gap too, but no extremum there, so a crossing is not taken for a touch (#11535).
/// An open curve's ends count as extrema too: a touch at its end, or a monotone gap (an open
/// curve running away from the other), takes the gap nearest zero.
fn touch_gap(gaps: &[f64], closed: bool) -> f64 {
    let n = gaps.len();
    let at = |i: usize, back: bool| -> Option<f64> {
        let j = match (back, closed) {
            (true, true) => (i + n - 1) % n,
            (false, true) => (i + 1) % n,
            (true, false) => i.checked_sub(1)?,
            (false, false) => i + 1,
        };
        gaps.get(j).copied()
    };
    let mut best: Option<f64> = None;
    for (i, &g) in gaps.iter().enumerate() {
        let (Some(p), Some(q)) = (at(i, true), at(i, false)) else { continue };
        if !((g >= p && g >= q) || (g <= p && g <= q)) {
            continue;
        }
        let bend = p - 2.0 * g + q;
        let v = if bend.abs() > 1e-15 { g - (q - p) * (q - p) / (8.0 * bend) } else { g };
        let v = if v.is_finite() { v } else { g };
        if best.is_none_or(|b| v.abs() < b.abs()) {
            best = Some(v);
        }
    }
    // An open curve's ends are extrema of its gap too (a touch at its end, or a gap that is
    // monotone and has no other extremum).
    if !closed && let (Some(&first), Some(&last)) = (gaps.first(), gaps.last()) {
        for end in [first, last] {
            if best.is_none_or(|b| end.abs() < b.abs()) {
                best = Some(end);
            }
        }
    }
    best.unwrap_or(0.0)
}

fn line_dist(p: Vec2, a: Vec2, b: Vec2) -> f64 {
    let d = b - a;
    let l = d.len().max(1e-12);
    d.cross(p - a) / l
}

/// Residual rows of one constraint.
fn residuals(s: &State, k: &ConstraintKind, out: &mut Vec<f64>) {
    use ConstraintKind::*;
    match *k {
        PatternPoint { p, q, center, angle, mut offset, directions } => {
            for (l, distance) in directions.into_iter().flatten() {
                let (a, b) = s.line(l);
                let u = (b - a).normalized().unwrap_or(Vec2::ZERO);
                offset += u * distance.x + u.perp() * distance.y;
            }
            let c = center.map(|c| s.p(c)).unwrap_or(Vec2::ZERO);
            let d = s.p(p) - c;
            let (sin, cos) = angle.sin_cos();
            let delta = s.p(q) - c - Vec2::new(d.x * cos - d.y * sin, d.x * sin + d.y * cos) - offset;
            out.extend([delta.x, delta.y]);
        }
        PatternRadius { a, b } => out.push(s.radius_of(a) - s.radius_of(b)),
        // Offset distances drive derived geometry in refresh_offsets, never source DOFs.
        OffsetDistance { .. } => {}
        Coincident { p, q } => {
            let d = s.p(p) - s.p(q);
            out.extend([d.x, d.y]);
        }
        PointAlong { p, c, at } => {
            let d = s.p(p) - s.along(c, at);
            out.extend([d.x, d.y]);
        }
        PointOnCurve { p, c } => {
            let pp = s.p(p);
            if s.is_freeform(c) {
                out.push(s.freeform_dist(c, pp));
            } else if s.is_line(c) {
                let (a, b) = s.line(c);
                out.push(line_dist(pp, a, b));
            } else {
                let (cc, r) = s.round(c);
                out.push(pp.dist(cc) - r);
            }
        }
        Horizontal { l } => {
            let (a, b) = s.line(l);
            let scale = if s.sk.curves.get(l).is_some_and(|c| c.infinite) { (b - a).len().max(1e-12) } else { 1.0 };
            // An infinite line's defining points may be very close together. Its visible
            // direction must remain horizontal even when their separation is below the
            // distance tolerance, so measure direction rather than endpoint distance.
            out.push((b.y - a.y) / scale);
        }
        Vertical { l } => {
            let (a, b) = s.line(l);
            let scale = if s.sk.curves.get(l).is_some_and(|c| c.infinite) { (b - a).len().max(1e-12) } else { 1.0 };
            out.push((b.x - a.x) / scale);
        }
        HorizontalPoints { p, q } => out.push(s.p(q).y - s.p(p).y),
        VerticalPoints { p, q } => out.push(s.p(q).x - s.p(p).x),
        Parallel { a, b } | Perpendicular { a, b } => {
            let (a0, a1) = s.line(a);
            let (b0, b1) = s.line(b);
            let (da, db) = (a1 - a0, b1 - b0);
            // The sine (parallel) or cosine (perpendicular) of the angle between the lines:
            // independent of their lengths, so the solver can't satisfy it by shrinking a line
            // to nothing (scaling by the summed lengths did, collapsing dragged rectangles).
            let scale = (da.len() * db.len()).max(1e-12);
            let v = if matches!(k, Parallel { .. }) { da.cross(db) } else { da.dot(db) };
            out.push(v / scale);
        }
        Collinear { a, b } => {
            let (a0, a1) = s.line(a);
            let (b0, b1) = s.line(b);
            out.push(line_dist(b0, a0, a1));
            out.push(line_dist(b1, a0, a1));
        }
        Tangent { a, b } => {
            let (la, lb) = (s.is_line(a), s.is_line(b));
            if s.is_freeform(a) || s.is_freeform(b) {
                // Without a shared end point: the curves touch (an extremum of the gap is zero).
                let (f, o) = if s.is_freeform(a) { (a, b) } else { (b, a) };
                let mut poly = s.poly(f);
                // A closed curve's polyline ends where it starts: its samples run round.
                let closed = poly.len() > 2 && poly.first().zip(poly.last()).is_some_and(|(p, q)| p.dist(*q) < 1e-9);
                if closed {
                    poly.pop();
                }
                // Signed gaps (smooth through zero, unlike their sizes).
                let gaps: Vec<f64> = if s.is_line(o) {
                    let (p0, p1) = s.line(o);
                    poly.iter().map(|q| line_dist(*q, p0, p1)).collect()
                } else if s.is_freeform(o) {
                    let other = s.poly(o);
                    poly.iter().map(|q| crate::curves::polyline_signed_dist(&other, *q)).collect()
                } else {
                    let (cc, r) = s.round(o);
                    poly.iter().map(|q| q.dist(cc) - r).collect()
                };
                let d = touch_gap(&gaps, closed);
                out.push(if d.is_finite() { d } else { 0.0 });
            } else if la || lb {
                let (l, c) = if la { (a, b) } else { (b, a) };
                let (p0, p1) = s.line(l);
                let (cc, r) = s.round(c);
                out.push(line_dist(cc, p0, p1).abs() - r);
            } else {
                let (c1, r1) = s.round(a);
                let (c2, r2) = s.round(b);
                let d = c1.dist(c2);
                let ext = d - (r1 + r2);
                let int = d - (r1 - r2).abs();
                out.push(if ext.abs() <= int.abs() { ext } else { int });
            }
        }
        Equal { a, b } => {
            if s.is_line(a) {
                let (a0, a1) = s.line(a);
                let (b0, b1) = s.line(b);
                out.push(a0.dist(a1) - b0.dist(b1));
            } else {
                out.push(s.round(a).1 - s.round(b).1);
            }
        }
        Concentric { a, b } => {
            let d = s.round(a).0 - s.round(b).0;
            out.extend([d.x, d.y]);
        }
        Midpoint { p, l } => {
            let (a, b) = s.line(l);
            let d = s.p(p) - (a + b) * 0.5;
            out.extend([d.x, d.y]);
        }
        Symmetric { p, q, l } => {
            let (a, b) = s.line(l);
            let (pp, qq) = (s.p(p), s.p(q));
            let dir = b - a;
            let len = dir.len().max(1e-12);
            out.push(line_dist((pp + qq) * 0.5, a, b));
            out.push((qq - pp).dot(dir) / len);
        }
        Fix { .. } => {}
        // A pierce holds its point where the other sketch's curve crosses this sketch's
        // plane: the point is placed there before the solve and kept there (it is
        // locked), so the constraint adds no rows of its own.
        Pierce { .. } => {}
        // A distance within convergence tolerance of zero means coincidence: two
        // component rows keep both directions constrained even when the points meet.
        Distance { p, q, value } if value.abs() <= TOL => {
            let d = s.p(p) - s.p(q);
            out.extend([d.x, d.y]);
        }
        Distance { p, q, value } => out.push(s.p(p).dist(s.p(q)) - value),
        // At zero the signed component has the same solutions as its magnitude, but keeps
        // a nonzero derivative when the points line up for freedom and redundancy analysis.
        DistanceX { p, q, value: 0.0 } => out.push(s.p(q).x - s.p(p).x),
        DistanceY { p, q, value: 0.0 } => out.push(s.p(q).y - s.p(p).y),
        DistanceX { p, q, value } => out.push((s.p(q).x - s.p(p).x).abs() - value),
        DistanceY { p, q, value } => out.push((s.p(q).y - s.p(p).y).abs() - value),
        PointLineDistance { p, l, value } => {
            let (a, b) = s.line(l);
            let d = line_dist(s.p(p), a, b);
            // At zero this is point-on-line; the signed distance retains its slope.
            out.push(if value.abs() <= TOL { d } else { d.abs() - value });
        }
        LineCircleDistance { l, c, value, inside } => out.push(s.line_circle_gap(l, c, inside) - value),
        PointCircleDistance { p, c, value, inside } => out.push(s.point_circle_gap(p, c, inside) - value),
        CircleCircleDistance { a, b, value, circles } => out.push(s.circle_circle_gap(a, b, circles) - value),
        // A length within convergence tolerance of zero means the line's two ends meet:
        // the component rows keep both directions constrained even when they do, the way a
        // coincidence does (the same treatment a distance of zero gets above).
        Length { l, value } if value.abs() <= TOL => {
            let (a, b) = s.line(l);
            out.extend([b.x - a.x, b.y - a.y]);
        }
        Length { l, value } => {
            let (a, b) = s.line(l);
            out.push(a.dist(b) - value);
        }
        LineAngle { l, value } => {
            let (a, b) = s.line(l);
            // A dimension with no typed length must not satisfy its angle by collapsing
            // the line. Scale with the original geometry, independently of the unknowns.
            let scale = match s.sk.curves.get(l).map(|c| &c.kind) {
                Some(CurveKind::Line { a, b }) => s.sk.point(*a).zip(s.sk.point(*b)).map(|(a, b)| a.dist(b)).unwrap_or(1.0),
                _ => 1.0,
            };
            out.push(wrap_angle((b - a).angle() - value) * scale.max(1.0));
        }
        ArcSweep { c, value } => out.push((s.arc_sweep(c) - value) * s.sk.radius(c).unwrap_or(1.0).max(1.0)),
        SlotOverallLength { a, b, value } => out.push(s.slot_length(a, b) - value),
        Radius { c, value } => out.push(s.radius_of(c) - value),
        Diameter { c, value } => out.push(2.0 * s.round(c).1 - value),
        Angle { a, b, value, flip } => {
            let (a0, a1) = s.line(a);
            let (b0, b1) = s.line(b);
            let (da, db) = (a1 - a0, b1 - b0);
            let ang = da.cross(db).atan2(da.dot(db));
            let scale = 0.5 * (da.len() + db.len());
            let target = if flip { value + std::f64::consts::PI } else { value };
            out.push(wrap_angle(ang - target) * scale.max(1e-6));
        }
        Smooth { a, b } => {
            let shared = match (s.ends(a), s.ends(b)) {
                (Some((a0, a1)), Some((b0, b1))) => [a0, a1].into_iter().find(|x| *x == b0 || *x == b1),
                _ => None,
            };
            let Some(p) = shared else {
                out.extend([0.0, 0.0, 0.0]);
                return;
            };
            match (s.tangent_at(a, p), s.tangent_at(b, p)) {
                (Some(u), Some(v)) => out.push(u.cross(v) * 10.0),
                _ => out.push(0.0),
            }
            let k = s.curvature_at(a, p) - s.curvature_at(b, p);
            out.extend([k.x * 100.0, k.y * 100.0]);
        }
        ArcLength { c, value } => out.push(s.arc_length(c) - value),
        LinearDiameter { p, l, value } => {
            let (a, b) = s.line(l);
            out.push(2.0 * line_dist(s.p(p), a, b).abs() - value);
        }
    }
}

/// Measured value of a dimension (for driven dimensions).
fn measure(s: &State, k: &ConstraintKind) -> Option<f64> {
    use ConstraintKind::*;
    Some(match *k {
        Distance { p, q, .. } => s.p(p).dist(s.p(q)),
        DistanceX { p, q, .. } => (s.p(q).x - s.p(p).x).abs(),
        DistanceY { p, q, .. } => (s.p(q).y - s.p(p).y).abs(),
        PointLineDistance { p, l, .. } => {
            let (a, b) = s.line(l);
            line_dist(s.p(p), a, b).abs()
        }
        LineCircleDistance { l, c, inside, .. } => s.line_circle_gap(l, c, inside),
        PointCircleDistance { p, c, inside, .. } => s.point_circle_gap(p, c, inside),
        CircleCircleDistance { a, b, circles, .. } => s.circle_circle_gap(a, b, circles),
        Length { l, .. } => {
            let (a, b) = s.line(l);
            a.dist(b)
        }
        LineAngle { l, value } => {
            let (a, b) = s.line(l);
            value + wrap_angle((b - a).angle() - value)
        }
        ArcSweep { c, .. } => s.arc_sweep(c),
        SlotOverallLength { a, b, .. } => s.slot_length(a, b),
        Radius { c, .. } => s.radius_of(c),
        Diameter { c, .. } => 2.0 * s.round(c).1,
        Angle { a, b, flip, .. } => {
            let (a0, a1) = s.line(a);
            let (b0, b1) = s.line(b);
            let (da, db) = (a1 - a0, b1 - b0);
            let ang = da.cross(db).atan2(da.dot(db)) - if flip { std::f64::consts::PI } else { 0.0 };
            ang.rem_euclid(std::f64::consts::TAU)
        }
        ArcLength { c, .. } => s.arc_length(c),
        LinearDiameter { p, l, .. } => {
            let (a, b) = s.line(l);
            2.0 * line_dist(s.p(p), a, b).abs()
        }
        _ => return None,
    })
}

/// What a dimension measures on the sketch as it stands (mm, radians for angles); `None` for a
/// constraint that is not a dimension.
pub fn measure_dimension(sk: &Sketch, k: &ConstraintKind) -> Option<f64> {
    let lay = Layout { pvar: vec![None; sk.points.len()], rvar: vec![None; sk.curves.len()], n: 0, points: 0, slide: Vec::new() };
    measure(&State { sk, lay: &lay, x: &[] }, k).filter(|v| v.is_finite())
}

/// Where the point at share `at` (0 to 1) of curve `c`'s length lies on the sketch as it stands,
/// measured from the curve's start as [`ConstraintKind::PointAlong`] measures it; `None` for an
/// unknown curve, a share out of range or a curve with no length to share.
pub fn point_along(sk: &Sketch, c: usize, at: f64) -> Option<Vec2> {
    if !(at.is_finite() && (0.0..=1.0).contains(&at)) {
        return None;
    }
    let lay = Layout { pvar: vec![None; sk.points.len()], rvar: vec![None; sk.curves.len()], n: 0, points: 0, slide: Vec::new() };
    crate::curves::point_along(&State { sk, lay: &lay, x: &[] }.segs(c), at).filter(|p| p.x.is_finite() && p.y.is_finite())
}

/// One residual block: implicit arc radius equality, a user constraint, or a tangency at a known
/// touch point (better conditioned than the distance form when an end point is on the curve).
enum Block<'a> {
    Closure { a: usize, b: usize },
    Arc { c: usize, a: usize, b: usize },
    User(usize, &'a ConstraintKind),
    TangentAt(usize, &'a ConstraintKind, usize),
}

fn copy_block<'a>(b: &Block<'a>) -> Block<'a> {
    match b {
        Block::Closure { a, b } => Block::Closure { a: *a, b: *b },
        Block::Arc { c, a, b } => Block::Arc { c: *c, a: *a, b: *b },
        Block::User(i, k) => Block::User(*i, k),
        Block::TangentAt(i, k, p) => Block::TangentAt(*i, k, *p),
    }
}

fn block_residuals(s: &State, b: &Block, out: &mut Vec<f64>) {
    #[cfg(feature = "solver-profiling")]
    profiling::count(|c| c.residual_block_evaluations = c.residual_block_evaluations.saturating_add(1));
    match b {
        Block::Closure { a, b } => {
            let d = s.p(*a) - s.p(*b);
            out.extend([d.x, d.y]);
        }
        Block::Arc { c, a, b } => {
            let cc = s.p(*c);
            out.push(cc.dist(s.p(*b)) - cc.dist(s.p(*a)));
        }
        Block::User(_, k) => residuals(s, k, out),
        Block::TangentAt(_, k, p) => {
            let ConstraintKind::Tangent { a, b } = **k else { return };
            let pt = s.p(*p);
            if s.is_freeform(a) || s.is_freeform(b) {
                // Directions at the shared end parallel.
                match (s.tangent_at(a, *p), s.tangent_at(b, *p)) {
                    (Some(u), Some(v)) => out.push(u.cross(v) * 10.0),
                    _ => out.push(0.0),
                }
            } else if s.is_line(a) || s.is_line(b) {
                let (l, c) = if s.is_line(a) { (a, b) } else { (b, a) };
                let (p0, p1) = s.line(l);
                let (cc, _) = s.round(c);
                let d = p1 - p0;
                // The radius to the touch point is perpendicular to the line.
                out.push((pt - cc).dot(d) / d.len().max(1e-12));
            } else {
                let (c1, _) = s.round(a);
                let (c2, _) = s.round(b);
                let (u, v) = (pt - c1, pt - c2);
                // Both centres on one line through the touch point.
                out.push(u.cross(v) / (u.len() + v.len()).max(1e-12));
            }
        }
    }
}

/// Every (point, curve) pair of a point-on-curve constraint, sorted (for [`touch_point`]).
pub(crate) fn points_on_curves(sk: &Sketch) -> Vec<(usize, usize)> {
    let mut on: Vec<(usize, usize)> = sk
        .constraints
        .iter()
        .filter_map(|c| match c.kind {
            ConstraintKind::PointOnCurve { p, c } => Some((p, c)),
            _ => None,
        })
        .collect();
    on.sort_unstable();
    on
}

/// A point where a tangency must happen: an end point shared by the two curves, or a line end
/// point constrained onto the round curve (`on_curve` from [`points_on_curves`]).
pub(crate) fn touch_point(sk: &Sketch, k: &ConstraintKind, on_curve: &[(usize, usize)]) -> Option<usize> {
    let ConstraintKind::Tangent { a, b } = *k else { return None };
    let ends = |c: usize| -> Vec<usize> {
        match sk.curves.get(c).map(|c| &c.kind) {
            Some(k) => k.ends().map(|(a, b)| vec![a, b]).unwrap_or_default(),
            None => Vec::new(),
        }
    };
    let (ea, eb) = (ends(a), ends(b));
    if let Some(p) = ea.iter().find(|p| eb.contains(p)) {
        return Some(*p);
    }
    let on = |p: usize, c: usize| on_curve.binary_search(&(p, c)).is_ok();
    if let Some(p) = ea.iter().find(|p| on(**p, b)).or_else(|| eb.iter().find(|p| on(**p, a))) {
        return Some(*p);
    }
    contact_through_coincident(sk, a, b, &ea, &eb, on_curve)
}

/// Whether curve `c` is a straight line.
fn is_straight(sk: &Sketch, c: usize) -> bool {
    matches!(sk.curves.get(c).map(|c| &c.kind), Some(CurveKind::Line { .. }))
}

/// A touch point the two curves reach through `Coincident` constraints, when they share no point
/// and no end of one is a point-on-curve of the other: a point lying on `a` (an end of it, or a
/// point-on-curve of it) tied by a chain of `Coincident` constraints to a point lying on `b`
/// (the chain may be empty: a free point on both curves). That covers two ends tied together, a
/// line end tied to a free point that is on the circle, and a free point on both curves.
/// Free-form curves count only their ends. Without this the tangency falls back to the
/// touch-free form (distance from the centre equals the radius), whose Jacobian is
/// rank-deficient at the solution: the touch point is a double root of it, so it converges to
/// only sqrt(residual) of tangent and drops rank (see the `coincident_tangent_*` tests). The
/// point returned is the one lying on the round curve (for a free-form curve, its end), so the
/// radius to it is read from the curve it belongs to.
fn contact_through_coincident(sk: &Sketch, a: usize, b: usize, ea: &[usize], eb: &[usize], on_curve: &[(usize, usize)]) -> Option<usize> {
    let n = sk.points.len();
    let free = |c: usize| sk.curves.get(c).is_some_and(|c| c.kind.is_freeform());
    // Points lying on a curve: its ends, and (unless free-form) the points constrained onto it.
    let lying = |c: usize, ends: &[usize]| -> Vec<usize> {
        let mut v: Vec<usize> = ends.to_vec();
        if !free(c) {
            v.extend(on_curve.iter().filter(|(_, cc)| *cc == c).map(|(p, _)| *p));
            // The midpoint of a line lies on it.
            v.extend(sk.constraints.iter().filter(|k| !k.driven).filter_map(|k| match k.kind {
                ConstraintKind::Midpoint { p, l } if l == c => Some(p),
                _ => None,
            }));
        }
        v.retain(|p| *p < n);
        v
    };
    let (on_a, on_b) = (lying(a, ea), lying(b, eb));
    if on_a.is_empty() || on_b.is_empty() {
        return None;
    }
    let mut parent: Vec<usize> = (0..n).collect();
    for c in sk.constraints.iter().filter(|c| !c.driven) {
        if let ConstraintKind::Coincident { p, q } = c.kind
            && p != q
            && p < n
            && q < n
        {
            union(&mut parent, p, q);
        }
    }
    for &p in &on_a {
        let root = find(&mut parent, p);
        if let Some(&q) = on_b.iter().find(|q| find(&mut parent, **q) == root) {
            return Some(if free(a) {
                p
            } else if free(b) || is_straight(sk, a) {
                q
            } else {
                p
            });
        }
    }
    None
}

/// Variables a block depends on, and whether it reads a point that is a constant of the solve.
fn block_vars(sk: &Sketch, lay: &Layout, b: &Block) -> (Vec<usize>, bool) {
    let mut v = Vec::new();
    let mut constant = false;
    // Adds a point's variables; true when it is a constant.
    let pt = |v: &mut Vec<usize>, p: usize| match lay.pvar.get(p).copied().flatten() {
        Some(x) => {
            v.extend([x, x + 1]);
            false
        }
        None => true,
    };
    for r in block_refs(sk, b) {
        let (c, fits): (usize, fn(&CurveKind) -> bool) = match r {
            Ref::Point(p) => {
                constant |= pt(&mut v, p);
                continue;
            }
            Ref::Curve(c) => (c, |_| true),
            Ref::Line(c) => (c, |k| matches!(k, CurveKind::Line { .. })),
            Ref::Round(c) => (c, |k| matches!(k, CurveKind::Circle { .. } | CurveKind::Arc { .. })),
        };
        // A curve of another kind reads as a constant (see `State::line`, `State::round`).
        let Some(k) = sk.curves.get(c).map(|c| &c.kind).filter(|k| fits(k)) else {
            constant = true;
            continue;
        };
        for q in k.point_ids() {
            constant |= pt(&mut v, q);
        }
        v.extend(lay.rvar.get(c).copied().flatten());
    }
    v.sort_unstable();
    v.dedup();
    (v, constant)
}

/// What a block reads: a point, or a curve (its points and its radius), of any kind or read
/// as a line or as a circle or arc (the residual reads another kind as a constant).
#[derive(Clone, Copy)]
enum Ref {
    Point(usize),
    Curve(usize),
    Line(usize),
    Round(usize),
}

/// What a block reads.
fn block_refs(sk: &Sketch, b: &Block) -> Vec<Ref> {
    use ConstraintKind::*;
    use Ref::{Curve as C, Line as L, Point as P, Round as R};
    let is = |c: usize, f: fn(&CurveKind) -> bool| sk.curves.get(c).is_some_and(|x| f(&x.kind));
    let line = |c: usize| is(c, |k| matches!(k, CurveKind::Line { .. }));
    let freeform = |c: usize| is(c, CurveKind::is_freeform);
    // A tangency reads a free-form curve as such, else a line and a round, or two rounds.
    let tangent = |a: usize, b: usize| {
        if freeform(a) || freeform(b) {
            [C(a), C(b)]
        } else if line(a) {
            [L(a), R(b)]
        } else if line(b) {
            [R(a), L(b)]
        } else {
            [R(a), R(b)]
        }
    };
    match b {
        Block::Closure { a, b } => vec![P(*a), P(*b)],
        Block::Arc { c, a, b } => vec![P(*c), P(*a), P(*b)],
        Block::User(_, k) => match **k {
            PatternPoint { p, q, center, directions, .. } => {
                vec![P(p), P(q)].into_iter().chain(center.map(P)).chain(directions.into_iter().flatten().map(|(l, _)| L(l))).collect()
            }
            PatternRadius { a, b } => vec![C(a), C(b)],
            Coincident { p, q }
            | HorizontalPoints { p, q }
            | VerticalPoints { p, q }
            | Distance { p, q, .. }
            | DistanceX { p, q, .. }
            | DistanceY { p, q, .. } => vec![P(p), P(q)],
            PointOnCurve { p, c } | PointAlong { p, c, .. } => vec![P(p), C(c)],
            Midpoint { p, l } | PointLineDistance { p, l, .. } | LinearDiameter { p, l, .. } => vec![P(p), L(l)],
            LineCircleDistance { l, c, .. } => vec![L(l), R(c)],
            PointCircleDistance { p, c, .. } => vec![P(p), R(c)],
            CircleCircleDistance { a, b, .. } => vec![R(a), R(b)],
            Horizontal { l } | Vertical { l } | Length { l, .. } | LineAngle { l, .. } => vec![L(l)],
            // Another kind reads a constant value, whatever its points: as good as any.
            ArcSweep { c, .. } | Radius { c, .. } | Diameter { c, .. } | ArcLength { c, .. } => vec![C(c)],
            Parallel { a, b } | Perpendicular { a, b } | Collinear { a, b } | Angle { a, b, .. } => vec![L(a), L(b)],
            Equal { a, b } if line(a) => vec![L(a), L(b)],
            Equal { a, b } | Concentric { a, b } | SlotOverallLength { a, b, .. } => vec![R(a), R(b)],
            Tangent { a, b } => tangent(a, b).to_vec(),
            Smooth { a, b } => vec![C(a), C(b)],
            Symmetric { p, q, l } => vec![P(p), P(q), L(l)],
            Fix { .. } | OffsetDistance { .. } | Pierce { .. } => vec![],
        },
        Block::TangentAt(_, k, p) => match **k {
            ConstraintKind::Tangent { a, b } if freeform(a) || freeform(b) => vec![P(*p), C(a), C(b)],
            ConstraintKind::Tangent { a, b } => [P(*p)].into_iter().chain(tangent(a, b)).collect(),
            _ => vec![P(*p)],
        },
    }
}

/// A positive distance edited from zero needs an opening direction: central differences
/// of its magnitude cancel at coincidence. Use a unit radial subgradient there, or the
/// signed line normal. Once separated, ordinary central differences apply again.
fn distance_opening_slope(s: &State, b: &Block, v: usize) -> Option<f64> {
    let point = |p: usize, gradient: Vec2| match s.lay.pvar.get(p).copied().flatten() {
        Some(first) if v == first => gradient.x,
        Some(first) if v == first + 1 => gradient.y,
        _ => 0.0,
    };
    match b {
        Block::User(_, ConstraintKind::Distance { p, q, value }) if *value > TOL => {
            let d = s.p(*q) - s.p(*p);
            if d.len() > TOL {
                return None;
            }
            // Unequal nonzero components avoid symmetry with axes and 45-degree guides.
            let direction = d.normalized().unwrap_or(Vec2::new(0.6, 0.8));
            Some(point(*q, direction) - point(*p, direction))
        }
        Block::User(_, ConstraintKind::PointLineDistance { p, l, value }) if *value > TOL => {
            let (a, b) = s.line(*l);
            let signed = line_dist(s.p(*p), a, b);
            if signed.abs() > TOL {
                return None;
            }
            let Some(CurveKind::Line { a: ai, b: bi }) = s.sk.curves.get(*l).map(|c| &c.kind) else { return None };
            let d = b - a;
            let length = d.len();
            if length <= 1e-12 {
                return None;
            }
            let normal = d.perp() * (if signed < 0.0 { -1.0 } else { 1.0 } / length);
            let along = (s.p(*p) - a).dot(d) / (length * length);
            Some(point(*p, normal) + point(*ai, normal * (along - 1.0)) - point(*bi, normal * along))
        }
        _ => None,
    }
}

/// Residual vector and Jacobian (rows × all n vars) for the given blocks.
fn system(sk: &Sketch, lay: &Layout, blocks: &[(Block, Vec<usize>)], x: &mut [f64], with_j: bool) -> (Vec<f64>, Option<Mat>, Vec<usize>) {
    #[cfg(feature = "solver-profiling")]
    let _timer = profiling::timer(Phase::ResidualSystem);
    #[cfg(feature = "solver-profiling")]
    profiling::count(|c| {
        c.residual_system_evaluations = c.residual_system_evaluations.saturating_add(1);
        if with_j {
            c.jacobian_evaluations = c.jacobian_evaluations.saturating_add(1);
        }
    });
    let mut r = Vec::new();
    let mut owner = Vec::new();
    for (bi, (b, _)) in blocks.iter().enumerate() {
        let before = r.len();
        block_residuals(&State { sk, lay, x }, b, &mut r);
        owner.extend(std::iter::repeat_n(bi, r.len() - before));
    }
    if !with_j {
        return (r, None, owner);
    }
    #[cfg(feature = "solver-profiling")]
    let _jacobian_timer = profiling::timer(Phase::Jacobian);
    let mut j = Mat::zeros(r.len(), lay.n);
    let mut row = 0;
    let mut plus = Vec::new();
    let mut minus = Vec::new();
    for (b, vars) in blocks {
        plus.clear();
        block_residuals(&State { sk, lay, x }, b, &mut plus);
        let rows = plus.len();
        for &v in vars {
            let Some(x0) = x.get(v).copied() else { continue };
            let opening = distance_opening_slope(&State { sk, lay, x }, b, v);
            let h = direction_difference_step(&State { sk, lay, x }, b, v, x0);
            if let Some(xv) = x.get_mut(v) {
                *xv = x0 + h;
            }
            plus.clear();
            block_residuals(&State { sk, lay, x }, b, &mut plus);
            if let Some(xv) = x.get_mut(v) {
                *xv = x0 - h;
            }
            minus.clear();
            block_residuals(&State { sk, lay, x }, b, &mut minus);
            if let Some(xv) = x.get_mut(v) {
                *xv = x0;
            }
            for k in 0..rows {
                let d = (plus.get(k).copied().unwrap_or(0.0) - minus.get(k).copied().unwrap_or(0.0)) / (2.0 * h);
                j.set(row + k, v, if k == 0 { opening.unwrap_or(d) } else { d });
            }
        }
        row += rows;
    }
    (r, Some(j), owner)
}

/// Residuals and the Jacobian restricted to `vars` (columns in that order; `col` maps a global
/// variable to its column, usize::MAX elsewhere). Blocks only touch their component's variables,
/// so a component's Jacobian is small even in a huge sketch.
fn local_system(
    sk: &Sketch,
    lay: &Layout,
    blocks: &[(Block, Vec<usize>)],
    x: &mut [f64],
    col: &[usize],
    ncols: usize,
) -> (Vec<f64>, Mat, Vec<usize>) {
    #[cfg(feature = "solver-profiling")]
    let _timer = profiling::timer(Phase::Jacobian);
    #[cfg(feature = "solver-profiling")]
    profiling::count(|c| c.jacobian_evaluations = c.jacobian_evaluations.saturating_add(1));
    let (r, _, owner) = system(sk, lay, blocks, x, false);
    let mut j = Mat::zeros(r.len(), ncols);
    let mut row = 0;
    let mut plus = Vec::new();
    let mut minus = Vec::new();
    for (b, vars) in blocks {
        plus.clear();
        block_residuals(&State { sk, lay, x }, b, &mut plus);
        let rows = plus.len();
        for &v in vars {
            let Some(c) = col.get(v).copied().filter(|c| *c < ncols) else { continue };
            let Some(x0) = x.get(v).copied() else { continue };
            let opening = distance_opening_slope(&State { sk, lay, x }, b, v);
            let h = direction_difference_step(&State { sk, lay, x }, b, v, x0);
            if let Some(xv) = x.get_mut(v) {
                *xv = x0 + h;
            }
            plus.clear();
            block_residuals(&State { sk, lay, x }, b, &mut plus);
            if let Some(xv) = x.get_mut(v) {
                *xv = x0 - h;
            }
            minus.clear();
            block_residuals(&State { sk, lay, x }, b, &mut minus);
            if let Some(xv) = x.get_mut(v) {
                *xv = x0;
            }
            for k in 0..rows {
                let d = (plus.get(k).copied().unwrap_or(0.0) - minus.get(k).copied().unwrap_or(0.0)) / (2.0 * h);
                j.set(row + k, c, if k == 0 { opening.unwrap_or(d) } else { d });
            }
        }
        row += rows;
    }
    (r, j, owner)
}

/// An infinite line's direction derivative must be sampled within its defining span. The
/// usual coordinate-sized step can cross its other end and measure a half-turn instead
/// of the local slope when the saved defining points are very close (#11001).
fn direction_difference_step(s: &State<'_>, block: &Block<'_>, variable: usize, value: f64) -> f64 {
    let mut step = 1e-7 * value.abs().max(1.0);
    let Block::User(_, kind) = block else { return step };
    let lines = match **kind {
        ConstraintKind::Angle { a, b, .. } => [Some(a), Some(b)],
        ConstraintKind::LineAngle { l, .. } => [Some(l), None],
        ConstraintKind::Horizontal { l } | ConstraintKind::Vertical { l } if s.sk.curves.get(l).is_some_and(|c| c.infinite) => [Some(l), None],
        _ => return step,
    };
    for l in lines.into_iter().flatten() {
        let Some(CurveKind::Line { a, b }) = s.sk.curves.get(l).filter(|c| c.infinite).map(|c| &c.kind) else { continue };
        let depends = [a, b].into_iter().any(|&p| s.lay.pvar.get(p).copied().flatten().is_some_and(|v| variable == v || variable == v + 1));
        if depends {
            let length = (s.p(*b) - s.p(*a)).len();
            if length > 0.0 {
                step = step.min(length * 1e-3);
            }
        }
    }
    // Keep both samples representable when the sketch is far from its origin.
    step.max(value.abs() * f64::EPSILON * 8.0)
}

fn max_abs(v: &[f64]) -> f64 {
    v.iter().fold(0.0_f64, |m, x| if x.is_finite() { m.max(x.abs()) } else { f64::INFINITY })
}
fn norm2(v: &[f64]) -> f64 {
    v.iter().map(|x| x * x).sum()
}

/// Levenberg–Marquardt on one component (variables `vars`, blocks `blocks`). Returns the
/// iterations and the largest residual left. Its work counts against a live drag frame's
/// numerical allowance when `budget` has one ([`Budget::frame`]); the solve itself runs as it
/// would without it. `give_up`: stop once
/// stalled (see [`STALL_ITERS`]); not in a live frame, whose allowance is measured in the work
/// the full iteration does.
fn lm_in(
    sk: &Sketch,
    lay: &Layout,
    blocks: &[(Block, Vec<usize>)],
    vars: &[usize],
    x: &mut Vec<f64>,
    col: &[usize],
    budget: &mut Budget,
    give_up: bool,
) -> (usize, f64) {
    if !budget.counts_numeric() {
        return lm_run(sk, lay, blocks, vars, x, col, MAX_ITERS, None, give_up).unwrap_or((0, f64::INFINITY));
    }
    let mut meter = Budget::new(usize::MAX);
    let out = lm_capped_with_budget(sk, lay, blocks, vars, x, col, MAX_ITERS, Some(&mut meter)).unwrap_or((0, f64::INFINITY));
    budget.charge_numeric(meter.spent());
    out
}

/// [`lm`] with at most `max_iters` iterations.
fn lm_capped(
    sk: &Sketch,
    lay: &Layout,
    blocks: &[(Block, Vec<usize>)],
    vars: &[usize],
    x: &mut Vec<f64>,
    col: &[usize],
    max_iters: usize,
) -> (usize, f64) {
    // Without a work budget the initial residual is always evaluated.
    lm_capped_with_budget(sk, lay, blocks, vars, x, col, max_iters, None).unwrap_or((0, f64::INFINITY))
}

/// Deterministic work units, shared with the frame's decomposition budget. Estimates bound
/// dense arithmetic; they are not a wall-clock deadline. None means no residual was evaluated.
fn lm_capped_with_budget(
    sk: &Sketch,
    lay: &Layout,
    blocks: &[(Block, Vec<usize>)],
    vars: &[usize],
    x: &mut Vec<f64>,
    col: &[usize],
    max_iters: usize,
    budget: Option<&mut Budget>,
) -> Option<(usize, f64)> {
    lm_run(sk, lay, blocks, vars, x, col, max_iters, budget, false)
}

/// [`lm_capped_with_budget`], giving up once stalled when `give_up` (see [`STALL_ITERS`]).
fn lm_run(
    sk: &Sketch,
    lay: &Layout,
    blocks: &[(Block, Vec<usize>)],
    vars: &[usize],
    x: &mut Vec<f64>,
    col: &[usize],
    max_iters: usize,
    mut budget: Option<&mut Budget>,
    give_up: bool,
) -> Option<(usize, f64)> {
    #[cfg(feature = "solver-profiling")]
    let _timer = profiling::timer(Phase::Lm);
    let evaluation_work = if budget.is_some() { residual_work(lay, blocks) } else { 0 };
    if !within_budget(&mut budget, evaluation_work) {
        return None;
    }
    let n = vars.len();
    #[cfg(test)]
    lm_vars::add(n);
    let mut lambda = 1e-3;
    let (mut r, _, _) = system(sk, lay, blocks, x, false);
    let mut f = norm2(&r);
    #[cfg(feature = "solver-profiling")]
    let run = profiling::start_run(n, r.len(), max_iters, f);
    // The sum of squares at the start of each iteration, while giving up is allowed.
    let mut costs = Vec::new();
    for it in 0..max_iters {
        if max_abs(&r) < TOL {
            #[cfg(feature = "solver-profiling")]
            profiling::finish_run(run, StopReason::ResidualTolerance, max_abs(&r));
            return Some((it, max_abs(&r)));
        }
        if give_up {
            if let Some(&earlier) = it.checked_sub(STALL_ITERS).and_then(|k| costs.get(k))
                && max_abs(&r) > STALL_RESIDUAL
                && earlier - f <= STALL_DECREASE * earlier
            {
                #[cfg(feature = "solver-profiling")]
                profiling::finish_run(run, StopReason::Stalled, max_abs(&r));
                return Some((it, max_abs(&r)));
            }
            costs.push(f);
        }
        let normal_work =
            n.saturating_mul(n).saturating_mul(r.len()).saturating_add(evaluation_work.saturating_mul(n.saturating_mul(2).saturating_add(1)));
        if !within_budget(&mut budget, normal_work) {
            #[cfg(feature = "solver-profiling")]
            profiling::finish_run(run, StopReason::WorkBudget, max_abs(&r));
            return Some((it, max_abs(&r)));
        }
        #[cfg(feature = "solver-profiling")]
        profiling::count(|c| c.outer_iterations = c.outer_iterations.saturating_add(1));
        let (_, j, _) = local_system(sk, lay, blocks, x, col, n);
        // Normal equations of this component.
        #[cfg(feature = "solver-profiling")]
        let normal_timer = profiling::timer(Phase::NormalEquations);
        let mut a = Mat::zeros(n, n);
        let mut g = vec![0.0; n];
        for row in 0..j.rows {
            let ri = r.get(row).copied().unwrap_or(0.0);
            let nz: Vec<(usize, f64)> = (0..n).map(|li| (li, j.get(row, li))).filter(|(_, d)| *d != 0.0).collect();
            for &(li, di) in &nz {
                if let Some(gi) = g.get_mut(li) {
                    *gi += di * ri;
                }
                for &(lk, dk) in &nz {
                    a.add(li, lk, di * dk);
                }
            }
        }
        #[cfg(feature = "solver-profiling")]
        drop(normal_timer);
        let mut improved = false;
        // Damping by distance moved, not by JᵀJ's diagonal (Marquardt): of the steps that fit the
        // residuals equally well it takes the shortest, so what the constraints leave free moves
        // as little as it can. (Scaled by the diagonal, a variable the residuals see weakly is
        // cheap to move: a point held on a line made the line's far end swing round instead of
        // the point sliding along it.) A point held on a curve is cheaper still, so it slides
        // rather than the curve's ends moving.
        let weight: Vec<f64> = vars.iter().map(|&v| if lay.slide.get(v).copied().unwrap_or(false) { SLIDE_WEIGHT } else { 1.0 }).collect();
        for _attempt in 0..30 {
            let linear_work = n.saturating_mul(n).saturating_mul(n).saturating_add(evaluation_work);
            if !within_budget(&mut budget, linear_work) {
                #[cfg(feature = "solver-profiling")]
                profiling::finish_run(run, StopReason::WorkBudget, max_abs(&r));
                return Some((it, max_abs(&r)));
            }
            let mut m = a.clone();
            for (i, w) in weight.iter().enumerate() {
                m.add(i, i, lambda * w + 1e-12);
            }
            let rhs: Vec<f64> = g.iter().map(|v| -v).collect();
            #[cfg(feature = "solver-profiling")]
            let linear_timer = profiling::timer(Phase::LinearSolve);
            let step = lin_solve(m, rhs);
            #[cfg(feature = "solver-profiling")]
            drop(linear_timer);
            let Some(step) = step else {
                #[cfg(feature = "solver-profiling")]
                profiling::record_trial(run, it, _attempt, lambda, f, None, &g, &j, None, Decision::LinearFailure);
                lambda *= 10.0;
                continue;
            };
            let mut trial = x.clone();
            for (li, &v) in vars.iter().enumerate() {
                if let (Some(t), Some(s)) = (trial.get_mut(v), step.get(li)) {
                    *t += s;
                }
            }
            let (rt, _, _) = system(sk, lay, blocks, &mut trial, false);
            let ft = norm2(&rt);
            #[cfg(feature = "solver-profiling")]
            profiling::record_trial(
                run,
                it,
                _attempt,
                lambda,
                f,
                Some(ft),
                &g,
                &j,
                Some(&step),
                if ft.is_finite() && ft < f { Decision::Accepted } else { Decision::Rejected },
            );
            if ft.is_finite() && ft < f {
                *x = trial;
                r = rt;
                f = ft;
                lambda = (lambda / 3.0).max(1e-12);
                improved = true;
                break;
            }
            lambda *= 4.0;
            if lambda > 1e12 {
                break;
            }
        }
        if !improved {
            #[cfg(feature = "solver-profiling")]
            profiling::finish_run(run, StopReason::NoImprovement, max_abs(&r));
            return Some((it, max_abs(&r)));
        }
    }
    #[cfg(feature = "solver-profiling")]
    profiling::finish_run(run, StopReason::IterationLimit, max_abs(&r));
    Some((max_iters, max_abs(&r)))
}

fn within_budget(budget: &mut Option<&mut Budget>, work: usize) -> bool {
    budget.as_deref_mut().is_none_or(|b| b.try_charge(work))
}

fn residual_work(lay: &Layout, blocks: &[(Block, Vec<usize>)]) -> usize {
    blocks.iter().fold(lay.n.max(1), |work, (_, vars)| work.saturating_add(vars.len().max(1)))
}

/// The variables LM was given and its runs on this thread, for tests that count what the
/// construction leaves to it.
#[cfg(test)]
pub(crate) mod lm_vars {
    use std::cell::Cell;

    thread_local! {
        static VARS: Cell<usize> = const { Cell::new(0) };
        static RUNS: Cell<usize> = const { Cell::new(0) };
    }

    pub(super) fn add(n: usize) {
        VARS.with(|c| c.set(c.get() + n));
        RUNS.with(|c| c.set(c.get() + 1));
    }

    /// The variables since the last call.
    pub(crate) fn take() -> usize {
        VARS.with(|c| c.replace(0))
    }

    /// The LM runs since the last call.
    pub(crate) fn runs() -> usize {
        RUNS.with(|c| c.replace(0))
    }
}

/// The pinned analysis is exact (see [`pinned`]); in this crate's tests every analysis is
/// checked against the dense analysis of the whole component wherever that one is reliable:
/// its Jacobian finite, and its answer the same from a thousandth to a thousand times its
/// tolerance. (Where it is not, the Jacobian is nearly singular and the two analyses may
/// decide its rank differently: the dense one on the whole matrix, the pinned one on the
/// remainder after eliminating what the constraints pin down, and which pivots fall under the
/// tolerance depends on that order.)
#[cfg(test)]
fn assert_dense_agrees(j: &Mat, rank: usize, determined: &[bool]) {
    let at = |tol: f64| if j.rows > 0 { determined_vars(j, tol) } else { (vec![false; j.cols], 0) };
    let dense = at(1e-7);
    if j.data.iter().any(|v| !v.is_finite()) || at(1e-10) != dense || at(1e-4) != dense {
        return;
    }
    assert_eq!((rank, determined), (dense.1, dense.0.as_slice()), "the pinned rank analysis disagrees with the dense one");
}

/// Least squared singular value the rows pinning an unknown must have on its own columns
/// (a singular value of 1e-4, a thousand times the rank analysis' pivot tolerance)…
const PIN_RANK: f64 = 1e-8;
/// …and the least ratio of its squared singular values (a condition number of at most 1e4), so
/// that the 2 × 2 test is decided well clear of rounding.
const PIN_CONDITION: f64 = 1e-8;

/// What [`pinned`] works for.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Pin {
    /// The solve: the candidates are where the seed constructed them, and every row that pins
    /// one must hold there (below `TOL`), as LM will not move it.
    Verified,
    /// The rank analysis of a component some block ties to a constant.
    Anchored,
    /// The rank analysis of a component no block ties to a constant: the point whose first
    /// variable this is counts as a constant (it takes out the translation, see `pinned`).
    Floating(usize),
}

impl Pin {
    /// The first variable of the point taken as a constant.
    fn anchor(self) -> Option<usize> {
        match self {
            Pin::Floating(a) => Some(a),
            Pin::Verified | Pin::Anchored => None,
        }
    }
}

/// Map `keep` to columns `0..` and the other variables of `all` to none.
fn columns(col: &mut [usize], keep: &[usize], all: &[usize]) {
    for v in all {
        if let Some(c) = col.get_mut(*v) {
            *c = usize::MAX;
        }
    }
    for (k, v) in keep.iter().enumerate() {
        if let Some(c) = col.get_mut(*v) {
            *c = k;
        }
    }
}

/// The variables of `vars` neither pinned nor of the point at `anchor` (sorted, as `vars`).
fn unpinned(vars: &[usize], pin: &[bool], anchor: Option<usize>) -> Vec<usize> {
    let anchored = |v: usize| anchor.is_some_and(|a| v == a || v == a + 1);
    vars.iter().zip(pin).filter(|(v, p)| !**p && !anchored(**v)).map(|(v, _)| *v).collect()
}

/// The blocks that read one of `vars` (sorted).
fn blocks_reading<'a>(blocks: &[(Block<'a>, Vec<usize>)], vars: &[usize]) -> Vec<(Block<'a>, Vec<usize>)> {
    blocks.iter().filter(|(_, bv)| bv.iter().any(|v| vars.binary_search(v).is_ok())).map(|(b, v)| (copy_block(b), v.clone())).collect()
}

/// Which variables of one component (`vars`, sorted; `blocks` its blocks) the constraints pin
/// down one unknown after another: an unknown is pinned when the rows of the blocks that read
/// nothing else but constants and unknowns pinned before it have full column rank on its own
/// columns (well conditioned: `PIN_RANK`, `PIN_CONDITION`). Only `candidate` unknowns are
/// pinned; for [`Pin::Verified`] also only where those rows hold.
///
/// Why this is exact. Order the pinned unknowns as they were pinned, P, and call the rest R.
/// Each pinned unknown has its rows S_u, which read nothing after it in P and nothing in R, so
/// the rows S = ∪ S_u of the Jacobian restricted to the columns of P form a block lower
/// triangular matrix whose diagonal blocks have full column rank, and they are zero on R. For
/// any vector (p, r) in the null space of J, S gives p = 0, so the null space is
/// {(0, r) : J_R r = 0}, where J_R is J's columns of R (every row, those of S included, are zero
/// there). Hence:
/// - rank J = |P| + rank J_R: the analysis eliminates P by construction and runs the dense rank
///   analysis on J_R only;
/// - every pinned variable is determined (zero in every null vector), and a variable of R is
///   determined in J exactly when it is in J_R.
///
/// For the solve, the same structure means the pinned values are the only ones near them that
/// satisfy S, given the constants: freezing them at verified values and solving R with LM finds
/// a solution of the whole system whenever one exists with P where the seed put it. (When LM
/// cannot solve R that way, the component is solved whole, as without pinning.)
///
/// A component no block ties to a constant ([`Pin::Floating`]) is invariant under
/// translation: every residual depends only on differences of its points (and radii, which a
/// translation leaves alone), so the translations t_x, t_y are null vectors of J. Removing one
/// point a's two columns then keeps the rank, as any null vector of J is a null vector of J
/// without a (all of whose entries on a are zero) plus a translation: rank J = rank J_{-a}, and
/// J_{-a} is analysed as above with a as a constant. The translations move every point, so no
/// point coordinate of such a component is determined; a radius is determined when it is in
/// J_{-a} (the translations leave it alone).
fn pinned(
    sk: &Sketch,
    lay: &Layout,
    blocks: &[(Block, Vec<usize>)],
    vars: &[usize],
    x: &mut [f64],
    candidate: &dyn Fn(usize) -> bool,
    pin: Pin,
) -> Vec<bool> {
    let nv = vars.len();
    let local = |v: usize| vars.binary_search(&v).ok();
    // Per local unknown (by its first variable's index): pinned, or the anchor.
    let mut done = vec![false; nv];
    if let Some(a) = pin.anchor().and_then(local).and_then(|a| done.get_mut(a)) {
        *a = true;
    }
    let block_units: Vec<Vec<usize>> = blocks
        .iter()
        .map(|(_, bv)| {
            let mut u: Vec<usize> = bv.iter().filter_map(|v| local(lay.unit(*v))).collect();
            u.dedup();
            u
        })
        .collect();
    let mut of_unit: Vec<Vec<usize>> = vec![Vec::new(); nv];
    for (bi, us) in block_units.iter().enumerate() {
        for u in us {
            if let Some(list) = of_unit.get_mut(*u) {
                list.push(bi);
            }
        }
    }
    let open = |done: &[bool], u: &usize| !done.get(*u).copied().unwrap_or(true);
    // Per block: its unknowns not pinned yet. A block is ready for its last one.
    let mut pending: Vec<usize> = block_units.iter().map(|us| us.iter().filter(|u| open(&done, u)).count()).collect();
    let mut ready: Vec<usize> = (0..blocks.len()).filter(|bi| pending.get(*bi) == Some(&1)).rev().collect();
    let mut gram = vec![[0.0_f64; 3]; nv];
    let mut bad = vec![false; nv];
    let mut queue = Vec::new();
    let mut out = vec![false; nv];
    loop {
        while let Some(bi) = ready.pop() {
            let (Some(us), Some((block, _))) = (block_units.get(bi), blocks.get(bi)) else { continue };
            let Some(&u) = us.iter().find(|u| open(&done, u)) else { continue };
            let Some(&first) = vars.get(u) else { continue };
            if bad.get(u).copied().unwrap_or(true) || !candidate(first) {
                continue;
            }
            let Some(g) = gram.get_mut(u) else { continue };
            let residual = accumulate(sk, lay, block, &[first, first + 1][..lay.width(first)], x, g);
            if pin == Pin::Verified
                && !(residual < TOL)
                && let Some(b) = bad.get_mut(u)
            {
                *b = true;
                continue;
            }
            queue.push(u);
        }
        let Some(u) = queue.pop() else { break };
        let (Some(&first), Some(&g)) = (vars.get(u), gram.get(u)) else { continue };
        let w = lay.width(first);
        if !open(&done, &u) || bad.get(u).copied().unwrap_or(true) || !full_rank(g, w) {
            continue;
        }
        for k in u..u + w {
            if let (Some(d), Some(o)) = (done.get_mut(k), out.get_mut(k)) {
                (*d, *o) = (true, true);
            }
        }
        for &bi in of_unit.get(u).into_iter().flatten() {
            if let Some(p) = pending.get_mut(bi) {
                *p = p.saturating_sub(1);
                if *p == 1 {
                    ready.push(bi);
                }
            }
        }
    }
    out
}

/// Add the rows of block `b`, restricted to the columns of `unit` (one or two variables), to
/// `gram` (their AᵀA: [a00, a01, a11]), with the same differences as [`local_system`]; returns
/// the block's largest residual.
fn accumulate(sk: &Sketch, lay: &Layout, b: &Block, unit: &[usize], x: &mut [f64], gram: &mut [f64; 3]) -> f64 {
    let mut r = Vec::new();
    block_residuals(&State { sk, lay, x }, b, &mut r);
    let mut d = [Vec::new(), Vec::new()];
    let (mut plus, mut minus) = (Vec::new(), Vec::new());
    for (&v, dk) in unit.iter().zip(&mut d) {
        let Some(x0) = x.get(v).copied() else { continue };
        let h = direction_difference_step(&State { sk, lay, x }, b, v, x0);
        for (at, out) in [(x0 + h, &mut plus), (x0 - h, &mut minus)] {
            if let Some(xv) = x.get_mut(v) {
                *xv = at;
            }
            out.clear();
            block_residuals(&State { sk, lay, x }, b, out);
        }
        if let Some(xv) = x.get_mut(v) {
            *xv = x0;
        }
        *dk = plus.iter().zip(&minus).map(|(p, m)| (p - m) / (2.0 * h)).collect();
    }
    let [d0, d1] = &d;
    for k in 0..r.len() {
        let (a, b) = (d0.get(k).copied().unwrap_or(0.0), d1.get(k).copied().unwrap_or(0.0));
        gram[0] += a * a;
        gram[1] += a * b;
        gram[2] += b * b;
    }
    max_abs(&r)
}

/// The rows behind `gram` (see [`accumulate`]) have full, well-conditioned column rank on a
/// unit of `width` variables.
fn full_rank(gram: [f64; 3], width: usize) -> bool {
    let [a, b, c] = gram;
    let (min, max) = if width == 1 {
        (a, a)
    } else {
        let max = 0.5 * (a + c + ((a - c).powi(2) + 4.0 * b * b).sqrt());
        (if max > 0.0 { (a * c - b * b) / max } else { 0.0 }, max)
    };
    min.is_finite() && max.is_finite() && min >= PIN_RANK && min >= PIN_CONDITION * max
}

/// Solve the sketch in place. On failure the geometry is restored and the report lists the
/// violated constraints.
pub fn solve(sk: &mut Sketch) -> SolveReport {
    solve_with(sk, &Hold::default(), None, Analysis::Full, None)
}

/// Solve with some geometry held as if it were fixed (for this solve only): applying a
/// constraint between two entities holds the first so only the second moves. Everything else
/// moves as little as it can. On failure the geometry is restored.
pub fn solve_holding(sk: &mut Sketch, hold: &Hold) -> SolveReport {
    solve_with(sk, hold, None, Analysis::Full, None)
}

/// What a solve works out besides placing the geometry.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Analysis {
    /// Freedom analysis plus redundant constraint IDs. This is the complete diagnostic report
    /// used by the public solve helpers and final sketch evaluation.
    Full,
    /// Degrees of freedom and which geometry the constraints determine, with the same rank
    /// analysis as `Full`, but no redundant constraint search (`redundant` is empty).
    Freedom,
    /// Only whether it solved: the report's `dof` is 0 and its determined flags are empty. For
    /// solves whose report is only checked with [`SolveReport::ok`] (the frames of a drag).
    StatusOnly,
}

/// [`solve`] with some geometry held as if it were fixed (for this solve only): applying a
/// constraint between two entities holds the first so only the second moves; a drag holds what
/// it drags. Everything else moves as little as it can. On failure the geometry is restored.
///
/// `reference`, after an interactive move: the points' positions from before it. Points the
/// constraints pin down keep the orientation they had there rather than the one the move left
/// them in. Points appended after the reference was taken use their current positions; a
/// reference longer than the point list is ignored.
///
/// `budget`: the work the seed's cluster decomposition may do, shared with other solves (the
/// steps of a live drag frame, [`Budget::frame`]); [`Budget::full`] for this solve alone when
/// `None`.
pub fn solve_with(sk: &mut Sketch, hold: &Hold, reference: Option<&[Vec2]>, analysis: Analysis, budget: Option<&mut Budget>) -> SolveReport {
    let mut own = Budget::full();
    solve_from(sk, hold, reference, analysis, None, budget.unwrap_or(&mut own))
}

/// Driving values by constraint id (see [`Sketch::driving_values`]).
pub type DrivingValues = std::collections::BTreeMap<String, f64>;

/// [`solve`] after driving values changed: the sketch's geometry is its stored solved state,
/// solved for `old` (by constraint id; constraints added since have none). A component the
/// construction leaves to the iteration (a triconnected one) can fail to converge, or fold a
/// constrained triangle over, when solved for the new values in one jump; it is then solved
/// again by stepping its changed values from old to new (see `continue_values`). Where no
/// value changed a solve behaves as [`solve`].
pub fn solve_after_value_edit(sk: &mut Sketch, old: &DrivingValues) -> SolveReport {
    solve_after_edit(sk, old, None)
}

/// [`solve_after_value_edit`] of a sketch whose linked geometry may have moved as well: once
/// its links are refreshed ([`Sketch::update_link`]), the linked points are where their sources
/// are now and everything else is still the stored solved state. `stored` has every point's
/// position in that state ([`Sketch::positions_in`]; `None` when no link moved), and the sides
/// and turns the solve keeps are read there, as [`solve_with`] reads them from the positions
/// before an interactive move. Read where the links are now, a point dimensioned from a
/// projected line is on the far side of it as soon as the source moves the line past the point.
pub fn solve_after_edit(sk: &mut Sketch, old: &DrivingValues, stored: Option<&[Vec2]>) -> SolveReport {
    solve_after_edit_with_analysis(sk, old, stored, Analysis::Full)
}

/// [`solve_after_edit`] with only the requested diagnostics. Continuation, branch checks and
/// geometry restoration are identical at every analysis level.
pub fn solve_after_edit_with_analysis(sk: &mut Sketch, old: &DrivingValues, stored: Option<&[Vec2]>, analysis: Analysis) -> SolveReport {
    let old_values: Vec<Option<f64>> = sk.constraints.iter().map(|c| old.get(&c.id).copied()).collect();
    solve_from(sk, &Hold::default(), stored, analysis, Some(&old_values), &mut Budget::full())
}

/// The orientations of `stored` that `solved` (the same sketch, its links moved and solved
/// again) turned over, by constraint id: the sides of unsigned offsets and the turns of
/// distance triangles, each read where `stored` has its points and where `solved` has them.
/// A solve after its links moved checks none of these when no value changed, so a jump can
/// land on the mirror image of a part of the sketch and still report it solved. Empty when the
/// two sketches are not the same entities (a link was rebuilt).
pub fn flips_from_stored(solved: &Sketch, stored: &Sketch) -> Vec<String> {
    let aligned = solved.points.len() == stored.points.len()
        && solved.curves.len() == stored.curves.len()
        && solved.constraints.len() == stored.constraints.len()
        && solved.points.iter().zip(&stored.points).all(|(p, q)| p.id == q.id)
        && solved.constraints.iter().zip(&stored.constraints).all(|(c, d)| c.id == d.id);
    if !aligned {
        return Vec::new();
    }
    let hold = Hold::default();
    let (lay_before, lay_now) = (layout(stored, &hold), layout(solved, &hold));
    let (x_before, x_now) = (initial_x(stored, &lay_before), initial_x(solved, &lay_now));
    let before = State { sk: stored, lay: &lay_before, x: &x_before };
    let now = State { sk: solved, lay: &lay_now, x: &x_now };
    let (blocks, _) = build_blocks(stored, &lay_before, &points_on_curves(stored));
    let mut out: Vec<String> = Vec::new();
    for (o, cs) in orients(&before, &blocks) {
        if reference_orientation(&before, o).zip(orientation(&now, o)).is_some_and(|(b, n)| b != n) {
            for ci in cs {
                if let Some(c) = stored.constraints.get(ci)
                    && !out.contains(&c.id)
                {
                    out.push(c.id.clone());
                }
            }
        }
    }
    out
}

/// The finest steps a link move is split into: a walk that needs smaller ones gives up.
const LINK_STEPS: usize = 4096;
/// The walk's first step (in [`LINK_STEPS`]), small enough to stay on the stored solution's
/// branch; the secant of it predicts the next.
const LINK_FIRST_STEP: usize = 4;
/// Most solves one [`solve_after_link_move`] may spend.
const LINK_STEP_SOLVES: usize = 400;

/// [`solve_after_edit`] for a sketch whose linked (or fixed) points moved far from where
/// `stored` has them, when that solve fails or turns the sketch over (also as
/// [`flips_from_stored`] tells): one jump can take a
/// sketch of many constraints to a solution it cannot reach (the iteration fails) or to
/// another one (a dimension's side flips), although the sketch solves where the links are now
/// when it is drawn there. The changed values are solved first with the links where they were
/// stored; then the moved points are walked from there to where they are now, in steps that
/// halve where a step fails or turns a constraint over and grow again where they solve, each
/// solved from the last two solutions carried on along their secant. `sk` is the stored sketch with its links refreshed and
/// its new values applied (what [`solve_after_edit`] takes), `old` the values `stored` is
/// solved for. `None` (and `sk` left as it was) when nothing moved, the point lists differ (a
/// link was rebuilt), or the walk does not reach the end.
pub fn solve_after_link_move(sk: &mut Sketch, stored: &Sketch, old: &DrivingValues, analysis: Analysis) -> Option<SolveReport> {
    let aligned = sk.points.len() == stored.points.len() && sk.points.iter().zip(&stored.points).all(|(p, q)| p.id == q.id);
    if !aligned || sk.curves.len() != stored.curves.len() {
        return None;
    }
    let to: Vec<Vec2> = sk.points.iter().map(|p| p.pos).collect();
    let from: Vec<Vec2> = stored.points.iter().map(|p| p.pos).collect();
    let moving: Vec<usize> =
        sk.points.iter().enumerate().filter(|(i, p)| (p.fixed || p.link.is_some()) && from.get(*i) != to.get(*i)).map(|(i, _)| i).collect();
    // Linked circles keep their radius as a constant: it is walked with the points.
    let radius = |c: &crate::model::Curve| match c.kind {
        CurveKind::Circle { r, .. } | CurveKind::Ellipse { r, .. } if c.link.is_some() => Some(r),
        _ => None,
    };
    let radii: Vec<(usize, f64, f64)> = sk
        .curves
        .iter()
        .zip(&stored.curves)
        .enumerate()
        .filter_map(|(i, (c, s))| Some((i, radius(s)?, radius(c)?)))
        .filter(|(_, a, b)| a != b)
        .collect();
    if moving.is_empty() && radii.is_empty() {
        return None;
    }
    let target = sk.clone();
    // The walk's sketch at `t` of the way: the moved points there, every other point where the
    // last solved step left it.
    let at = |t: f64, solved: &[Vec2]| -> Sketch {
        let mut step = target.clone();
        for (p, s) in step.points.iter_mut().zip(solved) {
            p.pos = *s;
        }
        for &i in &moving {
            if let (Some(p), Some(a), Some(b)) = (step.points.get_mut(i), from.get(i), to.get(i)) {
                p.pos = *a + (*b - *a) * t;
            }
        }
        for &(i, a, b) in &radii {
            if let Some(crate::model::Curve { kind: CurveKind::Circle { r, .. } | CurveKind::Ellipse { r, .. }, .. }) = step.curves.get_mut(i) {
                *r = a + (b - a) * t;
            }
        }
        step
    };
    // The new values where the links were stored (a value edit, continued as `solve_after_edit` does).
    let mut first = at(0.0, &from);
    if !solve_after_edit_with_analysis(&mut first, old, None, Analysis::StatusOnly).keeps_orientation() {
        return None;
    }
    let mut solved: Vec<Vec2> = first.points.iter().map(|p| p.pos).collect();
    let values = target.driving_values();
    // Predictor and corrector: each step starts from the last two solutions carried on along
    // their secant (a tangent to a moving circle moves with it instead of hopping to the
    // circle's other side) and is solved from there. A tiny first step gives the secant; a
    // step grows while it solves, and stays below one that failed (a failed solve costs the
    // iteration's whole budget) until a run of solved steps lets it grow again.
    let mut prev: Option<(usize, Vec<Vec2>)> = None;
    let (mut t, mut h, mut cap, mut run, mut spent) = (0usize, LINK_FIRST_STEP, LINK_STEPS, 0usize, 0usize);
    while t < LINK_STEPS {
        if spent >= LINK_STEP_SOLVES {
            return None;
        }
        spent += 1;
        let next = (t + h).min(LINK_STEPS);
        let start: Vec<Vec2> = match &prev {
            Some((tp, pp)) if *tp < t => {
                let k = (next - t) as f64 / (t - tp) as f64;
                solved.iter().zip(pp).map(|(s, p)| *s + (*s - *p) * k).collect()
            }
            _ => solved.clone(),
        };
        let mut step = at(next as f64 / LINK_STEPS as f64, &start);
        let last = at(t as f64 / LINK_STEPS as f64, &solved);
        let before = step.positions_in(&last);
        if solve_after_edit_with_analysis(&mut step, &values, before.as_deref(), Analysis::StatusOnly).keeps_orientation()
            && flips_from_stored(&step, &last).is_empty()
        {
            prev = Some((t, std::mem::replace(&mut solved, step.points.iter().map(|p| p.pos).collect())));
            t = next;
            run += 1;
            if run >= 3 {
                (cap, run) = ((2 * cap).min(LINK_STEPS), 0);
            }
            h = (2 * h).min(cap).max(1);
        } else if h > 1 {
            (cap, run) = ((h / 2).max(1), 0);
            h /= 2;
        } else {
            return None;
        }
    }
    let mut done = target;
    for (p, s) in done.points.iter_mut().zip(&solved) {
        p.pos = *s;
    }
    let report = solve_with(&mut done, &Hold::default(), Some(&solved), analysis, None);
    (report.keeps_orientation() && flips_from_stored(&done, stored).is_empty()).then(|| {
        *sk = done;
        report
    })
}

impl Sketch {
    /// Each dimension's driving value by constraint id, as [`solve_after_value_edit`] takes
    /// them.
    pub fn driving_values(&self) -> DrivingValues {
        self.constraints.iter().filter_map(|c| Some((c.id.clone(), c.kind.value()?))).collect()
    }
}

/// The variables' values where the sketch is now.
fn initial_x(sk: &Sketch, lay: &Layout) -> Vec<f64> {
    let mut x = vec![0.0; lay.n];
    for (i, p) in sk.points.iter().enumerate() {
        if let Some(v) = lay.pvar.get(i).copied().flatten() {
            set_point(&mut x, v, p.pos);
        }
    }
    for (i, c) in sk.curves.iter().enumerate() {
        if let (CurveKind::Circle { r, .. } | CurveKind::Ellipse { r, .. }, Some(v)) = (&c.kind, lay.rvar.get(i).copied().flatten())
            && let Some(s) = x.get_mut(v)
        {
            *s = *r;
        }
    }
    x
}

/// The solve's blocks in order (the curves' own relations, then the driving constraints in
/// constraint order) with the variables each reads, and per block whether it reads a constant
/// point.
fn build_blocks<'a>(sk: &'a Sketch, lay: &Layout, on_curve: &[(usize, usize)]) -> (Vec<(Block<'a>, Vec<usize>)>, Vec<bool>) {
    let mut raw = Vec::new();
    for (k, c) in sk.curves.iter().enumerate() {
        if let CurveKind::Spline { pts, periodic: true, .. } = &c.kind
            && let (Some(a), Some(b)) = (pts.first(), pts.last())
            && a != b
        {
            raw.push(Block::Closure { a: *a, b: *b });
        }
        if let CurveKind::Arc { c, a, b } = c.kind
            && !sk.offset_arc_follows_source(k)
        {
            raw.push(Block::Arc { c, a, b });
        }
    }
    for (i, c) in sk.constraints.iter().enumerate() {
        if c.driven || matches!(c.kind, ConstraintKind::OffsetDistance { .. }) || sk.follows_its_source(&c.kind) {
            continue;
        }
        raw.push(match touch_point(sk, &c.kind, on_curve) {
            Some(p) => Block::TangentAt(i, &c.kind, p),
            None => Block::User(i, &c.kind),
        });
    }
    let mut blocks: Vec<(Block, Vec<usize>)> = Vec::with_capacity(raw.len());
    let mut reads_constant = Vec::with_capacity(raw.len());
    for bl in raw {
        let (vars, constant) = block_vars(sk, lay, &bl);
        blocks.push((bl, vars));
        reads_constant.push(constant);
    }

    (blocks, reads_constant)
}

#[cfg(not(test))]
fn solve_from(
    sk: &mut Sketch,
    hold: &Hold,
    reference: Option<&[Vec2]>,
    analysis: Analysis,
    old_values: Option<&[Option<f64>]>,
    budget: &mut Budget,
) -> SolveReport {
    solve_sensed(sk, hold, reference, analysis, old_values, budget)
}

/// In this crate's tests every solve is repeated without the constructive seed: the seed only
/// chooses where the iteration starts, so status, degrees of freedom and determined flags must
/// not depend on it, nor the (empty) failing list of a solved sketch. The one difference
/// allowed is the seed's purpose: the iteration from the plain start fails where the seeded
/// one solves. Which constraints a failed solve leaves violated depends on where the iteration
/// stopped; the seed may only narrow it.
#[cfg(test)]
fn solve_from(
    sk: &mut Sketch,
    hold: &Hold,
    reference: Option<&[Vec2]>,
    analysis: Analysis,
    old_values: Option<&[Option<f64>]>,
    budget: &mut Budget,
) -> SolveReport {
    use crate::construct::switch;
    if !(switch::seed_on() && switch::differential_on()) {
        return solve_sensed(sk, hold, reference, analysis, old_values, budget);
    }
    let mut plain = sk.clone();
    let without = switch::without_seed(|| solve_sensed(&mut plain, hold, reference, analysis, old_values, &mut Budget::full()));
    let with = solve_sensed(sk, hold, reference, analysis, old_values, budget);
    assert_same_outcome(&with, &without);
    with
}

/// The outcome the constructive seed must not change (see `solve_from`).
#[cfg(test)]
fn assert_same_outcome(with: &SolveReport, without: &SolveReport) {
    if with.ok() && !without.ok() {
        return;
    }
    assert_eq!(
        (with.status, with.dof, &with.point_determined, &with.curve_determined),
        (without.status, without.dof, &without.point_determined, &without.curve_determined),
        "the constructive seed changed the solve's outcome"
    );
    // Turned-over orientations depend on where the iteration went; only conflicts count.
    let conflicts = |r: &SolveReport| r.failing.iter().filter(|c| !r.folded.contains(c)).cloned().collect::<Vec<_>>();
    if with.ok() {
        assert_eq!(conflicts(with), conflicts(without));
    } else {
        assert!(conflicts(with).iter().all(|c| without.failing.contains(c)), "seeded {with:?}, unseeded {without:?}");
    }
}

/// Write a point's position into its two variables starting at `v`.
/// An arc's ends follow its centre: when the seed moved the centre and did not construct an end,
/// that end starts carried by the centre's displacement (the arc translates, keeping its radius).
/// Left behind, the ends of an arc whose centre is put on the origin are turned by LM instead of
/// following it (reference test 20-slot-constrained).
fn carry_with_seeded(x: &mut [f64], x0: &[f64], constructed: &[bool], blocks: &[(Block, Vec<usize>)], lay: &Layout) {
    let var = |p: usize| lay.pvar.get(p).copied().flatten();
    let built = |v: usize| constructed.get(v).copied().unwrap_or(false);
    let mut carried: Vec<(usize, Vec2)> = Vec::new();
    for (block, _) in blocks {
        let Block::Arc { c, a, b } = *block else { continue };
        let Some(vc) = var(c).filter(|v| built(*v)) else { continue };
        let (Some(now), Some(was)) = (x.get(vc..vc + 2), x0.get(vc..vc + 2)) else { continue };
        let d = Vec2::new(now[0] - was[0], now[1] - was[1]);
        if d.x == 0.0 && d.y == 0.0 {
            continue;
        }
        carried.extend([a, b].into_iter().filter_map(var).filter(|v| !built(*v)).map(|v| (v, d)));
    }
    for (v, d) in carried {
        if let Some([px, py]) = x.get_mut(v..v + 2) {
            *px += d.x;
            *py += d.y;
        }
    }
}

fn set_point(x: &mut [f64], v: usize, at: Vec2) {
    if let Some([sx, sy]) = x.get_mut(v..v.saturating_add(2)) {
        *sx = at.x;
        *sy = at.y;
    }
}

/// Exactly opposite directions sit on the wrapped angle's derivative discontinuity: nudge one
/// free endpoint of each such line into a continuous branch before Newton iterations.
fn nudge_line_angles(sk: &Sketch, lay: &Layout, x: &mut [f64]) {
    for constraint in &sk.constraints {
        if constraint.driven {
            continue;
        }
        let ConstraintKind::LineAngle { l, value } = constraint.kind else { continue };
        let Some(CurveKind::Line { a, b }) = sk.curves.get(l).map(|c| &c.kind) else { continue };
        let state = State { sk, lay, x };
        let (pa, pb) = (state.p(*a), state.p(*b));
        let delta = wrap_angle((pb - pa).angle() - value);
        if delta.abs() < std::f64::consts::PI - 1e-5 || !delta.is_finite() {
            continue;
        }
        let d = Vec2::from_angle((pb - pa).angle() - delta.signum() * 0.01) * pa.dist(pb);
        let (point, at) = if lay.pvar.get(*b).copied().flatten().is_some() { (*b, pa + d) } else { (*a, pb - d) };
        if let Some(index) = lay.pvar.get(point).copied().flatten() {
            set_point(x, index, at);
        }
    }
}

/// Continuation steps an edit in sixty-fourths of it: the smallest sub-step is one of them.
const SUBSTEPS: usize = 64;
/// LM iterations one continuation may spend over all its sub-steps (taken and halved).
const CONTINUATION_ITERS: usize = 4 * MAX_ITERS;
/// Triangles of distance dimensions whose turn one component's fold check reads.
const MAX_TRIPLES: usize = 1024;
/// Neighbour visits while finding those triangles.
const MAX_TRIPLE_WORK: usize = 100_000;

/// An orientation the constraints leave open, which an edit of their values must keep: the
/// mirror image is "the other solution" (Owen 1991 §5: whether three dimensioned points occur
/// clockwise or counter-clockwise; an unsigned offset's side).
#[derive(Clone, Copy, Debug)]
enum Orient {
    /// The turn of three points pairwise joined by distances (coincident corners merged).
    Turn([usize; 3]),
    /// Which side of `p` the point `q` is along x (`DistanceX` of the given size).
    SideX(usize, usize, f64),
    /// The same along y (`DistanceY`).
    SideY(usize, usize, f64),
    /// Which side of line `l` the point `p` is on (`PointLineDistance`, `LinearDiameter`, a
    /// circle's centre for `LineCircleDistance`).
    OfLine(usize, usize, f64),
    /// Which of two nested circles or arcs encloses the other.
    RadiusOrder(usize, usize),
    /// Which way along line `l` the point `q` is from `p`: a `Distance` between two points that
    /// both lie on `l` (its ends, points on it, or points coincident with either; one of them may
    /// lie on it by what else holds it).
    Along(usize, usize, usize, f64),
}

/// An orientation's signed offset in a state (a corner's distance from the opposite side, an
/// offset along its axis or from its line), the size it is measured against and how far the
/// coordinates are from the origin.
fn offset(s: &State, o: Orient) -> Option<(f64, f64, f64)> {
    let coords = |ps: &[Vec2]| ps.iter().fold(0.0_f64, |m, p| m.max(crate::loci::mag(*p)));
    Some(match o {
        Orient::Turn([a, b, c]) => {
            let (pa, pb, pc) = (s.p(a), s.p(b), s.p(c));
            let size = pa.dist(pb).max(pa.dist(pc)).max(pb.dist(pc));
            ((pb - pa).normalized()?.cross(pc - pa), size, coords(&[pa, pb, pc]))
        }
        Orient::SideX(p, q, size) => {
            let (pp, pq) = (s.p(p), s.p(q));
            (pq.x - pp.x, size, coords(&[pp, pq]))
        }
        Orient::SideY(p, q, size) => {
            let (pp, pq) = (s.p(p), s.p(q));
            (pq.y - pp.y, size, coords(&[pp, pq]))
        }
        Orient::OfLine(p, l, size) => {
            let (a, b) = s.line(l);
            let pp = s.p(p);
            ((b - a).normalized()?.cross(pp - a), size, coords(&[pp, a, b]))
        }
        Orient::RadiusOrder(a, b) => {
            let (ca, ra) = s.round(a);
            let (cb, rb) = s.round(b);
            // Even a thin wall has an inside and an outside. Use the radius difference as
            // its size; rounding still accounts for the radii and the arc coordinates.
            (ra - rb, (ra - rb).abs(), ra.max(rb).max(coords(&[ca, cb])))
        }
        Orient::Along(p, q, l, size) => {
            let (a, b) = s.line(l);
            let (pp, pq) = (s.p(p), s.p(q));
            ((b - a).normalized()?.dot(pq - pp), size, coords(&[pp, pq, a, b]))
        }
    })
}

/// The sign of an orientation in a state; `None` when too close to zero to tell. It is the
/// constructive seed's side test (`loci::side`, the rounding of the coordinates and a tiny
/// share of the size), so the seed and the fold check agree on which way a triangle turns.
/// Belongs in `loci` beside `side` (moved there once the lines-and-rounds work is merged).
fn orientation(s: &State, o: Orient) -> Option<f64> {
    offset(s, o).and_then(|(delta, size, coords)| crate::loci::side(delta, size, coords))
}

/// A reference orientation must be clear: an offset of at least this share of its size (for a
/// triangle, a height of 1/1000 of its longest side, about 0.06°). Nearer degenerate, solver
/// noise decides the sign, and no edit is refused for turning it over.
const ORIENTED: f64 = 1e-3;

/// The orientation of the stored state that an edit must keep: its sign where it is clear
/// (see [`ORIENTED`]), else `None`.
fn reference_orientation(s: &State, o: Orient) -> Option<f64> {
    offset(s, o).filter(|(delta, size, _)| delta.abs() > ORIENTED * size).and_then(|(delta, size, coords)| crate::loci::side(delta, size, coords))
}

/// A driving value `t` of the way from `old` to `new`: angles of a line or between two lines
/// turn the short way round.
fn value_at(kind: &ConstraintKind, old: f64, new: f64, t: f64) -> f64 {
    if t >= 1.0 {
        return new;
    }
    match kind {
        ConstraintKind::LineAngle { .. } | ConstraintKind::Angle { .. } => old + wrap_angle(new - old) * t,
        _ => old + (new - old) * t,
    }
}

/// Whether a value can be stepped from `old` to `new`: not a signed arc sweep that changes
/// sign (the arc's end points swap; there is no path of arcs between the two).
fn steppable(kind: &ConstraintKind, old: f64, new: f64) -> bool {
    !(matches!(kind, ConstraintKind::ArcSweep { .. }) && old * new <= 0.0)
}

/// One component's driving values changed by an edit, and the orientations of the stored
/// state.
struct ValueEdit {
    /// Block index, constraint index, the constraint (with its new value) and its old value.
    changed: Vec<(usize, usize, ConstraintKind, f64)>,
    /// Orientations with the constraints that set them and their sign in the stored state.
    orients: Vec<(Orient, Vec<usize>, Option<f64>)>,
}

impl ValueEdit {
    /// The values of `sub` changed against `old` (per constraint), `before` being the stored
    /// state; `None` when nothing changed.
    fn of(before: &State, sub: &[(Block, Vec<usize>)], old: &[Option<f64>]) -> Option<Self> {
        let changed: Vec<_> = sub
            .iter()
            .enumerate()
            .filter_map(|(k, (b, _))| {
                let Block::User(ci, kind) = b else { return None };
                let (o, n) = (old.get(*ci).copied().flatten()?, kind.value()?);
                (o.is_finite() && n.is_finite() && o != n).then(|| (k, *ci, (*kind).clone(), o))
            })
            .collect();
        if changed.is_empty() {
            return None;
        }
        let orients = orients(before, sub).into_iter().map(|(o, cs)| (o, cs, reference_orientation(before, o))).collect();
        Some(ValueEdit { changed, orients })
    }

    /// The stored state is solved for the old values: there is a solved state to continue
    /// from and orientations to keep (a sketch stored unsolved has neither).
    fn starts_solved(&self, before: &State, sub: &[(Block, Vec<usize>)]) -> bool {
        let olds = self.kinds_at(0);
        let mut blocks: Vec<(Block, Vec<usize>)> = sub.iter().map(|(b, v)| (copy_block(b), v.clone())).collect();
        self.point_at(&mut blocks, &olds);
        max_abs(&system(before.sk, before.lay, &blocks, &mut before.x.to_vec(), false).0) < ACCEPT
    }

    /// The values can be stepped (see [`steppable`]).
    fn continuable(&self) -> bool {
        self.changed.iter().all(|(_, _, k, o)| k.value().is_some_and(|n| steppable(k, *o, n)))
    }

    /// The changed constraints `j` sixty-fourths of the way from their old values to the new.
    fn kinds_at(&self, j: usize) -> Vec<ConstraintKind> {
        let t = j as f64 / SUBSTEPS as f64;
        self.changed
            .iter()
            .map(|(_, _, kind, o)| {
                let mut k = kind.clone();
                if let Some(n) = kind.value() {
                    k.set_value(value_at(kind, *o, n, t));
                }
                k
            })
            .collect()
    }

    /// Point the changed constraints' blocks at `kinds` (as [`ValueEdit::kinds_at`] gives them).
    fn point_at<'a>(&self, blocks: &mut [(Block<'a>, Vec<usize>)], kinds: &'a [ConstraintKind]) {
        for ((k, ci, ..), kind) in self.changed.iter().zip(kinds) {
            if let Some(slot) = blocks.get_mut(*k) {
                slot.0 = Block::User(*ci, kind);
            }
        }
    }

    /// The constraints setting an orientation of the stored state that `now` turns the other way.
    fn flipped<'a>(&'a self, now: &'a State) -> impl Iterator<Item = &'a usize> + 'a {
        self.orients.iter().filter(|(o, _, before)| before.zip(orientation(now, *o)).is_some_and(|(b, n)| b != n)).flat_map(|(_, cs, _)| cs)
    }

    /// Solved, keeping every orientation of the stored state.
    fn holds(&self, residual: f64, now: &State) -> bool {
        residual < ACCEPT && self.flipped(now).next().is_none()
    }
}

/// The orientations the driving constraints of `sub` leave open: triangles of distances and
/// line lengths (coincident points count as one, the corners of a triangle of lines), and the
/// sides of unsigned offsets. Each with the constraints that set it; capped.
fn orients(s: &State, sub: &[(Block, Vec<usize>)]) -> Vec<(Orient, Vec<usize>)> {
    use std::collections::{BTreeMap, BTreeSet};
    let free = |p: usize| s.lay.pvar.get(p).copied().flatten().is_some();
    let line = |l: usize| match s.sk.curves.get(l).map(|c| &c.kind) {
        Some(CurveKind::Line { a, b }) => Some((*a, *b)),
        _ => None,
    };
    let mut out = Vec::new();
    let mut joins = Vec::new();
    let mut edges = Vec::new();
    let mut spans: Vec<(usize, usize, f64, usize)> = Vec::new();
    for (b, _) in sub {
        // A tangency at a point the two curves share (or a line's end held on the round) is a
        // block of its own; its round keeps its side of the line all the same.
        let (Block::User(ci, kind) | Block::TangentAt(ci, kind, _)) = b else { continue };
        match **kind {
            ConstraintKind::Coincident { p, q } => joins.push((p, q)),
            ConstraintKind::Distance { p, q, value } => {
                edges.push((p, q, *ci));
                spans.push((p, q, value, *ci));
            }
            ConstraintKind::Length { l, .. } => edges.extend(line(l).map(|(p, q)| (p, q, *ci))),
            ConstraintKind::DistanceX { p, q, value } if free(p) || free(q) => out.push((Orient::SideX(p, q, value), vec![*ci])),
            ConstraintKind::DistanceY { p, q, value } if free(p) || free(q) => out.push((Orient::SideY(p, q, value), vec![*ci])),
            ConstraintKind::PointLineDistance { p, l, value } => out.push((Orient::OfLine(p, l, value), vec![*ci])),
            ConstraintKind::LinearDiameter { p, l, value } => out.push((Orient::OfLine(p, l, value / 2.0), vec![*ci])),
            // The unsigned gap has two solutions: a large diameter edit can otherwise
            // exchange the inner and outer circle and turn an extruded tube into a disc.
            ConstraintKind::CircleCircleDistance { a, b, circles: TwoCircles::Nested, .. } => {
                out.push((Orient::RadiusOrder(a, b), vec![*ci]));
            }
            // The circle stays on its side of the line: the distance is unsigned.
            ConstraintKind::LineCircleDistance { l, c, value, .. } => {
                if let Some(CurveKind::Circle { c: centre, .. } | CurveKind::Arc { c: centre, .. }) = s.sk.curves.get(c).map(|x| &x.kind) {
                    out.push((Orient::OfLine(*centre, l, value + s.round(c).1), vec![*ci]));
                }
            }
            // A line tangent to a circle: the circle stays on its side (away from their ends, the
            // other tangent of that direction is a diameter away; at an end they share, the other
            // tangent from the line's far end is its mirror image).
            ConstraintKind::Tangent { a, b } => {
                let (l, c) = if s.is_line(a) { (a, b) } else { (b, a) };
                if s.is_line(l)
                    && let Some(CurveKind::Circle { c: centre, .. } | CurveKind::Arc { c: centre, .. }) = s.sk.curves.get(c).map(|x| &x.kind)
                {
                    out.push((Orient::OfLine(*centre, l, s.round(c).1), vec![*ci]));
                }
            }
            _ => {}
        }
    }
    // A distance between two points on one line leaves which way along it open: the other
    // solution is the same distance back past `p`. A point is on a line as one of its ends, as a
    // point held on it, or coincident with either, read from the whole sketch (the line may be
    // fixed, solved apart from these points).
    let ends = |l: usize| line(l).map(|(a, b)| [a, b]).unwrap_or([usize::MAX; 2]);
    let mut lines_at: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
    let mut together: Vec<(usize, usize)> = Vec::new();
    if !spans.is_empty() {
        for (l, c) in s.sk.curves.iter().enumerate() {
            if let CurveKind::Line { a, b } = c.kind {
                lines_at.entry(a).or_default().push(l);
                lines_at.entry(b).or_default().push(l);
            }
        }
        for c in &s.sk.constraints {
            match c.kind {
                ConstraintKind::PointOnCurve { p, c } if line(c).is_some() => lines_at.entry(p).or_default().push(c),
                ConstraintKind::Coincident { p, q } => together.push((p, q)),
                _ => {}
            }
        }
    }
    let lines_of = |p: usize| -> Vec<usize> {
        let joined = together.iter().filter_map(|&(x, y)| {
            if x == p {
                Some(y)
            } else if y == p {
                Some(x)
            } else {
                None
            }
        });
        std::iter::once(p).chain(joined).flat_map(|x| lines_at.get(&x).into_iter().flatten().copied()).collect()
    };
    // One of the two may lie on the line by what else holds it (the mirror image of a point on
    // it, across a line square to it): where it is now, as exactly as a solve puts it.
    let lies_on = |x: usize, l: usize| {
        let ((a, b), px) = (s.line(l), s.p(x));
        let reach = 1e-7 * crate::loci::mag(a).max(crate::loci::mag(b)).max(crate::loci::mag(px)).max(1.0);
        (b - a).normalized().is_some_and(|d| d.cross(px - a).abs() <= reach)
    };
    for &(p, q, value, ci) in &spans {
        if !(free(p) || free(q)) {
            continue;
        }
        let (lp, lq) = (lines_of(p), lines_of(q));
        let both = |l: &usize| (lp.contains(l) || lies_on(p, *l)) && (lq.contains(l) || lies_on(q, *l));
        if let Some(l) = lp.iter().chain(&lq).copied().find(|l| both(l) && !(ends(*l).contains(&p) && ends(*l).contains(&q))) {
            out.push((Orient::Along(p, q, l, value), vec![ci]));
        }
    }
    // Union-find over the points these constraints name (not the whole sketch).
    let mut local: BTreeMap<usize, usize> = BTreeMap::new();
    for (p, q) in joins.iter().copied().chain(edges.iter().map(|&(p, q, _)| (p, q))) {
        for i in [p, q] {
            let n = local.len();
            local.entry(i).or_insert(n);
        }
    }
    let mut parent: Vec<usize> = (0..local.len()).collect();
    let at = |i: usize| local.get(&i).copied().unwrap_or(0);
    for &(p, q) in &joins {
        union(&mut parent, at(p), at(q));
    }
    // Each group stands for the first of its points met; it is free when any of them is.
    let mut rep: BTreeMap<usize, usize> = BTreeMap::new();
    let mut free_groups: BTreeSet<usize> = BTreeSet::new();
    let mut adj: BTreeMap<usize, BTreeMap<usize, usize>> = BTreeMap::new();
    for &(p, q, ci) in &edges {
        let [a, b] = [p, q].map(|i| {
            let r = *rep.entry(find(&mut parent, at(i))).or_insert(i);
            if free(i) {
                free_groups.insert(r);
            }
            r
        });
        if a != b {
            adj.entry(a).or_default().entry(b).or_insert(ci);
            adj.entry(b).or_default().entry(a).or_insert(ci);
        }
    }
    let mut work = 0usize;
    let mut triangles = 0usize;
    for (&a, na) in &adj {
        for (&b, &ab) in na.range(a + 1..) {
            let Some(nb) = adj.get(&b) else { continue };
            for (&c, &ac) in na.range(b + 1..) {
                work += 1;
                if work > MAX_TRIPLE_WORK || triangles >= MAX_TRIPLES {
                    return out;
                }
                if let Some(&bc) = nb.get(&c)
                    && [a, b, c].iter().any(|p| free_groups.contains(p))
                {
                    triangles += 1;
                    out.push((Orient::Turn([a, b, c]), vec![ab, bc, ac]));
                }
            }
        }
    }
    out
}

/// Dimension continuation: solve the component `sub` from `x` (its previous solved state) for
/// its changed values stepped from old to new, each sub-step from the previous solution. A
/// sub-step that fails or flips an orientation of the previous state is halved; the step
/// doubles again after one that holds. Gives up below one [`SUBSTEPS`]th of the edit or after
/// [`CONTINUATION_ITERS`] iterations. Returns the iterations and whether the new values were
/// reached; `x` holds the last sub-step's solution either way.
fn continue_values(
    sk: &Sketch,
    lay: &Layout,
    sub: &[(Block, Vec<usize>)],
    vars: &[usize],
    col: &[usize],
    x: &mut [f64],
    edit: &ValueEdit,
) -> (usize, bool) {
    #[cfg(feature = "solver-profiling")]
    profiling::count(|c| c.continuation_runs = c.continuation_runs.saturating_add(1));
    // Every sub-step lands on a sixty-fourth: the changed constraints at each, built once.
    let arena: Vec<Vec<ConstraintKind>> = (0..=SUBSTEPS).map(|j| edit.kinds_at(j)).collect();
    let mut blocks: Vec<(Block, Vec<usize>)> = sub.iter().map(|(b, v)| (copy_block(b), v.clone())).collect();
    let (mut t, mut h, mut spent) = (0, SUBSTEPS / 2, 0);
    let mut trial = x.to_vec();
    while t < SUBSTEPS && spent < CONTINUATION_ITERS {
        let next = (t + h).min(SUBSTEPS);
        if let Some(kinds) = arena.get(next) {
            edit.point_at(&mut blocks, kinds);
        }
        trial.copy_from_slice(x);
        let (its, residual) = lm_capped(sk, lay, &blocks, vars, &mut trial, col, MAX_ITERS.min(CONTINUATION_ITERS - spent));
        spent += its.max(1);
        if edit.holds(residual, &State { sk, lay, x: &trial }) {
            x.copy_from_slice(&trial);
            t = next;
            h = (2 * h).min(SUBSTEPS);
        } else if h > 1 {
            h /= 2;
        } else {
            break;
        }
    }
    (spent, t >= SUBSTEPS)
}

/// A line tangent to an arc at the arc's end `p` continues the arc's travel there, as a
/// fillet's line leaves its arc: `Some(1.0)`; turned back onto the arc, `Some(-1.0)`; `None`
/// when too short to tell. The travel runs counter-clockwise from the arc's `a` to its `b`.
fn tangent_sense(sk: &Sketch, pos: &dyn Fn(usize) -> Vec2, arc: usize, line: usize, p: usize) -> Option<f64> {
    let CurveKind::Arc { c, a, b } = sk.curves.get(arc)?.kind else { return None };
    let CurveKind::Line { a: la, b: lb } = sk.curves.get(line)?.kind else { return None };
    let far = if la == p {
        lb
    } else if lb == p {
        la
    } else {
        return None;
    };
    let outward = if p == b {
        1.0
    } else if p == a {
        -1.0
    } else {
        return None;
    };
    let along = (pos(p) - pos(c)).perp();
    let leaving = pos(far) - pos(p);
    let d = along.dot(leaving) * outward;
    (d.abs() > 1e-9 * along.len() * leaving.len()).then(|| d.signum())
}

/// An arc with lines tangent at its ends, as a solve started or left it: its sweep (counter-
/// clockwise from `a` to `b`) and each line's sense.
struct ArcSense {
    arc: usize,
    sweep: f64,
    /// (line, touch point, tangent constraint index, sense)
    lines: Vec<(usize, usize, usize, Option<f64>)>,
}

/// The arcs a solve may turn over (no arc sweep dimension of their own, not fixed, not
/// linked) with the lines tangent at their ends, read at `pos`.
fn arc_senses(sk: &Sketch, pos: &dyn Fn(usize) -> Vec2) -> Vec<ArcSense> {
    let swept: std::collections::BTreeSet<usize> = sk
        .constraints
        .iter()
        .filter(|c| !c.driven)
        .filter_map(|c| match c.kind {
            ConstraintKind::ArcSweep { c, .. } => Some(c),
            _ => None,
        })
        .collect();
    let arc =
        |i: usize| sk.curves.get(i).is_some_and(|c| matches!(c.kind, CurveKind::Arc { .. }) && !c.fixed && c.link.is_none() && !swept.contains(&i));
    let line = |i: usize| sk.curves.get(i).is_some_and(|c| matches!(c.kind, CurveKind::Line { .. }));
    let on_curve = points_on_curves(sk);
    let mut out: Vec<ArcSense> = Vec::new();
    for (ci, c) in sk.constraints.iter().enumerate().filter(|(_, c)| !c.driven) {
        let ConstraintKind::Tangent { a, b } = c.kind else { continue };
        let Some(p) = touch_point(sk, &c.kind, &on_curve) else { continue };
        let (arc, line) = if arc(a) && line(b) {
            (a, b)
        } else if arc(b) && line(a) {
            (b, a)
        } else {
            continue;
        };
        let sense = tangent_sense(sk, pos, arc, line, p);
        let entry = match out.iter().position(|e| e.arc == arc) {
            Some(k) => k,
            None => {
                let CurveKind::Arc { c, a, b } = sk.curves[arc].kind else { continue };
                let sweep = ((pos(b) - pos(c)).angle() - (pos(a) - pos(c)).angle()).rem_euclid(std::f64::consts::TAU);
                out.push(ArcSense { arc, sweep, lines: Vec::new() });
                out.len() - 1
            }
        };
        if let Some(e) = out.get_mut(entry) {
            e.lines.push((line, p, ci, sense));
        }
    }
    out
}

/// What a solve did to a filleted arc, against how it started.
enum Turn {
    /// Still the same arc between its lines.
    Kept,
    /// It ran round the other way with its lines following: the corner it rounds mirrored. Its
    /// ends swapped, it is that corner's short arc again.
    Swap,
    /// One of its two lines cut back through it: the corner mirrored, the arc did not. The
    /// arc reflected across the line that stayed (`across`) with that line's touch point
    /// (`p`) is the start to solve again from.
    Mirror { p: usize, across: usize },
    /// It looped the other way round, or a line folded back onto it: no arc of a corner.
    Over(Vec<usize>),
}

fn turn(before: &ArcSense, after: &ArcSense) -> Turn {
    let jump = (after.sweep - before.sweep).abs() > std::f64::consts::PI;
    // A line whose sense was clear and no longer is collapsed onto the arc: turned too.
    let lines: Vec<(&(usize, usize, usize, Option<f64>), bool)> = before
        .lines
        .iter()
        .filter_map(|l @ (line, p, _, was)| {
            let was = (*was)?;
            let is = after.lines.iter().find(|(m, q, ..)| (m, q) == (line, p)).map(|(.., is)| *is)?;
            Some((l, is != Some(was)))
        })
        .collect();
    let (all, any) = (lines.iter().all(|(_, f)| *f), lines.iter().any(|(_, f)| *f));
    match (jump, any, all) {
        (false, false, _) => Turn::Kept,
        (true, _, true) => Turn::Swap,
        (false, true, false) if lines.len() == 2 => {
            let Some(turned) = lines.iter().find(|(_, f)| *f).map(|(l, _)| l) else { return Turn::Kept };
            let Some(stayed) = lines.iter().find(|(_, f)| !*f).map(|(l, _)| l) else { return Turn::Kept };
            Turn::Mirror { p: turned.1, across: stayed.0 }
        }
        _ => Turn::Over(lines.iter().map(|(l, _)| l.2).collect()),
    }
}

/// The arc's ends swapped: the same circle run the other way round from the same points, so the
/// stored counter-clockwise arc is the one on the other side of its chord. `reversed` keeps the
/// as-drawn start and end.
fn swap_arc_ends(sk: &mut Sketch, arc: usize) {
    if let Some(curve) = sk.curves.get_mut(arc)
        && let CurveKind::Arc { a, b, .. } = &mut curve.kind
    {
        std::mem::swap(a, b);
        curve.reversed = !curve.reversed;
    }
}

/// The arc's centre and the touch point `p` reflected across line `across`, and its ends
/// swapped: the corner's fillet on the mirrored side.
fn mirror_arc(sk: &mut Sketch, arc: usize, p: usize, across: usize) {
    let Some(CurveKind::Arc { c, .. }) = sk.curves.get(arc).map(|c| c.kind.clone()) else { return };
    let Some(CurveKind::Line { a: la, b: lb }) = sk.curves.get(across).map(|c| c.kind.clone()) else { return };
    let (Some(pa), Some(pb)) = (sk.point(la), sk.point(lb)) else { return };
    let Some(d) = (pb - pa).normalized() else { return };
    let reflect = |q: Vec2| pa + d * (q - pa).dot(d) * 2.0 - (q - pa);
    for i in [c, p] {
        if let Some(q) = sk.point(i)
            && let Some(point) = sk.points.get_mut(i)
            && !point.fixed
        {
            point.pos = reflect(q);
        }
    }
    swap_arc_ends(sk, arc);
}

/// Every fillet of `before` is still an arc of its corner in `after` (the same sketch moved: its
/// lines keep their sense at the arc and the arc its side of its chord): what a feasible move
/// of the cursor may keep. See [`solve_sensed`].
pub fn fillets_kept(before: &Sketch, after: &Sketch) -> bool {
    let was = arc_senses(before, &|i| before.points.get(i).map(|p| p.pos).unwrap_or_default());
    let now = arc_senses(after, &|i| after.points.get(i).map(|p| p.pos).unwrap_or_default());
    was.iter().all(|b| now.iter().find(|a| a.arc == b.arc).is_none_or(|a| matches!(turn(b, a), Turn::Kept)))
}

/// The turns of every filleted arc from `before` to where `sk` is now, applying the swaps.
fn settle(sk: &mut Sketch, before: &[ArcSense]) -> Vec<(usize, Turn)> {
    let after = arc_senses(sk, &|i| sk.points.get(i).map(|p| p.pos).unwrap_or_default());
    // A swap gives the corner its arc back when its lines cut back through it. An arc whose lines
    // all leave it already rounds its corner, whatever the reference it is judged against (a
    // mirrored start) showed: swapping that one would make the fillet its complement.
    let turns: Vec<(usize, Turn)> = before
        .iter()
        .filter_map(|b| {
            after.iter().find(|a| a.arc == b.arc).map(|a| {
                let leave = !a.lines.is_empty() && a.lines.iter().all(|l| l.3 == Some(1.0));
                (b.arc, turn(b, a), leave)
            })
        })
        .filter_map(|(arc, t, leave)| match t {
            Turn::Kept => None,
            Turn::Swap if leave => None,
            t => Some((arc, t)),
        })
        .collect();
    for (arc, t) in &turns {
        if matches!(t, Turn::Swap) {
            swap_arc_ends(sk, *arc);
        }
    }
    turns
}

/// [`solve_inner`], keeping each fillet an arc of its corner: a line tangent at an arc's end
/// keeps its sense there (it leaves the arc, as it did), and the arc stays on its side of its
/// chord. Positions are compared with `reference` (an interactive move's start) or the
/// stored ones. A corner that mirrored gets its arc on the mirrored side (its ends swapped, or
/// the arc reflected across the line that stayed and solved again). A solve that would loop
/// the arc round the other way, or fold a line back onto it, is refused as a fold is: the
/// geometry stays and the tangent constraints are reported as `folded`.
fn solve_sensed(
    sk: &mut Sketch,
    hold: &Hold,
    reference: Option<&[Vec2]>,
    analysis: Analysis,
    old_values: Option<&[Option<f64>]>,
    budget: &mut Budget,
) -> SolveReport {
    let stored: Vec<Vec2> = sk.points.iter().map(|p| p.pos).collect();
    let pos = |i: usize| reference.and_then(|r| r.get(i)).or_else(|| stored.get(i)).copied().unwrap_or_default();
    let before = arc_senses(sk, &pos);
    if before.is_empty() {
        return solve_inner(sk, hold, reference, analysis, old_values, budget);
    }
    let start = sk.clone();
    let mut report = solve_inner(sk, hold, reference, analysis, old_values, budget);
    if !report.ok() {
        return report;
    }
    let mut turns = settle(sk, &before);
    let mirrors: Vec<(usize, usize, usize)> =
        turns.iter().filter_map(|(arc, t)| if let Turn::Mirror { p, across } = t { Some((*arc, *p, *across)) } else { None }).collect();
    if !mirrors.is_empty() {
        let solved = sk.clone();
        for (arc, p, across) in &mirrors {
            mirror_arc(sk, *arc, *p, *across);
        }
        let again = solve_inner(sk, hold, reference, analysis, old_values, budget);
        let again_turns = if again.ok() { settle(sk, &before) } else { Vec::new() };
        if again.ok() && again_turns.is_empty() {
            return again;
        }
        *sk = solved;
    }
    let over: Vec<usize> = turns
        .iter_mut()
        .flat_map(|(_, t)| match t {
            Turn::Over(cs) => std::mem::take(cs),
            Turn::Mirror { .. } => Vec::new(),
            _ => Vec::new(),
        })
        .collect();
    let mirrored_still: Vec<usize> = turns
        .iter()
        .filter(|(_, t)| matches!(t, Turn::Mirror { .. }))
        .flat_map(|(arc, _)| before.iter().find(|b| b.arc == *arc).map(|b| b.lines.iter().map(|l| l.2).collect::<Vec<_>>()).unwrap_or_default())
        .collect();
    let folded: Vec<String> = over.into_iter().chain(mirrored_still).filter_map(|ci| sk.constraints.get(ci).map(|c| c.id.clone())).collect();
    if folded.is_empty() {
        return report;
    }
    *sk = start;
    report.status = SolveStatus::Failed;
    for id in folded {
        if !report.failing.contains(&id) {
            report.failing.push(id.clone());
        }
        if !report.folded.contains(&id) {
            report.folded.push(id);
        }
    }
    report
}

fn solve_inner(
    sk: &mut Sketch,
    hold: &Hold,
    reference: Option<&[Vec2]>,
    analysis: Analysis,
    old_values: Option<&[Option<f64>]>,
    budget: &mut Budget,
) -> SolveReport {
    #[cfg(feature = "solver-profiling")]
    let _timer = profiling::timer(Phase::Solve);
    #[cfg(feature = "solver-profiling")]
    profiling::count(|c| c.solve_calls = c.solve_calls.saturating_add(1));
    sk.prune_patterns();
    sk.refresh_pattern_shapes();
    place_pierced_points(sk);
    let mut orientation_before = Vec::new();
    for constraint in &sk.constraints {
        if !constraint.driven
            && let ConstraintKind::ArcSweep { c, value } = constraint.kind
            && value.is_finite()
            && let Some(curve) = sk.curves.get_mut(c)
            && let CurveKind::Arc { a, b, .. } = &mut curve.kind
            && curve.reversed != (value < 0.0)
        {
            orientation_before.push((c, *a, *b, curve.reversed));
            std::mem::swap(a, b);
            curve.reversed = value < 0.0;
        }
    }
    let lay = layout(sk, hold);
    let mut x = initial_x(sk, &lay);
    let x0 = x.clone();
    let on_curve = points_on_curves(sk);
    // Start from the constructed positions of the points the constraints pin down (see
    // `construct`); LM still verifies every constraint from there. A touching placement does
    // not pin a point down well and is left where it is (`Placement::anchors`). `unseeded`
    // keeps the start the solve would have without the seed, for the variables the seed moved:
    // a component the seeded start cannot solve is solved again from there, and only if the
    // seed moved its start.
    let mut unseeded = None;
    // Per variable: the seed constructed it (a candidate to stay where it was put, see `pinned`).
    let mut constructed = vec![false; lay.n];
    if crate::construct::switch::seed_on() {
        let given: Vec<bool> = lay.pvar.iter().map(Option::is_none).collect();
        // A drag step solves against its reference and moves only held points. Any other solve
        // applies edits: also the one after linked geometry moved, whose reference is the
        // stored state.
        let edits = reference.is_none() || old_values.is_some();
        #[cfg(feature = "solver-profiling")]
        let seed_timer = profiling::timer(Phase::Seed);
        let seeded = crate::construct::seed(sk, &given, reference, edits, &on_curve, budget);
        #[cfg(feature = "solver-profiling")]
        drop(seed_timer);
        for (i, (at, how)) in seeded.pos.iter().zip(&seeded.placed_by).enumerate() {
            if let (Some(at), Some(how), Some(v)) = (at, how, lay.pvar.get(i).copied().flatten())
                && how.anchors()
            {
                set_point(&mut x, v, *at);
                // A floated cluster's pose is a guess at freedom the constraints leave: LM's
                // start, never pinned.
                if how.builds()
                    && let Some(c) = constructed.get_mut(v..v + 2)
                {
                    c.fill(true);
                }
            }
        }
        for (r, v) in seeded.radius.iter().zip(&lay.rvar) {
            if let (Some(r), Some(v)) = (r, v)
                && let Some(slot) = x.get_mut(*v)
            {
                *slot = *r;
                if let Some(c) = constructed.get_mut(*v) {
                    *c = true;
                }
            }
        }
        if x != x0 {
            let mut plain = x0.clone();
            nudge_line_angles(sk, &lay, &mut plain);
            unseeded = Some(plain);
        }
    }
    nudge_line_angles(sk, &lay, &mut x);

    // The blocks, and per block whether it reads a constant point.
    let (blocks, reads_constant) = build_blocks(sk, &lay, &on_curve);

    carry_with_seeded(&mut x, &x0, &constructed, &blocks, &lay);
    // The plain start, for the variables whose start the seed (or carrying along it) moved.
    let unseeded = unseeded.map(|plain: Vec<f64>| plain.into_iter().zip(&x).map(|(p, s)| (p != *s).then_some(p)).collect::<Vec<_>>());

    // Connected components over variables.
    let mut parent: Vec<usize> = (0..lay.n).collect();
    for (_, vars) in &blocks {
        if let Some(&first) = vars.first() {
            for &v in vars.iter().skip(1) {
                union(&mut parent, first, v);
            }
        }
    }
    let mut comps: Vec<(usize, Vec<usize>, Vec<usize>)> = Vec::new(); // (root, vars, block idx)
    let mut comp_of: std::collections::HashMap<usize, usize> = std::collections::HashMap::new();
    for v in 0..lay.n {
        let r = find(&mut parent, v);
        match comp_of.get(&r) {
            Some(&k) => {
                if let Some(c) = comps.get_mut(k) {
                    c.1.push(v);
                }
            }
            None => {
                comp_of.insert(r, comps.len());
                comps.push((r, vec![v], Vec::new()));
            }
        }
    }
    let mut constant_blocks = Vec::new();
    for (bi, (_, vars)) in blocks.iter().enumerate() {
        match vars.first() {
            Some(&v) => {
                let r = find(&mut parent, v);
                if let Some(c) = comp_of.get(&r).and_then(|k| comps.get_mut(*k)) {
                    c.2.push(bi);
                }
            }
            None => constant_blocks.push(bi),
        }
    }
    // Column of each variable in the system being solved or analysed (usize::MAX outside it).
    let mut col = vec![usize::MAX; lay.n];
    // Only success matters to a status-only solve: a component LM cannot solve is left as soon
    // as the iteration stalls (see `STALL_ITERS`). It fails either way, and a failed solve
    // leaves the geometry as it was.
    let give_up = analysis == Analysis::StatusOnly;

    let mut iterations = 0;
    let mut continuations = 0;
    let mut folded: Vec<String> = Vec::new();
    let all_blocks = blocks;
    let oversized = |vars: &[usize]| vars.len() > MAX_COMPONENT_VARS;
    #[cfg(feature = "solver-profiling")]
    profiling::count(|c| {
        c.components = c.components.saturating_add(comps.len() as u64);
        c.oversized_components = c.oversized_components.saturating_add(comps.iter().filter(|(_, v, b)| !b.is_empty() && oversized(v)).count() as u64);
        c.constructed_variables = c.constructed_variables.saturating_add(constructed.iter().filter(|v| **v).count() as u64);
    });
    let blocks_of = |bis: &mut dyn Iterator<Item = usize>| -> Vec<(Block, Vec<usize>)> {
        bis.filter_map(|bi| all_blocks.get(bi).map(|(b, v)| (copy_block(b), v.clone()))).collect()
    };
    for (_, vars, bis) in &comps {
        if bis.is_empty() || oversized(vars) {
            continue;
        }
        let sub = blocks_of(&mut bis.iter().copied());
        let start: Vec<f64> = vars.iter().filter_map(|v| x.get(*v).copied()).collect();
        let mut residual = max_abs(&system(sk, &lay, &sub, &mut x, false).0);
        // Already solved (by the seed, or before): nothing to iterate.
        if !(residual < TOL) {
            columns(&mut col, vars, vars);
            // What the seed constructed and the constraints pin down stays where the seed put it
            // (see `pinned`); LM solves the rest with those values as constants.
            let (mut pinned_failed, mut solved) = (false, false);
            if vars.iter().any(|v| constructed.get(*v).copied().unwrap_or(false)) {
                let candidate = |v: usize| constructed.get(v).copied().unwrap_or(false);
                let pin = pinned(sk, &lay, &sub, vars, &mut x, &candidate, Pin::Verified);
                if pin.contains(&true) {
                    let rest = unpinned(vars, &pin, None);
                    let rest_blocks = blocks_reading(&sub, &rest);
                    columns(&mut col, &rest, vars);
                    let (its, r) = if rest.is_empty() { (0, 0.0) } else { lm_in(sk, &lay, &rest_blocks, &rest, &mut x, &col, budget, give_up) };
                    iterations += its;
                    residual = r;
                    solved = residual < ACCEPT;
                    if !solved {
                        // The rest cannot be solved with the pinned values: the whole component is.
                        for (&v, s0) in vars.iter().zip(&start) {
                            if let Some(s) = x.get_mut(v) {
                                *s = *s0;
                            }
                        }
                        columns(&mut col, vars, vars);
                        pinned_failed = true;
                    }
                }
            }
            // A seeded start can leave LM stuck where the plain start solves (a partly
            // constructed component): the seeded solution is kept whenever it solves, otherwise a
            // component the seed touched is solved again from where it would have started without
            // the seed. After a failed pinned solve, the whole component goes straight to that
            // start (the seeded one is where the pinned solve failed), or to its own start when
            // the seed did not move it.
            let reseeded = unseeded.as_ref().filter(|plain| vars.iter().any(|v| plain.get(*v).is_some_and(Option::is_some)));
            if !(solved || pinned_failed && reseeded.is_some()) {
                let (its, r) = lm_in(sk, &lay, &sub, vars, &mut x, &col, budget, give_up);
                iterations += its;
                residual = r;
            }
            if !(residual < ACCEPT)
                && let Some(plain) = reseeded
            {
                #[cfg(feature = "solver-profiling")]
                profiling::count(|c| c.plain_start_retries = c.plain_start_retries.saturating_add(1));
                for (&v, s0) in vars.iter().zip(&start) {
                    if let Some(s) = x.get_mut(v) {
                        *s = plain.get(v).copied().flatten().unwrap_or(*s0);
                    }
                }
                let (its, r) = lm_in(sk, &lay, &sub, vars, &mut x, &col, budget, give_up);
                iterations += its;
                residual = r;
            }
        }
        // Continuation (below) solves the whole component: the pinned values belong to the new
        // values, not to the ones it steps through.
        columns(&mut col, vars, vars);
        // After an edit of driving values from a solved state, a component the one-jump solve
        // left unsolved, or turned over (an orientation of that state flipped), is solved by
        // continuation from there. Its result replaces the one-jump result only when it solves
        // and keeps every orientation; a solved result that still flips one is refused.
        if let Some(old) = old_values
            && let Some(edit) = ValueEdit::of(&State { sk, lay: &lay, x: &x0 }, &sub, old)
            && !edit.holds(residual, &State { sk, lay: &lay, x: &x })
            && edit.starts_solved(&State { sk, lay: &lay, x: &x0 }, &sub)
        {
            if edit.continuable() {
                continuations += 1;
                // This component's variables restart from the previous state; the components
                // solved before it keep their solutions (LM here touches only `vars`).
                let mut from = x.clone();
                for &v in vars {
                    if let (Some(s), Some(s0)) = (from.get_mut(v), x0.get(v)) {
                        *s = *s0;
                    }
                }
                let (its, mut done) = continue_values(sk, &lay, &sub, vars, &col, &mut from, &edit);
                iterations += its;
                if !done {
                    // The last sub-step's solution, solved for the new values in one jump.
                    let (its, r) = lm_in(sk, &lay, &sub, vars, &mut from, &col, budget, false);
                    iterations += its;
                    done = edit.holds(r, &State { sk, lay: &lay, x: &from });
                }
                if done {
                    x = from;
                    residual = 0.0;
                }
            }
            if residual < ACCEPT {
                let now = State { sk, lay: &lay, x: &x };
                for ci in edit.flipped(&now) {
                    if let Some(c) = sk.constraints.get(*ci)
                        && !folded.contains(&c.id)
                    {
                        folded.push(c.id.clone());
                    }
                }
            }
        }
    }

    // Final residuals and analysis, component by component (the Jacobian is block diagonal:
    // its rank is the sum of the components' ranks).
    #[cfg(feature = "solver-profiling")]
    let _analysis_timer = profiling::timer(Phase::Analysis);
    let mut max_residual = 0.0_f64;
    let mut failing: Vec<String> = Vec::new();
    let mut det = vec![false; lay.n];
    let mut rank = 0;
    let mut redundant: Vec<String> = Vec::new();
    let mut degenerate = false;
    // Tangents whose touch-free form is violated (or whose round curve collapsed): named in
    // `failing` only when the sketch failed anyway, so a sketch inside the acceptance tolerance
    // is never `Solved` with a constraint in `failing`.
    let mut named: Vec<String> = Vec::new();
    // A component too large to solve is a failure, not an allocation.
    let too_large = comps.iter().filter(|(_, vars, bis)| !bis.is_empty() && oversized(vars)).map(|(_, vars, _)| vars.len()).max();
    if too_large.is_some() {
        max_residual = f64::MAX;
    }
    let mut check = |r: &[f64], owner: &[usize], blocks: &[(Block, Vec<usize>)], failing: &mut Vec<String>| {
        max_residual = max_residual.max(max_abs(r));
        for (row, v) in r.iter().enumerate() {
            if !(v.abs() < ACCEPT)
                && let Some((Block::User(ci, _) | Block::TangentAt(ci, _, _), _)) = owner.get(row).and_then(|bi| blocks.get(*bi))
                && let Some(c) = sk.constraints.get(*ci)
                && !failing.contains(&c.id)
            {
                failing.push(c.id.clone());
            }
        }
    };
    for (_, vars, bis) in &comps {
        if oversized(vars) {
            continue;
        }
        let sub = blocks_of(&mut bis.iter().copied());
        if sub.is_empty() {
            continue;
        }
        let (r, _, owner) = system(sk, &lay, &sub, &mut x, false);
        check(&r, &owner, &sub, &mut failing);
        // A tangency read at its touch point can hold there while the curves are not tangent (the
        // touch point is not on the line, or not on the round curve): that failure is named by the
        // constraint that ties the point, and the tangent is named as well when the touch-free
        // form (distance from the centre equals the radius) is violated. A tangent whose round
        // curve has collapsed to a point holds trivially and is a degenerate answer: it fails.
        let now = State { sk, lay: &lay, x: &x };
        for (b, _) in &sub {
            let (Block::User(ci, k) | Block::TangentAt(ci, k, _)) = b else { continue };
            // An angle requires two directions. A nearly collapsed line can satisfy its
            // horizontal/vertical residual within tolerance while pointing anywhere, so
            // the angle alone must not turn that degenerate pose into a solved sketch.
            // Compare against the input length, so an already short reference still solves.
            let angular_lines = match **k {
                ConstraintKind::Angle { a, b, .. } => Some([a, b]),
                ConstraintKind::LineAngle { l, .. } => Some([l, l]),
                _ => None,
            };
            if angular_lines.is_some_and(|lines| {
                lines.iter().any(|&l| {
                    let (a, b) = now.line(l);
                    let original = match sk.curves.get(l).map(|c| &c.kind) {
                        Some(CurveKind::Line { a, b }) => sk.point(*a).zip(sk.point(*b)).map_or(1.0, |(a, b)| a.dist(b)),
                        _ => 1.0,
                    };
                    a.dist(b) < ACCEPT * original
                })
            }) {
                if let Some(c) = sk.constraints.get(*ci)
                    && !failing.contains(&c.id)
                {
                    failing.push(c.id.clone());
                }
                degenerate = true;
            }
            let ConstraintKind::Tangent { a: ta, b: tb } = **k else { continue };
            let Some(c) = sk.constraints.get(*ci) else { continue };
            let mut touch_free = Vec::new();
            if matches!(b, Block::TangentAt(..)) {
                residuals(&now, k, &mut touch_free);
            }
            let collapsed = [ta, tb].iter().any(|&cv| !now.is_line(cv) && !now.is_freeform(cv) && now.radius_of(cv) < ACCEPT);
            if (collapsed || touch_free.iter().any(|v| !(v.abs() < ACCEPT))) && !named.contains(&c.id) {
                named.push(c.id.clone());
            }
            degenerate |= collapsed;
        }
        if analysis == Analysis::StatusOnly {
            continue;
        }
        // The rank analysis runs on what `pinned` leaves: see there for why that is exact.
        let floating = bis.iter().all(|bi| !reads_constant.get(*bi).copied().unwrap_or(true));
        let pin = match vars.iter().copied().find(|v| lay.is_point(*v)) {
            Some(anchor) if floating => Pin::Floating(anchor),
            _ => Pin::Anchored,
        };
        let pin_flags = pinned(sk, &lay, &sub, vars, &mut x, &|_| true, pin);
        let rest = unpinned(vars, &pin_flags, pin.anchor());
        columns(&mut col, &rest, vars);
        let (_, j, _) = local_system(sk, &lay, &blocks_reading(&sub, &rest), &mut x, &col, rest.len());
        let (rest_det, rest_rank) = if j.rows > 0 { determined_vars(&j, 1e-7) } else { (vec![false; rest.len()], 0) };
        let comp_rank = pin_flags.iter().filter(|p| **p).count() + rest_rank;
        rank += comp_rank;
        // More rows than rank: some constraint may be implied by the others.
        if analysis == Analysis::Full && r.len() > comp_rank && vars.len() <= redundancy::MAX_REDUNDANCY_VARS {
            let (dependent, _) = redundancy::dependent_blocks(sk, &lay, &sub, vars, &mut x, None);
            for ((b, _), d) in sub.iter().zip(dependent) {
                if d && let Some(c) = redundancy::block_constraint(b).and_then(|ci| sk.constraints.get(ci))
                    && !redundant.contains(&c.id)
                {
                    redundant.push(c.id.clone());
                }
            }
        }
        for (&v, pinned) in vars.iter().zip(&pin_flags) {
            let flag = match rest.binary_search(&v) {
                Ok(k) => rest_det.get(k).copied().unwrap_or(false),
                Err(_) => *pinned,
            };
            // A floating component's translation moves every point.
            let moves = matches!(pin, Pin::Floating(_)) && lay.is_point(v);
            if let Some(slot) = det.get_mut(v) {
                *slot = flag && !moves;
            }
        }
        #[cfg(test)]
        {
            columns(&mut col, vars, vars);
            let (_, j, _) = local_system(sk, &lay, &sub, &mut x, &col, vars.len());
            let reduced: Vec<bool> = vars.iter().map(|v| det.get(*v).copied().unwrap_or(false)).collect();
            assert_dense_agrees(&j, comp_rank, &reduced);
        }
    }
    let consts = blocks_of(&mut constant_blocks.iter().copied());
    if !consts.is_empty() {
        let (r, _, owner) = system(sk, &lay, &consts, &mut x, false);
        check(&r, &owner, &consts, &mut failing);
    }
    if degenerate {
        max_residual = max_residual.max(1.0);
    }
    // Weld the whole connected closure graph, preserving every immutable node.
    // Validate the actual prospective geometry before accepting a numerical solve.
    let has_periodic = sk.curves.iter().any(|c| matches!(c.kind, CurveKind::Spline { periodic: true, .. }));
    let periodic_positions = if has_periodic {
        let state = State { sk, lay: &lay, x: &x };
        let mut positions = (0..sk.points.len()).map(|i| state.p(i)).collect::<Vec<_>>();
        let mut parent = (0..positions.len()).collect::<Vec<_>>();
        for curve in &sk.curves {
            if let CurveKind::Spline { pts, periodic: true, .. } = &curve.kind
                && let (Some(a), Some(b)) = (pts.first(), pts.last())
                && *a < parent.len()
                && *b < parent.len()
            {
                union(&mut parent, *b, *a);
            }
        }
        let mut representatives = std::collections::BTreeMap::new();
        let mut valid = true;
        for i in 0..positions.len() {
            let root = find(&mut parent, i);
            if let Some(previous) = representatives.get(&root).copied() {
                let fixed = |p| lay.pvar.get(p).is_some_and(Option::is_none);
                if fixed(i) && fixed(previous) && positions[i] != positions[previous] {
                    valid = false;
                }
                if fixed(i) && !fixed(previous) {
                    representatives.insert(root, i);
                }
            } else {
                representatives.insert(root, i);
            }
        }
        for (i, position) in positions.iter_mut().enumerate() {
            if let Some(index) = representatives.get(&find(&mut parent, i)) {
                *position = state.p(*index);
            }
        }
        for curve in &sk.curves {
            if let CurveKind::Spline { pts, control, degree, periodic: true, .. } = &curve.kind {
                let points = pts.iter().map(|i| positions.get(*i).copied()).collect::<Option<Vec<_>>>();
                if *control || *degree != 3 || points.as_ref().is_none_or(|p| crate::periodic::validate_periodic_points(p).is_err()) {
                    valid = false;
                }
            }
        }
        if !valid {
            max_residual = max_residual.max(1.0);
            None
        } else {
            Some(positions)
        }
    } else {
        None
    };
    let status = if max_residual < ACCEPT { SolveStatus::Solved } else { SolveStatus::Failed };
    if status == SolveStatus::Failed {
        for id in named {
            if !failing.contains(&id) {
                failing.push(id);
            }
        }
    }
    for id in &folded {
        if !failing.contains(id) {
            failing.push(id.clone());
        }
    }
    let use_x = if status == SolveStatus::Solved { &x } else { &x0 };
    // Write back.
    for (i, p) in sk.points.iter_mut().enumerate() {
        if let Some(v) = lay.pvar.get(i).copied().flatten() {
            p.pos = Vec2::new(use_x.get(v).copied().unwrap_or(p.pos.x), use_x.get(v + 1).copied().unwrap_or(p.pos.y));
        }
    }
    for (i, c) in sk.curves.iter_mut().enumerate() {
        if let (CurveKind::Circle { r, .. } | CurveKind::Ellipse { r, .. }, Some(v)) = (&mut c.kind, lay.rvar.get(i).copied().flatten()) {
            *r = use_x.get(v).copied().unwrap_or(*r).abs().max(1e-9);
        }
    }
    if status == SolveStatus::Solved
        && let Some(positions) = periodic_positions
    {
        for (point, position) in sk.points.iter_mut().zip(positions) {
            point.pos = position;
        }
    }
    if status == SolveStatus::Failed {
        for (ci, a_before, b_before, reversed) in orientation_before.into_iter().rev() {
            if let Some(curve) = sk.curves.get_mut(ci)
                && let CurveKind::Arc { a, b, .. } = &mut curve.kind
            {
                *a = a_before;
                *b = b_before;
                curve.reversed = reversed;
            }
        }
    }
    let vdet = |v: Option<usize>| v.is_none_or(|v| det.get(v).copied().unwrap_or(false));
    let pdet = |p: usize| match lay.pvar.get(p).copied().flatten() {
        Some(v) => vdet(Some(v)) && vdet(Some(v + 1)),
        None => true,
    };
    refresh_driven_dimensions(sk);
    let (dof, point_determined, curve_determined) = match analysis {
        Analysis::Full | Analysis::Freedom => (
            lay.n.saturating_sub(rank),
            (0..sk.points.len()).map(pdet).collect(),
            sk.curves.iter().enumerate().map(|(i, c)| c.kind.point_ids().into_iter().all(pdet) && vdet(lay.rvar.get(i).copied().flatten())).collect(),
        ),
        Analysis::StatusOnly => (0, Vec::new(), Vec::new()),
    };
    SolveReport {
        status,
        dof,
        iterations,
        max_residual: if max_residual.is_finite() { max_residual } else { f64::MAX },
        failing,
        folded,
        continuations,
        point_determined,
        curve_determined,
        redundant,
        oversized: too_large,
    }
}

/// Geometry can also be finalized by feasible cursor motion, without another solve.
/// Both paths must measure reference dimensions from the pose they publish.
fn refresh_driven_dimensions(sk: &mut Sketch) {
    let fixed_lay = Layout { pvar: vec![None; sk.points.len()], rvar: vec![None; sk.curves.len()], n: 0, points: 0, slide: Vec::new() };
    let measured: Vec<Option<f64>> =
        sk.constraints.iter().map(|c| if c.driven { measure(&State { sk, lay: &fixed_lay, x: &[] }, &c.kind) } else { None }).collect();
    for (c, m) in sk.constraints.iter_mut().zip(measured) {
        if let Some(v) = m
            && v.is_finite()
        {
            c.kind.set_value(v);
        }
    }
}

#[cfg(test)]
mod continuation_unit_tests {
    use super::*;

    #[test]
    fn angles_step_the_short_way_round() {
        let line = ConstraintKind::LineAngle { l: 0, value: 0.0 };
        let (old, new) = (179f64.to_radians(), (-179f64).to_radians());
        let half = value_at(&line, old, new, 0.5);
        assert!((half - 180f64.to_radians()).abs() < 1e-12, "{}", half.to_degrees());
        let first = value_at(&line, old, new, 1.0 / SUBSTEPS as f64);
        assert!((first - old).abs() < 2f64.to_radians() / 32.0, "a sixty-fourth of 2°, not of 358°");
        assert_eq!(value_at(&line, old, new, 1.0), new);
        let distance = ConstraintKind::Distance { p: 0, q: 1, value: 0.0 };
        assert_eq!(value_at(&distance, 10.0, 20.0, 0.5), 15.0);
    }

    #[test]
    fn a_sweep_changing_sign_is_not_stepped() {
        let sweep = ConstraintKind::ArcSweep { c: 0, value: 0.0 };
        assert!(!steppable(&sweep, 1.0, -1.0));
        assert!(steppable(&sweep, 1.0, 2.0));
        assert!(steppable(&ConstraintKind::LineAngle { l: 0, value: 0.0 }, 3.0, -3.0));
    }

    #[test]
    fn only_clear_orientations_are_kept() {
        // A triangle flat to solver noise has a side by the seed's test but none to keep.
        let mut sk = Sketch::new();
        let a = sk.add_point(Vec2::new(0.0, 0.0), None).unwrap();
        let b = sk.add_point(Vec2::new(40.0, 0.0), None).unwrap();
        let c = sk.add_point(Vec2::new(20.0, 1e-6), None).unwrap();
        let lay = Layout { pvar: vec![None; sk.points.len()], rvar: vec![None; sk.curves.len()], n: 0, points: 0, slide: Vec::new() };
        let turn = Orient::Turn([a, b, c]);
        let state =
            |sk: &Sketch| (orientation(&State { sk, lay: &lay, x: &[] }, turn), reference_orientation(&State { sk, lay: &lay, x: &[] }, turn));
        assert_eq!(state(&sk), (Some(1.0), None));
        sk.points[c].pos = Vec2::new(20.0, 0.1);
        assert_eq!(state(&sk), (Some(1.0), Some(1.0)));
        // A side offset well below its dimension's size is no reference either.
        let side = Orient::SideX(a, c, 20.0);
        sk.points[c].pos = Vec2::new(1e-6, 5.0);
        assert_eq!(reference_orientation(&State { sk: &sk, lay: &lay, x: &[] }, side), None);
    }

    #[test]
    fn offsets_have_a_side() {
        let mut sk = Sketch::new();
        let p = sk.add_point(Vec2::new(0.0, 0.0), None).unwrap();
        let q = sk.add_point(Vec2::new(10.0, 5.0), None).unwrap();
        let r = sk.add_point(Vec2::new(0.0, 10.0), None).unwrap();
        let l = sk.add_line(Vec2::new(-5.0, -5.0), Vec2::new(5.0, -5.0), None, None, None).unwrap();
        let lay = Layout { pvar: vec![None; sk.points.len()], rvar: vec![None; sk.curves.len()], n: 0, points: 0, slide: Vec::new() };
        let sign = |sk: &Sketch, o: Orient| orientation(&State { sk, lay: &lay, x: &[] }, o);
        let checks = [Orient::SideX(p, q, 10.0), Orient::SideY(p, q, 5.0), Orient::OfLine(q, l, 10.0), Orient::Turn([p, q, r])];
        let before: Vec<_> = checks.iter().map(|o| sign(&sk, *o)).collect();
        assert!(before.iter().all(Option::is_some), "{before:?}");
        // q mirrored through p and below the line: every side and the turn flip.
        sk.points[q].pos = Vec2::new(-10.0, -15.0);
        let after: Vec<_> = checks.iter().map(|o| sign(&sk, *o)).collect();
        for (b, a) in before.iter().zip(&after) {
            assert_eq!(b.zip(*a).map(|(b, a)| b == a), Some(false), "{before:?} {after:?}");
        }
        // On the line: no side to tell.
        sk.points[q].pos = Vec2::new(0.0, -5.0);
        assert_eq!(sign(&sk, Orient::OfLine(q, l, 10.0)), None);
    }
}

#[cfg(test)]
mod typed_dimension_tests {
    use super::*;

    #[test]
    fn failed_signed_sweep_restores_arc_orientation_and_coordinates() {
        let mut sk = Sketch::new();
        let c = sk.add_arc(Vec2::ZERO, Vec2::new(10.0, 0.0), Vec2::new(0.0, 10.0), [Some(0), None, None], None).unwrap();
        let id = sk.add_constraint(ConstraintKind::ArcSweep { c, value: std::f64::consts::FRAC_PI_2 }, None).unwrap();
        sk.curves[c].fixed = true;
        assert!(solve(&mut sk).ok());
        let before = sk.curves.clone();
        let points = sk.points.clone();
        sk.constraints.iter_mut().find(|constraint| constraint.id == id).unwrap().kind.set_value(-std::f64::consts::FRAC_PI_2);
        assert!(!solve(&mut sk).ok());
        assert_eq!(sk.curves, before);
        assert_eq!(sk.points, points);
    }

    /// A constraint read on a curve of the wrong kind (a midpoint of an arc, pushed past
    /// validation) reads constants for it: its component is tied to them, not floating, and the
    /// pinned analysis agrees with the dense one (checked in every test solve).
    #[test]
    fn a_curve_read_as_another_kind_ties_its_component() {
        let mut sk = Sketch::new();
        let arc = sk.add_arc(Vec2::new(5.0, 5.0), Vec2::new(15.0, 5.0), Vec2::new(5.0, 15.0), [None, None, None], None).unwrap();
        let p = sk.add_point(Vec2::new(3.0, 1.0), None).unwrap();
        sk.constraints.push(crate::model::Constraint {
            id: "m".into(),
            kind: ConstraintKind::Midpoint { p, l: arc },
            param: None,
            driven: false,
            text: None,
        });
        let rep = solve(&mut sk);
        assert!(rep.ok(), "{rep:?}");
        assert!(rep.point_determined[p], "the midpoint of the constant line: {rep:?}");
        assert_eq!(rep.dof, 5, "the arc's centre and ends, less its equal radii: {rep:?}");
    }

    #[test]
    fn a_status_only_solve_places_the_geometry_as_a_full_one() {
        let mut sk = Sketch::new();
        let l = sk.add_line(Vec2::ZERO, Vec2::new(10.0, 3.0), Some(0), None, None).unwrap();
        sk.add_constraint(ConstraintKind::LineAngle { l, value: 0.5 }, None).unwrap();
        let mut quick = sk.clone();
        let full = solve(&mut sk);
        let status = solve_with(&mut quick, &Hold::default(), None, Analysis::StatusOnly, None);
        assert!(full.ok() && status.ok());
        assert_eq!(quick, sk);
        assert_eq!(full.dof, 1, "the end slides along the line");
        assert_eq!((status.dof, status.point_determined.len(), status.curve_determined.len()), (0, 0, 0));
    }

    #[test]
    fn signed_dimensions_validate_kinds_values_and_survive_curve_removal() {
        let mut sk = Sketch::new();
        let l = sk.add_line(Vec2::ZERO, Vec2::new(10.0, 10.0), Some(0), None, None).unwrap();
        assert!(sk.add_constraint(ConstraintKind::ArcSweep { c: l, value: 1.0 }, None).is_err());
        assert!(sk.add_constraint(ConstraintKind::LineAngle { l, value: f64::NAN }, None).is_err());
        sk.add_constraint(ConstraintKind::LineAngle { l, value: -std::f64::consts::FRAC_PI_4 }, None).unwrap();
        assert!(solve(&mut sk).ok());
        let CurveKind::Line { a, b } = sk.curves[l].kind else { panic!("line") };
        let direction = sk.points[b].pos - sk.points[a].pos;
        assert!((direction.angle() + std::f64::consts::FRAC_PI_4).abs() < 1e-7);
        sk.remove_curves(&[l]);
        assert!(sk.constraints.is_empty());
    }

    /// One connected component is solved as a dense system, so its variable count sets the
    /// allocation: 10,000 chained points are 20,000 variables and a 3.2 GB matrix. The solve
    /// has to report failure instead of asking for the memory, because an allocation failure
    /// aborts the process where a failed solve does not.
    #[test]
    fn components_too_large_to_solve_fail_instead_of_allocating() {
        let mut sk = Sketch::new();
        let mut previous = 0;
        for i in 1..10_000 {
            let p = sk.add_point(Vec2::new(0.001 * i as f64, 0.0), None).unwrap();
            sk.add_constraint(ConstraintKind::Coincident { p: previous, q: p }, None).unwrap();
            previous = p;
        }
        let before = sk.points.clone();
        let t = std::time::Instant::now();
        let report = solve(&mut sk);
        assert_eq!(report.status, SolveStatus::Failed);
        // Geometry is left as it was.
        assert_eq!(sk.points, before);
        assert!(t.elapsed() < std::time::Duration::from_secs(10), "took {:?}", t.elapsed());
    }

    /// A sketch whose components each stay under the cap still solves.
    #[test]
    fn many_small_components_still_solve() {
        let mut sk = Sketch::new();
        for i in 0..200 {
            let a = sk.add_point(Vec2::new(i as f64, 0.0), None).unwrap();
            let b = sk.add_point(Vec2::new(i as f64, 5.0), None).unwrap();
            let l = sk.add_line_pts(a, b, None).unwrap();
            sk.add_constraint(ConstraintKind::Vertical { l }, None).unwrap();
        }
        assert!(solve(&mut sk).ok());
    }
}

#[cfg(test)]
mod touch_gap_tests {
    use super::touch_gap;

    /// #11535: an open curve that touches the other at its end (the gap y = 9t^2 - 8t^3 starts at
    /// zero with zero slope, and has its interior maximum 1.63 further on) has residual zero.
    #[test]
    fn an_open_curve_touching_at_its_end_has_no_residual() {
        let gaps: Vec<f64> = (0..=100).map(|i| f64::from(i) / 100.0).map(|t| 9.0 * t * t - 8.0 * t * t * t).collect();
        assert!(touch_gap(&gaps, false).abs() < 1e-12);
    }

    /// A crossing's zero, with a bigger extremum beside it, is not a touch.
    #[test]
    fn a_crossing_is_not_a_touch() {
        let gaps: Vec<f64> = (0..=100).map(|i| (f64::from(i) / 100.0 - 0.5) * 4.0 + 0.2 * (f64::from(i) / 8.0).sin()).collect();
        assert!(touch_gap(&gaps, false).abs() > 0.5);
    }
}