Skip to main content

textflow/
bidi.rs

1use crate::unicode::Script;
2use core::ops::Range;
3
4use crate::buffer::SliceWriter;
5
6#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
7pub enum BaseDirection {
8    #[default]
9    Auto,
10    LeftToRight,
11    RightToLeft,
12}
13
14#[derive(Clone, Copy, Debug, Eq, PartialEq)]
15pub enum Direction {
16    LeftToRight,
17    RightToLeft,
18}
19
20impl Direction {
21    pub const fn from_level(level: u8) -> Self {
22        if level & 1 == 0 {
23            Self::LeftToRight
24        } else {
25            Self::RightToLeft
26        }
27    }
28}
29
30#[derive(Clone, Debug, Eq, PartialEq)]
31pub struct BidiRun {
32    pub text: Range<usize>,
33    pub level: u8,
34    pub direction: Direction,
35}
36
37impl BidiRun {
38    pub const fn empty() -> Self {
39        Self {
40            text: 0..0,
41            level: 0,
42            direction: Direction::LeftToRight,
43        }
44    }
45}
46
47#[derive(Clone, Copy, Debug, Eq, PartialEq)]
48pub enum BidiError {
49    InsufficientCapacity { required: usize },
50    UnsupportedControl { offset: usize },
51    InvalidTextRange,
52}
53
54pub struct BidiText<'a> {
55    text: Range<usize>,
56    direction: Direction,
57    runs: &'a [BidiRun],
58}
59
60impl<'a> BidiText<'a> {
61    pub fn resolve(
62        text: &str,
63        range: Range<usize>,
64        base_direction: BaseDirection,
65        output: &'a mut [BidiRun],
66    ) -> Result<Self, BidiError> {
67        validate_range(text, &range)?;
68        if let Some(offset) = text[range.clone()]
69            .char_indices()
70            .find_map(|(offset, character)| {
71                is_bidi_control(character).then_some(range.start + offset)
72            })
73        {
74            return Err(BidiError::UnsupportedControl { offset });
75        }
76        let direction = resolve_base_direction(&text[range.clone()], base_direction);
77        let mut writer = RunWriter::new(output, direction);
78        resolve_runs(text, range.clone(), direction, &mut writer);
79        let runs = writer.finish()?;
80        Ok(Self {
81            text: range,
82            direction,
83            runs,
84        })
85    }
86
87    pub const fn direction(&self) -> Direction {
88        self.direction
89    }
90
91    pub fn text(&self) -> Range<usize> {
92        self.text.clone()
93    }
94
95    pub const fn logical_runs(&self) -> &[BidiRun] {
96        self.runs
97    }
98
99    pub fn visual_runs_into<'b>(
100        &self,
101        output: &'b mut [BidiRun],
102    ) -> Result<&'b [BidiRun], BidiError> {
103        if output.len() < self.runs.len() {
104            return Err(BidiError::InsufficientCapacity {
105                required: self.runs.len(),
106            });
107        }
108        output[..self.runs.len()].clone_from_slice(self.runs);
109        let max_level = output[..self.runs.len()]
110            .iter()
111            .map(|run| run.level)
112            .max()
113            .unwrap_or(0);
114        let min_odd = output[..self.runs.len()]
115            .iter()
116            .filter(|run| run.level % 2 == 1)
117            .map(|run| run.level)
118            .min();
119        if let Some(min_odd) = min_odd {
120            for level in (min_odd..=max_level).rev() {
121                reverse_level_sequences(&mut output[..self.runs.len()], level);
122            }
123        }
124        Ok(&output[..self.runs.len()])
125    }
126}
127
128fn resolve_runs(text: &str, range: Range<usize>, base: Direction, writer: &mut RunWriter<'_>) {
129    let mut segment_start = range.start;
130    let mut active = base;
131    let mut neutral_start = None;
132
133    for (local_offset, character) in text[range.clone()].char_indices() {
134        let offset = range.start + local_offset;
135        match strong_direction(character) {
136            Some(next) => {
137                if let Some(neutral) = neutral_start.take() {
138                    writer.push(segment_start..neutral, active);
139                    let neutral_direction = if active == next { active } else { base };
140                    writer.push(neutral..offset, neutral_direction);
141                    segment_start = offset;
142                } else if next != active {
143                    writer.push(segment_start..offset, active);
144                    segment_start = offset;
145                }
146                active = next;
147            }
148            None => {
149                neutral_start.get_or_insert(offset);
150            }
151        }
152    }
153
154    if let Some(neutral) = neutral_start {
155        writer.push(segment_start..neutral, active);
156        writer.push(neutral..range.end, base);
157    } else {
158        writer.push(segment_start..range.end, active);
159    }
160}
161
162struct RunWriter<'a> {
163    output: SliceWriter<'a, BidiRun>,
164    base: Direction,
165    last_direction: Option<Direction>,
166}
167
168impl<'a> RunWriter<'a> {
169    fn new(output: &'a mut [BidiRun], base: Direction) -> Self {
170        Self {
171            output: SliceWriter::new(output),
172            base,
173            last_direction: None,
174        }
175    }
176
177    fn push(&mut self, text: Range<usize>, direction: Direction) {
178        if text.is_empty() {
179            return;
180        }
181        if self.last_direction == Some(direction) {
182            if let Some(last) = self.output.last_mut() {
183                last.text.end = text.end;
184            }
185            return;
186        }
187        self.output.push(BidiRun {
188            text,
189            level: level(self.base, direction),
190            direction,
191        });
192        self.last_direction = Some(direction);
193    }
194
195    fn finish(self) -> Result<&'a [BidiRun], BidiError> {
196        self.output
197            .finish()
198            .map_err(|required| BidiError::InsufficientCapacity { required })
199    }
200}
201
202fn resolve_base_direction(text: &str, requested: BaseDirection) -> Direction {
203    match requested {
204        BaseDirection::LeftToRight => Direction::LeftToRight,
205        BaseDirection::RightToLeft => Direction::RightToLeft,
206        BaseDirection::Auto => text
207            .chars()
208            .find_map(strong_direction)
209            .unwrap_or(Direction::LeftToRight),
210    }
211}
212
213fn strong_direction(character: char) -> Option<Direction> {
214    if character.is_ascii_digit() || matches!(character as u32, 0x0660..=0x0669 | 0x06F0..=0x06F9) {
215        return Some(Direction::LeftToRight);
216    }
217    match Script::of(character) {
218        Script::Hebrew | Script::Arabic => Some(Direction::RightToLeft),
219        Script::Latin
220        | Script::Greek
221        | Script::Cyrillic
222        | Script::Devanagari
223        | Script::Han
224        | Script::Hiragana
225        | Script::Katakana
226        | Script::Hangul => Some(Direction::LeftToRight),
227        Script::Common | Script::Inherited | Script::Unknown => None,
228    }
229}
230
231fn level(base: Direction, direction: Direction) -> u8 {
232    match (base, direction) {
233        (Direction::LeftToRight, Direction::LeftToRight) => 0,
234        (Direction::LeftToRight, Direction::RightToLeft) => 1,
235        (Direction::RightToLeft, Direction::RightToLeft) => 1,
236        (Direction::RightToLeft, Direction::LeftToRight) => 2,
237    }
238}
239
240fn reverse_level_sequences(runs: &mut [BidiRun], level: u8) {
241    let mut start = 0;
242    while start < runs.len() {
243        if runs[start].level < level {
244            start += 1;
245            continue;
246        }
247        let mut end = start + 1;
248        while end < runs.len() && runs[end].level >= level {
249            end += 1;
250        }
251        runs[start..end].reverse();
252        start = end;
253    }
254}
255
256fn validate_range(text: &str, range: &Range<usize>) -> Result<(), BidiError> {
257    if range.start <= range.end
258        && range.end <= text.len()
259        && text.is_char_boundary(range.start)
260        && text.is_char_boundary(range.end)
261    {
262        Ok(())
263    } else {
264        Err(BidiError::InvalidTextRange)
265    }
266}
267
268fn is_bidi_control(character: char) -> bool {
269    matches!(
270        character as u32,
271        0x061C | 0x200E..=0x200F | 0x202A..=0x202E | 0x2066..=0x2069
272    )
273}
274
275#[cfg(test)]
276mod tests {
277    use super::*;
278    use std::prelude::v1::*;
279
280    fn slots<const N: usize>() -> [BidiRun; N] {
281        core::array::from_fn(|_| BidiRun::empty())
282    }
283
284    #[test]
285    fn resolves_common_mixed_runs_without_allocation() {
286        let text = "abc אבג 123";
287        let mut logical = slots::<8>();
288        let bidi =
289            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut logical).unwrap();
290
291        assert_eq!(bidi.direction(), Direction::LeftToRight);
292        assert_eq!(bidi.logical_runs().len(), 3);
293        assert_eq!(&text[bidi.logical_runs()[0].text.clone()], "abc ");
294        assert_eq!(&text[bidi.logical_runs()[1].text.clone()], "אבג");
295        assert_eq!(&text[bidi.logical_runs()[2].text.clone()], " 123");
296    }
297
298    #[test]
299    fn reorders_rtl_runs_into_visual_order() {
300        let text = "אבג abc";
301        let mut logical = slots::<8>();
302        let bidi = BidiText::resolve(
303            text,
304            0..text.len(),
305            BaseDirection::RightToLeft,
306            &mut logical,
307        )
308        .unwrap();
309        let mut visual = slots::<8>();
310        let visual = bidi.visual_runs_into(&mut visual).unwrap();
311
312        assert_eq!(&text[visual[0].text.clone()], "abc");
313        assert_eq!(visual[0].level, 2);
314        assert_eq!(&text[visual[1].text.clone()], "אבג ");
315        assert_eq!(visual[1].level, 1);
316    }
317
318    #[test]
319    fn reports_capacity_and_unsupported_controls() {
320        let mut one = slots::<1>();
321        let mixed = "abc אבג";
322        assert_eq!(
323            BidiText::resolve(mixed, 0..mixed.len(), BaseDirection::Auto, &mut one)
324                .err()
325                .unwrap(),
326            BidiError::InsufficientCapacity { required: 2 }
327        );
328        let controlled = "abc\u{202E}def";
329        assert_eq!(
330            BidiText::resolve(
331                controlled,
332                0..controlled.len(),
333                BaseDirection::Auto,
334                &mut one
335            )
336            .err()
337            .unwrap(),
338            BidiError::UnsupportedControl { offset: 3 }
339        );
340    }
341}