Skip to main content

ferrichess_study/tree/
model.rs

1use std::{collections::BTreeSet, error::Error, fmt};
2
3use shakmaty::{Chess, Move};
4
5use crate::domain::Annotation;
6
7/// A stable identifier into a [`MoveTree`] arena.
8#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
9pub struct NodeId(usize);
10
11impl NodeId {
12    #[must_use]
13    pub const fn index(self) -> usize {
14        self.0
15    }
16}
17
18/// One independently deduplicable piece of comment text.
19#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
20pub struct CommentFragment(String);
21
22impl CommentFragment {
23    pub fn new(text: impl Into<String>) -> Self {
24        Self(text.into())
25    }
26
27    #[must_use]
28    pub fn as_str(&self) -> &str {
29        &self.0
30    }
31
32    pub fn into_string(self) -> String {
33        self.0
34    }
35}
36
37impl<T: Into<String>> From<T> for CommentFragment {
38    fn from(text: T) -> Self {
39        Self::new(text)
40    }
41}
42
43/// A node in the move-tree arena.
44#[derive(Clone, Debug, Eq, PartialEq)]
45pub struct Node {
46    parent: Option<NodeId>,
47    chess_move: Option<Move>,
48    children: Vec<NodeId>,
49    comments: Vec<CommentFragment>,
50    annotations: BTreeSet<Annotation>,
51}
52
53impl Node {
54    fn root() -> Self {
55        Self {
56            parent: None,
57            chess_move: None,
58            children: Vec::new(),
59            comments: Vec::new(),
60            annotations: BTreeSet::new(),
61        }
62    }
63
64    fn child(parent: NodeId, chess_move: Move) -> Self {
65        Self {
66            parent: Some(parent),
67            chess_move: Some(chess_move),
68            children: Vec::new(),
69            comments: Vec::new(),
70            annotations: BTreeSet::new(),
71        }
72    }
73
74    #[must_use]
75    pub const fn parent(&self) -> Option<NodeId> {
76        self.parent
77    }
78
79    #[must_use]
80    pub const fn chess_move(&self) -> Option<Move> {
81        self.chess_move
82    }
83
84    #[must_use]
85    pub fn children(&self) -> &[NodeId] {
86        &self.children
87    }
88
89    #[must_use]
90    pub fn comments(&self) -> &[CommentFragment] {
91        &self.comments
92    }
93
94    #[must_use]
95    pub const fn annotations(&self) -> &BTreeSet<Annotation> {
96        &self.annotations
97    }
98
99    pub fn add_comment(&mut self, comment: impl Into<CommentFragment>) -> bool {
100        let comment = comment.into();
101        if self.comments.contains(&comment) {
102            false
103        } else {
104            self.comments.push(comment);
105            true
106        }
107    }
108
109    pub fn add_annotation(&mut self, annotation: Annotation) -> bool {
110        self.annotations.insert(annotation)
111    }
112}
113
114/// An owned, ordered arena of chess moves rooted at an explicit position.
115#[derive(Clone, Debug, Eq, PartialEq)]
116pub struct MoveTree {
117    starting_position: Chess,
118    nodes: Vec<Node>,
119    root: NodeId,
120}
121
122impl Default for MoveTree {
123    fn default() -> Self {
124        Self::new()
125    }
126}
127
128impl MoveTree {
129    #[must_use]
130    pub fn new() -> Self {
131        Self::from_position(Chess::default())
132    }
133
134    #[must_use]
135    pub fn from_position(starting_position: Chess) -> Self {
136        Self {
137            starting_position,
138            nodes: vec![Node::root()],
139            root: NodeId(0),
140        }
141    }
142
143    #[must_use]
144    pub const fn starting_position(&self) -> &Chess {
145        &self.starting_position
146    }
147
148    #[must_use]
149    pub const fn root(&self) -> NodeId {
150        self.root
151    }
152
153    #[must_use]
154    pub const fn len(&self) -> usize {
155        self.nodes.len()
156    }
157
158    #[must_use]
159    pub const fn is_empty(&self) -> bool {
160        false
161    }
162
163    #[must_use]
164    pub fn node(&self, id: NodeId) -> Option<&Node> {
165        self.nodes.get(id.0)
166    }
167
168    pub fn node_mut(&mut self, id: NodeId) -> Option<&mut Node> {
169        self.nodes.get_mut(id.0)
170    }
171
172    pub fn add_child(&mut self, parent: NodeId, chess_move: Move) -> Result<NodeId, TreeError> {
173        if self.node(parent).is_none() {
174            return Err(TreeError::UnknownNode(parent));
175        }
176
177        let child = NodeId(self.nodes.len());
178        self.nodes.push(Node::child(parent, chess_move));
179        self.nodes[parent.0].children.push(child);
180        Ok(child)
181    }
182
183    /// Moves an existing direct child to the main-variation position.
184    pub fn promote_child(&mut self, parent: NodeId, child: NodeId) -> Result<(), TreeError> {
185        let node = self
186            .nodes
187            .get_mut(parent.0)
188            .ok_or(TreeError::UnknownNode(parent))?;
189        let index = node
190            .children
191            .iter()
192            .position(|candidate| *candidate == child)
193            .ok_or(TreeError::NotAChild { parent, child })?;
194        node.children[..=index].rotate_right(1);
195        Ok(())
196    }
197
198    /// Returns node identifiers in deterministic depth-first pre-order.
199    pub fn traverse(&self) -> impl Iterator<Item = NodeId> + '_ {
200        let mut stack = vec![self.root];
201        std::iter::from_fn(move || {
202            let id = stack.pop()?;
203            stack.extend(self.nodes[id.0].children.iter().rev().copied());
204            Some(id)
205        })
206    }
207
208    /// Checks all arena ownership, reachability, and parent/child invariants.
209    pub fn validate(&self) -> Result<(), TreeError> {
210        let root = self
211            .nodes
212            .get(self.root.0)
213            .ok_or(TreeError::UnknownNode(self.root))?;
214        if root.parent.is_some() || root.chess_move.is_some() {
215            return Err(TreeError::InvalidRoot);
216        }
217
218        let mut seen = vec![false; self.nodes.len()];
219        let mut stack = vec![self.root];
220        while let Some(parent) = stack.pop() {
221            if seen[parent.0] {
222                return Err(TreeError::DuplicateOrCyclicNode(parent));
223            }
224            seen[parent.0] = true;
225
226            for &child in &self.nodes[parent.0].children {
227                let child_node = self
228                    .nodes
229                    .get(child.0)
230                    .ok_or(TreeError::UnknownNode(child))?;
231                if child_node.parent != Some(parent) {
232                    return Err(TreeError::ParentMismatch {
233                        child,
234                        expected: parent,
235                        actual: child_node.parent,
236                    });
237                }
238                if child_node.chess_move.is_none() {
239                    return Err(TreeError::MissingMove(child));
240                }
241                stack.push(child);
242            }
243        }
244
245        if let Some(index) = seen.iter().position(|visited| !visited) {
246            return Err(TreeError::UnreachableNode(NodeId(index)));
247        }
248        Ok(())
249    }
250}
251
252#[derive(Clone, Debug, Eq, PartialEq)]
253pub enum TreeError {
254    UnknownNode(NodeId),
255    NotAChild {
256        parent: NodeId,
257        child: NodeId,
258    },
259    InvalidRoot,
260    DuplicateOrCyclicNode(NodeId),
261    ParentMismatch {
262        child: NodeId,
263        expected: NodeId,
264        actual: Option<NodeId>,
265    },
266    MissingMove(NodeId),
267    UnreachableNode(NodeId),
268    PlyCommentOutOfBounds {
269        line_number: usize,
270        ply: u32,
271        available_plies: u32,
272    },
273}
274
275impl fmt::Display for TreeError {
276    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
277        match self {
278            Self::UnknownNode(node) => write!(formatter, "unknown node {}", node.index()),
279            Self::NotAChild { parent, child } => write!(
280                formatter,
281                "node {} is not a child of node {}",
282                child.index(),
283                parent.index()
284            ),
285            Self::InvalidRoot => formatter.write_str("root node has a parent or move"),
286            Self::DuplicateOrCyclicNode(node) => write!(
287                formatter,
288                "node {} is referenced more than once or forms a cycle",
289                node.index()
290            ),
291            Self::ParentMismatch {
292                child,
293                expected,
294                actual,
295            } => write!(
296                formatter,
297                "node {} has parent {actual:?}, expected node {}",
298                child.index(),
299                expected.index()
300            ),
301            Self::MissingMove(node) => {
302                write!(formatter, "non-root node {} has no move", node.index())
303            }
304            Self::UnreachableNode(node) => {
305                write!(formatter, "node {} is unreachable", node.index())
306            }
307            Self::PlyCommentOutOfBounds {
308                line_number,
309                ply,
310                available_plies,
311            } => write!(
312                formatter,
313                "line {line_number} targets ply {ply}, but the mainline has {available_plies} plies"
314            ),
315        }
316    }
317}
318
319impl Error for TreeError {}
320
321#[cfg(test)]
322mod tests {
323    use shakmaty::{Chess, Move, Position, Role, Square};
324
325    use crate::domain::Annotation;
326
327    use super::{CommentFragment, MoveTree, NodeId, TreeError};
328
329    fn normal(from: Square, to: Square, role: Role) -> Move {
330        Move::Normal {
331            role,
332            from,
333            capture: None,
334            to,
335            promotion: None,
336        }
337    }
338
339    #[test]
340    fn tree_retains_its_explicit_starting_position() {
341        let after_e4 = Chess::default()
342            .play(normal(Square::E2, Square::E4, Role::Pawn))
343            .unwrap();
344        let tree = MoveTree::from_position(after_e4.clone());
345
346        assert_eq!(tree.starting_position(), &after_e4);
347    }
348
349    #[test]
350    fn insertion_and_traversal_are_deterministic() {
351        let mut tree = MoveTree::new();
352        let root = tree.root();
353        let e4 = tree
354            .add_child(root, normal(Square::E2, Square::E4, Role::Pawn))
355            .unwrap();
356        let d4 = tree
357            .add_child(root, normal(Square::D2, Square::D4, Role::Pawn))
358            .unwrap();
359        let e5 = tree
360            .add_child(e4, normal(Square::E7, Square::E5, Role::Pawn))
361            .unwrap();
362
363        assert_eq!(tree.traverse().collect::<Vec<_>>(), [root, e4, e5, d4]);
364        assert_eq!(tree.node(e5).unwrap().parent(), Some(e4));
365        assert_eq!(tree.validate(), Ok(()));
366    }
367
368    #[test]
369    fn promotion_changes_only_explicit_child_order() {
370        let mut tree = MoveTree::new();
371        let root = tree.root();
372        let e4 = tree
373            .add_child(root, normal(Square::E2, Square::E4, Role::Pawn))
374            .unwrap();
375        let d4 = tree
376            .add_child(root, normal(Square::D2, Square::D4, Role::Pawn))
377            .unwrap();
378
379        tree.promote_child(root, d4).unwrap();
380        assert_eq!(tree.node(root).unwrap().children(), [d4, e4]);
381        assert_eq!(tree.validate(), Ok(()));
382    }
383
384    #[test]
385    fn promotion_rejects_non_children() {
386        let mut tree = MoveTree::new();
387        let root = tree.root();
388        let e4 = tree
389            .add_child(root, normal(Square::E2, Square::E4, Role::Pawn))
390            .unwrap();
391        let e5 = tree
392            .add_child(e4, normal(Square::E7, Square::E5, Role::Pawn))
393            .unwrap();
394
395        assert_eq!(
396            tree.promote_child(root, e5),
397            Err(TreeError::NotAChild {
398                parent: root,
399                child: e5
400            })
401        );
402    }
403
404    #[test]
405    fn comments_deduplicate_without_losing_order() {
406        let mut tree = MoveTree::new();
407        let root = tree.root();
408        let node = tree.node_mut(root).unwrap();
409
410        assert!(node.add_comment("first"));
411        assert!(node.add_comment("second"));
412        assert!(!node.add_comment("first"));
413        assert_eq!(
414            node.comments(),
415            [
416                CommentFragment::new("first"),
417                CommentFragment::new("second")
418            ]
419        );
420    }
421
422    #[test]
423    fn annotations_are_typed_and_sorted() {
424        let mut tree = MoveTree::new();
425        let node = tree.node_mut(tree.root()).unwrap();
426        node.add_annotation(Annotation::Dubious);
427        node.add_annotation(Annotation::Good);
428        node.add_annotation(Annotation::Good);
429
430        assert_eq!(
431            node.annotations().iter().copied().collect::<Vec<_>>(),
432            [Annotation::Good, Annotation::Dubious]
433        );
434    }
435
436    #[test]
437    fn unknown_parent_is_rejected_without_mutating_the_arena() {
438        let mut tree = MoveTree::new();
439        let result = tree.add_child(NodeId(99), normal(Square::E2, Square::E4, Role::Pawn));
440
441        assert_eq!(result, Err(TreeError::UnknownNode(NodeId(99))));
442        assert_eq!(tree.len(), 1);
443        assert_eq!(tree.validate(), Ok(()));
444    }
445
446    #[test]
447    fn validation_detects_a_broken_parent_link() {
448        let mut tree = MoveTree::new();
449        let root = tree.root();
450        let child = tree
451            .add_child(root, normal(Square::E2, Square::E4, Role::Pawn))
452            .unwrap();
453        tree.nodes[child.index()].parent = Some(child);
454
455        assert_eq!(
456            tree.validate(),
457            Err(TreeError::ParentMismatch {
458                child,
459                expected: root,
460                actual: Some(child),
461            })
462        );
463    }
464}