use std::collections::{BTreeMap, BTreeSet};

use bone_kernel::{
    DatumFeature, ExtrudeFeature, RevolveAxis, RevolveFeature, SweepAlignment, SweepFeature,
    SweepPath,
};
use bone_types::{
    BodyId, DatumId, ExtrudeId, FeatureGeneration, FeatureId, Point3, RevolveId, RollbackMarker,
    SketchId, SketchPlaneBasis, SweepId, UnitVec3,
};
use serde::{Deserialize, Serialize};

use super::{gen_key, key_from_index, max_gen};
use crate::sketch3::Sketch3;

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum PrincipalPlane {
    Xy,
    Yz,
    Zx,
}

impl PrincipalPlane {
    #[must_use]
    pub fn basis(self) -> SketchPlaneBasis {
        let (x, y) = match self {
            Self::Xy => (UnitVec3::x_axis(), UnitVec3::y_axis()),
            Self::Yz => (UnitVec3::y_axis(), UnitVec3::z_axis()),
            Self::Zx => (UnitVec3::z_axis(), UnitVec3::x_axis()),
        };
        SketchPlaneBasis::new_unchecked(Point3::origin(), x, y)
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum FeatureNode {
    Origin,
    PrincipalPlane(PrincipalPlane),
    Sketch(SketchId),
    Extrude(ExtrudeId),
    Revolve(RevolveId),
    Sweep(SweepId),
    Datum(DatumId),
    ImportedBody(BodyId),
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub enum FeatureEdge {
    SketchToExtrude {
        sketch: FeatureId,
        extrude: FeatureId,
    },
    FaceToSketch {
        face_feature: FeatureId,
        sketch: FeatureId,
    },
    ReferenceToDatum {
        reference: FeatureId,
        datum: FeatureId,
    },
    AxisToRevolve {
        axis: FeatureId,
        revolve: FeatureId,
    },
    PathToSweep {
        path: FeatureId,
        sweep: FeatureId,
    },
    AxisToSweep {
        axis: FeatureId,
        sweep: FeatureId,
    },
    PierceToSketch {
        curve_sketch: FeatureId,
        sketch: FeatureId,
    },
}

impl FeatureEdge {
    #[must_use]
    pub fn endpoints(self) -> (FeatureId, FeatureId) {
        match self {
            Self::SketchToExtrude { sketch, extrude } => (sketch, extrude),
            Self::FaceToSketch {
                face_feature,
                sketch,
            } => (face_feature, sketch),
            Self::ReferenceToDatum { reference, datum } => (reference, datum),
            Self::AxisToRevolve { axis, revolve } => (axis, revolve),
            Self::PathToSweep { path, sweep } => (path, sweep),
            Self::AxisToSweep { axis, sweep } => (axis, sweep),
            Self::PierceToSketch {
                curve_sketch,
                sketch,
            } => (curve_sketch, sketch),
        }
    }
}

fn axis_source(axis: RevolveAxis) -> Option<FeatureId> {
    match axis {
        RevolveAxis::SketchLine(_) => None,
        RevolveAxis::Edge(label) => Some(label.feature),
        RevolveAxis::Datum(datum) => Some(datum),
        RevolveAxis::Sketch3Line { sketch, .. } => Some(sketch),
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
struct FeatureEntry {
    id: FeatureId,
    node: FeatureNode,
}

#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub struct FeatureTree {
    entries: Vec<FeatureEntry>,
    #[serde(default)]
    id_high_water: FeatureGeneration,
    #[serde(skip)]
    edges: Vec<FeatureEdge>,
}

impl FeatureTree {
    #[must_use]
    pub fn seeded() -> Self {
        let seeds = [
            FeatureNode::Origin,
            FeatureNode::PrincipalPlane(PrincipalPlane::Xy),
            FeatureNode::PrincipalPlane(PrincipalPlane::Yz),
            FeatureNode::PrincipalPlane(PrincipalPlane::Zx),
        ];
        let entries: Vec<FeatureEntry> = seeds
            .into_iter()
            .zip(1u32..)
            .map(|(node, idx)| FeatureEntry {
                id: key_from_index(idx),
                node,
            })
            .collect();
        let id_high_water = max_gen(entries.iter().map(|e| e.id));
        Self {
            entries,
            id_high_water,
            edges: Vec::new(),
        }
    }

    #[must_use]
    pub fn node(&self, id: FeatureId) -> Option<FeatureNode> {
        self.entries.iter().find(|e| e.id == id).map(|e| e.node)
    }

    pub fn iter(&self) -> impl Iterator<Item = (FeatureId, FeatureNode)> + '_ {
        self.entries.iter().map(|e| (e.id, e.node))
    }

    #[must_use]
    pub fn feature_of_sketch(&self, sketch: SketchId) -> Option<FeatureId> {
        self.feature_of(|node| matches!(node, FeatureNode::Sketch(s) if *s == sketch))
    }

    #[must_use]
    pub fn origin_feature(&self) -> Option<FeatureId> {
        self.feature_of(|node| matches!(node, FeatureNode::Origin))
    }

    #[must_use]
    pub fn principal_plane_feature(&self, plane: PrincipalPlane) -> Option<FeatureId> {
        self.feature_of(|node| matches!(node, FeatureNode::PrincipalPlane(p) if *p == plane))
    }

    pub fn push_sketch(&mut self, sketch: SketchId) -> FeatureId {
        if let Some(existing) = self.feature_of_sketch(sketch) {
            return existing;
        }
        let id = self.allocate();
        self.entries.push(FeatureEntry {
            id,
            node: FeatureNode::Sketch(sketch),
        });
        id
    }

    pub fn remove_sketch(&mut self, sketch: SketchId) -> Option<FeatureId> {
        let id = self.feature_of_sketch(sketch)?;
        self.entries.retain(|e| e.id != id);
        self.drop_edges_incident(id);
        Some(id)
    }

    #[must_use]
    pub fn feature_of_extrude(&self, extrude: ExtrudeId) -> Option<FeatureId> {
        self.feature_of(|node| matches!(node, FeatureNode::Extrude(x) if *x == extrude))
    }

    pub fn push_extrude(&mut self, extrude: ExtrudeId, feature: &ExtrudeFeature) -> FeatureId {
        let id = self.feature_of_extrude(extrude).unwrap_or_else(|| {
            let id = self.allocate();
            self.entries.push(FeatureEntry {
                id,
                node: FeatureNode::Extrude(extrude),
            });
            id
        });
        let edge = self.sketch_edge(id, feature);
        self.drop_sketch_to_extrude(id);
        self.edges.extend(edge);
        self.edges.sort_unstable();
        id
    }

    pub fn remove_extrude(&mut self, extrude: ExtrudeId) -> Option<FeatureId> {
        let id = self.feature_of_extrude(extrude)?;
        self.entries.retain(|e| e.id != id);
        self.drop_edges_incident(id);
        Some(id)
    }

    #[must_use]
    pub fn feature_of_revolve(&self, revolve: RevolveId) -> Option<FeatureId> {
        self.feature_of(|node| matches!(node, FeatureNode::Revolve(x) if *x == revolve))
    }

    pub fn push_revolve(&mut self, revolve: RevolveId, feature: &RevolveFeature) -> FeatureId {
        let id = self.feature_of_revolve(revolve).unwrap_or_else(|| {
            let id = self.allocate();
            self.entries.push(FeatureEntry {
                id,
                node: FeatureNode::Revolve(revolve),
            });
            id
        });
        let edges = self.revolve_edges(id, feature);
        self.drop_sketch_to_extrude(id);
        self.drop_axis_to_revolve(id);
        self.edges.extend(edges);
        self.edges.sort_unstable();
        self.edges.dedup();
        id
    }

    pub fn remove_revolve(&mut self, revolve: RevolveId) -> Option<FeatureId> {
        let id = self.feature_of_revolve(revolve)?;
        self.entries.retain(|e| e.id != id);
        self.drop_edges_incident(id);
        Some(id)
    }

    #[must_use]
    pub fn feature_of_sweep(&self, sweep: SweepId) -> Option<FeatureId> {
        self.feature_of(|node| matches!(node, FeatureNode::Sweep(x) if *x == sweep))
    }

    pub fn push_sweep(&mut self, sweep: SweepId, feature: &SweepFeature) -> FeatureId {
        let id = self.feature_of_sweep(sweep).unwrap_or_else(|| {
            let id = self.allocate();
            self.entries.push(FeatureEntry {
                id,
                node: FeatureNode::Sweep(sweep),
            });
            id
        });
        let edges = self.sweep_edges(id, feature);
        self.drop_sketch_to_extrude(id);
        self.drop_path_to_sweep(id);
        self.drop_axis_to_sweep(id);
        self.edges.extend(edges);
        self.edges.sort_unstable();
        self.edges.dedup();
        id
    }

    pub fn remove_sweep(&mut self, sweep: SweepId) -> Option<FeatureId> {
        let id = self.feature_of_sweep(sweep)?;
        self.entries.retain(|e| e.id != id);
        self.drop_edges_incident(id);
        Some(id)
    }

    #[must_use]
    pub fn feature_of_datum(&self, datum: DatumId) -> Option<FeatureId> {
        self.feature_of(|node| matches!(node, FeatureNode::Datum(d) if *d == datum))
    }

    pub fn push_datum(&mut self, datum: DatumId, feature: &DatumFeature) -> FeatureId {
        let id = self.feature_of_datum(datum).unwrap_or_else(|| {
            let id = self.allocate();
            self.entries.push(FeatureEntry {
                id,
                node: FeatureNode::Datum(datum),
            });
            id
        });
        let edges = self.datum_edges(id, feature);
        self.drop_reference_to_datum(id);
        self.edges.extend(edges);
        self.edges.sort_unstable();
        self.edges.dedup();
        id
    }

    pub fn remove_datum(&mut self, datum: DatumId) -> Option<FeatureId> {
        let id = self.feature_of_datum(datum)?;
        self.entries.retain(|e| e.id != id);
        self.drop_edges_incident(id);
        Some(id)
    }

    fn datum_edges(&self, datum: FeatureId, feature: &DatumFeature) -> Vec<FeatureEdge> {
        let mut references: Vec<FeatureId> = feature
            .targets()
            .into_iter()
            .map(bone_types::DatumTarget::source_feature)
            .filter(|reference| *reference != datum && self.node(*reference).is_some())
            .collect();
        references.sort_unstable();
        references.dedup();
        references
            .into_iter()
            .map(|reference| FeatureEdge::ReferenceToDatum { reference, datum })
            .collect()
    }

    #[must_use]
    pub(crate) fn datum_reference_conflict(
        &self,
        datum: DatumId,
        feature: &DatumFeature,
    ) -> Option<FeatureId> {
        let id = self.feature_of_datum(datum)?;
        let descendants = self.descendants(id);
        let here = self.position_of(id);
        feature
            .targets()
            .into_iter()
            .map(bone_types::DatumTarget::source_feature)
            .filter(|reference| *reference != id && self.node(*reference).is_some())
            .find(|reference| {
                descendants.contains(reference)
                    || matches!(
                        (self.position_of(*reference), here),
                        (Some(reference_at), Some(here_at)) if reference_at >= here_at
                    )
            })
    }

    fn drop_reference_to_datum(&mut self, datum: FeatureId) {
        self.edges.retain(|edge| {
            !matches!(edge, FeatureEdge::ReferenceToDatum { datum: target, .. } if *target == datum)
        });
    }

    pub fn push_imported_body(&mut self, feature: FeatureId, body: BodyId) {
        self.entries.push(FeatureEntry {
            id: feature,
            node: FeatureNode::ImportedBody(body),
        });
    }

    fn position_of(&self, id: FeatureId) -> Option<usize> {
        self.entries.iter().position(|entry| entry.id == id)
    }

    pub(crate) fn move_before(&mut self, id: FeatureId, anchor: FeatureId) {
        if id == anchor {
            return;
        }
        let Some(from) = self.position_of(id) else {
            return;
        };
        let entry = self.entries.remove(from);
        match self.position_of(anchor) {
            Some(to) => self.entries.insert(to, entry),
            None => self.entries.push(entry),
        }
    }

    fn place(&mut self, moved: FeatureId, anchor: FeatureId, before: bool) {
        if before {
            self.move_before(moved, anchor);
        } else {
            self.move_after(moved, anchor);
        }
    }

    #[must_use]
    pub(crate) fn reorder_is_legal(
        &self,
        moved: FeatureId,
        anchor: FeatureId,
        before: bool,
    ) -> bool {
        if self.is_seeded_reference(moved) || self.is_seeded_reference(anchor) || moved == anchor {
            return false;
        }
        let mut trial = self.clone();
        trial.place(moved, anchor, before);
        trial.order_violation().is_none()
    }

    pub(crate) fn try_reorder(
        &mut self,
        moved: FeatureId,
        anchor: FeatureId,
        before: bool,
    ) -> bool {
        if !self.reorder_is_legal(moved, anchor, before) {
            return false;
        }
        self.place(moved, anchor, before);
        true
    }

    pub(crate) fn move_before_keeping_order(&mut self, id: FeatureId, anchor: FeatureId) {
        let last_parent = self
            .parents(id)
            .into_iter()
            .filter_map(|parent| self.position_of(parent).map(|pos| (pos, parent)))
            .max();
        match (self.position_of(anchor), last_parent) {
            (Some(anchor_at), Some((parent_at, parent))) if parent_at >= anchor_at => {
                self.move_after(id, parent);
            }
            (Some(_), _) => self.move_before(id, anchor),
            (None, _) => {}
        }
    }

    fn move_after(&mut self, id: FeatureId, anchor: FeatureId) {
        if id == anchor {
            return;
        }
        let Some(from) = self.position_of(id) else {
            return;
        };
        let entry = self.entries.remove(from);
        match self.position_of(anchor) {
            Some(to) => self.entries.insert(to + 1, entry),
            None => self.entries.push(entry),
        }
    }

    fn reorder_after(&mut self, feature: FeatureId, anchor: FeatureId) {
        let already_ordered = matches!(
            (self.position_of(feature), self.position_of(anchor)),
            (Some(child), Some(parent)) if child > parent
        );
        if already_ordered {
            return;
        }
        self.move_after(feature, anchor);
        self.children(feature)
            .into_iter()
            .for_each(|child| self.reorder_after(child, feature));
    }

    #[must_use]
    pub fn edges(&self) -> &[FeatureEdge] {
        &self.edges
    }

    pub(crate) fn rebuild_edges<'a>(
        &mut self,
        extrudes: impl Iterator<Item = (ExtrudeId, &'a ExtrudeFeature)>,
        revolves: impl Iterator<Item = (RevolveId, &'a RevolveFeature)>,
        sweeps: impl Iterator<Item = (SweepId, &'a SweepFeature)>,
        datums: impl Iterator<Item = (DatumId, &'a DatumFeature)>,
        sketches: impl Iterator<Item = (SketchId, &'a Sketch3)>,
        face_bindings: impl Iterator<Item = (FeatureId, FeatureId)>,
    ) {
        let mut rebuilt: Vec<FeatureEdge> = extrudes
            .filter_map(|(extrude, feature)| {
                let extrude = self.feature_of_extrude(extrude)?;
                self.sketch_edge(extrude, feature)
            })
            .collect();
        rebuilt.extend(revolves.flat_map(|(revolve, feature)| {
            self.feature_of_revolve(revolve)
                .map(|revolve| self.revolve_edges(revolve, feature))
                .unwrap_or_default()
        }));
        rebuilt.extend(sweeps.flat_map(|(sweep, feature)| {
            self.feature_of_sweep(sweep)
                .map(|sweep| self.sweep_edges(sweep, feature))
                .unwrap_or_default()
        }));
        rebuilt.extend(datums.flat_map(|(datum, feature)| {
            self.feature_of_datum(datum)
                .map(|datum| self.datum_edges(datum, feature))
                .unwrap_or_default()
        }));
        rebuilt.extend(sketches.flat_map(|(sketch_id, sketch)| {
            self.feature_of_sketch(sketch_id)
                .map(|sketch_feature| Self::pierce_edges(sketch_feature, sketch))
                .unwrap_or_default()
        }));
        rebuilt.extend(
            face_bindings.map(|(face_feature, sketch)| FeatureEdge::FaceToSketch {
                face_feature,
                sketch,
            }),
        );
        rebuilt.sort_unstable();
        rebuilt.dedup();
        self.edges = rebuilt;
    }

    pub(crate) fn bind_face_to_sketch(&mut self, face_feature: FeatureId, sketch: FeatureId) {
        self.edges.retain(|edge| {
            !matches!(edge, FeatureEdge::FaceToSketch { sketch: target, .. } if *target == sketch)
        });
        self.edges.push(FeatureEdge::FaceToSketch {
            face_feature,
            sketch,
        });
        self.edges.sort_unstable();
        self.reorder_after(sketch, face_feature);
    }

    fn sketch_edge(&self, extrude: FeatureId, feature: &ExtrudeFeature) -> Option<FeatureEdge> {
        let sketch = self.feature_of_sketch(feature.sketch)?;
        Some(FeatureEdge::SketchToExtrude { sketch, extrude })
    }

    fn revolve_edges(&self, revolve: FeatureId, feature: &RevolveFeature) -> Vec<FeatureEdge> {
        self.revolve_sketch_edge(revolve, feature)
            .into_iter()
            .chain(self.revolve_axis_edge(revolve, feature))
            .collect()
    }

    fn revolve_sketch_edge(
        &self,
        revolve: FeatureId,
        feature: &RevolveFeature,
    ) -> Option<FeatureEdge> {
        let sketch = self.feature_of_sketch(feature.sketch)?;
        Some(FeatureEdge::SketchToExtrude {
            sketch,
            extrude: revolve,
        })
    }

    fn revolve_axis_edge(
        &self,
        revolve: FeatureId,
        feature: &RevolveFeature,
    ) -> Option<FeatureEdge> {
        let axis = axis_source(feature.axis)?;
        (axis != revolve && self.node(axis).is_some() && self.precedes(axis, revolve))
            .then_some(FeatureEdge::AxisToRevolve { axis, revolve })
    }

    fn precedes(&self, earlier: FeatureId, later: FeatureId) -> bool {
        matches!(
            (self.position_of(earlier), self.position_of(later)),
            (Some(a), Some(b)) if a < b
        )
    }

    fn drop_axis_to_revolve(&mut self, revolve: FeatureId) {
        self.edges.retain(|edge| {
            !matches!(edge, FeatureEdge::AxisToRevolve { revolve: target, .. } if *target == revolve)
        });
    }

    fn pierce_edges(sketch_feature: FeatureId, sketch: &Sketch3) -> Vec<FeatureEdge> {
        sketch
            .pierce_curve_sketches()
            .filter(|&curve_sketch| curve_sketch != sketch_feature)
            .map(|curve_sketch| FeatureEdge::PierceToSketch {
                curve_sketch,
                sketch: sketch_feature,
            })
            .fold(Vec::new(), |mut edges, edge| {
                if !edges.contains(&edge) {
                    edges.push(edge);
                }
                edges
            })
    }

    fn sweep_edges(&self, sweep: FeatureId, feature: &SweepFeature) -> Vec<FeatureEdge> {
        self.sweep_profile_edge(sweep, feature)
            .into_iter()
            .chain(self.sweep_rail_edge(sweep, feature.path))
            .chain(
                feature
                    .guides
                    .iter()
                    .filter_map(|guide| self.sweep_rail_edge(sweep, *guide)),
            )
            .chain(self.sweep_axis_edge(sweep, feature))
            .fold(Vec::new(), |mut edges, edge| {
                if !edges.contains(&edge) {
                    edges.push(edge);
                }
                edges
            })
    }

    fn sweep_profile_edge(&self, sweep: FeatureId, feature: &SweepFeature) -> Option<FeatureEdge> {
        let sketch = self.feature_of_sketch(feature.profile)?;
        Some(FeatureEdge::SketchToExtrude {
            sketch,
            extrude: sweep,
        })
    }

    fn sweep_rail_edge(&self, sweep: FeatureId, rail: SweepPath) -> Option<FeatureEdge> {
        let path = match rail {
            SweepPath::Sketch(sketch) => self.feature_of_sketch(sketch)?,
            SweepPath::Edge(label) => label.feature,
        };
        (path != sweep && self.node(path).is_some() && self.precedes(path, sweep))
            .then_some(FeatureEdge::PathToSweep { path, sweep })
    }

    fn sweep_axis_edge(&self, sweep: FeatureId, feature: &SweepFeature) -> Option<FeatureEdge> {
        let SweepAlignment::DirectionVector { axis } = feature.alignment else {
            return None;
        };
        let axis = axis_source(axis)?;
        (axis != sweep && self.node(axis).is_some() && self.precedes(axis, sweep))
            .then_some(FeatureEdge::AxisToSweep { axis, sweep })
    }

    fn drop_path_to_sweep(&mut self, sweep: FeatureId) {
        self.edges.retain(|edge| {
            !matches!(edge, FeatureEdge::PathToSweep { sweep: target, .. } if *target == sweep)
        });
    }

    fn drop_axis_to_sweep(&mut self, sweep: FeatureId) {
        self.edges.retain(|edge| {
            !matches!(edge, FeatureEdge::AxisToSweep { sweep: target, .. } if *target == sweep)
        });
    }

    fn drop_edges_incident(&mut self, feature: FeatureId) {
        self.edges.retain(|edge| {
            let (parent, child) = edge.endpoints();
            parent != feature && child != feature
        });
    }

    fn drop_sketch_to_extrude(&mut self, extrude: FeatureId) {
        self.edges.retain(|edge| {
            !matches!(edge, FeatureEdge::SketchToExtrude { extrude: target, .. } if *target == extrude)
        });
    }

    fn feature_of(&self, matches_node: impl Fn(&FeatureNode) -> bool) -> Option<FeatureId> {
        self.entries
            .iter()
            .find(|e| matches_node(&e.node))
            .map(|e| e.id)
    }

    pub(crate) fn allocate(&mut self) -> FeatureId {
        let next = self
            .id_high_water
            .raised_to(max_gen(self.entries.iter().map(|e| e.id)))
            .succ();
        self.id_high_water = next;
        gen_key(next)
    }

    pub(crate) fn raise_high_water(&mut self) {
        self.id_high_water = self
            .id_high_water
            .raised_to(max_gen(self.entries.iter().map(|e| e.id)));
    }

    #[must_use]
    pub fn children(&self, id: FeatureId) -> Vec<FeatureId> {
        self.edges
            .iter()
            .map(|edge| edge.endpoints())
            .filter(|(parent, _)| *parent == id)
            .map(|(_, child)| child)
            .collect::<BTreeSet<_>>()
            .into_iter()
            .collect()
    }

    #[must_use]
    pub fn parents(&self, id: FeatureId) -> Vec<FeatureId> {
        self.edges
            .iter()
            .map(|edge| edge.endpoints())
            .filter(|(_, child)| *child == id)
            .map(|(parent, _)| parent)
            .collect::<BTreeSet<_>>()
            .into_iter()
            .collect()
    }

    #[must_use]
    pub fn descendants(&self, id: FeatureId) -> Vec<FeatureId> {
        reachable(id, &self.adjacency(Direction::Forward), BTreeSet::new())
            .into_iter()
            .collect()
    }

    #[must_use]
    pub fn ancestors(&self, id: FeatureId) -> Vec<FeatureId> {
        reachable(id, &self.adjacency(Direction::Backward), BTreeSet::new())
            .into_iter()
            .collect()
    }

    #[must_use]
    pub fn rolled_back(&self, marker: RollbackMarker) -> BTreeSet<FeatureId> {
        let Some(target) = marker.feature() else {
            return BTreeSet::new();
        };
        self.position_of(target)
            .map(|start| self.entries[start..].iter().map(|entry| entry.id).collect())
            .unwrap_or_default()
    }

    #[must_use]
    pub(crate) fn rollable_order(&self) -> Vec<FeatureId> {
        self.entries
            .iter()
            .filter(|entry| {
                !matches!(
                    entry.node,
                    FeatureNode::Origin | FeatureNode::PrincipalPlane(_)
                )
            })
            .map(|entry| entry.id)
            .collect()
    }

    #[must_use]
    pub fn is_seeded_reference(&self, id: FeatureId) -> bool {
        matches!(
            self.node(id),
            Some(FeatureNode::Origin | FeatureNode::PrincipalPlane(_))
        )
    }

    #[must_use]
    pub(crate) fn order_violation(&self) -> Option<FeatureEdge> {
        self.edges.iter().copied().find(|edge| {
            let (parent, child) = edge.endpoints();
            matches!(
                (self.position_of(parent), self.position_of(child)),
                (Some(parent_at), Some(child_at)) if parent_at >= child_at
            )
        })
    }

    #[must_use]
    pub(crate) fn find_cycle(&self) -> Option<FeatureId> {
        let adjacency = self.adjacency(Direction::Forward);
        self.entries
            .iter()
            .fold((BTreeSet::new(), None), |(done, found), entry| {
                if found.is_some() || done.contains(&entry.id) {
                    (done, found)
                } else {
                    detect_cycle(entry.id, &adjacency, done, BTreeSet::new())
                }
            })
            .1
    }

    #[must_use]
    pub fn topo_order(&self) -> Vec<FeatureId> {
        self.entries.iter().map(|entry| entry.id).collect()
    }

    fn adjacency(&self, direction: Direction) -> BTreeMap<FeatureId, BTreeSet<FeatureId>> {
        self.edges.iter().map(|edge| edge.endpoints()).fold(
            BTreeMap::new(),
            |mut acc, (parent, child)| {
                let (from, to) = match direction {
                    Direction::Forward => (parent, child),
                    Direction::Backward => (child, parent),
                };
                acc.entry(from).or_default().insert(to);
                acc
            },
        )
    }
}

#[derive(Copy, Clone)]
enum Direction {
    Forward,
    Backward,
}

fn reachable(
    start: FeatureId,
    adjacency: &BTreeMap<FeatureId, BTreeSet<FeatureId>>,
    reached: BTreeSet<FeatureId>,
) -> BTreeSet<FeatureId> {
    adjacency
        .get(&start)
        .into_iter()
        .flatten()
        .fold(reached, |reached, &next| {
            if reached.contains(&next) {
                reached
            } else {
                reachable(next, adjacency, insert(reached, next))
            }
        })
}

fn detect_cycle(
    node: FeatureId,
    adjacency: &BTreeMap<FeatureId, BTreeSet<FeatureId>>,
    done: BTreeSet<FeatureId>,
    on_path: BTreeSet<FeatureId>,
) -> (BTreeSet<FeatureId>, Option<FeatureId>) {
    let on_path = insert(on_path, node);
    let (done, found) =
        adjacency
            .get(&node)
            .into_iter()
            .flatten()
            .fold((done, None), |(done, found), &next| {
                if found.is_some() {
                    (done, found)
                } else if on_path.contains(&next) {
                    (done, Some(next))
                } else if done.contains(&next) {
                    (done, None)
                } else {
                    detect_cycle(next, adjacency, done, on_path.clone())
                }
            });
    (insert(done, node), found)
}

fn insert(set: BTreeSet<FeatureId>, value: FeatureId) -> BTreeSet<FeatureId> {
    let mut next = set;
    next.insert(value);
    next
}

#[cfg(test)]
pub(crate) fn sample_blind_extrude(sketch: SketchId) -> ExtrudeFeature {
    use bone_types::{Length, PositiveLength, millimeter};
    let Ok(depth) = PositiveLength::new(Length::new::<millimeter>(10.0)) else {
        panic!("10 mm is a positive length");
    };
    ExtrudeFeature::blind(sketch, depth)
}

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

    use proptest::prelude::*;

    use super::{FeatureEdge, FeatureId, FeatureNode, FeatureTree, sample_blind_extrude};
    use bone_types::{ExtrudeId, SketchId};

    fn sketch_key(n: u64) -> SketchId {
        use slotmap::KeyData;
        SketchId::from(KeyData::from_ffi((1u64 << 32) | n))
    }

    #[test]
    fn push_and_remove_extrude_maintain_nodes_and_edges() {
        let mut tree = FeatureTree::seeded();
        let sketch = SketchId::default();
        let sketch_feature = tree.push_sketch(sketch);
        let extrude = ExtrudeId::default();
        let extrude_feature = tree.push_extrude(extrude, &sample_blind_extrude(sketch));
        assert_eq!(
            tree.node(extrude_feature),
            Some(FeatureNode::Extrude(extrude))
        );
        assert_eq!(tree.feature_of_extrude(extrude), Some(extrude_feature));
        assert_eq!(
            tree.edges(),
            &[FeatureEdge::SketchToExtrude {
                sketch: sketch_feature,
                extrude: extrude_feature,
            }]
        );

        let mut tree = FeatureTree::seeded();
        let sketch = SketchId::default();
        tree.push_sketch(sketch);
        let extrude = ExtrudeId::default();
        let feature = sample_blind_extrude(sketch);
        let first = tree.push_extrude(extrude, &feature);
        let count_before = tree.iter().count();
        let second = tree.push_extrude(extrude, &feature);
        assert_eq!(first, second);
        assert_eq!(tree.iter().count(), count_before);
        assert_eq!(tree.edges().len(), 1);

        let mut tree = FeatureTree::seeded();
        let extrude = ExtrudeId::default();
        let extrude_feature =
            tree.push_extrude(extrude, &sample_blind_extrude(SketchId::default()));
        assert_eq!(
            tree.node(extrude_feature),
            Some(FeatureNode::Extrude(extrude))
        );
        assert!(tree.edges().is_empty());

        let mut tree = FeatureTree::seeded();
        let sketch_a = sketch_key(1);
        let sketch_b = sketch_key(2);
        tree.push_sketch(sketch_a);
        let feat_b = tree.push_sketch(sketch_b);
        let extrude = ExtrudeId::default();
        let ext_feat = tree.push_extrude(extrude, &sample_blind_extrude(sketch_a));
        tree.push_extrude(extrude, &sample_blind_extrude(sketch_b));
        assert_eq!(
            tree.edges(),
            &[FeatureEdge::SketchToExtrude {
                sketch: feat_b,
                extrude: ext_feat,
            }]
        );

        let mut tree = FeatureTree::seeded();
        let sketch = SketchId::default();
        tree.push_sketch(sketch);
        let extrude = ExtrudeId::default();
        let ext_feat = tree.push_extrude(extrude, &sample_blind_extrude(sketch));
        let downstream = tree.push_sketch(sketch_key(2));
        let face_edge = FeatureEdge::FaceToSketch {
            face_feature: ext_feat,
            sketch: downstream,
        };
        tree.edges.push(face_edge);
        tree.edges.sort_unstable();
        tree.push_extrude(extrude, &sample_blind_extrude(sketch));
        assert!(
            tree.edges().contains(&face_edge),
            "re-pushing an extrude must not erase a downstream face-bound dependency"
        );
        assert_eq!(
            tree.edges()
                .iter()
                .filter(|e| matches!(e, FeatureEdge::SketchToExtrude { extrude, .. } if *extrude == ext_feat))
                .count(),
            1,
            "the sketch-to-extrude edge stays single after a re-push"
        );

        let mut tree = FeatureTree::seeded();
        let sketch = SketchId::default();
        tree.push_sketch(sketch);
        let extrude = ExtrudeId::default();
        tree.push_extrude(extrude, &sample_blind_extrude(sketch));
        assert_eq!(tree.edges().len(), 1);
        let removed = tree.remove_extrude(extrude);
        assert!(removed.is_some());
        assert_eq!(tree.feature_of_extrude(extrude), None);
        assert!(tree.edges().is_empty());
    }

    fn extrude_key(n: u64) -> ExtrudeId {
        use slotmap::KeyData;
        ExtrudeId::from(KeyData::from_ffi((1u64 << 32) | n))
    }

    #[test]
    fn edges_are_derived_and_canonical() -> Result<(), Box<dyn std::error::Error>> {
        let mut tree = FeatureTree::seeded();
        let sketch = SketchId::default();
        tree.push_sketch(sketch);
        tree.push_extrude(ExtrudeId::default(), &sample_blind_extrude(sketch));
        assert_eq!(tree.edges().len(), 1);
        let ron = crate::io::ron_io::to_string(&tree)?;
        assert!(!ron.contains("edges"));
        let back = crate::io::ron_io::from_str::<FeatureTree>(&ron)?;
        assert!(back.edges().is_empty());

        let sketch = SketchId::default();
        let high = extrude_key(5);
        let low = extrude_key(2);
        let mut pushed = FeatureTree::seeded();
        pushed.push_sketch(sketch);
        pushed.push_extrude(high, &sample_blind_extrude(sketch));
        pushed.push_extrude(low, &sample_blind_extrude(sketch));
        let mut rebuilt = pushed.clone();
        let extrudes = std::collections::BTreeMap::from([
            (low, sample_blind_extrude(sketch)),
            (high, sample_blind_extrude(sketch)),
        ]);
        rebuilt.rebuild_edges(
            extrudes.iter().map(|(id, feature)| (*id, feature)),
            std::iter::empty(),
            std::iter::empty(),
            std::iter::empty(),
            std::iter::empty::<(SketchId, &crate::sketch3::Sketch3)>(),
            std::iter::empty(),
        );
        assert_eq!(
            pushed.edges(),
            rebuilt.edges(),
            "live edge order must match the load rebuild irrespective of push order"
        );
        assert_eq!(pushed.edges().len(), 2);
        Ok(())
    }

    #[test]
    fn graph_queries_ordering_binding_and_cycles() {
        let mut tree = FeatureTree::seeded();
        let (sketch_feature, extrude_feature) =
            sketch_extrude_pair(&mut tree, sketch_key(1), extrude_key(1));
        assert_eq!(tree.children(sketch_feature), vec![extrude_feature]);
        assert_eq!(tree.parents(extrude_feature), vec![sketch_feature]);
        assert!(tree.children(extrude_feature).is_empty());
        assert!(tree.parents(sketch_feature).is_empty());
        assert_eq!(tree.descendants(sketch_feature), vec![extrude_feature]);
        assert_eq!(tree.ancestors(extrude_feature), vec![sketch_feature]);
        assert!(tree.descendants(extrude_feature).is_empty());
        assert!(tree.ancestors(sketch_feature).is_empty());
        let order = tree.topo_order();
        let all: BTreeSet<FeatureId> = tree.iter().map(|(id, _)| id).collect();
        assert_eq!(
            order.iter().copied().collect::<BTreeSet<_>>(),
            all,
            "topo order must visit every node exactly once"
        );
        let pos = |id| order.iter().position(|other| *other == id);
        assert!(
            pos(sketch_feature) < pos(extrude_feature),
            "a parent must precede its child"
        );

        assert!(
            tree.order_violation().is_none(),
            "a freshly built sketch-then-extrude chain is in dependency order",
        );
        tree.move_before(extrude_feature, sketch_feature);
        assert_eq!(
            tree.order_violation().map(FeatureEdge::endpoints),
            Some((sketch_feature, extrude_feature)),
            "moving the extrude above its sketch is reported as an order violation",
        );

        let parent = super::super::key_from_index::<FeatureId>(7);
        let child = super::super::key_from_index::<FeatureId>(9);
        assert_eq!(
            FeatureEdge::SketchToExtrude {
                sketch: parent,
                extrude: child,
            }
            .endpoints(),
            (parent, child)
        );
        assert_eq!(
            FeatureEdge::FaceToSketch {
                face_feature: parent,
                sketch: child,
            }
            .endpoints(),
            (parent, child)
        );

        let mut tree = FeatureTree::seeded();
        let first = tree.push_sketch(sketch_key(1));
        tree.remove_sketch(sketch_key(1));
        let second = tree.push_sketch(sketch_key(2));
        assert_ne!(
            first, second,
            "a removed top id must never be handed out again"
        );

        let mut tree = FeatureTree::seeded();
        let early_sketch = tree.push_sketch(sketch_key(1));
        let early_extrude = tree.push_extrude(extrude_key(1), &sample_blind_extrude(sketch_key(1)));
        tree.push_sketch(sketch_key(2));
        let body = tree.push_extrude(extrude_key(2), &sample_blind_extrude(sketch_key(2)));
        tree.bind_face_to_sketch(body, early_sketch);
        assert!(
            tree.order_violation().is_none(),
            "binding an earlier sketch onto a later body drags its subtree past the target",
        );
        let order = tree.rollable_order();
        let position = |needle: FeatureId| order.iter().position(|f| *f == needle);
        assert!(
            position(body) < position(early_sketch),
            "the bound sketch now follows the body it sits on",
        );
        assert!(
            position(early_sketch) < position(early_extrude),
            "the bound sketch still precedes its own extrude",
        );

        let mut tree = FeatureTree::seeded();
        let a = tree.push_sketch(sketch_key(1));
        let b = tree.push_sketch(sketch_key(2));
        assert_eq!(tree.find_cycle(), None);
        tree.edges = vec![
            FeatureEdge::SketchToExtrude {
                sketch: a,
                extrude: b,
            },
            FeatureEdge::SketchToExtrude {
                sketch: b,
                extrude: a,
            },
        ];
        tree.edges.sort_unstable();
        assert!(
            tree.find_cycle().is_some(),
            "a back edge in the dependency graph must be reported"
        );
    }

    fn sketch_extrude_pair(
        tree: &mut FeatureTree,
        sketch: SketchId,
        extrude: ExtrudeId,
    ) -> (FeatureId, FeatureId) {
        let sketch_feature = tree.push_sketch(sketch);
        let extrude_feature = tree.push_extrude(extrude, &sample_blind_extrude(sketch));
        (sketch_feature, extrude_feature)
    }

    #[test]
    fn a_direction_vector_axis_edge_tracks_the_sweep_alignment() {
        use bone_kernel::{RevolveAxis, SweepAlignment, SweepFeature, SweepPath};
        use bone_types::{EdgeLabel, EdgeRole, SketchEntityId, SweepId};

        let mut tree = FeatureTree::seeded();
        let (_axis_sketch, axis_body) =
            sketch_extrude_pair(&mut tree, sketch_key(1), extrude_key(1));
        let profile = tree.push_sketch(sketch_key(2));
        let path = tree.push_sketch(sketch_key(3));

        let base = SweepFeature::boss(sketch_key(2), SweepPath::Sketch(sketch_key(3)));
        let aligned = SweepFeature {
            alignment: SweepAlignment::DirectionVector {
                axis: RevolveAxis::Edge(EdgeLabel {
                    feature: axis_body,
                    role: EdgeRole::StartCapEdge {
                        from: SketchEntityId::default(),
                    },
                }),
            },
            ..base.clone()
        };
        let sweep = tree.push_sweep(SweepId::default(), &aligned);
        let parents = tree.parents(sweep);
        assert!(
            parents.contains(&axis_body),
            "the alignment axis body must be an upstream dependency of the sweep"
        );
        assert!(parents.contains(&profile), "the profile stays a dependency");
        assert!(parents.contains(&path), "the path stays a dependency");

        tree.push_sweep(SweepId::default(), &base);
        let parents = tree.parents(sweep);
        assert!(
            !parents.contains(&axis_body),
            "clearing the direction axis must drop the stale dependency edge"
        );
        assert!(
            parents.contains(&profile) && parents.contains(&path),
            "the profile and path survive the re-push"
        );
    }

    #[derive(Clone, Debug)]
    enum Op {
        Add,
        Remove(usize),
    }

    fn op_strategy() -> impl Strategy<Value = Op> {
        prop_oneof![
            2 => Just(Op::Add),
            1 => (0usize..1024).prop_map(Op::Remove),
        ]
    }

    proptest! {
        #[test]
        fn feature_ids_never_reused(ops in proptest::collection::vec(op_strategy(), 0..64)) {
            let tree = FeatureTree::seeded();
            let seeds: Vec<FeatureId> = tree.iter().map(|(id, _)| id).collect();
            let (_, _, _, handed_out) = ops.into_iter().fold(
                (tree, Vec::<SketchId>::new(), 0u64, seeds),
                |(mut tree, mut live, counter, mut handed_out), op| match op {
                    Op::Add => {
                        let sketch = sketch_key(counter + 1);
                        handed_out.push(tree.push_sketch(sketch));
                        live.push(sketch);
                        (tree, live, counter + 1, handed_out)
                    }
                    Op::Remove(index) => {
                        if !live.is_empty() {
                            let removed = live.remove(index % live.len());
                            tree.remove_sketch(removed);
                        }
                        (tree, live, counter, handed_out)
                    }
                },
            );
            let unique: BTreeSet<FeatureId> = handed_out.iter().copied().collect();
            prop_assert_eq!(
                unique.len(),
                handed_out.len(),
                "a feature id held by a reference or snapshot was reused after a delete"
            );
        }
    }
}
