1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606
// Copyright 2015 The Servo Project Developers. See the
// COPYRIGHT file at the top-level directory of this distribution.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
//! 3.3.4 - 3.3.6. Resolve implicit levels and types.
#[cfg(not(feature = "smallvec"))]
use alloc::vec::Vec;
use core::cmp::max;
#[cfg(feature = "smallvec")]
use smallvec::SmallVec;
use super::char_data::BidiClass::{self, *};
use super::level::Level;
use super::prepare::{not_removed_by_x9, IsolatingRunSequence};
use super::{BidiDataSource, TextSource};
/// 3.3.4 Resolving Weak Types
///
/// <http://www.unicode.org/reports/tr9/#Resolving_Weak_Types>
#[cfg_attr(feature = "flame_it", flamer::flame)]
pub fn resolve_weak<'a, T: TextSource<'a> + ?Sized>(
text: &'a T,
sequence: &IsolatingRunSequence,
processing_classes: &mut [BidiClass],
) {
// Note: The spec treats these steps as individual passes that are applied one after the other
// on the entire IsolatingRunSequence at once. We instead collapse it into a single iteration,
// which is straightforward for rules that are based on the state of the current character, but not
// for rules that care about surrounding characters. To deal with them, we retain additional state
// about previous character classes that may have since been changed by later rules.
// The previous class for the purposes of rule W4/W6, not tracking changes made after or during W4.
let mut prev_class_before_w4 = sequence.sos;
// The previous class for the purposes of rule W5.
let mut prev_class_before_w5 = sequence.sos;
// The previous class for the purposes of rule W1, not tracking changes from any other rules.
let mut prev_class_before_w1 = sequence.sos;
let mut last_strong_is_al = false;
#[cfg(feature = "smallvec")]
let mut et_run_indices = SmallVec::<[usize; 8]>::new(); // for W5
#[cfg(not(feature = "smallvec"))]
let mut et_run_indices = Vec::new(); // for W5
#[cfg(feature = "smallvec")]
let mut bn_run_indices = SmallVec::<[usize; 8]>::new(); // for W5 + <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
#[cfg(not(feature = "smallvec"))]
let mut bn_run_indices = Vec::new(); // for W5 + <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
for (run_index, level_run) in sequence.runs.iter().enumerate() {
for i in &mut level_run.clone() {
if processing_classes[i] == BN {
// <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
// Keeps track of bn runs for W5 in case we see an ET.
bn_run_indices.push(i);
// BNs aren't real, skip over them.
continue;
}
// Store the processing class of all rules before W2/W1.
// Used to keep track of the last strong character for W2. W3 is able to insert new strong
// characters, so we don't want to be misled by it.
let mut w2_processing_class = processing_classes[i];
// <http://www.unicode.org/reports/tr9/#W1>
//
if processing_classes[i] == NSM {
processing_classes[i] = match prev_class_before_w1 {
RLI | LRI | FSI | PDI => ON,
_ => prev_class_before_w1,
};
// W1 occurs before W2, update this.
w2_processing_class = processing_classes[i];
}
prev_class_before_w1 = processing_classes[i];
// <http://www.unicode.org/reports/tr9/#W2>
// <http://www.unicode.org/reports/tr9/#W3>
//
match processing_classes[i] {
EN => {
if last_strong_is_al {
// W2. If previous strong char was AL, change EN to AN.
processing_classes[i] = AN;
}
}
// W3.
AL => processing_classes[i] = R,
_ => {}
}
// update last_strong_is_al.
match w2_processing_class {
L | R => {
last_strong_is_al = false;
}
AL => {
last_strong_is_al = true;
}
_ => {}
}
let class_before_w456 = processing_classes[i];
// <http://www.unicode.org/reports/tr9/#W4>
// <http://www.unicode.org/reports/tr9/#W5>
// <http://www.unicode.org/reports/tr9/#W6> (separators only)
// (see below for W6 terminator code)
//
match processing_classes[i] {
// <http://www.unicode.org/reports/tr9/#W6>
EN => {
// W5. If a run of ETs is adjacent to an EN, change the ETs to EN.
for j in &et_run_indices {
processing_classes[*j] = EN;
}
et_run_indices.clear();
}
// <http://www.unicode.org/reports/tr9/#W4>
// <http://www.unicode.org/reports/tr9/#W6>
ES | CS => {
// See https://github.com/servo/unicode-bidi/issues/86 for improving this.
// We want to make sure we check the correct next character by skipping past the rest
// of this one.
if let Some((_, char_len)) = text.char_at(i) {
let mut next_class = sequence
.iter_forwards_from(i + char_len, run_index)
.map(|j| processing_classes[j])
// <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
.find(not_removed_by_x9)
.unwrap_or(sequence.eos);
if next_class == EN && last_strong_is_al {
// Apply W2 to next_class. We know that last_strong_is_al
// has no chance of changing on this character so we can still assume its value
// will be the same by the time we get to it.
next_class = AN;
}
processing_classes[i] =
match (prev_class_before_w4, processing_classes[i], next_class) {
// W4
(EN, ES, EN) | (EN, CS, EN) => EN,
// W4
(AN, CS, AN) => AN,
// W6 (separators only)
(_, _, _) => ON,
};
// W6 + <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
// We have to do this before W5 gets its grubby hands on these characters and thinks
// they're part of an ET run.
// We check for ON to ensure that we had hit the W6 branch above, since this `ES | CS` match
// arm handles both W4 and W6.
if processing_classes[i] == ON {
for idx in sequence.iter_backwards_from(i, run_index) {
let class = &mut processing_classes[idx];
if *class != BN {
break;
}
*class = ON;
}
for idx in sequence.iter_forwards_from(i + char_len, run_index) {
let class = &mut processing_classes[idx];
if *class != BN {
break;
}
*class = ON;
}
}
} else {
// We're in the middle of a character, copy over work done for previous bytes
// since it's going to be the same answer.
processing_classes[i] = processing_classes[i - 1];
}
}
// <http://www.unicode.org/reports/tr9/#W5>
ET => {
match prev_class_before_w5 {
EN => processing_classes[i] = EN,
_ => {
// <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
// If there was a BN run before this, that's now a part of this ET run.
et_run_indices.extend(bn_run_indices.clone());
// In case this is followed by an EN.
et_run_indices.push(i);
}
}
}
_ => {}
}
// Common loop iteration code
//
// <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
// BN runs would have already continued the loop, clear them before we get to the next one.
bn_run_indices.clear();
// W6 above only deals with separators, so it doesn't change anything W5 cares about,
// so we still can update this after running that part of W6.
prev_class_before_w5 = processing_classes[i];
// <http://www.unicode.org/reports/tr9/#W6> (terminators only)
// (see above for W6 separator code)
//
if prev_class_before_w5 != ET {
// W6. If we didn't find an adjacent EN, turn any ETs into ON instead.
for j in &et_run_indices {
processing_classes[*j] = ON;
}
et_run_indices.clear();
}
// We stashed this before W4/5/6 could get their grubby hands on it, and it's not
// used in the W6 terminator code below so we can update it now.
prev_class_before_w4 = class_before_w456;
}
}
// Rerun this check in case we ended with a sequence of BNs (i.e., we'd never
// hit the end of the for loop above).
// W6. If we didn't find an adjacent EN, turn any ETs into ON instead.
for j in &et_run_indices {
processing_classes[*j] = ON;
}
et_run_indices.clear();
// W7. If the previous strong char was L, change EN to L.
let mut last_strong_is_l = sequence.sos == L;
for i in sequence.runs.iter().cloned().flatten() {
match processing_classes[i] {
EN if last_strong_is_l => {
processing_classes[i] = L;
}
L => {
last_strong_is_l = true;
}
R | AL => {
last_strong_is_l = false;
}
// <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
// Already scanning past BN here.
_ => {}
}
}
}
#[cfg(feature = "smallvec")]
type BracketPairVec = SmallVec<[BracketPair; 8]>;
#[cfg(not(feature = "smallvec"))]
type BracketPairVec = Vec<BracketPair>;
/// 3.3.5 Resolving Neutral Types
///
/// <http://www.unicode.org/reports/tr9/#Resolving_Neutral_Types>
#[cfg_attr(feature = "flame_it", flamer::flame)]
pub fn resolve_neutral<'a, D: BidiDataSource, T: TextSource<'a> + ?Sized>(
text: &'a T,
data_source: &D,
sequence: &IsolatingRunSequence,
levels: &[Level],
original_classes: &[BidiClass],
processing_classes: &mut [BidiClass],
) {
// e = embedding direction
let e: BidiClass = levels[sequence.runs[0].start].bidi_class();
let not_e = if e == BidiClass::L {
BidiClass::R
} else {
BidiClass::L
};
// N0. Process bracket pairs.
// > Identify the bracket pairs in the current isolating run sequence according to BD16.
// We use processing_classes, not original_classes, due to BD14/BD15
let mut bracket_pairs = BracketPairVec::new();
identify_bracket_pairs(
text,
data_source,
sequence,
processing_classes,
&mut bracket_pairs,
);
// > For each bracket-pair element in the list of pairs of text positions
//
// Note: Rust ranges are interpreted as [start..end), be careful using `pair` directly
// for indexing as it will include the opening bracket pair but not the closing one.
for pair in bracket_pairs {
#[cfg(feature = "std")]
debug_assert!(
pair.start < processing_classes.len(),
"identify_bracket_pairs returned a range that is out of bounds!"
);
#[cfg(feature = "std")]
debug_assert!(
pair.end < processing_classes.len(),
"identify_bracket_pairs returned a range that is out of bounds!"
);
let mut found_e = false;
let mut found_not_e = false;
let mut class_to_set = None;
let start_char_len =
T::char_len(text.subrange(pair.start..pair.end).chars().next().unwrap());
// > Inspect the bidirectional types of the characters enclosed within the bracket pair.
//
// `pair` is [start, end) so we will end up processing the opening character but not the closing one.
//
for enclosed_i in sequence.iter_forwards_from(pair.start + start_char_len, pair.start_run) {
if enclosed_i >= pair.end {
#[cfg(feature = "std")]
debug_assert!(
enclosed_i == pair.end,
"If we skipped past this, the iterator is broken"
);
break;
}
let class = processing_classes[enclosed_i];
if class == e {
found_e = true;
} else if class == not_e {
found_not_e = true;
} else if matches!(class, BidiClass::EN | BidiClass::AN) {
// > Within this scope, bidirectional types EN and AN are treated as R.
if e == BidiClass::L {
found_not_e = true;
} else {
found_e = true;
}
}
// If we have found a character with the class of the embedding direction
// we can bail early.
if found_e {
break;
}
}
// > If any strong type (either L or R) matching the embedding direction is found
if found_e {
// > .. set the type for both brackets in the pair to match the embedding direction
class_to_set = Some(e);
// > Otherwise, if there is a strong type it must be opposite the embedding direction
} else if found_not_e {
// > Therefore, test for an established context with a preceding strong type by
// > checking backwards before the opening paired bracket
// > until the first strong type (L, R, or sos) is found.
// (see note above about processing_classes and character boundaries)
let mut previous_strong = sequence
.iter_backwards_from(pair.start, pair.start_run)
.map(|i| processing_classes[i])
.find(|class| {
matches!(
class,
BidiClass::L | BidiClass::R | BidiClass::EN | BidiClass::AN
)
})
.unwrap_or(sequence.sos);
// > Within this scope, bidirectional types EN and AN are treated as R.
if matches!(previous_strong, BidiClass::EN | BidiClass::AN) {
previous_strong = BidiClass::R;
}
// > If the preceding strong type is also opposite the embedding direction,
// > context is established,
// > so set the type for both brackets in the pair to that direction.
// AND
// > Otherwise set the type for both brackets in the pair to the embedding direction.
// > Either way it gets set to previous_strong
//
// Both branches amount to setting the type to the strong type.
class_to_set = Some(previous_strong);
}
if let Some(class_to_set) = class_to_set {
// Update all processing classes corresponding to the start and end elements, as requested.
// We should include all bytes of the character, not the first one.
let end_char_len =
T::char_len(text.subrange(pair.end..text.len()).chars().next().unwrap());
for class in &mut processing_classes[pair.start..pair.start + start_char_len] {
*class = class_to_set;
}
for class in &mut processing_classes[pair.end..pair.end + end_char_len] {
*class = class_to_set;
}
// <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
for idx in sequence.iter_backwards_from(pair.start, pair.start_run) {
let class = &mut processing_classes[idx];
if *class != BN {
break;
}
*class = class_to_set;
}
// > Any number of characters that had original bidirectional character type NSM prior to the application of
// > W1 that immediately follow a paired bracket which changed to L or R under N0 should change to match the type of their preceding bracket.
// This rule deals with sequences of NSMs, so we can just update them all at once, we don't need to worry
// about character boundaries. We do need to be careful to skip the full set of bytes for the parentheses characters.
let nsm_start = pair.start + start_char_len;
for idx in sequence.iter_forwards_from(nsm_start, pair.start_run) {
let class = original_classes[idx];
if class == BidiClass::NSM || processing_classes[idx] == BN {
processing_classes[idx] = class_to_set;
} else {
break;
}
}
let nsm_end = pair.end + end_char_len;
for idx in sequence.iter_forwards_from(nsm_end, pair.end_run) {
let class = original_classes[idx];
if class == BidiClass::NSM || processing_classes[idx] == BN {
processing_classes[idx] = class_to_set;
} else {
break;
}
}
}
// > Otherwise, there are no strong types within the bracket pair
// > Therefore, do not set the type for that bracket pair
}
// N1 and N2.
// Indices of every byte in this isolating run sequence
let mut indices = sequence.runs.iter().flat_map(Clone::clone);
let mut prev_class = sequence.sos;
while let Some(mut i) = indices.next() {
// Process sequences of NI characters.
#[cfg(feature = "smallvec")]
let mut ni_run = SmallVec::<[usize; 8]>::new();
#[cfg(not(feature = "smallvec"))]
let mut ni_run = Vec::new();
// The BN is for <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
if is_NI(processing_classes[i]) || processing_classes[i] == BN {
// Consume a run of consecutive NI characters.
ni_run.push(i);
let mut next_class;
loop {
match indices.next() {
Some(j) => {
i = j;
next_class = processing_classes[j];
// The BN is for <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
if is_NI(next_class) || next_class == BN {
ni_run.push(i);
} else {
break;
}
}
None => {
next_class = sequence.eos;
break;
}
};
}
// N1-N2.
//
// <http://www.unicode.org/reports/tr9/#N1>
// <http://www.unicode.org/reports/tr9/#N2>
let new_class = match (prev_class, next_class) {
(L, L) => L,
(R, R)
| (R, AN)
| (R, EN)
| (AN, R)
| (AN, AN)
| (AN, EN)
| (EN, R)
| (EN, AN)
| (EN, EN) => R,
(_, _) => e,
};
for j in &ni_run {
processing_classes[*j] = new_class;
}
ni_run.clear();
}
prev_class = processing_classes[i];
}
}
struct BracketPair {
/// The text-relative index of the opening bracket.
start: usize,
/// The text-relative index of the closing bracket.
end: usize,
/// The index of the run (in the run sequence) that the opening bracket is in.
start_run: usize,
/// The index of the run (in the run sequence) that the closing bracket is in.
end_run: usize,
}
/// 3.1.3 Identifying Bracket Pairs
///
/// Returns all paired brackets in the source, as indices into the
/// text source.
///
/// <https://www.unicode.org/reports/tr9/#BD16>
fn identify_bracket_pairs<'a, T: TextSource<'a> + ?Sized, D: BidiDataSource>(
text: &'a T,
data_source: &D,
run_sequence: &IsolatingRunSequence,
original_classes: &[BidiClass],
bracket_pairs: &mut BracketPairVec,
) {
#[cfg(feature = "smallvec")]
let mut stack = SmallVec::<[(char, usize, usize); 8]>::new();
#[cfg(not(feature = "smallvec"))]
let mut stack = Vec::new();
for (run_index, level_run) in run_sequence.runs.iter().enumerate() {
for (i, ch) in text.subrange(level_run.clone()).char_indices() {
let actual_index = level_run.start + i;
// All paren characters are ON.
// From BidiBrackets.txt:
// > The Unicode property value stability policy guarantees that characters
// > which have bpt=o or bpt=c also have bc=ON and Bidi_M=Y
if original_classes[actual_index] != BidiClass::ON {
continue;
}
if let Some(matched) = data_source.bidi_matched_opening_bracket(ch) {
if matched.is_open {
// > If an opening paired bracket is found ...
// > ... and there is no room in the stack,
// > stop processing BD16 for the remainder of the isolating run sequence.
if stack.len() >= 63 {
break;
}
// > ... push its Bidi_Paired_Bracket property value and its text position onto the stack
stack.push((matched.opening, actual_index, run_index))
} else {
// > If a closing paired bracket is found, do the following
// > Declare a variable that holds a reference to the current stack element
// > and initialize it with the top element of the stack.
// AND
// > Else, if the current stack element is not at the bottom of the stack
for (stack_index, element) in stack.iter().enumerate().rev() {
// > Compare the closing paired bracket being inspected or its canonical
// > equivalent to the bracket in the current stack element.
if element.0 == matched.opening {
// > If the values match, meaning the two characters form a bracket pair, then
// > Append the text position in the current stack element together with the
// > text position of the closing paired bracket to the list.
let pair = BracketPair {
start: element.1,
end: actual_index,
start_run: element.2,
end_run: run_index,
};
bracket_pairs.push(pair);
// > Pop the stack through the current stack element inclusively.
stack.truncate(stack_index);
break;
}
}
}
}
}
}
// > Sort the list of pairs of text positions in ascending order based on
// > the text position of the opening paired bracket.
bracket_pairs.sort_by_key(|r| r.start);
}
/// 3.3.6 Resolving Implicit Levels
///
/// Returns the maximum embedding level in the paragraph.
///
/// <http://www.unicode.org/reports/tr9/#Resolving_Implicit_Levels>
#[cfg_attr(feature = "flame_it", flamer::flame)]
pub fn resolve_levels(processing_classes: &[BidiClass], levels: &mut [Level]) -> Level {
let mut max_level = Level::ltr();
assert_eq!(processing_classes.len(), levels.len());
for i in 0..levels.len() {
match (levels[i].is_rtl(), processing_classes[i]) {
(false, AN) | (false, EN) => levels[i].raise(2).expect("Level number error"),
(false, R) | (true, L) | (true, EN) | (true, AN) => {
levels[i].raise(1).expect("Level number error")
}
// <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters> handled here
(_, _) => {}
}
max_level = max(max_level, levels[i]);
}
max_level
}
/// Neutral or Isolate formatting character (B, S, WS, ON, FSI, LRI, RLI, PDI)
///
/// <http://www.unicode.org/reports/tr9/#NI>
#[allow(non_snake_case)]
fn is_NI(class: BidiClass) -> bool {
matches!(class, B | S | WS | ON | FSI | LRI | RLI | PDI)
}