ogeom_algo/

check.rs

//! Checking a shape against the model's invariants.
//!
//! Everything in `docs/DATA_MODEL.md` that can be checked with geometry in
//! hand, checked in one place. The builders enforce what they can at the moment
//! of construction; this catches what only becomes wrong later: an edge whose
//! tolerance was widened past its face's, a shell left open by an operation
//! that dropped a face, a pcurve that has stopped agreeing with its curve.
//!
//! # It reports, it does not judge
//!
//! The result is a list of what is wrong and where, not a boolean. A boolean
//! answers "should I panic", which is never the question: an imported shape is
//! usually invalid in some specific, fixable way, and healing it needs to know
//! which way. A caller that only wants the boolean asks
//! [`Diagnosis::is_valid`].
//!
//! # Severity is not a comment
//!
//! [`Severity::Broken`] means an algorithm reading this shape will get a wrong
//! answer rather than an error: an open shell has no inside, so every
//! containment test against it is a coin toss. [`Severity::Suspect`] means
//! something is out of order but every operation will still behave: a tolerance
//! larger than the feature it describes is alarming and not yet wrong.
//!
//! The distinction is what lets a pipeline decide. Booleans refuse `Broken`
//! input because they would produce nonsense from it; they proceed on
//! `Suspect` because refusing would reject most real imported geometry.

use ogeom_core::{FastMap, FastSet};
use std::fmt;

use ogeom_core::{OgeomResult, Tolerances, ogeom_bail};
use ogeom_geom::{Curve2d, Curve3d, Surface};
use ogeom_math::Point2;
use ogeom_mesh::Deflection;
use ogeom_topo::{EdgeRepr, Filter, Model, Shape, ShapeType, TShapeId, explore, explore_unique};

/// How badly a problem breaks the shape.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Severity {
    /// Out of order, but every operation will still behave.
    Suspect,
    /// An algorithm reading this shape will get a wrong answer, not an error.
    Broken,
}

/// One thing wrong with a shape.
#[derive(Debug, Clone, PartialEq)]
pub struct Problem {
    /// How badly it breaks things.
    pub severity: Severity,
    /// The sub-shape it is about.
    pub at: Shape,
    /// What kind of sub-shape that is, so a report reads without a lookup.
    pub kind: ShapeType,
    /// What is wrong, in a sentence.
    pub what: String,
}

impl fmt::Display for Problem {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mark = match self.severity {
            Severity::Broken => "broken",
            Severity::Suspect => "suspect",
        };
        write!(f, "[{mark}] {:?}: {}", self.kind, self.what)
    }
}

/// Everything wrong with a shape.
#[derive(Debug, Clone, PartialEq, Default)]
pub struct Diagnosis {
    /// The problems found, in the order they were found.
    pub problems: Vec<Problem>,
}

impl Diagnosis {
    /// Whether nothing is wrong at all.
    #[must_use]
    pub fn is_valid(&self) -> bool {
        self.problems.is_empty()
    }

    /// Whether anything would make an algorithm answer wrongly.
    ///
    /// The question a boolean or a mass property should ask before starting.
    #[must_use]
    pub fn is_usable(&self) -> bool {
        !self.problems.iter().any(|p| p.severity == Severity::Broken)
    }

    /// The worst severity found.
    #[must_use]
    pub fn worst(&self) -> Option<Severity> {
        self.problems.iter().map(|p| p.severity).max()
    }

    /// The problems of one severity.
    #[must_use]
    pub fn of(&self, severity: Severity) -> Vec<&Problem> {
        self.problems
            .iter()
            .filter(|p| p.severity == severity)
            .collect()
    }

    fn note(&mut self, severity: Severity, at: &Shape, kind: ShapeType, what: String) {
        self.problems.push(Problem {
            severity,
            at: at.clone(),
            kind,
            what,
        });
    }
}

impl fmt::Display for Diagnosis {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.problems.is_empty() {
            return write!(f, "valid");
        }
        for (i, problem) in self.problems.iter().enumerate() {
            if i > 0 {
                writeln!(f)?;
            }
            write!(f, "{problem}")?;
        }
        Ok(())
    }
}

/// Check a shape and everything below it.
///
/// # Errors
///
/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if a handle does not
/// resolve. A dangling handle is not a *finding*; it means the shape and the
/// model do not belong together, and every other answer would be about
/// something that is not there.
pub fn check(model: &Model, shape: &Shape, tol: Tolerances) -> OgeomResult<Diagnosis> {
    check_kept(model, shape, tol, &crate::ProbeCache::new())
}

/// [`check`], probing faces' orientation through `kept`: a caller that
/// checks a model, mends it and checks it again pays once for what the
/// mend left alone.
///
/// # Errors
///
/// As [`check`].
pub fn check_kept(
    model: &Model,
    shape: &Shape,
    tol: Tolerances,
    kept: &crate::ProbeCache,
) -> OgeomResult<Diagnosis> {
    if model.node(shape).is_none() {
        ogeom_bail!(Dangling, "shape refers to a node not in this model");
    }
    let mut found = Diagnosis::default();

    // Every distinct sub-shape from one walk, by type. The walk is
    // pre-order, so each type's shapes come in the order a walk for that
    // type alone would give.
    let mut distinct: FastMap<ShapeType, Vec<Shape>> = FastMap::default();
    let mut seen = FastSet::default();
    for sub in explore(model, shape, Filter::All)? {
        if seen.insert(ogeom_topo::SameKey(sub.clone())) {
            distinct.entry(model.kind_of(&sub)?).or_default().push(sub);
        }
    }
    let of = |kind: ShapeType| distinct.get(&kind).map_or(&[][..], Vec::as_slice);

    each(of(ShapeType::Edge), &mut found, |edge, out| {
        check_edge(model, edge, tol, out)
    })?;
    each(of(ShapeType::Wire), &mut found, |wire, out| {
        check_wire(model, wire, tol, out)
    })?;
    each(of(ShapeType::Face), &mut found, |face, out| {
        check_face(model, face, tol, out)?;
        check_face_chart(model, face, &|_| false, tol, out)?;
        check_seam_sides(model, face, tol, out)
    })?;
    note_out_and_back(crate::out_and_back(model, shape, tol)?, &mut found);
    for shell in of(ShapeType::Shell) {
        check_shell(model, shell, &mut found)?;
    }
    for solid in of(ShapeType::Solid) {
        let crossings = crate::self_cross::crossings(model, solid, kept.meshes(), tol)?;
        check_orientation(model, solid, tol, kept, !crossings.is_empty(), &mut found)?;
        note_crossings(crossings, &mut found);
    }
    // Tolerance containment: a face is no looser than its edges, an edge no
    // looser than its vertices, checked through every level below each.
    each(of(ShapeType::Face), &mut found, |face, out| {
        compare(model, face, ShapeType::Face, out)
    })?;
    each(of(ShapeType::Edge), &mut found, |edge, out| {
        compare(model, edge, ShapeType::Edge, out)
    })?;
    Ok(found)
}

/// Run one check over every shape in parallel, each into its own findings,
/// and append them to `found` in shape order: the diagnosis a serial walk
/// gives. The first shape in order that fails fails the whole.
fn each(
    shapes: &[Shape],
    found: &mut Diagnosis,
    one: impl Fn(&Shape, &mut Diagnosis) -> OgeomResult<()> + Sync,
) -> OgeomResult<()> {
    let parts = ogeom_core::parallel::map_ordered(shapes, |_, shape| {
        let mut part = Diagnosis::default();
        one(shape, &mut part).map(|()| part)
    });
    for part in parts {
        found.problems.extend(part?.problems);
    }
    Ok(())
}

/// Report every face of a solid that faces into its material, and every
/// face that reads facing out of it at one place and into it at another.
///
/// A face is read at two places spread over it, not one: on a boundary that
/// passes through itself or overlaps, a face can read out over part of its
/// extent and in over the rest, and which part a single probe lands on
/// would decide the answer. A probe can misread, though, and a face of a
/// sound solid must not be named on a misreading. A face read both ways is
/// named where the solid's boundary was found `crossed`, where its first
/// place (the one a single probe asks) reads it facing in, or where the
/// solid's winding number bears out a place reading it facing in; else the
/// inward reading is taken for the probe's and nothing is named.
fn check_orientation(
    model: &Model,
    solid: &Shape,
    tol: Tolerances,
    kept: &crate::ProbeCache,
    crossed: bool,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let boundary = match probe_boundary(model, solid, tol) {
        Ok(boundary) => boundary.keeping(kept),
        Err(e @ (ogeom_core::OgeomError::Cancelled | ogeom_core::OgeomError::Dangling(_))) => {
            return Err(e);
        }
        Err(_) => return Ok(()),
    };
    let faces = explore_unique(model, solid, ShapeType::Face)?;
    let read =
        ogeom_core::parallel::map_ordered(&faces, |_, face| -> OgeomResult<Option<String>> {
            let places = face_places(
                model,
                face,
                &boundary,
                PLACES_READ,
                PLACES_READ + SPARE,
                tol,
            )?;
            let read = Readings::of(&places);
            if !read.disagree() {
                return Ok((read.verdict() == Some(true)).then(|| {
                    "the face's outward normal points into the material: its \
                 orientation is reversed"
                        .to_string()
                }));
            }
            let mut credible = crossed || places.first().is_some_and(|p| p.inward);
            for place in places.iter().filter(|p| p.inward) {
                if credible {
                    break;
                }
                credible = read_place(model, face, &boundary, place, true, tol)? == Some(true);
            }
            Ok(credible.then(|| {
                format!(
                    "the face reads facing out of the material at {} of the \
                 places probed and into it at {}: the boundary passes \
                 through itself or overlaps",
                    read.out, read.inward
                )
            }))
        });
    for (face, read) in faces.iter().zip(read) {
        if let Some(what) = read? {
            found.note(Severity::Broken, face, ShapeType::Face, what);
        }
    }
    Ok(())
}

/// How many places `check` reads each face at: the largest triangle's
/// middle and that of the large triangle farthest from it. Each place costs a
/// probe's rays, and the faces of a boundary crossing itself are named by
/// the crossing as well.
const PLACES_READ: usize = 2;

/// How many places, over a shell's faces, must agree before they say which
/// way the shell faces, where one probe is not to decide it.
pub(crate) const AGREEING: usize = 3;

/// What the probes of a face read: at how many places its outside was
/// found outside the material, and at how many inside it.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub(crate) struct Readings {
    /// Places where the face faces out of the material.
    pub(crate) out: usize,
    /// Places where it faces into it.
    pub(crate) inward: usize,
}

impl Readings {
    /// What `places` read, counted.
    fn of(places: &[Place]) -> Self {
        let inward = places.iter().filter(|p| p.inward).count();
        Self {
            out: places.len() - inward,
            inward,
        }
    }

    /// Whether the face faces into the material: `None` where nothing
    /// read, or the places read disagree.
    pub(crate) const fn verdict(self) -> Option<bool> {
        match (self.out > 0, self.inward > 0) {
            (true, false) => Some(false),
            (false, true) => Some(true),
            _ => None,
        }
    }

    /// Whether some places read out and others in.
    pub(crate) const fn disagree(self) -> bool {
        self.out > 0 && self.inward > 0
    }

    /// How many places read at all.
    pub(crate) const fn count(self) -> usize {
        self.out + self.inward
    }
}

/// Note every pair of consecutive edges that runs out and back along one
/// path ([`out_and_back`](crate::out_and_back)): the face's region is the
/// same without that stretch of its boundary, but its tip is a vertex that
/// bounds no corner, which every boolean through the face meets as a
/// strand and a mesher has to strip.
fn note_out_and_back(pairs: Vec<crate::OutAndBack>, found: &mut Diagnosis) {
    for pair in pairs {
        let [out, back] = pair.edges;
        let w = pair.wire;
        let what = match pair.notch {
            None => format!(
                "edge {out} of wire {w} runs out and edge {back} straight back along \
                 it: the pair bounds nothing"
            ),
            Some(notch) => {
                let (long, short) = if notch.longer == 0 {
                    (out, back)
                } else {
                    (back, out)
                };
                format!(
                    "edge {short} of wire {w} runs along part of edge {long} and \
                     back: that stretch of the boundary bounds nothing"
                )
            }
        };
        found.note(Severity::Suspect, &pair.face, ShapeType::Face, what);
    }
}

/// Report every place where a solid's boundary passes through itself: a
/// face folded through itself, or two faces crossing away from the edges
/// they share.
fn note_crossings(crossings: Vec<crate::self_cross::SelfCrossing>, found: &mut Diagnosis) {
    for crossing in crossings {
        let at = crossing.at;
        let whom = if crossing.face.is_same(&crossing.other) {
            "itself"
        } else {
            "another face of the solid"
        };
        found.note(
            Severity::Broken,
            &crossing.face,
            ShapeType::Face,
            format!(
                "the face passes through {whom} at ({:.6}, {:.6}, {:.6}): the \
                 boundary crosses itself, so it bounds no single region",
                at.x, at.y, at.z
            ),
        );
    }
}

/// The faces of a solid that face into its material.
///
/// A face's flag is the only thing that says which side of its surface the
/// material is on, and a flipped one leaves every edge used twice and the
/// shell closed: nothing topological sees it. Nor do the flags asked about
/// each other along shared edges: that walk reads which side of an edge a
/// face lies on from its chart, and where the chart cannot say (an apex, a
/// boundary whose middle is not inside it) it has to take the flags as they
/// come. So every face is probed: a point a little off it along its outward
/// normal must lie outside the material and the point as far the other way
/// inside it. A face whose outside is inside is named; a probe that cannot
/// tell names nothing, so a face is never named on a guess. A face whose
/// chart cannot be walked is not asked at all.
///
/// # Errors
///
/// [`OgeomError::Cancelled`](ogeom_core::OgeomError::Cancelled) and
/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) only; a
/// question the geometry cannot answer names no face.
pub fn inside_out_faces(model: &Model, solid: &Shape, tol: Tolerances) -> OgeomResult<Vec<Shape>> {
    inside_out_faces_kept(model, solid, tol, &crate::ProbeCache::new())
}

/// [`inside_out_faces`], through `kept`: see [`check_kept`].
///
/// # Errors
///
/// As [`inside_out_faces`].
pub fn inside_out_faces_kept(
    model: &Model,
    solid: &Shape,
    tol: Tolerances,
    kept: &crate::ProbeCache,
) -> OgeomResult<Vec<Shape>> {
    let boundary = match probe_boundary(model, solid, tol) {
        Ok(boundary) => boundary.keeping(kept),
        // A question the geometry cannot answer (an open shell, a chart
        // walk off its domain) is no finding; only cancellation and a
        // broken model are errors.
        Err(e @ (ogeom_core::OgeomError::Cancelled | ogeom_core::OgeomError::Dangling(_))) => {
            return Err(e);
        }
        Err(_) => return Ok(Vec::new()),
    };
    let faces = explore_unique(model, solid, ShapeType::Face)?;
    turned_in_against(model, &boundary, &faces, tol)
}

/// The boundary of `solid` its faces are probed against, as
/// [`inside_out_faces`] builds it.
pub(crate) fn probe_boundary(
    model: &Model,
    solid: &Shape,
    tol: Tolerances,
) -> OgeomResult<crate::SolidBoundary> {
    crate::SolidBoundary::of(model, solid, tol.confusion() * 1e4, tol)
}

/// The faces of `faces` whose probe against `boundary` finds material on
/// their outside, probed in parallel.
fn turned_in_against(
    model: &Model,
    boundary: &crate::SolidBoundary,
    faces: &[Shape],
    tol: Tolerances,
) -> OgeomResult<Vec<Shape>> {
    let inward = ogeom_core::parallel::map_ordered(faces, |_, face| {
        faces_inward(model, face, boundary, tol)
    });
    let mut out = Vec::new();
    for (face, inward) in faces.iter().zip(inward) {
        if inward? == Some(true) {
            out.push(face.clone());
        }
    }
    Ok(out)
}

/// Whether a face's outward normal points into the solid's material; `None`
/// where the probe cannot tell: the first place of [`face_readings`] that
/// reads decides, among as many triangles as a reading of three places
/// tries.
pub(crate) fn faces_inward(
    model: &Model,
    face: &Shape,
    boundary: &crate::SolidBoundary,
    tol: Tolerances,
) -> OgeomResult<Option<bool>> {
    const PROBES: usize = 3;
    Ok(face_places(model, face, boundary, 1, PROBES + SPARE, tol)?
        .first()
        .map(|p| p.inward))
}

/// Which way a face faces at up to `wanted` places spread over it.
///
/// Probed at the middle of the face's largest mesh triangle, then at the
/// middles of the large triangles farthest from those already probed, so
/// that the places read spread over the face rather than crowd where its
/// largest triangles lie. A place that cannot tell is passed over, and a
/// few more are tried than wanted. Each place is read by [`read_place`],
/// its shortest step well clear of the band within which a point counts as
/// on the face.
pub(crate) fn face_readings(
    model: &Model,
    face: &Shape,
    boundary: &crate::SolidBoundary,
    wanted: usize,
    tol: Tolerances,
) -> OgeomResult<Readings> {
    Ok(Readings::of(&face_places(
        model,
        face,
        boundary,
        wanted,
        wanted + SPARE,
        tol,
    )?))
}

/// How many places beyond those wanted are tried before giving up.
const SPARE: usize = 2;

/// The places of [`face_readings`], up to `wanted` of them among the first
/// `tried` triangles, each with what it read, in the order they were read.
fn face_places(
    model: &Model,
    face: &Shape,
    boundary: &crate::SolidBoundary,
    wanted: usize,
    tried: usize,
    tol: Tolerances,
) -> OgeomResult<Vec<Place>> {
    /// How many of the largest triangles the places are chosen among.
    const CHOSEN_AMONG: usize = 32;
    // Meshed where the face stands in its own frame: a placement moves the
    // probe points with the material, but placed positions round, and the
    // rounding reorders triangles of one area. Where the face reads
    // differently over its extent, that would let a rigid motion change
    // the answer.
    let own = face.located(ogeom_topo::Location::identity());
    let mut places: Vec<Place> = Vec::new();
    let Ok(mesh) = ogeom_mesh::triangulate_face_kept(
        model,
        &own,
        Deflection::default(),
        boundary.kept().meshes(),
        tol,
    ) else {
        return Ok(places);
    };
    if mesh.parameters.len() != mesh.positions.len() {
        return Ok(places);
    }
    let Some(data) = model.node(face).and_then(|n| n.data().as_face()) else {
        return Ok(places);
    };
    let Some(surface) = model.geometry().surface(data.surface) else {
        return Ok(places);
    };
    let area = |t: &[u32; 3]| {
        let [a, b, c] = t.map(|i| mesh.positions[i as usize]);
        (b - a).cross(c - a).magnitude()
    };
    let middle = |t: &[u32; 3]| {
        let [a, b, c] = t.map(|i| mesh.positions[i as usize]);
        a + ((b - a) + (c - a)) / 3.0
    };
    let mut largest: Vec<(f64, &[u32; 3])> = mesh.triangles.iter().map(|t| (area(t), t)).collect();
    largest.sort_by(|x, y| y.0.total_cmp(&x.0));
    largest.truncate(CHOSEN_AMONG);
    // The largest first, then each time the one farthest from every
    // middle already taken; ties to the larger.
    let mut order: Vec<(f64, &[u32; 3])> = Vec::with_capacity(largest.len());
    let mut apart: Vec<f64> = vec![f64::INFINITY; largest.len()];
    let mut taken = vec![false; largest.len()];
    for _ in 0..largest.len() {
        let mut best: Option<usize> = None;
        for k in 0..largest.len() {
            if !taken[k] && best.is_none_or(|b| apart[k] > apart[b]) {
                best = Some(k);
            }
        }
        let Some(k) = best else { break };
        taken[k] = true;
        order.push(largest[k]);
        let at = middle(largest[k].1);
        for (j, (_, t)) in largest.iter().enumerate() {
            apart[j] = apart[j].min(middle(t).distance(at));
        }
    }
    let placement = face.transform(model.datums())?;
    let flip = face.orientation() == ogeom_topo::Orientation::Reversed;
    // Twenty times the band a point counts as on the face within, and
    // never below a thousand confusion distances.
    let shortest = data.tolerance.get().max(tol.confusion() * 1e3) * 20.0;
    // The band a point counts as on the face's boundary within.
    let on_face = tol.confusion().max(data.tolerance.get());
    let mut trim: Option<crate::classify::FaceTrim<'_>> = None;
    for (size, triangle) in order.into_iter().take(tried) {
        if places.len() >= wanted {
            break;
        }
        let uv = triangle.map(|i| mesh.parameters[i as usize]);
        let (u, v) = (
            (uv[0].0 + uv[1].0 + uv[2].0) / 3.0,
            (uv[0].1 + uv[1].1 + uv[2].1) / 3.0,
        );
        let (Ok(point), Ok(normal)) = (surface.point_at(u, v, tol), surface.normal_at(u, v, tol))
        else {
            continue;
        };
        let point = placement.apply(point);
        // The chart middle of a triangle lies on the face only where the
        // face's region is convex there: a thin ring's longest triangles
        // span its hole, and their middles stand in it, off the face, where
        // the two sides read whatever surrounds the hole. The face's trim is
        // drawn at the boundary's own ring chord, whose band a face narrower
        // than it (a thin sheet's rim) lies within whole, and drawn once for
        // every place asked.
        if trim.is_none() {
            let held = Deflection {
                chord: tol.confusion() * 1e4,
                ..Deflection::default()
            };
            trim = Some(crate::classify::FaceTrim::of(model, face, held, tol)?);
        }
        let Some(drawn) = trim.as_ref() else {
            continue;
        };
        if drawn.holds(model, (u, v), on_face, tol)? == crate::Containment::Out {
            continue;
        }
        let mut outward = placement.apply_vector(normal.vector());
        if flip {
            outward = -outward;
        }
        let first = (size.sqrt() * 0.05).max(tol.confusion() * 1e5);
        let mut place = Place {
            point,
            outward,
            ladder: Ladder { first, shortest },
            inward: false,
        };
        if let Some(inward) = read_place(model, face, boundary, &place, false, tol)? {
            place.inward = inward;
            places.push(place);
        }
    }
    Ok(places)
}

/// One place a face was read at, and whether it read facing into the
/// material there.
#[derive(Debug, Clone, Copy)]
struct Place {
    point: ogeom_math::Point,
    outward: ogeom_math::Vector,
    ladder: Ladder,
    inward: bool,
}

/// The steps a place is read at: from `first` down by tenths to `shortest`.
#[derive(Debug, Clone, Copy)]
struct Ladder {
    first: f64,
    shortest: f64,
}

/// Whether the face faces into the material at a place, read a step off it
/// each way along its outward normal: by the boundary's rays, or by its
/// winding number at the chord it was first meshed at where `by_winding`
/// says; `None` where no step tells.
///
/// The first step is a fraction of the probed triangle's size, and shorter
/// steps follow: a step longer than the solid is thick lands past its far
/// side, and one across a gap narrower than the step lands in the material
/// beyond, and either leaves both points on the same side.
fn read_place(
    model: &Model,
    face: &Shape,
    boundary: &crate::SolidBoundary,
    place: &Place,
    by_winding: bool,
    tol: Tolerances,
) -> OgeomResult<Option<bool>> {
    let side = |at| -> Option<crate::Containment> {
        if by_winding {
            boundary.wound_coarsely(model, at, tol)
        } else {
            boundary.holds(model, at, tol).ok()
        }
    };
    let (point, outward, ladder) = (place.point, place.outward, place.ladder);
    let mut step = ladder.first;
    loop {
        ogeom_core::progress::checkpoint()?;
        // A step reads the face's two sides only where it meets no
        // other face on the way: off a sliver folded back between its
        // neighbours, a step longer than the sliver is wide passes under
        // one of them and reads the other's side. Off a sheet's rim the
        // same step runs between the broad faces and meets none.
        let (out_at, in_at) = (point + outward * step, point - outward * step);
        let clear = boundary.clear_between(model, point, out_at, face, tol)?
            && boundary.clear_between(model, point, in_at, face, tol)?;
        if clear && let (Some(outside), Some(inside)) = (side(out_at), side(in_at)) {
            match (outside, inside) {
                (crate::Containment::In, crate::Containment::Out) => return Ok(Some(true)),
                (crate::Containment::Out, crate::Containment::In) => return Ok(Some(false)),
                _ => {}
            }
        }
        if step <= ladder.shortest {
            return Ok(None);
        }
        step = (step * 0.1).max(ladder.shortest);
    }
}

/// Check that a shape's *tessellation* agrees with its topology.
///
/// Separate from [`check`] because it needs a deflection, and because it asks a
/// different question: not "is this shape well formed" but "do its two
/// descriptions of itself agree". A shell whose edges are all used twice is
/// closed as far as the topology knows. If the mesh built from it still has a
/// boundary, then some face's pcurves do not cover the region its edges claim
/// to bound, and the topology cannot see that, because the defect is entirely
/// in parameter space.
///
/// That failure is worth its own function because it is *invisible* to every
/// other check. Face counts look right, the shell closes, each face
/// triangulates without error, and the solid still has a slit down it. The
/// first thing to notice is usually a volume that is quietly wrong.
///
/// Reports the position of the unshared edges, not just their number: where the
/// mesh comes apart is the whole diagnosis, and a count sends you looking.
///
/// # Errors
///
/// As [`ogeom_mesh::triangulate()`].
pub fn check_tessellation(
    model: &Model,
    shape: &Shape,
    deflection: Deflection,
    tol: Tolerances,
) -> OgeomResult<Diagnosis> {
    let mut found = Diagnosis::default();

    for shell in explore_unique(model, shape, ShapeType::Shell)? {
        // An open shell is *meant* to have a boundary, so a mesh with one is
        // agreement, not disagreement. Only a shell the topology calls closed
        // makes a claim the mesh can contradict.
        if !crate::build::is_shell_closed(model, &shell)? {
            continue;
        }
        let mesh = ogeom_mesh::triangulate(model, &shell, deflection, tol)?;
        if mesh.is_empty() {
            found.note(
                Severity::Broken,
                &shell,
                ShapeType::Shell,
                "the topology says this shell is closed and it tessellates to \
                 nothing at all"
                    .into(),
            );
            continue;
        }
        if let Some(report) = open_edges(&mesh) {
            found.note(Severity::Broken, &shell, ShapeType::Shell, report);
        }
    }
    Ok(found)
}

/// Describe a mesh's unshared edges, or `None` if every edge is shared twice.
fn open_edges(mesh: &ogeom_topo::Triangulation) -> Option<String> {
    let mut uses: FastMap<(u32, u32), usize> = FastMap::default();
    for triangle in &mesh.triangles {
        for i in 0..3 {
            let (a, b) = (triangle[i], triangle[(i + 1) % 3]);
            *uses.entry((a.min(b), a.max(b))).or_default() += 1;
        }
    }

    let mut loose: Vec<&(u32, u32)> = uses
        .iter()
        .filter(|(_, n)| **n != 2)
        .map(|(e, _)| e)
        .collect();
    if loose.is_empty() {
        return None;
    }
    // Deterministic: a diagnosis that names a different edge each run is one
    // nobody can act on.
    loose.sort_unstable();

    let sample: Vec<String> = loose
        .iter()
        .take(3)
        .map(|(a, b)| {
            let (p, q) = (mesh.positions[*a as usize], mesh.positions[*b as usize]);
            format!(
                "({:.6}, {:.6}, {:.6})-({:.6}, {:.6}, {:.6})",
                p.x, p.y, p.z, q.x, q.y, q.z
            )
        })
        .collect();

    Some(format!(
        "the topology says this shell is closed, but its mesh has {} triangle \
         edge(s) not shared by two triangles, so the tessellated solid has a \
         slit in it. The first are at {}. This is a parameter-space defect \
         (some face's pcurves do not cover the region its edges bound), and no \
         topological check can see it",
        loose.len(),
        sample.join(", ")
    ))
}

/// An edge's curve must reach the vertices it claims to join, and its
/// representations must agree with each other.
fn check_edge(
    model: &Model,
    edge: &Shape,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let Some(node) = model.node(edge) else {
        ogeom_bail!(Dangling, "edge is not in this model");
    };
    let Some(data) = node.data().as_edge() else {
        return Ok(());
    };
    let reach = data.tolerance.get().max(tol.confusion());

    let Some(EdgeRepr::Curve3d { curve, range, .. }) = data.curve3d() else {
        // A degenerate edge is *supposed* to have no curve. Any other edge
        // without one has nowhere in space it runs, and every algorithm that
        // walks a boundary will skip it silently.
        if !data.degenerate {
            found.note(
                Severity::Broken,
                edge,
                ShapeType::Edge,
                "no curve in space, and not marked degenerate; a boundary walk \
                 will step over it without noticing"
                    .into(),
            );
        }
        return Ok(());
    };
    if data.degenerate {
        found.note(
            Severity::Suspect,
            edge,
            ShapeType::Edge,
            "marked degenerate but carries a curve in space".into(),
        );
    }
    let Some(geometry) = model.geometry().curve(*curve) else {
        ogeom_bail!(Dangling, "curve is not in this model");
    };

    let placement = edge.transform(model.datums())?;
    let bounds = model.children_of(edge)?;
    for (parameter, vertex) in [(range.0, bounds.first()), (range.1, bounds.last())] {
        let Some(vertex) = vertex else { continue };
        let Some((point, vertex_reach)) = model
            .node(vertex)
            .and_then(|n| n.data().as_vertex())
            .map(|v| (v.point, v.tolerance.get()))
        else {
            continue;
        };
        let placed = vertex.transform(model.datums())?.apply(point);
        let on_curve = placement.apply(geometry.point_at(parameter, tol)?);
        let gap = on_curve.distance(placed);
        // The junction's own stated tolerance is the radius within which
        // things meeting it may stray; the same acceptance construction
        // applies. A checker stricter than the builder would condemn what
        // the builder rightly admitted and honestly recorded.
        let reach = reach.max(vertex_reach);
        if gap > reach {
            found.note(
                Severity::Broken,
                edge,
                ShapeType::Edge,
                format!(
                    "curve stops {gap} from the vertex it should meet, outside \
                     its tolerance of {reach}; the boundary has a gap there"
                ),
            );
        }
    }

    check_spanned(
        model,
        edge,
        (geometry, *range),
        &placement,
        data.tolerance.get(),
        tol,
        found,
    )?;

    let curve_location = match data.curve3d() {
        Some(EdgeRepr::Curve3d { location, .. }) => location.clone(),
        _ => ogeom_topo::Location::identity(),
    };
    check_pcurves(
        model,
        edge,
        data,
        (geometry, *range, &curve_location),
        reach,
        tol,
        found,
    )?;
    Ok(())
}

/// An edge whose pcurve stands farther off its curve than the edge is long
/// is reported suspect.
///
/// The pcurve then describes some other stretch of its surface, one the
/// edge does not reach at its own scale: a fit whose end landed on the far
/// side of a closed chart runs the far way round it. Its tolerance covers
/// the gap, as it must for the edge to pass the containment tests, and is
/// then wider than the edge is long. A gap past the tolerance is broken
/// and reported by [`check_pcurves`], so only an edge no longer than its
/// tolerance is measured here.
///
/// An exact pcurve, paced like its curve or not, stands off it by no more
/// than the chord between two of its points, and is never reported. One
/// that is only within its tolerance of the edge can be: the test is a
/// heuristic, which is why the finding is suspect and not broken.
fn check_spanned(
    model: &Model,
    edge: &Shape,
    (curve, range): (&ogeom_geom::Curve, (f64, f64)),
    placement: &ogeom_math::Transform,
    tolerance: f64,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    if let Some((gap, length)) =
        spanned_past(model, edge, (curve, range), placement, tolerance, tol)?
    {
        found.note(
            Severity::Suspect,
            edge,
            ShapeType::Edge,
            format!(
                "has a pcurve {gap} off its curve, farther than the edge's own \
                 length of {length}: the pcurve describes another stretch of its \
                 surface, and the tolerance of {tolerance} covering it is wider \
                 than the edge"
            ),
        );
    }
    Ok(())
}

/// The length of an edge whose pcurves stand farther off its curve than
/// it is long, as [`check`](crate::check()) reports it suspect; `None`
/// where the edge is not reported, or has no curve.
///
/// # Errors
///
/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if the edge
/// or its geometry is not in `model`; as the curve's evaluation.
pub(crate) fn edge_spanned_past(
    model: &Model,
    edge: &Shape,
    tol: Tolerances,
) -> OgeomResult<Option<f64>> {
    let Some(data) = model.node(edge).and_then(|n| n.data().as_edge()) else {
        ogeom_bail!(Dangling, "edge is not in this model");
    };
    let Some(EdgeRepr::Curve3d { curve, range, .. }) = data.curve3d() else {
        return Ok(None);
    };
    let Some(geometry) = model.geometry().curve(*curve) else {
        ogeom_bail!(Dangling, "curve is not in this model");
    };
    let placement = edge.transform(model.datums())?;
    Ok(spanned_past(
        model,
        edge,
        (geometry, *range),
        &placement,
        data.tolerance.get(),
        tol,
    )?
    .map(|(_, length)| length))
}

/// The gap and the length of an edge at most `tolerance` long whose
/// pcurves stand farther off its curve than it is long, by more than the
/// confusion distance.
fn spanned_past(
    model: &Model,
    edge: &Shape,
    (curve, range): (&ogeom_geom::Curve, (f64, f64)),
    placement: &ogeom_math::Transform,
    tolerance: f64,
    tol: Tolerances,
) -> OgeomResult<Option<(f64, f64)>> {
    // A polyline through points of the edge in order is no longer than
    // the edge: where it is longer than the tolerance, so is the edge. The
    // chord between the ends is the one-piece polyline, and turns most
    // edges away for two evaluations.
    const PIECES: u32 = 16;
    let scale = placement.scale_factor().abs();
    let at = |f: f64| curve.point_at((range.1 - range.0).mul_add(f, range.0), tol);
    if at(0.0)?.distance(at(1.0)?) * scale > tolerance {
        return Ok(None);
    }
    let mut polyline = 0.0;
    let mut last = at(0.0)?;
    for i in 1..=PIECES {
        let next = at(f64::from(i) / f64::from(PIECES))?;
        polyline += last.distance(next);
        last = next;
    }
    if polyline * scale > tolerance {
        return Ok(None);
    }
    let Ok(length) = crate::length::curve_length(curve, range, tol) else {
        return Ok(None);
    };
    if length * scale > tolerance {
        return Ok(None);
    }
    let Some(gap) = crate::pcurve_gap::edge_pcurve_gap_sampled(model, edge, tol)? else {
        return Ok(None);
    };
    // Below the confusion tolerance a gap and a length are rounding: an
    // edge with no length has a gap of a few ulps.
    Ok((gap > length + tol.confusion()).then_some((gap, length)))
}

/// Verify that every pcurve lands where the 3D curve does, to the edge's
/// tolerance.
///
/// The tolerance is the radius about the curve within which every
/// description of the edge lies, so each pcurve lifted through its surface
/// stays inside it all along the edge, not only at its ends. An edge
/// claiming `same_parameter` is held to the claim: the lifted point at each
/// parameter within the tolerance of the curve's point at the same
/// parameter, since every algorithm evaluates whichever representation is
/// cheapest and assumes the answer interchangeable. An edge making no claim
/// may pace its pcurves differently, so a lifted point is measured against
/// the nearest point of the curve's stretch. A pcurve at another placement
/// than the curve describes the edge where that occurrence stands, and is
/// not compared.
fn check_pcurves(
    model: &Model,
    edge: &Shape,
    data: &ogeom_topo::EdgeData,
    (curve, range, location): (&ogeom_geom::Curve, (f64, f64), &ogeom_topo::Location),
    reach: f64,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    check_plain_pcurves_apart(model, edge, data, tol, found)?;
    let claimed = data.same_parameter();
    for repr in &data.representations {
        let (sides, pcurve_range, surface_id, at) = match repr {
            EdgeRepr::PCurve {
                curve,
                range,
                surface,
                location,
            } => ([Some(*curve), None], *range, *surface, location),
            EdgeRepr::Seam {
                forward,
                reversed,
                range,
                surface,
                location,
            } => (
                [Some(*forward), Some(*reversed)],
                *range,
                *surface,
                location,
            ),
            _ => continue,
        };
        if at != location {
            continue;
        }
        let Some(surface) = model.geometry().surface(surface_id) else {
            ogeom_bail!(Dangling, "an edge names geometry not in this model");
        };
        if let [Some(ahead), Some(back)] = sides {
            check_seam_closes(
                model,
                edge,
                (ahead, back, pcurve_range),
                surface,
                tol,
                found,
            )?;
        }
        for pcurve_id in sides.into_iter().flatten() {
            let Some(pcurve) = model.geometry().pcurve(pcurve_id) else {
                ogeom_bail!(Dangling, "an edge names geometry not in this model");
            };
            let Some((gap, t)) = pcurve_off_curve(
                (curve, range),
                (pcurve, pcurve_range),
                surface,
                reach,
                claimed,
                tol,
            )?
            else {
                continue;
            };
            let what = if claimed {
                format!(
                    "claims same_parameter but its pcurve is {gap} from its curve at \
                     parameter {t} of the range, outside the edge's tolerance of {reach}"
                )
            } else {
                format!(
                    "has a pcurve that leaves its curve by {gap} at parameter {t} of \
                     the range, outside the edge's tolerance of {reach}; the face it \
                     bounds and the curve its neighbour follows part there"
                )
            };
            found.note(Severity::Broken, edge, ShapeType::Edge, what);
        }
    }
    Ok(())
}

/// A seam's two sides stand a period apart across a direction its surface
/// closes in, so that the face walking both reads one place twice. On a
/// surface that does not close across them, the side a face does not walk
/// names another stretch of the surface, or none, and a face reading the
/// edge by its orientation alone can read that one.
fn check_seam_closes(
    model: &Model,
    edge: &Shape,
    (ahead, back, range): (ogeom_topo::PCurveId, ogeom_topo::PCurveId, (f64, f64)),
    surface: &ogeom_geom::SurfaceGeometry,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let (Some(ahead), Some(back)) = (
        model.geometry().pcurve(ahead),
        model.geometry().pcurve(back),
    ) else {
        ogeom_bail!(Dangling, "an edge names geometry not in this model");
    };
    let middle = 0.5 * (range.0 + range.1);
    let apart = ahead.point_at(middle, tol)? - back.point_at(middle, tol)?;
    let (across_u, closes) = if apart.x.abs() >= apart.y.abs() {
        (true, surface.is_periodic_u() || surface.is_closed_u(tol))
    } else {
        (false, surface.is_periodic_v() || surface.is_closed_v(tol))
    };
    if !closes && apart.x.hypot(apart.y) > tol.parametric() {
        found.note(
            Severity::Broken,
            edge,
            ShapeType::Edge,
            format!(
                "carries a seam on a surface that does not close in {}: its two sides \
                 stand {} apart, and the side a face does not walk names another \
                 stretch of the surface",
                if across_u { "u" } else { "v" },
                apart.x.hypot(apart.y)
            ),
        );
    }
    Ok(())
}

/// How far a pcurve, lifted through its surface, leaves its edge's curve
/// beyond `reach`: the widest gap and where along the range it stands, or
/// `None` where it keeps within `reach` everywhere sampled. Held to the
/// same parameter where `paced`; otherwise a lifted point is measured
/// against the nearest point of the curve's stretch.
pub(crate) fn pcurve_off_curve(
    (curve, range): (&ogeom_geom::Curve, (f64, f64)),
    (pcurve, pcurve_range): (&ogeom_geom::PlanarCurve, (f64, f64)),
    surface: &ogeom_geom::SurfaceGeometry,
    reach: f64,
    paced: bool,
    tol: Tolerances,
) -> OgeomResult<Option<(f64, f64)>> {
    // A pcurve fitted through its edge's points strays most between them,
    // so the samples are many more than a fit takes per span.
    const SAMPLES: u32 = 32;
    // A gap stated where it was measured reads a few ulps wider measured
    // again here, through another chain of evaluations: past the tolerance
    // by rounding alone is within it.
    let reach = reach * (1.0 + 1e-9);
    let mut widest: Option<(f64, f64)> = None;
    for i in 0..=SAMPLES {
        let t = f64::from(i) / f64::from(SAMPLES);
        let on_curve = curve.point_at(range.0 + (range.1 - range.0) * t, tol)?;
        let uv = pcurve.point_at(pcurve_range.0 + (pcurve_range.1 - pcurve_range.0) * t, tol)?;
        let Ok(lifted) = surface.point_at(uv.x, uv.y, tol) else {
            continue;
        };
        let mut gap = on_curve.distance(lifted);
        if gap > reach && !paced {
            gap = gap.min(crate::pcurve_gap::nearest_on_stretch(
                curve, range, lifted, tol,
            )?);
        }
        if gap > reach && widest.is_none_or(|(g, _)| gap > g) {
            widest = Some((gap, t));
        }
    }
    Ok(widest)
}

/// A wire's edges must meet end to end.
pub(crate) fn check_wire(
    model: &Model,
    wire: &Shape,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let edges = model.ordered_children_of(wire)?;
    if edges.is_empty() {
        found.note(
            Severity::Broken,
            wire,
            ShapeType::Wire,
            "has no edges, so it bounds nothing".into(),
        );
        return Ok(());
    }
    for i in 0..edges.len() {
        let (Some((_, end)), Some((next, _))) = (
            crate::build::edge_vertices(model, &edges[i])?,
            crate::build::edge_vertices(model, &edges[(i + 1) % edges.len()])?,
        ) else {
            found.note(
                Severity::Broken,
                wire,
                ShapeType::Wire,
                format!("edge {i} has no bounding vertices, so it joins nothing"),
            );
            continue;
        };
        if !end.is_same(&next)
            && !model.same_position(&end, &next, tol)?
            && !crate::build::one_point(model, &end, &next, tol)?
        {
            found.note(
                Severity::Broken,
                wire,
                ShapeType::Wire,
                format!(
                    "edge {i} ends where edge {} does not begin; a face built on \
                     this has a gap in its boundary",
                    (i + 1) % edges.len()
                ),
            );
        }
    }
    Ok(())
}

/// Every edge of a face needs a pcurve on that face's surface, and the
/// boundary those pcurves draw must not cross itself in the surface's chart
/// ([`chart_crossings`](crate::chart_crossings)): a figure eight encloses no
/// single region, and the mesher, the classifier and a boolean each read it
/// differently.
fn check_face(
    model: &Model,
    face: &Shape,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let Some(node) = model.node(face) else {
        ogeom_bail!(Dangling, "face is not in this model");
    };
    let Some(data) = node.data().as_face() else {
        return Ok(());
    };
    if model.geometry().surface(data.surface).is_none() {
        ogeom_bail!(Dangling, "face names a surface not in this model");
    }

    let wires = model.children_of(face)?;
    if wires.is_empty() && !data.natural_restriction {
        found.note(
            Severity::Broken,
            face,
            ShapeType::Face,
            "has no wires and is not marked as covering its whole surface, so \
             what it is a face *of* is undefined"
                .into(),
        );
    }

    for wire in &wires {
        for edge in model.children_of(wire)? {
            let Some(edge_data) = model.node(&edge).and_then(|n| n.data().as_edge()) else {
                continue;
            };
            if edge_data
                .pcurve_for(data.surface, edge.location())
                .is_none()
            {
                found.note(
                    Severity::Broken,
                    &edge,
                    ShapeType::Edge,
                    "bounds a face it has no pcurve on; the face cannot be split \
                     or triangulated in its own parameter space"
                        .into(),
                );
            }
        }
    }
    for crossing in crate::chart_crossings(model, face, tol)? {
        let at = crossing.at;
        let [(wa, ea), (wb, eb)] = crossing.edges;
        found.note(
            Severity::Broken,
            face,
            ShapeType::Face,
            format!(
                "its boundary crosses itself in its surface's chart at \
                 ({:.6}, {:.6}, {:.6}), edge {ea} of wire {wa} across edge {eb} \
                 of wire {wb}: it encloses no single region",
                at.x, at.y, at.z
            ),
        );
    }
    Ok(())
}

/// An edge's plain pcurves on one surface, at one placement, must agree.
///
/// A face finds its edge's pcurve by surface and placement, and the lookup
/// answers with the first that matches. Where two plain pcurves stand on
/// one surface and part (the two columns of a closed surface's seam,
/// attached as two plain pcurves for two faces on that surface), every face
/// reads the first, and a face that walks the other column reads its
/// boundary a period away. Apart is measured along the surface between
/// them: two fits of one edge stay within its tolerance of each other,
/// two columns of a seam stand the surface's girth apart.
fn check_plain_pcurves_apart(
    model: &Model,
    edge: &Shape,
    data: &ogeom_topo::EdgeData,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let reach = CHART_GAP_SLACK * data.tolerance.get().max(tol.approximation());
    let plain: Vec<_> = data
        .representations
        .iter()
        .filter_map(|r| match r {
            EdgeRepr::PCurve {
                curve,
                surface,
                location,
                range,
            } => Some((*curve, *surface, location, *range)),
            _ => None,
        })
        .collect();
    for (i, a) in plain.iter().enumerate() {
        for b in &plain[i + 1..] {
            if a.1 != b.1 || a.2 != b.2 {
                continue;
            }
            let (Some(surface), Some(pa), Some(pb)) = (
                model.geometry().surface(a.1),
                model.geometry().pcurve(a.0),
                model.geometry().pcurve(b.0),
            ) else {
                ogeom_bail!(Dangling, "an edge names geometry not in this model");
            };
            let apart = pcurves_apart(surface, (pa, a.3), (pb, b.3), tol)?;
            if apart > reach {
                found.note(
                    Severity::Broken,
                    edge,
                    ShapeType::Edge,
                    format!(
                        "holds two plain pcurves on one surface that stand {apart} \
                         apart along it; a lookup by surface finds the first for \
                         every face, so a face walking the other reads its boundary \
                         in the wrong place"
                    ),
                );
                return Ok(());
            }
        }
    }
    Ok(())
}

/// The widest distance between two pcurves, each sampled evenly over its
/// own range, measured along the surface between them.
fn pcurves_apart(
    surface: &ogeom_geom::SurfaceGeometry,
    (a, ra): (&ogeom_geom::PlanarCurve, (f64, f64)),
    (b, rb): (&ogeom_geom::PlanarCurve, (f64, f64)),
    tol: Tolerances,
) -> OgeomResult<f64> {
    const SAMPLES: u32 = 4;
    let mut widest = 0.0_f64;
    for i in 0..=SAMPLES {
        let t = f64::from(i) / f64::from(SAMPLES);
        let pa = a.point_at(ra.0 + (ra.1 - ra.0) * t, tol)?;
        let pb = b.point_at(rb.0 + (rb.1 - rb.0) * t, tol)?;
        if let Some(apart) = along_surface(surface, pa, pb, tol) {
            widest = widest.max(apart);
        }
    }
    Ok(widest)
}

/// Where a face's boundary does not close in its surface's chart, each in
/// a sentence; none where it closes. The test [`check`] makes of every
/// face, for a builder asking it of the faces it made. A wire `kept` names
/// is one the builder took over as it stood, and is not walked.
///
/// # Errors
///
/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if the face
/// names a surface not in the model.
pub fn chart_breaks(
    model: &Model,
    face: &Shape,
    kept: &dyn Fn(&Shape) -> bool,
    tol: Tolerances,
) -> OgeomResult<Vec<String>> {
    let mut found = Diagnosis::default();
    check_face_chart(model, face, kept, tol, &mut found)?;
    Ok(found.problems.into_iter().map(|p| p.what).collect())
}

/// A face's boundary, read edge by edge through the pcurve lookup the
/// boolean and the mesher use, must close in its surface's chart.
///
/// Each edge is read as its face walks it: a plain pcurve from its start to
/// its end, or reversed; a seam on the side whose start continues the point
/// walked to, as the mesher picks it. At each joint, one edge's end and the
/// next edge's start stand within the joint's tolerance of each other,
/// measured along the surface between them, or a whole period apart along
/// a direction the surface closes in. Otherwise the boundary does not close
/// there.
///
/// A ring that goes once round the surface with no seam (a band's rim, one
/// circle) closes by a single period's jump, and each such jump counts
/// toward the ring's turns round the surface. Jumps that cancel (a period
/// one way at one joint, back at another) at an edge that holds another
/// plain pcurve on the surface close nothing: the lookup found the first,
/// and the face walks the other, on the far column of the surface's seam.
/// Cancelling jumps at edges with one pcurve each are a ring folding across
/// the chart's join, which the mesher folds back, and are not reported.
///
/// Either way a boolean through the face finds a strand that dangles. A
/// wire with an edge that has no pcurve on the face is reported by
/// [`check_face`] and not walked.
fn check_face_chart(
    model: &Model,
    face: &Shape,
    kept: &dyn Fn(&Shape) -> bool,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let Some(data) = model.node(face).and_then(|n| n.data().as_face()) else {
        return Ok(());
    };
    let surface_id = data.surface;
    let Some(surface) = model.geometry().surface(surface_id) else {
        ogeom_bail!(Dangling, "face names a surface not in this model");
    };
    let ((u0, u1), (v0, v1)) = surface.domain();
    let periods = [
        (surface.is_periodic_u() || surface.is_closed_u(tol)).then_some(u1 - u0),
        (surface.is_periodic_v() || surface.is_closed_v(tol)).then_some(v1 - v0),
    ];
    let stored = face.oriented(ogeom_topo::Orientation::Forward);
    'wires: for wire in model.ordered_children_of(&stored)? {
        let edges = model.ordered_children_of(&wire)?;
        if kept(&wire) {
            continue;
        }
        let Some(ends) = chart_ends(model, surface_id, &edges, tol)? else {
            continue;
        };
        // The walk starts off a seam: a seam's side is picked by the point
        // already walked to.
        let Some(start) = ends.iter().position(|(e, _)| e.len() == 1) else {
            continue;
        };
        let n = edges.len();
        let mut walked: Vec<(Point2, Point2)> = Vec::with_capacity(n);
        for k in 0..n {
            let sides = &ends[(start + k) % n].0;
            let picked = match walked.last() {
                Some(&(_, last)) => sides
                    .iter()
                    .min_by(|a, b| last.distance(a.0).total_cmp(&last.distance(b.0))),
                None => sides.first(),
            };
            let Some(&picked) = picked else { break };
            walked.push(picked);
        }
        // Whole periods jumped at the joints, signed and in all, per
        // direction.
        let mut turns = [0_i64; 2];
        let mut jumps = [0_i64; 2];
        let mut misread = false;
        for k in 0..walked.len() {
            let (i, j) = ((start + k) % n, (start + k + 1) % n);
            let (end, next) = (walked[k].1, walked[(k + 1) % walked.len()].0);
            let reach = joint_reach(model, &edges[i], &edges[j], tol)?;
            let Some(apart) = along_surface(surface, end, next, tol) else {
                continue;
            };
            if apart <= reach {
                continue;
            }
            // The next edge's start brought to the end's copy of the chart.
            let mut whole = [0_i64; 2];
            let mut moved = next;
            for (axis, period) in periods.iter().enumerate() {
                let Some(period) = period.filter(|p| *p > 0.0 && p.is_finite()) else {
                    continue;
                };
                let (from, to) = if axis == 0 {
                    (end.x, &mut moved.x)
                } else {
                    (end.y, &mut moved.y)
                };
                #[allow(clippy::cast_possible_truncation, reason = "a few periods")]
                let shift = ((from - *to) / period).round() as i64;
                #[allow(clippy::cast_precision_loss, reason = "a few periods")]
                {
                    *to += shift as f64 * period;
                }
                whole[axis] = -shift;
            }
            let closes = whole != [0, 0]
                && along_surface(surface, end, moved, tol).is_some_and(|gap| gap <= reach);
            if !closes {
                found.note(
                    Severity::Broken,
                    face,
                    ShapeType::Face,
                    format!(
                        "its boundary does not close in its surface's chart: edge \
                         {i} ends {apart} along the surface from where edge {j} \
                         begins, outside the joint's tolerance of {reach}; a \
                         boolean through the face finds a strand that dangles"
                    ),
                );
                continue 'wires;
            }
            for axis in 0..2 {
                turns[axis] += whole[axis];
                jumps[axis] += whole[axis].abs();
            }
            misread |= ends[i].1 || ends[j].1;
        }
        if misread && (0..2).any(|axis| jumps[axis] > turns[axis].abs()) {
            found.note(
                Severity::Broken,
                face,
                ShapeType::Face,
                "its boundary does not close in its surface's chart: it jumps a \
                 whole period at joints whose jumps cancel, so an edge between \
                 them is read on the far column of the surface's seam; a boolean \
                 through the face finds a strand that dangles"
                    .into(),
            );
        }
    }
    Ok(())
}

/// How far apart, along the surface, one edge's end and the next edge's
/// start may stand in a face's chart before the boundary is open there:
/// [`CHART_GAP_SLACK`] times the widest of the two edges' tolerances and
/// the joint vertex's.
fn joint_reach(model: &Model, from: &Shape, to: &Shape, tol: Tolerances) -> OgeomResult<f64> {
    let joint = crate::build::edge_vertices(model, from)?
        .and_then(|(_, v)| model.tolerance_of(&v).ok().flatten())
        .map_or(0.0, |t| t.get());
    Ok(CHART_GAP_SLACK
        * [from, to]
            .iter()
            .filter_map(|e| model.tolerance_of(e).ok().flatten())
            .map(|t| t.get())
            .fold(joint.max(tol.approximation()), f64::max))
}

/// One edge of a ring as [`check_seam_sides`] walks it: its ends in the
/// chart as the ring walks it, the pcurve and range they come from and the
/// move that takes the pcurve to them, and, for a seam the ring walks both
/// ways, the direction across which its two sides stand apart.
struct SeamStep<'a> {
    ends: (Point2, Point2),
    pcurve: &'a ogeom_geom::PlanarCurve,
    range: (f64, f64),
    by: ogeom_math::Vector2,
    back: bool,
    across: Option<usize>,
}

/// A ring that walks a seam both ways across a direction its surface
/// repeats in must chain, in the surface's chart, from each of the seam's
/// sides to the other through the edges between.
///
/// Every edge keeps the face on its left, so of a seam's two sides, which
/// stand a period apart (a far side stated whole periods further is read
/// a period from the near one) and bound the window the face wraps, an
/// occurrence walks the one from which the other lies on its left: the one
/// the face lies against. That reading is the boolean's, and it does not
/// trust the seam's stored designation, which a file may state swapped.
/// Every other edge may be stated any whole number of periods off and is
/// moved to start where the ring has reached: on a repeating chart no copy
/// is the stated one, and the ring's own direction is all that places an
/// edge between the seam's sides. On a chart that closes without repeating the
/// domain places every pcurve, a reader takes the ring as stated, and the
/// ring is not read here.
///
/// Where the edges between two such occurrences meet the seam's column
/// only at their two ends, they lie
/// between two neighbouring copies of the column and run from one
/// occurrence's side to the next one's side in one copy of the chart: if
/// they arrive a whole period off it, they leave the column on the side
/// away from the face, and the boundary does not close with the face on
/// its left. Rims turned to run the other way round a drum, their uses
/// kept, do that; read on the nearer side, as [`check_face_chart`] reads
/// a seam, the same ring closes, round the window the wrong way.
///
/// A boolean folds such a ring onto the seam's sides and finds a strand
/// that dangles. Edges between that meet the column elsewhere (a ring
/// round the end of a seam that stops inside the face), occurrences of one
/// seam that meet directly (across the join, at a pole or at a slit's
/// tip), a seam walked once in the ring, and a ring that does not close
/// at all, which [`check_face_chart`] reports, are not read. A joint
/// bridged in space rather than in the chart (at a pole, or within its
/// tolerance) places the next edge only to within its chart gap, so an
/// arrival is named only where it stands off the next side by more than
/// half a period beyond the gaps summed.
fn check_seam_sides(
    model: &Model,
    face: &Shape,
    tol: Tolerances,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let Some(data) = model.node(face).and_then(|n| n.data().as_face()) else {
        return Ok(());
    };
    let surface_id = data.surface;
    let Some(surface) = model.geometry().surface(surface_id) else {
        ogeom_bail!(Dangling, "face names a surface not in this model");
    };
    let ((u0, u1), (v0, v1)) = surface.domain();
    let periods = [
        (surface.is_periodic_u() || surface.is_closed_u(tol)).then_some(u1 - u0),
        (surface.is_periodic_v() || surface.is_closed_v(tol)).then_some(v1 - v0),
    ]
    .map(|p| p.filter(|p| *p > 0.0 && p.is_finite()));
    let repeats = [surface.is_periodic_u(), surface.is_periodic_v()];
    if !repeats.iter().any(|r| *r) {
        return Ok(());
    }
    let along = |p: Point2, axis: usize| if axis == 0 { p.x } else { p.y };
    let stored = face.oriented(ogeom_topo::Orientation::Forward);
    'wires: for wire in model.ordered_children_of(&stored)? {
        let edges = model.ordered_children_of(&wire)?;
        let mut steps: Vec<SeamStep<'_>> = Vec::with_capacity(edges.len());
        for edge in &edges {
            let Some(edge_data) = model.node(edge).and_then(|n| n.data().as_edge()) else {
                continue 'wires;
            };
            let back = edge.orientation() == ogeom_topo::Orientation::Reversed;
            let curve = |id| -> OgeomResult<&ogeom_geom::PlanarCurve> {
                let Some(pcurve) = model.geometry().pcurve(id) else {
                    ogeom_bail!(Dangling, "an edge names geometry not in this model");
                };
                Ok(pcurve)
            };
            let walked = |pcurve: &ogeom_geom::PlanarCurve, range: (f64, f64)| {
                let (a, b) = (
                    pcurve.point_at(range.0, tol)?,
                    pcurve.point_at(range.1, tol)?,
                );
                OgeomResult::Ok(if back { (b, a) } else { (a, b) })
            };
            match edge_data.pcurve_for(surface_id, edge.location()) {
                Some(EdgeRepr::PCurve {
                    curve: id, range, ..
                }) => {
                    let pcurve = curve(*id)?;
                    steps.push(SeamStep {
                        ends: walked(pcurve, *range)?,
                        pcurve,
                        range: *range,
                        by: ogeom_math::Vector2::new(0.0, 0.0),
                        back,
                        across: None,
                    });
                }
                Some(EdgeRepr::Seam {
                    forward,
                    reversed,
                    range,
                    ..
                }) => {
                    if edges.iter().filter(|e| e.is_same(edge)).count() != 2 {
                        continue 'wires;
                    }
                    let (ahead, other) = (curve(*forward)?, curve(*reversed)?);
                    let (a, b) = walked(ahead, *range)?;
                    let middle = 0.5 * (range.0 + range.1);
                    let towards = other.point_at(middle, tol)? - ahead.point_at(middle, tol)?;
                    let run = b - a;
                    let left = run.x * towards.y - run.y * towards.x;
                    // Sides that do not stand apart across the run name no
                    // side the face lies against.
                    if left.abs() <= run.magnitude() * towards.magnitude() * tol.angular() {
                        continue 'wires;
                    }
                    let across = usize::from(towards.y.abs() > towards.x.abs());
                    let (Some(period), true) = (periods[across], repeats[across]) else {
                        continue 'wires;
                    };
                    // The far side read a period from the near one, towards
                    // it: a file may state it whole periods further.
                    let mut by = ogeom_math::Vector2::new(0.0, 0.0);
                    if left < 0.0 {
                        if across == 0 {
                            by.x = period.copysign(towards.x);
                        } else {
                            by.y = period.copysign(towards.y);
                        }
                    }
                    steps.push(SeamStep {
                        ends: (a + by, b + by),
                        pcurve: ahead,
                        range: *range,
                        by,
                        back,
                        across: Some(across),
                    });
                }
                _ => continue 'wires,
            }
        }
        let n = steps.len();
        for axis in 0..2 {
            let Some(period) = periods[axis] else {
                continue;
            };
            let pinned: Vec<usize> = (0..n).filter(|&k| steps[k].across == Some(axis)).collect();
            for (at, &from) in pinned.iter().enumerate() {
                let to = pinned[(at + 1) % pinned.len()];
                let between: Vec<usize> = (1..n)
                    .map(|k| (from + k) % n)
                    .take_while(|&k| k != to)
                    .collect();
                if between.is_empty() {
                    continue;
                }
                let column = along(steps[from].ends.1, axis);
                // Which gap between neighbouring copies of the column a
                // point lies in, or `None` on the column itself.
                let gap_of = |p: Point2| {
                    let turns = (along(p, axis) - column) / period;
                    ((turns - turns.round()).abs() * period > tol.parametric())
                        .then(|| turns.floor())
                };
                let mut last = steps[from].ends.1;
                let mut slack = 0.0;
                let mut elsewhere = false;
                let mut prior = from;
                for (k, &i) in between.iter().enumerate() {
                    let Some((shift, gap)) = chained(
                        model,
                        surface,
                        (&edges[prior], &edges[i]),
                        last,
                        steps[i].ends.0,
                        &periods,
                        tol,
                    )?
                    else {
                        continue 'wires;
                    };
                    slack += gap;
                    let step = &steps[i];
                    let mut previous: Option<f64> = None;
                    for j in 0..=SEAM_SIDE_SAMPLES {
                        let t = f64::from(j) / f64::from(SEAM_SIDE_SAMPLES);
                        let t = if step.back { 1.0 - t } else { t };
                        let p = step
                            .pcurve
                            .point_at(step.range.0 + (step.range.1 - step.range.0) * t, tol)?
                            + step.by
                            + shift;
                        let first = k == 0 && j == 0;
                        let arrival = k + 1 == between.len() && j == SEAM_SIDE_SAMPLES;
                        match gap_of(p) {
                            None if !first && !arrival => elsewhere = true,
                            None => {}
                            Some(g) => {
                                elsewhere |= previous.is_some_and(|q| q != g);
                                previous = Some(g);
                            }
                        }
                    }
                    last = step.ends.1 + shift;
                    prior = i;
                }
                if elsewhere {
                    continue;
                }
                let next = steps[to].ends.0;
                let off = along(next, axis) - along(last, axis);
                let turns = (off / period).round();
                let mut home = next;
                if axis == 0 {
                    home.x -= turns * period;
                } else {
                    home.y -= turns * period;
                }
                let reach = joint_reach(model, &edges[prior], &edges[to], tol)?;
                let meets = along_surface(surface, last, home, tol).is_some_and(|d| d <= reach)
                    || along_surface(surface, last, next, tol).is_some_and(|d| d <= reach);
                if !meets || off.abs() - slack <= 0.5 * period {
                    continue;
                }
                found.note(
                    Severity::Broken,
                    face,
                    ShapeType::Face,
                    format!(
                        "its boundary, each seam read on the side the face lies \
                         against, does not close in its surface's chart: edges \
                         {} to {} run from one side of a seam to the other and \
                         arrive {turns} periods off it, leaving the seam on the \
                         side away from the face; a boolean through the face \
                         finds a strand that dangles",
                        between[0],
                        between[between.len() - 1]
                    ),
                );
                continue 'wires;
            }
        }
    }
    Ok(())
}

/// How finely [`check_seam_sides`] samples an edge between two sides of a
/// seam for where it meets the seam's column: a crossing shows as two
/// neighbouring samples in different gaps between the column's copies.
const SEAM_SIDE_SAMPLES: u32 = 16;

/// The whole periods that bring the start `next` of an edge to where the
/// ring has reached, `last`, after the edge `edges.0`, and the chart gap
/// left at the joint: where the joint meets in space within its reach,
/// without a move or with one; `None` where it does not.
fn chained(
    model: &Model,
    surface: &ogeom_geom::SurfaceGeometry,
    edges: (&Shape, &Shape),
    last: Point2,
    next: Point2,
    periods: &[Option<f64>; 2],
    tol: Tolerances,
) -> OgeomResult<Option<(ogeom_math::Vector2, f64)>> {
    let reach = joint_reach(model, edges.0, edges.1, tol)?;
    let mut shift = ogeom_math::Vector2::new(0.0, 0.0);
    if along_surface(surface, last, next, tol).is_some_and(|d| d > reach) {
        if let Some(period) = periods[0] {
            shift.x = ((last.x - next.x) / period).round() * period;
        }
        if let Some(period) = periods[1] {
            shift.y = ((last.y - next.y) / period).round() * period;
        }
        if !along_surface(surface, last, next + shift, tol).is_some_and(|d| d <= reach) {
            return Ok(None);
        }
    }
    Ok(Some((shift, last.distance(next + shift))))
}

/// How many times its joint's tolerance a gap in a face's chart may span
/// before the boundary is open there. A fitted trim's ends wander from its
/// vertex by about the tolerance its edge states, and never less than the
/// fitting accuracy, which is where the tolerance taken starts.
pub(crate) const CHART_GAP_SLACK: f64 = 10.0;

/// An edge's ends in a face's chart as the face walks it (one pair for a
/// pcurve, one per side for a seam), and whether the edge holds another
/// plain pcurve on the surface at the same placement.
type ChartEnds = (Vec<(Point2, Point2)>, bool);

/// Each edge's [`ChartEnds`]; `None` where an edge has no pcurve on the
/// surface.
fn chart_ends(
    model: &Model,
    surface: ogeom_topo::SurfaceId,
    edges: &[Shape],
    tol: Tolerances,
) -> OgeomResult<Option<Vec<ChartEnds>>> {
    let mut ends = Vec::with_capacity(edges.len());
    for edge in edges {
        let Some(data) = model.node(edge).and_then(|n| n.data().as_edge()) else {
            return Ok(None);
        };
        let (ids, range, another) = match data.pcurve_for(surface, edge.location()) {
            Some(EdgeRepr::PCurve {
                curve,
                range,
                location,
                ..
            }) => {
                let plain = data
                    .representations
                    .iter()
                    .filter(|r| {
                        matches!(r, EdgeRepr::PCurve { .. })
                            && r.surface() == Some(surface)
                            && r.location() == Some(location)
                    })
                    .count();
                (vec![*curve], *range, plain > 1)
            }
            Some(EdgeRepr::Seam {
                forward,
                reversed,
                range,
                ..
            }) => (vec![*forward, *reversed], *range, false),
            _ => return Ok(None),
        };
        let mut sides = Vec::with_capacity(ids.len());
        for id in ids {
            let Some(pcurve) = model.geometry().pcurve(id) else {
                ogeom_bail!(Dangling, "an edge names geometry not in this model");
            };
            let (a, b) = (
                pcurve.point_at(range.0, tol)?,
                pcurve.point_at(range.1, tol)?,
            );
            sides.push(if edge.orientation() == ogeom_topo::Orientation::Reversed {
                (b, a)
            } else {
                (a, b)
            });
        }
        ends.push((sides, another));
    }
    Ok(Some(ends))
}

/// The length of the straight chart segment from `a` to `b`, lifted onto
/// the surface: nothing where the two meet at a pole, a period's worth of
/// surface where they stand on two columns of a seam, and what lies past
/// the end of a direction the surface stops in measured from that end.
/// `None` where the surface cannot be evaluated along it.
fn along_surface(
    surface: &ogeom_geom::SurfaceGeometry,
    a: Point2,
    b: Point2,
    tol: Tolerances,
) -> Option<f64> {
    const PIECES: u32 = 8;
    if a.distance(b) <= tol.parametric() {
        return Some(0.0);
    }
    let at = |t: f64| lifted_in_domain(surface, a + (b - a) * t, tol);
    let mut last = at(0.0).ok()?;
    let mut length = 0.0;
    for i in 1..=PIECES {
        let next = at(f64::from(i) / f64::from(PIECES)).ok()?;
        length += last.distance(next);
        last = next;
    }
    Some(length)
}

/// The surface's point at `uv`; where the surface refuses it, a parameter
/// past the end of a direction that neither repeats nor closes taken back
/// to that end: the point of the surface nearest in its chart. A joint
/// between pcurve ends standing past a sphere's pole is then measured from
/// where the surface stops, instead of going unread. A surface that
/// evaluates past its stated domain (a plane, whose domain is a window
/// onto it) is measured where the parameters stand.
fn lifted_in_domain(
    surface: &ogeom_geom::SurfaceGeometry,
    uv: Point2,
    tol: Tolerances,
) -> OgeomResult<ogeom_math::Point> {
    if let Ok(point) = surface.point_at(uv.x, uv.y, tol) {
        return Ok(point);
    }
    let ((u0, u1), (v0, v1)) = surface.domain();
    let u = if surface.is_periodic_u() || surface.is_closed_u(tol) {
        uv.x
    } else {
        uv.x.max(u0).min(u1)
    };
    let v = if surface.is_periodic_v() || surface.is_closed_v(tol) {
        uv.y
    } else {
        uv.y.max(v0).min(v1)
    };
    surface.point_at(u, v, tol)
}

/// A shell is closed when every edge is used an even number of times.
///
/// Reported as `Suspect` rather than `Broken` on its own: an open shell is a
/// perfectly good surface and plenty of operations want one. It becomes
/// `Broken` only when something asks it to bound a volume, which is a question
/// this function is not being asked.
fn check_shell(model: &Model, shell: &Shape, found: &mut Diagnosis) -> OgeomResult<()> {
    let mut uses: FastMap<TShapeId, usize> = FastMap::default();
    for face in explore(model, shell, Filter::OfType(ShapeType::Face))? {
        for wire in model.children_of(&face)? {
            for edge in model.children_of(&wire)? {
                if model
                    .node(&edge)
                    .and_then(|n| n.data().as_edge())
                    .is_some_and(|d| d.degenerate)
                {
                    continue;
                }
                *uses.entry(edge.node()).or_default() += 1;
            }
        }
    }
    let odd = uses.values().filter(|n| *n % 2 == 1).count();
    if odd > 0 {
        found.note(
            Severity::Suspect,
            shell,
            ShapeType::Shell,
            format!(
                "{odd} edge(s) used an odd number of times, so the shell is open \
                 along them; it encloses no volume"
            ),
        );
    }
    for edge in walked_one_way(model, shell)? {
        found.note(
            Severity::Suspect,
            &edge,
            ShapeType::Edge,
            "walked the same way by both its faces: one of them does not keep \
             its material on the left of its rings"
                .into(),
        );
    }
    Ok(())
}

/// The edges between two faces of `shape` that both faces walk the same
/// way, in the order the walk first meets them.
///
/// Each face keeps its material on the left of its rings about its outward
/// normal, so an edge two faces share is walked once each way, senses
/// composed. That holds for any edge with two faces, closed shell or sheet;
/// an edge with one face or more than two says nothing. A degenerate edge
/// (a pole, an apex) bounds nothing and is not asked, and a seam, walked
/// both ways by its one face, passes.
pub(crate) fn walked_one_way(model: &Model, shape: &Shape) -> OgeomResult<Vec<Shape>> {
    type Walks = (Shape, usize, usize);
    let mut walks: FastMap<(TShapeId, ogeom_topo::Location), Walks> = FastMap::default();
    let mut order = Vec::new();
    for face in explore(model, shape, Filter::OfType(ShapeType::Face))? {
        for edge in explore(model, &face, Filter::OfType(ShapeType::Edge))? {
            if model
                .node(&edge)
                .and_then(|n| n.data().as_edge())
                .is_some_and(|d| d.degenerate)
            {
                continue;
            }
            let key = (edge.node(), edge.location().clone());
            let walk = walks.entry(key.clone()).or_insert_with(|| {
                order.push(key);
                (edge.clone(), 0, 0)
            });
            walk.1 += 1;
            if edge.orientation() == ogeom_topo::Orientation::Forward {
                walk.2 += 1;
            }
        }
    }
    Ok(order
        .into_iter()
        .filter_map(|key| {
            let (edge, uses, forward) = walks.remove(&key)?;
            (uses == 2 && forward != 1).then_some(edge)
        })
        .collect())
}

/// Restore tolerance containment below `shape`: every edge widened to at
/// least the faces it bounds, every vertex to at least the edges it bounds.
///
/// The rule [`check`] enforces, established the only way the data model
/// allows: by raising what is bounded, never lowering what bounds. Each
/// face and then each edge is widened to its own tolerance through
/// [`Model::widen`], which cascades to everything below it and leaves
/// anything already looser as it is. Returns how many entities grew.
///
/// An operation that widens an edge's tolerance by writing it directly (a
/// reader recording how far a pcurve sits from its curve) leaves the
/// edge's vertices behind; this is the pass that brings them along. What
/// `shape` shares with other shapes is copied first ([`Model::unshare`]),
/// so their tolerances stay as they are.
///
/// # Errors
///
/// [`OgeomError::Dangling`](ogeom_core::OgeomError::Dangling) if the shape,
/// or anything below it, does not resolve in this model.
pub fn restore_containment(model: &mut Model, shape: &Shape) -> OgeomResult<usize> {
    model.unshare(shape)?;
    let bounded: Vec<Shape> = explore_unique(model, shape, ShapeType::Edge)?
        .into_iter()
        .chain(explore_unique(model, shape, ShapeType::Vertex)?)
        .collect();
    let before: Vec<f64> = bounded
        .iter()
        .map(|s| model.tolerance_of(s).map(|t| t.map_or(0.0, |t| t.get())))
        .collect::<OgeomResult<_>>()?;
    for kind in [ShapeType::Face, ShapeType::Edge] {
        for bounding in explore_unique(model, shape, kind)? {
            if let Some(own) = model.tolerance_of(&bounding)? {
                model.widen(&bounding, own)?;
            }
        }
    }
    let mut grown = 0;
    for (s, was) in bounded.iter().zip(before) {
        if model.tolerance_of(s)?.is_some_and(|t| t.get() > was) {
            grown += 1;
        }
    }
    Ok(grown)
}

/// Compare one shape's tolerance against everything below it.
fn compare(
    model: &Model,
    shape: &Shape,
    kind: ShapeType,
    found: &mut Diagnosis,
) -> OgeomResult<()> {
    let Some(bounding) = model.tolerance_of(shape)? else {
        return Ok(());
    };
    // Each occurrence once: a vertex reached through both its edges is one
    // containment claim, not two.
    let mut seen = FastSet::default();
    for below in explore(model, shape, Filter::All)? {
        if below.is_same(shape) || !seen.insert(ogeom_topo::SameKey(below.clone())) {
            continue;
        }
        let Some(bounded) = model.tolerance_of(&below)? else {
            continue;
        };
        if bounded.get() < bounding.get() {
            found.note(
                Severity::Broken,
                &below,
                model.kind_of(&below)?,
                format!(
                    "tolerance {} is tighter than the {kind:?} that bounds it \
                     ({}); the bound does not reliably contain what it bounds",
                    bounded.get(),
                    bounding.get()
                ),
            );
        }
    }
    Ok(())
}

/// Faces of one shape that reach each other without sharing topology:
/// self-intersection, detected as the interference it is.
///
/// Every unordered pair of distinct faces that share no edge and no vertex
/// node, and that hulls holding their geometry do not prove apart, is put
/// through the exact minimum-distance machinery; a pair within the
/// confusion tolerance of touching is reported. Adjacent faces meet at
/// their shared boundary by construction and are not interference; a valid
/// solid therefore reports nothing, and a sheet folded through itself names
/// the faces that cross.
///
/// # Errors
///
/// As [`crate::distance_between_shapes`].
pub fn check_self_intersection(
    model: &Model,
    shape: &Shape,
    tol: Tolerances,
) -> OgeomResult<Vec<(Shape, Shape)>> {
    crossings_among(model, shape, None, tol)
}

/// [`check_self_intersection`] over the pairs holding at least one of
/// `near`: after an edit that moved some faces, the pairs of faces it left
/// alone cannot have begun to cross.
///
/// # Errors
///
/// As [`check_self_intersection`].
pub fn check_self_intersection_near(
    model: &Model,
    shape: &Shape,
    near: &[Shape],
    tol: Tolerances,
) -> OgeomResult<Vec<(Shape, Shape)>> {
    let near: ogeom_core::FastSet<TShapeId> = near.iter().map(Shape::node).collect();
    crossings_among(model, shape, Some(&near), tol)
}

fn crossings_among(
    model: &Model,
    shape: &Shape,
    near: Option<&ogeom_core::FastSet<TShapeId>>,
    tol: Tolerances,
) -> OgeomResult<Vec<(Shape, Shape)>> {
    use ogeom_topo::explore_unique;
    let faces = explore_unique(model, shape, ShapeType::Face)?;
    let asked = |i: usize| near.is_none_or(|n| n.contains(&faces[i].node()));
    // The topology below each face, for the adjacency exclusion, its
    // elements and its box: each face gathered and bounded once, not once
    // per pair it is in.
    let prepared = ogeom_core::parallel::map_ordered(&faces, |_, face| {
        let mut below = ogeom_core::FastSet::default();
        for kind in [ShapeType::Edge, ShapeType::Vertex] {
            for sub in explore_unique(model, face, kind)? {
                below.insert(sub.node());
            }
        }
        let gathered = crate::proximity::Elements::of(model, face, tol)?;
        let bounds = crate::measure::shape_bounds(model, face, tol)?.expanded(tol.confusion());
        Ok((below, gathered, bounds))
    });
    let prepared = prepared
        .into_iter()
        .collect::<OgeomResult<Vec<(ogeom_core::FastSet<TShapeId>, _, ogeom_math::Aabb)>>>()?;

    // Candidate pairs by sweeping the boxes along x: a pair whose x
    // intervals do not overlap cannot have boxes that meet. Sorted back
    // into (i, j) order, so the answer lists pairs as a scan of every pair
    // would.
    let mut by_x: Vec<(f64, f64, usize)> = prepared
        .iter()
        .enumerate()
        .filter_map(|(i, (_, _, bounds))| Some((bounds.low()?.x, bounds.high()?.x, i)))
        .collect();
    by_x.sort_by(|a, b| a.0.total_cmp(&b.0).then(a.2.cmp(&b.2)));
    let mut pairs = Vec::new();
    for (k, &(_, high, i)) in by_x.iter().enumerate() {
        for &(low, _, j) in &by_x[k + 1..] {
            if low > high {
                break;
            }
            let (i, j) = (i.min(j), i.max(j));
            if (asked(i) || asked(j))
                && prepared[i].2.intersects(&prepared[j].2)
                && prepared[i].0.is_disjoint(&prepared[j].0)
            {
                pairs.push((i, j));
            }
        }
    }
    pairs.sort_unstable();

    let touching = ogeom_core::parallel::map_ordered(&pairs, |_, &(i, j)| {
        ogeom_core::progress::checkpoint()?;
        // Faces whose boxes meet are often proven apart by the hulls of
        // their pieces, at a fraction of the cost of measuring them.
        if prepared[i]
            .1
            .apart_by_more_than(&prepared[j].1, tol.confusion(), tol)
        {
            return Ok(false);
        }
        let reach = crate::proximity::distance_between_prepared(
            &prepared[i].1,
            &prepared[j].1,
            ogeom_intersect::ExtremaOptions::default(),
            tol,
        )?;
        Ok(reach.distance <= tol.confusion())
    });
    let mut crossings = Vec::new();
    for (&(i, j), touching) in pairs.iter().zip(touching) {
        if touching? {
            crossings.push((faces[i].clone(), faces[j].clone()));
        }
    }
    Ok(crossings)
}

/// How many edges between two faces of `shape` both faces walk the same
/// way: none where every face keeps its material on the left of its rings.
#[cfg(test)]
pub(crate) fn edges_walked_one_way(model: &Model, shape: &Shape) -> usize {
    walked_one_way(model, shape).map_or(0, |edges| edges.len())
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
    use super::*;
    use crate::{make_box, make_cylinder, make_sphere, make_torus};
    use ogeom_core::Tolerance;
    use ogeom_math::{Frame, Point};
    use ogeom_topo::NodeData;
    use ogeom_topo::VertexData;

    const T: Tolerances = Tolerances::millimetres();

    #[test]
    fn every_primitive_is_valid() {
        // The check earns its keep only if the things known to be right pass
        // it. A checker that flags a correct box is worse than none, because
        // every real finding then reads as noise.
        let mut model = Model::new();
        let shapes = [
            make_box(&mut model, Frame::WORLD, (2.0, 3.0, 4.0), T)
                .unwrap()
                .shape,
            make_cylinder(&mut model, Frame::WORLD, 2.0, 5.0, T)
                .unwrap()
                .shape,
            make_sphere(&mut model, Frame::WORLD, 3.0, T).unwrap().shape,
            make_torus(&mut model, Frame::WORLD, 5.0, 2.0, T)
                .unwrap()
                .shape,
        ];
        for shape in &shapes {
            let found = check(&model, shape, T).unwrap();
            assert!(found.is_valid(), "a primitive was flagged: {found}");
        }
    }

    #[test]
    fn a_prism_is_valid() {
        use ogeom_math::Vector;
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let face = explore_unique(&model, &solid, ShapeType::Face).unwrap()[0].clone();
        let prism = crate::make_prism(&mut model, &face, Vector::new(0.0, 0.0, 2.0), T)
            .unwrap()
            .shape;

        let found = check(&model, &prism, T).unwrap();
        assert!(found.is_valid(), "the prism was flagged: {found}");
    }

    #[test]
    fn a_single_face_is_reported_open_but_still_usable() {
        // An open shell is a perfectly good surface, and plenty of operations
        // want one. Calling it broken would make the checker useless for every
        // sheet body.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let face = explore_unique(&model, &solid, ShapeType::Face).unwrap()[0].clone();
        let shell = crate::build::make_shell(&mut model, std::slice::from_ref(&face))
            .unwrap()
            .shape;

        let found = check(&model, &shell, T).unwrap();
        assert!(!found.is_valid(), "an open shell is worth reporting");
        assert!(found.is_usable(), "but nothing here answers wrongly");
        assert_eq!(found.worst(), Some(Severity::Suspect));
        assert_eq!(found.of(Severity::Suspect).len(), 1);
    }

    #[test]
    fn a_vertex_tighter_than_its_edge_is_caught() {
        // The containment rule runs the other way from intuition: the *bound*
        // is looser, and a vertex tighter than the edge that caps it means the
        // edge does not reliably reach it.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let edge = explore_unique(&model, &solid, ShapeType::Edge).unwrap()[0].clone();

        // Widen the edge alone, bypassing the cascading repair that exists to
        // stop exactly this.
        let loose = Tolerance::new(1e-3).unwrap();
        if let Some(NodeData::Edge(data)) = model.node_mut(&edge).map(ogeom_topo::TShape::data_mut)
        {
            data.tolerance = loose;
        }

        let found = check(&model, &edge, T).unwrap();
        assert!(!found.is_usable(), "a broken containment is not usable");
        let broken = found.of(Severity::Broken);
        assert!(!broken.is_empty());
        assert!(broken.iter().all(|p| p.kind == ShapeType::Vertex));
    }

    #[test]
    fn a_face_too_loose_for_its_boundary_names_each_part_once() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let face = explore_unique(&model, &solid, ShapeType::Face).unwrap()[0].clone();
        if let Some(NodeData::Face(data)) = model.node_mut(&face).map(ogeom_topo::TShape::data_mut)
        {
            data.tolerance = Tolerance::new(1e-3).unwrap();
        }
        // Four edges and four corners, each reached through two edges and
        // named once.
        let broken = check(&model, &face, T).unwrap().of(Severity::Broken).len();
        assert_eq!(broken, 8);
    }

    #[test]
    fn an_edge_with_no_curve_and_no_excuse_is_caught() {
        let mut model = Model::new();
        let v = model.add_vertex(VertexData::new(Point::ORIGIN));
        let edge = model
            .add_edge(ogeom_topo::EdgeData::new(), &[v.clone(), v])
            .unwrap();

        let found = check(&model, &edge, T).unwrap();
        assert!(!found.is_usable());
        assert!(found.problems[0].what.contains("not marked degenerate"));
    }

    #[test]
    fn an_edge_whose_curve_misses_its_vertex_is_caught() {
        // The failure that leaves a gap in every face built on the wire, and
        // which nothing notices until something walks the boundary.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let vertex = explore_unique(&model, &solid, ShapeType::Vertex).unwrap()[0].clone();
        if let Some(NodeData::Vertex(data)) =
            model.node_mut(&vertex).map(ogeom_topo::TShape::data_mut)
        {
            data.point = Point::new(50.0, 50.0, 50.0);
        }

        let found = check(&model, &solid, T).unwrap();
        assert!(!found.is_usable());
        assert!(
            found
                .of(Severity::Broken)
                .iter()
                .any(|p| p.what.contains("from the vertex it should meet")),
            "got {found}"
        );
    }

    #[test]
    fn a_face_whose_edge_has_no_pcurve_is_caught() {
        // Without a pcurve the face cannot be split in a boolean or
        // triangulated at all, and the failure surfaces far from its cause.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let face = explore_unique(&model, &solid, ShapeType::Face).unwrap()[0].clone();
        let edge = model
            .children_of(&model.children_of(&face).unwrap()[0])
            .unwrap()[0]
            .clone();
        if let Some(NodeData::Edge(data)) = model.node_mut(&edge).map(ogeom_topo::TShape::data_mut)
        {
            data.representations.retain(|r| r.is_curve3d());
        }

        let found = check(&model, &face, T).unwrap();
        assert!(!found.is_usable());
        assert!(
            found
                .of(Severity::Broken)
                .iter()
                .any(|p| p.what.contains("no pcurve on")),
            "got {found}"
        );
    }

    #[test]
    fn an_edge_whose_pcurve_leaves_its_curve_is_caught() {
        // A pcurve standing off its edge's curve by more than the edge's
        // tolerance parts the face it bounds from the neighbour following
        // the curve, whether or not the edge claims the two share a
        // parameter. A box edge's pcurve on one face is moved a hundredth
        // sideways in that face's chart.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let face = explore_unique(&model, &solid, ShapeType::Face).unwrap()[0].clone();
        let face_node = model.node(&face).unwrap().clone();
        let NodeData::Face(face_data) = face_node.data() else {
            panic!("not a face")
        };
        let surface = face_data.surface;
        let edge = model
            .children_of(&model.children_of(&face).unwrap()[0])
            .unwrap()[0]
            .clone();
        assert!(check(&model, &solid, T).unwrap().is_valid());

        let NodeData::Edge(data) = model.node(&edge).unwrap().data().clone() else {
            panic!("not an edge")
        };
        let original = data
            .representations
            .iter()
            .find_map(|r| match r {
                EdgeRepr::PCurve {
                    curve, surface: s, ..
                } if *s == surface => Some(*curve),
                _ => None,
            })
            .expect("the edge has a pcurve on the face");
        let basis = model.geometry().pcurve(original).unwrap().clone();
        let moved = model
            .geometry_mut()
            .add_pcurve(ogeom_geom::PlanarCurve::Offset(Box::new(
                ogeom_geom::Offset2d::new(basis, 0.01).unwrap(),
            )));
        if let Some(NodeData::Edge(data)) = model.node_mut(&edge).map(ogeom_topo::TShape::data_mut)
        {
            for repr in &mut data.representations {
                if let EdgeRepr::PCurve {
                    curve, surface: s, ..
                } = repr
                    && *s == surface
                {
                    *curve = moved;
                }
            }
        }

        let found = check(&model, &solid, T).unwrap();
        assert!(!found.is_usable(), "got {found}");
        assert!(
            found
                .of(Severity::Broken)
                .iter()
                .any(|p| p.kind == ShapeType::Edge && p.what.contains("leaves its curve by")),
            "got {found}"
        );
    }

    #[test]
    fn a_pcurve_farther_off_than_its_edge_is_long_is_suspect() {
        // A box a thousandth tall: one of its upright edges, 0.001 long,
        // widened to 0.002 with its vertices, has its pcurve on one face
        // moved sideways in that face's chart, where a plane's chart
        // measures as space does. Moved 0.0015 the pcurve stands farther
        // off than the edge is long; moved 0.0005 it does not. Either way
        // the tolerance covers it, and nothing is broken.
        for (offset, reported) in [(0.0015, true), (0.0005, false)] {
            let mut model = Model::new();
            let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 0.001), T)
                .unwrap()
                .shape;
            let edge = explore_unique(&model, &solid, ShapeType::Edge)
                .unwrap()
                .into_iter()
                .find(|edge| {
                    let (a, b) = crate::build::edge_vertices(&model, edge).unwrap().unwrap();
                    let at = |v: &Shape| model.node(v).unwrap().data().as_vertex().unwrap().point;
                    (at(&a).distance(at(&b)) - 0.001).abs() < 1e-12
                })
                .unwrap();
            model.widen(&edge, Tolerance::new(0.002).unwrap()).unwrap();
            let NodeData::Edge(data) = model.node(&edge).unwrap().data().clone() else {
                panic!("not an edge")
            };
            let (original, surface) = data
                .representations
                .iter()
                .find_map(|r| match r {
                    EdgeRepr::PCurve { curve, surface, .. } => Some((*curve, *surface)),
                    _ => None,
                })
                .unwrap();
            let basis = model.geometry().pcurve(original).unwrap().clone();
            let moved = model
                .geometry_mut()
                .add_pcurve(ogeom_geom::PlanarCurve::Offset(Box::new(
                    ogeom_geom::Offset2d::new(basis, offset).unwrap(),
                )));
            if let Some(NodeData::Edge(data)) =
                model.node_mut(&edge).map(ogeom_topo::TShape::data_mut)
            {
                for repr in &mut data.representations {
                    if let EdgeRepr::PCurve {
                        curve, surface: s, ..
                    } = repr
                        && *s == surface
                    {
                        *curve = moved;
                    }
                }
            }

            let found = check(&model, &solid, T).unwrap();
            assert!(found.is_usable(), "got {found}");
            let suspect = found.of(Severity::Suspect);
            if reported {
                assert_eq!(suspect.len(), 1, "got {found}");
                assert!(suspect[0].at.is_same(&edge), "got {found}");
            } else {
                assert!(found.is_valid(), "got {found}");
            }
        }
    }

    #[test]
    fn an_edge_below_the_confusion_tolerance_is_not_suspect() {
        // An edge 5e-8 long on the x axis, with a pcurve on the plane z = 0
        // running beside it 8e-8 off: farther off than the edge is long,
        // and within its tolerance, but both below the confusion
        // tolerance, where a gap and a length are rounding.
        use ogeom_geom::{Curve, Curve2d as _, Curve3d as _, LineCurve, PlaneSurface};
        let mut model = Model::new();
        let line = LineCurve::segment(Point::ORIGIN, Point::new(1.0, 0.0, 0.0), T).unwrap();
        let start = line.domain().0;
        let edge = crate::make_edge(&mut model, Curve::Line(line), (start, start + 5e-8), T)
            .unwrap()
            .shape;
        let plane = PlaneSurface::over(
            ogeom_math::Plane::new(Frame::WORLD),
            (-1.0, 1.0),
            (-1.0, 1.0),
        )
        .unwrap();
        let surface = model.geometry_mut().add_surface(plane.into());
        let beside: ogeom_geom::PlanarCurve =
            ogeom_geom::Line2d::segment(Point2::new(0.0, 8e-8), Point2::new(1.0, 8e-8), T)
                .unwrap()
                .into();
        let range = (beside.domain().0, beside.domain().0 + 5e-8);
        let pcurve = model.geometry_mut().add_pcurve(beside);
        if let Some(NodeData::Edge(data)) = model.node_mut(&edge).map(ogeom_topo::TShape::data_mut)
        {
            data.representations.push(EdgeRepr::PCurve {
                curve: pcurve,
                range,
                surface,
                location: ogeom_topo::Location::identity(),
            });
        }
        let gap = crate::pcurve_gap::edge_pcurve_gap(&model, &edge, T)
            .unwrap()
            .unwrap();
        assert!(gap > 5e-8 && gap < 1e-7, "{gap}");
        let found = check(&model, &edge, T).unwrap();
        assert!(found.is_valid(), "got {found}");
    }

    #[test]
    fn a_gap_on_a_plane_outside_its_window_is_measured_where_it_stands() {
        // A unit square at x, y in [5, 6] on a plane whose stated domain is
        // the window [-1, 1] squared: a plane evaluates anywhere, and one
        // edge's pcurve moved 0.3 along x leaves the boundary open by that
        // much at both its ends, however far outside the window it stands.
        use ogeom_geom::{Curve2d as _, PlaneSurface};
        let square = |shift: f64| {
            let mut model = Model::new();
            let corners = [(5.0, 5.0), (6.0, 5.0), (6.0, 6.0), (5.0, 6.0)]
                .map(|(x, y)| Point::new(x, y, 0.0));
            let wire = crate::make_polygon(&mut model, &corners, true, T)
                .unwrap()
                .shape;
            let plane = PlaneSurface::over(
                ogeom_math::Plane::new(Frame::WORLD),
                (-1.0, 1.0),
                (-1.0, 1.0),
            )
            .unwrap();
            let surface = model.geometry_mut().add_surface(plane.into());
            let edges = model.ordered_children_of(&wire).unwrap();
            for (k, edge) in edges.iter().enumerate() {
                let forward = edge.oriented(ogeom_topo::Orientation::Forward);
                let (a, b) = crate::build::edge_vertices(&model, &forward)
                    .unwrap()
                    .unwrap();
                let at = |v: &Shape| {
                    let p = model
                        .node(v)
                        .and_then(|n| n.data().as_vertex())
                        .unwrap()
                        .point;
                    let moved = if k == 0 { shift } else { 0.0 };
                    Point2::new(p.x + moved, p.y)
                };
                let line: ogeom_geom::PlanarCurve = ogeom_geom::Line2d::segment(at(&a), at(&b), T)
                    .unwrap()
                    .into();
                let range = line.domain();
                crate::attach_pcurve(
                    &mut model,
                    &forward,
                    line,
                    surface,
                    ogeom_topo::Location::identity(),
                    range,
                )
                .unwrap();
            }
            let face = crate::make_face_on(&mut model, surface, &[wire], T)
                .unwrap()
                .shape;
            chart_breaks(&model, &face, &|_| false, T).unwrap()
        };
        assert!(square(0.0).is_empty(), "{:?}", square(0.0));
        assert_eq!(
            square(0.3).len(),
            1,
            "the moved pcurve leaves the square open"
        );
    }

    #[test]
    fn a_seam_on_a_plane_is_reported() {
        // An edge on the x axis carrying a seam on the plane z = 0, its
        // two sides one unit apart in v: a plane closes in neither
        // direction, so the second side is another line of it. The same
        // edge with one side as a plain pcurve is sound.
        use ogeom_geom::{Curve, Curve3d as _, LineCurve, PlaneSurface};
        let seamed = |second: Option<f64>| {
            let mut model = Model::new();
            let line = LineCurve::segment(Point::ORIGIN, Point::new(1.0, 0.0, 0.0), T).unwrap();
            let range = line.domain();
            let edge = crate::make_edge(&mut model, Curve::Line(line), range, T)
                .unwrap()
                .shape;
            let plane = PlaneSurface::over(
                ogeom_math::Plane::new(Frame::WORLD),
                (-2.0, 2.0),
                (-2.0, 2.0),
            )
            .unwrap();
            let surface = model.geometry_mut().add_surface(plane.into());
            let at = |v: f64| -> ogeom_geom::PlanarCurve {
                ogeom_geom::Line2d::segment(Point2::new(0.0, v), Point2::new(1.0, v), T)
                    .unwrap()
                    .into()
            };
            let here = ogeom_topo::Location::identity();
            match second {
                Some(v) => {
                    crate::attach_seam(&mut model, &edge, at(0.0), at(v), surface, here, range)
                }
                None => crate::attach_pcurve(&mut model, &edge, at(0.0), surface, here, range),
            }
            .unwrap();
            check(&model, &edge, T).unwrap()
        };
        assert!(seamed(None).is_valid());
        let found = seamed(Some(1.0));
        assert!(
            found
                .problems
                .iter()
                .any(|p| p.what.contains("seam on a surface that does not close")),
            "got {found}"
        );
    }

    #[test]
    fn a_diagnosis_reads_as_a_report_rather_than_a_debug_dump() {
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        assert_eq!(check(&model, &solid, T).unwrap().to_string(), "valid");

        let face = explore_unique(&model, &solid, ShapeType::Face).unwrap()[0].clone();
        let shell = crate::build::make_shell(&mut model, std::slice::from_ref(&face))
            .unwrap()
            .shape;
        let text = check(&model, &shell, T).unwrap().to_string();
        assert!(text.starts_with("[suspect] Shell:"), "got {text}");
        assert!(text.contains("open"), "got {text}");
    }

    #[test]
    fn a_handle_that_does_not_resolve_is_an_error_not_a_finding() {
        // A dangling handle means the shape and the model do not belong
        // together. Every finding would then be about something that is not
        // there, which is worse than no finding.
        //
        // A handle from a *different* model is caught too, and by the same
        // route: arena keys carry the identifier of the arena that issued them,
        // so a foreign one resolves to nothing rather than to whatever sits at
        // that index.
        let mut other = Model::new();
        for _ in 0..4 {
            other.add_vertex(VertexData::new(Point::ORIGIN));
        }
        let beyond = other.add_vertex(VertexData::new(Point::ORIGIN));

        let empty = Model::new();
        assert!(check(&empty, &beyond, T).is_err());
    }

    /// The edges of `diagnosis` named as walked the same way by both their
    /// faces.
    fn walked_one_way_named(diagnosis: &Diagnosis) -> Vec<TShapeId> {
        diagnosis
            .problems
            .iter()
            .filter(|p| {
                p.severity == Severity::Suspect
                    && p.kind == ShapeType::Edge
                    && p.what.starts_with("walked the same way by both its faces")
            })
            .map(|p| p.at.node())
            .collect()
    }

    /// A face of a box rebuilt with its ring walked back, its sense kept,
    /// walks each of its four edges the same way as the face beside it:
    /// `check` names those four edges, in the closed box and in a sheet of
    /// that face and one neighbour, where it names the one edge they share.
    #[test]
    fn an_edge_both_faces_walk_the_same_way_is_named() {
        let mut model = Model::new();
        let block = make_box(&mut model, Frame::WORLD, (1.0, 2.0, 3.0), T)
            .unwrap()
            .shape;
        let faces = explore_unique(&model, &block, ShapeType::Face).unwrap();
        let face = faces[2].clone();
        let data = model.node(&face).unwrap().data().as_face().unwrap().clone();
        let stored = face.oriented(ogeom_topo::Orientation::Forward);
        let [wire] = &model.ordered_children_of(&stored).unwrap()[..] else {
            panic!("a box face has one ring");
        };
        let ring = model.ordered_children_of(wire).unwrap();
        let back: Vec<Shape> = ring.iter().rev().map(Shape::reversed).collect();
        let back = crate::build::make_wire(&mut model, &back, T).unwrap().shape;
        let walked_back = model
            .add_face(data, &[back])
            .unwrap()
            .oriented(face.orientation());

        let mut held = faces.clone();
        held[2] = walked_back.clone();
        let shell = crate::build::make_shell(&mut model, &held).unwrap().shape;
        let solid = crate::build::make_solid(&mut model, &[shell])
            .unwrap()
            .shape;
        let diagnosis = check(&model, &solid, T).unwrap();
        let mut named = walked_one_way_named(&diagnosis);
        named.sort();
        let mut ring_nodes: Vec<TShapeId> = ring.iter().map(Shape::node).collect();
        ring_nodes.sort();
        assert_eq!(named, ring_nodes, "{diagnosis}");
        assert!(diagnosis.is_usable(), "{diagnosis}");

        let beside = faces
            .iter()
            .find(|f| {
                let theirs = explore_unique(&model, f, ShapeType::Edge).unwrap();
                !f.is_same(&face) && theirs.iter().any(|e| ring_nodes.contains(&e.node()))
            })
            .unwrap()
            .clone();
        let sheet = crate::build::make_shell(&mut model, &[walked_back, beside])
            .unwrap()
            .shape;
        assert_eq!(
            walked_one_way_named(&check(&model, &sheet, T).unwrap()).len(),
            1
        );
        assert!(walked_one_way_named(&check(&model, &block, T).unwrap()).is_empty());
    }

    /// A B-spline sheet over [-5, 5]^2 at height `lift + bend (x^2 - y^2) / 20`,
    /// bounded by its border iso-curves.
    fn spline_sheet(model: &mut Model, lift: f64, bend: f64) -> Shape {
        use ogeom_geom::Surface as _;
        let n = 11;
        let at = |k: i32| -5.0 + 10.0 * f64::from(k) / f64::from(n - 1);
        let rows: Vec<Vec<Point>> = (0..n)
            .map(|j| {
                (0..n)
                    .map(|i| {
                        let (x, y) = (at(i), at(j));
                        Point::new(x, y, bend.mul_add((x * x - y * y) / 20.0, lift))
                    })
                    .collect()
            })
            .collect();
        let surface = ogeom_geom::fit::fit_surface_grid(&rows, 3, 1e-6, T)
            .unwrap()
            .curve;
        let ((u0, u1), (v0, v1)) = surface.domain();
        let corners: Vec<Shape> = [(u0, v0), (u1, v0), (u1, v1), (u0, v1)]
            .iter()
            .map(|&(u, v)| crate::make_vertex(model, surface.point_at(u, v, T).unwrap()).shape)
            .collect();
        let mut iso = |curve: ogeom_geom::BSplineCurve, from: usize, to: usize| {
            let range = curve.domain();
            crate::make_edge_between(model, curve.into(), range, &corners[from], &corners[to], T)
                .unwrap()
                .shape
        };
        let south = iso(surface.iso_v_curve(v0, T).unwrap(), 0, 1);
        let east = iso(surface.iso_u_curve(u1, T).unwrap(), 1, 2);
        let north = iso(surface.iso_v_curve(v1, T).unwrap(), 3, 2);
        let west = iso(surface.iso_u_curve(u0, T).unwrap(), 0, 3);
        let wires = [vec![south, east, north.reversed(), west.reversed()]];
        crate::make_face_with_pcurves(model, surface.into(), &wires, T)
            .unwrap()
            .shape
    }

    #[test]
    fn spline_sheets_whose_boxes_overlap_are_told_apart_or_measured() {
        let mut model = Model::new();
        let saddle = spline_sheet(&mut model, 0.0, 1.0);
        // The same saddle a twentieth above: every box of the two meets,
        // and the finer boxes prove them apart.
        let above = spline_sheet(&mut model, 0.05, 1.0);
        // A flat sheet through the saddle's middle crosses it along both
        // diagonals.
        let flat = spline_sheet(&mut model, 0.0, 0.0);
        let elements = |s: &Shape| crate::proximity::Elements::of(&model, s, T).unwrap();
        let (saddle_e, above_e, flat_e) = (elements(&saddle), elements(&above), elements(&flat));
        assert!(saddle_e.apart_by_more_than(&above_e, T.confusion(), T));
        assert!(!saddle_e.apart_by_more_than(&flat_e, T.confusion(), T));

        let nested = crate::make_compound(&mut model, &[saddle.clone(), above])
            .unwrap()
            .shape;
        assert!(
            check_self_intersection(&model, &nested, T)
                .unwrap()
                .is_empty()
        );
        let crossed = crate::make_compound(&mut model, &[saddle, flat])
            .unwrap()
            .shape;
        assert_eq!(
            check_self_intersection(&model, &crossed, T).unwrap().len(),
            1
        );
    }

    #[test]
    fn a_rigid_placement_does_not_change_which_faces_read_inside_out() {
        // Two overlapping boxes as the shells of one solid: the second
        // covers half of the first's top face, so that face reads facing
        // out over one half and in over the other, and its two triangles,
        // of one area, are probed on opposite halves. A rigid motion moves
        // the material with the face; it must not move which half is asked
        // by the rounding of the triangles' placed areas.
        use ogeom_math::{Point, Transform, Vector};
        let mut model = Model::new();
        let first = make_box(&mut model, Frame::WORLD, (2.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let at = Frame::WORLD.with_origin(Point::new(1.0, -1.0, 0.5));
        let second = make_box(&mut model, at, (2.0, 3.0, 1.0), T).unwrap().shape;
        let shells = [&first, &second]
            .map(|s| explore_unique(&model, s, ShapeType::Shell).unwrap()[0].clone());
        let solid = model.add_solid(&shells).unwrap();
        let named = |model: &Model, solid: &Shape| -> Vec<_> {
            inside_out_faces(model, solid, T)
                .unwrap()
                .iter()
                .map(|f| (f.node(), f.orientation()))
                .collect()
        };
        let unplaced = named(&model, &solid);
        for step in 1..48 {
            let angle = f64::from(step) * 0.131;
            let motion = Transform::translation(Vector::new(37.3, -11.9, 70.1))
                * Transform::rotation(ogeom_math::Axis::Z, angle)
                * Transform::rotation(ogeom_math::Axis::X, angle * 0.7);
            let placed = crate::transformed(&mut model, &solid, motion)
                .unwrap()
                .shape;
            assert_eq!(
                named(&model, &placed),
                unplaced,
                "placed by a rotation of {angle}, other faces read inside out"
            );
        }
    }

    /// A drum or a frustum with each rim circle restated on its frame
    /// mirrored (`y` reversed) or turned half a turn about `x`, so that it
    /// runs the other way round, its uses in the faces kept.
    fn rims_turned(frustum: bool, turn: fn(Frame) -> Frame) -> (Model, Shape, Shape) {
        use ogeom_geom::{CircleCurve, Curve};
        let mut model = Model::new();
        let solid = if frustum {
            crate::make_cone(&mut model, Frame::WORLD, 1.0, 0.5, 2.0, T)
        } else {
            make_cylinder(&mut model, Frame::WORLD, 1.0, 2.0, T)
        }
        .unwrap()
        .shape;
        let surface = |_: &ogeom_geom::SurfaceGeometry| Ok(None);
        let curve = |c: &Curve, range: (f64, f64)| {
            Ok(match c {
                Curve::Circle(c) => {
                    let circle = c.circle();
                    let circle = ogeom_math::Circle::new(turn(circle.frame()), circle.radius(), T)?;
                    Some((CircleCurve::new(circle).into(), range))
                }
                _ => None,
            })
        };
        let turned = crate::restate_geometry(&mut model, &solid, &surface, &curve, T)
            .unwrap()
            .shape;
        (model, solid, turned)
    }

    fn seam_side_findings(diagnosis: &Diagnosis) -> Vec<&Problem> {
        diagnosis
            .problems
            .iter()
            .filter(|p| p.what.contains("the side the face lies against"))
            .collect()
    }

    /// Rims turned to run the other way round, their uses kept: the wall's
    /// ring, each seam occurrence read on the side the face lies against,
    /// runs from one side to the other a whole period the wrong way, which
    /// a boolean through the wall reads as a strand that dangles. The wall
    /// is named, and nothing else; the drum as built is valid.
    #[test]
    fn rims_turned_over_under_their_uses_leave_the_wall_s_seam_open() {
        let turns: [fn(Frame) -> Frame; 2] = [
            |f| f.mirrored(),
            |f| Frame::from_axes(f.origin(), f.x(), -f.y(), -f.z(), T).unwrap(),
        ];
        for turn in turns {
            for frustum in [false, true] {
                let (model, solid, turned) = rims_turned(frustum, turn);
                assert!(check(&model, &solid, T).unwrap().is_valid());
                let diagnosis = check(&model, &turned, T).unwrap();
                let named = seam_side_findings(&diagnosis);
                assert_eq!(named.len(), 1, "{diagnosis}");
                assert_eq!(named[0].severity, Severity::Broken);
                let wall = model.node(&named[0].at).unwrap().data().as_face().unwrap();
                assert!(
                    model
                        .geometry()
                        .surface(wall.surface)
                        .unwrap()
                        .is_periodic_u(),
                    "{diagnosis}"
                );
            }
        }
    }

    /// The same turned drum restated as splines: the wall's chart closes
    /// without repeating, so every pcurve stands where its domain puts it
    /// and the ring is read as stated, as the boolean reads it. It is not
    /// named.
    #[test]
    fn rims_turned_over_on_a_chart_that_does_not_repeat_are_not_named() {
        let (mut model, _, turned) = rims_turned(false, |f| f.mirrored());
        let splines = crate::to_nurbs(&mut model, &turned, T).unwrap().shape;
        let diagnosis = check(&model, &splines, T).unwrap();
        assert!(seam_side_findings(&diagnosis).is_empty(), "{diagnosis}");
    }

    /// A rim stated a whole turn off the wall's window, still running the
    /// way the face needs, chains onto the seam's sides once moved by the
    /// turn, and is not named.
    #[test]
    fn a_rim_stated_a_turn_off_its_window_is_not_named() {
        let mut model = Model::new();
        let solid = make_cylinder(&mut model, Frame::WORLD, 1.0, 2.0, T)
            .unwrap()
            .shape;
        let mut moved = 0;
        for face in explore_unique(&model, &solid, ShapeType::Face).unwrap() {
            let surface = model.node(&face).unwrap().data().as_face().unwrap().surface;
            if !model.geometry().surface(surface).unwrap().is_periodic_u() {
                continue;
            }
            for edge in explore_unique(&model, &face, ShapeType::Edge).unwrap() {
                let data = model.node(&edge).unwrap().data().as_edge().unwrap();
                let Some(EdgeRepr::PCurve { curve, .. }) =
                    data.pcurve_for(surface, edge.location())
                else {
                    continue;
                };
                let curve = *curve;
                let off = ogeom_math::Transform2::translation(ogeom_math::Vector2::new(
                    2.0 * core::f64::consts::PI,
                    0.0,
                ));
                let shifted = model
                    .geometry()
                    .pcurve(curve)
                    .unwrap()
                    .transformed(&off, T)
                    .unwrap();
                *model.geometry_mut().pcurve_mut(curve).unwrap() = shifted;
                moved += 1;
            }
        }
        assert_eq!(moved, 2);
        let diagnosis = check(&model, &solid, T).unwrap();
        assert!(seam_side_findings(&diagnosis).is_empty(), "{diagnosis}");
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tessellation_tests {
    use super::*;
    use crate::{make_box, make_cone, make_cylinder, make_sphere, make_torus};
    use ogeom_math::{Frame, Point};
    use ogeom_topo::{NodeData, VertexData};

    const T: Tolerances = Tolerances::millimetres();

    fn fine() -> Deflection {
        Deflection {
            chord: 0.02,
            ..Deflection::default()
        }
    }

    #[test]
    fn every_primitive_tessellates_into_a_mesh_that_agrees_with_its_topology() {
        // The regression net for every seam and every pole. A primitive whose
        // shell closes but whose mesh does not is the failure this exists to
        // name, and it is invisible to every other check.
        let mut model = Model::new();
        let shapes = [
            make_box(&mut model, Frame::WORLD, (2.0, 3.0, 4.0), T)
                .unwrap()
                .shape,
            make_cylinder(&mut model, Frame::WORLD, 2.0, 5.0, T)
                .unwrap()
                .shape,
            make_sphere(&mut model, Frame::WORLD, 3.0, T).unwrap().shape,
            make_cone(&mut model, Frame::WORLD, 3.0, 1.0, 4.0, T)
                .unwrap()
                .shape,
            make_cone(&mut model, Frame::WORLD, 3.0, 0.0, 4.0, T)
                .unwrap()
                .shape,
            make_torus(&mut model, Frame::WORLD, 5.0, 2.0, T)
                .unwrap()
                .shape,
        ];
        for shape in &shapes {
            let found = check_tessellation(&model, shape, fine(), T).unwrap();
            assert!(found.is_valid(), "a primitive's mesh came apart: {found}");
        }
    }

    #[test]
    fn a_prism_tessellates_into_an_agreeing_mesh_whichever_face_it_swept() {
        // A sweep of a box's downward face must triangulate as well as one of
        // its upward face: lateral walls wound the wrong way fail to
        // triangulate while the shell still closes and every other check
        // passes. Both directions are covered, so a regression cannot hide
        // behind the one that works.
        use ogeom_math::Vector;
        for role in [
            crate::primitive::roles::FACE_MAX_Z,
            crate::primitive::roles::FACE_MIN_Z,
        ] {
            let mut model = Model::new();
            let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
                .unwrap()
                .shape;
            let face = explore_unique(&model, &solid, ShapeType::Face)
                .unwrap()
                .into_iter()
                .find(|f| {
                    model
                        .provenance_of(f)
                        .and_then(ogeom_core::Provenance::role)
                        == Some(role)
                })
                .expect("the box has a face with that role");
            let prism = crate::make_prism(&mut model, &face, Vector::new(0.0, 0.0, 2.0), T)
                .unwrap()
                .shape;
            assert!(
                check_tessellation(&model, &prism, fine(), T)
                    .unwrap()
                    .is_valid(),
                "{role:?}"
            );
            assert!(check(&model, &prism, T).unwrap().is_valid(), "{role:?}");
        }
    }

    #[test]
    fn moving_a_vertex_does_not_move_the_mesh() {
        // Tessellation reads curves and pcurves, never vertex positions, so a
        // vertex moved off its edges is caught by `check` (the curve no longer
        // reaches it) and is invisible to `check_tessellation`. The two checks
        // see different things, which is why both exist.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (2.0, 2.0, 2.0), T)
            .unwrap()
            .shape;
        let before = ogeom_mesh::triangulate(&model, &solid, fine(), T).unwrap();

        let vertex = explore_unique(&model, &solid, ShapeType::Vertex).unwrap()[0].clone();
        if let Some(NodeData::Vertex(data)) =
            model.node_mut(&vertex).map(ogeom_topo::TShape::data_mut)
        {
            data.point = Point::new(0.5, 0.5, 0.5);
        }

        let after = ogeom_mesh::triangulate(&model, &solid, fine(), T).unwrap();
        assert_eq!(before.positions, after.positions);
        assert!(
            check_tessellation(&model, &solid, fine(), T)
                .unwrap()
                .is_valid()
        );
        assert!(
            !check(&model, &solid, T).unwrap().is_usable(),
            "check sees it"
        );
    }

    #[test]
    fn an_open_shell_is_not_reported_because_it_never_claimed_to_close() {
        // A mesh with a boundary is agreement here, not disagreement. Flagging
        // it would make the check useless for every sheet body.
        let mut model = Model::new();
        let solid = make_box(&mut model, Frame::WORLD, (1.0, 1.0, 1.0), T)
            .unwrap()
            .shape;
        let face = explore_unique(&model, &solid, ShapeType::Face).unwrap()[0].clone();
        let shell = crate::build::make_shell(&mut model, std::slice::from_ref(&face))
            .unwrap()
            .shape;
        assert!(
            check_tessellation(&model, &shell, fine(), T)
                .unwrap()
                .is_valid()
        );
    }

    #[test]
    fn a_shape_with_no_shell_has_nothing_to_disagree_about() {
        let mut model = Model::new();
        let vertex = model.add_vertex(VertexData::new(Point::ORIGIN));
        assert!(
            check_tessellation(&model, &vertex, fine(), T)
                .unwrap()
                .is_valid()
        );
    }
}