Skip to main content

ferrichess_study/tree/
merge.rs

1use std::{collections::HashMap, error::Error, fmt};
2
3use shakmaty::{Chess, Move, Position};
4
5use crate::domain::{PositionKey, RepertoireSide, SourceId};
6
7use super::{MoveTree, NodeId, TreeError};
8
9/// One repertoire-side move rejected while merging a source tree.
10#[derive(Clone, Debug, Eq, PartialEq)]
11pub struct MergeConflict {
12    pub position: PositionKey,
13    pub selected_move: Move,
14    pub selected_source: SourceId,
15    pub rejected_move: Move,
16    pub rejected_source: SourceId,
17}
18
19/// Observable results from merging one source tree.
20#[derive(Clone, Debug, Default, Eq, PartialEq)]
21pub struct MergeReport {
22    pub added_nodes: usize,
23    pub merged_nodes: usize,
24    pub conflicts: Vec<MergeConflict>,
25}
26
27#[derive(Clone, Debug, Eq, PartialEq)]
28struct SelectedMove {
29    chess_move: Move,
30    source: SourceId,
31}
32
33/// Stateful, deterministic policy for merging raw lines into one repertoire tree.
34///
35/// A session remembers which source first selected the repertoire move at each
36/// position. Opponent alternatives remain ordered branches. A later source's
37/// main variation is promoted when it is accepted, matching the current Python
38/// ordering behavior.
39#[derive(Clone, Debug)]
40pub struct MoveTreeMerger {
41    repertoire_side: RepertoireSide,
42    selected_moves: HashMap<PositionKey, SelectedMove>,
43    has_merged_source: bool,
44}
45
46impl MoveTreeMerger {
47    #[must_use]
48    pub fn new(repertoire_side: RepertoireSide) -> Self {
49        Self {
50            repertoire_side,
51            selected_moves: HashMap::new(),
52            has_merged_source: false,
53        }
54    }
55
56    /// Merges a source tree into `target`, returning all policy conflicts.
57    ///
58    /// The first call requires an empty target so every selected move has known
59    /// provenance. Subsequent calls must use the same target and session.
60    pub fn merge(
61        &mut self,
62        target: &mut MoveTree,
63        source: &MoveTree,
64        source_id: impl Into<SourceId>,
65    ) -> Result<MergeReport, MergeError> {
66        if PositionKey::from_position(target.starting_position())
67            != PositionKey::from_position(source.starting_position())
68        {
69            return Err(MergeError::StartingPositionMismatch);
70        }
71        if !self.has_merged_source && target.len() != 1 {
72            return Err(MergeError::TargetHasUntrackedMoves);
73        }
74
75        let source_id = source_id.into();
76        let mut report = MergeReport::default();
77        self.merge_node(
78            target,
79            target.root(),
80            source,
81            source.root(),
82            target.starting_position().clone(),
83            &source_id,
84            &mut report,
85        )?;
86        target.validate()?;
87        self.has_merged_source = true;
88        Ok(report)
89    }
90
91    #[allow(clippy::too_many_arguments)]
92    fn merge_node(
93        &mut self,
94        target: &mut MoveTree,
95        target_parent: NodeId,
96        source: &MoveTree,
97        source_parent: NodeId,
98        position: Chess,
99        source_id: &SourceId,
100        report: &mut MergeReport,
101    ) -> Result<(), MergeError> {
102        let source_children = source
103            .node(source_parent)
104            .ok_or(TreeError::UnknownNode(source_parent))?
105            .children()
106            .to_vec();
107
108        for (index, source_child) in source_children.into_iter().enumerate() {
109            let chess_move = source
110                .node(source_child)
111                .ok_or(TreeError::UnknownNode(source_child))?
112                .chess_move()
113                .ok_or(TreeError::MissingMove(source_child))?;
114            if !position.is_legal(chess_move) {
115                return Err(MergeError::IllegalMove {
116                    source: source_id.clone(),
117                    node: source_child,
118                });
119            }
120
121            if self.repertoire_side.is_repertoire_turn(position.turn()) {
122                let key = PositionKey::from_position(&position);
123                if let Some(selected) = self.selected_moves.get(&key) {
124                    if selected.chess_move != chess_move {
125                        report.conflicts.push(MergeConflict {
126                            position: key,
127                            selected_move: selected.chess_move,
128                            selected_source: selected.source.clone(),
129                            rejected_move: chess_move,
130                            rejected_source: source_id.clone(),
131                        });
132                        continue;
133                    }
134                } else {
135                    self.selected_moves.insert(
136                        key,
137                        SelectedMove {
138                            chess_move,
139                            source: source_id.clone(),
140                        },
141                    );
142                }
143            }
144
145            let existing = find_child(target, target_parent, chess_move);
146            let target_child = if let Some(child) = existing {
147                report.merged_nodes += 1;
148                child
149            } else {
150                report.added_nodes += 1;
151                target.add_child(target_parent, chess_move)?
152            };
153            merge_node_content(target, target_child, source, source_child)?;
154            if index == 0 {
155                target.promote_child(target_parent, target_child)?;
156            }
157
158            let mut child_position = position.clone();
159            child_position.play_unchecked(chess_move);
160            self.merge_node(
161                target,
162                target_child,
163                source,
164                source_child,
165                child_position,
166                source_id,
167                report,
168            )?;
169        }
170        Ok(())
171    }
172}
173
174fn find_child(tree: &MoveTree, parent: NodeId, chess_move: Move) -> Option<NodeId> {
175    tree.node(parent)?
176        .children()
177        .iter()
178        .copied()
179        .find(|&child| tree.node(child).and_then(super::Node::chess_move) == Some(chess_move))
180}
181
182fn merge_node_content(
183    target: &mut MoveTree,
184    target_node: NodeId,
185    source: &MoveTree,
186    source_node: NodeId,
187) -> Result<(), TreeError> {
188    let source_node = source
189        .node(source_node)
190        .ok_or(TreeError::UnknownNode(source_node))?;
191    let source_comment = rendered_comment(source_node);
192    let target_comment = target
193        .node(target_node)
194        .ok_or(TreeError::UnknownNode(target_node))
195        .map(rendered_comment)?;
196    let complete_comment_already_present =
197        !source_comment.is_empty() && source_comment == target_comment;
198    let target_node = target
199        .node_mut(target_node)
200        .ok_or(TreeError::UnknownNode(target_node))?;
201    if !complete_comment_already_present {
202        for comment in source_node.comments() {
203            target_node.add_comment(comment.clone());
204        }
205    }
206    for &annotation in source_node.annotations() {
207        target_node.add_annotation(annotation);
208    }
209    Ok(())
210}
211
212fn rendered_comment(node: &super::Node) -> String {
213    node.comments()
214        .iter()
215        .map(super::CommentFragment::as_str)
216        .collect::<Vec<_>>()
217        .join(" ")
218}
219
220#[derive(Clone, Debug, Eq, PartialEq)]
221pub enum MergeError {
222    StartingPositionMismatch,
223    TargetHasUntrackedMoves,
224    IllegalMove { source: SourceId, node: NodeId },
225    Tree(TreeError),
226}
227
228impl fmt::Display for MergeError {
229    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
230        match self {
231            Self::StartingPositionMismatch => {
232                formatter.write_str("source and target starting positions differ")
233            }
234            Self::TargetHasUntrackedMoves => formatter.write_str(
235                "the first merge target contains moves whose source provenance is unknown",
236            ),
237            Self::IllegalMove { source, node } => write!(
238                formatter,
239                "source {} contains an illegal move at node {}",
240                source.as_path().display(),
241                node.index()
242            ),
243            Self::Tree(error) => error.fmt(formatter),
244        }
245    }
246}
247
248impl Error for MergeError {
249    fn source(&self) -> Option<&(dyn Error + 'static)> {
250        match self {
251            Self::Tree(error) => Some(error),
252            _ => None,
253        }
254    }
255}
256
257impl From<TreeError> for MergeError {
258    fn from(error: TreeError) -> Self {
259        Self::Tree(error)
260    }
261}
262
263#[cfg(test)]
264mod tests {
265    use shakmaty::{Chess, Position, san::SanPlus};
266
267    use crate::{
268        domain::{Annotation, RepertoireSide},
269        tree::{MoveTree, RawTreeBuilder},
270    };
271
272    use super::{MergeError, MoveTreeMerger};
273
274    fn build(side: RepertoireSide, text: &str) -> MoveTree {
275        RawTreeBuilder::new(side).build(text).unwrap().tree
276    }
277
278    fn child_sans(tree: &MoveTree, node: crate::tree::NodeId, position: &Chess) -> Vec<String> {
279        tree.node(node)
280            .unwrap()
281            .children()
282            .iter()
283            .map(|&child| {
284                SanPlus::from_move(
285                    position.clone(),
286                    tree.node(child).unwrap().chess_move().unwrap(),
287                )
288                .to_string()
289            })
290            .collect()
291    }
292
293    fn node_after(tree: &MoveTree, sans: &[&str]) -> (crate::tree::NodeId, Chess) {
294        let mut node = tree.root();
295        let mut position = Chess::default();
296        for expected in sans {
297            let child = tree
298                .node(node)
299                .unwrap()
300                .children()
301                .iter()
302                .copied()
303                .find(|&child| {
304                    SanPlus::from_move(
305                        position.clone(),
306                        tree.node(child).unwrap().chess_move().unwrap(),
307                    )
308                    .to_string()
309                        == *expected
310                })
311                .unwrap();
312            position.play_unchecked(tree.node(child).unwrap().chess_move().unwrap());
313            node = child;
314        }
315        (node, position)
316    }
317
318    #[test]
319    fn merges_opponent_branches_and_promotes_the_later_mainline() {
320        let first = build(RepertoireSide::White, "1. e4c52. Nf3");
321        let second = build(RepertoireSide::White, "1. e4e52. Nf3");
322        let mut target = MoveTree::new();
323        let mut merger = MoveTreeMerger::new(RepertoireSide::White);
324
325        merger.merge(&mut target, &first, "001.raw").unwrap();
326        merger.merge(&mut target, &second, "002.raw").unwrap();
327
328        let (e4, position) = node_after(&target, &["e4"]);
329        assert_eq!(child_sans(&target, e4, &position), ["e5", "c5"]);
330    }
331
332    #[test]
333    fn reports_and_rejects_a_conflicting_repertoire_move() {
334        let first = build(RepertoireSide::Black, "1. e4e52. Nf3Nc6");
335        let second = build(RepertoireSide::Black, "1. e4c52. Nf3d6");
336        let mut target = MoveTree::new();
337        let mut merger = MoveTreeMerger::new(RepertoireSide::Black);
338
339        merger.merge(&mut target, &first, "001.raw").unwrap();
340        let report = merger.merge(&mut target, &second, "002.raw").unwrap();
341
342        assert_eq!(report.conflicts.len(), 1);
343        let conflict = &report.conflicts[0];
344        assert_eq!(conflict.selected_source.as_path().to_str(), Some("001.raw"));
345        assert_eq!(conflict.rejected_source.as_path().to_str(), Some("002.raw"));
346        let (e4, position) = node_after(&target, &["e4"]);
347        assert_eq!(child_sans(&target, e4, &position), ["e5"]);
348    }
349
350    #[test]
351    fn merges_comments_and_annotations_on_shared_nodes() {
352        let first = build(RepertoireSide::White, "1. e4!e5\nshared\n2. Nf3");
353        let second = build(RepertoireSide::White, "1. e4?!e5\nshared\nextra\n2. Nf3");
354        let mut target = MoveTree::new();
355        let mut merger = MoveTreeMerger::new(RepertoireSide::White);
356
357        merger.merge(&mut target, &first, "001.raw").unwrap();
358        merger.merge(&mut target, &second, "002.raw").unwrap();
359
360        let (e4, _) = node_after(&target, &["e4"]);
361        assert_eq!(
362            target.node(e4).unwrap().annotations(),
363            &[Annotation::Good, Annotation::Dubious]
364                .into_iter()
365                .collect()
366        );
367        let (e5, _) = node_after(&target, &["e4", "e5"]);
368        let comments: Vec<_> = target
369            .node(e5)
370            .unwrap()
371            .comments()
372            .iter()
373            .map(|comment| comment.as_str())
374            .collect();
375        assert_eq!(comments, ["shared", "extra"]);
376    }
377
378    #[test]
379    fn deduplicates_the_same_comment_with_different_fragment_boundaries() {
380        let first = build(
381            RepertoireSide::White,
382            "1. e4e5\nAlpha. Beta.\nGamma.\n2. Nf3",
383        );
384        let second = build(
385            RepertoireSide::White,
386            "1. e4e5\nAlpha.\nBeta. Gamma.\n2. Bc4",
387        );
388        let mut target = MoveTree::new();
389        let mut merger = MoveTreeMerger::new(RepertoireSide::White);
390
391        merger.merge(&mut target, &first, "001.raw").unwrap();
392        merger.merge(&mut target, &second, "002.raw").unwrap();
393
394        let (e5, _) = node_after(&target, &["e4", "e5"]);
395        let comments: Vec<_> = target
396            .node(e5)
397            .unwrap()
398            .comments()
399            .iter()
400            .map(|comment| comment.as_str())
401            .collect();
402        assert_eq!(comments, ["Alpha. Beta.", "Gamma."]);
403    }
404
405    #[test]
406    fn rejects_an_initial_target_with_unknown_provenance() {
407        let source = build(RepertoireSide::White, "1. e4");
408        let mut target = build(RepertoireSide::White, "1. d4");
409        let mut merger = MoveTreeMerger::new(RepertoireSide::White);
410
411        assert_eq!(
412            merger.merge(&mut target, &source, "001.raw"),
413            Err(MergeError::TargetHasUntrackedMoves)
414        );
415    }
416}