Upgrade unicode-bidi to 0.3.15 am: 1ab7a07061

Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/unicode-bidi/+/2950807

Change-Id: I14d9a3b40c0486cf544654d3abd745dec7c3b633
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
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 @@
           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
diff --git a/.gitignore b/.gitignore
index 2ee9aa6..5bf8684 100644
--- a/.gitignore
+++ b/.gitignore
@@ -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"
diff --git a/Android.bp b/Android.bp
index df86c52..a0a5af6 100644
--- a/Android.bp
+++ b/Android.bp
@@ -43,7 +43,7 @@
     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 @@
     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"
diff --git a/Cargo.toml b/Cargo.toml
index 73aff86..80f71ff 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -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"
diff --git a/METADATA b/METADATA
index 2b51f3e..a004976 100644
--- a/METADATA
+++ b/METADATA
@@ -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 @@
             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 @@
     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 @@
     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 @@
         }
 
         // 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 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 @@
                     // 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 @@
                                 }
                                 *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 @@
 ///
 /// <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 @@
         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 @@
         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 @@
 
             // 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 @@
                     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 @@
 /// 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 @@
     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 @@
 /// <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 @@
     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
diff --git a/src/lib.rs b/src/lib.rs
index 81d4fb5..1072b67 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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 deprecated;
 pub mod format_chars;
 pub mod level;
+pub mod utf16;
 
 mod char_data;
 mod explicit;
@@ -94,13 +94,69 @@
 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 @@
 }
 
 /// 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 @@
         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
+    }
+}
 
-        // 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();
+/// 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>,
 
-        let mut para_start = 0;
-        let mut para_level = default_para_level;
+    /// 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)),
+        );
+
+        InitialInfoExt {
+            base: InitialInfo {
+                text,
+                original_classes,
+                paragraphs,
+            },
+            pure_ltr,
+        }
+    }
+}
+
+/// 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
+        }
+    );
+
+    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;
+
+    #[cfg(feature = "flame_it")]
+    flame::start("compute_initial_info(): iter text.char_indices()");
+
+    for (i, c) in text.char_indices() {
+        let class = data_source.bidi_class(c);
 
         #[cfg(feature = "flame_it")]
-        flame::start("InitialInfo::new(): iter text.char_indices()");
+        flame::start("original_classes.extend()");
 
-        for (i, c) in text.char_indices() {
-            let class = data_source.bidi_class(c);
+        let len = T::char_len(c);
+        original_classes.extend(repeat(class).take(len));
 
-            #[cfg(feature = "flame_it")]
-            flame::start("original_classes.extend()");
+        #[cfg(feature = "flame_it")]
+        flame::end("original_classes.extend()");
 
-            original_classes.extend(repeat(class).take(c.len_utf8()));
-
-            #[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 };
-                                }
-                            }
-                        }
-
-                        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 });
+            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 };
                             }
                         }
                     }
-                }
 
-                RLI | LRI | FSI => {
-                    isolate_stack.push(i);
+                    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 });
+                        }
+                    }
                 }
-
-                PDI => {
-                    isolate_stack.pop();
-                }
-
-                _ => {}
             }
+
+            AN | LRE | RLE | LRO | RLO => {
+                is_pure_ltr = false;
+            }
+
+            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());
-
-        #[cfg(feature = "flame_it")]
-        flame::end("InitialInfo::new(): iter text.char_indices()");
-
-        InitialInfo {
-            text,
-            original_classes,
-            paragraphs,
-        }
+        debug_assert_eq!(paragraphs.len(), pure_ltr.len());
     }
+    debug_assert_eq!(original_classes.len(), text.len());
+
+    #[cfg(feature = "flame_it")]
+    flame::end("compute_initial_info(): iter text.char_indices()");
+
+    (
+        original_classes,
+        para_level.unwrap_or(LTR_LEVEL),
+        is_pure_ltr,
+    )
 }
 
 /// Bidi information of the text.
@@ -308,6 +456,7 @@
     /// 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 @@
         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 &paragraphs {
+        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 @@
     }
 
     /// 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 @@
     ///
     /// 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,170 +607,47 @@
     /// 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>) {
-        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()];
-
-        // 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;
-                }
-            }
-            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;
-            }
-        }
-
-        // 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);
-            }
-        }
-        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");
-
-        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;
-                }
-
-                // 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;
-                }
-
-                // Reverse the runs within this sequence.
-                runs[seq_start..seq_end].reverse();
-
-                seq_start = seq_end;
-            }
-            max_level
-                .lower(1)
-                .expect("Lowering embedding level below zero");
-        }
-
-        (levels, runs)
+        let levels = self.reordered_levels(para, line.clone());
+        visual_runs_for_line(levels, &line)
     }
 
     /// If processed text has any computed RTL levels
@@ -618,6 +659,508 @@
     }
 }
 
+/// 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,
+            &para_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());
+
+        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, 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;
+            }
+
+            // 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;
+                }
+                seq_end += 1;
+            }
+            // Reverse the runs within this sequence.
+            runs[seq_start..seq_end].reverse();
+
+            seq_start = seq_end;
+        }
+        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;
+        }
+
+        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;
+        }
+
+        start_index..end_index
+    }
+
+    // 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.
+
+    if levels.is_empty() {
+        return vec![];
+    }
+
+    // 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))
+        });
+
+    // Initialize an index map
+    let mut result: Vec<usize> = (0..levels.len()).collect();
+
+    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();
+
+            if range.end >= levels.len() {
+                break;
+            }
+        }
+
+        max.lower(1).expect("Level error");
+    }
+
+    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;
+        }
+    }
+}
+
 /// 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`.
@@ -628,42 +1171,53 @@
 }
 
 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;
-            }
-
-            if self.info.levels[i].is_rtl() {
-                rtl = true;
-            }
-        }
-
-        if ltr && rtl {
-            return Direction::Mixed;
-        }
-
-        if ltr {
-            return Direction::Ltr;
-        }
-
-        Direction::Rtl
+        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]
     }
 }
 
+/// 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 level.is_rtl() {
+            rtl = true;
+            if ltr {
+                return Direction::Mixed;
+            }
+        }
+    }
+
+    if ltr {
+        return Direction::Ltr;
+    }
+
+    Direction::Rtl
+}
+
 /// Assign levels to characters removed by rule X9.
 ///
 /// The levels assigned to these characters are not specified by the algorithm.  This function
@@ -677,46 +1231,256 @@
     }
 }
 
+/// 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 @@
                         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 @@
                         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,
+                }],
+            ),
+        ];
 
-        // 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]);
+        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),
+                    }
+                )
+            }
+        }
+    }
+
+    #[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);
+        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),
+        ];
 
-        // 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);
+        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 @@
             .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"]
-        );
+        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&[דג(בא"]),
+        ];
 
-        // 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&[דג(בא"]);
+        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 @@
             .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}";
+        let text = &to_utf16(text);
+        let bidi_info = BidiInfoU16::new(text, None);
         assert_eq!(
-            reordered_levels_for_paras(text),
-            vec![Level::vec(&[1, 1, 1, 1, 1, 2, 2])]
+            bidi_info.reordered_levels(&bidi_info.paragraphs[0], 1..4),
+            Level::vec(&[0, 0, 0, 1, 1]),
         );
-        assert_eq!(
-            reordered_levels_per_char_for_paras(text),
-            vec![Level::vec(&[1, 1, 2])]
-        );
-         */
-
-        /* TODO
-        // BidiTest:291284 (AN RLI PDF R)
-        assert_eq!(
-            reordered_levels_per_char_for_paras("\u{0605}\u{2067}\u{202C}\u{0590}"),
-            vec![&["2", "0", "x", "1"]]
-        );
-         */
     }
 
     #[test]
@@ -1036,6 +2048,19 @@
         // 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 @@
         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 @@
         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 @@
         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 @@
         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 @@
 }
 
 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,
+            &para_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)
+    }
+}