chess/game/
traversal.rs

1use core::{cmp::Ordering, fmt, iter::FusedIterator, ops::Deref, slice};
2
3use crate::position::Evaluation;
4
5use super::*;
6
7/// An error from traversing a game tree.
8#[derive(Debug, thiserror::Error)]
9pub enum Error {
10    #[error("position slot {0} not found")]
11    Position(PositionSlot),
12    #[error("move slot {0} not found")]
13    Move(MoveSlot),
14    #[error(transparent)]
15    Option(#[from] Missing),
16}
17
18/// A result of traversing a game tree.
19pub type Result<T, E = Error> = core::result::Result<T, E>;
20
21/// Chooses an option within a game position.
22pub trait Choose: Into<Choice> {
23    fn choose(self, position: PositionRef<'_>) -> Result<usize, Missing>;
24}
25
26/// Concrete instantiation of any Choose type.
27// This is a "mini-version" of the enum/trait bridge,
28// as exemplified in the `enum-trait` crate.
29#[derive(Clone, Copy, Eq, PartialEq)]
30#[non_exhaustive]
31pub enum Choice {
32    Index(usize),
33    Move(chess::Move),
34    Slot(MoveSlot),
35}
36
37/// A choice that does not identify an existing option in a position.
38#[derive(Debug, thiserror::Error)]
39#[error("option {choice:?} not found in position slot {position}")]
40pub struct Missing {
41    pub position: PositionSlot,
42    pub choice: Choice,
43}
44
45impl fmt::Debug for Choice {
46    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
47        match self {
48            Self::Index(index) => write!(f, "Index({index})"),
49            Self::Move(play) => write!(f, "Move({play})"),
50            Self::Slot(slot) => write!(f, "Slot({slot})"),
51        }
52    }
53}
54
55impl From<usize> for Choice {
56    fn from(index: usize) -> Self {
57        Self::Index(index)
58    }
59}
60
61impl From<MoveSlot> for Choice {
62    fn from(slot: MoveSlot) -> Self {
63        Self::Slot(slot)
64    }
65}
66
67impl From<chess::Move> for Choice {
68    fn from(play: chess::Move) -> Self {
69        Self::Move(play)
70    }
71}
72
73/// The partial order of a position within a game tree.
74#[derive(Clone, Copy)]
75pub struct Order<'g> {
76    game: &'g Game,
77    pub slot: PositionSlot,
78}
79
80/// Iterator over the moves from a position.
81#[derive(Clone)]
82pub struct Moves<'g> {
83    game: &'g Game,
84    slots: slice::Iter<'g, MoveSlot>,
85}
86
87/// Lending iterator over the options from a position in index order.
88///
89/// Options removed before being reached are skipped.
90pub struct MovesMut<'g> {
91    game: &'g mut Game,
92    position: PositionSlot,
93    index: usize,
94    visited: Set<MoveSlot>,
95    protected: Protected,
96}
97
98impl Game {
99    pub fn play(&self, slot: MoveSlot) -> Result<MoveRef<'_>> {
100        self.tree
101            .contains(slot.into())
102            .then_some(MoveRef { game: self, slot })
103            .ok_or(Error::Move(slot))
104    }
105
106    pub fn play_mut(&mut self, slot: MoveSlot) -> Result<MoveMut<'_>> {
107        if !self.tree.contains(slot.into()) {
108            return Err(Error::Move(slot));
109        }
110        Ok(MoveMut::new(self, slot))
111    }
112
113    pub fn position(&self, slot: PositionSlot) -> Result<PositionRef<'_>> {
114        self.tree
115            .contains(slot)
116            .then_some(PositionRef { game: self, slot })
117            .ok_or(Error::Position(slot))
118    }
119
120    pub fn position_mut(&mut self, slot: PositionSlot) -> Result<PositionMut<'_>> {
121        if !self.tree.contains(slot) {
122            return Err(Error::Position(slot));
123        }
124        Ok(PositionMut::new(self, slot))
125    }
126
127    pub const fn start(&self) -> PositionRef<'_> {
128        PositionRef { game: self, slot: START }
129    }
130
131    pub const fn start_mut(&mut self) -> PositionMut<'_> {
132        PositionMut::new(self, START)
133    }
134
135    pub const fn into_cursor(self) -> Cursor {
136        Cursor::new(self)
137    }
138
139    pub const fn cursor(&self) -> CursorRef<'_> {
140        Cursor { game: self, slot: START, preserve: Set::new() }
141    }
142
143    pub const fn cursor_mut(&mut self) -> CursorMut<'_> {
144        Cursor { game: self, slot: START, preserve: Set::new() }
145    }
146
147    pub const fn order(&self, slot: PositionSlot) -> Order<'_> {
148        Order { game: self, slot }
149    }
150}
151
152/// Access API.
153impl<'g> PositionRef<'g> {
154    pub const fn slot(&self) -> PositionSlot {
155        self.slot
156    }
157
158    pub const fn game(&self) -> &'g Game {
159        self.game
160    }
161
162    pub fn into_game(self) -> Game {
163        Game::unchecked_with_mode_next(
164            self.position().position(),
165            self.game.mode(),
166            self.game.tree.next(),
167        )
168    }
169
170    pub fn index(&self, option: impl Choose) -> Result<usize> {
171        Ok(option.choose(*self)?)
172    }
173
174    pub fn has_option(&self, option: impl Choose) -> bool {
175        self.index(option).is_ok()
176    }
177
178    pub(in crate::game) fn position(&self) -> &'g Position {
179        self.game.tree.position(self.slot)
180    }
181}
182
183/// Traversal API.
184impl<'g> PositionRef<'g> {
185    pub const fn cursor(self) -> CursorRef<'g> {
186        Cursor { game: self.game, slot: self.slot, preserve: Set::new() }
187    }
188
189    pub const fn play(&self) -> start::Result<MoveRef<'g>> {
190        match self.slot {
191            PositionSlot::Move(slot) => Ok(MoveRef { game: self.game, slot }),
192            PositionSlot::Start => Err(start::Error),
193        }
194    }
195
196    pub fn main(&self) -> Result<MoveRef<'g>> {
197        self.option(0)
198    }
199
200    pub fn option(&self, option: impl Choose) -> Result<MoveRef<'g>> {
201        let index = self.index(option)?;
202        let slot = self.position().options[index];
203        Ok(MoveRef { game: self.game, slot })
204    }
205
206    pub fn has_options(&self) -> bool {
207        !self.position().options.is_empty()
208    }
209
210    pub fn has_alternatives(&self) -> bool {
211        self.position().options.len() >= 2
212    }
213
214    pub fn alternatives(&self) -> Moves<'g> {
215        let slots = self.position().options.get(1..).unwrap_or_default().iter();
216        Moves { game: self.game, slots }
217    }
218
219    pub fn iter(&self) -> Moves<'g> {
220        Moves { game: self.game, slots: self.position().options.iter() }
221    }
222}
223
224impl Deref for PositionRef<'_> {
225    type Target = Position;
226
227    fn deref(&self) -> &Position {
228        self.position()
229    }
230}
231
232/// Access API.
233impl<'g> PositionMut<'g> {
234    const fn new(game: &'g mut Game, slot: PositionSlot) -> Self {
235        Self { game, slot, protected: Protected::new() }
236    }
237
238    pub const fn slot(&self) -> PositionSlot {
239        self.slot
240    }
241
242    pub const fn game(&self) -> &Game {
243        self.game
244    }
245
246    pub const fn as_ref(&self) -> PositionRef<'_> {
247        PositionRef { game: self.game, slot: self.slot }
248    }
249
250    pub fn into_ref(self) -> PositionRef<'g> {
251        PositionRef { game: self.game, slot: self.slot }
252    }
253
254    pub fn set_comment(&mut self, comment: Option<Text>) {
255        self.update_public(|public| public.comment = comment);
256    }
257
258    pub fn set_evaluation(&mut self, evaluation: Option<Evaluation>) {
259        self.position_mut().evaluation = evaluation;
260    }
261
262    pub fn set_expanded(&mut self, expanded: bool) {
263        self.update_public(|public| public.expanded = expanded);
264    }
265
266    pub fn update_public(&mut self, update: impl FnOnce(&mut PositionPublic)) {
267        let before = self.game.tracks_changes().then(|| self.public.clone());
268        update(&mut self.position_mut().public);
269        if let Some(before) = before
270            && before != self.public
271        {
272            self.game.track(change::Patch::Position { slot: self.slot, public: Box::new(before) });
273        }
274    }
275
276    pub(in crate::game) fn position(&self) -> &Position {
277        self.game.tree.position(self.slot)
278    }
279
280    pub(in crate::game) fn position_mut(&mut self) -> &mut Position {
281        self.game.tree.position_mut(self.slot)
282    }
283}
284
285/// Traversal API.
286impl<'g> PositionMut<'g> {
287    pub fn cursor_mut(&mut self) -> CursorMut<'_> {
288        let mut preserve = self.protected.unremovable.clone();
289        preserve.insert(self.slot);
290        Cursor { game: self.game, slot: self.slot, preserve }
291    }
292
293    pub fn into_cursor_mut(self) -> CursorMut<'g> {
294        Cursor { game: self.game, slot: self.slot, preserve: self.protected.unremovable }
295    }
296
297    pub const fn play(&self) -> start::Result<MoveRef<'_>> {
298        match self.slot {
299            PositionSlot::Move(slot) => Ok(MoveRef { game: self.game, slot }),
300            PositionSlot::Start => Err(start::Error),
301        }
302    }
303
304    pub fn play_mut(&mut self) -> start::Result<MoveMut<'_>> {
305        match self.slot {
306            PositionSlot::Move(slot) => {
307                Ok(MoveMut { game: self.game, slot, protected: self.protected.clone() })
308            }
309            PositionSlot::Start => Err(start::Error),
310        }
311    }
312
313    pub fn into_play(self) -> start::Result<MoveMut<'g>> {
314        match self.slot {
315            PositionSlot::Move(slot) => {
316                Ok(MoveMut { game: self.game, slot, protected: self.protected })
317            }
318            PositionSlot::Start => Err(start::Error),
319        }
320    }
321
322    pub fn main_mut(&mut self) -> Result<MoveMut<'_>> {
323        self.option_mut(0)
324    }
325
326    pub fn into_main(self) -> Result<MoveMut<'g>> {
327        self.into_option(0)
328    }
329
330    pub fn option_mut(&mut self, option: impl Choose) -> Result<MoveMut<'_>> {
331        let slot = self.as_ref().option(option)?.slot();
332        Ok(MoveMut { game: self.game, slot, protected: self.protected.clone() })
333    }
334
335    pub fn into_option(self, option: impl Choose) -> Result<MoveMut<'g>> {
336        let slot = self.as_ref().option(option)?.slot();
337        Ok(MoveMut { game: self.game, slot, protected: self.protected })
338    }
339
340    pub fn alternatives_mut(&mut self) -> MovesMut<'_> {
341        MovesMut {
342            game: self.game,
343            position: self.slot,
344            index: 1,
345            visited: Set::new(),
346            protected: self.protected.clone(),
347        }
348    }
349
350    pub fn into_alternatives(self) -> MovesMut<'g> {
351        MovesMut {
352            game: self.game,
353            position: self.slot,
354            index: 1,
355            visited: Set::new(),
356            protected: self.protected,
357        }
358    }
359
360    pub fn iter_mut(&mut self) -> MovesMut<'_> {
361        MovesMut {
362            game: self.game,
363            position: self.slot,
364            index: 0,
365            visited: Set::new(),
366            protected: self.protected.clone(),
367        }
368    }
369
370    pub fn into_iter_mut(self) -> MovesMut<'g> {
371        MovesMut {
372            game: self.game,
373            position: self.slot,
374            index: 0,
375            visited: Set::new(),
376            protected: self.protected,
377        }
378    }
379}
380
381impl Deref for PositionMut<'_> {
382    type Target = Position;
383
384    fn deref(&self) -> &Position {
385        self.position()
386    }
387}
388
389/// Access API.
390impl<'g> MoveRef<'g> {
391    pub const fn slot(&self) -> MoveSlot {
392        self.slot
393    }
394
395    pub const fn game(&self) -> &'g Game {
396        self.game
397    }
398
399    pub fn into_game(self) -> Game {
400        let mut game = self.previous().into_game();
401        game.start_mut()
402            .insert_at_untracked(Some(self.slot), 0, self.play().play)
403            .expect("move is legal in its previous position");
404        game
405    }
406
407    pub fn comment(&self) -> Option<&'g Text> {
408        self.game.tree.position(self.slot.into()).comment()
409    }
410
411    pub fn evaluation(&self) -> Option<&'g Evaluation> {
412        self.game.tree.position(self.slot.into()).evaluation()
413    }
414
415    pub fn expanded(&self) -> bool {
416        self.game.tree.position(self.slot.into()).expanded()
417    }
418
419    pub(in crate::game) fn play(&self) -> &Move {
420        self.game.tree.play(self.slot)
421    }
422}
423
424/// Traversal API.
425impl<'g> MoveRef<'g> {
426    pub fn previous(&self) -> PositionRef<'g> {
427        PositionRef { game: self.game, slot: self.play().previous }
428    }
429
430    pub const fn position(&self) -> PositionRef<'g> {
431        PositionRef { game: self.game, slot: PositionSlot::Move(self.slot) }
432    }
433}
434
435impl Deref for MoveRef<'_> {
436    type Target = Move;
437
438    fn deref(&self) -> &Move {
439        self.play()
440    }
441}
442
443/// Access API.
444impl<'g> MoveMut<'g> {
445    const fn new(game: &'g mut Game, slot: MoveSlot) -> Self {
446        Self { game, slot, protected: Protected::new() }
447    }
448
449    pub const fn slot(&self) -> MoveSlot {
450        self.slot
451    }
452
453    pub const fn game(&self) -> &Game {
454        self.game
455    }
456
457    pub const fn as_ref(&self) -> MoveRef<'_> {
458        MoveRef { game: self.game, slot: self.slot }
459    }
460
461    pub fn into_ref(self) -> MoveRef<'g> {
462        MoveRef { game: self.game, slot: self.slot }
463    }
464
465    pub fn set_intro(&mut self, intro: Option<Text>) {
466        self.update_public(|public| public.affixes.intro = intro);
467    }
468
469    pub fn set_outro(&mut self, outro: Option<Text>) {
470        self.update_public(|public| public.affixes.outro = outro);
471    }
472
473    pub fn update_commands(&mut self, update: impl FnOnce(&mut Vec<Command>)) {
474        self.update_public(|public| update(&mut public.commands));
475    }
476
477    pub fn update_nags(&mut self, update: impl FnOnce(&mut Vec<Nag>)) {
478        self.update_public(|public| update(&mut public.nags));
479    }
480
481    pub fn update_public(&mut self, update: impl FnOnce(&mut MovePublic)) {
482        let before = self.game.tracks_changes().then(|| self.public.clone());
483        update(&mut self.play_mut().public);
484        if let Some(before) = before
485            && before != self.public
486        {
487            self.game.track(change::Patch::Move { slot: self.slot, public: Box::new(before) });
488        }
489    }
490
491    pub fn comment(&self) -> Option<&Text> {
492        self.game.tree.position(self.slot.into()).comment()
493    }
494
495    pub fn evaluation(&self) -> Option<&Evaluation> {
496        self.as_ref().evaluation()
497    }
498
499    pub fn expanded(&self) -> bool {
500        self.as_ref().expanded()
501    }
502
503    pub fn set_comment(&mut self, comment: Option<Text>) {
504        self.position_mut().set_comment(comment);
505    }
506
507    pub fn set_evaluation(&mut self, evaluation: Option<Evaluation>) {
508        self.position_mut().set_evaluation(evaluation);
509    }
510
511    pub fn set_expanded(&mut self, expanded: bool) {
512        self.position_mut().set_expanded(expanded);
513    }
514
515    pub(in crate::game) fn play(&self) -> &Move {
516        self.game.tree.play(self.slot)
517    }
518
519    pub(in crate::game) fn play_mut(&mut self) -> &mut Move {
520        self.game.tree.play_mut(self.slot)
521    }
522}
523
524/// Traversal API.
525impl<'g> MoveMut<'g> {
526    pub fn previous(&self) -> PositionRef<'_> {
527        self.as_ref().previous()
528    }
529
530    pub fn previous_mut(&mut self) -> PositionMut<'_> {
531        let slot = self.play().previous;
532        let protected = self.protected.with_unremovable(self.slot.into());
533        PositionMut { game: self.game, slot, protected }
534    }
535
536    pub fn into_previous(self) -> PositionMut<'g> {
537        let slot = self.play().previous;
538        PositionMut { game: self.game, slot, protected: self.protected }
539    }
540
541    pub const fn position(&self) -> PositionRef<'_> {
542        PositionRef { game: self.game, slot: PositionSlot::Move(self.slot) }
543    }
544
545    pub fn position_mut(&mut self) -> PositionMut<'_> {
546        PositionMut {
547            game: self.game,
548            slot: PositionSlot::Move(self.slot),
549            protected: self.protected.clone(),
550        }
551    }
552
553    pub fn into_position(self) -> PositionMut<'g> {
554        PositionMut {
555            game: self.game,
556            slot: PositionSlot::Move(self.slot),
557            protected: self.protected,
558        }
559    }
560}
561
562impl Deref for MoveMut<'_> {
563    type Target = Move;
564
565    fn deref(&self) -> &Move {
566        self.play()
567    }
568}
569
570impl PartialEq<PositionSlot> for Order<'_> {
571    fn eq(&self, other: &PositionSlot) -> bool {
572        self.slot == *other
573    }
574}
575
576impl PartialOrd<PositionSlot> for Order<'_> {
577    fn partial_cmp(&self, other: &PositionSlot) -> Option<Ordering> {
578        if self.slot == *other {
579            return Some(Ordering::Equal);
580        }
581        if !self.game.tree.contains(self.slot) || !self.game.tree.contains(*other) {
582            return None;
583        }
584        if self.game.tree.less_equal(self.slot, *other) {
585            Some(Ordering::Less)
586        } else if self.game.tree.less_equal(*other, self.slot) {
587            Some(Ordering::Greater)
588        } else {
589            None
590        }
591    }
592}
593
594impl Choose for usize {
595    fn choose(self, position: PositionRef<'_>) -> Result<usize, Missing> {
596        (self < position.options().len())
597            .then_some(self)
598            .ok_or(Missing { position: position.slot(), choice: self.into() })
599    }
600}
601
602impl Choose for MoveSlot {
603    fn choose(self, position: PositionRef<'_>) -> Result<usize, Missing> {
604        position
605            .options()
606            .iter()
607            .position(|option| *option == self)
608            .ok_or(Missing { position: position.slot(), choice: self.into() })
609    }
610}
611
612impl Choose for chess::Move {
613    fn choose(self, position: PositionRef<'_>) -> Result<usize, Missing> {
614        position
615            .iter()
616            .position(|option| **option == self)
617            .ok_or(Missing { position: position.slot(), choice: self.into() })
618    }
619}
620
621impl<'g> IntoIterator for PositionRef<'g> {
622    type Item = MoveRef<'g>;
623    type IntoIter = Moves<'g>;
624
625    fn into_iter(self) -> Self::IntoIter {
626        self.iter()
627    }
628}
629
630impl<'g> Iterator for Moves<'g> {
631    type Item = MoveRef<'g>;
632
633    fn next(&mut self) -> Option<Self::Item> {
634        let slot = self.slots.next().copied()?;
635        Some(MoveRef { game: self.game, slot })
636    }
637
638    fn size_hint(&self) -> (usize, Option<usize>) {
639        self.slots.size_hint()
640    }
641}
642
643impl DoubleEndedIterator for Moves<'_> {
644    fn next_back(&mut self) -> Option<Self::Item> {
645        let slot = self.slots.next_back().copied()?;
646        Some(MoveRef { game: self.game, slot })
647    }
648}
649
650impl ExactSizeIterator for Moves<'_> {}
651impl FusedIterator for Moves<'_> {}
652
653impl MovesMut<'_> {
654    #[allow(clippy::should_implement_trait)]
655    pub fn next(&mut self) -> Option<MoveMut<'_>> {
656        loop {
657            let slot = self.game.tree.position(self.position).options.get(self.index).copied()?;
658            self.index += 1;
659
660            if self.visited.insert(slot) && self.game.tree.contains(slot.into()) {
661                return Some(MoveMut { game: self.game, slot, protected: self.protected.clone() });
662            }
663        }
664    }
665}
666
667#[cfg(test)]
668mod tests {
669    use crate::{Role::Pawn, Square::*};
670
671    use super::*;
672
673    #[test]
674    fn choice_debug() {
675        let slot = MoveSlot::from_index(21).unwrap();
676        let play = chess::Move::normal(Pawn, E2, E4);
677
678        assert_eq!(format!("{:?}", Choice::Index(37)), "Index(37)");
679        assert_eq!(format!("{:?}", Choice::Move(play)), "Move(e2-e4)");
680        assert_eq!(format!("{:?}", Choice::Slot(slot)), "Slot(22)");
681    }
682
683    #[test]
684    fn missing_display() {
685        let position = PositionSlot::from(12);
686        let slot = MoveSlot::from_index(21).unwrap();
687        let play = chess::Move::normal(Pawn, E2, E4);
688
689        assert_eq!(Error::Position(position).to_string(), "position slot 12 not found");
690        assert_eq!(Error::Move(slot).to_string(), "move slot 22 not found");
691        assert_eq!(
692            Missing { position, choice: Choice::Index(37) }.to_string(),
693            "option Index(37) not found in position slot 12"
694        );
695        assert_eq!(
696            Missing { position, choice: Choice::Slot(slot) }.to_string(),
697            "option Slot(22) not found in position slot 12"
698        );
699        assert_eq!(
700            Missing { position, choice: Choice::Move(play) }.to_string(),
701            "option Move(e2-e4) not found in position slot 12"
702        );
703    }
704}
chess/game/traversal.rs

chess/game/
traversal.rs
