bidi/bidi.mbt1///|2/// Unicode Bidirectional Algorithm (UAX #9)3///4/// This module implements the Unicode Bidirectional Algorithm for5/// determining the display order of text containing both left-to-right6/// and right-to-left characters.78///|9/// Direction of text10#derive(Eq)11pub(all) enum Direction {12 LTR // Left-to-Right (base level 0)13 RTL // Right-to-Left (base level 1)14}1516///|17pub extend Direction with Eq::{not_equal, equal}1819///|20pub extend Direction with Show::{to_string, output}2122///|23pub impl Show for Direction with fn output(self, logger) {24 match self {25 LTR => logger.write_string("LTR")26 RTL => logger.write_string("RTL")27 }28}2930///|31/// Result of bidi processing - a paragraph with resolved levels32pub(all) struct BidiParagraph {33 /// Original characters34 chars : Array[Char]35 /// Original Bidi classes (before resolution)36 original_classes : Array[BidiClass]37 /// Resolved Bidi classes (after W and N rules)38 resolved_classes : Array[BidiClass]39 /// Resolved embedding level per character (0-125)40 levels : Array[Int32]41 /// Paragraph embedding level (0 for LTR, 1 for RTL)42 base_level : Int3243}4445///|46/// Maximum embedding level allowed by UAX #947let max_depth : Int32 = 1254849///|50/// Look up Bidi_Class for a character51pub fn bidi_class(c : Char) -> BidiClass {52 lookup_bidi_class(c)53}5455///|56/// Detect the base direction of text (P2-P3)57/// Returns the direction of the first strong character,58/// or LTR if no strong character is found59pub fn detect_direction(text : String) -> Direction {60 let level = determine_paragraph_level(text, default_level=0)61 if level == 0 {62 LTR63 } else {64 RTL65 }66}6768///|69/// Check if text requires bidi processing70/// Returns false for pure LTR text (optimization)71#cfg(not(any(target="native", target="wasm")))72pub fn requires_bidi(text : String) -> Bool {73 for c in text {74 let bc = lookup_bidi_class(c)75 if bc.is_strong_rtl() || bc.is_explicit() {76 return true77 }78 }79 false80}8182///|83/// Check if text requires bidi processing84/// Returns false for pure LTR text (optimization)85#cfg(any(target="native", target="wasm"))86pub fn requires_bidi(text : String) -> Bool {87 // Once a stretch of characters has had its classes looked up, blocks of88 // eight code units are tried: a block below `LeftToRightLimit` needs no89 // lookup. The stretch starts short, so that text with an early90 // right-to-left character never reaches a block, and grows while no block91 // can be skipped, so that text above the limit pays for few tries.92 let length = text.length()93 let mut offset = 094 let mut stretch = MinClassStretch95 while offset < length {96 let mut end = if length - offset > stretch {97 offset + stretch98 } else {99 length100 }101 if end < length &&102 text[end - 1].is_leading_surrogate() &&103 text[end].is_trailing_surrogate() {104 // Keep a surrogate pair that crosses the end of the stretch together.105 end += 1106 }107 // This range is already `0 <= offset < end <= length`, which is all the108 // old bounds-checked view verified: a raw view needs no clamping, and it109 // also keeps a lone surrogate that a block boundary may land on.110 for c in text.unsafe_view(start=offset, end~) {111 let bc = lookup_bidi_class(c)112 if bc.is_strong_rtl() || bc.is_explicit() {113 return true114 }115 }116 offset = skip_left_to_right_blocks(text, end, length)117 if offset > end {118 stretch = MinClassStretch119 } else if stretch < MaxClassStretch {120 stretch = 4 * stretch121 }122 }123 false124}125126///|127/// Code units looked up before the first block and after a block that cannot128/// be skipped.129#cfg(any(target="native", target="wasm"))130const MinClassStretch : Int32 = 16131132///|133#cfg(any(target="native", target="wasm"))134const MaxClassStretch : Int32 = 4096135136///|137/// Code points below U+0590, where the Hebrew block starts, are neither138/// strongly right-to-left nor explicit formatting characters.139#cfg(any(target="native", target="wasm"))140const LeftToRightLimit : Int32 = 0x590141142///|143/// Skip blocks of eight code units that are all below `LeftToRightLimit`,144/// and return the offset of the first block that is not, or that is145/// incomplete.146#cfg(any(target="native", target="wasm"))147// The SIMD operations are experimental upstream. Only this function uses148// them, so the alert is silenced here and not for the whole package.149#warnings("-alert_experimental")150fn skip_left_to_right_blocks(151 text : String,152 start : Int32,153 length : Int32,154) -> Int32 {155 let limit = @v128.i16x8_splat(LeftToRightLimit.to_uint16())156 let mut offset = start157 while offset + 8 <= length {158 // SAFETY: offset is nonnegative and offset + 8 <= length is checked above.159 let block = @v128.v128_load_i16x8(text, offset)160 if @v128.v128_any_true(@v128.i16x8_ge_u(block, limit)) {161 break162 }163 offset += 8164 }165 offset166}167168///|169/// Process text according to the Unicode Bidirectional Algorithm170/// If `direction` is omitted, infer it from the first strong character.171/// Returns a BidiParagraph with resolved embedding levels for each character172pub fn process(text : String, direction? : Direction) -> BidiParagraph {173 let base_level = if direction is Some(direction) {174 direction.level()175 } else {176 determine_paragraph_level(text, default_level=0)177 }178 process_at_base_level(text, base_level)179}180181///|182/// Process text with explicit base direction183/// Use when the paragraph direction is known externally184#deprecated("Use process(text, direction=direction) instead")185pub fn process_with_direction(186 text : String,187 direction : Direction,188) -> BidiParagraph {189 process(text, direction~)190}191192///|193/// Process text with explicit base level194#deprecated("Use process(text, direction=LTR or RTL) instead")195pub fn process_with_base_level(196 text : String,197 base_level : Int32,198) -> BidiParagraph {199 process_at_base_level(text, base_level)200}201202///|203fn process_at_base_level(text : String, base_level : Int32) -> BidiParagraph {204 // Convert to char array and get original classes205 let chars : Array[Char] = Array(capacity=text.length())206 let original_classes : Array[BidiClass] = Array(capacity=text.length())207 let mut has_explicit = false208 let mut has_rtl = false209 for c in text {210 let bc = lookup_bidi_class(c)211 if bc.is_explicit() {212 has_explicit = true213 } else if bc is (R | AL | AN) {214 has_rtl = true215 }216 chars.push(c)217 original_classes.push(bc)218 }219 if base_level == 0 && !has_explicit && !has_rtl {220 // With no R, AL, AN or explicit formatting character in a left-to-right221 // paragraph, W1-W7 and N0-N2 resolve every type but BN to L (the most222 // recent strong type, sos and eos are all L), so every level stays 0.223 let resolved_classes : Array[BidiClass] = Array(224 capacity=original_classes.length(),225 )226 for bc in original_classes {227 resolved_classes.push(if bc is BN { BN } else { L })228 }229 let levels : Array[Int32] = Array::make(chars.length(), 0)230 return { chars, original_classes, resolved_classes, levels, base_level, }231 }232233 // Make a copy for resolution234 let resolved_classes = original_classes.copy()235236 // Allocate levels array237 let levels : Array[Int32] = Array::make(chars.length(), base_level)238 let sequences = if has_explicit {239 // X1-X10: Process explicit formatting characters240 let isolate_pairs = process_explicit(resolved_classes, levels, base_level)241242 // Align NSM levels with the previous non-X9 character.243 adjust_nsm_levels(original_classes, levels)244245 // Compute isolating run sequences246 compute_isolating_run_sequences(247 resolved_classes, levels, original_classes, base_level, isolate_pairs,248 )249 } else {250 // Without embeddings, overrides or isolates, X1-X8 leave every type as251 // it is and every character at the paragraph level, so the paragraph is252 // one level run.253 paragraph_run_sequence(resolved_classes, base_level)254 }255 let bracket_scratch = BracketScratch::new()256 for seq in sequences {257 // W1-W7: Resolve weak types258 resolve_weak_types(resolved_classes, levels, seq)259260 // N0: Resolve bracket pairs, and the NSMs that follow a changed bracket261 resolve_bracket_pairs(262 bracket_scratch, chars, resolved_classes, original_classes, seq,263 )264265 // N1-N2: Resolve neutral types266 resolve_neutral_types(resolved_classes, levels, seq)267 }268269 // I1-I2: Apply implicit levels270 apply_implicit_levels(resolved_classes, levels)271272 // L1: Reset whitespace and separator levels273 reset_whitespace_levels(original_classes, levels, base_level)274 { chars, original_classes, resolved_classes, levels, base_level, }275}276277///|278/// Reorder text for display according to resolved levels279/// Returns array of character indices in visual order280/// X9-removed characters (LRE, RLE, LRO, RLO, PDF, BN) are excluded281pub fn reorder(para : BidiParagraph) -> Array[Int32] {282 // X9: remove explicit formatting and BN before reordering.283 let indices : Array[Int32] = [284 for i, bc in para.original_classes if !bc.is_x9_removed() => i285 ]286 apply_reordering(indices, para.levels, para.base_level)287}288289///|290/// Reorder text and return the visually-ordered string291pub fn reorder_string(para : BidiParagraph) -> String {292 let order = reorder(para)293 let sb = StringBuilder()294 for i in order {295 let c = para.chars[i]296 let level = para.levels[i]297 // Apply mirroring for RTL levels (odd levels)298 if level % 2 == 1 {299 sb.write_char(@bidi_data.bidi_mirroring_glyph(c))300 } else {301 sb.write_char(c)302 }303 }304 sb.to_string()305}306307///|308/// Get the mirrored glyph for a character if in RTL context309pub fn get_mirrored(c : Char, level : Int32) -> Char {310 if level % 2 == 1 {311 @bidi_data.bidi_mirroring_glyph(c)312 } else {313 c314 }315}316317///|318/// Get embedding level for direction319pub fn Direction::level(self : Direction) -> Int32 {320 match self {321 LTR => 0322 RTL => 1323 }324}325326///|327/// Get direction from embedding level328pub fn direction_from_level(level : Int32) -> Direction {329 if level % 2 == 0 {330 LTR331 } else {332 RTL333 }334}335
///|
/// Unicode Bidirectional Algorithm (UAX #9)
///
/// This module implements the Unicode Bidirectional Algorithm for
/// determining the display order of text containing both left-to-right
/// and right-to-left characters.
///|
/// Direction of text
#derive(Eq)
pub(all) enum Direction {
LTR // Left-to-Right (base level 0)
RTL // Right-to-Left (base level 1)
}
///|
pub extend Direction with Eq::{not_equal, equal}
///|
pub extend Direction with Show::{to_string, output}
///|
pub impl Show for Direction with fn output(self, logger) {
match self {
LTR => logger.write_string("LTR")
RTL => logger.write_string("RTL")
}
}
///|
/// Result of bidi processing - a paragraph with resolved levels
pub(all) struct BidiParagraph {
/// Original characters
chars : Array[Char]
/// Original Bidi classes (before resolution)
original_classes : Array[BidiClass]
/// Resolved Bidi classes (after W and N rules)
resolved_classes : Array[BidiClass]
/// Resolved embedding level per character (0-125)
levels : Array[Int32]
/// Paragraph embedding level (0 for LTR, 1 for RTL)
base_level : Int32
}
///|
/// Maximum embedding level allowed by UAX #9
let max_depth : Int32 = 125
///|
/// Look up Bidi_Class for a character
pub fn bidi_class(c : Char) -> BidiClass {
lookup_bidi_class(c)
}
///|
/// Detect the base direction of text (P2-P3)
/// Returns the direction of the first strong character,
/// or LTR if no strong character is found
pub fn detect_direction(text : String) -> Direction {
let level = determine_paragraph_level(text, default_level=0)
if level == 0 {
LTR
} else {
RTL
}
}
///|
/// Check if text requires bidi processing
/// Returns false for pure LTR text (optimization)
#cfg(not(any(target="native", target="wasm")))
pub fn requires_bidi(text : String) -> Bool {
for c in text {
let bc = lookup_bidi_class(c)
if bc.is_strong_rtl() || bc.is_explicit() {
return true
}
}
false
}
///|
/// Check if text requires bidi processing
/// Returns false for pure LTR text (optimization)
#cfg(any(target="native", target="wasm"))
pub fn requires_bidi(text : String) -> Bool {
// Once a stretch of characters has had its classes looked up, blocks of
// eight code units are tried: a block below `LeftToRightLimit` needs no
// lookup. The stretch starts short, so that text with an early
// right-to-left character never reaches a block, and grows while no block
// can be skipped, so that text above the limit pays for few tries.
let length = text.length()
let mut offset = 0
let mut stretch = MinClassStretch
while offset < length {
let mut end = if length - offset > stretch {
offset + stretch
} else {
length
}
if end < length &&
text[end - 1].is_leading_surrogate() &&
text[end].is_trailing_surrogate() {
// Keep a surrogate pair that crosses the end of the stretch together.
end += 1
}
// This range is already `0 <= offset < end <= length`, which is all the
// old bounds-checked view verified: a raw view needs no clamping, and it
// also keeps a lone surrogate that a block boundary may land on.
for c in text.unsafe_view(start=offset, end~) {
let bc = lookup_bidi_class(c)
if bc.is_strong_rtl() || bc.is_explicit() {
return true
}
}
offset = skip_left_to_right_blocks(text, end, length)
if offset > end {
stretch = MinClassStretch
} else if stretch < MaxClassStretch {
stretch = 4 * stretch
}
}
false
}
///|
/// Code units looked up before the first block and after a block that cannot
/// be skipped.
#cfg(any(target="native", target="wasm"))
const MinClassStretch : Int32 = 16
///|
#cfg(any(target="native", target="wasm"))
const MaxClassStretch : Int32 = 4096
///|
/// Code points below U+0590, where the Hebrew block starts, are neither
/// strongly right-to-left nor explicit formatting characters.
#cfg(any(target="native", target="wasm"))
const LeftToRightLimit : Int32 = 0x590
///|
/// Skip blocks of eight code units that are all below `LeftToRightLimit`,
/// and return the offset of the first block that is not, or that is
/// incomplete.
#cfg(any(target="native", target="wasm"))
// The SIMD operations are experimental upstream. Only this function uses
// them, so the alert is silenced here and not for the whole package.
#warnings("-alert_experimental")
fn skip_left_to_right_blocks(
text : String,
start : Int32,
length : Int32,
) -> Int32 {
let limit = @v128.i16x8_splat(LeftToRightLimit.to_uint16())
let mut offset = start
while offset + 8 <= length {
// SAFETY: offset is nonnegative and offset + 8 <= length is checked above.
let block = @v128.v128_load_i16x8(text, offset)
if @v128.v128_any_true(@v128.i16x8_ge_u(block, limit)) {
break
}
offset += 8
}
offset
}
///|
/// Process text according to the Unicode Bidirectional Algorithm
/// If `direction` is omitted, infer it from the first strong character.
/// Returns a BidiParagraph with resolved embedding levels for each character
pub fn process(text : String, direction? : Direction) -> BidiParagraph {
let base_level = if direction is Some(direction) {
direction.level()
} else {
determine_paragraph_level(text, default_level=0)
}
process_at_base_level(text, base_level)
}
///|
/// Process text with explicit base direction
/// Use when the paragraph direction is known externally
#deprecated("Use process(text, direction=direction) instead")
pub fn process_with_direction(
text : String,
direction : Direction,
) -> BidiParagraph {
process(text, direction~)
}
///|
/// Process text with explicit base level
#deprecated("Use process(text, direction=LTR or RTL) instead")
pub fn process_with_base_level(
text : String,
base_level : Int32,
) -> BidiParagraph {
process_at_base_level(text, base_level)
}
///|
fn process_at_base_level(text : String, base_level : Int32) -> BidiParagraph {
// Convert to char array and get original classes
let chars : Array[Char] = Array(capacity=text.length())
let original_classes : Array[BidiClass] = Array(capacity=text.length())
let mut has_explicit = false
let mut has_rtl = false
for c in text {
let bc = lookup_bidi_class(c)
if bc.is_explicit() {
has_explicit = true
} else if bc is (R | AL | AN) {
has_rtl = true
}
chars.push(c)
original_classes.push(bc)
}
if base_level == 0 && !has_explicit && !has_rtl {
// With no R, AL, AN or explicit formatting character in a left-to-right
// paragraph, W1-W7 and N0-N2 resolve every type but BN to L (the most
// recent strong type, sos and eos are all L), so every level stays 0.
let resolved_classes : Array[BidiClass] = Array(
capacity=original_classes.length(),
)
for bc in original_classes {
resolved_classes.push(if bc is BN { BN } else { L })
}
let levels : Array[Int32] = Array::make(chars.length(), 0)
return { chars, original_classes, resolved_classes, levels, base_level, }
}
// Make a copy for resolution
let resolved_classes = original_classes.copy()
// Allocate levels array
let levels : Array[Int32] = Array::make(chars.length(), base_level)
let sequences = if has_explicit {
// X1-X10: Process explicit formatting characters
let isolate_pairs = process_explicit(resolved_classes, levels, base_level)
// Align NSM levels with the previous non-X9 character.
adjust_nsm_levels(original_classes, levels)
// Compute isolating run sequences
compute_isolating_run_sequences(
resolved_classes, levels, original_classes, base_level, isolate_pairs,
)
} else {
// Without embeddings, overrides or isolates, X1-X8 leave every type as
// it is and every character at the paragraph level, so the paragraph is
// one level run.
paragraph_run_sequence(resolved_classes, base_level)
}
let bracket_scratch = BracketScratch::new()
for seq in sequences {
// W1-W7: Resolve weak types
resolve_weak_types(resolved_classes, levels, seq)
// N0: Resolve bracket pairs, and the NSMs that follow a changed bracket
resolve_bracket_pairs(
bracket_scratch, chars, resolved_classes, original_classes, seq,
)
// N1-N2: Resolve neutral types
resolve_neutral_types(resolved_classes, levels, seq)
}
// I1-I2: Apply implicit levels
apply_implicit_levels(resolved_classes, levels)
// L1: Reset whitespace and separator levels
reset_whitespace_levels(original_classes, levels, base_level)
{ chars, original_classes, resolved_classes, levels, base_level, }
}
///|
/// Reorder text for display according to resolved levels
/// Returns array of character indices in visual order
/// X9-removed characters (LRE, RLE, LRO, RLO, PDF, BN) are excluded
pub fn reorder(para : BidiParagraph) -> Array[Int32] {
// X9: remove explicit formatting and BN before reordering.
let indices : Array[Int32] = [
for i, bc in para.original_classes if !bc.is_x9_removed() => i
]
apply_reordering(indices, para.levels, para.base_level)
}
///|
/// Reorder text and return the visually-ordered string
pub fn reorder_string(para : BidiParagraph) -> String {
let order = reorder(para)
let sb = StringBuilder()
for i in order {
let c = para.chars[i]
let level = para.levels[i]
// Apply mirroring for RTL levels (odd levels)
if level % 2 == 1 {
sb.write_char(@bidi_data.bidi_mirroring_glyph(c))
} else {
sb.write_char(c)
}
}
sb.to_string()
}
///|
/// Get the mirrored glyph for a character if in RTL context
pub fn get_mirrored(c : Char, level : Int32) -> Char {
if level % 2 == 1 {
@bidi_data.bidi_mirroring_glyph(c)
} else {
c
}
}
///|
/// Get embedding level for direction
pub fn Direction::level(self : Direction) -> Int32 {
match self {
LTR => 0
RTL => 1
}
}
///|
/// Get direction from embedding level
pub fn direction_from_level(level : Int32) -> Direction {
if level % 2 == 0 {
LTR
} else {
RTL
}
}