document_graphics/sgf/
position.rs

1use super::*;
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq)]
4pub enum Color {
5    Black,
6    White,
7}
8impl Color {
9    pub fn other(self) -> Self {
10        match self {
11            Self::Black => Self::White,
12            Self::White => Self::Black,
13        }
14    }
15    fn index(self) -> usize {
16        if self == Self::Black { 0 } else { 1 }
17    }
18}
19#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub struct Point {
21    pub x: u8,
22    pub y: u8,
23}
24impl Point {
25    pub fn coordinate(self, height: u8) -> String {
26        const LETTERS: &[u8] = b"ABCDEFGHJKLMNOPQRSTUVWXYZ";
27        let x = self.x as usize;
28        let column = if x < LETTERS.len() {
29            (LETTERS[x] as char).to_string()
30        } else {
31            format!(
32                "{}{}",
33                LETTERS[x / LETTERS.len() - 1] as char,
34                LETTERS[x % LETTERS.len()] as char
35            )
36        };
37        format!("{column}{}", height.saturating_sub(self.y))
38    }
39}
40#[derive(Debug, Clone, Copy, PartialEq, Eq)]
41pub struct Played {
42    pub color: Color,
43    pub point: Option<Point>,
44    pub number: u32,
45}
46#[derive(Debug, Clone, PartialEq, Eq)]
47pub enum MarkKind {
48    Circle,
49    Square,
50    Triangle,
51    Cross,
52    Selected,
53    Label(String),
54    Territory(Color),
55    Dim,
56}
57#[derive(Debug, Clone, PartialEq, Eq)]
58pub struct Mark {
59    pub at: Point,
60    pub kind: MarkKind,
61}
62#[derive(Debug, Clone)]
63pub struct Line {
64    pub from: Point,
65    pub to: Point,
66    pub arrow: bool,
67}
68
69/// A single board. Applications may cache a bounded number of these independently.
70#[derive(Debug, Clone)]
71pub struct Position {
72    pub width: u8,
73    pub height: u8,
74    pub to_play: Color,
75    /// Prisoners taken by Black, then White. Setup stones never count as captures.
76    pub captures: [u32; 2],
77    pub move_number: u32,
78    pub last_move: Option<Played>,
79    pub marks: Vec<Mark>,
80    pub lines: Vec<Line>,
81    node: NodeId,
82    source: Arc<[u8]>,
83    board: Vec<Option<Color>>,
84    numbers: Vec<u32>,
85}
86impl Position {
87    pub(super) fn validate(&self) -> Result<(), Error> {
88        if !(1..=52).contains(&self.width)
89            || !(1..=52).contains(&self.height)
90            || self.board.len() != self.width as usize * self.height as usize
91            || self.marks.len() > 512
92            || self.lines.len() > 512
93        {
94            return Err(Error::Limit("Invalid or oversized SGF diagram"));
95        }
96        let inside = |p: Point| p.x < self.width && p.y < self.height;
97        if self
98            .marks
99            .iter()
100            .any(|m| !inside(m.at) || matches!(&m.kind, MarkKind::Label(s) if s.chars().count()>32))
101            || self.lines.iter().any(|l| !inside(l.from) || !inside(l.to))
102            || self
103                .last_move
104                .is_some_and(|m| m.point.is_some_and(|p| !inside(p)))
105        {
106            return Err(Error::Limit("Invalid or oversized SGF board annotation"));
107        }
108        Ok(())
109    }
110    pub fn node(&self) -> NodeId {
111        self.node
112    }
113    pub fn stone(&self, point: Point) -> Option<Color> {
114        if point.x >= self.width || point.y >= self.height {
115            return None;
116        }
117        self.board
118            .get(point.y as usize * self.width as usize + point.x as usize)
119            .copied()
120            .flatten()
121    }
122    pub fn number(&self, point: Point) -> u32 {
123        if point.x >= self.width || point.y >= self.height {
124            return 0;
125        }
126        self.numbers
127            .get(point.y as usize * self.width as usize + point.x as usize)
128            .copied()
129            .unwrap_or(0)
130    }
131    /// Incremental forward navigation; the target must be a direct child.
132    pub fn advance(
133        &self,
134        doc: &Collection,
135        node: NodeId,
136        cancel: &AtomicBool,
137    ) -> Result<Self, Error> {
138        if !Arc::ptr_eq(&self.source, &doc.source)
139            || doc
140                .nodes
141                .get(node)
142                .is_none_or(|n| n.parent != Some(self.node))
143        {
144            return Err(invalid(
145                0,
146                "Position does not precede the requested SGF node",
147            ));
148        }
149        self.validate()?;
150        let mut next = self.clone();
151        next.apply(doc, node, &mut Work::new(self.board.len(), cancel))?;
152        Ok(next)
153    }
154    fn index(&self, p: Point) -> usize {
155        p.y as usize * self.width as usize + p.x as usize
156    }
157    fn apply(&mut self, doc: &Collection, node: NodeId, work: &mut Work<'_>) -> Result<(), Error> {
158        check(work.cancel)?;
159        let offset = doc.nodes[node].source.start;
160        let black = doc.text(node, "B");
161        let white = doc.text(node, "W");
162        if black.is_some() && white.is_some() {
163            return Err(invalid(offset, "B and W cannot share an SGF node"));
164        }
165        let has_move = black.is_some() || white.is_some();
166        if doc.ranges(node, "B").len() > 1 || doc.ranges(node, "W").len() > 1 {
167            return Err(invalid(offset, "A move must have one value"));
168        }
169        for key in ["SZ", "GM", "CA", "FF"] {
170            if doc.nodes[node].parent.is_some() && !doc.ranges(node, key).is_empty() {
171                return Err(invalid(offset, "Root property outside the SGF root"));
172            }
173        }
174        for (key, color) in [
175            ("AE", None),
176            ("AB", Some(Color::Black)),
177            ("AW", Some(Color::White)),
178        ] {
179            if has_move && !doc.ranges(node, key).is_empty() {
180                return Err(invalid(
181                    offset,
182                    "Moves and setup stones cannot share an SGF node",
183                ));
184            }
185            for value in doc.values(node, key) {
186                for point in points(&value, self.width, self.height, offset)? {
187                    work.step()?;
188                    let i = self.index(point);
189                    self.board[i] = color;
190                    self.numbers[i] = 0;
191                }
192            }
193        }
194        if let Some(value) = black.as_ref().or(white.as_ref()) {
195            self.move_number = self.move_number.saturating_add(1);
196            if let Some(number) = doc.text(node, "MN") {
197                self.move_number = number
198                    .trim()
199                    .parse::<u32>()
200                    .map_err(|_| invalid(offset, "Invalid SGF move number"))?;
201            }
202            let color = if black.is_some() {
203                Color::Black
204            } else {
205                Color::White
206            };
207            let point =
208                if value.is_empty() || (value == "tt" && self.width <= 19 && self.height <= 19) {
209                    None
210                } else {
211                    Some(point(value, self.width, self.height, offset)?)
212                };
213            if let Some(p) = point {
214                let i = self.index(p);
215                self.board[i] = Some(color);
216                self.numbers[i] = self.move_number;
217                for j in neighbors(i, self.width as usize, self.board.len()) {
218                    if self.board[j] == Some(color.other()) {
219                        self.remove_dead(j, color, work)?;
220                    }
221                }
222                self.remove_dead(i, color.other(), work)?;
223            }
224            self.last_move = Some(Played {
225                color,
226                point,
227                number: self.move_number,
228            });
229            self.to_play = color.other();
230        } else if doc.nodes[node].parent.is_none()
231            && doc
232                .text(node, "HA")
233                .and_then(|s| s.parse::<u16>().ok())
234                .is_some_and(|n| n >= 2)
235        {
236            self.to_play = Color::White;
237        }
238        if let Some(player) = doc.text(node, "PL") {
239            self.to_play = match player.as_str() {
240                "B" => Color::Black,
241                "W" => Color::White,
242                _ => return Err(invalid(offset, "Invalid player to move")),
243            };
244        }
245        // Most markup is node-local. Dimmed points inherit until DD[] clears them.
246        self.marks.retain(|m| matches!(m.kind, MarkKind::Dim));
247        if !doc.ranges(node, "DD").is_empty() {
248            self.marks.clear();
249        }
250        self.lines.clear();
251        for (key, kind) in [
252            ("CR", MarkKind::Circle),
253            ("SQ", MarkKind::Square),
254            ("TR", MarkKind::Triangle),
255            ("MA", MarkKind::Cross),
256            ("SL", MarkKind::Selected),
257            ("TB", MarkKind::Territory(Color::Black)),
258            ("TW", MarkKind::Territory(Color::White)),
259            ("DD", MarkKind::Dim),
260        ] {
261            for value in doc.values(node, key) {
262                for at in points(&value, self.width, self.height, offset)? {
263                    work.step()?;
264                    if self.marks.len() >= 512 {
265                        return Err(Error::Limit("SGF node exceeds 512 board marks"));
266                    }
267                    self.marks.push(Mark {
268                        at,
269                        kind: kind.clone(),
270                    });
271                }
272            }
273        }
274        for value in doc.values(node, "LB") {
275            let (p, label) = value
276                .split_once(':')
277                .ok_or_else(|| invalid(offset, "Invalid SGF label"))?;
278            if self.marks.len() >= 512 || label.chars().count() > 32 {
279                return Err(Error::Limit("SGF board label limit exceeded"));
280            }
281            self.marks.push(Mark {
282                at: point(p, self.width, self.height, offset)?,
283                kind: MarkKind::Label(label.into()),
284            });
285        }
286        for (key, arrow) in [("AR", true), ("LN", false)] {
287            for value in doc.values(node, key) {
288                if self.lines.len() >= 512 {
289                    return Err(Error::Limit("SGF node exceeds 512 lines"));
290                }
291                let (a, b) = value
292                    .split_once(':')
293                    .ok_or_else(|| invalid(offset, "Invalid SGF line"))?;
294                self.lines.push(Line {
295                    from: point(a, self.width, self.height, offset)?,
296                    to: point(b, self.width, self.height, offset)?,
297                    arrow,
298                });
299            }
300        }
301        self.node = node;
302        Ok(())
303    }
304    fn remove_dead(
305        &mut self,
306        start: usize,
307        captor: Color,
308        work: &mut Work<'_>,
309    ) -> Result<(), Error> {
310        let Some(color) = self.board[start] else {
311            return Ok(());
312        };
313        work.seen.fill(false);
314        work.stack.clear();
315        work.group.clear();
316        work.stack.push(start);
317        while let Some(i) = work.stack.pop() {
318            if work.seen[i] {
319                continue;
320            }
321            work.seen[i] = true;
322            work.step()?;
323            work.group.push(i);
324            for j in neighbors(i, self.width as usize, self.board.len()) {
325                match self.board[j] {
326                    None => return Ok(()),
327                    Some(c) if c == color && !work.seen[j] => work.stack.push(j),
328                    _ => {}
329                }
330            }
331        }
332        for &i in &work.group {
333            self.board[i] = None;
334            self.numbers[i] = 0;
335        }
336        self.captures[captor.index()] =
337            self.captures[captor.index()].saturating_add(work.group.len() as u32);
338        Ok(())
339    }
340}
341fn neighbors(i: usize, width: usize, len: usize) -> impl Iterator<Item = usize> {
342    [
343        if !i.is_multiple_of(width) {
344            Some(i - 1)
345        } else {
346            None
347        },
348        if i % width + 1 < width {
349            Some(i + 1)
350        } else {
351            None
352        },
353        i.checked_sub(width),
354        if i + width < len {
355            Some(i + width)
356        } else {
357            None
358        },
359    ]
360    .into_iter()
361    .flatten()
362}
363struct Work<'a> {
364    seen: Vec<bool>,
365    stack: Vec<usize>,
366    group: Vec<usize>,
367    steps: usize,
368    cancel: &'a AtomicBool,
369}
370impl<'a> Work<'a> {
371    fn new(size: usize, cancel: &'a AtomicBool) -> Self {
372        Self {
373            seen: vec![false; size],
374            stack: Vec::new(),
375            group: Vec::new(),
376            steps: 0,
377            cancel,
378        }
379    }
380    fn step(&mut self) -> Result<(), Error> {
381        self.steps += 1;
382        if self.steps > 20_000_000 {
383            return Err(Error::Limit(
384                "SGF position reconstruction exceeded its work limit",
385            ));
386        }
387        if self.steps.is_multiple_of(1024) {
388            check(self.cancel)?;
389        }
390        Ok(())
391    }
392}
393pub(super) fn at(doc: &Collection, node: NodeId, cancel: &AtomicBool) -> Result<Position, Error> {
394    check(cancel)?;
395    let selected = doc
396        .nodes
397        .get(node)
398        .ok_or_else(|| invalid(0, "Unknown SGF node"))?;
399    let game = &doc.games[selected.game];
400    let size = game.width as usize * game.height as usize;
401    let mut result = Position {
402        width: game.width,
403        height: game.height,
404        to_play: Color::Black,
405        captures: [0, 0],
406        move_number: 0,
407        last_move: None,
408        marks: Vec::new(),
409        lines: Vec::new(),
410        node: game.root,
411        source: doc.source.clone(),
412        board: vec![None; size],
413        numbers: vec![0; size],
414    };
415    let mut path = Vec::new();
416    let mut current = Some(node);
417    while let Some(id) = current {
418        check(cancel)?;
419        path.push(id);
420        current = doc.nodes[id].parent;
421    }
422    let mut work = Work::new(size, cancel);
423    for id in path.into_iter().rev() {
424        work.step()?;
425        result.apply(doc, id, &mut work)?;
426    }
427    Ok(result)
428}
429pub(super) fn point(s: &str, width: u8, height: u8, offset: usize) -> Result<Point, Error> {
430    let index = |b| match b {
431        b'a'..=b'z' => Some(b - b'a'),
432        b'A'..=b'Z' => Some(b - b'A' + 26),
433        _ => None,
434    };
435    let b = s.as_bytes();
436    if b.len() == 2
437        && let (Some(x), Some(y)) = (index(b[0]), index(b[1]))
438        && x < width
439        && y < height
440    {
441        return Ok(Point { x, y });
442    }
443    Err(invalid(offset, "SGF point is outside the board"))
444}
445fn points(s: &str, width: u8, height: u8, offset: usize) -> Result<Vec<Point>, Error> {
446    if s.is_empty() {
447        return Ok(Vec::new());
448    }
449    if let Some((a, b)) = s.split_once(':') {
450        let a = point(a, width, height, offset)?;
451        let b = point(b, width, height, offset)?;
452        if a.x > b.x || a.y > b.y {
453            return Err(invalid(offset, "Reversed SGF point rectangle"));
454        }
455        Ok((a.y..=b.y)
456            .flat_map(|y| (a.x..=b.x).map(move |x| Point { x, y }))
457            .collect())
458    } else {
459        Ok(vec![point(s, width, height, offset)?])
460    }
461}
document_graphics/sgf/position.rs

document_graphics/sgf/
position.rs
