Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/unicode/bidi.rs

22.0 KiB, 1 run

created by r1870400018:13898, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The bidirectional algorithm, following UAX #9.
2//!
3//! Text that mixes a right to left script with a left to right one is stored in the order it is
4//! read, not the order it is drawn. The algorithm resolves an embedding level for every character,
5//! and from those levels a renderer can put the characters in the order they appear on the line.
6//!
7//! The whole string is taken as one paragraph. A caller with several paragraphs should split them
8//! first, which is rule P1, and resolve each on its own.
9//!
10//! ```
11//! use oxedyne_fe2o3_text::unicode::bidi::{
12//! self,
13//! Direction,
14//! };
15//!
16//! // A Hebrew word between two English ones.
17//! let info = bidi::resolve("a \u{05D0}\u{05D1} b", Direction::Auto);
18//! assert_eq!(info.para_level, 0);
19//! assert_eq!(info.levels[2], 1); // The Hebrew runs right to left.
20//! ```
21
22use crate::unicode::{
23 lookup::{
24 self,
25 Partitioned,
26 },
27 prop::{
28 BidiClass as B,
29 BracketKind,
30 },
31 tables::{
32 bidi::{
33 BRACKET_KEYS,
34 BRACKET_KINDS,
35 BRACKET_PAIRS,
36 },
37 norm::{
38 CANON_KEYS,
39 CANON_OFFS,
40 CANON_POOL,
41 },
42 },
43};
44
45/// The deepest embedding the algorithm allows, from BD2.
46const MAX_DEPTH: u8 = 125;
47
48/// The most bracket pairs BD16 will track before it gives up on the rest of the sequence.
49const MAX_PAIRS: usize = 63;
50
51/// The direction a paragraph is laid out in.
52#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
53pub enum Direction {
54 /// Left to right, whatever the text says.
55 Ltr,
56 /// Right to left, whatever the text says.
57 Rtl,
58 /// Taken from the first strong character, by rules P2 and P3.
59 Auto,
60}
61
62/// The resolved levels of a paragraph.
63#[derive(Clone, Debug)]
64pub struct BidiInfo {
65 /// The embedding level of the paragraph, even for left to right and odd for right to left.
66 pub para_level: u8,
67 /// The embedding level of each character.
68 pub levels: Vec<u8>,
69 /// The Bidi_Class of each character, as it was before the algorithm resolved anything.
70 pub classes: Vec<B>,
71 /// Whether rule X9 removed each character, which is to say whether it is an embedding, an
72 /// override, a pop or a boundary neutral. A renderer draws nothing for these, and their level
73 /// means nothing.
74 pub removed: Vec<bool>,
75 /// The byte offset of each character in the string.
76 pub offsets: Vec<usize>,
77}
78
79impl BidiInfo {
80
81 /// Returns the indices of the characters in the order they are drawn, left to right, leaving
82 /// out the characters that rule X9 removed. This is rule L2.
83 pub fn visual_order(&self) -> Vec<usize> {
84
85 let keep: Vec<usize> = (0..self.levels.len())
86 .filter(|i| !lookup::get(&self.removed, *i, true))
87 .collect();
88
89 let lv: Vec<u8> = keep.iter()
90 .map(|i| lookup::get(&self.levels, *i, self.para_level))
91 .collect();
92
93 let mut order = keep;
94 let hi = lv.iter().copied().max().unwrap_or(self.para_level);
95 let lo = lv.iter()
96 .copied()
97 .filter(|l| l % 2 == 1)
98 .min()
99 .unwrap_or(hi.saturating_add(1));
100
101 // Reverse every run at the deepest level, then at each level above the lowest odd one.
102 let mut level = hi;
103 while level >= lo && level > 0 {
104 let mut i = 0;
105 while i < lv.len() {
106 if lookup::get(&lv, i, 0) >= level {
107 let mut j = i;
108 while j < lv.len() && lookup::get(&lv, j, 0) >= level {
109 j += 1;
110 }
111 order[i..j].reverse();
112 i = j;
113 } else {
114 i += 1;
115 }
116 }
117 level -= 1;
118 }
119
120 order
121 }
122
123 /// Whether any character needs the algorithm at all, which is to say whether the text is not
124 /// simply left to right.
125 pub fn has_rtl(&self) -> bool {
126 self.para_level % 2 == 1 || self.levels.iter().any(|l| l % 2 == 1)
127 }
128}
129
130/// Resolves the embedding levels of `s`, taken as one paragraph.
131pub fn resolve(s: &str, dir: Direction) -> BidiInfo {
132
133 let chars: Vec<char> = s.chars().collect();
134 let offsets: Vec<usize> = s.char_indices().map(|(i, _)| i).collect();
135 let classes: Vec<B> = chars.iter().map(|c| B::of(*c)).collect();
136
137 let para_level = match dir {
138 Direction::Ltr => 0,
139 Direction::Rtl => 1,
140 Direction::Auto => first_strong(&classes, 0, classes.len()),
141 };
142
143 resolve_levels(&chars, &classes, para_level, offsets)
144}
145
146/// Resolves the embedding levels of a sequence whose classes are already known, which is what the
147/// Unicode conformance test gives.
148pub fn resolve_classes(chars: &[char], classes: &[B], dir: Direction) -> BidiInfo {
149
150 let para_level = match dir {
151 Direction::Ltr => 0,
152 Direction::Rtl => 1,
153 Direction::Auto => first_strong(classes, 0, classes.len()),
154 };
155
156 let offsets = (0..chars.len()).collect();
157 resolve_levels(chars, classes, para_level, offsets)
158}
159
160/// Returns the level the first strong character in `cls[from..to]` calls for, skipping anything
161/// inside an isolate. This is rules P2 and P3.
162fn first_strong(cls: &[B], from: usize, to: usize) -> u8 {
163 let mut depth = 0usize;
164 for i in from..to {
165 match lookup::get(cls, i, B::ON) {
166 B::LRI | B::RLI | B::FSI => depth += 1,
167 B::PDI => depth = depth.saturating_sub(1),
168 B::L if depth == 0 => return 0,
169 B::R | B::AL if depth == 0 => return 1,
170 _ => (),
171 }
172 }
173 0
174}
175
176/// Returns the index of the PDI that closes the isolate initiator at `i`, or the length of the
177/// text if there is none. This is rule BD9.
178fn matching_pdi(cls: &[B], i: usize) -> usize {
179 let mut depth = 1usize;
180 for j in (i + 1)..cls.len() {
181 match lookup::get(cls, j, B::ON) {
182 B::LRI | B::RLI | B::FSI => depth += 1,
183 B::PDI => {
184 depth -= 1;
185 if depth == 0 {
186 return j;
187 }
188 },
189 _ => (),
190 }
191 }
192 cls.len()
193}
194
195/// An entry on the directional status stack of rules X1 to X8.
196#[derive(Clone, Copy)]
197struct Status {
198 /// The embedding level the entry establishes.
199 level: u8,
200 /// The direction the entry forces on the characters it covers, if it forces one.
201 over: Option<B>,
202 /// Whether the entry was pushed by an isolate initiator.
203 iso: bool,
204}
205
206/// The whole of the algorithm, once the paragraph level is settled.
207fn resolve_levels(
208 chars: &[char],
209 orig: &[B],
210 para_level: u8,
211 offsets: Vec<usize>,
212)
213 -> BidiInfo
214{
215 let n = orig.len();
216
217 // X1 to X8. The explicit embeddings, overrides and isolates give every character a level, and
218 // take the formatting characters themselves out of the text.
219 let mut levels = vec![para_level; n];
220 let mut cls = orig.to_vec();
221 let mut removed = vec![false; n];
222
223 let mut stack = vec![Status { level: para_level, over: None, iso: false }];
224 let mut overflow_iso = 0usize;
225 let mut overflow_emb = 0usize;
226 let mut valid_iso = 0usize;
227
228 for i in 0..n {
229 let last = match stack.last() {
230 Some(s) => *s,
231 None => Status { level: para_level, over: None, iso: false },
232 };
233 match lookup::get(orig, i, B::ON) {
234
235 // X2 to X5. An embedding or an override raises the level.
236 c @ (B::RLE | B::LRE | B::RLO | B::LRO) => {
237 levels[i] = last.level;
238 removed[i] = true;
239 let rtl = matches!(c, B::RLE | B::RLO);
240 let next = next_level(last.level, rtl);
241 let over = match c {
242 B::RLO => Some(B::R),
243 B::LRO => Some(B::L),
244 _ => None,
245 };
246 if next <= MAX_DEPTH && overflow_iso == 0 && overflow_emb == 0 {
247 stack.push(Status { level: next, over, iso: false });
248 } else if overflow_iso == 0 {
249 overflow_emb += 1;
250 }
251 },
252
253 // X5a, X5b, X5c. An isolate raises the level, but unlike an embedding it stays in the
254 // text and hides its contents from the rules outside it.
255 c @ (B::RLI | B::LRI | B::FSI) => {
256 let rtl = match c {
257 B::RLI => true,
258 B::LRI => false,
259 // X5c. A first strong isolate takes its direction from what it holds.
260 _ => first_strong(orig, i + 1, matching_pdi(orig, i)) == 1,
261 };
262 levels[i] = last.level;
263 if let Some(o) = last.over {
264 cls[i] = o;
265 }
266 let next = next_level(last.level, rtl);
267 if next <= MAX_DEPTH && overflow_iso == 0 && overflow_emb == 0 {
268 valid_iso += 1;
269 stack.push(Status { level: next, over: None, iso: true });
270 } else {
271 overflow_iso += 1;
272 }
273 },
274
275 // X6a. A pop directional isolate closes the nearest isolate that is still open.
276 B::PDI => {
277 if overflow_iso > 0 {
278 overflow_iso -= 1;
279 } else if valid_iso > 0 {
280 overflow_emb = 0;
281 while stack.last().map(|s| !s.iso).unwrap_or(false) {
282 stack.pop();
283 }
284 stack.pop();
285 valid_iso -= 1;
286 }
287 let now = match stack.last() {
288 Some(s) => *s,
289 None => Status { level: para_level, over: None, iso: false },
290 };
291 levels[i] = now.level;
292 if let Some(o) = now.over {
293 cls[i] = o;
294 }
295 },
296
297 // X7. A pop directional format closes the nearest embedding or override.
298 B::PDF => {
299 levels[i] = last.level;
300 removed[i] = true;
301 if overflow_iso > 0 {
302 // An isolate is still open, so this pop belongs to nothing.
303 } else if overflow_emb > 0 {
304 overflow_emb -= 1;
305 } else if !last.iso && stack.len() >= 2 {
306 stack.pop();
307 }
308 },
309
310 // X8. A paragraph separator sits at the paragraph level.
311 B::B => {
312 levels[i] = para_level;
313 },
314
315 // X9. A boundary neutral leaves the text.
316 B::BN => {
317 levels[i] = last.level;
318 removed[i] = true;
319 },
320
321 // X6. Everything else takes the level, and the direction, of the entry it sits under.
322 _ => {
323 levels[i] = last.level;
324 if let Some(o) = last.over {
325 cls[i] = o;
326 }
327 },
328 }
329 }
330
331 // BD13. The characters that survive X9 fall into level runs, and the runs join up across the
332 // isolates that link them into isolating run sequences.
333 let seqs = sequences(orig, &levels, &removed);
334
335 // X10. Each sequence needs to know what lies beyond each of its ends.
336 let mut ends = Vec::with_capacity(seqs.len());
337 for seq in &seqs {
338 ends.push(surrounding(orig, &levels, &removed, seq, para_level));
339 }
340
341 // W, N and I, one sequence at a time. The levels only change at the end, so that the sos and
342 // eos above were all read from the explicit levels.
343 let mut resolved: Vec<(usize, u8)> = Vec::new();
344 for (seq, (sos, eos)) in seqs.iter().zip(ends.iter()) {
345 let level = seq.first()
346 .and_then(|i| levels.get(*i))
347 .copied()
348 .unwrap_or(para_level);
349 let mut sc: Vec<B> = seq.iter()
350 .map(|i| lookup::get(&cls, *i, B::ON))
351 .collect();
352
353 // Rule N0 asks what a character was before W1 changed it, so the classes are kept.
354 let entering = sc.clone();
355 weak(&mut sc, *sos);
356 neutral(chars, seq, &mut sc, &entering, level, *sos, *eos);
357
358 // I1, I2. A run of the opposite direction, or a number, sits one or two levels deeper.
359 for (k, c) in sc.iter().enumerate() {
360 let mut lv = level;
361 if level % 2 == 0 {
362 match c {
363 B::R => lv = level.saturating_add(1),
364 B::AN | B::EN => lv = level.saturating_add(2),
365 _ => (),
366 }
367 } else if matches!(c, B::L | B::EN | B::AN) {
368 lv = level.saturating_add(1);
369 }
370 if let Some(i) = seq.get(k) {
371 resolved.push((*i, lv));
372 }
373 }
374 }
375 for (i, lv) in resolved {
376 if let Some(slot) = levels.get_mut(i) {
377 *slot = lv;
378 }
379 }
380
381 // L1. Separators, and the whitespace that runs up to them or to the end of the paragraph, go
382 // back to the paragraph level.
383 for i in 0..n {
384 if matches!(lookup::get(orig, i, B::ON), B::S | B::B) {
385 levels[i] = para_level;
386 reset_before(orig, &mut levels, &removed, i, para_level);
387 }
388 }
389 reset_before(orig, &mut levels, &removed, n, para_level);
390
391 BidiInfo {
392 para_level,
393 levels,
394 classes: orig.to_vec(),
395 removed,
396 offsets,
397 }
398}
399
400/// Returns the next level above `level` in the given direction, which rules X2 to X5b call the
401/// least odd or least even level greater than it.
402fn next_level(level: u8, rtl: bool) -> u8 {
403 if rtl {
404 (level + 1) | 1
405 } else {
406 (level + 2) & !1
407 }
408}
409
410/// Walks back from `i` over the whitespace and isolate formatting characters, and the characters
411/// X9 removed, putting them back at the paragraph level. This is the second half of rule L1.
412fn reset_before(
413 orig: &[B],
414 levels: &mut [u8],
415 removed: &[bool],
416 i: usize,
417 para_level: u8,
418) {
419 let mut j = i;
420 while j > 0 {
421 j -= 1;
422 if lookup::get(removed, j, false) {
423 levels[j] = para_level;
424 continue;
425 }
426 match lookup::get(orig, j, B::ON) {
427 B::WS | B::LRI | B::RLI | B::FSI | B::PDI => levels[j] = para_level,
428 _ => break,
429 }
430 }
431}
432
433/// Builds the isolating run sequences of rule BD13.
434fn sequences(orig: &[B], levels: &[u8], removed: &[bool]) -> Vec<Vec<usize>> {
435
436 // The characters X9 did not remove, in order.
437 let keep: Vec<usize> = (0..orig.len())
438 .filter(|i| !lookup::get(removed, *i, true))
439 .collect();
440
441 // The level runs: maximal stretches of the surviving characters at one level.
442 let mut runs: Vec<Vec<usize>> = Vec::new();
443 for i in keep {
444 let lv = lookup::get(levels, i, 0);
445 let same = runs.last()
446 .and_then(|r| r.last())
447 .map(|last| lookup::get(levels, *last, 0) == lv)
448 .unwrap_or(false);
449 if same {
450 if let Some(r) = runs.last_mut() {
451 r.push(i);
452 }
453 } else {
454 runs.push(vec![i]);
455 }
456 }
457
458 // A run beginning with a PDI that closes an isolate belongs to the sequence of that isolate,
459 // so it does not begin one of its own.
460 let closes: Vec<bool> = runs.iter()
461 .map(|r| match r.first() {
462 Some(i) => lookup::get(orig, *i, B::ON) == B::PDI && has_initiator(orig, *i),
463 None => false,
464 })
465 .collect();
466
467 let mut seqs = Vec::new();
468 for (r, run) in runs.iter().enumerate() {
469 if lookup::get(&closes, r, false) {
470 continue;
471 }
472 let mut seq = run.clone();
473 let mut k = r;
474 // While the sequence ends on an isolate initiator that is closed somewhere, the run that
475 // begins with its PDI carries on the same sequence.
476 loop {
477 let last = match seq.last() {
478 Some(i) => *i,
479 None => break,
480 };
481 if !matches!(lookup::get(orig, last, B::ON), B::LRI | B::RLI | B::FSI) {
482 break;
483 }
484 let pdi = matching_pdi(orig, last);
485 if pdi >= orig.len() {
486 break;
487 }
488 // Find the run that begins with that PDI.
489 let mut found = None;
490 for (j, run) in runs.iter().enumerate().skip(k + 1) {
491 if run.first() == Some(&pdi) {
492 found = Some(j);
493 break;
494 }
495 }
496 match found {
497 Some(j) => {
498 if let Some(run) = runs.get(j) {
499 seq.extend_from_slice(run);
500 }
501 k = j;
502 },
503 None => break,
504 }
505 }
506 seqs.push(seq);
507 }
508
509 seqs
510}
511
512/// Whether the PDI at `i` closes an isolate initiator.
513fn has_initiator(orig: &[B], i: usize) -> bool {
514 let mut depth = 0usize;
515 let mut j = i;
516 while j > 0 {
517 j -= 1;
518 match lookup::get(orig, j, B::ON) {
519 B::PDI => depth += 1,
520 B::LRI | B::RLI | B::FSI => {
521 if depth == 0 {
522 return true;
523 }
524 depth -= 1;
525 },
526 _ => (),
527 }
528 }
529 false
530}
531
532/// Returns the directions that stand at either end of an isolating run sequence, the sos and eos
533/// of rule X10.
534fn surrounding(
535 orig: &[B],
536 levels: &[u8],
537 removed: &[bool],
538 seq: &[usize],
539 para_level: u8,
540)
541 -> (B, B)
542{
543 let first = seq.first().copied().unwrap_or(0);
544 let last = seq.last().copied().unwrap_or(0);
545 let level = lookup::get(levels, first, para_level);
546
547 // Before the sequence: the nearest surviving character, or the paragraph itself.
548 let mut before = para_level;
549 let mut i = first;
550 while i > 0 {
551 i -= 1;
552 if !lookup::get(removed, i, true) {
553 before = lookup::get(levels, i, para_level);
554 break;
555 }
556 }
557
558 // After it: the same, unless the sequence ends on an isolate that nothing closes, in which
559 // case the paragraph stands beyond it.
560 let mut after = para_level;
561 let open_isolate = matches!(lookup::get(orig, last, B::ON), B::LRI | B::RLI | B::FSI)
562 && matching_pdi(orig, last) >= orig.len();
563 if !open_isolate {
564 for i in (last + 1)..orig.len() {
565 if !lookup::get(removed, i, true) {
566 after = lookup::get(levels, i, para_level);
567 break;
568 }
569 }
570 }
571
572 (dir_of(level.max(before)), dir_of(level.max(after)))
573}
574
575/// Returns the direction an embedding level stands for.
576fn dir_of(level: u8) -> B {
577 if level % 2 == 1 {
578 B::R
579 } else {
580 B::L
581 }
582}
583
584/// Rules W1 to W7, which resolve the weak types of an isolating run sequence in place.
585fn weak(sc: &mut [B], sos: B) {
586
587 let n = sc.len();
588
589 // W1. A nonspacing mark takes the type of what it marks, which for a run of marks is the type
590 // the mark before it has just taken.
591 let mut prev = sos;
592 for i in 0..n {
593 if lookup::get(sc, i, B::ON) == B::NSM {
594 sc[i] = match prev {
595 B::LRI | B::RLI | B::FSI | B::PDI => B::ON,
596 other => other,
597 };
598 }
599 prev = lookup::get(sc, i, B::ON);
600 }
601
602 // W2. A European number after an Arabic letter is an Arabic number.
603 let mut strong = sos;
604 for i in 0..n {
605 match lookup::get(sc, i, B::ON) {
606 B::L | B::R | B::AL => strong = lookup::get(sc, i, B::ON),
607 B::EN if strong == B::AL => sc[i] = B::AN,
608 _ => (),
609 }
610 }
611
612 // W3. An Arabic letter is simply right to left from here on.
613 for i in 0..n {
614 if lookup::get(sc, i, B::ON) == B::AL {
615 sc[i] = B::R;
616 }
617 }
618
619 // W4. A separator between two numbers of a kind joins them.
620 for i in 1..n.saturating_sub(1) {
621 let (a, b, c) = (
622 lookup::get(sc, i - 1, B::ON),
623 lookup::get(sc, i, B::ON),
624 lookup::get(sc, i + 1, B::ON),
625 );
626 if b == B::ES && a == B::EN && c == B::EN {
627 sc[i] = B::EN;
628 } else if b == B::CS && a == c && matches!(a, B::EN | B::AN) {
629 sc[i] = a;
630 }
631 }
632
633 // W5. A run of terminators beside a European number joins it.
634 let mut i = 0;
635 while i < n {
636 if lookup::get(sc, i, B::ON) != B::ET {
637 i += 1;
638 continue;
639 }
640 let mut j = i;
641 while j < n && lookup::get(sc, j, B::ON) == B::ET {
642 j += 1;
643 }
644 let before = i > 0 && lookup::get(sc, i - 1, B::ON) == B::EN;
645 let after = j < n && lookup::get(sc, j, B::ON) == B::EN;
646 if before || after {
647 for k in i..j {
648 sc[k] = B::EN;
649 }
650 }
651 i = j;
652 }
653
654 // W6. The separators and terminators that are left are neutral.
655 for i in 0..n {
656 if matches!(lookup::get(sc, i, B::ON), B::ET | B::ES | B::CS) {
657 sc[i] = B::ON;
658 }
659 }
660
661 // W7. A European number after a left to right character is left to right.
662 let mut strong = sos;
663 for i in 0..n {
664 match lookup::get(sc, i, B::ON) {
665 B::L | B::R => strong = lookup::get(sc, i, B::ON),
666 B::EN if strong == B::L => sc[i] = B::L,
667 _ => (),
668 }
669 }
670}
671
672/// Whether a class is a neutral or an isolate formatting character, the NI of UAX #9.
673fn is_ni(c: B) -> bool {
674 matches!(c, B::B | B::S | B::WS | B::ON | B::FSI | B::LRI | B::RLI | B::PDI)
675}
676
677/// The direction a class stands for when the neutral rules look for a strong one, where a number
678/// counts as right to left.
679fn strength(c: B) -> Option<B> {
680 match c {
681 B::L => Some(B::L),
682 B::R | B::EN | B::AN => Some(B::R),
683 _ => None,
684 }
685}
686
687/// Rules N0 to N2, which resolve the neutral types of an isolating run sequence in place.
688fn neutral(
689 chars: &[char],
690 seq: &[usize],
691 sc: &mut [B],
692 entering: &[B],
693 level: u8,
694 sos: B,
695 eos: B,
696) {
697 let n = sc.len();
698 let e = dir_of(level);
699 let o = if e == B::L { B::R } else { B::L };
700
701 // N0. A bracket pair takes the direction of what it holds, or of what stands before it.
702 for (open, close) in bracket_pairs(chars, seq, sc) {
703
704 let mut inside_e = false;
705 let mut inside_o = false;
706 for k in (open + 1)..close {
707 match strength(lookup::get(sc, k, B::ON)) {
708 Some(s) if s == e => {
709 inside_e = true;
710 break;
711 },
712 Some(_) => inside_o = true,
713 None => (),
714 }
715 }
716
717 let set = if inside_e {
718 Some(e)
719 } else if inside_o {
720 // The direction before the pair decides, and where it is the opposite direction the
721 // brackets follow it rather than the embedding.
722 let mut ctx = sos;
723 let mut k = open;
724 while k > 0 {
725 k -= 1;
726 if let Some(s) = strength(lookup::get(sc, k, B::ON)) {
727 ctx = s;
728 break;
729 }
730 }
731 if ctx == o {
732 Some(o)
733 } else {
734 Some(e)
735 }
736 } else {
737 None
738 };
739
740 if let Some(d) = set {
741 sc[open] = d;
742 sc[close] = d;
743 // A mark that followed a bracket follows it here too.
744 for k in [open, close] {
745 for m in (k + 1)..n {
746 if lookup::get(entering, m, B::ON) != B::NSM {
747 break;
748 }
749 sc[m] = d;
750 }
751 }
752 }
753 }
754
755 // N1. A run of neutrals between two characters of the same direction takes that direction.
756 // N2. Any other run of neutrals takes the direction of the embedding.
757 let mut i = 0;
758 while i < n {
759 if !is_ni(lookup::get(sc, i, B::ON)) {
760 i += 1;
761 continue;
762 }
763 let mut j = i;
764 while j < n && is_ni(lookup::get(sc, j, B::ON)) {
765 j += 1;
766 }
767 let before = if i == 0 {
768 sos
769 } else {
770 strength(lookup::get(sc, i - 1, B::ON)).unwrap_or(e)
771 };
772 let after = if j == n {
773 eos
774 } else {
775 strength(lookup::get(sc, j, B::ON)).unwrap_or(e)
776 };
777 let d = if before == after { before } else { e };
778 for k in i..j {
779 sc[k] = d;
780 }
781 i = j;
782 }
783}
784
785/// Finds the bracket pairs of an isolating run sequence, in the order they open. This is rule
786/// BD16.
787fn bracket_pairs(chars: &[char], seq: &[usize], sc: &[B]) -> Vec<(usize, usize)> {
788
789 let mut stack: Vec<(char, usize)> = Vec::new();
790 let mut pairs: Vec<(usize, usize)> = Vec::new();
791
792 for (k, i) in seq.iter().enumerate() {
793 if lookup::get(sc, k, B::ON) != B::ON {
794 continue;
795 }
796 let c = match chars.get(*i) {
797 Some(c) => *c,
798 None => continue,
799 };
800 match bracket_kind(c) {
801 BracketKind::Open => {
802 if stack.len() >= MAX_PAIRS {
803 // BD16 gives up on the rest of the sequence rather than grow the stack.
804 break;
805 }
806 stack.push((canonical(paired(c)), k));
807 },
808 BracketKind::Close => {
809 let want = canonical(c);
810 for idx in (0..stack.len()).rev() {
811 if let Some((expect, open)) = stack.get(idx) {
812 if *expect == want {
813 pairs.push((*open, k));
814 stack.truncate(idx);
815 break;
816 }
817 }
818 }
819 },
820 BracketKind::None => (),
821 }
822 }
823
824 pairs.sort();
825 pairs
826}
827
828/// Returns the kind of bracket `c` is.
829fn bracket_kind(c: char) -> BracketKind {
830 match lookup::find(&BRACKET_KEYS, c) {
831 Some(i) => match lookup::get(&BRACKET_KINDS, i, 2) {
832 0 => BracketKind::Open,
833 1 => BracketKind::Close,
834 _ => BracketKind::None,
835 },
836 None => BracketKind::None,
837 }
838}
839
840/// Returns the bracket `c` pairs with, or `c` itself if it is not a bracket.
841fn paired(c: char) -> char {
842 match lookup::find(&BRACKET_KEYS, c) {
843 Some(i) => lookup::get(&BRACKET_PAIRS, i, c),
844 None => c,
845 }
846}
847
848/// Returns the character a bracket is canonically equivalent to, so that the two spellings of the
849/// angle brackets pair with each other, as BD16 requires.
850fn canonical(c: char) -> char {
851 match lookup::find(&CANON_KEYS, c) {
852 Some(i) => {
853 let a = lookup::get(&CANON_OFFS, i, 0) as usize;
854 let b = lookup::get(&CANON_OFFS, i + 1, 0) as usize;
855 let seq = lookup::pool(&CANON_POOL, a, b);
856 match seq {
857 [one] => *one,
858 _ => c,
859 }
860 },
861 None => c,
862 }
863}