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

use bone_kernel::ExtrudeFeature;
use bone_types::{BodyId, ExtrudeId, FeatureGeneration, FeatureId, RollbackMarker, SketchId};
use serde::{Deserialize, Serialize};

use super::{gen_key, key_from_index, max_gen};

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

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum FeatureNode {
    Origin,
    PrincipalPlane(PrincipalPlane),
    Sketch(SketchId),
    Extrude(ExtrudeId),
    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,
    },
}

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),
        }
    }
}

#[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))
    }

    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)
    }

    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_datum(moved) || self.is_datum(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)>,
        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(
            face_bindings.map(|(face_feature, sketch)| FeatureEdge::FaceToSketch {
                face_feature,
                sketch,
            }),
        );
        rebuilt.sort_unstable();
        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 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_datum(&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> {
        let adjacency = self.adjacency(Direction::Forward);
        let (_, postorder) = self
            .entries
            .iter()
            .fold((BTreeSet::new(), Vec::new()), |(visited, order), entry| {
                visit_post(entry.id, &adjacency, visited, order)
            });
        postorder.into_iter().rev().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 visit_post(
    node: FeatureId,
    adjacency: &BTreeMap<FeatureId, BTreeSet<FeatureId>>,
    visited: BTreeSet<FeatureId>,
    order: Vec<FeatureId>,
) -> (BTreeSet<FeatureId>, Vec<FeatureId>) {
    if visited.contains(&node) {
        return (visited, order);
    }
    let (visited, mut order) = adjacency.get(&node).into_iter().flatten().fold(
        (insert(visited, node), order),
        |(visited, order), &child| visit_post(child, adjacency, visited, order),
    );
    order.push(node);
    (visited, order)
}

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_kernel::{ExtrudeDirection, ExtrudeEndCondition, ExtrudeSense, MergeResult};
    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 {
        sketch,
        direction: ExtrudeDirection::Normal {
            sense: ExtrudeSense::Forward,
        },
        end_condition: ExtrudeEndCondition::Blind { depth },
        draft: None,
        thin_wall: None,
        merge_result: MergeResult::Merge,
    }
}

#[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};

    #[test]
    fn push_extrude_adds_node_and_links_sketch() {
        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,
            }]
        );
    }

    #[test]
    fn push_extrude_is_idempotent_on_duplicate_id() {
        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);
    }

    #[test]
    fn push_extrude_without_sketch_node_records_no_edge() {
        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());
    }

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

    #[test]
    fn push_extrude_retargets_edge_to_new_sketch() {
        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,
            }]
        );
    }

    #[test]
    fn push_extrude_preserves_face_bound_child_edge() {
        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"
        );
    }

    #[test]
    fn remove_extrude_drops_node_and_edge() {
        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());
    }

    #[test]
    fn edges_are_derived_not_persisted() {
        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 Ok(ron) = crate::io::ron_io::to_string(&tree) else {
            panic!("feature tree serializes");
        };
        assert!(!ron.contains("edges"));
        let Ok(back) = crate::io::ron_io::from_str::<FeatureTree>(&ron) else {
            panic!("feature tree deserializes");
        };
        assert!(back.edges().is_empty());
    }

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

    #[test]
    fn edges_canonical_regardless_of_push_order() {
        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(),
        );

        assert_eq!(
            pushed.edges(),
            rebuilt.edges(),
            "live edge order must match the load rebuild irrespective of push order"
        );
        assert_eq!(pushed.edges().len(), 2);
    }

    #[test]
    fn allocate_does_not_reuse_removed_top_id() {
        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"
        );
    }

    #[test]
    fn endpoints_orient_parent_before_child() {
        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)
        );
    }

    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 children_and_parents_read_the_edges() {
        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());
    }

    #[test]
    fn descendants_and_ancestors_follow_the_chain() {
        let mut tree = FeatureTree::seeded();
        let (sketch_feature, extrude_feature) =
            sketch_extrude_pair(&mut tree, sketch_key(1), extrude_key(1));
        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());
    }

    #[test]
    fn topo_order_lists_every_node_parents_first() {
        let mut tree = FeatureTree::seeded();
        let (sketch_feature, extrude_feature) =
            sketch_extrude_pair(&mut tree, sketch_key(1), extrude_key(1));
        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"
        );
    }

    #[test]
    fn order_violation_flags_a_child_before_its_parent() {
        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!(
            tree.order_violation().is_none(),
            "a freshly built sketch-then-extrude chain is in dependency order",
        );

        let Some(sketch_feature) = tree.feature_of_sketch(sketch) else {
            panic!("the sketch resolves to a feature node");
        };
        let Some(extrude_feature) = tree.feature_of_extrude(extrude) else {
            panic!("the extrude resolves to a feature node");
        };
        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",
        );
    }

    #[test]
    fn binding_a_face_reorders_the_sketch_subtree_after_its_target() {
        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",
        );
    }

    #[test]
    fn find_cycle_flags_a_back_edge() {
        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"
        );
    }

    #[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"
            );
        }
    }
}
