use std::collections::{BTreeMap, BTreeSet, HashMap};
use std::time::Instant;

use bone_solver::{
    ConstraintSystem, CurveRadius, DofConfig, DofReport, LineHandle, NewtonConfig, PointHandle,
    Residual, SolverError, analyze_dof, analyze_dof_at, decompose, dedup_preserving_order,
    minimal_unsatisfiable_subset, solve_newton_decomposed,
};
use bone_types::{
    Angle, BudgetCeiling, DegreesOfFreedom, Length, Parameter, ParameterIndex, Point2,
    ResidualIndex, SketchDimensionId, SketchEntityId, SketchItemId, SketchRelationId, SketchStatus,
    millimeter, radian,
};

use super::{
    DimensionKind, DimensionValue, Sketch, SketchDimension, SketchEntity, SketchEntityKind,
    SketchRelation,
};

#[derive(Debug, Clone, PartialEq, thiserror::Error)]
pub enum DragError {
    #[error("dragged entity {0:?} is not a Point")]
    NotAPoint(SketchEntityId),
    #[error("dragged entity {0:?} not found in sketch")]
    NotFound(SketchEntityId),
    #[error(transparent)]
    Solver(#[from] SolverError),
}

#[derive(Clone, Debug)]
pub struct Mapping {
    points: BTreeMap<SketchEntityId, PointHandle>,
    radii: BTreeMap<SketchEntityId, ParameterIndex>,
    residual_origin: Vec<Origin>,
}

#[derive(Copy, Clone, Debug, PartialEq)]
enum Origin {
    Relation(SketchRelationId),
    Dimension(SketchDimensionId),
    Intrinsic(SketchEntityId),
}

impl Mapping {
    #[must_use]
    pub fn point(&self, id: SketchEntityId) -> Option<PointHandle> {
        self.points.get(&id).copied()
    }

    #[must_use]
    pub fn radius(&self, id: SketchEntityId) -> Option<ParameterIndex> {
        self.radii.get(&id).copied()
    }

    #[must_use]
    pub fn item_of_residual(&self, idx: ResidualIndex) -> Option<SketchItemId> {
        self.residual_origin.get(idx.as_usize()).map(|o| match *o {
            Origin::Relation(id) => SketchItemId::Relation(id),
            Origin::Dimension(id) => SketchItemId::Dimension(id),
            Origin::Intrinsic(id) => SketchItemId::Entity(id),
        })
    }

    #[must_use]
    pub fn items(&self, indices: impl IntoIterator<Item = ResidualIndex>) -> Vec<SketchItemId> {
        indices
            .into_iter()
            .filter_map(|i| self.item_of_residual(i))
            .collect()
    }

    #[must_use]
    pub fn entity_of_parameter(&self, idx: ParameterIndex) -> Option<SketchEntityId> {
        self.points
            .iter()
            .find_map(|(id, h)| (h.x == idx || h.y == idx).then_some(*id))
            .or_else(|| {
                self.radii
                    .iter()
                    .find_map(|(id, p)| (*p == idx).then_some(*id))
            })
    }
}

#[derive(Clone, Debug, PartialEq)]
pub struct SketchDofReport {
    dof: DegreesOfFreedom,
    under_constrained: Vec<SketchEntityId>,
    over_constrained: Vec<SketchItemId>,
    redundant_consistent: Vec<SketchItemId>,
}

impl SketchDofReport {
    #[must_use]
    pub fn dof(&self) -> DegreesOfFreedom {
        self.dof
    }

    #[must_use]
    pub fn under_constrained(&self) -> &[SketchEntityId] {
        &self.under_constrained
    }

    #[must_use]
    pub fn over_constrained(&self) -> &[SketchItemId] {
        &self.over_constrained
    }

    #[must_use]
    pub fn redundant_consistent(&self) -> &[SketchItemId] {
        &self.redundant_consistent
    }

    fn from_solver_report(report: &DofReport, mapping: &Mapping) -> Self {
        Self {
            dof: report.dof(),
            under_constrained: dedup_preserving_order(
                report
                    .under_constrained()
                    .iter()
                    .filter_map(|p| mapping.entity_of_parameter(*p)),
            ),
            over_constrained: dedup_preserving_order(
                mapping.items(report.over_constrained().iter().copied()),
            ),
            redundant_consistent: dedup_preserving_order(
                mapping.items(report.redundant_consistent().iter().copied()),
            ),
        }
    }
}

impl Sketch {
    #[must_use]
    pub fn lower(&self) -> (ConstraintSystem, Mapping) {
        let (parameters, points, radii) = self.entity_order().iter().fold(
            (
                Vec::<Parameter>::new(),
                BTreeMap::<SketchEntityId, PointHandle>::new(),
                BTreeMap::<SketchEntityId, ParameterIndex>::new(),
            ),
            |(mut parameters, mut points, mut radii), id| {
                match self.entities()[*id] {
                    SketchEntity::Point(p) => {
                        let (x, y) = p.at().coords_mm();
                        let handle = PointHandle {
                            x: push_parameter(&mut parameters, x),
                            y: push_parameter(&mut parameters, y),
                        };
                        points.insert(*id, handle);
                    }
                    SketchEntity::Circle(c) => {
                        let idx = push_parameter(&mut parameters, c.radius().get::<millimeter>());
                        radii.insert(*id, idx);
                    }
                    SketchEntity::Line(_) | SketchEntity::Arc(_) => {}
                }
                (parameters, points, radii)
            },
        );

        let intrinsic_rows: Vec<(Residual, Origin)> = self
            .entity_order()
            .iter()
            .flat_map(|eid| {
                intrinsic_residuals(self, *eid, &points)
                    .into_iter()
                    .map(move |r| (r, Origin::Intrinsic(*eid)))
            })
            .collect();

        let relation_rows: Vec<(Residual, Origin)> = self
            .relation_order()
            .iter()
            .flat_map(|rid| {
                lower_relation(self, self.relations()[*rid], &points, &radii, &parameters)
                    .into_iter()
                    .map(move |r| (r, Origin::Relation(*rid)))
            })
            .collect();

        let dimension_rows: Vec<(Residual, Origin)> = self
            .dimension_order()
            .iter()
            .filter(|did| self.dimensions()[**did].kind() != DimensionKind::Driven)
            .flat_map(|did| {
                lower_dimension(self, self.dimensions()[*did], &points, &radii)
                    .into_iter()
                    .map(move |r| (r, Origin::Dimension(*did)))
            })
            .collect();

        let combined: Vec<(Residual, Origin)> = intrinsic_rows
            .into_iter()
            .chain(relation_rows)
            .chain(dimension_rows)
            .collect();
        let residual_origin: Vec<Origin> = combined
            .iter()
            .flat_map(|(r, o)| std::iter::repeat_n(*o, r.rows()))
            .collect();
        let residuals: Vec<Residual> = combined.into_iter().map(|(r, _)| r).collect();
        let system = ConstraintSystem::new(parameters, residuals);
        let mapping = Mapping {
            points,
            radii,
            residual_origin,
        };
        (system, mapping)
    }

    pub fn solve(&self) -> Result<Sketch, SolverError> {
        let (system, mapping) = self.lower();
        let decomposition = decompose(&system);
        match solve_newton_decomposed(&system, &decomposition, NewtonConfig::DEFAULT) {
            Ok(parameters) => {
                let report = analyze_dof_at(&system, &parameters, DofConfig::DEFAULT);
                if report.over_constrained().is_empty() {
                    Ok(self.clone().apply_solution(&parameters, &mapping))
                } else {
                    Err(narrow_over_defined(
                        &system,
                        &mapping,
                        report.over_constrained(),
                    ))
                }
            }
            Err(SolverError::NoSolutionFound { last }) => {
                let report = analyze_dof(&system, DofConfig::DEFAULT);
                if report.over_constrained().is_empty() {
                    Err(SolverError::NoSolutionFound { last })
                } else {
                    Err(narrow_over_defined(
                        &system,
                        &mapping,
                        report.over_constrained(),
                    ))
                }
            }
            Err(other) => Err(other),
        }
    }

    pub fn solve_with_drag(
        &self,
        dragged: SketchEntityId,
        target: Point2,
        budget: BudgetCeiling,
    ) -> Result<Sketch, DragError> {
        self.solve_with_drag_pins(&[(dragged, target)], budget)
    }

    pub fn solve_with_drag_pins(
        &self,
        pins: &[(SketchEntityId, Point2)],
        budget: BudgetCeiling,
    ) -> Result<Sketch, DragError> {
        let started = Instant::now();
        pins.iter().try_for_each(|(id, _)| {
            let entity = self
                .entities()
                .get(*id)
                .copied()
                .ok_or(DragError::NotFound(*id))?;
            if matches!(entity, SketchEntity::Point(_)) {
                Ok(())
            } else {
                Err(DragError::NotAPoint(*id))
            }
        })?;
        let fixed_points: BTreeSet<SketchEntityId> = self
            .relations()
            .values()
            .filter_map(|rel| match *rel {
                SketchRelation::Fix(id) => Some(id),
                _ => None,
            })
            .collect();
        let deduped: Vec<(SketchEntityId, Point2)> = pins
            .iter()
            .copied()
            .enumerate()
            .filter(|(i, (id, _))| pins[..*i].iter().all(|(prior, _)| prior != id))
            .filter(|(_, (id, _))| !fixed_points.contains(id))
            .map(|(_, pair)| pair)
            .collect();
        let updates: HashMap<SketchEntityId, Point2> = deduped.iter().copied().collect();
        let warm = self.clone().with_point_positions(&updates);
        let (system, mapping) = warm.lower();
        let extra: Vec<Residual> = deduped
            .iter()
            .flat_map(|(id, target)| {
                let Some(handle) = mapping.point(*id) else {
                    unreachable!("Point entity must lower to a PointHandle in the mapping")
                };
                let (tx, ty) = target.coords_mm();
                [
                    Residual::Pin {
                        param: handle.x,
                        target: tx,
                    },
                    Residual::Pin {
                        param: handle.y,
                        target: ty,
                    },
                ]
            })
            .collect();
        let system = system.with_extra_residuals(extra);
        let decomposition = decompose(&system);
        let remaining = BudgetCeiling::new(budget.duration().saturating_sub(started.elapsed()));
        let cfg = NewtonConfig {
            budget: Some(remaining),
            ..NewtonConfig::DEFAULT
        };
        let parameters = solve_newton_decomposed(&system, &decomposition, cfg)?;
        Ok(warm.apply_solution(&parameters, &mapping))
    }

    #[must_use]
    pub fn analyze_dof(&self) -> SketchDofReport {
        let (system, mapping) = self.lower();
        let decomposition = decompose(&system);
        let report = match solve_newton_decomposed(&system, &decomposition, NewtonConfig::DEFAULT) {
            Ok(parameters) => analyze_dof_at(&system, &parameters, DofConfig::DEFAULT),
            Err(_) => analyze_dof(&system, DofConfig::DEFAULT),
        };
        SketchDofReport::from_solver_report(&report, &mapping)
    }

    #[must_use]
    pub fn status(&self) -> SketchStatusReport {
        let dangling = collect_dangling(self);
        if !dangling.is_empty() {
            return SketchStatusReport::dangling(dangling);
        }
        let (system, mapping) = self.lower();
        let decomposition = decompose(&system);
        match solve_newton_decomposed(&system, &decomposition, NewtonConfig::DEFAULT) {
            Ok(parameters) => {
                let report = analyze_dof_at(&system, &parameters, DofConfig::DEFAULT);
                if !report.over_constrained().is_empty() {
                    return SketchStatusReport::over_defined(narrow_conflicts(
                        &system,
                        &mapping,
                        report.over_constrained(),
                    ));
                }
                if report.dof().value() > 0 {
                    SketchStatusReport::under_defined(report.dof())
                } else {
                    SketchStatusReport::fully_defined()
                }
            }
            Err(SolverError::OverDefined { conflicts }) => {
                SketchStatusReport::over_defined(conflicts)
            }
            Err(SolverError::NoSolutionFound { .. }) => {
                let report = analyze_dof(&system, DofConfig::DEFAULT);
                if report.over_constrained().is_empty() {
                    SketchStatusReport::no_solution_found()
                } else {
                    SketchStatusReport::over_defined(narrow_conflicts(
                        &system,
                        &mapping,
                        report.over_constrained(),
                    ))
                }
            }
            Err(SolverError::InvalidSolutionFound { .. }) => {
                SketchStatusReport::invalid_solution_found()
            }
            Err(SolverError::Budget { .. }) => SketchStatusReport::no_solution_found(),
        }
    }

    #[must_use]
    pub fn measure(&self, dim: SketchDimension) -> Option<DimensionValue> {
        measure_dimension(self, dim)
    }

    #[must_use]
    pub fn apply_solution(self, parameters: &[Parameter], mapping: &Mapping) -> Self {
        let point_updates: HashMap<SketchEntityId, bone_types::Point2> = mapping
            .points
            .iter()
            .map(|(id, h)| {
                let p = bone_types::Point2::from_mm(
                    parameters[h.x.as_usize()].value(),
                    parameters[h.y.as_usize()].value(),
                );
                (*id, p)
            })
            .collect();
        let radius_updates: HashMap<SketchEntityId, Length> = mapping
            .radii
            .iter()
            .map(|(id, idx)| {
                (
                    *id,
                    Length::new::<millimeter>(parameters[idx.as_usize()].value()),
                )
            })
            .collect();
        let next = self
            .with_point_positions(&point_updates)
            .with_circle_radii(&radius_updates);
        recompute_driven(next).with_bumped_version()
    }
}

fn narrow_over_defined(
    system: &ConstraintSystem,
    mapping: &Mapping,
    over_flagged: &[ResidualIndex],
) -> SolverError {
    SolverError::OverDefined {
        conflicts: narrow_conflicts(system, mapping, over_flagged),
    }
}

fn narrow_conflicts(
    system: &ConstraintSystem,
    mapping: &Mapping,
    over_flagged: &[ResidualIndex],
) -> Vec<SketchItemId> {
    let mus = minimal_unsatisfiable_subset(system, over_flagged, DofConfig::DEFAULT);
    let rows = if mus.is_empty() { over_flagged } else { &mus };
    dedup_preserving_order(mapping.items(rows.iter().copied()))
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SketchStatusReport {
    status: SketchStatus,
    offending: Vec<SketchItemId>,
    dof: DegreesOfFreedom,
}

impl SketchStatusReport {
    #[must_use]
    pub fn status(&self) -> SketchStatus {
        self.status
    }

    #[must_use]
    pub fn offending(&self) -> &[SketchItemId] {
        &self.offending
    }

    #[must_use]
    pub fn dof(&self) -> DegreesOfFreedom {
        self.dof
    }

    fn fully_defined() -> Self {
        Self {
            status: SketchStatus::FullyDefined,
            offending: Vec::new(),
            dof: DegreesOfFreedom::new(0),
        }
    }

    fn under_defined(dof: DegreesOfFreedom) -> Self {
        Self {
            status: SketchStatus::UnderDefined,
            offending: Vec::new(),
            dof,
        }
    }

    fn over_defined(offending: Vec<SketchItemId>) -> Self {
        Self {
            status: SketchStatus::OverDefined,
            offending,
            dof: DegreesOfFreedom::new(0),
        }
    }

    fn no_solution_found() -> Self {
        Self {
            status: SketchStatus::NoSolutionFound,
            offending: Vec::new(),
            dof: DegreesOfFreedom::new(0),
        }
    }

    fn invalid_solution_found() -> Self {
        Self {
            status: SketchStatus::InvalidSolutionFound,
            offending: Vec::new(),
            dof: DegreesOfFreedom::new(0),
        }
    }

    fn dangling(offending: Vec<SketchItemId>) -> Self {
        Self {
            status: SketchStatus::Dangling,
            offending,
            dof: DegreesOfFreedom::new(0),
        }
    }
}

fn collect_dangling(sketch: &Sketch) -> Vec<SketchItemId> {
    let entity_exists = |id: SketchEntityId| sketch.entities().contains_key(id);
    let dangling_entities = sketch
        .entities()
        .iter()
        .filter(|(_, entity)| !entity.references().into_iter().all(entity_exists))
        .map(|(eid, _)| SketchItemId::Entity(eid));
    let dangling_rels = sketch
        .relations()
        .iter()
        .filter(|(_, rel)| !rel.references().into_iter().all(entity_exists))
        .map(|(rid, _)| SketchItemId::Relation(rid));
    let dangling_dims = sketch
        .dimensions()
        .iter()
        .filter(|(_, dim)| !dim.references().into_iter().all(entity_exists))
        .map(|(did, _)| SketchItemId::Dimension(did));
    dangling_entities
        .chain(dangling_rels)
        .chain(dangling_dims)
        .collect()
}

fn push_parameter(out: &mut Vec<Parameter>, value: f64) -> ParameterIndex {
    let idx = ParameterIndex::new(u32::try_from(out.len()).unwrap_or(u32::MAX));
    out.push(Parameter::new(value));
    idx
}

fn intrinsic_residuals(
    sketch: &Sketch,
    id: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
) -> Vec<Residual> {
    match sketch.entities().get(id) {
        Some(SketchEntity::Arc(a)) => match (
            points.get(&a.center()).copied(),
            points.get(&a.start()).copied(),
            points.get(&a.end()).copied(),
        ) {
            (Some(center), Some(spoke), Some(end)) => vec![Residual::CoincidentPointCurve {
                point: end,
                curve: CurveRadius::FromSpoke { center, spoke },
            }],
            _ => Vec::new(),
        },
        _ => Vec::new(),
    }
}

fn lower_relation(
    sketch: &Sketch,
    relation: SketchRelation,
    points: &BTreeMap<SketchEntityId, PointHandle>,
    radii: &BTreeMap<SketchEntityId, ParameterIndex>,
    parameters: &[Parameter],
) -> Vec<Residual> {
    match relation {
        SketchRelation::Coincident(a, b) => lower_coincident(sketch, a, b, points, radii),
        SketchRelation::Horizontal(id) => line_handle(sketch, id, points)
            .map(Residual::Horizontal)
            .into_iter()
            .collect(),
        SketchRelation::Vertical(id) => line_handle(sketch, id, points)
            .map(Residual::Vertical)
            .into_iter()
            .collect(),
        SketchRelation::Parallel(a, b) => combine_lines(sketch, a, b, points, Residual::Parallel),
        SketchRelation::Perpendicular(a, b) => {
            combine_lines(sketch, a, b, points, Residual::Perpendicular)
        }
        SketchRelation::Tangent(a, b) => lower_tangent(sketch, a, b, points, radii),
        SketchRelation::Equal(a, b) => lower_equal(sketch, a, b, points, radii),
        SketchRelation::Concentric(a, b) => lower_concentric(sketch, a, b, points),
        SketchRelation::Midpoint { point, line } => lower_midpoint(sketch, point, line, points),
        SketchRelation::Symmetric { a, b, axis } => lower_symmetric(sketch, a, b, axis, points),
        SketchRelation::Fix(id) => lower_fix(sketch, id, points, radii, parameters),
    }
}

fn lower_symmetric(
    sketch: &Sketch,
    a: SketchEntityId,
    b: SketchEntityId,
    axis: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
) -> Vec<Residual> {
    let (Some(a_handle), Some(b_handle), Some(line)) = (
        points.get(&a).copied(),
        points.get(&b).copied(),
        line_handle(sketch, axis, points),
    ) else {
        return Vec::new();
    };
    vec![Residual::Symmetric {
        a: a_handle,
        b: b_handle,
        axis: line,
    }]
}

fn lower_coincident(
    sketch: &Sketch,
    a: SketchEntityId,
    b: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
    radii: &BTreeMap<SketchEntityId, ParameterIndex>,
) -> Vec<Residual> {
    let ka = kind(sketch, a);
    let kb = kind(sketch, b);
    let (point_id, other_id, other_kind) = match (ka, kb) {
        (SketchEntityKind::Point, _) => (a, b, kb),
        (_, SketchEntityKind::Point) => (b, a, ka),
        _ => unreachable!("Coincident validation guarantees at least one point operand"),
    };
    let Some(point) = points.get(&point_id).copied() else {
        return Vec::new();
    };
    match other_kind {
        SketchEntityKind::Point => points
            .get(&other_id)
            .copied()
            .map(|q| vec![Residual::CoincidentPointPoint(point, q)])
            .unwrap_or_default(),
        SketchEntityKind::Line => line_handle(sketch, other_id, points)
            .map(|line| vec![Residual::CoincidentPointLine { point, line }])
            .unwrap_or_default(),
        SketchEntityKind::Circle | SketchEntityKind::Arc => {
            curve_radius(sketch, other_id, points, radii)
                .map(|curve| vec![Residual::CoincidentPointCurve { point, curve }])
                .unwrap_or_default()
        }
    }
}

fn combine_lines(
    sketch: &Sketch,
    a: SketchEntityId,
    b: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
    build: impl Fn(LineHandle, LineHandle) -> Residual,
) -> Vec<Residual> {
    match (
        line_handle(sketch, a, points),
        line_handle(sketch, b, points),
    ) {
        (Some(la), Some(lb)) => vec![build(la, lb)],
        _ => Vec::new(),
    }
}

fn lower_tangent(
    sketch: &Sketch,
    a: SketchEntityId,
    b: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
    radii: &BTreeMap<SketchEntityId, ParameterIndex>,
) -> Vec<Residual> {
    let ka = kind(sketch, a);
    let kb = kind(sketch, b);
    let line_id;
    let curve_id;
    match (ka, kb) {
        (SketchEntityKind::Line, _) => {
            line_id = Some(a);
            curve_id = b;
        }
        (_, SketchEntityKind::Line) => {
            line_id = Some(b);
            curve_id = a;
        }
        _ => {
            line_id = None;
            curve_id = a;
        }
    }
    if let Some(lid) = line_id {
        return match (
            line_handle(sketch, lid, points),
            curve_radius(sketch, curve_id, points, radii),
        ) {
            (Some(line), Some(curve)) => vec![Residual::TangentLineCurve { line, curve }],
            _ => Vec::new(),
        };
    }
    match (
        curve_radius(sketch, a, points, radii),
        curve_radius(sketch, b, points, radii),
    ) {
        (Some(ca), Some(cb)) => vec![Residual::TangentCurveCurve { a: ca, b: cb }],
        _ => Vec::new(),
    }
}

fn lower_equal(
    sketch: &Sketch,
    a: SketchEntityId,
    b: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
    radii: &BTreeMap<SketchEntityId, ParameterIndex>,
) -> Vec<Residual> {
    match (kind(sketch, a), kind(sketch, b)) {
        (SketchEntityKind::Line, SketchEntityKind::Line) => {
            combine_lines(sketch, a, b, points, Residual::EqualLength)
        }
        (ka, kb) if is_curve(ka) && is_curve(kb) => match (
            curve_radius(sketch, a, points, radii),
            curve_radius(sketch, b, points, radii),
        ) {
            (Some(ca), Some(cb)) => vec![Residual::EqualRadius(ca, cb)],
            _ => Vec::new(),
        },
        _ => unreachable!("Equal validation guarantees matching-kind operands"),
    }
}

fn lower_midpoint(
    sketch: &Sketch,
    point_id: SketchEntityId,
    line_id: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
) -> Vec<Residual> {
    match (
        points.get(&point_id).copied(),
        line_handle(sketch, line_id, points),
    ) {
        (Some(point), Some(line)) => vec![Residual::MidpointPointLine { point, line }],
        _ => Vec::new(),
    }
}

fn lower_concentric(
    sketch: &Sketch,
    a: SketchEntityId,
    b: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
) -> Vec<Residual> {
    let ca = curve_center(sketch, a).and_then(|c| points.get(&c).copied());
    let cb = curve_center(sketch, b).and_then(|c| points.get(&c).copied());
    match (ca, cb) {
        (Some(p), Some(q)) => vec![Residual::CoincidentPointPoint(p, q)],
        _ => Vec::new(),
    }
}

fn lower_fix(
    sketch: &Sketch,
    id: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
    radii: &BTreeMap<SketchEntityId, ParameterIndex>,
    parameters: &[Parameter],
) -> Vec<Residual> {
    let Some(entity) = sketch.entities().get(id).copied() else {
        return Vec::new();
    };
    let point_ids: Vec<SketchEntityId> = match entity {
        SketchEntity::Point(_) => vec![id],
        _ => entity.references().into_iter().collect(),
    };
    let pins_from_points = point_ids
        .into_iter()
        .filter_map(|pid| points.get(&pid).copied())
        .flat_map(|h| {
            [
                Residual::Pin {
                    param: h.x,
                    target: parameters[h.x.as_usize()].value(),
                },
                Residual::Pin {
                    param: h.y,
                    target: parameters[h.y.as_usize()].value(),
                },
            ]
        });
    let radius_pin = matches!(entity, SketchEntity::Circle(_))
        .then(|| radii.get(&id).copied())
        .flatten()
        .map(|idx| Residual::Pin {
            param: idx,
            target: parameters[idx.as_usize()].value(),
        });
    pins_from_points.chain(radius_pin).collect()
}

fn lower_dimension(
    sketch: &Sketch,
    dim: SketchDimension,
    points: &BTreeMap<SketchEntityId, PointHandle>,
    radii: &BTreeMap<SketchEntityId, ParameterIndex>,
) -> Vec<Residual> {
    match dim {
        SketchDimension::Linear { a, b, value, .. } => match (points.get(&a), points.get(&b)) {
            (Some(pa), Some(pb)) => vec![Residual::LinearDistance {
                a: *pa,
                b: *pb,
                value_mm: value.get::<millimeter>(),
            }],
            _ => Vec::new(),
        },
        SketchDimension::Radius { target, value, .. } => {
            curve_radius(sketch, target, points, radii)
                .map(|curve| {
                    vec![Residual::RadiusCurve {
                        curve,
                        value_mm: value.get::<millimeter>(),
                    }]
                })
                .unwrap_or_default()
        }
        SketchDimension::Diameter { target, value, .. } => {
            curve_radius(sketch, target, points, radii)
                .map(|curve| {
                    vec![Residual::RadiusCurve {
                        curve,
                        value_mm: value.get::<millimeter>() * 0.5,
                    }]
                })
                .unwrap_or_default()
        }
        SketchDimension::Angular { a, b, value, .. } => {
            combine_lines(sketch, a, b, points, move |la, lb| {
                Residual::AngularBetweenLines {
                    a: la,
                    b: lb,
                    angle_rad: value.get::<radian>(),
                }
            })
        }
    }
}

fn kind(sketch: &Sketch, id: SketchEntityId) -> SketchEntityKind {
    sketch
        .entities()
        .get(id)
        .map_or(SketchEntityKind::Point, SketchEntity::kind)
}

fn is_curve(k: SketchEntityKind) -> bool {
    matches!(k, SketchEntityKind::Circle | SketchEntityKind::Arc)
}

fn line_handle(
    sketch: &Sketch,
    id: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
) -> Option<LineHandle> {
    let entity = sketch.entities().get(id)?;
    let SketchEntity::Line(l) = entity else {
        return None;
    };
    Some(LineHandle {
        a: *points.get(&l.a())?,
        b: *points.get(&l.b())?,
    })
}

fn curve_radius(
    sketch: &Sketch,
    id: SketchEntityId,
    points: &BTreeMap<SketchEntityId, PointHandle>,
    radii: &BTreeMap<SketchEntityId, ParameterIndex>,
) -> Option<CurveRadius> {
    match sketch.entities().get(id)? {
        SketchEntity::Circle(c) => {
            let center = *points.get(&c.center())?;
            let radius = *radii.get(&id)?;
            Some(CurveRadius::Explicit { center, radius })
        }
        SketchEntity::Arc(a) => {
            let center = *points.get(&a.center())?;
            let spoke = *points.get(&a.start())?;
            Some(CurveRadius::FromSpoke { center, spoke })
        }
        _ => None,
    }
}

fn curve_center(sketch: &Sketch, id: SketchEntityId) -> Option<SketchEntityId> {
    match sketch.entities().get(id)? {
        SketchEntity::Circle(c) => Some(c.center()),
        SketchEntity::Arc(a) => Some(a.center()),
        _ => None,
    }
}

fn recompute_driven(sketch: Sketch) -> Sketch {
    let driven_updates: Vec<(SketchDimensionId, DimensionValue)> = sketch
        .dimension_order()
        .iter()
        .filter_map(|did| {
            let dim = *sketch.dimensions().get(*did)?;
            if dim.kind() != DimensionKind::Driven {
                return None;
            }
            let value = measure_dimension(&sketch, dim)?;
            Some((*did, value))
        })
        .collect();
    sketch.with_driven_dimension_values(&driven_updates)
}

fn measure_dimension(sketch: &Sketch, dim: SketchDimension) -> Option<DimensionValue> {
    match dim {
        SketchDimension::Linear { a, b, .. } => {
            let pa = point_position(sketch, a)?;
            let pb = point_position(sketch, b)?;
            let (ax, ay) = pa.coords_mm();
            let (bx, by) = pb.coords_mm();
            let dx = bx - ax;
            let dy = by - ay;
            Some(DimensionValue::Length(Length::new::<millimeter>(
                (dx * dx + dy * dy).sqrt(),
            )))
        }
        SketchDimension::Radius { target, .. } => measure_radius(sketch, target)
            .map(|r| DimensionValue::Length(Length::new::<millimeter>(r))),
        SketchDimension::Diameter { target, .. } => measure_radius(sketch, target)
            .map(|r| DimensionValue::Length(Length::new::<millimeter>(2.0 * r))),
        SketchDimension::Angular { a, b, .. } => {
            measure_angle(sketch, a, b).map(|r| DimensionValue::Angle(Angle::new::<radian>(r)))
        }
    }
}

fn point_position(sketch: &Sketch, id: SketchEntityId) -> Option<bone_types::Point2> {
    match sketch.entities().get(id)? {
        SketchEntity::Point(p) => Some(p.at()),
        _ => None,
    }
}

fn measure_radius(sketch: &Sketch, id: SketchEntityId) -> Option<f64> {
    match sketch.entities().get(id)? {
        SketchEntity::Circle(c) => Some(c.radius().get::<millimeter>()),
        SketchEntity::Arc(a) => {
            let center = point_position(sketch, a.center())?;
            let start = point_position(sketch, a.start())?;
            let (cx, cy) = center.coords_mm();
            let (sx, sy) = start.coords_mm();
            let dx = sx - cx;
            let dy = sy - cy;
            Some((dx * dx + dy * dy).sqrt())
        }
        _ => None,
    }
}

fn measure_angle(sketch: &Sketch, a: SketchEntityId, b: SketchEntityId) -> Option<f64> {
    let la = line_endpoints(sketch, a)?;
    let lb = line_endpoints(sketch, b)?;
    let (d1x, d1y) = (la.1.0 - la.0.0, la.1.1 - la.0.1);
    let (d2x, d2y) = (lb.1.0 - lb.0.0, lb.1.1 - lb.0.1);
    let mag = ((d1x * d1x + d1y * d1y) * (d2x * d2x + d2y * d2y)).sqrt();
    if mag <= 0.0 {
        return None;
    }
    let cos = (d1x * d2x + d1y * d2y) / mag;
    Some(cos.abs().clamp(0.0, 1.0).acos())
}

fn line_endpoints(sketch: &Sketch, id: SketchEntityId) -> Option<((f64, f64), (f64, f64))> {
    match sketch.entities().get(id)? {
        SketchEntity::Line(l) => {
            let a = point_position(sketch, l.a())?.coords_mm();
            let b = point_position(sketch, l.b())?.coords_mm();
            Some((a, b))
        }
        _ => None,
    }
}

#[cfg(test)]
mod tests {
    use std::collections::BTreeSet;

    use super::*;
    use crate::sketch::{EditOutcome, SketchEdit};
    use bone_solver::{assemble_jacobian, evaluate_residuals, sparsity_pattern};
    use bone_types::{Point2, Point3, SketchPlaneBasis, Tolerance, UnitVec3};
    use nalgebra::DMatrix;

    fn xy_plane() -> SketchPlaneBasis {
        let Ok(basis) = SketchPlaneBasis::new(
            Point3::origin(),
            UnitVec3::x_axis(),
            UnitVec3::y_axis(),
            Tolerance::new(1e-9),
        ) else {
            panic!("xy axes are orthogonal");
        };
        basis
    }

    fn apply(sketch: &Sketch, edits: Vec<SketchEdit>) -> (Sketch, Vec<EditOutcome>) {
        let Ok(pair) = sketch.apply_all(edits) else {
            panic!("fixture edits apply cleanly");
        };
        pair
    }

    fn mm_val(v: f64) -> Length {
        Length::new::<millimeter>(v)
    }

    fn entity_id(outcome: &EditOutcome) -> SketchEntityId {
        let EditOutcome::Entity(id) = outcome else {
            panic!("expected entity outcome");
        };
        *id
    }

    fn generous_budget() -> BudgetCeiling {
        BudgetCeiling::new(core::time::Duration::from_secs(5))
    }

    fn rectangle_sketch() -> (Sketch, [SketchEntityId; 4]) {
        let base = Sketch::new(xy_plane());
        let (after, out) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(7.0, 0.5))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(7.5, 3.2))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.3, 2.9))),
            ],
        );
        let ids = [0_usize, 1, 2, 3].map(|i| entity_id(&out[i]));
        (after, ids)
    }

    fn constrained_rectangle() -> Sketch {
        let (base, corners) = rectangle_sketch();
        let [corner_0, corner_1, corner_2, corner_3] = corners;
        let (with_edges, out) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::line(corner_0, corner_1, false)),
                SketchEdit::AddEntity(SketchEntity::line(corner_1, corner_2, false)),
                SketchEdit::AddEntity(SketchEntity::line(corner_2, corner_3, false)),
                SketchEdit::AddEntity(SketchEntity::line(corner_3, corner_0, false)),
            ],
        );
        let [edge_bottom, edge_right, edge_top, edge_left] =
            [0_usize, 1, 2, 3].map(|i| entity_id(&out[i]));
        apply(
            &with_edges,
            vec![
                SketchEdit::AddRelation(SketchRelation::Horizontal(edge_bottom)),
                SketchEdit::AddRelation(SketchRelation::Horizontal(edge_top)),
                SketchEdit::AddRelation(SketchRelation::Vertical(edge_right)),
                SketchEdit::AddRelation(SketchRelation::Vertical(edge_left)),
                SketchEdit::AddRelation(SketchRelation::Fix(corner_0)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a: corner_0,
                    b: corner_1,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a: corner_1,
                    b: corner_2,
                    value: mm_val(5.0),
                    kind: DimensionKind::Driving,
                }),
            ],
        )
        .0
    }

    fn finite_difference_jacobian(
        system: &ConstraintSystem,
        params: &[f64],
        eps: f64,
    ) -> DMatrix<f64> {
        let rows = system.row_count();
        let cols = params.len();
        (0..cols).fold(DMatrix::<f64>::zeros(rows, cols), |mut m, col| {
            let mut plus = params.to_vec();
            plus[col] += eps;
            let mut minus = params.to_vec();
            minus[col] -= eps;
            let rp = evaluate_residuals(system, &plus);
            let rn = evaluate_residuals(system, &minus);
            (0..rows).for_each(|row| {
                m[(row, col)] = (rp[row] - rn[row]) / (2.0 * eps);
            });
            m
        })
    }

    fn point_coords(sketch: &Sketch) -> Vec<(f64, f64)> {
        sketch
            .entity_order()
            .iter()
            .filter_map(|id| match sketch.entities().get(*id)? {
                SketchEntity::Point(p) => Some(p.at().coords_mm()),
                _ => None,
            })
            .collect()
    }

    #[test]
    fn rectangle_solves_to_exact_dimensions() {
        let Ok(solved) = constrained_rectangle().solve() else {
            panic!("rectangle solves");
        };
        let coords = point_coords(&solved);
        let expected = [(0.0, 0.0), (10.0, 0.0), (10.0, 5.0), (0.0, 5.0)];
        expected.iter().zip(coords.iter()).for_each(|(want, got)| {
            assert!((want.0 - got.0).abs() < 1e-6, "x: {want:?} vs {got:?}");
            assert!((want.1 - got.1).abs() < 1e-6, "y: {want:?} vs {got:?}");
        });
    }

    #[test]
    fn rectangle_analytic_jacobian_matches_finite_difference() {
        let sketch = constrained_rectangle();
        let (system, _) = sketch.lower();
        let params: Vec<f64> = system.parameters().iter().map(|p| p.value()).collect();
        let analytic = assemble_jacobian(&system, &params);
        let fd = finite_difference_jacobian(&system, &params, 1e-6);
        let diff = (&analytic - &fd).abs().max();
        assert!(diff < 1e-4, "jacobian mismatch (max diff {diff})");
    }

    #[test]
    fn rectangle_sparsity_pattern_is_stable() {
        let (system, _) = constrained_rectangle().lower();
        let pattern = sparsity_pattern(&system);
        insta::assert_snapshot!("rectangle_sparsity", pattern.display());
    }

    #[test]
    fn tangent_line_to_circle_solves() {
        let base = Sketch::new(xy_plane());
        let (with_points, out) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(10.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(3.0, 3.5))),
            ],
        );
        let [line_start, line_end, circle_center] = [0_usize, 1, 2].map(|i| entity_id(&out[i]));
        let (with_shapes, out2) = apply(
            &with_points,
            vec![
                SketchEdit::AddEntity(SketchEntity::line(line_start, line_end, false)),
                SketchEdit::AddEntity(SketchEntity::circle(circle_center, mm_val(2.0), false)),
            ],
        );
        let [line_id, circle_id] = [0_usize, 1].map(|i| entity_id(&out2[i]));
        let sketch = apply(
            &with_shapes,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(line_start)),
                SketchEdit::AddRelation(SketchRelation::Fix(line_end)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a: line_start,
                    b: circle_center,
                    value: mm_val(5.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Radius {
                    target: circle_id,
                    value: mm_val(2.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddRelation(SketchRelation::Tangent(line_id, circle_id)),
            ],
        )
        .0;
        let Ok(solved) = sketch.solve() else {
            panic!("tangent line-circle solves");
        };
        let coords = point_coords(&solved);
        let (start_x, start_y) = coords[0];
        let (end_x, end_y) = coords[1];
        let (center_x, center_y) = coords[2];
        assert!(start_x.abs() < 1e-6 && start_y.abs() < 1e-6);
        assert!((end_x - 10.0).abs() < 1e-6 && end_y.abs() < 1e-6);
        assert!(
            (center_y.abs() - 2.0).abs() < 1e-6,
            "center-to-line {center_y}"
        );
        let radial = (center_x * center_x + center_y * center_y).sqrt();
        assert!((radial - 5.0).abs() < 1e-6, "|c| {radial}");
    }

    #[test]
    fn item_of_residual_tracks_rows_across_multi_row_residuals() {
        let base = Sketch::new(xy_plane());
        let (s, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.5, 0.5))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(5.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(5.5, 0.5))),
            ],
        );
        let [p0, p1, p2, p3] = [0_usize, 1, 2, 3].map(|i| entity_id(&outs[i]));
        let (sketch, rel_outs) = apply(
            &s,
            vec![
                SketchEdit::AddRelation(SketchRelation::Coincident(p0, p1)),
                SketchEdit::AddRelation(SketchRelation::Fix(p2)),
                SketchEdit::AddRelation(SketchRelation::Coincident(p2, p3)),
            ],
        );
        let relation_ids: Vec<SketchRelationId> = rel_outs
            .iter()
            .map(|o| match *o {
                EditOutcome::Relation(id) => id,
                _ => panic!("expected relation outcome"),
            })
            .collect();
        let (system, mapping) = sketch.lower();
        assert_eq!(system.row_count(), 6);
        let expected: [SketchItemId; 6] = [
            SketchItemId::Relation(relation_ids[0]),
            SketchItemId::Relation(relation_ids[0]),
            SketchItemId::Relation(relation_ids[1]),
            SketchItemId::Relation(relation_ids[1]),
            SketchItemId::Relation(relation_ids[2]),
            SketchItemId::Relation(relation_ids[2]),
        ];
        expected.iter().enumerate().for_each(|(i, want)| {
            let Ok(row) = u32::try_from(i) else {
                unreachable!("fixture row count fits in u32")
            };
            let got = mapping.item_of_residual(ResidualIndex::new(row));
            assert_eq!(got, Some(*want), "row {i}");
        });
    }

    #[test]
    fn under_constrained_horizontal_line_solves() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(1.0, 3.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (with_line, out_line) = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
        );
        let line = entity_id(&out_line[0]);
        let sketch = apply(
            &with_line,
            vec![SketchEdit::AddRelation(SketchRelation::Horizontal(line))],
        )
        .0;
        let Ok(solved) = sketch.solve() else {
            panic!("under-constrained Horizontal should solve, not fail")
        };
        let coords = point_coords(&solved);
        assert!(
            (coords[0].1 - coords[1].1).abs() < 1e-6,
            "y-values should match after Horizontal: {coords:?}"
        );
    }

    #[test]
    fn driven_dimension_is_recomputed_post_solve() {
        let (base, corners) = rectangle_sketch();
        let [corner_0, corner_1, _corner_2, _corner_3] = corners;
        let sketch = apply(
            &base,
            vec![SketchEdit::AddDimension(SketchDimension::Linear {
                a: corner_0,
                b: corner_1,
                value: mm_val(0.0),
                kind: DimensionKind::Driven,
            })],
        )
        .0;
        let Ok(solved) = sketch.solve() else {
            panic!("solve with driven dim");
        };
        let driven_id = solved.dimension_order()[0];
        let SketchDimension::Linear { value, .. } = solved.dimensions()[driven_id] else {
            panic!("driven should remain Linear");
        };
        let expected = (7.0_f64.powi(2) + 0.5_f64.powi(2)).sqrt();
        assert!((value.get::<millimeter>() - expected).abs() < 1e-9);
    }

    #[test]
    fn arc_end_stays_on_implicit_circle_after_solve() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(2.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.3, 2.5))),
            ],
        );
        let [center, start, end] = [0_usize, 1, 2].map(|i| entity_id(&outs[i]));
        let (with_arc, out_arc) = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::arc(
                center, start, end, false,
            ))],
        );
        let _arc = entity_id(&out_arc[0]);
        let sketch = apply(
            &with_arc,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(center)),
                SketchEdit::AddRelation(SketchRelation::Fix(start)),
            ],
        )
        .0;
        let Ok(solved) = sketch.solve() else {
            panic!("arc coherence solve");
        };
        let coords = point_coords(&solved);
        let (cx, cy) = coords[0];
        let (sx, sy) = coords[1];
        let (ex, ey) = coords[2];
        let r_start = ((sx - cx).powi(2) + (sy - cy).powi(2)).sqrt();
        let r_end = ((ex - cx).powi(2) + (ey - cy).powi(2)).sqrt();
        assert!(
            (r_start - r_end).abs() < 1e-6,
            "arc end must lie on implicit circle: r_start={r_start} r_end={r_end}"
        );
    }

    fn horizontal_line_fixture(p0: (f64, f64), p1: (f64, f64), length_mm: f64) -> Sketch {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(p0.0, p0.1))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(p1.0, p1.1))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (with_line, line_outs) = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
        );
        let line = entity_id(&line_outs[0]);
        apply(
            &with_line,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(a)),
                SketchEdit::AddRelation(SketchRelation::Horizontal(line)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(length_mm),
                    kind: DimensionKind::Driving,
                }),
            ],
        )
        .0
    }

    fn disjoint_pair_fixture() -> Sketch {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(7.0, 0.3))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(100.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(107.0, 0.3))),
            ],
        );
        let [a0, a1, b0, b1] = [0_usize, 1, 2, 3].map(|i| entity_id(&outs[i]));
        let (with_lines, line_outs) = apply(
            &with_points,
            vec![
                SketchEdit::AddEntity(SketchEntity::line(a0, a1, false)),
                SketchEdit::AddEntity(SketchEntity::line(b0, b1, false)),
            ],
        );
        let [line_a, line_b] = [0_usize, 1].map(|i| entity_id(&line_outs[i]));
        apply(
            &with_lines,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(a0)),
                SketchEdit::AddRelation(SketchRelation::Horizontal(line_a)),
                SketchEdit::AddRelation(SketchRelation::Fix(b0)),
                SketchEdit::AddRelation(SketchRelation::Horizontal(line_b)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a: a0,
                    b: a1,
                    value: mm_val(5.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a: b0,
                    b: b1,
                    value: mm_val(9.0),
                    kind: DimensionKind::Driving,
                }),
            ],
        )
        .0
    }

    #[test]
    fn disjoint_sketches_solve_per_component() {
        let Ok(solved_a) = horizontal_line_fixture((0.0, 0.0), (7.0, 0.3), 5.0).solve() else {
            panic!("component A solves alone");
        };
        let Ok(solved_b) = horizontal_line_fixture((100.0, 0.0), (107.0, 0.3), 9.0).solve() else {
            panic!("component B solves alone");
        };
        let Ok(joint_solved) = disjoint_pair_fixture().solve() else {
            panic!("joint disjoint-component solve");
        };
        let joint_coords = point_coords(&joint_solved);
        let expected_joint: Vec<(f64, f64)> = point_coords(&solved_a)
            .into_iter()
            .chain(point_coords(&solved_b))
            .collect();
        expected_joint
            .iter()
            .zip(joint_coords.iter())
            .for_each(|(want, got)| {
                assert!(
                    (want.0 - got.0).abs() < 1e-9,
                    "x alone-vs-joint {want:?} vs {got:?}"
                );
                assert!(
                    (want.1 - got.1).abs() < 1e-9,
                    "y alone-vs-joint {want:?} vs {got:?}"
                );
            });
        let expected_absolute = [(0.0, 0.0), (5.0, 0.0), (100.0, 0.0), (109.0, 0.0)];
        expected_absolute
            .iter()
            .zip(joint_coords.iter())
            .for_each(|(want, got)| {
                assert!((want.0 - got.0).abs() < 1e-6, "x {want:?} vs {got:?}");
                assert!((want.1 - got.1).abs() < 1e-6, "y {want:?} vs {got:?}");
            });
    }

    #[test]
    fn conflicting_dimensions_report_over_defined() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(5.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (sketch, dim_outs) = apply(
            &with_points,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(a)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(3.0),
                    kind: DimensionKind::Driving,
                }),
            ],
        );
        let dim_ids: Vec<SketchDimensionId> = dim_outs
            .iter()
            .filter_map(|o| match *o {
                EditOutcome::Dimension(id) => Some(id),
                _ => None,
            })
            .collect();
        let Err(err) = sketch.solve() else {
            panic!("conflicting dimensions must surface OverDefined");
        };
        let SolverError::OverDefined { conflicts } = err else {
            panic!("expected OverDefined, got {err:?}");
        };
        assert!(!conflicts.is_empty(), "conflicts populated");
        let has_dim = conflicts
            .iter()
            .any(|c| matches!(*c, SketchItemId::Dimension(id) if dim_ids.contains(&id)));
        assert!(has_dim, "at least one of the conflicting dimensions names");
    }

    #[test]
    fn rectangle_with_conflicting_parallel_edge_dims_reports_over_defined() {
        let (rect, corners) = rectangle_sketch();
        let [corner_0, corner_1, corner_2, corner_3] = corners;
        let (with_edges, out) = apply(
            &rect,
            vec![
                SketchEdit::AddEntity(SketchEntity::line(corner_0, corner_1, false)),
                SketchEdit::AddEntity(SketchEntity::line(corner_1, corner_2, false)),
                SketchEdit::AddEntity(SketchEntity::line(corner_2, corner_3, false)),
                SketchEdit::AddEntity(SketchEntity::line(corner_3, corner_0, false)),
            ],
        );
        let [bottom, right, top, left] = [0_usize, 1, 2, 3].map(|i| entity_id(&out[i]));
        let (sketch, _) = apply(
            &with_edges,
            vec![
                SketchEdit::AddRelation(SketchRelation::Horizontal(bottom)),
                SketchEdit::AddRelation(SketchRelation::Horizontal(top)),
                SketchEdit::AddRelation(SketchRelation::Vertical(right)),
                SketchEdit::AddRelation(SketchRelation::Vertical(left)),
                SketchEdit::AddRelation(SketchRelation::Fix(corner_0)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a: corner_0,
                    b: corner_1,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a: corner_2,
                    b: corner_3,
                    value: mm_val(8.0),
                    kind: DimensionKind::Driving,
                }),
            ],
        );
        let Err(err) = sketch.solve() else {
            panic!("rectangle horizontals plus two unequal parallel-edge dims must conflict");
        };
        assert!(
            matches!(err, SolverError::OverDefined { .. }),
            "expected OverDefined, got {err:?}",
        );
    }

    #[test]
    fn measure_linear_returns_geometric_distance() {
        let base = Sketch::new(xy_plane());
        let (sketch, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(3.0, 4.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let Some(value) = sketch.measure(SketchDimension::Linear {
            a,
            b,
            value: mm_val(0.0),
            kind: DimensionKind::Driving,
        }) else {
            panic!("measure linear yielded None");
        };
        let DimensionValue::Length(length) = value else {
            panic!("linear measure must yield Length");
        };
        assert!((length.get::<millimeter>() - 5.0).abs() < 1e-9);
    }

    #[test]
    fn redundant_dimension_does_not_block_solve() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(10.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let sketch = apply(
            &with_points,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(a)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
            ],
        )
        .0;
        let report = sketch.analyze_dof();
        assert_eq!(report.dof().value(), 1);
        assert!(report.over_constrained().is_empty());
        assert!(!report.redundant_consistent().is_empty());
        let Ok(_) = sketch.solve() else {
            panic!("redundant-consistent system must solve");
        };
    }

    #[test]
    fn redundant_dimension_at_unsatisfied_seed_still_solves() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(5.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let sketch = apply(
            &with_points,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(a)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
            ],
        )
        .0;
        let report = sketch.analyze_dof();
        assert_eq!(report.dof().value(), 1);
        assert!(
            report.over_constrained().is_empty(),
            "redundant-consistent dims at unsatisfied seed must not be flagged as conflicts"
        );
        assert!(!report.redundant_consistent().is_empty());
        let Ok(solved) = sketch.solve() else {
            panic!("redundant-consistent dims at unsatisfied seed must solve");
        };
        let coords = point_coords(&solved);
        let (bx, by) = coords[1];
        let radial = (bx * bx + by * by).sqrt();
        assert!(
            (radial - 10.0).abs() < 1e-6,
            "free endpoint should move to |b|=10mm, got {radial}"
        );
    }

    #[test]
    fn analyze_dof_reports_fully_constrained_rectangle() {
        let sketch = constrained_rectangle();
        let report = sketch.analyze_dof();
        assert_eq!(report.dof().value(), 0);
        assert!(report.over_constrained().is_empty());
        assert!(report.redundant_consistent().is_empty());
        assert!(report.under_constrained().is_empty());
    }

    #[test]
    fn analyze_dof_reports_free_line() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(1.0, 3.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (with_line, line_outs) = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
        );
        let line = entity_id(&line_outs[0]);
        let sketch = apply(
            &with_line,
            vec![SketchEdit::AddRelation(SketchRelation::Horizontal(line))],
        )
        .0;
        let report = sketch.analyze_dof();
        assert_eq!(report.dof().value(), 3);
        assert!(report.over_constrained().is_empty());
        assert!(!report.under_constrained().is_empty());
    }

    fn three_conflicting_linear_dims_fixture() -> (Sketch, Vec<SketchDimensionId>) {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(5.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (sketch, dim_outs) = apply(
            &with_points,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(a)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(7.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
            ],
        );
        let dim_ids: Vec<SketchDimensionId> = dim_outs
            .iter()
            .filter_map(|o| match *o {
                EditOutcome::Dimension(id) => Some(id),
                _ => None,
            })
            .collect();
        (sketch, dim_ids)
    }

    #[test]
    fn mus_narrows_three_conflicting_dims_to_odd_one_out() {
        let (sketch, dim_ids) = three_conflicting_linear_dims_fixture();
        let Err(err) = sketch.solve() else {
            panic!("three conflicting dims must surface OverDefined");
        };
        let SolverError::OverDefined { conflicts } = err else {
            panic!("expected OverDefined, got {err:?}");
        };
        let added: BTreeSet<SketchItemId> = dim_ids
            .iter()
            .copied()
            .map(SketchItemId::Dimension)
            .collect();
        assert!(
            !conflicts.is_empty() && conflicts.len() < dim_ids.len(),
            "MUS must narrow {{10, 7, 10}} strictly below the full dim set: \
             conflicts={conflicts:?} dim_ids={dim_ids:?}",
        );
        if let Some(stray) = conflicts.iter().find(|c| !added.contains(c)) {
            panic!("unexpected conflict: {stray:?} not in {dim_ids:?}");
        }
        assert!(
            conflicts.contains(&SketchItemId::Dimension(dim_ids[1])),
            "MUS must flag the 7mm outlier (dim_ids[1]): \
             conflicts={conflicts:?} dim_ids={dim_ids:?}",
        );
    }

    #[test]
    fn mus_on_three_distinct_conflicting_dims_returns_minimal_conflict() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(5.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (sketch, dim_outs) = apply(
            &with_points,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(a)),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(10.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(7.0),
                    kind: DimensionKind::Driving,
                }),
                SketchEdit::AddDimension(SketchDimension::Linear {
                    a,
                    b,
                    value: mm_val(4.0),
                    kind: DimensionKind::Driving,
                }),
            ],
        );
        let dim_ids: Vec<SketchDimensionId> = dim_outs
            .iter()
            .filter_map(|o| match *o {
                EditOutcome::Dimension(id) => Some(id),
                _ => None,
            })
            .collect();
        let Err(SolverError::OverDefined { conflicts }) = sketch.solve() else {
            panic!("three distinct-value conflicting dims must surface OverDefined");
        };
        assert!(!conflicts.is_empty(), "MUS must be non-empty");
        assert!(
            conflicts.len() <= dim_ids.len(),
            "MUS must not exceed the added-dim count: conflicts={conflicts:?}",
        );
        if let Some(bad) = conflicts
            .iter()
            .find(|c| !matches!(c, SketchItemId::Dimension(id) if dim_ids.contains(id)))
        {
            panic!("unexpected conflict: {bad:?} not in {dim_ids:?}");
        }
        assert_eq!(
            conflicts.iter().collect::<BTreeSet<_>>().len(),
            conflicts.len(),
            "conflicts must be deduped: {conflicts:?}",
        );
    }

    #[test]
    fn narrow_over_defined_dedups_multi_row_parent() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(1.0, 1.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (sketch, rel_outs) = apply(
            &with_points,
            vec![SketchEdit::AddRelation(SketchRelation::Coincident(a, b))],
        );
        let EditOutcome::Relation(coincident_id) = rel_outs[0] else {
            panic!("expected relation outcome");
        };
        let (system, mapping) = sketch.lower();
        let rows: Vec<ResidualIndex> = (0..system.row_count())
            .map(|i| {
                let Ok(iv) = u32::try_from(i) else {
                    unreachable!("fixture row count fits in u32")
                };
                ResidualIndex::new(iv)
            })
            .collect();
        assert_eq!(rows.len(), 2, "Coincident is a two-row residual");
        let err = narrow_over_defined(&system, &mapping, &rows);
        let SolverError::OverDefined { conflicts } = err else {
            panic!("narrow_over_defined must surface OverDefined");
        };
        assert_eq!(
            conflicts,
            vec![SketchItemId::Relation(coincident_id)],
            "two rows of one Coincident must collapse to a single conflict: {conflicts:?}",
        );
    }

    fn draggable_horizontal_line() -> (Sketch, SketchEntityId, SketchEntityId) {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(5.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (with_line, line_outs) = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
        );
        let line = entity_id(&line_outs[0]);
        let sketch = apply(
            &with_line,
            vec![
                SketchEdit::AddRelation(SketchRelation::Fix(a)),
                SketchEdit::AddRelation(SketchRelation::Horizontal(line)),
            ],
        )
        .0;
        (sketch, a, b)
    }

    #[test]
    fn solve_with_drag_along_horizontal_lands_on_target() {
        let (sketch, a, b) = draggable_horizontal_line();
        let target = Point2::from_mm(8.0, 0.0);
        let Ok(dragged) = sketch.solve_with_drag(b, target, generous_budget()) else {
            panic!("feasible drag along Horizontal must converge");
        };
        let coords = point_coords(&dragged);
        let (bx, by) = coords[1];
        assert!(
            (bx - 8.0).abs() < 1e-6,
            "dragged x must land at target.x: {bx}",
        );
        assert!(
            by.abs() < 1e-6,
            "Horizontal holds: a.y={} b.y={by}",
            coords[0].1,
        );
        let (ax, ay) = coords[0];
        assert!(
            ax.abs() < 1e-9 && ay.abs() < 1e-9,
            "Fix on a holds: ({ax}, {ay})",
        );
        let _ = a;
    }

    #[test]
    fn solve_with_drag_pins_translates_line_endpoints() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(4.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (sketch, _line_outs) = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
        );
        let pins = [
            (a, Point2::from_mm(3.0, 2.0)),
            (b, Point2::from_mm(7.0, 2.0)),
        ];
        let Ok(dragged) = sketch.solve_with_drag_pins(&pins, generous_budget()) else {
            panic!("translating both endpoints by a constant delta must converge");
        };
        let coords = point_coords(&dragged);
        let (ax, ay) = coords[0];
        let (bx, by) = coords[1];
        assert!(
            (ax - 3.0).abs() < 1e-9 && (ay - 2.0).abs() < 1e-9,
            "endpoint a lands at pin: ({ax}, {ay})",
        );
        assert!(
            (bx - 7.0).abs() < 1e-9 && (by - 2.0).abs() < 1e-9,
            "endpoint b lands at pin: ({bx}, {by})",
        );
    }

    #[test]
    fn solve_with_drag_pins_ignores_drag_on_fixed_point() {
        let base = Sketch::new(xy_plane());
        let (with_point, outs) = apply(
            &base,
            vec![SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(
                1.0, 2.0,
            )))],
        );
        let p = entity_id(&outs[0]);
        let Ok((sketch, _)) = with_point.apply(SketchEdit::AddRelation(SketchRelation::Fix(p)))
        else {
            panic!("Fix relation should add cleanly");
        };
        let pins = [(p, Point2::from_mm(10.0, 20.0))];
        let Ok(dragged) = sketch.solve_with_drag_pins(&pins, generous_budget()) else {
            panic!("solve should converge even when drag pins are no-ops");
        };
        let (x, y) = point_coords(&dragged)[0];
        assert!(
            (x - 1.0).abs() < 1e-9 && (y - 2.0).abs() < 1e-9,
            "fixed point must not move under drag: ({x}, {y})",
        );
    }

    #[test]
    fn solve_with_drag_pins_dedupes_repeated_id() {
        let base = Sketch::new(xy_plane());
        let (sketch, outs) = apply(
            &base,
            vec![SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(
                0.0, 0.0,
            )))],
        );
        let p = entity_id(&outs[0]);
        let target = Point2::from_mm(2.0, 3.0);
        let pins = [(p, target), (p, target)];
        let Ok(dragged) = sketch.solve_with_drag_pins(&pins, generous_budget()) else {
            panic!("duplicate pins for the same point must dedupe and converge");
        };
        let (x, y) = point_coords(&dragged)[0];
        assert!(
            (x - 2.0).abs() < 1e-9 && (y - 3.0).abs() < 1e-9,
            "deduped pin lands on target: ({x}, {y})",
        );
    }

    #[test]
    fn measure_angle_returns_acute_for_obtuse_lines() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(1.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(-1.0, 0.0))),
            ],
        );
        let [p0, p1, p2, p3] = [0_usize, 1, 2, 3].map(|i| entity_id(&outs[i]));
        let (sketch, line_outs) = apply(
            &with_points,
            vec![
                SketchEdit::AddEntity(SketchEntity::line(p0, p1, false)),
                SketchEdit::AddEntity(SketchEntity::line(p2, p3, false)),
            ],
        );
        let [l1, l2] = [0_usize, 1].map(|i| entity_id(&line_outs[i]));
        let Some(value) = sketch.measure(SketchDimension::Angular {
            a: l1,
            b: l2,
            value: Angle::new::<radian>(0.0),
            kind: DimensionKind::Driving,
        }) else {
            panic!("angular measure yielded None");
        };
        let DimensionValue::Angle(angle) = value else {
            panic!("angular measure must yield Angle");
        };
        assert!(angle.get::<radian>().abs() < 1e-9);
    }

    #[test]
    fn solve_with_drag_pins_rejects_non_point_target() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(1.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (sketch, line_outs) = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
        );
        let line = entity_id(&line_outs[0]);
        let result =
            sketch.solve_with_drag_pins(&[(line, Point2::from_mm(0.0, 0.0))], generous_budget());
        assert!(matches!(result, Err(DragError::NotAPoint(id)) if id == line));
    }

    #[test]
    fn solve_with_drag_rejects_non_point() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(1.0, 0.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let (sketch, line_outs) = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
        );
        let line = entity_id(&line_outs[0]);
        let result = sketch.solve_with_drag(line, Point2::from_mm(0.0, 0.0), generous_budget());
        let Err(err) = result else {
            panic!("dragging a Line must reject, got {result:?}");
        };
        assert!(matches!(err, DragError::NotAPoint(id) if id == line));
    }

    #[test]
    fn solve_with_drag_rejects_unknown_entity_id() {
        let sketch = constrained_rectangle();
        let stranger = SketchEntityId::default();
        let result = sketch.solve_with_drag(stranger, Point2::from_mm(0.0, 0.0), generous_budget());
        let Err(err) = result else {
            panic!("unknown entity id must reject, got {result:?}");
        };
        assert!(matches!(err, DragError::NotFound(id) if id == stranger));
    }

    #[test]
    fn solve_with_drag_returns_budget_when_ceiling_is_zero() {
        let sketch = constrained_rectangle();
        let target = Point2::from_mm(20.0, 20.0);
        let drag_id = sketch.entity_order()[1];
        let result = sketch.solve_with_drag(
            drag_id,
            target,
            BudgetCeiling::new(core::time::Duration::ZERO),
        );
        match result {
            Err(DragError::Solver(SolverError::Budget { .. })) => {}
            other => panic!("expected Budget, got {other:?}"),
        }
    }

    #[test]
    fn solve_with_drag_on_fixed_point_keeps_point_anchored() {
        let base = Sketch::new(xy_plane());
        let (with_point, outs) = apply(
            &base,
            vec![SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(
                0.0, 0.0,
            )))],
        );
        let p = entity_id(&outs[0]);
        let sketch = apply(
            &with_point,
            vec![SketchEdit::AddRelation(SketchRelation::Fix(p))],
        )
        .0;
        let target = Point2::from_mm(8.0, 5.0);
        let Ok(dragged) = sketch.solve_with_drag(p, target, generous_budget()) else {
            panic!("drag on Fix'd point should still solve");
        };
        let (x, y) = point_coords(&dragged)[0];
        assert!(
            x.abs() < 1e-9 && y.abs() < 1e-9,
            "Fix overrides drag: ({x}, {y}) should stay at origin",
        );
    }

    #[test]
    fn solve_is_bit_identical_across_repeated_invocations() {
        let sketch = constrained_rectangle();
        let Ok(first) = sketch.solve() else {
            panic!("rectangle solves once");
        };
        let Ok(second) = sketch.solve() else {
            panic!("rectangle solves twice");
        };
        let lhs = point_coords(&first);
        let rhs = point_coords(&second);
        lhs.iter().zip(rhs.iter()).for_each(|(a, b)| {
            assert_eq!(
                a.0.to_bits(),
                b.0.to_bits(),
                "x must match bit-for-bit: {a:?} vs {b:?}",
            );
            assert_eq!(
                a.1.to_bits(),
                b.1.to_bits(),
                "y must match bit-for-bit: {a:?} vs {b:?}",
            );
        });
    }

    #[test]
    fn over_defined_conflicts_are_identical_across_repeated_invocations() {
        let (sketch, _) = three_conflicting_linear_dims_fixture();
        let Err(SolverError::OverDefined { conflicts: first }) = sketch.solve() else {
            panic!("conflicting fixture must surface OverDefined on first solve");
        };
        let Err(SolverError::OverDefined { conflicts: second }) = sketch.solve() else {
            panic!("conflicting fixture must surface OverDefined on second solve");
        };
        assert_eq!(
            first, second,
            "MUS conflict ordering must be identical across runs",
        );
    }

    #[test]
    fn drag_is_bit_identical_across_repeated_invocations() {
        let (sketch, _a, b) = draggable_horizontal_line();
        let target = Point2::from_mm(13.5, 0.0);
        let Ok(first) = sketch.solve_with_drag(b, target, generous_budget()) else {
            panic!("first drag solves");
        };
        let Ok(second) = sketch.solve_with_drag(b, target, generous_budget()) else {
            panic!("second drag solves");
        };
        let lhs = point_coords(&first);
        let rhs = point_coords(&second);
        lhs.iter().zip(rhs.iter()).for_each(|(a, b)| {
            assert_eq!(a.0.to_bits(), b.0.to_bits());
            assert_eq!(a.1.to_bits(), b.1.to_bits());
        });
    }

    #[cfg(not(debug_assertions))]
    #[test]
    fn drag_resolve_completes_inside_frame_budget() {
        use std::time::Instant;
        let (sketch, _a, b) = draggable_horizontal_line();
        (0..16).for_each(|i| {
            let f = f64::from(i);
            let target = Point2::from_mm(8.0 + 0.1 * f, 0.0);
            let started = Instant::now();
            let Ok(_) = sketch.solve_with_drag(b, target, BudgetCeiling::FRAME_16MS) else {
                panic!("drag solve must converge inside budget at step {i}");
            };
            let elapsed = started.elapsed();
            assert!(
                elapsed <= core::time::Duration::from_millis(16),
                "drag step {i} took {elapsed:?}, exceeding 16 ms budget",
            );
        });
    }

    mod determinism {
        use super::*;
        use proptest::prelude::*;

        #[derive(Copy, Clone, Debug)]
        struct DragSeed {
            base_x: i32,
            base_y: i32,
            target_dx: i32,
            target_dy: i32,
            length: u32,
        }

        fn arb_drag_seed() -> impl Strategy<Value = DragSeed> {
            (
                -10_000_i32..10_000,
                -10_000_i32..10_000,
                -20_000_i32..20_000,
                -20_000_i32..20_000,
                500_u32..50_000,
            )
                .prop_map(|(base_x, base_y, target_dx, target_dy, length)| DragSeed {
                    base_x,
                    base_y,
                    target_dx,
                    target_dy,
                    length,
                })
        }

        fn build_horizontal_line(seed: DragSeed) -> (Sketch, SketchEntityId) {
            let bx = f64::from(seed.base_x) * 1e-3;
            let by = f64::from(seed.base_y) * 1e-3;
            let length_mm_value = f64::from(seed.length) * 1e-3;
            let base = Sketch::new(xy_plane());
            let (with_points, outs) = apply(
                &base,
                vec![
                    SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(bx, by))),
                    SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(bx + 1.0, by + 1.0))),
                ],
            );
            let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
            let (with_line, line_outs) = apply(
                &with_points,
                vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
            );
            let line = entity_id(&line_outs[0]);
            let sketch = apply(
                &with_line,
                vec![
                    SketchEdit::AddRelation(SketchRelation::Fix(a)),
                    SketchEdit::AddRelation(SketchRelation::Horizontal(line)),
                    SketchEdit::AddDimension(SketchDimension::Linear {
                        a,
                        b,
                        value: mm_val(length_mm_value),
                        kind: DimensionKind::Driving,
                    }),
                ],
            )
            .0;
            (sketch, b)
        }

        fn assert_coord_pairs_bit_identical(
            lhs: &[(f64, f64)],
            rhs: &[(f64, f64)],
        ) -> Result<(), TestCaseError> {
            lhs.iter().zip(rhs.iter()).try_for_each(|(a, b)| {
                prop_assert_eq!(a.0.to_bits(), b.0.to_bits());
                prop_assert_eq!(a.1.to_bits(), b.1.to_bits());
                Ok(())
            })
        }

        proptest! {
            #[test]
            fn solve_is_bit_identical_for_random_horizontal_lines(seed in arb_drag_seed()) {
                let (sketch, _b) = build_horizontal_line(seed);
                let Ok(first) = sketch.solve() else {
                    return Ok(());
                };
                let Ok(second) = sketch.solve() else {
                    unreachable!("first solve succeeded; second cannot diverge under determinism");
                };
                assert_coord_pairs_bit_identical(&point_coords(&first), &point_coords(&second))?;
            }

            #[test]
            fn drag_is_bit_identical_for_random_horizontal_lines(seed in arb_drag_seed()) {
                let (sketch, drag_id) = build_horizontal_line(seed);
                let tx = f64::from(seed.base_x + seed.target_dx) * 1e-3;
                let ty = f64::from(seed.base_y + seed.target_dy) * 1e-3;
                let target = Point2::from_mm(tx, ty);
                let Ok(first) = sketch.solve_with_drag(drag_id, target, generous_budget()) else {
                    return Ok(());
                };
                let Ok(second) = sketch.solve_with_drag(drag_id, target, generous_budget()) else {
                    unreachable!("first drag succeeded; second must too under determinism");
                };
                assert_coord_pairs_bit_identical(&point_coords(&first), &point_coords(&second))?;
            }
        }
    }

    #[test]
    fn arc_intrinsic_residual_tags_entity_origin() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(2.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 2.0))),
            ],
        );
        let [c, s, e] = [0_usize, 1, 2].map(|i| entity_id(&outs[i]));
        let sketch = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::arc(c, s, e, false))],
        )
        .0;
        let arc_id = sketch.entity_order()[3];
        let (system, mapping) = sketch.lower();
        assert_eq!(system.row_count(), 1, "one intrinsic row per arc");
        let got = mapping.item_of_residual(ResidualIndex::new(0));
        assert_eq!(got, Some(SketchItemId::Entity(arc_id)));
    }

    #[test]
    fn status_fully_constrained_rectangle_is_fully_defined() {
        let sketch = constrained_rectangle();
        let report = sketch.status();
        assert_eq!(report.status(), SketchStatus::FullyDefined);
        assert!(report.offending().is_empty());
        assert_eq!(report.dof().value(), 0);
    }

    #[test]
    fn status_free_line_is_under_defined() {
        let base = Sketch::new(xy_plane());
        let (with_points, outs) = apply(
            &base,
            vec![
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(0.0, 0.0))),
                SketchEdit::AddEntity(SketchEntity::point(Point2::from_mm(1.0, 3.0))),
            ],
        );
        let [a, b] = [0_usize, 1].map(|i| entity_id(&outs[i]));
        let sketch = apply(
            &with_points,
            vec![SketchEdit::AddEntity(SketchEntity::line(a, b, false))],
        )
        .0;
        let report = sketch.status();
        assert_eq!(report.status(), SketchStatus::UnderDefined);
        assert!(report.offending().is_empty());
        assert!(report.dof().value() > 0);
    }

    #[test]
    fn status_three_conflicting_dims_is_over_defined() {
        let (sketch, dim_ids) = three_conflicting_linear_dims_fixture();
        let report = sketch.status();
        assert_eq!(report.status(), SketchStatus::OverDefined);
        assert!(!report.offending().is_empty());
        let added: BTreeSet<SketchItemId> = dim_ids
            .iter()
            .copied()
            .map(SketchItemId::Dimension)
            .collect();
        assert!(report.offending().iter().all(|c| added.contains(c)));
    }
}
