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::Thai
223        | Script::Devanagari
224        | Script::Han
225        | Script::Hiragana
226        | Script::Katakana
227        | Script::Hangul => Some(Direction::LeftToRight),
228        Script::Common | Script::Inherited | Script::Unknown => None,
229    }
230}
231
232fn level(base: Direction, direction: Direction) -> u8 {
233    match (base, direction) {
234        (Direction::LeftToRight, Direction::LeftToRight) => 0,
235        (Direction::LeftToRight, Direction::RightToLeft) => 1,
236        (Direction::RightToLeft, Direction::RightToLeft) => 1,
237        (Direction::RightToLeft, Direction::LeftToRight) => 2,
238    }
239}
240
241fn reverse_level_sequences(runs: &mut [BidiRun], level: u8) {
242    let mut start = 0;
243    while start < runs.len() {
244        if runs[start].level < level {
245            start += 1;
246            continue;
247        }
248        let mut end = start + 1;
249        while end < runs.len() && runs[end].level >= level {
250            end += 1;
251        }
252        runs[start..end].reverse();
253        start = end;
254    }
255}
256
257fn validate_range(text: &str, range: &Range<usize>) -> Result<(), BidiError> {
258    if range.start <= range.end
259        && range.end <= text.len()
260        && text.is_char_boundary(range.start)
261        && text.is_char_boundary(range.end)
262    {
263        Ok(())
264    } else {
265        Err(BidiError::InvalidTextRange)
266    }
267}
268
269fn is_bidi_control(character: char) -> bool {
270    matches!(
271        character as u32,
272        0x061C | 0x200E..=0x200F | 0x202A..=0x202E | 0x2066..=0x2069
273    )
274}
275
276#[cfg(test)]
277mod tests {
278    use super::*;
279    use std::prelude::v1::*;
280
281    fn slots<const N: usize>() -> [BidiRun; N] {
282        core::array::from_fn(|_| BidiRun::empty())
283    }
284
285    #[test]
286    fn resolves_common_mixed_runs_without_allocation() {
287        let text = "abc אבג 123";
288        let mut logical = slots::<8>();
289        let bidi =
290            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut logical).unwrap();
291
292        assert_eq!(bidi.direction(), Direction::LeftToRight);
293        assert_eq!(bidi.logical_runs().len(), 3);
294        assert_eq!(&text[bidi.logical_runs()[0].text.clone()], "abc ");
295        assert_eq!(&text[bidi.logical_runs()[1].text.clone()], "אבג");
296        assert_eq!(&text[bidi.logical_runs()[2].text.clone()], " 123");
297    }
298
299    #[test]
300    fn reorders_rtl_runs_into_visual_order() {
301        let text = "אבג abc";
302        let mut logical = slots::<8>();
303        let bidi = BidiText::resolve(
304            text,
305            0..text.len(),
306            BaseDirection::RightToLeft,
307            &mut logical,
308        )
309        .unwrap();
310        let mut visual = slots::<8>();
311        let visual = bidi.visual_runs_into(&mut visual).unwrap();
312
313        assert_eq!(&text[visual[0].text.clone()], "abc");
314        assert_eq!(visual[0].level, 2);
315        assert_eq!(&text[visual[1].text.clone()], "אבג ");
316        assert_eq!(visual[1].level, 1);
317    }
318
319    #[test]
320    fn keeps_arabic_indic_numbers_ltr_inside_rtl_text() {
321        let text = "مرحبا ١٢٣ عالم";
322        let mut logical = slots::<8>();
323        let bidi =
324            BidiText::resolve(text, 0..text.len(), BaseDirection::Auto, &mut logical).unwrap();
325
326        assert_eq!(bidi.direction(), Direction::RightToLeft);
327        assert_eq!(bidi.logical_runs().len(), 3);
328        assert_eq!(bidi.logical_runs()[0].direction, Direction::RightToLeft);
329        assert_eq!(&text[bidi.logical_runs()[1].text.clone()], "١٢٣");
330        assert_eq!(bidi.logical_runs()[1].direction, Direction::LeftToRight);
331        assert_eq!(bidi.logical_runs()[2].direction, Direction::RightToLeft);
332
333        let mut visual = slots::<8>();
334        let visual = bidi.visual_runs_into(&mut visual).unwrap();
335        assert_eq!(&text[visual[0].text.clone()], " عالم");
336        assert_eq!(&text[visual[1].text.clone()], "١٢٣");
337        assert_eq!(&text[visual[2].text.clone()], "مرحبا ");
338    }
339
340    #[test]
341    fn reports_capacity_and_unsupported_controls() {
342        let mut one = slots::<1>();
343        let mixed = "abc אבג";
344        assert_eq!(
345            BidiText::resolve(mixed, 0..mixed.len(), BaseDirection::Auto, &mut one)
346                .err()
347                .unwrap(),
348            BidiError::InsufficientCapacity { required: 2 }
349        );
350        let controlled = "abc\u{202E}def";
351        assert_eq!(
352            BidiText::resolve(
353                controlled,
354                0..controlled.len(),
355                BaseDirection::Auto,
356                &mut one
357            )
358            .err()
359            .unwrap(),
360            BidiError::UnsupportedControl { offset: 3 }
361        );
362    }
363}