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, removed_by_x9, IsolatingRunSequence};
18use super::BidiDataSource;
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(
25 text: &str,
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(ch) = text.get(i..).and_then(|s| s.chars().next()) {
124 let mut next_class = sequence
125 .iter_forwards_from(i + ch.len_utf8(), 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 + ch.len_utf8(), 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<D: BidiDataSource>(
252 text: &str,
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_len_utf8 = text[pair.start..].chars().next().unwrap().len_utf8();
292 // > Inspect the bidirectional types of the characters enclosed within the bracket pair.
293 //
294 // `pair` is [start, end) so we will end up processing the opening character but not the closing one.
295 //
296 for enclosed_i in sequence.iter_forwards_from(pair.start + start_len_utf8, pair.start_run) {
297 if enclosed_i >= pair.end {
298 #[cfg(feature = "std")]
299 debug_assert!(
300 enclosed_i == pair.end,
301 "If we skipped past this, the iterator is broken"
302 );
303 break;
304 }
305 let class = processing_classes[enclosed_i];
306 if class == e {
307 found_e = true;
308 } else if class == not_e {
309 found_not_e = true;
310 } else if class == BidiClass::EN || class == BidiClass::AN {
311 // > Within this scope, bidirectional types EN and AN are treated as R.
312 if e == BidiClass::L {
313 found_not_e = true;
314 } else {
315 found_e = true;
316 }
317 }
318
319 // If we have found a character with the class of the embedding direction
320 // we can bail early.
321 if found_e {
322 break;
323 }
324 }
325 // > If any strong type (either L or R) matching the embedding direction is found
326 if found_e {
327 // > .. set the type for both brackets in the pair to match the embedding direction
328 class_to_set = Some(e);
329 // > Otherwise, if there is a strong type it must be opposite the embedding direction
330 } else if found_not_e {
331 // > Therefore, test for an established context with a preceding strong type by
332 // > checking backwards before the opening paired bracket
333 // > until the first strong type (L, R, or sos) is found.
334 // (see note above about processing_classes and character boundaries)
335 let mut previous_strong = sequence
336 .iter_backwards_from(pair.start, pair.start_run)
337 .map(|i| processing_classes[i])
338 .find(|class| {
339 *class == BidiClass::L
340 || *class == BidiClass::R
341 || *class == BidiClass::EN
342 || *class == BidiClass::AN
343 })
344 .unwrap_or(sequence.sos);
345
346 // > Within this scope, bidirectional types EN and AN are treated as R.
347 if previous_strong == BidiClass::EN || previous_strong == BidiClass::AN {
348 previous_strong = BidiClass::R;
349 }
350
351 // > If the preceding strong type is also opposite the embedding direction,
352 // > context is established,
353 // > so set the type for both brackets in the pair to that direction.
354 // AND
355 // > Otherwise set the type for both brackets in the pair to the embedding direction.
356 // > Either way it gets set to previous_strong
357 //
358 // Both branches amount to setting the type to the strong type.
359 class_to_set = Some(previous_strong);
360 }
361
362 if let Some(class_to_set) = class_to_set {
363 // Update all processing classes corresponding to the start and end elements, as requested.
364 // We should include all bytes of the character, not the first one.
365 let end_len_utf8 = text[pair.end..].chars().next().unwrap().len_utf8();
366 for class in &mut processing_classes[pair.start..pair.start + start_len_utf8] {
367 *class = class_to_set;
368 }
369 for class in &mut processing_classes[pair.end..pair.end + end_len_utf8] {
370 *class = class_to_set;
371 }
372 // <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
373 for idx in sequence.iter_backwards_from(pair.start, pair.start_run) {
374 let class = &mut processing_classes[idx];
375 if *class != BN {
376 break;
377 }
378 *class = class_to_set;
379 }
380 // > Any number of characters that had original bidirectional character type NSM prior to the application of
381 // > 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.
382
383 // This rule deals with sequences of NSMs, so we can just update them all at once, we don't need to worry
384 // about character boundaries. We do need to be careful to skip the full set of bytes for the parentheses characters.
385 let nsm_start = pair.start + start_len_utf8;
386 for idx in sequence.iter_forwards_from(nsm_start, pair.start_run) {
387 let class = original_classes[idx];
388 if class == BidiClass::NSM || processing_classes[idx] == BN {
389 processing_classes[idx] = class_to_set;
390 } else {
391 break;
392 }
393 }
394 let nsm_end = pair.end + end_len_utf8;
395 for idx in sequence.iter_forwards_from(nsm_end, pair.end_run) {
396 let class = original_classes[idx];
397 if class == BidiClass::NSM || processing_classes[idx] == BN {
398 processing_classes[idx] = class_to_set;
399 } else {
400 break;
401 }
402 }
403 }
404 // > Otherwise, there are no strong types within the bracket pair
405 // > Therefore, do not set the type for that bracket pair
406 }
407
408 // N1 and N2.
409 // Indices of every byte in this isolating run sequence
410 let mut indices = sequence.runs.iter().flat_map(Clone::clone);
411 let mut prev_class = sequence.sos;
412 while let Some(mut i) = indices.next() {
413 // Process sequences of NI characters.
414 let mut ni_run = Vec::new();
415 // The BN is for <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
416 if is_NI(processing_classes[i]) || processing_classes[i] == BN {
417 // Consume a run of consecutive NI characters.
418 ni_run.push(i);
419 let mut next_class;
420 loop {
421 match indices.next() {
422 Some(j) => {
423 i = j;
424 next_class = processing_classes[j];
425 // The BN is for <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters>
426 if is_NI(next_class) || next_class == BN {
427 ni_run.push(i);
428 } else {
429 break;
430 }
431 }
432 None => {
433 next_class = sequence.eos;
434 break;
435 }
436 };
437 }
438 // N1-N2.
439 //
440 // <http://www.unicode.org/reports/tr9/#N1>
441 // <http://www.unicode.org/reports/tr9/#N2>
442 let new_class = match (prev_class, next_class) {
443 (L, L) => L,
444 (R, R)
445 | (R, AN)
446 | (R, EN)
447 | (AN, R)
448 | (AN, AN)
449 | (AN, EN)
450 | (EN, R)
451 | (EN, AN)
452 | (EN, EN) => R,
453 (_, _) => e,
454 };
455 for j in &ni_run {
456 processing_classes[*j] = new_class;
457 }
458 ni_run.clear();
459 }
460 prev_class = processing_classes[i];
461 }
462}
463
464struct BracketPair {
465 /// The text-relative index of the opening bracket.
466 start: usize,
467 /// The text-relative index of the closing bracket.
468 end: usize,
469 /// The index of the run (in the run sequence) that the opening bracket is in.
470 start_run: usize,
471 /// The index of the run (in the run sequence) that the closing bracket is in.
472 end_run: usize,
473}
474/// 3.1.3 Identifying Bracket Pairs
475///
476/// Returns all paired brackets in the source, as indices into the
477/// text source.
478///
479/// <https://www.unicode.org/reports/tr9/#BD16>
480fn identify_bracket_pairs<D: BidiDataSource>(
481 text: &str,
482 data_source: &D,
483 run_sequence: &IsolatingRunSequence,
484 original_classes: &[BidiClass],
485) -> Vec<BracketPair> {
486 let mut ret = vec![];
487 let mut stack = vec![];
488
489 for (run_index, level_run) in run_sequence.runs.iter().enumerate() {
490 let slice = if let Some(slice) = text.get(level_run.clone()) {
491 slice
492 } else {
493 #[cfg(feature = "std")]
494 std::debug_assert!(
495 false,
496 "Found broken indices in level run: found indices {}..{} for string of length {}",
497 level_run.start,
498 level_run.end,
499 text.len()
500 );
501 return ret;
502 };
503
504 for (i, ch) in slice.char_indices() {
505 let actual_index = level_run.start + i;
506 // All paren characters are ON.
507 // From BidiBrackets.txt:
508 // > The Unicode property value stability policy guarantees that characters
509 // > which have bpt=o or bpt=c also have bc=ON and Bidi_M=Y
510 if original_classes[level_run.start + i] != BidiClass::ON {
511 continue;
512 }
513
514 if let Some(matched) = data_source.bidi_matched_opening_bracket(ch) {
515 if matched.is_open {
516 // > If an opening paired bracket is found ...
517
518 // > ... and there is no room in the stack,
519 // > stop processing BD16 for the remainder of the isolating run sequence.
520 if stack.len() >= 63 {
521 break;
522 }
523 // > ... push its Bidi_Paired_Bracket property value and its text position onto the stack
524 stack.push((matched.opening, actual_index, run_index))
525 } else {
526 // > If a closing paired bracket is found, do the following
527
528 // > Declare a variable that holds a reference to the current stack element
529 // > and initialize it with the top element of the stack.
530 // AND
531 // > Else, if the current stack element is not at the bottom of the stack
532 for (stack_index, element) in stack.iter().enumerate().rev() {
533 // > Compare the closing paired bracket being inspected or its canonical
534 // > equivalent to the bracket in the current stack element.
535 if element.0 == matched.opening {
536 // > If the values match, meaning the two characters form a bracket pair, then
537
538 // > Append the text position in the current stack element together with the
539 // > text position of the closing paired bracket to the list.
540 let pair = BracketPair {
541 start: element.1,
542 end: actual_index,
543 start_run: element.2,
544 end_run: run_index,
545 };
546 ret.push(pair);
547
548 // > Pop the stack through the current stack element inclusively.
549 stack.truncate(stack_index);
550 break;
551 }
552 }
553 }
554 }
555 }
556 }
557 // > Sort the list of pairs of text positions in ascending order based on
558 // > the text position of the opening paired bracket.
559 ret.sort_by_key(|r| r.start);
560 ret
561}
562
563/// 3.3.6 Resolving Implicit Levels
564///
565/// Returns the maximum embedding level in the paragraph.
566///
567/// <http://www.unicode.org/reports/tr9/#Resolving_Implicit_Levels>
568#[cfg_attr(feature = "flame_it", flamer::flame)]
569pub fn resolve_levels(original_classes: &[BidiClass], levels: &mut [Level]) -> Level {
570 let mut max_level: Level = Level::ltr();
571 assert_eq!(original_classes.len(), levels.len());
572 for i: usize in 0..levels.len() {
573 match (levels[i].is_rtl(), original_classes[i]) {
574 (false, AN) | (false, EN) => levels[i].raise(2).expect(msg:"Level number error"),
575 (false, R) | (true, L) | (true, EN) | (true, AN) => {
576 levels[i].raise(1).expect(msg:"Level number error")
577 }
578 // <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters> handled here
579 (_, _) => {}
580 }
581 max_level = max(v1:max_level, v2:levels[i]);
582 }
583
584 max_level
585}
586
587/// Neutral or Isolate formatting character (B, S, WS, ON, FSI, LRI, RLI, PDI)
588///
589/// <http://www.unicode.org/reports/tr9/#NI>
590#[allow(non_snake_case)]
591fn is_NI(class: BidiClass) -> bool {
592 match class {
593 B | S | WS | ON | FSI | LRI | RLI | PDI => true,
594 _ => false,
595 }
596}
597