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