Skip to main content

text_typeset/shaping/
shaper.rs

1use harfrust::{Buffer, Direction, Feature, ShapeOptions, ShaperFont, Tag};
2
3use crate::font::registry::FontRegistry;
4use crate::font::resolve::ResolvedFont;
5use crate::shaping::run::{ShapedGlyph, ShapedRun};
6use crate::types::FontFeature;
7
8/// Convert public [`FontFeature`] toggles into harfrust [`Feature`]s,
9/// applied across the whole shaped string (global range). Script-mandated
10/// features apply regardless; these are the discretionary toggles.
11pub fn to_harfrust_features(features: &[FontFeature]) -> Vec<Feature> {
12    features
13        .iter()
14        .map(|f| Feature::new(Tag::new(&f.tag), f.value, ..))
15        .collect()
16}
17
18/// Read units-per-em for a font face.
19///
20/// `harfrust::FontRef` is a thin wrapper over read-fonts and exposes
21/// the `head` table only through the `read_fonts::TableProvider` trait,
22/// which harfrust doesn't re-export. Since we already depend on swash
23/// for `font_metrics_px` further down, we reuse swash's `Metrics` to
24/// pull UPEM — one less dependency surface to maintain.
25fn units_per_em(bytes: &[u8], face_index: u32) -> Option<u16> {
26    let font_ref = swash::FontRef::from_index(bytes, face_index as usize)?;
27    let upem = font_ref.metrics(&[]).units_per_em;
28    if upem == 0 { None } else { Some(upem) }
29}
30
31/// Text direction for shaping.
32#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
33pub enum TextDirection {
34    /// Auto-detect from text content (default).
35    #[default]
36    Auto,
37    LeftToRight,
38    RightToLeft,
39}
40
41/// Shape a text string with the given resolved font.
42///
43/// Returns a ShapedRun with glyph IDs and pixel-space positions.
44/// The `text_offset` is the byte offset of this text within the block
45/// (used for cluster mapping back to document positions).
46/// Shape a text string with automatic glyph fallback.
47///
48/// After shaping with the primary font, any .notdef glyphs (glyph_id==0)
49/// are detected and re-shaped with fallback fonts. If no fallback font
50/// covers a character, it remains as .notdef (renders as blank space
51/// with correct advance).
52pub fn shape_text(
53    registry: &FontRegistry,
54    resolved: &ResolvedFont,
55    text: &str,
56    text_offset: usize,
57) -> Option<ShapedRun> {
58    shape_text_with_fallback(
59        registry,
60        resolved,
61        text,
62        text_offset,
63        TextDirection::Auto,
64        &[],
65    )
66}
67
68/// Shape text with an explicit direction and glyph fallback.
69///
70/// Like `shape_text`, but caller supplies the direction instead of letting
71/// rustybuzz guess. Used by the bidi-aware layout path, which splits text
72/// into directional runs before shaping.
73pub fn shape_text_with_fallback(
74    registry: &FontRegistry,
75    resolved: &ResolvedFont,
76    text: &str,
77    text_offset: usize,
78    direction: TextDirection,
79    features: &[Feature],
80) -> Option<ShapedRun> {
81    let mut run = shape_text_directed(registry, resolved, text, text_offset, direction, features)?;
82    let breaks = blank_hard_breaks(text, &mut run);
83
84    // Check for .notdef glyphs and attempt fallback. A hard break is glyph 0
85    // on purpose: no font is looked for to draw it.
86    if run.glyphs.iter().filter(|g| g.glyph_id == 0).count() > breaks && !text.is_empty() {
87        apply_glyph_fallback(registry, resolved, text, text_offset, features, &mut run);
88        // A break beside a character the primary font lacks is re-shaped with
89        // it, in a font that may well draw it.
90        blank_hard_breaks(text, &mut run);
91    }
92
93    Some(run)
94}
95
96/// Whether `glyph` stands for a hard line break of `text`, the text its run was shaped
97/// from.
98fn is_hard_break_glyph(text: &str, glyph: &ShapedGlyph) -> bool {
99    text.get(glyph.cluster as usize..)
100        .and_then(|rest| rest.chars().next())
101        .is_some_and(crate::types::is_hard_break)
102}
103
104/// Lay out every hard line break in `run` as nothing: glyph 0, which is never
105/// drawn, with no advance and no offset (see [`crate::types::is_hard_break`]).
106/// Returns how many there are.
107///
108/// A font draws a line separator as it likes (a box, a pilcrow) or not at all,
109/// and gives it whatever advance it likes, which pushed a right-aligned or
110/// centred line off its place by that much.
111fn blank_hard_breaks(text: &str, run: &mut ShapedRun) -> usize {
112    let mut count = 0;
113    for glyph in &mut run.glyphs {
114        if is_hard_break_glyph(text, glyph) {
115            glyph.glyph_id = 0;
116            glyph.x_advance = 0.0;
117            glyph.x_offset = 0.0;
118            glyph.y_offset = 0.0;
119            count += 1;
120        }
121    }
122    if count > 0 {
123        run.advance_width = run.glyphs.iter().map(|g| g.x_advance).sum();
124    }
125    count
126}
127
128/// Re-shape .notdef glyphs using fallback fonts.
129///
130/// Works on **spans** of consecutive .notdef glyphs, not on glyphs one at a
131/// time: each span is mapped back to the character range that produced it and
132/// that whole range is re-shaped in the fallback font, then spliced in.
133///
134/// Shaping a span as a unit is what makes complex scripts survive fallback.
135/// Re-shaping character by character — which this used to do — cannot join
136/// Arabic, because a letter shaped alone has no neighbours and can only take
137/// its isolated form. It also kept only the *first* glyph of each result, so
138/// any letter whose isolated form is a base plus a mark lost the mark. An
139/// Arabic word set in a font without Arabic came out as disconnected,
140/// dotless stumps.
141///
142/// A span is re-shaped with the run's own direction rather than `Auto`, so
143/// the substituted glyphs come back in the same visual order as the ones
144/// around them.
145fn apply_glyph_fallback(
146    registry: &FontRegistry,
147    primary: &ResolvedFont,
148    text: &str,
149    text_offset: usize,
150    features: &[Feature],
151    run: &mut ShapedRun,
152) {
153    use crate::font::resolve::find_fallback_font;
154
155    // Maximal spans of consecutive .notdef glyphs, as index ranges. A hard break
156    // is glyph 0 on purpose (see `blank_hard_breaks`) and ends a span: inside one it
157    // would choose the span's font, since a span is re-shaped in the font that draws
158    // its first character, and a character beside it would lose its own.
159    let missing = |glyph: &ShapedGlyph| glyph.glyph_id == 0 && !is_hard_break_glyph(text, glyph);
160    let mut spans: Vec<std::ops::Range<usize>> = Vec::new();
161    let mut i = 0;
162    while i < run.glyphs.len() {
163        if missing(&run.glyphs[i]) {
164            let start = i;
165            while i < run.glyphs.len() && missing(&run.glyphs[i]) {
166                i += 1;
167            }
168            spans.push(start..i);
169        } else {
170            i += 1;
171        }
172    }
173    if spans.is_empty() {
174        return;
175    }
176
177    // Splice from the back so earlier ranges stay valid as lengths change.
178    for span in spans.into_iter().rev() {
179        let Some((byte_start, byte_end)) = notdef_char_range(&run.glyphs, &span, text) else {
180            continue;
181        };
182        let Some(slice) = text.get(byte_start..byte_end) else {
183            continue;
184        };
185        let Some(first_char) = slice.chars().next() else {
186            continue;
187        };
188
189        let Some(fallback_id) = find_fallback_font(registry, first_char, primary.font_face_id)
190        else {
191            continue; // no fallback available — leave the span as .notdef
192        };
193        let Some(fallback_entry) = registry.get(fallback_id) else {
194            continue;
195        };
196
197        let fallback_resolved = ResolvedFont {
198            font_face_id: fallback_id,
199            size_px: primary.size_px,
200            face_index: fallback_entry.face_index,
201            swash_cache_key: fallback_entry.swash_cache_key,
202            scale_factor: primary.scale_factor,
203            weight: primary.weight,
204        };
205
206        let Some(fallback_run) = shape_text_directed(
207            registry,
208            &fallback_resolved,
209            slice,
210            text_offset + byte_start,
211            run.direction,
212            features,
213        ) else {
214            continue;
215        };
216        if fallback_run.glyphs.is_empty() {
217            continue;
218        }
219
220        // Clusters come back local to `slice`; lift them into `text` space,
221        // which is what the rest of the pipeline expects of this run.
222        let replacement: Vec<ShapedGlyph> = fallback_run
223            .glyphs
224            .into_iter()
225            .map(|mut g| {
226                g.cluster += byte_start as u32;
227                g.font_face_id = fallback_id;
228                g
229            })
230            .collect();
231
232        run.glyphs.splice(span, replacement);
233    }
234
235    run.advance_width = run.glyphs.iter().map(|g| g.x_advance).sum();
236}
237
238/// The byte range of `text` that a span of consecutive .notdef glyphs covers.
239///
240/// Glyphs sit in visual order, so clusters ascend across an LTR run and
241/// descend across an RTL one. Taking the min and max over the span rather
242/// than its first and last glyph keeps this direction-agnostic.
243///
244/// The span's end is the nearest cluster *after* it among the glyphs outside
245/// it — the start of whatever the primary font did manage to shape — or the
246/// end of the text when the span runs to the edge.
247fn notdef_char_range(
248    glyphs: &[ShapedGlyph],
249    span: &std::ops::Range<usize>,
250    text: &str,
251) -> Option<(usize, usize)> {
252    let inside = glyphs.get(span.clone())?;
253    let start = inside.iter().map(|g| g.cluster as usize).min()?;
254    let last = inside.iter().map(|g| g.cluster as usize).max()?;
255
256    let end = glyphs
257        .iter()
258        .enumerate()
259        .filter(|(i, _)| !span.contains(i))
260        .map(|(_, g)| g.cluster as usize)
261        .filter(|&c| c > last)
262        .min()
263        .unwrap_or(text.len());
264
265    if start >= end || !text.is_char_boundary(start) || !text.is_char_boundary(end) {
266        return None;
267    }
268    Some((start, end))
269}
270
271/// Shape text with an explicit direction.
272pub fn shape_text_directed(
273    registry: &FontRegistry,
274    resolved: &ResolvedFont,
275    text: &str,
276    text_offset: usize,
277    direction: TextDirection,
278    features: &[Feature],
279) -> Option<ShapedRun> {
280    let entry = registry.get(resolved.font_face_id)?;
281    let font = entry.shaping_font()?;
282
283    let upem = units_per_em(entry.bytes(), entry.face_index).unwrap_or(0) as f32;
284    if upem == 0.0 {
285        return None;
286    }
287    // Shape at physical ppem, then divide results by scale_factor so
288    // downstream layout stays in logical pixels. See ResolvedFont.
289    let sf = resolved.scale_factor.max(f32::MIN_POSITIVE);
290    let physical_size = resolved.size_px * sf;
291    let physical_scale = physical_size / upem;
292    let inv_sf = 1.0 / sf;
293
294    let mut buffer = Buffer::new();
295    buffer.push_str(text);
296    match direction {
297        TextDirection::LeftToRight => buffer.set_direction(Direction::LeftToRight),
298        TextDirection::RightToLeft => buffer.set_direction(Direction::RightToLeft),
299        TextDirection::Auto => {}
300    }
301    // Always guess, including after an explicit set_direction. The guess
302    // only fills in what is still unset — it assigns `script` when it is
303    // `None` and `direction` when it is `Invalid` — so the caller's
304    // direction survives untouched and the script gets populated.
305    //
306    // That script is what picks the shaper: with `script: None` harfrust
307    // falls back to DEFAULT_SHAPER, which never requests init/medi/fina/
308    // isol, and Arabic comes out in disconnected isolated forms. Setting
309    // it selects ARABIC_SHAPER and the letters join. It also keeps
310    // harfrust from panicking on a still-Invalid direction in the Auto
311    // case, which is why this call used to live in that branch alone.
312    buffer.guess_segment_properties();
313
314    // Resolve the concrete direction (Auto is now decided by the buffer).
315    // Stored on the run so hit-testing knows RTL glyph order.
316    let resolved_direction = if buffer.direction() == Direction::RightToLeft {
317        TextDirection::RightToLeft
318    } else {
319        TextDirection::LeftToRight
320    };
321
322    // The font is opened once per face and cached on the FontEntry, and
323    // it keeps its preprocessed tables, so repeated shape calls (every
324    // relayout/keystroke) reuse them; the ShaperFont over it is cheap.
325    harfrust::shape(
326        &ShaperFont::new(font),
327        &mut buffer,
328        ShapeOptions::new().features(features),
329    )
330    .ok()?;
331
332    let infos = buffer.glyph_infos();
333    let positions = buffer.glyph_positions();
334
335    let mut glyphs = Vec::with_capacity(infos.len());
336    let mut total_advance = 0.0f32;
337
338    for (info, pos) in infos.iter().zip(positions.iter()) {
339        let x_advance = pos.x_advance as f32 * physical_scale * inv_sf;
340        let y_advance = pos.y_advance as f32 * physical_scale * inv_sf;
341        let x_offset = pos.x_offset as f32 * physical_scale * inv_sf;
342        let y_offset = pos.y_offset as f32 * physical_scale * inv_sf;
343
344        glyphs.push(ShapedGlyph {
345            glyph_id: info.glyph_id as u16,
346            cluster: info.cluster,
347            x_advance,
348            y_advance,
349            x_offset,
350            y_offset,
351            font_face_id: resolved.font_face_id,
352        });
353
354        total_advance += x_advance;
355    }
356
357    Some(ShapedRun {
358        font_face_id: resolved.font_face_id,
359        size_px: resolved.size_px,
360        weight: resolved.weight,
361        glyphs,
362        advance_width: total_advance,
363        text_range: text_offset..text_offset + text.len(),
364        direction: resolved_direction,
365        bidi_level: if resolved_direction == TextDirection::RightToLeft {
366            1
367        } else {
368            0
369        },
370        underline_style: crate::types::UnderlineStyle::None,
371        overline: false,
372        strikeout: false,
373        is_link: false,
374        foreground_color: None,
375        underline_color: None,
376        background_color: None,
377        anchor_href: None,
378        tooltip: None,
379        vertical_alignment: crate::types::VerticalAlignment::Normal,
380        image_name: None,
381        image_height: 0.0,
382    })
383}
384
385/// Shape a text string, reusing a harfrust `Buffer` to avoid allocations.
386pub fn shape_text_with_buffer(
387    registry: &FontRegistry,
388    resolved: &ResolvedFont,
389    text: &str,
390    text_offset: usize,
391    buffer: Buffer,
392    features: &[Feature],
393) -> Option<(ShapedRun, Buffer)> {
394    let entry = registry.get(resolved.font_face_id)?;
395    let font = entry.shaping_font()?;
396
397    let upem = units_per_em(entry.bytes(), entry.face_index).unwrap_or(0) as f32;
398    if upem == 0.0 {
399        return None;
400    }
401    let sf = resolved.scale_factor.max(f32::MIN_POSITIVE);
402    let physical_size = resolved.size_px * sf;
403    let physical_scale = physical_size / upem;
404    let inv_sf = 1.0 / sf;
405
406    let mut buffer = buffer;
407    buffer.push_str(text);
408    // Recycled buffers come back without segment properties; explicitly
409    // guess them so harfrust doesn't panic on Direction::Invalid.
410    buffer.guess_segment_properties();
411
412    let resolved_direction = if buffer.direction() == Direction::RightToLeft {
413        TextDirection::RightToLeft
414    } else {
415        TextDirection::LeftToRight
416    };
417
418    harfrust::shape(
419        &ShaperFont::new(font),
420        &mut buffer,
421        ShapeOptions::new().features(features),
422    )
423    .ok()?;
424
425    let infos = buffer.glyph_infos();
426    let positions = buffer.glyph_positions();
427
428    let mut glyphs = Vec::with_capacity(infos.len());
429    let mut total_advance = 0.0f32;
430
431    for (info, pos) in infos.iter().zip(positions.iter()) {
432        let x_advance = pos.x_advance as f32 * physical_scale * inv_sf;
433        let y_advance = pos.y_advance as f32 * physical_scale * inv_sf;
434        let x_offset = pos.x_offset as f32 * physical_scale * inv_sf;
435        let y_offset = pos.y_offset as f32 * physical_scale * inv_sf;
436
437        glyphs.push(ShapedGlyph {
438            glyph_id: info.glyph_id as u16,
439            cluster: info.cluster,
440            x_advance,
441            y_advance,
442            x_offset,
443            y_offset,
444            font_face_id: resolved.font_face_id,
445        });
446
447        total_advance += x_advance;
448    }
449
450    let run = ShapedRun {
451        font_face_id: resolved.font_face_id,
452        size_px: resolved.size_px,
453        weight: resolved.weight,
454        glyphs,
455        advance_width: total_advance,
456        text_range: text_offset..text_offset + text.len(),
457        direction: resolved_direction,
458        bidi_level: if resolved_direction == TextDirection::RightToLeft {
459            1
460        } else {
461            0
462        },
463        underline_style: crate::types::UnderlineStyle::None,
464        overline: false,
465        strikeout: false,
466        is_link: false,
467        foreground_color: None,
468        underline_color: None,
469        background_color: None,
470        anchor_href: None,
471        tooltip: None,
472        vertical_alignment: crate::types::VerticalAlignment::Normal,
473        image_name: None,
474        image_height: 0.0,
475    };
476    let mut run = run;
477    blank_hard_breaks(text, &mut run);
478
479    // Reclaim the buffer for reuse: clearing keeps the allocation and
480    // drops the contents and segment properties.
481    buffer.clear();
482    Some((run, buffer))
483}
484
485pub struct FontMetricsPx {
486    pub ascent: f32,
487    pub descent: f32,
488    pub leading: f32,
489    pub underline_offset: f32,
490    pub strikeout_offset: f32,
491    pub stroke_size: f32,
492}
493
494/// Get font metrics (ascent, descent, leading) scaled to logical pixels.
495///
496/// Scales at `size_px * scale_factor` (physical) and divides by
497/// `scale_factor`, so callers always see logical-pixel metrics.
498pub fn font_metrics_px(registry: &FontRegistry, resolved: &ResolvedFont) -> Option<FontMetricsPx> {
499    let entry = registry.get(resolved.font_face_id)?;
500    let font_ref = swash::FontRef::from_index(entry.bytes(), entry.face_index as usize)?;
501    let sf = resolved.scale_factor.max(f32::MIN_POSITIVE);
502    let physical_size = resolved.size_px * sf;
503    let metrics = font_ref.metrics(&[]).scale(physical_size);
504    let inv_sf = 1.0 / sf;
505
506    Some(FontMetricsPx {
507        ascent: metrics.ascent * inv_sf,
508        descent: metrics.descent * inv_sf,
509        leading: metrics.leading * inv_sf,
510        underline_offset: metrics.underline_offset * inv_sf,
511        strikeout_offset: metrics.strikeout_offset * inv_sf,
512        stroke_size: metrics.stroke_size * inv_sf,
513    })
514}
515
516/// A bidi run: a contiguous range of text with the same direction.
517pub struct BidiRun {
518    pub byte_range: std::ops::Range<usize>,
519    pub direction: TextDirection,
520    /// Visual order index (for reordering after line breaking).
521    pub visual_order: usize,
522    /// UAX #9 embedding level: even is LTR, odd is RTL.
523    ///
524    /// Rule L2 reorders by level, not by direction, and the two are not
525    /// interchangeable: a Latin phrase quoted inside Arabic inside an
526    /// English paragraph sits at level 2, and reordering it as though it
527    /// were level 0 puts it on the wrong side of the Arabic. `direction`
528    /// cannot tell those apart — `level` can.
529    pub level: u8,
530}
531
532/// A paragraph's bidi structure in **logical** order.
533///
534/// [`bidi_runs`] returns runs already reordered for display, which suits
535/// a single-line label that is shaped and painted in one go. The
536/// multi-line editor cannot use that: line breaking is a logical
537/// operation, so runs have to stay in logical order until the breaker has
538/// decided where the lines fall, and only then get reordered *per line*.
539/// Reordering the paragraph up front and breaking afterwards would
540/// scramble any paragraph that wraps.
541pub struct BidiParagraph {
542    /// Runs of uniform embedding level, in logical order.
543    pub runs: Vec<BidiRun>,
544    /// The paragraph embedding level actually used — the explicit base
545    /// direction when one was given, else the rule P2/P3 auto-detection.
546    pub para_level: u8,
547}
548
549impl BidiParagraph {
550    /// The paragraph's base direction, as resolved.
551    pub fn base_direction(&self) -> TextDirection {
552        if self.para_level % 2 == 1 {
553            TextDirection::RightToLeft
554        } else {
555            TextDirection::LeftToRight
556        }
557    }
558}
559
560/// The unicode-bidi paragraph level that expresses `base`.
561///
562/// `None` asks unicode-bidi to auto-detect (rules P2/P3: the first strong
563/// character wins, defaulting to LTR when the text has none). An explicit
564/// level overrides that — which is the point of honouring a stored
565/// paragraph direction, since P2/P3 incorrectly classifies any RTL
566/// paragraph that happens to open with a digit, a Latin acronym or an
567/// opening quote.
568fn base_para_level(base: TextDirection) -> Option<unicode_bidi::Level> {
569    match base {
570        TextDirection::Auto => None,
571        TextDirection::LeftToRight => Some(unicode_bidi::Level::ltr()),
572        TextDirection::RightToLeft => Some(unicode_bidi::Level::rtl()),
573    }
574}
575
576/// Resolve `text`'s bidi structure under an explicit or auto base direction.
577///
578/// Runs come back in logical order, each tagged with its embedding level.
579/// Callers shape each run with its own direction and later reorder the
580/// runs of each line with [`visual_order`].
581pub fn analyze_paragraph(text: &str, base: TextDirection) -> BidiParagraph {
582    use unicode_bidi::BidiInfo;
583
584    if text.is_empty() {
585        return BidiParagraph {
586            runs: Vec::new(),
587            para_level: base_para_level(base).map_or(0, |l| l.number()),
588        };
589    }
590
591    let bidi_info = BidiInfo::new(text, base_para_level(base));
592
593    // A block is one paragraph as far as layout is concerned; if the text
594    // somehow carries a hard break, the first paragraph's level is the
595    // one that governs alignment.
596    let para_level = bidi_info
597        .paragraphs
598        .first()
599        .map(|p| p.level.number())
600        .or_else(|| base_para_level(base).map(|l| l.number()))
601        .unwrap_or(0);
602
603    // Group consecutive characters of equal level. Iterating by
604    // `char_indices` rather than by byte keeps a run boundary from ever
605    // landing inside a multi-byte character.
606    let mut starts: Vec<(usize, u8)> = Vec::new();
607    for (idx, _) in text.char_indices() {
608        let level = bidi_info.levels[idx].number();
609        if starts.last().map(|&(_, l)| l) != Some(level) {
610            starts.push((idx, level));
611        }
612    }
613
614    // Each run ends where the next begins; the last ends with the text.
615    let ends = starts
616        .iter()
617        .skip(1)
618        .map(|&(start, _)| start)
619        .chain(std::iter::once(text.len()));
620
621    let runs: Vec<BidiRun> = starts
622        .iter()
623        .zip(ends)
624        .map(|(&(start, level), end)| BidiRun {
625            byte_range: start..end,
626            direction: if level % 2 == 1 {
627                TextDirection::RightToLeft
628            } else {
629                TextDirection::LeftToRight
630            },
631            // Always 0 here: these runs are in *logical* order and the
632            // block path reorders per line after breaking, so a
633            // paragraph-wide visual index would be both unused and
634            // misleading. `bidi_runs` fills it in for the single-line
635            // path, which does lay a paragraph out in one go.
636            visual_order: 0,
637            level,
638        })
639        .collect();
640
641    BidiParagraph { runs, para_level }
642}
643
644/// Reorder items from logical into visual order per UAX #9 rule L2.
645///
646/// Returns indices into `levels`: `result[0]` is the item to paint
647/// leftmost. L2 reads "from the highest level down to the lowest odd
648/// level, reverse any contiguous sequence of items at that level or
649/// higher", which is what the loop below does literally.
650pub fn visual_order(levels: &[u8]) -> Vec<usize> {
651    let mut order: Vec<usize> = (0..levels.len()).collect();
652    let Some(&max) = levels.iter().max() else {
653        return order;
654    };
655    // With no odd level nothing is RTL, so logical order is already visual.
656    let Some(min_odd) = levels.iter().copied().filter(|l| l % 2 == 1).min() else {
657        return order;
658    };
659
660    let mut level = max;
661    while level >= min_odd {
662        let mut i = 0;
663        while i < order.len() {
664            if levels[order[i]] >= level {
665                let start = i;
666                while i < order.len() && levels[order[i]] >= level {
667                    i += 1;
668                }
669                order[start..i].reverse();
670            } else {
671                i += 1;
672            }
673        }
674        // min_odd is odd, hence >= 1, so this cannot wrap past zero.
675        level -= 1;
676    }
677    order
678}
679
680/// Analyze text for bidirectional content and return directional runs
681/// in **visual order** per UAX #9 (Unicode Bidirectional Algorithm, rule L2).
682///
683/// The returned runs can be shaped independently and concatenated left-to-right
684/// to produce correctly-ordered mixed-script text (e.g. Latin embedded in
685/// Arabic). For pure-LTR text, returns a single LTR run. For pure-RTL text,
686/// returns a single RTL run.
687pub fn bidi_runs(text: &str) -> Vec<BidiRun> {
688    use unicode_bidi::BidiInfo;
689
690    if text.is_empty() {
691        return Vec::new();
692    }
693
694    let bidi_info = BidiInfo::new(text, None);
695    let mut runs = Vec::new();
696
697    for para in &bidi_info.paragraphs {
698        let (levels, level_runs) = bidi_info.visual_runs(para, para.range.clone());
699        for level_run in level_runs {
700            if level_run.is_empty() {
701                continue;
702            }
703            let level = levels[level_run.start];
704            let direction = if level.is_rtl() {
705                TextDirection::RightToLeft
706            } else {
707                TextDirection::LeftToRight
708            };
709            let visual_order = runs.len();
710            runs.push(BidiRun {
711                byte_range: level_run,
712                direction,
713                visual_order,
714                level: level.number(),
715            });
716        }
717    }
718
719    if runs.is_empty() {
720        runs.push(BidiRun {
721            byte_range: 0..text.len(),
722            direction: TextDirection::LeftToRight,
723            visual_order: 0,
724            level: 0,
725        });
726    }
727
728    runs
729}
730
731#[cfg(test)]
732mod bidi_tests {
733    use super::*;
734
735    const ARABIC: &str = "\u{0643}\u{062A}\u{0628}"; // كتب
736    const HEBREW: &str = "\u{05E9}\u{05DC}\u{05D5}\u{05DD}"; // שלום
737
738    #[test]
739    fn rule_l2_leaves_all_ltr_text_alone() {
740        assert_eq!(visual_order(&[0, 0, 0]), vec![0, 1, 2]);
741        assert_eq!(visual_order(&[]), Vec::<usize>::new());
742    }
743
744    #[test]
745    fn rule_l2_reverses_a_run_of_rtl() {
746        // level 0 "a", level 1 RTL, level 0 "b" -> the RTL span reverses
747        // in place but stays between its neighbours.
748        assert_eq!(visual_order(&[0, 1, 1, 0]), vec![0, 2, 1, 3]);
749    }
750
751    #[test]
752    fn rule_l2_nests_an_ltr_island_inside_rtl() {
753        // An English phrase (level 2) quoted inside Arabic (level 1)
754        // inside an English paragraph (level 0). The level-2 island must
755        // keep its own left-to-right order while the level-1 material
756        // around it reverses — the case `direction` alone cannot express.
757        let levels = [0, 1, 2, 2, 1, 0];
758        assert_eq!(visual_order(&levels), vec![0, 4, 2, 3, 1, 5]);
759    }
760
761    #[test]
762    fn rule_l2_reverses_the_whole_line_in_an_rtl_paragraph() {
763        // Level 1 throughout with a level-2 Latin word: the paragraph
764        // reads right-to-left, so logical item 0 paints rightmost.
765        assert_eq!(visual_order(&[1, 2, 1]), vec![2, 1, 0]);
766    }
767
768    #[test]
769    fn a_leading_digit_does_not_fool_auto_detection() {
770        // Worth pinning, because it is easy to assume otherwise: digits
771        // are type EN, not strong, so rule P2 skips them and finds the
772        // Arabic. An Arabic paragraph opening with a number needs no
773        // explicit direction.
774        let text = "123 \u{0643}\u{062A}\u{0628}";
775        assert_eq!(analyze_paragraph(text, TextDirection::Auto).para_level, 1);
776    }
777
778    #[test]
779    fn an_explicit_base_direction_overrides_first_strong_detection() {
780        // A Latin acronym *is* strong (type L), so rule P2 stops at the
781        // "NASA" and calls this Arabic paragraph left-to-right — the
782        // real false detection, and the reason a stored paragraph
783        // direction has to win over guessing.
784        let text = "NASA \u{0623}\u{0639}\u{0644}\u{0646}\u{062A}";
785        assert_eq!(
786            analyze_paragraph(text, TextDirection::Auto).para_level,
787            0,
788            "auto-detection is expected to get this one wrong"
789        );
790
791        let forced = analyze_paragraph(text, TextDirection::RightToLeft);
792        assert_eq!(forced.para_level, 1);
793        assert_eq!(forced.base_direction(), TextDirection::RightToLeft);
794
795        // And the override genuinely changes the layout, not just the
796        // recorded level: the Arabic now leads visually. Runs come back
797        // in logical order, so ask rule L2 which one paints leftmost —
798        // the same thing a caller laying the paragraph out would do.
799        let auto = analyze_paragraph(text, TextDirection::Auto);
800        let first_visual = |p: &BidiParagraph| {
801            let levels: Vec<u8> = p.runs.iter().map(|r| r.level).collect();
802            visual_order(&levels).first().map(|&i| p.runs[i].direction)
803        };
804        assert_eq!(first_visual(&auto), Some(TextDirection::LeftToRight));
805        assert_eq!(first_visual(&forced), Some(TextDirection::RightToLeft));
806    }
807
808    #[test]
809    fn pure_arabic_auto_detects_as_rtl() {
810        let para = analyze_paragraph(ARABIC, TextDirection::Auto);
811        assert_eq!(para.base_direction(), TextDirection::RightToLeft);
812        assert_eq!(para.runs.len(), 1);
813        assert_eq!(para.runs[0].direction, TextDirection::RightToLeft);
814        assert_eq!(para.runs[0].byte_range, 0..ARABIC.len());
815    }
816
817    #[test]
818    fn runs_come_back_in_logical_order_and_cover_the_text() {
819        // "hello <hebrew> world" — three runs, contiguous, logical order.
820        let text = format!("hello {HEBREW} world");
821        let para = analyze_paragraph(&text, TextDirection::Auto);
822
823        assert!(para.runs.len() >= 2, "expected a directional split");
824        assert_eq!(para.runs[0].byte_range.start, 0);
825        assert_eq!(para.runs.last().unwrap().byte_range.end, text.len());
826        for pair in para.runs.windows(2) {
827            assert_eq!(
828                pair[0].byte_range.end, pair[1].byte_range.start,
829                "runs must tile the text with no gap or overlap"
830            );
831            assert!(
832                pair[0].byte_range.start < pair[1].byte_range.start,
833                "runs must be in logical order"
834            );
835        }
836        assert!(
837            para.runs
838                .iter()
839                .any(|r| r.direction == TextDirection::RightToLeft),
840            "the Hebrew span should have produced an RTL run"
841        );
842    }
843
844    #[test]
845    fn run_boundaries_never_split_a_multibyte_character() {
846        let text = format!("a{ARABIC}b{HEBREW}c");
847        for run in analyze_paragraph(&text, TextDirection::Auto).runs {
848            assert!(
849                text.is_char_boundary(run.byte_range.start)
850                    && text.is_char_boundary(run.byte_range.end),
851                "run {:?} splits a character in {text:?}",
852                run.byte_range
853            );
854        }
855    }
856
857    #[test]
858    fn rule_l2_over_a_real_paragraph_is_a_permutation() {
859        let text = format!("hello {HEBREW} world {ARABIC} end");
860        let para = analyze_paragraph(&text, TextDirection::Auto);
861        let levels: Vec<u8> = para.runs.iter().map(|r| r.level).collect();
862
863        let mut seen = visual_order(&levels);
864        seen.sort_unstable();
865        assert_eq!(
866            seen,
867            (0..para.runs.len()).collect::<Vec<_>>(),
868            "every run must appear exactly once in the visual order"
869        );
870    }
871
872    #[test]
873    fn empty_text_analyzes_without_panicking() {
874        let para = analyze_paragraph("", TextDirection::RightToLeft);
875        assert!(para.runs.is_empty());
876        assert_eq!(para.para_level, 1);
877    }
878}