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