bidi/bracket.mbt1///|2/// N0: Bracket Pair Processing3///4/// This rule handles matching bracket pairs according to UAX #9.5/// It uses the Bidi_Paired_Bracket property to find bracket pairs6/// and resolves their types based on context.78///|9priv struct BracketPair {10 open_index : Int3211 close_index : Int3212 open_position : Int3213 close_position : Int3214 /// Strong types between the brackets: `StrongLtr`, `StrongRtl`, or both.15 strong : Int3216}1718///|19/// An L between a bracket pair.20const StrongLtr : Int32 = 12122///|23/// An R, EN or AN between a bracket pair.24const StrongRtl : Int32 = 22526///|27priv struct BracketStackEntry {28 bracket : Char29 char_index : Int3230 sequence_position : Int3231}3233///|34/// Working storage for bracket pairing, reused across the isolating run35/// sequences of a paragraph.36priv struct BracketScratch {37 /// The pairs found in the current sequence.38 pairs : Array[BracketPair]39 /// Open brackets not yet closed.40 stack : Array[BracketStackEntry]41 /// Strong types seen directly inside each open bracket on the stack.42 strong : Array[Int32]43}4445///|46fn BracketScratch::new() -> BracketScratch {47 { pairs: [], stack: [], strong: [], }48}4950///|51/// Resolve bracket pairs within an isolating run sequence52fn resolve_bracket_pairs(53 scratch : BracketScratch,54 chars : Array[Char],55 types : Array[BidiClass],56 original_classes : Array[BidiClass],57 seq : IsolatingRunSequence,58) -> Unit {59 let indices = seq.indices60 if indices.length() == 0 {61 return62 }6364 // Find bracket pairs in the sequence65 find_bracket_pairs(scratch, chars, types, indices)66 let pairs = scratch.pairs67 if pairs.length() == 0 {68 return69 }7071 // Get embedding direction72 let embedding_is_ltr = seq.level % 2 == 073 let embedding_direction : BidiClass = if embedding_is_ltr {74 BidiClass::L75 } else {76 BidiClass::R77 }78 let opposite_direction : BidiClass = if embedding_is_ltr {79 BidiClass::R80 } else {81 BidiClass::L82 }83 let embedding_strong = if embedding_is_ltr { StrongLtr } else { StrongRtl }84 let opposite_strong = if embedding_is_ltr { StrongRtl } else { StrongLtr }8586 // Scan context monotonically as opening positions increase. Reading from87 // types includes brackets resolved by earlier N0 pairs.88 let mut context_position = 089 let mut context_type = seq.sos90 for pair in pairs {91 while context_position < pair.open_position {92 match types[indices[context_position]] {93 L => context_type = BidiClass::L94 R | EN | AN => context_type = BidiClass::R95 _ => ()96 }97 context_position += 198 }99100 // N0b, N0c: Determine bracket type from the strong types inside the pair101 let resolved = if (pair.strong & embedding_strong) != 0 {102 embedding_direction103 } else if (pair.strong & opposite_strong) != 0 {104 let context_matches_embedding = if embedding_is_ltr {105 context_type is L106 } else {107 context_type is R108 }109 if context_matches_embedding {110 embedding_direction111 } else {112 // N0c2: Set brackets to opposite direction113 opposite_direction114 }115 } else {116 // With no strong type inside, leave brackets as ON117 continue118 }119 types[pair.open_index] = resolved120 types[pair.close_index] = resolved121 retype_following_marks(122 types,123 original_classes,124 indices,125 pair.open_position,126 resolved,127 )128 retype_following_marks(129 types,130 original_classes,131 indices,132 pair.close_position,133 resolved,134 )135 }136}137138///|139/// N0: characters that were NSM before W1 and follow a bracket that N0140/// changed take the bracket's new type. They are still ON here, the type W1141/// gave them from the bracket.142fn retype_following_marks(143 types : Array[BidiClass],144 original_classes : Array[BidiClass],145 indices : Array[Int32],146 bracket_position : Int32,147 resolved : BidiClass,148) -> Unit {149 for position in (bracket_position + 1)..<indices.length() {150 let idx = indices[position]151 guard original_classes[idx] is NSM && types[idx] is ON else { break }152 types[idx] = resolved153 }154}155156///|157/// Find all bracket pairs in an isolating run sequence158/// Leaves them in `scratch.pairs`, sorted by opening position in the sequence.159///160/// The same pass records which strong types lie between each pair. An open161/// bracket collects the strong types seen while it is the innermost one, and162/// hands them to the bracket enclosing it when it is closed or discarded.163/// Brackets resolved for other pairs never count: a pair is resolved before164/// any pair inside it, so the types read here are the ones N0 starts from.165fn find_bracket_pairs(166 scratch : BracketScratch,167 chars : Array[Char],168 types : Array[BidiClass],169 indices : Array[Int32],170) -> Unit {171 let { pairs, stack, strong, } = scratch172 pairs.clear()173 stack.clear()174 strong.clear()175 let mut overflow = false176 for sequence_position, idx in indices {177 // Only consider brackets that are ON type (after weak resolution)178 match types[idx] {179 ON => ()180 L => {181 if strong.length() > 0 {182 strong[strong.length() - 1] = strong[strong.length() - 1] | StrongLtr183 }184 continue185 }186 R | EN | AN => {187 if strong.length() > 0 {188 strong[strong.length() - 1] = strong[strong.length() - 1] | StrongRtl189 }190 continue191 }192 _ => continue193 }194 let c = chars[idx]195 let bracket_type = @bidi_data.bracket_type(c)196 match bracket_type {197 Open =>198 // Push to stack199 if stack.length() < 63 { // BD16 limit200 stack.push({ bracket: c, char_index: idx, sequence_position, })201 strong.push(0)202 } else {203 overflow = true204 break205 }206 Close =>207 // Find matching opening bracket208 if @bidi_data.paired_bracket(c) is Some(matching_open) {209 let matching_canonical = canonical_bracket(matching_open)210 // Search stack from top for matching open bracket211 let mut found = -1212 for j in (stack.length() - 1)>=..0 {213 if canonical_bracket(stack[j].bracket) == matching_canonical {214 found = j215 break216 }217 }218 if found >= 0 {219 let open_entry = stack[found]220 // Everything above the match lies inside the pair too.221 let mut inside = 0222 for j in found..<strong.length() {223 inside = inside | strong[j]224 }225 pairs.push({226 open_index: open_entry.char_index,227 close_index: idx,228 open_position: open_entry.sequence_position,229 close_position: sequence_position,230 strong: inside,231 })232 // Remove found entry and everything above it233 stack.truncate(found)234 strong.truncate(found)235 if found > 0 {236 strong[found - 1] = strong[found - 1] | inside237 }238 }239 }240 None => ()241 }242 }243244 if overflow {245 pairs.clear()246 return247 }248249 // Sort pairs by opening position250 pairs.sort_by(fn(a, b) { a.open_position - b.open_position })251}252253///|254/// Map bracket characters to their canonical equivalents for matching.255fn canonical_bracket(c : Char) -> Char {256 match c {257 '\u{2329}' => '\u{3008}'258 '\u{232A}' => '\u{3009}'259 _ => c260 }261}262
///|
/// N0: Bracket Pair Processing
///
/// This rule handles matching bracket pairs according to UAX #9.
/// It uses the Bidi_Paired_Bracket property to find bracket pairs
/// and resolves their types based on context.
///|
priv struct BracketPair {
open_index : Int32
close_index : Int32
open_position : Int32
close_position : Int32
/// Strong types between the brackets: `StrongLtr`, `StrongRtl`, or both.
strong : Int32
}
///|
/// An L between a bracket pair.
const StrongLtr : Int32 = 1
///|
/// An R, EN or AN between a bracket pair.
const StrongRtl : Int32 = 2
///|
priv struct BracketStackEntry {
bracket : Char
char_index : Int32
sequence_position : Int32
}
///|
/// Working storage for bracket pairing, reused across the isolating run
/// sequences of a paragraph.
priv struct BracketScratch {
/// The pairs found in the current sequence.
pairs : Array[BracketPair]
/// Open brackets not yet closed.
stack : Array[BracketStackEntry]
/// Strong types seen directly inside each open bracket on the stack.
strong : Array[Int32]
}
///|
fn BracketScratch::new() -> BracketScratch {
{ pairs: [], stack: [], strong: [], }
}
///|
/// Resolve bracket pairs within an isolating run sequence
fn resolve_bracket_pairs(
scratch : BracketScratch,
chars : Array[Char],
types : Array[BidiClass],
original_classes : Array[BidiClass],
seq : IsolatingRunSequence,
) -> Unit {
let indices = seq.indices
if indices.length() == 0 {
return
}
// Find bracket pairs in the sequence
find_bracket_pairs(scratch, chars, types, indices)
let pairs = scratch.pairs
if pairs.length() == 0 {
return
}
// Get embedding direction
let embedding_is_ltr = seq.level % 2 == 0
let embedding_direction : BidiClass = if embedding_is_ltr {
BidiClass::L
} else {
BidiClass::R
}
let opposite_direction : BidiClass = if embedding_is_ltr {
BidiClass::R
} else {
BidiClass::L
}
let embedding_strong = if embedding_is_ltr { StrongLtr } else { StrongRtl }
let opposite_strong = if embedding_is_ltr { StrongRtl } else { StrongLtr }
// Scan context monotonically as opening positions increase. Reading from
// types includes brackets resolved by earlier N0 pairs.
let mut context_position = 0
let mut context_type = seq.sos
for pair in pairs {
while context_position < pair.open_position {
match types[indices[context_position]] {
L => context_type = BidiClass::L
R | EN | AN => context_type = BidiClass::R
_ => ()
}
context_position += 1
}
// N0b, N0c: Determine bracket type from the strong types inside the pair
let resolved = if (pair.strong & embedding_strong) != 0 {
embedding_direction
} else if (pair.strong & opposite_strong) != 0 {
let context_matches_embedding = if embedding_is_ltr {
context_type is L
} else {
context_type is R
}
if context_matches_embedding {
embedding_direction
} else {
// N0c2: Set brackets to opposite direction
opposite_direction
}
} else {
// With no strong type inside, leave brackets as ON
continue
}
types[pair.open_index] = resolved
types[pair.close_index] = resolved
retype_following_marks(
types,
original_classes,
indices,
pair.open_position,
resolved,
)
retype_following_marks(
types,
original_classes,
indices,
pair.close_position,
resolved,
)
}
}
///|
/// N0: characters that were NSM before W1 and follow a bracket that N0
/// changed take the bracket's new type. They are still ON here, the type W1
/// gave them from the bracket.
fn retype_following_marks(
types : Array[BidiClass],
original_classes : Array[BidiClass],
indices : Array[Int32],
bracket_position : Int32,
resolved : BidiClass,
) -> Unit {
for position in (bracket_position + 1)..<indices.length() {
let idx = indices[position]
guard original_classes[idx] is NSM && types[idx] is ON else { break }
types[idx] = resolved
}
}
///|
/// Find all bracket pairs in an isolating run sequence
/// Leaves them in `scratch.pairs`, sorted by opening position in the sequence.
///
/// The same pass records which strong types lie between each pair. An open
/// bracket collects the strong types seen while it is the innermost one, and
/// hands them to the bracket enclosing it when it is closed or discarded.
/// Brackets resolved for other pairs never count: a pair is resolved before
/// any pair inside it, so the types read here are the ones N0 starts from.
fn find_bracket_pairs(
scratch : BracketScratch,
chars : Array[Char],
types : Array[BidiClass],
indices : Array[Int32],
) -> Unit {
let { pairs, stack, strong, } = scratch
pairs.clear()
stack.clear()
strong.clear()
let mut overflow = false
for sequence_position, idx in indices {
// Only consider brackets that are ON type (after weak resolution)
match types[idx] {
ON => ()
L => {
if strong.length() > 0 {
strong[strong.length() - 1] = strong[strong.length() - 1] | StrongLtr
}
continue
}
R | EN | AN => {
if strong.length() > 0 {
strong[strong.length() - 1] = strong[strong.length() - 1] | StrongRtl
}
continue
}
_ => continue
}
let c = chars[idx]
let bracket_type = @bidi_data.bracket_type(c)
match bracket_type {
Open =>
// Push to stack
if stack.length() < 63 { // BD16 limit
stack.push({ bracket: c, char_index: idx, sequence_position, })
strong.push(0)
} else {
overflow = true
break
}
Close =>
// Find matching opening bracket
if @bidi_data.paired_bracket(c) is Some(matching_open) {
let matching_canonical = canonical_bracket(matching_open)
// Search stack from top for matching open bracket
let mut found = -1
for j in (stack.length() - 1)>=..0 {
if canonical_bracket(stack[j].bracket) == matching_canonical {
found = j
break
}
}
if found >= 0 {
let open_entry = stack[found]
// Everything above the match lies inside the pair too.
let mut inside = 0
for j in found..<strong.length() {
inside = inside | strong[j]
}
pairs.push({
open_index: open_entry.char_index,
close_index: idx,
open_position: open_entry.sequence_position,
close_position: sequence_position,
strong: inside,
})
// Remove found entry and everything above it
stack.truncate(found)
strong.truncate(found)
if found > 0 {
strong[found - 1] = strong[found - 1] | inside
}
}
}
None => ()
}
}
if overflow {
pairs.clear()
return
}
// Sort pairs by opening position
pairs.sort_by(fn(a, b) { a.open_position - b.open_position })
}
///|
/// Map bracket characters to their canonical equivalents for matching.
fn canonical_bracket(c : Char) -> Char {
match c {
'\u{2329}' => '\u{3008}'
'\u{232A}' => '\u{3009}'
_ => c
}
}