diff options
| -rw-r--r-- | .cargo_vcs_info.json | 2 | ||||
| -rw-r--r-- | .github/workflows/main.yml | 3 | ||||
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | .rustfmt.toml | 1 | ||||
| -rw-r--r-- | Android.bp | 4 | ||||
| -rw-r--r-- | Cargo.lock | 175 | ||||
| -rw-r--r-- | Cargo.toml | 2 | ||||
| -rw-r--r-- | Cargo.toml.orig | 2 | ||||
| -rw-r--r-- | METADATA | 23 | ||||
| -rw-r--r-- | src/deprecated.rs | 4 | ||||
| -rw-r--r-- | src/explicit.rs | 9 | ||||
| -rw-r--r-- | src/implicit.rs | 57 | ||||
| -rw-r--r-- | src/level.rs | 15 | ||||
| -rw-r--r-- | src/lib.rs | 2125 | ||||
| -rw-r--r-- | src/prepare.rs | 21 | ||||
| -rw-r--r-- | src/utf16.rs | 791 |
16 files changed, 2650 insertions, 585 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index 67b5a63..3db1323 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,6 +1,6 @@ { "git": { - "sha1": "cd1de5d1ddbba789c29b6d69811ef49c820eefd4" + "sha1": "dd8a2cf2f4f843aafc25aa765fca17564738cf36" }, "path_in_vcs": "" }
\ No newline at end of file diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml index 17f92a9..f2a9b5f 100644 --- a/.github/workflows/main.yml +++ b/.github/workflows/main.yml @@ -19,6 +19,9 @@ jobs: toolchain: ${{ matrix.rust }} override: true profile: minimal + - name: Unpin dependencies except on MSRV + if: matrix.rust != '1.36.0' + run: cargo update - uses: actions-rs/cargo@v1 with: command: build @@ -1,4 +1,3 @@ -Cargo.lock /data/ /target/ /*.html diff --git a/.rustfmt.toml b/.rustfmt.toml index 7587a1d..e416686 100644 --- a/.rustfmt.toml +++ b/.rustfmt.toml @@ -1,2 +1 @@ array_width = 80 -brace_style = "SameLineWhere" @@ -43,7 +43,7 @@ rust_library { host_supported: true, crate_name: "unicode_bidi", cargo_env_compat: true, - cargo_pkg_version: "0.3.10", + cargo_pkg_version: "0.3.15", srcs: ["src/lib.rs"], edition: "2018", features: [ @@ -65,7 +65,7 @@ rust_test { host_supported: true, crate_name: "unicode_bidi", cargo_env_compat: true, - cargo_pkg_version: "0.3.10", + cargo_pkg_version: "0.3.15", srcs: ["src/lib.rs"], test_suites: ["general-tests"], auto_gen_config: true, diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..681617d --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,175 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +[[package]] +name = "flame" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "lazy_static 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)", + "serde 1.0.156 (registry+https://github.com/rust-lang/crates.io-index)", + "serde_derive 1.0.156 (registry+https://github.com/rust-lang/crates.io-index)", + "serde_json 1.0.99 (registry+https://github.com/rust-lang/crates.io-index)", + "thread-id 3.3.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "flamer" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "flame 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", + "quote 1.0.30 (registry+https://github.com/rust-lang/crates.io-index)", + "syn 1.0.109 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "itoa" +version = "1.0.9" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "lazy_static" +version = "0.2.11" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "libc" +version = "0.2.149" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "proc-macro2" +version = "1.0.65" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "unicode-ident 1.0.12 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "quote" +version = "1.0.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "proc-macro2 1.0.65 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "redox_syscall" +version = "0.1.57" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "ryu" +version = "1.0.15" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "serde" +version = "1.0.156" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "serde_derive 1.0.156 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "serde_derive" +version = "1.0.156" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "proc-macro2 1.0.65 (registry+https://github.com/rust-lang/crates.io-index)", + "quote 1.0.30 (registry+https://github.com/rust-lang/crates.io-index)", + "syn 1.0.109 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "serde_json" +version = "1.0.99" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "itoa 1.0.9 (registry+https://github.com/rust-lang/crates.io-index)", + "ryu 1.0.15 (registry+https://github.com/rust-lang/crates.io-index)", + "serde 1.0.156 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "serde_test" +version = "1.0.175" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "serde 1.0.156 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "syn" +version = "1.0.109" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "proc-macro2 1.0.65 (registry+https://github.com/rust-lang/crates.io-index)", + "quote 1.0.30 (registry+https://github.com/rust-lang/crates.io-index)", + "unicode-ident 1.0.12 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "thread-id" +version = "3.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "libc 0.2.149 (registry+https://github.com/rust-lang/crates.io-index)", + "redox_syscall 0.1.57 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "unicode-bidi" +version = "0.3.15" +dependencies = [ + "flame 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", + "flamer 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "serde 1.0.156 (registry+https://github.com/rust-lang/crates.io-index)", + "serde_test 1.0.175 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "unicode-ident" +version = "1.0.12" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[metadata] +"checksum flame 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "1fc2706461e1ee94f55cab2ed2e3d34ae9536cfa830358ef80acff1a3dacab30" +"checksum flamer 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "36b732da54fd4ea34452f2431cf464ac7be94ca4b339c9cd3d3d12eb06fe7aab" +"checksum itoa 1.0.9 (registry+https://github.com/rust-lang/crates.io-index)" = "af150ab688ff2122fcef229be89cb50dd66af9e01a4ff320cc137eecc9bacc38" +"checksum lazy_static 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)" = "76f033c7ad61445c5b347c7382dd1237847eb1bce590fe50365dcb33d546be73" +"checksum libc 0.2.149 (registry+https://github.com/rust-lang/crates.io-index)" = "a08173bc88b7955d1b3145aa561539096c421ac8debde8cbc3612ec635fee29b" +"checksum proc-macro2 1.0.65 (registry+https://github.com/rust-lang/crates.io-index)" = "92de25114670a878b1261c79c9f8f729fb97e95bac93f6312f583c60dd6a1dfe" +"checksum quote 1.0.30 (registry+https://github.com/rust-lang/crates.io-index)" = "5907a1b7c277254a8b15170f6e7c97cfa60ee7872a3217663bb81151e48184bb" +"checksum redox_syscall 0.1.57 (registry+https://github.com/rust-lang/crates.io-index)" = "41cc0f7e4d5d4544e8861606a285bb08d3e70712ccc7d2b84d7c0ccfaf4b05ce" +"checksum ryu 1.0.15 (registry+https://github.com/rust-lang/crates.io-index)" = "1ad4cc8da4ef723ed60bced201181d83791ad433213d8c24efffda1eec85d741" +"checksum serde 1.0.156 (registry+https://github.com/rust-lang/crates.io-index)" = "314b5b092c0ade17c00142951e50ced110ec27cea304b1037c6969246c2469a4" +"checksum serde_derive 1.0.156 (registry+https://github.com/rust-lang/crates.io-index)" = "d7e29c4601e36bcec74a223228dce795f4cd3616341a4af93520ca1a837c087d" +"checksum serde_json 1.0.99 (registry+https://github.com/rust-lang/crates.io-index)" = "46266871c240a00b8f503b877622fe33430b3c7d963bdc0f2adc511e54a1eae3" +"checksum serde_test 1.0.175 (registry+https://github.com/rust-lang/crates.io-index)" = "29baf0f77ca9ad9c6ed46e1b408b5e0f30b5184bcd66884e7f6d36bd7a65a8a4" +"checksum syn 1.0.109 (registry+https://github.com/rust-lang/crates.io-index)" = "72b64191b275b66ffe2469e8af2c1cfe3bafa67b529ead792a6d0160888b4237" +"checksum thread-id 3.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c7fbf4c9d56b320106cd64fd024dadfa0be7cb4706725fc44a7d7ce952d820c1" +"checksum unicode-ident 1.0.12 (registry+https://github.com/rust-lang/crates.io-index)" = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" +"checksum winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" +"checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" +"checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" @@ -12,7 +12,7 @@ [package] edition = "2018" name = "unicode-bidi" -version = "0.3.10" +version = "0.3.15" authors = ["The Servo Project Developers"] exclude = [ "benches/**", diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 02bc85b..f3ae311 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -1,6 +1,6 @@ [package] name = "unicode-bidi" -version = "0.3.10" +version = "0.3.15" authors = ["The Servo Project Developers"] license = "MIT OR Apache-2.0" description = "Implementation of the Unicode Bidirectional Algorithm" @@ -1,23 +1,20 @@ # This project was upgraded with external_updater. -# Usage: tools/external_updater/updater.sh update rust/crates/unicode-bidi -# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md +# Usage: tools/external_updater/updater.sh update external/rust/crates/unicode-bidi +# For more info, check https://cs.android.com/android/platform/superproject/+/main:tools/external_updater/README.md name: "unicode-bidi" description: "Implementation of the Unicode Bidirectional Algorithm" third_party { - url { - type: HOMEPAGE - value: "https://crates.io/crates/unicode-bidi" - } - url { - type: ARCHIVE - value: "https://static.crates.io/crates/unicode-bidi/unicode-bidi-0.3.10.crate" - } - version: "0.3.10" license_type: NOTICE last_upgrade_date { - year: 2023 + year: 2024 month: 2 - day: 6 + day: 5 + } + homepage: "https://crates.io/crates/unicode-bidi" + identifier { + type: "Archive" + value: "https://static.crates.io/crates/unicode-bidi/unicode-bidi-0.3.15.crate" + version: "0.3.15" } } diff --git a/src/deprecated.rs b/src/deprecated.rs index ec3b84f..74a24f5 100644 --- a/src/deprecated.rs +++ b/src/deprecated.rs @@ -46,8 +46,8 @@ pub fn visual_runs(line: Range<usize>, levels: &[Level]) -> Vec<LevelRun> { start = i; run_level = new_level; - min_level = min(run_level, min_level); - max_level = max(run_level, max_level); + min_level = cmp::min(run_level, min_level); + max_level = cmp::max(run_level, max_level); } } runs.push(start..line.end); diff --git a/src/explicit.rs b/src/explicit.rs index a9b13e8..d4ad897 100644 --- a/src/explicit.rs +++ b/src/explicit.rs @@ -18,14 +18,15 @@ use super::char_data::{ BidiClass::{self, *}, }; use super::level::Level; +use super::TextSource; /// Compute explicit embedding levels for one paragraph of text (X1-X8). /// /// `processing_classes[i]` must contain the `BidiClass` of the char at byte index `i`, /// for each char in `text`. #[cfg_attr(feature = "flame_it", flamer::flame)] -pub fn compute( - text: &str, +pub fn compute<'a, T: TextSource<'a> + ?Sized>( + text: &'a T, para_level: Level, original_classes: &[BidiClass], levels: &mut [Level], @@ -41,7 +42,7 @@ pub fn compute( let mut overflow_embedding_count = 0u32; let mut valid_isolate_count = 0u32; - for (i, c) in text.char_indices() { + for (i, len) in text.indices_lengths() { match original_classes[i] { // Rules X2-X5c RLE | LRE | RLO | LRO | RLI | LRI | FSI => { @@ -167,7 +168,7 @@ pub fn compute( } // Handle multi-byte characters. - for j in 1..c.len_utf8() { + for j in 1..len { levels[i + j] = levels[i]; processing_classes[i + j] = processing_classes[i]; } diff --git a/src/implicit.rs b/src/implicit.rs index 294af7c..0311053 100644 --- a/src/implicit.rs +++ b/src/implicit.rs @@ -14,15 +14,15 @@ use core::cmp::max; use super::char_data::BidiClass::{self, *}; use super::level::Level; -use super::prepare::{not_removed_by_x9, removed_by_x9, IsolatingRunSequence}; -use super::BidiDataSource; +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( - text: &str, +pub fn resolve_weak<'a, T: TextSource<'a> + ?Sized>( + text: &'a T, sequence: &IsolatingRunSequence, processing_classes: &mut [BidiClass], ) { @@ -120,9 +120,9 @@ pub fn resolve_weak( // 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(ch) = text.get(i..).and_then(|s| s.chars().next()) { + if let Some((_, char_len)) = text.char_at(i) { let mut next_class = sequence - .iter_forwards_from(i + ch.len_utf8(), run_index) + .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) @@ -156,7 +156,7 @@ pub fn resolve_weak( } *class = ON; } - for idx in sequence.iter_forwards_from(i + ch.len_utf8(), run_index) { + for idx in sequence.iter_forwards_from(i + char_len, run_index) { let class = &mut processing_classes[idx]; if *class != BN { break; @@ -248,8 +248,8 @@ pub fn resolve_weak( /// /// <http://www.unicode.org/reports/tr9/#Resolving_Neutral_Types> #[cfg_attr(feature = "flame_it", flamer::flame)] -pub fn resolve_neutral<D: BidiDataSource>( - text: &str, +pub fn resolve_neutral<'a, D: BidiDataSource, T: TextSource<'a> + ?Sized>( + text: &'a T, data_source: &D, sequence: &IsolatingRunSequence, levels: &[Level], @@ -288,12 +288,13 @@ pub fn resolve_neutral<D: BidiDataSource>( let mut found_not_e = false; let mut class_to_set = None; - let start_len_utf8 = text[pair.start..].chars().next().unwrap().len_utf8(); + 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_len_utf8, pair.start_run) { + 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!( @@ -362,11 +363,12 @@ pub fn resolve_neutral<D: BidiDataSource>( 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_len_utf8 = text[pair.end..].chars().next().unwrap().len_utf8(); - for class in &mut processing_classes[pair.start..pair.start + start_len_utf8] { + 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_len_utf8] { + 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> @@ -382,7 +384,7 @@ pub fn resolve_neutral<D: BidiDataSource>( // 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_len_utf8; + 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 { @@ -391,7 +393,7 @@ pub fn resolve_neutral<D: BidiDataSource>( break; } } - let nsm_end = pair.end + end_len_utf8; + 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 { @@ -477,8 +479,8 @@ struct BracketPair { /// text source. /// /// <https://www.unicode.org/reports/tr9/#BD16> -fn identify_bracket_pairs<D: BidiDataSource>( - text: &str, +fn identify_bracket_pairs<'a, T: TextSource<'a> + ?Sized, D: BidiDataSource>( + text: &'a T, data_source: &D, run_sequence: &IsolatingRunSequence, original_classes: &[BidiClass], @@ -487,27 +489,14 @@ fn identify_bracket_pairs<D: BidiDataSource>( let mut stack = vec![]; for (run_index, level_run) in run_sequence.runs.iter().enumerate() { - let slice = if let Some(slice) = text.get(level_run.clone()) { - slice - } else { - #[cfg(feature = "std")] - std::debug_assert!( - false, - "Found broken indices in level run: found indices {}..{} for string of length {}", - level_run.start, - level_run.end, - text.len() - ); - return ret; - }; - - for (i, ch) in slice.char_indices() { + 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[level_run.start + i] != BidiClass::ON { + if original_classes[actual_index] != BidiClass::ON { continue; } diff --git a/src/level.rs b/src/level.rs index f2e0d99..ef4f6d9 100644 --- a/src/level.rs +++ b/src/level.rs @@ -16,6 +16,7 @@ use alloc::string::{String, ToString}; use alloc::vec::Vec; use core::convert::{From, Into}; +use core::slice; use super::char_data::BidiClass; @@ -31,6 +32,7 @@ use super::char_data::BidiClass; /// <http://www.unicode.org/reports/tr9/#BD2> #[derive(Copy, Clone, Debug, Eq, Ord, PartialEq, PartialOrd)] #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +#[repr(transparent)] pub struct Level(u8); pub const LTR_LEVEL: Level = Level(0); @@ -194,6 +196,19 @@ impl Level { pub fn vec(v: &[u8]) -> Vec<Level> { v.iter().map(|&x| x.into()).collect() } + + /// Converts a byte slice to a slice of Levels + /// + /// Does _not_ check if each level is within bounds (`<=` [`MAX_IMPLICIT_DEPTH`]), + /// which is not a requirement for safety but is a requirement for correctness of the algorithm. + pub fn from_slice_unchecked(v: &[u8]) -> &[Level] { + debug_assert_eq!(core::mem::size_of::<u8>(), core::mem::size_of::<Level>()); + unsafe { + // Safety: The two arrays are the same size and layout-compatible since + // Level is `repr(transparent)` over `u8` + slice::from_raw_parts(v as *const [u8] as *const u8 as *const Level, v.len()) + } + } } /// If levels has any RTL (odd) level @@ -65,7 +65,6 @@ //! //! [tr9]: <http://www.unicode.org/reports/tr9/> -#![forbid(unsafe_code)] #![no_std] // We need to link to std to make doc tests work on older Rust versions #[cfg(feature = "std")] @@ -77,6 +76,7 @@ pub mod data_source; pub mod deprecated; pub mod format_chars; pub mod level; +pub mod utf16; mod char_data; mod explicit; @@ -94,13 +94,69 @@ pub use crate::char_data::{bidi_class, HardcodedBidiData}; use alloc::borrow::Cow; use alloc::string::String; use alloc::vec::Vec; -use core::cmp::{max, min}; +use core::char; +use core::cmp; use core::iter::repeat; use core::ops::Range; +use core::str::CharIndices; use crate::format_chars as chars; use crate::BidiClass::*; +/// Trait that abstracts over a text source for use by the bidi algorithms. +/// We implement this for str (UTF-8) and for [u16] (UTF-16, native-endian). +/// (For internal unicode-bidi use; API may be unstable.) +/// This trait is sealed and cannot be implemented for types outside this crate. +pub trait TextSource<'text>: private::Sealed { + type CharIter: Iterator<Item = char>; + type CharIndexIter: Iterator<Item = (usize, char)>; + type IndexLenIter: Iterator<Item = (usize, usize)>; + + /// Return the length of the text in code units. + #[doc(hidden)] + fn len(&self) -> usize; + + /// Get the character at a given code unit index, along with its length in code units. + /// Returns None if index is out of range, or points inside a multi-code-unit character. + /// Returns REPLACEMENT_CHARACTER for any unpaired surrogates in UTF-16. + #[doc(hidden)] + fn char_at(&self, index: usize) -> Option<(char, usize)>; + + /// Return a subrange of the text, indexed by code units. + /// (We don't implement all of the Index trait, just the minimum we use.) + #[doc(hidden)] + fn subrange(&self, range: Range<usize>) -> &Self; + + /// An iterator over the text returning Unicode characters, + /// REPLACEMENT_CHAR for invalid code units. + #[doc(hidden)] + fn chars(&'text self) -> Self::CharIter; + + /// An iterator over the text returning (index, char) tuples, + /// where index is the starting code-unit index of the character, + /// and char is its Unicode value (or REPLACEMENT_CHAR if invalid). + #[doc(hidden)] + fn char_indices(&'text self) -> Self::CharIndexIter; + + /// An iterator over the text returning (index, length) tuples, + /// where index is the starting code-unit index of the character, + /// and length is its length in code units. + #[doc(hidden)] + fn indices_lengths(&'text self) -> Self::IndexLenIter; + + /// Number of code units the given character uses. + #[doc(hidden)] + fn char_len(ch: char) -> usize; +} + +mod private { + pub trait Sealed {} + + // Implement for str and [u16] only. + impl Sealed for str {} + impl Sealed for [u16] {} +} + #[derive(PartialEq, Debug)] pub enum Direction { Ltr, @@ -109,7 +165,7 @@ pub enum Direction { } /// Bidi information about a single paragraph -#[derive(Debug, PartialEq)] +#[derive(Clone, Debug, PartialEq)] pub struct ParagraphInfo { /// The paragraphs boundaries within the text, as byte indices. /// @@ -176,100 +232,192 @@ impl<'text> InitialInfo<'text> { text: &'a str, default_para_level: Option<Level>, ) -> InitialInfo<'a> { - let mut original_classes = Vec::with_capacity(text.len()); + InitialInfoExt::new_with_data_source(data_source, text, default_para_level).base + } +} + +/// Extended version of InitialInfo (not public API). +#[derive(PartialEq, Debug)] +struct InitialInfoExt<'text> { + /// The base InitialInfo for the text, recording its paragraphs and bidi classes. + base: InitialInfo<'text>, + + /// Parallel to base.paragraphs, records whether each paragraph is "pure LTR" that + /// requires no further bidi processing (i.e. there are no RTL characters or bidi + /// control codes present). + pure_ltr: Vec<bool>, +} + +impl<'text> InitialInfoExt<'text> { + /// Find the paragraphs and BidiClasses in a string of text, with a custom [`BidiDataSource`] + /// for Bidi data. If you just wish to use the hardcoded Bidi data, please use [`InitialInfo::new()`] + /// instead (enabled with tbe default `hardcoded-data` Cargo feature) + /// + /// <http://www.unicode.org/reports/tr9/#The_Paragraph_Level> + /// + /// Also sets the class for each First Strong Isolate initiator (FSI) to LRI or RLI if a strong + /// character is found before the matching PDI. If no strong character is found, the class will + /// remain FSI, and it's up to later stages to treat these as LRI when needed. + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn new_with_data_source<'a, D: BidiDataSource>( + data_source: &D, + text: &'a str, + default_para_level: Option<Level>, + ) -> InitialInfoExt<'a> { + let mut paragraphs = Vec::<ParagraphInfo>::new(); + let mut pure_ltr = Vec::<bool>::new(); + let (original_classes, _, _) = compute_initial_info( + data_source, + text, + default_para_level, + Some((&mut paragraphs, &mut pure_ltr)), + ); - // The stack contains the starting byte index for each nested isolate we're inside. - let mut isolate_stack = Vec::new(); - let mut paragraphs = Vec::new(); + InitialInfoExt { + base: InitialInfo { + text, + original_classes, + paragraphs, + }, + pure_ltr, + } + } +} - let mut para_start = 0; - let mut para_level = default_para_level; +/// Implementation of initial-info computation for both BidiInfo and ParagraphBidiInfo. +/// To treat the text as (potentially) multiple paragraphs, the caller should pass the +/// pair of optional outparam arrays to receive the ParagraphInfo and pure-ltr flags +/// for each paragraph. Passing None for split_paragraphs will ignore any paragraph- +/// separator characters in the text, treating it just as a single paragraph. +/// Returns the array of BidiClass values for each code unit of the text, along with +/// the embedding level and pure-ltr flag for the *last* (or only) paragraph. +fn compute_initial_info<'a, D: BidiDataSource, T: TextSource<'a> + ?Sized>( + data_source: &D, + text: &'a T, + default_para_level: Option<Level>, + mut split_paragraphs: Option<(&mut Vec<ParagraphInfo>, &mut Vec<bool>)>, +) -> (Vec<BidiClass>, Level, bool) { + let mut original_classes = Vec::with_capacity(text.len()); + + // The stack contains the starting code unit index for each nested isolate we're inside. + let mut isolate_stack = Vec::new(); + + debug_assert!( + if let Some((ref paragraphs, ref pure_ltr)) = split_paragraphs { + paragraphs.is_empty() && pure_ltr.is_empty() + } else { + true + } + ); - #[cfg(feature = "flame_it")] - flame::start("InitialInfo::new(): iter text.char_indices()"); + let mut para_start = 0; + let mut para_level = default_para_level; + + // Per-paragraph flag: can subsequent processing be skipped? Set to false if any + // RTL characters or bidi control characters are encountered in the paragraph. + let mut is_pure_ltr = true; - for (i, c) in text.char_indices() { - let class = data_source.bidi_class(c); + #[cfg(feature = "flame_it")] + flame::start("compute_initial_info(): iter text.char_indices()"); - #[cfg(feature = "flame_it")] - flame::start("original_classes.extend()"); + for (i, c) in text.char_indices() { + let class = data_source.bidi_class(c); + + #[cfg(feature = "flame_it")] + flame::start("original_classes.extend()"); - original_classes.extend(repeat(class).take(c.len_utf8())); + let len = T::char_len(c); + original_classes.extend(repeat(class).take(len)); - #[cfg(feature = "flame_it")] - flame::end("original_classes.extend()"); + #[cfg(feature = "flame_it")] + flame::end("original_classes.extend()"); - match class { - B => { + match class { + B => { + if let Some((ref mut paragraphs, ref mut pure_ltr)) = split_paragraphs { // P1. Split the text into separate paragraphs. The paragraph separator is kept // with the previous paragraph. - let para_end = i + c.len_utf8(); + let para_end = i + len; paragraphs.push(ParagraphInfo { range: para_start..para_end, // P3. If no character is found in p2, set the paragraph level to zero. level: para_level.unwrap_or(LTR_LEVEL), }); + pure_ltr.push(is_pure_ltr); // Reset state for the start of the next paragraph. para_start = para_end; // TODO: Support defaulting to direction of previous paragraph // // <http://www.unicode.org/reports/tr9/#HL1> para_level = default_para_level; + is_pure_ltr = true; isolate_stack.clear(); } + } - L | R | AL => { - match isolate_stack.last() { - Some(&start) => { - if original_classes[start] == FSI { - // X5c. If the first strong character between FSI and its matching - // PDI is R or AL, treat it as RLI. Otherwise, treat it as LRI. - for j in 0..chars::FSI.len_utf8() { - original_classes[start + j] = - if class == L { LRI } else { RLI }; - } + L | R | AL => { + if class != L { + is_pure_ltr = false; + } + match isolate_stack.last() { + Some(&start) => { + if original_classes[start] == FSI { + // X5c. If the first strong character between FSI and its matching + // PDI is R or AL, treat it as RLI. Otherwise, treat it as LRI. + for j in 0..T::char_len(chars::FSI) { + original_classes[start + j] = if class == L { LRI } else { RLI }; } } + } - None => { - if para_level.is_none() { - // P2. Find the first character of type L, AL, or R, while skipping - // any characters between an isolate initiator and its matching - // PDI. - para_level = Some(if class != L { RTL_LEVEL } else { LTR_LEVEL }); - } + None => { + if para_level.is_none() { + // P2. Find the first character of type L, AL, or R, while skipping + // any characters between an isolate initiator and its matching + // PDI. + para_level = Some(if class != L { RTL_LEVEL } else { LTR_LEVEL }); } } } + } - RLI | LRI | FSI => { - isolate_stack.push(i); - } + AN | LRE | RLE | LRO | RLO => { + is_pure_ltr = false; + } - PDI => { - isolate_stack.pop(); - } + RLI | LRI | FSI => { + is_pure_ltr = false; + isolate_stack.push(i); + } - _ => {} + PDI => { + isolate_stack.pop(); } + + _ => {} } + } + + if let Some((paragraphs, pure_ltr)) = split_paragraphs { if para_start < text.len() { paragraphs.push(ParagraphInfo { range: para_start..text.len(), level: para_level.unwrap_or(LTR_LEVEL), }); + pure_ltr.push(is_pure_ltr); } - assert_eq!(original_classes.len(), text.len()); + debug_assert_eq!(paragraphs.len(), pure_ltr.len()); + } + debug_assert_eq!(original_classes.len(), text.len()); - #[cfg(feature = "flame_it")] - flame::end("InitialInfo::new(): iter text.char_indices()"); + #[cfg(feature = "flame_it")] + flame::end("compute_initial_info(): iter text.char_indices()"); - InitialInfo { - text, - original_classes, - paragraphs, - } - } + ( + original_classes, + para_level.unwrap_or(LTR_LEVEL), + is_pure_ltr, + ) } /// Bidi information of the text. @@ -308,6 +456,7 @@ impl<'text> BidiInfo<'text> { /// TODO: Support auto-RTL base direction #[cfg_attr(feature = "flame_it", flamer::flame)] #[cfg(feature = "hardcoded-data")] + #[inline] pub fn new(text: &str, default_para_level: Option<Level>) -> BidiInfo<'_> { Self::new_with_data_source(&HardcodedBidiData, text, default_para_level) } @@ -326,67 +475,80 @@ impl<'text> BidiInfo<'text> { text: &'a str, default_para_level: Option<Level>, ) -> BidiInfo<'a> { - let InitialInfo { - original_classes, - paragraphs, - .. - } = InitialInfo::new_with_data_source(data_source, text, default_para_level); + let InitialInfoExt { base, pure_ltr, .. } = + InitialInfoExt::new_with_data_source(data_source, text, default_para_level); let mut levels = Vec::<Level>::with_capacity(text.len()); - let mut processing_classes = original_classes.clone(); + let mut processing_classes = base.original_classes.clone(); - for para in ¶graphs { + for (para, is_pure_ltr) in base.paragraphs.iter().zip(pure_ltr.iter()) { let text = &text[para.range.clone()]; - let original_classes = &original_classes[para.range.clone()]; - let processing_classes = &mut processing_classes[para.range.clone()]; + let original_classes = &base.original_classes[para.range.clone()]; - let new_len = levels.len() + para.range.len(); - levels.resize(new_len, para.level); - let levels = &mut levels[para.range.clone()]; - - explicit::compute( + compute_bidi_info_for_para( + data_source, + para, + *is_pure_ltr, text, - para.level, original_classes, - levels, - processing_classes, + &mut processing_classes, + &mut levels, ); - - let sequences = prepare::isolating_run_sequences(para.level, original_classes, levels); - for sequence in &sequences { - implicit::resolve_weak(text, sequence, processing_classes); - implicit::resolve_neutral( - text, - data_source, - sequence, - levels, - original_classes, - processing_classes, - ); - } - implicit::resolve_levels(processing_classes, levels); - - assign_levels_to_removed_chars(para.level, original_classes, levels); } BidiInfo { text, - original_classes, - paragraphs, + original_classes: base.original_classes, + paragraphs: base.paragraphs, levels, } } - /// Re-order a line based on resolved levels and return only the embedding levels, one `Level` - /// per *byte*. + /// Produce the levels for this paragraph as needed for reordering, one level per *byte* + /// in the paragraph. The returned vector includes bytes that are not included + /// in the `line`, but will not adjust them. + /// + /// This runs [Rule L1], you can run + /// [Rule L2] by calling [`Self::reorder_visual()`]. + /// If doing so, you may prefer to use [`Self::reordered_levels_per_char()`] instead + /// to avoid non-byte indices. + /// + /// For an all-in-one reordering solution, consider using [`Self::reorder_visual()`]. + /// + /// [Rule L1]: https://www.unicode.org/reports/tr9/#L1 + /// [Rule L2]: https://www.unicode.org/reports/tr9/#L2 #[cfg_attr(feature = "flame_it", flamer::flame)] pub fn reordered_levels(&self, para: &ParagraphInfo, line: Range<usize>) -> Vec<Level> { - let (levels, _) = self.visual_runs(para, line); + assert!(line.start <= self.levels.len()); + assert!(line.end <= self.levels.len()); + + let mut levels = self.levels.clone(); + let line_classes = &self.original_classes[line.clone()]; + let line_levels = &mut levels[line.clone()]; + + reorder_levels( + line_classes, + line_levels, + self.text.subrange(line), + para.level, + ); + levels } - /// Re-order a line based on resolved levels and return only the embedding levels, one `Level` - /// per *character*. + /// Produce the levels for this paragraph as needed for reordering, one level per *character* + /// in the paragraph. The returned vector includes characters that are not included + /// in the `line`, but will not adjust them. + /// + /// This runs [Rule L1], you can run + /// [Rule L2] by calling [`Self::reorder_visual()`]. + /// If doing so, you may prefer to use [`Self::reordered_levels_per_char()`] instead + /// to avoid non-byte indices. + /// + /// For an all-in-one reordering solution, consider using [`Self::reorder_visual()`]. + /// + /// [Rule L1]: https://www.unicode.org/reports/tr9/#L1 + /// [Rule L2]: https://www.unicode.org/reports/tr9/#L2 #[cfg_attr(feature = "flame_it", flamer::flame)] pub fn reordered_levels_per_char( &self, @@ -398,24 +560,18 @@ impl<'text> BidiInfo<'text> { } /// Re-order a line based on resolved levels and return the line in display order. + /// + /// This does not apply [Rule L3] or [Rule L4] around combining characters or mirroring. + /// + /// [Rule L3]: https://www.unicode.org/reports/tr9/#L3 + /// [Rule L4]: https://www.unicode.org/reports/tr9/#L4 #[cfg_attr(feature = "flame_it", flamer::flame)] pub fn reorder_line(&self, para: &ParagraphInfo, line: Range<usize>) -> Cow<'text, str> { - let (levels, runs) = self.visual_runs(para, line.clone()); - - // If all isolating run sequences are LTR, no reordering is needed - if runs.iter().all(|run| levels[run.start].is_ltr()) { + if !level::has_rtl(&self.levels[line.clone()]) { return self.text[line].into(); } - - let mut result = String::with_capacity(line.len()); - for run in runs { - if levels[run.start].is_rtl() { - result.extend(self.text[run].chars().rev()); - } else { - result.push_str(&self.text[run]); - } - } - result.into() + let (levels, runs) = self.visual_runs(para, line.clone()); + reorder_line(self.text, line, levels, runs) } /// Reorders pre-calculated levels of a sequence of characters. @@ -426,6 +582,14 @@ impl<'text> BidiInfo<'text> { /// /// the index map will result in `indexMap[visualIndex]==logicalIndex`. /// + /// This only runs [Rule L2](http://www.unicode.org/reports/tr9/#L2) as it does not have + /// information about the actual text. + /// + /// Furthermore, if `levels` is an array that is aligned with code units, bytes within a codepoint may be + /// reversed. You may need to fix up the map to deal with this. Alternatively, only pass in arrays where each `Level` + /// is for a single code point. + /// + /// /// # # Example /// ``` /// use unicode_bidi::BidiInfo; @@ -443,57 +607,154 @@ impl<'text> BidiInfo<'text> { /// let levels: Vec<Level> = vec![l0, l0, l0, l1, l1, l1, l2, l2]; /// let index_map = BidiInfo::reorder_visual(&levels); /// assert_eq!(levels.len(), index_map.len()); - /// assert_eq!(index_map, [0, 1, 2, 5, 4, 3, 6, 7]); + /// assert_eq!(index_map, [0, 1, 2, 6, 7, 5, 4, 3]); /// ``` + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[inline] pub fn reorder_visual(levels: &[Level]) -> Vec<usize> { - // Gets the next range - fn next_range(levels: &[level::Level], start_index: usize) -> Range<usize> { - if levels.is_empty() || start_index >= levels.len() { - return start_index..start_index; - } - - let mut end_index = start_index + 1; - while end_index < levels.len() { - if levels[start_index] != levels[end_index] { - return start_index..end_index; - } - end_index += 1; - } - - start_index..end_index - } - - if levels.is_empty() { - return vec![]; - } - let mut result: Vec<usize> = (0..levels.len()).collect(); - - let mut range: Range<usize> = 0..0; - loop { - range = next_range(levels, range.end); - if levels[range.start].is_rtl() { - result[range.clone()].reverse(); - } - - if range.end >= levels.len() { - break; - } - } - - result + reorder_visual(levels) } /// Find the level runs within a line and return them in visual order. /// /// `line` is a range of bytes indices within `levels`. /// + /// The first return value is a vector of levels used by the reordering algorithm, + /// i.e. the result of [Rule L1]. The second return value is a vector of level runs, + /// the result of [Rule L2], showing the visual order that each level run (a run of text with the + /// same level) should be displayed. Within each run, the display order can be checked + /// against the Level vector. + /// + /// This does not handle [Rule L3] (combining characters) or [Rule L4] (mirroring), + /// as that should be handled by the engine using this API. + /// + /// Conceptually, this is the same as running [`Self::reordered_levels()`] followed by + /// [`Self::reorder_visual()`], however it returns the result as a list of level runs instead + /// of producing a level map, since one may wish to deal with the fact that this is operating on + /// byte rather than character indices. + /// /// <http://www.unicode.org/reports/tr9/#Reordering_Resolved_Levels> + /// + /// [Rule L1]: https://www.unicode.org/reports/tr9/#L1 + /// [Rule L2]: https://www.unicode.org/reports/tr9/#L2 + /// [Rule L3]: https://www.unicode.org/reports/tr9/#L3 + /// [Rule L4]: https://www.unicode.org/reports/tr9/#L4 #[cfg_attr(feature = "flame_it", flamer::flame)] + #[inline] pub fn visual_runs( &self, para: &ParagraphInfo, line: Range<usize>, ) -> (Vec<Level>, Vec<LevelRun>) { + let levels = self.reordered_levels(para, line.clone()); + visual_runs_for_line(levels, &line) + } + + /// If processed text has any computed RTL levels + /// + /// This information is usually used to skip re-ordering of text when no RTL level is present + #[inline] + pub fn has_rtl(&self) -> bool { + level::has_rtl(&self.levels) + } +} + +/// Bidi information of text treated as a single paragraph. +/// +/// The `original_classes` and `levels` vectors are indexed by byte offsets into the text. If a +/// character is multiple bytes wide, then its class and level will appear multiple times in these +/// vectors. +#[derive(Debug, PartialEq)] +pub struct ParagraphBidiInfo<'text> { + /// The text + pub text: &'text str, + + /// The BidiClass of the character at each byte in the text. + pub original_classes: Vec<BidiClass>, + + /// The directional embedding level of each byte in the text. + pub levels: Vec<Level>, + + /// The paragraph embedding level. + pub paragraph_level: Level, + + /// Whether the paragraph is purely LTR. + pub is_pure_ltr: bool, +} + +impl<'text> ParagraphBidiInfo<'text> { + /// Determine the bidi embedding level. + /// + /// + /// The `hardcoded-data` Cargo feature (enabled by default) must be enabled to use this. + /// + /// TODO: In early steps, check for special cases that allow later steps to be skipped. like + /// text that is entirely LTR. See the `nsBidi` class from Gecko for comparison. + /// + /// TODO: Support auto-RTL base direction + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[cfg(feature = "hardcoded-data")] + #[inline] + pub fn new(text: &str, default_para_level: Option<Level>) -> ParagraphBidiInfo<'_> { + Self::new_with_data_source(&HardcodedBidiData, text, default_para_level) + } + + /// Determine the bidi embedding level, with a custom [`BidiDataSource`] + /// for Bidi data. If you just wish to use the hardcoded Bidi data, please use [`BidiInfo::new()`] + /// instead (enabled with tbe default `hardcoded-data` Cargo feature). + /// + /// (This is the single-paragraph equivalent of BidiInfo::new_with_data_source, + /// and should be kept in sync with it. + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn new_with_data_source<'a, D: BidiDataSource>( + data_source: &D, + text: &'a str, + default_para_level: Option<Level>, + ) -> ParagraphBidiInfo<'a> { + // Here we could create a ParagraphInitialInfo struct to parallel the one + // used by BidiInfo, but there doesn't seem any compelling reason for it. + let (original_classes, paragraph_level, is_pure_ltr) = + compute_initial_info(data_source, text, default_para_level, None); + + let mut levels = Vec::<Level>::with_capacity(text.len()); + let mut processing_classes = original_classes.clone(); + + let para_info = ParagraphInfo { + range: Range { + start: 0, + end: text.len(), + }, + level: paragraph_level, + }; + + compute_bidi_info_for_para( + data_source, + ¶_info, + is_pure_ltr, + text, + &original_classes, + &mut processing_classes, + &mut levels, + ); + + ParagraphBidiInfo { + text, + original_classes, + levels, + paragraph_level, + is_pure_ltr, + } + } + + /// Produce the levels for this paragraph as needed for reordering, one level per *byte* + /// in the paragraph. The returned vector includes bytes that are not included + /// in the `line`, but will not adjust them. + /// + /// See BidiInfo::reordered_levels for details. + /// + /// (This should be kept in sync with BidiInfo::reordered_levels.) + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reordered_levels(&self, line: Range<usize>) -> Vec<Level> { assert!(line.start <= self.levels.len()); assert!(line.end <= self.levels.len()); @@ -501,120 +762,402 @@ impl<'text> BidiInfo<'text> { let line_classes = &self.original_classes[line.clone()]; let line_levels = &mut levels[line.clone()]; - // Reset some whitespace chars to paragraph level. - // <http://www.unicode.org/reports/tr9/#L1> - let line_str: &str = &self.text[line.clone()]; - let mut reset_from: Option<usize> = Some(0); - let mut reset_to: Option<usize> = None; - let mut prev_level = para.level; - for (i, c) in line_str.char_indices() { - match line_classes[i] { - // Segment separator, Paragraph separator - B | S => { - assert_eq!(reset_to, None); - reset_to = Some(i + c.len_utf8()); - if reset_from == None { - reset_from = Some(i); - } - } - // Whitespace, isolate formatting - WS | FSI | LRI | RLI | PDI => { - if reset_from == None { - reset_from = Some(i); - } - } - // <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters> - // same as above + set the level - RLE | LRE | RLO | LRO | PDF | BN => { - if reset_from == None { - reset_from = Some(i); - } - // also set the level to previous - line_levels[i] = prev_level; - } - _ => { - reset_from = None; - } + reorder_levels( + line_classes, + line_levels, + self.text.subrange(line), + self.paragraph_level, + ); + + levels + } + + /// Produce the levels for this paragraph as needed for reordering, one level per *character* + /// in the paragraph. The returned vector includes characters that are not included + /// in the `line`, but will not adjust them. + /// + /// See BidiInfo::reordered_levels_per_char for details. + /// + /// (This should be kept in sync with BidiInfo::reordered_levels_per_char.) + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reordered_levels_per_char(&self, line: Range<usize>) -> Vec<Level> { + let levels = self.reordered_levels(line); + self.text.char_indices().map(|(i, _)| levels[i]).collect() + } + + /// Re-order a line based on resolved levels and return the line in display order. + /// + /// See BidiInfo::reorder_line for details. + /// + /// (This should be kept in sync with BidiInfo::reorder_line.) + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reorder_line(&self, line: Range<usize>) -> Cow<'text, str> { + if !level::has_rtl(&self.levels[line.clone()]) { + return self.text[line].into(); + } + + let (levels, runs) = self.visual_runs(line.clone()); + + reorder_line(self.text, line, levels, runs) + } + + /// Reorders pre-calculated levels of a sequence of characters. + /// + /// See BidiInfo::reorder_visual for details. + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[inline] + pub fn reorder_visual(levels: &[Level]) -> Vec<usize> { + reorder_visual(levels) + } + + /// Find the level runs within a line and return them in visual order. + /// + /// `line` is a range of bytes indices within `levels`. + /// + /// See BidiInfo::visual_runs for details. + /// + /// (This should be kept in sync with BidiInfo::visual_runs.) + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[inline] + pub fn visual_runs(&self, line: Range<usize>) -> (Vec<Level>, Vec<LevelRun>) { + let levels = self.reordered_levels(line.clone()); + visual_runs_for_line(levels, &line) + } + + /// If processed text has any computed RTL levels + /// + /// This information is usually used to skip re-ordering of text when no RTL level is present + #[inline] + pub fn has_rtl(&self) -> bool { + !self.is_pure_ltr + } + + /// Return the paragraph's Direction (Ltr, Rtl, or Mixed) based on its levels. + #[inline] + pub fn direction(&self) -> Direction { + para_direction(&self.levels) + } +} + +/// Return a line of the text in display order based on resolved levels. +/// +/// `text` the full text passed to the `BidiInfo` or `ParagraphBidiInfo` for analysis +/// `line` a range of byte indices within `text` corresponding to one line +/// `levels` array of `Level` values, with `line`'s levels reordered into visual order +/// `runs` array of `LevelRun`s in visual order +/// +/// (`levels` and `runs` are the result of calling `BidiInfo::visual_runs()` or +/// `ParagraphBidiInfo::visual_runs()` for the line of interest.) +/// +/// Returns: the reordered text of the line. +/// +/// This does not apply [Rule L3] or [Rule L4] around combining characters or mirroring. +/// +/// [Rule L3]: https://www.unicode.org/reports/tr9/#L3 +/// [Rule L4]: https://www.unicode.org/reports/tr9/#L4 +fn reorder_line<'text>( + text: &'text str, + line: Range<usize>, + levels: Vec<Level>, + runs: Vec<LevelRun>, +) -> Cow<'text, str> { + // If all isolating run sequences are LTR, no reordering is needed + if runs.iter().all(|run| levels[run.start].is_ltr()) { + return text[line].into(); + } + + let mut result = String::with_capacity(line.len()); + for run in runs { + if levels[run.start].is_rtl() { + result.extend(text[run].chars().rev()); + } else { + result.push_str(&text[run]); + } + } + result.into() +} + +/// Find the level runs within a line and return them in visual order. +/// +/// `line` is a range of code-unit indices within `levels`. +/// +/// The first return value is a vector of levels used by the reordering algorithm, +/// i.e. the result of [Rule L1]. The second return value is a vector of level runs, +/// the result of [Rule L2], showing the visual order that each level run (a run of text with the +/// same level) should be displayed. Within each run, the display order can be checked +/// against the Level vector. +/// +/// This does not handle [Rule L3] (combining characters) or [Rule L4] (mirroring), +/// as that should be handled by the engine using this API. +/// +/// Conceptually, this is the same as running [`reordered_levels()`] followed by +/// [`reorder_visual()`], however it returns the result as a list of level runs instead +/// of producing a level map, since one may wish to deal with the fact that this is operating on +/// byte rather than character indices. +/// +/// <http://www.unicode.org/reports/tr9/#Reordering_Resolved_Levels> +/// +/// [Rule L1]: https://www.unicode.org/reports/tr9/#L1 +/// [Rule L2]: https://www.unicode.org/reports/tr9/#L2 +/// [Rule L3]: https://www.unicode.org/reports/tr9/#L3 +/// [Rule L4]: https://www.unicode.org/reports/tr9/#L4 +fn visual_runs_for_line(levels: Vec<Level>, line: &Range<usize>) -> (Vec<Level>, Vec<LevelRun>) { + // Find consecutive level runs. + let mut runs = Vec::new(); + let mut start = line.start; + let mut run_level = levels[start]; + let mut min_level = run_level; + let mut max_level = run_level; + + for (i, &new_level) in levels.iter().enumerate().take(line.end).skip(start + 1) { + if new_level != run_level { + // End of the previous run, start of a new one. + runs.push(start..i); + start = i; + run_level = new_level; + min_level = cmp::min(run_level, min_level); + max_level = cmp::max(run_level, max_level); + } + } + runs.push(start..line.end); + + let run_count = runs.len(); + + // Re-order the odd runs. + // <http://www.unicode.org/reports/tr9/#L2> + + // Stop at the lowest *odd* level. + min_level = min_level.new_lowest_ge_rtl().expect("Level error"); + // This loop goes through contiguous chunks of level runs that have a level + // ≥ max_level and reverses their contents, reducing max_level by 1 each time. + while max_level >= min_level { + // Look for the start of a sequence of consecutive runs of max_level or higher. + let mut seq_start = 0; + while seq_start < run_count { + if levels[runs[seq_start].start] < max_level { + seq_start += 1; + continue; } - if let (Some(from), Some(to)) = (reset_from, reset_to) { - for level in &mut line_levels[from..to] { - *level = para.level; + + // Found the start of a sequence. Now find the end. + let mut seq_end = seq_start + 1; + while seq_end < run_count { + if levels[runs[seq_end].start] < max_level { + break; } - reset_from = None; - reset_to = None; + seq_end += 1; } - prev_level = line_levels[i]; + // Reverse the runs within this sequence. + runs[seq_start..seq_end].reverse(); + + seq_start = seq_end; } - if let Some(from) = reset_from { - for level in &mut line_levels[from..] { - *level = para.level; + max_level + .lower(1) + .expect("Lowering embedding level below zero"); + } + (levels, runs) +} + +/// Reorders pre-calculated levels of a sequence of characters. +/// +/// NOTE: This is a convenience method that does not use a `Paragraph` object. It is +/// intended to be used when an application has determined the levels of the objects (character sequences) +/// and just needs to have them reordered. +/// +/// the index map will result in `indexMap[visualIndex]==logicalIndex`. +/// +/// This only runs [Rule L2](http://www.unicode.org/reports/tr9/#L2) as it does not have +/// information about the actual text. +/// +/// Furthermore, if `levels` is an array that is aligned with code units, bytes within a codepoint may be +/// reversed. You may need to fix up the map to deal with this. Alternatively, only pass in arrays where each `Level` +/// is for a single code point. +fn reorder_visual(levels: &[Level]) -> Vec<usize> { + // Gets the next range of characters after start_index with a level greater + // than or equal to `max` + fn next_range(levels: &[level::Level], mut start_index: usize, max: Level) -> Range<usize> { + if levels.is_empty() || start_index >= levels.len() { + return start_index..start_index; + } + while let Some(l) = levels.get(start_index) { + if *l >= max { + break; } + start_index += 1; } - // Find consecutive level runs. - let mut runs = Vec::new(); - let mut start = line.start; - let mut run_level = levels[start]; - let mut min_level = run_level; - let mut max_level = run_level; - - for (i, &new_level) in levels.iter().enumerate().take(line.end).skip(start + 1) { - if new_level != run_level { - // End of the previous run, start of a new one. - runs.push(start..i); - start = i; - run_level = new_level; - min_level = min(run_level, min_level); - max_level = max(run_level, max_level); + if levels.get(start_index).is_none() { + // If at the end of the array, adding one will + // produce an out-of-range end element + return start_index..start_index; + } + + let mut end_index = start_index + 1; + while let Some(l) = levels.get(end_index) { + if *l < max { + return start_index..end_index; } + end_index += 1; } - runs.push(start..line.end); - let run_count = runs.len(); + start_index..end_index + } - // Re-order the odd runs. - // <http://www.unicode.org/reports/tr9/#L2> + // This implementation is similar to the L2 implementation in `visual_runs()` + // but it cannot benefit from a precalculated LevelRun vector so needs to be different. - // Stop at the lowest *odd* level. - min_level = min_level.new_lowest_ge_rtl().expect("Level error"); + if levels.is_empty() { + return vec![]; + } - while max_level >= min_level { - // Look for the start of a sequence of consecutive runs of max_level or higher. - let mut seq_start = 0; - while seq_start < run_count { - if self.levels[runs[seq_start].start] < max_level { - seq_start += 1; - continue; - } + // Get the min and max levels + let (mut min, mut max) = levels + .iter() + .fold((levels[0], levels[0]), |(min, max), &l| { + (cmp::min(min, l), cmp::max(max, l)) + }); - // Found the start of a sequence. Now find the end. - let mut seq_end = seq_start + 1; - while seq_end < run_count { - if self.levels[runs[seq_end].start] < max_level { - break; - } - seq_end += 1; - } + // Initialize an index map + let mut result: Vec<usize> = (0..levels.len()).collect(); - // Reverse the runs within this sequence. - runs[seq_start..seq_end].reverse(); + if min == max && min.is_ltr() { + // Everything is LTR and at the same level, do nothing + return result; + } + + // Stop at the lowest *odd* level, since everything below that + // is LTR and does not need further reordering + min = min.new_lowest_ge_rtl().expect("Level error"); + + // For each max level, take all contiguous chunks of + // levels ≥ max and reverse them + // + // We can do this check with the original levels instead of checking reorderings because all + // prior reorderings will have been for contiguous chunks of levels >> max, which will + // be a subset of these chunks anyway. + while min <= max { + let mut range = 0..0; + loop { + range = next_range(levels, range.end, max); + result[range.clone()].reverse(); - seq_start = seq_end; + if range.end >= levels.len() { + break; } - max_level - .lower(1) - .expect("Lowering embedding level below zero"); } - (levels, runs) + max.lower(1).expect("Level error"); } - /// If processed text has any computed RTL levels - /// - /// This information is usually used to skip re-ordering of text when no RTL level is present - #[inline] - pub fn has_rtl(&self) -> bool { - level::has_rtl(&self.levels) + result +} + +/// The core of BidiInfo initialization, factored out into a function that both +/// the utf-8 and utf-16 versions of BidiInfo can use. +fn compute_bidi_info_for_para<'a, D: BidiDataSource, T: TextSource<'a> + ?Sized>( + data_source: &D, + para: &ParagraphInfo, + is_pure_ltr: bool, + text: &'a T, + original_classes: &[BidiClass], + processing_classes: &mut [BidiClass], + levels: &mut Vec<Level>, +) { + let new_len = levels.len() + para.range.len(); + levels.resize(new_len, para.level); + if para.level == LTR_LEVEL && is_pure_ltr { + return; + } + + let processing_classes = &mut processing_classes[para.range.clone()]; + let levels = &mut levels[para.range.clone()]; + + explicit::compute( + text, + para.level, + original_classes, + levels, + processing_classes, + ); + + let sequences = prepare::isolating_run_sequences(para.level, original_classes, levels); + for sequence in &sequences { + implicit::resolve_weak(text, sequence, processing_classes); + implicit::resolve_neutral( + text, + data_source, + sequence, + levels, + original_classes, + processing_classes, + ); + } + implicit::resolve_levels(processing_classes, levels); + + assign_levels_to_removed_chars(para.level, original_classes, levels); +} + +/// Produce the levels for this paragraph as needed for reordering, one level per *code unit* +/// in the paragraph. The returned vector includes code units that are not included +/// in the `line`, but will not adjust them. +/// +/// This runs [Rule L1] +/// +/// [Rule L1]: https://www.unicode.org/reports/tr9/#L1 +fn reorder_levels<'a, T: TextSource<'a> + ?Sized>( + line_classes: &[BidiClass], + line_levels: &mut [Level], + line_text: &'a T, + para_level: Level, +) { + // Reset some whitespace chars to paragraph level. + // <http://www.unicode.org/reports/tr9/#L1> + let mut reset_from: Option<usize> = Some(0); + let mut reset_to: Option<usize> = None; + let mut prev_level = para_level; + for (i, c) in line_text.char_indices() { + match line_classes[i] { + // Segment separator, Paragraph separator + B | S => { + assert_eq!(reset_to, None); + reset_to = Some(i + T::char_len(c)); + if reset_from == None { + reset_from = Some(i); + } + } + // Whitespace, isolate formatting + WS | FSI | LRI | RLI | PDI => { + if reset_from == None { + reset_from = Some(i); + } + } + // <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters> + // same as above + set the level + RLE | LRE | RLO | LRO | PDF | BN => { + if reset_from == None { + reset_from = Some(i); + } + // also set the level to previous + line_levels[i] = prev_level; + } + _ => { + reset_from = None; + } + } + if let (Some(from), Some(to)) = (reset_from, reset_to) { + for level in &mut line_levels[from..to] { + *level = para_level; + } + reset_from = None; + reset_to = None; + } + prev_level = line_levels[i]; + } + if let Some(from) = reset_from { + for level in &mut line_levels[from..] { + *level = para_level; + } } } @@ -628,40 +1171,51 @@ pub struct Paragraph<'a, 'text> { } impl<'a, 'text> Paragraph<'a, 'text> { + #[inline] pub fn new(info: &'a BidiInfo<'text>, para: &'a ParagraphInfo) -> Paragraph<'a, 'text> { Paragraph { info, para } } /// Returns if the paragraph is Left direction, right direction or mixed. + #[inline] pub fn direction(&self) -> Direction { - let mut ltr = false; - let mut rtl = false; - for i in self.para.range.clone() { - if self.info.levels[i].is_ltr() { - ltr = true; - } + para_direction(&self.info.levels[self.para.range.clone()]) + } - if self.info.levels[i].is_rtl() { - rtl = true; - } - } + /// Returns the `Level` of a certain character in the paragraph. + #[inline] + pub fn level_at(&self, pos: usize) -> Level { + let actual_position = self.para.range.start + pos; + self.info.levels[actual_position] + } +} - if ltr && rtl { - return Direction::Mixed; +/// Return the directionality of the paragraph (Left, Right or Mixed) from its levels. +#[cfg_attr(feature = "flame_it", flamer::flame)] +fn para_direction(levels: &[Level]) -> Direction { + let mut ltr = false; + let mut rtl = false; + for level in levels { + if level.is_ltr() { + ltr = true; + if rtl { + return Direction::Mixed; + } } - if ltr { - return Direction::Ltr; + if level.is_rtl() { + rtl = true; + if ltr { + return Direction::Mixed; + } } - - Direction::Rtl } - /// Returns the `Level` of a certain character in the paragraph. - pub fn level_at(&self, pos: usize) -> Level { - let actual_position = self.para.range.start + pos; - self.info.levels[actual_position] + if ltr { + return Direction::Ltr; } + + Direction::Rtl } /// Assign levels to characters removed by rule X9. @@ -677,46 +1231,256 @@ fn assign_levels_to_removed_chars(para_level: Level, classes: &[BidiClass], leve } } +/// Get the base direction of the text provided according to the Unicode Bidirectional Algorithm. +/// +/// See rules P2 and P3. +/// +/// The base direction is derived from the first character in the string with bidi character type +/// L, R, or AL. If the first such character has type L, Direction::Ltr is returned. If the first +/// such character has type R or AL, Direction::Rtl is returned. +/// +/// If the string does not contain any character of these types (outside of embedded isolate runs), +/// then Direction::Mixed is returned (but should be considered as meaning "neutral" or "unknown", +/// not in fact mixed directions). +/// +/// This is a lightweight function for use when only the base direction is needed and no further +/// bidi processing of the text is needed. +/// +/// If the text contains paragraph separators, this function considers only the first paragraph. +#[cfg(feature = "hardcoded-data")] +#[inline] +pub fn get_base_direction<'a, T: TextSource<'a> + ?Sized>(text: &'a T) -> Direction { + get_base_direction_with_data_source(&HardcodedBidiData, text) +} + +/// Get the base direction of the text provided according to the Unicode Bidirectional Algorithm, +/// considering the full text if the first paragraph is all-neutral. +/// +/// This is the same as get_base_direction except that it does not stop at the first block +/// separator, but just resets the embedding level and continues to look for a strongly- +/// directional character. So the result will be the base direction of the first paragraph +/// that is not purely neutral characters. +#[cfg(feature = "hardcoded-data")] +#[inline] +pub fn get_base_direction_full<'a, T: TextSource<'a> + ?Sized>(text: &'a T) -> Direction { + get_base_direction_full_with_data_source(&HardcodedBidiData, text) +} + +#[inline] +pub fn get_base_direction_with_data_source<'a, D: BidiDataSource, T: TextSource<'a> + ?Sized>( + data_source: &D, + text: &'a T, +) -> Direction { + get_base_direction_impl(data_source, text, false) +} + +#[inline] +pub fn get_base_direction_full_with_data_source< + 'a, + D: BidiDataSource, + T: TextSource<'a> + ?Sized, +>( + data_source: &D, + text: &'a T, +) -> Direction { + get_base_direction_impl(data_source, text, true) +} + +fn get_base_direction_impl<'a, D: BidiDataSource, T: TextSource<'a> + ?Sized>( + data_source: &D, + text: &'a T, + use_full_text: bool, +) -> Direction { + let mut isolate_level = 0; + for c in text.chars() { + match data_source.bidi_class(c) { + LRI | RLI | FSI => isolate_level = isolate_level + 1, + PDI if isolate_level > 0 => isolate_level = isolate_level - 1, + L if isolate_level == 0 => return Direction::Ltr, + R | AL if isolate_level == 0 => return Direction::Rtl, + B if !use_full_text => break, + B if use_full_text => isolate_level = 0, + _ => (), + } + } + // If no strong char was found, return Mixed. Normally this will be treated as Ltr by callers + // (see rule P3), but we don't map this to Ltr here so that a caller that wants to apply other + // heuristics to an all-neutral paragraph can tell the difference. + Direction::Mixed +} + +/// Implementation of TextSource for UTF-8 text (a string slice). +impl<'text> TextSource<'text> for str { + type CharIter = core::str::Chars<'text>; + type CharIndexIter = core::str::CharIndices<'text>; + type IndexLenIter = Utf8IndexLenIter<'text>; + + #[inline] + fn len(&self) -> usize { + (self as &str).len() + } + #[inline] + fn char_at(&self, index: usize) -> Option<(char, usize)> { + if let Some(slice) = self.get(index..) { + if let Some(ch) = slice.chars().next() { + return Some((ch, ch.len_utf8())); + } + } + None + } + #[inline] + fn subrange(&self, range: Range<usize>) -> &Self { + &(self as &str)[range] + } + #[inline] + fn chars(&'text self) -> Self::CharIter { + (self as &str).chars() + } + #[inline] + fn char_indices(&'text self) -> Self::CharIndexIter { + (self as &str).char_indices() + } + #[inline] + fn indices_lengths(&'text self) -> Self::IndexLenIter { + Utf8IndexLenIter::new(&self) + } + #[inline] + fn char_len(ch: char) -> usize { + ch.len_utf8() + } +} + +/// Iterator over (UTF-8) string slices returning (index, char_len) tuple. +#[derive(Debug)] +pub struct Utf8IndexLenIter<'text> { + iter: CharIndices<'text>, +} + +impl<'text> Utf8IndexLenIter<'text> { + #[inline] + pub fn new(text: &'text str) -> Self { + Utf8IndexLenIter { + iter: text.char_indices(), + } + } +} + +impl Iterator for Utf8IndexLenIter<'_> { + type Item = (usize, usize); + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + if let Some((pos, ch)) = self.iter.next() { + return Some((pos, ch.len_utf8())); + } + None + } +} + +#[cfg(test)] +fn to_utf16(s: &str) -> Vec<u16> { + s.encode_utf16().collect() +} + #[cfg(test)] #[cfg(feature = "hardcoded-data")] mod tests { use super::*; + use utf16::{ + BidiInfo as BidiInfoU16, InitialInfo as InitialInfoU16, Paragraph as ParagraphU16, + ParagraphBidiInfo as ParagraphBidiInfoU16, + }; + + #[test] + fn test_utf16_text_source() { + let text: &[u16] = + &[0x41, 0xD801, 0xDC01, 0x20, 0xD800, 0x20, 0xDFFF, 0x20, 0xDC00, 0xD800]; + assert_eq!(text.char_at(0), Some(('A', 1))); + assert_eq!(text.char_at(1), Some(('\u{10401}', 2))); + assert_eq!(text.char_at(2), None); + assert_eq!(text.char_at(3), Some((' ', 1))); + assert_eq!(text.char_at(4), Some((char::REPLACEMENT_CHARACTER, 1))); + assert_eq!(text.char_at(5), Some((' ', 1))); + assert_eq!(text.char_at(6), Some((char::REPLACEMENT_CHARACTER, 1))); + assert_eq!(text.char_at(7), Some((' ', 1))); + assert_eq!(text.char_at(8), Some((char::REPLACEMENT_CHARACTER, 1))); + assert_eq!(text.char_at(9), Some((char::REPLACEMENT_CHARACTER, 1))); + assert_eq!(text.char_at(10), None); + } + + #[test] + fn test_utf16_char_iter() { + let text: &[u16] = + &[0x41, 0xD801, 0xDC01, 0x20, 0xD800, 0x20, 0xDFFF, 0x20, 0xDC00, 0xD800]; + assert_eq!(text.len(), 10); + assert_eq!(text.chars().count(), 9); + let mut chars = text.chars(); + assert_eq!(chars.next(), Some('A')); + assert_eq!(chars.next(), Some('\u{10401}')); + assert_eq!(chars.next(), Some(' ')); + assert_eq!(chars.next(), Some('\u{FFFD}')); + assert_eq!(chars.next(), Some(' ')); + assert_eq!(chars.next(), Some('\u{FFFD}')); + assert_eq!(chars.next(), Some(' ')); + assert_eq!(chars.next(), Some('\u{FFFD}')); + assert_eq!(chars.next(), Some('\u{FFFD}')); + assert_eq!(chars.next(), None); + } + #[test] fn test_initial_text_info() { - let text = "a1"; - assert_eq!( - InitialInfo::new(text, None), - InitialInfo { - text, - original_classes: vec![L, EN], - paragraphs: vec![ParagraphInfo { + let tests = vec![ + ( + // text + "a1", + // expected bidi classes per utf-8 byte + vec![L, EN], + // expected paragraph-info for utf-8 + vec![ParagraphInfo { range: 0..2, level: LTR_LEVEL, - },], - } - ); - - let text = "غ א"; - assert_eq!( - InitialInfo::new(text, None), - InitialInfo { - text, - original_classes: vec![AL, AL, WS, R, R], - paragraphs: vec![ParagraphInfo { + }], + // expected bidi classes per utf-16 code unit + vec![L, EN], + // expected paragraph-info for utf-16 + vec![ParagraphInfo { + range: 0..2, + level: LTR_LEVEL, + }], + ), + ( + // Arabic, space, Hebrew + "\u{0639} \u{05D0}", + vec![AL, AL, WS, R, R], + vec![ParagraphInfo { range: 0..5, level: RTL_LEVEL, - },], - } - ); - - let text = "a\u{2029}b"; - assert_eq!( - InitialInfo::new(text, None), - InitialInfo { - text, - original_classes: vec![L, B, B, B, L], - paragraphs: vec![ + }], + vec![AL, WS, R], + vec![ParagraphInfo { + range: 0..3, + level: RTL_LEVEL, + }], + ), + ( + // SMP characters from Kharoshthi, Cuneiform, Adlam: + "\u{10A00}\u{12000}\u{1E900}", + vec![R, R, R, R, L, L, L, L, R, R, R, R], + vec![ParagraphInfo { + range: 0..12, + level: RTL_LEVEL, + }], + vec![R, R, L, L, R, R], + vec![ParagraphInfo { + range: 0..6, + level: RTL_LEVEL, + }], + ), + ( + "a\u{2029}b", + vec![L, B, B, B, L], + vec![ ParagraphInfo { range: 0..4, level: LTR_LEVEL, @@ -726,114 +1490,168 @@ mod tests { level: LTR_LEVEL, }, ], - } - ); - - let text = format!("{}א{}a", chars::FSI, chars::PDI); - assert_eq!( - InitialInfo::new(&text, None), - InitialInfo { - text: &text, - original_classes: vec![RLI, RLI, RLI, R, R, PDI, PDI, PDI, L], - paragraphs: vec![ParagraphInfo { + vec![L, B, L], + vec![ + ParagraphInfo { + range: 0..2, + level: LTR_LEVEL, + }, + ParagraphInfo { + range: 2..3, + level: LTR_LEVEL, + }, + ], + ), + ( + "\u{2068}א\u{2069}a", // U+2068 FSI, U+2069 PDI + vec![RLI, RLI, RLI, R, R, PDI, PDI, PDI, L], + vec![ParagraphInfo { range: 0..9, level: LTR_LEVEL, - },], - } - ); + }], + vec![RLI, R, PDI, L], + vec![ParagraphInfo { + range: 0..4, + level: LTR_LEVEL, + }], + ), + ]; + + for t in tests { + assert_eq!( + InitialInfo::new(t.0, None), + InitialInfo { + text: t.0, + original_classes: t.1, + paragraphs: t.2, + } + ); + let text = &to_utf16(t.0); + assert_eq!( + InitialInfoU16::new(text, None), + InitialInfoU16 { + text, + original_classes: t.3, + paragraphs: t.4, + } + ); + } } #[test] #[cfg(feature = "hardcoded-data")] fn test_process_text() { - let text = "abc123"; - assert_eq!( - BidiInfo::new(text, Some(LTR_LEVEL)), - BidiInfo { - text, - levels: Level::vec(&[0, 0, 0, 0, 0, 0]), - original_classes: vec![L, L, L, EN, EN, EN], - paragraphs: vec![ParagraphInfo { + let tests = vec![ + ( + // text + "abc123", + // base level + Some(LTR_LEVEL), + // levels + Level::vec(&[0, 0, 0, 0, 0, 0]), + // original_classes + vec![L, L, L, EN, EN, EN], + // paragraphs + vec![ParagraphInfo { range: 0..6, level: LTR_LEVEL, - },], - } - ); - - let text = "abc אבג"; - assert_eq!( - BidiInfo::new(text, Some(LTR_LEVEL)), - BidiInfo { - text, - levels: Level::vec(&[0, 0, 0, 0, 1, 1, 1, 1, 1, 1]), - original_classes: vec![L, L, L, WS, R, R, R, R, R, R], - paragraphs: vec![ParagraphInfo { + }], + // levels_u16 + Level::vec(&[0, 0, 0, 0, 0, 0]), + // original_classes_u16 + vec![L, L, L, EN, EN, EN], + // paragraphs_u16 + vec![ParagraphInfo { + range: 0..6, + level: LTR_LEVEL, + }], + ), + ( + "abc \u{05D0}\u{05D1}\u{05D2}", + Some(LTR_LEVEL), + Level::vec(&[0, 0, 0, 0, 1, 1, 1, 1, 1, 1]), + vec![L, L, L, WS, R, R, R, R, R, R], + vec![ParagraphInfo { range: 0..10, level: LTR_LEVEL, - },], - } - ); - assert_eq!( - BidiInfo::new(text, Some(RTL_LEVEL)), - BidiInfo { - text, - levels: Level::vec(&[2, 2, 2, 1, 1, 1, 1, 1, 1, 1]), - original_classes: vec![L, L, L, WS, R, R, R, R, R, R], - paragraphs: vec![ParagraphInfo { + }], + Level::vec(&[0, 0, 0, 0, 1, 1, 1]), + vec![L, L, L, WS, R, R, R], + vec![ParagraphInfo { + range: 0..7, + level: LTR_LEVEL, + }], + ), + ( + "abc \u{05D0}\u{05D1}\u{05D2}", + Some(RTL_LEVEL), + Level::vec(&[2, 2, 2, 1, 1, 1, 1, 1, 1, 1]), + vec![L, L, L, WS, R, R, R, R, R, R], + vec![ParagraphInfo { range: 0..10, level: RTL_LEVEL, - },], - } - ); - - let text = "אבג abc"; - assert_eq!( - BidiInfo::new(text, Some(LTR_LEVEL)), - BidiInfo { - text, - levels: Level::vec(&[1, 1, 1, 1, 1, 1, 0, 0, 0, 0]), - original_classes: vec![R, R, R, R, R, R, WS, L, L, L], - paragraphs: vec![ParagraphInfo { + }], + Level::vec(&[2, 2, 2, 1, 1, 1, 1]), + vec![L, L, L, WS, R, R, R], + vec![ParagraphInfo { + range: 0..7, + level: RTL_LEVEL, + }], + ), + ( + "\u{05D0}\u{05D1}\u{05D2} abc", + Some(LTR_LEVEL), + Level::vec(&[1, 1, 1, 1, 1, 1, 0, 0, 0, 0]), + vec![R, R, R, R, R, R, WS, L, L, L], + vec![ParagraphInfo { range: 0..10, level: LTR_LEVEL, - },], - } - ); - assert_eq!( - BidiInfo::new(text, None), - BidiInfo { - text, - levels: Level::vec(&[1, 1, 1, 1, 1, 1, 1, 2, 2, 2]), - original_classes: vec![R, R, R, R, R, R, WS, L, L, L], - paragraphs: vec![ParagraphInfo { + }], + Level::vec(&[1, 1, 1, 0, 0, 0, 0]), + vec![R, R, R, WS, L, L, L], + vec![ParagraphInfo { + range: 0..7, + level: LTR_LEVEL, + }], + ), + ( + "\u{05D0}\u{05D1}\u{05D2} abc", + None, + Level::vec(&[1, 1, 1, 1, 1, 1, 1, 2, 2, 2]), + vec![R, R, R, R, R, R, WS, L, L, L], + vec![ParagraphInfo { range: 0..10, level: RTL_LEVEL, - },], - } - ); - - let text = "غ2ظ א2ג"; - assert_eq!( - BidiInfo::new(text, Some(LTR_LEVEL)), - BidiInfo { - text, - levels: Level::vec(&[1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1]), - original_classes: vec![AL, AL, EN, AL, AL, WS, R, R, EN, R, R], - paragraphs: vec![ParagraphInfo { + }], + Level::vec(&[1, 1, 1, 1, 2, 2, 2]), + vec![R, R, R, WS, L, L, L], + vec![ParagraphInfo { + range: 0..7, + level: RTL_LEVEL, + }], + ), + ( + "\u{063A}2\u{0638} \u{05D0}2\u{05D2}", + Some(LTR_LEVEL), + Level::vec(&[1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1]), + vec![AL, AL, EN, AL, AL, WS, R, R, EN, R, R], + vec![ParagraphInfo { range: 0..11, level: LTR_LEVEL, - },], - } - ); - - let text = "a א.\nג"; - assert_eq!( - BidiInfo::new(text, None), - BidiInfo { - text, - original_classes: vec![L, WS, R, R, CS, B, R, R], - levels: Level::vec(&[0, 0, 1, 1, 0, 0, 1, 1]), - paragraphs: vec![ + }], + Level::vec(&[1, 2, 1, 1, 1, 2, 1]), + vec![AL, EN, AL, WS, R, EN, R], + vec![ParagraphInfo { + range: 0..7, + level: LTR_LEVEL, + }], + ), + ( + "a א.\nג", + None, + Level::vec(&[0, 0, 1, 1, 0, 0, 1, 1]), + vec![L, WS, R, R, CS, B, R, R], + vec![ ParagraphInfo { range: 0..6, level: LTR_LEVEL, @@ -843,37 +1661,201 @@ mod tests { level: RTL_LEVEL, }, ], + Level::vec(&[0, 0, 1, 0, 0, 1]), + vec![L, WS, R, CS, B, R], + vec![ + ParagraphInfo { + range: 0..5, + level: LTR_LEVEL, + }, + ParagraphInfo { + range: 5..6, + level: RTL_LEVEL, + }, + ], + ), + // BidiTest:69635 (AL ET EN) + ( + "\u{060B}\u{20CF}\u{06F9}", + None, + Level::vec(&[1, 1, 1, 1, 1, 2, 2]), + vec![AL, AL, ET, ET, ET, EN, EN], + vec![ParagraphInfo { + range: 0..7, + level: RTL_LEVEL, + }], + Level::vec(&[1, 1, 2]), + vec![AL, ET, EN], + vec![ParagraphInfo { + range: 0..3, + level: RTL_LEVEL, + }], + ), + ]; + + for t in tests { + assert_eq!( + BidiInfo::new(t.0, t.1), + BidiInfo { + text: t.0, + levels: t.2.clone(), + original_classes: t.3.clone(), + paragraphs: t.4.clone(), + } + ); + // If it was a single paragraph, also test ParagraphBidiInfo. + if t.4.len() == 1 { + assert_eq!( + ParagraphBidiInfo::new(t.0, t.1), + ParagraphBidiInfo { + text: t.0, + original_classes: t.3, + levels: t.2.clone(), + paragraph_level: t.4[0].level, + is_pure_ltr: !level::has_rtl(&t.2), + } + ) } - ); + let text = &to_utf16(t.0); + assert_eq!( + BidiInfoU16::new(text, t.1), + BidiInfoU16 { + text, + levels: t.5.clone(), + original_classes: t.6.clone(), + paragraphs: t.7.clone(), + } + ); + if t.7.len() == 1 { + assert_eq!( + ParagraphBidiInfoU16::new(text, t.1), + ParagraphBidiInfoU16 { + text: text, + original_classes: t.6.clone(), + levels: t.5.clone(), + paragraph_level: t.7[0].level, + is_pure_ltr: !level::has_rtl(&t.5), + } + ) + } + } + } - // BidiTest:69635 (AL ET EN) - let bidi_info = BidiInfo::new("\u{060B}\u{20CF}\u{06F9}", None); - assert_eq!(bidi_info.original_classes, vec![AL, AL, ET, ET, ET, EN, EN]); + #[test] + #[cfg(feature = "hardcoded-data")] + fn test_paragraph_bidi_info() { + // Passing text that includes a paragraph break to the ParagraphBidiInfo API: + // this is a misuse of the API by the client, but our behavior is safe & + // consistent. The embedded paragraph break acts like a separator (tab) would. + let tests = vec![ + ( + "a א.\nג", + None, + // utf-8 results: + vec![L, WS, R, R, CS, B, R, R], + Level::vec(&[0, 0, 1, 1, 1, 1, 1, 1]), + // utf-16 results: + vec![L, WS, R, CS, B, R], + Level::vec(&[0, 0, 1, 1, 1, 1]), + // paragraph level; is_pure_ltr + LTR_LEVEL, + false, + ), + ( + "\u{5d1} a.\nb.", + None, + // utf-8 results: + vec![R, R, WS, L, CS, B, L, CS], + Level::vec(&[1, 1, 1, 2, 2, 2, 2, 1]), + // utf-16 results: + vec![R, WS, L, CS, B, L, CS], + Level::vec(&[1, 1, 2, 2, 2, 2, 1]), + // paragraph level; is_pure_ltr + RTL_LEVEL, + false, + ), + ( + "a א.\tג", + None, + // utf-8 results: + vec![L, WS, R, R, CS, S, R, R], + Level::vec(&[0, 0, 1, 1, 1, 1, 1, 1]), + // utf-16 results: + vec![L, WS, R, CS, S, R], + Level::vec(&[0, 0, 1, 1, 1, 1]), + // paragraph level; is_pure_ltr + LTR_LEVEL, + false, + ), + ( + "\u{5d1} a.\tb.", + None, + // utf-8 results: + vec![R, R, WS, L, CS, S, L, CS], + Level::vec(&[1, 1, 1, 2, 2, 2, 2, 1]), + // utf-16 results: + vec![R, WS, L, CS, S, L, CS], + Level::vec(&[1, 1, 2, 2, 2, 2, 1]), + // paragraph level; is_pure_ltr + RTL_LEVEL, + false, + ), + ]; + + for t in tests { + assert_eq!( + ParagraphBidiInfo::new(t.0, t.1), + ParagraphBidiInfo { + text: t.0, + original_classes: t.2, + levels: t.3, + paragraph_level: t.6, + is_pure_ltr: t.7, + } + ); + let text = &to_utf16(t.0); + assert_eq!( + ParagraphBidiInfoU16::new(text, t.1), + ParagraphBidiInfoU16 { + text: text, + original_classes: t.4, + levels: t.5, + paragraph_level: t.6, + is_pure_ltr: t.7, + } + ); + } } #[test] #[cfg(feature = "hardcoded-data")] fn test_bidi_info_has_rtl() { - // ASCII only - assert_eq!(BidiInfo::new("123", None).has_rtl(), false); - assert_eq!(BidiInfo::new("123", Some(LTR_LEVEL)).has_rtl(), false); - assert_eq!(BidiInfo::new("123", Some(RTL_LEVEL)).has_rtl(), false); - assert_eq!(BidiInfo::new("abc", None).has_rtl(), false); - assert_eq!(BidiInfo::new("abc", Some(LTR_LEVEL)).has_rtl(), false); - assert_eq!(BidiInfo::new("abc", Some(RTL_LEVEL)).has_rtl(), false); - assert_eq!(BidiInfo::new("abc 123", None).has_rtl(), false); - assert_eq!(BidiInfo::new("abc\n123", None).has_rtl(), false); - - // With Hebrew - assert_eq!(BidiInfo::new("אבּג", None).has_rtl(), true); - assert_eq!(BidiInfo::new("אבּג", Some(LTR_LEVEL)).has_rtl(), true); - assert_eq!(BidiInfo::new("אבּג", Some(RTL_LEVEL)).has_rtl(), true); - assert_eq!(BidiInfo::new("abc אבּג", None).has_rtl(), true); - assert_eq!(BidiInfo::new("abc\nאבּג", None).has_rtl(), true); - assert_eq!(BidiInfo::new("אבּג abc", None).has_rtl(), true); - assert_eq!(BidiInfo::new("אבּג\nabc", None).has_rtl(), true); - assert_eq!(BidiInfo::new("אבּג 123", None).has_rtl(), true); - assert_eq!(BidiInfo::new("אבּג\n123", None).has_rtl(), true); + let tests = vec![ + // ASCII only + ("123", None, false), + ("123", Some(LTR_LEVEL), false), + ("123", Some(RTL_LEVEL), false), + ("abc", None, false), + ("abc", Some(LTR_LEVEL), false), + ("abc", Some(RTL_LEVEL), false), + ("abc 123", None, false), + ("abc\n123", None, false), + // With Hebrew + ("\u{05D0}\u{05D1}\u{05BC}\u{05D2}", None, true), + ("\u{05D0}\u{05D1}\u{05BC}\u{05D2}", Some(LTR_LEVEL), true), + ("\u{05D0}\u{05D1}\u{05BC}\u{05D2}", Some(RTL_LEVEL), true), + ("abc \u{05D0}\u{05D1}\u{05BC}\u{05D2}", None, true), + ("abc\n\u{05D0}\u{05D1}\u{05BC}\u{05D2}", None, true), + ("\u{05D0}\u{05D1}\u{05BC}\u{05D2} abc", None, true), + ("\u{05D0}\u{05D1}\u{05BC}\u{05D2}\nabc", None, true), + ("\u{05D0}\u{05D1}\u{05BC}\u{05D2} 123", None, true), + ("\u{05D0}\u{05D1}\u{05BC}\u{05D2}\n123", None, true), + ]; + + for t in tests { + assert_eq!(BidiInfo::new(t.0, t.1).has_rtl(), t.2); + assert_eq!(BidiInfoU16::new(&to_utf16(t.0), t.1).has_rtl(), t.2); + } } #[cfg(feature = "hardcoded-data")] @@ -886,76 +1868,70 @@ mod tests { .collect() } + #[cfg(feature = "hardcoded-data")] + fn reorder_paras_u16(text: &[u16]) -> Vec<Cow<'_, [u16]>> { + let bidi_info = BidiInfoU16::new(text, None); + bidi_info + .paragraphs + .iter() + .map(|para| bidi_info.reorder_line(para, para.range.clone())) + .collect() + } + #[test] #[cfg(feature = "hardcoded-data")] fn test_reorder_line() { - // Bidi_Class: L L L B L L L B L L L - assert_eq!( - reorder_paras("abc\ndef\nghi"), - vec!["abc\n", "def\n", "ghi"] - ); - - // Bidi_Class: L L EN B L L EN B L L EN - assert_eq!( - reorder_paras("ab1\nde2\ngh3"), - vec!["ab1\n", "de2\n", "gh3"] - ); - - // Bidi_Class: L L L B AL AL AL - assert_eq!(reorder_paras("abc\nابج"), vec!["abc\n", "جبا"]); - - // Bidi_Class: AL AL AL B L L L - assert_eq!(reorder_paras("ابج\nabc"), vec!["\nجبا", "abc"]); - - assert_eq!(reorder_paras("1.-2"), vec!["1.-2"]); - assert_eq!(reorder_paras("1-.2"), vec!["1-.2"]); - assert_eq!(reorder_paras("abc אבג"), vec!["abc גבא"]); - - // Numbers being weak LTR characters, cannot reorder strong RTL - assert_eq!(reorder_paras("123 אבג"), vec!["גבא 123"]); - - assert_eq!(reorder_paras("abc\u{202A}def"), vec!["abc\u{202A}def"]); - - assert_eq!( - reorder_paras("abc\u{202A}def\u{202C}ghi"), - vec!["abc\u{202A}def\u{202C}ghi"] - ); - - assert_eq!( - reorder_paras("abc\u{2066}def\u{2069}ghi"), - vec!["abc\u{2066}def\u{2069}ghi"] - ); - - // Testing for RLE Character - assert_eq!( - reorder_paras("\u{202B}abc אבג\u{202C}"), - vec!["\u{202B}\u{202C}גבא abc"] - ); - - // Testing neutral characters - assert_eq!(reorder_paras("אבג? אבג"), vec!["גבא ?גבא"]); - - // Testing neutral characters with special case - assert_eq!(reorder_paras("A אבג?"), vec!["A גבא?"]); - - // Testing neutral characters with Implicit RTL Marker - assert_eq!(reorder_paras("A אבג?\u{200F}"), vec!["A \u{200F}?גבא"]); - assert_eq!(reorder_paras("אבג abc"), vec!["abc גבא"]); - assert_eq!( - reorder_paras("abc\u{2067}.-\u{2069}ghi"), - vec!["abc\u{2067}-.\u{2069}ghi"] - ); - - assert_eq!( - reorder_paras("Hello, \u{2068}\u{202E}world\u{202C}\u{2069}!"), - vec!["Hello, \u{2068}\u{202E}\u{202C}dlrow\u{2069}!"] - ); - - // With mirrorable characters in RTL run - assert_eq!(reorder_paras("א(ב)ג."), vec![".ג)ב(א"]); - - // With mirrorable characters on level boundry - assert_eq!(reorder_paras("אב(גד[&ef].)gh"), vec!["gh).]ef&[דג(בא"]); + let tests = vec![ + // Bidi_Class: L L L B L L L B L L L + ("abc\ndef\nghi", vec!["abc\n", "def\n", "ghi"]), + // Bidi_Class: L L EN B L L EN B L L EN + ("ab1\nde2\ngh3", vec!["ab1\n", "de2\n", "gh3"]), + // Bidi_Class: L L L B AL AL AL + ("abc\nابج", vec!["abc\n", "جبا"]), + // Bidi_Class: AL AL AL B L L L + ( + "\u{0627}\u{0628}\u{062C}\nabc", + vec!["\n\u{062C}\u{0628}\u{0627}", "abc"], + ), + ("1.-2", vec!["1.-2"]), + ("1-.2", vec!["1-.2"]), + ("abc אבג", vec!["abc גבא"]), + // Numbers being weak LTR characters, cannot reorder strong RTL + ("123 \u{05D0}\u{05D1}\u{05D2}", vec!["גבא 123"]), + ("abc\u{202A}def", vec!["abc\u{202A}def"]), + ( + "abc\u{202A}def\u{202C}ghi", + vec!["abc\u{202A}def\u{202C}ghi"], + ), + ( + "abc\u{2066}def\u{2069}ghi", + vec!["abc\u{2066}def\u{2069}ghi"], + ), + // Testing for RLE Character + ("\u{202B}abc אבג\u{202C}", vec!["\u{202b}גבא abc\u{202c}"]), + // Testing neutral characters + ("\u{05D0}בג? אבג", vec!["גבא ?גבא"]), + // Testing neutral characters with special case + ("A אבג?", vec!["A גבא?"]), + // Testing neutral characters with Implicit RTL Marker + ("A אבג?\u{200F}", vec!["A \u{200F}?גבא"]), + ("\u{05D0}בג abc", vec!["abc גבא"]), + ("abc\u{2067}.-\u{2069}ghi", vec!["abc\u{2067}-.\u{2069}ghi"]), + ( + "Hello, \u{2068}\u{202E}world\u{202C}\u{2069}!", + vec!["Hello, \u{2068}\u{202E}\u{202C}dlrow\u{2069}!"], + ), + // With mirrorable characters in RTL run + ("\u{05D0}(ב)ג.", vec![".ג)ב(א"]), + // With mirrorable characters on level boundary + ("\u{05D0}ב(גד[&ef].)gh", vec!["gh).]ef&[דג(בא"]), + ]; + + for t in tests { + assert_eq!(reorder_paras(t.0), t.1); + let expect_utf16 = t.1.iter().map(|v| to_utf16(v)).collect::<Vec<_>>(); + assert_eq!(reorder_paras_u16(&to_utf16(t.0)), expect_utf16); + } } fn reordered_levels_for_paras(text: &str) -> Vec<Vec<Level>> { @@ -976,47 +1952,83 @@ mod tests { .collect() } + fn reordered_levels_for_paras_u16(text: &[u16]) -> Vec<Vec<Level>> { + let bidi_info = BidiInfoU16::new(text, None); + bidi_info + .paragraphs + .iter() + .map(|para| bidi_info.reordered_levels(para, para.range.clone())) + .collect() + } + + fn reordered_levels_per_char_for_paras_u16(text: &[u16]) -> Vec<Vec<Level>> { + let bidi_info = BidiInfoU16::new(text, None); + bidi_info + .paragraphs + .iter() + .map(|para| bidi_info.reordered_levels_per_char(para, para.range.clone())) + .collect() + } + #[test] #[cfg(feature = "hardcoded-data")] fn test_reordered_levels() { - // BidiTest:946 (LRI PDI) - let text = "\u{2067}\u{2069}"; - assert_eq!( - reordered_levels_for_paras(text), - vec![Level::vec(&[0, 0, 0, 0, 0, 0])] - ); - assert_eq!( - reordered_levels_per_char_for_paras(text), - vec![Level::vec(&[0, 0])] - ); + let tests = vec![ + // BidiTest:946 (LRI PDI) + ( + "\u{2067}\u{2069}", + vec![Level::vec(&[0, 0, 0, 0, 0, 0])], + vec![Level::vec(&[0, 0])], + vec![Level::vec(&[0, 0])], + ), + // BidiTest:69635 (AL ET EN) + ( + "\u{060B}\u{20CF}\u{06F9}", + vec![Level::vec(&[1, 1, 1, 1, 1, 2, 2])], + vec![Level::vec(&[1, 1, 2])], + vec![Level::vec(&[1, 1, 2])], + ), + ]; + + for t in tests { + assert_eq!(reordered_levels_for_paras(t.0), t.1); + assert_eq!(reordered_levels_per_char_for_paras(t.0), t.2); + let text = &to_utf16(t.0); + assert_eq!(reordered_levels_for_paras_u16(text), t.3); + assert_eq!(reordered_levels_per_char_for_paras_u16(text), t.2); + } + + let tests = vec![ + // BidiTest:291284 (AN RLI PDF R) + ( + "\u{0605}\u{2067}\u{202C}\u{0590}", + vec![&["2", "2", "0", "0", "0", "x", "x", "x", "1", "1"]], + vec![&["2", "0", "x", "1"]], + vec![&["2", "0", "x", "1"]], + ), + ]; + + for t in tests { + assert_eq!(reordered_levels_for_paras(t.0), t.1); + assert_eq!(reordered_levels_per_char_for_paras(t.0), t.2); + let text = &to_utf16(t.0); + assert_eq!(reordered_levels_for_paras_u16(text), t.3); + assert_eq!(reordered_levels_per_char_for_paras_u16(text), t.2); + } let text = "aa טֶ"; let bidi_info = BidiInfo::new(text, None); assert_eq!( bidi_info.reordered_levels(&bidi_info.paragraphs[0], 3..7), Level::vec(&[0, 0, 0, 1, 1, 1, 1]), - ) - - /* TODO - /// BidiTest:69635 (AL ET EN) - let text = "\u{060B}\u{20CF}\u{06F9}"; - assert_eq!( - reordered_levels_for_paras(text), - vec![Level::vec(&[1, 1, 1, 1, 1, 2, 2])] ); - assert_eq!( - reordered_levels_per_char_for_paras(text), - vec![Level::vec(&[1, 1, 2])] - ); - */ - /* TODO - // BidiTest:291284 (AN RLI PDF R) + let text = &to_utf16(text); + let bidi_info = BidiInfoU16::new(text, None); assert_eq!( - reordered_levels_per_char_for_paras("\u{0605}\u{2067}\u{202C}\u{0590}"), - vec![&["2", "0", "x", "1"]] + bidi_info.reordered_levels(&bidi_info.paragraphs[0], 1..4), + Level::vec(&[0, 0, 0, 1, 1]), ); - */ } #[test] @@ -1036,6 +2048,19 @@ mod tests { // should not be part of any paragraph. assert_eq!(bidi_info.paragraphs[0].len(), text.len() + 1); assert_eq!(bidi_info.paragraphs[1].len(), text2.len()); + + let text = &to_utf16(text); + let bidi_info = BidiInfoU16::new(text, None); + assert_eq!(bidi_info.paragraphs.len(), 1); + assert_eq!(bidi_info.paragraphs[0].len(), text.len()); + + let text2 = &to_utf16(text2); + let whole_text = &to_utf16(&whole_text); + let bidi_info = BidiInfoU16::new(&whole_text, None); + assert_eq!(bidi_info.paragraphs.len(), 2); + + assert_eq!(bidi_info.paragraphs[0].len(), text.len() + 1); + assert_eq!(bidi_info.paragraphs[1].len(), text2.len()); } #[test] @@ -1051,6 +2076,16 @@ mod tests { assert_eq!(p_ltr.direction(), Direction::Ltr); assert_eq!(p_rtl.direction(), Direction::Rtl); assert_eq!(p_mixed.direction(), Direction::Mixed); + + let all_paragraphs = &to_utf16(&all_paragraphs); + let bidi_info = BidiInfoU16::new(&all_paragraphs, None); + assert_eq!(bidi_info.paragraphs.len(), 3); + let p_ltr = ParagraphU16::new(&bidi_info, &bidi_info.paragraphs[0]); + let p_rtl = ParagraphU16::new(&bidi_info, &bidi_info.paragraphs[1]); + let p_mixed = ParagraphU16::new(&bidi_info, &bidi_info.paragraphs[2]); + assert_eq!(p_ltr.direction(), Direction::Ltr); + assert_eq!(p_rtl.direction(), Direction::Rtl); + assert_eq!(p_mixed.direction(), Direction::Mixed); } #[test] @@ -1059,28 +2094,33 @@ mod tests { let empty = ""; let bidi_info = BidiInfo::new(empty, Option::from(RTL_LEVEL)); assert_eq!(bidi_info.paragraphs.len(), 0); - // The paragraph separator will take the value of the default direction - // which is left to right. - let empty = "\n"; - let bidi_info = BidiInfo::new(empty, None); - assert_eq!(bidi_info.paragraphs.len(), 1); - let p = Paragraph::new(&bidi_info, &bidi_info.paragraphs[0]); - assert_eq!(p.direction(), Direction::Ltr); - // The paragraph separator will take the value of the given initial direction - // which is left to right. - let empty = "\n"; - let bidi_info = BidiInfo::new(empty, Option::from(LTR_LEVEL)); - assert_eq!(bidi_info.paragraphs.len(), 1); - let p = Paragraph::new(&bidi_info, &bidi_info.paragraphs[0]); - assert_eq!(p.direction(), Direction::Ltr); - // The paragraph separator will take the value of the given initial direction - // which is right to left. - let empty = "\n"; - let bidi_info = BidiInfo::new(empty, Option::from(RTL_LEVEL)); - assert_eq!(bidi_info.paragraphs.len(), 1); - let p = Paragraph::new(&bidi_info, &bidi_info.paragraphs[0]); - assert_eq!(p.direction(), Direction::Rtl); + let empty = &to_utf16(empty); + let bidi_info = BidiInfoU16::new(empty, Option::from(RTL_LEVEL)); + assert_eq!(bidi_info.paragraphs.len(), 0); + + let tests = vec![ + // The paragraph separator will take the value of the default direction + // which is left to right. + ("\n", None, Direction::Ltr), + // The paragraph separator will take the value of the given initial direction + // which is left to right. + ("\n", Option::from(LTR_LEVEL), Direction::Ltr), + // The paragraph separator will take the value of the given initial direction + // which is right to left. + ("\n", Option::from(RTL_LEVEL), Direction::Rtl), + ]; + + for t in tests { + let bidi_info = BidiInfo::new(t.0, t.1); + assert_eq!(bidi_info.paragraphs.len(), 1); + let p = Paragraph::new(&bidi_info, &bidi_info.paragraphs[0]); + assert_eq!(p.direction(), t.2); + let text = &to_utf16(t.0); + let bidi_info = BidiInfoU16::new(text, t.1); + let p = ParagraphU16::new(&bidi_info, &bidi_info.paragraphs[0]); + assert_eq!(p.direction(), t.2); + } } #[test] @@ -1101,6 +2141,61 @@ mod tests { assert_eq!(p_mixed.info.levels.len(), 54); assert_eq!(p_mixed.para.range.start, 28); assert_eq!(p_mixed.level_at(ltr_text.len()), RTL_LEVEL); + + let all_paragraphs = &to_utf16(&all_paragraphs); + let bidi_info = BidiInfoU16::new(&all_paragraphs, None); + assert_eq!(bidi_info.paragraphs.len(), 3); + + let p_ltr = ParagraphU16::new(&bidi_info, &bidi_info.paragraphs[0]); + let p_rtl = ParagraphU16::new(&bidi_info, &bidi_info.paragraphs[1]); + let p_mixed = ParagraphU16::new(&bidi_info, &bidi_info.paragraphs[2]); + + assert_eq!(p_ltr.level_at(0), LTR_LEVEL); + assert_eq!(p_rtl.level_at(0), RTL_LEVEL); + assert_eq!(p_mixed.level_at(0), LTR_LEVEL); + assert_eq!(p_mixed.info.levels.len(), 40); + assert_eq!(p_mixed.para.range.start, 21); + assert_eq!(p_mixed.level_at(ltr_text.len()), RTL_LEVEL); + } + + #[test] + fn test_get_base_direction() { + let tests = vec![ + ("", Direction::Mixed), // return Mixed if no strong character found + ("123[]-+\u{2019}\u{2060}\u{00bf}?", Direction::Mixed), + ("3.14\npi", Direction::Mixed), // only first paragraph is considered + ("[123 'abc']", Direction::Ltr), + ("[123 '\u{0628}' abc", Direction::Rtl), + ("[123 '\u{2066}abc\u{2069}'\u{0628}]", Direction::Rtl), // embedded isolate is ignored + ("[123 '\u{2066}abc\u{2068}'\u{0628}]", Direction::Mixed), + ]; + + for t in tests { + assert_eq!(get_base_direction(t.0), t.1); + let text = &to_utf16(t.0); + assert_eq!(get_base_direction(text.as_slice()), t.1); + } + } + + #[test] + fn test_get_base_direction_full() { + let tests = vec![ + ("", Direction::Mixed), // return Mixed if no strong character found + ("123[]-+\u{2019}\u{2060}\u{00bf}?", Direction::Mixed), + ("3.14\npi", Direction::Ltr), // direction taken from the second paragraph + ("3.14\n\u{05D0}", Direction::Rtl), // direction taken from the second paragraph + ("[123 'abc']", Direction::Ltr), + ("[123 '\u{0628}' abc", Direction::Rtl), + ("[123 '\u{2066}abc\u{2069}'\u{0628}]", Direction::Rtl), // embedded isolate is ignored + ("[123 '\u{2066}abc\u{2068}'\u{0628}]", Direction::Mixed), + ("[123 '\u{2066}abc\u{2068}'\n\u{0628}]", Direction::Rtl), // \n resets embedding level + ]; + + for t in tests { + assert_eq!(get_base_direction_full(t.0), t.1); + let text = &to_utf16(t.0); + assert_eq!(get_base_direction_full(text.as_slice()), t.1); + } } } diff --git a/src/prepare.rs b/src/prepare.rs index 21675e6..9234e1a 100644 --- a/src/prepare.rs +++ b/src/prepare.rs @@ -59,7 +59,17 @@ pub fn isolating_run_sequences( assert!(!stack.is_empty()); let start_class = original_classes[run.start]; - let end_class = original_classes[run.end - 1]; + // > In rule X10, [..] skip over any BNs when [..]. + // > Do the same when determining if the last character of the sequence is an isolate initiator. + // + // <https://www.unicode.org/reports/tr9/#Retaining_Explicit_Formatting_Characters> + let end_class = original_classes[run.start..run.end] + .iter() + .copied() + .rev() + .filter(not_removed_by_x9) + .next() + .unwrap_or(start_class); let mut sequence = if start_class == PDI && stack.len() > 1 { // Continue a previous sequence interrupted by an isolate. @@ -166,15 +176,6 @@ pub fn isolating_run_sequences( } impl IsolatingRunSequence { - /// Returns the full range of text represented by this isolating run sequence - pub(crate) fn text_range(&self) -> Range<usize> { - if let (Some(start), Some(end)) = (self.runs.first(), self.runs.last()) { - start.start..end.end - } else { - return 0..0; - } - } - /// Given a text-relative position `pos` and an index of the level run it is in, /// produce an iterator of all characters after and pos (`pos..`) that are in this /// run sequence diff --git a/src/utf16.rs b/src/utf16.rs new file mode 100644 index 0000000..dcd9baf --- /dev/null +++ b/src/utf16.rs @@ -0,0 +1,791 @@ +// Copyright 2023 The Mozilla Foundation. 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. + +use super::TextSource; + +use alloc::borrow::Cow; +use alloc::vec::Vec; +use core::char; +use core::ops::Range; + +use crate::{ + compute_bidi_info_for_para, compute_initial_info, level, para_direction, reorder_levels, + reorder_visual, visual_runs_for_line, +}; +use crate::{BidiClass, BidiDataSource, Direction, Level, LevelRun, ParagraphInfo}; + +#[cfg(feature = "hardcoded-data")] +use crate::HardcodedBidiData; + +/// Initial bidi information of the text (UTF-16 version). +/// +/// Contains the text paragraphs and `BidiClass` of its characters. +#[derive(PartialEq, Debug)] +pub struct InitialInfo<'text> { + /// The text + pub text: &'text [u16], + + /// The BidiClass of the character at each code unit in the text. + /// If a character is multiple code units, its class will appear multiple times in the vector. + pub original_classes: Vec<BidiClass>, + + /// The boundaries and level of each paragraph within the text. + pub paragraphs: Vec<ParagraphInfo>, +} + +impl<'text> InitialInfo<'text> { + /// Find the paragraphs and BidiClasses in a string of text. + /// + /// <http://www.unicode.org/reports/tr9/#The_Paragraph_Level> + /// + /// Also sets the class for each First Strong Isolate initiator (FSI) to LRI or RLI if a strong + /// character is found before the matching PDI. If no strong character is found, the class will + /// remain FSI, and it's up to later stages to treat these as LRI when needed. + /// + /// The `hardcoded-data` Cargo feature (enabled by default) must be enabled to use this. + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[cfg(feature = "hardcoded-data")] + pub fn new(text: &[u16], default_para_level: Option<Level>) -> InitialInfo<'_> { + Self::new_with_data_source(&HardcodedBidiData, text, default_para_level) + } + + /// Find the paragraphs and BidiClasses in a string of text, with a custom [`BidiDataSource`] + /// for Bidi data. If you just wish to use the hardcoded Bidi data, please use [`InitialInfo::new()`] + /// instead (enabled with tbe default `hardcoded-data` Cargo feature) + /// + /// <http://www.unicode.org/reports/tr9/#The_Paragraph_Level> + /// + /// Also sets the class for each First Strong Isolate initiator (FSI) to LRI or RLI if a strong + /// character is found before the matching PDI. If no strong character is found, the class will + /// remain FSI, and it's up to later stages to treat these as LRI when needed. + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn new_with_data_source<'a, D: BidiDataSource>( + data_source: &D, + text: &'a [u16], + default_para_level: Option<Level>, + ) -> InitialInfo<'a> { + InitialInfoExt::new_with_data_source(data_source, text, default_para_level).base + } +} + +/// Extended version of InitialInfo (not public API). +#[derive(PartialEq, Debug)] +struct InitialInfoExt<'text> { + /// The base InitialInfo for the text, recording its paragraphs and bidi classes. + base: InitialInfo<'text>, + + /// Parallel to base.paragraphs, records whether each paragraph is "pure LTR" that + /// requires no further bidi processing (i.e. there are no RTL characters or bidi + /// control codes present). + pure_ltr: Vec<bool>, +} + +impl<'text> InitialInfoExt<'text> { + /// Find the paragraphs and BidiClasses in a string of text, with a custom [`BidiDataSource`] + /// for Bidi data. If you just wish to use the hardcoded Bidi data, please use [`InitialInfo::new()`] + /// instead (enabled with tbe default `hardcoded-data` Cargo feature) + /// + /// <http://www.unicode.org/reports/tr9/#The_Paragraph_Level> + /// + /// Also sets the class for each First Strong Isolate initiator (FSI) to LRI or RLI if a strong + /// character is found before the matching PDI. If no strong character is found, the class will + /// remain FSI, and it's up to later stages to treat these as LRI when needed. + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn new_with_data_source<'a, D: BidiDataSource>( + data_source: &D, + text: &'a [u16], + default_para_level: Option<Level>, + ) -> InitialInfoExt<'a> { + let mut paragraphs = Vec::<ParagraphInfo>::new(); + let mut pure_ltr = Vec::<bool>::new(); + let (original_classes, _, _) = compute_initial_info( + data_source, + text, + default_para_level, + Some((&mut paragraphs, &mut pure_ltr)), + ); + + InitialInfoExt { + base: InitialInfo { + text, + original_classes, + paragraphs, + }, + pure_ltr, + } + } +} + +/// Bidi information of the text (UTF-16 version). +/// +/// The `original_classes` and `levels` vectors are indexed by code unit offsets into the text. If a +/// character is multiple code units wide, then its class and level will appear multiple times in these +/// vectors. +// TODO: Impl `struct StringProperty<T> { values: Vec<T> }` and use instead of Vec<T> +#[derive(Debug, PartialEq)] +pub struct BidiInfo<'text> { + /// The text + pub text: &'text [u16], + + /// The BidiClass of the character at each byte in the text. + pub original_classes: Vec<BidiClass>, + + /// The directional embedding level of each byte in the text. + pub levels: Vec<Level>, + + /// The boundaries and paragraph embedding level of each paragraph within the text. + /// + /// TODO: Use SmallVec or similar to avoid overhead when there are only one or two paragraphs? + /// Or just don't include the first paragraph, which always starts at 0? + pub paragraphs: Vec<ParagraphInfo>, +} + +impl<'text> BidiInfo<'text> { + /// Split the text into paragraphs and determine the bidi embedding levels for each paragraph. + /// + /// + /// The `hardcoded-data` Cargo feature (enabled by default) must be enabled to use this. + /// + /// TODO: In early steps, check for special cases that allow later steps to be skipped. like + /// text that is entirely LTR. See the `nsBidi` class from Gecko for comparison. + /// + /// TODO: Support auto-RTL base direction + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[cfg(feature = "hardcoded-data")] + #[inline] + pub fn new(text: &[u16], default_para_level: Option<Level>) -> BidiInfo<'_> { + Self::new_with_data_source(&HardcodedBidiData, text, default_para_level) + } + + /// Split the text into paragraphs and determine the bidi embedding levels for each paragraph, with a custom [`BidiDataSource`] + /// for Bidi data. If you just wish to use the hardcoded Bidi data, please use [`BidiInfo::new()`] + /// instead (enabled with tbe default `hardcoded-data` Cargo feature). + /// + /// TODO: In early steps, check for special cases that allow later steps to be skipped. like + /// text that is entirely LTR. See the `nsBidi` class from Gecko for comparison. + /// + /// TODO: Support auto-RTL base direction + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn new_with_data_source<'a, D: BidiDataSource>( + data_source: &D, + text: &'a [u16], + default_para_level: Option<Level>, + ) -> BidiInfo<'a> { + let InitialInfoExt { base, pure_ltr, .. } = + InitialInfoExt::new_with_data_source(data_source, text, default_para_level); + + let mut levels = Vec::<Level>::with_capacity(text.len()); + let mut processing_classes = base.original_classes.clone(); + + for (para, is_pure_ltr) in base.paragraphs.iter().zip(pure_ltr.iter()) { + let text = &text[para.range.clone()]; + let original_classes = &base.original_classes[para.range.clone()]; + + compute_bidi_info_for_para( + data_source, + para, + *is_pure_ltr, + text, + original_classes, + &mut processing_classes, + &mut levels, + ); + } + + BidiInfo { + text, + original_classes: base.original_classes, + paragraphs: base.paragraphs, + levels, + } + } + + /// Produce the levels for this paragraph as needed for reordering, one level per *byte* + /// in the paragraph. The returned vector includes bytes that are not included + /// in the `line`, but will not adjust them. + /// + /// This runs [Rule L1], you can run + /// [Rule L2] by calling [`Self::reorder_visual()`]. + /// If doing so, you may prefer to use [`Self::reordered_levels_per_char()`] instead + /// to avoid non-byte indices. + /// + /// For an all-in-one reordering solution, consider using [`Self::reorder_visual()`]. + /// + /// [Rule L1]: https://www.unicode.org/reports/tr9/#L1 + /// [Rule L2]: https://www.unicode.org/reports/tr9/#L2 + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reordered_levels(&self, para: &ParagraphInfo, line: Range<usize>) -> Vec<Level> { + assert!(line.start <= self.levels.len()); + assert!(line.end <= self.levels.len()); + + let mut levels = self.levels.clone(); + let line_classes = &self.original_classes[line.clone()]; + let line_levels = &mut levels[line.clone()]; + let line_str: &[u16] = &self.text[line.clone()]; + + reorder_levels(line_classes, line_levels, line_str, para.level); + + levels + } + + /// Produce the levels for this paragraph as needed for reordering, one level per *character* + /// in the paragraph. The returned vector includes characters that are not included + /// in the `line`, but will not adjust them. + /// + /// This runs [Rule L1], you can run + /// [Rule L2] by calling [`Self::reorder_visual()`]. + /// If doing so, you may prefer to use [`Self::reordered_levels_per_char()`] instead + /// to avoid non-byte indices. + /// + /// For an all-in-one reordering solution, consider using [`Self::reorder_visual()`]. + /// + /// [Rule L1]: https://www.unicode.org/reports/tr9/#L1 + /// [Rule L2]: https://www.unicode.org/reports/tr9/#L2 + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reordered_levels_per_char( + &self, + para: &ParagraphInfo, + line: Range<usize>, + ) -> Vec<Level> { + let levels = self.reordered_levels(para, line); + self.text.char_indices().map(|(i, _)| levels[i]).collect() + } + + /// Re-order a line based on resolved levels and return the line in display order. + /// + /// This does not apply [Rule L3] or [Rule L4] around combining characters or mirroring. + /// + /// [Rule L3]: https://www.unicode.org/reports/tr9/#L3 + /// [Rule L4]: https://www.unicode.org/reports/tr9/#L4 + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reorder_line(&self, para: &ParagraphInfo, line: Range<usize>) -> Cow<'text, [u16]> { + if !level::has_rtl(&self.levels[line.clone()]) { + return self.text[line].into(); + } + let (levels, runs) = self.visual_runs(para, line.clone()); + reorder_line(self.text, line, levels, runs) + } + + /// Reorders pre-calculated levels of a sequence of characters. + /// + /// NOTE: This is a convenience method that does not use a `Paragraph` object. It is + /// intended to be used when an application has determined the levels of the objects (character sequences) + /// and just needs to have them reordered. + /// + /// the index map will result in `indexMap[visualIndex]==logicalIndex`. + /// + /// This only runs [Rule L2](http://www.unicode.org/reports/tr9/#L2) as it does not have + /// information about the actual text. + /// + /// Furthermore, if `levels` is an array that is aligned with code units, bytes within a codepoint may be + /// reversed. You may need to fix up the map to deal with this. Alternatively, only pass in arrays where each `Level` + /// is for a single code point. + /// + /// + /// # # Example + /// ``` + /// use unicode_bidi::BidiInfo; + /// use unicode_bidi::Level; + /// + /// let l0 = Level::from(0); + /// let l1 = Level::from(1); + /// let l2 = Level::from(2); + /// + /// let levels = vec![l0, l0, l0, l0]; + /// let index_map = BidiInfo::reorder_visual(&levels); + /// assert_eq!(levels.len(), index_map.len()); + /// assert_eq!(index_map, [0, 1, 2, 3]); + /// + /// let levels: Vec<Level> = vec![l0, l0, l0, l1, l1, l1, l2, l2]; + /// let index_map = BidiInfo::reorder_visual(&levels); + /// assert_eq!(levels.len(), index_map.len()); + /// assert_eq!(index_map, [0, 1, 2, 6, 7, 5, 4, 3]); + /// ``` + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[inline] + pub fn reorder_visual(levels: &[Level]) -> Vec<usize> { + reorder_visual(levels) + } + + /// Find the level runs within a line and return them in visual order. + /// + /// `line` is a range of bytes indices within `levels`. + /// + /// The first return value is a vector of levels used by the reordering algorithm, + /// i.e. the result of [Rule L1]. The second return value is a vector of level runs, + /// the result of [Rule L2], showing the visual order that each level run (a run of text with the + /// same level) should be displayed. Within each run, the display order can be checked + /// against the Level vector. + /// + /// This does not handle [Rule L3] (combining characters) or [Rule L4] (mirroring), + /// as that should be handled by the engine using this API. + /// + /// Conceptually, this is the same as running [`Self::reordered_levels()`] followed by + /// [`Self::reorder_visual()`], however it returns the result as a list of level runs instead + /// of producing a level map, since one may wish to deal with the fact that this is operating on + /// byte rather than character indices. + /// + /// <http://www.unicode.org/reports/tr9/#Reordering_Resolved_Levels> + /// + /// [Rule L1]: https://www.unicode.org/reports/tr9/#L1 + /// [Rule L2]: https://www.unicode.org/reports/tr9/#L2 + /// [Rule L3]: https://www.unicode.org/reports/tr9/#L3 + /// [Rule L4]: https://www.unicode.org/reports/tr9/#L4 + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[inline] + pub fn visual_runs( + &self, + para: &ParagraphInfo, + line: Range<usize>, + ) -> (Vec<Level>, Vec<LevelRun>) { + let levels = self.reordered_levels(para, line.clone()); + visual_runs_for_line(levels, &line) + } + + /// If processed text has any computed RTL levels + /// + /// This information is usually used to skip re-ordering of text when no RTL level is present + #[inline] + pub fn has_rtl(&self) -> bool { + level::has_rtl(&self.levels) + } +} + +/// Bidi information of text treated as a single paragraph. +/// +/// The `original_classes` and `levels` vectors are indexed by code unit offsets into the text. If a +/// character is multiple code units wide, then its class and level will appear multiple times in these +/// vectors. +#[derive(Debug, PartialEq)] +pub struct ParagraphBidiInfo<'text> { + /// The text + pub text: &'text [u16], + + /// The BidiClass of the character at each byte in the text. + pub original_classes: Vec<BidiClass>, + + /// The directional embedding level of each byte in the text. + pub levels: Vec<Level>, + + /// The paragraph embedding level. + pub paragraph_level: Level, + + /// Whether the paragraph is purely LTR. + pub is_pure_ltr: bool, +} + +impl<'text> ParagraphBidiInfo<'text> { + /// Determine the bidi embedding level. + /// + /// + /// The `hardcoded-data` Cargo feature (enabled by default) must be enabled to use this. + /// + /// TODO: In early steps, check for special cases that allow later steps to be skipped. like + /// text that is entirely LTR. See the `nsBidi` class from Gecko for comparison. + /// + /// TODO: Support auto-RTL base direction + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[cfg(feature = "hardcoded-data")] + #[inline] + pub fn new(text: &[u16], default_para_level: Option<Level>) -> ParagraphBidiInfo<'_> { + Self::new_with_data_source(&HardcodedBidiData, text, default_para_level) + } + + /// Determine the bidi embedding level, with a custom [`BidiDataSource`] + /// for Bidi data. If you just wish to use the hardcoded Bidi data, please use [`BidiInfo::new()`] + /// instead (enabled with tbe default `hardcoded-data` Cargo feature). + /// + /// (This is the single-paragraph equivalent of BidiInfo::new_with_data_source, + /// and should be kept in sync with it. + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn new_with_data_source<'a, D: BidiDataSource>( + data_source: &D, + text: &'a [u16], + default_para_level: Option<Level>, + ) -> ParagraphBidiInfo<'a> { + // Here we could create a ParagraphInitialInfo struct to parallel the one + // used by BidiInfo, but there doesn't seem any compelling reason for it. + let (original_classes, paragraph_level, is_pure_ltr) = + compute_initial_info(data_source, text, default_para_level, None); + + let mut levels = Vec::<Level>::with_capacity(text.len()); + let mut processing_classes = original_classes.clone(); + + let para_info = ParagraphInfo { + range: Range { + start: 0, + end: text.len(), + }, + level: paragraph_level, + }; + + compute_bidi_info_for_para( + data_source, + ¶_info, + is_pure_ltr, + text, + &original_classes, + &mut processing_classes, + &mut levels, + ); + + ParagraphBidiInfo { + text, + original_classes, + levels, + paragraph_level, + is_pure_ltr, + } + } + + /// Produce the levels for this paragraph as needed for reordering, one level per *code unit* + /// in the paragraph. The returned vector includes code units that are not included + /// in the `line`, but will not adjust them. + /// + /// See BidiInfo::reordered_levels for details. + /// + /// (This should be kept in sync with BidiInfo::reordered_levels.) + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reordered_levels(&self, line: Range<usize>) -> Vec<Level> { + assert!(line.start <= self.levels.len()); + assert!(line.end <= self.levels.len()); + + let mut levels = self.levels.clone(); + let line_classes = &self.original_classes[line.clone()]; + let line_levels = &mut levels[line.clone()]; + + reorder_levels( + line_classes, + line_levels, + self.text.subrange(line), + self.paragraph_level, + ); + + levels + } + + /// Produce the levels for this paragraph as needed for reordering, one level per *character* + /// in the paragraph. The returned vector includes characters that are not included + /// in the `line`, but will not adjust them. + /// + /// See BidiInfo::reordered_levels_per_char for details. + /// + /// (This should be kept in sync with BidiInfo::reordered_levels_per_char.) + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reordered_levels_per_char(&self, line: Range<usize>) -> Vec<Level> { + let levels = self.reordered_levels(line); + self.text.char_indices().map(|(i, _)| levels[i]).collect() + } + + /// Re-order a line based on resolved levels and return the line in display order. + /// + /// See BidiInfo::reorder_line for details. + /// + /// (This should be kept in sync with BidiInfo::reorder_line.) + #[cfg_attr(feature = "flame_it", flamer::flame)] + pub fn reorder_line(&self, line: Range<usize>) -> Cow<'text, [u16]> { + if !level::has_rtl(&self.levels[line.clone()]) { + return self.text[line].into(); + } + let (levels, runs) = self.visual_runs(line.clone()); + reorder_line(self.text, line, levels, runs) + } + + /// Reorders pre-calculated levels of a sequence of characters. + /// + /// See BidiInfo::reorder_visual for details. + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[inline] + pub fn reorder_visual(levels: &[Level]) -> Vec<usize> { + reorder_visual(levels) + } + + /// Find the level runs within a line and return them in visual order. + /// + /// `line` is a range of code-unit indices within `levels`. + /// + /// See `BidiInfo::visual_runs` for details. + /// + /// (This should be kept in sync with BidiInfo::visual_runs.) + #[cfg_attr(feature = "flame_it", flamer::flame)] + #[inline] + pub fn visual_runs(&self, line: Range<usize>) -> (Vec<Level>, Vec<LevelRun>) { + let levels = self.reordered_levels(line.clone()); + visual_runs_for_line(levels, &line) + } + + /// If processed text has any computed RTL levels + /// + /// This information is usually used to skip re-ordering of text when no RTL level is present + #[inline] + pub fn has_rtl(&self) -> bool { + !self.is_pure_ltr + } + + /// Return the paragraph's Direction (Ltr, Rtl, or Mixed) based on its levels. + #[inline] + pub fn direction(&self) -> Direction { + para_direction(&self.levels) + } +} + +/// Return a line of the text in display order based on resolved levels. +/// +/// `text` the full text passed to the `BidiInfo` or `ParagraphBidiInfo` for analysis +/// `line` a range of byte indices within `text` corresponding to one line +/// `levels` array of `Level` values, with `line`'s levels reordered into visual order +/// `runs` array of `LevelRun`s in visual order +/// +/// (`levels` and `runs` are the result of calling `BidiInfo::visual_runs()` or +/// `ParagraphBidiInfo::visual_runs()` for the line of interest.) +/// +/// Returns: the reordered text of the line. +/// +/// This does not apply [Rule L3] or [Rule L4] around combining characters or mirroring. +/// +/// [Rule L3]: https://www.unicode.org/reports/tr9/#L3 +/// [Rule L4]: https://www.unicode.org/reports/tr9/#L4 +fn reorder_line<'text>( + text: &'text [u16], + line: Range<usize>, + levels: Vec<Level>, + runs: Vec<LevelRun>, +) -> Cow<'text, [u16]> { + // If all isolating run sequences are LTR, no reordering is needed + if runs.iter().all(|run| levels[run.start].is_ltr()) { + return text[line].into(); + } + + let mut result = Vec::<u16>::with_capacity(line.len()); + for run in runs { + if levels[run.start].is_rtl() { + let mut buf = [0; 2]; + for c in text[run].chars().rev() { + result.extend(c.encode_utf16(&mut buf).iter()); + } + } else { + result.extend(text[run].iter()); + } + } + result.into() +} + +/// Contains a reference of `BidiInfo` and one of its `paragraphs`. +/// And it supports all operation in the `Paragraph` that needs also its +/// `BidiInfo` such as `direction`. +#[derive(Debug)] +pub struct Paragraph<'a, 'text> { + pub info: &'a BidiInfo<'text>, + pub para: &'a ParagraphInfo, +} + +impl<'a, 'text> Paragraph<'a, 'text> { + #[inline] + pub fn new(info: &'a BidiInfo<'text>, para: &'a ParagraphInfo) -> Paragraph<'a, 'text> { + Paragraph { info, para } + } + + /// Returns if the paragraph is Left direction, right direction or mixed. + #[inline] + pub fn direction(&self) -> Direction { + para_direction(&self.info.levels[self.para.range.clone()]) + } + + /// Returns the `Level` of a certain character in the paragraph. + #[inline] + pub fn level_at(&self, pos: usize) -> Level { + let actual_position = self.para.range.start + pos; + self.info.levels[actual_position] + } +} + +/// Implementation of TextSource for UTF-16 text in a [u16] array. +/// Note that there could be unpaired surrogates present! + +// Convenience functions to check whether a UTF16 code unit is a surrogate. +#[inline] +fn is_high_surrogate(code: u16) -> bool { + (code & 0xFC00) == 0xD800 +} +#[inline] +fn is_low_surrogate(code: u16) -> bool { + (code & 0xFC00) == 0xDC00 +} + +impl<'text> TextSource<'text> for [u16] { + type CharIter = Utf16CharIter<'text>; + type CharIndexIter = Utf16CharIndexIter<'text>; + type IndexLenIter = Utf16IndexLenIter<'text>; + + #[inline] + fn len(&self) -> usize { + (self as &[u16]).len() + } + fn char_at(&self, index: usize) -> Option<(char, usize)> { + if index >= self.len() { + return None; + } + // Get the indicated code unit and try simply converting it to a char; + // this will fail if it is half of a surrogate pair. + let c = self[index]; + if let Some(ch) = char::from_u32(c.into()) { + return Some((ch, 1)); + } + // If it's a low surrogate, and was immediately preceded by a high surrogate, + // then we're in the middle of a (valid) character, and should return None. + if is_low_surrogate(c) && index > 0 && is_high_surrogate(self[index - 1]) { + return None; + } + // Otherwise, try to decode, returning REPLACEMENT_CHARACTER for errors. + if let Some(ch) = char::decode_utf16(self[index..].iter().cloned()).next() { + if let Ok(ch) = ch { + // This must be a surrogate pair, otherwise char::from_u32() above should + // have succeeded! + debug_assert!(ch.len_utf16() == 2, "BMP should have already been handled"); + return Some((ch, ch.len_utf16())); + } + } else { + debug_assert!( + false, + "Why did decode_utf16 return None when we're not at the end?" + ); + return None; + } + // Failed to decode UTF-16: we must have encountered an unpaired surrogate. + // Return REPLACEMENT_CHARACTER (not None), to continue processing the following text + // and keep indexing correct. + Some((char::REPLACEMENT_CHARACTER, 1)) + } + #[inline] + fn subrange(&self, range: Range<usize>) -> &Self { + &(self as &[u16])[range] + } + #[inline] + fn chars(&'text self) -> Self::CharIter { + Utf16CharIter::new(&self) + } + #[inline] + fn char_indices(&'text self) -> Self::CharIndexIter { + Utf16CharIndexIter::new(&self) + } + #[inline] + fn indices_lengths(&'text self) -> Self::IndexLenIter { + Utf16IndexLenIter::new(&self) + } + #[inline] + fn char_len(ch: char) -> usize { + ch.len_utf16() + } +} + +/// Iterator over UTF-16 text in a [u16] slice, returning (index, char_len) tuple. +#[derive(Debug)] +pub struct Utf16IndexLenIter<'text> { + text: &'text [u16], + cur_pos: usize, +} + +impl<'text> Utf16IndexLenIter<'text> { + #[inline] + pub fn new(text: &'text [u16]) -> Self { + Utf16IndexLenIter { text, cur_pos: 0 } + } +} + +impl Iterator for Utf16IndexLenIter<'_> { + type Item = (usize, usize); + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + if let Some((_, char_len)) = self.text.char_at(self.cur_pos) { + let result = (self.cur_pos, char_len); + self.cur_pos += char_len; + return Some(result); + } + None + } +} + +/// Iterator over UTF-16 text in a [u16] slice, returning (index, char) tuple. +#[derive(Debug)] +pub struct Utf16CharIndexIter<'text> { + text: &'text [u16], + cur_pos: usize, +} + +impl<'text> Utf16CharIndexIter<'text> { + pub fn new(text: &'text [u16]) -> Self { + Utf16CharIndexIter { text, cur_pos: 0 } + } +} + +impl Iterator for Utf16CharIndexIter<'_> { + type Item = (usize, char); + + fn next(&mut self) -> Option<Self::Item> { + if let Some((ch, char_len)) = self.text.char_at(self.cur_pos) { + let result = (self.cur_pos, ch); + self.cur_pos += char_len; + return Some(result); + } + None + } +} + +/// Iterator over UTF-16 text in a [u16] slice, returning Unicode chars. +/// (Unlike the other iterators above, this also supports reverse iteration.) +#[derive(Debug)] +pub struct Utf16CharIter<'text> { + text: &'text [u16], + cur_pos: usize, + end_pos: usize, +} + +impl<'text> Utf16CharIter<'text> { + pub fn new(text: &'text [u16]) -> Self { + Utf16CharIter { + text, + cur_pos: 0, + end_pos: text.len(), + } + } +} + +impl Iterator for Utf16CharIter<'_> { + type Item = char; + + fn next(&mut self) -> Option<Self::Item> { + if let Some((ch, char_len)) = self.text.char_at(self.cur_pos) { + self.cur_pos += char_len; + return Some(ch); + } + None + } +} + +impl DoubleEndedIterator for Utf16CharIter<'_> { + fn next_back(&mut self) -> Option<Self::Item> { + if self.end_pos <= self.cur_pos { + return None; + } + self.end_pos -= 1; + if let Some(ch) = char::from_u32(self.text[self.end_pos] as u32) { + return Some(ch); + } + if self.end_pos > self.cur_pos { + if let Some((ch, char_len)) = self.text.char_at(self.end_pos - 1) { + if char_len == 2 { + self.end_pos -= 1; + return Some(ch); + } + } + } + Some(char::REPLACEMENT_CHARACTER) + } +} |