mod bracket_table;
mod class_table;
pub mod mirror;
mod mirror_table;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[allow(clippy::upper_case_acronyms)]
pub enum Class {
L,
R,
AL,
EN,
ES,
ET,
AN,
CS,
NSM,
BN,
B,
S,
WS,
ON,
LRE,
LRO,
RLE,
RLO,
PDF,
LRI,
RLI,
FSI,
PDI,
}
impl Class {
#[must_use]
pub fn is_isolate_initiator(self) -> bool {
matches!(self, Self::LRI | Self::RLI | Self::FSI)
}
#[must_use]
pub fn is_removed_by_x9(self) -> bool {
matches!(
self,
Self::RLE | Self::LRE | Self::RLO | Self::LRO | Self::PDF | Self::BN
)
}
#[must_use]
pub fn is_strong(self) -> bool {
matches!(self, Self::L | Self::R | Self::AL)
}
}
#[must_use]
pub fn class(c: char) -> Class {
let c = c as u32;
let r = class_table::RANGES;
let mut lo = 0usize;
let mut hi = r.len();
while lo < hi {
let mid = lo + (hi - lo) / 2;
let (first, last, k) = r[mid];
if c < first {
hi = mid;
} else if c > last {
lo = mid + 1;
} else {
return k;
}
}
Class::L
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Direction {
Ltr,
Rtl,
Auto,
}
pub const MAX_DEPTH: u8 = 125;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Levels {
pub levels: Vec<u8>,
pub paragraph: u8,
pub classes: Vec<Class>,
}
#[must_use]
pub fn paragraph_level(text: &[Class]) -> u8 {
let mut depth = 0usize;
for c in text {
match c {
c if c.is_isolate_initiator() => depth += 1,
Class::PDI if depth > 0 => depth -= 1,
Class::L if depth == 0 => return 0,
Class::R | Class::AL if depth == 0 => return 1,
_ => {}
}
}
0
}
fn matching_pdi(classes: &[Class]) -> Vec<Option<usize>> {
let mut out = vec![None; classes.len()];
for (i, c) in classes.iter().enumerate() {
if !c.is_isolate_initiator() {
continue;
}
let mut depth = 1usize;
for (j, d) in classes.iter().enumerate().skip(i + 1) {
if d.is_isolate_initiator() {
depth += 1;
} else if *d == Class::PDI {
depth -= 1;
if depth == 0 {
out[i] = Some(j);
break;
}
}
}
}
out
}
#[derive(Clone, Copy)]
struct Status {
level: u8,
override_to: Option<Class>,
isolate: bool,
}
fn explicit(classes: &[Class], para: u8, pdi_of: &[Option<usize>]) -> (Vec<u8>, Vec<Class>) {
let n = classes.len();
let mut levels = vec![para; n];
let mut out = classes.to_vec();
let mut stack: Vec<Status> = vec![Status {
level: para,
override_to: None,
isolate: false,
}];
let mut overflow_isolate = 0usize;
let mut overflow_embedding = 0usize;
let mut valid_isolate = 0usize;
for i in 0..n {
let c = classes[i];
match c {
Class::RLE | Class::LRE | Class::RLO | Class::LRO => {
levels[i] = stack.last().map_or(para, |s| s.level);
let rtl = matches!(c, Class::RLE | Class::RLO);
let next = next_level(stack.last().map_or(para, |s| s.level), rtl);
let over = match c {
Class::RLO => Some(Class::R),
Class::LRO => Some(Class::L),
_ => None,
};
if next <= MAX_DEPTH && overflow_isolate == 0 && overflow_embedding == 0 {
stack.push(Status {
level: next,
override_to: over,
isolate: false,
});
} else if overflow_isolate == 0 {
overflow_embedding += 1;
}
}
Class::RLI | Class::LRI | Class::FSI => {
let top = stack.last().copied().unwrap_or(Status {
level: para,
override_to: None,
isolate: false,
});
levels[i] = top.level;
if let Some(o) = top.override_to {
out[i] = o;
}
let rtl = match c {
Class::RLI => true,
Class::LRI => false,
_ => {
let end = pdi_of[i].unwrap_or(n);
paragraph_level(&classes[i + 1..end]) == 1
}
};
let next = next_level(top.level, rtl);
if next <= MAX_DEPTH && overflow_isolate == 0 && overflow_embedding == 0 {
valid_isolate += 1;
stack.push(Status {
level: next,
override_to: None,
isolate: true,
});
} else {
overflow_isolate += 1;
}
}
Class::PDI => {
if overflow_isolate > 0 {
overflow_isolate -= 1;
} else if valid_isolate > 0 {
overflow_embedding = 0;
while stack.last().is_some_and(|s| !s.isolate) {
stack.pop();
}
stack.pop();
valid_isolate -= 1;
}
let top = stack.last().copied().unwrap_or(Status {
level: para,
override_to: None,
isolate: false,
});
levels[i] = top.level;
if let Some(o) = top.override_to {
out[i] = o;
}
}
Class::PDF => {
levels[i] = stack.last().map_or(para, |s| s.level);
if overflow_isolate > 0 {
} else if overflow_embedding > 0 {
overflow_embedding -= 1;
} else if stack.last().is_some_and(|s| !s.isolate) && stack.len() > 1 {
stack.pop();
}
}
Class::B => {
stack.truncate(1);
overflow_isolate = 0;
overflow_embedding = 0;
valid_isolate = 0;
levels[i] = para;
}
_ => {
let top = stack.last().copied().unwrap_or(Status {
level: para,
override_to: None,
isolate: false,
});
levels[i] = top.level;
if !c.is_removed_by_x9()
&& let Some(o) = top.override_to
{
out[i] = o;
}
}
}
}
(levels, out)
}
fn next_level(level: u8, rtl: bool) -> u8 {
if rtl {
(level + 1) | 1
} else {
(level + 2) & !1
}
}
#[must_use]
pub fn resolve(text: &str, direction: Direction) -> Levels {
let chars: Vec<char> = text.chars().collect();
let classes: Vec<Class> = chars.iter().copied().map(class).collect();
resolve_inner(&classes, Some(&chars), direction)
}
#[must_use]
pub fn resolve_classes(classes: &[Class], direction: Direction) -> Levels {
resolve_inner(classes, None, direction)
}
fn resolve_inner(classes: &[Class], chars: Option<&[char]>, direction: Direction) -> Levels {
let para = match direction {
Direction::Ltr => 0,
Direction::Rtl => 1,
Direction::Auto => paragraph_level(classes),
};
let pdi_of = matching_pdi(classes);
let (mut levels, effective) = explicit(classes, para, &pdi_of);
for seq in isolating_runs(&effective, &levels, para, &pdi_of) {
resolve_sequence(&seq, &effective, &mut levels, chars);
}
for i in 0..classes.len() {
if classes[i].is_removed_by_x9() {
levels[i] = if i == 0 { para } else { levels[i - 1] };
}
}
let n = classes.len();
let resettable = |k: Class| {
matches!(
k,
Class::WS | Class::LRI | Class::RLI | Class::FSI | Class::PDI
) || k.is_removed_by_x9()
};
for i in 0..n {
if !matches!(classes[i], Class::B | Class::S) {
continue;
}
levels[i] = para;
for j in (0..i).rev() {
if !resettable(classes[j]) {
break;
}
levels[j] = para;
}
}
let mut i = n;
while i > 0 && resettable(classes[i - 1]) {
i -= 1;
levels[i] = para;
}
Levels {
levels,
paragraph: para,
classes: classes.to_vec(),
}
}
#[derive(Debug)]
struct Sequence {
indices: Vec<usize>,
level: u8,
sos: Class,
eos: Class,
}
fn isolating_runs(
classes: &[Class],
levels: &[u8],
para: u8,
pdi_of: &[Option<usize>],
) -> Vec<Sequence> {
let n = classes.len();
let keep: Vec<usize> = (0..n).filter(|i| !classes[*i].is_removed_by_x9()).collect();
let mut runs: Vec<Vec<usize>> = Vec::new();
for i in keep {
match runs.last_mut() {
Some(r) if levels[*r.last().unwrap()] == levels[i] => r.push(i),
_ => runs.push(vec![i]),
}
}
let mut used = vec![false; runs.len()];
let start_of: std::collections::BTreeMap<usize, usize> =
runs.iter().enumerate().map(|(k, r)| (r[0], k)).collect();
let mut out = Vec::new();
for k in 0..runs.len() {
if used[k] {
continue;
}
let first = runs[k][0];
if classes[first] == Class::PDI && pdi_of.contains(&Some(first)) {
continue;
}
let mut indices: Vec<usize> = Vec::new();
let mut at = k;
loop {
used[at] = true;
indices.extend_from_slice(&runs[at]);
let last = *runs[at].last().unwrap();
let Some(m) = pdi_of.get(last).copied().flatten() else {
break;
};
if !classes[last].is_isolate_initiator() {
break;
}
let Some(next) = start_of.get(&m).copied() else {
break;
};
if used[next] {
break;
}
at = next;
}
let level = levels[indices[0]];
let before = indices[0];
let prev = (0..before).rev().find(|i| !classes[*i].is_removed_by_x9());
let sos_level =
levels[prev.unwrap_or(0)]
.max(level)
.max(if prev.is_none() { para } else { 0 });
let after = *indices.last().unwrap();
let ends_isolated =
classes[after].is_isolate_initiator() && pdi_of.get(after).copied().flatten().is_none();
let next = (after + 1..n).find(|i| !classes[*i].is_removed_by_x9());
let eos_level = match next {
_ if ends_isolated => level.max(para),
None => level.max(para),
Some(k) => levels[k].max(level),
};
out.push(Sequence {
indices,
level,
sos: if sos_level % 2 == 1 {
Class::R
} else {
Class::L
},
eos: if eos_level % 2 == 1 {
Class::R
} else {
Class::L
},
});
}
out
}
fn bracket_pairs(indices: &[usize], chars: &[char]) -> Vec<(usize, usize)> {
fn canonical(c: char) -> char {
match c {
'\u{2329}' => '\u{3008}',
'\u{232A}' => '\u{3009}',
other => other,
}
}
let mut stack: Vec<(char, usize)> = Vec::new();
let mut out: Vec<(usize, usize)> = Vec::new();
for (k, idx) in indices.iter().enumerate() {
let Some(ch) = chars.get(*idx).copied() else {
continue;
};
match bracket_of(ch) {
Some((pair, bracket_table::Bracket::Open)) => {
if stack.len() == 63 {
return out;
}
stack.push((canonical(pair), k));
}
Some((_, bracket_table::Bracket::Close)) => {
let me = canonical(ch);
if let Some(at) = stack.iter().rposition(|(want, _)| *want == me) {
out.push((stack[at].1, k));
stack.truncate(at);
}
}
None => {}
}
}
out.sort_unstable();
out
}
#[must_use]
fn bracket_of(c: char) -> Option<(char, bracket_table::Bracket)> {
let key = c as u32;
let t = bracket_table::BRACKETS;
let i = t.binary_search_by_key(&key, |(a, _, _)| *a).ok()?;
let (_, pair, kind) = t[i];
Some((char::from_u32(pair)?, kind))
}
fn resolve_sequence(seq: &Sequence, classes: &[Class], levels: &mut [u8], chars: Option<&[char]>) {
let n = seq.indices.len();
if n == 0 {
return;
}
let mut c: Vec<Class> = seq.indices.iter().map(|i| classes[*i]).collect();
#[allow(clippy::needless_range_loop)]
for i in 0..n {
if c[i] != Class::NSM {
continue;
}
c[i] = if i == 0 {
seq.sos
} else if c[i - 1].is_isolate_initiator() || c[i - 1] == Class::PDI {
Class::ON
} else {
c[i - 1]
};
}
#[allow(clippy::needless_range_loop)]
for i in 0..n {
if c[i] != Class::EN {
continue;
}
let strong = (0..i)
.rev()
.map(|j| c[j])
.find(|k| k.is_strong())
.unwrap_or(seq.sos);
if strong == Class::AL {
c[i] = Class::AN;
}
}
for k in c.iter_mut() {
if *k == Class::AL {
*k = Class::R;
}
}
for i in 1..n.saturating_sub(1) {
if c[i] == Class::ES && c[i - 1] == Class::EN && c[i + 1] == Class::EN {
c[i] = Class::EN;
} else if c[i] == Class::CS
&& ((c[i - 1] == Class::EN && c[i + 1] == Class::EN)
|| (c[i - 1] == Class::AN && c[i + 1] == Class::AN))
{
c[i] = c[i - 1];
}
}
let mut i = 0;
while i < n {
if c[i] != Class::ET {
i += 1;
continue;
}
let mut j = i;
while j < n && c[j] == Class::ET {
j += 1;
}
let before = i > 0 && c[i - 1] == Class::EN;
let after = j < n && c[j] == Class::EN;
if before || after {
for k in &mut c[i..j] {
*k = Class::EN;
}
}
i = j;
}
for k in c.iter_mut() {
if matches!(*k, Class::ES | Class::ET | Class::CS) {
*k = Class::ON;
}
}
#[allow(clippy::needless_range_loop)]
for i in 0..n {
if c[i] != Class::EN {
continue;
}
let strong = (0..i)
.rev()
.map(|j| c[j])
.find(|k| k.is_strong())
.unwrap_or(seq.sos);
if strong == Class::L {
c[i] = Class::L;
}
}
if let Some(chars) = chars {
let e = if seq.level % 2 == 1 {
Class::R
} else {
Class::L
};
let o = if e == Class::R { Class::L } else { Class::R };
for (open, close) in bracket_pairs(&seq.indices, chars) {
let inside = |want: Class| {
(open + 1..close).any(|k| match c[k] {
Class::L => want == Class::L,
Class::R | Class::EN | Class::AN => want == Class::R,
_ => false,
})
};
let to = if inside(e) {
Some(e)
} else if inside(o) {
let before = (0..open)
.rev()
.find_map(|k| match c[k] {
Class::L => Some(Class::L),
Class::R | Class::EN | Class::AN => Some(Class::R),
_ => None,
})
.unwrap_or(seq.sos);
Some(if before == o { o } else { e })
} else {
None
};
if let Some(to) = to {
c[open] = to;
c[close] = to;
}
}
}
let strong_of = |k: Class| -> Option<Class> {
match k {
Class::L => Some(Class::L),
Class::R | Class::EN | Class::AN => Some(Class::R),
_ => None,
}
};
let neutral = |k: Class| {
matches!(k, Class::B | Class::S | Class::WS | Class::ON | Class::PDI)
|| k.is_isolate_initiator()
};
let mut i = 0;
while i < n {
if !neutral(c[i]) {
i += 1;
continue;
}
let mut j = i;
while j < n && neutral(c[j]) {
j += 1;
}
let before = if i == 0 {
seq.sos
} else {
strong_of(c[i - 1]).unwrap_or(seq.sos)
};
let after = if j == n {
seq.eos
} else {
strong_of(c[j]).unwrap_or(seq.eos)
};
let to = if before == after {
before
} else if seq.level % 2 == 1 {
Class::R
} else {
Class::L
};
for k in &mut c[i..j] {
*k = to;
}
i = j;
}
for (k, idx) in seq.indices.iter().enumerate() {
let lvl = seq.level;
levels[*idx] = if lvl.is_multiple_of(2) {
match c[k] {
Class::R => lvl + 1,
Class::AN | Class::EN => lvl + 2,
_ => lvl,
}
} else {
match c[k] {
Class::L | Class::EN | Class::AN => lvl + 1,
_ => lvl,
}
};
}
}
#[must_use]
pub fn reorder(levels: &[u8], paragraph: u8) -> Vec<usize> {
let mut out: Vec<usize> = (0..levels.len()).collect();
if levels.is_empty() {
return out;
}
let highest = *levels.iter().max().unwrap_or(&0);
let lowest_odd = levels
.iter()
.filter(|l| **l % 2 == 1)
.min()
.copied()
.unwrap_or(u8::MAX)
.min(if paragraph % 2 == 1 {
paragraph
} else {
u8::MAX
});
if lowest_odd == u8::MAX {
return out;
}
let mut level = highest.max(lowest_odd);
while level >= lowest_odd && level > 0 {
let mut i = 0;
while i < levels.len() {
if levels[i] < level {
i += 1;
continue;
}
let mut j = i;
while j < levels.len() && levels[j] >= level {
j += 1;
}
out[i..j].reverse();
i = j;
}
level -= 1;
}
out
}
impl Levels {
#[must_use]
pub fn visual(&self) -> Vec<usize> {
let keep: Vec<usize> = (0..self.classes.len())
.filter(|i| !self.classes[*i].is_removed_by_x9())
.collect();
let kept: Vec<u8> = keep.iter().map(|i| self.levels[*i]).collect();
reorder(&kept, self.paragraph)
.into_iter()
.map(|k| keep[k])
.collect()
}
}
#[must_use]
pub fn visual_order(text: &str, direction: Direction) -> Vec<usize> {
resolve(text, direction).visual()
}
#[cfg(test)]
mod tests {
use super::*;
use String;
fn visual(text: &str, d: Direction) -> String {
let r = resolve(text, d);
let chars: Vec<char> = text.chars().collect();
r.visual()
.into_iter()
.map(|i| mirror::at_level(chars[i], r.levels[i]))
.collect()
}
#[test]
fn latin_is_left_alone() {
assert_eq!(visual("Hello", Direction::Ltr), "Hello");
assert_eq!(resolve("Hello", Direction::Ltr).levels, vec![0, 0, 0, 0, 0]);
}
#[test]
fn hebrew_reverses() {
let t = "\u{5D0}\u{5D1}\u{5D2}";
assert_eq!(visual(t, Direction::Auto), "\u{5D2}\u{5D1}\u{5D0}");
assert_eq!(resolve(t, Direction::Auto).paragraph, 1);
}
#[test]
fn the_paragraph_direction_comes_from_the_first_strong_character() {
assert_eq!(resolve("abc \u{5D0}", Direction::Auto).paragraph, 0);
assert_eq!(resolve("\u{5D0} abc", Direction::Auto).paragraph, 1);
assert_eq!(resolve("123 ... \u{5D0}", Direction::Auto).paragraph, 1);
assert_eq!(resolve("123", Direction::Auto).paragraph, 0);
assert_eq!(
resolve("\u{2066}\u{5D0}\u{2069}abc", Direction::Auto).paragraph,
0
);
}
#[test]
fn a_number_after_hebrew_stays_with_it() {
let t = "\u{5D0}\u{5D1} 12 \u{5D2}";
let r = resolve(t, Direction::Auto);
assert_eq!(r.paragraph, 1);
assert_eq!(r.levels, vec![1, 1, 1, 2, 2, 1, 1]);
assert_eq!(visual(t, Direction::Auto), "\u{5D2} 12 \u{5D1}\u{5D0}");
}
#[test]
fn an_arabic_letter_turns_a_following_number_arabic() {
let t = "\u{627}12";
let r = resolve(t, Direction::Auto);
assert_eq!(r.levels, vec![1, 2, 2]);
let r = resolve("a12", Direction::Ltr);
assert_eq!(r.levels, vec![0, 0, 0]);
}
#[test]
fn brackets_lean_with_what_they_contain() {
let t = "\u{5D0} (\u{5D1}) b";
let r = resolve(t, Direction::Ltr);
assert_eq!(r.levels, vec![1, 1, 1, 1, 1, 0, 0]);
assert_eq!(visual(t, Direction::Ltr), "(\u{5D1}) \u{5D0} b");
}
#[test]
fn an_override_forces_direction() {
let t = "a\u{202E}bcd\u{202C}e";
assert_eq!(
visual(t, Direction::Ltr),
"a\u{202E}dcb\u{202C}e".replace(['\u{202E}', '\u{202C}'], "")
);
}
#[test]
fn an_isolate_does_not_leak() {
let inside = "abc \u{2066}\u{5D0}\u{5D1}\u{2069} 12";
let leaky = "abc \u{202B}\u{5D0}\u{5D1}\u{202C} 12";
let a = resolve(inside, Direction::Ltr);
let b = resolve(leaky, Direction::Ltr);
assert_ne!(a.levels, b.levels, "the isolate behaved like an embedding");
}
#[test]
fn the_visual_order_is_always_a_permutation() {
for t in [
"",
" ",
"abc",
"\u{5D0}\u{5D1}",
"a\u{202E}b\u{202C}c",
"a\u{2066}b\u{2069}c",
"\u{2069}\u{2069}\u{2069}",
"((((((",
"a\u{5B7}\u{5B7}b",
] {
for d in [Direction::Ltr, Direction::Rtl, Direction::Auto] {
let r = resolve(t, d);
assert_eq!(r.levels.len(), t.chars().count(), "{t:?}");
let order = r.visual();
let mut sorted = order.clone();
sorted.sort_unstable();
let expect: Vec<usize> = (0..t.chars().count())
.filter(|i| !r.classes[*i].is_removed_by_x9())
.collect();
assert_eq!(sorted, expect, "{t:?} at {d:?} is not a permutation");
}
}
}
#[test]
fn deep_nesting_stops_at_the_limit() {
let mut t = String::new();
for _ in 0..200 {
t.push('\u{202B}');
}
t.push('a');
let r = resolve(&t, Direction::Ltr);
assert!(
r.levels.iter().all(|l| *l <= MAX_DEPTH + 1),
"a level ran past the cap"
);
assert_eq!(r.levels.len(), t.chars().count());
}
#[test]
fn a_class_is_found_for_every_codepoint() {
for c in [
'\0',
'a',
'\u{5D0}',
'\u{627}',
'\u{661}',
'\u{2066}',
'\u{10FFFF}',
'\u{E0001}',
] {
let _ = class(c);
}
assert_eq!(class('a'), Class::L);
assert_eq!(class('\u{5D0}'), Class::R);
assert_eq!(class('\u{627}'), Class::AL);
assert_eq!(class('1'), Class::EN);
assert_eq!(class('\u{661}'), Class::AN);
assert_eq!(class(' '), Class::WS);
assert_eq!(class('\u{2066}'), Class::LRI);
assert_eq!(class('\u{200B}'), Class::BN);
}
#[test]
fn the_class_table_is_sorted_and_complete() {
let mut next = 0u32;
for (first, last, _) in class_table::RANGES {
assert_eq!(*first, next, "a gap or overlap before {first:#X}");
assert!(last >= first);
next = last + 1;
}
assert_eq!(next, 0x11_0000, "the table stops at {next:#X}");
}
}