ochrepad_core/
brackets.rs

1//! Matching brackets: `()`, `[]` and `{}`. Plain text: a bracket inside a
2//! string or comment counts like any other. The search is bounded so a caret
3//! next to an unmatched bracket in a huge file stays cheap.
4
5use crate::position::ByteOffset;
6use crate::text::Document;
7
8/// How far either way to look for the match.
9pub const SEARCH_LIMIT: usize = 100_000;
10
11const PAIRS: [(u8, u8); 3] = [(b'(', b')'), (b'[', b']'), (b'{', b'}')];
12
13/// A bracket next to a caret, and its match if there is one in reach.
14#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15pub struct BracketPair {
16    /// The bracket at the caret.
17    pub at: ByteOffset,
18    pub matching: Option<ByteOffset>,
19    /// Whether the bracket is after the caret (else before it).
20    pub after_caret: bool,
21}
22
23fn byte_at(doc: &Document, pos: ByteOffset) -> Option<u8> {
24    doc.char_at(pos).filter(char::is_ascii).map(|c| c as u8)
25}
26
27/// The bracket just after `caret`, or else just before it, and its match.
28pub fn bracket_at(doc: &Document, caret: ByteOffset) -> Option<BracketPair> {
29    let is_bracket = |b: u8| PAIRS.iter().any(|&(o, c)| b == o || b == c);
30    let (at, after_caret) = match byte_at(doc, caret).filter(|&b| is_bracket(b)) {
31        Some(_) => (caret, true),
32        None if caret.0 > 0 => {
33            // A bracket is one byte; inside a longer character there is none.
34            let before = ByteOffset(caret.0 - 1);
35            if !doc.is_char_boundary(before) {
36                return None;
37            }
38            byte_at(doc, before).filter(|&b| is_bracket(b))?;
39            (before, false)
40        }
41        None => return None,
42    };
43    Some(BracketPair {
44        at,
45        matching: find_match(doc, at),
46        after_caret,
47    })
48}
49
50/// The bracket matching the one at `at`, counting nesting of the same kind.
51pub fn find_match(doc: &Document, at: ByteOffset) -> Option<ByteOffset> {
52    let b = byte_at(doc, at)?;
53    // Brackets are ASCII, which never occurs inside a UTF-8 multibyte
54    // sequence, so scanning bytes is safe.
55    if let Some(&(open, close)) = PAIRS.iter().find(|p| p.0 == b) {
56        // The window's edge may fall inside a multibyte character.
57        let mut end = (at.0 + 1 + SEARCH_LIMIT).min(doc.len().0);
58        while !doc.is_char_boundary(ByteOffset(end)) {
59            end -= 1;
60        }
61        let text = doc.slice(ByteOffset(at.0 + 1)..ByteOffset(end));
62        let mut depth = 0usize;
63        for (i, c) in text.bytes().enumerate() {
64            if c == open {
65                depth += 1;
66            } else if c == close {
67                if depth == 0 {
68                    return Some(ByteOffset(at.0 + 1 + i));
69                }
70                depth -= 1;
71            }
72        }
73        None
74    } else {
75        let &(open, close) = PAIRS.iter().find(|p| p.1 == b)?;
76        let mut start = at.0.saturating_sub(SEARCH_LIMIT);
77        while !doc.is_char_boundary(ByteOffset(start)) {
78            start += 1;
79        }
80        let text = doc.slice(ByteOffset(start)..at);
81        let mut depth = 0usize;
82        for (i, c) in text.bytes().enumerate().rev() {
83            if c == close {
84                depth += 1;
85            } else if c == open {
86                if depth == 0 {
87                    return Some(ByteOffset(start + i));
88                }
89                depth -= 1;
90            }
91        }
92        None
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    fn pair(text: &str, caret: usize) -> Option<(usize, Option<usize>, bool)> {
101        bracket_at(&Document::new(text), ByteOffset(caret))
102            .map(|p| (p.at.0, p.matching.map(|m| m.0), p.after_caret))
103    }
104
105    #[test]
106    fn brackets_match_with_nesting_and_either_side_of_the_caret() {
107        let t = "f(a[1], (b))";
108        assert_eq!(pair(t, 1), Some((1, Some(11), true)));
109        assert_eq!(pair(t, 12), Some((11, Some(1), false)));
110        assert_eq!(pair(t, 8), Some((8, Some(10), true)));
111        assert_eq!(pair(t, 4), Some((3, Some(5), false)), "after the [");
112        assert_eq!(
113            pair(t, 5),
114            Some((5, Some(3), true)),
115            "] wins when right after the caret"
116        );
117        assert_eq!(pair("x(é)", 1), Some((1, Some(4), true)));
118        assert_eq!(
119            pair("(]", 0),
120            Some((0, None, true)),
121            "other kinds do not close it"
122        );
123        assert_eq!(pair("abc", 1), None);
124        assert_eq!(pair("İx", 2), None, "after a two-byte character");
125    }
126
127    #[test]
128    fn the_search_window_never_splits_a_character() {
129        // Unmatched brackets with more than the search limit of multibyte
130        // text beside them: every alignment of the window's edge.
131        for pad in 0..4 {
132            let filler = "é".repeat(SEARCH_LIMIT / 2 + 3);
133            let open = format!("{}{{{filler}", "x".repeat(pad));
134            assert_eq!(pair(&open, pad), Some((pad, None, true)));
135            let close = format!("{filler}{}}}", "x".repeat(pad));
136            let at = close.len() - 1;
137            assert_eq!(pair(&close, at), Some((at, None, true)));
138            // 3- and 4-byte characters too.
139            let wide = format!("{}[{}", "x".repeat(pad), "漢😀".repeat(SEARCH_LIMIT / 6));
140            assert_eq!(pair(&wide, pad), Some((pad, None, true)));
141        }
142    }
143}
ochrepad_core/brackets.rs

ochrepad_core/
brackets.rs
